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 "base.hh"
110#include <algorithm>
111#include <iostream>
112#include <iterator>
113
114#include "asciik.hh"
115#include "simplestring_xform.hh"
116#include "cmd.hh"
117#include "app_state.hh"
118
119using std::insert_iterator;
120using std::max;
121using std::min;
122using std::ostream;
123using std::ostream_iterator;
124using std::pair;
125using std::set;
126using std::string;
127using std::vector;
128using std::find;
129using std::reverse;
130using std::distance;
131
132static revision_id ghost; // valid but empty revision_id to be used as ghost value
133
134asciik::asciik(ostream & os, size_t min_width)
135 : width(min_width), output(os)
136{
137}
138
139void
140asciik::links_cross(set<pair<size_t, size_t> > const & links,
141 set<size_t> & crosses) const
142{
143 for (set<pair<size_t, size_t> >::const_iterator link = links.begin();
144 link != links.end(); ++link)
145 {
146 size_t i = link->first, j = link->second;
147 if (i != j)
148 for (size_t coord = 2 * min(i, j) + 1, end = 2 * max(i, j);
149 coord < end; ++coord)
150 crosses.insert(coord);
151 }
152}
153
154void
155asciik::draw(size_t const curr_items,
156 size_t const next_items,
157 size_t const curr_loc,
158 set<pair<size_t, size_t> > const & links,
159 set<size_t> const & curr_ghosts,
160 string const & annotation) const
161{
162 size_t line_len = max(width, max(curr_items, next_items) * 2);
163 string line(line_len, ' '); // actual len: curr_items * 2 - 1
164 string interline(line_len, ' '); // actual len: max(curr_items, next_items) * 2 - 1
165 string interline2(line_len, ' ');
166
167 // first draw the flow-through bars in the line
168 for (size_t i = 0; i < curr_items; ++i)
169 line[i * 2] = '|';
170
171 // but then erase it for ghosts
172 for (set<size_t>::const_iterator i = curr_ghosts.begin();
173 i != curr_ghosts.end(); ++i)
174 line[(*i) * 2] = ' ';
175
176 // then the links
177 set<size_t> dots;
178 for (set<pair<size_t, size_t> >::const_iterator link = links.begin();
179 link != links.end(); ++link)
180 {
181 size_t i = link->first;
182 size_t j = link->second;
183 if (i == j)
184 interline[2 * i] = '|';
185 else
186 {
187 size_t start, end, dot;
188 if (j < i)
189 {
190 // | .---o
191 // |/| | |
192 // 0 1 2 3
193 // j i
194 // 0123456
195 // s e
196 start = 2 * j + 3;
197 end = 2 * i;
198 dot = start - 1;
199 interline[dot - 1] = '/';
200 }
201 else // j > i
202 {
203 // o---.
204 // | | |\|
205 // 0 1 2 3
206 // i j
207 // 0123456
208 // s e
209 start = 2 * i + 1;
210 end = 2 * j - 2;
211 dot = end;
212 interline[dot + 1] = '\\';
213 }
214 if (end > start)
215 {
216 dots.insert(dot);
217 for (size_t l = start; l < end; ++l)
218 line[l] = '-';
219 }
220 }
221 // prepare the proper continuation line
222 interline2[j * 2] = '|';
223 }
224 // add any dots (must do this in a second pass, so that things still work if
225 // there are cases like:
226 // | .-----.-o
227 // |/| | |/|
228 // where we want to make sure that the second dot overwrites the first -.
229 for (set<size_t>::const_iterator dot = dots.begin();
230 dot != dots.end(); ++dot)
231 line[*dot] = '.';
232 // and add the main attraction (may overwrite a '.').
233 line[curr_loc * 2] = 'o';
234
235 // split a multi-line annotation
236 vector<string> lines;
237 split_into_lines(annotation, lines);
238 int num_lines = lines.size();
239 if (num_lines < 1)
240 lines.push_back(string(""));
241 if (num_lines < 2)
242 lines.push_back(string(""));
243 // ignore empty lines at the end
244 while ((num_lines > 2) && (lines[num_lines - 1].size() == 0))
245 --num_lines;
246
247 // prints it out
248 //TODO convert line/interline/interline2 from ASCII to system charset
249 output << line << " " << lines[0] << '\n';
250 output << interline << " " << lines[1] << '\n';
251 for (int i = 2; i < num_lines; ++i)
252 output << interline2 << " " << lines[i] << '\n';
253}
254
255bool
256asciik::try_draw(vector<revision_id> const & next_row,
257 size_t const curr_loc,
258 set<revision_id> const & parents,
259 string const & annotation) const
260{
261 size_t curr_items = curr_row.size();
262 size_t next_items = next_row.size();
263 I(curr_loc < curr_items);
264
265 set<size_t> curr_ghosts;
266 for (size_t i = 0; i < curr_items; ++i)
267 if (idx(curr_row, i) == ghost)
268 curr_ghosts.insert(i);
269
270 set<pair<size_t, size_t> > preservation_links;
271 bool have_shift = false;
272 for (size_t i = 0; i < curr_items; ++i)
273 {
274 if (idx(curr_row, i) != ghost)
275 {
276 vector<revision_id>::const_iterator found =
277 find(next_row.begin(), next_row.end(), idx(curr_row, i));
278 if (found != next_row.end())
279 {
280 size_t j = distance(next_row.begin(), found);
281 size_t d = i>j ? i-j : j-i;
282 if (d > 1)
283 return false;
284 if (d != 0)
285 have_shift = true;
286 preservation_links.insert(pair<size_t, size_t>(i, j));
287 }
288 }
289 }
290
291 set<pair<size_t, size_t> > parent_links;
292 for (set<revision_id>::const_iterator p = parents.begin();
293 p != parents.end(); ++p)
294 if (*p != ghost)
295 {
296 size_t i = curr_loc;
297 size_t j = distance(next_row.begin(),
298 find(next_row.begin(), next_row.end(), *p));
299 I(j < next_items);
300 size_t d = i>j ? i-j : j-i;
301 if ((d > 1) && have_shift)
302 return false;
303 parent_links.insert(pair<size_t, size_t>(i, j));
304 }
305
306 set<size_t> preservation_crosses, parent_crosses, intersection_crosses;
307 links_cross(preservation_links, preservation_crosses);
308 links_cross(parent_links, parent_crosses);
309 set_intersection(
310 preservation_crosses.begin(), preservation_crosses.end(),
311 parent_crosses.begin(), parent_crosses.end(),
312 insert_iterator<set<size_t> >(intersection_crosses, intersection_crosses.begin()));
313 if (intersection_crosses.size() > 0)
314 return false;
315
316 set<pair<size_t, size_t> > links(preservation_links);
317 copy(parent_links.begin(), parent_links.end(),
318 insert_iterator<set<pair<size_t, size_t> > >(links, links.begin()));
319 draw(curr_items, next_items, curr_loc, links, curr_ghosts, annotation);
320 return true;
321}
322
323void
324asciik::print(revision_id const & rev,
325 set<revision_id> const & parents,
326 string const & annotation)
327{
328 if (find(curr_row.begin(), curr_row.end(), rev) == curr_row.end())
329 curr_row.push_back(rev);
330 size_t curr_loc = distance(curr_row.begin(),
331 find(curr_row.begin(), curr_row.end(), rev));
332 // it must be found as either it was there already or we just added it
333 I(curr_loc < curr_row.size());
334
335 set<revision_id> new_revs;
336 for (set<revision_id>::const_iterator parent = parents.begin();
337 parent != parents.end(); ++parent)
338 if (find(curr_row.begin(), curr_row.end(), *parent) == curr_row.end())
339 new_revs.insert(*parent);
340
341 vector<revision_id> next_row(curr_row);
342 I(curr_loc < next_row.size());
343 next_row.insert(
344 next_row.erase(next_row.begin() + curr_loc),
345 new_revs.begin(), new_revs.end());
346
347 // now next_row contains exactly the revisions it needs to, except that no
348 // ghost handling has been done.
349 vector<revision_id> no_ghost(next_row);
350 vector<revision_id>::iterator first_ghost = find(no_ghost.begin(),
351 no_ghost.end(), ghost);
352 if (first_ghost != no_ghost.end())
353 no_ghost.erase(first_ghost);
354
355 if (try_draw(no_ghost, curr_loc, parents, annotation))
356 curr_row = no_ghost;
357 else if (try_draw(next_row, curr_loc, parents, annotation))
358 curr_row = next_row;
359 else if (new_revs.size() == 0) // this line has disappeared
360 {
361 vector<revision_id> extra_ghost(next_row);
362 I(curr_loc < extra_ghost.size());
363 extra_ghost.insert(extra_ghost.begin() + curr_loc, ghost);
364 I(try_draw(extra_ghost, curr_loc, parents, annotation));
365 curr_row = extra_ghost;
366 }
367}
368
369CMD(asciik, "asciik", "", CMD_REF(debug), N_("SELECTOR"),
370 N_("Prints an ASCII representation of the revisions' graph"),
371 "",
372 options::opts::none)
373{
374 N(args.size() == 1,
375 F("wrong argument count"));
376
377 vector<pair<selectors::selector_type, string> >
378 sels(selectors::parse_selector(args[0](), app));
379
380 // we jam through an "empty" selection on sel_ident type
381 set<string> completions;
382 //set<hexenc<id>> completions;
383 selectors::selector_type ty = selectors::sel_ident;
384 selectors::complete_selector("", sels, ty, completions, app);
385
386 asciik graph(std::cout, 10);
387 set<revision_id> revs;
388 for (set<string>::const_iterator i = completions.begin();
389 i != completions.end(); ++i)
390 {
391 revision_id rid(*i);
392 revs.insert(rid);
393 }
394 vector<revision_id> sorted;
395 toposort(revs, sorted, app);
396 vector<revision_id> curr_row;
397 reverse(sorted.begin(), sorted.end());
398 for (vector<revision_id>::const_iterator rev = sorted.begin();
399 rev != sorted.end(); ++rev)
400 {
401 set<revision_id> parents;
402 app.db.get_revision_parents(*rev, parents);
403 parents.erase(ghost); // remove the fake parent that root nodes have
404 graph.print(*rev, parents, rev->inner()());
405 }
406}

Archive Download this file

Branches

Tags

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