Skip to content

Proof: ellipsis dot-run normalization is locally idempotent and protection-stable #491

Description

@leynos

Proof target: ellipsis dot-run normalization

Relevant code: src/ellipsis.rs (replace_dot_runs), ADR 0005.

For a maximal unprotected dot run of length n, the implementation emits "…" * (n / 3) followed by "." * (n % 3). Since 0 <= n % 3 < 3, no replaceable triple remains in that run.

Goals

  • Local correctness. replace_dot_runs(s) maps each maximal run of n dots to ⌊n/3⌋ ellipses and n mod 3 dots, and preserves every non-dot character in order.
  • Local idempotence. replace_dot_runs(replace_dot_runs(s)) == replace_dot_runs(s).
  • Protection stability (the important part). A region protected on the first run (URL, path, code span, code block, per ADR 0005) is still protected on the second run. Proving the arithmetic does not establish this; it requires that the emitted ellipsis characters cannot create or destroy a protection boundary.

Implementation recipe

  1. Verify replace_dot_runs over Seq<char> with a spec fn normalize_runs, proving by induction on the run structure. This is a self-contained beginner-level Verus target and a good first kernel for the harness.
  2. Specify the protection predicate spec fn protected(s, i) -> bool for the region scanner in src/ellipsis/; treat the URL/path regexes as external contracts in the ledger.
  3. Prove lemma_ellipsis_char_is_neutral: inserting at an unprotected position does not change protected at any other position. This is the lemma that makes the whole-feature idempotence follow.
  4. Ledger: local correctness and local idempotence; protection stability is a cross-pass result and depends on the fence kernel for code blocks.

Non-vacuity tests

  • Witness proofs: "a....b" yields "a….b"; "......" yields "……"; ".." unchanged.
  • Mutation: emit n % 3 + 1 trailing dots and confirm the idempotence lemma fails on the "......" witness (which would gain a triple).
  • Executable: the existing tests/data ellipsis fixtures plus the fence reproduction from the unmatched-block issue as a negative case (literal... inside a fence must be untouched).

Related issues

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    documentationImprovements or additions to documentationlowBacklog work, hygiene, or technical debt planned opportunistically, without a strict deadline.testingTest coverage, test infrastructure, and verification tooling work.

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions