#1873: DiffMatchPatch.java

Google's diff-match-patch algorithm library by Neil Fraser, embedded directly in ProjectForge under the original package name.fraser.neil.plaintext. Licensed under Apache License 2.0. Provides synchronous text comparison (diff), fuzzy matching (match), and patch application (patch) — the same algorithms that power Google Docs, Etherpad, and Wikipedia's revision comparison. Used by ProjectForge for text change tracking and version comparison.

Origin and License

• Author: Neil Fraser (fraser@google.com), Google Inc.
• Copyright: 2006 Google Inc.
• License: Apache License 2.0
• Original project: google-diff-match-patch on GitHub
• Homepage: http://code.google.com/p/google-diff-match-patch/ (original Google Code, now archived)
• Package preserved: name.fraser.neil.plaintext — the exact package name from the original library

Algorithm Overview

The library implements three related algorithms, all operating on plain text:

1. Diff — Myers' O(ND) Difference Algorithm

Computes the minimal set of edits to transform text1 into text2. The core algorithm is Myers' diff algorithm (1986), which finds the shortest edit script using an O(ND) time/space approach where N is the sum of string lengths and D is the number of differences.

• Operation enum: DELETE, INSERT, EQUAL — each diff is a linked list of operations
• Optimizations: common prefix/suffix stripping, line-level pre-comparison (checklines flag), deadline-based early termination
• Post-processing: diff_cleanupSemantic() makes diffs human-readable; diff_cleanupEfficiency() optimizes for machine processing; diff_cleanupMerge() merges adjacent equal/deletion operations
• Semantic cleanup: recognizes sentence/paragraph boundaries, short isolated equalities, and whitespace changes for more intuitive output

2. Match — Bitap Algorithm (Shift-Or)

Locates the best approximate match for a pattern within a larger text. Uses the Bitap algorithm (also known as shift-or or Baeza-Yates–Gonnet algorithm) which:

• Encodes the pattern as a bitmask of character positions
• Uses bitwise operations for O(n) approximate string matching
• Supports fuzzy matching with configurable error threshold (Match_Threshold)
• Uses a locality-sensitive scoring system (Match_Distance) to prefer matches near the expected location

3. Patch — Unified Diff Format + Fuzzy Application

Creates patches (text representations of diffs) that can be serialized, transmitted, and applied to other texts:

• Uses a unified diff-like format: @@ -start,length +start,length @@ context
• Patches can be applied with tolerance for line number drift (Patch_Margin context for matching)
• patch_apply() attempts fuzzy matching when exact context doesn't match — uses Match algorithm internally
• Supports partial patch application with results indicating which patches succeeded

Key Configuration Parameters

Field	Default	Purpose
Diff_Timeout	1.0 seconds	Maximum seconds for a diff computation before returning partial result (0 = infinite)
Diff_EditCost	4	Cost of an empty edit operation — higher values produce cleaner, less fragmented diffs
Match_Threshold	0.5	Fuzzy match threshold (0.0 = exact, 1.0 = very loose)
Match_Distance	1000	Locality bonus — distance in characters from expected match location
Patch_DeleteThreshold	0.5	How closely delete blocks must match expected content to be accepted
Patch_Margin	4	Context character count around patch hunks
Match_MaxBits	32	Bit width for the Bitap algorithm (matches Java int size)

Data Structure: Diff (Inner Class)

Diffs are represented as a LinkedList<Diff> where each Diff is an inner static class with:

• Operation operation — DELETE, INSERT, or EQUAL
• String text — the text segment for this operation

Internal Helper: LinesToCharsResult

An optimization for large texts: converts lines to unique Unicode characters, performs the diff on the compressed representation, then reconstructs line-level output. This dramatically reduces the comparison space for line-oriented text (e.g., source code).

Imports

• java.io.UnsupportedEncodingException
• java.net.URLDecoder / URLEncoder — For encoding diff output for URL-safe transmission
• java.util.* — Lists, Maps, ArrayLists, LinkedLists, regex Patterns

ProjectForge Usage

ProjectForge embeds this library rather than depending on it as an external JAR. This was likely done because:

1. The library is stable and rarely changes (last significant update was the Java port circa 2010)
2. Embedding avoids dependency management issues
3. The package name (name.fraser.neil.plaintext) is distinct and non-conflicting
4. It may have custom modifications for ProjectForge-specific needs (though the code appears to be the standard port)

The DiffMatchPatch is used for tracking changes to text fields in ProjectForge's data objects — showing what changed between versions of an address, project description, or other text content.

48a93dedb Colored console log. UserGroupCache export for debugging and comparing work now. CollectionUtil improved. KotlinStringExtension.shortenMiddle() added.