intermediate changes

ref:04088b5ce70b83f5eaf307a1743e0179beaeb170

5 files changed, 44 insertions, 73 deletions

diff --git a/contrib/libs/re2/re2/prefilter_tree.cc b/contrib/libs/re2/re2/prefilter_tree.cc
index fdf4e083c9..1e4eaffcae 100644
--- a/contrib/libs/re2/re2/prefilter_tree.cc
+++ b/contrib/libs/re2/re2/prefilter_tree.cc
@@ -8,7 +8,6 @@
 #include <algorithm>
 #include <map>
 #include <memory>
-#include <set>
 #include <string>
 #include <utility>
 #include <vector>
@@ -36,9 +35,6 @@ PrefilterTree::PrefilterTree(int min_atom_len)
 PrefilterTree::~PrefilterTree() {
   for (size_t i = 0; i < prefilter_vec_.size(); i++)
     delete prefilter_vec_[i];
-
-  for (size_t i = 0; i < entries_.size(); i++)
-    delete entries_[i].parents;
 }
 
 void PrefilterTree::Add(Prefilter* prefilter) {
@@ -67,7 +63,6 @@ void PrefilterTree::Compile(std::vector<std::string>* atom_vec) {
 
   compiled_ = true;
 
-  // TODO(junyer): Use std::unordered_set<Prefilter*> instead?
   NodeMap nodes;
   AssignUniqueIds(&nodes, atom_vec);
 
@@ -78,25 +73,21 @@ void PrefilterTree::Compile(std::vector<std::string>* atom_vec) {
   // not miss out on any regexps triggering by getting rid of a
   // prefilter node.
   for (size_t i = 0; i < entries_.size(); i++) {
-    StdIntMap* parents = entries_[i].parents;
-    if (parents->size() > 8) {
+    std::vector<int>& parents = entries_[i].parents;
+    if (parents.size() > 8) {
       // This one triggers too many things. If all the parents are AND
       // nodes and have other things guarding them, then get rid of
       // this trigger. TODO(vsri): Adjust the threshold appropriately,
       // make it a function of total number of nodes?
       bool have_other_guard = true;
-      for (StdIntMap::iterator it = parents->begin();
-           it != parents->end(); ++it) {
+      for (int parent : parents) {
         have_other_guard = have_other_guard &&
-            (entries_[it->first].propagate_up_at_count > 1);
+            (entries_[parent].propagate_up_at_count > 1);
       }
-
       if (have_other_guard) {
-        for (StdIntMap::iterator it = parents->begin();
-             it != parents->end(); ++it)
-          entries_[it->first].propagate_up_at_count -= 1;
-
-        parents->clear();  // Forget the parents
+        for (int parent : parents)
+          entries_[parent].propagate_up_at_count -= 1;
+        parents.clear();  // Forget the parents
       }
     }
   }
@@ -217,20 +208,7 @@ void PrefilterTree::AssignUniqueIds(NodeMap* nodes,
       node->set_unique_id(canonical->unique_id());
     }
   }
-  entries_.resize(nodes->size());
-
-  // Create parent StdIntMap for the entries.
-  for (int i = static_cast<int>(v.size()) - 1; i >= 0; i--) {
-    Prefilter* prefilter = v[i];
-    if (prefilter == NULL)
-      continue;
-
-    if (CanonicalNode(nodes, prefilter) != prefilter)
-      continue;
-
-    Entry* entry = &entries_[prefilter->unique_id()];
-    entry->parents = new StdIntMap();
-  }
+  entries_.resize(unique_id);
 
   // Fill the entries.
   for (int i = static_cast<int>(v.size()) - 1; i >= 0; i--) {
@@ -241,41 +219,34 @@ void PrefilterTree::AssignUniqueIds(NodeMap* nodes,
     if (CanonicalNode(nodes, prefilter) != prefilter)
       continue;
 
-    Entry* entry = &entries_[prefilter->unique_id()];
+    int id = prefilter->unique_id();
 
     switch (prefilter->op()) {
       default:
-      case Prefilter::ALL:
         LOG(DFATAL) << "Unexpected op: " << prefilter->op();
         return;
 
       case Prefilter::ATOM:
-        entry->propagate_up_at_count = 1;
+        entries_[id].propagate_up_at_count = 1;
         break;
 
       case Prefilter::OR:
       case Prefilter::AND: {
-        std::set<int> uniq_child;
+        // For each child, we append our id to the child's list of
+        // parent ids... unless we happen to have done so already.
+        // The number of appends is the number of unique children,
+        // which allows correct upward propagation from AND nodes.
+        int up_count = 0;
         for (size_t j = 0; j < prefilter->subs()->size(); j++) {
-          Prefilter* child = (*prefilter->subs())[j];
-          Prefilter* canonical = CanonicalNode(nodes, child);
-          if (canonical == NULL) {
-            LOG(DFATAL) << "Null canonical node";
-            return;
-          }
-          int child_id = canonical->unique_id();
-          uniq_child.insert(child_id);
-          // To the child, we want to add to parent indices.
-          Entry* child_entry = &entries_[child_id];
-          if (child_entry->parents->find(prefilter->unique_id()) ==
-              child_entry->parents->end()) {
-            (*child_entry->parents)[prefilter->unique_id()] = 1;
+          int child_id = (*prefilter->subs())[j]->unique_id();
+          std::vector<int>& parents = entries_[child_id].parents;
+          if (parents.empty() || parents.back() != id) {
+            parents.push_back(id);
+            up_count++;
           }
         }
-        entry->propagate_up_at_count = prefilter->op() == Prefilter::AND
-                                           ? static_cast<int>(uniq_child.size())
-                                           : 1;
-
+        entries_[id].propagate_up_at_count =
+            prefilter->op() == Prefilter::AND ? up_count : 1;
         break;
       }
     }
@@ -336,10 +307,7 @@ void PrefilterTree::PropagateMatch(const std::vector<int>& atom_ids,
       regexps->set(entry.regexps[i], 1);
     int c;
     // Pass trigger up to parents.
-    for (StdIntMap::iterator it = entry.parents->begin();
-         it != entry.parents->end();
-         ++it) {
-      int j = it->first;
+    for (int j : entry.parents) {
       const Entry& parent = entries_[j];
       // Delay until all the children have succeeded.
       if (parent.propagate_up_at_count > 1) {
@@ -369,12 +337,12 @@ void PrefilterTree::PrintDebugInfo(NodeMap* nodes) {
   LOG(ERROR) << "#Unique Nodes: " << entries_.size();
 
   for (size_t i = 0; i < entries_.size(); i++) {
-    StdIntMap* parents = entries_[i].parents;
+    const std::vector<int>& parents = entries_[i].parents;
     const std::vector<int>& regexps = entries_[i].regexps;
     LOG(ERROR) << "EntryId: " << i
-               << " N: " << parents->size() << " R: " << regexps.size();
-    for (StdIntMap::iterator it = parents->begin(); it != parents->end(); ++it)
-      LOG(ERROR) << it->first;
+               << " N: " << parents.size() << " R: " << regexps.size();
+    for (int parent : parents)
+      LOG(ERROR) << parent;
   }
   LOG(ERROR) << "Map:";
   for (NodeMap::const_iterator iter = nodes->begin();
diff --git a/contrib/libs/re2/re2/prefilter_tree.h b/contrib/libs/re2/re2/prefilter_tree.h
index 5d73074d97..6de1c38eb5 100644
--- a/contrib/libs/re2/re2/prefilter_tree.h
+++ b/contrib/libs/re2/re2/prefilter_tree.h
@@ -59,7 +59,8 @@ class PrefilterTree {
 
  private:
   typedef SparseArray<int> IntMap;
-  typedef std::map<int, int> StdIntMap;
+  // TODO(junyer): Use std::unordered_set<Prefilter*> instead?
+  // It should be trivial to get rid of the stringification...
   typedef std::map<std::string, Prefilter*> NodeMap;
 
   // Each unique node has a corresponding Entry that helps in
@@ -77,7 +78,7 @@ class PrefilterTree {
     // are two different nodes, but they share the atom 'def'. So when
     // 'def' matches, it triggers two parents, corresponding to the two
     // different OR nodes.
-    StdIntMap* parents;
+    std::vector<int> parents;
 
     // When this node is ready to trigger the parent, what are the
     // regexps that are triggered.
diff --git a/contrib/libs/re2/re2/prog.h b/contrib/libs/re2/re2/prog.h
index 4af012ab6f..72c9856dc1 100644
--- a/contrib/libs/re2/re2/prog.h
+++ b/contrib/libs/re2/re2/prog.h
@@ -361,7 +361,6 @@ class Prog {
   // Returns true on success, false on error.
   bool PossibleMatchRange(std::string* min, std::string* max, int maxlen);
 
-  // EXPERIMENTAL! SUBJECT TO CHANGE!
   // Outputs the program fanout into the given sparse array.
   void Fanout(SparseArray<int>* fanout);
 
diff --git a/contrib/libs/re2/re2/stringpiece.h b/contrib/libs/re2/re2/stringpiece.h
index ef7cef99e6..f09d141053 100644
--- a/contrib/libs/re2/re2/stringpiece.h
+++ b/contrib/libs/re2/re2/stringpiece.h
@@ -19,18 +19,13 @@
 //
 // Arghh!  I wish C++ literals were "string".
 
-// Doing this simplifies the logic below.
-#ifndef __has_include
-#define __has_include(x) 0
-#endif
-
 #include <stddef.h>
 #include <string.h>
 #include <algorithm>
 #include <iosfwd>
 #include <iterator>
 #include <string>
-#if __has_include(<string_view>) && __cplusplus >= 201703L
+#ifdef __cpp_lib_string_view
 #include <string_view>
 #endif
 #include <util/generic/string.h>
@@ -58,7 +53,7 @@ class StringPiece {
   // expected.
   StringPiece()
       : data_(NULL), size_(0) {}
-#if __has_include(<string_view>) && __cplusplus >= 201703L
+#ifdef __cpp_lib_string_view
   StringPiece(const std::string_view& str)
       : data_(str.data()), size_(str.size()) {}
 #endif
@@ -106,6 +101,14 @@ class StringPiece {
     size_ = len;
   }
 
+#ifdef __cpp_lib_string_view
+  // Converts to `std::basic_string_view`.
+  operator std::basic_string_view<char, traits_type>() const {
+    if (!data_) return {};
+    return std::basic_string_view<char, traits_type>(data_, size_);
+  }
+#endif
+
   // Converts to `std::basic_string`.
   template <typename A>
   explicit operator std::basic_string<char, traits_type, A>() const {
diff --git a/contrib/libs/re2/util/mutex.h b/contrib/libs/re2/util/mutex.h
index 158046bb5c..4b6772ae22 100644
--- a/contrib/libs/re2/util/mutex.h
+++ b/contrib/libs/re2/util/mutex.h
@@ -33,8 +33,8 @@ typedef SRWLOCK MutexType;
 #include <stdlib.h>
 typedef pthread_rwlock_t MutexType;
 #else
-#include <mutex>
-typedef std::mutex MutexType;
+#include <shared_mutex>
+typedef std::shared_mutex MutexType;
 #endif
 
 namespace re2 {
@@ -95,8 +95,8 @@ Mutex::Mutex()             { }
 Mutex::~Mutex()            { }
 void Mutex::Lock()         { mutex_.lock(); }
 void Mutex::Unlock()       { mutex_.unlock(); }
-void Mutex::ReaderLock()   { Lock(); }  // C++11 doesn't have std::shared_mutex.
-void Mutex::ReaderUnlock() { Unlock(); }
+void Mutex::ReaderLock()   { mutex_.lock_shared(); }
+void Mutex::ReaderUnlock() { mutex_.unlock_shared(); }
 
 #endif