monotone

monotone Mtn Source Tree

Root/roster_merge.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 <set>
11
12#include "vocab.hh"
13#include "roster_merge.hh"
14#include "parallel_iter.hh"
15#include "safe_map.hh"
16
17using std::make_pair;
18using std::pair;
19using std::set;
20using std::string;
21
22bool
23roster_merge_result::is_clean() const
24{
25 return is_clean_except_for_content()
26 && file_content_conflicts.empty();
27}
28
29bool
30roster_merge_result::is_clean_except_for_content() const
31{
32 return node_name_conflicts.empty()
33 && node_attr_conflicts.empty()
34 && orphaned_node_conflicts.empty()
35 && rename_target_conflicts.empty()
36 && directory_loop_conflicts.empty()
37 && illegal_name_conflicts.empty()
38 && !missing_root_dir;
39}
40
41static void
42debug_describe_conflicts(roster_merge_result const & result, string & out)
43{
44 out = (FL("unclean roster_merge: %d name conflicts, %d content conflicts, %d attr conflicts, "
45 "%d orphaned node conflicts, %d rename target conflicts, %d directory loop conflicts\n")
46 % result.node_name_conflicts.size()
47 % result.file_content_conflicts.size()
48 % result.node_attr_conflicts.size()
49 % result.orphaned_node_conflicts.size()
50 % result.rename_target_conflicts.size()
51 % result.directory_loop_conflicts.size())
52 .str();
53
54 for (size_t i = 0; i < result.node_name_conflicts.size(); ++i)
55 out += (FL("name conflict on node %d: [parent %d, self %s] vs. [parent %d, self %s]")
56 % result.node_name_conflicts[i].nid
57 % result.node_name_conflicts[i].left.first
58 % result.node_name_conflicts[i].left.second
59 % result.node_name_conflicts[i].right.first
60 % result.node_name_conflicts[i].right.second)
61 .str();
62
63 for (size_t i = 0; i < result.file_content_conflicts.size(); ++i)
64 out += (FL("content conflict on node %d: [%s] vs. [%s]")
65 % result.file_content_conflicts[i].nid
66 % result.file_content_conflicts[i].left
67 % result.file_content_conflicts[i].right)
68 .str();
69
70 for (size_t i = 0; i < result.node_attr_conflicts.size(); ++i)
71 out += (FL("attribute conflict on node %d, key %s: [%d, %s] vs. [%d, %s]")
72 % result.node_attr_conflicts[i].nid
73 % result.node_attr_conflicts[i].key
74 % result.node_attr_conflicts[i].left.first
75 % result.node_attr_conflicts[i].left.second
76 % result.node_attr_conflicts[i].right.first
77 % result.node_attr_conflicts[i].right.second)
78 .str();
79
80 for (size_t i = 0; i < result.orphaned_node_conflicts.size(); ++i)
81 out += (FL("orphaned node conflict on node %d, dead parent %d, name %s")
82 % result.orphaned_node_conflicts[i].nid
83 % result.orphaned_node_conflicts[i].parent_name.first
84 % result.orphaned_node_conflicts[i].parent_name.second)
85 .str();
86
87 for (size_t i = 0; i < result.rename_target_conflicts.size(); ++i)
88 out += (FL("rename target conflict: nodes %d, %d, both want parent %d, name %s")
89 % result.rename_target_conflicts[i].nid1
90 % result.rename_target_conflicts[i].nid2
91 % result.rename_target_conflicts[i].parent_name.first
92 % result.rename_target_conflicts[i].parent_name.second)
93 .str();
94
95 for (size_t i = 0; i < result.directory_loop_conflicts.size(); ++i)
96 out += (FL("directory loop conflict: node %d, wanted parent %d, name %s")
97 % result.directory_loop_conflicts[i].nid
98 % result.directory_loop_conflicts[i].parent_name.first
99 % result.directory_loop_conflicts[i].parent_name.second)
100 .str();
101
102 for (size_t i = 0; i < result.illegal_name_conflicts.size(); ++i)
103 out += (FL("illegal name conflict: node %d, wanted parent %d, name %s")
104 % result.illegal_name_conflicts[i].nid
105 % result.illegal_name_conflicts[i].parent_name.first
106 % result.illegal_name_conflicts[i].parent_name.second)
107 .str();
108}
109
110template <> void
111dump(roster_merge_result const & result, string & out)
112{
113 debug_describe_conflicts(result, out);
114 string roster_part;
115 dump(result.roster, roster_part);
116 out += "\n\n";
117 out += roster_part;
118}
119
120void
121roster_merge_result::log_conflicts() const
122{
123 string str;
124 debug_describe_conflicts(*this, str);
125 L(FL("%s") % str);
126}
127
128void
129roster_merge_result::warn_non_content_conflicts() const
130{
131 for (size_t i = 0; i < node_name_conflicts.size(); ++i)
132 W(F("name conflict on node %d: [parent %d, self %s] vs. [parent %d, self %s]")
133 % node_name_conflicts[i].nid
134 % node_name_conflicts[i].left.first
135 % node_name_conflicts[i].left.second
136 % node_name_conflicts[i].right.first
137 % node_name_conflicts[i].right.second);
138
139 for (size_t i = 0; i < node_attr_conflicts.size(); ++i)
140 W(F("attribute conflict on node %d, key %s: [%d, %s] vs. [%d, %s]")
141 % node_attr_conflicts[i].nid
142 % node_attr_conflicts[i].key
143 % node_attr_conflicts[i].left.first
144 % node_attr_conflicts[i].left.second
145 % node_attr_conflicts[i].right.first
146 % node_attr_conflicts[i].right.second);
147
148 for (size_t i = 0; i < orphaned_node_conflicts.size(); ++i)
149 W(F("orphaned node conflict on node %d, dead parent %d, name %s")
150 % orphaned_node_conflicts[i].nid
151 % orphaned_node_conflicts[i].parent_name.first
152 % orphaned_node_conflicts[i].parent_name.second);
153
154 for (size_t i = 0; i < rename_target_conflicts.size(); ++i)
155 W(F("rename target conflict: nodes %d, %d, both want parent %d, name %s")
156 % rename_target_conflicts[i].nid1
157 % rename_target_conflicts[i].nid2
158 % rename_target_conflicts[i].parent_name.first
159 % rename_target_conflicts[i].parent_name.second);
160
161 for (size_t i = 0; i < directory_loop_conflicts.size(); ++i)
162 W(F("directory loop conflict: node %d, wanted parent %d, name %s")
163 % directory_loop_conflicts[i].nid
164 % directory_loop_conflicts[i].parent_name.first
165 % directory_loop_conflicts[i].parent_name.second);
166
167 for (size_t i = 0; i < illegal_name_conflicts.size(); ++i)
168 W(F("illegal name conflict: node %d, wanted parent %d, name %s")
169 % illegal_name_conflicts[i].nid
170 % illegal_name_conflicts[i].parent_name.first
171 % illegal_name_conflicts[i].parent_name.second);
172}
173
174void
175roster_merge_result::clear()
176{
177 node_name_conflicts.clear();
178 file_content_conflicts.clear();
179 node_attr_conflicts.clear();
180 orphaned_node_conflicts.clear();
181 rename_target_conflicts.clear();
182 directory_loop_conflicts.clear();
183 illegal_name_conflicts.clear();
184 missing_root_dir = false;
185 roster = roster_t();
186}
187
188namespace
189{
190 // a wins if *(b) > a. Which is to say that all members of b_marks are
191 // ancestors of a. But all members of b_marks are ancestors of the
192 // _b_, so the previous statement is the same as saying that _no_
193 // members of b_marks is an _uncommon_ ancestor of _b_.
194 bool
195 a_wins(set<revision_id> const & b_marks,
196 set<revision_id> const & b_uncommon_ancestors)
197 {
198 for (set<revision_id>::const_iterator i = b_marks.begin();
199 i != b_marks.end(); ++i)
200 if (b_uncommon_ancestors.find(*i) != b_uncommon_ancestors.end())
201 return false;
202 return true;
203 }
204
205 // returns true if merge was successful ('result' is valid), false otherwise
206 // ('conflict_descriptor' is valid).
207 template <typename T, typename C> bool
208 merge_scalar(T const & left,
209 set<revision_id> const & left_marks,
210 set<revision_id> const & left_uncommon_ancestors,
211 T const & right,
212 set<revision_id> const & right_marks,
213 set<revision_id> const & right_uncommon_ancestors,
214 T & result,
215 C & conflict_descriptor)
216 {
217 if (left == right)
218 {
219 result = left;
220 return true;
221 }
222 MM(left_marks);
223 MM(left_uncommon_ancestors);
224 MM(right_marks);
225 MM(right_uncommon_ancestors);
226 bool left_wins = a_wins(right_marks, right_uncommon_ancestors);
227 bool right_wins = a_wins(left_marks, left_uncommon_ancestors);
228 // two bools means 4 cases:
229 // left_wins && right_wins
230 // this is ambiguous clean merge, which is theoretically impossible.
231 I(!(left_wins && right_wins));
232 // left_wins && !right_wins
233 if (left_wins && !right_wins)
234 {
235 result = left;
236 return true;
237 }
238 // !left_wins && right_wins
239 if (!left_wins && right_wins)
240 {
241 result = right;
242 return true;
243 }
244 // !left_wins && !right_wins
245 if (!left_wins && !right_wins)
246 {
247 conflict_descriptor.left = left;
248 conflict_descriptor.right = right;
249 return false;
250 }
251 I(false);
252 }
253
254 inline void
255 create_node_for(node_t const & n, roster_t & new_roster)
256 {
257 if (is_dir_t(n))
258 new_roster.create_dir_node(n->self);
259 else if (is_file_t(n))
260 new_roster.create_file_node(file_id(), n->self);
261 else
262 I(false);
263 }
264
265 inline void
266 insert_if_unborn(node_t const & n,
267 marking_map const & markings,
268 set<revision_id> const & uncommon_ancestors,
269 roster_t & new_roster)
270 {
271 revision_id const & birth = safe_get(markings, n->self).birth_revision;
272 if (uncommon_ancestors.find(birth) != uncommon_ancestors.end())
273 create_node_for(n, new_roster);
274 }
275
276 bool
277 would_make_dir_loop(roster_t const & r, node_id nid, node_id parent)
278 {
279 // parent may not be fully attached yet; that's okay. that just means
280 // we'll run into a node with a null parent somewhere before we hit the
281 // actual root; whether we hit the actual root or not, hitting a node
282 // with a null parent will tell us that this particular attachment won't
283 // create a loop.
284 for (node_id curr = parent; !null_node(curr); curr = r.get_node(curr)->parent)
285 {
286 if (curr == nid)
287 return true;
288 }
289 return false;
290 }
291
292 void
293 assign_name(roster_merge_result & result, node_id nid,
294 node_id parent, path_component name)
295 {
296 // this function is reponsible for detecting structural conflicts. by the
297 // time we've gotten here, we have a node that's unambiguously decided on
298 // a name; but it might be that that name does not exist (because the
299 // parent dir is gone), or that it's already taken (by another node), or
300 // that putting this node there would create a directory loop. In all
301 // such cases, rather than actually attach the node, we write a conflict
302 // structure and leave it detached.
303
304 // the root dir is somewhat special. it can't be orphaned, and it can't
305 // make a dir loop. it can, however, have a name collision.
306 if (null_node(parent))
307 {
308 I(null_name(name));
309 if (result.roster.has_root())
310 {
311 // see comments below about name collisions.
312 rename_target_conflict c;
313 c.nid1 = nid;
314 c.nid2 = result.roster.root()->self;
315 c.parent_name = make_pair(parent, name);
316 split_path root_sp;
317 file_path().split(root_sp);
318 result.roster.detach_node(root_sp);
319 result.rename_target_conflicts.push_back(c);
320 return;
321 }
322 }
323 else
324 {
325 // orphan:
326 if (!result.roster.has_node(parent))
327 {
328 orphaned_node_conflict c;
329 c.nid = nid;
330 c.parent_name = make_pair(parent, name);
331 result.orphaned_node_conflicts.push_back(c);
332 return;
333 }
334
335 dir_t p = downcast_to_dir_t(result.roster.get_node(parent));
336
337 // name conflict:
338 // see the comment in roster_merge.hh for the analysis showing that at
339 // most two nodes can participate in a rename target conflict. this code
340 // exploits that; after this code runs, there will be no node at the given
341 // location in the tree, which means that in principle, if there were a
342 // third node that _also_ wanted to go here, when we got around to
343 // attaching it we'd have no way to realize it should be a conflict. but
344 // that never happens, so we don't have to keep a lookaside set of
345 // "poisoned locations" or anything.
346 if (p->has_child(name))
347 {
348 rename_target_conflict c;
349 c.nid1 = nid;
350 c.nid2 = p->get_child(name)->self;
351 c.parent_name = make_pair(parent, name);
352 p->detach_child(name);
353 result.rename_target_conflicts.push_back(c);
354 return;
355 }
356
357 if (would_make_dir_loop(result.roster, nid, parent))
358 {
359 directory_loop_conflict c;
360 c.nid = nid;
361 c.parent_name = make_pair(parent, name);
362 result.directory_loop_conflicts.push_back(c);
363 return;
364 }
365 }
366 // hey, we actually made it. attach the node!
367 result.roster.attach_node(nid, parent, name);
368 }
369
370 void
371 copy_node_forward(roster_merge_result & result, node_t const & n,
372 node_t const & old_n)
373 {
374 I(n->self == old_n->self);
375 n->attrs = old_n->attrs;
376 if (is_file_t(n))
377 downcast_to_file_t(n)->content = downcast_to_file_t(old_n)->content;
378 assign_name(result, n->self, old_n->parent, old_n->name);
379 }
380
381} // end anonymous namespace
382
383void
384roster_merge(roster_t const & left_parent,
385 marking_map const & left_markings,
386 set<revision_id> const & left_uncommon_ancestors,
387 roster_t const & right_parent,
388 marking_map const & right_markings,
389 set<revision_id> const & right_uncommon_ancestors,
390 roster_merge_result & result)
391{
392 result.clear();
393 MM(left_parent);
394 MM(left_markings);
395 MM(right_parent);
396 MM(right_markings);
397 MM(result);
398
399 // First handle lifecycles, by die-die-die merge -- our result will contain
400 // everything that is alive in both parents, or alive in one and unborn in
401 // the other, exactly.
402 {
403 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
404 while (i.next())
405 {
406 switch (i.state())
407 {
408 case parallel::invalid:
409 I(false);
410
411 case parallel::in_left:
412 insert_if_unborn(i.left_data(),
413 left_markings, left_uncommon_ancestors,
414 result.roster);
415 break;
416
417 case parallel::in_right:
418 insert_if_unborn(i.right_data(),
419 right_markings, right_uncommon_ancestors,
420 result.roster);
421 break;
422
423 case parallel::in_both:
424 create_node_for(i.left_data(), result.roster);
425 break;
426 }
427 }
428 }
429
430 // okay, our roster now contains a bunch of empty, detached nodes. fill
431 // them in one at a time with *-merge.
432 {
433 node_map::const_iterator left_i, right_i;
434 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
435 node_map::const_iterator new_i = result.roster.all_nodes().begin();
436 marking_map::const_iterator left_mi = left_markings.begin();
437 marking_map::const_iterator right_mi = right_markings.begin();
438 while (i.next())
439 {
440 switch (i.state())
441 {
442 case parallel::invalid:
443 I(false);
444
445 case parallel::in_left:
446 {
447 node_t const & left_n = i.left_data();
448 // we skip nodes that aren't in the result roster (were
449 // deleted in the lifecycles step above)
450 if (result.roster.has_node(left_n->self))
451 {
452 copy_node_forward(result, new_i->second, left_n);
453 ++new_i;
454 }
455 ++left_mi;
456 break;
457 }
458
459 case parallel::in_right:
460 {
461 node_t const & right_n = i.right_data();
462 // we skip nodes that aren't in the result roster
463 if (result.roster.has_node(right_n->self))
464 {
465 copy_node_forward(result, new_i->second, right_n);
466 ++new_i;
467 }
468 ++right_mi;
469 break;
470 }
471
472 case parallel::in_both:
473 {
474 I(new_i->first == i.left_key());
475 I(left_mi->first == i.left_key());
476 I(right_mi->first == i.right_key());
477 node_t const & left_n = i.left_data();
478 marking_t const & left_marking = left_mi->second;
479 node_t const & right_n = i.right_data();
480 marking_t const & right_marking = right_mi->second;
481 node_t const & new_n = new_i->second;
482 // merge name
483 {
484 pair<node_id, path_component> new_name;
485 node_name_conflict conflict(new_n->self);
486 if (merge_scalar(make_pair(left_n->parent, left_n->name),
487 left_marking.parent_name,
488 left_uncommon_ancestors,
489 make_pair(right_n->parent, right_n->name),
490 right_marking.parent_name,
491 right_uncommon_ancestors,
492 new_name, conflict))
493 {
494 assign_name(result, new_n->self,
495 new_name.first, new_name.second);
496 }
497 else
498 {
499 // unsuccessful merge; leave node detached and save
500 // conflict object
501 result.node_name_conflicts.push_back(conflict);
502 }
503 }
504 // if a file, merge content
505 if (is_file_t(new_n))
506 {
507 file_content_conflict conflict(new_n->self);
508 if (merge_scalar(downcast_to_file_t(left_n)->content,
509 left_marking.file_content,
510 left_uncommon_ancestors,
511 downcast_to_file_t(right_n)->content,
512 right_marking.file_content,
513 right_uncommon_ancestors,
514 downcast_to_file_t(new_n)->content,
515 conflict))
516 {
517 // successful merge
518 }
519 else
520 {
521 downcast_to_file_t(new_n)->content = file_id();
522 result.file_content_conflicts.push_back(conflict);
523 }
524 }
525 // merge attributes
526 {
527 full_attr_map_t::const_iterator left_ai = left_n->attrs.begin();
528 full_attr_map_t::const_iterator right_ai = right_n->attrs.begin();
529 parallel::iter<full_attr_map_t> attr_i(left_n->attrs,
530 right_n->attrs);
531 while(attr_i.next())
532 {
533 switch (attr_i.state())
534 {
535 case parallel::invalid:
536 I(false);
537 case parallel::in_left:
538 safe_insert(new_n->attrs, attr_i.left_value());
539 break;
540 case parallel::in_right:
541 safe_insert(new_n->attrs, attr_i.right_value());
542 break;
543 case parallel::in_both:
544 pair<bool, attr_value> new_value;
545 node_attr_conflict conflict(new_n->self);
546 conflict.key = attr_i.left_key();
547 I(conflict.key == attr_i.right_key());
548 if (merge_scalar(attr_i.left_data(),
549 safe_get(left_marking.attrs,
550 attr_i.left_key()),
551 left_uncommon_ancestors,
552 attr_i.right_data(),
553 safe_get(right_marking.attrs,
554 attr_i.right_key()),
555 right_uncommon_ancestors,
556 new_value,
557 conflict))
558 {
559 // successful merge
560 safe_insert(new_n->attrs,
561 make_pair(attr_i.left_key(),
562 new_value));
563 }
564 else
565 {
566 // unsuccessful merge
567 // leave out the attr entry entirely, and save the
568 // conflict
569 result.node_attr_conflicts.push_back(conflict);
570 }
571 break;
572 }
573
574 }
575 }
576 }
577 ++left_mi;
578 ++right_mi;
579 ++new_i;
580 break;
581 }
582 }
583 I(left_mi == left_markings.end());
584 I(right_mi == right_markings.end());
585 I(new_i == result.roster.all_nodes().end());
586 }
587
588 // now check for the possible global problems
589 if (!result.roster.has_root())
590 result.missing_root_dir = true;
591 else
592 {
593 // we can't have an illegal _MTN dir unless we have a root node in the
594 // first place...
595 split_path bookkeeping_root_split;
596 bookkeeping_root_split.push_back(the_null_component);
597 bookkeeping_root_split.push_back(bookkeeping_root_component);
598 if (result.roster.has_node(bookkeeping_root_split))
599 {
600 illegal_name_conflict conflict;
601 node_t n = result.roster.get_node(bookkeeping_root_split);
602 conflict.nid = n->self;
603 conflict.parent_name.first = n->parent;
604 conflict.parent_name.second = n->name;
605 I(n->name == bookkeeping_root_component);
606 I(n->self == result.roster.detach_node(bookkeeping_root_split));
607 result.illegal_name_conflicts.push_back(conflict);
608 }
609 }
610}
611
612#ifdef BUILD_UNIT_TESTS
613#include "unit_tests.hh"
614
615// cases for testing:
616//
617// (DONE:)
618//
619// lifecycle, file and dir
620// alive in both
621// alive in one and unborn in other (left vs. right)
622// alive in one and dead in other (left vs. right)
623//
624// mark merge:
625// same in both, same mark
626// same in both, diff marks
627// different, left wins with 1 mark
628// different, right wins with 1 mark
629// different, conflict with 1 mark
630// different, left wins with 2 marks
631// different, right wins with 2 marks
632// different, conflict with 1 mark winning, 1 mark losing
633// different, conflict with 2 marks both conflicting
634//
635// for:
636// node name and parent, file and dir
637// node attr, file and dir
638// file content
639//
640// attr lifecycle:
641// seen in both -->mark merge cases, above
642// live in one and unseen in other -->live
643// dead in one and unseen in other -->dead
644//
645// two diff nodes with same name
646// directory loops
647// orphans
648// illegal node ("_MTN")
649// missing root dir
650//
651// (NEEDED:)
652//
653// interactions:
654// in-node name conflict prevents other problems:
655// in-node name conflict + possible between-node name conflict
656// a vs. b, plus a, b, exist in result
657// left: 1: a
658// 2: b
659// right: 1: b
660// 3: a
661// in-node name conflict + both possible names orphaned
662// a/foo vs. b/foo conflict, + a, b exist in parents but deleted in
663// children
664// left: 1: a
665// 2: a/foo
666// right:
667// 3: b
668// 2: b/foo
669// in-node name conflict + directory loop conflict
670// a/bottom vs. b/bottom, with a and b both moved inside it
671// in-node name conflict + one name illegal
672// _MTN vs. foo
673// in-node name conflict causes other problems:
674// in-node name conflict + causes missing root dir
675// "" vs. foo and bar vs. ""
676// between-node name conflict prevents other problems:
677// between-node name conflict + both nodes orphaned
678// this is not possible
679// between-node name conflict + both nodes cause loop
680// this is not possible
681// between-node name conflict + both nodes illegal
682// two nodes that both merge to _MTN
683// this is not possible
684// between-node name conflict causes other problems:
685// between-node name conflict + causes missing root dir
686// two nodes that both want ""
687
688split_path
689split(string const & s)
690{
691 split_path sp;
692 file_path_internal(s).split(sp);
693 return sp;
694}
695
696typedef enum { scalar_a, scalar_b, scalar_conflict } scalar_val;
697
698template <> void
699dump(scalar_val const & v, string & out)
700{
701 switch (v)
702 {
703 case scalar_a:
704 out = "scalar_a";
705 break;
706 case scalar_b:
707 out = "scalar_b";
708 break;
709 case scalar_conflict:
710 out = "scalar_conflict";
711 break;
712 }
713}
714
715void string_to_set(string const & from, set<revision_id> & to)
716{
717 to.clear();
718 for (string::const_iterator i = from.begin(); i != from.end(); ++i)
719 {
720 string rid_str(40, *i);
721 to.insert(revision_id(rid_str));
722 }
723}
724
725
726template <typename S> void
727test_a_scalar_merge_impl(scalar_val left_val, string const & left_marks_str,
728 string const & left_uncommon_str,
729 scalar_val right_val, string const & right_marks_str,
730 string const & right_uncommon_str,
731 scalar_val expected_outcome)
732{
733 MM(left_val);
734 MM(left_marks_str);
735 MM(left_uncommon_str);
736 MM(right_val);
737 MM(right_marks_str);
738 MM(right_uncommon_str);
739 MM(expected_outcome);
740
741 S scalar;
742 roster_t left_parent, right_parent;
743 marking_map left_markings, right_markings;
744 set<revision_id> left_uncommon_ancestors, right_uncommon_ancestors;
745 roster_merge_result result;
746
747 set<revision_id> left_marks, right_marks;
748
749 MM(left_parent);
750 MM(right_parent);
751 MM(left_markings);
752 MM(right_markings);
753 MM(left_uncommon_ancestors);
754 MM(right_uncommon_ancestors);
755 MM(left_marks);
756 MM(right_marks);
757 MM(result);
758
759 string_to_set(left_marks_str, left_marks);
760 scalar.setup_parent(left_val, left_marks, left_parent, left_markings);
761 string_to_set(right_marks_str, right_marks);
762 scalar.setup_parent(right_val, right_marks, right_parent, right_markings);
763
764 string_to_set(left_uncommon_str, left_uncommon_ancestors);
765 string_to_set(right_uncommon_str, right_uncommon_ancestors);
766
767 roster_merge(left_parent, left_markings, left_uncommon_ancestors,
768 right_parent, right_markings, right_uncommon_ancestors,
769 result);
770
771 scalar.check_result(left_val, right_val, result, expected_outcome);
772}
773
774static const revision_id root_rid = revision_id(string("0000000000000000000000000000000000000000"));
775static const file_id arbitrary_file = file_id(string("0000000000000000000000000000000000000000"));
776
777struct base_scalar
778{
779 testing_node_id_source nis;
780 node_id root_nid;
781 node_id thing_nid;
782 base_scalar() : root_nid(nis.next()), thing_nid(nis.next())
783 {}
784
785 void
786 make_dir(string const & name, node_id nid, roster_t & r, marking_map & markings)
787 {
788 r.create_dir_node(nid);
789 r.attach_node(nid, split(name));
790 marking_t marking;
791 marking.birth_revision = root_rid;
792 marking.parent_name.insert(root_rid);
793 safe_insert(markings, make_pair(nid, marking));
794 }
795
796 void
797 make_file(string const & name, node_id nid, roster_t & r, marking_map & markings)
798 {
799 r.create_file_node(arbitrary_file, nid);
800 r.attach_node(nid, split(name));
801 marking_t marking;
802 marking.birth_revision = root_rid;
803 marking.parent_name.insert(root_rid);
804 marking.file_content.insert(root_rid);
805 safe_insert(markings, make_pair(nid, marking));
806 }
807
808 void
809 make_root(roster_t & r, marking_map & markings)
810 {
811 make_dir("", root_nid, r, markings);
812 }
813};
814
815struct file_scalar : public virtual base_scalar
816{
817 split_path thing_name;
818 file_scalar() : thing_name(split("thing"))
819 {}
820
821 void
822 make_thing(roster_t & r, marking_map & markings)
823 {
824 make_root(r, markings);
825 make_file("thing", thing_nid, r, markings);
826 }
827};
828
829struct dir_scalar : public virtual base_scalar
830{
831 split_path thing_name;
832 dir_scalar() : thing_name(split("thing"))
833 {}
834
835 void
836 make_thing(roster_t & r, marking_map & markings)
837 {
838 make_root(r, markings);
839 make_dir("thing", thing_nid, r, markings);
840 }
841};
842
843struct name_shared_stuff : public virtual base_scalar
844{
845 virtual split_path path_for(scalar_val val) = 0;
846 path_component pc_for(scalar_val val)
847 {
848 split_path sp = path_for(val);
849 return idx(sp, sp.size() - 1);
850 }
851 virtual node_id parent_for(scalar_val val) = 0;
852
853 void
854 check_result(scalar_val left_val, scalar_val right_val,
855 // NB result is writeable -- we can scribble on it
856 roster_merge_result & result, scalar_val expected_val)
857 {
858 split_path name;
859 switch (expected_val)
860 {
861 case scalar_a: case scalar_b:
862 result.roster.get_name(thing_nid, name);
863 I(name == path_for(expected_val));
864 break;
865 case scalar_conflict:
866 node_name_conflict const & c = idx(result.node_name_conflicts, 0);
867 I(c.nid == thing_nid);
868 I(c.left == make_pair(parent_for(left_val), pc_for(left_val)));
869 I(c.right == make_pair(parent_for(right_val), pc_for(right_val)));
870 I(null_node(result.roster.get_node(thing_nid)->parent));
871 I(null_name(result.roster.get_node(thing_nid)->name));
872 // resolve the conflict, thus making sure that resolution works and
873 // that this was the only conflict signaled
874 // attach implicitly checks that we were already detached
875 result.roster.attach_node(thing_nid, split("thing"));
876 result.node_name_conflicts.pop_back();
877 break;
878 }
879 // by now, the merge should have been resolved cleanly, one way or another
880 result.roster.check_sane();
881 I(result.is_clean());
882 }
883
884 virtual ~name_shared_stuff() {};
885};
886
887template <typename T>
888struct basename_scalar : public name_shared_stuff, public T
889{
890 virtual split_path path_for(scalar_val val)
891 {
892 I(val != scalar_conflict);
893 return split((val == scalar_a) ? "a" : "b");
894 }
895 virtual node_id parent_for(scalar_val val)
896 {
897 I(val != scalar_conflict);
898 return root_nid;
899 }
900
901 void
902 setup_parent(scalar_val val, set<revision_id> marks,
903 roster_t & r, marking_map & markings)
904 {
905 this->T::make_thing(r, markings);
906 r.detach_node(this->T::thing_name);
907 r.attach_node(thing_nid, path_for(val));
908 markings.find(thing_nid)->second.parent_name = marks;
909 }
910
911 virtual ~basename_scalar() {}
912};
913
914template <typename T>
915struct parent_scalar : public virtual name_shared_stuff, public T
916{
917 node_id a_dir_nid, b_dir_nid;
918 parent_scalar() : a_dir_nid(nis.next()), b_dir_nid(nis.next())
919 {}
920
921 virtual split_path path_for(scalar_val val)
922 {
923 I(val != scalar_conflict);
924 return split((val == scalar_a) ? "a/thing" : "b/thing");
925 }
926 virtual node_id parent_for(scalar_val val)
927 {
928 I(val != scalar_conflict);
929 return ((val == scalar_a) ? a_dir_nid : b_dir_nid);
930 }
931
932 void
933 setup_parent(scalar_val val, set<revision_id> marks,
934 roster_t & r, marking_map & markings)
935 {
936 this->T::make_thing(r, markings);
937 make_dir("a", a_dir_nid, r, markings);
938 make_dir("b", b_dir_nid, r, markings);
939 r.detach_node(this->T::thing_name);
940 r.attach_node(thing_nid, path_for(val));
941 markings.find(thing_nid)->second.parent_name = marks;
942 }
943
944 virtual ~parent_scalar() {}
945};
946
947template <typename T>
948struct attr_scalar : public virtual base_scalar, public T
949{
950 attr_value attr_value_for(scalar_val val)
951 {
952 I(val != scalar_conflict);
953 return attr_value((val == scalar_a) ? "a" : "b");
954 }
955
956 void
957 setup_parent(scalar_val val, set<revision_id> marks,
958 roster_t & r, marking_map & markings)
959 {
960 this->T::make_thing(r, markings);
961 r.set_attr(this->T::thing_name, attr_key("test_key"), attr_value_for(val));
962 markings.find(thing_nid)->second.attrs[attr_key("test_key")] = marks;
963 }
964
965 void
966 check_result(scalar_val left_val, scalar_val right_val,
967 // NB result is writeable -- we can scribble on it
968 roster_merge_result & result, scalar_val expected_val)
969 {
970 split_path name;
971 switch (expected_val)
972 {
973 case scalar_a: case scalar_b:
974 I(result.roster.get_node(thing_nid)->attrs[attr_key("test_key")]
975 == make_pair(true, attr_value_for(expected_val)));
976 break;
977 case scalar_conflict:
978 node_attr_conflict const & c = idx(result.node_attr_conflicts, 0);
979 I(c.nid == thing_nid);
980 I(c.key == attr_key("test_key"));
981 I(c.left == make_pair(true, attr_value_for(left_val)));
982 I(c.right == make_pair(true, attr_value_for(right_val)));
983 full_attr_map_t const & attrs = result.roster.get_node(thing_nid)->attrs;
984 I(attrs.find(attr_key("test_key")) == attrs.end());
985 // resolve the conflict, thus making sure that resolution works and
986 // that this was the only conflict signaled
987 result.roster.set_attr(this->T::thing_name, attr_key("test_key"),
988 attr_value("conflict -- RESOLVED"));
989 result.node_attr_conflicts.pop_back();
990 break;
991 }
992 // by now, the merge should have been resolved cleanly, one way or another
993 result.roster.check_sane();
994 I(result.is_clean());
995 }
996};
997
998struct file_content_scalar : public virtual file_scalar
999{
1000 file_id content_for(scalar_val val)
1001 {
1002 I(val != scalar_conflict);
1003 return file_id(string((val == scalar_a)
1004 ? "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1005 : "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1006 }
1007
1008 void
1009 setup_parent(scalar_val val, set<revision_id> marks,
1010 roster_t & r, marking_map & markings)
1011 {
1012 make_thing(r, markings);
1013 downcast_to_file_t(r.get_node(thing_name))->content = content_for(val);
1014 markings.find(thing_nid)->second.file_content = marks;
1015 }
1016
1017 void
1018 check_result(scalar_val left_val, scalar_val right_val,
1019 // NB result is writeable -- we can scribble on it
1020 roster_merge_result & result, scalar_val expected_val)
1021 {
1022 split_path name;
1023 switch (expected_val)
1024 {
1025 case scalar_a: case scalar_b:
1026 I(downcast_to_file_t(result.roster.get_node(thing_nid))->content
1027 == content_for(expected_val));
1028 break;
1029 case scalar_conflict:
1030 file_content_conflict const & c = idx(result.file_content_conflicts, 0);
1031 I(c.nid == thing_nid);
1032 I(c.left == content_for(left_val));
1033 I(c.right == content_for(right_val));
1034 file_id & content = downcast_to_file_t(result.roster.get_node(thing_nid))->content;
1035 I(null_id(content));
1036 // resolve the conflict, thus making sure that resolution works and
1037 // that this was the only conflict signaled
1038 content = file_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1039 result.file_content_conflicts.pop_back();
1040 break;
1041 }
1042 // by now, the merge should have been resolved cleanly, one way or another
1043 result.roster.check_sane();
1044 I(result.is_clean());
1045 }
1046};
1047
1048void
1049test_a_scalar_merge(scalar_val left_val, string const & left_marks_str,
1050 string const & left_uncommon_str,
1051 scalar_val right_val, string const & right_marks_str,
1052 string const & right_uncommon_str,
1053 scalar_val expected_outcome)
1054{
1055 test_a_scalar_merge_impl<basename_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1056 right_val, right_marks_str, right_uncommon_str,
1057 expected_outcome);
1058 test_a_scalar_merge_impl<basename_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1059 right_val, right_marks_str, right_uncommon_str,
1060 expected_outcome);
1061 test_a_scalar_merge_impl<parent_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1062 right_val, right_marks_str, right_uncommon_str,
1063 expected_outcome);
1064 test_a_scalar_merge_impl<parent_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1065 right_val, right_marks_str, right_uncommon_str,
1066 expected_outcome);
1067 test_a_scalar_merge_impl<attr_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1068 right_val, right_marks_str, right_uncommon_str,
1069 expected_outcome);
1070 test_a_scalar_merge_impl<attr_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1071 right_val, right_marks_str, right_uncommon_str,
1072 expected_outcome);
1073 test_a_scalar_merge_impl<file_content_scalar>(left_val, left_marks_str, left_uncommon_str,
1074 right_val, right_marks_str, right_uncommon_str,
1075 expected_outcome);
1076}
1077
1078
1079void
1080test_scalar_merges()
1081{
1082 // Notation: a1* means, "value is a, this is node 1 in the graph, it is
1083 // marked". ".2" means, "value is unimportant and different from either a
1084 // or b, this is node 2 in the graph, it is not marked".
1085 //
1086 // Backslashes with dots after them mean, the C++ line continuation rules
1087 // are annoying when it comes to drawing ascii graphs -- the dot is only to
1088 // stop the backslash from having special meaning to the parser. So just
1089 // ignore them :-).
1090
1091 // same in both, same mark
1092 // a1*
1093 // / \.
1094 // a2 a3
1095 test_a_scalar_merge(scalar_a, "1", "2", scalar_a, "1", "3", scalar_a);
1096
1097 // same in both, diff marks
1098 // .1*
1099 // / \.
1100 // a2* a3*
1101 test_a_scalar_merge(scalar_a, "2", "2", scalar_a, "3", "3", scalar_a);
1102
1103 // different, left wins with 1 mark
1104 // a1*
1105 // / \.
1106 // b2* a3
1107 test_a_scalar_merge(scalar_b, "2", "2", scalar_a, "1", "3", scalar_b);
1108
1109 // different, right wins with 1 mark
1110 // a1*
1111 // / \.
1112 // a2 b3*
1113 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "3", "3", scalar_b);
1114
1115 // different, conflict with 1 mark
1116 // .1*
1117 // / \.
1118 // a2* b3*
1119 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "3", "3", scalar_conflict);
1120
1121 // different, left wins with 2 marks
1122 // a1*
1123 // / \.
1124 // a2 a3
1125 // / \.
1126 // b4* b5*
1127 // \ /
1128 // b6
1129 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "1", "3", scalar_b);
1130
1131 // different, right wins with 2 marks
1132 // a1*
1133 // / \.
1134 // a2 a3
1135 // / \.
1136 // b4* b5*
1137 // \ /
1138 // b6
1139 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "45", "3456", scalar_b);
1140
1141 // different, conflict with 1 mark winning, 1 mark losing
1142 // .1*
1143 // / \.
1144 // a2* a3*
1145 // \ / \.
1146 // a4 b5*
1147 test_a_scalar_merge(scalar_a, "23", "24", scalar_b, "5", "5", scalar_conflict);
1148
1149 //
1150 // .1*
1151 // / \.
1152 // a2* a3*
1153 // / \ /
1154 // b4* a5
1155 test_a_scalar_merge(scalar_b, "4", "4", scalar_a, "23", "35", scalar_conflict);
1156
1157 // different, conflict with 2 marks both conflicting
1158 //
1159 // .1*
1160 // / \.
1161 // .2 a3*
1162 // / \.
1163 // b4* b5*
1164 // \ /
1165 // b6
1166 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "3", "3", scalar_conflict);
1167
1168 //
1169 // .1*
1170 // / \.
1171 // a2* .3
1172 // / \.
1173 // b4* b5*
1174 // \ /
1175 // b6
1176 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "45", "3456", scalar_conflict);
1177
1178 //
1179 // _.1*_
1180 // / \.
1181 // .2 .3
1182 // / \ / \.
1183 // a4* a5* b6* b7*
1184 // \ / \ /
1185 // a8 b9
1186 test_a_scalar_merge(scalar_a, "45", "2458", scalar_b, "67", "3679", scalar_conflict);
1187}
1188
1189namespace
1190{
1191 const revision_id a_uncommon1 = revision_id(string("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
1192 const revision_id a_uncommon2 = revision_id(string("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1193 const revision_id b_uncommon1 = revision_id(string("cccccccccccccccccccccccccccccccccccccccc"));
1194 const revision_id b_uncommon2 = revision_id(string("dddddddddddddddddddddddddddddddddddddddd"));
1195 const revision_id common1 = revision_id(string("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"));
1196 const revision_id common2 = revision_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1197
1198 const file_id fid1 = file_id(string("1111111111111111111111111111111111111111"));
1199 const file_id fid2 = file_id(string("2222222222222222222222222222222222222222"));
1200
1201}
1202
1203static void
1204make_dir(roster_t & r, marking_map & markings,
1205 revision_id const & birth_rid, revision_id const & parent_name_rid,
1206 string const & name, node_id nid)
1207{
1208 r.create_dir_node(nid);
1209 r.attach_node(nid, split(name));
1210 marking_t marking;
1211 marking.birth_revision = birth_rid;
1212 marking.parent_name.insert(parent_name_rid);
1213 safe_insert(markings, make_pair(nid, marking));
1214}
1215
1216static void
1217make_file(roster_t & r, marking_map & markings,
1218 revision_id const & birth_rid, revision_id const & parent_name_rid,
1219 revision_id const & file_content_rid,
1220 string const & name, file_id const & content,
1221 node_id nid)
1222{
1223 r.create_file_node(content, nid);
1224 r.attach_node(nid, split(name));
1225 marking_t marking;
1226 marking.birth_revision = birth_rid;
1227 marking.parent_name.insert(parent_name_rid);
1228 marking.file_content.insert(file_content_rid);
1229 safe_insert(markings, make_pair(nid, marking));
1230}
1231
1232static void
1233make_node_lifecycle_objs(roster_t & r, marking_map & markings, revision_id const & uncommon,
1234 string const & name, node_id common_dir_nid, node_id common_file_nid,
1235 node_id & safe_dir_nid, node_id & safe_file_nid, node_id_source & nis)
1236{
1237 make_dir(r, markings, common1, common1, "common_old_dir", common_dir_nid);
1238 make_file(r, markings, common1, common1, common1, "common_old_file", fid1, common_file_nid);
1239 safe_dir_nid = nis.next();
1240 make_dir(r, markings, uncommon, uncommon, name + "_safe_dir", safe_dir_nid);
1241 safe_file_nid = nis.next();
1242 make_file(r, markings, uncommon, uncommon, uncommon, name + "_safe_file", fid1, safe_file_nid);
1243 make_dir(r, markings, common1, common1, name + "_dead_dir", nis.next());
1244 make_file(r, markings, common1, common1, common1, name + "_dead_file", fid1, nis.next());
1245}
1246
1247
1248static void
1249test_roster_merge_node_lifecycle()
1250{
1251 roster_t a_roster, b_roster;
1252 marking_map a_markings, b_markings;
1253 set<revision_id> a_uncommon, b_uncommon;
1254 // boilerplate to get uncommon revision sets...
1255 a_uncommon.insert(a_uncommon1);
1256 a_uncommon.insert(a_uncommon2);
1257 b_uncommon.insert(b_uncommon1);
1258 b_uncommon.insert(b_uncommon2);
1259 testing_node_id_source nis;
1260 // boilerplate to set up a root node...
1261 {
1262 node_id root_nid = nis.next();
1263 make_dir(a_roster, a_markings, common1, common1, "", root_nid);
1264 make_dir(b_roster, b_markings, common1, common1, "", root_nid);
1265 }
1266 // create some nodes on each side
1267 node_id common_dir_nid = nis.next();
1268 node_id common_file_nid = nis.next();
1269 node_id a_safe_dir_nid, a_safe_file_nid, b_safe_dir_nid, b_safe_file_nid;
1270 make_node_lifecycle_objs(a_roster, a_markings, a_uncommon1, "a", common_dir_nid, common_file_nid,
1271 a_safe_dir_nid, a_safe_file_nid, nis);
1272 make_node_lifecycle_objs(b_roster, b_markings, b_uncommon1, "b", common_dir_nid, common_file_nid,
1273 b_safe_dir_nid, b_safe_file_nid, nis);
1274 // do the merge
1275 roster_merge_result result;
1276 roster_merge(a_roster, a_markings, a_uncommon, b_roster, b_markings, b_uncommon, result);
1277 I(result.is_clean());
1278 // 7 = 1 root + 2 common + 2 safe a + 2 safe b
1279 I(result.roster.all_nodes().size() == 7);
1280 // check that they're the right ones...
1281 I(shallow_equal(result.roster.get_node(common_dir_nid),
1282 a_roster.get_node(common_dir_nid), false));
1283 I(shallow_equal(result.roster.get_node(common_file_nid),
1284 a_roster.get_node(common_file_nid), false));
1285 I(shallow_equal(result.roster.get_node(common_dir_nid),
1286 b_roster.get_node(common_dir_nid), false));
1287 I(shallow_equal(result.roster.get_node(common_file_nid),
1288 b_roster.get_node(common_file_nid), false));
1289 I(shallow_equal(result.roster.get_node(a_safe_dir_nid),
1290 a_roster.get_node(a_safe_dir_nid), false));
1291 I(shallow_equal(result.roster.get_node(a_safe_file_nid),
1292 a_roster.get_node(a_safe_file_nid), false));
1293 I(shallow_equal(result.roster.get_node(b_safe_dir_nid),
1294 b_roster.get_node(b_safe_dir_nid), false));
1295 I(shallow_equal(result.roster.get_node(b_safe_file_nid),
1296 b_roster.get_node(b_safe_file_nid), false));
1297}
1298
1299static void
1300test_roster_merge_attr_lifecycle()
1301{
1302 roster_t left_roster, right_roster;
1303 marking_map left_markings, right_markings;
1304 MM(left_roster);
1305 MM(left_markings);
1306 MM(right_roster);
1307 MM(right_markings);
1308 set<revision_id> old_revs, left_revs, right_revs;
1309 string_to_set("0", old_revs);
1310 string_to_set("1", left_revs);
1311 string_to_set("2", right_revs);
1312 revision_id old_rid = *old_revs.begin();
1313 testing_node_id_source nis;
1314 node_id dir_nid = nis.next();
1315 make_dir(left_roster, left_markings, old_rid, old_rid, "", dir_nid);
1316 make_dir(right_roster, right_markings, old_rid, old_rid, "", dir_nid);
1317 node_id file_nid = nis.next();
1318 make_file(left_roster, left_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1319 make_file(right_roster, right_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1320
1321 // put one live and one dead attr on each thing on each side, with uncommon
1322 // marks on them
1323 safe_insert(left_roster.get_node(dir_nid)->attrs,
1324 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1325 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1326 safe_insert(left_roster.get_node(dir_nid)->attrs,
1327 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1328 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1329 safe_insert(left_roster.get_node(file_nid)->attrs,
1330 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1331 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1332 safe_insert(left_roster.get_node(file_nid)->attrs,
1333 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1334 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1335
1336 safe_insert(right_roster.get_node(dir_nid)->attrs,
1337 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
1338 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_live"), right_revs));
1339 safe_insert(right_roster.get_node(dir_nid)->attrs,
1340 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
1341 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
1342 safe_insert(right_roster.get_node(file_nid)->attrs,
1343 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
1344 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_live"), right_revs));
1345 safe_insert(right_roster.get_node(file_nid)->attrs,
1346 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
1347 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
1348
1349 roster_merge_result result;
1350 MM(result);
1351 roster_merge(left_roster, left_markings, left_revs,
1352 right_roster, right_markings, right_revs,
1353 result);
1354 I(result.roster.all_nodes().size() == 2);
1355 I(result.roster.get_node(dir_nid)->attrs.size() == 4);
1356 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
1357 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1358 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
1359 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1360 I(result.roster.get_node(file_nid)->attrs.size() == 4);
1361 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
1362 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1363 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
1364 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1365}
1366
1367struct structural_conflict_helper
1368{
1369 roster_t left_roster, right_roster;
1370 marking_map left_markings, right_markings;
1371 set<revision_id> old_revs, left_revs, right_revs;
1372 revision_id old_rid, left_rid, right_rid;
1373 testing_node_id_source nis;
1374 node_id root_nid;
1375 roster_merge_result result;
1376
1377 virtual void setup() = 0;
1378 virtual void check() = 0;
1379
1380 void test()
1381 {
1382 MM(left_roster);
1383 MM(left_markings);
1384 MM(right_roster);
1385 MM(right_markings);
1386 string_to_set("0", old_revs);
1387 string_to_set("1", left_revs);
1388 string_to_set("2", right_revs);
1389 old_rid = *old_revs.begin();
1390 left_rid = *left_revs.begin();
1391 right_rid = *right_revs.begin();
1392 root_nid = nis.next();
1393 make_dir(left_roster, left_markings, old_rid, old_rid, "", root_nid);
1394 make_dir(right_roster, right_markings, old_rid, old_rid, "", root_nid);
1395
1396 setup();
1397
1398 MM(result);
1399 roster_merge(left_roster, left_markings, left_revs,
1400 right_roster, right_markings, right_revs,
1401 result);
1402
1403 check();
1404 }
1405
1406 virtual ~structural_conflict_helper() {}
1407};
1408
1409// two diff nodes with same name
1410struct simple_rename_target_conflict : public structural_conflict_helper
1411{
1412 node_id left_nid, right_nid;
1413 virtual void setup()
1414 {
1415 left_nid = nis.next();
1416 make_dir(left_roster, left_markings, left_rid, left_rid, "thing", left_nid);
1417 right_nid = nis.next();
1418 make_dir(right_roster, right_markings, right_rid, right_rid, "thing", right_nid);
1419 }
1420
1421 virtual void check()
1422 {
1423 I(!result.is_clean());
1424 rename_target_conflict const & c = idx(result.rename_target_conflicts, 0);
1425 I((c.nid1 == left_nid && c.nid2 == right_nid)
1426 || (c.nid1 == right_nid && c.nid2 == left_nid));
1427 I(c.parent_name == make_pair(root_nid, idx(split("thing"), 1)));
1428 // this tests that they were detached, implicitly
1429 result.roster.attach_node(left_nid, split("left"));
1430 result.roster.attach_node(right_nid, split("right"));
1431 result.rename_target_conflicts.pop_back();
1432 I(result.is_clean());
1433 result.roster.check_sane();
1434 }
1435};
1436
1437// directory loops
1438struct simple_dir_loop_conflict : public structural_conflict_helper
1439{
1440 node_id left_top_nid, right_top_nid;
1441
1442 virtual void setup()
1443 {
1444 left_top_nid = nis.next();
1445 right_top_nid = nis.next();
1446
1447 make_dir(left_roster, left_markings, old_rid, old_rid, "top", left_top_nid);
1448 make_dir(left_roster, left_markings, old_rid, left_rid, "top/bottom", right_top_nid);
1449
1450 make_dir(right_roster, right_markings, old_rid, old_rid, "top", right_top_nid);
1451 make_dir(right_roster, right_markings, old_rid, right_rid, "top/bottom", left_top_nid);
1452 }
1453
1454 virtual void check()
1455 {
1456 I(!result.is_clean());
1457 directory_loop_conflict const & c = idx(result.directory_loop_conflicts, 0);
1458 I((c.nid == left_top_nid && c.parent_name == make_pair(right_top_nid, idx(split("bottom"), 1)))
1459 || (c.nid == right_top_nid && c.parent_name == make_pair(left_top_nid, idx(split("bottom"), 1))));
1460 // this tests it was detached, implicitly
1461 result.roster.attach_node(c.nid, split("resolved"));
1462 result.directory_loop_conflicts.pop_back();
1463 I(result.is_clean());
1464 result.roster.check_sane();
1465 }
1466};
1467
1468// orphans
1469struct simple_orphan_conflict : public structural_conflict_helper
1470{
1471 node_id a_dead_parent_nid, a_live_child_nid, b_dead_parent_nid, b_live_child_nid;
1472
1473 // in ancestor, both parents are alive
1474 // in left, a_dead_parent is dead, and b_live_child is created
1475 // in right, b_dead_parent is dead, and a_live_child is created
1476
1477 virtual void setup()
1478 {
1479 a_dead_parent_nid = nis.next();
1480 a_live_child_nid = nis.next();
1481 b_dead_parent_nid = nis.next();
1482 b_live_child_nid = nis.next();
1483
1484 make_dir(left_roster, left_markings, old_rid, old_rid, "b_parent", b_dead_parent_nid);
1485 make_dir(left_roster, left_markings, left_rid, left_rid, "b_parent/b_child", b_live_child_nid);
1486
1487 make_dir(right_roster, right_markings, old_rid, old_rid, "a_parent", a_dead_parent_nid);
1488 make_dir(right_roster, right_markings, right_rid, right_rid, "a_parent/a_child", a_live_child_nid);
1489 }
1490
1491 virtual void check()
1492 {
1493 I(!result.is_clean());
1494 I(result.orphaned_node_conflicts.size() == 2);
1495 orphaned_node_conflict a, b;
1496 if (idx(result.orphaned_node_conflicts, 0).nid == a_live_child_nid)
1497 {
1498 a = idx(result.orphaned_node_conflicts, 0);
1499 b = idx(result.orphaned_node_conflicts, 1);
1500 }
1501 else
1502 {
1503 a = idx(result.orphaned_node_conflicts, 1);
1504 b = idx(result.orphaned_node_conflicts, 0);
1505 }
1506 I(a.nid == a_live_child_nid);
1507 I(a.parent_name == make_pair(a_dead_parent_nid, idx(split("a_child"), 1)));
1508 I(b.nid == b_live_child_nid);
1509 I(b.parent_name == make_pair(b_dead_parent_nid, idx(split("b_child"), 1)));
1510 // this tests it was detached, implicitly
1511 result.roster.attach_node(a.nid, split("resolved_a"));
1512 result.roster.attach_node(b.nid, split("resolved_b"));
1513 result.orphaned_node_conflicts.pop_back();
1514 result.orphaned_node_conflicts.pop_back();
1515 I(result.is_clean());
1516 result.roster.check_sane();
1517 }
1518};
1519
1520// illegal node ("_MTN")
1521struct simple_illegal_name_conflict : public structural_conflict_helper
1522{
1523 node_id new_root_nid, bad_dir_nid;
1524
1525 // in left, new_root is the root (it existed in old, but was renamed in left)
1526 // in right, new_root is still a subdir, the old root still exists, and a
1527 // new dir has been created
1528
1529 virtual void setup()
1530 {
1531 new_root_nid = nis.next();
1532 bad_dir_nid = nis.next();
1533
1534 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1535 safe_erase(left_markings, root_nid);
1536 make_dir(left_roster, left_markings, old_rid, left_rid, "", new_root_nid);
1537
1538 make_dir(right_roster, right_markings, old_rid, old_rid, "root_to_be", new_root_nid);
1539 make_dir(right_roster, right_markings, right_rid, right_rid, "root_to_be/_MTN", bad_dir_nid);
1540 }
1541
1542 virtual void check()
1543 {
1544 I(!result.is_clean());
1545 illegal_name_conflict const & c = idx(result.illegal_name_conflicts, 0);
1546 I(c.nid == bad_dir_nid);
1547 I(c.parent_name == make_pair(new_root_nid, bookkeeping_root_component));
1548 // this tests it was detached, implicitly
1549 result.roster.attach_node(bad_dir_nid, split("dir_formerly_known_as__MTN"));
1550 result.illegal_name_conflicts.pop_back();
1551 I(result.is_clean());
1552 result.roster.check_sane();
1553 }
1554};
1555
1556// missing root dir
1557struct simple_missing_root_dir : public structural_conflict_helper
1558{
1559 node_id other_root_nid;
1560
1561 // left and right each have different root nodes, and each has deleted the
1562 // other's root node
1563
1564 virtual void setup()
1565 {
1566 other_root_nid = nis.next();
1567
1568 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1569 safe_erase(left_markings, root_nid);
1570 make_dir(left_roster, left_markings, old_rid, old_rid, "", other_root_nid);
1571 }
1572
1573 virtual void check()
1574 {
1575 I(!result.is_clean());
1576 I(result.missing_root_dir);
1577 result.roster.attach_node(result.roster.create_dir_node(nis), split(""));
1578 result.missing_root_dir = false;
1579 I(result.is_clean());
1580 result.roster.check_sane();
1581 }
1582};
1583
1584
1585static void
1586test_simple_structural_conflicts()
1587{
1588 {
1589 simple_rename_target_conflict t;
1590 t.test();
1591 }
1592 {
1593 simple_dir_loop_conflict t;
1594 t.test();
1595 }
1596 {
1597 simple_orphan_conflict t;
1598 t.test();
1599 }
1600 {
1601 simple_illegal_name_conflict t;
1602 t.test();
1603 }
1604 {
1605 simple_missing_root_dir t;
1606 t.test();
1607 }
1608}
1609
1610struct node_name_plus_helper : public structural_conflict_helper
1611{
1612 node_id name_conflict_nid;
1613 node_id left_parent, right_parent;
1614 path_component left_name, right_name;
1615 void make_nn_conflict(string const & left_path, string const & right_path)
1616 {
1617 name_conflict_nid = nis.next();
1618 make_dir(left_roster, left_markings, old_rid, left_rid, left_path, name_conflict_nid);
1619 left_parent = left_roster.get_node(split(left_path))->parent;
1620 left_name = left_roster.get_node(split(left_path))->name;
1621 make_dir(right_roster, right_markings, old_rid, right_rid, right_path, name_conflict_nid);
1622 right_parent = right_roster.get_node(split(right_path))->parent;
1623 right_name = right_roster.get_node(split(right_path))->name;
1624 }
1625 void check_nn_conflict()
1626 {
1627 I(!result.is_clean());
1628 node_name_conflict const & c = idx(result.node_name_conflicts, 0);
1629 I(c.nid == name_conflict_nid);
1630 I(c.left == make_pair(left_parent, left_name));
1631 I(c.right == make_pair(right_parent, right_name));
1632 result.roster.attach_node(name_conflict_nid, split("totally_other_name"));
1633 result.node_name_conflicts.pop_back();
1634 I(result.is_clean());
1635 result.roster.check_sane();
1636 }
1637};
1638
1639struct node_name_plus_rename_target : public node_name_plus_helper
1640{
1641 node_id a_nid, b_nid;
1642
1643 virtual void setup()
1644 {
1645 a_nid = nis.next();
1646 b_nid = nis.next();
1647 make_nn_conflict("a", "b");
1648 make_dir(left_roster, left_markings, left_rid, left_rid, "b", b_nid);
1649 make_dir(right_roster, right_markings, right_rid, right_rid, "a", a_nid);
1650 }
1651
1652 virtual void check()
1653 {
1654 // there should just be a single conflict on name_conflict_nid, and a and
1655 // b should have landed fine
1656 I(result.roster.get_node(split("a"))->self == a_nid);
1657 I(result.roster.get_node(split("b"))->self == b_nid);
1658 check_nn_conflict();
1659 }
1660};
1661
1662struct node_name_plus_orphan : public node_name_plus_helper
1663{
1664 node_id a_nid, b_nid;
1665
1666 virtual void setup()
1667 {
1668 a_nid = nis.next();
1669 b_nid = nis.next();
1670 make_dir(left_roster, left_markings, old_rid, left_rid, "a", a_nid);
1671 make_dir(right_roster, right_markings, old_rid, right_rid, "b", b_nid);
1672 make_nn_conflict("a/foo", "b/foo");
1673 }
1674
1675 virtual void check()
1676 {
1677 I(result.roster.all_nodes().size() == 2);
1678 check_nn_conflict();
1679 }
1680};
1681
1682struct node_name_plus_directory_loop : public node_name_plus_helper
1683{
1684 node_id a_nid, b_nid;
1685
1686 virtual void setup()
1687 {
1688 a_nid = nis.next();
1689 b_nid = nis.next();
1690 make_dir(left_roster, left_markings, old_rid, old_rid, "a", a_nid);
1691 make_dir(right_roster, right_markings, old_rid, old_rid, "b", b_nid);
1692 make_nn_conflict("a/foo", "b/foo");
1693 make_dir(left_roster, left_markings, old_rid, left_rid, "a/foo/b", b_nid);
1694 make_dir(right_roster, right_markings, old_rid, right_rid, "b/foo/a", a_nid);
1695 }
1696
1697 virtual void check()
1698 {
1699 I(downcast_to_dir_t(result.roster.get_node(name_conflict_nid))->children.size() == 2);
1700 check_nn_conflict();
1701 }
1702};
1703
1704struct node_name_plus_illegal_name : public node_name_plus_helper
1705{
1706 node_id new_root_nid;
1707
1708 virtual void setup()
1709 {
1710 new_root_nid = nis.next();
1711 make_dir(left_roster, left_markings, old_rid, old_rid, "new_root", new_root_nid);
1712 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1713 safe_erase(right_markings, root_nid);
1714 make_dir(right_roster, right_markings, old_rid, right_rid, "", new_root_nid);
1715 make_nn_conflict("new_root/_MTN", "foo");
1716 }
1717
1718 virtual void check()
1719 {
1720 I(result.roster.root()->self == new_root_nid);
1721 I(result.roster.all_nodes().size() == 2);
1722 check_nn_conflict();
1723 }
1724};
1725
1726struct node_name_plus_missing_root : public structural_conflict_helper
1727{
1728 node_id left_root_nid, right_root_nid;
1729
1730 virtual void setup()
1731 {
1732 left_root_nid = nis.next();
1733 right_root_nid = nis.next();
1734
1735 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1736 safe_erase(left_markings, root_nid);
1737 make_dir(left_roster, left_markings, old_rid, left_rid, "", left_root_nid);
1738 make_dir(left_roster, left_markings, old_rid, left_rid, "right_root", right_root_nid);
1739
1740 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1741 safe_erase(right_markings, root_nid);
1742 make_dir(right_roster, right_markings, old_rid, right_rid, "", right_root_nid);
1743 make_dir(right_roster, right_markings, old_rid, right_rid, "left_root", left_root_nid);
1744 }
1745 void check_helper(node_name_conflict const & left_c, node_name_conflict const & right_c)
1746 {
1747 I(left_c.nid == left_root_nid);
1748 I(left_c.left == make_pair(the_null_node, the_null_component));
1749 I(left_c.right == make_pair(right_root_nid, idx(split("left_root"), 1)));
1750
1751 I(right_c.nid == right_root_nid);
1752 I(right_c.left == make_pair(left_root_nid, idx(split("right_root"), 1)));
1753 I(right_c.right == make_pair(the_null_node, the_null_component));
1754 }
1755 virtual void check()
1756 {
1757 I(!result.is_clean());
1758 I(result.node_name_conflicts.size() == 2);
1759
1760 if (idx(result.node_name_conflicts, 0).nid == left_root_nid)
1761 check_helper(idx(result.node_name_conflicts, 0),
1762 idx(result.node_name_conflicts, 1));
1763 else
1764 check_helper(idx(result.node_name_conflicts, 1),
1765 idx(result.node_name_conflicts, 0));
1766
1767 I(result.missing_root_dir);
1768
1769 result.roster.attach_node(left_root_nid, split(""));
1770 result.roster.attach_node(right_root_nid, split("totally_other_name"));
1771 result.node_name_conflicts.pop_back();
1772 result.node_name_conflicts.pop_back();
1773 result.missing_root_dir = false;
1774 I(result.is_clean());
1775 result.roster.check_sane();
1776 }
1777};
1778
1779struct rename_target_plus_missing_root : public structural_conflict_helper
1780{
1781 node_id left_root_nid, right_root_nid;
1782
1783 virtual void setup()
1784 {
1785 left_root_nid = nis.next();
1786 right_root_nid = nis.next();
1787
1788 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1789 safe_erase(left_markings, root_nid);
1790 make_dir(left_roster, left_markings, left_rid, left_rid, "", left_root_nid);
1791
1792 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1793 safe_erase(right_markings, root_nid);
1794 make_dir(right_roster, right_markings, right_rid, right_rid, "", right_root_nid);
1795 }
1796 virtual void check()
1797 {
1798 I(!result.is_clean());
1799 rename_target_conflict const & c = idx(result.rename_target_conflicts, 0);
1800 I((c.nid1 == left_root_nid && c.nid2 == right_root_nid)
1801 || (c.nid1 == right_root_nid && c.nid2 == left_root_nid));
1802 I(c.parent_name == make_pair(the_null_node, the_null_component));
1803
1804 I(result.missing_root_dir);
1805
1806 // we can't just attach one of these as the root -- see the massive
1807 // comment on the old_locations member of roster_t, in roster.hh.
1808 result.roster.attach_node(result.roster.create_dir_node(nis), split(""));
1809 result.roster.attach_node(left_root_nid, split("totally_left_name"));
1810 result.roster.attach_node(right_root_nid, split("totally_right_name"));
1811 result.rename_target_conflicts.pop_back();
1812 result.missing_root_dir = false;
1813 I(result.is_clean());
1814 result.roster.check_sane();
1815 }
1816};
1817
1818static void
1819test_complex_structural_conflicts()
1820{
1821 {
1822 node_name_plus_rename_target t;
1823 t.test();
1824 }
1825 {
1826 node_name_plus_orphan t;
1827 t.test();
1828 }
1829 {
1830 node_name_plus_directory_loop t;
1831 t.test();
1832 }
1833 {
1834 node_name_plus_illegal_name t;
1835 t.test();
1836 }
1837 {
1838 node_name_plus_missing_root t;
1839 t.test();
1840 }
1841 {
1842 rename_target_plus_missing_root t;
1843 t.test();
1844 }
1845}
1846
1847void
1848add_roster_merge_tests(test_suite * suite)
1849{
1850 I(suite);
1851 suite->add(BOOST_TEST_CASE(&test_roster_merge_node_lifecycle));
1852 suite->add(BOOST_TEST_CASE(&test_roster_merge_attr_lifecycle));
1853 suite->add(BOOST_TEST_CASE(&test_scalar_merges));
1854 suite->add(BOOST_TEST_CASE(&test_simple_structural_conflicts));
1855 suite->add(BOOST_TEST_CASE(&test_complex_structural_conflicts));
1856}
1857
1858#endif // BUILD_UNIT_TESTS
1859
1860// Local Variables:
1861// mode: C++
1862// fill-column: 76
1863// c-file-style: "gnu"
1864// indent-tabs-mode: nil
1865// End:
1866// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status