Add a keyboard-driven file finder to the Gitiles header
Pressing "/" on any page that addresses a commit opens a palette that
fuzzy-matches every blob path in that revision; Enter navigates
straight to the file.
The index is the paths_only tree listing, fetched on first open rather
than on page load, so a reader who never searches costs the server
nothing. Its URL is pinned to the resolved commit SHA: BaseServlet
only marks a response cacheable when the revision is named by object
ID, so a branch-named URL would be refetched on every open, and
content addressing retires a stale copy without a revalidation
roundtrip.
Matching runs in a Worker against a string-free index -- path bytes in
flat buffers with Int32Array offsets -- so no amount of index work can
drop a frame on the main thread. Directories are interned, collapsing
chromium/src from 506,237 paths to 46,286 directory runs, and the byte
buffers are trimmed to what was written. The whole index is then 28 MB
against 37 MB of path text: smaller than the corpus it indexes.
There is no cap. Every path in the revision is held and considered; if
a path matches, either it is on screen or twenty strictly
better-ranked paths are.
Ranking
-------
Queries run in tiers, cheapest first, and a tier is skipped only when
a cheaper one has already filled the display. That is exact rather
than heuristic, because the tiers are a strict ordering: nothing a
later one produces can displace what an earlier one found.
A the whole path literally starts with the query
B the basename starts with it
C the basename contains it as a subsequence
D the path contains it as a subsequence
A comes first because B, C and D all score the basename alone, and a
query the directory has already absorbed leaves the basename scoring
nothing. Without A, typing a path got monotonically worse the more of
it you spelled: 1,254 paths start with "base/t" and none of them
reached the top twenty. A is two binary searches, because the index is
in byte order and so those paths are contiguous. It is case-sensitive
by design -- a case-folded range would not be contiguous -- which is
sound only because it promotes and never filters, so a reader who
types the wrong case loses the promotion, not the result.
Greedy directory consumption decides whether a file matches, not how
well. Consuming as much of the query as possible in the directory
leaves the shortest remainder for the basename, which is what makes D
sound and cheap, but it is forced rather than chosen: the directory of
base/base64.h eats "base" out of the query "base64.h", so the file
scored as a directory-assisted match and took D's penalty for that.
Typing a filename exactly then put it at position 9, behind eight
unrelated test pages whose directories happened to contain none of the
query. A basename that carries the whole query on its own is scored as
the basename match it is, whatever the directory could also have
supplied. Only the order changes; the candidate set, and the monotone
narrowing it rests on, are untouched.
Subsequence matching is monotone under query extension, so each
keystroke narrows the previous candidate set and backspace pops it.
Directory prefixes are memoised, which is what makes D affordable: the
506k paths in chromium/src share only 46k distinct directories. D
resumes each directory's greedy match from the length it shares with
the previous one, rejects a file whose basename alone cannot supply
the characters the directory failed to consume, and accepts a whole
directory run wholesale once the directory has consumed the query.
Measured on that corpus (506,237 blobs) under node v22, on the worker
thread: 480 ms to build the index, and 25 ms for the worst keystroke,
which is a basename query. Path-directed queries are answered by A in
under a millisecond. End to end in a browser on the same corpus,
including fetch, gzip, JSON.parse and the postMessage round trip:
1,737 ms from "/" to a usable index and a median keystroke of 1.9 ms.
Android's largest repository, toolchain/rustc at 223,429 paths, is
718 ms and 2.1 ms. Typing does not depend on the link: shaping the
origin to 5 Mbps and 150 ms of RTT leaves the median at 2.0 ms and
moves only the one-time open, to 2.95 s.
When A or B fills the display the engine stops there, so its count is
then a lower bound and the display says so with a trailing "+".
Matched characters are marked in the row. The engine measures in UTF-8
bytes and the UI marks substrings of a JS string, whose indices are
UTF-16 code units, so the offsets are only meaningful for an ASCII
path; on anything else they drifted and marked characters that had not
matched. A path whose byte length differs from its string length is
therefore shown unmarked. That is four paths in chromium/src, and the
link is built from the whole path and was never affected.
Empty state
-----------
An empty box offers the files this reader keeps returning to, best
first, rather than the repository in tree order -- which on
chromium/src means offering ".gn". The score is an exponentially
decayed visit count: on each visit
s <- s * 2^(-dt / HALF_LIFE) + 1
which expands to the sum over past visits of 2^(-age/HALF_LIFE), with
a one-week half-life, so frequent files outrank once-opened ones and
abandoned files fall away. Remembered paths are checked against the
index before they are shown, so a file deleted since it was last
opened is dropped rather than offered as a row that 404s. Only files
opened through the finder are recorded. Ranking for non-empty queries
is untouched, so two readers typing the same query see the same
results in the same order. The store lives in localStorage, is keyed
per repository, holds at most 200 entries, and is a record of what
this reader opened, so on a shared machine it is visible to anyone
with the browser profile. Storage being absent, denied, full or
corrupt falls back to the plain listing. The offered list is cut to
the display limit like every other channel: the UI paints exactly that
many rows but takes its selection bounds from what it was sent, so a
longer list let the selection run off the end of the rows onto nothing.
Warming
-------
The finder resolves a query in single-digit milliseconds and then
hands the reader a link they still have to wait on, so the highlighted
destination is warmed. This is only possible because result links are
SHA-pinned and therefore cacheable. Three mechanisms were measured in
Chrome under the access pattern the finder creates -- many warms on
one page, no reload in between:
link rel=prefetch warms some destinations and cancels others with
ERR_ABORTED; unusable here
fetch, low prio completes every time, lands on disk, but carries
no Sec-Purpose
speculation rules completes every time, lands in the prefetch
cache, carries Sec-Purpose: prefetch
So the warm is a one-URL prefetch rule where the API exists, falling
back to a low-priority fetch where it does not. The rule set is
swapped rather than grown, so at most one destination is speculated on
at a time, and it is torn down when the palette closes. A 250 ms
debounce, a dedupe set and a cap of 32 distinct destinations per
session keep it polite.
Gitiles sets no Content-Security-Policy of its own, so the policy
belongs to whoever deploys it. A script-src carrying neither
'strict-dynamic' nor 'inline-speculation-rules' blocks the rule set,
and a blocked rule reports nothing to the code that installed it, so
warming would stop with no signal. A securitypolicyviolation listener
downgrades to the fetch path, which connect-src governs and which
therefore survives exactly the policy that kills the rule.
Reach
-----
The finder is on every page that names a repository, not only trees.
A keyboard shortcut only earns its keep once it is reflex, and a
reader who hits "/" on the repository index and gets nothing has
learned not to try. Pages that address a revision search that
revision; the repository index and the ref list carry none, so they
fall back to HEAD, which on the index is the tree already on screen. A
revision that peels to something other than a commit deliberately does
not fall back rather than silently answer about different content.
Because the URL is content-addressed, every page in a repository names
the same listing, so it is fetched once and reused across navigations.
Arrow keys, Ctrl-N/P and PageUp/PageDown move the selection; Escape
closes; Enter opens the file and Ctrl/Cmd-Enter opens it in a new tab.
The palette is closed on pagehide so that a page restored from the
back/forward cache does not come back with a stale overlay covering
it.
Focus never leaves the input, so the input names the selected row with
aria-activedescendant -- without it a screen reader is told nothing at
all as the selection travels, which for a feature that exists to be
driven from the keyboard is most of the feature. Rows are not tab
stops and Tab is held, so focus cannot walk out of a dialog that
declares itself modal.
Configuration
-------------
Setting gitiles.fileSearch (default true) to false turns the finder
off. The index is linear in the number of paths in the revision and
deliberately uncapped, because a file that exists must be findable, so
a deployment whose repositories are larger than anything measured here
needs a switch rather than a patch.
A deployment can also decline it without meaning to: a policy with a
restrictive worker-src rejects the Worker constructor synchronously,
with no event to observe. That is caught, because the overlay is
already on screen and the input is not yet focused when it throws --
unhandled, it left a dialog the reader could neither type into nor
close. The reader is told instead, and asking again retries, so a
one-off failure loading the index does not disable the finder for the
life of the page.
Verification
------------
FileSearchTest pins the things that break silently: the listing URL
naming a commit SHA rather than a branch or tag object, the script tag
carrying the request CSP nonce, Markdown documentation pages rendering
the trigger and overlay, and gitiles.fileSearch = false rendering no
finder at all.
The CSP downgrade was driven in headless Chrome against a served
script-src 'self', paired against the same proxy without the header:
the hardened run reports a script-src-elem violation, drops the rule
and still warms the highlighted destination exactly once; the control
reports no violation, keeps the rule and also warms exactly once.
The engine was checked against a brute-force oracle over all 506,237
paths of chromium/src: every path is findable by its own basename, no
displayed row fails to match, and a reported total is exact whenever
the engine claims exactness and a true lower bound otherwise. The
resumed directory pass was additionally compared against an
independent per-directory rescan for 3,021 queries across all 46,286
directories, 139,830,006 comparisons, with no disagreement. The
palette, the empty state and the warming were driven end to end in
headless Chrome against the same repository.
Ranking, the empty state at more than a screenful, the unmarked
non-ASCII row, aria-activedescendant tracking the selection, Tab being
held, and a refused Worker constructor were each driven in headless
Chrome against chromium/src. Scoring a basename-only match as one
costs nothing measurable: over eight queries spanning every channel,
the median keystroke moves by at most 0.05 ms either way and the index
build is unchanged.
Eighteen unit tests drive the worker through its message protocol on
the js_test lane, covering the listing load and its failure, ranking,
the promoted path-prefix and basename-prefix channels, negative-scored
weak matches, directory highlight ranges, the unmarked non-ASCII row,
leading U+FEFF preservation, and the cut to the displayed row count.
Each was checked against a mutant: reverting the basename-first
scoring fix, the ASCII guard on highlight ranges, or the cut to LIMIT
makes the suite fail, and the unmutated worker passes 18 of 18.
Thirty-five more drive the palette itself. jstests/fake_dom.js is not
a browser and does not try to be one: it is a recording of the calls
the script makes -- attributes set, classes toggled, preventDefault
counts, timers queued, storage written -- and what it declines to
model is listed in its header. That is the right shape here because
what is worth pinning is this script's own bookkeeping rather than any
browser semantics. The tests cover opening and dismissal, row reuse
and the cut to twenty, selection clamping and aria-activedescendant,
IME composition guards, the worker handshake and the ways it can fail,
the frecency store's decay, cap and empty fallback, and warming both
under speculation rules and after a policy has refused them.
Nine reverted fixes were each caught: not resetting the selection on a
new query, clamping it to the result count rather than to the rows on
screen, leaving rows in the tab order, dropping the row ids, dropping
aria-activedescendant, letting Tab escape the palette, leaving the
Worker constructor unguarded, dropping the exponential decay, and
leaving the store uncapped. Unmutated, 35 of 35 pass.
Bug: 564986686
TAG=agy
CONV=0b3e4b30-d902-4587-8bb2-ce23109d6955
CONV=60d1bfdf-34a4-460e-85ab-0f251e052543
Change-Id: I32240619cb19aedb30cbf82f96c926031a242d74
Gitiles is a simple repository browser for Git repositories, built on JGit. Its guiding principle is simplicity: it has no formal access controls, no write access, no fancy Javascript, etc.
Gitiles automatically renders *.md Markdown files into HTML for simplified documentation. Refer to the Markdown documentation for details.
Gitiles is configurable in a git-style configuration file named gitiles.config. Refer to the configuration documentation for details.
Use gerrit's issue tracker to file bugs.
Please refer to the Developer Guide.