r38653 MediaWiki - Code Review archive

Repository:	MediaWiki
Revision:	< r38652‎ \| r38653 \| r38654 >
Date:	19:40, 5 August 2008
Author:	guyvdb
Status:	old
Tags:
Comment:	Alternative experimental diff implementation. Enable by setting = 'wikidiff3'.
Modified paths:	/trunk/phase3/includes/Diff.php (added) (history) /trunk/phase3/includes/DifferenceEngine.php (modified) (history)

Diff [purge]

Index: trunk/phase3/includes/Diff.php
—	—	@@ -0,0 +1,472 @@
	2	+<?php
	3	+/* Copyright (C) 2008 Guy Van den Broeck <guy@guyvdb.eu>
	4	+ *
	5	+ * This program is free software; you can redistribute it and/or modify
	6	+ * it under the terms of the GNU General Public License as published by
	7	+ * the Free Software Foundation; either version 2 of the License, or
	8	+ * (at your option) any later version.
	9	+ *
	10	+ * This program is distributed in the hope that it will be useful,
	11	+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	13	+ * GNU General Public License for more details.
	14	+ *
	15	+ * You should have received a copy of the GNU General Public License
	16	+ * along with this program; if not, write to the Free Software
	17	+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	18	+ * or see http://www.gnu.org/
	19	+ */
	20	+
	21	+/**
	22	+ * Implementation of the Diff algorithm.
	23	+ *
	24	+ * DO NOT USE ON PRODUCTION SYSTEMS
	25	+ *
	26	+ * The algorithm is based on the O(NP) LCS algorithm as descibed by Wu et al. in "An O(NP) Sequence Comparison Algorithm"
	27	+ * and extended with my own ideas.
	28	+ *
	29	+ * @return array($from_removed, $to_added)
	30	+ * TRUE if the token was removed or added.
	31	+ *
	32	+ * @author Guy Van den Broeck
	33	+ */
	34	+function wikidiff3_diff(array $from, array $to, $boundRunningTime=FALSE, $max_NP_before_bound = 800000){
	35	+ wfProfileIn( __METHOD__ );
	36	+
	37	+ $m = sizeof($from);
	38	+ $n = sizeof($to);
	39	+
	40	+ $result_from = array_fill(0,$m,TRUE);
	41	+ $result_to = array_fill(0,$n,TRUE);
	42	+
	43	+ //reduce the complexity for the next step (intentionally done twice)
	44	+ //remove common tokens at the start
	45	+ $i=0;
	46	+ while($i<$m && $i<$n && $from[$i]===$to[$i]){
	47	+ $result_from[$i] = $result_to[$i] = FALSE;
	48	+ unset($from[$i],$to[$i]);
	49	+ ++$i;
	50	+ }
	51	+
	52	+ //remove common tokens at the end
	53	+ $j=1;
	54	+ while($i+$j<=$m && $i+$j<=$n && $from[$m-$j]===$to[$n-$j]){
	55	+ $result_from[$m-$j] = $result_to[$n-$j] = FALSE;
	56	+ unset($from[$m-$j],$to[$n-$j]);
	57	+ ++$j;
	58	+ }
	59	+
	60	+ $newFrom = $newFromIndex = $newTo = $newToIndex = array();
	61	+
	62	+ //remove tokens not in both sequences
	63	+ $shared = array_fill_keys($from,FALSE);
	64	+ foreach($to as $index => $el){
	65	+ if(array_key_exists($el,$shared)){
	66	+ //keep it
	67	+ $shared[$el] = TRUE;
	68	+ $newTo[] = $el;
	69	+ $newToIndex[] = $index;
	70	+ }
	71	+ }
	72	+ foreach($from as $index => $el){
	73	+ if($shared[$el]){
	74	+ //keep it
	75	+ $newFrom[] = $el;
	76	+ $newFromIndex[] = $index;
	77	+ }
	78	+ }
	79	+
	80	+ unset($from, $to, $shared);
	81	+
	82	+ $m2 = sizeof($newFrom);
	83	+ $n2 = sizeof($newTo);
	84	+ $offsetx = $offsety = 0;
	85	+ $from_inLcs = new InLcs($m2);
	86	+ $to_inLcs = new InLcs($n2);
	87	+
	88	+ wikidiff3_diffPart($newFrom, $newTo, $from_inLcs, $to_inLcs, $m2, $n2, $offsetx, $offsety, $m2, $boundRunningTime, $max_NP_before_bound);
	89	+
	90	+ foreach($from_inLcs->inLcs as $key => $in){
	91	+ if($in){
	92	+ $result_from[$newFromIndex[$key]] = FALSE;
	93	+ }
	94	+ }
	95	+ foreach($to_inLcs->inLcs as $key => $in){
	96	+ if($in){
	97	+ $result_to[$newToIndex[$key]] = FALSE;
	98	+ }
	99	+ }
	100	+
	101	+ wfProfileOut( __METHOD__ );
	102	+ return array($result_from, $result_to);
	103	+}
	104	+
	105	+function wikidiff3_diffPart(array $a, array $b, InLcs $a_inLcs, InLcs $b_inLcs, $m, $n, $offsetx, $offsety, $bestKnownLcs, $boundRunningTime=FALSE, $max_NP_before_bound = 800000){
	106	+ if($bestKnownLcs==0 \|\| $m==0 \|\| $n==0){
	107	+ return;
	108	+ }
	109	+
	110	+ if($m>$n){
	111	+ return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound);
	112	+ }
	113	+
	114	+ $a_inLcs_sym = &$a_inLcs->inLcs;
	115	+ $b_inLcs_sym = &$b_inLcs->inLcs;
	116	+
	117	+ //remove common tokens at the start
	118	+ while($m>0 && $n>0 && $a[0]===$b[0]){
	119	+ $a_inLcs_sym[$offsetx] = $b_inLcs_sym[$offsety] = TRUE;
	120	+ ++$offsetx; ++$offsety;
	121	+ --$m; --$n;
	122	+ --$bestKnownLcs;
	123	+ array_shift($a);
	124	+ array_shift($b);
	125	+ }
	126	+
	127	+ //remove common tokens at the end
	128	+ while($m>0 && $n>0 && $a[$m-1]===$b[$n-1]){
	129	+ $a_inLcs_sym[$offsetx+$m-1] = $b_inLcs_sym[$offsety+$n-1] = TRUE;
	130	+ --$m; --$n;
	131	+ --$bestKnownLcs;
	132	+ array_pop($a);
	133	+ array_pop($b);
	134	+ }
	135	+
	136	+ if($bestKnownLcs==0 \|\| $m==0 \|\| $n==0){
	137	+ return;
	138	+ }
	139	+ if($m>$n){
	140	+ return wikidiff3_diffPart($b, $a, $b_inLcs, $a_inLcs, $n, $m, $offsety, $offsetx, $bestKnownLcs, $boundRunningTime, $max_NP_before_bound);
	141	+ }
	142	+
	143	+ $delta = $n-$m;
	144	+ $delta_plus_1 = $delta+1;
	145	+ $delta_min_1 = $delta-1;
	146	+
	147	+ $fpForw = $snakeBeginForw = $snakeEndForw = array_fill( 0, $delta_plus_1, -1);
	148	+ $lcsSizeForw = $snakekForw = $lcsSizeBack = $snakekBack = array_fill( 0, $delta_plus_1, 0);
	149	+ $fpBack = $snakeBeginBack = $snakeEndBack = array_fill( 0, $delta_plus_1, $n);
	150	+ $overlap = $delta>1 ? array_fill( 1, $delta_min_1, FALSE) : array();
	151	+ $bestLcsLength = $bestLcsLengthTop = $bestLcsLengthBottom = -1;
	152	+
	153	+ if($boundRunningTime){
	154	+ $maxp_before_bound = max((-$delta+sqrt($delta*$delta+($max_NP_before_bound<<2)))>>1,2);
	155	+ if($maxp_before_bound>=$m){
	156	+ $boundRunningTime = false;
	157	+ unset($maxp_before_bound);
	158	+ }
	159	+ }
	160	+
	161	+ $p=-1;
	162	+ $m_min_1 = $m-1;
	163	+ $maxp=$m_min_1-$bestLcsLength;
	164	+
	165	+ while($p<$maxp){
	166	+
	167	+ if($boundRunningTime && $p>$maxp_before_bound){
	168	+ // bound the running time by stopping early
	169	+ if($bestLcsLength>=0){
	170	+ // accept the best LCS thusfar
	171	+ break;
	172	+ }else{
	173	+ $bestLcsProgressForw = $bestkForw = 0;
	174	+ foreach($lcsSizeForw as $k => $localLcsProgress){
	175	+ if($localLcsProgress>$bestLcsProgressForw \|\| ($localLcsProgress==$bestLcsProgressForw && $bestkForw > $k)){
	176	+ $bestLcsProgressForw = $localLcsProgress;
	177	+ $bestkForw = $k;
	178	+ }
	179	+ }
	180	+ $bestLcsProgressBack = $bestkBack = 0;
	181	+ foreach($lcsSizeBack as $k => $localLcsProgress){
	182	+ if($localLcsProgress>$bestLcsProgressBack \|\| ($localLcsProgress==$bestLcsProgressBack && $bestkBack < $k)){
	183	+ $bestLcsProgressBack = $localLcsProgress;
	184	+ $bestkBack = $k;
	185	+ }
	186	+ }
	187	+ if($fpForw[$bestkForw]-$bestkForw>$fpBack[$bestkBack]-$bestkBack){
	188	+ // This is hard, maybe try some more? Can this even happen? A solution will be found soon anyway.
	189	+ }else{
	190	+ // lets do this
	191	+ $topSnakeStart = $snakeBeginForw[$bestkForw];
	192	+ $topSnakeEnd = $snakeEndForw[$bestkForw];
	193	+ $topSnakek = $snakekForw[$bestkForw];
	194	+ $bestLcsLengthTop = $lcsSizeForw[$bestkBack] + $topSnakeStart - $topSnakeEnd;
	195	+
	196	+ $bottomSnakeStart = $snakeEndBack[$bestkBack]+1;
	197	+ $bottomSnakeEnd = $snakeBeginBack[$bestkBack]+1;
	198	+ $bottomSnakek = $snakekBack[$bestkBack];
	199	+ $bestLcsLengthBottom = $lcsSizeBack[$bestkBack] + $bottomSnakeStart - $bottomSnakeEnd;
	200	+
	201	+ if($bottomSnakeStart-$topSnakeEnd>$n0.6 && ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek)>$m0.6){
	202	+ // cut the sequence from both sides (there isn't enough progress, 60% of the sequence is not covered)
	203	+ // also diff the middle now
	204	+ if($bottomSnakeEnd>($fpForw[$bestkForw]>>1)){
	205	+ // do the middle diff between the snakes
	206	+ wfDebug(" Limiting diff run time from both sides, middle between snakes\n");
	207	+ $m_t = ($bottomSnakeStart-$bottomSnakek)-($topSnakeEnd-$topSnakek);
	208	+ $n_t = $bottomSnakeStart-$topSnakeEnd;
	209	+ $a_t = array_slice($a, $topSnakeEnd-$topSnakek, $m_t);
	210	+ $b_t = array_slice($b, $topSnakeEnd, $n_t);
	211	+ $offsetx_t = $offsetx+($topSnakeEnd-$topSnakek);
	212	+ $offsety_t = $offsety+$topSnakeEnd;
	213	+ }else{
	214	+ // the snake is too early in the sequence, do the middle diff between endpoints of progress
	215	+ wfDebug(" Limiting diff run time from both sides, middle between endpoints\n");
	216	+ $m_t = ($fpBack[$bestkBack]+1-$bestkBack)-($fpForw[$bestkForw]-$bestkForw);
	217	+ $n_t = $fpBack[$bestkBack]+1-$fpForw[$bestkForw];
	218	+ $a_t = array_slice($a, $fpForw[$bestkForw]-$bestkForw, $m_t);
	219	+ $b_t = array_slice($b, $fpForw[$bestkForw], $n_t);
	220	+ $offsetx_t = $offsetx+($fpForw[$bestkForw]-$bestkForw);
	221	+ $offsety_t = $offsety+$fpForw[$bestkForw];
	222	+ }
	223	+ 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);
	224	+ }else if(min($n-$bottomSnakeStart, $m-($bottomSnakeStart-$bottomSnakek))>min($topSnakeEnd, $topSnakeEnd-$topSnakek)){
	225	+ // the bottom snake is more interesting
	226	+ wfDebug("Limiting diff run time from bottom side\n");
	227	+ $topSnakeStart = $bottomSnakeStart;
	228	+ $topSnakeEnd = $bottomSnakeEnd;
	229	+ $topSnakek = $bottomSnakek;
	230	+ $bestLcsLengthTop = $topSnakeEnd-$topSnakek;
	231	+ $bottomSnakeStart = $bottomSnakeEnd;
	232	+ }else{
	233	+ // the top snake is more interesting
	234	+ wfDebug(" Limiting diff run time from top side\n");
	235	+ $bottomSnakeStart = $topSnakeEnd;
	236	+ $bottomSnakeEnd = $topSnakeEnd;
	237	+ $bottomSnakek = $topSnakek;
	238	+ $bestLcsLengthBottom = $m-($bottomSnakeEnd-$bottomSnakek);
	239	+ }
	240	+ break;
	241	+ }
	242	+ }
	243	+ }
	244	+ ++$p;
	245	+ $overlap[-$p] = $overlap[$delta+$p] = FALSE;
	246	+
	247	+ $min_p_min_1 = -$p-1;
	248	+ $delta_plus_1_plus_p = $delta_plus_1+$p;
	249	+
	250	+ // forward
	251	+ $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] =
	252	+ $snakeBeginForw[$delta_plus_1_plus_p] = $snakeEndForw[$delta_plus_1_plus_p] = $snakekForw[$delta_plus_1_plus_p] = -1;
	253	+ $lcsSizeForw[$min_p_min_1] = $lcsSizeForw[$delta_plus_1_plus_p] = 0;
	254	+
	255	+ $k=-$p;
	256	+ do {
	257	+ $k_plus_1 = $k+1;
	258	+ $k_min_1 = $k-1;
	259	+
	260	+ $fpBelow = $fpForw[$k_min_1]+1;
	261	+ $fpAbove = $fpForw[$k_plus_1];
	262	+ $y = &$fpForw[$k];
	263	+ if($fpBelow>$fpAbove){
	264	+ $oldy = $y = $fpBelow;
	265	+ $lcsSizeForw[$k] = $lcsSizeForw[$k_min_1];
	266	+ $snakeBeginForw[$k] = $snakeBeginForw[$k_min_1];
	267	+ $snakeEndForw[$k] = $snakeEndForw[$k_min_1];
	268	+ $snakekForw[$k] = $snakekForw[$k_min_1];
	269	+ }else{
	270	+ $oldy = $y = $fpAbove;
	271	+ $lcsSizeForw[$k] = $lcsSizeForw[$k_plus_1];
	272	+ $snakeBeginForw[$k] = $snakeBeginForw[$k_plus_1];
	273	+ $snakeEndForw[$k] = $snakeEndForw[$k_plus_1];
	274	+ $snakekForw[$k] = $snakekForw[$k_plus_1];
	275	+ }
	276	+ $x = $y-$k;
	277	+ while($x < $m && $y < $n && $a[$x]===$b[$y]){
	278	+ ++$x;
	279	+ ++$y;
	280	+ }
	281	+ if($y-$oldy>0){
	282	+ $lcsSizeForw[$k] += $y-$oldy;
	283	+ $snakeBeginForw[$k] = $oldy;
	284	+ $snakeEndForw[$k]= $y;
	285	+ $snakekForw[$k] = $k;
	286	+ }
	287	+ if($y>=$fpBack[$k] && !$overlap[$k]){
	288	+ // there is overlap
	289	+ $overlap[$k]=TRUE;
	290	+ $lcsLength = $lcsSizeForw[$k]+$lcsSizeBack[$k];
	291	+ if($y>$fpBack[$k]+1){
	292	+ $snakeoverlap = $y-$fpBack[$k]-1;
	293	+ $lcsLength -= $snakeoverlap;
	294	+ }
	295	+ if($lcsLength>$bestLcsLength){
	296	+ // a better sequence found!
	297	+ $bestLcsLength = $lcsLength;
	298	+
	299	+ $topSnakeStart = $snakeBeginForw[$k];
	300	+ $topSnakeEnd = $snakeEndForw[$k];
	301	+ $topSnakek = $snakekForw[$k];
	302	+
	303	+ // aligned snakes bite (\ )
	304	+ // ( \ \)
	305	+ $bottomSnakeStart = max($snakeEndBack[$k]+1, $topSnakeEnd+max(0,$snakekBack[$k]-$snakekForw[$k]));
	306	+ $bottomSnakeEnd = max($snakeBeginBack[$k]+1, $bottomSnakeStart);
	307	+ $bottomSnakek = $snakekBack[$k];
	308	+
	309	+ if($bottomSnakeEnd<$y){
	310	+ $bottomSnakeStart = $y;
	311	+ $bottomSnakeEnd = $y;
	312	+ $bottomSnakek = $k;
	313	+ }
	314	+
	315	+ $bestLcsLengthTop = $lcsSizeForw[$k]-($snakeEndForw[$k]-$snakeBeginForw[$k]);
	316	+ $bestLcsLengthBottom = $lcsSizeBack[$k]-($snakeBeginBack[$k]-$snakeEndBack[$k]);
	317	+ if($bestKnownLcs==$lcsLength){
	318	+ $fpForw[$k]=$y;
	319	+ break 2;
	320	+ }
	321	+ $maxp=$m_min_1-$bestLcsLength;
	322	+ }
	323	+ }
	324	+ if($k<$delta_min_1){
	325	+ ++$k;
	326	+ }else if($k>$delta){
	327	+ --$k;
	328	+ }else if($k==$delta_min_1){
	329	+ $k = $delta+$p;
	330	+ }else{
	331	+ break;
	332	+ }
	333	+ } while(TRUE);
	334	+
	335	+ // backward
	336	+ $fpBack[$min_p_min_1] = $snakeBeginBack[$min_p_min_1] = $snakeEndBack[$min_p_min_1] = $snakekBack[$min_p_min_1] =
	337	+ $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;
	338	+ $lcsSizeBack[$min_p_min_1] = $lcsSizeBack[$delta_plus_1_plus_p] = 0;
	339	+
	340	+ $k=$delta+$p;
	341	+ do {
	342	+ $k_plus_1 = $k+1;
	343	+ $k_min_1 = $k-1;
	344	+
	345	+ $fpBelow = $fpBack[$k_min_1];
	346	+ $fpAbove = $fpBack[$k_plus_1]-1;
	347	+ $y = &$fpBack[$k];
	348	+ if($fpBelow<$fpAbove){
	349	+ $oldy = $y = $fpBelow;
	350	+ $lcsSizeBack[$k] = $lcsSizeBack[$k_min_1];
	351	+ $snakeBeginBack[$k] = $snakeBeginBack[$k_min_1];
	352	+ $snakeEndBack[$k] = $snakeEndBack[$k_min_1];
	353	+ $snakekBack[$k] = $snakekBack[$k_min_1];
	354	+ }else{
	355	+ $oldy = $y = $fpAbove;
	356	+ $lcsSizeBack[$k] = $lcsSizeBack[$k_plus_1];
	357	+ $snakeBeginBack[$k] = $snakeBeginBack[$k_plus_1];
	358	+ $snakeEndBack[$k] = $snakeEndBack[$k_plus_1];
	359	+ $snakekBack[$k] = $snakekBack[$k_plus_1];
	360	+ }
	361	+ $x = $y-$k;
	362	+ while($x > -1 && $y > -1 && $a[$x]===$b[$y]){
	363	+ --$x;
	364	+ --$y;
	365	+ }
	366	+ if($oldy-$y>0){
	367	+ $lcsSizeBack[$k] += $oldy-$y;
	368	+ $snakeBeginBack[$k] = $oldy;
	369	+ $snakeEndBack[$k] = $y;
	370	+ $snakekBack[$k] = $k;
	371	+ }
	372	+ if($fpForw[$k]>=$y && !$overlap[$k]){
	373	+ // there is overlap
	374	+ $overlap[$k]=TRUE;
	375	+ $lcsLength = $lcsSizeForw[$k]+$lcsSizeBack[$k];
	376	+ if($fpForw[$k]>$y+1){
	377	+ $snakeoverlap = $fpForw[$k]-$y-1;
	378	+ $lcsLength -= $snakeoverlap;
	379	+ }
	380	+ if($lcsLength>$bestLcsLength){
	381	+ // a better sequence found!
	382	+ $bestLcsLength = $lcsLength;
	383	+
	384	+ $topSnakeStart = $snakeBeginForw[$k];
	385	+ $topSnakeEnd = $snakeEndForw[$k];
	386	+ $topSnakek = $snakekForw[$k];
	387	+
	388	+ // aligned snakes bite (\ )
	389	+ // ( \ \)
	390	+ $bottomSnakeStart = max($snakeEndBack[$k]+1, $topSnakeEnd+max(0,$snakekBack[$k]-$snakekForw[$k]));
	391	+ $bottomSnakeEnd = max($snakeBeginBack[$k]+1, $bottomSnakeStart);
	392	+ $bottomSnakek = $snakekBack[$k];
	393	+
	394	+ if($bottomSnakeEnd<$fpForw[$k]){
	395	+ $bottomSnakeStart = $fpForw[$k];
	396	+ $bottomSnakeEnd = $fpForw[$k];
	397	+ $bottomSnakek = $k;
	398	+ }
	399	+
	400	+ $bestLcsLengthTop = $lcsSizeForw[$k]-($snakeEndForw[$k]-$snakeBeginForw[$k]);
	401	+ $bestLcsLengthBottom = $lcsSizeBack[$k]-($snakeBeginBack[$k]-$snakeEndBack[$k]);
	402	+ if($bestKnownLcs==$lcsLength){
	403	+ $fpBack[$k] = $y;
	404	+ break 2;
	405	+ }
	406	+ $maxp=$m_min_1-$bestLcsLength;
	407	+ }
	408	+ }
	409	+ if($k>1){
	410	+ --$k;
	411	+ }else if($k<0){
	412	+ ++$k;
	413	+ }else if($k==1){
	414	+ $k = -$p;
	415	+ }else{
	416	+ break;
	417	+ }
	418	+ } while(TRUE);
	419	+ }
	420	+
	421	+ unset($fpForw, $fpBack, $lcsSizeForw, $lcsSizeBack);
	422	+ unset($snakeBeginForw, $snakeBeginBack, $snakeEndForw, $snakeEndBack, $snakekForw, $snakekBack);
	423	+ unset($overlap);
	424	+
	425	+ // Mark snakes as in LCS
	426	+ $maxi = $offsetx+$topSnakeEnd-$topSnakek;
	427	+ for($i=$offsetx+$topSnakeStart-$topSnakek;$i<$maxi;++$i){
	428	+ $a_inLcs_sym[$i] = TRUE;
	429	+ }
	430	+ $maxi = $offsety+$topSnakeEnd;
	431	+ for($i=$offsety+$topSnakeStart;$i<$maxi;++$i){
	432	+ $b_inLcs_sym[$i] = TRUE;
	433	+ }
	434	+ $maxi = $offsetx+$bottomSnakeEnd-$bottomSnakek;
	435	+ for($i=$offsetx+$bottomSnakeStart-$bottomSnakek;$i<$maxi;++$i){
	436	+ $a_inLcs_sym[$i] = TRUE;
	437	+ }
	438	+ $maxi = $offsety+$bottomSnakeEnd;
	439	+ for($i=$offsety+$bottomSnakeStart;$i<$maxi;++$i){
	440	+ $b_inLcs_sym[$i] = TRUE;
	441	+ }
	442	+
	443	+ $m_t = $topSnakeStart-$topSnakek;
	444	+ $a_t = array_slice($a, 0, $m_t);
	445	+ $b_t = array_slice($b, 0, $topSnakeStart);
	446	+
	447	+ $m_b = $m-($bottomSnakeEnd-$bottomSnakek);
	448	+ $n_b = $n-$bottomSnakeEnd;
	449	+ $a_b = array_slice($a, $bottomSnakeEnd-$bottomSnakek, $m_b);
	450	+ $b_b = array_slice($b, $bottomSnakeEnd, $n_b);
	451	+
	452	+ wikidiff3_diffPart($a_t, $b_t, $a_inLcs, $b_inLcs, $m_t, $topSnakeStart, $offsetx, $offsety, $bestLcsLengthTop, $boundRunningTime, $max_NP_before_bound);
	453	+
	454	+ 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);
	455	+}
	456	+
	457	+class InLcs {
	458	+
	459	+ public $inLcs;
	460	+
	461	+ function __construct($length){
	462	+ $this->inLcs = $length>0 ? array_fill(0,$length,FALSE): array();
	463	+ }
	464	+
	465	+ /**
	466	+ * Get the length of the Longest Common Subsequence (computed)
	467	+ */
	468	+ public function getLcsLength(){
	469	+ return array_sum($this->inLcs);
	470	+ }
	471	+
	472	+}
	473	+?>
\ No newline at end of file
Index: trunk/phase3/includes/DifferenceEngine.php
—	—	@@ -3,6 +3,8 @@
4	4	* @defgroup DifferenceEngine DifferenceEngine
5	5	*/
6	6
	7	+require_once( 'Diff.php' );
	8	+
7	9	/**
8	10	* Constant to indicate diff cache compatibility.
9	11	* Bump this when changing the diff formatting in a way that
—	—	@@ -77,7 +79,7 @@
78	80	global $wgUser, $wgOut, $wgUseExternalEditor, $wgUseRCPatrol;
79	81	wfProfileIn( __METHOD__ );
80	82
81		~~- # If external diffs are enabled both globally and for the user,~~
	83	+ # If external diffs are enabled both globally and for the user,
82	84	# we'll use the application/x-external-editor interface to call
83	85	# an external diff tool like kompare, kdiff3, etc.
84	86	if($wgUseExternalEditor && $wgUser->getOption('externaldiff')) {
—	—	@@ -88,19 +90,19 @@
89	91	$url2=$this->mTitle->getFullURL("action=raw&oldid=".$this->mNewid);
90	92	$special=$wgLang->getNsText(NS_SPECIAL);
91	93	$control=<<<CONTROL
92		~~-[Process]~~
93		~~-Type=Diff text~~
94		~~-Engine=MediaWiki~~
95		~~-Script={$wgServer}{$wgScript}~~
96		~~-Special namespace={$special}~~
	94	+ [Process]
	95	+ Type=Diff text
	96	+ Engine=MediaWiki
	97	+ Script={$wgServer}{$wgScript}
	98	+ Special namespace={$special}
97	99
98		~~-[File]~~
99		~~-Extension=wiki~~
100		~~-URL=$url1~~
	100	+ [File]
	101	+ Extension=wiki
	102	+ URL=$url1
101	103
102		~~-[File 2]~~
103		~~-Extension=wiki~~
104		~~-URL=$url2~~
	104	+ [File 2]
	105	+ Extension=wiki
	106	+ URL=$url2
105	107	CONTROL;
106	108	echo($control);
107	109	return;
—	—	@@ -170,15 +172,15 @@
171	173	// Look for an unpatrolled change corresponding to this diff
172	174	$db = wfGetDB( DB_SLAVE );
173	175	$change = RecentChange::newFromConds(
174		~~- array(~~
175		~~- // Add redundant user,timestamp condition so we can use the existing index~~
	176	+ array(
	177	+ // Add redundant user,timestamp condition so we can use the existing index
176	178	'rc_user_text' => $this->mNewRev->getRawUserText(),
177	179	'rc_timestamp' => $db->timestamp( $this->mNewRev->getTimestamp() ),
178	180	'rc_this_oldid' => $this->mNewid,
179	181	'rc_last_oldid' => $this->mOldid,
180	182	'rc_patrolled' => 0
181		~~- ),~~
182		~~- __METHOD__~~
	183	+ ),
	184	+ __METHOD__
183	185	);
184	186	if( $change instanceof RecentChange ) {
185	187	$rcid = $change->mAttribs['rc_id'];
—	—	@@ -190,8 +192,8 @@
191	193	// Build the link
192	194	if( $rcid ) {
193	195	$patrol = ' <span class="patrollink">[' . $sk->makeKnownLinkObj(
194		~~- $this->mTitle,~~
195		~~- wfMsgHtml( 'markaspatrolleddiff' ),~~
	196	+ $this->mTitle,
	197	+ wfMsgHtml( 'markaspatrolleddiff' ),
196	198	"action=markpatrolled&rcid={$rcid}"
197	199	) . ']</span>';
198	200	} else {
—	—	@@ -225,33 +227,33 @@
226	228	if( $wgUser->isAllowed( 'deleterevision' ) ) {
227	229	$revdel = SpecialPage::getTitleFor( 'Revisiondelete' );
228	230	if( !$this->mOldRev->userCan( Revision::DELETED_RESTRICTED ) ) {
229		~~- // If revision was hidden from sysops~~
	231	+ // If revision was hidden from sysops
230	232	$ldel = wfMsgHtml('rev-delundel');
231	233	} else {
232	234	$ldel = $sk->makeKnownLinkObj( $revdel,
233		~~- wfMsgHtml('rev-delundel'),~~
	235	+ wfMsgHtml('rev-delundel'),
234	236	'target=' . urlencode( $this->mOldRev->mTitle->getPrefixedDbkey() ) .
235	237	'&oldid=' . urlencode( $this->mOldRev->getId() ) );
236	238	// Bolden oversighted content
237	239	if( $this->mOldRev->isDeleted( Revision::DELETED_RESTRICTED ) )
238		~~- $ldel = "<strong>$ldel</strong>";~~
	240	+ $ldel = "<strong>$ldel</strong>";
239	241	}
240	242	$ldel = "   <tt>(<small>$ldel</small>)</tt> ";
241	243	// We don't currently handle well changing the top revision's settings
242	244	if( $this->mNewRev->isCurrent() ) {
243		~~- // If revision was hidden from sysops~~
	245	+ // If revision was hidden from sysops
244	246	$rdel = wfMsgHtml('rev-delundel');
245	247	} else if( !$this->mNewRev->userCan( Revision::DELETED_RESTRICTED ) ) {
246		~~- // If revision was hidden from sysops~~
	248	+ // If revision was hidden from sysops
247	249	$rdel = wfMsgHtml('rev-delundel');
248	250	} else {
249	251	$rdel = $sk->makeKnownLinkObj( $revdel,
250		~~- wfMsgHtml('rev-delundel'),~~
	252	+ wfMsgHtml('rev-delundel'),
251	253	'target=' . urlencode( $this->mNewRev->mTitle->getPrefixedDbkey() ) .
252	254	'&oldid=' . urlencode( $this->mNewRev->getId() ) );
253	255	// Bolden oversighted content
254	256	if( $this->mNewRev->isDeleted( Revision::DELETED_RESTRICTED ) )
255		~~- $rdel = "<strong>$rdel</strong>";~~
	257	+ $rdel = "<strong>$rdel</strong>";
256	258	}
257	259	$rdel = "   <tt>(<small>$rdel</small>)</tt> ";
258	260	}
—	—	@@ -268,7 +270,7 @@
269	271	$this->showDiff( $oldHeader, $newHeader );
270	272
271	273	if ( !$diffOnly )
272		~~- $this->renderNewRevision();~~
	274	+ $this->renderNewRevision();
273	275
274	276	wfProfileOut( __METHOD__ );
275	277	}
—	—	@@ -283,9 +285,9 @@
284	286	$wgOut->addHTML( "<hr /><h2>{$this->mPagetitle}</h2>\n" );
285	287	#add deleted rev tag if needed
286	288	if( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
287		~~- $wgOut->addWikiMsg( 'rev-deleted-text-permission' );~~
	289	+ $wgOut->addWikiMsg( 'rev-deleted-text-permission' );
288	290	} else if( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
289		~~- $wgOut->addWikiMsg( 'rev-deleted-text-view' );~~
	291	+ $wgOut->addWikiMsg( 'rev-deleted-text-view' );
290	292	}
291	293
292	294	if( !$this->mNewRev->isCurrent() ) {
—	—	@@ -310,7 +312,7 @@
311	313	$wgOut->addHtml( "\n</pre>\n" );
312	314	}
313	315	} else
314		~~- $wgOut->addWikiTextTidy( $this->mNewtext );~~
	316	+ $wgOut->addWikiTextTidy( $this->mNewtext );
315	317
316	318	if( !$this->mNewRev->isCurrent() ) {
317	319	$wgOut->parserOptions()->setEditSection( $oldEditSectionSetting );
—	—	@@ -356,9 +358,9 @@
357	359
358	360	$nextlink = $sk->makeKnownLinkObj( $this->mTitle, wfMsgHtml( 'nextdiff' ), 'diff=next&oldid='.$this->mNewid, '', '', 'id="differences-nextlink"' );
359	361	$header = "<div class=\"firstrevisionheader\" style=\"text-align: center\"><strong>{$this->mOldtitle}</strong><br />" .
360		~~- $sk->revUserTools( $this->mNewRev ) . "<br />" .~~
361		~~- $sk->revComment( $this->mNewRev ) . "<br />" .~~
362		~~- $nextlink . "</div>\n";~~
	362	+ $sk->revUserTools( $this->mNewRev ) . "<br />" .
	363	+ $sk->revComment( $this->mNewRev ) . "<br />" .
	364	+ $nextlink . "</div>\n";
363	365
364	366	$wgOut->addHTML( $header );
365	367
—	—	@@ -423,9 +425,9 @@
424	426	wfProfileIn( __METHOD__ );
425	427	// Check if the diff should be hidden from this user
426	428	if ( $this->mOldRev && !$this->mOldRev->userCan(Revision::DELETED_TEXT) ) {
427		~~- return '';~~
	429	+ return '';
428	430	} else if ( $this->mNewRev && !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
429		~~- return '';~~
	431	+ return '';
430	432	}
431	433	// Cacheable?
432	434	$key = false;
—	—	@@ -486,7 +488,7 @@
487	489	dl('php_wikidiff.so');
488	490	}
489	491	return $wgContLang->unsegementForDiff( wikidiff_do_diff( $otext, $ntext, 2 ) ) .
490		~~- $this->debug( 'wikidiff1' );~~
	492	+ $this->debug( 'wikidiff1' );
491	493	}
492	494
493	495	if ( $wgExternalDiffEngine == 'wikidiff2' ) {
—	—	@@ -505,7 +507,7 @@
506	508	return $text;
507	509	}
508	510	}
509		~~- if ( $wgExternalDiffEngine !== false ) {~~
	511	+ if ( $wgExternalDiffEngine != 'wikidiff3' && $wgExternalDiffEngine !== false ) {
510	512	# Diff via the shell
511	513	global $wgTmpDirectory;
512	514	$tempName1 = tempnam( $wgTmpDirectory, 'diff_' );
—	—	@@ -541,9 +543,9 @@
542	544	$diffs = new Diff( $ota, $nta );
543	545	$formatter = new TableDiffFormatter();
544	546	return $wgContLang->unsegmentForDiff( $formatter->format( $diffs ) ) .
545		~~- $this->debug();~~
	547	+ $this->debug();
546	548	}
547		-
	549	+
548	550	/**
549	551	* Generate a debug comment indicating diff generating time,
550	552	* server node, and generator backend.
—	—	@@ -556,10 +558,10 @@
557	559	}
558	560	$data[] = wfTimestamp( TS_DB );
559	561	return "<!-- diff generator: " .
560		~~- implode( " ",~~
561		~~- array_map(~~
	562	+ implode( " ",
	563	+ array_map(
562	564	"htmlspecialchars",
563		~~- $data ) ) .~~
	565	+ $data ) ) .
564	566	" -->\n";
565	567	}
566	568
—	—	@@ -568,7 +570,7 @@
569	571	*/
570	572	function localiseLineNumbers( $text ) {
571	573	return preg_replace_callback( '/<!--LINE (\d+)-->/',
572		~~- array( &$this, 'localiseLineNumbersCb' ), $text );~~
	574	+ array( &$this, 'localiseLineNumbersCb' ), $text );
573	575	}
574	576
575	577	function localiseLineNumbersCb( $matches ) {
—	—	@@ -582,7 +584,7 @@
583	585	*/
584	586	function getMultiNotice() {
585	587	if ( !is_object($this->mOldRev) \|\| !is_object($this->mNewRev) )
586		~~- return '';~~
	588	+ return '';
587	589
588	590	if( !$this->mOldPage->equals( $this->mNewPage ) ) {
589	591	// Comparing two different pages? Count would be meaningless.
—	—	@@ -597,7 +599,7 @@
598	600
599	601	$n = $this->mTitle->countRevisionsBetween( $oldid, $newid );
600	602	if ( !$n )
601		~~- return '';~~
	603	+ return '';
602	604
603	605	return wfMsgExt( 'diff-multi', array( 'parseinline' ), $n );
604	606	}
—	—	@@ -610,19 +612,19 @@
611	613	global $wgOut;
612	614
613	615	$header = "
614		~~- <table class='diff'>~~
615		~~- <col class='diff-marker' />~~
616		~~- <col class='diff-content' />~~
617		~~- <col class='diff-marker' />~~
618		~~- <col class='diff-content' />~~
619		~~- <tr valign='top'>~~
620		~~- <td colspan='2' class='diff-otitle'>{$otitle}</td>~~
621		~~- <td colspan='2' class='diff-ntitle'>{$ntitle}</td>~~
622		~~- </tr>~~
	616	+ <table class='diff'>
	617	+ <col class='diff-marker' />
	618	+ <col class='diff-content' />
	619	+ <col class='diff-marker' />
	620	+ <col class='diff-content' />
	621	+ <tr valign='top'>
	622	+ <td colspan='2' class='diff-otitle'>{$otitle}</td>
	623	+ <td colspan='2' class='diff-ntitle'>{$ntitle}</td>
	624	+ </tr>
623	625	";
624	626
625	627	if ( $multi != '' )
626		~~- $header .= "<tr><td colspan='4' align='center' class='diff-multi'>{$multi}</td></tr>";~~
	628	+ $header .= "<tr><td colspan='4' align='center' class='diff-multi'>{$multi}</td></tr>";
627	629
628	630	return $header . $diff . "</table>";
629	631	}
—	—	@@ -657,10 +659,10 @@
658	660
659	661	// Load the new revision object
660	662	$this->mNewRev = $this->mNewid
661		~~- ? Revision::newFromId( $this->mNewid )~~
662		~~- : Revision::newFromTitle( $this->mTitle );~~
	663	+ ? Revision::newFromId( $this->mNewid )
	664	+ : Revision::newFromTitle( $this->mTitle );
663	665	if( !$this->mNewRev instanceof Revision )
664		~~- return false;~~
	666	+ return false;
665	667
666	668	// Update the new revision ID in case it was 0 (makes life easier doing UI stuff)
667	669	$this->mNewid = $this->mNewRev->getId();
—	—	@@ -688,9 +690,9 @@
689	691	$this->mNewtitle .= " (<a href='$newEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
690	692	}
691	693	if ( !$this->mNewRev->userCan(Revision::DELETED_TEXT) ) {
692		~~- $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";~~
	694	+ $this->mNewtitle = "<span class='history-deleted'>{$this->mPagetitle}</span>";
693	695	} else if ( $this->mNewRev->isDeleted(Revision::DELETED_TEXT) ) {
694		~~- $this->mNewtitle = '<span class="history-deleted">'.$this->mNewtitle.'</span>';~~
	696	+ $this->mNewtitle = '<span class="history-deleted">'.$this->mNewtitle.'</span>';
695	697	}
696	698
697	699	// Load the old revision object
—	—	@@ -722,7 +724,7 @@
723	725	$this->mOldPagetitle = htmlspecialchars( wfMsg( 'revisionasof', $t ) );
724	726
725	727	$this->mOldtitle = "<a href='$oldLink'>{$this->mOldPagetitle}</a>"
726		~~- . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";~~
	728	+ . " (<a href='$oldEdit'>" . wfMsgHtml( $editable ? 'editold' : 'viewsourceold' ) . "</a>)";
727	729	// Add an "undo" link
728	730	$newUndo = $this->mNewPage->escapeLocalUrl( 'action=edit&undoafter=' . $this->mOldid . '&undo=' . $this->mNewid);
729	731	if( $editable && !$this->mOldRev->isDeleted( Revision::DELETED_TEXT ) && !$this->mNewRev->isDeleted( Revision::DELETED_TEXT ) ) {
—	—	@@ -730,9 +732,9 @@
731	733	}
732	734
733	735	if( !$this->mOldRev->userCan( Revision::DELETED_TEXT ) ) {
734		~~- $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';~~
	736	+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldPagetitle . '</span>';
735	737	} else if( $this->mOldRev->isDeleted( Revision::DELETED_TEXT ) ) {
736		~~- $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';~~
	738	+ $this->mOldtitle = '<span class="history-deleted">' . $this->mOldtitle . '</span>';
737	739	}
738	740	}
739	741
—	—	@@ -828,7 +830,7 @@
829	831
830	832	function _DiffOp_Copy ($orig, $closing = false) {
831	833	if (!is_array($closing))
832		~~- $closing = $orig;~~
	834	+ $closing = $orig;
833	835	$this->orig = $orig;
834	836	$this->closing = $closing;
835	837	}
—	—	@@ -892,7 +894,6 @@
893	895	}
894	896	}
895	897
896		-
897	898	/**
898	899	* Class used internally by Diff to actually compute the diffs.
899	900	*
—	—	@@ -911,65 +912,77 @@
912	913	* are my own.
913	914	*
914	915	* Line length limits for robustness added by Tim Starling, 2005-08-31
	916	+ * Alternative implementation added by Guy Van den Broeck, 2008-07-30
915	917	*
916		~~- * @author Geoffrey T. Dairiki, Tim Starling~~
	918	+ * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
917	919	* @private
918	920	* @ingroup DifferenceEngine
919	921	*/
920	922	class _DiffEngine {
	923	+
921	924	const MAX_XREF_LENGTH = 10000;
922	925
923	926	function diff ($from_lines, $to_lines) {
924	927	wfProfileIn( __METHOD__ );
925	928
	929	+ global $wgExternalDiffEngine;
	930	+
926	931	$n_from = sizeof($from_lines);
927	932	$n_to = sizeof($to_lines);
928	933
929		~~- $this->xchanged = $this->ychanged = array();~~
930		~~- $this->xv = $this->yv = array();~~
931		~~- $this->xind = $this->yind = array();~~
932		~~- unset($this->seq);~~
933		~~- unset($this->in_seq);~~
934		~~- unset($this->lcs);~~
	934	+ if($wgExternalDiffEngine == 'wikidiff3'){
	935	+ // wikidiff3
	936	+ list($this->xchanged, $this->ychanged) = wikidiff3_diff($from_lines, $to_lines, TRUE, 100000);
	937	+ }else{
	938	+ // old diff
	939	+ wfProfileIn( __METHOD__ ." - basicdiff");
	940	+ $this->xchanged = $this->ychanged = array();
	941	+ $this->xv = $this->yv = array();
	942	+ $this->xind = $this->yind = array();
	943	+ unset($this->seq);
	944	+ unset($this->in_seq);
	945	+ unset($this->lcs);
935	946
936		~~- // Skip leading common lines.~~
937		~~- for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {~~
938		~~- if ($from_lines[$skip] !== $to_lines[$skip])~~
	947	+ // Skip leading common lines.
	948	+ for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
	949	+ if ($from_lines[$skip] !== $to_lines[$skip])
939	950	break;
940		~~- $this->xchanged[$skip] = $this->ychanged[$skip] = false;~~
941		~~- }~~
942		~~- // Skip trailing common lines.~~
943		~~- $xi = $n_from; $yi = $n_to;~~
944		~~- for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {~~
945		~~- if ($from_lines[$xi] !== $to_lines[$yi])~~
	951	+ $this->xchanged[$skip] = $this->ychanged[$skip] = false;
	952	+ }
	953	+ // Skip trailing common lines.
	954	+ $xi = $n_from; $yi = $n_to;
	955	+ for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
	956	+ if ($from_lines[$xi] !== $to_lines[$yi])
946	957	break;
947		~~- $this->xchanged[$xi] = $this->ychanged[$yi] = false;~~
948		~~- }~~
	958	+ $this->xchanged[$xi] = $this->ychanged[$yi] = false;
	959	+ }
949	960
950		~~- // Ignore lines which do not exist in both files.~~
951		~~- for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {~~
952		~~- $xhash[$this->_line_hash($from_lines[$xi])] = 1;~~
953		~~- }~~
	961	+ // Ignore lines which do not exist in both files.
	962	+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
	963	+ $xhash[$this->_line_hash($from_lines[$xi])] = 1;
	964	+ }
954	965
955		~~- for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {~~
956		~~- $line = $to_lines[$yi];~~
957		~~- if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )~~
	966	+ for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
	967	+ $line = $to_lines[$yi];
	968	+ if ( ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) )
958	969	continue;
959		~~- $yhash[$this->_line_hash($line)] = 1;~~
960		~~- $this->yv[] = $line;~~
961		~~- $this->yind[] = $yi;~~
962		~~- }~~
963		~~- for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {~~
964		~~- $line = $from_lines[$xi];~~
965		~~- if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )~~
	970	+ $yhash[$this->_line_hash($line)] = 1;
	971	+ $this->yv[] = $line;
	972	+ $this->yind[] = $yi;
	973	+ }
	974	+ for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
	975	+ $line = $from_lines[$xi];
	976	+ if ( ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) )
966	977	continue;
967		~~- $this->xv[] = $line;~~
968		~~- $this->xind[] = $xi;~~
	978	+ $this->xv[] = $line;
	979	+ $this->xind[] = $xi;
	980	+ }
	981	+
	982	+ // Find the LCS.
	983	+ $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
	984	+ wfProfileOut( __METHOD__ ." - basicdiff");
969	985	}
970	986
971		~~- // Find the LCS.~~
972		~~- $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));~~
973		-
974	987	// Merge edits when possible
975	988	$this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
976	989	$this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
—	—	@@ -984,28 +997,28 @@
985	998	// Skip matching "snake".
986	999	$copy = array();
987	1000	while ( $xi < $n_from && $yi < $n_to
988		~~- && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {~~
	1001	+ && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
989	1002	$copy[] = $from_lines[$xi++];
990	1003	++$yi;
991	1004	}
992	1005	if ($copy)
993		~~- $edits[] = new _DiffOp_Copy($copy);~~
	1006	+ $edits[] = new _DiffOp_Copy($copy);
994	1007
995	1008	// Find deletes & adds.
996	1009	$delete = array();
997	1010	while ($xi < $n_from && $this->xchanged[$xi])
998		~~- $delete[] = $from_lines[$xi++];~~
	1011	+ $delete[] = $from_lines[$xi++];
999	1012
1000	1013	$add = array();
1001	1014	while ($yi < $n_to && $this->ychanged[$yi])
1002		~~- $add[] = $to_lines[$yi++];~~
	1015	+ $add[] = $to_lines[$yi++];
1003	1016
1004	1017	if ($delete && $add)
1005		~~- $edits[] = new _DiffOp_Change($delete, $add);~~
	1018	+ $edits[] = new _DiffOp_Change($delete, $add);
1006	1019	elseif ($delete)
1007		~~- $edits[] = new _DiffOp_Delete($delete);~~
	1020	+ $edits[] = new _DiffOp_Delete($delete);
1008	1021	elseif ($add)
1009		~~- $edits[] = new _DiffOp_Add($add);~~
	1022	+ $edits[] = new _DiffOp_Add($add);
1010	1023	}
1011	1024	wfProfileOut( __METHOD__ );
1012	1025	return $edits;
—	—	@@ -1022,7 +1035,6 @@
1023	1036	}
1024	1037	}
1025	1038
1026		-
1027	1039	/* Divide the Largest Common Subsequence (LCS) of the sequences
1028	1040	* [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
1029	1041	* sized segments.
—	—	@@ -1040,23 +1052,22 @@
1041	1053	* of the portions it is going to specify.
1042	1054	*/
1043	1055	function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
1044		~~- wfProfileIn( __METHOD__ );~~
1045	1056	$flip = false;
1046	1057
1047	1058	if ($xlim - $xoff > $ylim - $yoff) {
1048	1059	// Things seems faster (I'm not sure I understand why)
1049		~~- // when the shortest sequence in X.~~
1050		~~- $flip = true;~~
	1060	+ // when the shortest sequence in X.
	1061	+ $flip = true;
1051	1062	list ($xoff, $xlim, $yoff, $ylim)
1052	1063	= array( $yoff, $ylim, $xoff, $xlim);
1053	1064	}
1054	1065
1055	1066	if ($flip)
1056		~~- for ($i = $ylim - 1; $i >= $yoff; $i--)~~
1057		~~- $ymatches[$this->xv[$i]][] = $i;~~
	1067	+ for ($i = $ylim - 1; $i >= $yoff; $i--)
	1068	+ $ymatches[$this->xv[$i]][] = $i;
1058	1069	else
1059		~~- for ($i = $ylim - 1; $i >= $yoff; $i--)~~
1060		~~- $ymatches[$this->yv[$i]][] = $i;~~
	1070	+ for ($i = $ylim - 1; $i >= $yoff; $i--)
	1071	+ $ymatches[$this->yv[$i]][] = $i;
1061	1072
1062	1073	$this->lcs = 0;
1063	1074	$this->seq[0]= $yoff - 1;
—	—	@@ -1068,23 +1079,23 @@
1069	1080	for ($chunk = 0; $chunk < $nchunks; $chunk++) {
1070	1081	wfProfileIn( __METHOD__ . "-chunk" );
1071	1082	if ($chunk > 0)
1072		~~- for ($i = 0; $i <= $this->lcs; $i++)~~
1073		~~- $ymids[$i][$chunk-1] = $this->seq[$i];~~
	1083	+ for ($i = 0; $i <= $this->lcs; $i++)
	1084	+ $ymids[$i][$chunk-1] = $this->seq[$i];
1074	1085
1075	1086	$x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
1076	1087	for ( ; $x < $x1; $x++) {
1077	1088	$line = $flip ? $this->yv[$x] : $this->xv[$x];
1078		~~- if (empty($ymatches[$line]))~~
1079		~~- continue;~~
	1089	+ if (empty($ymatches[$line]))
	1090	+ continue;
1080	1091	$matches = $ymatches[$line];
1081	1092	reset($matches);
1082	1093	while (list ($junk, $y) = each($matches))
1083		~~- if (empty($this->in_seq[$y])) {~~
1084		~~- $k = $this->_lcs_pos($y);~~
1085		~~- USE_ASSERTS && assert($k > 0);~~
1086		~~- $ymids[$k] = $ymids[$k-1];~~
1087		~~- break;~~
1088		~~- }~~
	1094	+ if (empty($this->in_seq[$y])) {
	1095	+ $k = $this->_lcs_pos($y);
	1096	+ USE_ASSERTS && assert($k > 0);
	1097	+ $ymids[$k] = $ymids[$k-1];
	1098	+ break;
	1099	+ }
1089	1100	while (list ( /* $junk */, $y) = each($matches)) {
1090	1101	if ($y > $this->seq[$k-1]) {
1091	1102	USE_ASSERTS && assert($y < $this->seq[$k]);
—	—	@@ -1100,7 +1111,6 @@
1101	1112	}
1102	1113	}
1103	1114	}
1104		~~- wfProfileOut( __METHOD__ . "-chunk" );~~
1105	1115	}
1106	1116
1107	1117	$seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
—	—	@@ -1112,13 +1122,10 @@
1113	1123	}
1114	1124	$seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
1115	1125
1116		~~- wfProfileOut( __METHOD__ );~~
1117	1126	return array($this->lcs, $seps);
1118	1127	}
1119	1128
1120	1129	function _lcs_pos ($ypos) {
1121		~~- wfProfileIn( __METHOD__ );~~
1122		-
1123	1130	$end = $this->lcs;
1124	1131	if ($end == 0 \|\| $ypos > $this->seq[$end]) {
1125	1132	$this->seq[++$this->lcs] = $ypos;
—	—	@@ -1131,9 +1138,9 @@
1132	1139	while ($beg < $end) {
1133	1140	$mid = (int)(($beg + $end) / 2);
1134	1141	if ( $ypos > $this->seq[$mid] )
1135		~~- $beg = $mid + 1;~~
	1142	+ $beg = $mid + 1;
1136	1143	else
1137		~~- $end = $mid;~~
	1144	+ $end = $mid;
1138	1145	}
1139	1146
1140	1147	USE_ASSERTS && assert($ypos != $this->seq[$end]);
—	—	@@ -1141,7 +1148,6 @@
1142	1149	$this->in_seq[$this->seq[$end]] = false;
1143	1150	$this->seq[$end] = $ypos;
1144	1151	$this->in_seq[$ypos] = 1;
1145		~~- wfProfileOut( __METHOD__ );~~
1146	1152	return $end;
1147	1153	}
1148	1154
—	—	@@ -1157,24 +1163,22 @@
1158	1164	* All line numbers are origin-0 and discarded lines are not counted.
1159	1165	*/
1160	1166	function _compareseq ($xoff, $xlim, $yoff, $ylim) {
1161		~~- wfProfileIn( __METHOD__ );~~
1162		-
1163	1167	// Slide down the bottom initial diagonal.
1164	1168	while ($xoff < $xlim && $yoff < $ylim
1165		~~- && $this->xv[$xoff] == $this->yv[$yoff]) {~~
	1169	+ && $this->xv[$xoff] == $this->yv[$yoff]) {
1166	1170	++$xoff;
1167	1171	++$yoff;
1168	1172	}
1169	1173
1170	1174	// Slide up the top initial diagonal.
1171	1175	while ($xlim > $xoff && $ylim > $yoff
1172		~~- && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {~~
	1176	+ && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
1173	1177	--$xlim;
1174	1178	--$ylim;
1175	1179	}
1176	1180
1177	1181	if ($xoff == $xlim \|\| $yoff == $ylim)
1178		~~- $lcs = 0;~~
	1182	+ $lcs = 0;
1179	1183	else {
1180	1184	// This is ad hoc but seems to work well.
1181	1185	//$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
—	—	@@ -1188,9 +1192,9 @@
1189	1193	// X and Y sequences have no common subsequence:
1190	1194	// mark all changed.
1191	1195	while ($yoff < $ylim)
1192		~~- $this->ychanged[$this->yind[$yoff++]] = 1;~~
	1196	+ $this->ychanged[$this->yind[$yoff++]] = 1;
1193	1197	while ($xoff < $xlim)
1194		~~- $this->xchanged[$this->xind[$xoff++]] = 1;~~
	1198	+ $this->xchanged[$this->xind[$xoff++]] = 1;
1195	1199	} else {
1196	1200	// Use the partitions to split this problem into subproblems.
1197	1201	reset($seps);
—	—	@@ -1200,7 +1204,6 @@
1201	1205	$pt1 = $pt2;
1202	1206	}
1203	1207	}
1204		~~- wfProfileOut( __METHOD__ );~~
1205	1208	}
1206	1209
1207	1210	/* Adjust inserts/deletes of identical lines to join changes
—	—	@@ -1237,23 +1240,23 @@
1238	1241	* $other_changed[$j] == false.
1239	1242	*/
1240	1243	while ($j < $other_len && $other_changed[$j])
1241		~~- $j++;~~
	1244	+ $j++;
1242	1245
1243	1246	while ($i < $len && ! $changed[$i]) {
1244	1247	USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1245	1248	$i++; $j++;
1246	1249	while ($j < $other_len && $other_changed[$j])
1247		~~- $j++;~~
	1250	+ $j++;
1248	1251	}
1249	1252
1250	1253	if ($i == $len)
1251		~~- break;~~
	1254	+ break;
1252	1255
1253	1256	$start = $i;
1254	1257
1255	1258	// Find the end of this run of changes.
1256	1259	while (++$i < $len && $changed[$i])
1257		~~- continue;~~
	1260	+ continue;
1258	1261
1259	1262	do {
1260	1263	/*
—	—	@@ -1271,10 +1274,10 @@
1272	1275	$changed[--$start] = 1;
1273	1276	$changed[--$i] = false;
1274	1277	while ($start > 0 && $changed[$start - 1])
1275		~~- $start--;~~
	1278	+ $start--;
1276	1279	USE_ASSERTS && assert('$j > 0');
1277	1280	while ($other_changed[--$j])
1278		~~- continue;~~
	1281	+ continue;
1279	1282	USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1280	1283	}
1281	1284
—	—	@@ -1296,14 +1299,14 @@
1297	1300	$changed[$start++] = false;
1298	1301	$changed[$i++] = 1;
1299	1302	while ($i < $len && $changed[$i])
1300		~~- $i++;~~
	1303	+ $i++;
1301	1304
1302	1305	USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
1303	1306	$j++;
1304	1307	if ($j < $other_len && $other_changed[$j]) {
1305	1308	$corresponding = $i;
1306	1309	while ($j < $other_len && $other_changed[$j])
1307		~~- $j++;~~
	1310	+ $j++;
1308	1311	}
1309	1312	}
1310	1313	} while ($runlength != $i - $start);
—	—	@@ -1317,7 +1320,7 @@
1318	1321	$changed[--$i] = 0;
1319	1322	USE_ASSERTS && assert('$j > 0');
1320	1323	while ($other_changed[--$j])
1321		~~- continue;~~
	1324	+ continue;
1322	1325	USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
1323	1326	}
1324	1327	}
—	—	@@ -1376,7 +1379,7 @@
1377	1380	function isEmpty () {
1378	1381	foreach ($this->edits as $edit) {
1379	1382	if ($edit->type != 'copy')
1380		~~- return false;~~
	1383	+ return false;
1381	1384	}
1382	1385	return true;
1383	1386	}
—	—	@@ -1392,7 +1395,7 @@
1393	1396	$lcs = 0;
1394	1397	foreach ($this->edits as $edit) {
1395	1398	if ($edit->type == 'copy')
1396		~~- $lcs += sizeof($edit->orig);~~
	1399	+ $lcs += sizeof($edit->orig);
1397	1400	}
1398	1401	return $lcs;
1399	1402	}
—	—	@@ -1410,7 +1413,7 @@
1411	1414
1412	1415	foreach ($this->edits as $edit) {
1413	1416	if ($edit->orig)
1414		~~- array_splice($lines, sizeof($lines), 0, $edit->orig);~~
	1417	+ array_splice($lines, sizeof($lines), 0, $edit->orig);
1415	1418	}
1416	1419	return $lines;
1417	1420	}
—	—	@@ -1428,7 +1431,7 @@
1429	1432
1430	1433	foreach ($this->edits as $edit) {
1431	1434	if ($edit->closing)
1432		~~- array_splice($lines, sizeof($lines), 0, $edit->closing);~~
	1435	+ array_splice($lines, sizeof($lines), 0, $edit->closing);
1433	1436	}
1434	1437	return $lines;
1435	1438	}
—	—	@@ -1441,21 +1444,21 @@
1442	1445	function _check ($from_lines, $to_lines) {
1443	1446	wfProfileIn( __METHOD__ );
1444	1447	if (serialize($from_lines) != serialize($this->orig()))
1445		~~- trigger_error("Reconstructed original doesn't match", E_USER_ERROR);~~
	1448	+ trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
1446	1449	if (serialize($to_lines) != serialize($this->closing()))
1447		~~- trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);~~
	1450	+ trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
1448	1451
1449	1452	$rev = $this->reverse();
1450	1453	if (serialize($to_lines) != serialize($rev->orig()))
1451		~~- trigger_error("Reversed original doesn't match", E_USER_ERROR);~~
	1454	+ trigger_error("Reversed original doesn't match", E_USER_ERROR);
1452	1455	if (serialize($from_lines) != serialize($rev->closing()))
1453		~~- trigger_error("Reversed closing doesn't match", E_USER_ERROR);~~
	1456	+ trigger_error("Reversed closing doesn't match", E_USER_ERROR);
1454	1457
1455	1458
1456	1459	$prevtype = 'none';
1457	1460	foreach ($this->edits as $edit) {
1458	1461	if ( $prevtype == $edit->type )
1459		~~- trigger_error("Edit sequence is non-optimal", E_USER_ERROR);~~
	1462	+ trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
1460	1463	$prevtype = $edit->type;
1461	1464	}
1462	1465
—	—	@@ -1496,7 +1499,7 @@
1497	1500	* have the same number of elements as $to_lines.
1498	1501	*/
1499	1502	function MappedDiff($from_lines, $to_lines,
1500		~~- $mapped_from_lines, $mapped_to_lines) {~~
	1503	+ $mapped_from_lines, $mapped_to_lines) {
1501	1504	wfProfileIn( __METHOD__ );
1502	1505
1503	1506	assert(sizeof($from_lines) == sizeof($mapped_from_lines));
—	—	@@ -1579,8 +1582,8 @@
1580	1583	$block[] = new _DiffOp_Copy($context);
1581	1584	}
1582	1585	$this->_block($x0, $ntrail + $xi - $x0,
1583		~~- $y0, $ntrail + $yi - $y0,~~
1584		~~- $block);~~
	1586	+ $y0, $ntrail + $yi - $y0,
	1587	+ $block);
1585	1588	$block = false;
1586	1589	}
1587	1590	}
—	—	@@ -1593,21 +1596,21 @@
1594	1597	$y0 = $yi - sizeof($context);
1595	1598	$block = array();
1596	1599	if ($context)
1597		~~- $block[] = new _DiffOp_Copy($context);~~
	1600	+ $block[] = new _DiffOp_Copy($context);
1598	1601	}
1599	1602	$block[] = $edit;
1600	1603	}
1601	1604
1602	1605	if ($edit->orig)
1603		~~- $xi += sizeof($edit->orig);~~
	1606	+ $xi += sizeof($edit->orig);
1604	1607	if ($edit->closing)
1605		~~- $yi += sizeof($edit->closing);~~
	1608	+ $yi += sizeof($edit->closing);
1606	1609	}
1607	1610
1608	1611	if (is_array($block))
1609		~~- $this->_block($x0, $xi - $x0,~~
1610		~~- $y0, $yi - $y0,~~
1611		~~- $block);~~
	1612	+ $this->_block($x0, $xi - $x0,
	1613	+ $y0, $yi - $y0,
	1614	+ $block);
1612	1615
1613	1616	$end = $this->_end_diff();
1614	1617	wfProfileOut( __METHOD__ );
—	—	@@ -1619,15 +1622,15 @@
1620	1623	$this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
1621	1624	foreach ($edits as $edit) {
1622	1625	if ($edit->type == 'copy')
1623		~~- $this->_context($edit->orig);~~
	1626	+ $this->_context($edit->orig);
1624	1627	elseif ($edit->type == 'add')
1625		~~- $this->_added($edit->closing);~~
	1628	+ $this->_added($edit->closing);
1626	1629	elseif ($edit->type == 'delete')
1627		~~- $this->_deleted($edit->orig);~~
	1630	+ $this->_deleted($edit->orig);
1628	1631	elseif ($edit->type == 'change')
1629		~~- $this->_changed($edit->orig, $edit->closing);~~
	1632	+ $this->_changed($edit->orig, $edit->closing);
1630	1633	else
1631		~~- trigger_error('Unknown edit type', E_USER_ERROR);~~
	1634	+ trigger_error('Unknown edit type', E_USER_ERROR);
1632	1635	}
1633	1636	$this->_end_block();
1634	1637	wfProfileOut( __METHOD__ );
—	—	@@ -1645,9 +1648,9 @@
1646	1649
1647	1650	function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1648	1651	if ($xlen > 1)
1649		~~- $xbeg .= "," . ($xbeg + $xlen - 1);~~
	1652	+ $xbeg .= "," . ($xbeg + $xlen - 1);
1650	1653	if ($ylen > 1)
1651		~~- $ybeg .= "," . ($ybeg + $ylen - 1);~~
	1654	+ $ybeg .= "," . ($ybeg + $ylen - 1);
1652	1655
1653	1656	return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
1654	1657	}
—	—	@@ -1661,7 +1664,7 @@
1662	1665
1663	1666	function _lines($lines, $prefix = ' ') {
1664	1667	foreach ($lines as $line)
1665		~~- echo "$prefix $line\n";~~
	1668	+ echo "$prefix $line\n";
1666	1669	}
1667	1670
1668	1671	function _context($lines) {
—	—	@@ -1716,40 +1719,40 @@
1717	1720	$newline = 1;
1718	1721	$retval = array();
1719	1722	foreach($diff->edits as $edit)
1720		~~- switch($edit->type) {~~
1721		~~- case 'add':~~
1722		~~- foreach($edit->closing as $l) {~~
1723		~~- $retval[] = array(~~
	1723	+ switch($edit->type) {
	1724	+ case 'add':
	1725	+ foreach($edit->closing as $l) {
	1726	+ $retval[] = array(
1724	1727	'action' => 'add',
1725	1728	'new'=> $l,
1726	1729	'newline' => $newline++
1727		~~- );~~
1728		~~- }~~
1729		~~- break;~~
1730		~~- case 'delete':~~
1731		~~- foreach($edit->orig as $l) {~~
1732		~~- $retval[] = array(~~
	1730	+ );
	1731	+ }
	1732	+ break;
	1733	+ case 'delete':
	1734	+ foreach($edit->orig as $l) {
	1735	+ $retval[] = array(
1733	1736	'action' => 'delete',
1734	1737	'old' => $l,
1735	1738	'oldline' => $oldline++,
1736		~~- );~~
1737		~~- }~~
1738		~~- break;~~
1739		~~- case 'change':~~
1740		~~- foreach($edit->orig as $i => $l) {~~
1741		~~- $retval[] = array(~~
	1739	+ );
	1740	+ }
	1741	+ break;
	1742	+ case 'change':
	1743	+ foreach($edit->orig as $i => $l) {
	1744	+ $retval[] = array(
1742	1745	'action' => 'change',
1743	1746	'old' => $l,
1744	1747	'new' => @$edit->closing[$i],
1745	1748	'oldline' => $oldline++,
1746	1749	'newline' => $newline++,
1747		~~- );~~
1748		~~- }~~
1749		~~- break;~~
1750		~~- case 'copy':~~
1751		~~- $oldline += count($edit->orig);~~
1752		~~- $newline += count($edit->orig);~~
1753		~~- }~~
	1750	+ );
	1751	+ }
	1752	+ break;
	1753	+ case 'copy':
	1754	+ $oldline += count($edit->orig);
	1755	+ $newline += count($edit->orig);
	1756	+ }
1754	1757	return $retval;
1755	1758	}
1756	1759	}
—	—	@@ -1777,13 +1780,13 @@
1778	1781	function _flushGroup ($new_tag) {
1779	1782	if ($this->_group !== '') {
1780	1783	if ($this->_tag == 'ins')
1781		~~- $this->_line .= '<ins class="diffchange diffchange-inline">' .~~
1782		~~- htmlspecialchars ( $this->_group ) . '</ins>';~~
	1784	+ $this->_line .= '<ins class="diffchange diffchange-inline">' .
	1785	+ htmlspecialchars ( $this->_group ) . '</ins>';
1783	1786	elseif ($this->_tag == 'del')
1784		~~- $this->_line .= '<del class="diffchange diffchange-inline">' .~~
1785		~~- htmlspecialchars ( $this->_group ) . '</del>';~~
	1787	+ $this->_line .= '<del class="diffchange diffchange-inline">' .
	1788	+ htmlspecialchars ( $this->_group ) . '</del>';
1786	1789	else
1787		~~- $this->_line .= htmlspecialchars ( $this->_group );~~
	1790	+ $this->_line .= htmlspecialchars ( $this->_group );
1788	1791	}
1789	1792	$this->_group = '';
1790	1793	$this->_tag = $new_tag;
—	—	@@ -1792,21 +1795,21 @@
1793	1796	function _flushLine ($new_tag) {
1794	1797	$this->_flushGroup($new_tag);
1795	1798	if ($this->_line != '')
1796		~~- array_push ( $this->_lines, $this->_line );~~
	1799	+ array_push ( $this->_lines, $this->_line );
1797	1800	else
1798		~~- # make empty lines visible by inserting an NBSP~~
1799		~~- array_push ( $this->_lines, NBSP );~~
	1801	+ # make empty lines visible by inserting an NBSP
	1802	+ array_push ( $this->_lines, NBSP );
1800	1803	$this->_line = '';
1801	1804	}
1802	1805
1803	1806	function addWords ($words, $tag = '') {
1804	1807	if ($tag != $this->_tag)
1805		~~- $this->_flushGroup($tag);~~
	1808	+ $this->_flushGroup($tag);
1806	1809
1807	1810	foreach ($words as $word) {
1808	1811	// new-line should only come as first char of word.
1809	1812	if ($word == '')
1810		~~- continue;~~
	1813	+ continue;
1811	1814	if ($word[0] == "\n") {
1812	1815	$this->_flushLine($tag);
1813	1816	$word = substr($word, 1);
—	—	@@ -1837,7 +1840,7 @@
1838	1841	list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
1839	1842
1840	1843	$this->MappedDiff($orig_words, $closing_words,
1841		~~- $orig_stripped, $closing_stripped);~~
	1844	+ $orig_stripped, $closing_stripped);
1842	1845	wfProfileOut( __METHOD__ );
1843	1846	}
1844	1847
—	—	@@ -1862,7 +1865,7 @@
1863	1866	} else {
1864	1867	$m = array();
1865	1868	if (preg_match_all('/ ( [^\S\n]+ \| [0-9_A-Za-z\x80-\xff]+ \| . ) (?: (?!< \n) [^\S\n])? /xs',
1866		~~- $line, $m))~~
	1869	+ $line, $m))
1867	1870	{
1868	1871	$words = array_merge( $words, $m[0] );
1869	1872	$stripped = array_merge( $stripped, $m[1] );
—	—	@@ -1879,9 +1882,9 @@
1880	1883
1881	1884	foreach ($this->edits as $edit) {
1882	1885	if ($edit->type == 'copy')
1883		~~- $orig->addWords($edit->orig);~~
	1886	+ $orig->addWords($edit->orig);
1884	1887	elseif ($edit->orig)
1885		~~- $orig->addWords($edit->orig, 'del');~~
	1888	+ $orig->addWords($edit->orig, 'del');
1886	1889	}
1887	1890	$lines = $orig->getLines();
1888	1891	wfProfileOut( __METHOD__ );
—	—	@@ -1894,9 +1897,9 @@
1895	1898
1896	1899	foreach ($this->edits as $edit) {
1897	1900	if ($edit->type == 'copy')
1898		~~- $closing->addWords($edit->closing);~~
	1901	+ $closing->addWords($edit->closing);
1899	1902	elseif ($edit->closing)
1900		~~- $closing->addWords($edit->closing, 'ins');~~
	1903	+ $closing->addWords($edit->closing, 'ins');
1901	1904	}
1902	1905	$lines = $closing->getLines();
1903	1906	wfProfileOut( __METHOD__ );
—	—	@@ -1969,24 +1972,24 @@
1970	1973	function _added( $lines ) {
1971	1974	foreach ($lines as $line) {
1972	1975	echo '<tr>' . $this->emptyLine() .
1973		~~- $this->addedLine( '<ins class="diffchange">' .~~
1974		~~- htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";~~
	1976	+ $this->addedLine( '<ins class="diffchange">' .
	1977	+ htmlspecialchars ( $line ) . '</ins>' ) . "</tr>\n";
1975	1978	}
1976	1979	}
1977	1980
1978	1981	function _deleted($lines) {
1979	1982	foreach ($lines as $line) {
1980	1983	echo '<tr>' . $this->deletedLine( '<del class="diffchange">' .
1981		~~- htmlspecialchars ( $line ) . '</del>' ) .~~
1982		~~- $this->emptyLine() . "</tr>\n";~~
	1984	+ htmlspecialchars ( $line ) . '</del>' ) .
	1985	+ $this->emptyLine() . "</tr>\n";
1983	1986	}
1984	1987	}
1985	1988
1986	1989	function _context( $lines ) {
1987	1990	foreach ($lines as $line) {
1988	1991	echo '<tr>' .
1989		~~- $this->contextLine( htmlspecialchars ( $line ) ) .~~
1990		~~- $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";~~
	1992	+ $this->contextLine( htmlspecialchars ( $line ) ) .
	1993	+ $this->contextLine( htmlspecialchars ( $line ) ) . "</tr>\n";
1991	1994	}
1992	1995	}
1993	1996
—	—	@@ -2003,11 +2006,11 @@
2004	2007	while ( $line = array_shift( $del ) ) {
2005	2008	$aline = array_shift( $add );
2006	2009	echo '<tr>' . $this->deletedLine( $line ) .
2007		~~- $this->addedLine( $aline ) . "</tr>\n";~~
	2010	+ $this->addedLine( $aline ) . "</tr>\n";
2008	2011	}
2009	2012	foreach ($add as $line) { # If any leftovers
2010	2013	echo '<tr>' . $this->emptyLine() .
2011		~~- $this->addedLine( $line ) . "</tr>\n";~~
	2014	+ $this->addedLine( $line ) . "</tr>\n";
2012	2015	}
2013	2016	wfProfileOut( __METHOD__ );
2014	2017	}

Status & tagging log

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