How mitsuhiko/similar works
1. What this repo is
- similar is a Rust library crate, not an application or service.
- Its job is to compute diffs between sequences and text, then expose those diffs through iterator-based APIs and formatted outputs like unified diff.
2. Public architecture boundary
- The main public entrypoint is src/lib.rs.
- From the README and file layout, the crate exposes high-level text diff types such as TextDiff, change tags, and unified-diff rendering, while keeping the algorithm internals behind module boundaries.
3. Core data model
- src/types.rs, src/common.rs, and src/iter.rs define the shared diff vocabulary: change tags, edit/change representations, and iterators over diff results.
- These types form the bridge between “algorithm output” and “user-facing iteration/rendering.”
4. Algorithm subsystem
- src/algorithms/ is the main computational engine.
- It contains multiple diff strategies: Myers, Patience, Hunt-style, Histogram, and classic LCS.
- This suggests a layered strategy selection model where the library can choose the most appropriate algorithm or fall back between them based on the input.
5. Algorithm pipeline and post-processing
- Files like preflight.rs, capture.rs, hook.rs, replace.rs, and compact.rs indicate that raw matching is not the whole story.
- The flow likely starts with preflight analysis, runs a matching algorithm, then applies capture/grouping, replacement detection, and compaction to turn raw matches into cleaner human-readable edit blocks.
6. Sequence and text abstraction boundary
- src/text/abstraction.rs, src/text/inline.rs, src/text/mod.rs, and src/text/utils.rs provide the text-specific layer.
- This layer adapts raw text into comparable units such as lines, words, characters, graphemes, and inline representations.
- The README’s examples imply that the same diff core is reused for both generic sequences and text-aware operations.
7. Unified diff generation
- src/udiff.rs is the formatting layer that converts diff results into unified diff text.
- This is a separate concern from the diff algorithm itself: the algorithm computes changes, and udiff turns them into a standard textual patch format.
8. Generic lookup and low-level helpers
- src/lookup.rs, src/utils.rs, and src/algorithms/utils.rs contain supporting mechanics for matching and comparing items.
- The README’s no_std note is important architecturally: the crate can use alloc only, and optionally swaps between BTreeMap and hashbrown::HashMap depending on features.
9. Runtime and environment constraints
- src/deadline_support.rs shows the crate supports time-bounded execution or cancellation-like behavior for expensive diff computations.
- That matters for architecture because it means some algorithms can be interrupted or short-circuited rather than always running to completion.
10. Behavior verification and snapshots
- The many src/**/snapshots files indicate snapshot-based regression testing for algorithm behavior, text formatting, and unified diff output.
- This is a strong signal that output stability is part of the design contract, especially for a library used in snapshot testing workflows.
11. Examples and usage surfaces
- examples/ demonstrates the main integration points: terminal rendering, inline highlighting, serde integration, ownership patterns, non-string inputs, and large inputs.
- These examples map directly to the library’s architectural themes: generic diffing, text specialization, and output formatting.
12. Tooling and release workflow
- The repository includes clippy, rustfmt, test, and publish GitHub Actions workflows plus a Makefile.
- These do not affect runtime architecture, but they reinforce that the crate is intended to be a stable, well-tested library with strong formatting/linting discipline.
13. How data flows through the crate
- User input enters through generic sequence APIs or text-specific constructors.
- The chosen algorithm in src/algorithms/ computes matches and edits.
- Shared iterator/model types carry those edits outward.
- Higher-level renderers like unified diff and text/terminal-oriented helpers format the results for consumption.
14. Main architectural boundary to diagram
- The clearest diagram boundary is: public API layer on top, diff algorithm engine in the middle, and text/formatting adapters around it.
- Everything else in the repository supports one of those three responsibilities: matching, modeling, or presentation.
Main entry points: algorithms/mod.rs Engine · lookup.rs Lookup · lib.rs lib.rs · text/mod.rs Text API
Components 21
Public API
Crate entrypoints and exported iteration/model surface.
- lib.rs · Primary public entrypoint for the library.
src/lib.rs
Core Model
Shared diff vocabulary and iterator-based change representations.
Algorithms
Diff engines and post-processing pipeline.
- Engine · Dispatches and wires the diff algorithm stack.
src/algorithms/mod.rs - Preflight · Initial inspection and setup before matching.
src/algorithms/preflight.rs - Myers · Primary Myers-style sequence matcher.
src/algorithms/myers.rs - Patience · Patience-based matcher for reordered inputs.
src/algorithms/patience.rs - Histogram · Histogram-style matching strategy.
src/algorithms/histogram.rs - Hunt · Hunt-style matching strategy.
src/algorithms/hunt.rs - LCS · Classic longest-common-subsequence matcher.
src/algorithms/lcs.rs - Capture · Groups raw matches into higher-level edit blocks.
src/algorithms/capture.rs - Replace · Detects replacement regions and restructures edits.
src/algorithms/replace.rs - Compact · Compacts and cleans up emitted edit regions.
src/algorithms/compact.rs
Text Layer
Text-specific abstractions and rendering helpers.
- Text API · Text-oriented constructors and diff helpers.
src/text/mod.rs - Text Units · Turns text into lines, words, chars, and graphemes.
src/text/abstraction.rs - Inline · Inline and semantic text diff presentation.
src/text/inline.rs
Formatting
Patch-style output generation.
- Unified Diff · Renders diff results as unified diff text.
src/udiff.rs
Connections 34
- lib.rs → Types: exports · Public diff vocabulary is surfaced from the crate root.
- lib.rs → Iterators: exports · Iterator-based diff views are part of the public API.
- lib.rs → Engine: uses · Root API delegates diff computation to the algorithm engine.
- lib.rs → Text API: exports · Text-specific constructors and helpers are exposed publicly.
- lib.rs → Unified Diff: exports · Unified diff rendering is part of the user-facing surface.
- Types → Common: shares · Core representations build on the shared change vocabulary.
- Iterators → Types: yields · Iterators expose computed edits through shared types.
- Text API → Text Units: adapts · Text APIs rely on text-to-unit abstraction.
- Text API → Inline: renders · Inline text diff helpers build on the text facade.
- Text API → Unified Diff: formats · Text diff helpers can emit unified diff output.
- Text API → Engine: drives · Text operations invoke the shared diff engine.
- Engine → Preflight: starts · Algorithm execution begins with preflight analysis.
- Engine → Myers: selects · Engine can dispatch to Myers as a core strategy.
- Engine → Patience: selects · Engine can dispatch to Patience as a strategy.
- Engine → Histogram: selects · Engine can dispatch to Histogram as a strategy.
- Engine → Hunt: selects · Engine can dispatch to Hunt as a strategy.
- Engine → LCS: selects · Engine can dispatch to LCS as a fallback or baseline.
- Preflight → Capture: feeds · Initial analysis feeds capture/grouping post-processing.
- Myers → Capture: emits · Raw matches are funneled into capture processing.
- Patience → Capture: emits · Patience output is normalized through capture.
- Capture → Replace: refines · Captured blocks are refined into replacement regions.
- Replace → Compact: cleans · Replacement detection is compacted into final edits.
- Compact → Iterators: produces · Final algorithm output is presented as iterators.
- Capture → Lookup: uses · Capture logic depends on low-level matching support.
- Myers → Lookup: uses · Sequence matching relies on lookup helpers.
- Patience → Lookup: uses · Sequence matching relies on lookup helpers.
- Histogram → Lookup: uses · Sequence matching relies on lookup helpers.
- Hunt → Lookup: uses · Sequence matching relies on lookup helpers.
- LCS → Lookup: uses · Sequence matching relies on lookup helpers.
- Engine → Deadline: guards · Expensive computations can be deadline-bounded.
- Lookup → Utils: uses · Matching support shares internal helper code.
- Unified Diff → Types: formats · Unified diff rendering consumes the shared change model.
- Inline → Types: formats · Inline renderers consume the shared change model.
- Text Units → Utils: normalizes · Text abstraction uses shared helpers for splitting and normalization.