Repository: lalrpop/lalrpop (language: rust)

Issue:
Upgrading to version 0.19.10 breaks compilation
Hello,
We are using Lalrpop with version 0.19.9 and regex version 1.7.3
When we upgraded lalrpop to version 0.19.10 we are getting:
```
error: failed to run custom build command for `cel-parser v0.1.3-alpha.0 (/Users/omer/workspace/cel-rust/parser)`

Caused by:
  process didn't exit successfully: `/Users/omer/workspace/cel-rust/target/debug/build/cel-parser-062774afdad45860/build-script-build` (exit status: 101)
  --- stdout
  processing file `/Users/omer/workspace/cel-rust/parser/src/cel.lalrpop`

  --- stderr
  thread 'main' panicked at 'attempt to subtract with overflow', /Users/omer/.cargo/registry/src/github.com-1ecc6299db9ec823/lalrpop-0.19.10/src/lexer/dfa/overlap.rs:73:49
  note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
```

Any ideas what can cause that?


Discussion / hints:
Could you also share the result with `RUST_BACKTRACE=1`? it will shows call stack, so we can understand better where lalrpop met error.
Or maybe an example to add as a testcase?
I've managed to get a test case repro like this in lexer/dfa/overlap.rs:

```
#[test]
fn null() {
    let result = test! {
        '\0' ..= '\0',
        '\0' ..= 'a',
    };
    assert_eq!(result, vec!['\0' ..= '\0', 1 as char ..= 'a']);
}
```

It looks like there are some logic errors in f8355259771c0c180c10a044341370235e7264c9 with the subtraction of 1 on the ranges potentially causing integer underflow.
Probably as another symptom of the same bug, this test case I added is failing as well:

```
#[test]
fn empty_range() {
    let result = test! {
        'b' ..= 'b',
        'a' ..= '9',
    };
    assert_eq!(result, vec!['a' ..= 'a', 'b' ..= 'b', 'c' ..= '9']);
}
```

```
---- lexer::dfa::overlap::null stdout ----
thread 'lexer::dfa::overlap::null' panicked at 'attempt to subtract with overflow', lalrpop/src/lexer/dfa/overlap.rs:73:49
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- lexer::dfa::overlap::empty_range stdout ----
thread 'lexer::dfa::overlap::empty_range' panicked at 'assertion failed: `(left == right)`
  left: `['b'..='b']`,
 right: `['a'..='a', 'b'..='b', 'c'..='9']`', lalrpop/src/lexer/dfa/overlap.rs:151:5
```
is #748 related?
I'll open a pr. @dburgener, I'm not sure that second one should work? The chars get converted to integers so the range a ..= 9 is empty right?
Oh, good catch @Pat-Lafon.  Yeah, I had my ASCII backwards and was thinking 0-9 was after a-z.  You're totally right.
When I fix the second case to this:

```
#[test]
fn empty_range() {
    let result = test! {
        'b' ..= 'b',
        'a' ..= 'z',
    };
    assert_eq!(result, vec!['a' ..= 'a', 'b' ..= 'b', 'c' ..= 'z']);
}
```

It now fails like this:

```
---- lexer::dfa::overlap::empty_range stdout ----
thread 'lexer::dfa::overlap::empty_range' panicked at 'assertion failed: `(left == right)`
  left: `['a'..='a', 'b'..='z']`,
 right: `['a'..='a', 'b'..='b', 'c'..='z']`', lalrpop/src/lexer/dfa/overlap.rs:151:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
```

I'm pretty sure the 'b'..='z' range should be getting split there.  I suspect it's getting incorrectly treated as an empty exclusive range.
> I've managed to get a test case repro like this in lexer/dfa/overlap.rs:
> 
> ```
> #[test]
> fn null() {
>     let result = test! {
>         '\0' ..= '\0',
>         '\0' ..= 'a',
>     };
>     assert_eq!(result, vec!['\0' ..= '\0', 1 as char ..= 'a']);
> }
> ```
> 
> It looks like there are some logic errors in [f835525](https://github.com/lalrpop/lalrpop/commit/f8355259771c0c180c10a044341370235e7264c9) with the subtraction of 1 on the ranges potentially causing integer underflow.

So the issue here is specifically because you are using the null character right? 

This also fails but for a different reason than underflow.
``` rust
#[test]
fn null() {
    let result = test! {
        '0' ..= '0',
        '0' ..= 'a',
    };
    assert_eq!(result, vec!['0' ..= '0', '1' ..= 'a']);
}
```
Your second test case is what I was trying to capture in my second test case.

I think the RangeInclusive conversion introduced both the possibility of underflow, and is inaccurately omitting single character ranges.
Yes, the underflow should be specifically the null character.

Fix patch:
diff --git a/lalrpop/src/lexer/dfa/overlap.rs b/lalrpop/src/lexer/dfa/overlap.rs
index ee7d09d78..2a77b6dd3 100644
--- a/lalrpop/src/lexer/dfa/overlap.rs
+++ b/lalrpop/src/lexer/dfa/overlap.rs
@@ -20,6 +20,7 @@
 use crate::collections::Set;
 use crate::lexer::nfa::Test;
 use std::cmp;
+use std::ops::RangeInclusive;
 
 pub fn remove_overlap(ranges: &Set<Test>) -> Vec<Test> {
     // We will do this in the dumbest possible way to start. :)
@@ -38,6 +39,8 @@ pub fn remove_overlap(ranges: &Set<Test>) -> Vec<Test> {
     // prune them out.
     disjoint_ranges.retain(|r| !r.is_empty());
 
+    disjoint_ranges.sort();
+
     disjoint_ranges
 }
 
@@ -46,6 +49,9 @@ fn add_range(range: Test, start_index: usize, disjoint_ranges: &mut Vec<Test>) {
         return;
     }
 
+    dbg!(&range);
+    dbg!(&disjoint_ranges);
+
     // Find first overlapping range in `disjoint_ranges`, if any.
     match disjoint_ranges[start_index..]
         .iter()
@@ -69,10 +75,18 @@ fn add_range(range: Test, start_index: usize, disjoint_ranges: &mut Vec<Test>) {
             let max_max = cmp::max(range.end(), overlapping_range.end());
             // When working with inclusive ranges, we need to be sure to not double count
             // the meeting points of low-mid_range and mid-max_range.
-            // So we subtract 1 from the end of the low_range and mid_range as these elements are already included in the start of their corresponding next ranges.
-            let low_range = Test::new(min_min..=mid_min - 1);
-            let mid_range = Test::new(mid_min..=mid_max - 1);
-            let max_range = Test::new(mid_max..=max_max);
+            // So we adjust the end of the low_range and start of max_range as these elements are already included in the start of their corresponding next ranges.
+
+            let low_range = if mid_min == 0 {
+                // This is an edgecase where both ranges start at the null character
+                // In this case we don't want to create a range from 0 to -1
+                // Thus we create an empty range
+                Test::new(RangeInclusive::new(1, 0))
+            } else {
+                Test::new(min_min..=mid_min - 1)
+            };
+            let mid_range = Test::new(mid_min..=mid_max);
+            let max_range = Test::new(mid_max + 1..=max_max);
 
             assert!(low_range.is_disjoint(&mid_range));
             assert!(low_range.is_disjoint(&max_range));
@@ -118,7 +132,7 @@ fn alphabet() {
         'c' ..= 'l',
         '0' ..= '9',
     };
-    assert_eq!(result, vec!['0'..='9', 'a'..='b', 'c'..='k', 'l'..='z']);
+    assert_eq!(result, vec!['0'..='9', 'a'..='b', 'c'..='l', 'm'..='z']);
 }
 
 #[test]
@@ -129,7 +143,10 @@ fn repeat() {
         'l' ..= 'z',
         '0' ..= '9',
     };
-    assert_eq!(result, vec!['0'..='9', 'a'..='b', 'c'..='k', 'l'..='z']);
+    assert_eq!(
+        result,
+        vec!['0'..='9', 'a'..='b', 'c'..='k', 'l'..='l', 'm'..='z']
+    );
 }
 
 #[test]
@@ -139,5 +156,26 @@ fn stagger() {
         '2' ..= '4',
         '3' ..= '5',
     };
-    assert_eq!(result, vec!['0'..='1', '2'..='2', '3'..='3', '4'..='5']);
+    assert_eq!(
+        result,
+        vec!['0'..='1', '2'..='2', '3'..='3', '4'..='4', '5'..='5']
+    );
+}
+
+#[test]
+fn empty_range() {
+    let result = test! {
+        'b' ..= 'b',
+        'a' ..= 'z',
+    };
+    assert_eq!(result, vec!['a'..='a', 'b'..='b', 'c'..='z']);
+}
+
+#[test]
+fn null() {
+    let result = test! {
+        '\0' ..= '\0',
+        '\0' ..= 'a',
+    };
+    assert_eq!(result, vec!['\0'..='\0', 1 as char..='a']);
 }
diff --git a/lalrpop/src/lexer/nfa/mod.rs b/lalrpop/src/lexer/nfa/mod.rs
index 864f7946d..534c36a02 100644
--- a/lalrpop/src/lexer/nfa/mod.rs
+++ b/lalrpop/src/lexer/nfa/mod.rs
@@ -579,7 +579,8 @@ impl Test {
     pub fn len(&self) -> u32 {
         // The reason we don't have a RangeInclusive::len is because it panics if the range is 0..=u32::max
         // Akin to https://github.com/rust-lang/rust/issues/36386
-        self.end() - self.start()
+        // Plus one because the range is inclusive
+        self.end() + 1 - self.start()
     }
 
     pub fn contains_u32(&self, c: u32) -> bool {
@@ -628,10 +629,10 @@ impl Debug for Test {
                         write!(fmt, "{}", start)
                     }
                 } else {
-                    write!(fmt, "[{:?}..{:?}]", start, end)
+                    write!(fmt, "[{:?}..={:?}]", start, end)
                 }
             }
-            _ => write!(fmt, "[{:?}..{:?}]", self.start(), self.end()),
+            _ => write!(fmt, "[{:?}..]{:?}]", self.start(), self.end()),
         }
     }
 }


Test patch: