list pattern matching · compiler development

As I am working on adding .. as rest in list pattern matching, I noticed that our list pattern matching has a bug related to redundant patterns:

The 3rd pattern is redundant:

4│       when [2, 1] is
5│         [1, .., 1] -> 0
6│         [1, ..] -> 1
7│>        [.., 1] -> 2
8│         _ -> 3

Any value of this shape will be handled by a previous pattern, so this
one should be removed.

The third pattern is what should match here , but it is marked as redudant. Any tips on debugging/fixing this? I assume this would be a change to the constrain_pattern function, but maybe this checking is elsewhere, this code is new to me.

Ayaz Hafiz (Nov 20 2023 at 20:43):

Brendan Hansknecht (Nov 20 2023 at 20:48):

Brendan Hansknecht (Nov 20 2023 at 21:46):

Don't understand the code enough yte to have a fix, but the core issue is that [1, ..] and [.., 1] both end up boiling down the the equivalent of a literal 1 in the recursive usefulness check. As such, If one of the patterns exists, the other is not useful. Somehow the before and after related information needs to be added here such that the pattern check can differentiate a 1 at the beginning and a 1 at the end.

Ayaz Hafiz (Nov 20 2023 at 21:48):

Oh interesting. [1,..] should boil down into the infinite sequence [1], [1, _], [1, _, _], ... and [..,1] to [1], [_, 1], [_,_,1], ..., so maybe that's being lost somewhere after the first of each sequence ([1]`) is compared

Brendan Hansknecht (Nov 20 2023 at 21:49):

I think it is related to minimizing the length of the list, but I am not fully sure. Cause we don't actually want to generate [1], [1, _], [1, _, _], .... So there is logic to restrict to the minimal size list necessary for comparison. I assume the bug is there. But I don't fully understand all the pieces, so maybe there is something more.

Ayaz Hafiz (Nov 20 2023 at 21:57):

So what we want is for the second and third case, to generate the comparisons [1, _] and [_, 1]. That's enough to see the lack of redundancy

Brendan Hansknecht (Nov 20 2023 at 23:09):

If you or maybe folkert have a chance to look at this, it would be much appreciated.

I pushed a commit that is my attempted fix, but looking at the tests that are failing, I think I made it too flexible. My gut feeling is that the fix should be pretty simple overall.

My new test case can be run with cargo test-gen-llvm -- rest_as. It is functional with my attempted fix, but a lot of tests under -p roc_load --test test_reporting are broken in a way that leads to new error messages that definitely are wrong.

Isaac Van Doren (Nov 20 2023 at 23:13):

There is this related issue, someone said they would take a look at it a few days ago so might be worth letting them know that you have a fix https://github.com/roc-lang/roc/issues/5187

Brendan Hansknecht (Nov 20 2023 at 23:14):

oops. Didn't mean to take a fix from someone. Just got annoyed and wanted to use the feature

Isaac Van Doren (Nov 20 2023 at 23:15):

Yes I am very eager to use it also, it will significantly clean up some code I have

Ayaz Hafiz (Nov 21 2023 at 01:00):

Brendan Hansknecht (Nov 21 2023 at 01:12):

Ayaz Hafiz (Nov 21 2023 at 02:38):

This is great Brendan, I think you were totally on the right track. I think the problem is that you are specializing to the list constructor which is being checked for redundancy, rather than to the patterns that are checked against.

Ayaz Hafiz (Nov 21 2023 at 02:39):

diff --git a/crates/compiler/exhaustive/src/lib.rs b/crates/compiler/exhaustive/src/lib.rs
index 090b222ac..5239cb725 100644
--- a/crates/compiler/exhaustive/src/lib.rs
+++ b/crates/compiler/exhaustive/src/lib.rs
@@ -389,7 +389,6 @@ pub fn is_useful(mut old_matrix: PatternMatrix, mut vector: Row) -> bool {
                             vector.extend(args);
                         } else {
                             // TODO turn this into an iteration over the outer loop rather than bouncing
-                            vector.extend(args);
                             for list_ctor in spec_list_ctors {
                                 let mut old_matrix = old_matrix.clone();
                                 let mut spec_matrix = Vec::with_capacity(old_matrix.len());
@@ -400,10 +399,19 @@ pub fn is_useful(mut old_matrix: PatternMatrix, mut vector: Row) -> bool {
                                     &mut spec_matrix,
                                 );

-                                if is_useful(spec_matrix, vector.clone()) {
+                                let mut vector = vector.clone();
+                                specialize_row_with_polymorphic_list(
+                                    &mut vector,
+                                    &args,
+                                    arity,
+                                    list_ctor,
+                                );
+
+                                if is_useful(spec_matrix, vector) {
                                     return true;
                                 }
                             }
+
                             return false;
                         }
                     }
@@ -504,6 +512,36 @@ fn specialize_matrix_by_list(
     }
 }

+fn specialize_row_with_polymorphic_list(
+    row: &mut Vec<Pattern>,
+    list_element_patterns: &[Pattern],
+    polymorphic_list_ctor: ListArity,
+    specialized_list_ctor: ListArity,
+) {
+    let min_len = specialized_list_ctor.min_len();
+    if list_element_patterns.len() > min_len {
+        row.extend(list_element_patterns.iter().cloned());
+    }
+
+    let (patterns_before, patterns_after) = match polymorphic_list_ctor {
+        ListArity::Slice(before, after) => (
+            &list_element_patterns[..before],
+            &list_element_patterns[after..],
+        ),
+        ListArity::Exact(_) => (list_element_patterns, &[] as &[Pattern]),
+    };
+
+    let middle_any_patterns_needed =
+        specialized_list_ctor.min_len() - polymorphic_list_ctor.min_len();
+    let middle_patterns = std::iter::repeat(Anything).take(middle_any_patterns_needed);
+
+    row.extend(
+        (patterns_before.iter().cloned())
+            .chain(middle_patterns)
+            .chain(patterns_after.iter().cloned()),
+    );
+}
+
 // Specialize a row that matches a list's constructor(s).
 //
 // See the docs on [build_list_ctors_covering_patterns] for more information on how list
diff --git a/crates/compiler/uitest/tests/foo1.txt b/crates/compiler/uitest/tests/foo1.txt
new file mode 100644
index 000000000..4939d9710
--- /dev/null
+++ b/crates/compiler/uitest/tests/foo1.txt
@@ -0,0 +1,6 @@
+app "test" provides [main] to "./platform"
+
+main = when [] is
+    [1, .., 1] -> "one"
+    [_, .., 1] -> "two"
+    _ -> "three"

Brendan Hansknecht (Nov 21 2023 at 02:54):

Hmm, I can't apply the patch for some reason. do you think you could just push a commit to the branch?

Ayaz Hafiz (Nov 21 2023 at 02:56):

Done. I didn't add tests though. We'll want a few tests in roc_load/tests/reporting

Brendan Hansknecht (Nov 21 2023 at 02:59):

Ayaz Hafiz (Nov 21 2023 at 03:03):

Brendan Hansknecht (Nov 21 2023 at 03:26):

Richard Feldman (Nov 21 2023 at 03:47):

I misread this as "ffs" and I was like "oh no what happened?" and then I realized "oh what happened is that I am old"