1 // Copyright 2009 The RE2 Authors. All Rights Reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 #include "util/util.h"
6 #include "util/flags.h"
7 #include "re2/prefilter.h"
8 #include "re2/prefilter_tree.h"
9 #include "re2/re2.h"
10
11 DEFINE_int32(filtered_re2_min_atom_len,
12 3,
13 "Strings less than this length are not stored as atoms");
14
15 namespace re2 {
16
PrefilterTree()17 PrefilterTree::PrefilterTree()
18 : compiled_(false) {
19 }
20
~PrefilterTree()21 PrefilterTree::~PrefilterTree() {
22 for (int i = 0; i < prefilter_vec_.size(); i++)
23 delete prefilter_vec_[i];
24
25 for (int i = 0; i < entries_.size(); i++)
26 delete entries_[i].parents;
27 }
28
29 // Functions used for adding and Compiling prefilters to the
30 // PrefilterTree.
KeepPart(Prefilter * prefilter,int level)31 static bool KeepPart(Prefilter* prefilter, int level) {
32 if (prefilter == NULL)
33 return false;
34
35 switch (prefilter->op()) {
36 default:
37 LOG(DFATAL) << "Unexpected op in KeepPart: "
38 << prefilter->op();
39 return false;
40
41 case Prefilter::ALL:
42 return false;
43
44 case Prefilter::ATOM:
45 return prefilter->atom().size() >=
46 FLAGS_filtered_re2_min_atom_len;
47
48 case Prefilter::AND: {
49 int j = 0;
50 vector<Prefilter*>* subs = prefilter->subs();
51 for (int i = 0; i < subs->size(); i++)
52 if (KeepPart((*subs)[i], level + 1))
53 (*subs)[j++] = (*subs)[i];
54 else
55 delete (*subs)[i];
56
57 subs->resize(j);
58 return j > 0;
59 }
60
61 case Prefilter::OR:
62 for (int i = 0; i < prefilter->subs()->size(); i++)
63 if (!KeepPart((*prefilter->subs())[i], level + 1))
64 return false;
65 return true;
66 }
67 }
68
Add(Prefilter * f)69 void PrefilterTree::Add(Prefilter *f) {
70 if (compiled_) {
71 LOG(DFATAL) << "Add after Compile.";
72 return;
73 }
74 if (f != NULL && !KeepPart(f, 0)) {
75 delete f;
76 f = NULL;
77 }
78
79 prefilter_vec_.push_back(f);
80 }
81
Compile(vector<string> * atom_vec)82 void PrefilterTree::Compile(vector<string>* atom_vec) {
83 if (compiled_) {
84 LOG(DFATAL) << "Compile after Compile.";
85 return;
86 }
87
88 // We do this check to support some legacy uses of
89 // PrefilterTree that call Compile before adding any regexps,
90 // and expect Compile not to have effect.
91 if (prefilter_vec_.empty())
92 return;
93
94 compiled_ = true;
95
96 AssignUniqueIds(atom_vec);
97
98 // Identify nodes that are too common among prefilters and are
99 // triggering too many parents. Then get rid of them if possible.
100 // Note that getting rid of a prefilter node simply means they are
101 // no longer necessary for their parent to trigger; that is, we do
102 // not miss out on any regexps triggering by getting rid of a
103 // prefilter node.
104 for (int i = 0; i < entries_.size(); i++) {
105 StdIntMap* parents = entries_[i].parents;
106 if (parents->size() > 8) {
107 // This one triggers too many things. If all the parents are AND
108 // nodes and have other things guarding them, then get rid of
109 // this trigger. TODO(vsri): Adjust the threshold appropriately,
110 // make it a function of total number of nodes?
111 bool have_other_guard = true;
112 for (StdIntMap::iterator it = parents->begin(); it != parents->end(); ++it)
113 have_other_guard = have_other_guard &&
114 (entries_[it->first].propagate_up_at_count > 1);
115
116 if (have_other_guard) {
117 for (StdIntMap::iterator it = parents->begin();
118 it != parents->end(); ++it)
119 entries_[it->first].propagate_up_at_count -= 1;
120
121 parents->clear(); // Forget the parents
122 }
123 }
124 }
125
126 PrintDebugInfo();
127 }
128
CanonicalNode(Prefilter * node)129 Prefilter* PrefilterTree::CanonicalNode(Prefilter* node) {
130 string node_string = NodeString(node);
131 map<string, Prefilter*>::iterator iter = node_map_.find(node_string);
132 if (iter == node_map_.end())
133 return NULL;
134 return (*iter).second;
135 }
136
Itoa(int n)137 static string Itoa(int n) {
138 char buf[100];
139 snprintf(buf, sizeof buf, "%d", n);
140 return string(buf);
141 }
142
NodeString(Prefilter * node) const143 string PrefilterTree::NodeString(Prefilter* node) const {
144 // Adding the operation disambiguates AND/OR/atom nodes.
145 string s = Itoa(node->op()) + ":";
146 if (node->op() == Prefilter::ATOM) {
147 s += node->atom();
148 } else {
149 for (int i = 0; i < node->subs()->size() ; i++) {
150 if (i > 0)
151 s += ',';
152 s += Itoa((*node->subs())[i]->unique_id());
153 }
154 }
155 return s;
156 }
157
AssignUniqueIds(vector<string> * atom_vec)158 void PrefilterTree::AssignUniqueIds(vector<string>* atom_vec) {
159 atom_vec->clear();
160
161 // Build vector of all filter nodes, sorted topologically
162 // from top to bottom in v.
163 vector<Prefilter*> v;
164
165 // Add the top level nodes of each regexp prefilter.
166 for (int i = 0; i < prefilter_vec_.size(); i++) {
167 Prefilter* f = prefilter_vec_[i];
168 if (f == NULL)
169 unfiltered_.push_back(i);
170
171 // We push NULL also on to v, so that we maintain the
172 // mapping of index==regexpid for level=0 prefilter nodes.
173 v.push_back(f);
174 }
175
176 // Now add all the descendant nodes.
177 for (int i = 0; i < v.size(); i++) {
178 Prefilter* f = v[i];
179 if (f == NULL)
180 continue;
181 if (f->op() == Prefilter::AND || f->op() == Prefilter::OR) {
182 const vector<Prefilter*>& subs = *f->subs();
183 for (int j = 0; j < subs.size(); j++)
184 v.push_back(subs[j]);
185 }
186 }
187
188 // Identify unique nodes.
189 int unique_id = 0;
190 for (int i = v.size() - 1; i >= 0; i--) {
191 Prefilter *node = v[i];
192 if (node == NULL)
193 continue;
194 node->set_unique_id(-1);
195 Prefilter* canonical = CanonicalNode(node);
196 if (canonical == NULL) {
197 // Any further nodes that have the same node string
198 // will find this node as the canonical node.
199 node_map_[NodeString(node)] = node;
200 if (node->op() == Prefilter::ATOM) {
201 atom_vec->push_back(node->atom());
202 atom_index_to_id_.push_back(unique_id);
203 }
204 node->set_unique_id(unique_id++);
205 } else {
206 node->set_unique_id(canonical->unique_id());
207 }
208 }
209 entries_.resize(node_map_.size());
210
211 // Create parent IntMap for the entries.
212 for (int i = v.size() - 1; i >= 0; i--) {
213 Prefilter* prefilter = v[i];
214 if (prefilter == NULL)
215 continue;
216
217 if (CanonicalNode(prefilter) != prefilter)
218 continue;
219
220 Entry* entry = &entries_[prefilter->unique_id()];
221 entry->parents = new StdIntMap();
222 }
223
224 // Fill the entries.
225 for (int i = v.size() - 1; i >= 0; i--) {
226 Prefilter* prefilter = v[i];
227 if (prefilter == NULL)
228 continue;
229
230 if (CanonicalNode(prefilter) != prefilter)
231 continue;
232
233 Entry* entry = &entries_[prefilter->unique_id()];
234
235 switch (prefilter->op()) {
236 default:
237 case Prefilter::ALL:
238 LOG(DFATAL) << "Unexpected op: " << prefilter->op();
239 return;
240
241 case Prefilter::ATOM:
242 entry->propagate_up_at_count = 1;
243 break;
244
245 case Prefilter::OR:
246 case Prefilter::AND: {
247 set<int> uniq_child;
248 for (int j = 0; j < prefilter->subs()->size() ; j++) {
249 Prefilter* child = (*prefilter->subs())[j];
250 Prefilter* canonical = CanonicalNode(child);
251 if (canonical == NULL) {
252 LOG(DFATAL) << "Null canonical node";
253 return;
254 }
255 int child_id = canonical->unique_id();
256 uniq_child.insert(child_id);
257 // To the child, we want to add to parent indices.
258 Entry* child_entry = &entries_[child_id];
259 if (child_entry->parents->find(prefilter->unique_id()) == child_entry->parents->end())
260 (*child_entry->parents)[prefilter->unique_id()] = 1;
261 }
262 entry->propagate_up_at_count =
263 prefilter->op() == Prefilter::AND ? uniq_child.size() : 1;
264
265 break;
266 }
267 }
268 }
269
270 // For top level nodes, populate regexp id.
271 for (int i = 0; i < prefilter_vec_.size(); i++) {
272 if (prefilter_vec_[i] == NULL)
273 continue;
274 int id = CanonicalNode(prefilter_vec_[i])->unique_id();
275 DCHECK_LE(0, id);
276 Entry* entry = &entries_[id];
277 entry->regexps.push_back(i);
278 }
279 }
280
281 // Functions for triggering during search.
RegexpsGivenStrings(const vector<int> & matched_atoms,vector<int> * regexps) const282 void PrefilterTree::RegexpsGivenStrings(
283 const vector<int>& matched_atoms,
284 vector<int>* regexps) const {
285 regexps->clear();
286 if (!compiled_) {
287 LOG(WARNING) << "Compile() not called";
288 for (int i = 0; i < prefilter_vec_.size(); ++i)
289 regexps->push_back(i);
290 } else {
291 if (!prefilter_vec_.empty()) {
292 IntMap regexps_map(prefilter_vec_.size());
293 vector<int> matched_atom_ids;
294 for (int j = 0; j < matched_atoms.size(); j++) {
295 matched_atom_ids.push_back(atom_index_to_id_[matched_atoms[j]]);
296 VLOG(10) << "Atom id:" << atom_index_to_id_[matched_atoms[j]];
297 }
298 PropagateMatch(matched_atom_ids, ®exps_map);
299 for (IntMap::iterator it = regexps_map.begin();
300 it != regexps_map.end();
301 ++it)
302 regexps->push_back(it->index());
303
304 regexps->insert(regexps->end(), unfiltered_.begin(), unfiltered_.end());
305 }
306 }
307 sort(regexps->begin(), regexps->end());
308 }
309
PropagateMatch(const vector<int> & atom_ids,IntMap * regexps) const310 void PrefilterTree::PropagateMatch(const vector<int>& atom_ids,
311 IntMap* regexps) const {
312 IntMap count(entries_.size());
313 IntMap work(entries_.size());
314 for (int i = 0; i < atom_ids.size(); i++)
315 work.set(atom_ids[i], 1);
316 for (IntMap::iterator it = work.begin(); it != work.end(); ++it) {
317 const Entry& entry = entries_[it->index()];
318 VLOG(10) << "Processing: " << it->index();
319 // Record regexps triggered.
320 for (int i = 0; i < entry.regexps.size(); i++) {
321 VLOG(10) << "Regexp triggered: " << entry.regexps[i];
322 regexps->set(entry.regexps[i], 1);
323 }
324 int c;
325 // Pass trigger up to parents.
326 for (StdIntMap::iterator it = entry.parents->begin();
327 it != entry.parents->end();
328 ++it) {
329 int j = it->first;
330 const Entry& parent = entries_[j];
331 VLOG(10) << " parent= " << j << " trig= " << parent.propagate_up_at_count;
332 // Delay until all the children have succeeded.
333 if (parent.propagate_up_at_count > 1) {
334 if (count.has_index(j)) {
335 c = count.get_existing(j) + 1;
336 count.set_existing(j, c);
337 } else {
338 c = 1;
339 count.set_new(j, c);
340 }
341 if (c < parent.propagate_up_at_count)
342 continue;
343 }
344 VLOG(10) << "Triggering: " << j;
345 // Trigger the parent.
346 work.set(j, 1);
347 }
348 }
349 }
350
351 // Debugging help.
PrintPrefilter(int regexpid)352 void PrefilterTree::PrintPrefilter(int regexpid) {
353 LOG(INFO) << DebugNodeString(prefilter_vec_[regexpid]);
354 }
355
PrintDebugInfo()356 void PrefilterTree::PrintDebugInfo() {
357 VLOG(10) << "#Unique Atoms: " << atom_index_to_id_.size();
358 VLOG(10) << "#Unique Nodes: " << entries_.size();
359
360 for (int i = 0; i < entries_.size(); ++i) {
361 StdIntMap* parents = entries_[i].parents;
362 const vector<int>& regexps = entries_[i].regexps;
363 VLOG(10) << "EntryId: " << i
364 << " N: " << parents->size() << " R: " << regexps.size();
365 for (StdIntMap::iterator it = parents->begin(); it != parents->end(); ++it)
366 VLOG(10) << it->first;
367 }
368 VLOG(10) << "Map:";
369 for (map<string, Prefilter*>::const_iterator iter = node_map_.begin();
370 iter != node_map_.end(); ++iter)
371 VLOG(10) << "NodeId: " << (*iter).second->unique_id()
372 << " Str: " << (*iter).first;
373 }
374
DebugNodeString(Prefilter * node) const375 string PrefilterTree::DebugNodeString(Prefilter* node) const {
376 string node_string = "";
377
378 if (node->op() == Prefilter::ATOM) {
379 DCHECK(!node->atom().empty());
380 node_string += node->atom();
381 } else {
382 // Adding the operation disambiguates AND and OR nodes.
383 node_string += node->op() == Prefilter::AND ? "AND" : "OR";
384 node_string += "(";
385 for (int i = 0; i < node->subs()->size() ; i++) {
386 if (i > 0)
387 node_string += ',';
388 node_string += Itoa((*node->subs())[i]->unique_id());
389 node_string += ":";
390 node_string += DebugNodeString((*node->subs())[i]);
391 }
392 node_string += ")";
393 }
394 return node_string;
395 }
396
397 } // namespace re2
398