Associated types on traits #3470
Comments
This was referenced Aug 16, 2024
github-merge-queue bot
pushed a commit
that referenced
this issue
Aug 22, 2024
# Description ## Problem\* Resolves #3470 (does not fix #5544) ## Summary\* Implements a basic form of associated types in Noir. - The main limitation of this work is that all associated types must be explicitly specified in trait constraints (e.g. `Foo: Iterator<Elem = i32>`) Instead of `Foo: Iterator` - Eliding these requires inserting additional implicit generics anywhere these constraints are used which I considered for this PR but opted to limit the size instead and leave it for later work. ## Additional Context This is a large PR which has quite a few non-trivial changes so I'll try to summarize as best I can to help with reviews: - Made the `Span` on `UnresolvedType` non-optional for better error messages. - Added `GenericTypeArgs` struct to hold both "ordered" and "named" generics. Ordered generics are the ones we are used to where they are specified in order. Named generics are associated types where they are prefixed with `Name =` and may be given in any order in a generics list. - Added a `Generic` trait to abstract over something that can be generic (struct, type alias, trait, etc) so that we can share the same method for resolving all generic things. This saved some code since we were duplicating checks on these before, and have much more now that we have to check named args as well. - Added `TraitGenerics` as the resolved version of `GenericTypeArgs`. This is used in a couple places including the `impl Trait` type in the type system. - Added associated types to the `lookup_trait_implementation` functions in the NodeInterner. These are just treated as normal generics more or less. When we allow these to be omitted in the future we should probably fill these with fresh type variables so that they are still present but always succeed unification. - Stored associated types in trait impls in a separate map in the NodeInterner since they are needed to be referenced within the type signature of methods in the impl, which is before the impl as a whole finishes resolution. - Resolved `Self::AssociatedType` paths. Not that #5544 is not fixed, `Trait::AssociatedType` is still a panic. - Added `current_trait` and `current_trait_impl` fields to the elaborator to resolve these. Otherwise we don't know what `Self` refers to. - Resolved `<Type as Trait>::Type` paths. These are called `AsTraitPath`s. Caveat: these are not allowed/resolved in arithmetic generics still. This prevents e.g. `let Size = <T as Serialize>::Size + <U as Serialize>::Size;`. This is more of an issue for when we allow implicit associated types. For now since they must be explicit, `<T as Serialize>::Size` must already be a named generic in scope so the example would look more like `let Size = TSize + USize;`, see the `serialize` test as an example. - Additionally I had to make a couple more updates to arithmetic generics to get the `serialize` test working: - The existing rules were mostly good until monomorphization when we'd have to re-do the same trait constraints but now we'd know the actual end sizes (constants) for the constraints. This turned out to make it more difficult as we had to solve `4 = a + b` when serializing a pair where `a` and `b` are the serialized sizes of each item. In this case `1` and `3` were the correct answers, and since these refer to specific items in the pair, even an answer of `3` and `1` would be incorrect. I ended up solving `<constant> = a + b` to `<constant> - b = a` so that when we recur on the trait constraints for each item in the pair we'd get `T: Serialize<Size = 4 - b>` and `U: Serialize<Size = a>`. ~~I have a feeling the ordering could be wrong here. It type checks but requires type annotations on the result of `serialize`.~~. We could add more cases besides just subtraction but since this issue isn't directly related to associated generics though I'm considering this future work. ## Documentation\* Check one: - [ ] No documentation needed. - [x] Documentation included in this PR. - [ ] **[For Experimental Features]** Documentation to be submitted in a separate PR. # PR Checklist\* - [ ] I have tested the changes locally. - [ ] I have formatted the changes with [Prettier](https://prettier.io/) and/or `cargo fmt` on default settings. --------- Co-authored-by: Ary Borenszweig <[email protected]> Co-authored-by: Tom <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem
We should have associated types on traits. These are partially implemented currently but are untested and require type checking changes, among others.
Happy Case
Associated types such as the following work:
Alternatives Considered
No response
Additional Context
No response
Would you like to submit a PR for this Issue?
No
Support Needs
No response
The text was updated successfully, but these errors were encountered: