google / google/xls

over-eager typecheck for array bounds in unroll_for!

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

Description

**Describe the bug**
It seems that the typechecker eagerly evaluate all indexes when typechecking array access expression in `unroll_for!` loops.

**To Reproduce**

```
fn array_typecheck_bug() -> u8 {
let arr = u8[2][2]:[[u8:0, u8:1], [u8:2, u8:3]];
unroll_for!(x, acc_x): (u2, u8) in u2:0..u2:2 {
unroll_for!(y, acc_y): (u2, u8) in u2:0..u2:2 {
if y == u2:0 { u8:0 } else { arr[x][y-u2:1] }
}(acc_x)
}(u8:0)
}

#[test]
fn array_typecheck_bug_test() {
assert_eq(array_typecheck_bug(), u8:2);
}
```
will produce the following error:
```
Error: INVALID_ARGUMENT: Index out of bounds; index: 3 >= 2 elements; lhs: [u8:0, u8:1]; while processing index; while evaluating: {
if u2:0 == u2:0 { u8:0 } else { arr[u2:0][u2:0 - u2:1] }
}
=== Source Location Trace: ===
xls/common/status/status_builder.cc:197
xls/dslx/interp_value.cc:623
xls/dslx/bytecode/bytecode_interpreter.cc:882
xls/dslx/bytecode/bytecode_interpreter.cc:346
xls/dslx/bytecode/bytecode_interpreter.cc:211
xls/dslx/bytecode/bytecode_interpreter.cc:152
xls/dslx/constexpr_evaluator.cc:702
xls/dslx/constexpr_evaluator.cc:232
xls/dslx/constexpr_evaluator.cc:624
xls/dslx/constexpr_evaluator.cc:232
xls/dslx/type_system/deduce.cc:399
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:832
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:902
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce_ctx.cc:186
xls/dslx/type_system/deduce.cc:550
xls/dslx/type_system/deduce.cc:666
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:832
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:902
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce_ctx.cc:186
xls/dslx/type_system/deduce.cc:379
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:832
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:902
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce_ctx.cc:186
xls/dslx/type_system/deduce.cc:550
xls/dslx/type_system/deduce.cc:666
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:832
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce.cc:902
xls/dslx/type_system/deduce.cc:2123
xls/dslx/type_system/deduce.cc:2137
xls/dslx/type_system/deduce_ctx.cc:131
xls/dslx/type_system/deduce_ctx.cc:186
xls/dslx/type_system/typecheck_function.cc:198
xls/dslx/type_system/typecheck_module.cc:326
xls/dslx/type_system/typecheck_module.cc:326
xls/dslx/parse_and_typecheck.cc:98
xls/dslx/interpreter_main.cc:199
```
even though the `y` index will never be `u2:0` when the `if` expression resolve the its second branch.

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.