1# Copyright 2017 The Chromium Authors. All rights reserved. 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5# TODO(dpranke): Rename this to 'expectations.py' to remove the 'parser' 6# part and make it a bit more generic. Consider if we can reword this to 7# also not talk about 'expectations' so much (i.e., to find a clearer way 8# to talk about them that doesn't have quite so much legacy baggage), but 9# that might not be possible. 10 11import itertools 12import re 13import logging 14 15from collections import OrderedDict 16from collections import defaultdict 17 18from typ import python_2_3_compat 19from typ.json_results import ResultType 20 21_EXPECTATION_MAP = { 22 'crash': ResultType.Crash, 23 'failure': ResultType.Failure, 24 'pass': ResultType.Pass, 25 'timeout': ResultType.Timeout, 26 'skip': ResultType.Skip 27} 28 29_RESULT_TAGS = { 30 ResultType.Failure: 'Failure', 31 ResultType.Crash: 'Crash', 32 ResultType.Timeout: 'Timeout', 33 ResultType.Pass: 'Pass', 34 ResultType.Skip: 'Skip' 35} 36 37_SLOW_TAG = 'Slow' 38_RETRY_ON_FAILURE_TAG = 'RetryOnFailure' 39 40 41class ConflictResolutionTypes(object): 42 UNION = 1 43 OVERRIDE = 2 44 45 46def _group_to_string(group): 47 msg = ', '.join(group) 48 k = msg.rfind(', ') 49 return msg[:k] + ' and ' + msg[k+2:] if k != -1 else msg 50 51 52def _default_tags_conflict(t1, t2): 53 return t1 != t2 54 55 56class ParseError(Exception): 57 58 def __init__(self, lineno, msg): 59 super(ParseError, self).__init__('%d: %s' % (lineno, msg)) 60 61 62class Expectation(object): 63 def __init__(self, reason=None, test='*', tags=None, results=None, lineno=0, 64 retry_on_failure=False, is_slow_test=False, 65 conflict_resolution=ConflictResolutionTypes.UNION, raw_tags=None, raw_results=None, 66 is_glob=False, trailing_comments=None): 67 """Constructor for expectations. 68 69 Args: 70 reason: String that indicates the reason for the expectation. 71 test: String indicating which test is being affected. 72 tags: List of tags that the expectation applies to. Tags are combined 73 using a logical and, i.e., all of the tags need to be present for 74 the expectation to apply. For example, if tags = ['Mac', 'Debug'], 75 then the test must be running with the 'Mac' and 'Debug' tags 76 set; just 'Mac', or 'Mac' and 'Release', would not qualify. 77 results: List of outcomes for test. Example: ['Skip', 'Pass'] 78 """ 79 tags = tags or [] 80 self._is_default_pass = not results 81 results = results or {ResultType.Pass} 82 reason = reason or '' 83 trailing_comments = trailing_comments or '' 84 assert python_2_3_compat.is_str(reason) 85 assert python_2_3_compat.is_str(test) 86 self._reason = reason 87 self._test = test 88 self._tags = frozenset(tags) 89 self._results = frozenset(results) 90 self._lineno = lineno 91 self._raw_tags = raw_tags 92 self._raw_results = raw_results 93 self.should_retry_on_failure = retry_on_failure 94 self.is_slow_test = is_slow_test 95 self.conflict_resolution = conflict_resolution 96 self._is_glob = is_glob 97 self._trailing_comments = trailing_comments 98 99 def __eq__(self, other): 100 return (self.reason == other.reason and self.test == other.test 101 and self.should_retry_on_failure == other.should_retry_on_failure 102 and self.is_slow_test == other.is_slow_test 103 and self.tags == other.tags and self.results == other.results 104 and self.lineno == other.lineno 105 and self.trailing_comments == other.trailing_comments) 106 107 def _set_string_value(self): 108 """This method will create an expectation line in string form and set the 109 _string_value member variable to it. If the _raw_results lists and _raw_tags 110 list are not set then the _tags list and _results set will be used to set them. 111 Setting the _raw_results and _raw_tags list to the original lists through the constructor 112 during parsing stops unintended modifications to test expectations when rewriting files. 113 """ 114 # If this instance is for a glob type expectation then do not escape 115 # the last asterisk 116 if self.is_glob: 117 assert len(self._test) and self._test[-1] == '*', ( 118 'For Expectation instances for glob type expectations, the test value ' 119 'must end in an asterisk') 120 pattern = self._test[:-1].replace('*', '\\*') + '*' 121 else: 122 pattern = self._test.replace('*', '\\*') 123 self._string_value = '' 124 if self._reason: 125 self._string_value += self._reason + ' ' 126 if self.raw_tags: 127 self._string_value += '[ %s ] ' % ' '.join(self.raw_tags) 128 self._string_value += pattern + ' ' 129 self._string_value += '[ %s ]' % ' '.join(self.raw_results) 130 if self._trailing_comments: 131 self._string_value += self._trailing_comments 132 133 def add_expectations(self, results, reason=None): 134 if reason: 135 self._reason = ' '.join(set(self._reason.split() + reason.split())) 136 if not results <= self._results: 137 self._results = frozenset(self._results | results) 138 self._raw_results = sorted( 139 [_RESULT_TAGS[t] for t in self._results]) 140 141 @property 142 def raw_tags(self): 143 if not self._raw_tags: 144 self._raw_tags = {t[0].upper() + t[1:].lower() for t in self._tags} 145 return self._raw_tags 146 147 @property 148 def raw_results(self): 149 if not self._raw_results: 150 self._raw_results = {_RESULT_TAGS[t] for t in self._results} 151 if self.is_slow_test: 152 self._raw_results.add(_SLOW_TAG) 153 if self.should_retry_on_failure: 154 self._raw_results.add(_RETRY_ON_FAILURE_TAG) 155 return self._raw_results 156 157 def to_string(self): 158 self._set_string_value() 159 return self._string_value 160 161 @property 162 def is_default_pass(self): 163 return self._is_default_pass 164 165 @property 166 def reason(self): 167 return self._reason 168 169 @property 170 def test(self): 171 return self._test 172 173 @test.setter 174 def test(self, v): 175 if not len(v): 176 raise ValueError('Cannot set test to empty string') 177 if self.is_glob and v[-1] != '*': 178 raise ValueError( 179 'test value for glob type expectations must end with an asterisk') 180 self._test = v 181 182 @property 183 def tags(self): 184 return self._tags 185 186 @property 187 def results(self): 188 return self._results 189 190 @property 191 def lineno(self): 192 return self._lineno 193 194 @lineno.setter 195 def lineno(self, lineno): 196 self._lineno = lineno 197 198 @property 199 def is_glob(self): 200 return self._is_glob 201 202 @property 203 def trailing_comments(self): 204 return self._trailing_comments 205 206 207class TaggedTestListParser(object): 208 """Parses lists of tests and expectations for them. 209 210 This parser covers the 'tagged' test lists format in: 211 bit.ly/chromium-test-list-format 212 213 Takes raw expectations data as a string read from the expectation file 214 in the format: 215 216 # This is an example expectation file. 217 # 218 # tags: [ 219 # Mac Mac10.1 Mac10.2 220 # Win Win8 221 # ] 222 # tags: [ Release Debug ] 223 224 crbug.com/123 [ Win ] benchmark/story [ Skip ] 225 ... 226 """ 227 CONFLICTS_ALLOWED = '# conflicts_allowed: ' 228 RESULT_TOKEN = '# results: [' 229 TAG_TOKEN = '# tags: [' 230 # The bug field (optional), including optional subproject. 231 BUG_PREFIX_REGEX = '(?:crbug.com/|skbug.com/|webkit.org/)' 232 _MATCH_STRING = r'^(?:(' + BUG_PREFIX_REGEX + '(?:[^/]*/)?\d+\s)*)' 233 _MATCH_STRING += r'(?:\[ (.+) \] )?' # The label field (optional). 234 _MATCH_STRING += r'(\S+) ' # The test path field. 235 _MATCH_STRING += r'\[ ([^\[.]+) \]' # The expectation field. 236 _MATCH_STRING += r'(\s+#.*)?$' # End comment (optional). 237 MATCHER = re.compile(_MATCH_STRING) 238 239 def __init__(self, raw_data, conflict_resolution=ConflictResolutionTypes.UNION): 240 self.tag_sets = [] 241 self.conflicts_allowed = False 242 self.expectations = [] 243 self._allowed_results = set() 244 self._tag_to_tag_set = {} 245 self._conflict_resolution = conflict_resolution 246 self._parse_raw_expectation_data(raw_data) 247 248 def _parse_raw_expectation_data(self, raw_data): 249 lines = raw_data.splitlines() 250 lineno = 1 251 num_lines = len(lines) 252 tag_sets_intersection = set() 253 first_tag_line = None 254 while lineno <= num_lines: 255 line = lines[lineno - 1].strip() 256 if (line.startswith(self.TAG_TOKEN) or 257 line.startswith(self.RESULT_TOKEN)): 258 if line.startswith(self.TAG_TOKEN): 259 token = self.TAG_TOKEN 260 else: 261 token = self.RESULT_TOKEN 262 # Handle tags. 263 if self.expectations: 264 raise ParseError(lineno, 265 'Tag found after first expectation.') 266 if not first_tag_line: 267 first_tag_line = lineno 268 right_bracket = line.find(']') 269 if right_bracket == -1: 270 # multi-line tag set 271 tag_set = set( 272 [t.lower() for t in line[len(token):].split()]) 273 lineno += 1 274 while lineno <= num_lines and right_bracket == -1: 275 line = lines[lineno - 1].strip() 276 if line[0] != '#': 277 raise ParseError( 278 lineno, 279 'Multi-line tag set missing leading "#"') 280 right_bracket = line.find(']') 281 if right_bracket == -1: 282 tag_set.update( 283 [t.lower() for t in line[1:].split()]) 284 lineno += 1 285 else: 286 tag_set.update( 287 [t.lower() 288 for t in line[1:right_bracket].split()]) 289 if line[right_bracket+1:]: 290 raise ParseError( 291 lineno, 292 'Nothing is allowed after a closing tag ' 293 'bracket') 294 else: 295 if line[right_bracket+1:]: 296 raise ParseError( 297 lineno, 298 'Nothing is allowed after a closing tag ' 299 'bracket') 300 tag_set = set( 301 [t.lower() 302 for t in line[len(token):right_bracket].split()]) 303 if token == self.TAG_TOKEN: 304 tag_sets_intersection.update( 305 (t for t in tag_set if t in self._tag_to_tag_set)) 306 self.tag_sets.append(tag_set) 307 self._tag_to_tag_set.update( 308 {tg: id(tag_set) for tg in tag_set}) 309 else: 310 self._allowed_results.update(tag_set) 311 elif line.startswith(self.CONFLICTS_ALLOWED): 312 bool_value = line[len(self.CONFLICTS_ALLOWED):].lower() 313 if bool_value not in ('true', 'false'): 314 raise ParseError( 315 lineno, 316 ("Unrecognized value '%s' given for conflicts_allowed " 317 "descriptor" % 318 bool_value)) 319 self.conflicts_allowed = bool_value == 'true' 320 elif line.startswith('#') or not line: 321 # Ignore, it is just a comment or empty. 322 lineno += 1 323 continue 324 elif not tag_sets_intersection: 325 self.expectations.append( 326 self._parse_expectation_line(lineno, line)) 327 else: 328 break 329 lineno += 1 330 if tag_sets_intersection: 331 is_multiple_tags = len(tag_sets_intersection) > 1 332 tag_tags = 'tags' if is_multiple_tags else 'tag' 333 was_were = 'were' if is_multiple_tags else 'was' 334 error_msg = 'The {0} {1} {2} found in multiple tag sets'.format( 335 tag_tags, _group_to_string( 336 sorted(list(tag_sets_intersection))), was_were) 337 raise ParseError(first_tag_line, error_msg) 338 339 def _parse_expectation_line(self, lineno, line): 340 match = self.MATCHER.match(line) 341 if not match: 342 raise ParseError(lineno, 'Syntax error: %s' % line) 343 344 reason, raw_tags, test, raw_results, trailing_comments = match.groups() 345 346 # TODO(rmhasan): Find a better regex to capture the reasons. The '*' in 347 # the reasons regex only allows us to get the last bug. We need to write 348 # the below code to get the full list of reasons. 349 if reason: 350 reason = reason.strip() 351 index = line.find(reason) 352 reason = line[:index] + reason 353 354 tags = [raw_tag.lower() for raw_tag in raw_tags.split()] if raw_tags else [] 355 tag_set_ids = set() 356 357 for i in range(len(test)-1): 358 if test[i] == '*' and ((i > 0 and test[i-1] != '\\') or i == 0): 359 raise ParseError(lineno, 360 'Invalid glob, \'*\' can only be at the end of the pattern') 361 362 for t in tags: 363 if not t in self._tag_to_tag_set: 364 raise ParseError(lineno, 'Unknown tag "%s"' % t) 365 else: 366 tag_set_ids.add(self._tag_to_tag_set[t]) 367 368 if len(tag_set_ids) != len(tags): 369 error_msg = ('The tag group contains tags that are ' 370 'part of the same tag set') 371 tags_by_tag_set_id = defaultdict(list) 372 for t in tags: 373 tags_by_tag_set_id[self._tag_to_tag_set[t]].append(t) 374 for tag_intersection in tags_by_tag_set_id.values(): 375 error_msg += ('\n - Tags %s are part of the same tag set' % 376 _group_to_string(sorted(tag_intersection))) 377 raise ParseError(lineno, error_msg) 378 379 results = [] 380 retry_on_failure = False 381 is_slow_test = False 382 for r in raw_results.split(): 383 r = r.lower() 384 if r not in self._allowed_results: 385 raise ParseError(lineno, 'Unknown result type "%s"' % r) 386 try: 387 # The test expectations may contain expected results and 388 # the RetryOnFailure tag 389 if r in _EXPECTATION_MAP: 390 results.append(_EXPECTATION_MAP[r]) 391 elif r == 'retryonfailure': 392 retry_on_failure = True 393 elif r == 'slow': 394 is_slow_test = True 395 else: 396 raise KeyError 397 except KeyError: 398 raise ParseError(lineno, 'Unknown result type "%s"' % r) 399 400 # remove escapes for asterisks 401 is_glob = not test.endswith('\\*') and test.endswith('*') 402 test = test.replace('\\*', '*') 403 if raw_tags: 404 raw_tags = raw_tags.split() 405 if raw_results: 406 raw_results = raw_results.split() 407 # Tags from tag groups will be stored in lower case in the Expectation 408 # instance. These tags will be compared to the tags passed in to 409 # the Runner instance which are also stored in lower case. 410 return Expectation( 411 reason, test, tags, results, lineno, retry_on_failure, is_slow_test, 412 self._conflict_resolution, raw_tags=raw_tags, raw_results=raw_results, 413 is_glob=is_glob, trailing_comments=trailing_comments) 414 415 416class TestExpectations(object): 417 418 def __init__(self, tags=None, ignored_tags=None): 419 self.tag_sets = [] 420 self.ignored_tags = set(ignored_tags or []) 421 self.set_tags(tags or []) 422 # Expectations may either refer to individual tests, or globs of 423 # tests. Each test (or glob) may have multiple sets of tags and 424 # expected results, so we store these in dicts ordered by the string 425 # for ease of retrieve. glob_exps use an OrderedDict rather than 426 # a regular dict for reasons given below. 427 self.individual_exps = OrderedDict() 428 self.glob_exps = OrderedDict() 429 self._tags_conflict = _default_tags_conflict 430 431 def set_tags(self, tags, raise_ex_for_bad_tags=False): 432 self.validate_condition_tags(tags, raise_ex_for_bad_tags) 433 self._tags = [tag.lower() for tag in tags] 434 435 def add_tags(self, new_tags, raise_ex_for_bad_tags=False): 436 self.validate_condition_tags(new_tags, raise_ex_for_bad_tags) 437 self._tags = list( 438 set(self._tags) | set([tag.lower() for tag in new_tags])) 439 440 @property 441 def tags(self): 442 return self._tags[:] 443 444 def validate_condition_tags(self, tags, raise_ex_for_bad_tags): 445 # This function will be used to validate if each tag in the tags list 446 # is declared in a test expectations file. This validation will make 447 # sure that the tags written in the test expectations files match tags 448 # that are generated by the test runner. 449 def _pluralize_unknown(missing): 450 if len(missing) > 1: 451 return ('s %s ' % ', '.join(missing[:-1]) + 'and %s ' % missing[-1] + 'are', 452 'have', 's are') 453 else: 454 return (' %s ' % missing[0] + 'is', 'has', ' is') 455 tags = [t.lower() for t in tags] 456 unknown_tags = sorted([ 457 t for t in tags 458 if self.tag_sets and all( 459 t not in tag_set and t not in self.ignored_tags 460 for tag_set in self.tag_sets)]) 461 if unknown_tags: 462 msg = ( 463 'Tag%s not declared in the expectations file and %s not been ' 464 'explicitly ignored by the test. There may have been a typo in ' 465 'the expectations file. Please make sure the aforementioned ' 466 'tag%s declared at the top of the expectations file.' % 467 _pluralize_unknown(unknown_tags)) 468 if raise_ex_for_bad_tags: 469 raise ValueError(msg) 470 else: 471 logging.warning(msg) 472 473 def parse_tagged_list(self, raw_data, file_name='', 474 tags_conflict=_default_tags_conflict, 475 conflict_resolution=ConflictResolutionTypes.UNION): 476 ret = 0 477 self.file_name = file_name 478 try: 479 parser = TaggedTestListParser(raw_data, conflict_resolution) 480 except ParseError as e: 481 return 1, str(e) 482 self.tag_sets = parser.tag_sets 483 self._tags_conflict = tags_conflict 484 # TODO(crbug.com/83560) - Add support for multiple policies 485 # for supporting multiple matching lines, e.g., allow/union, 486 # reject, etc. Right now, you effectively just get a union. 487 glob_exps = [] 488 for exp in parser.expectations: 489 if exp.is_glob: 490 glob_exps.append(exp) 491 else: 492 self.individual_exps.setdefault(exp.test, []).append(exp) 493 494 # Each glob may also have multiple matching lines. By ordering the 495 # globs by decreasing length, this allows us to find the most 496 # specific glob by a simple linear search in expected_results_for(). 497 glob_exps.sort(key=lambda exp: len(exp.test), reverse=True) 498 for exp in glob_exps: 499 self.glob_exps.setdefault(exp.test, []).append(exp) 500 501 errors = '' 502 if not parser.conflicts_allowed: 503 errors = self.check_test_expectations_patterns_for_conflicts() 504 ret = 1 if errors else 0 505 return ret, errors 506 507 def merge_test_expectations(self, other): 508 # Merges another TestExpectation instance into this instance. 509 # It will merge the other instance's and this instance's 510 # individual_exps and glob_exps dictionaries. 511 self.add_tags(other.tags) 512 for pattern, exps in other.individual_exps.items(): 513 self.individual_exps.setdefault(pattern, []).extend(exps) 514 for pattern, exps in other.glob_exps.items(): 515 self.glob_exps.setdefault(pattern, []).extend(exps) 516 # resort the glob patterns by length in self.glob_exps ordered 517 # dictionary 518 glob_exps = self.glob_exps 519 self.glob_exps = OrderedDict() 520 for pattern, exps in sorted( 521 glob_exps.items(), key=lambda item: len(item[0]), reverse=True): 522 self.glob_exps[pattern] = exps 523 524 def expectations_for(self, test): 525 # Returns an Expectation. 526 # 527 # A given test may have multiple expectations, each with different 528 # sets of tags that apply and different expected results, e.g.: 529 # 530 # [ Mac ] TestFoo.test_bar [ Skip ] 531 # [ Debug Win ] TestFoo.test_bar [ Pass Failure ] 532 # 533 # To determine the expected results for a test, we have to loop over 534 # all of the failures matching a test, find the ones whose tags are 535 # a subset of the ones in effect, and return the union of all of the 536 # results. For example, if the runner is running with {Debug, Mac, Mac10.12} 537 # then lines with no tags, {Mac}, or {Debug, Mac} would all match, but 538 # {Debug, Win} would not. We also have to set the should_retry_on_failure 539 # boolean variable to True if any of the expectations have the 540 # should_retry_on_failure flag set to true 541 # 542 # The longest matching test string (name or glob) has priority. 543 self._results = set() 544 self._reasons = set() 545 self._exp_tags = set() 546 self._should_retry_on_failure = False 547 self._is_slow_test = False 548 self._trailing_comments = str() 549 550 def _update_expected_results(exp): 551 if exp.tags.issubset(self._tags): 552 if exp.conflict_resolution == ConflictResolutionTypes.UNION: 553 if not exp.is_default_pass: 554 self._results.update(exp.results) 555 self._should_retry_on_failure |= exp.should_retry_on_failure 556 self._is_slow_test |= exp.is_slow_test 557 self._exp_tags.update(exp.tags) 558 if exp.trailing_comments: 559 self._trailing_comments += exp.trailing_comments + '\n' 560 if exp.reason: 561 self._reasons.update([exp.reason]) 562 else: 563 self._results = set(exp.results) 564 self._should_retry_on_failure = exp.should_retry_on_failure 565 self._is_slow_test = exp.is_slow_test 566 self._exp_tags = set(exp.tags) 567 self._trailing_comments = exp.trailing_comments 568 if exp.reason: 569 self._reasons = {exp.reason} 570 571 # First, check for an exact match on the test name. 572 for exp in self.individual_exps.get(test, []): 573 _update_expected_results(exp) 574 575 if self._results or self._is_slow_test or self._should_retry_on_failure: 576 return Expectation( 577 test=test, results=self._results, tags=self._exp_tags, 578 retry_on_failure=self._should_retry_on_failure, 579 is_slow_test=self._is_slow_test, reason=' '.join(self._reasons), 580 trailing_comments=self._trailing_comments) 581 582 # If we didn't find an exact match, check for matching globs. Match by 583 # the most specific (i.e., longest) glob first. Because self.globs_exps 584 # is ordered by length, this is a simple linear search 585 for glob, exps in self.glob_exps.items(): 586 glob = glob[:-1] 587 if test.startswith(glob): 588 for exp in exps: 589 _update_expected_results(exp) 590 # if *any* of the exps matched, results will be non-empty, 591 # and we're done. If not, keep looking through ever-shorter 592 # globs. 593 if self._results or self._is_slow_test or self._should_retry_on_failure: 594 return Expectation( 595 test=test, results=self._results, tags=self._exp_tags, 596 retry_on_failure=self._should_retry_on_failure, 597 is_slow_test=self._is_slow_test, reason=' '.join(self._reasons), 598 trailing_comments=self._trailing_comments) 599 600 # Nothing matched, so by default, the test is expected to pass. 601 return Expectation(test=test) 602 603 def tag_sets_conflict(self, s1, s2): 604 # Tag sets s1 and s2 have no conflict when there exists a tag in s1 605 # and tag in s2 that are from the same tag declaration set and do not 606 # conflict with each other. 607 for tag_set in self.tag_sets: 608 for t1, t2 in itertools.product(s1, s2): 609 if (t1 in tag_set and t2 in tag_set and 610 self._tags_conflict(t1, t2)): 611 return False 612 return True 613 614 def check_test_expectations_patterns_for_conflicts(self): 615 # This function makes sure that any test expectations that have the same 616 # pattern do not conflict with each other. Test expectations conflict 617 # if their tag sets do not have conflicting tags. Tags conflict when 618 # they belong to the same tag declaration set. For example an 619 # expectations file may have a tag declaration set for operating systems 620 # which might look like [ win linux]. A test expectation that has the 621 # linux tag will not conflict with an expectation that has the win tag. 622 error_msg = '' 623 patterns_to_exps = dict(self.individual_exps) 624 patterns_to_exps.update(self.glob_exps) 625 for pattern, exps in patterns_to_exps.items(): 626 conflicts_exist = False 627 for e1, e2 in itertools.combinations(exps, 2): 628 if self.tag_sets_conflict(e1.tags, e2.tags): 629 if not conflicts_exist: 630 error_msg += ( 631 '\nFound conflicts for pattern %s%s:\n' % 632 (pattern, 633 (' in %s' % 634 self.file_name if self.file_name else ''))) 635 conflicts_exist = True 636 error_msg += (' line %d conflicts with line %d\n' % 637 (e1.lineno, e2.lineno)) 638 return error_msg 639 640 def check_for_broken_expectations(self, test_names): 641 # It returns a list expectations that do not apply to any test names in 642 # the test_names list. 643 # 644 # args: 645 # test_names: list of test names that are used to find test expectations 646 # that do not apply to any of test names in the list. 647 broken_exps = [] 648 test_names = set(test_names) 649 for pattern, exps in self.individual_exps.items(): 650 if pattern not in test_names: 651 broken_exps.extend(exps) 652 653 # look for broken glob expectations 654 # first create a trie of test names 655 trie = {} 656 broken_glob_exps = [] 657 for test in test_names: 658 _trie = trie.setdefault(test[0], {}) 659 for l in test[1:]: 660 _trie = _trie.setdefault(l, {}) 661 _trie.setdefault('\0', {}) 662 663 # look for globs that do not match any test names and append their 664 # expectations to glob_broken_exps 665 for pattern, exps in self.glob_exps.items(): 666 _trie = trie 667 for i, l in enumerate(pattern): 668 if l == '*' and i == len(pattern) - 1: 669 break 670 if l not in _trie: 671 broken_glob_exps.extend(exps) 672 break 673 _trie = _trie[l] 674 return broken_exps + broken_glob_exps 675