Performed an initial research on how does the old Options UI search mechanism works, posting findings below. The related code resides at https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/resources/options/search_page.js.


User enters text in a native <input type="search"> element which handles logic
for when to fire a 'search' event. Once a 'search' event is fired...

1) Update window URL, for example chrome://settings/search#cookies.
2) Hide all currently displayed sections.
3) Minimal processing of search query text (lower case, remove some characters).
4) Gather references to all section to be searched.
5) For each section,
   - create a native TreeWalker instance (via document.createTreeWalker)
   - traverse all text inside that section via the TreeWalker.
   - Split text nodes as necessary to wrap all matching text with a <span>
     (styled with a yellow background).
   - If any match was found unhide the section.
6) Search subsections (sections that are hidden behind an extra click) and
   display search bubbles accordingly, uses helper SearchBubble class).

Clearing all highlighted text needs to re-combined all text nodes that were
split earlier.

Further investigation is needed to determine how this mechanism needs to be modified
to work with the MD Settings. Things that most likely will get in the way, are the
usage of ShadowDOM and lazy-loading.

I see a couple of options:

1) attempt to port the old logic using TreeWalker to Polymer.dom.getDistributedNodes(), but thar be dragons

2) allow or force each component to implement a SearchableBehavior that defines an interface:

/** @polymerBehavior */
var SearchableBehavior = {
 /**
  * @param {string} term A search term to find.
  * @return {boolean} Whether |term| was found inside.
  */
  search: function(term) { assertNotReached(); },
  
  /**
   * Marks |term| in |node| and throws if not found.
   * @param {string} term A search term.
   * @param {Node} node The node in which |term| was found.
   */
  highlight: function(term, node) {
    // default implementation that scans |node.textContent| for |term|
    // and highlights if founds, throws if not found.
  },
};

Regarding 2: It seems promising. There would also be a need for an "unhighlight" method on the interface.

Also regardless of which approach (1, 2 or other) is chosen, it is not clear how searching will happen in sections that do not even exist in the DOM because they are lazily instantiated. An alternative idea I am still exploring in my mind is the following.

All text content exists in loadTimeData map. Searching this map could produce a list of string IDs that have matches. Then if we can add an association between string IDs to Polymer elements that use those strings, we could find all elements that need to be inserted in the search results (and possibly even instantiate lazy elements that include string IDs that matched).

#c7/dpapad: what about $i18n{}?

@c8/dbeam: Are those strings excluded from loadTimeData currently? If yes, we could maybe add them back.

Status update: I have been able to port the old mechanism for highlighting matches, such that it works across Shadow DOM boundaries (https://codereview.chromium.org/1952493002). There are still a few problems to solve with regards to highlighting, but this looks very promising (see screenshots). Currently searching is invoked from the dev console.

Deleted: search_within_settings1.png 87.0 KB

	search_within_settings1.png 87.0 KB View Download

Deleted: search_within_settings2.png 80.0 KB

	search_within_settings2.png 80.0 KB View Download

FYI, I have updated the proof of concept CL (https://codereview.chromium.org/1952493002) to use the search box on the top right, instead of having to issue queries from the Dev tools, works pretty well.

Minor issue not addressed yet: When the search result is within a settings-box, the introduced <span> wrapper around the matched text is not displayed correctly.

The immediate next step is to hide sections that don't have any match. After that, and depending on the exact mocks by Alan, we need to figure out how to search sections that don't exist in the DOM.

Mocks should be complete, see  crbug.com/602469 

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8cecfb55a718e2336332af555f41bdc8041c2391

commit 8cecfb55a718e2336332af555f41bdc8041c2391
Author: dpapad <dpapad@chromium.org>
Date: Tue Jun 14 18:18:56 2016

WebUI: cr-search-field, do not call delegate if search query did not change.

CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation
BUG= 608535 

Review-Url: https://codereview.chromium.org/2057353002
Cr-Commit-Position: refs/heads/master@{#399750}

[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/chrome/browser/resources/md_history/history_toolbar.js
[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/chrome/test/data/webui/cr_elements/cr_toolbar_search_field_tests.js
[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/ui/webui/resources/cr_elements/cr_search_field/cr_search_field_behavior.js

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8cecfb55a718e2336332af555f41bdc8041c2391

commit 8cecfb55a718e2336332af555f41bdc8041c2391
Author: dpapad <dpapad@chromium.org>
Date: Tue Jun 14 18:18:56 2016

WebUI: cr-search-field, do not call delegate if search query did not change.

CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation
BUG= 608535 

Review-Url: https://codereview.chromium.org/2057353002
Cr-Commit-Position: refs/heads/master@{#399750}

[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/chrome/browser/resources/md_history/history_toolbar.js
[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/chrome/test/data/webui/cr_elements/cr_toolbar_search_field_tests.js
[modify] https://crrev.com/8cecfb55a718e2336332af555f41bdc8041c2391/ui/webui/resources/cr_elements/cr_search_field/cr_search_field_behavior.js

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/37e9a8a91b3ec7abfb226cd63553a2149ef0888f

commit 37e9a8a91b3ec7abfb226cd63553a2149ef0888f
Author: dpapad <dpapad@chromium.org>
Date: Tue Jun 21 00:45:04 2016

MD Settings: Migrate from paper-drawer-panel to app-drawer.

Also remove usage of paper-toolbar replace with an equivalent simple
div for now. The goal is to re-use cr-toolbar in follow up CLs.

As a result of using app-drawer two bugs are fixed. Previously
- user could interact with the search box while the drawer was open,
- user could not close drawer by clicking on the toolbar

BUG= 608535 , 602896 
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2074063003
Cr-Commit-Position: refs/heads/master@{#400854}

[modify] https://crrev.com/37e9a8a91b3ec7abfb226cd63553a2149ef0888f/chrome/browser/resources/settings/settings_ui/settings_ui.html
[modify] https://crrev.com/37e9a8a91b3ec7abfb226cd63553a2149ef0888f/chrome/browser/resources/settings/settings_ui/settings_ui.js
[modify] https://crrev.com/37e9a8a91b3ec7abfb226cd63553a2149ef0888f/chrome/test/data/webui/settings/rtl_tests.js
[modify] https://crrev.com/37e9a8a91b3ec7abfb226cd63553a2149ef0888f/third_party/polymer/v1_0/find_unused_elements.py
[modify] https://crrev.com/37e9a8a91b3ec7abfb226cd63553a2149ef0888f/ui/webui/resources/polymer_resources.grdp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/48c8c979b1440101b879a05352cfd5907a8ef643

commit 48c8c979b1440101b879a05352cfd5907a8ef643
Author: dpapad <dpapad@chromium.org>
Date: Wed Jun 22 03:24:04 2016

MD Settings: Replace current toolbar with cr-toolbar.

 - Modify cr-toolbar to accept an icon next to the page title.
 - Add string for  search placeholder.
 - Add temporary "coming soon!" text to indicate that search is not
   functional yet (displayed along the placeholder text).

BUG= 608535 
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2064013002
Cr-Commit-Position: refs/heads/master@{#401192}

[modify] https://crrev.com/48c8c979b1440101b879a05352cfd5907a8ef643/chrome/app/settings_strings.grdp
[modify] https://crrev.com/48c8c979b1440101b879a05352cfd5907a8ef643/chrome/browser/resources/settings/settings_ui/settings_ui.html
[modify] https://crrev.com/48c8c979b1440101b879a05352cfd5907a8ef643/chrome/browser/ui/webui/settings/md_settings_localized_strings_provider.cc
[modify] https://crrev.com/48c8c979b1440101b879a05352cfd5907a8ef643/ui/webui/resources/cr_elements/cr_toolbar/cr_toolbar.html

 Issue 622307  has been merged into this issue.

 Issue 622422  has been merged into this issue.

 Issue 622095  has been merged into this issue.

 Issue 622884  has been merged into this issue.

 Issue 623313  has been merged into this issue.

 Issue 623852  has been merged into this issue.

 Issue 623948  has been merged into this issue.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9a07dc6b71462795d776490acb1e51142c9afd74

commit 9a07dc6b71462795d776490acb1e51142c9afd74
Author: dpapad <dpapad@chromium.org>
Date: Wed Jun 29 23:09:44 2016

MD Settings: Improve rendering performance of fonts page.

The fonts page includes a few very large <settings-dropdown-menu> instances.
While implementing force-rendering for the purposes of "search within settings"
it was revealed that it occupied about 1.3s of the main thread to render itself.
There are two separate improvements bundled in this CL.
 1) Replace <paper-item> with a simple styled <button>. This change alone reduces
    total rendering time from 1.3s to 0.25s.
 2) Use the new itemCount feature for dom-repeat to yield, instead of rendering
    the entire template all at once.

BUG= 602896 , 608535 
TEST=Click on "Customize fonts", observe how much faster the subpage opens.
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2106723003
Cr-Commit-Position: refs/heads/master@{#402981}

[modify] https://crrev.com/9a07dc6b71462795d776490acb1e51142c9afd74/chrome/browser/resources/md_downloads/vulcanized.html
[modify] https://crrev.com/9a07dc6b71462795d776490acb1e51142c9afd74/chrome/browser/resources/settings/controls/settings_dropdown_menu.html
[modify] https://crrev.com/9a07dc6b71462795d776490acb1e51142c9afd74/third_party/polymer/v1_0/chromium.patch
[modify] https://crrev.com/9a07dc6b71462795d776490acb1e51142c9afd74/third_party/polymer/v1_0/components-chromium/paper-item/paper-item-shared-styles.html

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d516b7a2c3b7c11aedd23522b34e6cfbb7916df5

commit d516b7a2c3b7c11aedd23522b34e6cfbb7916df5
Author: dpapad <dpapad@chromium.org>
Date: Fri Jul 01 00:24:22 2016

Relanding MD Settings: Improve rendering performance of fonts page.

First version of this CL was reverted (cl/2119733002).

The fonts page includes a few very large <settings-dropdown-menu> instances.
While implementing force-rendering for the purposes of "search within settings"
it was revealed that it occupied about 1.3s of the main thread to render itself.
There are two separate improvements bundled in this CL.
 1) Replace <paper-item> with a simple styled <div>. This change alone reduces
    total rendering time from 1.3s to 0.25s.
 2) Use the new initialCount feature for dom-repeat to yield, instead of
    rendering the entire template all at once.

BUG= 602896 , 608535 
TEST=Click on "Customize fonts", observe how much faster the subpage opens.
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2114793002
Cr-Commit-Position: refs/heads/master@{#403366}

[modify] https://crrev.com/d516b7a2c3b7c11aedd23522b34e6cfbb7916df5/chrome/browser/resources/settings/controls/settings_dropdown_menu.html

 Issue 625849  has been merged into this issue.

 Issue 625054  has been merged into this issue.

Verified the reland as per the test given in C#28 on the latest M-53(53.0.2785.8) on Windows-7, Mac OS 10.11.5 and Linux Ubuntu 14.04. This is working as intended and clicking the 'Customize fonts' under chrome://md-settings opens the subpage without any slowness.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/e18c3a8d876d941206fc600dea2681dab2d290d8

commit e18c3a8d876d941206fc600dea2681dab2d290d8
Author: dpapad <dpapad@chromium.org>
Date: Thu Jul 07 19:57:27 2016

MD Settings: First iteration of searching within settings.

This CL includes the core logic of the searching mechanism
 - Traversing the DOM tree (taking into account Shadow DOM).
 - Finding and highlighting matches (using familiar yellow rectangle
   for now).
 - Showing/hiding <settings-section> instances depending on search
   outcome.
 - Un-highlighting matches and restoring DOM structure.
 - Navigating to the default page (chrome://md-settings), when a search
   is triggered from any other page/sub-page.
 - Force rendering of the "advanced" page and update search results.

Sub-pages that are not rendered are currently not searched. This will be
addressed in follow up CLs along with multiple other issues.

BUG= 608535 
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2082793003
Cr-Commit-Position: refs/heads/master@{#404222}

[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/compiled_resources2.gyp
[add] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/search_settings.js
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_main/compiled_resources2.gyp
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_main/settings_main.html
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_main/settings_main.js
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_resources.grd
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_ui/settings_ui.html
[modify] https://crrev.com/e18c3a8d876d941206fc600dea2681dab2d290d8/chrome/browser/resources/settings/settings_ui/settings_ui.js

dpapad@ I was wondering if anything is being done to make search a bit smarter than old settings? Currently old settings just detects verbatim words. Could we detect typos and synonyms?

mgreenwald@: no, we're not doing that yet

to expand: we've thought about this for a long time (me: many years, md-settings group: 1+ years).

Google's a search company and stuff, so we're known for it and should do the best job we can here, but in the interests of shipping we're really only keeping parity with the previous version of settings for now.

I get tons of settings feature requests all the time.  this is high on my list as a very useful enhancement, and you're more than welcome to file a feature request (if there's not one already) so we keep track of it and prioritize it correctly.

BUT, we're not currently looking for more things to be added to our minimum viable product for md-settings v1.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a153ff0d4ebfee359d511c0879ebbce1073e088a

commit a153ff0d4ebfee359d511c0879ebbce1073e088a
Author: dpapad <dpapad@chromium.org>
Date: Wed Jul 13 19:45:36 2016

MD Settings: Second iteration of search within settings.

 - Force render parts of the page that should be searched but
   are currently not rendered.
 - Ensuring that searching code yields often enough to the main
   thread to prevent UI freeze.

Specifically
 - Adding three types of tasks TopLevelSearchTask, SearchTask and
   RenderTask.
 - Adding a task manager class, which yields before executing a
   task by using window.requestIdleCallback().
 - Canceling obsolete tasks (happens when a new search is issued after the
   task was posted but before it made it to the front of the queue).

BUG= 608535 
TEST=Navigate to chrome://md-settings. Search for a term that exists in
an unrendered sub-page, for example "engine". Navigate to the subpage by
clicking "Manage search engines". Notice that matches are magically
highlighted even though this subpage was not rendered when the search was
initiated.

CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2103133007
Cr-Commit-Position: refs/heads/master@{#405232}

[modify] https://crrev.com/a153ff0d4ebfee359d511c0879ebbce1073e088a/chrome/browser/resources/settings/search_settings.js

Posting a summary of remaining (known) issues:

Features
1 Add a "no results" message.
2 Show spinner while search is in progress.
3 Skip dynamic data searching: Flesh out mechanism to avoid searching dynamic
  data. Currently <paper-item> and <iron-list> is skipped, but other dynamic
  content is still searched. Perhaps adding a "no-search" attribute and updating
  the DOM traversal code is better).
4 Need mechanism to highlight sub-level matches (equivalent of SearchBubble in
  old Options).

Bugs
5 Currently rendered Nodes that have attribute "hidden" are still searched (and
  highlighted), and cause their parent settings-section to be included in the
  results.
6 Forced rendering is currently turned off for site-settings, because of a
  runtime assertion error, need to fix the error and enable force rendering.

Performance
7 Consider not blocking the UI thread for more than 16ms (or as close as to
  that as possible). Currently, even though the algorithm has been asyncified,
  some "atomic" synchronous chunks of work can take longer than 16ms (specific
  data needed).

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9b50cd3cc71e19825a546f82c0f2734e03efb172

commit 9b50cd3cc71e19825a546f82c0f2734e03efb172
Author: dpapad <dpapad@chromium.org>
Date: Tue Jul 19 18:19:39 2016

MD Settings: Show/hide spinner when searching starts/ends.

 - SearchManager notifies observer when searching starts/ends.
 - Make <settings-main> instance an observer of SearchManager.
 - Use data binding to update the spinner-active property of
   <cr-toolbar>.

BUG= 608535 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2153013003
Cr-Commit-Position: refs/heads/master@{#406321}

[modify] https://crrev.com/9b50cd3cc71e19825a546f82c0f2734e03efb172/chrome/browser/resources/settings/search_settings.js
[modify] https://crrev.com/9b50cd3cc71e19825a546f82c0f2734e03efb172/chrome/browser/resources/settings/settings_main/settings_main.js
[modify] https://crrev.com/9b50cd3cc71e19825a546f82c0f2734e03efb172/chrome/browser/resources/settings/settings_ui/settings_ui.html
[modify] https://crrev.com/9b50cd3cc71e19825a546f82c0f2734e03efb172/chrome/browser/resources/settings/settings_ui/settings_ui.js

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/2e78a5383cf4651004dace4e7f708eba0c30753f

commit 2e78a5383cf4651004dace4e7f708eba0c30753f
Author: dpapad <dpapad@chromium.org>
Date: Wed Aug 10 01:45:51 2016

MD Settings: Skip hidden nodes when searching.

Nodes that are hidden, either with the "hidden" attribute, or via an explicit
style "display: none" are not applicable to the user's current state and should
be skipped.

Nodes that are hidden via a different CSS class, for example <iron-pages> CSS rule
:host > ::content > :not(.iron-selected) { display: none !important; }

are still being searched, and need to be addressed in follow up.

BUG= 608535 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2223083003
Cr-Commit-Position: refs/heads/master@{#410915}

[modify] https://crrev.com/2e78a5383cf4651004dace4e7f708eba0c30753f/chrome/browser/resources/settings/search_settings.js
[modify] https://crrev.com/2e78a5383cf4651004dace4e7f708eba0c30753f/chrome/browser/resources/settings/settings_page/settings_section.html
[modify] https://crrev.com/2e78a5383cf4651004dace4e7f708eba0c30753f/chrome/browser/resources/settings/settings_page/settings_section.js

Status update: Searching is functional. Few issues remain to be fully done:

1) Change current search bubbles UI to match the latest request from @bettes [1]. The
   current search bubble UI is mostly a simplified version of the old Options search
   bubble [2]. It is simplified since it was always pointing to the right, and there is
   no border. Satisfying latest request will require to bring back some of the old
   bubble complexity.
2) Expose searching via the URL, for example navigating to
   chrome://md-settings#search=foo should pre-populate the search box with "foo" and
   spawn a search request. This would be nice to have, but not a blocker AFAIK. 

Other than that, things should mostly work. In the case where more tuning of what should be
search/skipped is needed, the mechanisms are all in place
 - Blacklist of elements that are always skipped [3]. Consider adding "DIALOG" as a new entry.
 - no-search attribute respected by the searching algorithm. If present on an element, the entire
   subtree under the element will be ignored. Currently used only for <settings-subpage> elements
   and their corresponding <template>.
 - Elements with attribute "hidden" or with an explicit style.display "none", are skipped. 

Things to consider prelaunch:
window.requestIdleCallback() is used to ensure that the page is as responsive as
possible while forced-renderings of subpages is happening in the background [4]. For
example try typing fast "Goog", wait until the spinner starts, and then type
"le", it is pretty responsive.

My observation is that requestIdleCallback() is too conservative and even
though it achieves good responsiveness, it increases the overall search time of
the 1st search (spinner on to spinner off time), by 100% compared to
window.setTimeout(..., 0). setTimeout seems to be achieving good enough
responsiveness, and better overall search time. Again, this consideration makes
a difference only for the 1st search (because the 1st search triggers the
forced-renderings, and therefore it triggers multiple tasks). I suggest experimenting
locally with the two versions to decide which one achieves a better responsiveness VS
speed trade-off.

[1] https://bugs.chromium.org/p/chromium/issues/detail?id=633657#c8
[2] https://cs.chromium.org/chromium/src/chrome/browser/resources/print_preview/common/search_bubble.css
[3] https://cs.chromium.org/chromium/src/chrome/browser/resources/settings/search_settings.js?l=21
[4] https://cs.chromium.org/chromium/src/chrome/browser/resources/settings/search_settings.js?l=417

As you try that experimentation I'd suggest checking on a low end Chromebook or Windows machine. Your Z620/840 or Macbook is very fast, it's possible that on those (most common) machines the setTimeout is worse.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9474e1a879494292768c724190da09fd77b64a06

commit 9474e1a879494292768c724190da09fd77b64a06
Author: dpapad <dpapad@chromium.org>
Date: Fri Aug 12 01:59:09 2016

MD Settings: Remove iron-pages usage from <settings-sync-page>.

This facilitates the searching algorithm to ignore hidden nodes.
<iron-pages> hides the currently not displayed pages using a custom CSS
:host > ::content > :not(.iron-selected) { display: none !important; }
which bypasses the searching algorithm's visibility checks. Using the
"hidden" attribute instead of <iron-pages> fixes the issue.

BUG= 608535 
TEST=When logged in to chrome and after sync prefs have been fetched, search
for "Please wait". There should be no search hit in the "People" section.
Previously a search hit occurred within a hidden message that was not applicable
to the current state of the user.
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:closure_compilation

Review-Url: https://codereview.chromium.org/2230833003
Cr-Commit-Position: refs/heads/master@{#411514}

[modify] https://crrev.com/9474e1a879494292768c724190da09fd77b64a06/chrome/browser/resources/settings/people_page/sync_page.html
[modify] https://crrev.com/9474e1a879494292768c724190da09fd77b64a06/chrome/browser/resources/settings/people_page/sync_page.js
[modify] https://crrev.com/9474e1a879494292768c724190da09fd77b64a06/chrome/test/data/webui/settings/people_page_sync_page_test.js

 Issue 647739  has been merged into this issue.

Search functionality has been implemented. A possible improvement is already tracked by issue 651573. Further performance improvements should be tracked by separate bugs.