```Prune `PrefilterTree` edges instead of nodes.

Credit and gratitude to Daniel Keller for devising and refining the
probability-based heuristics.

Change-Id: Id99ffb0be27a2549f1ee0af1f7925027a3076127
```
```diff --git a/re2/prefilter_tree.cc b/re2/prefilter_tree.cc
index 1e4eaff..af50b31 100644
--- a/re2/prefilter_tree.cc
+++ b/re2/prefilter_tree.cc
```
```@@ -4,6 +4,7 @@

#include "re2/prefilter_tree.h"

+#include <math.h>
#include <stddef.h>
#include <algorithm>
#include <map>
@@ -65,33 +66,6 @@

NodeMap nodes;
AssignUniqueIds(&nodes, atom_vec);
-
-  // Identify nodes that are too common among prefilters and are
-  // triggering too many parents. Then get rid of them if possible.
-  // Note that getting rid of a prefilter node simply means they are
-  // no longer necessary for their parent to trigger; that is, we do
-  // not miss out on any regexps triggering by getting rid of a
-  // prefilter node.
-  for (size_t i = 0; i < entries_.size(); i++) {
-    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 (int parent : parents) {
-        have_other_guard = have_other_guard &&
-            (entries_[parent].propagate_up_at_count > 1);
-      }
-      if (have_other_guard) {
-        for (int parent : parents)
-          entries_[parent].propagate_up_at_count -= 1;
-        parents.clear();  // Forget the parents
-      }
-    }
-  }
-
PrintDebugInfo(&nodes);
}
@@ -215,12 +189,9 @@
Prefilter* prefilter = v[i];
if (prefilter == NULL)
continue;
-
if (CanonicalNode(nodes, prefilter) != prefilter)
continue;
-
int id = prefilter->unique_id();
-
switch (prefilter->op()) {
default:
LOG(DFATAL) << "Unexpected op: " << prefilter->op();
@@ -261,6 +232,51 @@
Entry* entry = &entries_[id];
entry->regexps.push_back(static_cast<int>(i));
}
+
+  // Lastly, using probability-based heuristics, we identify nodes
+  // that trigger too many parents and then we try to prune edges.
+  // We use logarithms below to avoid the likelihood of underflow.
+  double log_num_regexps = std::log(prefilter_vec_.size() - unfiltered_.size());
+  // Hoisted this above the loop so that we don't thrash the heap.
+  std::vector<std::pair<int, int>> entries_by_num_edges;
+  for (int i = static_cast<int>(v.size()) - 1; i >= 0; i--) {
+    Prefilter* prefilter = v[i];
+    // Pruning applies only to AND nodes because it "just" reduces
+    // precision; applied to OR nodes, it would break correctness.
+    if (prefilter == NULL || prefilter->op() != Prefilter::AND)
+      continue;
+    if (CanonicalNode(nodes, prefilter) != prefilter)
+      continue;
+    int id = prefilter->unique_id();
+
+    // Sort the current node's children by the numbers of parents.
+    entries_by_num_edges.clear();
+    for (size_t j = 0; j < prefilter->subs()->size(); j++) {
+      int child_id = (*prefilter->subs())[j]->unique_id();
+      const std::vector<int>& parents = entries_[child_id].parents;
+      entries_by_num_edges.emplace_back(parents.size(), child_id);
+    }
+    std::stable_sort(entries_by_num_edges.begin(), entries_by_num_edges.end());
+
+    // A running estimate of how many regexps will be triggered by
+    // pruning the remaining children's edges to the current node.
+    // Our nominal target is one, so the threshold is log(1) == 0;
+    // pruning occurs iff the child has more than nine edges left.
+    double log_num_triggered = log_num_regexps;
+    for (const auto& pair : entries_by_num_edges) {
+      int child_id = pair.second;
+      std::vector<int>& parents = entries_[child_id].parents;
+      if (log_num_triggered > 0.) {
+        log_num_triggered += std::log(parents.size());
+        log_num_triggered -= log_num_regexps;
+      } else if (parents.size() > 9) {
+        auto it = std::find(parents.begin(), parents.end(), id);
+        DCHECK(it != parents.end());
+        parents.erase(it);
+        entries_[id].propagate_up_at_count--;
+      }
+    }
+  }
}

// Functions for triggering during search.
```