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