collections: Don't recurse in hashmap robin_hood

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

Close #12860

2 files changed, 99 insertions, 31 deletions

diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs
index 85a47d0d62c..d92e31efb9d 100644
--- a/src/libcollections/hashmap.rs
+++ b/src/libcollections/hashmap.rs
@@ -1069,41 +1069,49 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// so we have some sort of upper bound on the number of probes to do.
     ///
     /// 'hash', 'k', and 'v' are the elements to robin hood into the hashtable.
-    fn robin_hood(&mut self, index: table::FullIndex, dib_param: uint,
-                  hash: table::SafeHash, k: K, v: V) {
-        let (old_hash, old_key, old_val) = {
-            let (old_hash_ref, old_key_ref, old_val_ref) = self.table.read_all_mut(&index);
-
-            let old_hash = replace(old_hash_ref, hash);
-            let old_key  = replace(old_key_ref,  k);
-            let old_val  = replace(old_val_ref,  v);
-
-            (old_hash, old_key, old_val)
-        };
-
-        let mut probe = self.probe_next(index.raw_index());
-
-        for dib in range(dib_param + 1, self.table.size()) {
-            let full_index = match self.table.peek(probe) {
-                table::Empty(idx) => {
-                    // Finally. A hole!
-                    self.table.put(idx, old_hash, old_key, old_val);
-                    return;
-                },
-                table::Full(idx) => idx
+    fn robin_hood(&mut self, mut index: table::FullIndex, mut dib_param: uint,
+                  mut hash: table::SafeHash, mut k: K, mut v: V) {
+        'outer: loop {
+            let (old_hash, old_key, old_val) = {
+                let (old_hash_ref, old_key_ref, old_val_ref) =
+                        self.table.read_all_mut(&index);
+
+                let old_hash = replace(old_hash_ref, hash);
+                let old_key  = replace(old_key_ref,  k);
+                let old_val  = replace(old_val_ref,  v);
+
+                (old_hash, old_key, old_val)
             };
 
-            let probe_dib = self.bucket_distance(&full_index);
+            let mut probe = self.probe_next(index.raw_index());
+
+            for dib in range(dib_param + 1, self.table.size()) {
+                let full_index = match self.table.peek(probe) {
+                    table::Empty(idx) => {
+                        // Finally. A hole!
+                        self.table.put(idx, old_hash, old_key, old_val);
+                        return;
+                    },
+                    table::Full(idx) => idx
+                };
+
+                let probe_dib = self.bucket_distance(&full_index);
+
+                // Robin hood! Steal the spot.
+                if probe_dib < dib {
+                    index = full_index;
+                    dib_param = probe_dib;
+                    hash = old_hash;
+                    k = old_key;
+                    v = old_val;
+                    continue 'outer;
+                }
 
-            if probe_dib < dib {
-                // Robin hood! Steal the spot. This had better be tail call.
-                return self.robin_hood(full_index, probe_dib, old_hash, old_key, old_val);
+                probe = self.probe_next(probe);
             }
 
-            probe = self.probe_next(probe);
+            fail!("HashMap fatal error: 100% load factor?");
         }
-
-        fail!("HashMap fatal error: 100% load factor?");
     }
 
     /// Manually insert a pre-hashed key-value pair, without first checking
@@ -1948,7 +1956,6 @@ mod test_map {
 
 #[cfg(test)]
 mod test_set {
-    use super::HashMap;
     use super::HashSet;
     use std::container::Container;
     use std::vec::ImmutableEqVector;
@@ -2193,7 +2200,6 @@ mod test_set {
 mod bench {
     extern crate test;
     use self::test::BenchHarness;
-    use std::iter;
     use std::iter::{range_inclusive};
 
     #[bench]
diff --git a/src/test/run-pass/issue-12860.rs b/src/test/run-pass/issue-12860.rs
new file mode 100644
index 00000000000..52eafaadfd4
--- /dev/null
+++ b/src/test/run-pass/issue-12860.rs
@@ -0,0 +1,62 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// ignore-fast
+
+extern crate collections;
+
+use collections::HashSet;
+
+#[deriving(Eq, Hash)]
+struct XYZ {
+    x: int,
+    y: int,
+    z: int
+}
+
+fn main() {
+    let mut connected = HashSet::new();
+    let mut border = HashSet::new();
+
+    let middle = XYZ{x: 0, y: 0, z: 0};
+    border.insert(middle);
+
+    while border.len() > 0 && connected.len() < 10000 {
+        let choice = *(border.iter().next().unwrap());
+        border.remove(&choice);
+        connected.insert(choice);
+
+        let cxp = XYZ{x: choice.x + 1, y: choice.y, z: choice.z};
+        let cxm = XYZ{x: choice.x - 1, y: choice.y, z: choice.z};
+        let cyp = XYZ{x: choice.x, y: choice.y + 1, z: choice.z};
+        let cym = XYZ{x: choice.x, y: choice.y - 1, z: choice.z};
+        let czp = XYZ{x: choice.x, y: choice.y, z: choice.z + 1};
+        let czm = XYZ{x: choice.x, y: choice.y, z: choice.z - 1};
+
+        if !connected.contains(&cxp) {
+            border.insert(cxp);
+        }
+        if  !connected.contains(&cxm){
+            border.insert(cxm);
+        }
+        if !connected.contains(&cyp){
+            border.insert(cyp);
+        }
+        if !connected.contains(&cym) {
+            border.insert(cym);
+        }
+        if !connected.contains(&czp){
+            border.insert(czp);
+        }
+        if !connected.contains(&czm) {
+            border.insert(czm);
+        }
+    }
+}