Compilation of match statements

I will endeavor to explain the code as best I can. I have only a loose understanding of some parts of it.

Matching

The basic state of the code is maintained in an array m of Match objects. Each Match describes some list of patterns, all of which must match against the current list of values. If those patterns match, then the arm listed in the match is the correct arm. A given arm may have multiple corresponding match entries, one for each alternative that remains. As we proceed these sets of matches are adjusted by the various enter_XXX() functions, each of which adjusts the set of options given some information about the value which has been matched.

So, initially, there is one value and N matches, each of which have one constituent pattern. N here is usually the number of arms but may be greater, if some arms have multiple alternatives. For example, here:

enum Foo { A, B(int), C(uint, uint) }
match foo {
    A => ...,
    B(x) => ...,
    C(1u, 2) => ...,
    C(_) => ...
}

The value would be foo. There would be four matches, each of which contains one pattern (and, in one case, a guard). We could collect the various options and then compile the code for the case where foo is an A, a B, and a C. When we generate the code for C, we would (1) drop the two matches that do not match a C and (2) expand the other two into two patterns each. In the first case, the two patterns would be 1u and 2, and the in the second case the _ pattern would be expanded into _ and _. The two values are of course the arguments to C.

Here is a quick guide to the various functions:

• compile_submatch(): The main workhouse. It takes a list of values and a list of matches and finds the various possibilities that could occur.

• enter_XXX(): modifies the list of matches based on some information about the value that has been matched. For example, enter_rec_or_struct() adjusts the values given that a record or struct has been matched. This is an infallible pattern, so all of the matches must be either wildcards or record/struct patterns. enter_opt() handles the fallible cases, and it is correspondingly more complex.

Bindings

We store information about the bound variables for each arm as part of the per-arm ArmData struct. There is a mapping from identifiers to BindingInfo structs. These structs contain the mode/id/type of the binding, but they also contain up to two LLVM values, called llmatch and llbinding respectively (the llbinding, as will be described shortly, is optional and only present for by-value bindings---therefore it is bundled up as part of the TransBindingMode type). Both point at allocas.

The llmatch binding always stores a pointer into the value being matched which points at the data for the binding. If the value being matched has type T, then, llmatch will point at an alloca of type T* (and hence llmatch has type T**). So, if you have a pattern like:

let a: A = ...; let b: B = ...; match (a, b) { (ref c, d) => { ... } }

For c and d, we would generate allocas of type C* and D* respectively. These are called the llmatch. As we match, when we come up against an identifier, we store the current pointer into the corresponding alloca.

In addition, for each by-value binding (copy or move), we will create a second alloca (llbinding) that will hold the final value. In this example, that means that d would have this second alloca of type D (and hence llbinding has type D*).

Once a pattern is completely matched, and assuming that there is no guard pattern, we will branch to a block that leads to the body itself. For any by-value bindings, this block will first load the ptr from llmatch (the one of type D*) and copy/move the value into llbinding (the one of type D). The second alloca then becomes the value of the local variable. For by ref bindings, the value of the local variable is simply the first alloca.

So, for the example above, we would generate a setup kind of like this:

   +-------+
   | Entry |
   +-------+
       |
   +-------------------------------------------+
   | llmatch_c = (addr of first half of tuple) |
   | llmatch_d = (addr of first half of tuple) |
   +-------------------------------------------+
       |
   +--------------------------------------+
   | *llbinding_d = **llmatch_dlbinding_d |
   +--------------------------------------+

If there is a guard, the situation is slightly different, because we must execute the guard code. Moreover, we need to do so once for each of the alternatives that lead to the arm, because if the guard fails, they may have different points from which to continue the search. Therefore, in that case, we generate code that looks more like:

   +-------+
   | Entry |
   +-------+
       |
   +-------------------------------------------+
   | llmatch_c = (addr of first half of tuple) |
   | llmatch_d = (addr of first half of tuple) |
   +-------------------------------------------+
       |
   +-------------------------------------------------+
   | *llbinding_d = **llmatch_dlbinding_d            |
   | check condition                                 |
   | if false { free *llbinding_d, goto next case }  |
   | if true { goto body }                           |
   +-------------------------------------------------+

The handling for the cleanups is a bit... sensitive. Basically, the body is the one that invokes add_clean() for each binding. During the guard evaluation, we add temporary cleanups and revoke them after the guard is evaluated (it could fail, after all). Presuming the guard fails, we drop the various values we copied explicitly. Note that guards and moves are just plain incompatible.

Some relevant helper functions that manage bindings: - create_bindings_map() - store_non_ref_bindings() - insert_lllocals()

Notes on vector pattern matching.

Vector pattern matching is surprisingly tricky. The problem is that the structure of the vector isn't fully known, and slice matches can be done on subparts of it.

The way that vector pattern matches are dealt with, then, is as follows. First, we make the actual condition associated with a vector pattern simply a vector length comparison. So the pattern [1, .. x] gets the condition "vec len >= 1", and the pattern [.. x] gets the condition "vec len >= 0". The problem here is that having the condition "vec len >= 1" hold clearly does not mean that only a pattern that has exactly that condition will match. This means that it may well be the case that a condition holds, but none of the patterns matching that condition match; to deal with this, when doing vector length matches, we have match failures proceed to the next condition to check.

There are a couple more subtleties to deal with. While the "actual" condition associated with vector length tests is simply a test on the vector length, the actual vec_len Opt entry contains more information used to restrict which matches are associated with it. So that all matches in a submatch are matching against the same values from inside the vector, they are split up by how many elements they match at the front and at the back of the vector. In order to make sure that arms are properly checked in order, even with the overmatching conditions, each vec_len Opt entry is associated with a range of matches. Consider the following:

match &[1, 2, 3] { [1, 1, .. _] => 0, [1, 2, 2, .. _] => 1, [1, 2, 3, .. _] => 2, [1, 2, .. _] => 3, _ => 4 } The proper arm to match is arm 2, but arms 0 and 3 both have the condition "len >= 2". If arm 3 was lumped in with arm 0, then the wrong branch would be taken. Instead, vec_len Opts are associated with a contiguous range of matches that have the same "shape". This is sort of ugly and requires a bunch of special handling of vec_len options.