auto merge of #9087 : fhahn/rust/rust_crate_map, r=brson

This patch converts the rust_crate_map.cpp to Rust as mentioned at the end of #8880.

4 files changed, 224 insertions, 54 deletions

diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index fab8299f7a7..09f0af00417 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -687,6 +687,17 @@ impl<T:Hash + Eq> HashSet<T> {
         HashSet { map: HashMap::with_capacity(capacity) }
     }
 
+    /// Create an empty HashSet with space for at least `capacity`
+    /// elements in the hash table, using `k0` and `k1` as the keys.
+    ///
+    /// Warning: `k0` and `k1` are normally randomly generated, and
+    /// are designed to allow HashSets to be resistant to attacks that
+    /// cause many collisions and very poor performance. Setting them
+    /// manually using this function can expose a DoS attack vector.
+    pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashSet<T> {
+        HashSet { map: HashMap::with_capacity_and_keys(k0, k1, capacity) }
+    }
+
     /// Reserve space for at least `n` elements in the hash table.
     pub fn reserve_at_least(&mut self, n: uint) {
         self.map.reserve_at_least(n)
diff --git a/src/libstd/rt/crate_map.rs b/src/libstd/rt/crate_map.rs
new file mode 100644
index 00000000000..270b5e5b137
--- /dev/null
+++ b/src/libstd/rt/crate_map.rs
@@ -0,0 +1,200 @@
+// Copyright 2013 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.
+
+
+use libc::{c_void, c_char};
+use ptr;
+use ptr::RawPtr;
+use vec;
+use hashmap::HashSet;
+use container::MutableSet;
+
+pub struct ModEntry{
+    name: *c_char,
+    log_level: *mut u32
+}
+struct CrateMapV0 {
+    entries: *ModEntry,
+    children: [*CrateMap, ..1]
+}
+
+struct CrateMap {
+    version: i32,
+    annihilate_fn: *c_void,
+    entries: *ModEntry,
+    /// a dynamically sized struct, where all pointers to children are listed adjacent
+    /// to the struct, terminated with NULL
+    children: [*CrateMap, ..1]
+}
+
+unsafe fn version(crate_map: *CrateMap) -> i32 {
+    match (*crate_map).version {
+        1 => return 1,
+        _ => return 0
+    }
+}
+
+/// Returns a pointer to the annihilate function of the CrateMap
+pub unsafe fn annihilate_fn(crate_map: *CrateMap) -> *c_void {
+    match version(crate_map) {
+        0 => return ptr::null(),
+        1 => return (*crate_map).annihilate_fn,
+        _ => fail!("Unknown crate map version!")
+    }
+}
+
+unsafe fn entries(crate_map: *CrateMap) -> *ModEntry {
+    match version(crate_map) {
+        0 => {
+            let v0 = crate_map as (*CrateMapV0);
+            return (*v0).entries;
+        }
+        1 => return (*crate_map).entries,
+        _ => fail!("Unknown crate map version!")
+    }
+}
+
+unsafe fn iterator(crate_map: *CrateMap) -> **CrateMap {
+    match version(crate_map) {
+        0 => {
+            let v0 = crate_map as (*CrateMapV0);
+            return vec::raw::to_ptr((*v0).children);
+        }
+        1 => return vec::raw::to_ptr((*crate_map).children),
+        _ => fail!("Unknown crate map version!")
+    }
+}
+
+unsafe fn iter_module_map(mod_entries: *ModEntry, f: &fn(*mut ModEntry)) {
+    let mut curr = mod_entries;
+
+    while !(*curr).name.is_null() {
+        f(curr as *mut ModEntry);
+        curr = curr.offset(1);
+    }
+}
+
+unsafe fn do_iter_crate_map(crate_map: *CrateMap, f: &fn(*mut ModEntry),
+                            visited: &mut HashSet<*CrateMap>) {
+    if visited.insert(crate_map) {
+        iter_module_map(entries(crate_map), |x| f(x));
+        let child_crates = iterator(crate_map);
+        do ptr::array_each(child_crates) |child| {
+            do_iter_crate_map(child, |x| f(x), visited);
+        }
+    }
+}
+
+/// Iterates recursively over `crate_map` and all child crate maps
+pub unsafe fn iter_crate_map(crate_map: *CrateMap, f: &fn(*mut ModEntry)) {
+    // XXX: use random numbers as keys from the OS-level RNG when there is a nice
+    //        way to do this
+    let mut v: HashSet<*CrateMap> = HashSet::with_capacity_and_keys(0, 0, 32);
+    do_iter_crate_map(crate_map, f, &mut v);
+}
+
+#[test]
+fn iter_crate_map_duplicates() {
+    use c_str::ToCStr;
+    use cast::transmute;
+
+    struct CrateMapT3 {
+        version: i32,
+        annihilate_fn: *c_void,
+        entries: *ModEntry,
+        children: [*CrateMap, ..3]
+    }
+
+    unsafe {
+        let mod_name1 = "c::m1".to_c_str();
+        let mut level3: u32 = 3;
+
+        let entries: ~[ModEntry] = ~[
+            ModEntry { name: mod_name1.with_ref(|buf| buf), log_level: &mut level3},
+            ModEntry { name: ptr::null(), log_level: ptr::mut_null()}
+        ];
+        let child_crate = CrateMap {
+            version: 1,
+            annihilate_fn: ptr::null(),
+            entries: vec::raw::to_ptr(entries),
+            children: [ptr::null()]
+        };
+
+        let root_crate = CrateMapT3 {
+            version: 1, annihilate_fn: ptr::null(),
+            entries: vec::raw::to_ptr([ModEntry { name: ptr::null(), log_level: ptr::mut_null()}]),
+            children: [&child_crate as *CrateMap, &child_crate as *CrateMap, ptr::null()]
+        };
+
+        let mut cnt = 0;
+        do iter_crate_map(transmute(&root_crate)) |entry| {
+            assert!(*(*entry).log_level == 3);
+            cnt += 1;
+        }
+        assert!(cnt == 1);
+    }
+}
+
+#[test]
+fn iter_crate_map_follow_children() {
+    use c_str::ToCStr;
+    use cast::transmute;
+
+    struct CrateMapT2 {
+        version: i32,
+        annihilate_fn: *c_void,
+        entries: *ModEntry,
+        children: [*CrateMap, ..2]
+    }
+
+    unsafe {
+        let mod_name1 = "c::m1".to_c_str();
+        let mod_name2 = "c::m2".to_c_str();
+        let mut level2: u32 = 2;
+        let mut level3: u32 = 3;
+        let child_crate2 = CrateMap {
+            version: 1,
+            annihilate_fn: ptr::null(),
+            entries: vec::raw::to_ptr([
+                ModEntry { name: mod_name1.with_ref(|buf| buf), log_level: &mut level2},
+                ModEntry { name: mod_name2.with_ref(|buf| buf), log_level: &mut level3},
+                ModEntry { name: ptr::null(), log_level: ptr::mut_null()}
+            ]),
+            children: [ptr::null()]
+        };
+
+        let child_crate1 = CrateMapT2 {
+            version: 1,
+            annihilate_fn: ptr::null(),
+            entries: vec::raw::to_ptr([
+                ModEntry { name: "t::f1".to_c_str().with_ref(|buf| buf), log_level: &mut 1},
+                ModEntry { name: ptr::null(), log_level: ptr::mut_null()}
+            ]),
+            children: [&child_crate2 as *CrateMap, ptr::null()]
+        };
+
+        let child_crate1_ptr: *CrateMap = transmute(&child_crate1);
+        let root_crate = CrateMapT2 {
+            version: 1, annihilate_fn: ptr::null(),
+            entries: vec::raw::to_ptr([
+                ModEntry { name: "t::f1".to_c_str().with_ref(|buf| buf), log_level: &mut 0},
+                ModEntry { name: ptr::null(), log_level: ptr::mut_null()}
+            ]),
+            children: [child_crate1_ptr, ptr::null()]
+        };
+
+        let mut cnt = 0;
+        do iter_crate_map(transmute(&root_crate)) |entry| {
+            assert!(*(*entry).log_level == cnt);
+            cnt += 1;
+        }
+        assert!(cnt == 4);
+    }
+}
diff --git a/src/libstd/rt/logging.rs b/src/libstd/rt/logging.rs
index 8a4aba3eb87..0dd096b5bf3 100644
--- a/src/libstd/rt/logging.rs
+++ b/src/libstd/rt/logging.rs
@@ -7,66 +7,24 @@
 // <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.
-use cast::transmute;
 use either::*;
-use libc::{c_void, uintptr_t, c_char, exit, STDERR_FILENO};
+use libc::{uintptr_t, exit, STDERR_FILENO};
 use option::{Some, None, Option};
 use rt::util::dumb_println;
+use rt::crate_map::{ModEntry, iter_crate_map};
 use str::StrSlice;
 use str::raw::from_c_str;
 use u32;
-use unstable::raw::Closure;
 use vec::ImmutableVector;
-
+use cast::transmute;
 
 struct LogDirective {
     name: Option<~str>,
     level: u32
 }
 
-// This is the Rust representation of the mod_entry struct in src/rt/rust_crate_map.h
-struct ModEntry{
-    name: *c_char,
-    log_level: *mut u32
-}
-
 static MAX_LOG_LEVEL: u32 = 255;
 static DEFAULT_LOG_LEVEL: u32 = 1;
-
-fn iter_crate_map(map: *u8, f: &fn(*mut ModEntry)) {
-    unsafe {
-        let closure : Closure = transmute(f);
-        let code = transmute(closure.code);
-        let env = transmute(closure.env);
-        rust_iter_crate_map(transmute(map), iter_cb, code, env);
-    }
-
-    extern fn iter_cb(code: *c_void, env: *c_void, entry: *ModEntry){
-         unsafe {
-            let closure: Closure = Closure {
-                code: transmute(code),
-                env: transmute(env),
-            };
-            let closure: &fn(*ModEntry) = transmute(closure);
-            return closure(entry);
-        }
-    }
-    extern {
-        #[cfg(not(stage0))]
-        #[rust_stack]
-        fn rust_iter_crate_map(map: *c_void,
-                    f: extern "C" fn(*c_void, *c_void, entry: *ModEntry),
-                    code: *c_void,
-                    data: *c_void);
-
-        #[cfg(stage0)]
-        #[rust_stack]
-        fn rust_iter_crate_map(map: *c_void,
-                    f: *u8,
-                    code: *c_void,
-                    data: *c_void);
-    }
-}
 static log_level_names : &'static[&'static str] = &'static["error", "warn", "info", "debug"];
 
 /// Parse an individual log level that is either a number or a symbolic log level
@@ -96,12 +54,10 @@ fn parse_log_level(level: &str) -> Option<u32> {
     log_level
 }
 
-
 /// Parse a logging specification string (e.g: "crate1,crate2::mod3,crate3::x=1")
 /// and return a vector with log directives.
 /// Valid log levels are 0-255, with the most likely ones being 1-4 (defined in std::).
 /// Also supports string log levels of error, warn, info, and debug
-
 fn parse_logging_spec(spec: ~str) -> ~[LogDirective]{
     let mut dirs = ~[];
     for s in spec.split_iter(',') {
@@ -186,12 +142,10 @@ fn update_log_settings(crate_map: *u8, settings: ~str) {
     if settings.len() > 0 {
         if settings == ~"::help" || settings == ~"?" {
             dumb_println("\nCrate log map:\n");
-            do iter_crate_map(crate_map) |entry: *mut ModEntry| {
-                unsafe {
+            unsafe {
+                do iter_crate_map(transmute(crate_map)) |entry: *mut ModEntry| {
                     dumb_println(" "+from_c_str((*entry).name));
                 }
-            }
-            unsafe {
                 exit(1);
             }
         }
@@ -199,9 +153,11 @@ fn update_log_settings(crate_map: *u8, settings: ~str) {
     }
 
     let mut n_matches: u32 = 0;
-    do iter_crate_map(crate_map) |entry: *mut ModEntry| {
-        let m = update_entry(dirs, entry);
-        n_matches += m;
+    unsafe {
+        do iter_crate_map(transmute(crate_map)) |entry: *mut ModEntry| {
+            let m = update_entry(dirs, entry);
+            n_matches += m;
+        }
     }
 
     if n_matches < (dirs.len() as u32) {
diff --git a/src/libstd/rt/mod.rs b/src/libstd/rt/mod.rs
index c9c3c4ec6da..53f62786b62 100644
--- a/src/libstd/rt/mod.rs
+++ b/src/libstd/rt/mod.rs
@@ -126,6 +126,9 @@ pub mod local_heap;
 /// The Logger trait and implementations
 pub mod logging;
 
+/// Crate map
+pub mod crate_map;
+
 /// Tools for testing the runtime
 pub mod test;