Fixed dumb link_tree bug, added test for link tree.

4 files changed, 274 insertions, 87 deletions

diff --git a/lib/spack/llnl/util/filesystem.py b/lib/spack/llnl/util/filesystem.py
index 0578415653..576aeb16bd 100644
--- a/lib/spack/llnl/util/filesystem.py
+++ b/lib/spack/llnl/util/filesystem.py
@@ -23,7 +23,7 @@
 # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
 __all__ = ['set_install_permissions', 'install', 'expand_user', 'working_dir',
-           'touch', 'mkdirp', 'force_remove', 'join_path', 'ancestor',
+           'touch', 'touchp', 'mkdirp', 'force_remove', 'join_path', 'ancestor',
            'can_access', 'filter_file', 'change_sed_delimiter', 'is_exe']
 
 import os
@@ -204,6 +204,12 @@ def touch(path):
         os.utime(path, None)
 
 
+def touchp(path):
+    """Like touch, but creates any parent directories needed for the file."""
+    mkdirp(os.path.dirname(path))
+    touch(path)
+
+
 def join_path(prefix, *args):
     path = str(prefix)
     for elt in args:
diff --git a/lib/spack/llnl/util/link_tree.py b/lib/spack/llnl/util/link_tree.py
index 2d7126be2c..887f6f4d26 100644
--- a/lib/spack/llnl/util/link_tree.py
+++ b/lib/spack/llnl/util/link_tree.py
@@ -29,108 +29,116 @@ import os
 import shutil
 from llnl.util.filesystem import mkdirp
 
+empty_file_name = '.spack-empty'
 
-class LinkTree(object):
-    """Class to create trees of symbolic links from a source directory.
 
-    LinkTree objects are constructed with a source root.  Their
-    methods allow you to create and delete trees of symbolic links
-    back to the source tree in specific destination directories.
-    Trees comprise symlinks only to files; directries are never
-    symlinked to, to prevent the source directory from ever being
-    modified.
+def traverse_tree(source_root, dest_root, rel_path='', **kwargs):
+    """Traverse two filesystem trees simultaneously.
+
+    Walks the LinkTree directory in pre or post order.  Yields each
+    file in the source directory with a matching path from the dest
+    directory, along with whether the file is a directory.
+    e.g., for this tree::
+
+        root/
+          a/
+            file1
+            file2
+          b/
+            file3
+
+    When called on dest, this yields::
+
+        ('root',         'dest')
+        ('root/a',       'dest/a')
+        ('root/a/file1', 'dest/a/file1')
+        ('root/a/file2', 'dest/a/file2')
+        ('root/b',       'dest/b')
+        ('root/b/file3', 'dest/b/file3')
+
+    Optional args:
+
+    order=[pre|post] -- Whether to do pre- or post-order traveral.
+
+    ignore=<predicate> -- Predicate indicating which files to ignore.
+
+    follow_nonexisting -- Whether to descend into directories in
+                          src that do not exit in dest. Default True.
+
+    follow_links -- Whether to descend into symlinks in src.
 
     """
-    def __init__(self, source_root):
-        self._root = source_root
+    follow_nonexisting = kwargs.get('follow_nonexisting', True)
+    follow_links = kwargs.get('follow_link', False)
 
+    # Yield in pre or post order?
+    order  = kwargs.get('order', 'pre')
+    if order not in ('pre', 'post'):
+        raise ValueError("Order must be 'pre' or 'post'.")
 
-    def traverse(self, dest_root, **kwargs):
-        """Traverse LinkTree root and dest simultaneously.
+    # List of relative paths to ignore under the src root.
+    ignore = kwargs.get('ignore', lambda filename: False)
 
-        Walks the LinkTree directory in pre or post order.  Yields
-        each file in the source directory with a matching path from
-        the dest directory.  e.g., for this tree::
+    # Don't descend into ignored directories
+    if ignore(rel_path):
+        return
 
-            root/
-              a/
-                file1
-                file2
-              b/
-                file3
+    source_path = os.path.join(source_root, rel_path)
+    dest_path   = os.path.join(dest_root, rel_path)
 
-        When called on dest, this yields::
+    # preorder yields directories before children
+    if order == 'pre':
+        yield (source_path, dest_path)
 
-            ('root',         'dest')
-            ('root/a',       'dest/a')
-            ('root/a/file1', 'dest/a/file1')
-            ('root/a/file2', 'dest/a/file2')
-            ('root/b',       'dest/b')
-            ('root/b/file3', 'dest/b/file3')
+    for f in os.listdir(source_path):
+        source_child = os.path.join(source_path, f)
+        dest_child   = os.path.join(dest_path, f)
 
-        Optional args:
+        # Treat as a directory
+        if os.path.isdir(source_child) and (
+            follow_links or not os.path.islink(source_child)):
 
-        order=[pre|post] -- Whether to do pre- or post-order traveral.
+            # When follow_nonexisting isn't set, don't descend into dirs
+            # in source that do not exist in dest
+            if follow_nonexisting or os.path.exists(dest_child):
+                tuples = traverse_tree(source_child, dest_child, rel_path, **kwargs)
+                for t in tuples: yield t
 
-        ignore=<predicate> -- Predicate indicating which files to ignore.
+        # Treat as a file.
+        elif not ignore(os.path.join(rel_path, f)):
+            yield (source_child, dest_child)
+
+    if order == 'post':
+        yield (source_path, dest_path)
 
-        follow_nonexisting -- Whether to descend into directories in
-                              src that do not exit in dest.
 
-        """
-        # Yield directories before or after their contents.
-        order  = kwargs.get('order', 'pre')
-        if order not in ('pre', 'post'):
-            raise ValueError("Order must be 'pre' or 'post'.")
-
-        # List of relative paths to ignore under the src root.
-        ignore = kwargs.get('ignore', lambda filename: False)
-
-        # Whether to descend when dirs dont' exist in dest.
-        follow_nonexisting = kwargs.get('follow_nonexisting', True)
-
-        for dirpath, dirnames, filenames in os.walk(self._root):
-            rel_path  = dirpath[len(self._root):]
-            rel_path = rel_path.lstrip(os.path.sep)
-            dest_dirpath = os.path.join(dest_root, rel_path)
-
-            # Don't descend into ignored directories
-            if ignore(dest_dirpath):
-                return
-
-            # Don't descend into dirs in dest that do not exist in src.
-            if not follow_nonexisting:
-                dirnames[:] = [
-                    d for d in dirnames
-                    if os.path.exists(os.path.join(dest_dirpath, d))]
-
-            # preorder yields directories before children
-            if order == 'pre':
-                yield (dirpath, dest_dirpath)
-
-            for name in filenames:
-                src_file  = os.path.join(dirpath, name)
-                dest_file = os.path.join(dest_dirpath, name)
-
-                # Ignore particular paths inside the install root.
-                src_relpath = src_file[len(self._root):]
-                src_relpath = src_relpath.lstrip(os.path.sep)
-                if ignore(src_relpath):
-                    continue
 
-                yield (src_file, dest_file)
+class LinkTree(object):
+    """Class to create trees of symbolic links from a source directory.
 
-            # postorder yields directories after children
-            if order == 'post':
-                yield (dirpath, dest_dirpath)
+    LinkTree objects are constructed with a source root.  Their
+    methods allow you to create and delete trees of symbolic links
+    back to the source tree in specific destination directories.
+    Trees comprise symlinks only to files; directries are never
+    symlinked to, to prevent the source directory from ever being
+    modified.
+
+    """
+    def __init__(self, source_root):
+        if not os.path.exists(source_root):
+            raise IOError("No such file or directory: '%s'", source_root)
 
+        self._root = source_root
 
 
     def find_conflict(self, dest_root, **kwargs):
-        """Returns the first file in dest that also exists in src."""
+        """Returns the first file in dest that conflicts with src"""
         kwargs['follow_nonexisting'] = False
-        for src, dest in self.traverse(dest_root, **kwargs):
-            if os.path.exists(dest) and not os.path.isdir(dest):
+        for src, dest in traverse_tree(self._root, dest_root, **kwargs):
+            if os.path.isdir(src):
+                if os.path.exists(dest) and not os.path.isdir(dest):
+                    return dest
+            elif os.path.exists(dest):
                 return dest
         return None
 
@@ -138,9 +146,20 @@ class LinkTree(object):
     def merge(self, dest_root, **kwargs):
         """Link all files in src into dest, creating directories if necessary."""
         kwargs['order'] = 'pre'
-        for src, dest in self.traverse(dest_root, **kwargs):
+        for src, dest in traverse_tree(self._root, dest_root, **kwargs):
             if os.path.isdir(src):
-                mkdirp(dest)
+                if not os.path.exists(dest):
+                    mkdirp(dest)
+                    continue
+
+                if not os.path.isdir(dest):
+                    raise ValueError("File blocks directory: %s" % dest)
+
+                # mark empty directories so they aren't removed on unmerge.
+                if not os.listdir(dest):
+                    marker = os.path.join(dest, empty_file_name)
+                    touch(marker)
+
             else:
                 assert(not os.path.exists(dest))
                 os.symlink(src, dest)
@@ -153,12 +172,20 @@ class LinkTree(object):
 
         """
         kwargs['order'] = 'post'
-        for src, dest in self.traverse(dest_root, **kwargs):
-            if os.path.isdir(dest):
+        for src, dest in traverse_tree(self._root, dest_root, **kwargs):
+            if os.path.isdir(src):
+                if not os.path.isdir(dest):
+                    raise ValueError("File blocks directory: %s" % dest)
+
+                # remove directory if it is empty.
                 if not os.listdir(dest):
-                    # TODO: what if empty directories were present pre-merge?
                     shutil.rmtree(dest, ignore_errors=True)
 
+                # remove empty dir marker if present.
+                marker = os.path.join(dest, empty_file_name)
+                if os.path.exists(marker):
+                    os.remove(marker)
+
             elif os.path.exists(dest):
                 if not os.path.islink(dest):
                     raise ValueError("%s is not a link tree!" % dest)
diff --git a/lib/spack/spack/test/__init__.py b/lib/spack/spack/test/__init__.py
index 0eda667abc..c53e6774fc 100644
--- a/lib/spack/spack/test/__init__.py
+++ b/lib/spack/spack/test/__init__.py
@@ -51,7 +51,8 @@ test_names = ['versions',
               'hg_fetch',
               'mirror',
               'url_extrapolate',
-              'cc']
+              'cc',
+              'link_tree']
 
 
 def list_tests():
diff --git a/lib/spack/spack/test/link_tree.py b/lib/spack/spack/test/link_tree.py
new file mode 100644
index 0000000000..bc7c2c6b5e
--- /dev/null
+++ b/lib/spack/spack/test/link_tree.py
@@ -0,0 +1,153 @@
+##############################################################################
+# Copyright (c) 2013, Lawrence Livermore National Security, LLC.
+# Produced at the Lawrence Livermore National Laboratory.
+#
+# This file is part of Spack.
+# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
+# LLNL-CODE-647188
+#
+# For details, see https://scalability-llnl.github.io/spack
+# Please also see the LICENSE file for our notice and the LGPL.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License (as published by
+# the Free Software Foundation) version 2.1 dated February 1999.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
+# conditions of the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+##############################################################################
+import os
+import unittest
+import shutil
+import tempfile
+from contextlib import closing
+
+from llnl.util.filesystem import *
+from llnl.util.link_tree import LinkTree
+
+from spack.stage import Stage
+
+
+class LinkTreeTest(unittest.TestCase):
+    """Tests Spack's LinkTree class."""
+
+    def setUp(self):
+        self.stage = Stage('link-tree-test')
+
+        with working_dir(self.stage.path):
+            touchp('source/1')
+            touchp('source/a/b/2')
+            touchp('source/a/b/3')
+            touchp('source/c/4')
+            touchp('source/c/d/5')
+            touchp('source/c/d/6')
+            touchp('source/c/d/e/7')
+
+        source_path = os.path.join(self.stage.path, 'source')
+        self.link_tree = LinkTree(source_path)
+
+
+    def tearDown(self):
+        if self.stage:
+            self.stage.destroy()
+
+
+    def check_file_link(self, filename):
+        self.assertTrue(os.path.isfile(filename))
+        self.assertTrue(os.path.islink(filename))
+
+
+    def check_dir(self, filename):
+        self.assertTrue(os.path.isdir(filename))
+
+
+    def test_merge_to_new_directory(self):
+        with working_dir(self.stage.path):
+            self.link_tree.merge('dest')
+
+            self.check_file_link('dest/1')
+            self.check_file_link('dest/a/b/2')
+            self.check_file_link('dest/a/b/3')
+            self.check_file_link('dest/c/4')
+            self.check_file_link('dest/c/d/5')
+            self.check_file_link('dest/c/d/6')
+            self.check_file_link('dest/c/d/e/7')
+
+            self.link_tree.unmerge('dest')
+
+            self.assertFalse(os.path.exists('dest'))
+
+
+    def test_merge_to_existing_directory(self):
+        with working_dir(self.stage.path):
+
+            touchp('dest/x')
+            touchp('dest/a/b/y')
+
+            self.link_tree.merge('dest')
+
+            self.check_file_link('dest/1')
+            self.check_file_link('dest/a/b/2')
+            self.check_file_link('dest/a/b/3')
+            self.check_file_link('dest/c/4')
+            self.check_file_link('dest/c/d/5')
+            self.check_file_link('dest/c/d/6')
+            self.check_file_link('dest/c/d/e/7')
+
+            self.assertTrue(os.path.isfile('dest/x'))
+            self.assertTrue(os.path.isfile('dest/a/b/y'))
+
+            self.link_tree.unmerge('dest')
+
+            self.assertTrue(os.path.isfile('dest/x'))
+            self.assertTrue(os.path.isfile('dest/a/b/y'))
+
+            self.assertFalse(os.path.isfile('dest/1'))
+            self.assertFalse(os.path.isfile('dest/a/b/2'))
+            self.assertFalse(os.path.isfile('dest/a/b/3'))
+            self.assertFalse(os.path.isfile('dest/c/4'))
+            self.assertFalse(os.path.isfile('dest/c/d/5'))
+            self.assertFalse(os.path.isfile('dest/c/d/6'))
+            self.assertFalse(os.path.isfile('dest/c/d/e/7'))
+
+
+    def test_merge_with_empty_directories(self):
+        with working_dir(self.stage.path):
+            mkdirp('dest/f/g')
+            mkdirp('dest/a/b/h')
+
+            self.link_tree.merge('dest')
+            self.link_tree.unmerge('dest')
+
+            self.assertFalse(os.path.exists('dest/1'))
+            self.assertFalse(os.path.exists('dest/a/b/2'))
+            self.assertFalse(os.path.exists('dest/a/b/3'))
+            self.assertFalse(os.path.exists('dest/c/4'))
+            self.assertFalse(os.path.exists('dest/c/d/5'))
+            self.assertFalse(os.path.exists('dest/c/d/6'))
+            self.assertFalse(os.path.exists('dest/c/d/e/7'))
+
+            self.assertTrue(os.path.isdir('dest/a/b/h'))
+            self.assertTrue(os.path.isdir('dest/f/g'))
+
+
+    def test_ignore(self):
+        with working_dir(self.stage.path):
+            touchp('source/.spec')
+            touchp('dest/.spec')
+
+            self.link_tree.merge('dest', ignore=lambda x: x == '.spec')
+            self.link_tree.unmerge('dest', ignore=lambda x: x == '.spec')
+
+            self.assertFalse(os.path.exists('dest/1'))
+            self.assertFalse(os.path.exists('dest/a'))
+            self.assertFalse(os.path.exists('dest/c'))
+
+            self.assertTrue(os.path.isfile('source/.spec'))
+            self.assertTrue(os.path.isfile('dest/.spec'))