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