monotone

monotone Mtn Source Tree

Root/src/migrate_ancestry.cc

1// Copyright (C) 2010 Stephen Leake <stephen_leake@stephe-leake.org>
2// Copyright (C) 2004 Graydon Hoare <graydon@pobox.com>
3//
4// This program is made available under the GNU GPL version 2.0 or
5// greater. See the accompanying file COPYING for details.
6//
7// This program is distributed WITHOUT ANY WARRANTY; without even the
8// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
9// PURPOSE.
10
11#include "base.hh"
12#include "migration.hh"
13#include "revision.hh"
14#include "roster.hh"
15#include "project.hh"
16#include "constants.hh"
17#include "database.hh"
18#include "graph.hh"
19#include "key_store.hh"
20#include "lazy_rng.hh"
21#include "legacy.hh"
22#include "outdated_indicator.hh"
23#include "simplestring_xform.hh"
24#include "ui.hh"
25#include "vocab_cast.hh"
26
27#include "safe_map.hh"
28#include <sstream>
29#include <queue>
30#include "vector.hh"
31#include <boost/shared_ptr.hpp>
32
33using std::back_inserter;
34using std::deque;
35using std::make_pair;
36using std::map;
37using std::multimap;
38using std::ostringstream;
39using std::pair;
40using std::queue;
41using std::set;
42using std::string;
43using std::vector;
44using boost::shared_ptr;
45
46// Stuff related to rebuilding the revision graph. Unfortunately this is a
47// real enough error case that we need support code for it.
48
49typedef map<u64, pair<shared_ptr<roster_t>, shared_ptr<marking_map> > >
50parent_roster_map;
51
52template <> void
53dump(parent_roster_map const & prm, string & out)
54{
55 ostringstream oss;
56 for (parent_roster_map::const_iterator i = prm.begin(); i != prm.end(); ++i)
57 {
58 oss << "roster: " << i->first << '\n';
59 string roster_str, indented_roster_str;
60 dump(*i->second.first, roster_str);
61 prefix_lines_with(" ", roster_str, indented_roster_str);
62 oss << indented_roster_str;
63 oss << "\nroster's marking:\n";
64 string marking_str, indented_marking_str;
65 dump(*i->second.second, marking_str);
66 prefix_lines_with(" ", marking_str, indented_marking_str);
67 oss << indented_marking_str;
68 oss << "\n\n";
69 }
70 out = oss.str();
71}
72
73// FIXME: this algorithm is incredibly inefficient; it's O(n) where n is the
74// size of the entire revision graph.
75
76template<typename T> static bool
77is_ancestor(T const & ancestor_id,
78 T const & descendent_id,
79 multimap<T, T> const & graph)
80{
81 set<T> visited;
82 queue<T> queue;
83
84 queue.push(ancestor_id);
85
86 while (!queue.empty())
87 {
88 T current_id = queue.front();
89 queue.pop();
90
91 if (current_id == descendent_id)
92 return true;
93 else
94 {
95 typedef typename multimap<T, T>::const_iterator gi;
96 pair<gi, gi> children = graph.equal_range(current_id);
97 for (gi i = children.first; i != children.second; ++i)
98 {
99 if (visited.find(i->second) == visited.end())
100 {
101 queue.push(i->second);
102 visited.insert(i->second);
103 }
104 }
105 }
106 }
107 return false;
108}
109
110bool
111is_ancestor(database & db,
112 revision_id const & ancestor_id,
113 revision_id const & descendent_id)
114{
115 L(FL("checking whether %s is an ancestor of %s")
116 % ancestor_id
117 % descendent_id);
118
119 multimap<revision_id, revision_id> graph;
120 db.get_forward_ancestry(graph);
121 return is_ancestor(ancestor_id, descendent_id, graph);
122}
123
124namespace {
125
126struct anc_graph
127{
128 anc_graph(bool existing, database & db, key_store & keys,
129 project_t & project) :
130 existing_graph(existing),
131 db(db),
132 keys(keys),
133 project(project),
134 max_node(0),
135 n_nodes("nodes", "n", 1),
136 n_certs_in("certs in", "c", 1),
137 n_revs_out("revs out", "r", 1),
138 n_certs_out("certs out", "C", 1)
139 {}
140
141 bool existing_graph;
142 database & db;
143 key_store & keys;
144 project_t & project;
145 u64 max_node;
146
147 ticker n_nodes;
148 ticker n_certs_in;
149 ticker n_revs_out;
150 ticker n_certs_out;
151
152 map<u64,manifest_id> node_to_old_man;
153 map<manifest_id,u64> old_man_to_node;
154
155 map<u64,revision_id> node_to_old_rev;
156 map<revision_id,u64> old_rev_to_node;
157
158 map<u64,revision_id> node_to_new_rev;
159 map<revision_id,u64> new_rev_to_node;
160
161 map<u64, legacy::renames_map> node_to_renames;
162
163 multimap<u64, pair<cert_name, cert_value> > certs;
164 multimap<u64, u64> ancestry;
165 set<string> branches;
166
167 void add_node_ancestry(u64 child, u64 parent);
168 void write_certs();
169 void kluge_for_bogus_merge_edges();
170 void rebuild_ancestry(set<string> const & attrs_to_drop);
171 void get_node_manifest(u64 node, manifest_id & man);
172 u64 add_node_for_old_manifest(manifest_id const & man);
173 u64 add_node_for_oldstyle_revision(revision_id const & rev);
174 void construct_revisions_from_ancestry(set<string> const & attrs_to_drop);
175 void fixup_node_identities(parent_roster_map const & parent_rosters,
176 roster_t & child_roster,
177 legacy::renames_map const & renames);
178};
179
180}
181
182void anc_graph::add_node_ancestry(u64 child, u64 parent)
183{
184 L(FL("noting ancestry from child %d -> parent %d") % child % parent);
185 ancestry.insert(make_pair(child, parent));
186}
187
188void anc_graph::get_node_manifest(u64 node, manifest_id & man)
189{
190 map<u64,manifest_id>::const_iterator i = node_to_old_man.find(node);
191 I(i != node_to_old_man.end());
192 man = i->second;
193}
194
195void anc_graph::write_certs()
196{
197 {
198 // regenerate epochs on all branches to random states
199
200 for (set<string>::const_iterator i = branches.begin(); i != branches.end(); ++i)
201 {
202 char buf[constants::epochlen_bytes];
203#if BOTAN_VERSION_CODE >= BOTAN_VERSION_CODE_FOR(1,7,7)
204 lazy_rng::get().randomize(reinterpret_cast<Botan::byte *>(buf),
205 constants::epochlen_bytes);
206#else
207 Botan::Global_RNG::randomize(reinterpret_cast<Botan::byte *>(buf),
208 constants::epochlen_bytes);
209#endif
210 epoch_data new_epoch(string(buf, buf + constants::epochlen_bytes),
211 origin::internal);
212 L(FL("setting epoch for %s to %s")
213 % *i % new_epoch);
214 db.set_epoch(branch_name(*i, origin::internal), new_epoch);
215 }
216 }
217
218
219 typedef multimap<u64, pair<cert_name, cert_value> >::const_iterator ci;
220
221 for (map<u64,revision_id>::const_iterator i = node_to_new_rev.begin();
222 i != node_to_new_rev.end(); ++i)
223 {
224 revision_id rev(i->second);
225
226 pair<ci,ci> range = certs.equal_range(i->first);
227
228 for (ci j = range.first; j != range.second; ++j)
229 {
230 cert_name name(j->second.first);
231 cert_value val(j->second.second);
232
233 if (project.put_cert(keys, rev, name, val))
234 ++n_certs_out;
235 }
236 }
237}
238
239void
240anc_graph::kluge_for_bogus_merge_edges()
241{
242 // This kluge exists because in the 0.24-era monotone databases, several
243 // bad merges still existed in which one side of the merge is an ancestor
244 // of the other side of the merge. In other words, graphs which look like
245 // this:
246 //
247 // a ----------------------> e
248 // \ /
249 // \---> b -> c -> d ----/
250 //
251 // Such merges confuse the roster-building algorithm, because they should
252 // never have occurred in the first place: a was not a head at the time
253 // of the merge, e should simply have been considered an extension of d.
254 //
255 // So... we drop the a->e edges entirely.
256 //
257 // Note: this kluge drops edges which are a struct superset of those
258 // dropped by a previous kluge ("3-ancestor") so we have removed that
259 // code.
260
261 P(F("scanning for bogus merge edges"));
262
263 multimap<u64,u64> parent_to_child_map;
264 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
265 i != ancestry.end(); ++i)
266 parent_to_child_map.insert(make_pair(i->second, i->first));
267
268 map<u64, u64> edges_to_kill;
269 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
270 i != ancestry.end(); ++i)
271 {
272 multimap<u64, u64>::const_iterator j = i;
273 ++j;
274 u64 child = i->first;
275 // NB: ancestry is a multimap from child->parent(s)
276 if (j != ancestry.end())
277 {
278 if (j->first == i->first)
279 {
280 L(FL("considering old merge edge %s") %
281 safe_get(node_to_old_rev, i->first));
282 u64 parent1 = i->second;
283 u64 parent2 = j->second;
284 if (is_ancestor (parent1, parent2, parent_to_child_map))
285 safe_insert(edges_to_kill, make_pair(child, parent1));
286 else if (is_ancestor (parent2, parent1, parent_to_child_map))
287 safe_insert(edges_to_kill, make_pair(child, parent2));
288 }
289 }
290 }
291
292 for (map<u64, u64>::const_iterator i = edges_to_kill.begin();
293 i != edges_to_kill.end(); ++i)
294 {
295 u64 child = i->first;
296 u64 parent = i->second;
297 bool killed = false;
298 for (multimap<u64, u64>::iterator j = ancestry.lower_bound(child);
299 j->first == child; ++j)
300 {
301 if (j->second == parent)
302 {
303 P(F("optimizing out redundant edge %d -> %d")
304 % parent % child);
305 ancestry.erase(j);
306 killed = true;
307 break;
308 }
309 }
310
311 if (!killed)
312 W(F("failed to eliminate edge %d -> %d")
313 % parent % child);
314 }
315}
316
317
318void
319anc_graph::rebuild_ancestry(set<string> const & attrs_to_drop)
320{
321 kluge_for_bogus_merge_edges();
322
323 P(F("rebuilding %d nodes") % max_node);
324 {
325 transaction_guard guard(db);
326 if (existing_graph)
327 db.delete_existing_revs_and_certs();
328 construct_revisions_from_ancestry(attrs_to_drop);
329 write_certs();
330 if (existing_graph)
331 db.delete_existing_manifests();
332 guard.commit();
333 }
334}
335
336u64
337anc_graph::add_node_for_old_manifest(manifest_id const & man)
338{
339 I(!existing_graph);
340 u64 node = 0;
341 if (old_man_to_node.find(man) == old_man_to_node.end())
342 {
343 node = max_node++;
344 ++n_nodes;
345 L(FL("node %d = manifest %s")
346 % node % man);
347 old_man_to_node.insert(make_pair(man, node));
348 node_to_old_man.insert(make_pair(node, man));
349
350 // load certs
351 vector<cert> mcerts;
352 db.get_manifest_certs(man, mcerts);
353 for(vector<cert>::const_iterator i = mcerts.begin();
354 i != mcerts.end(); ++i)
355 {
356 L(FL("loaded '%s' manifest cert for node %s") % i->name % node);
357 ++n_certs_in;
358 certs.insert(make_pair(node, make_pair(i->name, i->value)));
359 }
360 }
361 else
362 {
363 node = old_man_to_node[man];
364 }
365 return node;
366}
367
368u64 anc_graph::add_node_for_oldstyle_revision(revision_id const & rev)
369{
370 I(existing_graph);
371 I(!null_id(rev));
372 u64 node = 0;
373 if (old_rev_to_node.find(rev) == old_rev_to_node.end())
374 {
375 node = max_node++;
376 ++n_nodes;
377
378 manifest_id man;
379 legacy::renames_map renames;
380 legacy::get_manifest_and_renames_for_rev(db, rev, man, renames);
381
382 L(FL("node %d = revision %s = manifest %s")
383 % node
384 % rev
385 % man);
386 old_rev_to_node.insert(make_pair(rev, node));
387 node_to_old_rev.insert(make_pair(node, rev));
388 node_to_old_man.insert(make_pair(node, man));
389 node_to_renames.insert(make_pair(node, renames));
390
391 // load certs
392 vector<cert> rcerts;
393 db.get_revision_certs(rev, rcerts);
394 db.erase_bogus_certs(project, rcerts);
395 for(vector<cert>::const_iterator i = rcerts.begin();
396 i != rcerts.end(); ++i)
397 {
398 L(FL("loaded '%s' revision cert for node %s") % i->name % node);
399 ++n_certs_in;
400 certs.insert(make_pair(node, make_pair(i->name,
401 i->value)));
402
403 if (i->name == branch_cert_name)
404 branches.insert(i->value());
405 }
406 }
407 else
408 {
409 node = old_rev_to_node[rev];
410 }
411
412 return node;
413}
414
415static bool
416not_dead_yet(node_id nid, u64 birth_rev,
417 parent_roster_map const & parent_rosters,
418 multimap<u64, u64> const & child_to_parents)
419{
420 // Any given node, at each point in the revision graph, is in one of the
421 // states "alive", "unborn", "dead". The invariant we must maintain in
422 // constructing our revision graph is that if a node is dead in any parent,
423 // then it must also be dead in the child. The purpose of this function is
424 // to take a node, and a list of parents, and determine whether that node is
425 // allowed to be alive in a child of the given parents.
426
427 // "Alive" means, the node currently exists in the revision's tree.
428 // "Unborn" means, the node does not exist in the revision's tree, and the
429 // node's birth revision is _not_ an ancestor of the revision.
430 // "Dead" means, the node does not exist in the revision's tree, and the
431 // node's birth revision _is_ an ancestor of the revision.
432
433 // L(FL("testing liveliness of node %d, born in rev %d") % nid % birth_rev);
434 for (parent_roster_map::const_iterator r = parent_rosters.begin();
435 r != parent_rosters.end(); ++r)
436 {
437 shared_ptr<roster_t> parent = r->second.first;
438 // L(FL("node %d %s in parent roster %d")
439 // % nid
440 // % (parent->has_node(n->first) ? "exists" : "does not exist" )
441 // % r->first);
442
443 if (!parent->has_node(nid))
444 {
445 deque<u64> work;
446 set<u64> seen;
447 work.push_back(r->first);
448 while (!work.empty())
449 {
450 u64 curr = work.front();
451 work.pop_front();
452 // L(FL("examining ancestor %d of parent roster %d, looking for anc=%d")
453 // % curr % r->first % birth_rev);
454
455 if (seen.find(curr) != seen.end())
456 continue;
457 seen.insert(curr);
458
459 if (curr == birth_rev)
460 {
461 // L(FL("node is dead in %d") % r->first);
462 return false;
463 }
464 typedef multimap<u64, u64>::const_iterator ci;
465 pair<ci,ci> range = child_to_parents.equal_range(curr);
466 for (ci i = range.first; i != range.second; ++i)
467 {
468 if (i->first != curr)
469 continue;
470 work.push_back(i->second);
471 }
472 }
473 }
474 }
475 // L(FL("node is alive in all parents, returning true"));
476 return true;
477}
478
479// Recursive helper function for insert_into_roster.
480static void
481insert_parents_into_roster(roster_t & child_roster,
482 temp_node_id_source & nis,
483 file_path const & pth,
484 file_path const & full)
485{
486 if (child_roster.has_node(pth))
487 {
488 E(is_dir_t(child_roster.get_node(pth)), origin::internal,
489 F("directory '%s' for path '%s' cannot be added, "
490 "as there is a file in the way") % pth % full);
491 return;
492 }
493
494 if (!pth.empty())
495 insert_parents_into_roster(child_roster, nis, pth.dirname(), full);
496
497 child_roster.attach_node(child_roster.create_dir_node(nis), pth);
498}
499
500static void
501insert_into_roster(roster_t & child_roster,
502 temp_node_id_source & nis,
503 file_path const & pth,
504 file_id const & fid)
505{
506 if (child_roster.has_node(pth))
507 {
508 const_node_t n = child_roster.get_node(pth);
509 E(is_file_t(n), origin::internal,
510 F("path '%s' cannot be added, as there is a directory in the way") % pth);
511 const_file_t f = downcast_to_file_t(n);
512 E(f->content == fid, origin::internal,
513 F("path '%s' added twice with differing content") % pth);
514 return;
515 }
516
517 insert_parents_into_roster(child_roster, nis, pth.dirname(), pth);
518 child_roster.attach_node(child_roster.create_file_node(fid, nis), pth);
519}
520
521void
522anc_graph::fixup_node_identities(parent_roster_map const & parent_rosters,
523 roster_t & child_roster,
524 legacy::renames_map const & renames)
525{
526 // Our strategy here is to iterate over every node in every parent, and
527 // for each parent node P find zero or one tmp nodes in the child which
528 // represents the fate of P:
529 //
530 // - If any of the parents thinks that P has died, we do not search for
531 // it in the child; we leave it as "dropped".
532 //
533 // - We fetch the name N of the parent node P, and apply the rename map
534 // to N, getting "remapped name" M. If we find a child node C with
535 // name M in the child roster, with the same type as P, we identify P
536 // and C, and swap P for C in the child.
537
538
539 // Map node_id -> birth rev
540 map<node_id, u64> nodes_in_any_parent;
541
542 // Stage 1: collect all nodes (and their birth revs) in any parent.
543 for (parent_roster_map::const_iterator i = parent_rosters.begin();
544 i != parent_rosters.end(); ++i)
545 {
546 shared_ptr<roster_t> parent_roster = i->second.first;
547 shared_ptr<marking_map> parent_marking = i->second.second;
548
549 node_map const & nodes = parent_roster->all_nodes();
550 for (node_map::const_iterator j = nodes.begin(); j != nodes.end(); ++j)
551 {
552 node_id n = j->first;
553 revision_id birth_rev = parent_marking->get_marking(n)->birth_revision;
554 u64 birth_node = safe_get(new_rev_to_node, birth_rev);
555 map<node_id, u64>::const_iterator i = nodes_in_any_parent.find(n);
556 if (i != nodes_in_any_parent.end())
557 I(i->second == birth_node);
558 else
559 safe_insert(nodes_in_any_parent,
560 make_pair(n, birth_node));
561 }
562 }
563
564 // Stage 2: For any node which is actually live, try to locate a mapping
565 // from a parent instance of it to a child node.
566 for (map<node_id, u64>::const_iterator i = nodes_in_any_parent.begin();
567 i != nodes_in_any_parent.end(); ++i)
568 {
569 node_id n = i->first;
570 u64 birth_rev = i->second;
571
572 if (child_roster.has_node(n))
573 continue;
574
575 if (not_dead_yet(n, birth_rev, parent_rosters, ancestry))
576 {
577 for (parent_roster_map::const_iterator j = parent_rosters.begin();
578 j != parent_rosters.end(); ++j)
579 {
580 shared_ptr<roster_t> parent_roster = j->second.first;
581
582 if (!parent_roster->has_node(n))
583 continue;
584
585 file_path fp;
586 parent_roster->get_name(n, fp);
587
588 // Try remapping the name.
589 if (node_to_old_rev.find(j->first) != node_to_old_rev.end())
590 {
591 legacy::renames_map::const_iterator rmap;
592 revision_id parent_rid = safe_get(node_to_old_rev, j->first);
593 rmap = renames.find(parent_rid);
594 if (rmap != renames.end())
595 fp = find_new_path_for(rmap->second, fp);
596 }
597
598 // See if we can match this node against a child.
599 if ((!child_roster.has_node(n))
600 && child_roster.has_node(fp))
601 {
602 const_node_t pn = parent_roster->get_node(n);
603 const_node_t cn = child_roster.get_node(fp);
604 if (is_file_t(pn) == is_file_t(cn))
605 {
606 child_roster.replace_node_id(cn->self, n);
607 break;
608 }
609 }
610 }
611 }
612 }
613}
614
615struct
616current_rev_debugger
617{
618 u64 node;
619 anc_graph const & agraph;
620 current_rev_debugger(u64 n, anc_graph const & ag)
621 : node(n), agraph(ag)
622 {
623 }
624};
625
626template <> void
627dump(current_rev_debugger const & d, string & out)
628{
629 typedef multimap<u64, pair<cert_name, cert_value> >::const_iterator ci;
630 pair<ci,ci> range = d.agraph.certs.equal_range(d.node);
631 for(ci i = range.first; i != range.second; ++i)
632 {
633 if (i->first == d.node)
634 {
635 out += "cert '" + i->second.first() + "'";
636 out += "= '" + i->second.second() + "'\n";
637 }
638 }
639}
640
641
642void
643anc_graph::construct_revisions_from_ancestry(set<string> const & attrs_to_drop)
644{
645 // This is an incredibly cheesy, and also reasonably simple sorting
646 // system: we put all the root nodes in the work queue. we take a
647 // node out of the work queue and check if its parents are done. if
648 // they are, we process it and insert its children. otherwise we put
649 // it back on the end of the work queue. This both ensures that we're
650 // always processing something *like* a frontier, while avoiding the
651 // need to worry about one side of the frontier advancing faster than
652 // another.
653
654 typedef multimap<u64,u64>::const_iterator ci;
655 multimap<u64,u64> parent_to_child_map;
656 deque<u64> work;
657 set<u64> done;
658
659 {
660 // Set up the parent->child mapping and prime the work queue
661
662 set<u64> children, all;
663 for (multimap<u64, u64>::const_iterator i = ancestry.begin();
664 i != ancestry.end(); ++i)
665 {
666 parent_to_child_map.insert(make_pair(i->second, i->first));
667 children.insert(i->first);
668 }
669 for (map<u64,manifest_id>::const_iterator i = node_to_old_man.begin();
670 i != node_to_old_man.end(); ++i)
671 {
672 all.insert(i->first);
673 }
674
675 set_difference(all.begin(), all.end(),
676 children.begin(), children.end(),
677 back_inserter(work));
678 }
679
680 while (!work.empty())
681 {
682
683 u64 child = work.front();
684
685 current_rev_debugger dbg(child, *this);
686 MM(dbg);
687
688 work.pop_front();
689
690 if (done.find(child) != done.end())
691 continue;
692
693 pair<ci,ci> parent_range = ancestry.equal_range(child);
694 set<u64> parents;
695 bool parents_all_done = true;
696 for (ci i = parent_range.first; parents_all_done && i != parent_range.second; ++i)
697 {
698 if (i->first != child)
699 continue;
700 u64 parent = i->second;
701 if (done.find(parent) == done.end())
702 {
703 work.push_back(child);
704 parents_all_done = false;
705 }
706 else
707 parents.insert(parent);
708 }
709
710 if (parents_all_done
711 && (node_to_new_rev.find(child) == node_to_new_rev.end()))
712 {
713 L(FL("processing node %d") % child);
714
715 manifest_id old_child_mid;
716 legacy::manifest_map old_child_man;
717
718 get_node_manifest(child, old_child_mid);
719 manifest_data mdat;
720 db.get_manifest_version(old_child_mid, mdat);
721 legacy::read_manifest_map(mdat, old_child_man);
722
723 // Load all the parent rosters into a temporary roster map
724 parent_roster_map parent_rosters;
725 MM(parent_rosters);
726
727 for (ci i = parent_range.first; parents_all_done && i != parent_range.second; ++i)
728 {
729 if (i->first != child)
730 continue;
731 u64 parent = i->second;
732 if (parent_rosters.find(parent) == parent_rosters.end())
733 {
734 shared_ptr<roster_t> ros = shared_ptr<roster_t>(new roster_t());
735 shared_ptr<marking_map> mm = shared_ptr<marking_map>(new marking_map());
736 db.get_roster(safe_get(node_to_new_rev, parent), *ros, *mm);
737 safe_insert(parent_rosters, make_pair(parent, make_pair(ros, mm)));
738 }
739 }
740
741 file_path attr_path = file_path_internal(".mt-attrs");
742 file_path old_ignore_path = file_path_internal(".mt-ignore");
743 file_path new_ignore_path = file_path_internal(".mtn-ignore");
744
745 roster_t child_roster;
746 MM(child_roster);
747 temp_node_id_source nis;
748
749 // all rosters shall have a root node.
750 child_roster.attach_node(child_roster.create_dir_node(nis),
751 file_path_internal(""));
752
753 for (legacy::manifest_map::const_iterator i = old_child_man.begin();
754 i != old_child_man.end(); ++i)
755 {
756 if (i->first == attr_path)
757 continue;
758 // convert .mt-ignore to .mtn-ignore... except if .mtn-ignore
759 // already exists, just leave things alone.
760 else if (i->first == old_ignore_path
761 && old_child_man.find(new_ignore_path) == old_child_man.end())
762 insert_into_roster(child_roster, nis, new_ignore_path, i->second);
763 else
764 insert_into_roster(child_roster, nis, i->first, i->second);
765 }
766
767 // migrate attributes out of .mt-attrs
768 {
769 legacy::manifest_map::const_iterator i = old_child_man.find(attr_path);
770 if (i != old_child_man.end())
771 {
772 file_data dat;
773 db.get_file_version(i->second, dat);
774 legacy::dot_mt_attrs_map attrs;
775 legacy::read_dot_mt_attrs(dat.inner(), attrs);
776 for (legacy::dot_mt_attrs_map::const_iterator j = attrs.begin();
777 j != attrs.end(); ++j)
778 {
779 if (child_roster.has_node(j->first))
780 {
781 map<string, string> const &
782 fattrs = j->second;
783 for (map<string, string>::const_iterator
784 k = fattrs.begin();
785 k != fattrs.end(); ++k)
786 {
787 string key = k->first;
788 if (attrs_to_drop.find(key) != attrs_to_drop.end())
789 {
790 // ignore it
791 }
792 else if (key == "execute" || key == "manual_merge")
793 child_roster.set_attr(j->first,
794 attr_key("mtn:" + key,
795 origin::internal),
796 attr_value(k->second,
797 origin::internal));
798 else
799 E(false, origin::no_fault,
800 F("unknown attribute '%s' on path '%s'.\n"
801 "Please contact %s so we can work out the right way to migrate this\n"
802 "(if you just want it to go away, see the switch '--drop-attr', but\n"
803 "seriously, if you'd like to keep it, we're happy to figure out how)")
804 % key % j->first % PACKAGE_BUGREPORT);
805 }
806 }
807 }
808 }
809 }
810
811 // Now knit the parent node IDs into child node IDs (which are currently all
812 // tmpids), wherever possible.
813 fixup_node_identities(parent_rosters, child_roster, node_to_renames[child]);
814
815 revision_t rev;
816 rev.made_for = made_for_database;
817 MM(rev);
818 calculate_ident(child_roster, rev.new_manifest);
819
820 // For each parent, construct an edge in the revision structure by analyzing the
821 // relationship between the parent roster and the child roster (and placing the
822 // result in a cset)
823
824 for (parent_roster_map::const_iterator i = parent_rosters.begin();
825 i != parent_rosters.end(); ++i)
826 {
827 u64 parent = i->first;
828 revision_id parent_rid = safe_get(node_to_new_rev, parent);
829 shared_ptr<roster_t> parent_roster = i->second.first;
830 shared_ptr<cset> cs = shared_ptr<cset>(new cset());
831 MM(*cs);
832 make_cset(*parent_roster, child_roster, *cs);
833 safe_insert(rev.edges, make_pair(parent_rid, cs));
834 }
835
836 // It is possible that we're at a "root" node here -- a node
837 // which had no parent in the old rev graph -- in which case we
838 // synthesize an edge from the empty revision to the current,
839 // containing a cset which adds all the files in the child.
840
841 if (rev.edges.empty())
842 {
843 revision_id parent_rid;
844 shared_ptr<roster_t> parent_roster = shared_ptr<roster_t>(new roster_t());
845 shared_ptr<cset> cs = shared_ptr<cset>(new cset());
846 MM(*cs);
847 make_cset(*parent_roster, child_roster, *cs);
848 safe_insert(rev.edges, make_pair (parent_rid, cs));
849
850 }
851
852 // Finally, put all this excitement into the database and save
853 // the new_rid for use in the cert-writing pass.
854
855 revision_id new_rid;
856 calculate_ident(rev, new_rid);
857 node_to_new_rev.insert(make_pair(child, new_rid));
858 new_rev_to_node.insert(make_pair(new_rid, child));
859
860 /*
861 P(F("------------------------------------------------"));
862 P(F("made revision %s with %d edges, manifest id = %s")
863 % new_rid % rev.edges.size() % rev.new_manifest);
864
865 {
866 string rtmp;
867 data dtmp;
868 dump(dbg, rtmp);
869 write_revision(rev, dtmp);
870 P(F("%s") % rtmp);
871 P(F("%s") % dtmp);
872 }
873 P(F("------------------------------------------------"));
874 */
875
876 L(FL("mapped node %d to revision %s") % child % new_rid);
877 if (db.put_revision(new_rid, rev))
878 {
879 db.put_file_sizes_for_revision(rev);
880 ++n_revs_out;
881 }
882
883 // Mark this child as done, hooray!
884 safe_insert(done, child);
885
886 // Extend the work queue with all the children of this child
887 pair<ci,ci> grandchild_range = parent_to_child_map.equal_range(child);
888 for (ci i = grandchild_range.first;
889 i != grandchild_range.second; ++i)
890 {
891 if (i->first != child)
892 continue;
893 if (done.find(i->second) == done.end())
894 work.push_back(i->second);
895 }
896 }
897 }
898}
899
900void
901build_roster_style_revs_from_manifest_style_revs(database & db, key_store & keys,
902 project_t & project,
903 set<string> const & attrs_to_drop)
904{
905 anc_graph graph(true, db, keys, project);
906
907 P(F("converting existing revision graph to new roster-style revisions"));
908 multimap<revision_id, revision_id> existing_graph;
909
910 // cross-check that we're getting everything
911 // in fact the code in this function is wrong, because if a revision has no
912 // parents and no children (it is a root revision, and no children have been
913 // committed under it), then we will simply drop it!
914 // This code at least causes this case to throw an assertion; FIXME: make
915 // this case actually work.
916 set<revision_id> all_rev_ids;
917 db.get_revision_ids(all_rev_ids);
918
919 db.get_forward_ancestry(existing_graph);
920 for (multimap<revision_id, revision_id>::const_iterator i = existing_graph.begin();
921 i != existing_graph.end(); ++i)
922 {
923 // FIXME: insert for the null id as well, and do the same for the
924 // changesetify code, and then reach rebuild_ancestry how to deal with
925 // such things. (I guess u64(0) should represent the null parent?)
926 if (!null_id(i->first))
927 {
928 u64 parent_node = graph.add_node_for_oldstyle_revision(i->first);
929 all_rev_ids.erase(i->first);
930 u64 child_node = graph.add_node_for_oldstyle_revision(i->second);
931 all_rev_ids.erase(i->second);
932 graph.add_node_ancestry(child_node, parent_node);
933 }
934 }
935
936 for (set<revision_id>::const_iterator i = all_rev_ids.begin();
937 i != all_rev_ids.end(); ++i)
938 {
939 graph.add_node_for_oldstyle_revision(*i);
940 }
941
942 graph.rebuild_ancestry(attrs_to_drop);
943}
944
945
946void
947build_changesets_from_manifest_ancestry(database & db, key_store & keys,
948 project_t & project,
949 set<string> const & attrs_to_drop)
950{
951 anc_graph graph(false, db, keys, project);
952
953 P(F("rebuilding revision graph from manifest certs"));
954
955 vector<cert> tmp;
956 db.get_manifest_certs(cert_name("ancestor"), tmp);
957
958 for (vector<cert>::const_iterator i = tmp.begin();
959 i != tmp.end(); ++i)
960 {
961 manifest_id child, parent;
962 child = manifest_id(i->ident.inner());
963 parent = typecast_vocab<manifest_id>(i->value);
964
965 u64 parent_node = graph.add_node_for_old_manifest(parent);
966 u64 child_node = graph.add_node_for_old_manifest(child);
967 graph.add_node_ancestry(child_node, parent_node);
968 }
969
970 graph.rebuild_ancestry(attrs_to_drop);
971}
972
973
974// This is a special function solely for the use of regenerate_caches -- it
975// must work even when caches (especially, the height cache!) do not exist.
976// For all other purposes, use toposort above.
977static void
978allrevs_toposorted(database & db,
979 vector<revision_id> & revisions)
980{
981 // get the complete ancestry
982 rev_ancestry_map graph;
983 db.get_forward_ancestry(graph);
984 toposort_rev_ancestry(graph, revisions);
985}
986
987static void
988regenerate_heights(database & db)
989{
990 P(F("regenerating cached heights"));
991 db.ensure_open_for_cache_reset();
992
993 {
994 transaction_guard guard(db);
995 db.delete_existing_heights();
996
997 vector<revision_id> sorted_ids;
998 allrevs_toposorted(db, sorted_ids);
999
1000 ticker done(_("regenerated"), "r", 1);
1001 done.set_total(sorted_ids.size());
1002
1003 for (std::vector<revision_id>::const_iterator i = sorted_ids.begin();
1004 i != sorted_ids.end(); ++i)
1005 {
1006 revision_t rev;
1007 revision_id const & rev_id = *i;
1008 db.get_revision(rev_id, rev);
1009 db.put_height_for_revision(rev_id, rev);
1010 ++done;
1011 }
1012
1013 guard.commit();
1014 }
1015 P(F("finished regenerating cached heights"));
1016}
1017
1018static void
1019regenerate_rosters(database & db)
1020{
1021 P(F("regenerating cached rosters"));
1022 db.ensure_open_for_cache_reset();
1023
1024 {
1025 transaction_guard guard(db);
1026 db.delete_existing_rosters();
1027
1028 vector<revision_id> sorted_ids;
1029 allrevs_toposorted(db, sorted_ids);
1030
1031 ticker done(_("regenerated"), "r", 1);
1032 done.set_total(sorted_ids.size());
1033
1034 for (std::vector<revision_id>::const_iterator i = sorted_ids.begin();
1035 i != sorted_ids.end(); ++i)
1036 {
1037 revision_t rev;
1038 revision_id const & rev_id = *i;
1039 db.get_revision(rev_id, rev);
1040 db.put_roster_for_revision(rev_id, rev);
1041 ++done;
1042 }
1043
1044 guard.commit();
1045 }
1046 P(F("finished regenerating cached rosters"));
1047}
1048
1049static void
1050regenerate_branches(database & db)
1051{
1052 P(F("regenerating cached branches"));
1053 db.ensure_open_for_cache_reset();
1054
1055 {
1056 transaction_guard guard(db);
1057 db.delete_existing_branch_leaves();
1058
1059 vector<cert> all_branch_certs;
1060 db.get_revision_certs(branch_cert_name, all_branch_certs);
1061 set<string> seen_branches;
1062
1063 ticker done(_("regenerated"), "r", 1);
1064
1065 for (vector<cert>::const_iterator i = all_branch_certs.begin();
1066 i != all_branch_certs.end(); ++i)
1067 {
1068 string const name = i->value();
1069
1070 std::pair<set<string>::iterator, bool> inserted =
1071 seen_branches.insert(name);
1072
1073 if (inserted.second)
1074 {
1075 db.recalc_branch_leaves(i->value);
1076 ++done;
1077 }
1078 }
1079 guard.commit();
1080 }
1081 P(F("finished regenerating cached branches"));
1082}
1083
1084static void
1085regenerate_file_sizes(database & db)
1086{
1087 P(F("regenerating cached file sizes for revisions"));
1088 db.ensure_open_for_cache_reset();
1089
1090 {
1091 transaction_guard guard(db);
1092 db.delete_existing_file_sizes();
1093
1094 vector<revision_id> sorted_ids;
1095 allrevs_toposorted(db, sorted_ids);
1096
1097 ticker done(_("regenerated"), "r", 1);
1098 done.set_total(sorted_ids.size());
1099
1100 for (std::vector<revision_id>::const_iterator i = sorted_ids.begin();
1101 i != sorted_ids.end(); ++i)
1102 {
1103 revision_t rev;
1104 revision_id const & rev_id = *i;
1105 db.get_revision(rev_id, rev);
1106 db.put_file_sizes_for_revision(rev);
1107 ++done;
1108 }
1109
1110 guard.commit();
1111 }
1112 P(F("finished regenerating cached file sizes"));
1113}
1114
1115void
1116regenerate_caches(database & db, regen_cache_type type)
1117{
1118 I(type != regen_none);
1119
1120 if ((type & regen_heights) == regen_heights)
1121 regenerate_heights(db);
1122 if ((type & regen_rosters) == regen_rosters)
1123 regenerate_rosters(db);
1124 if ((type & regen_branches) == regen_branches)
1125 regenerate_branches(db);
1126 if ((type & regen_file_sizes) == regen_file_sizes)
1127 regenerate_file_sizes(db);
1128}
1129
1130// Local Variables:
1131// mode: C++
1132// fill-column: 76
1133// c-file-style: "gnu"
1134// indent-tabs-mode: nil
1135// End:
1136// 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