path2: Replace the path module outright

Remove the old path.
Rename path2 to path.
Update all clients for the new path.

Also make some miscellaneous changes to the Path APIs to help the
adoption process.

15 files changed, 792 insertions, 621 deletions

diff --git a/src/librustpkg/api.rs b/src/librustpkg/api.rs
index 390a09d4aa3..6e0908d2a4f 100644
--- a/src/librustpkg/api.rs
+++ b/src/librustpkg/api.rs
@@ -43,18 +43,18 @@ pub fn new_default_context(c: workcache::Context, p: Path) -> BuildContext {
 }
 
 fn file_is_fresh(path: &str, in_hash: &str) -> bool {
-    let path = Path(path);
+    let path = Path::from_str(path);
     os::path_exists(&path) && in_hash == digest_file_with_date(&path)
 }
 
 fn binary_is_fresh(path: &str, in_hash: &str) -> bool {
-    let path = Path(path);
+    let path = Path::from_str(path);
     os::path_exists(&path) && in_hash == digest_only_date(&path)
 }
 
 pub fn new_workcache_context(p: &Path) -> workcache::Context {
-    let db_file = p.push("rustpkg_db.json"); // ??? probably wrong
-    debug2!("Workcache database file: {}", db_file.to_str());
+    let db_file = p.join_str("rustpkg_db.json"); // ??? probably wrong
+    debug2!("Workcache database file: {}", db_file.display());
     let db = RWArc::new(Database::new(db_file));
     let lg = RWArc::new(Logger::new());
     let cfg = Arc::new(TreeMap::new());
@@ -73,7 +73,7 @@ pub fn build_lib(sysroot: Path, root: Path, name: ~str, version: Version,
         source_workspace: root.clone(),
         build_in_destination: false,
         destination_workspace: root.clone(),
-        start_dir: root.push("src").push(name),
+        start_dir: root.join_many_str(["src", name.as_slice()]),
         id: PkgId{ version: version, ..PkgId::new(name)},
         // n.b. This assumes the package only has one crate
         libs: ~[mk_crate(lib)],
@@ -91,7 +91,7 @@ pub fn build_exe(sysroot: Path, root: Path, name: ~str, version: Version,
         source_workspace: root.clone(),
         build_in_destination: false,
         destination_workspace: root.clone(),
-        start_dir: root.push("src").push(name),
+        start_dir: root.join_many_str(["src", name.as_slice()]),
         id: PkgId{ version: version, ..PkgId::new(name)},
         libs: ~[],
         // n.b. This assumes the package only has one crate
diff --git a/src/librustpkg/context.rs b/src/librustpkg/context.rs
index 3b3cfe45b7a..41b04c389ae 100644
--- a/src/librustpkg/context.rs
+++ b/src/librustpkg/context.rs
@@ -123,7 +123,7 @@ impl Context {
 
     /// Debugging
     pub fn sysroot_str(&self) -> ~str {
-        self.sysroot.to_str()
+        self.sysroot.as_str().unwrap().to_owned()
     }
 
     // Hack so that rustpkg can run either out of a rustc target dir,
@@ -132,7 +132,11 @@ impl Context {
         if !in_target(&self.sysroot) {
             self.sysroot.clone()
         } else {
-            self.sysroot.pop().pop().pop()
+            let mut p = self.sysroot.clone();
+            p.pop();
+            p.pop();
+            p.pop();
+            p
         }
     }
 
@@ -150,8 +154,10 @@ impl Context {
 /// rustpkg from a Rust target directory. This is part of a
 /// kludgy hack used to adjust the sysroot.
 pub fn in_target(sysroot: &Path) -> bool {
-    debug2!("Checking whether {} is in target", sysroot.to_str());
-    os::path_is_dir(&sysroot.pop().pop().push("rustc"))
+    debug2!("Checking whether {} is in target", sysroot.display());
+    let mut p = sysroot.dir_path();
+    p.set_filename_str("rustc");
+    os::path_is_dir(&p)
 }
 
 impl RustcFlags {
diff --git a/src/librustpkg/installed_packages.rs b/src/librustpkg/installed_packages.rs
index a3b807d1fc5..995f484a4e6 100644
--- a/src/librustpkg/installed_packages.rs
+++ b/src/librustpkg/installed_packages.rs
@@ -17,27 +17,33 @@ use std::os;
 pub fn list_installed_packages(f: &fn(&PkgId) -> bool) -> bool  {
     let workspaces = rust_path();
     for p in workspaces.iter() {
-        let binfiles = os::list_dir(&p.push("bin"));
+        let binfiles = os::list_dir(&p.join_str("bin"));
         for exec in binfiles.iter() {
-            let p = Path(*exec);
-            let exec_path = p.filestem();
-            do exec_path.iter().advance |s| {
-                f(&PkgId::new(*s))
-            };
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            match exec.filestem_str() {
+                None => (),
+                Some(exec_path) => {
+                    if !f(&PkgId::new(exec_path)) {
+                        return false;
+                    }
+                }
+            }
         }
-        let libfiles = os::list_dir(&p.push("lib"));
+        let libfiles = os::list_dir(&p.join_str("lib"));
         for lib in libfiles.iter() {
-            let lib = Path(*lib);
-            debug2!("Full name: {}", lib.to_str());
-            match has_library(&lib) {
+            debug2!("Full name: {}", lib.display());
+            match has_library(lib) {
                 Some(basename) => {
+                    let parent = p.join_str("lib");
                     debug2!("parent = {}, child = {}",
-                            p.push("lib").to_str(), lib.to_str());
-                    let rel_p = p.push("lib/").get_relative_to(&lib);
-                    debug2!("Rel: {}", rel_p.to_str());
-                    let rel_path = rel_p.push(basename).to_str();
-                    debug2!("Rel name: {}", rel_path);
-                    f(&PkgId::new(rel_path));
+                            parent.display(), lib.display());
+                    let rel_p = lib.path_relative_from(&parent).unwrap();
+                    debug2!("Rel: {}", rel_p.display());
+                    let rel_path = rel_p.join_str(basename);
+                    do rel_path.with_display_str |s| {
+                        debug2!("Rel name: {}", s);
+                        f(&PkgId::new(s));
+                    }
                 }
                 None => ()
             }
@@ -48,10 +54,9 @@ pub fn list_installed_packages(f: &fn(&PkgId) -> bool) -> bool  {
 
 pub fn has_library(p: &Path) -> Option<~str> {
     let files = os::list_dir(p);
-    for q in files.iter() {
-        let as_path = Path(*q);
-        if as_path.filetype() == Some(os::consts::DLL_SUFFIX) {
-            let stuff : &str = as_path.filestem().expect("has_library: weird path");
+    for path in files.iter() {
+        if path.extension_str() == Some(os::consts::DLL_EXTENSION) {
+            let stuff : &str = path.filestem_str().expect("has_library: weird path");
             let mut stuff2 = stuff.split_str_iter(&"-");
             let stuff3: ~[&str] = stuff2.collect();
             // argh
@@ -67,8 +72,10 @@ pub fn package_is_installed(p: &PkgId) -> bool {
     do list_installed_packages() |installed| {
         if installed == p {
             is_installed = true;
+            false
+        } else {
+            true
         }
-        false
     };
     is_installed
 }
diff --git a/src/librustpkg/package_id.rs b/src/librustpkg/package_id.rs
index c06e197787c..bd22f1da913 100644
--- a/src/librustpkg/package_id.rs
+++ b/src/librustpkg/package_id.rs
@@ -59,14 +59,14 @@ impl PkgId {
             }
         };
 
-        let path = Path(s);
-        if path.is_absolute {
+        let path = Path::from_str(s);
+        if !path.is_relative() {
             return cond.raise((path, ~"absolute pkgid"));
         }
-        if path.components.len() < 1 {
+        if path.filename().is_none() {
             return cond.raise((path, ~"0-length pkgid"));
         }
-        let short_name = path.filestem().expect(format!("Strange path! {}", s));
+        let short_name = path.filestem_str().expect(format!("Strange path! {}", s));
 
         let version = match given_version {
             Some(v) => v,
@@ -87,9 +87,11 @@ impl PkgId {
     }
 
     pub fn hash(&self) -> ~str {
-        format!("{}-{}-{}", self.path.to_str(),
-                hash(self.path.to_str() + self.version.to_str()),
-                self.version.to_str())
+        // FIXME (#9639): hash should take a &[u8] so we can hash the real path
+        do self.path.with_display_str |s| {
+            let vers = self.version.to_str();
+            format!("{}-{}-{}", s, hash(s + vers), vers)
+        }
     }
 
     pub fn short_name_with_version(&self) -> ~str {
@@ -98,7 +100,7 @@ impl PkgId {
 
     /// True if the ID has multiple components
     pub fn is_complex(&self) -> bool {
-        self.short_name != self.path.to_str()
+        self.short_name.as_bytes() != self.path.as_vec()
     }
 
     pub fn prefixes_iter(&self) -> Prefixes {
@@ -115,7 +117,7 @@ impl PkgId {
 
 pub fn prefixes_iter(p: &Path) -> Prefixes {
     Prefixes {
-        components: p.components().to_owned(),
+        components: p.str_component_iter().map(|x|x.unwrap().to_owned()).to_owned_vec(),
         remaining: ~[]
     }
 }
@@ -133,9 +135,10 @@ impl Iterator<(Path, Path)> for Prefixes {
         }
         else {
             let last = self.components.pop();
-            self.remaining.push(last);
+            self.remaining.unshift(last);
             // converting to str and then back is a little unfortunate
-            Some((Path(self.components.to_str()), Path(self.remaining.to_str())))
+            Some((Path::from_str(self.components.connect("/")),
+                  Path::from_str(self.remaining.connect("/"))))
         }
     }
 }
@@ -143,7 +146,7 @@ impl Iterator<(Path, Path)> for Prefixes {
 impl ToStr for PkgId {
     fn to_str(&self) -> ~str {
         // should probably use the filestem and not the whole path
-        format!("{}-{}", self.path.to_str(), self.version.to_str())
+        format!("{}-{}", self.path.as_str().unwrap(), self.version.to_str())
     }
 }
 
diff --git a/src/librustpkg/package_source.rs b/src/librustpkg/package_source.rs
index 4ffc57d7512..a924694cca5 100644
--- a/src/librustpkg/package_source.rs
+++ b/src/librustpkg/package_source.rs
@@ -58,9 +58,9 @@ impl ToStr for PkgSrc {
     fn to_str(&self) -> ~str {
         format!("Package ID {} in start dir {} [workspaces = {} -> {}]",
                 self.id.to_str(),
-                self.start_dir.to_str(),
-                self.source_workspace.to_str(),
-                self.destination_workspace.to_str())
+                self.start_dir.display(),
+                self.source_workspace.display(),
+                self.destination_workspace.display())
     }
 }
 condition! {
@@ -79,8 +79,8 @@ impl PkgSrc {
         debug2!("Checking package source for package ID {}, \
                 workspace = {} -> {}, use_rust_path_hack = {:?}",
                 id.to_str(),
-                source_workspace.to_str(),
-                destination_workspace.to_str(),
+                source_workspace.display(),
+                destination_workspace.display(),
                 use_rust_path_hack);
 
         let mut destination_workspace = destination_workspace.clone();
@@ -94,22 +94,27 @@ impl PkgSrc {
         } else {
             // We search for sources under both src/ and build/ , because build/ is where
             // automatically-checked-out sources go.
-            let result = source_workspace.push("src").push_rel(&id.path.pop()).push(format!("{}-{}",
-                                                         id.short_name, id.version.to_str()));
+            let mut result = source_workspace.join_str("src");
+            result.push_path(&id.path.dir_path());
+            result.push_str(format!("{}-{}", id.short_name, id.version.to_str()));
+            to_try.push(result);
+            let mut result = source_workspace.join_str("src");
+            result.push_path(&id.path);
             to_try.push(result);
-            to_try.push(source_workspace.push("src").push_rel(&id.path));
 
-            let result = build_dir.push("src").push_rel(&id.path.pop()).push(format!("{}-{}",
-                                                         id.short_name, id.version.to_str()));
+            let mut result = build_dir.join_str("src");
+            result.push_path(&id.path.dir_path());
+            result.push_str(format!("{}-{}", id.short_name, id.version.to_str()));
             to_try.push(result.clone());
             output_names.push(result);
-            let other_result = build_dir.push("src").push_rel(&id.path);
+            let mut other_result = build_dir.join_str("src");
+            other_result.push_path(&id.path);
             to_try.push(other_result.clone());
             output_names.push(other_result);
 
         }
 
-        debug2!("Checking dirs: {:?}", to_try.map(|s| s.to_str()).connect(":"));
+        debug2!("Checking dirs: {:?}", to_try.map(|p| p.to_display_str()).connect(":"));
 
         let path = to_try.iter().find(|&d| os::path_exists(d));
 
@@ -123,14 +128,14 @@ impl PkgSrc {
                 // See if any of the prefixes of this package ID form a valid package ID
                 // That is, is this a package ID that points into the middle of a workspace?
                 for (prefix, suffix) in id.prefixes_iter() {
-                    let package_id = PkgId::new(prefix.to_str());
-                    let path = build_dir.push_rel(&package_id.path);
-                    debug2!("in loop: checking if {} is a directory", path.to_str());
+                    let package_id = PkgId::new(prefix.as_str().unwrap());
+                    let path = build_dir.join_path(&package_id.path);
+                    debug2!("in loop: checking if {} is a directory", path.display());
                     if os::path_is_dir(&path) {
                         let ps = PkgSrc::new(source_workspace,
                                              destination_workspace,
                                              use_rust_path_hack,
-                                             PkgId::new(prefix.to_str()));
+                                             package_id);
                         match ps {
                             PkgSrc {
                                 source_workspace: source,
@@ -141,7 +146,7 @@ impl PkgSrc {
                                     source_workspace: source.clone(),
                                     build_in_destination: build_in_destination,
                                     destination_workspace: destination,
-                                    start_dir: start.push_rel(&suffix),
+                                    start_dir: start.join_path(&suffix),
                                     id: id,
                                     libs: ~[],
                                     mains: ~[],
@@ -159,7 +164,7 @@ impl PkgSrc {
                 // Ok, no prefixes work, so try fetching from git
                 let mut ok_d = None;
                 for w in output_names.iter() {
-                    debug2!("Calling fetch_git on {}", w.to_str());
+                    debug2!("Calling fetch_git on {}", w.display());
                     let target_dir_opt = PkgSrc::fetch_git(w, &id);
                     for p in target_dir_opt.iter() {
                         ok_d = Some(p.clone());
@@ -209,9 +214,9 @@ impl PkgSrc {
             }
         };
         debug2!("3. build_in_destination = {:?}", build_in_destination);
-        debug2!("source: {} dest: {}", source_workspace.to_str(), destination_workspace.to_str());
+        debug2!("source: {} dest: {}", source_workspace.display(), destination_workspace.display());
 
-        debug2!("For package id {}, returning {}", id.to_str(), dir.to_str());
+        debug2!("For package id {}, returning {}", id.to_str(), dir.display());
 
         if !os::path_is_dir(&dir) {
             cond.raise((id.clone(), ~"supplied path for package dir is a \
@@ -240,8 +245,8 @@ impl PkgSrc {
         use conditions::git_checkout_failed::cond;
 
         debug2!("Checking whether {} (path = {}) exists locally. Cwd = {}, does it? {:?}",
-                pkgid.to_str(), pkgid.path.to_str(),
-                os::getcwd().to_str(),
+                pkgid.to_str(), pkgid.path.display(),
+                os::getcwd().display(),
                 os::path_exists(&pkgid.path));
 
         match safe_git_clone(&pkgid.path, &pkgid.version, local) {
@@ -250,14 +255,14 @@ impl PkgSrc {
                 Some(local.clone())
             }
             DirToUse(clone_target) => {
-                if pkgid.path.components().len() < 2 {
+                if pkgid.path.component_iter().nth(1).is_none() {
                     // If a non-URL, don't bother trying to fetch
                     return None;
                 }
 
-                let url = format!("https://{}", pkgid.path.to_str());
+                let url = format!("https://{}", pkgid.path.as_str().unwrap());
                 debug2!("Fetching package: git clone {} {} [version={}]",
-                        url, clone_target.to_str(), pkgid.version.to_str());
+                        url, clone_target.display(), pkgid.version.to_str());
 
                 let mut failed = false;
 
@@ -273,7 +278,7 @@ impl PkgSrc {
 
                 // Move clone_target to local.
                 // First, create all ancestor directories.
-                let moved = make_dir_rwx_recursive(&local.pop())
+                let moved = make_dir_rwx_recursive(&local.dir_path())
                     && os::rename_file(&clone_target, local);
                 if moved { Some(local.clone()) }
                     else { None }
@@ -284,28 +289,31 @@ impl PkgSrc {
     // If a file named "pkg.rs" in the start directory exists,
     // return the path for it. Otherwise, None
     pub fn package_script_option(&self) -> Option<Path> {
-        let maybe_path = self.start_dir.push("pkg.rs");
-        debug2!("package_script_option: checking whether {} exists", maybe_path.to_str());
+        let maybe_path = self.start_dir.join_str("pkg.rs");
+        debug2!("package_script_option: checking whether {} exists", maybe_path.display());
         if os::path_exists(&maybe_path) {
             Some(maybe_path)
-        }
-        else {
+        } else {
             None
         }
     }
 
     /// True if the given path's stem is self's pkg ID's stem
     fn stem_matches(&self, p: &Path) -> bool {
-        p.filestem().map_default(false, |p| { p == self.id.short_name.as_slice() })
+        p.filestem().map_default(false, |p| { p == self.id.short_name.as_bytes() })
     }
 
     pub fn push_crate(cs: &mut ~[Crate], prefix: uint, p: &Path) {
-        assert!(p.components.len() > prefix);
-        let mut sub = Path("");
-        for c in p.components.slice(prefix, p.components.len()).iter() {
-            sub = sub.push(*c);
+        let mut it = p.component_iter().peekable();
+        if prefix > 0 {
+            it.nth(prefix-1); // skip elements
+        }
+        assert!(it.peek().is_some());
+        let mut sub = Path::from_str(".");
+        for c in it {
+            sub.push(c);
         }
-        debug2!("Will compile crate {}", sub.to_str());
+        debug2!("Will compile crate {}", sub.display());
         cs.push(Crate::new(&sub));
     }
 
@@ -318,10 +326,10 @@ impl PkgSrc {
     pub fn find_crates_with_filter(&mut self, filter: &fn(&str) -> bool) {
         use conditions::missing_pkg_files::cond;
 
-        let prefix = self.start_dir.components.len();
+        let prefix = self.start_dir.component_iter().len();
         debug2!("Matching against {}", self.id.short_name);
         do os::walk_dir(&self.start_dir) |pth| {
-            let maybe_known_crate_set = match pth.filename() {
+            let maybe_known_crate_set = match pth.filename_str() {
                 Some(filename) if filter(filename) => match filename {
                     "lib.rs" => Some(&mut self.libs),
                     "main.rs" => Some(&mut self.mains),
@@ -349,7 +357,7 @@ impl PkgSrc {
         }
 
         debug2!("In {}, found {} libs, {} mains, {} tests, {} benchs",
-               self.start_dir.to_str(),
+               self.start_dir.display(),
                self.libs.len(),
                self.mains.len(),
                self.tests.len(),
@@ -362,18 +370,17 @@ impl PkgSrc {
                     cfgs: &[~str],
                     what: OutputType) {
         for crate in crates.iter() {
-            let path = self.start_dir.push_rel(&crate.file).normalize();
-            debug2!("build_crates: compiling {}", path.to_str());
-            let path_str = path.to_str();
+            let path = self.start_dir.join_path(&crate.file);
+            debug2!("build_crates: compiling {}", path.display());
             let cfgs = crate.cfgs + cfgs;
 
             do ctx.workcache_context.with_prep(crate_tag(&path)) |prep| {
-                debug2!("Building crate {}, declaring it as an input", path.to_str());
-                prep.declare_input("file", path.to_str(),
+                debug2!("Building crate {}, declaring it as an input", path.display());
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                prep.declare_input("file", path.as_str().unwrap(),
                                    workcache_support::digest_file_with_date(&path));
                 let subpath = path.clone();
                 let subcfgs = cfgs.clone();
-                let subpath_str = path_str.clone();
                 let subcx = ctx.clone();
                 let id = self.id.clone();
                 let sub_dir = self.build_workspace().clone();
@@ -387,9 +394,14 @@ impl PkgSrc {
                                                sub_flags,
                                                subcfgs,
                                                false,
-                                               what).to_str();
-                    debug2!("Result of compiling {} was {}", subpath_str, result);
-                    result
+                                               what);
+                    // XXX: result is an Option<Path>. The following code did not take that
+                    // into account. I'm not sure if the workcache really likes seeing the
+                    // output as "Some(\"path\")". But I don't know what to do about it.
+                    // FIXME (#9639): This needs to handle non-utf8 paths
+                    let result = result.map(|p|p.as_str().unwrap());
+                    debug2!("Result of compiling {} was {}", subpath.display(), result.to_str());
+                    result.to_str()
                 }
             };
         }
@@ -403,10 +415,10 @@ impl PkgSrc {
         debug2!("In declare inputs, self = {}", self.to_str());
         for cs in to_do.iter() {
             for c in cs.iter() {
-                let path = self.start_dir.push_rel(&c.file).normalize();
-                debug2!("Declaring input: {}", path.to_str());
-                prep.declare_input("file",
-                                   path.to_str(),
+                let path = self.start_dir.join_path(&c.file);
+                debug2!("Declaring input: {}", path.display());
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                prep.declare_input("file", path.as_str().unwrap(),
                                    workcache_support::digest_file_with_date(&path.clone()));
             }
         }
@@ -422,7 +434,7 @@ impl PkgSrc {
         let tests = self.tests.clone();
         let benchs = self.benchs.clone();
         debug2!("Building libs in {}, destination = {}",
-               self.source_workspace.to_str(), self.build_workspace().to_str());
+               self.source_workspace.display(), self.build_workspace().display());
         self.build_crates(build_context, libs, cfgs, Lib);
         debug2!("Building mains");
         self.build_crates(build_context, mains, cfgs, Main);
@@ -447,7 +459,7 @@ impl PkgSrc {
         let crate_sets = [&self.libs, &self.mains, &self.tests, &self.benchs];
         for crate_set in crate_sets.iter() {
             for c in crate_set.iter() {
-                debug2!("Built crate: {}", c.file.to_str())
+                debug2!("Built crate: {}", c.file.display())
             }
         }
     }
diff --git a/src/librustpkg/path_util.rs b/src/librustpkg/path_util.rs
index fbb2255ad1c..34b387fc9a7 100644
--- a/src/librustpkg/path_util.rs
+++ b/src/librustpkg/path_util.rs
@@ -53,7 +53,7 @@ pub fn make_dir_rwx_recursive(p: &Path) -> bool { os::mkdir_recursive(p, U_RWX)
 /// True if there's a directory in <workspace> with
 /// pkgid's short name
 pub fn workspace_contains_package_id(pkgid: &PkgId, workspace: &Path) -> bool {
-    workspace_contains_package_id_(pkgid, workspace, |p| { p.push("src") }).is_some()
+    workspace_contains_package_id_(pkgid, workspace, |p| p.join_str("src")).is_some()
 }
 
 pub fn workspace_contains_package_id_(pkgid: &PkgId, workspace: &Path,
@@ -68,10 +68,9 @@ pub fn workspace_contains_package_id_(pkgid: &PkgId, workspace: &Path,
     let mut found = None;
     do os::walk_dir(&src_dir) |p| {
         if os::path_is_dir(p) {
-            if *p == src_dir.push_rel(&pkgid.path) || {
-                let pf = p.filename();
-                do pf.iter().any |pf| {
-                    let g = pf.to_str();
+            if *p == src_dir.join_path(&pkgid.path) || {
+                let pf = p.filename_str();
+                do pf.iter().any |&g| {
                     match split_version_general(g, '-') {
                         None => false,
                         Some((ref might_match, ref vers)) => {
@@ -89,9 +88,9 @@ pub fn workspace_contains_package_id_(pkgid: &PkgId, workspace: &Path,
     };
 
     if found.is_some() {
-        debug2!("Found {} in {}", pkgid.to_str(), workspace.to_str());
+        debug2!("Found {} in {}", pkgid.to_str(), workspace.display());
     } else {
-        debug2!("Didn't find {} in {}", pkgid.to_str(), workspace.to_str());
+        debug2!("Didn't find {} in {}", pkgid.to_str(), workspace.display());
     }
     found
 }
@@ -99,20 +98,24 @@ pub fn workspace_contains_package_id_(pkgid: &PkgId, workspace: &Path,
 /// Return the target-specific build subdirectory, pushed onto `base`;
 /// doesn't check that it exists or create it
 pub fn target_build_dir(workspace: &Path) -> Path {
-    workspace.push("build").push(host_triple())
+    let mut dir = workspace.join_str("build");
+    dir.push_str(host_triple());
+    dir
 }
 
 /// Return the target-specific lib subdirectory, pushed onto `base`;
 /// doesn't check that it exists or create it
 fn target_lib_dir(workspace: &Path) -> Path {
-    workspace.push("lib").push(host_triple())
+    let mut dir = workspace.join_str("lib");
+    dir.push_str(host_triple());
+    dir
 }
 
 /// Return the bin subdirectory, pushed onto `base`;
 /// doesn't check that it exists or create it
 /// note: this isn't target-specific
 fn target_bin_dir(workspace: &Path) -> Path {
-    workspace.push("bin")
+    workspace.join_str("bin")
 }
 
 /// Figure out what the executable name for <pkgid> in <workspace>'s build
@@ -121,12 +124,12 @@ pub fn built_executable_in_workspace(pkgid: &PkgId, workspace: &Path) -> Option<
     let mut result = target_build_dir(workspace);
     result = mk_output_path(Main, Build, pkgid, result);
     debug2!("built_executable_in_workspace: checking whether {} exists",
-           result.to_str());
+           result.display());
     if os::path_exists(&result) {
         Some(result)
     }
     else {
-        debug2!("built_executable_in_workspace: {} does not exist", result.to_str());
+        debug2!("built_executable_in_workspace: {} does not exist", result.display());
         None
     }
 }
@@ -148,12 +151,12 @@ fn output_in_workspace(pkgid: &PkgId, workspace: &Path, what: OutputType) -> Opt
     // should use a target-specific subdirectory
     result = mk_output_path(what, Build, pkgid, result);
     debug2!("output_in_workspace: checking whether {} exists",
-           result.to_str());
+           result.display());
     if os::path_exists(&result) {
         Some(result)
     }
     else {
-        error2!("output_in_workspace: {} does not exist", result.to_str());
+        error2!("output_in_workspace: {} does not exist", result.display());
         None
     }
 }
@@ -167,7 +170,8 @@ pub fn built_library_in_workspace(pkgid: &PkgId, workspace: &Path) -> Option<Pat
 /// Does the actual searching stuff
 pub fn installed_library_in_workspace(pkg_path: &Path, workspace: &Path) -> Option<Path> {
     // This could break once we're handling multiple versions better -- I should add a test for it
-    match pkg_path.filename() {
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    match pkg_path.filename_str() {
         None => None,
         Some(short_name) => library_in_workspace(pkg_path,
                                                  short_name,
@@ -189,10 +193,10 @@ pub fn library_in_workspace(path: &Path, short_name: &str, where: Target,
     // contents
 
     debug2!("short_name = {} where = {:?} workspace = {} \
-            prefix = {}", short_name, where, workspace.to_str(), prefix);
+            prefix = {}", short_name, where, workspace.display(), prefix);
 
     let dir_to_search = match where {
-        Build => target_build_dir(workspace).push_rel(path),
+        Build => target_build_dir(workspace).join_path(path),
         Install => target_lib_dir(workspace)
     };
 
@@ -201,28 +205,24 @@ pub fn library_in_workspace(path: &Path, short_name: &str, where: Target,
 
 // rustc doesn't use target-specific subdirectories
 pub fn system_library(sysroot: &Path, lib_name: &str) -> Option<Path> {
-    library_in(lib_name, &NoVersion, &sysroot.push("lib"))
+    library_in(lib_name, &NoVersion, &sysroot.join_str("lib"))
 }
 
 fn library_in(short_name: &str, version: &Version, dir_to_search: &Path) -> Option<Path> {
-    debug2!("Listing directory {}", dir_to_search.to_str());
+    debug2!("Listing directory {}", dir_to_search.display());
     let dir_contents = os::list_dir(dir_to_search);
     debug2!("dir has {:?} entries", dir_contents.len());
 
     let lib_prefix = format!("{}{}", os::consts::DLL_PREFIX, short_name);
-    let lib_filetype = os::consts::DLL_SUFFIX;
+    let lib_filetype = os::consts::DLL_EXTENSION;
 
     debug2!("lib_prefix = {} and lib_filetype = {}", lib_prefix, lib_filetype);
 
     // Find a filename that matches the pattern:
     // (lib_prefix)-hash-(version)(lib_suffix)
-    let paths = do dir_contents.iter().map |p| {
-        Path((*p).clone())
-    };
-
-    let mut libraries = do paths.filter |p| {
-        let extension = p.filetype();
-        debug2!("p = {}, p's extension is {:?}", p.to_str(), extension);
+    let mut libraries = do dir_contents.iter().filter |p| {
+        let extension = p.extension_str();
+        debug2!("p = {}, p's extension is {:?}", p.display(), extension);
         match extension {
             None => false,
             Some(ref s) => lib_filetype == *s
@@ -233,7 +233,7 @@ fn library_in(short_name: &str, version: &Version, dir_to_search: &Path) -> Opti
     for p_path in libraries {
         // Find a filename that matches the pattern: (lib_prefix)-hash-(version)(lib_suffix)
         // and remember what the hash was
-        let mut f_name = match p_path.filestem() {
+        let mut f_name = match p_path.filestem_str() {
             Some(s) => s, None => continue
         };
         // Already checked the filetype above
@@ -267,14 +267,14 @@ fn library_in(short_name: &str, version: &Version, dir_to_search: &Path) -> Opti
 
     if result_filename.is_none() {
         debug2!("warning: library_in_workspace didn't find a library in {} for {}",
-                  dir_to_search.to_str(), short_name);
+                  dir_to_search.display(), short_name);
     }
 
     // Return the filename that matches, which we now know exists
     // (if result_filename != None)
     let abs_path = do result_filename.map |result_filename| {
-        let absolute_path = dir_to_search.push_rel(&result_filename);
-        debug2!("result_filename = {}", absolute_path.to_str());
+        let absolute_path = dir_to_search.join_path(&result_filename);
+        debug2!("result_filename = {}", absolute_path.display());
         absolute_path
     };
 
@@ -297,7 +297,7 @@ pub fn target_library_in_workspace(pkgid: &PkgId, workspace: &Path) -> Path {
     if !os::path_is_dir(workspace) {
         cond.raise(((*workspace).clone(),
                     format!("Workspace supplied to target_library_in_workspace \
-                             is not a directory! {}", workspace.to_str())));
+                             is not a directory! {}", workspace.display())));
     }
     target_file_in_workspace(pkgid, workspace, Lib, Install)
 }
@@ -329,14 +329,14 @@ fn target_file_in_workspace(pkgid: &PkgId, workspace: &Path,
     // Artifacts in the build directory live in a package-ID-specific subdirectory,
     // but installed ones don't.
     let result = match (where, what) {
-                (Build, _)         => target_build_dir(workspace).push_rel(&pkgid.path),
-                (Install, Lib)     => target_lib_dir(workspace),
+                (Build, _)      => target_build_dir(workspace).join_path(&pkgid.path),
+                (Install, Lib)  => target_lib_dir(workspace),
                 (Install, _)    => target_bin_dir(workspace)
     };
     if !os::path_exists(&result) && !mkdir_recursive(&result, U_RWX) {
         cond.raise((result.clone(), format!("target_file_in_workspace couldn't \
             create the {} dir (pkgid={}, workspace={}, what={:?}, where={:?}",
-            subdir, pkgid.to_str(), workspace.to_str(), what, where)));
+            subdir, pkgid.to_str(), workspace.display(), what, where)));
     }
     mk_output_path(what, where, pkgid, result)
 }
@@ -347,8 +347,8 @@ pub fn build_pkg_id_in_workspace(pkgid: &PkgId, workspace: &Path) -> Path {
     use conditions::bad_path::cond;
 
     let mut result = target_build_dir(workspace);
-    result = result.push_rel(&pkgid.path);
-    debug2!("Creating build dir {} for package id {}", result.to_str(),
+    result.push_path(&pkgid.path);
+    debug2!("Creating build dir {} for package id {}", result.display(),
            pkgid.to_str());
     if os::path_exists(&result) || os::mkdir_recursive(&result, U_RWX) {
         result
@@ -370,16 +370,16 @@ pub fn mk_output_path(what: OutputType, where: Target,
         // If we're installing, it just goes under <workspace>...
         Install => workspace,
         // and if we're just building, it goes in a package-specific subdir
-        Build => workspace.push_rel(&pkg_id.path)
+        Build => workspace.join_path(&pkg_id.path)
     };
     debug2!("[{:?}:{:?}] mk_output_path: short_name = {}, path = {}", what, where,
            if what == Lib { short_name_with_version.clone() } else { pkg_id.short_name.clone() },
-           dir.to_str());
+           dir.display());
     let mut output_path = match what {
         // this code is duplicated from elsewhere; fix this
-        Lib => dir.push(os::dll_filename(short_name_with_version)),
+        Lib => dir.join_str(os::dll_filename(short_name_with_version)),
         // executable names *aren't* versioned
-        _ => dir.push(format!("{}{}{}", pkg_id.short_name,
+        _ => dir.join_str(format!("{}{}{}", pkg_id.short_name,
                            match what {
                                Test => "test",
                                Bench => "bench",
@@ -388,9 +388,9 @@ pub fn mk_output_path(what: OutputType, where: Target,
                            os::EXE_SUFFIX))
     };
     if !output_path.is_absolute() {
-        output_path = os::getcwd().push_rel(&output_path).normalize();
+        output_path = os::getcwd().join_path(&output_path);
     }
-    debug2!("mk_output_path: returning {}", output_path.to_str());
+    debug2!("mk_output_path: returning {}", output_path.display());
     output_path
 }
 
@@ -409,14 +409,14 @@ pub fn uninstall_package_from(workspace: &Path, pkgid: &PkgId) {
     }
     if !did_something {
         warn(format!("Warning: there don't seem to be any files for {} installed in {}",
-             pkgid.to_str(), workspace.to_str()));
+             pkgid.to_str(), workspace.display()));
     }
 
 }
 
 fn dir_has_file(dir: &Path, file: &str) -> bool {
     assert!(dir.is_absolute());
-    os::path_exists(&dir.push(file))
+    os::path_exists(&dir.join_str(file))
 }
 
 pub fn find_dir_using_rust_path_hack(p: &PkgId) -> Option<Path> {
@@ -425,15 +425,15 @@ pub fn find_dir_using_rust_path_hack(p: &PkgId) -> Option<Path> {
         // Require that the parent directory match the package ID
         // Note that this only matches if the package ID being searched for
         // has a name that's a single component
-        if dir.is_parent_of(&p.path) || dir.is_parent_of(&versionize(&p.path, &p.version)) {
-            debug2!("In find_dir_using_rust_path_hack: checking dir {}", dir.to_str());
+        if dir.ends_with_path(&p.path) || dir.ends_with_path(&versionize(&p.path, &p.version)) {
+            debug2!("In find_dir_using_rust_path_hack: checking dir {}", dir.display());
             if dir_has_file(dir, "lib.rs") || dir_has_file(dir, "main.rs")
                 || dir_has_file(dir, "test.rs") || dir_has_file(dir, "bench.rs") {
-                debug2!("Did find id {} in dir {}", p.to_str(), dir.to_str());
+                debug2!("Did find id {} in dir {}", p.to_str(), dir.display());
                 return Some(dir.clone());
             }
         }
-        debug2!("Didn't find id {} in dir {}", p.to_str(), dir.to_str())
+        debug2!("Didn't find id {} in dir {}", p.to_str(), dir.display())
     }
     None
 }
@@ -449,8 +449,12 @@ pub fn user_set_rust_path() -> bool {
 
 /// Append the version string onto the end of the path's filename
 pub fn versionize(p: &Path, v: &Version) -> Path {
-    let q = p.file_path().to_str();
-    p.with_filename(format!("{}-{}", q, v.to_str()))
+    let q = p.file_path().expect("path is a directory");
+    let mut q = q.as_vec().to_owned();
+    q.push('-' as u8);
+    let vs = v.to_str();
+    q.push_all(vs.as_bytes());
+    p.with_filename(q)
 }
 
 
diff --git a/src/librustpkg/rustpkg.rs b/src/librustpkg/rustpkg.rs
index 63195112747..47a65753cc9 100644
--- a/src/librustpkg/rustpkg.rs
+++ b/src/librustpkg/rustpkg.rs
@@ -105,7 +105,7 @@ impl<'self> PkgScript<'self> {
         let binary = os::args()[0].to_managed();
         // Build the rustc session data structures to pass
         // to the compiler
-        debug2!("pkgscript parse: {}", sysroot.to_str());
+        debug2!("pkgscript parse: {}", sysroot.display());
         let options = @session::options {
             binary: binary,
             maybe_sysroot: Some(sysroot),
@@ -141,31 +141,36 @@ impl<'self> PkgScript<'self> {
                   sysroot: &Path) -> (~[~str], ExitCode) {
         let sess = self.sess;
 
-        debug2!("Working directory = {}", self.build_dir.to_str());
+        debug2!("Working directory = {}", self.build_dir.display());
         // Collect together any user-defined commands in the package script
         let crate = util::ready_crate(sess, self.crate.take_unwrap());
         debug2!("Building output filenames with script name {}",
                driver::source_name(&driver::file_input(self.input.clone())));
-        let exe = self.build_dir.push(~"pkg" + util::exe_suffix());
+        let exe = self.build_dir.join_str("pkg" + util::exe_suffix());
         util::compile_crate_from_input(&self.input,
                                        exec,
                                        Nothing,
                                        &self.build_dir,
                                        sess,
                                        crate);
-        debug2!("Running program: {} {} {}", exe.to_str(),
-               sysroot.to_str(), "install");
+        debug2!("Running program: {} {} {}", exe.display(),
+               sysroot.display(), "install");
         // Discover the output
-        exec.discover_output("binary", exe.to_str(), digest_only_date(&exe));
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        exec.discover_output("binary", exe.as_str().unwrap(), digest_only_date(&exe));
         // FIXME #7401 should support commands besides `install`
-        let status = run::process_status(exe.to_str(), [sysroot.to_str(), ~"install"]);
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        let status = run::process_status(exe.as_str().unwrap(),
+                                         [sysroot.as_str().unwrap().to_owned(), ~"install"]);
         if status != 0 {
             return (~[], status);
         }
         else {
             debug2!("Running program (configs): {} {} {}",
-                   exe.to_str(), sysroot.to_str(), "configs");
-            let output = run::process_output(exe.to_str(), [sysroot.to_str(), ~"configs"]);
+                   exe.display(), sysroot.display(), "configs");
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            let output = run::process_output(exe.as_str().unwrap(),
+                                             [sysroot.as_str().unwrap().to_owned(), ~"configs"]);
             // Run the configs() function to get the configs
             let cfgs = str::from_utf8_slice(output.output).word_iter()
                 .map(|w| w.to_owned()).collect();
@@ -208,7 +213,8 @@ impl CtxMethods for BuildContext {
             match cwd_to_workspace() {
                 None if self.context.use_rust_path_hack => {
                     let cwd = os::getcwd();
-                    let pkgid = PkgId::new(cwd.components[cwd.components.len() - 1]);
+                    // FIXME (#9639): This needs to handle non-utf8 paths
+                    let pkgid = PkgId::new(cwd.filename_str().unwrap());
                     let mut pkg_src = PkgSrc::new(cwd, default_workspace(), true, pkgid);
                     self.build(&mut pkg_src, what);
                     match pkg_src {
@@ -237,13 +243,12 @@ impl CtxMethods for BuildContext {
             let mut dest_ws = default_workspace();
             do each_pkg_parent_workspace(&self.context, &pkgid) |workspace| {
                 debug2!("found pkg {} in workspace {}, trying to build",
-                       pkgid.to_str(), workspace.to_str());
+                       pkgid.to_str(), workspace.display());
                 dest_ws = determine_destination(os::getcwd(),
                                                 self.context.use_rust_path_hack,
                                                 workspace);
-                let mut pkg_src = PkgSrc::new(workspace.clone(), dest_ws.clone(),
-                                              false, pkgid.clone());
-                self.build(&mut pkg_src, what);
+                let mut pkg_src = PkgSrc::new(workspace.clone(), false, pkgid.clone());
+                dest_ws = Some(self.build(&mut pkg_src, what));
                 true
             };
             // n.b. If this builds multiple packages, it only returns the workspace for
@@ -290,8 +295,9 @@ impl CtxMethods for BuildContext {
                     match cwd_to_workspace() {
                         None if self.context.use_rust_path_hack => {
                             let cwd = os::getcwd();
+                            // FIXME (#9639): This needs to handle non-utf8 paths
                             let inferred_pkgid =
-                                PkgId::new(cwd.components[cwd.components.len() - 1]);
+                                PkgId::new(cwd.filename_str().unwrap());
                             self.install(PkgSrc::new(cwd, default_workspace(),
                                                      true, inferred_pkgid), &Everything);
                         }
@@ -331,7 +337,9 @@ impl CtxMethods for BuildContext {
             "list" => {
                 io::println("Installed packages:");
                 do installed_packages::list_installed_packages |pkg_id| {
-                    println(pkg_id.path.to_str());
+                    do pkg_id.path.with_display_str |s| {
+                        println(s);
+                    }
                     true
                 };
             }
@@ -379,7 +387,7 @@ impl CtxMethods for BuildContext {
                     do each_pkg_parent_workspace(&self.context, &pkgid) |workspace| {
                         path_util::uninstall_package_from(workspace, &pkgid);
                         note(format!("Uninstalled package {} (was installed in {})",
-                                  pkgid.to_str(), workspace.to_str()));
+                                  pkgid.to_str(), workspace.display()));
                         true
                     };
                 }
@@ -407,23 +415,25 @@ impl CtxMethods for BuildContext {
         let pkgid = pkg_src.id.clone();
 
         debug2!("build: workspace = {} (in Rust path? {:?} is git dir? {:?} \
-                pkgid = {} pkgsrc start_dir = {}", workspace.to_str(),
-               in_rust_path(&workspace), is_git_dir(&workspace.push_rel(&pkgid.path)),
-               pkgid.to_str(), pkg_src.start_dir.to_str());
+                pkgid = {} pkgsrc start_dir = {}", workspace.display(),
+               in_rust_path(&workspace), is_git_dir(&workspace.join_path(&pkgid.path)),
+               pkgid.to_str(), pkg_src.start_dir.display());
 
         // If workspace isn't in the RUST_PATH, and it's a git repo,
         // then clone it into the first entry in RUST_PATH, and repeat
-        if !in_rust_path(&workspace) && is_git_dir(&workspace.push_rel(&pkgid.path)) {
-            let out_dir = default_workspace().push("src").push_rel(&pkgid.path);
-            let git_result = source_control::safe_git_clone(&workspace.push_rel(&pkgid.path),
+        if !in_rust_path(&workspace) && is_git_dir(&workspace.join_path(&pkgid.path)) {
+            let mut out_dir = default_workspace().join_str("src");
+            out_dir.push_path(&pkgid.path);
+            let git_result = source_control::safe_git_clone(&workspace.join_path(&pkgid.path),
                                                             &pkgid.version,
                                                             &out_dir);
             match git_result {
                 CheckedOutSources => make_read_only(&out_dir),
-                _ => cond.raise((pkgid.path.to_str(), out_dir.clone()))
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                _ => cond.raise((pkgid.path.as_str().unwrap(), out_dir.clone()))
             };
             let default_ws = default_workspace();
-            debug2!("Calling build recursively with {:?} and {:?}", default_ws.to_str(),
+            debug2!("Calling build recursively with {:?} and {:?}", default_ws.display(),
                    pkgid.to_str());
             return self.build(&mut PkgSrc::new(default_ws.clone(),
                                                default_ws,
@@ -439,8 +449,10 @@ impl CtxMethods for BuildContext {
         let cfgs = match pkg_src.package_script_option() {
             Some(package_script_path) => {
                 let sysroot = self.sysroot_to_use();
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                let pkg_script_path_str = package_script_path.as_str().unwrap();
                 let (cfgs, hook_result) =
-                    do self.workcache_context.with_prep(package_script_path.to_str()) |prep| {
+                    do self.workcache_context.with_prep(pkg_script_path_str) |prep| {
                     let sub_sysroot = sysroot.clone();
                     let package_script_path_clone = package_script_path.clone();
                     let sub_ws = workspace.clone();
@@ -476,13 +488,13 @@ impl CtxMethods for BuildContext {
                 // Find crates inside the workspace
                 &Everything => pkg_src.find_crates(),
                 // Find only tests
-                &Tests => pkg_src.find_crates_with_filter(|s| { is_test(&Path(s)) }),
+                &Tests => pkg_src.find_crates_with_filter(|s| { is_test(&Path::from_str(s)) }),
                 // Don't infer any crates -- just build the one that was requested
                 &JustOne(ref p) => {
                     // We expect that p is relative to the package source's start directory,
                     // so check that assumption
-                    debug2!("JustOne: p = {}", p.to_str());
-                    assert!(os::path_exists(&pkg_src.start_dir.push_rel(p)));
+                    debug2!("JustOne: p = {}", p.display());
+                    assert!(os::path_exists(&pkg_src.start_dir.join_path(p)));
                     if is_lib(p) {
                         PkgSrc::push_crate(&mut pkg_src.libs, 0, p);
                     } else if is_main(p) {
@@ -492,7 +504,7 @@ impl CtxMethods for BuildContext {
                     } else if is_bench(p) {
                         PkgSrc::push_crate(&mut pkg_src.benchs, 0, p);
                     } else {
-                        warn(format!("Not building any crates for dependency {}", p.to_str()));
+                        warn(format!("Not building any crates for dependency {}", p.display()));
                         return;
                     }
                 }
@@ -509,10 +521,10 @@ impl CtxMethods for BuildContext {
 
         let dir = build_pkg_id_in_workspace(id, workspace);
         note(format!("Cleaning package {} (removing directory {})",
-                        id.to_str(), dir.to_str()));
+                        id.to_str(), dir.display()));
         if os::path_exists(&dir) {
             os::remove_dir_recursive(&dir);
-            note(format!("Removed directory {}", dir.to_str()));
+            note(format!("Removed directory {}", dir.display()));
         }
 
         note(format!("Cleaned package {}", id.to_str()));
@@ -541,21 +553,22 @@ impl CtxMethods for BuildContext {
         debug2!("In declare inputs for {}", id.to_str());
         for cs in to_do.iter() {
             for c in cs.iter() {
-                let path = pkg_src.start_dir.push_rel(&c.file).normalize();
-                debug2!("Recording input: {}", path.to_str());
-                inputs.push((~"file", path.to_str()));
+                let path = pkg_src.start_dir.join_path(&c.file);
+                debug2!("Recording input: {}", path.display());
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                inputs.push((~"file", path.as_str().unwrap().to_owned()));
             }
         }
 
         let result = self.install_no_build(pkg_src.build_workspace(),
                                            &pkg_src.destination_workspace,
-                                           &id).map(|s| Path(*s));
+                                           &id).map(|s| Path::from_str(*s));
         debug2!("install: id = {}, about to call discover_outputs, {:?}",
-               id.to_str(), result.to_str());
+               id.to_str(), result.map(|p| p.to_display_str()));
         installed_files = installed_files + result;
         note(format!("Installed package {} to {}",
                      id.to_str(),
-                     pkg_src.destination_workspace.to_str()));
+                     pkg_src.destination_workspace.display()));
         (installed_files, inputs)
     }
 
@@ -578,18 +591,20 @@ impl CtxMethods for BuildContext {
 
         debug2!("target_exec = {} target_lib = {:?} \
                maybe_executable = {:?} maybe_library = {:?}",
-               target_exec.to_str(), target_lib,
+               target_exec.display(), target_lib,
                maybe_executable, maybe_library);
 
         do self.workcache_context.with_prep(id.install_tag()) |prep| {
             for ee in maybe_executable.iter() {
+                // FIXME (#9639): This needs to handle non-utf8 paths
                 prep.declare_input("binary",
-                                   ee.to_str(),
+                                   ee.as_str().unwrap(),
                                    workcache_support::digest_only_date(ee));
             }
             for ll in maybe_library.iter() {
+                // FIXME (#9639): This needs to handle non-utf8 paths
                 prep.declare_input("binary",
-                                   ll.to_str(),
+                                   ll.as_str().unwrap(),
                                    workcache_support::digest_only_date(ll));
             }
             let subex = maybe_executable.clone();
@@ -601,31 +616,32 @@ impl CtxMethods for BuildContext {
                 let mut outputs = ~[];
 
                 for exec in subex.iter() {
-                    debug2!("Copying: {} -> {}", exec.to_str(), sub_target_ex.to_str());
+                    debug2!("Copying: {} -> {}", exec.display(), sub_target_ex.display());
                     if !(os::mkdir_recursive(&sub_target_ex.dir_path(), U_RWX) &&
                          os::copy_file(exec, &sub_target_ex)) {
                         cond.raise(((*exec).clone(), sub_target_ex.clone()));
                     }
+                    // FIXME (#9639): This needs to handle non-utf8 paths
                     exe_thing.discover_output("binary",
-                        sub_target_ex.to_str(),
+                        sub_target_ex.as_str().unwrap(),
                         workcache_support::digest_only_date(&sub_target_ex));
-                    outputs.push(sub_target_ex.to_str());
+                    outputs.push(sub_target_ex.as_str().unwrap().to_owned());
                 }
                 for lib in sublib.iter() {
-                    let target_lib = sub_target_lib
+                    let mut target_lib = sub_target_lib
                         .clone().expect(format!("I built {} but apparently \
-                                             didn't install it!", lib.to_str()));
+                                             didn't install it!", lib.display()));
                     let target_lib = target_lib
-                        .pop().push(lib.filename().expect("weird target lib"));
+                        .set_filename(lib.filename().expect("weird target lib"));
                     if !(os::mkdir_recursive(&target_lib.dir_path(), U_RWX) &&
                          os::copy_file(lib, &target_lib)) {
                         cond.raise(((*lib).clone(), target_lib.clone()));
                     }
-                    debug2!("3. discovering output {}", target_lib.to_str());
+                    debug2!("3. discovering output {}", target_lib.display());
                     exe_thing.discover_output("binary",
-                                              target_lib.to_str(),
+                                              target_lib.as_str().unwrap(),
                                               workcache_support::digest_only_date(&target_lib));
-                    outputs.push(target_lib.to_str());
+                    outputs.push(target_lib.as_str().unwrap().to_owned());
                 }
                 outputs
             }
@@ -639,23 +655,24 @@ impl CtxMethods for BuildContext {
     fn test(&self, pkgid: &PkgId, workspace: &Path)  {
         match built_test_in_workspace(pkgid, workspace) {
             Some(test_exec) => {
-                debug2!("test: test_exec = {}", test_exec.to_str());
-                let status = run::process_status(test_exec.to_str(), [~"--test"]);
+                debug2!("test: test_exec = {}", test_exec.display());
+                // FIXME (#9639): This needs to handle non-utf8 paths
+                let status = run::process_status(test_exec.as_str().unwrap(), [~"--test"]);
                 os::set_exit_status(status);
             }
             None => {
                 error(format!("Internal error: test executable for package ID {} in workspace {} \
                            wasn't built! Please report this as a bug.",
-                           pkgid.to_str(), workspace.to_str()));
+                           pkgid.to_str(), workspace.display()));
             }
         }
     }
 
     fn init(&self) {
-        os::mkdir_recursive(&Path("src"),   U_RWX);
-        os::mkdir_recursive(&Path("lib"),   U_RWX);
-        os::mkdir_recursive(&Path("bin"),   U_RWX);
-        os::mkdir_recursive(&Path("build"), U_RWX);
+        os::mkdir_recursive(&Path::from_str("src"),   U_RWX);
+        os::mkdir_recursive(&Path::from_str("lib"),   U_RWX);
+        os::mkdir_recursive(&Path::from_str("bin"),   U_RWX);
+        os::mkdir_recursive(&Path::from_str("build"), U_RWX);
     }
 
     fn uninstall(&self, _id: &str, _vers: Option<~str>)  {
@@ -835,12 +852,13 @@ pub fn main_args(args: &[~str]) -> int {
     let mut remaining_args: ~[~str] = remaining_args.map(|s| (*s).clone()).collect();
     remaining_args.shift();
     let sroot = match supplied_sysroot {
-        Some(getopts::Val(s)) => Path(s),
+        Some(getopts::Val(s)) => Path::from_str(s),
         _ => filesearch::get_or_default_sysroot()
     };
 
-    debug2!("Using sysroot: {}", sroot.to_str());
-    debug2!("Will store workcache in {}", default_workspace().to_str());
+    debug2!("Using sysroot: {}", sroot.display());
+    let ws = default_workspace();
+    debug2!("Will store workcache in {}", ws.display());
 
     let rm_args = remaining_args.clone();
     let sub_cmd = cmd.clone();
@@ -866,7 +884,8 @@ pub fn main_args(args: &[~str]) -> int {
 
 fn declare_package_script_dependency(prep: &mut workcache::Prep, pkg_src: &PkgSrc) {
     match pkg_src.package_script_option() {
-        Some(ref p) => prep.declare_input("file", p.to_str(),
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        Some(ref p) => prep.declare_input("file", p.as_str().unwrap(),
                                       workcache_support::digest_file_with_date(p)),
         None => ()
     }
diff --git a/src/librustpkg/search.rs b/src/librustpkg/search.rs
index f0042e1f8e2..080ba461f05 100644
--- a/src/librustpkg/search.rs
+++ b/src/librustpkg/search.rs
@@ -18,7 +18,7 @@ use version::Version;
 pub fn find_installed_library_in_rust_path(pkg_path: &Path, _version: &Version) -> Option<Path> {
     let rp = rust_path();
     debug2!("find_installed_library_in_rust_path: looking for path {}",
-            pkg_path.to_str());
+            pkg_path.display());
     for p in rp.iter() {
         match installed_library_in_workspace(pkg_path, p) {
             Some(path) => return Some(path),
diff --git a/src/librustpkg/source_control.rs b/src/librustpkg/source_control.rs
index 33b86e7cbc5..b910c079205 100644
--- a/src/librustpkg/source_control.rs
+++ b/src/librustpkg/source_control.rs
@@ -24,14 +24,17 @@ use path_util::chmod_read_only;
 pub fn safe_git_clone(source: &Path, v: &Version, target: &Path) -> CloneResult {
     if os::path_exists(source) {
         debug2!("{} exists locally! Cloning it into {}",
-                source.to_str(), target.to_str());
+                source.display(), target.display());
         // Ok to use target here; we know it will succeed
         assert!(os::path_is_dir(source));
         assert!(is_git_dir(source));
 
         if !os::path_exists(target) {
-            debug2!("Running: git clone {} {}", source.to_str(), target.to_str());
-            let outp = run::process_output("git", [~"clone", source.to_str(), target.to_str()]);
+            debug2!("Running: git clone {} {}", source.display(), target.display());
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            let outp = run::process_output("git", [~"clone",
+                                                   source.as_str().unwrap().to_owned(),
+                                                   target.as_str().unwrap().to_owned()]);
             if outp.status != 0 {
                 io::println(str::from_utf8_owned(outp.output.clone()));
                 io::println(str::from_utf8_owned(outp.error));
@@ -40,11 +43,13 @@ pub fn safe_git_clone(source: &Path, v: &Version, target: &Path) -> CloneResult
                 else {
                 match v {
                     &ExactRevision(ref s) => {
+                        let git_dir = target.join_str(".git");
                         debug2!("`Running: git --work-tree={} --git-dir={} checkout {}",
-                                *s, target.to_str(), target.push(".git").to_str());
+                                *s, target.display(), git_dir.display());
+                        // FIXME (#9639: This needs to handle non-utf8 paths
                         let outp = run::process_output("git",
-                            [format!("--work-tree={}", target.to_str()),
-                             format!("--git-dir={}", target.push(".git").to_str()),
+                            [format!("--work-tree={}", target.as_str().unwrap().to_owned()),
+                             format!("--git-dir={}", git_dir.as_str().unwrap().to_owned()),
                              ~"checkout", format!("{}", *s)]);
                         if outp.status != 0 {
                             io::println(str::from_utf8_owned(outp.output.clone()));
@@ -59,11 +64,13 @@ pub fn safe_git_clone(source: &Path, v: &Version, target: &Path) -> CloneResult
             // Check that no version was specified. There's no reason to not handle the
             // case where a version was requested, but I haven't implemented it.
             assert!(*v == NoVersion);
+            let git_dir = target.join_str(".git");
             debug2!("Running: git --work-tree={} --git-dir={} pull --no-edit {}",
-                    target.to_str(), target.push(".git").to_str(), source.to_str());
-            let args = [format!("--work-tree={}", target.to_str()),
-                        format!("--git-dir={}", target.push(".git").to_str()),
-                        ~"pull", ~"--no-edit", source.to_str()];
+                    target.display(), git_dir.display(), source.display());
+            // FIXME (#9639: This needs to handle non-utf8 paths
+            let args = [format!("--work-tree={}", target.as_str().unwrap().to_owned()),
+                        format!("--git-dir={}", git_dir.as_str().unwrap().to_owned()),
+                        ~"pull", ~"--no-edit", source.as_str().unwrap().to_owned()];
             let outp = run::process_output("git", args);
             assert!(outp.status == 0);
         }
@@ -73,7 +80,7 @@ pub fn safe_git_clone(source: &Path, v: &Version, target: &Path) -> CloneResult
 
         let scratch_dir = TempDir::new("rustpkg");
         let clone_target = match scratch_dir {
-            Some(d) => d.unwrap().push("rustpkg_temp"),
+            Some(d) => d.unwrap().join_str("rustpkg_temp"),
             None    => cond.raise(~"Failed to create temporary directory for fetching git sources")
         };
 
@@ -109,7 +116,7 @@ pub fn git_clone_url(source: &str, target: &Path, v: &Version) {
     else {
         match v {
             &ExactRevision(ref s) | &Tagged(ref s) => {
-                    let outp = process_output_in_cwd("git", [~"checkout", format!("{}", *s)],
+                    let outp = process_output_in_cwd("git", [~"checkout", s.to_owned()],
                                                          target);
                     if outp.status != 0 {
                         debug2!("{}", str::from_utf8_owned(outp.output.clone()));
@@ -129,5 +136,5 @@ fn process_output_in_cwd(prog: &str, args: &[~str], cwd: &Path) -> ProcessOutput
 }
 
 pub fn is_git_dir(p: &Path) -> bool {
-    os::path_is_dir(&p.push(".git"))
+    os::path_is_dir(&p.join_str(".git"))
 }
diff --git a/src/librustpkg/target.rs b/src/librustpkg/target.rs
index 664f6807227..9f371a86535 100644
--- a/src/librustpkg/target.rs
+++ b/src/librustpkg/target.rs
@@ -50,13 +50,13 @@ pub fn is_bench(p: &Path) -> bool {
 
 fn file_is(p: &Path, stem: &str) -> bool {
     match p.filestem() {
-        Some(s) if s == stem => true,
+        Some(s) if s == stem.as_bytes() => true,
         _ => false
     }
 }
 
 pub fn lib_name_of(p: &Path) -> Path {
-    p.push("lib.rs")
+    p.join_str("lib.rs")
 }
 
 pub static lib_crate_filename: &'static str = "lib.rs";
diff --git a/src/librustpkg/tests.rs b/src/librustpkg/tests.rs
index d03243599ef..de7ad9dc06b 100644
--- a/src/librustpkg/tests.rs
+++ b/src/librustpkg/tests.rs
@@ -41,7 +41,7 @@ use util::datestamp;
 
 fn fake_ctxt(sysroot: Path, workspace: &Path) -> BuildContext {
     let context = workcache::Context::new(
-        RWArc::new(Database::new(workspace.push("rustpkg_db.json"))),
+        RWArc::new(Database::new(workspace.join_str("rustpkg_db.json"))),
         RWArc::new(Logger::new()),
         Arc::new(TreeMap::new()));
     BuildContext {
@@ -59,7 +59,7 @@ fn fake_ctxt(sysroot: Path, workspace: &Path) -> BuildContext {
 fn fake_pkg() -> PkgId {
     let sn = ~"bogus";
     PkgId {
-        path: Path(sn),
+        path: Path::from_str(sn),
         short_name: sn,
         version: NoVersion
     }
@@ -67,7 +67,7 @@ fn fake_pkg() -> PkgId {
 
 fn git_repo_pkg() -> PkgId {
     PkgId {
-        path: Path("mockgithub.com/catamorphism/test-pkg"),
+        path: Path::from_str("mockgithub.com/catamorphism/test-pkg"),
         short_name: ~"test-pkg",
         version: NoVersion
     }
@@ -75,7 +75,7 @@ fn git_repo_pkg() -> PkgId {
 
 fn git_repo_pkg_with_tag(a_tag: ~str) -> PkgId {
     PkgId {
-        path: Path("mockgithub.com/catamorphism/test-pkg"),
+        path: Path::from_str("mockgithub.com/catamorphism/test-pkg"),
         short_name: ~"test-pkg",
         version: Tagged(a_tag)
     }
@@ -101,35 +101,36 @@ fn mk_empty_workspace(short_name: &Path, version: &Version, tag: &str) -> TempDi
 
 fn mk_workspace(workspace: &Path, short_name: &Path, version: &Version) -> Path {
     // include version number in directory name
-    let package_dir = workspace.push_many([~"src", format!("{}-{}",
-                                                short_name.to_str(), version.to_str())]);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let package_dir = workspace.join_many_str([~"src", format!("{}-{}",
+                                                short_name.as_str().unwrap(), version.to_str())]);
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
     package_dir
 }
 
 fn mk_temp_workspace(short_name: &Path, version: &Version) -> (TempDir, Path) {
     let workspace_dir = mk_empty_workspace(short_name, version, "temp_workspace");
-    let package_dir = workspace_dir.path().push_many([~"src",
-                                                      format!("{}-{}",
-                                                              short_name.to_str(),
-                                                              version.to_str())]);
+    let package_dir = workspace_dir.path().join_many_str([~"src",
+                                                          format!("{}-{}",
+                                                                  short_name.to_str(),
+                                                                  version.to_str())]);
 
-    debug2!("Created {} and does it exist? {:?}", package_dir.to_str(),
+    debug2!("Created {} and does it exist? {:?}", package_dir.display(),
           os::path_is_dir(&package_dir));
     // Create main, lib, test, and bench files
-    debug2!("mk_workspace: creating {}", package_dir.to_str());
+    debug2!("mk_workspace: creating {}", package_dir.display());
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
-    debug2!("Created {} and does it exist? {:?}", package_dir.to_str(),
+    debug2!("Created {} and does it exist? {:?}", package_dir.display(),
           os::path_is_dir(&package_dir));
     // Create main, lib, test, and bench files
 
-    writeFile(&package_dir.push("main.rs"),
+    writeFile(&package_dir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&package_dir.push("lib.rs"),
+    writeFile(&package_dir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&package_dir.push("test.rs"),
+    writeFile(&package_dir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&package_dir.push("bench.rs"),
+    writeFile(&package_dir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
     (workspace_dir, package_dir)
 }
@@ -153,18 +154,18 @@ fn run_git(args: &[~str], env: Option<~[(~str, ~str)]>, cwd: &Path, err_msg: &st
 /// Should create an empty git repo in p, relative to the tmp dir, and return the new
 /// absolute path
 fn init_git_repo(p: &Path) -> TempDir {
-    assert!(!p.is_absolute());
+    assert!(p.is_relative());
     let tmp = TempDir::new("git_local").expect("couldn't create temp dir");
-    let work_dir = tmp.path().push_rel(p);
+    let work_dir = tmp.path().join_path(p);
     let work_dir_for_opts = work_dir.clone();
     assert!(os::mkdir_recursive(&work_dir, U_RWX));
-    debug2!("Running: git init in {}", work_dir.to_str());
-    let ws = work_dir.to_str();
+    debug2!("Running: git init in {}", work_dir.display());
     run_git([~"init"], None, &work_dir_for_opts,
-        format!("Couldn't initialize git repository in {}", ws));
+        format!("Couldn't initialize git repository in {}", work_dir.display()));
     // Add stuff to the dir so that git tag succeeds
-    writeFile(&work_dir.push("README"), "");
-    run_git([~"add", ~"README"], None, &work_dir_for_opts, format!("Couldn't add in {}", ws));
+    writeFile(&work_dir.join_str("README"), "");
+    run_git([~"add", ~"README"], None, &work_dir_for_opts, format!("Couldn't add in {}",
+                                                                work_dir.display()));
     git_commit(&work_dir_for_opts, ~"whatever");
     tmp
 }
@@ -176,11 +177,11 @@ fn add_all_and_commit(repo: &Path) {
 
 fn git_commit(repo: &Path, msg: ~str) {
     run_git([~"commit", ~"--author=tester <test@mozilla.com>", ~"-m", msg],
-            None, repo, format!("Couldn't commit in {}", repo.to_str()));
+            None, repo, format!("Couldn't commit in {}", repo.display()));
 }
 
 fn git_add_all(repo: &Path) {
-    run_git([~"add", ~"-A"], None, repo, format!("Couldn't add all files in {}", repo.to_str()));
+    run_git([~"add", ~"-A"], None, repo, format!("Couldn't add all files in {}", repo.display()));
 }
 
 fn add_git_tag(repo: &Path, tag: ~str) {
@@ -188,7 +189,7 @@ fn add_git_tag(repo: &Path, tag: ~str) {
     git_add_all(repo);
     git_commit(repo, ~"whatever");
     run_git([~"tag", tag.clone()], None, repo,
-            format!("Couldn't add git tag {} in {}", tag, repo.to_str()));
+            format!("Couldn't add git tag {} in {}", tag, repo.display()));
 }
 
 fn is_rwx(p: &Path) -> bool {
@@ -215,24 +216,29 @@ fn is_read_only(p: &Path) -> bool {
     }
 }
 
+fn ends_with(v: &[u8], needle: &[u8]) -> bool {
+    v.len() >= needle.len() && v.slice_from(v.len() - needle.len()) == needle
+}
+
 fn test_sysroot() -> Path {
     // Totally gross hack but it's just for test cases.
     // Infer the sysroot from the exe name and pray that it's right.
     // (Did I mention it was a gross hack?)
-    let self_path = os::self_exe_path().expect("Couldn't get self_exe path");
-    self_path.pop()
+    let mut self_path = os::self_exe_path().expect("Couldn't get self_exe path");
+    self_path.pop();
+    self_path
 }
 
 // Returns the path to rustpkg
 fn rustpkg_exec() -> Path {
     // Ugh
-    let first_try = test_sysroot().push_many(
+    let first_try = test_sysroot().join_many_str(
         [~"lib", ~"rustc", host_triple(), ~"bin", ~"rustpkg"]);
     if is_executable(&first_try) {
         first_try
     }
     else {
-        let second_try = test_sysroot().push_many([~"bin", ~"rustpkg"]);
+        let second_try = test_sysroot().join_many_str(["bin", "rustpkg"]);
         if is_executable(&second_try) {
             second_try
         }
@@ -275,12 +281,14 @@ enum ProcessResult {
 /// Returns the process's output.
 fn command_line_test_with_env(args: &[~str], cwd: &Path, env: Option<~[(~str, ~str)]>)
     -> ProcessResult {
-    let cmd = rustpkg_exec().to_str();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let exec_path = rustpkg_exec();
+    let cmd = exec_path.as_str().unwrap().to_owned();
     let env_str = match env {
         Some(ref pairs) => pairs.map(|&(ref k, ref v)| { format!("{}={}", *k, *v) }).connect(","),
         None        => ~""
     };
-    debug2!("{} cd {}; {} {}", env_str, cwd.to_str(), cmd, args.connect(" "));
+    debug2!("{} cd {}; {} {}", env_str, cwd.display(), cmd, args.connect(" "));
     assert!(os::path_is_dir(&*cwd));
     let cwd = (*cwd).clone();
     let mut prog = run::Process::new(cmd, args, run::ProcessOptions {
@@ -314,27 +322,27 @@ to make sure the command succeeded
 
 fn create_local_package(pkgid: &PkgId) -> TempDir {
     let (workspace, parent_dir) = mk_temp_workspace(&pkgid.path, &pkgid.version);
-    debug2!("Created empty package dir for {}, returning {}", pkgid.to_str(), parent_dir.to_str());
+    debug2!("Created empty package dir for {}, returning {}", pkgid.to_str(), parent_dir.display());
     workspace
 }
 
 fn create_local_package_in(pkgid: &PkgId, pkgdir: &Path) -> Path {
 
-    let package_dir = pkgdir.push_many([~"src", pkgid.to_str()]);
+    let package_dir = pkgdir.join_many_str([~"src", pkgid.to_str()]);
 
     // Create main, lib, test, and bench files
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
-    debug2!("Created {} and does it exist? {:?}", package_dir.to_str(),
+    debug2!("Created {} and does it exist? {:?}", package_dir.display(),
           os::path_is_dir(&package_dir));
     // Create main, lib, test, and bench files
 
-    writeFile(&package_dir.push("main.rs"),
+    writeFile(&package_dir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&package_dir.push("lib.rs"),
+    writeFile(&package_dir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&package_dir.push("test.rs"),
+    writeFile(&package_dir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&package_dir.push("bench.rs"),
+    writeFile(&package_dir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
     package_dir
 }
@@ -348,11 +356,11 @@ fn create_local_package_with_dep(pkgid: &PkgId, subord_pkgid: &PkgId) -> TempDir
     let package_dir = create_local_package(pkgid);
     create_local_package_in(subord_pkgid, package_dir.path());
     // Write a main.rs file into pkgid that references subord_pkgid
-    writeFile(&package_dir.path().push_many([~"src", pkgid.to_str(), ~"main.rs"]),
+    writeFile(&package_dir.path().join_many_str([~"src", pkgid.to_str(), ~"main.rs"]),
               format!("extern mod {};\nfn main() \\{\\}",
                    subord_pkgid.short_name));
     // Write a lib.rs file into subord_pkgid that has something in it
-    writeFile(&package_dir.path().push_many([~"src", subord_pkgid.to_str(), ~"lib.rs"]),
+    writeFile(&package_dir.path().join_many_str([~"src", subord_pkgid.to_str(), ~"lib.rs"]),
               "pub fn f() {}");
     package_dir
 }
@@ -371,7 +379,7 @@ fn assert_lib_exists(repo: &Path, pkg_path: &Path, v: Version) {
 }
 
 fn lib_exists(repo: &Path, pkg_path: &Path, _v: Version) -> bool { // ??? version?
-    debug2!("assert_lib_exists: repo = {}, pkg_path = {}", repo.to_str(), pkg_path.to_str());
+    debug2!("assert_lib_exists: repo = {}, pkg_path = {}", repo.display(), pkg_path.display());
     let lib = installed_library_in_workspace(pkg_path, repo);
     debug2!("assert_lib_exists: checking whether {:?} exists", lib);
     lib.is_some() && {
@@ -385,13 +393,13 @@ fn assert_executable_exists(repo: &Path, short_name: &str) {
 }
 
 fn executable_exists(repo: &Path, short_name: &str) -> bool {
-    debug2!("executable_exists: repo = {}, short_name = {}", repo.to_str(), short_name);
+    debug2!("executable_exists: repo = {}, short_name = {}", repo.display(), short_name);
     let exec = target_executable_in_workspace(&PkgId::new(short_name), repo);
     os::path_exists(&exec) && is_rwx(&exec)
 }
 
 fn test_executable_exists(repo: &Path, short_name: &str) -> bool {
-    debug2!("test_executable_exists: repo = {}, short_name = {}", repo.to_str(), short_name);
+    debug2!("test_executable_exists: repo = {}, short_name = {}", repo.display(), short_name);
     let exec = built_test_in_workspace(&PkgId::new(short_name), repo);
     do exec.map_default(false) |exec| {
         os::path_exists(&exec) && is_rwx(&exec)
@@ -411,7 +419,7 @@ fn assert_built_executable_exists(repo: &Path, short_name: &str) {
 
 fn built_executable_exists(repo: &Path, short_name: &str) -> bool {
     debug2!("assert_built_executable_exists: repo = {}, short_name = {}",
-            repo.to_str(), short_name);
+            repo.display(), short_name);
     let exec = built_executable_in_workspace(&PkgId::new(short_name), repo);
     exec.is_some() && {
        let execname = exec.get_ref();
@@ -444,7 +452,7 @@ fn llvm_bitcode_file_exists(repo: &Path, short_name: &str) -> bool {
 }
 
 fn file_exists(repo: &Path, short_name: &str, extension: &str) -> bool {
-    os::path_exists(&target_build_dir(repo).push_many([short_name.to_owned(),
+    os::path_exists(&target_build_dir(repo).join_many_str([short_name.to_owned(),
                                      format!("{}.{}", short_name, extension)]))
 }
 
@@ -453,7 +461,7 @@ fn assert_built_library_exists(repo: &Path, short_name: &str) {
 }
 
 fn built_library_exists(repo: &Path, short_name: &str) -> bool {
-    debug2!("assert_built_library_exists: repo = {}, short_name = {}", repo.to_str(), short_name);
+    debug2!("assert_built_library_exists: repo = {}, short_name = {}", repo.display(), short_name);
     let lib = built_library_in_workspace(&PkgId::new(short_name), repo);
     lib.is_some() && {
         let libname = lib.get_ref();
@@ -488,8 +496,8 @@ fn command_line_test_output_with_env(args: &[~str], env: ~[(~str, ~str)]) -> ~[~
 // assumes short_name and path are one and the same -- I should fix
 fn lib_output_file_name(workspace: &Path, short_name: &str) -> Path {
     debug2!("lib_output_file_name: given {} and short name {}",
-           workspace.to_str(), short_name);
-    library_in_workspace(&Path(short_name),
+           workspace.display(), short_name);
+    library_in_workspace(&Path::from_str(short_name),
                          short_name,
                          Build,
                          workspace,
@@ -498,17 +506,19 @@ fn lib_output_file_name(workspace: &Path, short_name: &str) -> Path {
 }
 
 fn output_file_name(workspace: &Path, short_name: ~str) -> Path {
-    target_build_dir(workspace).push(short_name).push(format!("{}{}", short_name, os::EXE_SUFFIX))
+    target_build_dir(workspace).join_str(short_name).join_str(format!("{}{}", short_name,
+                                                                      os::EXE_SUFFIX))
 }
 
 fn touch_source_file(workspace: &Path, pkgid: &PkgId) {
     use conditions::bad_path::cond;
-    let pkg_src_dir = workspace.push_many([~"src", pkgid.to_str()]);
+    let pkg_src_dir = workspace.join_many_str([~"src", pkgid.to_str()]);
     let contents = os::list_dir_path(&pkg_src_dir);
     for p in contents.iter() {
-        if p.filetype() == Some(".rs") {
+        if p.extension_str() == Some("rs") {
             // should be able to do this w/o a process
-            if run::process_output("touch", [p.to_str()]).status != 0 {
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            if run::process_output("touch", [p.as_str().unwrap().to_owned()]).status != 0 {
                 let _ = cond.raise((pkg_src_dir.clone(), ~"Bad path"));
             }
         }
@@ -518,10 +528,10 @@ fn touch_source_file(workspace: &Path, pkgid: &PkgId) {
 /// Add a comment at the end
 fn frob_source_file(workspace: &Path, pkgid: &PkgId, filename: &str) {
     use conditions::bad_path::cond;
-    let pkg_src_dir = workspace.push_many([~"src", pkgid.to_str()]);
+    let pkg_src_dir = workspace.join_many_str([~"src", pkgid.to_str()]);
     let mut maybe_p = None;
-    let maybe_file = pkg_src_dir.push(filename);
-    debug2!("Trying to frob {} -- {}", pkg_src_dir.to_str(), filename);
+    let maybe_file = pkg_src_dir.join_str(filename);
+    debug2!("Trying to frob {} -- {}", pkg_src_dir.display(), filename);
     if os::path_exists(&maybe_file) {
         maybe_p = Some(maybe_file);
     }
@@ -535,17 +545,17 @@ fn frob_source_file(workspace: &Path, pkgid: &PkgId, filename: &str) {
             }
         }
         None => fail2!("frob_source_file failed to find a source file in {}",
-                           pkg_src_dir.to_str())
+                           pkg_src_dir.display())
     }
 }
 
 #[test]
 fn test_make_dir_rwx() {
     let temp = &os::tmpdir();
-    let dir = temp.push("quux");
+    let dir = temp.join_str("quux");
     assert!(!os::path_exists(&dir) ||
             os::remove_dir_recursive(&dir));
-    debug2!("Trying to make {}", dir.to_str());
+    debug2!("Trying to make {}", dir.display());
     assert!(make_dir_rwx(&dir));
     assert!(os::path_is_dir(&dir));
     assert!(is_rwx(&dir));
@@ -557,12 +567,12 @@ fn test_install_valid() {
     use path_util::installed_library_in_workspace;
 
     let sysroot = test_sysroot();
-    debug2!("sysroot = {}", sysroot.to_str());
+    debug2!("sysroot = {}", sysroot.display());
     let temp_pkg_id = fake_pkg();
     let (temp_workspace, _pkg_dir) = mk_temp_workspace(&temp_pkg_id.path, &NoVersion);
     let temp_workspace = temp_workspace.path();
     let ctxt = fake_ctxt(sysroot, temp_workspace);
-    debug2!("temp_workspace = {}", temp_workspace.to_str());
+    debug2!("temp_workspace = {}", temp_workspace.display());
     // should have test, bench, lib, and main
     let src = PkgSrc::new(temp_workspace.clone(),
                           temp_workspace.clone(),
@@ -571,7 +581,7 @@ fn test_install_valid() {
     ctxt.install(src, &Everything);
     // Check that all files exist
     let exec = target_executable_in_workspace(&temp_pkg_id, temp_workspace);
-    debug2!("exec = {}", exec.to_str());
+    debug2!("exec = {}", exec.display());
     assert!(os::path_exists(&exec));
     assert!(is_rwx(&exec));
 
@@ -583,7 +593,7 @@ fn test_install_valid() {
     // And that the test and bench executables aren't installed
     assert!(!os::path_exists(&target_test_in_workspace(&temp_pkg_id, temp_workspace)));
     let bench = target_bench_in_workspace(&temp_pkg_id, temp_workspace);
-    debug2!("bench = {}", bench.to_str());
+    debug2!("bench = {}", bench.display());
     assert!(!os::path_exists(&bench));
 
     // Make sure the db isn't dirty, so that it doesn't try to save()
@@ -619,29 +629,30 @@ fn test_install_git() {
     let temp_pkg_id = git_repo_pkg();
     let repo = init_git_repo(&temp_pkg_id.path);
     let repo = repo.path();
-    debug2!("repo = {}", repo.to_str());
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test-pkg"]);
-    debug2!("repo_subdir = {}", repo_subdir.to_str());
+    debug2!("repo = {}", repo.display());
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test-pkg"]);
+    debug2!("repo_subdir = {}", repo_subdir.display());
 
-    writeFile(&repo_subdir.push("main.rs"),
+    writeFile(&repo_subdir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&repo_subdir.push("lib.rs"),
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&repo_subdir.push("test.rs"),
+    writeFile(&repo_subdir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&repo_subdir.push("bench.rs"),
+    writeFile(&repo_subdir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
     add_git_tag(&repo_subdir, ~"0.1"); // this has the effect of committing the files
 
     debug2!("test_install_git: calling rustpkg install {} in {}",
-           temp_pkg_id.path.to_str(), repo.to_str());
+           temp_pkg_id.path.display(), repo.display());
     // should have test, bench, lib, and main
-    command_line_test([~"install", temp_pkg_id.path.to_str()], repo);
-    let ws = repo.push(".rust");
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([~"install", temp_pkg_id.path.as_str().unwrap().to_owned()], repo);
+    let ws = repo.join_str(".rust");
     // Check that all files exist
-    debug2!("Checking for files in {}", ws.to_str());
+    debug2!("Checking for files in {}", ws.display());
     let exec = target_executable_in_workspace(&temp_pkg_id, &ws);
-    debug2!("exec = {}", exec.to_str());
+    debug2!("exec = {}", exec.display());
     assert!(os::path_exists(&exec));
     assert!(is_rwx(&exec));
     let _built_lib =
@@ -657,9 +668,9 @@ fn test_install_git() {
     // And that the test and bench executables aren't installed
     let test = target_test_in_workspace(&temp_pkg_id, &ws);
     assert!(!os::path_exists(&test));
-    debug2!("test = {}", test.to_str());
+    debug2!("test = {}", test.display());
     let bench = target_bench_in_workspace(&temp_pkg_id, &ws);
-    debug2!("bench = {}", bench.to_str());
+    debug2!("bench = {}", bench.display());
     assert!(!os::path_exists(&bench));
 }
 
@@ -685,7 +696,7 @@ fn test_package_ids_must_be_relative_path_like() {
             PkgId::new("github.com/catamorphism/test-pkg").to_str());
 
     do cond.trap(|(p, e)| {
-        assert!("" == p.to_str());
+        assert!(p.filename().is_none())
         assert!("0-length pkgid" == e);
         whatever.clone()
     }).inside {
@@ -694,11 +705,14 @@ fn test_package_ids_must_be_relative_path_like() {
     }
 
     do cond.trap(|(p, e)| {
-        assert_eq!(p.to_str(), os::make_absolute(&Path("foo/bar/quux")).to_str());
+        let abs = os::make_absolute(&Path::from_str("foo/bar/quux"));
+        assert_eq!(p, abs);
         assert!("absolute pkgid" == e);
         whatever.clone()
     }).inside {
-        let z = PkgId::new(os::make_absolute(&Path("foo/bar/quux")).to_str());
+        let zp = os::make_absolute(&Path::from_str("foo/bar/quux"));
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        let z = PkgId::new(zp.as_str().unwrap());
         assert_eq!(~"foo-0.1", z.to_str());
     }
 
@@ -707,17 +721,17 @@ fn test_package_ids_must_be_relative_path_like() {
 #[test]
 fn test_package_version() {
     let local_path = "mockgithub.com/catamorphism/test_pkg_version";
-    let repo = init_git_repo(&Path(local_path));
+    let repo = init_git_repo(&Path::from_str(local_path));
     let repo = repo.path();
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test_pkg_version"]);
-    debug2!("Writing files in: {}", repo_subdir.to_str());
-    writeFile(&repo_subdir.push("main.rs"),
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test_pkg_version"]);
+    debug2!("Writing files in: {}", repo_subdir.display());
+    writeFile(&repo_subdir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&repo_subdir.push("lib.rs"),
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&repo_subdir.push("test.rs"),
+    writeFile(&repo_subdir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&repo_subdir.push("bench.rs"),
+    writeFile(&repo_subdir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
     add_git_tag(&repo_subdir, ~"0.4");
 
@@ -726,59 +740,64 @@ fn test_package_version() {
     // This should look at the prefix, clone into a workspace, then build.
     command_line_test([~"install", ~"mockgithub.com/catamorphism/test_pkg_version"],
                       repo);
-    let ws = repo.push(".rust");
+    let ws = repo.join_str(".rust");
     // we can still match on the filename to make sure it contains the 0.4 version
     assert!(match built_library_in_workspace(&temp_pkg_id,
                                              &ws) {
-        Some(p) => p.to_str().ends_with(format!("0.4{}", os::consts::DLL_SUFFIX)),
+        Some(p) => {
+            let suffix = format!("0.4{}", os::consts::DLL_SUFFIX);
+            ends_with(p.as_vec(), suffix.as_bytes())
+        }
         None    => false
     });
     assert!(built_executable_in_workspace(&temp_pkg_id, &ws)
-            == Some(target_build_dir(&ws).push_many([~"mockgithub.com",
-                                                    ~"catamorphism",
-                                                    ~"test_pkg_version",
-                                                    ~"test_pkg_version"])));
+            == Some(target_build_dir(&ws).join_many_str(["mockgithub.com",
+                                                         "catamorphism",
+                                                         "test_pkg_version",
+                                                         "test_pkg_version"])));
 }
 
 #[test]
 fn test_package_request_version() {
     let local_path = "mockgithub.com/catamorphism/test_pkg_version";
-    let repo = init_git_repo(&Path(local_path));
+    let repo = init_git_repo(&Path::from_str(local_path));
     let repo = repo.path();
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test_pkg_version"]);
-    debug2!("Writing files in: {}", repo_subdir.to_str());
-    writeFile(&repo_subdir.push("main.rs"),
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test_pkg_version"]);
+    debug2!("Writing files in: {}", repo_subdir.display());
+    writeFile(&repo_subdir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&repo_subdir.push("lib.rs"),
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&repo_subdir.push("test.rs"),
+    writeFile(&repo_subdir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&repo_subdir.push("bench.rs"),
+    writeFile(&repo_subdir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
-    writeFile(&repo_subdir.push("version-0.3-file.txt"), "hi");
+    writeFile(&repo_subdir.join_str("version-0.3-file.txt"), "hi");
     add_git_tag(&repo_subdir, ~"0.3");
-    writeFile(&repo_subdir.push("version-0.4-file.txt"), "hello");
+    writeFile(&repo_subdir.join_str("version-0.4-file.txt"), "hello");
     add_git_tag(&repo_subdir, ~"0.4");
 
     command_line_test([~"install", format!("{}\\#0.3", local_path)], repo);
 
-    assert!(match installed_library_in_workspace(&Path("test_pkg_version"), &repo.push(".rust")) {
+    assert!(match installed_library_in_workspace(&Path::from_str("test_pkg_version"),
+                                                 &repo.join_str(".rust")) {
         Some(p) => {
-            debug2!("installed: {}", p.to_str());
-            p.to_str().ends_with(format!("0.3{}", os::consts::DLL_SUFFIX))
+            debug2!("installed: {}", p.display());
+            let suffix = format!("0.3{}", os::consts::DLL_SUFFIX);
+            ends_with(p.as_vec(), suffix.as_bytes())
         }
         None    => false
     });
     let temp_pkg_id = PkgId::new("mockgithub.com/catamorphism/test_pkg_version#0.3");
-    assert!(target_executable_in_workspace(&temp_pkg_id, &repo.push(".rust"))
-            == repo.push_many([~".rust", ~"bin", ~"test_pkg_version"]));
+    assert!(target_executable_in_workspace(&temp_pkg_id, &repo.join_str(".rust"))
+            == repo.join_many_str([".rust", "bin", "test_pkg_version"]));
 
-    let dir = target_build_dir(&repo.push(".rust"))
-        .push_rel(&Path("src/mockgithub.com/catamorphism/test_pkg_version-0.3"));
-    debug2!("dir = {}", dir.to_str());
+    let mut dir = target_build_dir(&repo.join_str(".rust"));
+    dir.push_path(&Path::from_str("src/mockgithub.com/catamorphism/test_pkg_version-0.3"));
+    debug2!("dir = {}", dir.display());
     assert!(os::path_is_dir(&dir));
-    assert!(os::path_exists(&dir.push("version-0.3-file.txt")));
-    assert!(!os::path_exists(&dir.push("version-0.4-file.txt")));
+    assert!(os::path_exists(&dir.join_str("version-0.3-file.txt")));
+    assert!(!os::path_exists(&dir.join_str("version-0.4-file.txt")));
 }
 
 #[test]
@@ -791,23 +810,23 @@ fn rustpkg_install_url_2() {
 
 #[test]
 fn rustpkg_library_target() {
-    let foo_repo = init_git_repo(&Path("foo"));
+    let foo_repo = init_git_repo(&Path::from_str("foo"));
     let foo_repo = foo_repo.path();
-    let package_dir = foo_repo.push("foo");
+    let package_dir = foo_repo.join_str("foo");
 
-    debug2!("Writing files in: {}", package_dir.to_str());
-    writeFile(&package_dir.push("main.rs"),
+    debug2!("Writing files in: {}", package_dir.display());
+    writeFile(&package_dir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&package_dir.push("lib.rs"),
+    writeFile(&package_dir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
-    writeFile(&package_dir.push("test.rs"),
+    writeFile(&package_dir.join_str("test.rs"),
               "#[test] pub fn f() { (); }");
-    writeFile(&package_dir.push("bench.rs"),
+    writeFile(&package_dir.join_str("bench.rs"),
               "#[bench] pub fn f() { (); }");
 
     add_git_tag(&package_dir, ~"1.0");
     command_line_test([~"install", ~"foo"], foo_repo);
-    assert_lib_exists(&foo_repo.push(".rust"), &Path("foo"), ExactRevision(~"1.0"));
+    assert_lib_exists(&foo_repo.join_str(".rust"), &Path::from_str("foo"), ExactRevision(~"1.0"));
 }
 
 #[test]
@@ -822,29 +841,31 @@ fn rustpkg_local_pkg() {
 fn package_script_with_default_build() {
     let dir = create_local_package(&PkgId::new("fancy-lib"));
     let dir = dir.path();
-    debug2!("dir = {}", dir.to_str());
-    let source = test_sysroot().pop().pop().pop().push_many(
-        [~"src", ~"librustpkg", ~"testsuite", ~"pass", ~"src", ~"fancy-lib", ~"pkg.rs"]);
-    debug2!("package_script_with_default_build: {}", source.to_str());
+    debug2!("dir = {}", dir.display());
+    let mut source = test_sysroot().dir_path();
+    source.pop(); source.pop();
+    source.push_many_str(
+        ["src", "librustpkg", "testsuite", "pass", "src", "fancy-lib", "pkg.rs"]);
+    debug2!("package_script_with_default_build: {}", source.display());
     if !os::copy_file(&source,
-                      &dir.push_many([~"src", ~"fancy-lib-0.1", ~"pkg.rs"])) {
+                      &dir.join_many_str(["src", "fancy-lib-0.1", "pkg.rs"])) {
         fail2!("Couldn't copy file");
     }
     command_line_test([~"install", ~"fancy-lib"], dir);
-    assert_lib_exists(dir, &Path("fancy-lib"), NoVersion);
-    assert!(os::path_exists(&target_build_dir(dir).push_many([~"fancy-lib", ~"generated.rs"])));
+    assert_lib_exists(dir, &Path::from_str("fancy-lib"), NoVersion);
+    assert!(os::path_exists(&target_build_dir(dir).join_many_str(["fancy-lib", "generated.rs"])));
 }
 
 #[test]
 fn rustpkg_build_no_arg() {
     let tmp = TempDir::new("rustpkg_build_no_arg").expect("rustpkg_build_no_arg failed");
-    let tmp = tmp.path().push(".rust");
-    let package_dir = tmp.push_many([~"src", ~"foo"]);
+    let tmp = tmp.path().join_str(".rust");
+    let package_dir = tmp.join_many_str(["src", "foo"]);
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
 
-    writeFile(&package_dir.push("main.rs"),
+    writeFile(&package_dir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    debug2!("build_no_arg: dir = {}", package_dir.to_str());
+    debug2!("build_no_arg: dir = {}", package_dir.display());
     command_line_test([~"build"], &package_dir);
     assert_built_executable_exists(&tmp, "foo");
 }
@@ -852,26 +873,26 @@ fn rustpkg_build_no_arg() {
 #[test]
 fn rustpkg_install_no_arg() {
     let tmp = TempDir::new("rustpkg_install_no_arg").expect("rustpkg_install_no_arg failed");
-    let tmp = tmp.path().push(".rust");
-    let package_dir = tmp.push_many([~"src", ~"foo"]);
+    let tmp = tmp.path().join_str(".rust");
+    let package_dir = tmp.join_many_str(["src", "foo"]);
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
-    writeFile(&package_dir.push("lib.rs"),
+    writeFile(&package_dir.join_str("lib.rs"),
               "fn main() { let _x = (); }");
-    debug2!("install_no_arg: dir = {}", package_dir.to_str());
+    debug2!("install_no_arg: dir = {}", package_dir.display());
     command_line_test([~"install"], &package_dir);
-    assert_lib_exists(&tmp, &Path("foo"), NoVersion);
+    assert_lib_exists(&tmp, &Path::from_str("foo"), NoVersion);
 }
 
 #[test]
 fn rustpkg_clean_no_arg() {
     let tmp = TempDir::new("rustpkg_clean_no_arg").expect("rustpkg_clean_no_arg failed");
-    let tmp = tmp.path().push(".rust");
-    let package_dir = tmp.push_many([~"src", ~"foo"]);
+    let tmp = tmp.path().join_str(".rust");
+    let package_dir = tmp.join_many_str(["src", "foo"]);
     assert!(os::mkdir_recursive(&package_dir, U_RWX));
 
-    writeFile(&package_dir.push("main.rs"),
+    writeFile(&package_dir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    debug2!("clean_no_arg: dir = {}", package_dir.to_str());
+    debug2!("clean_no_arg: dir = {}", package_dir.display());
     command_line_test([~"build"], &package_dir);
     assert_built_executable_exists(&tmp, "foo");
     command_line_test([~"clean"], &package_dir);
@@ -882,16 +903,17 @@ fn rustpkg_clean_no_arg() {
 #[test]
 fn rust_path_test() {
     let dir_for_path = TempDir::new("more_rust").expect("rust_path_test failed");
-    let dir = mk_workspace(dir_for_path.path(), &Path("foo"), &NoVersion);
-    debug2!("dir = {}", dir.to_str());
-    writeFile(&dir.push("main.rs"), "fn main() { let _x = (); }");
+    let dir = mk_workspace(dir_for_path.path(), &Path::from_str("foo"), &NoVersion);
+    debug2!("dir = {}", dir.display());
+    writeFile(&dir.join_str("main.rs"), "fn main() { let _x = (); }");
 
     let cwd = os::getcwd();
-    debug2!("cwd = {}", cwd.to_str());
+    debug2!("cwd = {}", cwd.display());
                                      // use command_line_test_with_env
+    // FIXME (#9639): This needs to handle non-utf8 paths
     command_line_test_with_env([~"install", ~"foo"],
                                &cwd,
-                               Some(~[(~"RUST_PATH", dir_for_path.path().to_str())]));
+                               Some(~[(~"RUST_PATH", dir_for_path.path().as_str().unwrap())]));
     assert_executable_exists(dir_for_path.path(), "foo");
 }
 
@@ -899,21 +921,21 @@ fn rust_path_test() {
 #[ignore] // FIXME(#9184) tests can't change the cwd (other tests are sad then)
 fn rust_path_contents() {
     let dir = TempDir::new("rust_path").expect("rust_path_contents failed");
-    let abc = &dir.path().push_many([~"A", ~"B", ~"C"]);
-    assert!(os::mkdir_recursive(&abc.push(".rust"), U_RWX));
-    assert!(os::mkdir_recursive(&abc.pop().push(".rust"), U_RWX));
-    assert!(os::mkdir_recursive(&abc.pop().pop().push(".rust"), U_RWX));
+    let abc = &dir.path().join_many_str(["A", "B", "C"]);
+    assert!(os::mkdir_recursive(&abc.join_str(".rust"), U_RWX));
+    assert!(os::mkdir_recursive(&abc.with_filename(".rust"), U_RWX));
+    assert!(os::mkdir_recursive(&abc.dir_path().with_filename(".rust"), U_RWX));
     assert!(os::change_dir(abc));
 
     let p = rust_path();
-    let cwd = os::getcwd().push(".rust");
-    let parent = cwd.pop().pop().push(".rust");
-    let grandparent = cwd.pop().pop().pop().push(".rust");
+    let cwd = os::getcwd().join_str(".rust");
+    let parent = cwd.dir_path().with_filename_str(".rust");
+    let grandparent = cwd.dir_path().dir_path().with_filename_str(".rust");
     assert!(p.contains(&cwd));
     assert!(p.contains(&parent));
     assert!(p.contains(&grandparent));
     for a_path in p.iter() {
-        assert!(!a_path.components.is_empty());
+        assert!(a_path.filename().is_some());
     }
 }
 
@@ -921,9 +943,9 @@ fn rust_path_contents() {
 fn rust_path_parse() {
     os::setenv("RUST_PATH", "/a/b/c:/d/e/f:/g/h/i");
     let paths = rust_path();
-    assert!(paths.contains(&Path("/g/h/i")));
-    assert!(paths.contains(&Path("/d/e/f")));
-    assert!(paths.contains(&Path("/a/b/c")));
+    assert!(paths.contains(&Path::from_str("/g/h/i")));
+    assert!(paths.contains(&Path::from_str("/d/e/f")));
+    assert!(paths.contains(&Path::from_str("/a/b/c")));
     os::unsetenv("RUST_PATH");
 }
 
@@ -940,7 +962,8 @@ fn test_list() {
 
 // list doesn't output very much right now...
     command_line_test([~"install", ~"foo"], dir);
-    let env_arg = ~[(~"RUST_PATH", dir.to_str())];
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let env_arg = ~[(~"RUST_PATH", dir.as_str().unwrap().to_owned())];
     let list_output = command_line_test_output_with_env([~"list"], env_arg.clone());
     assert!(list_output.iter().any(|x| x.starts_with("foo")));
 
@@ -966,7 +989,8 @@ fn install_remove() {
     create_local_package_in(&foo, dir);
     create_local_package_in(&bar, dir);
     create_local_package_in(&quux, dir);
-    let rust_path_to_use = ~[(~"RUST_PATH", dir.to_str())];
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let rust_path_to_use = ~[(~"RUST_PATH", dir.as_str().unwrap().to_owned())];
     command_line_test([~"install", ~"foo"], dir);
     command_line_test([~"install", ~"bar"], dir);
     command_line_test([~"install", ~"quux"], dir);
@@ -996,12 +1020,12 @@ fn install_check_duplicates() {
     let mut contents = ~[];
     let check_dups = |p: &PkgId| {
         if contents.contains(p) {
-            fail2!("package {} appears in `list` output more than once", p.path.to_str());
+            fail2!("package {} appears in `list` output more than once", p.path.display());
         }
         else {
             contents.push((*p).clone());
         }
-        false
+        true
     };
     list_installed_packages(check_dups);
 }
@@ -1059,7 +1083,7 @@ fn do_rebuild_dep_dates_change() {
     touch_source_file(workspace, &dep_id);
     command_line_test([~"build", ~"foo"], workspace);
     let new_bar_date = datestamp(&bar_lib_name);
-    debug2!("Datestamp on {} is {:?}", bar_lib_name.to_str(), new_bar_date);
+    debug2!("Datestamp on {} is {:?}", bar_lib_name.display(), new_bar_date);
     assert!(new_bar_date > bar_date);
 }
 
@@ -1120,21 +1144,23 @@ fn test_non_numeric_tag() {
     let temp_pkg_id = git_repo_pkg();
     let repo = init_git_repo(&temp_pkg_id.path);
     let repo = repo.path();
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test-pkg"]);
-    writeFile(&repo_subdir.push("foo"), "foo");
-    writeFile(&repo_subdir.push("lib.rs"),
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test-pkg"]);
+    writeFile(&repo_subdir.join_str("foo"), "foo");
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
     add_git_tag(&repo_subdir, ~"testbranch");
-    writeFile(&repo_subdir.push("testbranch_only"), "hello");
+    writeFile(&repo_subdir.join_str("testbranch_only"), "hello");
     add_git_tag(&repo_subdir, ~"another_tag");
-    writeFile(&repo_subdir.push("not_on_testbranch_only"), "bye bye");
+    writeFile(&repo_subdir.join_str("not_on_testbranch_only"), "bye bye");
     add_all_and_commit(&repo_subdir);
 
-    command_line_test([~"install", format!("{}\\#testbranch", temp_pkg_id.path.to_str())], repo);
-    let file1 = repo.push_many(["mockgithub.com", "catamorphism",
-                                "test-pkg", "testbranch_only"]);
-    let file2 = repo.push_many(["mockgithub.com", "catamorphism", "test-pkg",
-                                "master_only"]);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([~"install", format!("{}\\#testbranch",
+                                           temp_pkg_id.path.as_str().unwrap())], repo);
+    let file1 = repo.join_many_str(["mockgithub.com", "catamorphism",
+                                    "test-pkg", "testbranch_only"]);
+    let file2 = repo.join_many_str(["mockgithub.com", "catamorphism", "test-pkg",
+                                    "master_only"]);
     assert!(os::path_exists(&file1));
     assert!(!os::path_exists(&file2));
 }
@@ -1143,12 +1169,13 @@ fn test_non_numeric_tag() {
 fn test_extern_mod() {
     let dir = TempDir::new("test_extern_mod").expect("test_extern_mod");
     let dir = dir.path();
-    let main_file = dir.push("main.rs");
+    let main_file = dir.join_str("main.rs");
     let lib_depend_dir = TempDir::new("foo").expect("test_extern_mod");
     let lib_depend_dir = lib_depend_dir.path();
-    let aux_dir = lib_depend_dir.push_many(["src", "mockgithub.com", "catamorphism", "test_pkg"]);
+    let aux_dir = lib_depend_dir.join_many_str(["src", "mockgithub.com", "catamorphism",
+                                                "test_pkg"]);
     assert!(os::mkdir_recursive(&aux_dir, U_RWX));
-    let aux_pkg_file = aux_dir.push("lib.rs");
+    let aux_pkg_file = aux_dir.join_str("lib.rs");
 
     writeFile(&aux_pkg_file, "pub mod bar { pub fn assert_true() {  assert!(true); } }\n");
     assert!(os::path_exists(&aux_pkg_file));
@@ -1159,15 +1186,19 @@ fn test_extern_mod() {
 
     command_line_test([~"install", ~"mockgithub.com/catamorphism/test_pkg"], lib_depend_dir);
 
-    let exec_file = dir.push("out");
+    let exec_file = dir.join_str("out");
     // Be sure to extend the existing environment
-    let env = Some([(~"RUST_PATH", lib_depend_dir.to_str())] + os::env());
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let env = Some([(~"RUST_PATH", lib_depend_dir.as_str().unwrap().to_owned())] + os::env());
     let rustpkg_exec = rustpkg_exec();
-    let rustc = rustpkg_exec.with_filename("rustc");
-
-    let mut prog = run::Process::new(rustc.to_str(), [main_file.to_str(),
-                                                      ~"--sysroot", test_sysroot().to_str(),
-                                               ~"-o", exec_file.to_str()],
+    let rustc = rustpkg_exec.with_filename_str("rustc");
+
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let mut prog = run::Process::new(rustc.as_str().unwrap(),
+                                     [main_file.as_str().unwrap().to_owned(),
+                                      ~"--sysroot", test_sys.as_str().unwrap().to_owned(),
+                                      ~"-o", exec_file.as_str().unwrap().to_owned()],
                                      run::ProcessOptions {
         env: env,
         dir: Some(dir),
@@ -1188,12 +1219,12 @@ fn test_extern_mod() {
 fn test_extern_mod_simpler() {
     let dir = TempDir::new("test_extern_mod_simpler").expect("test_extern_mod_simpler");
     let dir = dir.path();
-    let main_file = dir.push("main.rs");
+    let main_file = dir.join_str("main.rs");
     let lib_depend_dir = TempDir::new("foo").expect("test_extern_mod_simpler");
     let lib_depend_dir = lib_depend_dir.path();
-    let aux_dir = lib_depend_dir.push_many(["src", "rust-awesomeness"]);
+    let aux_dir = lib_depend_dir.join_many_str(["src", "rust-awesomeness"]);
     assert!(os::mkdir_recursive(&aux_dir, U_RWX));
-    let aux_pkg_file = aux_dir.push("lib.rs");
+    let aux_pkg_file = aux_dir.join_str("lib.rs");
 
     writeFile(&aux_pkg_file, "pub mod bar { pub fn assert_true() {  assert!(true); } }\n");
     assert!(os::path_exists(&aux_pkg_file));
@@ -1204,21 +1235,25 @@ fn test_extern_mod_simpler() {
 
     command_line_test([~"install", ~"rust-awesomeness"], lib_depend_dir);
 
-    let exec_file = dir.push("out");
+    let exec_file = dir.join_str("out");
     // Be sure to extend the existing environment
-    let env = Some([(~"RUST_PATH", lib_depend_dir.to_str())] + os::env());
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let env = Some([(~"RUST_PATH", lib_depend_dir.as_str().unwrap().to_owned())] + os::env());
     let rustpkg_exec = rustpkg_exec();
-    let rustc = rustpkg_exec.with_filename("rustc");
+    let rustc = rustpkg_exec.with_filename_str("rustc");
+    let test_sys = test_sysroot();
     debug2!("RUST_PATH={} {} {} \n --sysroot {} -o {}",
-                     lib_depend_dir.to_str(),
-                     rustc.to_str(),
-                     main_file.to_str(),
-                     test_sysroot().to_str(),
-                     exec_file.to_str());
-
-    let mut prog = run::Process::new(rustc.to_str(), [main_file.to_str(),
-                                                      ~"--sysroot", test_sysroot().to_str(),
-                                               ~"-o", exec_file.to_str()],
+                     lib_depend_dir.display(),
+                     rustc.display(),
+                     main_file.display(),
+                     test_sys.display(),
+                     exec_file.display());
+
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let mut prog = run::Process::new(rustc.as_str().unwrap(),
+                                     [main_file.as_str().unwrap().to_owned(),
+                                      ~"--sysroot", test_sys.as_str().unwrap().to_owned(),
+                                      ~"-o", exec_file.as_str().unwrap().to_owned()],
                                      run::ProcessOptions {
         env: env,
         dir: Some(dir),
@@ -1240,11 +1275,11 @@ fn test_import_rustpkg() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    writeFile(&workspace.push_many([~"src", ~"foo-0.1", ~"pkg.rs"]),
+    writeFile(&workspace.join_many_str(["src", "foo-0.1", "pkg.rs"]),
               "extern mod rustpkg; fn main() {}");
     command_line_test([~"build", ~"foo"], workspace);
-    debug2!("workspace = {}", workspace.to_str());
-    assert!(os::path_exists(&target_build_dir(workspace).push("foo").push(format!("pkg{}",
+    debug2!("workspace = {}", workspace.display());
+    assert!(os::path_exists(&target_build_dir(workspace).join_str("foo").join_str(format!("pkg{}",
         os::EXE_SUFFIX))));
 }
 
@@ -1253,11 +1288,11 @@ fn test_macro_pkg_script() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    writeFile(&workspace.push_many([~"src", ~"foo-0.1", ~"pkg.rs"]),
+    writeFile(&workspace.join_many_str(["src", "foo-0.1", "pkg.rs"]),
               "extern mod rustpkg; fn main() { debug2!(\"Hi\"); }");
     command_line_test([~"build", ~"foo"], workspace);
-    debug2!("workspace = {}", workspace.to_str());
-    assert!(os::path_exists(&target_build_dir(workspace).push("foo").push(format!("pkg{}",
+    debug2!("workspace = {}", workspace.display());
+    assert!(os::path_exists(&target_build_dir(workspace).join_str("foo").join_str(format!("pkg{}",
         os::EXE_SUFFIX))));
 }
 
@@ -1267,14 +1302,16 @@ fn multiple_workspaces() {
 // Copy the exact same package into directory B and install it
 // Set the RUST_PATH to A:B
 // Make a third package that uses foo, make sure we can build/install it
-    let (a_loc, _pkg_dir) = mk_temp_workspace(&Path("foo"), &NoVersion);
-    let (b_loc, _pkg_dir) = mk_temp_workspace(&Path("foo"), &NoVersion);
+    let (a_loc, _pkg_dir) = mk_temp_workspace(&Path::from_str("foo"), &NoVersion);
+    let (b_loc, _pkg_dir) = mk_temp_workspace(&Path::from_str("foo"), &NoVersion);
     let (a_loc, b_loc) = (a_loc.path(), b_loc.path());
-    debug2!("Trying to install foo in {}", a_loc.to_str());
+    debug2!("Trying to install foo in {}", a_loc.display());
     command_line_test([~"install", ~"foo"], a_loc);
-    debug2!("Trying to install foo in {}", b_loc.to_str());
+    debug2!("Trying to install foo in {}", b_loc.display());
     command_line_test([~"install", ~"foo"], b_loc);
-    let env = Some(~[(~"RUST_PATH", format!("{}:{}", a_loc.to_str(), b_loc.to_str()))]);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let env = Some(~[(~"RUST_PATH", format!("{}:{}", a_loc.as_str().unwrap(),
+                                            b_loc.as_str().unwrap()))]);
     let c_loc = create_local_package_with_dep(&PkgId::new("bar"), &PkgId::new("foo"));
     command_line_test_with_env([~"install", ~"bar"], c_loc.path(), env);
 }
@@ -1291,19 +1328,19 @@ fn rust_path_hack_test(hack_flag: bool) {
    let p_id = PkgId::new("foo");
    let workspace = create_local_package(&p_id);
    let workspace = workspace.path();
-   let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+   let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
    let dest_workspace = dest_workspace.path();
    let rust_path = Some(~[(~"RUST_PATH",
        format!("{}:{}",
-               dest_workspace.to_str(),
-               workspace.push_many(["src", "foo-0.1"]).to_str()))]);
+               dest_workspace.as_str().unwrap(),
+               foo_path.as_str().unwrap()))]);
    command_line_test_with_env(~[~"install"] + if hack_flag { ~[~"--rust-path-hack"] } else { ~[] } +
                                ~[~"foo"], dest_workspace, rust_path);
-   assert_lib_exists(dest_workspace, &Path("foo"), NoVersion);
+   assert_lib_exists(dest_workspace, &Path::from_str("foo"), NoVersion);
    assert_executable_exists(dest_workspace, "foo");
    assert_built_library_exists(dest_workspace, "foo");
    assert_built_executable_exists(dest_workspace, "foo");
-   assert!(!lib_exists(workspace, &Path("foo"), NoVersion));
+   assert!(!lib_exists(workspace, &Path::from_str("foo"), NoVersion));
    assert!(!executable_exists(workspace, "foo"));
    assert!(!built_library_exists(workspace, "foo"));
    assert!(!built_executable_exists(workspace, "foo"));
@@ -1332,18 +1369,19 @@ fn test_rust_path_can_contain_package_dirs_without_flag() {
 fn rust_path_hack_cwd() {
    // Same as rust_path_hack_test, but the CWD is the dir to build out of
    let cwd = TempDir::new("foo").expect("rust_path_hack_cwd");
-   let cwd = cwd.path().push("foo");
+   let cwd = cwd.path().join_str("foo");
    assert!(os::mkdir_recursive(&cwd, U_RWX));
-   writeFile(&cwd.push("lib.rs"), "pub fn f() { }");
+   writeFile(&cwd.join_str("lib.rs"), "pub fn f() { }");
 
-   let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+   let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
    let dest_workspace = dest_workspace.path();
-   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.to_str())]);
+   // FIXME (#9639): This needs to handle non-utf8 paths
+   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.as_str().unwrap().to_owned())]);
    command_line_test_with_env([~"install", ~"--rust-path-hack", ~"foo"], &cwd, rust_path);
-   debug2!("Checking that foo exists in {}", dest_workspace.to_str());
-   assert_lib_exists(dest_workspace, &Path("foo"), NoVersion);
+   debug2!("Checking that foo exists in {}", dest_workspace.display());
+   assert_lib_exists(dest_workspace, &Path::from_str("foo"), NoVersion);
    assert_built_library_exists(dest_workspace, "foo");
-   assert!(!lib_exists(&cwd, &Path("foo"), NoVersion));
+   assert!(!lib_exists(&cwd, &Path::from_str("foo"), NoVersion));
    assert!(!built_library_exists(&cwd, "foo"));
 }
 
@@ -1351,19 +1389,20 @@ fn rust_path_hack_cwd() {
 fn rust_path_hack_multi_path() {
    // Same as rust_path_hack_test, but with a more complex package ID
    let cwd = TempDir::new("pkg_files").expect("rust_path_hack_cwd");
-   let subdir = cwd.path().push_many([~"foo", ~"bar", ~"quux"]);
+   let subdir = cwd.path().join_many_str(["foo", "bar", "quux"]);
    assert!(os::mkdir_recursive(&subdir, U_RWX));
-   writeFile(&subdir.push("lib.rs"), "pub fn f() { }");
+   writeFile(&subdir.join_str("lib.rs"), "pub fn f() { }");
    let name = ~"foo/bar/quux";
 
-   let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+   let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
    let dest_workspace = dest_workspace.path();
-   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.to_str())]);
+   // FIXME (#9639): This needs to handle non-utf8 paths
+   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.as_str().unwrap().to_owned())]);
    command_line_test_with_env([~"install", ~"--rust-path-hack", name.clone()], &subdir, rust_path);
-   debug2!("Checking that {} exists in {}", name, dest_workspace.to_str());
-   assert_lib_exists(dest_workspace, &Path("quux"), NoVersion);
+   debug2!("Checking that {} exists in {}", name, dest_workspace.display());
+   assert_lib_exists(dest_workspace, &Path::from_str("quux"), NoVersion);
    assert_built_library_exists(dest_workspace, name);
-   assert!(!lib_exists(&subdir, &Path("quux"), NoVersion));
+   assert!(!lib_exists(&subdir, &Path::from_str("quux"), NoVersion));
    assert!(!built_library_exists(&subdir, name));
 }
 
@@ -1372,18 +1411,19 @@ fn rust_path_hack_install_no_arg() {
    // Same as rust_path_hack_cwd, but making rustpkg infer the pkg id
    let cwd = TempDir::new("pkg_files").expect("rust_path_hack_install_no_arg");
    let cwd = cwd.path();
-   let source_dir = cwd.push("foo");
+   let source_dir = cwd.join_str("foo");
    assert!(make_dir_rwx(&source_dir));
-   writeFile(&source_dir.push("lib.rs"), "pub fn f() { }");
+   writeFile(&source_dir.join_str("lib.rs"), "pub fn f() { }");
 
-   let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+   let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
    let dest_workspace = dest_workspace.path();
-   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.to_str())]);
+   // FIXME (#9639): This needs to handle non-utf8 paths
+   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.as_str().unwrap().to_owned())]);
    command_line_test_with_env([~"install", ~"--rust-path-hack"], &source_dir, rust_path);
-   debug2!("Checking that foo exists in {}", dest_workspace.to_str());
-   assert_lib_exists(dest_workspace, &Path("foo"), NoVersion);
+   debug2!("Checking that foo exists in {}", dest_workspace.display());
+   assert_lib_exists(dest_workspace, &Path::from_str("foo"), NoVersion);
    assert_built_library_exists(dest_workspace, "foo");
-   assert!(!lib_exists(&source_dir, &Path("foo"), NoVersion));
+   assert!(!lib_exists(&source_dir, &Path::from_str("foo"), NoVersion));
    assert!(!built_library_exists(cwd, "foo"));
 }
 
@@ -1391,15 +1431,16 @@ fn rust_path_hack_install_no_arg() {
 fn rust_path_hack_build_no_arg() {
    // Same as rust_path_hack_install_no_arg, but building instead of installing
    let cwd = TempDir::new("pkg_files").expect("rust_path_hack_build_no_arg");
-   let source_dir = cwd.path().push("foo");
+   let source_dir = cwd.path().join_str("foo");
    assert!(make_dir_rwx(&source_dir));
-   writeFile(&source_dir.push("lib.rs"), "pub fn f() { }");
+   writeFile(&source_dir.join_str("lib.rs"), "pub fn f() { }");
 
-   let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+   let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
    let dest_workspace = dest_workspace.path();
-   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.to_str())]);
+   // FIXME (#9639): This needs to handle non-utf8 paths
+   let rust_path = Some(~[(~"RUST_PATH", dest_workspace.as_str().unwrap().to_owned())]);
    command_line_test_with_env([~"build", ~"--rust-path-hack"], &source_dir, rust_path);
-   debug2!("Checking that foo exists in {}", dest_workspace.to_str());
+   debug2!("Checking that foo exists in {}", dest_workspace.display());
    assert_built_library_exists(dest_workspace, "foo");
    assert!(!built_library_exists(&source_dir, "foo"));
 }
@@ -1408,16 +1449,18 @@ fn rust_path_hack_build_no_arg() {
 fn rust_path_install_target() {
     let dir_for_path = TempDir::new(
         "source_workspace").expect("rust_path_install_target failed");
-    let dir = mk_workspace(dir_for_path.path(), &Path("foo"), &NoVersion);
-    debug2!("dir = {}", dir.to_str());
-    writeFile(&dir.push("main.rs"), "fn main() { let _x = (); }");
+    let mut dir = mk_workspace(dir_for_path.path(), &Path::from_str("foo"), &NoVersion);
+    debug2!("dir = {}", dir.display());
+    writeFile(&dir.join_str("main.rs"), "fn main() { let _x = (); }");
     let dir_to_install_to = TempDir::new(
         "dest_workspace").expect("rust_path_install_target failed");
     let dir_to_install_to = dir_to_install_to.path();
-    let dir = dir.pop().pop();
+    dir.pop(); dir.pop();
 
-    let rust_path = Some(~[(~"RUST_PATH", format!("{}:{}", dir_to_install_to.to_str(),
-                                               dir.to_str()))]);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let rust_path = Some(~[(~"RUST_PATH", format!("{}:{}",
+                                                  dir_to_install_to.as_str().unwrap(),
+                                                  dir.as_str().unwrap()))]);
     let cwd = os::getcwd();
     command_line_test_with_env([~"install", ~"foo"],
                                &cwd,
@@ -1433,8 +1476,10 @@ fn sysroot_flag() {
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
     // no-op sysroot setting; I'm not sure how else to test this
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
     command_line_test([~"--sysroot",
-                       test_sysroot().to_str(),
+                       test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"foo"],
                       workspace);
@@ -1446,7 +1491,9 @@ fn compile_flag_build() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"--no-link",
                        ~"foo"],
@@ -1461,7 +1508,9 @@ fn compile_flag_fail() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test_expect_fail([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"--no-link",
                        ~"foo"],
@@ -1479,7 +1528,9 @@ fn notrans_flag_build() {
                          ~"--pretty", ~"-S"];
 
     for flag in flags_to_test.iter() {
-        command_line_test([test_sysroot().to_str(),
+        let test_sys = test_sysroot();
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        command_line_test([test_sys.as_str().unwrap().to_owned(),
                            ~"build",
                            flag.clone(),
                            ~"foo"],
@@ -1501,14 +1552,16 @@ fn notrans_flag_fail() {
     let flags_to_test = [~"--no-trans", ~"--parse-only",
                          ~"--pretty", ~"-S"];
     for flag in flags_to_test.iter() {
-        command_line_test_expect_fail([test_sysroot().to_str(),
+        let test_sys = test_sysroot();
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                            ~"install",
                            flag.clone(),
                            ~"foo"],
                           workspace, None, BAD_FLAG_CODE);
         assert!(!built_executable_exists(workspace, "foo"));
         assert!(!object_file_exists(workspace, "foo"));
-        assert!(!lib_exists(workspace, &Path("foo"), NoVersion));
+        assert!(!lib_exists(workspace, &Path::from_str("foo"), NoVersion));
     }
 }
 
@@ -1517,7 +1570,9 @@ fn dash_S() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sysroot().as_str().unwrap().to_owned(),
                        ~"build",
                        ~"-S",
                        ~"foo"],
@@ -1532,7 +1587,9 @@ fn dash_S_fail() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test_expect_fail([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"-S",
                        ~"foo"],
@@ -1548,9 +1605,11 @@ fn test_cfg_build() {
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
     // If the cfg flag gets messed up, this won't compile
-    writeFile(&workspace.push_many(["src", "foo-0.1", "main.rs"]),
+    writeFile(&workspace.join_many_str(["src", "foo-0.1", "main.rs"]),
                "#[cfg(quux)] fn main() {}");
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"--cfg",
                        ~"quux",
@@ -1564,9 +1623,11 @@ fn test_cfg_fail() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    writeFile(&workspace.push_many(["src", "foo-0.1", "main.rs"]),
+    writeFile(&workspace.join_many_str(["src", "foo-0.1", "main.rs"]),
                "#[cfg(quux)] fn main() {}");
-    match command_line_test_partial([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    match command_line_test_partial([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"foo"],
                       workspace) {
@@ -1581,7 +1642,9 @@ fn test_emit_llvm_S_build() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"-S", ~"--emit-llvm",
                        ~"foo"],
@@ -1597,7 +1660,9 @@ fn test_emit_llvm_S_fail() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test_expect_fail([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"-S", ~"--emit-llvm",
                        ~"foo"],
@@ -1615,7 +1680,9 @@ fn test_emit_llvm_build() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"--emit-llvm",
                        ~"foo"],
@@ -1632,7 +1699,9 @@ fn test_emit_llvm_fail() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test_expect_fail([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"--emit-llvm",
                        ~"foo"],
@@ -1659,7 +1728,9 @@ fn test_linker_build() {
     let sess = build_session(options,
                              @diagnostic::DefaultEmitter as
                                 @diagnostic::Emitter);
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"--linker",
                        get_cc_prog(sess),
@@ -1681,7 +1752,9 @@ fn test_build_install_flags_fail() {
                      ~[~"-Z", ~"--time-passes"]];
     let cwd = os::getcwd();
     for flag in forbidden.iter() {
-        command_line_test_expect_fail([test_sysroot().to_str(),
+        let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+        command_line_test_expect_fail([test_sys.as_str().unwrap().to_owned(),
                            ~"list"] + *flag, &cwd, None, BAD_FLAG_CODE);
     }
 }
@@ -1691,7 +1764,9 @@ fn test_optimized_build() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"-O",
                        ~"foo"],
@@ -1705,23 +1780,23 @@ fn pkgid_pointing_to_subdir() {
     // rustpkg should recognize that and treat the part after some_repo/ as a subdir
     let workspace = TempDir::new("parent_repo").expect("Couldn't create temp dir");
     let workspace = workspace.path();
-    assert!(os::mkdir_recursive(&workspace.push_many([~"src", ~"mockgithub.com",
-                                                     ~"mozilla", ~"some_repo"]), U_RWX));
+    assert!(os::mkdir_recursive(&workspace.join_many_str(["src", "mockgithub.com",
+                                                          "mozilla", "some_repo"]), U_RWX));
 
-    let foo_dir = workspace.push_many([~"src", ~"mockgithub.com", ~"mozilla", ~"some_repo",
-                                       ~"extras", ~"foo"]);
-    let bar_dir = workspace.push_many([~"src", ~"mockgithub.com", ~"mozilla", ~"some_repo",
-                                       ~"extras", ~"bar"]);
+    let foo_dir = workspace.join_many_str(["src", "mockgithub.com", "mozilla", "some_repo",
+                                           "extras", "foo"]);
+    let bar_dir = workspace.join_many_str(["src", "mockgithub.com", "mozilla", "some_repo",
+                                           "extras", "bar"]);
     assert!(os::mkdir_recursive(&foo_dir, U_RWX));
     assert!(os::mkdir_recursive(&bar_dir, U_RWX));
-    writeFile(&foo_dir.push("lib.rs"), "pub fn f() {}");
-    writeFile(&bar_dir.push("lib.rs"), "pub fn g() {}");
+    writeFile(&foo_dir.join_str("lib.rs"), "pub fn f() {}");
+    writeFile(&bar_dir.join_str("lib.rs"), "pub fn g() {}");
 
-    debug2!("Creating a file in {}", workspace.to_str());
-    let testpkg_dir = workspace.push_many([~"src", ~"testpkg-0.1"]);
+    debug2!("Creating a file in {}", workspace.display());
+    let testpkg_dir = workspace.join_many_str(["src", "testpkg-0.1"]);
     assert!(os::mkdir_recursive(&testpkg_dir, U_RWX));
 
-    writeFile(&testpkg_dir.push("main.rs"),
+    writeFile(&testpkg_dir.join_str("main.rs"),
               "extern mod foo = \"mockgithub.com/mozilla/some_repo/extras/foo\";\n
                extern mod bar = \"mockgithub.com/mozilla/some_repo/extras/bar\";\n
                use foo::f; use bar::g; \n
@@ -1738,22 +1813,23 @@ fn test_recursive_deps() {
     let c_id = PkgId::new("c");
     let b_workspace = create_local_package_with_dep(&b_id, &c_id);
     let b_workspace = b_workspace.path();
-    writeFile(&b_workspace.push("src").push("c-0.1").push("lib.rs"),
+    writeFile(&b_workspace.join_many_str(["src", "c-0.1", "lib.rs"])),
                "pub fn g() {}");
     let a_workspace = create_local_package(&a_id);
     let a_workspace = a_workspace.path();
-    writeFile(&a_workspace.push("src").push("a-0.1").push("main.rs"),
+    writeFile(&a_workspace.join_many_str(["src", "a-0.1", "main.rs"]),
                "extern mod b; use b::f; fn main() { f(); }");
-    writeFile(&b_workspace.push("src").push("b-0.1").push("lib.rs"),
+    writeFile(&b_workspace.join_many_str(["src", "b-0.1", "lib.rs"]),
                "extern mod c; use c::g; pub fn f() { g(); }");
-    let environment = Some(~[(~"RUST_PATH", b_workspace.to_str())]);
-    debug2!("RUST_PATH={}", b_workspace.to_str());
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let environment = Some(~[(~"RUST_PATH", b_workspace.as_str().unwrap().to_owned())]);
+    debug2!("RUST_PATH={}", b_workspace.display());
     command_line_test_with_env([~"install", ~"a"],
                                a_workspace,
                                environment);
-    assert_lib_exists(a_workspace, &Path("a"), NoVersion);
-    assert_lib_exists(b_workspace, &Path("b"), NoVersion);
-    assert_lib_exists(b_workspace, &Path("c"), NoVersion);
+    assert_lib_exists(a_workspace, &Path::from_str("a"), NoVersion);
+    assert_lib_exists(b_workspace, &Path::from_str("b"), NoVersion);
+    assert_lib_exists(b_workspace, &Path::from_str("c"), NoVersion);
 }
 
 #[test]
@@ -1761,13 +1837,16 @@ fn test_install_to_rust_path() {
     let p_id = PkgId::new("foo");
     let second_workspace = create_local_package(&p_id);
     let second_workspace = second_workspace.path();
-    let first_workspace = mk_empty_workspace(&Path("p"), &NoVersion, "dest");
+    let first_workspace = mk_empty_workspace(&Path::from_str("p"), &NoVersion, "dest");
     let first_workspace = first_workspace.path();
+    // FIXME (#9639): This needs to handle non-utf8 paths
     let rust_path = Some(~[(~"RUST_PATH",
-                            format!("{}:{}", first_workspace.to_str(),
-                                 second_workspace.to_str()))]);
-    debug2!("RUST_PATH={}:{}", first_workspace.to_str(), second_workspace.to_str());
-    command_line_test_with_env([test_sysroot().to_str(),
+                            format!("{}:{}", first_workspace.as_str().unwrap(),
+                                    second_workspace.as_str().unwrap()))]);
+    debug2!("RUST_PATH={}:{}", first_workspace.display(), second_workspace.display());
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test_with_env([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"foo"],
                       &os::getcwd(), rust_path);
@@ -1782,13 +1861,15 @@ fn test_target_specific_build_dir() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"build",
                        ~"foo"],
                       workspace);
     assert!(os::path_is_dir(&target_build_dir(workspace)));
     assert!(built_executable_exists(workspace, "foo"));
-    assert!(os::list_dir(&workspace.push("build")).len() == 1);
+    assert!(os::list_dir(&workspace.join_str("build")).len() == 1);
 }
 
 #[test]
@@ -1796,14 +1877,16 @@ fn test_target_specific_install_dir() {
     let p_id = PkgId::new("foo");
     let workspace = create_local_package(&p_id);
     let workspace = workspace.path();
-    command_line_test([test_sysroot().to_str(),
+    let test_sys = test_sysroot();
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([test_sys.as_str().unwrap().to_owned(),
                        ~"install",
                        ~"foo"],
                       workspace);
-    assert!(os::path_is_dir(&workspace.push("lib").push(host_triple())));
-    assert_lib_exists(workspace, &Path("foo"), NoVersion);
-    assert!(os::list_dir(&workspace.push("lib")).len() == 1);
-    assert!(os::path_is_dir(&workspace.push("bin")));
+    assert!(os::path_is_dir(&workspace.join_many_str(["lib", host_triple()])));
+    assert_lib_exists(workspace, &Path::from_str("foo"), NoVersion);
+    assert!(os::list_dir(&workspace.join_str("lib")).len() == 1);
+    assert!(os::path_is_dir(&workspace.join_str("bin")));
     assert_executable_exists(workspace, "foo");
 }
 
@@ -1813,10 +1896,10 @@ fn test_dependencies_terminate() {
     let b_id = PkgId::new("b");
     let workspace = create_local_package(&b_id);
     let workspace = workspace.path();
-    let b_dir = workspace.push_many([~"src", ~"b-0.1"]);
-    let b_subdir = b_dir.push("test");
+    let b_dir = workspace.join_many_str(["src", "b-0.1"]);
+    let b_subdir = b_dir.join_str("test");
     assert!(os::mkdir_recursive(&b_subdir, U_RWX));
-    writeFile(&b_subdir.push("test.rs"),
+    writeFile(&b_subdir.join_str("test.rs"),
               "extern mod b; use b::f; #[test] fn g() { f() }");
     command_line_test([~"install", ~"b"], workspace);
 }
@@ -1877,14 +1960,16 @@ fn correct_package_name_with_rust_path_hack() {
     let bar_id = PkgId::new("bar");
     let foo_workspace = create_local_package(&foo_id);
     let foo_workspace = foo_workspace.path();
-    let dest_workspace = mk_empty_workspace(&Path("bar"), &NoVersion, "dest_workspace");
+    let dest_workspace = mk_empty_workspace(&Path::from_str("bar"), &NoVersion, "dest_workspace");
     let dest_workspace = dest_workspace.path();
 
-    writeFile(&dest_workspace.push_many(["src", "bar-0.1", "main.rs"]),
+    writeFile(&dest_workspace.join_many_str(["src", "bar-0.1", "main.rs"]),
               "extern mod blat; fn main() { let _x = (); }");
 
-    let rust_path = Some(~[(~"RUST_PATH", format!("{}:{}", dest_workspace.to_str(),
-                        foo_workspace.push_many(["src", "foo-0.1"]).to_str()))]);
+    let foo_path = foo_workspace.join_many_str(["src", "foo-0.1"]);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    let rust_path = Some(~[(~"RUST_PATH", format!("{}:{}", dest_workspace.as_str().unwrap(),
+                                                  foo_path.as_str().unwrap()))]);
     // bar doesn't exist, but we want to make sure rustpkg doesn't think foo is bar
     command_line_test_expect_fail([~"install", ~"--rust-path-hack", ~"bar"],
                                   // FIXME #3408: Should be NONEXISTENT_PACKAGE_CODE
@@ -1904,7 +1989,7 @@ fn test_rustpkg_test_creates_exec() {
     let foo_id = PkgId::new("foo");
     let foo_workspace = create_local_package(&foo_id);
     let foo_workspace = foo_workspace.path();
-    writeFile(&foo_workspace.push_many(["src", "foo-0.1", "test.rs"]),
+    writeFile(&foo_workspace.join_many_str(["src", "foo-0.1", "test.rs"]),
               "#[test] fn f() { assert!('a' == 'a'); }");
     command_line_test([~"test", ~"foo"], foo_workspace);
     assert!(test_executable_exists(foo_workspace, "foo"));
@@ -1928,7 +2013,7 @@ fn test_rebuild_when_needed() {
     let foo_id = PkgId::new("foo");
     let foo_workspace = create_local_package(&foo_id);
     let foo_workspace = foo_workspace.path();
-    let test_crate = foo_workspace.push_many(["src", "foo-0.1", "test.rs"]);
+    let test_crate = foo_workspace.join_many_str(["src", "foo-0.1", "test.rs"]);
     writeFile(&test_crate, "#[test] fn f() { assert!('a' == 'a'); }");
     command_line_test([~"test", ~"foo"], foo_workspace);
     assert!(test_executable_exists(foo_workspace, "foo"));
@@ -1948,7 +2033,7 @@ fn test_no_rebuilding() {
     let foo_id = PkgId::new("foo");
     let foo_workspace = create_local_package(&foo_id);
     let foo_workspace = foo_workspace.path();
-    let test_crate = foo_workspace.push_many(["src", "foo-0.1", "test.rs"]);
+    let test_crate = foo_workspace.join_many_str(["src", "foo-0.1", "test.rs"]);
     writeFile(&test_crate, "#[test] fn f() { assert!('a' == 'a'); }");
     command_line_test([~"test", ~"foo"], foo_workspace);
     assert!(test_executable_exists(foo_workspace, "foo"));
@@ -1969,23 +2054,24 @@ fn test_installed_read_only() {
     let temp_pkg_id = git_repo_pkg();
     let repo = init_git_repo(&temp_pkg_id.path);
     let repo = repo.path();
-    debug2!("repo = {}", repo.to_str());
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test-pkg"]);
-    debug2!("repo_subdir = {}", repo_subdir.to_str());
+    debug2!("repo = {}", repo.display());
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test-pkg"]);
+    debug2!("repo_subdir = {}", repo_subdir.display());
 
-    writeFile(&repo_subdir.push("main.rs"),
+    writeFile(&repo_subdir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&repo_subdir.push("lib.rs"),
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
     add_git_tag(&repo_subdir, ~"0.1"); // this has the effect of committing the files
 
-    command_line_test([~"install", temp_pkg_id.path.to_str()], repo);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([~"install", temp_pkg_id.path.as_str().unwrap().to_owned()], repo);
 
-    let ws = repo.push(".rust");
+    let ws = repo.join_str(".rust");
     // Check that all files exist
-    debug2!("Checking for files in {}", ws.to_str());
+    debug2!("Checking for files in {}", ws.display());
     let exec = target_executable_in_workspace(&temp_pkg_id, &ws);
-    debug2!("exec = {}", exec.to_str());
+    debug2!("exec = {}", exec.display());
     assert!(os::path_exists(&exec));
     assert!(is_rwx(&exec));
     let built_lib =
@@ -1995,8 +2081,8 @@ fn test_installed_read_only() {
     assert!(is_rwx(&built_lib));
 
     // Make sure sources are (a) under "build" and (b) read-only
-    let src1 = target_build_dir(&ws).push_many([~"src", temp_pkg_id.to_str(), ~"main.rs"]);
-    let src2 = target_build_dir(&ws).push_many([~"src", temp_pkg_id.to_str(), ~"lib.rs"]);
+    let src1 = target_build_dir(&ws).join_many_str(["src", temp_pkg_id.to_str(), "main.rs"]);
+    let src2 = target_build_dir(&ws).join_many_str(["src", temp_pkg_id.to_str(), "lib.rs"]);
     assert!(os::path_exists(&src1));
     assert!(os::path_exists(&src2));
     assert!(is_read_only(&src1));
@@ -2008,29 +2094,30 @@ fn test_installed_local_changes() {
     let temp_pkg_id = git_repo_pkg();
     let repo = init_git_repo(&temp_pkg_id.path);
     let repo = repo.path();
-    debug2!("repo = {}", repo.to_str());
-    let repo_subdir = repo.push_many([~"mockgithub.com", ~"catamorphism", ~"test-pkg"]);
-    debug2!("repo_subdir = {}", repo_subdir.to_str());
-    assert!(os::mkdir_recursive(&repo.push_many([".rust", "src"]), U_RWX));
+    debug2!("repo = {}", repo.display());
+    let repo_subdir = repo.join_many_str(["mockgithub.com", "catamorphism", "test-pkg"]);
+    debug2!("repo_subdir = {}", repo_subdir.display());
+    assert!(os::mkdir_recursive(&repo.join_many_str([".rust", "src"]), U_RWX));
 
-    writeFile(&repo_subdir.push("main.rs"),
+    writeFile(&repo_subdir.join_str("main.rs"),
               "fn main() { let _x = (); }");
-    writeFile(&repo_subdir.push("lib.rs"),
+    writeFile(&repo_subdir.join_str("lib.rs"),
               "pub fn f() { let _x = (); }");
     add_git_tag(&repo_subdir, ~"0.1"); // this has the effect of committing the files
 
-    command_line_test([~"install", temp_pkg_id.path.to_str()], repo);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([~"install", temp_pkg_id.path.as_str().unwrap().to_owned()], repo);
 
 
     // We installed the dependency.
     // Now start a new workspace and clone it into it
     let hacking_workspace = mk_emptier_workspace("hacking_workspace");
     let hacking_workspace = hacking_workspace.path();
-    let target_dir = hacking_workspace.push_many([~"src",
-                                                  ~"mockgithub.com",
-                                                  ~"catamorphism",
-                                                  ~"test-pkg-0.1"]);
-    debug2!("---- git clone {} {}", repo_subdir.to_str(), target_dir.to_str());
+    let target_dir = hacking_workspace.join_many_str(["src",
+                                                      "mockgithub.com",
+                                                      "catamorphism",
+                                                      "test-pkg-0.1"]);
+    debug2!("---- git clone {} {}", repo_subdir.display(), target_dir.display());
 
     let c_res = safe_git_clone(&repo_subdir, &NoVersion, &target_dir);
 
@@ -2040,19 +2127,21 @@ fn test_installed_local_changes() {
     };
 
     // Make a local change to it
-    writeFile(&target_dir.push("lib.rs"),
+    writeFile(&target_dir.join_str("lib.rs"),
               "pub fn g() { let _x = (); }");
 
     // Finally, make *another* package that uses it
     let importer_pkg_id = fake_pkg();
     let main_subdir = create_local_package_in(&importer_pkg_id, hacking_workspace);
-    writeFile(&main_subdir.push("main.rs"),
+    writeFile(&main_subdir.join_str("main.rs"),
               "extern mod test = \"mockgithub.com/catamorphism/test-pkg\"; \
               use test::g;
               fn main() { g(); }");
     // And make sure we can build it
 
-    command_line_test([~"build", importer_pkg_id.path.to_str()], hacking_workspace);
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    command_line_test([~"build", importer_pkg_id.path.as_str().unwrap().to_owned()],
+                      hacking_workspace);
 }
 
 #[test]
@@ -2060,8 +2149,10 @@ fn test_7402() {
     let dir = create_local_package(&PkgId::new("foo"));
     let dest_workspace = TempDir::new("more_rust").expect("test_7402");
     let dest_workspace = dest_workspace.path();
+    // FIXME (#9639): This needs to handle non-utf8 paths
     let rust_path = Some(~[(~"RUST_PATH",
-                            format!("{}:{}", dest_workspace.to_str(), dir.path().to_str()))]);
+                            format!("{}:{}", dest_workspace.as_str().unwrap(),
+                                    dir.path().as_str().unwrap()))]);
     let cwd = os::getcwd();
     command_line_test_with_env([~"install", ~"foo"], &cwd, rust_path);
     assert_executable_exists(dest_workspace, "foo");
@@ -2072,7 +2163,7 @@ fn test_compile_error() {
     let foo_id = PkgId::new("foo");
     let foo_workspace = create_local_package(&foo_id);
     let foo_workspace = foo_workspace.path();
-    let main_crate = foo_workspace.push_many(["src", "foo-0.1", "main.rs"]);
+    let main_crate = foo_workspace.join_many_str(["src", "foo-0.1", "main.rs"]);
     // Write something bogus
     writeFile(&main_crate, "pub fn main() { if 42 != ~\"the answer\" { fail!(); } }");
     let result = command_line_test_partial([~"build", ~"foo"], foo_workspace);
diff --git a/src/librustpkg/util.rs b/src/librustpkg/util.rs
index d66dd847405..14de18734ed 100644
--- a/src/librustpkg/util.rs
+++ b/src/librustpkg/util.rs
@@ -170,13 +170,14 @@ pub fn compile_input(context: &BuildContext,
                      cfgs: &[~str],
                      opt: bool,
                      what: OutputType) -> Option<Path> {
-    assert!(in_file.components.len() > 1);
-    let input = driver::file_input((*in_file).clone());
-    debug2!("compile_input: {} / {:?}", in_file.to_str(), what);
+    assert!(in_file.component_iter().nth(1).is_some());
+    let input = driver::file_input(in_file.clone());
+    debug2!("compile_input: {} / {:?}", in_file.display(), what);
     // tjc: by default, use the package ID name as the link name
     // not sure if we should support anything else
 
-    let out_dir = target_build_dir(workspace).push_rel(&pkg_id.path);
+    let mut out_dir = target_build_dir(workspace);
+    out_dir.push_path(&pkg_id.path);
     // Make the output directory if it doesn't exist already
     assert!(os::mkdir_recursive(&out_dir, U_RWX));
 
@@ -184,7 +185,8 @@ pub fn compile_input(context: &BuildContext,
 
     debug2!("flags: {}", flags.connect(" "));
     debug2!("cfgs: {}", cfgs.connect(" "));
-    debug2!("compile_input's sysroot = {}", context.sysroot().to_str());
+    let csysroot = context.sysroot();
+    debug2!("compile_input's sysroot = {}", csysroot.display());
 
     let crate_type = match what {
         Lib => lib_crate,
@@ -209,10 +211,15 @@ pub fn compile_input(context: &BuildContext,
         context.sysroot()
     }
     else {
-        context.sysroot().pop().pop().pop()
+        let mut p = context.sysroot().clone();
+        p.pop();
+        p.pop();
+        p.pop();
+        p
     };
-    debug2!("compile_input's sysroot = {}", context.sysroot().to_str());
-    debug2!("sysroot_to_use = {}", sysroot_to_use.to_str());
+    let csysroot = context.sysroot();
+    debug2!("compile_input's sysroot = {}", csysroot.display());
+    debug2!("sysroot_to_use = {}", sysroot_to_use.display());
 
     let output_type = match context.compile_upto() {
         Assemble => link::output_type_assembly,
@@ -260,7 +267,7 @@ pub fn compile_input(context: &BuildContext,
 
     find_and_install_dependencies(context, pkg_id, sess, exec, &crate,
                                   |p| {
-                                      debug2!("a dependency: {}", p.to_str());
+                                      debug2!("a dependency: {}", p.display());
                                       // Pass the directory containing a dependency
                                       // as an additional lib search path
                                       if !addl_lib_search_paths.contains(&p) {
@@ -278,18 +285,19 @@ pub fn compile_input(context: &BuildContext,
             _     => pkg_id.short_name.to_managed()
         };
         debug2!("Injecting link name: {}", name_to_use);
+        // FIXME (#9639): This needs to handle non-utf8 paths
         let link_options =
             ~[attr::mk_name_value_item_str(@"name", name_to_use),
               attr::mk_name_value_item_str(@"vers", pkg_id.version.to_str().to_managed())] +
             ~[attr::mk_name_value_item_str(@"package_id",
-                                           pkg_id.path.to_str().to_managed())];
+                                           pkg_id.path.as_str().unwrap().to_managed())];
 
         debug2!("link options: {:?}", link_options);
         crate.attrs = ~[attr::mk_attr(attr::mk_list_item(@"link", link_options))];
     }
 
     debug2!("calling compile_crate_from_input, workspace = {},
-           building_library = {:?}", out_dir.to_str(), sess.building_library);
+           building_library = {:?}", out_dir.display(), sess.building_library);
     let result = compile_crate_from_input(in_file,
                                           exec,
                                           context.compile_upto(),
@@ -303,11 +311,12 @@ pub fn compile_input(context: &BuildContext,
     else {
         result
     };
-    debug2!("About to discover output {}", discovered_output.to_str());
     for p in discovered_output.iter() {
+        debug2!("About to discover output {}", p.display());
         if os::path_exists(p) {
-            debug2!("4. discovering output {}", p.to_str());
-            exec.discover_output("binary", p.to_str(), digest_only_date(p));
+            debug2!("4. discovering output {}", p.display());
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            exec.discover_output("binary", p.as_str().unwrap(), digest_only_date(p));
         }
         // Nothing to do if it doesn't exist -- that could happen if we had the
         // -S or -emit-llvm flags, etc.
@@ -330,21 +339,21 @@ pub fn compile_crate_from_input(input: &Path,
 // given
                                 crate: ast::Crate) -> Option<Path> {
     debug2!("Calling build_output_filenames with {}, building library? {:?}",
-           out_dir.to_str(), sess.building_library);
+           out_dir.display(), sess.building_library);
 
     // bad copy
-    debug2!("out_dir = {}", out_dir.to_str());
+    debug2!("out_dir = {}", out_dir.display());
     let outputs = driver::build_output_filenames(&driver::file_input(input.clone()),
                                                  &Some(out_dir.clone()), &None,
                                                  crate.attrs, sess);
 
     debug2!("Outputs are out_filename: {} and obj_filename: {} and output type = {:?}",
-           outputs.out_filename.to_str(),
-           outputs.obj_filename.to_str(),
+           outputs.out_filename.display(),
+           outputs.obj_filename.display(),
            sess.opts.output_type);
     debug2!("additional libraries:");
     for lib in sess.opts.addl_lib_search_paths.iter() {
-        debug2!("an additional library: {}", lib.to_str());
+        debug2!("an additional library: {}", lib.display());
     }
     let analysis = driver::phase_3_run_analysis_passes(sess, &crate);
     if driver::stop_after_phase_3(sess) { return None; }
@@ -359,9 +368,10 @@ pub fn compile_crate_from_input(input: &Path,
     driver::phase_6_link_output(sess, &translation, outputs);
 
     // Register dependency on the source file
-    exec.discover_input("file", input.to_str(), digest_file_with_date(input));
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    exec.discover_input("file", input.as_str().unwrap(), digest_file_with_date(input));
 
-    debug2!("Built {}, date = {:?}", outputs.out_filename.to_str(),
+    debug2!("Built {}, date = {:?}", outputs.out_filename.display(),
            datestamp(&outputs.out_filename));
 
     Some(outputs.out_filename)
@@ -383,7 +393,7 @@ pub fn compile_crate(ctxt: &BuildContext,
                      crate: &Path, workspace: &Path,
                      flags: &[~str], cfgs: &[~str], opt: bool,
                      what: OutputType) -> Option<Path> {
-    debug2!("compile_crate: crate={}, workspace={}", crate.to_str(), workspace.to_str());
+    debug2!("compile_crate: crate={}, workspace={}", crate.display(), workspace.display());
     debug2!("compile_crate: short_name = {}, flags =...", pkg_id.to_str());
     for fl in flags.iter() {
         debug2!("+++ {}", *fl);
@@ -414,15 +424,16 @@ impl<'self> Visitor<()> for ViewItemVisitor<'self> {
                 // Check standard Rust library path first
                 match system_library(&self.context.sysroot(), lib_name) {
                     Some(ref installed_path) => {
-                        debug2!("It exists: {}", installed_path.to_str());
+                        debug2!("It exists: {}", installed_path.display());
                         // Say that [path for c] has a discovered dependency on
                         // installed_path
                         // For binary files, we only hash the datestamp, not the contents.
                         // I'm not sure what the right thing is.
                         // Now we know that this crate has a discovered dependency on
                         // installed_path
+                        // FIXME (#9639): This needs to handle non-utf8 paths
                         self.exec.discover_input("binary",
-                                                 installed_path.to_str(),
+                                                 installed_path.as_str().unwrap(),
                                                  digest_only_date(installed_path));
                     }
                     None => {
@@ -456,7 +467,8 @@ impl<'self> Visitor<()> for ViewItemVisitor<'self> {
                                                   self.context.context.use_rust_path_hack,
                                                   pkg_id);
                         let (outputs_disc, inputs_disc) =
-                            self.context.install(pkg_src, &JustOne(Path(lib_crate_filename)));
+                            self.context.install(pkg_src,
+                                                 &JustOne(Path::from_str(lib_crate_filename)));
                         debug2!("Installed {}, returned {:?} dependencies and \
                                {:?} transitive dependencies",
                                lib_name, outputs_disc.len(), inputs_disc.len());
@@ -465,24 +477,27 @@ impl<'self> Visitor<()> for ViewItemVisitor<'self> {
                         // It must have installed *something*...
                         assert!(!outputs_disc.is_empty());
                         for dep in outputs_disc.iter() {
-                            debug2!("Discovering a binary input: {}", dep.to_str());
+                            debug2!("Discovering a binary input: {}", dep.display());
+                            // FIXME (#9639): This needs to handle non-utf8 paths
                             self.exec.discover_input("binary",
-                                                     dep.to_str(),
+                                                     dep.as_str().unwrap(),
                                                      digest_only_date(dep));
                             // Also, add an additional search path
-                            debug2!("Installed {} into {}", dep.to_str(), dep.pop().to_str());
-                            (self.save)(dep.pop());
+                            debug2!("Installed {} into {}", dep.display(),
+                                    dep.dir_path().display());
+                            (self.save)(dep.dir_path());
                         }
                         for &(ref what, ref dep) in inputs_disc.iter() {
                             if *what == ~"file" {
                                 self.exec.discover_input(*what,
                                                          *dep,
-                                                         digest_file_with_date(&Path(*dep)));
+                                                         digest_file_with_date(
+                                                             &Path::from_str(*dep)));
                             }
                                 else if *what == ~"binary" {
                                 self.exec.discover_input(*what,
                                                          *dep,
-                                                         digest_only_date(&Path(*dep)));
+                                                         digest_only_date(&Path::from_str(*dep)));
                             }
                                 else {
                                 fail2!("Bad kind: {}", *what);
@@ -559,7 +574,7 @@ fn debug_flags() -> ~[~str] { ~[] }
 
 /// Returns the last-modified date as an Option
 pub fn datestamp(p: &Path) -> Option<libc::time_t> {
-    debug2!("Scrutinizing datestamp for {} - does it exist? {:?}", p.to_str(), os::path_exists(p));
+    debug2!("Scrutinizing datestamp for {} - does it exist? {:?}", p.display(), os::path_exists(p));
     let out = p.stat().map(|stat| stat.st_mtime);
     debug2!("Date = {:?}", out);
     out.map(|t| { t as libc::time_t })
diff --git a/src/librustpkg/version.rs b/src/librustpkg/version.rs
index 17b3cad0c2c..d0c76498c62 100644
--- a/src/librustpkg/version.rs
+++ b/src/librustpkg/version.rs
@@ -98,15 +98,16 @@ pub fn parse_vers(vers: ~str) -> result::Result<semver::Version, ~str> {
 pub fn try_getting_local_version(local_path: &Path) -> Option<Version> {
     let rustpath = rust_path();
     for rp in rustpath.iter() {
-        let local_path = rp.push_rel(local_path);
-        let git_dir = local_path.push(".git");
+        let local_path = rp.join_path(local_path);
+        let git_dir = local_path.join_str(".git");
         if !os::path_is_dir(&git_dir) {
             continue;
         }
+        // FIXME (#9639): This needs to handle non-utf8 paths
         let outp = run::process_output("git",
-                                   [format!("--git-dir={}", git_dir.to_str()), ~"tag", ~"-l"]);
+                                   ["--git-dir=" + git_dir.as_str().unwrap(), ~"tag", ~"-l"]);
 
-        debug2!("git --git-dir={} tag -l ~~~> {:?}", git_dir.to_str(), outp.status);
+        debug2!("git --git-dir={} tag -l ~~~> {:?}", git_dir.display(), outp.status);
 
         if outp.status != 0 {
             continue;
@@ -136,21 +137,23 @@ pub fn try_getting_version(remote_path: &Path) -> Option<Version> {
         let tmp_dir = tmp_dir.expect("try_getting_version: couldn't create temp dir");
         let tmp_dir = tmp_dir.path();
         debug2!("(to get version) executing \\{git clone https://{} {}\\}",
-               remote_path.to_str(),
-               tmp_dir.to_str());
-        let outp  = run::process_output("git", [~"clone",
-                                                format!("https://{}",
-                                                        remote_path.to_str()),
-                                                tmp_dir.to_str()]);
+               remote_path.display(),
+               tmp_dir.display());
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        let outp  = run::process_output("git", [~"clone", format!("https://{}",
+                                                                  remote_path.as_str().unwrap()),
+                                                tmp_dir.as_str().unwrap().to_owned()]);
         if outp.status == 0 {
             debug2!("Cloned it... ( {}, {} )",
                    str::from_utf8(outp.output),
                    str::from_utf8(outp.error));
             let mut output = None;
+            let git_dir = tmp_dir.join_str(".git");
             debug2!("(getting version, now getting tags) executing \\{git --git-dir={} tag -l\\}",
-                   tmp_dir.push(".git").to_str());
+                   git_dir.display());
+            // FIXME (#9639): This needs to handle non-utf8 paths
             let outp = run::process_output("git",
-                                           [format!("--git-dir={}", tmp_dir.push(".git").to_str()),
+                                           ["--git-dir=" + git_dir.as_str().unwrap(),
                                             ~"tag", ~"-l"]);
             let output_text = str::from_utf8(outp.output);
             debug2!("Full output: ( {} ) [{:?}]", output_text, outp.status);
@@ -203,8 +206,8 @@ pub fn try_parsing_version(s: &str) -> Option<Version> {
 
 /// Just an approximation
 fn is_url_like(p: &Path) -> bool {
-    let str = p.to_str();
-    str.split_iter('/').len() > 2
+    // check if there are more than 2 /-separated components
+    p.as_vec().split_iter(|b| *b == '/' as u8).nth(2).is_some()
 }
 
 /// If s is of the form foo#bar, where bar is a valid version
diff --git a/src/librustpkg/workcache_support.rs b/src/librustpkg/workcache_support.rs
index 8af24ff4c38..34404ad625c 100644
--- a/src/librustpkg/workcache_support.rs
+++ b/src/librustpkg/workcache_support.rs
@@ -30,7 +30,12 @@ pub fn digest_file_with_date(path: &Path) -> ~str {
             (*sha).input_str(st.st_mtime.to_str());
             (*sha).result_str()
         }
-        Err(e) => cond.raise((path.clone(), format!("Couldn't read file: {}", e))).to_str()
+        Err(e) => {
+            let path = cond.raise((path.clone(), format!("Couldn't read file: {}", e)));
+            // FIXME (#9639): This needs to handle non-utf8 paths
+            // XXX: I'm pretty sure this is the wrong return value
+            path.as_str().unwrap().to_owned()
+        }
     }
 }
 
@@ -51,13 +56,15 @@ pub fn digest_only_date(path: &Path) -> ~str {
 pub fn discover_outputs(e: &mut workcache::Exec, outputs: ~[Path]) {
     debug2!("Discovering {:?} outputs", outputs.len());
     for p in outputs.iter() {
-        debug2!("Discovering output! {}", p.to_str());
+        debug2!("Discovering output! {}", p.display());
         // For now, assume that all discovered outputs are binaries
-        e.discover_output("binary", p.to_str(), digest_only_date(p));
+        // FIXME (#9639): This needs to handle non-utf8 paths
+        e.discover_output("binary", p.as_str().unwrap(), digest_only_date(p));
     }
 }
 
 /// Returns the function name for building a crate
 pub fn crate_tag(p: &Path) -> ~str {
-    p.to_str() // implicitly, it's "build(p)"...
+    // FIXME (#9639): This needs to handle non-utf8 paths
+    p.as_str().unwrap().to_owned() // implicitly, it's "build(p)"...
 }
diff --git a/src/librustpkg/workspace.rs b/src/librustpkg/workspace.rs
index d5dab15c02a..15f9760a637 100644
--- a/src/librustpkg/workspace.rs
+++ b/src/librustpkg/workspace.rs
@@ -10,7 +10,7 @@
 
 // rustpkg utilities having to do with workspaces
 
-use std::{os,util};
+use std::os;
 use std::path::Path;
 use context::Context;
 use path_util::{workspace_contains_package_id, find_dir_using_rust_path_hack, default_workspace};
@@ -26,8 +26,8 @@ pub fn each_pkg_parent_workspace(cx: &Context, pkgid: &PkgId, action: &fn(&Path)
         // tjc: make this a condition
         fail2!("Package {} not found in any of \
                     the following workspaces: {}",
-                   pkgid.path.to_str(),
-                   rust_path().to_str());
+                   pkgid.path.display(),
+                   rust_path().map(|p| p.to_display_str()).to_str());
     }
     for ws in workspaces.iter() {
         if action(ws) {
@@ -52,7 +52,7 @@ pub fn pkg_parent_workspaces(cx: &Context, pkgid: &PkgId) -> ~[Path] {
 }
 
 pub fn is_workspace(p: &Path) -> bool {
-    os::path_is_dir(&p.push("src"))
+    os::path_is_dir(&p.join_str("src"))
 }
 
 /// Construct a workspace and package-ID name based on the current directory.
@@ -60,16 +60,13 @@ pub fn is_workspace(p: &Path) -> bool {
 pub fn cwd_to_workspace() -> Option<(Path, PkgId)> {
     let cwd = os::getcwd();
     for path in rust_path().move_iter() {
-        let srcpath = path.push("src");
+        let srcpath = path.join_str("src");
         if srcpath.is_ancestor_of(&cwd) {
-            // I'd love to use srcpath.get_relative_to(cwd) but it behaves wrong
-            // I'd say broken, but it has tests enforcing the wrong behavior.
-            // instead, just hack up the components vec
-            let mut pkgid = cwd;
-            pkgid.is_absolute = false;
-            let comps = util::replace(&mut pkgid.components, ~[]);
-            pkgid.components = comps.move_iter().skip(srcpath.components.len()).collect();
-            return Some((path, PkgId::new(pkgid.components.connect("/"))))
+            let rel = cwd.path_relative_from(&srcpath);
+            let rel_s = rel.and_then_ref(|p|p.as_str());
+            if rel_s.is_some() {
+                return Some((path, PkgId::new(rel_s.unwrap())));
+            }
         }
     }
     None