source: trunk/forum/includes/diff/diff.php

Last change on this file was 702, checked in by george, 15 years ago
  • Upraveno: Aktualizace fóra.
File size: 23.7 KB
Line 
1<?php
2/**
3*
4* @package diff
5* @version $Id$
6* @copyright (c) 2006 phpBB Group
7* @license http://opensource.org/licenses/gpl-license.php GNU Public License
8*
9*/
10
11/**
12* @ignore
13*/
14if (!defined('IN_PHPBB'))
15{
16 exit;
17}
18
19/**
20* Code from pear.php.net, Text_Diff-1.1.0 package
21* http://pear.php.net/package/Text_Diff/
22*
23* Modified by phpBB Group to meet our coding standards
24* and being able to integrate into phpBB
25*
26* General API for generating and formatting diffs - the differences between
27* two sequences of strings.
28*
29* Copyright 2004 Geoffrey T. Dairiki <dairiki@dairiki.org>
30* Copyright 2004-2008 The Horde Project (http://www.horde.org/)
31*
32* @package diff
33* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
34*/
35class diff
36{
37 /**
38 * Array of changes.
39 * @var array
40 */
41 var $_edits;
42
43 /**
44 * Computes diffs between sequences of strings.
45 *
46 * @param array $from_lines An array of strings. Typically these are lines from a file.
47 * @param array $to_lines An array of strings.
48 */
49 function diff(&$from_content, &$to_content, $preserve_cr = true)
50 {
51 $diff_engine = new diff_engine();
52 $this->_edits = $diff_engine->diff($from_content, $to_content, $preserve_cr);
53 }
54
55 /**
56 * Returns the array of differences.
57 */
58 function get_diff()
59 {
60 return $this->_edits;
61 }
62
63 /**
64 * returns the number of new (added) lines in a given diff.
65 *
66 * @since Text_Diff 1.1.0
67 *
68 * @return integer The number of new lines
69 */
70 function count_added_lines()
71 {
72 $count = 0;
73
74 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
75 {
76 $edit = $this->_edits[$i];
77
78 if (is_a($edit, 'diff_op_add') || is_a($edit, 'diff_op_change'))
79 {
80 $count += $edit->nfinal();
81 }
82 }
83 return $count;
84 }
85
86 /**
87 * Returns the number of deleted (removed) lines in a given diff.
88 *
89 * @since Text_Diff 1.1.0
90 *
91 * @return integer The number of deleted lines
92 */
93 function count_deleted_lines()
94 {
95 $count = 0;
96
97 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
98 {
99 $edit = $this->_edits[$i];
100
101 if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_change'))
102 {
103 $count += $edit->norig();
104 }
105 }
106 return $count;
107 }
108
109 /**
110 * Computes a reversed diff.
111 *
112 * Example:
113 * <code>
114 * $diff = new diff($lines1, $lines2);
115 * $rev = $diff->reverse();
116 * </code>
117 *
118 * @return diff A Diff object representing the inverse of the original diff.
119 * Note that we purposely don't return a reference here, since
120 * this essentially is a clone() method.
121 */
122 function reverse()
123 {
124 if (version_compare(zend_version(), '2', '>'))
125 {
126 $rev = clone($this);
127 }
128 else
129 {
130 $rev = $this;
131 }
132
133 $rev->_edits = array();
134
135 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
136 {
137 $edit = $this->_edits[$i];
138 $rev->_edits[] = $edit->reverse();
139 }
140
141 return $rev;
142 }
143
144 /**
145 * Checks for an empty diff.
146 *
147 * @return boolean True if two sequences were identical.
148 */
149 function is_empty()
150 {
151 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
152 {
153 $edit = $this->_edits[$i];
154
155 // skip diff_op_copy
156 if (is_a($edit, 'diff_op_copy'))
157 {
158 continue;
159 }
160
161 if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_add'))
162 {
163 $orig = $edit->orig;
164 $final = $edit->final;
165
166 // We can simplify one case where the array is usually supposed to be empty...
167 if (sizeof($orig) == 1 && trim($orig[0]) === '') $orig = array();
168 if (sizeof($final) == 1 && trim($final[0]) === '') $final = array();
169
170 if (!$orig && !$final)
171 {
172 continue;
173 }
174
175 return false;
176 }
177
178 return false;
179 }
180
181 return true;
182 }
183
184 /**
185 * Computes the length of the Longest Common Subsequence (LCS).
186 *
187 * This is mostly for diagnostic purposes.
188 *
189 * @return integer The length of the LCS.
190 */
191 function lcs()
192 {
193 $lcs = 0;
194
195 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
196 {
197 $edit = $this->_edits[$i];
198
199 if (is_a($edit, 'diff_op_copy'))
200 {
201 $lcs += sizeof($edit->orig);
202 }
203 }
204 return $lcs;
205 }
206
207 /**
208 * Gets the original set of lines.
209 *
210 * This reconstructs the $from_lines parameter passed to the constructor.
211 *
212 * @return array The original sequence of strings.
213 */
214 function get_original()
215 {
216 $lines = array();
217
218 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
219 {
220 $edit = $this->_edits[$i];
221
222 if ($edit->orig)
223 {
224 array_splice($lines, sizeof($lines), 0, $edit->orig);
225 }
226 }
227 return $lines;
228 }
229
230 /**
231 * Gets the final set of lines.
232 *
233 * This reconstructs the $to_lines parameter passed to the constructor.
234 *
235 * @return array The sequence of strings.
236 */
237 function get_final()
238 {
239 $lines = array();
240
241 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
242 {
243 $edit = $this->_edits[$i];
244
245 if ($edit->final)
246 {
247 array_splice($lines, sizeof($lines), 0, $edit->final);
248 }
249 }
250 return $lines;
251 }
252
253 /**
254 * Removes trailing newlines from a line of text. This is meant to be used with array_walk().
255 *
256 * @param string &$line The line to trim.
257 * @param integer $key The index of the line in the array. Not used.
258 */
259 function trim_newlines(&$line, $key)
260 {
261 $line = str_replace(array("\n", "\r"), '', $line);
262 }
263
264 /**
265 * Checks a diff for validity.
266 *
267 * This is here only for debugging purposes.
268 */
269 function _check($from_lines, $to_lines)
270 {
271 if (serialize($from_lines) != serialize($this->get_original()))
272 {
273 trigger_error("[diff] Reconstructed original doesn't match", E_USER_ERROR);
274 }
275
276 if (serialize($to_lines) != serialize($this->get_final()))
277 {
278 trigger_error("[diff] Reconstructed final doesn't match", E_USER_ERROR);
279 }
280
281 $rev = $this->reverse();
282
283 if (serialize($to_lines) != serialize($rev->get_original()))
284 {
285 trigger_error("[diff] Reversed original doesn't match", E_USER_ERROR);
286 }
287
288 if (serialize($from_lines) != serialize($rev->get_final()))
289 {
290 trigger_error("[diff] Reversed final doesn't match", E_USER_ERROR);
291 }
292
293 $prevtype = null;
294
295 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
296 {
297 $edit = $this->_edits[$i];
298
299 if ($prevtype == get_class($edit))
300 {
301 trigger_error("[diff] Edit sequence is non-optimal", E_USER_ERROR);
302 }
303 $prevtype = get_class($edit);
304 }
305
306 return true;
307 }
308}
309
310/**
311* @package diff
312* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
313*/
314class mapped_diff extends diff
315{
316 /**
317 * Computes a diff between sequences of strings.
318 *
319 * This can be used to compute things like case-insensitve diffs, or diffs
320 * which ignore changes in white-space.
321 *
322 * @param array $from_lines An array of strings.
323 * @param array $to_lines An array of strings.
324 * @param array $mapped_from_lines This array should have the same size number of elements as $from_lines.
325 * The elements in $mapped_from_lines and $mapped_to_lines are what is actually
326 * compared when computing the diff.
327 * @param array $mapped_to_lines This array should have the same number of elements as $to_lines.
328 */
329 function mapped_diff(&$from_lines, &$to_lines, &$mapped_from_lines, &$mapped_to_lines)
330 {
331 if (sizeof($from_lines) != sizeof($mapped_from_lines) || sizeof($to_lines) != sizeof($mapped_to_lines))
332 {
333 return false;
334 }
335
336 parent::diff($mapped_from_lines, $mapped_to_lines);
337
338 $xi = $yi = 0;
339 for ($i = 0; $i < sizeof($this->_edits); $i++)
340 {
341 $orig = &$this->_edits[$i]->orig;
342 if (is_array($orig))
343 {
344 $orig = array_slice($from_lines, $xi, sizeof($orig));
345 $xi += sizeof($orig);
346 }
347
348 $final = &$this->_edits[$i]->final;
349 if (is_array($final))
350 {
351 $final = array_slice($to_lines, $yi, sizeof($final));
352 $yi += sizeof($final);
353 }
354 }
355 }
356}
357
358/**
359* @package diff
360* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
361*
362* @access private
363*/
364class diff_op
365{
366 var $orig;
367 var $final;
368
369 function &reverse()
370 {
371 trigger_error('[diff] Abstract method', E_USER_ERROR);
372 }
373
374 function norig()
375 {
376 return ($this->orig) ? sizeof($this->orig) : 0;
377 }
378
379 function nfinal()
380 {
381 return ($this->final) ? sizeof($this->final) : 0;
382 }
383}
384
385/**
386* @package diff
387* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
388*
389* @access private
390*/
391class diff_op_copy extends diff_op
392{
393 function diff_op_copy($orig, $final = false)
394 {
395 if (!is_array($final))
396 {
397 $final = $orig;
398 }
399 $this->orig = $orig;
400 $this->final = $final;
401 }
402
403 function &reverse()
404 {
405 $reverse = new diff_op_copy($this->final, $this->orig);
406 return $reverse;
407 }
408}
409
410/**
411* @package diff
412* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
413*
414* @access private
415*/
416class diff_op_delete extends diff_op
417{
418 function diff_op_delete($lines)
419 {
420 $this->orig = $lines;
421 $this->final = false;
422 }
423
424 function &reverse()
425 {
426 $reverse = new diff_op_add($this->orig);
427 return $reverse;
428 }
429}
430
431/**
432* @package diff
433* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
434*
435* @access private
436*/
437class diff_op_add extends diff_op
438{
439 function diff_op_add($lines)
440 {
441 $this->final = $lines;
442 $this->orig = false;
443 }
444
445 function &reverse()
446 {
447 $reverse = new diff_op_delete($this->final);
448 return $reverse;
449 }
450}
451
452/**
453* @package diff
454* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
455*
456* @access private
457*/
458class diff_op_change extends diff_op
459{
460 function diff_op_change($orig, $final)
461 {
462 $this->orig = $orig;
463 $this->final = $final;
464 }
465
466 function &reverse()
467 {
468 $reverse = new diff_op_change($this->final, $this->orig);
469 return $reverse;
470 }
471}
472
473
474/**
475* A class for computing three way diffs.
476*
477* @package diff
478* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
479*/
480class diff3 extends diff
481{
482 /**
483 * Conflict counter.
484 * @var integer
485 */
486 var $_conflicting_blocks = 0;
487
488 /**
489 * Computes diff between 3 sequences of strings.
490 *
491 * @param array $orig The original lines to use.
492 * @param array $final1 The first version to compare to.
493 * @param array $final2 The second version to compare to.
494 */
495 function diff3(&$orig, &$final1, &$final2, $preserve_cr = true)
496 {
497 $diff_engine = new diff_engine();
498
499 $diff_1 = $diff_engine->diff($orig, $final1, $preserve_cr);
500 $diff_2 = $diff_engine->diff($orig, $final2, $preserve_cr);
501
502 unset($diff_engine);
503
504 $this->_edits = $this->_diff3($diff_1, $diff_2);
505 }
506
507 /**
508 * Return number of conflicts
509 */
510 function get_num_conflicts()
511 {
512 $conflicts = 0;
513
514 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
515 {
516 $edit = $this->_edits[$i];
517
518 if ($edit->is_conflict())
519 {
520 $conflicts++;
521 }
522 }
523
524 return $conflicts;
525 }
526
527 /**
528 * Get conflicts content for download. This is generally a merged file, but preserving conflicts and adding explanations to it.
529 * A user could then go through this file, search for the conflicts and changes the code accordingly.
530 *
531 * @param string $label1 the cvs file version/label from the original set of lines
532 * @param string $label2 the cvs file version/label from the new set of lines
533 * @param string $label_sep the explanation between label1 and label2 - more of a helper for the user
534 *
535 * @return mixed the merged output
536 */
537 function get_conflicts_content($label1 = 'CURRENT_FILE', $label2 = 'NEW_FILE', $label_sep = 'DIFF_SEP_EXPLAIN')
538 {
539 global $user;
540
541 $label1 = (!empty($user->lang[$label1])) ? $user->lang[$label1] : $label1;
542 $label2 = (!empty($user->lang[$label2])) ? $user->lang[$label2] : $label2;
543 $label_sep = (!empty($user->lang[$label_sep])) ? $user->lang[$label_sep] : $label_sep;
544
545 $lines = array();
546
547 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
548 {
549 $edit = $this->_edits[$i];
550
551 if ($edit->is_conflict())
552 {
553 // Start conflict label
554 $label_start = array('<<<<<<< ' . $label1);
555 $label_mid = array('======= ' . $label_sep);
556 $label_end = array('>>>>>>> ' . $label2);
557
558 $lines = array_merge($lines, $label_start, $edit->final1, $label_mid, $edit->final2, $label_end);
559 $this->_conflicting_blocks++;
560 }
561 else
562 {
563 $lines = array_merge($lines, $edit->merged());
564 }
565 }
566
567 return $lines;
568 }
569
570 /**
571 * Return merged output (used by the renderer)
572 *
573 * @return mixed the merged output
574 */
575 function merged_output()
576 {
577 return $this->get_conflicts_content();
578 }
579
580 /**
581 * Merge the output and use the new file code for conflicts
582 */
583 function merged_new_output()
584 {
585 $lines = array();
586
587 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
588 {
589 $edit = $this->_edits[$i];
590
591 if ($edit->is_conflict())
592 {
593 $lines = array_merge($lines, $edit->final2);
594 }
595 else
596 {
597 $lines = array_merge($lines, $edit->merged());
598 }
599 }
600
601 return $lines;
602 }
603
604 /**
605 * Merge the output and use the original file code for conflicts
606 */
607 function merged_orig_output()
608 {
609 $lines = array();
610
611 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
612 {
613 $edit = $this->_edits[$i];
614
615 if ($edit->is_conflict())
616 {
617 $lines = array_merge($lines, $edit->final1);
618 }
619 else
620 {
621 $lines = array_merge($lines, $edit->merged());
622 }
623 }
624
625 return $lines;
626 }
627
628 /**
629 * Get conflicting block(s)
630 */
631 function get_conflicts()
632 {
633 $conflicts = array();
634
635 for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
636 {
637 $edit = $this->_edits[$i];
638
639 if ($edit->is_conflict())
640 {
641 $conflicts[] = array($edit->final1, $edit->final2);
642 }
643 }
644
645 return $conflicts;
646 }
647
648 /**
649 * @access private
650 */
651 function _diff3(&$edits1, &$edits2)
652 {
653 $edits = array();
654 $bb = new diff3_block_builder();
655
656 $e1 = current($edits1);
657 $e2 = current($edits2);
658
659 while ($e1 || $e2)
660 {
661 if ($e1 && $e2 && is_a($e1, 'diff_op_copy') && is_a($e2, 'diff_op_copy'))
662 {
663 // We have copy blocks from both diffs. This is the (only) time we want to emit a diff3 copy block.
664 // Flush current diff3 diff block, if any.
665 if ($edit = $bb->finish())
666 {
667 $edits[] = $edit;
668 }
669
670 $ncopy = min($e1->norig(), $e2->norig());
671 $edits[] = new diff3_op_copy(array_slice($e1->orig, 0, $ncopy));
672
673 if ($e1->norig() > $ncopy)
674 {
675 array_splice($e1->orig, 0, $ncopy);
676 array_splice($e1->final, 0, $ncopy);
677 }
678 else
679 {
680 $e1 = next($edits1);
681 }
682
683 if ($e2->norig() > $ncopy)
684 {
685 array_splice($e2->orig, 0, $ncopy);
686 array_splice($e2->final, 0, $ncopy);
687 }
688 else
689 {
690 $e2 = next($edits2);
691 }
692 }
693 else
694 {
695 if ($e1 && $e2)
696 {
697 if ($e1->orig && $e2->orig)
698 {
699 $norig = min($e1->norig(), $e2->norig());
700 $orig = array_splice($e1->orig, 0, $norig);
701 array_splice($e2->orig, 0, $norig);
702 $bb->input($orig);
703 }
704 else
705 {
706 $norig = 0;
707 }
708
709 if (is_a($e1, 'diff_op_copy'))
710 {
711 $bb->out1(array_splice($e1->final, 0, $norig));
712 }
713
714 if (is_a($e2, 'diff_op_copy'))
715 {
716 $bb->out2(array_splice($e2->final, 0, $norig));
717 }
718 }
719
720 if ($e1 && ! $e1->orig)
721 {
722 $bb->out1($e1->final);
723 $e1 = next($edits1);
724 }
725
726 if ($e2 && ! $e2->orig)
727 {
728 $bb->out2($e2->final);
729 $e2 = next($edits2);
730 }
731 }
732 }
733
734 if ($edit = $bb->finish())
735 {
736 $edits[] = $edit;
737 }
738
739 return $edits;
740 }
741}
742
743/**
744* @package diff
745* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
746*
747* @access private
748*/
749class diff3_op
750{
751 function diff3_op($orig = false, $final1 = false, $final2 = false)
752 {
753 $this->orig = $orig ? $orig : array();
754 $this->final1 = $final1 ? $final1 : array();
755 $this->final2 = $final2 ? $final2 : array();
756 }
757
758 function merged()
759 {
760 if (!isset($this->_merged))
761 {
762 // Prepare the arrays before we compare them. ;)
763 $this->solve_prepare();
764
765 if ($this->final1 === $this->final2)
766 {
767 $this->_merged = &$this->final1;
768 }
769 else if ($this->final1 === $this->orig)
770 {
771 $this->_merged = &$this->final2;
772 }
773 else if ($this->final2 === $this->orig)
774 {
775 $this->_merged = &$this->final1;
776 }
777 else
778 {
779 // The following tries to aggressively solve conflicts...
780 $this->_merged = false;
781 $this->solve_conflict();
782 }
783 }
784
785 return $this->_merged;
786 }
787
788 function is_conflict()
789 {
790 return ($this->merged() === false) ? true : false;
791 }
792
793 /**
794 * Function to prepare the arrays for comparing - we want to skip over newline changes
795 * @author acydburn
796 */
797 function solve_prepare()
798 {
799 // We can simplify one case where the array is usually supposed to be empty...
800 if (sizeof($this->orig) == 1 && trim($this->orig[0]) === '') $this->orig = array();
801 if (sizeof($this->final1) == 1 && trim($this->final1[0]) === '') $this->final1 = array();
802 if (sizeof($this->final2) == 1 && trim($this->final2[0]) === '') $this->final2 = array();
803
804 // Now we only can have the case where the only difference between arrays are newlines, so compare all cases
805
806 // First, some strings we can compare...
807 $orig = $final1 = $final2 = '';
808
809 foreach ($this->orig as $null => $line) $orig .= trim($line);
810 foreach ($this->final1 as $null => $line) $final1 .= trim($line);
811 foreach ($this->final2 as $null => $line) $final2 .= trim($line);
812
813 // final1 === final2
814 if ($final1 === $final2)
815 {
816 // We preserve the part which will be used in the merge later
817 $this->final2 = $this->final1;
818 }
819 // final1 === orig
820 else if ($final1 === $orig)
821 {
822 // Here it does not really matter what we choose, but we will use the new code
823 $this->orig = $this->final1;
824 }
825 // final2 === orig
826 else if ($final2 === $orig)
827 {
828 // Here it does not really matter too (final1 will be used), but we will use the new code
829 $this->orig = $this->final2;
830 }
831 }
832
833 /**
834 * Find code portions from $orig in $final1 and use $final2 as merged instance if provided
835 * @author acydburn
836 */
837 function _compare_conflict_seq($orig, $final1, $final2 = false)
838 {
839 $result = array('merge_found' => false, 'merge' => array());
840
841 $_orig = &$this->$orig;
842 $_final1 = &$this->$final1;
843
844 // Ok, we basically search for $orig in $final1
845 $compare_seq = sizeof($_orig);
846
847 // Go through the conflict code
848 for ($i = 0, $j = 0, $size = sizeof($_final1); $i < $size; $i++, $j = $i)
849 {
850 $line = $_final1[$i];
851 $skip = 0;
852
853 for ($x = 0; $x < $compare_seq; $x++)
854 {
855 // Try to skip all matching lines
856 if (trim($line) === trim($_orig[$x]))
857 {
858 $line = (++$j < $size) ? $_final1[$j] : $line;
859 $skip++;
860 }
861 }
862
863 if ($skip === $compare_seq)
864 {
865 $result['merge_found'] = true;
866
867 if ($final2 !== false)
868 {
869 $result['merge'] = array_merge($result['merge'], $this->$final2);
870 }
871 $i += ($skip - 1);
872 }
873 else if ($final2 !== false)
874 {
875 $result['merge'][] = $line;
876 }
877 }
878
879 return $result;
880 }
881
882 /**
883 * Tries to solve conflicts aggressively based on typical "assumptions"
884 * @author acydburn
885 */
886 function solve_conflict()
887 {
888 $this->_merged = false;
889
890 // CASE ONE: orig changed into final2, but modified/unknown code in final1.
891 // IF orig is found "as is" in final1 we replace the code directly in final1 and populate this as final2/merge
892 if (sizeof($this->orig) && sizeof($this->final2))
893 {
894 $result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
895
896 if ($result['merge_found'])
897 {
898 $this->final2 = $result['merge'];
899 $this->_merged = &$this->final2;
900 return;
901 }
902
903 $result = $this->_compare_conflict_seq('final2', 'final1');
904
905 if ($result['merge_found'])
906 {
907 $this->_merged = &$this->final1;
908 return;
909 }
910
911 // Try to solve $Id$ issues. ;)
912 if (sizeof($this->orig) == 1 && sizeof($this->final1) == 1 && sizeof($this->final2) == 1)
913 {
914 $match = '#^' . preg_quote('* @version $Id: ', '#') . '[a-z\._\- ]+[0-9]+ [0-9]{4}-[0-9]{2}-[0-9]{2} [0-9\:Z]+ [a-z0-9_\- ]+\$$#';
915
916 if (preg_match($match, $this->orig[0]) && preg_match($match, $this->final1[0]) && preg_match($match, $this->final2[0]))
917 {
918 $this->_merged = &$this->final2;
919 return;
920 }
921 }
922
923 $second_run = false;
924
925 // Try to solve issues where the only reason why the above did not work is a newline being removed in the final1 code but exist in the orig/final2 code
926 if (trim($this->orig[0]) === '' && trim($this->final2[0]) === '')
927 {
928 unset($this->orig[0], $this->final2[0]);
929 $this->orig = array_values($this->orig);
930 $this->final2 = array_values($this->final2);
931
932 $second_run = true;
933 }
934
935 // The same is true for a line at the end. ;)
936 if (sizeof($this->orig) && sizeof($this->final2) && sizeof($this->orig) === sizeof($this->final2) && trim($this->orig[sizeof($this->orig)-1]) === '' && trim($this->final2[sizeof($this->final2)-1]) === '')
937 {
938 unset($this->orig[sizeof($this->orig)-1], $this->final2[sizeof($this->final2)-1]);
939 $this->orig = array_values($this->orig);
940 $this->final2 = array_values($this->final2);
941
942 $second_run = true;
943 }
944
945 if ($second_run)
946 {
947 $result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
948
949 if ($result['merge_found'])
950 {
951 $this->final2 = $result['merge'];
952 $this->_merged = &$this->final2;
953 return;
954 }
955
956 $result = $this->_compare_conflict_seq('final2', 'final1');
957
958 if ($result['merge_found'])
959 {
960 $this->_merged = &$this->final1;
961 return;
962 }
963 }
964
965 return;
966 }
967
968 // CASE TWO: Added lines from orig to final2 but final1 had added lines too. Just merge them.
969 if (!sizeof($this->orig) && $this->final1 !== $this->final2 && sizeof($this->final1) && sizeof($this->final2))
970 {
971 $result = $this->_compare_conflict_seq('final2', 'final1');
972
973 if ($result['merge_found'])
974 {
975 $this->final2 = $this->final1;
976 $this->_merged = &$this->final1;
977 }
978 else
979 {
980 $result = $this->_compare_conflict_seq('final1', 'final2');
981
982 if (!$result['merge_found'])
983 {
984 $this->final2 = array_merge($this->final1, $this->final2);
985 $this->_merged = &$this->final2;
986 }
987 else
988 {
989 $this->final2 = $this->final1;
990 $this->_merged = &$this->final1;
991 }
992 }
993
994 return;
995 }
996
997 // CASE THREE: Removed lines (orig has the to-remove line(s), but final1 has additional lines which does not need to be removed). Just remove orig from final1 and then use final1 as final2/merge
998 if (!sizeof($this->final2) && sizeof($this->orig) && sizeof($this->final1) && $this->orig !== $this->final1)
999 {
1000 $result = $this->_compare_conflict_seq('orig', 'final1');
1001
1002 if (!$result['merge_found'])
1003 {
1004 return;
1005 }
1006
1007 // First of all, try to find the code in orig in final1. ;)
1008 $compare_seq = sizeof($this->orig);
1009 $begin = $end = -1;
1010 $j = 0;
1011
1012 for ($i = 0, $size = sizeof($this->final1); $i < $size; $i++)
1013 {
1014 $line = $this->final1[$i];
1015
1016 if (trim($line) === trim($this->orig[$j]))
1017 {
1018 // Mark begin
1019 if ($begin === -1)
1020 {
1021 $begin = $i;
1022 }
1023
1024 // End is always $i, the last found line
1025 $end = $i;
1026
1027 if (isset($this->orig[$j+1]))
1028 {
1029 $j++;
1030 }
1031 }
1032 }
1033
1034 if ($begin !== -1 && $begin + ($compare_seq - 1) == $end)
1035 {
1036 foreach ($this->final1 as $i => $line)
1037 {
1038 if ($i < $begin || $i > $end)
1039 {
1040 $merged[] = $line;
1041 }
1042 }
1043
1044 $this->final2 = $merged;
1045 $this->_merged = &$this->final2;
1046 }
1047
1048 return;
1049 }
1050
1051 return;
1052 }
1053}
1054
1055/**
1056* @package diff
1057* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
1058*
1059* @access private
1060*/
1061class diff3_op_copy extends diff3_op
1062{
1063 function diff3_op_copy($lines = false)
1064 {
1065 $this->orig = $lines ? $lines : array();
1066 $this->final1 = &$this->orig;
1067 $this->final2 = &$this->orig;
1068 }
1069
1070 function merged()
1071 {
1072 return $this->orig;
1073 }
1074
1075 function is_conflict()
1076 {
1077 return false;
1078 }
1079}
1080
1081/**
1082* @package diff
1083* @author Geoffrey T. Dairiki <dairiki@dairiki.org>
1084*
1085* @access private
1086*/
1087class diff3_block_builder
1088{
1089 function diff3_block_builder()
1090 {
1091 $this->_init();
1092 }
1093
1094 function input($lines)
1095 {
1096 if ($lines)
1097 {
1098 $this->_append($this->orig, $lines);
1099 }
1100 }
1101
1102 function out1($lines)
1103 {
1104 if ($lines)
1105 {
1106 $this->_append($this->final1, $lines);
1107 }
1108 }
1109
1110 function out2($lines)
1111 {
1112 if ($lines)
1113 {
1114 $this->_append($this->final2, $lines);
1115 }
1116 }
1117
1118 function is_empty()
1119 {
1120 return !$this->orig && !$this->final1 && !$this->final2;
1121 }
1122
1123 function finish()
1124 {
1125 if ($this->is_empty())
1126 {
1127 return false;
1128 }
1129 else
1130 {
1131 $edit = new diff3_op($this->orig, $this->final1, $this->final2);
1132 $this->_init();
1133 return $edit;
1134 }
1135 }
1136
1137 function _init()
1138 {
1139 $this->orig = $this->final1 = $this->final2 = array();
1140 }
1141
1142 function _append(&$array, $lines)
1143 {
1144 array_splice($array, sizeof($array), 0, $lines);
1145 }
1146}
1147
1148?>
Note: See TracBrowser for help on using the repository browser.