MD Settings: First iteration of searching within settings.

chrome/browser/resources/settings/search_settings.js

Index: chrome/browser/resources/settings/search_settings.js
diff --git a/chrome/browser/resources/settings/search_settings.js b/chrome/browser/resources/settings/search_settings.js
new file mode 100644
index 0000000000000000000000000000000000000000..edb7c3c3ea3f1ed6df2de6a57a1aacc22a3369c1
--- /dev/null
+++ b/chrome/browser/resources/settings/search_settings.js
@@ -0,0 +1,211 @@
+// 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;
+
+  /**
+   * List of elements types that should not be searched at all.
+   * @const {!Set<string>}
+   */
+  IGNORED_ELEMENTS = new Set([

[Dan Beam, 2016/07/01 00:54:55]

nit: var IGNORED_ELEMENTS

[dpapad, 2016/07/01 18:08:43]

Oops, done.

+    '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',
+  ]);
+
+
+  /**
+   * 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(

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

I am still using TreeWalker for removing highlights here, because it seems
faster than the recursive version. I kept the recursive version around if you
want to verify timings, just replace the contents of this function with
http://pastebin.com/jrWF82q4.

[Dan Beam, 2016/07/01 00:54:55]

can we use queryEffectiveChildren('.search-highlight-hit,
.search-hightlight-wrapper') instead?
https://www.polymer-project.org/1.0/docs/devguide/local-dom#light-dom-children

[dpapad, 2016/07/01 18:08:43]

search-highlight-hit and search-hightlight-wrapper classes are only needed
inside removeHighlightUi_() method, not here. Here we need to start a new search
every time a shadoRoot is encountered, so I don't fully understand your
suggestion.

In general, I'd like to avoid using Polymer helper functions in favor of native
functions, since Polymer helpers mostly provide a cross-compatibility layer for
Shady and Shadow DOM, which we don't need.

+        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 given 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) {
+    function doSearch(node) {
+      if (IGNORED_ELEMENTS.has(node.tagName))

[Dan Beam, 2016/07/01 00:54:55]

esprehn@ recommended just doing:

function ignoreNode(node) {
  var nodeName = node.nodeName;
  return nodeName == 'CONTENT' || nodeName == 'CR-EVENTS' ...;
}

[dpapad, 2016/07/01 18:08:43]

Looking up whether an item exists in a Set is advertized as O(1). The compound
OR statement seems like a linear search. Am I missing something? Perhaps this is
a question for @esprehn. I would like to know more before removing the Set usage
here.

+        return;
+
+      if (node.nodeType == Node.TEXT_NODE) {
+        var textContent = node.nodeValue.trim();
+        if (textContent.length == 0)
+          return;
+        if (regExp.test(textContent)) {

[Dan Beam, 2016/07/01 00:54:55]

it's not clear to me whether we should be using regexp or indexOf() but in this
case I'm fairly sure that using regexp makes the code simpler (and I can't prove
the performance diff)

+          revealParentSection_(node);
+          applyHighlightUi_(node, textContent.split(regExp));

[Dan Beam, 2016/07/01 00:54:55]

ah, if we use regex we don't have to make as many case-converted copies.  that's
an advantage

[dpapad, 2016/07/01 18:08:43]

True.

+          return;
+        }
+      }
+
+      var childNodes = node.childNodes;
+      for (var i = 0, length = childNodes.length; i < length; ++i) {
+        doSearch(childNodes[i]);

[Dan Beam, 2016/07/01 00:54:55]

esprehn said using
https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSibling might be
faster, i.e.

  var child = node.firstChild;
  while (child !== null) {
    doSearch(child);
    child = child.nextSibling;
  }

[dpapad, 2016/07/01 18:08:43]

Done. There was a subtlety here though. If there is a hit |child| is being
removed from the DOM inside doSearch(), and is being replaced by a new node.
Therefore, calling nextSibling after |child| has been removed from the DOM is
not correct (always returns null). But, since TEXT_NODE nodes never have
children, and we only replace TEXT_NODE nodes in the DOM, calling nextSibling
after doSearch() is fine. I added an early return statement few lines above,
since for TEXT_NODES we don't even need to get here.

[dpapad, 2016/07/01 18:21:11]

Fixed subtlety at patchset 7. TEXT_NODE still have siblings, so my reasoning
above was partially wrong (need to call nextSibling before doSearch()).

+      }
+
+      var shadowRoot = node.shadowRoot;
+      if (shadowRoot)
+        doSearch(shadowRoot);
+    }
+
+    doSearch(page);
+  }
+
+  /**
+   * Finds and makes visible the <settings-section> parent of |node|.
+   * @param {!Node} node
+   */
+  function revealParentSection_(node) {
+    // 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;

[Dan Beam, 2016/07/01 00:54:55]

worth using domHost?
https://www.polymer-project.org/1.0/docs/api/Polymer.Base#property-domHost

[dpapad, 2016/07/01 18:08:43]

No. The reason is that domHost includes a few Polymer function calls that are
completely unnecessary, see [1] and [2].

[1]
https://cs.chromium.org/chromium/src/third_party/polymer/v1_0/components-chro...
[2]
https://cs.chromium.org/chromium/src/third_party/polymer/v1_0/components-chro...
(needed for Shady DOM only).

+    }
+    if (parent)
+      parent.style.display = '';
+  }
+
+  /**
+   * @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';

[Dan Beam, 2016/07/01 00:54:55]

can we use [hidden] instead?

[dpapad, 2016/07/01 18:08:43]

Done.

+  }
+
+  /**
+   * 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, '\\$&');

[Dan Beam, 2016/07/01 00:54:55]

why toLowerCase() if we're using 'i'?

[dpapad, 2016/07/01 18:08:43]

Removed.

+    if (searchText.length == 0) {
+      setSectionsVisibility_(page, true);
+      return;
+    }
+
+    setSectionsVisibility_(page, false);
+    findAndHighlightMatches_(page, new RegExp('(' + searchText + ')', 'i'));
+  }
+
+  return {
+    search: search,
+  };
+});