1use rustc_hash::FxHashMap;
14use rustc_hash::FxHashSet;
15use tracing::{Level, debug, span};
16use tsz_binder::{FlowNode, FlowNodeArena, FlowNodeId, flow_flags};
17use tsz_parser::parser::node::NodeArena;
18use tsz_parser::parser::{NodeIndex, NodeList, syntax_kind_ext};
19use tsz_scanner::SyntaxKind;
20
21#[derive(Clone, Debug)]
27pub struct FlowGraph {
28 pub nodes: FlowNodeArena,
30 pub node_flow: FxHashMap<u32, FlowNodeId>,
32 pub unreachable_flow: FlowNodeId,
34 pub unreachable_nodes: FxHashSet<u32>,
36}
37
38impl FlowGraph {
39 pub fn new() -> Self {
41 let mut nodes = FlowNodeArena::new();
42 let unreachable_flow = nodes.alloc(flow_flags::UNREACHABLE);
43
44 Self {
45 nodes,
46 node_flow: FxHashMap::default(),
47 unreachable_flow,
48 unreachable_nodes: FxHashSet::default(),
49 }
50 }
51
52 pub fn get_flow_at_node(&self, node: NodeIndex) -> Option<FlowNodeId> {
54 self.node_flow.get(&node.0).copied()
55 }
56
57 pub fn get_node(&self, id: FlowNodeId) -> Option<&FlowNode> {
59 self.nodes.get(id)
60 }
61
62 pub fn has_flow_at_node(&self, node: NodeIndex) -> bool {
64 self.node_flow.contains_key(&node.0)
65 }
66
67 pub fn is_unreachable(&self, node: NodeIndex) -> bool {
69 self.unreachable_nodes.contains(&node.0)
70 }
71
72 pub fn mark_unreachable(&mut self, node: NodeIndex) {
74 self.unreachable_nodes.insert(node.0);
75 }
76}
77
78impl Default for FlowGraph {
79 fn default() -> Self {
80 Self::new()
81 }
82}
83
84pub struct FlowGraphBuilder<'a> {
89 arena: &'a NodeArena,
91 graph: FlowGraph,
93 current_flow: FlowNodeId,
95 flow_stack: Vec<FlowContext>,
97 async_depth: u32,
99 generator_depth: u32,
101}
102
103#[derive(Clone, Copy)]
105struct FlowContext {
106 break_label: FlowNodeId,
108 continue_label: Option<FlowNodeId>,
110 context_type: FlowContextType,
112 finally_block: NodeIndex,
114 label: NodeIndex,
116}
117
118#[derive(Clone, Copy, PartialEq)]
119enum FlowContextType {
120 Loop,
121 Switch,
122 Try,
123}
124
125impl<'a> FlowGraphBuilder<'a> {
126 pub fn new(arena: &'a NodeArena) -> Self {
128 let mut graph = FlowGraph::new();
129 let start_flow = graph.nodes.alloc(flow_flags::START);
130
131 FlowGraphBuilder {
132 arena,
133 graph,
134 current_flow: start_flow,
135 flow_stack: Vec::new(),
136 async_depth: 0,
137 generator_depth: 0,
138 }
139 }
140
141 pub fn build_source_file(&mut self, statements: &NodeList) -> &FlowGraph {
143 let _span = span!(
144 Level::DEBUG,
145 "build_flow_graph",
146 num_statements = statements.nodes.len()
147 )
148 .entered();
149 debug!(
150 "Building flow graph for source file with {} statements",
151 statements.nodes.len()
152 );
153
154 for &stmt_idx in &statements.nodes {
155 if stmt_idx.is_some() {
156 self.build_statement(stmt_idx);
157 }
158 }
159 &self.graph
160 }
161
162 pub fn build_flow_graph(&mut self, statements: &NodeList) -> &FlowGraph {
172 self.build_source_file(statements)
173 }
174
175 pub fn build_function_body(
186 &mut self,
187 body: &tsz_parser::parser::node::BlockData,
188 ) -> &FlowGraph {
189 let _span = span!(
190 Level::DEBUG,
191 "build_function_body",
192 num_statements = body.statements.nodes.len()
193 )
194 .entered();
195 debug!(
196 "Building flow graph for function body with {} statements",
197 body.statements.nodes.len()
198 );
199
200 self.graph = FlowGraph::new();
202 self.current_flow = self.graph.nodes.alloc(flow_flags::START);
203 self.flow_stack.clear();
204 self.async_depth = 0;
205 self.generator_depth = 0;
206
207 self.build_block(body);
209 &self.graph
210 }
211
212 fn build_statement(&mut self, stmt_idx: NodeIndex) {
214 let Some(node) = self.arena.get(stmt_idx) else {
215 return;
216 };
217
218 match node.kind {
219 syntax_kind_ext::BLOCK => {
221 if let Some(block) = self.arena.get_block(node) {
222 self.build_block(block);
223 }
224 }
225
226 syntax_kind_ext::IF_STATEMENT => {
228 if let Some(if_stmt) = self.arena.get_if_statement(node) {
229 self.build_if_statement(if_stmt);
230 }
231 }
232
233 syntax_kind_ext::WHILE_STATEMENT => {
235 if let Some(loop_data) = self.arena.get_loop(node) {
236 self.build_while_statement(loop_data);
237 }
238 }
239
240 syntax_kind_ext::DO_STATEMENT => {
242 if let Some(loop_data) = self.arena.get_loop(node) {
243 self.build_do_while_statement(loop_data);
244 }
245 }
246
247 syntax_kind_ext::FOR_STATEMENT => {
249 if let Some(loop_data) = self.arena.get_loop(node) {
250 self.build_for_statement(loop_data);
251 }
252 }
253
254 syntax_kind_ext::FOR_IN_STATEMENT => {
256 if let Some(for_in_of) = self.arena.get_for_in_of(node) {
257 self.build_for_in_statement(for_in_of);
258 }
259 }
260
261 syntax_kind_ext::FOR_OF_STATEMENT => {
263 if let Some(for_in_of) = self.arena.get_for_in_of(node) {
264 self.build_for_of_statement(for_in_of);
265 }
266 }
267
268 syntax_kind_ext::SWITCH_STATEMENT => {
270 if let Some(switch_data) = self.arena.get_switch(node) {
271 self.build_switch_statement(switch_data);
272 }
273 }
274
275 syntax_kind_ext::TRY_STATEMENT => {
277 if let Some(try_data) = self.arena.get_try(node) {
278 self.build_try_statement(try_data);
279 }
280 }
281
282 syntax_kind_ext::LABELED_STATEMENT => {
284 if let Some(labeled_data) = self.arena.get_labeled_statement(node) {
285 self.build_labeled_statement(labeled_data);
286 }
287 }
288
289 syntax_kind_ext::VARIABLE_DECLARATION => {
291 if let Some(var_decl) = self.arena.get_variable_declaration(node) {
292 self.build_variable_declaration(var_decl, stmt_idx);
293 }
294 }
295
296 syntax_kind_ext::VARIABLE_STATEMENT | syntax_kind_ext::VARIABLE_DECLARATION_LIST => {
298 if let Some(var_data) = self.arena.get_variable(node) {
299 for &decl_idx in &var_data.declarations.nodes {
300 if decl_idx.is_some() {
301 self.build_statement(decl_idx);
302 }
303 }
304 }
305 self.record_node_flow(stmt_idx);
306 }
307
308 syntax_kind_ext::FUNCTION_DECLARATION
310 | syntax_kind_ext::FUNCTION_EXPRESSION
311 | syntax_kind_ext::ARROW_FUNCTION => {
312 if let Some(func) = self.arena.get_function(node) {
313 let was_async = func.is_async;
315 let was_generator = func.asterisk_token;
316
317 if was_async {
318 self.async_depth += 1;
319 }
320 if was_generator {
321 self.generator_depth += 1;
322 }
323
324 self.record_node_flow(stmt_idx);
325 if was_async {
329 self.async_depth -= 1;
330 }
331 if was_generator {
332 self.generator_depth -= 1;
333 }
334 }
335 }
336
337 syntax_kind_ext::EXPRESSION_STATEMENT => {
339 if let Some(expr_stmt) = self.arena.get_expression_statement(node) {
341 self.handle_expression_for_suspension_points(expr_stmt.expression);
342 self.handle_expression_for_assignments(expr_stmt.expression);
343 }
344 self.record_node_flow(stmt_idx);
345 }
346
347 syntax_kind_ext::AWAIT_EXPRESSION => {
349 self.handle_await_expression(stmt_idx);
350 self.record_node_flow(stmt_idx);
351 }
352
353 syntax_kind_ext::YIELD_EXPRESSION => {
355 self.handle_yield_expression(stmt_idx);
356 self.record_node_flow(stmt_idx);
357 }
358
359 syntax_kind_ext::CLASS_DECLARATION | syntax_kind_ext::CLASS_EXPRESSION => {
361 self.build_class_declaration(stmt_idx);
362 }
363
364 syntax_kind_ext::RETURN_STATEMENT | syntax_kind_ext::THROW_STATEMENT => {
366 self.record_node_flow(stmt_idx);
367
368 let mut finally_flows: Vec<NodeIndex> = Vec::new();
370 for ctx in self.flow_stack.iter().rev() {
371 if ctx.finally_block.is_some() && ctx.context_type == FlowContextType::Try {
372 finally_flows.push(ctx.finally_block);
373 }
374 }
375
376 for finally_block in finally_flows.iter().rev() {
378 self.build_statement(*finally_block);
379 }
380
381 self.current_flow = self.graph.unreachable_flow;
383 }
384
385 syntax_kind_ext::BREAK_STATEMENT => {
386 self.record_node_flow(stmt_idx);
387 self.handle_break(stmt_idx);
388 }
389
390 syntax_kind_ext::CONTINUE_STATEMENT => {
391 self.record_node_flow(stmt_idx);
392 self.handle_continue(stmt_idx);
393 }
394
395 _ => {
396 self.record_node_flow(stmt_idx);
398 }
399 }
400 }
401
402 pub fn build_block(&mut self, block: &tsz_parser::parser::node::BlockData) {
410 for &stmt_idx in &block.statements.nodes {
411 if stmt_idx.is_some() {
412 self.build_statement(stmt_idx);
413 }
414 }
415 }
416
417 fn build_if_statement(&mut self, if_stmt: &tsz_parser::parser::node::IfStatementData) {
419 self.handle_expression_for_assignments(if_stmt.expression);
421
422 let pre_condition_flow = self.current_flow;
424
425 if pre_condition_flow == self.graph.unreachable_flow {
427 self.build_statement(if_stmt.then_statement);
429 if if_stmt.else_statement.is_some() {
430 self.build_statement(if_stmt.else_statement);
431 }
432 return;
434 }
435
436 let true_flow = self.create_flow_node(
438 flow_flags::TRUE_CONDITION,
439 pre_condition_flow,
440 if_stmt.expression,
441 );
442
443 self.current_flow = true_flow;
445 self.build_statement(if_stmt.then_statement);
446 let post_then_flow = self.current_flow;
447
448 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
450
451 if if_stmt.else_statement.is_some() {
453 let false_flow = self.create_flow_node(
455 flow_flags::FALSE_CONDITION,
456 pre_condition_flow,
457 if_stmt.expression,
458 );
459
460 self.current_flow = false_flow;
462 self.build_statement(if_stmt.else_statement);
463 let post_else_flow = self.current_flow;
464
465 self.add_antecedent(merge_label, post_then_flow);
467 self.add_antecedent(merge_label, post_else_flow);
468 } else {
469 let false_flow = self.create_flow_node(
471 flow_flags::FALSE_CONDITION,
472 pre_condition_flow,
473 if_stmt.expression,
474 );
475
476 self.add_antecedent(merge_label, post_then_flow);
477 self.add_antecedent(merge_label, false_flow);
478 }
479
480 self.current_flow = merge_label;
481 }
482
483 fn build_while_statement(&mut self, loop_data: &tsz_parser::parser::node::LoopData) {
485 let loop_label = self.graph.nodes.alloc(flow_flags::LOOP_LABEL);
487 if self.current_flow.is_some()
488 && let Some(node) = self.graph.nodes.get_mut(loop_label)
489 {
490 node.antecedent.push(self.current_flow);
491 }
492
493 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
495
496 self.flow_stack.push(FlowContext {
498 break_label: merge_label,
499 continue_label: Some(loop_label),
500 context_type: FlowContextType::Loop,
501 finally_block: NodeIndex::NONE,
502 label: NodeIndex::NONE,
503 });
504
505 self.current_flow = loop_label;
506
507 self.handle_expression_for_assignments(loop_data.condition);
509
510 let true_flow =
512 self.create_flow_node(flow_flags::TRUE_CONDITION, loop_label, loop_data.condition);
513
514 self.current_flow = true_flow;
516 self.build_statement(loop_data.statement);
517
518 self.add_antecedent(loop_label, self.current_flow);
520
521 let false_flow =
523 self.create_flow_node(flow_flags::FALSE_CONDITION, loop_label, loop_data.condition);
524
525 self.add_antecedent(merge_label, false_flow);
527
528 self.flow_stack.pop();
529 self.current_flow = merge_label;
530 }
531
532 fn build_do_while_statement(&mut self, loop_data: &tsz_parser::parser::node::LoopData) {
534 let loop_label = self.graph.nodes.alloc(flow_flags::LOOP_LABEL);
536 if self.current_flow.is_some()
537 && let Some(node) = self.graph.nodes.get_mut(loop_label)
538 {
539 node.antecedent.push(self.current_flow);
540 }
541
542 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
544
545 self.flow_stack.push(FlowContext {
547 break_label: merge_label,
548 continue_label: Some(loop_label),
549 context_type: FlowContextType::Loop,
550 finally_block: NodeIndex::NONE,
551 label: NodeIndex::NONE,
552 });
553
554 self.current_flow = loop_label;
555
556 self.build_statement(loop_data.statement);
558
559 self.add_antecedent(loop_label, self.current_flow);
561
562 self.handle_expression_for_assignments(loop_data.condition);
564
565 let pre_condition_flow = self.current_flow;
567
568 let true_flow = self.create_flow_node(
570 flow_flags::TRUE_CONDITION,
571 pre_condition_flow,
572 loop_data.condition,
573 );
574 self.add_antecedent(loop_label, true_flow);
575
576 let false_flow = self.create_flow_node(
578 flow_flags::FALSE_CONDITION,
579 pre_condition_flow,
580 loop_data.condition,
581 );
582 self.add_antecedent(merge_label, false_flow);
583
584 self.flow_stack.pop();
585 self.current_flow = merge_label;
586 }
587
588 fn build_for_statement(&mut self, loop_data: &tsz_parser::parser::node::LoopData) {
590 let loop_label = self.graph.nodes.alloc(flow_flags::LOOP_LABEL);
592 if self.current_flow.is_some()
593 && let Some(node) = self.graph.nodes.get_mut(loop_label)
594 {
595 node.antecedent.push(self.current_flow);
596 }
597
598 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
600
601 self.flow_stack.push(FlowContext {
603 break_label: merge_label,
604 continue_label: Some(loop_label),
605 context_type: FlowContextType::Loop,
606 finally_block: NodeIndex::NONE,
607 label: NodeIndex::NONE,
608 });
609
610 if loop_data.initializer.is_some() {
612 self.build_statement(loop_data.initializer);
613 self.add_antecedent(loop_label, self.current_flow);
614 }
615
616 self.current_flow = loop_label;
617
618 if loop_data.condition.is_some() {
620 self.handle_expression_for_assignments(loop_data.condition);
622
623 let true_flow =
624 self.create_flow_node(flow_flags::TRUE_CONDITION, loop_label, loop_data.condition);
625 self.current_flow = true_flow;
626
627 self.build_statement(loop_data.statement);
629
630 self.add_antecedent(loop_label, self.current_flow);
632
633 let false_flow =
635 self.create_flow_node(flow_flags::FALSE_CONDITION, loop_label, loop_data.condition);
636 self.add_antecedent(merge_label, false_flow);
637 } else {
638 self.build_statement(loop_data.statement);
640 self.add_antecedent(loop_label, self.current_flow);
641 }
642
643 if loop_data.incrementor.is_some() {
645 let flow = self.create_flow_node(
646 flow_flags::ASSIGNMENT,
647 self.current_flow,
648 loop_data.incrementor,
649 );
650 self.current_flow = flow;
651 self.add_antecedent(loop_label, self.current_flow);
652 }
653
654 self.flow_stack.pop();
655 self.current_flow = merge_label;
656 }
657
658 fn build_for_in_statement(&mut self, for_in_of: &tsz_parser::parser::node::ForInOfData) {
660 let loop_label = self.graph.nodes.alloc(flow_flags::LOOP_LABEL);
662 if self.current_flow.is_some()
663 && let Some(node) = self.graph.nodes.get_mut(loop_label)
664 {
665 node.antecedent.push(self.current_flow);
666 }
667
668 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
670
671 self.flow_stack.push(FlowContext {
673 break_label: merge_label,
674 continue_label: Some(loop_label),
675 context_type: FlowContextType::Loop,
676 finally_block: NodeIndex::NONE,
677 label: NodeIndex::NONE,
678 });
679
680 if for_in_of.initializer.is_some() {
682 self.build_statement(for_in_of.initializer);
683 }
684
685 self.current_flow = loop_label;
686
687 self.build_statement(for_in_of.statement);
689
690 self.add_antecedent(loop_label, self.current_flow);
692 self.add_antecedent(merge_label, self.current_flow);
693
694 self.flow_stack.pop();
695 self.current_flow = merge_label;
696 }
697
698 fn build_for_of_statement(&mut self, for_in_of: &tsz_parser::parser::node::ForInOfData) {
700 let loop_label = self.graph.nodes.alloc(flow_flags::LOOP_LABEL);
702 if self.current_flow.is_some()
703 && let Some(node) = self.graph.nodes.get_mut(loop_label)
704 {
705 node.antecedent.push(self.current_flow);
706 }
707
708 let merge_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
710
711 self.flow_stack.push(FlowContext {
713 break_label: merge_label,
714 continue_label: Some(loop_label),
715 context_type: FlowContextType::Loop,
716 finally_block: NodeIndex::NONE,
717 label: NodeIndex::NONE,
718 });
719
720 if for_in_of.initializer.is_some() {
722 self.build_statement(for_in_of.initializer);
723 }
724
725 self.current_flow = loop_label;
726
727 self.build_statement(for_in_of.statement);
729
730 self.add_antecedent(loop_label, self.current_flow);
732 self.add_antecedent(merge_label, self.current_flow);
733
734 self.flow_stack.pop();
735 self.current_flow = merge_label;
736 }
737
738 fn build_switch_statement(&mut self, switch_data: &tsz_parser::parser::node::SwitchData) {
740 self.handle_expression_for_assignments(switch_data.expression);
742
743 let pre_switch_flow = self.current_flow;
744
745 let end_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
747
748 self.flow_stack.push(FlowContext {
750 break_label: end_label,
751 continue_label: None,
752 context_type: FlowContextType::Switch,
753 finally_block: NodeIndex::NONE,
754 label: NodeIndex::NONE,
755 });
756
757 let mut has_default_clause = false;
759
760 if let Some(case_block_node) = self.arena.get(switch_data.case_block) {
762 let Some(case_block) = self.arena.get_block(case_block_node) else {
763 self.flow_stack.pop();
764 self.current_flow = end_label;
765 return;
766 };
767 let mut fallthrough_flow = FlowNodeId::NONE;
768
769 for &clause_idx in &case_block.statements.nodes {
770 if clause_idx.is_none() {
771 continue;
772 }
773 let Some(clause_node) = self.arena.get(clause_idx) else {
774 continue;
775 };
776
777 match clause_node.kind {
778 syntax_kind_ext::CASE_CLAUSE => {
779 if let Some(clause) = self.arena.get_case_clause(clause_node) {
780 let clause_flow = self.create_switch_clause_flow(
782 pre_switch_flow,
783 fallthrough_flow,
784 clause.expression,
785 );
786 self.current_flow = clause_flow;
787
788 for &stmt_idx in &clause.statements.nodes {
790 if stmt_idx.is_some() {
791 self.build_statement(stmt_idx);
792 }
793 }
794
795 if self.current_flow != self.graph.unreachable_flow {
797 fallthrough_flow = self.current_flow;
798 } else {
799 fallthrough_flow = FlowNodeId::NONE;
800 }
801 }
802 }
803
804 syntax_kind_ext::DEFAULT_CLAUSE => {
805 has_default_clause = true;
806 if let Some(clause) = self.arena.get_case_clause(clause_node) {
807 let clause_flow = self.create_switch_clause_flow(
808 pre_switch_flow,
809 fallthrough_flow,
810 NodeIndex::NONE, );
812 self.current_flow = clause_flow;
813
814 for &stmt_idx in &clause.statements.nodes {
815 if stmt_idx.is_some() {
816 self.build_statement(stmt_idx);
817 }
818 }
819
820 self.add_antecedent(end_label, self.current_flow);
821 fallthrough_flow = FlowNodeId::NONE;
822 }
823 }
824
825 _ => {}
826 }
827 }
828
829 if !has_default_clause {
835 let implicit_default_flow = self.create_switch_clause_flow(
836 pre_switch_flow,
837 FlowNodeId::NONE, switch_data.case_block, );
840 self.add_antecedent(end_label, implicit_default_flow);
842 }
843 }
844
845 self.flow_stack.pop();
846 self.current_flow = end_label;
847 }
848
849 fn build_try_statement(&mut self, try_data: &tsz_parser::parser::node::TryData) {
851 let pre_try_flow = self.current_flow;
852 let has_finally = try_data.finally_block.is_some();
853
854 let pre_finally_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
856
857 let finally_ctx = has_finally.then_some(FlowContext {
859 break_label: FlowNodeId::NONE, continue_label: None,
861 context_type: FlowContextType::Try,
862 finally_block: try_data.finally_block,
863 label: NodeIndex::NONE,
864 });
865
866 if let Some(ctx) = finally_ctx {
867 self.flow_stack.push(ctx);
868 }
869
870 self.build_statement(try_data.try_block);
872 let post_try_flow = self.current_flow;
873
874 let post_catch_flow = if try_data.catch_clause.is_some() {
876 if let Some(catch_node) = self.arena.get(try_data.catch_clause) {
877 if let Some(catch) = self.arena.get_catch_clause(catch_node) {
878 self.current_flow = pre_try_flow;
880
881 if catch.variable_declaration.is_some() {
883 self.build_statement(catch.variable_declaration);
884 }
885
886 self.build_statement(catch.block);
888 Some(self.current_flow)
889 } else {
890 None
891 }
892 } else {
893 None
894 }
895 } else {
896 None
897 };
898
899 if has_finally {
901 self.flow_stack.pop();
902 }
903
904 self.add_antecedent(pre_finally_label, post_try_flow);
906
907 if let Some(catch_flow) = post_catch_flow {
909 self.add_antecedent(pre_finally_label, catch_flow);
910 }
911
912 if has_finally {
914 self.current_flow = pre_finally_label;
916 self.build_statement(try_data.finally_block);
917 } else {
919 self.current_flow = pre_finally_label;
921 }
922 }
923
924 fn build_labeled_statement(&mut self, labeled_data: &tsz_parser::parser::node::LabeledData) {
929 let break_label = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
931
932 self.flow_stack.push(FlowContext {
934 break_label,
935 continue_label: None, context_type: FlowContextType::Loop, finally_block: NodeIndex::NONE,
938 label: labeled_data.label,
939 });
940
941 self.build_statement(labeled_data.statement);
943
944 self.flow_stack.pop();
946
947 self.current_flow = break_label;
949 }
950
951 fn build_variable_declaration(
953 &mut self,
954 var_decl: &tsz_parser::parser::node::VariableDeclarationData,
955 idx: NodeIndex,
956 ) {
957 self.track_variable_declaration(var_decl, idx);
959
960 if var_decl.initializer.is_some() {
962 self.handle_expression_for_suspension_points(var_decl.initializer);
963 }
964 }
965
966 fn handle_break(&mut self, stmt_idx: NodeIndex) {
968 let break_label = if let Some(stmt_node) = self.arena.get(stmt_idx) {
970 self.arena
971 .get_jump_data(stmt_node)
972 .map(|jump_data| jump_data.label)
973 .unwrap_or(NodeIndex::NONE)
974 } else {
975 NodeIndex::NONE
976 };
977
978 let mut finally_blocks: Vec<NodeIndex> = Vec::new();
980 let mut target_label = FlowNodeId::NONE;
981
982 let label_text = if break_label.is_some() {
984 self.arena
985 .get(break_label)
986 .and_then(|node| self.arena.get_identifier(node))
987 .map(|id| id.escaped_text.as_str())
988 } else {
989 None
990 };
991
992 for ctx in self.flow_stack.iter().rev() {
993 if ctx.finally_block.is_some() && ctx.context_type == FlowContextType::Try {
994 finally_blocks.push(ctx.finally_block);
995 }
996
997 if let Some(label) = label_text {
999 if ctx.label.is_some()
1000 && let Some(ctx_label_node) = self.arena.get(ctx.label)
1001 && let Some(ctx_label_data) = self.arena.get_identifier(ctx_label_node)
1002 && ctx_label_data.escaped_text == label
1003 {
1004 target_label = ctx.break_label;
1005 break;
1006 }
1007 } else {
1008 if ctx.break_label != FlowNodeId::NONE {
1010 target_label = ctx.break_label;
1011 break;
1012 }
1013 }
1014 }
1015
1016 for finally_block in finally_blocks.iter().rev() {
1018 self.build_statement(*finally_block);
1019 }
1020
1021 if target_label.is_some() {
1023 self.add_antecedent(target_label, self.current_flow);
1024 }
1025 self.current_flow = self.graph.unreachable_flow;
1026 }
1027
1028 fn handle_continue(&mut self, stmt_idx: NodeIndex) {
1030 let continue_label_idx = if let Some(stmt_node) = self.arena.get(stmt_idx) {
1032 self.arena
1033 .get_jump_data(stmt_node)
1034 .map(|jump_data| jump_data.label)
1035 .unwrap_or(NodeIndex::NONE)
1036 } else {
1037 NodeIndex::NONE
1038 };
1039
1040 let mut finally_blocks: Vec<NodeIndex> = Vec::new();
1042 let mut target_label = FlowNodeId::NONE;
1043
1044 let label_text = if continue_label_idx.is_some() {
1046 self.arena
1047 .get(continue_label_idx)
1048 .and_then(|node| self.arena.get_identifier(node))
1049 .map(|id| id.escaped_text.as_str())
1050 } else {
1051 None
1052 };
1053
1054 for ctx in self.flow_stack.iter().rev() {
1055 if ctx.finally_block.is_some() && ctx.context_type == FlowContextType::Try {
1056 finally_blocks.push(ctx.finally_block);
1057 }
1058
1059 if let Some(label) = label_text {
1061 if ctx.label.is_some()
1062 && let Some(ctx_label_node) = self.arena.get(ctx.label)
1063 && let Some(ctx_label_data) = self.arena.get_identifier(ctx_label_node)
1064 && ctx_label_data.escaped_text == label
1065 && let Some(continue_label) = ctx.continue_label
1066 {
1067 target_label = continue_label;
1068 break;
1069 }
1070 } else {
1071 if let Some(continue_label) = ctx.continue_label {
1073 target_label = continue_label;
1074 break;
1075 }
1076 }
1077 }
1078
1079 for finally_block in finally_blocks.iter().rev() {
1081 self.build_statement(*finally_block);
1082 }
1083
1084 if target_label.is_some() {
1086 self.add_antecedent(target_label, self.current_flow);
1087 }
1088 self.current_flow = self.graph.unreachable_flow;
1089 }
1090
1091 fn create_flow_node(
1093 &mut self,
1094 flags: u32,
1095 antecedent: FlowNodeId,
1096 node: NodeIndex,
1097 ) -> FlowNodeId {
1098 if antecedent == self.graph.unreachable_flow {
1101 return self.graph.unreachable_flow;
1102 }
1103
1104 let id = self.graph.nodes.alloc(flags);
1105 if let Some(flow) = self.graph.nodes.get_mut(id) {
1106 if antecedent.is_some() && antecedent != self.graph.unreachable_flow {
1107 flow.antecedent.push(antecedent);
1108 }
1109 flow.node = node;
1110 }
1111 id
1112 }
1113
1114 fn create_switch_clause_flow(
1116 &mut self,
1117 pre_switch: FlowNodeId,
1118 fallthrough: FlowNodeId,
1119 expression: NodeIndex,
1120 ) -> FlowNodeId {
1121 let id = self.graph.nodes.alloc(flow_flags::SWITCH_CLAUSE);
1122 if let Some(node) = self.graph.nodes.get_mut(id) {
1123 node.node = expression;
1124 if pre_switch.is_some() && pre_switch != self.graph.unreachable_flow {
1125 node.antecedent.push(pre_switch);
1126 }
1127 if fallthrough.is_some() && fallthrough != self.graph.unreachable_flow {
1128 node.antecedent.push(fallthrough);
1129 }
1130 }
1131 id
1132 }
1133
1134 fn add_antecedent(&mut self, label: FlowNodeId, antecedent: FlowNodeId) {
1136 if antecedent.is_none() || antecedent == self.graph.unreachable_flow {
1137 return;
1138 }
1139
1140 if let Some(node) = self.graph.nodes.get_mut(label)
1141 && !node.antecedent.contains(&antecedent)
1142 {
1143 node.antecedent.push(antecedent);
1144 }
1145 }
1146
1147 fn record_node_flow(&mut self, node: NodeIndex) {
1149 if self.current_flow.is_some() {
1150 self.graph.node_flow.insert(node.0, self.current_flow);
1151
1152 if self.current_flow == self.graph.unreachable_flow {
1154 self.graph.mark_unreachable(node);
1155 }
1156 }
1157 }
1158
1159 const fn in_async_function(&self) -> bool {
1161 self.async_depth > 0
1162 }
1163
1164 const fn in_generator_function(&self) -> bool {
1166 self.generator_depth > 0
1167 }
1168
1169 fn track_variable_declaration(
1184 &mut self,
1185 var_decl: &tsz_parser::parser::node::VariableDeclarationData,
1186 decl_node: NodeIndex,
1187 ) {
1188 self.record_node_flow(decl_node);
1190
1191 if var_decl.initializer.is_some() {
1193 self.track_assignment(decl_node);
1194 }
1195 }
1196
1197 fn track_assignment(&mut self, target: NodeIndex) {
1204 let flow = self.create_flow_node(flow_flags::ASSIGNMENT, self.current_flow, target);
1206 self.current_flow = flow;
1207 }
1208
1209 fn handle_expression_for_suspension_points(&mut self, expr_idx: NodeIndex) {
1215 let Some(node) = self.arena.get(expr_idx) else {
1216 return;
1217 };
1218
1219 if self.in_async_function()
1223 && node.kind == SyntaxKind::Identifier as u16
1224 && let Some(ident) = self.arena.get_identifier(node)
1225 && ident.escaped_text == "await"
1226 {
1227 self.handle_await_expression(expr_idx);
1228 return;
1229 }
1230
1231 if node.kind == syntax_kind_ext::AWAIT_EXPRESSION {
1233 self.handle_await_expression(expr_idx);
1234 if let Some(unary_data) = self.arena.get_unary_expr_ex(node) {
1236 self.handle_expression_for_suspension_points(unary_data.expression);
1237 }
1238 return;
1239 }
1240
1241 if node.kind == syntax_kind_ext::YIELD_EXPRESSION {
1243 self.handle_yield_expression(expr_idx);
1244 if let Some(unary_data) = self.arena.get_unary_expr_ex(node)
1246 && unary_data.expression.is_some()
1247 {
1248 self.handle_expression_for_suspension_points(unary_data.expression);
1249 }
1250 return;
1251 }
1252
1253 match node.kind {
1255 syntax_kind_ext::BINARY_EXPRESSION => {
1256 if let Some(binary) = self.arena.get_binary_expr(node) {
1257 self.handle_expression_for_suspension_points(binary.left);
1258 self.handle_expression_for_suspension_points(binary.right);
1259 }
1260 }
1261 syntax_kind_ext::CONDITIONAL_EXPRESSION => {
1262 if let Some(cond) = self.arena.get_conditional_expr(node) {
1263 self.handle_expression_for_suspension_points(cond.condition);
1264 self.handle_expression_for_suspension_points(cond.when_true);
1265 self.handle_expression_for_suspension_points(cond.when_false);
1266 }
1267 }
1268 syntax_kind_ext::CALL_EXPRESSION => {
1269 if let Some(call) = self.arena.get_call_expr(node) {
1270 self.handle_expression_for_suspension_points(call.expression);
1271 if let Some(args) = &call.arguments {
1272 for &arg in &args.nodes {
1273 if arg.is_some() {
1274 self.handle_expression_for_suspension_points(arg);
1275 }
1276 }
1277 }
1278 }
1279 }
1280 syntax_kind_ext::PROPERTY_ACCESS_EXPRESSION
1281 | syntax_kind_ext::ELEMENT_ACCESS_EXPRESSION => {
1282 if let Some(access) = self.arena.get_access_expr(node) {
1283 self.handle_expression_for_suspension_points(access.expression);
1284 if access.name_or_argument.is_some() {
1285 self.handle_expression_for_suspension_points(access.name_or_argument);
1286 }
1287 }
1288 }
1289 _ => {
1290 }
1293 }
1294 }
1295
1296 fn handle_expression_for_assignments(&mut self, expr_idx: NodeIndex) {
1300 let Some(node) = self.arena.get(expr_idx) else {
1301 return;
1302 };
1303
1304 match node.kind {
1305 syntax_kind_ext::BINARY_EXPRESSION => {
1306 let Some(binary) = self.arena.get_binary_expr(node) else {
1307 return;
1308 };
1309
1310 let is_short_circuit = binary.operator_token
1312 == tsz_scanner::SyntaxKind::AmpersandAmpersandToken as u16
1313 || binary.operator_token == tsz_scanner::SyntaxKind::BarBarToken as u16
1314 || binary.operator_token
1315 == tsz_scanner::SyntaxKind::QuestionQuestionToken as u16;
1316
1317 if is_short_circuit {
1318 self.handle_expression_for_assignments(binary.left);
1321 let after_left_flow = self.current_flow;
1322
1323 if binary.operator_token
1324 == tsz_scanner::SyntaxKind::AmpersandAmpersandToken as u16
1325 {
1326 let true_condition = self.create_flow_node(
1328 flow_flags::TRUE_CONDITION,
1329 after_left_flow,
1330 binary.left,
1331 );
1332 self.current_flow = true_condition;
1333 self.handle_expression_for_assignments(binary.right);
1334 let after_right_flow = self.current_flow;
1335
1336 let false_condition = self.create_flow_node(
1338 flow_flags::FALSE_CONDITION,
1339 after_left_flow,
1340 binary.left,
1341 );
1342
1343 let merge = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
1345 self.add_antecedent(merge, after_right_flow);
1346 self.add_antecedent(merge, false_condition);
1347 self.current_flow = merge;
1348 } else {
1349 let false_condition = self.create_flow_node(
1351 flow_flags::FALSE_CONDITION,
1352 after_left_flow,
1353 binary.left,
1354 );
1355 self.current_flow = false_condition;
1356 self.handle_expression_for_assignments(binary.right);
1357 let after_right_flow = self.current_flow;
1358
1359 let true_condition = self.create_flow_node(
1361 flow_flags::TRUE_CONDITION,
1362 after_left_flow,
1363 binary.left,
1364 );
1365
1366 let merge = self.graph.nodes.alloc(flow_flags::BRANCH_LABEL);
1368 self.add_antecedent(merge, after_right_flow);
1369 self.add_antecedent(merge, true_condition);
1370 self.current_flow = merge;
1371 }
1372 } else {
1373 if Self::is_assignment_operator_token(binary.operator_token) {
1375 let flow = self.create_flow_node(
1376 flow_flags::ASSIGNMENT,
1377 self.current_flow,
1378 expr_idx,
1379 );
1380 self.current_flow = flow;
1381 }
1382
1383 self.handle_expression_for_assignments(binary.left);
1384 self.handle_expression_for_assignments(binary.right);
1385 }
1386 }
1387 syntax_kind_ext::CONDITIONAL_EXPRESSION => {
1388 if let Some(cond) = self.arena.get_conditional_expr(node) {
1389 self.handle_expression_for_assignments(cond.condition);
1390 self.handle_expression_for_assignments(cond.when_true);
1391 self.handle_expression_for_assignments(cond.when_false);
1392 }
1393 }
1394 syntax_kind_ext::CALL_EXPRESSION => {
1395 if let Some(call) = self.arena.get_call_expr(node) {
1396 self.handle_expression_for_assignments(call.expression);
1397 if let Some(args) = &call.arguments {
1398 for &arg in &args.nodes {
1399 if arg.is_some() {
1400 self.handle_expression_for_assignments(arg);
1401 }
1402 }
1403 }
1404
1405 if self.is_array_mutation_call(expr_idx) {
1407 let flow = self.create_flow_array_mutation(expr_idx);
1408 self.current_flow = flow;
1409 }
1410 }
1411 }
1412 syntax_kind_ext::PROPERTY_ACCESS_EXPRESSION
1413 | syntax_kind_ext::ELEMENT_ACCESS_EXPRESSION => {
1414 if let Some(access) = self.arena.get_access_expr(node) {
1415 self.handle_expression_for_assignments(access.expression);
1416 if access.name_or_argument.is_some() {
1417 self.handle_expression_for_assignments(access.name_or_argument);
1418 }
1419 }
1420 }
1421 _ => {}
1422 }
1423 }
1424
1425 const fn is_assignment_operator_token(operator_token: u16) -> bool {
1426 matches!(
1427 operator_token,
1428 x if x == SyntaxKind::EqualsToken as u16
1429 || x == SyntaxKind::PlusEqualsToken as u16
1430 || x == SyntaxKind::MinusEqualsToken as u16
1431 || x == SyntaxKind::AsteriskEqualsToken as u16
1432 || x == SyntaxKind::SlashEqualsToken as u16
1433 || x == SyntaxKind::PercentEqualsToken as u16
1434 || x == SyntaxKind::AsteriskAsteriskEqualsToken as u16
1435 || x == SyntaxKind::LessThanLessThanEqualsToken as u16
1436 || x == SyntaxKind::GreaterThanGreaterThanEqualsToken as u16
1437 || x == SyntaxKind::GreaterThanGreaterThanGreaterThanEqualsToken as u16
1438 || x == SyntaxKind::AmpersandEqualsToken as u16
1439 || x == SyntaxKind::CaretEqualsToken as u16
1440 || x == SyntaxKind::BarEqualsToken as u16
1441 || x == SyntaxKind::BarBarEqualsToken as u16
1442 || x == SyntaxKind::AmpersandAmpersandEqualsToken as u16
1443 || x == SyntaxKind::QuestionQuestionEqualsToken as u16
1444 )
1445 }
1446
1447 fn is_array_mutation_call(&self, call_idx: NodeIndex) -> bool {
1449 let Some(call_node) = self.arena.get(call_idx) else {
1450 return false;
1451 };
1452 let Some(call) = self.arena.get_call_expr(call_node) else {
1453 return false;
1454 };
1455 let Some(callee_node) = self.arena.get(call.expression) else {
1456 return false;
1457 };
1458 let Some(access) = self.arena.get_access_expr(callee_node) else {
1459 return false;
1460 };
1461
1462 if access.question_dot_token {
1464 return false;
1465 }
1466
1467 let Some(name_node) = self.arena.get(access.name_or_argument) else {
1468 return false;
1469 };
1470
1471 let name = if let Some(ident) = self.arena.get_identifier(name_node) {
1472 ident.escaped_text.as_str()
1473 } else if let Some(literal) = self.arena.get_literal(name_node) {
1474 if name_node.kind == tsz_scanner::SyntaxKind::StringLiteral as u16 {
1475 literal.text.as_str()
1476 } else {
1477 return false;
1478 }
1479 } else {
1480 return false;
1481 };
1482
1483 matches!(
1484 name,
1485 "copyWithin"
1486 | "fill"
1487 | "pop"
1488 | "push"
1489 | "reverse"
1490 | "shift"
1491 | "sort"
1492 | "splice"
1493 | "unshift"
1494 )
1495 }
1496
1497 fn create_flow_array_mutation(&mut self, call_idx: NodeIndex) -> FlowNodeId {
1499 let id = self.graph.nodes.alloc(flow_flags::ARRAY_MUTATION);
1500 if let Some(node) = self.graph.nodes.get_mut(id) {
1501 node.node = call_idx;
1502 if self.current_flow.is_some() && self.current_flow != self.graph.unreachable_flow {
1503 node.antecedent.push(self.current_flow);
1504 }
1505 }
1506 id
1507 }
1508
1509 fn handle_await_expression(&mut self, await_node: NodeIndex) {
1511 if self.in_async_function() {
1512 let await_point =
1514 self.create_flow_node(flow_flags::AWAIT_POINT, self.current_flow, await_node);
1515 self.current_flow = await_point;
1516 }
1517 }
1519
1520 fn handle_yield_expression(&mut self, yield_node: NodeIndex) {
1522 if self.in_generator_function() {
1523 let yield_point =
1525 self.create_flow_node(flow_flags::YIELD_POINT, self.current_flow, yield_node);
1526 self.current_flow = yield_point;
1527 }
1528 }
1530
1531 pub const fn graph(&self) -> &FlowGraph {
1533 &self.graph
1534 }
1535
1536 pub fn into_graph(self) -> FlowGraph {
1538 self.graph
1539 }
1540
1541 fn build_class_declaration(&mut self, idx: NodeIndex) {
1553 let Some(node) = self.arena.get(idx) else {
1554 return;
1555 };
1556 let Some(class) = self.arena.get_class(node) else {
1557 return;
1558 };
1559
1560 if let Some(heritage_clauses) = &class.heritage_clauses {
1562 for &clause_idx in &heritage_clauses.nodes {
1563 if clause_idx.is_none() {
1564 continue;
1565 }
1566 if let Some(clause_node) = self.arena.get(clause_idx)
1567 && let Some(heritage) = self.arena.get_heritage_clause(clause_node)
1568 {
1569 if heritage.token == SyntaxKind::ExtendsKeyword as u16 {
1571 for &type_idx in &heritage.types.nodes {
1572 if type_idx.is_none() {
1573 continue;
1574 }
1575 if let Some(expr_with_type) = self.arena.get(type_idx)
1576 && let Some(data) = self.arena.get_expr_type_args(expr_with_type)
1577 {
1578 self.handle_expression_for_suspension_points(data.expression);
1580 }
1581 }
1582 }
1583 }
1584 }
1585 }
1586
1587 let members = class.members.nodes.clone();
1589
1590 for &member_idx in &members {
1595 if member_idx.is_none() {
1596 continue;
1597 }
1598 let Some(member_node) = self.arena.get(member_idx) else {
1599 continue;
1600 };
1601
1602 match member_node.kind {
1603 k if k == syntax_kind_ext::PROPERTY_DECLARATION => {
1604 if let Some(prop) = self.arena.get_property_decl(member_node) {
1605 let prop_name = prop.name;
1606 let prop_initializer = prop.initializer;
1607 let prop_modifiers = prop.modifiers.clone();
1608
1609 if let Some(name_node) = self.arena.get(prop_name)
1611 && name_node.kind == syntax_kind_ext::COMPUTED_PROPERTY_NAME
1612 && let Some(computed) = self.arena.get_computed_property(name_node)
1613 {
1614 self.handle_expression_for_suspension_points(computed.expression);
1615 }
1616
1617 if self.has_static_modifier(&prop_modifiers) && prop_initializer.is_some() {
1619 self.handle_expression_for_suspension_points(prop_initializer);
1620 let flow = self.create_flow_node(
1622 flow_flags::ASSIGNMENT,
1623 self.current_flow,
1624 member_idx,
1625 );
1626 self.current_flow = flow;
1627 }
1628 }
1629 }
1630 k if k == syntax_kind_ext::CLASS_STATIC_BLOCK_DECLARATION => {
1631 if let Some(block) = self.arena.get_block(member_node) {
1633 self.build_block(block);
1634 }
1635 }
1636 k if k == syntax_kind_ext::METHOD_DECLARATION => {
1637 if let Some(method) = self.arena.get_method_decl(member_node) {
1639 let method_name = method.name;
1640 if let Some(name_node) = self.arena.get(method_name)
1641 && name_node.kind == syntax_kind_ext::COMPUTED_PROPERTY_NAME
1642 && let Some(computed) = self.arena.get_computed_property(name_node)
1643 {
1644 self.handle_expression_for_suspension_points(computed.expression);
1645 }
1646 }
1647 }
1648 k if k == syntax_kind_ext::GET_ACCESSOR || k == syntax_kind_ext::SET_ACCESSOR => {
1649 if let Some(accessor) = self.arena.get_accessor(member_node) {
1651 let accessor_name = accessor.name;
1652 if let Some(name_node) = self.arena.get(accessor_name)
1653 && name_node.kind == syntax_kind_ext::COMPUTED_PROPERTY_NAME
1654 && let Some(computed) = self.arena.get_computed_property(name_node)
1655 {
1656 self.handle_expression_for_suspension_points(computed.expression);
1657 }
1658 }
1659 }
1660 _ => {}
1661 }
1662 }
1663
1664 self.record_node_flow(idx);
1665 }
1666
1667 fn has_static_modifier(&self, modifiers: &Option<NodeList>) -> bool {
1669 self.arena
1670 .has_modifier(modifiers, SyntaxKind::StaticKeyword)
1671 }
1672}
1673
1674#[cfg(test)]
1675#[path = "../../tests/flow_graph_builder.rs"]
1676mod tests;