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 E : : sym_tags(),
55 E : outgoing_sym_tags(),
56 E : links(),
57 E : 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 E : : type_(kPatternNone) {
145 E : }
146 :
147 E : explicit PatternBuilder(SymTag sym_tag)
148 E : : 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 E : : 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 E : : type_(type),
166 E : 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 E : : 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 E : : type_(kPatternCallback),
189 E : push_callback_(push_callback),
190 E : pop_callback_(pop_callback),
191 E : 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 : std::unique_ptr<PatternBuilder> pb0_;
448 : std::unique_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 : std::unique_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 E : if (elem->links.size() == 0 ||
546 : !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(SymTag sym_tag,
599 : uint32_t symbol_id,
600 E : 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 E : BrowserDirective directive = elem->InvokePushCallback(*this,
630 : tag_lineage_,
631 : 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 E : directive = elem->InvokePopCallback(*this,
676 : tag_lineage_,
677 : 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 E : front_[i]->InvokePopCallback(*this,
707 : tag_lineage_,
708 : 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 E : HRESULT hr = root->findChildren(sym_tag,
777 : NULL,
778 : nsNone,
779 : 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 E : if (FAILED(symbol->get_symIndexId(&symbol_id)) ||
812 : 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
|