Epic: Implement Traits

[nickysn]

This is a tracking issue for the implementation of traits.

Noir Traits Roadmap

Note: Traits are a huge feature, and this list is by no means final. Expect more steps to be added along the way.

Parser

• [x] [MVP] Parse trait definitions, trait implementations and trait constraint expressions on functions: https://github.com/noir-lang/noir/pull/1886
• [x] [MVP] Parser support for generic traits in where clauses, as well as having several traits, concatenated by '+'': https://github.com/noir-lang/noir/pull/2430
• [x] [MVP] Trait name in trait implementation must be changed from Ident to Path in order to support implementing a trait in a different module: https://github.com/noir-lang/noir/pull/2844
• [x] [MVP] Don't expect a semicolon after a default method in trait: https://github.com/noir-lang/noir/pull/2987

Parser (optional)

• Support for impl TraitName as a parameter and return type: https://github.com/noir-lang/noir/issues/2397
• [ ] impl TraitName as a parameter
• [x] impl TraitName as a return type: https://github.com/noir-lang/noir/commit/4cb20244abba0abc49be0376611979a786563565

Def collector

• Remove the premature checks, that should be done at a later phase:
  • [x] [MVP] function parameters (should be done later, because the current code cannot deal correctly with e.g. type aliases): https://github.com/noir-lang/noir/pull/2585
  • [x] [MVP] function return type (same reason as the above): https://github.com/noir-lang/noir/pull/2585
• Check for duplicated trait items inside the trait
  • [x] Types: https://github.com/noir-lang/noir/pull/2927
  • [x] Consts: https://github.com/noir-lang/noir/pull/2927
  • [x] [MVP] Functions: https://github.com/noir-lang/noir/pull/2927
• Remove unnecessary checks:
  • [x] type of trait implementation doesn't have to be struct: https://github.com/noir-lang/noir/pull/2964
  • [x] allow two or more traits to share the same function/const/type name and implement the same type: https://github.com/noir-lang/noir/pull/3126

    trait Trait1 {
        fn tralala();
    }
    trait Trait2 {
        fn tralala();
    }
    struct MyStruct {}
    impl Trait1 for MyStruct {
        fn tralala() {
        }
    }
    impl Trait2 for MyStruct {
        fn tralala() {
        }
    }

Name resolution/Type checking

• [x] [MVP] Check for duplicate implementations for the same Trait and Type (this check should work even for empty traits!): https://github.com/noir-lang/noir/pull/2585
• [X] [MVP] Support implementing traits, when the trait, type and trait impl are all in different modules: https://github.com/noir-lang/noir/pull/2844
• [X] [MVP] Enforce the Rust trait coherence rules (https://github.com/Ixrec/rust-orphan-rules). They disallow "orphan traits" - these are traits implementations, located in a crate that is different both from the crate of the trait and the crate of the type. Note that these rules don't apply to modules, but only to crates! https://github.com/noir-lang/noir/pull/2844
• Check whether members of the implementation match their signature in the trait definition:
  • Types in the trait implementation match a type, defined in the trait by:
    • [ ] Name
  • Consts in the trait implementation match a const, defined in the trait by:
    • [ ] Const name
    • [ ] Type
  • Functions in the trait implementation match a function, defined in the trait by:
    • [X] [MVP] Function name: https://github.com/noir-lang/noir/pull/2652
    • [X] [MVP] Parameter list and their types: https://github.com/noir-lang/noir/pull/2652
    • [X] [MVP] The return type: https://github.com/noir-lang/noir/pull/2652
• Check whether everything that needs implementation is implemented in the impl part of the trait
  • [ ] Types (all types must be defined in the implementation, because they never have a default value)
  • [ ] Consts without default value
  • [x] [MVP] Functions without default implementation: https://github.com/noir-lang/noir/pull/2585
• Resolve types, defined inside a trait:
  • [ ] using the type inside the trait

    trait MyTrait {
        type MyTraitType;
        let MyConst: MyTraitType;
        fn MyFunc(para: MyTraitType);
    }

• [ ] using the type outside the trait

    trait MyTrait {
        type MyTraitType;
    }
     
    fn main()
    {
        let a: MyTrait::MyTraitType = ...
    }

• Support using a const, defined inside a trait
  • [ ] using the const inside the trait
  • [ ] using the const outside the trait
• Resolve calls of functions, defined in a trait
  • inside the trait
  • [X] [MVP] via Self:: https://github.com/noir-lang/noir/pull/2958
  • [x] [MVP] via self.. Test: https://github.com/noir-lang/noir/pull/2918
  • outside the trait
  • [x] [MVP] via the type name (TODO: tests?)
  • [X] [MVP] via T:: (generic type) https://github.com/noir-lang/noir/pull/2958
  • [x] [MVP] via v. (method invocation) (TODO: tests?)
  • [ ] via <TypeName as TraitName>::
  • [x] via TraitName:: (works only when the method has a Self parameter. Type inference is used to determine which implementation to use.)
• Implement trait constraints. They must be supported everywhere where generics are accepted:
  • [x] [MVP] generic free functions (fn foo<T>() where T: ...): https://github.com/noir-lang/noir/pull/2717
  • [ ] trait methods (trait Foo<T> where T: ... { )
  • [ ] free impl blocks (impl<T> Foo<T> where T...)
  • [x] trait impl blocks (impl<T,U> Foo<T> for Bar<U> where T...)
  • [ ] structs (struct Foo<T> where T: ...)

Monomorphization

• [x] [MVP] Instantiate the trait-accepting functions in the monomorphizer: https://github.com/noir-lang/noir/pull/2717

### Support generic traits
- [ ] Allow generic traits to be implemented multiple times for the same type.
- [x] Pick the correct overload for trait methods based on call arguments.
- [ ] https://github.com/noir-lang/noir/issues/3471

Implement builtin traits

• [x] Operator overloading: Rust std::ops equivalents (Add, Sub, ...)
• [x] Operator overloading: Rust std::cmp equivalentes (Eq, PartialEq)
• [ ] Function traits (Fn)

### Support combining of traits
- [ ] https://github.com/noir-lang/noir/issues/3949

Testing

• [X] [MVP] Refactor compiler so code can be tested for emiting specific errors https://github.com/noir-lang/noir/pull/2760

### Bugs
- [ ] https://github.com/noir-lang/noir/issues/3474
- [ ] https://github.com/noir-lang/noir/issues/3940
- [ ] https://github.com/noir-lang/noir/issues/3948
- [ ] https://github.com/noir-lang/noir/issues/3964
- [ ] https://github.com/noir-lang/noir/issues/4088
- [ ] https://github.com/noir-lang/noir/issues/4095
- [ ] https://github.com/noir-lang/noir/issues/4124

[kevaundray]

Adding #2629 for when this Epic is nearing completion

[Savio-Sou]

Added a "Bugs" section to the original Issue with latest ones @jfecher gathered.

[Savio-Sou]

Added https://github.com/noir-lang/noir/issues/3471 and https://github.com/noir-lang/noir/issues/3949. Useful features for Aztec.nr development.

[jfecher]

I've made issues for all the remaining items. They are:

• Support Trait Inheritance: https://github.com/noir-lang/noir/issues/3949
• Add where clause on an impl: https://github.com/noir-lang/noir/issues/4508
• Support trait constraints directly in a generics list: https://github.com/noir-lang/noir/issues/4541
• Support impl Trait in a parameter position: https://github.com/noir-lang/noir/issues/4540
• Support <Type as Trait> syntax: https://github.com/noir-lang/noir/issues/4539
• Implement associated types for traits: https://github.com/noir-lang/noir/issues/4538

Of these, only #4538 is a major item. The rest are mostly small syntactic shorthands which would be nice to have. #4539 is to some degree necessary, but only once we have #4538.