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