cairo_lang_lowering/borrow_check/
analysis.rs

1//! This module introduces the BackAnalysis utility that allows writing analyzers that go backwards
2//! in the flow of the program, on a Lowered representation.
3
4use std::collections::HashMap;
5
6use crate::{Block, BlockEnd, BlockId, Lowered, MatchInfo, Statement, VarRemapping, VarUsage};
7
8/// Location of a lowering statement inside a block.
9pub type StatementLocation = (BlockId, usize);
10
11/// Analyzer trait to implement for each specific analysis.
12#[allow(unused_variables)]
13pub trait Analyzer<'db, 'a> {
14    type Info: Clone;
15    fn visit_block_start(&mut self, info: &mut Self::Info, block_id: BlockId, block: &Block<'db>) {}
16    fn visit_stmt(
17        &mut self,
18        info: &mut Self::Info,
19        statement_location: StatementLocation,
20        stmt: &'a Statement<'db>,
21    ) {
22    }
23    fn visit_goto(
24        &mut self,
25        info: &mut Self::Info,
26        statement_location: StatementLocation,
27        target_block_id: BlockId,
28        remapping: &'a VarRemapping<'db>,
29    ) {
30    }
31    fn merge_match(
32        &mut self,
33        statement_location: StatementLocation,
34        match_info: &'a MatchInfo<'db>,
35        infos: impl Iterator<Item = Self::Info>,
36    ) -> Self::Info;
37    fn info_from_return(
38        &mut self,
39        statement_location: StatementLocation,
40        vars: &'a [VarUsage<'db>],
41    ) -> Self::Info;
42
43    /// Default `info_from_panic` implementation for post 'lower_panics' phases.
44    /// Earlier phases need to override this implementation.
45    fn info_from_panic(
46        &mut self,
47        statement_location: StatementLocation,
48        var: &VarUsage<'db>,
49    ) -> Self::Info {
50        unreachable!("Panics should have been stripped in the `lower_panics` phase.");
51    }
52}
53
54/// Main analysis type that allows traversing the flow backwards.
55pub struct BackAnalysis<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> {
56    lowered: &'a Lowered<'db>,
57    pub analyzer: TAnalyzer,
58    block_info: HashMap<BlockId, TAnalyzer::Info>,
59}
60impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
61    /// Creates a new BackAnalysis instance.
62    pub fn new(lowered: &'a Lowered<'db>, analyzer: TAnalyzer) -> Self {
63        Self { lowered, analyzer, block_info: Default::default() }
64    }
65    /// Gets the analysis info for the entire function.
66    pub fn get_root_info(&mut self) -> TAnalyzer::Info {
67        let mut dfs_stack = vec![BlockId::root()];
68        while let Some(block_id) = dfs_stack.last() {
69            let end = &self.lowered.blocks[*block_id].end;
70            if !self.add_missing_dependency_blocks(&mut dfs_stack, end) {
71                self.calc_block_info(dfs_stack.pop().unwrap());
72            }
73        }
74        self.block_info.remove(&BlockId::root()).unwrap()
75    }
76
77    /// Gets the analysis info from the start of a block.
78    fn calc_block_info(&mut self, block_id: BlockId) {
79        let mut info = self.get_end_info(block_id);
80
81        // Go through statements backwards, and update info.
82        for (i, stmt) in self.lowered.blocks[block_id].statements.iter().enumerate().rev() {
83            let statement_location = (block_id, i);
84            self.analyzer.visit_stmt(&mut info, statement_location, stmt);
85        }
86
87        self.analyzer.visit_block_start(&mut info, block_id, &self.lowered.blocks[block_id]);
88
89        // Store result.
90        self.block_info.insert(block_id, info);
91    }
92
93    /// Adds to the DFS stack the dependent blocks that are not yet in cache - returns whether if
94    /// there are any such blocks.
95    fn add_missing_dependency_blocks(
96        &self,
97        dfs_stack: &mut Vec<BlockId>,
98        block_end: &'a BlockEnd<'_>,
99    ) -> bool {
100        match block_end {
101            BlockEnd::NotSet => unreachable!(),
102            BlockEnd::Goto(target_block_id, _)
103                if !self.block_info.contains_key(target_block_id) =>
104            {
105                dfs_stack.push(*target_block_id);
106                true
107            }
108            BlockEnd::Goto(_, _) | BlockEnd::Return(..) | BlockEnd::Panic(_) => false,
109            BlockEnd::Match { info } => {
110                let mut missing_cache = false;
111                for arm in info.arms() {
112                    if !self.block_info.contains_key(&arm.block_id) {
113                        dfs_stack.push(arm.block_id);
114                        missing_cache = true;
115                    }
116                }
117                missing_cache
118            }
119        }
120    }
121
122    /// Gets the analysis info from the block's end onwards.
123    fn get_end_info(&mut self, block_id: BlockId) -> TAnalyzer::Info {
124        let block_end = &self.lowered.blocks[block_id].end;
125        let statement_location = (block_id, self.lowered.blocks[block_id].statements.len());
126        match block_end {
127            BlockEnd::NotSet => unreachable!(),
128            BlockEnd::Goto(target_block_id, remapping) => {
129                let mut info = self.block_info[target_block_id].clone();
130                self.analyzer.visit_goto(
131                    &mut info,
132                    statement_location,
133                    *target_block_id,
134                    remapping,
135                );
136                info
137            }
138            BlockEnd::Return(vars, _location) => {
139                self.analyzer.info_from_return(statement_location, vars)
140            }
141            BlockEnd::Panic(data) => self.analyzer.info_from_panic(statement_location, data),
142            BlockEnd::Match { info } => {
143                // Can remove the block since match blocks do not merge.
144                let arm_infos =
145                    info.arms().iter().map(|arm| self.block_info.remove(&arm.block_id).unwrap());
146                self.analyzer.merge_match(statement_location, info, arm_infos)
147            }
148        }
149    }
150}
cairo_lang_lowering/borrow_check/analysis.rs

cairo_lang_lowering/borrow_check/
analysis.rs
