Added unit tests for spec normalization.

3 files changed, 135 insertions, 25 deletions

diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index cd87adb990..3658277634 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -380,7 +380,8 @@ class Package(object):
         visited.add(self.name)
 
         yield self
-        for name, spec in self.dependencies.iteritems():
+        for name in sorted(self.dependencies.keys()):
+            spec = self.dependencies[name]
             for pkg in packages.get(name).preorder_traversal(visited):
                 yield pkg
 
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 2731c344ab..f7f4299942 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -78,6 +78,7 @@ from spack.color import *
 from spack.util.lang import *
 from spack.util.string import *
 
+
 """This map determines the coloring of specs when using color output.
    We make the fields different colors to enhance readability.
    See spack.color for descriptions of the color codes.
@@ -226,7 +227,7 @@ class DependencyMap(HashableMap):
 
 @key_ordering
 class Spec(object):
-    def __init__(self, spec_like):
+    def __init__(self, spec_like, *dep_like):
         # Copy if spec_like is a Spec.
         if type(spec_like) == Spec:
             self._dup(spec_like)
@@ -254,6 +255,16 @@ class Spec(object):
         self.compiler = other.compiler
         self.dependencies = other.dependencies
 
+        # This allows users to construct a spec DAG with literals.
+        # Note that given two specs a and b, Spec(a) copies a, but
+        # Spec(a, b) will copy a but just add b as a dep.
+        for dep in dep_like:
+            if type(dep) == str:
+                dep_spec = Spec(dep)
+                self.dependencies[dep_spec.name] = dep_spec
+            elif type(dep) == Spec:
+                self.dependencies[dep.name] = dep
+
 
     #
     # Private routines here are called by the parser when building a spec.
@@ -315,17 +326,27 @@ class Spec(object):
                     and self.dependencies.concrete)
 
 
-    def preorder_traversal(self, visited=None):
+    def preorder_traversal(self, visited=None, d=0, **kwargs):
+        unique = kwargs.setdefault('unique', True)
+        depth  = kwargs.setdefault('depth', False)
+        keyfun = kwargs.setdefault('key', id)
+        noroot = kwargs.setdefault('noroot', False)
+
         if visited is None:
             visited = set()
 
-        if id(self) in visited:
+        if keyfun(self) in visited:
+            if not unique:
+                yield (d, self) if depth else self
             return
-        visited.add(id(self))
+        visited.add(keyfun(self))
 
-        yield self
-        for dep in self.dependencies.itervalues():
-            for spec in dep.preorder_traversal(visited):
+        if d > 0 or not noroot:
+            yield (d, self) if depth else self
+
+        for key in sorted(self.dependencies.keys()):
+            for spec in self.dependencies[key].preorder_traversal(
+                    visited, d+1, **kwargs):
                 yield spec
 
 
@@ -368,10 +389,14 @@ class Spec(object):
         # Ensure dependencies have right versions
 
 
-    def flatten(self):
-        """Pull all dependencies up to the root (this spec).
-           Merge constraints for dependencies with the same name, and if they
-           conflict, throw an exception. """
+    def flat_dependencies(self):
+        """Return a DependencyMap containing all dependencies with their
+           constraints merged.  If there are any conflicts, throw an exception.
+
+           This will work even on specs that are not normalized; i.e. specs
+           that have two instances of the same dependency in the DAG.
+           This is used as the first step of normalization.
+        """
         # This ensures that the package descriptions themselves are consistent
         self.package.validate_dependencies()
 
@@ -393,7 +418,14 @@ class Spec(object):
             # so this means OUR code is not sane!
             raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message)
 
-        self.dependencies = flat_deps
+        return flat_deps
+
+
+    def flatten(self):
+        """Pull all dependencies up to the root (this spec).
+           Merge constraints for dependencies with the same name, and if they
+           conflict, throw an exception. """
+        self.dependencies = self.flat_dependencies()
 
 
     def _normalize_helper(self, visited, spec_deps):
@@ -432,11 +464,8 @@ class Spec(object):
 
         # Then ensure that the packages mentioned are sane, that the
         # provided spec is sane, and that all dependency specs are in the
-        # root node of the spec.  Flatten will do this for us.
-        self.flatten()
-
-        # Now that we're flat we can get all our dependencies at once.
-        spec_deps = self.dependencies
+        # root node of the spec.  flat_dependencies will do this for us.
+        spec_deps = self.flat_dependencies()
         self.dependencies = DependencyMap()
 
         visited = set()
@@ -535,7 +564,7 @@ class Spec(object):
         return colorize_spec(self)
 
 
-    def str_without_deps(self):
+    def str_no_deps(self):
         out = self.name
 
         # If the version range is entirely open, omit it
@@ -553,12 +582,19 @@ class Spec(object):
         return out
 
 
-    def tree(self, indent=""):
+    def tree(self):
         """Prints out this spec and its dependencies, tree-formatted
-           with indentation.  Each node also has an id."""
-        out = indent + self.str_without_deps()
-        for dep in sorted(self.dependencies.keys()):
-            out += "\n" + self.dependencies[dep].tree(indent + "    ")
+           with indentation."""
+        out = ""
+        cur_id = 0
+        ids = {}
+        for d, node in self.preorder_traversal(unique=False, depth=True):
+            if not id(node) in ids:
+                cur_id += 1
+                ids[id(node)] = cur_id
+            out += str(ids[id(node)])
+            out += " "+ ("    " * d)
+            out += node.str_no_deps() + "\n"
         return out
 
 
@@ -567,7 +603,11 @@ class Spec(object):
 
 
     def __str__(self):
-        return self.str_without_deps() + str(self.dependencies)
+        byname = lambda d: d.name
+        deps = self.preorder_traversal(key=byname, noroot=True)
+        sorted_deps = sorted(deps, key=byname)
+        dep_string = ''.join("^" + dep.str_no_deps() for dep in sorted_deps)
+        return self.str_no_deps() + dep_string
 
 
 #
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index a9dd0ec41c..bdb64fee80 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -115,3 +115,72 @@ class ValidationTest(unittest.TestCase):
         set_pkg_dep('mpileaks', 'mpich=bgqos_0')
         spec = Spec('mpileaks ^mpich=sles_10_ppc64 ^callpath ^dyninst ^libelf ^libdwarf')
         self.assertRaises(spack.spec.UnsatisfiableArchitectureSpecError, spec.normalize)
+
+
+    def test_invalid_dep(self):
+        spec = Spec('libelf ^mpich')
+        self.assertRaises(spack.spec.InvalidDependencyException, spec.normalize)
+
+        spec = Spec('libelf ^libdwarf')
+        self.assertRaises(spack.spec.InvalidDependencyException, spec.normalize)
+
+        spec = Spec('mpich ^dyninst ^libelf')
+        self.assertRaises(spack.spec.InvalidDependencyException, spec.normalize)
+
+
+    def test_equal(self):
+        spec = Spec('mpileaks ^callpath ^libelf ^libdwarf')
+        self.assertNotEqual(spec, Spec(
+            'mpileaks', Spec('callpath',
+                             Spec('libdwarf',
+                                  Spec('libelf')))))
+        self.assertNotEqual(spec, Spec(
+            'mpileaks', Spec('callpath',
+                             Spec('libelf',
+                                  Spec('libdwarf')))))
+
+        self.assertEqual(spec, Spec(
+            'mpileaks', Spec('callpath'), Spec('libdwarf'), Spec('libelf')))
+
+        self.assertEqual(spec, Spec(
+            'mpileaks', Spec('libelf'), Spec('libdwarf'), Spec('callpath')))
+
+
+    def test_normalize_mpileaks(self):
+        spec = Spec('mpileaks ^mpich ^callpath ^dyninst ^libelf@1.8.11 ^libdwarf')
+
+        expected_flat = Spec(
+            'mpileaks', Spec('mpich'), Spec('callpath'), Spec('dyninst'),
+            Spec('libelf@1.8.11'), Spec('libdwarf'))
+
+        mpich = Spec('mpich')
+        libelf = Spec('libelf@1.8.11')
+        expected_normalized = Spec(
+            'mpileaks',
+            Spec('callpath',
+                 Spec('dyninst', Spec('libdwarf', libelf),
+                      libelf),
+                 mpich), mpich)
+
+        expected_non_dag = Spec(
+            'mpileaks',
+            Spec('callpath',
+                 Spec('dyninst', Spec('libdwarf', Spec('libelf@1.8.11')),
+                      Spec('libelf@1.8.11')),
+                 mpich), Spec('mpich'))
+
+        self.assertEqual(expected_normalized, expected_non_dag)
+
+        self.assertEqual(str(expected_normalized), str(expected_non_dag))
+        self.assertEqual(str(spec), str(expected_non_dag))
+        self.assertEqual(str(expected_normalized), str(spec))
+
+        self.assertEqual(spec, expected_flat)
+        self.assertNotEqual(spec, expected_normalized)
+        self.assertNotEqual(spec, expected_non_dag)
+
+        spec.normalize()
+
+        self.assertNotEqual(spec, expected_flat)
+        self.assertEqual(spec, expected_normalized)
+        self.assertEqual(spec, expected_non_dag)