r76252 MediaWiki - Code Review archive

Repository:MediaWiki
Revision:< r76251‎ | r76252 | r76253 >
Date:16:28, 7 November 2010
Author:ialex
Status:resolved (Comments)
Tags:
Comment:
* (bug 24833) Files name in includes/diff/ are now less confusing

Diff.php -> WikiDiff3.php, more descriptive
DifferenceEngine.php -> WikiDiff.php, for consistency with the above and to make way for the file below
DifferenceInterface.php -> DifferenceEngine.php, since it contains the DifferenceEngine class
Modified paths:
  • /trunk/phase3/RELEASE-NOTES (modified) (history)
  • /trunk/phase3/includes/AutoLoader.php (modified) (history)
  • /trunk/phase3/includes/diff/Diff.php (deleted) (history)
  • /trunk/phase3/includes/diff/DifferenceEngine.php (replaced) (history)
  • /trunk/phase3/includes/diff/DifferenceInterface.php (deleted) (history)
  • /trunk/phase3/includes/diff/WikiDiff.php (added) (history)
  • /trunk/phase3/includes/diff/WikiDiff3.php (added) (history)

Diff [purge]

Index: trunk/phase3/RELEASE-NOTES
——@@ -401,6 +401,7 @@
402402 * Cache multiple sizes of InstantCommons thumbnails
403403 * (bug 25488) Disallowing anonymous users to read pages no longer throws error
404404 on discussion pages with vector as default skin
 405+* (bug 24833) Files name in includes/diff/ are now less confusing
405406
406407 === API changes in 1.17 ===
407408 * (bug 22738) Allow filtering by action type on query=logevent.
Index: trunk/phase3/includes/AutoLoader.php
——@@ -398,23 +398,23 @@
399399 'IBM_DB2Field' => 'includes/db/DatabaseIbm_db2.php',
400400
401401 # includes/diff
402 - 'ArrayDiffFormatter' => 'includes/diff/DifferenceEngine.php',
403 - '_DiffEngine' => 'includes/diff/DifferenceEngine.php',
404 - 'DifferenceEngine' => 'includes/diff/DifferenceInterface.php',
405 - 'DiffFormatter' => 'includes/diff/DifferenceEngine.php',
406 - 'Diff' => 'includes/diff/DifferenceEngine.php',
407 - '_DiffOp_Add' => 'includes/diff/DifferenceEngine.php',
408 - '_DiffOp_Change' => 'includes/diff/DifferenceEngine.php',
409 - '_DiffOp_Copy' => 'includes/diff/DifferenceEngine.php',
410 - '_DiffOp_Delete' => 'includes/diff/DifferenceEngine.php',
411 - '_DiffOp' => 'includes/diff/DifferenceEngine.php',
412 - '_HWLDF_WordAccumulator' => 'includes/diff/DifferenceEngine.php',
413 - 'MappedDiff' => 'includes/diff/DifferenceEngine.php',
414 - 'RangeDifference' => 'includes/diff/Diff.php',
415 - 'TableDiffFormatter' => 'includes/diff/DifferenceEngine.php',
416 - 'UnifiedDiffFormatter' => 'includes/diff/DifferenceEngine.php',
417 - 'WikiDiff3' => 'includes/diff/Diff.php',
418 - 'WordLevelDiff' => 'includes/diff/DifferenceEngine.php',
 402+ 'ArrayDiffFormatter' => 'includes/diff/WikiDiff.php',
 403+ '_DiffEngine' => 'includes/diff/WikiDiff.php',
 404+ 'DifferenceEngine' => 'includes/diff/DifferenceEngine.php',
 405+ 'DiffFormatter' => 'includes/diff/WikiDiff.php',
 406+ 'Diff' => 'includes/diff/WikiDiff.php',
 407+ '_DiffOp_Add' => 'includes/diff/WikiDiff.php',
 408+ '_DiffOp_Change' => 'includes/diff/WikiDiff.php',
 409+ '_DiffOp_Copy' => 'includes/diff/WikiDiff.php',
 410+ '_DiffOp_Delete' => 'includes/diff/WikiDiff.php',
 411+ '_DiffOp' => 'includes/diff/WikiDiff.php',
 412+ '_HWLDF_WordAccumulator' => 'includes/diff/WikiDiff.php',
 413+ 'MappedDiff' => 'includes/diff/WikiDiff.php',
 414+ 'RangeDifference' => 'includes/diff/WikiDiff3.php',
 415+ 'TableDiffFormatter' => 'includes/diff/WikiDiff.php',
 416+ 'UnifiedDiffFormatter' => 'includes/diff/WikiDiff.php',
 417+ 'WikiDiff3' => 'includes/diff/WikiDiff3.php',
 418+ 'WordLevelDiff' => 'includes/diff/WikiDiff.php',
419419
420420 # includes/filerepo
421421 'ArchivedFile' => 'includes/filerepo/ArchivedFile.php',
Index: trunk/phase3/includes/diff/Diff.php
——@@ -1,586 +0,0 @@
2 -<?php
3 -/**
4 - * New version of the difference engine
5 - *
6 - * Copyright © 2008 Guy Van den Broeck <guy@guyvdb.eu>
7 - *
8 - * This program is free software; you can redistribute it and/or modify
9 - * it under the terms of the GNU General Public License as published by
10 - * the Free Software Foundation; either version 2 of the License, or
11 - * (at your option) any later version.
12 - *
13 - * This program is distributed in the hope that it will be useful,
14 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 - * GNU General Public License for more details.
17 - *
18 - * You should have received a copy of the GNU General Public License
19 - * along with this program; if not, write to the Free Software
20 - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 - * http://www.gnu.org/copyleft/gpl.html
22 - *
23 - * @file
24 - * @ingroup DifferenceEngine
25 - */
26 -
27 -/**
28 - * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
29 - * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
30 - * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
31 - * "An O(NP) Sequence Comparison Algorithm").
32 - *
33 - * This implementation supports an upper bound on the excution time.
34 - *
35 - * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
36 - *
37 - * @author Guy Van den Broeck
38 - * @ingroup DifferenceEngine
39 - */
40 -class WikiDiff3 {
41 -
42 - //Input variables
43 - private $from;
44 - private $to;
45 - private $m;
46 - private $n;
47 -
48 - private $tooLong;
49 - private $powLimit;
50 -
51 - //State variables
52 - private $maxDifferences;
53 - private $lcsLengthCorrectedForHeuristic = false;
54 -
55 - //Output variables
56 - public $length;
57 - public $removed;
58 - public $added;
59 - public $heuristicUsed;
60 -
61 - function __construct($tooLong = 2000000, $powLimit = 1.45){
62 - $this->tooLong = $tooLong;
63 - $this->powLimit = $powLimit;
64 - }
65 -
66 - public function diff(/*array*/ $from, /*array*/ $to){
67 - //remember initial lengths
68 - $m = sizeof($from);
69 - $n = count($to);
70 -
71 - $this->heuristicUsed = false;
72 -
73 - //output
74 - $removed = $m > 0 ? array_fill(0, $m, true) : array();
75 - $added = $n > 0 ? array_fill(0, $n, true) : array();
76 -
77 - //reduce the complexity for the next step (intentionally done twice)
78 - //remove common tokens at the start
79 - $i = 0;
80 - while($i < $m && $i < $n && $from[$i] === $to[$i]) {
81 - $removed[$i] = $added[$i] = false;
82 - unset($from[$i], $to[$i]);
83 - ++$i;
84 - }
85 -
86 - //remove common tokens at the end
87 - $j = 1;
88 - while($i + $j <= $m && $i + $j <= $n && $from[$m - $j] === $to[$n - $j]) {
89 - $removed[$m - $j] = $added[$n - $j] = false;
90 - unset($from[$m - $j], $to[$n - $j]);
91 - ++$j;
92 - }
93 -
94 - $this->from = $newFromIndex = $this->to = $newToIndex = array();
95 -
96 - //remove tokens not in both sequences
97 - $shared = array();
98 - foreach( $from as $key ) {
99 - $shared[$key] = false;
100 - }
101 -
102 - foreach($to as $index => &$el) {
103 - if(array_key_exists($el, $shared)) {
104 - //keep it
105 - $this->to[] = $el;
106 - $shared[$el] = true;
107 - $newToIndex[] = $index;
108 - }
109 - }
110 - foreach($from as $index => &$el) {
111 - if($shared[$el]) {
112 - //keep it
113 - $this->from[] = $el;
114 - $newFromIndex[] = $index;
115 - }
116 - }
117 -
118 - unset($shared, $from, $to);
119 -
120 - $this->m = count($this->from);
121 - $this->n = count($this->to);
122 -
123 - $this->removed = $this->m > 0 ? array_fill(0, $this->m, true) : array();
124 - $this->added = $this->n > 0 ? array_fill(0, $this->n, true) : array();
125 -
126 - if ($this->m == 0 || $this->n == 0) {
127 - $this->length = 0;
128 - } else {
129 - $this->maxDifferences = ceil(($this->m + $this->n) / 2.0);
130 - if ($this->m * $this->n > $this->tooLong) {
131 - // limit complexity to D^POW_LIMIT for long sequences
132 - $this->maxDifferences = floor(pow($this->maxDifferences, $this->powLimit - 1.0));
133 - wfDebug("Limiting max number of differences to $this->maxDifferences\n");
134 - }
135 -
136 - /*
137 - * The common prefixes and suffixes are always part of some LCS, include
138 - * them now to reduce our search space
139 - */
140 - $max = min($this->m, $this->n);
141 - for ($forwardBound = 0; $forwardBound < $max
142 - && $this->from[$forwardBound] === $this->to[$forwardBound];
143 - ++$forwardBound) {
144 - $this->removed[$forwardBound] = $this->added[$forwardBound] = false;
145 - }
146 -
147 - $backBoundL1 = $this->m - 1;
148 - $backBoundL2 = $this->n - 1;
149 -
150 - while ($backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
151 - && $this->from[$backBoundL1] === $this->to[$backBoundL2]) {
152 - $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
153 - }
154 -
155 - $temp = array_fill(0, $this->m + $this->n + 1, 0);
156 - $V = array($temp, $temp);
157 - $snake = array(0, 0, 0);
158 -
159 - $this->length = $forwardBound + $this->m - $backBoundL1 - 1
160 - + $this->lcs_rec($forwardBound, $backBoundL1,
161 - $forwardBound, $backBoundL2, $V, $snake);
162 - }
163 -
164 - $this->m = $m;
165 - $this->n = $n;
166 -
167 - $this->length += $i + $j - 1;
168 -
169 - foreach($this->removed as $key => &$removed_elem) {
170 - if(!$removed_elem) {
171 - $removed[$newFromIndex[$key]] = false;
172 - }
173 - }
174 - foreach($this->added as $key => &$added_elem) {
175 - if(!$added_elem) {
176 - $added[$newToIndex[$key]] = false;
177 - }
178 - }
179 - $this->removed = $removed;
180 - $this->added = $added;
181 - }
182 -
183 - function diff_range($from_lines, $to_lines) {
184 - // Diff and store locally
185 - $this->diff($from_lines, $to_lines);
186 - unset($from_lines, $to_lines);
187 -
188 - $ranges = array();
189 - $xi = $yi = 0;
190 - while ($xi < $this->m || $yi < $this->n) {
191 - // Matching "snake".
192 - while ($xi < $this->m && $yi < $this->n
193 - && !$this->removed[$xi]
194 - && !$this->added[$yi]) {
195 - ++$xi;
196 - ++$yi;
197 - }
198 - // Find deletes & adds.
199 - $xstart = $xi;
200 - while ($xi < $this->m && $this->removed[$xi]) {
201 - ++$xi;
202 - }
203 -
204 - $ystart = $yi;
205 - while ($yi < $this->n && $this->added[$yi]) {
206 - ++$yi;
207 - }
208 -
209 - if ($xi > $xstart || $yi > $ystart) {
210 - $ranges[] = new RangeDifference($xstart, $xi,
211 - $ystart, $yi);
212 - }
213 - }
214 - return $ranges;
215 - }
216 -
217 - private function lcs_rec($bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake) {
218 - // check that both sequences are non-empty
219 - if ($bottoml1 > $topl1 || $bottoml2 > $topl2) {
220 - return 0;
221 - }
222 -
223 - $d = $this->find_middle_snake($bottoml1, $topl1, $bottoml2,
224 - $topl2, $V, $snake);
225 -
226 - // need to store these so we don't lose them when they're
227 - // overwritten by the recursion
228 - $len = $snake[2];
229 - $startx = $snake[0];
230 - $starty = $snake[1];
231 -
232 - // the middle snake is part of the LCS, store it
233 - for ($i = 0; $i < $len; ++$i) {
234 - $this->removed[$startx + $i] = $this->added[$starty + $i] = false;
235 - }
236 -
237 - if ($d > 1) {
238 - return $len
239 - + $this->lcs_rec($bottoml1, $startx - 1, $bottoml2,
240 - $starty - 1, $V, $snake)
241 - + $this->lcs_rec($startx + $len, $topl1, $starty + $len,
242 - $topl2, $V, $snake);
243 - } else if ($d == 1) {
244 - /*
245 - * In this case the sequences differ by exactly 1 line. We have
246 - * already saved all the lines after the difference in the for loop
247 - * above, now we need to save all the lines before the difference.
248 - */
249 - $max = min($startx - $bottoml1, $starty - $bottoml2);
250 - for ($i = 0; $i < $max; ++$i) {
251 - $this->removed[$bottoml1 + $i] =
252 - $this->added[$bottoml2 + $i] = false;
253 - }
254 - return $max + $len;
255 - }
256 - return $len;
257 - }
258 -
259 - private function find_middle_snake($bottoml1, $topl1, $bottoml2,$topl2, &$V, &$snake) {
260 - $from = &$this->from;
261 - $to = &$this->to;
262 - $V0 = &$V[0];
263 - $V1 = &$V[1];
264 - $snake0 = &$snake[0];
265 - $snake1 = &$snake[1];
266 - $snake2 = &$snake[2];
267 - $bottoml1_min_1 = $bottoml1-1;
268 - $bottoml2_min_1 = $bottoml2-1;
269 - $N = $topl1 - $bottoml1_min_1;
270 - $M = $topl2 - $bottoml2_min_1;
271 - $delta = $N - $M;
272 - $maxabsx = $N+$bottoml1;
273 - $maxabsy = $M+$bottoml2;
274 - $limit = min($this->maxDifferences, ceil(($N + $M ) / 2));
275 -
276 - //value_to_add_forward: a 0 or 1 that we add to the start
277 - // offset to make it odd/even
278 - if (($M & 1) == 1) {
279 - $value_to_add_forward = 1;
280 - } else {
281 - $value_to_add_forward = 0;
282 - }
283 -
284 - if (($N & 1) == 1) {
285 - $value_to_add_backward = 1;
286 - } else {
287 - $value_to_add_backward = 0;
288 - }
289 -
290 - $start_forward = -$M;
291 - $end_forward = $N;
292 - $start_backward = -$N;
293 - $end_backward = $M;
294 -
295 - $limit_min_1 = $limit - 1;
296 - $limit_plus_1 = $limit + 1;
297 -
298 - $V0[$limit_plus_1] = 0;
299 - $V1[$limit_min_1] = $N;
300 - $limit = min($this->maxDifferences, ceil(($N + $M ) / 2));
301 -
302 - if (($delta & 1) == 1) {
303 - for ($d = 0; $d <= $limit; ++$d) {
304 - $start_diag = max($value_to_add_forward + $start_forward, -$d);
305 - $end_diag = min($end_forward, $d);
306 - $value_to_add_forward = 1 - $value_to_add_forward;
307 -
308 - // compute forward furthest reaching paths
309 - for ($k = $start_diag; $k <= $end_diag; $k += 2) {
310 - if ($k == -$d || ($k < $d
311 - && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k])) {
312 - $x = $V0[$limit_plus_1 + $k];
313 - } else {
314 - $x = $V0[$limit_min_1 + $k] + 1;
315 - }
316 -
317 - $absx = $snake0 = $x + $bottoml1;
318 - $absy = $snake1 = $x - $k + $bottoml2;
319 -
320 - while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
321 - ++$absx;
322 - ++$absy;
323 - }
324 - $x = $absx-$bottoml1;
325 -
326 - $snake2 = $absx -$snake0;
327 - $V0[$limit + $k] = $x;
328 - if ($k >= $delta - $d + 1 && $k <= $delta + $d - 1
329 - && $x >= $V1[$limit + $k - $delta]) {
330 - return 2 * $d - 1;
331 - }
332 -
333 - // check to see if we can cut down the diagonal range
334 - if ($x >= $N && $end_forward > $k - 1) {
335 - $end_forward = $k - 1;
336 - } else if ($absy - $bottoml2 >= $M) {
337 - $start_forward = $k + 1;
338 - $value_to_add_forward = 0;
339 - }
340 - }
341 -
342 - $start_diag = max($value_to_add_backward + $start_backward, -$d);
343 - $end_diag = min($end_backward, $d);
344 - $value_to_add_backward = 1 - $value_to_add_backward;
345 -
346 - // compute backward furthest reaching paths
347 - for ($k = $start_diag; $k <= $end_diag; $k += 2) {
348 - if ($k == $d
349 - || ($k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k])) {
350 - $x = $V1[$limit_min_1 + $k];
351 - } else {
352 - $x = $V1[$limit_plus_1 + $k] - 1;
353 - }
354 -
355 - $y = $x - $k - $delta;
356 -
357 - $snake2 = 0;
358 - while ($x > 0 && $y > 0
359 - && $from[$x +$bottoml1_min_1] === $to[$y + $bottoml2_min_1]) {
360 - --$x;
361 - --$y;
362 - ++$snake2;
363 - }
364 - $V1[$limit + $k] = $x;
365 -
366 - // check to see if we can cut down our diagonal range
367 - if ($x <= 0) {
368 - $start_backward = $k + 1;
369 - $value_to_add_backward = 0;
370 - } else if ($y <= 0 && $end_backward > $k - 1) {
371 - $end_backward = $k - 1;
372 - }
373 - }
374 - }
375 - } else {
376 - for ($d = 0; $d <= $limit; ++$d) {
377 - $start_diag = max($value_to_add_forward + $start_forward, -$d);
378 - $end_diag = min($end_forward, $d);
379 - $value_to_add_forward = 1 - $value_to_add_forward;
380 -
381 - // compute forward furthest reaching paths
382 - for ($k = $start_diag; $k <= $end_diag; $k += 2) {
383 - if ($k == -$d
384 - || ($k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k])) {
385 - $x = $V0[$limit_plus_1 + $k];
386 - } else {
387 - $x = $V0[$limit_min_1 + $k] + 1;
388 - }
389 -
390 - $absx = $snake0 = $x + $bottoml1;
391 - $absy = $snake1 = $x - $k + $bottoml2;
392 -
393 - while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
394 - ++$absx;
395 - ++$absy;
396 - }
397 - $x = $absx-$bottoml1;
398 - $snake2 = $absx -$snake0;
399 - $V0[$limit + $k] = $x;
400 -
401 - // check to see if we can cut down the diagonal range
402 - if ($x >= $N && $end_forward > $k - 1) {
403 - $end_forward = $k - 1;
404 - } else if ($absy-$bottoml2 >= $M) {
405 - $start_forward = $k + 1;
406 - $value_to_add_forward = 0;
407 - }
408 - }
409 -
410 - $start_diag = max($value_to_add_backward + $start_backward, -$d);
411 - $end_diag = min($end_backward, $d);
412 - $value_to_add_backward = 1 - $value_to_add_backward;
413 -
414 - // compute backward furthest reaching paths
415 - for ($k = $start_diag; $k <= $end_diag; $k += 2) {
416 - if ($k == $d
417 - || ($k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k])) {
418 - $x = $V1[$limit_min_1 + $k];
419 - } else {
420 - $x = $V1[$limit_plus_1 + $k] - 1;
421 - }
422 -
423 - $y = $x - $k - $delta;
424 -
425 - $snake2 = 0;
426 - while ($x > 0 && $y > 0
427 - && $from[$x +$bottoml1_min_1] === $to[$y + $bottoml2_min_1]) {
428 - --$x;
429 - --$y;
430 - ++$snake2;
431 - }
432 - $V1[$limit + $k] = $x;
433 -
434 - if ($k >= -$delta - $d && $k <= $d - $delta
435 - && $x <= $V0[$limit + $k + $delta]) {
436 - $snake0 = $bottoml1 + $x;
437 - $snake1 = $bottoml2 + $y;
438 - return 2 * $d;
439 - }
440 -
441 - // check to see if we can cut down our diagonal range
442 - if ($x <= 0) {
443 - $start_backward = $k + 1;
444 - $value_to_add_backward = 0;
445 - } else if ($y <= 0 && $end_backward > $k - 1) {
446 - $end_backward = $k - 1;
447 - }
448 - }
449 - }
450 - }
451 - /*
452 - * computing the true LCS is too expensive, instead find the diagonal
453 - * with the most progress and pretend a midle snake of length 0 occurs
454 - * there.
455 - */
456 -
457 - $most_progress = self::findMostProgress($M, $N, $limit, $V);
458 -
459 - $snake0 = $bottoml1 + $most_progress[0];
460 - $snake1 = $bottoml2 + $most_progress[1];
461 - $snake2 = 0;
462 - wfDebug("Computing the LCS is too expensive. Using a heuristic.\n");
463 - $this->heuristicUsed = true;
464 - return 5; /*
465 - * HACK: since we didn't really finish the LCS computation
466 - * we don't really know the length of the SES. We don't do
467 - * anything with the result anyway, unless it's <=1. We know
468 - * for a fact SES > 1 so 5 is as good a number as any to
469 - * return here
470 - */
471 - }
472 -
473 - private static function findMostProgress($M, $N, $limit, $V) {
474 - $delta = $N - $M;
475 -
476 - if (($M & 1) == ($limit & 1)) {
477 - $forward_start_diag = max(-$M, -$limit);
478 - } else {
479 - $forward_start_diag = max(1 - $M, -$limit);
480 - }
481 -
482 - $forward_end_diag = min($N, $limit);
483 -
484 - if (($N & 1) == ($limit & 1)) {
485 - $backward_start_diag = max(-$N, -$limit);
486 - } else {
487 - $backward_start_diag = max(1 - $N, -$limit);
488 - }
489 -
490 - $backward_end_diag = -min($M, $limit);
491 -
492 - $temp = array(0, 0, 0);
493 -
494 -
495 - $max_progress = array_fill(0, ceil(max($forward_end_diag - $forward_start_diag,
496 - $backward_end_diag - $backward_start_diag) / 2), $temp);
497 - $num_progress = 0; // the 1st entry is current, it is initialized
498 - // with 0s
499 -
500 - // first search the forward diagonals
501 - for ($k = $forward_start_diag; $k <= $forward_end_diag; $k += 2) {
502 - $x = $V[0][$limit + $k];
503 - $y = $x - $k;
504 - if ($x > $N || $y > $M) {
505 - continue;
506 - }
507 -
508 - $progress = $x + $y;
509 - if ($progress > $max_progress[0][2]) {
510 - $num_progress = 0;
511 - $max_progress[0][0] = $x;
512 - $max_progress[0][1] = $y;
513 - $max_progress[0][2] = $progress;
514 - } else if ($progress == $max_progress[0][2]) {
515 - ++$num_progress;
516 - $max_progress[$num_progress][0] = $x;
517 - $max_progress[$num_progress][1] = $y;
518 - $max_progress[$num_progress][2] = $progress;
519 - }
520 - }
521 -
522 - $max_progress_forward = true; // initially the maximum
523 - // progress is in the forward
524 - // direction
525 -
526 - // now search the backward diagonals
527 - for ($k = $backward_start_diag; $k <= $backward_end_diag; $k += 2) {
528 - $x = $V[1][$limit + $k];
529 - $y = $x - $k - $delta;
530 - if ($x < 0 || $y < 0) {
531 - continue;
532 - }
533 -
534 - $progress = $N - $x + $M - $y;
535 - if ($progress > $max_progress[0][2]) {
536 - $num_progress = 0;
537 - $max_progress_forward = false;
538 - $max_progress[0][0] = $x;
539 - $max_progress[0][1] = $y;
540 - $max_progress[0][2] = $progress;
541 - } else if ($progress == $max_progress[0][2] && !$max_progress_forward) {
542 - ++$num_progress;
543 - $max_progress[$num_progress][0] = $x;
544 - $max_progress[$num_progress][1] = $y;
545 - $max_progress[$num_progress][2] = $progress;
546 - }
547 - }
548 -
549 - // return the middle diagonal with maximal progress.
550 - return $max_progress[floor($num_progress / 2)];
551 - }
552 -
553 - public function getLcsLength(){
554 - if($this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic){
555 - $this->lcsLengthCorrectedForHeuristic = true;
556 - $this->length = $this->m-array_sum($this->added);
557 - }
558 - return $this->length;
559 - }
560 -
561 -}
562 -
563 -/**
564 - * Alternative representation of a set of changes, by the index
565 - * ranges that are changed.
566 - *
567 - * @ingroup DifferenceEngine
568 - */
569 -class RangeDifference {
570 -
571 - public $leftstart;
572 - public $leftend;
573 - public $leftlength;
574 -
575 - public $rightstart;
576 - public $rightend;
577 - public $rightlength;
578 -
579 - function __construct($leftstart, $leftend, $rightstart, $rightend){
580 - $this->leftstart = $leftstart;
581 - $this->leftend = $leftend;
582 - $this->leftlength = $leftend - $leftstart;
583 - $this->rightstart = $rightstart;
584 - $this->rightend = $rightend;
585 - $this->rightlength = $rightend - $rightstart;
586 - }
587 -}
Index: trunk/phase3/includes/diff/DifferenceInterface.php
——@@ -1,1072 +0,0 @@
2 -<?php
3 -/**
4 - * User interface for the difference engine
5 - *
6 - * @file
7 - * @ingroup DifferenceEngine
8 - */
9 -
10 -/**
11 - * Constant to indicate diff cache compatibility.
12 - * Bump this when changing the diff formatting in a way that
13 - * fixes important bugs or such to force cached diff views to
14 - * clear.
15 - */
16 -define( 'MW_DIFF_VERSION', '1.11a' );
17 -
18 -/**
19 - * @todo document
20 - * @ingroup DifferenceEngine
21 - */
22 -class DifferenceEngine {
23 - /**#@+
24 - * @private
25 - */
26 - var $mOldid, $mNewid, $mTitle;
27 - var $mOldtitle, $mNewtitle, $mPagetitle;
28 - var $mOldtext, $mNewtext;
29 - var $mOldPage, $mNewPage;
30 - var $mRcidMarkPatrolled;
31 - var $mOldRev, $mNewRev;
32 - var $mRevisionsLoaded = false; // Have the revisions been loaded
33 - var $mTextLoaded = 0; // How many text blobs have been loaded, 0, 1 or 2?
34 - var $mCacheHit = false; // Was the diff fetched from cache?
35 -
36 - /**
37 - * Set this to true to add debug info to the HTML output.
38 - * Warning: this may cause RSS readers to spuriously mark articles as "new"
39 - * (bug 20601)
40 - */
41 - var $enableDebugComment = false;
42 -
43 - // If true, line X is not displayed when X is 1, for example to increase
44 - // readability and conserve space with many small diffs.
45 - protected $mReducedLineNumbers = false;
46 -
47 - protected $unhide = false; # show rev_deleted content if allowed
48 - /**#@-*/
49 -
50 - /**
51 - * Constructor
52 - * @param $titleObj Title object that the diff is associated with
53 - * @param $old Integer: old ID we want to show and diff with.
54 - * @param $new String: either 'prev' or 'next'.
55 - * @param $rcid Integer: ??? FIXME (default 0)
56 - * @param $refreshCache boolean If set, refreshes the diff cache
57 - * @param $unhide boolean If set, allow viewing deleted revs
58 - */
59 - function __construct( $titleObj = null, $old = 0, $new = 0, $rcid = 0,
60 - $refreshCache = false, $unhide = false )
61 - {
62 - if ( $titleObj ) {
63 - $this->mTitle = $titleObj;
64 - } else {
65 - global $wgTitle;
66 - $this->mTitle = $wgTitle;
67 - }
68 - wfDebug("DifferenceEngine old '$old' new '$new' rcid '$rcid'\n");
69 -
70 - if ( 'prev' === $new ) {
71 - # Show diff between revision $old and the previous one.
72 - # Get previous one from DB.
73 - $this->mNewid = intval($old);
74 - $this->mOldid = $this->mTitle->getPreviousRevisionID( $this->mNewid );
75 - } elseif ( 'next' === $new ) {
76 - # Show diff between revision $old and the next one.
77 - # Get next one from DB.
78 - $this->mOldid = intval($old);
79 - $this->mNewid = $this->mTitle->getNextRevisionID( $this->mOldid );
80 - if ( false === $this->mNewid ) {
81 - # if no result, NewId points to the newest old revision. The only newer
82 - # revision is cur, which is "0".
83 - $this->mNewid = 0;
84 - }
85 - } else {
86 - $this->mOldid = intval($old);
87 - $this->mNewid = intval($new);
88 - wfRunHooks( 'NewDifferenceEngine', array(&$titleObj, &$this->mOldid, &$this->mNewid, $old, $new) );
89 - }
90 - $this->mRcidMarkPatrolled = intval($rcid); # force it to be an integer
91 - $this->mRefreshCache = $refreshCache;
92 - $this->unhide = $unhide;
93 - }
94 -
95 - function setReducedLineNumbers( $value = true ) {
96 - $this->mReducedLineNumbers = $value;
97 - }
98 -
99 - function getTitle() {
100 - return $this->mTitle;
101 - }
102 -
103 - function wasCacheHit() {
104 - return $this->mCacheHit;
105 - }
106 -
107 - function getOldid() {
108 - return $this->mOldid;
109 - }
110 -
111 - function getNewid() {
112 - return $this->mNewid;
113 - }
114 -
115 - function showDiffPage( $diffOnly = false ) {
116 - global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol;
117 - wfProfileIn( __METHOD__ );
118 -
119 -
120 - # If external diffs are enabled both globally and for the user,
121 - # we'll use the application/x-external-editor interface to call
122 - # an external diff tool like kompare, kdiff3, etc.
123 - if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) {
124 - global $wgInputEncoding,$wgServer,$wgScript,$wgLang;
125 - $wgOut->disable();
126 - header ( "Content-type: application/x-external-editor; charset=".$wgInputEncoding );
127 - $url1=$this->mTitle->getFullURL( array(
128 - 'action' => 'raw',
129 - 'oldid' => $this->mOldid
130 - ) );
131 - $url2=$this->mTitle->getFullURL( array(
132 - 'action' => 'raw',
133 - 'oldid' => $this->mNewid
134 - ) );
135 - $special=$wgLang->getNsText(NS_SPECIAL);
136 - $control=<<<CONTROL
137 - [Process]
138 - Type=Diff text
139 - Engine=MediaWiki
140 - Script={$wgServer}{$wgScript}
141 - Special namespace={$special}
142 -
143 - [File]
144 - Extension=wiki
145 - URL=$url1
146 -
147 - [File 2]
148 - Extension=wiki
149 - URL=$url2
150 -CONTROL;
151 - echo($control);
152 - return;
153 - }
154 -
155 - $wgOut->setArticleFlag( false );
156 - if ( !$this->loadRevisionData() ) {
157 - $t = $this->mTitle->getPrefixedText();
158 - $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
159 - $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
160 - $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
161 - wfProfileOut( __METHOD__ );
162 - return;
163 - }
164 -
165 - wfRunHooks( 'DiffViewHeader', array( $this, $this->mOldRev, $this->mNewRev ) );
166 -
167 - if ( $this->mNewRev->isCurrent() ) {
168 - $wgOut->setArticleFlag( true );
169 - }
170 -
171 - # mOldid is false if the difference engine is called with a "vague" query for
172 - # a diff between a version V and its previous version V' AND the version V
173 - # is the first version of that article. In that case, V' does not exist.
174 - if ( $this->mOldid === false ) {
175 - $this->showFirstRevision();
176 - $this->renderNewRevision(); // should we respect $diffOnly here or not?
177 - wfProfileOut( __METHOD__ );
178 - return;
179 - }
180 -
181 - $wgOut->suppressQuickbar();
182 -
183 - $oldTitle = $this->mOldPage->getPrefixedText();
184 - $newTitle = $this->mNewPage->getPrefixedText();
185 - if( $oldTitle == $newTitle ) {
186 - $wgOut->setPageTitle( $newTitle );
187 - } else {
188 - $wgOut->setPageTitle( $oldTitle . ', ' . $newTitle );
189 - }
190 - if ( $this->mNewPage->equals( $this->mOldPage ) ) {
191 - $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
192 - } else {
193 - $wgOut->setSubtitle( wfMsgExt( 'difference-multipage', array( 'parseinline' ) ) );
194 - }
195 - $wgOut->setRobotPolicy( 'noindex,nofollow' );
196 -
197 - if ( !$this->mOldPage->userCanRead() || !$this->mNewPage->userCanRead() ) {
198 - $wgOut->loginToUse();
199 - $wgOut->output();
200 - $wgOut->disable();
201 - wfProfileOut( __METHOD__ );
202 - return;
203 - }
204 -
205 - $sk = $wgUser->getSkin();
206 -
207 - // Check if page is editable
208 - $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
209 - if ( $editable && $this->mNewRev->isCurrent() && $wgUser->isAllowed( 'rollback' ) ) {
210 - $rollback = '&#160;&#160;&#160;' . $sk->generateRollback( $this->mNewRev );
211 - } else {
212 - $rollback = '';
213 - }
214 -
215 - // Prepare a change patrol link, if applicable
216 - if( $wgUseRCPatrol && $this->mTitle->userCan('patrol') ) {
217 - // If we've been given an explicit change identifier, use it; saves time
218 - if( $this->mRcidMarkPatrolled ) {
219 - $rcid = $this->mRcidMarkPatrolled;
220 - $rc = RecentChange::newFromId( $rcid );
221 - // Already patrolled?
222 - $rcid = is_object($rc) && !$rc->getAttribute('rc_patrolled') ? $rcid : 0;
223 - } else {
224 - // Look for an unpatrolled change corresponding to this diff
225 - $db = wfGetDB( DB_SLAVE );
226 - $change = RecentChange::newFromConds(
227 - array(
228 - // Redundant user,timestamp condition so we can use the existing index
229 - 'rc_user_text' => $this->mNewRev->getRawUserText(),
230 - 'rc_timestamp' => $db->timestamp( $this->mNewRev->getTimestamp() ),
231 - 'rc_this_oldid' => $this->mNewid,
232 - 'rc_last_oldid' => $this->mOldid,
233 - 'rc_patrolled' => 0
234 - ),
235 - __METHOD__
236 - );
237 - if( $change instanceof RecentChange ) {
238 - $rcid = $change->mAttribs['rc_id'];
239 - $this->mRcidMarkPatrolled = $rcid;
240 - } else {
241 - // None found
242 - $rcid = 0;
243 - }
244 - }
245 - // Build the link
246 - if( $rcid ) {
247 - $token = $wgUser->editToken( $rcid );
248 - $patrol = ' <span class="patrollink">[' . $sk->link(
249 - $this->mTitle,
250 - wfMsgHtml( 'markaspatrolleddiff' ),
251 - array(),
252 - array(
253 - 'action' => 'markpatrolled',
254 - 'rcid' => $rcid,
255 - 'token' => $token,
256 - ),
257 - array(
258 - 'known',
259 - 'noclasses'
260 - )
261 - ) . ']</span>';
262 - } else {
263 - $patrol = '';
264 - }
265 - } else {
266 - $patrol = '';
267 - }
268 -
269 - # Carry over 'diffonly' param via navigation links
270 - if( $diffOnly != $wgUser->getBoolOption('diffonly') ) {
271 - $query['diffonly'] = $diffOnly;
272 - }
273 -
274 - # Make "previous revision link"
275 - $query['diff'] = 'prev';
276 - $query['oldid'] = $this->mOldid;
277 - # Cascade unhide param in links for easy deletion browsing
278 - if( $this->unhide ) {
279 - $query['unhide'] = 1;
280 - }
281 - if( !$this->mOldRev->getPrevious() ) {
282 - $prevlink = '&#160;';
283 - } else {
284 - $prevlink = $sk->link(
285 - $this->mTitle,
286 - wfMsgHtml( 'previousdiff' ),
287 - array(
288 - 'id' => 'differences-prevlink'
289 - ),
290 - $query,
291 - array(
292 - 'known',
293 - 'noclasses'
294 - )
295 - );
296 - }
297 -
298 - # Make "next revision link"
299 - $query['diff'] = 'next';
300 - $query['oldid'] = $this->mNewid;
301 - # Skip next link on the top revision
302 - if( $this->mNewRev->isCurrent() ) {
303 - $nextlink = '&#160;';
304 - } else {
305 - $nextlink = $sk->link(
306 - $this->mTitle,
307 - wfMsgHtml( 'nextdiff' ),
308 - array(
309 - 'id' => 'differences-nextlink'
310 - ),
311 - $query,
312 - array(
313 - 'known',
314 - 'noclasses'
315 - )
316 - );
317 - }
318 -
319 - $oldminor = '';
320 - $newminor = '';
321 -
322 - if( $this->mOldRev->isMinor() ) {
323 - $oldminor = ChangesList::flag( 'minor' );
324 - }
325 - if( $this->mNewRev->isMinor() ) {
326 - $newminor = ChangesList::flag( 'minor' );
327 - }
328 -
329 - # Handle RevisionDelete links...
330 - $ldel = $this->revisionDeleteLink( $this->mOldRev );
331 - $rdel = $this->revisionDeleteLink( $this->mNewRev );
332 -
333 - $oldHeader = '<div id="mw-diff-otitle1"><strong>'.$this->mOldtitle.'</strong></div>' .
334 - '<div id="mw-diff-otitle2">' .
335 - $sk->revUserTools( $this->mOldRev, !$this->unhide ).'</div>' .
336 - '<div id="mw-diff-otitle3">' . $oldminor .
337 - $sk->revComment( $this->mOldRev, !$diffOnly, !$this->unhide ).$ldel.'</div>' .
338 - '<div id="mw-diff-otitle4">' . $prevlink .'</div>';
339 - $newHeader = '<div id="mw-diff-ntitle1"><strong>'.$this->mNewtitle.'</strong></div>' .
340 - '<div id="mw-diff-ntitle2">' . $sk->revUserTools( $this->mNewRev, !$this->unhide ) .
341 - " $rollback</div>" .
342 - '<div id="mw-diff-ntitle3">' . $newminor .
343 - $sk->revComment( $this->mNewRev, !$diffOnly, !$this->unhide ).$rdel.'</div>' .
344 - '<div id="mw-diff-ntitle4">' . $nextlink . $patrol . '</div>';
345 -
346 - # Check if this user can see the revisions
347 - $allowed = $this->mOldRev->userCan(Revision::DELETED_TEXT)
348 - && $this->mNewRev->userCan(Revision::DELETED_TEXT);
349 - # Check if one of the revisions is deleted/suppressed
350 - $deleted = $suppressed = false;
351 - if( $this->mOldRev->isDeleted(Revision::DELETED_TEXT) ) {
352 - $deleted = true; // old revisions text is hidden
353 - if( $this->mOldRev->isDeleted(Revision::DELETED_RESTRICTED) )
354 - $suppressed = true; // also suppressed
355 - }
356 - if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
357 - $deleted = true; // new revisions text is hidden
358 - if( $this->mNewRev->isDeleted(Revision::DELETED_RESTRICTED) )
359 - $suppressed = true; // also suppressed
360 - }
361 - # If the diff cannot be shown due to a deleted revision, then output
362 - # the diff header and links to unhide (if available)...
363 - if( $deleted && (!$this->unhide || !$allowed) ) {
364 - $this->showDiffStyle();
365 - $multi = $this->getMultiNotice();
366 - $wgOut->addHTML( $this->addHeader( '', $oldHeader, $newHeader, $multi ) );
367 - if( !$allowed ) {
368 - $msg = $suppressed ? 'rev-suppressed-no-diff' : 'rev-deleted-no-diff';
369 - # Give explanation for why revision is not visible
370 - $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n",
371 - array( $msg ) );
372 - } else {
373 - # Give explanation and add a link to view the diff...
374 - $link = $this->mTitle->getFullUrl( array(
375 - 'diff' => $this->mNewid,
376 - 'oldid' => $this->mOldid,
377 - 'unhide' => 1
378 - ) );
379 - $msg = $suppressed ? 'rev-suppressed-unhide-diff' : 'rev-deleted-unhide-diff';
380 - $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", array( $msg, $link ) );
381 - }
382 - # Otherwise, output a regular diff...
383 - } else {
384 - # Add deletion notice if the user is viewing deleted content
385 - $notice = '';
386 - if( $deleted ) {
387 - $msg = $suppressed ? 'rev-suppressed-diff-view' : 'rev-deleted-diff-view';
388 - $notice = "<div class='mw-warning plainlinks'>\n".wfMsgExt($msg,'parseinline')."</div>\n";
389 - }
390 - $this->showDiff( $oldHeader, $newHeader, $notice );
391 - if( !$diffOnly ) {
392 - $this->renderNewRevision();
393 - }
394 - }
395 - wfProfileOut( __METHOD__ );
396 - }
397 -
398 - protected function revisionDeleteLink( $rev ) {
399 - global $wgUser;
400 - $link = '';
401 - $canHide = $wgUser->isAllowed( 'deleterevision' );
402 - // Show del/undel link if:
403 - // (a) the user can delete revisions, or
404 - // (b) the user can view deleted revision *and* this one is deleted
405 - if( $canHide || ($rev->getVisibility() && $wgUser->isAllowed( 'deletedhistory' )) ) {
406 - $sk = $wgUser->getSkin();
407 - if( !$rev->userCan( Revision::DELETED_RESTRICTED ) ) {
408 - $link = $sk->revDeleteLinkDisabled( $canHide ); // revision was hidden from sysops
409 - } else {
410 - $query = array(
411 - 'type' => 'revision',
412 - 'target' => $rev->mTitle->getPrefixedDbkey(),
413 - 'ids' => $rev->getId()
414 - );
415 - $link = $sk->revDeleteLink( $query,
416 - $rev->isDeleted( Revision::DELETED_RESTRICTED ), $canHide );
417 - }
418 - $link = '&#160;&#160;&#160;' . $link . ' ';
419 - }
420 - return $link;
421 - }
422 -
423 - /**
424 - * Show the new revision of the page.
425 - */
426 - function renderNewRevision() {
427 - global $wgOut, $wgUser;
428 - wfProfileIn( __METHOD__ );
429 -
430 - $wgOut->addHTML( "<hr /><h2>{$this->mPagetitle}</h2>\n" );
431 - # Add deleted rev tag if needed
432 - if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
433 - $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", 'rev-deleted-text-permission' );
434 - } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
435 - $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", 'rev-deleted-text-view' );
436 - }
437 -
438 - $pCache = true;
439 - if( !$this->mNewRev->isCurrent() ) {
440 - $oldEditSectionSetting = $wgOut->parserOptions()->setEditSection( false );
441 - $pCache = false;
442 - }
443 -
444 - $this->loadNewText();
445 - if( is_object( $this->mNewRev ) ) {
446 - $wgOut->setRevisionId( $this->mNewRev->getId() );
447 - }
448 -
449 - if( $this->mTitle->isCssJsSubpage() || $this->mTitle->isCssOrJsPage() ) {
450 - // Stolen from Article::view --AG 2007-10-11
451 - // Give hooks a chance to customise the output
452 - if( wfRunHooks( 'ShowRawCssJs', array( $this->mNewtext, $this->mTitle, $wgOut ) ) ) {
453 - // Wrap the whole lot in a <pre> and don't parse
454 - $m = array();
455 - preg_match( '!\.(css|js)$!u', $this->mTitle->getText(), $m );
456 - $wgOut->addHTML( "<pre class=\"mw-code mw-{$m[1]}\" dir=\"ltr\">\n" );
457 - $wgOut->addHTML( htmlspecialchars( $this->mNewtext ) );
458 - $wgOut->addHTML( "\n</pre>\n" );
459 - }
460 - } elseif( wfRunHooks( 'ArticleContentOnDiff', array( $this, $wgOut ) ) ) {
461 - if ( $pCache ) {
462 - $article = new Article( $this->mTitle, 0 );
463 - $pOutput = ParserCache::singleton()->get( $article, $wgOut->parserOptions() );
464 - if( $pOutput ) {
465 - $wgOut->addParserOutput( $pOutput );
466 - } else {
467 - $article->doViewParse();
468 - }
469 - } else {
470 - $wgOut->addWikiTextTidy( $this->mNewtext );
471 - }
472 - }
473 -
474 - if( is_object( $this->mNewRev ) && !$this->mNewRev->isCurrent() ) {
475 - $wgOut->parserOptions()->setEditSection( $oldEditSectionSetting );
476 - }
477 -
478 - # Add redundant patrol link on bottom...
479 - if( $this->mRcidMarkPatrolled && $this->mTitle->quickUserCan('patrol') ) {
480 - $sk = $wgUser->getSkin();
481 - $token = $wgUser->editToken( $this->mRcidMarkPatrolled );
482 - $wgOut->addHTML(
483 - "<div class='patrollink'>[" . $sk->link(
484 - $this->mTitle,
485 - wfMsgHtml( 'markaspatrolleddiff' ),
486 - array(),
487 - array(
488 - 'action' => 'markpatrolled',
489 - 'rcid' => $this->mRcidMarkPatrolled,
490 - 'token' => $token,
491 - )
492 - ) . ']</div>'
493 - );
494 - }
495 -
496 - wfProfileOut( __METHOD__ );
497 - }
498 -
499 - /**
500 - * Show the first revision of an article. Uses normal diff headers in
501 - * contrast to normal "old revision" display style.
502 - */
503 - function showFirstRevision() {
504 - global $wgOut, $wgUser;
505 - wfProfileIn( __METHOD__ );
506 -
507 - # Get article text from the DB
508 - #
509 - if ( ! $this->loadNewText() ) {
510 - $t = $this->mTitle->getPrefixedText();
511 - $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
512 - $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
513 - $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
514 - wfProfileOut( __METHOD__ );
515 - return;
516 - }
517 - if ( $this->mNewRev->isCurrent() ) {
518 - $wgOut->setArticleFlag( true );
519 - }
520 -
521 - # Check if user is allowed to look at this page. If not, bail out.
522 - #
523 - if ( !$this->mTitle->userCanRead() ) {
524 - $wgOut->loginToUse();
525 - $wgOut->output();
526 - wfProfileOut( __METHOD__ );
527 - throw new MWException("Permission Error: you do not have access to view this page");
528 - }
529 -
530 - # Prepare the header box
531 - #
532 - $sk = $wgUser->getSkin();
533 -
534 - $next = $this->mTitle->getNextRevisionID( $this->mNewid );
535 - if( !$next ) {
536 - $nextlink = '';
537 - } else {
538 - $nextlink = '<br />' . $sk->link(
539 - $this->mTitle,
540 - wfMsgHtml( 'nextdiff' ),
541 - array(
542 - 'id' => 'differences-nextlink'
543 - ),
544 - array(
545 - 'diff' => 'next',
546 - 'oldid' => $this->mNewid,
547 - ),
548 - array(
549 - 'known',
550 - 'noclasses'
551 - )
552 - );
553 - }
554 - $header = "<div class=\"firstrevisionheader\" style=\"text-align: center\">" .
555 - $sk->revUserTools( $this->mNewRev ) . "<br />" . $sk->revComment( $this->mNewRev ) . $nextlink . "</div>\n";
556 -
557 - $wgOut->addHTML( $header );
558 -
559 - $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
560 - $wgOut->setRobotPolicy( 'noindex,nofollow' );
561 -
562 - wfProfileOut( __METHOD__ );
563 - }
564 -
565 - /**
566 - * Get the diff text, send it to $wgOut
567 - * Returns false if the diff could not be generated, otherwise returns true
568 - */
569 - function showDiff( $otitle, $ntitle, $notice = '' ) {
570 - global $wgOut;
571 - $diff = $this->getDiff( $otitle, $ntitle, $notice );
572 - if ( $diff === false ) {
573 - $wgOut->addWikiMsg( 'missing-article', "<nowiki>(fixme, bug)</nowiki>", '' );
574 - return false;
575 - } else {
576 - $this->showDiffStyle();
577 - $wgOut->addHTML( $diff );
578 - return true;
579 - }
580 - }
581 -
582 - /**
583 - * Add style sheets and supporting JS for diff display.
584 - */
585 - function showDiffStyle() {
586 - global $wgOut;
587 - $wgOut->addModules( 'mediawiki.legacy.diff' );
588 - }
589 -
590 - /**
591 - * Get complete diff table, including header
592 - *
593 - * @param $otitle Title: old title
594 - * @param $ntitle Title: new title
595 - * @param $notice String: HTML between diff header and body
596 - * @return mixed
597 - */
598 - function getDiff( $otitle, $ntitle, $notice = '' ) {
599 - $body = $this->getDiffBody();
600 - if ( $body === false ) {
601 - return false;
602 - } else {
603 - $multi = $this->getMultiNotice();
604 - return $this->addHeader( $body, $otitle, $ntitle, $multi, $notice );
605 - }
606 - }
607 -
608 - /**
609 - * Get the diff table body, without header
610 - *
611 - * @return mixed
612 - */
613 - function getDiffBody() {
614 - global $wgMemc;
615 - wfProfileIn( __METHOD__ );
616 - $this->mCacheHit = true;
617 - // Check if the diff should be hidden from this user
618 - if ( !$this->loadRevisionData() )
619 - return '';
620 - if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) {
621 - return '';
622 - } else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
623 - return '';
624 - } else if ( $this->mOldRev && $this->mNewRev && $this->mOldRev->getID() == $this->mNewRev->getID() ) {
625 - return '';
626 - }
627 - // Cacheable?
628 - $key = false;
629 - if ( $this->mOldid && $this->mNewid ) {
630 - $key = wfMemcKey( 'diff', 'version', MW_DIFF_VERSION, 'oldid', $this->mOldid, 'newid', $this->mNewid );
631 - // Try cache
632 - if ( !$this->mRefreshCache ) {
633 - $difftext = $wgMemc->get( $key );
634 - if ( $difftext ) {
635 - wfIncrStats( 'diff_cache_hit' );
636 - $difftext = $this->localiseLineNumbers( $difftext );
637 - $difftext .= "\n<!-- diff cache key $key -->\n";
638 - wfProfileOut( __METHOD__ );
639 - return $difftext;
640 - }
641 - } // don't try to load but save the result
642 - }
643 - $this->mCacheHit = false;
644 -
645 - // Loadtext is permission safe, this just clears out the diff
646 - if ( !$this->loadText() ) {
647 - wfProfileOut( __METHOD__ );
648 - return false;
649 - }
650 -
651 - $difftext = $this->generateDiffBody( $this->mOldtext, $this->mNewtext );
652 -
653 - // Save to cache for 7 days
654 - if ( !wfRunHooks( 'AbortDiffCache', array( &$this ) ) ) {
655 - wfIncrStats( 'diff_uncacheable' );
656 - } else if ( $key !== false && $difftext !== false ) {
657 - wfIncrStats( 'diff_cache_miss' );
658 - $wgMemc->set( $key, $difftext, 7*86400 );
659 - } else {
660 - wfIncrStats( 'diff_uncacheable' );
661 - }
662 - // Replace line numbers with the text in the user's language
663 - if ( $difftext !== false ) {
664 - $difftext = $this->localiseLineNumbers( $difftext );
665 - }
666 - wfProfileOut( __METHOD__ );
667 - return $difftext;
668 - }
669 -
670 - /**
671 - * Make sure the proper modules are loaded before we try to
672 - * make the diff
673 - */
674 - private function initDiffEngines() {
675 - global $wgExternalDiffEngine;
676 - if ( $wgExternalDiffEngine == 'wikidiff' && !function_exists( 'wikidiff_do_diff' ) ) {
677 - wfProfileIn( __METHOD__ . '-php_wikidiff.so' );
678 - wfSuppressWarnings();
679 - dl( 'php_wikidiff.so' );
680 - wfRestoreWarnings();
681 - wfProfileOut( __METHOD__ . '-php_wikidiff.so' );
682 - }
683 - else if ( $wgExternalDiffEngine == 'wikidiff2' && !function_exists( 'wikidiff2_do_diff' ) ) {
684 - wfProfileIn( __METHOD__ . '-php_wikidiff2.so' );
685 - wfSuppressWarnings();
686 - wfDl( 'wikidiff2' );
687 - wfRestoreWarnings();
688 - wfProfileOut( __METHOD__ . '-php_wikidiff2.so' );
689 - }
690 - }
691 -
692 - /**
693 - * Generate a diff, no caching
694 - *
695 - * @param $otext String: old text, must be already segmented
696 - * @param $ntext String: new text, must be already segmented
697 - */
698 - function generateDiffBody( $otext, $ntext ) {
699 - global $wgExternalDiffEngine, $wgContLang;
700 -
701 - $otext = str_replace( "\r\n", "\n", $otext );
702 - $ntext = str_replace( "\r\n", "\n", $ntext );
703 -
704 - $this->initDiffEngines();
705 -
706 - if ( $wgExternalDiffEngine == 'wikidiff' && function_exists( 'wikidiff_do_diff' ) ) {
707 - # For historical reasons, external diff engine expects
708 - # input text to be HTML-escaped already
709 - $otext = htmlspecialchars ( $wgContLang->segmentForDiff( $otext ) );
710 - $ntext = htmlspecialchars ( $wgContLang->segmentForDiff( $ntext ) );
711 - return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) .
712 - $this->debug( 'wikidiff1' );
713 - }
714 -
715 - if ( $wgExternalDiffEngine == 'wikidiff2' && function_exists( 'wikidiff2_do_diff' ) ) {
716 - # Better external diff engine, the 2 may some day be dropped
717 - # This one does the escaping and segmenting itself
718 - wfProfileIn( 'wikidiff2_do_diff' );
719 - $text = wikidiff2_do_diff( $otext, $ntext, 2 );
720 - $text .= $this->debug( 'wikidiff2' );
721 - wfProfileOut( 'wikidiff2_do_diff' );
722 - return $text;
723 - }
724 - if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) {
725 - # Diff via the shell
726 - global $wgTmpDirectory;
727 - $tempName1 = tempnam( $wgTmpDirectory, 'diff_' );
728 - $tempName2 = tempnam( $wgTmpDirectory, 'diff_' );
729 -
730 - $tempFile1 = fopen( $tempName1, "w" );
731 - if ( !$tempFile1 ) {
732 - wfProfileOut( __METHOD__ );
733 - return false;
734 - }
735 - $tempFile2 = fopen( $tempName2, "w" );
736 - if ( !$tempFile2 ) {
737 - wfProfileOut( __METHOD__ );
738 - return false;
739 - }
740 - fwrite( $tempFile1, $otext );
741 - fwrite( $tempFile2, $ntext );
742 - fclose( $tempFile1 );
743 - fclose( $tempFile2 );
744 - $cmd = wfEscapeShellArg( $wgExternalDiffEngine, $tempName1, $tempName2 );
745 - wfProfileIn( __METHOD__ . "-shellexec" );
746 - $difftext = wfShellExec( $cmd );
747 - $difftext .= $this->debug( "external $wgExternalDiffEngine" );
748 - wfProfileOut( __METHOD__ . "-shellexec" );
749 - unlink( $tempName1 );
750 - unlink( $tempName2 );
751 - return $difftext;
752 - }
753 -
754 - # Native PHP diff
755 - $ota = explode( "\n", $wgContLang->segmentForDiff( $otext ) );
756 - $nta = explode( "\n", $wgContLang->segmentForDiff( $ntext ) );
757 - $diffs = new Diff( $ota, $nta );
758 - $formatter = new TableDiffFormatter();
759 - return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) .
760 - $this->debug();
761 - }
762 -
763 - /**
764 - * Generate a debug comment indicating diff generating time,
765 - * server node, and generator backend.
766 - */
767 - protected function debug( $generator="internal" ) {
768 - global $wgShowHostnames;
769 - if ( !$this->enableDebugComment ) {
770 - return '';
771 - }
772 - $data = array( $generator );
773 - if( $wgShowHostnames ) {
774 - $data[] = wfHostname();
775 - }
776 - $data[] = wfTimestamp( TS_DB );
777 - return "<!-- diff generator: " .
778 - implode( " ",
779 - array_map(
780 - "htmlspecialchars",
781 - $data ) ) .
782 - " -->\n";
783 - }
784 -
785 - /**
786 - * Replace line numbers with the text in the user's language
787 - */
788 - function localiseLineNumbers( $text ) {
789 - return preg_replace_callback( '/<!--LINE (\d+)-->/',
790 - array( &$this, 'localiseLineNumbersCb' ), $text );
791 - }
792 -
793 - function localiseLineNumbersCb( $matches ) {
794 - global $wgLang;
795 - if ( $matches[1] === '1' && $this->mReducedLineNumbers ) return '';
796 - return wfMsgExt( 'lineno', 'escape', $wgLang->formatNum( $matches[1] ) );
797 - }
798 -
799 -
800 - /**
801 - * If there are revisions between the ones being compared, return a note saying so.
802 - */
803 - function getMultiNotice() {
804 - if ( !is_object($this->mOldRev) || !is_object($this->mNewRev) )
805 - return '';
806 -
807 - if( !$this->mOldPage->equals( $this->mNewPage ) ) {
808 - // Comparing two different pages? Count would be meaningless.
809 - return '';
810 - }
811 -
812 - $oldid = $this->mOldRev->getId();
813 - $newid = $this->mNewRev->getId();
814 - if ( $oldid > $newid ) {
815 - $tmp = $oldid; $oldid = $newid; $newid = $tmp;
816 - }
817 -
818 - $n = $this->mTitle->countRevisionsBetween( $oldid, $newid );
819 - if ( !$n ) {
820 - return '';
821 - } else {
822 - global $wgLang;
823 - $dbr = wfGetDB( DB_SLAVE );
824 -
825 - // Actually, the limit is $limit + 1. We do this so we can detect
826 - // if there are > 100 authors in a given revision range. If they
827 - // are, $limit will be passed to diff-multi-manyusers for l10n.
828 - $limit = 100;
829 - $res = $dbr->select( 'revision', 'DISTINCT rev_user_text',
830 - array(
831 - 'rev_page = ' . $this->mOldRev->getPage(),
832 - 'rev_id > ' . $this->mOldRev->getId(),
833 - 'rev_id < ' . $this->mNewRev->getId()
834 - ), __METHOD__,
835 - array( 'LIMIT' => $limit + 1 )
836 - );
837 - $numUsers = $dbr->numRows( $res );
838 - if( $numUsers > $limit ) {
839 - $msg = 'diff-multi-manyusers';
840 - $numUsers = $limit;
841 - } else {
842 - $msg = 'diff-multi';
843 - }
844 - return wfMsgExt( $msg, array( 'parseinline' ), $wgLang->formatnum( $n ),
845 - $wgLang->formatnum( $numUsers ) );
846 - }
847 - }
848 -
849 -
850 - /**
851 - * Add the header to a diff body
852 - */
853 - static function addHeader( $diff, $otitle, $ntitle, $multi = '', $notice = '' ) {
854 - $header = "<table class='diff'>";
855 - if( $diff ) { // Safari/Chrome show broken output if cols not used
856 - $header .= "
857 - <col class='diff-marker' />
858 - <col class='diff-content' />
859 - <col class='diff-marker' />
860 - <col class='diff-content' />";
861 - $colspan = 2;
862 - $multiColspan = 4;
863 - } else {
864 - $colspan = 1;
865 - $multiColspan = 2;
866 - }
867 - $header .= "
868 - <tr valign='top'>
869 - <td colspan='$colspan' class='diff-otitle'>{$otitle}</td>
870 - <td colspan='$colspan' class='diff-ntitle'>{$ntitle}</td>
871 - </tr>";
872 -
873 - if ( $multi != '' ) {
874 - $header .= "<tr><td colspan='{$multiColspan}' align='center' class='diff-multi'>{$multi}</td></tr>";
875 - }
876 - if ( $notice != '' ) {
877 - $header .= "<tr><td colspan='{$multiColspan}' align='center'>{$notice}</td></tr>";
878 - }
879 -
880 - return $header . $diff . "</table>";
881 - }
882 -
883 - /**
884 - * Use specified text instead of loading from the database
885 - */
886 - function setText( $oldText, $newText ) {
887 - $this->mOldtext = $oldText;
888 - $this->mNewtext = $newText;
889 - $this->mTextLoaded = 2;
890 - $this->mRevisionsLoaded = true;
891 - }
892 -
893 - /**
894 - * Load revision metadata for the specified articles. If newid is 0, then compare
895 - * the old article in oldid to the current article; if oldid is 0, then
896 - * compare the current article to the immediately previous one (ignoring the
897 - * value of newid).
898 - *
899 - * If oldid is false, leave the corresponding revision object set
900 - * to false. This is impossible via ordinary user input, and is provided for
901 - * API convenience.
902 - */
903 - function loadRevisionData() {
904 - global $wgLang, $wgUser;
905 - if ( $this->mRevisionsLoaded ) {
906 - return true;
907 - } else {
908 - // Whether it succeeds or fails, we don't want to try again
909 - $this->mRevisionsLoaded = true;
910 - }
911 -
912 - // Load the new revision object
913 - $this->mNewRev = $this->mNewid
914 - ? Revision::newFromId( $this->mNewid )
915 - : Revision::newFromTitle( $this->mTitle );
916 - if( !$this->mNewRev instanceof Revision )
917 - return false;
918 -
919 - // Update the new revision ID in case it was 0 (makes life easier doing UI stuff)
920 - $this->mNewid = $this->mNewRev->getId();
921 -
922 - // Check if page is editable
923 - $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
924 -
925 - // Set assorted variables
926 - $timestamp = $wgLang->timeanddate( $this->mNewRev->getTimestamp(), true );
927 - $dateofrev = $wgLang->date( $this->mNewRev->getTimestamp(), true );
928 - $timeofrev = $wgLang->time( $this->mNewRev->getTimestamp(), true );
929 - $this->mNewPage = $this->mNewRev->getTitle();
930 - if( $this->mNewRev->isCurrent() ) {
931 - $newLink = $this->mNewPage->escapeLocalUrl( array(
932 - 'oldid' => $this->mNewid
933 - ) );
934 - $this->mPagetitle = htmlspecialchars( wfMsg(
935 - 'currentrev-asof',
936 - $timestamp,
937 - $dateofrev,
938 - $timeofrev
939 - ) );
940 - $newEdit = $this->mNewPage->escapeLocalUrl( array(
941 - 'action' => 'edit'
942 - ) );
943 -
944 - $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
945 - $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
946 - } else {
947 - $newLink = $this->mNewPage->escapeLocalUrl( array(
948 - 'oldid' => $this->mNewid
949 - ) );
950 - $newEdit = $this->mNewPage->escapeLocalUrl( array(
951 - 'action' => 'edit',
952 - 'oldid' => $this->mNewid
953 - ) );
954 - $this->mPagetitle = htmlspecialchars( wfMsg(
955 - 'revisionasof',
956 - $timestamp,
957 - $dateofrev,
958 - $timeofrev
959 - ) );
960 -
961 - $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
962 - $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
963 - }
964 - if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
965 - $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";
966 - } else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
967 - $this->mNewtitle = "<span class='history-deleted'>{$this->mNewtitle}</span>";
968 - }
969 -
970 - // Load the old revision object
971 - $this->mOldRev = false;
972 - if( $this->mOldid ) {
973 - $this->mOldRev = Revision::newFromId( $this->mOldid );
974 - } elseif ( $this->mOldid === 0 ) {
975 - $rev = $this->mNewRev->getPrevious();
976 - if( $rev ) {
977 - $this->mOldid = $rev->getId();
978 - $this->mOldRev = $rev;
979 - } else {
980 - // No previous revision; mark to show as first-version only.
981 - $this->mOldid = false;
982 - $this->mOldRev = false;
983 - }
984 - }/* elseif ( $this->mOldid === false ) leave mOldRev false; */
985 -
986 - if( is_null( $this->mOldRev ) ) {
987 - return false;
988 - }
989 -
990 - if ( $this->mOldRev ) {
991 - $this->mOldPage = $this->mOldRev->getTitle();
992 -
993 - $t = $wgLang->timeanddate( $this->mOldRev->getTimestamp(), true );
994 - $dateofrev = $wgLang->date( $this->mOldRev->getTimestamp(), true );
995 - $timeofrev = $wgLang->time( $this->mOldRev->getTimestamp(), true );
996 - $oldLink = $this->mOldPage->escapeLocalUrl( array(
997 - 'oldid' => $this->mOldid
998 - ) );
999 - $oldEdit = $this->mOldPage->escapeLocalUrl( array(
1000 - 'action' => 'edit',
1001 - 'oldid' => $this->mOldid
1002 - ) );
1003 - $this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t, $dateofrev, $timeofrev ) );
1004 -
1005 - $this->mOldtitle = "<a href='$oldLink'>{$this->mOldPagetitle}</a>"
1006 - . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
1007 - // Add an "undo" link
1008 - $newUndo = $this->mNewPage->escapeLocalUrl( array(
1009 - 'action' => 'edit',
1010 - 'undoafter' => $this->mOldid,
1011 - 'undo' => $this->mNewid
1012 - ) );
1013 - $htmlLink = htmlspecialchars( wfMsg( 'editundo' ) );
1014 - $htmlTitle = $wgUser->getSkin()->titleAttrib( 'undo' );
1015 - if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) {
1016 - $this->mNewtitle .= " (<a href='$newUndo' $htmlTitle>" . $htmlLink . "</a>)";
1017 - }
1018 -
1019 - if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) {
1020 - $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';
1021 - } else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) {
1022 - $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';
1023 - }
1024 - }
1025 -
1026 - return true;
1027 - }
1028 -
1029 - /**
1030 - * Load the text of the revisions, as well as revision data.
1031 - */
1032 - function loadText() {
1033 - if ( $this->mTextLoaded == 2 ) {
1034 - return true;
1035 - } else {
1036 - // Whether it succeeds or fails, we don't want to try again
1037 - $this->mTextLoaded = 2;
1038 - }
1039 -
1040 - if ( !$this->loadRevisionData() ) {
1041 - return false;
1042 - }
1043 - if ( $this->mOldRev ) {
1044 - $this->mOldtext = $this->mOldRev->getText( Revision::FOR_THIS_USER );
1045 - if ( $this->mOldtext === false ) {
1046 - return false;
1047 - }
1048 - }
1049 - if ( $this->mNewRev ) {
1050 - $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
1051 - if ( $this->mNewtext === false ) {
1052 - return false;
1053 - }
1054 - }
1055 - return true;
1056 - }
1057 -
1058 - /**
1059 - * Load the text of the new revision, not the old one
1060 - */
1061 - function loadNewText() {
1062 - if ( $this->mTextLoaded >= 1 ) {
1063 - return true;
1064 - } else {
1065 - $this->mTextLoaded = 1;
1066 - }
1067 - if ( !$this->loadRevisionData() ) {
1068 - return false;
1069 - }
1070 - $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
1071 - return true;
1072 - }
1073 -}
Index: trunk/phase3/includes/diff/WikiDiff.php
——@@ -0,0 +1,1241 @@
 2+<?php
 3+/**
 4+ * A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
 5+ *
 6+ * Copyright © 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
 7+ * You may copy this code freely under the conditions of the GPL.
 8+ *
 9+ * @file
 10+ * @ingroup DifferenceEngine
 11+ * @defgroup DifferenceEngine DifferenceEngine
 12+ */
 13+
 14+/**
 15+ * @todo document
 16+ * @private
 17+ * @ingroup DifferenceEngine
 18+ */
 19+class _DiffOp {
 20+ var $type;
 21+ var $orig;
 22+ var $closing;
 23+
 24+ function reverse() {
 25+ trigger_error('pure virtual', E_USER_ERROR);
 26+ }
 27+
 28+ function norig() {
 29+ return $this->orig ? sizeof($this->orig) : 0;
 30+ }
 31+
 32+ function nclosing() {
 33+ return $this->closing ? sizeof($this->closing) : 0;
 34+ }
 35+}
 36+
 37+/**
 38+ * @todo document
 39+ * @private
 40+ * @ingroup DifferenceEngine
 41+ */
 42+class _DiffOp_Copy extends _DiffOp {
 43+ var $type = 'copy';
 44+
 45+ function __construct ($orig, $closing = false) {
 46+ if (!is_array($closing))
 47+ $closing = $orig;
 48+ $this->orig = $orig;
 49+ $this->closing = $closing;
 50+ }
 51+
 52+ function reverse() {
 53+ return new _DiffOp_Copy($this->closing, $this->orig);
 54+ }
 55+}
 56+
 57+/**
 58+ * @todo document
 59+ * @private
 60+ * @ingroup DifferenceEngine
 61+ */
 62+class _DiffOp_Delete extends _DiffOp {
 63+ var $type = 'delete';
 64+
 65+ function __construct ($lines) {
 66+ $this->orig = $lines;
 67+ $this->closing = false;
 68+ }
 69+
 70+ function reverse() {
 71+ return new _DiffOp_Add($this->orig);
 72+ }
 73+}
 74+
 75+/**
 76+ * @todo document
 77+ * @private
 78+ * @ingroup DifferenceEngine
 79+ */
 80+class _DiffOp_Add extends _DiffOp {
 81+ var $type = 'add';
 82+
 83+ function __construct ($lines) {
 84+ $this->closing = $lines;
 85+ $this->orig = false;
 86+ }
 87+
 88+ function reverse() {
 89+ return new _DiffOp_Delete($this->closing);
 90+ }
 91+}
 92+
 93+/**
 94+ * @todo document
 95+ * @private
 96+ * @ingroup DifferenceEngine
 97+ */
 98+class _DiffOp_Change extends _DiffOp {
 99+ var $type = 'change';
 100+
 101+ function __construct ($orig, $closing) {
 102+ $this->orig = $orig;
 103+ $this->closing = $closing;
 104+ }
 105+
 106+ function reverse() {
 107+ return new _DiffOp_Change($this->closing, $this->orig);
 108+ }
 109+}
 110+
 111+/**
 112+ * Class used internally by Diff to actually compute the diffs.
 113+ *
 114+ * The algorithm used here is mostly lifted from the perl module
 115+ * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
 116+ * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
 117+ *
 118+ * More ideas are taken from:
 119+ * http://www.ics.uci.edu/~eppstein/161/960229.html
 120+ *
 121+ * Some ideas are (and a bit of code) are from from analyze.c, from GNU
 122+ * diffutils-2.7, which can be found at:
 123+ * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
 124+ *
 125+ * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
 126+ * are my own.
 127+ *
 128+ * Line length limits for robustness added by Tim Starling, 2005-08-31
 129+ * Alternative implementation added by Guy Van den Broeck, 2008-07-30
 130+ *
 131+ * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
 132+ * @private
 133+ * @ingroup DifferenceEngine
 134+ */
 135+class _DiffEngine {
 136+
 137+ const MAX_XREF_LENGTH = 10000;
 138+
 139+ function diff ($from_lines, $to_lines){
 140+ wfProfileIn( __METHOD__ );
 141+
 142+ // Diff and store locally
 143+ $this->diff_local($from_lines, $to_lines);
 144+
 145+ // Merge edits when possible
 146+ $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
 147+ $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
 148+
 149+ // Compute the edit operations.
 150+ $n_from = sizeof($from_lines);
 151+ $n_to = sizeof($to_lines);
 152+
 153+ $edits = array();
 154+ $xi = $yi = 0;
 155+ while ($xi < $n_from || $yi < $n_to) {
 156+ assert($yi < $n_to || $this->xchanged[$xi]);
 157+ assert($xi < $n_from || $this->ychanged[$yi]);
 158+
 159+ // Skip matching "snake".
 160+ $copy = array();
 161+ while ( $xi < $n_from && $yi < $n_to
 162+ && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
 163+ $copy[] = $from_lines[$xi++];
 164+ ++$yi;
 165+ }
 166+ if ($copy)
 167+ $edits[] = new _DiffOp_Copy($copy);
 168+
 169+ // Find deletes & adds.
 170+ $delete = array();
 171+ while ($xi < $n_from && $this->xchanged[$xi])
 172+ $delete[] = $from_lines[$xi++];
 173+
 174+ $add = array();
 175+ while ($yi < $n_to && $this->ychanged[$yi])
 176+ $add[] = $to_lines[$yi++];
 177+
 178+ if ($delete && $add)
 179+ $edits[] = new _DiffOp_Change($delete, $add);
 180+ elseif ($delete)
 181+ $edits[] = new _DiffOp_Delete($delete);
 182+ elseif ($add)
 183+ $edits[] = new _DiffOp_Add($add);
 184+ }
 185+ wfProfileOut( __METHOD__ );
 186+ return $edits;
 187+ }
 188+
 189+ function diff_local ($from_lines, $to_lines) {
 190+ global $wgExternalDiffEngine;
 191+ wfProfileIn( __METHOD__);
 192+
 193+ if($wgExternalDiffEngine == 'wikidiff3'){
 194+ // wikidiff3
 195+ $wikidiff3 = new WikiDiff3();
 196+ $wikidiff3->diff($from_lines, $to_lines);
 197+ $this->xchanged = $wikidiff3->removed;
 198+ $this->ychanged = $wikidiff3->added;
 199+ unset($wikidiff3);
 200+ }else{
 201+ // old diff
 202+ $n_from = sizeof($from_lines);
 203+ $n_to = sizeof($to_lines);
 204+ $this->xchanged = $this->ychanged = array();
 205+ $this->xv = $this->yv = array();
 206+ $this->xind = $this->yind = array();
 207+ unset($this->seq);
 208+ unset($this->in_seq);
 209+ unset($this->lcs);
 210+
 211+ // Skip leading common lines.
 212+ for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
 213+ if ($from_lines[$skip] !== $to_lines[$skip])
 214+ break;
 215+ $this->xchanged[$skip] = $this->ychanged[$skip] = false;
 216+ }
 217+ // Skip trailing common lines.
 218+ $xi = $n_from; $yi = $n_to;
 219+ for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
 220+ if ($from_lines[$xi] !== $to_lines[$yi])
 221+ break;
 222+ $this->xchanged[$xi] = $this->ychanged[$yi] = false;
 223+ }
 224+
 225+ // Ignore lines which do not exist in both files.
 226+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
 227+ $xhash[$this->_line_hash($from_lines[$xi])] = 1;
 228+ }
 229+
 230+ for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
 231+ $line = $to_lines[$yi];
 232+ if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )
 233+ continue;
 234+ $yhash[$this->_line_hash($line)] = 1;
 235+ $this->yv[] = $line;
 236+ $this->yind[] = $yi;
 237+ }
 238+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
 239+ $line = $from_lines[$xi];
 240+ if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )
 241+ continue;
 242+ $this->xv[] = $line;
 243+ $this->xind[] = $xi;
 244+ }
 245+
 246+ // Find the LCS.
 247+ $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
 248+ }
 249+ wfProfileOut( __METHOD__ );
 250+ }
 251+
 252+ /**
 253+ * Returns the whole line if it's small enough, or the MD5 hash otherwise
 254+ */
 255+ function _line_hash( $line ) {
 256+ if ( strlen( $line ) > self::MAX_XREF_LENGTH ) {
 257+ return md5( $line );
 258+ } else {
 259+ return $line;
 260+ }
 261+ }
 262+
 263+ /* Divide the Largest Common Subsequence (LCS) of the sequences
 264+ * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 265+ * sized segments.
 266+ *
 267+ * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an
 268+ * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 269+ * sub sequences. The first sub-sequence is contained in [X0, X1),
 270+ * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note
 271+ * that (X0, Y0) == (XOFF, YOFF) and
 272+ * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 273+ *
 274+ * This function assumes that the first lines of the specified portions
 275+ * of the two files do not match, and likewise that the last lines do not
 276+ * match. The caller must trim matching lines from the beginning and end
 277+ * of the portions it is going to specify.
 278+ */
 279+ function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
 280+ $flip = false;
 281+
 282+ if ($xlim - $xoff > $ylim - $yoff) {
 283+ // Things seems faster (I'm not sure I understand why)
 284+ // when the shortest sequence in X.
 285+ $flip = true;
 286+ list ($xoff, $xlim, $yoff, $ylim)
 287+ = array( $yoff, $ylim, $xoff, $xlim);
 288+ }
 289+
 290+ if ($flip)
 291+ for ($i = $ylim - 1; $i >= $yoff; $i--)
 292+ $ymatches[$this->xv[$i]][] = $i;
 293+ else
 294+ for ($i = $ylim - 1; $i >= $yoff; $i--)
 295+ $ymatches[$this->yv[$i]][] = $i;
 296+
 297+ $this->lcs = 0;
 298+ $this->seq[0]= $yoff - 1;
 299+ $this->in_seq = array();
 300+ $ymids[0] = array();
 301+
 302+ $numer = $xlim - $xoff + $nchunks - 1;
 303+ $x = $xoff;
 304+ for ($chunk = 0; $chunk < $nchunks; $chunk++) {
 305+ if ($chunk > 0)
 306+ for ($i = 0; $i <= $this->lcs; $i++)
 307+ $ymids[$i][$chunk-1] = $this->seq[$i];
 308+
 309+ $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
 310+ for ( ; $x < $x1; $x++) {
 311+ $line = $flip ? $this->yv[$x] : $this->xv[$x];
 312+ if (empty($ymatches[$line])) {
 313+ continue;
 314+ }
 315+ $matches = $ymatches[$line];
 316+ reset($matches);
 317+ while ( list( $junk, $y ) = each( $matches ) ) {
 318+ if ( empty( $this->in_seq[$y] ) ) {
 319+ $k = $this->_lcs_pos( $y );
 320+ assert( $k > 0 );
 321+ $ymids[$k] = $ymids[$k-1];
 322+ break;
 323+ }
 324+ }
 325+ while (list ( /* $junk */, $y) = each($matches)) {
 326+ if ($y > $this->seq[$k-1]) {
 327+ assert($y < $this->seq[$k]);
 328+ // Optimization: this is a common case:
 329+ // next match is just replacing previous match.
 330+ $this->in_seq[$this->seq[$k]] = false;
 331+ $this->seq[$k] = $y;
 332+ $this->in_seq[$y] = 1;
 333+ } else if (empty($this->in_seq[$y])) {
 334+ $k = $this->_lcs_pos($y);
 335+ assert($k > 0);
 336+ $ymids[$k] = $ymids[$k-1];
 337+ }
 338+ }
 339+ }
 340+ }
 341+
 342+ $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
 343+ $ymid = $ymids[$this->lcs];
 344+ for ($n = 0; $n < $nchunks - 1; $n++) {
 345+ $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
 346+ $y1 = $ymid[$n] + 1;
 347+ $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
 348+ }
 349+ $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
 350+
 351+ return array($this->lcs, $seps);
 352+ }
 353+
 354+ function _lcs_pos ($ypos) {
 355+ $end = $this->lcs;
 356+ if ($end == 0 || $ypos > $this->seq[$end]) {
 357+ $this->seq[++$this->lcs] = $ypos;
 358+ $this->in_seq[$ypos] = 1;
 359+ return $this->lcs;
 360+ }
 361+
 362+ $beg = 1;
 363+ while ($beg < $end) {
 364+ $mid = (int)(($beg + $end) / 2);
 365+ if ( $ypos > $this->seq[$mid] )
 366+ $beg = $mid + 1;
 367+ else
 368+ $end = $mid;
 369+ }
 370+
 371+ assert($ypos != $this->seq[$end]);
 372+
 373+ $this->in_seq[$this->seq[$end]] = false;
 374+ $this->seq[$end] = $ypos;
 375+ $this->in_seq[$ypos] = 1;
 376+ return $end;
 377+ }
 378+
 379+ /* Find LCS of two sequences.
 380+ *
 381+ * The results are recorded in the vectors $this->{x,y}changed[], by
 382+ * storing a 1 in the element for each line that is an insertion
 383+ * or deletion (ie. is not in the LCS).
 384+ *
 385+ * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 386+ *
 387+ * Note that XLIM, YLIM are exclusive bounds.
 388+ * All line numbers are origin-0 and discarded lines are not counted.
 389+ */
 390+ function _compareseq ($xoff, $xlim, $yoff, $ylim) {
 391+ // Slide down the bottom initial diagonal.
 392+ while ($xoff < $xlim && $yoff < $ylim
 393+ && $this->xv[$xoff] == $this->yv[$yoff]) {
 394+ ++$xoff;
 395+ ++$yoff;
 396+ }
 397+
 398+ // Slide up the top initial diagonal.
 399+ while ($xlim > $xoff && $ylim > $yoff
 400+ && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
 401+ --$xlim;
 402+ --$ylim;
 403+ }
 404+
 405+ if ($xoff == $xlim || $yoff == $ylim)
 406+ $lcs = 0;
 407+ else {
 408+ // This is ad hoc but seems to work well.
 409+ //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 410+ //$nchunks = max(2,min(8,(int)$nchunks));
 411+ $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
 412+ list ($lcs, $seps)
 413+ = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
 414+ }
 415+
 416+ if ($lcs == 0) {
 417+ // X and Y sequences have no common subsequence:
 418+ // mark all changed.
 419+ while ($yoff < $ylim)
 420+ $this->ychanged[$this->yind[$yoff++]] = 1;
 421+ while ($xoff < $xlim)
 422+ $this->xchanged[$this->xind[$xoff++]] = 1;
 423+ } else {
 424+ // Use the partitions to split this problem into subproblems.
 425+ reset($seps);
 426+ $pt1 = $seps[0];
 427+ while ($pt2 = next($seps)) {
 428+ $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
 429+ $pt1 = $pt2;
 430+ }
 431+ }
 432+ }
 433+
 434+ /* Adjust inserts/deletes of identical lines to join changes
 435+ * as much as possible.
 436+ *
 437+ * We do something when a run of changed lines include a
 438+ * line at one end and has an excluded, identical line at the other.
 439+ * We are free to choose which identical line is included.
 440+ * `compareseq' usually chooses the one at the beginning,
 441+ * but usually it is cleaner to consider the following identical line
 442+ * to be the "change".
 443+ *
 444+ * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 445+ */
 446+ function _shift_boundaries ($lines, &$changed, $other_changed) {
 447+ wfProfileIn( __METHOD__ );
 448+ $i = 0;
 449+ $j = 0;
 450+
 451+ assert('sizeof($lines) == sizeof($changed)');
 452+ $len = sizeof($lines);
 453+ $other_len = sizeof($other_changed);
 454+
 455+ while (1) {
 456+ /*
 457+ * Scan forwards to find beginning of another run of changes.
 458+ * Also keep track of the corresponding point in the other file.
 459+ *
 460+ * Throughout this code, $i and $j are adjusted together so that
 461+ * the first $i elements of $changed and the first $j elements
 462+ * of $other_changed both contain the same number of zeros
 463+ * (unchanged lines).
 464+ * Furthermore, $j is always kept so that $j == $other_len or
 465+ * $other_changed[$j] == false.
 466+ */
 467+ while ($j < $other_len && $other_changed[$j])
 468+ $j++;
 469+
 470+ while ($i < $len && ! $changed[$i]) {
 471+ assert('$j < $other_len && ! $other_changed[$j]');
 472+ $i++; $j++;
 473+ while ($j < $other_len && $other_changed[$j])
 474+ $j++;
 475+ }
 476+
 477+ if ($i == $len)
 478+ break;
 479+
 480+ $start = $i;
 481+
 482+ // Find the end of this run of changes.
 483+ while (++$i < $len && $changed[$i])
 484+ continue;
 485+
 486+ do {
 487+ /*
 488+ * Record the length of this run of changes, so that
 489+ * we can later determine whether the run has grown.
 490+ */
 491+ $runlength = $i - $start;
 492+
 493+ /*
 494+ * Move the changed region back, so long as the
 495+ * previous unchanged line matches the last changed one.
 496+ * This merges with previous changed regions.
 497+ */
 498+ while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
 499+ $changed[--$start] = 1;
 500+ $changed[--$i] = false;
 501+ while ($start > 0 && $changed[$start - 1])
 502+ $start--;
 503+ assert('$j > 0');
 504+ while ($other_changed[--$j])
 505+ continue;
 506+ assert('$j >= 0 && !$other_changed[$j]');
 507+ }
 508+
 509+ /*
 510+ * Set CORRESPONDING to the end of the changed run, at the last
 511+ * point where it corresponds to a changed run in the other file.
 512+ * CORRESPONDING == LEN means no such point has been found.
 513+ */
 514+ $corresponding = $j < $other_len ? $i : $len;
 515+
 516+ /*
 517+ * Move the changed region forward, so long as the
 518+ * first changed line matches the following unchanged one.
 519+ * This merges with following changed regions.
 520+ * Do this second, so that if there are no merges,
 521+ * the changed region is moved forward as far as possible.
 522+ */
 523+ while ($i < $len && $lines[$start] == $lines[$i]) {
 524+ $changed[$start++] = false;
 525+ $changed[$i++] = 1;
 526+ while ($i < $len && $changed[$i])
 527+ $i++;
 528+
 529+ assert('$j < $other_len && ! $other_changed[$j]');
 530+ $j++;
 531+ if ($j < $other_len && $other_changed[$j]) {
 532+ $corresponding = $i;
 533+ while ($j < $other_len && $other_changed[$j])
 534+ $j++;
 535+ }
 536+ }
 537+ } while ($runlength != $i - $start);
 538+
 539+ /*
 540+ * If possible, move the fully-merged run of changes
 541+ * back to a corresponding run in the other file.
 542+ */
 543+ while ($corresponding < $i) {
 544+ $changed[--$start] = 1;
 545+ $changed[--$i] = 0;
 546+ assert('$j > 0');
 547+ while ($other_changed[--$j])
 548+ continue;
 549+ assert('$j >= 0 && !$other_changed[$j]');
 550+ }
 551+ }
 552+ wfProfileOut( __METHOD__ );
 553+ }
 554+}
 555+
 556+/**
 557+ * Class representing a 'diff' between two sequences of strings.
 558+ * @todo document
 559+ * @private
 560+ * @ingroup DifferenceEngine
 561+ */
 562+class Diff
 563+{
 564+ var $edits;
 565+
 566+ /**
 567+ * Constructor.
 568+ * Computes diff between sequences of strings.
 569+ *
 570+ * @param $from_lines array An array of strings.
 571+ * (Typically these are lines from a file.)
 572+ * @param $to_lines array An array of strings.
 573+ */
 574+ function __construct($from_lines, $to_lines) {
 575+ $eng = new _DiffEngine;
 576+ $this->edits = $eng->diff($from_lines, $to_lines);
 577+ //$this->_check($from_lines, $to_lines);
 578+ }
 579+
 580+ /**
 581+ * Compute reversed Diff.
 582+ *
 583+ * SYNOPSIS:
 584+ *
 585+ * $diff = new Diff($lines1, $lines2);
 586+ * $rev = $diff->reverse();
 587+ * @return object A Diff object representing the inverse of the
 588+ * original diff.
 589+ */
 590+ function reverse () {
 591+ $rev = $this;
 592+ $rev->edits = array();
 593+ foreach ($this->edits as $edit) {
 594+ $rev->edits[] = $edit->reverse();
 595+ }
 596+ return $rev;
 597+ }
 598+
 599+ /**
 600+ * Check for empty diff.
 601+ *
 602+ * @return bool True iff two sequences were identical.
 603+ */
 604+ function isEmpty () {
 605+ foreach ($this->edits as $edit) {
 606+ if ($edit->type != 'copy')
 607+ return false;
 608+ }
 609+ return true;
 610+ }
 611+
 612+ /**
 613+ * Compute the length of the Longest Common Subsequence (LCS).
 614+ *
 615+ * This is mostly for diagnostic purposed.
 616+ *
 617+ * @return int The length of the LCS.
 618+ */
 619+ function lcs () {
 620+ $lcs = 0;
 621+ foreach ($this->edits as $edit) {
 622+ if ($edit->type == 'copy')
 623+ $lcs += sizeof($edit->orig);
 624+ }
 625+ return $lcs;
 626+ }
 627+
 628+ /**
 629+ * Get the original set of lines.
 630+ *
 631+ * This reconstructs the $from_lines parameter passed to the
 632+ * constructor.
 633+ *
 634+ * @return array The original sequence of strings.
 635+ */
 636+ function orig() {
 637+ $lines = array();
 638+
 639+ foreach ($this->edits as $edit) {
 640+ if ($edit->orig)
 641+ array_splice($lines, sizeof($lines), 0, $edit->orig);
 642+ }
 643+ return $lines;
 644+ }
 645+
 646+ /**
 647+ * Get the closing set of lines.
 648+ *
 649+ * This reconstructs the $to_lines parameter passed to the
 650+ * constructor.
 651+ *
 652+ * @return array The sequence of strings.
 653+ */
 654+ function closing() {
 655+ $lines = array();
 656+
 657+ foreach ($this->edits as $edit) {
 658+ if ($edit->closing)
 659+ array_splice($lines, sizeof($lines), 0, $edit->closing);
 660+ }
 661+ return $lines;
 662+ }
 663+
 664+ /**
 665+ * Check a Diff for validity.
 666+ *
 667+ * This is here only for debugging purposes.
 668+ */
 669+ function _check ($from_lines, $to_lines) {
 670+ wfProfileIn( __METHOD__ );
 671+ if (serialize($from_lines) != serialize($this->orig()))
 672+ trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 673+ if (serialize($to_lines) != serialize($this->closing()))
 674+ trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
 675+
 676+ $rev = $this->reverse();
 677+ if (serialize($to_lines) != serialize($rev->orig()))
 678+ trigger_error("Reversed original doesn't match", E_USER_ERROR);
 679+ if (serialize($from_lines) != serialize($rev->closing()))
 680+ trigger_error("Reversed closing doesn't match", E_USER_ERROR);
 681+
 682+
 683+ $prevtype = 'none';
 684+ foreach ($this->edits as $edit) {
 685+ if ( $prevtype == $edit->type )
 686+ trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 687+ $prevtype = $edit->type;
 688+ }
 689+
 690+ $lcs = $this->lcs();
 691+ trigger_error('Diff okay: LCS = '.$lcs, E_USER_NOTICE);
 692+ wfProfileOut( __METHOD__ );
 693+ }
 694+}
 695+
 696+/**
 697+ * @todo document, bad name.
 698+ * @private
 699+ * @ingroup DifferenceEngine
 700+ */
 701+class MappedDiff extends Diff
 702+{
 703+ /**
 704+ * Constructor.
 705+ *
 706+ * Computes diff between sequences of strings.
 707+ *
 708+ * This can be used to compute things like
 709+ * case-insensitve diffs, or diffs which ignore
 710+ * changes in white-space.
 711+ *
 712+ * @param $from_lines array An array of strings.
 713+ * (Typically these are lines from a file.)
 714+ *
 715+ * @param $to_lines array An array of strings.
 716+ *
 717+ * @param $mapped_from_lines array This array should
 718+ * have the same size number of elements as $from_lines.
 719+ * The elements in $mapped_from_lines and
 720+ * $mapped_to_lines are what is actually compared
 721+ * when computing the diff.
 722+ *
 723+ * @param $mapped_to_lines array This array should
 724+ * have the same number of elements as $to_lines.
 725+ */
 726+ function __construct($from_lines, $to_lines,
 727+ $mapped_from_lines, $mapped_to_lines) {
 728+ wfProfileIn( __METHOD__ );
 729+
 730+ assert(sizeof($from_lines) == sizeof($mapped_from_lines));
 731+ assert(sizeof($to_lines) == sizeof($mapped_to_lines));
 732+
 733+ parent::__construct($mapped_from_lines, $mapped_to_lines);
 734+
 735+ $xi = $yi = 0;
 736+ for ($i = 0; $i < sizeof($this->edits); $i++) {
 737+ $orig = &$this->edits[$i]->orig;
 738+ if (is_array($orig)) {
 739+ $orig = array_slice($from_lines, $xi, sizeof($orig));
 740+ $xi += sizeof($orig);
 741+ }
 742+
 743+ $closing = &$this->edits[$i]->closing;
 744+ if (is_array($closing)) {
 745+ $closing = array_slice($to_lines, $yi, sizeof($closing));
 746+ $yi += sizeof($closing);
 747+ }
 748+ }
 749+ wfProfileOut( __METHOD__ );
 750+ }
 751+}
 752+
 753+/**
 754+ * A class to format Diffs
 755+ *
 756+ * This class formats the diff in classic diff format.
 757+ * It is intended that this class be customized via inheritance,
 758+ * to obtain fancier outputs.
 759+ * @todo document
 760+ * @private
 761+ * @ingroup DifferenceEngine
 762+ */
 763+class DiffFormatter {
 764+ /**
 765+ * Number of leading context "lines" to preserve.
 766+ *
 767+ * This should be left at zero for this class, but subclasses
 768+ * may want to set this to other values.
 769+ */
 770+ var $leading_context_lines = 0;
 771+
 772+ /**
 773+ * Number of trailing context "lines" to preserve.
 774+ *
 775+ * This should be left at zero for this class, but subclasses
 776+ * may want to set this to other values.
 777+ */
 778+ var $trailing_context_lines = 0;
 779+
 780+ /**
 781+ * Format a diff.
 782+ *
 783+ * @param $diff object A Diff object.
 784+ * @return string The formatted output.
 785+ */
 786+ function format($diff) {
 787+ wfProfileIn( __METHOD__ );
 788+
 789+ $xi = $yi = 1;
 790+ $block = false;
 791+ $context = array();
 792+
 793+ $nlead = $this->leading_context_lines;
 794+ $ntrail = $this->trailing_context_lines;
 795+
 796+ $this->_start_diff();
 797+
 798+ foreach ($diff->edits as $edit) {
 799+ if ($edit->type == 'copy') {
 800+ if (is_array($block)) {
 801+ if (sizeof($edit->orig) <= $nlead + $ntrail) {
 802+ $block[] = $edit;
 803+ }
 804+ else{
 805+ if ($ntrail) {
 806+ $context = array_slice($edit->orig, 0, $ntrail);
 807+ $block[] = new _DiffOp_Copy($context);
 808+ }
 809+ $this->_block($x0, $ntrail + $xi - $x0,
 810+ $y0, $ntrail + $yi - $y0,
 811+ $block);
 812+ $block = false;
 813+ }
 814+ }
 815+ $context = $edit->orig;
 816+ }
 817+ else {
 818+ if (! is_array($block)) {
 819+ $context = array_slice($context, sizeof($context) - $nlead);
 820+ $x0 = $xi - sizeof($context);
 821+ $y0 = $yi - sizeof($context);
 822+ $block = array();
 823+ if ($context)
 824+ $block[] = new _DiffOp_Copy($context);
 825+ }
 826+ $block[] = $edit;
 827+ }
 828+
 829+ if ($edit->orig)
 830+ $xi += sizeof($edit->orig);
 831+ if ($edit->closing)
 832+ $yi += sizeof($edit->closing);
 833+ }
 834+
 835+ if (is_array($block))
 836+ $this->_block($x0, $xi - $x0,
 837+ $y0, $yi - $y0,
 838+ $block);
 839+
 840+ $end = $this->_end_diff();
 841+ wfProfileOut( __METHOD__ );
 842+ return $end;
 843+ }
 844+
 845+ function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
 846+ wfProfileIn( __METHOD__ );
 847+ $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
 848+ foreach ($edits as $edit) {
 849+ if ($edit->type == 'copy')
 850+ $this->_context($edit->orig);
 851+ elseif ($edit->type == 'add')
 852+ $this->_added($edit->closing);
 853+ elseif ($edit->type == 'delete')
 854+ $this->_deleted($edit->orig);
 855+ elseif ($edit->type == 'change')
 856+ $this->_changed($edit->orig, $edit->closing);
 857+ else
 858+ trigger_error('Unknown edit type', E_USER_ERROR);
 859+ }
 860+ $this->_end_block();
 861+ wfProfileOut( __METHOD__ );
 862+ }
 863+
 864+ function _start_diff() {
 865+ ob_start();
 866+ }
 867+
 868+ function _end_diff() {
 869+ $val = ob_get_contents();
 870+ ob_end_clean();
 871+ return $val;
 872+ }
 873+
 874+ function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 875+ if ($xlen > 1)
 876+ $xbeg .= "," . ($xbeg + $xlen - 1);
 877+ if ($ylen > 1)
 878+ $ybeg .= "," . ($ybeg + $ylen - 1);
 879+
 880+ return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
 881+ }
 882+
 883+ function _start_block($header) {
 884+ echo $header . "\n";
 885+ }
 886+
 887+ function _end_block() {
 888+ }
 889+
 890+ function _lines($lines, $prefix = ' ') {
 891+ foreach ($lines as $line)
 892+ echo "$prefix $line\n";
 893+ }
 894+
 895+ function _context($lines) {
 896+ $this->_lines($lines);
 897+ }
 898+
 899+ function _added($lines) {
 900+ $this->_lines($lines, '>');
 901+ }
 902+ function _deleted($lines) {
 903+ $this->_lines($lines, '<');
 904+ }
 905+
 906+ function _changed($orig, $closing) {
 907+ $this->_deleted($orig);
 908+ echo "---\n";
 909+ $this->_added($closing);
 910+ }
 911+}
 912+
 913+/**
 914+ * A formatter that outputs unified diffs
 915+ * @ingroup DifferenceEngine
 916+ */
 917+
 918+class UnifiedDiffFormatter extends DiffFormatter {
 919+ var $leading_context_lines = 2;
 920+ var $trailing_context_lines = 2;
 921+
 922+ function _added($lines) {
 923+ $this->_lines($lines, '+');
 924+ }
 925+ function _deleted($lines) {
 926+ $this->_lines($lines, '-');
 927+ }
 928+ function _changed($orig, $closing) {
 929+ $this->_deleted($orig);
 930+ $this->_added($closing);
 931+ }
 932+ function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 933+ return "@@ -$xbeg,$xlen +$ybeg,$ylen @@";
 934+ }
 935+}
 936+
 937+/**
 938+ * A pseudo-formatter that just passes along the Diff::$edits array
 939+ * @ingroup DifferenceEngine
 940+ */
 941+class ArrayDiffFormatter extends DiffFormatter {
 942+ function format($diff) {
 943+ $oldline = 1;
 944+ $newline = 1;
 945+ $retval = array();
 946+ foreach($diff->edits as $edit)
 947+ switch($edit->type) {
 948+ case 'add':
 949+ foreach($edit->closing as $l) {
 950+ $retval[] = array(
 951+ 'action' => 'add',
 952+ 'new'=> $l,
 953+ 'newline' => $newline++
 954+ );
 955+ }
 956+ break;
 957+ case 'delete':
 958+ foreach($edit->orig as $l) {
 959+ $retval[] = array(
 960+ 'action' => 'delete',
 961+ 'old' => $l,
 962+ 'oldline' => $oldline++,
 963+ );
 964+ }
 965+ break;
 966+ case 'change':
 967+ foreach($edit->orig as $i => $l) {
 968+ $retval[] = array(
 969+ 'action' => 'change',
 970+ 'old' => $l,
 971+ 'new' => @$edit->closing[$i],
 972+ 'oldline' => $oldline++,
 973+ 'newline' => $newline++,
 974+ );
 975+ }
 976+ break;
 977+ case 'copy':
 978+ $oldline += count($edit->orig);
 979+ $newline += count($edit->orig);
 980+ }
 981+ return $retval;
 982+ }
 983+}
 984+
 985+/**
 986+ * Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
 987+ *
 988+ */
 989+
 990+define('NBSP', '&#160;'); // iso-8859-x non-breaking space.
 991+
 992+/**
 993+ * @todo document
 994+ * @private
 995+ * @ingroup DifferenceEngine
 996+ */
 997+class _HWLDF_WordAccumulator {
 998+ function __construct () {
 999+ $this->_lines = array();
 1000+ $this->_line = '';
 1001+ $this->_group = '';
 1002+ $this->_tag = '';
 1003+ }
 1004+
 1005+ function _flushGroup ($new_tag) {
 1006+ if ($this->_group !== '') {
 1007+ if ($this->_tag == 'ins')
 1008+ $this->_line .= '<ins class="diffchange diffchange-inline">' .
 1009+ htmlspecialchars ( $this->_group ) . '</ins>';
 1010+ elseif ($this->_tag == 'del')
 1011+ $this->_line .= '<del class="diffchange diffchange-inline">' .
 1012+ htmlspecialchars ( $this->_group ) . '</del>';
 1013+ else
 1014+ $this->_line .= htmlspecialchars ( $this->_group );
 1015+ }
 1016+ $this->_group = '';
 1017+ $this->_tag = $new_tag;
 1018+ }
 1019+
 1020+ function _flushLine ($new_tag) {
 1021+ $this->_flushGroup($new_tag);
 1022+ if ($this->_line != '')
 1023+ array_push ( $this->_lines, $this->_line );
 1024+ else
 1025+ # make empty lines visible by inserting an NBSP
 1026+ array_push ( $this->_lines, NBSP );
 1027+ $this->_line = '';
 1028+ }
 1029+
 1030+ function addWords ($words, $tag = '') {
 1031+ if ($tag != $this->_tag)
 1032+ $this->_flushGroup($tag);
 1033+
 1034+ foreach ($words as $word) {
 1035+ // new-line should only come as first char of word.
 1036+ if ($word == '')
 1037+ continue;
 1038+ if ($word[0] == "\n") {
 1039+ $this->_flushLine($tag);
 1040+ $word = substr($word, 1);
 1041+ }
 1042+ assert(!strstr($word, "\n"));
 1043+ $this->_group .= $word;
 1044+ }
 1045+ }
 1046+
 1047+ function getLines() {
 1048+ $this->_flushLine('~done');
 1049+ return preg_replace( '/\n/m', '', $this->_lines);
 1050+ }
 1051+}
 1052+
 1053+/**
 1054+ * @todo document
 1055+ * @private
 1056+ * @ingroup DifferenceEngine
 1057+ */
 1058+class WordLevelDiff extends MappedDiff {
 1059+ const MAX_LINE_LENGTH = 10000;
 1060+
 1061+ function __construct ($orig_lines, $closing_lines) {
 1062+ wfProfileIn( __METHOD__ );
 1063+
 1064+ list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
 1065+ list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
 1066+
 1067+ parent::__construct($orig_words, $closing_words,
 1068+ $orig_stripped, $closing_stripped);
 1069+ wfProfileOut( __METHOD__ );
 1070+ }
 1071+
 1072+ function _split($lines) {
 1073+ wfProfileIn( __METHOD__ );
 1074+
 1075+ $words = array();
 1076+ $stripped = array();
 1077+ $first = true;
 1078+ foreach ( $lines as $line ) {
 1079+ # If the line is too long, just pretend the entire line is one big word
 1080+ # This prevents resource exhaustion problems
 1081+ if ( $first ) {
 1082+ $first = false;
 1083+ } else {
 1084+ $words[] = "\n";
 1085+ $stripped[] = "\n";
 1086+ }
 1087+ if ( strlen( $line ) > self::MAX_LINE_LENGTH ) {
 1088+ $words[] = $line;
 1089+ $stripped[] = $line;
 1090+ } else {
 1091+ $m = array();
 1092+ if (preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
 1093+ $line, $m))
 1094+ {
 1095+ $words = array_merge( $words, $m[0] );
 1096+ $stripped = array_merge( $stripped, $m[1] );
 1097+ }
 1098+ }
 1099+ }
 1100+ wfProfileOut( __METHOD__ );
 1101+ return array($words, $stripped);
 1102+ }
 1103+
 1104+ function orig () {
 1105+ wfProfileIn( __METHOD__ );
 1106+ $orig = new _HWLDF_WordAccumulator;
 1107+
 1108+ foreach ($this->edits as $edit) {
 1109+ if ($edit->type == 'copy')
 1110+ $orig->addWords($edit->orig);
 1111+ elseif ($edit->orig)
 1112+ $orig->addWords($edit->orig, 'del');
 1113+ }
 1114+ $lines = $orig->getLines();
 1115+ wfProfileOut( __METHOD__ );
 1116+ return $lines;
 1117+ }
 1118+
 1119+ function closing () {
 1120+ wfProfileIn( __METHOD__ );
 1121+ $closing = new _HWLDF_WordAccumulator;
 1122+
 1123+ foreach ($this->edits as $edit) {
 1124+ if ($edit->type == 'copy')
 1125+ $closing->addWords($edit->closing);
 1126+ elseif ($edit->closing)
 1127+ $closing->addWords($edit->closing, 'ins');
 1128+ }
 1129+ $lines = $closing->getLines();
 1130+ wfProfileOut( __METHOD__ );
 1131+ return $lines;
 1132+ }
 1133+}
 1134+
 1135+/**
 1136+ * Wikipedia Table style diff formatter.
 1137+ * @todo document
 1138+ * @private
 1139+ * @ingroup DifferenceEngine
 1140+ */
 1141+class TableDiffFormatter extends DiffFormatter {
 1142+ function __construct() {
 1143+ $this->leading_context_lines = 2;
 1144+ $this->trailing_context_lines = 2;
 1145+ }
 1146+
 1147+ public static function escapeWhiteSpace( $msg ) {
 1148+ $msg = preg_replace( '/^ /m', '&#160; ', $msg );
 1149+ $msg = preg_replace( '/ $/m', ' &#160;', $msg );
 1150+ $msg = preg_replace( '/ /', '&#160; ', $msg );
 1151+ return $msg;
 1152+ }
 1153+
 1154+ function _block_header( $xbeg, $xlen, $ybeg, $ylen ) {
 1155+ $r = '<tr><td colspan="2" class="diff-lineno"><!--LINE '.$xbeg."--></td>\n" .
 1156+ '<td colspan="2" class="diff-lineno"><!--LINE '.$ybeg."--></td></tr>\n";
 1157+ return $r;
 1158+ }
 1159+
 1160+ function _start_block( $header ) {
 1161+ echo $header;
 1162+ }
 1163+
 1164+ function _end_block() {
 1165+ }
 1166+
 1167+ function _lines( $lines, $prefix=' ', $color='white' ) {
 1168+ }
 1169+
 1170+ # HTML-escape parameter before calling this
 1171+ function addedLine( $line ) {
 1172+ return $this->wrapLine( '+', 'diff-addedline', $line );
 1173+ }
 1174+
 1175+ # HTML-escape parameter before calling this
 1176+ function deletedLine( $line ) {
 1177+ return $this->wrapLine( '&minus;', 'diff-deletedline', $line );
 1178+ }
 1179+
 1180+ # HTML-escape parameter before calling this
 1181+ function contextLine( $line ) {
 1182+ return $this->wrapLine( '&#160;', 'diff-context', $line );
 1183+ }
 1184+
 1185+ private function wrapLine( $marker, $class, $line ) {
 1186+ if( $line !== '' ) {
 1187+ // The <div> wrapper is needed for 'overflow: auto' style to scroll properly
 1188+ $line = Xml::tags( 'div', null, $this->escapeWhiteSpace( $line ) );
 1189+ }
 1190+ return "<td class='diff-marker'>$marker</td><td class='$class'>$line</td>";
 1191+ }
 1192+
 1193+ function emptyLine() {
 1194+ return '<td colspan="2">&#160;</td>';
 1195+ }
 1196+
 1197+ function _added( $lines ) {
 1198+ foreach ($lines as $line) {
 1199+ echo '<tr>' . $this->emptyLine() .
 1200+ $this->addedLine( '<ins class="diffchange">' .
 1201+ htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";
 1202+ }
 1203+ }
 1204+
 1205+ function _deleted($lines) {
 1206+ foreach ($lines as $line) {
 1207+ echo '<tr>' . $this->deletedLine( '<del class="diffchange">' .
 1208+ htmlspecialchars ( $line ) . '</del>' ) .
 1209+ $this->emptyLine() . "</tr>\n";
 1210+ }
 1211+ }
 1212+
 1213+ function _context( $lines ) {
 1214+ foreach ($lines as $line) {
 1215+ echo '<tr>' .
 1216+ $this->contextLine( htmlspecialchars ( $line ) ) .
 1217+ $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";
 1218+ }
 1219+ }
 1220+
 1221+ function _changed( $orig, $closing ) {
 1222+ wfProfileIn( __METHOD__ );
 1223+
 1224+ $diff = new WordLevelDiff( $orig, $closing );
 1225+ $del = $diff->orig();
 1226+ $add = $diff->closing();
 1227+
 1228+ # Notice that WordLevelDiff returns HTML-escaped output.
 1229+ # Hence, we will be calling addedLine/deletedLine without HTML-escaping.
 1230+
 1231+ while ( $line = array_shift( $del ) ) {
 1232+ $aline = array_shift( $add );
 1233+ echo '<tr>' . $this->deletedLine( $line ) .
 1234+ $this->addedLine( $aline ) . "</tr>\n";
 1235+ }
 1236+ foreach ($add as $line) { # If any leftovers
 1237+ echo '<tr>' . $this->emptyLine() .
 1238+ $this->addedLine( $line ) . "</tr>\n";
 1239+ }
 1240+ wfProfileOut( __METHOD__ );
 1241+ }
 1242+}
Property changes on: trunk/phase3/includes/diff/WikiDiff.php
___________________________________________________________________
Added: svn:eol-style
11243 + native
Added: svn:keywords
21244 + Author Date Id Revision
Index: trunk/phase3/includes/diff/WikiDiff3.php
——@@ -0,0 +1,586 @@
 2+<?php
 3+/**
 4+ * New version of the difference engine
 5+ *
 6+ * Copyright © 2008 Guy Van den Broeck <guy@guyvdb.eu>
 7+ *
 8+ * This program is free software; you can redistribute it and/or modify
 9+ * it under the terms of the GNU General Public License as published by
 10+ * the Free Software Foundation; either version 2 of the License, or
 11+ * (at your option) any later version.
 12+ *
 13+ * This program is distributed in the hope that it will be useful,
 14+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
 15+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 16+ * GNU General Public License for more details.
 17+ *
 18+ * You should have received a copy of the GNU General Public License
 19+ * along with this program; if not, write to the Free Software
 20+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 21+ * http://www.gnu.org/copyleft/gpl.html
 22+ *
 23+ * @file
 24+ * @ingroup DifferenceEngine
 25+ */
 26+
 27+/**
 28+ * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
 29+ * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
 30+ * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
 31+ * "An O(NP) Sequence Comparison Algorithm").
 32+ *
 33+ * This implementation supports an upper bound on the excution time.
 34+ *
 35+ * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
 36+ *
 37+ * @author Guy Van den Broeck
 38+ * @ingroup DifferenceEngine
 39+ */
 40+class WikiDiff3 {
 41+
 42+ //Input variables
 43+ private $from;
 44+ private $to;
 45+ private $m;
 46+ private $n;
 47+
 48+ private $tooLong;
 49+ private $powLimit;
 50+
 51+ //State variables
 52+ private $maxDifferences;
 53+ private $lcsLengthCorrectedForHeuristic = false;
 54+
 55+ //Output variables
 56+ public $length;
 57+ public $removed;
 58+ public $added;
 59+ public $heuristicUsed;
 60+
 61+ function __construct($tooLong = 2000000, $powLimit = 1.45){
 62+ $this->tooLong = $tooLong;
 63+ $this->powLimit = $powLimit;
 64+ }
 65+
 66+ public function diff(/*array*/ $from, /*array*/ $to){
 67+ //remember initial lengths
 68+ $m = sizeof($from);
 69+ $n = count($to);
 70+
 71+ $this->heuristicUsed = false;
 72+
 73+ //output
 74+ $removed = $m > 0 ? array_fill(0, $m, true) : array();
 75+ $added = $n > 0 ? array_fill(0, $n, true) : array();
 76+
 77+ //reduce the complexity for the next step (intentionally done twice)
 78+ //remove common tokens at the start
 79+ $i = 0;
 80+ while($i < $m && $i < $n && $from[$i] === $to[$i]) {
 81+ $removed[$i] = $added[$i] = false;
 82+ unset($from[$i], $to[$i]);
 83+ ++$i;
 84+ }
 85+
 86+ //remove common tokens at the end
 87+ $j = 1;
 88+ while($i + $j <= $m && $i + $j <= $n && $from[$m - $j] === $to[$n - $j]) {
 89+ $removed[$m - $j] = $added[$n - $j] = false;
 90+ unset($from[$m - $j], $to[$n - $j]);
 91+ ++$j;
 92+ }
 93+
 94+ $this->from = $newFromIndex = $this->to = $newToIndex = array();
 95+
 96+ //remove tokens not in both sequences
 97+ $shared = array();
 98+ foreach( $from as $key ) {
 99+ $shared[$key] = false;
 100+ }
 101+
 102+ foreach($to as $index => &$el) {
 103+ if(array_key_exists($el, $shared)) {
 104+ //keep it
 105+ $this->to[] = $el;
 106+ $shared[$el] = true;
 107+ $newToIndex[] = $index;
 108+ }
 109+ }
 110+ foreach($from as $index => &$el) {
 111+ if($shared[$el]) {
 112+ //keep it
 113+ $this->from[] = $el;
 114+ $newFromIndex[] = $index;
 115+ }
 116+ }
 117+
 118+ unset($shared, $from, $to);
 119+
 120+ $this->m = count($this->from);
 121+ $this->n = count($this->to);
 122+
 123+ $this->removed = $this->m > 0 ? array_fill(0, $this->m, true) : array();
 124+ $this->added = $this->n > 0 ? array_fill(0, $this->n, true) : array();
 125+
 126+ if ($this->m == 0 || $this->n == 0) {
 127+ $this->length = 0;
 128+ } else {
 129+ $this->maxDifferences = ceil(($this->m + $this->n) / 2.0);
 130+ if ($this->m * $this->n > $this->tooLong) {
 131+ // limit complexity to D^POW_LIMIT for long sequences
 132+ $this->maxDifferences = floor(pow($this->maxDifferences, $this->powLimit - 1.0));
 133+ wfDebug("Limiting max number of differences to $this->maxDifferences\n");
 134+ }
 135+
 136+ /*
 137+ * The common prefixes and suffixes are always part of some LCS, include
 138+ * them now to reduce our search space
 139+ */
 140+ $max = min($this->m, $this->n);
 141+ for ($forwardBound = 0; $forwardBound < $max
 142+ && $this->from[$forwardBound] === $this->to[$forwardBound];
 143+ ++$forwardBound) {
 144+ $this->removed[$forwardBound] = $this->added[$forwardBound] = false;
 145+ }
 146+
 147+ $backBoundL1 = $this->m - 1;
 148+ $backBoundL2 = $this->n - 1;
 149+
 150+ while ($backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
 151+ && $this->from[$backBoundL1] === $this->to[$backBoundL2]) {
 152+ $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
 153+ }
 154+
 155+ $temp = array_fill(0, $this->m + $this->n + 1, 0);
 156+ $V = array($temp, $temp);
 157+ $snake = array(0, 0, 0);
 158+
 159+ $this->length = $forwardBound + $this->m - $backBoundL1 - 1
 160+ + $this->lcs_rec($forwardBound, $backBoundL1,
 161+ $forwardBound, $backBoundL2, $V, $snake);
 162+ }
 163+
 164+ $this->m = $m;
 165+ $this->n = $n;
 166+
 167+ $this->length += $i + $j - 1;
 168+
 169+ foreach($this->removed as $key => &$removed_elem) {
 170+ if(!$removed_elem) {
 171+ $removed[$newFromIndex[$key]] = false;
 172+ }
 173+ }
 174+ foreach($this->added as $key => &$added_elem) {
 175+ if(!$added_elem) {
 176+ $added[$newToIndex[$key]] = false;
 177+ }
 178+ }
 179+ $this->removed = $removed;
 180+ $this->added = $added;
 181+ }
 182+
 183+ function diff_range($from_lines, $to_lines) {
 184+ // Diff and store locally
 185+ $this->diff($from_lines, $to_lines);
 186+ unset($from_lines, $to_lines);
 187+
 188+ $ranges = array();
 189+ $xi = $yi = 0;
 190+ while ($xi < $this->m || $yi < $this->n) {
 191+ // Matching "snake".
 192+ while ($xi < $this->m && $yi < $this->n
 193+ && !$this->removed[$xi]
 194+ && !$this->added[$yi]) {
 195+ ++$xi;
 196+ ++$yi;
 197+ }
 198+ // Find deletes & adds.
 199+ $xstart = $xi;
 200+ while ($xi < $this->m && $this->removed[$xi]) {
 201+ ++$xi;
 202+ }
 203+
 204+ $ystart = $yi;
 205+ while ($yi < $this->n && $this->added[$yi]) {
 206+ ++$yi;
 207+ }
 208+
 209+ if ($xi > $xstart || $yi > $ystart) {
 210+ $ranges[] = new RangeDifference($xstart, $xi,
 211+ $ystart, $yi);
 212+ }
 213+ }
 214+ return $ranges;
 215+ }
 216+
 217+ private function lcs_rec($bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake) {
 218+ // check that both sequences are non-empty
 219+ if ($bottoml1 > $topl1 || $bottoml2 > $topl2) {
 220+ return 0;
 221+ }
 222+
 223+ $d = $this->find_middle_snake($bottoml1, $topl1, $bottoml2,
 224+ $topl2, $V, $snake);
 225+
 226+ // need to store these so we don't lose them when they're
 227+ // overwritten by the recursion
 228+ $len = $snake[2];
 229+ $startx = $snake[0];
 230+ $starty = $snake[1];
 231+
 232+ // the middle snake is part of the LCS, store it
 233+ for ($i = 0; $i < $len; ++$i) {
 234+ $this->removed[$startx + $i] = $this->added[$starty + $i] = false;
 235+ }
 236+
 237+ if ($d > 1) {
 238+ return $len
 239+ + $this->lcs_rec($bottoml1, $startx - 1, $bottoml2,
 240+ $starty - 1, $V, $snake)
 241+ + $this->lcs_rec($startx + $len, $topl1, $starty + $len,
 242+ $topl2, $V, $snake);
 243+ } else if ($d == 1) {
 244+ /*
 245+ * In this case the sequences differ by exactly 1 line. We have
 246+ * already saved all the lines after the difference in the for loop
 247+ * above, now we need to save all the lines before the difference.
 248+ */
 249+ $max = min($startx - $bottoml1, $starty - $bottoml2);
 250+ for ($i = 0; $i < $max; ++$i) {
 251+ $this->removed[$bottoml1 + $i] =
 252+ $this->added[$bottoml2 + $i] = false;
 253+ }
 254+ return $max + $len;
 255+ }
 256+ return $len;
 257+ }
 258+
 259+ private function find_middle_snake($bottoml1, $topl1, $bottoml2,$topl2, &$V, &$snake) {
 260+ $from = &$this->from;
 261+ $to = &$this->to;
 262+ $V0 = &$V[0];
 263+ $V1 = &$V[1];
 264+ $snake0 = &$snake[0];
 265+ $snake1 = &$snake[1];
 266+ $snake2 = &$snake[2];
 267+ $bottoml1_min_1 = $bottoml1-1;
 268+ $bottoml2_min_1 = $bottoml2-1;
 269+ $N = $topl1 - $bottoml1_min_1;
 270+ $M = $topl2 - $bottoml2_min_1;
 271+ $delta = $N - $M;
 272+ $maxabsx = $N+$bottoml1;
 273+ $maxabsy = $M+$bottoml2;
 274+ $limit = min($this->maxDifferences, ceil(($N + $M ) / 2));
 275+
 276+ //value_to_add_forward: a 0 or 1 that we add to the start
 277+ // offset to make it odd/even
 278+ if (($M & 1) == 1) {
 279+ $value_to_add_forward = 1;
 280+ } else {
 281+ $value_to_add_forward = 0;
 282+ }
 283+
 284+ if (($N & 1) == 1) {
 285+ $value_to_add_backward = 1;
 286+ } else {
 287+ $value_to_add_backward = 0;
 288+ }
 289+
 290+ $start_forward = -$M;
 291+ $end_forward = $N;
 292+ $start_backward = -$N;
 293+ $end_backward = $M;
 294+
 295+ $limit_min_1 = $limit - 1;
 296+ $limit_plus_1 = $limit + 1;
 297+
 298+ $V0[$limit_plus_1] = 0;
 299+ $V1[$limit_min_1] = $N;
 300+ $limit = min($this->maxDifferences, ceil(($N + $M ) / 2));
 301+
 302+ if (($delta & 1) == 1) {
 303+ for ($d = 0; $d <= $limit; ++$d) {
 304+ $start_diag = max($value_to_add_forward + $start_forward, -$d);
 305+ $end_diag = min($end_forward, $d);
 306+ $value_to_add_forward = 1 - $value_to_add_forward;
 307+
 308+ // compute forward furthest reaching paths
 309+ for ($k = $start_diag; $k <= $end_diag; $k += 2) {
 310+ if ($k == -$d || ($k < $d
 311+ && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k])) {
 312+ $x = $V0[$limit_plus_1 + $k];
 313+ } else {
 314+ $x = $V0[$limit_min_1 + $k] + 1;
 315+ }
 316+
 317+ $absx = $snake0 = $x + $bottoml1;
 318+ $absy = $snake1 = $x - $k + $bottoml2;
 319+
 320+ while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
 321+ ++$absx;
 322+ ++$absy;
 323+ }
 324+ $x = $absx-$bottoml1;
 325+
 326+ $snake2 = $absx -$snake0;
 327+ $V0[$limit + $k] = $x;
 328+ if ($k >= $delta - $d + 1 && $k <= $delta + $d - 1
 329+ && $x >= $V1[$limit + $k - $delta]) {
 330+ return 2 * $d - 1;
 331+ }
 332+
 333+ // check to see if we can cut down the diagonal range
 334+ if ($x >= $N && $end_forward > $k - 1) {
 335+ $end_forward = $k - 1;
 336+ } else if ($absy - $bottoml2 >= $M) {
 337+ $start_forward = $k + 1;
 338+ $value_to_add_forward = 0;
 339+ }
 340+ }
 341+
 342+ $start_diag = max($value_to_add_backward + $start_backward, -$d);
 343+ $end_diag = min($end_backward, $d);
 344+ $value_to_add_backward = 1 - $value_to_add_backward;
 345+
 346+ // compute backward furthest reaching paths
 347+ for ($k = $start_diag; $k <= $end_diag; $k += 2) {
 348+ if ($k == $d
 349+ || ($k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k])) {
 350+ $x = $V1[$limit_min_1 + $k];
 351+ } else {
 352+ $x = $V1[$limit_plus_1 + $k] - 1;
 353+ }
 354+
 355+ $y = $x - $k - $delta;
 356+
 357+ $snake2 = 0;
 358+ while ($x > 0 && $y > 0
 359+ && $from[$x +$bottoml1_min_1] === $to[$y + $bottoml2_min_1]) {
 360+ --$x;
 361+ --$y;
 362+ ++$snake2;
 363+ }
 364+ $V1[$limit + $k] = $x;
 365+
 366+ // check to see if we can cut down our diagonal range
 367+ if ($x <= 0) {
 368+ $start_backward = $k + 1;
 369+ $value_to_add_backward = 0;
 370+ } else if ($y <= 0 && $end_backward > $k - 1) {
 371+ $end_backward = $k - 1;
 372+ }
 373+ }
 374+ }
 375+ } else {
 376+ for ($d = 0; $d <= $limit; ++$d) {
 377+ $start_diag = max($value_to_add_forward + $start_forward, -$d);
 378+ $end_diag = min($end_forward, $d);
 379+ $value_to_add_forward = 1 - $value_to_add_forward;
 380+
 381+ // compute forward furthest reaching paths
 382+ for ($k = $start_diag; $k <= $end_diag; $k += 2) {
 383+ if ($k == -$d
 384+ || ($k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k])) {
 385+ $x = $V0[$limit_plus_1 + $k];
 386+ } else {
 387+ $x = $V0[$limit_min_1 + $k] + 1;
 388+ }
 389+
 390+ $absx = $snake0 = $x + $bottoml1;
 391+ $absy = $snake1 = $x - $k + $bottoml2;
 392+
 393+ while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
 394+ ++$absx;
 395+ ++$absy;
 396+ }
 397+ $x = $absx-$bottoml1;
 398+ $snake2 = $absx -$snake0;
 399+ $V0[$limit + $k] = $x;
 400+
 401+ // check to see if we can cut down the diagonal range
 402+ if ($x >= $N && $end_forward > $k - 1) {
 403+ $end_forward = $k - 1;
 404+ } else if ($absy-$bottoml2 >= $M) {
 405+ $start_forward = $k + 1;
 406+ $value_to_add_forward = 0;
 407+ }
 408+ }
 409+
 410+ $start_diag = max($value_to_add_backward + $start_backward, -$d);
 411+ $end_diag = min($end_backward, $d);
 412+ $value_to_add_backward = 1 - $value_to_add_backward;
 413+
 414+ // compute backward furthest reaching paths
 415+ for ($k = $start_diag; $k <= $end_diag; $k += 2) {
 416+ if ($k == $d
 417+ || ($k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k])) {
 418+ $x = $V1[$limit_min_1 + $k];
 419+ } else {
 420+ $x = $V1[$limit_plus_1 + $k] - 1;
 421+ }
 422+
 423+ $y = $x - $k - $delta;
 424+
 425+ $snake2 = 0;
 426+ while ($x > 0 && $y > 0
 427+ && $from[$x +$bottoml1_min_1] === $to[$y + $bottoml2_min_1]) {
 428+ --$x;
 429+ --$y;
 430+ ++$snake2;
 431+ }
 432+ $V1[$limit + $k] = $x;
 433+
 434+ if ($k >= -$delta - $d && $k <= $d - $delta
 435+ && $x <= $V0[$limit + $k + $delta]) {
 436+ $snake0 = $bottoml1 + $x;
 437+ $snake1 = $bottoml2 + $y;
 438+ return 2 * $d;
 439+ }
 440+
 441+ // check to see if we can cut down our diagonal range
 442+ if ($x <= 0) {
 443+ $start_backward = $k + 1;
 444+ $value_to_add_backward = 0;
 445+ } else if ($y <= 0 && $end_backward > $k - 1) {
 446+ $end_backward = $k - 1;
 447+ }
 448+ }
 449+ }
 450+ }
 451+ /*
 452+ * computing the true LCS is too expensive, instead find the diagonal
 453+ * with the most progress and pretend a midle snake of length 0 occurs
 454+ * there.
 455+ */
 456+
 457+ $most_progress = self::findMostProgress($M, $N, $limit, $V);
 458+
 459+ $snake0 = $bottoml1 + $most_progress[0];
 460+ $snake1 = $bottoml2 + $most_progress[1];
 461+ $snake2 = 0;
 462+ wfDebug("Computing the LCS is too expensive. Using a heuristic.\n");
 463+ $this->heuristicUsed = true;
 464+ return 5; /*
 465+ * HACK: since we didn't really finish the LCS computation
 466+ * we don't really know the length of the SES. We don't do
 467+ * anything with the result anyway, unless it's <=1. We know
 468+ * for a fact SES > 1 so 5 is as good a number as any to
 469+ * return here
 470+ */
 471+ }
 472+
 473+ private static function findMostProgress($M, $N, $limit, $V) {
 474+ $delta = $N - $M;
 475+
 476+ if (($M & 1) == ($limit & 1)) {
 477+ $forward_start_diag = max(-$M, -$limit);
 478+ } else {
 479+ $forward_start_diag = max(1 - $M, -$limit);
 480+ }
 481+
 482+ $forward_end_diag = min($N, $limit);
 483+
 484+ if (($N & 1) == ($limit & 1)) {
 485+ $backward_start_diag = max(-$N, -$limit);
 486+ } else {
 487+ $backward_start_diag = max(1 - $N, -$limit);
 488+ }
 489+
 490+ $backward_end_diag = -min($M, $limit);
 491+
 492+ $temp = array(0, 0, 0);
 493+
 494+
 495+ $max_progress = array_fill(0, ceil(max($forward_end_diag - $forward_start_diag,
 496+ $backward_end_diag - $backward_start_diag) / 2), $temp);
 497+ $num_progress = 0; // the 1st entry is current, it is initialized
 498+ // with 0s
 499+
 500+ // first search the forward diagonals
 501+ for ($k = $forward_start_diag; $k <= $forward_end_diag; $k += 2) {
 502+ $x = $V[0][$limit + $k];
 503+ $y = $x - $k;
 504+ if ($x > $N || $y > $M) {
 505+ continue;
 506+ }
 507+
 508+ $progress = $x + $y;
 509+ if ($progress > $max_progress[0][2]) {
 510+ $num_progress = 0;
 511+ $max_progress[0][0] = $x;
 512+ $max_progress[0][1] = $y;
 513+ $max_progress[0][2] = $progress;
 514+ } else if ($progress == $max_progress[0][2]) {
 515+ ++$num_progress;
 516+ $max_progress[$num_progress][0] = $x;
 517+ $max_progress[$num_progress][1] = $y;
 518+ $max_progress[$num_progress][2] = $progress;
 519+ }
 520+ }
 521+
 522+ $max_progress_forward = true; // initially the maximum
 523+ // progress is in the forward
 524+ // direction
 525+
 526+ // now search the backward diagonals
 527+ for ($k = $backward_start_diag; $k <= $backward_end_diag; $k += 2) {
 528+ $x = $V[1][$limit + $k];
 529+ $y = $x - $k - $delta;
 530+ if ($x < 0 || $y < 0) {
 531+ continue;
 532+ }
 533+
 534+ $progress = $N - $x + $M - $y;
 535+ if ($progress > $max_progress[0][2]) {
 536+ $num_progress = 0;
 537+ $max_progress_forward = false;
 538+ $max_progress[0][0] = $x;
 539+ $max_progress[0][1] = $y;
 540+ $max_progress[0][2] = $progress;
 541+ } else if ($progress == $max_progress[0][2] && !$max_progress_forward) {
 542+ ++$num_progress;
 543+ $max_progress[$num_progress][0] = $x;
 544+ $max_progress[$num_progress][1] = $y;
 545+ $max_progress[$num_progress][2] = $progress;
 546+ }
 547+ }
 548+
 549+ // return the middle diagonal with maximal progress.
 550+ return $max_progress[floor($num_progress / 2)];
 551+ }
 552+
 553+ public function getLcsLength(){
 554+ if($this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic){
 555+ $this->lcsLengthCorrectedForHeuristic = true;
 556+ $this->length = $this->m-array_sum($this->added);
 557+ }
 558+ return $this->length;
 559+ }
 560+
 561+}
 562+
 563+/**
 564+ * Alternative representation of a set of changes, by the index
 565+ * ranges that are changed.
 566+ *
 567+ * @ingroup DifferenceEngine
 568+ */
 569+class RangeDifference {
 570+
 571+ public $leftstart;
 572+ public $leftend;
 573+ public $leftlength;
 574+
 575+ public $rightstart;
 576+ public $rightend;
 577+ public $rightlength;
 578+
 579+ function __construct($leftstart, $leftend, $rightstart, $rightend){
 580+ $this->leftstart = $leftstart;
 581+ $this->leftend = $leftend;
 582+ $this->leftlength = $leftend - $leftstart;
 583+ $this->rightstart = $rightstart;
 584+ $this->rightend = $rightend;
 585+ $this->rightlength = $rightend - $rightstart;
 586+ }
 587+}
Property changes on: trunk/phase3/includes/diff/WikiDiff3.php
___________________________________________________________________
Added: svn:eol-style
1588 + native
Index: trunk/phase3/includes/diff/DifferenceEngine.php
——@@ -1,1241 +1,1072 @@
22 <?php
33 /**
4 - * A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
 4+ * User interface for the difference engine
55 *
6 - * Copyright © 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
7 - * You may copy this code freely under the conditions of the GPL.
8 - *
96 * @file
107 * @ingroup DifferenceEngine
11 - * @defgroup DifferenceEngine DifferenceEngine
128 */
13 -
 9+
1410 /**
15 - * @todo document
16 - * @private
17 - * @ingroup DifferenceEngine
 11+ * Constant to indicate diff cache compatibility.
 12+ * Bump this when changing the diff formatting in a way that
 13+ * fixes important bugs or such to force cached diff views to
 14+ * clear.
1815 */
19 -class _DiffOp {
20 - var $type;
21 - var $orig;
22 - var $closing;
 16+define( 'MW_DIFF_VERSION', '1.11a' );
2317
24 - function reverse() {
25 - trigger_error('pure virtual', E_USER_ERROR);
26 - }
27 -
28 - function norig() {
29 - return $this->orig ? sizeof($this->orig) : 0;
30 - }
31 -
32 - function nclosing() {
33 - return $this->closing ? sizeof($this->closing) : 0;
34 - }
35 -}
36 -
3718 /**
3819 * @todo document
39 - * @private
4020 * @ingroup DifferenceEngine
4121 */
42 -class _DiffOp_Copy extends _DiffOp {
43 - var $type = 'copy';
 22+class DifferenceEngine {
 23+ /**#@+
 24+ * @private
 25+ */
 26+ var $mOldid, $mNewid, $mTitle;
 27+ var $mOldtitle, $mNewtitle, $mPagetitle;
 28+ var $mOldtext, $mNewtext;
 29+ var $mOldPage, $mNewPage;
 30+ var $mRcidMarkPatrolled;
 31+ var $mOldRev, $mNewRev;
 32+ var $mRevisionsLoaded = false; // Have the revisions been loaded
 33+ var $mTextLoaded = 0; // How many text blobs have been loaded, 0, 1 or 2?
 34+ var $mCacheHit = false; // Was the diff fetched from cache?
4435
45 - function __construct ($orig, $closing = false) {
46 - if (!is_array($closing))
47 - $closing = $orig;
48 - $this->orig = $orig;
49 - $this->closing = $closing;
50 - }
 36+ /**
 37+ * Set this to true to add debug info to the HTML output.
 38+ * Warning: this may cause RSS readers to spuriously mark articles as "new"
 39+ * (bug 20601)
 40+ */
 41+ var $enableDebugComment = false;
5142
52 - function reverse() {
53 - return new _DiffOp_Copy($this->closing, $this->orig);
54 - }
55 -}
 43+ // If true, line X is not displayed when X is 1, for example to increase
 44+ // readability and conserve space with many small diffs.
 45+ protected $mReducedLineNumbers = false;
5646
57 -/**
58 - * @todo document
59 - * @private
60 - * @ingroup DifferenceEngine
61 - */
62 -class _DiffOp_Delete extends _DiffOp {
63 - var $type = 'delete';
 47+ protected $unhide = false; # show rev_deleted content if allowed
 48+ /**#@-*/
6449
65 - function __construct ($lines) {
66 - $this->orig = $lines;
67 - $this->closing = false;
68 - }
 50+ /**
 51+ * Constructor
 52+ * @param $titleObj Title object that the diff is associated with
 53+ * @param $old Integer: old ID we want to show and diff with.
 54+ * @param $new String: either 'prev' or 'next'.
 55+ * @param $rcid Integer: ??? FIXME (default 0)
 56+ * @param $refreshCache boolean If set, refreshes the diff cache
 57+ * @param $unhide boolean If set, allow viewing deleted revs
 58+ */
 59+ function __construct( $titleObj = null, $old = 0, $new = 0, $rcid = 0,
 60+ $refreshCache = false, $unhide = false )
 61+ {
 62+ if ( $titleObj ) {
 63+ $this->mTitle = $titleObj;
 64+ } else {
 65+ global $wgTitle;
 66+ $this->mTitle = $wgTitle;
 67+ }
 68+ wfDebug("DifferenceEngine old '$old' new '$new' rcid '$rcid'\n");
6969
70 - function reverse() {
71 - return new _DiffOp_Add($this->orig);
 70+ if ( 'prev' === $new ) {
 71+ # Show diff between revision $old and the previous one.
 72+ # Get previous one from DB.
 73+ $this->mNewid = intval($old);
 74+ $this->mOldid = $this->mTitle->getPreviousRevisionID( $this->mNewid );
 75+ } elseif ( 'next' === $new ) {
 76+ # Show diff between revision $old and the next one.
 77+ # Get next one from DB.
 78+ $this->mOldid = intval($old);
 79+ $this->mNewid = $this->mTitle->getNextRevisionID( $this->mOldid );
 80+ if ( false === $this->mNewid ) {
 81+ # if no result, NewId points to the newest old revision. The only newer
 82+ # revision is cur, which is "0".
 83+ $this->mNewid = 0;
 84+ }
 85+ } else {
 86+ $this->mOldid = intval($old);
 87+ $this->mNewid = intval($new);
 88+ wfRunHooks( 'NewDifferenceEngine', array(&$titleObj, &$this->mOldid, &$this->mNewid, $old, $new) );
 89+ }
 90+ $this->mRcidMarkPatrolled = intval($rcid); # force it to be an integer
 91+ $this->mRefreshCache = $refreshCache;
 92+ $this->unhide = $unhide;
7293 }
73 -}
7494
75 -/**
76 - * @todo document
77 - * @private
78 - * @ingroup DifferenceEngine
79 - */
80 -class _DiffOp_Add extends _DiffOp {
81 - var $type = 'add';
82 -
83 - function __construct ($lines) {
84 - $this->closing = $lines;
85 - $this->orig = false;
 95+ function setReducedLineNumbers( $value = true ) {
 96+ $this->mReducedLineNumbers = $value;
8697 }
8798
88 - function reverse() {
89 - return new _DiffOp_Delete($this->closing);
 99+ function getTitle() {
 100+ return $this->mTitle;
90101 }
91 -}
92 -
93 -/**
94 - * @todo document
95 - * @private
96 - * @ingroup DifferenceEngine
97 - */
98 -class _DiffOp_Change extends _DiffOp {
99 - var $type = 'change';
100 -
101 - function __construct ($orig, $closing) {
102 - $this->orig = $orig;
103 - $this->closing = $closing;
 102+
 103+ function wasCacheHit() {
 104+ return $this->mCacheHit;
104105 }
105 -
106 - function reverse() {
107 - return new _DiffOp_Change($this->closing, $this->orig);
 106+
 107+ function getOldid() {
 108+ return $this->mOldid;
108109 }
109 -}
 110+
 111+ function getNewid() {
 112+ return $this->mNewid;
 113+ }
110114
111 -/**
112 - * Class used internally by Diff to actually compute the diffs.
113 - *
114 - * The algorithm used here is mostly lifted from the perl module
115 - * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
116 - * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
117 - *
118 - * More ideas are taken from:
119 - * http://www.ics.uci.edu/~eppstein/161/960229.html
120 - *
121 - * Some ideas are (and a bit of code) are from from analyze.c, from GNU
122 - * diffutils-2.7, which can be found at:
123 - * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
124 - *
125 - * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
126 - * are my own.
127 - *
128 - * Line length limits for robustness added by Tim Starling, 2005-08-31
129 - * Alternative implementation added by Guy Van den Broeck, 2008-07-30
130 - *
131 - * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
132 - * @private
133 - * @ingroup DifferenceEngine
134 - */
135 -class _DiffEngine {
136 -
137 - const MAX_XREF_LENGTH = 10000;
138 -
139 - function diff ($from_lines, $to_lines){
 115+ function showDiffPage( $diffOnly = false ) {
 116+ global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol;
140117 wfProfileIn( __METHOD__ );
141118
142 - // Diff and store locally
143 - $this->diff_local($from_lines, $to_lines);
144119
145 - // Merge edits when possible
146 - $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
147 - $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
 120+ # If external diffs are enabled both globally and for the user,
 121+ # we'll use the application/x-external-editor interface to call
 122+ # an external diff tool like kompare, kdiff3, etc.
 123+ if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) {
 124+ global $wgInputEncoding,$wgServer,$wgScript,$wgLang;
 125+ $wgOut->disable();
 126+ header ( "Content-type: application/x-external-editor; charset=".$wgInputEncoding );
 127+ $url1=$this->mTitle->getFullURL( array(
 128+ 'action' => 'raw',
 129+ 'oldid' => $this->mOldid
 130+ ) );
 131+ $url2=$this->mTitle->getFullURL( array(
 132+ 'action' => 'raw',
 133+ 'oldid' => $this->mNewid
 134+ ) );
 135+ $special=$wgLang->getNsText(NS_SPECIAL);
 136+ $control=<<<CONTROL
 137+ [Process]
 138+ Type=Diff text
 139+ Engine=MediaWiki
 140+ Script={$wgServer}{$wgScript}
 141+ Special namespace={$special}
148142
149 - // Compute the edit operations.
150 - $n_from = sizeof($from_lines);
151 - $n_to = sizeof($to_lines);
 143+ [File]
 144+ Extension=wiki
 145+ URL=$url1
152146
153 - $edits = array();
154 - $xi = $yi = 0;
155 - while ($xi < $n_from || $yi < $n_to) {
156 - assert($yi < $n_to || $this->xchanged[$xi]);
157 - assert($xi < $n_from || $this->ychanged[$yi]);
 147+ [File 2]
 148+ Extension=wiki
 149+ URL=$url2
 150+CONTROL;
 151+ echo($control);
 152+ return;
 153+ }
158154
159 - // Skip matching "snake".
160 - $copy = array();
161 - while ( $xi < $n_from && $yi < $n_to
162 - && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
163 - $copy[] = $from_lines[$xi++];
164 - ++$yi;
165 - }
166 - if ($copy)
167 - $edits[] = new _DiffOp_Copy($copy);
 155+ $wgOut->setArticleFlag( false );
 156+ if ( !$this->loadRevisionData() ) {
 157+ $t = $this->mTitle->getPrefixedText();
 158+ $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
 159+ $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
 160+ $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
 161+ wfProfileOut( __METHOD__ );
 162+ return;
 163+ }
168164
169 - // Find deletes & adds.
170 - $delete = array();
171 - while ($xi < $n_from && $this->xchanged[$xi])
172 - $delete[] = $from_lines[$xi++];
 165+ wfRunHooks( 'DiffViewHeader', array( $this, $this->mOldRev, $this->mNewRev ) );
173166
174 - $add = array();
175 - while ($yi < $n_to && $this->ychanged[$yi])
176 - $add[] = $to_lines[$yi++];
 167+ if ( $this->mNewRev->isCurrent() ) {
 168+ $wgOut->setArticleFlag( true );
 169+ }
177170
178 - if ($delete && $add)
179 - $edits[] = new _DiffOp_Change($delete, $add);
180 - elseif ($delete)
181 - $edits[] = new _DiffOp_Delete($delete);
182 - elseif ($add)
183 - $edits[] = new _DiffOp_Add($add);
 171+ # mOldid is false if the difference engine is called with a "vague" query for
 172+ # a diff between a version V and its previous version V' AND the version V
 173+ # is the first version of that article. In that case, V' does not exist.
 174+ if ( $this->mOldid === false ) {
 175+ $this->showFirstRevision();
 176+ $this->renderNewRevision(); // should we respect $diffOnly here or not?
 177+ wfProfileOut( __METHOD__ );
 178+ return;
184179 }
185 - wfProfileOut( __METHOD__ );
186 - return $edits;
187 - }
188180
189 - function diff_local ($from_lines, $to_lines) {
190 - global $wgExternalDiffEngine;
191 - wfProfileIn( __METHOD__);
 181+ $wgOut->suppressQuickbar();
192182
193 - if($wgExternalDiffEngine == 'wikidiff3'){
194 - // wikidiff3
195 - $wikidiff3 = new WikiDiff3();
196 - $wikidiff3->diff($from_lines, $to_lines);
197 - $this->xchanged = $wikidiff3->removed;
198 - $this->ychanged = $wikidiff3->added;
199 - unset($wikidiff3);
200 - }else{
201 - // old diff
202 - $n_from = sizeof($from_lines);
203 - $n_to = sizeof($to_lines);
204 - $this->xchanged = $this->ychanged = array();
205 - $this->xv = $this->yv = array();
206 - $this->xind = $this->yind = array();
207 - unset($this->seq);
208 - unset($this->in_seq);
209 - unset($this->lcs);
210 -
211 - // Skip leading common lines.
212 - for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
213 - if ($from_lines[$skip] !== $to_lines[$skip])
214 - break;
215 - $this->xchanged[$skip] = $this->ychanged[$skip] = false;
216 - }
217 - // Skip trailing common lines.
218 - $xi = $n_from; $yi = $n_to;
219 - for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
220 - if ($from_lines[$xi] !== $to_lines[$yi])
221 - break;
222 - $this->xchanged[$xi] = $this->ychanged[$yi] = false;
223 - }
224 -
225 - // Ignore lines which do not exist in both files.
226 - for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
227 - $xhash[$this->_line_hash($from_lines[$xi])] = 1;
228 - }
229 -
230 - for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
231 - $line = $to_lines[$yi];
232 - if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )
233 - continue;
234 - $yhash[$this->_line_hash($line)] = 1;
235 - $this->yv[] = $line;
236 - $this->yind[] = $yi;
237 - }
238 - for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
239 - $line = $from_lines[$xi];
240 - if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )
241 - continue;
242 - $this->xv[] = $line;
243 - $this->xind[] = $xi;
244 - }
245 -
246 - // Find the LCS.
247 - $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
 183+ $oldTitle = $this->mOldPage->getPrefixedText();
 184+ $newTitle = $this->mNewPage->getPrefixedText();
 185+ if( $oldTitle == $newTitle ) {
 186+ $wgOut->setPageTitle( $newTitle );
 187+ } else {
 188+ $wgOut->setPageTitle( $oldTitle . ', ' . $newTitle );
248189 }
249 - wfProfileOut( __METHOD__ );
250 - }
251 -
252 - /**
253 - * Returns the whole line if it's small enough, or the MD5 hash otherwise
254 - */
255 - function _line_hash( $line ) {
256 - if ( strlen( $line ) > self::MAX_XREF_LENGTH ) {
257 - return md5( $line );
 190+ if ( $this->mNewPage->equals( $this->mOldPage ) ) {
 191+ $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
258192 } else {
259 - return $line;
 193+ $wgOut->setSubtitle( wfMsgExt( 'difference-multipage', array( 'parseinline' ) ) );
260194 }
261 - }
 195+ $wgOut->setRobotPolicy( 'noindex,nofollow' );
262196
263 - /* Divide the Largest Common Subsequence (LCS) of the sequences
264 - * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
265 - * sized segments.
266 - *
267 - * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an
268 - * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
269 - * sub sequences. The first sub-sequence is contained in [X0, X1),
270 - * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note
271 - * that (X0, Y0) == (XOFF, YOFF) and
272 - * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
273 - *
274 - * This function assumes that the first lines of the specified portions
275 - * of the two files do not match, and likewise that the last lines do not
276 - * match. The caller must trim matching lines from the beginning and end
277 - * of the portions it is going to specify.
278 - */
279 - function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
280 - $flip = false;
281 -
282 - if ($xlim - $xoff > $ylim - $yoff) {
283 - // Things seems faster (I'm not sure I understand why)
284 - // when the shortest sequence in X.
285 - $flip = true;
286 - list ($xoff, $xlim, $yoff, $ylim)
287 - = array( $yoff, $ylim, $xoff, $xlim);
 197+ if ( !$this->mOldPage->userCanRead() || !$this->mNewPage->userCanRead() ) {
 198+ $wgOut->loginToUse();
 199+ $wgOut->output();
 200+ $wgOut->disable();
 201+ wfProfileOut( __METHOD__ );
 202+ return;
288203 }
289204
290 - if ($flip)
291 - for ($i = $ylim - 1; $i >= $yoff; $i--)
292 - $ymatches[$this->xv[$i]][] = $i;
293 - else
294 - for ($i = $ylim - 1; $i >= $yoff; $i--)
295 - $ymatches[$this->yv[$i]][] = $i;
 205+ $sk = $wgUser->getSkin();
296206
297 - $this->lcs = 0;
298 - $this->seq[0]= $yoff - 1;
299 - $this->in_seq = array();
300 - $ymids[0] = array();
 207+ // Check if page is editable
 208+ $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
 209+ if ( $editable && $this->mNewRev->isCurrent() && $wgUser->isAllowed( 'rollback' ) ) {
 210+ $rollback = '&#160;&#160;&#160;' . $sk->generateRollback( $this->mNewRev );
 211+ } else {
 212+ $rollback = '';
 213+ }
301214
302 - $numer = $xlim - $xoff + $nchunks - 1;
303 - $x = $xoff;
304 - for ($chunk = 0; $chunk < $nchunks; $chunk++) {
305 - if ($chunk > 0)
306 - for ($i = 0; $i <= $this->lcs; $i++)
307 - $ymids[$i][$chunk-1] = $this->seq[$i];
308 -
309 - $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
310 - for ( ; $x < $x1; $x++) {
311 - $line = $flip ? $this->yv[$x] : $this->xv[$x];
312 - if (empty($ymatches[$line])) {
313 - continue;
 215+ // Prepare a change patrol link, if applicable
 216+ if( $wgUseRCPatrol && $this->mTitle->userCan('patrol') ) {
 217+ // If we've been given an explicit change identifier, use it; saves time
 218+ if( $this->mRcidMarkPatrolled ) {
 219+ $rcid = $this->mRcidMarkPatrolled;
 220+ $rc = RecentChange::newFromId( $rcid );
 221+ // Already patrolled?
 222+ $rcid = is_object($rc) && !$rc->getAttribute('rc_patrolled') ? $rcid : 0;
 223+ } else {
 224+ // Look for an unpatrolled change corresponding to this diff
 225+ $db = wfGetDB( DB_SLAVE );
 226+ $change = RecentChange::newFromConds(
 227+ array(
 228+ // Redundant user,timestamp condition so we can use the existing index
 229+ 'rc_user_text' => $this->mNewRev->getRawUserText(),
 230+ 'rc_timestamp' => $db->timestamp( $this->mNewRev->getTimestamp() ),
 231+ 'rc_this_oldid' => $this->mNewid,
 232+ 'rc_last_oldid' => $this->mOldid,
 233+ 'rc_patrolled' => 0
 234+ ),
 235+ __METHOD__
 236+ );
 237+ if( $change instanceof RecentChange ) {
 238+ $rcid = $change->mAttribs['rc_id'];
 239+ $this->mRcidMarkPatrolled = $rcid;
 240+ } else {
 241+ // None found
 242+ $rcid = 0;
314243 }
315 - $matches = $ymatches[$line];
316 - reset($matches);
317 - while ( list( $junk, $y ) = each( $matches ) ) {
318 - if ( empty( $this->in_seq[$y] ) ) {
319 - $k = $this->_lcs_pos( $y );
320 - assert( $k > 0 );
321 - $ymids[$k] = $ymids[$k-1];
322 - break;
323 - }
324 - }
325 - while (list ( /* $junk */, $y) = each($matches)) {
326 - if ($y > $this->seq[$k-1]) {
327 - assert($y < $this->seq[$k]);
328 - // Optimization: this is a common case:
329 - // next match is just replacing previous match.
330 - $this->in_seq[$this->seq[$k]] = false;
331 - $this->seq[$k] = $y;
332 - $this->in_seq[$y] = 1;
333 - } else if (empty($this->in_seq[$y])) {
334 - $k = $this->_lcs_pos($y);
335 - assert($k > 0);
336 - $ymids[$k] = $ymids[$k-1];
337 - }
338 - }
339244 }
 245+ // Build the link
 246+ if( $rcid ) {
 247+ $token = $wgUser->editToken( $rcid );
 248+ $patrol = ' <span class="patrollink">[' . $sk->link(
 249+ $this->mTitle,
 250+ wfMsgHtml( 'markaspatrolleddiff' ),
 251+ array(),
 252+ array(
 253+ 'action' => 'markpatrolled',
 254+ 'rcid' => $rcid,
 255+ 'token' => $token,
 256+ ),
 257+ array(
 258+ 'known',
 259+ 'noclasses'
 260+ )
 261+ ) . ']</span>';
 262+ } else {
 263+ $patrol = '';
 264+ }
 265+ } else {
 266+ $patrol = '';
340267 }
341268
342 - $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
343 - $ymid = $ymids[$this->lcs];
344 - for ($n = 0; $n < $nchunks - 1; $n++) {
345 - $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
346 - $y1 = $ymid[$n] + 1;
347 - $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
 269+ # Carry over 'diffonly' param via navigation links
 270+ if( $diffOnly != $wgUser->getBoolOption('diffonly') ) {
 271+ $query['diffonly'] = $diffOnly;
348272 }
349 - $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
350273
351 - return array($this->lcs, $seps);
352 - }
353 -
354 - function _lcs_pos ($ypos) {
355 - $end = $this->lcs;
356 - if ($end == 0 || $ypos > $this->seq[$end]) {
357 - $this->seq[++$this->lcs] = $ypos;
358 - $this->in_seq[$ypos] = 1;
359 - return $this->lcs;
 274+ # Make "previous revision link"
 275+ $query['diff'] = 'prev';
 276+ $query['oldid'] = $this->mOldid;
 277+ # Cascade unhide param in links for easy deletion browsing
 278+ if( $this->unhide ) {
 279+ $query['unhide'] = 1;
360280 }
 281+ if( !$this->mOldRev->getPrevious() ) {
 282+ $prevlink = '&#160;';
 283+ } else {
 284+ $prevlink = $sk->link(
 285+ $this->mTitle,
 286+ wfMsgHtml( 'previousdiff' ),
 287+ array(
 288+ 'id' => 'differences-prevlink'
 289+ ),
 290+ $query,
 291+ array(
 292+ 'known',
 293+ 'noclasses'
 294+ )
 295+ );
 296+ }
361297
362 - $beg = 1;
363 - while ($beg < $end) {
364 - $mid = (int)(($beg + $end) / 2);
365 - if ( $ypos > $this->seq[$mid] )
366 - $beg = $mid + 1;
367 - else
368 - $end = $mid;
 298+ # Make "next revision link"
 299+ $query['diff'] = 'next';
 300+ $query['oldid'] = $this->mNewid;
 301+ # Skip next link on the top revision
 302+ if( $this->mNewRev->isCurrent() ) {
 303+ $nextlink = '&#160;';
 304+ } else {
 305+ $nextlink = $sk->link(
 306+ $this->mTitle,
 307+ wfMsgHtml( 'nextdiff' ),
 308+ array(
 309+ 'id' => 'differences-nextlink'
 310+ ),
 311+ $query,
 312+ array(
 313+ 'known',
 314+ 'noclasses'
 315+ )
 316+ );
369317 }
370318
371 - assert($ypos != $this->seq[$end]);
 319+ $oldminor = '';
 320+ $newminor = '';
372321
373 - $this->in_seq[$this->seq[$end]] = false;
374 - $this->seq[$end] = $ypos;
375 - $this->in_seq[$ypos] = 1;
376 - return $end;
377 - }
378 -
379 - /* Find LCS of two sequences.
380 - *
381 - * The results are recorded in the vectors $this->{x,y}changed[], by
382 - * storing a 1 in the element for each line that is an insertion
383 - * or deletion (ie. is not in the LCS).
384 - *
385 - * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
386 - *
387 - * Note that XLIM, YLIM are exclusive bounds.
388 - * All line numbers are origin-0 and discarded lines are not counted.
389 - */
390 - function _compareseq ($xoff, $xlim, $yoff, $ylim) {
391 - // Slide down the bottom initial diagonal.
392 - while ($xoff < $xlim && $yoff < $ylim
393 - && $this->xv[$xoff] == $this->yv[$yoff]) {
394 - ++$xoff;
395 - ++$yoff;
 322+ if( $this->mOldRev->isMinor() ) {
 323+ $oldminor = ChangesList::flag( 'minor' );
396324 }
397 -
398 - // Slide up the top initial diagonal.
399 - while ($xlim > $xoff && $ylim > $yoff
400 - && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
401 - --$xlim;
402 - --$ylim;
 325+ if( $this->mNewRev->isMinor() ) {
 326+ $newminor = ChangesList::flag( 'minor' );
403327 }
404328
405 - if ($xoff == $xlim || $yoff == $ylim)
406 - $lcs = 0;
407 - else {
408 - // This is ad hoc but seems to work well.
409 - //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
410 - //$nchunks = max(2,min(8,(int)$nchunks));
411 - $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
412 - list ($lcs, $seps)
413 - = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
414 - }
 329+ # Handle RevisionDelete links...
 330+ $ldel = $this->revisionDeleteLink( $this->mOldRev );
 331+ $rdel = $this->revisionDeleteLink( $this->mNewRev );
415332
416 - if ($lcs == 0) {
417 - // X and Y sequences have no common subsequence:
418 - // mark all changed.
419 - while ($yoff < $ylim)
420 - $this->ychanged[$this->yind[$yoff++]] = 1;
421 - while ($xoff < $xlim)
422 - $this->xchanged[$this->xind[$xoff++]] = 1;
 333+ $oldHeader = '<div id="mw-diff-otitle1"><strong>'.$this->mOldtitle.'</strong></div>' .
 334+ '<div id="mw-diff-otitle2">' .
 335+ $sk->revUserTools( $this->mOldRev, !$this->unhide ).'</div>' .
 336+ '<div id="mw-diff-otitle3">' . $oldminor .
 337+ $sk->revComment( $this->mOldRev, !$diffOnly, !$this->unhide ).$ldel.'</div>' .
 338+ '<div id="mw-diff-otitle4">' . $prevlink .'</div>';
 339+ $newHeader = '<div id="mw-diff-ntitle1"><strong>'.$this->mNewtitle.'</strong></div>' .
 340+ '<div id="mw-diff-ntitle2">' . $sk->revUserTools( $this->mNewRev, !$this->unhide ) .
 341+ " $rollback</div>" .
 342+ '<div id="mw-diff-ntitle3">' . $newminor .
 343+ $sk->revComment( $this->mNewRev, !$diffOnly, !$this->unhide ).$rdel.'</div>' .
 344+ '<div id="mw-diff-ntitle4">' . $nextlink . $patrol . '</div>';
 345+
 346+ # Check if this user can see the revisions
 347+ $allowed = $this->mOldRev->userCan(Revision::DELETED_TEXT)
 348+ && $this->mNewRev->userCan(Revision::DELETED_TEXT);
 349+ # Check if one of the revisions is deleted/suppressed
 350+ $deleted = $suppressed = false;
 351+ if( $this->mOldRev->isDeleted(Revision::DELETED_TEXT) ) {
 352+ $deleted = true; // old revisions text is hidden
 353+ if( $this->mOldRev->isDeleted(Revision::DELETED_RESTRICTED) )
 354+ $suppressed = true; // also suppressed
 355+ }
 356+ if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
 357+ $deleted = true; // new revisions text is hidden
 358+ if( $this->mNewRev->isDeleted(Revision::DELETED_RESTRICTED) )
 359+ $suppressed = true; // also suppressed
 360+ }
 361+ # If the diff cannot be shown due to a deleted revision, then output
 362+ # the diff header and links to unhide (if available)...
 363+ if( $deleted && (!$this->unhide || !$allowed) ) {
 364+ $this->showDiffStyle();
 365+ $multi = $this->getMultiNotice();
 366+ $wgOut->addHTML( $this->addHeader( '', $oldHeader, $newHeader, $multi ) );
 367+ if( !$allowed ) {
 368+ $msg = $suppressed ? 'rev-suppressed-no-diff' : 'rev-deleted-no-diff';
 369+ # Give explanation for why revision is not visible
 370+ $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n",
 371+ array( $msg ) );
 372+ } else {
 373+ # Give explanation and add a link to view the diff...
 374+ $link = $this->mTitle->getFullUrl( array(
 375+ 'diff' => $this->mNewid,
 376+ 'oldid' => $this->mOldid,
 377+ 'unhide' => 1
 378+ ) );
 379+ $msg = $suppressed ? 'rev-suppressed-unhide-diff' : 'rev-deleted-unhide-diff';
 380+ $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", array( $msg, $link ) );
 381+ }
 382+ # Otherwise, output a regular diff...
423383 } else {
424 - // Use the partitions to split this problem into subproblems.
425 - reset($seps);
426 - $pt1 = $seps[0];
427 - while ($pt2 = next($seps)) {
428 - $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
429 - $pt1 = $pt2;
 384+ # Add deletion notice if the user is viewing deleted content
 385+ $notice = '';
 386+ if( $deleted ) {
 387+ $msg = $suppressed ? 'rev-suppressed-diff-view' : 'rev-deleted-diff-view';
 388+ $notice = "<div class='mw-warning plainlinks'>\n".wfMsgExt($msg,'parseinline')."</div>\n";
430389 }
 390+ $this->showDiff( $oldHeader, $newHeader, $notice );
 391+ if( !$diffOnly ) {
 392+ $this->renderNewRevision();
 393+ }
431394 }
 395+ wfProfileOut( __METHOD__ );
432396 }
 397+
 398+ protected function revisionDeleteLink( $rev ) {
 399+ global $wgUser;
 400+ $link = '';
 401+ $canHide = $wgUser->isAllowed( 'deleterevision' );
 402+ // Show del/undel link if:
 403+ // (a) the user can delete revisions, or
 404+ // (b) the user can view deleted revision *and* this one is deleted
 405+ if( $canHide || ($rev->getVisibility() && $wgUser->isAllowed( 'deletedhistory' )) ) {
 406+ $sk = $wgUser->getSkin();
 407+ if( !$rev->userCan( Revision::DELETED_RESTRICTED ) ) {
 408+ $link = $sk->revDeleteLinkDisabled( $canHide ); // revision was hidden from sysops
 409+ } else {
 410+ $query = array(
 411+ 'type' => 'revision',
 412+ 'target' => $rev->mTitle->getPrefixedDbkey(),
 413+ 'ids' => $rev->getId()
 414+ );
 415+ $link = $sk->revDeleteLink( $query,
 416+ $rev->isDeleted( Revision::DELETED_RESTRICTED ), $canHide );
 417+ }
 418+ $link = '&#160;&#160;&#160;' . $link . ' ';
 419+ }
 420+ return $link;
 421+ }
433422
434 - /* Adjust inserts/deletes of identical lines to join changes
435 - * as much as possible.
436 - *
437 - * We do something when a run of changed lines include a
438 - * line at one end and has an excluded, identical line at the other.
439 - * We are free to choose which identical line is included.
440 - * `compareseq' usually chooses the one at the beginning,
441 - * but usually it is cleaner to consider the following identical line
442 - * to be the "change".
443 - *
444 - * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 423+ /**
 424+ * Show the new revision of the page.
445425 */
446 - function _shift_boundaries ($lines, &$changed, $other_changed) {
 426+ function renderNewRevision() {
 427+ global $wgOut, $wgUser;
447428 wfProfileIn( __METHOD__ );
448 - $i = 0;
449 - $j = 0;
450429
451 - assert('sizeof($lines) == sizeof($changed)');
452 - $len = sizeof($lines);
453 - $other_len = sizeof($other_changed);
 430+ $wgOut->addHTML( "<hr /><h2>{$this->mPagetitle}</h2>\n" );
 431+ # Add deleted rev tag if needed
 432+ if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 433+ $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", 'rev-deleted-text-permission' );
 434+ } else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
 435+ $wgOut->wrapWikiMsg( "<div class='mw-warning plainlinks'>\n$1\n</div>\n", 'rev-deleted-text-view' );
 436+ }
454437
455 - while (1) {
456 - /*
457 - * Scan forwards to find beginning of another run of changes.
458 - * Also keep track of the corresponding point in the other file.
459 - *
460 - * Throughout this code, $i and $j are adjusted together so that
461 - * the first $i elements of $changed and the first $j elements
462 - * of $other_changed both contain the same number of zeros
463 - * (unchanged lines).
464 - * Furthermore, $j is always kept so that $j == $other_len or
465 - * $other_changed[$j] == false.
466 - */
467 - while ($j < $other_len && $other_changed[$j])
468 - $j++;
 438+ $pCache = true;
 439+ if( !$this->mNewRev->isCurrent() ) {
 440+ $oldEditSectionSetting = $wgOut->parserOptions()->setEditSection( false );
 441+ $pCache = false;
 442+ }
469443
470 - while ($i < $len && ! $changed[$i]) {
471 - assert('$j < $other_len && ! $other_changed[$j]');
472 - $i++; $j++;
473 - while ($j < $other_len && $other_changed[$j])
474 - $j++;
 444+ $this->loadNewText();
 445+ if( is_object( $this->mNewRev ) ) {
 446+ $wgOut->setRevisionId( $this->mNewRev->getId() );
 447+ }
 448+
 449+ if( $this->mTitle->isCssJsSubpage() || $this->mTitle->isCssOrJsPage() ) {
 450+ // Stolen from Article::view --AG 2007-10-11
 451+ // Give hooks a chance to customise the output
 452+ if( wfRunHooks( 'ShowRawCssJs', array( $this->mNewtext, $this->mTitle, $wgOut ) ) ) {
 453+ // Wrap the whole lot in a <pre> and don't parse
 454+ $m = array();
 455+ preg_match( '!\.(css|js)$!u', $this->mTitle->getText(), $m );
 456+ $wgOut->addHTML( "<pre class=\"mw-code mw-{$m[1]}\" dir=\"ltr\">\n" );
 457+ $wgOut->addHTML( htmlspecialchars( $this->mNewtext ) );
 458+ $wgOut->addHTML( "\n</pre>\n" );
475459 }
 460+ } elseif( wfRunHooks( 'ArticleContentOnDiff', array( $this, $wgOut ) ) ) {
 461+ if ( $pCache ) {
 462+ $article = new Article( $this->mTitle, 0 );
 463+ $pOutput = ParserCache::singleton()->get( $article, $wgOut->parserOptions() );
 464+ if( $pOutput ) {
 465+ $wgOut->addParserOutput( $pOutput );
 466+ } else {
 467+ $article->doViewParse();
 468+ }
 469+ } else {
 470+ $wgOut->addWikiTextTidy( $this->mNewtext );
 471+ }
 472+ }
 473+
 474+ if( is_object( $this->mNewRev ) && !$this->mNewRev->isCurrent() ) {
 475+ $wgOut->parserOptions()->setEditSection( $oldEditSectionSetting );
 476+ }
476477
477 - if ($i == $len)
478 - break;
 478+ # Add redundant patrol link on bottom...
 479+ if( $this->mRcidMarkPatrolled && $this->mTitle->quickUserCan('patrol') ) {
 480+ $sk = $wgUser->getSkin();
 481+ $token = $wgUser->editToken( $this->mRcidMarkPatrolled );
 482+ $wgOut->addHTML(
 483+ "<div class='patrollink'>[" . $sk->link(
 484+ $this->mTitle,
 485+ wfMsgHtml( 'markaspatrolleddiff' ),
 486+ array(),
 487+ array(
 488+ 'action' => 'markpatrolled',
 489+ 'rcid' => $this->mRcidMarkPatrolled,
 490+ 'token' => $token,
 491+ )
 492+ ) . ']</div>'
 493+ );
 494+ }
479495
480 - $start = $i;
 496+ wfProfileOut( __METHOD__ );
 497+ }
481498
482 - // Find the end of this run of changes.
483 - while (++$i < $len && $changed[$i])
484 - continue;
 499+ /**
 500+ * Show the first revision of an article. Uses normal diff headers in
 501+ * contrast to normal "old revision" display style.
 502+ */
 503+ function showFirstRevision() {
 504+ global $wgOut, $wgUser;
 505+ wfProfileIn( __METHOD__ );
485506
486 - do {
487 - /*
488 - * Record the length of this run of changes, so that
489 - * we can later determine whether the run has grown.
490 - */
491 - $runlength = $i - $start;
 507+ # Get article text from the DB
 508+ #
 509+ if ( ! $this->loadNewText() ) {
 510+ $t = $this->mTitle->getPrefixedText();
 511+ $d = wfMsgExt( 'missingarticle-diff', array( 'escape' ), $this->mOldid, $this->mNewid );
 512+ $wgOut->setPagetitle( wfMsg( 'errorpagetitle' ) );
 513+ $wgOut->addWikiMsg( 'missing-article', "<nowiki>$t</nowiki>", $d );
 514+ wfProfileOut( __METHOD__ );
 515+ return;
 516+ }
 517+ if ( $this->mNewRev->isCurrent() ) {
 518+ $wgOut->setArticleFlag( true );
 519+ }
492520
493 - /*
494 - * Move the changed region back, so long as the
495 - * previous unchanged line matches the last changed one.
496 - * This merges with previous changed regions.
497 - */
498 - while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
499 - $changed[--$start] = 1;
500 - $changed[--$i] = false;
501 - while ($start > 0 && $changed[$start - 1])
502 - $start--;
503 - assert('$j > 0');
504 - while ($other_changed[--$j])
505 - continue;
506 - assert('$j >= 0 && !$other_changed[$j]');
507 - }
 521+ # Check if user is allowed to look at this page. If not, bail out.
 522+ #
 523+ if ( !$this->mTitle->userCanRead() ) {
 524+ $wgOut->loginToUse();
 525+ $wgOut->output();
 526+ wfProfileOut( __METHOD__ );
 527+ throw new MWException("Permission Error: you do not have access to view this page");
 528+ }
508529
509 - /*
510 - * Set CORRESPONDING to the end of the changed run, at the last
511 - * point where it corresponds to a changed run in the other file.
512 - * CORRESPONDING == LEN means no such point has been found.
513 - */
514 - $corresponding = $j < $other_len ? $i : $len;
 530+ # Prepare the header box
 531+ #
 532+ $sk = $wgUser->getSkin();
515533
516 - /*
517 - * Move the changed region forward, so long as the
518 - * first changed line matches the following unchanged one.
519 - * This merges with following changed regions.
520 - * Do this second, so that if there are no merges,
521 - * the changed region is moved forward as far as possible.
522 - */
523 - while ($i < $len && $lines[$start] == $lines[$i]) {
524 - $changed[$start++] = false;
525 - $changed[$i++] = 1;
526 - while ($i < $len && $changed[$i])
527 - $i++;
 534+ $next = $this->mTitle->getNextRevisionID( $this->mNewid );
 535+ if( !$next ) {
 536+ $nextlink = '';
 537+ } else {
 538+ $nextlink = '<br />' . $sk->link(
 539+ $this->mTitle,
 540+ wfMsgHtml( 'nextdiff' ),
 541+ array(
 542+ 'id' => 'differences-nextlink'
 543+ ),
 544+ array(
 545+ 'diff' => 'next',
 546+ 'oldid' => $this->mNewid,
 547+ ),
 548+ array(
 549+ 'known',
 550+ 'noclasses'
 551+ )
 552+ );
 553+ }
 554+ $header = "<div class=\"firstrevisionheader\" style=\"text-align: center\">" .
 555+ $sk->revUserTools( $this->mNewRev ) . "<br />" . $sk->revComment( $this->mNewRev ) . $nextlink . "</div>\n";
528556
529 - assert('$j < $other_len && ! $other_changed[$j]');
530 - $j++;
531 - if ($j < $other_len && $other_changed[$j]) {
532 - $corresponding = $i;
533 - while ($j < $other_len && $other_changed[$j])
534 - $j++;
535 - }
536 - }
537 - } while ($runlength != $i - $start);
 557+ $wgOut->addHTML( $header );
538558
539 - /*
540 - * If possible, move the fully-merged run of changes
541 - * back to a corresponding run in the other file.
542 - */
543 - while ($corresponding < $i) {
544 - $changed[--$start] = 1;
545 - $changed[--$i] = 0;
546 - assert('$j > 0');
547 - while ($other_changed[--$j])
548 - continue;
549 - assert('$j >= 0 && !$other_changed[$j]');
550 - }
551 - }
 559+ $wgOut->setSubtitle( wfMsgExt( 'difference', array( 'parseinline' ) ) );
 560+ $wgOut->setRobotPolicy( 'noindex,nofollow' );
 561+
552562 wfProfileOut( __METHOD__ );
553563 }
554 -}
555564
556 -/**
557 - * Class representing a 'diff' between two sequences of strings.
558 - * @todo document
559 - * @private
560 - * @ingroup DifferenceEngine
561 - */
562 -class Diff
563 -{
564 - var $edits;
565 -
566565 /**
567 - * Constructor.
568 - * Computes diff between sequences of strings.
569 - *
570 - * @param $from_lines array An array of strings.
571 - * (Typically these are lines from a file.)
572 - * @param $to_lines array An array of strings.
 566+ * Get the diff text, send it to $wgOut
 567+ * Returns false if the diff could not be generated, otherwise returns true
573568 */
574 - function __construct($from_lines, $to_lines) {
575 - $eng = new _DiffEngine;
576 - $this->edits = $eng->diff($from_lines, $to_lines);
577 - //$this->_check($from_lines, $to_lines);
 569+ function showDiff( $otitle, $ntitle, $notice = '' ) {
 570+ global $wgOut;
 571+ $diff = $this->getDiff( $otitle, $ntitle, $notice );
 572+ if ( $diff === false ) {
 573+ $wgOut->addWikiMsg( 'missing-article', "<nowiki>(fixme, bug)</nowiki>", '' );
 574+ return false;
 575+ } else {
 576+ $this->showDiffStyle();
 577+ $wgOut->addHTML( $diff );
 578+ return true;
 579+ }
578580 }
579581
580582 /**
581 - * Compute reversed Diff.
582 - *
583 - * SYNOPSIS:
584 - *
585 - * $diff = new Diff($lines1, $lines2);
586 - * $rev = $diff->reverse();
587 - * @return object A Diff object representing the inverse of the
588 - * original diff.
 583+ * Add style sheets and supporting JS for diff display.
589584 */
590 - function reverse () {
591 - $rev = $this;
592 - $rev->edits = array();
593 - foreach ($this->edits as $edit) {
594 - $rev->edits[] = $edit->reverse();
595 - }
596 - return $rev;
 585+ function showDiffStyle() {
 586+ global $wgOut;
 587+ $wgOut->addModules( 'mediawiki.legacy.diff' );
597588 }
598589
599590 /**
600 - * Check for empty diff.
 591+ * Get complete diff table, including header
601592 *
602 - * @return bool True iff two sequences were identical.
 593+ * @param $otitle Title: old title
 594+ * @param $ntitle Title: new title
 595+ * @param $notice String: HTML between diff header and body
 596+ * @return mixed
603597 */
604 - function isEmpty () {
605 - foreach ($this->edits as $edit) {
606 - if ($edit->type != 'copy')
 598+ function getDiff( $otitle, $ntitle, $notice = '' ) {
 599+ $body = $this->getDiffBody();
 600+ if ( $body === false ) {
607601 return false;
 602+ } else {
 603+ $multi = $this->getMultiNotice();
 604+ return $this->addHeader( $body, $otitle, $ntitle, $multi, $notice );
608605 }
609 - return true;
610606 }
611607
612608 /**
613 - * Compute the length of the Longest Common Subsequence (LCS).
 609+ * Get the diff table body, without header
614610 *
615 - * This is mostly for diagnostic purposed.
616 - *
617 - * @return int The length of the LCS.
 611+ * @return mixed
618612 */
619 - function lcs () {
620 - $lcs = 0;
621 - foreach ($this->edits as $edit) {
622 - if ($edit->type == 'copy')
623 - $lcs += sizeof($edit->orig);
 613+ function getDiffBody() {
 614+ global $wgMemc;
 615+ wfProfileIn( __METHOD__ );
 616+ $this->mCacheHit = true;
 617+ // Check if the diff should be hidden from this user
 618+ if ( !$this->loadRevisionData() )
 619+ return '';
 620+ if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) {
 621+ return '';
 622+ } else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 623+ return '';
 624+ } else if ( $this->mOldRev && $this->mNewRev && $this->mOldRev->getID() == $this->mNewRev->getID() ) {
 625+ return '';
624626 }
625 - return $lcs;
626 - }
627 -
628 - /**
629 - * Get the original set of lines.
630 - *
631 - * This reconstructs the $from_lines parameter passed to the
632 - * constructor.
633 - *
634 - * @return array The original sequence of strings.
635 - */
636 - function orig() {
637 - $lines = array();
638 -
639 - foreach ($this->edits as $edit) {
640 - if ($edit->orig)
641 - array_splice($lines, sizeof($lines), 0, $edit->orig);
 627+ // Cacheable?
 628+ $key = false;
 629+ if ( $this->mOldid && $this->mNewid ) {
 630+ $key = wfMemcKey( 'diff', 'version', MW_DIFF_VERSION, 'oldid', $this->mOldid, 'newid', $this->mNewid );
 631+ // Try cache
 632+ if ( !$this->mRefreshCache ) {
 633+ $difftext = $wgMemc->get( $key );
 634+ if ( $difftext ) {
 635+ wfIncrStats( 'diff_cache_hit' );
 636+ $difftext = $this->localiseLineNumbers( $difftext );
 637+ $difftext .= "\n<!-- diff cache key $key -->\n";
 638+ wfProfileOut( __METHOD__ );
 639+ return $difftext;
 640+ }
 641+ } // don't try to load but save the result
642642 }
643 - return $lines;
644 - }
 643+ $this->mCacheHit = false;
645644
646 - /**
647 - * Get the closing set of lines.
648 - *
649 - * This reconstructs the $to_lines parameter passed to the
650 - * constructor.
651 - *
652 - * @return array The sequence of strings.
653 - */
654 - function closing() {
655 - $lines = array();
656 -
657 - foreach ($this->edits as $edit) {
658 - if ($edit->closing)
659 - array_splice($lines, sizeof($lines), 0, $edit->closing);
 645+ // Loadtext is permission safe, this just clears out the diff
 646+ if ( !$this->loadText() ) {
 647+ wfProfileOut( __METHOD__ );
 648+ return false;
660649 }
661 - return $lines;
662 - }
663650
664 - /**
665 - * Check a Diff for validity.
666 - *
667 - * This is here only for debugging purposes.
668 - */
669 - function _check ($from_lines, $to_lines) {
670 - wfProfileIn( __METHOD__ );
671 - if (serialize($from_lines) != serialize($this->orig()))
672 - trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
673 - if (serialize($to_lines) != serialize($this->closing()))
674 - trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
 651+ $difftext = $this->generateDiffBody( $this->mOldtext, $this->mNewtext );
675652
676 - $rev = $this->reverse();
677 - if (serialize($to_lines) != serialize($rev->orig()))
678 - trigger_error("Reversed original doesn't match", E_USER_ERROR);
679 - if (serialize($from_lines) != serialize($rev->closing()))
680 - trigger_error("Reversed closing doesn't match", E_USER_ERROR);
681 -
682 -
683 - $prevtype = 'none';
684 - foreach ($this->edits as $edit) {
685 - if ( $prevtype == $edit->type )
686 - trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
687 - $prevtype = $edit->type;
 653+ // Save to cache for 7 days
 654+ if ( !wfRunHooks( 'AbortDiffCache', array( &$this ) ) ) {
 655+ wfIncrStats( 'diff_uncacheable' );
 656+ } else if ( $key !== false && $difftext !== false ) {
 657+ wfIncrStats( 'diff_cache_miss' );
 658+ $wgMemc->set( $key, $difftext, 7*86400 );
 659+ } else {
 660+ wfIncrStats( 'diff_uncacheable' );
688661 }
689 -
690 - $lcs = $this->lcs();
691 - trigger_error('Diff okay: LCS = '.$lcs, E_USER_NOTICE);
 662+ // Replace line numbers with the text in the user's language
 663+ if ( $difftext !== false ) {
 664+ $difftext = $this->localiseLineNumbers( $difftext );
 665+ }
692666 wfProfileOut( __METHOD__ );
 667+ return $difftext;
693668 }
694 -}
695669
696 -/**
697 - * @todo document, bad name.
698 - * @private
699 - * @ingroup DifferenceEngine
700 - */
701 -class MappedDiff extends Diff
702 -{
703670 /**
704 - * Constructor.
705 - *
706 - * Computes diff between sequences of strings.
707 - *
708 - * This can be used to compute things like
709 - * case-insensitve diffs, or diffs which ignore
710 - * changes in white-space.
711 - *
712 - * @param $from_lines array An array of strings.
713 - * (Typically these are lines from a file.)
714 - *
715 - * @param $to_lines array An array of strings.
716 - *
717 - * @param $mapped_from_lines array This array should
718 - * have the same size number of elements as $from_lines.
719 - * The elements in $mapped_from_lines and
720 - * $mapped_to_lines are what is actually compared
721 - * when computing the diff.
722 - *
723 - * @param $mapped_to_lines array This array should
724 - * have the same number of elements as $to_lines.
 671+ * Make sure the proper modules are loaded before we try to
 672+ * make the diff
725673 */
726 - function __construct($from_lines, $to_lines,
727 - $mapped_from_lines, $mapped_to_lines) {
728 - wfProfileIn( __METHOD__ );
729 -
730 - assert(sizeof($from_lines) == sizeof($mapped_from_lines));
731 - assert(sizeof($to_lines) == sizeof($mapped_to_lines));
732 -
733 - parent::__construct($mapped_from_lines, $mapped_to_lines);
734 -
735 - $xi = $yi = 0;
736 - for ($i = 0; $i < sizeof($this->edits); $i++) {
737 - $orig = &$this->edits[$i]->orig;
738 - if (is_array($orig)) {
739 - $orig = array_slice($from_lines, $xi, sizeof($orig));
740 - $xi += sizeof($orig);
741 - }
742 -
743 - $closing = &$this->edits[$i]->closing;
744 - if (is_array($closing)) {
745 - $closing = array_slice($to_lines, $yi, sizeof($closing));
746 - $yi += sizeof($closing);
747 - }
 674+ private function initDiffEngines() {
 675+ global $wgExternalDiffEngine;
 676+ if ( $wgExternalDiffEngine == 'wikidiff' && !function_exists( 'wikidiff_do_diff' ) ) {
 677+ wfProfileIn( __METHOD__ . '-php_wikidiff.so' );
 678+ wfSuppressWarnings();
 679+ dl( 'php_wikidiff.so' );
 680+ wfRestoreWarnings();
 681+ wfProfileOut( __METHOD__ . '-php_wikidiff.so' );
748682 }
749 - wfProfileOut( __METHOD__ );
 683+ else if ( $wgExternalDiffEngine == 'wikidiff2' && !function_exists( 'wikidiff2_do_diff' ) ) {
 684+ wfProfileIn( __METHOD__ . '-php_wikidiff2.so' );
 685+ wfSuppressWarnings();
 686+ wfDl( 'wikidiff2' );
 687+ wfRestoreWarnings();
 688+ wfProfileOut( __METHOD__ . '-php_wikidiff2.so' );
 689+ }
750690 }
751 -}
752691
753 -/**
754 - * A class to format Diffs
755 - *
756 - * This class formats the diff in classic diff format.
757 - * It is intended that this class be customized via inheritance,
758 - * to obtain fancier outputs.
759 - * @todo document
760 - * @private
761 - * @ingroup DifferenceEngine
762 - */
763 -class DiffFormatter {
764692 /**
765 - * Number of leading context "lines" to preserve.
 693+ * Generate a diff, no caching
766694 *
767 - * This should be left at zero for this class, but subclasses
768 - * may want to set this to other values.
 695+ * @param $otext String: old text, must be already segmented
 696+ * @param $ntext String: new text, must be already segmented
769697 */
770 - var $leading_context_lines = 0;
 698+ function generateDiffBody( $otext, $ntext ) {
 699+ global $wgExternalDiffEngine, $wgContLang;
771700
772 - /**
773 - * Number of trailing context "lines" to preserve.
774 - *
775 - * This should be left at zero for this class, but subclasses
776 - * may want to set this to other values.
777 - */
778 - var $trailing_context_lines = 0;
 701+ $otext = str_replace( "\r\n", "\n", $otext );
 702+ $ntext = str_replace( "\r\n", "\n", $ntext );
779703
780 - /**
781 - * Format a diff.
782 - *
783 - * @param $diff object A Diff object.
784 - * @return string The formatted output.
785 - */
786 - function format($diff) {
787 - wfProfileIn( __METHOD__ );
 704+ $this->initDiffEngines();
788705
789 - $xi = $yi = 1;
790 - $block = false;
791 - $context = array();
 706+ if ( $wgExternalDiffEngine == 'wikidiff' && function_exists( 'wikidiff_do_diff' ) ) {
 707+ # For historical reasons, external diff engine expects
 708+ # input text to be HTML-escaped already
 709+ $otext = htmlspecialchars ( $wgContLang->segmentForDiff( $otext ) );
 710+ $ntext = htmlspecialchars ( $wgContLang->segmentForDiff( $ntext ) );
 711+ return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) .
 712+ $this->debug( 'wikidiff1' );
 713+ }
792714
793 - $nlead = $this->leading_context_lines;
794 - $ntrail = $this->trailing_context_lines;
 715+ if ( $wgExternalDiffEngine == 'wikidiff2' && function_exists( 'wikidiff2_do_diff' ) ) {
 716+ # Better external diff engine, the 2 may some day be dropped
 717+ # This one does the escaping and segmenting itself
 718+ wfProfileIn( 'wikidiff2_do_diff' );
 719+ $text = wikidiff2_do_diff( $otext, $ntext, 2 );
 720+ $text .= $this->debug( 'wikidiff2' );
 721+ wfProfileOut( 'wikidiff2_do_diff' );
 722+ return $text;
 723+ }
 724+ if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) {
 725+ # Diff via the shell
 726+ global $wgTmpDirectory;
 727+ $tempName1 = tempnam( $wgTmpDirectory, 'diff_' );
 728+ $tempName2 = tempnam( $wgTmpDirectory, 'diff_' );
795729
796 - $this->_start_diff();
797 -
798 - foreach ($diff->edits as $edit) {
799 - if ($edit->type == 'copy') {
800 - if (is_array($block)) {
801 - if (sizeof($edit->orig) <= $nlead + $ntrail) {
802 - $block[] = $edit;
803 - }
804 - else{
805 - if ($ntrail) {
806 - $context = array_slice($edit->orig, 0, $ntrail);
807 - $block[] = new _DiffOp_Copy($context);
808 - }
809 - $this->_block($x0, $ntrail + $xi - $x0,
810 - $y0, $ntrail + $yi - $y0,
811 - $block);
812 - $block = false;
813 - }
814 - }
815 - $context = $edit->orig;
 730+ $tempFile1 = fopen( $tempName1, "w" );
 731+ if ( !$tempFile1 ) {
 732+ wfProfileOut( __METHOD__ );
 733+ return false;
816734 }
817 - else {
818 - if (! is_array($block)) {
819 - $context = array_slice($context, sizeof($context) - $nlead);
820 - $x0 = $xi - sizeof($context);
821 - $y0 = $yi - sizeof($context);
822 - $block = array();
823 - if ($context)
824 - $block[] = new _DiffOp_Copy($context);
825 - }
826 - $block[] = $edit;
 735+ $tempFile2 = fopen( $tempName2, "w" );
 736+ if ( !$tempFile2 ) {
 737+ wfProfileOut( __METHOD__ );
 738+ return false;
827739 }
828 -
829 - if ($edit->orig)
830 - $xi += sizeof($edit->orig);
831 - if ($edit->closing)
832 - $yi += sizeof($edit->closing);
 740+ fwrite( $tempFile1, $otext );
 741+ fwrite( $tempFile2, $ntext );
 742+ fclose( $tempFile1 );
 743+ fclose( $tempFile2 );
 744+ $cmd = wfEscapeShellArg( $wgExternalDiffEngine, $tempName1, $tempName2 );
 745+ wfProfileIn( __METHOD__ . "-shellexec" );
 746+ $difftext = wfShellExec( $cmd );
 747+ $difftext .= $this->debug( "external $wgExternalDiffEngine" );
 748+ wfProfileOut( __METHOD__ . "-shellexec" );
 749+ unlink( $tempName1 );
 750+ unlink( $tempName2 );
 751+ return $difftext;
833752 }
834753
835 - if (is_array($block))
836 - $this->_block($x0, $xi - $x0,
837 - $y0, $yi - $y0,
838 - $block);
839 -
840 - $end = $this->_end_diff();
841 - wfProfileOut( __METHOD__ );
842 - return $end;
 754+ # Native PHP diff
 755+ $ota = explode( "\n", $wgContLang->segmentForDiff( $otext ) );
 756+ $nta = explode( "\n", $wgContLang->segmentForDiff( $ntext ) );
 757+ $diffs = new Diff( $ota, $nta );
 758+ $formatter = new TableDiffFormatter();
 759+ return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) .
 760+ $this->debug();
843761 }
844762
845 - function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
846 - wfProfileIn( __METHOD__ );
847 - $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
848 - foreach ($edits as $edit) {
849 - if ($edit->type == 'copy')
850 - $this->_context($edit->orig);
851 - elseif ($edit->type == 'add')
852 - $this->_added($edit->closing);
853 - elseif ($edit->type == 'delete')
854 - $this->_deleted($edit->orig);
855 - elseif ($edit->type == 'change')
856 - $this->_changed($edit->orig, $edit->closing);
857 - else
858 - trigger_error('Unknown edit type', E_USER_ERROR);
 763+ /**
 764+ * Generate a debug comment indicating diff generating time,
 765+ * server node, and generator backend.
 766+ */
 767+ protected function debug( $generator="internal" ) {
 768+ global $wgShowHostnames;
 769+ if ( !$this->enableDebugComment ) {
 770+ return '';
859771 }
860 - $this->_end_block();
861 - wfProfileOut( __METHOD__ );
 772+ $data = array( $generator );
 773+ if( $wgShowHostnames ) {
 774+ $data[] = wfHostname();
 775+ }
 776+ $data[] = wfTimestamp( TS_DB );
 777+ return "<!-- diff generator: " .
 778+ implode( " ",
 779+ array_map(
 780+ "htmlspecialchars",
 781+ $data ) ) .
 782+ " -->\n";
862783 }
863784
864 - function _start_diff() {
865 - ob_start();
 785+ /**
 786+ * Replace line numbers with the text in the user's language
 787+ */
 788+ function localiseLineNumbers( $text ) {
 789+ return preg_replace_callback( '/<!--LINE (\d+)-->/',
 790+ array( &$this, 'localiseLineNumbersCb' ), $text );
866791 }
867792
868 - function _end_diff() {
869 - $val = ob_get_contents();
870 - ob_end_clean();
871 - return $val;
 793+ function localiseLineNumbersCb( $matches ) {
 794+ global $wgLang;
 795+ if ( $matches[1] === '1' && $this->mReducedLineNumbers ) return '';
 796+ return wfMsgExt( 'lineno', 'escape', $wgLang->formatNum( $matches[1] ) );
872797 }
873798
874 - function _block_header($xbeg, $xlen, $ybeg, $ylen) {
875 - if ($xlen > 1)
876 - $xbeg .= "," . ($xbeg + $xlen - 1);
877 - if ($ylen > 1)
878 - $ybeg .= "," . ($ybeg + $ylen - 1);
879799
880 - return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
881 - }
 800+ /**
 801+ * If there are revisions between the ones being compared, return a note saying so.
 802+ */
 803+ function getMultiNotice() {
 804+ if ( !is_object($this->mOldRev) || !is_object($this->mNewRev) )
 805+ return '';
882806
883 - function _start_block($header) {
884 - echo $header . "\n";
885 - }
 807+ if( !$this->mOldPage->equals( $this->mNewPage ) ) {
 808+ // Comparing two different pages? Count would be meaningless.
 809+ return '';
 810+ }
886811
887 - function _end_block() {
888 - }
 812+ $oldid = $this->mOldRev->getId();
 813+ $newid = $this->mNewRev->getId();
 814+ if ( $oldid > $newid ) {
 815+ $tmp = $oldid; $oldid = $newid; $newid = $tmp;
 816+ }
889817
890 - function _lines($lines, $prefix = ' ') {
891 - foreach ($lines as $line)
892 - echo "$prefix $line\n";
 818+ $n = $this->mTitle->countRevisionsBetween( $oldid, $newid );
 819+ if ( !$n ) {
 820+ return '';
 821+ } else {
 822+ global $wgLang;
 823+ $dbr = wfGetDB( DB_SLAVE );
 824+
 825+ // Actually, the limit is $limit + 1. We do this so we can detect
 826+ // if there are > 100 authors in a given revision range. If they
 827+ // are, $limit will be passed to diff-multi-manyusers for l10n.
 828+ $limit = 100;
 829+ $res = $dbr->select( 'revision', 'DISTINCT rev_user_text',
 830+ array(
 831+ 'rev_page = ' . $this->mOldRev->getPage(),
 832+ 'rev_id > ' . $this->mOldRev->getId(),
 833+ 'rev_id < ' . $this->mNewRev->getId()
 834+ ), __METHOD__,
 835+ array( 'LIMIT' => $limit + 1 )
 836+ );
 837+ $numUsers = $dbr->numRows( $res );
 838+ if( $numUsers > $limit ) {
 839+ $msg = 'diff-multi-manyusers';
 840+ $numUsers = $limit;
 841+ } else {
 842+ $msg = 'diff-multi';
 843+ }
 844+ return wfMsgExt( $msg, array( 'parseinline' ), $wgLang->formatnum( $n ),
 845+ $wgLang->formatnum( $numUsers ) );
 846+ }
893847 }
894848
895 - function _context($lines) {
896 - $this->_lines($lines);
897 - }
898849
899 - function _added($lines) {
900 - $this->_lines($lines, '>');
901 - }
902 - function _deleted($lines) {
903 - $this->_lines($lines, '<');
904 - }
 850+ /**
 851+ * Add the header to a diff body
 852+ */
 853+ static function addHeader( $diff, $otitle, $ntitle, $multi = '', $notice = '' ) {
 854+ $header = "<table class='diff'>";
 855+ if( $diff ) { // Safari/Chrome show broken output if cols not used
 856+ $header .= "
 857+ <col class='diff-marker' />
 858+ <col class='diff-content' />
 859+ <col class='diff-marker' />
 860+ <col class='diff-content' />";
 861+ $colspan = 2;
 862+ $multiColspan = 4;
 863+ } else {
 864+ $colspan = 1;
 865+ $multiColspan = 2;
 866+ }
 867+ $header .= "
 868+ <tr valign='top'>
 869+ <td colspan='$colspan' class='diff-otitle'>{$otitle}</td>
 870+ <td colspan='$colspan' class='diff-ntitle'>{$ntitle}</td>
 871+ </tr>";
905872
906 - function _changed($orig, $closing) {
907 - $this->_deleted($orig);
908 - echo "---\n";
909 - $this->_added($closing);
910 - }
911 -}
912 -
913 -/**
914 - * A formatter that outputs unified diffs
915 - * @ingroup DifferenceEngine
916 - */
917 -
918 -class UnifiedDiffFormatter extends DiffFormatter {
919 - var $leading_context_lines = 2;
920 - var $trailing_context_lines = 2;
921 -
922 - function _added($lines) {
923 - $this->_lines($lines, '+');
924 - }
925 - function _deleted($lines) {
926 - $this->_lines($lines, '-');
927 - }
928 - function _changed($orig, $closing) {
929 - $this->_deleted($orig);
930 - $this->_added($closing);
931 - }
932 - function _block_header($xbeg, $xlen, $ybeg, $ylen) {
933 - return "@@ -$xbeg,$xlen +$ybeg,$ylen @@";
934 - }
935 -}
936 -
937 -/**
938 - * A pseudo-formatter that just passes along the Diff::$edits array
939 - * @ingroup DifferenceEngine
940 - */
941 -class ArrayDiffFormatter extends DiffFormatter {
942 - function format($diff) {
943 - $oldline = 1;
944 - $newline = 1;
945 - $retval = array();
946 - foreach($diff->edits as $edit)
947 - switch($edit->type) {
948 - case 'add':
949 - foreach($edit->closing as $l) {
950 - $retval[] = array(
951 - 'action' => 'add',
952 - 'new'=> $l,
953 - 'newline' => $newline++
954 - );
955 - }
956 - break;
957 - case 'delete':
958 - foreach($edit->orig as $l) {
959 - $retval[] = array(
960 - 'action' => 'delete',
961 - 'old' => $l,
962 - 'oldline' => $oldline++,
963 - );
964 - }
965 - break;
966 - case 'change':
967 - foreach($edit->orig as $i => $l) {
968 - $retval[] = array(
969 - 'action' => 'change',
970 - 'old' => $l,
971 - 'new' => @$edit->closing[$i],
972 - 'oldline' => $oldline++,
973 - 'newline' => $newline++,
974 - );
975 - }
976 - break;
977 - case 'copy':
978 - $oldline += count($edit->orig);
979 - $newline += count($edit->orig);
 873+ if ( $multi != '' ) {
 874+ $header .= "<tr><td colspan='{$multiColspan}' align='center' class='diff-multi'>{$multi}</td></tr>";
980875 }
981 - return $retval;
982 - }
983 -}
 876+ if ( $notice != '' ) {
 877+ $header .= "<tr><td colspan='{$multiColspan}' align='center'>{$notice}</td></tr>";
 878+ }
984879
985 -/**
986 - * Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
987 - *
988 - */
989 -
990 -define('NBSP', '&#160;'); // iso-8859-x non-breaking space.
991 -
992 -/**
993 - * @todo document
994 - * @private
995 - * @ingroup DifferenceEngine
996 - */
997 -class _HWLDF_WordAccumulator {
998 - function __construct () {
999 - $this->_lines = array();
1000 - $this->_line = '';
1001 - $this->_group = '';
1002 - $this->_tag = '';
 880+ return $header . $diff . "</table>";
1003881 }
1004882
1005 - function _flushGroup ($new_tag) {
1006 - if ($this->_group !== '') {
1007 - if ($this->_tag == 'ins')
1008 - $this->_line .= '<ins class="diffchange diffchange-inline">' .
1009 - htmlspecialchars ( $this->_group ) . '</ins>';
1010 - elseif ($this->_tag == 'del')
1011 - $this->_line .= '<del class="diffchange diffchange-inline">' .
1012 - htmlspecialchars ( $this->_group ) . '</del>';
1013 - else
1014 - $this->_line .= htmlspecialchars ( $this->_group );
1015 - }
1016 - $this->_group = '';
1017 - $this->_tag = $new_tag;
 883+ /**
 884+ * Use specified text instead of loading from the database
 885+ */
 886+ function setText( $oldText, $newText ) {
 887+ $this->mOldtext = $oldText;
 888+ $this->mNewtext = $newText;
 889+ $this->mTextLoaded = 2;
 890+ $this->mRevisionsLoaded = true;
1018891 }
1019892
1020 - function _flushLine ($new_tag) {
1021 - $this->_flushGroup($new_tag);
1022 - if ($this->_line != '')
1023 - array_push ( $this->_lines, $this->_line );
1024 - else
1025 - # make empty lines visible by inserting an NBSP
1026 - array_push ( $this->_lines, NBSP );
1027 - $this->_line = '';
1028 - }
1029 -
1030 - function addWords ($words, $tag = '') {
1031 - if ($tag != $this->_tag)
1032 - $this->_flushGroup($tag);
1033 -
1034 - foreach ($words as $word) {
1035 - // new-line should only come as first char of word.
1036 - if ($word == '')
1037 - continue;
1038 - if ($word[0] == "\n") {
1039 - $this->_flushLine($tag);
1040 - $word = substr($word, 1);
1041 - }
1042 - assert(!strstr($word, "\n"));
1043 - $this->_group .= $word;
 893+ /**
 894+ * Load revision metadata for the specified articles. If newid is 0, then compare
 895+ * the old article in oldid to the current article; if oldid is 0, then
 896+ * compare the current article to the immediately previous one (ignoring the
 897+ * value of newid).
 898+ *
 899+ * If oldid is false, leave the corresponding revision object set
 900+ * to false. This is impossible via ordinary user input, and is provided for
 901+ * API convenience.
 902+ */
 903+ function loadRevisionData() {
 904+ global $wgLang, $wgUser;
 905+ if ( $this->mRevisionsLoaded ) {
 906+ return true;
 907+ } else {
 908+ // Whether it succeeds or fails, we don't want to try again
 909+ $this->mRevisionsLoaded = true;
1044910 }
1045 - }
1046911
1047 - function getLines() {
1048 - $this->_flushLine('~done');
1049 - return preg_replace( '/\n/m', '', $this->_lines);
1050 - }
1051 -}
 912+ // Load the new revision object
 913+ $this->mNewRev = $this->mNewid
 914+ ? Revision::newFromId( $this->mNewid )
 915+ : Revision::newFromTitle( $this->mTitle );
 916+ if( !$this->mNewRev instanceof Revision )
 917+ return false;
1052918
1053 -/**
1054 - * @todo document
1055 - * @private
1056 - * @ingroup DifferenceEngine
1057 - */
1058 -class WordLevelDiff extends MappedDiff {
1059 - const MAX_LINE_LENGTH = 10000;
 919+ // Update the new revision ID in case it was 0 (makes life easier doing UI stuff)
 920+ $this->mNewid = $this->mNewRev->getId();
1060921
1061 - function __construct ($orig_lines, $closing_lines) {
1062 - wfProfileIn( __METHOD__ );
 922+ // Check if page is editable
 923+ $editable = $this->mNewRev->getTitle()->userCan( 'edit' );
1063924
1064 - list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
1065 - list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
 925+ // Set assorted variables
 926+ $timestamp = $wgLang->timeanddate( $this->mNewRev->getTimestamp(), true );
 927+ $dateofrev = $wgLang->date( $this->mNewRev->getTimestamp(), true );
 928+ $timeofrev = $wgLang->time( $this->mNewRev->getTimestamp(), true );
 929+ $this->mNewPage = $this->mNewRev->getTitle();
 930+ if( $this->mNewRev->isCurrent() ) {
 931+ $newLink = $this->mNewPage->escapeLocalUrl( array(
 932+ 'oldid' => $this->mNewid
 933+ ) );
 934+ $this->mPagetitle = htmlspecialchars( wfMsg(
 935+ 'currentrev-asof',
 936+ $timestamp,
 937+ $dateofrev,
 938+ $timeofrev
 939+ ) );
 940+ $newEdit = $this->mNewPage->escapeLocalUrl( array(
 941+ 'action' => 'edit'
 942+ ) );
1066943
1067 - parent::__construct($orig_words, $closing_words,
1068 - $orig_stripped, $closing_stripped);
1069 - wfProfileOut( __METHOD__ );
1070 - }
 944+ $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
 945+ $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
 946+ } else {
 947+ $newLink = $this->mNewPage->escapeLocalUrl( array(
 948+ 'oldid' => $this->mNewid
 949+ ) );
 950+ $newEdit = $this->mNewPage->escapeLocalUrl( array(
 951+ 'action' => 'edit',
 952+ 'oldid' => $this->mNewid
 953+ ) );
 954+ $this->mPagetitle = htmlspecialchars( wfMsg(
 955+ 'revisionasof',
 956+ $timestamp,
 957+ $dateofrev,
 958+ $timeofrev
 959+ ) );
1071960
1072 - function _split($lines) {
1073 - wfProfileIn( __METHOD__ );
 961+ $this->mNewtitle = "<a href='$newLink'>{$this->mPagetitle}</a>";
 962+ $this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
 963+ }
 964+ if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
 965+ $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";
 966+ } else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
 967+ $this->mNewtitle = "<span class='history-deleted'>{$this->mNewtitle}</span>";
 968+ }
1074969
1075 - $words = array();
1076 - $stripped = array();
1077 - $first = true;
1078 - foreach ( $lines as $line ) {
1079 - # If the line is too long, just pretend the entire line is one big word
1080 - # This prevents resource exhaustion problems
1081 - if ( $first ) {
1082 - $first = false;
 970+ // Load the old revision object
 971+ $this->mOldRev = false;
 972+ if( $this->mOldid ) {
 973+ $this->mOldRev = Revision::newFromId( $this->mOldid );
 974+ } elseif ( $this->mOldid === 0 ) {
 975+ $rev = $this->mNewRev->getPrevious();
 976+ if( $rev ) {
 977+ $this->mOldid = $rev->getId();
 978+ $this->mOldRev = $rev;
1083979 } else {
1084 - $words[] = "\n";
1085 - $stripped[] = "\n";
 980+ // No previous revision; mark to show as first-version only.
 981+ $this->mOldid = false;
 982+ $this->mOldRev = false;
1086983 }
1087 - if ( strlen( $line ) > self::MAX_LINE_LENGTH ) {
1088 - $words[] = $line;
1089 - $stripped[] = $line;
1090 - } else {
1091 - $m = array();
1092 - if (preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
1093 - $line, $m))
1094 - {
1095 - $words = array_merge( $words, $m[0] );
1096 - $stripped = array_merge( $stripped, $m[1] );
1097 - }
1098 - }
1099 - }
1100 - wfProfileOut( __METHOD__ );
1101 - return array($words, $stripped);
1102 - }
 984+ }/* elseif ( $this->mOldid === false ) leave mOldRev false; */
1103985
1104 - function orig () {
1105 - wfProfileIn( __METHOD__ );
1106 - $orig = new _HWLDF_WordAccumulator;
1107 -
1108 - foreach ($this->edits as $edit) {
1109 - if ($edit->type == 'copy')
1110 - $orig->addWords($edit->orig);
1111 - elseif ($edit->orig)
1112 - $orig->addWords($edit->orig, 'del');
 986+ if( is_null( $this->mOldRev ) ) {
 987+ return false;
1113988 }
1114 - $lines = $orig->getLines();
1115 - wfProfileOut( __METHOD__ );
1116 - return $lines;
1117 - }
1118989
1119 - function closing () {
1120 - wfProfileIn( __METHOD__ );
1121 - $closing = new _HWLDF_WordAccumulator;
 990+ if ( $this->mOldRev ) {
 991+ $this->mOldPage = $this->mOldRev->getTitle();
1122992
1123 - foreach ($this->edits as $edit) {
1124 - if ($edit->type == 'copy')
1125 - $closing->addWords($edit->closing);
1126 - elseif ($edit->closing)
1127 - $closing->addWords($edit->closing, 'ins');
1128 - }
1129 - $lines = $closing->getLines();
1130 - wfProfileOut( __METHOD__ );
1131 - return $lines;
1132 - }
1133 -}
 993+ $t = $wgLang->timeanddate( $this->mOldRev->getTimestamp(), true );
 994+ $dateofrev = $wgLang->date( $this->mOldRev->getTimestamp(), true );
 995+ $timeofrev = $wgLang->time( $this->mOldRev->getTimestamp(), true );
 996+ $oldLink = $this->mOldPage->escapeLocalUrl( array(
 997+ 'oldid' => $this->mOldid
 998+ ) );
 999+ $oldEdit = $this->mOldPage->escapeLocalUrl( array(
 1000+ 'action' => 'edit',
 1001+ 'oldid' => $this->mOldid
 1002+ ) );
 1003+ $this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t, $dateofrev, $timeofrev ) );
11341004
1135 -/**
1136 - * Wikipedia Table style diff formatter.
1137 - * @todo document
1138 - * @private
1139 - * @ingroup DifferenceEngine
1140 - */
1141 -class TableDiffFormatter extends DiffFormatter {
1142 - function __construct() {
1143 - $this->leading_context_lines = 2;
1144 - $this->trailing_context_lines = 2;
1145 - }
 1005+ $this->mOldtitle = "<a href='$oldLink'>{$this->mOldPagetitle}</a>"
 1006+ . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
 1007+ // Add an "undo" link
 1008+ $newUndo = $this->mNewPage->escapeLocalUrl( array(
 1009+ 'action' => 'edit',
 1010+ 'undoafter' => $this->mOldid,
 1011+ 'undo' => $this->mNewid
 1012+ ) );
 1013+ $htmlLink = htmlspecialchars( wfMsg( 'editundo' ) );
 1014+ $htmlTitle = $wgUser->getSkin()->titleAttrib( 'undo' );
 1015+ if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) {
 1016+ $this->mNewtitle .= " (<a href='$newUndo' $htmlTitle>" . $htmlLink . "</a>)";
 1017+ }
11461018
1147 - public static function escapeWhiteSpace( $msg ) {
1148 - $msg = preg_replace( '/^ /m', '&#160; ', $msg );
1149 - $msg = preg_replace( '/ $/m', ' &#160;', $msg );
1150 - $msg = preg_replace( '/ /', '&#160; ', $msg );
1151 - return $msg;
1152 - }
1153 -
1154 - function _block_header( $xbeg, $xlen, $ybeg, $ylen ) {
1155 - $r = '<tr><td colspan="2" class="diff-lineno"><!--LINE '.$xbeg."--></td>\n" .
1156 - '<td colspan="2" class="diff-lineno"><!--LINE '.$ybeg."--></td></tr>\n";
1157 - return $r;
1158 - }
1159 -
1160 - function _start_block( $header ) {
1161 - echo $header;
1162 - }
1163 -
1164 - function _end_block() {
1165 - }
1166 -
1167 - function _lines( $lines, $prefix=' ', $color='white' ) {
1168 - }
1169 -
1170 - # HTML-escape parameter before calling this
1171 - function addedLine( $line ) {
1172 - return $this->wrapLine( '+', 'diff-addedline', $line );
1173 - }
1174 -
1175 - # HTML-escape parameter before calling this
1176 - function deletedLine( $line ) {
1177 - return $this->wrapLine( '&minus;', 'diff-deletedline', $line );
1178 - }
1179 -
1180 - # HTML-escape parameter before calling this
1181 - function contextLine( $line ) {
1182 - return $this->wrapLine( '&#160;', 'diff-context', $line );
1183 - }
1184 -
1185 - private function wrapLine( $marker, $class, $line ) {
1186 - if( $line !== '' ) {
1187 - // The <div> wrapper is needed for 'overflow: auto' style to scroll properly
1188 - $line = Xml::tags( 'div', null, $this->escapeWhiteSpace( $line ) );
 1019+ if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) {
 1020+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';
 1021+ } else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) {
 1022+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';
 1023+ }
11891024 }
1190 - return "<td class='diff-marker'>$marker</td><td class='$class'>$line</td>";
1191 - }
11921025
1193 - function emptyLine() {
1194 - return '<td colspan="2">&#160;</td>';
 1026+ return true;
11951027 }
11961028
1197 - function _added( $lines ) {
1198 - foreach ($lines as $line) {
1199 - echo '<tr>' . $this->emptyLine() .
1200 - $this->addedLine( '<ins class="diffchange">' .
1201 - htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";
 1029+ /**
 1030+ * Load the text of the revisions, as well as revision data.
 1031+ */
 1032+ function loadText() {
 1033+ if ( $this->mTextLoaded == 2 ) {
 1034+ return true;
 1035+ } else {
 1036+ // Whether it succeeds or fails, we don't want to try again
 1037+ $this->mTextLoaded = 2;
12021038 }
1203 - }
12041039
1205 - function _deleted($lines) {
1206 - foreach ($lines as $line) {
1207 - echo '<tr>' . $this->deletedLine( '<del class="diffchange">' .
1208 - htmlspecialchars ( $line ) . '</del>' ) .
1209 - $this->emptyLine() . "</tr>\n";
 1040+ if ( !$this->loadRevisionData() ) {
 1041+ return false;
12101042 }
1211 - }
1212 -
1213 - function _context( $lines ) {
1214 - foreach ($lines as $line) {
1215 - echo '<tr>' .
1216 - $this->contextLine( htmlspecialchars ( $line ) ) .
1217 - $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";
 1043+ if ( $this->mOldRev ) {
 1044+ $this->mOldtext = $this->mOldRev->getText( Revision::FOR_THIS_USER );
 1045+ if ( $this->mOldtext === false ) {
 1046+ return false;
 1047+ }
12181048 }
 1049+ if ( $this->mNewRev ) {
 1050+ $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
 1051+ if ( $this->mNewtext === false ) {
 1052+ return false;
 1053+ }
 1054+ }
 1055+ return true;
12191056 }
12201057
1221 - function _changed( $orig, $closing ) {
1222 - wfProfileIn( __METHOD__ );
1223 -
1224 - $diff = new WordLevelDiff( $orig, $closing );
1225 - $del = $diff->orig();
1226 - $add = $diff->closing();
1227 -
1228 - # Notice that WordLevelDiff returns HTML-escaped output.
1229 - # Hence, we will be calling addedLine/deletedLine without HTML-escaping.
1230 -
1231 - while ( $line = array_shift( $del ) ) {
1232 - $aline = array_shift( $add );
1233 - echo '<tr>' . $this->deletedLine( $line ) .
1234 - $this->addedLine( $aline ) . "</tr>\n";
 1058+ /**
 1059+ * Load the text of the new revision, not the old one
 1060+ */
 1061+ function loadNewText() {
 1062+ if ( $this->mTextLoaded >= 1 ) {
 1063+ return true;
 1064+ } else {
 1065+ $this->mTextLoaded = 1;
12351066 }
1236 - foreach ($add as $line) { # If any leftovers
1237 - echo '<tr>' . $this->emptyLine() .
1238 - $this->addedLine( $line ) . "</tr>\n";
 1067+ if ( !$this->loadRevisionData() ) {
 1068+ return false;
12391069 }
1240 - wfProfileOut( __METHOD__ );
 1070+ $this->mNewtext = $this->mNewRev->getText( Revision::FOR_THIS_USER );
 1071+ return true;
12411072 }
12421073 }
Property changes on: trunk/phase3/includes/diff/DifferenceEngine.php
___________________________________________________________________
Deleted: svn:keywords
12431074 - Author Date Id Revision

Follow-up revisions

RevisionCommit summaryAuthorDate
r82512Per Tim Starling, follow-up r76252: move WikiDiff.php to DairikiDiff.php to n...ialex16:28, 20 February 2011

Comments

#Comment by 😂 (talk | contribs)   20:03, 7 November 2010

Omg thanks :D

#Comment by Tim Starling (talk | contribs)   07:23, 20 January 2011

You can't call the PHP diff engine "WikiDiff". Wikidiff2 is called wikidiff2 because it's partly based on a C++ diff engine called "wikidiff":

http://svn.wikimedia.org/svnroot/mediawiki/trunk/extensions/wikidiff/

which was most certainly not the same thing as the Dairiki diff engine.

Also, I don't think it's appropriate to call Guy Van den Broeck's diff engine "WikiDiff3" since it's not related to wikidiff2 in any way.

In other words: think of another name. "Wikidiff" is already taken.

#Comment by IAlex (talk | contribs)   16:30, 20 February 2011

Moved WikiDiff.php to DairikiDiff.php in r82512; but I'm not going to move WikiDiff3 as long as the class inside this file is named "WikiDiff3".

Status & tagging log