Enum support

[Y-Nak]

Add enum and match support

Overview

Enum

enum types can be defined using the enum keyword.
Variants can contain any number of types inside them with tuple like syntax.

pub enum MyEnum {
    Unit
    // Can Hold data inside it.
    Tuple(u32, u256, bool)
}

Constructors for each variant are automatically implemented, and constructors look like below.

let unit: MyEnum = MyEnum::Unit
let tup: MyEnum = MyEnum::Tuple(1, 2, false)

Match

In fe, match is a statement, not an expression. But this can be changed.
match syntax is almost the same as the Rust, e.g.,

match my_enum {
    MyEnum::Unit => {
        return 1
    }
    MyEnum::Tuple(a, b, true) => {
        return u256(a) + b
    }
    MyEnum::Tuple(a, b, false) => {
        return u256(a) - b 
    }
}

// can also use a tuple pattern
match (x, b) => {
   (MyEnum::Unit, true) => {
       return 2
   }
   (MyEnum::Tuple(.., true), true) => {
       return 3
   }
   _ => {
       return 0
   }
}

Currently below patterns are allowed,

• Wildcard(_), which matches all patterns: _
• Named variable, which matches all patterns and binds the value to make the value usable in the arm. e.g., a, b and c in MyEnum::Tuple(a, b, c)
• Boolean literal(true and false)
• Enum variant. e.g., MyEnum::Tuple(a, b, c)
• Tuple pattern. e.g., (a, b, c)
• Rest pattern(..), which matches the rest of the pattern. e.g., MyEnum::Tuple(.., true)
• Or pattern(|). e.g., MyEnum::Unit | MyEnum::Tuple(.., true)

Also fe compiler checks for exhaustiveness and reachability for pattern matching, and will emit an error when all patterns are not covered or unreachable arms are detected.

Exhaustiveness check example

match val {
    MyEnum::Unit => {
        return 0
    }
    
    MyEnum::Tuple(.., false) => {
        return 1
    }
}

↓

error: patterns are not exhaustive
   ┌─ foo.fe:13:9
   │  
13 │ ╭         match val {
14 │ │             MyEnum::Unit => {
15 │ │                 return 0
16 │ │             }
   · │
20 │ │             }
21 │ │         }
   │ ╰─────────^ `MyEnum::Tuple(_, _, true)` not covered

Reachability check example

match val {
    MyEnum::Unit => {
        return 0
    }
    
    MyEnum::Tuple(a, b, _) => {
        return u256(a) + b
    }

    MyEnum::Tuple(a, b, false) => {
        return u256(a) - b
    }
}

↓

error: unreachable pattern 
   ┌─ foo.fe:22:13
   │
22 │             MyEnum::Tuple(a, b, false) => {
   │             ^^^^^^^^^^^^^^^^^^^^^^^^^^ this arm is unreachable

Implementation details

Exhaustiveness and Reachability

The algorithm to check exhaustiveness and reachability is based on Warnings for pattern matching. The implementation is found in analyzer/src/traversal/pattern_analysis. In this paper, there are only three types of patterns defined.

1. Wildcard
2. Or
3. Constructor

In the implementation, SimplifiedPattern represents them, and high-level patterns in fe are properly lowered into it in the simplify_pattern function in the module.

match lowering

match statement should be lowered into MIR, which has a switch instruction but can no longer represent such a high-level control flow. switch instruction represents branching to multiple destinations according to the target(scrutinee) value, but the target value should be a primitive type(integer or boolean). So this lowering can basically be regarded as the decision tree construction. But multiple decision trees can be constructed from the same match statement, so we need to construct a better one. To achieve this, I implemented the method which is described in Compiling Pattern Matching to Good Decision Trees. The implementation can be found in mir/src/lower/pattern_matching.

E.g.,

enum MyEnum {
    Unit
    Tuple(u32, u256, bool)
}

enum MyEnumNested {
    Unit
    Nested(MyEnum)
    
    fn nested(self) -> u256 {
        match self {
            MyEnumNested::Nested(MyEnum::Unit | MyEnum::Tuple(.., false)) => {
                return 1
            }
            
            
            _ => {
                return 0
            }
        }
    }
}

↓ Decision tree construction

↓ MIR construction from the decision tree

To-Do

• OPTIONAL: Update Spec if applicable
• Add entry to the release notes (may forgo for trivial changes)
• Clean up commit history

[Y-Nak]

@g-r-a-n-t
When these lines are uncommented, the test fails with the message thread 'features::enum_match' panicked at 'attempt to subtract with overflow', crates/test-utils/src/lib.rs:158:24.
This seems to be a bug related to GasReporter or evm::StackExecutor, but I didn't look into it yet.

[Y-Nak]

This heuristic is necessary to select a switch's exit or merge block because multiple merge block candidates cannot be distinguished only by looking at a MIR CFG. This is because of the existence of a default arm.
Please consider the following example and the corresponding MIR.

pub enum MyEnum {
    Unit
    UnitTuple()
    Tuple(u32, u256)
}

pub enum Tuple2{
    Value(MyEnum, MyEnum)
}


contract Foo {
    pub fn bar() -> u256 {
        let tup: Tuple2 = Tuple2::Value(MyEnum::Tuple(1, 2), MyEnum::UnitTuple())
        let res: u256 = 0
        match tup {
            Tuple2::Value(MyEnum::Unit, MyEnum::Tuple(x, y)) | Tuple2::Value(MyEnum::Tuple(x, y), MyEnum::UnitTuple()) => {
                res = u256(x) + y
            }
            _ => {
                return 0
            }
        }
        
        return res
    }
}

Here, the "original" exit block is bb1(or bb5 which can be seen as the exit block because it's the immediate dominator of bb1). But only by looking at the MIR we can't distinguish it from bb7, because both of them are in the union of dominance frontiers of bb3, bb9, and bb12.

NOTE:

1. This algorithm is deterministic.
2. This algorithm doesn't change the semantics of the original code even if it fails to find the original exit block. But if it fails to find the original exit block, the generated yul would be much greater than the optimal code.
3. If there is no return in all arms, this algorithm can certainly find the original exit block.

[cburgdorf]

Epic work! I just skimmed over the code. A lot of it is way over my head so I didn't do a deep dive. What I looked at looked great 👍 🥷

[cburgdorf]

Looks like this is now covered by more generalized code 👍

[cburgdorf]

Great to see the PR covering a spec update, too! ❤️

[sbillig]

This is amazing, as usual @Y-Nak. Sorry it took me so long to read through!