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