Buildcache: Install into non-default directory layouts (#13797)

* Buildcache: Install into non-default directory layouts

Store a dictionary mapping of original dependency prefixes to dependency hashes

Use the loaded spec to grab the new dependency prefixes in the new directory layout.

Map the original dependency prefixes to the new dependency prefixes using the dependency hashes.

Use the dependency prefixes map to replace original rpaths with new rpaths preserving the order.
For mach-o binaries, use the dependency prefixes map to replace the dependency library entires for libraries and executables and the replace the library id for libraries.

On Linux, patchelf is used to replace the rpaths of elf binaries.
On macOS, install_name_tool is used to replace the rpaths and  dependency libraries  of mach-o binaries and the id of mach-o libraries.
On Linux, macholib is used to replace the dependency libraries of mach-o binaries and the id of mach-o libraries.

Binary text with padding replacement is attempted for all binaries for the following paths:
spack layout root
spack prefix
sbang script location
dependency prefixes
package prefix
 Text replacement is attempted for all text files using the paths above.

Symbolic links to the absolute path of the package install prefix are replaced, all others produce warnings.

4 files changed, 896 insertions, 585 deletions

diff --git a/lib/spack/external/altgraph/__init__.py b/lib/spack/external/altgraph/__init__.py
index 289c6408d1..ee70a9c91b 100644
--- a/lib/spack/external/altgraph/__init__.py
+++ b/lib/spack/external/altgraph/__init__.py
@@ -139,9 +139,12 @@ To display the graph we can use the GraphViz backend::
   @contributor: U{Reka Albert <http://www.phys.psu.edu/~ralbert/>}
 
 '''
-import pkg_resources
-__version__ = pkg_resources.require('altgraph')[0].version
-
+# import pkg_resources
+# __version__ = pkg_resources.require('altgraph')[0].version
+# pkg_resources is not finding the altgraph import despite the fact that it is in sys.path
+# there is no .dist-info or .egg-info for pkg_resources to query the version from
+# so it must be set manually
+__version__ = '0.16.1'
 
 class GraphError(ValueError):
     pass
diff --git a/lib/spack/spack/binary_distribution.py b/lib/spack/spack/binary_distribution.py
index 0569bcc665..7902e5fc58 100644
--- a/lib/spack/spack/binary_distribution.py
+++ b/lib/spack/spack/binary_distribution.py
@@ -10,6 +10,9 @@ import tarfile
 import shutil
 import tempfile
 import hashlib
+import glob
+import platform
+
 from contextlib import closing
 import ruamel.yaml as yaml
 
@@ -53,7 +56,7 @@ BUILD_CACHE_INDEX_TEMPLATE = '''
 BUILD_CACHE_INDEX_ENTRY_TEMPLATE = '  <li><a href="{path}">{path}</a></li>'
 
 
-class NoOverwriteException(Exception):
+class NoOverwriteException(spack.error.SpackError):
     """
     Raised when a file exists and must be overwritten.
     """
@@ -68,14 +71,18 @@ class NoGpgException(spack.error.SpackError):
     """
     Raised when gpg2 is not in PATH
     """
-    pass
+
+    def __init__(self, msg):
+        super(NoGpgException, self).__init__(msg)
 
 
 class NoKeyException(spack.error.SpackError):
     """
     Raised when gpg has no default key added.
     """
-    pass
+
+    def __init__(self, msg):
+        super(NoKeyException, self).__init__(msg)
 
 
 class PickKeyException(spack.error.SpackError):
@@ -84,7 +91,7 @@ class PickKeyException(spack.error.SpackError):
     """
 
     def __init__(self, keys):
-        err_msg = "Multi keys available for signing\n%s\n" % keys
+        err_msg = "Multiple keys available for signing\n%s\n" % keys
         err_msg += "Use spack buildcache create -k <key hash> to pick a key."
         super(PickKeyException, self).__init__(err_msg)
 
@@ -107,7 +114,9 @@ class NewLayoutException(spack.error.SpackError):
     """
     Raised if directory layout is different from buildcache.
     """
-    pass
+
+    def __init__(self, msg):
+        super(NewLayoutException, self).__init__(msg)
 
 
 def build_cache_relative_path():
@@ -137,15 +146,21 @@ def read_buildinfo_file(prefix):
     return buildinfo
 
 
-def write_buildinfo_file(prefix, workdir, rel=False):
+def write_buildinfo_file(spec, workdir, rel=False):
     """
     Create a cache file containing information
     required for the relocation
     """
+    prefix = spec.prefix
     text_to_relocate = []
     binary_to_relocate = []
     link_to_relocate = []
     blacklist = (".spack", "man")
+    prefix_to_hash = dict()
+    prefix_to_hash[str(spec.package.prefix)] = spec.dag_hash()
+    deps = spack.build_environment.get_rpath_deps(spec.package)
+    for d in deps:
+        prefix_to_hash[str(d.prefix)] = d.dag_hash()
     # Do this at during tarball creation to save time when tarball unpacked.
     # Used by make_package_relative to determine binaries to change.
     for root, dirs, files in os.walk(prefix, topdown=True):
@@ -162,8 +177,8 @@ def write_buildinfo_file(prefix, workdir, rel=False):
                         link_to_relocate.append(rel_path_name)
                     else:
                         msg = 'Absolute link %s to %s ' % (path_name, link)
-                        msg += 'outside of stage %s ' % prefix
-                        msg += 'cannot be relocated.'
+                        msg += 'outside of prefix %s ' % prefix
+                        msg += 'should not be relocated.'
                         tty.warn(msg)
 
             if relocate.needs_binary_relocation(m_type, m_subtype):
@@ -184,6 +199,7 @@ def write_buildinfo_file(prefix, workdir, rel=False):
     buildinfo['relocate_textfiles'] = text_to_relocate
     buildinfo['relocate_binaries'] = binary_to_relocate
     buildinfo['relocate_links'] = link_to_relocate
+    buildinfo['prefix_to_hash'] = prefix_to_hash
     filename = buildinfo_file_name(workdir)
     with open(filename, 'w') as outfile:
         outfile.write(syaml.dump(buildinfo, default_flow_style=True))
@@ -356,7 +372,7 @@ def build_tarball(spec, outdir, force=False, rel=False, unsigned=False,
     os.remove(temp_tarfile_path)
 
     # create info for later relocation and create tar
-    write_buildinfo_file(spec.prefix, workdir, rel=rel)
+    write_buildinfo_file(spec, workdir, rel)
 
     # optionally make the paths in the binaries relative to each other
     # in the spack install tree before creating tarball
@@ -370,7 +386,7 @@ def build_tarball(spec, outdir, force=False, rel=False, unsigned=False,
             tty.die(e)
     else:
         try:
-            make_package_placeholder(workdir, spec, allow_root)
+            check_package_relocatable(workdir, spec, allow_root)
         except Exception as e:
             shutil.rmtree(workdir)
             shutil.rmtree(tarfile_dir)
@@ -400,6 +416,7 @@ def build_tarball(spec, outdir, force=False, rel=False, unsigned=False,
     buildinfo = {}
     buildinfo['relative_prefix'] = os.path.relpath(
         spec.prefix, spack.store.layout.root)
+    buildinfo['relative_rpaths'] = rel
     spec_dict['buildinfo'] = buildinfo
     spec_dict['full_hash'] = spec.full_hash()
 
@@ -481,100 +498,149 @@ def make_package_relative(workdir, spec, allow_root):
     """
     prefix = spec.prefix
     buildinfo = read_buildinfo_file(workdir)
-    old_path = buildinfo['buildpath']
+    old_layout_root = buildinfo['buildpath']
     orig_path_names = list()
     cur_path_names = list()
     for filename in buildinfo['relocate_binaries']:
         orig_path_names.append(os.path.join(prefix, filename))
         cur_path_names.append(os.path.join(workdir, filename))
-    if spec.architecture.platform == 'darwin':
+    if (spec.architecture.platform == 'darwin' or
+        spec.architecture.platform == 'test' and
+            platform.system().lower() == 'darwin'):
         relocate.make_macho_binaries_relative(cur_path_names, orig_path_names,
-                                              old_path, allow_root)
-    else:
+                                              old_layout_root)
+    if (spec.architecture.platform == 'linux' or
+        spec.architecture.platform == 'test' and
+            platform.system().lower() == 'linux'):
         relocate.make_elf_binaries_relative(cur_path_names, orig_path_names,
-                                            old_path, allow_root)
+                                            old_layout_root)
+    relocate.check_files_relocatable(cur_path_names, allow_root)
     orig_path_names = list()
     cur_path_names = list()
-    for filename in buildinfo.get('relocate_links', []):
-        orig_path_names.append(os.path.join(prefix, filename))
-        cur_path_names.append(os.path.join(workdir, filename))
+    for linkname in buildinfo.get('relocate_links', []):
+        orig_path_names.append(os.path.join(prefix, linkname))
+        cur_path_names.append(os.path.join(workdir, linkname))
     relocate.make_link_relative(cur_path_names, orig_path_names)
 
 
-def make_package_placeholder(workdir, spec, allow_root):
+def check_package_relocatable(workdir, spec, allow_root):
     """
     Check if package binaries are relocatable.
     Change links to placeholder links.
     """
-    prefix = spec.prefix
     buildinfo = read_buildinfo_file(workdir)
     cur_path_names = list()
     for filename in buildinfo['relocate_binaries']:
         cur_path_names.append(os.path.join(workdir, filename))
     relocate.check_files_relocatable(cur_path_names, allow_root)
 
-    cur_path_names = list()
-    for filename in buildinfo.get('relocate_links', []):
-        cur_path_names.append(os.path.join(workdir, filename))
-    relocate.make_link_placeholder(cur_path_names, workdir, prefix)
-
 
-def relocate_package(workdir, spec, allow_root):
+def relocate_package(spec, allow_root):
     """
     Relocate the given package
     """
+    workdir = str(spec.prefix)
     buildinfo = read_buildinfo_file(workdir)
-    new_path = str(spack.store.layout.root)
-    new_prefix = str(spack.paths.prefix)
-    old_path = str(buildinfo['buildpath'])
-    old_prefix = str(buildinfo.get('spackprefix',
-                                   '/not/in/buildinfo/dictionary'))
-    rel = buildinfo.get('relative_rpaths', False)
-
-    tty.msg("Relocating package from",
-            "%s to %s." % (old_path, new_path))
-    path_names = set()
+    new_layout_root = str(spack.store.layout.root)
+    new_prefix = str(spec.prefix)
+    new_rel_prefix = str(os.path.relpath(new_prefix, new_layout_root))
+    new_spack_prefix = str(spack.paths.prefix)
+    old_layout_root = str(buildinfo['buildpath'])
+    old_spack_prefix = str(buildinfo.get('spackprefix'))
+    old_rel_prefix = buildinfo.get('relative_prefix')
+    old_prefix = os.path.join(old_layout_root, old_rel_prefix)
+    rel = buildinfo.get('relative_rpaths')
+    prefix_to_hash = buildinfo.get('prefix_to_hash', None)
+    if (old_rel_prefix != new_rel_prefix and not prefix_to_hash):
+        msg = "Package tarball was created from an install "
+        msg += "prefix with a different directory layout and an older "
+        msg += "buildcache create implementation. It cannot be relocated."
+        raise NewLayoutException(msg)
+    # older buildcaches do not have the prefix_to_hash dictionary
+    # need to set an empty dictionary and add one entry to
+    # prefix_to_prefix to reproduce the old behavior
+    if not prefix_to_hash:
+        prefix_to_hash = dict()
+    hash_to_prefix = dict()
+    hash_to_prefix[spec.format('{hash}')] = str(spec.package.prefix)
+    new_deps = spack.build_environment.get_rpath_deps(spec.package)
+    for d in new_deps:
+        hash_to_prefix[d.format('{hash}')] = str(d.prefix)
+    prefix_to_prefix = dict()
+    for orig_prefix, hash in prefix_to_hash.items():
+        prefix_to_prefix[orig_prefix] = hash_to_prefix.get(hash, None)
+    prefix_to_prefix[old_prefix] = new_prefix
+    prefix_to_prefix[old_layout_root] = new_layout_root
+
+    tty.debug("Relocating package from",
+              "%s to %s." % (old_layout_root, new_layout_root))
+
+    def is_backup_file(file):
+        return file.endswith('~')
+
+    # Text files containing the prefix text
+    text_names = list()
     for filename in buildinfo['relocate_textfiles']:
-        path_name = os.path.join(workdir, filename)
+        text_name = os.path.join(workdir, filename)
         # Don't add backup files generated by filter_file during install step.
-        if not path_name.endswith('~'):
-            path_names.add(path_name)
-    relocate.relocate_text(path_names, oldpath=old_path,
-                           newpath=new_path, oldprefix=old_prefix,
-                           newprefix=new_prefix)
-    # If the binary files in the package were not edited to use
-    # relative RPATHs, then the RPATHs need to be relocated
-    if rel:
-        if old_path != new_path:
-            files_to_relocate = list(filter(
-                lambda pathname: not relocate.file_is_relocatable(
-                    pathname, paths_to_relocate=[old_path, old_prefix]),
-                map(lambda filename: os.path.join(workdir, filename),
-                    buildinfo['relocate_binaries'])))
-
-            if len(old_path) < len(new_path) and files_to_relocate:
-                tty.debug('Cannot do a binary string replacement with padding '
-                          'for package because %s is longer than %s.' %
-                          (new_path, old_path))
-            else:
-                for path_name in files_to_relocate:
-                    relocate.replace_prefix_bin(path_name, old_path, new_path)
-    else:
-        path_names = set()
-        for filename in buildinfo['relocate_binaries']:
-            path_name = os.path.join(workdir, filename)
-            path_names.add(path_name)
-        if spec.architecture.platform == 'darwin':
-            relocate.relocate_macho_binaries(path_names, old_path,
-                                             new_path, allow_root)
-        else:
-            relocate.relocate_elf_binaries(path_names, old_path,
-                                           new_path, allow_root)
-        path_names = set()
-        for filename in buildinfo.get('relocate_links', []):
-            path_name = os.path.join(workdir, filename)
-            path_names.add(path_name)
-        relocate.relocate_links(path_names, old_path, new_path)
+        if not is_backup_file(text_name):
+            text_names.append(text_name)
+
+# If we are installing back to the same location don't replace anything
+    if old_layout_root != new_layout_root:
+        paths_to_relocate = [old_spack_prefix, old_layout_root]
+        paths_to_relocate.extend(prefix_to_hash.keys())
+        files_to_relocate = list(filter(
+            lambda pathname: not relocate.file_is_relocatable(
+                pathname, paths_to_relocate=paths_to_relocate),
+            map(lambda filename: os.path.join(workdir, filename),
+                buildinfo['relocate_binaries'])))
+        # If the buildcache was not created with relativized rpaths
+        # do the relocation of path in binaries
+        if (spec.architecture.platform == 'darwin' or
+            spec.architecture.platform == 'test' and
+                platform.system().lower() == 'darwin'):
+            relocate.relocate_macho_binaries(files_to_relocate,
+                                             old_layout_root,
+                                             new_layout_root,
+                                             prefix_to_prefix, rel,
+                                             old_prefix,
+                                             new_prefix)
+        if (spec.architecture.platform == 'linux' or
+            spec.architecture.platform == 'test' and
+                platform.system().lower() == 'linux'):
+            relocate.relocate_elf_binaries(files_to_relocate,
+                                           old_layout_root,
+                                           new_layout_root,
+                                           prefix_to_prefix, rel,
+                                           old_prefix,
+                                           new_prefix)
+        # Relocate links to the new install prefix
+            link_names = [linkname
+                          for linkname in buildinfo.get('relocate_links', [])]
+            relocate.relocate_links(link_names,
+                                    old_layout_root,
+                                    new_layout_root,
+                                    old_prefix,
+                                    new_prefix,
+                                    prefix_to_prefix)
+
+    # For all buildcaches
+        # relocate the install prefixes in text files including dependencies
+        relocate.relocate_text(text_names,
+                               old_layout_root, new_layout_root,
+                               old_prefix, new_prefix,
+                               old_spack_prefix,
+                               new_spack_prefix,
+                               prefix_to_prefix)
+
+        # relocate the install prefixes in binary files including dependencies
+        relocate.relocate_text_bin(files_to_relocate,
+                                   old_layout_root, new_layout_root,
+                                   old_prefix, new_prefix,
+                                   old_spack_prefix,
+                                   new_spack_prefix,
+                                   prefix_to_prefix)
 
 
 def extract_tarball(spec, filename, allow_root=False, unsigned=False,
@@ -610,7 +676,7 @@ def extract_tarball(spec, filename, allow_root=False, unsigned=False,
                 Gpg.verify('%s.asc' % specfile_path, specfile_path, suppress)
             except Exception as e:
                 shutil.rmtree(tmpdir)
-                tty.die(e)
+                raise e
         else:
             shutil.rmtree(tmpdir)
             raise NoVerifyException(
@@ -639,22 +705,30 @@ def extract_tarball(spec, filename, allow_root=False, unsigned=False,
     # if the original relative prefix is in the spec file use it
     buildinfo = spec_dict.get('buildinfo', {})
     old_relative_prefix = buildinfo.get('relative_prefix', new_relative_prefix)
+    rel = buildinfo.get('relative_rpaths')
     # if the original relative prefix and new relative prefix differ the
     # directory layout has changed and the  buildcache cannot be installed
-    if old_relative_prefix != new_relative_prefix:
-        shutil.rmtree(tmpdir)
-        msg = "Package tarball was created from an install "
-        msg += "prefix with a different directory layout.\n"
-        msg += "It cannot be relocated."
-        raise NewLayoutException(msg)
+    # if it was created with relative rpaths
+    info = 'old relative prefix %s\nnew relative prefix %s\nrelative rpaths %s'
+    tty.debug(info %
+              (old_relative_prefix, new_relative_prefix, rel))
+#    if (old_relative_prefix != new_relative_prefix and (rel)):
+#        shutil.rmtree(tmpdir)
+#        msg = "Package tarball was created from an install "
+#        msg += "prefix with a different directory layout. "
+#        msg += "It cannot be relocated because it "
+#        msg += "uses relative rpaths."
+#        raise NewLayoutException(msg)
 
     # extract the tarball in a temp directory
     with closing(tarfile.open(tarfile_path, 'r')) as tar:
         tar.extractall(path=tmpdir)
-    # the base of the install prefix is used when creating the tarball
-    # so the pathname should be the same now that the directory layout
-    # is confirmed
-    workdir = os.path.join(tmpdir, os.path.basename(spec.prefix))
+    # get the parent directory of the file .spack/binary_distribution
+    # this should the directory unpacked from the tarball whose
+    # name is unknown because the prefix naming is unknown
+    bindist_file = glob.glob('%s/*/.spack/binary_distribution' % tmpdir)[0]
+    workdir = re.sub('/.spack/binary_distribution$', '', bindist_file)
+    tty.debug('workdir %s' % workdir)
     # install_tree copies hardlinks
     # create a temporary tarfile from prefix and exract it to workdir
     # tarfile preserves hardlinks
@@ -672,10 +746,10 @@ def extract_tarball(spec, filename, allow_root=False, unsigned=False,
     os.remove(specfile_path)
 
     try:
-        relocate_package(spec.prefix, spec, allow_root)
+        relocate_package(spec, allow_root)
     except Exception as e:
         shutil.rmtree(spec.prefix)
-        tty.die(e)
+        raise e
     else:
         manifest_file = os.path.join(spec.prefix,
                                      spack.store.layout.metadata_dir,
@@ -685,6 +759,8 @@ def extract_tarball(spec, filename, allow_root=False, unsigned=False,
             tty.warn('No manifest file in tarball for spec %s' % spec_id)
     finally:
         shutil.rmtree(tmpdir)
+        if os.path.exists(filename):
+            os.remove(filename)
 
 
 # Internal cache for downloaded specs
@@ -732,7 +808,7 @@ def get_spec(spec=None, force=False):
         tty.debug("No Spack mirrors are currently configured")
         return {}
 
-    if spec in _cached_specs:
+    if _cached_specs and spec in _cached_specs:
         return _cached_specs
 
     for mirror in spack.mirror.MirrorCollection().values():
@@ -817,7 +893,7 @@ def get_keys(install=False, trust=False, force=False):
         mirror_dir = url_util.local_file_path(fetch_url_build_cache)
         if mirror_dir:
             tty.msg("Finding public keys in %s" % mirror_dir)
-            files = os.listdir(mirror_dir)
+            files = os.listdir(str(mirror_dir))
             for file in files:
                 if re.search(r'\.key', file) or re.search(r'\.pub', file):
                     link = url_util.join(fetch_url_build_cache, file)
diff --git a/lib/spack/spack/relocate.py b/lib/spack/spack/relocate.py
index c8c7947f9c..7a36434736 100644
--- a/lib/spack/spack/relocate.py
+++ b/lib/spack/spack/relocate.py
@@ -13,6 +13,9 @@ import spack.cmd
 import llnl.util.lang
 from spack.util.executable import Executable, ProcessError
 import llnl.util.tty as tty
+from macholib.MachO import MachO
+from spack.spec import Spec
+import macholib.mach_o
 
 
 class InstallRootStringException(spack.error.SpackError):
@@ -41,45 +44,56 @@ class BinaryStringReplacementException(spack.error.SpackError):
             (file_path, old_len, new_len))
 
 
-class MissingMacholibException(spack.error.SpackError):
+class BinaryTextReplaceException(spack.error.SpackError):
     """
-    Raised when the size of the file changes after binary path substitution.
+    Raised when the new install path is shorter than the old install path
+    so binary text replacement cannot occur.
+    """
+
+    def __init__(self, old_path, new_path):
+        msg = "New path longer than old path: binary text"
+        msg += " replacement not possible."
+        err_msg = "The new path %s" % new_path
+        err_msg += " is longer than the old path %s.\n" % old_path
+        err_msg += "Text replacement in binaries will not work.\n"
+        err_msg += "Create buildcache from an install path "
+        err_msg += "longer than new path."
+        super(BinaryTextReplaceException, self).__init__(msg, err_msg)
+
+
+class PatchelfError(spack.error.SpackError):
+    """
+    Raised when patchelf command returns a ProcessError.
     """
 
     def __init__(self, error):
-        super(MissingMacholibException, self).__init__(
-            "%s\n"
-            "Python package macholib needs to be avaiable to list\n"
-            "and modify a mach-o binary's rpaths, deps and id.\n"
-            "Use virtualenv with pip install macholib or\n"
-            "use spack to install the py-macholib package\n"
-            "spack install py-macholib\n"
-            "spack activate py-macholib\n"
-            "spack load python\n"
-            % error)
+        super(PatchelfError, self).__init__(error)
 
 
 def get_patchelf():
     """
+    Returns the full patchelf binary path if available in $PATH.
     Builds and installs spack patchelf package on linux platforms
-    using the first concretized spec.
-    Returns the full patchelf binary path.
+    using the first concretized spec if it is not installed and
+    returns the full patchelf binary path.
     """
     # as we may need patchelf, find out where it is
     patchelf = spack.util.executable.which('patchelf')
     if patchelf is not None:
         return patchelf.path
-    else:
-        if str(spack.architecture.platform()) == 'test':
-            return None
-        if str(spack.architecture.platform()) == 'darwin':
-            return None
-        patchelf_spec = spack.cmd.parse_specs("patchelf", concretize=True)[0]
-        patchelf = spack.repo.get(patchelf_spec)
-        if not patchelf.installed:
-            patchelf.do_install(use_cache=False)
+    patchelf_spec = Spec('patchelf').concretized()
+    patchelf = patchelf_spec.package
+    if patchelf.installed:
         patchelf_executable = os.path.join(patchelf.prefix.bin, "patchelf")
         return patchelf_executable
+    else:
+        if (str(spack.architecture.platform()) == 'test' or
+            str(spack.architecture.platform()) == 'darwin'):
+            return None
+        else:
+            patchelf.do_install()
+            patchelf_executable = os.path.join(patchelf.prefix.bin, "patchelf")
+            return patchelf_executable
 
 
 def get_existing_elf_rpaths(path_name):
@@ -95,33 +109,53 @@ def get_existing_elf_rpaths(path_name):
     else:
         patchelf = Executable(get_patchelf())
 
+    rpaths = list()
     try:
         output = patchelf('--print-rpath', '%s' %
                           path_name, output=str, error=str)
-        return output.rstrip('\n').split(':')
+        rpaths = output.rstrip('\n').split(':')
     except ProcessError as e:
-        tty.debug('patchelf --print-rpath produced an error on %s' %
-                  path_name, e)
-        return []
-    return
+        msg = 'patchelf --print-rpath %s produced an error %s' % (path_name, e)
+        raise PatchelfError(msg)
+    return rpaths
 
 
-def get_relative_rpaths(path_name, orig_dir, orig_rpaths):
+def get_relative_elf_rpaths(path_name, orig_layout_root, orig_rpaths):
     """
-    Replaces orig_dir with relative path from dirname(path_name) if an rpath
-    in orig_rpaths contains orig_path. Prefixes $ORIGIN
+    Replaces orig rpath with relative path from dirname(path_name) if an rpath
+    in orig_rpaths contains orig_layout_root. Prefixes $ORIGIN
     to relative paths and returns replacement rpaths.
     """
     rel_rpaths = []
     for rpath in orig_rpaths:
-        if re.match(orig_dir, rpath):
+        if re.match(orig_layout_root, rpath):
             rel = os.path.relpath(rpath, start=os.path.dirname(path_name))
-            rel_rpaths.append('$ORIGIN/%s' % rel)
+            rel_rpaths.append(os.path.join('$ORIGIN', '%s' % rel))
         else:
             rel_rpaths.append(rpath)
     return rel_rpaths
 
 
+def get_normalized_elf_rpaths(orig_path_name, rel_rpaths):
+    """
+    Normalize the relative rpaths with respect to the original path name
+    of the file. If the rpath starts with $ORIGIN replace $ORIGIN with the
+    dirname of the original path name and then normalize the rpath.
+    A dictionary mapping relativized rpaths to normalized rpaths is returned.
+    """
+    norm_rpaths = list()
+    for rpath in rel_rpaths:
+        if rpath.startswith('$ORIGIN'):
+            sub = re.sub('$ORIGIN',
+                         os.path.dirname(orig_path_name),
+                         rpath)
+            norm = os.path.normpath(sub)
+            norm_rpaths.append(norm)
+        else:
+            norm_rpaths.append(rpath)
+    return norm_rpaths
+
+
 def set_placeholder(dirname):
     """
     return string of @'s with same length
@@ -129,183 +163,157 @@ def set_placeholder(dirname):
     return '@' * len(dirname)
 
 
-def get_placeholder_rpaths(path_name, orig_rpaths):
+def macho_make_paths_relative(path_name, old_layout_root,
+                              rpaths, deps, idpath):
     """
-    Replaces original layout root dir with a placeholder string in all rpaths.
+    Return a dictionary mapping the original rpaths to the relativized rpaths.
+    This dictionary is used to replace paths in mach-o binaries.
+    Replace old_dir with relative path from dirname of path name
+    in rpaths and deps; idpath is replaced with @rpath/libname.
     """
-    rel_rpaths = []
-    orig_dir = spack.store.layout.root
-    for rpath in orig_rpaths:
-        if re.match(orig_dir, rpath):
-            placeholder = set_placeholder(orig_dir)
-            rel = re.sub(orig_dir, placeholder, rpath)
-            rel_rpaths.append('%s' % rel)
-        else:
-            rel_rpaths.append(rpath)
-    return rel_rpaths
-
-
-def macho_get_paths(path_name):
-    """
-    Examines the output of otool -l path_name for these three fields:
-    LC_ID_DYLIB, LC_LOAD_DYLIB, LC_RPATH and parses out the rpaths,
-    dependiencies and library id.
-    Returns these values.
-    """
-    otool = Executable('otool')
-    output = otool("-l", path_name, output=str, err=str)
-    last_cmd = None
-    idpath = None
-    rpaths = []
-    deps = []
-    for line in output.split('\n'):
-        match = re.search('( *[a-zA-Z]+ )(.*)', line)
-        if match:
-            lhs = match.group(1).lstrip().rstrip()
-            rhs = match.group(2)
-            match2 = re.search(r'(.*) \(.*\)', rhs)
-            if match2:
-                rhs = match2.group(1)
-            if lhs == 'cmd':
-                last_cmd = rhs
-            if lhs == 'path' and last_cmd == 'LC_RPATH':
-                rpaths.append(rhs)
-            if lhs == 'name' and last_cmd == 'LC_ID_DYLIB':
-                idpath = rhs
-            if lhs == 'name' and last_cmd == 'LC_LOAD_DYLIB':
-                deps.append(rhs)
-    return rpaths, deps, idpath
-
-
-def macho_make_paths_relative(path_name, old_dir, rpaths, deps, idpath):
-    """
-    Replace old_dir with relative path from dirname(path_name)
-    in rpaths and deps; idpaths are replaced with @rpath/libname as needed;
-    replacement are returned.
-    """
-    new_idpath = None
+    paths_to_paths = dict()
     if idpath:
-        new_idpath = '@rpath/%s' % os.path.basename(idpath)
-    new_rpaths = list()
-    new_deps = list()
+        paths_to_paths[idpath] = os.path.join(
+            '@rpath', '%s' % os.path.basename(idpath))
     for rpath in rpaths:
-        if re.match(old_dir, rpath):
+        if re.match(old_layout_root, rpath):
             rel = os.path.relpath(rpath, start=os.path.dirname(path_name))
-            new_rpaths.append('@loader_path/%s' % rel)
+            paths_to_paths[rpath] = os.path.join('@loader_path', '%s' % rel)
         else:
-            new_rpaths.append(rpath)
+            paths_to_paths[rpath] = rpath
     for dep in deps:
-        if re.match(old_dir, dep):
+        if re.match(old_layout_root, dep):
             rel = os.path.relpath(dep, start=os.path.dirname(path_name))
-            new_deps.append('@loader_path/%s' % rel)
+            paths_to_paths[dep] = os.path.join('@loader_path', '%s' % rel)
         else:
-            new_deps.append(dep)
-    return (new_rpaths, new_deps, new_idpath)
+            paths_to_paths[dep] = dep
+    return paths_to_paths
 
 
-def macho_make_paths_placeholder(rpaths, deps, idpath):
+def macho_make_paths_normal(orig_path_name, rpaths, deps, idpath):
     """
-    Replace old_dir with a placeholder of the same length
-    in rpaths and deps and idpaths is needed.
-    replacement are returned.
+    Return a dictionary mapping the relativized rpaths to the original rpaths.
+    This dictionary is used to replace paths in mach-o binaries.
+    Replace '@loader_path' with the dirname of the origname path name
+    in rpaths and deps; idpath is replaced with the original path name
     """
-    new_idpath = None
-    old_dir = spack.store.layout.root
-    placeholder = set_placeholder(old_dir)
+    rel_to_orig = dict()
     if idpath:
-        new_idpath = re.sub(old_dir, placeholder, idpath)
-    new_rpaths = list()
-    new_deps = list()
+        rel_to_orig[idpath] = orig_path_name
+
     for rpath in rpaths:
-        if re.match(old_dir, rpath):
-            ph = re.sub(old_dir, placeholder, rpath)
-            new_rpaths.append('%s' % ph)
+        if re.match('@loader_path', rpath):
+            norm = os.path.normpath(re.sub(re.escape('@loader_path'),
+                                           os.path.dirname(orig_path_name),
+                                           rpath))
+            rel_to_orig[rpath] = norm
         else:
-            new_rpaths.append(rpath)
+            rel_to_orig[rpath] = rpath
     for dep in deps:
-        if re.match(old_dir, dep):
-            ph = re.sub(old_dir, placeholder, dep)
-            new_deps.append('%s' % ph)
+        if re.match('@loader_path', dep):
+            norm = os.path.normpath(re.sub(re.escape('@loader_path'),
+                                           os.path.dirname(orig_path_name),
+                                           dep))
+            rel_to_orig[dep] = norm
         else:
-            new_deps.append(dep)
-    return (new_rpaths, new_deps, new_idpath)
-
+            rel_to_orig[dep] = dep
+    return rel_to_orig
+
+
+def macho_find_paths(orig_rpaths, deps, idpath,
+                     old_layout_root, prefix_to_prefix):
+    """
+    Inputs
+    original rpaths from mach-o binaries
+    dependency libraries for mach-o binaries
+    id path of mach-o libraries
+    old install directory layout root
+    prefix_to_prefix dictionary which maps prefixes in the old directory layout
+    to directories in the new directory layout
+    Output
+    paths_to_paths dictionary which maps all of the old paths to new paths
+    """
+    paths_to_paths = dict()
+    for orig_rpath in orig_rpaths:
+        if orig_rpath.startswith(old_layout_root):
+            for old_prefix, new_prefix in prefix_to_prefix.items():
+                if orig_rpath.startswith(old_prefix):
+                    new_rpath = re.sub(re.escape(old_prefix),
+                                       new_prefix, orig_rpath)
+                    paths_to_paths[orig_rpath] = new_rpath
+        else:
+            paths_to_paths[orig_rpath] = orig_rpath
 
-def macho_replace_paths(old_dir, new_dir, rpaths, deps, idpath):
-    """
-    Replace old_dir with new_dir in rpaths, deps and idpath
-    and return replacements
-    """
-    new_idpath = None
     if idpath:
-        new_idpath = idpath.replace(old_dir, new_dir)
-    new_rpaths = list()
-    new_deps = list()
-    for rpath in rpaths:
-        new_rpath = rpath.replace(old_dir, new_dir)
-        new_rpaths.append(new_rpath)
+        for old_prefix, new_prefix in prefix_to_prefix.items():
+            if idpath.startswith(old_prefix):
+                paths_to_paths[idpath] = re.sub(
+                    re.escape(old_prefix), new_prefix, idpath)
     for dep in deps:
-        new_dep = dep.replace(old_dir, new_dir)
-        new_deps.append(new_dep)
-    return new_rpaths, new_deps, new_idpath
+        for old_prefix, new_prefix in prefix_to_prefix.items():
+            if dep.startswith(old_prefix):
+                paths_to_paths[dep] = re.sub(
+                    re.escape(old_prefix), new_prefix, dep)
+        if dep.startswith('@'):
+            paths_to_paths[dep] = dep
+
+    return paths_to_paths
 
 
 def modify_macho_object(cur_path, rpaths, deps, idpath,
-                        new_rpaths, new_deps, new_idpath):
+                        paths_to_paths):
     """
-    Modify MachO binary path_name by replacing old_dir with new_dir
-    or the relative path to spack install root.
-    The old install dir in LC_ID_DYLIB is replaced with the new install dir
-    using install_name_tool -id newid binary
-    The old install dir in LC_LOAD_DYLIB is replaced with the new install dir
-    using install_name_tool -change old new binary
-    The old install dir in LC_RPATH is replaced with the new install dir using
-    install_name_tool  -rpath old new binary
+    This function is used to make machO buildcaches on macOS by
+    replacing old paths with new paths using install_name_tool
+    Inputs:
+    mach-o binary to be modified
+    original rpaths
+    original dependency paths
+    original id path if a mach-o library
+    dictionary mapping paths in old install layout to new install layout
     """
     # avoid error message for libgcc_s
     if 'libgcc_' in cur_path:
         return
     install_name_tool = Executable('install_name_tool')
-    if new_idpath and not idpath == new_idpath:
-        install_name_tool('-id', new_idpath, str(cur_path))
-
-    if len(deps) == len(new_deps):
-        for orig, new in zip(deps, new_deps):
-            if not orig == new:
-                install_name_tool('-change', orig, new, str(cur_path))
-
-    if len(rpaths) == len(new_rpaths):
-        for orig, new in zip(rpaths, new_rpaths):
-            if not orig == new:
-                install_name_tool('-rpath', orig, new, str(cur_path))
 
+    if idpath:
+        new_idpath = paths_to_paths.get(idpath, None)
+        if new_idpath and not idpath == new_idpath:
+            install_name_tool('-id', new_idpath, str(cur_path))
+    for dep in deps:
+        new_dep = paths_to_paths.get(dep)
+        if new_dep and dep != new_dep:
+            install_name_tool('-change', dep, new_dep, str(cur_path))
+
+    for orig_rpath in rpaths:
+        new_rpath = paths_to_paths.get(orig_rpath)
+        if new_rpath and not orig_rpath == new_rpath:
+            install_name_tool('-rpath', orig_rpath, new_rpath, str(cur_path))
     return
 
 
-def modify_object_macholib(cur_path, old_dir, new_dir):
+def modify_object_macholib(cur_path, paths_to_paths):
     """
-    Modify MachO binary path_name by replacing old_dir with new_dir
-    or the relative path to spack install root.
-    The old install dir in LC_ID_DYLIB is replaced with the new install dir
-    using py-macholib
-    The old install dir in LC_LOAD_DYLIB is replaced with the new install dir
-    using py-macholib
-    The old install dir in LC_RPATH is replaced with the new install dir using
-    using py-macholib
+    This function is used when install machO buildcaches on linux by
+    rewriting mach-o loader commands for dependency library paths of
+    mach-o binaries and the id path for mach-o libraries.
+    Rewritting of rpaths is handled by replace_prefix_bin.
+    Inputs
+    mach-o binary to be modified
+    dictionary mapping paths in old install layout to new install layout
     """
-    if cur_path.endswith('.o'):
-        return
-    try:
-        from macholib.MachO import MachO
-    except ImportError as e:
-        raise MissingMacholibException(e)
-
-    def match_func(cpath):
-        rpath = cpath.replace(old_dir, new_dir)
-        return rpath
 
     dll = MachO(cur_path)
-    dll.rewriteLoadCommands(match_func)
+
+    changedict = paths_to_paths
+
+    def changefunc(path):
+        npath = changedict.get(path, None)
+        return npath
+
+    dll.rewriteLoadCommands(changefunc)
+
     try:
         f = open(dll.filename, 'rb+')
         for header in dll.headers:
@@ -320,14 +328,32 @@ def modify_object_macholib(cur_path, old_dir, new_dir):
     return
 
 
-def strings_contains_installroot(path_name, root_dir):
+def macholib_get_paths(cur_path):
     """
-    Check if the file contain the install root string.
+    Get rpaths, dependencies and id of mach-o objects
+    using python macholib package
     """
-    strings = Executable('strings')
-    output = strings('%s' % path_name,
-                     output=str, err=str)
-    return (root_dir in output or spack.paths.prefix in output)
+    dll = MachO(cur_path)
+
+    ident = None
+    rpaths = list()
+    deps = list()
+    for header in dll.headers:
+        rpaths = [data.rstrip(b'\0').decode('utf-8')
+                  for load_command, dylib_command, data in header.commands if
+                  load_command.cmd == macholib.mach_o.LC_RPATH]
+        deps = [data.rstrip(b'\0').decode('utf-8')
+                for load_command, dylib_command, data in header.commands if
+                load_command.cmd == macholib.mach_o.LC_LOAD_DYLIB]
+        idents = [data.rstrip(b'\0').decode('utf-8')
+                  for load_command, dylib_command, data in header.commands if
+                  load_command.cmd == macholib.mach_o.LC_ID_DYLIB]
+        if len(idents) == 1:
+            ident = idents[0]
+    tty.debug('ident: %s' % ident)
+    tty.debug('deps: %s' % deps)
+    tty.debug('rpaths: %s' % rpaths)
+    return (rpaths, deps, ident)
 
 
 def modify_elf_object(path_name, new_rpaths):
@@ -338,9 +364,9 @@ def modify_elf_object(path_name, new_rpaths):
     new_joined = ':'.join(new_rpaths)
 
     # if we're relocating patchelf itself, use it
+    bak_path = path_name + ".bak"
 
     if path_name[-13:] == "/bin/patchelf":
-        bak_path = path_name + ".bak"
         shutil.copy(path_name, bak_path)
         patchelf = Executable(bak_path)
     else:
@@ -350,9 +376,11 @@ def modify_elf_object(path_name, new_rpaths):
         patchelf('--force-rpath', '--set-rpath', '%s' % new_joined,
                  '%s' % path_name, output=str, error=str)
     except ProcessError as e:
-        tty.die('patchelf --set-rpath %s failed' %
-                path_name, e)
+        msg = 'patchelf --set-rpath %s failed with error %s' % (path_name, e)
+        raise PatchelfError(msg)
         pass
+    if os.path.exists(bak_path):
+        os.remove(bak_path)
 
 
 def needs_binary_relocation(m_type, m_subtype):
@@ -447,11 +475,15 @@ def replace_prefix_nullterm(path_name, old_dir, new_dir):
             return data
         return match.group().replace(old_dir.encode('utf-8'),
                                      new_dir.encode('utf-8')) + b'\0' * padding
+
+    if len(new_dir) > len(old_dir):
+        raise BinaryTextReplaceException(old_dir, new_dir)
+
     with open(path_name, 'rb+') as f:
         data = f.read()
         f.seek(0)
         original_data_len = len(data)
-        pat = re.compile(old_dir.encode('utf-8') + b'([^\0]*?)\0')
+        pat = re.compile(re.escape(old_dir).encode('utf-8') + b'([^\0]*?)\0')
         if not pat.search(data):
             return
         ndata = pat.sub(replace, data)
@@ -462,80 +494,129 @@ def replace_prefix_nullterm(path_name, old_dir, new_dir):
         f.truncate()
 
 
-def relocate_macho_binaries(path_names, old_dir, new_dir, allow_root):
+def relocate_macho_binaries(path_names, old_layout_root, new_layout_root,
+                            prefix_to_prefix, rel, old_prefix, new_prefix):
     """
-    Change old_dir to new_dir in LC_RPATH of mach-o files (on macOS)
-    Change old_dir to new_dir in LC_ID and LC_DEP of mach-o files
-    Account for the case where old_dir is now a placeholder
+    Use macholib python package to get the rpaths, depedent libraries
+    and library identity for libraries from the MachO object. Modify them
+    with the replacement paths queried from the dictionary mapping old layout
+    prefixes to hashes and the dictionary mapping hashes to the new layout
+    prefixes.
     """
-    placeholder = set_placeholder(old_dir)
+
     for path_name in path_names:
+        # Corner case where macho object file ended up in the path name list
         if path_name.endswith('.o'):
             continue
-        if new_dir == old_dir:
-            continue
-        if platform.system().lower() == 'darwin':
-            rpaths, deps, idpath = macho_get_paths(path_name)
-            # one pass to replace placeholder
-            (n_rpaths,
-             n_deps,
-             n_idpath) = macho_replace_paths(placeholder,
-                                             new_dir,
-                                             rpaths,
-                                             deps,
-                                             idpath)
-            # another pass to replace old_dir
-            (new_rpaths,
-             new_deps,
-             new_idpath) = macho_replace_paths(old_dir,
-                                               new_dir,
-                                               n_rpaths,
-                                               n_deps,
-                                               n_idpath)
-            modify_macho_object(path_name,
-                                rpaths, deps, idpath,
-                                new_rpaths, new_deps, new_idpath)
+        if rel:
+            # get the relativized paths
+            rpaths, deps, idpath = macholib_get_paths(path_name)
+            # get the file path name in the original prefix
+            orig_path_name = re.sub(re.escape(new_prefix), old_prefix,
+                                    path_name)
+            # get the mapping of the relativized paths to the original
+            # normalized paths
+            rel_to_orig = macho_make_paths_normal(orig_path_name,
+                                                  rpaths, deps,
+                                                  idpath)
+            # replace the relativized paths with normalized paths
+            if platform.system().lower() == 'darwin':
+                modify_macho_object(path_name, rpaths, deps,
+                                    idpath, rel_to_orig)
+            else:
+                modify_object_macholib(path_name,
+                                       rel_to_orig)
+            # get the normalized paths in the mach-o binary
+            rpaths, deps, idpath = macholib_get_paths(path_name)
+            # get the mapping of paths in old prefix to path in new prefix
+            paths_to_paths = macho_find_paths(rpaths, deps, idpath,
+                                              old_layout_root,
+                                              prefix_to_prefix)
+            # replace the old paths with new paths
+            if platform.system().lower() == 'darwin':
+                modify_macho_object(path_name, rpaths, deps,
+                                    idpath, paths_to_paths)
+            else:
+                modify_object_macholib(path_name,
+                                       paths_to_paths)
+            # get the new normalized path in the mach-o binary
+            rpaths, deps, idpath = macholib_get_paths(path_name)
+            # get the mapping of paths to relative paths in the new prefix
+            paths_to_paths = macho_make_paths_relative(path_name,
+                                                       new_layout_root,
+                                                       rpaths, deps, idpath)
+            # replace the new paths with relativized paths in the new prefix
+            if platform.system().lower() == 'darwin':
+                modify_macho_object(path_name, rpaths, deps,
+                                    idpath, paths_to_paths)
+            else:
+                modify_object_macholib(path_name,
+                                       paths_to_paths)
         else:
-            modify_object_macholib(path_name, placeholder, new_dir)
-            modify_object_macholib(path_name, old_dir, new_dir)
-        if len(new_dir) <= len(old_dir):
-            replace_prefix_nullterm(path_name, old_dir, new_dir)
+            # get the paths in the old prefix
+            rpaths, deps, idpath = macholib_get_paths(path_name)
+            # get the mapping of paths in the old prerix to the new prefix
+            paths_to_paths = macho_find_paths(rpaths, deps, idpath,
+                                              old_layout_root,
+                                              prefix_to_prefix)
+            # replace the old paths with new paths
+            if platform.system().lower() == 'darwin':
+                modify_macho_object(path_name, rpaths, deps,
+                                    idpath, paths_to_paths)
+            else:
+                modify_object_macholib(path_name,
+                                       paths_to_paths)
+
+
+def elf_find_paths(orig_rpaths, old_layout_root, prefix_to_prefix):
+    new_rpaths = list()
+    for orig_rpath in orig_rpaths:
+        if orig_rpath.startswith(old_layout_root):
+            for old_prefix, new_prefix in prefix_to_prefix.items():
+                if orig_rpath.startswith(old_prefix):
+                    new_rpaths.append(re.sub(re.escape(old_prefix),
+                                             new_prefix, orig_rpath))
         else:
-            tty.warn('Cannot do a binary string replacement'
-                     ' with padding for %s'
-                     ' because %s is longer than %s' %
-                     (path_name, new_dir, old_dir))
+            new_rpaths.append(orig_rpath)
+    return new_rpaths
 
 
-def relocate_elf_binaries(path_names, old_dir, new_dir, allow_root):
+def relocate_elf_binaries(path_names, old_layout_root, new_layout_root,
+                          prefix_to_prefix, rel, old_prefix, new_prefix):
     """
-    Change old_dir to new_dir in RPATHs of elf binaries
-    Account for the case where old_dir is now a placeholder
+    Use patchelf to get the original rpaths and then replace them with
+    rpaths in the new directory layout.
+    New rpaths are determined from a dictionary mapping the prefixes in the
+    old directory layout to the prefixes in the new directory layout if the
+    rpath was in the old layout root, i.e. system paths are not replaced.
     """
-    placeholder = set_placeholder(old_dir)
     for path_name in path_names:
         orig_rpaths = get_existing_elf_rpaths(path_name)
-        if orig_rpaths:
-            # one pass to replace placeholder
-            n_rpaths = substitute_rpath(orig_rpaths,
-                                        placeholder, new_dir)
-            # one pass to replace old_dir
-            new_rpaths = substitute_rpath(n_rpaths,
-                                          old_dir, new_dir)
+        new_rpaths = list()
+        if rel:
+            # get the file path in the old_prefix
+            orig_path_name = re.sub(re.escape(new_prefix), old_prefix,
+                                    path_name)
+            # get the normalized rpaths in the old prefix using the file path
+            # in the orig prefix
+            orig_norm_rpaths = get_normalized_elf_rpaths(orig_path_name,
+                                                         orig_rpaths)
+            # get the normalize rpaths in the new prefix
+            norm_rpaths = elf_find_paths(orig_norm_rpaths, old_layout_root,
+                                         prefix_to_prefix)
+            # get the relativized rpaths in the new prefix
+            new_rpaths = get_relative_elf_rpaths(path_name, new_layout_root,
+                                                 norm_rpaths)
+            modify_elf_object(path_name, new_rpaths)
+        else:
+            new_rpaths = elf_find_paths(orig_rpaths, old_layout_root,
+                                        prefix_to_prefix)
             modify_elf_object(path_name, new_rpaths)
-            if not new_dir == old_dir:
-                if len(new_dir) <= len(old_dir):
-                    replace_prefix_bin(path_name, old_dir, new_dir)
-                else:
-                    tty.warn('Cannot do a binary string replacement'
-                             ' with padding for %s'
-                             ' because %s is longer than %s.' %
-                             (path_name, new_dir, old_dir))
 
 
 def make_link_relative(cur_path_names, orig_path_names):
     """
-    Change absolute links to be relative.
+    Change absolute links to relative links.
     """
     for cur_path, orig_path in zip(cur_path_names, orig_path_names):
         target = os.readlink(orig_path)
@@ -545,8 +626,8 @@ def make_link_relative(cur_path_names, orig_path_names):
         os.symlink(relative_target, cur_path)
 
 
-def make_macho_binaries_relative(cur_path_names, orig_path_names, old_dir,
-                                 allow_root):
+def make_macho_binaries_relative(cur_path_names, orig_path_names,
+                                 old_layout_root):
     """
     Replace old RPATHs with paths relative to old_dir in binary files
     """
@@ -555,33 +636,26 @@ def make_macho_binaries_relative(cur_path_names, orig_path_names, old_dir,
         deps = set()
         idpath = None
         if platform.system().lower() == 'darwin':
-            (rpaths, deps, idpath) = macho_get_paths(cur_path)
-            (new_rpaths,
-             new_deps,
-             new_idpath) = macho_make_paths_relative(orig_path, old_dir,
-                                                     rpaths, deps, idpath)
+            (rpaths, deps, idpath) = macholib_get_paths(cur_path)
+            paths_to_paths = macho_make_paths_relative(orig_path,
+                                                       old_layout_root,
+                                                       rpaths, deps, idpath)
             modify_macho_object(cur_path,
                                 rpaths, deps, idpath,
-                                new_rpaths, new_deps, new_idpath)
-        if (not allow_root and
-                not file_is_relocatable(cur_path)):
-            raise InstallRootStringException(cur_path, old_dir)
+                                paths_to_paths)
 
 
-def make_elf_binaries_relative(cur_path_names, orig_path_names, old_dir,
-                               allow_root):
+def make_elf_binaries_relative(cur_path_names, orig_path_names,
+                               old_layout_root):
     """
     Replace old RPATHs with paths relative to old_dir in binary files
     """
     for cur_path, orig_path in zip(cur_path_names, orig_path_names):
         orig_rpaths = get_existing_elf_rpaths(cur_path)
         if orig_rpaths:
-            new_rpaths = get_relative_rpaths(orig_path, old_dir,
-                                             orig_rpaths)
+            new_rpaths = get_relative_elf_rpaths(orig_path, old_layout_root,
+                                                 orig_rpaths)
             modify_elf_object(cur_path, new_rpaths)
-        if (not allow_root and
-                not file_is_relocatable(cur_path)):
-            raise InstallRootStringException(cur_path, old_dir)
 
 
 def check_files_relocatable(cur_path_names, allow_root):
@@ -595,63 +669,74 @@ def check_files_relocatable(cur_path_names, allow_root):
                 cur_path, spack.store.layout.root)
 
 
-def make_link_placeholder(cur_path_names, cur_dir, old_dir):
-    """
-    Replace old install path with placeholder in absolute links.
-
-    Links in ``cur_path_names`` must link to absolute paths.
-    """
-    for cur_path in cur_path_names:
-        placeholder = set_placeholder(spack.store.layout.root)
-        placeholder_prefix = old_dir.replace(spack.store.layout.root,
-                                             placeholder)
-        cur_src = os.readlink(cur_path)
-        rel_src = os.path.relpath(cur_src, cur_dir)
-        new_src = os.path.join(placeholder_prefix, rel_src)
-
-        os.unlink(cur_path)
-        os.symlink(new_src, cur_path)
+def relocate_links(linknames, old_layout_root, new_layout_root,
+                   old_install_prefix, new_install_prefix, prefix_to_prefix):
+    """
+    The symbolic links in filenames are absolute links or placeholder links.
+    The old link target is read and the placeholder is replaced by the old
+    layout root. If the old link target is in the old install prefix, the new
+    link target is create by replacing the old install prefix with the new
+    install prefix.
+    """
+    placeholder = set_placeholder(old_layout_root)
+    link_names = [os.path.join(new_install_prefix, linkname)
+                  for linkname in linknames]
+    for link_name in link_names:
+        old_link_target = os.readlink(link_name)
+        old_link_target = re.sub(placeholder, old_layout_root, old_link_target)
+        if old_link_target.startswith(old_install_prefix):
+            new_link_target = re.sub(
+                old_install_prefix, new_install_prefix, old_link_target)
+            os.unlink(link_name)
+            os.symlink(new_link_target, link_name)
+        else:
+            msg = 'Old link target %s' % old_link_target
+            msg += ' for symbolic link %s is outside' % link_name
+            msg += ' of the old install prefix %s.\n' % old_install_prefix
+            msg += 'This symbolic link will not be relocated'
+            msg += ' and might break relocation.'
+            tty.warn(msg)
 
 
-def relocate_links(path_names, old_dir, new_dir):
+def relocate_text(path_names, old_layout_root, new_layout_root,
+                  old_install_prefix, new_install_prefix,
+                  old_spack_prefix, new_spack_prefix,
+                  prefix_to_prefix):
     """
-    Replace old path with new path in link sources.
-
-    Links in ``path_names`` must link to absolute paths or placeholders.
+    Replace old paths with new paths in text files
+    including the path the the spack sbang script
     """
-    placeholder = set_placeholder(old_dir)
-    for path_name in path_names:
-        old_src = os.readlink(path_name)
-        # replace either placeholder or old_dir
-        new_src = old_src.replace(placeholder, new_dir, 1)
-        new_src = new_src.replace(old_dir, new_dir, 1)
-
-        os.unlink(path_name)
-        os.symlink(new_src, path_name)
+    sbangre = '#!/bin/bash %s/bin/sbang' % old_spack_prefix
+    sbangnew = '#!/bin/bash %s/bin/sbang' % new_spack_prefix
 
-
-def relocate_text(path_names, oldpath, newpath, oldprefix, newprefix):
-    """
-    Replace old path with new path in text files
-    including the path the the spack sbang script.
-    """
-    sbangre = '#!/bin/bash %s/bin/sbang' % oldprefix
-    sbangnew = '#!/bin/bash %s/bin/sbang' % newprefix
     for path_name in path_names:
-        replace_prefix_text(path_name, oldpath, newpath)
+        replace_prefix_text(path_name, old_install_prefix, new_install_prefix)
+        for orig_dep_prefix, new_dep_prefix in prefix_to_prefix.items():
+            replace_prefix_text(path_name, orig_dep_prefix, new_dep_prefix)
+        replace_prefix_text(path_name, old_layout_root, new_layout_root)
         replace_prefix_text(path_name, sbangre, sbangnew)
-        replace_prefix_text(path_name, oldprefix, newprefix)
 
 
-def substitute_rpath(orig_rpath, topdir, new_root_path):
-    """
-    Replace topdir with new_root_path RPATH list orig_rpath
-    """
-    new_rpaths = []
-    for path in orig_rpath:
-        new_rpath = path.replace(topdir, new_root_path)
-        new_rpaths.append(new_rpath)
-    return new_rpaths
+def relocate_text_bin(path_names, old_layout_root, new_layout_root,
+                      old_install_prefix, new_install_prefix,
+                      old_spack_prefix, new_spack_prefix,
+                      prefix_to_prefix):
+    """
+      Replace null terminated path strings hard coded into binaries.
+      Raise an exception when the new path in longer than the old path
+      because this breaks the binary.
+      """
+    if len(new_install_prefix) <= len(old_install_prefix):
+        for path_name in path_names:
+            for old_dep_prefix, new_dep_prefix in prefix_to_prefix.items():
+                if len(new_dep_prefix) <= len(old_dep_prefix):
+                    replace_prefix_bin(
+                        path_name, old_dep_prefix, new_dep_prefix)
+            replace_prefix_bin(path_name, old_spack_prefix, new_spack_prefix)
+    else:
+        if len(path_names) > 0:
+            raise BinaryTextReplaceException(
+                old_install_prefix, new_install_prefix)
 
 
 def is_relocatable(spec):
@@ -729,7 +814,7 @@ def file_is_relocatable(file, paths_to_relocate=None):
             set_of_strings.discard(rpaths)
     if platform.system().lower() == 'darwin':
         if m_subtype == 'x-mach-binary':
-            rpaths, deps, idpath = macho_get_paths(file)
+            rpaths, deps, idpath = macholib_get_paths(file)
             set_of_strings.discard(set(rpaths))
             set_of_strings.discard(set(deps))
             if idpath is not None:
@@ -779,6 +864,8 @@ def mime_type(file):
     file_cmd = Executable('file')
     output = file_cmd('-b', '-h', '--mime-type', file, output=str, error=str)
     tty.debug('[MIME_TYPE] {0} -> {1}'.format(file, output.strip()))
+    # In corner cases the output does not contain a subtype prefixed with a /
+    # In those cases add the / so the tuple can be formed.
     if '/' not in output:
         output += '/'
     split_by_slash = output.strip().split('/')
diff --git a/lib/spack/spack/test/packaging.py b/lib/spack/spack/test/packaging.py
index 39d12df7b7..5d5b2ccf8b 100644
--- a/lib/spack/spack/test/packaging.py
+++ b/lib/spack/spack/test/packaging.py
@@ -8,10 +8,11 @@ This test checks the binary packaging infrastructure
 """
 import os
 import stat
-import sys
 import shutil
 import pytest
 import argparse
+import re
+import platform
 
 from llnl.util.filesystem import mkdirp
 
@@ -19,16 +20,15 @@ import spack.repo
 import spack.store
 import spack.binary_distribution as bindist
 import spack.cmd.buildcache as buildcache
-import spack.util.gpg
 from spack.spec import Spec
 from spack.paths import mock_gpg_keys_path
 from spack.fetch_strategy import URLFetchStrategy, FetchStrategyComposite
 from spack.relocate import needs_binary_relocation, needs_text_relocation
-from spack.relocate import strings_contains_installroot
-from spack.relocate import get_patchelf, relocate_text, relocate_links
-from spack.relocate import substitute_rpath, get_relative_rpaths
-from spack.relocate import macho_replace_paths, macho_make_paths_relative
-from spack.relocate import modify_macho_object, macho_get_paths
+from spack.relocate import relocate_text, relocate_links
+from spack.relocate import get_relative_elf_rpaths
+from spack.relocate import macho_make_paths_relative
+from spack.relocate import set_placeholder, macho_find_paths
+from spack.relocate import file_is_relocatable
 
 
 def has_gpg():
@@ -50,9 +50,9 @@ def fake_fetchify(url, pkg):
 @pytest.mark.usefixtures('install_mockery', 'mock_gnupghome')
 def test_buildcache(mock_archive, tmpdir):
     # tweak patchelf to only do a download
-    spec = Spec("patchelf")
-    spec.concretize()
-    pkg = spack.repo.get(spec)
+    pspec = Spec("patchelf")
+    pspec.concretize()
+    pkg = spack.repo.get(pspec)
     fake_fetchify(pkg.fetcher, pkg)
     mkdirp(os.path.join(pkg.prefix, "bin"))
     patchelfscr = os.path.join(pkg.prefix, "bin", "patchelf")
@@ -71,7 +71,7 @@ echo $PATH"""
     pkg = spec.package
     fake_fetchify(mock_archive.url, pkg)
     pkg.do_install()
-    pkghash = '/' + spec.dag_hash(7)
+    pkghash = '/' + str(spec.dag_hash(7))
 
     # Put some non-relocatable file in there
     filename = os.path.join(spec.prefix, "dummy.txt")
@@ -99,88 +99,69 @@ echo $PATH"""
     parser = argparse.ArgumentParser()
     buildcache.setup_parser(parser)
 
+    create_args = ['create', '-a', '-f', '-d', mirror_path, pkghash]
     # Create a private key to sign package with if gpg2 available
     if spack.util.gpg.Gpg.gpg():
         spack.util.gpg.Gpg.create(name='test key 1', expires='0',
                                   email='spack@googlegroups.com',
                                   comment='Spack test key')
-        # Create build cache with signing
-        args = parser.parse_args(['create', '-d', mirror_path, str(spec)])
-        buildcache.buildcache(parser, args)
-
-        # Uninstall the package
-        pkg.do_uninstall(force=True)
-
-        # test overwrite install
-        args = parser.parse_args(['install', '-f', str(pkghash)])
-        buildcache.buildcache(parser, args)
-
-        files = os.listdir(spec.prefix)
+    else:
+        create_args.insert(create_args.index('-a'), '-u')
 
-        # create build cache with relative path and signing
-        args = parser.parse_args(
-            ['create', '-d', mirror_path, '-f', '-r', str(spec)])
-        buildcache.buildcache(parser, args)
+    args = parser.parse_args(create_args)
+    buildcache.buildcache(parser, args)
+    # trigger overwrite warning
+    buildcache.buildcache(parser, args)
 
-        # Uninstall the package
-        pkg.do_uninstall(force=True)
+    # Uninstall the package
+    pkg.do_uninstall(force=True)
 
-        # install build cache with verification
-        args = parser.parse_args(['install', str(spec)])
-        buildcache.install_tarball(spec, args)
+    install_args = ['install', '-a', '-f', pkghash]
+    if not spack.util.gpg.Gpg.gpg():
+        install_args.insert(install_args.index('-a'), '-u')
+    args = parser.parse_args(install_args)
+    # Test install
+    buildcache.buildcache(parser, args)
 
-        # test overwrite install
-        args = parser.parse_args(['install', '-f', str(pkghash)])
-        buildcache.buildcache(parser, args)
+    files = os.listdir(spec.prefix)
 
-    else:
-        # create build cache without signing
-        args = parser.parse_args(
-            ['create', '-d', mirror_path, '-f', '-u', str(spec)])
-        buildcache.buildcache(parser, args)
-
-        # Uninstall the package
-        pkg.do_uninstall(force=True)
-
-        # install build cache without verification
-        args = parser.parse_args(['install', '-u', str(spec)])
-        buildcache.install_tarball(spec, args)
-
-        files = os.listdir(spec.prefix)
-        assert 'link_to_dummy.txt' in files
-        assert 'dummy.txt' in files
-        # test overwrite install without verification
-        args = parser.parse_args(['install', '-f', '-u', str(pkghash)])
-        buildcache.buildcache(parser, args)
-
-        # create build cache with relative path
-        args = parser.parse_args(
-            ['create', '-d', mirror_path, '-f', '-r', '-u', str(pkghash)])
-        buildcache.buildcache(parser, args)
-
-        # Uninstall the package
-        pkg.do_uninstall(force=True)
-
-        # install build cache
-        args = parser.parse_args(['install', '-u', str(spec)])
-        buildcache.install_tarball(spec, args)
-
-        # test overwrite install
-        args = parser.parse_args(['install', '-f', '-u', str(pkghash)])
-        buildcache.buildcache(parser, args)
-
-        files = os.listdir(spec.prefix)
-        assert 'link_to_dummy.txt' in files
-        assert 'dummy.txt' in files
-        assert os.path.realpath(
-            os.path.join(spec.prefix, 'link_to_dummy.txt')
-        ) == os.path.realpath(os.path.join(spec.prefix, 'dummy.txt'))
+    assert 'link_to_dummy.txt' in files
+    assert 'dummy.txt' in files
 
     # Validate the relocation information
     buildinfo = bindist.read_buildinfo_file(spec.prefix)
     assert(buildinfo['relocate_textfiles'] == ['dummy.txt'])
     assert(buildinfo['relocate_links'] == ['link_to_dummy.txt'])
 
+    # create build cache with relative path
+    create_args.insert(create_args.index('-a'), '-f')
+    create_args.insert(create_args.index('-a'), '-r')
+    args = parser.parse_args(create_args)
+    buildcache.buildcache(parser, args)
+
+    # Uninstall the package
+    pkg.do_uninstall(force=True)
+
+    if not spack.util.gpg.Gpg.gpg():
+        install_args.insert(install_args.index('-a'), '-u')
+    args = parser.parse_args(install_args)
+    buildcache.buildcache(parser, args)
+
+    # test overwrite install
+    install_args.insert(install_args.index('-a'), '-f')
+    args = parser.parse_args(install_args)
+    buildcache.buildcache(parser, args)
+
+    files = os.listdir(spec.prefix)
+    assert 'link_to_dummy.txt' in files
+    assert 'dummy.txt' in files
+#    assert os.path.realpath(
+#        os.path.join(spec.prefix, 'link_to_dummy.txt')
+#    ) == os.path.realpath(os.path.join(spec.prefix, 'dummy.txt'))
+
+    args = parser.parse_args(['keys'])
+    buildcache.buildcache(parser, args)
+
     args = parser.parse_args(['list'])
     buildcache.buildcache(parser, args)
 
@@ -200,6 +181,9 @@ echo $PATH"""
     args = parser.parse_args(['keys', '-f'])
     buildcache.buildcache(parser, args)
 
+    args = parser.parse_args(['keys', '-i', '-t'])
+    buildcache.buildcache(parser, args)
+
     # unregister mirror with spack config
     mirrors = {}
     spack.config.set('mirrors', mirrors)
@@ -210,7 +194,10 @@ echo $PATH"""
     bindist._cached_specs = set()
 
 
+@pytest.mark.usefixtures('install_mockery')
 def test_relocate_text(tmpdir):
+    spec = Spec('trivial-install-test-package')
+    spec.concretize()
     with tmpdir.as_cwd():
         # Validate the text path replacement
         old_dir = '/home/spack/opt/spack'
@@ -220,24 +207,46 @@ def test_relocate_text(tmpdir):
             script.close()
         filenames = [filename]
         new_dir = '/opt/rh/devtoolset/'
-        relocate_text(filenames, oldpath=old_dir, newpath=new_dir,
-                      oldprefix=old_dir, newprefix=new_dir)
+        relocate_text(filenames, old_dir, new_dir,
+                      old_dir, new_dir,
+                      old_dir, new_dir,
+                      {old_dir: new_dir})
         with open(filename, "r")as script:
             for line in script:
                 assert(new_dir in line)
-        assert(strings_contains_installroot(filename, old_dir) is False)
+        assert(file_is_relocatable(os.path.realpath(filename)))
+    # Remove cached binary specs since we deleted the mirror
+    bindist._cached_specs = set()
 
 
 def test_relocate_links(tmpdir):
     with tmpdir.as_cwd():
-        old_dir = '/home/spack/opt/spack'
-        filename = 'link.ln'
-        old_src = os.path.join(old_dir, filename)
-        os.symlink(old_src, filename)
-        filenames = [filename]
-        new_dir = '/opt/rh/devtoolset'
-        relocate_links(filenames, old_dir, new_dir)
-        assert os.path.realpath(filename) == os.path.join(new_dir, filename)
+        old_layout_root = os.path.join(
+            '%s' % tmpdir, 'home', 'spack', 'opt', 'spack')
+        old_install_prefix = os.path.join(
+            '%s' % old_layout_root, 'debian6', 'test')
+        old_binname = os.path.join(old_install_prefix, 'binfile')
+        placeholder = set_placeholder(old_layout_root)
+        re.sub(old_layout_root, placeholder, old_binname)
+        filenames = ['link.ln', 'outsideprefix.ln']
+        new_layout_root = os.path.join(
+            '%s' % tmpdir, 'opt', 'rh', 'devtoolset')
+        new_install_prefix = os.path.join(
+            '%s' % new_layout_root, 'test', 'debian6')
+        new_linkname = os.path.join(new_install_prefix, 'link.ln')
+        new_linkname2 = os.path.join(new_install_prefix, 'outsideprefix.ln')
+        new_binname = os.path.join(new_install_prefix, 'binfile')
+        mkdirp(new_install_prefix)
+        with open(new_binname, 'w') as f:
+            f.write('\n')
+        os.utime(new_binname, None)
+        os.symlink(old_binname, new_linkname)
+        os.symlink('/usr/lib/libc.so', new_linkname2)
+        relocate_links(filenames, old_layout_root, new_layout_root,
+                       old_install_prefix, new_install_prefix,
+                       {old_install_prefix: new_install_prefix})
+        assert os.readlink(new_linkname) == new_binname
+        assert os.readlink(new_linkname2) == '/usr/lib/libc.so'
 
 
 def test_needs_relocation():
@@ -246,15 +255,222 @@ def test_needs_relocation():
     assert needs_binary_relocation('application', 'x-executable')
     assert not needs_binary_relocation('application', 'x-octet-stream')
     assert not needs_binary_relocation('text', 'x-')
-
     assert needs_text_relocation('text', 'x-')
     assert not needs_text_relocation('symbolic link to', 'x-')
 
     assert needs_binary_relocation('application', 'x-mach-binary')
 
 
-def test_macho_paths():
-
+def test_replace_paths(tmpdir):
+    with tmpdir.as_cwd():
+        suffix = 'dylib' if platform.system().lower() == 'darwin' else 'so'
+        hash_a = '53moz6jwnw3xpiztxwhc4us26klribws'
+        hash_b = 'tk62dzu62kd4oh3h3heelyw23hw2sfee'
+        hash_c = 'hdkhduizmaddpog6ewdradpobnbjwsjl'
+        hash_d = 'hukkosc7ahff7o65h6cdhvcoxm57d4bw'
+        hash_loco = 'zy4oigsc4eovn5yhr2lk4aukwzoespob'
+
+        prefix2hash = dict()
+
+        old_spack_dir = os.path.join('%s' % tmpdir,
+                                     'Users', 'developer', 'spack')
+        mkdirp(old_spack_dir)
+
+        oldprefix_a = os.path.join('%s' % old_spack_dir, 'pkgA-%s' % hash_a)
+        oldlibdir_a = os.path.join('%s' % oldprefix_a, 'lib')
+        mkdirp(oldlibdir_a)
+        prefix2hash[str(oldprefix_a)] = hash_a
+
+        oldprefix_b = os.path.join('%s' % old_spack_dir, 'pkgB-%s' % hash_b)
+        oldlibdir_b = os.path.join('%s' % oldprefix_b, 'lib')
+        mkdirp(oldlibdir_b)
+        prefix2hash[str(oldprefix_b)] = hash_b
+
+        oldprefix_c = os.path.join('%s' % old_spack_dir, 'pkgC-%s' % hash_c)
+        oldlibdir_c = os.path.join('%s' % oldprefix_c, 'lib')
+        oldlibdir_cc = os.path.join('%s' % oldlibdir_c, 'C')
+        mkdirp(oldlibdir_c)
+        prefix2hash[str(oldprefix_c)] = hash_c
+
+        oldprefix_d = os.path.join('%s' % old_spack_dir, 'pkgD-%s' % hash_d)
+        oldlibdir_d = os.path.join('%s' % oldprefix_d, 'lib')
+        mkdirp(oldlibdir_d)
+        prefix2hash[str(oldprefix_d)] = hash_d
+
+        oldprefix_local = os.path.join('%s' % tmpdir, 'usr', 'local')
+        oldlibdir_local = os.path.join('%s' % oldprefix_local, 'lib')
+        mkdirp(oldlibdir_local)
+        prefix2hash[str(oldprefix_local)] = hash_loco
+        libfile_a = 'libA.%s' % suffix
+        libfile_b = 'libB.%s' % suffix
+        libfile_c = 'libC.%s' % suffix
+        libfile_d = 'libD.%s' % suffix
+        libfile_loco = 'libloco.%s' % suffix
+        old_libnames  = [os.path.join(oldlibdir_a, libfile_a),
+                         os.path.join(oldlibdir_b, libfile_b),
+                         os.path.join(oldlibdir_c, libfile_c),
+                         os.path.join(oldlibdir_d, libfile_d),
+                         os.path.join(oldlibdir_local, libfile_loco)]
+
+        for old_libname in old_libnames:
+            with open(old_libname, 'a'):
+                os.utime(old_libname, None)
+
+        hash2prefix = dict()
+
+        new_spack_dir = os.path.join('%s' % tmpdir, 'Users', 'Shared',
+                                     'spack')
+        mkdirp(new_spack_dir)
+
+        prefix_a = os.path.join(new_spack_dir, 'pkgA-%s' % hash_a)
+        libdir_a = os.path.join(prefix_a, 'lib')
+        mkdirp(libdir_a)
+        hash2prefix[hash_a] = str(prefix_a)
+
+        prefix_b = os.path.join(new_spack_dir, 'pkgB-%s' % hash_b)
+        libdir_b = os.path.join(prefix_b, 'lib')
+        mkdirp(libdir_b)
+        hash2prefix[hash_b] = str(prefix_b)
+
+        prefix_c = os.path.join(new_spack_dir, 'pkgC-%s' % hash_c)
+        libdir_c = os.path.join(prefix_c, 'lib')
+        libdir_cc = os.path.join(libdir_c, 'C')
+        mkdirp(libdir_cc)
+        hash2prefix[hash_c] = str(prefix_c)
+
+        prefix_d = os.path.join(new_spack_dir, 'pkgD-%s' % hash_d)
+        libdir_d = os.path.join(prefix_d, 'lib')
+        mkdirp(libdir_d)
+        hash2prefix[hash_d] = str(prefix_d)
+
+        prefix_local = os.path.join('%s' % tmpdir, 'usr', 'local')
+        libdir_local = os.path.join(prefix_local, 'lib')
+        mkdirp(libdir_local)
+        hash2prefix[hash_loco] = str(prefix_local)
+
+        new_libnames  = [os.path.join(libdir_a, libfile_a),
+                         os.path.join(libdir_b, libfile_b),
+                         os.path.join(libdir_cc, libfile_c),
+                         os.path.join(libdir_d, libfile_d),
+                         os.path.join(libdir_local, libfile_loco)]
+
+        for new_libname in new_libnames:
+            with open(new_libname, 'a'):
+                os.utime(new_libname, None)
+
+        prefix2prefix = dict()
+        for prefix, hash in prefix2hash.items():
+            prefix2prefix[prefix] = hash2prefix[hash]
+
+        out_dict = macho_find_paths([oldlibdir_a, oldlibdir_b,
+                                     oldlibdir_c,
+                                     oldlibdir_cc, oldlibdir_local],
+                                    [os.path.join(oldlibdir_a,
+                                                  libfile_a),
+                                     os.path.join(oldlibdir_b,
+                                                  libfile_b),
+                                     os.path.join(oldlibdir_local,
+                                                  libfile_loco)],
+                                    os.path.join(oldlibdir_cc,
+                                                 libfile_c),
+                                    old_spack_dir,
+                                    prefix2prefix
+                                    )
+        assert out_dict == {oldlibdir_a: libdir_a,
+                            oldlibdir_b: libdir_b,
+                            oldlibdir_c: libdir_c,
+                            oldlibdir_cc: libdir_cc,
+                            libdir_local: libdir_local,
+                            os.path.join(oldlibdir_a, libfile_a):
+                            os.path.join(libdir_a, libfile_a),
+                            os.path.join(oldlibdir_b, libfile_b):
+                            os.path.join(libdir_b, libfile_b),
+                            os.path.join(oldlibdir_local, libfile_loco):
+                            os.path.join(libdir_local, libfile_loco),
+                            os.path.join(oldlibdir_cc, libfile_c):
+                            os.path.join(libdir_cc, libfile_c)}
+
+        out_dict = macho_find_paths([oldlibdir_a, oldlibdir_b,
+                                     oldlibdir_c,
+                                     oldlibdir_cc,
+                                     oldlibdir_local],
+                                    [os.path.join(oldlibdir_a,
+                                                  libfile_a),
+                                     os.path.join(oldlibdir_b,
+                                                  libfile_b),
+                                     os.path.join(oldlibdir_cc,
+                                                  libfile_c),
+                                     os.path.join(oldlibdir_local,
+                                                  libfile_loco)],
+                                    None,
+                                    old_spack_dir,
+                                    prefix2prefix
+                                    )
+        assert out_dict == {oldlibdir_a: libdir_a,
+                            oldlibdir_b: libdir_b,
+                            oldlibdir_c: libdir_c,
+                            oldlibdir_cc: libdir_cc,
+                            libdir_local: libdir_local,
+                            os.path.join(oldlibdir_a, libfile_a):
+                            os.path.join(libdir_a, libfile_a),
+                            os.path.join(oldlibdir_b, libfile_b):
+                            os.path.join(libdir_b, libfile_b),
+                            os.path.join(oldlibdir_local, libfile_loco):
+                            os.path.join(libdir_local, libfile_loco),
+                            os.path.join(oldlibdir_cc, libfile_c):
+                            os.path.join(libdir_cc, libfile_c)}
+
+        out_dict = macho_find_paths([oldlibdir_a, oldlibdir_b,
+                                     oldlibdir_c, oldlibdir_cc,
+                                     oldlibdir_local],
+                                    ['@rpath/%s' % libfile_a,
+                                     '@rpath/%s' % libfile_b,
+                                     '@rpath/%s' % libfile_c,
+                                     '@rpath/%s' % libfile_loco],
+                                    None,
+                                    old_spack_dir,
+                                    prefix2prefix
+                                    )
+
+        assert out_dict == {'@rpath/%s' % libfile_a:
+                            '@rpath/%s' % libfile_a,
+                            '@rpath/%s' % libfile_b:
+                            '@rpath/%s' % libfile_b,
+                            '@rpath/%s' % libfile_c:
+                            '@rpath/%s' % libfile_c,
+                            '@rpath/%s' % libfile_loco:
+                            '@rpath/%s' % libfile_loco,
+                            oldlibdir_a: libdir_a,
+                            oldlibdir_b: libdir_b,
+                            oldlibdir_c: libdir_c,
+                            oldlibdir_cc: libdir_cc,
+                            libdir_local: libdir_local,
+                            }
+
+        out_dict = macho_find_paths([oldlibdir_a,
+                                     oldlibdir_b,
+                                     oldlibdir_d,
+                                     oldlibdir_local],
+                                    ['@rpath/%s' % libfile_a,
+                                     '@rpath/%s' % libfile_b,
+                                     '@rpath/%s' % libfile_loco],
+                                    None,
+                                    old_spack_dir,
+                                    prefix2prefix)
+        assert out_dict == {'@rpath/%s' % libfile_a:
+                            '@rpath/%s' % libfile_a,
+                            '@rpath/%s' % libfile_b:
+                            '@rpath/%s' % libfile_b,
+                            '@rpath/%s' % libfile_loco:
+                            '@rpath/%s' % libfile_loco,
+                            oldlibdir_a: libdir_a,
+                            oldlibdir_b: libdir_b,
+                            oldlibdir_d: libdir_d,
+                            libdir_local: libdir_local,
+                            }
+
+
+def test_macho_make_paths():
     out = macho_make_paths_relative('/Users/Shares/spack/pkgC/lib/libC.dylib',
                                     '/Users/Shared/spack',
                                     ('/Users/Shared/spack/pkgA/lib',
@@ -264,13 +480,19 @@ def test_macho_paths():
                                      '/Users/Shared/spack/pkgB/libB.dylib',
                                      '/usr/local/lib/libloco.dylib'),
                                     '/Users/Shared/spack/pkgC/lib/libC.dylib')
-    assert out == (['@loader_path/../../../../Shared/spack/pkgA/lib',
-                    '@loader_path/../../../../Shared/spack/pkgB/lib',
-                    '/usr/local/lib'],
-                   ['@loader_path/../../../../Shared/spack/pkgA/libA.dylib',
-                    '@loader_path/../../../../Shared/spack/pkgB/libB.dylib',
-                    '/usr/local/lib/libloco.dylib'],
-                   '@rpath/libC.dylib')
+    assert out == {'/Users/Shared/spack/pkgA/lib':
+                   '@loader_path/../../../../Shared/spack/pkgA/lib',
+                   '/Users/Shared/spack/pkgB/lib':
+                   '@loader_path/../../../../Shared/spack/pkgB/lib',
+                   '/usr/local/lib': '/usr/local/lib',
+                   '/Users/Shared/spack/pkgA/libA.dylib':
+                   '@loader_path/../../../../Shared/spack/pkgA/libA.dylib',
+                   '/Users/Shared/spack/pkgB/libB.dylib':
+                   '@loader_path/../../../../Shared/spack/pkgB/libB.dylib',
+                   '/usr/local/lib/libloco.dylib':
+                   '/usr/local/lib/libloco.dylib',
+                   '/Users/Shared/spack/pkgC/lib/libC.dylib':
+                   '@rpath/libC.dylib'}
 
     out = macho_make_paths_relative('/Users/Shared/spack/pkgC/bin/exeC',
                                     '/Users/Shared/spack',
@@ -281,98 +503,21 @@ def test_macho_paths():
                                      '/Users/Shared/spack/pkgB/libB.dylib',
                                      '/usr/local/lib/libloco.dylib'), None)
 
-    assert out == (['@loader_path/../../pkgA/lib',
-                    '@loader_path/../../pkgB/lib',
-                    '/usr/local/lib'],
-                   ['@loader_path/../../pkgA/libA.dylib',
-                    '@loader_path/../../pkgB/libB.dylib',
-                    '/usr/local/lib/libloco.dylib'], None)
-
-    out = macho_replace_paths('/Users/Shared/spack',
-                              '/Applications/spack',
-                              ('/Users/Shared/spack/pkgA/lib',
-                               '/Users/Shared/spack/pkgB/lib',
-                               '/usr/local/lib'),
-                              ('/Users/Shared/spack/pkgA/libA.dylib',
-                               '/Users/Shared/spack/pkgB/libB.dylib',
-                               '/usr/local/lib/libloco.dylib'),
-                              '/Users/Shared/spack/pkgC/lib/libC.dylib')
-    assert out == (['/Applications/spack/pkgA/lib',
-                    '/Applications/spack/pkgB/lib',
-                    '/usr/local/lib'],
-                   ['/Applications/spack/pkgA/libA.dylib',
-                    '/Applications/spack/pkgB/libB.dylib',
-                    '/usr/local/lib/libloco.dylib'],
-                   '/Applications/spack/pkgC/lib/libC.dylib')
-
-    out = macho_replace_paths('/Users/Shared/spack',
-                              '/Applications/spack',
-                              ('/Users/Shared/spack/pkgA/lib',
-                               '/Users/Shared/spack/pkgB/lib',
-                               '/usr/local/lib'),
-                              ('/Users/Shared/spack/pkgA/libA.dylib',
-                               '/Users/Shared/spack/pkgB/libB.dylib',
-                               '/usr/local/lib/libloco.dylib'),
-                              None)
-    assert out == (['/Applications/spack/pkgA/lib',
-                    '/Applications/spack/pkgB/lib',
-                    '/usr/local/lib'],
-                   ['/Applications/spack/pkgA/libA.dylib',
-                    '/Applications/spack/pkgB/libB.dylib',
-                    '/usr/local/lib/libloco.dylib'],
-                   None)
+    assert out == {'/Users/Shared/spack/pkgA/lib':
+                   '@loader_path/../../pkgA/lib',
+                   '/Users/Shared/spack/pkgB/lib':
+                   '@loader_path/../../pkgB/lib',
+                   '/usr/local/lib': '/usr/local/lib',
+                   '/Users/Shared/spack/pkgA/libA.dylib':
+                   '@loader_path/../../pkgA/libA.dylib',
+                   '/Users/Shared/spack/pkgB/libB.dylib':
+                   '@loader_path/../../pkgB/libB.dylib',
+                   '/usr/local/lib/libloco.dylib':
+                   '/usr/local/lib/libloco.dylib'}
 
 
 def test_elf_paths():
-    out = get_relative_rpaths(
+    out = get_relative_elf_rpaths(
         '/usr/bin/test', '/usr',
         ('/usr/lib', '/usr/lib64', '/opt/local/lib'))
     assert out == ['$ORIGIN/../lib', '$ORIGIN/../lib64', '/opt/local/lib']
-
-    out = substitute_rpath(
-        ('/usr/lib', '/usr/lib64', '/opt/local/lib'), '/usr', '/opt')
-    assert out == ['/opt/lib', '/opt/lib64', '/opt/local/lib']
-
-
-@pytest.mark.skipif(sys.platform != 'darwin',
-                    reason="only works with Mach-o objects")
-def test_relocate_macho(tmpdir):
-    with tmpdir.as_cwd():
-
-        get_patchelf()  # this does nothing on Darwin
-
-        rpaths, deps, idpath = macho_get_paths('/bin/bash')
-        nrpaths, ndeps, nid = macho_make_paths_relative('/bin/bash', '/usr',
-                                                        rpaths, deps, idpath)
-        shutil.copyfile('/bin/bash', 'bash')
-        modify_macho_object('bash',
-                            rpaths, deps, idpath,
-                            nrpaths, ndeps, nid)
-
-        rpaths, deps, idpath = macho_get_paths('/bin/bash')
-        nrpaths, ndeps, nid = macho_replace_paths('/usr', '/opt',
-                                                  rpaths, deps, idpath)
-        shutil.copyfile('/bin/bash', 'bash')
-        modify_macho_object('bash',
-                            rpaths, deps, idpath,
-                            nrpaths, ndeps, nid)
-
-        path = '/usr/lib/libncurses.5.4.dylib'
-        rpaths, deps, idpath = macho_get_paths(path)
-        nrpaths, ndeps, nid = macho_make_paths_relative(path, '/usr',
-                                                        rpaths, deps, idpath)
-        shutil.copyfile(
-            '/usr/lib/libncurses.5.4.dylib', 'libncurses.5.4.dylib')
-        modify_macho_object('libncurses.5.4.dylib',
-                            rpaths, deps, idpath,
-                            nrpaths, ndeps, nid)
-
-        rpaths, deps, idpath = macho_get_paths(path)
-        nrpaths, ndeps, nid = macho_replace_paths('/usr', '/opt',
-                                                  rpaths, deps, idpath)
-        shutil.copyfile(
-            '/usr/lib/libncurses.5.4.dylib', 'libncurses.5.4.dylib')
-        modify_macho_object(
-            'libncurses.5.4.dylib',
-            rpaths, deps, idpath,
-            nrpaths, ndeps, nid)