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