89 seen = {} |
89 seen = {} |
90 # XXX this should be 'parentset.min()' assuming 'parentset' is a smartset |
90 # XXX this should be 'parentset.min()' assuming 'parentset' is a smartset |
91 # (and if it is not, it should.) |
91 # (and if it is not, it should.) |
92 minroot = min(roots) |
92 minroot = min(roots) |
93 roots = set(roots) |
93 roots = set(roots) |
|
94 # prefetch all the things! (because python is slow) |
|
95 reached = reachable.add |
|
96 dovisit = visit.append |
|
97 nextvisit = visit.pop |
94 # open-code the post-order traversal due to the tiny size of |
98 # open-code the post-order traversal due to the tiny size of |
95 # sys.getrecursionlimit() |
99 # sys.getrecursionlimit() |
96 while visit: |
100 while visit: |
97 rev = visit.pop() |
101 rev = nextvisit() |
98 if rev in roots: |
102 if rev in roots: |
99 reachable.add(rev) |
103 reached(rev) |
100 parents = parentrevs(rev) |
104 parents = parentrevs(rev) |
101 seen[rev] = parents |
105 seen[rev] = parents |
102 for parent in parents: |
106 for parent in parents: |
103 if parent >= minroot and parent not in seen: |
107 if parent >= minroot and parent not in seen: |
104 visit.append(parent) |
108 dovisit(parent) |
105 if not reachable: |
109 if not reachable: |
106 return baseset() |
110 return baseset() |
107 for rev in sorted(seen): |
111 for rev in sorted(seen): |
108 for parent in seen[rev]: |
112 for parent in seen[rev]: |
109 if parent in reachable: |
113 if parent in reachable: |
110 reachable.add(rev) |
114 reached(rev) |
111 return baseset(sorted(reachable)) |
115 return baseset(sorted(reachable)) |
112 |
116 |
113 elements = { |
117 elements = { |
114 "(": (21, ("group", 1, ")"), ("func", 1, ")")), |
118 "(": (21, ("group", 1, ")"), ("func", 1, ")")), |
115 "##": (20, None, ("_concat", 20)), |
119 "##": (20, None, ("_concat", 20)), |