google / google/xls

DSLX Match Exhaustiveness Checking with Range Analysis

Open
#1,961 4 comments 0 reactions 0 assignees View on GitHub
dslx enhancement
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

### What's hard to do? (limit 100 words)

I'm not sure how feasible this is in DSLX land, but one gotcha I noticed is that the match arm exhaustiveness checking can be sensitive to what input you use.

For example, take:

```
fn foo(x: u2) -> u2 {
match x {
u2:0 => u2:0,
u2:1 => u2:1,
u2:2 => u2:1,
u2:3 => u2:2,
}
}
```

This satisfies exhaustiveness checking. But suppose `x` is actually encoded as a biased value (i.e. 0 is not a valid value in the natural input space), and the result is more naturally expressed in terms of the unbiased value. You can't write:

```
fn foo(x: u2) -> u2 {
let unbiased_x = x as u3 + u3:1;
match unbiased_x {
u3:1 => u2:0,
u3:2 => u2:1,
u3:3 => u2:1,
u3:4 => u2:2,
}
}
```

since you would get:

> uN[3] Match patterns are not exhaustive; e.g. `u3:0` not covered; please add remaining patterns to complete the match or a default case via `_ => ...`

### Current best alternative workaround (limit 100 words)

In some cases like above, it's easy to just use a different match pattern (the `u2`), but otherwise, you can add a default arm that can't ever really be reached.

### Your view of the "best case XLS enhancement" (limit 100 words)

It'd be cool if we could infer this is actually exhaustive.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.