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 updates 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            if let Some(next_usage_position) = self.vars.insert((*var).into(), position) {
94                // Variable already used. If it's not dup, that is an issue.
95                reporter.dup(position, (*var).into(), next_usage_position);
96            } else {
97                reporter.last_use(position, (*var).into());
98            }
99        }
100    }
101
102    /// Updates the demand when some variables are introduced right before the current flow.
103    pub fn variables_introduced<V: Copy + Into<Var>, T: DemandReporter<Var, Aux>>(
104        &mut self,
105        reporter: &mut T,
106        vars: &[V],
107        position: T::IntroducePosition,
108    ) {
109        for var in vars {
110            if self.vars.swap_remove(&(*var).into()).is_none() {
111                // Variable introduced, but not demanded. If it's not drop, that is an issue.
112                reporter.drop_aux(position, (*var).into(), self.aux.clone());
113            }
114        }
115    }
116
117    /// Merges [Demand]s from multiple branches into one, reporting diagnostics in the way.
118    pub fn merge_demands<T: DemandReporter<Var, Aux>>(
119        demands: &[(Self, T::IntroducePosition)],
120        reporter: &mut T,
121    ) -> Self {
122        // Union demands.
123        let mut vars = OrderedHashMap::default();
124        for (arm_demand, _) in demands {
125            vars.extend(arm_demand.vars.iter().map(|(var, position)| (*var, *position)));
126        }
127        let demand = Self { vars, aux: Aux::merge(demands.iter().map(|(d, _)| &d.aux)) };
128        // Check each var.
129        for var in demand.vars.keys() {
130            for (arm_demand, position) in demands {
131                if !arm_demand.vars.contains_key(var) {
132                    // Variable demanded only on some branches. It should be dropped in other.
133                    // If it's not drop, that is an issue.
134                    reporter.drop_aux(*position, *var, arm_demand.aux.clone());
135                }
136            }
137        }
138        demand
139    }
140}
141
142pub trait AuxCombine {
143    fn merge<'a, I: Iterator<Item = &'a Self>>(iter: I) -> Self
144    where
145        Self: 'a;
146}
147
148impl AuxCombine for () {
149    fn merge<'a, I: Iterator<Item = &'a Self>>(_: I) -> Self {}
150}
cairo_lang_lowering/borrow_check/demand.rs

cairo_lang_lowering/borrow_check/
demand.rs
