monotone

monotone Mtn Source Tree

Root/asciik.cc

1// Copyright (C) 2006 Nathaniel Smith <njs@pobox.com>
2// Copyright (C) 2007 Lapo Luchini <lapo@lapo.it>
3// Copyright (C) 2007 Gabriele Dini Ciacci <dark.schneider@iol.it>
4//
5// This program is made available under the GNU GPL version 2.0 or
6// greater. See the accompanying file COPYING for details.
7//
8// This program is distributed WITHOUT ANY WARRANTY; without even the
9// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
10// PURPOSE.
11
12/*
13BUGS:
14
151)
16
17| | | | | | |\ \ \ \
18| | | | | | o | | | | 145c71fb56cff358dd711773586ae6b5219b0cfc
19| | | | | | |\ \ \ \ \
20
21should be
22
23| | | | | | |\ \ \ \
24| | | | | | o \ \ \ \ 145c71fb56cff358dd711773586ae6b5219b0cfc
25| | | | | | |\ \ \ \ \
26
27need some sort "inertia", if we moved sideways before and are moving
28sideways now...
29
302)
31
32It actually is possible to remove a ghost on the same line as a long
33rightwards edge -- and it even looks better than not doing it, at least in
34some cases. Consider:
35
36Current:
37
38| | | o | | | | | 0f07da5974be8bf91495a34093efc635dcf1f01c
39| | | |\ \ \ \ \ \
40| | | | .-o | | | | 20037e09def77cc217679bf2f72baf5fa0415649
41| | | |/| | | | |
42| | | o---. | | | | de74b6e2bd612ba40f1afc3eba3f9a3d8f419135
43| | | | | \| | | |
44| | | o | | | | | 3fd16665caab9d942e6c5254b477587ff7d3722d
45| | | | | / / / /
46| | | o | | | | | 38f3561cc4bf294b99436f98cd97fc707b422bfa
47| | | | | | | | |
48| | | | .-o | | | 59017bc836986a59fd1ac6fba4f78fe1045c67e9
49| | | |/| | | | |
50| | | o | | | | | 97e8f96bb34774003de428292edbdd562ca6d867
51| | | | | | | | |
52
53Desired:
54
55| | | o | | | | | 0f07da5974be8bf91495a34093efc635dcf1f01c
56| | | |\ \ \ \ \ \
57| | | | .-o | | | | 20037e09def77cc217679bf2f72baf5fa0415649
58| | | |/| | | | |
59| | | o-. | | | | de74b6e2bd612ba40f1afc3eba3f9a3d8f419135
60| | | | |\ / / / /
61| | | o | | | | | 3fd16665caab9d942e6c5254b477587ff7d3722d
62| | | | | | | | |
63| | | o | | | | | 38f3561cc4bf294b99436f98cd97fc707b422bfa
64| | | | | | | | |
65| | | | .-o | | | 59017bc836986a59fd1ac6fba4f78fe1045c67e9
66| | | |/| | | | |
67| | | o | | | | | 97e8f96bb34774003de428292edbdd562ca6d867
68| | | | | | | | |
69
70Possibly the no-shift-while-drawing-long-edges code could even be removed,
71deferring to the no-edge-crossings code.
72
73
74How this works:
75 This is completely iterative; we have no lookahead whatsoever. We output
76 each line before even looking at the next. (This means the layout is
77 much less clever than it could be, because there is no global
78 optimization; but it also means we can calculate these things in zero
79 time, incrementally while running log.)
80
81 Output comes in two-line chunks -- a "line", which contains exactly one
82 node, and then an "interline", which contains edges that will link us to
83 the next line.
84
85 A design goal of the system is that you can always trivially increase the
86 space between two "lines", by adding another "| | | |"-type interline
87 after the real interline. This allows us to put arbitrarily long
88 annotations in the space to the right of the graph, for each revision --
89 we can just stretch the graph portion to give us more space.
90
91Loop:
92 We start knowing, for each logical column, what thing has to go there
93 (because this was determined last time)
94 We use this to first determine what thing has to go in each column next
95 time (though we will not draw them yet).
96 This is somewhat tricky, because we do want to squish things towards the
97 left when possible. However, we have very limited drawing options -- we
98 can slide several things 1 space to the left or right and do no other long
99 sideways edges; or, we can draw 1 or 2 long sideways edges, but then
100 everything else must go straight. So, we try a few different layouts.
101 The options are, remove a "ghost" if one exists, don't remove a ghost, and
102 insert a ghost. (A "ghost" is a blank space left by a line that has
103 terminated or merged back into another line, but we haven't shifted things
104 over sideways yet to fill in the space.)
105
106 Having found a layout that works, we draw lines connecting things! Yay.
107*/
108
109#include <algorithm>
110#include <iostream>
111#include <iterator>
112
113#include "asciik.hh"
114#include "cmd.hh"
115#include "simplestring_xform.hh"
116
117using std::insert_iterator;
118using std::max;
119using std::min;
120using std::ostream;
121using std::ostream_iterator;
122using std::pair;
123using std::set;
124using std::string;
125using std::vector;
126using std::find;
127using std::reverse;
128using std::distance;
129
130static revision_id ghost; // valid but empty revision_id to be used as ghost value
131
132asciik::asciik(ostream & os, size_t min_width)
133 : width(min_width), output(os)
134{
135}
136
137void
138asciik::links_cross(set<pair<size_t, size_t> > const & links,
139 set<size_t> & crosses) const
140{
141 for (set<pair<size_t, size_t> >::const_iterator link = links.begin();
142 link != links.end(); ++link)
143 {
144 size_t i = link->first, j = link->second;
145 if (i != j)
146 for (size_t coord = 2 * min(i, j) + 1, end = 2 * max(i, j);
147 coord < end; ++coord)
148 crosses.insert(coord);
149 }
150}
151
152void
153asciik::draw(size_t const curr_items,
154 size_t const next_items,
155 size_t const curr_loc,
156 set<pair<size_t, size_t> > const & links,
157 set<size_t> const & curr_ghosts,
158 string const & annotation) const
159{
160 size_t line_len = max(width, max(curr_items, next_items) * 2);
161 string line(line_len, ' '); // actual len: curr_items * 2 - 1
162 string interline(line_len, ' '); // actual len: max(curr_items, next_items) * 2 - 1
163 string interline2(line_len, ' ');
164
165 // first draw the flow-through bars in the line
166 for (size_t i = 0; i < curr_items; ++i)
167 line[i * 2] = '|';
168
169 // but then erase it for ghosts
170 for (set<size_t>::const_iterator i = curr_ghosts.begin();
171 i != curr_ghosts.end(); ++i)
172 line[(*i) * 2] = ' ';
173
174 // then the links
175 set<size_t> dots;
176 for (set<pair<size_t, size_t> >::const_iterator link = links.begin();
177 link != links.end(); ++link)
178 {
179 size_t i = link->first;
180 size_t j = link->second;
181 if (i == j)
182 interline[2 * i] = '|';
183 else
184 {
185 size_t start, end, dot;
186 if (j < i)
187 {
188 // | .---o
189 // |/| | |
190 // 0 1 2 3
191 // j i
192 // 0123456
193 // s e
194 start = 2 * j + 3;
195 end = 2 * i;
196 dot = start - 1;
197 interline[dot - 1] = '/';
198 }
199 else // j > i
200 {
201 // o---.
202 // | | |\|
203 // 0 1 2 3
204 // i j
205 // 0123456
206 // s e
207 start = 2 * i + 1;
208 end = 2 * j - 2;
209 dot = end;
210 interline[dot + 1] = '\\';
211 }
212 if (end > start)
213 {
214 dots.insert(dot);
215 for (size_t l = start; l < end; ++l)
216 line[l] = '-';
217 }
218 }
219 // prepare the proper continuation line
220 interline2[j * 2] = '|';
221 }
222 // add any dots (must do this in a second pass, so that things still work if
223 // there are cases like:
224 // | .-----.-o
225 // |/| | |/|
226 // where we want to make sure that the second dot overwrites the first -.
227 for (set<size_t>::const_iterator dot = dots.begin();
228 dot != dots.end(); ++dot)
229 line[*dot] = '.';
230 // and add the main attraction (may overwrite a '.').
231 line[curr_loc * 2] = 'o';
232
233 // split a multi-line annotation
234 vector<string> lines;
235 split_into_lines(annotation, lines);
236 int num_lines = lines.size();
237 if (num_lines < 1)
238 lines.push_back(string(""));
239 if (num_lines < 2)
240 lines.push_back(string(""));
241 // ignore empty lines at the end
242 while ((num_lines > 2) && (lines[num_lines - 1].size() == 0))
243 --num_lines;
244
245 // prints it out
246 //TODO convert line/interline/interline2 from ASCII to system charset
247 output << line << " " << lines[0] << '\n';
248 output << interline << " " << lines[1] << '\n';
249 for (int i = 2; i < num_lines; ++i)
250 output << interline2 << " " << lines[i] << '\n';
251}
252
253bool
254asciik::try_draw(vector<revision_id> const & next_row,
255 size_t const curr_loc,
256 set<revision_id> const & parents,
257 string const & annotation) const
258{
259 size_t curr_items = curr_row.size();
260 size_t next_items = next_row.size();
261 I(curr_loc < curr_items);
262
263 set<size_t> curr_ghosts;
264 for (size_t i = 0; i < curr_items; ++i)
265 if (idx(curr_row, i) == ghost)
266 curr_ghosts.insert(i);
267
268 set<pair<size_t, size_t> > preservation_links;
269 bool have_shift = false;
270 for (size_t i = 0; i < curr_items; ++i)
271 {
272 if (idx(curr_row, i) != ghost)
273 {
274 vector<revision_id>::const_iterator found =
275 find(next_row.begin(), next_row.end(), idx(curr_row, i));
276 if (found != next_row.end())
277 {
278 size_t j = distance(next_row.begin(), found);
279 size_t d = i>j ? i-j : j-i;
280 if (d > 1)
281 return false;
282 if (d != 0)
283 have_shift = true;
284 preservation_links.insert(pair<size_t, size_t>(i, j));
285 }
286 }
287 }
288
289 set<pair<size_t, size_t> > parent_links;
290 for (set<revision_id>::const_iterator p = parents.begin();
291 p != parents.end(); ++p)
292 if (*p != ghost)
293 {
294 size_t i = curr_loc;
295 size_t j = distance(next_row.begin(),
296 find(next_row.begin(), next_row.end(), *p));
297 I(j < next_items);
298 size_t d = i>j ? i-j : j-i;
299 if ((d > 1) && have_shift)
300 return false;
301 parent_links.insert(pair<size_t, size_t>(i, j));
302 }
303
304 set<size_t> preservation_crosses, parent_crosses, intersection_crosses;
305 links_cross(preservation_links, preservation_crosses);
306 links_cross(parent_links, parent_crosses);
307 set_intersection(
308 preservation_crosses.begin(), preservation_crosses.end(),
309 parent_crosses.begin(), parent_crosses.end(),
310 insert_iterator<set<size_t> >(intersection_crosses, intersection_crosses.begin()));
311 if (intersection_crosses.size() > 0)
312 return false;
313
314 set<pair<size_t, size_t> > links(preservation_links);
315 copy(parent_links.begin(), parent_links.end(),
316 insert_iterator<set<pair<size_t, size_t> > >(links, links.begin()));
317 draw(curr_items, next_items, curr_loc, links, curr_ghosts, annotation);
318 return true;
319}
320
321void
322asciik::print(revision_id const & rev,
323 set<revision_id> const & parents,
324 string const & annotation)
325{
326 if (find(curr_row.begin(), curr_row.end(), rev) == curr_row.end())
327 curr_row.push_back(rev);
328 size_t curr_loc = distance(curr_row.begin(),
329 find(curr_row.begin(), curr_row.end(), rev));
330 // it must be found as either it was there already or we just added it
331 I(curr_loc < curr_row.size());
332
333 set<revision_id> new_revs;
334 for (set<revision_id>::const_iterator parent = parents.begin();
335 parent != parents.end(); ++parent)
336 if (find(curr_row.begin(), curr_row.end(), *parent) == curr_row.end())
337 new_revs.insert(*parent);
338
339 vector<revision_id> next_row(curr_row);
340 I(curr_loc < next_row.size());
341 next_row.insert(
342 next_row.erase(next_row.begin() + curr_loc),
343 new_revs.begin(), new_revs.end());
344
345 // now next_row contains exactly the revisions it needs to, except that no
346 // ghost handling has been done.
347 vector<revision_id> no_ghost(next_row);
348 vector<revision_id>::iterator first_ghost = find(no_ghost.begin(),
349 no_ghost.end(), ghost);
350 if (first_ghost != no_ghost.end())
351 no_ghost.erase(first_ghost);
352
353 if (try_draw(no_ghost, curr_loc, parents, annotation))
354 curr_row = no_ghost;
355 else if (try_draw(next_row, curr_loc, parents, annotation))
356 curr_row = next_row;
357 else if (new_revs.size() == 0) // this line has disappeared
358 {
359 vector<revision_id> extra_ghost(next_row);
360 I(curr_loc < extra_ghost.size());
361 extra_ghost.insert(extra_ghost.begin() + curr_loc, ghost);
362 I(try_draw(extra_ghost, curr_loc, parents, annotation));
363 curr_row = extra_ghost;
364 }
365}
366
367CMD(asciik, N_("debug"), N_("SELECTOR"),
368 N_("prints an ASCII representation of the graph"), options::opts::none)
369{
370 N(args.size() == 1,
371 F("wrong argument count"));
372
373 vector<pair<selectors::selector_type, string> >
374 sels(selectors::parse_selector(args[0](), app));
375
376 // we jam through an "empty" selection on sel_ident type
377 set<string> completions;
378 //set<hexenc<id>> completions;
379 selectors::selector_type ty = selectors::sel_ident;
380 selectors::complete_selector("", sels, ty, completions, app);
381
382 asciik graph(std::cout, 10);
383 set<revision_id> revs;
384 for (set<string>::const_iterator i = completions.begin();
385 i != completions.end(); ++i)
386 {
387 revision_id rid(*i);
388 revs.insert(rid);
389 }
390 vector<revision_id> sorted;
391 toposort(revs, sorted, app);
392 vector<revision_id> curr_row;
393 reverse(sorted.begin(), sorted.end());
394 for (vector<revision_id>::const_iterator rev = sorted.begin();
395 rev != sorted.end(); ++rev)
396 {
397 set<revision_id> parents;
398 app.db.get_revision_parents(*rev, parents);
399 parents.erase(ghost); // remove the fake parent that root nodes have
400 graph.print(*rev, parents, rev->inner()());
401 }
402}

Archive Download this file

Branches

Tags

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