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 L(FL("Performing a roster_merge"));
393
394 result.clear();
395 MM(left_parent);
396 MM(left_markings);
397 MM(right_parent);
398 MM(right_markings);
399 MM(result);
400
401 // First handle lifecycles, by die-die-die merge -- our result will contain
402 // everything that is alive in both parents, or alive in one and unborn in
403 // the other, exactly.
404 {
405 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
406 while (i.next())
407 {
408 switch (i.state())
409 {
410 case parallel::invalid:
411 I(false);
412
413 case parallel::in_left:
414 insert_if_unborn(i.left_data(),
415 left_markings, left_uncommon_ancestors,
416 result.roster);
417 break;
418
419 case parallel::in_right:
420 insert_if_unborn(i.right_data(),
421 right_markings, right_uncommon_ancestors,
422 result.roster);
423 break;
424
425 case parallel::in_both:
426 create_node_for(i.left_data(), result.roster);
427 break;
428 }
429 }
430 }
431
432 // okay, our roster now contains a bunch of empty, detached nodes. fill
433 // them in one at a time with *-merge.
434 {
435 node_map::const_iterator left_i, right_i;
436 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
437 node_map::const_iterator new_i = result.roster.all_nodes().begin();
438 marking_map::const_iterator left_mi = left_markings.begin();
439 marking_map::const_iterator right_mi = right_markings.begin();
440 while (i.next())
441 {
442 switch (i.state())
443 {
444 case parallel::invalid:
445 I(false);
446
447 case parallel::in_left:
448 {
449 node_t const & left_n = i.left_data();
450 // we skip nodes that aren't in the result roster (were
451 // deleted in the lifecycles step above)
452 if (result.roster.has_node(left_n->self))
453 {
454 copy_node_forward(result, new_i->second, left_n);
455 ++new_i;
456 }
457 ++left_mi;
458 break;
459 }
460
461 case parallel::in_right:
462 {
463 node_t const & right_n = i.right_data();
464 // we skip nodes that aren't in the result roster
465 if (result.roster.has_node(right_n->self))
466 {
467 copy_node_forward(result, new_i->second, right_n);
468 ++new_i;
469 }
470 ++right_mi;
471 break;
472 }
473
474 case parallel::in_both:
475 {
476 I(new_i->first == i.left_key());
477 I(left_mi->first == i.left_key());
478 I(right_mi->first == i.right_key());
479 node_t const & left_n = i.left_data();
480 marking_t const & left_marking = left_mi->second;
481 node_t const & right_n = i.right_data();
482 marking_t const & right_marking = right_mi->second;
483 node_t const & new_n = new_i->second;
484 // merge name
485 {
486 pair<node_id, path_component> new_name;
487 node_name_conflict conflict(new_n->self);
488 if (merge_scalar(make_pair(left_n->parent, left_n->name),
489 left_marking.parent_name,
490 left_uncommon_ancestors,
491 make_pair(right_n->parent, right_n->name),
492 right_marking.parent_name,
493 right_uncommon_ancestors,
494 new_name, conflict))
495 {
496 assign_name(result, new_n->self,
497 new_name.first, new_name.second);
498 }
499 else
500 {
501 // unsuccessful merge; leave node detached and save
502 // conflict object
503 result.node_name_conflicts.push_back(conflict);
504 }
505 }
506 // if a file, merge content
507 if (is_file_t(new_n))
508 {
509 file_content_conflict conflict(new_n->self);
510 if (merge_scalar(downcast_to_file_t(left_n)->content,
511 left_marking.file_content,
512 left_uncommon_ancestors,
513 downcast_to_file_t(right_n)->content,
514 right_marking.file_content,
515 right_uncommon_ancestors,
516 downcast_to_file_t(new_n)->content,
517 conflict))
518 {
519 // successful merge
520 }
521 else
522 {
523 downcast_to_file_t(new_n)->content = file_id();
524 result.file_content_conflicts.push_back(conflict);
525 }
526 }
527 // merge attributes
528 {
529 full_attr_map_t::const_iterator left_ai = left_n->attrs.begin();
530 full_attr_map_t::const_iterator right_ai = right_n->attrs.begin();
531 parallel::iter<full_attr_map_t> attr_i(left_n->attrs,
532 right_n->attrs);
533 while(attr_i.next())
534 {
535 switch (attr_i.state())
536 {
537 case parallel::invalid:
538 I(false);
539 case parallel::in_left:
540 safe_insert(new_n->attrs, attr_i.left_value());
541 break;
542 case parallel::in_right:
543 safe_insert(new_n->attrs, attr_i.right_value());
544 break;
545 case parallel::in_both:
546 pair<bool, attr_value> new_value;
547 node_attr_conflict conflict(new_n->self);
548 conflict.key = attr_i.left_key();
549 I(conflict.key == attr_i.right_key());
550 if (merge_scalar(attr_i.left_data(),
551 safe_get(left_marking.attrs,
552 attr_i.left_key()),
553 left_uncommon_ancestors,
554 attr_i.right_data(),
555 safe_get(right_marking.attrs,
556 attr_i.right_key()),
557 right_uncommon_ancestors,
558 new_value,
559 conflict))
560 {
561 // successful merge
562 safe_insert(new_n->attrs,
563 make_pair(attr_i.left_key(),
564 new_value));
565 }
566 else
567 {
568 // unsuccessful merge
569 // leave out the attr entry entirely, and save the
570 // conflict
571 result.node_attr_conflicts.push_back(conflict);
572 }
573 break;
574 }
575
576 }
577 }
578 }
579 ++left_mi;
580 ++right_mi;
581 ++new_i;
582 break;
583 }
584 }
585 I(left_mi == left_markings.end());
586 I(right_mi == right_markings.end());
587 I(new_i == result.roster.all_nodes().end());
588 }
589
590 // now check for the possible global problems
591 if (!result.roster.has_root())
592 result.missing_root_dir = true;
593 else
594 {
595 // we can't have an illegal _MTN dir unless we have a root node in the
596 // first place...
597 split_path bookkeeping_root_split;
598 bookkeeping_root_split.push_back(the_null_component);
599 bookkeeping_root_split.push_back(bookkeeping_root_component);
600 if (result.roster.has_node(bookkeeping_root_split))
601 {
602 illegal_name_conflict conflict;
603 node_t n = result.roster.get_node(bookkeeping_root_split);
604 conflict.nid = n->self;
605 conflict.parent_name.first = n->parent;
606 conflict.parent_name.second = n->name;
607 I(n->name == bookkeeping_root_component);
608 I(n->self == result.roster.detach_node(bookkeeping_root_split));
609 result.illegal_name_conflicts.push_back(conflict);
610 }
611 }
612}
613
614#ifdef BUILD_UNIT_TESTS
615#include "unit_tests.hh"
616
617#include "roster_delta.hh"
618
619// cases for testing:
620//
621// (DONE:)
622//
623// lifecycle, file and dir
624// alive in both
625// alive in one and unborn in other (left vs. right)
626// alive in one and dead in other (left vs. right)
627//
628// mark merge:
629// same in both, same mark
630// same in both, diff marks
631// different, left wins with 1 mark
632// different, right wins with 1 mark
633// different, conflict with 1 mark
634// different, left wins with 2 marks
635// different, right wins with 2 marks
636// different, conflict with 1 mark winning, 1 mark losing
637// different, conflict with 2 marks both conflicting
638//
639// for:
640// node name and parent, file and dir
641// node attr, file and dir
642// file content
643//
644// attr lifecycle:
645// seen in both -->mark merge cases, above
646// live in one and unseen in other -->live
647// dead in one and unseen in other -->dead
648//
649// two diff nodes with same name
650// directory loops
651// orphans
652// illegal node ("_MTN")
653// missing root dir
654//
655// (NEEDED:)
656//
657// interactions:
658// in-node name conflict prevents other problems:
659// in-node name conflict + possible between-node name conflict
660// a vs. b, plus a, b, exist in result
661// left: 1: a
662// 2: b
663// right: 1: b
664// 3: a
665// in-node name conflict + both possible names orphaned
666// a/foo vs. b/foo conflict, + a, b exist in parents but deleted in
667// children
668// left: 1: a
669// 2: a/foo
670// right:
671// 3: b
672// 2: b/foo
673// in-node name conflict + directory loop conflict
674// a/bottom vs. b/bottom, with a and b both moved inside it
675// in-node name conflict + one name illegal
676// _MTN vs. foo
677// in-node name conflict causes other problems:
678// in-node name conflict + causes missing root dir
679// "" vs. foo and bar vs. ""
680// between-node name conflict prevents other problems:
681// between-node name conflict + both nodes orphaned
682// this is not possible
683// between-node name conflict + both nodes cause loop
684// this is not possible
685// between-node name conflict + both nodes illegal
686// two nodes that both merge to _MTN
687// this is not possible
688// between-node name conflict causes other problems:
689// between-node name conflict + causes missing root dir
690// two nodes that both want ""
691
692split_path
693split(string const & s)
694{
695 split_path sp;
696 file_path_internal(s).split(sp);
697 return sp;
698}
699
700typedef enum { scalar_a, scalar_b, scalar_conflict } scalar_val;
701
702template <> void
703dump(scalar_val const & v, string & out)
704{
705 switch (v)
706 {
707 case scalar_a:
708 out = "scalar_a";
709 break;
710 case scalar_b:
711 out = "scalar_b";
712 break;
713 case scalar_conflict:
714 out = "scalar_conflict";
715 break;
716 }
717}
718
719void string_to_set(string const & from, set<revision_id> & to)
720{
721 to.clear();
722 for (string::const_iterator i = from.begin(); i != from.end(); ++i)
723 {
724 string rid_str(40, *i);
725 to.insert(revision_id(rid_str));
726 }
727}
728
729
730template <typename S> void
731test_a_scalar_merge_impl(scalar_val left_val, string const & left_marks_str,
732 string const & left_uncommon_str,
733 scalar_val right_val, string const & right_marks_str,
734 string const & right_uncommon_str,
735 scalar_val expected_outcome)
736{
737 MM(left_val);
738 MM(left_marks_str);
739 MM(left_uncommon_str);
740 MM(right_val);
741 MM(right_marks_str);
742 MM(right_uncommon_str);
743 MM(expected_outcome);
744
745 S scalar;
746 roster_t left_parent, right_parent;
747 marking_map left_markings, right_markings;
748 set<revision_id> left_uncommon_ancestors, right_uncommon_ancestors;
749 roster_merge_result result;
750
751 set<revision_id> left_marks, right_marks;
752
753 MM(left_parent);
754 MM(right_parent);
755 MM(left_markings);
756 MM(right_markings);
757 MM(left_uncommon_ancestors);
758 MM(right_uncommon_ancestors);
759 MM(left_marks);
760 MM(right_marks);
761 MM(result);
762
763 string_to_set(left_marks_str, left_marks);
764 scalar.setup_parent(left_val, left_marks, left_parent, left_markings);
765 string_to_set(right_marks_str, right_marks);
766 scalar.setup_parent(right_val, right_marks, right_parent, right_markings);
767
768 string_to_set(left_uncommon_str, left_uncommon_ancestors);
769 string_to_set(right_uncommon_str, right_uncommon_ancestors);
770
771 roster_merge(left_parent, left_markings, left_uncommon_ancestors,
772 right_parent, right_markings, right_uncommon_ancestors,
773 result);
774
775 // go ahead and check the roster_delta code too, while we're at it...
776 test_roster_delta_on(left_parent, left_markings, right_parent, right_markings);
777
778 scalar.check_result(left_val, right_val, result, expected_outcome);
779}
780
781static const revision_id root_rid = revision_id(string("0000000000000000000000000000000000000000"));
782static const file_id arbitrary_file = file_id(string("0000000000000000000000000000000000000000"));
783
784struct base_scalar
785{
786 testing_node_id_source nis;
787 node_id root_nid;
788 node_id thing_nid;
789 base_scalar() : root_nid(nis.next()), thing_nid(nis.next())
790 {}
791
792 void
793 make_dir(string const & name, node_id nid, roster_t & r, marking_map & markings)
794 {
795 r.create_dir_node(nid);
796 r.attach_node(nid, split(name));
797 marking_t marking;
798 marking.birth_revision = root_rid;
799 marking.parent_name.insert(root_rid);
800 safe_insert(markings, make_pair(nid, marking));
801 }
802
803 void
804 make_file(string const & name, node_id nid, roster_t & r, marking_map & markings)
805 {
806 r.create_file_node(arbitrary_file, nid);
807 r.attach_node(nid, split(name));
808 marking_t marking;
809 marking.birth_revision = root_rid;
810 marking.parent_name.insert(root_rid);
811 marking.file_content.insert(root_rid);
812 safe_insert(markings, make_pair(nid, marking));
813 }
814
815 void
816 make_root(roster_t & r, marking_map & markings)
817 {
818 make_dir("", root_nid, r, markings);
819 }
820};
821
822struct file_scalar : public virtual base_scalar
823{
824 split_path thing_name;
825 file_scalar() : thing_name(split("thing"))
826 {}
827
828 void
829 make_thing(roster_t & r, marking_map & markings)
830 {
831 make_root(r, markings);
832 make_file("thing", thing_nid, r, markings);
833 }
834};
835
836struct dir_scalar : public virtual base_scalar
837{
838 split_path thing_name;
839 dir_scalar() : thing_name(split("thing"))
840 {}
841
842 void
843 make_thing(roster_t & r, marking_map & markings)
844 {
845 make_root(r, markings);
846 make_dir("thing", thing_nid, r, markings);
847 }
848};
849
850struct name_shared_stuff : public virtual base_scalar
851{
852 virtual split_path path_for(scalar_val val) = 0;
853 path_component pc_for(scalar_val val)
854 {
855 split_path sp = path_for(val);
856 return idx(sp, sp.size() - 1);
857 }
858 virtual node_id parent_for(scalar_val val) = 0;
859
860 void
861 check_result(scalar_val left_val, scalar_val right_val,
862 // NB result is writeable -- we can scribble on it
863 roster_merge_result & result, scalar_val expected_val)
864 {
865 split_path name;
866 switch (expected_val)
867 {
868 case scalar_a: case scalar_b:
869 result.roster.get_name(thing_nid, name);
870 I(name == path_for(expected_val));
871 break;
872 case scalar_conflict:
873 node_name_conflict const & c = idx(result.node_name_conflicts, 0);
874 I(c.nid == thing_nid);
875 I(c.left == make_pair(parent_for(left_val), pc_for(left_val)));
876 I(c.right == make_pair(parent_for(right_val), pc_for(right_val)));
877 I(null_node(result.roster.get_node(thing_nid)->parent));
878 I(null_name(result.roster.get_node(thing_nid)->name));
879 // resolve the conflict, thus making sure that resolution works and
880 // that this was the only conflict signaled
881 // attach implicitly checks that we were already detached
882 result.roster.attach_node(thing_nid, split("thing"));
883 result.node_name_conflicts.pop_back();
884 break;
885 }
886 // by now, the merge should have been resolved cleanly, one way or another
887 result.roster.check_sane();
888 I(result.is_clean());
889 }
890
891 virtual ~name_shared_stuff() {};
892};
893
894template <typename T>
895struct basename_scalar : public name_shared_stuff, public T
896{
897 virtual split_path path_for(scalar_val val)
898 {
899 I(val != scalar_conflict);
900 return split((val == scalar_a) ? "a" : "b");
901 }
902 virtual node_id parent_for(scalar_val val)
903 {
904 I(val != scalar_conflict);
905 return root_nid;
906 }
907
908 void
909 setup_parent(scalar_val val, set<revision_id> marks,
910 roster_t & r, marking_map & markings)
911 {
912 this->T::make_thing(r, markings);
913 r.detach_node(this->T::thing_name);
914 r.attach_node(thing_nid, path_for(val));
915 markings.find(thing_nid)->second.parent_name = marks;
916 }
917
918 virtual ~basename_scalar() {}
919};
920
921template <typename T>
922struct parent_scalar : public virtual name_shared_stuff, public T
923{
924 node_id a_dir_nid, b_dir_nid;
925 parent_scalar() : a_dir_nid(nis.next()), b_dir_nid(nis.next())
926 {}
927
928 virtual split_path path_for(scalar_val val)
929 {
930 I(val != scalar_conflict);
931 return split((val == scalar_a) ? "a/thing" : "b/thing");
932 }
933 virtual node_id parent_for(scalar_val val)
934 {
935 I(val != scalar_conflict);
936 return ((val == scalar_a) ? a_dir_nid : b_dir_nid);
937 }
938
939 void
940 setup_parent(scalar_val val, set<revision_id> marks,
941 roster_t & r, marking_map & markings)
942 {
943 this->T::make_thing(r, markings);
944 make_dir("a", a_dir_nid, r, markings);
945 make_dir("b", b_dir_nid, r, markings);
946 r.detach_node(this->T::thing_name);
947 r.attach_node(thing_nid, path_for(val));
948 markings.find(thing_nid)->second.parent_name = marks;
949 }
950
951 virtual ~parent_scalar() {}
952};
953
954template <typename T>
955struct attr_scalar : public virtual base_scalar, public T
956{
957 attr_value attr_value_for(scalar_val val)
958 {
959 I(val != scalar_conflict);
960 return attr_value((val == scalar_a) ? "a" : "b");
961 }
962
963 void
964 setup_parent(scalar_val val, set<revision_id> marks,
965 roster_t & r, marking_map & markings)
966 {
967 this->T::make_thing(r, markings);
968 r.set_attr(this->T::thing_name, attr_key("test_key"), attr_value_for(val));
969 markings.find(thing_nid)->second.attrs[attr_key("test_key")] = marks;
970 }
971
972 void
973 check_result(scalar_val left_val, scalar_val right_val,
974 // NB result is writeable -- we can scribble on it
975 roster_merge_result & result, scalar_val expected_val)
976 {
977 split_path name;
978 switch (expected_val)
979 {
980 case scalar_a: case scalar_b:
981 I(result.roster.get_node(thing_nid)->attrs[attr_key("test_key")]
982 == make_pair(true, attr_value_for(expected_val)));
983 break;
984 case scalar_conflict:
985 node_attr_conflict const & c = idx(result.node_attr_conflicts, 0);
986 I(c.nid == thing_nid);
987 I(c.key == attr_key("test_key"));
988 I(c.left == make_pair(true, attr_value_for(left_val)));
989 I(c.right == make_pair(true, attr_value_for(right_val)));
990 full_attr_map_t const & attrs = result.roster.get_node(thing_nid)->attrs;
991 I(attrs.find(attr_key("test_key")) == attrs.end());
992 // resolve the conflict, thus making sure that resolution works and
993 // that this was the only conflict signaled
994 result.roster.set_attr(this->T::thing_name, attr_key("test_key"),
995 attr_value("conflict -- RESOLVED"));
996 result.node_attr_conflicts.pop_back();
997 break;
998 }
999 // by now, the merge should have been resolved cleanly, one way or another
1000 result.roster.check_sane();
1001 I(result.is_clean());
1002 }
1003};
1004
1005struct file_content_scalar : public virtual file_scalar
1006{
1007 file_id content_for(scalar_val val)
1008 {
1009 I(val != scalar_conflict);
1010 return file_id(string((val == scalar_a)
1011 ? "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1012 : "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1013 }
1014
1015 void
1016 setup_parent(scalar_val val, set<revision_id> marks,
1017 roster_t & r, marking_map & markings)
1018 {
1019 make_thing(r, markings);
1020 downcast_to_file_t(r.get_node(thing_name))->content = content_for(val);
1021 markings.find(thing_nid)->second.file_content = marks;
1022 }
1023
1024 void
1025 check_result(scalar_val left_val, scalar_val right_val,
1026 // NB result is writeable -- we can scribble on it
1027 roster_merge_result & result, scalar_val expected_val)
1028 {
1029 split_path name;
1030 switch (expected_val)
1031 {
1032 case scalar_a: case scalar_b:
1033 I(downcast_to_file_t(result.roster.get_node(thing_nid))->content
1034 == content_for(expected_val));
1035 break;
1036 case scalar_conflict:
1037 file_content_conflict const & c = idx(result.file_content_conflicts, 0);
1038 I(c.nid == thing_nid);
1039 I(c.left == content_for(left_val));
1040 I(c.right == content_for(right_val));
1041 file_id & content = downcast_to_file_t(result.roster.get_node(thing_nid))->content;
1042 I(null_id(content));
1043 // resolve the conflict, thus making sure that resolution works and
1044 // that this was the only conflict signaled
1045 content = file_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1046 result.file_content_conflicts.pop_back();
1047 break;
1048 }
1049 // by now, the merge should have been resolved cleanly, one way or another
1050 result.roster.check_sane();
1051 I(result.is_clean());
1052 }
1053};
1054
1055void
1056test_a_scalar_merge(scalar_val left_val, string const & left_marks_str,
1057 string const & left_uncommon_str,
1058 scalar_val right_val, string const & right_marks_str,
1059 string const & right_uncommon_str,
1060 scalar_val expected_outcome)
1061{
1062 test_a_scalar_merge_impl<basename_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1063 right_val, right_marks_str, right_uncommon_str,
1064 expected_outcome);
1065 test_a_scalar_merge_impl<basename_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1066 right_val, right_marks_str, right_uncommon_str,
1067 expected_outcome);
1068 test_a_scalar_merge_impl<parent_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1069 right_val, right_marks_str, right_uncommon_str,
1070 expected_outcome);
1071 test_a_scalar_merge_impl<parent_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1072 right_val, right_marks_str, right_uncommon_str,
1073 expected_outcome);
1074 test_a_scalar_merge_impl<attr_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1075 right_val, right_marks_str, right_uncommon_str,
1076 expected_outcome);
1077 test_a_scalar_merge_impl<attr_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1078 right_val, right_marks_str, right_uncommon_str,
1079 expected_outcome);
1080 test_a_scalar_merge_impl<file_content_scalar>(left_val, left_marks_str, left_uncommon_str,
1081 right_val, right_marks_str, right_uncommon_str,
1082 expected_outcome);
1083}
1084
1085UNIT_TEST(roster_merge, scalar_merges)
1086{
1087 // Notation: a1* means, "value is a, this is node 1 in the graph, it is
1088 // marked". ".2" means, "value is unimportant and different from either a
1089 // or b, this is node 2 in the graph, it is not marked".
1090 //
1091 // Backslashes with dots after them mean, the C++ line continuation rules
1092 // are annoying when it comes to drawing ascii graphs -- the dot is only to
1093 // stop the backslash from having special meaning to the parser. So just
1094 // ignore them :-).
1095
1096 // same in both, same mark
1097 // a1*
1098 // / \.
1099 // a2 a3
1100 test_a_scalar_merge(scalar_a, "1", "2", scalar_a, "1", "3", scalar_a);
1101
1102 // same in both, diff marks
1103 // .1*
1104 // / \.
1105 // a2* a3*
1106 test_a_scalar_merge(scalar_a, "2", "2", scalar_a, "3", "3", scalar_a);
1107
1108 // different, left wins with 1 mark
1109 // a1*
1110 // / \.
1111 // b2* a3
1112 test_a_scalar_merge(scalar_b, "2", "2", scalar_a, "1", "3", scalar_b);
1113
1114 // different, right wins with 1 mark
1115 // a1*
1116 // / \.
1117 // a2 b3*
1118 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "3", "3", scalar_b);
1119
1120 // different, conflict with 1 mark
1121 // .1*
1122 // / \.
1123 // a2* b3*
1124 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "3", "3", scalar_conflict);
1125
1126 // different, left wins with 2 marks
1127 // a1*
1128 // / \.
1129 // a2 a3
1130 // / \.
1131 // b4* b5*
1132 // \ /
1133 // b6
1134 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "1", "3", scalar_b);
1135
1136 // different, right wins with 2 marks
1137 // a1*
1138 // / \.
1139 // a2 a3
1140 // / \.
1141 // b4* b5*
1142 // \ /
1143 // b6
1144 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "45", "3456", scalar_b);
1145
1146 // different, conflict with 1 mark winning, 1 mark losing
1147 // .1*
1148 // / \.
1149 // a2* a3*
1150 // \ / \.
1151 // a4 b5*
1152 test_a_scalar_merge(scalar_a, "23", "24", scalar_b, "5", "5", scalar_conflict);
1153
1154 //
1155 // .1*
1156 // / \.
1157 // a2* a3*
1158 // / \ /
1159 // b4* a5
1160 test_a_scalar_merge(scalar_b, "4", "4", scalar_a, "23", "35", scalar_conflict);
1161
1162 // different, conflict with 2 marks both conflicting
1163 //
1164 // .1*
1165 // / \.
1166 // .2 a3*
1167 // / \.
1168 // b4* b5*
1169 // \ /
1170 // b6
1171 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "3", "3", scalar_conflict);
1172
1173 //
1174 // .1*
1175 // / \.
1176 // a2* .3
1177 // / \.
1178 // b4* b5*
1179 // \ /
1180 // b6
1181 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "45", "3456", scalar_conflict);
1182
1183 //
1184 // _.1*_
1185 // / \.
1186 // .2 .3
1187 // / \ / \.
1188 // a4* a5* b6* b7*
1189 // \ / \ /
1190 // a8 b9
1191 test_a_scalar_merge(scalar_a, "45", "2458", scalar_b, "67", "3679", scalar_conflict);
1192}
1193
1194namespace
1195{
1196 const revision_id a_uncommon1 = revision_id(string("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
1197 const revision_id a_uncommon2 = revision_id(string("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1198 const revision_id b_uncommon1 = revision_id(string("cccccccccccccccccccccccccccccccccccccccc"));
1199 const revision_id b_uncommon2 = revision_id(string("dddddddddddddddddddddddddddddddddddddddd"));
1200 const revision_id common1 = revision_id(string("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"));
1201 const revision_id common2 = revision_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1202
1203 const file_id fid1 = file_id(string("1111111111111111111111111111111111111111"));
1204 const file_id fid2 = file_id(string("2222222222222222222222222222222222222222"));
1205
1206}
1207
1208static void
1209make_dir(roster_t & r, marking_map & markings,
1210 revision_id const & birth_rid, revision_id const & parent_name_rid,
1211 string const & name, node_id nid)
1212{
1213 r.create_dir_node(nid);
1214 r.attach_node(nid, split(name));
1215 marking_t marking;
1216 marking.birth_revision = birth_rid;
1217 marking.parent_name.insert(parent_name_rid);
1218 safe_insert(markings, make_pair(nid, marking));
1219}
1220
1221static void
1222make_file(roster_t & r, marking_map & markings,
1223 revision_id const & birth_rid, revision_id const & parent_name_rid,
1224 revision_id const & file_content_rid,
1225 string const & name, file_id const & content,
1226 node_id nid)
1227{
1228 r.create_file_node(content, nid);
1229 r.attach_node(nid, split(name));
1230 marking_t marking;
1231 marking.birth_revision = birth_rid;
1232 marking.parent_name.insert(parent_name_rid);
1233 marking.file_content.insert(file_content_rid);
1234 safe_insert(markings, make_pair(nid, marking));
1235}
1236
1237static void
1238make_node_lifecycle_objs(roster_t & r, marking_map & markings, revision_id const & uncommon,
1239 string const & name, node_id common_dir_nid, node_id common_file_nid,
1240 node_id & safe_dir_nid, node_id & safe_file_nid, node_id_source & nis)
1241{
1242 make_dir(r, markings, common1, common1, "common_old_dir", common_dir_nid);
1243 make_file(r, markings, common1, common1, common1, "common_old_file", fid1, common_file_nid);
1244 safe_dir_nid = nis.next();
1245 make_dir(r, markings, uncommon, uncommon, name + "_safe_dir", safe_dir_nid);
1246 safe_file_nid = nis.next();
1247 make_file(r, markings, uncommon, uncommon, uncommon, name + "_safe_file", fid1, safe_file_nid);
1248 make_dir(r, markings, common1, common1, name + "_dead_dir", nis.next());
1249 make_file(r, markings, common1, common1, common1, name + "_dead_file", fid1, nis.next());
1250}
1251
1252UNIT_TEST(roster_merge, node_lifecycle)
1253{
1254 roster_t a_roster, b_roster;
1255 marking_map a_markings, b_markings;
1256 set<revision_id> a_uncommon, b_uncommon;
1257 // boilerplate to get uncommon revision sets...
1258 a_uncommon.insert(a_uncommon1);
1259 a_uncommon.insert(a_uncommon2);
1260 b_uncommon.insert(b_uncommon1);
1261 b_uncommon.insert(b_uncommon2);
1262 testing_node_id_source nis;
1263 // boilerplate to set up a root node...
1264 {
1265 node_id root_nid = nis.next();
1266 make_dir(a_roster, a_markings, common1, common1, "", root_nid);
1267 make_dir(b_roster, b_markings, common1, common1, "", root_nid);
1268 }
1269 // create some nodes on each side
1270 node_id common_dir_nid = nis.next();
1271 node_id common_file_nid = nis.next();
1272 node_id a_safe_dir_nid, a_safe_file_nid, b_safe_dir_nid, b_safe_file_nid;
1273 make_node_lifecycle_objs(a_roster, a_markings, a_uncommon1, "a", common_dir_nid, common_file_nid,
1274 a_safe_dir_nid, a_safe_file_nid, nis);
1275 make_node_lifecycle_objs(b_roster, b_markings, b_uncommon1, "b", common_dir_nid, common_file_nid,
1276 b_safe_dir_nid, b_safe_file_nid, nis);
1277 // do the merge
1278 roster_merge_result result;
1279 roster_merge(a_roster, a_markings, a_uncommon, b_roster, b_markings, b_uncommon, result);
1280 I(result.is_clean());
1281 // go ahead and check the roster_delta code too, while we're at it...
1282 test_roster_delta_on(a_roster, a_markings, b_roster, b_markings);
1283 // 7 = 1 root + 2 common + 2 safe a + 2 safe b
1284 I(result.roster.all_nodes().size() == 7);
1285 // check that they're the right ones...
1286 I(shallow_equal(result.roster.get_node(common_dir_nid),
1287 a_roster.get_node(common_dir_nid), false));
1288 I(shallow_equal(result.roster.get_node(common_file_nid),
1289 a_roster.get_node(common_file_nid), false));
1290 I(shallow_equal(result.roster.get_node(common_dir_nid),
1291 b_roster.get_node(common_dir_nid), false));
1292 I(shallow_equal(result.roster.get_node(common_file_nid),
1293 b_roster.get_node(common_file_nid), false));
1294 I(shallow_equal(result.roster.get_node(a_safe_dir_nid),
1295 a_roster.get_node(a_safe_dir_nid), false));
1296 I(shallow_equal(result.roster.get_node(a_safe_file_nid),
1297 a_roster.get_node(a_safe_file_nid), false));
1298 I(shallow_equal(result.roster.get_node(b_safe_dir_nid),
1299 b_roster.get_node(b_safe_dir_nid), false));
1300 I(shallow_equal(result.roster.get_node(b_safe_file_nid),
1301 b_roster.get_node(b_safe_file_nid), false));
1302}
1303
1304UNIT_TEST(roster_merge, attr_lifecycle)
1305{
1306 roster_t left_roster, right_roster;
1307 marking_map left_markings, right_markings;
1308 MM(left_roster);
1309 MM(left_markings);
1310 MM(right_roster);
1311 MM(right_markings);
1312 set<revision_id> old_revs, left_revs, right_revs;
1313 string_to_set("0", old_revs);
1314 string_to_set("1", left_revs);
1315 string_to_set("2", right_revs);
1316 revision_id old_rid = *old_revs.begin();
1317 testing_node_id_source nis;
1318 node_id dir_nid = nis.next();
1319 make_dir(left_roster, left_markings, old_rid, old_rid, "", dir_nid);
1320 make_dir(right_roster, right_markings, old_rid, old_rid, "", dir_nid);
1321 node_id file_nid = nis.next();
1322 make_file(left_roster, left_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1323 make_file(right_roster, right_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1324
1325 // put one live and one dead attr on each thing on each side, with uncommon
1326 // marks on them
1327 safe_insert(left_roster.get_node(dir_nid)->attrs,
1328 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1329 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1330 safe_insert(left_roster.get_node(dir_nid)->attrs,
1331 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1332 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1333 safe_insert(left_roster.get_node(file_nid)->attrs,
1334 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1335 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1336 safe_insert(left_roster.get_node(file_nid)->attrs,
1337 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1338 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1339
1340 safe_insert(right_roster.get_node(dir_nid)->attrs,
1341 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
1342 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_live"), right_revs));
1343 safe_insert(right_roster.get_node(dir_nid)->attrs,
1344 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
1345 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
1346 safe_insert(right_roster.get_node(file_nid)->attrs,
1347 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
1348 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_live"), right_revs));
1349 safe_insert(right_roster.get_node(file_nid)->attrs,
1350 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
1351 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
1352
1353 roster_merge_result result;
1354 MM(result);
1355 roster_merge(left_roster, left_markings, left_revs,
1356 right_roster, right_markings, right_revs,
1357 result);
1358 // go ahead and check the roster_delta code too, while we're at it...
1359 test_roster_delta_on(left_roster, left_markings, right_roster, right_markings);
1360 I(result.roster.all_nodes().size() == 2);
1361 I(result.roster.get_node(dir_nid)->attrs.size() == 4);
1362 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
1363 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1364 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
1365 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1366 I(result.roster.get_node(file_nid)->attrs.size() == 4);
1367 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
1368 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1369 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
1370 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
1371}
1372
1373struct structural_conflict_helper
1374{
1375 roster_t left_roster, right_roster;
1376 marking_map left_markings, right_markings;
1377 set<revision_id> old_revs, left_revs, right_revs;
1378 revision_id old_rid, left_rid, right_rid;
1379 testing_node_id_source nis;
1380 node_id root_nid;
1381 roster_merge_result result;
1382
1383 virtual void setup() = 0;
1384 virtual void check() = 0;
1385
1386 void test()
1387 {
1388 MM(left_roster);
1389 MM(left_markings);
1390 MM(right_roster);
1391 MM(right_markings);
1392 string_to_set("0", old_revs);
1393 string_to_set("1", left_revs);
1394 string_to_set("2", right_revs);
1395 old_rid = *old_revs.begin();
1396 left_rid = *left_revs.begin();
1397 right_rid = *right_revs.begin();
1398 root_nid = nis.next();
1399 make_dir(left_roster, left_markings, old_rid, old_rid, "", root_nid);
1400 make_dir(right_roster, right_markings, old_rid, old_rid, "", root_nid);
1401
1402 setup();
1403
1404 MM(result);
1405 roster_merge(left_roster, left_markings, left_revs,
1406 right_roster, right_markings, right_revs,
1407 result);
1408 // go ahead and check the roster_delta code too, while we're at it...
1409 test_roster_delta_on(left_roster, left_markings, right_roster, right_markings);
1410
1411 check();
1412 }
1413
1414 virtual ~structural_conflict_helper() {}
1415};
1416
1417// two diff nodes with same name
1418struct simple_rename_target_conflict : public structural_conflict_helper
1419{
1420 node_id left_nid, right_nid;
1421 virtual void setup()
1422 {
1423 left_nid = nis.next();
1424 make_dir(left_roster, left_markings, left_rid, left_rid, "thing", left_nid);
1425 right_nid = nis.next();
1426 make_dir(right_roster, right_markings, right_rid, right_rid, "thing", right_nid);
1427 }
1428
1429 virtual void check()
1430 {
1431 I(!result.is_clean());
1432 rename_target_conflict const & c = idx(result.rename_target_conflicts, 0);
1433 I((c.nid1 == left_nid && c.nid2 == right_nid)
1434 || (c.nid1 == right_nid && c.nid2 == left_nid));
1435 I(c.parent_name == make_pair(root_nid, idx(split("thing"), 1)));
1436 // this tests that they were detached, implicitly
1437 result.roster.attach_node(left_nid, split("left"));
1438 result.roster.attach_node(right_nid, split("right"));
1439 result.rename_target_conflicts.pop_back();
1440 I(result.is_clean());
1441 result.roster.check_sane();
1442 }
1443};
1444
1445// directory loops
1446struct simple_dir_loop_conflict : public structural_conflict_helper
1447{
1448 node_id left_top_nid, right_top_nid;
1449
1450 virtual void setup()
1451 {
1452 left_top_nid = nis.next();
1453 right_top_nid = nis.next();
1454
1455 make_dir(left_roster, left_markings, old_rid, old_rid, "top", left_top_nid);
1456 make_dir(left_roster, left_markings, old_rid, left_rid, "top/bottom", right_top_nid);
1457
1458 make_dir(right_roster, right_markings, old_rid, old_rid, "top", right_top_nid);
1459 make_dir(right_roster, right_markings, old_rid, right_rid, "top/bottom", left_top_nid);
1460 }
1461
1462 virtual void check()
1463 {
1464 I(!result.is_clean());
1465 directory_loop_conflict const & c = idx(result.directory_loop_conflicts, 0);
1466 I((c.nid == left_top_nid && c.parent_name == make_pair(right_top_nid, idx(split("bottom"), 1)))
1467 || (c.nid == right_top_nid && c.parent_name == make_pair(left_top_nid, idx(split("bottom"), 1))));
1468 // this tests it was detached, implicitly
1469 result.roster.attach_node(c.nid, split("resolved"));
1470 result.directory_loop_conflicts.pop_back();
1471 I(result.is_clean());
1472 result.roster.check_sane();
1473 }
1474};
1475
1476// orphans
1477struct simple_orphan_conflict : public structural_conflict_helper
1478{
1479 node_id a_dead_parent_nid, a_live_child_nid, b_dead_parent_nid, b_live_child_nid;
1480
1481 // in ancestor, both parents are alive
1482 // in left, a_dead_parent is dead, and b_live_child is created
1483 // in right, b_dead_parent is dead, and a_live_child is created
1484
1485 virtual void setup()
1486 {
1487 a_dead_parent_nid = nis.next();
1488 a_live_child_nid = nis.next();
1489 b_dead_parent_nid = nis.next();
1490 b_live_child_nid = nis.next();
1491
1492 make_dir(left_roster, left_markings, old_rid, old_rid, "b_parent", b_dead_parent_nid);
1493 make_dir(left_roster, left_markings, left_rid, left_rid, "b_parent/b_child", b_live_child_nid);
1494
1495 make_dir(right_roster, right_markings, old_rid, old_rid, "a_parent", a_dead_parent_nid);
1496 make_dir(right_roster, right_markings, right_rid, right_rid, "a_parent/a_child", a_live_child_nid);
1497 }
1498
1499 virtual void check()
1500 {
1501 I(!result.is_clean());
1502 I(result.orphaned_node_conflicts.size() == 2);
1503 orphaned_node_conflict a, b;
1504 if (idx(result.orphaned_node_conflicts, 0).nid == a_live_child_nid)
1505 {
1506 a = idx(result.orphaned_node_conflicts, 0);
1507 b = idx(result.orphaned_node_conflicts, 1);
1508 }
1509 else
1510 {
1511 a = idx(result.orphaned_node_conflicts, 1);
1512 b = idx(result.orphaned_node_conflicts, 0);
1513 }
1514 I(a.nid == a_live_child_nid);
1515 I(a.parent_name == make_pair(a_dead_parent_nid, idx(split("a_child"), 1)));
1516 I(b.nid == b_live_child_nid);
1517 I(b.parent_name == make_pair(b_dead_parent_nid, idx(split("b_child"), 1)));
1518 // this tests it was detached, implicitly
1519 result.roster.attach_node(a.nid, split("resolved_a"));
1520 result.roster.attach_node(b.nid, split("resolved_b"));
1521 result.orphaned_node_conflicts.pop_back();
1522 result.orphaned_node_conflicts.pop_back();
1523 I(result.is_clean());
1524 result.roster.check_sane();
1525 }
1526};
1527
1528// illegal node ("_MTN")
1529struct simple_illegal_name_conflict : public structural_conflict_helper
1530{
1531 node_id new_root_nid, bad_dir_nid;
1532
1533 // in left, new_root is the root (it existed in old, but was renamed in left)
1534 // in right, new_root is still a subdir, the old root still exists, and a
1535 // new dir has been created
1536
1537 virtual void setup()
1538 {
1539 new_root_nid = nis.next();
1540 bad_dir_nid = nis.next();
1541
1542 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1543 safe_erase(left_markings, root_nid);
1544 make_dir(left_roster, left_markings, old_rid, left_rid, "", new_root_nid);
1545
1546 make_dir(right_roster, right_markings, old_rid, old_rid, "root_to_be", new_root_nid);
1547 make_dir(right_roster, right_markings, right_rid, right_rid, "root_to_be/_MTN", bad_dir_nid);
1548 }
1549
1550 virtual void check()
1551 {
1552 I(!result.is_clean());
1553 illegal_name_conflict const & c = idx(result.illegal_name_conflicts, 0);
1554 I(c.nid == bad_dir_nid);
1555 I(c.parent_name == make_pair(new_root_nid, bookkeeping_root_component));
1556 // this tests it was detached, implicitly
1557 result.roster.attach_node(bad_dir_nid, split("dir_formerly_known_as__MTN"));
1558 result.illegal_name_conflicts.pop_back();
1559 I(result.is_clean());
1560 result.roster.check_sane();
1561 }
1562};
1563
1564// missing root dir
1565struct simple_missing_root_dir : public structural_conflict_helper
1566{
1567 node_id other_root_nid;
1568
1569 // left and right each have different root nodes, and each has deleted the
1570 // other's root node
1571
1572 virtual void setup()
1573 {
1574 other_root_nid = nis.next();
1575
1576 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1577 safe_erase(left_markings, root_nid);
1578 make_dir(left_roster, left_markings, old_rid, old_rid, "", other_root_nid);
1579 }
1580
1581 virtual void check()
1582 {
1583 I(!result.is_clean());
1584 I(result.missing_root_dir);
1585 result.roster.attach_node(result.roster.create_dir_node(nis), split(""));
1586 result.missing_root_dir = false;
1587 I(result.is_clean());
1588 result.roster.check_sane();
1589 }
1590};
1591
1592UNIT_TEST(roster_merge, simple_structural_conflicts)
1593{
1594 {
1595 simple_rename_target_conflict t;
1596 t.test();
1597 }
1598 {
1599 simple_dir_loop_conflict t;
1600 t.test();
1601 }
1602 {
1603 simple_orphan_conflict t;
1604 t.test();
1605 }
1606 {
1607 simple_illegal_name_conflict t;
1608 t.test();
1609 }
1610 {
1611 simple_missing_root_dir t;
1612 t.test();
1613 }
1614}
1615
1616struct node_name_plus_helper : public structural_conflict_helper
1617{
1618 node_id name_conflict_nid;
1619 node_id left_parent, right_parent;
1620 path_component left_name, right_name;
1621 void make_nn_conflict(string const & left_path, string const & right_path)
1622 {
1623 name_conflict_nid = nis.next();
1624 make_dir(left_roster, left_markings, old_rid, left_rid, left_path, name_conflict_nid);
1625 left_parent = left_roster.get_node(split(left_path))->parent;
1626 left_name = left_roster.get_node(split(left_path))->name;
1627 make_dir(right_roster, right_markings, old_rid, right_rid, right_path, name_conflict_nid);
1628 right_parent = right_roster.get_node(split(right_path))->parent;
1629 right_name = right_roster.get_node(split(right_path))->name;
1630 }
1631 void check_nn_conflict()
1632 {
1633 I(!result.is_clean());
1634 node_name_conflict const & c = idx(result.node_name_conflicts, 0);
1635 I(c.nid == name_conflict_nid);
1636 I(c.left == make_pair(left_parent, left_name));
1637 I(c.right == make_pair(right_parent, right_name));
1638 result.roster.attach_node(name_conflict_nid, split("totally_other_name"));
1639 result.node_name_conflicts.pop_back();
1640 I(result.is_clean());
1641 result.roster.check_sane();
1642 }
1643};
1644
1645struct node_name_plus_rename_target : public node_name_plus_helper
1646{
1647 node_id a_nid, b_nid;
1648
1649 virtual void setup()
1650 {
1651 a_nid = nis.next();
1652 b_nid = nis.next();
1653 make_nn_conflict("a", "b");
1654 make_dir(left_roster, left_markings, left_rid, left_rid, "b", b_nid);
1655 make_dir(right_roster, right_markings, right_rid, right_rid, "a", a_nid);
1656 }
1657
1658 virtual void check()
1659 {
1660 // there should just be a single conflict on name_conflict_nid, and a and
1661 // b should have landed fine
1662 I(result.roster.get_node(split("a"))->self == a_nid);
1663 I(result.roster.get_node(split("b"))->self == b_nid);
1664 check_nn_conflict();
1665 }
1666};
1667
1668struct node_name_plus_orphan : public node_name_plus_helper
1669{
1670 node_id a_nid, b_nid;
1671
1672 virtual void setup()
1673 {
1674 a_nid = nis.next();
1675 b_nid = nis.next();
1676 make_dir(left_roster, left_markings, old_rid, left_rid, "a", a_nid);
1677 make_dir(right_roster, right_markings, old_rid, right_rid, "b", b_nid);
1678 make_nn_conflict("a/foo", "b/foo");
1679 }
1680
1681 virtual void check()
1682 {
1683 I(result.roster.all_nodes().size() == 2);
1684 check_nn_conflict();
1685 }
1686};
1687
1688struct node_name_plus_directory_loop : public node_name_plus_helper
1689{
1690 node_id a_nid, b_nid;
1691
1692 virtual void setup()
1693 {
1694 a_nid = nis.next();
1695 b_nid = nis.next();
1696 make_dir(left_roster, left_markings, old_rid, old_rid, "a", a_nid);
1697 make_dir(right_roster, right_markings, old_rid, old_rid, "b", b_nid);
1698 make_nn_conflict("a/foo", "b/foo");
1699 make_dir(left_roster, left_markings, old_rid, left_rid, "a/foo/b", b_nid);
1700 make_dir(right_roster, right_markings, old_rid, right_rid, "b/foo/a", a_nid);
1701 }
1702
1703 virtual void check()
1704 {
1705 I(downcast_to_dir_t(result.roster.get_node(name_conflict_nid))->children.size() == 2);
1706 check_nn_conflict();
1707 }
1708};
1709
1710struct node_name_plus_illegal_name : public node_name_plus_helper
1711{
1712 node_id new_root_nid;
1713
1714 virtual void setup()
1715 {
1716 new_root_nid = nis.next();
1717 make_dir(left_roster, left_markings, old_rid, old_rid, "new_root", new_root_nid);
1718 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1719 safe_erase(right_markings, root_nid);
1720 make_dir(right_roster, right_markings, old_rid, right_rid, "", new_root_nid);
1721 make_nn_conflict("new_root/_MTN", "foo");
1722 }
1723
1724 virtual void check()
1725 {
1726 I(result.roster.root()->self == new_root_nid);
1727 I(result.roster.all_nodes().size() == 2);
1728 check_nn_conflict();
1729 }
1730};
1731
1732struct node_name_plus_missing_root : public structural_conflict_helper
1733{
1734 node_id left_root_nid, right_root_nid;
1735
1736 virtual void setup()
1737 {
1738 left_root_nid = nis.next();
1739 right_root_nid = nis.next();
1740
1741 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1742 safe_erase(left_markings, root_nid);
1743 make_dir(left_roster, left_markings, old_rid, left_rid, "", left_root_nid);
1744 make_dir(left_roster, left_markings, old_rid, left_rid, "right_root", right_root_nid);
1745
1746 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1747 safe_erase(right_markings, root_nid);
1748 make_dir(right_roster, right_markings, old_rid, right_rid, "", right_root_nid);
1749 make_dir(right_roster, right_markings, old_rid, right_rid, "left_root", left_root_nid);
1750 }
1751 void check_helper(node_name_conflict const & left_c, node_name_conflict const & right_c)
1752 {
1753 I(left_c.nid == left_root_nid);
1754 I(left_c.left == make_pair(the_null_node, the_null_component));
1755 I(left_c.right == make_pair(right_root_nid, idx(split("left_root"), 1)));
1756
1757 I(right_c.nid == right_root_nid);
1758 I(right_c.left == make_pair(left_root_nid, idx(split("right_root"), 1)));
1759 I(right_c.right == make_pair(the_null_node, the_null_component));
1760 }
1761 virtual void check()
1762 {
1763 I(!result.is_clean());
1764 I(result.node_name_conflicts.size() == 2);
1765
1766 if (idx(result.node_name_conflicts, 0).nid == left_root_nid)
1767 check_helper(idx(result.node_name_conflicts, 0),
1768 idx(result.node_name_conflicts, 1));
1769 else
1770 check_helper(idx(result.node_name_conflicts, 1),
1771 idx(result.node_name_conflicts, 0));
1772
1773 I(result.missing_root_dir);
1774
1775 result.roster.attach_node(left_root_nid, split(""));
1776 result.roster.attach_node(right_root_nid, split("totally_other_name"));
1777 result.node_name_conflicts.pop_back();
1778 result.node_name_conflicts.pop_back();
1779 result.missing_root_dir = false;
1780 I(result.is_clean());
1781 result.roster.check_sane();
1782 }
1783};
1784
1785struct rename_target_plus_missing_root : public structural_conflict_helper
1786{
1787 node_id left_root_nid, right_root_nid;
1788
1789 virtual void setup()
1790 {
1791 left_root_nid = nis.next();
1792 right_root_nid = nis.next();
1793
1794 left_roster.drop_detached_node(left_roster.detach_node(split("")));
1795 safe_erase(left_markings, root_nid);
1796 make_dir(left_roster, left_markings, left_rid, left_rid, "", left_root_nid);
1797
1798 right_roster.drop_detached_node(right_roster.detach_node(split("")));
1799 safe_erase(right_markings, root_nid);
1800 make_dir(right_roster, right_markings, right_rid, right_rid, "", right_root_nid);
1801 }
1802 virtual void check()
1803 {
1804 I(!result.is_clean());
1805 rename_target_conflict const & c = idx(result.rename_target_conflicts, 0);
1806 I((c.nid1 == left_root_nid && c.nid2 == right_root_nid)
1807 || (c.nid1 == right_root_nid && c.nid2 == left_root_nid));
1808 I(c.parent_name == make_pair(the_null_node, the_null_component));
1809
1810 I(result.missing_root_dir);
1811
1812 // we can't just attach one of these as the root -- see the massive
1813 // comment on the old_locations member of roster_t, in roster.hh.
1814 result.roster.attach_node(result.roster.create_dir_node(nis), split(""));
1815 result.roster.attach_node(left_root_nid, split("totally_left_name"));
1816 result.roster.attach_node(right_root_nid, split("totally_right_name"));
1817 result.rename_target_conflicts.pop_back();
1818 result.missing_root_dir = false;
1819 I(result.is_clean());
1820 result.roster.check_sane();
1821 }
1822};
1823
1824UNIT_TEST(roster_merge, complex_structural_conflicts)
1825{
1826 {
1827 node_name_plus_rename_target t;
1828 t.test();
1829 }
1830 {
1831 node_name_plus_orphan t;
1832 t.test();
1833 }
1834 {
1835 node_name_plus_directory_loop t;
1836 t.test();
1837 }
1838 {
1839 node_name_plus_illegal_name t;
1840 t.test();
1841 }
1842 {
1843 node_name_plus_missing_root t;
1844 t.test();
1845 }
1846 {
1847 rename_target_plus_missing_root t;
1848 t.test();
1849 }
1850}
1851
1852#endif // BUILD_UNIT_TESTS
1853
1854// Local Variables:
1855// mode: C++
1856// fill-column: 76
1857// c-file-style: "gnu"
1858// indent-tabs-mode: nil
1859// End:
1860// 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