Implement GATs

[scalexm]

Step 1

The grammar needs to be extended to support bounds and (quantified) where clauses on associated types like in:

trait Foo {
    type Item<'a, T>: Clone where Self: Sized;
}

The grammar is located parser.lalrpop, and the AST in ast.rs.

When this is done, this item:

chalk/chalk-parse/src/parser.lalrpop

Lines 204 to 207 in eeb2182

	WhereClauses: Vec<WhereClause> = {
	"where" <Comma<WhereClause>>,
	() => vec![],
	};

won't be needed anymore because we will be using QuantifiedWhereClauses everywhere.

We would also remove where clauses on associated type values because they are useless:

chalk/chalk-parse/src/parser.lalrpop

Lines 104 to 111 in eeb2182

	AssocTyValue: AssocTyValue = {
	"type" <n:Id> <a:Angle<ParameterKind>> <wc:WhereClauses> "=" <v:Ty> ";" => AssocTyValue {
	name: n,
	parameter_kinds: a,
	value: v,
	where_clauses: wc,
	},
	};

Step 2

Currently, a where clause of the form where T: Foo<Item = U> translated to a single domain goal ProjectionEq(<T as Foo>::Item = U). We would need this clause to be translated to two distinct domain goals:

• ProjectionEq(<T as Foo>::Item = U) as before
• Implemented(T: Foo)

Currently, we cannot translate one AST where clause to multiple IR domain goals. This means that the following trait:

chalk/src/lower/mod.rs

Lines 437 to 439 in eeb2182

	trait LowerWhereClause<T> {
	fn lower(&self, env: &Env) -> Result<T>;
	}

should be changed into something like:

trait LowerWhereClause<T> {
    fn lower(&self, env: &Env) -> Result<Vec<T>>;
}

Step 3

Now we should be in a position where we can implement the various rules written in this comment (niko's comment just below can be ignored, it was basically merged into the main one). This includes:

• program clauses which should be implemented in lower/mod.rs
• WF requirements which should be implemented in lower/wf.rs

Note: the organization of these two files will change after #114 is fixed, so the preceding text may become obsolete.

Step 4

At that point, the domain goal WellFormed(ProjectionEq) will be unused. See #115 for the next steps.

cc @rust-lang-nursery/wg-traits

[scalexm]

Follow-up (should be straightforward): support quantified bounds on GATs, both in the grammar and in the rules, e.g.

trait Foo {
    type Item<V>: forall<'a> Fn(&'a V);
}

[scalexm]

(Reopening because of the follow-up)