[omnibox] Improve Pedal triggering with natural concept detection

The first method of triggering Pedals used small sets of known
match suggestions, and did not cover most of the possible ways
that users might indicate their intention.  This CL dramatically
expands the space of acceptable queries by checking match text
against small sets of concepts.  When all required concepts
are present, with or without non-required concepts, with no
extraneous text uncovered by the concept set, the Pedal triggers.
This approach efficiently represents large sets of trigger
suggestions without wasting a lot of space on string structures.

Bug: 893183
Change-Id: I75a8ce1510a732c3ea38088ec21b7b3e828c1617
Reviewed-on: https://chromium-review.googlesource.com/c/1402026
Commit-Queue: Orin Jaworski <orinj@chromium.org>
Reviewed-by: Tommy Li <tommycli@chromium.org>
Cr-Commit-Position: refs/heads/master@{#623530}
diff --git a/components/omnibox/browser/BUILD.gn b/components/omnibox/browser/BUILD.gn
index 855d589..7d18e55 100644
--- a/components/omnibox/browser/BUILD.gn
+++ b/components/omnibox/browser/BUILD.gn
@@ -380,6 +380,7 @@
     "omnibox_controller_unittest.cc",
     "omnibox_edit_model_unittest.cc",
     "omnibox_field_trial_unittest.cc",
+    "omnibox_pedal_implementations_unittest.cc",
     "omnibox_pedal_provider_unittest.cc",
     "omnibox_pedal_unittest.cc",
     "omnibox_popup_model_unittest.cc",
diff --git a/components/omnibox/browser/omnibox_pedal.cc b/components/omnibox/browser/omnibox_pedal.cc
index 176eac4..a12c2bd7 100644
--- a/components/omnibox/browser/omnibox_pedal.cc
+++ b/components/omnibox/browser/omnibox_pedal.cc
@@ -4,6 +4,8 @@
 
 #include "components/omnibox/browser/omnibox_pedal.h"
 
+#include <cctype>
+
 #include "base/strings/utf_string_conversions.h"
 #include "components/omnibox/browser/omnibox_client.h"
 #include "components/omnibox/browser/omnibox_edit_controller.h"
@@ -21,8 +23,61 @@
       hint_short(l10n_util::GetStringUTF16(id_hint_short)),
       suggestion_contents(l10n_util::GetStringUTF16(id_suggestion_contents)) {}
 
-OmniboxPedal::OmniboxPedal(OmniboxPedal::LabelStrings strings)
-    : strings_(strings) {}
+// =============================================================================
+
+OmniboxPedal::SynonymGroup::SynonymGroup(
+    bool required,
+    std::initializer_list<const char*> synonyms)
+    : required_(required) {
+  // The DCHECK logic below is quickly ensuring that the synonyms are provided
+  // in descending order of string length.
+#if DCHECK_IS_ON()
+  size_t min_size = std::numeric_limits<std::size_t>::max();
+#endif
+  synonyms_.reserve(synonyms.size());
+  for (const char* synonym : synonyms) {
+    synonyms_.push_back(base::ASCIIToUTF16(synonym));
+#if DCHECK_IS_ON()
+    size_t size = synonyms_.back().size();
+    DCHECK_LE(size, min_size);
+    min_size = size;
+#endif
+  }
+}
+
+OmniboxPedal::SynonymGroup::SynonymGroup(const SynonymGroup& other) = default;
+
+OmniboxPedal::SynonymGroup::~SynonymGroup() = default;
+
+bool OmniboxPedal::SynonymGroup::EraseFirstMatchIn(
+    base::string16& remaining) const {
+  for (const auto& synonym : synonyms_) {
+    const size_t pos = remaining.find(synonym);
+    if (pos != base::string16::npos) {
+      remaining.erase(pos, synonym.size());
+      return true;
+    }
+  }
+  return !required_;
+}
+
+// =============================================================================
+
+OmniboxPedal::OmniboxPedal(
+    LabelStrings strings,
+    GURL url,
+    std::initializer_list<const char*> triggers,
+    std::initializer_list<const SynonymGroup> synonym_groups)
+    : strings_(strings), url_(url) {
+  triggers_.reserve(triggers.size());
+  for (const char* trigger : triggers) {
+    triggers_.insert(base::ASCIIToUTF16(trigger));
+  }
+  synonym_groups_.reserve(synonym_groups.size());
+  for (const SynonymGroup& group : synonym_groups) {
+    synonym_groups_.push_back(group);
+  }
+}
 
 OmniboxPedal::~OmniboxPedal() {}
 
@@ -67,7 +122,20 @@
 #endif
 
 bool OmniboxPedal::IsTriggerMatch(const base::string16& match_text) const {
-  return triggers_.find(match_text) != triggers_.end();
+  return (triggers_.find(match_text) != triggers_.end()) ||
+         IsConceptMatch(match_text);
+}
+
+bool OmniboxPedal::IsConceptMatch(const base::string16& match_text) const {
+  base::string16 remaining = match_text;
+  for (const auto& group : synonym_groups_) {
+    if (!group.EraseFirstMatchIn(remaining))
+      return false;
+  }
+  // If any non-space is remaining, it means there is something in match_text
+  // that was not covered by groups, so conservatively treat it as non-match.
+  const auto is_space = [](auto c) { return std::isspace(c); };
+  return std::all_of(remaining.begin(), remaining.end(), is_space);
 }
 
 void OmniboxPedal::OpenURL(OmniboxPedal::ExecutionContext& context,
diff --git a/components/omnibox/browser/omnibox_pedal.h b/components/omnibox/browser/omnibox_pedal.h
index 38db74c..578481e 100644
--- a/components/omnibox/browser/omnibox_pedal.h
+++ b/components/omnibox/browser/omnibox_pedal.h
@@ -7,6 +7,7 @@
 
 #include <unordered_set>
 
+#include "base/gtest_prod_util.h"
 #include "base/strings/string16.h"
 #include "base/time/time.h"
 #include "build/build_config.h"
@@ -39,6 +40,37 @@
     const base::string16 suggestion_contents;
   };
 
+  class SynonymGroup {
+   public:
+    // Note: synonyms must be specified in decreasing order by string length
+    // so that longest matches will be detected first.  For example,
+    // "incognito window" must come before "incognito" so that the " window"
+    // part will also be covered by this group -- otherwise it would be left
+    // intact and wrongly treated as uncovered by the checking algorithm.
+    // See OmniboxPedal::IsConceptMatch for the logic that necessitates order.
+    SynonymGroup(bool required, std::initializer_list<const char*> synonyms);
+    SynonymGroup(const SynonymGroup& other);
+    ~SynonymGroup();
+
+    // Removes first matching synonym from given |remaining| string if any are
+    // found.  Returns true if checking may continue; false if no further
+    // checking is required because what remains cannot be a concept match.
+    bool EraseFirstMatchIn(base::string16& remaining) const;
+
+   protected:
+    // If this is true, a synonym of the group must be present for triggering.
+    // If false, then presence is simply allowed and does not inhibit triggering
+    // (any text not covered by groups would stop trigger).
+    bool required_;
+
+    // The set of interchangeable alternative representations for this group:
+    // when trying to clear browsing data, a user may think of 'erase', 'clear',
+    // 'delete', etc.  Even though these are not strictly synonymous in natural
+    // language, they are considered equivalent within the context of intention
+    // to perform this Pedal's action.
+    std::vector<base::string16> synonyms_;
+  };
+
   // ExecutionContext provides the necessary structure for Pedal
   // execution implementations that potentially vary widely, and
   // references are preferred over pointers for members that are
@@ -61,7 +93,11 @@
     base::TimeTicks match_selection_timestamp_;
   };
 
-  OmniboxPedal(LabelStrings strings);
+  OmniboxPedal(
+      LabelStrings strings,
+      GURL url,
+      std::initializer_list<const char*> triggers,
+      std::initializer_list<const OmniboxPedal::SynonymGroup> synonym_groups);
   virtual ~OmniboxPedal();
 
   // Provides read access to labels associated with this Pedal.
@@ -105,9 +141,19 @@
   bool IsTriggerMatch(const base::string16& match_text) const;
 
  protected:
+  FRIEND_TEST_ALL_PREFIXES(OmniboxPedalTest, SynonymGroupErasesFirstMatchOnly);
+  FRIEND_TEST_ALL_PREFIXES(OmniboxPedalTest, SynonymGroupsDriveConceptMatches);
+
+  // If a sufficient set of triggering synonym groups are present in match_text
+  // then it's a concept match and this returns true.  If a required group is
+  // not present, or if match_text contains extraneous text not covered by any
+  // synonym group, then it's not a concept match and this returns false.
+  bool IsConceptMatch(const base::string16& match_text) const;
+
   // Use this for the common case of navigating to a URL.
   void OpenURL(ExecutionContext& context, const GURL& url) const;
 
+  std::vector<SynonymGroup> synonym_groups_;
   std::unordered_set<base::string16> triggers_;
   LabelStrings strings_;
 
diff --git a/components/omnibox/browser/omnibox_pedal_implementations.cc b/components/omnibox/browser/omnibox_pedal_implementations.cc
index 17e00c0b..60c1e6358 100644
--- a/components/omnibox/browser/omnibox_pedal_implementations.cc
+++ b/components/omnibox/browser/omnibox_pedal_implementations.cc
@@ -16,66 +16,71 @@
 #include "components/omnibox/browser/vector_icons.h"  // nogncheck
 #endif
 
-// A small convenience wrapper for the common implementation pattern below.
-class OmniboxPedalCommon : public OmniboxPedal {
- public:
-  OmniboxPedalCommon(LabelStrings strings,
-                     GURL url,
-                     std::initializer_list<const char*> triggers)
-      : OmniboxPedal(strings) {
-    url_ = url;
-    for (const char* trigger : triggers) {
-      triggers_.insert(base::ASCIIToUTF16(trigger));
-    }
-  }
-};
-
 // =============================================================================
 
-class OmniboxPedalClearBrowsingData : public OmniboxPedalCommon {
- public:
-  OmniboxPedalClearBrowsingData()
-      : OmniboxPedalCommon(
-            LabelStrings(
-                IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT,
-                IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT_SHORT,
-                IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_SUGGESTION_CONTENTS),
-            GURL("chrome://settings/clearBrowserData"),
-            {
-                "how to clear browsing data on chrome",
-                "how to clear history",
-                "how to clear history on google chrome",
-                "how to clear history on chrome",
-                "how to clear history in google chrome",
-                "how to clear google chrome history",
-                "how to clear history google chrome",
-                "how to clear browsing history in chrome",
-                "clear browsing data",
-                "clear history",
-                "clear browsing data on chrome",
-                "clear history on google chrome",
-                "clear history google chrome",
-                "clear browsing history in chrome",
-                "clear cookies chrome",
-                "clear chrome history",
-                "clear chrome cache",
-                "history clear",
-                "history clear chrome",
-            }) {}
+OmniboxPedalClearBrowsingData::OmniboxPedalClearBrowsingData()
+    : OmniboxPedal(
+          LabelStrings(
+              IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT,
+              IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT_SHORT,
+              IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_SUGGESTION_CONTENTS),
+          GURL("chrome://settings/clearBrowserData"),
+          {
+              "how to clear browsing data on chrome",
+              "how to clear history",
+              "how to clear history on google chrome",
+              "how to clear history on chrome",
+              "how to clear history in google chrome",
+              "how to clear google chrome history",
+              "how to clear history google chrome",
+              "how to clear browsing history in chrome",
+              "clear browsing data",
+              "clear history",
+              "clear browsing data on chrome",
+              "clear history on google chrome",
+              "clear history google chrome",
+              "clear browsing history in chrome",
+              "clear cookies chrome",
+              "clear chrome history",
+              "clear chrome cache",
+              "history clear",
+              "history clear chrome",
+          },
+          {
+              SynonymGroup(false,
+                           {
+                               "google chrome",
+                               "browser",
+                               "chrome",
+                           }),
+              SynonymGroup(true,
+                           {
+                               "delete",
+                               "remove",
+                               "erase",
+                               "clear",
+                               "wipe",
+                           }),
+              SynonymGroup(true,
+                           {
+                               "history",
+                               "cache",
+                               "data",
+                           }),
+          }) {}
 
 #if (!defined(OS_ANDROID) || BUILDFLAG(ENABLE_VR)) && !defined(OS_IOS)
-  const gfx::VectorIcon& GetVectorIcon() const override {
-    return omnibox::kAnswerWhenIsIcon;
-  }
+const gfx::VectorIcon& OmniboxPedalClearBrowsingData::GetVectorIcon() const {
+  return omnibox::kAnswerWhenIsIcon;
+}
 #endif
-};
 
 // =============================================================================
 
-class OmniboxPedalChangeSearchEngine : public OmniboxPedalCommon {
+class OmniboxPedalChangeSearchEngine : public OmniboxPedal {
  public:
   OmniboxPedalChangeSearchEngine()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             LabelStrings(
                 IDS_OMNIBOX_PEDAL_CHANGE_SEARCH_ENGINE_HINT,
                 IDS_OMNIBOX_PEDAL_CHANGE_SEARCH_ENGINE_HINT_SHORT,
@@ -90,61 +95,133 @@
                 "how to set google as default search engine in chrome",
                 "how to make google default search engine",
                 "how to change default search engine in google chrome",
-                "change search engine", "change google search engine",
+                "change search engine",
+                "change google search engine",
                 "change chrome searh engine",
                 "change default search engine in chrome",
-                "change search engine chrome", "change default search chrome",
-                "change search chrome", "switch chrome search engine",
+                "change search engine chrome",
+                "change default search chrome",
+                "change search chrome",
+                "switch chrome search engine",
                 "switch search engine",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "choose",
+                                 "change",
+                                 "switch",
+                                 "select",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "standard search engine",
+                                 "default search engine",
+                                 "search engine",
+                                 "search",
+                             }),
             }) {}
 };
 
 // =============================================================================
 
-class OmniboxPedalManagePasswords : public OmniboxPedalCommon {
+class OmniboxPedalManagePasswords : public OmniboxPedal {
  public:
   OmniboxPedalManagePasswords()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             LabelStrings(
                 IDS_OMNIBOX_PEDAL_MANAGE_PASSWORDS_HINT,
                 IDS_OMNIBOX_PEDAL_MANAGE_PASSWORDS_HINT_SHORT,
                 IDS_OMNIBOX_PEDAL_MANAGE_PASSWORDS_SUGGESTION_CONTENTS),
             GURL("chrome://settings/passwords"),
             {
-                "passwords", "find my passwords", "save passwords in chrome",
-                "view saved passwords", "delete passwords",
-                "find saved passwords", "where does chrome store passwords",
+                "passwords",
+                "find my passwords",
+                "save passwords in chrome",
+                "view saved passwords",
+                "delete passwords",
+                "find saved passwords",
+                "where does chrome store passwords",
                 "how to see passwords in chrome",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "manager",
+                                 "manage",
+                                 "update",
+                                 "change",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "passwords",
+                             }),
             }) {}
 };
 
 // =============================================================================
 
 // TODO(orinj): Use better scoping for existing setting, or link to new UI.
-class OmniboxPedalChangeHomePage : public OmniboxPedalCommon {
+class OmniboxPedalChangeHomePage : public OmniboxPedal {
  public:
   OmniboxPedalChangeHomePage()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             LabelStrings(
                 IDS_OMNIBOX_PEDAL_CHANGE_HOME_PAGE_HINT,
                 IDS_OMNIBOX_PEDAL_CHANGE_HOME_PAGE_HINT_SHORT,
                 IDS_OMNIBOX_PEDAL_CHANGE_HOME_PAGE_SUGGESTION_CONTENTS),
             GURL("chrome://settings/?search=show+home+button"),
             {
-                "how to change home page", "how to change your home page",
-                "how do i change my home page", "change home page google",
-                "home page chrome", "change home chrome",
-                "change chrome home page", "how to change home page on chrome",
-                "how to change home page in chrome", "change chrome home",
+                "how to change home page",
+                "how to change your home page",
+                "how do i change my home page",
+                "change home page google",
+                "home page chrome",
+                "change home chrome",
+                "change chrome home page",
+                "how to change home page on chrome",
+                "how to change home page in chrome",
+                "change chrome home",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "change",
+                                 "choose",
+                                 "set",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "home page",
+                                 "homepage",
+                             }),
             }) {}
 };
 
 // =============================================================================
 
-class OmniboxPedalUpdateCreditCard : public OmniboxPedalCommon {
+class OmniboxPedalUpdateCreditCard : public OmniboxPedal {
  public:
   OmniboxPedalUpdateCreditCard()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             OmniboxPedal::LabelStrings(
                 IDS_OMNIBOX_PEDAL_UPDATE_CREDIT_CARD_HINT,
                 IDS_OMNIBOX_PEDAL_UPDATE_CREDIT_CARD_HINT_SHORT,
@@ -155,24 +232,73 @@
                 "how to remove credit card from google chrome",
                 "remove google chrome credit cards",
                 "access google chrome credit cards",
-                "google chrome credit cards", "chrome credit cards",
-                "get to chrome credit cards", "chrome credit saved",
+                "google chrome credit cards",
+                "chrome credit cards",
+                "get to chrome credit cards",
+                "chrome credit saved",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "update",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "credit card",
+                                 "card info",
+                                 "cards",
+                             }),
             }) {}
 };
 
 // =============================================================================
 
-class OmniboxPedalLaunchIncognito : public OmniboxPedalCommon {
+class OmniboxPedalLaunchIncognito : public OmniboxPedal {
  public:
   OmniboxPedalLaunchIncognito()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             LabelStrings(
                 IDS_OMNIBOX_PEDAL_LAUNCH_INCOGNITO_HINT,
                 IDS_OMNIBOX_PEDAL_LAUNCH_INCOGNITO_HINT_SHORT,
                 IDS_OMNIBOX_PEDAL_LAUNCH_INCOGNITO_SUGGESTION_CONTENTS),
             GURL(),
             {
-                "what is incognito", "what's incognito mode",
+                "what is incognito",
+                "what's incognito mode",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "launch",
+                                 "start",
+                                 "enter",
+                                 "open",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "incognito window",
+                                 "incognito mode",
+                                 "private window",
+                                 "incognito tab",
+                                 "private mode",
+                                 "dark window",
+                                 "private tab",
+                                 "incognito",
+                                 "dark mode",
+                                 "dark tab",
+                             }),
             }) {}
 
   void Execute(ExecutionContext& context) const override {
@@ -182,20 +308,43 @@
 
 // =============================================================================
 
-class OmniboxPedalTranslate : public OmniboxPedalCommon {
+class OmniboxPedalTranslate : public OmniboxPedal {
  public:
   OmniboxPedalTranslate()
-      : OmniboxPedalCommon(
+      : OmniboxPedal(
             LabelStrings(IDS_OMNIBOX_PEDAL_TRANSLATE_HINT,
                          IDS_OMNIBOX_PEDAL_TRANSLATE_HINT_SHORT,
                          IDS_OMNIBOX_PEDAL_TRANSLATE_SUGGESTION_CONTENTS),
             GURL(),
             {
                 "how to change language in google chrome",
-                "change language chrome", "change chrome language",
-                "change language in chrome", "switch chrome language",
-                "translate language", "translate in chrome",
-                "translate on page", "translate language chrome",
+                "change language chrome",
+                "change chrome language",
+                "change language in chrome",
+                "switch chrome language",
+                "translate language",
+                "translate in chrome",
+                "translate on page",
+                "translate language chrome",
+            },
+            {
+                SynonymGroup(false,
+                             {
+                                 "google chrome",
+                                 "browser",
+                                 "chrome",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "change language",
+                                 "translate",
+                             }),
+                SynonymGroup(true,
+                             {
+                                 "this page",
+                                 "page",
+                                 "this",
+                             }),
             }) {}
 
   void Execute(ExecutionContext& context) const override {
@@ -205,30 +354,44 @@
 
 // =============================================================================
 
-class OmniboxPedalUpdateChrome : public OmniboxPedalCommon {
- public:
-  OmniboxPedalUpdateChrome()
-      : OmniboxPedalCommon(
-            LabelStrings(IDS_OMNIBOX_PEDAL_UPDATE_CHROME_HINT,
-                         IDS_OMNIBOX_PEDAL_UPDATE_CHROME_HINT_SHORT,
-                         IDS_OMNIBOX_PEDAL_UPDATE_CHROME_SUGGESTION_CONTENTS),
-            GURL(),
-            {
-                "how to update google chrome", "how to update chrome",
-                "how do i update google chrome", "how to update chrome browser",
-                "update google chrome", "update chrome",
-                "update chrome browser",
-            }) {}
+OmniboxPedalUpdateChrome::OmniboxPedalUpdateChrome()
+    : OmniboxPedal(
+          LabelStrings(IDS_OMNIBOX_PEDAL_UPDATE_CHROME_HINT,
+                       IDS_OMNIBOX_PEDAL_UPDATE_CHROME_HINT_SHORT,
+                       IDS_OMNIBOX_PEDAL_UPDATE_CHROME_SUGGESTION_CONTENTS),
+          GURL(),
+          {
+              "how to update google chrome",
+              "how to update chrome",
+              "how do i update google chrome",
+              "how to update chrome browser",
+              "update google chrome",
+              "update chrome",
+              "update chrome browser",
+          },
+          {
+              SynonymGroup(true,
+                           {
+                               "google chrome",
+                               "browser",
+                               "chrome",
+                           }),
+              SynonymGroup(true,
+                           {
+                               "upgrade",
+                               "install",
+                               "update",
+                           }),
+          }) {}
 
-  void Execute(ExecutionContext& context) const override {
-    context.client_.OpenUpdateChromeDialog();
-  }
+void OmniboxPedalUpdateChrome::Execute(ExecutionContext& context) const {
+  context.client_.OpenUpdateChromeDialog();
+}
 
-  bool IsReadyToTrigger(
-      const AutocompleteProviderClient& client) const override {
-    return client.IsBrowserUpdateAvailable();
-  }
-};
+bool OmniboxPedalUpdateChrome::IsReadyToTrigger(
+    const AutocompleteProviderClient& client) const {
+  return client.IsBrowserUpdateAvailable();
+}
 
 // =============================================================================
 
diff --git a/components/omnibox/browser/omnibox_pedal_implementations.h b/components/omnibox/browser/omnibox_pedal_implementations.h
index 0550aa5..0d70702 100644
--- a/components/omnibox/browser/omnibox_pedal_implementations.h
+++ b/components/omnibox/browser/omnibox_pedal_implementations.h
@@ -8,7 +8,24 @@
 #include <memory>
 #include <vector>
 
-class OmniboxPedal;
+#include "build/build_config.h"
+#include "components/omnibox/browser/omnibox_pedal.h"
+
+class OmniboxPedalClearBrowsingData : public OmniboxPedal {
+ public:
+  OmniboxPedalClearBrowsingData();
+#if (!defined(OS_ANDROID) || BUILDFLAG(ENABLE_VR)) && !defined(OS_IOS)
+  const gfx::VectorIcon& GetVectorIcon() const override;
+#endif
+};
+
+class OmniboxPedalUpdateChrome : public OmniboxPedal {
+ public:
+  OmniboxPedalUpdateChrome();
+  void Execute(ExecutionContext& context) const override;
+  bool IsReadyToTrigger(
+      const AutocompleteProviderClient& client) const override;
+};
 
 // Returns the full set of encapsulated OmniboxPedal implementations.
 std::vector<std::unique_ptr<OmniboxPedal>> GetPedalImplementations();
diff --git a/components/omnibox/browser/omnibox_pedal_implementations_unittest.cc b/components/omnibox/browser/omnibox_pedal_implementations_unittest.cc
new file mode 100644
index 0000000..59ef623
--- /dev/null
+++ b/components/omnibox/browser/omnibox_pedal_implementations_unittest.cc
@@ -0,0 +1,56 @@
+// Copyright 2018 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.
+
+#include "components/omnibox/browser/omnibox_pedal_implementations.h"
+
+#include "base/strings/utf_string_conversions.h"
+#include "base/test/scoped_task_environment.h"
+#include "base/time/time.h"
+#include "components/omnibox/browser/mock_autocomplete_provider_client.h"
+#include "components/omnibox/browser/omnibox_pedal_provider.h"
+#include "components/omnibox/browser/test_omnibox_client.h"
+#include "components/omnibox/browser/test_omnibox_edit_controller.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+class OmniboxPedalImplementationsTest : public testing::Test {
+ protected:
+  OmniboxPedalImplementationsTest()
+      : omnibox_client_(new TestOmniboxClient),
+        omnibox_edit_controller_(new TestOmniboxEditController) {}
+
+  base::test::ScopedTaskEnvironment task_environment_;
+  std::unique_ptr<TestOmniboxClient> omnibox_client_;
+  std::unique_ptr<TestOmniboxEditController> omnibox_edit_controller_;
+};
+
+TEST_F(OmniboxPedalImplementationsTest, ClientReadiesPedalUpdateChrome) {
+  MockAutocompleteProviderClient client;
+  const OmniboxPedalUpdateChrome pedal;
+  EXPECT_EQ(false, pedal.IsReadyToTrigger(client));
+  client.set_browser_update_available(true);
+  EXPECT_EQ(true, pedal.IsReadyToTrigger(client));
+}
+
+TEST_F(OmniboxPedalImplementationsTest, ProviderFiltersPedalUpdateChrome) {
+  MockAutocompleteProviderClient client;
+  OmniboxPedalProvider provider(client);
+  const base::string16 trigger = base::ASCIIToUTF16("update chrome");
+  const OmniboxPedal* pedal = provider.FindPedalMatch(trigger);
+  EXPECT_EQ(pedal, nullptr) << "Pedal not filtered by condition.";
+  client.set_browser_update_available(true);
+  pedal = provider.FindPedalMatch(trigger);
+  EXPECT_NE(pedal, nullptr) << "Pedal not discovered though condition is met.";
+  EXPECT_TRUE(pedal->IsTriggerMatch(trigger));
+}
+
+TEST_F(OmniboxPedalImplementationsTest, PedalClearBrowsingDataExecutes) {
+  MockAutocompleteProviderClient client;
+  base::TimeTicks match_selection_timestamp;
+  OmniboxPedal::ExecutionContext context(
+      *omnibox_client_, *omnibox_edit_controller_, match_selection_timestamp);
+  const OmniboxPedalClearBrowsingData pedal;
+  pedal.Execute(context);
+  const GURL& url = omnibox_edit_controller_->destination_url();
+  EXPECT_EQ(url, GURL("chrome://settings/clearBrowserData"));
+}
diff --git a/components/omnibox/browser/omnibox_pedal_provider.h b/components/omnibox/browser/omnibox_pedal_provider.h
index 67e4e7a..d85d930 100644
--- a/components/omnibox/browser/omnibox_pedal_provider.h
+++ b/components/omnibox/browser/omnibox_pedal_provider.h
@@ -18,7 +18,8 @@
   explicit OmniboxPedalProvider(AutocompleteProviderClient& client);
   ~OmniboxPedalProvider();
 
-  // Returns the Pedal triggered by given match_text or nullptr if none trigger.
+  // Returns the Pedal triggered by given |match_text| or nullptr if none
+  // trigger.
   OmniboxPedal* FindPedalMatch(const base::string16& match_text) const;
 
  protected:
diff --git a/components/omnibox/browser/omnibox_pedal_unittest.cc b/components/omnibox/browser/omnibox_pedal_unittest.cc
index a9faca9..511f3a7 100644
--- a/components/omnibox/browser/omnibox_pedal_unittest.cc
+++ b/components/omnibox/browser/omnibox_pedal_unittest.cc
@@ -5,51 +5,72 @@
 #include "components/omnibox/browser/omnibox_pedal.h"
 
 #include "base/strings/utf_string_conversions.h"
-#include "base/test/scoped_task_environment.h"
-#include "base/time/time.h"
-#include "components/omnibox/browser/mock_autocomplete_provider_client.h"
+#include "components/omnibox/browser/omnibox_pedal_implementations.h"
 #include "components/omnibox/browser/omnibox_pedal_provider.h"
-#include "components/omnibox/browser/test_omnibox_client.h"
-#include "components/omnibox/browser/test_omnibox_edit_controller.h"
+#include "components/strings/grit/components_strings.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "url/gurl.h"
 
 class OmniboxPedalTest : public testing::Test {
  protected:
-  OmniboxPedalTest()
-      : omnibox_client_(new TestOmniboxClient),
-        omnibox_edit_controller_(new TestOmniboxEditController) {}
-
-  base::test::ScopedTaskEnvironment task_environment_;
-  std::unique_ptr<TestOmniboxClient> omnibox_client_;
-  std::unique_ptr<TestOmniboxEditController> omnibox_edit_controller_;
+  OmniboxPedalTest() {}
 };
 
-TEST_F(OmniboxPedalTest, PedalExecutes) {
-  MockAutocompleteProviderClient client;
-  OmniboxPedalProvider provider(client);
-  base::TimeTicks match_selection_timestamp;
-  OmniboxPedal::ExecutionContext context(
-      *omnibox_client_, *omnibox_edit_controller_, match_selection_timestamp);
-  {
-    const base::string16 trigger = base::ASCIIToUTF16("clear history");
-    const OmniboxPedal* pedal = provider.FindPedalMatch(trigger);
-    EXPECT_NE(pedal, nullptr) << "Pedal not registered or not triggered.";
-    EXPECT_TRUE(pedal->IsTriggerMatch(trigger));
-    pedal->Execute(context);
-    const GURL& url = omnibox_edit_controller_->destination_url();
-    EXPECT_EQ(url, GURL("chrome://settings/clearBrowserData"));
-  }
+TEST_F(OmniboxPedalTest, SynonymGroupErasesFirstMatchOnly) {
+  const auto group = OmniboxPedal::SynonymGroup(true, {
+                                                          "hello",
+                                                          "hi",
+                                                      });
+  base::string16 text = base::ASCIIToUTF16("hello hi world");
+  const bool found = group.EraseFirstMatchIn(text);
+  EXPECT_TRUE(found);
+  // Only the first representative should be removed.
+  EXPECT_EQ(text, base::ASCIIToUTF16(" hi world"));
 }
 
-TEST_F(OmniboxPedalTest, PedalIsFiltered) {
-  MockAutocompleteProviderClient client;
-  OmniboxPedalProvider provider(client);
-  const base::string16 trigger = base::ASCIIToUTF16("update chrome");
-  const OmniboxPedal* pedal = provider.FindPedalMatch(trigger);
-  EXPECT_EQ(pedal, nullptr) << "Pedal not filtered by condition.";
-  client.set_browser_update_available(true);
-  pedal = provider.FindPedalMatch(trigger);
-  EXPECT_NE(pedal, nullptr) << "Pedal not discovered though condition is met.";
-  EXPECT_TRUE(pedal->IsTriggerMatch(trigger));
-}
\ No newline at end of file
+TEST_F(OmniboxPedalTest, SynonymGroupsDriveConceptMatches) {
+  OmniboxPedal test_pedal(
+      OmniboxPedal::LabelStrings(
+          IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT,
+          IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_HINT_SHORT,
+          IDS_OMNIBOX_PEDAL_CLEAR_BROWSING_DATA_SUGGESTION_CONTENTS),
+      GURL(),
+      {
+          "test trigger phrase",
+      },
+      {
+          OmniboxPedal::SynonymGroup(false,
+                                     {
+                                         "optional",
+                                     }),
+          OmniboxPedal::SynonymGroup(true,
+                                     {
+                                         "required_a",
+                                     }),
+          OmniboxPedal::SynonymGroup(true,
+                                     {
+                                         "required_b",
+                                     }),
+      });
+  const auto is_concept_match = [&](const char* text) {
+    return test_pedal.IsConceptMatch(base::ASCIIToUTF16(text));
+  };
+
+  // As long as required synonym groups are present, order shouldn't matter.
+  EXPECT_TRUE(is_concept_match("required_a required_b"));
+  EXPECT_TRUE(is_concept_match("required_b required_a"));
+
+  // Optional groups may be added without stopping trigger.
+  EXPECT_TRUE(is_concept_match("required_a required_b optional"));
+  EXPECT_TRUE(is_concept_match("required_a optional required_b"));
+  EXPECT_TRUE(is_concept_match("optional required_b required_a"));
+
+  // Any required group's absence will stop trigger.
+  EXPECT_FALSE(is_concept_match("required_a optional"));
+  EXPECT_FALSE(is_concept_match("nonsense"));
+  EXPECT_FALSE(is_concept_match("nonsense optional"));
+
+  // Presence of extra text will stop trigger even with all required present.
+  EXPECT_FALSE(is_concept_match("required_a required_b nonsense optional"));
+  EXPECT_FALSE(is_concept_match("required_b required_a nonsense"));
+}