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