monotone

monotone Mtn Source Tree

Root/change_set.cc

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

Archive Download this file

Branches

Tags

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