antfu / antfu/diff-match-patch-es
diffCleanupSemantic(Lossless) can run into an infinite loop
Nobody has claimed this yet.
- Dominant language
- TypeScript
- Stars
- 200
- Forks
- 6
- PR merge metrics
- No merged PRs in 30d
Description
Describe the bug
For a specifically crafted input, diffFromDelta would produce a delta that cause diffCleanupSemantic and diffCleanupSemanticLossless to hang (infinite loop).
The documentation for diffFromDelta says that it would throw on invalid input, but it's not doing that for this case. Or this could be an issue with diffCleanupSemantic and diffCleanupSemanticLossless where they are mishandling specific diffs.
This is happening due to the empty edit/equality tuples. Reproducible on the latest v2.0.1.
Reproduction:
import { diffCleanupSemantic, diffFromDelta } from 'diff-match-patch-es'
const diffs = diffFromDelta('ac', '=1\t-0\t=0\t+b\t=1')
console.log('diff:', JSON.stringify(diffs))
diffCleanupSemantic(diffs)
Potential fix (unverified):
The original Java version has some extra check:
while (edit.length() != 0 && equality2.length() != 0
&& edit.charAt(0) == equality2.charAt(0)) {
But missing from the JS (and TS) version:
Reproduction
https://github.com/aforemendude/bugs-reproduction/tree/main/diff-match-patch-es-delta-inf-loop
System Info
System:
OS: Linux 7.0 Ubuntu 24.04.4 LTS 24.04.4 LTS (Noble Numbat)
CPU: (4) x64 Intel(R) N95
Memory: 12.39 GB / 15.40 GB
Container: Yes
Shell: 5.2.21 - /bin/bash
Binaries:
Node: 24.18.0 - /usr/local/nodejs/bin/node
npm: 11.16.0 - /usr/local/nodejs/bin/npm
Used Package Manager
npm
Validations
- Follow our Code of Conduct
- Read the Contributing Guide.
- Check that there isn't already an issue that reports the same bug to avoid creating a duplicate.
- Check that this is a concrete bug. For Q&A, please open a GitHub Discussion instead.
- The provided reproduction is a minimal reproducible of the bug.
Contributions
- I am willing to submit a PR to fix this issue
- I am willing to submit a PR with failing tests (actually just go ahead and do it, thanks!)
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Run the supplied reproduction first, then inspect the cited logic in src/diff.ts around diffCleanupSemantic and compare it with the linked Java implementation. Use the crafted diffFromDelta input to verify the hang is gone and confirm the documented invalid-input behavior, ideally with regression coverage.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript, typescript
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 74/100