# Higher-ranked trait bounds

One of the more subtle concepts in trait resolution is higher-ranked trait bounds. An example of such a bound is `for<'a> MyTrait<&'a isize>`. Let's walk through how selection on higher-ranked trait references works.

## Basic matching and placeholder leaks

Suppose we have a trait `Foo`:

``````
#![allow(unused_variables)]
fn main() {
trait Foo<X> {
fn foo(&self, x: X) { }
}
}
``````

Let's say we have a function `want_hrtb` that wants a type which implements `Foo<&'a isize>` for any `'a`:

``````fn want_hrtb<T>() where T : for<'a> Foo<&'a isize> { ... }
``````

Now we have a struct `AnyInt` that implements `Foo<&'a isize>` for any `'a`:

``````struct AnyInt;
impl<'a> Foo<&'a isize> for AnyInt { }
``````

And the question is, does `AnyInt : for<'a> Foo<&'a isize>`? We want the answer to be yes. The algorithm for figuring it out is closely related to the subtyping for higher-ranked types (which is described here and also in a paper by SPJ. If you wish to understand higher-ranked subtyping, we recommend you read the paper). There are a few parts:

1. Replace bound regions in the obligation with placeholders.
2. Match the impl against the placeholder obligation.
3. Check for placeholder leaks.

So let's work through our example.

1. The first thing we would do is to replace the bound region in the obligation with a placeholder, yielding `AnyInt : Foo<&'0 isize>` (here `'0` represents placeholder region #0). Note that we now have no quantifiers; in terms of the compiler type, this changes from a `ty::PolyTraitRef` to a `TraitRef`. We would then create the `TraitRef` from the impl, using fresh variables for it's bound regions (and thus getting `Foo<&'\$a isize>`, where `'\$a` is the inference variable for `'a`).

2. Next we relate the two trait refs, yielding a graph with the constraint that `'0 == '\$a`.

3. Finally, we check for placeholder "leaks" – a leak is basically any attempt to relate a placeholder region to another placeholder region, or to any region that pre-existed the impl match. The leak check is done by searching from the placeholder region to find the set of regions that it is related to in any way. This is called the "taint" set. To pass the check, that set must consist solely of itself and region variables from the impl. If the taint set includes any other region, then the match is a failure. In this case, the taint set for `'0` is `{'0, '\$a}`, and hence the check will succeed.

Let's consider a failure case. Imagine we also have a struct

``````struct StaticInt;
impl Foo<&'static isize> for StaticInt;
``````

We want the obligation `StaticInt : for<'a> Foo<&'a isize>` to be considered unsatisfied. The check begins just as before. `'a` is replaced with a placeholder `'0` and the impl trait reference is instantiated to `Foo<&'static isize>`. When we relate those two, we get a constraint like `'static == '0`. This means that the taint set for `'0` is `{'0, 'static}`, which fails the leak check.

TODO: This is because `'static` is not a region variable but is in the taint set, right?

## Higher-ranked trait obligations

Once the basic matching is done, we get to another interesting topic: how to deal with impl obligations. I'll work through a simple example here. Imagine we have the traits `Foo` and `Bar` and an associated impl:

``````
#![allow(unused_variables)]
fn main() {
trait Foo<X> {
fn foo(&self, x: X) { }
}

trait Bar<X> {
fn bar(&self, x: X) { }
}

impl<X,F> Foo<X> for F
where F : Bar<X>
{
}
}
``````

Now let's say we have a obligation `Baz: for<'a> Foo<&'a isize>` and we match this impl. What obligation is generated as a result? We want to get `Baz: for<'a> Bar<&'a isize>`, but how does that happen?

After the matching, we are in a position where we have a placeholder substitution like `X => &'0 isize`. If we apply this substitution to the impl obligations, we get `F : Bar<&'0 isize>`. Obviously this is not directly usable because the placeholder region `'0` cannot leak out of our computation.

What we do is to create an inverse mapping from the taint set of `'0` back to the original bound region (`'a`, here) that `'0` resulted from. (This is done in `higher_ranked::plug_leaks`). We know that the leak check passed, so this taint set consists solely of the placeholder region itself plus various intermediate region variables. We then walk the trait-reference and convert every region in that taint set back to a late-bound region, so in this case we'd wind up with `Baz: for<'a> Bar<&'a isize>`.