1#! /usr/bin/env python3 2 3# Copyright 2007 Google Inc. 4# 5# This program is free software; you can redistribute it and/or 6# modify it under the terms of the GNU General Public License 7# as published by the Free Software Foundation; either version 2 8# of the License, or (at your option) any later version. 9# 10# This program is distributed in the hope that it will be useful, 11# but WITHOUT ANY WARRANTY; without even the implied warranty of 12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13# GNU General Public License for more details. 14# 15# You should have received a copy of the GNU General Public License 16# along with this program; if not, write to the Free Software 17# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 18# USA. 19 20"""A graph-based algorithm for memoizing include closure calculations.""" 21 22__author__ = "Nils Klarlund" 23 24# TODO(klarlund) For computed includes, some static analysis checks must be 25# introduced to verify soundness of node reutilization in FindNode. 26 27import os 28 29import basics 30import macro_eval 31import parse_file 32import statistics 33import include_analyzer 34 35Debug = basics.Debug 36DEBUG_TRACE = basics.DEBUG_TRACE 37DEBUG_DATA = basics.DEBUG_DATA 38NotCoveredError = basics.NotCoveredError 39 40# RESOLUTION MODES 41 42RESOLVED = 1 # filepath already resolved and denotes an existing file 43QUOTE = 2 # filepath to be resolved against quote directories 44ANGLE = 3 # filepath to be resolved against angle directories 45NEXT = 4 # filepath to be resolved against each and every quote 46 # directory; this is how we handle #include_next 47RESOLUTION_MODES = [ RESOLVED, QUOTE, ANGLE, NEXT ] 48# Textual representation of RESOLUTION_MODES. 49RESOLUTION_MODES_STR = [ None, 'RESOLVED', 'QUOTE', 'ANGLE', 'NEXT' ] 50 51 52# MAIN COURSE 53 54class UnionCache(object): 55 """Frozen sets and their unions, represented by integers. 56 57 Frozensets are Python's immutable and hashable sets. We hash them into set 58 ids, which are integers. That allows us to cache union operations efficiently. 59 """ 60 61 def __init__(self): 62 """Constructor: 63 Instance variables: 64 members: members[set_id] = frozenset([s1,..., sn]), the members of the set 65 cache: cache[(set1_id, set2_id)] = the id of the union of set1 and set2 66 id_map: the set of frozen sets we have seen mapped to {1, 2, ..} 67 """ 68 self.members = {} 69 self.cache = {} 70 self.id_map = {} 71 72 def SetId(self, members): 73 """Memoize the frozenset of members and return set id.""" 74 frozen = frozenset(members) 75 try: 76 return self.id_map[frozen] 77 except KeyError: 78 self.id_map[frozen] = len(self.id_map) + 1 79 self.members[len(self.id_map)] = frozen 80 return len(self.id_map) 81 82 def Elements(self, set_id): 83 """The frozenset corresponding to a set id.""" 84 return self.members[set_id] 85 86 def Union(self, set1_id, set2_id): 87 """Return the set id of the union of sets represented by set ids.""" 88 try: 89 return self.cache[(set1_id, set2_id)] 90 except KeyError: 91 frozen = self.members[set1_id] | self.members[set2_id] 92 frozen_id = self.SetId(frozen) 93 self.cache[(set1_id, set2_id)] = frozen_id 94 return frozen_id 95 96 97class SupportRecord(object): 98 """Record the symbols that expressions depend on. 99 100 A support record is an object that contains a mutable support set of symbols. 101 Each node in the summary graph is associated with a support record. It is the 102 set of symbols upon which the included computes depend. A support record is 103 initially deemed valid. If a symbol is redefined, then it becomes invalid. 104 For efficiency, the valid field is sometimes explicitly handled by a user of 105 this object. 106 """ 107 108 def __init__(self, support_master): 109 """Constructor. 110 Argument: 111 support_master: a record for holding the reverse mapping from symbols to 112 support records that contain them. 113 Instance Variables: 114 support_master: see above 115 union_cache: a union cache for set manipulation 116 support_id: the id of a set in union_cache; the set consists of all 117 symbols referenced by computed includes in any include 118 dependency of the node to which the support record belongs 119 valid: a Boolean 120 """ 121 self.support_master = support_master 122 self.valid = True 123 self.union_cache = support_master.union_cache 124 self.support_id = self.union_cache.SetId([]) 125 126 def Update(self, set_id): 127 """Augment the support record with the set represented by set_id. 128 """ 129 union_id = self.union_cache.Union(self.support_id, 130 set_id) 131 if union_id != self.support_id: 132 self.support_master.SupportRecordDependencyAdd( 133 self.union_cache.Elements(set_id), 134 self) 135 self.support_id = union_id 136 137 def UpdateSet(self, symbols): 138 """Add symbols to the support. 139 140 This function is similar to Update, but the argument is a list of elements. 141 """ 142 self.Update(self.union_cache.SetId(symbols)) 143 144 145class SupportMaster(object): 146 """Record the support records that depend on a given symbol. 147 148 A map symbol_to_records is maintained. For each symbol s 149 self.symbol_to_records[s] is the set of support records r whose support set 150 contains s.""" 151 152 def __init__(self): 153 """Constructor. 154 155 Instance variables: 156 symbol_to_records: a mapping to record sets 157 union_cache: a UnionCache for memoizing sets and their unions 158 """ 159 self.symbol_to_records = {} 160 self.union_cache = UnionCache() 161 162 def SupportRecordDependencyAdd(self, symbols, support_record): 163 """Add dependency of support record on symbol.""" 164 for symbol in symbols: 165 if symbol not in self.symbol_to_records: 166 self.symbol_to_records[symbol] = set([]) 167 self.symbol_to_records[symbol].add(support_record) 168 169 def InvalidateRecords(self, symbol): 170 """Mark as invalid all support records whose set contains symbol.""" 171 if symbol in self.symbol_to_records: 172 for support_record in self.symbol_to_records[symbol]: 173 support_record.valid = False 174 175 176class IncludeAnalyzerMemoizingNode(include_analyzer.IncludeAnalyzer): 177 """A memoizing algorithm for include analysis based on a graph construction. 178 179 Instance variables: 180 181 master_cache: a two-level node cache 182 183 The key of the top-level cache is an include configuration of the form 184 (currdir_idx, quote_dirs, angle_dirs) 185 186 The value of the top-level cache is a node-cache (defined next). 187 188 The key of the second-level (node) cache has the form 189 (filepath_idx, resolution_mode, file_dir_idx) 190 191 A node is the value of the second-level (node) cache. It has the form 192 [filepath_real_idx, filepath_resolved_pair, [node_0, ...node_n-1], 193 support_record] 194 195 where each node_i, for 1 <= i < n, is a node representing a direct include 196 dependency of node. The direct include dependencies are the edges of a 197 directed graph called the summary graph. 198 199 TODO(csilvers): document what the values of the node-cache mean. 200 201 In this class, the top-level key is referred to as 'incl_config', the 202 top-level value is referred to as 'node_cache_for_incl_config', the 203 second-level key is referred to as 'key', and the second-level value is 204 referred to as 'node'. 205 206 There are many disjoint summary graphs, one for each include configuration. 207 Each node of a summary graph is the image of a key, that is, there are values 208 incl_config and key such that node == master_cache[incl_config][key]. 209 210 As stated the node cache works pre-resolution. But it may well be that, say, 211 two occurrences of #include "foo.h" in files with different file directories 212 (that is, the files containing the foo.h includes are in different 213 directories) actually resolve to the same foo.h file. In that case, we should 214 reuse the foo.h node -- with a catch: all though the file may be the same 215 real file, their containing directories may be different. For example, the 216 file may be in the real location /D/foo.h, but it may also be known as 217 /E/foo.h, where E is a directory containing a symbolic link foo.h pointing to 218 /D/foo.h. If file foo.h has a quoted include of bar.h, that is, contains the 219 directive 220 221 #include "bar.h" 222 223 then bar.h is looked for in /D if the file directory is /D, but it is looked 224 for in /E if the file directory is /E. That is the real file directory of 225 /E/foo.h is *not* the directory component of the realpath of /E/foo.h. 226 Rather, it is the realpath of the directory component of /E/foo.h, that is, 227 the realpath of /E. 228 229 Thus, if we memoize files according to their real location, then the file 230 directory as understood above must also be taken into account. 231 232 In particular, we also use as keys pairs of the form: 233 234 (realpath index of resolved file, real path index of filedir). 235 236 This realpath-oriented memoization is not a frivolous attempt at optimization. 237 It is essential to avoiding infinite loops as in: 238 239 D/mem.h 240 D/../D/mem.h 241 D/../D/../D/mem.h 242 243 generated by an include of the form "#include ../D/mem.h" in file mem.h. 244 245 One would think that obviosly these prefixes denote the same location. But 246 they need not! For D of the first line could be a symbolic link to a real 247 directory dir1_D. And, the second D could be another symbolic link in 248 dir1_D/ to dir2_D, etc... 249 250 So, when the include processor is lead astray by includes that resolve this 251 way it is by no means obvious how to investigate the paths with symbolic links 252 of the form 253 254 (D/..)* 255 256 This will diverge even if there is just one mem.h file with an include of 257 ../D/mem.h started in the real directory D. [Remember that the include 258 processor does not heed include guards.] 259 260 For termination, we rely on the fact that eventually the pair (realpath of 261 file, real path of file directory) will be seen again (because there are 262 finitely many files and directories). In practice, with this technique, the 263 recursion is stopped at the second attempt to include mem.h. 264 """ 265 266 # The magic '3' selects the fourth component of a node, see the class 267 # documentation. 268 SUPPORT_RECORD = 3 269 270 def _InitializeAllCachesMemoizing(self): 271 self.master_cache = {} 272 # Keep track of the support of each included file. The support of the file 273 # is the union of the support of expressions in computed includes in the 274 # file or in recursively included file. 275 self.support_master = SupportMaster() 276 # Enable the mechanism that invalidates all support records that contain a 277 # symbol that is being defined or redefined. 278 self.parse_file.SetDefineCallback(self.support_master.InvalidateRecords) 279 280 def __init__(self, client_root_keeper, stat_reset_triggers={}): 281 """Constructor.""" 282 include_analyzer.IncludeAnalyzer.__init__(self, 283 client_root_keeper, 284 stat_reset_triggers) 285 self._InitializeAllCachesMemoizing() 286 287 def ClearStatCaches(self): 288 """Reset stat caches and the node cache, which depends on stat caches.""" 289 # First, clear caches as the IncludeAnalyzer class prescribes it. 290 include_analyzer.IncludeAnalyzer.ClearStatCaches(self) 291 # Then, clear own caches. 292 self._InitializeAllCachesMemoizing() 293 294 def _PrintableFilePath(self, fp): 295 return (isinstance(fp, int) and self.includepath_map.String(fp) 296 or isinstance(fp, tuple) and 297 (self.directory_map.string[fp[0]], 298 self.includepath_map.string[fp[1]])) 299 300 301 def RunAlgorithm(self, filepath_resolved_pair, filepath_real_idx): 302 """See RunAlgorithm of class IncludeAnalyzer in include_analyzer.""" 303 incl_config = (self.currdir_idx, self.quote_dirs, self.angle_dirs) 304 try: 305 nodes_for_incl_config = self.master_cache[incl_config] 306 except KeyError: 307 nodes_for_incl_config = self.master_cache[incl_config] = {} 308 309 # Process symbols defined on command line. 310 for d_opt in self.d_opts: 311 if len(d_opt) == 1: 312 lhs, rhs = d_opt[0], "1" 313 elif len(d_opt) == 2: 314 [lhs, rhs] = d_opt 315 parse_file.InsertMacroDefInTable(lhs, rhs, self.symbol_table, 316 self.support_master.InvalidateRecords) 317 else: 318 # Assume this is a syntax error of some sort. 319 pass 320 321 # Construct or find the node for filepath_resolved. 322 node = self.FindNode(nodes_for_incl_config, 323 filepath_resolved_pair, 324 RESOLVED, 325 None, 326 filepath_real_idx) 327 # Find the nodes reachable from node and represent as an include closure. 328 include_closure = {} 329 self._CalculateIncludeClosureExceptSystem(node, include_closure) 330 return include_closure 331 332 def FindNode(self, 333 nodes_for_incl_config, 334 fp, 335 resolution_mode, 336 file_dir_idx=None, 337 fp_real_idx=None): 338 """Find a previously constructed node or create a new node. 339 340 Arguments: 341 nodes_for_incl_config: a dictionary (see class documentation). 342 fp: a filepath index or, if resolution_mode == RESOLVED, a filepath pair 343 resolution_mode: an integer in RESOLUTION_MODES 344 file_dir_idx: consider the file F that has the line '#include "fp"' 345 which is causing us to call FindNode on fp. file_dir_idx is the 346 index of dirname(F). (This argument affects the semantics of 347 resolution for resolution_mode == QUOTE.) 348 fp_real_idx: the realpath index of resolved filepath 349 (Useful for resolution_mode == RESOLVED only.) 350 Returns: 351 a node or None 352 Raises: 353 NotCoveredError 354 355 This is function is long, too long. But function calls are 356 expensive in Python. TODO(klarlund): refactor. 357 """ 358 # Convenient abbreviations for cache access. 359 dir_map = self.directory_map 360 includepath_map = self.includepath_map 361 resolve = self.build_stat_cache.Resolve 362 # Now a little dynamic type verification. Remember that "A implies B" is 363 # exactly the same as "not A or B", at least in some primitive formal 364 # systems. 365 assert isinstance(nodes_for_incl_config, dict) 366 assert (not self.IsFilepathPair(fp) 367 or resolution_mode == RESOLVED) 368 assert (not fp 369 or (self.IsFilepathPair(fp) 370 or (resolution_mode != RESOLVED 371 and self.IsIncludepathIndex(fp)))) 372 assert resolution_mode in RESOLUTION_MODES 373 assert not resolution_mode == QUOTE or file_dir_idx 374 assert not file_dir_idx or resolution_mode == QUOTE 375 assert not fp_real_idx or resolution_mode == RESOLVED 376 377 if __debug__: 378 Debug(DEBUG_TRACE, 379 "FindNode: fp: %s, mode: %s\n file_dir: %s,\n fp_real: %s" % 380 (self._PrintableFilePath(fp), 381 RESOLUTION_MODES_STR[resolution_mode], 382 not file_dir_idx and " " or dir_map.string[file_dir_idx], 383 not fp_real_idx and " " 384 or self.realpath_map.string[fp_real_idx])) 385 statistics.find_node_counter += 1 386 387 if fp == None: return 388 389 # We must remember the resolution_mode when we key our function call. And 390 # for resolution_mode == QUOTE it is important to also remember the 391 # file_dir_idx, because the filepath is resolved against file_dir. 392 key = (fp, resolution_mode, file_dir_idx) 393 if key in nodes_for_incl_config: 394 # Is the support record valid? 395 if nodes_for_incl_config[key][self.SUPPORT_RECORD].valid: 396 statistics.master_hit_counter += 1 397 return nodes_for_incl_config[key] 398 else: 399 # Invalid support record. The meaning of some computed includes may have 400 # changed. 401 node = nodes_for_incl_config[key] 402 currdir_idx = self.currdir_idx 403 quote_dirs = self.quote_dirs 404 angle_dirs = self.angle_dirs 405 # Retrieve filepath information. That is still OK. Disregard children, 406 # because they will be rebuilt. Reuse support_record. Don't switch 407 # support_record.valid to True before running through all the caching 408 # code below -- we don't want to reuse an earlier result. 409 [fp_real_idx, fp_resolved_pair, _, support_record] = node 410 Debug(DEBUG_TRACE, 411 "Invalid record for translation unit: %s, file: %s", 412 self.translation_unit, self._PrintableFilePath(fp)) 413 414 else: 415 # This is a new file -- for this include configuration at least. 416 support_record = SupportRecord(self.support_master) 417 currdir_idx = self.currdir_idx 418 quote_dirs = self.quote_dirs 419 angle_dirs = self.angle_dirs 420 421 if resolution_mode == QUOTE: 422 (fp_resolved_pair, fp_real_idx) = ( 423 resolve(fp, currdir_idx, file_dir_idx, quote_dirs)) 424 elif resolution_mode == ANGLE: 425 (fp_resolved_pair, fp_real_idx) = ( 426 resolve(fp, currdir_idx, None, angle_dirs)) 427 elif resolution_mode == NEXT: 428 # The node we return is just a dummy whose children are all the 429 # possible resolvants. 430 fp_resolved_pair = None 431 fp_real_idx = None 432 else: 433 assert resolution_mode == RESOLVED 434 assert fp_real_idx # this is the realpath corresponding to fp 435 assert self.IsFilepathPair(fp) 436 fp_resolved_pair = fp # we are given the resolvant 437 438 if fp_resolved_pair: 439 # The resolution succeeded. Before recursing, make sure to 440 # mirror the path. Guard the call of MirrorPath with a cache 441 # check; many files will have been visited before (for other 442 # include directories). 443 (d_, fp_) = fp_resolved_pair 444 if (fp_resolved_pair, currdir_idx) not in self.mirrored: 445 self.mirrored.add((fp_resolved_pair, currdir_idx)) 446 self.mirror_path.DoPath( 447 os.path.join(dir_map.string[currdir_idx], 448 dir_map.string[d_], 449 includepath_map.string[fp_]), 450 currdir_idx, 451 self.client_root_keeper.client_root) 452 453 # We have fp_resolved_pair if and only if we have fp_real_idx 454 assert not fp_resolved_pair or fp_real_idx 455 assert not fp_real_idx or fp_resolved_pair 456 # Now construct the node, even before we know the children; this 457 # early construction/late filling-in of children allows us to stop 458 # a recursion early, when key is in nodes_for_incl_config. A cyclic 459 # structure may arise in this way. 460 children = [] 461 node = (fp_real_idx, fp_resolved_pair, children, 462 support_record) 463 nodes_for_incl_config[key] = node 464 465 if not fp_resolved_pair: 466 if resolution_mode == NEXT: 467 # Create children of this dummy node. Try against all 468 # directories in quote_dirs; that list includes the 469 # angle_dirs. Recurse for each success. 470 for d in quote_dirs: 471 (fp_resolved_pair_, fp_real_idx_) = ( 472 resolve(fp, currdir_idx, None, (d,))) 473 if fp_resolved_pair_ != None: 474 node_ = self.FindNode(nodes_for_incl_config, 475 fp_resolved_pair_, 476 RESOLVED, 477 None, # file_dir_idx 478 fp_real_idx_) 479 children.append(node_) 480 return node 481 else: 482 # For non-NEXT resolution modes 483 return node 484 485 # Now, we've got the resolution: (search directory, include path). 486 assert (fp and fp_real_idx and fp_resolved_pair) 487 (searchdir_idx, includepath_idx) = fp_resolved_pair 488 489 # We need the realpath index of the current file directory. That's because 490 # we are going to ask whether we have really visited this file, despite the 491 # failure above to recognize it using a possibly relative name. Here, 492 # 'really' means 'with respect to realpath'. Please see the class 493 # documentation for why we need to calculate the realpath index of file 494 # directory as part of the investigation of whether we have 'really' 495 # encountered the file before. 496 try: 497 (fp_dirname_idx, fp_dirname_real_idx) = ( 498 self.dirname_cache.cache[(currdir_idx, 499 searchdir_idx, 500 includepath_idx)]) 501 except KeyError: 502 (fp_dirname_idx, fp_dirname_real_idx) = ( 503 self.dirname_cache.Lookup(currdir_idx, 504 searchdir_idx, 505 includepath_idx)) 506 507 if resolution_mode != RESOLVED: 508 # See whether we know about filepath post-resolution. 509 if ((fp_real_idx, fp_dirname_real_idx) in nodes_for_incl_config 510 and support_record.valid): 511 statistics.master_hit_counter += 1 512 # Redo former decision about node: we use the one that is 513 # already there. 514 node = nodes_for_incl_config[(fp_real_idx, fp_dirname_real_idx)] 515 nodes_for_incl_config[key] = node 516 return node 517 # Couldn't find node under real name. We'll remember the node, but have to 518 # continue processing it. 519 nodes_for_incl_config[(fp_real_idx, fp_dirname_real_idx)] = node 520 521 # All chances of hitting the node cache are now exhausted! 522 statistics.master_miss_counter += 1 523 # If we're revisiting because the support record was invalid, then it is 524 # time to set it. 525 support_record.valid = True 526 527 # Try to get the cached result of parsing file. 528 try: 529 (quote_includes, angle_includes, expr_includes, next_includes) = ( 530 self.file_cache[fp_real_idx]) 531 except KeyError: 532 # Parse the file. 533 self.file_cache[fp_real_idx] = self.parse_file.Parse( 534 self.realpath_map.string[fp_real_idx], 535 self.symbol_table) 536 (quote_includes, angle_includes, expr_includes, next_includes) = ( 537 self.file_cache[fp_real_idx]) 538 539 540 # Do the includes of the form #include "foo.h". 541 for quote_filepath in quote_includes: 542 node_ = self.FindNode(nodes_for_incl_config, quote_filepath, QUOTE, 543 fp_dirname_idx) 544 if node_: 545 children.append(node_) 546 support_record.Update(node_[self.SUPPORT_RECORD].support_id) 547 # Do the includes of the form #include <foo.h>. 548 for angle_filepath in angle_includes: 549 node_ = self.FindNode(nodes_for_incl_config, angle_filepath, ANGLE) 550 if node_: 551 children.append(node_) 552 support_record.Update(node_[self.SUPPORT_RECORD].support_id) 553 if __debug__: 554 if expr_includes: # Computed includes are interesting 555 Debug(DEBUG_DATA, "FindNode, expr_includes: file: %s: '%s'", 556 (isinstance(fp, int) and includepath_map.String(fp) 557 or (isinstance(fp, tuple) and 558 (dir_map.string[fp[0]], 559 includepath_map.string[fp[1]]))), 560 expr_includes) 561 562 # Do the includes of the form #include expr, the computed includes. 563 for expr in expr_includes: 564 # Use multi-valued semantics to gather set of possible filepaths that the 565 # C/C++ string expr may evaluate to under preprocessing semantics, given 566 # the current symbol table. The symbols are all those of possible 567 # expansions. 568 (files, symbols) = ( 569 macro_eval.ResolveExpr(includepath_map.Index, 570 resolve, 571 expr, 572 self.currdir_idx, fp_dirname_idx, 573 self.quote_dirs, self.angle_dirs, 574 self.symbol_table)) 575 for (fp_resolved_pair_, fp_real_idx_) in files: 576 node_ = self.FindNode(nodes_for_incl_config, 577 fp_resolved_pair_, 578 RESOLVED, None, fp_real_idx_) 579 if node_: 580 children.append(node_) 581 support_record.Update(node_[self.SUPPORT_RECORD].support_id) 582 # Now the resolution of includes of the file of the present node depends 583 # on symbols. 584 support_record.UpdateSet(symbols) 585 586 # Do includes of the form #include_next "foo.h" or # #include_next <foo.h>. 587 for include_next_filepath in next_includes: 588 node_ = self.FindNode(nodes_for_incl_config, include_next_filepath, NEXT) 589 if node_: 590 children.append(node_) 591 support_record.Update(node_[self.SUPPORT_RECORD].support_id) 592 return node 593 594 def _CalculateIncludeClosureExceptSystem(self, node, include_closure): 595 """Explore the subgraph reachable from node and gather real paths. 596 597 Arguments: 598 node: the node of the translation unit, the initial source file 599 (see class documentation for a description of this tuple). 600 include_closure: a map (see IncludeAnalyzer.RunAlgorithm 601 documentation for a description of this map). 602 Modifies: 603 include_closure. We modify in place to avoid copying this big struct. 604 """ 605 assert not include_closure # should start out empty 606 # We access prefix_cache's vars directly, so we need to ensure it's filled. 607 self.systemdir_prefix_cache.FillCache(self.realpath_map) 608 visited = set([]) 609 starts_with_systemdir = self.systemdir_prefix_cache.cache 610 dir_map_string = self.directory_map.string 611 if not node: return 612 stack = ([node]) # TODO(csilvers): consider using a deque 613 if __debug__: statistics.len_calculated_closure_nonsys = 0 614 while stack: 615 node = stack.pop(-1) 616 id_ = id(node) 617 if id_ in visited: 618 continue 619 visited.add(id_) 620 # We optimized away: 621 # 622 # (fp_real_idx, fp_resolved_pair, children) = node 623 # 624 # so that the common case (that fp_real_idx is known to compiler) 625 # is dispatched away with quickly: 626 if node[0]: # fp_real_idx 627 if __debug__: statistics.len_calculated_closure_nonsys += 1 628 # We ignore "system" includes like /usr/include/stdio.h. 629 # These files are not likely to change, so it's safe to skip them. 630 if not starts_with_systemdir[node[0]]: 631 # Add the resolved filepath to those found for realpath. 632 if node[0] not in include_closure: 633 include_closure[node[0]] = [] 634 searchdir_idx = node[1][0] # the searchdir part of fp_pair 635 if (searchdir_idx and dir_map_string[searchdir_idx] and 636 dir_map_string[searchdir_idx][0] == '/'): 637 include_closure[node[0]].append(node[1]) 638 # Even when a node does not describe a filepath, it may still 639 # have children that do if it is a dummy node. 640 # TODO(csilvers): see if it speeds things up to append node[2], 641 # so stack is a list of lists. 642 stack.extend(node[2]) 643 statistics.len_calculated_closure = len(include_closure) 644