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