robin-hood HashMap "tail-call" should be rewritten as a loop #12860

pnkfelix · 2014-03-13T08:00:25Z

This code:

https://github.com/mozilla/rust/blob/2eebeb81372e320510a1c1e2eef96eb5146a1e1f/src/libcollections/hashmap.rs#L1099

is believed to be causing this stack overflow:

https://gist.github.com/Meyermagic/9523484

Some cursory analysis indicates that this code shouldn't need to be using (an attempt at) tail recursion; a version that uses a loop shouldn't be a difficult refactoring. See discussion here:

https://botbot.me/mozilla/rust/msg/12053161/

Meyermagic · 2014-03-13T08:53:51Z

The following reduced example causes the behavior in question: https://gist.github.com/Meyermagic/9524658

This switches a "tail call" to a manual loop to get around LLVM not optimizing to a tail call. Close #12860

fix: Insert spaces when inlining a function defined in a macro. (partially) fixes rust-lang#12860. This PR (only) addresses the whitespace issue when inlining functions defined in macros. Additionally, the indentation/spacing is not ideal, but works, e.g. ```rs macro_rules! define_function { () => { fn test_function_macro() { if let Some(3) = 3i32.checked_add(0) { println!("3 + 0 == 3"); } } }; } define_function!(); fn main() { test_function_macro(); } // previously became // ... fn main() { ifletSome(3)=3i32.checked_add(0){println!("3 + 0 == 3");}; } // now becomes // ... fn main() { if let Some(3) = 3i32.checked_add(0){ println!("3 + 0 == 3"); }; } ``` The `self` -> `this` problem[^this] is (probably?) a separate problem that I am also looking into. [^this]: As mentioned in [my comment on the above issue](rust-lang/rust-analyzer#12860 (comment)), inlining a method defined in a macro does not properly replace `self` with the new local `this`.

alexcrichton mentioned this issue Mar 13, 2014

collections: Don't recurse in hashmap robin_hood #12867

Merged

bors added a commit that referenced this issue Mar 14, 2014

auto merge of #12867 : alexcrichton/rust/issue-12860, r=thestinger

29756a3

This switches a "tail call" to a manual loop to get around LLVM not optimizing to a tail call. Close #12860

alexcrichton closed this as completed in 05c991c Mar 14, 2014

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

robin-hood HashMap "tail-call" should be rewritten as a loop #12860

robin-hood HashMap "tail-call" should be rewritten as a loop #12860

pnkfelix commented Mar 13, 2014

Meyermagic commented Mar 13, 2014

robin-hood HashMap "tail-call" should be rewritten as a loop #12860

robin-hood HashMap "tail-call" should be rewritten as a loop #12860

Comments

pnkfelix commented Mar 13, 2014

Meyermagic commented Mar 13, 2014