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