# mitsuhiko/similar architecture

> Architecture diagram of the GitHub repository mitsuhiko/similar, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-06-16). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/mitsuhiko/similar
- Repository: https://github.com/mitsuhiko/similar

## Overview

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: [`src/algorithms/mod.rs`](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/mod.rs) (Engine), [`src/lookup.rs`](https://github.com/mitsuhiko/similar/blob/main/src/lookup.rs) (Lookup), [`src/lib.rs`](https://github.com/mitsuhiko/similar/blob/main/src/lib.rs) (lib.rs), [`src/text/mod.rs`](https://github.com/mitsuhiko/similar/blob/main/src/text/mod.rs) (Text API)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_public_api["Public API"]
  node_lib["lib.rs<br/>crate root<br/>[lib.rs]"]
end

subgraph group_core_model["Core Model"]
  node_types["Types<br/>[types.rs]"]
  node_common["Common<br/>shared ops<br/>[common.rs]"]
  node_iter(("Iterators<br/>[iter.rs]"))
end

subgraph group_algorithms["Algorithms"]
  node_alg_mod["Engine<br/>algorithm entry<br/>[mod.rs]"]
  node_preflight{{"Preflight<br/>analysis stage<br/>[preflight.rs]"}}
  node_myers["Myers<br/>diff algorithm<br/>[myers.rs]"]
  node_patience["Patience<br/>diff algorithm<br/>[patience.rs]"]
  node_histogram["Histogram<br/>diff algorithm<br/>[histogram.rs]"]
  node_hunt["Hunt<br/>diff algorithm<br/>[hunt.rs]"]
  node_lcs["LCS<br/>diff algorithm<br/>[lcs.rs]"]
  node_capture{{"Capture<br/>post-process<br/>[capture.rs]"}}
  node_replace{{"Replace<br/>post-process<br/>[replace.rs]"}}
  node_compact{{"Compact<br/>post-process<br/>[compact.rs]"}}
end

subgraph group_text_layer["Text Layer"]
  node_text_mod["Text API<br/>text facade<br/>[mod.rs]"]
  node_abstraction["Text Units<br/>text abstraction<br/>[abstraction.rs]"]
  node_inline["Inline<br/>text rendering<br/>[inline.rs]"]
end

subgraph group_formatting["Formatting"]
  node_udiff["Unified Diff<br/>formatter<br/>[udiff.rs]"]
end

subgraph group_support["Support"]
  node_lookup(("Lookup<br/>matching support<br/>[lookup.rs]"))
  node_deadline(("Deadline<br/>execution control"))
  node_utils(("Utils<br/>helpers<br/>[utils.rs]"))
end

node_lib -->|"exports"| node_types
node_lib -->|"exports"| node_iter
node_lib -->|"uses"| node_alg_mod
node_lib -->|"exports"| node_text_mod
node_lib -->|"exports"| node_udiff
node_types -->|"shares"| node_common
node_iter -->|"yields"| node_types
node_text_mod -->|"adapts"| node_abstraction
node_text_mod -->|"renders"| node_inline
node_text_mod -->|"formats"| node_udiff
node_text_mod -->|"drives"| node_alg_mod
node_alg_mod -->|"starts"| node_preflight
node_alg_mod -->|"selects"| node_myers
node_alg_mod -->|"selects"| node_patience
node_alg_mod -->|"selects"| node_histogram
node_alg_mod -->|"selects"| node_hunt
node_alg_mod -->|"selects"| node_lcs
node_preflight -->|"feeds"| node_capture
node_myers -->|"emits"| node_capture
node_patience -->|"emits"| node_capture
node_capture -->|"refines"| node_replace
node_replace -->|"cleans"| node_compact
node_compact -->|"produces"| node_iter
node_capture -->|"uses"| node_lookup
node_myers -->|"uses"| node_lookup
node_patience -->|"uses"| node_lookup
node_histogram -->|"uses"| node_lookup
node_hunt -->|"uses"| node_lookup
node_lcs -->|"uses"| node_lookup
node_alg_mod -->|"guards"| node_deadline
node_lookup -->|"uses"| node_utils
node_udiff -->|"formats"| node_types
node_inline -->|"formats"| node_types
node_abstraction -->|"normalizes"| node_utils

click node_lib "https://github.com/mitsuhiko/similar/blob/main/src/lib.rs"
click node_types "https://github.com/mitsuhiko/similar/blob/main/src/types.rs"
click node_common "https://github.com/mitsuhiko/similar/blob/main/src/common.rs"
click node_iter "https://github.com/mitsuhiko/similar/blob/main/src/iter.rs"
click node_alg_mod "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/mod.rs"
click node_preflight "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/preflight.rs"
click node_myers "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/myers.rs"
click node_patience "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/patience.rs"
click node_histogram "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/histogram.rs"
click node_hunt "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/hunt.rs"
click node_lcs "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/lcs.rs"
click node_capture "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/capture.rs"
click node_replace "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/replace.rs"
click node_compact "https://github.com/mitsuhiko/similar/blob/main/src/algorithms/compact.rs"
click node_text_mod "https://github.com/mitsuhiko/similar/blob/main/src/text/mod.rs"
click node_abstraction "https://github.com/mitsuhiko/similar/blob/main/src/text/abstraction.rs"
click node_inline "https://github.com/mitsuhiko/similar/blob/main/src/text/inline.rs"
click node_udiff "https://github.com/mitsuhiko/similar/blob/main/src/udiff.rs"
click node_lookup "https://github.com/mitsuhiko/similar/blob/main/src/lookup.rs"
click node_deadline "https://github.com/mitsuhiko/similar/blob/main/src/deadline_support.rs"
click node_utils "https://github.com/mitsuhiko/similar/blob/main/src/utils.rs"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_lib toneBlue
class node_types,node_common,node_iter toneAmber
class node_alg_mod,node_preflight,node_myers,node_patience,node_histogram,node_hunt,node_lcs,node_capture,node_replace,node_compact toneMint
class node_text_mod,node_abstraction,node_inline toneRose
class node_udiff toneIndigo
class node_lookup,node_deadline,node_utils toneTeal
```

## Components

### Public API

Crate entrypoints and exported iteration/model surface.

- [lib.rs](https://github.com/mitsuhiko/similar/blob/main/src/lib.rs): crate root · Primary public entrypoint for the library. · `src/lib.rs`

### Core Model

Shared diff vocabulary and iterator-based change representations.

- [Types](https://github.com/mitsuhiko/similar/blob/main/src/types.rs): diff types · Change tags, edits, and shared diff data structures. · `src/types.rs`
- [Common](https://github.com/mitsuhiko/similar/blob/main/src/common.rs): shared ops · Common diff vocabulary and helper definitions. · `src/common.rs`
- [Iterators](https://github.com/mitsuhiko/similar/blob/main/src/iter.rs): diff iterators · Iterator-based views over computed diffs. · `src/iter.rs`

### Algorithms

Diff engines and post-processing pipeline.

- [Engine](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/mod.rs): algorithm entry · Dispatches and wires the diff algorithm stack. · `src/algorithms/mod.rs`
- [Preflight](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/preflight.rs): analysis stage · Initial inspection and setup before matching. · `src/algorithms/preflight.rs`
- [Myers](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/myers.rs): diff algorithm · Primary Myers-style sequence matcher. · `src/algorithms/myers.rs`
- [Patience](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/patience.rs): diff algorithm · Patience-based matcher for reordered inputs. · `src/algorithms/patience.rs`
- [Histogram](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/histogram.rs): diff algorithm · Histogram-style matching strategy. · `src/algorithms/histogram.rs`
- [Hunt](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/hunt.rs): diff algorithm · Hunt-style matching strategy. · `src/algorithms/hunt.rs`
- [LCS](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/lcs.rs): diff algorithm · Classic longest-common-subsequence matcher. · `src/algorithms/lcs.rs`
- [Capture](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/capture.rs): post-process · Groups raw matches into higher-level edit blocks. · `src/algorithms/capture.rs`
- [Replace](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/replace.rs): post-process · Detects replacement regions and restructures edits. · `src/algorithms/replace.rs`
- [Compact](https://github.com/mitsuhiko/similar/blob/main/src/algorithms/compact.rs): post-process · Compacts and cleans up emitted edit regions. · `src/algorithms/compact.rs`

### Text Layer

Text-specific abstractions and rendering helpers.

- [Text API](https://github.com/mitsuhiko/similar/blob/main/src/text/mod.rs): text facade · Text-oriented constructors and diff helpers. · `src/text/mod.rs`
- [Text Units](https://github.com/mitsuhiko/similar/blob/main/src/text/abstraction.rs): text abstraction · Turns text into lines, words, chars, and graphemes. · `src/text/abstraction.rs`
- [Inline](https://github.com/mitsuhiko/similar/blob/main/src/text/inline.rs): text rendering · Inline and semantic text diff presentation. · `src/text/inline.rs`

### Formatting

Patch-style output generation.

- [Unified Diff](https://github.com/mitsuhiko/similar/blob/main/src/udiff.rs): formatter · Renders diff results as unified diff text. · `src/udiff.rs`

### Support

Lookup, helpers, and execution constraints.

- [Lookup](https://github.com/mitsuhiko/similar/blob/main/src/lookup.rs): matching support · Low-level comparison and matching support. · `src/lookup.rs`
- [Deadline](https://github.com/mitsuhiko/similar/blob/main/src/deadline_support.rs): execution control · Time-bounded execution support for expensive diffing. · `src/deadline_support.rs`
- [Utils](https://github.com/mitsuhiko/similar/blob/main/src/utils.rs): helpers · General-purpose internal helpers used across the crate. · `src/utils.rs`

## Connections

- 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.