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