Merge branch 'features/dep-graph' into develop

9 files changed, 646 insertions, 54 deletions

diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py
index 049d158c6d..db15da0506 100644
--- a/lib/spack/llnl/util/lang.py
+++ b/lib/spack/llnl/util/lang.py
@@ -269,6 +269,28 @@ def in_function(function_name):
         del stack
 
 
+def check_kwargs(kwargs, fun):
+    """Helper for making functions with kwargs.  Checks whether the kwargs
+       are empty after all of them have been popped off.  If they're
+       not, raises an error describing which kwargs are invalid.
+
+       Example::
+
+          def foo(self, **kwargs):
+              x = kwargs.pop('x', None)
+              y = kwargs.pop('y', None)
+              z = kwargs.pop('z', None)
+              check_kwargs(kwargs, self.foo)
+
+          # This raises a TypeError:
+          foo(w='bad kwarg')
+    """
+    if kwargs:
+        raise TypeError(
+            "'%s' is an invalid keyword argument for function %s()."
+            % (next(kwargs.iterkeys()), fun.__name__))
+
+
 class RequiredAttributeError(ValueError):
     def __init__(self, message):
         super(RequiredAttributeError, self).__init__(message)
diff --git a/lib/spack/llnl/util/tty/color.py b/lib/spack/llnl/util/tty/color.py
index 598e9d44f5..81688d7f14 100644
--- a/lib/spack/llnl/util/tty/color.py
+++ b/lib/spack/llnl/util/tty/color.py
@@ -177,17 +177,20 @@ def cescape(string):
 
 class ColorStream(object):
     def __init__(self, stream, color=None):
-        self.__class__ = type(stream.__class__.__name__,
-                              (self.__class__, stream.__class__), {})
-        self.__dict__ = stream.__dict__
-        self.color = color
-        self.stream = stream
+        self._stream = stream
+        self._color = color
 
     def write(self, string, **kwargs):
-        if kwargs.get('raw', False):
-            super(ColorStream, self).write(string)
-        else:
-            cwrite(string, self.stream, self.color)
+        raw = kwargs.get('raw', False)
+        raw_write = getattr(self._stream, 'write')
+
+        color = self._color
+        if self._color is None:
+            if raw:
+                color=True
+            else:
+                color = self._stream.isatty()
+        raw_write(colorize(string, color=color))
 
     def writelines(self, sequence, **kwargs):
         raw = kwargs.get('raw', False)
diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py
index 39dbfbb150..cb93a1b543 100644
--- a/lib/spack/spack/cmd/graph.py
+++ b/lib/spack/spack/cmd/graph.py
@@ -22,9 +22,45 @@
 # along with this program; if not, write to the Free Software Foundation,
 # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
+from external import argparse
+
 import spack
+import spack.cmd
+from spack.graph import *
+
+description = "Generate graphs of package dependency relationships."
+
+def setup_parser(subparser):
+    setup_parser.parser = subparser
+
+    method = subparser.add_mutually_exclusive_group()
+    method.add_argument(
+        '--ascii', action='store_true',
+        help="Draw graph as ascii to stdout (default).")
+    method.add_argument(
+        '--dot', action='store_true',
+        help="Generate graph in dot format and print to stdout.")
+
+    subparser.add_argument(
+        '--concretize', action='store_true', help="Concretize specs before graphing.")
+
+    subparser.add_argument(
+        'specs', nargs=argparse.REMAINDER, help="specs of packages to graph.")
 
-description = "Write out inter-package dependencies in dot graph format"
 
 def graph(parser, args):
-    spack.db.graph_dependencies()
+    specs = spack.cmd.parse_specs(
+        args.specs, normalize=True, concretize=args.concretize)
+
+    if not specs:
+        setup_parser.parser.print_help()
+        return 1
+
+    if args.dot:    # Dot graph only if asked for.
+        graph_dot(*specs)
+
+    elif specs:     # ascii is default: user doesn't need to provide it explicitly
+        graph_ascii(specs[0], debug=spack.debug)
+        for spec in specs[1:]:
+            print # extra line bt/w independent graphs
+            graph_ascii(spec, debug=spack.debug)
diff --git a/lib/spack/spack/cmd/location.py b/lib/spack/spack/cmd/location.py
index 3fc05d471d..509c336b69 100644
--- a/lib/spack/spack/cmd/location.py
+++ b/lib/spack/spack/cmd/location.py
@@ -111,4 +111,3 @@ def location(parser, args):
                     tty.die("Build directory does not exist yet. Run this to create it:",
                             "spack stage " + " ".join(args.spec))
                 print pkg.stage.source_path
-
diff --git a/lib/spack/spack/cmd/md5.py b/lib/spack/spack/cmd/md5.py
index 496835c64b..dfa1be412b 100644
--- a/lib/spack/spack/cmd/md5.py
+++ b/lib/spack/spack/cmd/md5.py
@@ -41,6 +41,7 @@ def setup_parser(subparser):
 def md5(parser, args):
     if not args.files:
         setup_parser.parser.print_help()
+        return 1
 
     for f in args.files:
         if not os.path.isfile(f):
diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py
index 5fcb0a9b5a..e2cb5689c0 100644
--- a/lib/spack/spack/cmd/spec.py
+++ b/lib/spack/spack/cmd/spec.py
@@ -27,8 +27,8 @@ import spack.cmd
 
 import llnl.util.tty as tty
 
-import spack.url as url
 import spack
+import spack.url as url
 
 description = "print out abstract and concrete versions of a spec."
 
diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py
new file mode 100644
index 0000000000..5fb6a9cd23
--- /dev/null
+++ b/lib/spack/spack/graph.py
@@ -0,0 +1,553 @@
+##############################################################################
+# 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
+##############################################################################
+"""Functions for graphing DAGs of dependencies.
+
+This file contains code for graphing DAGs of software packages
+(i.e. Spack specs).  There are two main functions you probably care
+about:
+
+graph_ascii() will output a colored graph of a spec in ascii format,
+kind of like the graph git shows with "git log --graph", e.g.::
+
+    o  mpileaks
+    |\
+    | |\
+    | o |  callpath
+    |/| |
+    | |\|
+    | |\ \
+    | | |\ \
+    | | | | o  adept-utils
+    | |_|_|/|
+    |/| | | |
+    o | | | |  mpi
+     / / / /
+    | | o |  dyninst
+    | |/| |
+    |/|/| |
+    | | |/
+    | o |  libdwarf
+    |/ /
+    o |  libelf
+     /
+    o  boost
+
+graph_dot() will output a graph of a spec (or multiple specs) in dot
+format.
+
+Note that ``graph_ascii`` assumes a single spec while ``graph_dot``
+can take a number of specs as input.
+
+"""
+__all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot']
+
+from heapq import *
+
+from llnl.util.lang import *
+from llnl.util.tty.color import *
+
+import spack
+from spack.spec import Spec
+
+
+def topological_sort(spec, **kwargs):
+    """Topological sort for specs.
+
+    Return a list of dependency specs sorted topologically.  The spec
+    argument is not modified in the process.
+
+    """
+    reverse = kwargs.get('reverse', False)
+    if not reverse:
+        parents  = lambda s: s.dependents
+        children = lambda s: s.dependencies
+    else:
+        parents  = lambda s: s.dependencies
+        children = lambda s: s.dependents
+
+    # Work on a copy so this is nondestructive.
+    spec = spec.copy()
+    nodes = spec.index()
+
+    topo_order = []
+    remaining = [name for name in nodes.keys() if not parents(nodes[name])]
+    heapify(remaining)
+
+    while remaining:
+        name = heappop(remaining)
+        topo_order.append(name)
+
+        node = nodes[name]
+        for dep in children(node).values():
+            del parents(dep)[node.name]
+            if not parents(dep):
+                heappush(remaining, dep.name)
+
+    if any(parents(s) for s in spec.traverse()):
+        raise ValueError("Spec has cycles!")
+    else:
+        return topo_order
+
+
+def find(seq, predicate):
+    """Find index in seq for which predicate is True.
+
+    Searches the sequence and returns the index of the element for
+    which the predicate evaluates to True.  Returns -1 if the
+    predicate does not evaluate to True for any element in seq.
+
+    """
+    for i, elt in enumerate(seq):
+        if predicate(elt):
+            return i
+    return -1
+
+
+# Names of different graph line states.  We Record previous line
+# states so that we can easily determine what to do when connecting.
+states = ('node', 'collapse', 'merge-right', 'expand-right', 'back-edge')
+NODE, COLLAPSE, MERGE_RIGHT, EXPAND_RIGHT, BACK_EDGE = states
+
+class AsciiGraph(object):
+    def __init__(self):
+        # These can be set after initialization or after a call to
+        # graph() to change behavior.
+        self.node_character = '*'
+        self.debug = False
+        self.indent = 0
+
+        # These are colors in the order they'll be used for edges.
+        # See llnl.util.tty.color for details on color characters.
+        self.colors = 'rgbmcyRGBMCY'
+
+        # Internal vars are used in the graph() function and are
+        # properly initialized there.
+        self._name_to_color = None    # Node name to color
+        self._out = None              # Output stream
+        self._frontier = None         # frontier
+        self._nodes = None            # dict from name -> node
+        self._prev_state = None       # State of previous line
+        self._prev_index = None       # Index of expansion point of prev line
+
+
+    def _indent(self):
+        self._out.write(self.indent * ' ')
+
+
+    def _write_edge(self, string, index, sub=0):
+        """Write a colored edge to the output stream."""
+        name = self._frontier[index][sub]
+        edge = "@%s{%s}" % (self._name_to_color[name], string)
+        self._out.write(edge)
+
+
+    def _connect_deps(self, i, deps, label=None):
+        """Connect dependencies to existing edges in the frontier.
+
+        ``deps`` are to be inserted at position i in the
+        frontier. This routine determines whether other open edges
+        should be merged with <deps> (if there are other open edges
+        pointing to the same place) or whether they should just be
+        inserted as a completely new open edge.
+
+        Open edges that are not fully expanded (i.e. those that point
+        at multiple places) are left intact.
+
+        Parameters:
+
+        label    -- optional debug label for the connection.
+
+        Returns: True if the deps were connected to another edge
+        (i.e. the frontier did not grow) and False if the deps were
+        NOT already in the frontier (i.e. they were inserted and the
+        frontier grew).
+
+        """
+        if len(deps) == 1 and deps in self._frontier:
+            j = self._frontier.index(deps)
+
+            # convert a right connection into a left connection
+            if i < j:
+                self._frontier.pop(j)
+                self._frontier.insert(i, deps)
+                return self._connect_deps(j, deps, label)
+
+            collapse = True
+            if self._prev_state == EXPAND_RIGHT:
+                # Special case where previous line expanded and i is off by 1.
+                self._back_edge_line([], j, i+1, True, label + "-1.5 " + str((i+1,j)))
+                collapse = False
+
+            else:
+                # Previous node also expanded here, so i is off by one.
+                if self._prev_state == NODE and self._prev_index < i:
+                    i += 1
+
+                if i-j > 1:
+                    # We need two lines to connect if distance > 1
+                    self._back_edge_line([], j,  i, True, label + "-1 " + str((i,j)))
+                    collapse = False
+
+            self._back_edge_line([j], -1, -1, collapse, label + "-2 " + str((i,j)))
+            return True
+
+        elif deps:
+            self._frontier.insert(i, deps)
+            return False
+
+
+    def _set_state(self, state, index, label=None):
+        if state not in states:
+            raise ValueError("Invalid graph state!")
+        self._prev_state = state
+        self._prev_index = index
+
+        if self.debug:
+            self._out.write(" " * 20)
+            self._out.write("%-20s" % (
+                str(self._prev_state) if self._prev_state else ''))
+            self._out.write("%-20s" % (str(label) if label else ''))
+            self._out.write("%s" % self._frontier)
+
+
+    def _back_edge_line(self, prev_ends, end, start, collapse, label=None):
+        """Write part of a backwards edge in the graph.
+
+        Writes single- or multi-line backward edges in an ascii graph.
+        For example, a single line edge::
+
+            | | | | o |
+            | | | |/ /  <-- single-line edge connects two nodes.
+            | | | o |
+
+        Or a multi-line edge (requires two calls to back_edge)::
+
+            | | | | o |
+            | |_|_|/ /   <-- multi-line edge crosses vertical edges.
+            |/| | | |
+            o | | | |
+
+        Also handles "pipelined" edges, where the same line contains
+        parts of multiple edges::
+
+                      o start
+            | |_|_|_|/|
+            |/| | |_|/| <-- this line has parts of 2 edges.
+            | | |/| | |
+            o   o
+
+        Arguments:
+
+        prev_ends -- indices in frontier of previous edges that need
+                     to be finished on this line.
+
+        end -- end of the current edge on this line.
+
+        start -- start index of the current edge.
+
+        collapse -- whether the graph will be collapsing (i.e. whether
+                    to slant the end of the line or keep it straight)
+
+        label -- optional debug label to print after the line.
+
+        """
+        def advance(to_pos, edges):
+            """Write edges up to <to_pos>."""
+            for i in range(self._pos, to_pos):
+                for e in edges():
+                    self._write_edge(*e)
+                self._pos += 1
+
+        flen = len(self._frontier)
+        self._pos = 0
+        self._indent()
+
+        for p in prev_ends:
+            advance(p,         lambda: [("| ", self._pos)] )
+            advance(p+1,       lambda: [("|/", self._pos)] )
+
+        if end >= 0:
+            advance(end + 1,   lambda: [("| ", self._pos)] )
+            advance(start - 1, lambda: [("|",  self._pos), ("_", end)] )
+        else:
+            advance(start - 1, lambda: [("| ", self._pos)] )
+
+        if start >= 0:
+            advance(start,     lambda: [("|",  self._pos), ("/", end)] )
+
+        if collapse:
+            advance(flen,      lambda: [(" /", self._pos)] )
+        else:
+            advance(flen,      lambda: [("| ", self._pos)] )
+
+        self._set_state(BACK_EDGE, end, label)
+        self._out.write("\n")
+
+
+    def _node_line(self, index, name):
+        """Writes a line with a node at index."""
+        self._indent()
+        for c in range(index):
+            self._write_edge("| ", c)
+
+        self._out.write("%s " % self.node_character)
+
+        for c in range(index+1, len(self._frontier)):
+            self._write_edge("| ", c)
+
+        self._out.write(" %s" % name)
+        self._set_state(NODE, index)
+        self._out.write("\n")
+
+
+    def _collapse_line(self, index):
+        """Write a collapsing line after a node was added at index."""
+        self._indent()
+        for c in range(index):
+            self._write_edge("| ", c)
+        for c in range(index, len(self._frontier)):
+            self._write_edge(" /", c)
+
+        self._set_state(COLLAPSE, index)
+        self._out.write("\n")
+
+
+    def _merge_right_line(self, index):
+        """Edge at index is same as edge to right.  Merge directly with '\'"""
+        self._indent()
+        for c in range(index):
+            self._write_edge("| ", c)
+        self._write_edge("|", index)
+        self._write_edge("\\", index+1)
+        for c in range(index+1, len(self._frontier)):
+            self._write_edge("| ", c )
+
+        self._set_state(MERGE_RIGHT, index)
+        self._out.write("\n")
+
+
+    def _expand_right_line(self, index):
+        self._indent()
+        for c in range(index):
+            self._write_edge("| ", c)
+
+        self._write_edge("|", index)
+        self._write_edge("\\", index+1)
+
+        for c in range(index+2, len(self._frontier)):
+            self._write_edge(" \\", c)
+
+        self._set_state(EXPAND_RIGHT, index)
+        self._out.write("\n")
+
+
+    def write(self, spec, **kwargs):
+        """Write out an ascii graph of the provided spec.
+
+        Arguments:
+        spec -- spec to graph.  This only handles one spec at a time.
+
+        Optional arguments:
+
+        out -- file object to write out to (default is sys.stdout)
+
+        color -- whether to write in color.  Default is to autodetect
+                 based on output file.
+
+        """
+        out = kwargs.get('out', None)
+        if not out:
+            out = sys.stdout
+
+        color = kwargs.get('color', None)
+        if not color:
+            color = out.isatty()
+        self._out = ColorStream(sys.stdout, color=color)
+
+        # We'll traverse the spec in topo order as we graph it.
+        topo_order = topological_sort(spec, reverse=True)
+
+        # Work on a copy to be nondestructive
+        spec = spec.copy()
+        self._nodes = spec.index()
+
+        # Colors associated with each node in the DAG.
+        # Edges are colored by the node they point to.
+        self._name_to_color = dict((name, self.colors[i % len(self.colors)])
+                                  for i, name in enumerate(topo_order))
+
+        # Frontier tracks open edges of the graph as it's written out.
+        self._frontier = [[spec.name]]
+        while self._frontier:
+            # Find an unexpanded part of frontier
+            i = find(self._frontier, lambda f: len(f) > 1)
+
+            if i >= 0:
+                # Expand frontier until there are enough columns for all children.
+
+                # Figure out how many back connections there are and
+                # sort them so we do them in order
+                back = []
+                for d in self._frontier[i]:
+                    b = find(self._frontier[:i], lambda f: f == [d])
+                    if b != -1:
+                        back.append((b, d))
+
+                # Do all back connections in sorted order so we can
+                # pipeline them and save space.
+                if back:
+                    back.sort()
+                    prev_ends = []
+                    for j, (b, d) in enumerate(back):
+                        self._frontier[i].remove(d)
+                        if i-b > 1:
+                            self._back_edge_line(prev_ends, b, i, False, 'left-1')
+                            del prev_ends[:]
+                        prev_ends.append(b)
+
+                    # Check whether we did ALL the deps as back edges,
+                    # in which case we're done.
+                    collapse = not self._frontier[i]
+                    if collapse:
+                        self._frontier.pop(i)
+                    self._back_edge_line(prev_ends, -1, -1, collapse, 'left-2')
+
+                elif len(self._frontier[i]) > 1:
+                    # Expand forward after doing all back connections
+
+                    if (i+1 < len(self._frontier) and len(self._frontier[i+1]) == 1
+                        and self._frontier[i+1][0] in self._frontier[i]):
+                        # We need to connect to the element to the right.
+                        # Keep lines straight by connecting directly and
+                        # avoiding unnecessary expand/contract.
+                        name = self._frontier[i+1][0]
+                        self._frontier[i].remove(name)
+                        self._merge_right_line(i)
+
+                    else:
+                        # Just allow the expansion here.
+                        name = self._frontier[i].pop(0)
+                        deps = [name]
+                        self._frontier.insert(i, deps)
+                        self._expand_right_line(i)
+
+                        self._frontier.pop(i)
+                        self._connect_deps(i, deps, "post-expand")
+
+
+                # Handle any remaining back edges to the right
+                j = i+1
+                while j < len(self._frontier):
+                    deps = self._frontier.pop(j)
+                    if not self._connect_deps(j, deps, "back-from-right"):
+                        j += 1
+
+            else:
+                # Nothing to expand; add dependencies for a node.
+                name = topo_order.pop()
+                node = self._nodes[name]
+
+                # Find the named node in the frontier and draw it.
+                i = find(self._frontier, lambda f: name in f)
+                self._node_line(i, name)
+
+                # Replace node with its dependencies
+                self._frontier.pop(i)
+                if node.dependencies:
+                    deps = sorted((d for d in node.dependencies), reverse=True)
+                    self._connect_deps(i, deps, "new-deps") # anywhere.
+
+                elif self._frontier:
+                    self._collapse_line(i)
+
+
+def graph_ascii(spec, **kwargs):
+    node_character = kwargs.get('node', 'o')
+    out            = kwargs.pop('out', None)
+    debug          = kwargs.pop('debug', False)
+    indent         = kwargs.pop('indent', 0)
+    color          = kwargs.pop('color', None)
+    check_kwargs(kwargs, graph_ascii)
+
+    graph = AsciiGraph()
+    graph.debug = debug
+    graph.indent = indent
+    graph.node_character = node_character
+
+    graph.write(spec, color=color, out=out)
+
+
+
+def graph_dot(*specs, **kwargs):
+    """Generate a graph in dot format of all provided specs.
+
+    Print out a dot formatted graph of all the dependencies between
+    package.  Output can be passed to graphviz, e.g.:
+
+        spack graph --dot qt | dot -Tpdf > spack-graph.pdf
+
+    """
+    out = kwargs.pop('out', sys.stdout)
+    check_kwargs(kwargs, graph_dot)
+
+    out.write('digraph G {\n')
+    out.write('  label = "Spack Dependencies"\n')
+    out.write('  labelloc = "b"\n')
+    out.write('  rankdir = "LR"\n')
+    out.write('  ranksep = "5"\n')
+    out.write('\n')
+
+    def quote(string):
+        return '"%s"' % string
+
+    if not specs:
+        specs = [p.name for p in spack.db.all_packages()]
+    else:
+        roots = specs
+        specs = set()
+        for spec in roots:
+            specs.update(Spec(s.name) for s in spec.normalized().traverse())
+
+    deps = []
+    for spec in specs:
+        out.write('  %-30s [label="%s"]\n' % (quote(spec.name), spec.name))
+
+        # Skip virtual specs (we'll find out about them from concrete ones.
+        if spec.virtual:
+            continue
+
+        # Add edges for each depends_on in the package.
+        for dep_name, dep in spec.package.dependencies.iteritems():
+            deps.append((spec.name, dep_name))
+
+        # If the package provides something, add an edge for that.
+        for provider in set(s.name for s in spec.package.provided):
+            deps.append((provider, spec.name))
+
+    out.write('\n')
+
+    for pair in deps:
+        out.write('  "%s" -> "%s"\n' % pair)
+    out.write('}\n')
diff --git a/lib/spack/spack/packages.py b/lib/spack/spack/packages.py
index 25d01fe7eb..db43d3909a 100644
--- a/lib/spack/spack/packages.py
+++ b/lib/spack/spack/packages.py
@@ -30,7 +30,7 @@ import imp
 
 import llnl.util.tty as tty
 from llnl.util.filesystem import join_path
-from llnl.util.lang import memoized
+from llnl.util.lang import *
 
 import spack.error
 import spack.spec
@@ -214,38 +214,6 @@ class PackageDB(object):
         return cls
 
 
-    def graph_dependencies(self, out=sys.stdout):
-        """Print out a graph of all the dependencies between package.
-           Graph is in dot format."""
-        out.write('digraph G {\n')
-        out.write('  label = "Spack Dependencies"\n')
-        out.write('  labelloc = "b"\n')
-        out.write('  rankdir = "LR"\n')
-        out.write('  ranksep = "5"\n')
-        out.write('\n')
-
-        def quote(string):
-            return '"%s"' % string
-
-        deps = []
-        for pkg in self.all_packages():
-            out.write('  %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name))
-
-            # Add edges for each depends_on in the package.
-            for dep_name, dep in pkg.dependencies.iteritems():
-                deps.append((pkg.name, dep_name))
-
-            # If the package provides something, add an edge for that.
-            for provider in set(p.name for p in pkg.provided):
-                deps.append((provider, pkg.name))
-
-        out.write('\n')
-
-        for pair in deps:
-            out.write('  "%s" -> "%s"\n' % pair)
-        out.write('}\n')
-
-
 class UnknownPackageError(spack.error.SpackError):
     """Raised when we encounter a package spack doesn't have."""
     def __init__(self, name):
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 570bb1191c..2f4fe9ca24 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -712,6 +712,15 @@ class Spec(object):
             raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message)
 
 
+    def index(self):
+        """Return DependencyMap that points to all the dependencies in this
+           spec."""
+        dm = DependencyMap()
+        for spec in self.traverse():
+            dm[spec.name] = spec
+        return dm
+
+
     def flatten(self):
         """Pull all dependencies up to the root (this spec).
            Merge constraints for dependencies with the same name, and if they
@@ -858,7 +867,7 @@ class Spec(object):
     def normalized(self):
         """Return a normalized copy of this spec without modifying this spec."""
         clone = self.copy()
-        clone.normalized()
+        clone.normalize()
         return clone
 
 
@@ -1289,12 +1298,13 @@ class Spec(object):
     def tree(self, **kwargs):
         """Prints out this spec and its dependencies, tree-formatted
            with indentation."""
-        color  = kwargs.get('color', False)
-        depth  = kwargs.get('depth', False)
-        showid = kwargs.get('ids',   False)
-        cover  = kwargs.get('cover', 'nodes')
-        indent = kwargs.get('indent', 0)
-        format = kwargs.get('format', '$_$@$%@$+$=')
+        color  = kwargs.pop('color', False)
+        depth  = kwargs.pop('depth', False)
+        showid = kwargs.pop('ids',   False)
+        cover  = kwargs.pop('cover', 'nodes')
+        indent = kwargs.pop('indent', 0)
+        fmt    = kwargs.pop('format', '$_$@$%@$+$=')
+        check_kwargs(kwargs, self.tree)
 
         out = ""
         cur_id = 0
@@ -1311,7 +1321,7 @@ class Spec(object):
             out += ("    " * d)
             if d > 0:
                 out += "^"
-            out += node.format(format, color=color) + "\n"
+            out += node.format(fmt, color=color) + "\n"
         return out