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