Implement trait constraints

[mohammadfawaz]

Trait constraints using where seem to be parsed but not yet handled in later stages: https://github.com/FuelLabs/sway/blob/dce836d9e78841dc35a184c918e15e8161cd1882/sway-core/src/semantic_analysis/ast_node/mod.rs#L537

The where keyword can be applied in many contexts. See trait_bounds and its uses in https://github.com/FuelLabs/sway/blob/dce836d9e78841dc35a184c918e15e8161cd1882/sway-core/src/sway.pest#L211

• [x] #1163
• [x] #1159
• [x] #1162
• [x] #4560

[adlerjohn]

Can you clarify what specifically is missing?

[emilyaherbert]

Blocked by #1821.

[emilyaherbert]

copying this from slack for record keeping

My best recommendation for solving this is this:

imagine that we have this example:

trait Double<T> {
  fn double(self) -> T;
}

trait Triple<T> {
  fn triple(self) -> T;
}

impl Double<u64> for u64 {
  fn double(self) -> u64 {
    self + self
  }
}

impl Triple<u64> for u64 {
  fn triple(self) -> u64 {
    self + self + self
  }
}

struct Foo<T> {
  x: T
}

impl<T> Foo<T> where T: Double + Triple {
  fn math(self) -> Foo<T> {
    let a = self.x.double();
    let b = self.x.triple();
    Foo {
      x: a + b
    }
  }
}

on the inside of the compiler we (in pseudocode) change this to:

impl<T> Foo<T> {
  //                       ↓↓↓↓↓↓↓
  fn math(self) -> Foo<T> where T: Double + Triple {
    let a = self.x.double();
    let b = self.x.triple();
    Foo {
      x: a + b
    }
  }
}

During type checking of the impl<T> Foo<T> block, we assume that T does implement Double and Triple and we proceed as we normally would for nested generic functions.

Then, during monomorphization of Foo for some specific T, we check to see if T implements Double and Triple. If it does, then we proceed as normal.

The benefits of this are:

1. low overhead in terms of developer time
2. we can create better error message. "X does not implement Double" is a better error message than "X does not have this method"
3. We can eliminate the use of dummy functions
4. the same logic could be used for enums, structs, and functions

The key to understanding this approach is to approach it with this mindset: from the perspective of inside of math, we know that T implements Double and Triple, because that is how math is defined. The error that users could make however, is providing a T that does not implement Double or Triple.

In other words, as far as math is concerned, it will only accept T's that implement both Double and Triple, and because of this, we know that any T that math accepts will have the methods from inside Double and Triple.

In other words, we can make the strong assertion (1) that given math and a set of trait constraints, any given T either implements those traits or not. A weaker assertion (2) is that given math and a set of trait constraints, any given T either implements all the methods from the set of trait constraints or it does not. Luckily, assertion (1) strictly supersedes assertion (2), and we are able to take advantage of this fact, using the approach above :smile:

How will we be able to insert the right implementation of double() and triple()?

I think that this will require the use of a "function engine" that operates like the type engine. The inlined function for self.x.double() could be Ref(double, T). Much like how we resolve the Ref(TypeId) for types, Ref(double, T) would resolve to the double implementation on T (where T as this point is itself a resolved type, like u64).

[Centril]

During type checking of the impl<T> Foo<T> block, we assume that T does implement Double and Triple and we proceed as we normally would for nested generic functions.

Then, during monomorphization of Foo for some specific T, we check to see if T implements Double and Triple. If it does, then we proceed as normal.

If we aim for a ML-based (e.g., Rust, Haskell, OCaml, ...) approach to generics (my preference), we should indeed provide the assumption that T: Double + Triple inside the block. However, the check that Specific: Double + Triple should not happen during monomorphization. One reason for this is because Specific itself may be a type parameter, as opposed to a concrete and known type. Rather, the check whether we can satisfy the constraints on the impl should be done pre-monomorphization.

[emilyaherbert]

As of #1692 going in, this issue should now be totally unblocked! 🎉 There is a prototype for implementing trait constraints here for someone that wants to pick up this ticket: https://github.com/emilyaherbert/declaration-engine-and-collection-context-demo/blob/d5961b35b6928418b9822cecc42c9ab134836836/de/src/semantic_analysis/inference/declaration.rs#L129

However, the check that Specific: Double + Triple should not happen during monomorphization. One reason for this is because Specific itself may be a type parameter, as opposed to a concrete and known type. Rather, the check whether we can satisfy the constraints on the impl should be done pre-monomorphization.

Makes sense @Centril! Right now, at least in the prototype, the only thing that can be on the LHS of a trait constraint is a type parameter (as opposed to what I think you're thinking about with more complex patterns on the LHS). My belief is that in order to target those patterns, we will need to complete the collection context initiative (#1819 and https://github.com/FuelLabs/sway-rfcs/blob/emilyaherbert/declartion-engine/rfcs/0003-declaration-engine.md#future-possibilities and https://github.com/emilyaherbert/declaration-engine-and-collection-context-demo/tree/master/de_cc). The descriptions are pretty out of date as we have gained more insight since they were written, but at a high level, adding the CC will allow us disentangle type collection, type checking, type inference, and AST transformation, which currently all occur in a single transformative pass from an untyped AST to a fully typed AST. It will also create a compiler mechanism through which, at any given type inference step, we can use to 'look ahead' at 'out of order' nodes, because currently nodes must be placed in the correct order before the transformative typing pass. All of this is to say, I expect that these additions will make expanding trait constraints in the future much easier and will give us the opportunity to check constraint satisfaction before monomorphization 😄

[emilyaherbert]

More tickets for #1692 have come up, meaning this issue is now blocked again momentarily 😢

[sezna]

We also need this for impl self blocks :)

[PaulRBerg]

Have these been implemented? The docs say that they have not, but this issue is closed.

[esdrubal]

Hi @PaulRBerg, thanks for noticing. These have been implemented. Created PR to remove the documentation note: https://github.com/FuelLabs/sway/pull/4986