Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/tensorflow/python/autograph/pyct/cfg.py: 20%

1# Copyright 2017 The TensorFlow Authors. 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"""Control flow graph (CFG) structure for Python AST representation. 

16 

17The CFG is a digraph with edges representing valid control flow. Each 

18node is associated with exactly one AST node, but not all AST nodes may have 

19a corresponding CFG counterpart. 

20 

21Once built, the CFG itself is immutable, but the values it holds need not be; 

22they are usually annotated with information extracted by walking the graph. 

23 

24Tip: Use `Graph.as_dot` to visualize the CFG using any DOT viewer. 

25 

26Note: the CFG tries to include all code paths that MAY be taken, with a single 

27notable exception: 

28 * function calls do not generate edges corresponding to exceptions they may 

29 raise (i.e. a function call in the middle of a block does not return or jump 

30 to any except or finally block) 

31TODO(mdan): Consider adding the edges above. They'd only add ~O(n) edges. 

32TODO(mdan): Alternatively, consider adding an edge from try to all its excepts. 

33""" 

34 

35# TODO(mdan): The notion of 'statements' below is inaccurate. 

36# They should rather be called 'block statements', because they include 

37# statements that may have a body, e.g. if and while. 

38 

39import collections 

40import enum 

41import weakref 

42 

43import astunparse 

44import gast 

45 

46from tensorflow.python.autograph.pyct import anno 

47 

48 

49class Node(object): 

50 """A node in the CFG. 

51 

52 Although new instances of this class are mutable, the objects that a user 

53 finds in the CFG are typically not. 

54 

55 The nodes represent edges in the CFG graph, and maintain pointers to allow 

56 efficient walking in both forward and reverse order. The following property 

57 holds for all nodes: "child in node.next" iff "node in child.prev". 

58 

59 Attributes: 

60 next: FrozenSet[Node, ...], the nodes that follow this node, in control flow 

61 order 

62 prev: FrozenSet[Node, ...], the nodes that precede this node, in reverse 

63 control flow order 

64 ast_node: ast.AST, the AST node corresponding to this CFG node 

65 """ 

66 

67 def __init__(self, next_, prev, ast_node): 

68 self.next = next_ 

69 self.prev = prev 

70 self.ast_node = ast_node 

71 

72 def freeze(self): 

73 self.next = frozenset(self.next) 

74 # Assumption: All CFG nodes have identical life spans, because the graph 

75 # owns them. Nodes should never be used outside the context of an existing 

76 # graph. 

77 self.prev = weakref.WeakSet(self.prev) 

78 

79 def __repr__(self): 

80 if isinstance(self.ast_node, gast.FunctionDef): 

81 return 'def %s' % self.ast_node.name 

82 elif isinstance(self.ast_node, gast.ClassDef): 

83 return 'class %s' % self.ast_node.name 

84 elif isinstance(self.ast_node, gast.withitem): 

85 # TODO(xjun): remove use of astunparse 

86 return astunparse.unparse(self.ast_node.context_expr).strip() 

87 return astunparse.unparse(self.ast_node).strip() 

88 

89 

90class Graph( 

91 collections.namedtuple( 

92 'Graph', 

93 ['entry', 'exit', 'error', 'index', 'stmt_prev', 'stmt_next'])): 

94 """A Control Flow Graph. 

95 

96 The CFG maintains an index to allow looking up a CFG node by the AST node to 

97 which it is associated. The index can also be enumerated in top-down, depth 

98 first order. 

99 

100 Walking the graph in forward or reverse order is supported by double 

101 parent-child links. 

102 

103 Note: the error nodes are not wired to their corresponding finally guards, 

104 because these are shared, and wiring them would create a reverse path from 

105 normal control flow into the error nodes, which we want to avoid. 

106 

107 The graph also maintains edges corresponding to higher level statements 

108 like for-else loops. A node is considered successor of a statement if there 

109 is an edge from a node that is lexically a child of that statement to a node 

110 that is not. Statement predecessors are analogously defined. 

111 

112 Attributes: 

113 entry: Node, the entry node 

114 exit: FrozenSet[Node, ...], the exit nodes 

115 error: FrozenSet[Node, ...], nodes that exit due to an explicitly raised 

116 error (errors propagated from function calls are not accounted) 

117 index: Dict[ast.Node, Node], mapping AST nodes to the respective CFG node 

118 stmt_prev: Dict[ast.Node, FrozenSet[Node, ...]], mapping statement AST nodes 

119 to their predecessor CFG nodes 

120 stmt_next: Dict[ast.Node, FrozenSet[Node, ...]], mapping statement AST nodes 

121 to their successor CFG nodes 

122 """ 

123 

124 def __repr__(self): 

125 return self.as_dot() 

126 

127 def as_dot(self): 

128 """Print CFG in DOT format.""" 

129 result = 'digraph CFG {\n' 

130 for node in self.index.values(): 

131 result += ' %s [label="%s"];\n' % (id(node), node) 

132 for node in self.index.values(): 

133 for next_ in node.next: 

134 result += ' %s -> %s;\n' % (id(node), id(next_)) 

135 result += '}' 

136 return result 

137 

138 

139class _WalkMode(enum.Enum): 

140 FORWARD = 1 

141 REVERSE = 2 

142 

143 

144# TODO(mdan): Rename to DataFlowAnalyzer. 

145# TODO(mdan): Consider specializations that use gen/kill/transfer abstractions. 

146class GraphVisitor(object): 

147 """Base class for a CFG visitors. 

148 

149 This implementation is not thread safe. 

150 

151 The visitor has some facilities to simplify dataflow analyses. In particular, 

152 it allows revisiting the nodes at the decision of the subclass. This can be 

153 used to visit the graph until the state reaches a fixed point. 

154 

155 For more details on dataflow analysis, see 

156 https://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec02-Dataflow.pdf 

157 

158 Note: the literature generally suggests visiting successor nodes only when the 

159 state of the current node changed, regardless of whether that successor has 

160 ever been visited. This implementation visits every successor at least once. 

161 

162 Attributes: 

163 graph: Graph 

164 in_: Dict[Node, Any], stores node-keyed state during a visit 

165 out: Dict[Node, Any], stores node-keyed state during a visit 

166 """ 

167 

168 def __init__(self, graph): 

169 self.graph = graph 

170 self.reset() 

171 

172 def init_state(self, node): 

173 """State initialization function. 

174 

175 Optional to overload. 

176 

177 An in/out state slot will be created for each node in the graph. Subclasses 

178 must overload this to control what that is initialized to. 

179 

180 Args: 

181 node: Node 

182 """ 

183 raise NotImplementedError('Subclasses must implement this.') 

184 

185 # TODO(mdan): Rename to flow? 

186 def visit_node(self, node): 

187 """Visitor function. 

188 

189 Args: 

190 node: Node 

191 

192 Returns: 

193 bool, whether the node should be revisited; subclasses can visit every 

194 reachable node exactly once by always returning False 

195 """ 

196 raise NotImplementedError('Subclasses must implement this.') 

197 

198 def reset(self): 

199 self.in_ = { 

200 node: self.init_state(node) for node in self.graph.index.values() 

201 } 

202 self.out = { 

203 node: self.init_state(node) for node in self.graph.index.values() 

204 } 

205 

206 def can_ignore(self, node): 

207 """Returns True if the node can safely be assumed not to touch variables.""" 

208 ast_node = node.ast_node 

209 if anno.hasanno(ast_node, anno.Basic.SKIP_PROCESSING): 

210 return True 

211 return isinstance(ast_node, 

212 (gast.Break, gast.Continue, gast.Raise, gast.Pass)) 

213 

214 def _visit_internal(self, mode): 

215 """Visits the CFG, breadth-first.""" 

216 assert mode in (_WalkMode.FORWARD, _WalkMode.REVERSE) 

217 if mode == _WalkMode.FORWARD: 

218 open_ = [self.graph.entry] 

219 elif mode == _WalkMode.REVERSE: 

220 open_ = list(self.graph.exit) 

221 closed = set() 

222 

223 while open_: 

224 node = open_.pop(0) 

225 closed.add(node) 

226 

227 should_revisit = self.visit_node(node) 

228 

229 if mode == _WalkMode.FORWARD: 

230 children = node.next 

231 elif mode == _WalkMode.REVERSE: 

232 children = node.prev 

233 

234 for next_ in children: 

235 if should_revisit or next_ not in closed: 

236 open_.append(next_) 

237 

238 def visit_forward(self): 

239 self._visit_internal(_WalkMode.FORWARD) 

240 

241 def visit_reverse(self): 

242 self._visit_internal(_WalkMode.REVERSE) 

243 

244 

245class GraphBuilder(object): 

246 """Builder that constructs a CFG from a given AST. 

247 

248 This GraphBuilder facilitates constructing the DAG that forms the CFG when 

249 nodes 

250 are supplied in lexical order (i.e., top-down, depth first). Under these 

251 conditions, it supports building patterns found in typical structured 

252 programs. 

253 

254 This builder ignores the flow generated by exceptions, which are assumed to 

255 always be catastrophic and present purely for diagnostic purposes (e.g. to 

256 print debug information). Statements like raise and try/catch sections are 

257 allowed and will generate control flow edges, but ordinary statements are 

258 assumed not to raise exceptions. 

259 

260 Finally sections are also correctly interleaved between break/continue/return 

261 nodes and their subsequent statements. 

262 

263 Important concepts: 

264 * nodes - nodes refer to CFG nodes; AST nodes are qualified explicitly 

265 * leaf set - since the graph is constructed gradually, a leaf set maintains 

266 the CFG nodes that will precede the node that the builder expects to 

267 receive next; when an ordinary node is added, it is connected to the 

268 existing leaves and it in turn becomes the new leaf 

269 * jump nodes - nodes that should generate edges other than what 

270 ordinary nodes would; these correspond to break, continue and return 

271 statements 

272 * sections - logical delimiters for subgraphs that require special 

273 edges; there are various types of nodes, each admitting various 

274 types of jump nodes; sections are identified by their corresponding AST 

275 node 

276 """ 

277 

278 # TODO(mdan): Perhaps detail this in a markdown doc. 

279 # TODO(mdan): Add exception support. 

280 

281 def __init__(self, parent_ast_node): 

282 self.reset() 

283 self.parent = parent_ast_node 

284 

285 def reset(self): 

286 """Resets the state of this factory.""" 

287 self.head = None 

288 self.errors = set() 

289 self.node_index = {} 

290 

291 # TODO(mdan): Too many primitives. Use classes. 

292 self.leaves = set() 

293 

294 # Note: This mechanism requires that nodes are added in lexical order (top 

295 # to bottom, depth first). 

296 self.active_stmts = set() 

297 self.owners = {} # type: Set[any] 

298 self.forward_edges = set() # type: Tuple[Node, Node] # (from, to) 

299 

300 self.finally_sections = {} 

301 # Dict values represent (entry, exits) 

302 self.finally_section_subgraphs = { 

303 } # type: Dict[ast.AST, Tuple[Node, Set[Node]]] 

304 # Whether the guard section can be reached from the statement that precedes 

305 # it. 

306 self.finally_section_has_direct_flow = {} 

307 # Finally sections that await their first node. 

308 self.pending_finally_sections = set() 

309 

310 # Exit jumps keyed by the section they affect. 

311 self.exits = {} 

312 

313 # The entry of loop sections, keyed by the section. 

314 self.section_entry = {} 

315 # Continue jumps keyed by the section they affect. 

316 self.continues = {} 

317 

318 # Raise jumps keyed by the except section guarding them. 

319 self.raises = {} 

320 

321 # The entry of conditional sections, keyed by the section. 

322 self.cond_entry = {} 

323 # Lists of leaf nodes corresponding to each branch in the section. 

324 self.cond_leaves = {} 

325 

326 def _connect_nodes(self, first, second): 

327 """Connects nodes to signify that control flows from first to second. 

328 

329 Args: 

330 first: Union[Set[Node, ...], Node] 

331 second: Node 

332 """ 

333 if isinstance(first, Node): 

334 first.next.add(second) 

335 second.prev.add(first) 

336 self.forward_edges.add((first, second)) 

337 else: 

338 for node in first: 

339 self._connect_nodes(node, second) 

340 

341 def _add_new_node(self, ast_node): 

342 """Grows the graph by adding a CFG node following the current leaves.""" 

343 if ast_node in self.node_index: 

344 raise ValueError('%s added twice' % ast_node) 

345 # Assumption: All CFG nodes have identical life spans, because the graph 

346 # owns them. Nodes should never be used outside the context of an existing 

347 # graph. 

348 node = Node(next_=set(), prev=weakref.WeakSet(), ast_node=ast_node) 

349 self.node_index[ast_node] = node 

350 self.owners[node] = frozenset(self.active_stmts) 

351 

352 if self.head is None: 

353 self.head = node 

354 

355 for leaf in self.leaves: 

356 self._connect_nodes(leaf, node) 

357 

358 # If any finally section awaits its first node, populate it. 

359 for section_id in self.pending_finally_sections: 

360 self.finally_section_subgraphs[section_id][0] = node 

361 self.pending_finally_sections = set() 

362 

363 return node 

364 

365 def begin_statement(self, stmt): 

366 """Marks the beginning of a statement. 

367 

368 Args: 

369 stmt: Hashable, a key by which the statement can be identified in the 

370 CFG's stmt_prev and stmt_next attributes 

371 """ 

372 self.active_stmts.add(stmt) 

373 

374 def end_statement(self, stmt): 

375 """Marks the end of a statement. 

376 

377 Args: 

378 stmt: Hashable, a key by which the statement can be identified in the 

379 CFG's stmt_prev and stmt_next attributes; must match a key previously 

380 passed to begin_statement. 

381 """ 

382 self.active_stmts.remove(stmt) 

383 

384 def add_ordinary_node(self, ast_node): 

385 """Grows the graph by adding an ordinary CFG node. 

386 

387 Ordinary nodes are followed by the next node, in lexical order, that is, 

388 they become the new leaf set. 

389 

390 Args: 

391 ast_node: ast.AST 

392 

393 Returns: 

394 Node 

395 """ 

396 node = self._add_new_node(ast_node) 

397 self.leaves = set((node,)) 

398 return node 

399 

400 def _add_jump_node(self, ast_node, guards): 

401 """Grows the graph by adding a jump node. 

402 

403 Jump nodes are added to the current leaf set, and the leaf set becomes 

404 empty. If the jump node is the last in a cond section, then it may be added 

405 back to the leaf set by a separate mechanism. 

406 

407 Args: 

408 ast_node: ast.AST 

409 guards: Tuple[ast.AST, ...], the finally sections active for this node 

410 

411 Returns: 

412 Node 

413 """ 

414 node = self._add_new_node(ast_node) 

415 self.leaves = set() 

416 # The guards themselves may not yet be complete, and will be wired later. 

417 self.finally_sections[node] = guards 

418 return node 

419 

420 def _connect_jump_to_finally_sections(self, node): 

421 """Connects a jump node to the finally sections protecting it.""" 

422 cursor = set((node,)) 

423 if node not in self.finally_sections: 

424 return cursor 

425 for guard_section_id in self.finally_sections[node]: 

426 guard_begin, guard_ends = self.finally_section_subgraphs[guard_section_id] 

427 self._connect_nodes(cursor, guard_begin) 

428 cursor = guard_ends 

429 del self.finally_sections[node] 

430 # TODO(mdan): Should garbage-collect finally_section_subgraphs. 

431 return cursor 

432 

433 def add_exit_node(self, ast_node, section_id, guards): 

434 """Grows the graph by adding an exit node. 

435 

436 This node becomes an exit for the current section. 

437 

438 Args: 

439 ast_node: ast.AST 

440 section_id: Hashable, the node for which ast_node should be considered to 

441 be an exit node 

442 guards: Tuple[ast.AST, ...], the finally sections that guard ast_node 

443 

444 Returns: 

445 Node 

446 """ 

447 node = self._add_jump_node(ast_node, guards) 

448 self.exits[section_id].add(node) 

449 return node 

450 

451 def add_continue_node(self, ast_node, section_id, guards): 

452 """Grows the graph by adding a reentry node. 

453 

454 This node causes control flow to go back to the loop section's entry. 

455 

456 Args: 

457 ast_node: ast.AST 

458 section_id: Hashable, the node for which ast_node should be considered to 

459 be an exit node 

460 guards: Tuple[ast.AST, ...], the finally sections that guard ast_node 

461 """ 

462 node = self._add_jump_node(ast_node, guards) 

463 self.continues[section_id].add(node) 

464 

465 def connect_raise_node(self, node, except_guards): 

466 """Adds extra connection between a raise node and containing except guards. 

467 

468 The node is a graph node, not an ast node. 

469 

470 Args: 

471 node: Node 

472 except_guards: Tuple[ast.AST, ...], the except sections that guard node 

473 """ 

474 for guard in except_guards: 

475 if guard in self.raises: 

476 self.raises[guard].append(node) 

477 else: 

478 self.raises[guard] = [node] 

479 

480 def enter_section(self, section_id): 

481 """Enters a regular section. 

482 

483 Regular sections admit exit jumps, which end the section. 

484 

485 Args: 

486 section_id: Hashable, the same node that will be used in calls to the 

487 ast_node arg passed to add_exit_node 

488 """ 

489 assert section_id not in self.exits 

490 self.exits[section_id] = set() 

491 

492 def exit_section(self, section_id): 

493 """Exits a regular section.""" 

494 

495 # Exits are jump nodes, which may be protected. 

496 for exit_ in self.exits[section_id]: 

497 self.leaves |= self._connect_jump_to_finally_sections(exit_) 

498 

499 del self.exits[section_id] 

500 

501 def enter_loop_section(self, section_id, entry_node): 

502 """Enters a loop section. 

503 

504 Loop sections define an entry node. The end of the section always flows back 

505 to the entry node. These admit continue jump nodes which also flow to the 

506 entry node. 

507 

508 Args: 

509 section_id: Hashable, the same node that will be used in calls to the 

510 ast_node arg passed to add_continue_node 

511 entry_node: ast.AST, the entry node into the loop (e.g. the test node for 

512 while loops) 

513 """ 

514 assert section_id not in self.section_entry 

515 assert section_id not in self.continues 

516 self.continues[section_id] = set() 

517 node = self.add_ordinary_node(entry_node) 

518 self.section_entry[section_id] = node 

519 

520 def exit_loop_section(self, section_id): 

521 """Exits a loop section.""" 

522 self._connect_nodes(self.leaves, self.section_entry[section_id]) 

523 

524 # continues are jump nodes, which may be protected. 

525 for reentry in self.continues[section_id]: 

526 guard_ends = self._connect_jump_to_finally_sections(reentry) 

527 self._connect_nodes(guard_ends, self.section_entry[section_id]) 

528 

529 # Loop nodes always loop back. 

530 self.leaves = set((self.section_entry[section_id],)) 

531 

532 del self.continues[section_id] 

533 del self.section_entry[section_id] 

534 

535 def enter_cond_section(self, section_id): 

536 """Enters a conditional section. 

537 

538 Conditional sections define an entry node, and one or more branches. 

539 

540 Args: 

541 section_id: Hashable, the same node that will be used in calls to the 

542 section_id arg passed to new_cond_branch 

543 """ 

544 

545 assert section_id not in self.cond_entry 

546 assert section_id not in self.cond_leaves 

547 self.cond_leaves[section_id] = [] 

548 

549 def new_cond_branch(self, section_id): 

550 """Begins a new branch in a cond section.""" 

551 assert section_id in self.cond_leaves 

552 

553 if section_id in self.cond_entry: 

554 # Subsequent splits move back to the split point, and memorize the 

555 # current leaves. 

556 self.cond_leaves[section_id].append(self.leaves) 

557 self.leaves = self.cond_entry[section_id] 

558 else: 

559 # If this is the first time we split a section, just remember the split 

560 # point. 

561 self.cond_entry[section_id] = self.leaves 

562 

563 def exit_cond_section(self, section_id): 

564 """Exits a conditional section.""" 

565 for split in self.cond_leaves[section_id]: 

566 self.leaves |= split 

567 del self.cond_entry[section_id] 

568 del self.cond_leaves[section_id] 

569 

570 def enter_except_section(self, section_id): 

571 """Enters an except section.""" 

572 if section_id in self.raises: 

573 self.leaves.update(self.raises[section_id]) 

574 

575 def enter_finally_section(self, section_id): 

576 """Enters a finally section.""" 

577 # TODO(mdan): This, not the caller, should track the active sections. 

578 self.finally_section_subgraphs[section_id] = [None, None] 

579 if self.leaves: 

580 self.finally_section_has_direct_flow[section_id] = True 

581 else: 

582 self.finally_section_has_direct_flow[section_id] = False 

583 self.pending_finally_sections.add(section_id) 

584 

585 def exit_finally_section(self, section_id): 

586 """Exits a finally section.""" 

587 assert section_id not in self.pending_finally_sections, 'Empty finally?' 

588 self.finally_section_subgraphs[section_id][1] = self.leaves 

589 # If the guard can only be reached by a jump, then it will not flow 

590 # into the statement that follows it. 

591 if not self.finally_section_has_direct_flow[section_id]: 

592 self.leaves = set() 

593 del self.finally_section_has_direct_flow[section_id] 

594 

595 def build(self): 

596 """Returns the CFG accumulated so far and resets the builder. 

597 

598 Returns: 

599 Graph 

600 """ 

601 # Freeze the nodes. 

602 for node in self.node_index.values(): 

603 node.freeze() 

604 

605 # Build the statement edges. 

606 stmt_next = {} 

607 stmt_prev = {} 

608 

609 for node in self.node_index.values(): 

610 for stmt in self.owners[node]: 

611 if stmt not in stmt_prev: 

612 stmt_prev[stmt] = set() 

613 if stmt not in stmt_next: 

614 stmt_next[stmt] = set() 

615 

616 for first, second in self.forward_edges: 

617 stmts_exited = self.owners[first] - self.owners[second] 

618 for stmt in stmts_exited: 

619 stmt_next[stmt].add(second) 

620 stmts_entered = self.owners[second] - self.owners[first] 

621 for stmt in stmts_entered: 

622 stmt_prev[stmt].add(first) 

623 for stmt in stmt_next: 

624 stmt_next[stmt] = frozenset(stmt_next[stmt]) 

625 for stmt in stmt_prev: 

626 stmt_prev[stmt] = frozenset(stmt_prev[stmt]) 

627 

628 # Construct the final graph object. 

629 result = Graph( 

630 entry=self.head, 

631 exit=self.leaves, 

632 error=self.errors, 

633 index=self.node_index, 

634 stmt_prev=stmt_prev, 

635 stmt_next=stmt_next) 

636 

637 # Reset the state. 

638 self.reset() 

639 

640 return result 

641 

642 

643class AstToCfg(gast.NodeVisitor): 

644 """Converts an AST to CFGs. 

645 

646 A separate CFG will be constructed for each function. 

647 """ 

648 

649 def __init__(self): 

650 super(AstToCfg, self).__init__() 

651 

652 self.builder_stack = [] 

653 self.builder = None 

654 self.cfgs = {} 

655 

656 self.lexical_scopes = [] 

657 

658 def _enter_lexical_scope(self, node): 

659 self.lexical_scopes.append(node) 

660 

661 def _exit_lexical_scope(self, node): 

662 leaving_node = self.lexical_scopes.pop() 

663 assert node == leaving_node 

664 

665 def _get_enclosing_finally_scopes(self, stop_at): 

666 included = [] 

667 for node in reversed(self.lexical_scopes): 

668 if isinstance(node, gast.Try) and node.finalbody: 

669 included.append(node) 

670 if isinstance(node, stop_at): 

671 return node, included 

672 return None, included 

673 

674 def _get_enclosing_except_scopes(self, stop_at): 

675 included = [] 

676 for node in reversed(self.lexical_scopes): 

677 if isinstance(node, gast.Try) and node.handlers: 

678 included.extend(node.handlers) 

679 if isinstance(node, stop_at): 

680 break 

681 return included 

682 

683 def _process_basic_statement(self, node): 

684 self.generic_visit(node) 

685 self.builder.add_ordinary_node(node) 

686 

687 def _process_exit_statement(self, 

688 node, 

689 exits_nodes_of_type, 

690 may_exit_via_except=False): 

691 self.generic_visit(node) 

692 # Note: this is safe because we process functions separately. 

693 try_node, guards = self._get_enclosing_finally_scopes(exits_nodes_of_type) 

694 assert try_node is not None, '{} that is not enclosed by any of {}'.format( 

695 node, exits_nodes_of_type) 

696 

697 node = self.builder.add_exit_node(node, try_node, guards) 

698 

699 if may_exit_via_except: 

700 except_guards = self._get_enclosing_except_scopes(exits_nodes_of_type) 

701 self.builder.connect_raise_node(node, except_guards) 

702 

703 def _process_continue_statement(self, node, *loops_to_nodes_of_type): 

704 # Note: this is safe because we process functions separately. 

705 try_node, guards = self._get_enclosing_finally_scopes( 

706 tuple(loops_to_nodes_of_type)) 

707 if try_node is None: 

708 raise ValueError('%s that is not enclosed by any of %s' % 

709 (node, loops_to_nodes_of_type)) 

710 self.builder.add_continue_node(node, try_node, guards) 

711 

712 def visit_ClassDef(self, node): 

713 # We also keep the ClassDef node in the CFG, since it technically is a 

714 # statement. 

715 # For example, this is legal and allows executing user code: 

716 # 

717 # class Foo(bar()): 

718 # pass 

719 # 

720 # It also has a scope: 

721 # 

722 # class Bar(object): 

723 # a = 1 

724 if self.builder is None: 

725 self.generic_visit(node) 

726 return 

727 

728 self.builder.add_ordinary_node(node) 

729 

730 self.builder_stack.append(self.builder) 

731 self.builder = GraphBuilder(node) 

732 self._enter_lexical_scope(node) 

733 

734 self._process_basic_statement(node) 

735 

736 self._exit_lexical_scope(node) 

737 # TODO(mdan): Track the CFG local to the class definition as well? 

738 self.builder = self.builder_stack.pop() 

739 

740 def _process_function_def(self, node, is_lambda): 

741 # The function body is stored in a separate graph, because function 

742 # definitions have effects very different from function calls. 

743 if self.builder is not None: 

744 self.builder.add_ordinary_node(node) 

745 

746 self.builder_stack.append(self.builder) 

747 self.builder = GraphBuilder(node) 

748 

749 self._enter_lexical_scope(node) 

750 self.builder.enter_section(node) 

751 

752 self._process_basic_statement(node.args) 

753 if is_lambda: 

754 self._process_exit_statement(node.body, (gast.Lambda,)) 

755 else: 

756 for stmt in node.body: 

757 self.visit(stmt) 

758 

759 self.builder.exit_section(node) 

760 self._exit_lexical_scope(node) 

761 

762 self.cfgs[node] = self.builder.build() 

763 self.builder = self.builder_stack.pop() 

764 

765 def visit_FunctionDef(self, node): 

766 self._process_function_def(node, is_lambda=False) 

767 

768 def visit_Lambda(self, node): 

769 self._process_function_def(node, is_lambda=True) 

770 

771 def visit_Return(self, node): 

772 self._process_exit_statement(node, (gast.FunctionDef,)) 

773 

774 def visit_Import(self, node): 

775 self._process_basic_statement(node) 

776 

777 def visit_ImportFrom(self, node): 

778 self._process_basic_statement(node) 

779 

780 def visit_Expr(self, node): 

781 self._process_basic_statement(node) 

782 

783 def visit_Assign(self, node): 

784 self._process_basic_statement(node) 

785 

786 def visit_AnnAssign(self, node): 

787 self._process_basic_statement(node) 

788 

789 def visit_AugAssign(self, node): 

790 self._process_basic_statement(node) 

791 

792 def visit_Pass(self, node): 

793 self._process_basic_statement(node) 

794 

795 def visit_Global(self, node): 

796 self._process_basic_statement(node) 

797 

798 def visit_Nonlocal(self, node): 

799 self._process_basic_statement(node) 

800 

801 def visit_Print(self, node): 

802 self._process_basic_statement(node) 

803 

804 def visit_Raise(self, node): 

805 self._process_exit_statement( 

806 node, (gast.FunctionDef,), may_exit_via_except=True) 

807 self.builder.errors.add(node) 

808 

809 def visit_Assert(self, node): 

810 # Ignoring the effect of exceptions. 

811 self._process_basic_statement(node) 

812 

813 def visit_Delete(self, node): 

814 self._process_basic_statement(node) 

815 

816 def visit_If(self, node): 

817 # No need to track ifs as lexical scopes, for now. 

818 # Lexical scopes are generally tracked in order to be able to resolve the 

819 # targets of jump statements like break/continue/etc. Since there is no 

820 # statement that can interrupt a conditional, we don't need to track their 

821 # lexical scope. That may change in the future. 

822 self.builder.begin_statement(node) 

823 

824 self.builder.enter_cond_section(node) 

825 self._process_basic_statement(node.test) 

826 

827 self.builder.new_cond_branch(node) 

828 for stmt in node.body: 

829 self.visit(stmt) 

830 

831 self.builder.new_cond_branch(node) 

832 for stmt in node.orelse: 

833 self.visit(stmt) 

834 

835 self.builder.exit_cond_section(node) 

836 self.builder.end_statement(node) 

837 

838 def visit_While(self, node): 

839 self.builder.begin_statement(node) 

840 self._enter_lexical_scope(node) 

841 

842 self.builder.enter_section(node) 

843 

844 self.generic_visit(node.test) 

845 self.builder.enter_loop_section(node, node.test) 

846 for stmt in node.body: 

847 self.visit(stmt) 

848 self.builder.exit_loop_section(node) 

849 

850 # Note: although the orelse is technically part of the loop node, 

851 # the statements inside it don't affect the loop itself. For example, a 

852 # break in the loop's orelse will not affect the loop itself. 

853 self._exit_lexical_scope(node) 

854 

855 for stmt in node.orelse: 

856 self.visit(stmt) 

857 

858 self.builder.exit_section(node) 

859 self.builder.end_statement(node) 

860 

861 def visit_For(self, node): 

862 self.builder.begin_statement(node) 

863 self._enter_lexical_scope(node) 

864 

865 self.builder.enter_section(node) 

866 

867 # Note: Strictly speaking, this should be node.target + node.iter. 

868 # However, the activity analysis accounts for this inconsistency, 

869 # so dataflow analysis produces the correct values. 

870 self.generic_visit(node.iter) 

871 self.builder.enter_loop_section(node, node.iter) 

872 # Also include the "extra loop test" annotation, to capture things like the 

873 # control variable for return and break in for loops. 

874 if anno.hasanno(node, anno.Basic.EXTRA_LOOP_TEST): 

875 self._process_basic_statement( 

876 anno.getanno(node, anno.Basic.EXTRA_LOOP_TEST)) 

877 for stmt in node.body: 

878 self.visit(stmt) 

879 self.builder.exit_loop_section(node) 

880 

881 # Note: although the orelse is technically part of the loop node, 

882 # they don't count as loop bodies. For example, a break in the loop's 

883 # orelse will affect the parent loop, not the current one. 

884 self._exit_lexical_scope(node) 

885 

886 for stmt in node.orelse: 

887 self.visit(stmt) 

888 

889 self.builder.exit_section(node) 

890 self.builder.end_statement(node) 

891 

892 def visit_Break(self, node): 

893 self._process_exit_statement(node, ( 

894 gast.While, 

895 gast.For, 

896 )) 

897 

898 def visit_Continue(self, node): 

899 self._process_continue_statement(node, ( 

900 gast.While, 

901 gast.For, 

902 )) 

903 

904 def visit_ExceptHandler(self, node): 

905 self.builder.begin_statement(node) 

906 self.builder.enter_except_section(node) 

907 

908 if node.type is not None: 

909 self.visit(node.type) 

910 if node.name is not None: 

911 self.visit(node.name) 

912 

913 for stmt in node.body: