monotone

monotone Mtn Source Tree

Root/roster_merge.cc

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