chalk_ir/
zip.rs

1//! Traits for "zipping" types, walking through two structures and checking that they match.
2
3use crate::fold::TypeFoldable;
4use crate::*;
5use std::fmt::Debug;
6use std::sync::Arc;
7
8/// When we zip types, we basically traverse the structure, ensuring
9/// that it matches.  When we come to types/lifetimes, we invoke the
10/// callback methods in the zipper to match them up. Primarily used
11/// during unification or similar operations.
12///
13/// So e.g. if you had `A: Eq<B>` zipped with `X: Eq<Y>`, then the zipper
14/// would get two callbacks, one pairing `A` and `X`, and the other pairing
15/// `B` and `Y`.
16///
17/// For things other than types/lifetimes, the zip impls will
18/// guarantee equality. So e.g. if you have `A: Eq<B>` zipped with `X:
19/// Ord<Y>`, you would wind up with an error, no matter what zipper
20/// you are using. This is because the traits `Eq` and `Ord` are
21/// represented by two distinct `ItemId` values, and the impl for
22/// `ItemId` requires that all `ItemId` in the two zipped values match
23/// up.
24pub trait Zipper<I: Interner> {
25    /// Indicates that the two types `a` and `b` were found in matching spots.
26    fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()>;
27
28    /// Indicates that the two lifetimes `a` and `b` were found in matching spots.
29    fn zip_lifetimes(
30        &mut self,
31        variance: Variance,
32        a: &Lifetime<I>,
33        b: &Lifetime<I>,
34    ) -> Fallible<()>;
35
36    /// Indicates that the two consts `a` and `b` were found in matching spots.
37    fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()>;
38
39    /// Zips two values appearing beneath binders.
40    fn zip_binders<T>(
41        &mut self,
42        variance: Variance,
43        a: &Binders<T>,
44        b: &Binders<T>,
45    ) -> Fallible<()>
46    where
47        T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>;
48
49    /// Zips two substs
50    fn zip_substs(
51        &mut self,
52        ambient: Variance,
53        variances: Option<Variances<I>>,
54        a: &[GenericArg<I>],
55        b: &[GenericArg<I>],
56    ) -> Fallible<()>
57    where
58        Self: Sized,
59    {
60        for (i, (a, b)) in a.iter().zip(b.iter()).enumerate() {
61            let variance = variances
62                .as_ref()
63                .map(|v| v.as_slice(self.interner())[i])
64                .unwrap_or(Variance::Invariant);
65            Zip::zip_with(self, ambient.xform(variance), a, b)?;
66        }
67        Ok(())
68    }
69
70    /// Retrieves the interner from the underlying zipper object
71    fn interner(&self) -> I;
72
73    /// Retrieves the `UnificationDatabase` from the underlying zipper object
74    fn unification_database(&self) -> &dyn UnificationDatabase<I>;
75}
76
77impl<'f, Z, I> Zipper<I> for &'f mut Z
78where
79    I: Interner,
80    Z: Zipper<I>,
81{
82    fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
83        (**self).zip_tys(variance, a, b)
84    }
85
86    fn zip_lifetimes(
87        &mut self,
88        variance: Variance,
89        a: &Lifetime<I>,
90        b: &Lifetime<I>,
91    ) -> Fallible<()> {
92        (**self).zip_lifetimes(variance, a, b)
93    }
94
95    fn zip_consts(&mut self, variance: Variance, a: &Const<I>, b: &Const<I>) -> Fallible<()> {
96        (**self).zip_consts(variance, a, b)
97    }
98
99    fn zip_binders<T>(&mut self, variance: Variance, a: &Binders<T>, b: &Binders<T>) -> Fallible<()>
100    where
101        T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>,
102    {
103        (**self).zip_binders(variance, a, b)
104    }
105
106    fn interner(&self) -> I {
107        Z::interner(*self)
108    }
109
110    fn unification_database(&self) -> &dyn UnificationDatabase<I> {
111        (**self).unification_database()
112    }
113}
114
115/// The `Zip` trait walks two values, invoking the `Zipper` methods where
116/// appropriate, but otherwise requiring strict equality.
117///
118/// See `Zipper` trait for more details.
119///
120/// To implement the trait, typically you would use one of the macros
121/// like `eq_zip!`, `struct_zip!`, or `enum_zip!`.
122pub trait Zip<I>: Debug
123where
124    I: Interner,
125{
126    /// Uses the zipper to walk through two values, ensuring that they match.
127    fn zip_with<Z: Zipper<I>>(
128        zipper: &mut Z,
129        variance: Variance,
130        a: &Self,
131        b: &Self,
132    ) -> Fallible<()>;
133}
134
135impl<'a, T: ?Sized + Zip<I>, I: Interner> Zip<I> for &'a T {
136    fn zip_with<Z: Zipper<I>>(
137        zipper: &mut Z,
138        variance: Variance,
139        a: &Self,
140        b: &Self,
141    ) -> Fallible<()> {
142        <T as Zip<I>>::zip_with(zipper, variance, a, b)
143    }
144}
145
146impl<I: Interner> Zip<I> for () {
147    fn zip_with<Z: Zipper<I>>(_: &mut Z, _: Variance, _: &Self, _: &Self) -> Fallible<()> {
148        Ok(())
149    }
150}
151
152impl<T: Zip<I>, I: Interner> Zip<I> for Vec<T> {
153    fn zip_with<Z: Zipper<I>>(
154        zipper: &mut Z,
155        variance: Variance,
156        a: &Self,
157        b: &Self,
158    ) -> Fallible<()> {
159        <[T] as Zip<I>>::zip_with(zipper, variance, a, b)
160    }
161}
162
163impl<T: Zip<I>, I: Interner> Zip<I> for [T] {
164    fn zip_with<Z: Zipper<I>>(
165        zipper: &mut Z,
166        variance: Variance,
167        a: &Self,
168        b: &Self,
169    ) -> Fallible<()> {
170        if a.len() != b.len() {
171            return Err(NoSolution);
172        }
173
174        for (a_elem, b_elem) in a.iter().zip(b) {
175            Zip::zip_with(zipper, variance, a_elem, b_elem)?;
176        }
177
178        Ok(())
179    }
180}
181
182impl<T: Zip<I>, I: Interner> Zip<I> for Arc<T> {
183    fn zip_with<Z: Zipper<I>>(
184        zipper: &mut Z,
185        variance: Variance,
186        a: &Self,
187        b: &Self,
188    ) -> Fallible<()> {
189        <T as Zip<I>>::zip_with(zipper, variance, a, b)
190    }
191}
192
193impl<T: Zip<I>, I: Interner> Zip<I> for Box<T> {
194    fn zip_with<Z: Zipper<I>>(
195        zipper: &mut Z,
196        variance: Variance,
197        a: &Self,
198        b: &Self,
199    ) -> Fallible<()> {
200        <T as Zip<I>>::zip_with(zipper, variance, a, b)
201    }
202}
203
204impl<T: Zip<I>, U: Zip<I>, I: Interner> Zip<I> for (T, U) {
205    fn zip_with<Z: Zipper<I>>(
206        zipper: &mut Z,
207        variance: Variance,
208        a: &Self,
209        b: &Self,
210    ) -> Fallible<()> {
211        Zip::zip_with(zipper, variance, &a.0, &b.0)?;
212        Zip::zip_with(zipper, variance, &a.1, &b.1)?;
213        Ok(())
214    }
215}
216
217impl<I: Interner> Zip<I> for Ty<I> {
218    fn zip_with<Z: Zipper<I>>(
219        zipper: &mut Z,
220        variance: Variance,
221        a: &Self,
222        b: &Self,
223    ) -> Fallible<()> {
224        zipper.zip_tys(variance, a, b)
225    }
226}
227
228impl<I: Interner> Zip<I> for Lifetime<I> {
229    fn zip_with<Z: Zipper<I>>(
230        zipper: &mut Z,
231        variance: Variance,
232        a: &Self,
233        b: &Self,
234    ) -> Fallible<()> {
235        zipper.zip_lifetimes(variance, a, b)
236    }
237}
238
239impl<I: Interner> Zip<I> for Const<I> {
240    fn zip_with<Z: Zipper<I>>(
241        zipper: &mut Z,
242        variance: Variance,
243        a: &Self,
244        b: &Self,
245    ) -> Fallible<()> {
246        zipper.zip_consts(variance, a, b)
247    }
248}
249impl<I: Interner, T> Zip<I> for Binders<T>
250where
251    T: Clone + HasInterner<Interner = I> + Zip<I> + TypeFoldable<I>,
252{
253    fn zip_with<Z: Zipper<I>>(
254        zipper: &mut Z,
255        variance: Variance,
256        a: &Self,
257        b: &Self,
258    ) -> Fallible<()> {
259        zipper.zip_binders(variance, a, b)
260    }
261}
262
263/// Generates a Zip impl that requires the two values be
264/// equal. Suitable for atomic, scalar values.
265macro_rules! eq_zip {
266    ($I:ident => $t:ty) => {
267        impl<$I: Interner> Zip<$I> for $t {
268            fn zip_with<Z: Zipper<$I>>(
269                _zipper: &mut Z,
270                _variance: Variance,
271                a: &Self,
272                b: &Self,
273            ) -> Fallible<()> {
274                if a != b {
275                    return Err(NoSolution);
276                }
277                Ok(())
278            }
279        }
280    };
281}
282
283eq_zip!(I => AdtId<I>);
284eq_zip!(I => TraitId<I>);
285eq_zip!(I => AssocTypeId<I>);
286eq_zip!(I => OpaqueTyId<I>);
287eq_zip!(I => CoroutineId<I>);
288eq_zip!(I => ForeignDefId<I>);
289eq_zip!(I => FnDefId<I>);
290eq_zip!(I => ClosureId<I>);
291eq_zip!(I => QuantifierKind);
292eq_zip!(I => PhantomData<I>);
293eq_zip!(I => PlaceholderIndex);
294eq_zip!(I => ClausePriority);
295eq_zip!(I => Mutability);
296eq_zip!(I => Scalar);
297
298impl<T: HasInterner<Interner = I> + Zip<I>, I: Interner> Zip<I> for InEnvironment<T> {
299    fn zip_with<Z: Zipper<I>>(
300        zipper: &mut Z,
301        variance: Variance,
302        a: &Self,
303        b: &Self,
304    ) -> Fallible<()> {
305        Zip::zip_with(zipper, variance, &a.environment, &b.environment)?;
306        Zip::zip_with(zipper, variance, &a.goal, &b.goal)?;
307        Ok(())
308    }
309}
310
311impl<I: Interner> Zip<I> for Environment<I> {
312    fn zip_with<Z: Zipper<I>>(
313        zipper: &mut Z,
314        variance: Variance,
315        a: &Self,
316        b: &Self,
317    ) -> Fallible<()> {
318        let interner = zipper.interner();
319        assert_eq!(a.clauses.len(interner), b.clauses.len(interner)); // or different numbers of clauses
320        Zip::zip_with(
321            zipper,
322            variance,
323            a.clauses.as_slice(interner),
324            b.clauses.as_slice(interner),
325        )?;
326        Ok(())
327    }
328}
329
330impl<I: Interner> Zip<I> for Goals<I> {
331    fn zip_with<Z: Zipper<I>>(
332        zipper: &mut Z,
333        variance: Variance,
334        a: &Self,
335        b: &Self,
336    ) -> Fallible<()> {
337        let interner = zipper.interner();
338        Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?;
339        Ok(())
340    }
341}
342
343impl<I: Interner> Zip<I> for ProgramClauses<I> {
344    fn zip_with<Z: Zipper<I>>(
345        zipper: &mut Z,
346        variance: Variance,
347        a: &Self,
348        b: &Self,
349    ) -> Fallible<()> {
350        let interner = zipper.interner();
351        Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?;
352        Ok(())
353    }
354}
355
356impl<I: Interner> Zip<I> for Constraints<I> {
357    fn zip_with<Z: Zipper<I>>(
358        zipper: &mut Z,
359        variance: Variance,
360        a: &Self,
361        b: &Self,
362    ) -> Fallible<()> {
363        let interner = zipper.interner();
364        Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?;
365        Ok(())
366    }
367}
368
369impl<I: Interner> Zip<I> for QuantifiedWhereClauses<I> {
370    fn zip_with<Z: Zipper<I>>(
371        zipper: &mut Z,
372        variance: Variance,
373        a: &Self,
374        b: &Self,
375    ) -> Fallible<()> {
376        let interner = zipper.interner();
377        Zip::zip_with(zipper, variance, a.as_slice(interner), b.as_slice(interner))?;
378        Ok(())
379    }
380}
381
382// Annoyingly, Goal cannot use `enum_zip` because some variants have
383// two parameters, and I'm too lazy to make the macro account for the
384// relevant name mangling.
385impl<I: Interner> Zip<I> for Goal<I> {
386    fn zip_with<Z: Zipper<I>>(
387        zipper: &mut Z,
388        variance: Variance,
389        a: &Self,
390        b: &Self,
391    ) -> Fallible<()> {
392        let interner = zipper.interner();
393        Zip::zip_with(zipper, variance, a.data(interner), b.data(interner))
394    }
395}
396
397// I'm too lazy to make `enum_zip` support type parameters.
398impl<I: Interner> Zip<I> for VariableKind<I> {
399    fn zip_with<Z: Zipper<I>>(
400        zipper: &mut Z,
401        variance: Variance,
402        a: &Self,
403        b: &Self,
404    ) -> Fallible<()> {
405        match (a, b) {
406            (VariableKind::Ty(a), VariableKind::Ty(b)) if a == b => Ok(()),
407            (VariableKind::Lifetime, VariableKind::Lifetime) => Ok(()),
408            (VariableKind::Const(ty_a), VariableKind::Const(ty_b)) => {
409                Zip::zip_with(zipper, variance, ty_a, ty_b)
410            }
411            (VariableKind::Ty(_), _)
412            | (VariableKind::Lifetime, _)
413            | (VariableKind::Const(_), _) => panic!("zipping things of mixed kind"),
414        }
415    }
416}
417
418impl<I: Interner> Zip<I> for GenericArg<I> {
419    fn zip_with<Z: Zipper<I>>(
420        zipper: &mut Z,
421        variance: Variance,
422        a: &Self,
423        b: &Self,
424    ) -> Fallible<()> {
425        let interner = zipper.interner();
426        Zip::zip_with(zipper, variance, a.data(interner), b.data(interner))
427    }
428}
429
430impl<I: Interner> Zip<I> for ProgramClause<I> {
431    fn zip_with<Z: Zipper<I>>(
432        zipper: &mut Z,
433        variance: Variance,
434        a: &Self,
435        b: &Self,
436    ) -> Fallible<()> {
437        let interner = zipper.interner();
438        Zip::zip_with(zipper, variance, a.data(interner), b.data(interner))
439    }
440}
441
442impl<I: Interner> Zip<I> for TraitRef<I> {
443    fn zip_with<Z: Zipper<I>>(
444        zipper: &mut Z,
445        variance: Variance,
446        a: &Self,
447        b: &Self,
448    ) -> Fallible<()> {
449        let interner = zipper.interner();
450        Zip::zip_with(zipper, variance, &a.trait_id, &b.trait_id)?;
451        zipper.zip_substs(
452            variance,
453            None,
454            a.substitution.as_slice(interner),
455            b.substitution.as_slice(interner),
456        )
457    }
458}
459
460impl<I: Interner> Zip<I> for ProjectionTy<I> {
461    fn zip_with<Z: Zipper<I>>(
462        zipper: &mut Z,
463        variance: Variance,
464        a: &Self,
465        b: &Self,
466    ) -> Fallible<()> {
467        let interner = zipper.interner();
468        Zip::zip_with(zipper, variance, &a.associated_ty_id, &b.associated_ty_id)?;
469        zipper.zip_substs(
470            variance,
471            None,
472            a.substitution.as_slice(interner),
473            b.substitution.as_slice(interner),
474        )
475    }
476}
477
478impl<I: Interner> Zip<I> for OpaqueTy<I> {
479    fn zip_with<Z: Zipper<I>>(
480        zipper: &mut Z,
481        variance: Variance,
482        a: &Self,
483        b: &Self,
484    ) -> Fallible<()> {
485        let interner = zipper.interner();
486        Zip::zip_with(zipper, variance, &a.opaque_ty_id, &b.opaque_ty_id)?;
487        zipper.zip_substs(
488            variance,
489            None,
490            a.substitution.as_slice(interner),
491            b.substitution.as_slice(interner),
492        )
493    }
494}
495
496impl<I: Interner> Zip<I> for DynTy<I> {
497    fn zip_with<Z: Zipper<I>>(
498        zipper: &mut Z,
499        variance: Variance,
500        a: &Self,
501        b: &Self,
502    ) -> Fallible<()> {
503        Zip::zip_with(
504            zipper,
505            variance.xform(Variance::Invariant),
506            &a.bounds,
507            &b.bounds,
508        )?;
509        Zip::zip_with(
510            zipper,
511            variance.xform(Variance::Contravariant),
512            &a.lifetime,
513            &b.lifetime,
514        )?;
515        Ok(())
516    }
517}
518
519impl<I: Interner> Zip<I> for FnSubst<I> {
520    fn zip_with<Z: Zipper<I>>(
521        zipper: &mut Z,
522        variance: Variance,
523        a: &Self,
524        b: &Self,
525    ) -> Fallible<()> {
526        let interner = zipper.interner();
527        // Parameters
528        Zip::zip_with(
529            zipper,
530            variance.xform(Variance::Contravariant),
531            &a.0.as_slice(interner)[..a.0.len(interner) - 1],
532            &b.0.as_slice(interner)[..b.0.len(interner) - 1],
533        )?;
534        // Return type
535        Zip::zip_with(
536            zipper,
537            variance,
538            a.0.iter(interner).last().unwrap(),
539            b.0.iter(interner).last().unwrap(),
540        )?;
541        Ok(())
542    }
543}
chalk_ir/zip.rs

chalk_ir/
zip.rs
