monotone

monotone Mtn Source Tree

Root/revision.cc

1// Copyright (C) 2004 Graydon Hoare <graydon@pobox.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include <cctype>
11#include <cstdlib>
12#include <iostream>
13#include <map>
14#include <queue>
15#include <set>
16#include <sstream>
17#include <stack>
18#include <string>
19#include <iterator>
20#include <functional>
21#include <list>
22
23#include <boost/lexical_cast.hpp>
24#include <boost/dynamic_bitset.hpp>
25#include <boost/shared_ptr.hpp>
26
27#include "botan/botan.h"
28
29#include "app_state.hh"
30#include "basic_io.hh"
31#include "cert.hh"
32#include "cset.hh"
33#include "constants.hh"
34#include "interner.hh"
35#include "keys.hh"
36#include "numeric_vocab.hh"
37#include "revision.hh"
38#include "sanity.hh"
39#include "transforms.hh"
40#include "simplestring_xform.hh"
41#include "ui.hh"
42#include "vocab.hh"
43#include "safe_map.hh"
44#include "legacy.hh"
45
46using std::back_inserter;
47using std::copy;
48using std::deque;
49using std::list;
50using std::make_pair;
51using std::map;
52using std::max;
53using std::multimap;
54using std::ostringstream;
55using std::pair;
56using std::queue;
57using std::set;
58using std::stack;
59using std::string;
60using std::vector;
61
62using boost::dynamic_bitset;
63using boost::shared_ptr;
64
65void revision_t::check_sane() const
66{
67 // null id in current manifest only permitted if previous
68 // state was null and no changes
69 if (null_id(new_manifest))
70 {
71 for (edge_map::const_iterator i = edges.begin();
72 i != edges.end(); ++i)
73 I(null_id(edge_old_revision(i)));
74 }
75
76 if (edges.size() == 1)
77 {
78 // no particular checks to be done right now
79 }
80 else if (edges.size() == 2)
81 {
82 // merge nodes cannot have null revisions
83 for (edge_map::const_iterator i = edges.begin(); i != edges.end(); ++i)
84 I(!null_id(edge_old_revision(i)));
85 }
86 else
87 // revisions must always have either 1 or 2 edges
88 I(false);
89
90 // we used to also check that if there were multiple edges that had patches
91 // for the same file, then the new hashes on each edge matched each other.
92 // this is not ported over to roster-style revisions because it's an
93 // inadequate check, and the real check, that the new manifest id is correct
94 // (done in put_revision, for instance) covers this case automatically.
95}
96
97bool
98revision_t::is_merge_node() const
99{
100 return edges.size() > 1;
101}
102
103bool
104revision_t::is_nontrivial() const
105{
106 check_sane();
107 // merge revisions are never trivial, because even if the resulting node
108 // happens to be identical to both parents, the merge is still recording
109 // that fact.
110 if (is_merge_node())
111 return true;
112 else
113 return !edge_changes(edges.begin()).empty();
114}
115
116revision_t::revision_t(revision_t const & other)
117{
118 /* behave like normal constructor if other is empty */
119 if (null_id(other.new_manifest) && other.edges.empty()) return;
120 other.check_sane();
121 new_manifest = other.new_manifest;
122 edges = other.edges;
123}
124
125revision_t const &
126revision_t::operator=(revision_t const & other)
127{
128 other.check_sane();
129 new_manifest = other.new_manifest;
130 edges = other.edges;
131 return *this;
132}
133
134
135// For a surprisingly long time, we have been using an algorithm which
136// is nonsense, based on a misunderstanding of what "LCA" means. The
137// LCA of two nodes is *not* the first common ancestor which you find
138// when iteratively expanding their ancestor sets. Instead, the LCA is
139// the common ancestor which is a descendent of all other common
140// ancestors.
141//
142// In general, a set of nodes in a DAG doesn't always have an
143// LCA. There might be multiple common ancestors which are not parents
144// of one another. So we implement something which is "functionally
145// useful" for finding a merge point (and moreover, which always
146// terminates): we find an LCA of the input set if it exists,
147// otherwise we replace the input set with the nodes we did find and
148// repeat.
149//
150// All previous discussions in monotone-land, before say August 2005,
151// of LCA (and LCAD) are essentially wrong due to our silly
152// misunderstanding. It's unfortunate, but our half-baked
153// approximations worked almost well enough to take us through 3 years
154// of deployed use. Hopefully this more accurate new use will serve us
155// even longer.
156
157typedef unsigned long ctx;
158typedef dynamic_bitset<> bitmap;
159typedef shared_ptr<bitmap> shared_bitmap;
160
161static void
162calculate_ancestors_from_graph(interner<ctx> & intern,
163 revision_id const & init,
164 multimap<revision_id, revision_id> const & graph,
165 map< ctx, shared_bitmap > & ancestors,
166 shared_bitmap & total_union);
167
168void
169find_common_ancestor_for_merge(revision_id const & left,
170 revision_id const & right,
171 revision_id & anc,
172 app_state & app)
173{
174 interner<ctx> intern;
175 set<ctx> leaves;
176 map<ctx, shared_bitmap> ancestors;
177
178 shared_bitmap isect = shared_bitmap(new bitmap());
179 shared_bitmap isect_ancs = shared_bitmap(new bitmap());
180
181 leaves.insert(intern.intern(left.inner()()));
182 leaves.insert(intern.intern(right.inner()()));
183
184
185 multimap<revision_id, revision_id> inverse_graph;
186 {
187 multimap<revision_id, revision_id> graph;
188 app.db.get_revision_ancestry(graph);
189 typedef multimap<revision_id, revision_id>::const_iterator gi;
190 for (gi i = graph.begin(); i != graph.end(); ++i)
191 inverse_graph.insert(make_pair(i->second, i->first));
192 }
193
194
195 while (leaves.size() != 1)
196 {
197 isect->clear();
198 isect_ancs->clear();
199
200 // First intersect all ancestors of current leaf set
201 for (set<ctx>::const_iterator i = leaves.begin(); i != leaves.end(); ++i)
202 {
203 ctx curr_leaf = *i;
204 shared_bitmap curr_leaf_ancestors;
205 map<ctx, shared_bitmap >::const_iterator j = ancestors.find(*i);
206 if (j != ancestors.end())
207 curr_leaf_ancestors = j->second;
208 else
209 {
210 curr_leaf_ancestors = shared_bitmap(new bitmap());
211 calculate_ancestors_from_graph(intern, revision_id(intern.lookup(curr_leaf)),
212 inverse_graph, ancestors,
213 curr_leaf_ancestors);
214 }
215 if (isect->size() > curr_leaf_ancestors->size())
216 curr_leaf_ancestors->resize(isect->size());
217
218 if (curr_leaf_ancestors->size() > isect->size())
219 isect->resize(curr_leaf_ancestors->size());
220
221 if (i == leaves.begin())
222 *isect = *curr_leaf_ancestors;
223 else
224 (*isect) &= (*curr_leaf_ancestors);
225 }
226
227 // isect is now the set of common ancestors of leaves, but that is not enough.
228 // We need the set of leaves of isect; to do that we calculate the set of
229 // ancestors of isect, in order to subtract it from isect (below).
230 set<ctx> new_leaves;
231 for (ctx i = 0; i < isect->size(); ++i)
232 {
233 if (isect->test(i))
234 {
235 calculate_ancestors_from_graph(intern, revision_id(intern.lookup(i)),
236 inverse_graph, ancestors, isect_ancs);
237 }
238 }
239
240 // Finally, the subtraction step: for any element i of isect, if
241 // it's *not* in isect_ancs, it survives as a new leaf.
242 leaves.clear();
243 for (ctx i = 0; i < isect->size(); ++i)
244 {
245 if (!isect->test(i))
246 continue;
247 if (i < isect_ancs->size() && isect_ancs->test(i))
248 continue;
249 safe_insert(leaves, i);
250 }
251 }
252
253 I(leaves.size() == 1);
254 anc = revision_id(intern.lookup(*leaves.begin()));
255}
256
257// FIXME: this algorithm is incredibly inefficient; it's O(n) where n is the
258// size of the entire revision graph.
259
260template<typename T> static bool
261is_ancestor(T const & ancestor_id,
262 T const & descendent_id,
263 multimap<T, T> const & graph)
264{
265
266 set<T> visited;
267 queue<T> queue;
268
269 queue.push(ancestor_id);
270
271 while (!queue.empty())
272 {
273 T current_id = queue.front();
274 queue.pop();
275
276 if (current_id == descendent_id)
277 return true;
278 else
279 {
280 typedef typename multimap<T, T>::const_iterator gi;
281 pair<gi, gi> children = graph.equal_range(current_id);
282 for (gi i = children.first; i != children.second; ++i)
283 {
284 if (visited.find(i->second) == visited.end())
285 {
286 queue.push(i->second);
287 visited.insert(i->second);
288 }
289 }
290 }
291 }
292 return false;
293}
294
295bool
296is_ancestor(revision_id const & ancestor_id,
297 revision_id const & descendent_id,
298 app_state & app)
299{
300 L(FL("checking whether %s is an ancestor of %s") % ancestor_id % descendent_id);
301
302 multimap<revision_id, revision_id> graph;
303 app.db.get_revision_ancestry(graph);
304 return is_ancestor(ancestor_id, descendent_id, graph);
305}
306
307
308static void
309add_bitset_to_union(shared_bitmap src,
310 shared_bitmap dst)
311{
312 if (dst->size() > src->size())
313 src->resize(dst->size());
314 if (src->size() > dst->size())
315 dst->resize(src->size());
316 *dst |= *src;
317}
318
319
320static void
321calculate_ancestors_from_graph(interner<ctx> & intern,
322 revision_id const & init,
323 multimap<revision_id, revision_id> const & graph,
324 map< ctx, shared_bitmap > & ancestors,
325 shared_bitmap & total_union)
326{
327 typedef multimap<revision_id, revision_id>::const_iterator gi;
328 stack<ctx> stk;
329
330 stk.push(intern.intern(init.inner()()));
331
332 while (! stk.empty())
333 {
334 ctx us = stk.top();
335 revision_id rev(hexenc<id>(intern.lookup(us)));
336
337 pair<gi,gi> parents = graph.equal_range(rev);
338 bool pushed = false;
339
340 // first make sure all parents are done
341 for (gi i = parents.first; i != parents.second; ++i)
342 {
343 ctx parent = intern.intern(i->second.inner()());
344 if (ancestors.find(parent) == ancestors.end())
345 {
346 stk.push(parent);
347 pushed = true;
348 break;
349 }
350 }
351
352 // if we pushed anything we stop now. we'll come back later when all
353 // the parents are done.
354 if (pushed)
355 continue;
356
357 shared_bitmap b = shared_bitmap(new bitmap());
358
359 for (gi i = parents.first; i != parents.second; ++i)
360 {
361 ctx parent = intern.intern(i->second.inner()());
362
363 // set all parents
364 if (b->size() <= parent)
365 b->resize(parent + 1);
366 b->set(parent);
367
368 // ensure all parents are loaded into the ancestor map
369 I(ancestors.find(parent) != ancestors.end());
370
371 // union them into our map
372 map< ctx, shared_bitmap >::const_iterator j = ancestors.find(parent);
373 I(j != ancestors.end());
374 add_bitset_to_union(j->second, b);
375 }
376
377 add_bitset_to_union(b, total_union);
378 ancestors.insert(make_pair(us, b));
379 stk.pop();
380 }
381}
382
383// this function actually toposorts the whole graph, and then filters by the
384// passed in set. if anyone ever needs to toposort the whole graph, then,
385// this function would be a good thing to generalize...
386void
387toposort(set<revision_id> const & revisions,
388 vector<revision_id> & sorted,
389 app_state & app)
390{
391 sorted.clear();
392 typedef multimap<revision_id, revision_id>::iterator gi;
393 typedef map<revision_id, int>::iterator pi;
394 multimap<revision_id, revision_id> graph;
395 app.db.get_revision_ancestry(graph);
396 set<revision_id> leaves;
397 app.db.get_revision_ids(leaves);
398 map<revision_id, int> pcount;
399 for (gi i = graph.begin(); i != graph.end(); ++i)
400 pcount.insert(make_pair(i->first, 0));
401 for (gi i = graph.begin(); i != graph.end(); ++i)
402 ++(pcount[i->second]);
403 // first find the set of graph roots
404 list<revision_id> roots;
405 for (pi i = pcount.begin(); i != pcount.end(); ++i)
406 if(i->second==0)
407 roots.push_back(i->first);
408 while (!roots.empty())
409 {
410 // now stick them in our ordering (if wanted) and remove them from the
411 // graph, calculating the new roots as we go
412 L(FL("new root: %s") % (roots.front()));
413 if (revisions.find(roots.front()) != revisions.end())
414 sorted.push_back(roots.front());
415 for(gi i = graph.lower_bound(roots.front());
416 i != graph.upper_bound(roots.front()); i++)
417 if(--(pcount[i->second]) == 0)
418 roots.push_back(i->second);
419 graph.erase(roots.front());
420 leaves.erase(roots.front());
421 roots.pop_front();
422 }
423 I(graph.empty());
424 for (set<revision_id>::const_iterator i = leaves.begin();
425 i != leaves.end(); ++i)
426 {
427 L(FL("new leaf: %s") % (*i));
428 if (revisions.find(*i) != revisions.end())
429 sorted.push_back(*i);
430 }
431}
432
433// This function looks at a set of revisions, and for every pair A, B in that
434// set such that A is an ancestor of B, it erases A.
435
436void
437erase_ancestors(set<revision_id> & revisions, app_state & app)
438{
439 typedef multimap<revision_id, revision_id>::const_iterator gi;
440 multimap<revision_id, revision_id> graph;
441 multimap<revision_id, revision_id> inverse_graph;
442
443 app.db.get_revision_ancestry(graph);
444 for (gi i = graph.begin(); i != graph.end(); ++i)
445 inverse_graph.insert(make_pair(i->second, i->first));
446
447 interner<ctx> intern;
448 map< ctx, shared_bitmap > ancestors;
449
450 shared_bitmap u = shared_bitmap(new bitmap());
451
452 for (set<revision_id>::const_iterator i = revisions.begin();
453 i != revisions.end(); ++i)
454 {
455 calculate_ancestors_from_graph(intern, *i, inverse_graph, ancestors, u);
456 }
457
458 set<revision_id> tmp;
459 for (set<revision_id>::const_iterator i = revisions.begin();
460 i != revisions.end(); ++i)
461 {
462 ctx id = intern.intern(i->inner()());
463 bool has_ancestor_in_set = id < u->size() && u->test(id);
464 if (!has_ancestor_in_set)
465 tmp.insert(*i);
466 }
467
468 revisions = tmp;
469}
470
471// This function takes a revision A and a set of revision Bs, calculates the
472// ancestry of each, and returns the set of revisions that are in A's ancestry
473// but not in the ancestry of any of the Bs. It tells you 'what's new' in A
474// that's not in the Bs. If the output set if non-empty, then A will
475// certainly be in it; but the output set might be empty.
476void
477ancestry_difference(revision_id const & a, set<revision_id> const & bs,
478 set<revision_id> & new_stuff,
479 app_state & app)
480{
481 new_stuff.clear();
482 typedef multimap<revision_id, revision_id>::const_iterator gi;
483 multimap<revision_id, revision_id> graph;
484 multimap<revision_id, revision_id> inverse_graph;
485
486 app.db.get_revision_ancestry(graph);
487 for (gi i = graph.begin(); i != graph.end(); ++i)
488 inverse_graph.insert(make_pair(i->second, i->first));
489
490 interner<ctx> intern;
491 map< ctx, shared_bitmap > ancestors;
492
493 shared_bitmap u = shared_bitmap(new bitmap());
494
495 for (set<revision_id>::const_iterator i = bs.begin();
496 i != bs.end(); ++i)
497 {
498 calculate_ancestors_from_graph(intern, *i, inverse_graph, ancestors, u);
499 ctx c = intern.intern(i->inner()());
500 if (u->size() <= c)
501 u->resize(c + 1);
502 u->set(c);
503 }
504
505 shared_bitmap au = shared_bitmap(new bitmap());
506 calculate_ancestors_from_graph(intern, a, inverse_graph, ancestors, au);
507 {
508 ctx c = intern.intern(a.inner()());
509 if (au->size() <= c)
510 au->resize(c + 1);
511 au->set(c);
512 }
513
514 au->resize(max(au->size(), u->size()));
515 u->resize(max(au->size(), u->size()));
516
517 *au -= *u;
518
519 for (unsigned int i = 0; i != au->size(); ++i)
520 {
521 if (au->test(i))
522 {
523 revision_id rid(intern.lookup(i));
524 if (!null_id(rid))
525 new_stuff.insert(rid);
526 }
527 }
528}
529
530void
531select_nodes_modified_by_rev(revision_id const & rid,
532 revision_t const & rev,
533 roster_t const new_roster,
534 set<node_id> & nodes_modified,
535 app_state & app)
536{
537 nodes_modified.clear();
538
539 for (edge_map::const_iterator i = rev.edges.begin();
540 i != rev.edges.end(); ++i)
541 {
542 set<node_id> edge_nodes_modified;
543 roster_t old_roster;
544 app.db.get_roster(edge_old_revision(i), old_roster);
545 select_nodes_modified_by_cset(edge_changes(i),
546 old_roster,
547 new_roster,
548 edge_nodes_modified);
549
550 copy(edge_nodes_modified.begin(), edge_nodes_modified.end(),
551 inserter(nodes_modified, nodes_modified.begin()));
552 }
553}
554
555
556void
557make_revision(revision_id const & old_rev_id,
558 roster_t const & old_roster,
559 roster_t const & new_roster,
560 revision_t & rev)
561{
562 shared_ptr<cset> cs(new cset());
563
564 rev.edges.clear();
565 make_cset(old_roster, new_roster, *cs);
566
567 calculate_ident(new_roster, rev.new_manifest);
568 L(FL("new manifest_id is %s") % rev.new_manifest);
569
570 safe_insert(rev.edges, make_pair(old_rev_id, cs));
571}
572
573
574// Stuff related to rebuilding the revision graph. Unfortunately this is a
575// real enough error case that we need support code for it.
576
577typedef map<u64, pair<shared_ptr<roster_t>, shared_ptr<marking_map> > >
578parent_roster_map;
579
580template <> void
581dump(parent_roster_map const & prm, string & out)
582{
583 ostringstream oss;
584 for (parent_roster_map::const_iterator i = prm.begin(); i != prm.end(); ++i)
585 {
586 oss << "roster: " << i->first << "\n";
587 string roster_str, indented_roster_str;
588 dump(*i->second.first, roster_str);
589 prefix_lines_with(" ", roster_str, indented_roster_str);
590 oss << indented_roster_str;
591 oss << "\nroster's marking:\n";
592 string marking_str, indented_marking_str;
593 dump(*i->second.second, marking_str);
594 prefix_lines_with(" ", marking_str, indented_marking_str);
595 oss << indented_marking_str;
596 oss << "\n\n";
597 }
598 out = oss.str();
599}
600
601struct anc_graph
602{
603 anc_graph(bool existing, app_state & a) :
604 existing_graph(existing),
605 app(a),
606 max_node(0),
607 n_nodes("nodes", "n", 1),
608 n_certs_in("certs in", "c", 1),
609 n_revs_out("revs out", "r", 1),
610 n_certs_out("certs out", "C", 1)
611 {}
612
613 bool existing_graph;
614 app_state & app;
615 u64 max_node;
616
617 ticker n_nodes;
618 ticker n_certs_in;
619 ticker n_revs_out;
620 ticker n_certs_out;
621
622 map<u64,manifest_id> node_to_old_man;
623 map<manifest_id,u64> old_man_to_node;
624
625 map<u64,revision_id> node_to_old_rev;
626 map<revision_id,u64> old_rev_to_node;
627
628 map<u64,revision_id> node_to_new_rev;
629 map<revision_id,u64> new_rev_to_node;
630
631 map<u64, legacy::renames_map> node_to_renames;
632
633 multimap<u64, pair<cert_name, cert_value> > certs;
634 multimap<u64, u64> ancestry;
635 set<string> branches;
636
637 void add_node_ancestry(u64 child, u64 parent);
638 void write_certs();
639 void kluge_for_bogus_merge_edges();
640 void rebuild_ancestry();
641 void get_node_manifest(u64 node, manifest_id & man);
642 u64 add_node_for_old_manifest(manifest_id const & man);
643 u64 add_node_for_oldstyle_revision(revision_id const & rev);
644 void construct_revisions_from_ancestry();
645 void fixup_node_identities(parent_roster_map const & parent_rosters,
646 roster_t & child_roster,
647 legacy::renames_map const & renames);
648};
649
650
651void anc_graph::add_node_ancestry(u64 child, u64 parent)
652{
653 L(FL("noting ancestry from child %d -> parent %d") % child % parent);
654 ancestry.insert(make_pair(child, parent));
655}
656
657void anc_graph::get_node_manifest(u64 node, manifest_id & man)
658{
659 map<u64,manifest_id>::const_iterator i = node_to_old_man.find(node);
660 I(i != node_to_old_man.end());
661 man = i->second;
662}
663
664void anc_graph::write_certs()
665{
666 {
667 // regenerate epochs on all branches to random states
668
669 for (set<string>::const_iterator i = branches.begin(); i != branches.end(); ++i)
670 {
671 char buf[constants::epochlen_bytes];
672 Botan::Global_RNG::randomize(reinterpret_cast<Botan::byte *>(buf), constants::epochlen_bytes);
673 hexenc<data> hexdata;
674 encode_hexenc(data(string(buf, buf + constants::epochlen_bytes)), hexdata);
675 epoch_data new_epoch(hexdata);
676 L(FL("setting epoch for %s to %s") % *i % new_epoch);
677 app.db.set_epoch(cert_value(*i), new_epoch);
678 }
679 }
680
681
682 typedef multimap<u64, pair<cert_name, cert_value> >::const_iterator ci;
683
684 for (map<u64,revision_id>::const_iterator i = node_to_new_rev.begin();
685 i != node_to_new_rev.end(); ++i)
686 {
687 revision_id rev(i->second);
688
689 pair<ci,ci> range = certs.equal_range(i->first);
690
691 for (ci j = range.first; j != range.second; ++j)
692 {
693 cert_name name(j->second.first);
694 cert_value val(j->second.second);
695
696 cert new_cert;
697 make_simple_cert(rev.inner(), name, val, app, new_cert);
698 revision<cert> rcert(new_cert);
699 if (! app.db.revision_cert_exists(rcert))
700 {
701 ++n_certs_out;
702 app.db.put_revision_cert(rcert);
703 }
704 }
705 }
706}
707
708void
709anc_graph::kluge_for_bogus_merge_edges()
710{
711 // This kluge exists because in the 0.24-era monotone databases, several
712 // bad merges still existed in which one side of the merge is an ancestor
713 // of the other side of the merge. In other words, graphs which look like
714 // this:
715 //
716 // a ----------------------> e
717 // \ /
718 // \---> b -> c -> d ----/
719 //
720 // Such merges confuse the roster-building algorithm, because they should
721 // never have occurred in the first place: a was not a head at the time
722 // of the merge, e should simply have been considered an extension of d.
723 //
724 // So... we drop the a->e edges entirely.
725 //
726 // Note: this kluge drops edges which are a struct superset of those
727 // dropped by a previous kluge ("3-ancestor") so we have removed that
728 // code.
729
730 P(F("scanning for bogus merge edges"));
731
732 multimap<u64,u64> parent_to_child_map;
733 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
734 i != ancestry.end(); ++i)
735 parent_to_child_map.insert(make_pair(i->second, i->first));
736
737 map<u64, u64> edges_to_kill;
738 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
739 i != ancestry.end(); ++i)
740 {
741 multimap<u64, u64>::const_iterator j = i;
742 ++j;
743 u64 child = i->first;
744 // NB: ancestry is a multimap from child->parent(s)
745 if (j != ancestry.end())
746 {
747 if (j->first == i->first)
748 {
749 L(FL("considering old merge edge %s") %
750 safe_get(node_to_old_rev, i->first));
751 u64 parent1 = i->second;
752 u64 parent2 = j->second;
753 if (is_ancestor (parent1, parent2, parent_to_child_map))
754 safe_insert(edges_to_kill, make_pair(child, parent1));
755 else if (is_ancestor (parent2, parent1, parent_to_child_map))
756 safe_insert(edges_to_kill, make_pair(child, parent2));
757 }
758 }
759 }
760
761 for (map<u64, u64>::const_iterator i = edges_to_kill.begin();
762 i != edges_to_kill.end(); ++i)
763 {
764 u64 child = i->first;
765 u64 parent = i->second;
766 bool killed = false;
767 for (multimap<u64, u64>::iterator j = ancestry.lower_bound(child);
768 j->first == child; ++j)
769 {
770 if (j->second == parent)
771 {
772 P(F("optimizing out redundant edge %d -> %d")
773 % parent % child);
774 ancestry.erase(j);
775 killed = true;
776 break;
777 }
778 }
779
780 if (!killed)
781 W(F("failed to eliminate edge %d -> %d")
782 % parent % child);
783 }
784}
785
786
787void
788anc_graph::rebuild_ancestry()
789{
790 kluge_for_bogus_merge_edges();
791
792 P(F("rebuilding %d nodes") % max_node);
793 {
794 transaction_guard guard(app.db);
795 if (existing_graph)
796 app.db.delete_existing_revs_and_certs();
797 construct_revisions_from_ancestry();
798 write_certs();
799 if (existing_graph)
800 app.db.delete_existing_manifests();
801 guard.commit();
802 }
803}
804
805u64
806anc_graph::add_node_for_old_manifest(manifest_id const & man)
807{
808 I(!existing_graph);
809 u64 node = 0;
810 if (old_man_to_node.find(man) == old_man_to_node.end())
811 {
812 node = max_node++;
813 ++n_nodes;
814 L(FL("node %d = manifest %s") % node % man);
815 old_man_to_node.insert(make_pair(man, node));
816 node_to_old_man.insert(make_pair(node, man));
817
818 // load certs
819 vector< manifest<cert> > mcerts;
820 app.db.get_manifest_certs(man, mcerts);
821 erase_bogus_certs(mcerts, app);
822 for(vector< manifest<cert> >::const_iterator i = mcerts.begin();
823 i != mcerts.end(); ++i)
824 {
825 L(FL("loaded '%s' manifest cert for node %s") % i->inner().name % node);
826 cert_value tv;
827 decode_base64(i->inner().value, tv);
828 ++n_certs_in;
829 certs.insert(make_pair(node,
830 make_pair(i->inner().name, tv)));
831 }
832 }
833 else
834 {
835 node = old_man_to_node[man];
836 }
837 return node;
838}
839
840u64 anc_graph::add_node_for_oldstyle_revision(revision_id const & rev)
841{
842 I(existing_graph);
843 I(!null_id(rev));
844 u64 node = 0;
845 if (old_rev_to_node.find(rev) == old_rev_to_node.end())
846 {
847 node = max_node++;
848 ++n_nodes;
849
850 manifest_id man;
851 legacy::renames_map renames;
852 legacy::get_manifest_and_renames_for_rev(app, rev, man, renames);
853
854 L(FL("node %d = revision %s = manifest %s") % node % rev % man);
855 old_rev_to_node.insert(make_pair(rev, node));
856 node_to_old_rev.insert(make_pair(node, rev));
857 node_to_old_man.insert(make_pair(node, man));
858 node_to_renames.insert(make_pair(node, renames));
859
860 // load certs
861 vector< revision<cert> > rcerts;
862 app.db.get_revision_certs(rev, rcerts);
863 erase_bogus_certs(rcerts, app);
864 for(vector< revision<cert> >::const_iterator i = rcerts.begin();
865 i != rcerts.end(); ++i)
866 {
867 L(FL("loaded '%s' revision cert for node %s") % i->inner().name % node);
868 cert_value tv;
869 decode_base64(i->inner().value, tv);
870 ++n_certs_in;
871 certs.insert(make_pair(node,
872 make_pair(i->inner().name, tv)));
873
874 if (i->inner().name == branch_cert_name)
875 branches.insert(tv());
876 }
877 }
878 else
879 {
880 node = old_rev_to_node[rev];
881 }
882
883 return node;
884}
885
886static bool
887not_dead_yet(node_id nid, u64 birth_rev,
888 parent_roster_map const & parent_rosters,
889 multimap<u64, u64> const & child_to_parents)
890{
891 // Any given node, at each point in the revision graph, is in one of the
892 // states "alive", "unborn", "dead". The invariant we must maintain in
893 // constructing our revision graph is that if a node is dead in any parent,
894 // then it must also be dead in the child. The purpose of this function is
895 // to take a node, and a list of parents, and determine whether that node is
896 // allowed to be alive in a child of the given parents.
897
898 // "Alive" means, the node currently exists in the revision's tree.
899 // "Unborn" means, the node does not exist in the revision's tree, and the
900 // node's birth revision is _not_ an ancestor of the revision.
901 // "Dead" means, the node does not exist in the revision's tree, and the
902 // node's birth revision _is_ an ancestor of the revision.
903
904 // L(FL("testing liveliness of node %d, born in rev %d") % nid % birth_rev);
905 for (parent_roster_map::const_iterator r = parent_rosters.begin();
906 r != parent_rosters.end(); ++r)
907 {
908 shared_ptr<roster_t> parent = r->second.first;
909 // L(FL("node %d %s in parent roster %d")
910 // % nid
911 // % (parent->has_node(n->first) ? "exists" : "does not exist" )
912 // % r->first);
913
914 if (!parent->has_node(nid))
915 {
916 deque<u64> work;
917 set<u64> seen;
918 work.push_back(r->first);
919 while (!work.empty())
920 {
921 u64 curr = work.front();
922 work.pop_front();
923 // L(FL("examining ancestor %d of parent roster %d, looking for anc=%d")
924 // % curr % r->first % birth_rev);
925
926 if (seen.find(curr) != seen.end())
927 continue;
928 seen.insert(curr);
929
930 if (curr == birth_rev)
931 {
932 // L(FL("node is dead in %d") % r->first);
933 return false;
934 }
935 typedef multimap<u64, u64>::const_iterator ci;
936 pair<ci,ci> range = child_to_parents.equal_range(curr);
937 for (ci i = range.first; i != range.second; ++i)
938 {
939 if (i->first != curr)
940 continue;
941 work.push_back(i->second);
942 }
943 }
944 }
945 }
946 // L(FL("node is alive in all parents, returning true"));
947 return true;
948}
949
950
951static split_path
952find_old_path_for(map<split_path, split_path> const & renames,
953 split_path const & new_path)
954{
955 split_path leader, trailer;
956 leader = new_path;
957 while (!leader.empty())
958 {
959 if (renames.find(leader) != renames.end())
960 {
961 leader = safe_get(renames, leader);
962 break;
963 }
964 path_component pc = leader.back();
965 leader.pop_back();
966 trailer.insert(trailer.begin(), pc);
967 }
968 split_path result;
969 copy(leader.begin(), leader.end(), back_inserter(result));
970 copy(trailer.begin(), trailer.end(), back_inserter(result));
971 return result;
972}
973
974static split_path
975find_new_path_for(map<split_path, split_path> const & renames,
976 split_path const & old_path)
977{
978 map<split_path, split_path> reversed;
979 for (map<split_path, split_path>::const_iterator i = renames.begin();
980 i != renames.end(); ++i)
981 reversed.insert(make_pair(i->second, i->first));
982 // this is a hackish kluge. seems to work, though.
983 return find_old_path_for(reversed, old_path);
984}
985
986static void
987insert_into_roster(roster_t & child_roster,
988 temp_node_id_source & nis,
989 file_path const & pth,
990 file_id const & fid)
991{
992 split_path sp, dirname;
993 path_component basename;
994 pth.split(sp);
995
996 E(!child_roster.has_node(sp),
997 F("Path %s added to child roster multiple times\n") % pth);
998
999 dirname_basename(sp, dirname, basename);
1000
1001 {
1002 split_path tmp_pth;
1003 for (split_path::const_iterator i = dirname.begin(); i != dirname.end();
1004 ++i)
1005 {
1006 tmp_pth.push_back(*i);
1007 if (child_roster.has_node(tmp_pth))
1008 {
1009 E(is_dir_t(child_roster.get_node(tmp_pth)),
1010 F("Directory for path %s cannot be added, as there is a file in the way\n") % pth);
1011 }
1012 else
1013 child_roster.attach_node(child_roster.create_dir_node(nis), tmp_pth);
1014 }
1015 }
1016
1017 if (child_roster.has_node(sp))
1018 {
1019 node_t n = child_roster.get_node(sp);
1020 E(is_file_t(n),
1021 F("Path %s cannot be added, as there is a directory in the way") % sp);
1022 file_t f = downcast_to_file_t(n);
1023 E(f->content == fid,
1024 F("Path %s added twice with differing content\n") % sp);
1025 }
1026 else
1027 child_roster.attach_node(child_roster.create_file_node(fid, nis), sp);
1028}
1029
1030void
1031anc_graph::fixup_node_identities(parent_roster_map const & parent_rosters,
1032 roster_t & child_roster,
1033 legacy::renames_map const & renames)
1034{
1035 // Our strategy here is to iterate over every node in every parent, and
1036 // for each parent node P find zero or one tmp nodes in the child which
1037 // represents the fate of P:
1038 //
1039 // - If any of the parents thinks that P has died, we do not search for
1040 // it in the child; we leave it as "dropped".
1041 //
1042 // - We fetch the name N of the parent node P, and apply the rename map
1043 // to N, getting "remapped name" M. If we find a child node C with
1044 // name M in the child roster, with the same type as P, we identify P
1045 // and C, and swap P for C in the child.
1046
1047
1048 // Map node_id -> birth rev
1049 map<node_id, u64> nodes_in_any_parent;
1050
1051 // Stage 1: collect all nodes (and their birth revs) in any parent.
1052 for (parent_roster_map::const_iterator i = parent_rosters.begin();
1053 i != parent_rosters.end(); ++i)
1054 {
1055 shared_ptr<roster_t> parent_roster = i->second.first;
1056 shared_ptr<marking_map> parent_marking = i->second.second;
1057
1058 node_map const & nodes = parent_roster->all_nodes();
1059 for (node_map::const_iterator j = nodes.begin(); j != nodes.end(); ++j)
1060 {
1061 node_id n = j->first;
1062 revision_id birth_rev = safe_get(*parent_marking, n).birth_revision;
1063 u64 birth_node = safe_get(new_rev_to_node, birth_rev);
1064 map<node_id, u64>::const_iterator i = nodes_in_any_parent.find(n);
1065 if (i != nodes_in_any_parent.end())
1066 I(i->second == birth_node);
1067 else
1068 safe_insert(nodes_in_any_parent,
1069 make_pair(n, birth_node));
1070 }
1071 }
1072
1073 // Stage 2: For any node which is actually live, try to locate a mapping
1074 // from a parent instance of it to a child node.
1075 for (map<node_id, u64>::const_iterator i = nodes_in_any_parent.begin();
1076 i != nodes_in_any_parent.end(); ++i)
1077 {
1078 node_id n = i->first;
1079 u64 birth_rev = i->second;
1080
1081 if (child_roster.has_node(n))
1082 continue;
1083
1084 if (not_dead_yet(n, birth_rev, parent_rosters, ancestry))
1085 {
1086 for (parent_roster_map::const_iterator j = parent_rosters.begin();
1087 j != parent_rosters.end(); ++j)
1088 {
1089 shared_ptr<roster_t> parent_roster = j->second.first;
1090
1091 if (!parent_roster->has_node(n))
1092 continue;
1093
1094 split_path sp;
1095 parent_roster->get_name(n, sp);
1096
1097 // Try remapping the name.
1098 if (node_to_old_rev.find(j->first) != node_to_old_rev.end())
1099 {
1100 legacy::renames_map::const_iterator rmap;
1101 revision_id parent_rid = safe_get(node_to_old_rev, j->first);
1102 rmap = renames.find(parent_rid);
1103 if (rmap != renames.end())
1104 sp = find_new_path_for(rmap->second, sp);
1105 }
1106
1107 // See if we can match this node against a child.
1108 if ((!child_roster.has_node(n))
1109 && child_roster.has_node(sp))
1110 {
1111 node_t pn = parent_roster->get_node(n);
1112 node_t cn = child_roster.get_node(sp);
1113 if (is_file_t(pn) == is_file_t(cn))
1114 {
1115 child_roster.replace_node_id(cn->self, n);
1116 break;
1117 }
1118 }
1119 }
1120 }
1121 }
1122}
1123
1124struct
1125current_rev_debugger
1126{
1127 u64 node;
1128 anc_graph const & agraph;
1129 current_rev_debugger(u64 n, anc_graph const & ag)
1130 : node(n), agraph(ag)
1131 {
1132 }
1133};
1134
1135template <> void
1136dump(current_rev_debugger const & d, string & out)
1137{
1138 typedef multimap<u64, pair<cert_name, cert_value> >::const_iterator ci;
1139 pair<ci,ci> range = d.agraph.certs.equal_range(d.node);
1140 for(ci i = range.first; i != range.second; ++i)
1141 {
1142 if (i->first == d.node)
1143 {
1144 out += "cert '" + i->second.first() + "'";
1145 out += "= '" + i->second.second() + "'\n";
1146 }
1147 }
1148}
1149
1150
1151void
1152anc_graph::construct_revisions_from_ancestry()
1153{
1154 // This is an incredibly cheesy, and also reasonably simple sorting
1155 // system: we put all the root nodes in the work queue. we take a
1156 // node out of the work queue and check if its parents are done. if
1157 // they are, we process it and insert its children. otherwise we put
1158 // it back on the end of the work queue. This both ensures that we're
1159 // always processing something *like* a frontier, while avoiding the
1160 // need to worry about one side of the frontier advancing faster than
1161 // another.
1162
1163 typedef multimap<u64,u64>::const_iterator ci;
1164 multimap<u64,u64> parent_to_child_map;
1165 deque<u64> work;
1166 set<u64> done;
1167
1168 {
1169 // Set up the parent->child mapping and prime the work queue
1170
1171 set<u64> children, all;
1172 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
1173 i != ancestry.end(); ++i)
1174 {
1175 parent_to_child_map.insert(make_pair(i->second, i->first));
1176 children.insert(i->first);
1177 }
1178 for (map<u64,manifest_id>::const_iterator i = node_to_old_man.begin();
1179 i != node_to_old_man.end(); ++i)
1180 {
1181 all.insert(i->first);
1182 }
1183
1184 set_difference(all.begin(), all.end(),
1185 children.begin(), children.end(),
1186 back_inserter(work));
1187 }
1188
1189 while (!work.empty())
1190 {
1191
1192 u64 child = work.front();
1193
1194 current_rev_debugger dbg(child, *this);
1195 MM(dbg);
1196
1197 work.pop_front();
1198
1199 if (done.find(child) != done.end())
1200 continue;
1201
1202 pair<ci,ci> parent_range = ancestry.equal_range(child);
1203 set<u64> parents;
1204 bool parents_all_done = true;
1205 for (ci i = parent_range.first; parents_all_done && i != parent_range.second; ++i)
1206 {
1207 if (i->first != child)
1208 continue;
1209 u64 parent = i->second;
1210 if (done.find(parent) == done.end())
1211 {
1212 work.push_back(child);
1213 parents_all_done = false;
1214 }
1215 else
1216 parents.insert(parent);
1217 }
1218
1219 if (parents_all_done
1220 && (node_to_new_rev.find(child) == node_to_new_rev.end()))
1221 {
1222 L(FL("processing node %d") % child);
1223
1224 manifest_id old_child_mid;
1225 legacy::manifest_map old_child_man;
1226
1227 get_node_manifest(child, old_child_mid);
1228 manifest_data mdat;
1229 app.db.get_manifest_version(old_child_mid, mdat);
1230 legacy::read_manifest_map(mdat, old_child_man);
1231
1232 // Load all the parent rosters into a temporary roster map
1233 parent_roster_map parent_rosters;
1234 MM(parent_rosters);
1235
1236 for (ci i = parent_range.first; parents_all_done && i != parent_range.second; ++i)
1237 {
1238 if (i->first != child)
1239 continue;
1240 u64 parent = i->second;
1241 if (parent_rosters.find(parent) == parent_rosters.end())
1242 {
1243 shared_ptr<roster_t> ros = shared_ptr<roster_t>(new roster_t());
1244 shared_ptr<marking_map> mm = shared_ptr<marking_map>(new marking_map());
1245 app.db.get_roster(safe_get(node_to_new_rev, parent), *ros, *mm);
1246 safe_insert(parent_rosters, make_pair(parent, make_pair(ros, mm)));
1247 }
1248 }
1249
1250 file_path attr_path = file_path_internal(".mt-attrs");
1251 file_path old_ignore_path = file_path_internal(".mt-ignore");
1252 file_path new_ignore_path = file_path_internal(".mtn-ignore");
1253
1254 roster_t child_roster;
1255 MM(child_roster);
1256 temp_node_id_source nis;
1257
1258 // all rosters shall have a root node.
1259 {
1260 split_path root_pth;
1261 file_path().split(root_pth);
1262 child_roster.attach_node(child_roster.create_dir_node(nis), root_pth);
1263 }
1264
1265 for (legacy::manifest_map::const_iterator i = old_child_man.begin();
1266 i != old_child_man.end(); ++i)
1267 {
1268 if (i->first == attr_path)
1269 continue;
1270 // convert .mt-ignore to .mtn-ignore... except if .mtn-ignore
1271 // already exists, just leave things alone.
1272 else if (i->first == old_ignore_path
1273 && old_child_man.find(new_ignore_path) == old_child_man.end())
1274 insert_into_roster(child_roster, nis, new_ignore_path, i->second);
1275 else
1276 insert_into_roster(child_roster, nis, i->first, i->second);
1277 }
1278
1279 // migrate attributes out of .mt-attrs
1280 {
1281 legacy::manifest_map::const_iterator i = old_child_man.find(attr_path);
1282 if (i != old_child_man.end())
1283 {
1284 file_data dat;
1285 app.db.get_file_version(i->second, dat);
1286 legacy::dot_mt_attrs_map attrs;
1287 legacy::read_dot_mt_attrs(dat.inner(), attrs);
1288 for (legacy::dot_mt_attrs_map::const_iterator j = attrs.begin();
1289 j != attrs.end(); ++j)
1290 {
1291 split_path sp;
1292 j->first.split(sp);
1293 if (child_roster.has_node(sp))
1294 {
1295 map<string, string> const &
1296 fattrs = j->second;
1297 for (map<string, string>::const_iterator
1298 k = fattrs.begin();
1299 k != fattrs.end(); ++k)
1300 {
1301 string key = k->first;
1302 if (app.attrs_to_drop.find(key) != app.attrs_to_drop.end())
1303 {
1304 // ignore it
1305 }
1306 else if (key == "execute" || key == "manual_merge")
1307 child_roster.set_attr(sp,
1308 attr_key("mtn:" + key),
1309 attr_value(k->second));
1310 else
1311 E(false, F("unknown attribute '%s' on path '%s'\n"
1312 "please contact %s so we can work out the right way to migrate this\n"
1313 "(if you just want it to go away, see the switch --drop-attr, but\n"
1314 "seriously, if you'd like to keep it, we're happy to figure out how)")
1315 % key % file_path(sp) % PACKAGE_BUGREPORT);
1316 }
1317 }
1318 }
1319 }
1320 }
1321
1322 // Now knit the parent node IDs into child node IDs (which are currently all
1323 // tmpids), wherever possible.
1324 fixup_node_identities(parent_rosters, child_roster, node_to_renames[child]);
1325
1326 revision_t rev;
1327 MM(rev);
1328 calculate_ident(child_roster, rev.new_manifest);
1329
1330 // For each parent, construct an edge in the revision structure by analyzing the
1331 // relationship between the parent roster and the child roster (and placing the
1332 // result in a cset)
1333
1334 for (parent_roster_map::const_iterator i = parent_rosters.begin();
1335 i != parent_rosters.end(); ++i)
1336 {
1337 u64 parent = i->first;
1338 revision_id parent_rid = safe_get(node_to_new_rev, parent);
1339 shared_ptr<roster_t> parent_roster = i->second.first;
1340 shared_ptr<cset> cs = shared_ptr<cset>(new cset());
1341 MM(*cs);
1342 make_cset(*parent_roster, child_roster, *cs);
1343 safe_insert(rev.edges, make_pair(parent_rid, cs));
1344 }
1345
1346 // It is possible that we're at a "root" node here -- a node
1347 // which had no parent in the old rev graph -- in which case we
1348 // synthesize an edge from the empty revision to the current,
1349 // containing a cset which adds all the files in the child.
1350
1351 if (rev.edges.empty())
1352 {
1353 revision_id parent_rid;
1354 shared_ptr<roster_t> parent_roster = shared_ptr<roster_t>(new roster_t());
1355 shared_ptr<cset> cs = shared_ptr<cset>(new cset());
1356 MM(*cs);
1357 make_cset(*parent_roster, child_roster, *cs);
1358 safe_insert(rev.edges, make_pair (parent_rid, cs));
1359
1360 }
1361
1362 // Finally, put all this excitement into the database and save
1363 // the new_rid for use in the cert-writing pass.
1364
1365 revision_id new_rid;
1366 calculate_ident(rev, new_rid);
1367 node_to_new_rev.insert(make_pair(child, new_rid));
1368 new_rev_to_node.insert(make_pair(new_rid, child));
1369
1370 /*
1371 P(F("------------------------------------------------"));
1372 P(F("made revision %s with %d edges, manifest id = %s")
1373 % new_rid % rev.edges.size() % rev.new_manifest);
1374
1375 {
1376 string rtmp;
1377 data dtmp;
1378 dump(dbg, rtmp);
1379 write_revision(rev, dtmp);
1380 P(F("%s") % rtmp);
1381 P(F("%s") % dtmp);
1382 }
1383 P(F("------------------------------------------------"));
1384 */
1385
1386 if (!app.db.revision_exists (new_rid))
1387 {
1388 L(FL("mapped node %d to revision %s") % child % new_rid);
1389 app.db.put_revision(new_rid, rev);
1390 ++n_revs_out;
1391 }
1392 else
1393 {
1394 L(FL("skipping already existing revision %s") % new_rid);
1395 }
1396
1397 // Mark this child as done, hooray!
1398 safe_insert(done, child);
1399
1400 // Extend the work queue with all the children of this child
1401 pair<ci,ci> grandchild_range = parent_to_child_map.equal_range(child);
1402 for (ci i = grandchild_range.first;
1403 i != grandchild_range.second; ++i)
1404 {
1405 if (i->first != child)
1406 continue;
1407 if (done.find(i->second) == done.end())
1408 work.push_back(i->second);
1409 }
1410 }
1411 }
1412}
1413
1414void
1415build_roster_style_revs_from_manifest_style_revs(app_state & app)
1416{
1417 app.db.ensure_open_for_format_changes();
1418 app.db.check_is_not_rosterified();
1419
1420 global_sanity.set_relaxed(true);
1421 anc_graph graph(true, app);
1422
1423 P(F("converting existing revision graph to new roster-style revisions"));
1424 multimap<revision_id, revision_id> existing_graph;
1425
1426 {
1427 // early short-circuit to avoid failure after lots of work
1428 rsa_keypair_id key;
1429 get_user_key(key,app);
1430 require_password(key, app);
1431 }
1432
1433 // cross-check that we're getting everything
1434 // in fact the code in this function is wrong, because if a revision has no
1435 // parents and no children (it is a root revision, and no children have been
1436 // committed under it), then we will simply drop it!
1437 // This code at least causes this case to throw an assertion; FIXME: make
1438 // this case actually work.
1439 set<revision_id> all_rev_ids;
1440 app.db.get_revision_ids(all_rev_ids);
1441
1442 app.db.get_revision_ancestry(existing_graph);
1443 for (multimap<revision_id, revision_id>::const_iterator i = existing_graph.begin();
1444 i != existing_graph.end(); ++i)
1445 {
1446 // FIXME: insert for the null id as well, and do the same for the
1447 // changesetify code, and then reach rebuild_ancestry how to deal with
1448 // such things. (I guess u64(0) should represent the null parent?)
1449 if (!null_id(i->first))
1450 {
1451 u64 parent_node = graph.add_node_for_oldstyle_revision(i->first);
1452 all_rev_ids.erase(i->first);
1453 u64 child_node = graph.add_node_for_oldstyle_revision(i->second);
1454 all_rev_ids.erase(i->second);
1455 graph.add_node_ancestry(child_node, parent_node);
1456 }
1457 }
1458
1459 for (set<revision_id>::const_iterator i = all_rev_ids.begin();
1460 i != all_rev_ids.end(); ++i)
1461 {
1462 graph.add_node_for_oldstyle_revision(*i);
1463 }
1464
1465 global_sanity.set_relaxed(false);
1466 graph.rebuild_ancestry();
1467}
1468
1469
1470void
1471build_changesets_from_manifest_ancestry(app_state & app)
1472{
1473 app.db.ensure_open_for_format_changes();
1474 app.db.check_is_not_rosterified();
1475
1476 anc_graph graph(false, app);
1477
1478 P(F("rebuilding revision graph from manifest certs"));
1479
1480 {
1481 // early short-circuit to avoid failure after lots of work
1482 rsa_keypair_id key;
1483 get_user_key(key,app);
1484 require_password(key, app);
1485 }
1486
1487 vector< manifest<cert> > tmp;
1488 app.db.get_manifest_certs(cert_name("ancestor"), tmp);
1489 erase_bogus_certs(tmp, app);
1490
1491 for (vector< manifest<cert> >::const_iterator i = tmp.begin();
1492 i != tmp.end(); ++i)
1493 {
1494 cert_value tv;
1495 decode_base64(i->inner().value, tv);
1496 manifest_id child, parent;
1497 child = i->inner().ident;
1498 parent = hexenc<id>(tv());
1499
1500 u64 parent_node = graph.add_node_for_old_manifest(parent);
1501 u64 child_node = graph.add_node_for_old_manifest(child);
1502 graph.add_node_ancestry(child_node, parent_node);
1503 }
1504
1505 graph.rebuild_ancestry();
1506}
1507
1508// i/o stuff
1509
1510namespace
1511{
1512 namespace syms
1513 {
1514 symbol const format_version("format_version");
1515 symbol const old_revision("old_revision");
1516 symbol const new_manifest("new_manifest");
1517 }
1518}
1519
1520void
1521print_edge(basic_io::printer & printer,
1522 edge_entry const & e)
1523{
1524 basic_io::stanza st;
1525 st.push_hex_pair(syms::old_revision, edge_old_revision(e).inner());
1526 printer.print_stanza(st);
1527 print_cset(printer, edge_changes(e));
1528}
1529
1530static void
1531print_insane_revision(basic_io::printer & printer,
1532 revision_t const & rev)
1533{
1534
1535 basic_io::stanza format_stanza;
1536 format_stanza.push_str_pair(syms::format_version, "1");
1537 printer.print_stanza(format_stanza);
1538
1539 basic_io::stanza manifest_stanza;
1540 manifest_stanza.push_hex_pair(syms::new_manifest, rev.new_manifest.inner());
1541 printer.print_stanza(manifest_stanza);
1542
1543 for (edge_map::const_iterator edge = rev.edges.begin();
1544 edge != rev.edges.end(); ++edge)
1545 print_edge(printer, *edge);
1546}
1547
1548void
1549print_revision(basic_io::printer & printer,
1550 revision_t const & rev)
1551{
1552 rev.check_sane();
1553 print_insane_revision(printer, rev);
1554}
1555
1556
1557void
1558parse_edge(basic_io::parser & parser,
1559 edge_map & es)
1560{
1561 shared_ptr<cset> cs(new cset());
1562 MM(*cs);
1563 manifest_id old_man;
1564 revision_id old_rev;
1565 string tmp;
1566
1567 parser.esym(syms::old_revision);
1568 parser.hex(tmp);
1569 old_rev = revision_id(tmp);
1570
1571 parse_cset(parser, *cs);
1572
1573 es.insert(make_pair(old_rev, cs));
1574}
1575
1576
1577void
1578parse_revision(basic_io::parser & parser,
1579 revision_t & rev)
1580{
1581 MM(rev);
1582 rev.edges.clear();
1583 string tmp;
1584 parser.esym(syms::format_version);
1585 parser.str(tmp);
1586 E(tmp == "1",
1587 F("encountered a revision with unknown format, version '%s'\n"
1588 "I only know how to understand the version '1' format\n"
1589 "a newer version of monotone is required to complete this operation")
1590 % tmp);
1591 parser.esym(syms::new_manifest);
1592 parser.hex(tmp);
1593 rev.new_manifest = manifest_id(tmp);
1594 while (parser.symp(syms::old_revision))
1595 parse_edge(parser, rev.edges);
1596 rev.check_sane();
1597}
1598
1599void
1600read_revision(data const & dat,
1601 revision_t & rev)
1602{
1603 MM(rev);
1604 basic_io::input_source src(dat(), "revision");
1605 basic_io::tokenizer tok(src);
1606 basic_io::parser pars(tok);
1607 parse_revision(pars, rev);
1608 I(src.lookahead == EOF);
1609 rev.check_sane();
1610}
1611
1612void
1613read_revision(revision_data const & dat,
1614 revision_t & rev)
1615{
1616 read_revision(dat.inner(), rev);
1617 rev.check_sane();
1618}
1619
1620static void write_insane_revision(revision_t const & rev,
1621 data & dat)
1622{
1623 basic_io::printer pr;
1624 print_insane_revision(pr, rev);
1625 dat = data(pr.buf);
1626}
1627
1628template <> void
1629dump(revision_t const & rev, string & out)
1630{
1631 data dat;
1632 write_insane_revision(rev, dat);
1633 out = dat();
1634}
1635
1636void
1637write_revision(revision_t const & rev,
1638 data & dat)
1639{
1640 rev.check_sane();
1641 write_insane_revision(rev, dat);
1642}
1643
1644void
1645write_revision(revision_t const & rev,
1646 revision_data & dat)
1647{
1648 data d;
1649 write_revision(rev, d);
1650 dat = revision_data(d);
1651}
1652
1653void calculate_ident(revision_t const & cs,
1654 revision_id & ident)
1655{
1656 data tmp;
1657 hexenc<id> tid;
1658 write_revision(cs, tmp);
1659 calculate_ident(tmp, tid);
1660 ident = tid;
1661}
1662
1663#ifdef BUILD_UNIT_TESTS
1664#include "unit_tests.hh"
1665#include "sanity.hh"
1666
1667static void
1668test_find_old_new_path_for()
1669{
1670 map<split_path, split_path> renames;
1671 split_path foo, foo_bar, foo_baz, quux, quux_baz;
1672 file_path_internal("foo").split(foo);
1673 file_path_internal("foo/bar").split(foo_bar);
1674 file_path_internal("foo/baz").split(foo_baz);
1675 file_path_internal("quux").split(quux);
1676 file_path_internal("quux/baz").split(quux_baz);
1677 I(foo == find_old_path_for(renames, foo));
1678 I(foo == find_new_path_for(renames, foo));
1679 I(foo_bar == find_old_path_for(renames, foo_bar));
1680 I(foo_bar == find_new_path_for(renames, foo_bar));
1681 I(quux == find_old_path_for(renames, quux));
1682 I(quux == find_new_path_for(renames, quux));
1683 renames.insert(make_pair(foo, quux));
1684 renames.insert(make_pair(foo_bar, foo_baz));
1685 I(quux == find_old_path_for(renames, foo));
1686 I(foo == find_new_path_for(renames, quux));
1687 I(quux_baz == find_old_path_for(renames, foo_baz));
1688 I(foo_baz == find_new_path_for(renames, quux_baz));
1689 I(foo_baz == find_old_path_for(renames, foo_bar));
1690 I(foo_bar == find_new_path_for(renames, foo_baz));
1691}
1692
1693void
1694add_revision_tests(test_suite * suite)
1695{
1696 I(suite);
1697 suite->add(BOOST_TEST_CASE(&test_find_old_new_path_for));
1698}
1699
1700
1701#endif // BUILD_UNIT_TESTS
1702
1703// Local Variables:
1704// mode: C++
1705// fill-column: 76
1706// c-file-style: "gnu"
1707// indent-tabs-mode: nil
1708// End:
1709// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

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