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

• [MVP] Parse trait definitions, trait implementations and trait constraint expressions on functions: feat: Implement parsing of traits #1886
• [MVP] Parser support for generic traits in where clauses, as well as having several traits, concatenated by '+'': fix(parser): fixes for the parsing of 'where' clauses #2430
• [MVP] Trait name in trait implementation must be changed from Ident to Path in order to support implementing a trait in a different module: feat(traits): multi module support for traits #2844
• [MVP] Don't expect a semicolon after a default method in trait: fix(traits)!: trait functions with a default implementation must not be followed by a semicolon #2987

Parser (optional)

• Support for impl TraitName as a parameter and return type: feat: Add parser support for trait as parameter to function or as a return type #2397
• impl TraitName as a parameter
• impl TraitName as a return type: 4cb2024

Def collector

• Remove the premature checks, that should be done at a later phase:
  • [MVP] function parameters (should be done later, because the current code cannot deal correctly with e.g. type aliases): feat(traits): Add default and override of methods #2585
  • [MVP] function return type (same reason as the above): feat(traits): Add default and override of methods #2585
• Check for duplicated trait items inside the trait
  • Types: feat(traits): added checks for duplicated trait associated items (types, consts, functions) #2927
  • Consts: feat(traits): added checks for duplicated trait associated items (types, consts, functions) #2927
  • [MVP] Functions: feat(traits): added checks for duplicated trait associated items (types, consts, functions) #2927
• Remove unnecessary checks:
  • type of trait implementation doesn't have to be struct: feat(traits): Add trait impl for buildin types #2964
  • allow two or more traits to share the same function/const/type name and implement the same type: feat(traits): allow multiple traits to share the same associated function name and to be implemented for the same type #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

• [MVP] Check for duplicate implementations for the same Trait and Type (this check should work even for empty traits!): feat(traits): Add default and override of methods #2585
• [MVP] Support implementing traits, when the trait, type and trait impl are all in different modules: feat(traits): multi module support for traits #2844
• [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! feat(traits): multi module support for traits #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:
    • [MVP] Function name: feat(traits): Type checking for Trait impl method signatures  #2652
    • [MVP] Parameter list and their types: feat(traits): Type checking for Trait impl method signatures  #2652
    • [MVP] The return type: feat(traits): Type checking for Trait impl method signatures  #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
  • [MVP] Functions without default implementation: feat(traits): Add default and override of methods #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
  • [MVP] via Self:: feat(traits): Improve support for traits static method resolution #2958
  • [MVP] via self.. Test: chore(traits): added exhaustive test for trait function calls #2918
  • outside the trait
  • [MVP] via the type name (TODO: tests?)
  • [MVP] via T:: (generic type) feat(traits): Improve support for traits static method resolution #2958
  • [MVP] via v. (method invocation) (TODO: tests?)
  • via <TypeName as TraitName>::
  • 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:
  • [MVP] generic free functions (fn foo() where T: ...): feat(traits): Implement trait bounds typechecker + monomorphizer passes #2717
  • trait methods (trait Foo where T: ... { )
  • free impl blocks (impl Foo where T...)
  • trait impl blocks (impl<T,U> Foo for Bar where T...)
  • structs (struct Foo where T: ...)

Monomorphization

• [MVP] Instantiate the trait-accepting functions in the monomorphizer: feat(traits): Implement trait bounds typechecker + monomorphizer passes #2717

Support generic traits

Beta Give feedback

1. Allow generic traits to be implemented multiple times for the same type.
2. Pick the correct overload for trait methods based on call arguments.
3. Support generic traits #3471
   enhancement +1
   

Implement builtin traits

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

Support combining of traits

Beta Give feedback

1. Support Trait Inheritance #3949
   enhancement +1

Testing

• [MVP] Refactor compiler so code can be tested for emiting specific errors chore(errors): Refactor errors representation in compiler #2760

Bugs

Beta Give feedback

1. Traits should allow methods with generic return types #3474
   bug +1
   
2. Trait implemented for all T is not resolved #3940
   bug +1
   
3. Methods from implementing traits should be visible #3948
   bug +1
4. Panic when using trait static method references to generic impls #3964
   E-MEDIUM P-HIGH bug +3
   
5. Generic traits that return generic arrays don't bind array lengths #4088
   bug +1
   
6. Trait methods are not found on mut references #4095
   bug +1
   
7. Method calls don't apply trait constraints #4124
   bug +1
   

[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 #3471 and #3949. Useful features for Aztec.nr development.

[jfecher]

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

• Support Trait Inheritance: Support Trait Inheritance #3949
• Add where clause on an impl: Add where clause on an impl #4508
• Support trait constraints directly in a generics list: Support trait constraints directly in a generics list #4541
• Support impl Trait in a parameter position: Support impl Trait in a parameter position #4540
• Support <Type as Trait> syntax: Support <Type as Trait> syntax #4539
• Implement associated types for traits: Implement associated types for traits #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.