Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Stack exhausted in the Nfa #98

Closed
ArtemGr opened this issue Jul 1, 2015 · 7 comments
Closed

Stack exhausted in the Nfa #98

ArtemGr opened this issue Jul 1, 2015 · 7 comments
Labels
bug

Comments

@ArtemGr
Copy link

ArtemGr commented Jul 1, 2015

So with the latest crates.io regex crates I got this:

(gdb) bt
#0  0x0000555555dfafae in rust_stack_exhausted ()
#1  0x00005555556a96a9 in __morestack ()
#2  0x0000555555ad8db6 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=167, at=...) at src/crates/by_db/../../by_db.rs:481
#3  0x0000555555ad8cae in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=165, at=...) at src/crates/by_db/../../by_db.rs:481
#4  0x0000555555ad8b61 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=163, at=...) at src/crates/by_db/../../by_db.rs:481
#5  0x0000555555ad8a14 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=161, at=...) at src/crates/by_db/../../by_db.rs:481
#6  0x0000555555ad88c7 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=159, at=...) at src/crates/by_db/../../by_db.rs:481
#7  0x0000555555ad877a in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=157, at=...) at src/crates/by_db/../../by_db.rs:481
#8  0x0000555555ad862d in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=155, at=...) at src/crates/by_db/../../by_db.rs:481
#9  0x0000555555ad84e0 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=153, at=...) at src/crates/by_db/../../by_db.rs:481
#10 0x0000555555ad8393 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=151, at=...) at src/crates/by_db/../../by_db.rs:481
#11 0x0000555555ad8246 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=149, at=...) at src/crates/by_db/../../by_db.rs:481
#12 0x0000555555ad80f9 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=147, at=...) at src/crates/by_db/../../by_db.rs:481
#13 0x0000555555ad7fac in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=145, at=...) at src/crates/by_db/../../by_db.rs:481
#14 0x0000555555ad7e5f in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=143, at=...) at src/crates/by_db/../../by_db.rs:481
#15 0x0000555555ad7d12 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=141, at=...) at src/crates/by_db/../../by_db.rs:481
#16 0x0000555555ad7bc5 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=139, at=...) at src/crates/by_db/../../by_db.rs:481
#17 0x0000555555ad7a78 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=137, at=...) at src/crates/by_db/../../by_db.rs:481
#18 0x0000555555ad792b in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=135, at=...) at src/crates/by_db/../../by_db.rs:481
#19 0x0000555555ad77de in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=133, at=...) at src/crates/by_db/../../by_db.rs:481
#20 0x0000555555ad7691 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=131, at=...) at src/crates/by_db/../../by_db.rs:481
#21 0x0000555555ad7544 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=129, at=...) at src/crates/by_db/../../by_db.rs:481
#22 0x0000555555ad73f7 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=127, at=...) at src/crates/by_db/../../by_db.rs:481
#23 0x0000555555ad72aa in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=125, at=...) at src/crates/by_db/../../by_db.rs:481
#24 0x0000555555ad715d in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=123, at=...) at src/crates/by_db/../../by_db.rs:481
#25 0x0000555555ad7010 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=121, at=...) at src/crates/by_db/../../by_db.rs:481
#26 0x0000555555ad6ec3 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=119, at=...) at src/crates/by_db/../../by_db.rs:481
#27 0x0000555555ad6d76 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=117, at=...) at src/crates/by_db/../../by_db.rs:481
#28 0x0000555555ad6c29 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=115, at=...) at src/crates/by_db/../../by_db.rs:481
#29 0x0000555555ad6adc in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=113, at=...) at src/crates/by_db/../../by_db.rs:481
#30 0x0000555555ad698f in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=111, at=...) at src/crates/by_db/../../by_db.rs:481
#31 0x0000555555ad6842 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=109, at=...) at src/crates/by_db/../../by_db.rs:481
#32 0x0000555555ad66f5 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=107, at=...) at src/crates/by_db/../../by_db.rs:481
#33 0x0000555555ad65a8 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=105, at=...) at src/crates/by_db/../../by_db.rs:481
#34 0x0000555555ad645b in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=103, at=...) at src/crates/by_db/../../by_db.rs:481
#35 0x0000555555ad630e in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=101, at=...) at src/crates/by_db/../../by_db.rs:481
#36 0x0000555555ad61c1 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=99, at=...) at src/crates/by_db/../../by_db.rs:481
#37 0x0000555555ad6074 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=97, at=...) at src/crates/by_db/../../by_db.rs:481
#38 0x0000555555ad5f27 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=95, at=...) at src/crates/by_db/../../by_db.rs:481
#39 0x0000555555ad5dda in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=93, at=...) at src/crates/by_db/../../by_db.rs:481
#40 0x0000555555ad5c8d in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=91, at=...) at src/crates/by_db/../../by_db.rs:481
#41 0x0000555555ad5b40 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=89, at=...) at src/crates/by_db/../../by_db.rs:481
#42 0x0000555555ad59f3 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=87, at=...) at src/crates/by_db/../../by_db.rs:481
#43 0x0000555555ad58a6 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=85, at=...) at src/crates/by_db/../../by_db.rs:481
#44 0x0000555555ad5759 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=83, at=...) at src/crates/by_db/../../by_db.rs:481
#45 0x0000555555ad560c in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=81, at=...) at src/crates/by_db/../../by_db.rs:481
#46 0x0000555555ad54bf in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=79, at=...) at src/crates/by_db/../../by_db.rs:481
#47 0x0000555555ad5372 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=77, at=...) at src/crates/by_db/../../by_db.rs:481
#48 0x0000555555ad5225 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=75, at=...) at src/crates/by_db/../../by_db.rs:481
#49 0x0000555555ad50d8 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=73, at=...) at src/crates/by_db/../../by_db.rs:481
#50 0x0000555555ad4f8b in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=71, at=...) at src/crates/by_db/../../by_db.rs:481
#51 0x0000555555ad4e3e in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=69, at=...) at src/crates/by_db/../../by_db.rs:481
#52 0x0000555555ad4cf1 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=67, at=...) at src/crates/by_db/../../by_db.rs:481
#53 0x0000555555ad4ba4 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=65, at=...) at src/crates/by_db/../../by_db.rs:481
#54 0x0000555555ad4a57 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=63, at=...) at src/crates/by_db/../../by_db.rs:481
#55 0x0000555555ad490a in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=61, at=...) at src/crates/by_db/../../by_db.rs:481
#56 0x0000555555ad47bd in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=59, at=...) at src/crates/by_db/../../by_db.rs:481
#57 0x0000555555ad4670 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=57, at=...) at src/crates/by_db/../../by_db.rs:481
#58 0x0000555555ad4523 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=55, at=...) at src/crates/by_db/../../by_db.rs:481
#59 0x0000555555ad43d6 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=53, at=...) at src/crates/by_db/../../by_db.rs:481
#60 0x0000555555ad4289 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=51, at=...) at src/crates/by_db/../../by_db.rs:481
#61 0x0000555555ad413c in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=49, at=...) at src/crates/by_db/../../by_db.rs:481
#62 0x0000555555ad3fef in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=47, at=...) at src/crates/by_db/../../by_db.rs:481
#63 0x0000555555ad3ea2 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=45, at=...) at src/crates/by_db/../../by_db.rs:481
#64 0x0000555555ad3d55 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=43, at=...) at src/crates/by_db/../../by_db.rs:481
#65 0x0000555555ad3c08 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=41, at=...) at src/crates/by_db/../../by_db.rs:481
#66 0x0000555555ad3abb in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=39, at=...) at src/crates/by_db/../../by_db.rs:481
#67 0x0000555555ad396e in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=37, at=...) at src/crates/by_db/../../by_db.rs:481
#68 0x0000555555ad3821 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=35, at=...) at src/crates/by_db/../../by_db.rs:481
#69 0x0000555555ad36d4 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=33, at=...) at src/crates/by_db/../../by_db.rs:481
#70 0x0000555555ad3587 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=31, at=...) at src/crates/by_db/../../by_db.rs:481
#71 0x0000555555ad343a in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=29, at=...) at src/crates/by_db/../../by_db.rs:481
#72 0x0000555555ad32ed in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=27, at=...) at src/crates/by_db/../../by_db.rs:481
#73 0x0000555555ad31a0 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=25, at=...) at src/crates/by_db/../../by_db.rs:481
#74 0x0000555555ad3053 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=23, at=...) at src/crates/by_db/../../by_db.rs:481
#75 0x0000555555ad2f06 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=21, at=...) at src/crates/by_db/../../by_db.rs:481
#76 0x0000555555ad2db9 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=19, at=...) at src/crates/by_db/../../by_db.rs:481
#77 0x0000555555ad2c6c in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=17, at=...) at src/crates/by_db/../../by_db.rs:481
#78 0x0000555555ad2b1f in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=15, at=...) at src/crates/by_db/../../by_db.rs:481
---Type <return> to continue, or q <return> to quit---
#79 0x0000555555ad29d2 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=13, at=...) at src/crates/by_db/../../by_db.rs:481
#80 0x0000555555ad2885 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=11, at=...) at src/crates/by_db/../../by_db.rs:481
#81 0x0000555555ad2738 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=9, at=...) at src/crates/by_db/../../by_db.rs:481
#82 0x0000555555ad25eb in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=7, at=...) at src/crates/by_db/../../by_db.rs:481
#83 0x0000555555ad249e in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=5, at=...) at src/crates/by_db/../../by_db.rs:481
#84 0x0000555555ad2351 in by_db::log_sql::exec::Nfa<'t>::add (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, thread_caps=..., pc=3, at=...) at src/crates/by_db/../../by_db.rs:481
#85 0x0000555555ae04ac in by_db::log_sql::exec::Nfa<'t>::step (self=0x7fffeebf8ad0, nlist=0x7fffeebf6878, caps=..., thread_caps=..., pc=2, at=..., at_next=...)
    at src/crates/by_db/../../by_db.rs:481
#86 0x0000555555ad0c3a in by_db::log_sql::exec::Nfa<'t>::exec (self=0x7fffeebf8ad0, q=0x7fffeebf4620, caps=..., at=...) at src/crates/by_db/../../by_db.rs:481
#87 0x0000555555acc955 in by_db::log_sql::exec (caps=..., input=..., start=0) at src/crates/by_db/../../by_db.rs:481
#88 0x0000555555da8539 in regex::re::exec (re=0x7fffeebf9030, caps=..., text=..., start=0)
    at /home/grank/.cargo/registry/src/github.com-0a35038f75765ae4/regex-0.1.38/src/re.rs:1145
#89 0x0000555555da8771 in regex::re::Regex::captures (self=0x7fffeebf9030, text=...) at /home/grank/.cargo/registry/src/github.com-0a35038f75765ae4/regex-0.1.38/src/re.rs:409
#90 0x0000555555ac0a30 in by_db::log_sql (sql=..., ffi_or_rust=..., hit_or_miss=..., ttl_sec=7200) at src/crates/by_db/../../by_db.rs:481

The code:

fn log_sql (sql: &str, ffi_or_rust: &str, hit_or_miss: &str, ttl_sec: u32) {
  let short_sql = regex! (r"\r\n") .replace_all (sql, "");
  let short_sql = regex! (r"\s+") .replace_all (&short_sql, " ");
  // NB: Using regex to shorten the string because there might be Unicode characters in it.
  if let Some (short_sql) = regex! (r"^.{1,90}") .captures (&short_sql) {
    if let Some (short_sql) = short_sql.at (0) {
      log! ("cached_*] {kind} {hit} ({sql}){ttl}.",
        kind = ffi_or_rust, hit = hit_or_miss, sql = short_sql,
        ttl = if hit_or_miss == "miss" {format! (" {}", ttl_sec)} else {String::new()});}}}

The error seems to happen in the ^.{1,90} regex.

regex 0.1.38; regex_macros 0.1.20; rustc 1.3.0-nightly (faa04a8b9 2015-06-30)

Interesting?

P.S. Decreasing the range of accepted characters (to {1,70}) works, but I wonder why didn't it happened before. Is it a smaller stack in the nightly Rust or a different implementation of the regex?
@ArtemGr ArtemGr changed the title Stack overflow in the Nfa Stack exhausted in the Nfa Jul 1, 2015
@BurntSushi BurntSushi added the bug label Jul 1, 2015
@BurntSushi
Copy link
Member

@ArtemGr I'm not sure if any recent changes caused this---the recursive nature of add hasn't changed. Looks like I should be using an explicit stack. :-)

@BurntSushi
Copy link
Member

Now that I look at it more closely, I think the compilation of {m,n} expressions is sub-optimal, and I may have touched this recently.

e.g.,

[andrew@Liger debug] ./regex-compile '^.{1,4}'
Original: ^.{1,4}
cap names: [None]
prefixes: Empty (complete: false)
anchored begin true
anchored end false
------------------------
000    Save(0)
001    StartText
002    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
003    Split(4, 5)
004    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
005    Split(6, 7)
006    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
007    Split(8, 9)
008    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
009    Save(1)
010    Match

add will recurse through all of those Split instructions (5 -> 7 -> ...). Given enough of them, it will blow the stack. Seems like a better compilation would be:

000    Save(0)
001    StartText
002    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
003    Split(4, 9)
004    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
005    Split(6, 9)
006    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
007    Split(8, 9)
008    '\u{0}'-'\t', '\u{b}'-'\u{10ffff}'
009    Save(1)
010    Match

That way, we eliminate the circuitous path and let each split jump straight to the match.

@BurntSushi
Copy link
Member

Yup, here's the problem, and I definitely touched this in the last few weeks: https://github.com/rust-lang/regex/blob/master/src/compile.rs#L180-L186

@ArtemGr
Copy link
Author

ArtemGr commented Jul 1, 2015

Looks like regression then. Glad I'm not seeing things )

@BurntSushi
Copy link
Member

Yup. I should have a fix in some time today.

@BurntSushi
Copy link
Member

Fun little tidbit: ^.{1,2000} works fine on my system. If I bump that to ^.{1,2500}, then I can reproduce the issue.

@ArtemGr
Copy link
Author

ArtemGr commented Jul 2, 2015

Cool, thanks!

BurntSushi added a commit that referenced this issue Jul 5, 2015
@BurntSushi
Remove hard test for regex! macro.
12f0c1b 
rustc appears to have a lot of trouble generating code for the
regex `^.{1,2500}`. Presumably it is just too big. The regex
is used to test a stack overflow regression in #98.

This commit moves the test so that it only runs on dynamic regexes,
which can handle it just fine.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@ArtemGr @BurntSushi