monotone

monotone Mtn Source Tree

Root/roster.cc

1// Copyright (C) 2005 Nathaniel Smith <njs@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 <algorithm>
11#include <stack>
12#include <set>
13#include <string>
14#include <vector>
15#include <sstream>
16
17#include "app_state.hh"
18#include "basic_io.hh"
19#include "cset.hh"
20#include "platform-wrapped.hh"
21#include "roster.hh"
22#include "revision.hh"
23#include "vocab.hh"
24#include "transforms.hh"
25#include "simplestring_xform.hh"
26#include "file_io.hh"
27#include "parallel_iter.hh"
28#include "restrictions.hh"
29#include "safe_map.hh"
30#include "ui.hh"
31
32#include <boost/lexical_cast.hpp>
33
34using std::inserter;
35using std::make_pair;
36using std::map;
37using std::ostringstream;
38using std::pair;
39using std::reverse;
40using std::set;
41using std::set_union;
42using std::stack;
43using std::string;
44using std::vector;
45
46using boost::lexical_cast;
47
48///////////////////////////////////////////////////////////////////
49
50template <> void
51dump(full_attr_map_t const & val, string & out)
52{
53 ostringstream oss;
54 for (full_attr_map_t::const_iterator i = val.begin(); i != val.end(); ++i)
55 oss << "attr key: '" << i->first << "'\n"
56 << " status: " << (i->second.first ? "live" : "dead") << '\n'
57 << " value: '" << i->second.second << "'\n";
58 out = oss.str();
59}
60
61template <> void
62dump(set<revision_id> const & revids, string & out)
63{
64 out.clear();
65 bool first = true;
66 for (set<revision_id>::const_iterator i = revids.begin();
67 i != revids.end(); ++i)
68 {
69 if (!first)
70 out += ", ";
71 first = false;
72 out += i->inner()();
73 }
74}
75
76template <> void
77dump(marking_t const & marking, string & out)
78{
79 ostringstream oss;
80 string tmp;
81 oss << "birth_revision: " << marking.birth_revision << '\n';
82 dump(marking.parent_name, tmp);
83 oss << "parent_name: " << tmp << '\n';
84 dump(marking.file_content, tmp);
85 oss << "file_content: " << tmp << '\n';
86 oss << "attrs (number: " << marking.attrs.size() << "):\n";
87 for (map<attr_key, set<revision_id> >::const_iterator
88 i = marking.attrs.begin(); i != marking.attrs.end(); ++i)
89 {
90 dump(i->second, tmp);
91 oss << " " << i->first << ": " << tmp << '\n';
92 }
93 out = oss.str();
94}
95
96template <> void
97dump(marking_map const & markings, string & out)
98{
99 ostringstream oss;
100 for (marking_map::const_iterator i = markings.begin();
101 i != markings.end();
102 ++i)
103 {
104 oss << "Marking for " << i->first << ":\n";
105 string marking_str, indented_marking_str;
106 dump(i->second, marking_str);
107 prefix_lines_with(" ", marking_str, indented_marking_str);
108 oss << indented_marking_str << '\n';
109 }
110 out = oss.str();
111}
112
113namespace
114{
115 //
116 // We have a few concepts of "nullness" here:
117 //
118 // - the_null_node is a node_id. It does not correspond to a real node;
119 // it's an id you use for the parent of the root, or of any node which
120 // is detached.
121 //
122 // - the_null_component is a path_component. It is the *name* of the root
123 // node. Its string representation is "", the empty string.
124 //
125 // - The split_path corresponding to the_null_node is [], the empty vector.
126 //
127 // - The split_path corresponding to the root node is [""], the 1-element
128 // vector containing the_null_component.
129 //
130 // - The split_path corresponding to foo/bar is ["", "foo", "bar"].
131 //
132 // - The only legal one-element split_path is [""], referring to the
133 // root node.
134 //
135 // We do this in order to support the notion of moving the root directory
136 // around, or applying attributes to the root directory (though we will
137 // not support moving the root at this time, since we haven't worked out
138 // all the UI implications yet).
139 //
140
141
142 const node_id first_node = 1;
143 const node_id first_temp_node = widen<node_id, int>(1) << (sizeof(node_id) * 8 - 1);
144 inline bool temp_node(node_id n)
145 {
146 return n & first_temp_node;
147 }
148}
149
150
151node::node(node_id i)
152 : self(i),
153 parent(the_null_node),
154 name(the_null_component)
155{
156}
157
158
159node::node()
160 : self(the_null_node),
161 parent(the_null_node),
162 name(the_null_component)
163{
164}
165
166
167dir_node::dir_node(node_id i)
168 : node(i)
169{
170}
171
172
173dir_node::dir_node()
174 : node()
175{
176}
177
178
179bool
180dir_node::has_child(path_component const & pc) const
181{
182 return children.find(pc) != children.end();
183}
184
185node_t
186dir_node::get_child(path_component const & pc) const
187{
188 return safe_get(children, pc);
189}
190
191
192void
193dir_node::attach_child(path_component const & pc, node_t child)
194{
195 I(null_node(child->parent));
196 I(null_name(child->name));
197 safe_insert(children, make_pair(pc, child));
198 child->parent = this->self;
199 child->name = pc;
200}
201
202
203node_t
204dir_node::detach_child(path_component const & pc)
205{
206 node_t n = get_child(pc);
207 n->parent = the_null_node;
208 n->name = the_null_component;
209 safe_erase(children, pc);
210 return n;
211}
212
213
214node_t
215dir_node::clone()
216{
217 dir_t d = dir_t(new dir_node(self));
218 d->parent = parent;
219 d->name = name;
220 d->attrs = attrs;
221 d->children = children;
222 return d;
223}
224
225
226file_node::file_node(node_id i, file_id const & f)
227 : node(i),
228 content(f)
229{
230}
231
232
233file_node::file_node()
234 : node()
235{
236}
237
238
239node_t
240file_node::clone()
241{
242 file_t f = file_t(new file_node(self, content));
243 f->parent = parent;
244 f->name = name;
245 f->attrs = attrs;
246 return f;
247}
248
249template <> void
250dump(node_t const & n, string & out)
251{
252 ostringstream oss;
253 string name;
254 dump(n->name, name);
255 oss << "address: " << n << " (uses: " << n.use_count() << ")\n"
256 << "self: " << n->self << '\n'
257 << "parent: " << n->parent << '\n'
258 << "name: " << name << '\n';
259 string attr_map_s;
260 dump(n->attrs, attr_map_s);
261 oss << "attrs:\n" << attr_map_s;
262 oss << "type: ";
263 if (is_file_t(n))
264 oss << "file\n"
265 << "content: " << downcast_to_file_t(n)->content << '\n';
266 else
267 {
268 oss << "dir\n";
269 dir_map const & c = downcast_to_dir_t(n)->children;
270 oss << "children: " << c.size() << '\n';
271 for (dir_map::const_iterator i = c.begin(); i != c.end(); ++i)
272 {
273 dump(i->first, name);
274 oss << " " << name << " -> " << i->second << '\n';
275 }
276 }
277 out = oss.str();
278}
279
280// helper
281void
282roster_t::do_deep_copy_from(roster_t const & other)
283{
284 MM(*this);
285 MM(other);
286 I(!root_dir);
287 I(nodes.empty());
288 for (node_map::const_iterator i = other.nodes.begin(); i != other.nodes.end();
289 ++i)
290 safe_insert(nodes, make_pair(i->first, i->second->clone()));
291 for (node_map::iterator i = nodes.begin(); i != nodes.end(); ++i)
292 if (is_dir_t(i->second))
293 {
294 dir_map & children = downcast_to_dir_t(i->second)->children;
295 for (dir_map::iterator j = children.begin(); j != children.end(); ++j)
296 j->second = safe_get(nodes, j->second->self);
297 }
298 if (other.root_dir)
299 root_dir = downcast_to_dir_t(safe_get(nodes, other.root_dir->self));
300}
301
302roster_t::roster_t(roster_t const & other)
303{
304 do_deep_copy_from(other);
305}
306
307roster_t &
308roster_t::operator=(roster_t const & other)
309{
310 root_dir.reset();
311 nodes.clear();
312 do_deep_copy_from(other);
313 return *this;
314}
315
316
317struct
318dfs_iter
319{
320
321 dir_t root;
322 bool return_root;
323 stack< pair<dir_t, dir_map::const_iterator> > stk;
324
325
326 dfs_iter(dir_t r)
327 : root(r), return_root(root)
328 {
329 if (root && !root->children.empty())
330 stk.push(make_pair(root, root->children.begin()));
331 }
332
333
334 bool finished() const
335 {
336 return (!return_root) && stk.empty();
337 }
338
339
340 node_t operator*() const
341 {
342 I(!finished());
343 if (return_root)
344 return root;
345 else
346 {
347 I(!stk.empty());
348 return stk.top().second->second;
349 }
350 }
351
352
353 void operator++()
354 {
355 I(!finished());
356
357 if (return_root)
358 {
359 return_root = false;
360 return;
361 }
362
363 // we're not finished, so we need to set up so operator* will return the
364 // right thing.
365 node_t ntmp = stk.top().second->second;
366 if (is_dir_t(ntmp))
367 {
368 dir_t dtmp = downcast_to_dir_t(ntmp);
369 stk.push(make_pair(dtmp, dtmp->children.begin()));
370 }
371 else
372 ++(stk.top().second);
373
374 while (!stk.empty()
375 && stk.top().second == stk.top().first->children.end())
376 {
377 stk.pop();
378 if (!stk.empty())
379 ++stk.top().second;
380 }
381 }
382};
383
384
385bool
386roster_t::has_root() const
387{
388 return static_cast<bool>(root_dir);
389}
390
391
392inline bool
393same_type(node_t a, node_t b)
394{
395 return is_file_t(a) == is_file_t(b);
396}
397
398
399inline bool
400shallow_equal(node_t a, node_t b,
401 bool shallow_compare_dir_children,
402 bool compare_file_contents)
403{
404 if (a->self != b->self)
405 return false;
406
407 if (a->parent != b->parent)
408 return false;
409
410 if (a->name != b->name)
411 return false;
412
413 if (a->attrs != b->attrs)
414 return false;
415
416 if (! same_type(a,b))
417 return false;
418
419 if (is_file_t(a))
420 {
421 if (compare_file_contents)
422 {
423 file_t fa = downcast_to_file_t(a);
424 file_t fb = downcast_to_file_t(b);
425 if (!(fa->content == fb->content))
426 return false;
427 }
428 }
429 else
430 {
431 dir_t da = downcast_to_dir_t(a);
432 dir_t db = downcast_to_dir_t(b);
433
434 if (shallow_compare_dir_children)
435 {
436 if (da->children.size() != db->children.size())
437 return false;
438
439 dir_map::const_iterator
440 i = da->children.begin(),
441 j = db->children.begin();
442
443 while (i != da->children.end() && j != db->children.end())
444 {
445 if (i->first != j->first)
446 return false;
447 if (i->second->self != j->second->self)
448 return false;
449 ++i;
450 ++j;
451 }
452 I(i == da->children.end() && j == db->children.end());
453 }
454 }
455 return true;
456}
457
458
459// FIXME_ROSTERS: why does this do two loops? why does it pass 'true' to
460// shallow_equal?
461// -- njs
462bool
463roster_t::operator==(roster_t const & other) const
464{
465 node_map::const_iterator i = nodes.begin(), j = other.nodes.begin();
466 while (i != nodes.end() && j != other.nodes.end())
467 {
468 if (i->first != j->first)
469 return false;
470 if (!shallow_equal(i->second, j->second, true))
471 return false;
472 ++i;
473 ++j;
474 }
475
476 if (i != nodes.end() || j != other.nodes.end())
477 return false;
478
479 dfs_iter p(root_dir), q(other.root_dir);
480 while (! (p.finished() || q.finished()))
481 {
482 if (!shallow_equal(*p, *q, true))
483 return false;
484 ++p;
485 ++q;
486 }
487
488 if (!(p.finished() && q.finished()))
489 return false;
490
491 return true;
492}
493
494// This is exactly the same as roster_t::operator== (and the same FIXME
495// above applies) except that it does not compare file contents.
496bool
497equal_shapes(roster_t const & a, roster_t const & b)
498{
499 node_map::const_iterator i = a.nodes.begin(), j = b.nodes.begin();
500 while (i != a.nodes.end() && j != b.nodes.end())
501 {
502 if (i->first != j->first)
503 return false;
504 if (!shallow_equal(i->second, j->second, true, false))
505 return false;
506 ++i;
507 ++j;
508 }
509
510 if (i != a.nodes.end() || j != b.nodes.end())
511 return false;
512
513 dfs_iter p(a.root_dir), q(b.root_dir);
514 while (! (p.finished() || q.finished()))
515 {
516 if (!shallow_equal(*p, *q, true, false))
517 return false;
518 ++p;
519 ++q;
520 }
521
522 if (!(p.finished() && q.finished()))
523 return false;
524
525 return true;
526}
527
528
529node_t
530roster_t::get_node(split_path const & sp) const
531{
532 split_path dirname;
533 path_component basename;
534 dirname_basename(sp, dirname, basename);
535
536 MM(sp);
537 MM(*this);
538
539 I(has_root());
540
541 if (dirname.empty())
542 {
543 I(null_name(basename));
544 return root_dir;
545 }
546
547 dir_t d = root_dir;
548 for (split_path::const_iterator i = dirname.begin()+1; i != dirname.end(); ++i)
549 d = downcast_to_dir_t(d->get_child(*i));
550 return d->get_child(basename);
551}
552
553bool
554roster_t::has_node(node_id n) const
555{
556 return nodes.find(n) != nodes.end();
557}
558
559bool
560roster_t::is_root(node_id n) const
561{
562 return has_root() && root_dir->self == n;
563}
564
565bool
566roster_t::has_node(split_path const & sp) const
567{
568 split_path dirname;
569 path_component basename;
570 dirname_basename(sp, dirname, basename);
571
572 if (dirname.empty())
573 {
574 I(null_name(basename));
575 return has_root();
576 }
577
578 // If we have no root, we *definitely* don't have a non-root path
579 if (!has_root())
580 return false;
581
582 dir_t d = root_dir;
583 for (split_path::const_iterator i = dirname.begin()+1; i != dirname.end(); ++i)
584 {
585 if (d->children.find(*i) == d->children.end())
586 return false;
587 node_t child = d->get_child(*i);
588 if (!is_dir_t(child))
589 return false;
590 d = downcast_to_dir_t(child);
591 }
592 return d->children.find(basename) != d->children.end();
593}
594
595
596
597node_t
598roster_t::get_node(node_id nid) const
599{
600 return safe_get(nodes, nid);
601}
602
603
604void
605roster_t::get_name(node_id nid, split_path & sp) const
606{
607 I(!null_node(nid));
608 sp.clear();
609 while (!null_node(nid))
610 {
611 node_t n = get_node(nid);
612 sp.push_back(n->name);
613 nid = n->parent;
614 }
615 reverse(sp.begin(), sp.end());
616}
617
618
619void
620roster_t::replace_node_id(node_id from, node_id to)
621{
622 I(!null_node(from));
623 I(!null_node(to));
624 node_t n = get_node(from);
625 safe_erase(nodes, from);
626 safe_insert(nodes, make_pair(to, n));
627 n->self = to;
628
629 if (is_dir_t(n))
630 {
631 dir_t d = downcast_to_dir_t(n);
632 for (dir_map::iterator i = d->children.begin(); i != d->children.end(); ++i)
633 {
634 I(i->second->parent == from);
635 i->second->parent = to;
636 }
637 }
638}
639
640
641// this records the old location into the old_locations member, to prevent the
642// same node from being re-attached at the same place.
643node_id
644roster_t::detach_node(split_path const & pth)
645{
646 split_path dirname;
647 path_component basename;
648 dirname_basename(pth, dirname, basename);
649
650 I(has_root());
651 if (dirname.empty())
652 {
653 // detaching the root dir
654 I(null_name(basename));
655 node_id root_id = root_dir->self;
656 safe_insert(old_locations,
657 make_pair(root_id, make_pair(root_dir->parent, root_dir->name)));
658 // clear ("reset") the root_dir shared_pointer
659 root_dir.reset();
660 I(!has_root());
661 return root_id;
662 }
663
664 dir_t parent = downcast_to_dir_t(get_node(dirname));
665 node_id nid = parent->detach_child(basename)->self;
666 safe_insert(old_locations,
667 make_pair(nid, make_pair(parent->self, basename)));
668 I(!null_node(nid));
669 return nid;
670}
671
672void
673roster_t::detach_node(node_id nid)
674{
675 node_t n = get_node(nid);
676 if (null_node(n->parent))
677 {
678 // detaching the root dir
679 I(null_name(n->name));
680 safe_insert(old_locations,
681 make_pair(nid, make_pair(n->parent, n->name)));
682 root_dir.reset();
683 I(!has_root());
684 }
685 else
686 {
687 path_component name = n->name;
688 dir_t parent = downcast_to_dir_t(get_node(n->parent));
689 I(parent->detach_child(name) == n);
690 safe_insert(old_locations,
691 make_pair(nid, make_pair(n->parent, name)));
692 }
693}
694
695void
696roster_t::drop_detached_node(node_id nid)
697{
698 // ensure the node is already detached
699 node_t n = get_node(nid);
700 I(null_node(n->parent));
701 I(null_name(n->name));
702 // if it's a dir, make sure it's empty
703 if (is_dir_t(n))
704 I(downcast_to_dir_t(n)->children.empty());
705 // all right, kill it
706 safe_erase(nodes, nid);
707 // can use safe_erase here, because while not every detached node appears in
708 // old_locations, all those that used to be in the tree do. and you should
709 // only ever be dropping nodes that were detached, not nodes that you just
710 // created and that have never been attached.
711 safe_erase(old_locations, nid);
712}
713
714
715// this creates a node in a detached state, but it does _not_ insert an entry
716// for it into the old_locations member, because there is no old_location to
717// forbid
718node_id
719roster_t::create_dir_node(node_id_source & nis)
720{
721 node_id nid = nis.next();
722 create_dir_node(nid);
723 return nid;
724}
725void
726roster_t::create_dir_node(node_id nid)
727{
728 dir_t d = dir_t(new dir_node());
729 d->self = nid;
730 safe_insert(nodes, make_pair(nid, d));
731}
732
733
734// this creates a node in a detached state, but it does _not_ insert an entry
735// for it into the old_locations member, because there is no old_location to
736// forbid
737node_id
738roster_t::create_file_node(file_id const & content, node_id_source & nis)
739{
740 node_id nid = nis.next();
741 create_file_node(content, nid);
742 return nid;
743}
744void
745roster_t::create_file_node(file_id const & content, node_id nid)
746{
747 file_t f = file_t(new file_node());
748 f->self = nid;
749 f->content = content;
750 safe_insert(nodes, make_pair(nid, f));
751}
752
753void
754roster_t::attach_node(node_id nid, split_path const & dst)
755{
756 split_path dirname;
757 path_component basename;
758 dirname_basename(dst, dirname, basename);
759
760 MM(dst);
761
762 if (dirname.empty())
763 // attaching the root node
764 attach_node(nid, the_null_node, basename);
765 else
766 attach_node(nid, get_node(dirname)->self, basename);
767}
768
769void
770roster_t::attach_node(node_id nid, node_id parent, path_component name)
771{
772 node_t n = get_node(nid);
773
774 I(!null_node(n->self));
775 // ensure the node is already detached (as best one can)
776 I(null_node(n->parent));
777 I(null_name(n->name));
778
779 // this iterator might point to old_locations.end(), because old_locations
780 // only includes entries for renames, not new nodes
781 map<node_id, pair<node_id, path_component> >::iterator
782 i = old_locations.find(nid);
783
784 if (null_node(parent) || null_name(name))
785 {
786 I(null_node(parent) && null_name(name));
787 I(null_node(n->parent));
788 I(null_name(n->name));
789 I(!has_root());
790 root_dir = downcast_to_dir_t(n);
791 I(i == old_locations.end() || i->second != make_pair(root_dir->parent,
792 root_dir->name));
793 }
794 else
795 {
796 dir_t parent_n = downcast_to_dir_t(get_node(parent));
797 parent_n->attach_child(name, n);
798 I(i == old_locations.end() || i->second != make_pair(n->parent, n->name));
799 }
800
801 if (i != old_locations.end())
802 old_locations.erase(i);
803}
804
805void
806roster_t::apply_delta(split_path const & pth,
807 file_id const & old_id,
808 file_id const & new_id)
809{
810 file_t f = downcast_to_file_t(get_node(pth));
811 I(f->content == old_id);
812 I(!null_node(f->self));
813 I(!(f->content == new_id));
814 f->content = new_id;
815}
816
817void
818roster_t::set_content(node_id nid, file_id const & new_id)
819{
820 file_t f = downcast_to_file_t(get_node(nid));
821 I(!(f->content == new_id));
822 f->content = new_id;
823}
824
825
826void
827roster_t::clear_attr(split_path const & pth,
828 attr_key const & name)
829{
830 set_attr(pth, name, make_pair(false, attr_value()));
831}
832
833void
834roster_t::erase_attr(node_id nid,
835 attr_key const & name)
836{
837 node_t n = get_node(nid);
838 safe_erase(n->attrs, name);
839}
840
841void
842roster_t::set_attr(split_path const & pth,
843 attr_key const & name,
844 attr_value const & val)
845{
846 set_attr(pth, name, make_pair(true, val));
847}
848
849
850void
851roster_t::set_attr(split_path const & pth,
852 attr_key const & name,
853 pair<bool, attr_value> const & val)
854{
855 node_t n = get_node(pth);
856 I(val.first || val.second().empty());
857 I(!null_node(n->self));
858 full_attr_map_t::iterator i = n->attrs.find(name);
859 if (i == n->attrs.end())
860 i = safe_insert(n->attrs, make_pair(name,
861 make_pair(false, attr_value())));
862 I(i->second != val);
863 i->second = val;
864}
865
866// same as above, but allowing <unknown> -> <dead> transition
867void
868roster_t::set_attr_unknown_to_dead_ok(node_id nid,
869 attr_key const & name,
870 pair<bool, attr_value> const & val)
871{
872 node_t n = get_node(nid);
873 I(val.first || val.second().empty());
874 full_attr_map_t::iterator i = n->attrs.find(name);
875 if (i != n->attrs.end())
876 I(i->second != val);
877 n->attrs[name] = val;
878}
879
880bool
881roster_t::get_attr(split_path const & pth,
882 attr_key const & name,
883 attr_value & val) const
884{
885 I(has_node(pth));
886
887 node_t n = get_node(pth);
888 full_attr_map_t::const_iterator i = n->attrs.find(name);
889 if (i != n->attrs.end() && i->second.first)
890 {
891 val = i->second.second;
892 return true;
893 }
894 return false;
895}
896
897
898template <> void
899dump(roster_t const & val, string & out)
900{
901 ostringstream oss;
902 if (val.root_dir)
903 oss << "Root node: " << val.root_dir->self << '\n'
904 << " at " << val.root_dir << ", uses: " << val.root_dir.use_count() << '\n';
905 else
906 oss << "root dir is NULL\n";
907 for (node_map::const_iterator i = val.nodes.begin(); i != val.nodes.end(); ++i)
908 {
909 oss << "\nNode " << i->first << '\n';
910 string node_s;
911 dump(i->second, node_s);
912 oss << node_s;
913 }
914 out = oss.str();
915}
916
917void
918roster_t::check_sane(bool temp_nodes_ok) const
919{
920 I(has_root());
921 node_map::const_iterator ri;
922
923 I(old_locations.empty());
924
925 for (ri = nodes.begin();
926 ri != nodes.end();
927 ++ri)
928 {
929 node_id nid = ri->first;
930 I(!null_node(nid));
931 if (!temp_nodes_ok)
932 I(!temp_node(nid));
933 node_t n = ri->second;
934 I(n->self == nid);
935 if (is_dir_t(n))
936 {
937 if (null_name(n->name) || null_node(n->parent))
938 I(null_name(n->name) && null_node(n->parent));
939 else
940 I(!null_name(n->name) && !null_node(n->parent));
941 }
942 else
943 {
944 I(!null_name(n->name) && !null_node(n->parent));
945 I(!null_id(downcast_to_file_t(n)->content));
946 }
947 for (full_attr_map_t::const_iterator i = n->attrs.begin(); i != n->attrs.end(); ++i)
948 I(i->second.first || i->second.second().empty());
949 if (n != root_dir)
950 {
951 I(!null_node(n->parent));
952 I(downcast_to_dir_t(get_node(n->parent))->get_child(n->name) == n);
953 }
954
955 }
956
957 I(has_root());
958 size_t maxdepth = nodes.size();
959 for (dfs_iter i(root_dir); !i.finished(); ++i)
960 {
961 I(*i == get_node((*i)->self));
962 I(maxdepth-- > 0);
963 }
964 I(maxdepth == 0);
965}
966
967void
968roster_t::check_sane_against(marking_map const & markings, bool temp_nodes_ok) const
969{
970
971 check_sane(temp_nodes_ok);
972
973 node_map::const_iterator ri;
974 marking_map::const_iterator mi;
975
976 for (ri = nodes.begin(), mi = markings.begin();
977 ri != nodes.end() && mi != markings.end();
978 ++ri, ++mi)
979 {
980 I(!null_id(mi->second.birth_revision));
981 I(!mi->second.parent_name.empty());
982
983 if (is_file_t(ri->second))
984 I(!mi->second.file_content.empty());
985 else
986 I(mi->second.file_content.empty());
987
988 full_attr_map_t::const_iterator rai;
989 map<attr_key, set<revision_id> >::const_iterator mai;
990 for (rai = ri->second->attrs.begin(), mai = mi->second.attrs.begin();
991 rai != ri->second->attrs.end() && mai != mi->second.attrs.end();
992 ++rai, ++mai)
993 {
994 I(rai->first == mai->first);
995 I(!mai->second.empty());
996 }
997 I(rai == ri->second->attrs.end() && mai == mi->second.attrs.end());
998 // TODO: attrs
999 }
1000
1001 I(ri == nodes.end() && mi == markings.end());
1002}
1003
1004
1005temp_node_id_source::temp_node_id_source()
1006 : curr(first_temp_node)
1007{}
1008
1009node_id
1010temp_node_id_source::next()
1011{
1012 node_id n = curr++;
1013 I(temp_node(n));
1014 return n;
1015}
1016
1017editable_roster_base::editable_roster_base(roster_t & r, node_id_source & nis)
1018 : r(r), nis(nis)
1019{}
1020
1021node_id
1022editable_roster_base::detach_node(split_path const & src)
1023{
1024 // L(FL("detach_node('%s')") % file_path(src));
1025 return r.detach_node(src);
1026}
1027
1028void
1029editable_roster_base::drop_detached_node(node_id nid)
1030{
1031 // L(FL("drop_detached_node(%d)") % nid);
1032 r.drop_detached_node(nid);
1033}
1034
1035node_id
1036editable_roster_base::create_dir_node()
1037{
1038 // L(FL("create_dir_node()"));
1039 node_id n = r.create_dir_node(nis);
1040 // L(FL("create_dir_node() -> %d") % n);
1041 return n;
1042}
1043
1044node_id
1045editable_roster_base::create_file_node(file_id const & content)
1046{
1047 // L(FL("create_file_node('%s')") % content);
1048 node_id n = r.create_file_node(content, nis);
1049 // L(FL("create_file_node('%s') -> %d") % content % n);
1050 return n;
1051}
1052
1053void
1054editable_roster_base::attach_node(node_id nid, split_path const & dst)
1055{
1056 // L(FL("attach_node(%d, '%s')") % nid % file_path(dst));
1057 MM(dst);
1058 MM(this->r);
1059 r.attach_node(nid, dst);
1060}
1061
1062void
1063editable_roster_base::apply_delta(split_path const & pth,
1064 file_id const & old_id,
1065 file_id const & new_id)
1066{
1067 // L(FL("clear_attr('%s', '%s', '%s')") % file_path(pth) % old_id % new_id);
1068 r.apply_delta(pth, old_id, new_id);
1069}
1070
1071void
1072editable_roster_base::clear_attr(split_path const & pth,
1073 attr_key const & name)
1074{
1075 // L(FL("clear_attr('%s', '%s')") % file_path(pth) % name);
1076 r.clear_attr(pth, name);
1077}
1078
1079void
1080editable_roster_base::set_attr(split_path const & pth,
1081 attr_key const & name,
1082 attr_value const & val)
1083{
1084 // L(FL("set_attr('%s', '%s', '%s')") % file_path(pth) % name % val);
1085 r.set_attr(pth, name, val);
1086}
1087
1088void
1089editable_roster_base::commit()
1090{
1091}
1092
1093namespace
1094{
1095 struct true_node_id_source
1096 : public node_id_source
1097 {
1098 true_node_id_source(app_state & app) : app(app) {}
1099 virtual node_id next()
1100 {
1101 node_id n = app.db.next_node_id();
1102 I(!temp_node(n));
1103 return n;
1104 }
1105 app_state & app;
1106 };
1107
1108
1109 class editable_roster_for_merge
1110 : public editable_roster_base
1111 {
1112 public:
1113 set<node_id> new_nodes;
1114 editable_roster_for_merge(roster_t & r, node_id_source & nis)
1115 : editable_roster_base(r, nis)
1116 {}
1117 virtual node_id create_dir_node()
1118 {
1119 node_id nid = this->editable_roster_base::create_dir_node();
1120 new_nodes.insert(nid);
1121 return nid;
1122 }
1123 virtual node_id create_file_node(file_id const & content)
1124 {
1125 node_id nid = this->editable_roster_base::create_file_node(content);
1126 new_nodes.insert(nid);
1127 return nid;
1128 }
1129 };
1130
1131
1132 void union_new_nodes(roster_t & a, set<node_id> & a_new,
1133 roster_t & b, set<node_id> & b_new,
1134 node_id_source & nis)
1135 {
1136 // We must not replace a node whose id is in both a_new and b_new
1137 // with a new temp id that is already in either set. b_new is
1138 // destructively modified, so record the union of both sets now.
1139 set<node_id> all_new_nids;
1140 std::set_union(a_new.begin(), a_new.end(),
1141 b_new.begin(), b_new.end(),
1142 std::inserter(all_new_nids, all_new_nids.begin()));
1143
1144 // First identify nodes that are new in A but not in B, or new in both.
1145 for (set<node_id>::const_iterator i = a_new.begin(); i != a_new.end(); ++i)
1146 {
1147 node_id const aid = *i;
1148 split_path sp;
1149 // SPEEDUP?: climb out only so far as is necessary to find a shared
1150 // id? possibly faster (since usually will get a hit immediately),
1151 // but may not be worth the effort (since it doesn't take that long to
1152 // get out in any case)
1153 a.get_name(aid, sp);
1154 node_id bid = b.get_node(sp)->self;
1155 if (b_new.find(bid) != b_new.end())
1156 {
1157 I(temp_node(bid));
1158 node_id new_nid;
1159 do
1160 new_nid = nis.next();
1161 while (all_new_nids.find(new_nid) != all_new_nids.end());
1162
1163 a.replace_node_id(aid, new_nid);
1164 b.replace_node_id(bid, new_nid);
1165 b_new.erase(bid);
1166 }
1167 else
1168 {
1169 a.replace_node_id(aid, bid);
1170 }
1171 }
1172
1173 // Now identify nodes that are new in B but not A.
1174 for (set<node_id>::const_iterator i = b_new.begin(); i != b_new.end(); i++)
1175 {
1176 node_id const bid = *i;
1177 split_path sp;
1178 // SPEEDUP?: climb out only so far as is necessary to find a shared
1179 // id? possibly faster (since usually will get a hit immediately),
1180 // but may not be worth the effort (since it doesn't take that long to
1181 // get out in any case)
1182 b.get_name(bid, sp);
1183 node_id aid = a.get_node(sp)->self;
1184 I(a_new.find(aid) == a_new.end());
1185 b.replace_node_id(bid, aid);
1186 }
1187 }
1188
1189 void
1190 union_corpses(roster_t & left, roster_t & right)
1191 {
1192 // left and right should be equal, except that each may have some attr
1193 // corpses that the other does not
1194 map<node_id, node_t>::const_iterator left_i = left.all_nodes().begin();
1195 map<node_id, node_t>::const_iterator right_i = right.all_nodes().begin();
1196 while (left_i != left.all_nodes().end() || right_i != right.all_nodes().end())
1197 {
1198 I(left_i->second->self == right_i->second->self);
1199 parallel::iter<full_attr_map_t> j(left_i->second->attrs,
1200 right_i->second->attrs);
1201 // we batch up the modifications until the end, so as not to be
1202 // changing things around under the parallel::iter's feet
1203 set<attr_key> left_missing, right_missing;
1204 while (j.next())
1205 {
1206 MM(j);
1207 switch (j.state())
1208 {
1209 case parallel::invalid:
1210 I(false);
1211
1212 case parallel::in_left:
1213 // this is a corpse
1214 I(!j.left_data().first);
1215 right_missing.insert(j.left_key());
1216 break;
1217
1218 case parallel::in_right:
1219 // this is a corpse
1220 I(!j.right_data().first);
1221 left_missing.insert(j.right_key());
1222 break;
1223
1224 case parallel::in_both:
1225 break;
1226 }
1227 }
1228 for (set<attr_key>::const_iterator j = left_missing.begin();
1229 j != left_missing.end(); ++j)
1230 safe_insert(left_i->second->attrs,
1231 make_pair(*j, make_pair(false, attr_value())));
1232 for (set<attr_key>::const_iterator j = right_missing.begin();
1233 j != right_missing.end(); ++j)
1234 safe_insert(right_i->second->attrs,
1235 make_pair(*j, make_pair(false, attr_value())));
1236 ++left_i;
1237 ++right_i;
1238 }
1239 I(left_i == left.all_nodes().end());
1240 I(right_i == right.all_nodes().end());
1241 }
1242
1243 // After this, left should == right, and there should be no temporary ids.
1244 // Destroys sets, because that's handy (it has to scan over both, but it can
1245 // skip some double-scanning)
1246 void
1247 unify_rosters(roster_t & left, set<node_id> & left_new,
1248 roster_t & right, set<node_id> & right_new,
1249 node_id_source & nis)
1250 {
1251 // Our basic problem is this: when interpreting a revision with multiple
1252 // csets, those csets all give enough information for us to get the same
1253 // manifest, and even a bit more than that. However, there is some
1254 // information that is not exposed at the manifest level, and csets alone
1255 // do not give us all we need. This function is responsible taking the
1256 // two rosters that we get from pure cset application, and fixing them up
1257 // so that they are wholly identical.
1258
1259 // The first thing that is missing is identification of files. If one
1260 // cset says "add_file" and the other says nothing, then the add_file is
1261 // not really an add_file. One of our rosters will have a temp id for
1262 // this file, and the other will not. In this case, we replace the temp
1263 // id with the other side's permanent id. However, if both csets say
1264 // "add_file", then this really is a new id; both rosters will have temp
1265 // ids, and we replace both of them with a newly allocated id. After
1266 // this, the two rosters will have identical node_ids at every path.
1267 union_new_nodes(left, left_new, right, right_new, nis);
1268
1269 // The other thing we need to fix up is attr corpses. Live attrs are made
1270 // identical by the csets; but if, say, on one side of a fork an attr is
1271 // added and then deleted, then one of our incoming merge rosters will
1272 // have a corpse for that attr, and the other will not. We need to make
1273 // sure at both of them end up with the corpse. This function fixes up
1274 // that.
1275 union_corpses(left, right);
1276 }
1277
1278 template <typename T> void
1279 mark_unmerged_scalar(set<revision_id> const & parent_marks,
1280 T const & parent_val,
1281 revision_id const & new_rid,
1282 T const & new_val,
1283 set<revision_id> & new_marks)
1284 {
1285 I(new_marks.empty());
1286 if (parent_val == new_val)
1287 new_marks = parent_marks;
1288 else
1289 new_marks.insert(new_rid);
1290 }
1291
1292 // This function implements the case.
1293 // a b1
1294 // \ /
1295 // b2
1296 void
1297 mark_won_merge(set<revision_id> const & a_marks,
1298 set<revision_id> const & a_uncommon_ancestors,
1299 set<revision_id> const & b1_marks,
1300 revision_id const & new_rid,
1301 set<revision_id> & new_marks)
1302 {
1303 for (set<revision_id>::const_iterator i = a_marks.begin();
1304 i != a_marks.end(); ++i)
1305 {
1306 if (a_uncommon_ancestors.find(*i) != a_uncommon_ancestors.end())
1307 {
1308 // at least one element of *(a) is not an ancestor of b1
1309 new_marks.clear();
1310 new_marks.insert(new_rid);
1311 return;
1312 }
1313 }
1314 // all elements of *(a) are ancestors of b1; this was a clean merge to b,
1315 // so copy forward the marks.
1316 new_marks = b1_marks;
1317 }
1318
1319 template <typename T> void
1320 mark_merged_scalar(set<revision_id> const & left_marks,
1321 set<revision_id> const & left_uncommon_ancestors,
1322 T const & left_val,
1323 set<revision_id> const & right_marks,
1324 set<revision_id> const & right_uncommon_ancestors,
1325 T const & right_val,
1326 revision_id const & new_rid,
1327 T const & new_val,
1328 set<revision_id> & new_marks)
1329 {
1330 I(new_marks.empty());
1331
1332 // let's not depend on T::operator!= being defined, only on T::operator==
1333 // being defined.
1334 bool diff_from_left = !(new_val == left_val);
1335 bool diff_from_right = !(new_val == right_val);
1336
1337 // some quick sanity checks
1338 for (set<revision_id>::const_iterator i = left_marks.begin();
1339 i != left_marks.end(); ++i)
1340 I(right_uncommon_ancestors.find(*i) == right_uncommon_ancestors.end());
1341 for (set<revision_id>::const_iterator i = right_marks.begin();
1342 i != right_marks.end(); ++i)
1343 I(left_uncommon_ancestors.find(*i) == left_uncommon_ancestors.end());
1344
1345 if (diff_from_left && diff_from_right)
1346 new_marks.insert(new_rid);
1347
1348 else if (diff_from_left && !diff_from_right)
1349 mark_won_merge(left_marks, left_uncommon_ancestors, right_marks,
1350 new_rid, new_marks);
1351
1352 else if (!diff_from_left && diff_from_right)
1353 mark_won_merge(right_marks, right_uncommon_ancestors, left_marks,
1354 new_rid, new_marks);
1355
1356 else
1357 {
1358 // this is the case
1359 // a a
1360 // \ /
1361 // a
1362 // so we simply union the mark sets. This is technically not
1363 // quite the canonical multi-*-merge thing to do; in the case
1364 // a1*
1365 // / \ (blah blah; avoid multi-line-comment warning)
1366 // b a2
1367 // | |
1368 // a3* |
1369 // \ /
1370 // a4
1371 // we will set *(a4) = {a1, a3}, even though the minimal
1372 // common ancestor set is {a3}. we could fix this by running
1373 // erase_ancestors. However, there isn't really any point;
1374 // the only operation performed on *(a4) is to test *(a4) > R
1375 // for some revision R. The truth-value of this test cannot
1376 // be affected by added new revisions to *(a4) that are
1377 // ancestors of revisions that are already in *(a4).
1378 set_union(left_marks.begin(), left_marks.end(),
1379 right_marks.begin(), right_marks.end(),
1380 inserter(new_marks, new_marks.begin()));
1381 }
1382 }
1383
1384 void
1385 mark_new_node(revision_id const & new_rid, node_t n, marking_t & new_marking)
1386 {
1387 new_marking.birth_revision = new_rid;
1388 I(new_marking.parent_name.empty());
1389 new_marking.parent_name.insert(new_rid);
1390 I(new_marking.file_content.empty());
1391 if (is_file_t(n))
1392 new_marking.file_content.insert(new_rid);
1393 I(new_marking.attrs.empty());
1394 set<revision_id> singleton;
1395 singleton.insert(new_rid);
1396 for (full_attr_map_t::const_iterator i = n->attrs.begin();
1397 i != n->attrs.end(); ++i)
1398 new_marking.attrs.insert(make_pair(i->first, singleton));
1399 }
1400
1401 void
1402 mark_unmerged_node(marking_t const & parent_marking, node_t parent_n,
1403 revision_id const & new_rid, node_t n,
1404 marking_t & new_marking)
1405 {
1406 // SPEEDUP?: the common case here is that the parent and child nodes are
1407 // exactly identical, in which case the markings are also exactly
1408 // identical. There might be a win in first doing an overall
1409 // comparison/copy, in case it can be better optimized as a block
1410 // comparison and a block copy...
1411
1412 I(same_type(parent_n, n) && parent_n->self == n->self);
1413
1414 new_marking.birth_revision = parent_marking.birth_revision;
1415
1416 mark_unmerged_scalar(parent_marking.parent_name,
1417 make_pair(parent_n->parent, parent_n->name),
1418 new_rid,
1419 make_pair(n->parent, n->name),
1420 new_marking.parent_name);
1421
1422 if (is_file_t(n))
1423 mark_unmerged_scalar(parent_marking.file_content,
1424 downcast_to_file_t(parent_n)->content,
1425 new_rid,
1426 downcast_to_file_t(n)->content,
1427 new_marking.file_content);
1428
1429 for (full_attr_map_t::const_iterator i = n->attrs.begin();
1430 i != n->attrs.end(); ++i)
1431 {
1432 set<revision_id> & new_marks = new_marking.attrs[i->first];
1433 I(new_marks.empty());
1434 full_attr_map_t::const_iterator j = parent_n->attrs.find(i->first);
1435 if (j == parent_n->attrs.end())
1436 new_marks.insert(new_rid);
1437 else
1438 mark_unmerged_scalar(safe_get(parent_marking.attrs, i->first),
1439 j->second,
1440 new_rid, i->second, new_marks);
1441 }
1442 }
1443
1444 void
1445 mark_merged_node(marking_t const & left_marking,
1446 set<revision_id> const & left_uncommon_ancestors,
1447 node_t ln,
1448 marking_t const & right_marking,
1449 set<revision_id> const & right_uncommon_ancestors,
1450 node_t rn,
1451 revision_id const & new_rid,
1452 node_t n,
1453 marking_t & new_marking)
1454 {
1455 I(same_type(ln, n) && same_type(rn, n));
1456 I(left_marking.birth_revision == right_marking.birth_revision);
1457 new_marking.birth_revision = left_marking.birth_revision;
1458
1459 // name
1460 mark_merged_scalar(left_marking.parent_name, left_uncommon_ancestors,
1461 make_pair(ln->parent, ln->name),
1462 right_marking.parent_name, right_uncommon_ancestors,
1463 make_pair(rn->parent, rn->name),
1464 new_rid,
1465 make_pair(n->parent, n->name),
1466 new_marking.parent_name);
1467 // content
1468 if (is_file_t(n))
1469 {
1470 file_t f = downcast_to_file_t(n);
1471 file_t lf = downcast_to_file_t(ln);
1472 file_t rf = downcast_to_file_t(rn);
1473 mark_merged_scalar(left_marking.file_content, left_uncommon_ancestors,
1474 lf->content,
1475 right_marking.file_content, right_uncommon_ancestors,
1476 rf->content,
1477 new_rid, f->content, new_marking.file_content);
1478 }
1479 // attrs
1480 for (full_attr_map_t::const_iterator i = n->attrs.begin();
1481 i != n->attrs.end(); ++i)
1482 {
1483 attr_key const & key = i->first;
1484 full_attr_map_t::const_iterator li = ln->attrs.find(key);
1485 full_attr_map_t::const_iterator ri = rn->attrs.find(key);
1486 I(new_marking.attrs.find(key) == new_marking.attrs.end());
1487 // [], when used to refer to a non-existent element, default
1488 // constructs that element and returns a reference to it. We make use
1489 // of this here.
1490 set<revision_id> & new_marks = new_marking.attrs[key];
1491
1492 if (li == ln->attrs.end() && ri == rn->attrs.end())
1493 // this is a brand new attribute, never before seen
1494 safe_insert(new_marks, new_rid);
1495
1496 else if (li != ln->attrs.end() && ri == rn->attrs.end())
1497 // only the left side has seen this attr before
1498 mark_unmerged_scalar(safe_get(left_marking.attrs, key),
1499 li->second,
1500 new_rid, i->second, new_marks);
1501
1502 else if (li == ln->attrs.end() && ri != rn->attrs.end())
1503 // only the right side has seen this attr before
1504 mark_unmerged_scalar(safe_get(right_marking.attrs, key),
1505 ri->second,
1506 new_rid, i->second, new_marks);
1507
1508 else
1509 // both sides have seen this attr before
1510 mark_merged_scalar(safe_get(left_marking.attrs, key),
1511 left_uncommon_ancestors,
1512 li->second,
1513 safe_get(right_marking.attrs, key),
1514 right_uncommon_ancestors,
1515 ri->second,
1516 new_rid, i->second, new_marks);
1517 }
1518
1519 // some extra sanity checking -- attributes are not allowed to be deleted,
1520 // so we double check that they haven't.
1521 // SPEEDUP?: this code could probably be made more efficient -- but very
1522 // rarely will any node have more than, say, one attribute, so it probably
1523 // doesn't matter.
1524 for (full_attr_map_t::const_iterator i = ln->attrs.begin();
1525 i != ln->attrs.end(); ++i)
1526 I(n->attrs.find(i->first) != n->attrs.end());
1527 for (full_attr_map_t::const_iterator i = rn->attrs.begin();
1528 i != rn->attrs.end(); ++i)
1529 I(n->attrs.find(i->first) != n->attrs.end());
1530 }
1531
1532} // anonymous namespace
1533
1534
1535// This function is also responsible for verifying ancestry invariants --
1536// those invariants on a roster that involve the structure of the roster's
1537// parents, rather than just the structure of the roster itself.
1538void
1539mark_merge_roster(roster_t const & left_roster,
1540 marking_map const & left_markings,
1541 set<revision_id> const & left_uncommon_ancestors,
1542 roster_t const & right_roster,
1543 marking_map const & right_markings,
1544 set<revision_id> const & right_uncommon_ancestors,
1545 revision_id const & new_rid,
1546 roster_t const & merge,
1547 marking_map & new_markings)
1548{
1549 for (node_map::const_iterator i = merge.all_nodes().begin();
1550 i != merge.all_nodes().end(); ++i)
1551 {
1552 node_t const & n = i->second;
1553 // SPEEDUP?: instead of using find repeatedly, iterate everything in
1554 // parallel
1555 map<node_id, node_t>::const_iterator lni = left_roster.all_nodes().find(i->first);
1556 map<node_id, node_t>::const_iterator rni = right_roster.all_nodes().find(i->first);
1557
1558 bool exists_in_left = (lni != left_roster.all_nodes().end());
1559 bool exists_in_right = (rni != right_roster.all_nodes().end());
1560
1561 marking_t new_marking;
1562
1563 if (!exists_in_left && !exists_in_right)
1564 mark_new_node(new_rid, n, new_marking);
1565
1566 else if (!exists_in_left && exists_in_right)
1567 {
1568 node_t const & right_node = rni->second;
1569 marking_t const & right_marking = safe_get(right_markings, n->self);
1570 // must be unborn on the left (as opposed to dead)
1571 I(right_uncommon_ancestors.find(right_marking.birth_revision)
1572 != right_uncommon_ancestors.end());
1573 mark_unmerged_node(right_marking, right_node,
1574 new_rid, n, new_marking);
1575 }
1576 else if (exists_in_left && !exists_in_right)
1577 {
1578 node_t const & left_node = lni->second;
1579 marking_t const & left_marking = safe_get(left_markings, n->self);
1580 // must be unborn on the right (as opposed to dead)
1581 I(left_uncommon_ancestors.find(left_marking.birth_revision)
1582 != left_uncommon_ancestors.end());
1583 mark_unmerged_node(left_marking, left_node,
1584 new_rid, n, new_marking);
1585 }
1586 else
1587 {
1588 node_t const & left_node = lni->second;
1589 node_t const & right_node = rni->second;
1590 mark_merged_node(safe_get(left_markings, n->self),
1591 left_uncommon_ancestors, left_node,
1592 safe_get(right_markings, n->self),
1593 right_uncommon_ancestors, right_node,
1594 new_rid, n, new_marking);
1595 }
1596
1597 safe_insert(new_markings, make_pair(i->first, new_marking));
1598 }
1599}
1600
1601namespace {
1602
1603 class editable_roster_for_nonmerge
1604 : public editable_roster_base
1605 {
1606 public:
1607 editable_roster_for_nonmerge(roster_t & r, node_id_source & nis,
1608 revision_id const & rid,
1609 marking_map & markings)
1610 : editable_roster_base(r, nis),
1611 rid(rid), markings(markings)
1612 {}
1613
1614 virtual node_id detach_node(split_path const & src)
1615 {
1616 node_id nid = this->editable_roster_base::detach_node(src);
1617 marking_map::iterator marking = markings.find(nid);
1618 I(marking != markings.end());
1619 marking->second.parent_name.clear();
1620 marking->second.parent_name.insert(rid);
1621 return nid;
1622 }
1623
1624 virtual void drop_detached_node(node_id nid)
1625 {
1626 this->editable_roster_base::drop_detached_node(nid);
1627 safe_erase(markings, nid);
1628 }
1629
1630 virtual node_id create_dir_node()
1631 {
1632 return handle_new(this->editable_roster_base::create_dir_node());
1633 }
1634
1635 virtual node_id create_file_node(file_id const & content)
1636 {
1637 return handle_new(this->editable_roster_base::create_file_node(content));
1638 }
1639
1640 virtual void apply_delta(split_path const & pth,
1641 file_id const & old_id, file_id const & new_id)
1642 {
1643 this->editable_roster_base::apply_delta(pth, old_id, new_id);
1644 node_id nid = r.get_node(pth)->self;
1645 marking_map::iterator marking = markings.find(nid);
1646 I(marking != markings.end());
1647 marking->second.file_content.clear();
1648 marking->second.file_content.insert(rid);
1649 }
1650
1651 virtual void clear_attr(split_path const & pth, attr_key const & name)
1652 {
1653 this->editable_roster_base::clear_attr(pth, name);
1654 handle_attr(pth, name);
1655 }
1656
1657 virtual void set_attr(split_path const & pth, attr_key const & name,
1658 attr_value const & val)
1659 {
1660 this->editable_roster_base::set_attr(pth, name, val);
1661 handle_attr(pth, name);
1662 }
1663
1664 node_id handle_new(node_id nid)
1665 {
1666 node_t n = r.get_node(nid);
1667 marking_t new_marking;
1668 mark_new_node(rid, n, new_marking);
1669 safe_insert(markings, make_pair(nid, new_marking));
1670 return nid;
1671 }
1672
1673 void handle_attr(split_path const & pth, attr_key const & name)
1674 {
1675 node_id nid = r.get_node(pth)->self;
1676 marking_map::iterator marking = markings.find(nid);
1677 map<attr_key, set<revision_id> >::iterator am = marking->second.attrs.find(name);
1678 if (am == marking->second.attrs.end())
1679 {
1680 marking->second.attrs.insert(make_pair(name, set<revision_id>()));
1681 am = marking->second.attrs.find(name);
1682 }
1683
1684 I(am != marking->second.attrs.end());
1685 am->second.clear();
1686 am->second.insert(rid);
1687 }
1688
1689 private:
1690 revision_id const & rid;
1691 // markings starts out as the parent's markings
1692 marking_map & markings;
1693 };
1694
1695 // Interface note: make_roster_for_merge and make_roster_for_nonmerge
1696 // each exist in two variants:
1697 //
1698 // 1. A variant that does all of the actual work, taking every single
1699 // relevant base-level data object as a separate argument. This
1700 // variant is called directly by the unit tests, and also by variant 2.
1701 //
1702 // 2. A variant that takes a revision object, a revision ID, a database,
1703 // and a node_id_source. This variant uses those four things to look
1704 // up all of the low-level data required by variant 1, then calls
1705 // variant 1 to get the real work done. This is the one called by
1706 // (one variant of) make_roster_for_revision.
1707
1708 // yes, this function takes 14 arguments. I'm very sorry.
1709 void
1710 make_roster_for_merge(revision_id const & left_rid,
1711 roster_t const & left_roster,
1712 marking_map const & left_markings,
1713 cset const & left_cs,
1714 set<revision_id> const & left_uncommon_ancestors,
1715
1716 revision_id const & right_rid,
1717 roster_t const & right_roster,
1718 marking_map const & right_markings,
1719 cset const & right_cs,
1720 set<revision_id> const & right_uncommon_ancestors,
1721
1722 revision_id const & new_rid,
1723 roster_t & new_roster,
1724 marking_map & new_markings,
1725 node_id_source & nis)
1726 {
1727 I(!null_id(left_rid) && !null_id(right_rid));
1728 I(left_uncommon_ancestors.find(left_rid) != left_uncommon_ancestors.end());
1729 I(left_uncommon_ancestors.find(right_rid) == left_uncommon_ancestors.end());
1730 I(right_uncommon_ancestors.find(right_rid) != right_uncommon_ancestors.end());
1731 I(right_uncommon_ancestors.find(left_rid) == right_uncommon_ancestors.end());
1732 MM(left_rid);
1733 MM(left_roster);
1734 MM(left_markings);
1735 MM(left_cs);
1736 MM(left_uncommon_ancestors);
1737 MM(right_rid);
1738 MM(right_roster);
1739 MM(right_markings);
1740 MM(right_cs);
1741 MM(right_uncommon_ancestors);
1742 MM(new_rid);
1743 MM(new_roster);
1744 MM(new_markings);
1745 {
1746 temp_node_id_source temp_nis;
1747 new_roster = left_roster;
1748 roster_t from_right_r(right_roster);
1749 MM(from_right_r);
1750
1751 editable_roster_for_merge from_left_er(new_roster, temp_nis);
1752 editable_roster_for_merge from_right_er(from_right_r, temp_nis);
1753
1754 left_cs.apply_to(from_left_er);
1755 right_cs.apply_to(from_right_er);
1756
1757 set<node_id> new_ids;
1758 unify_rosters(new_roster, from_left_er.new_nodes,
1759 from_right_r, from_right_er.new_nodes,
1760 nis);
1761
1762 // Kluge: If both csets have no content changes, and the node_id_source
1763 // passed to this function is a temp_node_id_source, then we are being
1764 // called from get_current_roster_shape, and we should not attempt to
1765 // verify that these rosters match as far as content IDs.
1766 if (left_cs.deltas_applied.size() == 0
1767 && right_cs.deltas_applied.size() == 0
1768 && typeid(nis) == typeid(temp_node_id_source))
1769 I(equal_shapes(new_roster, from_right_r));
1770 else
1771 I(new_roster == from_right_r);
1772 }
1773
1774 // SPEEDUP?: instead of constructing new marking from scratch, track which
1775 // nodes were modified, and scan only them
1776 // load one of the parent markings directly into the new marking map
1777 new_markings.clear();
1778 mark_merge_roster(left_roster, left_markings, left_uncommon_ancestors,
1779 right_roster, right_markings, right_uncommon_ancestors,
1780 new_rid, new_roster, new_markings);
1781 }
1782
1783
1784 // WARNING: this function is not tested directly (no unit tests). Do not
1785 // put real logic in it.
1786 void
1787 make_roster_for_merge(revision_t const & rev, revision_id const & new_rid,
1788 roster_t & new_roster, marking_map & new_markings,
1789 database & db, node_id_source & nis)
1790 {
1791 edge_map::const_iterator i = rev.edges.begin();
1792 revision_id const & left_rid = edge_old_revision(i);
1793 cset const & left_cs = edge_changes(i);
1794 ++i;
1795 revision_id const & right_rid = edge_old_revision(i);
1796 cset const & right_cs = edge_changes(i);
1797
1798 I(!null_id(left_rid) && !null_id(right_rid));
1799 database::cached_roster left_cached, right_cached;
1800 db.get_roster(left_rid, left_cached);
1801 db.get_roster(right_rid, right_cached);
1802
1803 set<revision_id> left_uncommon_ancestors, right_uncommon_ancestors;
1804 db.get_uncommon_ancestors(left_rid, right_rid,
1805 left_uncommon_ancestors,
1806 right_uncommon_ancestors);
1807
1808 make_roster_for_merge(left_rid, *left_cached.first, *left_cached.second,
1809 left_cs, left_uncommon_ancestors,
1810 right_rid, *right_cached.first, *right_cached.second,
1811 right_cs, right_uncommon_ancestors,
1812 new_rid,
1813 new_roster, new_markings,
1814 nis);
1815 }
1816
1817 // Warning: this function expects the parent's roster and markings in the
1818 // 'new_roster' and 'new_markings' parameters, and they are modified
1819 // destructively!
1820 // This function performs an almost identical task to
1821 // mark_roster_with_one_parent; however, for efficiency, it is implemented
1822 // in a different, destructive way.
1823 void
1824 make_roster_for_nonmerge(cset const & cs,
1825 revision_id const & new_rid,
1826 roster_t & new_roster, marking_map & new_markings,
1827 node_id_source & nis)
1828 {
1829 editable_roster_for_nonmerge er(new_roster, nis, new_rid, new_markings);
1830 cs.apply_to(er);
1831 }
1832
1833 // WARNING: this function is not tested directly (no unit tests). Do not
1834 // put real logic in it.
1835 void
1836 make_roster_for_nonmerge(revision_t const & rev,
1837 revision_id const & new_rid,
1838 roster_t & new_roster, marking_map & new_markings,
1839 database & db, node_id_source & nis)
1840 {
1841 revision_id const & parent_rid = edge_old_revision(rev.edges.begin());
1842 cset const & parent_cs = edge_changes(rev.edges.begin());
1843 db.get_roster(parent_rid, new_roster, new_markings);
1844 make_roster_for_nonmerge(parent_cs, new_rid, new_roster, new_markings, nis);
1845 }
1846}
1847
1848void
1849mark_roster_with_no_parents(revision_id const & rid,
1850 roster_t const & roster,
1851 marking_map & markings)
1852{
1853 roster_t mock_parent;
1854 marking_map mock_parent_markings;
1855 mark_roster_with_one_parent(mock_parent, mock_parent_markings,
1856 rid, roster, markings);
1857}
1858
1859void
1860mark_roster_with_one_parent(roster_t const & parent,
1861 marking_map const & parent_markings,
1862 revision_id const & child_rid,
1863 roster_t const & child,
1864 marking_map & child_markings)
1865{
1866 MM(parent);
1867 MM(parent_markings);
1868 MM(child_rid);
1869 MM(child);
1870 MM(child_markings);
1871
1872 I(!null_id(child_rid));
1873 child_markings.clear();
1874
1875 for (node_map::const_iterator i = child.all_nodes().begin();
1876 i != child.all_nodes().end(); ++i)
1877 {
1878 marking_t new_marking;
1879 if (parent.has_node(i->first))
1880 mark_unmerged_node(safe_get(parent_markings, i->first),
1881 parent.get_node(i->first),
1882 child_rid, i->second, new_marking);
1883 else
1884 mark_new_node(child_rid, i->second, new_marking);
1885 safe_insert(child_markings, make_pair(i->first, new_marking));
1886 }
1887
1888 child.check_sane_against(child_markings, true);
1889}
1890
1891// WARNING: this function is not tested directly (no unit tests). Do not put
1892// real logic in it.
1893void
1894make_roster_for_revision(revision_t const & rev, revision_id const & new_rid,
1895 roster_t & new_roster, marking_map & new_markings,
1896 database & db, node_id_source & nis)
1897{
1898 MM(rev);
1899 MM(new_rid);
1900 MM(new_roster);
1901 MM(new_markings);
1902 if (rev.edges.size() == 1)
1903 make_roster_for_nonmerge(rev, new_rid, new_roster, new_markings, db, nis);
1904 else if (rev.edges.size() == 2)
1905 make_roster_for_merge(rev, new_rid, new_roster, new_markings, db, nis);
1906 else
1907 I(false);
1908
1909 // If nis is not a true_node_id_source, we have to assume we can get temp
1910 // node ids out of it. ??? Provide a predicate method on node_id_sources
1911 // instead of doing a typeinfo comparison.
1912 new_roster.check_sane_against(new_markings,
1913 typeid(nis) != typeid(true_node_id_source));
1914}
1915
1916void
1917make_roster_for_revision(revision_t const & rev, revision_id const & new_rid,
1918 roster_t & new_roster, marking_map & new_markings,
1919 app_state & app)
1920{
1921 true_node_id_source nis(app);
1922 make_roster_for_revision(rev, new_rid, new_roster, new_markings, app.db, nis);
1923}
1924
1925
1926////////////////////////////////////////////////////////////////////
1927// Calculation of a cset
1928////////////////////////////////////////////////////////////////////
1929
1930
1931namespace
1932{
1933
1934 void delta_only_in_from(roster_t const & from,
1935 node_id nid, node_t n,
1936 cset & cs)
1937 {
1938 split_path sp;
1939 from.get_name(nid, sp);
1940 safe_insert(cs.nodes_deleted, sp);
1941 }
1942
1943
1944 void delta_only_in_to(roster_t const & to, node_id nid, node_t n,
1945 cset & cs)
1946 {
1947 split_path sp;
1948 to.get_name(nid, sp);
1949 if (is_file_t(n))
1950 {
1951 safe_insert(cs.files_added,
1952 make_pair(sp, downcast_to_file_t(n)->content));
1953 }
1954 else
1955 {
1956 safe_insert(cs.dirs_added, sp);
1957 }
1958 for (full_attr_map_t::const_iterator i = n->attrs.begin();
1959 i != n->attrs.end(); ++i)
1960 if (i->second.first)
1961 safe_insert(cs.attrs_set,
1962 make_pair(make_pair(sp, i->first), i->second.second));
1963 }
1964
1965 void delta_in_both(node_id nid,
1966 roster_t const & from, node_t from_n,
1967 roster_t const & to, node_t to_n,
1968 cset & cs)
1969 {
1970 I(same_type(from_n, to_n));
1971 I(from_n->self == to_n->self);
1972
1973 if (shallow_equal(from_n, to_n, false))
1974 return;
1975
1976 split_path from_sp, to_sp;
1977 from.get_name(nid, from_sp);
1978 to.get_name(nid, to_sp);
1979
1980 // Compare name and path.
1981 if (from_n->name != to_n->name || from_n->parent != to_n->parent)
1982 safe_insert(cs.nodes_renamed, make_pair(from_sp, to_sp));
1983
1984 // Compare file content.
1985 if (is_file_t(from_n))
1986 {
1987 file_t from_f = downcast_to_file_t(from_n);
1988 file_t to_f = downcast_to_file_t(to_n);
1989 if (!(from_f->content == to_f->content))
1990 {
1991 safe_insert(cs.deltas_applied,
1992 make_pair(to_sp, make_pair(from_f->content,
1993 to_f->content)));
1994 }
1995 }
1996
1997 // Compare attrs.
1998 {
1999 parallel::iter<full_attr_map_t> i(from_n->attrs, to_n->attrs);
2000 while (i.next())
2001 {
2002 MM(i);
2003 if ((i.state() == parallel::in_left
2004 || (i.state() == parallel::in_both && !i.right_data().first))
2005 && i.left_data().first)
2006 {
2007 safe_insert(cs.attrs_cleared,
2008 make_pair(to_sp, i.left_key()));
2009 }
2010 else if ((i.state() == parallel::in_right
2011 || (i.state() == parallel::in_both && !i.left_data().first))
2012 && i.right_data().first)
2013 {
2014 safe_insert(cs.attrs_set,
2015 make_pair(make_pair(to_sp, i.right_key()),
2016 i.right_data().second));
2017 }
2018 else if (i.state() == parallel::in_both
2019 && i.right_data().first
2020 && i.left_data().first
2021 && i.right_data().second != i.left_data().second)
2022 {
2023 safe_insert(cs.attrs_set,
2024 make_pair(make_pair(to_sp, i.right_key()),
2025 i.right_data().second));
2026 }
2027 }
2028 }
2029 }
2030}
2031
2032void
2033make_cset(roster_t const & from, roster_t const & to, cset & cs)
2034{
2035 cs.clear();
2036 parallel::iter<node_map> i(from.all_nodes(), to.all_nodes());
2037 while (i.next())
2038 {
2039 MM(i);
2040 switch (i.state())
2041 {
2042 case parallel::invalid:
2043 I(false);
2044
2045 case parallel::in_left:
2046 // deleted
2047 delta_only_in_from(from, i.left_key(), i.left_data(), cs);
2048 break;
2049
2050 case parallel::in_right:
2051 // added
2052 delta_only_in_to(to, i.right_key(), i.right_data(), cs);
2053 break;
2054
2055 case parallel::in_both:
2056 // moved/renamed/patched/attribute changes
2057 delta_in_both(i.left_key(), from, i.left_data(), to, i.right_data(), cs);
2058 break;
2059 }
2060 }
2061}
2062
2063
2064// we assume our input is sane
2065bool
2066equal_up_to_renumbering(roster_t const & a, marking_map const & a_markings,
2067 roster_t const & b, marking_map const & b_markings)
2068{
2069 if (a.all_nodes().size() != b.all_nodes().size())
2070 return false;
2071
2072 for (node_map::const_iterator i = a.all_nodes().begin();
2073 i != a.all_nodes().end(); ++i)
2074 {
2075 split_path sp;
2076 a.get_name(i->first, sp);
2077 if (!b.has_node(sp))
2078 return false;
2079 node_t b_n = b.get_node(sp);
2080 // we already know names are the same
2081 if (!same_type(i->second, b_n))
2082 return false;
2083 if (i->second->attrs != b_n->attrs)
2084 return false;
2085 if (is_file_t(i->second))
2086 {
2087 if (!(downcast_to_file_t(i->second)->content
2088 == downcast_to_file_t(b_n)->content))
2089 return false;
2090 }
2091 // nodes match, check the markings too
2092 if (!(safe_get(a_markings, i->first) == safe_get(b_markings, b_n->self)))
2093 return false;
2094 }
2095 return true;
2096}
2097
2098
2099void make_restricted_csets(roster_t const & from, roster_t const & to,
2100 cset & included, cset & excluded,
2101 node_restriction const & mask)
2102{
2103 included.clear();
2104 excluded.clear();
2105
2106 L(FL("building restricted csets"));
2107 parallel::iter<node_map> i(from.all_nodes(), to.all_nodes());
2108 while (i.next())
2109 {
2110 MM(i);
2111 switch (i.state())
2112 {
2113 case parallel::invalid:
2114 I(false);
2115
2116 case parallel::in_left:
2117 // deleted
2118 if (mask.includes(from, i.left_key()))
2119 {
2120 delta_only_in_from(from, i.left_key(), i.left_data(), included);
2121 L(FL("included left %d") % i.left_key());
2122 }
2123 else
2124 {
2125 delta_only_in_from(from, i.left_key(), i.left_data(), excluded);
2126 L(FL("excluded left %d") % i.left_key());
2127 }
2128 break;
2129
2130 case parallel::in_right:
2131 // added
2132 if (mask.includes(to, i.right_key()))
2133 {
2134 delta_only_in_to(to, i.right_key(), i.right_data(), included);
2135 L(FL("included right %d") % i.right_key());
2136 }
2137 else
2138 {
2139 delta_only_in_to(to, i.right_key(), i.right_data(), excluded);
2140 L(FL("excluded right %d") % i.right_key());
2141 }
2142 break;
2143
2144 case parallel::in_both:
2145 // moved/renamed/patched/attribute changes
2146 if (mask.includes(from, i.left_key()) || mask.includes(to, i.right_key()))
2147 {
2148 delta_in_both(i.left_key(), from, i.left_data(), to, i.right_data(), included);
2149 L(FL("in both %d %d") % i.left_key() % i.right_key());
2150 }
2151 else
2152 {
2153 delta_in_both(i.left_key(), from, i.left_data(), to, i.right_data(), excluded);
2154 L(FL("in both %d %d") % i.left_key() % i.right_key());
2155 }
2156 break;
2157 }
2158 }
2159
2160}
2161
2162class editable_roster_for_check
2163 : public editable_roster_base
2164{
2165 public:
2166 editable_roster_for_check(roster_t & r);
2167 virtual node_id detach_node(split_path const & src);
2168 virtual void drop_detached_node(node_id nid);
2169 virtual void attach_node(node_id nid, split_path const & dst);
2170 int problems;
2171
2172 private:
2173 temp_node_id_source nis;
2174 map<node_id, pair<split_path, vector<path_component> > > detached_dirs;
2175};
2176
2177editable_roster_for_check::editable_roster_for_check(roster_t & r)
2178 : editable_roster_base(r, nis), problems(0)
2179{
2180 node_map nodes = r.all_nodes();
2181
2182 if (!nodes.empty())
2183 {
2184 node_map::const_iterator i = nodes.begin();
2185 node_id max = i->first;
2186
2187 for (; i != nodes.end(); ++i)
2188 {
2189 if (i->first > max)
2190 max = i->first;
2191 }
2192
2193 // ensure our node source starts beyond the max temp node in this roster
2194 while (nis.next() <= max)
2195 ;
2196 }
2197}
2198
2199node_id
2200editable_roster_for_check::detach_node(split_path const & src)
2201{
2202 node_t n = r.get_node(src);
2203 if (is_dir_t(n))
2204 {
2205 dir_t dir = downcast_to_dir_t(n);
2206 vector<path_component> children;
2207 for (dir_map::const_iterator
2208 i = dir->children.begin(); i != dir->children.end(); ++i)
2209 {
2210 children.push_back(i->first);
2211 }
2212 detached_dirs.insert(make_pair(dir->self,
2213 make_pair(src, children)));
2214 }
2215
2216 return this->editable_roster_base::detach_node(src);
2217}
2218
2219void
2220editable_roster_for_check::drop_detached_node(node_id nid)
2221{
2222 node_t n = r.get_node(nid);
2223 if (is_dir_t(n) && !downcast_to_dir_t(n)->children.empty())
2224 {
2225 map<node_id, pair<split_path, vector<path_component> > >::const_iterator
2226 i = detached_dirs.find(nid);
2227 I(i != detached_dirs.end());
2228
2229 split_path dir = i->second.first;
2230 for (vector<path_component>::const_iterator
2231 p = i->second.second.begin(); p != i->second.second.end(); ++p)
2232 {
2233 split_path child(dir);
2234 child.push_back(*p);
2235 W(F("restriction includes deletion of '%s' but excludes deletion of '%s'")
2236 % dir % child);
2237 problems++;
2238 }
2239 }
2240 else
2241 {
2242 this->editable_roster_base::drop_detached_node(nid);
2243 }
2244}
2245
2246void
2247editable_roster_for_check::attach_node(node_id nid, split_path const & dst)
2248{
2249 split_path dirname;
2250 path_component basename;
2251 dirname_basename(dst, dirname, basename);
2252
2253 if (!dirname.empty() && !r.has_node(dirname))
2254 {
2255 W(F("restriction excludes addition of '%s' but includes addition of '%s'")
2256 % dirname % dst);
2257 problems++;
2258 }
2259 else
2260 {
2261 this->editable_roster_base::attach_node(nid, dst);
2262 }
2263}
2264
2265void
2266check_restricted_cset(roster_t const & roster, cset const & cs)
2267{
2268 // This command checks that a cset generated by make_restricted_cset still
2269 // is sensical when applied to the given roster -- e.g., it does not
2270 // include a deletion of a directory that would be empty, except that some
2271 // of the deletions/renames that emptied it were not included in the
2272 // restriction, it does not include the addition of a file when the
2273 // addition of its parent directory was not included, etc.
2274
2275 MM(roster);
2276 MM(cs);
2277
2278 // make a copy of the roster to apply the cset to destructively
2279 roster_t tmp(roster);
2280 editable_roster_for_check e(tmp);
2281 cs.apply_to(e);
2282
2283 N(e.problems == 0, F("invalid restriction"));
2284}
2285
2286
2287void
2288select_nodes_modified_by_cset(cset const & cs,
2289 roster_t const & old_roster,
2290 roster_t const & new_roster,
2291 set<node_id> & nodes_modified)
2292{
2293 nodes_modified.clear();
2294
2295 path_set modified_prestate_nodes;
2296 path_set modified_poststate_nodes;
2297
2298 // Pre-state damage
2299
2300 copy(cs.nodes_deleted.begin(), cs.nodes_deleted.end(),
2301 inserter(modified_prestate_nodes, modified_prestate_nodes.begin()));
2302
2303 for (map<split_path, split_path>::const_iterator i = cs.nodes_renamed.begin();
2304 i != cs.nodes_renamed.end(); ++i)
2305 modified_prestate_nodes.insert(i->first);
2306
2307 // Post-state damage
2308
2309 copy(cs.dirs_added.begin(), cs.dirs_added.end(),
2310 inserter(modified_poststate_nodes, modified_poststate_nodes.begin()));
2311
2312 for (map<split_path, file_id>::const_iterator i = cs.files_added.begin();
2313 i != cs.files_added.end(); ++i)
2314 modified_poststate_nodes.insert(i->first);
2315
2316 for (map<split_path, split_path>::const_iterator i = cs.nodes_renamed.begin();
2317 i != cs.nodes_renamed.end(); ++i)
2318 modified_poststate_nodes.insert(i->second);
2319
2320 for (map<split_path, pair<file_id, file_id> >::const_iterator i = cs.deltas_applied.begin();
2321 i != cs.deltas_applied.end(); ++i)
2322 modified_poststate_nodes.insert(i->first);
2323
2324 for (set<pair<split_path, attr_key> >::const_iterator i = cs.attrs_cleared.begin();
2325 i != cs.attrs_cleared.end(); ++i)
2326 modified_poststate_nodes.insert(i->first);
2327
2328 for (map<pair<split_path, attr_key>, attr_value>::const_iterator i = cs.attrs_set.begin();
2329 i != cs.attrs_set.end(); ++i)
2330 modified_poststate_nodes.insert(i->first.first);
2331
2332 // Finale
2333
2334 for (path_set::const_iterator i = modified_prestate_nodes.begin();
2335 i != modified_prestate_nodes.end(); ++i)
2336 {
2337 I(old_roster.has_node(*i));
2338 nodes_modified.insert(old_roster.get_node(*i)->self);
2339 }
2340
2341 for (path_set::const_iterator i = modified_poststate_nodes.begin();
2342 i != modified_poststate_nodes.end(); ++i)
2343 {
2344 I(new_roster.has_node(*i));
2345 nodes_modified.insert(new_roster.get_node(*i)->self);
2346 }
2347
2348}
2349
2350void
2351roster_t::extract_path_set(path_set & paths) const
2352{
2353 paths.clear();
2354 if (has_root())
2355 {
2356 for (dfs_iter i(root_dir); !i.finished(); ++i)
2357 {
2358 node_t curr = *i;
2359 split_path pth;
2360 get_name(curr->self, pth);
2361 if (!workspace_root(pth))
2362 paths.insert(pth);
2363 }
2364 }
2365}
2366
2367
2368////////////////////////////////////////////////////////////////////
2369// I/O routines
2370////////////////////////////////////////////////////////////////////
2371
2372void
2373push_marking(basic_io::stanza & st,
2374 bool is_file,
2375 marking_t const & mark)
2376{
2377
2378 I(!null_id(mark.birth_revision));
2379 st.push_hex_pair(basic_io::syms::birth, mark.birth_revision.inner());
2380
2381 for (set<revision_id>::const_iterator i = mark.parent_name.begin();
2382 i != mark.parent_name.end(); ++i)
2383 st.push_hex_pair(basic_io::syms::path_mark, i->inner());
2384
2385 if (is_file)
2386 {
2387 for (set<revision_id>::const_iterator i = mark.file_content.begin();
2388 i != mark.file_content.end(); ++i)
2389 st.push_hex_pair(basic_io::syms::content_mark, i->inner());
2390 }
2391 else
2392 I(mark.file_content.empty());
2393
2394 for (map<attr_key, set<revision_id> >::const_iterator i = mark.attrs.begin();
2395 i != mark.attrs.end(); ++i)
2396 {
2397 for (set<revision_id>::const_iterator j = i->second.begin();
2398 j != i->second.end(); ++j)
2399 st.push_hex_triple(basic_io::syms::attr_mark, i->first(), j->inner());
2400 }
2401}
2402
2403
2404void
2405parse_marking(basic_io::parser & pa,
2406 marking_t & marking)
2407{
2408 while (pa.symp())
2409 {
2410 string rev;
2411 if (pa.symp(basic_io::syms::birth))
2412 {
2413 pa.sym();
2414 pa.hex(rev);
2415 marking.birth_revision = revision_id(rev);
2416 }
2417 else if (pa.symp(basic_io::syms::path_mark))
2418 {
2419 pa.sym();
2420 pa.hex(rev);
2421 safe_insert(marking.parent_name, revision_id(rev));
2422 }
2423 else if (pa.symp(basic_io::syms::content_mark))
2424 {
2425 pa.sym();
2426 pa.hex(rev);
2427 safe_insert(marking.file_content, revision_id(rev));
2428 }
2429 else if (pa.symp(basic_io::syms::attr_mark))
2430 {
2431 string k;
2432 pa.sym();
2433 pa.str(k);
2434 pa.hex(rev);
2435 attr_key key = attr_key(k);
2436 safe_insert(marking.attrs[key], revision_id(rev));
2437 }
2438 else break;
2439 }
2440}
2441
2442// SPEEDUP?: hand-writing a parser for manifests was a measurable speed win,
2443// and the original parser was much simpler than basic_io. After benchmarking
2444// consider replacing the roster disk format with something that can be
2445// processed more efficiently.
2446
2447void
2448roster_t::print_to(basic_io::printer & pr,
2449 marking_map const & mm,
2450 bool print_local_parts) const
2451{
2452 I(has_root());
2453 {
2454 basic_io::stanza st;
2455 st.push_str_pair(basic_io::syms::format_version, "1");
2456 pr.print_stanza(st);
2457 }
2458 for (dfs_iter i(root_dir); !i.finished(); ++i)
2459 {
2460 node_t curr = *i;
2461 split_path pth;
2462 get_name(curr->self, pth);
2463
2464 file_path fp = file_path(pth);
2465
2466 basic_io::stanza st;
2467 if (is_dir_t(curr))
2468 {
2469 // L(FL("printing dir %s") % fp);
2470 st.push_file_pair(basic_io::syms::dir, fp);
2471 }
2472 else
2473 {
2474 file_t ftmp = downcast_to_file_t(curr);
2475 st.push_file_pair(basic_io::syms::file, fp);
2476 st.push_hex_pair(basic_io::syms::content, ftmp->content.inner());
2477 // L(FL("printing file %s") % fp);
2478 }
2479
2480 if (print_local_parts)
2481 {
2482 I(curr->self != the_null_node);
2483 st.push_str_pair(basic_io::syms::ident, lexical_cast<string>(curr->self));
2484 }
2485
2486 // Push the non-dormant part of the attr map
2487 for (full_attr_map_t::const_iterator j = curr->attrs.begin();
2488 j != curr->attrs.end(); ++j)
2489 {
2490 if (j->second.first)
2491 {
2492 // L(FL("printing attr %s : %s = %s") % fp % j->first % j->second);
2493 st.push_str_triple(basic_io::syms::attr, j->first(), j->second.second());
2494 }
2495 }
2496
2497 if (print_local_parts)
2498 {
2499 // Push the dormant part of the attr map
2500 for (full_attr_map_t::const_iterator j = curr->attrs.begin();
2501 j != curr->attrs.end(); ++j)
2502 {
2503 if (!j->second.first)
2504 {
2505 I(j->second.second().empty());
2506 st.push_str_pair(basic_io::syms::dormant_attr, j->first());
2507 }
2508 }
2509
2510 marking_map::const_iterator m = mm.find(curr->self);
2511 I(m != mm.end());
2512 push_marking(st, is_file_t(curr), m->second);
2513 }
2514
2515 pr.print_stanza(st);
2516 }
2517}
2518
2519inline size_t
2520read_num(string const & s)
2521{
2522 size_t n = 0;
2523
2524 for (string::const_iterator i = s.begin(); i != s.end(); i++)
2525 {
2526 I(*i >= '0' && *i <= '9');
2527 n *= 10;
2528 n += static_cast<size_t>(*i - '0');
2529 }
2530 return n;
2531}
2532
2533void
2534roster_t::parse_from(basic_io::parser & pa,
2535 marking_map & mm)
2536{
2537 // Instantiate some lookaside caches to ensure this roster reuses
2538 // string storage across ATOMIC elements.
2539 id::symtab id_syms;
2540 path_component::symtab path_syms;
2541 attr_key::symtab attr_key_syms;
2542 attr_value::symtab attr_value_syms;
2543
2544
2545 // We *always* parse the local part of a roster, because we do not
2546 // actually send the non-local part over the network; the only times
2547 // we serialize a manifest (non-local roster) is when we're printing
2548 // it out for a user, or when we're hashing it for a manifest ID.
2549 nodes.clear();
2550 root_dir.reset();
2551 mm.clear();
2552
2553 {
2554 pa.esym(basic_io::syms::format_version);
2555 string vers;
2556 pa.str(vers);
2557 I(vers == "1");
2558 }
2559
2560 while(pa.symp())
2561 {
2562 string pth, ident, rev;
2563 node_t n;
2564
2565 if (pa.symp(basic_io::syms::file))
2566 {
2567 string content;
2568 pa.sym();
2569 pa.str(pth);
2570 pa.esym(basic_io::syms::content);
2571 pa.hex(content);
2572 pa.esym(basic_io::syms::ident);
2573 pa.str(ident);
2574 n = file_t(new file_node(read_num(ident),
2575 file_id(content)));
2576 }
2577 else if (pa.symp(basic_io::syms::dir))
2578 {
2579 pa.sym();
2580 pa.str(pth);
2581 pa.esym(basic_io::syms::ident);
2582 pa.str(ident);
2583 n = dir_t(new dir_node(read_num(ident)));
2584 }
2585 else
2586 break;
2587
2588 I(static_cast<bool>(n));
2589
2590 safe_insert(nodes, make_pair(n->self, n));
2591 if (is_dir_t(n) && pth.empty())
2592 {
2593 I(! has_root());
2594 root_dir = downcast_to_dir_t(n);
2595 }
2596 else
2597 {
2598 I(!pth.empty());
2599 split_path sp;
2600 internal_string_to_split_path(pth, sp);
2601 attach_node(n->self, sp);
2602 }
2603
2604 // Non-dormant attrs
2605 while(pa.symp(basic_io::syms::attr))
2606 {
2607 pa.sym();
2608 string k, v;
2609 pa.str(k);
2610 pa.str(v);
2611 safe_insert(n->attrs, make_pair(attr_key(k),
2612 make_pair(true, attr_value(v))));
2613 }
2614
2615 // Dormant attrs
2616 while(pa.symp(basic_io::syms::dormant_attr))
2617 {
2618 pa.sym();
2619 string k;
2620 pa.str(k);
2621 safe_insert(n->attrs, make_pair(attr_key(k),
2622 make_pair(false, attr_value())));
2623 }
2624
2625 {
2626 marking_t & m(safe_insert(mm, make_pair(n->self, marking_t()))->second);
2627 parse_marking(pa, m);
2628 }
2629 }
2630}
2631
2632
2633void
2634read_roster_and_marking(roster_data const & dat,
2635 roster_t & ros,
2636 marking_map & mm)
2637{
2638 basic_io::input_source src(dat.inner()(), "roster");
2639 basic_io::tokenizer tok(src);
2640 basic_io::parser pars(tok);
2641 ros.parse_from(pars, mm);
2642 I(src.lookahead == EOF);
2643 ros.check_sane_against(mm);
2644}
2645
2646
2647static void
2648write_roster_and_marking(roster_t const & ros,
2649 marking_map const & mm,
2650 data & dat,
2651 bool print_local_parts)
2652{
2653 if (print_local_parts)
2654 ros.check_sane_against(mm);
2655 else
2656 ros.check_sane(true);
2657 basic_io::printer pr;
2658 ros.print_to(pr, mm, print_local_parts);
2659 dat = data(pr.buf);
2660}
2661
2662
2663void
2664write_roster_and_marking(roster_t const & ros,
2665 marking_map const & mm,
2666 roster_data & dat)
2667{
2668 data tmp;
2669 write_roster_and_marking(ros, mm, tmp, true);
2670 dat = roster_data(tmp);
2671}
2672
2673
2674void
2675write_manifest_of_roster(roster_t const & ros,
2676 manifest_data & dat)
2677{
2678 data tmp;
2679 marking_map mm;
2680 write_roster_and_marking(ros, mm, tmp, false);
2681 dat = manifest_data(tmp);
2682}
2683
2684void calculate_ident(roster_t const & ros,
2685 manifest_id & ident)
2686{
2687 manifest_data tmp;
2688 if (!ros.all_nodes().empty())
2689 {
2690 write_manifest_of_roster(ros, tmp);
2691 calculate_ident(tmp, ident);
2692 }
2693}
2694
2695////////////////////////////////////////////////////////////////////
2696// testing
2697////////////////////////////////////////////////////////////////////
2698
2699#ifdef BUILD_UNIT_TESTS
2700#include "unit_tests.hh"
2701#include "sanity.hh"
2702#include "constants.hh"
2703#include "randomizer.hh"
2704
2705#include "roster_delta.hh"
2706
2707#include <string>
2708#include <cstdlib>
2709#include <boost/lexical_cast.hpp>
2710
2711using std::logic_error;
2712using std::search;
2713
2714using boost::shared_ptr;
2715
2716static void
2717make_fake_marking_for(roster_t const & r, marking_map & mm)
2718{
2719 mm.clear();
2720 revision_id rid(string("0123456789abcdef0123456789abcdef01234567"));
2721 for (node_map::const_iterator i = r.all_nodes().begin(); i != r.all_nodes().end();
2722 ++i)
2723 {
2724 marking_t fake_marks;
2725 mark_new_node(rid, i->second, fake_marks);
2726 mm.insert(make_pair(i->first, fake_marks));
2727 }
2728}
2729
2730static void
2731do_testing_on_one_roster(roster_t const & r)
2732{
2733 if (!r.has_root())
2734 {
2735 I(r.all_nodes().size() == 0);
2736 // not much testing to be done on an empty roster -- can't iterate over
2737 // it or read/write it.
2738 return;
2739 }
2740
2741 MM(r);
2742 // test dfs_iter by making sure it returns the same number of items as there
2743 // are items in all_nodes()
2744 int n; MM(n);
2745 n = r.all_nodes().size();
2746 int dfs_counted = 0; MM(dfs_counted);
2747 split_path root_name;
2748 file_path().split(root_name);
2749 for (dfs_iter i(downcast_to_dir_t(r.get_node(root_name))); !i.finished(); ++i)
2750 ++dfs_counted;
2751 I(n == dfs_counted);
2752
2753 // do a read/write spin
2754 roster_data r_dat; MM(r_dat);
2755 marking_map fm;
2756 make_fake_marking_for(r, fm);
2757 write_roster_and_marking(r, fm, r_dat);
2758 roster_t r2; MM(r2);
2759 marking_map fm2;
2760 read_roster_and_marking(r_dat, r2, fm2);
2761 I(r == r2);
2762 I(fm == fm2);
2763 roster_data r2_dat; MM(r2_dat);
2764 write_roster_and_marking(r2, fm2, r2_dat);
2765 I(r_dat == r2_dat);
2766}
2767
2768static void
2769do_testing_on_two_equivalent_csets(cset const & a, cset const & b)
2770{
2771 // we do all this reading/writing/comparing of both strings and objects to
2772 // cross-check the reading, writing, and comparison logic against each
2773 // other. (if, say, there is a field in cset that == forgets to check but
2774 // that write remembers to include, this should catch it).
2775 MM(a);
2776 MM(b);
2777 I(a == b);
2778
2779 data a_dat, b_dat, a2_dat, b2_dat;
2780 MM(a_dat);
2781 MM(b_dat);
2782 MM(a2_dat);
2783 MM(b2_dat);
2784
2785 write_cset(a, a_dat);
2786 write_cset(b, b_dat);
2787 I(a_dat == b_dat);
2788 cset a2, b2;
2789 MM(a2);
2790 MM(b2);
2791 read_cset(a_dat, a2);
2792 read_cset(b_dat, b2);
2793 I(a2 == a);
2794 I(b2 == b);
2795 I(b2 == a);
2796 I(a2 == b);
2797 I(a2 == b2);
2798 write_cset(a2, a2_dat);
2799 write_cset(b2, b2_dat);
2800 I(a_dat == a2_dat);
2801 I(b_dat == b2_dat);
2802}
2803
2804static void
2805apply_cset_and_do_testing(roster_t & r, cset const & cs, node_id_source & nis)
2806{
2807 MM(r);
2808 MM(cs);
2809 roster_t original = r;
2810 MM(original);
2811 I(original == r);
2812
2813 editable_roster_base e(r, nis);
2814 cs.apply_to(e);
2815
2816 cset derived;
2817 MM(derived);
2818 make_cset(original, r, derived);
2819
2820 do_testing_on_two_equivalent_csets(cs, derived);
2821 do_testing_on_one_roster(r);
2822}
2823
2824static void
2825tests_on_two_rosters(roster_t const & a, roster_t const & b, node_id_source & nis)
2826{
2827 MM(a);
2828 MM(b);
2829
2830 do_testing_on_one_roster(a);
2831 do_testing_on_one_roster(b);
2832
2833 cset a_to_b; MM(a_to_b);
2834 cset b_to_a; MM(b_to_a);
2835 make_cset(a, b, a_to_b);
2836 make_cset(b, a, b_to_a);
2837 roster_t a2(b); MM(a2);
2838 roster_t b2(a); MM(b2);
2839 // we can't use a cset to entirely empty out a roster, so don't bother doing
2840 // the apply_to tests towards an empty roster
2841 // (NOTE: if you notice this special case in a time when root dirs can be
2842 // renamed or deleted, remove it, it will no longer be necessary.
2843 if (!a.all_nodes().empty())
2844 {
2845 editable_roster_base eb(a2, nis);
2846 b_to_a.apply_to(eb);
2847 }
2848 else
2849 a2 = a;
2850 if (!b.all_nodes().empty())
2851 {
2852 editable_roster_base ea(b2, nis);
2853 a_to_b.apply_to(ea);
2854 }
2855 else
2856 b2 = b;
2857 // We'd like to assert that a2 == a and b2 == b, but we can't, because they
2858 // will have new ids assigned.
2859 // But they _will_ have the same manifests, assuming things are working
2860 // correctly.
2861 manifest_data a_dat; MM(a_dat);
2862 manifest_data a2_dat; MM(a2_dat);
2863 manifest_data b_dat; MM(b_dat);
2864 manifest_data b2_dat; MM(b2_dat);
2865 if (a.has_root())
2866 write_manifest_of_roster(a, a_dat);
2867 if (a2.has_root())
2868 write_manifest_of_roster(a2, a2_dat);
2869 if (b.has_root())
2870 write_manifest_of_roster(b, b_dat);
2871 if (b2.has_root())
2872 write_manifest_of_roster(b2, b2_dat);
2873 I(a_dat == a2_dat);
2874 I(b_dat == b2_dat);
2875
2876 cset a2_to_b2; MM(a2_to_b2);
2877 cset b2_to_a2; MM(b2_to_a2);
2878 make_cset(a2, b2, a2_to_b2);
2879 make_cset(b2, a2, b2_to_a2);
2880 do_testing_on_two_equivalent_csets(a_to_b, a2_to_b2);
2881 do_testing_on_two_equivalent_csets(b_to_a, b2_to_a2);
2882
2883 {
2884 marking_map a_marking;
2885 make_fake_marking_for(a, a_marking);
2886 marking_map b_marking;
2887 make_fake_marking_for(b, b_marking);
2888 test_roster_delta_on(a, a_marking, b, b_marking);
2889 }
2890}
2891
2892template<typename M>
2893typename M::const_iterator
2894random_element(M const & m, randomizer & rng)
2895{
2896 size_t i = rng.uniform(m.size());
2897 typename M::const_iterator j = m.begin();
2898 while (i > 0)
2899 {
2900 I(j != m.end());
2901 --i;
2902 ++j;
2903 }
2904 return j;
2905}
2906
2907string new_word(randomizer & rng)
2908{
2909 static string wordchars = "abcdefghijlkmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
2910 static unsigned tick = 0;
2911 string tmp;
2912 do
2913 {
2914 tmp += wordchars[rng.uniform(wordchars.size())];
2915 }
2916 while (tmp.size() < 10 && !rng.flip(10));
2917 return tmp + lexical_cast<string>(tick++);
2918}
2919
2920file_id new_ident(randomizer & rng)
2921{
2922 static string tab = "0123456789abcdef";
2923 string tmp;
2924 tmp.reserve(constants::idlen);
2925 for (unsigned i = 0; i < constants::idlen; ++i)
2926 tmp += tab[rng.uniform(tab.size())];
2927 return file_id(tmp);
2928}
2929
2930path_component new_component(randomizer & rng)
2931{
2932 split_path pieces;
2933 file_path_internal(new_word(rng)).split(pieces);
2934 return pieces.back();
2935}
2936
2937
2938attr_key pick_attr(full_attr_map_t const & attrs, randomizer & rng)
2939{
2940 return random_element(attrs, rng)->first;
2941}
2942
2943attr_key pick_attr(attr_map_t const & attrs, randomizer & rng)
2944{
2945 return random_element(attrs, rng)->first;
2946}
2947
2948bool parent_of(split_path const & p,
2949 split_path const & c)
2950{
2951 bool is_parent = false;
2952
2953 if (p.size() <= c.size())
2954 {
2955 split_path::const_iterator c_anchor =
2956 search(c.begin(), c.end(),
2957 p.begin(), p.end());
2958
2959 is_parent = (c_anchor == c.begin());
2960 }
2961
2962 // L(FL("path '%s' is%s parent of '%s'")
2963 // % file_path(p)
2964 // % (is_parent ? "" : " not")
2965 // % file_path(c));
2966
2967 return is_parent;
2968}
2969
2970void perform_random_action(roster_t & r, node_id_source & nis, randomizer & rng)
2971{
2972 cset c;
2973 I(r.has_root());
2974 while (c.empty())
2975 {
2976 node_t n = random_element(r.all_nodes(), rng)->second;
2977 split_path pth;
2978 r.get_name(n->self, pth);
2979 // L(FL("considering acting on '%s'") % file_path(pth));
2980
2981 switch (rng.uniform(7))
2982 {
2983 default:
2984 case 0:
2985 case 1:
2986 case 2:
2987 if (is_file_t(n) || (pth.size() > 1 && rng.flip()))
2988 // Add a sibling of an existing entry.
2989 pth[pth.size() - 1] = new_component(rng);
2990
2991 else
2992 // Add a child of an existing entry.
2993 pth.push_back(new_component(rng));
2994
2995 if (rng.flip())
2996 {
2997 // L(FL("adding dir '%s'") % file_path(pth));
2998 safe_insert(c.dirs_added, pth);
2999 }
3000 else
3001 {
3002 // L(FL("adding file '%s'") % file_path(pth));
3003 safe_insert(c.files_added, make_pair(pth, new_ident(rng)));
3004 }
3005 break;
3006
3007 case 3:
3008 if (is_file_t(n))
3009 {
3010 // L(FL("altering content of file '%s'") % file_path(pth));
3011 safe_insert(c.deltas_applied,
3012 make_pair
3013 (pth, make_pair(downcast_to_file_t(n)->content,
3014 new_ident(rng))));
3015 }
3016 break;
3017
3018 case 4:
3019 {
3020 node_t n2 = random_element(r.all_nodes(), rng)->second;
3021 split_path pth2;
3022 r.get_name(n2->self, pth2);
3023
3024 if (n == n2)
3025 continue;
3026
3027 if (is_file_t(n2) || (pth2.size() > 1 && rng.flip()))
3028 {
3029 // L(FL("renaming to a sibling of an existing entry '%s'")
3030 // % file_path(pth2));
3031 // Move to a sibling of an existing entry.
3032 pth2[pth2.size() - 1] = new_component(rng);
3033 }
3034
3035 else
3036 {
3037 // L(FL("renaming to a child of an existing entry '%s'")
3038 // % file_path(pth2));
3039 // Move to a child of an existing entry.
3040 pth2.push_back(new_component(rng));
3041 }
3042
3043 if (!parent_of(pth, pth2))
3044 {
3045 // L(FL("renaming '%s' -> '%s")
3046 // % file_path(pth) % file_path(pth2));
3047 safe_insert(c.nodes_renamed, make_pair(pth, pth2));
3048 }
3049 }
3050 break;
3051
3052 case 5:
3053 if (!null_node(n->parent)
3054 && (is_file_t(n) || downcast_to_dir_t(n)->children.empty())
3055 && r.all_nodes().size() > 1) // do not delete the root
3056 {
3057 // L(FL("deleting '%s'") % file_path(pth));
3058 safe_insert(c.nodes_deleted, pth);
3059 }
3060 break;
3061
3062 case 6:
3063 if (!n->attrs.empty() && rng.flip())
3064 {
3065 attr_key k = pick_attr(n->attrs, rng);
3066 if (safe_get(n->attrs, k).first)
3067 {
3068 if (rng.flip())
3069 {
3070 // L(FL("clearing attr on '%s'") % file_path(pth));
3071 safe_insert(c.attrs_cleared, make_pair(pth, k));
3072 }
3073 else
3074 {
3075 // L(FL("changing attr on '%s'\n") % file_path(pth));
3076 safe_insert(c.attrs_set,
3077 make_pair(make_pair(pth, k), new_word(rng)));
3078 }
3079 }
3080 else
3081 {
3082 // L(FL("setting previously set attr on '%s'")
3083 // % file_path(pth));
3084 safe_insert(c.attrs_set,
3085 make_pair(make_pair(pth, k), new_word(rng)));
3086 }
3087 }
3088 else
3089 {
3090 // L(FL("setting attr on '%s'") % file_path(pth));
3091 safe_insert(c.attrs_set,
3092 make_pair(make_pair(pth, new_word(rng)), new_word(rng)));
3093 }
3094 break;
3095 }
3096 }
3097 // now do it
3098 apply_cset_and_do_testing(r, c, nis);
3099}
3100
3101testing_node_id_source::testing_node_id_source()
3102 : curr(first_node)
3103{}
3104
3105node_id
3106testing_node_id_source::next()
3107{
3108 // L(FL("creating node %x") % curr);
3109 node_id n = curr++;
3110 I(!temp_node(n));
3111 return n;
3112}
3113
3114template <> void
3115dump(int const & i, string & out)
3116{
3117 out = lexical_cast<string>(i) + "\n";
3118}
3119
3120UNIT_TEST(roster, random_actions)
3121{
3122 randomizer rng;
3123 roster_t r;
3124 testing_node_id_source nis;
3125
3126 roster_t empty, prev, recent, ancient;
3127
3128 {
3129 // give all the rosters a root
3130 split_path root;
3131 cset c;
3132 root.push_back(the_null_component);
3133 c.dirs_added.insert(root);
3134 apply_cset_and_do_testing(r, c, nis);
3135 }
3136
3137 empty = ancient = recent = prev = r;
3138 for (int i = 0; i < 2000; )
3139 {
3140 int manychanges = 100 + rng.uniform(300);
3141 // P(F("random roster actions: outer step at %d, making %d changes")
3142 // % i % manychanges);
3143
3144 for (int outer_limit = i + manychanges; i < outer_limit; )
3145 {
3146 int fewchanges = 5 + rng.uniform(10);
3147 // P(F("random roster actions: inner step at %d, making %d changes")
3148 // % i % fewchanges);
3149
3150 for (int inner_limit = i + fewchanges; i < inner_limit; i++)
3151 {
3152 // P(F("random roster actions: change %d") % i);
3153 perform_random_action(r, nis, rng);
3154 I(!(prev == r));
3155 prev = r;
3156 }
3157 tests_on_two_rosters(recent, r, nis);
3158 tests_on_two_rosters(empty, r, nis);
3159 recent = r;
3160 }
3161 tests_on_two_rosters(ancient, r, nis);
3162 ancient = r;
3163 }
3164}
3165
3166// some of our raising operations leave our state corrupted. so rather than
3167// trying to do all the illegal things in one pass, we re-run this function a
3168// bunch of times, and each time we do only one of these potentially
3169// corrupting tests. Test numbers are in the range [0, total).
3170
3171#define MAYBE(code) if (total == to_run) { L(FL(#code)); code; return; } ++total
3172
3173static void
3174check_sane_roster_do_tests(int to_run, int& total)
3175{
3176 total = 0;
3177 testing_node_id_source nis;
3178 roster_t r;
3179 MM(r);
3180
3181 // roster must have a root dir
3182 MAYBE(BOOST_CHECK_THROW(r.check_sane(false), logic_error));
3183 MAYBE(BOOST_CHECK_THROW(r.check_sane(true), logic_error));
3184
3185 split_path sp_, sp_foo, sp_foo_bar, sp_foo_baz;
3186 file_path().split(sp_);
3187 file_path_internal("foo").split(sp_foo);
3188 file_path_internal("foo/bar").split(sp_foo_bar);
3189 file_path_internal("foo/baz").split(sp_foo_baz);
3190 node_id nid_f = r.create_file_node(file_id(string("0000000000000000000000000000000000000000")),
3191 nis);
3192 // root must be a directory, not a file
3193 MAYBE(BOOST_CHECK_THROW(r.attach_node(nid_f, sp_), logic_error));
3194
3195 node_id root_dir = r.create_dir_node(nis);
3196 r.attach_node(root_dir, sp_);
3197 // has a root dir, but a detached file
3198 MAYBE(BOOST_CHECK_THROW(r.check_sane(false), logic_error));
3199 MAYBE(BOOST_CHECK_THROW(r.check_sane(true), logic_error));
3200
3201 r.attach_node(nid_f, sp_foo);
3202 // now should be sane
3203 BOOST_CHECK_NOT_THROW(r.check_sane(false), logic_error);
3204 BOOST_CHECK_NOT_THROW(r.check_sane(true), logic_error);
3205
3206 node_id nid_d = r.create_dir_node(nis);
3207 // if "foo" exists, can't attach another node at "foo"
3208 MAYBE(BOOST_CHECK_THROW(r.attach_node(nid_d, sp_foo), logic_error));
3209 // if "foo" is a file, can't attach a node at "foo/bar"
3210 MAYBE(BOOST_CHECK_THROW(r.attach_node(nid_d, sp_foo_bar), logic_error));
3211
3212 BOOST_CHECK(r.detach_node(sp_foo) == nid_f);
3213 r.attach_node(nid_d, sp_foo);
3214 r.attach_node(nid_f, sp_foo_bar);
3215 BOOST_CHECK_NOT_THROW(r.check_sane(false), logic_error);
3216 BOOST_CHECK_NOT_THROW(r.check_sane(true), logic_error);
3217
3218 temp_node_id_source nis_tmp;
3219 node_id nid_tmp = r.create_dir_node(nis_tmp);
3220 // has a detached node
3221 MAYBE(BOOST_CHECK_THROW(r.check_sane(false), logic_error));
3222 MAYBE(BOOST_CHECK_THROW(r.check_sane(true), logic_error));
3223 r.attach_node(nid_tmp, sp_foo_baz);
3224 // now has no detached nodes, but one temp node
3225 MAYBE(BOOST_CHECK_THROW(r.check_sane(false), logic_error));
3226 BOOST_CHECK_NOT_THROW(r.check_sane(true), logic_error);
3227}
3228
3229#undef MAYBE
3230
3231UNIT_TEST(roster, check_sane_roster)
3232{
3233 int total;
3234 check_sane_roster_do_tests(-1, total);
3235 for (int to_run = 0; to_run < total; ++to_run)
3236 {
3237 L(FL("check_sane_roster_test: loop = %i (of %i)") % to_run % (total - 1));
3238 int tmp;
3239 check_sane_roster_do_tests(to_run, tmp);
3240 }
3241}
3242
3243UNIT_TEST(roster, check_sane_roster_loop)
3244{
3245 testing_node_id_source nis;
3246 roster_t r; MM(r);
3247 split_path root, foo_bar;
3248 file_path().split(root);
3249 file_path_internal("foo/bar").split(foo_bar);
3250 r.attach_node(r.create_dir_node(nis), root);
3251 node_id nid_foo = r.create_dir_node(nis);
3252 node_id nid_bar = r.create_dir_node(nis);
3253 r.attach_node(nid_foo, nid_bar, foo_bar[1]);
3254 r.attach_node(nid_bar, nid_foo, foo_bar[2]);
3255 BOOST_CHECK_THROW(r.check_sane(true), logic_error);
3256}
3257
3258UNIT_TEST(roster, check_sane_roster_screwy_dir_map)
3259{
3260 testing_node_id_source nis;
3261 roster_t r; MM(r);
3262 split_path root, foo;
3263 file_path().split(root);
3264 file_path_internal("foo").split(foo);
3265 r.attach_node(r.create_dir_node(nis), root);
3266 roster_t other; MM(other);
3267 node_id other_nid = other.create_dir_node(nis);
3268 dir_t root_n = downcast_to_dir_t(r.get_node(root));
3269 root_n->children.insert(make_pair(*(foo.end()-1), other.get_node(other_nid)));
3270 BOOST_CHECK_THROW(r.check_sane(), logic_error);
3271 // well, but that one was easy, actually, because a dir traversal will hit
3272 // more nodes than actually exist... so let's make it harder, by making sure
3273 // that a dir traversal will hit exactly as many nodes as actually exist.
3274 node_id distractor_nid = r.create_dir_node(nis);
3275 BOOST_CHECK_THROW(r.check_sane(), logic_error);
3276 // and even harder, by making that node superficially valid too
3277 dir_t distractor_n = downcast_to_dir_t(r.get_node(distractor_nid));
3278 distractor_n->parent = distractor_nid;
3279 distractor_n->name = *(foo.end()-1);
3280 distractor_n->children.insert(make_pair(distractor_n->name, distractor_n));
3281 BOOST_CHECK_THROW(r.check_sane(), logic_error);
3282}
3283
3284UNIT_TEST(roster, bad_attr)
3285{
3286 testing_node_id_source nis;
3287 roster_t r; MM(r);
3288 split_path root;
3289 file_path().split(root);
3290 r.attach_node(r.create_dir_node(nis), root);
3291 BOOST_CHECK_THROW(r.set_attr(root, attr_key("test_key1"),
3292 make_pair(false, attr_value("invalid"))),
3293 logic_error);
3294 BOOST_CHECK_NOT_THROW(r.check_sane(true), logic_error);
3295 safe_insert(r.get_node(root)->attrs,
3296 make_pair(attr_key("test_key2"),
3297 make_pair(false, attr_value("invalid"))));
3298 BOOST_CHECK_THROW(r.check_sane(true), logic_error);
3299}
3300
3301////////////////////////////////////////////////////////////////////////
3302// exhaustive marking tests
3303////////////////////////////////////////////////////////////////////////
3304
3305// The marking/roster generation code is extremely critical. It is the very
3306// core of monotone's versioning technology, very complex, and bugs can result
3307// in corrupt and nonsensical histories (not to mention erroneous merges and
3308// the like). Furthermore, the code that implements it is littered with
3309// case-by-case analysis, where copy-paste errors could easily occur. So the
3310// purpose of this section is to systematically and exhaustively test every
3311// possible case.
3312//
3313// Our underlying merger, *-merge, works on scalars, case-by-case. The cases are:
3314// 0 parent:
3315// a*
3316// 1 parent:
3317// a a
3318// | |
3319// a b*
3320// 2 parents:
3321// a a a a a b a b
3322// \ / \ / \ / \ /
3323// a b* c* a?
3324//
3325// Each node has a number of scalars associated with it:
3326// * basename+parent
3327// * file content (iff a file)
3328// * attributes
3329//
3330// So for each scalar, we want to test each way it can appear in each of the
3331// above shapes. This is made more complex by lifecycles. We can achieve a 0
3332// parent node as:
3333// * a node in a 0-parent roster (root revision)
3334// * a newly added node in a 1-parent roster
3335// * a newly added node in a 2-parent roster
3336// a 1 parent node as:
3337// * a pre-existing node in a 1-parent roster
3338// * a node in a 2-parent roster that only existed in one of the parents
3339// a 2 parent node as:
3340// * a pre-existing node in a 2-parent roster
3341//
3342// Because the basename+parent and file_content scalars have lifetimes that
3343// exactly match the lifetime of the node they are on, those are all the cases
3344// for these scalars. However, attrs make things a bit more complicated,
3345// because they can be added. An attr can have 0 parents:
3346// * in any of the above cases, with an attribute newly added on the node
3347// And one parent:
3348// * in any of the cases above with one node parent and the attr pre-existing
3349// * in a 2-parent node where the attr exists in only one of the parents
3350//
3351// Plus, just to be sure, in the merge cases we check both the given example
3352// and the mirror-reversed one, since the code implementing this could
3353// conceivably mark merge(A, B) right but get merge(B, A) wrong. And for the
3354// scalars that can appear on either files or dirs, we check both.
3355
3356// The following somewhat elaborate code implements all these checks. The
3357// most important background assumption to know, is that it always assumes
3358// (and this assumption is hard-coded in various places) that it is looking at
3359// one of the following topologies:
3360//
3361// old
3362//
3363// old
3364// |
3365// new
3366//
3367// old
3368// / \.
3369// left right
3370// \ /
3371// new
3372//
3373// There is various tricksiness in making sure that the root directory always
3374// has the right birth_revision, that nodes are created with good birth
3375// revisions and sane markings on the scalars we are not interested in, etc.
3376// This code is ugly and messy and could use refactoring, but it seems to
3377// work.
3378
3379////////////////
3380// These are some basic utility pieces handy for the exhaustive mark tests
3381
3382namespace
3383{
3384 template <typename T> set<T>
3385 singleton(T const & t)
3386 {
3387 set<T> s;
3388 s.insert(t);
3389 return s;
3390 }
3391
3392 template <typename T> set<T>
3393 doubleton(T const & t1, T const & t2)
3394 {
3395 set<T> s;
3396 s.insert(t1);
3397 s.insert(t2);
3398 return s;
3399 }
3400
3401 revision_id old_rid(string("0000000000000000000000000000000000000000"));
3402 revision_id left_rid(string("1111111111111111111111111111111111111111"));
3403 revision_id right_rid(string("2222222222222222222222222222222222222222"));
3404 revision_id new_rid(string("4444444444444444444444444444444444444444"));
3405
3406 split_path
3407 split(string const & s)
3408 {
3409 split_path sp;
3410 file_path_internal(s).split(sp);
3411 return sp;
3412 }
3413
3414////////////////
3415// These classes encapsulate information about all the different scalars
3416// that *-merge applies to.
3417
3418 typedef enum { scalar_a, scalar_b, scalar_c,
3419 scalar_none, scalar_none_2 } scalar_val;
3420
3421 void
3422 dump(scalar_val const & val, string & out)
3423 {
3424 switch (val)
3425 {
3426 case scalar_a: out = "scalar_a"; break;
3427 case scalar_b: out = "scalar_b"; break;
3428 case scalar_c: out = "scalar_c"; break;
3429 case scalar_none: out = "scalar_none"; break;
3430 case scalar_none_2: out = "scalar_none_2"; break;
3431 }
3432 out += "\n";
3433 }
3434
3435 struct a_scalar
3436 {
3437 virtual void set(revision_id const & scalar_origin_rid,
3438 scalar_val val, set<revision_id> const & this_scalar_mark,
3439 roster_t & roster, marking_map & markings)
3440 = 0;
3441 virtual ~a_scalar() {};
3442
3443 node_id_source & nis;
3444 node_id const root_nid;
3445 node_id const obj_under_test_nid;
3446 a_scalar(node_id_source & nis)
3447 : nis(nis), root_nid(nis.next()), obj_under_test_nid(nis.next())
3448 {}
3449
3450 void setup(roster_t & roster, marking_map & markings)
3451 {
3452 roster.create_dir_node(root_nid);
3453 roster.attach_node(root_nid, split(""));
3454 marking_t marking;
3455 marking.birth_revision = old_rid;
3456 marking.parent_name.insert(old_rid);
3457 safe_insert(markings, make_pair(root_nid, marking));
3458 }
3459
3460 virtual string my_type() const = 0;
3461
3462 virtual void dump(string & out) const
3463 {
3464 ostringstream oss;
3465 oss << "type: " << my_type() << '\n'
3466 << "root_nid: " << root_nid << '\n'
3467 << "obj_under_test_nid: " << obj_under_test_nid << '\n';
3468 out = oss.str();
3469 }
3470 };
3471
3472 void
3473 dump(a_scalar const & s, string & out)
3474 {
3475 s.dump(out);
3476 }
3477
3478 struct file_maker
3479 {
3480 static void make_obj(revision_id const & scalar_origin_rid, node_id nid,
3481 roster_t & roster, marking_map & markings)
3482 {
3483 make_file(scalar_origin_rid, nid,
3484 file_id(string("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")),
3485 roster, markings);
3486 }
3487 static void make_file(revision_id const & scalar_origin_rid, node_id nid,
3488 file_id const & fid,
3489 roster_t & roster, marking_map & markings)
3490 {
3491 roster.create_file_node(fid, nid);
3492 marking_t marking;
3493 marking.birth_revision = scalar_origin_rid;
3494 marking.parent_name = marking.file_content = singleton(scalar_origin_rid);
3495 safe_insert(markings, make_pair(nid, marking));
3496 }
3497 };
3498
3499 struct dir_maker
3500 {
3501 static void make_obj(revision_id const & scalar_origin_rid, node_id nid,
3502 roster_t & roster, marking_map & markings)
3503 {
3504 roster.create_dir_node(nid);
3505 marking_t marking;
3506 marking.birth_revision = scalar_origin_rid;
3507 marking.parent_name = singleton(scalar_origin_rid);
3508 safe_insert(markings, make_pair(nid, marking));
3509 }
3510 };
3511
3512 struct file_content_scalar : public a_scalar
3513 {
3514 virtual string my_type() const { return "file_content_scalar"; }
3515
3516 map<scalar_val, file_id> values;
3517 file_content_scalar(node_id_source & nis)
3518 : a_scalar(nis)
3519 {
3520 safe_insert(values,
3521 make_pair(scalar_a,
3522 file_id(string("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))));
3523 safe_insert(values,
3524 make_pair(scalar_b,
3525 file_id(string("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"))));
3526 safe_insert(values,
3527 make_pair(scalar_c,
3528 file_id(string("cccccccccccccccccccccccccccccccccccccccc"))));
3529 }
3530 virtual void
3531 set(revision_id const & scalar_origin_rid, scalar_val val,
3532 std::set<revision_id> const & this_scalar_mark,
3533 roster_t & roster, marking_map & markings)
3534 {
3535 setup(roster, markings);
3536 if (val != scalar_none)
3537 {
3538 file_maker::make_file(scalar_origin_rid, obj_under_test_nid,
3539 safe_get(values, val),
3540 roster, markings);
3541 roster.attach_node(obj_under_test_nid, split("foo"));
3542 markings[obj_under_test_nid].file_content = this_scalar_mark;
3543 }
3544 roster.check_sane_against(markings);
3545 }
3546 };
3547
3548 template <typename T>
3549 struct X_basename_scalar : public a_scalar
3550 {
3551 virtual string my_type() const { return "X_basename_scalar"; }
3552
3553 map<scalar_val, split_path> values;
3554 X_basename_scalar(node_id_source & nis)
3555 : a_scalar(nis)
3556 {
3557 safe_insert(values, make_pair(scalar_a, split("a")));
3558 safe_insert(values, make_pair(scalar_b, split("b")));
3559 safe_insert(values, make_pair(scalar_c, split("c")));
3560 }
3561 virtual void
3562 set(revision_id const & scalar_origin_rid, scalar_val val,
3563 std::set<revision_id> const & this_scalar_mark,
3564 roster_t & roster, marking_map & markings)
3565 {
3566 setup(roster, markings);
3567 if (val != scalar_none)
3568 {
3569 T::make_obj(scalar_origin_rid, obj_under_test_nid, roster, markings);
3570 roster.attach_node(obj_under_test_nid, safe_get(values, val));
3571 markings[obj_under_test_nid].parent_name = this_scalar_mark;
3572 }
3573 roster.check_sane_against(markings);
3574 }
3575 };
3576
3577 template <typename T>
3578 struct X_parent_scalar : public a_scalar
3579 {
3580 virtual string my_type() const { return "X_parent_scalar"; }
3581
3582 map<scalar_val, split_path> values;
3583 node_id const a_nid, b_nid, c_nid;
3584 X_parent_scalar(node_id_source & nis)
3585 : a_scalar(nis), a_nid(nis.next()), b_nid(nis.next()), c_nid(nis.next())
3586 {
3587 safe_insert(values, make_pair(scalar_a, split("dir_a/foo")));
3588 safe_insert(values, make_pair(scalar_b, split("dir_b/foo")));
3589 safe_insert(values, make_pair(scalar_c, split("dir_c/foo")));
3590 }
3591 void
3592 setup_dirs(roster_t & roster, marking_map & markings)
3593 {
3594 roster.create_dir_node(a_nid);
3595 roster.attach_node(a_nid, split("dir_a"));
3596 roster.create_dir_node(b_nid);
3597 roster.attach_node(b_nid, split("dir_b"));
3598 roster.create_dir_node(c_nid);
3599 roster.attach_node(c_nid, split("dir_c"));
3600 marking_t marking;
3601 marking.birth_revision = old_rid;
3602 marking.parent_name.insert(old_rid);
3603 safe_insert(markings, make_pair(a_nid, marking));
3604 safe_insert(markings, make_pair(b_nid, marking));
3605 safe_insert(markings, make_pair(c_nid, marking));
3606 }
3607 virtual void
3608 set(revision_id const & scalar_origin_rid, scalar_val val,
3609 std::set<revision_id> const & this_scalar_mark,
3610 roster_t & roster, marking_map & markings)
3611 {
3612 setup(roster, markings);
3613 setup_dirs(roster, markings);
3614 if (val != scalar_none)
3615 {
3616 T::make_obj(scalar_origin_rid, obj_under_test_nid, roster, markings);
3617 roster.attach_node(obj_under_test_nid, safe_get(values, val));
3618 markings[obj_under_test_nid].parent_name = this_scalar_mark;
3619 }
3620 roster.check_sane_against(markings);
3621 }
3622 };
3623
3624 // this scalar represents an attr whose node already exists, and we put an
3625 // attr on it.
3626 template <typename T>
3627 struct X_attr_existing_node_scalar : public a_scalar
3628 {
3629 virtual string my_type() const { return "X_attr_scalar"; }
3630
3631 map<scalar_val, pair<bool, attr_value> > values;
3632 X_attr_existing_node_scalar(node_id_source & nis)
3633 : a_scalar(nis)
3634 {
3635 safe_insert(values, make_pair(scalar_a, make_pair(true, attr_value("a"))));
3636 safe_insert(values, make_pair(scalar_b, make_pair(true, attr_value("b"))));
3637 safe_insert(values, make_pair(scalar_c, make_pair(true, attr_value("c"))));
3638 }
3639 virtual void
3640 set(revision_id const & scalar_origin_rid, scalar_val val,
3641 std::set<revision_id> const & this_scalar_mark,
3642 roster_t & roster, marking_map & markings)
3643 {
3644 setup(roster, markings);
3645 // _not_ scalar_origin_rid, because our object exists everywhere, regardless of
3646 // when the attr shows up
3647 T::make_obj(old_rid, obj_under_test_nid, roster, markings);
3648 roster.attach_node(obj_under_test_nid, split("foo"));
3649 if (val != scalar_none)
3650 {
3651 safe_insert(roster.get_node(obj_under_test_nid)->attrs,
3652 make_pair(attr_key("test_key"), safe_get(values, val)));
3653 markings[obj_under_test_nid].attrs[attr_key("test_key")] = this_scalar_mark;
3654 }
3655 roster.check_sane_against(markings);
3656 }
3657 };
3658
3659 // this scalar represents an attr whose node does not exist; we create the
3660 // node when we create the attr.
3661 template <typename T>
3662 struct X_attr_new_node_scalar : public a_scalar
3663 {
3664 virtual string my_type() const { return "X_attr_scalar"; }
3665
3666 map<scalar_val, pair<bool, attr_value> > values;
3667 X_attr_new_node_scalar(node_id_source & nis)
3668 : a_scalar(nis)
3669 {
3670 safe_insert(values, make_pair(scalar_a, make_pair(true, attr_value("a"))));
3671 safe_insert(values, make_pair(scalar_b, make_pair(true, attr_value("b"))));
3672 safe_insert(values, make_pair(scalar_c, make_pair(true, attr_value("c"))));
3673 }
3674 virtual void
3675 set(revision_id const & scalar_origin_rid, scalar_val val,
3676 std::set<revision_id> const & this_scalar_mark,
3677 roster_t & roster, marking_map & markings)
3678 {
3679 setup(roster, markings);
3680 if (val != scalar_none)
3681 {
3682 T::make_obj(scalar_origin_rid, obj_under_test_nid, roster, markings);
3683 roster.attach_node(obj_under_test_nid, split("foo"));
3684 safe_insert(roster.get_node(obj_under_test_nid)->attrs,
3685 make_pair(attr_key("test_key"), safe_get(values, val)));
3686 markings[obj_under_test_nid].attrs[attr_key("test_key")] = this_scalar_mark;
3687 }
3688 roster.check_sane_against(markings);
3689 }
3690 };
3691
3692 typedef vector<shared_ptr<a_scalar> > scalars;
3693 scalars
3694 all_scalars(node_id_source & nis)
3695 {
3696 scalars ss;
3697 ss.push_back(shared_ptr<a_scalar>(new file_content_scalar(nis)));
3698 ss.push_back(shared_ptr<a_scalar>(new X_basename_scalar<file_maker>(nis)));
3699 ss.push_back(shared_ptr<a_scalar>(new X_basename_scalar<dir_maker>(nis)));
3700 ss.push_back(shared_ptr<a_scalar>(new X_parent_scalar<file_maker>(nis)));
3701 ss.push_back(shared_ptr<a_scalar>(new X_parent_scalar<dir_maker>(nis)));
3702 ss.push_back(shared_ptr<a_scalar>(new X_attr_existing_node_scalar<file_maker>(nis)));
3703 ss.push_back(shared_ptr<a_scalar>(new X_attr_existing_node_scalar<dir_maker>(nis)));
3704 ss.push_back(shared_ptr<a_scalar>(new X_attr_new_node_scalar<file_maker>(nis)));
3705 ss.push_back(shared_ptr<a_scalar>(new X_attr_new_node_scalar<dir_maker>(nis)));
3706 return ss;
3707 }
3708}
3709
3710////////////////
3711// These functions encapsulate the logic for running a particular mark
3712// scenario with a particular scalar with 0, 1, or 2 roster parents.
3713
3714static void
3715run_with_0_roster_parents(a_scalar & s, revision_id scalar_origin_rid,
3716 scalar_val new_val,
3717 set<revision_id> const & new_mark_set,
3718 node_id_source & nis)
3719{
3720 MM(s);
3721 MM(scalar_origin_rid);
3722 MM(new_val);
3723 MM(new_mark_set);
3724 roster_t expected_roster; MM(expected_roster);
3725 marking_map expected_markings; MM(expected_markings);
3726
3727 s.set(scalar_origin_rid, new_val, new_mark_set, expected_roster, expected_markings);
3728
3729 roster_t empty_roster;
3730 cset cs; MM(cs);
3731 make_cset(empty_roster, expected_roster, cs);
3732
3733 roster_t new_roster; MM(new_roster);
3734 marking_map new_markings; MM(new_markings);
3735 // this function takes the old parent roster/marking and modifies them; in
3736 // our case, the parent roster/marking are empty, and so are our
3737 // roster/marking, so we don't need to do anything special.
3738 make_roster_for_nonmerge(cs, old_rid, new_roster, new_markings, nis);
3739
3740 I(equal_up_to_renumbering(expected_roster, expected_markings,
3741 new_roster, new_markings));
3742
3743 marking_map new_markings2; MM(new_markings2);
3744 mark_roster_with_no_parents(old_rid, new_roster, new_markings2);
3745 I(new_markings == new_markings2);
3746
3747 marking_map new_markings3; MM(new_markings3);
3748 roster_t parent3;
3749 marking_map old_markings3;
3750 mark_roster_with_one_parent(parent3, old_markings3, old_rid, new_roster,
3751 new_markings3);
3752 I(new_markings == new_markings3);
3753}
3754
3755static void
3756run_with_1_roster_parent(a_scalar & s,
3757 revision_id scalar_origin_rid,
3758 scalar_val parent_val,
3759 set<revision_id> const & parent_mark_set,
3760 scalar_val new_val,
3761 set<revision_id> const & new_mark_set,
3762 node_id_source & nis)
3763{
3764 MM(s);
3765 MM(scalar_origin_rid);
3766 MM(parent_val);
3767 MM(parent_mark_set);
3768 MM(new_val);
3769 MM(new_mark_set);
3770 roster_t parent_roster; MM(parent_roster);
3771 marking_map parent_markings; MM(parent_markings);
3772 roster_t expected_roster; MM(expected_roster);
3773 marking_map expected_markings; MM(expected_markings);
3774
3775 s.set(scalar_origin_rid, parent_val, parent_mark_set, parent_roster, parent_markings);
3776 s.set(scalar_origin_rid, new_val, new_mark_set, expected_roster, expected_markings);
3777
3778 cset cs; MM(cs);
3779 make_cset(parent_roster, expected_roster, cs);
3780
3781 roster_t new_roster; MM(new_roster);
3782 marking_map new_markings; MM(new_markings);
3783 new_roster = parent_roster;
3784 new_markings = parent_markings;
3785 make_roster_for_nonmerge(cs, new_rid, new_roster, new_markings, nis);
3786
3787 I(equal_up_to_renumbering(expected_roster, expected_markings,
3788 new_roster, new_markings));
3789
3790 marking_map new_markings2; MM(new_markings2);
3791 mark_roster_with_one_parent(parent_roster, parent_markings,
3792 new_rid, new_roster, new_markings2);
3793 I(new_markings == new_markings2);
3794}
3795
3796static void
3797run_with_2_roster_parents(a_scalar & s,
3798 revision_id scalar_origin_rid,
3799 scalar_val left_val,
3800 set<revision_id> const & left_mark_set,
3801 scalar_val right_val,
3802 set<revision_id> const & right_mark_set,
3803 scalar_val new_val,
3804 set<revision_id> const & new_mark_set,
3805 node_id_source & nis)
3806{
3807 MM(s);
3808 MM(scalar_origin_rid);
3809 MM(left_val);
3810 MM(left_mark_set);
3811 MM(right_val);
3812 MM(right_mark_set);
3813 MM(new_val);
3814 MM(new_mark_set);
3815 roster_t left_roster; MM(left_roster);
3816 roster_t right_roster; MM(right_roster);
3817 roster_t expected_roster; MM(expected_roster);
3818 marking_map left_markings; MM(left_markings);
3819 marking_map right_markings; MM(right_markings);
3820 marking_map expected_markings; MM(expected_markings);
3821
3822 s.set(scalar_origin_rid, left_val, left_mark_set, left_roster, left_markings);
3823 s.set(scalar_origin_rid, right_val, right_mark_set, right_roster, right_markings);
3824 s.set(scalar_origin_rid, new_val, new_mark_set, expected_roster, expected_markings);
3825
3826 cset left_cs; MM(left_cs);
3827 cset right_cs; MM(right_cs);
3828 make_cset(left_roster, expected_roster, left_cs);
3829 make_cset(right_roster, expected_roster, right_cs);
3830
3831 set<revision_id> left_uncommon_ancestors; MM(left_uncommon_ancestors);
3832 left_uncommon_ancestors.insert(left_rid);
3833 set<revision_id> right_uncommon_ancestors; MM(right_uncommon_ancestors);
3834 right_uncommon_ancestors.insert(right_rid);
3835
3836 roster_t new_roster; MM(new_roster);
3837 marking_map new_markings; MM(new_markings);
3838 make_roster_for_merge(left_rid, left_roster, left_markings, left_cs,
3839 left_uncommon_ancestors,
3840 right_rid, right_roster, right_markings, right_cs,
3841 right_uncommon_ancestors,
3842 new_rid, new_roster, new_markings,
3843 nis);
3844
3845 I(equal_up_to_renumbering(expected_roster, expected_markings,
3846 new_roster, new_markings));
3847}
3848
3849////////////////
3850// These functions encapsulate all the different ways to get a 0 parent node,
3851// a 1 parent node, and a 2 parent node.
3852
3853////////////////
3854// These functions encapsulate all the different ways to get a 0 parent
3855// scalar, a 1 parent scalar, and a 2 parent scalar.
3856
3857// FIXME: have clients just use s.nis instead of passing it separately...?
3858
3859static void
3860run_a_2_scalar_parent_mark_scenario_exact(revision_id const & scalar_origin_rid,
3861 scalar_val left_val,
3862 set<revision_id> const & left_mark_set,
3863 scalar_val right_val,
3864 set<revision_id> const & right_mark_set,
3865 scalar_val new_val,
3866 set<revision_id> const & new_mark_set)
3867{
3868 testing_node_id_source nis;
3869 scalars ss = all_scalars(nis);
3870 for (scalars::const_iterator i = ss.begin(); i != ss.end(); ++i)
3871 {
3872 run_with_2_roster_parents(**i, scalar_origin_rid,
3873 left_val, left_mark_set,
3874 right_val, right_mark_set,
3875 new_val, new_mark_set,
3876 nis);
3877 }
3878}
3879
3880static revision_id
3881flip_revision_id(revision_id const & rid)
3882{
3883 if (rid == old_rid || rid == new_rid)
3884 return rid;
3885 else if (rid == left_rid)
3886 return right_rid;
3887 else if (rid == right_rid)
3888 return left_rid;
3889 else
3890 I(false);
3891}
3892
3893static set<revision_id>
3894flip_revision(set<revision_id> const & rids)
3895{
3896 set<revision_id> flipped_rids;
3897 for (set<revision_id>::const_iterator i = rids.begin(); i != rids.end(); ++i)
3898 flipped_rids.insert(flip_revision_id(*i));
3899 return flipped_rids;
3900}
3901
3902static void
3903run_a_2_scalar_parent_mark_scenario(revision_id const & scalar_origin_rid,
3904 scalar_val left_val,
3905 set<revision_id> const & left_mark_set,
3906 scalar_val right_val,
3907 set<revision_id> const & right_mark_set,
3908 scalar_val new_val,
3909 set<revision_id> const & new_mark_set)
3910{
3911 // run both what we're given...
3912 run_a_2_scalar_parent_mark_scenario_exact(scalar_origin_rid,
3913 left_val, left_mark_set,
3914 right_val, right_mark_set,
3915 new_val, new_mark_set);
3916 // ...and its symmetric reflection. but we have to flip the mark set,
3917 // because the exact stuff has hard-coded the names of the various
3918 // revisions and their uncommon ancestor sets.
3919 {
3920 set<revision_id> flipped_left_mark_set = flip_revision(left_mark_set);
3921 set<revision_id> flipped_right_mark_set = flip_revision(right_mark_set);
3922 set<revision_id> flipped_new_mark_set = flip_revision(new_mark_set);
3923
3924 run_a_2_scalar_parent_mark_scenario_exact(flip_revision_id(scalar_origin_rid),
3925 right_val, flipped_right_mark_set,
3926 left_val, flipped_left_mark_set,
3927 new_val, flipped_new_mark_set);
3928 }
3929}
3930
3931static void
3932run_a_2_scalar_parent_mark_scenario(scalar_val left_val,
3933 set<revision_id> const & left_mark_set,
3934 scalar_val right_val,
3935 set<revision_id> const & right_mark_set,
3936 scalar_val new_val,
3937 set<revision_id> const & new_mark_set)
3938{
3939 run_a_2_scalar_parent_mark_scenario(old_rid,
3940 left_val, left_mark_set,
3941 right_val, right_mark_set,
3942 new_val, new_mark_set);
3943}
3944
3945static void
3946run_a_1_scalar_parent_mark_scenario(scalar_val parent_val,
3947 set<revision_id> const & parent_mark_set,
3948 scalar_val new_val,
3949 set<revision_id> const & new_mark_set)
3950{
3951 {
3952 testing_node_id_source nis;
3953 scalars ss = all_scalars(nis);
3954 for (scalars::const_iterator i = ss.begin(); i != ss.end(); ++i)
3955 run_with_1_roster_parent(**i, old_rid,
3956 parent_val, parent_mark_set,
3957 new_val, new_mark_set,
3958 nis);
3959 }
3960 // this is an asymmetric, test, so run it via the code that will test it
3961 // both ways
3962 run_a_2_scalar_parent_mark_scenario(left_rid,
3963 parent_val, parent_mark_set,
3964 scalar_none, set<revision_id>(),
3965 new_val, new_mark_set);
3966}
3967
3968static void
3969run_a_0_scalar_parent_mark_scenario()
3970{
3971 {
3972 testing_node_id_source nis;
3973 scalars ss = all_scalars(nis);
3974 for (scalars::const_iterator i = ss.begin(); i != ss.end(); ++i)
3975 {
3976 run_with_0_roster_parents(**i, old_rid, scalar_a, singleton(old_rid), nis);
3977 run_with_1_roster_parent(**i, new_rid,
3978 scalar_none, set<revision_id>(),
3979 scalar_a, singleton(new_rid),
3980 nis);
3981 run_with_2_roster_parents(**i, new_rid,
3982 scalar_none, set<revision_id>(),
3983 scalar_none, set<revision_id>(),
3984 scalar_a, singleton(new_rid),
3985 nis);
3986 }
3987 }
3988}
3989
3990////////////////
3991// These functions contain the actual list of *-merge cases that we would like
3992// to test.
3993
3994UNIT_TEST(roster, all_0_scalar_parent_mark_scenarios)
3995{
3996 L(FL("TEST: begin checking 0-parent marking"));
3997 // a*
3998 run_a_0_scalar_parent_mark_scenario();
3999 L(FL("TEST: end checking 0-parent marking"));
4000}
4001
4002UNIT_TEST(roster, all_1_scalar_parent_mark_scenarios)
4003{
4004 L(FL("TEST: begin checking 1-parent marking"));
4005 // a
4006 // |
4007 // a
4008 run_a_1_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4009 scalar_a, singleton(old_rid));
4010 // a*
4011 // |
4012 // a
4013 run_a_1_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4014 scalar_a, singleton(left_rid));
4015 // a* a*
4016 // \ /
4017 // a
4018 // |
4019 // a
4020 run_a_1_scalar_parent_mark_scenario(scalar_a, doubleton(left_rid, right_rid),
4021 scalar_a, doubleton(left_rid, right_rid));
4022 // a
4023 // |
4024 // b*
4025 run_a_1_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4026 scalar_b, singleton(new_rid));
4027 // a*
4028 // |
4029 // b*
4030 run_a_1_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4031 scalar_b, singleton(new_rid));
4032 // a* a*
4033 // \ /
4034 // a
4035 // |
4036 // b*
4037 run_a_1_scalar_parent_mark_scenario(scalar_a, doubleton(left_rid, right_rid),
4038 scalar_b, singleton(new_rid));
4039 L(FL("TEST: end checking 1-parent marking"));
4040}
4041
4042UNIT_TEST(roster, all_2_scalar_parent_mark_scenarios)
4043{
4044 L(FL("TEST: begin checking 2-parent marking"));
4045 ///////////////////////////////////////////////////////////////////
4046 // a a
4047 // \ /
4048 // a
4049 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4050 scalar_a, singleton(old_rid),
4051 scalar_a, singleton(old_rid));
4052 // a a*
4053 // \ /
4054 // a
4055 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4056 scalar_a, singleton(right_rid),
4057 scalar_a, doubleton(old_rid, right_rid));
4058 // a* a*
4059 // \ /
4060 // a
4061 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4062 scalar_a, singleton(right_rid),
4063 scalar_a, doubleton(left_rid, right_rid));
4064
4065 ///////////////////////////////////////////////////////////////////
4066 // a a
4067 // \ /
4068 // b*
4069 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4070 scalar_a, singleton(old_rid),
4071 scalar_b, singleton(new_rid));
4072 // a a*
4073 // \ /
4074 // b*
4075 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4076 scalar_a, singleton(right_rid),
4077 scalar_b, singleton(new_rid));
4078 // a* a*
4079 // \ /
4080 // b*
4081 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4082 scalar_a, singleton(right_rid),
4083 scalar_b, singleton(new_rid));
4084
4085 ///////////////////////////////////////////////////////////////////
4086 // a* b*
4087 // \ /
4088 // c*
4089 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4090 scalar_b, singleton(right_rid),
4091 scalar_c, singleton(new_rid));
4092 // a b*
4093 // \ /
4094 // c*
4095 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4096 scalar_b, singleton(right_rid),
4097 scalar_c, singleton(new_rid));
4098 // this case cannot actually arise, because if *(a) = *(b) then val(a) =
4099 // val(b). but hey.
4100 // a b
4101 // \ /
4102 // c*
4103 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4104 scalar_b, singleton(old_rid),
4105 scalar_c, singleton(new_rid));
4106
4107 ///////////////////////////////////////////////////////////////////
4108 // a* b*
4109 // \ /
4110 // a*
4111 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4112 scalar_b, singleton(right_rid),
4113 scalar_a, singleton(new_rid));
4114 // a b*
4115 // \ /
4116 // a*
4117 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(old_rid),
4118 scalar_b, singleton(right_rid),
4119 scalar_a, singleton(new_rid));
4120 // a* b
4121 // \ /
4122 // a
4123 run_a_2_scalar_parent_mark_scenario(scalar_a, singleton(left_rid),
4124 scalar_b, singleton(old_rid),
4125 scalar_a, singleton(left_rid));
4126
4127 // FIXME: be nice to test:
4128 // a* a* b
4129 // \ / /
4130 // a /
4131 // \ /
4132 // a
4133 L(FL("TEST: end checking 2-parent marking"));
4134}
4135
4136// there is _one_ remaining case that the above tests miss, because they
4137// couple scalar lifetimes and node lifetimes. Maybe they shouldn't do that,
4138// but anyway... until someone decides to refactor, we need this. The basic
4139// issue is that for content and name scalars, the scalar lifetime and the
4140// node lifetime are identical. For attrs, this isn't necessarily true. This
4141// is why we have two different attr scalars. Let's say that "." means a node
4142// that doesn't exist, and "+" means a node that exists but has no roster.
4143// The first scalar checks cases like
4144// +
4145// |
4146// a
4147//
4148// + +
4149// \ /
4150// a*
4151//
4152// a* +
4153// \ /
4154// a
4155// and the second one checks cases like
4156// .
4157// |
4158// a
4159//
4160// . .
4161// \ /
4162// a*
4163//
4164// a* .
4165// \ /
4166// a
4167// Between them, they cover _almost_ all possibilities. The one that they
4168// miss is:
4169// . +
4170// \ /
4171// a*
4172// (and its reflection).
4173// That is what this test checks.
4174// Sorry it's so code-duplication-iferous. Refactors would be good...
4175
4176namespace
4177{
4178 // this scalar represents an attr whose node may or may not already exist
4179 template <typename T>
4180 struct X_attr_mixed_scalar : public a_scalar
4181 {
4182 virtual string my_type() const { return "X_attr_scalar"; }
4183
4184 map<scalar_val, pair<bool, attr_value> > values;
4185 X_attr_mixed_scalar(node_id_source & nis)
4186 : a_scalar(nis)
4187 {
4188 safe_insert(values, make_pair(scalar_a, make_pair(true, attr_value("a"))));
4189 safe_insert(values, make_pair(scalar_b, make_pair(true, attr_value("b"))));
4190 safe_insert(values, make_pair(scalar_c, make_pair(true, attr_value("c"))));
4191 }
4192 virtual void
4193 set(revision_id const & scalar_origin_rid, scalar_val val,
4194 std::set<revision_id> const & this_scalar_mark,
4195 roster_t & roster, marking_map & markings)
4196 {
4197 setup(roster, markings);
4198 // scalar_none is . in the above notation
4199 // and scalar_none_2 is +
4200 if (val != scalar_none)
4201 {
4202 T::make_obj(scalar_origin_rid, obj_under_test_nid, roster, markings);
4203 roster.attach_node(obj_under_test_nid, split("foo"));
4204 }
4205 if (val != scalar_none && val != scalar_none_2)
4206 {
4207 safe_insert(roster.get_node(obj_under_test_nid)->attrs,
4208 make_pair(attr_key("test_key"), safe_get(values, val)));
4209 markings[obj_under_test_nid].attrs[attr_key("test_key")] = this_scalar_mark;
4210 }
4211 roster.check_sane_against(markings);
4212 }
4213 };
4214}
4215
4216UNIT_TEST(roster, residual_attr_mark_scenario)
4217{
4218 L(FL("TEST: begin checking residual attr marking case"));
4219 {
4220 testing_node_id_source nis;
4221 X_attr_mixed_scalar<file_maker> s(nis);
4222 run_with_2_roster_parents(s, left_rid,
4223 scalar_none_2, set<revision_id>(),
4224 scalar_none, set<revision_id>(),
4225 scalar_a, singleton(new_rid),
4226 nis);
4227 }
4228 {
4229 testing_node_id_source nis;
4230 X_attr_mixed_scalar<dir_maker> s(nis);
4231 run_with_2_roster_parents(s, left_rid,
4232 scalar_none_2, set<revision_id>(),
4233 scalar_none, set<revision_id>(),
4234 scalar_a, singleton(new_rid),
4235 nis);
4236 }
4237 {
4238 testing_node_id_source nis;
4239 X_attr_mixed_scalar<file_maker> s(nis);
4240 run_with_2_roster_parents(s, right_rid,
4241 scalar_none, set<revision_id>(),
4242 scalar_none_2, set<revision_id>(),
4243 scalar_a, singleton(new_rid),
4244 nis);
4245 }
4246 {
4247 testing_node_id_source nis;
4248 X_attr_mixed_scalar<dir_maker> s(nis);
4249 run_with_2_roster_parents(s, right_rid,
4250 scalar_none, set<revision_id>(),
4251 scalar_none_2, set<revision_id>(),
4252 scalar_a, singleton(new_rid),
4253 nis);
4254 }
4255 L(FL("TEST: end checking residual attr marking case"));
4256}
4257
4258////////////////////////////////////////////////////////////////////////
4259// end of exhaustive tests
4260////////////////////////////////////////////////////////////////////////
4261
4262////////////////////////////////////////////////////////////////////////
4263// lifecyle tests
4264////////////////////////////////////////////////////////////////////////
4265
4266// nodes can't survive dying on one side of a merge
4267UNIT_TEST(roster, die_die_die_merge)
4268{
4269 roster_t left_roster; MM(left_roster);
4270 marking_map left_markings; MM(left_markings);
4271 roster_t right_roster; MM(right_roster);
4272 marking_map right_markings; MM(right_markings);
4273 testing_node_id_source nis;
4274
4275 // left roster is empty except for the root
4276 left_roster.attach_node(left_roster.create_dir_node(nis), split(""));
4277 marking_t an_old_marking;
4278 an_old_marking.birth_revision = old_rid;
4279 an_old_marking.parent_name = singleton(old_rid);
4280 safe_insert(left_markings, make_pair(left_roster.get_node(split(""))->self,
4281 an_old_marking));
4282 // right roster is identical, except for a dir created in the old rev
4283 right_roster = left_roster;
4284 right_markings = left_markings;
4285 right_roster.attach_node(right_roster.create_dir_node(nis), split("foo"));
4286 safe_insert(right_markings, make_pair(right_roster.get_node(split("foo"))->self,
4287 an_old_marking));
4288
4289 left_roster.check_sane_against(left_markings);
4290 right_roster.check_sane_against(right_markings);
4291
4292 cset left_cs; MM(left_cs);
4293 // we add the node
4294 left_cs.dirs_added.insert(split("foo"));
4295 // we do nothing
4296 cset right_cs; MM(right_cs);
4297
4298 roster_t new_roster; MM(new_roster);
4299 marking_map new_markings; MM(new_markings);
4300
4301 // because the dir was created in the old rev, the left side has logically
4302 // seen it and killed it, so it needs to be dead in the result.
4303 BOOST_CHECK_THROW(
4304 make_roster_for_merge(left_rid, left_roster, left_markings, left_cs,
4305 singleton(left_rid),
4306 right_rid, right_roster, right_markings, right_cs,
4307 singleton(right_rid),
4308 new_rid, new_roster, new_markings,
4309 nis),
4310 logic_error);
4311 BOOST_CHECK_THROW(
4312 make_roster_for_merge(right_rid, right_roster, right_markings, right_cs,
4313 singleton(right_rid),
4314 left_rid, left_roster, left_markings, left_cs,
4315 singleton(left_rid),
4316 new_rid, new_roster, new_markings,
4317 nis),
4318 logic_error);
4319}
4320// nodes can't change type file->dir or dir->file
4321// make_cset fails
4322// merging a file and a dir with the same nid and no mention of what should
4323// happen to them fails
4324
4325UNIT_TEST(roster, same_nid_diff_type)
4326{
4327 randomizer rng;
4328 testing_node_id_source nis;
4329
4330 roster_t dir_roster; MM(dir_roster);
4331 marking_map dir_markings; MM(dir_markings);
4332 dir_roster.attach_node(dir_roster.create_dir_node(nis), split(""));
4333 marking_t marking;
4334 marking.birth_revision = old_rid;
4335 marking.parent_name = singleton(old_rid);
4336 safe_insert(dir_markings, make_pair(dir_roster.get_node(split(""))->self,
4337 marking));
4338
4339 roster_t file_roster; MM(file_roster);
4340 marking_map file_markings; MM(file_markings);
4341 file_roster = dir_roster;
4342 file_markings = dir_markings;
4343
4344 // okay, they both have the root dir
4345 node_id nid = nis.next();
4346 dir_roster.create_dir_node(nid);
4347 dir_roster.attach_node(nid, split("foo"));
4348 safe_insert(dir_markings, make_pair(nid, marking));
4349
4350 file_roster.create_file_node(new_ident(rng), nid);
4351 file_roster.attach_node(nid, split("foo"));
4352 marking.file_content = singleton(old_rid);
4353 safe_insert(file_markings, make_pair(nid, marking));
4354
4355 dir_roster.check_sane_against(dir_markings);
4356 file_roster.check_sane_against(file_markings);
4357
4358 cset cs; MM(cs);
4359 BOOST_CHECK_THROW(make_cset(dir_roster, file_roster, cs), logic_error);
4360 BOOST_CHECK_THROW(make_cset(file_roster, dir_roster, cs), logic_error);
4361
4362 cset left_cs; MM(left_cs);
4363 cset right_cs; MM(right_cs);
4364 roster_t new_roster; MM(new_roster);
4365 marking_map new_markings; MM(new_markings);
4366 BOOST_CHECK_THROW(
4367 make_roster_for_merge(left_rid, dir_roster, dir_markings, left_cs,
4368 singleton(left_rid),
4369 right_rid, file_roster, file_markings, right_cs,
4370 singleton(right_rid),
4371 new_rid, new_roster, new_markings,
4372 nis),
4373 logic_error);
4374 BOOST_CHECK_THROW(
4375 make_roster_for_merge(left_rid, file_roster, file_markings, left_cs,
4376 singleton(left_rid),
4377 right_rid, dir_roster, dir_markings, right_cs,
4378 singleton(right_rid),
4379 new_rid, new_roster, new_markings,
4380 nis),
4381 logic_error);
4382
4383}
4384
4385UNIT_TEST(roster, write_roster)
4386{
4387 L(FL("TEST: write_roster_test"));
4388 roster_t r; MM(r);
4389 marking_map mm; MM(mm);
4390
4391 testing_node_id_source nis;
4392 split_path root, foo, xx, fo, foo_bar, foo_ang, foo_zoo;
4393 file_path().split(root);
4394 file_path_internal("foo").split(foo);
4395 file_path_internal("foo/ang").split(foo_ang);
4396 file_path_internal("foo/bar").split(foo_bar);
4397 file_path_internal("foo/zoo").split(foo_zoo);
4398 file_path_internal("fo").split(fo);
4399 file_path_internal("xx").split(xx);
4400
4401 file_id f1(string("1111111111111111111111111111111111111111"));
4402 revision_id rid(string("1234123412341234123412341234123412341234"));
4403 node_id nid;
4404
4405 // if adding new nodes, add them at the end to keep the node_id order
4406
4407 nid = nis.next();
4408 r.create_dir_node(nid);
4409 r.attach_node(nid, root);
4410 mark_new_node(rid, r.get_node(nid), mm[nid]);
4411
4412 nid = nis.next();
4413 r.create_dir_node(nid);
4414 r.attach_node(nid, foo);
4415 mark_new_node(rid, r.get_node(nid), mm[nid]);
4416
4417 nid = nis.next();
4418 r.create_dir_node(nid);
4419 r.attach_node(nid, xx);
4420 r.set_attr(xx, attr_key("say"), attr_value("hello"));
4421 mark_new_node(rid, r.get_node(nid), mm[nid]);
4422
4423 nid = nis.next();
4424 r.create_dir_node(nid);
4425 r.attach_node(nid, fo);
4426 mark_new_node(rid, r.get_node(nid), mm[nid]);
4427
4428 // check that files aren't ordered separately to dirs & vice versa
4429 nid = nis.next();
4430 r.create_file_node(f1, nid);
4431 r.attach_node(nid, foo_bar);
4432 r.set_attr(foo_bar, attr_key("fascist"), attr_value("tidiness"));
4433 mark_new_node(rid, r.get_node(nid), mm[nid]);
4434
4435 nid = nis.next();
4436 r.create_dir_node(nid);
4437 r.attach_node(nid, foo_ang);
4438 mark_new_node(rid, r.get_node(nid), mm[nid]);
4439
4440 nid = nis.next();
4441 r.create_dir_node(nid);
4442 r.attach_node(nid, foo_zoo);
4443 r.set_attr(foo_zoo, attr_key("regime"), attr_value("new"));
4444 r.clear_attr(foo_zoo, attr_key("regime"));
4445 mark_new_node(rid, r.get_node(nid), mm[nid]);
4446
4447 {
4448 // manifest first
4449 manifest_data mdat; MM(mdat);
4450 write_manifest_of_roster(r, mdat);
4451
4452 manifest_data
4453 expected(string("format_version \"1\"\n"
4454 "\n"
4455 "dir \"\"\n"
4456 "\n"
4457 "dir \"fo\"\n"
4458 "\n"
4459 "dir \"foo\"\n"
4460 "\n"
4461 "dir \"foo/ang\"\n"
4462 "\n"
4463 " file \"foo/bar\"\n"
4464 "content [1111111111111111111111111111111111111111]\n"
4465 " attr \"fascist\" \"tidiness\"\n"
4466 "\n"
4467 "dir \"foo/zoo\"\n"
4468 "\n"
4469 " dir \"xx\"\n"
4470 "attr \"say\" \"hello\"\n"
4471 ));
4472 MM(expected);
4473
4474 BOOST_CHECK_NOT_THROW( I(expected == mdat), logic_error);
4475 }
4476
4477 {
4478 // full roster with local parts
4479 roster_data rdat; MM(rdat);
4480 write_roster_and_marking(r, mm, rdat);
4481
4482 // node_id order is a hassle.
4483 // root 1, foo 2, xx 3, fo 4, foo_bar 5, foo_ang 6, foo_zoo 7
4484 roster_data
4485 expected(string("format_version \"1\"\n"
4486 "\n"
4487 " dir \"\"\n"
4488 " ident \"1\"\n"
4489 " birth [1234123412341234123412341234123412341234]\n"
4490 "path_mark [1234123412341234123412341234123412341234]\n"
4491 "\n"
4492 " dir \"fo\"\n"
4493 " ident \"4\"\n"
4494 " birth [1234123412341234123412341234123412341234]\n"
4495 "path_mark [1234123412341234123412341234123412341234]\n"
4496 "\n"
4497 " dir \"foo\"\n"
4498 " ident \"2\"\n"
4499 " birth [1234123412341234123412341234123412341234]\n"
4500 "path_mark [1234123412341234123412341234123412341234]\n"
4501 "\n"
4502 " dir \"foo/ang\"\n"
4503 " ident \"6\"\n"
4504 " birth [1234123412341234123412341234123412341234]\n"
4505 "path_mark [1234123412341234123412341234123412341234]\n"
4506 "\n"
4507 " file \"foo/bar\"\n"
4508 " content [1111111111111111111111111111111111111111]\n"
4509 " ident \"5\"\n"
4510 " attr \"fascist\" \"tidiness\"\n"
4511 " birth [1234123412341234123412341234123412341234]\n"
4512 " path_mark [1234123412341234123412341234123412341234]\n"
4513 "content_mark [1234123412341234123412341234123412341234]\n"
4514 " attr_mark \"fascist\" [1234123412341234123412341234123412341234]\n"
4515 "\n"
4516 " dir \"foo/zoo\"\n"
4517 " ident \"7\"\n"
4518 "dormant_attr \"regime\"\n"
4519 " birth [1234123412341234123412341234123412341234]\n"
4520 " path_mark [1234123412341234123412341234123412341234]\n"
4521 " attr_mark \"regime\" [1234123412341234123412341234123412341234]\n"
4522 "\n"
4523 " dir \"xx\"\n"
4524 " ident \"3\"\n"
4525 " attr \"say\" \"hello\"\n"
4526 " birth [1234123412341234123412341234123412341234]\n"
4527 "path_mark [1234123412341234123412341234123412341234]\n"
4528 "attr_mark \"say\" [1234123412341234123412341234123412341234]\n"
4529 ));
4530 MM(expected);
4531
4532 BOOST_CHECK_NOT_THROW( I(expected == rdat), logic_error);
4533 }
4534}
4535
4536UNIT_TEST(roster, check_sane_against)
4537{
4538 testing_node_id_source nis;
4539 split_path root, foo, bar;
4540 file_path().split(root);
4541 file_path_internal("foo").split(foo);
4542 file_path_internal("bar").split(bar);
4543
4544 file_id f1(string("1111111111111111111111111111111111111111"));
4545 revision_id rid(string("1234123412341234123412341234123412341234"));
4546 node_id nid;
4547
4548 {
4549 L(FL("TEST: check_sane_against_test, no extra nodes in rosters"));
4550 roster_t r; MM(r);
4551 marking_map mm; MM(mm);
4552
4553 nid = nis.next();
4554 r.create_dir_node(nid);
4555 r.attach_node(nid, root);
4556 mark_new_node(rid, r.get_node(nid), mm[nid]);
4557
4558 nid = nis.next();
4559 r.create_dir_node(nid);
4560 r.attach_node(nid, foo);
4561 mark_new_node(rid, r.get_node(nid), mm[nid]);
4562
4563 nid = nis.next();
4564 r.create_dir_node(nid);
4565 r.attach_node(nid, bar);
4566 // missing the marking
4567
4568 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4569 }
4570
4571 {
4572 L(FL("TEST: check_sane_against_test, no extra nodes in markings"));
4573 roster_t r; MM(r);
4574 marking_map mm; MM(mm);
4575
4576 nid = nis.next();
4577 r.create_dir_node(nid);
4578 r.attach_node(nid, root);
4579 mark_new_node(rid, r.get_node(nid), mm[nid]);
4580
4581 nid = nis.next();
4582 r.create_dir_node(nid);
4583 r.attach_node(nid, foo);
4584 mark_new_node(rid, r.get_node(nid), mm[nid]);
4585
4586 nid = nis.next();
4587 r.create_dir_node(nid);
4588 r.attach_node(nid, bar);
4589 mark_new_node(rid, r.get_node(nid), mm[nid]);
4590 r.detach_node(bar);
4591
4592 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4593 }
4594
4595 {
4596 L(FL("TEST: check_sane_against_test, missing birth rev"));
4597 roster_t r; MM(r);
4598 marking_map mm; MM(mm);
4599
4600 nid = nis.next();
4601 r.create_dir_node(nid);
4602 r.attach_node(nid, root);
4603 mark_new_node(rid, r.get_node(nid), mm[nid]);
4604
4605 nid = nis.next();
4606 r.create_dir_node(nid);
4607 r.attach_node(nid, foo);
4608 mark_new_node(rid, r.get_node(nid), mm[nid]);
4609 mm[nid].birth_revision = revision_id();
4610
4611 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4612 }
4613
4614 {
4615 L(FL("TEST: check_sane_against_test, missing path mark"));
4616 roster_t r; MM(r);
4617 marking_map mm; MM(mm);
4618
4619 nid = nis.next();
4620 r.create_dir_node(nid);
4621 r.attach_node(nid, root);
4622 mark_new_node(rid, r.get_node(nid), mm[nid]);
4623
4624 nid = nis.next();
4625 r.create_dir_node(nid);
4626 r.attach_node(nid, foo);
4627 mark_new_node(rid, r.get_node(nid), mm[nid]);
4628 mm[nid].parent_name.clear();
4629
4630 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4631 }
4632
4633 {
4634 L(FL("TEST: check_sane_against_test, missing content mark"));
4635 roster_t r; MM(r);
4636 marking_map mm; MM(mm);
4637
4638 nid = nis.next();
4639 r.create_dir_node(nid);
4640 r.attach_node(nid, root);
4641 mark_new_node(rid, r.get_node(nid), mm[nid]);
4642
4643 nid = nis.next();
4644 r.create_file_node(f1, nid);
4645 r.attach_node(nid, foo);
4646 mark_new_node(rid, r.get_node(nid), mm[nid]);
4647 mm[nid].file_content.clear();
4648
4649 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4650 }
4651
4652 {
4653 L(FL("TEST: check_sane_against_test, extra content mark"));
4654 roster_t r; MM(r);
4655 marking_map mm; MM(mm);
4656
4657 nid = nis.next();
4658 r.create_dir_node(nid);
4659 r.attach_node(nid, root);
4660 mark_new_node(rid, r.get_node(nid), mm[nid]);
4661
4662 nid = nis.next();
4663 r.create_dir_node(nid);
4664 r.attach_node(nid, foo);
4665 mark_new_node(rid, r.get_node(nid), mm[nid]);
4666 mm[nid].file_content.insert(rid);
4667
4668 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4669 }
4670
4671 {
4672 L(FL("TEST: check_sane_against_test, missing attr mark"));
4673 roster_t r; MM(r);
4674 marking_map mm; MM(mm);
4675
4676 nid = nis.next();
4677 r.create_dir_node(nid);
4678 r.attach_node(nid, root);
4679 // NB: mark and _then_ add attr
4680 mark_new_node(rid, r.get_node(nid), mm[nid]);
4681 r.set_attr(root, attr_key("my_key"), attr_value("my_value"));
4682
4683 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4684 }
4685
4686 {
4687 L(FL("TEST: check_sane_against_test, empty attr mark"));
4688 roster_t r; MM(r);
4689 marking_map mm; MM(mm);
4690
4691 nid = nis.next();
4692 r.create_dir_node(nid);
4693 r.attach_node(nid, root);
4694 r.set_attr(root, attr_key("my_key"), attr_value("my_value"));
4695 mark_new_node(rid, r.get_node(nid), mm[nid]);
4696 mm[nid].attrs[attr_key("my_key")].clear();
4697
4698 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4699 }
4700
4701 {
4702 L(FL("TEST: check_sane_against_test, extra attr mark"));
4703 roster_t r; MM(r);
4704 marking_map mm; MM(mm);
4705
4706 nid = nis.next();
4707 r.create_dir_node(nid);
4708 r.attach_node(nid, root);
4709 r.set_attr(root, attr_key("my_key"), attr_value("my_value"));
4710 mark_new_node(rid, r.get_node(nid), mm[nid]);
4711 mm[nid].attrs[attr_key("my_second_key")].insert(rid);
4712
4713 BOOST_CHECK_THROW(r.check_sane_against(mm), logic_error);
4714 }
4715}
4716
4717static void
4718check_post_roster_unification_ok(roster_t const & left,
4719 roster_t const & right,
4720 bool temp_nodes_ok)
4721{
4722 MM(left);
4723 MM(right);
4724 I(left == right);
4725 left.check_sane(temp_nodes_ok);
4726 right.check_sane(temp_nodes_ok);
4727}
4728
4729static void
4730create_random_unification_task(roster_t & left,
4731 roster_t & right,
4732 editable_roster_base & left_erb,
4733 editable_roster_base & right_erb,
4734 editable_roster_for_merge & left_erm,
4735 editable_roster_for_merge & right_erm,
4736 randomizer & rng)
4737{
4738 size_t n_nodes = 20 + rng.uniform(60);
4739
4740 // Stick in a root if there isn't one.
4741 if (!left.has_root())
4742 {
4743 I(!right.has_root());
4744 split_path root;
4745 root.push_back(the_null_component);
4746
4747 node_id left_nid = left_erm.create_dir_node();
4748 left_erm.attach_node(left_nid, root);
4749
4750 node_id right_nid = right_erm.create_dir_node();
4751 right_erm.attach_node(right_nid, root);
4752 }
4753
4754 // Now throw in a bunch of others
4755 for (size_t i = 0; i < n_nodes; ++i)
4756 {
4757 node_t left_n = random_element(left.all_nodes(), rng)->second;
4758
4759 // With equal probability, choose to make the new node appear to
4760 // be new in just the left, just the right, or both.
4761 editable_roster_base * left_er;
4762 editable_roster_base * right_er;
4763 switch (rng.uniform(2))
4764 {
4765 case 0: left_er = &left_erm; right_er = &right_erm; break;
4766 case 1: left_er = &left_erb; right_er = &right_erm; break;
4767 case 2: left_er = &left_erm; right_er = &right_erb; break;
4768 default: I(false);
4769 }
4770
4771 node_id left_nid, right_nid;
4772 if (rng.flip())
4773 {
4774 left_nid = left_er->create_dir_node();
4775 right_nid = right_er->create_dir_node();
4776 }
4777 else
4778 {
4779 file_id fid = new_ident(rng);
4780 left_nid = left_er->create_file_node(fid);
4781 right_nid = right_er->create_file_node(fid);
4782 }
4783
4784 split_path pth;
4785 left.get_name(left_n->self, pth);
4786
4787 I(right.has_node(pth));
4788
4789 if (is_file_t(left_n) || (pth.size() > 1 && rng.flip()))
4790 // Add a sibling of an existing entry.
4791 pth[pth.size() - 1] = new_component(rng);
4792 else
4793 // Add a child of an existing entry.
4794 pth.push_back(new_component(rng));
4795
4796 left_er->attach_node(left_nid, pth);
4797 right_er->attach_node(right_nid, pth);
4798 }
4799}
4800
4801static void
4802unify_rosters_randomized_core(node_id_source & tmp_nis,
4803 node_id_source & test_nis,
4804 bool temp_nodes_ok)
4805{
4806 roster_t left, right;
4807 randomizer rng;
4808 for (size_t i = 0; i < 30; ++i)
4809 {
4810 editable_roster_base left_erb(left, test_nis);
4811 editable_roster_base right_erb(right, test_nis);
4812 editable_roster_for_merge left_erm(left, tmp_nis);
4813 editable_roster_for_merge right_erm(right, tmp_nis);
4814
4815 create_random_unification_task(left, right,
4816 left_erb, right_erb,
4817 left_erm, right_erm, rng);
4818 unify_rosters(left, left_erm.new_nodes,
4819 right, right_erm.new_nodes,
4820 test_nis);
4821 check_post_roster_unification_ok(left, right, temp_nodes_ok);
4822 }
4823}
4824
4825UNIT_TEST(roster, unify_rosters_randomized_trueids)
4826{
4827 L(FL("TEST: begin checking unification of rosters (randomly, true IDs)"));
4828 temp_node_id_source tmp_nis;
4829 testing_node_id_source test_nis;
4830 unify_rosters_randomized_core(tmp_nis, test_nis, false);
4831 L(FL("TEST: end checking unification of rosters (randomly, true IDs)"));
4832}
4833
4834UNIT_TEST(roster, unify_rosters_randomized_tempids)
4835{
4836 L(FL("TEST: begin checking unification of rosters (randomly, temp IDs)"));
4837 temp_node_id_source tmp_nis;
4838 unify_rosters_randomized_core(tmp_nis, tmp_nis, true);
4839 L(FL("TEST: end checking unification of rosters (randomly, temp IDs)"));
4840}
4841
4842UNIT_TEST(roster, unify_rosters_end_to_end_ids)
4843{
4844 L(FL("TEST: begin checking unification of rosters (end to end, ids)"));
4845 revision_id has_rid = left_rid;
4846 revision_id has_not_rid = right_rid;
4847 file_id my_fid(string("9012901290129012901290129012901290129012"));
4848
4849 testing_node_id_source nis;
4850
4851 roster_t has_not_roster; MM(has_not_roster);
4852 marking_map has_not_markings; MM(has_not_markings);
4853 {
4854 has_not_roster.attach_node(has_not_roster.create_dir_node(nis), split(""));
4855 marking_t root_marking;
4856 root_marking.birth_revision = old_rid;
4857 root_marking.parent_name = singleton(old_rid);
4858 safe_insert(has_not_markings, make_pair(has_not_roster.root()->self,
4859 root_marking));
4860 }
4861
4862 roster_t has_roster = has_not_roster; MM(has_roster);
4863 marking_map has_markings = has_not_markings; MM(has_markings);
4864 node_id new_id;
4865 {
4866 new_id = has_roster.create_file_node(my_fid, nis);
4867 has_roster.attach_node(new_id, split("foo"));
4868 marking_t file_marking;
4869 file_marking.birth_revision = has_rid;
4870 file_marking.parent_name = file_marking.file_content = singleton(has_rid);
4871 safe_insert(has_markings, make_pair(new_id, file_marking));
4872 }
4873
4874 cset add_cs; MM(add_cs);
4875 safe_insert(add_cs.files_added, make_pair(split("foo"), my_fid));
4876 cset no_add_cs; MM(no_add_cs);
4877
4878 // added in left, then merged
4879 {
4880 roster_t new_roster; MM(new_roster);
4881 marking_map new_markings; MM(new_markings);
4882 make_roster_for_merge(has_rid, has_roster, has_markings, no_add_cs,
4883 singleton(has_rid),
4884 has_not_rid, has_not_roster, has_not_markings, add_cs,
4885 singleton(has_not_rid),
4886 new_rid, new_roster, new_markings,
4887 nis);
4888 I(new_roster.get_node(split("foo"))->self == new_id);
4889 }
4890 // added in right, then merged
4891 {
4892 roster_t new_roster; MM(new_roster);
4893 marking_map new_markings; MM(new_markings);
4894 make_roster_for_merge(has_not_rid, has_not_roster, has_not_markings, add_cs,
4895 singleton(has_not_rid),
4896 has_rid, has_roster, has_markings, no_add_cs,
4897 singleton(has_rid),
4898 new_rid, new_roster, new_markings,
4899 nis);
4900 I(new_roster.get_node(split("foo"))->self == new_id);
4901 }
4902 // added in merge
4903 // this is a little "clever", it uses the same has_not_roster twice, but the
4904 // second time it passes the has_rid, to make it a possible graph.
4905 {
4906 roster_t new_roster; MM(new_roster);
4907 marking_map new_markings; MM(new_markings);
4908 make_roster_for_merge(has_not_rid, has_not_roster, has_not_markings, add_cs,
4909 singleton(has_not_rid),
4910 has_rid, has_not_roster, has_not_markings, add_cs,
4911 singleton(has_rid),
4912 new_rid, new_roster, new_markings,
4913 nis);
4914 I(new_roster.get_node(split("foo"))->self
4915 != has_roster.get_node(split("foo"))->self);
4916 }
4917 L(FL("TEST: end checking unification of rosters (end to end, ids)"));
4918}
4919
4920UNIT_TEST(roster, unify_rosters_end_to_end_attr_corpses)
4921{
4922 L(FL("TEST: begin checking unification of rosters (end to end, attr corpses)"));
4923 revision_id first_rid = left_rid;
4924 revision_id second_rid = right_rid;
4925 file_id my_fid(string("9012901290129012901290129012901290129012"));
4926
4927 testing_node_id_source nis;
4928
4929 // Both rosters have the file "foo"; in one roster, it has the attr corpse
4930 // "testfoo1", and in the other, it has the attr corpse "testfoo2". Only
4931 // the second roster has the file "bar"; it has the attr corpse "testbar".
4932
4933 roster_t first_roster; MM(first_roster);
4934 marking_map first_markings; MM(first_markings);
4935 node_id foo_id;
4936 {
4937 first_roster.attach_node(first_roster.create_dir_node(nis), split(""));
4938 marking_t marking;
4939 marking.birth_revision = old_rid;
4940 marking.parent_name = singleton(old_rid);
4941 safe_insert(first_markings, make_pair(first_roster.root()->self, marking));
4942
4943 foo_id = first_roster.create_file_node(my_fid, nis);
4944 first_roster.attach_node(foo_id, split("foo"));
4945 marking.file_content = singleton(old_rid);
4946 safe_insert(first_markings,
4947 make_pair(first_roster.get_node(split("foo"))->self, marking));
4948 }
4949
4950 roster_t second_roster = first_roster; MM(second_roster);
4951 marking_map second_markings = first_markings; MM(second_markings);
4952 {
4953 second_roster.attach_node(second_roster.create_file_node(my_fid, nis),
4954 split("bar"));
4955 safe_insert(second_roster.get_node(split("bar"))->attrs,
4956 make_pair(attr_key("testbar"), make_pair(false, attr_value())));
4957 marking_t marking;
4958 marking.birth_revision = second_rid;
4959 marking.parent_name = marking.file_content = singleton(second_rid);
4960 safe_insert(marking.attrs,
4961 make_pair(attr_key("testbar"), singleton(second_rid)));
4962 safe_insert(second_markings,
4963 make_pair(second_roster.get_node(split("bar"))->self, marking));
4964 }
4965
4966 // put in the attrs on foo
4967 {
4968 safe_insert(first_roster.get_node(foo_id)->attrs,
4969 make_pair(attr_key("testfoo1"), make_pair(false, attr_value())));
4970 safe_insert(first_markings.find(foo_id)->second.attrs,
4971 make_pair(attr_key("testfoo1"), singleton(first_rid)));
4972 safe_insert(second_roster.get_node(foo_id)->attrs,
4973 make_pair(attr_key("testfoo2"), make_pair(false, attr_value())));
4974 safe_insert(second_markings.find(foo_id)->second.attrs,
4975 make_pair(attr_key("testfoo2"), singleton(second_rid)));
4976 }
4977
4978 cset add_cs; MM(add_cs);
4979 safe_insert(add_cs.files_added, make_pair(split("bar"), my_fid));
4980 cset no_add_cs; MM(no_add_cs);
4981
4982 {
4983 roster_t new_roster; MM(new_roster);
4984 marking_map new_markings; MM(new_markings);
4985 make_roster_for_merge(first_rid, first_roster, first_markings, add_cs,
4986 singleton(first_rid),
4987 second_rid, second_roster, second_markings, no_add_cs,
4988 singleton(second_rid),
4989 new_rid, new_roster, new_markings,
4990 nis);
4991 I(new_roster.get_node(split("foo"))->attrs.size() == 2);
4992 I(new_roster.get_node(split("bar"))->attrs
4993 == second_roster.get_node(split("bar"))->attrs);
4994 I(new_roster.get_node(split("bar"))->attrs.size() == 1);
4995 }
4996 {
4997 roster_t new_roster; MM(new_roster);
4998 marking_map new_markings; MM(new_markings);
4999 make_roster_for_merge(second_rid, second_roster, second_markings, no_add_cs,
5000 singleton(second_rid),
5001 first_rid, first_roster, first_markings, add_cs,
5002 singleton(first_rid),
5003 new_rid, new_roster, new_markings,
5004 nis);
5005 I(new_roster.get_node(split("foo"))->attrs.size() == 2);
5006 I(new_roster.get_node(split("bar"))->attrs
5007 == second_roster.get_node(split("bar"))->attrs);
5008 I(new_roster.get_node(split("bar"))->attrs.size() == 1);
5009 }
5010
5011 L(FL("TEST: end checking unification of rosters (end to end, attr corpses)"));
5012}
5013
5014#endif // BUILD_UNIT_TESTS
5015
5016// Local Variables:
5017// mode: C++
5018// fill-column: 76
5019// c-file-style: "gnu"
5020// indent-tabs-mode: nil
5021// End:
5022// 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