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

Archive Download this file

Branches

Tags

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