refactor occurs check into a folder

[nikomatsakis]

The occurs check code in src/solve/infer/unify.rs (specifically, the methods defined on OccursCheck) follows a very folder-like pattern. Unfortunately, it can't quite use the Folder trait (as defined in fold.rs) because that trait only contains "callback methods" for processing free lifetime/type/krate variables. The occurs check needs to be able intercept all types, at least, as well as names that live in a universe and a few other things. We could add callback methods for those things to Folder.

I imagine the resulting trait would look like:

pub trait Folder {
    // Methods today:
    fn fold_free_var(&mut self, depth: usize, binders: usize) -> Result<Ty>;
    fn fold_free_lifetime_var(&mut self, depth: usize, binders: usize) -> Result<Lifetime>;
    fn fold_free_krate_var(&mut self, depth: usize, binders: usize) -> Result<Krate>;

    // Methods we need:
    fn fold_ty(&mut self, ty: &Ty, binders: usize) -> Result<Ty>;
    fn fold_lifetime(&mut self, lifetime: &Lifetime, binders: usize) -> Result<Lifetime>;
}

One thing that I'm not crazy about is that fold_ty invokes fold_free_var etc, at least in its default incarnation, so putting them into the same trait might mean that if you override fold_ty you would not need the other methods. So it might be better to have Folder just include the higher-level methods (e.g., fold_ty) and then have a new trait VarFolder where we define a bridge impl like impl<T: VarFolder> Folder for T. Or something like that.

[fabric-and-ink]

Working on it.

[nikomatsakis]

@fabric-and-ink cool, feel free to come to gitter channel with questions, if any arise

[fabric-and-ink]

Slow but steady progress... :)

[fabric-and-ink]

I followed your suggestion to implement a bridge trait. Now I am stuck at connecting both kinds of folders at this point:

    fn fold_lifetime(&mut self, lifetime: &Lifetime, binders: usize) -> Result<Lifetime> {
        match *lifetime {
            Lifetime::Var(ref var) => self.fold_free_lifetime_var(*var, binders),
            Lifetime::ForAll(universe_index) => {
                unimplemented!();
            },
        }
    }

I don't know what a universe is in this context (see #51) and therefore don't now how to proceed. Any hints? :)

[nikomatsakis]

@fabric-and-ink sorry, missed these comments! Maybe post your branch somewhere I can see it?

[fabric-and-ink]

There you go: https://github.com/fabric-and-ink/chalk/commit/649689f2c5843a59ef941316e11641de78c6be13

Nevermind, I got it. 🤦‍

[fabric-and-ink]

Replaced the old Folder trait (now FolderVar) with the new Folder. Now I am at this point. The "bridge" impl and the impl for Folder + ?Sized ... are in conflict. But the second impl is necessary to make for example this work.

[fabric-and-ink]

@nikomatsakis any hints on how to solve the trait conflict? (See last comment.)

[scalexm]

@fabric-and-ink niko is not extremely available right now, but I'll try to help you soon :)

[scalexm]

@fabric-and-ink How about:

pub struct FolderRef<'f, F> where F: 'f + ?Sized {
    folder: &'f mut F,
}

impl<'f, F: ?Sized> FolderRef<'f, F> {
    pub fn new(folder: &'f mut F) -> Self {
        FolderRef {
            folder,
        }
    }
}

impl<'f, F: Folder + ?Sized> Folder for FolderRef<'f, F> {
    fn fold_ty(&mut self, ty: &Ty, binders: usize) -> Result<Ty> {
        self.folder.fold_ty(ty, binders)
    }

    fn fold_lifetime(&mut self, lifetime: &Lifetime, binders: usize) -> Result<Lifetime> {
        self.folder.fold_lifetime(lifetime, binders)
    }
}

and then you use it like that:

impl<T: Fold> Fold for Shifted<T> {
    type Result = T::Result;

    fn fold_with(&self, folder: &mut Folder, binders: usize) -> Result<Self::Result> {
        // I... think this is right if binders is not zero, but not sure,
        // and don't care to think about it.
        assert_eq!(binders, 0);

        // First up-shift any variables. i.e., if `self.value`
        // contains a free var with index 0, and `self.adjustment ==
        // 2`, we will translate it to a free var with index 2; then
        // we will fold *that* through `folder`.
        let mut new_folder = (Shifter::new(self.adjustment), FolderRef::new(folder));
        self.value.fold_with(&mut new_folder, binders)
    }
}

With that I think you should be good :)

[fabric-and-ink]

Nice! Thank you! That worked well :)