Repository navigation
Stack overflow compiling slice pattern for big array #53820
Description
The following fails with a stack overflow:
#![feature(slice_patterns)]
fn main() {
match [0u8; 16*1024] {
[..] => {}
}
}I see tests failing on miri's CI on Windows when the size is just 1024, so my suspicion is that this code will fail to compile on Windows with a smaller slice -- but I do not have a Windows machine to test that.
Activity
RalfJung commentedon Aug 30, 2018
Seems like we already had that once with #17877, and it came back?
RalfJung commentedon Aug 30, 2018
Running this in gdb, the top end of the stack looks like
Further down:
oli-obk commentedon Aug 30, 2018
cc @varkor
Centril commentedon Jul 30, 2019
cc @nagisa also?
RalfJung commentedon Jul 30, 2019
I updated the example to the changed syntax; it still reproduces with the latest nightly.
[-]Stack overflow compiling slice pattern for big slice[/-][+]Stack overflow compiling slice pattern for big array[/+]Nadrieril commentedon Sep 2, 2019
Since no one has done it publicly so far, I thought I'd investigate this error a bit.
First, I reduced the example to (playground link):
From the stack trace, we know that the overflow occurs at the only line
is_usefulcalls itself directly:rust/src/librustc_mir/hair/pattern/_match.rs
Line 1199 in fdaf594
From my understanding of the code and the algorithm, this means that
matrixhas way too many columns. This is precisely what we would expect to happen if we considered a fixed-size array as a large tuple and naively applied the algorithm from the paper.And this is in fact what seems to be happening: in the case of a fixed-size array,
constructor_sub_pattern_tysreturns a Vec of the same size as the array, andis_useful_specializedends up making aMatrixwith as many columns. Whereas the code for matching slices only uses as many matrix columns as (essentially) the longest pattern of the match, the code for fixed-size arrays brutally considers them as big tuples and calls it a day. It essentially considers[a, ..]as if it was[a, _, _, _, ..., _]. The algorithm then proceeds with these subpatterns one-by-one recursively, hence the stack overflow.I looks to me like this issue doesn't come from a small oversight somewhere, but rather is a structural consequence of how fixed-size array patterns where shoehorned into the usefulness algorithm. So I feel that a good solution to this issue would need to rethink how to hande arrays (and slices too probably).
My idea for a solution would be the following: We would view a pattern
[a, b, .., c]as something likeCons(a, Cons(b, Snoc(c, [..]))), which means we keep the number of matrix columns to a minimum, but we treat[..]specially when trying to specialize. For example, if we encounter a[..]when computingS(Cons, P), we would pretend[..]was actually[] | Cons(_, [..])(or just[]if we know the size is 0), and then continue as usual.Am I making sense ?
Centril commentedon Sep 2, 2019
Thanks for the investigation! cc @varkor, @arielb1, and @matthewjasper.
10 remaining items
oli-obk commentedon Sep 24, 2019
technically it should be
./x.py test src/librustc_mir --stage 1, but I don't know if that does what it appears it should, never tested itNadrieril commentedon Sep 26, 2019
@oli-obk Thanks !
So I've started working on this, and so far I've refactored some things here and there to make the code easier to follow. I'm not sure my decisions are good and this actually improves the code though. Also this is not strictly necessary to fix this particular issue. Is that an ok thing for me to be doing ? Should I maybe push those changes as a separate refactor PR ?
Centril commentedon Sep 26, 2019
Not only is it OK, it's awesome to first refactor and then implement. :) If it is a large refactor it might make sense to split things into different PRs.
Nadrieril commentedon Oct 6, 2019
I've put up a large refactor over there: #65160.
If and once it gets merged, fixing the issue should just be a case of using the VarLenSlice constructor for fixed-length arrays as well.
Auto merge of #66129 - Nadrieril:refactor-slice-pat-usefulness, r=<try>
Auto merge of #66129 - Nadrieril:refactor-slice-pat-usefulness, r=varkor
Rollup merge of rust-lang#66497 - Nadrieril:fix-53820, r=varkor
Auto merge of #66571 - Centril:rollup-41tn2fw, r=Centril
Rollup merge of rust-lang#67712 - Centril:stabilize-slice_patterns, r…
Rollup merge of rust-lang#67712 - Centril:stabilize-slice_patterns, r…