monotone

monotone Mtn Source Tree

Root/diff_patch.cc

1// Copyright (C) 2002 Graydon Hoare <graydon@pobox.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include "config.h"
11
12#include <algorithm>
13#include <iterator>
14#include <map>
15#include <string>
16#include <vector>
17
18#include <boost/shared_ptr.hpp>
19#include <boost/scoped_ptr.hpp>
20#include <boost/regex.hpp>
21#include "diff_patch.hh"
22#include "interner.hh"
23#include "lcs.hh"
24#include "roster.hh"
25#include "packet.hh"
26#include "safe_map.hh"
27#include "sanity.hh"
28#include "transforms.hh"
29#include "simplestring_xform.hh"
30#include "vocab.hh"
31#include "revision.hh"
32#include "constants.hh"
33#include "file_io.hh"
34
35using std::make_pair;
36using std::map;
37using std::min;
38using std::ostream;
39using std::ostream_iterator;
40using std::string;
41using std::swap;
42using std::vector;
43
44using boost::shared_ptr;
45
46//
47// a 3-way merge works like this:
48//
49// /----> right
50// ancestor
51// \----> left
52//
53// first you compute the edit list "EDITS(ancestor,left)".
54//
55// then you make an offset table "leftpos" which describes positions in
56// "ancestor" as they map to "left"; that is, for 0 < apos <
57// ancestor.size(), we have
58//
59// left[leftpos[apos]] == ancestor[apos]
60//
61// you do this by walking through the edit list and either jumping the
62// current index ahead an extra position, on an insert, or remaining still,
63// on a delete. on an insert *or* a delete, you push the current index back
64// onto the leftpos array.
65//
66// next you compute the edit list "EDITS(ancestor,right)".
67//
68// you then go through this edit list applying the edits to left, rather
69// than ancestor, and using the table leftpos to map the position of each
70// edit to an appropriate spot in left. this means you walk a "curr_left"
71// index through the edits, and for each edit e:
72//
73// - if e is a delete (and e.pos is a position in ancestor)
74// - increment curr_left without copying anything to "merged"
75//
76// - if e is an insert (and e.pos is a position in right)
77// - copy right[e.pos] to "merged"
78// - leave curr_left alone
79//
80// - when advancing to apos (and apos is a position in ancestor)
81// - copy left[curr_left] to merged while curr_left < leftpos[apos]
82//
83//
84// the practical upshot is that you apply the delta from ancestor->right
85// to the adjusted contexts in left, producing something vaguely like
86// the concatenation of delta(ancestor,left) :: delta(ancestor,right).
87//
88// NB: this is, as far as I can tell, what diff3 does. I don't think I'm
89// infringing on anyone's fancy patents here.
90//
91
92typedef enum { preserved = 0, deleted = 1, changed = 2 } edit_t;
93static const char etab[3][10] =
94 {
95 "preserved",
96 "deleted",
97 "changed"
98 };
99
100struct extent
101{
102 extent(size_t p, size_t l, edit_t t)
103 : pos(p), len(l), type(t)
104 {}
105 size_t pos;
106 size_t len;
107 edit_t type;
108};
109
110void calculate_extents(vector<long, QA(long)> const & a_b_edits,
111 vector<long, QA(long)> const & b,
112 vector<long, QA(long)> & prefix,
113 vector<extent> & extents,
114 vector<long, QA(long)> & suffix,
115 size_t const a_len,
116 interner<long> & intern)
117{
118 extents.reserve(a_len * 2);
119
120 size_t a_pos = 0, b_pos = 0;
121
122 for (vector<long, QA(long)>::const_iterator i = a_b_edits.begin();
123 i != a_b_edits.end(); ++i)
124 {
125 // L(FL("edit: %d") % *i);
126 if (*i < 0)
127 {
128 // negative elements code the negation of the one-based index into A
129 // of the element to be deleted
130 size_t a_deleted = (-1 - *i);
131
132 // fill positions out to the deletion point
133 while (a_pos < a_deleted)
134 {
135 a_pos++;
136 extents.push_back(extent(b_pos++, 1, preserved));
137 }
138
139 // L(FL(" -- delete at A-pos %d (B-pos = %d)") % a_deleted % b_pos);
140
141 // skip the deleted line
142 a_pos++;
143 extents.push_back(extent(b_pos, 0, deleted));
144 }
145 else
146 {
147 // positive elements code the one-based index into B of the element to
148 // be inserted
149 size_t b_inserted = (*i - 1);
150
151 // fill positions out to the insertion point
152 while (b_pos < b_inserted)
153 {
154 a_pos++;
155 extents.push_back(extent(b_pos++, 1, preserved));
156 }
157
158 // L(FL(" -- insert at B-pos %d (A-pos = %d) : '%s'")
159 // % b_inserted % a_pos % intern.lookup(b.at(b_inserted)));
160
161 // record that there was an insertion, but a_pos did not move.
162 if ((b_pos == 0 && extents.empty())
163 || (b_pos == prefix.size()))
164 {
165 prefix.push_back(b.at(b_pos));
166 }
167 else if (a_len == a_pos)
168 {
169 suffix.push_back(b.at(b_pos));
170 }
171 else
172 {
173 // make the insertion
174 extents.back().type = changed;
175 extents.back().len++;
176 }
177 b_pos++;
178 }
179 }
180
181 while (extents.size() < a_len)
182 extents.push_back(extent(b_pos++, 1, preserved));
183}
184
185void normalize_extents(vector<extent> & a_b_map,
186 vector<long, QA(long)> const & a,
187 vector<long, QA(long)> const & b)
188{
189 for (size_t i = 0; i < a_b_map.size(); ++i)
190 {
191 if (i > 0)
192 {
193 size_t j = i;
194 while (j > 0
195 && (a_b_map.at(j-1).type == preserved)
196 && (a_b_map.at(j).type == changed)
197 && (a.at(j) == b.at(a_b_map.at(j).pos + a_b_map.at(j).len - 1)))
198 {
199 // This is implied by (a_b_map.at(j-1).type == preserved)
200 I(a.at(j-1) == b.at(a_b_map.at(j-1).pos));
201
202 // Coming into loop we have:
203 // i
204 // z --pres--> z 0
205 // o --pres--> o 1
206 // a --chng--> a 2 The important thing here is that 'a' in
207 // t the LHS matches with ...
208 // u
209 // v
210 // a ... the a on the RHS here. Hence we can
211 // q --pres--> q 3 'shift' the entire 'changed' block
212 // e --chng--> d 4 upwards, leaving a 'preserved' line
213 // g --pres--> g 5 'a'->'a'
214 //
215 // Want to end up with:
216 // i
217 // z --pres--> z 0
218 // o --chng--> o 1
219 // a
220 // t
221 // u
222 // v
223 // a --pres--> a 2
224 // q --pres--> q 3
225 // e --chng--> d 4
226 // g --pres--> g 5
227 //
228 // Now all the 'changed' extents are normalised to the
229 // earliest possible position.
230
231 L(FL("exchanging preserved extent [%d+%d] with changed extent [%d+%d]")
232 % a_b_map.at(j-1).pos
233 % a_b_map.at(j-1).len
234 % a_b_map.at(j).pos
235 % a_b_map.at(j).len);
236
237 swap(a_b_map.at(j-1).len, a_b_map.at(j).len);
238 swap(a_b_map.at(j-1).type, a_b_map.at(j).type);
239 --j;
240 }
241 }
242 }
243
244 for (size_t i = 0; i < a_b_map.size(); ++i)
245 {
246 if (i > 0)
247 {
248 size_t j = i;
249 while (j > 0
250 && a_b_map.at(j).type == changed
251 && a_b_map.at(j-1).type == changed
252 && a_b_map.at(j).len > 1
253 && a_b_map.at(j-1).pos + a_b_map.at(j-1).len == a_b_map.at(j).pos)
254 {
255 // step 1: move a chunk from this insert extent to its
256 // predecessor
257 size_t piece = a_b_map.at(j).len - 1;
258 // L(FL("moving change piece of len %d from pos %d to pos %d")
259 // % piece
260 // % a_b_map.at(j).pos
261 // % a_b_map.at(j-1).pos);
262 a_b_map.at(j).len = 1;
263 a_b_map.at(j).pos += piece;
264 a_b_map.at(j-1).len += piece;
265
266 // step 2: if this extent (now of length 1) has become a "changed"
267 // extent identical to its previous state, switch it to a "preserved"
268 // extent.
269 if (b.at(a_b_map.at(j).pos) == a.at(j))
270 {
271 // L(FL("changing normalized 'changed' extent at %d to 'preserved'")
272 // % a_b_map.at(j).pos);
273 a_b_map.at(j).type = preserved;
274 }
275 --j;
276 }
277 }
278 }
279}
280
281
282void merge_extents(vector<extent> const & a_b_map,
283 vector<extent> const & a_c_map,
284 vector<long, QA(long)> const & b,
285 vector<long, QA(long)> const & c,
286 interner<long> const & in,
287 vector<long, QA(long)> & merged)
288{
289 I(a_b_map.size() == a_c_map.size());
290
291 vector<extent>::const_iterator i = a_b_map.begin();
292 vector<extent>::const_iterator j = a_c_map.begin();
293 merged.reserve(a_b_map.size() * 2);
294
295 // for (; i != a_b_map.end(); ++i, ++j)
296 // {
297
298 // L(FL("trying to merge: [%s %d %d] vs. [%s %d %d]")
299 // % etab[i->type] % i->pos % i->len
300 // % etab[j->type] % j->pos % j->len);
301 // }
302
303 // i = a_b_map.begin();
304 // j = a_c_map.begin();
305
306 for (; i != a_b_map.end(); ++i, ++j)
307 {
308
309 // L(FL("trying to merge: [%s %d %d] vs. [%s %d %d]")
310 // % etab[i->type] % i->pos % i->len
311 // % etab[j->type] % j->pos % j->len);
312
313 // mutual, identical preserves / inserts / changes
314 if (((i->type == changed && j->type == changed)
315 || (i->type == preserved && j->type == preserved))
316 && i->len == j->len)
317 {
318 for (size_t k = 0; k < i->len; ++k)
319 {
320 if (b.at(i->pos + k) != c.at(j->pos + k))
321 {
322 L(FL("conflicting edits: %s %d[%d] '%s' vs. %s %d[%d] '%s'")
323 % etab[i->type] % i->pos % k % in.lookup(b.at(i->pos + k))
324 % etab[j->type] % j->pos % k % in.lookup(c.at(j->pos + k)));
325 throw conflict();
326 }
327 merged.push_back(b.at(i->pos + k));
328 }
329 }
330
331 // mutual or single-edge deletes
332 else if ((i->type == deleted && j->type == deleted)
333 || (i->type == deleted && j->type == preserved)
334 || (i->type == preserved && j->type == deleted))
335 {
336 // do nothing
337 }
338
339 // single-edge insert / changes
340 else if (i->type == changed && j->type == preserved)
341 for (size_t k = 0; k < i->len; ++k)
342 merged.push_back(b.at(i->pos + k));
343
344 else if (i->type == preserved && j->type == changed)
345 for (size_t k = 0; k < j->len; ++k)
346 merged.push_back(c.at(j->pos + k));
347
348 else
349 {
350 L(FL("conflicting edits: [%s %d %d] vs. [%s %d %d]")
351 % etab[i->type] % i->pos % i->len
352 % etab[j->type] % j->pos % j->len);
353 throw conflict();
354 }
355
356 // if (merged.empty())
357 // L(FL(" --> EMPTY"));
358 // else
359 // L(FL(" --> [%d]: %s") % (merged.size() - 1) % in.lookup(merged.back()));
360 }
361}
362
363
364void merge_via_edit_scripts(vector<string> const & ancestor,
365 vector<string> const & left,
366 vector<string> const & right,
367 vector<string> & merged)
368{
369 vector<long, QA(long)> anc_interned;
370 vector<long, QA(long)> left_interned, right_interned;
371 vector<long, QA(long)> left_edits, right_edits;
372 vector<long, QA(long)> left_prefix, right_prefix;
373 vector<long, QA(long)> left_suffix, right_suffix;
374 vector<extent> left_extents, right_extents;
375 vector<long, QA(long)> merged_interned;
376 interner<long> in;
377
378 // for (int i = 0; i < min(min(left.size(), right.size()), ancestor.size()); ++i)
379 // {
380 // cerr << '[' << i << "] " << left[i] << ' ' << ancestor[i] << ' ' << right[i] << '\n';
381 // }
382
383 anc_interned.reserve(ancestor.size());
384 for (vector<string>::const_iterator i = ancestor.begin();
385 i != ancestor.end(); ++i)
386 anc_interned.push_back(in.intern(*i));
387
388 left_interned.reserve(left.size());
389 for (vector<string>::const_iterator i = left.begin();
390 i != left.end(); ++i)
391 left_interned.push_back(in.intern(*i));
392
393 right_interned.reserve(right.size());
394 for (vector<string>::const_iterator i = right.begin();
395 i != right.end(); ++i)
396 right_interned.push_back(in.intern(*i));
397
398 L(FL("calculating left edit script on %d -> %d lines")
399 % anc_interned.size() % left_interned.size());
400
401 edit_script(anc_interned.begin(), anc_interned.end(),
402 left_interned.begin(), left_interned.end(),
403 min(ancestor.size(), left.size()),
404 left_edits);
405
406 L(FL("calculating right edit script on %d -> %d lines")
407 % anc_interned.size() % right_interned.size());
408
409 edit_script(anc_interned.begin(), anc_interned.end(),
410 right_interned.begin(), right_interned.end(),
411 min(ancestor.size(), right.size()),
412 right_edits);
413
414 L(FL("calculating left extents on %d edits") % left_edits.size());
415 calculate_extents(left_edits, left_interned,
416 left_prefix, left_extents, left_suffix,
417 anc_interned.size(), in);
418
419 L(FL("calculating right extents on %d edits") % right_edits.size());
420 calculate_extents(right_edits, right_interned,
421 right_prefix, right_extents, right_suffix,
422 anc_interned.size(), in);
423
424 L(FL("normalizing %d right extents") % right_extents.size());
425 normalize_extents(right_extents, anc_interned, right_interned);
426
427 L(FL("normalizing %d left extents") % left_extents.size());
428 normalize_extents(left_extents, anc_interned, left_interned);
429
430
431 if ((!right_prefix.empty()) && (!left_prefix.empty()))
432 {
433 L(FL("conflicting prefixes"));
434 throw conflict();
435 }
436
437 if ((!right_suffix.empty()) && (!left_suffix.empty()))
438 {
439 L(FL("conflicting suffixes"));
440 throw conflict();
441 }
442
443 L(FL("merging %d left, %d right extents")
444 % left_extents.size() % right_extents.size());
445
446 copy(left_prefix.begin(), left_prefix.end(), back_inserter(merged_interned));
447 copy(right_prefix.begin(), right_prefix.end(), back_inserter(merged_interned));
448
449 merge_extents(left_extents, right_extents,
450 left_interned, right_interned,
451 in, merged_interned);
452
453 copy(left_suffix.begin(), left_suffix.end(), back_inserter(merged_interned));
454 copy(right_suffix.begin(), right_suffix.end(), back_inserter(merged_interned));
455
456 merged.reserve(merged_interned.size());
457 for (vector<long, QA(long)>::const_iterator i = merged_interned.begin();
458 i != merged_interned.end(); ++i)
459 merged.push_back(in.lookup(*i));
460}
461
462
463bool merge3(vector<string> const & ancestor,
464 vector<string> const & left,
465 vector<string> const & right,
466 vector<string> & merged)
467{
468 try
469 {
470 merge_via_edit_scripts(ancestor, left, right, merged);
471 }
472 catch(conflict &)
473 {
474 L(FL("conflict detected. no merge."));
475 return false;
476 }
477 return true;
478}
479
480
481///////////////////////////////////////////////////////////////////////////
482// content_merge_database_adaptor
483///////////////////////////////////////////////////////////////////////////
484
485
486content_merge_database_adaptor::content_merge_database_adaptor(app_state & app,
487 revision_id const & left,
488 revision_id const & right,
489 marking_map const & mm)
490 : app(app), mm(mm)
491{
492 // FIXME: possibly refactor to run this lazily, as we don't
493 // need to find common ancestors if we're never actually
494 // called on to do content merging.
495 find_common_ancestor_for_merge(left, right, lca, app);
496}
497
498void
499content_merge_database_adaptor::record_merge(file_id const & left_ident,
500 file_id const & right_ident,
501 file_id const & merged_ident,
502 file_data const & left_data,
503 file_data const & merged_data)
504{
505 L(FL("recording successful merge of %s <-> %s into %s")
506 % left_ident % right_ident % merged_ident);
507
508 delta left_delta, right_delta;
509 transaction_guard guard(app.db);
510
511 diff(left_data.inner(), merged_data.inner(), left_delta);
512 diff(left_data.inner(), merged_data.inner(), right_delta);
513 packet_db_writer dbw(app);
514 dbw.consume_file_delta (left_ident, merged_ident, file_delta(left_delta));
515 dbw.consume_file_delta (right_ident, merged_ident, file_delta(right_delta));
516 guard.commit();
517}
518
519static void
520load_and_cache_roster(revision_id const & rid,
521 map<revision_id, shared_ptr<roster_t const> > & rmap,
522 shared_ptr<roster_t const> & rout,
523 app_state & app)
524{
525 map<revision_id, shared_ptr<roster_t const> >::const_iterator i = rmap.find(rid);
526 if (i != rmap.end())
527 rout = i->second;
528 else
529 {
530 database::cached_roster cr;
531 app.db.get_roster(rid, cr);
532 safe_insert(rmap, make_pair(rid, cr.first));
533 rout = cr.first;
534 }
535}
536
537void
538content_merge_database_adaptor::get_ancestral_roster(node_id nid,
539 shared_ptr<roster_t const> & anc)
540{
541 // Given a file, if the lca is nonzero and its roster contains the file,
542 // then we use its roster. Otherwise we use the roster at the file's
543 // birth revision, which is the "per-file worst case" lca.
544
545 // Begin by loading any non-empty file lca roster
546 if (!lca.inner()().empty())
547 load_and_cache_roster(lca, rosters, anc, app);
548
549 // If there is no LCA, or the LCA's roster doesn't contain the file,
550 // then use the file's birth roster.
551 if (!anc || !anc->has_node(nid))
552 {
553 marking_map::const_iterator j = mm.find(nid);
554 I(j != mm.end());
555 load_and_cache_roster(j->second.birth_revision, rosters, anc, app);
556 }
557 I(anc);
558}
559
560void
561content_merge_database_adaptor::get_version(file_id const & ident,
562 file_data & dat) const
563{
564 app.db.get_file_version(ident, dat);
565}
566
567
568///////////////////////////////////////////////////////////////////////////
569// content_merge_workspace_adaptor
570///////////////////////////////////////////////////////////////////////////
571
572void
573content_merge_workspace_adaptor::record_merge(file_id const & left_id,
574 file_id const & right_id,
575 file_id const & merged_id,
576 file_data const & left_data,
577 file_data const & merged_data)
578{
579 L(FL("temporarily recording merge of %s <-> %s into %s")
580 % left_id % right_id % merged_id);
581 // this is an insert instead of a safe_insert because it is perfectly
582 // legal (though rare) to have multiple merges resolve to the same file
583 // contents.
584 temporary_store.insert(make_pair(merged_id, merged_data));
585}
586
587void
588content_merge_workspace_adaptor::get_ancestral_roster(node_id nid,
589 shared_ptr<roster_t const> & anc)
590{
591 // When doing an update, the base revision is always the ancestor to
592 // use for content merging.
593 anc = base;
594}
595
596void
597content_merge_workspace_adaptor::get_version(file_id const & ident,
598 file_data & dat) const
599{
600 map<file_id,file_data>::const_iterator i = temporary_store.find(ident);
601 if (i != temporary_store.end())
602 dat = i->second;
603 else if (app.db.file_version_exists(ident))
604 app.db.get_file_version(ident, dat);
605 else
606 {
607 data tmp;
608 file_id fid;
609 map<file_id, file_path>::const_iterator i = content_paths.find(ident);
610 I(i != content_paths.end());
611
612 require_path_is_file(i->second,
613 F("file '%s' does not exist in workspace") % i->second,
614 F("'%s' in workspace is a directory, not a file") % i->second);
615 read_data(i->second, tmp);
616 calculate_ident(file_data(tmp), fid);
617 E(fid == ident,
618 F("file %s in workspace has id %s, wanted %s")
619 % i->second % fid % ident);
620 dat = file_data(tmp);
621 }
622}
623
624
625///////////////////////////////////////////////////////////////////////////
626// content_merger
627///////////////////////////////////////////////////////////////////////////
628
629content_merger::content_merger(app_state & app,
630 roster_t const & anc_ros,
631 roster_t const & left_ros,
632 roster_t const & right_ros,
633 content_merge_adaptor & adaptor)
634 : app(app),
635 anc_ros(anc_ros),
636 left_ros(left_ros),
637 right_ros(right_ros),
638 adaptor(adaptor)
639{}
640
641string
642content_merger::get_file_encoding(file_path const & path,
643 roster_t const & ros)
644{
645 attr_value v;
646 split_path sp;
647 path.split(sp);
648 if (ros.get_attr(sp, attr_key(constants::encoding_attribute), v))
649 return v();
650 return constants::default_encoding;
651}
652
653bool
654content_merger::attribute_manual_merge(file_path const & path,
655 roster_t const & ros)
656{
657 attr_value v;
658 split_path sp;
659 path.split(sp);
660 if (ros.get_attr(sp, attr_key(constants::manual_merge_attribute), v)
661 && v() == "true")
662 return true;
663 return false; // default: enable auto merge
664}
665
666bool
667content_merger::try_to_merge_files(file_path const & anc_path,
668 file_path const & left_path,
669 file_path const & right_path,
670 file_path const & merged_path,
671 file_id const & ancestor_id,
672 file_id const & left_id,
673 file_id const & right_id,
674 file_id & merged_id)
675{
676 // This version of try_to_merge_files should only be called when there is a
677 // real merge3 to perform.
678 I(!null_id(ancestor_id));
679 I(!null_id(left_id));
680 I(!null_id(right_id));
681
682 L(FL("trying to merge %s <-> %s (ancestor: %s)")
683 % left_id % right_id % ancestor_id);
684
685 if (left_id == right_id)
686 {
687 L(FL("files are identical"));
688 merged_id = left_id;
689 return true;
690 }
691
692 file_data left_data, right_data, ancestor_data;
693 data left_unpacked, ancestor_unpacked, right_unpacked, merged_unpacked;
694
695 adaptor.get_version(left_id, left_data);
696 adaptor.get_version(ancestor_id, ancestor_data);
697 adaptor.get_version(right_id, right_data);
698
699 left_unpacked = left_data.inner();
700 ancestor_unpacked = ancestor_data.inner();
701 right_unpacked = right_data.inner();
702
703 if (!attribute_manual_merge(left_path, left_ros) &&
704 !attribute_manual_merge(right_path, right_ros))
705 {
706 // both files mergeable by monotone internal algorithm, try to merge
707 // note: the ancestor is not considered for manual merging. Forcing the
708 // user to merge manually just because of an ancestor mistakenly marked
709 // manual seems too harsh
710 string left_encoding, anc_encoding, right_encoding;
711 left_encoding = this->get_file_encoding(left_path, left_ros);
712 anc_encoding = this->get_file_encoding(anc_path, anc_ros);
713 right_encoding = this->get_file_encoding(right_path, right_ros);
714
715 vector<string> left_lines, ancestor_lines, right_lines, merged_lines;
716 split_into_lines(left_unpacked(), left_encoding, left_lines);
717 split_into_lines(ancestor_unpacked(), anc_encoding, ancestor_lines);
718 split_into_lines(right_unpacked(), right_encoding, right_lines);
719
720 if (merge3(ancestor_lines,
721 left_lines,
722 right_lines,
723 merged_lines))
724 {
725 hexenc<id> tmp_id;
726 file_data merge_data;
727 string tmp;
728
729 L(FL("internal 3-way merged ok"));
730 join_lines(merged_lines, tmp);
731 calculate_ident(data(tmp), tmp_id);
732 file_id merged_fid(tmp_id);
733 merge_data = file_data(tmp);
734
735 merged_id = merged_fid;
736 adaptor.record_merge(left_id, right_id, merged_fid,
737 left_data, merge_data);
738
739 return true;
740 }
741 }
742
743 P(F("help required for 3-way merge\n"
744 "[ancestor] %s\n"
745 "[ left] %s\n"
746 "[ right] %s\n"
747 "[ merged] %s")
748 % anc_path
749 % left_path
750 % right_path
751 % merged_path);
752
753 if (app.lua.hook_merge3(anc_path, left_path, right_path, merged_path,
754 ancestor_unpacked, left_unpacked,
755 right_unpacked, merged_unpacked))
756 {
757 hexenc<id> tmp_id;
758 file_data merge_data;
759
760 L(FL("lua merge3 hook merged ok"));
761 calculate_ident(merged_unpacked, tmp_id);
762 file_id merged_fid(tmp_id);
763 merge_data = file_data(merged_unpacked);
764
765 merged_id = merged_fid;
766 adaptor.record_merge(left_id, right_id, merged_fid,
767 left_data, merge_data);
768 return true;
769 }
770
771 return false;
772}
773
774// the remaining part of this file just handles printing out various
775// diff formats for the case where someone wants to *read* a diff
776// rather than apply it.
777
778struct hunk_consumer
779{
780 vector<string> const & a;
781 vector<string> const & b;
782 size_t ctx;
783 ostream & ost;
784 boost::scoped_ptr<boost::regex const> encloser_re;
785 size_t a_begin, b_begin, a_len, b_len;
786 long skew;
787
788 vector<string>::const_reverse_iterator encloser_last_match;
789 vector<string>::const_reverse_iterator encloser_last_search;
790
791 virtual void flush_hunk(size_t pos) = 0;
792 virtual void advance_to(size_t newpos) = 0;
793 virtual void insert_at(size_t b_pos) = 0;
794 virtual void delete_at(size_t a_pos) = 0;
795 virtual void find_encloser(size_t pos, string & encloser);
796 virtual ~hunk_consumer() {}
797 hunk_consumer(vector<string> const & a,
798 vector<string> const & b,
799 size_t ctx,
800 ostream & ost,
801 string const & encloser_pattern)
802 : a(a), b(b), ctx(ctx), ost(ost), encloser_re(0),
803 a_begin(0), b_begin(0), a_len(0), b_len(0), skew(0),
804 encloser_last_match(a.rend()), encloser_last_search(a.rend())
805 {
806 if (encloser_pattern != "")
807 encloser_re.reset(new boost::regex(encloser_pattern));
808 }
809};
810
811/* Find, and write to ENCLOSER, the nearest line before POS which matches
812 ENCLOSER_PATTERN. We remember the last line scanned, and the matched, to
813 avoid duplication of effort. */
814
815void
816hunk_consumer::find_encloser(size_t pos, string & encloser)
817{
818 typedef vector<string>::const_reverse_iterator riter;
819
820 // Precondition: encloser_last_search <= pos <= a.size().
821 I(pos <= a.size());
822 // static_cast<> to silence compiler unsigned vs. signed comparison
823 // warning, after first making sure that the static_cast is safe.
824 I(a.rend() - encloser_last_search >= 0);
825 I(pos >= static_cast<size_t>(a.rend() - encloser_last_search));
826
827 if (!encloser_re)
828 return;
829
830 riter last = encloser_last_search;
831 riter i = riter(a.begin() + pos);
832
833 encloser_last_search = i;
834
835 // i is a reverse_iterator, so this loop goes backward through the vector.
836 for (; i != last; i++)
837 if (boost::regex_search (*i, *encloser_re))
838 {
839 encloser_last_match = i;
840 break;
841 }
842
843 if (encloser_last_match == a.rend())
844 return;
845
846 L(FL("find_encloser: from %u matching %d, \"%s\"")
847 % pos % (a.rend() - encloser_last_match) % *encloser_last_match);
848
849 // the number 40 is chosen to match GNU diff. it could safely be
850 // increased up to about 60 without overflowing the standard
851 // terminal width.
852 encloser = string(" ") + (*encloser_last_match).substr(0, 40);
853}
854
855void walk_hunk_consumer(vector<long, QA(long)> const & lcs,
856 vector<long, QA(long)> const & lines1,
857 vector<long, QA(long)> const & lines2,
858 hunk_consumer & cons)
859{
860
861 size_t a = 0, b = 0;
862 if (lcs.begin() == lcs.end())
863 {
864 // degenerate case: files have nothing in common
865 cons.advance_to(0);
866 while (a < lines1.size())
867 cons.delete_at(a++);
868 while (b < lines2.size())
869 cons.insert_at(b++);
870 cons.flush_hunk(a);
871 }
872 else
873 {
874 // normal case: files have something in common
875 for (vector<long, QA(long)>::const_iterator i = lcs.begin();
876 i != lcs.end(); ++i, ++a, ++b)
877 {
878 if (idx(lines1, a) == *i && idx(lines2, b) == *i)
879 continue;
880
881 cons.advance_to(a);
882 while (idx(lines1,a) != *i)
883 cons.delete_at(a++);
884 while (idx(lines2,b) != *i)
885 cons.insert_at(b++);
886 }
887 if (b < lines2.size())
888 {
889 cons.advance_to(a);
890 while(b < lines2.size())
891 cons.insert_at(b++);
892 }
893 if (a < lines1.size())
894 {
895 cons.advance_to(a);
896 while(a < lines1.size())
897 cons.delete_at(a++);
898 }
899 cons.flush_hunk(a);
900 }
901}
902
903struct unidiff_hunk_writer : public hunk_consumer
904{
905 vector<string> hunk;
906
907 virtual void flush_hunk(size_t pos);
908 virtual void advance_to(size_t newpos);
909 virtual void insert_at(size_t b_pos);
910 virtual void delete_at(size_t a_pos);
911 virtual ~unidiff_hunk_writer() {}
912 unidiff_hunk_writer(vector<string> const & a,
913 vector<string> const & b,
914 size_t ctx,
915 ostream & ost,
916 string const & encloser_pattern)
917 : hunk_consumer(a, b, ctx, ost, encloser_pattern)
918 {}
919};
920
921void unidiff_hunk_writer::insert_at(size_t b_pos)
922{
923 b_len++;
924 hunk.push_back(string("+") + b[b_pos]);
925}
926
927void unidiff_hunk_writer::delete_at(size_t a_pos)
928{
929 a_len++;
930 hunk.push_back(string("-") + a[a_pos]);
931}
932
933void unidiff_hunk_writer::flush_hunk(size_t pos)
934{
935 if (hunk.size() > 0)
936 {
937 // insert trailing context
938 size_t a_pos = a_begin + a_len;
939 for (size_t i = 0; (i < ctx) && (a_pos + i < a.size()); ++i)
940 {
941 hunk.push_back(string(" ") + a[a_pos + i]);
942 a_len++;
943 b_len++;
944 }
945
946 // write hunk to stream
947 if (a_len == 0)
948 ost << "@@ -0,0";
949 else
950 {
951 ost << "@@ -" << a_begin+1;
952 if (a_len > 1)
953 ost << ',' << a_len;
954 }
955
956 if (b_len == 0)
957 ost << " +0,0";
958 else
959 {
960 ost << " +" << b_begin+1;
961 if (b_len > 1)
962 ost << ',' << b_len;
963 }
964
965 {
966 string encloser;
967 ptrdiff_t first_mod = 0;
968 vector<string>::const_iterator i;
969 for (i = hunk.begin(); i != hunk.end(); i++)
970 if ((*i)[0] != ' ')
971 {
972 first_mod = i - hunk.begin();
973 break;
974 }
975
976 find_encloser(a_begin + first_mod, encloser);
977 ost << " @@" << encloser << '\n';
978 }
979 copy(hunk.begin(), hunk.end(), ostream_iterator<string>(ost, "\n"));
980 }
981
982 // reset hunk
983 hunk.clear();
984 skew += b_len - a_len;
985 a_begin = pos;
986 b_begin = pos + skew;
987 a_len = 0;
988 b_len = 0;
989}
990
991void unidiff_hunk_writer::advance_to(size_t newpos)
992{
993 if (a_begin + a_len + (2 * ctx) < newpos)
994 {
995 flush_hunk(newpos);
996
997 // insert new leading context
998 if (newpos - ctx < a.size())
999 {
1000 for (size_t i = ctx; i > 0; --i)
1001 {
1002 // The original test was (newpos - i < 0), but since newpos
1003 // is size_t (unsigned), it will never go negative. Testing
1004 // that newpos is smaller than i is the same test, really.
1005 if (newpos < i)
1006 continue;
1007 hunk.push_back(string(" ") + a[newpos - i]);
1008 a_begin--; a_len++;
1009 b_begin--; b_len++;
1010 }
1011 }
1012 }
1013 else
1014 {
1015 // pad intermediate context
1016 while(a_begin + a_len < newpos)
1017 {
1018 hunk.push_back(string(" ") + a[a_begin + a_len]);
1019 a_len++;
1020 b_len++;
1021 }
1022 }
1023}
1024
1025struct cxtdiff_hunk_writer : public hunk_consumer
1026{
1027 // For context diffs, we have to queue up calls to insert_at/delete_at
1028 // until we hit an advance_to, so that we can get the tags right: an
1029 // unpaired insert gets a + in the left margin, an unpaired delete a -,
1030 // but if they are paired, they both get !. Hence, we have both the
1031 // 'inserts' and 'deletes' queues of line numbers, and the 'from_file' and
1032 // 'to_file' queues of line strings.
1033 vector<size_t> inserts;
1034 vector<size_t> deletes;
1035 vector<string> from_file;
1036 vector<string> to_file;
1037 bool have_insertions;
1038 bool have_deletions;
1039
1040 virtual void flush_hunk(size_t pos);
1041 virtual void advance_to(size_t newpos);
1042 virtual void insert_at(size_t b_pos);
1043 virtual void delete_at(size_t a_pos);
1044 void flush_pending_mods();
1045 virtual ~cxtdiff_hunk_writer() {}
1046 cxtdiff_hunk_writer(vector<string> const & a,
1047 vector<string> const & b,
1048 size_t ctx,
1049 ostream & ost,
1050 string const & encloser_pattern)
1051 : hunk_consumer(a, b, ctx, ost, encloser_pattern),
1052 have_insertions(false), have_deletions(false)
1053 {}
1054};
1055
1056void cxtdiff_hunk_writer::insert_at(size_t b_pos)
1057{
1058 inserts.push_back(b_pos);
1059 have_insertions = true;
1060}
1061
1062void cxtdiff_hunk_writer::delete_at(size_t a_pos)
1063{
1064 deletes.push_back(a_pos);
1065 have_deletions = true;
1066}
1067
1068void cxtdiff_hunk_writer::flush_hunk(size_t pos)
1069{
1070 flush_pending_mods();
1071
1072 if (have_deletions || have_insertions)
1073 {
1074 // insert trailing context
1075 size_t ctx_start = a_begin + a_len;
1076 for (size_t i = 0; (i < ctx) && (ctx_start + i < a.size()); ++i)
1077 {
1078 from_file.push_back(string(" ") + a[ctx_start + i]);
1079 a_len++;
1080 }
1081
1082 ctx_start = b_begin + b_len;
1083 for (size_t i = 0; (i < ctx) && (ctx_start + i < b.size()); ++i)
1084 {
1085 to_file.push_back(string(" ") + b[ctx_start + i]);
1086 b_len++;
1087 }
1088
1089 {
1090 string encloser;
1091 ptrdiff_t first_insert = b_len;
1092 ptrdiff_t first_delete = a_len;
1093 vector<string>::const_iterator i;
1094
1095 if (have_deletions)
1096 for (i = from_file.begin(); i != from_file.end(); i++)
1097 if ((*i)[0] != ' ')
1098 {
1099 first_delete = i - from_file.begin();
1100 break;
1101 }
1102 if (have_insertions)
1103 for (i = to_file.begin(); i != to_file.end(); i++)
1104 if ((*i)[0] != ' ')
1105 {
1106 first_insert = i - to_file.begin();
1107 break;
1108 }
1109
1110 find_encloser(a_begin + min(first_insert, first_delete),
1111 encloser);
1112
1113 ost << "***************" << encloser << '\n';
1114 }
1115
1116 ost << "*** " << (a_begin + 1) << ',' << (a_begin + a_len) << " ****\n";
1117 if (have_deletions)
1118 copy(from_file.begin(), from_file.end(), ostream_iterator<string>(ost, "\n"));
1119
1120 ost << "--- " << (b_begin + 1) << ',' << (b_begin + b_len) << " ----\n";
1121 if (have_insertions)
1122 copy(to_file.begin(), to_file.end(), ostream_iterator<string>(ost, "\n"));
1123 }
1124
1125 // reset hunk
1126 to_file.clear();
1127 from_file.clear();
1128 have_insertions = false;
1129 have_deletions = false;
1130 skew += b_len - a_len;
1131 a_begin = pos;
1132 b_begin = pos + skew;
1133 a_len = 0;
1134 b_len = 0;
1135}
1136
1137void cxtdiff_hunk_writer::flush_pending_mods()
1138{
1139 // nothing to flush?
1140 if (inserts.empty() && deletes.empty())
1141 return;
1142
1143 string prefix;
1144
1145 // if we have just insertions to flush, prefix them with "+"; if
1146 // just deletions, prefix with "-"; if both, prefix with "!"
1147 if (inserts.empty() && !deletes.empty())
1148 prefix = "-";
1149 else if (deletes.empty() && !inserts.empty())
1150 prefix = "+";
1151 else
1152 prefix = "!";
1153
1154 for (vector<size_t>::const_iterator i = deletes.begin();
1155 i != deletes.end(); ++i)
1156 {
1157 from_file.push_back(prefix + string(" ") + a[*i]);
1158 a_len++;
1159 }
1160 for (vector<size_t>::const_iterator i = inserts.begin();
1161 i != inserts.end(); ++i)
1162 {
1163 to_file.push_back(prefix + string(" ") + b[*i]);
1164 b_len++;
1165 }
1166
1167 // clear pending mods
1168 inserts.clear();
1169 deletes.clear();
1170}
1171
1172void cxtdiff_hunk_writer::advance_to(size_t newpos)
1173{
1174 // We must first flush out pending mods because otherwise our calculation
1175 // of whether we need to generate a new hunk header will be way off.
1176 // It is correct (i.e. consistent with diff(1)) to reset the +/-/!
1177 // generation algorithm between sub-components of a single hunk.
1178 flush_pending_mods();
1179
1180 if (a_begin + a_len + (2 * ctx) < newpos)
1181 {
1182 flush_hunk(newpos);
1183
1184 // insert new leading context
1185 if (newpos - ctx < a.size())
1186 {
1187 for (size_t i = ctx; i > 0; --i)
1188 {
1189 // The original test was (newpos - i < 0), but since newpos
1190 // is size_t (unsigned), it will never go negative. Testing
1191 // that newpos is smaller than i is the same test, really.
1192 if (newpos < i)
1193 continue;
1194
1195 // note that context diffs prefix common text with two
1196 // spaces, whereas unified diffs use a single space
1197 from_file.push_back(string(" ") + a[newpos - i]);
1198 to_file.push_back(string(" ") + a[newpos - i]);
1199 a_begin--; a_len++;
1200 b_begin--; b_len++;
1201 }
1202 }
1203 }
1204 else
1205 // pad intermediate context
1206 while (a_begin + a_len < newpos)
1207 {
1208 from_file.push_back(string(" ") + a[a_begin + a_len]);
1209 to_file.push_back(string(" ") + a[a_begin + a_len]);
1210 a_len++;
1211 b_len++;
1212 }
1213}
1214
1215void
1216make_diff(string const & filename1,
1217 string const & filename2,
1218 file_id const & id1,
1219 file_id const & id2,
1220 data const & data1,
1221 data const & data2,
1222 ostream & ost,
1223 diff_type type,
1224 string const & pattern)
1225{
1226 if (guess_binary(data1()) || guess_binary(data2()))
1227 {
1228 ost << "# " << filename2 << " is binary\n";
1229 return;
1230 }
1231
1232 vector<string> lines1, lines2;
1233 split_into_lines(data1(), lines1);
1234 split_into_lines(data2(), lines2);
1235
1236 vector<long, QA(long)> left_interned;
1237 vector<long, QA(long)> right_interned;
1238 vector<long, QA(long)> lcs;
1239
1240 interner<long> in;
1241
1242 left_interned.reserve(lines1.size());
1243 for (vector<string>::const_iterator i = lines1.begin();
1244 i != lines1.end(); ++i)
1245 left_interned.push_back(in.intern(*i));
1246
1247 right_interned.reserve(lines2.size());
1248 for (vector<string>::const_iterator i = lines2.begin();
1249 i != lines2.end(); ++i)
1250 right_interned.push_back(in.intern(*i));
1251
1252 lcs.reserve(min(lines1.size(),lines2.size()));
1253 longest_common_subsequence(left_interned.begin(), left_interned.end(),
1254 right_interned.begin(), right_interned.end(),
1255 min(lines1.size(), lines2.size()),
1256 back_inserter(lcs));
1257
1258 // The existence of various hacky diff parsers in the world somewhat
1259 // constrains what output we can use. Here are some notes on how various
1260 // tools interpret the header lines of a diff file:
1261 //
1262 // interdiff/filterdiff (patchutils):
1263 // Attempt to parse a timestamp after each whitespace. If they succeed,
1264 // then they take the filename as everything up to the whitespace they
1265 // succeeded at, and the timestamp as everything after. If they fail,
1266 // then they take the filename to be everything up to the first
1267 // whitespace. Have hardcoded that /dev/null and timestamps at the
1268 // epoch (in any timezone) indicate a file that did not exist.
1269 //
1270 // filterdiff filters on the first filename line. interdiff matches on
1271 // the first filename line.
1272 // PatchReader perl library (used by Bugzilla):
1273 // Takes the filename to be everything up to the first tab; requires
1274 // that there be a tab. Determines the filename based on the first
1275 // filename line.
1276 // diffstat:
1277 // Can handle pretty much everything; tries to read up to the first tab
1278 // to get the filename. Knows that "/dev/null", "", and anything
1279 // beginning "/tmp/" are meaningless. Uses the second filename line.
1280 // patch:
1281 // If there is a tab, considers everything up to that tab to be the
1282 // filename. If there is not a tab, considers everything up to the
1283 // first whitespace to be the filename.
1284 //
1285 // Contains comment: 'If the [file]name is "/dev/null", ignore the name
1286 // and mark the file as being nonexistent. The name "/dev/null" appears
1287 // in patches regardless of how NULL_DEVICE is spelled.' Also detects
1288 // timestamps at the epoch as indicating that a file does not exist.
1289 //
1290 // Uses the first filename line as the target, unless it is /dev/null or
1291 // has an epoch timestamp in which case it uses the second.
1292 // trac:
1293 // Anything up to the first whitespace, or end of line, is considered
1294 // filename. Does not care about timestamp. Uses the shorter of the
1295 // two filenames as the filename (!).
1296 //
1297 // Conclusions:
1298 // -- You must have a tab, both to prevent PatchReader blowing up, and
1299 // to make it possible to have filenames with spaces in them.
1300 // (Filenames with tabs in them are always impossible to properly
1301 // express; FIXME what should be done if one occurs?)
1302 // -- What comes after that tab matters not at all, though it probably
1303 // shouldn't look like a timestamp, or have any trailing part that
1304 // looks like a timestamp, unless it really is a timestamp. Simply
1305 // having a trailing tab should work fine.
1306 // -- If you need to express that some file does not exist, you should
1307 // use /dev/null as the path. patch(1) goes so far as to claim that
1308 // this is part of the diff format definition.
1309 // -- If you want your patches to actually _work_ with patch(1), then
1310 // renames are basically hopeless (you can do them by hand _after_
1311 // running patch), adds work so long as the first line says either
1312 // the new file's name or "/dev/null", nothing else, and deletes work
1313 // if the new file name is "/dev/null", nothing else. (ATM we don't
1314 // write out patches for deletes anyway.)
1315 switch (type)
1316 {
1317 case unified_diff:
1318 {
1319 ost << "--- " << filename1 << '\t' << id1 << '\n';
1320 ost << "+++ " << filename2 << '\t' << id2 << '\n';
1321
1322 unidiff_hunk_writer hunks(lines1, lines2, 3, ost, pattern);
1323 walk_hunk_consumer(lcs, left_interned, right_interned, hunks);
1324 break;
1325 }
1326 case context_diff:
1327 {
1328 ost << "*** " << filename1 << '\t' << id1 << '\n';
1329 ost << "--- " << filename2 << '\t' << id2 << '\n';
1330
1331 cxtdiff_hunk_writer hunks(lines1, lines2, 3, ost, pattern);
1332 walk_hunk_consumer(lcs, left_interned, right_interned, hunks);
1333 break;
1334 }
1335 default:
1336 {
1337 // should never reach this; the external_diff type is not
1338 // handled by this function.
1339 I(false);
1340 }
1341 }
1342}
1343
1344#ifdef BUILD_UNIT_TESTS
1345#include "unit_tests.hh"
1346#include "transforms.hh"
1347#include <boost/lexical_cast.hpp>
1348#include "randomfile.hh"
1349
1350using std::cerr;
1351using std::cout;
1352using std::stringstream;
1353
1354using boost::lexical_cast;
1355
1356static void dump_incorrect_merge(vector<string> const & expected,
1357 vector<string> const & got,
1358 string const & prefix)
1359{
1360 size_t mx = expected.size();
1361 if (mx < got.size())
1362 mx = got.size();
1363 for (size_t i = 0; i < mx; ++i)
1364 {
1365 cerr << "bad merge: " << i << " [" << prefix << "]\t";
1366
1367 if (i < expected.size())
1368 cerr << '[' << expected[i] << "]\t";
1369 else
1370 cerr << "[--nil--]\t";
1371
1372 if (i < got.size())
1373 cerr << '[' << got[i] << "]\t";
1374 else
1375 cerr << "[--nil--]\t";
1376
1377 cerr << '\n';
1378 }
1379}
1380
1381// high tech randomizing test
1382UNIT_TEST(diff_patch, randomizing_merge)
1383{
1384 randomizer rng;
1385 for (int i = 0; i < 30; ++i)
1386 {
1387 vector<string> anc, d1, d2, m1, m2, gm;
1388
1389 file_randomizer::build_random_fork(anc, d1, d2, gm, (10 + 2 * i), rng);
1390
1391 BOOST_CHECK(merge3(anc, d1, d2, m1));
1392 if (gm != m1)
1393 dump_incorrect_merge (gm, m1, "random_merge 1");
1394 BOOST_CHECK(gm == m1);
1395
1396 BOOST_CHECK(merge3(anc, d2, d1, m2));
1397 if (gm != m2)
1398 dump_incorrect_merge (gm, m2, "random_merge 2");
1399 BOOST_CHECK(gm == m2);
1400 }
1401}
1402
1403
1404// old boring tests
1405UNIT_TEST(diff_patch, merge_prepend)
1406{
1407 BOOST_CHECKPOINT("prepend test");
1408 vector<string> anc, d1, d2, m1, m2, gm;
1409 for (int i = 10; i < 20; ++i)
1410 {
1411 d2.push_back(lexical_cast<string>(i));
1412 gm.push_back(lexical_cast<string>(i));
1413 }
1414
1415 for (int i = 0; i < 10; ++i)
1416 {
1417 anc.push_back(lexical_cast<string>(i));
1418 d1.push_back(lexical_cast<string>(i));
1419 d2.push_back(lexical_cast<string>(i));
1420 gm.push_back(lexical_cast<string>(i));
1421 }
1422
1423 BOOST_CHECK(merge3(anc, d1, d2, m1));
1424 if (gm != m1)
1425 dump_incorrect_merge (gm, m1, "merge_prepend 1");
1426 BOOST_CHECK(gm == m1);
1427
1428
1429 BOOST_CHECK(merge3(anc, d2, d1, m2));
1430 if (gm != m2)
1431 dump_incorrect_merge (gm, m2, "merge_prepend 2");
1432 BOOST_CHECK(gm == m2);
1433}
1434
1435UNIT_TEST(diff_patch, merge_append)
1436{
1437 BOOST_CHECKPOINT("append test");
1438 vector<string> anc, d1, d2, m1, m2, gm;
1439 for (int i = 0; i < 10; ++i)
1440 anc.push_back(lexical_cast<string>(i));
1441
1442 d1 = anc;
1443 d2 = anc;
1444 gm = anc;
1445
1446 for (int i = 10; i < 20; ++i)
1447 {
1448 d2.push_back(lexical_cast<string>(i));
1449 gm.push_back(lexical_cast<string>(i));
1450 }
1451
1452 BOOST_CHECK(merge3(anc, d1, d2, m1));
1453 if (gm != m1)
1454 dump_incorrect_merge (gm, m1, "merge_append 1");
1455 BOOST_CHECK(gm == m1);
1456
1457 BOOST_CHECK(merge3(anc, d2, d1, m2));
1458 if (gm != m2)
1459 dump_incorrect_merge (gm, m2, "merge_append 2");
1460 BOOST_CHECK(gm == m2);
1461
1462
1463}
1464
1465UNIT_TEST(diff_patch, merge_additions)
1466{
1467 BOOST_CHECKPOINT("additions test");
1468 string ancestor("I like oatmeal\nI like orange juice\nI like toast");
1469 string desc1("I like oatmeal\nI don't like spam\nI like orange juice\nI like toast");
1470 string confl("I like oatmeal\nI don't like tuna\nI like orange juice\nI like toast");
1471 string desc2("I like oatmeal\nI like orange juice\nI don't like tuna\nI like toast");
1472 string good_merge("I like oatmeal\nI don't like spam\nI like orange juice\nI don't like tuna\nI like toast");
1473 vector<string> anc, d1, cf, d2, m1, m2, gm;
1474
1475 split_into_lines(ancestor, anc);
1476 split_into_lines(desc1, d1);
1477 split_into_lines(confl, cf);
1478 split_into_lines(desc2, d2);
1479 split_into_lines(good_merge, gm);
1480
1481 BOOST_CHECK(merge3(anc, d1, d2, m1));
1482 if (gm != m1)
1483 dump_incorrect_merge (gm, m1, "merge_addition 1");
1484 BOOST_CHECK(gm == m1);
1485
1486 BOOST_CHECK(merge3(anc, d2, d1, m2));
1487 if (gm != m2)
1488 dump_incorrect_merge (gm, m2, "merge_addition 2");
1489 BOOST_CHECK(gm == m2);
1490
1491 BOOST_CHECK(!merge3(anc, d1, cf, m1));
1492}
1493
1494UNIT_TEST(diff_patch, merge_deletions)
1495{
1496 string ancestor("I like oatmeal\nI like orange juice\nI like toast");
1497 string desc2("I like oatmeal\nI like toast");
1498
1499 vector<string> anc, d1, d2, m1, m2, gm;
1500
1501 split_into_lines(ancestor, anc);
1502 split_into_lines(desc2, d2);
1503 d1 = anc;
1504 gm = d2;
1505
1506 BOOST_CHECK(merge3(anc, d1, d2, m1));
1507 if (gm != m1)
1508 dump_incorrect_merge (gm, m1, "merge_deletion 1");
1509 BOOST_CHECK(gm == m1);
1510
1511 BOOST_CHECK(merge3(anc, d2, d1, m2));
1512 if (gm != m2)
1513 dump_incorrect_merge (gm, m2, "merge_deletion 2");
1514 BOOST_CHECK(gm == m2);
1515}
1516
1517#endif // BUILD_UNIT_TESTS
1518
1519// Local Variables:
1520// mode: C++
1521// fill-column: 76
1522// c-file-style: "gnu"
1523// indent-tabs-mode: nil
1524// End:
1525// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

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