text: // 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.
  
  #ifndef COMPONENTS_OMNIBOX_BROWSER_ACTIONS_OMNIBOX_PEDAL_H_
  #define COMPONENTS_OMNIBOX_BROWSER_ACTIONS_OMNIBOX_PEDAL_H_
  
  #include <unordered_set>
  #include <vector>
  
  #include "base/gtest_prod_util.h"
  #include "base/values.h"
  #include "build/build_config.h"
  #include "components/omnibox/browser/actions/omnibox_action.h"
  #include "components/omnibox/browser/actions/omnibox_pedal_concepts.h"
  #include "components/omnibox/browser/buildflags.h"
  #include "url/gurl.h"
  
  // Conceptually, a Pedal is a fixed action that can be taken by the user
  // pressing a button or taking a new dedicated suggestion when some
  // associated intention is detected in an omnibox match suggestion.
  // The typical action is to navigate to an internal Chrome surface
  // like settings, but other actions like translation or launching
  // an incognito window are possible.  The intention is detected by
  // checking trigger queries against suggested match queries.
  class OmniboxPedal : public OmniboxAction {
   public:
    struct Token {
      // Token identifier from the common token dictionary.
      int id;
  
      // Index of the next unconsumed token node. Initially this is set to
      // the token's own index, indicating this token is unconsumed. Calls
      // to |TokenSequence::Consume| may then update it to greater values,
      // indicating that this token is consumed.
      size_t link;
    };
  
    // This is a specialized container for the sequence matching algorithm.
    // It is intended only for single-threaded access by OmniboxPedal classes.
    class TokenSequence {
     public:
      // Construct with reserved size; used when loading real data.
      explicit TokenSequence(size_t reserve_size);
  
      // Construct with given sequence of |token_ids|; used by tests.
      explicit TokenSequence(std::vector<int> token_ids);
  
      // Don't use copies. They were necessary with old algorithm,
      // but this structure is amenable to efficient resets on kept instances.
      TokenSequence(const TokenSequence&) = delete;
      TokenSequence& operator=(const TokenSequence&) = delete;
      TokenSequence(TokenSequence&&);
      TokenSequence& operator=(TokenSequence&&);
      ~TokenSequence();
  
      // Returns true if all tokens are consumed (true for empty sequences).
      bool IsFullyConsumed();
  
      // Returns the number of unconsumed tokens remaining. Used by tests.
      size_t CountUnconsumed() const;
  
      // Add token with given |id| to sequence.
      void Add(int id);
  
      // Clears all tokens from this sequence.
      inline void Clear() { tokens_.clear(); }
  
      // Initializes all links in sequence to their own index, indicating
      // unconsumed state for all. This is needed after calls to Erase.
      void ResetLinks();
  
      // Removes one or more instances of |erase_sequence| from this sequence
      // by erasing token items from the |tokens_| container.
      // Returns true if this sequence was changed; false if no match is found.
      bool Erase(const TokenSequence& erase_sequence, bool erase_only_once);
  
      // Consumes one or more instances of |consume_sequence| from this sequence
      // by updating links on matching tokens. The container is not modified,
      // only its contained elements may be mutated.
      // Returns true if matches were found and consumed; false if no match.
      bool Consume(const TokenSequence& consume_sequence, bool consume_only_once);
  
      // Returns the total number of tokens, regardless of consumed status.
      inline size_t Size() const { return tokens_.size(); }
  
      // Returns collection memory estimate for tracing.
      size_t EstimateMemoryUsage() const;
  
     private:
      // Returns true if this sequence, starting at |index|, matches given
      // |sequence|. The |index_mask| can be used to disregard consumed status (0)
      // or require that all tokens must be unconsumed to match (~0).
      bool MatchesAt(const TokenSequence& sequence,
                     size_t index,
                     size_t index_mask) const;
  
      // Follows links on tokens starting at |from_index| and returns the first
      // unconsumed index. Returns |Size()| if no unconsumed token is found.
      size_t WalkToUnconsumedIndexFrom(size_t from_index);
  
      // Storage for tokens.
      std::vector<Token> tokens_;
    };
  
    struct SynonymGroupSpec {
      bool required;
      bool match_once;
      int message_id;
    };
  
    class SynonymGroup {
     public:
      // Note: synonyms must be specified in decreasing order by 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, bool match_once, size_t reserve_size);
      SynonymGroup(SynonymGroup&&);
      ~SynonymGroup();
      SynonymGroup(const SynonymGroup&) = delete;
      SynonymGroup& operator=(const SynonymGroup&) = delete;
      SynonymGroup& operator=(SynonymGroup&&);
  
      // Removes one or more matching synonyms from given |remaining| sequence if
      // any are found.  Returns true if checking may continue; false if no more
      // checking is required because what remains cannot be a concept match.
      // Note, if |fully_erase| is true and this method returns true, the
      // |remaining| container has changed structure so ResetLinks must be called.
      // This method doesn't call ResetLinks in that case, for efficiency.
      bool EraseMatchesIn(TokenSequence& remaining, bool fully_erase) const;
  
      // Add a synonym token sequence to this group.
      void AddSynonym(TokenSequence synonym);
  
      // When runtime data was preprocessed by pedal_processor,
      // it avoided the need to sort at runtime in Chromium, but with
      // the TC-based l10n technique, data loading needs to be robust
      // enough to handle various forms and orders in translation data.
      // Hence, a call to `SortSynonyms` is required after all calls
      // to `AddSynonym` are complete. We may eliminate this step
      // if we implement post-processing of the .xtb translation files.
      void SortSynonyms();
  
      // Estimates RAM usage in bytes for this synonym group.
      size_t EstimateMemoryUsage() const;
  
      // Erases sequences in ignore group from all synonyms in this group.
      void EraseIgnoreGroup(const SynonymGroup& ignore_group);
  
      // Returns true if this synonym group contains nontrivial data that can
      // be used by the matching algorithm.
      bool IsValid() 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_;
  
      // If this is true, then only the rightmost instance of first synonym found
      // will be taken from text being checked, and additional instances will
      // inhibit trigger because repetition actually changes meaning.  If false,
      // then all instances of all synonyms are taken (repetition is meaningless).
      bool match_once_;
  
      // 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<TokenSequence> synonyms_;
    };
  
    OmniboxPedal(OmniboxPedalId id, LabelStrings strings, GURL url);
  
    // Writes labels associated with this Pedal by taking named
    //  values from provided dictionary value |ui_strings|.
    void SetLabelStrings(const base::Value& ui_strings);
  
    // Sets the destination URL for the Pedal.
    void SetNavigationUrl(const GURL& url);
  
  #if (!defined(OS_ANDROID) || BUILDFLAG(ENABLE_VR)) && !defined(OS_IOS)
    // Returns the default vector icon to use for Pedals that do not specify one.
    static const gfx::VectorIcon& GetDefaultVectorIcon();
  #endif
  
    // Add a verbatim token sequence for direct matching.
    // This can improve user experience of omnibox pedals by ensuring that
    // button text entered verbatim is always a sufficient trigger. Since
    // button text labels are not always within the specified set of triggers,
    // it may be possible to discover a pedal, memorize the button
    // label, and then go seeking it out again with the button label, but
    // not find it. With the verbatim sequence, learning a pedal by label will
    // always make the pedal available with that exact input (ignoring case and
    // the common ignore group).
    void AddVerbatimSequence(TokenSequence sequence);
  
    // Move a synonym group into this Pedal's collection.
    void AddSynonymGroup(SynonymGroup&& group);
  
    // Specify synonym groups to load from localization strings.
    virtual std::vector<SynonymGroupSpec> SpecifySynonymGroups() const;
  
    OmniboxPedalId id() const { return id_; }
  
    // Sometimes pedals report different IDs for metrics, either to enable
    // feature discrimination (e.g. incognito mode) or to unify metrics
    // of closely related pedals (e.g. a ChromeOS specialization of a pedal).
    virtual OmniboxPedalId GetMetricsId() const;
  
    // If a sufficient set of triggering synonym groups are present in
    // match_sequence then it's a concept match and this returns true.  If a
    // required group is not present, or if match_sequence contains extraneous
    // tokens not covered by any synonym group, then it's not a concept match and
    // this returns false. |match_sequence| is consumed/mutated by this method.
    bool IsConceptMatch(TokenSequence& match_sequence) const;
  
    // OmniboxAction overrides:
    void RecordActionShown(size_t position) const override;
    void RecordActionExecuted(size_t position) const override;
  #if (!defined(OS_ANDROID) || BUILDFLAG(ENABLE_VR)) && !defined(OS_IOS)
    const gfx::VectorIcon& GetVectorIcon() const override;
  #endif
    size_t EstimateMemoryUsage() const override;
    int32_t GetID() const override;
  
   protected:
    FRIEND_TEST_ALL_PREFIXES(OmniboxPedalTest, SynonymGroupErasesFirstMatchOnly);
    FRIEND_TEST_ALL_PREFIXES(OmniboxPedalTest, SynonymGroupsDriveConceptMatches);
    FRIEND_TEST_ALL_PREFIXES(OmniboxPedalTest,
                             VerbatimSynonymGroupDrivesConceptMatches);
    FRIEND_TEST_ALL_PREFIXES(OmniboxPedalImplementationsTest,
                             UnorderedSynonymExpressionsAreConceptMatches);
  
    ~OmniboxPedal() override;
  
    OmniboxPedalId id_;
  
    // Before standard synonym group matching, we can check the verbatim
    // syonym group for direct matches, e.g. with the button label text.
    SynonymGroup verbatim_synonym_group_;
  
    std::vector<SynonymGroup> synonym_groups_;
  };
  
  #endif  // COMPONENTS_OMNIBOX_BROWSER_ACTIONS_OMNIBOX_PEDAL_H_
  