MD Settings: First iteration of searching within settings.

chrome/browser/resources/settings/search_settings.js

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+cr.define('settings', function() {
+  /** @const {string} */
+  var WRAPPER_CSS_CLASS = 'search-highlight-wrapper';
+
+  /** @const {string} */
+  var HIT_CSS_CLASS = 'search-highlight-hit';
+
+  /** @const {!RegExp} */
+  var SANITIZE_REGEX = /[-[\]{}()*+?.,\\^$|#\s]/g;
+
+  /**
+   * Finds all previous highlighted nodes under |node| (both within self and
+   * children's Shadow DOM) and removes the highlight.
+   * @param {!Node} node
+   * @private
+   */
+  function findAndRemoveHighligts_(node) {
+    removeHighlightUi_(node.shadowRoot);
+
+    // Finds all descendants of |node| that have their own Shadow DOM. It
+    // does NOT pierce through the Shadow DOM boundary (which is why
+    // |findAndRemoveHighligts_| has to be called recursively.
+    var children = [];
+    var walker = document.createTreeWalker(
+        node.shadowRoot, NodeFilter.SHOW_ELEMENT, null, false);
+    var currentNode = null;
+    while ((currentNode = walker.nextNode()) !== null) {
+      if (!!currentNode.shadowRoot)
+        children.push(currentNode);
+    }
+
+    children.forEach(findAndRemoveHighligts_);
+  }
+
+  /**
+   * Applies the highlight UI (yellow rectangle) around all matches in |node|.
+   * param {!Node} node The text node to be highlighted. |node| ends up being
+   * removed from the DOM tree.
+   * @param {!Array<string>} tokens The string tokens that did not match.
+   * @private
+   */
+  function applyHighlightUi_(node, tokens) {
+    var wrapper = document.createElement('span');
+    wrapper.classList.add(WRAPPER_CSS_CLASS);
+    // Use existing node as placeholder to determine where to insert the
+    // replacement content.
+    node.parentNode.insertBefore(wrapper, node);
+
+    for (var i = 0; i < tokens.length; ++i) {
+      if (i % 2 == 0) {
+        wrapper.appendChild(document.createTextNode(tokens[i]));
+      } else {
+        var span = document.createElement('span');
+        span.classList.add(HIT_CSS_CLASS);
+        span.style['background-color'] = 'yellow';
+        span.textContent = tokens[i];
+        wrapper.appendChild(span);
+      }
+    }
+
+    node.remove();
+  }
+
+  /**
+   * Removes highlight UI (yellow rectangle) from previous matches in the given
+   * element and descendants. It does NOT pierce through Shadow DOM.
+   * @param {!Element} element
+   * @private
+   */
+  function removeHighlightUi_(element) {
+    var wrappers = element.querySelectorAll('.' + WRAPPER_CSS_CLASS);
+    for (var i = 0; i < wrappers.length; i++) {
+      var wrapper = wrappers[i];
+      var hitElements = wrapper.querySelectorAll('.' + HIT_CSS_CLASS);
+      // For each hit element, remove the highlighting.
+      for (var j = 0; j < hitElements.length; j++) {
+        var hitElement = hitElements[j];
+        wrapper.replaceChild(hitElement.firstChild, hitElement);
+      }
+
+      // Normalize so that adjacent text nodes will be combined.
+      wrapper.normalize();
+      // Restore the DOM structure as it was before the search occurred.
+      if (wrapper.previousSibling)
+        wrapper.textContent = ' ' + wrapper.textContent;
+      if (wrapper.nextSibling)
+        wrapper.textContent = wrapper.textContent + ' ';
+
+      wrapper.parentElement.insertBefore(
+          wrapper.firstChild, wrapper.nextSibling);
+
+      wrapper.remove();
+    }
+  }
+
+  /**
+   * Traverses the entire DOM (including Shadow DOM), finds text nodes that
+   * match the giver regular expression and applies the highlight UI. It also
+   * ensures that <settings-section> instances become visible if any matches
+   * occurred under their subtree.
+   *
+   * @param {!Element} page The page to be searched, should be either
+   *     <settings-basic-page> or <settings-advanced-page>.
+   * @param {!RegExp} regExp The regular expression to detect matches.
+   * @private
+   */
+  function findAndHighlightMatches_(page, regExp) {
+    var walker = new ShadowDomTreeWalker(page);
+    var node = walker.nextNode();
+    while (node !== null) {
+      var textContent = node.nodeValue.trim();
+      if (!regExp.test(textContent)) {
+        node = walker.nextNode();
+        continue;
+      }
+
+      // Find corresponding SETTINGS-SECTION parent and make it visible.
+      var parent = node;
+      while (!!parent && parent.tagName !== 'SETTINGS-SECTION') {
+        parent = parent.nodeType == Node.DOCUMENT_FRAGMENT_NODE ?
+            parent.host : parent.parentNode;
+      }
+      if (!!parent)
+        parent.style.display = '';
+
+      var nextNode = walker.nextNode();
+      applyHighlightUi_(node, textContent.split(regExp));
+      node = nextNode;
+    }
+  }
+
+  /**
+   * @param {!Element} page
+   * @param {boolean} visible
+   * @private
+   */
+  function setSectionsVisibility_(page, visible) {
+    var sections = Polymer.dom(page.root).querySelectorAll('settings-section');
+    for (var i = 0; i < sections.length; i++)
+      sections[i].style.display = visible ? '' : 'none';
+  }
+
+  /**
+   * Performs hierarchical search, starting at the given page element.
+   * @param {string} text
+   * @param {!Element} page Must be either <settings-basic-page> or
+   *     <settings-advanced-page>.
+   */
+  function search(text, page) {
+    findAndRemoveHighligts_(page);
+
+    // Generate search text by applying lowercase and escaping any characters
+    // that would be problematic for regular expressions.
+    var searchText = text.trim().toLowerCase().replace(SANITIZE_REGEX, '\\$&');
+    if (searchText.length == 0) {
+      setSectionsVisibility_(page, true);
+      return;
+    }
+
+    setSectionsVisibility_(page, false);
+    findAndHighlightMatches_(page, new RegExp('(' + searchText + ')', 'i'));
+  }
+
+  /**
+   * A utility class for navigating all text nodes in a DOM tree taking into
+   * account Shadow DOM nodes. The native TreeWalker does not traverse Shadow
+   * DOM.
+   * @constructor
+   *
+   * Example usage:
+   *
+   * var walker = new ShadowDomTreeWalker(myElememt);
+   * var node = null;
+   * while ((node = walker.nextNode()) !== null) {
+   *   // |node| is of type Node.TEXT_NODE.
+   *   // Do something with |node| here.
+   * }
+   *
+   * @param {!Node} node The root of the DOM tree to be traversed.
+   */
+  function ShadowDomTreeWalker(node) {
+    /** @private {!Array<!TreeWalker>} */
+    this.walkers_ = [];
+
+    /** @private {!NodeFilter} */
+    this.nodeFilter_ = /** @type {!NodeFilter} */ (
+        {acceptNode: this.filterFn_.bind(this)});
+
+    if (!!node.shadowRoot)
+      this.addWalker_(node.shadowRoot);
+    this.addWalker_(node);
+  }
+
+  /**
+   * List of elements types that should not be searched at all.
+   * @const {!Set<string>}
+   * @private
+   */
+  ShadowDomTreeWalker.IGNORED_ELEMENTS_ = new Set([
+    'CONTENT',
+    'CR-EVENTS',
+    'IMG',
+    'IRON-ICON',
+    'PAPER-ICON-BUTTON',
+    /* TODO(dpapad): paper-item is used for dynamically populated dropdown
+     * menus. Perhaps a better approach is to mark the entire dropdown menu such
+     * that search algorithm can skip it as a whole instead.
+     */
+    'PAPER-ITEM',
+    'PAPER-RIPPLE',
+    'STYLE',
+    'TEMPLATE',
+  ]);
+
+  ShadowDomTreeWalker.prototype = {
+    /**
+     * Adds a TreeWalker instance to the queue for the given |node|.
+     * @param {!Node} node
+     * @private
+     */
+    addWalker_: function(node) {
+      this.walkers_.push(
+          document.createTreeWalker(
+              node, NodeFilter.SHOW_ALL, this.nodeFilter_, false));

[Dan Beam, 2016/06/30 16:33:17]

according to esprehn@, if we're doing SHOW_ALL or SHOW_ELEMENT | SHOW_TEXT (it's
a bitmask, btw), we're not really gaining much by using a walker -- just adding
memory overhead

in my testing, I could not produce a slower recursive, pure JS + DOM version:
https://gist.github.com/danbeam/83a60be46c72ae57dd9bcc18bddc0e50

I put this in settings.js so it wasn't being eval()'d from the console (I've
heard v8 wont optimize that), and run it in quite a few different configurations
(NUM_TESTS = 1 so less JIT optimizations, NUM_TESTS=100, NUM_TESTS=1 but with a
ton of independently scheduled setTimeout()s, etc.).

I'm really tempted to just write recursive or iterative JS + DOM if it
simplifies things.

[dpapad, 2016/06/30 17:32:57]

Whether it simplifies things, is questionable, until we figure out how can the
recursive version be asyncified. I have already done this at
https://codereview.chromium.org/2103133007 for the iterative (Walker) version.
It is not clear to me if recursive approach simplifies things, and I would need
probably another day to try CL 2103133007 with recursive version.

Let me know if you think this is time well spent.

[dpapad, 2016/06/30 21:27:44]

I've updated this CL to traverse the DOM in a pure JS recursive manner, removed
ShadowDomTreeWalker helper class.

+    },
+
+    /**
+     * @return {?Node} The next text node in the DOM tree, or null if the end of
+     *     the traversal is reached.
+     */
+    nextNode: function() {
+      if (this.walkers_.length == 0)
+        return null;
+
+      var node = null;
+      do {
+        // Processing walkers in a FIFO order because it simplifies the code.
+        // The order of traversal is not important (unlike native TreeWalker),
+        // the only important invariant is to ensure that all nodes in the DOM
+        // tree are traversed.
+        var activeWalker = this.walkers_[0];
+        node = activeWalker.nextNode();
+        if (node === null) {
+          this.walkers_.splice(0, 1);
+        } else if (!!node.shadowRoot) {
+          // Adding TreeWalker for shadow root, if it exists, because shadowRoot
+          // is invisible from the normal root TreeWalker.
+          this.addWalker_(node.shadowRoot);
+        }
+      } while (node === null && this.walkers_.length > 0);
+
+      if (node !== null && node.nodeType != Node.TEXT_NODE) {
+        return this.nextNode();
+      }
+
+      return node;
+    },
+
+    /**
+     * @param {!Node} node
+     * @return {number}
+     */
+    filterFn_: function(node) {
+      if (ShadowDomTreeWalker.IGNORED_ELEMENTS_.has(node.tagName))
+        return NodeFilter.FILTER_REJECT;
+
+      if (node.nodeType == Node.TEXT_NODE && node.nodeValue.trim() == 0)
+        return NodeFilter.FILTER_REJECT;
+
+      return NodeFilter.FILTER_ACCEPT;
+    },
+  };
+
+  return {
+    search: search,
+  };
+});