summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/spack/spack/spec.py113
1 files changed, 71 insertions, 42 deletions
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index a8d080b0d2..caa8b0972f 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -1349,57 +1349,71 @@ class Spec(object):
return sorted((d for d in deps), reverse=True)
- def back_edge(end, start, **kwargs):
- assert(end < start)
- collapse = kwargs.get('collapse', True)
- label = kwargs.get('label', '') # debug label
+ def back_edge(prev_ends, end, start, collapse, label=None):
+ # Use prev & next for pipelining -- pipelined edges have
+ # the same start, and they're in sorted order e.g.::
+ #
+ # start
+ # | |_|_|_|/|
+ # |/| | |_|/|
+ # | | |/| | | <-- when doing this line.
+ # prev end
+ #
+ out.write(indent)
+ f = len(frontier)
- if (start - end) > 1:
- # This part draws a long back edge.
- out.write(indent)
- out.write("| " * (end + 1))
- out.write("|_" * (start - end - 2))
- out.write("|/")
- if collapse:
- out.write(" ")
- out.write("/ " * (len(frontier) - start))
- else:
- out.write("| " * (len(frontier) - start))
+ def advance(to, fun):
+ for i in range(advance.pos, to):
+ fun()
+ advance.pos += 1
+ advance.pos = 0
+
+ for p in prev_ends:
+ advance(p, lambda: out.write("| "))
+ advance(p+1, lambda: out.write("|/"))
- if debug:
- out.write(" " * 20)
- out.write("%s %s" % (frontier, label))
+ if end >= 0:
+ advance(end + 1, lambda: out.write("| "))
+ advance(start - 1, lambda: out.write("|_"))
+ else:
+ advance(start - 1, lambda: out.write("| "))
- out.write("\n")
+ if start >= 0:
+ advance(start, lambda: out.write("|/"))
- # This part draws the final collapsing line
- out.write(indent)
- out.write("| " * end)
- out.write("|/")
- out.write("| " * (start - end - 1))
- if (start - end) > 1 or not collapse:
- out.write("| " * (len(frontier) - start))
+ if collapse:
+ advance(len(frontier), lambda: out.write(" /"))
else:
- out.write(" /" * (len(frontier) - start))
+ advance(len(frontier), lambda: out.write("| "))
if debug:
- out.write(" " * 20)
- out.write("%s %s" % (frontier, label))
+ out.write(" " * 10)
+ if label: out.write(label)
+ out.write("%s" % frontier)
out.write("\n")
- def connect_deps(i, deps, **kwargs):
+ def connect_deps(i, deps, collapse, label):
+ """Connect dependencies to frontier at position i."""
if len(deps) == 1 and deps in frontier:
j = frontier.index(deps)
+
+ # connect to the left
if j < i:
- back_edge(j, i, **kwargs)
+ if i-j > 1: # two lines if distance > 1
+ back_edge([], j, i, True, label)
+ back_edge([j], -1, -1, (i-j == 1), label)
+
+ # connect to the right
else:
if i < j:
frontier.pop(j)
frontier.insert(i, deps)
- back_edge(i, j+1, **kwargs)
+ if j-i > 1:
+ back_edge([], i, j+1, collapse, label)
+ back_edge([i], -1, -1, not (j-i > 1) and collapse, label)
return True
elif deps:
@@ -1408,8 +1422,10 @@ class Spec(object):
def add_deps_to_frontier(node, i):
+ """Add dependencies to frontier, connecting them if they're fully
+ expanded, and deleting parent pointers."""
deps = ordered_deps(node)
- connect_deps(i, deps, label="add_deps")
+ connect_deps(i, deps, True, "add_deps")
for d in deps:
del nodes[d].dependents[node.name]
@@ -1432,13 +1448,26 @@ class Spec(object):
# Expand frontier until there are enough columns for all children.
if i >= 0:
- # Do all back connections possible from this element
- # before expanding.
- back_connect = [d for d in frontier[i] if [d] in frontier[:i]]
- for d in back_connect:
- j = frontier.index([d])
- frontier[i].remove(d)
- connect_deps(i, [d], collapse=False, label="back_connect")
+ # Figure out how many back connections there are and
+ # sort them so we do them in order
+ back = []
+ for d in frontier[i]:
+ b = find(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):
+ if i-b > 1:
+ back_edge(prev_ends, b, i, False)
+ del prev_ends[:]
+ prev_ends.append(b)
+ frontier[i].remove(d)
+ back_edge(prev_ends, -1, -1, False)
if not frontier[i]:
frontier.pop(i)
@@ -1465,7 +1494,7 @@ class Spec(object):
deps = [name]
out.write(" \\" * (len(frontier) - i - 1))
out.write("\n")
- connect_deps(i, deps, label="expansion")
+ connect_deps(i, deps, True, "expansion")
# Handle any remaining back edges to the right
j = i+1
@@ -1474,7 +1503,7 @@ class Spec(object):
# TODO: semantics of connect_deps are weird.
# TODO: false return means the popped item was put
# TODO: back & not connected.
- if not connect_deps(j, deps, label="ending"):
+ if not connect_deps(j, deps, True, "rem_back"):
j += 1
else: