ElementSimilarityDiffElementAligner<T> bails out to a plain delete+insert when a change section exceeds a combined size:
private const int MaximumChangedSectionSizeBeforePuntingToDeletePlusAdd = 15;
// ...
if (length1 + length2 > MaximumChangedSectionSizeBeforePuntingToDeletePlusAdd)
return new List<DiffElement<T?>>();
The comments justify this by fear of exponential blow-up ("recursive solution the combinations could get big fast"). But CalculateBestAlignment is memoized on AlignmentKey(lower1, lower2), so the number of distinct states is bounded by length1 * length2 and each is computed once — the algorithm is O(length1 × length2), not exponential.
Consequences of the low threshold:
- Any changed block with more than ~15 combined elements gets no similarity-based alignment at all; you just get a block of deletes followed by a block of inserts. For line-level text diffs this means a fairly small changed region loses all the nice Modify/Replace alignment.
Suggestions:
- Raise the threshold substantially (it's a quadratic guard, not exponential), or
- Replace the hard cutoff with a product-based guard (e.g.
length1 * length2 <= N) that reflects the real cost, and/or make it configurable via DiffOptions.
The comment block (src/DiffLib/Alignment/ElementSimilarityAligner.cs:16-21 and :93-97) should also be corrected since it mis-describes the complexity.
ElementSimilarityDiffElementAligner<T>bails out to a plain delete+insert when a change section exceeds a combined size:The comments justify this by fear of exponential blow-up ("recursive solution the combinations could get big fast"). But
CalculateBestAlignmentis memoized onAlignmentKey(lower1, lower2), so the number of distinct states is bounded bylength1 * length2and each is computed once — the algorithm is O(length1 × length2), not exponential.Consequences of the low threshold:
Suggestions:
length1 * length2 <= N) that reflects the real cost, and/or make it configurable viaDiffOptions.The comment block (
src/DiffLib/Alignment/ElementSimilarityAligner.cs:16-21and:93-97) should also be corrected since it mis-describes the complexity.