rusttyc/
constraint_graph.rs

1use crate::{
2    types::{Arity, Constructable, ContextSensitiveVariant, Partial, Preliminary, PreliminaryTypeTable, TypeTable},
3    TcErr, TcKey,
4};
5use std::collections::{HashMap, HashSet};
6
7#[derive(Debug, Clone)]
8pub(crate) struct ConstraintGraph<T: ContextSensitiveVariant> {
9    vertices: Vec<Vertex<T>>,
10}
11
12#[derive(Debug, Clone)]
13enum Vertex<T: ContextSensitiveVariant> {
14    /// Represents a former vertex that was unified with another one and not chosen to be the representative.
15    Fwd { this: TcKey, repr: TcKey },
16    /// Represents a full vertex.
17    Repr(FullVertex<T>),
18}
19
20impl<T: ContextSensitiveVariant> Vertex<T> {
21    fn this(&self) -> TcKey {
22        match self {
23            Vertex::Fwd { this, .. } => *this,
24            Vertex::Repr(fv) => fv.this,
25        }
26    }
27
28    /// Grants mutable access to the underlying full vertex.
29    /// # Panics
30    /// Panics if `self` is not a full vertex.
31    fn mut_full(&mut self) -> &mut FullVertex<T> {
32        match self {
33            Vertex::Fwd { .. } => panic!("That's not a rep!!"),
34            Vertex::Repr(vf) => vf,
35        }
36    }
37
38    /// Grants immutable access to the underlying full vertex.
39    /// # Panics
40    /// Panics if `self` is not a full vertex.
41    fn full(&self) -> &FullVertex<T> {
42        match self {
43            Vertex::Fwd { .. } => panic!("That's not a rep!!"),
44            Vertex::Repr(vf) => vf,
45        }
46    }
47
48    /// Returns the reference of the vertex representing this one.  Returns None if this vertex represents itself.
49    fn get_repr_nontrans(&self) -> Option<TcKey> {
50        match self {
51            Vertex::Fwd { repr, .. } => Some(*repr),
52            Vertex::Repr(_) => None,
53        }
54    }
55}
56
57#[derive(Debug, Clone)]
58struct FullVertex<T: ContextSensitiveVariant> {
59    this: TcKey,
60    ty: Type<T>,
61}
62
63#[derive(Debug, Clone, PartialEq, Eq)]
64struct Type<V: ContextSensitiveVariant> {
65    variant: V,
66    children: Vec<Option<TcKey>>,
67    upper_bounds: HashSet<TcKey>,
68}
69
70type EquateObligation = Vec<(TcKey, TcKey)>;
71type OptEquateObligation = Vec<Option<(TcKey, TcKey)>>;
72impl<V: ContextSensitiveVariant> Type<V> {
73    fn top() -> Self {
74        Type { variant: V::top(), children: Vec::new(), upper_bounds: HashSet::new() }
75    }
76
77    fn equal(this: &Self, that: &Self, ctx: &V::Context) -> bool {
78        V::equal(&this.variant, &that.variant, ctx)
79            && this.children == that.children
80            && this.upper_bounds == that.upper_bounds
81    }
82
83    fn set_arity_checked(&mut self, this: TcKey, new_arity: usize, ctx: &V::Context) -> Result<(), TcErr<V>> {
84        match self.variant.arity(ctx) {
85            Arity::Fixed(given_arity) if new_arity > given_arity => {
86                return Err(TcErr::ChildAccessOutOfBound(this, self.variant.clone(), new_arity))
87            }
88            Arity::Fixed(given_arity) => ConstraintGraph::<V>::fill_with(&mut self.children, None, given_arity),
89            Arity::Variable => ConstraintGraph::<V>::fill_with(&mut self.children, None, new_arity),
90        }
91        Ok(())
92    }
93
94    fn set_arity_unchecked(&mut self, new_arity: usize) {
95        ConstraintGraph::<V>::fill_with(&mut self.children, None, new_arity);
96    }
97
98    fn child(&self, n: usize) -> Option<TcKey> {
99        debug_assert!(self.children.len() > n);
100        self.children[n]
101    }
102
103    fn set_child(&mut self, n: usize, child: TcKey) {
104        debug_assert!(self.children.len() > n);
105        self.children[n] = Some(child);
106    }
107
108    fn add_upper_bound(&mut self, bound: TcKey) {
109        let _ = self.upper_bounds.insert(bound);
110    }
111
112    fn meet(
113        &mut self,
114        this: TcKey,
115        target_key: TcKey,
116        rhs: &Self,
117        ctx: &V::Context,
118    ) -> Result<EquateObligation, TcErr<V>> {
119        // TODO: Extremely inefficient; improve.
120        let lhs = self;
121        let left_arity = lhs.children.len();
122        let right_arity = rhs.children.len();
123
124        debug_assert!(lhs.variant.arity(ctx).to_opt().map(|a| a == left_arity).unwrap_or(true));
125        debug_assert!(rhs.variant.arity(ctx).to_opt().map(|a| a == right_arity).unwrap_or(true));
126
127        // println!("Meeting {:?} and {:?}.", lhs, rhs);
128
129        let left = Partial { variant: lhs.variant.clone(), least_arity: left_arity };
130        let right = Partial { variant: rhs.variant.clone(), least_arity: right_arity };
131        let Partial { variant: new_variant, least_arity } =
132            ContextSensitiveVariant::meet(left, right, ctx).map_err(|e| TcErr::Bound(this, Some(target_key), e))?;
133
134        // Make child arrays same length.
135        ConstraintGraph::<V>::fill_with(&mut lhs.children, None, right_arity); // Will be checked later.
136
137        let (mut equates, new_children): (OptEquateObligation, Vec<Option<TcKey>>) = lhs
138            .children
139            .iter()
140            .zip(rhs.children.iter().chain(std::iter::repeat(&None)))
141            .map(|(a, b)| (a.zip(*b), a.or(*b)))
142            .unzip();
143
144        let equates: EquateObligation = equates.drain(..).flatten().collect();
145
146        // commit changes
147        lhs.variant = new_variant;
148        lhs.children = new_children;
149        lhs.upper_bounds.extend(rhs.upper_bounds.iter());
150        lhs.set_arity_checked(target_key, least_arity, ctx)?;
151
152        // println!("Result: {:?}", lhs);
153
154        debug_assert!(lhs.variant.arity(ctx).to_opt().map(|a| a == lhs.children.len()).unwrap_or(true));
155
156        Ok(equates)
157    }
158
159    fn to_partial(&self) -> Partial<V> {
160        Partial { variant: self.variant.clone(), least_arity: self.children.len() }
161    }
162
163    fn with_partial(&mut self, this: TcKey, p: Partial<V>, ctx: &V::Context) -> Result<(), TcErr<V>> {
164        let Partial { variant, least_arity } = p;
165        match variant.arity(ctx) {
166            Arity::Variable => {
167                self.variant = variant;
168                self.set_arity_unchecked(least_arity); // set_arity increases or is no-op.
169                Ok(())
170            }
171            Arity::Fixed(arity) => {
172                assert_eq!(
173                    arity, least_arity,
174                    "meet of two variants yielded fixed-arity variant that did not match least arity."
175                );
176                if self.children.len() > arity {
177                    return Err(TcErr::ArityMismatch {
178                        key: this,
179                        variant,
180                        inferred_arity: self.children.len(),
181                        reported_arity: least_arity,
182                    });
183                }
184                self.variant = variant;
185                self.set_arity_unchecked(least_arity); // set_arity increases or is no-op.
186                debug_assert!(self.variant.arity(ctx).to_opt().map(|a| a == self.children.len()).unwrap_or(true));
187                Ok(())
188            }
189        }
190    }
191
192    fn to_preliminary(&self) -> Preliminary<V> {
193        Preliminary { variant: self.variant.clone(), children: self.children.clone() }
194    }
195}
196
197impl<T: ContextSensitiveVariant> Vertex<T> {
198    /// Creates a full vertex without information regarding its children.
199    fn new_niladic(this: TcKey) -> Vertex<T> {
200        Vertex::Repr(FullVertex { this, ty: Type::top() })
201    }
202}
203
204impl<T: ContextSensitiveVariant> ConstraintGraph<T> {
205    /// Creates an empty constraint graph.
206    pub(crate) fn new() -> Self {
207        ConstraintGraph { vertices: Vec::new() }
208    }
209
210    /// Create an iterator over all keys currently registered in the graph.
211    pub(crate) fn all_keys(&self) -> impl Iterator<Item = TcKey> + '_ {
212        self.vertices.iter().map(|v| v.this())
213    }
214
215    /// Creates and registers a new vertex.
216    pub(crate) fn create_vertex(&mut self) -> TcKey {
217        self.new_vertex().this()
218    }
219
220    fn new_vertex(&mut self) -> &mut Vertex<T> {
221        let key = TcKey::new(self.vertices.len());
222        let v = Vertex::new_niladic(key);
223        self.vertices.push(v);
224        self.vertices.last_mut().unwrap() // we just pushed it onto the vec.
225    }
226
227    /// Registers that a key has at least `n` children.  If this fact was already known and thus a key is already associated with the child,
228    /// the key is returned without calling the `keygen` function.  Otherwise, `keygen` generates a new key which will be added to the graph regularly,
229    /// associated with the child, and returned.
230    /// If the addition of the child reveals a contradiction, an Err is returned.  An Ok does _not_ indicate the absence of a contradiction.
231    pub(crate) fn nth_child(&mut self, parent: TcKey, n: usize, context: &T::Context) -> Result<TcKey, TcErr<T>> {
232        let parent_v = self.repr_mut(parent);
233        parent_v.ty.set_arity_checked(parent, n + 1, context)?; // n is an index, we want an arity of n+1
234        let nth_child = parent_v.ty.child(n);
235        if let Some(child) = nth_child {
236            return Ok(child);
237        }
238        let child_key = self.create_vertex();
239        self.repr_mut(parent).ty.set_child(n, child_key);
240        Ok(child_key)
241    }
242
243    /// Declares an asymmetric relation between two keys.
244    pub(crate) fn add_upper_bound(&mut self, target: TcKey, bound: TcKey) {
245        let bound = self.repr(bound).this;
246        self.repr_mut(target).ty.add_upper_bound(bound)
247    }
248
249    /// Declares a symmetric relation between two keys.
250    pub(crate) fn equate(&mut self, left: TcKey, right: TcKey, context: &T::Context) -> Result<(), TcErr<T>> {
251        let left = self.repr(left).this;
252        let right = self.repr(right).this;
253        let (rep, sub) = if left < right { (left, right) } else { (right, left) };
254        self.establish_fwd(sub, rep, context)
255    }
256
257    /// Imposes an explicit bound on a key.  An Err return indicates a contradiction, an Ok does not indicate the absence of a contradiction.
258    pub(crate) fn explicit_bound(&mut self, target: TcKey, bound: T, context: &T::Context) -> Result<(), TcErr<T>> {
259        self.add_explicit_bound(target, bound, context).map(|_| ())
260    }
261
262    // INTERNAL HELPER FUNCTIONS
263
264    /// Transforms `sub` into a forward to `repr`.
265    fn establish_fwd(&mut self, sub: TcKey, repr: TcKey, context: &T::Context) -> Result<(), TcErr<T>> {
266        if sub == repr {
267            // sub and repr are already in the same eq class since we started
268            // out with the identity relation;  nothing to do.
269            return Ok(());
270        }
271        debug_assert_eq!(sub, self.repr(sub).this, "cannot establish a forward for a vertex that already is a forward");
272        let mut new_fwd = Vertex::Fwd { this: sub, repr };
273        // Replace `sub` vertex with new_fwd.
274        std::mem::swap(self.vertex_mut(sub), &mut new_fwd);
275
276        let sub_v = new_fwd.full(); // We asserted it to be a full vertex.
277        let repr_v = self.repr_mut(repr);
278        // Meet-Alternative: let repr_v = self.repr(repr);
279
280        let equates = repr_v.ty.meet(repr, sub, &sub_v.ty, context)?;
281        // Meet-Alternative: let (new_ty, equates) = repr_v.ty.meet(repr, &sub_v.ty)?;
282        equates.into_iter().try_for_each(|(a, b)| self.equate(a, b, context))?;
283
284        // Meet-Alternative: self.repr_mut(repr).ty = new_ty;
285        Ok(())
286    }
287
288    pub(crate) fn lift(&mut self, variant: T, children: Vec<Option<TcKey>>) -> TcKey {
289        let v = self.new_vertex().mut_full();
290        v.ty.variant = variant;
291        v.ty.children = children;
292        v.this
293    }
294
295    fn add_explicit_bound(&mut self, target: TcKey, bound: T, context: &T::Context) -> Result<(), TcErr<T>> {
296        let target_v = self.repr_mut(target);
297        let lhs = target_v.ty.to_partial();
298        let rhs_arity = bound.arity(context).to_opt().unwrap_or(0);
299        let rhs = Partial { variant: bound, least_arity: rhs_arity };
300        let meet = T::meet(lhs, rhs, context).map_err(|e| TcErr::Bound(target, None, e))?;
301        target_v.ty.with_partial(target, meet, context)
302    }
303
304    // ACCESS LOGIC
305
306    fn vertex(&self, key: TcKey) -> &Vertex<T> {
307        &self.vertices[key.ix]
308    }
309
310    fn vertex_mut(&mut self, key: TcKey) -> &mut Vertex<T> {
311        &mut self.vertices[key.ix]
312    }
313
314    fn repr_mut(&mut self, v: TcKey) -> &mut FullVertex<T> {
315        match self.vertex(v).get_repr_nontrans() {
316            Some(next) => self.repr_mut(next),
317            None => self.vertex_mut(v).mut_full(),
318        }
319    }
320
321    /// Returns an Iterator over all full vertices in `self`.  This does not resolve forwards, thus every representative only occurs once.
322    fn reprs(&self) -> impl Iterator<Item = &FullVertex<T>> {
323        self.vertices.iter().filter_map(|v| match v {
324            Vertex::Fwd { .. } => None,
325            Vertex::Repr(fv) => Some(fv),
326        })
327    }
328
329    fn repr(&self, v: TcKey) -> &FullVertex<T> {
330        match &self.vertex(v) {
331            Vertex::Repr(fv) => fv,
332            Vertex::Fwd { repr, .. } => self.repr(*repr),
333        }
334    }
335
336    /// Adds `entry` to `v` until it has length `size`.
337    fn fill_with<X: Clone>(v: &mut Vec<X>, entry: X, size: usize) {
338        let diff = size.saturating_sub(v.len());
339        v.extend(vec![entry; diff]);
340    }
341}
342
343impl<T: ContextSensitiveVariant> ConstraintGraph<T> {
344    /// Starts a fix point computation successively checking and resolving constraints captured in the graph.  
345    /// Returns the type table mapping each registered key to a type if no contradiction occurs.
346    fn solve_constraints(&mut self, context: T::Context) -> Result<(), TcErr<T>> {
347        if self.is_cyclic() {
348            return Err(TcErr::CyclicGraph);
349        }
350        let mut change = true;
351        while change {
352            change = false;
353            change |= self.resolve_asymmetric(&context)?;
354        }
355        Ok(())
356    }
357
358    pub(crate) fn solve_preliminary(mut self, context: T::Context) -> Result<PreliminaryTypeTable<T>, TcErr<T>> {
359        self.solve_constraints(context)?;
360        Ok(self.construct_preliminary())
361    }
362
363    fn construct_preliminary(self) -> PreliminaryTypeTable<T> {
364        self.vertices
365            .iter()
366            .map(|v| v.this())
367            .collect::<Vec<TcKey>>()
368            .into_iter()
369            .map(|key| (key, self.repr(key).ty.to_preliminary()))
370            .collect()
371    }
372
373    /// Meets all the types of upper bounds with the type of the vertex itself.
374    fn resolve_asymmetric(&mut self, context: &T::Context) -> Result<bool, TcErr<T>> {
375        self.vertices
376            .iter()
377            .map(Vertex::this)
378            .collect::<Vec<TcKey>>()
379            .into_iter()
380            .map(|key| {
381                let vertex = self.repr(key);
382                let initial: (Type<T>, EquateObligation) = (vertex.ty.clone(), Vec::new());
383                let (new_type, equates) =
384                    vertex.ty.upper_bounds.iter().map(|b| (&self.repr(*b).ty, *b)).fold(Ok(initial), |lhs, rhs| {
385                        let (mut old_ty, mut equates) = lhs?;
386                        let (rhs, partner_key) = rhs;
387                        let new_equates = old_ty.meet(key, partner_key, rhs, context)?;
388                        // Meet-Alternative:
389                        // let (old_ty, mut equates) = lhs?;
390                        // let (new_ty, new_equates) = old_ty.meet(key, rhs)?;
391                        equates.extend(new_equates);
392                        // Meet-Alternative: Ok((new_ty, equates))
393                        Ok((old_ty, equates))
394                    })?;
395                let change = !Type::equal(&vertex.ty, &new_type, context);
396                self.repr_mut(key).ty = new_type;
397                equates.into_iter().try_for_each(|(k1, k2)| self.equate(k1, k2, context))?;
398                Ok(change)
399            })
400            .collect::<Result<Vec<bool>, TcErr<T>>>()
401            .map(|changes| changes.into_iter().any(|b| b))
402    }
403
404    #[must_use]
405    fn is_cyclic(&self) -> bool {
406        self.vertices.iter().any(|v| self.is_in_loop(v, vec![]))
407    }
408
409    fn is_in_loop(&self, vertex: &Vertex<T>, mut history: Vec<TcKey>) -> bool {
410        match *vertex {
411            Vertex::Fwd { this, repr } => {
412                if history.contains(&this) {
413                    return true;
414                } else {
415                    history.push(this);
416                    return self.is_in_loop(self.vertex(repr), history);
417                }
418            }
419            Vertex::Repr(FullVertex { this, .. }) => return history.contains(&this),
420        }
421    }
422}
423
424impl<V> ConstraintGraph<V>
425where
426    V: Constructable,
427{
428    pub(crate) fn solve(mut self, context: V::Context) -> Result<TypeTable<V>, TcErr<V>> {
429        self.solve_constraints(context)?;
430        self.construct_types()
431    }
432
433    fn construct_types(self) -> Result<TypeTable<V>, TcErr<V>> {
434        let mut resolved: HashMap<TcKey, V::Type> = HashMap::new();
435        let mut open: Vec<&FullVertex<V>> = self.reprs().collect();
436        loop {
437            let mut still_open = Vec::with_capacity(open.len());
438            // println!("Resolved: {:?}", resolved);
439            // println!("Open: {:?}", open.iter().map(|d| d.this).collect::<Vec<TcKey>>());
440            let num_open = open.len();
441            for v in open {
442                let children =
443                    v.ty.children
444                        .iter()
445                        .enumerate()
446                        .map(|(ix, c)| {
447                            if let Some(key) = c {
448                                Ok(resolved.get(&self.repr(*key).this).cloned())
449                            } else {
450                                V::construct(&V::top(), &Vec::new())
451                                    .map(Some)
452                                    .map_err(|e| TcErr::ChildConstruction(v.this, ix, v.ty.to_preliminary(), e))
453                            }
454                        })
455                        .collect::<Result<Option<Vec<V::Type>>, TcErr<V>>>()?;
456                if let Some(children) = children {
457                    let ty =
458                        v.ty.variant
459                            .construct(&children)
460                            .map_err(|e| TcErr::Construction(v.this, v.ty.to_preliminary(), e))?;
461                    let _ = resolved.insert(v.this, ty);
462                } else {
463                    still_open.push(v)
464                }
465            }
466            if still_open.is_empty() {
467                break;
468            }
469            if still_open.len() == num_open {
470                panic!("How tf does this diverge?!");
471            }
472            open = still_open;
473        }
474        Ok(self.vertices.iter().map(|v| (v.this(), resolved[&self.repr(v.this()).this].clone())).collect())
475    }
476}
rusttyc/constraint_graph.rs

rusttyc/
constraint_graph.rs
