Skip to main content

MAX_EDIT_DISTANCE

Constant MAX_EDIT_DISTANCE 

Source
pub const MAX_EDIT_DISTANCE: usize = 4096;
Expand description

How far apart two streams may be before the comparison stops looking for the smallest diff.

The diff is Myers’, whose cost is proportional to the edit distance and not to the stream lengths —which is why it is the right algorithm here and why this bound is the only thing that makes an unbounded input safe. Two streams that are nearly the same (the ordinary case, and the only interesting one) finish in a few passes. Two streams that are unrelated do not converge at all: the distance is the length of the longer one, and for a 40 000-token header that is 40 000 snapshots of a 40 000-wide array.

Past this the comparison returns what it has and sets Alignment::truncated. The bound is generous on purpose: the differences worth classifying are the ones a reading produced, and a reading that is 4 000 tokens away from the compiler is not being classified, it is being rewritten.