cairo_lang_lowering/borrow_check/
demand.rs

1//! This module provides the Demand utility struct used for analyzing usage of variables.
2use cairo_lang_utils::ordered_hash_map::OrderedHashMap;
3
4/// A reporting trait that reports each variables dup, drop and last_use positions.
5pub trait DemandReporter<Var, Aux = ()> {
6    type UsePosition: Copy;
7    type IntroducePosition: Copy;
8    fn drop_aux(&mut self, position: Self::IntroducePosition, var: Var, _aux: Aux) {
9        self.drop(position, var);
10    }
11    fn drop(&mut self, _position: Self::IntroducePosition, _var: Var) {}
12    fn dup(
13        &mut self,
14        _position: Self::UsePosition,
15        _var: Var,
16        _next_usage_position: Self::UsePosition,
17    ) {
18    }
19    fn last_use(&mut self, _position: Self::UsePosition, _var: Var) {}
20    fn unused_mapped_var(&mut self, _var: Var) {}
21}
22
23pub struct EmptyDemandReporter {}
24
25impl<Var> DemandReporter<Var> for EmptyDemandReporter {
26    type IntroducePosition = ();
27    type UsePosition = ();
28}
29
30/// Demanded variables from a certain point in the flow until the end of the function.
31/// Needs to be updated in backwards order.
32#[derive(Clone)]
33pub struct Demand<Var: std::hash::Hash + Eq + Copy, UsePosition, Aux: Clone + Default = ()> {
34    pub vars: OrderedHashMap<Var, UsePosition>,
35    pub aux: Aux,
36}
37impl<Var: std::hash::Hash + Eq + Copy, UsePosition, Aux: Clone + Default> Default
38    for Demand<Var, UsePosition, Aux>
39{
40    fn default() -> Self {
41        Self { vars: Default::default(), aux: Default::default() }
42    }
43}
44impl<Var: std::hash::Hash + Eq + Copy, UsePosition: Copy, Aux: Clone + Default + AuxCombine>
45    Demand<Var, UsePosition, Aux>
46{
47    /// Finalizes a demand. Returns a boolean representing success - if all the variable demands
48    /// were satisfied.
49    pub fn finalize(self) -> bool {
50        self.vars.is_empty()
51    }
52
53    /// Updates the demand when a variable remapping occurs.
54    pub fn apply_remapping<
55        'a,
56        V: Copy + Into<Var> + 'a,
57        T: DemandReporter<Var, Aux, UsePosition = UsePosition>,
58    >(
59        &mut self,
60        reporter: &mut T,
61        remapping: impl std::iter::DoubleEndedIterator<Item = (&'a V, (&'a V, T::UsePosition))>
62        + std::iter::ExactSizeIterator,
63    ) {
64        // Traverse the remapping in reverse order, as remappings can use the same variable more
65        // than once, and the whole usage is analyzed in reverse.
66        for (dst, (src, position)) in remapping.rev() {
67            let src = (*src).into();
68            let dst = (*dst).into();
69            if let Some(dest_next_usage_position) = self.vars.swap_remove(&dst) {
70                if let Some(next_usage_position) = self.vars.insert(src, dest_next_usage_position) {
71                    reporter.dup(position, src, next_usage_position);
72                } else {
73                    reporter.last_use(position, src);
74                }
75            } else {
76                reporter.unused_mapped_var(dst);
77            }
78        }
79    }
80
81    /// Updates the demand when some variables are used right before the current flow.
82    pub fn variables_used<
83        'a,
84        V: Copy + Into<Var> + 'a,
85        T: DemandReporter<Var, Aux, UsePosition = UsePosition>,
86    >(
87        &mut self,
88        reporter: &mut T,
89        vars: impl std::iter::DoubleEndedIterator<Item = (&'a V, T::UsePosition)>
90        + std::iter::ExactSizeIterator,
91    ) {
92        for (var, position) in vars.rev() {
93            let var = (*var).into();
94            if let Some(next_usage_position) = self.vars.insert(var, position) {
95                // Variable already used. If it's not dup, that is an issue.
96                reporter.dup(position, var, next_usage_position);
97            } else {
98                reporter.last_use(position, var);
99            }
100        }
101    }
102
103    /// Updates the demand when some variables are introduced right before the current flow.
104    pub fn variables_introduced<V: Copy + Into<Var>, T: DemandReporter<Var, Aux>>(
105        &mut self,
106        reporter: &mut T,
107        vars: &[V],
108        position: T::IntroducePosition,
109    ) {
110        for var in vars {
111            if self.vars.swap_remove(&(*var).into()).is_none() {
112                // Variable introduced, but not demanded. If it's not drop, that is an issue.
113                reporter.drop_aux(position, (*var).into(), self.aux.clone());
114            }
115        }
116    }
117
118    /// Merges [Demand]s from multiple branches into one, reporting diagnostics in the way.
119    pub fn merge_demands<T: DemandReporter<Var, Aux>>(
120        demands: &[(Self, T::IntroducePosition)],
121        reporter: &mut T,
122    ) -> Self {
123        // Union demands.
124        let mut vars = OrderedHashMap::default();
125        for (arm_demand, _) in demands {
126            vars.extend(arm_demand.vars.iter().map(|(var, position)| (*var, *position)));
127        }
128        let demand = Self { vars, aux: Aux::merge(demands.iter().map(|(d, _)| &d.aux)) };
129        // Check each var.
130        for var in demand.vars.keys() {
131            for (arm_demand, position) in demands {
132                if !arm_demand.vars.contains_key(var) {
133                    // Variable demanded only on some branches. It should be dropped in other.
134                    // If it's not drop, that is an issue.
135                    reporter.drop_aux(*position, *var, arm_demand.aux.clone());
136                }
137            }
138        }
139        demand
140    }
141}
142
143pub trait AuxCombine {
144    fn merge<'a, I: Iterator<Item = &'a Self>>(iter: I) -> Self
145    where
146        Self: 'a;
147}
148
149impl AuxCombine for () {
150    fn merge<'a, I: Iterator<Item = &'a Self>>(_: I) -> Self {}
151}
cairo_lang_lowering/borrow_check/demand.rs

cairo_lang_lowering/borrow_check/
demand.rs
