pw_docs: Add inline search to sidebar

Change-Id: I2edd8ba08f96708f5863f0de0981688122064d8d
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/207674
Lint: Lint 🤖 <android-build-ayeaye@system.gserviceaccount.com>
Commit-Queue: Asad Memon <asadmemon@google.com>
Reviewed-by: Chad Norvell <chadnorvell@google.com>
diff --git a/docs/conf.py b/docs/conf.py
index 7a229c2..d6a1c66 100644
--- a/docs/conf.py
+++ b/docs/conf.py
@@ -40,21 +40,22 @@
 pygments_dark_style = 'pw_console.pigweed_code_style.PigweedCodeStyle'
 
 extensions = [
-    'pw_docgen.sphinx.google_analytics',  # Enables optional Google Analytics
-    'pw_docgen.sphinx.kconfig',
-    'pw_docgen.sphinx.module_metadata',
-    'pw_docgen.sphinx.pigweed_live',
-    'pw_docgen.sphinx.pw_status_codes',
-    'pw_docgen.sphinx.seed_metadata',
-    'sphinx.ext.autodoc',  # Automatic documentation for Python code
-    'sphinx.ext.napoleon',  # Parses Google-style docstrings
-    'sphinxarg.ext',  # Automatic documentation of Python argparse
-    'sphinxcontrib.mermaid',
-    'sphinx_design',
-    'breathe',
-    'sphinx_copybutton',  # Copy-to-clipboard button on code blocks
-    'sphinx_reredirects',
-    'sphinx_sitemap',
+    "pw_docgen.sphinx.google_analytics",  # Enables optional Google Analytics
+    "pw_docgen.sphinx.kconfig",
+    "pw_docgen.sphinx.module_metadata",
+    "pw_docgen.sphinx.pigweed_live",
+    "pw_docgen.sphinx.pw_status_codes",
+    "pw_docgen.sphinx.inlinesearch",
+    "pw_docgen.sphinx.seed_metadata",
+    "sphinx.ext.autodoc",  # Automatic documentation for Python code
+    "sphinx.ext.napoleon",  # Parses Google-style docstrings
+    "sphinxarg.ext",  # Automatic documentation of Python argparse
+    "sphinxcontrib.mermaid",
+    "sphinx_design",
+    "breathe",
+    "sphinx_copybutton",  # Copy-to-clipboard button on code blocks
+    "sphinx_reredirects",
+    "sphinx_sitemap",
 ]
 
 # When a user clicks the copy-to-clipboard button the `$ ` prompt should not be
@@ -108,14 +109,18 @@
 # These paths are either relative to html_static_path
 # or fully qualified paths (eg. https://...)
 html_css_files = [
-    'css/pigweed.css',
+    "css/pigweed.css",
     # Needed for Inconsolata font.
-    'https://fonts.googleapis.com/css2?family=Inconsolata&display=swap',
+    "https://fonts.googleapis.com/css2?family=Inconsolata&display=swap",
     # FontAwesome for mermaid and sphinx-design
     "https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.4/css/all.min.css",
 ]
 
-html_js_files = ['js/pigweed.js']
+html_js_files = [
+    "js/pigweed.js",
+    # Needed for sidebar search
+    "https://cdnjs.cloudflare.com/ajax/libs/fuzzysort/2.0.4/fuzzysort.js",
+]
 
 # Furo color theme variables based on:
 # https://github.com/pradyunsg/furo/blob/main/src/furo/assets/styles/variables/_colors.scss
diff --git a/pw_docgen/py/BUILD.gn b/pw_docgen/py/BUILD.gn
index 6f4ca68..0aee933 100644
--- a/pw_docgen/py/BUILD.gn
+++ b/pw_docgen/py/BUILD.gn
@@ -28,6 +28,7 @@
     "pw_docgen/seed.py",
     "pw_docgen/sphinx/__init__.py",
     "pw_docgen/sphinx/google_analytics.py",
+    "pw_docgen/sphinx/inlinesearch/__init__.py",
     "pw_docgen/sphinx/kconfig.py",
     "pw_docgen/sphinx/module_metadata.py",
     "pw_docgen/sphinx/pigweed_live.py",
diff --git a/pw_docgen/py/pw_docgen/sphinx/inlinesearch/__init__.py b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/__init__.py
new file mode 100644
index 0000000..32a3a36
--- /dev/null
+++ b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/__init__.py
@@ -0,0 +1,84 @@
+# Copyright 2024 The Pigweed Authors
+#
+# 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
+#
+#     https://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.
+"""Build index to be used in the sidebar search input"""
+
+import os
+from os.path import dirname, join, exists
+import json
+import sphinx.search
+from sphinx.util.osutil import copyfile
+from sphinx.jinja2glue import SphinxFileSystemLoader
+
+
+class IndexBuilder(sphinx.search.IndexBuilder):
+    def freeze(self):
+        """Create a usable data structure for serializing."""
+        data = super().freeze()
+        try:
+            # Sphinx >= 1.5 format
+            # Due to changes from github.com/sphinx-doc/sphinx/pull/2454
+            base_file_names = data["docnames"]
+        except KeyError:
+            # Sphinx < 1.5 format
+            base_file_names = data["filenames"]
+
+        store = {
+            "docnames": base_file_names,
+            "titles": data["titles"],
+        }
+        index_dest = join(self.env.app.outdir, "sidebarindex.js")
+        f = open(index_dest, "w")
+        f.write("var SidebarSearchIndex=" + json.dumps(store))
+        f.close()
+        return data
+
+
+def builder_inited(app):
+    # adding a new loader to the template system puts our searchbox.html
+    # template in front of the others, it overrides whatever searchbox.html
+    # the current theme is using.
+    # it's still up to the theme to actually _use_ a file called searchbox.html
+    # somewhere in its layout. but the base theme and pretty much everything
+    # else that inherits from it uses this filename.
+    app.builder.templates.loaders.insert(
+        0, SphinxFileSystemLoader(dirname(__file__))
+    )
+
+
+def copy_static_files(app, _):
+    # because we're using the extension system instead of the theme system,
+    # it's our responsibility to copy over static files outselves.
+    files = ["js/searchbox.js", "css/searchbox.css"]
+    for f in files:
+        src = join(dirname(__file__), f)
+        dest = join(app.outdir, "_static", f)
+        if not exists(dirname(dest)):
+            os.makedirs(dirname(dest))
+        copyfile(src, dest)
+
+
+def setup(app):
+    # adds <script> and <link> to each of the generated pages to load these
+    # files.
+    app.add_css_file("css/searchbox.css")
+    app.add_js_file("js/searchbox.js")
+
+    app.connect("builder-inited", builder_inited)
+    app.connect("build-finished", copy_static_files)
+
+    sphinx.search.IndexBuilder = IndexBuilder
+    return {
+        "parallel_read_safe": True,
+        "parallel_write_safe": True,
+    }
diff --git a/pw_docgen/py/pw_docgen/sphinx/inlinesearch/css/searchbox.css b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/css/searchbox.css
new file mode 100644
index 0000000..1d87cdf
--- /dev/null
+++ b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/css/searchbox.css
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2024 The Pigweed Authors
+ *
+ * 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
+ *
+ *     https://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.
+ */
+.sidebar-search-container {
+  position: relative;
+}
+
+.sidebar-search-container .results {
+  display: none;
+  position: absolute;
+  top: 35px;
+  left: 0;
+  right: 0;
+  z-index: 10;
+  padding: 0;
+  margin: 0;
+  font-size: 14px;
+  text-align: left;
+  border-width: 1px;
+  border-style: solid;
+  border-color: #cbcfe2 #c8cee7 #c4c7d7;
+  border-radius: 3px;
+  background-color: var(--color-background-secondary);
+  -webkit-box-shadow: 0 1px 2px rgba(0, 0, 0, 0.1);
+  -moz-box-shadow: 0 1px 2px rgba(0, 0, 0, 0.1);
+  -ms-box-shadow: 0 1px 2px rgba(0, 0, 0, 0.1);
+  -o-box-shadow: 0 1px 2px rgba(0, 0, 0, 0.1);
+  box-shadow: 0 1px 2px rgba(0, 0, 0, 0.1);
+}
+
+.sidebar-search-container .results li {
+  display: block
+}
+
+.sidebar-search-container .results li:first-child {
+  margin-top: -1px
+}
+
+.sidebar-search-container .results li:first-child:before,
+.sidebar-search-container .results li:first-child:after {
+  display: block;
+  content: '';
+  width: 0;
+  height: 0;
+  position: absolute;
+  left: 50%;
+  margin-left: -5px;
+  border: 5px outset transparent;
+}
+
+.sidebar-search-container .results li:first-child:before {
+  border-bottom: 5px solid #c4c7d7;
+  top: -11px;
+}
+
+.sidebar-search-container .results li:first-child:after {
+  border-bottom: 5px solid #fdfdfd;
+  top: -10px;
+}
+
+.sidebar-search-container .results li:first-child.hover:before,
+.sidebar-search-container .results li:first-child.hover:after {
+  display: none
+}
+
+.sidebar-search-container .results li:last-child {
+  margin-bottom: -1px
+}
+
+.sidebar-search-container .results a {
+  display: flex;
+  flex-direction: column;
+  position: relative;
+  margin: 0 -1px;
+  padding: 6px 40px 6px 10px;
+  color: var(--color-foreground-secondary);
+  font-weight: 500;
+  text-decoration: none;
+  border: 1px solid transparent;
+  border-radius: 3px;
+}
+
+.sidebar-search-container .results a span {
+  margin: 0.3rem 0rem;
+}
+
+.sidebar-search-container .results a span b {
+  font-weight: 900;
+  color: var(--color-sidebar-brand-text);
+}
+
+.sidebar-search-container .results a small {
+  font-family: var(--font-stack--monospace);
+}
+
+.sidebar-search-container .results a:before {
+  content: '';
+  width: 18px;
+  height: 18px;
+  position: absolute;
+  top: 50%;
+  right: 10px;
+  margin-top: -9px;
+}
+
+.sidebar-search-container .results a.hover {
+  text-decoration: none;
+  background-color: var(--sd-color-card-border-hover);
+  color: var(--color-foreground-primary);
+}
+
+body[data-theme=light] .sidebar-search-container .results a.hover {
+  color: var(--color-highlight-on-target);
+}
+:-moz-placeholder {
+  color: #a7aabc;
+  font-weight: 200;
+}
+
+::-webkit-input-placeholder {
+  color: #a7aabc;
+  font-weight: 200;
+}
diff --git a/pw_docgen/py/pw_docgen/sphinx/inlinesearch/js/searchbox.js b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/js/searchbox.js
new file mode 100644
index 0000000..658868f
--- /dev/null
+++ b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/js/searchbox.js
@@ -0,0 +1,153 @@
+// Copyright 2024 The Pigweed Authors
+//
+// 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
+//
+//     https://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.
+
+document.addEventListener('DOMContentLoaded', () => {
+  'use strict';
+
+  const searchModule = function () {
+    let index = [];
+    const highlight = document.querySelector('#ls-highlight').value === 'true';
+    // First we add all page titles
+    const SidebarSearchIndex = window.SidebarSearchIndex;
+    SidebarSearchIndex.titles.forEach((title, docIndex) => {
+      let doc = SidebarSearchIndex.docnames[docIndex];
+      if (doc.endsWith('/doc')) doc = doc.slice(0, -3);
+      index.push({
+        title: title,
+        doc: doc,
+        hash: '',
+      });
+    });
+
+    const searchField = document.querySelector('#ls_search-field');
+    const searchResults = document.querySelector('#ls_search-results');
+
+    searchField.addEventListener('keyup', onKeyUp);
+    searchField.addEventListener('keypress', onKeyPress);
+    searchField.addEventListener('focusout', () => {
+      setTimeout(() => {
+        searchResults.style.display = 'none';
+      }, 100);
+    });
+    searchField.addEventListener('focusin', () => {
+      if (searchResults.querySelectorAll('li').length > 0) {
+        searchResults.style.display = 'block';
+      }
+    });
+
+    function onKeyUp(event) {
+      const keycode = event.keyCode || event.which;
+      const query = searchField.value;
+      let results = null;
+
+      if (keycode === 13) {
+        return;
+      }
+      if (keycode === 40 || keycode === 38) {
+        handleKeyboardNavigation(keycode);
+        return;
+      }
+      if (query === '') {
+        searchResults.innerHTML = '';
+        searchResults.style.display = 'none';
+        return;
+      }
+
+      results = window.fuzzysort.go(query, index, { key: 'title' });
+      searchResults.innerHTML = '';
+      searchResults.style.display = 'block';
+
+      if (results.length === 0) {
+        searchResults.innerHTML = '<li><a href="#">No results found</a></li>';
+      } else {
+        results.slice(0, 15).forEach((result) => {
+          searchResults.appendChild(createResultListElement(result));
+        });
+      }
+
+      // Set the width of the dropdown
+      searchResults.style.width =
+        Math.max(
+          searchField.offsetWidth,
+          Array.from(searchResults.children).reduce(
+            (max, child) => Math.max(max, child.offsetWidth),
+            0,
+          ) + 20,
+        ) + 'px';
+    }
+
+    function onKeyPress(event) {
+      if (event.keyCode === 13) {
+        event.preventDefault();
+        const active = searchResults.querySelector('li a.hover');
+        if (active) {
+          active.click();
+        } else {
+          window.location.href = `${window.DOCUMENTATION_OPTIONS.URL_ROOT}search.html?q=${searchField.value}&check_keywords=yes&area=default`;
+        }
+      }
+    }
+
+    function handleKeyboardNavigation(keycode) {
+      const items = Array.from(searchResults.querySelectorAll('li a'));
+      const activeIndex = items.findIndex((item) =>
+        item.classList.contains('hover'),
+      );
+
+      if (keycode === 40 && activeIndex < items.length - 1) {
+        // next
+        if (activeIndex > -1) items[activeIndex].classList.remove('hover');
+        items[activeIndex + 1].classList.add('hover');
+      } else if (keycode === 38 && activeIndex > 0) {
+        // prev
+        items[activeIndex].classList.remove('hover');
+        items[activeIndex - 1].classList.add('hover');
+      }
+    }
+
+    function buildHref(s) {
+      const highlightString = highlight
+        ? `?highlight=${encodeURIComponent(s.title || s.heading)}`
+        : '';
+      return `${window.DOCUMENTATION_OPTIONS.URL_ROOT}${s.doc}${window.DOCUMENTATION_OPTIONS.FILE_SUFFIX}${highlightString}#${s.hash}`;
+    }
+
+    function createResultListElement(s) {
+      const li = document.createElement('li');
+      const a = document.createElement('a');
+      a.href = buildHref(s.obj);
+      // create content
+      const span = document.createElement('span');
+      span.innerHTML = window.fuzzysort.highlight(s);
+      const small = document.createElement('small');
+      small.textContent = `${s.obj.doc}${window.DOCUMENTATION_OPTIONS.FILE_SUFFIX}`;
+      a.appendChild(span);
+      a.appendChild(small);
+
+      a.addEventListener('mouseenter', () => {
+        Array.from(searchResults.querySelectorAll('li a')).forEach((el) =>
+          el.classList.remove('hover'),
+        );
+        a.classList.add('hover');
+      });
+      a.addEventListener('mouseleave', () => {
+        a.classList.remove('hover');
+      });
+      li.appendChild(a);
+      return li;
+    }
+  };
+
+  searchModule();
+});
diff --git a/pw_docgen/py/pw_docgen/sphinx/inlinesearch/sidebar/search.html b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/sidebar/search.html
new file mode 100644
index 0000000..82589de
--- /dev/null
+++ b/pw_docgen/py/pw_docgen/sphinx/inlinesearch/sidebar/search.html
@@ -0,0 +1,24 @@
+<!--
+Copyright 2024 The Pigweed Authors
+
+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
+
+    https://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.
+-->
+<script src="{{ pathto('sidebarindex.js', 1) }}" type="text/javascript"></script>
+
+<form class="sidebar-search-container" action="" method="get" autocomplete="off">
+  <input type="hidden" name="check_keywords" value="yes" />
+  <input type="hidden" name="area" value="default" />
+  <input type="hidden" id="ls-highlight" value="true" />
+  <input type="text" class="sidebar-search" id="ls_search-field" name="q" placeholder="Search" />
+  <ul class="results" id="ls_search-results"></ul>
+</form>