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 <boost/shared_ptr.hpp>
14
15#include "vocab.hh"
16#include "roster_merge.hh"
17#include "parallel_iter.hh"
18#include "safe_map.hh"
19
20using boost::shared_ptr;
21
22using std::make_pair;
23using std::ostringstream;
24using std::pair;
25using std::set;
26using std::string;
27
28template <> void
29dump(invalid_name_conflict const & conflict, string & out)
30{
31 ostringstream oss;
32 oss << "invalid_name_conflict on node: " << conflict.nid << " "
33 << "parent: " << conflict.parent_name.first << " "
34 << "basename: " << conflict.parent_name.second << "\n";
35 out = oss.str();
36}
37
38template <> void
39dump(directory_loop_conflict const & conflict, string & out)
40{
41 ostringstream oss;
42 oss << "directory_loop_conflict on node: " << conflict.nid << " "
43 << "parent: " << conflict.parent_name.first << " "
44 << "basename: " << conflict.parent_name.second << "\n";
45 out = oss.str();
46}
47
48template <> void
49dump(orphaned_node_conflict const & conflict, string & out)
50{
51 ostringstream oss;
52 oss << "orphaned_node_conflict on node: " << conflict.nid << " "
53 << "parent: " << conflict.parent_name.first << " "
54 << "basename: " << conflict.parent_name.second << "\n";
55 out = oss.str();
56}
57
58template <> void
59dump(multiple_name_conflict const & conflict, string & out)
60{
61 ostringstream oss;
62 oss << "multiple_name_conflict on node: " << conflict.nid << " "
63 << "left parent: " << conflict.left.first << " "
64 << "basename: " << conflict.left.second << " "
65 << "right parent: " << conflict.right.first << " "
66 << "basename: " << conflict.right.second << "\n";
67 out = oss.str();
68}
69
70template <> void
71dump(duplicate_name_conflict const & conflict, string & out)
72{
73 ostringstream oss;
74 oss << "duplicate_name_conflict between left node: " << conflict.left_nid << " "
75 << "and right node: " << conflict.right_nid << " "
76 << "parent: " << conflict.parent_name.first << " "
77 << "basename: " << conflict.parent_name.second << "\n";
78 out = oss.str();
79}
80
81template <> void
82dump(attribute_conflict const & conflict, string & out)
83{
84 ostringstream oss;
85 oss << "attribute_conflict on node: " << conflict.nid << " "
86 << "attr: '" << conflict.key << "' "
87 << "left: " << conflict.left.first << " '" << conflict.left.second << "' "
88 << "right: " << conflict.right.first << " '" << conflict.right.second << "'\n";
89 out = oss.str();
90}
91
92template <> void
93dump(file_content_conflict const & conflict, string & out)
94{
95 ostringstream oss;
96 oss << "file_content_conflict on node: " << conflict.nid << " "
97 << "left: " << conflict.left << " "
98 << "right: " << conflict.right << "\n";
99 out = oss.str();
100}
101
102bool
103roster_merge_result::is_clean() const
104{
105 return !has_non_content_conflicts()
106 && !has_content_conflicts();
107}
108
109bool
110roster_merge_result::has_content_conflicts() const
111{
112 return file_content_conflicts.size() > 0;
113}
114
115bool
116roster_merge_result::has_non_content_conflicts() const
117{
118 return missing_root_dir
119 || !invalid_name_conflicts.empty()
120 || !directory_loop_conflicts.empty()
121 || !orphaned_node_conflicts.empty()
122 || !multiple_name_conflicts.empty()
123 || !duplicate_name_conflicts.empty()
124 || !attribute_conflicts.empty();
125}
126static void
127dump_conflicts(roster_merge_result const & result, string & out)
128{
129 if (result.missing_root_dir)
130 out += (FL("missing_root_conflict: root directory has been removed\n")).str();
131
132 dump(result.invalid_name_conflicts, out);
133 dump(result.directory_loop_conflicts, out);
134
135 dump(result.orphaned_node_conflicts, out);
136 dump(result.multiple_name_conflicts, out);
137 dump(result.duplicate_name_conflicts, out);
138
139 dump(result.attribute_conflicts, out);
140 dump(result.file_content_conflicts, out);
141}
142
143template <> void
144dump(roster_merge_result const & result, string & out)
145{
146 dump_conflicts(result, out);
147
148 string roster_part;
149 dump(result.roster, roster_part);
150 out += "\n\n";
151 out += roster_part;
152}
153
154void
155roster_merge_result::log_conflicts() const
156{
157 string str;
158 dump_conflicts(*this, str);
159 L(FL("%s") % str);
160}
161
162namespace
163{
164 enum node_type { file_type, dir_type };
165
166 node_type
167 get_type(roster_t const & roster, node_id const nid)
168 {
169 node_t n = roster.get_node(nid);
170
171 if (is_file_t(n))
172 return file_type;
173 else if (is_dir_t(n))
174 return dir_type;
175 else
176 I(false);
177 }
178}
179
180void
181roster_merge_result::report_missing_root_conflicts(roster_t const & left_roster,
182 roster_t const & right_roster,
183 content_merge_adaptor & adaptor) const
184{
185 MM(left_roster);
186 MM(right_roster);
187
188 if (missing_root_dir)
189 {
190 node_id left_root, right_root;
191 left_root = left_roster.root()->self;
192 right_root = right_roster.root()->self;
193
194 // these must be different for this conflict to happen
195 I(left_root != right_root);
196
197 shared_ptr<roster_t const> left_lca_roster, right_lca_roster;
198 revision_id left_lca_rid, right_lca_rid;
199 file_path left_lca_name, right_lca_name;
200
201 adaptor.get_ancestral_roster(left_root, left_lca_rid,
202 left_lca_roster);
203 adaptor.get_ancestral_roster(right_root, right_lca_rid,
204 right_lca_roster);
205
206 left_lca_roster->get_name(left_root, left_lca_name);
207 right_lca_roster->get_name(right_root, right_lca_name);
208
209 node_id left_lca_root = left_lca_roster->root()->self;
210 node_id right_lca_root = right_lca_roster->root()->self;
211
212 P(F("conflict: missing root directory"));
213
214 if (left_root != left_lca_root && right_root == right_lca_root)
215 {
216 P(F("directory '%s' pivoted to root on the left") % left_lca_name);
217 if (!right_roster.has_node(left_root))
218 P(F("directory '%s' deleted on the right") % left_lca_name);
219 }
220 else if (left_root == left_lca_root && right_root != right_lca_root)
221 {
222 if (!left_roster.has_node(right_root))
223 P(F("directory '%s' deleted on the left") % right_lca_name);
224 P(F("directory '%s' pivoted to root on the right") % right_lca_name);
225 }
226 else if (left_root != left_lca_root && right_root != right_lca_root)
227 {
228 P(F("directory '%s' pivoted to root on the left") % left_lca_name);
229 if (!right_roster.has_node(left_root))
230 P(F("directory '%s' deleted on the right") % left_lca_name);
231
232 if (!left_roster.has_node(right_root))
233 P(F("directory '%s' deleted on the left") % right_lca_name);
234 P(F("directory '%s' pivoted to root on the right") % right_lca_name);
235 }
236 // else
237 // other conflicts can cause the root dir to be left detached
238 // for example, merging two independently created projects
239 // in these cases don't report anything about pivot_root
240 }
241}
242
243void
244roster_merge_result::report_invalid_name_conflicts(roster_t const & left_roster,
245 roster_t const & right_roster,
246 content_merge_adaptor & adaptor) const
247{
248 MM(left_roster);
249 MM(right_roster);
250
251 for (size_t i = 0; i < invalid_name_conflicts.size(); ++i)
252 {
253 invalid_name_conflict const & conflict = invalid_name_conflicts[i];
254 MM(conflict);
255
256 I(!roster.is_attached(conflict.nid));
257
258 shared_ptr<roster_t const> lca_roster, parent_lca_roster;
259 revision_id lca_rid, parent_lca_rid;
260 file_path lca_name, lca_parent_name;
261
262 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
263 lca_roster->get_name(conflict.nid, lca_name);
264 lca_roster->get_name(conflict.parent_name.first, lca_parent_name);
265
266 adaptor.get_ancestral_roster(conflict.parent_name.first,
267 parent_lca_rid, parent_lca_roster);
268
269 P(F("conflict: invalid name _MTN in root directory"));
270
271 if (left_roster.root()->self == conflict.parent_name.first)
272 {
273 P(F("'%s' pivoted to root on the left")
274 % lca_parent_name);
275
276 file_path right_name;
277 right_roster.get_name(conflict.nid, right_name);
278 if (parent_lca_roster->has_node(conflict.nid))
279 {
280 P(F("'%s' renamed to '%s' on the right")
281 % lca_name % right_name);
282 }
283 else
284 {
285 P(F("'%s' added in revision %s on the right")
286 % right_name % lca_rid);
287 }
288 }
289 else if (right_roster.root()->self == conflict.parent_name.first)
290 {
291 P(F("'%s' pivoted to root on the right")
292 % lca_parent_name);
293
294 file_path left_name;
295 left_roster.get_name(conflict.nid, left_name);
296 if (parent_lca_roster->has_node(conflict.nid))
297 {
298 P(F("'%s' renamed to '%s' on the left")
299 % lca_name % left_name);
300 }
301 else
302 {
303 P(F("'%s' added in revision %s on the left")
304 % left_name % lca_rid);
305 }
306 }
307 else
308 I(false);
309 }
310}
311
312void
313roster_merge_result::report_directory_loop_conflicts(roster_t const & left_roster,
314 roster_t const & right_roster,
315 content_merge_adaptor & adaptor) const
316{
317 MM(left_roster);
318 MM(right_roster);
319
320 for (size_t i = 0; i < directory_loop_conflicts.size(); ++i)
321 {
322 directory_loop_conflict const & conflict = directory_loop_conflicts[i];
323 MM(conflict);
324
325 I(!roster.is_attached(conflict.nid));
326
327 file_path left_name, right_name, left_parent_name, right_parent_name;
328
329 left_roster.get_name(conflict.nid, left_name);
330 right_roster.get_name(conflict.nid, right_name);
331
332 left_roster.get_name(conflict.parent_name.first, left_parent_name);
333 right_roster.get_name(conflict.parent_name.first, right_parent_name);
334
335 shared_ptr<roster_t const> lca_roster;
336 revision_id lca_rid;
337 file_path lca_name, lca_parent_name;
338
339 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
340 lca_roster->get_name(conflict.nid, lca_name);
341 lca_roster->get_name(conflict.parent_name.first, lca_parent_name);
342
343 P(F("conflict: directory loop created"));
344
345 if (left_name != lca_name)
346 P(F("'%s' renamed to '%s' on the left")
347 % lca_name % left_name);
348
349 if (right_name != lca_name)
350 P(F("'%s' renamed to '%s' on the right")
351 % lca_name % right_name);
352
353 if (left_parent_name != lca_parent_name)
354 P(F("'%s' renamed to '%s' on the left")
355 % lca_parent_name % left_parent_name);
356
357 if (right_parent_name != lca_parent_name)
358 P(F("'%s' renamed to '%s' on the right")
359 % lca_parent_name % right_parent_name);
360 }
361}
362
363void
364roster_merge_result::report_orphaned_node_conflicts(roster_t const & left_roster,
365 roster_t const & right_roster,
366 content_merge_adaptor & adaptor) const
367{
368 MM(left_roster);
369 MM(right_roster);
370
371 for (size_t i = 0; i < orphaned_node_conflicts.size(); ++i)
372 {
373 orphaned_node_conflict const & conflict = orphaned_node_conflicts[i];
374 MM(conflict);
375
376 I(!roster.is_attached(conflict.nid));
377
378 shared_ptr<roster_t const> lca_roster, parent_lca_roster;
379 revision_id lca_rid, parent_lca_rid;
380 file_path lca_name;
381
382 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
383 adaptor.get_ancestral_roster(conflict.parent_name.first,
384 parent_lca_rid, parent_lca_roster);
385
386 lca_roster->get_name(conflict.nid, lca_name);
387
388 node_type type = get_type(*lca_roster, conflict.nid);
389
390 if (type == file_type)
391 P(F("conflict: orphaned file '%s' from revision %s")
392 % lca_name % lca_rid);
393 else
394 P(F("conflict: orphaned directory '%s' from revision %s")
395 % lca_name % lca_rid);
396
397 if (left_roster.has_node(conflict.parent_name.first) &&
398 !right_roster.has_node(conflict.parent_name.first))
399 {
400 file_path orphan_name, parent_name;
401 left_roster.get_name(conflict.nid, orphan_name);
402 left_roster.get_name(conflict.parent_name.first, parent_name);
403
404 P(F("parent directory '%s' was deleted on the right")
405 % parent_name);
406
407 if (parent_lca_roster->has_node(conflict.nid))
408 {
409 if (type == file_type)
410 P(F("file '%s' was renamed from '%s' on the left")
411 % orphan_name % lca_name);
412 else
413 P(F("directory '%s' was renamed from '%s' on the left")
414 % orphan_name % lca_name);
415 }
416 else
417 {
418 if (type == file_type)
419 P(F("file '%s' was added on the left")
420 % orphan_name);
421 else
422 P(F("directory '%s' was added on the left")
423 % orphan_name);
424
425 }
426 }
427 else if (!left_roster.has_node(conflict.parent_name.first) &&
428 right_roster.has_node(conflict.parent_name.first))
429 {
430 file_path orphan_name, parent_name;
431 right_roster.get_name(conflict.nid, orphan_name);
432 right_roster.get_name(conflict.parent_name.first, parent_name);
433
434 P(F("parent directory '%s' was deleted on the left")
435 % parent_name);
436
437 if (parent_lca_roster->has_node(conflict.nid))
438 {
439 if (type == file_type)
440 P(F("file '%s' was renamed from '%s' on the right")
441 % orphan_name % lca_name);
442 else
443 P(F("directory '%s' was renamed from '%s' on the right")
444 % orphan_name % lca_name);
445 }
446 else
447 {
448 if (type == file_type)
449 P(F("file '%s' was added on the right")
450 % orphan_name);
451 else
452 P(F("directory '%s' was added on the right")
453 % orphan_name);
454 }
455 }
456 else
457 I(false);
458 }
459}
460
461void
462roster_merge_result::report_multiple_name_conflicts(roster_t const & left_roster,
463 roster_t const & right_roster,
464 content_merge_adaptor & adaptor) const
465{
466 MM(left_roster);
467 MM(right_roster);
468
469 for (size_t i = 0; i < multiple_name_conflicts.size(); ++i)
470 {
471 multiple_name_conflict const & conflict = multiple_name_conflicts[i];
472 MM(conflict);
473
474 I(!roster.is_attached(conflict.nid));
475
476 file_path left_name, right_name;
477
478 left_roster.get_name(conflict.nid, left_name);
479 right_roster.get_name(conflict.nid, right_name);
480
481 shared_ptr<roster_t const> lca_roster;
482 revision_id lca_rid;
483 file_path lca_name;
484
485 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
486 lca_roster->get_name(conflict.nid, lca_name);
487
488 node_type type = get_type(*lca_roster, conflict.nid);
489
490 if (type == file_type)
491 P(F("conflict: multiple names for file '%s' from revision %s")
492 % lca_name % lca_rid);
493 else
494 P(F("conflict: multiple names for directory '%s' from revision %s")
495 % lca_name % lca_rid);
496
497 P(F("renamed to '%s' on the left") % left_name);
498 P(F("renamed to '%s' on the right") % right_name);
499 }
500}
501
502void
503roster_merge_result::report_duplicate_name_conflicts(roster_t const & left_roster,
504 roster_t const & right_roster,
505 content_merge_adaptor & adaptor) const
506{
507 MM(left_roster);
508 MM(right_roster);
509
510 for (size_t i = 0; i < duplicate_name_conflicts.size(); ++i)
511 {
512 duplicate_name_conflict const & conflict = duplicate_name_conflicts[i];
513 MM(conflict);
514
515 node_id left_nid, right_nid;
516
517 left_nid = conflict.left_nid;
518 right_nid = conflict.right_nid;
519
520 I(!roster.is_attached(left_nid));
521 I(!roster.is_attached(right_nid));
522
523 file_path left_name, right_name;
524
525 left_roster.get_name(left_nid, left_name);
526 right_roster.get_name(right_nid, right_name);
527
528 I(left_name == right_name);
529
530 shared_ptr<roster_t const> left_lca_roster, right_lca_roster;
531 revision_id left_lca_rid, right_lca_rid;
532
533 adaptor.get_ancestral_roster(left_nid, left_lca_rid, left_lca_roster);
534 adaptor.get_ancestral_roster(right_nid, right_lca_rid, right_lca_roster);
535
536 P(F("conflict: duplicate name '%s'") % left_name);
537
538 node_type left_type = get_type(left_roster, left_nid);
539 node_type right_type = get_type(right_roster, right_nid);
540
541 if (!left_lca_roster->has_node(right_nid) &&
542 !right_lca_roster->has_node(left_nid))
543 {
544 if (left_type == file_type)
545 P(F("added as a new file on the left"));
546 else
547 P(F("added as a new directory on the left"));
548
549 if (right_type == file_type)
550 P(F("added as a new file on the right"));
551 else
552 P(F("added as a new directory on the right"));
553 }
554 else if (!left_lca_roster->has_node(right_nid) &&
555 right_lca_roster->has_node(left_nid))
556 {
557 file_path left_lca_name;
558 left_lca_roster->get_name(left_nid, left_lca_name);
559
560 if (left_type == file_type)
561 P(F("renamed from file '%s' on the left") % left_lca_name);
562 else
563 P(F("renamed from directory '%s' on the left") % left_lca_name);
564
565 if (right_type == file_type)
566 P(F("added as a new file on the right"));
567 else
568 P(F("added as a new directory on the right"));
569 }
570 else if (left_lca_roster->has_node(right_nid) &&
571 !right_lca_roster->has_node(left_nid))
572 {
573 file_path right_lca_name;
574 right_lca_roster->get_name(right_nid, right_lca_name);
575
576 if (left_type == file_type)
577 P(F("added as a new file on the left"));
578 else
579 P(F("added as a new directory on the left"));
580
581 if (right_type == file_type)
582 P(F("renamed from file '%s' on the right") % right_lca_name);
583 else
584 P(F("renamed from directory '%s' on the right") % right_lca_name);
585 }
586 else if (left_lca_roster->has_node(right_nid) &&
587 right_lca_roster->has_node(left_nid))
588 {
589 file_path left_lca_name, right_lca_name;
590 left_lca_roster->get_name(left_nid, left_lca_name);
591 right_lca_roster->get_name(right_nid, right_lca_name);
592
593 if (left_type == file_type)
594 P(F("renamed from file '%s' on the left") % left_lca_name);
595 else
596 P(F("renamed from directory '%s' on the left") % left_lca_name);
597
598 if (right_type == file_type)
599 P(F("renamed from file '%s' on the right") % right_lca_name);
600 else
601 P(F("renamed from directory '%s' on the right") % right_lca_name);
602 }
603 else
604 I(false);
605 }
606}
607
608void
609roster_merge_result::report_attribute_conflicts(roster_t const & left_roster,
610 roster_t const & right_roster,
611 content_merge_adaptor & adaptor) const
612{
613 MM(left_roster);
614 MM(right_roster);
615
616 for (size_t i = 0; i < attribute_conflicts.size(); ++i)
617 {
618 attribute_conflict const & conflict = attribute_conflicts[i];
619 MM(conflict);
620
621 node_type type = get_type(roster, conflict.nid);
622
623 if (roster.is_attached(conflict.nid))
624 {
625 file_path name;
626 roster.get_name(conflict.nid, name);
627
628 if (type == file_type)
629 P(F("conflict: multiple values for attribute '%s' on file '%s'")
630 % conflict.key % name);
631 else
632 P(F("conflict: multiple values for attribute '%s' on directory '%s'")
633 % conflict.key % name);
634
635 if (conflict.left.first)
636 P(F("set to '%s' on the left") % conflict.left.second);
637 else
638 P(F("deleted on the left"));
639
640 if (conflict.right.first)
641 P(F("set to '%s' on the right") % conflict.right.second);
642 else
643 P(F("deleted on the right"));
644 }
645 else
646 {
647 // this node isn't attached in the merged roster and there
648 // isn't really a good name for it so report both the left
649 // and right names using a slightly different format
650
651 file_path left_name, right_name;
652 left_roster.get_name(conflict.nid, left_name);
653 right_roster.get_name(conflict.nid, right_name);
654
655 shared_ptr<roster_t const> lca_roster;
656 revision_id lca_rid;
657 file_path lca_name;
658
659 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
660 lca_roster->get_name(conflict.nid, lca_name);
661
662 if (type == file_type)
663 P(F("conflict: multiple values for attribute '%s' on file '%s' from revision %s")
664 % conflict.key % lca_name % lca_rid);
665 else
666 P(F("conflict: multiple values for attribute '%s' on directory '%s' from revision %s")
667 % conflict.key % lca_name % lca_rid);
668
669 if (conflict.left.first)
670 {
671 if (type == file_type)
672 P(F("set to '%s' on left file '%s'")
673 % conflict.left.second % left_name);
674 else
675 P(F("set to '%s' on left directory '%s'")
676 % conflict.left.second % left_name);
677 }
678 else
679 {
680 if (type == file_type)
681 P(F("deleted from left file '%s'")
682 % left_name);
683 else
684 P(F("deleted from left directory '%s'")
685 % left_name);
686 }
687
688 if (conflict.right.first)
689 {
690 if (type == file_type)
691 P(F("set to '%s' on right file '%s'")
692 % conflict.right.second % right_name);
693 else
694 P(F("set to '%s' on right directory '%s'")
695 % conflict.right.second % right_name);
696 }
697 else
698 {
699 if (type == file_type)
700 P(F("deleted from right file '%s'")
701 % right_name);
702 else
703 P(F("deleted from right directory '%s'")
704 % right_name);
705 }
706 }
707 }
708}
709
710void
711roster_merge_result::report_file_content_conflicts(roster_t const & left_roster,
712 roster_t const & right_roster,
713 content_merge_adaptor & adaptor) const
714{
715 MM(left_roster);
716 MM(right_roster);
717
718 for (size_t i = 0; i < file_content_conflicts.size(); ++i)
719 {
720 file_content_conflict const & conflict = file_content_conflicts[i];
721 MM(conflict);
722
723 if (roster.is_attached(conflict.nid))
724 {
725 file_path name;
726 roster.get_name(conflict.nid, name);
727
728 P(F("conflict: content conflict on file '%s'")
729 % name);
730 P(F("content hash is %s on the left") % conflict.left);
731 P(F("content hash is %s on the right") % conflict.right);
732 }
733 else
734 {
735 // this node isn't attached in the merged roster and there
736 // isn't really a good name for it so report both the left
737 // and right names using a slightly different format
738
739 file_path left_name, right_name;
740 left_roster.get_name(conflict.nid, left_name);
741 right_roster.get_name(conflict.nid, right_name);
742
743 shared_ptr<roster_t const> lca_roster;
744 revision_id lca_rid;
745 file_path lca_name;
746
747 adaptor.get_ancestral_roster(conflict.nid, lca_rid, lca_roster);
748 lca_roster->get_name(conflict.nid, lca_name);
749
750 P(F("conflict: content conflict on file '%s' from revision %s")
751 % lca_name % lca_rid);
752 P(F("content hash is %s on the left in file '%s'")
753 % conflict.left % left_name);
754 P(F("content hash is %s on the right in file '%s'")
755 % conflict.right % right_name);
756 }
757 }
758}
759
760void
761roster_merge_result::clear()
762{
763 missing_root_dir = false;
764 invalid_name_conflicts.clear();
765 directory_loop_conflicts.clear();
766
767 orphaned_node_conflicts.clear();
768 multiple_name_conflicts.clear();
769 duplicate_name_conflicts.clear();
770
771 attribute_conflicts.clear();
772 file_content_conflicts.clear();
773
774 roster = roster_t();
775}
776
777namespace
778{
779 // a wins if *(b) > a. Which is to say that all members of b_marks are
780 // ancestors of a. But all members of b_marks are ancestors of the
781 // _b_, so the previous statement is the same as saying that _no_
782 // members of b_marks is an _uncommon_ ancestor of _b_.
783 bool
784 a_wins(set<revision_id> const & b_marks,
785 set<revision_id> const & b_uncommon_ancestors)
786 {
787 for (set<revision_id>::const_iterator i = b_marks.begin();
788 i != b_marks.end(); ++i)
789 if (b_uncommon_ancestors.find(*i) != b_uncommon_ancestors.end())
790 return false;
791 return true;
792 }
793
794 // returns true if merge was successful ('result' is valid), false otherwise
795 // ('conflict_descriptor' is valid).
796 template <typename T, typename C> bool
797 merge_scalar(T const & left,
798 set<revision_id> const & left_marks,
799 set<revision_id> const & left_uncommon_ancestors,
800 T const & right,
801 set<revision_id> const & right_marks,
802 set<revision_id> const & right_uncommon_ancestors,
803 T & result,
804 C & conflict_descriptor)
805 {
806 if (left == right)
807 {
808 result = left;
809 return true;
810 }
811 MM(left_marks);
812 MM(left_uncommon_ancestors);
813 MM(right_marks);
814 MM(right_uncommon_ancestors);
815 bool left_wins = a_wins(right_marks, right_uncommon_ancestors);
816 bool right_wins = a_wins(left_marks, left_uncommon_ancestors);
817 // two bools means 4 cases:
818 // left_wins && right_wins
819 // this is ambiguous clean merge, which is theoretically impossible.
820 I(!(left_wins && right_wins));
821 // left_wins && !right_wins
822 if (left_wins && !right_wins)
823 {
824 result = left;
825 return true;
826 }
827 // !left_wins && right_wins
828 if (!left_wins && right_wins)
829 {
830 result = right;
831 return true;
832 }
833 // !left_wins && !right_wins
834 if (!left_wins && !right_wins)
835 {
836 conflict_descriptor.left = left;
837 conflict_descriptor.right = right;
838 return false;
839 }
840 I(false);
841 }
842
843 inline void
844 create_node_for(node_t const & n, roster_t & new_roster)
845 {
846 if (is_dir_t(n))
847 new_roster.create_dir_node(n->self);
848 else if (is_file_t(n))
849 new_roster.create_file_node(file_id(), n->self);
850 else
851 I(false);
852 }
853
854 inline void
855 insert_if_unborn(node_t const & n,
856 marking_map const & markings,
857 set<revision_id> const & uncommon_ancestors,
858 roster_t const & parent_roster,
859 roster_t & new_roster)
860 {
861 revision_id const & birth = safe_get(markings, n->self).birth_revision;
862 if (uncommon_ancestors.find(birth) != uncommon_ancestors.end())
863 create_node_for(n, new_roster);
864 else
865 {
866 // In this branch we are NOT inserting the node into the new roster as it
867 // has been deleted from the other side of the merge.
868 // In this case, output a warning if there are changes to the file on the
869 // side of the merge where it still exists.
870 set<revision_id> const & content_marks = safe_get(markings, n->self).file_content;
871 bool found_one_ignored_content = false;
872 for (set<revision_id>::const_iterator it = content_marks.begin(); it != content_marks.end(); it++)
873 {
874 if (uncommon_ancestors.find(*it) != uncommon_ancestors.end())
875 {
876 if (!found_one_ignored_content)
877 {
878 file_path fp;
879 parent_roster.get_name(n->self, fp);
880 W(F("Content changes to the file '%s'\n"
881 "will be ignored during this merge as the file has been\n"
882 "removed on one side of the merge. Affected revisions include:") % fp);
883 }
884 found_one_ignored_content = true;
885 W(F("Revision: %s") % *it);
886 }
887 }
888 }
889 }
890
891 bool
892 would_make_dir_loop(roster_t const & r, node_id nid, node_id parent)
893 {
894 // parent may not be fully attached yet; that's okay. that just means
895 // we'll run into a node with a null parent somewhere before we hit the
896 // actual root; whether we hit the actual root or not, hitting a node
897 // with a null parent will tell us that this particular attachment won't
898 // create a loop.
899 for (node_id curr = parent; !null_node(curr); curr = r.get_node(curr)->parent)
900 {
901 if (curr == nid)
902 return true;
903 }
904 return false;
905 }
906
907 enum side_t { left_side, right_side };
908
909 void
910 assign_name(roster_merge_result & result, node_id nid,
911 node_id parent, path_component name, side_t side)
912 {
913 // this function is reponsible for detecting structural conflicts. by the
914 // time we've gotten here, we have a node that's unambiguously decided on
915 // a name; but it might be that that name does not exist (because the
916 // parent dir is gone), or that it's already taken (by another node), or
917 // that putting this node there would create a directory loop. In all
918 // such cases, rather than actually attach the node, we write a conflict
919 // structure and leave it detached.
920
921 // the root dir is somewhat special. it can't be orphaned, and it can't
922 // make a dir loop. it can, however, have a name collision.
923 if (null_node(parent))
924 {
925 I(name.empty());
926 if (result.roster.has_root())
927 {
928 // see comments below about name collisions.
929 duplicate_name_conflict c;
930 // some other node has already been attached at the root location
931 // so write a conflict structure with this node on the indicated
932 // side of the merge and the attached node on the other side of
933 // the merge. detach the previously attached node and leave both
934 // conflicted nodes detached.
935 switch (side)
936 {
937 case left_side:
938 c.left_nid = nid;
939 c.right_nid = result.roster.root()->self;
940 break;
941 case right_side:
942 c.left_nid = result.roster.root()->self;
943 c.right_nid = nid;
944 break;
945 }
946 c.parent_name = make_pair(parent, name);
947 result.roster.detach_node(file_path());
948 result.duplicate_name_conflicts.push_back(c);
949 return;
950 }
951 }
952 else
953 {
954 // orphan:
955 if (!result.roster.has_node(parent))
956 {
957 orphaned_node_conflict c;
958 c.nid = nid;
959 c.parent_name = make_pair(parent, name);
960 result.orphaned_node_conflicts.push_back(c);
961 return;
962 }
963
964 dir_t p = downcast_to_dir_t(result.roster.get_node(parent));
965
966 // duplicate name conflict:
967 // see the comment in roster_merge.hh for the analysis showing that at
968 // most two nodes can participate in a duplicate name conflict. this code
969 // exploits that; after this code runs, there will be no node at the given
970 // location in the tree, which means that in principle, if there were a
971 // third node that _also_ wanted to go here, when we got around to
972 // attaching it we'd have no way to realize it should be a conflict. but
973 // that never happens, so we don't have to keep a lookaside set of
974 // "poisoned locations" or anything.
975 if (p->has_child(name))
976 {
977 duplicate_name_conflict c;
978 // some other node has already been attached at the named location
979 // so write a conflict structure with this node on the indicated
980 // side of the merge and the attached node on the other side of
981 // the merge. detach the previously attached node and leave both
982 // conflicted nodes detached.
983 switch (side)
984 {
985 case left_side:
986 c.left_nid = nid;
987 c.right_nid = p->get_child(name)->self;
988 break;
989 case right_side:
990 c.left_nid = p->get_child(name)->self;
991 c.right_nid = nid;
992 break;
993 }
994 c.parent_name = make_pair(parent, name);
995 p->detach_child(name);
996 result.duplicate_name_conflicts.push_back(c);
997 return;
998 }
999
1000 if (would_make_dir_loop(result.roster, nid, parent))
1001 {
1002 directory_loop_conflict c;
1003 c.nid = nid;
1004 c.parent_name = make_pair(parent, name);
1005 result.directory_loop_conflicts.push_back(c);
1006 return;
1007 }
1008 }
1009 // hey, we actually made it. attach the node!
1010 result.roster.attach_node(nid, parent, name);
1011 }
1012
1013 void
1014 copy_node_forward(roster_merge_result & result, node_t const & n,
1015 node_t const & old_n, side_t const & side)
1016 {
1017 I(n->self == old_n->self);
1018 n->attrs = old_n->attrs;
1019 if (is_file_t(n))
1020 downcast_to_file_t(n)->content = downcast_to_file_t(old_n)->content;
1021 assign_name(result, n->self, old_n->parent, old_n->name, side);
1022 }
1023
1024} // end anonymous namespace
1025
1026void
1027roster_merge(roster_t const & left_parent,
1028 marking_map const & left_markings,
1029 set<revision_id> const & left_uncommon_ancestors,
1030 roster_t const & right_parent,
1031 marking_map const & right_markings,
1032 set<revision_id> const & right_uncommon_ancestors,
1033 roster_merge_result & result)
1034{
1035 L(FL("Performing a roster_merge"));
1036
1037 result.clear();
1038 MM(left_parent);
1039 MM(left_markings);
1040 MM(right_parent);
1041 MM(right_markings);
1042 MM(result);
1043
1044 // First handle lifecycles, by die-die-die merge -- our result will contain
1045 // everything that is alive in both parents, or alive in one and unborn in
1046 // the other, exactly.
1047 {
1048 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
1049 while (i.next())
1050 {
1051 switch (i.state())
1052 {
1053 case parallel::invalid:
1054 I(false);
1055
1056 case parallel::in_left:
1057 insert_if_unborn(i.left_data(),
1058 left_markings, left_uncommon_ancestors, left_parent,
1059 result.roster);
1060 break;
1061
1062 case parallel::in_right:
1063 insert_if_unborn(i.right_data(),
1064 right_markings, right_uncommon_ancestors, right_parent,
1065 result.roster);
1066 break;
1067
1068 case parallel::in_both:
1069 create_node_for(i.left_data(), result.roster);
1070 break;
1071 }
1072 }
1073 }
1074
1075 // okay, our roster now contains a bunch of empty, detached nodes. fill
1076 // them in one at a time with *-merge.
1077 {
1078 node_map::const_iterator left_i, right_i;
1079 parallel::iter<node_map> i(left_parent.all_nodes(), right_parent.all_nodes());
1080 node_map::const_iterator new_i = result.roster.all_nodes().begin();
1081 marking_map::const_iterator left_mi = left_markings.begin();
1082 marking_map::const_iterator right_mi = right_markings.begin();
1083 while (i.next())
1084 {
1085 switch (i.state())
1086 {
1087 case parallel::invalid:
1088 I(false);
1089
1090 case parallel::in_left:
1091 {
1092 node_t const & left_n = i.left_data();
1093 // we skip nodes that aren't in the result roster (were
1094 // deleted in the lifecycles step above)
1095 if (result.roster.has_node(left_n->self))
1096 {
1097 // attach this node from the left roster. this may cause
1098 // a name collision with the previously attached node from
1099 // the other side of the merge.
1100 copy_node_forward(result, new_i->second, left_n, left_side);
1101 ++new_i;
1102 }
1103 ++left_mi;
1104 break;
1105 }
1106
1107 case parallel::in_right:
1108 {
1109 node_t const & right_n = i.right_data();
1110 // we skip nodes that aren't in the result roster
1111 if (result.roster.has_node(right_n->self))
1112 {
1113 // attach this node from the right roster. this may cause
1114 // a name collision with the previously attached node from
1115 // the other side of the merge.
1116 copy_node_forward(result, new_i->second, right_n, right_side);
1117 ++new_i;
1118 }
1119 ++right_mi;
1120 break;
1121 }
1122
1123 case parallel::in_both:
1124 {
1125 I(new_i->first == i.left_key());
1126 I(left_mi->first == i.left_key());
1127 I(right_mi->first == i.right_key());
1128 node_t const & left_n = i.left_data();
1129 marking_t const & left_marking = left_mi->second;
1130 node_t const & right_n = i.right_data();
1131 marking_t const & right_marking = right_mi->second;
1132 node_t const & new_n = new_i->second;
1133 // merge name
1134 {
1135 pair<node_id, path_component> left_name, right_name, new_name;
1136 multiple_name_conflict conflict(new_n->self);
1137 left_name = make_pair(left_n->parent, left_n->name);
1138 right_name = make_pair(right_n->parent, right_n->name);
1139 if (merge_scalar(left_name,
1140 left_marking.parent_name,
1141 left_uncommon_ancestors,
1142 right_name,
1143 right_marking.parent_name,
1144 right_uncommon_ancestors,
1145 new_name, conflict))
1146 {
1147 side_t winning_side;
1148
1149 if (new_name == left_name)
1150 winning_side = left_side;
1151 else if (new_name == right_name)
1152 winning_side = right_side;
1153 else
1154 I(false);
1155
1156 // attach this node from the winning side of the merge. if
1157 // there is a name collision the previously attached node
1158 // (which is blocking this one) must come from the other
1159 // side of the merge.
1160 assign_name(result, new_n->self,
1161 new_name.first, new_name.second, winning_side);
1162
1163 }
1164 else
1165 {
1166 // unsuccessful merge; leave node detached and save
1167 // conflict object
1168 result.multiple_name_conflicts.push_back(conflict);
1169 }
1170 }
1171 // if a file, merge content
1172 if (is_file_t(new_n))
1173 {
1174 file_content_conflict conflict(new_n->self);
1175 if (merge_scalar(downcast_to_file_t(left_n)->content,
1176 left_marking.file_content,
1177 left_uncommon_ancestors,
1178 downcast_to_file_t(right_n)->content,
1179 right_marking.file_content,
1180 right_uncommon_ancestors,
1181 downcast_to_file_t(new_n)->content,
1182 conflict))
1183 {
1184 // successful merge
1185 }
1186 else
1187 {
1188 downcast_to_file_t(new_n)->content = file_id();
1189 result.file_content_conflicts.push_back(conflict);
1190 }
1191 }
1192 // merge attributes
1193 {
1194 full_attr_map_t::const_iterator left_ai = left_n->attrs.begin();
1195 full_attr_map_t::const_iterator right_ai = right_n->attrs.begin();
1196 parallel::iter<full_attr_map_t> attr_i(left_n->attrs,
1197 right_n->attrs);
1198 while(attr_i.next())
1199 {
1200 switch (attr_i.state())
1201 {
1202 case parallel::invalid:
1203 I(false);
1204 case parallel::in_left:
1205 safe_insert(new_n->attrs, attr_i.left_value());
1206 break;
1207 case parallel::in_right:
1208 safe_insert(new_n->attrs, attr_i.right_value());
1209 break;
1210 case parallel::in_both:
1211 pair<bool, attr_value> new_value;
1212 attribute_conflict conflict(new_n->self);
1213 conflict.key = attr_i.left_key();
1214 I(conflict.key == attr_i.right_key());
1215 if (merge_scalar(attr_i.left_data(),
1216 safe_get(left_marking.attrs,
1217 attr_i.left_key()),
1218 left_uncommon_ancestors,
1219 attr_i.right_data(),
1220 safe_get(right_marking.attrs,
1221 attr_i.right_key()),
1222 right_uncommon_ancestors,
1223 new_value,
1224 conflict))
1225 {
1226 // successful merge
1227 safe_insert(new_n->attrs,
1228 make_pair(attr_i.left_key(),
1229 new_value));
1230 }
1231 else
1232 {
1233 // unsuccessful merge
1234 // leave out the attr entry entirely, and save the
1235 // conflict
1236 result.attribute_conflicts.push_back(conflict);
1237 }
1238 break;
1239 }
1240
1241 }
1242 }
1243 }
1244 ++left_mi;
1245 ++right_mi;
1246 ++new_i;
1247 break;
1248 }
1249 }
1250 I(left_mi == left_markings.end());
1251 I(right_mi == right_markings.end());
1252 I(new_i == result.roster.all_nodes().end());
1253 }
1254
1255 // now check for the possible global problems
1256 if (!result.roster.has_root())
1257 result.missing_root_dir = true;
1258 else
1259 {
1260 // we can't have an illegal _MTN dir unless we have a root node in the
1261 // first place...
1262 dir_t result_root = result.roster.root();
1263
1264 if (result_root->has_child(bookkeeping_root_component))
1265 {
1266 invalid_name_conflict conflict;
1267 node_t n = result_root->get_child(bookkeeping_root_component);
1268 conflict.nid = n->self;
1269 conflict.parent_name.first = n->parent;
1270 conflict.parent_name.second = n->name;
1271 I(n->name == bookkeeping_root_component);
1272
1273 result.roster.detach_node(n->self);
1274 result.invalid_name_conflicts.push_back(conflict);
1275 }
1276 }
1277}
1278
1279#ifdef BUILD_UNIT_TESTS
1280#include "unit_tests.hh"
1281
1282#include "roster_delta.hh"
1283
1284// cases for testing:
1285//
1286// (DONE:)
1287//
1288// lifecycle, file and dir
1289// alive in both
1290// alive in one and unborn in other (left vs. right)
1291// alive in one and dead in other (left vs. right)
1292//
1293// mark merge:
1294// same in both, same mark
1295// same in both, diff marks
1296// different, left wins with 1 mark
1297// different, right wins with 1 mark
1298// different, conflict with 1 mark
1299// different, left wins with 2 marks
1300// different, right wins with 2 marks
1301// different, conflict with 1 mark winning, 1 mark losing
1302// different, conflict with 2 marks both conflicting
1303//
1304// for:
1305// node name and parent, file and dir
1306// node attr, file and dir
1307// file content
1308//
1309// attr lifecycle:
1310// seen in both -->mark merge cases, above
1311// live in one and unseen in other -->live
1312// dead in one and unseen in other -->dead
1313//
1314// two diff nodes with same name
1315// directory loops
1316// orphans
1317// illegal node ("_MTN")
1318// missing root dir
1319//
1320// (NEEDED:)
1321//
1322// interactions:
1323// in-node name conflict prevents other problems:
1324// in-node name conflict + possible between-node name conflict
1325// a vs. b, plus a, b, exist in result
1326// left: 1: a
1327// 2: b
1328// right: 1: b
1329// 3: a
1330// in-node name conflict + both possible names orphaned
1331// a/foo vs. b/foo conflict, + a, b exist in parents but deleted in
1332// children
1333// left: 1: a
1334// 2: a/foo
1335// right:
1336// 3: b
1337// 2: b/foo
1338// in-node name conflict + directory loop conflict
1339// a/bottom vs. b/bottom, with a and b both moved inside it
1340// in-node name conflict + one name illegal
1341// _MTN vs. foo
1342// in-node name conflict causes other problems:
1343// in-node name conflict + causes missing root dir
1344// "" vs. foo and bar vs. ""
1345// between-node name conflict prevents other problems:
1346// between-node name conflict + both nodes orphaned
1347// this is not possible
1348// between-node name conflict + both nodes cause loop
1349// this is not possible
1350// between-node name conflict + both nodes illegal
1351// two nodes that both merge to _MTN
1352// this is not possible
1353// between-node name conflict causes other problems:
1354// between-node name conflict + causes missing root dir
1355// two nodes that both want ""
1356
1357typedef enum { scalar_a, scalar_b, scalar_conflict } scalar_val;
1358
1359template <> void
1360dump(scalar_val const & v, string & out)
1361{
1362 switch (v)
1363 {
1364 case scalar_a:
1365 out = "scalar_a";
1366 break;
1367 case scalar_b:
1368 out = "scalar_b";
1369 break;
1370 case scalar_conflict:
1371 out = "scalar_conflict";
1372 break;
1373 }
1374}
1375
1376void string_to_set(string const & from, set<revision_id> & to)
1377{
1378 to.clear();
1379 for (string::const_iterator i = from.begin(); i != from.end(); ++i)
1380 {
1381 string rid_str(40, *i);
1382 to.insert(revision_id(rid_str));
1383 }
1384}
1385
1386
1387template <typename S> void
1388test_a_scalar_merge_impl(scalar_val left_val, string const & left_marks_str,
1389 string const & left_uncommon_str,
1390 scalar_val right_val, string const & right_marks_str,
1391 string const & right_uncommon_str,
1392 scalar_val expected_outcome)
1393{
1394 MM(left_val);
1395 MM(left_marks_str);
1396 MM(left_uncommon_str);
1397 MM(right_val);
1398 MM(right_marks_str);
1399 MM(right_uncommon_str);
1400 MM(expected_outcome);
1401
1402 S scalar;
1403 roster_t left_parent, right_parent;
1404 marking_map left_markings, right_markings;
1405 set<revision_id> left_uncommon_ancestors, right_uncommon_ancestors;
1406 roster_merge_result result;
1407
1408 set<revision_id> left_marks, right_marks;
1409
1410 MM(left_parent);
1411 MM(right_parent);
1412 MM(left_markings);
1413 MM(right_markings);
1414 MM(left_uncommon_ancestors);
1415 MM(right_uncommon_ancestors);
1416 MM(left_marks);
1417 MM(right_marks);
1418 MM(result);
1419
1420 string_to_set(left_marks_str, left_marks);
1421 scalar.setup_parent(left_val, left_marks, left_parent, left_markings);
1422 string_to_set(right_marks_str, right_marks);
1423 scalar.setup_parent(right_val, right_marks, right_parent, right_markings);
1424
1425 string_to_set(left_uncommon_str, left_uncommon_ancestors);
1426 string_to_set(right_uncommon_str, right_uncommon_ancestors);
1427
1428 roster_merge(left_parent, left_markings, left_uncommon_ancestors,
1429 right_parent, right_markings, right_uncommon_ancestors,
1430 result);
1431
1432 // go ahead and check the roster_delta code too, while we're at it...
1433 test_roster_delta_on(left_parent, left_markings, right_parent, right_markings);
1434
1435 scalar.check_result(left_val, right_val, result, expected_outcome);
1436}
1437
1438static const revision_id root_rid = revision_id(string("0000000000000000000000000000000000000000"));
1439static const file_id arbitrary_file = file_id(string("0000000000000000000000000000000000000000"));
1440
1441struct base_scalar
1442{
1443 testing_node_id_source nis;
1444 node_id root_nid;
1445 node_id thing_nid;
1446 base_scalar() : root_nid(nis.next()), thing_nid(nis.next())
1447 {}
1448
1449 void
1450 make_dir(char const * name, node_id nid, roster_t & r, marking_map & markings)
1451 {
1452 r.create_dir_node(nid);
1453 r.attach_node(nid, file_path_internal(name));
1454 marking_t marking;
1455 marking.birth_revision = root_rid;
1456 marking.parent_name.insert(root_rid);
1457 safe_insert(markings, make_pair(nid, marking));
1458 }
1459
1460 void
1461 make_file(char const * name, node_id nid, roster_t & r, marking_map & markings)
1462 {
1463 r.create_file_node(arbitrary_file, nid);
1464 r.attach_node(nid, file_path_internal(name));
1465 marking_t marking;
1466 marking.birth_revision = root_rid;
1467 marking.parent_name.insert(root_rid);
1468 marking.file_content.insert(root_rid);
1469 safe_insert(markings, make_pair(nid, marking));
1470 }
1471
1472 void
1473 make_root(roster_t & r, marking_map & markings)
1474 {
1475 make_dir("", root_nid, r, markings);
1476 }
1477};
1478
1479struct file_scalar : public virtual base_scalar
1480{
1481 file_path thing_name;
1482 file_scalar() : thing_name(file_path_internal("thing"))
1483 {}
1484
1485 void
1486 make_thing(roster_t & r, marking_map & markings)
1487 {
1488 make_root(r, markings);
1489 make_file("thing", thing_nid, r, markings);
1490 }
1491};
1492
1493struct dir_scalar : public virtual base_scalar
1494{
1495 file_path thing_name;
1496 dir_scalar() : thing_name(file_path_internal("thing"))
1497 {}
1498
1499 void
1500 make_thing(roster_t & r, marking_map & markings)
1501 {
1502 make_root(r, markings);
1503 make_dir("thing", thing_nid, r, markings);
1504 }
1505};
1506
1507struct name_shared_stuff : public virtual base_scalar
1508{
1509 virtual file_path path_for(scalar_val val) = 0;
1510 path_component pc_for(scalar_val val)
1511 {
1512 return path_for(val).basename();
1513 }
1514 virtual node_id parent_for(scalar_val val) = 0;
1515
1516 void
1517 check_result(scalar_val left_val, scalar_val right_val,
1518 // NB result is writeable -- we can scribble on it
1519 roster_merge_result & result, scalar_val expected_val)
1520 {
1521 switch (expected_val)
1522 {
1523 case scalar_a: case scalar_b:
1524 {
1525 file_path fp;
1526 result.roster.get_name(thing_nid, fp);
1527 I(fp == path_for(expected_val));
1528 }
1529 break;
1530 case scalar_conflict:
1531 multiple_name_conflict const & c = idx(result.multiple_name_conflicts, 0);
1532 I(c.nid == thing_nid);
1533 I(c.left == make_pair(parent_for(left_val), pc_for(left_val)));
1534 I(c.right == make_pair(parent_for(right_val), pc_for(right_val)));
1535 I(null_node(result.roster.get_node(thing_nid)->parent));
1536 I(result.roster.get_node(thing_nid)->name.empty());
1537 // resolve the conflict, thus making sure that resolution works and
1538 // that this was the only conflict signaled
1539 // attach implicitly checks that we were already detached
1540 result.roster.attach_node(thing_nid, file_path_internal("thing"));
1541 result.multiple_name_conflicts.pop_back();
1542 break;
1543 }
1544 // by now, the merge should have been resolved cleanly, one way or another
1545 result.roster.check_sane();
1546 I(result.is_clean());
1547 }
1548
1549 virtual ~name_shared_stuff() {};
1550};
1551
1552template <typename T>
1553struct basename_scalar : public name_shared_stuff, public T
1554{
1555 virtual file_path path_for(scalar_val val)
1556 {
1557 I(val != scalar_conflict);
1558 return file_path_internal((val == scalar_a) ? "a" : "b");
1559 }
1560 virtual node_id parent_for(scalar_val val)
1561 {
1562 I(val != scalar_conflict);
1563 return root_nid;
1564 }
1565
1566 void
1567 setup_parent(scalar_val val, set<revision_id> marks,
1568 roster_t & r, marking_map & markings)
1569 {
1570 this->T::make_thing(r, markings);
1571 r.detach_node(this->T::thing_name);
1572 r.attach_node(thing_nid, path_for(val));
1573 markings.find(thing_nid)->second.parent_name = marks;
1574 }
1575
1576 virtual ~basename_scalar() {}
1577};
1578
1579template <typename T>
1580struct parent_scalar : public virtual name_shared_stuff, public T
1581{
1582 node_id a_dir_nid, b_dir_nid;
1583 parent_scalar() : a_dir_nid(nis.next()), b_dir_nid(nis.next())
1584 {}
1585
1586 virtual file_path path_for(scalar_val val)
1587 {
1588 I(val != scalar_conflict);
1589 return file_path_internal((val == scalar_a) ? "a/thing" : "b/thing");
1590 }
1591 virtual node_id parent_for(scalar_val val)
1592 {
1593 I(val != scalar_conflict);
1594 return ((val == scalar_a) ? a_dir_nid : b_dir_nid);
1595 }
1596
1597 void
1598 setup_parent(scalar_val val, set<revision_id> marks,
1599 roster_t & r, marking_map & markings)
1600 {
1601 this->T::make_thing(r, markings);
1602 make_dir("a", a_dir_nid, r, markings);
1603 make_dir("b", b_dir_nid, r, markings);
1604 r.detach_node(this->T::thing_name);
1605 r.attach_node(thing_nid, path_for(val));
1606 markings.find(thing_nid)->second.parent_name = marks;
1607 }
1608
1609 virtual ~parent_scalar() {}
1610};
1611
1612template <typename T>
1613struct attr_scalar : public virtual base_scalar, public T
1614{
1615 attr_value attr_value_for(scalar_val val)
1616 {
1617 I(val != scalar_conflict);
1618 return attr_value((val == scalar_a) ? "a" : "b");
1619 }
1620
1621 void
1622 setup_parent(scalar_val val, set<revision_id> marks,
1623 roster_t & r, marking_map & markings)
1624 {
1625 this->T::make_thing(r, markings);
1626 r.set_attr(this->T::thing_name, attr_key("test_key"), attr_value_for(val));
1627 markings.find(thing_nid)->second.attrs[attr_key("test_key")] = marks;
1628 }
1629
1630 void
1631 check_result(scalar_val left_val, scalar_val right_val,
1632 // NB result is writeable -- we can scribble on it
1633 roster_merge_result & result, scalar_val expected_val)
1634 {
1635 switch (expected_val)
1636 {
1637 case scalar_a: case scalar_b:
1638 I(result.roster.get_node(thing_nid)->attrs[attr_key("test_key")]
1639 == make_pair(true, attr_value_for(expected_val)));
1640 break;
1641 case scalar_conflict:
1642 attribute_conflict const & c = idx(result.attribute_conflicts, 0);
1643 I(c.nid == thing_nid);
1644 I(c.key == attr_key("test_key"));
1645 I(c.left == make_pair(true, attr_value_for(left_val)));
1646 I(c.right == make_pair(true, attr_value_for(right_val)));
1647 full_attr_map_t const & attrs = result.roster.get_node(thing_nid)->attrs;
1648 I(attrs.find(attr_key("test_key")) == attrs.end());
1649 // resolve the conflict, thus making sure that resolution works and
1650 // that this was the only conflict signaled
1651 result.roster.set_attr(this->T::thing_name, attr_key("test_key"),
1652 attr_value("conflict -- RESOLVED"));
1653 result.attribute_conflicts.pop_back();
1654 break;
1655 }
1656 // by now, the merge should have been resolved cleanly, one way or another
1657 result.roster.check_sane();
1658 I(result.is_clean());
1659 }
1660};
1661
1662struct file_content_scalar : public virtual file_scalar
1663{
1664 file_id content_for(scalar_val val)
1665 {
1666 I(val != scalar_conflict);
1667 return file_id(string((val == scalar_a)
1668 ? "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1669 : "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1670 }
1671
1672 void
1673 setup_parent(scalar_val val, set<revision_id> marks,
1674 roster_t & r, marking_map & markings)
1675 {
1676 make_thing(r, markings);
1677 downcast_to_file_t(r.get_node(thing_name))->content = content_for(val);
1678 markings.find(thing_nid)->second.file_content = marks;
1679 }
1680
1681 void
1682 check_result(scalar_val left_val, scalar_val right_val,
1683 // NB result is writeable -- we can scribble on it
1684 roster_merge_result & result, scalar_val expected_val)
1685 {
1686 switch (expected_val)
1687 {
1688 case scalar_a: case scalar_b:
1689 I(downcast_to_file_t(result.roster.get_node(thing_nid))->content
1690 == content_for(expected_val));
1691 break;
1692 case scalar_conflict:
1693 file_content_conflict const & c = idx(result.file_content_conflicts, 0);
1694 I(c.nid == thing_nid);
1695 I(c.left == content_for(left_val));
1696 I(c.right == content_for(right_val));
1697 file_id & content = downcast_to_file_t(result.roster.get_node(thing_nid))->content;
1698 I(null_id(content));
1699 // resolve the conflict, thus making sure that resolution works and
1700 // that this was the only conflict signaled
1701 content = file_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1702 result.file_content_conflicts.pop_back();
1703 break;
1704 }
1705 // by now, the merge should have been resolved cleanly, one way or another
1706 result.roster.check_sane();
1707 I(result.is_clean());
1708 }
1709};
1710
1711void
1712test_a_scalar_merge(scalar_val left_val, string const & left_marks_str,
1713 string const & left_uncommon_str,
1714 scalar_val right_val, string const & right_marks_str,
1715 string const & right_uncommon_str,
1716 scalar_val expected_outcome)
1717{
1718 test_a_scalar_merge_impl<basename_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1719 right_val, right_marks_str, right_uncommon_str,
1720 expected_outcome);
1721 test_a_scalar_merge_impl<basename_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1722 right_val, right_marks_str, right_uncommon_str,
1723 expected_outcome);
1724 test_a_scalar_merge_impl<parent_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1725 right_val, right_marks_str, right_uncommon_str,
1726 expected_outcome);
1727 test_a_scalar_merge_impl<parent_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1728 right_val, right_marks_str, right_uncommon_str,
1729 expected_outcome);
1730 test_a_scalar_merge_impl<attr_scalar<file_scalar> >(left_val, left_marks_str, left_uncommon_str,
1731 right_val, right_marks_str, right_uncommon_str,
1732 expected_outcome);
1733 test_a_scalar_merge_impl<attr_scalar<dir_scalar> >(left_val, left_marks_str, left_uncommon_str,
1734 right_val, right_marks_str, right_uncommon_str,
1735 expected_outcome);
1736 test_a_scalar_merge_impl<file_content_scalar>(left_val, left_marks_str, left_uncommon_str,
1737 right_val, right_marks_str, right_uncommon_str,
1738 expected_outcome);
1739}
1740
1741UNIT_TEST(roster_merge, scalar_merges)
1742{
1743 // Notation: a1* means, "value is a, this is node 1 in the graph, it is
1744 // marked". ".2" means, "value is unimportant and different from either a
1745 // or b, this is node 2 in the graph, it is not marked".
1746 //
1747 // Backslashes with dots after them mean, the C++ line continuation rules
1748 // are annoying when it comes to drawing ascii graphs -- the dot is only to
1749 // stop the backslash from having special meaning to the parser. So just
1750 // ignore them :-).
1751
1752 // same in both, same mark
1753 // a1*
1754 // / \.
1755 // a2 a3
1756 test_a_scalar_merge(scalar_a, "1", "2", scalar_a, "1", "3", scalar_a);
1757
1758 // same in both, diff marks
1759 // .1*
1760 // / \.
1761 // a2* a3*
1762 test_a_scalar_merge(scalar_a, "2", "2", scalar_a, "3", "3", scalar_a);
1763
1764 // different, left wins with 1 mark
1765 // a1*
1766 // / \.
1767 // b2* a3
1768 test_a_scalar_merge(scalar_b, "2", "2", scalar_a, "1", "3", scalar_b);
1769
1770 // different, right wins with 1 mark
1771 // a1*
1772 // / \.
1773 // a2 b3*
1774 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "3", "3", scalar_b);
1775
1776 // different, conflict with 1 mark
1777 // .1*
1778 // / \.
1779 // a2* b3*
1780 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "3", "3", scalar_conflict);
1781
1782 // different, left wins with 2 marks
1783 // a1*
1784 // / \.
1785 // a2 a3
1786 // / \.
1787 // b4* b5*
1788 // \ /
1789 // b6
1790 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "1", "3", scalar_b);
1791
1792 // different, right wins with 2 marks
1793 // a1*
1794 // / \.
1795 // a2 a3
1796 // / \.
1797 // b4* b5*
1798 // \ /
1799 // b6
1800 test_a_scalar_merge(scalar_a, "1", "2", scalar_b, "45", "3456", scalar_b);
1801
1802 // different, conflict with 1 mark winning, 1 mark losing
1803 // .1*
1804 // / \.
1805 // a2* a3*
1806 // \ / \.
1807 // a4 b5*
1808 test_a_scalar_merge(scalar_a, "23", "24", scalar_b, "5", "5", scalar_conflict);
1809
1810 //
1811 // .1*
1812 // / \.
1813 // a2* a3*
1814 // / \ /
1815 // b4* a5
1816 test_a_scalar_merge(scalar_b, "4", "4", scalar_a, "23", "35", scalar_conflict);
1817
1818 // different, conflict with 2 marks both conflicting
1819 //
1820 // .1*
1821 // / \.
1822 // .2 a3*
1823 // / \.
1824 // b4* b5*
1825 // \ /
1826 // b6
1827 test_a_scalar_merge(scalar_b, "45", "2456", scalar_a, "3", "3", scalar_conflict);
1828
1829 //
1830 // .1*
1831 // / \.
1832 // a2* .3
1833 // / \.
1834 // b4* b5*
1835 // \ /
1836 // b6
1837 test_a_scalar_merge(scalar_a, "2", "2", scalar_b, "45", "3456", scalar_conflict);
1838
1839 //
1840 // _.1*_
1841 // / \.
1842 // .2 .3
1843 // / \ / \.
1844 // a4* a5* b6* b7*
1845 // \ / \ /
1846 // a8 b9
1847 test_a_scalar_merge(scalar_a, "45", "2458", scalar_b, "67", "3679", scalar_conflict);
1848}
1849
1850namespace
1851{
1852 const revision_id a_uncommon1 = revision_id(string("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
1853 const revision_id a_uncommon2 = revision_id(string("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"));
1854 const revision_id b_uncommon1 = revision_id(string("cccccccccccccccccccccccccccccccccccccccc"));
1855 const revision_id b_uncommon2 = revision_id(string("dddddddddddddddddddddddddddddddddddddddd"));
1856 const revision_id common1 = revision_id(string("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"));
1857 const revision_id common2 = revision_id(string("ffffffffffffffffffffffffffffffffffffffff"));
1858
1859 const file_id fid1 = file_id(string("1111111111111111111111111111111111111111"));
1860 const file_id fid2 = file_id(string("2222222222222222222222222222222222222222"));
1861
1862}
1863
1864static void
1865make_dir(roster_t & r, marking_map & markings,
1866 revision_id const & birth_rid, revision_id const & parent_name_rid,
1867 string const & name, node_id nid)
1868{
1869 r.create_dir_node(nid);
1870 r.attach_node(nid, file_path_internal(name));
1871 marking_t marking;
1872 marking.birth_revision = birth_rid;
1873 marking.parent_name.insert(parent_name_rid);
1874 safe_insert(markings, make_pair(nid, marking));
1875}
1876
1877static void
1878make_file(roster_t & r, marking_map & markings,
1879 revision_id const & birth_rid, revision_id const & parent_name_rid,
1880 revision_id const & file_content_rid,
1881 string const & name, file_id const & content,
1882 node_id nid)
1883{
1884 r.create_file_node(content, nid);
1885 r.attach_node(nid, file_path_internal(name));
1886 marking_t marking;
1887 marking.birth_revision = birth_rid;
1888 marking.parent_name.insert(parent_name_rid);
1889 marking.file_content.insert(file_content_rid);
1890 safe_insert(markings, make_pair(nid, marking));
1891}
1892
1893static void
1894make_node_lifecycle_objs(roster_t & r, marking_map & markings, revision_id const & uncommon,
1895 string const & name, node_id common_dir_nid, node_id common_file_nid,
1896 node_id & safe_dir_nid, node_id & safe_file_nid, node_id_source & nis)
1897{
1898 make_dir(r, markings, common1, common1, "common_old_dir", common_dir_nid);
1899 make_file(r, markings, common1, common1, common1, "common_old_file", fid1, common_file_nid);
1900 safe_dir_nid = nis.next();
1901 make_dir(r, markings, uncommon, uncommon, name + "_safe_dir", safe_dir_nid);
1902 safe_file_nid = nis.next();
1903 make_file(r, markings, uncommon, uncommon, uncommon, name + "_safe_file", fid1, safe_file_nid);
1904 make_dir(r, markings, common1, common1, name + "_dead_dir", nis.next());
1905 make_file(r, markings, common1, common1, common1, name + "_dead_file", fid1, nis.next());
1906}
1907
1908UNIT_TEST(roster_merge, node_lifecycle)
1909{
1910 roster_t a_roster, b_roster;
1911 marking_map a_markings, b_markings;
1912 set<revision_id> a_uncommon, b_uncommon;
1913 // boilerplate to get uncommon revision sets...
1914 a_uncommon.insert(a_uncommon1);
1915 a_uncommon.insert(a_uncommon2);
1916 b_uncommon.insert(b_uncommon1);
1917 b_uncommon.insert(b_uncommon2);
1918 testing_node_id_source nis;
1919 // boilerplate to set up a root node...
1920 {
1921 node_id root_nid = nis.next();
1922 make_dir(a_roster, a_markings, common1, common1, "", root_nid);
1923 make_dir(b_roster, b_markings, common1, common1, "", root_nid);
1924 }
1925 // create some nodes on each side
1926 node_id common_dir_nid = nis.next();
1927 node_id common_file_nid = nis.next();
1928 node_id a_safe_dir_nid, a_safe_file_nid, b_safe_dir_nid, b_safe_file_nid;
1929 make_node_lifecycle_objs(a_roster, a_markings, a_uncommon1, "a", common_dir_nid, common_file_nid,
1930 a_safe_dir_nid, a_safe_file_nid, nis);
1931 make_node_lifecycle_objs(b_roster, b_markings, b_uncommon1, "b", common_dir_nid, common_file_nid,
1932 b_safe_dir_nid, b_safe_file_nid, nis);
1933 // do the merge
1934 roster_merge_result result;
1935 roster_merge(a_roster, a_markings, a_uncommon, b_roster, b_markings, b_uncommon, result);
1936 I(result.is_clean());
1937 // go ahead and check the roster_delta code too, while we're at it...
1938 test_roster_delta_on(a_roster, a_markings, b_roster, b_markings);
1939 // 7 = 1 root + 2 common + 2 safe a + 2 safe b
1940 I(result.roster.all_nodes().size() == 7);
1941 // check that they're the right ones...
1942 I(shallow_equal(result.roster.get_node(common_dir_nid),
1943 a_roster.get_node(common_dir_nid), false));
1944 I(shallow_equal(result.roster.get_node(common_file_nid),
1945 a_roster.get_node(common_file_nid), false));
1946 I(shallow_equal(result.roster.get_node(common_dir_nid),
1947 b_roster.get_node(common_dir_nid), false));
1948 I(shallow_equal(result.roster.get_node(common_file_nid),
1949 b_roster.get_node(common_file_nid), false));
1950 I(shallow_equal(result.roster.get_node(a_safe_dir_nid),
1951 a_roster.get_node(a_safe_dir_nid), false));
1952 I(shallow_equal(result.roster.get_node(a_safe_file_nid),
1953 a_roster.get_node(a_safe_file_nid), false));
1954 I(shallow_equal(result.roster.get_node(b_safe_dir_nid),
1955 b_roster.get_node(b_safe_dir_nid), false));
1956 I(shallow_equal(result.roster.get_node(b_safe_file_nid),
1957 b_roster.get_node(b_safe_file_nid), false));
1958}
1959
1960UNIT_TEST(roster_merge, attr_lifecycle)
1961{
1962 roster_t left_roster, right_roster;
1963 marking_map left_markings, right_markings;
1964 MM(left_roster);
1965 MM(left_markings);
1966 MM(right_roster);
1967 MM(right_markings);
1968 set<revision_id> old_revs, left_revs, right_revs;
1969 string_to_set("0", old_revs);
1970 string_to_set("1", left_revs);
1971 string_to_set("2", right_revs);
1972 revision_id old_rid = *old_revs.begin();
1973 testing_node_id_source nis;
1974 node_id dir_nid = nis.next();
1975 make_dir(left_roster, left_markings, old_rid, old_rid, "", dir_nid);
1976 make_dir(right_roster, right_markings, old_rid, old_rid, "", dir_nid);
1977 node_id file_nid = nis.next();
1978 make_file(left_roster, left_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1979 make_file(right_roster, right_markings, old_rid, old_rid, old_rid, "thing", fid1, file_nid);
1980
1981 // put one live and one dead attr on each thing on each side, with uncommon
1982 // marks on them
1983 safe_insert(left_roster.get_node(dir_nid)->attrs,
1984 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1985 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1986 safe_insert(left_roster.get_node(dir_nid)->attrs,
1987 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1988 safe_insert(left_markings[dir_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1989 safe_insert(left_roster.get_node(file_nid)->attrs,
1990 make_pair(attr_key("left_live"), make_pair(true, attr_value("left_live"))));
1991 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_live"), left_revs));
1992 safe_insert(left_roster.get_node(file_nid)->attrs,
1993 make_pair(attr_key("left_dead"), make_pair(false, attr_value(""))));
1994 safe_insert(left_markings[file_nid].attrs, make_pair(attr_key("left_dead"), left_revs));
1995
1996 safe_insert(right_roster.get_node(dir_nid)->attrs,
1997 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
1998 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_live"), right_revs));
1999 safe_insert(right_roster.get_node(dir_nid)->attrs,
2000 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
2001 safe_insert(right_markings[dir_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
2002 safe_insert(right_roster.get_node(file_nid)->attrs,
2003 make_pair(attr_key("right_live"), make_pair(true, attr_value("right_live"))));
2004 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_live"), right_revs));
2005 safe_insert(right_roster.get_node(file_nid)->attrs,
2006 make_pair(attr_key("right_dead"), make_pair(false, attr_value(""))));
2007 safe_insert(right_markings[file_nid].attrs, make_pair(attr_key("right_dead"), right_revs));
2008
2009 roster_merge_result result;
2010 MM(result);
2011 roster_merge(left_roster, left_markings, left_revs,
2012 right_roster, right_markings, right_revs,
2013 result);
2014 // go ahead and check the roster_delta code too, while we're at it...
2015 test_roster_delta_on(left_roster, left_markings, right_roster, right_markings);
2016 I(result.roster.all_nodes().size() == 2);
2017 I(result.roster.get_node(dir_nid)->attrs.size() == 4);
2018 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
2019 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
2020 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
2021 I(safe_get(result.roster.get_node(dir_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
2022 I(result.roster.get_node(file_nid)->attrs.size() == 4);
2023 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_live")) == make_pair(true, attr_value("left_live")));
2024 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
2025 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("right_live")) == make_pair(true, attr_value("right_live")));
2026 I(safe_get(result.roster.get_node(file_nid)->attrs, attr_key("left_dead")) == make_pair(false, attr_value("")));
2027}
2028
2029struct structural_conflict_helper
2030{
2031 roster_t left_roster, right_roster;
2032 marking_map left_markings, right_markings;
2033 set<revision_id> old_revs, left_revs, right_revs;
2034 revision_id old_rid, left_rid, right_rid;
2035 testing_node_id_source nis;
2036 node_id root_nid;
2037 roster_merge_result result;
2038
2039 virtual void setup() = 0;
2040 virtual void check() = 0;
2041
2042 void test()
2043 {
2044 MM(left_roster);
2045 MM(left_markings);
2046 MM(right_roster);
2047 MM(right_markings);
2048 string_to_set("0", old_revs);
2049 string_to_set("1", left_revs);
2050 string_to_set("2", right_revs);
2051 old_rid = *old_revs.begin();
2052 left_rid = *left_revs.begin();
2053 right_rid = *right_revs.begin();
2054 root_nid = nis.next();
2055 make_dir(left_roster, left_markings, old_rid, old_rid, "", root_nid);
2056 make_dir(right_roster, right_markings, old_rid, old_rid, "", root_nid);
2057
2058 setup();
2059
2060 MM(result);
2061 roster_merge(left_roster, left_markings, left_revs,
2062 right_roster, right_markings, right_revs,
2063 result);
2064 // go ahead and check the roster_delta code too, while we're at it...
2065 test_roster_delta_on(left_roster, left_markings, right_roster, right_markings);
2066
2067 check();
2068 }
2069
2070 virtual ~structural_conflict_helper() {}
2071};
2072
2073// two diff nodes with same name
2074struct simple_duplicate_name_conflict : public structural_conflict_helper
2075{
2076 node_id left_nid, right_nid;
2077 virtual void setup()
2078 {
2079 left_nid = nis.next();
2080 make_dir(left_roster, left_markings, left_rid, left_rid, "thing", left_nid);
2081 right_nid = nis.next();
2082 make_dir(right_roster, right_markings, right_rid, right_rid, "thing", right_nid);
2083 }
2084
2085 virtual void check()
2086 {
2087 I(!result.is_clean());
2088 duplicate_name_conflict const & c = idx(result.duplicate_name_conflicts, 0);
2089 I(c.left_nid == left_nid && c.right_nid == right_nid);
2090 I(c.parent_name == make_pair(root_nid, path_component("thing")));
2091 // this tests that they were detached, implicitly
2092 result.roster.attach_node(left_nid, file_path_internal("left"));
2093 result.roster.attach_node(right_nid, file_path_internal("right"));
2094 result.duplicate_name_conflicts.pop_back();
2095 I(result.is_clean());
2096 result.roster.check_sane();
2097 }
2098};
2099
2100// directory loops
2101struct simple_dir_loop_conflict : public structural_conflict_helper
2102{
2103 node_id left_top_nid, right_top_nid;
2104
2105 virtual void setup()
2106 {
2107 left_top_nid = nis.next();
2108 right_top_nid = nis.next();
2109
2110 make_dir(left_roster, left_markings, old_rid, old_rid, "top", left_top_nid);
2111 make_dir(left_roster, left_markings, old_rid, left_rid, "top/bottom", right_top_nid);
2112
2113 make_dir(right_roster, right_markings, old_rid, old_rid, "top", right_top_nid);
2114 make_dir(right_roster, right_markings, old_rid, right_rid, "top/bottom", left_top_nid);
2115 }
2116
2117 virtual void check()
2118 {
2119 I(!result.is_clean());
2120 directory_loop_conflict const & c = idx(result.directory_loop_conflicts, 0);
2121 I((c.nid == left_top_nid && c.parent_name == make_pair(right_top_nid, path_component("bottom")))
2122 || (c.nid == right_top_nid && c.parent_name == make_pair(left_top_nid, path_component("bottom"))));
2123 // this tests it was detached, implicitly
2124 result.roster.attach_node(c.nid, file_path_internal("resolved"));
2125 result.directory_loop_conflicts.pop_back();
2126 I(result.is_clean());
2127 result.roster.check_sane();
2128 }
2129};
2130
2131// orphans
2132struct simple_orphan_conflict : public structural_conflict_helper
2133{
2134 node_id a_dead_parent_nid, a_live_child_nid, b_dead_parent_nid, b_live_child_nid;
2135
2136 // in ancestor, both parents are alive
2137 // in left, a_dead_parent is dead, and b_live_child is created
2138 // in right, b_dead_parent is dead, and a_live_child is created
2139
2140 virtual void setup()
2141 {
2142 a_dead_parent_nid = nis.next();
2143 a_live_child_nid = nis.next();
2144 b_dead_parent_nid = nis.next();
2145 b_live_child_nid = nis.next();
2146
2147 make_dir(left_roster, left_markings, old_rid, old_rid, "b_parent", b_dead_parent_nid);
2148 make_dir(left_roster, left_markings, left_rid, left_rid, "b_parent/b_child", b_live_child_nid);
2149
2150 make_dir(right_roster, right_markings, old_rid, old_rid, "a_parent", a_dead_parent_nid);
2151 make_dir(right_roster, right_markings, right_rid, right_rid, "a_parent/a_child", a_live_child_nid);
2152 }
2153
2154 virtual void check()
2155 {
2156 I(!result.is_clean());
2157 I(result.orphaned_node_conflicts.size() == 2);
2158 orphaned_node_conflict a, b;
2159 if (idx(result.orphaned_node_conflicts, 0).nid == a_live_child_nid)
2160 {
2161 a = idx(result.orphaned_node_conflicts, 0);
2162 b = idx(result.orphaned_node_conflicts, 1);
2163 }
2164 else
2165 {
2166 a = idx(result.orphaned_node_conflicts, 1);
2167 b = idx(result.orphaned_node_conflicts, 0);
2168 }
2169 I(a.nid == a_live_child_nid);
2170 I(a.parent_name == make_pair(a_dead_parent_nid, path_component("a_child")));
2171 I(b.nid == b_live_child_nid);
2172 I(b.parent_name == make_pair(b_dead_parent_nid, path_component("b_child")));
2173 // this tests it was detached, implicitly
2174 result.roster.attach_node(a.nid, file_path_internal("resolved_a"));
2175 result.roster.attach_node(b.nid, file_path_internal("resolved_b"));
2176 result.orphaned_node_conflicts.pop_back();
2177 result.orphaned_node_conflicts.pop_back();
2178 I(result.is_clean());
2179 result.roster.check_sane();
2180 }
2181};
2182
2183// illegal node ("_MTN")
2184struct simple_invalid_name_conflict : public structural_conflict_helper
2185{
2186 node_id new_root_nid, bad_dir_nid;
2187
2188 // in left, new_root is the root (it existed in old, but was renamed in left)
2189 // in right, new_root is still a subdir, the old root still exists, and a
2190 // new dir has been created
2191
2192 virtual void setup()
2193 {
2194 new_root_nid = nis.next();
2195 bad_dir_nid = nis.next();
2196
2197 left_roster.drop_detached_node(left_roster.detach_node(file_path()));
2198 safe_erase(left_markings, root_nid);
2199 make_dir(left_roster, left_markings, old_rid, left_rid, "", new_root_nid);
2200
2201 make_dir(right_roster, right_markings, old_rid, old_rid, "root_to_be", new_root_nid);
2202 make_dir(right_roster, right_markings, right_rid, right_rid, "root_to_be/_MTN", bad_dir_nid);
2203 }
2204
2205 virtual void check()
2206 {
2207 I(!result.is_clean());
2208 invalid_name_conflict const & c = idx(result.invalid_name_conflicts, 0);
2209 I(c.nid == bad_dir_nid);
2210 I(c.parent_name == make_pair(new_root_nid, bookkeeping_root_component));
2211 // this tests it was detached, implicitly
2212 result.roster.attach_node(bad_dir_nid, file_path_internal("dir_formerly_known_as__MTN"));
2213 result.invalid_name_conflicts.pop_back();
2214 I(result.is_clean());
2215 result.roster.check_sane();
2216 }
2217};
2218
2219// missing root dir
2220struct simple_missing_root_dir : public structural_conflict_helper
2221{
2222 node_id other_root_nid;
2223
2224 // left and right each have different root nodes, and each has deleted the
2225 // other's root node
2226
2227 virtual void setup()
2228 {
2229 other_root_nid = nis.next();
2230
2231 left_roster.drop_detached_node(left_roster.detach_node(file_path()));
2232 safe_erase(left_markings, root_nid);
2233 make_dir(left_roster, left_markings, old_rid, old_rid, "", other_root_nid);
2234 }
2235
2236 virtual void check()
2237 {
2238 I(!result.is_clean());
2239 I(result.missing_root_dir);
2240 result.roster.attach_node(result.roster.create_dir_node(nis), file_path());
2241 result.missing_root_dir = false;
2242 I(result.is_clean());
2243 result.roster.check_sane();
2244 }
2245};
2246
2247UNIT_TEST(roster_merge, simple_structural_conflicts)
2248{
2249 {
2250 simple_duplicate_name_conflict t;
2251 t.test();
2252 }
2253 {
2254 simple_dir_loop_conflict t;
2255 t.test();
2256 }
2257 {
2258 simple_orphan_conflict t;
2259 t.test();
2260 }
2261 {
2262 simple_invalid_name_conflict t;
2263 t.test();
2264 }
2265 {
2266 simple_missing_root_dir t;
2267 t.test();
2268 }
2269}
2270
2271struct multiple_name_plus_helper : public structural_conflict_helper
2272{
2273 node_id name_conflict_nid;
2274 node_id left_parent, right_parent;
2275 path_component left_name, right_name;
2276 void make_multiple_name_conflict(string const & left, string const & right)
2277 {
2278 file_path left_path = file_path_internal(left);
2279 file_path right_path = file_path_internal(right);
2280 name_conflict_nid = nis.next();
2281 make_dir(left_roster, left_markings, old_rid, left_rid, left, name_conflict_nid);
2282 left_parent = left_roster.get_node(left_path)->parent;
2283 left_name = left_roster.get_node(left_path)->name;
2284 make_dir(right_roster, right_markings, old_rid, right_rid, right, name_conflict_nid);
2285 right_parent = right_roster.get_node(right_path)->parent;
2286 right_name = right_roster.get_node(right_path)->name;
2287 }
2288 void check_multiple_name_conflict()
2289 {
2290 I(!result.is_clean());
2291 multiple_name_conflict const & c = idx(result.multiple_name_conflicts, 0);
2292 I(c.nid == name_conflict_nid);
2293 I(c.left == make_pair(left_parent, left_name));
2294 I(c.right == make_pair(right_parent, right_name));
2295 result.roster.attach_node(name_conflict_nid, file_path_internal("totally_other_name"));
2296 result.multiple_name_conflicts.pop_back();
2297 I(result.is_clean());
2298 result.roster.check_sane();
2299 }
2300};
2301
2302struct multiple_name_plus_duplicate_name : public multiple_name_plus_helper
2303{
2304 node_id a_nid, b_nid;
2305
2306 virtual void setup()
2307 {
2308 a_nid = nis.next();
2309 b_nid = nis.next();
2310 make_multiple_name_conflict("a", "b");
2311 make_dir(left_roster, left_markings, left_rid, left_rid, "b", b_nid);
2312 make_dir(right_roster, right_markings, right_rid, right_rid, "a", a_nid);
2313 }
2314
2315 virtual void check()
2316 {
2317 // there should just be a single conflict on name_conflict_nid, and a and
2318 // b should have landed fine
2319 I(result.roster.get_node(file_path_internal("a"))->self == a_nid);
2320 I(result.roster.get_node(file_path_internal("b"))->self == b_nid);
2321 check_multiple_name_conflict();
2322 }
2323};
2324
2325struct multiple_name_plus_orphan : public multiple_name_plus_helper
2326{
2327 node_id a_nid, b_nid;
2328
2329 virtual void setup()
2330 {
2331 a_nid = nis.next();
2332 b_nid = nis.next();
2333 make_dir(left_roster, left_markings, old_rid, left_rid, "a", a_nid);
2334 make_dir(right_roster, right_markings, old_rid, right_rid, "b", b_nid);
2335 make_multiple_name_conflict("a/foo", "b/foo");
2336 }
2337
2338 virtual void check()
2339 {
2340 I(result.roster.all_nodes().size() == 2);
2341 check_multiple_name_conflict();
2342 }
2343};
2344
2345struct multiple_name_plus_directory_loop : public multiple_name_plus_helper
2346{
2347 node_id a_nid, b_nid;
2348
2349 virtual void setup()
2350 {
2351 a_nid = nis.next();
2352 b_nid = nis.next();
2353 make_dir(left_roster, left_markings, old_rid, old_rid, "a", a_nid);
2354 make_dir(right_roster, right_markings, old_rid, old_rid, "b", b_nid);
2355 make_multiple_name_conflict("a/foo", "b/foo");
2356 make_dir(left_roster, left_markings, old_rid, left_rid, "a/foo/b", b_nid);
2357 make_dir(right_roster, right_markings, old_rid, right_rid, "b/foo/a", a_nid);
2358 }
2359
2360 virtual void check()
2361 {
2362 I(downcast_to_dir_t(result.roster.get_node(name_conflict_nid))->children.size() == 2);
2363 check_multiple_name_conflict();
2364 }
2365};
2366
2367struct multiple_name_plus_invalid_name : public multiple_name_plus_helper
2368{
2369 node_id new_root_nid;
2370
2371 virtual void setup()
2372 {
2373 new_root_nid = nis.next();
2374 make_dir(left_roster, left_markings, old_rid, old_rid, "new_root", new_root_nid);
2375 right_roster.drop_detached_node(right_roster.detach_node(file_path()));
2376 safe_erase(right_markings, root_nid);
2377 make_dir(right_roster, right_markings, old_rid, right_rid, "", new_root_nid);
2378 make_multiple_name_conflict("new_root/_MTN", "foo");
2379 }
2380
2381 virtual void check()
2382 {
2383 I(result.roster.root()->self == new_root_nid);
2384 I(result.roster.all_nodes().size() == 2);
2385 check_multiple_name_conflict();
2386 }
2387};
2388
2389struct multiple_name_plus_missing_root : public structural_conflict_helper
2390{
2391 node_id left_root_nid, right_root_nid;
2392
2393 virtual void setup()
2394 {
2395 left_root_nid = nis.next();
2396 right_root_nid = nis.next();
2397
2398 left_roster.drop_detached_node(left_roster.detach_node(file_path()));
2399 safe_erase(left_markings, root_nid);
2400 make_dir(left_roster, left_markings, old_rid, left_rid, "", left_root_nid);
2401 make_dir(left_roster, left_markings, old_rid, left_rid, "right_root", right_root_nid);
2402
2403 right_roster.drop_detached_node(right_roster.detach_node(file_path()));
2404 safe_erase(right_markings, root_nid);
2405 make_dir(right_roster, right_markings, old_rid, right_rid, "", right_root_nid);
2406 make_dir(right_roster, right_markings, old_rid, right_rid, "left_root", left_root_nid);
2407 }
2408 void check_helper(multiple_name_conflict const & left_c,
2409 multiple_name_conflict const & right_c)
2410 {
2411 I(left_c.nid == left_root_nid);
2412 I(left_c.left == make_pair(the_null_node, path_component()));
2413 I(left_c.right == make_pair(right_root_nid, path_component("left_root")));
2414
2415 I(right_c.nid == right_root_nid);
2416 I(right_c.left == make_pair(left_root_nid, path_component("right_root")));
2417 I(right_c.right == make_pair(the_null_node, path_component()));
2418 }
2419 virtual void check()
2420 {
2421 I(!result.is_clean());
2422 I(result.multiple_name_conflicts.size() == 2);
2423
2424 if (idx(result.multiple_name_conflicts, 0).nid == left_root_nid)
2425 check_helper(idx(result.multiple_name_conflicts, 0),
2426 idx(result.multiple_name_conflicts, 1));
2427 else
2428 check_helper(idx(result.multiple_name_conflicts, 1),
2429 idx(result.multiple_name_conflicts, 0));
2430
2431 I(result.missing_root_dir);
2432
2433 result.roster.attach_node(left_root_nid, file_path());
2434 result.roster.attach_node(right_root_nid, file_path_internal("totally_other_name"));
2435 result.multiple_name_conflicts.pop_back();
2436 result.multiple_name_conflicts.pop_back();
2437 result.missing_root_dir = false;
2438 I(result.is_clean());
2439 result.roster.check_sane();
2440 }
2441};
2442
2443struct duplicate_name_plus_missing_root : public structural_conflict_helper
2444{
2445 node_id left_root_nid, right_root_nid;
2446
2447 virtual void setup()
2448 {
2449 left_root_nid = nis.next();
2450 right_root_nid = nis.next();
2451
2452 left_roster.drop_detached_node(left_roster.detach_node(file_path()));
2453 safe_erase(left_markings, root_nid);
2454 make_dir(left_roster, left_markings, left_rid, left_rid, "", left_root_nid);
2455
2456 right_roster.drop_detached_node(right_roster.detach_node(file_path()));
2457 safe_erase(right_markings, root_nid);
2458 make_dir(right_roster, right_markings, right_rid, right_rid, "", right_root_nid);
2459 }
2460 virtual void check()
2461 {
2462 I(!result.is_clean());
2463 duplicate_name_conflict const & c = idx(result.duplicate_name_conflicts, 0);
2464 I(c.left_nid == left_root_nid && c.right_nid == right_root_nid);
2465 I(c.parent_name == make_pair(the_null_node, path_component()));
2466
2467 I(result.missing_root_dir);
2468
2469 // we can't just attach one of these as the root -- see the massive
2470 // comment on the old_locations member of roster_t, in roster.hh.
2471 result.roster.attach_node(result.roster.create_dir_node(nis), file_path());
2472 result.roster.attach_node(left_root_nid, file_path_internal("totally_left_name"));
2473 result.roster.attach_node(right_root_nid, file_path_internal("totally_right_name"));
2474 result.duplicate_name_conflicts.pop_back();
2475 result.missing_root_dir = false;
2476 I(result.is_clean());
2477 result.roster.check_sane();
2478 }
2479};
2480
2481UNIT_TEST(roster_merge, complex_structural_conflicts)
2482{
2483 {
2484 multiple_name_plus_duplicate_name t;
2485 t.test();
2486 }
2487 {
2488 multiple_name_plus_orphan t;
2489 t.test();
2490 }
2491 {
2492 multiple_name_plus_directory_loop t;
2493 t.test();
2494 }
2495 {
2496 multiple_name_plus_invalid_name t;
2497 t.test();
2498 }
2499 {
2500 multiple_name_plus_missing_root t;
2501 t.test();
2502 }
2503 {
2504 duplicate_name_plus_missing_root t;
2505 t.test();
2506 }
2507}
2508
2509#endif // BUILD_UNIT_TESTS
2510
2511// Local Variables:
2512// mode: C++
2513// fill-column: 76
2514// c-file-style: "gnu"
2515// indent-tabs-mode: nil
2516// End:
2517// 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