1 : // Copyright 2012 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : #include "syzygy/pe/dia_browser.h"
16 :
17 : #include "base/logging.h"
18 :
19 : namespace {
20 :
21 : using pe::SymTag;
22 : using pe::SymTagBitSet;
23 : using pe::kSymTagBegin;
24 : using pe::kSymTagEnd;
25 :
26 : // Adds a sym_tag to set of SymTagBitSet. Handles the special case of SymTagNull
27 : // by adding *all* tags.
28 E : void AddToSymTagBitSet(SymTag tag, SymTagBitSet* set) {
29 E : if (tag == SymTagNull) {
30 E : set->set();
31 E : } else {
32 E : if (tag < kSymTagBegin || tag >= kSymTagEnd)
33 E : return;
34 E : set->set(static_cast<size_t>(tag) - kSymTagBegin);
35 : }
36 E : }
37 :
38 E : bool SymTagBitSetContains(SymTagBitSet set, SymTag tag) {
39 E : DCHECK(tag != SymTagNull);
40 E : return set.test(tag - kSymTagBegin);
41 E : }
42 :
43 : } // namespace
44 :
45 : namespace pe {
46 :
47 : using base::win::ScopedComPtr;
48 :
49 : const SymTag kSymTagInvalid(static_cast<SymTag>(-1));
50 :
51 : // Defines an element in a pattern.
52 : struct DiaBrowser::PatternElement {
53 : PatternElement()
54 : : sym_tags(),
55 : outgoing_sym_tags(),
56 : links(),
57 : pattern_id(-1),
58 E : full_match(false) {
59 E : }
60 :
61 E : ~PatternElement() {
62 E : }
63 :
64 : // Returns true if @p sym_tag matches the SymTagBitSet represented
65 : // by this PatternElement.
66 E : bool Matches(SymTag sym_tag) const {
67 E : return SymTagBitSetContains(sym_tags, sym_tag);
68 E : }
69 :
70 : // Invokes the callback on this PatternElement, if present.
71 : BrowserDirective InvokeCallback(const DiaBrowser& browser,
72 : const SymTagVector& tag_lineage,
73 : const SymbolPtrVector& symbol_lineage,
74 E : const MatchCallback& callback) const {
75 E : BrowserDirective directive = kBrowserContinue;
76 E : if (!callback.is_null())
77 E : directive = callback.Run(browser, tag_lineage, symbol_lineage);
78 :
79 E : if (directive == kBrowserContinue && links.empty())
80 E : directive = kBrowserTerminatePath;
81 :
82 E : return directive;
83 E : }
84 :
85 : BrowserDirective InvokePushCallback(
86 : const DiaBrowser& browser,
87 : const SymTagVector& tag_lineage,
88 E : const SymbolPtrVector& symbol_lineage) const {
89 E : return InvokeCallback(browser, tag_lineage, symbol_lineage, push_callback);
90 E : }
91 :
92 : BrowserDirective InvokePopCallback(
93 : const DiaBrowser& browser,
94 : const SymTagVector& tag_lineage,
95 E : const SymbolPtrVector& symbol_lineage) const {
96 E : return InvokeCallback(browser, tag_lineage, symbol_lineage, pop_callback);
97 E : }
98 :
99 : // Calculates the outgoing sym_tags for this element.
100 E : void CalculateOutgoingSymtags() {
101 E : outgoing_sym_tags.reset();
102 E : for (size_t i = 0; i < links.size(); ++i)
103 E : outgoing_sym_tags |= links[i]->sym_tags;
104 E : }
105 :
106 : // The set of symbols that may be matched at this node.
107 : SymTagBitSet sym_tags;
108 :
109 : // The union of all outgoing link SymTagBitSets.
110 : SymTagBitSet outgoing_sym_tags;
111 :
112 : // These are links to other PatternElements in the same pattern.
113 : std::vector<PatternElement*> links;
114 :
115 : // This indicates to which pattern this element belongs.
116 : // TODO(chrisha): Maybe a separate category_id for visited_ bookkeeping?
117 : size_t pattern_id;
118 :
119 : // If this is non-null, when reaching this point in the pattern we will
120 : // invoke the callback.
121 : MatchCallback push_callback;
122 : // This callback will be invoked when retreating back up the stack of matches.
123 : MatchCallback pop_callback;
124 :
125 : // If this is true, this node is an exit node for the pattern. Any time
126 : // we reach this node, a full match has been achieved.
127 : bool full_match;
128 : };
129 :
130 : // The PatternBuilder class represents regex-like patterns over SymTag paths.
131 : class DiaBrowser::PatternBuilder {
132 : public:
133 : enum PatternType {
134 : kPatternNone,
135 : kPatternTags,
136 : kPatternSeq,
137 : kPatternOr,
138 : kPatternOpt,
139 : kPatternPlus,
140 : kPatternStar,
141 : kPatternCallback
142 : };
143 :
144 E : PatternBuilder()
145 : : type_(kPatternNone) {
146 E : }
147 :
148 E : explicit PatternBuilder(SymTag sym_tag)
149 : : type_(kPatternTags) {
150 E : DCHECK(sym_tag != kSymTagInvalid);
151 E : AddToSymTagBitSet(sym_tag, &sym_tags_);
152 E : DCHECK(sym_tags_.count() > 0);
153 E : }
154 :
155 : explicit PatternBuilder(SymTagBitSet sym_tags)
156 : : type_(kPatternTags),
157 E : sym_tags_(sym_tags) {
158 : // We don't DCHECK(sym_tags_.count() > 0) because it's possible and valid
159 : // for a SymTagBitSet to be empty. This will fail on AddPattern, however.
160 E : }
161 :
162 : // For constructing kPatternSeq/kPatternOr patterns.
163 : PatternBuilder(PatternType type,
164 : const PatternBuilder& pb0,
165 : const PatternBuilder& pb1)
166 : : type_(type),
167 : pb0_(new PatternBuilder()),
168 E : pb1_(new PatternBuilder()) {
169 E : DCHECK(type_ == kPatternSeq || type_ == kPatternOr);
170 E : DCHECK(pb0.type_ != kPatternNone && pb1.type_ != kPatternNone);
171 E : pb0_->CopyFrom(pb0);
172 E : pb1_->CopyFrom(pb1);
173 E : }
174 :
175 : // For constructing kPatternOpt/kPatternPlus/kPatternStar patterns.
176 : PatternBuilder(PatternType type, const PatternBuilder& pb)
177 : : type_(type),
178 E : pb0_(new PatternBuilder()) {
179 E : DCHECK(type_ == kPatternOpt || type_ == kPatternPlus ||
180 : type_ == kPatternStar);
181 E : DCHECK(pb.type_ != kPatternNone);
182 E : pb0_->CopyFrom(pb);
183 E : }
184 :
185 : // For constructing kPatternCallback patterns.
186 : PatternBuilder(const PatternBuilder& pb,
187 : MatchCallback push_callback,
188 : MatchCallback pop_callback)
189 : : type_(kPatternCallback),
190 : push_callback_(push_callback),
191 : pop_callback_(pop_callback),
192 : pb0_(new PatternBuilder()),
193 E : pb1_(NULL) {
194 E : DCHECK(!push_callback.is_null());
195 E : DCHECK(pb.type_ != kPatternNone);
196 E : pb0_->CopyFrom(pb);
197 E : }
198 :
199 : // Performs a deep-copy of the given pattern builder.
200 E : void CopyFrom(const PatternBuilder& pb) {
201 E : type_ = pb.type_;
202 E : sym_tags_ = pb.sym_tags_;
203 E : push_callback_ = pb.push_callback_;
204 E : pop_callback_ = pb.pop_callback_;
205 :
206 E : if (pb.pb0_.get() != NULL) {
207 E : if (pb0_.get() == NULL)
208 E : pb0_.reset(new PatternBuilder());
209 E : pb0_->CopyFrom(*pb.pb0_);
210 E : } else {
211 E : pb0_.reset();
212 : }
213 :
214 E : if (pb.pb1_.get() != NULL) {
215 E : if (pb1_.get() == NULL)
216 E : pb1_.reset(new PatternBuilder());
217 E : pb1_->CopyFrom(*pb.pb1_);
218 E : } else {
219 E : pb1_.reset();
220 : }
221 E : }
222 :
223 E : PatternType type() const { return type_; }
224 :
225 : // A utility function that builds the 'or' pattern of two sub-patterns.
226 : // Performs optimizations as much as possible (merging SymTag and SymTagSet
227 : // sub-patterns).
228 : static void OrBuilder(const PatternBuilder& pb0,
229 : const PatternBuilder& pb1,
230 E : PatternBuilder* pbor) {
231 : // For simplification, we collect Tag-type sub-expressions. We ensure any
232 : // Or statement contains at most one tagset, and if so, this tagset is in
233 : // the first sub-expression. Since patterns are build from the inside out
234 : // (nested sub-expressions first), this simplification will propogate all
235 : // of the way through a set of nested Or statements.
236 :
237 E : if (pb0.type_ == kPatternTags) {
238 : // If the two sub-expressions are both SymTagSets, merge them.
239 E : if (pb1.type_ == kPatternTags) {
240 E : pbor->CopyFrom(PatternBuilder(pb0.sym_tags_ | pb1.sym_tags_));
241 E : return;
242 : }
243 :
244 : // If we have Or(tagset0, Or(tagset1, other)), merge to
245 : // Or(tagset0|tagset1, other).
246 E : if (pb1.type_ == kPatternOr && pb1.pb0_->type_ == kPatternTags) {
247 E : pbor->CopyFrom(pb1);
248 E : pbor->pb0_->sym_tags_ |= pb0.sym_tags_;
249 E : return;
250 : }
251 :
252 E : pbor->CopyFrom(PatternBuilder(kPatternOr, pb0, pb1));
253 E : return;
254 : }
255 :
256 : // If the first sub-expression is not a tagset, but the second one is,
257 : // then swap them and rerun the logic. This will do the simplification
258 : // above.
259 E : if (pb1.type_ == kPatternTags) {
260 E : DCHECK_NE(kPatternTags, pb0.type_);
261 E : return OrBuilder(pb1, pb0, pbor);
262 : }
263 :
264 : // At this point, neither of the sub-expression is a simple tagset.
265 : // Bring nested tagsets to the outermost Or expression, if they exist.
266 : // If the exist, they will be in the first sub-expression.
267 E : DCHECK_NE(kPatternTags, pb0.type_);
268 E : DCHECK_NE(kPatternTags, pb1.type_);
269 E : if (pb0.type_ == kPatternOr && pb0.pb0_->type_ == kPatternTags) {
270 : // The second entry should never also be a tagset, as it should have
271 : // been simplified if this were the case.
272 E : DCHECK_NE(kPatternTags, pb0.pb1_->type_);
273 :
274 : // If both are of type Or(tagset, other), then merge their
275 : // sym_tags and keep the sym_tags as the outermost entry.
276 : // That is, Or(Or(tagset0, other0), Or(tagset1, other1)) ->
277 : // Or(tagset0|tagset1, Or(other0, other1)).
278 E : if (pb1.type_ == kPatternOr && pb1.pb0_->type_ == kPatternTags) {
279 i : PatternBuilder pbA(pb0.pb0_->sym_tags_ | pb1.pb0_->sym_tags_);
280 i : PatternBuilder pbB(kPatternOr, *pb0.pb1_, *pb1.pb1_);
281 i : pbor->CopyFrom(PatternBuilder(kPatternOr, pbA, pbB));
282 i : return;
283 : }
284 :
285 : // Keep the sym_tags as the first sub-expression.
286 E : PatternBuilder pb(kPatternOr, *pb0.pb1_, pb1);
287 E : pbor->CopyFrom(PatternBuilder(kPatternOr, *pb0.pb0_, pb));
288 E : return;
289 : }
290 :
291 : // If the second sub-expression contains a nested tagset, but the first
292 : // does not, swap their order and rerun the logic. The above logic will
293 : // do the necessary simplification.
294 i : if (pb1.type_ == kPatternOr && pb1.pb0_->type_ == kPatternTags) {
295 i : DCHECK(pb0.type_ != kPatternOr || pb0.pb0_->type_ != kPatternTags);
296 i : return OrBuilder(pb1, pb0, pbor);
297 : }
298 :
299 : // If we get here, then neither of the sub-expressions contains a tagset.
300 i : DCHECK(pb0.type_ != kPatternOr || pb0.pb0_->type_ != kPatternTags);
301 i : DCHECK(pb1.type_ != kPatternOr || pb1.pb0_->type_ != kPatternTags);
302 i : pbor->CopyFrom(PatternBuilder(kPatternOr, pb0, pb1));
303 : return;
304 E : }
305 :
306 : protected:
307 : friend class DiaBrowser;
308 :
309 : // Returns the length of this pattern.
310 E : size_t Length() const {
311 E : switch (type_) {
312 : case kPatternNone:
313 i : return 0;
314 :
315 : case kPatternTags:
316 E : return 1;
317 :
318 : case kPatternSeq:
319 : case kPatternOr:
320 E : return pb0_->Length() + pb1_->Length();
321 :
322 : case kPatternOpt:
323 : case kPatternPlus:
324 : case kPatternStar:
325 : case kPatternCallback:
326 E : return pb0_->Length();
327 :
328 : default:
329 i : NOTREACHED() << "Invalid PatternType.";
330 i : return 0;
331 : }
332 E : }
333 :
334 : // Appends the entries of this pattern to @p entries.
335 : void GetEntries(PatternElement* pattern,
336 : size_t offset,
337 E : std::vector<PatternElement*>* entries) const {
338 E : switch (type_) {
339 : case kPatternNone:
340 i : break;
341 :
342 : case kPatternTags:
343 E : entries->push_back(pattern + offset);
344 E : break;
345 :
346 : case kPatternSeq:
347 : case kPatternOpt:
348 : case kPatternPlus:
349 : case kPatternStar:
350 : case kPatternCallback:
351 i : pb0_->GetEntries(pattern, offset, entries);
352 i : break;
353 :
354 : case kPatternOr:
355 i : pb0_->GetEntries(pattern, offset, entries);
356 i : pb1_->GetEntries(pattern, offset + pb0_->Length(), entries);
357 i : break;
358 :
359 : default:
360 i : NOTREACHED() << "Invalid PatternType.";
361 : break;
362 : }
363 E : }
364 :
365 : // Builds this pattern inside of a Pattern. We are given the set
366 : // of exit nodes of our predecessor pattern, and need to build a set of exit
367 : // nodes for our pattern. Exit nodes are appended to @p out_exits.
368 : // @p pattern is the root element of the pattern into which we are building,
369 : // and @p offset is the location at which we will insert our pattern.
370 : void Build(PatternElement* pattern,
371 : size_t offset,
372 : const std::vector<PatternElement*>& in_exits,
373 E : std::vector<PatternElement*>* out_exits) const {
374 E : switch (type_) {
375 : case kPatternNone:
376 i : return;
377 :
378 : case kPatternTags: {
379 E : pattern[offset].sym_tags = sym_tags_;
380 E : for (size_t i = 0; i < in_exits.size(); ++i)
381 E : in_exits[i]->links.push_back(pattern + offset);
382 E : out_exits->push_back(pattern + offset);
383 E : return;
384 : }
385 :
386 : case kPatternSeq: {
387 E : size_t len0 = pb0_->Length();
388 E : std::vector<PatternElement*> exits0;
389 E : pb0_->Build(pattern, offset, in_exits, &exits0);
390 E : pb1_->Build(pattern, offset + len0, exits0, out_exits);
391 E : return;
392 : }
393 :
394 : case kPatternOr: {
395 E : size_t len0 = pb0_->Length();
396 E : pb0_->Build(pattern, offset, in_exits, out_exits);
397 E : pb1_->Build(pattern, offset + len0, in_exits, out_exits);
398 E : return;
399 : }
400 :
401 : case kPatternOpt:
402 : case kPatternPlus:
403 : case kPatternStar: {
404 : // Link in the sub-pattern.
405 E : pb0_->Build(pattern, offset, in_exits, out_exits);
406 :
407 E : if (type_ != kPatternOpt) {
408 : // Hook up the output exits to the entries of the sub-pattern,
409 : // allowing this sub-pattern to be repeated.
410 E : std::vector<PatternElement*> entries;
411 E : pb0_->GetEntries(pattern, offset, &entries);
412 E : for (size_t i = 0; i < out_exits->size(); ++i)
413 E : for (size_t j = 0; j < entries.size(); ++j)
414 E : (*out_exits)[i]->links.push_back(entries[j]);
415 E : }
416 :
417 E : if (type_ != kPatternPlus) {
418 : // Add the input exits to the output exits, making the sub-pattern
419 : // optional.
420 E : out_exits->insert(out_exits->end(), in_exits.begin(), in_exits.end());
421 : }
422 E : return;
423 : }
424 :
425 : case kPatternCallback: {
426 E : pb0_->Build(pattern, offset, in_exits, out_exits);
427 :
428 : // Label the exit points of the sub-pattern with the provided
429 : // callback.
430 E : for (size_t i = 0; i < out_exits->size(); ++i) {
431 E : (*out_exits)[i]->push_callback = push_callback_;
432 E : (*out_exits)[i]->pop_callback = pop_callback_;
433 E : }
434 E : return;
435 : }
436 :
437 : default:
438 i : NOTREACHED() << "Invalid PatternType.";
439 : return;
440 : }
441 E : }
442 :
443 : private:
444 : PatternType type_;
445 : SymTagBitSet sym_tags_;
446 : MatchCallback push_callback_;
447 : MatchCallback pop_callback_;
448 : scoped_ptr<PatternBuilder> pb0_;
449 : scoped_ptr<PatternBuilder> pb1_;
450 :
451 : DISALLOW_COPY_AND_ASSIGN(PatternBuilder);
452 : };
453 :
454 E : DiaBrowser::~DiaBrowser() {
455 E : for (size_t i = 0; i < patterns_.size(); ++i)
456 E : delete [] patterns_[i];
457 E : }
458 :
459 : bool DiaBrowser::AddPattern(const builder::Proxy& pattern_builder_proxy,
460 E : const MatchCallback& push_callback) {
461 E : return AddPattern(pattern_builder_proxy, push_callback, MatchCallback());
462 E : }
463 :
464 : bool DiaBrowser::AddPattern(const builder::Proxy& pattern_builder_proxy,
465 : const MatchCallback& push_callback,
466 E : const MatchCallback& pop_callback) {
467 E : const PatternBuilder& pattern_builder(pattern_builder_proxy);
468 E : size_t pattern_length = pattern_builder.Length();
469 :
470 : // Empty patterns are rejected.
471 E : if (pattern_length == 0)
472 i : return false;
473 :
474 : // Build the pattern in place. We increment pattern_length by 1 so to have
475 : // room for a special root node at the beginning of the pattern.
476 E : ++pattern_length;
477 E : size_t pattern_id = patterns_.size();
478 E : scoped_ptr<PatternElement[]> pattern(new PatternElement[pattern_length]);
479 E : std::vector<PatternElement*> in_exits(1, pattern.get());
480 E : std::vector<PatternElement*> out_exits;
481 E : pattern_builder.Build(pattern.get(), 1, in_exits, &out_exits);
482 :
483 : // If the root element is one of the out_exits, this pattern will match the
484 : // 'null' sequence. Reject it!
485 E : for (size_t i = 0; i < out_exits.size(); ++i) {
486 E : if (out_exits[i] == pattern.get()) {
487 E : return false;
488 : }
489 E : }
490 :
491 : // If the root element points to itself, the pattern can match a 'null'
492 : // sequence. Reject it!
493 E : for (size_t i = 0; i < pattern[0].links.size(); ++i) {
494 E : if (pattern[0].links[i] == pattern.get()) {
495 i : return false;
496 : }
497 E : }
498 :
499 : // If any element in the pattern matches *no* sym_tags, the pattern is
500 : // unmatchable. Reject it!
501 E : for (size_t i = 1; i < pattern_length; ++i) {
502 E : if (pattern[i].sym_tags.none()) {
503 E : return false;
504 : }
505 E : }
506 :
507 : // Mark the exit nodes as being full match nodes, and set their callbacks.
508 E : for (size_t i = 0; i < out_exits.size(); ++i) {
509 E : out_exits[i]->full_match = true;
510 E : out_exits[i]->push_callback = push_callback;
511 E : out_exits[i]->pop_callback = pop_callback;
512 E : }
513 :
514 : // Label the pattern node with the id of this pattern, and precalculate
515 : // outgoing sym_tagsets as used by Browse.
516 E : for (size_t i = 0; i < pattern_length; ++i) {
517 E : pattern[i].pattern_id = pattern_id;
518 E : pattern[i].CalculateOutgoingSymtags();
519 E : }
520 :
521 E : patterns_.push_back(pattern.release());
522 :
523 E : return true;
524 E : }
525 :
526 : // This is a light-weight clone of Browse, without the actual DIA browsing,
527 : // and without callbacks. It is intended largely to test the pattern-matching
528 : // functionality.
529 E : size_t DiaBrowser::TestMatch(const SymTagVector& sym_tags) const {
530 E : size_t match_count = 0;
531 E : for (size_t pat_idx = 0; pat_idx < patterns_.size(); ++pat_idx) {
532 E : std::vector<const PatternElement*> front0(1, patterns_[pat_idx]);
533 E : std::vector<const PatternElement*> front1;
534 :
535 E : std::vector<const PatternElement*>* active = &front0;
536 E : std::vector<const PatternElement*>* next = &front1;
537 :
538 E : for (size_t sym_tag_idx = 0; sym_tag_idx < sym_tags.size(); ++sym_tag_idx) {
539 E : if (active->empty())
540 i : break;
541 :
542 E : SymTag sym_tag = sym_tags[sym_tag_idx];
543 E : for (size_t active_idx = 0; active_idx < active->size(); ++active_idx) {
544 E : const PatternElement* elem = (*active)[active_idx];
545 :
546 : if (elem->links.size() == 0 ||
547 E : !SymTagBitSetContains(elem->outgoing_sym_tags, sym_tag))
548 E : continue;
549 :
550 E : for (size_t link_idx = 0; link_idx < elem->links.size(); ++link_idx) {
551 E : const PatternElement* elem_next = elem->links[link_idx];
552 E : if (elem_next->Matches(sym_tag))
553 E : next->push_back(elem_next);
554 E : }
555 E : }
556 :
557 E : std::swap(active, next);
558 E : next->clear();
559 E : }
560 :
561 : // If we get here, those active nodes marked 'full_match' count as matches.
562 E : for (size_t i = 0; i < active->size(); ++i) {
563 E : const PatternElement* elem = (*active)[i];
564 E : if (elem->full_match)
565 E : ++match_count;
566 E : }
567 E : }
568 :
569 E : return match_count;
570 E : }
571 :
572 E : void DiaBrowser::PrepareForBrowse() {
573 E : Reset();
574 :
575 : // Set all patterns as valid, initialize the search front and set up
576 : // the first set of sym_tags to search for.
577 E : stopped_.resize(patterns_.size());
578 E : sym_tags_.resize(1);
579 E : sym_tags_[0].reset();
580 E : for (size_t i = 0; i < patterns_.size(); ++i) {
581 E : PatternElement* elem = patterns_[i];
582 E : front_.push_back(elem);
583 E : stopped_[i] = false;
584 E : sym_tags_[0] |= elem->outgoing_sym_tags;
585 E : }
586 E : front_size_.push_back(patterns_.size());
587 E : }
588 :
589 E : void DiaBrowser::Reset() {
590 E : visited_.clear();
591 E : tag_lineage_.clear();
592 E : symbol_lineage_.clear();
593 E : front_.clear();
594 E : front_size_.clear();
595 E : stopped_.clear();
596 E : sym_tags_.clear();
597 E : }
598 :
599 : DiaBrowser::BrowserDirective DiaBrowser::PushMatch(
600 E : SymTag sym_tag, uint32 symbol_id, SymTagBitSet* sym_tags) {
601 E : DCHECK(sym_tags != NULL);
602 E : DCHECK(!front_size_.empty());
603 :
604 E : sym_tags->reset();
605 E : size_t new_front = 0;
606 :
607 : // Examine every node at our current level in the front, and advance those
608 : // that we can.
609 E : size_t front_end = front_.size();
610 E : size_t front_begin = front_end - front_size_.back();
611 E : for (size_t f = front_begin; f < front_end; ++f) {
612 E : size_t patid = front_[f]->pattern_id;
613 E : if (stopped_[patid])
614 i : continue;
615 :
616 : // Iterate over the possible destinations of this element.
617 E : for (size_t l = 0; l < front_[f]->links.size(); ++l) {
618 E : PatternElement* elem = front_[f]->links[l];
619 :
620 E : if (!elem->Matches(sym_tag))
621 E : continue;
622 :
623 : // Each element will only be visited once per pattern element.
624 E : if (!visited_.insert(std::make_pair(elem, symbol_id)).second)
625 E : continue;
626 :
627 : // Invoke the callback for each valid destination, and truncate the
628 : // search if necessary.
629 : BrowserDirective directive = elem->InvokePushCallback(*this,
630 : tag_lineage_,
631 E : symbol_lineage_);
632 :
633 E : bool need_pop_callback = false;
634 E : switch (directive) {
635 : // Normal match. Add the destination to the new search front. We don't
636 : // need a local pop callback because this node will be added to the
637 : // search front. The pop callback will be invoked when we backtrack
638 : // later on.
639 : case kBrowserContinue:
640 E : *sym_tags |= elem->outgoing_sym_tags;
641 E : ++new_front;
642 E : front_.push_back(elem);
643 E : break;
644 :
645 : // Stop searching on this path: do not add the destination to the
646 : // search front and carry on as usual.
647 : case kBrowserTerminatePath:
648 E : need_pop_callback = true;
649 E : break;
650 :
651 : // Stop searching using this pattern: do not add the destination to the
652 : // search front, and mark the pattern as stopped.
653 : case kBrowserTerminatePattern:
654 i : stopped_[patid] = true;
655 i : l = front_[f]->links.size();
656 i : need_pop_callback = true;
657 i : break;
658 :
659 : // Both of these cause the search to terminate prematurely so we can
660 : // return immediately.
661 : case kBrowserTerminateAll:
662 : case kBrowserAbort:
663 i : return directive;
664 : }
665 :
666 : // Sometimes elements are the leaf node in a search, in which case we
667 : // need to immediately follow the push callback with a pop callback.
668 : // NOTE: We are currently handling the pop callback in two places: in
669 : // PopMatch and here. We could move all the handling to PopMatch if we
670 : // also pushed 'dead' search avenues to the front, but this would require
671 : // keeping additional state in the search front, or changing the semantics
672 : // of InvokeCallback and the logic in this routine, BrowseImpl and
673 : // PopMatch. Handling terminated paths here is far simpler.
674 E : if (need_pop_callback) {
675 : directive = elem->InvokePopCallback(*this,
676 : tag_lineage_,
677 E : symbol_lineage_);
678 E : if (directive == kBrowserTerminateAll || directive == kBrowserAbort)
679 i : return directive;
680 E : if (directive == kBrowserTerminatePattern) {
681 i : stopped_[patid] = true;
682 i : break; // This breaks out of the for loop.
683 : }
684 : }
685 E : }
686 E : }
687 :
688 E : front_size_.push_back(new_front);
689 E : return new_front == 0 ? kBrowserTerminatePath : kBrowserContinue;
690 E : }
691 :
692 E : DiaBrowser::BrowserDirective DiaBrowser::PopMatch(bool do_callbacks) {
693 E : if (do_callbacks) {
694 : // Before popping this bunch of elements from the search front, invoke their
695 : // callbacks with a 'pop' notification.
696 E : size_t i = front_.size() - front_size_.back();
697 E : for (; i < front_.size(); ++i) {
698 : // If this pattern is already stopped then we don't call the pop
699 : // callback.
700 E : size_t patid = front_[i]->pattern_id;
701 E : if (stopped_[patid])
702 i : continue;
703 :
704 : // Call the pop callback.
705 : BrowserDirective directive =
706 : front_[i]->InvokePopCallback(*this,
707 : tag_lineage_,
708 E : symbol_lineage_);
709 :
710 E : switch (directive) {
711 : // The path can't be stopped during a 'pop' notification, as its already
712 : // been explored by that point. So TerminatePath is a nop.
713 : case kBrowserContinue:
714 : case kBrowserTerminatePath:
715 i : break;
716 :
717 : // Stop searching using this pattern. This will prevent it from being
718 : // used in further search paths.
719 : case kBrowserTerminatePattern:
720 i : stopped_[patid] = true;
721 i : break;
722 :
723 : // Both of these cause the search to terminate prematurely.
724 : case kBrowserTerminateAll:
725 : case kBrowserAbort:
726 i : return directive;
727 : }
728 E : }
729 : }
730 :
731 : // Pop off the match history.
732 E : front_.resize(front_.size() - front_size_.back());
733 E : front_size_.pop_back();
734 :
735 E : return kBrowserContinue;
736 E : }
737 :
738 E : bool DiaBrowser::Browse(IDiaSymbol* root) {
739 E : PrepareForBrowse();
740 E : BrowserDirective directive = BrowseImpl(root, 0);
741 E : Reset();
742 E : return directive != kBrowserAbort;
743 E : }
744 :
745 : DiaBrowser::BrowserDirective DiaBrowser::BrowseImpl(IDiaSymbol* root,
746 E : size_t depth) {
747 E : if (sym_tags_[depth].none())
748 i : return kBrowserContinue;
749 :
750 : // Make sure we have a SymTagBitSet for the next level of recursion.
751 E : if (sym_tags_.size() < depth + 2)
752 E : sym_tags_.resize(depth + 2);
753 :
754 : // If all symbols are accepted, we can use SymTagNull as a wildcard rather
755 : // than iterating over each individual SymTag.
756 E : if (sym_tags_[depth].count() == sym_tags_[depth].size())
757 E : return BrowseEnum(root, depth, SymTagNull);
758 :
759 : // Iterate through all possible symbol tags that can be matched.
760 E : for (size_t i = 0; i < kSymTagCount; ++i) {
761 E : if (!sym_tags_[depth].test(i))
762 E : continue;
763 E : SymTag sym_tag = static_cast<SymTag>(kSymTagBegin + i);
764 E : BrowserDirective directive = BrowseEnum(root, depth, sym_tag);
765 E : if (directive == kBrowserTerminateAll || directive == kBrowserAbort)
766 i : return directive;
767 E : }
768 :
769 E : return kBrowserContinue;
770 E : }
771 :
772 : DiaBrowser::BrowserDirective DiaBrowser::BrowseEnum(
773 E : IDiaSymbol* root, size_t depth, SymTag sym_tag) {
774 : // Get the enum for this symbol type
775 E : ScopedComPtr<IDiaEnumSymbols> enum_symbols;
776 : HRESULT hr = root->findChildren(sym_tag,
777 : NULL,
778 : nsNone,
779 E : enum_symbols.Receive());
780 E : if (FAILED(hr)) {
781 i : LOG(ERROR) << "Failed to get DIA symbol enumerator: " << hr << ".";
782 i : return kBrowserAbort;
783 : }
784 :
785 : // Sometimes a NULL enum gets returned rather than an empty
786 : // enum. (Why?)
787 E : if (enum_symbols.get() == NULL)
788 E : return kBrowserContinue;
789 :
790 E : BrowserDirective directive = kBrowserContinue;
791 E : tag_lineage_.push_back(SymTagNull);
792 E : symbol_lineage_.push_back(SymbolPtr());
793 :
794 : // Iterate through the returned symbols.
795 E : while (true) {
796 E : SymbolPtr symbol;
797 E : ULONG fetched = 0;
798 E : hr = enum_symbols->Next(1, symbol.Receive(), &fetched);
799 E : if (FAILED(hr)) {
800 i : LOG(ERROR) << "Failed to enumerate DIA symbols: " << hr << ".";
801 i : directive = kBrowserAbort;
802 i : break;
803 : }
804 : // No more symbols?
805 E : if (fetched == 0)
806 E : break;
807 :
808 : // Get the symbol ID and tag type.
809 E : DWORD symbol_id = 0;
810 E : DWORD actual_sym_tag_dw = SymTagNull;
811 : if (FAILED(symbol->get_symIndexId(&symbol_id)) ||
812 E : FAILED(symbol->get_symTag(&actual_sym_tag_dw))) {
813 i : NOTREACHED() << "Failed to get symbol properties.";
814 i : directive = kBrowserAbort;
815 i : break;
816 : }
817 E : SymTag actual_sym_tag = static_cast<SymTag>(actual_sym_tag_dw);
818 E : if (sym_tag != SymTagNull)
819 E : DCHECK_EQ(sym_tag, actual_sym_tag);
820 :
821 E : tag_lineage_.back() = actual_sym_tag;
822 E : symbol_lineage_.back() = symbol;
823 :
824 : // Try to extend the match using this symbol. If this succeeds, recurse.
825 E : directive = PushMatch(actual_sym_tag, symbol_id, &sym_tags_[depth + 1]);
826 E : if (directive == kBrowserContinue)
827 E : directive = BrowseImpl(symbol.get(), depth + 1);
828 E : if (directive == kBrowserTerminateAll || directive == kBrowserAbort) {
829 : // We've terminated the search already, so we don't need to invoke the
830 : // pop callbacks.
831 i : PopMatch(false);
832 i : break;
833 : }
834 :
835 : // Roll back the search front, and terminate the search if need be.
836 E : directive = PopMatch(true);
837 E : if (directive == kBrowserTerminateAll || directive == kBrowserAbort)
838 i : break;
839 E : }
840 :
841 E : tag_lineage_.pop_back();
842 E : symbol_lineage_.pop_back();
843 :
844 E : return directive;
845 E : }
846 :
847 : namespace builder {
848 :
849 : typedef DiaBrowser::PatternBuilder PatternBuilder;
850 :
851 : Proxy::Proxy()
852 E : : pattern_builder_(new PatternBuilder()) {
853 E : }
854 :
855 : Proxy::Proxy(const PatternBuilder& pb)
856 E : : pattern_builder_(new PatternBuilder()) {
857 E : pattern_builder_->CopyFrom(pb);
858 E : }
859 :
860 : Proxy::Proxy(SymTag sym_tag)
861 E : : pattern_builder_(new PatternBuilder(sym_tag)) {
862 E : }
863 :
864 : Proxy::Proxy(SymTagBitSet sym_tags)
865 E : : pattern_builder_(new PatternBuilder(sym_tags)) {
866 E : }
867 :
868 E : Proxy::~Proxy() {
869 E : delete pattern_builder_;
870 E : }
871 :
872 E : Proxy Tag(SymTag sym_tag) {
873 E : return Proxy(sym_tag);
874 E : }
875 :
876 E : Proxy Tags(SymTagBitSet sym_tags) {
877 E : return Proxy(sym_tags);
878 E : }
879 :
880 : Proxy Tags(SymTag st0, SymTag st1, SymTag st2, SymTag st3,
881 E : SymTag st4, SymTag st5, SymTag st6, SymTag st7) {
882 E : DCHECK(st0 != kSymTagInvalid);
883 E : SymTagBitSet sym_tags;
884 E : AddToSymTagBitSet(st0, &sym_tags);
885 E : AddToSymTagBitSet(st1, &sym_tags);
886 E : AddToSymTagBitSet(st2, &sym_tags);
887 E : AddToSymTagBitSet(st3, &sym_tags);
888 E : AddToSymTagBitSet(st4, &sym_tags);
889 E : AddToSymTagBitSet(st5, &sym_tags);
890 E : AddToSymTagBitSet(st6, &sym_tags);
891 E : AddToSymTagBitSet(st7, &sym_tags);
892 E : DCHECK(sym_tags.count() > 0);
893 E : return Proxy(sym_tags);
894 E : }
895 :
896 : Proxy Not(SymTagBitSet sym_tags) {
897 : return Proxy(~sym_tags);
898 : }
899 :
900 : Proxy Not(SymTag st0, SymTag st1, SymTag st2, SymTag st3,
901 E : SymTag st4, SymTag st5, SymTag st6, SymTag st7) {
902 E : DCHECK(st0 != kSymTagInvalid);
903 E : SymTagBitSet sym_tags;
904 E : AddToSymTagBitSet(st0, &sym_tags);
905 E : AddToSymTagBitSet(st1, &sym_tags);
906 E : AddToSymTagBitSet(st2, &sym_tags);
907 E : AddToSymTagBitSet(st3, &sym_tags);
908 E : AddToSymTagBitSet(st4, &sym_tags);
909 E : AddToSymTagBitSet(st5, &sym_tags);
910 E : AddToSymTagBitSet(st6, &sym_tags);
911 E : AddToSymTagBitSet(st7, &sym_tags);
912 : // We don't DCHECK(sym_tags_.count() > 0) because it's possible and valid
913 : // for a Not(SymTagNull) to have created an empty SymTagBitSet. This will
914 : // fail on AddPattern, however.
915 E : return Proxy(~sym_tags);
916 E : }
917 :
918 : Proxy Seq(const Proxy& p0, const Proxy& p1, const Proxy& p2, const Proxy& p3,
919 E : const Proxy& p4, const Proxy& p5, const Proxy& p6, const Proxy& p7) {
920 E : DCHECK(p0->type() != PatternBuilder::kPatternNone);
921 E : DCHECK(p1->type() != PatternBuilder::kPatternNone);
922 E : PatternBuilder pb(PatternBuilder::kPatternSeq, p0, p1);
923 E : if (p2->type() != PatternBuilder::kPatternNone)
924 E : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p2));
925 E : if (p3->type() != PatternBuilder::kPatternNone)
926 E : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p3));
927 E : if (p4->type() != PatternBuilder::kPatternNone)
928 i : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p4));
929 E : if (p5->type() != PatternBuilder::kPatternNone)
930 i : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p5));
931 E : if (p6->type() != PatternBuilder::kPatternNone)
932 i : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p6));
933 E : if (p7->type() != PatternBuilder::kPatternNone)
934 i : pb.CopyFrom(PatternBuilder(PatternBuilder::kPatternSeq, pb, p7));
935 E : return Proxy(pb);
936 E : }
937 :
938 : Proxy Or(const Proxy& p0, const Proxy& p1, const Proxy& p2, const Proxy& p3,
939 E : const Proxy& p4, const Proxy& p5, const Proxy& p6, const Proxy& p7) {
940 E : DCHECK(p0->type() != PatternBuilder::kPatternNone);
941 E : DCHECK(p1->type() != PatternBuilder::kPatternNone);
942 : // We use the OrBuilder as an optimization to make sure that Tags
943 : // PatternBuilders are accumulated and simplified.
944 E : PatternBuilder pbor;
945 E : PatternBuilder::OrBuilder(p0, p1, &pbor);
946 E : if (p2->type() != PatternBuilder::kPatternNone) {
947 E : PatternBuilder pbtemp;
948 E : PatternBuilder::OrBuilder(pbor, p2, &pbtemp);
949 E : pbor.CopyFrom(pbtemp);
950 E : }
951 E : if (p3->type() != PatternBuilder::kPatternNone) {
952 E : PatternBuilder pbtemp;
953 E : PatternBuilder::OrBuilder(pbor, p3, &pbtemp);
954 E : pbor.CopyFrom(pbtemp);
955 E : }
956 E : if (p4->type() != PatternBuilder::kPatternNone) {
957 E : PatternBuilder pbtemp;
958 E : PatternBuilder::OrBuilder(pbor, p4, &pbtemp);
959 E : pbor.CopyFrom(pbtemp);
960 E : }
961 E : if (p5->type() != PatternBuilder::kPatternNone) {
962 E : PatternBuilder pbtemp;
963 E : PatternBuilder::OrBuilder(pbor, p5, &pbtemp);
964 E : pbor.CopyFrom(pbtemp);
965 E : }
966 E : if (p6->type() != PatternBuilder::kPatternNone) {
967 E : PatternBuilder pbtemp;
968 E : PatternBuilder::OrBuilder(pbor, p6, &pbtemp);
969 E : pbor.CopyFrom(pbtemp);
970 E : }
971 E : if (p7->type() != PatternBuilder::kPatternNone) {
972 E : PatternBuilder pbtemp;
973 E : PatternBuilder::OrBuilder(pbor, p7, &pbtemp);
974 E : pbor.CopyFrom(pbtemp);
975 E : }
976 E : return Proxy(pbor);
977 E : }
978 :
979 E : Proxy Opt(const Proxy& p) {
980 E : return Proxy(PatternBuilder(PatternBuilder::kPatternOpt, p));
981 E : }
982 :
983 E : Proxy Plus(const Proxy& p) {
984 E : return Proxy(PatternBuilder(PatternBuilder::kPatternPlus, p));
985 E : }
986 :
987 E : Proxy Star(const Proxy& p) {
988 E : return Proxy(PatternBuilder(PatternBuilder::kPatternStar, p));
989 E : }
990 :
991 E : Proxy Callback(const Proxy& p, const MatchCallback& push_callback) {
992 E : return Proxy(PatternBuilder(*p, push_callback, MatchCallback()));
993 E : }
994 :
995 : Proxy Callback(const Proxy& p,
996 : const MatchCallback& push_callback,
997 E : const MatchCallback& pop_callback) {
998 E : return Proxy(PatternBuilder(*p, push_callback, pop_callback));
999 E : }
1000 :
1001 : } // namespace builder
1002 :
1003 : } // namespace pe
|