Luigit
repositories / bugabinga.net

bugabinga.net

personal infrastructure for bugabinga!

owned by admin

.system/research/BB-RESEARCH-BWD1AIED-luigit-large-diff-behavior/index.md

Raw
Rendered preview

id: BB-RESEARCH-BWD1AIED type: research title: Luigit large diff behavior

Luigit large diff behavior

Scope

Determine how Luigit can remain responsive and bounded for large, hostile, or highly dissimilar diffs. Separate Git change discovery, textual comparison, optional structural analysis, result delivery, and browser rendering because each has different failure modes.

Facts

Diff computation is not viewport computation

A correct line diff compares complete token sequences. Myers has worst-case time proportional to the product of total input length and edit distance, with linear-space variants available. Patience and histogram algorithms trade strict minimality for anchors and useful behavior on source text. No general algorithm can derive globally consistent hunks from only visible lines because matches outside the viewport can change alignment and hunk boundaries.

A selected file therefore needs whole-file comparison or a previously computed whole-file result. Viewport awareness can defer file selection, formatting, syntax highlighting, intraline analysis, transfer, and DOM construction, but not generally the underlying line alignment.

Sources: Myers, An O(ND) Difference Algorithm and Its Variations, Git diff algorithms, imara-diff.

Git-aware discovery has separate expensive phases

Git first establishes changed paths and object identities, then may perform content comparison and rewrite detection. Exact rename and copy detection can require quadratic candidate comparison after cheaper matching fails. Git exposes diff.renameLimit specifically to prevent exhaustive rename or copy detection when candidate counts are too high.

Tree-delta summaries can therefore be cheap while rename classification or file contents remain deferred. A bounded public service must cap candidate counts independently from file, byte, line, and runtime limits.

Sources: Git diffcore, Git configuration, libgit2 diff API.

Libraries expose different resource controls

similar provides Myers, patience, and LCS algorithms plus deadline-aware entry points. Its documentation warns that large, highly distinct inputs can take too long and explains that a deadline may return an approximate partial result depending on the algorithm. A deadline bounds elapsed work only if the implementation checks it often enough; it does not bound input allocation, output size, or line length.

imara-diff provides linear-space Myers and histogram algorithms. It adds preprocessing and heuristics intended to avoid pathological quadratic behavior and recommends histogram for most human-facing diffs. Its public API produces ordered hunks but does not establish Git delta facts.

Difftastic demonstrates layered degradation for structural comparison. It imposes byte and graph limits, rejects unsupported or excessively erroneous parses, and falls back to textual output rather than allowing structural matching to consume unbounded resources. Its structural matcher explores a lazily generated graph, so graph-state count is a first-class limit distinct from source bytes.

Sources: similar deadlines and performance, imara-diff, Difftastic manual, Difftastic 0.70.0 source.

Production systems use progressive disclosure and hard ceilings

GitHub automatically loads only 400 lines and 20 KiB for one file. Its documented ceilings include 20,000 loadable lines or 500 KiB per file, 20,000 loadable lines or 1 MiB for a pull request, 300 files, and 25 renderable rich files. Content beyond a limit is not shown.

GitLab separates collapsed and unavailable states. A file is collapsed when a diff reaches 10% of configured patch, file, or line ceilings, while content exceeding a ceiling is marked Too large and cannot be expanded in the UI.

These values are service-specific precedents, not Luigit defaults. Their transferable pattern is an inexpensive summary, an auto-load budget, an explicit user-triggered expansion budget, and a hard unavailable state.

Sources: GitHub repository limits, GitLab diff limits.

Browser virtualization has semantic costs

Traditional virtualization keeps only a moving viewport in the DOM. That lowers layout and paint cost but removes off-screen content from browser find, selection, fragment navigation, printing, copying, and accessibility traversal. The abandoned native virtual-scroller proposal treated the DOM as the source of truth for those capabilities and explicitly identified initial parsing of a huge server-rendered DOM as a remaining problem.

CSS content-visibility: auto can skip layout and paint outside the viewport while retaining document content. It does not remove HTML transfer, parse, node-memory, or initial DOM-construction costs, so it helps medium results rather than arbitrarily large ones.

Sources: WICG virtual scroller explainer, CSS Containment Level 2, MDN content-visibility.

Progressive delivery does not imply progressive diffing

HTTP can deliver response bytes before the full body is generated, but intermediaries may buffer and compression may delay visible chunks. Caddy's reverse proxy supports response flushing controls and otherwise makes latency-sensitive flush decisions for streaming responses. The deployed path must therefore be measured through Caddy rather than inferred from application behavior.

Per-file progressive delivery is robust because each file result is independently valid. Streaming an unfinished hunk sequence is weaker: later computation can fail, a disconnected client can leave work running, and an HTML document can end mid-structure. Bounded computation should produce an internally complete file result before exposing it as complete.

Sources: Caddy reverse_proxy, HTTP semantics, HTTP/1.1 message framing.

Cancellation must propagate into the expensive operation

Client disconnect detection can stop queued or cooperative work. It cannot safely interrupt arbitrary in-process native or Rust code at an instruction boundary. A service-level cgroup can cap total process memory and CPU, but it cannot contain one request without affecting other requests. Hard per-request termination requires a process boundary.

Luigit's one-application-executable constraint still permits worker threads inside the executable, but excludes helper processes as the ordinary runtime design. Consequently, candidate libraries must support bounded inputs, bounded outputs, frequent deadline or cancellation checks, or workloads small enough to reject before entering an uninterruptible phase.

Sources: systemd resource control, Linux cgroup v2.

Cache correctness differs from cache admission

Commit, tree, and blob objects are immutable by object identity. A diff keyed by repository identity, old object ID, new object ID, engine options, and engine version is therefore content-stable. Public authorization is not immutable: Luigit may render only objects reachable from currently advertised refs. Every cache hit must recheck current reachability before disclosure.

Large objects can evict many useful small entries. Weighted admission and eviction must account for stored bytes and recomputation cost rather than entry count alone. Concurrent identical misses should share one in-flight computation. Failures caused by transient deadlines or load should not become long-lived negative cache entries.

Sources: Git object model, TinyLFU, Caffeine eviction.

Conclusions

Use staged work with independent budgets

The request path should be:

  1. Revalidate repository visibility and requested object reachability.
  2. Discover changed paths and cheap metadata under tree and file-count budgets.
  3. Apply bounded rename detection or report rename detection as skipped.
  4. Return the complete file summary before computing file bodies.
  5. Queue requested file comparisons in a fixed-size worker pool.
  6. Compare each selected file as a complete unit under input, line, output, memory, and elapsed-work budgets.
  7. Add intraline, syntax, and structural layers only while their separate budgets remain.
  8. Store and deliver independently valid file results.

This design prevents one large comparison from monopolizing all request threads and lets backpressure reject or defer new expensive work. No request may create an unbounded task, queue entry, allocation, output buffer, or cache entry.

Make degradation explicit and monotonic

Each file needs one observable state:

  • unchanged: no content change.
  • ready: inline diff available.
  • collapsed: available but outside automatic rendering budget.
  • filtered: hidden by an explicit user filter.
  • binary: textual rendering is inapplicable; metadata and downloads remain.
  • oversized: source dimensions exceed comparison policy.
  • truncated: a bounded partial representation exists, with omitted amount reported.
  • timed out: computation exceeded its work budget.
  • unavailable: objects are missing, corrupt, or no longer publicly reachable.

Optional analysis adds independent markers such as rename detection skipped, intraline omitted, syntax highlighting omitted, or structural fallback. A failed enhancement must preserve the canonical textual result when that result succeeded.

Virtualize rendering, not Git truth

Large comparisons should open on a complete file summary with counts and states. No-JavaScript navigation should render one file or one bounded hunk page at a time. JavaScript may prefetch adjacent files, retain a bounded window of rendered file sections, restore scroll position, and cancel work no longer needed.

Use ordinary complete DOM plus content-visibility: auto for medium results because browser semantics remain intact. Use bounded window virtualization only after measured DOM limits are exceeded. When virtualization is active, provide server-side file and hunk URLs, persistent anchors, full-file raw views, and complete patch download so omitted DOM is still reachable.

Compute lazily at file granularity

Generate tree and file summaries eagerly. Do not diff every changed file merely to render the comparison landing page. Compute a full textual diff only when a file enters the auto-load window, is explicitly opened, is needed for a complete patch download, or is admitted by idle prefetch.

Within a selected file, preserve whole-file alignment. Viewport-only line diffing is rejected because it can fabricate different hunks as the viewport moves. Viewport-only syntax highlighting and HTML generation remain valid because they do not alter change facts.

Separate canonical and presentation caches

Cache the canonical escaped textual diff model separately from rendered layouts and optional analysis. Use a key containing repository identity, old and new object IDs, comparison mode, algorithm settings, whitespace settings, context size, engine version, and schema version. Rendered unified and side-by-side fragments may use smaller derivative caches.

Apply per-entry and total-byte ceilings before admission. Prefer inexpensive weighted recency or frequency eviction available in the selected implementation stack; do not build a novel cache policy before measurements justify it. Expose cache bytes, entry count, admissions, evictions, hit rate, in-flight deduplication, and reclamation failures.

Treat complete patch download as a separate workload

A complete patch route may stream canonical textual output without constructing browser HTML. It still requires the same reachability checks and total byte, file, line, line-length, rename-candidate, CPU, memory, and concurrency limits. If policy prevents complete generation, return a clear failure before labeling any body complete. Do not call a truncated artifact a complete patch.

Start from measured tiers, not copied forge numbers

Use GitHub and GitLab values only as experiment baselines. Derive Luigit thresholds from the klops container budget, representative public repositories, Caddy behavior, and concurrent-request targets. Keep separate thresholds for automatic display, explicit expansion, and absolute refusal.

Initial tuning must include ordinary edits, fully dissimilar files, repeated lines, generated lockfiles, minified single lines, giant lines, binary blobs, hundreds of files, rename-candidate explosions, syntax parse failures, and concurrent cancellation. Measure wall time, CPU time, peak resident memory, allocations, output bytes, time to first summary, time to first file, browser parse time, DOM nodes, long tasks, scroll stability, and post-cancellation resource release.

Evidence needed before implementation choice

  • Confirm the selected Git library can enumerate deltas without loading every blob and can cap rename detection.
  • Confirm the selected textual diff library's cancellation frequency, peak memory, output bound, and fallback semantics with adversarial fixtures.
  • Determine whether structural analysis can obey byte, node, graph-state, CPU, and memory budgets in-process.
  • Measure Caddy time-to-first-byte and chunk visibility with compression enabled and disabled.
  • Find the browser threshold where complete DOM plus content-visibility loses to bounded virtualization on desktop and mobile hardware.
  • Verify keyboard navigation, focus retention, anchors, copy, selection, find, print, and screen-reader equivalents in both rendering modes.
  • Verify client disconnect, superseded requests, and navigation cancel queued and active cooperative work promptly.
  • Verify cache reachability checks prevent stale derived data from exposing objects removed from advertised refs.

Recommendation

Adopt summary-first, per-file lazy comparison with a fixed worker pool, cooperative cancellation, phase-specific hard budgets, and explicit degraded states. Use complete server-rendered file pages as the accessibility and no-JavaScript baseline; add content-visibility for medium results and bounded DOM virtualization only above measured thresholds. Do not promise viewport-only diff computation or hard per-request isolation inside one process because neither is technically sound under the current constraints.

---
id: BB-RESEARCH-BWD1AIED
type: research
title: Luigit large diff behavior
---

# Luigit large diff behavior

## Scope

Determine how Luigit can remain responsive and bounded for large, hostile, or highly dissimilar diffs.
Separate Git change discovery, textual comparison, optional structural analysis, result delivery, and browser rendering because each has different failure modes.

## Facts

### Diff computation is not viewport computation

A correct line diff compares complete token sequences.
Myers has worst-case time proportional to the product of total input length and edit distance, with linear-space variants available.
Patience and histogram algorithms trade strict minimality for anchors and useful behavior on source text.
No general algorithm can derive globally consistent hunks from only visible lines because matches outside the viewport can change alignment and hunk boundaries.

A selected file therefore needs whole-file comparison or a previously computed whole-file result.
Viewport awareness can defer file selection, formatting, syntax highlighting, intraline analysis, transfer, and DOM construction, but not generally the underlying line alignment.

Sources: [Myers, An O(ND) Difference Algorithm and Its Variations](https://www.xmailserver.org/diff2.pdf), [Git diff algorithms](https://git-scm.com/docs/git-diff), [imara-diff](https://docs.rs/imara-diff/latest/imara_diff/).

### Git-aware discovery has separate expensive phases

Git first establishes changed paths and object identities, then may perform content comparison and rewrite detection.
Exact rename and copy detection can require quadratic candidate comparison after cheaper matching fails.
Git exposes `diff.renameLimit` specifically to prevent exhaustive rename or copy detection when candidate counts are too high.

Tree-delta summaries can therefore be cheap while rename classification or file contents remain deferred.
A bounded public service must cap candidate counts independently from file, byte, line, and runtime limits.

Sources: [Git diffcore](https://git-scm.com/docs/gitdiffcore), [Git configuration](https://git-scm.com/docs/git-config#Documentation/git-config.txt-diffrenameLimit), [libgit2 diff API](https://libgit2.org/docs/reference/main/diff/index.html).

### Libraries expose different resource controls

`similar` provides Myers, patience, and LCS algorithms plus deadline-aware entry points.
Its documentation warns that large, highly distinct inputs can take too long and explains that a deadline may return an approximate partial result depending on the algorithm.
A deadline bounds elapsed work only if the implementation checks it often enough; it does not bound input allocation, output size, or line length.

`imara-diff` provides linear-space Myers and histogram algorithms.
It adds preprocessing and heuristics intended to avoid pathological quadratic behavior and recommends histogram for most human-facing diffs.
Its public API produces ordered hunks but does not establish Git delta facts.

Difftastic demonstrates layered degradation for structural comparison.
It imposes byte and graph limits, rejects unsupported or excessively erroneous parses, and falls back to textual output rather than allowing structural matching to consume unbounded resources.
Its structural matcher explores a lazily generated graph, so graph-state count is a first-class limit distinct from source bytes.

Sources: [`similar` deadlines and performance](https://docs.rs/similar/latest/similar/#deadlines-and-performance), [`imara-diff`](https://docs.rs/imara-diff/latest/imara_diff/), [Difftastic manual](https://difftastic.wilfred.me.uk/usage.html), [Difftastic 0.70.0 source](https://github.com/Wilfred/difftastic/tree/0.70.0).

### Production systems use progressive disclosure and hard ceilings

GitHub automatically loads only 400 lines and 20 KiB for one file.
Its documented ceilings include 20,000 loadable lines or 500 KiB per file, 20,000 loadable lines or 1 MiB for a pull request, 300 files, and 25 renderable rich files.
Content beyond a limit is not shown.

GitLab separates collapsed and unavailable states.
A file is collapsed when a diff reaches 10% of configured patch, file, or line ceilings, while content exceeding a ceiling is marked `Too large` and cannot be expanded in the UI.

These values are service-specific precedents, not Luigit defaults.
Their transferable pattern is an inexpensive summary, an auto-load budget, an explicit user-triggered expansion budget, and a hard unavailable state.

Sources: [GitHub repository limits](https://docs.github.com/en/repositories/creating-and-managing-repositories/repository-limits#diff-limits), [GitLab diff limits](https://docs.gitlab.com/administration/diff_limits/).

### Browser virtualization has semantic costs

Traditional virtualization keeps only a moving viewport in the DOM.
That lowers layout and paint cost but removes off-screen content from browser find, selection, fragment navigation, printing, copying, and accessibility traversal.
The abandoned native `virtual-scroller` proposal treated the DOM as the source of truth for those capabilities and explicitly identified initial parsing of a huge server-rendered DOM as a remaining problem.

CSS `content-visibility: auto` can skip layout and paint outside the viewport while retaining document content.
It does not remove HTML transfer, parse, node-memory, or initial DOM-construction costs, so it helps medium results rather than arbitrarily large ones.

Sources: [WICG virtual scroller explainer](https://wicg.github.io/virtual-scroller/), [CSS Containment Level 2](https://www.w3.org/TR/css-contain-2/#content-visibility), [MDN `content-visibility`](https://developer.mozilla.org/en-US/docs/Web/CSS/content-visibility).

### Progressive delivery does not imply progressive diffing

HTTP can deliver response bytes before the full body is generated, but intermediaries may buffer and compression may delay visible chunks.
Caddy's reverse proxy supports response flushing controls and otherwise makes latency-sensitive flush decisions for streaming responses.
The deployed path must therefore be measured through Caddy rather than inferred from application behavior.

Per-file progressive delivery is robust because each file result is independently valid.
Streaming an unfinished hunk sequence is weaker: later computation can fail, a disconnected client can leave work running, and an HTML document can end mid-structure.
Bounded computation should produce an internally complete file result before exposing it as complete.

Sources: [Caddy `reverse_proxy`](https://caddyserver.com/docs/caddyfile/directives/reverse_proxy), [HTTP semantics](https://www.rfc-editor.org/rfc/rfc9110), [HTTP/1.1 message framing](https://www.rfc-editor.org/rfc/rfc9112).

### Cancellation must propagate into the expensive operation

Client disconnect detection can stop queued or cooperative work.
It cannot safely interrupt arbitrary in-process native or Rust code at an instruction boundary.
A service-level cgroup can cap total process memory and CPU, but it cannot contain one request without affecting other requests.
Hard per-request termination requires a process boundary.

Luigit's one-application-executable constraint still permits worker threads inside the executable, but excludes helper processes as the ordinary runtime design.
Consequently, candidate libraries must support bounded inputs, bounded outputs, frequent deadline or cancellation checks, or workloads small enough to reject before entering an uninterruptible phase.

Sources: [systemd resource control](https://www.freedesktop.org/software/systemd/man/latest/systemd.resource-control.html), [Linux cgroup v2](https://docs.kernel.org/admin-guide/cgroup-v2.html).

### Cache correctness differs from cache admission

Commit, tree, and blob objects are immutable by object identity.
A diff keyed by repository identity, old object ID, new object ID, engine options, and engine version is therefore content-stable.
Public authorization is not immutable: Luigit may render only objects reachable from currently advertised refs.
Every cache hit must recheck current reachability before disclosure.

Large objects can evict many useful small entries.
Weighted admission and eviction must account for stored bytes and recomputation cost rather than entry count alone.
Concurrent identical misses should share one in-flight computation.
Failures caused by transient deadlines or load should not become long-lived negative cache entries.

Sources: [Git object model](https://git-scm.com/book/en/v2/Git-Internals-Git-Objects), [TinyLFU](https://arxiv.org/abs/1512.00727), [Caffeine eviction](https://github.com/ben-manes/caffeine/wiki/Eviction).

## Conclusions

### Use staged work with independent budgets

The request path should be:

1. Revalidate repository visibility and requested object reachability.
2. Discover changed paths and cheap metadata under tree and file-count budgets.
3. Apply bounded rename detection or report rename detection as skipped.
4. Return the complete file summary before computing file bodies.
5. Queue requested file comparisons in a fixed-size worker pool.
6. Compare each selected file as a complete unit under input, line, output, memory, and elapsed-work budgets.
7. Add intraline, syntax, and structural layers only while their separate budgets remain.
8. Store and deliver independently valid file results.

This design prevents one large comparison from monopolizing all request threads and lets backpressure reject or defer new expensive work.
No request may create an unbounded task, queue entry, allocation, output buffer, or cache entry.

### Make degradation explicit and monotonic

Each file needs one observable state:

- `unchanged`: no content change.
- `ready`: inline diff available.
- `collapsed`: available but outside automatic rendering budget.
- `filtered`: hidden by an explicit user filter.
- `binary`: textual rendering is inapplicable; metadata and downloads remain.
- `oversized`: source dimensions exceed comparison policy.
- `truncated`: a bounded partial representation exists, with omitted amount reported.
- `timed out`: computation exceeded its work budget.
- `unavailable`: objects are missing, corrupt, or no longer publicly reachable.

Optional analysis adds independent markers such as `rename detection skipped`, `intraline omitted`, `syntax highlighting omitted`, or `structural fallback`.
A failed enhancement must preserve the canonical textual result when that result succeeded.

### Virtualize rendering, not Git truth

Large comparisons should open on a complete file summary with counts and states.
No-JavaScript navigation should render one file or one bounded hunk page at a time.
JavaScript may prefetch adjacent files, retain a bounded window of rendered file sections, restore scroll position, and cancel work no longer needed.

Use ordinary complete DOM plus `content-visibility: auto` for medium results because browser semantics remain intact.
Use bounded window virtualization only after measured DOM limits are exceeded.
When virtualization is active, provide server-side file and hunk URLs, persistent anchors, full-file raw views, and complete patch download so omitted DOM is still reachable.

### Compute lazily at file granularity

Generate tree and file summaries eagerly.
Do not diff every changed file merely to render the comparison landing page.
Compute a full textual diff only when a file enters the auto-load window, is explicitly opened, is needed for a complete patch download, or is admitted by idle prefetch.

Within a selected file, preserve whole-file alignment.
Viewport-only line diffing is rejected because it can fabricate different hunks as the viewport moves.
Viewport-only syntax highlighting and HTML generation remain valid because they do not alter change facts.

### Separate canonical and presentation caches

Cache the canonical escaped textual diff model separately from rendered layouts and optional analysis.
Use a key containing repository identity, old and new object IDs, comparison mode, algorithm settings, whitespace settings, context size, engine version, and schema version.
Rendered unified and side-by-side fragments may use smaller derivative caches.

Apply per-entry and total-byte ceilings before admission.
Prefer inexpensive weighted recency or frequency eviction available in the selected implementation stack; do not build a novel cache policy before measurements justify it.
Expose cache bytes, entry count, admissions, evictions, hit rate, in-flight deduplication, and reclamation failures.

### Treat complete patch download as a separate workload

A complete patch route may stream canonical textual output without constructing browser HTML.
It still requires the same reachability checks and total byte, file, line, line-length, rename-candidate, CPU, memory, and concurrency limits.
If policy prevents complete generation, return a clear failure before labeling any body complete.
Do not call a truncated artifact a complete patch.

### Start from measured tiers, not copied forge numbers

Use GitHub and GitLab values only as experiment baselines.
Derive Luigit thresholds from the klops container budget, representative public repositories, Caddy behavior, and concurrent-request targets.
Keep separate thresholds for automatic display, explicit expansion, and absolute refusal.

Initial tuning must include ordinary edits, fully dissimilar files, repeated lines, generated lockfiles, minified single lines, giant lines, binary blobs, hundreds of files, rename-candidate explosions, syntax parse failures, and concurrent cancellation.
Measure wall time, CPU time, peak resident memory, allocations, output bytes, time to first summary, time to first file, browser parse time, DOM nodes, long tasks, scroll stability, and post-cancellation resource release.

## Evidence needed before implementation choice

- Confirm the selected Git library can enumerate deltas without loading every blob and can cap rename detection.
- Confirm the selected textual diff library's cancellation frequency, peak memory, output bound, and fallback semantics with adversarial fixtures.
- Determine whether structural analysis can obey byte, node, graph-state, CPU, and memory budgets in-process.
- Measure Caddy time-to-first-byte and chunk visibility with compression enabled and disabled.
- Find the browser threshold where complete DOM plus `content-visibility` loses to bounded virtualization on desktop and mobile hardware.
- Verify keyboard navigation, focus retention, anchors, copy, selection, find, print, and screen-reader equivalents in both rendering modes.
- Verify client disconnect, superseded requests, and navigation cancel queued and active cooperative work promptly.
- Verify cache reachability checks prevent stale derived data from exposing objects removed from advertised refs.

## Recommendation

Adopt summary-first, per-file lazy comparison with a fixed worker pool, cooperative cancellation, phase-specific hard budgets, and explicit degraded states.
Use complete server-rendered file pages as the accessibility and no-JavaScript baseline; add `content-visibility` for medium results and bounded DOM virtualization only above measured thresholds.
Do not promise viewport-only diff computation or hard per-request isolation inside one process because neither is technically sound under the current constraints.