r38623 MediaWiki - Code Review archive

Repository:	MediaWiki
Revision:	< r38622‎ \| r38623 \| r38624 >
Date:	13:45, 5 August 2008
Author:	guyvdb
Status:	old
Tags:
Comment:	Enable new diff in LocalSettings
Modified paths:	/branches/visual_diff/phase3/includes/Diff.php (modified) (history) /branches/visual_diff/phase3/includes/DifferenceEngine.php (modified) (history)

Diff [purge]

Index: branches/visual_diff/phase3/includes/Diff.php
—	—	@@ -19,18 +19,22 @@
20	20
21	21	/**
22	22	* Implementation of the Diff algorithm.
23		- *
	23	+ *
	24	+ * DO NOT USE ON PRODUCTION SYSTEMS
	25	+ *
24	26	* The algorithm is based on the O(NP) LCS algorithm as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm"
25	27	* and extended with my own ideas.
26	28	*
27	29	* @return array($from_removed, $to_added)
28		~~- * \| TRUE if the token was removed or added.~~
	30	+ * TRUE if the token was removed or added.
29	31	*
30	32	* @author Guy Van den Broeck
31	33	*/
32	34	function wikidiff3_diff(array $from, array $to, $boundRunningTime=FALSE, $max_NP_before_bound = 800000){
33	35	wfProfileIn( __METHOD__ );
34	36
	37	+ $time = microtime(true);
	38	+
35	39	$m = sizeof($from);
36	40	$n = sizeof($to);
37	41
—	—	@@ -41,8 +45,7 @@
42	46	//remove common tokens at the start
43	47	$i=0;
44	48	while($i<$m && $i<$n && $from[$i]===$to[$i]){
45		~~- $result_from[$i] = FALSE;~~
46		~~- $result_to[$i] = FALSE;~~
	49	+ $result_from[$i] = $result_to[$i] = FALSE;
47	50	unset($from[$i],$to[$i]);
48	51	++$i;
49	52	}
—	—	@@ -50,16 +53,12 @@
51	54	//remove common tokens at the end
52	55	$j=1;
53	56	while($i+$j<=$m && $i+$j<=$n && $from[$m-$j]===$to[$n-$j]){
54		~~- $result_from[$m-$j] = FALSE;~~
55		~~- $result_to[$n-$j] = FALSE;~~
	57	+ $result_from[$m-$j] = $result_to[$n-$j] = FALSE;
56	58	unset($from[$m-$j],$to[$n-$j]);
57	59	++$j;
58	60	}
59	61
60		~~- $newFrom = array();~~
61		~~- $newFromIndex = array();~~
62		~~- $newTo = array();~~
63		~~- $newToIndex = array();~~
	62	+ $newFrom = $newFromIndex = $newTo = $newToIndex = array();
64	63
65	64	//remove tokens not in both sequences
66	65	$shared = array_fill_keys($from,FALSE);
—	—	@@ -79,16 +78,15 @@
80	79	}
81	80	}
82	81
83		~~- unset($from, $to);~~
	82	+ unset($from, $to, $shared);
84	83
85		~~- $m = sizeof($newFrom);~~
86		~~- $n = sizeof($newTo);~~
87		~~- $offsetx = 0;~~
88		~~- $offsety = 0;~~
89		~~- $from_inLcs = new InLcs($m);~~
90		~~- $to_inLcs = new InLcs($n);~~
	84	+ $m2 = sizeof($newFrom);
	85	+ $n2 = sizeof($newTo);
	86	+ $offsetx = $offsety = 0;
	87	+ $from_inLcs = new InLcs($m2);
	88	+ $to_inLcs = new InLcs($n2);
91	89
92		~~- wikidiff3_diffPart($newFrom, $newTo, $from_inLcs, $to_inLcs, $m, $n, $offsetx, $offsety, $m, $boundRunningTime, $max_NP_before_bound);~~
	90	+ wikidiff3_diffPart($newFrom, $newTo, $from_inLcs, $to_inLcs, $m2, $n2, $offsetx, $offsety, $m2, $boundRunningTime, $max_NP_before_bound);
93	91
94	92	foreach($from_inLcs->inLcs as $key => $in){
95	93	if($in){
—	—	@@ -100,6 +98,7 @@
101	99	$result_to[$newToIndex[$key]] = FALSE;
102	100	}
103	101	}
	102	+
104	103	wfProfileOut( __METHOD__ );
105	104	return array($result_from, $result_to);
106	105	}
—	—	@@ -108,62 +107,52 @@
109	108	if($bestKnownLcs==0 \|\| $m==0 \|\| $n==0){
110	109	return;
111	110	}
	111	+
112	112	if($m>$n){
113	113	return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound);
114	114	}
115	115
116		~~- wfProfileIn( __METHOD__ );~~
117		-
118	116	$a_inLcs_sym = &$a_inLcs->inLcs;
119	117	$b_inLcs_sym = &$b_inLcs->inLcs;
120	118
121	119	//remove common tokens at the start
122	120	while($m>0 && $n>0 && $a[0]===$b[0]){
123		~~- $a_inLcs_sym[$offsetx] = TRUE;~~
124		~~- $b_inLcs_sym[$offsety] = TRUE;~~
	121	+ $a_inLcs_sym[$offsetx] = $b_inLcs_sym[$offsety] = TRUE;
125	122	++$offsetx; ++$offsety;
126		~~- $m--; $n--;~~
127		~~- $bestKnownLcs--;~~
	123	+ --$m; --$n;
	124	+ --$bestKnownLcs;
128	125	array_shift($a);
129	126	array_shift($b);
130	127	}
131	128
132	129	//remove common tokens at the end
133	130	while($m>0 && $n>0 && $a[$m-1]===$b[$n-1]){
134		~~- $a_inLcs_sym[$offsetx+$m-1] = TRUE;~~
135		~~- $b_inLcs_sym[$offsety+$n-1] = TRUE;~~
	131	+ $a_inLcs_sym[$offsetx+$m-1] = $b_inLcs_sym[$offsety+$n-1] = TRUE;
136	132	--$m; --$n;
137		~~- $bestKnownLcs--;~~
	133	+ --$bestKnownLcs;
138	134	array_pop($a);
139	135	array_pop($b);
140	136	}
141	137
	138	+ if($bestKnownLcs==0 \|\| $m==0 \|\| $n==0){
	139	+ return;
	140	+ }
	141	+ if($m>$n){
	142	+ return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound);
	143	+ }
	144	+
142	145	$delta = $n-$m;
143	146	$delta_plus_1 = $delta+1;
144	147	$delta_min_1 = $delta-1;
145	148
146		~~- $fpForw = array_fill( 0, $delta_plus_1, -1);~~
147		~~- $lcsSizeForw = array_fill( 0, $delta_plus_1, 0);~~
148		~~- $snakeBeginForw = array_fill( 0, $delta_plus_1, -1);~~
149		~~- $snakeEndForw = array_fill( 0, $delta_plus_1, -1);~~
150		~~- $snakekForw = array_fill( 0, $delta_plus_1, 0);~~
151		-
152		~~- $fpBack = array_fill( 0, $delta_plus_1, $n);~~
153		~~- $lcsSizeBack = array_fill( 0, $delta_plus_1, 0);~~
154		~~- $snakeBeginBack = array_fill( 0, $delta_plus_1, $n);~~
155		~~- $snakeEndBack = array_fill( 0, $delta_plus_1, $n);~~
156		~~- $snakekBack = array_fill( 0, $delta_plus_1, 0);~~
157		-
	149	+ $fpForw = $snakeBeginForw = $snakeEndForw = array_fill( 0, $delta_plus_1, -1);
	150	+ $lcsSizeForw = $snakekForw = $lcsSizeBack = $snakekBack = array_fill( 0, $delta_plus_1, 0);
	151	+ $fpBack = $snakeBeginBack = $snakeEndBack = array_fill( 0, $delta_plus_1, $n);
158	152	$overlap = $delta>1 ? array_fill( 1, $delta_min_1, FALSE) : array();
	153	+ $bestLcsLength = $bestLcsLengthTop = $bestLcsLengthBottom = -1;
159	154
160		~~- $bestKnownLcs = $bestKnownLcs;~~
161		-
162		~~- $bestLcsLength = -1;~~
163		~~- $bestLcsLengthTop = -1;~~
164		~~- $bestLcsLengthBottom = -1;~~
165		-
166	155	if($boundRunningTime){
167		~~- $maxp_before_bound = max($max_NP_before_bound/$n,10);~~
	156	+ $maxp_before_bound = max((-$delta+sqrt($delta*$delta+($max_NP_before_bound<<2)))>>1,2);
168	157	if($maxp_before_bound>=$m){
169	158	$boundRunningTime = false;
170	159	unset($maxp_before_bound);
—	—	@@ -178,40 +167,44 @@
179	168
180	169	if($boundRunningTime && $p>$maxp_before_bound){
181	170	// bound the running time by stopping early
182		~~- if($bestLcsLength>0){~~
	171	+ if($bestLcsLength>=0){
	172	+ // accept the best LCS thusfar
183	173	break;
184	174	}else{
185		~~- $bestLcsProgressForw=0;~~
186		~~- $bestkForw = 0;~~
	175	+ $bestLcsProgressForw = $bestkForw = 0;
187	176	foreach($lcsSizeForw as $k => $localLcsProgress){
188		~~- if($localLcsProgress>$bestLcsProgressForw){~~
	177	+ if($localLcsProgress>$bestLcsProgressForw \|\| ($localLcsProgress==$bestLcsProgressForw && $bestkForw > $k)){
189	178	$bestLcsProgressForw = $localLcsProgress;
190	179	$bestkForw = $k;
191	180	}
192	181	}
193		~~- $bestLcsProgressBack=0;~~
194		~~- $bestkBack = 0;~~
	182	+ $bestLcsProgressBack = $bestkBack = 0;
195	183	foreach($lcsSizeBack as $k => $localLcsProgress){
196		~~- if($localLcsProgress-max(0,-$k,$k-$delta)>$bestLcsProgressBack){~~
197		~~- $bestLcsProgressBack = $localLcsProgress-max(0,-$k,$k-$delta);~~
	184	+ if($localLcsProgress>$bestLcsProgressBack \|\| ($localLcsProgress==$bestLcsProgressBack && $bestkBack < $k)){
	185	+ $bestLcsProgressBack = $localLcsProgress;
198	186	$bestkBack = $k;
199	187	}
200	188	}
201		~~- if($lcsSizeForw[$bestkForw]>0 \|\| $lcsSizeForw[$bestkBack]>0){~~
202		~~- if($fpForw[$bestkForw]>$fpBack[$bestkBack] \|\| $fpForw[$bestkForw]-$bestkForw>$fpBack[$bestkBack]-$bestkBack){~~
203		~~- // This is hard, maybe try some more? Can this even happen?~~
204		~~- }else{~~
205		~~- $topSnakeStart = $snakeBeginForw[$bestkForw];~~
206		~~- $topSnakeEnd = $snakeEndForw[$bestkForw];~~
207		~~- $topSnakek = $snakekForw[$bestkForw];~~
208		~~- $bottomSnakeStart = $snakeEndBack[$bestkBack]+1;~~
209		~~- $bottomSnakeEnd = $snakeBeginBack[$bestkBack]+1;~~
210		~~- $bottomSnakek = $snakekBack[$bestkBack];~~
211		~~- $bestLcsLengthTop = $lcsSizeForw[$bestkBack] + $topSnakeStart - $topSnakeEnd;~~
212		~~- $bestLcsLengthBottom = $lcsSizeBack[$bestkBack] + $bottomSnakeStart - $bottomSnakeEnd;~~
	189	+ if($fpForw[$bestkForw]-$bestkForw>$fpBack[$bestkBack]-$bestkBack){
	190	+ // This is hard, maybe try some more? Can this even happen? A solution will be found soon anyway.
	191	+ }else{
	192	+ // lets do this
	193	+ $topSnakeStart = $snakeBeginForw[$bestkForw];
	194	+ $topSnakeEnd = $snakeEndForw[$bestkForw];
	195	+ $topSnakek = $snakekForw[$bestkForw];
	196	+ $bestLcsLengthTop = $lcsSizeForw[$bestkBack] + $topSnakeStart - $topSnakeEnd;
213	197
	198	+ $bottomSnakeStart = $snakeEndBack[$bestkBack]+1;
	199	+ $bottomSnakeEnd = $snakeBeginBack[$bestkBack]+1;
	200	+ $bottomSnakek = $snakekBack[$bestkBack];
	201	+ $bestLcsLengthBottom = $lcsSizeBack[$bestkBack] + $bottomSnakeStart - $bottomSnakeEnd;
	202	+
	203	+ if($bottomSnakeStart-$topSnakeEnd>$n0.6 && ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek)>$m0.6){
	204	+ // cut the sequence from both sides (there isn't enough progress, 60% of the sequence is not covered)
214	205	// also diff the middle now
215	206	if($bottomSnakeEnd>($fpForw[$bestkForw]>>1)){
	207	+ // do the middle diff between the snakes
	208	+ wfDebug(" Limiting diff run time from both sides, middle between snakes\n");
216	209	$m_t = ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek);
217	210	$n_t = $bottomSnakeStart-$topSnakeEnd;
218	211	$a_t = array_slice($a, $topSnakeEnd-$topSnakek, $m_t);
—	—	@@ -219,6 +212,8 @@
220	213	$offsetx_t = $offsetx+($topSnakeEnd-$topSnakek);
221	214	$offsety_t = $offsety+$topSnakeEnd;
222	215	}else{
	216	+ // the snake is too early in the sequence, do the middle diff between endpoints of progress
	217	+ wfDebug(" Limiting diff run time from both sides, middle between endpoints\n");
223	218	$m_t = ($fpBack[$bestkBack]+1-$bestkBack)-($fpForw[$bestkForw]-$bestkForw);
224	219	$n_t = $fpBack[$bestkBack]+1-$fpForw[$bestkForw];
225	220	$a_t = array_slice($a, $fpForw[$bestkForw]-$bestkForw, $m_t);
—	—	@@ -227,33 +222,37 @@
228	223	$offsety_t = $offsety+$fpForw[$bestkForw];
229	224	}
230	225	wikidiff3_diffPart($a_t, $b_t, $a_inLcs, $b_inLcs, $m_t, $n_t, $offsetx_t, $offsety_t, $m_t, $boundRunningTime, $max_NP_before_bound);
231		~~- break;~~
	226	+ }else if(min($n-$bottomSnakeStart, $m-($bottomSnakeStart-$bottomSnakek))>min($topSnakeEnd, $topSnakeEnd-$topSnakek)){
	227	+ // the bottom snake is more interesting
	228	+ wfDebug("Limiting diff run time from bottom side\n");
	229	+ $topSnakeStart = $bottomSnakeStart;
	230	+ $topSnakeEnd = $bottomSnakeEnd;
	231	+ $topSnakek = $bottomSnakek;
	232	+ $bestLcsLengthTop = $topSnakeEnd-$topSnakek;
	233	+ $bottomSnakeStart = $bottomSnakeEnd;
	234	+ }else{
	235	+ // the top snake is more interesting
	236	+ wfDebug(" Limiting diff run time from top side\n");
	237	+ $bottomSnakeStart = $topSnakeEnd;
	238	+ $bottomSnakeEnd = $topSnakeEnd;
	239	+ $bottomSnakek = $topSnakek;
	240	+ $bestLcsLengthBottom = $m-($bottomSnakeEnd-$bottomSnakek);
232	241	}
	242	+ break;
233	243	}
234		~~- //OOPS, problem~~
235		~~- //Maybe try a little more?~~
236	244	}
237	245	}
238	246	++$p;
239		~~- $overlap[-$p] = FALSE;~~
240		~~- $overlap[$delta+$p] = FALSE;~~
	247	+ $overlap[-$p] = $overlap[$delta+$p] = FALSE;
241	248
242	249	$min_p_min_1 = -$p-1;
243	250	$delta_plus_1_plus_p = $delta_plus_1+$p;
244	251
245	252	// forward
246		~~- $fpForw[$min_p_min_1] = -1;~~
247		~~- $lcsSizeForw[$min_p_min_1] = 0;~~
248		~~- $snakeBeginForw[$min_p_min_1]=-1;~~
249		~~- $snakeEndForw[$min_p_min_1]=-1;~~
250		~~- $snakekForw[$min_p_min_1]=-1;~~
	253	+ $fpForw[$min_p_min_1] = $snakeEndForw[$min_p_min_1] = $snakekForw[$min_p_min_1] = $snakeBeginForw[$min_p_min_1] = $fpForw[$delta_plus_1_plus_p] =
	254	+ $snakeBeginForw[$delta_plus_1_plus_p] = $snakeEndForw[$delta_plus_1_plus_p] = $snakekForw[$delta_plus_1_plus_p] = -1;
	255	+ $lcsSizeForw[$min_p_min_1] = $lcsSizeForw[$delta_plus_1_plus_p] = 0;
251	256
252		~~- $fpForw[$delta_plus_1_plus_p] = -1;~~
253		~~- $lcsSizeForw[$delta_plus_1_plus_p] = 0;~~
254		~~- $snakeBeginForw[$delta_plus_1_plus_p]=-1;~~
255		~~- $snakeEndForw[$delta_plus_1_plus_p]=-1;~~
256		~~- $snakekForw[$delta_plus_1_plus_p]=-1;~~
257		-
258	257	$k=-$p;
259	258	do {
260	259	$k_plus_1 = $k+1;
—	—	@@ -263,19 +262,18 @@
264	263	$fpAbove = $fpForw[$k_plus_1];
265	264	$y = &$fpForw[$k];
266	265	if($fpBelow>$fpAbove){
267		~~- $y = $fpBelow;~~
	266	+ $oldy = $y = $fpBelow;
268	267	$lcsSizeForw[$k] = $lcsSizeForw[$k_min_1];
269	268	$snakeBeginForw[$k] = $snakeBeginForw[$k_min_1];
270	269	$snakeEndForw[$k] = $snakeEndForw[$k_min_1];
271	270	$snakekForw[$k] = $snakekForw[$k_min_1];
272	271	}else{
273		~~- $y = $fpAbove;~~
	272	+ $oldy = $y = $fpAbove;
274	273	$lcsSizeForw[$k] = $lcsSizeForw[$k_plus_1];
275	274	$snakeBeginForw[$k] = $snakeBeginForw[$k_plus_1];
276	275	$snakeEndForw[$k] = $snakeEndForw[$k_plus_1];
277	276	$snakekForw[$k] = $snakekForw[$k_plus_1];
278	277	}
279		~~- $oldy = $y;~~
280	278	$x = $y-$k;
281	279	while($x < $m && $y < $n && $a[$x]===$b[$y]){
282	280	++$x;
—	—	@@ -336,18 +334,10 @@
337	335	} while(TRUE);
338	336
339	337	// backward
340		~~- $fpBack[$min_p_min_1] = $n;~~
341		~~- $lcsSizeBack[$min_p_min_1] = 0;~~
342		~~- $snakeBeginBack[$min_p_min_1]=$n;~~
343		~~- $snakeEndBack[$min_p_min_1]=$n;~~
344		~~- $snakekBack[$min_p_min_1]=$n;~~
	338	+ $fpBack[$min_p_min_1] = $snakeBeginBack[$min_p_min_1] = $snakeEndBack[$min_p_min_1] = $snakekBack[$min_p_min_1] =
	339	+ $fpBack[$delta_plus_1_plus_p] = $snakeBeginBack[$delta_plus_1_plus_p] = $snakeEndBack[$delta_plus_1_plus_p] = $snakekBack[$delta_plus_1_plus_p] = $n;
	340	+ $lcsSizeBack[$min_p_min_1] = $lcsSizeBack[$delta_plus_1_plus_p] = 0;
345	341
346		~~- $fpBack[$delta_plus_1_plus_p] = $n;~~
347		~~- $lcsSizeBack[$delta_plus_1_plus_p] = 0;~~
348		~~- $snakeBeginBack[$delta_plus_1_plus_p]=$n;~~
349		~~- $snakeEndBack[$delta_plus_1_plus_p]=$n;~~
350		~~- $snakekBack[$delta_plus_1_plus_p]=$n;~~
351		-
352	342	$k=$delta+$p;
353	343	do {
354	344	$k_plus_1 = $k+1;
—	—	@@ -357,19 +347,18 @@
358	348	$fpAbove = $fpBack[$k_plus_1]-1;
359	349	$y = &$fpBack[$k];
360	350	if($fpBelow<$fpAbove){
361		~~- $y = $fpBelow;~~
	351	+ $oldy = $y = $fpBelow;
362	352	$lcsSizeBack[$k] = $lcsSizeBack[$k_min_1];
363	353	$snakeBeginBack[$k] = $snakeBeginBack[$k_min_1];
364	354	$snakeEndBack[$k] = $snakeEndBack[$k_min_1];
365	355	$snakekBack[$k] = $snakekBack[$k_min_1];
366	356	}else{
367		~~- $y = $fpAbove;~~
	357	+ $oldy = $y = $fpAbove;
368	358	$lcsSizeBack[$k] = $lcsSizeBack[$k_plus_1];
369	359	$snakeBeginBack[$k] = $snakeBeginBack[$k_plus_1];
370	360	$snakeEndBack[$k] = $snakeEndBack[$k_plus_1];
371	361	$snakekBack[$k] = $snakekBack[$k_plus_1];
372	362	}
373		~~- $oldy = $y;~~
374	363	$x = $y-$k;
375	364	while($x > -1 && $y > -1 && $a[$x]===$b[$y]){
376	365	--$x;
—	—	@@ -464,8 +453,6 @@
465	454	wikidiff3_diffPart($a_t, $b_t, $a_inLcs, $b_inLcs, $m_t, $topSnakeStart, $offsetx, $offsety, $bestLcsLengthTop, $boundRunningTime, $max_NP_before_bound);
466	455
467	456	wikidiff3_diffPart($a_b, $b_b, $a_inLcs, $b_inLcs, $m_b, $n_b, $offsetx+($bottomSnakeEnd-$bottomSnakek), $offsety+$bottomSnakeEnd, $bestLcsLengthBottom, $boundRunningTime, $max_NP_before_bound);
468		-
469		~~- wfProfileOut( __METHOD__ );~~
470	457	}
471	458
472	459	class InLcs {
—	—	@@ -484,268 +471,4 @@
485	472	}
486	473
487	474	}
488		-
489		-/**
490		~~- * DISCLAIMER: The next classes are made obsolete by the previous function.~~
491		~~- * They implement Wu's O(NP) algorithm in a literal way and only compute the LCS.~~
492		~~- */~~
493		-
494		-/**
495		~~- * Class providing primitives for LCS or Diff.~~
496		- *
497		~~- * @author Guy Van den Broeck~~
498		~~- */~~
499		~~-class AbstractDiffAlgorithm {~~
500		-
501		- /**
502		~~- * Slide down the snake untill reaching an inequality.~~
503		~~- */~~
504		~~- protected function forward_snake( $k, $y, $maxx, $maxy, $a, $b, $offsetx=0, $offsety=0){~~
505		~~- $x = $y-$k;~~
506		~~- while($x < $maxx && $y < $maxy && $this->equals($a[$offsetx+$x],$b[$offsety+$y])){~~
507		~~- ++$x;~~
508		~~- ++$y;~~
509		~~- }~~
510		~~- return $y;~~
511		~~- }~~
512		-
513		- /**
514		~~- * Slide up the snake until reaching an inequality.~~
515		~~- */~~
516		~~- protected function backward_snake( $k, $y, $maxx, $maxy, $a, $b, $offsetx=0, $offsety=0){~~
517		~~- $x = $y-$k;~~
518		~~- while($x > $maxx && $y > $maxy && $this->equals($a[$offsetx+$x],$b[$offsety+$y])){~~
519		~~- --$x;~~
520		~~- --$y;~~
521		~~- }~~
522		~~- return $y;~~
523		~~- }~~
524		-
525		- /**
526		~~- * Override this method to compute the LCS with different equality measures.~~
527		~~- */~~
528		~~- public function equals($left, $right){~~
529		~~- return $left == $right;~~
530		~~- }~~
531		-}
532		-
533		-/**
534		~~- * Class implementing the LCS algorithm by backward propagation.~~
535		- *
536		~~- * This is the O(NP) variant as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm"~~
537		- *
538		~~- * @author Guy Van den Broeck~~
539		~~- */~~
540		~~-class BackwardLcs extends AbstractDiffAlgorithm {~~
541		-
542		- /*
543		~~- * Computers the length of the longest common subsequence of~~
544		~~- * the arrays $from and $to.~~
545		~~- */~~
546		~~- public function lcs (array $from, array $to) {~~
547		~~- return (sizeof($from)+sizeof($to)-$this->ses( $from, $to))/2;~~
548		~~- }~~
549		-
550		- /*
551		~~- * Computers the length of the shortest edit script of~~
552		~~- * the arrays $from and $to.~~
553		~~- */~~
554		~~- public function ses (array $from, array $to) {~~
555		~~- if(sizeof($from)>sizeof($to)){~~
556		~~- $temp = $from;~~
557		~~- $from = $to;~~
558		~~- $to = $temp;~~
559		~~- }~~
560		~~- $m = sizeof($from);~~
561		~~- $n = sizeof($to);~~
562		-
563		~~- if($n==0){~~
564		~~- return $m;~~
565		~~- }else if($m==0){~~
566		~~- return $n;~~
567		~~- }~~
568		-
569		~~- $delta = $n-$m;~~
570		~~- $p = -1;~~
571		~~- $fp = array_fill( 0, $delta+1, $n);~~
572		-
573		~~- do{~~
574		~~- ++$p;~~
575		-
576		~~- $fp[-$p-1] = $n;~~
577		~~- $fp[$delta+$p+1] = $n;~~
578		-
579		~~- for($k=$delta+$p;$k>0;$k--){~~
580		~~- $fp[$k] = $this->backward_snake( $k, min( $fp[$k+1]-1, $fp[$k-1]), -1, -1, $from, $to);~~
581		~~- }~~
582		~~- for($k=-$p;$k<0;$k++){~~
583		~~- $fp[$k] = $this->backward_snake( $k, min( $fp[$k+1]-1, $fp[$k-1]), -1, -1, $from, $to);~~
584		~~- }~~
585		~~- $fp[0] = $this->backward_snake( 0, min( $fp[1]-1, $fp[-1]), -1, -1, $from, $to);~~
586		~~- }while($fp[0]!=-1);~~
587		-
588		~~- return $delta+2*$p;~~
589		~~- }~~
590		-
591		-}
592		-
593		-/**
594		~~- * Class implementing the LCS algorithm by forward propagation.~~
595		- *
596		~~- * This is the O(NP) variant as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm"~~
597		- *
598		~~- * @author Guy Van den Broeck~~
599		~~- */~~
600		~~-class ForwardLcs extends AbstractDiffAlgorithm {~~
601		-
602		- /*
603		~~- * Computers the length of the longest common subsequence of~~
604		~~- * the arrays $from and $to.~~
605		~~- */~~
606		~~- public function lcs (array $from, array $to) {~~
607		~~- return (sizeof($from)+sizeof($to)-$this->ses( $from, $to))/2;~~
608		~~- }~~
609		-
610		- /*
611		~~- * Computers the length of the shortest edit script of~~
612		~~- * the arrays $from and $to.~~
613		~~- */~~
614		~~- public function ses (array $from, array $to) {~~
615		~~- if(sizeof($from)>sizeof($to)){~~
616		~~- $temp = $from;~~
617		~~- $from = $to;~~
618		~~- $to = $temp;~~
619		~~- }~~
620		~~- $m = sizeof($from);~~
621		~~- $n = sizeof($to);~~
622		-
623		~~- if($n==0){~~
624		~~- return $m;~~
625		~~- }else if($m==0){~~
626		~~- return $n;~~
627		~~- }~~
628		-
629		~~- $delta = $n-$m;~~
630		~~- $p = -1;~~
631		~~- $fp = array_fill( 0, $delta+1, -1);~~
632		~~- do{~~
633		~~- ++$p;~~
634		-
635		~~- $fp[-$p-1] = -1;~~
636		~~- $fp[$delta+$p+1] = -1;~~
637		-
638		~~- for($k=-$p;$k<$delta;$k++){~~
639		~~- $fp[$k] = $this->forward_snake( $k, max( $fp[$k-1]+1, $fp[$k+1]), $m, $n, $from, $to);~~
640		~~- }~~
641		~~- for($k=$delta+$p;$k>$delta;$k--){~~
642		~~- $fp[$k] = $this->forward_snake( $k, max( $fp[$k-1]+1, $fp[$k+1]), $m, $n, $from, $to);~~
643		~~- }~~
644		~~- $fp[$delta] = $this->forward_snake( $delta, max( $fp[$delta-1]+1, $fp[$delta+1]), $m, $n, $from, $to);~~
645		~~- }while($fp[$delta]!=$n);~~
646		-
647		~~- return $delta+2*$p;~~
648		~~- }~~
649		-
650		-}
651		-
652		-/**
653		~~- * Class implementing the LCS algorithm by bidirectional propagation.~~
654		- *
655		~~- * !!!!!!!!!!!!!!!!!!!!!!~~
656		~~- * BEWARE HERE BE DRAGONS~~
657		~~- * This algorithm is not guaranteed to find the exact size of the LCS.~~
658		~~- * There are border cases where it will be 1 (or more) off.~~
659		~~- * This implmentation is useful because it is very fast.~~
660		~~- * !!!!!!!!!!!!!!!!!!!!!!~~
661		- *
662		~~- * This is the O(NP) variant as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm"~~
663		- *
664		~~- * @author Guy Van den Broeck~~
665		~~- */~~
666		~~-class BidirectionalLcs extends AbstractDiffAlgorithm {~~
667		-
668		- /*
669		~~- * Computers the length of the longest common subsequence of~~
670		~~- * the arrays $from and $to.~~
671		~~- */~~
672		~~- public function lcs (array $from, array $to) {~~
673		~~- return (sizeof($from)+sizeof($to)-$this->ses( $from, $to))/2;~~
674		~~- }~~
675		-
676		- /*
677		~~- * Computers the length of the shortest edit script of~~
678		~~- * the arrays $from and $to.~~
679		~~- */~~
680		~~- public function ses (array $from, array $to) {~~
681		~~- if(sizeof($from)>sizeof($to)){~~
682		~~- $temp = $from;~~
683		~~- $from = $to;~~
684		~~- $to = $temp;~~
685		~~- }~~
686		~~- $m = sizeof($from);~~
687		~~- $n = sizeof($to);~~
688		-
689		~~- if($n==0){~~
690		~~- return $m;~~
691		~~- }else if($m==0){~~
692		~~- return $n;~~
693		~~- }~~
694		-
695		~~- $delta = $n-$m;~~
696		~~- $p = -1;~~
697		~~- $fpf = array_fill( 0, $delta+1, -1);~~
698		~~- $fpb = array_fill( 0, $delta+1, $n);~~
699		-
700		~~- $p = -1;~~
701		-
702		~~- while(1){~~
703		~~- ++$p;~~
704		-
705		~~- //forward~~
706		~~- $fpf[-$p-1] = -1;~~
707		~~- $fpf[$delta+$p+1] = -1;~~
708		-
709		~~- for($k=-$p;$k<$delta;$k++){~~
710		~~- $fpf[$k] = $this->forward_snake( $k, max( $fpf[$k-1]+1, $fpf[$k+1]), $m, $n, $from, $to);~~
711		~~- if($fpf[$k]>$fpb[$k]+1){~~
712		~~- return $delta+4*$p-4;~~
713		~~- }~~
714		~~- }~~
715		~~- for($k=$delta+$p;$k>$delta;$k--){~~
716		~~- $fpf[$k] = $this->forward_snake( $k, max( $fpf[$k-1]+1, $fpf[$k+1]), $m, $n, $from, $to);~~
717		~~- if($fpf[$k]>$fpb[$k]+1){~~
718		~~- return $delta+4*$p-4;~~
719		~~- }~~
720		~~- }~~
721		~~- $fpf[$delta] = $this->forward_snake( $delta, max( $fpf[$delta-1]+1, $fpf[$delta+1]), $m, $n, $from, $to);~~
722		-
723		~~- if($fpf[$delta]>$fpb[$delta]+1){~~
724		~~- return $delta+4*$p-4;~~
725		~~- }~~
726		-
727		~~- //backward~~
728		~~- $fpb[-$p-1] = $n;~~
729		~~- $fpb[$delta+$p+1] = $n;~~
730		-
731		~~- for($k=$delta+$p;$k>0;$k--){~~
732		~~- $fpb[$k] = $this->backward_snake( $k, min( $fpb[$k+1]-1, $fpb[$k-1]), -1, -1, $from, $to);~~
733		~~- if($fpf[$k]>$fpb[$k]+1){~~
734		~~- return $delta+4*$p;~~
735		~~- }~~
736		~~- }~~
737		~~- for($k=-$p;$k<0;$k++){~~
738		~~- $fpb[$k] = $this->backward_snake( $k, min( $fpb[$k+1]-1, $fpb[$k-1]), -1, -1, $from, $to);~~
739		~~- if($fpf[$k]>$fpb[$k]+1){~~
740		~~- return $delta+4*$p;~~
741		~~- }~~
742		~~- }~~
743		~~- $fpb[0] = $this->backward_snake( 0, min( $fpb[1]-1, $fpb[-1]), -1, -1, $from, $to);~~
744		-
745		~~- if($fpf[0]>$fpb[0]+1){~~
746		~~- return $delta+4*$p;~~
747		~~- }~~
748		-
749		~~- }~~
750		~~- }~~
751		-}
752	475	?>
\ No newline at end of file
Index: branches/visual_diff/phase3/includes/DifferenceEngine.php
—	—	@@ -83,7 +83,7 @@
84	84	global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol;
85	85	wfProfileIn( __METHOD__ );
86	86
87		~~- # If external diffs are enabled both globally and for the user,~~
	87	+ # If external diffs are enabled both globally and for the user,
88	88	# we'll use the application/x-external-editor interface to call
89	89	# an external diff tool like kompare, kdiff3, etc.
90	90	if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) {
—	—	@@ -94,19 +94,19 @@
95	95	$url2=$this->mTitle->getFullURL("action=raw&oldid=".$this->mNewid);
96	96	$special=$wgLang->getNsText(NS_SPECIAL);
97	97	$control=<<<CONTROL
98		~~-[Process]~~
99		~~-Type=Diff text~~
100		~~-Engine=MediaWiki~~
101		~~-Script={$wgServer}{$wgScript}~~
102		~~-Special namespace={$special}~~
	98	+ [Process]
	99	+ Type=Diff text
	100	+ Engine=MediaWiki
	101	+ Script={$wgServer}{$wgScript}
	102	+ Special namespace={$special}
103	103
104		~~-[File]~~
105		~~-Extension=wiki~~
106		~~-URL=$url1~~
	104	+ [File]
	105	+ Extension=wiki
	106	+ URL=$url1
107	107
108		~~-[File 2]~~
109		~~-Extension=wiki~~
110		~~-URL=$url2~~
	108	+ [File 2]
	109	+ Extension=wiki
	110	+ URL=$url2
111	111	CONTROL;
112	112	echo($control);
113	113	return;
—	—	@@ -176,15 +176,15 @@
177	177	// Look for an unpatrolled change corresponding to this diff
178	178	$db = wfGetDB( DB_SLAVE );
179	179	$change = RecentChange::newFromConds(
180		~~- array(~~
181		~~- // Add redundant user,timestamp condition so we can use the existing index~~
	180	+ array(
	181	+ // Add redundant user,timestamp condition so we can use the existing index
182	182	'rc_user_text' => $this->mNewRev->getRawUserText(),
183	183	'rc_timestamp' => $db->timestamp( $this->mNewRev->getTimestamp() ),
184	184	'rc_this_oldid' => $this->mNewid,
185	185	'rc_last_oldid' => $this->mOldid,
186	186	'rc_patrolled' => 0
187		~~- ),~~
188		~~- __METHOD__~~
	187	+ ),
	188	+ __METHOD__
189	189	);
190	190	if( $change instanceof RecentChange ) {
191	191	$rcid = $change->mAttribs['rc_id'];
—	—	@@ -196,8 +196,8 @@
197	197	// Build the link
198	198	if( $rcid ) {
199	199	$patrol = ' <span class="patrollink">[' . $sk->makeKnownLinkObj(
200		~~- $this->mTitle,~~
201		~~- wfMsgHtml( 'markaspatrolleddiff' ),~~
	200	+ $this->mTitle,
	201	+ wfMsgHtml( 'markaspatrolleddiff' ),
202	202	"action=markpatrolled&rcid={$rcid}"
203	203	) . ']</span>';
204	204	} else {
—	—	@@ -231,33 +231,33 @@
232	232	if( $wgUser->isAllowed( 'deleterevision' ) ) {
233	233	$revdel = SpecialPage::getTitleFor( 'Revisiondelete' );
234	234	if( !$this->mOldRev->userCan( Revision::DELETED_RESTRICTED ) ) {
235		~~- // If revision was hidden from sysops~~
	235	+ // If revision was hidden from sysops
236	236	$ldel = wfMsgHtml('rev-delundel');
237	237	} else {
238	238	$ldel = $sk->makeKnownLinkObj( $revdel,
239		~~- wfMsgHtml('rev-delundel'),~~
	239	+ wfMsgHtml('rev-delundel'),
240	240	'target=' . urlencode( $this->mOldRev->mTitle->getPrefixedDbkey() ) .
241	241	'&oldid=' . urlencode( $this->mOldRev->getId() ) );
242	242	// Bolden oversighted content
243	243	if( $this->mOldRev->isDeleted( Revision::DELETED_RESTRICTED ) )
244		~~- $ldel = "<strong>$ldel</strong>";~~
	244	+ $ldel = "<strong>$ldel</strong>";
245	245	}
246	246	$ldel = "   <tt>(<small>$ldel</small>)</tt> ";
247	247	// We don't currently handle well changing the top revision's settings
248	248	if( $this->mNewRev->isCurrent() ) {
249		~~- // If revision was hidden from sysops~~
	249	+ // If revision was hidden from sysops
250	250	$rdel = wfMsgHtml('rev-delundel');
251	251	} else if( !$this->mNewRev->userCan( Revision::DELETED_RESTRICTED ) ) {
252		~~- // If revision was hidden from sysops~~
	252	+ // If revision was hidden from sysops
253	253	$rdel = wfMsgHtml('rev-delundel');
254	254	} else {
255	255	$rdel = $sk->makeKnownLinkObj( $revdel,
256		~~- wfMsgHtml('rev-delundel'),~~
	256	+ wfMsgHtml('rev-delundel'),
257	257	'target=' . urlencode( $this->mNewRev->mTitle->getPrefixedDbkey() ) .
258	258	'&oldid=' . urlencode( $this->mNewRev->getId() ) );
259	259	// Bolden oversighted content
260	260	if( $this->mNewRev->isDeleted( Revision::DELETED_RESTRICTED ) )
261		~~- $rdel = "<strong>$rdel</strong>";~~
	261	+ $rdel = "<strong>$rdel</strong>";
262	262	}
263	263	$rdel = "   <tt>(<small>$rdel</small>)</tt> ";
264	264	}
—	—	@@ -274,7 +274,7 @@
275	275	$this->showDiff( $oldHeader, $newHeader );
276	276
277	277	if ( !$diffOnly )
278		~~- $this->renderNewRevision();~~
	278	+ $this->renderNewRevision();
279	279
280	280	wfProfileOut( __METHOD__ );
281	281	}
—	—	@@ -289,9 +289,9 @@
290	290	$wgOut->addHTML( "<hr /><h2>{$this->mPagetitle}</h2>\n" );
291	291	#add deleted rev tag if needed
292	292	if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
293		~~- $wgOut->addWikiMsg( 'rev-deleted-text-permission' );~~
	293	+ $wgOut->addWikiMsg( 'rev-deleted-text-permission' );
294	294	} else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
295		~~- $wgOut->addWikiMsg( 'rev-deleted-text-view' );~~
	295	+ $wgOut->addWikiMsg( 'rev-deleted-text-view' );
296	296	}
297	297
298	298	if( !$this->mNewRev->isCurrent() ) {
—	—	@@ -316,7 +316,7 @@
317	317	$wgOut->addHtml( "\n</pre>\n" );
318	318	}
319	319	} else
320		~~- $wgOut->addWikiTextTidy( $this->mNewtext );~~
	320	+ $wgOut->addWikiTextTidy( $this->mNewtext );
321	321
322	322	if( !$this->mNewRev->isCurrent() ) {
323	323	$wgOut->parserOptions()->setEditSection( $oldEditSectionSetting );
—	—	@@ -362,9 +362,9 @@
363	363
364	364	$nextlink = $sk->makeKnownLinkObj( $this->mTitle, wfMsgHtml( 'nextdiff' ), 'diff=next&oldid='.$this->mNewid, '', '', 'id="differences-nextlink"' );
365	365	$header = "<div class=\"firstrevisionheader\" style=\"text-align: center\"><strong>{$this->mOldtitle}</strong><br />" .
366		~~- $sk->revUserTools( $this->mNewRev ) . "<br />" .~~
367		~~- $sk->revComment( $this->mNewRev ) . "<br />" .~~
368		~~- $nextlink . "</div>\n";~~
	366	+ $sk->revUserTools( $this->mNewRev ) . "<br />" .
	367	+ $sk->revComment( $this->mNewRev ) . "<br />" .
	368	+ $nextlink . "</div>\n";
369	369
370	370	$wgOut->addHTML( $header );
371	371
—	—	@@ -429,9 +429,9 @@
430	430	wfProfileIn( __METHOD__ );
431	431	// Check if the diff should be hidden from this user
432	432	if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) {
433		~~- return '';~~
	433	+ return '';
434	434	} else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
435		~~- return '';~~
	435	+ return '';
436	436	}
437	437	// Cacheable?
438	438	$key = false;
—	—	@@ -492,7 +492,7 @@
493	493	dl('php_wikidiff.so');
494	494	}
495	495	return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) .
496		~~- $this->debug( 'wikidiff1' );~~
	496	+ $this->debug( 'wikidiff1' );
497	497	}
498	498
499	499	if ( $wgExternalDiffEngine == 'wikidiff2' ) {
—	—	@@ -511,7 +511,7 @@
512	512	return $text;
513	513	}
514	514	}
515		~~- if ( $wgExternalDiffEngine !== false ) {~~
	515	+ if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) {
516	516	# Diff via the shell
517	517	global $wgTmpDirectory;
518	518	$tempName1 = tempnam( $wgTmpDirectory, 'diff_' );
—	—	@@ -547,9 +547,9 @@
548	548	$diffs = new Diff( $ota, $nta );
549	549	$formatter = new TableDiffFormatter();
550	550	return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) .
551		~~- $this->debug();~~
	551	+ $this->debug();
552	552	}
553		-
	553	+
554	554	/**
555	555	* Generate a debug comment indicating diff generating time,
556	556	* server node, and generator backend.
—	—	@@ -562,10 +562,10 @@
563	563	}
564	564	$data[] = wfTimestamp( TS_DB );
565	565	return "<!-- diff generator: " .
566		~~- implode( " ",~~
567		~~- array_map(~~
	566	+ implode( " ",
	567	+ array_map(
568	568	"htmlspecialchars",
569		~~- $data ) ) .~~
	569	+ $data ) ) .
570	570	" -->\n";
571	571	}
572	572
—	—	@@ -574,7 +574,7 @@
575	575	*/
576	576	function localiseLineNumbers( $text ) {
577	577	return preg_replace_callback( '/<!--LINE (\d+)-->/',
578		~~- array( &$this, 'localiseLineNumbersCb' ), $text );~~
	578	+ array( &$this, 'localiseLineNumbersCb' ), $text );
579	579	}
580	580
581	581	function localiseLineNumbersCb( $matches ) {
—	—	@@ -588,7 +588,7 @@
589	589	*/
590	590	function getMultiNotice() {
591	591	if ( !is_object($this->mOldRev) \|\| !is_object($this->mNewRev) )
592		~~- return '';~~
	592	+ return '';
593	593
594	594	if( !$this->mOldPage->equals( $this->mNewPage ) ) {
595	595	// Comparing two different pages? Count would be meaningless.
—	—	@@ -603,7 +603,7 @@
604	604
605	605	$n = $this->mTitle->countRevisionsBetween( $oldid, $newid );
606	606	if ( !$n )
607		~~- return '';~~
	607	+ return '';
608	608
609	609	return wfMsgExt( 'diff-multi', array( 'parseinline' ), $n );
610	610	}
—	—	@@ -616,19 +616,19 @@
617	617	global $wgOut;
618	618
619	619	$header = "
620		~~- <table class='diff'>~~
621		~~- <col class='diff-marker' />~~
622		~~- <col class='diff-content' />~~
623		~~- <col class='diff-marker' />~~
624		~~- <col class='diff-content' />~~
625		~~- <tr valign='top'>~~
626		~~- <td colspan='2' class='diff-otitle'>{$otitle}</td>~~
627		~~- <td colspan='2' class='diff-ntitle'>{$ntitle}</td>~~
628		~~- </tr>~~
	620	+ <table class='diff'>
	621	+ <col class='diff-marker' />
	622	+ <col class='diff-content' />
	623	+ <col class='diff-marker' />
	624	+ <col class='diff-content' />
	625	+ <tr valign='top'>
	626	+ <td colspan='2' class='diff-otitle'>{$otitle}</td>
	627	+ <td colspan='2' class='diff-ntitle'>{$ntitle}</td>
	628	+ </tr>
629	629	";
630	630
631	631	if ( $multi != '' )
632		~~- $header .= "<tr><td colspan='4' align='center' class='diff-multi'>{$multi}</td></tr>";~~
	632	+ $header .= "<tr><td colspan='4' align='center' class='diff-multi'>{$multi}</td></tr>";
633	633
634	634	return $header . $diff . "</table>";
635	635	}
—	—	@@ -663,10 +663,10 @@
664	664
665	665	// Load the new revision object
666	666	$this->mNewRev = $this->mNewid
667		~~- ? Revision::newFromId( $this->mNewid )~~
668		~~- : Revision::newFromTitle( $this->mTitle );~~
	667	+ ? Revision::newFromId( $this->mNewid )
	668	+ : Revision::newFromTitle( $this->mTitle );
669	669	if( !$this->mNewRev instanceof Revision )
670		~~- return false;~~
	670	+ return false;
671	671
672	672	// Update the new revision ID in case it was 0 (makes life easier doing UI stuff)
673	673	$this->mNewid = $this->mNewRev->getId();
—	—	@@ -694,9 +694,9 @@
695	695	$this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
696	696	}
697	697	if ( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
698		~~- $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";~~
	698	+ $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";
699	699	} else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
700		~~- $this->mNewtitle = '<span class="history-deleted">'.$this->mNewtitle.'</span>';~~
	700	+ $this->mNewtitle = '<span class="history-deleted">'.$this->mNewtitle.'</span>';
701	701	}
702	702
703	703	// Load the old revision object
—	—	@@ -728,7 +728,7 @@
729	729	$this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t ) );
730	730
731	731	$this->mOldtitle = "<a href='$oldLink'>{$this->mOldPagetitle}</a>"
732		~~- . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";~~
	732	+ . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
733	733	// Add an "undo" link
734	734	$newUndo = $this->mNewPage->escapeLocalUrl( 'action=edit&undoafter=' . $this->mOldid . '&undo=' . $this->mNewid);
735	735	if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) {
—	—	@@ -736,9 +736,9 @@
737	737	}
738	738
739	739	if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) {
740		~~- $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';~~
	740	+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';
741	741	} else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) {
742		~~- $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';~~
	742	+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';
743	743	}
744	744	}
745	745
—	—	@@ -834,7 +834,7 @@
835	835
836	836	function _DiffOp_Copy ($orig, $closing = false) {
837	837	if (!is_array($closing))
838		~~- $closing = $orig;~~
	838	+ $closing = $orig;
839	839	$this->orig = $orig;
840	840	$this->closing = $closing;
841	841	}
—	—	@@ -898,66 +898,146 @@
899	899	}
900	900	}
901	901
902		-
903	902	/**
904	903	* Class used internally by Diff to actually compute the diffs.
905	904	*
906		~~- * The actual diff algorithm is replaced byt he wikidiff3_diff function in Diff.php.~~
	905	+ * The algorithm used here is mostly lifted from the perl module
	906	+ * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
	907	+ * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
907	908	*
	909	+ * More ideas are taken from:
	910	+ * http://www.ics.uci.edu/~eppstein/161/960229.html
	911	+ *
	912	+ * Some ideas are (and a bit of code) are from from analyze.c, from GNU
	913	+ * diffutils-2.7, which can be found at:
	914	+ * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
	915	+ *
	916	+ * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
	917	+ * are my own.
	918	+ *
	919	+ * Line length limits for robustness added by Tim Starling, 2005-08-31
	920	+ * Alternative implementation added by Guy Van den Broeck, 2008-07-30
	921	+ *
908	922	* @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
909	923	* @private
910	924	* @ingroup DifferenceEngine
911	925	*/
912	926	class _DiffEngine {
913	927
	928	+ const MAX_XREF_LENGTH = 10000;
	929	+
914	930	function diff ($from_lines, $to_lines) {
915	931	wfProfileIn( __METHOD__ );
916		~~- // Perform the basic diff algorithm~~
917		~~- list($xchanged, $ychanged) = wikidiff3_diff($from_lines, $to_lines);~~
918		-
	932	+
	933	+ global $wgExternalDiffEngine;
	934	+
	935	+ $n_from = sizeof($from_lines);
	936	+ $n_to = sizeof($to_lines);
	937	+
	938	+ if($wgExternalDiffEngine == 'wikidiff3'){
	939	+ // wikidiff3
	940	+ list($this->xchanged, $this->ychanged) = wikidiff3_diff($from_lines, $to_lines, TRUE, 100000);
	941	+ }else{
	942	+ // old diff
	943	+ wfProfileIn( __METHOD__ ." - basicdiff");
	944	+ $this->xchanged = $this->ychanged = array();
	945	+ $this->xv = $this->yv = array();
	946	+ $this->xind = $this->yind = array();
	947	+ unset($this->seq);
	948	+ unset($this->in_seq);
	949	+ unset($this->lcs);
	950	+
	951	+ // Skip leading common lines.
	952	+ for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
	953	+ if ($from_lines[$skip] !== $to_lines[$skip])
	954	+ break;
	955	+ $this->xchanged[$skip] = $this->ychanged[$skip] = false;
	956	+ }
	957	+ // Skip trailing common lines.
	958	+ $xi = $n_from; $yi = $n_to;
	959	+ for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
	960	+ if ($from_lines[$xi] !== $to_lines[$yi])
	961	+ break;
	962	+ $this->xchanged[$xi] = $this->ychanged[$yi] = false;
	963	+ }
	964	+
	965	+ // Ignore lines which do not exist in both files.
	966	+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
	967	+ $xhash[$this->_line_hash($from_lines[$xi])] = 1;
	968	+ }
	969	+
	970	+ for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
	971	+ $line = $to_lines[$yi];
	972	+ if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )
	973	+ continue;
	974	+ $yhash[$this->_line_hash($line)] = 1;
	975	+ $this->yv[] = $line;
	976	+ $this->yind[] = $yi;
	977	+ }
	978	+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
	979	+ $line = $from_lines[$xi];
	980	+ if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )
	981	+ continue;
	982	+ $this->xv[] = $line;
	983	+ $this->xind[] = $xi;
	984	+ }
	985	+
	986	+ // Find the LCS.
	987	+ $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
	988	+ wfProfileOut( __METHOD__ ." - basicdiff");
	989	+ }
	990	+
919	991	// Merge edits when possible
920		~~- $this->_shift_boundaries($from_lines, $xchanged, $ychanged);~~
921		~~- $this->_shift_boundaries($to_lines, $ychanged, $xchanged);~~
	992	+ $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
	993	+ $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
922	994
923	995	// Compute the edit operations.
924		~~- $n_from = sizeof($from_lines);~~
925		~~- $n_to = sizeof($to_lines);~~
926	996	$edits = array();
927	997	$xi = $yi = 0;
928	998	while ($xi < $n_from \|\| $yi < $n_to) {
929		~~- USE_ASSERTS && assert($yi < $n_to \|\| $xchanged[$xi]);~~
930		~~- USE_ASSERTS && assert($xi < $n_from \|\| $ychanged[$yi]);~~
	999	+ USE_ASSERTS && assert($yi < $n_to \|\| $this->xchanged[$xi]);
	1000	+ USE_ASSERTS && assert($xi < $n_from \|\| $this->ychanged[$yi]);
931	1001
932	1002	// Skip matching "snake".
933	1003	$copy = array();
934	1004	while ( $xi < $n_from && $yi < $n_to
935		~~- && !$xchanged[$xi] && !$ychanged[$yi]) {~~
	1005	+ && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
936	1006	$copy[] = $from_lines[$xi++];
937	1007	++$yi;
938	1008	}
939	1009	if ($copy)
940		~~- $edits[] = new _DiffOp_Copy($copy);~~
	1010	+ $edits[] = new _DiffOp_Copy($copy);
941	1011
942	1012	// Find deletes & adds.
943	1013	$delete = array();
944		~~- while ($xi < $n_from && $xchanged[$xi])~~
945		~~- $delete[] = $from_lines[$xi++];~~
	1014	+ while ($xi < $n_from && $this->xchanged[$xi])
	1015	+ $delete[] = $from_lines[$xi++];
946	1016
947	1017	$add = array();
948		~~- while ($yi < $n_to && $ychanged[$yi])~~
949		~~- $add[] = $to_lines[$yi++];~~
	1018	+ while ($yi < $n_to && $this->ychanged[$yi])
	1019	+ $add[] = $to_lines[$yi++];
950	1020
951	1021	if ($delete && $add)
952		~~- $edits[] = new _DiffOp_Change($delete, $add);~~
	1022	+ $edits[] = new _DiffOp_Change($delete, $add);
953	1023	elseif ($delete)
954		~~- $edits[] = new _DiffOp_Delete($delete);~~
	1024	+ $edits[] = new _DiffOp_Delete($delete);
955	1025	elseif ($add)
956		~~- $edits[] = new _DiffOp_Add($add);~~
	1026	+ $edits[] = new _DiffOp_Add($add);
957	1027	}
958	1028	wfProfileOut( __METHOD__ );
959	1029	return $edits;
960	1030	}
961	1031
	1032	+ /**
	1033	+ * Returns the whole line if it's small enough, or the MD5 hash otherwise
	1034	+ */
	1035	+ function _line_hash( $line ) {
	1036	+ if ( strlen( $line ) > self::MAX_XREF_LENGTH ) {
	1037	+ return md5( $line );
	1038	+ } else {
	1039	+ return $line;
	1040	+ }
	1041	+ }
962	1042
963	1043	/* Divide the Largest Common Subsequence (LCS) of the sequences
964	1044	* [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
—	—	@@ -976,23 +1056,22 @@
977	1057	* of the portions it is going to specify.
978	1058	*/
979	1059	function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
980		~~- wfProfileIn( __METHOD__ );~~
981	1060	$flip = false;
982	1061
983	1062	if ($xlim - $xoff > $ylim - $yoff) {
984	1063	// Things seems faster (I'm not sure I understand why)
985		~~- // when the shortest sequence in X.~~
986		~~- $flip = true;~~
	1064	+ // when the shortest sequence in X.
	1065	+ $flip = true;
987	1066	list ($xoff, $xlim, $yoff, $ylim)
988	1067	= array( $yoff, $ylim, $xoff, $xlim);
989	1068	}
990	1069
991	1070	if ($flip)
992		~~- for ($i = $ylim - 1; $i >= $yoff; $i--)~~
993		~~- $ymatches[$this->xv[$i]][] = $i;~~
	1071	+ for ($i = $ylim - 1; $i >= $yoff; $i--)
	1072	+ $ymatches[$this->xv[$i]][] = $i;
994	1073	else
995		~~- for ($i = $ylim - 1; $i >= $yoff; $i--)~~
996		~~- $ymatches[$this->yv[$i]][] = $i;~~
	1074	+ for ($i = $ylim - 1; $i >= $yoff; $i--)
	1075	+ $ymatches[$this->yv[$i]][] = $i;
997	1076
998	1077	$this->lcs = 0;
999	1078	$this->seq[0]= $yoff - 1;
—	—	@@ -1004,23 +1083,23 @@
1005	1084	for ($chunk = 0; $chunk < $nchunks; $chunk++) {
1006	1085	wfProfileIn( __METHOD__ . "-chunk" );
1007	1086	if ($chunk > 0)
1008		~~- for ($i = 0; $i <= $this->lcs; $i++)~~
1009		~~- $ymids[$i][$chunk-1] = $this->seq[$i];~~
	1087	+ for ($i = 0; $i <= $this->lcs; $i++)
	1088	+ $ymids[$i][$chunk-1] = $this->seq[$i];
1010	1089
1011	1090	$x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
1012	1091	for ( ; $x < $x1; $x++) {
1013	1092	$line = $flip ? $this->yv[$x] : $this->xv[$x];
1014		~~- if (empty($ymatches[$line]))~~
1015		~~- continue;~~
	1093	+ if (empty($ymatches[$line]))
	1094	+ continue;
1016	1095	$matches = $ymatches[$line];
1017	1096	reset($matches);
1018	1097	while (list ($junk, $y) = each($matches))
1019		~~- if (empty($this->in_seq[$y])) {~~
1020		~~- $k = $this->_lcs_pos($y);~~
1021		~~- USE_ASSERTS && assert($k > 0);~~
1022		~~- $ymids[$k] = $ymids[$k-1];~~
1023		~~- break;~~
1024		~~- }~~
	1098	+ if (empty($this->in_seq[$y])) {
	1099	+ $k = $this->_lcs_pos($y);
	1100	+ USE_ASSERTS && assert($k > 0);
	1101	+ $ymids[$k] = $ymids[$k-1];
	1102	+ break;
	1103	+ }
1025	1104	while (list ( /* $junk */, $y) = each($matches)) {
1026	1105	if ($y > $this->seq[$k-1]) {
1027	1106	USE_ASSERTS && assert($y < $this->seq[$k]);
—	—	@@ -1036,7 +1115,6 @@
1037	1116	}
1038	1117	}
1039	1118	}
1040		~~- wfProfileOut( __METHOD__ . "-chunk" );~~
1041	1119	}
1042	1120
1043	1121	$seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
—	—	@@ -1048,13 +1126,10 @@
1049	1127	}
1050	1128	$seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
1051	1129
1052		~~- wfProfileOut( __METHOD__ );~~
1053	1130	return array($this->lcs, $seps);
1054	1131	}
1055	1132
1056	1133	function _lcs_pos ($ypos) {
1057		~~- wfProfileIn( __METHOD__ );~~
1058		-
1059	1134	$end = $this->lcs;
1060	1135	if ($end == 0 \|\| $ypos > $this->seq[$end]) {
1061	1136	$this->seq[++$this->lcs] = $ypos;
—	—	@@ -1067,9 +1142,9 @@
1068	1143	while ($beg < $end) {
1069	1144	$mid = (int)(($beg + $end) / 2);
1070	1145	if ( $ypos > $this->seq[$mid] )
1071		~~- $beg = $mid + 1;~~
	1146	+ $beg = $mid + 1;
1072	1147	else
1073		~~- $end = $mid;~~
	1148	+ $end = $mid;
1074	1149	}
1075	1150
1076	1151	USE_ASSERTS && assert($ypos != $this->seq[$end]);
—	—	@@ -1077,7 +1152,6 @@
1078	1153	$this->in_seq[$this->seq[$end]] = false;
1079	1154	$this->seq[$end] = $ypos;
1080	1155	$this->in_seq[$ypos] = 1;
1081		~~- wfProfileOut( __METHOD__ );~~
1082	1156	return $end;
1083	1157	}
1084	1158
—	—	@@ -1093,24 +1167,22 @@
1094	1168	* All line numbers are origin-0 and discarded lines are not counted.
1095	1169	*/
1096	1170	function _compareseq ($xoff, $xlim, $yoff, $ylim) {
1097		~~- wfProfileIn( __METHOD__ );~~
1098		-
1099	1171	// Slide down the bottom initial diagonal.
1100	1172	while ($xoff < $xlim && $yoff < $ylim
1101		~~- && $this->xv[$xoff] == $this->yv[$yoff]) {~~
	1173	+ && $this->xv[$xoff] == $this->yv[$yoff]) {
1102	1174	++$xoff;
1103	1175	++$yoff;
1104	1176	}
1105	1177
1106	1178	// Slide up the top initial diagonal.
1107	1179	while ($xlim > $xoff && $ylim > $yoff
1108		~~- && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {~~
	1180	+ && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
1109	1181	--$xlim;
1110	1182	--$ylim;
1111	1183	}
1112	1184
1113	1185	if ($xoff == $xlim \|\| $yoff == $ylim)
1114		~~- $lcs = 0;~~
	1186	+ $lcs = 0;
1115	1187	else {
1116	1188	// This is ad hoc but seems to work well.
1117	1189	//$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
—	—	@@ -1124,9 +1196,9 @@
1125	1197	// X and Y sequences have no common subsequence:
1126	1198	// mark all changed.
1127	1199	while ($yoff < $ylim)
1128		~~- $this->ychanged[$this->yind[$yoff++]] = 1;~~
	1200	+ $this->ychanged[$this->yind[$yoff++]] = 1;
1129	1201	while ($xoff < $xlim)
1130		~~- $this->xchanged[$this->xind[$xoff++]] = 1;~~
	1202	+ $this->xchanged[$this->xind[$xoff++]] = 1;
1131	1203	} else {
1132	1204	// Use the partitions to split this problem into subproblems.
1133	1205	reset($seps);
—	—	@@ -1136,7 +1208,6 @@
1137	1209	$pt1 = $pt2;
1138	1210	}
1139	1211	}
1140		~~- wfProfileOut( __METHOD__ );~~
1141	1212	}
1142	1213
1143	1214	/* Adjust inserts/deletes of identical lines to join changes
—	—	@@ -1173,23 +1244,23 @@
1174	1245	* $other_changed[$j] == false.
1175	1246	*/
1176	1247	while ($j < $other_len && $other_changed[$j])
1177		~~- $j++;~~
	1248	+ $j++;
1178	1249
1179	1250	while ($i < $len && ! $changed[$i]) {
1180	1251	USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1181	1252	$i++; $j++;
1182	1253	while ($j < $other_len && $other_changed[$j])
1183		~~- $j++;~~
	1254	+ $j++;
1184	1255	}
1185	1256
1186	1257	if ($i == $len)
1187		~~- break;~~
	1258	+ break;
1188	1259
1189	1260	$start = $i;
1190	1261
1191	1262	// Find the end of this run of changes.
1192	1263	while (++$i < $len && $changed[$i])
1193		~~- continue;~~
	1264	+ continue;
1194	1265
1195	1266	do {
1196	1267	/*
—	—	@@ -1207,10 +1278,10 @@
1208	1279	$changed[--$start] = 1;
1209	1280	$changed[--$i] = false;
1210	1281	while ($start > 0 && $changed[$start - 1])
1211		~~- $start--;~~
	1282	+ $start--;
1212	1283	USE_ASSERTS && assert('$j > 0');
1213	1284	while ($other_changed[--$j])
1214		~~- continue;~~
	1285	+ continue;
1215	1286	USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1216	1287	}
1217	1288
—	—	@@ -1232,14 +1303,14 @@
1233	1304	$changed[$start++] = false;
1234	1305	$changed[$i++] = 1;
1235	1306	while ($i < $len && $changed[$i])
1236		~~- $i++;~~
	1307	+ $i++;
1237	1308
1238	1309	USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1239	1310	$j++;
1240	1311	if ($j < $other_len && $other_changed[$j]) {
1241	1312	$corresponding = $i;
1242	1313	while ($j < $other_len && $other_changed[$j])
1243		~~- $j++;~~
	1314	+ $j++;
1244	1315	}
1245	1316	}
1246	1317	} while ($runlength != $i - $start);
—	—	@@ -1253,7 +1324,7 @@
1254	1325	$changed[--$i] = 0;
1255	1326	USE_ASSERTS && assert('$j > 0');
1256	1327	while ($other_changed[--$j])
1257		~~- continue;~~
	1328	+ continue;
1258	1329	USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1259	1330	}
1260	1331	}
—	—	@@ -1312,7 +1383,7 @@
1313	1384	function isEmpty () {
1314	1385	foreach ($this->edits as $edit) {
1315	1386	if ($edit->type != 'copy')
1316		~~- return false;~~
	1387	+ return false;
1317	1388	}
1318	1389	return true;
1319	1390	}
—	—	@@ -1328,7 +1399,7 @@
1329	1400	$lcs = 0;
1330	1401	foreach ($this->edits as $edit) {
1331	1402	if ($edit->type == 'copy')
1332		~~- $lcs += sizeof($edit->orig);~~
	1403	+ $lcs += sizeof($edit->orig);
1333	1404	}
1334	1405	return $lcs;
1335	1406	}
—	—	@@ -1346,7 +1417,7 @@
1347	1418
1348	1419	foreach ($this->edits as $edit) {
1349	1420	if ($edit->orig)
1350		~~- array_splice($lines, sizeof($lines), 0, $edit->orig);~~
	1421	+ array_splice($lines, sizeof($lines), 0, $edit->orig);
1351	1422	}
1352	1423	return $lines;
1353	1424	}
—	—	@@ -1364,7 +1435,7 @@
1365	1436
1366	1437	foreach ($this->edits as $edit) {
1367	1438	if ($edit->closing)
1368		~~- array_splice($lines, sizeof($lines), 0, $edit->closing);~~
	1439	+ array_splice($lines, sizeof($lines), 0, $edit->closing);
1369	1440	}
1370	1441	return $lines;
1371	1442	}
—	—	@@ -1377,21 +1448,21 @@
1378	1449	function _check ($from_lines, $to_lines) {
1379	1450	wfProfileIn( __METHOD__ );
1380	1451	if (serialize($from_lines) != serialize($this->orig()))
1381		~~- trigger_error("Reconstructed original doesn't match", E_USER_ERROR);~~
	1452	+ trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
1382	1453	if (serialize($to_lines) != serialize($this->closing()))
1383		~~- trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);~~
	1454	+ trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
1384	1455
1385	1456	$rev = $this->reverse();
1386	1457	if (serialize($to_lines) != serialize($rev->orig()))
1387		~~- trigger_error("Reversed original doesn't match", E_USER_ERROR);~~
	1458	+ trigger_error("Reversed original doesn't match", E_USER_ERROR);
1388	1459	if (serialize($from_lines) != serialize($rev->closing()))
1389		~~- trigger_error("Reversed closing doesn't match", E_USER_ERROR);~~
	1460	+ trigger_error("Reversed closing doesn't match", E_USER_ERROR);
1390	1461
1391	1462
1392	1463	$prevtype = 'none';
1393	1464	foreach ($this->edits as $edit) {
1394	1465	if ( $prevtype == $edit->type )
1395		~~- trigger_error("Edit sequence is non-optimal", E_USER_ERROR);~~
	1466	+ trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
1396	1467	$prevtype = $edit->type;
1397	1468	}
1398	1469
—	—	@@ -1432,7 +1503,7 @@
1433	1504	* have the same number of elements as $to_lines.
1434	1505	*/
1435	1506	function MappedDiff($from_lines, $to_lines,
1436		~~- $mapped_from_lines, $mapped_to_lines) {~~
	1507	+ $mapped_from_lines, $mapped_to_lines) {
1437	1508	wfProfileIn( __METHOD__ );
1438	1509
1439	1510	assert(sizeof($from_lines) == sizeof($mapped_from_lines));
—	—	@@ -1515,8 +1586,8 @@
1516	1587	$block[] = new _DiffOp_Copy($context);
1517	1588	}
1518	1589	$this->_block($x0, $ntrail + $xi - $x0,
1519		~~- $y0, $ntrail + $yi - $y0,~~
1520		~~- $block);~~
	1590	+ $y0, $ntrail + $yi - $y0,
	1591	+ $block);
1521	1592	$block = false;
1522	1593	}
1523	1594	}
—	—	@@ -1529,21 +1600,21 @@
1530	1601	$y0 = $yi - sizeof($context);
1531	1602	$block = array();
1532	1603	if ($context)
1533		~~- $block[] = new _DiffOp_Copy($context);~~
	1604	+ $block[] = new _DiffOp_Copy($context);
1534	1605	}
1535	1606	$block[] = $edit;
1536	1607	}
1537	1608
1538	1609	if ($edit->orig)
1539		~~- $xi += sizeof($edit->orig);~~
	1610	+ $xi += sizeof($edit->orig);
1540	1611	if ($edit->closing)
1541		~~- $yi += sizeof($edit->closing);~~
	1612	+ $yi += sizeof($edit->closing);
1542	1613	}
1543	1614
1544	1615	if (is_array($block))
1545		~~- $this->_block($x0, $xi - $x0,~~
1546		~~- $y0, $yi - $y0,~~
1547		~~- $block);~~
	1616	+ $this->_block($x0, $xi - $x0,
	1617	+ $y0, $yi - $y0,
	1618	+ $block);
1548	1619
1549	1620	$end = $this->_end_diff();
1550	1621	wfProfileOut( __METHOD__ );
—	—	@@ -1555,15 +1626,15 @@
1556	1627	$this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
1557	1628	foreach ($edits as $edit) {
1558	1629	if ($edit->type == 'copy')
1559		~~- $this->_context($edit->orig);~~
	1630	+ $this->_context($edit->orig);
1560	1631	elseif ($edit->type == 'add')
1561		~~- $this->_added($edit->closing);~~
	1632	+ $this->_added($edit->closing);
1562	1633	elseif ($edit->type == 'delete')
1563		~~- $this->_deleted($edit->orig);~~
	1634	+ $this->_deleted($edit->orig);
1564	1635	elseif ($edit->type == 'change')
1565		~~- $this->_changed($edit->orig, $edit->closing);~~
	1636	+ $this->_changed($edit->orig, $edit->closing);
1566	1637	else
1567		~~- trigger_error('Unknown edit type', E_USER_ERROR);~~
	1638	+ trigger_error('Unknown edit type', E_USER_ERROR);
1568	1639	}
1569	1640	$this->_end_block();
1570	1641	wfProfileOut( __METHOD__ );
—	—	@@ -1581,9 +1652,9 @@
1582	1653
1583	1654	function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1584	1655	if ($xlen > 1)
1585		~~- $xbeg .= "," . ($xbeg + $xlen - 1);~~
	1656	+ $xbeg .= "," . ($xbeg + $xlen - 1);
1586	1657	if ($ylen > 1)
1587		~~- $ybeg .= "," . ($ybeg + $ylen - 1);~~
	1658	+ $ybeg .= "," . ($ybeg + $ylen - 1);
1588	1659
1589	1660	return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
1590	1661	}
—	—	@@ -1597,7 +1668,7 @@
1598	1669
1599	1670	function _lines($lines, $prefix = ' ') {
1600	1671	foreach ($lines as $line)
1601		~~- echo "$prefix $line\n";~~
	1672	+ echo "$prefix $line\n";
1602	1673	}
1603	1674
1604	1675	function _context($lines) {
—	—	@@ -1652,40 +1723,40 @@
1653	1724	$newline = 1;
1654	1725	$retval = array();
1655	1726	foreach($diff->edits as $edit)
1656		~~- switch($edit->type) {~~
1657		~~- case 'add':~~
1658		~~- foreach($edit->closing as $l) {~~
1659		~~- $retval[] = array(~~
	1727	+ switch($edit->type) {
	1728	+ case 'add':
	1729	+ foreach($edit->closing as $l) {
	1730	+ $retval[] = array(
1660	1731	'action' => 'add',
1661	1732	'new'=> $l,
1662	1733	'newline' => $newline++
1663		~~- );~~
1664		~~- }~~
1665		~~- break;~~
1666		~~- case 'delete':~~
1667		~~- foreach($edit->orig as $l) {~~
1668		~~- $retval[] = array(~~
	1734	+ );
	1735	+ }
	1736	+ break;
	1737	+ case 'delete':
	1738	+ foreach($edit->orig as $l) {
	1739	+ $retval[] = array(
1669	1740	'action' => 'delete',
1670	1741	'old' => $l,
1671	1742	'oldline' => $oldline++,
1672		~~- );~~
1673		~~- }~~
1674		~~- break;~~
1675		~~- case 'change':~~
1676		~~- foreach($edit->orig as $i => $l) {~~
1677		~~- $retval[] = array(~~
	1743	+ );
	1744	+ }
	1745	+ break;
	1746	+ case 'change':
	1747	+ foreach($edit->orig as $i => $l) {
	1748	+ $retval[] = array(
1678	1749	'action' => 'change',
1679	1750	'old' => $l,
1680	1751	'new' => @$edit->closing[$i],
1681	1752	'oldline' => $oldline++,
1682	1753	'newline' => $newline++,
1683		~~- );~~
1684		~~- }~~
1685		~~- break;~~
1686		~~- case 'copy':~~
1687		~~- $oldline += count($edit->orig);~~
1688		~~- $newline += count($edit->orig);~~
1689		~~- }~~
	1754	+ );
	1755	+ }
	1756	+ break;
	1757	+ case 'copy':
	1758	+ $oldline += count($edit->orig);
	1759	+ $newline += count($edit->orig);
	1760	+ }
1690	1761	return $retval;
1691	1762	}
1692	1763	}
—	—	@@ -1713,13 +1784,13 @@
1714	1785	function _flushGroup ($new_tag) {
1715	1786	if ($this->_group !== '') {
1716	1787	if ($this->_tag == 'ins')
1717		~~- $this->_line .= '<ins class="diffchange diffchange-inline">' .~~
1718		~~- htmlspecialchars ( $this->_group ) . '</ins>';~~
	1788	+ $this->_line .= '<ins class="diffchange diffchange-inline">' .
	1789	+ htmlspecialchars ( $this->_group ) . '</ins>';
1719	1790	elseif ($this->_tag == 'del')
1720		~~- $this->_line .= '<del class="diffchange diffchange-inline">' .~~
1721		~~- htmlspecialchars ( $this->_group ) . '</del>';~~
	1791	+ $this->_line .= '<del class="diffchange diffchange-inline">' .
	1792	+ htmlspecialchars ( $this->_group ) . '</del>';
1722	1793	else
1723		~~- $this->_line .= htmlspecialchars ( $this->_group );~~
	1794	+ $this->_line .= htmlspecialchars ( $this->_group );
1724	1795	}
1725	1796	$this->_group = '';
1726	1797	$this->_tag = $new_tag;
—	—	@@ -1728,21 +1799,21 @@
1729	1800	function _flushLine ($new_tag) {
1730	1801	$this->_flushGroup($new_tag);
1731	1802	if ($this->_line != '')
1732		~~- array_push ( $this->_lines, $this->_line );~~
	1803	+ array_push ( $this->_lines, $this->_line );
1733	1804	else
1734		~~- # make empty lines visible by inserting an NBSP~~
1735		~~- array_push ( $this->_lines, NBSP );~~
	1805	+ # make empty lines visible by inserting an NBSP
	1806	+ array_push ( $this->_lines, NBSP );
1736	1807	$this->_line = '';
1737	1808	}
1738	1809
1739	1810	function addWords ($words, $tag = '') {
1740	1811	if ($tag != $this->_tag)
1741		~~- $this->_flushGroup($tag);~~
	1812	+ $this->_flushGroup($tag);
1742	1813
1743	1814	foreach ($words as $word) {
1744	1815	// new-line should only come as first char of word.
1745	1816	if ($word == '')
1746		~~- continue;~~
	1817	+ continue;
1747	1818	if ($word[0] == "\n") {
1748	1819	$this->_flushLine($tag);
1749	1820	$word = substr($word, 1);
—	—	@@ -1773,7 +1844,7 @@
1774	1845	list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
1775	1846
1776	1847	$this->MappedDiff($orig_words, $closing_words,
1777		~~- $orig_stripped, $closing_stripped);~~
	1848	+ $orig_stripped, $closing_stripped);
1778	1849	wfProfileOut( __METHOD__ );
1779	1850	}
1780	1851
—	—	@@ -1798,7 +1869,7 @@
1799	1870	} else {
1800	1871	$m = array();
1801	1872	if (preg_match_all('/ ( [^\S\n]+ \| [0-9_A-Za-z\x80-\xff]+ \| . ) (?: (?!< \n) [^\S\n])? /xs',
1802		~~- $line, $m))~~
	1873	+ $line, $m))
1803	1874	{
1804	1875	$words = array_merge( $words, $m[0] );
1805	1876	$stripped = array_merge( $stripped, $m[1] );
—	—	@@ -1815,9 +1886,9 @@
1816	1887
1817	1888	foreach ($this->edits as $edit) {
1818	1889	if ($edit->type == 'copy')
1819		~~- $orig->addWords($edit->orig);~~
	1890	+ $orig->addWords($edit->orig);
1820	1891	elseif ($edit->orig)
1821		~~- $orig->addWords($edit->orig, 'del');~~
	1892	+ $orig->addWords($edit->orig, 'del');
1822	1893	}
1823	1894	$lines = $orig->getLines();
1824	1895	wfProfileOut( __METHOD__ );
—	—	@@ -1830,9 +1901,9 @@
1831	1902
1832	1903	foreach ($this->edits as $edit) {
1833	1904	if ($edit->type == 'copy')
1834		~~- $closing->addWords($edit->closing);~~
	1905	+ $closing->addWords($edit->closing);
1835	1906	elseif ($edit->closing)
1836		~~- $closing->addWords($edit->closing, 'ins');~~
	1907	+ $closing->addWords($edit->closing, 'ins');
1837	1908	}
1838	1909	$lines = $closing->getLines();
1839	1910	wfProfileOut( __METHOD__ );
—	—	@@ -1905,24 +1976,24 @@
1906	1977	function _added( $lines ) {
1907	1978	foreach ($lines as $line) {
1908	1979	echo '<tr>' . $this->emptyLine() .
1909		~~- $this->addedLine( '<ins class="diffchange">' .~~
1910		~~- htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";~~
	1980	+ $this->addedLine( '<ins class="diffchange">' .
	1981	+ htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";
1911	1982	}
1912	1983	}
1913	1984
1914	1985	function _deleted($lines) {
1915	1986	foreach ($lines as $line) {
1916	1987	echo '<tr>' . $this->deletedLine( '<del class="diffchange">' .
1917		~~- htmlspecialchars ( $line ) . '</del>' ) .~~
1918		~~- $this->emptyLine() . "</tr>\n";~~
	1988	+ htmlspecialchars ( $line ) . '</del>' ) .
	1989	+ $this->emptyLine() . "</tr>\n";
1919	1990	}
1920	1991	}
1921	1992
1922	1993	function _context( $lines ) {
1923	1994	foreach ($lines as $line) {
1924	1995	echo '<tr>' .
1925		~~- $this->contextLine( htmlspecialchars ( $line ) ) .~~
1926		~~- $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";~~
	1996	+ $this->contextLine( htmlspecialchars ( $line ) ) .
	1997	+ $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";
1927	1998	}
1928	1999	}
1929	2000
—	—	@@ -1939,11 +2010,11 @@
1940	2011	while ( $line = array_shift( $del ) ) {
1941	2012	$aline = array_shift( $add );
1942	2013	echo '<tr>' . $this->deletedLine( $line ) .
1943		~~- $this->addedLine( $aline ) . "</tr>\n";~~
	2014	+ $this->addedLine( $aline ) . "</tr>\n";
1944	2015	}
1945	2016	foreach ($add as $line) { # If any leftovers
1946	2017	echo '<tr>' . $this->emptyLine() .
1947		~~- $this->addedLine( $line ) . "</tr>\n";~~
	2018	+ $this->addedLine( $line ) . "</tr>\n";
1948	2019	}
1949	2020	wfProfileOut( __METHOD__ );
1950	2021	}

Status & tagging log

15:29, 12 September 2011 Meno25 (talk | contribs) changed the status of r38623 [removed: ok added: old]