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