From the right, two of sixteen

The sweep replaces a queue and a visited set with a sorted list and a cursor. Its correctness rests on one property: an occurrence produced by a phrase lies to the right of the occurrence it was produced from, so every insertion lands ahead of the cursor.

Take the property away and the method does not fail. It returns a shorter answer.

The experiment #

Same collection, same pattern, same phrases, same inner loop. The only change is the order the known occurrences are visited in: descending rather than ascending, with productions inserted into the same list at their sorted position.

The correct traversal reports sixteen occurrences. The reversed one reports two.

It loses fourteen — 87.5% — and one of the two it reports is the primary occurrence the search found rather than anything the propagation produced.

Why it loses them #

In descending order, a larger position comes earlier. A production lies to the right of its source, so it has a larger position, so it belongs earlier in the list — which is behind the cursor, which has already passed.

Every production is therefore inserted into a part of the list the sweep will never revisit.

The one exception is a production that lands in a region the cursor has not reached, which in descending order means a position smaller than the current one — and there are none, because every production is larger.

So the reversed sweep produces exactly the occurrences reachable in one step from a primary, and even those are lost if inserted behind. Two of sixteen.

There is a detail in the reversed implementation worth stating, because a careless version of the experiment would be measuring something else.

The reversed sweep is not simply the ascending one with its input reversed. Its insertion has to be reversed too — a production is inserted at its position in descending order — and its cursor has to be adjusted when an insertion lands before it, so that the list and the cursor stay consistent.

Doing that carefully is what makes the experiment a measurement of the order rather than of a broken list. A version that inserted ascending into a descending list would fail for a different reason and would prove nothing about the ordering property.

So the reversed sweep is a correct implementation of a wrong traversal, which is the thing a rejection test has to be. A walk that does not prune makes the same point about a different defect: the input a rejection constructs has to be something a person would plausibly write.

What makes it silent #

Every occurrence the reversed sweep reports is genuinely an occurrence. The positions are correct, the count is a number, and the pattern really does occur at each of them.

A search returning two positions looks exactly like a search returning two positions. There is no exception, no assertion, no invariant violated by the output, and no property of the answer that distinguishes it from a correct answer to a query with two occurrences.

The only way to see it is to run the other traversal and compare, which is what the rejection test does.

That is the shape this collection has learned to be careful about: a failure that makes an answer shorter rather than wrong. A wrong answer contains something that can be checked; a short one contains nothing.

The second time in two strands #

The same failure, on a different object, one strand earlier.

A document already in the answer is a chainless document listing whose correctness depends on visiting the left subrange before the right. Exchange the two recursions and it loses documents: on a collection of twenty-four documents, over forty patterns, some queries lost on five per cent of them, and the worst reported nine documents against a true seventeen.

Same shape. An ordering that a traversal depends on, a reversal that produces a short answer, and every reported item genuinely present.

Two objects, two strands, one failure mode. That the same defect appeared twice within two strands is what turned “check the order” from a note into a rejection test in both, and it is the reason this essay exists as a separate piece rather than as a paragraph.

The guard, and where it sits #

The rejection test demonstrates the failure and the guard prevents it, and the two are in different places for a reason.

The guard is inside the traversal, at the point of every production: an occurrence produced at or before the current position raises, with both positions in the message. It fires on a parse whose phrases have been modified, or on a different parse whose ordering guarantee is weaker.

The rejection test is outside, and it constructs the wrong traversal deliberately: the same occurrences visited from the right, with productions inserted at their sorted position and the cursor adjusted, and it requires the answer to come back short.

The guard catches a bad parse. The rejection catches a bad traversal. Neither catches the other, and both are needed because the property has two ways of being violated.

That division is worth stating because a single check on the answer would catch both and be unavailable: comparing against the queue’s answer works only if the queue is present, and the whole point of the substitution is that it is not.

The reference implementation as a permanent cost #

Since three optimisations here need a reference implementation to be checkable, it is worth asking whether the references should stay in the code or be deleted once the check has passed.

They stay, and the reason is that a check that has passed once is a check about a version of the code that no longer exists. The parse changes, the index gains a field, an inner loop is rewritten for speed — and each of those can break an ordering argument without touching the traversal that depends on it.

So the queue implementation is kept beside the sweep, permanently, and the two are run against each other on every check. That is a second implementation of a method to maintain, and it is the price of the substitution being verifiable at all.

The alternative — deleting the reference and trusting the argument — is what a published account of this method does, and it is why the ordering property was implicit and unchecked before this strand. An argument in a paper is not a thing that can be run.

The probe formula nobody checks is the general version from the other direction: a formula everybody quotes and nobody runs against the thing it describes. A claim about an optimisation’s correctness needs the unoptimised version to fail against, and an argument in a paper is not one.

What a bound would look like #

There is a version of this failure that is bounded and this one is not, which is worth drawing out.

If the reversed sweep lost a fixed fraction — half, say — its answers would be systematically short and a system might notice a suspicious pattern across many queries.

It loses 87.5% here and would lose a different fraction on a different collection: on two copies it would lose one of two, on a hundred copies it would lose ninety-nine of a hundred. The fraction is the propagation’s depth, which is the collection’s repetitiveness.

So the failure gets worse on exactly the collections the structure is for, and a system testing on a small non-repetitive corpus would see almost no error.

That is the least convenient possible behaviour for a defect and it is a general property of order-dependent traversals: the deeper the structure being traversed, the more an ordering error costs.

What the check must reject #

This collection’s habit is that each site’s machinery ends by being fed input it must refuse, and an assertion that has never rejected anything proves nothing.

The awkwardness with an order-dependent traversal is that the correct traversal never produces the failure, so nothing in a normal run exercises the guard. A test suite running a thousand queries on the correct implementation confirms that the guard does not misfire and says nothing about whether it fires.

So the rejection has to build the defective version, which means a second implementation of the traversal existing solely to be wrong.

That is a cost — a second implementation is a second thing to maintain — and it is the price of a check that can fail. The alternative is a guard nobody has ever seen fire, which is a guard nobody knows works.

The pruning that loses an occurrence #

There is a third instance in this collection and it is not an ordering, which is what makes it worth putting beside the two.

The pruning that loses an occurrence is a backtracking search whose bound is optimistic: a branch that could still reach an answer is cut, and the occurrences below it are never found. Same outcome — a short answer, every reported position genuine — from a different cause.

So the class is wider than orderings. It is any correctness argument that licenses not doing something, and the three kinds are: an ordering that makes a structure unnecessary, a bound that makes a branch unnecessary, and a test that makes a lookup unnecessary.

All three produce short answers when the argument fails, and none produces a wrong one.

The instrument for all three is the same and it is not a test on the answer. It is a second implementation that does the thing the argument licenses skipping, run on the same input, with the two answers compared.

That is expensive — a reference implementation for every optimisation of this kind — and it is the only thing that works. This collection has three of them: a queue beside the sweep, a chained listing beside the chainless one, and an exhaustive search beside the pruned one.

A short answer is worse than a wrong one #

It is worth arguing the ranking, because “silent” is doing a lot of work in this essay and a reader might reasonably think a wrong answer is worse than an incomplete one.

A wrong answer contains something checkable. A reported occurrence that is not an occurrence can be verified against the text in constant time per occurrence, and a system doing that verification catches every wrong position immediately.

A short answer contains nothing to check. Verifying that no occurrence is missing means finding all of them, which is the query.

So the two failures differ in whether a cheap independent check exists, and for this family the check for wrongness is a character comparison and the check for shortness is a second search.

That asymmetry is why this collection’s habits emphasise it. The pruning that loses an occurrence is the same argument on a backtracking search, and a document already in the answer records it for a listing: the failure is silent, which is what makes it worth a check rather than a comment. Every document the broken walk reports is genuinely in the answer; the answer is short, and a document listing has no way to notice what it did not find.

Three essays, three objects, one sentence.

Three orderings, three objects #

Collecting the ordering dependencies this collection has found, because a third one makes the pattern worth generalising.

Left-first, in a chainless document listing: the walk must visit the left subrange before the right, because the test it replaced asks whether a document’s first row in the range has been seen.

Left-to-right, in this propagation: the sweep must visit occurrences in text order, because a production lies to the right.

Leaf order, in an interval enumeration: the symbols come out in the tree’s leaf order, which is the alphabet’s only if the code is order-preserving — and one set, three orders is where reading it wrongly produces a plausible number that is wrong.

Three orderings, three objects, three silent failures. What they share is that the ordering carries information — about what has been done, about what lies ahead, about how things compare — and that a traversal in the wrong order produces output that is individually correct and collectively incomplete.

What the correct answer looks like #

For completeness the correct traversal’s behaviour on the same query is worth stating, because the essay so far is about what goes wrong.

Sixteen copies, a six-character pattern drawn from the base. One primary occurrence — the pattern crosses a phrase boundary in exactly one place — and fifteen secondaries.

The sweep processes the primary, finds the phrases whose source regions contain it, produces copies, inserts them ahead, and continues. Each of the fifteen is produced exactly once and reached exactly once.

Sixteen occurrences, in text order, with a frontier peaking at nine.

The queue produces the same sixteen in breadth-first order with a visited set of sixteen. Both examine the same three thousand three hundred and twenty-five phrases.

So the correct traversal is unremarkable, which is the point: the substitution changes bookkeeping and nothing else, and the only way to see that it depends on anything is to break the thing it depends on.

Why 87.5% and not 50% #

The specific fraction is worth working out, because it says the failure is not a coin flip.

The reversed sweep starts with the primary occurrences sorted descending. There is one primary here, so the list starts with one element and the cursor at zero.

Processing it produces every occurrence copied directly from it — on this collection, one, because the phrase structure is a chain of copies each pointing at the previous text. That production has a larger position, so in descending order it belongs before the cursor’s current element, so it is inserted at index zero and the cursor is advanced past it.

The sweep then finds the list exhausted and stops.

So the reversed traversal reports the primary and the one occurrence directly derived from it: two. The other fourteen are second-generation and later, and none is ever reached.

The fraction is therefore the propagation’s depth, not a random loss. On a collection of d copies chained this way the reversed sweep reports two of d, so the loss goes to one hundred per cent as the collection gets more repetitive.

That is the sharpest possible version of “the defect is worst where the structure is for”, and it is worth having as a number rather than as a direction.

What to do about it #

The instruction that comes out is narrow and worth having.

When a bookkeeping structure is removed because a traversal order makes it unnecessary, the order becomes part of the specification — and specifications that live only in a comment are specifications nobody checks.

Two things follow. The order should be enforced where it is relied on, by a guard that fires on the position rather than on the answer. And the rejection test should construct the wrong order and require a short answer, because that is the only evidence the guard is load-bearing.

Both are cheap. What is not cheap is finding out afterwards, on a corpus that happens to be deep, that a search has been quietly returning a fraction of its occurrences.

Where else an order is load-bearing here #

Two more traversals in this collection depend on an order and neither has a rejection test, which is worth naming as a queue rather than as a criticism.

The primary occurrence search intersects two ranges of phrase boundaries, and its implementation filters the smaller range against the larger’s rank window. That is an optimisation whose correctness does not depend on an order, so it is not in the class — but it does depend on the two orderings being consistent, and an index with z in its size is where the three orderings were built.

The parse itself produces phrases left to right and every downstream claim depends on it. The parse in one pass of the text is the linear construction, and its ordering is enforced by the algorithm rather than by a check — a parser cannot see text it has not read.

So of four order-dependent things in this family, one is enforced by physics, one is checked by this strand, one is checked by the strand before it, and one is a consistency requirement nothing tests. That last is a small gap and it is the shape of thing that goes unnoticed until a refactor moves a sort.