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

Archive Download this file

Branches

Tags

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