Merge "Exclude org.json pulled in by Closure Templates"
diff --git a/Documentation/config.md b/Documentation/config.md index c9c7448..ecca7e3 100644 --- a/Documentation/config.md +++ b/Documentation/config.md
@@ -140,6 +140,24 @@ redirectGitweb = false ``` +### File finder + +Serve the keyboard-driven finder, opened with `/` to search files on any page +that names a repository and repositories on the host index. Default: `true`. + +The finder is inert until a reader presses `/`; nothing is fetched and no index +is built before that. When it is opened on a repository page, the browser +downloads the revision's complete path listing and builds an index over it, both +linear in the number of paths and deliberately uncapped, so that a file which +exists is always findable. On the host index it indexes the repositories already +rendered on the page without an extra request. Set this to `false` to disable +both. + +``` +[gitiles] +fileSearch = false +``` + ## Markdown ### Disabling markdown
diff --git a/java/com/google/gitiles/Renderer.java b/java/com/google/gitiles/Renderer.java index fe22701..9931dab 100644 --- a/java/com/google/gitiles/Renderer.java +++ b/java/com/google/gitiles/Renderer.java
@@ -18,6 +18,7 @@ import static com.google.common.base.Preconditions.checkNotNull; import static com.google.common.base.Preconditions.checkState; import static java.nio.charset.StandardCharsets.UTF_8; +import static org.eclipse.jgit.lib.Constants.OBJ_COMMIT; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; @@ -45,8 +46,15 @@ import java.util.concurrent.ConcurrentMap; import java.util.function.Function; import java.util.zip.GZIPOutputStream; +import javax.annotation.Nullable; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; +import org.eclipse.jgit.http.server.ServletUtils; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.Repository; +import org.eclipse.jgit.revwalk.RevObject; +import org.eclipse.jgit.revwalk.RevWalk; /** * Renderer for Soy templates used by Gitiles. @@ -100,6 +108,8 @@ .put("gitiles.FAVICON_32_URL", "favicon-32x32.png") .put("gitiles.FAVICON_16_URL", "favicon-16x16.png") .put("gitiles.APPLE_TOUCH_ICON_URL", "apple-touch-icon.png") + .put("gitiles.FILE_SEARCH_JS_URL", "file-search.js") + .put("gitiles.FILE_SEARCH_WORKER_JS_URL", "file-search-worker.js") .buildOrThrow(); protected static Function<String, URL> fileUrlMapper() { @@ -242,11 +252,12 @@ }; } - SoySauce.Renderer newRenderer(String templateName) { + SoySauce.Renderer newRenderer(String templateName) throws IOException { return newRenderer(templateName, Optional.empty()); } - SoySauce.Renderer newRenderer(String templateName, Optional<HttpServletRequest> req) { + SoySauce.Renderer newRenderer(String templateName, Optional<HttpServletRequest> req) + throws IOException { ImmutableMap.Builder<String, Object> staticUrls = ImmutableMap.builder(); for (String key : STATIC_URL_GLOBALS.keySet()) { staticUrls.put( @@ -263,9 +274,123 @@ if (nonce.isPresent()) { ij.put("csp_nonce", nonce.get()); } + if (req.isPresent() && fileSearchEnabled(req.get())) { + String searchTreeUrl = fileSearchTreeUrl(req.get()); + if (searchTreeUrl != null) { + ij.put("SEARCH_TREE_URL", searchTreeUrl); + } else if (isHostIndex(req.get())) { + ij.put("SEARCH_REPOSITORIES", true); + } + } return getSauce().renderTemplate(templateName).setIj(ij.buildOrThrow()); } + /** + * Whether this deployment serves the file finder, from {@code gitiles.fileSearch}. + * + * <p>Defaults to true. The finder costs a deployment nothing until a reader presses "/", but the + * index it then builds is linear in the number of paths in the revision and has deliberately no + * cap, so an administrator whose repositories are far larger than anything upstream has measured + * needs a way to decline it without patching. + * + * <p>Access is read rather than required: {@link BaseServlet} initializes it before rendering any + * HTML, so it is present on every page that could carry the finder, and a request that somehow + * arrives without one is left with the default rather than silently losing the feature. + */ + private static boolean fileSearchEnabled(HttpServletRequest req) throws IOException { + Optional<GitilesAccess> access = GitilesAccess.getAccess(req); + if (access.isEmpty()) { + return true; + } + return access.get().getConfig().getBoolean("gitiles", null, "fileSearch", true); + } + + /** + * Whether this request renders a host index, the page that lists a host's repositories. + * + * <p>Such a page addresses no tree, so there are no file paths to find, but it is a listing all + * the same and the same keystroke should search it. No URL accompanies this signal because none + * is needed: the page already contains every repository it lists, so the finder reads them from + * the document rather than asking for them a second time. That also makes the finder's answers + * agree with the page by construction. + */ + private static boolean isHostIndex(HttpServletRequest req) { + GitilesView view = ViewFilter.getView(req); + return view != null && view.getType() == GitilesView.Type.HOST_INDEX; + } + + /** + * URL of the complete blob path listing the file finder should index, or null if this request + * addresses no tree at all. + * + * <p>The URL is pinned to the resolved commit SHA rather than to whatever name the user typed. + * {@link BaseServlet#setCacheHeaders} only marks a response cacheable when the revision is named + * by object ID; a branch-named URL is served {@code no-store} and would therefore be re-fetched + * on every use. Content addressing additionally means a new commit produces a new URL, so a + * client's copy is invalidated without a revalidation roundtrip. + * + * <p>Note the empty path part: a {@code PATH} view renders as {@code /+/<rev>/}, and the trailing + * slash is what distinguishes the root tree from the revision itself. + */ + @Nullable + private static String fileSearchTreeUrl(HttpServletRequest req) throws IOException { + GitilesView view = ViewFilter.getView(req); + if (view == null || view.getRepositoryName() == null) { + return null; + } + ObjectId commit = fileSearchCommit(req, view); + if (commit == null) { + return null; + } + return GitilesView.path() + .setHostName(view.getHostName()) + .setServletPath(view.getServletPath()) + .setRepositoryName(view.getRepositoryName()) + .setRevision(commit.name()) + .setPathPart("") + .putParam("format", "JSON") + .putParam("recursive", "1") + .putParam("paths_only", "1") + .toUrl(); + } + + /** + * The commit whose paths the finder should offer, or null if there is no sensible one. + * + * <p>Pages that address a revision use it, so the finder always searches what the reader is + * looking at. The repository index and the ref list address a repository but no revision, and + * skipping them would be the worst outcome for a keyboard shortcut: the repository index is where + * readers arrive, so {@code /} has to work there or it never becomes muscle memory. Those pages + * fall back to {@code HEAD}, which for the repository index is exactly the tree already on + * screen. + * + * <p>A revision that peels to something other than a commit deliberately does <em>not</em> fall + * back. Searching {@code HEAD} while the reader is looking at a tagged tree would silently answer + * about different content, and scoping the finder to what is displayed is a property worth more + * than one extra page's coverage. + */ + @Nullable + private static ObjectId fileSearchCommit(HttpServletRequest req, GitilesView view) + throws IOException { + Revision rev = view.getRevision(); + if (rev != null && !Revision.isNull(rev) && rev.getId() != null) { + return rev.getPeeledType() == OBJ_COMMIT ? rev.getPeeledId() : null; + } + Object attr = req.getAttribute(ServletUtils.ATTRIBUTE_REPOSITORY); + if (!(attr instanceof Repository repo)) { + return null; + } + ObjectId headId = repo.resolve(Constants.HEAD); + if (headId == null) { + // Unborn HEAD: an empty repository has nothing to find. + return null; + } + try (RevWalk walk = new RevWalk(repo)) { + RevObject head = walk.peel(walk.parseAny(headId)); + return head.getType() == OBJ_COMMIT ? head.copy() : null; + } + } + protected abstract SoySauce getSauce(); /**
diff --git a/javatests/com/google/gitiles/FileSearchTest.java b/javatests/com/google/gitiles/FileSearchTest.java new file mode 100644 index 0000000..68414e6 --- /dev/null +++ b/javatests/com/google/gitiles/FileSearchTest.java
@@ -0,0 +1,261 @@ +// Copyright (C) 2026 Google Inc. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package com.google.gitiles; + +import static com.google.common.truth.Truth.assertThat; +import static javax.servlet.http.HttpServletResponse.SC_OK; + +import java.util.regex.Matcher; +import java.util.regex.Pattern; +import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription; +import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.lib.Config; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevTag; +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Tests for the file finder markup emitted by {@code Common.soy}. */ +@RunWith(JUnit4.class) +public class FileSearchTest extends ServletTest { + private static final String REPO_NAME = "test-repo"; + + private static final Pattern TREE_URL = + Pattern.compile("data-tree-url=\"([^\"]*)\""); + + @Override + @Before + public void setUp() throws Exception { + repo = new TestRepository<>(new InMemoryRepository(new DfsRepositoryDescription(REPO_NAME))); + servlet = TestGitilesServlet.create(repo); + } + + @Test + public void treeViewRendersTriggerAndOverlay() throws Exception { + repo.branch("master").commit().add("dir/file.txt", "contents").create(); + String html = buildHtml("/" + REPO_NAME + "/+/master/dir/", false); + assertThat(html).contains("Header-menuItem FileSearch-trigger"); + assertThat(html).contains("id=\"file-search\""); + assertThat(html).contains("file-search.js"); + } + + @Test + public void blobViewRendersOverlay() throws Exception { + repo.branch("master").commit().add("file.txt", "contents").create(); + String html = buildHtml("/" + REPO_NAME + "/+/master/file.txt", false); + assertThat(html).contains("id=\"file-search\""); + } + + @Test + public void markdownDocViewRendersTriggerAndOverlay() throws Exception { + repo.branch("master").commit().add("README.md", "# Title\n").create(); + String html = buildHtml("/" + REPO_NAME + "/+/master/README.md", false); + assertThat(html).contains("Header-menuItem FileSearch-trigger"); + assertThat(html).contains("id=\"file-search\""); + assertThat(html).contains("file-search.js"); + } + + /** + * The listing URL must name the commit by object ID, not by the branch the reader typed. + * {@code BaseServlet#setCacheHeaders} only permits caching when {@code Revision#nameIsId} holds, + * so a branch-named URL would be re-fetched on every open. + */ + @Test + public void treeUrlIsPinnedToTheCommitSha() throws Exception { + RevCommit commit = repo.branch("master").commit().add("file.txt", "contents").create(); + String treeUrl = treeUrl(buildHtml("/" + REPO_NAME + "/+/master/", false)); + assertThat(treeUrl).contains("/+/" + commit.name() + "/?"); + assertThat(treeUrl).doesNotContain("master"); + } + + /** + * An annotated tag has its own object ID distinct from the commit it peels to; pinning the + * listing URL to the peeled commit SHA shares the cached index with commit-addressed views and + * ensures result links resolve as paths rather than failing {@code PathServlet}'s tag peel. + */ + @Test + public void annotatedTagIsPinnedToThePeeledCommitSha() throws Exception { + RevCommit commit = repo.branch("master").commit().add("file.txt", "contents").create(); + RevTag tag = repo.tag("v1.0", commit); + repo.update("refs/tags/v1.0", tag); + String treeUrl = treeUrl(buildHtml("/" + REPO_NAME + "/+/v1.0/", false)); + assertThat(treeUrl).contains("/+/" + commit.name() + "/?"); + assertThat(treeUrl).doesNotContain(tag.name()); + } + + /** A recursive listing scoped to the root tree; the trailing slash is what selects the tree. */ + @Test + public void treeUrlRequestsACompleteRecursiveListing() throws Exception { + repo.branch("master").commit().add("file.txt", "contents").create(); + String treeUrl = treeUrl(buildHtml("/" + REPO_NAME + "/+/master/", false)); + assertThat(treeUrl).contains("format=JSON"); + assertThat(treeUrl).contains("recursive=1"); + assertThat(treeUrl).contains("paths_only=1"); + } + + /** The listing URL is a live route, not a string we hope resolves. */ + @Test + public void treeUrlResolvesToTheBlobListing() throws Exception { + repo.branch("master").commit().add("dir/file.txt", "contents").add("top.txt", "x").create(); + String treeUrl = treeUrl(buildHtml("/" + REPO_NAME + "/+/master/", false)); + int q = treeUrl.indexOf('?'); + String path = + treeUrl.substring(FakeHttpServletRequest.SERVLET_PATH.length(), q); + TreeJsonData.PathList list = + buildJson(TreeJsonData.PathList.class, path, treeUrl.substring(q + 1)); + assertThat(list.paths).containsExactly("dir/file.txt", "top.txt").inOrder(); + } + + /** + * The repository index is where readers arrive, and it already displays HEAD's tree. If {@code /} + * does not work here it never becomes muscle memory. + */ + @Test + public void repositoryIndexRendersFileSearchScopedToHead() throws Exception { + RevCommit commit = repo.branch("master").commit().add("file.txt", "contents").create(); + repo.getRepository().updateRef("HEAD").link("refs/heads/master"); + String html = buildHtml("/" + REPO_NAME + "/", false); + assertThat(html).contains("id=\"file-search\""); + assertThat(treeUrl(html)).contains("/+/" + commit.name() + "/?"); + } + + /** The ref list addresses a repository but no revision; HEAD is the neutral default. */ + @Test + public void refListRendersFileSearchScopedToHead() throws Exception { + RevCommit commit = repo.branch("master").commit().add("file.txt", "contents").create(); + repo.getRepository().updateRef("HEAD").link("refs/heads/master"); + String html = buildHtml("/" + REPO_NAME + "/+refs/", false); + assertThat(treeUrl(html)).contains("/+/" + commit.name() + "/?"); + } + + @Test + public void logViewRendersFileSearch() throws Exception { + repo.branch("master").commit().add("file.txt", "contents").create(); + assertThat(buildHtml("/" + REPO_NAME + "/+log/master", false)).contains("id=\"file-search\""); + } + + /** + * A host index addresses no revision, so there are no paths to find, but it is a listing all the + * same and {@code /} should search it. No listing URL accompanies it: the page already contains + * every repository it lists, so the finder reads them from the document instead of fetching the + * same names again -- which matters because a host index response names no revision and is + * therefore served {@code no-store}. + */ + @Test + public void hostIndexRendersRepositorySearch() throws Exception { + String html = buildHtml("/", false); + assertThat(html).contains("id=\"file-search\""); + assertThat(html).contains("data-kind=\"repositories\""); + assertThat(html).doesNotContain("data-tree-url"); + assertThat(html).contains("Find repository"); + } + + /** The attribute that tells the two sources apart; the script keys all its behaviour off it. */ + @Test + public void treeViewRendersFileKind() throws Exception { + repo.branch("master").commit().add("file.txt", "contents").create(); + String html = buildHtml("/" + REPO_NAME + "/+/master/", false); + assertThat(html).contains("data-kind=\"files\""); + assertThat(html).contains("Find file"); + assertThat(html).doesNotContain("Find repository"); + } + + /** An empty repository has an unborn HEAD and nothing to find. */ + @Test + public void emptyRepositoryRendersNoFileSearch() throws Exception { + String html = buildHtml("/" + REPO_NAME + "/", false); + assertThat(html).doesNotContain("id=\"file-search\""); + } + + /** + * A revision that peels to something other than a commit does not fall back to HEAD: answering + * about HEAD while the reader looks at a tagged tree would silently search different content. + * {@code TreeSoyData} suppresses its own links under the same condition (TreeSoyData.java:165). + */ + @Test + public void tagPeelingToATreeRendersNoFileSearch() throws Exception { + RevCommit commit = repo.branch("master").commit().add("file.txt", "contents").create(); + repo.getRepository().updateRef("HEAD").link("refs/heads/master"); + RevTag tag = repo.tag("treetag", repo.parseBody(commit).getTree()); + repo.update("refs/tags/treetag", tag); + String html = buildHtml("/" + REPO_NAME + "/+/treetag", false); + assertThat(html).doesNotContain("id=\"file-search\""); + assertThat(html).doesNotContain("FileSearch-trigger"); + } + + /** + * A deployment can decline the finder. The index it builds is linear in the number of paths in + * the revision and uncapped by design, so an administrator whose repositories are larger than + * anything upstream has measured needs a switch rather than a patch. + */ + @Test + public void fileSearchDisabledByConfigRendersNothing() throws Exception { + Config config = new Config(); + config.setBoolean("gitiles", null, "fileSearch", false); + servlet = TestGitilesServlet.create(repo, config); + repo.branch("master").commit().add("dir/file.txt", "contents").create(); + + String html = buildHtml("/" + REPO_NAME + "/+/master/dir/", false); + + assertThat(html).doesNotContain("FileSearch-trigger"); + assertThat(html).doesNotContain("id=\"file-search\""); + assertThat(html).doesNotContain("file-search.js"); + } + + /** One switch covers both listings: the host index branch sits inside the same guard. */ + @Test + public void fileSearchDisabledByConfigRendersNoRepositorySearch() throws Exception { + Config config = new Config(); + config.setBoolean("gitiles", null, "fileSearch", false); + servlet = TestGitilesServlet.create(repo, config); + + String html = buildHtml("/", false); + + assertThat(html).doesNotContain("id=\"file-search\""); + assertThat(html).doesNotContain("data-kind=\"repositories\""); + } + + /** + * The overlay ships as an external script so it can be cached and so it survives a content + * security policy that forbids inline script. Soy annotates the tag with {@code $ij.csp_nonce} + * when the request carries a nonce; this test is what keeps it that way. + */ + @Test + public void scriptTagCarriesTheRequestNonce() throws Exception { + repo.branch("master").commit().add("file.txt", "contents").create(); + FakeHttpServletRequest req = FakeHttpServletRequest.newRequest(); + req.setPathInfo("/" + REPO_NAME + "/+/master/"); + req.setAttribute("nonce", "test-nonce-value"); + FakeHttpServletResponse res = new FakeHttpServletResponse(); + servlet.service(req, res); + assertThat(res.getStatus()).isEqualTo(SC_OK); + + String html = res.getActualBodyString(); + Matcher m = + Pattern.compile("<script[^>]*file-search\\.js[^>]*>").matcher(html); + assertThat(m.find()).isTrue(); + assertThat(m.group()).contains("nonce=\"test-nonce-value\""); + } + + private static String treeUrl(String html) { + Matcher m = TREE_URL.matcher(html); + assertThat(m.find()).isTrue(); + // The attribute is HTML-escaped in the document; the browser unescapes it for us. + return m.group(1).replace("&", "&"); + } +}
diff --git a/javatests/com/google/gitiles/TestGitilesAccess.java b/javatests/com/google/gitiles/TestGitilesAccess.java index 27e10cc..c0a92af 100644 --- a/javatests/com/google/gitiles/TestGitilesAccess.java +++ b/javatests/com/google/gitiles/TestGitilesAccess.java
@@ -23,15 +23,26 @@ import java.util.Map; import java.util.Set; import javax.servlet.http.HttpServletRequest; +import org.eclipse.jgit.errors.ConfigInvalidException; import org.eclipse.jgit.internal.storage.dfs.DfsRepository; import org.eclipse.jgit.lib.Config; /** Gitiles access for testing. */ public class TestGitilesAccess implements GitilesAccess.Factory { private final DfsRepository repo; + private final Config overrides; public TestGitilesAccess(DfsRepository repo) { + this(repo, new Config()); + } + + /** + * @param overrides settings applied on top of the defaults, for tests that exercise + * configuration-dependent behaviour. + */ + public TestGitilesAccess(DfsRepository repo, Config overrides) { this.repo = checkNotNull(repo); + this.overrides = checkNotNull(overrides); } @Override @@ -84,6 +95,15 @@ config.setBoolean("markdown", null, "smartquote", true); config.setStringList( "gitiles", null, "allowOriginRegex", ImmutableList.of("http://localhost")); + String extra = overrides.toText(); + if (!extra.isEmpty()) { + // Config merges by re-parsing, and a later entry wins over an earlier one. + try { + config.fromText(config.toText() + extra); + } catch (ConfigInvalidException e) { + throw new IllegalStateException("invalid config override in test", e); + } + } return config; } };
diff --git a/javatests/com/google/gitiles/TestGitilesServlet.java b/javatests/com/google/gitiles/TestGitilesServlet.java index b68ea87..3cd234e 100644 --- a/javatests/com/google/gitiles/TestGitilesServlet.java +++ b/javatests/com/google/gitiles/TestGitilesServlet.java
@@ -46,6 +46,18 @@ } /** + * Create a servlet whose {@link GitilesAccess} reports the given configuration. + * + * @param repo the test repo backing the servlet. + * @param config settings applied on top of the test defaults. + * @return a servlet. + */ + public static GitilesServlet create(final TestRepository<DfsRepository> repo, Config config) + throws ServletException { + return create(repo, new GitwebRedirectFilter(), new BranchRedirect(), config); + } + + /** * Create a servlet backed by a single test repository. * * <p>The servlet uses the same filter lists as a real servlet, but only knows about a single @@ -64,6 +76,15 @@ GitwebRedirectFilter gitwebRedirect, BranchRedirect branchRedirect) throws ServletException { + return create(repo, gitwebRedirect, branchRedirect, new Config()); + } + + private static GitilesServlet create( + final TestRepository<DfsRepository> repo, + GitwebRedirectFilter gitwebRedirect, + BranchRedirect branchRedirect, + Config accessConfig) + throws ServletException { final String repoName = repo.getRepository().getDescription().getRepositoryName(); GitilesServlet servlet = new GitilesServlet( @@ -71,7 +92,7 @@ new DefaultRenderer( GitilesServlet.STATIC_PREFIX, ImmutableList.<URL>of(), repoName + " test site"), TestGitilesUrls.URLS, - new TestGitilesAccess(repo.getRepository()), + new TestGitilesAccess(repo.getRepository(), accessConfig), new RepositoryResolver<HttpServletRequest>() { @Override public Repository open(HttpServletRequest req, String name)
diff --git a/jstests/BUILD b/jstests/BUILD index a18ee55..62e29e8 100644 --- a/jstests/BUILD +++ b/jstests/BUILD
@@ -1,6 +1,21 @@ load("//tools:js_test.bzl", "js_test") js_test( + name = "file_search_test", + srcs = ["file_search_test.js"], + data = [ + "fake_dom.js", + "//resources/com/google/gitiles", + ], +) + +js_test( + name = "file_search_worker_test", + srcs = ["file_search_worker_test.js"], + data = ["//resources/com/google/gitiles"], +) + +js_test( name = "js_test_rule_test", srcs = ["js_test_rule_test.js"], data = ["//resources/com/google/gitiles"],
diff --git a/jstests/fake_dom.js b/jstests/fake_dom.js new file mode 100644 index 0000000..b2c7dcd --- /dev/null +++ b/jstests/fake_dom.js
@@ -0,0 +1,606 @@ +// Copyright (C) 2026 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// A recording stand-in for the browser APIs file-search.js uses. +// +// What this is +// ------------ +// file-search.js is an IIFE that exports nothing and starts by looking for +// #file-search in the document. The only way to reach it is to give it a +// document. This builds the smallest one that lets it run, and records what it +// does to it. +// +// What it models faithfully +// ------------------------- +// Bookkeeping the finder performs itself: attributes set and removed, classes +// toggled, children appended, listeners registered and called, timers queued, +// storage read and written. Assertions about those are assertions about our +// code, and a recording cannot drift from what was recorded. +// +// What it does NOT model, and must not be asserted on +// --------------------------------------------------- +// * Event bubbling. `fire()` invokes listeners on the element they were +// registered on; a test names the target explicitly. The finder's own +// handlers use `ev.target.closest(...)`, which is honoured, but a test +// must not expect a click on a child to reach a parent's listener. +// * Focus semantics beyond "focus() was called, and activeElement moved". +// * Layout. scrollIntoView is counted, nothing more. +// * Content-Security-Policy, speculation rules, prefetch caching and +// navigation. Those are observed as "the finder asked", never as "the +// browser complied". The headless-browser checks cover the rest. +// +// Selector support is deliberately partial: descendant chains of class +// selectors with an optional attribute-presence test, which is everything +// file-search.js asks for and nothing more. An unsupported selector throws +// rather than quietly matching nothing. + +'use strict'; + +const fs = require('node:fs'); +const vm = require('node:vm'); + +const SRC = 'resources/com/google/gitiles/static/file-search.js'; + +// ------------------------------------------------------------------ nodes + +class TextNode { + constructor(text) { + this.nodeType = 3; + this.textContent = text; + this.parentNode = null; + } + get text() { + return this.textContent; + } +} + +class ClassList { + constructor(el) { + this.el = el; + } + _set() { + return new Set(this.el.className ? this.el.className.split(/\s+/).filter(Boolean) : []); + } + _write(s) { + this.el.className = Array.from(s).join(' '); + } + add(n) { + const s = this._set(); + s.add(n); + this._write(s); + } + remove(n) { + const s = this._set(); + s.delete(n); + this._write(s); + } + contains(n) { + return this._set().has(n); + } + toggle(n, force) { + const on = force === undefined ? !this.contains(n) : !!force; + if (on) this.add(n); + else this.remove(n); + return on; + } +} + +class Element { + constructor(tagName, doc) { + this.tagName = String(tagName).toUpperCase(); + this.ownerDocument = doc; + this.nodeType = 1; + this.childNodes = []; + this.parentNode = null; + this.attributes = Object.create(null); + this.className = ''; + this.classList = new ClassList(this); + this.hidden = false; + this.listeners = Object.create(null); + this.scrollCount = 0; + this.focusCount = 0; + } + + // --- attributes. id/href/tabIndex/type are properties the finder sets + // directly as well as through setAttribute, so keep the two in step. + setAttribute(n, v) { + this.attributes[n] = String(v); + } + getAttribute(n) { + return n in this.attributes ? this.attributes[n] : null; + } + removeAttribute(n) { + delete this.attributes[n]; + } + hasAttribute(n) { + return n in this.attributes; + } + + get id() { + return this.getAttribute('id') || ''; + } + set id(v) { + this.setAttribute('id', v); + } + get href() { + return this.getAttribute('href'); + } + set href(v) { + this.setAttribute('href', v); + } + get tabIndex() { + return this.hasAttribute('tabindex') ? Number(this.getAttribute('tabindex')) : 0; + } + set tabIndex(v) { + this.setAttribute('tabindex', v); + } + get type() { + return this.getAttribute('type') || ''; + } + set type(v) { + this.setAttribute('type', v); + } + get nonce() { + return this.getAttribute('nonce') || ''; + } + set nonce(v) { + this.setAttribute('nonce', v); + } + + // --- children + appendChild(child) { + if (child.parentNode) child.parentNode.removeChild(child); + child.parentNode = this; + this.childNodes.push(child); + return child; + } + removeChild(child) { + const i = this.childNodes.indexOf(child); + if (i >= 0) this.childNodes.splice(i, 1); + child.parentNode = null; + return child; + } + remove() { + if (this.parentNode) this.parentNode.removeChild(this); + } + get firstChild() { + return this.childNodes.length ? this.childNodes[0] : null; + } + get children() { + return this.childNodes.filter((n) => n.nodeType === 1); + } + + get textContent() { + return this.childNodes.map((n) => n.textContent).join(''); + } + set textContent(v) { + this.childNodes = []; + if (v !== '') this.appendChild(new TextNode(String(v))); + } + + // --- queries + querySelector(sel) { + return descendants(this).find((e) => matches(e, sel)) || null; + } + querySelectorAll(sel) { + return descendants(this).filter((e) => matches(e, sel)); + } + closest(sel) { + for (let e = this; e; e = e.parentNode) { + if (e.nodeType === 1 && matches(e, sel)) return e; + } + return null; + } + + // --- events and the two side effects worth counting + addEventListener(type, fn) { + (this.listeners[type] || (this.listeners[type] = [])).push(fn); + } + scrollIntoView() { + this.scrollCount++; + } + focus() { + this.focusCount++; + if (this.ownerDocument) this.ownerDocument.activeElement = this; + } +} + +function descendants(el) { + const out = []; + const walk = (n) => { + for (const c of n.childNodes) { + if (c.nodeType !== 1) continue; + out.push(c); + walk(c); + } + }; + walk(el); + return out; +} + +// --------------------------------------------------------------- selectors + +/** Parses ".A .B[attr]" into a list of simple selectors, innermost last. */ +function parse(sel) { + return sel + .trim() + .split(/\s+/) + .map((part) => { + const m = /^(\.[A-Za-z0-9_-]+|[A-Za-z]+)(?:\[([A-Za-z-]+)\])?$/.exec(part); + if (!m) throw new Error(`fake_dom: unsupported selector ${JSON.stringify(sel)}`); + return { + cls: m[1][0] === '.' ? m[1].slice(1) : null, + tag: m[1][0] === '.' ? null : m[1].toUpperCase(), + attr: m[2] || null, + }; + }); +} + +function simpleMatches(el, s) { + if (s.cls && !el.classList.contains(s.cls)) return false; + if (s.tag && el.tagName !== s.tag) return false; + if (s.attr && !el.hasAttribute(s.attr)) return false; + return true; +} + +function matches(el, sel) { + const parts = parse(sel); + if (!simpleMatches(el, parts[parts.length - 1])) return false; + let i = parts.length - 2; + for (let e = el.parentNode; e && i >= 0; e = e.parentNode) { + if (e.nodeType === 1 && simpleMatches(e, parts[i])) i--; + } + return i < 0; +} + +// --------------------------------------------------------------- the world + +class Document { + constructor() { + this.nodeType = 9; + this.childNodes = []; + this.listeners = Object.create(null); + this.activeElement = null; + this.head = new Element('head', this); + this.body = new Element('body', this); + this.appendChild(this.head); + this.appendChild(this.body); + // A real document always has an active element; it is the body when + // nothing else has focus. Starting at null made "/" look like it was + // being typed into whatever was focused last. + this.activeElement = this.body; + } + createElement(tag) { + return new Element(tag, this); + } + createTextNode(t) { + return new TextNode(t); + } + appendChild(c) { + c.parentNode = this; + this.childNodes.push(c); + return c; + } + getElementById(id) { + return descendants(this).find((e) => e.id === id) || null; + } + querySelector(sel) { + return descendants(this).find((e) => matches(e, sel)) || null; + } + querySelectorAll(sel) { + return descendants(this).filter((e) => matches(e, sel)); + } + addEventListener(type, fn) { + (this.listeners[type] || (this.listeners[type] = [])).push(fn); + } +} + +/** Invokes the listeners registered on `el` for `type`. No bubbling. */ +function fire(el, type, event) { + const ev = Object.assign({target: el, preventDefaultCount: 0}, event); + ev.preventDefault = () => { + ev.preventDefaultCount++; + }; + for (const fn of el.listeners[type] || []) fn(ev); + return ev; +} + +/** A clock the test drives, standing in for both timers and Date.now. */ +class Clock { + constructor() { + this.now = 1700000000000; + this.timers = new Map(); + this.next = 1; + } + setTimeout(fn, ms) { + const id = this.next++; + this.timers.set(id, {at: this.now + (ms || 0), fn}); + return id; + } + clearTimeout(id) { + this.timers.delete(id); + } + /** Runs everything due within `ms`, in time order. */ + advance(ms) { + const until = this.now + ms; + for (;;) { + let due = null; + for (const [id, t] of this.timers) { + if (t.at <= until && (due === null || t.at < due[1].at)) due = [id, t]; + } + if (!due) break; + this.timers.delete(due[0]); + this.now = due[1].at; + due[1].fn(); + } + this.now = until; + } +} + +class FakeStorage { + constructor(opts) { + this.map = new Map(); + this.throwOnGet = (opts && opts.throwOnGet) || false; + this.throwOnSet = (opts && opts.throwOnSet) || false; + } + getItem(k) { + if (this.throwOnGet) throw new Error('storage disabled'); + return this.map.has(k) ? this.map.get(k) : null; + } + setItem(k, v) { + if (this.throwOnSet) throw new Error('storage full'); + this.map.set(k, String(v)); + } +} + +// ------------------------------------------------------------------ set-up + +/** + * Builds the markup Common.soy renders for the palette. + * + * Kept to what file-search.js actually reaches for: the root and its three + * children, plus the trigger. The real template carries a backdrop and + * labelling this does not need. + */ +function buildPalette(doc, {workerUrl, treeUrl, kind}) { + const root = doc.createElement('div'); + root.id = 'file-search'; + root.hidden = true; + root.setAttribute('data-worker-url', workerUrl); + if (treeUrl) root.setAttribute('data-tree-url', treeUrl); + if (kind) root.setAttribute('data-kind', kind); + + const backdrop = doc.createElement('div'); + backdrop.className = 'FileSearch-backdrop'; + root.appendChild(backdrop); + + const input = doc.createElement('input'); + input.className = 'FileSearch-input'; + input.value = ''; + root.appendChild(input); + + const status = doc.createElement('div'); + status.className = 'FileSearch-status'; + root.appendChild(status); + + const list = doc.createElement('ul'); + list.className = 'FileSearch-results'; + root.appendChild(list); + + doc.body.appendChild(root); + + const trigger = doc.createElement('button'); + trigger.className = 'FileSearch-trigger'; + doc.body.appendChild(trigger); + + return {root, backdrop, input, status, list, trigger}; +} + +/** Builds the RepoList markup the host index renders, including the header row. */ +function buildRepoList(doc, repos) { + const wrap = doc.createElement('div'); + wrap.className = 'RepoList'; + const header = doc.createElement('div'); + header.className = 'RepoList-item RepoList-item--header'; + const headerName = doc.createElement('span'); + headerName.className = 'RepoList-itemName'; + headerName.textContent = 'Repository'; + header.appendChild(headerName); + wrap.appendChild(header); + for (const r of repos) { + const item = doc.createElement('a'); + item.className = 'RepoList-item'; + item.setAttribute('href', r.href); + const name = doc.createElement('span'); + name.className = 'RepoList-itemName'; + name.textContent = r.name; + item.appendChild(name); + if (r.desc) { + const d = doc.createElement('span'); + d.className = 'RepoList-itemDescription'; + d.textContent = r.desc; + item.appendChild(d); + } + wrap.appendChild(item); + } + doc.body.appendChild(wrap); + return wrap; +} + +/** + * Loads file-search.js against a fresh fake document. + * + * Options: + * kind 'files' (default) or 'repositories' + * repos [{name, href, desc}] for the host index + * workerFactory (url) => fake worker, or a function that throws to model a + * constructor refused by policy + * noWorker omit the Worker global entirely + * storage {throwOnGet, throwOnSet} + * speculation whether HTMLScriptElement.supports('speculationrules') is true + */ +function load(options = {}) { + const doc = new Document(); + const clock = new Clock(); + const repoMode = options.kind === 'repositories'; + const el = buildPalette(doc, { + workerUrl: '/+static/file-search-worker.js', + treeUrl: repoMode ? null : '/repo/+/HEAD/?format=JSON&paths_only=1', + kind: repoMode ? 'repositories' : null, + }); + if (repoMode) buildRepoList(doc, options.repos || []); + if (options.nonce) { + const s = doc.createElement('script'); + s.setAttribute('nonce', options.nonce); + doc.body.appendChild(s); + doc.currentScript = s; + } + + const workers = []; + const navigations = []; + const opened = []; + const fetches = []; + const storage = new FakeStorage(options.storage); + // A second page load sees whatever the first one left behind. + if (options.storageMap) storage.map = options.storageMap; + + function defaultWorkerFactory() { + const w = { + sent: [], + terminated: 0, + onmessage: null, + onerror: null, + postMessage(m) { + // A real postMessage structured-clones across the thread boundary, so + // the worker never receives the page's own objects. Modelling that + // also keeps recorded messages in this realm, where deepStrictEqual's + // prototype check can pass. + this.sent.push(JSON.parse(JSON.stringify(m))); + }, + terminate() { + this.terminated++; + }, + /** Delivers a message as the real worker would. */ + reply(msg) { + if (this.onmessage) this.onmessage({data: msg}); + }, + fail() { + if (this.onerror) this.onerror({}); + }, + }; + return w; + } + + const factory = options.workerFactory || defaultWorkerFactory; + + const location = {pathname: options.pathname || '/', href: '/'}; + const windowObj = { + localStorage: storage, + listeners: Object.create(null), + addEventListener(type, fn) { + (this.listeners[type] || (this.listeners[type] = [])).push(fn); + }, + open(href, target) { + opened.push({href, target}); + }, + get location() { + return location; + }, + }; + if (options.speculation) { + windowObj.HTMLScriptElement = {supports: (s) => s === 'speculationrules'}; + } + // window.location.href = ... must be observable as a navigation. + Object.defineProperty(location, 'href', { + get: () => location._href || '/', + set: (v) => { + location._href = v; + navigations.push(v); + }, + }); + + const sandbox = { + document: doc, + window: windowObj, + location, + console, + JSON, + Math, + Object, + Array, + String, + Number, + isFinite, + encodeURIComponent, + Date: {now: () => clock.now}, + setTimeout: (fn, ms) => clock.setTimeout(fn, ms), + clearTimeout: (id) => clock.clearTimeout(id), + fetch: (url, init) => { + fetches.push({url, init}); + return Promise.resolve({text: () => Promise.resolve('')}); + }, + }; + if (!options.noWorker) { + sandbox.Worker = function (url) { + const w = factory(url); + workers.push(w); + return w; + }; + } + sandbox.HTMLScriptElement = windowObj.HTMLScriptElement; + + vm.runInNewContext(fs.readFileSync(SRC, 'utf8'), sandbox, {filename: SRC}); + + return { + doc, + clock, + el, + storage, + workers, + navigations, + opened, + fetches, + sandbox, + /** The worker most recently constructed. */ + get worker() { + return workers[workers.length - 1]; + }, + /** Presses a key in the input. */ + key(k, extra) { + return fire(el.input, 'keydown', Object.assign({key: k}, extra)); + }, + /** Presses a key on the document, as a reader not in the palette would. */ + globalKey(k, extra) { + return fire(doc, 'keydown', Object.assign({key: k, target: doc.body}, extra)); + }, + /** Types into the input and lets the finder react. */ + type(text) { + el.input.value = text; + fire(el.input, 'input', {}); + }, + /** The rows currently painted, in display order. */ + visibleRows() { + return el.list.children.filter((li) => !li.hidden); + }, + /** The id named by aria-activedescendant, or null. */ + activeDescendant() { + return el.input.getAttribute('aria-activedescendant'); + }, + status() { + return el.status.textContent; + }, + }; +} + +module.exports = {load, fire, Element, Document, Clock};
diff --git a/jstests/file_search_test.js b/jstests/file_search_test.js new file mode 100644 index 0000000..943c611 --- /dev/null +++ b/jstests/file_search_test.js
@@ -0,0 +1,661 @@ +// Copyright (C) 2026 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Tests for the file finder's UI layer. +// +// file-search.js exports nothing, so these drive it the way a reader does: +// through the document and the events the browser would deliver. See +// fake_dom.js for what the stand-in models and, more importantly, what it +// does not. + +const {test, describe} = require('node:test'); +const assert = require('node:assert'); +const {load} = require('./fake_dom.js'); + +/** The number of rows the palette paints; see LIMIT in file-search.js. */ +const LIMIT = 20; + +/** Opens the palette and brings its worker to the ready state. */ +function opened(options) { + const env = load(options); + env.globalKey('/'); + env.worker.reply({type: 'ready', total: 1234}); + return env; +} + +/** The last message the page sent the worker. */ +function lastSent(env) { + return env.worker.sent[env.worker.sent.length - 1]; +} + +/** Answers the outstanding query with `paths`, echoing its sequence number. */ +function respond(env, paths, opts = {}) { + const msg = lastSent(env); + env.worker.reply({ + type: 'results', + seq: opts.seq !== undefined ? opts.seq : msg.seq, + q: msg.q || '', + total: opts.total !== undefined ? opts.total : paths.length, + exact: opts.exact !== undefined ? opts.exact : true, + recent: !!opts.recent, + items: paths.map((p) => ({path: p, ranges: opts.ranges || []})), + }); +} + +function paths(n, prefix = 'dir/f') { + const out = []; + for (let i = 0; i < n; i++) out.push(`${prefix}${String(i).padStart(3, '0')}.txt`); + return out; +} + +describe('opening', () => { + test('"/" reveals the palette and puts the caret in the box', () => { + const env = load(); + assert.strictEqual(env.el.root.hidden, true); + const ev = env.globalKey('/'); + assert.strictEqual(ev.preventDefaultCount, 1, 'Firefox binds / to Quick Find'); + assert.strictEqual(env.el.root.hidden, false); + assert.strictEqual(env.doc.activeElement, env.el.input); + assert.ok(env.doc.body.classList.contains('FileSearch-open')); + }); + + test('"/" is left alone while the reader is typing somewhere else', () => { + const env = load(); + const box = env.doc.createElement('input'); + env.doc.body.appendChild(box); + box.focus(); + env.globalKey('/'); + assert.strictEqual(env.el.root.hidden, true); + }); + + test('the index is fetched on first open, not on page load', () => { + const env = load(); + assert.strictEqual(env.workers.length, 0, 'a reader who never searches costs nothing'); + env.globalKey('/'); + assert.strictEqual(env.workers.length, 1); + assert.deepStrictEqual(lastSent(env), { + type: 'load', + url: '/repo/+/HEAD/?format=JSON&paths_only=1', + }); + }); + + test('Escape closes and gives focus back', () => { + const env = load(); + const before = env.doc.createElement('button'); + env.doc.body.appendChild(before); + before.focus(); + env.globalKey('/'); + const ev = env.key('Escape'); + assert.strictEqual(ev.preventDefaultCount, 1); + assert.strictEqual(env.el.root.hidden, true); + assert.strictEqual(env.doc.activeElement, before); + }); +}); + +describe('rows', () => { + test('are identified and taken out of the tab order', () => { + // Arrow keys never move focus, so the input has to name the selected row + // for a screen reader; and a listbox option that is a tab stop would let + // Tab walk out of a dialog that calls itself modal. + const env = load(); + const lis = env.el.list.children; + assert.strictEqual(lis.length, LIMIT); + lis.forEach((li, i) => { + assert.strictEqual(li.id, 'file-search-row-' + i); + assert.strictEqual(li.getAttribute('role'), 'option'); + assert.strictEqual(li.children[0].tabIndex, -1); + }); + }); + + test('link to the listing base with separators preserved', () => { + const env = opened(); + env.type('a b'); + respond(env, ['dir with space/a+b.txt']); + const a = env.el.list.children[0].children[0]; + assert.strictEqual(a.href, '/repo/+/HEAD/dir%20with%20space/a%2Bb.txt'); + }); + + test('mark the matched characters and nothing else', () => { + const env = opened(); + env.type('plain'); + respond(env, ['dir/plain.txt'], {ranges: [[4, 5]]}); + const a = env.el.list.children[0].children[0]; + const marks = a.children.filter((c) => c.tagName === 'MARK'); + assert.strictEqual(marks.length, 1); + assert.strictEqual(marks[0].textContent, 'plain'); + assert.strictEqual(a.textContent, 'dir/plain.txt'); + }); +}); + +describe('selection', () => { + test('returns to the best match on every new query', () => { + // Carrying it over meant that once a reader had arrowed at all, every + // later query left them on an arbitrary row -- the row Enter opens. + const env = opened(); + env.type('f'); + respond(env, paths(5)); + env.key('ArrowDown'); + env.key('ArrowDown'); + assert.strictEqual(env.activeDescendant(), 'file-search-row-2'); + + env.type('fo'); + respond(env, paths(5)); + assert.strictEqual(env.activeDescendant(), 'file-search-row-0'); + }); + + test('cannot escape the rows that were painted', () => { + // The display is what the selection moves over. Sizing it from the item + // count instead let a longer list strand the selection past the last row, + // where it highlighted nothing and Enter did nothing. + const env = opened(); + env.type('f'); + respond(env, paths(LIMIT + 5)); + for (let i = 0; i < LIMIT + 10; i++) env.key('ArrowDown'); + assert.strictEqual(env.activeDescendant(), 'file-search-row-' + (LIMIT - 1)); + + env.key('Enter'); + assert.deepStrictEqual(env.navigations, ['/repo/+/HEAD/dir/f019.txt']); + }); + + test('is named for a screen reader, and unnamed when there is nothing', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + assert.strictEqual(env.activeDescendant(), 'file-search-row-0'); + respond(env, []); + assert.strictEqual(env.activeDescendant(), null); + }); + + test('Tab is swallowed so focus cannot leave the modal', () => { + const env = opened(); + const ev = env.key('Tab'); + assert.strictEqual(ev.preventDefaultCount, 1); + }); + + test('PageDown moves by half a screen and stops at the end', () => { + const env = opened(); + env.type('f'); + respond(env, paths(15)); + env.key('PageDown'); + assert.strictEqual(env.activeDescendant(), 'file-search-row-10'); + env.key('PageDown'); + assert.strictEqual(env.activeDescendant(), 'file-search-row-14'); + }); + + test('Ctrl-N and Ctrl-P move like the arrows', () => { + const env = opened(); + env.type('f'); + respond(env, paths(5)); + env.key('n', {ctrlKey: true}); + assert.strictEqual(env.activeDescendant(), 'file-search-row-1'); + env.key('p', {ctrlKey: true}); + assert.strictEqual(env.activeDescendant(), 'file-search-row-0'); + }); + + test('ignores navigation and Enter while an IME composition is active', () => { + const {fire} = require('./fake_dom.js'); + const env = opened(); + env.type('f'); + respond(env, paths(3)); + fire(env.el.input, 'compositionstart', {}); + env.key('ArrowDown'); + env.key('Enter'); + env.key('Escape'); + assert.strictEqual(env.activeDescendant(), 'file-search-row-0'); + assert.strictEqual(env.navigations.length, 0); + assert.strictEqual(env.el.root.hidden, false); + fire(env.el.input, 'compositionend', {}); + }); +}); + +describe('the worker', () => { + test('being refused leaves a palette the reader can still dismiss', () => { + // A policy that forbids workers rejects the constructor synchronously. + // open() has revealed the overlay and not yet focused the input, so + // throwing would leave a dialog that can be neither typed into nor closed. + const env = load({ + workerFactory: () => { + throw new Error('blocked by Content-Security-Policy'); + }, + }); + assert.doesNotThrow(() => env.globalKey('/')); + assert.strictEqual(env.el.root.hidden, false); + assert.strictEqual(env.doc.activeElement, env.el.input, 'the box must be typable'); + assert.strictEqual(env.status(), 'File search is unavailable on this page'); + env.key('Escape'); + assert.strictEqual(env.el.root.hidden, true, 'and Escape must still work'); + }); + + test('is retried when the reader opens the palette again', () => { + let calls = 0; + const env = load({ + workerFactory: () => { + if (++calls === 1) throw new Error('transient'); + return { + sent: [], + postMessage(m) { + this.sent.push(m); + }, + terminate() {}, + onmessage: null, + onerror: null, + }; + }, + }); + env.globalKey('/'); + assert.strictEqual(env.status(), 'File search is unavailable on this page'); + env.key('Escape'); + env.globalKey('/'); + assert.strictEqual(calls, 2, 'a one-off failure must not disable the finder for the page'); + }); + + test('distinguishes failing to load from failing to search', () => { + const env = load(); + env.globalKey('/'); + env.worker.reply({type: 'error', message: 'HTTP 503'}); + assert.strictEqual(env.status(), 'Could not load file index: HTTP 503'); + + const env2 = opened(); + env2.type('x'); + env2.worker.reply({type: 'error', message: 'boom'}); + assert.strictEqual(env2.status(), 'File search failed: boom'); + + const env3 = load(); + env3.globalKey('/'); + env3.worker.fail(); + assert.strictEqual(env3.status(), 'Could not load file index'); + }); + + test('results overtaken by later keystrokes are dropped', () => { + const env = opened(); + env.type('a'); + respond(env, ['dir/first.txt']); + const stale = lastSent(env).seq; + + env.type('ab'); + respond(env, ['dir/overtaken.txt'], {seq: stale}); + const shown = () => env.el.list.children[0].children[0].textContent; + assert.strictEqual(shown(), 'dir/first.txt', 'the stale answer must not paint'); + + respond(env, ['dir/current.txt']); + assert.strictEqual(shown(), 'dir/current.txt'); + }); +}); + +describe('the status line', () => { + test('reports an exact count plainly and a partial one with a plus', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3), {total: 3, exact: true}); + assert.strictEqual(env.status(), '3 matches'); + + respond(env, paths(LIMIT), {total: 40, exact: false}); + assert.strictEqual(env.status(), 'Showing 20 of 40+ matches'); + }); + + test('says so when the exhaustive scan found nothing', () => { + const env = opened(); + env.type('zzz'); + respond(env, []); + assert.strictEqual(env.status(), 'No matching files'); + }); +}); + +describe('what the reader keeps coming back to', () => { + test('an opened file is remembered and offered on an empty box', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + env.key('Enter'); + + const again = opened({storageMap: env.storage.map}); + assert.deepStrictEqual(lastSent(again), { + type: 'recent', + seq: 1, + paths: ['dir/f000.txt'], + }); + }); + + test('a click is remembered the same as Enter', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + const {fire} = require('./fake_dom.js'); + fire(env.el.list, 'click', {target: env.el.list.children[1]}); + assert.match(env.storage.map.get([...env.storage.map.keys()][0]), /f001\.txt/); + }); + + test('scores halve every week, so frequency beats recency', () => { + // s <- s * 2^(-dt / HALF_LIFE) + 1, so an entry untouched for a week is + // worth half of one opened just now. + const env = opened(); + env.type('f'); + respond(env, paths(3)); + env.key('Enter'); // f000, at t0 + + const week = 7 * 24 * 60 * 60 * 1000; + env.clock.advance(week); + env.type('f'); + respond(env, paths(3)); + env.key('ArrowDown'); + env.key('Enter'); // f001, a week later + + const again = load({storageMap: env.storage.map}); + again.globalKey('/'); + again.worker.reply({type: 'ready', total: 3}); + assert.deepStrictEqual( + lastSent(again).paths, + ['dir/f001.txt', 'dir/f000.txt'], + 'f000 has decayed to 0.5, f001 is worth 1', + ); + }); + + test('the store is capped so a long-lived browser cannot grow without bound', () => { + const env = load(); + const key = 'gitiles.file-finder.recent./repo'; + const seeded = []; + for (let i = 0; i < 250; i++) { + seeded.push({p: `dir/old${i}.txt`, s: 1, t: 1700000000000}); + } + env.storage.map.set(key, JSON.stringify(seeded)); + env.globalKey('/'); + env.worker.reply({type: 'ready', total: 3}); + env.type('f'); + respond(env, paths(3)); + env.key('Enter'); + assert.strictEqual(JSON.parse(env.storage.map.get(key)).length, 200); + }); + + test('a storage that refuses to answer is tolerated', () => { + const env = load({storage: {throwOnGet: true, throwOnSet: true}}); + env.globalKey('/'); + env.worker.reply({type: 'ready', total: 3}); + assert.strictEqual(lastSent(env).type, 'query', 'falls through to the ordinary listing'); + env.type('f'); + respond(env, paths(3)); + assert.doesNotThrow(() => env.key('Enter')); + assert.deepStrictEqual(env.navigations, ['/repo/+/HEAD/dir/f000.txt']); + }); + + test('remembered entries are labelled as such, not as matches', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + env.key('Enter'); + + const again = opened({storageMap: env.storage.map}); + respond(again, ['dir/f000.txt'], {recent: true}); + assert.strictEqual(again.status(), 'Recently opened'); + }); + + test('falls back to the ordinary listing when no remembered file exists in this tree', () => { + const env = opened(); + env.type('f'); + respond(env, ['dir/deleted_on_this_branch.txt']); + env.key('Enter'); + + const again = opened({storageMap: env.storage.map}); + assert.strictEqual(lastSent(again).type, 'recent'); + respond(again, [], {recent: true}); + assert.deepStrictEqual(lastSent(again), { + type: 'query', + seq: 2, + q: '', + }); + respond(again, paths(3)); + assert.strictEqual(again.visibleRows().length, 3); + assert.strictEqual(again.status(), '3 matches'); + }); +}); + +describe('warming', () => { + test('the settled selection is warmed once', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + assert.strictEqual(env.fetches.length, 0, 'not before the selection settles'); + env.clock.advance(300); + assert.deepStrictEqual( + env.fetches.map((f) => f.url), + ['/repo/+/HEAD/dir/f000.txt'], + ); + assert.strictEqual(env.fetches[0].init.priority, 'low'); + }); + + test('typing does not fire one request per keystroke', () => { + const env = opened(); + for (const q of ['f', 'f0', 'f00', 'f000']) { + env.type(q); + respond(env, paths(3)); + env.clock.advance(150); + } + env.clock.advance(300); + assert.strictEqual(env.fetches.length, 1); + }); + + test('closing leaves no standing speculation behind', () => { + const env = opened(); + env.type('f'); + respond(env, paths(3)); + env.key('Escape'); + env.clock.advance(500); + assert.strictEqual(env.fetches.length, 0); + }); + + test('a worker reply arriving after close does not warm', () => { + const env = opened(); + env.type('f'); + env.key('Escape'); + respond(env, paths(3)); + env.clock.advance(500); + assert.strictEqual(env.fetches.length, 0); + }); + + test('installs a single speculation rule and downgrades to fetch on CSP violation', () => { + const {fire} = require('./fake_dom.js'); + const env = opened({speculation: true, nonce: 'csp-123'}); + env.type('f'); + respond(env, paths(3)); + env.clock.advance(300); + + const rule = () => env.doc.getElementById('file-search-speculation'); + assert.ok(rule(), 'speculation rule script installed'); + assert.strictEqual(rule().type, 'speculationrules'); + assert.strictEqual(rule().getAttribute('nonce'), 'csp-123'); + assert.deepStrictEqual(JSON.parse(rule().textContent), { + prefetch: [{source: 'list', urls: ['/repo/+/HEAD/dir/f000.txt']}], + }); + assert.strictEqual(env.fetches.length, 0); + + // Moving the selection replaces the rule rather than accumulating rules. + env.key('ArrowDown'); + env.clock.advance(300); + assert.strictEqual( + env.doc.head.querySelectorAll('script').length, + 1, + 'only one speculationrules script is live at a time', + ); + assert.deepStrictEqual(JSON.parse(rule().textContent), { + prefetch: [{source: 'list', urls: ['/repo/+/HEAD/dir/f001.txt']}], + }); + + // A report-only CSP violation must not disable speculation rules. + fire(env.doc, 'securitypolicyviolation', { + violatedDirective: 'script-src-elem', + disposition: 'report', + }); + assert.ok(rule()); + + // An enforced script-src violation removes the rule and falls back to fetch. + fire(env.doc, 'securitypolicyviolation', { + violatedDirective: 'script-src-elem', + disposition: 'enforce', + }); + assert.strictEqual(rule(), null); + env.clock.advance(300); + assert.deepStrictEqual( + env.fetches.map((f) => f.url), + ['/repo/+/HEAD/dir/f001.txt'], + ); + }); +}); + +describe('dismissal', () => { + test('the backdrop dismisses, the modal itself does not', () => { + const {fire} = require('./fake_dom.js'); + const env = opened(); + fire(env.el.root, 'mousedown', {target: env.el.input}); + assert.strictEqual(env.el.root.hidden, false); + fire(env.el.root, 'mousedown', {target: env.el.backdrop}); + assert.strictEqual(env.el.root.hidden, true); + }); + + test('Escape and Tab still work if focus leaves the input inside the modal', () => { + const env = opened(); + env.el.status.focus(); + const tab = env.globalKey('Tab'); + assert.strictEqual(tab.preventDefaultCount, 1); + assert.strictEqual(env.doc.activeElement, env.el.input); + + env.el.status.focus(); + const esc = env.globalKey('Escape'); + assert.strictEqual(esc.preventDefaultCount, 1); + assert.strictEqual(env.el.root.hidden, true); + }); + + test('leaving the page closes it, so the back/forward cache is clean', () => { + const {fire} = require('./fake_dom.js'); + const env = opened(); + for (const fn of env.sandbox.window.listeners['pagehide'] || []) fn({}); + assert.strictEqual(env.el.root.hidden, true); + }); +}); + +describe('the host index', () => { + const REPOS = [ + { + name: 'platform/frameworks/base', + href: '/b/platform/frameworks/base/', + desc: 'The framework', + }, + {name: 'platform/build', href: '/b/platform/build/'}, + // Repositories may legitimately be named after Object.prototype properties, + // both with and without descriptions, so both maps must have no prototype. + {name: 'constructor', href: '/b/constructor/', desc: 'Not a function'}, + {name: 'toString', href: '/b/toString/'}, + ]; + + function hostIndex(extra = {}) { + const env = load(Object.assign({kind: 'repositories', repos: REPOS}, extra)); + env.globalKey('/'); + env.worker.reply({type: 'ready', total: REPOS.length}); + return env; + } + + test('is read out of the page rather than fetched again', () => { + // The page already lists every repository, and that response carries no + // revision, so it is served no-store and would be re-fetched every load. + const env = hostIndex(); + assert.deepStrictEqual(env.worker.sent[0], { + type: 'load', + names: REPOS.map((r) => r.name), + }); + assert.strictEqual(env.fetches.length, 0); + }); + + test('links where the page links, and shows the description beside it', () => { + const env = hostIndex(); + env.type('base'); + respond(env, ['platform/frameworks/base']); + const a = env.el.list.children[0].children[0]; + assert.strictEqual(a.href, '/b/platform/frameworks/base/'); + const desc = a.children.find((c) => c.classList.contains('FileSearch-rowDesc')); + assert.strictEqual(desc.textContent, 'The framework'); + assert.strictEqual(a.textContent, 'platform/frameworks/base The framework'); + }); + + test('handles a repository named after an Object property', () => { + const env = hostIndex(); + env.type('cons'); + respond(env, ['constructor', 'toString']); + const a0 = env.el.list.children[0].children[0]; + assert.strictEqual(a0.href, '/b/constructor/'); + const a1 = env.el.list.children[1].children[0]; + assert.strictEqual(a1.href, '/b/toString/'); + assert.strictEqual( + a1.children.find((c) => c.classList.contains('FileSearch-rowDesc')), + undefined, + 'an unpopulated description must not resolve Object.prototype.toString', + ); + }); + + test('navigates on Enter and remembers the repository under the host index key', () => { + const env = hostIndex(); + env.type('base'); + respond(env, ['platform/frameworks/base']); + env.key('Enter'); + assert.deepStrictEqual(env.navigations, ['/b/platform/frameworks/base/']); + + const again = hostIndex({storageMap: env.storage.map}); + assert.deepStrictEqual(lastSent(again), { + type: 'recent', + seq: 1, + paths: ['platform/frameworks/base'], + }); + }); + + test('keeps one history for an index reached with or without a trailing slash', () => { + // Gitiles serves /b and /b/ as the same host index without redirecting. + const env = hostIndex({pathname: '/b/'}); + env.type('base'); + respond(env, ['platform/frameworks/base']); + env.key('Enter'); + + const again = hostIndex({pathname: '/b', storageMap: env.storage.map}); + assert.deepStrictEqual(lastSent(again), { + type: 'recent', + seq: 1, + paths: ['platform/frameworks/base'], + }); + }); + + test('never warms a repository page', () => { + // A repository index names no revision, so it is served no-store: a + // speculative fetch would be discarded and the request wasted. + const env = hostIndex(); + env.type('base'); + respond(env, ['platform/frameworks/base']); + env.clock.advance(1000); + assert.strictEqual(env.fetches.length, 0); + }); + + test('offers no palette at all when the index is empty', () => { + // An empty palette would be worse than none, and the trigger button must + // be hidden so the header does not offer a dead control. + const env = load({kind: 'repositories', repos: []}); + assert.strictEqual(env.el.trigger.hidden, true); + env.globalKey('/'); + assert.strictEqual(env.el.root.hidden, true); + assert.strictEqual(env.workers.length, 0); + }); + + test('ignores a duplicate listing of the same repository', () => { + const env = load({ + kind: 'repositories', + repos: [REPOS[1], REPOS[1], REPOS[0]], + }); + env.globalKey('/'); + assert.deepStrictEqual(lastSent(env).names, ['platform/build', 'platform/frameworks/base']); + }); +});
diff --git a/jstests/file_search_worker_test.js b/jstests/file_search_worker_test.js new file mode 100644 index 0000000..40100a1 --- /dev/null +++ b/jstests/file_search_worker_test.js
@@ -0,0 +1,366 @@ +// Copyright (C) 2026 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Tests for the file finder's search worker. +// +// The worker is a script, not a module: it exports nothing and assigns +// `self.onmessage`. That message protocol is the seam these tests use, so the +// code under test needs no modification and is exercised through exactly the +// surface a browser drives it through. + +const {test, describe} = require('node:test'); +const assert = require('node:assert'); +const fs = require('node:fs'); +const vm = require('node:vm'); + +const SRC = 'resources/com/google/gitiles/static/file-search-worker.js'; + +/** The worker's display cap; see LIMIT in the source. */ +const LIMIT = 20; + +/** + * Evaluates the worker in a fresh global containing only what a real + * DedicatedWorkerGlobalScope would offer it, and returns a handle for talking + * to it. + */ +function loadWorker(fetchImpl) { + const outbox = []; + const sandbox = { + TextEncoder, + TextDecoder, + fetch: fetchImpl, + self: { + onmessage: null, + // A real postMessage structured-clones across the worker boundary, so + // the main thread never sees the worker's own objects. Modelling that is + // both faithful and necessary: values built inside a vm context carry + // that context's prototypes, and assert.deepStrictEqual compares + // prototypes. + postMessage: (m) => outbox.push(JSON.parse(JSON.stringify(m))), + }, + }; + vm.runInNewContext(fs.readFileSync(SRC, 'utf8'), sandbox, {filename: SRC}); + return { + outbox, + /** Delivers one message and returns the reply, or undefined if silent. */ + async send(msg) { + const before = outbox.length; + await sandbox.self.onmessage({data: msg}); + return outbox.length > before ? outbox[outbox.length - 1] : undefined; + }, + }; +} + +/** Serves `paths` as the listing endpoint would, guard prefix and all. */ +function serving(paths) { + return async () => ({ + ok: true, + status: 200, + text: async () => ")]}'\n" + JSON.stringify({paths}), + }); +} + +/** + * Builds a worker holding an index over `paths`. + * + * The paths must be in byte order, as a recursive git tree listing is: the + * index binary searches them. + */ +async function indexed(paths) { + const w = loadWorker(serving(paths)); + const r = await w.send({type: 'load', url: '/+/HEAD/?format=JSON'}); + assert.strictEqual(r.type, 'ready', `load failed: ${JSON.stringify(r)}`); + assert.strictEqual(r.total, paths.length); + return w; +} + +/** + * Builds a worker from a listing the page already had, in any order. + * + * No fetch is reachable here, so a worker that tried to make one would fail + * rather than quietly succeed. + */ +async function fromNames(names) { + const w = loadWorker(async () => { + throw new Error('a supplied listing must not be fetched'); + }); + const r = await w.send({type: 'load', names}); + assert.strictEqual(r.type, 'ready', `load failed: ${JSON.stringify(r)}`); + assert.strictEqual(r.total, names.length); + return w; +} + +/** Types a query one keystroke at a time, the way a reader produces it. */ +async function type(w, q) { + let last; + for (let k = 1; k <= q.length; k++) { + last = await w.send({type: 'query', seq: k, q: q.slice(0, k)}); + } + return last; +} + +const CORPUS = [ + 'base/base64.h', + 'base/logging.h', + 'chrome/test/data/dromaeo/tests/dromaeo-string-base64.html', + 'net/base/base64.h', + 'third_party/blink/web_tests/tables/bug3166-4.html', +]; + +describe('loading', () => { + test('strips the anti-XSSI prefix from the listing', async () => { + const w = loadWorker(serving(CORPUS)); + const r = await w.send({type: 'load', url: '/+/HEAD/?format=JSON'}); + assert.deepStrictEqual(r, {type: 'ready', total: CORPUS.length}); + }); + + test('reports a failed fetch instead of throwing', async () => { + const w = loadWorker(async () => ({ok: false, status: 503})); + const r = await w.send({type: 'load', url: '/+/HEAD/?format=JSON'}); + assert.strictEqual(r.type, 'error'); + assert.match(r.message, /503/); + }); + + test('ignores a query that arrives before the index', async () => { + const w = loadWorker(serving(CORPUS)); + assert.strictEqual(await w.send({type: 'query', seq: 1, q: 'base'}), undefined); + assert.strictEqual(await w.send({type: 'recent', seq: 2, paths: []}), undefined); + }); +}); + +describe('a listing the page already had', () => { + test('is used instead of fetching one', async () => { + const w = await fromNames(CORPUS.slice()); + const r = await type(w, 'logging.h'); + assert.strictEqual(r.items[0].path, 'base/logging.h'); + }); + + test('is sorted, whatever order it arrives in', async () => { + // The index binary searches its paths, so an unsorted build silently + // fails to find paths that are present. + const w = await fromNames(CORPUS.slice().reverse()); + const r = await w.send({type: 'recent', seq: 1, paths: CORPUS.slice()}); + assert.deepStrictEqual(r.items.map((i) => i.path), CORPUS); + }); + + test('is sorted by UTF-8 bytes, not by UTF-16 code units', async () => { + // The two orders disagree above the basic plane. Array#sort would put + // U+10000 first, because its leading surrogate is 0xD800; the UTF-8 + // encodings run the other way, EF BF BD before F0 90 80 80. Sorting the + // wrong way makes the byte-wise binary search miss. + const names = ['dir/\u{10000}.txt', 'dir/\uFFFD.txt']; + const w = await fromNames(names.slice()); + const r = await w.send({type: 'recent', seq: 1, paths: names.slice()}); + assert.strictEqual(r.items.length, 2); + }); +}); + +describe('ranking', () => { + test('a basename carrying the whole query outranks an incidental match', async () => { + // The directory "base" can consume "base" out of the query, which would + // score base/base64.h as a directory-assisted match and sink it below + // files whose directories contributed nothing. + const w = await indexed(CORPUS); + const r = await type(w, 'base64.h'); + assert.deepStrictEqual(r.items.slice(0, 2).map((i) => i.path), [ + 'base/base64.h', + 'net/base/base64.h', + ]); + }); + + test('a basename carrying the post-slash query is not robbed by a deeper directory', async () => { + const w = await indexed([ + 'java/com/google/gitiles/GitilesView.java', + 'java/com/google/gitiles/ViewFilter.java', + 'net/base/64.h', + 'net/base/base64.h', + ]); + const r1 = await type(w, 'java/gitilesview'); + assert.deepStrictEqual( + r1.items.map((i) => i.path), + [ + 'java/com/google/gitiles/GitilesView.java', + 'java/com/google/gitiles/ViewFilter.java', + ], + ); + + const r2 = await type(w, 'net/base64.h'); + assert.deepStrictEqual( + r2.items.map((i) => i.path), + ['net/base/base64.h', 'net/base/64.h'], + ); + assert.deepStrictEqual(r2.items[0].ranges, [ + [0, 4], + [9, 8], + ]); + }); + + test('a shallower path breaks a tie', async () => { + const w = await indexed(CORPUS); + const r = await type(w, 'logging.h'); + assert.strictEqual(r.items[0].path, 'base/logging.h'); + + // Full staticRank precision is preserved in subsequence channels, so a + // depth-1 path beats a depth-2 path even when staticRank >> 4 would tie. + const w2 = await indexed(['a/b/logging_util.h', 'content/logging_util.h']); + const r2 = await type(w2, 'lutil'); + assert.deepStrictEqual( + r2.items.map((i) => i.path), + ['content/logging_util.h', 'a/b/logging_util.h'], + ); + }); + + test('a basename prefix outranks a non-prefix even when fewer than LIMIT', async () => { + // When channel B has fewer than LIMIT matches, channel C or D fills the + // remaining rows; B's prefix matches must stay ahead of non-prefix matches + // with higher camelCase or separator bonuses. + const w = await indexed([ + 'dir/abcdef_long_suffix_to_penalize.txt', + 'dir/x_ab_cd.txt', + ]); + const r = await type(w, 'abcd'); + assert.deepStrictEqual( + r.items.map((i) => i.path), + ['dir/abcdef_long_suffix_to_penalize.txt', 'dir/x_ab_cd.txt'], + ); + }); + + test('weak basename matches with negative scores still return rows', async () => { + // A single non-boundary match inside a long basename has a negative + // length-penalised score, which must still be offered rather than dropped. + const paths = []; + for (let i = 0; i < LIMIT + 5; i++) { + paths.push(`dir/f${String(i).padStart(2, '0')}x${'a'.repeat(50)}.txt`); + } + const w = await indexed(paths); + const r = await type(w, 'x'); + assert.strictEqual(r.items.length, LIMIT); + }); + + test('echoes the sequence number so the UI can discard stale replies', async () => { + const w = await indexed(CORPUS); + const r = await w.send({type: 'query', seq: 7, q: 'base64'}); + assert.strictEqual(r.seq, 7); + assert.strictEqual(r.q, 'base64'); + }); +}); + +describe('empty query', () => { + test('offers a capped, exact sample of the tree', async () => { + const paths = []; + for (let i = 0; i < 30; i++) paths.push(`dir/f${String(i).padStart(3, '0')}.txt`); + const w = await indexed(paths); + const r = await w.send({type: 'query', seq: 1, q: ''}); + assert.strictEqual(r.total, paths.length); + assert.strictEqual(r.exact, true); + assert.strictEqual(r.items.length, LIMIT); + assert.deepStrictEqual(r.items[0].ranges, []); + }); +}); + +describe('path-prefix matches', () => { + test('are promoted and marked across the whole query', async () => { + const w = await indexed(CORPUS); + const r = await type(w, 'base/base64'); + assert.strictEqual(r.items[0].path, 'base/base64.h'); + assert.deepStrictEqual(r.items[0].ranges, [[0, 'base/base64'.length]]); + }); + + test('report an inexact total once they fill the display', async () => { + // The count is a lower bound: other paths may match without starting with + // the query, so the display has to say "+". + const paths = []; + for (let i = 0; i < LIMIT + 5; i++) { + paths.push(`pkg/f${String(i).padStart(3, '0')}.txt`); + } + const w = await indexed(paths); + const r = await type(w, 'pkg/'); + assert.strictEqual(r.total, paths.length); + assert.strictEqual(r.exact, false); + assert.strictEqual(r.items.length, LIMIT); + }); +}); + +describe('highlight ranges', () => { + test('are omitted for non-ASCII paths', async () => { + // Ranges are UTF-8 byte offsets and the UI applies them as UTF-16 string + // indices. They agree only for ASCII; elsewhere, no marks beat wrong ones. + const paths = ['dir/plain.txt', 'dir/\u2605\u661f\u2605.txt']; + + const w = await indexed(paths); + const ascii = await type(w, 'plain'); + assert.deepStrictEqual(ascii.items[0].ranges, [[4, 5]]); + + const w2 = await indexed(paths); + const star = await type(w2, '\u2605\u661f\u2605'); + assert.strictEqual(star.items[0].path, 'dir/\u2605\u661f\u2605.txt'); + assert.deepStrictEqual(star.items[0].ranges, []); + }); + + test('marks directory characters consumed by the full-path channel', async () => { + const w = await indexed(['base/task/thread.h', 'other/file.h']); + const r = await type(w, 'bt/thread'); + assert.strictEqual(r.items[0].path, 'base/task/thread.h'); + assert.deepStrictEqual(r.items[0].ranges, [ + [0, 1], + [5, 1], + [9, 7], + ]); + }); + + test('preserves a leading U+FEFF in a path name', async () => { + const w = await indexed(['\ufeffbom.txt']); + const r = await type(w, 'bom'); + assert.strictEqual(r.items[0].path, '\ufeffbom.txt'); + }); +}); + +describe('remembered files', () => { + test('are cut to the number of rows the UI paints', async () => { + // Otherwise a reader could arrow past the last painted row into a + // selection that highlighted nothing and did nothing on Enter. + const paths = []; + for (let i = 0; i < 40; i++) paths.push(`dir/f${String(i).padStart(3, '0')}.txt`); + const w = await indexed(paths); + const r = await w.send({type: 'recent', seq: 1, paths: paths.slice()}); + assert.strictEqual(r.items.length, LIMIT); + assert.strictEqual(r.recent, true); + assert.strictEqual(r.q, ''); + }); + + test('drop paths that no longer exist at this revision', async () => { + const w = await indexed(['dir/kept.txt']); + const r = await w.send({ + type: 'recent', + seq: 1, + paths: ['dir/kept.txt', 'dir/deleted.txt'], + }); + assert.deepStrictEqual(r.items.map((i) => i.path), ['dir/kept.txt']); + }); + + test('keep the caller\'s order, since the scores live in the UI', async () => { + const paths = ['dir/a.txt', 'dir/b.txt', 'dir/c.txt']; + const w = await indexed(paths); + const r = await w.send({ + type: 'recent', + seq: 1, + paths: ['dir/c.txt', 'dir/a.txt', 'dir/b.txt'], + }); + assert.deepStrictEqual(r.items.map((i) => i.path), [ + 'dir/c.txt', + 'dir/a.txt', + 'dir/b.txt', + ]); + }); +});
diff --git a/resources/com/google/gitiles/static/base.css b/resources/com/google/gitiles/static/base.css index 8c21311..3116bb2 100644 --- a/resources/com/google/gitiles/static/base.css +++ b/resources/com/google/gitiles/static/base.css
@@ -766,3 +766,109 @@ .Diff-change { color: var(--diff-change); } + +/* File finder overlay. Themed entirely through the custom properties above, so + it follows the light/dark toggle without a second set of rules. */ +.FileSearch-trigger { + cursor: pointer; + background: none; + border: none; + font: inherit; + color: var(--toggle-btn-color); +} +.FileSearch-trigger:hover { + color: var(--toggle-btn-hover-color); + background: var(--toggle-btn-hover-bg); +} +.FileSearch-triggerKey { + border: 1px solid var(--toggle-btn-border); + border-radius: 3px; + padding: 0 4px; + margin-right: 4px; + font-family: monospace; +} +.FileSearch[hidden] { + display: none; +} +.FileSearch { + position: fixed; + inset: 0; + z-index: 100; +} +.FileSearch-backdrop { + position: absolute; + inset: 0; + background: rgba(0, 0, 0, 0.45); +} +.FileSearch-modal { + position: relative; + margin: 10vh auto 0; + max-width: 44rem; + width: 90%; + max-height: 70vh; + display: flex; + flex-direction: column; + background: var(--bg-color); + color: var(--text-color); + border: 1px solid var(--border-subtle-color); + border-radius: 6px; + box-shadow: 0 8px 32px rgba(0, 0, 0, 0.35); + overflow: hidden; +} +.FileSearch-input { + border: none; + border-bottom: 1px solid var(--border-color); + background: var(--bg-color); + color: var(--text-color); + font-family: monospace; + font-size: 15px; + padding: 12px 14px; + outline: none; + width: 100%; + box-sizing: border-box; +} +.FileSearch-status { + color: var(--muted-text-color); + font-size: 12px; + padding: 4px 14px; + border-bottom: 1px solid var(--border-color); + min-height: 1em; +} +.FileSearch-results { + list-style: none; + margin: 0; + padding: 0; + overflow-y: auto; +} +.FileSearch-row[hidden] { + display: none; +} +.FileSearch-row--selected { + background: var(--hover-bg); +} +.FileSearch-link { + display: block; + padding: 5px 14px; + font-family: monospace; + font-size: 13px; + color: var(--text-color); + text-decoration: none; + white-space: nowrap; + overflow: hidden; + text-overflow: ellipsis; +} +.FileSearch-link mark { + background: none; + color: var(--link-color); + font-weight: bold; +} +/* Secondary text on a result row. The row already clips with an ellipsis and + the name is painted first, so a long description truncates rather than + pushing the name out of view. */ +.FileSearch-rowDesc { + color: var(--muted-text-color); + margin-left: 1.5em; +} +body.FileSearch-open { + overflow: hidden; +}
diff --git a/resources/com/google/gitiles/static/file-search-worker.js b/resources/com/google/gitiles/static/file-search-worker.js new file mode 100644 index 0000000..1b0809d --- /dev/null +++ b/resources/com/google/gitiles/static/file-search-worker.js
@@ -0,0 +1,1109 @@ +// Copyright (C) 2026 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +/** + * File finder search engine. Runs in a Worker so that no amount of index work + * can drop a frame on the main thread. + * + * Protocol: + * in {type: 'load', url | names} -> out {type: 'ready', total} + * | out {type: 'error', message} + * in {type: 'query', seq, q} -> out {type: 'results', seq, q, total, + * exact, items} + * + * `items` is ranked and cut to the display limit. The display is limited; the + * search never is. If a path exists and matches, either it is shown or a + * strictly better-ranked path took its place. + * + * `total` counts the matches in the tier that produced `items` (see `search`). + * When a cheap tier already fills the display, the expensive tier is never run, + * so `total` is then a lower bound on all matching paths and `exact` is false. + * Making it exact would cost a full-corpus scan on every keystroke to refine a + * number nobody navigates by. + * + * The index is deliberately string-free. Paths live as bytes in two flat + * buffers (directories, basenames) with Int32Array offsets, so the hot loops + * walk contiguous memory and the collector never sees half a million objects. + * JS strings are materialised only for the rows actually displayed. + */ +'use strict'; + +/** Rows the UI shows. Ranking decides which; the scan still covers everything. */ +const LIMIT = 20; + +// Character classes for the 32-bit membership bitset, used as a reject filter. +// Case folded, with the separators that matter for path matching given their +// own bits. Bytes >= 0x80 all share bucket 31. +const CLS = new Uint8Array(256).fill(31); +for (let c = 0x61; c <= 0x7a; c++) CLS[c] = c - 0x61; // a-z +for (let c = 0x41; c <= 0x5a; c++) CLS[c] = c - 0x41; // A-Z, folded +for (let c = 0x30; c <= 0x39; c++) CLS[c] = 26; // 0-9 share one bit +CLS[0x2e] = 27; // . +CLS[0x5f] = 28; // _ +CLS[0x2d] = 29; // - +CLS[0x2f] = 30; // / + +/** ASCII lowercase fold, applied per byte during comparison. */ +const LOW = new Uint8Array(256); +for (let c = 0; c < 256; c++) LOW[c] = c >= 0x41 && c <= 0x5a ? c + 0x20 : c; + +/** Bytes that begin a new word for scoring purposes. */ +const SEP = new Uint8Array(256); +SEP[0x2e] = 1; +SEP[0x5f] = 1; +SEP[0x2d] = 1; +SEP[0x2f] = 1; +SEP[0x20] = 1; + +const SLASH = 0x2f; + +/** Stand-in for "no query", so an empty box allocates nothing. */ +const EMPTY = new Uint8Array(0); + +/** + * Shared UTF-8 encoder. It holds no state between calls -- `encode` returns a + * fresh array, `encodeInto` writes into a caller-supplied one -- and a worker + * is single-threaded, so one instance serves every caller. `setQuery` runs on + * every keystroke, which is where building one per call would otherwise show + * up. + */ +const ENC = new TextEncoder(); + +function isUpper(b) { + return b >= 0x41 && b <= 0x5a; +} + +function isLower(b) { + return b >= 0x61 && b <= 0x7a; +} + +function maskOf(buf, s, e) { + let m = 0; + for (let i = s; i < e; i++) m |= 1 << CLS[buf[i]]; + return m; +} + +function grow(buf, need) { + const next = new Uint8Array(Math.max(need, buf.length * 2)); + next.set(buf); + return next; +} + +/** @type {?Index} */ +let index = null; + +/** + * Flat, string-free index over every path in a tree. + * + * Directories are stored once per run rather than once per file. The server + * emits paths in tree order, which is byte-lexicographic, so files sharing a + * directory are adjacent and the runs fall out of one pass. On chromium/src + * this collapses 506,237 paths into 46,286 directories, which is the reduction + * that makes the full-path channel affordable. + */ +class Index { + constructor(paths) { + const n = paths.length; + + let totalLen = 0; + for (let i = 0; i < n; i++) totalLen += paths[i].length; + // UTF-8 can expand relative to UTF-16 length; grow on demand rather than + // reserving three bytes per character for a corpus that is nearly all + // ASCII. + let baseBuf = new Uint8Array(totalLen + 64); + let dirBuf = new Uint8Array(totalLen + 64); + + const baseOff = new Int32Array(n + 1); + const dirId = new Int32Array(n); + const dirOffTmp = new Int32Array(n + 1); + + let bp = 0; + let dp = 0; + let nd = 0; + let prevDir = null; + + for (let i = 0; i < n; i++) { + const p = paths[i]; + const slash = p.lastIndexOf('/'); + const dir = slash < 0 ? '' : p.substring(0, slash); + const base = slash < 0 ? p : p.substring(slash + 1); + + if (prevDir === null || dir !== prevDir) { + if (dp + dir.length * 3 > dirBuf.length) { + dirBuf = grow(dirBuf, dp + dir.length * 3); + } + dirOffTmp[nd] = dp; + dp += ENC.encodeInto(dir, dirBuf.subarray(dp)).written; + nd++; + prevDir = dir; + } + dirId[i] = nd - 1; + + if (bp + base.length * 3 > baseBuf.length) { + baseBuf = grow(baseBuf, bp + base.length * 3); + } + baseOff[i] = bp; + bp += ENC.encodeInto(base, baseBuf.subarray(bp)).written; + } + baseOff[n] = bp; + dirOffTmp[nd] = dp; + + // Both byte buffers were sized for the whole path text, since UTF-8 length + // is not known until the encode. Trim to what was written: baseBuf holds + // only basenames and dirBuf only the interned directories, so most of the + // reservation is empty. On chromium/src this is the difference between an + // 87 MB index and a 28 MB one. Same reason dirOff is trimmed below. + baseBuf = baseBuf.slice(0, bp); + dirBuf = dirBuf.slice(0, dp); + + this.n = n; + this.d = nd; + this.baseBuf = baseBuf; + this.baseOff = baseOff; + this.dirBuf = dirBuf; + this.dirOff = dirOffTmp.slice(0, nd + 1); + this.dirId = dirId; + + this.baseMask = new Int32Array(n); + for (let i = 0; i < n; i++) { + this.baseMask[i] = maskOf(baseBuf, baseOff[i], baseOff[i + 1]); + } + + // Files are contiguous within a directory run, so a run is an index range. + // Knowing it lets the full-path channel accept a whole directory at once + // when the directory alone already satisfies the query. + this.dirEnd = new Int32Array(nd); + for (let i = 0; i < n; i++) { + this.dirEnd[dirId[i]] = i + 1; + } + + // Byte-length of the prefix each directory shares with its predecessor. + // Paths arrive sorted, so adjacent directory runs such as .../core/html + // and .../core/svg usually differ only in their tails; the greedy query + // match over the shared head is identical and can be resumed rather than + // recomputed. This is what makes the per-directory pass cheap. + // + // Note the run list itself is not sorted and may repeat: a/x, a/b/y, a/z + // yields runs a, a/b, a. Nothing here relies on ordering, only on this + // being the literal shared prefix of two adjacent entries, so repeats are + // harmless (they simply produce a large lcp and no work at all). + this.dirLcp = new Int32Array(nd); + let maxDirLen = 0; + for (let d = 0; d < nd; d++) { + const s = this.dirOff[d]; + const e = this.dirOff[d + 1]; + if (e - s > maxDirLen) maxDirLen = e - s; + if (d === 0) continue; + const ps = this.dirOff[d - 1]; + const limit = Math.min(s - ps, e - s); + let l = 0; + while (l < limit && dirBuf[ps + l] === dirBuf[s + l]) l++; + this.dirLcp[d] = l; + } + + /** Greedy match state at each byte offset of the directory being scanned. */ + this.kAt = new Int32Array(maxDirLen + 1); + /** Per-directory query consumption, reused across keystrokes. */ + this.dmScratch = new Int32Array(nd); + + // Static rank: shallower and shorter wins. Breaks ties between equally + // good matches, and makes the prefix channel's top-K an integer compare. + this.staticRank = new Int32Array(n); + for (let i = 0; i < n; i++) { + const d = dirId[i]; + const ds = this.dirOff[d]; + const de = this.dirOff[d + 1]; + let depth = de > ds ? 1 : 0; + for (let j = ds; j < de; j++) { + if (dirBuf[j] === SLASH) depth++; + } + this.staticRank[i] = -(de - ds + (baseOff[i + 1] - baseOff[i]) + depth * 12); + } + + this.byBase = buildBasenameOrder(this); + this.decoder = new TextDecoder('utf-8', {ignoreBOM: true}); + this.reset(); + } + + reset() { + /** Query as lowercase UTF-8 bytes. */ + this.q = []; + /** + * The same query, exactly as typed. The index is ordered by raw bytes, so + * the literal prefix range has to be searched for in those terms, not in + * folded ones. + */ + this.qRaw = EMPTY; + this.qmask = 0; + // cand[t] holds files whose basename contains the first t query bytes as a + // subsequence. cand[0] is null, meaning "everything". + this.cand = [null]; + // dcand[t] is the same for the full path, but populated lazily: only query + // lengths that actually reached channel D have an entry. + this.dcand = [null]; + this.scratch = new Int32Array(this.n); + } + + cmpPrefix(i, q) { + let x = this.baseOff[i]; + const xe = this.baseOff[i + 1]; + const buf = this.baseBuf; + for (let k = 0; k < q.length; k++) { + if (x >= xe) return -1; + const d = LOW[buf[x++]] - q[k]; + if (d !== 0) return d < 0 ? -1 : 1; + } + return 0; + } + + /** Half-open range of `byBase` whose basenames start with `q`. */ + prefixRange(q) { + let lo = 0; + let hi = this.n; + while (lo < hi) { + const m = (lo + hi) >> 1; + if (this.cmpPrefix(this.byBase[m], q) < 0) lo = m + 1; + else hi = m; + } + const start = lo; + hi = this.n; + while (lo < hi) { + const m = (lo + hi) >> 1; + if (this.cmpPrefix(this.byBase[m], q) <= 0) lo = m + 1; + else hi = m; + } + return [start, lo]; + } + + /** True if `q[from..]` is a subsequence of basename `i`. */ + baseMatchesFrom(i, from) { + const q = this.q; + const ql = q.length; + if (from >= ql) return true; + const buf = this.baseBuf; + const e = this.baseOff[i + 1]; + let k = from; + for (let j = this.baseOff[i]; j < e; j++) { + if (LOW[buf[j]] === q[k] && ++k === ql) return true; + } + return false; + } + + /** + * Advance the channel-C candidate stack by one byte. + * + * Subsequence matching is monotone under query extension, so this only ever + * examines survivors of the previous keystroke; backspace is a pop. + */ + narrow() { + const prev = this.cand[this.cand.length - 1]; + const out = this.scratch; + const mask = this.qmask; + const baseMask = this.baseMask; + let n = 0; + if (prev === null) { + for (let i = 0; i < this.n; i++) { + if ((mask & ~baseMask[i]) !== 0) continue; + if (this.baseMatchesFrom(i, 0)) out[n++] = i; + } + } else { + for (let x = 0; x < prev.length; x++) { + const i = prev[x]; + if ((mask & ~baseMask[i]) !== 0) continue; + if (this.baseMatchesFrom(i, 0)) out[n++] = i; + } + } + this.cand.push(out.slice(0, n)); + } + + /** + * Sets the query, reusing whatever prefix of the candidate stack still + * applies. Typing extends it; backspacing pops it. + * + * The query is compared as UTF-8 bytes. For non-ASCII input a byte-level + * subsequence is a superset of a character-level one, so this can admit an + * extra row but can never hide a matching path. + */ + setQuery(text) { + const next = ENC.encode(text); + this.qRaw = next; + let keep = 0; + while (keep < next.length && keep < this.q.length && LOW[next[keep]] === this.q[keep]) { + keep++; + } + while (this.q.length > keep) { + this.q.pop(); + this.cand.pop(); + } + // Entries deeper than the surviving prefix describe a query that is no + // longer being asked. + if (this.dcand.length > keep + 1) { + this.dcand.length = keep + 1; + } + this.qmask = 0; + for (const c of this.q) this.qmask |= 1 << CLS[c]; + for (let k = keep; k < next.length; k++) { + const c = LOW[next[k]]; + this.q.push(c); + this.qmask |= 1 << CLS[c]; + this.narrow(); + } + } + + /** Byte length of the directory prefix, including its trailing slash. */ + shiftOf(i) { + const d = this.dirId[i]; + const len = this.dirOff[d + 1] - this.dirOff[d]; + return len === 0 ? 0 : len + 1; + } + + /** + * Byte length of the whole path. + * + * Equal to the length of the string {@link pathOf} returns exactly when the + * path is ASCII, which is what makes the byte offsets recorded during + * matching usable as indices into that string. + */ + pathByteLen(i) { + const d = this.dirId[i]; + const dirLen = this.dirOff[d + 1] - this.dirOff[d]; + const baseLen = this.baseOff[i + 1] - this.baseOff[i]; + return dirLen === 0 ? baseLen : dirLen + 1 + baseLen; + } + + /** Reconstructs a full path. Called only for displayed rows. */ + pathOf(i) { + const d = this.dirId[i]; + const ds = this.dirOff[d]; + const de = this.dirOff[d + 1]; + const base = this.decoder.decode(this.baseBuf.subarray(this.baseOff[i], this.baseOff[i + 1])); + if (de === ds) return base; + return this.decoder.decode(this.dirBuf.subarray(ds, de)) + '/' + base; + } + + /** + * Compares `bytes` against the path at `i`, as unsigned bytes. + * + * Walks the stored directory and basename in place rather than rebuilding + * the path, so a lookup costs no allocation. + */ + cmpPathAt(i, bytes) { + const d = this.dirId[i]; + const ds = this.dirOff[d]; + const de = this.dirOff[d + 1]; + const bs = this.baseOff[i]; + const be = this.baseOff[i + 1]; + const dirLen = de - ds; + const pathLen = dirLen === 0 ? be - bs : dirLen + 1 + (be - bs); + const n = bytes.length < pathLen ? bytes.length : pathLen; + for (let k = 0; k < n; k++) { + const c = this.byteAt(i, k, ds, bs, dirLen); + if (bytes[k] !== c) return bytes[k] - c; + } + return bytes.length - pathLen; + } + + /** + * Index of an exact path, or -1. + * + * The server emits paths in tree order, which for full paths is plain + * byte-lexicographic ascending order; that was checked over all 506,237 + * paths of chromium/src, so a binary search is sound. + */ + indexOfPath(path) { + const bytes = ENC.encode(path); + let lo = 0; + let hi = this.n - 1; + while (lo <= hi) { + const mid = (lo + hi) >> 1; + const c = this.cmpPathAt(mid, bytes); + if (c === 0) return mid; + if (c < 0) hi = mid - 1; + else lo = mid + 1; + } + return -1; + } + + /** + * Orders the path at `i` against `bytes` read as a prefix: negative if the + * path sorts before it, zero if the path starts with it, positive after. + * + * Note the sign convention is path-minus-query, matching {@link cmpPrefix}, + * which does the same job for basenames -- and the opposite of {@link + * cmpPathAt}, which answers a different question. + */ + pathStartsCmp(i, bytes) { + const d = this.dirId[i]; + const ds = this.dirOff[d]; + const de = this.dirOff[d + 1]; + const bs = this.baseOff[i]; + const dirLen = de - ds; + const pathLen = dirLen === 0 ? this.baseOff[i + 1] - bs : dirLen + 1 + (this.baseOff[i + 1] - bs); + // A path shorter than the query cannot start with it, and sorts before it. + if (pathLen < bytes.length) { + const n = pathLen; + for (let k = 0; k < n; k++) { + const c = this.byteAt(i, k, ds, bs, dirLen); + if (c !== bytes[k]) return c - bytes[k]; + } + return -1; + } + for (let k = 0; k < bytes.length; k++) { + const c = this.byteAt(i, k, ds, bs, dirLen); + if (c !== bytes[k]) return c - bytes[k]; + } + return 0; + } + + /** Byte `k` of path `i`, reading the stored directory and basename in place. */ + byteAt(i, k, ds, bs, dirLen) { + if (dirLen === 0) return this.baseBuf[bs + k]; + if (k < dirLen) return this.dirBuf[ds + k]; + if (k === dirLen) return SLASH; + return this.baseBuf[bs + k - dirLen - 1]; + } + + /** + * Half-open range of the index whose full paths literally start with the + * query as typed. + * + * Sound because the index is in byte order, so those paths are contiguous -- + * the same property {@link indexOfPath} relies on, and the reason a + * caller-supplied list is sorted on the way in. + * + * Deliberately case-sensitive: the order is over raw bytes, and a + * case-folded range would not be contiguous. Callers must therefore use this + * only to promote, never to filter, so that a reader who types the wrong + * case loses the promotion and not the result. + */ + pathPrefixRange() { + const bytes = this.qRaw; + if (bytes.length === 0) return [0, 0]; + let lo = 0; + let hi = this.n; + while (lo < hi) { + const m = (lo + hi) >> 1; + if (this.pathStartsCmp(m, bytes) < 0) lo = m + 1; + else hi = m; + } + const start = lo; + hi = this.n; + while (lo < hi) { + const m = (lo + hi) >> 1; + if (this.pathStartsCmp(m, bytes) <= 0) lo = m + 1; + else hi = m; + } + return [start, lo]; + } +} + +/** + * Sorts file indices by basename. At half a million entries this costs roughly + * a quarter of a second, once, in a worker. + */ +function buildBasenameOrder(ix) { + const order = new Array(ix.n); + for (let i = 0; i < ix.n; i++) order[i] = i; + const buf = ix.baseBuf; + const off = ix.baseOff; + order.sort((a, b) => { + let x = off[a]; + let y = off[b]; + const xe = off[a + 1]; + const ye = off[b + 1]; + while (x < xe && y < ye) { + const d = LOW[buf[x++]] - LOW[buf[y++]]; + if (d !== 0) return d; + } + return xe - off[a] - (ye - off[b]); + }); + return Int32Array.from(order); +} + +// --------------------------------------------------------------- scoring + +const BONUS_START = 40; +const BONUS_SEPARATOR = 30; +const BONUS_CAMEL = 25; +const BONUS_CONSECUTIVE = 20; +const PENALTY_GAP = 3; +const MAX_GAP_PENALTY = 30; + +/** + * Scratch for match offsets. Scoring runs on every candidate of every + * keystroke -- hundreds of thousands of times -- so it must not allocate. + * Basenames longer than this are still matched and scored, just without + * highlight offsets past the limit. + */ +const POS = new Int32Array(256); +let posCount = 0; + +/** + * Scores how well `q[from..]` aligns inside basename `i`, recording match + * offsets in `POS[0..posCount)` for highlighting. + * + * Two passes. A forward greedy match finds the earliest position at which the + * query can finish; a backward greedy match from there yields the tightest + * window, which is what a reader perceives as the real match. Forward-only + * greedy binds each character as early as it can and routinely selects the + * wrong occurrence -- for `gv` against `.../gitiles/GitilesView.java` it binds + * `g` to the first `g` of `gitiles` rather than to `GitilesView`. + * + * @return {number} score, or -1 when there is no match. + */ +function scoreBasename(ix, i, from) { + const q = ix.q; + const ql = q.length; + const buf = ix.baseBuf; + const s = ix.baseOff[i]; + const e = ix.baseOff[i + 1]; + posCount = 0; + if (from >= ql) return 0; + + let k = from; + let end = -1; + for (let j = s; j < e; j++) { + if (LOW[buf[j]] === q[k] && ++k === ql) { + end = j; + break; + } + } + if (end < 0) return -1; + + const count = ql - from; + const capped = count <= POS.length ? count : POS.length; + k = ql - 1; + for (let j = end; j >= s; j--) { + if (LOW[buf[j]] === q[k]) { + const slot = k - from; + if (slot < capped) POS[slot] = j - s; + if (k-- === from) break; + } + } + posCount = capped; + + let score = 0; + let prev = -2; + for (let t = 0; t < capped; t++) { + const pos = POS[t]; + const abs = s + pos; + if (pos === 0) { + score += BONUS_START; + } else { + const before = buf[abs - 1]; + if (SEP[before]) score += BONUS_SEPARATOR; + else if (isUpper(buf[abs]) && isLower(before)) score += BONUS_CAMEL; + } + if (pos === prev + 1) score += BONUS_CONSECUTIVE; + else if (prev >= 0) score -= Math.min((pos - prev - 1) * PENALTY_GAP, MAX_GAP_PENALTY); + prev = pos; + } + // Prefer covering more of a shorter name. + score -= (e - s - count) >> 1; + return score; +} + +// --------------------------------------------------------------- top-K + +/** + * Keeps the best `limit` items in an insertion-sorted pair of typed arrays. + * + * Exact: an item is rejected only when it cannot beat the current k-th best, + * and that threshold only ever rises. Candidates are offered in ascending + * index order and ties do not displace, so ordering is stable. + * + * Allocation-free by construction. The naive version -- push an object per + * candidate, sort at the end -- costs a hundred thousand short-lived objects + * on a broad query, which dominated everything else in the profile. + */ +class TopK { + constructor(limit) { + this.limit = limit; + this.score = new Float64Array(limit); + this.id = new Int32Array(limit); + this.size = 0; + } + + offer(score, id) { + const full = this.size === this.limit; + if (full && score <= this.score[this.limit - 1]) return; + let i = full ? this.limit - 1 : this.size++; + while (i > 0 && this.score[i - 1] < score) { + this.score[i] = this.score[i - 1]; + this.id[i] = this.id[i - 1]; + i--; + } + this.score[i] = score; + this.id[i] = id; + } + + ids() { + return Array.from(this.id.subarray(0, this.size)); + } +} + +// --------------------------------------------------------------- channels + +/** + * Greedy-maximal prefix of the query consumed by each directory, including the + * separator that follows it. + * + * Greedy is optimal here: consuming as much of the query as possible in the + * directory leaves the shortest remainder for the basename, and being a + * subsequence is monotone in the remainder. So a file matches the full path if + * and only if `q[dm[dir]..]` is a subsequence of its basename. Computing this + * once per directory rather than once per file is the whole reason the + * full-path channel is affordable. + * + * Each directory shares `lcp` bytes with the one before it, and the greedy + * state after those bytes is by definition identical, so `kAt` records the + * state at every offset of the directory just scanned and the next directory + * resumes from its own shared length. Only differing tails are examined. + * + * The one wrinkle is saturation. A scan that consumes the whole query stops + * early and leaves `kAt` unwritten past that point, so `sat` records where + * that happened and any resume at or beyond it is saturated by definition. + * Crucially `sat` must then be left alone: such a resume writes no `kAt` at + * all, and since the directory agrees with its predecessor for `lcp >= sat` + * bytes it saturates at the very same offset. Advancing `sat` to `lcp` would + * claim a range of `kAt` as valid that no scan has written since, and a later + * directory with a smaller `lcp` would resume from a stale state and + * under-count its match. Holding `sat` fixed keeps it equal to the highest + * offset `kAt` is valid at, so every read is either a written entry or a + * saturated one. + */ +function dirPrefixLens(ix) { + const q = ix.q; + const ql = q.length; + const dm = ix.dmScratch; + const kAt = ix.kAt; + const buf = ix.dirBuf; + const off = ix.dirOff; + const lcp = ix.dirLcp; + const nd = ix.d; + let sat = 0x7fffffff; + kAt[0] = 0; + for (let d = 0; d < nd; d++) { + const s = off[d]; + const len = off[d + 1] - s; + const l = lcp[d]; + let k; + if (l >= sat) { + k = ql; + } else { + k = kAt[l]; + let j = l; + for (; j < len && k < ql; j++) { + if (LOW[buf[s + j]] === q[k]) k++; + kAt[j + 1] = k; + } + sat = k === ql ? j : 0x7fffffff; + } + dm[d] = len > 0 && k < ql && q[k] === SLASH ? k + 1 : k; + } + return dm; +} + +/** + * Where in the query the basename of `i` has to start, for scoring. + * + * {@link dirPrefixLens} is greedy-maximal, which is exactly right for deciding + * whether a file matches at all: consuming as much as possible in the directory + * leaves the shortest remainder for the basename. It is the wrong split for + * scoring, because the greed 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, took the penalty in {@link search}, and landed + * below files whose basenames matched far worse but whose directories happened + * to contain none of the query -- typing the name of a file exactly put it at + * position 9 behind eight unrelated test pages. + * + * A basename that carries the whole filename portion of the query on its own + * -- everything after the last `/`, or the whole query when there is none -- + * is scored from there, whatever deeper directories could also have supplied. + * Every candidate returned by {@link narrowD} has already consumed all slashes + * in its directory (`dm[dir] >= minFrom`), so the candidate set and the + * monotone narrowing it depends on are unchanged. + */ +function scoreFrom(ix, dm, i) { + const minFrom = ix.q.lastIndexOf(SLASH) + 1; + return ix.baseMatchesFrom(i, minFrom) ? minFrom : dm[ix.dirId[i]]; +} + +/** + * Highlight ranges for the prefix `q[0..from)` matched in the directory of `i` + * (including the separator slash when `dirPrefixLens` consumed it). + */ +function dirRangesOf(ix, i, from) { + if (from <= 0) return []; + const d = ix.dirId[i]; + const ds = ix.dirOff[d]; + const de = ix.dirOff[d + 1]; + const buf = ix.dirBuf; + const q = ix.q; + const ranges = []; + let k = 0; + for (let j = ds; j < de && k < from; j++) { + if (LOW[buf[j]] === q[k]) { + const p = j - ds; + const last = ranges.length ? ranges[ranges.length - 1] : null; + if (last && last[0] + last[1] === p) last[1]++; + else ranges.push([p, 1]); + k++; + } + } + if (k < from && de > ds && q[k] === SLASH) { + const p = de - ds; + const last = ranges.length ? ranges[ranges.length - 1] : null; + if (last && last[0] + last[1] === p) last[1]++; + else ranges.push([p, 1]); + } + return ranges; +} + +/** Merges basename-relative match offsets into full-path highlight ranges. */ +function rangesOf(shift, prefix = []) { + const ranges = prefix; + for (let t = 0; t < posCount; t++) { + const p = POS[t] + shift; + const last = ranges.length ? ranges[ranges.length - 1] : null; + if (last && last[0] + last[1] === p) last[1]++; + else ranges.push([p, 1]); + } + return ranges; +} + +/** + * Builds a displayed row, dropping highlight ranges the UI cannot apply. + * + * Everything the engine measures is measured in UTF-8 bytes, but the UI marks + * substrings of a JS string, whose indices are UTF-16 code units. The two agree + * only for an ASCII path. For anything else the marks land on characters that + * did not match -- on chromium/src, searching for the stars in + * `file-for-drag-to-send3-ABC~...★星🌟星★...XYZ.txt` highlighted `XYZ`. + * + * Marking nothing is honest; marking the wrong characters is not. The link + * itself is built from the whole path and is unaffected either way. + */ +function row(ix, i, ranges) { + const path = ix.pathOf(i); + return {path, ranges: path.length === ix.pathByteLen(i) ? ranges : []}; +} + +/** + * Narrows the channel-D candidate set to the current query. + * + * Full-path subsequence matching is monotone under query extension, exactly as + * basename matching is, so this reuses the deepest previously computed set + * rather than rescanning the corpus. That matters because channel D engages + * for a whole path-directed query -- "base/task/thread" reaches it at the + * fifth keystroke and stays there -- and a full scan on each of the remaining + * keystrokes is what made this the slowest path in the engine. + * + * Filtering directly with the complete query rather than one byte at a time is + * valid for the same reason: matches of the longer query are a subset. + */ +function narrowD(ix, dm) { + const q = ix.q; + const ql = q.length; + let t = ql; + while (t > 0 && ix.dcand[t] === undefined) t--; + const start = ix.dcand[t]; + + // sufMask[k] is the 1-gram mask of q[k..]. A file can only match if its + // basename *alone* contains every character the directory failed to consume. + // That is strictly sharper than asking whether the directory and basename + // together contain the whole query, because directory characters cannot + // discharge an obligation that falls on the basename: on "base/task/thread" + // it cuts the files needing a subsequence scan from 239,228 to 553. + const sufMask = new Int32Array(ql + 1); + for (let k = ql - 1; k >= 0; k--) { + sufMask[k] = sufMask[k + 1] | (1 << CLS[q[k]]); + } + + const out = ix.scratch; + const baseMask = ix.baseMask; + const dirId = ix.dirId; + let n = 0; + + if (start === null || start === undefined) { + const dirEnd = ix.dirEnd; + const nd = ix.d; + let i = 0; + for (let d = 0; d < nd; d++) { + const end = dirEnd[d]; + const from = dm[d]; + if (from >= ql) { + // The directory alone consumed the query, so every file beneath it + // matches and none of them needs testing. + while (i < end) out[n++] = i++; + continue; + } + const need = sufMask[from]; + while (i < end) { + if ((need & ~baseMask[i]) === 0 && ix.baseMatchesFrom(i, from)) out[n++] = i; + i++; + } + } + } else { + for (let x = 0; x < start.length; x++) { + const i = start[x]; + const from = dm[dirId[i]]; + if ((sufMask[from] & ~baseMask[i]) !== 0) continue; + if (ix.baseMatchesFrom(i, from)) out[n++] = i; + } + } + const result = out.slice(0, n); + ix.dcand[ql] = result; + return result; +} + +/** + * Runs the ranked channels in cost order. + * + * A literal prefix of the whole path -- two binary searches + * B exact and prefix on the basename -- two binary searches + * C subsequence on the basename -- scan of the narrowed candidate set + * D subsequence on the full path -- dir-memoised, monotonically narrowed + * + * A channel is skipped only when a cheaper one already filled the display. + * That is exact rather than heuristic, because the ranking policy is a strict + * tiering: a path the reader has literally spelled the start of outranks + * everything, then a basename prefix outranks a non-prefix, and a basename + * match outranks a match that needed the directory. Nothing a later channel + * produces can displace what an earlier one found. + * + * A exists because B, C and D all score the *basename* alone. When the + * directory has already absorbed the whole query -- which is exactly what + * happens for "base/task" or "device/" -- scoreBasename returns 0, so a + * perfect prefix match scored zero and sank below any path where the basename + * happened to contribute. Typing a path got monotonically worse results the + * more of it you spelled, which is the opposite of what a finder is for. + * + * D is a superset of both A and C, so when D runs its count is the + * authoritative total. + */ +function search(ix) { + const q = ix.q; + + if (q.length === 0) { + const top = new TopK(LIMIT); + for (let i = 0; i < ix.n; i++) top.offer(ix.staticRank[i], i); + return { + total: ix.n, + exact: true, + items: top.ids().map((id) => ({path: ix.pathOf(id), ranges: []})), + }; + } + + // ---- channel A + const [as, ae] = ix.pathPrefixRange(); + const pathPrefixCount = ae - as; + let headroom = LIMIT - pathPrefixCount; + const head = []; + if (pathPrefixCount > 0) { + const top = new TopK(pathPrefixCount < LIMIT ? pathPrefixCount : LIMIT); + for (let i = as; i < ae; i++) top.offer(ix.staticRank[i], i); + for (const id of top.ids()) { + head.push(row(ix, id, [[0, ix.qRaw.length]])); + } + if (headroom <= 0) { + // The count is a lower bound: other paths may match without starting + // with the query. The display says so with a trailing "+". + return {total: pathPrefixCount, exact: false, items: head}; + } + } + + // ---- channel B + // + // Like A, basename-prefix matches are promoted into `head` even when there + // are too few of them to fill the display on their own, so a later channel + // can never place a non-prefix match above a prefix one or jump the order + // when the prefix count crosses LIMIT. + const [ps, pe] = ix.prefixRange(q); + let bCount = 0; + if (pe > ps) { + const top = new TopK(headroom); + for (let m = ps; m < pe; m++) { + const i = ix.byBase[m]; + if (i >= as && i < ae) continue; + bCount++; + const exact = ix.baseOff[i + 1] - ix.baseOff[i] === q.length; + top.offer(ix.staticRank[i] + (exact ? 1 << 20 : 0), i); + } + for (const id of top.ids()) { + head.push(row(ix, id, [[ix.shiftOf(id), q.length]])); + } + headroom = LIMIT - head.length; + if (headroom <= 0) { + return {total: pathPrefixCount + bCount, exact: false, items: head}; + } + } + + // Anything already promoted by A or B must not appear twice. + const promoted = (i) => + (i >= as && i < ae) || (bCount > 0 && ix.cmpPrefix(i, q) === 0); + + // ---- channel C + // + // Every entry in `cand` is already a basename subsequence match; the length + // penalty in scoreBasename can push a weak match in a long basename below + // zero, so a negative score is still a match and must not be filtered out. + const cand = ix.cand[ix.cand.length - 1]; + const count = cand === null ? ix.n : cand.length; + if (count >= headroom + head.length) { + const top = new TopK(headroom); + for (let x = 0; x < count; x++) { + const i = cand === null ? x : cand[x]; + if (promoted(i)) continue; + const sc = scoreBasename(ix, i, 0); + top.offer(sc * 1024 + ix.staticRank[i], i); + } + const items = head.concat( + top.ids().map((id) => { + scoreBasename(ix, id, 0); + return row(ix, id, rangesOf(ix.shiftOf(id))); + }), + ); + return {total: Math.max(count, items.length), exact: false, items}; + } + + // ---- channel D + // + // Reached when the cheaper channels cannot fill the display, which is the + // normal case for a path-directed query such as "base/task/thread". Without + // it the finder would report no matches for files that plainly exist. + const dm = dirPrefixLens(ix); + const matches = narrowD(ix, dm); + const top = new TopK(headroom); + for (let x = 0; x < matches.length; x++) { + const i = matches[x]; + if (promoted(i)) continue; + const from = scoreFrom(ix, dm, i); + const sc = scoreBasename(ix, i, from); + // A match that needed the directory ranks below any basename-only match. + top.offer(sc * 1024 + ix.staticRank[i] - (from > 0 ? 1 << 24 : 0), i); + } + const items = head.concat( + top.ids().map((id) => { + const from = scoreFrom(ix, dm, id); + scoreBasename(ix, id, from); + return row(ix, id, rangesOf(ix.shiftOf(id), dirRangesOf(ix, id, from))); + }), + ); + // Every path that starts with the query also contains it as a subsequence, + // so D has already counted what A and B promoted. + return {total: matches.length, exact: true, items}; +} + +/** + * Orders `names` by their UTF-8 bytes. + * + * The order an `Index` is built from is not cosmetic. `indexOfPath` binary + * searches it, so an unsorted index silently fails to find paths that are + * present -- measured on a real host index, 2,828 of 2,838 lookups. The + * directory-run compression also assumes runs of paths sharing a directory sit + * next to each other; scrambled input still answers correctly but loses the + * compression that makes the full-path channel fast. + * + * A recursive git tree listing already arrives in byte order. A caller-supplied + * list comes from whatever the page had and cannot be assumed to be in any + * order at all, so it is sorted here, with the code that depends on it, rather + * than trusted. + * + * The default `Array#sort` compares UTF-16 code units, which agrees with UTF-8 + * byte order for ASCII but not above it, so the bytes are compared directly. + */ +function sortByBytes(names) { + const keyed = names.map((s) => ({s, b: ENC.encode(s)})); + keyed.sort((x, y) => { + const a = x.b; + const b = y.b; + const n = a.length < b.length ? a.length : b.length; + for (let i = 0; i < n; i++) { + if (a[i] !== b[i]) return a[i] - b[i]; + } + return a.length - b.length; + }); + return keyed.map((e) => e.s); +} + +// --------------------------------------------------------------- messages + +self.onmessage = async (ev) => { + const msg = ev.data; + try { + if (msg.type === 'load') { + // Two sources, one index: a URL to fetch a listing from, or a list the + // page already had and so need not be asked for again. + let names; + if (msg.names) { + names = sortByBytes(msg.names); + } else { + const res = await fetch(msg.url, {credentials: 'same-origin'}); + if (!res.ok) throw new Error('HTTP ' + res.status); + const text = await res.text(); + // Gitiles prefixes JSON responses with an anti-XSSI guard. + const body = JSON.parse(text.replace(/^\)\]\}'\n/, '')); + names = body.paths || []; + } + index = new Index(names); + self.postMessage({type: 'ready', total: index.n}); + return; + } + if (msg.type === 'query') { + if (index === null) return; + index.setQuery(msg.q); + const {total, exact, items} = search(index); + self.postMessage({ + type: 'results', + seq: msg.seq, + q: msg.q, + total, + exact, + items, + }); + return; + } + if (msg.type === 'recent') { + // Remembered paths are only offered if they still exist at this + // revision: a file deleted or renamed since it was last opened would + // otherwise be presented as a result that 404s on Enter. Order is the + // caller's, so ranking stays entirely in the UI where the scores live. + // + // Cut to LIMIT like every other channel. The UI paints exactly that many + // rows but sizes its selection from the item count, so a reader with more + // than LIMIT remembered files could arrow past the last painted row into + // a selection that highlighted nothing and did nothing on Enter. + if (index === null) return; + const items = []; + for (let i = 0; i < msg.paths.length && items.length < LIMIT; i++) { + if (index.indexOfPath(msg.paths[i]) >= 0) { + items.push({path: msg.paths[i], ranges: []}); + } + } + self.postMessage({ + type: 'results', + seq: msg.seq, + q: '', + total: items.length, + exact: true, + recent: true, + items, + }); + return; + } + } catch (e) { + self.postMessage({type: 'error', message: String(e && e.message ? e.message : e)}); + } +};
diff --git a/resources/com/google/gitiles/static/file-search.js b/resources/com/google/gitiles/static/file-search.js new file mode 100644 index 0000000..9f503b7 --- /dev/null +++ b/resources/com/google/gitiles/static/file-search.js
@@ -0,0 +1,869 @@ +// Copyright (C) 2026 The Android Open Source Project +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +/** + * Finder UI. Press "/" to open, type to filter, Enter to go. + * + * One palette, two sources. A page that addresses a tree finds files, matching + * against an index fetched on first open -- not on page load, so a reader who + * never searches costs the server nothing. A host index finds repositories, + * which that page already lists, so nothing is fetched at all. + * + * All matching happens in a Worker (file-search-worker.js); this file only + * moves text in and paints rows out, so the input never stutters regardless of + * how much there is to search. + */ +(function () { + 'use strict'; + + /** Rows rendered. Must match LIMIT in the worker. */ + var LIMIT = 20; + + /** Rows PageUp/PageDown move by. Half a screen, so context is never lost. */ + var PAGE = 10; + + var trigger = document.querySelector('.FileSearch-trigger'); + var root = document.getElementById('file-search'); + if (!root || typeof Worker === 'undefined') { + if (trigger) { + trigger.hidden = true; + } + return; + } + + var workerUrl = root.getAttribute('data-worker-url'); + var treeUrl = root.getAttribute('data-tree-url'); + var repoMode = root.getAttribute('data-kind') === 'repositories'; + if (!workerUrl || (!repoMode && !treeUrl)) { + if (trigger) { + trigger.hidden = true; + } + return; + } + + /** What is being searched, for the reader-facing copy. */ + var NOUN = repoMode ? 'repositories' : 'files'; + var NOUN_ONE = repoMode ? 'repository' : 'file'; + var NOUN_CAP = repoMode ? 'Repository' : 'File'; + + /** + * The repositories this page lists: their names, links and descriptions. + * + * The host index renders every repository it knows about, so reading them + * back out of the document is both cheaper than asking the server for the + * same list again -- that response carries no revision and is therefore + * served no-store, so it would be re-fetched on every page load -- and + * exactly consistent with what the reader can see. Nothing can be missing + * from the finder that is present on the page, because they are the same + * list. The contract is the RepoList markup in HostIndex.soy. + * + * Names are used as keys, so the maps have no prototype: a repository may + * legitimately be called "constructor". + */ + function collectRepositories() { + var names = []; + var hrefs = Object.create(null); + var descs = Object.create(null); + var items = document.querySelectorAll('.RepoList .RepoList-item[href]'); + for (var i = 0; i < items.length; i++) { + var nameEl = items[i].querySelector('.RepoList-itemName'); + var name = nameEl ? nameEl.textContent.trim() : ''; + if (!name || hrefs[name] !== undefined) { + continue; + } + names.push(name); + hrefs[name] = items[i].getAttribute('href'); + var descEl = items[i].querySelector('.RepoList-itemDescription'); + var desc = descEl ? descEl.textContent.trim() : ''; + if (desc) { + descs[name] = desc; + } + } + return {names: names, hrefs: hrefs, descs: descs}; + } + + var repos = repoMode ? collectRepositories() : null; + if (repoMode && !repos.names.length) { + // A host index with nothing on it. Offering an empty palette would be + // worse than offering none, and the header trigger should not remain as a + // button that does nothing. + if (trigger) { + trigger.hidden = true; + } + return; + } + + // Base for file result links: the listing URL without its query string. It + // ends in a slash, so appending an encoded path yields the file's page. + // Repository links come from the page and need no base. + var fileBase = repoMode ? null : treeUrl.split('?')[0]; + + var input = root.querySelector('.FileSearch-input'); + var status = root.querySelector('.FileSearch-status'); + var list = root.querySelector('.FileSearch-results'); + + var worker = null; + var state = 'idle'; // idle | loading | ready | error + var seq = 0; + var lastRendered = -1; + var selected = 0; + var rows = []; + var composing = false; + var restoreFocus = null; + var showingRecent = false; + + // -------------------------------------------------------------- frecency + + /** + * What this reader has opened from the finder, most useful first. + * + * With an empty box there is nothing to match on, and listing alphabetically + * is useless -- on chromium/src that offers ".gn", and on a host index the + * first repository nobody has heard of. What a reader wants is the handful + * of entries they keep coming back to. + * + * 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). So an + * entry's weight halves for every week it goes untouched, frequent entries + * outrank once-opened ones, and one abandoned months ago falls away without + * ever needing a visit history: one number and one timestamp per entry + * suffice, and updating is O(1). + * + * Storage is scoped to the listing it describes -- a repository for paths, a + * host index for repository names, since a prefixed index lists them + * relative to that prefix -- and is capped so a long-lived browser cannot + * accumulate unbounded history. It records only what the reader opened + * *through the finder*, never pages merely visited. + * + * A host index is served at its path with or without a trailing slash, and + * without a redirect, so the slash is dropped from the key: otherwise one + * index would keep two histories depending on how it was reached. + */ + var RECENT_KEY = + 'gitiles.file-finder.recent.' + + (repoMode + ? 'repositories:' + (location.pathname.replace(/\/+$/, '') || '/') + : fileBase.split('/+/')[0]); + var RECENT_MAX = 200; + var RECENT_HALF_LIFE_MS = 7 * 24 * 60 * 60 * 1000; + + /** Reads the store, tolerating absence, denial, and corruption alike. */ + function loadRecent() { + var raw; + try { + raw = window.localStorage.getItem(RECENT_KEY); + } catch (e) { + // Storage can be disabled outright; the finder still works without it. + return []; + } + if (!raw) { + return []; + } + var parsed; + try { + parsed = JSON.parse(raw); + } catch (e) { + return []; + } + if (!parsed || !parsed.length) { + return []; + } + var out = []; + for (var i = 0; i < parsed.length; i++) { + var e = parsed[i]; + if (e && typeof e.p === 'string' && isFinite(e.s) && isFinite(e.t)) { + out.push({p: e.p, s: e.s, t: e.t}); + } + } + return out; + } + + function saveRecent(entries) { + try { + window.localStorage.setItem(RECENT_KEY, JSON.stringify(entries)); + } catch (e) { + // A full or read-only store is not worth reporting to the reader. + } + } + + /** Score of `e` decayed to `now`. */ + function decayed(e, now) { + return e.s * Math.pow(2, -(now - e.t) / RECENT_HALF_LIFE_MS); + } + + /** Records that the reader opened `path` from the finder. */ + function recordVisit(path) { + var now = Date.now(); + var entries = loadRecent(); + var found = null; + for (var i = 0; i < entries.length; i++) { + if (entries[i].p === path) { + found = entries[i]; + break; + } + } + if (found) { + found.s = decayed(found, now) + 1; + found.t = now; + } else { + entries.push({p: path, s: 1, t: now}); + } + if (entries.length > RECENT_MAX) { + entries.sort(function (a, b) { + return decayed(b, now) - decayed(a, now); + }); + entries.length = RECENT_MAX; + } + saveRecent(entries); + } + + /** Remembered paths, best first. */ + function recentPaths() { + var now = Date.now(); + var entries = loadRecent(); + entries.sort(function (a, b) { + return decayed(b, now) - decayed(a, now); + }); + var out = []; + for (var i = 0; i < entries.length && i < RECENT_MAX; i++) { + out.push(entries[i].p); + } + return out; + } + + // ------------------------------------------------------------- rendering + + /** + * Builds one row. + * + * The id is what lets the input name the selected row through + * aria-activedescendant: arrow keys never move focus, so without it a screen + * reader is told nothing at all as the selection travels. The link is taken + * out of the tab order for the same reason -- options in a listbox are not + * tab stops, and leaving them as stops would let Tab walk out of a dialog + * that declares itself modal. + */ + function makeRow(n) { + var li = document.createElement('li'); + li.className = 'FileSearch-row'; + li.id = 'file-search-row-' + n; + li.setAttribute('role', 'option'); + var a = document.createElement('a'); + a.className = 'FileSearch-link'; + a.tabIndex = -1; + li.appendChild(a); + list.appendChild(li); + return {li: li, a: a, path: null}; + } + + for (var i = 0; i < LIMIT; i++) { + rows.push(makeRow(i)); + } + + /** Encodes a repository path for use in a URL, preserving separators. */ + function encodePath(path) { + return path.split('/').map(encodeURIComponent).join('/'); + } + + /** + * Paints one row, marking the matched characters. + * + * `ranges` are [start, length] pairs over the path, already merged and in + * order by the worker. + */ + function paint(row, item) { + var a = row.a; + // A repository's link is whatever the page linked to; a file's is composed + // from the listing it was indexed from. + a.href = repoMode ? repos.hrefs[item.path] : fileBase + encodePath(item.path); + row.path = item.path; + while (a.firstChild) { + a.removeChild(a.firstChild); + } + var path = item.path; + var ranges = item.ranges || []; + var at = 0; + for (var r = 0; r < ranges.length; r++) { + var start = ranges[r][0]; + var len = ranges[r][1]; + if (start > at) { + a.appendChild(document.createTextNode(path.substring(at, start))); + } + var mark = document.createElement('mark'); + mark.textContent = path.substring(start, start + len); + a.appendChild(mark); + at = start + len; + } + if (at < path.length) { + a.appendChild(document.createTextNode(path.substring(at))); + } + if (repoMode && repos.descs[path]) { + // Repository names alone are often not enough to choose between: the + // page shows the description beside the name, so the finder does too. + // A space node separates the two for screen readers, which otherwise + // concatenate adjacent inline text across element boundaries. + a.appendChild(document.createTextNode(' ')); + var desc = document.createElement('span'); + desc.className = 'FileSearch-rowDesc'; + desc.textContent = repos.descs[path]; + a.appendChild(desc); + } + row.li.hidden = false; + } + + function render(items, total, exact) { + for (var i = 0; i < LIMIT; i++) { + if (i < items.length) { + paint(rows[i], items[i]); + } else { + rows[i].li.hidden = true; + rows[i].a.removeAttribute('href'); + rows[i].path = null; + } + } + // Count the rows that were painted, not the items that arrived. The worker + // cuts to LIMIT, but the display is what the selection moves over, and + // deriving one from the other is what let a longer message strand the + // selection past the last row. + lastRendered = items.length < LIMIT ? items.length : LIMIT; + if (selected >= lastRendered) { + selected = lastRendered ? lastRendered - 1 : 0; + } + highlight(); + + if (!items.length) { + // The scan is exhaustive, so this is trustworthy rather than a hedge. + setStatus(input.value ? 'No matching ' + NOUN : ''); + return; + } + if (showingRecent) { + // A count of remembered entries is not a match count, and calling it one + // would be a lie the reader can check. + setStatus(items.length === 1 ? 'Recently opened' : 'Recently opened ' + NOUN); + return; + } + // A trailing "+" means the search stopped once the best tier filled the + // display, so more paths match than were counted. See the worker protocol. + var count = total.toLocaleString() + (exact ? '' : '+'); + if (total > items.length) { + setStatus('Showing ' + items.length + ' of ' + count + ' matches'); + } else { + setStatus(count + (total === 1 ? ' match' : ' matches')); + } + } + + function setStatus(text) { + status.textContent = text; + } + + function clearRows() { + for (var i = 0; i < LIMIT; i++) { + rows[i].li.hidden = true; + rows[i].a.removeAttribute('href'); + rows[i].path = null; + } + lastRendered = 0; + selected = 0; + highlight(); + } + + function highlight() { + var active = null; + for (var i = 0; i < LIMIT; i++) { + var on = i === selected && !rows[i].li.hidden; + rows[i].li.classList.toggle('FileSearch-row--selected', on); + rows[i].li.setAttribute('aria-selected', on ? 'true' : 'false'); + if (on) { + active = rows[i].li.id; + rows[i].li.scrollIntoView({block: 'nearest'}); + } + } + // Focus stays in the input, so this is the only thing that tells a screen + // reader which row the arrow keys just moved to. + if (active) { + input.setAttribute('aria-activedescendant', active); + } else { + input.removeAttribute('aria-activedescendant'); + } + schedulePrefetch(); + } + + // ---------------------------------------------------------------- worker + + function ensureWorker() { + if (worker && state !== 'error') { + return; + } + if (worker) { + // A previous attempt failed. The reader asking again is the retry: a + // one-off network failure on first open should not disable the finder + // for the life of the page. + worker.terminate(); + worker = null; + } + clearRows(); + state = 'loading'; + setStatus('Loading ' + NOUN_ONE + ' index\u2026'); + try { + worker = new Worker(workerUrl); + } catch (e) { + // A deployment content security policy that forbids workers rejects the + // constructor synchronously, and there is no event to observe afterwards. + // Caught here because open() has already revealed the overlay and has not + // yet focused the input: throwing would leave the reader with a dialog + // they can neither type into nor dismiss with Escape. + worker = null; + state = 'error'; + setStatus(NOUN_CAP + ' search is unavailable on this page'); + return; + } + worker.onmessage = function (ev) { + var msg = ev.data; + if (msg.type === 'ready') { + state = 'ready'; + setStatus(msg.total.toLocaleString() + ' ' + NOUN); + query(); + } else if (msg.type === 'results') { + // Ignore responses overtaken by later keystrokes. + if (msg.seq === seq) { + if (showingRecent && !msg.items.length) { + showingRecent = false; + seq++; + worker.postMessage({type: 'query', seq: seq, q: input.value}); + return; + } + render(msg.items, msg.total, msg.exact); + } + } else if (msg.type === 'error') { + var loading = state === 'loading'; + state = 'error'; + setStatus( + (loading ? 'Could not load ' + NOUN_ONE + ' index: ' : NOUN_CAP + ' search failed: ') + + msg.message, + ); + } + }; + worker.onerror = function () { + state = 'error'; + setStatus('Could not load ' + NOUN_ONE + ' index'); + }; + worker.postMessage( + repoMode ? {type: 'load', names: repos.names} : {type: 'load', url: treeUrl}, + ); + } + + function query() { + if (state !== 'ready' || composing) { + return; + } + // A new query is a new result set, so the selection returns to the best + // match. Carrying it over meant that once a reader had arrowed at all, + // every later query left them on an arbitrary row -- which is the row Enter + // opens and the row the prefetch warms. + selected = 0; + seq++; + // An empty box has nothing to match on, so offer what the reader keeps + // coming back to. Falls through to the ordinary listing when there is + // nothing remembered yet, which is every reader's first visit. + if (!input.value) { + var paths = recentPaths(); + if (paths.length) { + showingRecent = true; + worker.postMessage({type: 'recent', seq: seq, paths: paths}); + return; + } + } + showingRecent = false; + worker.postMessage({type: 'query', seq: seq, q: input.value}); + } + + // ------------------------------------------------------------------- open + + function open() { + if (!root.hidden) { + return; + } + restoreFocus = document.activeElement; + root.hidden = false; + document.body.classList.add('FileSearch-open'); + input.value = ''; + selected = 0; + ensureWorker(); + input.focus(); + if (state === 'ready') { + query(); + } + } + + function close() { + if (root.hidden) { + return; + } + root.hidden = true; + document.body.classList.remove('FileSearch-open'); + // A selection the user has abandoned is not worth a request, and a closed + // palette should leave no standing speculation behind it. + if (prefetchTimer !== null) { + clearTimeout(prefetchTimer); + prefetchTimer = null; + } + removeRule(); + if (restoreFocus && restoreFocus.focus) { + restoreFocus.focus(); + } + restoreFocus = null; + } + + function navigate(ev) { + var row = rows[selected]; + var a = row && row.a; + if (!a || !a.href || row.li.hidden) { + return; + } + if (row.path) { + recordVisit(row.path); + } + if (ev && (ev.metaKey || ev.ctrlKey)) { + window.open(a.href, '_blank'); + } else { + window.location.href = a.href; + } + } + + // --------------------------------------------------------------- prefetch + + /** + * Warms the browser cache with the highlighted result, so Enter paints from + * cache instead of waiting on a round trip. + * + * This is only worth doing because result links are SHA-pinned and therefore + * carry a real max-age; warming a no-store URL would be discarded and the + * request wasted. That is exactly why repository results are never warmed: a + * repository index page names no revision, so it is served no-store. + * + * Where the Speculation Rules API is available the warm is expressed as a + * one-URL prefetch rule, which is the mechanism built for exactly this: + * the request is labelled `Sec-Purpose: prefetch`, so an operator can see + * speculative traffic in the logs and rate-limit or refuse it, and the + * result lands in the prefetch cache the following navigation reads. + * Elsewhere a low-priority same-origin `fetch` leaves an ordinary HTTP + * cache entry instead, which the navigation also reads but which the server + * cannot tell apart from a real request. + * + * `<link rel=prefetch>` is deliberately not used. Measured in Chrome + * against a 506k-path repository, a link element warms some destinations + * and cancels others with ERR_ABORTED under this access pattern -- many + * warms on one page, no reload in between -- so it is unreliable precisely + * where the finder needs it. + * + * Three limits keep it from being rude: a debounce, so typing a path does + * not fire one request per keystroke and only a selection the user rests on + * is warmed; a cap on distinct destinations, so a long session cannot fan + * out without bound; and, on the fetch path, a dedupe set. Failures are + * ignored by construction -- a warm that does not happen costs a cache + * miss, nothing more. + */ + var PREFETCH_DELAY_MS = 250; + var PREFETCH_MAX = 32; + var RULE_ID = 'file-search-speculation'; + var currentScript = + document.currentScript || document.querySelector('script[nonce]'); + var scriptNonce = currentScript + ? currentScript.nonce || currentScript.getAttribute('nonce') || '' + : ''; + var useRules = !!( + window.HTMLScriptElement && + HTMLScriptElement.supports && + HTMLScriptElement.supports('speculationrules') + ); + var prefetched = {}; + var prefetchCount = 0; + var prefetchTimer = null; + + /** + * Falls back to fetch warming if the deployment's CSP blocks the rule set. + * + * Gitiles sets no Content-Security-Policy of its own, so the policy belongs + * to whoever deployed it and cannot be known here. A `script-src` carrying + * neither `'strict-dynamic'` nor `'inline-speculation-rules'` blocks the + * injected rule, and a blocked rule reports nothing back to the code that + * installed it: warming would simply stop while `useRules` stayed true. The + * violation event is the only signal, so take it and switch to `fetchWarm`, + * which `connect-src` governs and which therefore survives exactly the + * policy that kills the rule. + * + * Any enforced `script-src` violation on the page trips this, not only ours. + * Warming the wrong way is harmless, and a policy strict enough to block + * someone else's inline script would almost certainly have blocked the rule + * too. + */ + document.addEventListener('securitypolicyviolation', function (event) { + if ( + !useRules || + event.disposition === 'report' || + !event.violatedDirective || + event.violatedDirective.indexOf('script-src') !== 0 + ) { + return; + } + useRules = false; + removeRule(); + // The blocked rules warmed nothing, so neither the dedupe set nor the + // budget they consumed reflects a request that was actually made. + prefetched = {}; + prefetchCount = 0; + schedulePrefetch(); + }); + + /** + * Replaces the finder's speculation rule set with one naming `href`. + * + * The old script is removed rather than amended: a growing rule list would + * ask the browser to hold every destination the selection has ever passed + * over, and the cap below only bounds how many are named in total, not how + * many are live at once. + */ + function installRule(href) { + removeRule(); + var script = document.createElement('script'); + script.id = RULE_ID; + script.type = 'speculationrules'; + if (scriptNonce) { + script.setAttribute('nonce', scriptNonce); + } + script.textContent = JSON.stringify({ + prefetch: [{source: 'list', urls: [href]}], + }); + document.head.appendChild(script); + } + + function removeRule() { + var script = document.getElementById(RULE_ID); + if (script) { + script.remove(); + } + } + + function fetchWarm(href) { + // The body is read and dropped: the point is the cache entry it leaves + // behind, not the text. + fetch(href, {credentials: 'same-origin', priority: 'low'}) + .then(function (response) { + return response.text(); + }) + .catch(function () { + // A failed warm is not an error the reader needs to know about. + }); + } + + function prefetch(href) { + if (!prefetched[href]) { + if (prefetchCount >= PREFETCH_MAX) { + return; + } + prefetched[href] = true; + prefetchCount++; + } else if (!useRules) { + // The HTTP cache still holds it, so arrowing back costs nothing. + return; + } + // A rule set that is swapped out may take its prefetch with it, so a + // destination revisited later has to be named again. + if (useRules) { + installRule(href); + } else { + fetchWarm(href); + } + } + + /** Queues a warm of whatever is selected once the selection settles. */ + function schedulePrefetch() { + if (repoMode || root.hidden || (!useRules && typeof fetch !== 'function')) { + return; + } + if (prefetchTimer !== null) { + clearTimeout(prefetchTimer); + } + prefetchTimer = setTimeout(function () { + prefetchTimer = null; + if (root.hidden) { + return; + } + var row = rows[selected]; + if (row && !row.li.hidden && row.a.href) { + prefetch(row.a.href); + } + }, PREFETCH_DELAY_MS); + } + + // Leaving the page must not put an open palette into the back/forward cache: + // the browser restores the DOM verbatim, so Back would land the reader on a + // page covered by a stale overlay. Closing here rather than repairing it on + // `pageshow` means the snapshot is already clean, so there is no flash on + // restore. Result links are SHA-pinned and therefore cacheable, which is + // exactly what makes those pages bfcache-eligible. + window.addEventListener('pagehide', function () { + close(); + }); + + // ------------------------------------------------------------------ input + + input.addEventListener('input', query); + input.addEventListener('compositionstart', function () { + composing = true; + }); + input.addEventListener('compositionend', function () { + composing = false; + query(); + }); + + /** Moves the selection by `delta` rows, clamped to what is displayed. */ + function move(delta) { + if (lastRendered <= 0) { + return; + } + var next = selected + delta; + if (next < 0) { + next = 0; + } else if (next > lastRendered - 1) { + next = lastRendered - 1; + } + if (next !== selected) { + selected = next; + highlight(); + } + } + + function onKeyDown(ev) { + if (composing || ev.isComposing || ev.keyCode === 229) { + return; + } + if (ev.key === 'Escape') { + ev.preventDefault(); + close(); + } else if (ev.key === 'Tab') { + // The dialog declares itself modal, so focus must not leave it. The rows + // are not tab stops, which leaves the input as the only one, so holding + // focus is just a matter of swallowing the key. + ev.preventDefault(); + input.focus(); + } else if ( + ev.key === 'ArrowDown' || + ((ev.key === 'n' || ev.key === 'N') && ev.ctrlKey) + ) { + ev.preventDefault(); + move(1); + } else if ( + ev.key === 'ArrowUp' || + ((ev.key === 'p' || ev.key === 'P') && ev.ctrlKey) + ) { + ev.preventDefault(); + move(-1); + } else if (ev.key === 'PageDown') { + // Without preventDefault the input scrolls the document behind the modal. + ev.preventDefault(); + move(PAGE); + } else if (ev.key === 'PageUp') { + ev.preventDefault(); + move(-PAGE); + } else if (ev.key === 'Enter') { + ev.preventDefault(); + navigate(ev); + } + } + + input.addEventListener('keydown', onKeyDown); + + // A row is an anchor, so a click navigates on its own without going through + // navigate(). Record it here or clicking would be remembered differently + // from pressing Enter on the same row. + list.addEventListener('click', function (ev) { + var li = ev.target.closest ? ev.target.closest('.FileSearch-row') : null; + if (!li) { + return; + } + for (var i = 0; i < LIMIT; i++) { + if (rows[i].li === li && rows[i].path) { + recordVisit(rows[i].path); + return; + } + } + }); + + list.addEventListener('mousemove', function (ev) { + var li = ev.target.closest ? ev.target.closest('.FileSearch-row') : null; + if (!li) { + return; + } + for (var i = 0; i < LIMIT; i++) { + if (rows[i].li === li && selected !== i) { + selected = i; + highlight(); + return; + } + } + }); + + root.addEventListener('mousedown', function (ev) { + // Clicking the backdrop dismisses; clicking inside the modal must not, + // and must not blur the input unless the click is on a result link. + if (ev.target === root || ev.target.classList.contains('FileSearch-backdrop')) { + close(); + } else if ( + ev.target !== input && + (!ev.target.closest || !ev.target.closest('.FileSearch-link')) + ) { + ev.preventDefault(); + input.focus(); + } + }); + + // ------------------------------------------------------------- global key + + function isEditable(el) { + if (!el) { + return false; + } + var tag = el.tagName; + return tag === 'INPUT' || tag === 'TEXTAREA' || tag === 'SELECT' || el.isContentEditable; + } + + document.addEventListener('keydown', function (ev) { + if (!root.hidden) { + if (ev.target !== input && document.activeElement !== input) { + onKeyDown(ev); + } + return; + } + if (ev.key !== '/' || ev.metaKey || ev.ctrlKey || ev.altKey) { + return; + } + if (isEditable(document.activeElement)) { + return; + } + // Firefox binds "/" to Quick Find; take it over. + ev.preventDefault(); + open(); + }); + + if (trigger) { + trigger.addEventListener('click', function (ev) { + ev.preventDefault(); + open(); + }); + } +})();
diff --git a/resources/com/google/gitiles/templates/Common.soy b/resources/com/google/gitiles/templates/Common.soy index 0aca3dc..e335ae0 100644 --- a/resources/com/google/gitiles/templates/Common.soy +++ b/resources/com/google/gitiles/templates/Common.soy
@@ -74,10 +74,12 @@ {/for} {sp} {/if} + {call fileSearchTrigger /} {call themeToggle /} </div> </div> </header> + {call fileSearch /} <div class="Site-content"> <div class="Container {if $containerClass}{$containerClass}{/if}"> @@ -116,6 +118,65 @@ {/template} /** + * Trigger for the finder, shown in the header menu. + * + * Renders nothing unless there is something to find: a revision with a tree, + * which SEARCH_TREE_URL being present signals, or a host index, which lists + * repositories instead. + */ +{template fileSearchTrigger} + {@inject? SEARCH_TREE_URL: string|null} + {@inject? SEARCH_REPOSITORIES: bool|null} +{if $SEARCH_TREE_URL or $SEARCH_REPOSITORIES} + {let $label: $SEARCH_REPOSITORIES ? 'Find repository' : 'Find file' /} +<button class="Header-menuItem FileSearch-trigger" type="button" title="{$label} (press /)" aria-label="{$label}"> + <span class="FileSearch-triggerKey" aria-hidden="true">/</span> + <span class="FileSearch-triggerLabel">{$label}</span> +</button> +{/if} +{/template} + +/** + * Finder overlay. + * + * The markup is inert until file-search.js runs. In file mode the index is + * fetched on first open rather than on page load, so a reader who never + * searches costs the server nothing. In repository mode nothing is fetched at + * all: the host index page already lists every repository, and the script + * reads them out of the document. + * + * Kept strict-html, unlike {@code header}, so that strict-html templates such + * as {@code Doc.soy} can call it directly; Soy's content security policy pass + * annotates the script tag with {@code $ij.csp_nonce} when the request carries + * a nonce. + */ +{template fileSearch} + {@inject? SEARCH_TREE_URL: string|null} + {@inject? SEARCH_REPOSITORIES: bool|null} + {@inject staticUrls: ?} +{if $SEARCH_TREE_URL or $SEARCH_REPOSITORIES} + {let $dialogLabel: $SEARCH_TREE_URL ? 'Find file' : 'Find repository' /} + {let $inputLabel: $SEARCH_TREE_URL ? 'Find a file by path' : 'Find a repository by name' /} +<div id="file-search" class="FileSearch" hidden + data-kind="{if $SEARCH_TREE_URL}files{else}repositories{/if}" + {if $SEARCH_TREE_URL}data-tree-url="{$SEARCH_TREE_URL}"{/if} + data-worker-url="{$staticUrls.FILE_SEARCH_WORKER_JS_URL}"> + <div class="FileSearch-backdrop"></div> + <div class="FileSearch-modal" role="dialog" aria-modal="true" aria-label="{$dialogLabel}"> + <input class="FileSearch-input" type="text" role="combobox" aria-expanded="true" + aria-autocomplete="list" autocomplete="off" autocorrect="off" + autocapitalize="off" spellcheck="false" placeholder="{$inputLabel}" + aria-label="{$inputLabel}" aria-controls="file-search-results"> + <div class="FileSearch-status" role="status" aria-live="polite"></div> + <ul class="FileSearch-results" id="file-search-results" role="listbox" + aria-label="{$dialogLabel}"></ul> + </div> +</div> +<script src="{$staticUrls.FILE_SEARCH_JS_URL}" defer></script> +{/if} +{/template} + +/** * Default (empty) custom head tag part * * This can be used to include per-project CSS/JS by
diff --git a/resources/com/google/gitiles/templates/Doc.soy b/resources/com/google/gitiles/templates/Doc.soy index fab786b..5551daf 100644 --- a/resources/com/google/gitiles/templates/Doc.soy +++ b/resources/com/google/gitiles/templates/Doc.soy
@@ -80,6 +80,7 @@ {if $homeUrl}</a>{/if} </div> <div class="Header-menu"> + {call common.fileSearchTrigger /} {call common.themeToggle /} </div> </div> @@ -89,6 +90,7 @@ </nav> {/if} </header> + {call common.fileSearch /} <div class="Site-content Site-Content--markdown"> <div class="Container"> <div class="doc">
diff --git a/resources/com/google/gitiles/templates/HostIndex.soy b/resources/com/google/gitiles/templates/HostIndex.soy index 353fd4f..ea23b5f 100644 --- a/resources/com/google/gitiles/templates/HostIndex.soy +++ b/resources/com/google/gitiles/templates/HostIndex.soy
@@ -42,6 +42,10 @@ </h1> {/if} + // file-search.js reads this list to answer "/" on a host index, rather than + // fetching the same names a second time. It looks for RepoList-item anchors + // and their RepoList-itemName and RepoList-itemDescription children, so + // those class names are a contract, not just styling hooks. <div class="RepoList"> <div class="RepoList-item RepoList-item--header"> <span class="RepoList-itemName">