Cheer up spell-checking code

chrome/browser/spellchecker/spellcheck_custom_dictionary.cc

 // Copyright (c) 2012 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 "chrome/browser/spellchecker/spellcheck_custom_dictionary.h"
 
 #include <stddef.h>
 #include <functional>
 #include <utility>
 
 #include "base/files/file_util.h"
 #include "base/files/important_file_writer.h"
 #include "base/md5.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
+#include "chrome/browser/spellchecker/set_difference_container.h"
 #include "chrome/browser/spellchecker/spellcheck_host_metrics.h"
 #include "chrome/common/chrome_constants.h"
 #include "chrome/common/spellcheck_common.h"
 #include "content/public/browser/browser_thread.h"
 #include "sync/api/sync_change.h"
 #include "sync/api/sync_error_factory.h"
 #include "sync/protocol/sync.pb.h"
 
 using content::BrowserThread;
 
@@ skipping 62 matching lines @@
              base::TrimWhitespaceASCII(word, base::TRIM_ALL, &tmp);
 }
 
 // Removes duplicate and invalid words from |to_add| word list. Looks for
 // duplicates in both |to_add| and |existing| word lists. Returns a bitmap of
 // |ChangeSanitationResult| values.
 int SanitizeWordsToAdd(const std::set<std::string>& existing,
                        std::set<std::string>* to_add) {
   DCHECK(to_add);
   // Do not add duplicate words.
-  std::set<std::string> new_words =
-      base::STLSetDifference<std::set<std::string>>(*to_add, existing);
+  spellcheck::set_difference_container<std::set<std::string>,
+                                       std::set<std::string> >

[please use gerrit instead, 2016/02/03 23:59:11]

No space inside of ">>".

[Kevin Bailey, 2016/02/04 16:34:12]

Done.

+     new_words(*to_add, existing);
   int result = VALID_CHANGE;
-  if (to_add->size() != new_words.size())
-    result |= DETECTED_DUPLICATE_WORDS;
+  unsigned new_words_size = 0;

[please use gerrit instead, 2016/02/03 23:59:11]

size_t, since we're comparing it to std::set::size(), which returns a size_t. A
size_t can be different from "unsigned int" on some platforms. For example, it
could be "unsigned long".

[Kevin Bailey, 2016/02/04 16:34:12]

If true, the unsigned would be promoted. I think you're think of the dangers of
comparing signed and unsigned.

[groby-ooo-7-16, 2016/02/04 19:38:36]

We're trying to avoid implicit promotions. 

Quoth the Chromium style guide: 
  Use size_t for object and allocation sizes, object counts, array and pointer
offsets, vector indices, and so on

   // Do not add invalid words.
   std::set<std::string> valid_new_words;
   for (const std::string& word : new_words) {
+    ++new_words_size;
     if (IsValidWord(word))
       valid_new_words.insert(valid_new_words.end(), word);
   }
-  if (valid_new_words.size() != new_words.size())
+  if (to_add->size() != new_words_size)
+    result |= DETECTED_DUPLICATE_WORDS;
+  if (valid_new_words.size() != new_words_size)
     result |= DETECTED_INVALID_WORDS;
   // Save the sanitized words to be added.
   std::swap(*to_add, valid_new_words);
   return result;
 }
 
 // Loads and returns the custom spellcheck dictionary from |path|. Must be
 // called on the file thread.
 scoped_ptr<SpellcheckCustomDictionary::LoadFileResult>
 LoadDictionaryFileReliably(const base::FilePath& path) {
@@ skipping 317 matching lines @@
         fix_invalid_file_.callback());
   }
 }
 
 void SpellcheckCustomDictionary::Apply(const Change& dictionary_change) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   if (!dictionary_change.to_add().empty()) {
     words_.insert(dictionary_change.to_add().begin(),
                   dictionary_change.to_add().end());
   }
-  if (!dictionary_change.to_remove().empty()) {
-    std::set<std::string> updated_words =
-        base::STLSetDifference<std::set<std::string>>(
-            words_, dictionary_change.to_remove());
-    std::swap(words_, updated_words);
-  }
+  for (const auto& word : dictionary_change.to_remove())
+    words_.erase(word);

[please use gerrit instead, 2016/02/03 23:59:11]

Let's not switch this algorithm, because it's O(n*log(n)), as opposed to the old
one, which is O(n).

[Kevin Bailey, 2016/02/04 16:34:12]

The old one is very O(n ln(n)). :) Consider:

line 445: go through ...to_add() and insert them in a set<>
line 450: go through ...to_remove() and insert them in a new set<>
line 449: assign to yet another set<>, but here you *might* get an RVO, or you
might not and hit another O(n ln(n))

The new code is also n.ln(n) but at least doesn't create any new sets<>s, and
IMHO is much more easy to read.

[groby-ooo-7-16, 2016/02/04 19:38:36]

Even if it were an O(n) vs O(n ln n) difference - and it isn't, STLSetDifference
is a O(n ln n) because it inserts -  it _really_ doesn't matter that much -
because changes and dictionaries are usually pretty small.

In terms of readability, I agree with Kevin - this is slightly better. IIRC we
used STLSetDifference because pre-C++11, the for loop was a bit more hideous to
read than this. 

As Bob Dylan says, the times, they are a-changing ;)

So let's do Kevin's version - unless I suffer from E_LOW_COFFEE and am missing
something critical?

(And if we were _really_ performance-obsessed, we'd handcode a loop and use the
hinting insert. But we really aren't. Really :)


On 2016/02/04 16:34:12, Kevin Bailey wrote:

 }
 
 void SpellcheckCustomDictionary::FixInvalidFile(
     scoped_ptr<LoadFileResult> load_file_result) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   BrowserThread::PostTask(
       BrowserThread::FILE, FROM_HERE,
       base::Bind(&SavePassedWordsToDictionaryFileReliably,
                  custom_dictionary_path_, base::Passed(&load_file_result)));
 }
@@ skipping 62 matching lines @@
 }
 
 void SpellcheckCustomDictionary::Notify(const Change& dictionary_change) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   if (!IsLoaded() || dictionary_change.empty())
     return;
   FOR_EACH_OBSERVER(Observer,
                     observers_,
                     OnCustomDictionaryChanged(dictionary_change));
 }