monotone

monotone Mtn Source Tree

Root/change_set.cc

1// copyright (C) 2004 graydon hoare <graydon@pobox.com>
2// all rights reserved.
3// licensed to the public under the terms of the GNU GPL (>= 2)
4// see the file COPYING for details
5
6// this is how you "ask for" the C99 constant constructor macros. *and*
7// you have to do so before any other files accidentally include
8// stdint.h. awesome.
9#define __STDC_CONSTANT_MACROS
10
11#include <algorithm>
12#include <iterator>
13#include <iostream>
14#include <list>
15#include <vector>
16#include <ext/hash_map>
17
18#include <boost/filesystem/path.hpp>
19#include <boost/shared_ptr.hpp>
20#include <boost/lexical_cast.hpp>
21
22#include "basic_io.hh"
23#include "change_set.hh"
24#include "constants.hh"
25#include "diff_patch.hh"
26#include "file_io.hh"
27#include "numeric_vocab.hh"
28#include "sanity.hh"
29#include "smap.hh"
30#include "path_component.hh"
31
32// our analyses in this file happen on one of two families of
33// related structures: a path_analysis or a directory_map.
34//
35// a path_analysis corresponds exactly to a normalized
36// path_rearrangement; they are two ways of writing the
37// same information
38//
39// the path_analysis stores two path_states. each path_state is a map from
40// transient identifiers (tids) to items. each item represents a semantic
41// element of a filesystem which has a type (file or directory), a name,
42// and a parent link (another tid). tids should be unique across a
43// path_analysis.
44
45typedef enum { ptype_directory, ptype_file } ptype;
46typedef u32 tid;
47static tid root_tid = 0;
48
49struct
50tid_source
51{
52 tid ctr;
53 tid_source() : ctr(root_tid + 1) {}
54 tid next() { I(ctr != UINT32_C(0xffffffff)); return ctr++; }
55};
56
57struct
58path_item
59{
60 tid parent;
61 ptype ty;
62 path_component name;
63 path_item() {}
64 path_item(tid p, ptype t, path_component n);
65 path_item(path_item const & other);
66 path_item const & operator=(path_item const & other);
67 bool operator==(path_item const & other) const;
68};
69
70
71template<typename T> struct identity
72{
73 size_t operator()(T const & v) const
74 {
75 return static_cast<size_t>(v);
76 }
77};
78
79typedef smap<tid, path_item> path_state;
80typedef smap<tid, tid> state_renumbering;
81typedef std::pair<path_state, path_state> path_analysis;
82
83// nulls and tests
84
85static file_id null_ident;
86
87// a directory_map is a more "normal" representation of a directory tree,
88// which you can traverse more conveniently from root to tip
89//
90// tid -> [ name -> (ptype, tid),
91// name -> (ptype, tid),
92// ... ]
93//
94// tid -> [ name -> (ptype, tid),
95// name -> (ptype, tid),
96// ... ]
97
98typedef smap< path_component, std::pair<ptype,tid> > directory_node;
99typedef smap<tid, boost::shared_ptr<directory_node> > directory_map;
100
101static path_component
102directory_entry_name(directory_node::const_iterator const & i)
103{
104 return i->first;
105}
106
107static ptype
108directory_entry_type(directory_node::const_iterator const & i)
109{
110 return i->second.first;
111}
112
113static tid
114directory_entry_tid(directory_node::const_iterator const & i)
115{
116 return i->second.second;
117}
118
119void
120change_set::add_file(file_path const & a)
121{
122 I(rearrangement.added_files.find(a) == rearrangement.added_files.end());
123 rearrangement.added_files.insert(a);
124}
125
126void
127change_set::add_file(file_path const & a, file_id const & ident)
128{
129 I(rearrangement.added_files.find(a) == rearrangement.added_files.end());
130 I(deltas.find(a) == deltas.end());
131 rearrangement.added_files.insert(a);
132 deltas.insert(std::make_pair(a, std::make_pair(null_ident, ident)));
133}
134
135void
136change_set::apply_delta(file_path const & path,
137 file_id const & src,
138 file_id const & dst)
139{
140 I(deltas.find(path) == deltas.end());
141 deltas.insert(std::make_pair(path, std::make_pair(src, dst)));
142}
143
144void
145change_set::delete_file(file_path const & d)
146{
147 I(rearrangement.deleted_files.find(d) == rearrangement.deleted_files.end());
148 rearrangement.deleted_files.insert(d);
149}
150
151void
152change_set::delete_dir(file_path const & d)
153{
154 I(rearrangement.deleted_dirs.find(d) == rearrangement.deleted_dirs.end());
155 rearrangement.deleted_dirs.insert(d);
156}
157
158void
159change_set::rename_file(file_path const & a, file_path const & b)
160{
161 I(rearrangement.renamed_files.find(a) == rearrangement.renamed_files.end());
162 rearrangement.renamed_files.insert(std::make_pair(a,b));
163}
164
165void
166change_set::rename_dir(file_path const & a, file_path const & b)
167{
168 I(rearrangement.renamed_dirs.find(a) == rearrangement.renamed_dirs.end());
169 rearrangement.renamed_dirs.insert(std::make_pair(a,b));
170}
171
172
173bool
174change_set::path_rearrangement::operator==(path_rearrangement const & other) const
175{
176 return deleted_files == other.deleted_files &&
177 deleted_dirs == other.deleted_dirs &&
178 renamed_files == other.renamed_files &&
179 renamed_dirs == other.renamed_dirs &&
180 added_files == other.added_files;
181}
182
183bool
184change_set::path_rearrangement::empty() const
185{
186 return deleted_files.empty() &&
187 deleted_dirs.empty() &&
188 renamed_files.empty() &&
189 renamed_dirs.empty() &&
190 added_files.empty();
191}
192
193bool
194change_set::path_rearrangement::has_added_file(file_path const & file) const
195{
196 return added_files.find(file) != added_files.end();
197}
198
199bool
200change_set::path_rearrangement::has_deleted_file(file_path const & file) const
201{
202 return deleted_files.find(file) != deleted_files.end();
203}
204
205bool
206change_set::path_rearrangement::has_renamed_file_dst(file_path const & file) const
207{
208 // FIXME: this is inefficient, but improvements would require a different
209 // structure for renamed_files (or perhaps a second reverse map). For now
210 // we'll assume that few files will be renamed per changeset.
211 for (std::map<file_path,file_path>::const_iterator rf = renamed_files.begin();
212 rf != renamed_files.end(); ++rf)
213 if (rf->second == file)
214 return true;
215 return false;
216}
217
218bool
219change_set::path_rearrangement::has_renamed_file_src(file_path const & file) const
220{
221 return renamed_files.find(file) != renamed_files.end();
222}
223
224bool
225change_set::empty() const
226{
227 return deltas.empty() && rearrangement.empty();
228}
229
230bool
231change_set::operator==(change_set const & other) const
232{
233 return rearrangement == other.rearrangement &&
234 deltas == other.deltas;
235}
236
237
238// simple accessors
239
240inline tid const &
241path_item_parent(path_item const & p)
242{
243 return p.parent;
244}
245
246inline ptype const &
247path_item_type(path_item const & p)
248{
249 return p.ty;
250}
251
252inline path_component
253path_item_name(path_item const & p)
254{
255 return p.name;
256}
257
258inline tid
259path_state_tid(path_state::const_iterator i)
260{
261 return i->first;
262}
263
264inline path_item const &
265path_state_item(path_state::const_iterator i)
266{
267 return i->second;
268}
269
270
271
272// structure dumping
273/*
274
275static void
276dump_renumbering(std::string const & s,
277 state_renumbering const & r)
278{
279 L(F("BEGIN dumping renumbering '%s'\n") % s);
280 for (state_renumbering::const_iterator i = r.begin();
281 i != r.end(); ++i)
282 {
283 L(F("%d -> %d\n") % i->first % i->second);
284 }
285 L(F("END dumping renumbering '%s'\n") % s);
286}
287
288static void
289dump_state(std::string const & s,
290 path_state const & st)
291{
292 L(F("BEGIN dumping state '%s'\n") % s);
293 for (path_state::const_iterator i = st.begin();
294 i != st.end(); ++i)
295 {
296 std::vector<path_component> tmp_v;
297 tmp.push_back(path_item_name(path_state_item(i)));
298 file_path tmp_fp;
299 compose_path(tmp_v, tmp_fp);
300 L(F("state '%s': tid %d, parent %d, type %s, name %s\n")
301 % s
302 % path_state_tid(i)
303 % path_item_parent(path_state_item(i))
304 % (path_item_type(path_state_item(i)) == ptype_directory ? "dir" : "file")
305 % tmp_fp);
306 }
307 L(F("END dumping state '%s'\n") % s);
308}
309
310static void
311dump_analysis(std::string const & s,
312 path_analysis const & t)
313{
314 L(F("BEGIN dumping tree '%s'\n") % s);
315 dump_state(s + " first", t.first);
316 dump_state(s + " second", t.second);
317 L(F("END dumping tree '%s'\n") % s);
318}
319
320*/
321
322
323// sanity checking
324
325static void
326check_sets_disjoint(std::set<file_path> const & a,
327 std::set<file_path> const & b)
328{
329 std::set<file_path> isect;
330 std::set_intersection(a.begin(), a.end(),
331 b.begin(), b.end(),
332 std::inserter(isect, isect.begin()));
333 if (!global_sanity.relaxed)
334 {
335 I(isect.empty());
336 }
337}
338
339change_set::path_rearrangement::path_rearrangement(path_rearrangement const & other)
340{
341 other.check_sane();
342 deleted_files = other.deleted_files;
343 deleted_dirs = other.deleted_dirs;
344 renamed_files = other.renamed_files;
345 renamed_dirs = other.renamed_dirs;
346 added_files = other.added_files;
347}
348
349change_set::path_rearrangement const &
350change_set::path_rearrangement::operator=(path_rearrangement const & other)
351{
352 other.check_sane();
353 deleted_files = other.deleted_files;
354 deleted_dirs = other.deleted_dirs;
355 renamed_files = other.renamed_files;
356 renamed_dirs = other.renamed_dirs;
357 added_files = other.added_files;
358 return *this;
359}
360
361static void
362extract_pairs_and_insert(std::map<file_path, file_path> const & in,
363 std::set<file_path> & firsts,
364 std::set<file_path> & seconds)
365{
366 for (std::map<file_path, file_path>::const_iterator i = in.begin();
367 i != in.end(); ++i)
368 {
369 firsts.insert(i->first);
370 seconds.insert(i->second);
371 }
372}
373
374template <typename A, typename B>
375static void
376extract_first(std::map<A, B> const & m, std::set<A> & s)
377{
378 s.clear();
379 for (typename std::map<A, B>::const_iterator i = m.begin();
380 i != m.end(); ++i)
381 {
382 s.insert(i->first);
383 }
384}
385
386static void
387extract_killed(path_analysis const & a,
388 std::set<file_path> & killed);
389
390
391static void
392check_no_deltas_on_killed_files(path_analysis const & pa,
393 change_set::delta_map const & del)
394{
395 std::set<file_path> killed;
396 std::set<file_path> delta_paths;
397
398 extract_killed(pa, killed);
399 extract_first(del, delta_paths);
400 check_sets_disjoint(killed, delta_paths);
401}
402
403static void
404check_delta_entries_not_directories(path_analysis const & pa,
405 change_set::delta_map const & dels);
406
407void
408analyze_rearrangement(change_set::path_rearrangement const & pr,
409 path_analysis & pa,
410 tid_source & ts);
411
412void
413sanity_check_path_analysis(path_analysis const & pr);
414
415void
416change_set::path_rearrangement::check_sane() const
417{
418 delta_map del;
419 this->check_sane(del);
420}
421
422void
423change_set::path_rearrangement::check_sane(delta_map const & deltas) const
424{
425 tid_source ts;
426 path_analysis pa;
427 analyze_rearrangement(*this, pa, ts);
428 sanity_check_path_analysis (pa);
429
430 check_no_deltas_on_killed_files(pa, deltas);
431 check_delta_entries_not_directories(pa, deltas);
432
433 // FIXME: extend this as you manage to think of more invariants
434 // which are cheap enough to check at this level.
435 std::set<file_path> renamed_srcs, renamed_dsts;
436 extract_pairs_and_insert(renamed_files, renamed_srcs, renamed_dsts);
437 extract_pairs_and_insert(renamed_dirs, renamed_srcs, renamed_dsts);
438
439 // Files cannot be split nor joined by renames.
440 I(renamed_files.size() + renamed_dirs.size() == renamed_srcs.size());
441 I(renamed_files.size() + renamed_dirs.size() == renamed_dsts.size());
442
443 check_sets_disjoint(deleted_files, deleted_dirs);
444 check_sets_disjoint(deleted_files, renamed_srcs);
445 check_sets_disjoint(deleted_dirs, renamed_srcs);
446
447 check_sets_disjoint(added_files, renamed_dsts);
448}
449
450change_set::change_set(change_set const & other)
451{
452 other.check_sane();
453 rearrangement = other.rearrangement;
454 deltas = other.deltas;
455}
456
457change_set const &change_set::operator=(change_set const & other)
458{
459 other.check_sane();
460 rearrangement = other.rearrangement;
461 deltas = other.deltas;
462 return *this;
463}
464
465void
466change_set::check_sane() const
467{
468 // FIXME: extend this as you manage to think of more invariants
469 // which are cheap enough to check at this level.
470
471 rearrangement.check_sane(this->deltas);
472
473 for (std::set<file_path>::const_iterator i = rearrangement.added_files.begin();
474 i != rearrangement.added_files.end(); ++i)
475 {
476 delta_map::const_iterator j = deltas.find(*i);
477 if (!global_sanity.relaxed)
478 {
479 I(j != deltas.end());
480 I(null_id(delta_entry_src(j)));
481 I(!null_id(delta_entry_dst(j)));
482 }
483 }
484
485 for (delta_map::const_iterator i = deltas.begin();
486 i != deltas.end(); ++i)
487 {
488 if (!global_sanity.relaxed)
489 {
490 I(!null_name(delta_entry_path(i)));
491 I(!null_id(delta_entry_dst(i)));
492 I(!(delta_entry_src(i) == delta_entry_dst(i)));
493 if (null_id(delta_entry_src(i)))
494 I(rearrangement.added_files.find(delta_entry_path(i))
495 != rearrangement.added_files.end());
496 }
497 }
498
499}
500
501static void
502sanity_check_path_item(path_item const & pi)
503{
504}
505
506static void
507confirm_proper_tree(path_state const & ps)
508{
509 std::map<tid,bool> confirmed;
510 I(ps.find(root_tid) == ps.end());
511 for (path_state::const_iterator i = ps.begin(); i != ps.end(); ++i)
512 {
513 tid curr = i->first;
514 path_item item = i->second;
515 std::map<tid,bool> ancs;
516
517 while (confirmed.find(curr) == confirmed.end())
518 {
519 sanity_check_path_item(item);
520 I(ancs.find(curr) == ancs.end());
521 ancs.insert(std::make_pair(curr,true));
522 if (path_item_parent(item) == root_tid)
523 break;
524 else
525 {
526 curr = path_item_parent(item);
527 path_state::const_iterator j = ps.find(curr);
528 I(j != ps.end());
529
530 // if we're null, our parent must also be null
531 if (null_name(item.name))
532 I(null_name(path_state_item(j).name));
533
534 item = path_state_item(j);
535 I(path_item_type(item) == ptype_directory);
536 }
537 }
538 std::copy(ancs.begin(), ancs.end(),
539 inserter(confirmed, confirmed.begin()));
540 }
541 I(confirmed.find(root_tid) == confirmed.end());
542}
543
544static void
545confirm_unique_entries_in_directories(path_state const & ps)
546{
547 std::map<std::pair<tid,path_component>, bool> entries;
548 for (path_state::const_iterator i = ps.begin(); i != ps.end(); ++i)
549 {
550 if (null_name(path_item_name(i->second)))
551 {
552 I(path_item_parent(i->second) == root_tid);
553 continue;
554 }
555
556 std::pair<tid,path_component> p = std::make_pair(path_item_parent(i->second),
557 path_item_name(i->second));
558 I(entries.find(p) == entries.end());
559 entries.insert(std::make_pair(p,true));
560 }
561}
562
563static void
564sanity_check_path_state(path_state const & ps)
565{
566 confirm_proper_tree(ps);
567 confirm_unique_entries_in_directories(ps);
568}
569
570path_item::path_item(tid p, ptype t, path_component n)
571 : parent(p), ty(t), name(n)
572{
573 sanity_check_path_item(*this);
574}
575
576path_item::path_item(path_item const & other)
577 : parent(other.parent), ty(other.ty), name(other.name)
578{
579 sanity_check_path_item(*this);
580}
581
582path_item const & path_item::operator=(path_item const & other)
583{
584 parent = other.parent;
585 ty = other.ty;
586 name = other.name;
587 sanity_check_path_item(*this);
588 return *this;
589}
590
591bool path_item::operator==(path_item const & other) const
592{
593 return this->parent == other.parent &&
594 this->ty == other.ty &&
595 this->name == other.name;
596}
597
598
599static void
600check_states_agree(path_state const & p1,
601 path_state const & p2)
602{
603 path_analysis pa;
604 pa.first = p1;
605 pa.second = p2;
606 // dump_analysis("agreement", pa);
607 for (path_state::const_iterator i = p1.begin(); i != p1.end(); ++i)
608 {
609 path_state::const_iterator j = p2.find(i->first);
610 I(j != p2.end());
611 I(path_item_type(i->second) == path_item_type(j->second));
612 // I(! (null_name(path_item_name(i->second))
613 // &&
614 // null_name(path_item_name(j->second))));
615 }
616}
617
618void
619sanity_check_path_analysis(path_analysis const & pr)
620{
621 sanity_check_path_state(pr.first);
622 sanity_check_path_state(pr.second);
623 check_states_agree(pr.first, pr.second);
624 check_states_agree(pr.second, pr.first);
625}
626
627
628// construction helpers
629
630static boost::shared_ptr<directory_node>
631new_dnode()
632{
633 return boost::shared_ptr<directory_node>(new directory_node());
634}
635
636static boost::shared_ptr<directory_node>
637dnode(directory_map & dir, tid t)
638{
639 boost::shared_ptr<directory_node> node;
640 directory_map::const_iterator dirent = dir.find(t);
641 if (dirent == dir.end())
642 {
643 node = new_dnode();
644 dir.insert(std::make_pair(t, node));
645 }
646 else
647 node = dirent->second;
648 return node;
649}
650
651static void
652get_full_path(path_state const & state,
653 tid t,
654 std::vector<path_component> & pth)
655{
656 std::vector<path_component> tmp;
657 while(t != root_tid)
658 {
659 path_state::const_iterator i = state.find(t);
660 I(i != state.end());
661 tmp.push_back(path_item_name(i->second));
662 t = path_item_parent(i->second);
663 }
664 pth.clear();
665 std::copy(tmp.rbegin(), tmp.rend(), inserter(pth, pth.begin()));
666}
667
668static void
669get_full_path(path_state const & state,
670 tid t,
671 file_path & pth)
672{
673 std::vector<path_component> tmp;
674 get_full_path(state, t, tmp);
675 // L(F("got %d-entry path for tid %d\n") % tmp.size() % t);
676 compose_path(tmp, pth);
677}
678
679static void
680clear_rearrangement(change_set::path_rearrangement & pr)
681{
682 pr.deleted_files.clear();
683 pr.deleted_dirs.clear();
684 pr.renamed_files.clear();
685 pr.renamed_dirs.clear();
686 pr.added_files.clear();
687}
688
689static void
690clear_change_set(change_set & cs)
691{
692 clear_rearrangement(cs.rearrangement);
693 cs.deltas.clear();
694}
695
696static void
697compose_rearrangement(path_analysis const & pa,
698 change_set::path_rearrangement & pr)
699{
700 clear_rearrangement(pr);
701
702 for (path_state::const_iterator i = pa.first.begin();
703 i != pa.first.end(); ++i)
704 {
705 tid curr(path_state_tid(i));
706 std::vector<path_component> old_name, new_name;
707 file_path old_path, new_path;
708
709 path_state::const_iterator j = pa.second.find(curr);
710 I(j != pa.second.end());
711 path_item old_item(path_state_item(i));
712 path_item new_item(path_state_item(j));
713
714 // compose names
715 if (!null_name(path_item_name(old_item)))
716 {
717 get_full_path(pa.first, curr, old_name);
718 compose_path(old_name, old_path);
719 }
720
721 if (!null_name(path_item_name(new_item)))
722 {
723 get_full_path(pa.second, curr, new_name);
724 compose_path(new_name, new_path);
725 }
726
727 if (old_path == new_path)
728 {
729 L(F("skipping preserved %s %d : '%s'\n")
730 % (path_item_type(old_item) == ptype_directory ? "directory" : "file")
731 % curr % old_path);
732 continue;
733 }
734
735 L(F("analyzing %s %d : '%s' -> '%s'\n")
736 % (path_item_type(old_item) == ptype_directory ? "directory" : "file")
737 % curr % old_path % new_path);
738
739 if (null_name(path_item_name(old_item)))
740 {
741 // an addition (which must be a file, not a directory)
742 I(! null_name(path_item_name(new_item)));
743 I(path_item_type(new_item) != ptype_directory);
744 pr.added_files.insert(new_path);
745 }
746 else if (null_name(path_item_name(new_item)))
747 {
748 // a deletion
749 I(! null_name(path_item_name(old_item)));
750 switch (path_item_type(new_item))
751 {
752 case ptype_directory:
753 pr.deleted_dirs.insert(old_path);
754 break;
755 case ptype_file:
756 pr.deleted_files.insert(old_path);
757 break;
758 }
759 }
760 else
761 {
762 // a generic rename
763 switch (path_item_type(new_item))
764 {
765 case ptype_directory:
766 pr.renamed_dirs.insert(std::make_pair(old_path, new_path));
767 break;
768 case ptype_file:
769 pr.renamed_files.insert(std::make_pair(old_path, new_path));
770 break;
771 }
772 }
773 }
774}
775
776
777
778static bool
779lookup_path(std::vector<path_component> const & pth,
780 directory_map const & dir,
781 tid & t)
782{
783 t = root_tid;
784 for (std::vector<path_component>::const_iterator i = pth.begin();
785 i != pth.end(); ++i)
786 {
787 directory_map::const_iterator dirent = dir.find(t);
788 if (dirent != dir.end())
789 {
790 boost::shared_ptr<directory_node> node = dirent->second;
791 directory_node::const_iterator entry = node->find(*i);
792 if (entry == node->end())
793 return false;
794 t = directory_entry_tid(entry);
795 }
796 else
797 return false;
798 }
799 return true;
800}
801
802static bool
803lookup_path(file_path const & pth,
804 directory_map const & dir,
805 tid & t)
806{
807 std::vector<path_component> vec;
808 split_path(pth, vec);
809 return lookup_path(vec, dir, t);
810}
811
812static tid
813ensure_entry(directory_map & dmap,
814 path_state & state,
815 tid dir_tid,
816 ptype entry_ty,
817 path_component entry,
818 tid_source & ts)
819{
820 I(! null_name(entry));
821
822 if (dir_tid != root_tid)
823 {
824 path_state::const_iterator parent = state.find(dir_tid);
825 I( parent != state.end());
826
827 // if our parent is null, we immediately become null too, and attach to
828 // the root node (where all null entries reside)
829 if (null_name(path_item_name(path_state_item(parent))))
830 {
831 tid new_tid = ts.next();
832 state.insert(std::make_pair(new_tid, path_item(root_tid, entry_ty, make_null_component())));
833 return new_tid;
834 }
835 }
836
837 boost::shared_ptr<directory_node> node = dnode(dmap, dir_tid);
838 directory_node::const_iterator node_entry = node->find(entry);
839
840 if (node_entry != node->end())
841 {
842 I(node_entry->second.first == entry_ty);
843 return node_entry->second.second;
844 }
845 else
846 {
847 tid new_tid = ts.next();
848 state.insert(std::make_pair(new_tid, path_item(dir_tid, entry_ty, entry)));
849 node->insert(std::make_pair(entry, std::make_pair(entry_ty, new_tid)));
850 return new_tid;
851 }
852}
853
854static tid
855ensure_dir_in_map (std::vector<path_component> pth,
856 directory_map & dmap,
857 path_state & state,
858 tid_source & ts)
859{
860 tid dir_tid = root_tid;
861 for (std::vector<path_component>::const_iterator p = pth.begin();
862 p != pth.end(); ++p)
863 {
864 dir_tid = ensure_entry(dmap, state, dir_tid,
865 ptype_directory, *p, ts);
866 }
867 return dir_tid;
868}
869
870static tid
871ensure_dir_in_map (file_path const & path,
872 directory_map & dmap,
873 path_state & state,
874 tid_source & ts)
875{
876 std::vector<path_component> components;
877 split_path(path, components);
878 return ensure_dir_in_map(components, dmap, state, ts);
879}
880
881static tid
882ensure_file_in_map (file_path const & path,
883 directory_map & dmap,
884 path_state & state,
885 tid_source & ts)
886{
887 std::vector<path_component> prefix;
888 path_component leaf_path;
889 split_path(path, prefix, leaf_path);
890
891 I(! null_name(leaf_path));
892 tid dir_tid = ensure_dir_in_map(prefix, dmap, state, ts);
893 return ensure_entry(dmap, state, dir_tid, ptype_file, leaf_path, ts);
894}
895
896static void
897ensure_entries_exist (path_state const & self_state,
898 directory_map & other_dmap,
899 path_state & other_state,
900 tid_source & ts)
901{
902 for (path_state::const_iterator i = self_state.begin();
903 i != self_state.end(); ++i)
904 {
905 if (other_state.find(path_state_tid(i)) != other_state.end())
906 continue;
907
908 if (null_name(path_item_name(path_state_item(i))))
909 continue;
910
911 file_path full;
912 get_full_path(self_state, path_state_tid(i), full);
913 switch (path_item_type(path_state_item(i)))
914 {
915 case ptype_directory:
916 ensure_dir_in_map(full, other_dmap, other_state, ts);
917 break;
918
919 case ptype_file:
920 ensure_file_in_map(full, other_dmap, other_state, ts);
921 break;
922 }
923 }
924}
925
926
927static void
928apply_state_renumbering(state_renumbering const & renumbering,
929 path_state & state)
930{
931 sanity_check_path_state(state);
932 path_state tmp(state);
933 state.clear();
934
935 for (path_state::const_iterator i = tmp.begin(); i != tmp.end(); ++i)
936 {
937 path_item item = path_state_item(i);
938 tid t = path_state_tid(i);
939
940 state_renumbering::const_iterator j = renumbering.find(t);
941 if (j != renumbering.end())
942 t = j->second;
943
944 j = renumbering.find(item.parent);
945 if (j != renumbering.end())
946 item.parent = j->second;
947
948 state.insert(std::make_pair(t, item));
949 }
950 sanity_check_path_state(state);
951}
952
953static void
954apply_state_renumbering(state_renumbering const & renumbering,
955 path_analysis & pa)
956{
957 apply_state_renumbering(renumbering, pa.first);
958 apply_state_renumbering(renumbering, pa.second);
959}
960
961
962// this takes a path in the path space defined by input_dir and rebuilds it
963// in the path space defined by output_space, including any changes to
964// parents in the path (rather than directly to the path leaf name). it
965// therefore *always* succeeds; sometimes it does nothing if there's no
966// affected parent, but you always get a rebuilt path in the output space.
967
968static void
969reconstruct_path(file_path const & input,
970 directory_map const & input_dir,
971 path_state const & output_space,
972 file_path & output)
973{
974 std::vector<path_component> vec;
975 std::vector<path_component> rebuilt;
976
977 // L(F("reconstructing path '%s' under analysis\n") % input);
978
979 split_path(input, vec);
980
981 tid t = root_tid;
982 std::vector<path_component>::const_iterator pth = vec.begin();
983 while (pth != vec.end())
984 {
985 directory_map::const_iterator dirent = input_dir.find(t);
986 if (dirent == input_dir.end())
987 break;
988
989 boost::shared_ptr<directory_node> node = dirent->second;
990 directory_node::const_iterator entry = node->find(*pth);
991 if (entry == node->end())
992 break;
993
994 {
995 // check to see if this is the image of an added or deleted entry
996 // (i.e. null name in output space), if so it terminates our
997 // search.
998 path_state::const_iterator i = output_space.find(directory_entry_tid(entry));
999 I(i != output_space.end());
1000 if (null_name(path_item_name(path_state_item(i))))
1001 {
1002 // L(F("input path element '%s' is null in output space, mapping truncated\n") % *pth);
1003 break;
1004 }
1005 }
1006
1007 // L(F("resolved entry '%s' in reconstruction\n") % *pth);
1008 ++pth;
1009 t = directory_entry_tid(entry);
1010
1011 if (directory_entry_type(entry) != ptype_directory)
1012 break;
1013 }
1014
1015 get_full_path(output_space, t, rebuilt);
1016
1017 while(pth != vec.end())
1018 {
1019 // L(F("copying tail entry '%s' in reconstruction\n") % *pth);
1020 rebuilt.push_back(*pth);
1021 ++pth;
1022 }
1023
1024 compose_path(rebuilt, output);
1025 // L(F("reconstructed path '%s' as '%s'\n") % input % output);
1026}
1027
1028
1029static void
1030build_directory_map(path_state const & state,
1031 directory_map & dir)
1032{
1033 sanity_check_path_state(state);
1034 dir.clear();
1035 // L(F("building directory map for %d entries\n") % state.size());
1036 for (path_state::const_iterator i = state.begin(); i != state.end(); ++i)
1037 {
1038 tid curr = path_state_tid(i);
1039 path_item item = path_state_item(i);
1040 tid parent = path_item_parent(item);
1041 path_component name = path_item_name(item);
1042 ptype type = path_item_type(item);
1043 // L(F("adding entry %s (%s %d) to directory node %d\n")
1044 // % name % (type == ptype_directory ? "dir" : "file") % curr % parent);
1045 dnode(dir, parent)->insert(std::make_pair(name,std::make_pair(type, curr)));
1046
1047 // also, make sure to add current node if it's a directory, even if
1048 // there are no entries in it
1049 if (type == ptype_directory)
1050 dnode(dir, curr);
1051 }
1052}
1053
1054
1055void
1056analyze_rearrangement(change_set::path_rearrangement const & pr,
1057 path_analysis & pa,
1058 tid_source & ts)
1059{
1060 directory_map first_map, second_map;
1061 state_renumbering renumbering;
1062 std::set<tid> damaged_in_first, damaged_in_second;
1063
1064 pa.first.clear();
1065 pa.second.clear();
1066
1067 for (std::set<file_path>::const_iterator f = pr.deleted_files.begin();
1068 f != pr.deleted_files.end(); ++f)
1069 {
1070 tid x = ensure_file_in_map(*f, first_map, pa.first, ts);
1071 pa.second.insert(std::make_pair(x, path_item(root_tid, ptype_file, make_null_component())));
1072 damaged_in_first.insert(x);
1073 }
1074
1075 for (std::set<file_path>::const_iterator d = pr.deleted_dirs.begin();
1076 d != pr.deleted_dirs.end(); ++d)
1077 {
1078 tid x = ensure_dir_in_map(*d, first_map, pa.first, ts);
1079 pa.second.insert(std::make_pair(x, path_item(root_tid, ptype_directory, make_null_component())));
1080 damaged_in_first.insert(x);
1081 }
1082
1083 for (std::map<file_path,file_path>::const_iterator rf = pr.renamed_files.begin();
1084 rf != pr.renamed_files.end(); ++rf)
1085 {
1086 tid a = ensure_file_in_map(rf->first, first_map, pa.first, ts);
1087 tid b = ensure_file_in_map(rf->second, second_map, pa.second, ts);
1088 I(renumbering.find(a) == renumbering.end());
1089 renumbering.insert(std::make_pair(b,a));
1090 damaged_in_first.insert(a);
1091 damaged_in_second.insert(b);
1092 }
1093
1094 for (std::map<file_path,file_path>::const_iterator rd = pr.renamed_dirs.begin();
1095 rd != pr.renamed_dirs.end(); ++rd)
1096 {
1097 tid a = ensure_dir_in_map(rd->first, first_map, pa.first, ts);
1098 tid b = ensure_dir_in_map(rd->second, second_map, pa.second, ts);
1099 I(renumbering.find(a) == renumbering.end());
1100 renumbering.insert(std::make_pair(b,a));
1101 damaged_in_first.insert(a);
1102 damaged_in_second.insert(b);
1103 }
1104
1105 for (std::set<file_path>::const_iterator a = pr.added_files.begin();
1106 a != pr.added_files.end(); ++a)
1107 {
1108 tid x = ensure_file_in_map(*a, second_map, pa.second, ts);
1109 pa.first.insert(std::make_pair(x, path_item(root_tid, ptype_file, make_null_component())));
1110 damaged_in_second.insert(x);
1111 }
1112
1113 // we now have two states which probably have a number of entries in
1114 // common. we know already of an interesting set of entries they have in
1115 // common: all the renamed_foo entries. for each such renamed_foo(a,b)
1116 // entry, we made an entry in our state_renumbering of the form b->a,
1117 // while building the states.
1118
1119 // dump_analysis("analyzed", pa);
1120 // dump_renumbering("first", renumbering);
1121 apply_state_renumbering(renumbering, pa.second);
1122 build_directory_map(pa.first, first_map);
1123 build_directory_map(pa.second, second_map);
1124 renumbering.clear();
1125 // dump_analysis("renumbered once", pa);
1126
1127 // that only gets us half way, though:
1128 //
1129 // - every object which was explicitly moved (thus stayed alive) has been
1130 // renumbered in re.second to have the same tid as in re.first
1131 //
1132 // - every object which was merely mentionned in passing -- say due to
1133 // being an intermediate directory in a path -- and was not moved, still
1134 // has differing tids in re.first and re.second (or worse, may only
1135 // even have an *entry* in one of them)
1136 //
1137 // the second point here is what we need to correct: if a path didn't
1138 // move, wasn't destroyed, and wasn't added, we want it to have the same
1139 // tid. but that's a relatively easy condition to check; we've been
1140 // keeping sets of all the objects which were damaged on each side of
1141 // this business anyways.
1142
1143
1144 // pass #1 makes sure that all the entries in each state *exist* within
1145 // the other state, even if they have the wrong numbers
1146
1147 ensure_entries_exist (pa.first, second_map, pa.second, ts);
1148 ensure_entries_exist (pa.second, first_map, pa.first, ts);
1149
1150 // pass #2 identifies common un-damaged elements from 2->1 and inserts
1151 // renumberings
1152
1153 for (path_state::const_iterator i = pa.second.begin();
1154 i != pa.second.end(); ++i)
1155 {
1156 tid first_tid, second_tid;
1157 second_tid = path_state_tid(i);
1158 file_path full;
1159 if (pa.first.find(second_tid) != pa.first.end())
1160 continue;
1161 get_full_path(pa.second, second_tid, full);
1162 if (damaged_in_second.find(second_tid) != damaged_in_second.end())
1163 continue;
1164 if (null_name(path_item_name(path_state_item(i))))
1165 continue;
1166 I(lookup_path(full, first_map, first_tid));
1167 renumbering.insert(std::make_pair(second_tid, first_tid));
1168 }
1169
1170 // dump_renumbering("second", renumbering);
1171 apply_state_renumbering(renumbering, pa.second);
1172 // dump_analysis("renumbered again", pa);
1173
1174 // that should be the whole deal; if we don't have consensus at this
1175 // point we have done something wrong.
1176 sanity_check_path_analysis (pa);
1177}
1178
1179void
1180normalize_path_rearrangement(change_set::path_rearrangement & norm)
1181{
1182 path_analysis tmp;
1183 tid_source ts;
1184
1185 analyze_rearrangement(norm, tmp, ts);
1186 clear_rearrangement(norm);
1187 compose_rearrangement(tmp, norm);
1188}
1189
1190void
1191normalize_change_set(change_set & norm)
1192{
1193 normalize_path_rearrangement(norm.rearrangement);
1194 change_set::delta_map tmp = norm.deltas;
1195 for (change_set::delta_map::const_iterator i = tmp.begin();
1196 i != tmp.end(); ++i)
1197 {
1198 if (delta_entry_src(i) == delta_entry_dst(i))
1199 norm.deltas.erase(delta_entry_path(i));
1200 }
1201}
1202
1203
1204// begin stuff related to concatenation
1205
1206static void
1207index_entries(path_state const & state,
1208 std::map<file_path, tid> & files,
1209 std::map<file_path, tid> & dirs)
1210{
1211 for (path_state::const_iterator i = state.begin();
1212 i != state.end(); ++i)
1213 {
1214 file_path full;
1215 path_item item = path_state_item(i);
1216 get_full_path(state, path_state_tid(i), full);
1217
1218 if (null_name(path_item_name(item)))
1219 continue;
1220
1221 switch (path_item_type(item))
1222 {
1223 case ptype_directory:
1224 dirs.insert(std::make_pair(full, path_state_tid(i)));
1225 break;
1226
1227 case ptype_file:
1228 files.insert(std::make_pair(full, path_state_tid(i)));
1229 break;
1230 }
1231 }
1232}
1233
1234// this takes every (p1,t1) entry in b and, if (p1,t2) it exists in a,
1235// inserts (t1,t2) in the rename set. in other words, it constructs the
1236// renumbering from b->a
1237static void
1238extend_renumbering_from_path_identities(std::map<file_path, tid> const & a,
1239 std::map<file_path, tid> const & b,
1240 state_renumbering & renumbering)
1241{
1242 for (std::map<file_path, tid>::const_iterator i = b.begin();
1243 i != b.end(); ++i)
1244 {
1245 I(! null_name(i->first));
1246 std::map<file_path, tid>::const_iterator j = a.find(i->first);
1247 if (j == a.end())
1248 continue;
1249 I(renumbering.find(i->second) == renumbering.end());
1250 renumbering.insert(std::make_pair(i->second, j->second));
1251 }
1252}
1253
1254static void
1255extend_state(path_state const & src,
1256 path_state & dst)
1257{
1258 for (path_state::const_iterator i = src.begin();
1259 i != src.end(); ++i)
1260 {
1261 if (dst.find(path_state_tid(i)) == dst.end())
1262 dst.insert(*i);
1263 }
1264}
1265
1266static void
1267ensure_tids_disjoint(path_analysis const & a,
1268 path_analysis const & b)
1269{
1270 for (path_state::const_iterator i = a.first.begin();
1271 i != a.first.end(); ++i)
1272 {
1273 I(b.first.find(path_state_tid(i)) == b.first.end());
1274 }
1275 for (path_state::const_iterator i = b.first.begin();
1276 i != b.first.end(); ++i)
1277 {
1278 I(a.first.find(path_state_tid(i)) == a.first.end());
1279 }
1280}
1281
1282static void
1283extract_killed(path_analysis const & a,
1284 std::set<file_path> & killed)
1285
1286{
1287 killed.clear();
1288 directory_map first_map, second_map;
1289
1290 build_directory_map(a.first, first_map);
1291 build_directory_map(a.second, second_map);
1292
1293 for (directory_map::const_iterator i = first_map.begin();
1294 i != first_map.end(); ++i)
1295 {
1296 tid dir_tid = i->first;
1297 directory_map::const_iterator j = second_map.find(dir_tid);
1298 I(j != second_map.end());
1299
1300 // a path P = DIR/LEAF is "killed" by a path_analysis iff the
1301 // directory node named DIR in the post-state contains LEAF in the
1302 // pre-state, and does not contain LEAF in the post-state
1303
1304 boost::shared_ptr<directory_node> first_node = i->second;
1305 boost::shared_ptr<directory_node> second_node = j->second;
1306
1307 for (directory_node::const_iterator p = first_node->begin();
1308 p != first_node->end(); ++p)
1309 {
1310 path_component first_name = directory_entry_name(p);
1311 directory_node::const_iterator q = second_node->find(first_name);
1312 if (q == second_node->end())
1313 {
1314 // found a killed entry
1315 std::vector<path_component> killed_name;
1316 file_path killed_path;
1317 get_full_path(a.second, dir_tid, killed_name);
1318 killed_name.push_back(first_name);
1319 compose_path(killed_name, killed_path);
1320 killed.insert(killed_path);
1321 }
1322 }
1323 }
1324}
1325
1326static void
1327check_delta_entries_not_directories(path_analysis const & pa,
1328 change_set::delta_map const & dels)
1329{
1330 directory_map dmap;
1331 build_directory_map(pa.second, dmap);
1332 for (change_set::delta_map::const_iterator i = dels.begin();
1333 i != dels.end(); ++i)
1334 {
1335 tid delta_tid;
1336 if (lookup_path(delta_entry_path(i), dmap, delta_tid))
1337 {
1338 path_state::const_iterator j = pa.second.find(delta_tid);
1339 I(j != pa.second.end());
1340 I(path_item_type(path_state_item(j)) == ptype_file);
1341 }
1342 }
1343}
1344
1345static void
1346concatenate_disjoint_analyses(path_analysis const & a,
1347 path_analysis const & b,
1348 std::set<file_path> const & a_killed,
1349 path_analysis & concatenated)
1350{
1351 std::map<file_path, tid> a_second_files, a_second_dirs;
1352 std::map<file_path, tid> b_first_files, b_first_dirs;
1353 path_analysis a_tmp(a), b_tmp(b);
1354 state_renumbering renumbering;
1355
1356 // the trick here is that a.second and b.first supposedly refer to the
1357 // same state-of-the-world, so all we need to do is:
1358 //
1359 // - confirm that both analyses have disjoint tids
1360 // - work out which tids in b to identify with tids in a
1361 // - renumber b
1362 //
1363 // - copy a.first -> concatenated.first
1364 // - insert all elements of b.first not already in concatenated.first
1365 // - copy b.second -> concatenated.second
1366 // - insert all elements of a.second not already in concatenated.second
1367
1368 ensure_tids_disjoint(a_tmp, b_tmp);
1369
1370 index_entries(a_tmp.second, a_second_files, a_second_dirs);
1371 index_entries(b_tmp.first, b_first_files, b_first_dirs);
1372
1373 {
1374 std::set<file_path>
1375 a_second_file_set, a_second_dir_set,
1376 b_first_file_set, b_first_dir_set;
1377
1378 extract_first(a_second_files, a_second_file_set);
1379 extract_first(a_second_dirs, a_second_dir_set);
1380 extract_first(b_first_files, b_first_file_set);
1381 extract_first(b_first_dirs, b_first_dir_set);
1382
1383 // check that there are no entry-type mismatches
1384 check_sets_disjoint(a_second_file_set, b_first_dir_set);
1385 check_sets_disjoint(a_second_dir_set, b_first_file_set);
1386
1387 // check that there's no use of killed entries
1388 check_sets_disjoint(a_killed, b_first_dir_set);
1389 check_sets_disjoint(a_killed, b_first_file_set);
1390 }
1391
1392 extend_renumbering_from_path_identities(a_second_files, b_first_files, renumbering);
1393 extend_renumbering_from_path_identities(a_second_dirs, b_first_dirs, renumbering);
1394
1395 // dump_analysis("state A", a_tmp);
1396 // dump_analysis("state B", b_tmp);
1397 // dump_renumbering("concatenation", renumbering);
1398 apply_state_renumbering(renumbering, b_tmp);
1399
1400 concatenated.first = a_tmp.first;
1401 concatenated.second = b_tmp.second;
1402
1403 extend_state(b_tmp.first, concatenated.first);
1404 extend_state(a_tmp.second, concatenated.second);
1405
1406 sanity_check_path_analysis(concatenated);
1407}
1408
1409void
1410concatenate_rearrangements(change_set::path_rearrangement const & a,
1411 change_set::path_rearrangement const & b,
1412 change_set::path_rearrangement & concatenated)
1413{
1414 a.check_sane();
1415 b.check_sane();
1416 concatenated = change_set::path_rearrangement();
1417
1418 tid_source ts;
1419 path_analysis a_analysis, b_analysis, concatenated_analysis;
1420
1421 analyze_rearrangement(a, a_analysis, ts);
1422 analyze_rearrangement(b, b_analysis, ts);
1423
1424 std::set<file_path> a_killed;
1425 extract_killed(a_analysis, a_killed);
1426
1427 concatenate_disjoint_analyses(a_analysis,
1428 b_analysis,
1429 a_killed,
1430 concatenated_analysis);
1431
1432 compose_rearrangement(concatenated_analysis,
1433 concatenated);
1434
1435 concatenated.check_sane();
1436}
1437
1438void
1439concatenate_change_sets(change_set const & a,
1440 change_set const & b,
1441 change_set & concatenated)
1442{
1443 a.check_sane();
1444 b.check_sane();
1445
1446 L(F("concatenating change sets\n"));
1447
1448 tid_source ts;
1449 path_analysis a_analysis, b_analysis, concatenated_analysis;
1450
1451 analyze_rearrangement(a.rearrangement, a_analysis, ts);
1452 analyze_rearrangement(b.rearrangement, b_analysis, ts);
1453
1454 std::set<file_path> a_killed;
1455 extract_killed(a_analysis, a_killed);
1456
1457 concatenate_disjoint_analyses(a_analysis,
1458 b_analysis,
1459 a_killed,
1460 concatenated_analysis);
1461
1462 compose_rearrangement(concatenated_analysis,
1463 concatenated.rearrangement);
1464
1465 // now process the deltas
1466
1467 concatenated.deltas.clear();
1468 directory_map a_dst_map, b_src_map;
1469 L(F("concatenating %d and %d deltas\n")
1470 % a.deltas.size() % b.deltas.size());
1471 build_directory_map(a_analysis.second, a_dst_map);
1472 build_directory_map(b_analysis.first, b_src_map);
1473
1474 // first rename a's deltas under the rearrangement of b
1475 for (change_set::delta_map::const_iterator del = a.deltas.begin();
1476 del != a.deltas.end(); ++del)
1477 {
1478 file_path new_pth;
1479 L(F("processing delta on %s\n") % delta_entry_path(del));
1480
1481 // work out the name of entry in b.first
1482 reconstruct_path(delta_entry_path(del), b_src_map, b_analysis.second, new_pth);
1483 L(F("delta on %s in first changeset renamed to %s\n")
1484 % delta_entry_path(del) % new_pth);
1485
1486 if (b.rearrangement.has_deleted_file(delta_entry_path(del)))
1487 // the delta should be removed if the file is going to be deleted
1488 L(F("discarding delta [%s]->[%s] for deleted file '%s'\n")
1489 % delta_entry_src(del) % delta_entry_dst(del) % delta_entry_path(del));
1490 else
1491 concatenated.deltas.insert(std::make_pair(new_pth,
1492 std::make_pair(delta_entry_src(del),
1493 delta_entry_dst(del))));
1494 }
1495
1496 // next fuse any deltas id1->id2 and id2->id3 to id1->id3
1497 for (change_set::delta_map::const_iterator del = b.deltas.begin();
1498 del != b.deltas.end(); ++del)
1499 {
1500
1501 file_path del_pth = delta_entry_path(del);
1502 change_set::delta_map::const_iterator existing =
1503 concatenated.deltas.find(del_pth);
1504 if (existing != concatenated.deltas.end())
1505 {
1506 L(F("fusing deltas on %s : %s -> %s and %s -> %s\n")
1507 % del_pth
1508 % delta_entry_src(existing)
1509 % delta_entry_dst(existing)
1510 % delta_entry_src(del)
1511 % delta_entry_dst(del));
1512 I(delta_entry_dst(existing) == delta_entry_src(del));
1513 std::pair<file_id, file_id> fused = std::make_pair(delta_entry_src(existing),
1514 delta_entry_dst(del));
1515 concatenated.deltas.erase(del_pth);
1516 concatenated.deltas.insert(std::make_pair((del_pth), fused));
1517 }
1518 else
1519 {
1520 L(F("delta on %s in second changeset copied forward\n") % del_pth);
1521 // in general don't want deltas on deleted files. however if a
1522 // file has been deleted then re-added, then a delta is valid
1523 // (it applies to the newly-added file)
1524 if (!b.rearrangement.has_deleted_file(del_pth)
1525 || b.rearrangement.has_added_file(del_pth)
1526 || b.rearrangement.has_renamed_file_dst(del_pth))
1527 concatenated.deltas.insert(*del);
1528 }
1529 }
1530
1531 normalize_change_set(concatenated);
1532 concatenated.check_sane();
1533
1534 L(F("finished concatenation\n"));
1535}
1536
1537// end stuff related to concatenation
1538
1539
1540// begin stuff related to merging
1541
1542
1543static void
1544extend_renumbering_via_added_files(path_analysis const & a,
1545 path_analysis const & b,
1546 state_renumbering & existing_renumbering,
1547 state_renumbering & renumbering)
1548{
1549 directory_map a_second_map;
1550 build_directory_map(a.second, a_second_map);
1551
1552 for (path_state::const_iterator i = b.first.begin();
1553 i != b.first.end(); ++i)
1554 {
1555 path_item item = path_state_item(i);
1556 if (path_item_type(item) == ptype_file && null_name(path_item_name(item)))
1557 {
1558 path_state::const_iterator j = b.second.find(path_state_tid(i));
1559 I(j != b.second.end());
1560 path_component leaf_name = path_item_name(path_state_item(j));
1561
1562 I(path_item_type(path_state_item(j)) == ptype_file);
1563 if (! null_name(leaf_name))
1564 {
1565 tid added_parent_tid = path_item_parent(path_state_item(j));
1566 state_renumbering::const_iterator ren = existing_renumbering.find(added_parent_tid);
1567 if (ren != existing_renumbering.end())
1568 added_parent_tid = ren->second;
1569 directory_map::const_iterator dirent = a_second_map.find(added_parent_tid);
1570 if (dirent != a_second_map.end())
1571 {
1572 boost::shared_ptr<directory_node> node = dirent->second;
1573 directory_node::const_iterator entry = node->find(leaf_name);
1574 if (entry != node->end() && directory_entry_type(entry) == ptype_file)
1575 {
1576 I(renumbering.find(path_state_tid(i)) == renumbering.end());
1577 renumbering.insert(std::make_pair(path_state_tid(i),
1578 directory_entry_tid(entry)));
1579 }
1580 }
1581 }
1582 }
1583 }
1584}
1585
1586static bool
1587find_item(tid t, path_state const & ps,
1588 path_item & item)
1589{
1590 path_state::const_iterator i = ps.find(t);
1591 if (i == ps.end())
1592 return false;
1593 item = path_state_item(i);
1594 return true;
1595}
1596
1597static bool
1598find_items(tid t, path_analysis const & pa,
1599 path_item & first, path_item & second)
1600{
1601 if (find_item(t, pa.first, first))
1602 {
1603 I(find_item(t, pa.second, second));
1604 I(path_item_type(first) == path_item_type(second));
1605 return true;
1606 }
1607 else
1608 {
1609 I(!find_item(t, pa.second, second));
1610 return false;
1611 }
1612}
1613
1614static void
1615resolve_conflict(tid t, ptype ty,
1616 path_analysis const & a_tmp,
1617 path_analysis const & b_tmp,
1618 path_item & resolved,
1619 path_state & resolved_conflicts,
1620 app_state & app)
1621{
1622 path_state::const_iterator i = resolved_conflicts.find(t);
1623
1624 path_item a_item, b_item;
1625 find_item(t, a_tmp.second, a_item);
1626 find_item(t, b_tmp.second, b_item);
1627
1628 file_path anc, a, b, res;
1629 get_full_path(a_tmp.first, t, anc);
1630 get_full_path(a_tmp.second, t, a);
1631 get_full_path(b_tmp.second, t, b);
1632
1633 if (i != resolved_conflicts.end())
1634 {
1635 resolved = path_state_item(i);
1636 }
1637 else if (null_name(path_item_name(a_item)) &&
1638 ! null_name(path_item_name(b_item)))
1639 {
1640 L(F("delete of %s dominates rename to %s\n") % anc % b);
1641 resolved = a_item;
1642 resolved_conflicts.insert(std::make_pair(t, resolved));
1643 }
1644 else if (null_name(path_item_name(b_item)) &&
1645 ! null_name(path_item_name(a_item)))
1646 {
1647 L(F("delete of %s dominates rename to %s\n") % anc % a);
1648 resolved = b_item;
1649 resolved_conflicts.insert(std::make_pair(t, resolved));
1650 }
1651 else
1652 {
1653 switch (ty)
1654 {
1655 case ptype_file:
1656 N(app.lua.hook_resolve_file_conflict(anc, a, b, res),
1657 F("unable to resolve file conflict '%s' -> '%s' vs. '%s'") % anc % a % b);
1658 break;
1659 case ptype_directory:
1660 N(app.lua.hook_resolve_dir_conflict(anc, a, b, res),
1661 F("unable to resolve dir conflict '%s' -> '%s' vs. '%s'") % anc % a % b);
1662 break;
1663 }
1664
1665 N((res == a || res == b),
1666 F("illegal conflict resolution '%s', wanted '%s' or '%s'\n") % res % a % b);
1667
1668 if (res == a)
1669 I(find_item(t, a_tmp.second, resolved));
1670 else
1671 I(find_item(t, b_tmp.second, resolved));
1672
1673 resolved_conflicts.insert(std::make_pair(t, resolved));
1674 }
1675}
1676
1677static void
1678ensure_no_rename_clobbers(path_analysis const & a,
1679 path_analysis const & b)
1680{
1681 // there is a special non-mergable pair of changes which we need
1682 // to identify here:
1683 //
1684 // tid i : x -> y in change A
1685 // tid j : z -> x in change B
1686 //
1687 // on the surface it looks like it ought to be mergable, since there is
1688 // no conflict in the tids. except for one problem: B effectively
1689 // clobbered i with j. there is nothing you can append to change B to
1690 // revive the identity of i; in fact you risk having i and j identified
1691 // if you form the naive merge concatenation BA. indeed, since A and B
1692 // both supposedly start in the same state (in which i occupies name x),
1693 // it really ought not to be possible to form B; you should have to
1694 // accompany it with some sort of statement about the fate of i.
1695 //
1696 // as it stands, we're going to fault when we see this. if it turns out
1697 // that there's a legal way of constructing such changes, one option is
1698 // to synthesize a delete of i in B; essentially read "z->x" as an
1699 // implicit "delete x first if it exists in post-state".
1700 //
1701 // however, for the time being this is a fault because we believe they
1702 // should be globally illegal clobbers.
1703
1704 directory_map b_first_map, b_second_map;
1705 build_directory_map (b.first, b_first_map);
1706 build_directory_map (b.second, b_second_map);
1707 tid a_tid, b_tid;
1708
1709 for (path_state::const_iterator i = a.first.begin();
1710 i != a.first.end(); ++i)
1711 {
1712 file_path anc_path, a_second_path;
1713 a_tid = path_state_tid(i);
1714 get_full_path(a.first, a_tid, anc_path);
1715
1716 if (! lookup_path(anc_path, b_first_map, b_tid))
1717 {
1718 file_path b_second_path;
1719 reconstruct_path(anc_path, b_first_map, b.second, b_second_path);
1720
1721 N(! lookup_path(b_second_path, b_second_map, b_tid),
1722 (F("tid %d (%s) clobbered tid %d (%s)\n")
1723 % b_tid % b_second_path
1724 % a_tid % anc_path));
1725 }
1726 }
1727
1728}
1729
1730static void
1731project_missing_changes(path_analysis const & a_tmp,
1732 path_analysis const & b_tmp,
1733 path_analysis & b_merged,
1734 path_state & resolved_conflicts,
1735 app_state & app)
1736{
1737
1738 // for each tid t adjusted in a:
1739 // - if t exists in b:
1740 // - if the change to t in b == change in a, skip
1741 // - else resolve conflict
1742 // - if conflict resolved in favour of a, append to merged
1743 // - if resolved in favour of b, skip
1744 // - else (no t in b) insert a's change to t in merged
1745
1746 for (path_state::const_iterator i = a_tmp.first.begin();
1747 i != a_tmp.first.end(); ++i)
1748 {
1749 tid t = path_state_tid(i);
1750 path_item a_first_item, a_second_item;
1751 path_item b_first_item, b_second_item;
1752 I(find_items(t, a_tmp, a_first_item, a_second_item));
1753 if (find_items(t, b_tmp, b_first_item, b_second_item))
1754 {
1755 I(a_first_item == b_first_item);
1756 if (a_second_item == b_second_item)
1757 {
1758 L(F("skipping common change on %s (tid %d)\n")
1759 % path_item_name(a_first_item) % t);
1760 }
1761 else if (a_first_item == a_second_item)
1762 {
1763 L(F("skipping neutral change of %s -> %s (tid %d)\n")
1764 % path_item_name(a_first_item)
1765 % path_item_name(a_second_item)
1766 % t);
1767 }
1768 else if (b_first_item == b_second_item)
1769 {
1770 L(F("propagating change on %s -> %s (tid %d)\n")
1771 % path_item_name(b_first_item)
1772 % path_item_name(b_second_item)
1773 % t);
1774 b_merged.first.insert(std::make_pair(t, b_second_item));
1775 b_merged.second.insert(std::make_pair(t, a_second_item));
1776 }
1777 else
1778 {
1779 // conflict
1780 path_item resolved;
1781 resolve_conflict(t, path_item_type(a_first_item), a_tmp, b_tmp,
1782 resolved, resolved_conflicts, app);
1783
1784 if (resolved == a_second_item)
1785 {
1786 L(F("conflict detected, resolved in A's favour\n"));
1787 b_merged.first.insert(std::make_pair(t, b_second_item));
1788 b_merged.second.insert(std::make_pair(t, a_second_item));
1789 }
1790 else
1791 {
1792 L(F("conflict detected, resolved in B's favour\n"));
1793 }
1794 }
1795 }
1796 else
1797 {
1798 // there was no entry in b at all for this tid, copy it
1799 b_merged.first.insert(std::make_pair(t, a_first_item));
1800 b_merged.second.insert(std::make_pair(t, a_second_item));
1801 }
1802 }
1803
1804 // now drive through b.second's view of the directory structure, in case
1805 // some intermediate b-only directories showed up the preimages of
1806 // A-favoured conflicts.
1807 extend_state(b_tmp.second, b_merged.first);
1808 extend_state(b_merged.first, b_merged.second);
1809}
1810
1811static void
1812rebuild_analysis(path_analysis const & src,
1813 path_analysis & dst,
1814 tid_source & ts)
1815{
1816 state_renumbering renumbering;
1817
1818 for (path_state::const_iterator i = src.first.begin();
1819 i != src.first.end(); ++i)
1820 renumbering.insert(std::make_pair(path_state_tid(i), ts.next()));
1821
1822 dst = src;
1823 apply_state_renumbering(renumbering, dst);
1824}
1825
1826static void
1827merge_disjoint_analyses(path_analysis const & a,
1828 path_analysis const & b,
1829 path_analysis & a_renumbered,
1830 path_analysis & b_renumbered,
1831 path_analysis & a_merged,
1832 path_analysis & b_merged,
1833 tid_source & ts,
1834 app_state & app)
1835{
1836 // we have anc->a and anc->b and we want to construct a->merged and
1837 // b->merged, leading to the eventual identity concatenate(a,a_merged) ==
1838 // concatenate(b,b_merged).
1839
1840 path_analysis a_tmp(a), b_tmp(b);
1841 state_renumbering renumbering;
1842
1843 ensure_tids_disjoint(a_tmp, b_tmp);
1844
1845 // fault on a particular class of mal-formed changesets
1846 ensure_no_rename_clobbers(a_tmp, b_tmp);
1847 ensure_no_rename_clobbers(b_tmp, a_tmp);
1848
1849 // a.first and b.first refer to the same state-of-the-world.
1850 //
1851 // we begin by driving all the entries in a.first into b.first and vice
1852 // versa.
1853
1854 {
1855 directory_map a_first_map, b_first_map;
1856 build_directory_map(a_tmp.first, a_first_map);
1857 build_directory_map(b_tmp.first, b_first_map);
1858 ensure_entries_exist(a_tmp.first, b_first_map, b_tmp.first, ts);
1859 ensure_entries_exist(b_tmp.first, a_first_map, a_tmp.first, ts);
1860 }
1861
1862 // we then drive any of the new arrivals in a.first to a.second, and
1863 // likewise on b
1864
1865 {
1866 directory_map a_second_map, b_second_map;
1867 build_directory_map(a_tmp.second, a_second_map);
1868 build_directory_map(b_tmp.second, b_second_map);
1869 ensure_entries_exist(a_tmp.first, a_second_map, a_tmp.second, ts);
1870 ensure_entries_exist(b_tmp.first, b_second_map, b_tmp.second, ts);
1871 }
1872
1873 // we then index, identify, and renumber all the immediately apparant
1874 // entries in each side.
1875
1876 {
1877 std::map<file_path, tid> a_first_files, a_first_dirs;
1878 std::map<file_path, tid> b_first_files, b_first_dirs;
1879 index_entries(a_tmp.first, a_first_files, a_first_dirs);
1880 index_entries(b_tmp.first, b_first_files, b_first_dirs);
1881 extend_renumbering_from_path_identities(a_first_files, b_first_files, renumbering);
1882 extend_renumbering_from_path_identities(a_first_dirs, b_first_dirs, renumbering);
1883 }
1884
1885 // once renamed, b_tmp will have moved a fair bit closer to a_tmp, in
1886 // terms of tids. there is still one set of files we haven't accounted
1887 // for, however: files added in a and b.
1888
1889 {
1890 state_renumbering aux_renumbering;
1891 extend_renumbering_via_added_files(a_tmp, b_tmp, renumbering, aux_renumbering);
1892 for (state_renumbering::const_iterator i = aux_renumbering.begin();
1893 i != aux_renumbering.end(); ++i)
1894 {
1895 I(renumbering.find(i->first) == renumbering.end());
1896 renumbering.insert(*i);
1897 }
1898 }
1899
1900 // renumbering now contains a *complete* renumbering of b->a,
1901 // so we reset a_tmp and b_tmp, and renumber b_tmp under this
1902 // scheme.
1903
1904 a_tmp = a;
1905 b_tmp = b;
1906 apply_state_renumbering(renumbering, b_tmp);
1907
1908 a_renumbered = a_tmp;
1909 b_renumbered = b_tmp;
1910
1911 // now we're ready to merge (and resolve conflicts)
1912 path_state resolved_conflicts;
1913 project_missing_changes(a_tmp, b_tmp, b_merged, resolved_conflicts, app);
1914 project_missing_changes(b_tmp, a_tmp, a_merged, resolved_conflicts, app);
1915
1916 {
1917 // now check: the merge analyses, when concatenated with their
1918 // predecessors, should lead to the same composite rearrangement
1919
1920 tid_source ts_tmp;
1921 path_analysis anc_a_check, a_merge_check, a_check;
1922 path_analysis anc_b_check, b_merge_check, b_check;
1923 change_set::path_rearrangement a_re, b_re;
1924
1925 rebuild_analysis(a, anc_a_check, ts_tmp);
1926 rebuild_analysis(b, anc_b_check, ts_tmp);
1927 rebuild_analysis(a_merged, a_merge_check, ts_tmp);
1928 rebuild_analysis(b_merged, b_merge_check, ts_tmp);
1929
1930 std::set<file_path> anc_a_killed, anc_b_killed;
1931 extract_killed(anc_a_check, anc_a_killed);
1932 extract_killed(anc_b_check, anc_b_killed);
1933
1934 concatenate_disjoint_analyses(anc_a_check, a_merge_check, anc_a_killed, a_check);
1935 concatenate_disjoint_analyses(anc_b_check, b_merge_check, anc_b_killed, b_check);
1936 compose_rearrangement(a_check, a_re);
1937 compose_rearrangement(b_check, b_re);
1938 I(a_re == b_re);
1939 }
1940
1941}
1942
1943static void
1944merge_deltas(file_path const & anc_path,
1945 file_path const & left_path,
1946 file_path const & right_path,
1947 file_path const & path_in_merged,
1948 std::map<file_path, file_id> & merge_finalists,
1949 file_id const & anc,
1950 file_id const & left,
1951 file_id const & right,
1952 file_id & finalist,
1953 merge_provider & merger)
1954{
1955 std::map<file_path, file_id>::const_iterator i = merge_finalists.find(path_in_merged);
1956 if (i != merge_finalists.end())
1957 {
1958 L(F("reusing merge resolution '%s' : '%s' -> '%s'\n")
1959 % path_in_merged % anc % i->second);
1960 finalist = i->second;
1961 }
1962 else
1963 {
1964 if (null_id(anc))
1965 {
1966 N(merger.try_to_merge_files(left_path, right_path, path_in_merged, left, right, finalist),
1967 F("merge of '%s' : '%s' vs. '%s' (no common ancestor) failed")
1968 % path_in_merged % left % right);
1969 }
1970 else
1971 {
1972 N(merger.try_to_merge_files(anc_path, left_path, right_path, path_in_merged,
1973 anc, left, right, finalist),
1974 F("merge of '%s' : '%s' -> '%s' vs '%s' failed")
1975 % path_in_merged % anc % left % right);
1976 }
1977
1978 L(F("merge of '%s' : '%s' -> '%s' vs '%s' resolved to '%s'\n")
1979 % path_in_merged % anc % left % right % finalist);
1980
1981 merge_finalists.insert(std::make_pair(path_in_merged, finalist));
1982 }
1983}
1984
1985static void
1986project_missing_deltas(change_set const & a,
1987 change_set const & b,
1988 path_analysis const & a_analysis,
1989 path_analysis const & b_analysis,
1990 path_analysis const & a_merged_analysis,
1991 change_set & b_merged,
1992 merge_provider & merger,
1993 std::map<file_path, file_id> & merge_finalists)
1994{
1995 directory_map a_second_map, b_first_map, a_merged_first_map;
1996 build_directory_map(a_analysis.second, a_second_map);
1997 build_directory_map(b_analysis.first, b_first_map);
1998 build_directory_map(a_merged_analysis.first, a_merged_first_map);
1999
2000 for (change_set::delta_map::const_iterator i = a.deltas.begin();
2001 i != a.deltas.end(); ++i)
2002 {
2003 file_path path_in_merged, path_in_anc, path_in_b_second;
2004
2005 // we have a fork like this:
2006 //
2007 //
2008 // +--> [a2]
2009 // [a1==b1]
2010 // +--> [b2]
2011 //
2012 // and we have a delta applied to a file in a2. we want to
2013 // figure out what to call this delta's path in b2. this means
2014 // reconstructing it in a1==b1, then reconstructing it *again*
2015 // in b2.
2016
2017 // first work out what the path in a.first == b.first is
2018 reconstruct_path(delta_entry_path(i), a_second_map,
2019 a_analysis.first, path_in_anc);
2020
2021 // first work out what the path in b.second is
2022 reconstruct_path(path_in_anc, b_first_map,
2023 b_analysis.second, path_in_b_second);
2024
2025 // then work out what the path in merged is
2026 reconstruct_path(delta_entry_path(i), a_merged_first_map,
2027 a_merged_analysis.second, path_in_merged);
2028
2029 // now check to see if there was a delta on the b.second name in b
2030 change_set::delta_map::const_iterator j = b.deltas.find(path_in_b_second);
2031
2032 if (j == b.deltas.end())
2033 {
2034 // if not, copy ours over using the merged name
2035 L(F("merge is copying delta '%s' : '%s' -> '%s'\n")
2036 % path_in_merged % delta_entry_src(i) % delta_entry_dst(i));
2037 I(b.deltas.find(path_in_merged) == b.deltas.end());
2038 if (b.rearrangement.has_deleted_file(path_in_merged))
2039 // if the file was deleted on the other fork of the merge, then
2040 // we don't want to keep this delta.
2041 L(F("skipping delta '%s'->'%s' on deleted file '%s'\n")
2042 % delta_entry_src(i) % delta_entry_dst(i) % path_in_merged);
2043 else
2044 b_merged.apply_delta(path_in_merged, delta_entry_src(i), delta_entry_dst(i));
2045 }
2046 else
2047 {
2048 // if so, either...
2049
2050 if (!(delta_entry_src(i) == delta_entry_src(j)))
2051 {
2052 // This is a bit of a corner case where a file was added then deleted on one
2053 // of the forks. The src for the addition fork will be null_id, but the src
2054 // for the other fork will be the ancestor file's id.
2055
2056 // if neither of the forks involved a file addition delta (null_id to something)
2057 // then something bad happened.
2058 I(null_id(delta_entry_src(i)) || null_id(delta_entry_src(j)));
2059
2060 if (null_id(delta_entry_src(i)))
2061 {
2062 // ... use the delta from 'a'
2063 // 'a' change_set included a delta []->[...], ie file added. We want to
2064 // follow this fork so it gets added to the b_merged changeset
2065 L(F("propagating new file addition delta on '%s' : '%s' -> '%s'\n")
2066 % path_in_merged
2067 % delta_entry_src(j)
2068 % delta_entry_dst(i));
2069 b_merged.apply_delta(path_in_merged, delta_entry_src(i), delta_entry_dst(i));
2070 }
2071 else if (null_id(delta_entry_src(j)))
2072 {
2073 // ... ignore the delta
2074 // 'b' change_set included a delta []->[...], ie file added. We don't need
2075 // to add it to the b_merged changeset, since any delta in 'a' will be
2076 // ignored (as 'b' includes deletions).
2077 L(F("skipping new file addition delta on '%s' : '' -> '%s'\n")
2078 % path_in_merged
2079 % delta_entry_dst(j));
2080 }
2081 }
2082 else if (delta_entry_dst(i) == delta_entry_dst(j))
2083 {
2084 // ... absorb identical deltas
2085 L(F("skipping common delta '%s' : '%s' -> '%s'\n")
2086 % path_in_merged % delta_entry_src(i) % delta_entry_dst(i));
2087 }
2088
2089 else if (delta_entry_src(i) == delta_entry_dst(i))
2090 {
2091 L(F("skipping neutral delta on '%s' : %s -> %s\n")
2092 % delta_entry_path(i)
2093 % delta_entry_src(i)
2094 % delta_entry_dst(i));
2095 }
2096
2097 else if (delta_entry_src(j) == delta_entry_dst(j))
2098 {
2099 L(F("propagating unperturbed delta on '%s' : '%s' -> '%s'\n")
2100 % delta_entry_path(i)
2101 % delta_entry_src(i)
2102 % delta_entry_dst(i));
2103 b_merged.apply_delta(path_in_merged, delta_entry_dst(j), delta_entry_dst(i));
2104 }
2105
2106 else
2107 {
2108 // ... or resolve conflict
2109 L(F("merging delta '%s' : '%s' -> '%s' vs. '%s'\n")
2110 % path_in_merged % delta_entry_src(i) % delta_entry_dst(i) % delta_entry_dst(j));
2111 file_id finalist;
2112
2113 merge_deltas(path_in_anc,
2114 delta_entry_path(i), // left_path
2115 delta_entry_path(j), // right_path
2116 path_in_merged,
2117 merge_finalists,
2118 delta_entry_src(i), // anc
2119 delta_entry_dst(i), // left
2120 delta_entry_dst(j), // right
2121 finalist, merger);
2122 L(F("resolved merge to '%s' : '%s' -> '%s'\n")
2123 % path_in_merged % delta_entry_src(i) % finalist);
2124
2125 // if the conflict resolved to something other than the
2126 // existing post-state of b, add a new entry to the deltas of
2127 // b finishing the job.
2128 if (! (finalist == delta_entry_dst(j)))
2129 b_merged.apply_delta(path_in_merged, delta_entry_dst(j), finalist);
2130 }
2131 }
2132 }
2133}
2134
2135
2136void
2137merge_change_sets(change_set const & a,
2138 change_set const & b,
2139 change_set & a_merged,
2140 change_set & b_merged,
2141 merge_provider & merger,
2142 app_state & app)
2143{
2144 a.check_sane();
2145 b.check_sane();
2146
2147 L(F("merging change sets\n"));
2148
2149 tid_source ts;
2150 path_analysis
2151 a_analysis, b_analysis,
2152 a_renumbered, b_renumbered,
2153 a_merged_analysis, b_merged_analysis;
2154
2155 analyze_rearrangement(a.rearrangement, a_analysis, ts);
2156 analyze_rearrangement(b.rearrangement, b_analysis, ts);
2157
2158 merge_disjoint_analyses(a_analysis, b_analysis,
2159 a_renumbered, b_renumbered,
2160 a_merged_analysis, b_merged_analysis,
2161 ts, app);
2162
2163 compose_rearrangement(a_merged_analysis,
2164 a_merged.rearrangement);
2165
2166 compose_rearrangement(b_merged_analysis,
2167 b_merged.rearrangement);
2168
2169 std::map<file_path, file_id> merge_finalists;
2170
2171 project_missing_deltas(a, b,
2172 a_renumbered, b_renumbered,
2173 a_merged_analysis,
2174 b_merged,
2175 merger, merge_finalists);
2176
2177 project_missing_deltas(b, a,
2178 b_renumbered, a_renumbered,
2179 b_merged_analysis,
2180 a_merged,
2181 merger, merge_finalists);
2182
2183 {
2184 // confirmation step
2185 change_set a_check, b_check;
2186 // dump_change_set("a", a);
2187 // dump_change_set("a_merged", a_merged);
2188 // dump_change_set("b", b);
2189 // dump_change_set("b_merged", b_merged);
2190 concatenate_change_sets(a, a_merged, a_check);
2191 concatenate_change_sets(b, b_merged, b_check);
2192 // dump_change_set("a_check", a_check);
2193 // dump_change_set("b_check", b_check);
2194 I(a_check == b_check);
2195 }
2196
2197 normalize_change_set(a_merged);
2198 normalize_change_set(b_merged);
2199
2200 a_merged.check_sane();
2201 b_merged.check_sane();
2202
2203 L(F("finished merge\n"));
2204}
2205
2206// end stuff related to merging
2207
2208void
2209invert_change_set(change_set const & a2b,
2210 manifest_map const & a_map,
2211 change_set & b2a)
2212{
2213 a2b.check_sane();
2214 tid_source ts;
2215 path_analysis a2b_analysis, b2a_analysis;
2216
2217 analyze_rearrangement(a2b.rearrangement, a2b_analysis, ts);
2218
2219 L(F("inverting change set\n"));
2220 b2a_analysis.first = a2b_analysis.second;
2221 b2a_analysis.second = a2b_analysis.first;
2222 compose_rearrangement(b2a_analysis, b2a.rearrangement);
2223
2224 b2a.deltas.clear();
2225
2226 // existing deltas are in "b space"
2227 for (path_state::const_iterator b = b2a_analysis.first.begin();
2228 b != b2a_analysis.first.end(); ++b)
2229 {
2230 path_state::const_iterator a = b2a_analysis.second.find(path_state_tid(b));
2231 I(a != b2a_analysis.second.end());
2232 if (path_item_type(path_state_item(b)) == ptype_file)
2233 {
2234 file_path b_pth, a_pth;
2235 get_full_path(b2a_analysis.first, path_state_tid(b), b_pth);
2236
2237 if (null_name(path_item_name(path_state_item(b))) &&
2238 ! null_name(path_item_name(path_state_item(a))))
2239 {
2240 // b->a represents an add in "a space"
2241 get_full_path(b2a_analysis.second, path_state_tid(a), a_pth);
2242 manifest_map::const_iterator i = a_map.find(a_pth);
2243 I(i != a_map.end());
2244 b2a.deltas.insert(std::make_pair(a_pth,
2245 std::make_pair(file_id(),
2246 manifest_entry_id(i))));
2247 L(F("converted 'delete %s' to 'add as %s' in inverse\n")
2248 % a_pth
2249 % manifest_entry_id(i));
2250 }
2251 else if (! null_name(path_item_name(path_state_item(b))) &&
2252 null_name(path_item_name(path_state_item(a))))
2253 {
2254 // b->a represents a del from "b space"
2255 get_full_path(b2a_analysis.first, path_state_tid(b), b_pth);
2256 L(F("converted add %s to delete in inverse\n") % b_pth );
2257 }
2258 else
2259 {
2260 get_full_path(b2a_analysis.first, path_state_tid(b), b_pth);
2261 get_full_path(b2a_analysis.second, path_state_tid(a), a_pth);
2262 change_set::delta_map::const_iterator del = a2b.deltas.find(b_pth);
2263 if (del == a2b.deltas.end())
2264 continue;
2265 file_id src_id(delta_entry_src(del)), dst_id(delta_entry_dst(del));
2266 L(F("converting delta %s -> %s on %s\n")
2267 % src_id % dst_id % b_pth);
2268 L(F("inverse is delta %s -> %s on %s\n")
2269 % dst_id % src_id % a_pth);
2270 b2a.deltas.insert(std::make_pair(a_pth, std::make_pair(dst_id, src_id)));
2271 }
2272 }
2273 }
2274
2275 // some deltas might not have been renamed, however. these we just invert the
2276 // direction on
2277 for (change_set::delta_map::const_iterator del = a2b.deltas.begin();
2278 del != a2b.deltas.end(); ++del)
2279 {
2280 // check to make sure this isn't the image of an add (now a delete)
2281 if (null_id(delta_entry_src(del)))
2282 continue;
2283 // check to make sure this isn't one of the already-moved deltas
2284 if (b2a.deltas.find(delta_entry_path(del)) != b2a.deltas.end())
2285 continue;
2286 b2a.deltas.insert(std::make_pair(delta_entry_path(del),
2287 std::make_pair(delta_entry_dst(del),
2288 delta_entry_src(del))));
2289 }
2290 normalize_change_set(b2a);
2291 b2a.check_sane();
2292}
2293
2294void
2295move_files_to_tmp_bottom_up(tid t,
2296 local_path const & temporary_root,
2297 path_state const & state,
2298 directory_map const & dmap)
2299{
2300 directory_map::const_iterator dirent = dmap.find(t);
2301 if (dirent != dmap.end())
2302 {
2303 boost::shared_ptr<directory_node> node = dirent->second;
2304 for (directory_node::const_iterator entry = node->begin();
2305 entry != node->end(); ++entry)
2306 {
2307 tid child = directory_entry_tid(entry);
2308 file_path path;
2309 path_item item;
2310
2311 find_item(child, state, item);
2312
2313 if (null_name(path_item_name(item)))
2314 continue;
2315
2316 // recursively move all sub-entries
2317 if (path_item_type(item) == ptype_directory)
2318 move_files_to_tmp_bottom_up(child, temporary_root, state, dmap);
2319
2320 get_full_path(state, child, path);
2321
2322 local_path src(path());
2323 local_path dst((mkpath(temporary_root())
2324 / mkpath(boost::lexical_cast<std::string>(child))).string());
2325
2326 P(F("moving %s -> %s\n") % src % dst);
2327 switch (path_item_type(item))
2328 {
2329 case ptype_file:
2330 if (file_exists(src))
2331 move_file(src, dst);
2332 break;
2333 case ptype_directory:
2334 if (directory_exists(src))
2335 move_dir(src, dst);
2336 break;
2337 }
2338 }
2339 }
2340}
2341
2342void
2343move_files_from_tmp_top_down(tid t,
2344 local_path const & temporary_root,
2345 path_state const & state,
2346 directory_map const & dmap)
2347{
2348 directory_map::const_iterator dirent = dmap.find(t);
2349 if (dirent != dmap.end())
2350 {
2351 boost::shared_ptr<directory_node> node = dirent->second;
2352 for (directory_node::const_iterator entry = node->begin();
2353 entry != node->end(); ++entry)
2354 {
2355 tid child = directory_entry_tid(entry);
2356 file_path path;
2357 path_item item;
2358
2359 find_item(child, state, item);
2360
2361 if (null_name(path_item_name(item)))
2362 continue;
2363
2364 get_full_path(state, child, path);
2365
2366 local_path src((mkpath(temporary_root())
2367 / mkpath(boost::lexical_cast<std::string>(child))).string());
2368 local_path dst(path());
2369
2370 switch (path_item_type(item))
2371 {
2372 case ptype_file:
2373 if (file_exists(src))
2374 {
2375 P(F("moving file %s -> %s\n") % src % dst);
2376 make_dir_for(path);
2377 move_file(src, dst);
2378 }
2379 break;
2380 case ptype_directory:
2381 if (directory_exists(src))
2382 {
2383 P(F("moving dir %s -> %s\n") % src % dst);
2384 make_dir_for(path);
2385 move_dir(src, dst);
2386 }
2387 break;
2388 }
2389
2390 // recursively move all sub-entries
2391 if (path_item_type(item) == ptype_directory)
2392 move_files_from_tmp_top_down(child, temporary_root, state, dmap);
2393 }
2394 }
2395}
2396
2397
2398void
2399apply_rearrangement_to_filesystem(change_set::path_rearrangement const & re,
2400 local_path const & temporary_root)
2401{
2402 re.check_sane();
2403 tid_source ts;
2404 path_analysis analysis;
2405 directory_map first_dmap, second_dmap;
2406
2407 analyze_rearrangement(re, analysis, ts);
2408 build_directory_map(analysis.first, first_dmap);
2409 build_directory_map(analysis.second, second_dmap);
2410
2411 if (analysis.first.empty())
2412 return;
2413
2414 move_files_to_tmp_bottom_up(root_tid, temporary_root,
2415 analysis.first, first_dmap);
2416
2417 move_files_from_tmp_top_down(root_tid, temporary_root,
2418 analysis.second, second_dmap);
2419}
2420
2421// application stuff
2422
2423void
2424apply_path_rearrangement(path_set const & old_ps,
2425 change_set::path_rearrangement const & pr,
2426 path_set & new_ps)
2427{
2428 pr.check_sane();
2429 change_set::path_rearrangement a, b, c;
2430 a.added_files = old_ps;
2431 concatenate_rearrangements(a, pr, c);
2432 new_ps = c.added_files;
2433}
2434
2435void
2436build_pure_addition_change_set(manifest_map const & man,
2437 change_set & cs)
2438{
2439 for (manifest_map::const_iterator i = man.begin(); i != man.end(); ++i)
2440 cs.add_file(manifest_entry_path(i), manifest_entry_id(i));
2441 cs.check_sane();
2442}
2443
2444// this function takes the rearrangement sitting in cs and "completes" the
2445// changeset by filling in all the deltas
2446
2447void
2448complete_change_set(manifest_map const & m_old,
2449 manifest_map const & m_new,
2450 change_set & cs)
2451{
2452 cs.rearrangement.check_sane();
2453 tid_source ts;
2454 path_analysis analysis;
2455 directory_map first_dmap, second_dmap;
2456
2457 analyze_rearrangement(cs.rearrangement, analysis, ts);
2458 build_directory_map(analysis.first, first_dmap);
2459 build_directory_map(analysis.second, second_dmap);
2460
2461 std::set<file_path> paths;
2462 extract_path_set(m_new, paths);
2463
2464 for (std::set<file_path>::const_iterator i = cs.rearrangement.added_files.begin();
2465 i != cs.rearrangement.added_files.end(); ++i)
2466 {
2467 manifest_map::const_iterator j = m_new.find(*i);
2468 I(j != m_new.end());
2469 cs.deltas.insert(std::make_pair(*i,
2470 std::make_pair(null_ident,
2471 manifest_entry_id(j))));
2472 paths.erase(*i);
2473 }
2474
2475 for (std::set<file_path>::const_iterator i = paths.begin();
2476 i != paths.end(); ++i)
2477 {
2478 file_path old_path;
2479 reconstruct_path(*i, second_dmap, analysis.first, old_path);
2480 manifest_map::const_iterator j = m_old.find(old_path);
2481 manifest_map::const_iterator k = m_new.find(*i);
2482 I(j != m_old.end());
2483 I(k != m_new.end());
2484 if (!(manifest_entry_id(j) == manifest_entry_id(k)))
2485 cs.deltas.insert(std::make_pair(*i, std::make_pair(manifest_entry_id(j),
2486 manifest_entry_id(k))));
2487 }
2488
2489 cs.check_sane();
2490}
2491
2492
2493void
2494apply_change_set(manifest_map const & old_man,
2495 change_set const & cs,
2496 manifest_map & new_man)
2497{
2498 cs.check_sane();
2499 change_set a, b;
2500 build_pure_addition_change_set(old_man, a);
2501 concatenate_change_sets(a, cs, b);
2502
2503 // If the composed change_set still has renames or deletions in it, then
2504 // they referred to things that weren't in the original manifest, and this
2505 // change_set should never have been applied to this manifest in the first
2506 // place.
2507 I(b.rearrangement.deleted_files.empty());
2508 I(b.rearrangement.renamed_files.empty());
2509 // Furthermore, all deltas should be add deltas
2510 for (change_set::delta_map::const_iterator i = b.deltas.begin();
2511 i != b.deltas.end(); ++i)
2512 {
2513 I(null_id(delta_entry_src(i)));
2514 I(b.rearrangement.added_files.find(delta_entry_path(i))
2515 != b.rearrangement.added_files.end());
2516 }
2517
2518 new_man.clear();
2519 for (std::set<file_path>::const_iterator i = b.rearrangement.added_files.begin();
2520 i != b.rearrangement.added_files.end(); ++i)
2521 {
2522 change_set::delta_map::const_iterator d = b.deltas.find(*i);
2523 I(d != b.deltas.end());
2524 new_man.insert(std::make_pair(*i, delta_entry_dst(d)));
2525 }
2526}
2527
2528// quick, optimistic and destructive version
2529void
2530apply_path_rearrangement(change_set::path_rearrangement const & pr,
2531 path_set & ps)
2532{
2533 pr.check_sane();
2534 if (pr.added_files.empty()
2535 && pr.renamed_files.empty()
2536 && pr.renamed_dirs.empty()
2537 && pr.deleted_dirs.empty())
2538 {
2539 // fast path for simple drop-or-nothing file operations
2540 for (std::set<file_path>::const_iterator i = pr.deleted_files.begin();
2541 i != pr.deleted_files.end(); ++i)
2542 {
2543 I(ps.find(*i) != ps.end());
2544 ps.erase(*i);
2545 }
2546 }
2547 else
2548 {
2549 // fall back to the slow way
2550 path_set tmp;
2551 apply_path_rearrangement(ps, pr, tmp);
2552 ps = tmp;
2553 }
2554}
2555
2556// quick, optimistic and destructive version
2557file_path
2558apply_change_set_inverse(change_set const & cs,
2559 file_path const & file_in_second)
2560{
2561 cs.check_sane();
2562 tid_source ts;
2563 path_analysis analysis;
2564 directory_map second_dmap;
2565 file_path file_in_first;
2566
2567 analyze_rearrangement(cs.rearrangement, analysis, ts);
2568 build_directory_map(analysis.second, second_dmap);
2569 reconstruct_path(file_in_second, second_dmap, analysis.first, file_in_first);
2570 return file_in_first;
2571}
2572
2573// quick, optimistic and destructive version
2574void
2575apply_change_set(change_set const & cs,
2576 manifest_map & man)
2577{
2578 cs.check_sane();
2579 if (cs.rearrangement.added_files.empty()
2580 && cs.rearrangement.renamed_files.empty()
2581 && cs.rearrangement.renamed_dirs.empty()
2582 && cs.rearrangement.deleted_dirs.empty())
2583 {
2584 // fast path for simple drop/delta file operations
2585 for (std::set<file_path>::const_iterator i = cs.rearrangement.deleted_files.begin();
2586 i != cs.rearrangement.deleted_files.end(); ++i)
2587 {
2588 man.erase(*i);
2589 }
2590 for (change_set::delta_map::const_iterator i = cs.deltas.begin();
2591 i != cs.deltas.end(); ++i)
2592 {
2593 if (!null_id(delta_entry_dst(i)))
2594 man[delta_entry_path(i)] = delta_entry_dst(i);
2595 }
2596 }
2597 else
2598 {
2599 // fall back to the slow way
2600 manifest_map tmp;
2601 apply_change_set(man, cs, tmp);
2602 man = tmp;
2603 }
2604}
2605
2606
2607// i/o stuff
2608
2609namespace
2610{
2611 namespace syms
2612 {
2613 std::string const patch("patch");
2614 std::string const from("from");
2615 std::string const to("to");
2616 std::string const add_file("add_file");
2617 std::string const delete_file("delete_file");
2618 std::string const delete_dir("delete_dir");
2619 std::string const rename_file("rename_file");
2620 std::string const rename_dir("rename_dir");
2621 }
2622}
2623
2624static void
2625parse_path_rearrangement(basic_io::parser & parser,
2626 change_set & cs)
2627{
2628 while (parser.symp())
2629 {
2630 std::string t1, t2;
2631 if (parser.symp(syms::add_file))
2632 {
2633 parser.sym();
2634 parser.str(t1);
2635 cs.add_file(file_path(t1));
2636 }
2637 else if (parser.symp(syms::delete_file))
2638 {
2639 parser.sym();
2640 parser.str(t1);
2641 cs.delete_file(file_path(t1));
2642 }
2643 else if (parser.symp(syms::delete_dir))
2644 {
2645 parser.sym();
2646 parser.str(t1);
2647 cs.delete_dir(file_path(t1));
2648 }
2649 else if (parser.symp(syms::rename_file))
2650 {
2651 parser.sym();
2652 parser.str(t1);
2653 parser.esym(syms::to);
2654 parser.str(t2);
2655 cs.rename_file(file_path(t1),
2656 file_path(t2));
2657 }
2658 else if (parser.symp(syms::rename_dir))
2659 {
2660 parser.sym();
2661 parser.str(t1);
2662 parser.esym(syms::to);
2663 parser.str(t2);
2664 cs.rename_dir(file_path(t1),
2665 file_path(t2));
2666 }
2667 else
2668 break;
2669 }
2670 cs.rearrangement.check_sane();
2671}
2672
2673
2674void
2675print_path_rearrangement(basic_io::printer & printer,
2676 change_set::path_rearrangement const & pr)
2677{
2678
2679 pr.check_sane();
2680 for (std::set<file_path>::const_iterator i = pr.deleted_files.begin();
2681 i != pr.deleted_files.end(); ++i)
2682 {
2683 basic_io::stanza st;
2684 st.push_str_pair(syms::delete_file, (*i)());
2685 printer.print_stanza(st);
2686 }
2687
2688 for (std::set<file_path>::const_iterator i = pr.deleted_dirs.begin();
2689 i != pr.deleted_dirs.end(); ++i)
2690 {
2691 basic_io::stanza st;
2692 st.push_str_pair(syms::delete_dir, (*i)());
2693 printer.print_stanza(st);
2694 }
2695
2696 for (std::map<file_path,file_path>::const_iterator i = pr.renamed_files.begin();
2697 i != pr.renamed_files.end(); ++i)
2698 {
2699 basic_io::stanza st;
2700 st.push_str_pair(syms::rename_file, i->first());
2701 st.push_str_pair(syms::to, i->second());
2702 printer.print_stanza(st);
2703 }
2704
2705 for (std::map<file_path,file_path>::const_iterator i = pr.renamed_dirs.begin();
2706 i != pr.renamed_dirs.end(); ++i)
2707 {
2708 basic_io::stanza st;
2709 st.push_str_pair(syms::rename_dir, i->first());
2710 st.push_str_pair(syms::to, i->second());
2711 printer.print_stanza(st);
2712 }
2713
2714 for (std::set<file_path>::const_iterator i = pr.added_files.begin();
2715 i != pr.added_files.end(); ++i)
2716 {
2717 basic_io::stanza st;
2718 st.push_str_pair(syms::add_file, (*i)());
2719 printer.print_stanza(st);
2720 }
2721}
2722
2723void
2724parse_change_set(basic_io::parser & parser,
2725 change_set & cs)
2726{
2727 clear_change_set(cs);
2728
2729 parse_path_rearrangement(parser, cs);
2730
2731 while (parser.symp(syms::patch))
2732 {
2733 std::string path, src, dst;
2734 parser.sym();
2735 parser.str(path);
2736 parser.esym(syms::from);
2737 parser.hex(src);
2738 parser.esym(syms::to);
2739 parser.hex(dst);
2740 cs.deltas.insert(std::make_pair(file_path(path),
2741 std::make_pair(file_id(src),
2742 file_id(dst))));
2743 }
2744 cs.check_sane();
2745}
2746
2747void
2748print_change_set(basic_io::printer & printer,
2749 change_set const & cs)
2750{
2751 cs.check_sane();
2752 print_path_rearrangement(printer, cs.rearrangement);
2753
2754 for (change_set::delta_map::const_iterator i = cs.deltas.begin();
2755 i != cs.deltas.end(); ++i)
2756 {
2757 basic_io::stanza st;
2758 st.push_str_pair(syms::patch, i->first());
2759 st.push_hex_pair(syms::from, i->second.first.inner()());
2760 st.push_hex_pair(syms::to, i->second.second.inner()());
2761 printer.print_stanza(st);
2762 }
2763}
2764
2765void
2766read_path_rearrangement(data const & dat,
2767 change_set::path_rearrangement & re)
2768{
2769 std::istringstream iss(dat());
2770 basic_io::input_source src(iss, "path_rearrangement");
2771 basic_io::tokenizer tok(src);
2772 basic_io::parser pars(tok);
2773 change_set cs;
2774 parse_path_rearrangement(pars, cs);
2775 re = cs.rearrangement;
2776 I(src.lookahead == EOF);
2777 re.check_sane();
2778}
2779
2780void
2781read_change_set(data const & dat,
2782 change_set & cs)
2783{
2784 std::istringstream iss(dat());
2785 basic_io::input_source src(iss, "change_set");
2786 basic_io::tokenizer tok(src);
2787 basic_io::parser pars(tok);
2788 parse_change_set(pars, cs);
2789 I(src.lookahead == EOF);
2790 cs.check_sane();
2791}
2792
2793void
2794write_change_set(change_set const & cs,
2795 data & dat)
2796{
2797 cs.check_sane();
2798 std::ostringstream oss;
2799 basic_io::printer pr(oss);
2800 print_change_set(pr, cs);
2801 dat = data(oss.str());
2802}
2803
2804void
2805write_path_rearrangement(change_set::path_rearrangement const & re,
2806 data & dat)
2807{
2808 re.check_sane();
2809 std::ostringstream oss;
2810 basic_io::printer pr(oss);
2811 print_path_rearrangement(pr, re);
2812 dat = data(oss.str());
2813}
2814
2815#ifdef BUILD_UNIT_TESTS
2816#include "unit_tests.hh"
2817#include "sanity.hh"
2818
2819static void dump_change_set(std::string const & ctx,
2820 change_set const & cs)
2821{
2822 data tmp;
2823 write_change_set(cs, tmp);
2824 L(F("[begin changeset %s]\n") % ctx);
2825 L(F("%s") % tmp);
2826 L(F("[end changeset %s]\n") % ctx);
2827}
2828
2829static void
2830spin_change_set(change_set const & cs)
2831{
2832 data tmp1;
2833 change_set cs1;
2834 write_change_set(cs, tmp1);
2835 dump_change_set("normalized", cs);
2836 read_change_set(tmp1, cs1);
2837 for (int i = 0; i < 5; ++i)
2838 {
2839 data tmp2;
2840 change_set cs2;
2841 write_change_set(cs1, tmp2);
2842 BOOST_CHECK(tmp1 == tmp2);
2843 read_change_set(tmp2, cs2);
2844 BOOST_CHECK(cs1.rearrangement == cs2.rearrangement);
2845 BOOST_CHECK(cs1.deltas == cs2.deltas);
2846 cs1 = cs2;
2847 }
2848}
2849
2850static void
2851disjoint_merge_test(std::string const & ab_str,
2852 std::string const & ac_str)
2853{
2854 change_set ab, ac, bm, cm;
2855
2856 app_state app;
2857
2858 L(F("beginning disjoint_merge_test\n"));
2859
2860 read_change_set(data(ab_str), ab);
2861 read_change_set(data(ac_str), ac);
2862
2863 manifest_map dummy;
2864
2865 merge_provider merger(app, dummy, dummy, dummy);
2866 merge_change_sets(ab, ac, bm, cm, merger, app);
2867
2868 dump_change_set("ab", ab);
2869 dump_change_set("ac", ac);
2870 dump_change_set("bm", bm);
2871 dump_change_set("cm", cm);
2872
2873 BOOST_CHECK(bm.rearrangement == ac.rearrangement);
2874 BOOST_CHECK(cm.rearrangement == ab.rearrangement);
2875
2876 L(F("finished disjoint_merge_test\n"));
2877}
2878
2879static void
2880disjoint_merge_tests()
2881{
2882 disjoint_merge_test
2883 ("rename_file \"foo\"\n"
2884 " to \"bar\"\n",
2885
2886 "rename_file \"apple\"\n"
2887 " to \"orange\"\n");
2888
2889 disjoint_merge_test
2890 ("rename_file \"foo/a.txt\"\n"
2891 " to \"bar/b.txt\"\n",
2892
2893 "rename_file \"bar/c.txt\"\n"
2894 " to \"baz/d.txt\"\n");
2895
2896 disjoint_merge_test
2897 ("patch \"foo/file.txt\"\n"
2898 " from [c6a4a6196bb4a744207e1a6e90273369b8c2e925]\n"
2899 " to [fe18ec0c55cbc72e4e51c58dc13af515a2f3a892]\n",
2900
2901 "rename_file \"foo/file.txt\"\n"
2902 " to \"foo/apple.txt\"\n");
2903
2904 disjoint_merge_test
2905 (
2906 "rename_file \"apple.txt\"\n"
2907 " to \"pear.txt\"\n"
2908 "\n"
2909 "patch \"foo.txt\"\n"
2910 " from [c6a4a6196bb4a744207e1a6e90273369b8c2e925]\n"
2911 " to [fe18ec0c55cbc72e4e51c58dc13af515a2f3a892]\n",
2912
2913 "rename_file \"foo.txt\"\n"
2914 " to \"bar.txt\"\n"
2915 "\n"
2916 "patch \"apple.txt\"\n"
2917 " from [fe18ec0c55cbc72e4e51c58dc13af515a2f3a892]\n"
2918 " to [435e816c30263c9184f94e7c4d5aec78ea7c028a]\n");
2919}
2920
2921static void
2922basic_change_set_test()
2923{
2924 try
2925 {
2926
2927 change_set cs;
2928 cs.delete_file(file_path("usr/lib/zombie"));
2929 cs.add_file(file_path("usr/bin/cat"),
2930 file_id(hexenc<id>("adc83b19e793491b1c6ea0fd8b46cd9f32e592fc")));
2931 cs.add_file(file_path("usr/local/bin/dog"),
2932 file_id(hexenc<id>("adc83b19e793491b1c6ea0fd8b46cd9f32e592fc")));
2933 cs.rename_file(file_path("usr/local/bin/dog"), file_path("usr/bin/dog"));
2934 cs.rename_file(file_path("usr/bin/cat"), file_path("usr/local/bin/chicken"));
2935 cs.add_file(file_path("usr/lib/libc.so"),
2936 file_id(hexenc<id>("435e816c30263c9184f94e7c4d5aec78ea7c028a")));
2937 cs.rename_dir(file_path("usr/lib"), file_path("usr/local/lib"));
2938 cs.apply_delta(file_path("usr/local/bin/chicken"),
2939 file_id(hexenc<id>("c6a4a6196bb4a744207e1a6e90273369b8c2e925")),
2940 file_id(hexenc<id>("fe18ec0c55cbc72e4e51c58dc13af515a2f3a892")));
2941 spin_change_set(cs);
2942 }
2943 catch (informative_failure & exn)
2944 {
2945 L(F("informative failure: %s\n") % exn.what);
2946 }
2947 catch (std::runtime_error & exn)
2948 {
2949 L(F("runtime error: %s\n") % exn.what());
2950 }
2951}
2952
2953static void
2954neutralize_change_test()
2955{
2956 try
2957 {
2958
2959 change_set cs1, cs2, csa;
2960 cs1.add_file(file_path("usr/lib/zombie"),
2961 file_id(hexenc<id>("adc83b19e793491b1c6ea0fd8b46cd9f32e592fc")));
2962 cs1.rename_file(file_path("usr/lib/apple"),
2963 file_path("usr/lib/orange"));
2964 cs1.rename_dir(file_path("usr/lib/moose"),
2965 file_path("usr/lib/squirrel"));
2966
2967 dump_change_set("neutralize target", cs1);
2968
2969 cs2.delete_file(file_path("usr/lib/zombie"));
2970 cs2.rename_file(file_path("usr/lib/orange"),
2971 file_path("usr/lib/apple"));
2972 cs2.rename_dir(file_path("usr/lib/squirrel"),
2973 file_path("usr/lib/moose"));
2974
2975 dump_change_set("neutralizer", cs2);
2976
2977 concatenate_change_sets(cs1, cs2, csa);
2978
2979 dump_change_set("neutralized", csa);
2980
2981 tid_source ts;
2982 path_analysis analysis;
2983 analyze_rearrangement(csa.rearrangement, analysis, ts);
2984
2985 BOOST_CHECK(analysis.first.empty());
2986 BOOST_CHECK(analysis.second.empty());
2987 }
2988 catch (informative_failure & exn)
2989 {
2990 L(F("informative failure: %s\n") % exn.what);
2991 }
2992 catch (std::runtime_error & exn)
2993 {
2994 L(F("runtime error: %s\n") % exn.what());
2995 }
2996}
2997
2998static void
2999non_interfering_change_test()
3000{
3001 try
3002 {
3003
3004 change_set cs1, cs2, csa;
3005 cs1.delete_file(file_path("usr/lib/zombie"));
3006 cs1.rename_file(file_path("usr/lib/orange"),
3007 file_path("usr/lib/apple"));
3008 cs1.rename_dir(file_path("usr/lib/squirrel"),
3009 file_path("usr/lib/moose"));
3010
3011 dump_change_set("non-interference A", cs1);
3012
3013 cs2.add_file(file_path("usr/lib/zombie"),
3014 file_id(hexenc<id>("adc83b19e793491b1c6ea0fd8b46cd9f32e592fc")));
3015 cs2.rename_file(file_path("usr/lib/pear"),
3016 file_path("usr/lib/orange"));
3017 cs2.rename_dir(file_path("usr/lib/spy"),
3018 file_path("usr/lib/squirrel"));
3019
3020 dump_change_set("non-interference B", cs2);
3021
3022 concatenate_change_sets(cs1, cs2, csa);
3023
3024 dump_change_set("non-interference combined", csa);
3025
3026 tid_source ts;
3027 path_analysis analysis;
3028 analyze_rearrangement(csa.rearrangement, analysis, ts);
3029
3030 BOOST_CHECK(analysis.first.size() == 8);
3031 BOOST_CHECK(analysis.second.size() == 8);
3032 }
3033 catch (informative_failure & exn)
3034 {
3035 L(F("informative failure: %s\n") % exn.what);
3036 }
3037 catch (std::runtime_error & exn)
3038 {
3039 L(F("runtime error: %s\n") % exn.what());
3040 }
3041}
3042
3043static const file_id fid_null;
3044static const file_id fid1 = file_id(hexenc<id>("aaaa3831e5eb74e6cd50b94f9e99e6a14d98d702"));
3045static const file_id fid2 = file_id(hexenc<id>("bbbb3831e5eb74e6cd50b94f9e99e6a14d98d702"));
3046static const file_id fid3 = file_id(hexenc<id>("cccc3831e5eb74e6cd50b94f9e99e6a14d98d702"));
3047
3048typedef enum { in_a, in_b } which_t;
3049struct bad_concatenate_change_test
3050{
3051 change_set a;
3052 change_set b;
3053 change_set combined;
3054 change_set concat;
3055 bool do_combine;
3056 std::string ident;
3057 bad_concatenate_change_test(char const *file, int line) :
3058 do_combine(false),
3059 ident((F("%s:%d") % file % line).str())
3060 {
3061 L(F("BEGINNING concatenation test %s\n") % ident);
3062 }
3063
3064 ~bad_concatenate_change_test()
3065 {
3066 L(F("FINISHING concatenation test %s\n") % ident);
3067 }
3068
3069 change_set & getit(which_t which)
3070 {
3071 if (which == in_a)
3072 return a;
3073 return b;
3074 }
3075 // Call combine() if you want to make sure that the things that are bad when
3076 // concatenated are also bad when all stuck together into a single
3077 // changeset.
3078 void combine() { do_combine = true; }
3079 void add_file(which_t which, std::string const & path, file_id fid = fid1)
3080 {
3081 getit(which).add_file(file_path(path), fid);
3082 if (do_combine)
3083 combined.add_file(file_path(path), fid);
3084 }
3085 void apply_delta(which_t which, std::string const & path,
3086 file_id from_fid,
3087 file_id to_fid)
3088 {
3089 getit(which).apply_delta(file_path(path), from_fid, to_fid);
3090 if (do_combine)
3091 combined.apply_delta(file_path(path), from_fid, to_fid);
3092 }
3093 void delete_file(which_t which, std::string const & path)
3094 {
3095 getit(which).delete_file(file_path(path));
3096 if (do_combine)
3097 combined.delete_file(file_path(path));
3098 }
3099 void delete_dir(which_t which, std::string const & path)
3100 {
3101 getit(which).delete_dir(file_path(path));
3102 if (do_combine)
3103 combined.delete_dir(file_path(path));
3104 }
3105 void rename_file(which_t which,
3106 std::string const & path1, std::string const & path2)
3107 {
3108 getit(which).rename_file(file_path(path1), file_path(path2));
3109 if (do_combine)
3110 combined.rename_file(file_path(path1), file_path(path2));
3111 }
3112 void rename_dir(which_t which,
3113 std::string const & path1, std::string const & path2)
3114 {
3115 getit(which).rename_dir(file_path(path1), file_path(path2));
3116 if (do_combine)
3117 combined.rename_dir(file_path(path1), file_path(path2));
3118 }
3119 void run()
3120 {
3121 L(F("RUNNING bad_concatenate_change_test %s\n") % ident);
3122 try
3123 {
3124 dump_change_set("a", a);
3125 dump_change_set("b", b);
3126 }
3127 catch (std::logic_error e)
3128 {
3129 L(F("skipping change_set printing, one or both are not sane\n"));
3130 }
3131 BOOST_CHECK_THROW(concatenate_change_sets(a, b, concat),
3132 std::logic_error);
3133 try { dump_change_set("concat", concat); }
3134 catch (std::logic_error e) { L(F("concat change_set is insane\n")); }
3135 if (do_combine)
3136 {
3137 L(F("Checking combined change set\n"));
3138 change_set empty_cs, combined_concat;
3139 BOOST_CHECK_THROW(concatenate_change_sets(combined,
3140 empty_cs,
3141 combined_concat),
3142 std::logic_error);
3143 try { dump_change_set("combined_concat", combined_concat); }
3144 catch (std::logic_error e) { L(F("combined_concat is insane\n")); }
3145 }
3146 }
3147 void run_both()
3148 {
3149 run();
3150 L(F("RUNNING bad_concatenate_change_test %s again backwards\n") % ident);
3151 BOOST_CHECK_THROW(concatenate_change_sets(a, b, concat),
3152 std::logic_error);
3153 }
3154};
3155
3156// We also do a number of just "bad change set" tests here, leaving one of
3157// them empty; this is because our main line of defense against bad
3158// change_sets, check_sane_history, does its checking by doing
3159// concatenations, so it's doing concatenations that we want to be sure does
3160// sanity checking.
3161static void
3162bad_concatenate_change_tests()
3163{
3164 // Files/directories can't be dropped on top of each other:
3165 BOOST_CHECKPOINT("on top");
3166 {
3167 bad_concatenate_change_test t(__FILE__, __LINE__);
3168 t.add_file(in_a, "target");
3169 t.add_file(in_b, "target");
3170 t.run();
3171 }
3172 {
3173 bad_concatenate_change_test t(__FILE__, __LINE__);
3174 t.combine();
3175 t.rename_file(in_a, "foo", "target");
3176 t.rename_file(in_b, "bar", "target");
3177 t.run();
3178 }
3179 {
3180 bad_concatenate_change_test t(__FILE__, __LINE__);
3181 t.combine();
3182 t.rename_dir(in_a, "foo", "target");
3183 t.rename_dir(in_b, "bar", "target");
3184 t.run();
3185 }
3186 {
3187 bad_concatenate_change_test t(__FILE__, __LINE__);
3188 t.combine();
3189 t.rename_file(in_a, "foo", "target");
3190 t.rename_dir(in_b, "bar", "target");
3191 t.run_both();
3192 }
3193 {
3194 bad_concatenate_change_test t(__FILE__, __LINE__);
3195 t.combine();
3196 t.add_file(in_a, "target");
3197 t.rename_file(in_b, "foo", "target");
3198 t.run_both();
3199 }
3200 {
3201 bad_concatenate_change_test t(__FILE__, __LINE__);
3202 t.combine();
3203 t.add_file(in_a, "target");
3204 t.rename_dir(in_b, "foo", "target");
3205 t.run_both();
3206 }
3207 {
3208 bad_concatenate_change_test t(__FILE__, __LINE__);
3209 t.combine();
3210 t.add_file(in_a, "target/subfile");
3211 t.add_file(in_b, "target");
3212 t.run_both();
3213 }
3214 {
3215 bad_concatenate_change_test t(__FILE__, __LINE__);
3216 t.combine();
3217 t.add_file(in_a, "target/subfile");
3218 t.rename_file(in_b, "foo", "target");
3219 t.run_both();
3220 }
3221 {
3222 bad_concatenate_change_test t(__FILE__, __LINE__);
3223 t.add_file(in_a, "target/subfile");
3224 t.rename_dir(in_b, "foo", "target");
3225 t.run_both();
3226 }
3227 // You can only delete something once
3228 BOOST_CHECKPOINT("delete once");
3229 {
3230 bad_concatenate_change_test t(__FILE__, __LINE__);
3231 t.delete_file(in_a, "target");
3232 t.delete_file(in_b, "target");
3233 t.run();
3234 }
3235 {
3236 bad_concatenate_change_test t(__FILE__, __LINE__);
3237 t.combine();
3238 t.delete_file(in_a, "target");
3239 t.delete_dir(in_b, "target");
3240 t.run_both();
3241 }
3242 {
3243 bad_concatenate_change_test t(__FILE__, __LINE__);
3244 t.delete_dir(in_a, "target");
3245 t.delete_dir(in_b, "target");
3246 t.run();
3247 }
3248 // You can't delete something that's not there anymore
3249 BOOST_CHECKPOINT("delete after rename");
3250 {
3251 bad_concatenate_change_test t(__FILE__, __LINE__);
3252 t.combine();
3253 t.delete_file(in_a, "target");
3254 t.rename_file(in_b, "target", "foo");
3255 t.run_both();
3256 }
3257 {
3258 bad_concatenate_change_test t(__FILE__, __LINE__);
3259 t.combine();
3260 t.delete_dir(in_a, "target");
3261 t.rename_file(in_b, "target", "foo");
3262 t.run_both();
3263 }
3264 {
3265 bad_concatenate_change_test t(__FILE__, __LINE__);
3266 t.combine();
3267 t.delete_dir(in_a, "target");
3268 t.rename_dir(in_b, "target", "foo");
3269 t.run_both();
3270 }
3271 {
3272 bad_concatenate_change_test t(__FILE__, __LINE__);
3273 t.combine();
3274 t.delete_file(in_a, "target");
3275 t.rename_dir(in_b, "target", "foo");
3276 t.run_both();
3277 }
3278 // Files/directories can't be split in two
3279 BOOST_CHECKPOINT("splitting files/dirs");
3280 {
3281 bad_concatenate_change_test t(__FILE__, __LINE__);
3282 t.rename_file(in_a, "target", "foo");
3283 t.rename_file(in_b, "target", "bar");
3284 t.run();
3285 }
3286 {
3287 bad_concatenate_change_test t(__FILE__, __LINE__);
3288 t.rename_dir(in_a, "target", "foo");
3289 t.rename_dir(in_b, "target", "bar");
3290 t.run();
3291 }
3292 {
3293 bad_concatenate_change_test t(__FILE__, __LINE__);
3294 t.combine();
3295 t.rename_dir(in_a, "target", "foo");
3296 t.rename_file(in_b, "target", "bar");
3297 t.run_both();
3298 }
3299 // Files and directories are different
3300 BOOST_CHECKPOINT("files != dirs");
3301 {
3302 bad_concatenate_change_test t(__FILE__, __LINE__);
3303 t.add_file(in_a, "target");
3304 t.delete_dir(in_b, "target");
3305 t.run();
3306 }
3307 {
3308 bad_concatenate_change_test t(__FILE__, __LINE__);
3309 t.add_file(in_a, "target/subfile");
3310 t.delete_file(in_b, "target");
3311 t.run();
3312 }
3313 {
3314 bad_concatenate_change_test t(__FILE__, __LINE__);
3315 t.add_file(in_a, "target/subfile");
3316 t.rename_file(in_b, "target", "foo");
3317 t.run();
3318 }
3319 {
3320 bad_concatenate_change_test t(__FILE__, __LINE__);
3321 t.rename_file(in_a, "foo", "target");
3322 t.delete_dir(in_b, "target");
3323 t.run();
3324 }
3325 {
3326 bad_concatenate_change_test t(__FILE__, __LINE__);
3327 t.combine();
3328 t.apply_delta(in_a, "target", fid1, fid2);
3329 t.delete_dir(in_b, "target");
3330 t.run_both();
3331 }
3332 {
3333 bad_concatenate_change_test t(__FILE__, __LINE__);
3334 t.rename_dir(in_a, "foo", "target");
3335 t.delete_file(in_b, "target");
3336 t.run();
3337 }
3338 {
3339 bad_concatenate_change_test t(__FILE__, __LINE__);
3340 t.combine();
3341 t.rename_dir(in_a, "foo", "target");
3342 t.apply_delta(in_b, "target", fid1, fid2);
3343 t.run_both();
3344 }
3345 {
3346 bad_concatenate_change_test t(__FILE__, __LINE__);
3347 t.combine();
3348 t.apply_delta(in_a, "target", fid1, fid2);
3349 t.rename_dir(in_b, "target", "bar");
3350 t.run_both();
3351 }
3352 {
3353 bad_concatenate_change_test t(__FILE__, __LINE__);
3354 t.rename_file(in_a, "foo", "target");
3355 t.rename_dir(in_b, "target", "bar");
3356 t.run();
3357 }
3358 {
3359 bad_concatenate_change_test t(__FILE__, __LINE__);
3360 t.rename_dir(in_a, "foo", "target");
3361 t.rename_file(in_b, "target", "bar");
3362 t.run();
3363 }
3364 // Directories can't be patched, and patches can't be directoried...
3365 BOOST_CHECKPOINT("can't patch dirs or vice versa");
3366 {
3367 bad_concatenate_change_test t(__FILE__, __LINE__);
3368 t.combine();
3369 t.add_file(in_a, "target/subfile");
3370 t.apply_delta(in_b, "target", fid_null, fid1);
3371 t.run_both();
3372 }
3373 {
3374 bad_concatenate_change_test t(__FILE__, __LINE__);
3375 t.combine();
3376 t.add_file(in_a, "target/subfile");
3377 t.apply_delta(in_b, "target", fid1, fid2);
3378 t.run_both();
3379 }
3380 // Deltas must be consistent
3381 BOOST_CHECKPOINT("consistent deltas");
3382 {
3383 bad_concatenate_change_test t(__FILE__, __LINE__);
3384 t.apply_delta(in_a, "target", fid1, fid2);
3385 t.apply_delta(in_b, "target", fid3, fid1);
3386 t.run();
3387 }
3388 {
3389 bad_concatenate_change_test t(__FILE__, __LINE__);
3390 t.add_file(in_a, "target", fid1);
3391 t.apply_delta(in_b, "target", fid2, fid3);
3392 t.run();
3393 }
3394 // Can't have a null source id if it's not an add
3395 BOOST_CHECKPOINT("null id on non-add");
3396 {
3397 bad_concatenate_change_test t(__FILE__, __LINE__);
3398 t.apply_delta(in_a, "target", fid_null, fid1);
3399 t.run();
3400 }
3401 // Can't have drop + delta with no add
3402 {
3403 bad_concatenate_change_test t(__FILE__, __LINE__);
3404 t.combine();
3405 t.delete_file(in_a, "target");
3406 t.apply_delta(in_b, "target", fid1, fid2);
3407 t.run();
3408 }
3409 // Can't have a null destination id, ever, with or without a delete_file
3410 BOOST_CHECKPOINT("no null destinations");
3411 {
3412 bad_concatenate_change_test t(__FILE__, __LINE__);
3413 t.delete_file(in_a, "target");
3414 t.apply_delta(in_a, "target", fid1, fid_null);
3415 t.run();
3416 }
3417 {
3418 bad_concatenate_change_test t(__FILE__, __LINE__);
3419 t.apply_delta(in_a, "target", fid1, fid_null);
3420 t.run();
3421 }
3422 // Can't have a patch with src == dst
3423 {
3424 bad_concatenate_change_test t(__FILE__, __LINE__);
3425 t.apply_delta(in_a, "target", fid1, fid1);
3426 t.run();
3427 }
3428}
3429
3430// FIXME: Things that should be added, but can't be trivially because they
3431// assert too early:
3432// anything repeated -- multiple adds, multiple deletes, multiple deltas
3433// including <rename a b, rename a c> in one changeset, for both files and dirs
3434// (probably should put these in strings, and do BOOST_CHECK_THROWS in the
3435// parser?)
3436
3437// FIXME: also need tests for the invariants in apply_manifest (and any
3438// invariants that should be there but aren't, of course)
3439
3440void
3441add_change_set_tests(test_suite * suite)
3442{
3443 I(suite);
3444 suite->add(BOOST_TEST_CASE(&basic_change_set_test));
3445 suite->add(BOOST_TEST_CASE(&neutralize_change_test));
3446 suite->add(BOOST_TEST_CASE(&non_interfering_change_test));
3447 suite->add(BOOST_TEST_CASE(&disjoint_merge_tests));
3448 suite->add(BOOST_TEST_CASE(&bad_concatenate_change_tests));
3449}
3450
3451
3452#endif // BUILD_UNIT_TESTS

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status