cairo_lang_lowering/optimizations/
validate.rs

1use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
2
3use crate::borrow_check::analysis::StatementLocation;
4use crate::{BlockId, FlatLowered, VariableId};
5
6/// Possible failing validations.
7#[derive(Debug)]
8pub enum ValidationError {
9    /// A variable was used in statement before being introduced.
10    UnknownUsageInStatement(VariableId, StatementLocation),
11    /// A variable was used in the end of a block before being introduced.
12    UnknownUsageInEnd(VariableId, BlockId),
13    /// A variable was introduced twice.
14    DoubleIntroduction(VariableId, Introduction, Introduction),
15}
16impl ValidationError {
17    pub fn to_message(&self) -> String {
18        match self {
19            ValidationError::UnknownUsageInStatement(var_id, (block_id, idx)) => format!(
20                "Variable `v{}` used in block{}:{idx} before being introduced",
21                var_id.index(),
22                block_id.0
23            ),
24            ValidationError::UnknownUsageInEnd(var_id, block_id) => format!(
25                "Variable `v{}` used in end of block{} before being introduced",
26                var_id.index(),
27                block_id.0
28            ),
29            ValidationError::DoubleIntroduction(var_id, intro1, intro2) => format!(
30                "Variable `v{}` introduced twice at: `{intro1}` and `{intro2}`",
31                var_id.index()
32            ),
33        }
34    }
35}
36
37/// Validates that the lowering structure is valid.
38///
39/// Currently only does basic SSA validations.
40pub fn validate(lowered: &FlatLowered) -> Result<(), ValidationError> {
41    if lowered.blocks.is_empty() {
42        return Ok(());
43    }
44    let mut introductions = UnorderedHashMap::<VariableId, Introduction>::default();
45    for param in &lowered.parameters {
46        introductions.insert(*param, Introduction::Parameter);
47    }
48
49    let mut stack = vec![BlockId::root()];
50    let mut visited = vec![false; lowered.blocks.len()];
51    while let Some(block_id) = stack.pop() {
52        if visited[block_id.0] {
53            continue;
54        }
55        visited[block_id.0] = true;
56        let block = &lowered.blocks[block_id];
57        for (stmt_index, stmt) in block.statements.iter().enumerate() {
58            for input in stmt.inputs() {
59                if !introductions.contains_key(&input.var_id) {
60                    return Err(ValidationError::UnknownUsageInStatement(
61                        input.var_id,
62                        (block_id, stmt_index),
63                    ));
64                }
65            }
66            for output in stmt.outputs().iter() {
67                let intro = Introduction::Statement((block_id, stmt_index));
68                if let Some(prev) = introductions.insert(*output, intro) {
69                    return Err(ValidationError::DoubleIntroduction(*output, prev, intro));
70                }
71            }
72        }
73        match &block.end {
74            crate::FlatBlockEnd::NotSet => unreachable!(),
75            crate::FlatBlockEnd::Return(vars, ..) => {
76                for var in vars {
77                    if !introductions.contains_key(&var.var_id) {
78                        return Err(ValidationError::UnknownUsageInEnd(var.var_id, block_id));
79                    }
80                }
81            }
82            crate::FlatBlockEnd::Panic(var) => {
83                if !introductions.contains_key(&var.var_id) {
84                    return Err(ValidationError::UnknownUsageInEnd(var.var_id, block_id));
85                }
86            }
87            crate::FlatBlockEnd::Goto(target_block_id, remapping) => {
88                for (new_var, old_var) in remapping.iter() {
89                    if !introductions.contains_key(&old_var.var_id) {
90                        return Err(ValidationError::UnknownUsageInEnd(old_var.var_id, block_id));
91                    }
92                    let intro = Introduction::Remapping(block_id, *target_block_id);
93                    if let Some(prev) = introductions.insert(*new_var, intro) {
94                        if !matches!(
95                            prev,
96                            Introduction::Remapping(_, target) if target == *target_block_id,
97                        ) {
98                            return Err(ValidationError::DoubleIntroduction(*new_var, prev, intro));
99                        }
100                    }
101                }
102                stack.push(*target_block_id);
103            }
104            crate::FlatBlockEnd::Match { info } => {
105                for input in info.inputs() {
106                    if !introductions.contains_key(&input.var_id) {
107                        return Err(ValidationError::UnknownUsageInEnd(input.var_id, block_id));
108                    }
109                }
110                for (arm_idx, arm) in info.arms().iter().enumerate() {
111                    for output in arm.var_ids.iter() {
112                        let intro = Introduction::Match(block_id, arm_idx);
113                        if let Some(prev) = introductions.insert(*output, intro) {
114                            return Err(ValidationError::DoubleIntroduction(*output, prev, intro));
115                        }
116                    }
117                    stack.push(arm.block_id);
118                }
119            }
120        }
121    }
122    Ok(())
123}
124
125/// The point a variable was introduced.
126#[derive(Copy, Clone, Debug, Eq, PartialEq)]
127pub enum Introduction {
128    /// The variable is a parameter.
129    Parameter,
130    /// The variable was introduced by a statement.
131    Statement(StatementLocation),
132    /// The variable was introduced by a remapping at the end of a block `0` to be supplied to block
133    /// `1`.
134    Remapping(BlockId, BlockId),
135    /// The variable was introduced by a match arm.
136    Match(BlockId, usize),
137}
138impl std::fmt::Display for Introduction {
139    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
140        match self {
141            Introduction::Parameter => write!(f, "parameter"),
142            Introduction::Statement((block_id, idx)) => write!(f, "block{}:{}", block_id.0, idx),
143            Introduction::Remapping(src, dst) => write!(f, "remapping {} -> {}", src.0, dst.0),
144            Introduction::Match(block_id, arm_idx) => {
145                write!(f, "block{} arm{}", block_id.0, arm_idx)
146            }
147        }
148    }
149}
cairo_lang_lowering/optimizations/validate.rs

cairo_lang_lowering/optimizations/
validate.rs
