monotone

monotone Mtn Source Tree

Root/contrib/asciik.py

1#!/usr/bin/python
2
3# BUGS:
4#
5# 1)
6#
7# | | | | | | |\ \ \ \
8# | | | | | | o | | | | 145c71fb56cff358dd711773586ae6b5219b0cfc
9# | | | | | | |\ \ \ \ \
10#
11# should be
12#
13# | | | | | | |\ \ \ \
14# | | | | | | o \ \ \ \ 145c71fb56cff358dd711773586ae6b5219b0cfc
15# | | | | | | |\ \ \ \ \
16#
17# need some sort "inertia", if we moved sideways before and are moving
18# sideways now...
19#
20# 2)
21#
22# It actually is possible to remove a ghost on the same line as a long
23# rightwards edge -- and it even looks better than not doing it, at least in
24# some cases. Consider:
25#
26# Current:
27#
28# | | | o | | | | | 0f07da5974be8bf91495a34093efc635dcf1f01c
29# | | | |\ \ \ \ \ \
30# | | | | .-o | | | | 20037e09def77cc217679bf2f72baf5fa0415649
31# | | | |/| | | | |
32# | | | o---. | | | | de74b6e2bd612ba40f1afc3eba3f9a3d8f419135
33# | | | | | \| | | |
34# | | | o | | | | | 3fd16665caab9d942e6c5254b477587ff7d3722d
35# | | | | | / / / /
36# | | | o | | | | | 38f3561cc4bf294b99436f98cd97fc707b422bfa
37# | | | | | | | | |
38# | | | | .-o | | | 59017bc836986a59fd1ac6fba4f78fe1045c67e9
39# | | | |/| | | | |
40# | | | o | | | | | 97e8f96bb34774003de428292edbdd562ca6d867
41# | | | | | | | | |
42#
43# Desired:
44#
45# | | | o | | | | | 0f07da5974be8bf91495a34093efc635dcf1f01c
46# | | | |\ \ \ \ \ \
47# | | | | .-o | | | | 20037e09def77cc217679bf2f72baf5fa0415649
48# | | | |/| | | | |
49# | | | o-. | | | | de74b6e2bd612ba40f1afc3eba3f9a3d8f419135
50# | | | | |\ / / / /
51# | | | o | | | | | 3fd16665caab9d942e6c5254b477587ff7d3722d
52# | | | | | | | | |
53# | | | o | | | | | 38f3561cc4bf294b99436f98cd97fc707b422bfa
54# | | | | | | | | |
55# | | | | .-o | | | 59017bc836986a59fd1ac6fba4f78fe1045c67e9
56# | | | |/| | | | |
57# | | | o | | | | | 97e8f96bb34774003de428292edbdd562ca6d867
58# | | | | | | | | |
59#
60# Possibly the no-shift-while-drawing-long-edges code could even be removed,
61# deferring to the no-edge-crossings code.
62
63
64
65
66# How this works:
67# This is completely iterative; we have no lookahead whatsoever. We output
68# each line before even looking at the next. (This means the layout is
69# much less clever than it could be, because there is no global
70# optimization; but it also means we can calculate these things in zero
71# time, incrementally while running log.)
72#
73# Output comes in two-line chunks -- a "line", which contains exactly one
74# node, and then an "interline", which contains edges that will link us to
75# the next line.
76#
77# A design goal of the system is that you can always trivially increase the
78# space between two "lines", by adding another "| | | |"-type interline
79# after the real interline. This allows us to put arbitrarily long
80# annotations in the space to the right of the graph, for each revision --
81# we can just stretch the graph portion to give us more space.
82#
83# Loop:
84# We start knowing, for each logical column, what thing has to go there
85# (because this was determined last time)
86# We use this to first determine what thing has to go in each column next
87# time (though we will not draw them yet).
88# This is somewhat tricky, because we do want to squish things towards the
89# left when possible. However, we have very limited drawing options -- we
90# can slide several things 1 space to the left or right and do no other long
91# sideways edges; or, we can draw 1 or 2 long sideways edges, but then
92# everything else must go straight. So, we try a few different layouts.
93# The options are, remove a "ghost" if one exists, don't remove a ghost, and
94# insert a ghost. (A "ghost" is a blank space left by a line that has
95# terminated or merged back into another line, but we haven't shifted things
96# over sideways yet to fill in the space.)
97#
98# Having found a layout that works, we draw lines connecting things! Yay.
99
100import sys
101from sets import Set as set
102
103# returns a dict {node: (parents,)}
104def parsegraph(f):
105 g = {}
106 for line in f:
107 pieces = line.strip().split()
108 g[pieces[0]] = tuple(pieces[1:])
109 return g
110
111# returns a list from bottom to top
112def parseorder(f):
113 order = []
114 for line in f:
115 order.append(line.strip())
116 order.reverse()
117 return order
118
119# takes two files:
120# one is output of 'automate graph'
121# other is output of 'automate select i: | automate toposort -@-'
122def main(name, args):
123 assert len(args) == 2
124 graph = parsegraph(open(args[0]))
125 order = parseorder(open(args[1]))
126
127 row = []
128 for rev in order:
129 row = print_row(row, rev, graph[rev])
130
131def print_row(curr_row, curr_rev, parents):
132 if curr_rev not in curr_row:
133 curr_row.append(curr_rev)
134 curr_loc = curr_row.index(curr_rev)
135
136 new_revs = []
137 for p in parents:
138 if p not in curr_row:
139 new_revs.append(p)
140 next_row = list(curr_row)
141 next_row[curr_loc:curr_loc + 1] = new_revs
142
143 # now next_row contains exactly the revisions it needs to, except that no
144 # ghost handling has been done.
145
146 no_ghost = without_a_ghost(next_row)
147 if try_draw(curr_row, no_ghost, curr_loc, parents):
148 return no_ghost
149 if try_draw(curr_row, next_row, curr_loc, parents):
150 return next_row
151 if not new_revs: # this line has disappeared
152 extra_ghost = with_a_ghost_added(next_row, curr_loc)
153 if try_draw(curr_row, extra_ghost, curr_loc, parents):
154 return extra_ghost
155 assert False
156
157def without_a_ghost(next_row):
158 wo = list(next_row)
159 if None in next_row:
160 wo.pop(next_row.index(None))
161 return wo
162
163def with_a_ghost_added(next_row, loc):
164 w = list(next_row)
165 w.insert(loc, None)
166 return w
167
168# coordinates of the columns where we draw sideways-moving links
169def links_cross(links):
170 crosses = set()
171 for i, j in links:
172 if i != j:
173 for coord in xrange(2 * min(i, j) + 1, 2 * max(i, j)):
174 crosses.add(coord)
175 return crosses
176
177def try_draw(curr_row, next_row, curr_loc, parents):
178 curr_items = len(curr_row)
179 next_items = len(next_row)
180 curr_ghosts = []
181 for i in xrange(curr_items):
182 if curr_row[i] is None:
183 curr_ghosts.append(i)
184 preservation_links = []
185 have_shift = False
186 for rev in curr_row:
187 if rev is not None and rev in next_row:
188 i = curr_row.index(rev)
189 j = next_row.index(rev)
190 if i != j:
191 have_shift = True
192 if abs(i - j) > 1:
193 return False
194 preservation_links.append((i, j))
195 parent_links = []
196 for p in parents:
197 i = curr_loc
198 j = next_row.index(p)
199 if abs(i - j) > 1 and have_shift:
200 return False
201 parent_links.append((i, j))
202
203 preservation_crosses = links_cross(preservation_links)
204 parent_crosses = links_cross(parent_links)
205 if preservation_crosses.intersection(parent_crosses):
206 return False
207
208 links = preservation_links + parent_links
209 draw(curr_items, next_items, curr_loc, links, curr_ghosts, curr_row[curr_loc])
210 return True
211
212def draw(curr_items, next_items, curr_loc, links, curr_ghosts, annotation):
213 line = [" "] * (curr_items * 2 - 1)
214 interline = [" "] * (max(curr_items, next_items) * 2 - 1)
215
216 # first draw the flow-through bars in the line
217 for i in xrange(curr_items):
218 line[i * 2] = "|"
219 # but then erase it for ghosts
220 for i in curr_ghosts:
221 line[i * 2] = " "
222 # then the links
223 dots = set()
224 for i, j in links:
225 if i == j:
226 interline[2 * i] = "|"
227 else:
228 if j < i:
229 # | .---o
230 # |/| | |
231 # 0 1 2 3
232 # j i
233 # 0123456
234 # s e
235 start = 2*j + 3
236 end = 2*i
237 dot = start - 1
238 interline[dot - 1] = "/"
239 else: # i < j
240 # o---.
241 # | | |\|
242 # 0 1 2 3
243 # i j
244 # 0123456
245 # s e
246 start = 2*i + 1
247 end = 2*j - 2
248 dot = end
249 interline[dot + 1] = "\\"
250 if end - start >= 1:
251 dots.add(dot)
252 line[start:end] = "-" * (end - start)
253 # add any dots (must do this in a second pass, so that if there are
254 # cases like:
255 # | .-----.-o
256 # |/| | |/|
257 # where we want to make sure the second dot overwrites the first --.
258 for dot in dots:
259 line[dot] = "."
260 # and add the main attraction (may overwrite a ".").
261 line[curr_loc * 2] = "o"
262
263 print "".join(line) + " " + annotation
264 print "".join(interline)
265
266if __name__ == "__main__":
267 main(sys.argv[0], sys.argv[1:])

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status