auto merge of #11867 : dmanescu/rust/8784-arena-glob, r=huonw

In line with the dissolution of libextra - #8784 - this moves arena and glob into
their own respective modules. Updates .gitignore with the entries
doc/{arena,glob} in accordance.

3 files changed, 0 insertions, 1381 deletions

diff --git a/src/libextra/arena.rs b/src/libextra/arena.rs
deleted file mode 100644
index 87f6e27b632..00000000000
--- a/src/libextra/arena.rs
+++ /dev/null
@@ -1,602 +0,0 @@
-// Copyright 2012-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.
-//
-//! The arena, a fast but limited type of allocator.
-//!
-//! Arenas are a type of allocator that destroy the objects within, all at
-//! once, once the arena itself is destroyed. They do not support deallocation
-//! of individual objects while the arena itself is still alive. The benefit
-//! of an arena is very fast allocation; just a pointer bump.
-
-#[allow(missing_doc)];
-
-use list::{List, Cons, Nil};
-use list;
-
-use std::at_vec;
-use std::cast::{transmute, transmute_mut, transmute_mut_region};
-use std::cast;
-use std::cell::{Cell, RefCell};
-use std::num;
-use std::ptr;
-use std::mem;
-use std::rt::global_heap;
-use std::uint;
-use std::unstable::intrinsics::{TyDesc, get_tydesc};
-use std::unstable::intrinsics;
-use std::util;
-
-// The way arena uses arrays is really deeply awful. The arrays are
-// allocated, and have capacities reserved, but the fill for the array
-// will always stay at 0.
-#[deriving(Clone)]
-struct Chunk {
-    data: RefCell<@[u8]>,
-    fill: Cell<uint>,
-    is_pod: Cell<bool>,
-}
-
-// Arenas are used to quickly allocate objects that share a
-// lifetime. The arena uses ~[u8] vectors as a backing store to
-// allocate objects from. For each allocated object, the arena stores
-// a pointer to the type descriptor followed by the
-// object. (Potentially with alignment padding after each of them.)
-// When the arena is destroyed, it iterates through all of its chunks,
-// and uses the tydesc information to trace through the objects,
-// calling the destructors on them.
-// One subtle point that needs to be addressed is how to handle
-// failures while running the user provided initializer function. It
-// is important to not run the destructor on uninitialized objects, but
-// how to detect them is somewhat subtle. Since alloc() can be invoked
-// recursively, it is not sufficient to simply exclude the most recent
-// object. To solve this without requiring extra space, we use the low
-// order bit of the tydesc pointer to encode whether the object it
-// describes has been fully initialized.
-
-// As an optimization, objects with destructors are stored in
-// different chunks than objects without destructors. This reduces
-// overhead when initializing plain-old-data and means we don't need
-// to waste time running the destructors of POD.
-#[no_freeze]
-pub struct Arena {
-    // The head is separated out from the list as a unbenchmarked
-    // microoptimization, to avoid needing to case on the list to
-    // access the head.
-    priv head: Chunk,
-    priv pod_head: Chunk,
-    priv chunks: RefCell<@List<Chunk>>,
-}
-
-impl Arena {
-    pub fn new() -> Arena {
-        Arena::new_with_size(32u)
-    }
-
-    pub fn new_with_size(initial_size: uint) -> Arena {
-        Arena {
-            head: chunk(initial_size, false),
-            pod_head: chunk(initial_size, true),
-            chunks: RefCell::new(@Nil),
-        }
-    }
-}
-
-fn chunk(size: uint, is_pod: bool) -> Chunk {
-    let mut v: @[u8] = @[];
-    unsafe { at_vec::raw::reserve(&mut v, size); }
-    Chunk {
-        data: RefCell::new(unsafe { cast::transmute(v) }),
-        fill: Cell::new(0u),
-        is_pod: Cell::new(is_pod),
-    }
-}
-
-#[unsafe_destructor]
-impl Drop for Arena {
-    fn drop(&mut self) {
-        unsafe {
-            destroy_chunk(&self.head);
-
-            list::each(self.chunks.get(), |chunk| {
-                if !chunk.is_pod.get() {
-                    destroy_chunk(chunk);
-                }
-                true
-            });
-        }
-    }
-}
-
-#[inline]
-fn round_up(base: uint, align: uint) -> uint {
-    (base.checked_add(&(align - 1))).unwrap() & !(&(align - 1))
-}
-
-// Walk down a chunk, running the destructors for any objects stored
-// in it.
-unsafe fn destroy_chunk(chunk: &Chunk) {
-    let mut idx = 0;
-    let buf = {
-        let data = chunk.data.borrow();
-        data.get().as_ptr()
-    };
-    let fill = chunk.fill.get();
-
-    while idx < fill {
-        let tydesc_data: *uint = transmute(ptr::offset(buf, idx as int));
-        let (tydesc, is_done) = un_bitpack_tydesc_ptr(*tydesc_data);
-        let (size, align) = ((*tydesc).size, (*tydesc).align);
-
-        let after_tydesc = idx + mem::size_of::<*TyDesc>();
-
-        let start = round_up(after_tydesc, align);
-
-        //debug!("freeing object: idx = {}, size = {}, align = {}, done = {}",
-        //       start, size, align, is_done);
-        if is_done {
-            ((*tydesc).drop_glue)(ptr::offset(buf, start as int) as *i8);
-        }
-
-        // Find where the next tydesc lives
-        idx = round_up(start + size, mem::pref_align_of::<*TyDesc>());
-    }
-}
-
-// We encode whether the object a tydesc describes has been
-// initialized in the arena in the low bit of the tydesc pointer. This
-// is necessary in order to properly do cleanup if a failure occurs
-// during an initializer.
-#[inline]
-unsafe fn bitpack_tydesc_ptr(p: *TyDesc, is_done: bool) -> uint {
-    let p_bits: uint = transmute(p);
-    p_bits | (is_done as uint)
-}
-#[inline]
-unsafe fn un_bitpack_tydesc_ptr(p: uint) -> (*TyDesc, bool) {
-    (transmute(p & !1), p & 1 == 1)
-}
-
-impl Arena {
-    // Functions for the POD part of the arena
-    fn alloc_pod_grow(&mut self, n_bytes: uint, align: uint) -> *u8 {
-        // Allocate a new chunk.
-        let chunk_size = at_vec::capacity(self.pod_head.data.get());
-        let new_min_chunk_size = num::max(n_bytes, chunk_size);
-        self.chunks.set(@Cons(self.pod_head.clone(), self.chunks.get()));
-        self.pod_head =
-            chunk(uint::next_power_of_two(new_min_chunk_size + 1u), true);
-
-        return self.alloc_pod_inner(n_bytes, align);
-    }
-
-    #[inline]
-    fn alloc_pod_inner(&mut self, n_bytes: uint, align: uint) -> *u8 {
-        unsafe {
-            let this = transmute_mut_region(self);
-            let start = round_up(this.pod_head.fill.get(), align);
-            let end = start + n_bytes;
-            if end > at_vec::capacity(this.pod_head.data.get()) {
-                return this.alloc_pod_grow(n_bytes, align);
-            }
-            this.pod_head.fill.set(end);
-
-            //debug!("idx = {}, size = {}, align = {}, fill = {}",
-            //       start, n_bytes, align, head.fill.get());
-
-            ptr::offset(this.pod_head.data.get().as_ptr(), start as int)
-        }
-    }
-
-    #[inline]
-    fn alloc_pod<'a, T>(&'a mut self, op: || -> T) -> &'a T {
-        unsafe {
-            let tydesc = get_tydesc::<T>();
-            let ptr = self.alloc_pod_inner((*tydesc).size, (*tydesc).align);
-            let ptr: *mut T = transmute(ptr);
-            intrinsics::move_val_init(&mut (*ptr), op());
-            return transmute(ptr);
-        }
-    }
-
-    // Functions for the non-POD part of the arena
-    fn alloc_nonpod_grow(&mut self, n_bytes: uint, align: uint)
-                         -> (*u8, *u8) {
-        // Allocate a new chunk.
-        let chunk_size = at_vec::capacity(self.head.data.get());
-        let new_min_chunk_size = num::max(n_bytes, chunk_size);
-        self.chunks.set(@Cons(self.head.clone(), self.chunks.get()));
-        self.head =
-            chunk(uint::next_power_of_two(new_min_chunk_size + 1u), false);
-
-        return self.alloc_nonpod_inner(n_bytes, align);
-    }
-
-    #[inline]
-    fn alloc_nonpod_inner(&mut self, n_bytes: uint, align: uint)
-                          -> (*u8, *u8) {
-        unsafe {
-            let start;
-            let end;
-            let tydesc_start;
-            let after_tydesc;
-
-            {
-                let head = transmute_mut_region(&mut self.head);
-
-                tydesc_start = head.fill.get();
-                after_tydesc = head.fill.get() + mem::size_of::<*TyDesc>();
-                start = round_up(after_tydesc, align);
-                end = start + n_bytes;
-            }
-
-            if end > at_vec::capacity(self.head.data.get()) {
-                return self.alloc_nonpod_grow(n_bytes, align);
-            }
-
-            let head = transmute_mut_region(&mut self.head);
-            head.fill.set(round_up(end, mem::pref_align_of::<*TyDesc>()));
-
-            //debug!("idx = {}, size = {}, align = {}, fill = {}",
-            //       start, n_bytes, align, head.fill);
-
-            let buf = self.head.data.get().as_ptr();
-            return (ptr::offset(buf, tydesc_start as int), ptr::offset(buf, start as int));
-        }
-    }
-
-    #[inline]
-    fn alloc_nonpod<'a, T>(&'a mut self, op: || -> T) -> &'a T {
-        unsafe {
-            let tydesc = get_tydesc::<T>();
-            let (ty_ptr, ptr) =
-                self.alloc_nonpod_inner((*tydesc).size, (*tydesc).align);
-            let ty_ptr: *mut uint = transmute(ty_ptr);
-            let ptr: *mut T = transmute(ptr);
-            // Write in our tydesc along with a bit indicating that it
-            // has *not* been initialized yet.
-            *ty_ptr = transmute(tydesc);
-            // Actually initialize it
-            intrinsics::move_val_init(&mut(*ptr), op());
-            // Now that we are done, update the tydesc to indicate that
-            // the object is there.
-            *ty_ptr = bitpack_tydesc_ptr(tydesc, true);
-
-            return transmute(ptr);
-        }
-    }
-
-    // The external interface
-    #[inline]
-    pub fn alloc<'a, T>(&'a self, op: || -> T) -> &'a T {
-        unsafe {
-            // FIXME: Borrow check
-            let this = transmute_mut(self);
-            if intrinsics::needs_drop::<T>() {
-                this.alloc_nonpod(op)
-            } else {
-                this.alloc_pod(op)
-            }
-        }
-    }
-}
-
-#[test]
-fn test_arena_destructors() {
-    let arena = Arena::new();
-    for i in range(0u, 10) {
-        // Arena allocate something with drop glue to make sure it
-        // doesn't leak.
-        arena.alloc(|| @i);
-        // Allocate something with funny size and alignment, to keep
-        // things interesting.
-        arena.alloc(|| [0u8, 1u8, 2u8]);
-    }
-}
-
-#[test]
-#[should_fail]
-fn test_arena_destructors_fail() {
-    let arena = Arena::new();
-    // Put some stuff in the arena.
-    for i in range(0u, 10) {
-        // Arena allocate something with drop glue to make sure it
-        // doesn't leak.
-        arena.alloc(|| { @i });
-        // Allocate something with funny size and alignment, to keep
-        // things interesting.
-        arena.alloc(|| { [0u8, 1u8, 2u8] });
-    }
-    // Now, fail while allocating
-    arena.alloc::<@int>(|| {
-        // Now fail.
-        fail!();
-    });
-}
-
-/// An arena that can hold objects of only one type.
-///
-/// Safety note: Modifying objects in the arena that have already had their
-/// `drop` destructors run can cause leaks, because the destructor will not
-/// run again for these objects.
-pub struct TypedArena<T> {
-    /// A pointer to the next object to be allocated.
-    priv ptr: *T,
-
-    /// A pointer to the end of the allocated area. When this pointer is
-    /// reached, a new chunk is allocated.
-    priv end: *T,
-
-    /// The type descriptor of the objects in the arena. This should not be
-    /// necessary, but is until generic destructors are supported.
-    priv tydesc: *TyDesc,
-
-    /// A pointer to the first arena segment.
-    priv first: Option<~TypedArenaChunk>,
-}
-
-struct TypedArenaChunk {
-    /// Pointer to the next arena segment.
-    next: Option<~TypedArenaChunk>,
-
-    /// The number of elements that this chunk can hold.
-    capacity: uint,
-
-    // Objects follow here, suitably aligned.
-}
-
-impl TypedArenaChunk {
-    #[inline]
-    fn new<T>(next: Option<~TypedArenaChunk>, capacity: uint)
-           -> ~TypedArenaChunk {
-        let mut size = mem::size_of::<TypedArenaChunk>();
-        size = round_up(size, mem::min_align_of::<T>());
-        let elem_size = mem::size_of::<T>();
-        let elems_size = elem_size.checked_mul(&capacity).unwrap();
-        size = size.checked_add(&elems_size).unwrap();
-
-        let mut chunk = unsafe {
-            let chunk = global_heap::exchange_malloc(size);
-            let mut chunk: ~TypedArenaChunk = cast::transmute(chunk);
-            intrinsics::move_val_init(&mut chunk.next, next);
-            chunk
-        };
-
-        chunk.capacity = capacity;
-        chunk
-    }
-
-    /// Destroys this arena chunk. If the type descriptor is supplied, the
-    /// drop glue is called; otherwise, drop glue is not called.
-    #[inline]
-    unsafe fn destroy(&mut self, len: uint, opt_tydesc: Option<*TyDesc>) {
-        // Destroy all the allocated objects.
-        match opt_tydesc {
-            None => {}
-            Some(tydesc) => {
-                let mut start = self.start(tydesc);
-                for _ in range(0, len) {
-                    ((*tydesc).drop_glue)(start as *i8);
-                    start = start.offset((*tydesc).size as int)
-                }
-            }
-        }
-
-        // Destroy the next chunk.
-        let next_opt = util::replace(&mut self.next, None);
-        match next_opt {
-            None => {}
-            Some(mut next) => {
-                // We assume that the next chunk is completely filled.
-                next.destroy(next.capacity, opt_tydesc)
-            }
-        }
-    }
-
-    // Returns a pointer to the first allocated object.
-    #[inline]
-    fn start(&self, tydesc: *TyDesc) -> *u8 {
-        let this: *TypedArenaChunk = self;
-        unsafe {
-            cast::transmute(round_up(this.offset(1) as uint, (*tydesc).align))
-        }
-    }
-
-    // Returns a pointer to the end of the allocated space.
-    #[inline]
-    fn end(&self, tydesc: *TyDesc) -> *u8 {
-        unsafe {
-            let size = (*tydesc).size.checked_mul(&self.capacity).unwrap();
-            self.start(tydesc).offset(size as int)
-        }
-    }
-}
-
-impl<T> TypedArena<T> {
-    /// Creates a new arena with preallocated space for 8 objects.
-    #[inline]
-    pub fn new() -> TypedArena<T> {
-        TypedArena::with_capacity(8)
-    }
-
-    /// Creates a new arena with preallocated space for the given number of
-    /// objects.
-    #[inline]
-    pub fn with_capacity(capacity: uint) -> TypedArena<T> {
-        let chunk = TypedArenaChunk::new::<T>(None, capacity);
-        let tydesc = unsafe {
-            intrinsics::get_tydesc::<T>()
-        };
-        TypedArena {
-            ptr: chunk.start(tydesc) as *T,
-            end: chunk.end(tydesc) as *T,
-            tydesc: tydesc,
-            first: Some(chunk),
-        }
-    }
-
-    /// Allocates an object into this arena.
-    #[inline]
-    pub fn alloc<'a>(&'a self, object: T) -> &'a T {
-        unsafe {
-            let this = cast::transmute_mut(self);
-            if this.ptr == this.end {
-                this.grow()
-            }
-
-            let ptr: &'a mut T = cast::transmute(this.ptr);
-            intrinsics::move_val_init(ptr, object);
-            this.ptr = this.ptr.offset(1);
-            let ptr: &'a T = ptr;
-            ptr
-        }
-    }
-
-    /// Grows the arena.
-    #[inline(never)]
-    fn grow(&mut self) {
-        let chunk = self.first.take_unwrap();
-        let new_capacity = chunk.capacity.checked_mul(&2).unwrap();
-        let chunk = TypedArenaChunk::new::<T>(Some(chunk), new_capacity);
-        self.ptr = chunk.start(self.tydesc) as *T;
-        self.end = chunk.end(self.tydesc) as *T;
-        self.first = Some(chunk)
-    }
-}
-
-#[unsafe_destructor]
-impl<T> Drop for TypedArena<T> {
-    fn drop(&mut self) {
-        // Determine how much was filled.
-        let start = self.first.get_ref().start(self.tydesc) as uint;
-        let end = self.ptr as uint;
-        let diff = (end - start) / mem::size_of::<T>();
-
-        // Pass that to the `destroy` method.
-        unsafe {
-            let opt_tydesc = if intrinsics::needs_drop::<T>() {
-                Some(self.tydesc)
-            } else {
-                None
-            };
-            self.first.get_mut_ref().destroy(diff, opt_tydesc)
-        }
-    }
-}
-
-#[cfg(test)]
-mod test {
-    use super::{Arena, TypedArena};
-    use test::BenchHarness;
-
-    struct Point {
-        x: int,
-        y: int,
-        z: int,
-    }
-
-    #[test]
-    pub fn test_pod() {
-        let arena = TypedArena::new();
-        for _ in range(0, 100000) {
-            arena.alloc(Point {
-                x: 1,
-                y: 2,
-                z: 3,
-            });
-        }
-    }
-
-    #[bench]
-    pub fn bench_pod(bh: &mut BenchHarness) {
-        let arena = TypedArena::new();
-        bh.iter(|| {
-            arena.alloc(Point {
-                x: 1,
-                y: 2,
-                z: 3,
-            });
-        })
-    }
-
-    #[bench]
-    pub fn bench_pod_nonarena(bh: &mut BenchHarness) {
-        bh.iter(|| {
-            let _ = ~Point {
-                x: 1,
-                y: 2,
-                z: 3,
-            };
-        })
-    }
-
-    #[bench]
-    pub fn bench_pod_old_arena(bh: &mut BenchHarness) {
-        let arena = Arena::new();
-        bh.iter(|| {
-            arena.alloc(|| {
-                Point {
-                    x: 1,
-                    y: 2,
-                    z: 3,
-                }
-            });
-        })
-    }
-
-    struct Nonpod {
-        string: ~str,
-        array: ~[int],
-    }
-
-    #[test]
-    pub fn test_nonpod() {
-        let arena = TypedArena::new();
-        for _ in range(0, 100000) {
-            arena.alloc(Nonpod {
-                string: ~"hello world",
-                array: ~[ 1, 2, 3, 4, 5 ],
-            });
-        }
-    }
-
-    #[bench]
-    pub fn bench_nonpod(bh: &mut BenchHarness) {
-        let arena = TypedArena::new();
-        bh.iter(|| {
-            arena.alloc(Nonpod {
-                string: ~"hello world",
-                array: ~[ 1, 2, 3, 4, 5 ],
-            });
-        })
-    }
-
-    #[bench]
-    pub fn bench_nonpod_nonarena(bh: &mut BenchHarness) {
-        bh.iter(|| {
-            let _ = ~Nonpod {
-                string: ~"hello world",
-                array: ~[ 1, 2, 3, 4, 5 ],
-            };
-        })
-    }
-
-    #[bench]
-    pub fn bench_nonpod_old_arena(bh: &mut BenchHarness) {
-        let arena = Arena::new();
-        bh.iter(|| {
-            let _ = arena.alloc(|| Nonpod {
-                string: ~"hello world",
-                array: ~[ 1, 2, 3, 4, 5 ],
-            });
-        })
-    }
-}
-
-
diff --git a/src/libextra/glob.rs b/src/libextra/glob.rs
deleted file mode 100644
index fb760685254..00000000000
--- a/src/libextra/glob.rs
+++ /dev/null
@@ -1,777 +0,0 @@
-// 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.
-
-/*!
- * Support for matching file paths against Unix shell style patterns.
- *
- * The `glob` and `glob_with` functions, in concert with the `Paths`
- * type, allow querying the filesystem for all files that match a particular
- * pattern - just like the libc `glob` function (for an example see the `glob`
- * documentation). The methods on the `Pattern` type provide functionality
- * for checking if individual paths match a particular pattern - in a similar
- * manner to the libc `fnmatch` function
- *
- * For consistency across platforms, and for Windows support, this module
- * is implemented entirely in Rust rather than deferring to the libc
- * `glob`/`fnmatch` functions.
- */
-
-use std::{os, path};
-use std::io;
-use std::io::fs;
-use std::path::is_sep;
-
-/**
- * An iterator that yields Paths from the filesystem that match a particular
- * pattern - see the `glob` function for more details.
- */
-pub struct Paths {
-    priv root: Path,
-    priv dir_patterns: ~[Pattern],
-    priv options: MatchOptions,
-    priv todo: ~[(Path,uint)]
-}
-
-///
-/// Return an iterator that produces all the Paths that match the given pattern,
-/// which may be absolute or relative to the current working directory.
-///
-/// is method uses the default match options and is equivalent to calling
-/// `glob_with(pattern, MatchOptions::new())`. Use `glob_with` directly if you
-/// want to use non-default match options.
-///
-/// # Example
-///
-/// Consider a directory `/media/pictures` containing only the files `kittens.jpg`,
-/// `puppies.jpg` and `hamsters.gif`:
-///
-/// ```rust
-/// use extra::glob::glob;
-///
-/// for path in glob("/media/pictures/*.jpg") {
-///     println!("{}", path.display());
-/// }
-/// ```
-///
-/// The above code will print:
-///
-/// ```
-/// /media/pictures/kittens.jpg
-/// /media/pictures/puppies.jpg
-/// ```
-///
-pub fn glob(pattern: &str) -> Paths {
-    glob_with(pattern, MatchOptions::new())
-}
-
-/**
- * Return an iterator that produces all the Paths that match the given pattern,
- * which may be absolute or relative to the current working directory.
- *
- * This function accepts Unix shell style patterns as described by `Pattern::new(..)`.
- * The options given are passed through unchanged to `Pattern::matches_with(..)` with
- * the exception that `require_literal_separator` is always set to `true` regardless of the
- * value passed to this function.
- *
- * Paths are yielded in alphabetical order, as absolute paths.
- */
-pub fn glob_with(pattern: &str, options: MatchOptions) -> Paths {
-    #[cfg(windows)]
-    fn check_windows_verbatim(p: &Path) -> bool { path::windows::is_verbatim(p) }
-    #[cfg(not(windows))]
-    fn check_windows_verbatim(_: &Path) -> bool { false }
-
-    // calculate root this way to handle volume-relative Windows paths correctly
-    let mut root = os::getcwd();
-    let pat_root = Path::new(pattern).root_path();
-    if pat_root.is_some() {
-        if check_windows_verbatim(pat_root.get_ref()) {
-            // FIXME: How do we want to handle verbatim paths? I'm inclined to return nothing,
-            // since we can't very well find all UNC shares with a 1-letter server name.
-            return Paths { root: root, dir_patterns: ~[], options: options, todo: ~[] };
-        }
-        root.push(pat_root.get_ref());
-    }
-
-    let root_len = pat_root.map_or(0u, |p| p.as_vec().len());
-    let dir_patterns = pattern.slice_from(root_len.min(&pattern.len()))
-                       .split_terminator(is_sep).map(|s| Pattern::new(s)).to_owned_vec();
-
-    let todo = list_dir_sorted(&root).move_iter().map(|x|(x,0u)).to_owned_vec();
-
-    Paths {
-        root: root,
-        dir_patterns: dir_patterns,
-        options: options,
-        todo: todo,
-    }
-}
-
-impl Iterator<Path> for Paths {
-
-    fn next(&mut self) -> Option<Path> {
-        loop {
-            if self.dir_patterns.is_empty() || self.todo.is_empty() {
-                return None;
-            }
-
-            let (path,idx) = self.todo.pop().unwrap();
-            let ref pattern = self.dir_patterns[idx];
-
-            if pattern.matches_with(match path.filename_str() {
-                // this ugly match needs to go here to avoid a borrowck error
-                None => {
-                    // FIXME (#9639): How do we handle non-utf8 filenames? Ignore them for now
-                    // Ideally we'd still match them against a *
-                    continue;
-                }
-                Some(x) => x
-            }, self.options) {
-                if idx == self.dir_patterns.len() - 1 {
-                    // it is not possible for a pattern to match a directory *AND* its children
-                    // so we don't need to check the children
-                    return Some(path);
-                } else {
-                    self.todo.extend(&mut list_dir_sorted(&path).move_iter().map(|x|(x,idx+1)));
-                }
-            }
-        }
-    }
-
-}
-
-fn list_dir_sorted(path: &Path) -> ~[Path] {
-    match io::result(|| fs::readdir(path)) {
-        Ok(mut children) => {
-            children.sort_by(|p1, p2| p2.filename().cmp(&p1.filename()));
-            children
-        }
-        Err(..) => ~[]
-    }
-}
-
-/**
- * A compiled Unix shell style pattern.
- */
-#[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, IterBytes, Default)]
-pub struct Pattern {
-    priv tokens: ~[PatternToken]
-}
-
-#[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, IterBytes)]
-enum PatternToken {
-    Char(char),
-    AnyChar,
-    AnySequence,
-    AnyWithin(~[CharSpecifier]),
-    AnyExcept(~[CharSpecifier])
-}
-
-#[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, IterBytes)]
-enum CharSpecifier {
-    SingleChar(char),
-    CharRange(char, char)
-}
-
-#[deriving(Eq)]
-enum MatchResult {
-    Match,
-    SubPatternDoesntMatch,
-    EntirePatternDoesntMatch
-}
-
-impl Pattern {
-
-    /**
-     * This function compiles Unix shell style patterns: `?` matches any single
-     * character, `*` matches any (possibly empty) sequence of characters and
-     * `[...]` matches any character inside the brackets, unless the first
-     * character is `!` in which case it matches any character except those
-     * between the `!` and the `]`. Character sequences can also specify ranges
-     * of characters, as ordered by Unicode, so e.g. `[0-9]` specifies any
-     * character between 0 and 9 inclusive.
-     *
-     * The metacharacters `?`, `*`, `[`, `]` can be matched by using brackets
-     * (e.g. `[?]`).  When a `]` occurs immediately following `[` or `[!` then
-     * it is interpreted as being part of, rather then ending, the character
-     * set, so `]` and NOT `]` can be matched by `[]]` and `[!]]` respectively.
-     * The `-` character can be specified inside a character sequence pattern by
-     * placing it at the start or the end, e.g. `[abc-]`.
-     *
-     * When a `[` does not have a closing `]` before the end of the string then
-     * the `[` will be treated literally.
-     */
-    pub fn new(pattern: &str) -> Pattern {
-
-        let chars = pattern.chars().to_owned_vec();
-        let mut tokens = ~[];
-        let mut i = 0;
-
-        while i < chars.len() {
-            match chars[i] {
-                '?' => {
-                    tokens.push(AnyChar);
-                    i += 1;
-                }
-                '*' => {
-                    // *, **, ***, ****, ... are all equivalent
-                    while i < chars.len() && chars[i] == '*' {
-                        i += 1;
-                    }
-                    tokens.push(AnySequence);
-                }
-                '[' => {
-
-                    if i <= chars.len() - 4 && chars[i + 1] == '!' {
-                        match chars.slice_from(i + 3).position_elem(&']') {
-                            None => (),
-                            Some(j) => {
-                                let chars = chars.slice(i + 2, i + 3 + j);
-                                let cs = parse_char_specifiers(chars);
-                                tokens.push(AnyExcept(cs));
-                                i += j + 4;
-                                continue;
-                            }
-                        }
-                    }
-                    else if i <= chars.len() - 3 && chars[i + 1] != '!' {
-                        match chars.slice_from(i + 2).position_elem(&']') {
-                            None => (),
-                            Some(j) => {
-                                let cs = parse_char_specifiers(chars.slice(i + 1, i + 2 + j));
-                                tokens.push(AnyWithin(cs));
-                                i += j + 3;
-                                continue;
-                            }
-                        }
-                    }
-
-                    // if we get here then this is not a valid range pattern
-                    tokens.push(Char('['));
-                    i += 1;
-                }
-                c => {
-                    tokens.push(Char(c));
-                    i += 1;
-                }
-            }
-        }
-
-        Pattern { tokens: tokens }
-    }
-
-    /**
-     * Escape metacharacters within the given string by surrounding them in
-     * brackets. The resulting string will, when compiled into a `Pattern`,
-     * match the input string and nothing else.
-     */
-    pub fn escape(s: &str) -> ~str {
-        let mut escaped = ~"";
-        for c in s.chars() {
-            match c {
-                // note that ! does not need escaping because it is only special inside brackets
-                '?' | '*' | '[' | ']' => {
-                    escaped.push_char('[');
-                    escaped.push_char(c);
-                    escaped.push_char(']');
-                }
-                c => {
-                    escaped.push_char(c);
-                }
-            }
-        }
-        escaped
-    }
-
-    /**
-     * Return if the given `str` matches this `Pattern` using the default
-     * match options (i.e. `MatchOptions::new()`).
-     *
-     * # Example
-     *
-     * ```rust
-     * use extra::glob::Pattern;
-     *
-     * assert!(Pattern::new("c?t").matches("cat"));
-     * assert!(Pattern::new("k[!e]tteh").matches("kitteh"));
-     * assert!(Pattern::new("d*g").matches("doog"));
-     * ```
-     */
-    pub fn matches(&self, str: &str) -> bool {
-        self.matches_with(str, MatchOptions::new())
-    }
-
-    /**
-     * Return if the given `Path`, when converted to a `str`, matches this `Pattern`
-     * using the default match options (i.e. `MatchOptions::new()`).
-     */
-    pub fn matches_path(&self, path: &Path) -> bool {
-        // FIXME (#9639): This needs to handle non-utf8 paths
-        path.as_str().map_or(false, |s| {
-            self.matches(s)
-        })
-    }
-
-    /**
-     * Return if the given `str` matches this `Pattern` using the specified match options.
-     */
-    pub fn matches_with(&self, str: &str, options: MatchOptions) -> bool {
-        self.matches_from(None, str, 0, options) == Match
-    }
-
-    /**
-     * Return if the given `Path`, when converted to a `str`, matches this `Pattern`
-     * using the specified match options.
-     */
-    pub fn matches_path_with(&self, path: &Path, options: MatchOptions) -> bool {
-        // FIXME (#9639): This needs to handle non-utf8 paths
-        path.as_str().map_or(false, |s| {
-            self.matches_with(s, options)
-        })
-    }
-
-    fn matches_from(&self,
-                    mut prev_char: Option<char>,
-                    mut file: &str,
-                    i: uint,
-                    options: MatchOptions) -> MatchResult {
-
-        let require_literal = |c| {
-            (options.require_literal_separator && is_sep(c)) ||
-            (options.require_literal_leading_dot && c == '.'
-             && is_sep(prev_char.unwrap_or('/')))
-        };
-
-        for (ti, token) in self.tokens.slice_from(i).iter().enumerate() {
-            match *token {
-                AnySequence => {
-                    loop {
-                        match self.matches_from(prev_char, file, i + ti + 1, options) {
-                            SubPatternDoesntMatch => (), // keep trying
-                            m => return m,
-                        }
-
-                        if file.is_empty() {
-                            return EntirePatternDoesntMatch;
-                        }
-
-                        let (c, next) = file.slice_shift_char();
-                        if require_literal(c) {
-                            return SubPatternDoesntMatch;
-                        }
-                        prev_char = Some(c);
-                        file = next;
-                    }
-                }
-                _ => {
-                    if file.is_empty() {
-                        return EntirePatternDoesntMatch;
-                    }
-
-                    let (c, next) = file.slice_shift_char();
-                    let matches = match *token {
-                        AnyChar => {
-                            !require_literal(c)
-                        }
-                        AnyWithin(ref specifiers) => {
-                            !require_literal(c) && in_char_specifiers(*specifiers, c, options)
-                        }
-                        AnyExcept(ref specifiers) => {
-                            !require_literal(c) && !in_char_specifiers(*specifiers, c, options)
-                        }
-                        Char(c2) => {
-                            chars_eq(c, c2, options.case_sensitive)
-                        }
-                        AnySequence => {
-                            unreachable!()
-                        }
-                    };
-                    if !matches {
-                        return SubPatternDoesntMatch;
-                    }
-                    prev_char = Some(c);
-                    file = next;
-                }
-            }
-        }
-
-        if file.is_empty() {
-            Match
-        } else {
-            SubPatternDoesntMatch
-        }
-    }
-
-}
-
-fn parse_char_specifiers(s: &[char]) -> ~[CharSpecifier] {
-    let mut cs = ~[];
-    let mut i = 0;
-    while i < s.len() {
-        if i + 3 <= s.len() && s[i + 1] == '-' {
-            cs.push(CharRange(s[i], s[i + 2]));
-            i += 3;
-        } else {
-            cs.push(SingleChar(s[i]));
-            i += 1;
-        }
-    }
-    cs
-}
-
-fn in_char_specifiers(specifiers: &[CharSpecifier], c: char, options: MatchOptions) -> bool {
-
-    for &specifier in specifiers.iter() {
-        match specifier {
-            SingleChar(sc) => {
-                if chars_eq(c, sc, options.case_sensitive) {
-                    return true;
-                }
-            }
-            CharRange(start, end) => {
-
-                // FIXME: work with non-ascii chars properly (issue #1347)
-                if !options.case_sensitive && c.is_ascii() && start.is_ascii() && end.is_ascii() {
-
-                    let start = start.to_ascii().to_lower();
-                    let end = end.to_ascii().to_lower();
-
-                    let start_up = start.to_upper();
-                    let end_up = end.to_upper();
-
-                    // only allow case insensitive matching when
-                    // both start and end are within a-z or A-Z
-                    if start != start_up && end != end_up {
-                        let start = start.to_char();
-                        let end = end.to_char();
-                        let c = c.to_ascii().to_lower().to_char();
-                        if c >= start && c <= end {
-                            return true;
-                        }
-                    }
-                }
-
-                if c >= start && c <= end {
-                    return true;
-                }
-            }
-        }
-    }
-
-    false
-}
-
-/// A helper function to determine if two chars are (possibly case-insensitively) equal.
-fn chars_eq(a: char, b: char, case_sensitive: bool) -> bool {
-    if cfg!(windows) && path::windows::is_sep(a) && path::windows::is_sep(b) {
-        true
-    } else if !case_sensitive && a.is_ascii() && b.is_ascii() {
-        // FIXME: work with non-ascii chars properly (issue #1347)
-        a.to_ascii().eq_ignore_case(b.to_ascii())
-    } else {
-        a == b
-    }
-}
-
-/**
- * Configuration options to modify the behaviour of `Pattern::matches_with(..)`
- */
-#[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, IterBytes, Default)]
-pub struct MatchOptions {
-
-    /**
-     * Whether or not patterns should be matched in a case-sensitive manner. This
-     * currently only considers upper/lower case relationships between ASCII characters,
-     * but in future this might be extended to work with Unicode.
-     */
-    priv case_sensitive: bool,
-
-    /**
-     * If this is true then path-component separator characters (e.g. `/` on Posix)
-     * must be matched by a literal `/`, rather than by `*` or `?` or `[...]`
-     */
-    priv require_literal_separator: bool,
-
-    /**
-     * If this is true then paths that contain components that start with a `.` will
-     * not match unless the `.` appears literally in the pattern: `*`, `?` or `[...]`
-     * will not match. This is useful because such files are conventionally considered
-     * hidden on Unix systems and it might be desirable to skip them when listing files.
-     */
-    priv require_literal_leading_dot: bool
-}
-
-impl MatchOptions {
-
-    /**
-     * Constructs a new `MatchOptions` with default field values. This is used
-     * when calling functions that do not take an explicit `MatchOptions` parameter.
-     *
-     * This function always returns this value:
-     *
-     * ```rust,ignore
-     * MatchOptions {
-     *     case_sensitive: true,
-     *     require_literal_separator: false.
-     *     require_literal_leading_dot: false
-     * }
-     * ```
-     */
-    pub fn new() -> MatchOptions {
-        MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        }
-    }
-
-}
-
-#[cfg(test)]
-mod test {
-    use std::os;
-    use super::*;
-
-    #[test]
-    fn test_absolute_pattern() {
-        // assume that the filesystem is not empty!
-        assert!(glob("/*").next().is_some());
-        assert!(glob("//").next().is_none());
-
-        // check windows absolute paths with host/device components
-        let root_with_device = os::getcwd().root_path().unwrap().join("*");
-        // FIXME (#9639): This needs to handle non-utf8 paths
-        assert!(glob(root_with_device.as_str().unwrap()).next().is_some());
-    }
-
-    #[test]
-    fn test_wildcard_optimizations() {
-        assert!(Pattern::new("a*b").matches("a___b"));
-        assert!(Pattern::new("a**b").matches("a___b"));
-        assert!(Pattern::new("a***b").matches("a___b"));
-        assert!(Pattern::new("a*b*c").matches("abc"));
-        assert!(!Pattern::new("a*b*c").matches("abcd"));
-        assert!(Pattern::new("a*b*c").matches("a_b_c"));
-        assert!(Pattern::new("a*b*c").matches("a___b___c"));
-        assert!(Pattern::new("abc*abc*abc").matches("abcabcabcabcabcabcabc"));
-        assert!(!Pattern::new("abc*abc*abc").matches("abcabcabcabcabcabcabca"));
-        assert!(Pattern::new("a*a*a*a*a*a*a*a*a").matches("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
-        assert!(Pattern::new("a*b[xyz]c*d").matches("abxcdbxcddd"));
-    }
-
-    #[test]
-    fn test_lots_of_files() {
-        // this is a good test because it touches lots of differently named files
-        glob("/*/*/*/*").skip(10000).next();
-    }
-
-    #[test]
-    fn test_range_pattern() {
-
-        let pat = Pattern::new("a[0-9]b");
-        for i in range(0, 10) {
-            assert!(pat.matches(format!("a{}b", i)));
-        }
-        assert!(!pat.matches("a_b"));
-
-        let pat = Pattern::new("a[!0-9]b");
-        for i in range(0, 10) {
-            assert!(!pat.matches(format!("a{}b", i)));
-        }
-        assert!(pat.matches("a_b"));
-
-        let pats = ["[a-z123]", "[1a-z23]", "[123a-z]"];
-        for &p in pats.iter() {
-            let pat = Pattern::new(p);
-            for c in "abcdefghijklmnopqrstuvwxyz".chars() {
-                assert!(pat.matches(c.to_str()));
-            }
-            for c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ".chars() {
-                let options = MatchOptions {case_sensitive: false, .. MatchOptions::new()};
-                assert!(pat.matches_with(c.to_str(), options));
-            }
-            assert!(pat.matches("1"));
-            assert!(pat.matches("2"));
-            assert!(pat.matches("3"));
-        }
-
-        let pats = ["[abc-]", "[-abc]", "[a-c-]"];
-        for &p in pats.iter() {
-            let pat = Pattern::new(p);
-            assert!(pat.matches("a"));
-            assert!(pat.matches("b"));
-            assert!(pat.matches("c"));
-            assert!(pat.matches("-"));
-            assert!(!pat.matches("d"));
-        }
-
-        let pat = Pattern::new("[2-1]");
-        assert!(!pat.matches("1"));
-        assert!(!pat.matches("2"));
-
-        assert!(Pattern::new("[-]").matches("-"));
-        assert!(!Pattern::new("[!-]").matches("-"));
-    }
-
-    #[test]
-    fn test_unclosed_bracket() {
-        // unclosed `[` should be treated literally
-        assert!(Pattern::new("abc[def").matches("abc[def"));
-        assert!(Pattern::new("abc[!def").matches("abc[!def"));
-        assert!(Pattern::new("abc[").matches("abc["));
-        assert!(Pattern::new("abc[!").matches("abc[!"));
-        assert!(Pattern::new("abc[d").matches("abc[d"));
-        assert!(Pattern::new("abc[!d").matches("abc[!d"));
-        assert!(Pattern::new("abc[]").matches("abc[]"));
-        assert!(Pattern::new("abc[!]").matches("abc[!]"));
-    }
-
-    #[test]
-    fn test_pattern_matches() {
-        let txt_pat = Pattern::new("*hello.txt");
-        assert!(txt_pat.matches("hello.txt"));
-        assert!(txt_pat.matches("gareth_says_hello.txt"));
-        assert!(txt_pat.matches("some/path/to/hello.txt"));
-        assert!(txt_pat.matches("some\\path\\to\\hello.txt"));
-        assert!(txt_pat.matches("/an/absolute/path/to/hello.txt"));
-        assert!(!txt_pat.matches("hello.txt-and-then-some"));
-        assert!(!txt_pat.matches("goodbye.txt"));
-
-        let dir_pat = Pattern::new("*some/path/to/hello.txt");
-        assert!(dir_pat.matches("some/path/to/hello.txt"));
-        assert!(dir_pat.matches("a/bigger/some/path/to/hello.txt"));
-        assert!(!dir_pat.matches("some/path/to/hello.txt-and-then-some"));
-        assert!(!dir_pat.matches("some/other/path/to/hello.txt"));
-    }
-
-    #[test]
-    fn test_pattern_escape() {
-        let s = "_[_]_?_*_!_";
-        assert_eq!(Pattern::escape(s), ~"_[[]_[]]_[?]_[*]_!_");
-        assert!(Pattern::new(Pattern::escape(s)).matches(s));
-    }
-
-    #[test]
-    fn test_pattern_matches_case_insensitive() {
-
-        let pat = Pattern::new("aBcDeFg");
-        let options = MatchOptions {
-            case_sensitive: false,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        };
-
-        assert!(pat.matches_with("aBcDeFg", options));
-        assert!(pat.matches_with("abcdefg", options));
-        assert!(pat.matches_with("ABCDEFG", options));
-        assert!(pat.matches_with("AbCdEfG", options));
-    }
-
-    #[test]
-    fn test_pattern_matches_case_insensitive_range() {
-
-        let pat_within = Pattern::new("[a]");
-        let pat_except = Pattern::new("[!a]");
-
-        let options_case_insensitive = MatchOptions {
-            case_sensitive: false,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        };
-        let options_case_sensitive = MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        };
-
-        assert!(pat_within.matches_with("a", options_case_insensitive));
-        assert!(pat_within.matches_with("A", options_case_insensitive));
-        assert!(!pat_within.matches_with("A", options_case_sensitive));
-
-        assert!(!pat_except.matches_with("a", options_case_insensitive));
-        assert!(!pat_except.matches_with("A", options_case_insensitive));
-        assert!(pat_except.matches_with("A", options_case_sensitive));
-    }
-
-    #[test]
-    fn test_pattern_matches_require_literal_separator() {
-
-        let options_require_literal = MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: true,
-            require_literal_leading_dot: false
-        };
-        let options_not_require_literal = MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        };
-
-        assert!(Pattern::new("abc/def").matches_with("abc/def", options_require_literal));
-        assert!(!Pattern::new("abc?def").matches_with("abc/def", options_require_literal));
-        assert!(!Pattern::new("abc*def").matches_with("abc/def", options_require_literal));
-        assert!(!Pattern::new("abc[/]def").matches_with("abc/def", options_require_literal));
-
-        assert!(Pattern::new("abc/def").matches_with("abc/def", options_not_require_literal));
-        assert!(Pattern::new("abc?def").matches_with("abc/def", options_not_require_literal));
-        assert!(Pattern::new("abc*def").matches_with("abc/def", options_not_require_literal));
-        assert!(Pattern::new("abc[/]def").matches_with("abc/def", options_not_require_literal));
-    }
-
-    #[test]
-    fn test_pattern_matches_require_literal_leading_dot() {
-
-        let options_require_literal_leading_dot = MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: false,
-            require_literal_leading_dot: true
-        };
-        let options_not_require_literal_leading_dot = MatchOptions {
-            case_sensitive: true,
-            require_literal_separator: false,
-            require_literal_leading_dot: false
-        };
-
-        let f = |options| Pattern::new("*.txt").matches_with(".hello.txt", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(!f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new(".*.*").matches_with(".hello.txt", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new("aaa/bbb/*").matches_with("aaa/bbb/.ccc", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(!f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new("aaa/bbb/*").matches_with("aaa/bbb/c.c.c.", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new("aaa/bbb/.*").matches_with("aaa/bbb/.ccc", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new("aaa/?bbb").matches_with("aaa/.bbb", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(!f(options_require_literal_leading_dot));
-
-        let f = |options| Pattern::new("aaa/[.]bbb").matches_with("aaa/.bbb", options);
-        assert!(f(options_not_require_literal_leading_dot));
-        assert!(!f(options_require_literal_leading_dot));
-    }
-
-    #[test]
-    fn test_matches_path() {
-        // on windows, (Path::new("a/b").as_str().unwrap() == "a\\b"), so this
-        // tests that / and \ are considered equivalent on windows
-        assert!(Pattern::new("a/b").matches_path(&Path::new("a/b")));
-    }
-}
diff --git a/src/libextra/lib.rs b/src/libextra/lib.rs
index 5a4fedd2b2a..bb89915dfd1 100644
--- a/src/libextra/lib.rs
+++ b/src/libextra/lib.rs
@@ -67,10 +67,8 @@ pub mod ebml;
 pub mod getopts;
 pub mod json;
 pub mod tempfile;
-pub mod glob;
 pub mod term;
 pub mod time;
-pub mod arena;
 pub mod base64;
 pub mod workcache;
 pub mod enum_set;