Omnibox: Make Keyword Provide More Generous with Matching

components/search_engines/template_url_service.cc

 // Copyright 2014 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/search_engines/template_url_service.h"
 
 #include <algorithm>
 #include <utility>
 
 #include "base/auto_reset.h"
 #include "base/command_line.h"
 #include "base/compiler_specific.h"
 #include "base/guid.h"
 #include "base/i18n/case_conversion.h"
 #include "base/memory/scoped_vector.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/prefs/pref_service.h"
 #include "base/profiler/scoped_tracker.h"
 #include "base/stl_util.h"
 #include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "base/time/default_clock.h"
 #include "base/time/time.h"
+#include "components/omnibox/browser/omnibox_field_trial.h"
 #include "components/pref_registry/pref_registry_syncable.h"
 #include "components/rappor/rappor_service.h"
 #include "components/search_engines/search_engines_pref_names.h"
 #include "components/search_engines/search_host_to_urls_map.h"
 #include "components/search_engines/search_terms_data.h"
 #include "components/search_engines/template_url.h"
 #include "components/search_engines/template_url_prepopulate_data.h"
 #include "components/search_engines/template_url_service_client.h"
 #include "components/search_engines/template_url_service_observer.h"
 #include "components/search_engines/util.h"
@@ skipping 107 matching lines @@
   int num_dupes = 0;
   for (std::map<std::string, int>::const_iterator it = duplicates.begin();
       it != duplicates.end(); ++it) {
     if (it->second > 1)
       num_dupes++;
   }
 
   UMA_HISTOGRAM_COUNTS_100("Search.SearchEngineDuplicateCounts", num_dupes);
 }
 
+// Returns the length of the registry portion of a hostname.  For example,
+// www.google.co.uk will return 5 (the length of co.uk).
+size_t GetRegistryLength(const base::string16& host) {
+  return net::registry_controlled_domains::GetRegistryLength(
+      base::UTF16ToUTF8(host),
+      net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES,
+      net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES);
+}
+
+// Returns the domain name (including registry) of a hostname.  For example,
+// www.google.co.uk will return google.co.uk.
+base::string16 GetDomainAndRegistry(const base::string16& host) {
+  return base::UTF8ToUTF16(
+      net::registry_controlled_domains::GetDomainAndRegistry(
+          base::UTF16ToUTF8(host),
+          net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES));
+}
+
+// Returns the length of the important part of the |keyword|, assumed to be
+// associated with the TemplateURL.  For instance, for the keyword
+// google.co.uk, this can return 6 (the length of google).

[Peter Kasting, 2015/11/12 20:36:11]

Nit: google -> "google"

[Mark P, 2015/11/12 21:42:49]

Done.

+size_t GetEffectiveKeywordLength(const base::string16& keyword,

[Peter Kasting, 2015/11/12 20:36:11]

Nit: Effective -> Meaningful

[Mark P, 2015/11/12 21:42:49]

Done.  Sorry I missed this during past revisions.

+                                 const TemplateURL* turl) {
+  if (OmniboxFieldTrial::KeywordRequiresRegistry())
+    return keyword.length();
+  const size_t registry_length = GetRegistryLength(keyword);
+  // If there's a registry, subtract the length of the registry portion of the
+  // keyword (e.g., co.uk) and an addition one for the dot that preceeds the
+  // registry.  Don't return something less than 0 regardless.

[Peter Kasting, 2015/11/12 20:36:11]

Nit: The point of the conditional is sort of obvious when you read it, so I'd
probably omit this sentence.

It might be clearer to write this code as something like:

  const size_t registry_length = GetRegistryLength(keyword);
  if (OmniboxFieldTrial::KeywordRequiresRegistry() || !registry_length)
    return keyword.length();
  // The meaningful keyword length is the length of any portion before the
  // registry ("co.uk") and its preceding dot.
  return std::max(keyword.length() - registry_length - 1, 0);

[Mark P, 2015/11/12 21:42:49]

Didn't restructure the beginning of this because I don't want to take the time
to compute registry lengths if the field trial isn't enabled.
Use your comment and (approximately) your code.  I needed a <int> type because
otherwise the compiler has trouble figuring out how to do the comparison (pasted
below in case you care).  I might be to do this by putting an appropriate
annotation on the "0", but I don't see what and the current <int> code is fine
with me.


../../components/search_engines/template_url_service.cc:184:10: error: no
matching function for call to 'max'
  return std::max(keyword.length() - (registry_length ? (registry_length + 1) :
0), 0);
         ^~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/algorithmfwd.h:356:5:
note: candidate template ignored: deduced conflicting types for parameter '_Tp'
('unsigned long' vs. 'int')
    max(const _Tp&, const _Tp&);
    ^
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:4236:5:
note: candidate template ignored: could not match
'initializer_list<type-parameter-0-0>' against 'unsigned long'
    max(initializer_list<_Tp> __l, _Compare __comp)
    ^
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/algorithmfwd.h:360:5:
note: candidate function template not viable: requires 3 arguments, but 2 were
provided
    max(const _Tp&, const _Tp&, _Compare);
    ^
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:4231:5:
note: candidate function template not viable: requires single argument '__l',
but 2 arguments were provided
    max(initializer_list<_Tp> __l)
    ^
1 error generated.

+  if (registry_length >= keyword.length())
+    return 0;
+  return keyword.length() - (registry_length ? (registry_length + 1) : 0);
+}
+
 }  // namespace
 
 
 // TemplateURLService::LessWithPrefix -----------------------------------------
 
 class TemplateURLService::LessWithPrefix {
  public:
   // We want to find the set of keywords that begin with a prefix.  The STL
   // algorithms will return the set of elements that are "equal to" the
   // prefix, where "equal(x, y)" means "!(cmp(x, y) || cmp(y, x))".  When
   // cmp() is the typical std::less<>, this results in lexicographic equality;
   // we need to extend this to mark a prefix as "not less than" a keyword it
   // begins, which will cause the desired elements to be considered "equal to"
   // the prefix.  Note: this is still a strict weak ordering, as required by
   // equal_range() (though I will not prove that here).
   //
   // Unfortunately the calling convention is not "prefix and element" but
   // rather "two elements", so we pass the prefix as a fake "element" which has
   // a NULL KeywordDataElement pointer.
   bool operator()(const KeywordToTemplateMap::value_type& elem1,
                   const KeywordToTemplateMap::value_type& elem2) const {
-    return (elem1.second == NULL) ?
+    return (elem1.second.first == NULL) ?
         (elem2.first.compare(0, elem1.first.length(), elem1.first) > 0) :
         (elem1.first < elem2.first);
   }
 };
 
 
 // TemplateURLService ---------------------------------------------------------
 
 TemplateURLService::TemplateURLService(
     PrefService* prefs,
@@ skipping 153 matching lines @@
   // We don't have a TemplateURL with keyword.  We still may not allow this
   // keyword if there's evidence we may have created this keyword before and
   // the user renamed it (because, for instance, the keyword is a common word
   // that may interfere with search queries).  An easy heuristic for this is
   // whether the user has a TemplateURL that has been manually modified (e.g.,
   // renamed) connected to the same host.
   return !url.is_valid() || url.host().empty() ||
       CanAddAutogeneratedKeywordForHost(url.host());
 }
 
-void TemplateURLService::FindMatchingKeywords(
+void TemplateURLService::AddMatchingKeywords(
     const base::string16& prefix,
-    bool support_replacement_only,
-    TemplateURLVector* matches) {
-  // Sanity check args.
-  if (prefix.empty())
-    return;
-  DCHECK(matches != NULL);
-  DCHECK(matches->empty());  // The code for exact matches assumes this.
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  AddMatchingKeywordsHelper(
+      keyword_to_template_map_, prefix, supports_replacement_only, matches);
+}
 
-  // Required for VS2010: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair
-  TemplateURL* const kNullTemplateURL = NULL;
-
-  // Find matching keyword range.  Searches the element map for keywords
-  // beginning with |prefix| and stores the endpoints of the resulting set in
-  // |match_range|.
-  const std::pair<KeywordToTemplateMap::const_iterator,
-                  KeywordToTemplateMap::const_iterator> match_range(
-      std::equal_range(
-          keyword_to_template_map_.begin(), keyword_to_template_map_.end(),
-          KeywordToTemplateMap::value_type(prefix, kNullTemplateURL),
-          LessWithPrefix()));
-
-  // Return vector of matching keywords.
-  for (KeywordToTemplateMap::const_iterator i(match_range.first);
-       i != match_range.second; ++i) {
-    if (!support_replacement_only ||
-        i->second->url_ref().SupportsReplacement(search_terms_data()))
-      matches->push_back(i->second);
-  }
+void TemplateURLService::AddMatchingDomainKeywords(
+    const base::string16& prefix,
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  AddMatchingKeywordsHelper(
+      keyword_domain_to_template_map_, prefix, supports_replacement_only,
+      matches);
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
     const base::string16& keyword) {
   KeywordToTemplateMap::const_iterator elem(
       keyword_to_template_map_.find(keyword));
   if (elem != keyword_to_template_map_.end())
-    return elem->second;
+    return elem->second.first;
   return (!loaded_ &&
       initial_default_search_provider_.get() &&
       (initial_default_search_provider_->keyword() == keyword)) ?
       initial_default_search_provider_.get() : NULL;
 }
 
 TemplateURL* TemplateURLService::GetTemplateURLForGUID(
     const std::string& sync_guid) {
   GUIDToTemplateMap::const_iterator elem(guid_to_template_map_.find(sync_guid));
   if (elem != guid_to_template_map_.end())
@@ skipping 1012 matching lines @@
   }
 
   // Request a server check for the correct Google URL if Google is the
   // default search engine.
   RequestGoogleURLTrackerServerCheckIfNecessary();
 }
 
 void TemplateURLService::RemoveFromMaps(TemplateURL* template_url) {
   const base::string16& keyword = template_url->keyword();
   DCHECK_NE(0U, keyword_to_template_map_.count(keyword));
-  if (keyword_to_template_map_[keyword] == template_url) {
+  if (keyword_to_template_map_[keyword].first == template_url) {
     // We need to check whether the keyword can now be provided by another
     // TemplateURL.  See the comments in AddToMaps() for more information on
     // extension keywords and how they can coexist with non-extension keywords.
     // In the case of more than one extension, we use the most recently
     // installed (which will be the most recently added, which will have the
     // highest ID).
     TemplateURL* best_fallback = NULL;
     for (TemplateURLVector::const_iterator i(template_urls_.begin());
          i != template_urls_.end(); ++i) {
       TemplateURL* turl = *i;
       // This next statement relies on the fact that there can only be one
       // non-Omnibox API TemplateURL with a given keyword.
       if ((turl != template_url) && (turl->keyword() == keyword) &&
           (!best_fallback ||
            (best_fallback->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) ||
            ((turl->GetType() == TemplateURL::OMNIBOX_API_EXTENSION) &&
             (turl->id() > best_fallback->id()))))
         best_fallback = turl;
     }
-    if (best_fallback)
-      keyword_to_template_map_[keyword] = best_fallback;
-    else
+    RemoveFromDomainMap(template_url);
+    if (best_fallback) {
+      keyword_to_template_map_[keyword] =
+          std::make_pair(best_fallback,
+                         GetEffectiveKeywordLength(keyword, best_fallback));
+      AddToDomainMap(best_fallback);
+    } else {
       keyword_to_template_map_.erase(keyword);
+    }
   }
 
   if (template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION)
     return;
 
   if (!template_url->sync_guid().empty())
     guid_to_template_map_.erase(template_url->sync_guid());
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_) {
     provider_map_->Remove(template_url);
   }
 }
 
 void TemplateURLService::AddToMaps(TemplateURL* template_url) {
   bool template_url_is_omnibox_api =
       template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
   const base::string16& keyword = template_url->keyword();
   KeywordToTemplateMap::const_iterator i =
       keyword_to_template_map_.find(keyword);
   if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = template_url;
+    keyword_to_template_map_[keyword] =
+        std::make_pair(template_url,
+                       GetEffectiveKeywordLength(keyword, template_url));
+    AddToDomainMap(template_url);
   } else {
-    const TemplateURL* existing_url = i->second;
+    const TemplateURL* existing_url = i->second.first;
     // We should only have overlapping keywords when at least one comes from
     // an extension.  In that case, the ranking order is:
     //   Manually-modified keywords > extension keywords > replaceable keywords
     // When there are multiple extensions, the last-added wins.
     bool existing_url_is_omnibox_api =
         existing_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
     DCHECK(existing_url_is_omnibox_api || template_url_is_omnibox_api);
     if (existing_url_is_omnibox_api ?
-        !CanReplace(template_url) : CanReplace(existing_url))
-      keyword_to_template_map_[keyword] = template_url;
+        !CanReplace(template_url) : CanReplace(existing_url)) {
+      RemoveFromDomainMap(existing_url);
+      keyword_to_template_map_[keyword] =
+          std::make_pair(template_url,
+                         GetEffectiveKeywordLength(keyword, template_url));
+      AddToDomainMap(template_url);
+    }
   }
 
   if (template_url_is_omnibox_api)
     return;
 
   if (!template_url->sync_guid().empty())
     guid_to_template_map_[template_url->sync_guid()] = template_url;
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_)
     provider_map_->Add(template_url, search_terms_data());
 }
 
+void TemplateURLService::RemoveFromDomainMap(const TemplateURL* template_url) {
+  const base::string16 domain = GetDomainAndRegistry(template_url->keyword());
+  if (domain.empty())
+    return;
+
+  for (KeywordDomainToTemplateMap::const_iterator it(
+           keyword_domain_to_template_map_.lower_bound(domain));
+       it != keyword_domain_to_template_map_.upper_bound(domain); ) {

[Peter Kasting, 2015/11/12 20:36:11]

You should pull the upper_bound() out of the loop here; it will remain valid
across erase() calls, and you don't want to recalculate it on every iteration.

Once this is done, going back to the equal_range() method of finding the upper
and lower bounds is more efficient.

I was mistaken to suggest remove_if() before since that can't be used with
associative containers, and I didn't point out that your previous code could
dereference a garbage iterator after erase() (but you fixed it anyway).  So I
think just combining equal_range() with this loop body is the best way to go.

[Mark P, 2015/11/12 21:42:49]

Still TODO.

[Mark P, 2015/11/12 23:18:41]

Good point.  Done, but then changed (see below)
Did equal_range() as you suggested, but it's longer than the previous code.  I
prefer the earlier version; I don't see what equal_range buys you that
lower_bound and upper_bound does not.  It's simply an extra variable.

+    if (it->second.first == template_url) {

[Peter Kasting, 2015/11/12 20:36:11]

Nit: {} unnecessary

[Mark P, 2015/11/12 21:42:49]

Done.

+      it = keyword_domain_to_template_map_.erase(it);
+    } else {
+      ++it;
+    }
+  }
+}
+
+void TemplateURLService::AddToDomainMap(TemplateURL* template_url) {
+  const base::string16 domain = GetDomainAndRegistry(template_url->keyword());
+  // Only bother adding an entry to the domain map if its key in the domain
+  // map would be different from the key in the regular map.
+  if (domain != template_url->keyword()) {
+    keyword_domain_to_template_map_.insert(std::make_pair(
+        domain,
+        std::make_pair(template_url,
+                       GetEffectiveKeywordLength(domain, template_url))));
+  }
+}
+
 // Helper for partition() call in next function.
 bool HasValidID(TemplateURL* t_url) {
   return t_url->id() != kInvalidTemplateURLID;
 }
 
 void TemplateURLService::SetTemplateURLs(TemplateURLVector* urls) {
   // Partition the URLs first, instead of implementing the loops below by simply
   // scanning the input twice.  While it's not supposed to happen normally, it's
   // possible for corrupt databases to return multiple entries with the same
   // keyword.  In this case, the first loop may delete the first entry when
@@ skipping 91 matching lines @@
                                         const TemplateURL& new_values) {
   DCHECK(existing_turl);
   if (std::find(template_urls_.begin(), template_urls_.end(), existing_turl) ==
       template_urls_.end())
     return false;
 
   DCHECK_NE(TemplateURL::OMNIBOX_API_EXTENSION, existing_turl->GetType());
 
   base::string16 old_keyword(existing_turl->keyword());
   keyword_to_template_map_.erase(old_keyword);
+  RemoveFromDomainMap(existing_turl);
   if (!existing_turl->sync_guid().empty())
     guid_to_template_map_.erase(existing_turl->sync_guid());
 
   // |provider_map_| is only initialized after loading has completed.
   if (loaded_)
     provider_map_->Remove(existing_turl);
 
   TemplateURLID previous_id = existing_turl->id();
   existing_turl->CopyFrom(new_values);
   existing_turl->data_.id = previous_id;
 
   if (loaded_) {
     provider_map_->Add(existing_turl, search_terms_data());
   }
 
   const base::string16& keyword = existing_turl->keyword();
   KeywordToTemplateMap::const_iterator i =
       keyword_to_template_map_.find(keyword);
   if (i == keyword_to_template_map_.end()) {
-    keyword_to_template_map_[keyword] = existing_turl;
+    keyword_to_template_map_[keyword] =
+        std::make_pair(existing_turl,
+                       GetEffectiveKeywordLength(keyword, existing_turl));
+    AddToDomainMap(existing_turl);
   } else {
     // We can theoretically reach here in two cases:
     //   * There is an existing extension keyword and sync brings in a rename of
     //     a non-extension keyword to match.  In this case we just need to pick
     //     which keyword has priority to update the keyword map.
     //   * Autogeneration of the keyword for a Google default search provider
     //     at load time causes it to conflict with an existing keyword.  In this
     //     case we delete the existing keyword if it's replaceable, or else undo
     //     the change in keyword for |existing_turl|.
-    TemplateURL* existing_keyword_turl = i->second;
+    TemplateURL* existing_keyword_turl = i->second.first;
     if (existing_keyword_turl->GetType() != TemplateURL::NORMAL) {
-      if (!CanReplace(existing_turl))
-        keyword_to_template_map_[keyword] = existing_turl;
+      if (!CanReplace(existing_turl)) {
+        keyword_to_template_map_[keyword] =
+            std::make_pair(existing_turl,
+                           GetEffectiveKeywordLength(keyword, existing_turl));
+        AddToDomainMap(existing_turl);
+      }
     } else {
       if (CanReplace(existing_keyword_turl)) {
         RemoveNoNotify(existing_keyword_turl);
       } else {
         existing_turl->data_.SetKeyword(old_keyword);
-        keyword_to_template_map_[old_keyword] = existing_turl;
+        keyword_to_template_map_[old_keyword] =
+            std::make_pair(existing_turl,
+                           GetEffectiveKeywordLength(old_keyword,
+                                                     existing_turl));
+        AddToDomainMap(existing_turl);
       }
     }
   }
   if (!existing_turl->sync_guid().empty())
     guid_to_template_map_[existing_turl->sync_guid()] = existing_turl;
 
   if (web_data_service_.get())
     web_data_service_->UpdateKeyword(existing_turl->data());
 
   // Inform sync of the update.
@@ skipping 104 matching lines @@
   bool something_changed = false;
   for (TemplateURLVector::iterator i(template_urls_.begin());
        i != template_urls_.end(); ++i) {
     TemplateURL* t_url = *i;
     if (t_url->HasGoogleBaseURLs(search_terms_data())) {
       TemplateURL updated_turl(t_url->data());
       updated_turl.ResetKeywordIfNecessary(search_terms_data(), false);
       KeywordToTemplateMap::const_iterator existing_entry =
           keyword_to_template_map_.find(updated_turl.keyword());
       if ((existing_entry != keyword_to_template_map_.end()) &&
-          (existing_entry->second != t_url)) {
+          (existing_entry->second.first != t_url)) {
         // The new autogenerated keyword conflicts with another TemplateURL.
         // Overwrite it if it's replaceable; otherwise, leave |t_url| using its
         // current keyword.  (This will not prevent |t_url| from auto-updating
         // the keyword in the future if the conflicting TemplateURL disappears.)
         // Note that we must still update |t_url| in this case, or the
         // |provider_map_| will not be updated correctly.
-        if (CanReplace(existing_entry->second))
-          RemoveNoNotify(existing_entry->second);
+        if (CanReplace(existing_entry->second.first))
+          RemoveNoNotify(existing_entry->second.first);
         else
           updated_turl.data_.SetKeyword(t_url->keyword());
       }
       something_changed = true;
       // This will send the keyword change to sync.  Note that other clients
       // need to reset the keyword to an appropriate local value when this
       // change arrives; see CreateTemplateURLFromTemplateURLAndSyncData().
       UpdateNoNotify(t_url, updated_turl);
     }
   }
@@ skipping 494 matching lines @@
   if (new_guid.empty()) {
     default_search_manager_.ClearUserSelectedDefaultSearchEngine();
     return;
   }
 
   TemplateURL* turl = GetTemplateURLForGUID(new_guid);
   if (turl)
     default_search_manager_.SetUserSelectedDefaultSearchEngine(turl->data());
 }
 
+template <typename Container>
+void TemplateURLService::AddMatchingKeywordsHelper(
+    const Container& keyword_to_template_map,
+    const base::string16& prefix,
+    bool supports_replacement_only,
+    TURLsAndMeaningfulLengths* matches) {
+  // Sanity check args.
+  if (prefix.empty())
+    return;
+  DCHECK(matches);
+
+  // Find matching keyword range.  Searches the element map for keywords
+  // beginning with |prefix| and stores the endpoints of the resulting set in
+  // |match_range|.
+  const std::pair<typename Container::const_iterator,
+                  typename Container::const_iterator> match_range(

[Peter Kasting, 2015/11/12 20:36:11]

Nit: I'd probably use auto here

[Mark P, 2015/11/12 21:42:49]

Done.

+      std::equal_range(
+          keyword_to_template_map.begin(), keyword_to_template_map.end(),
+          typename Container::value_type(prefix,
+                                         std::make_pair(nullptr, 0)),
+          LessWithPrefix()));
+
+  // Add to vector of matching keywords.
+  for (typename Container::const_iterator i(match_range.first);
+    i != match_range.second; ++i) {
+    if (!supports_replacement_only ||
+        i->second.first->url_ref().SupportsReplacement(search_terms_data()))
+      matches->push_back(i->second);
+  }
+}
+
 TemplateURL* TemplateURLService::FindPrepopulatedTemplateURL(
     int prepopulated_id) {
   for (TemplateURLVector::const_iterator i = template_urls_.begin();
        i != template_urls_.end(); ++i) {
     if ((*i)->prepopulate_id() == prepopulated_id)
       return *i;
   }
   return NULL;
 }
 
@@ skipping 38 matching lines @@
 
   if (most_recently_intalled_default) {
     base::AutoReset<DefaultSearchChangeOrigin> change_origin(
         &dsp_change_origin_, DSP_CHANGE_OVERRIDE_SETTINGS_EXTENSION);
     default_search_manager_.SetExtensionControlledDefaultSearchEngine(
         most_recently_intalled_default->data());
   } else {
     default_search_manager_.ClearExtensionControlledDefaultSearchEngine();
   }
 }