wp-reset / libs / diff / SequenceMatcher.php

SequenceMatcher.php in WP Reset 2.05, at libs/diff/SequenceMatcher.php

742 lines 19.3 KB

Raw Download Zip

1	<?php
2	/**
3	* Sequence matcher for Diff
4	*
5	* PHP version 5
6	*
7	* Copyright (c) 2009 Chris Boulton <chris.boulton@interspire.com>
8	*
9	* All rights reserved.
10	*
11	* Redistribution and use in source and binary forms, with or without
12	* modification, are permitted provided that the following conditions are met:
13	*
14	* - Redistributions of source code must retain the above copyright notice,
15	* this list of conditions and the following disclaimer.
16	* - Redistributions in binary form must reproduce the above copyright notice,
17	* this list of conditions and the following disclaimer in the documentation
18	* and/or other materials provided with the distribution.
19	* - Neither the name of the Chris Boulton nor the names of its contributors
20	* may be used to endorse or promote products derived from this software
21	* without specific prior written permission.
22	*
23	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
24	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
27	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33	* POSSIBILITY OF SUCH DAMAGE.
34	*
35	* @package Diff
36	* @author Chris Boulton <chris.boulton@interspire.com>
37	* @copyright (c) 2009 Chris Boulton
38	* @license New BSD License http://www.opensource.org/licenses/bsd-license.php
39	* @version 1.1
40	* @link http://github.com/chrisboulton/php-diff
41	*/
42
43	class WPR_Diff_SequenceMatcher
44	{
45	/**
46	* @var string\|array Either a string or an array containing a callback function to determine if a line is "junk" or not.
47	*/
48	private $junkCallback = null;
49
50	/**
51	* @var array The first sequence to compare against.
52	*/
53	private $a = null;
54
55	/**
56	* @var array The second sequence.
57	*/
58	private $b = null;
59
60	/**
61	* @var array Array of characters that are considered junk from the second sequence. Characters are the array key.
62	*/
63	private $junkDict = array();
64
65	/**
66	* @var array Array of indices that do not contain junk elements.
67	*/
68	private $b2j = array();
69
70	private $options = array();
71
72	private $defaultOptions = array(
73	'ignoreNewLines' => false,
74	'ignoreWhitespace' => false,
75	'ignoreCase' => false
76	);
77
78	/**
79	* The constructor. With the sequences being passed, they'll be set for the
80	* sequence matcher and it will perform a basic cleanup & calculate junk
81	* elements.
82	*
83	* @param string\|array $a A string or array containing the lines to compare against.
84	* @param string\|array $b A string or array containing the lines to compare.
85	* @param string\|array $junkCallback Either an array or string that references a callback function (if there is one) to determine 'junk' characters.
86	*/
87	public function __construct($a, $b, $junkCallback=null, $options)
88	{
89	$this->a = null;
90	$this->b = null;
91	$this->junkCallback = $junkCallback;
92	$this->setOptions($options);
93	$this->setSequences($a, $b);
94	}
95
96	public function setOptions($options)
97	{
98	$this->options = array_merge($this->defaultOptions, $options);
99	}
100
101	/**
102	* Set the first and second sequences to use with the sequence matcher.
103	*
104	* @param string\|array $a A string or array containing the lines to compare against.
105	* @param string\|array $b A string or array containing the lines to compare.
106	*/
107	public function setSequences($a, $b)
108	{
109	$this->setSeq1($a);
110	$this->setSeq2($b);
111	}
112
113	/**
114	* Set the first sequence ($a) and reset any internal caches to indicate that
115	* when calling the calculation methods, we need to recalculate them.
116	*
117	* @param string\|array $a The sequence to set as the first sequence.
118	*/
119	public function setSeq1($a)
120	{
121	if(!is_array($a)) {
122	$a = str_split($a);
123	}
124	if($a == $this->a) {
125	return;
126	}
127
128	$this->a= $a;
129	$this->matchingBlocks = null;
130	$this->opCodes = null;
131	}
132
133	/**
134	* Set the second sequence ($b) and reset any internal caches to indicate that
135	* when calling the calculation methods, we need to recalculate them.
136	*
137	* @param string\|array $b The sequence to set as the second sequence.
138	*/
139	public function setSeq2($b)
140	{
141	if(!is_array($b)) {
142	$b = str_split($b);
143	}
144	if($b == $this->b) {
145	return;
146	}
147
148	$this->b = $b;
149	$this->matchingBlocks = null;
150	$this->opCodes = null;
151	$this->fullBCount = null;
152	$this->chainB();
153	}
154
155	/**
156	* Generate the internal arrays containing the list of junk and non-junk
157	* characters for the second ($b) sequence.
158	*/
159	private function chainB()
160	{
161	$length = count ($this->b);
162	$this->b2j = array();
163	$popularDict = array();
164
165	for($i = 0; $i < $length; ++$i) {
166	$char = $this->b[$i];
167	if(isset($this->b2j[$char])) {
168	if($length >= 200 && count($this->b2j[$char]) * 100 > $length) {
169	$popularDict[$char] = 1;
170	unset($this->b2j[$char]);
171	}
172	else {
173	$this->b2j[$char][] = $i;
174	}
175	}
176	else {
177	$this->b2j[$char] = array(
178	$i
179	);
180	}
181	}
182
183	// Remove leftovers
184	foreach(array_keys($popularDict) as $char) {
185	unset($this->b2j[$char]);
186	}
187
188	$this->junkDict = array();
189	if(is_callable($this->junkCallback)) {
190	foreach(array_keys($popularDict) as $char) {
191	if(call_user_func($this->junkCallback, $char)) {
192	$this->junkDict[$char] = 1;
193	unset($popularDict[$char]);
194	}
195	}
196
197	foreach(array_keys($this->b2j) as $char) {
198	if(call_user_func($this->junkCallback, $char)) {
199	$this->junkDict[$char] = 1;
200	unset($this->b2j[$char]);
201	}
202	}
203	}
204	}
205
206	/**
207	* Checks if a particular character is in the junk dictionary
208	* for the list of junk characters.
209	*
210	* @return boolean $b True if the character is considered junk. False if not.
211	*/
212	private function isBJunk($b)
213	{
214	if(isset($this->juncDict[$b])) {
215	return true;
216	}
217
218	return false;
219	}
220
221	/**
222	* Find the longest matching block in the two sequences, as defined by the
223	* lower and upper constraints for each sequence. (for the first sequence,
224	* $alo - $ahi and for the second sequence, $blo - $bhi)
225	*
226	* Essentially, of all of the maximal matching blocks, return the one that
227	* startest earliest in $a, and all of those maximal matching blocks that
228	* start earliest in $a, return the one that starts earliest in $b.
229	*
230	* If the junk callback is defined, do the above but with the restriction
231	* that the junk element appears in the block. Extend it as far as possible
232	* by matching only junk elements in both $a and $b.
233	*
234	* @param int $alo The lower constraint for the first sequence.
235	* @param int $ahi The upper constraint for the first sequence.
236	* @param int $blo The lower constraint for the second sequence.
237	* @param int $bhi The upper constraint for the second sequence.
238	* @return array Array containing the longest match that includes the starting position in $a, start in $b and the length/size.
239	*/
240	public function findLongestMatch($alo, $ahi, $blo, $bhi)
241	{
242	$a = $this->a;
243	$b = $this->b;
244
245	$bestI = $alo;
246	$bestJ = $blo;
247	$bestSize = 0;
248
249	$j2Len = array();
250	$nothing = array();
251
252	for($i = $alo; $i < $ahi; ++$i) {
253	$newJ2Len = array();
254	$jDict = $this->arrayGetDefault($this->b2j, $a[$i], $nothing);
255	foreach($jDict as $jKey => $j) {
256	if($j < $blo) {
257	continue;
258	}
259	else if($j >= $bhi) {
260	break;
261	}
262
263	$k = $this->arrayGetDefault($j2Len, $j -1, 0) + 1;
264	$newJ2Len[$j] = $k;
265	if($k > $bestSize) {
266	$bestI = $i - $k + 1;
267	$bestJ = $j - $k + 1;
268	$bestSize = $k;
269	}
270	}
271
272	$j2Len = $newJ2Len;
273	}
274
275	while($bestI > $alo && $bestJ > $blo && !$this->isBJunk($b[$bestJ - 1]) &&
276	!$this->linesAreDifferent($bestI - 1, $bestJ - 1)) {
277	--$bestI;
278	--$bestJ;
279	++$bestSize;
280	}
281
282	while($bestI + $bestSize < $ahi && ($bestJ + $bestSize) < $bhi &&
283	!$this->isBJunk($b[$bestJ + $bestSize]) && !$this->linesAreDifferent($bestI + $bestSize, $bestJ + $bestSize)) {
284	++$bestSize;
285	}
286
287	while($bestI > $alo && $bestJ > $blo && $this->isBJunk($b[$bestJ - 1]) &&
288	!$this->isLineDifferent($bestI - 1, $bestJ - 1)) {
289	--$bestI;
290	--$bestJ;
291	++$bestSize;
292	}
293
294	while($bestI + $bestSize < $ahi && $bestJ + $bestSize < $bhi &&
295	$this->isBJunk($b[$bestJ + $bestSize]) && !$this->linesAreDifferent($bestI + $bestSize, $bestJ + $bestSize)) {
296	++$bestSize;
297	}
298
299	return array(
300	$bestI,
301	$bestJ,
302	$bestSize
303	);
304	}
305
306	/**
307	* Check if the two lines at the given indexes are different or not.
308	*
309	* @param int $aIndex Line number to check against in a.
310	* @param int $bIndex Line number to check against in b.
311	* @return boolean True if the lines are different and false if not.
312	*/
313	public function linesAreDifferent($aIndex, $bIndex)
314	{
315	$lineA = $this->a[$aIndex];
316	$lineB = $this->b[$bIndex];
317
318	if($this->options['ignoreWhitespace']) {
319	$replace = array("\t", ' ');
320	$lineA = str_replace($replace, '', $lineA);
321	$lineB = str_replace($replace, '', $lineB);
322	}
323
324	if($this->options['ignoreCase']) {
325	$lineA = strtolower($lineA);
326	$lineB = strtolower($lineB);
327	}
328
329	if($lineA != $lineB) {
330	return true;
331	}
332
333	return false;
334	}
335
336	/**
337	* Return a nested set of arrays for all of the matching sub-sequences
338	* in the strings $a and $b.
339	*
340	* Each block contains the lower constraint of the block in $a, the lower
341	* constraint of the block in $b and finally the number of lines that the
342	* block continues for.
343	*
344	* @return array Nested array of the matching blocks, as described by the function.
345	*/
346	public function getMatchingBlocks()
347	{
348	if(!empty($this->matchingBlocks)) {
349	return $this->matchingBlocks;
350	}
351
352	$aLength = count($this->a);
353	$bLength = count($this->b);
354
355	$queue = array(
356	array(
357	0,
358	$aLength,
359	0,
360	$bLength
361	)
362	);
363
364	$matchingBlocks = array();
365	while(!empty($queue)) {
366	list($alo, $ahi, $blo, $bhi) = array_pop($queue);
367	$x = $this->findLongestMatch($alo, $ahi, $blo, $bhi);
368	list($i, $j, $k) = $x;
369	if($k) {
370	$matchingBlocks[] = $x;
371	if($alo < $i && $blo < $j) {
372	$queue[] = array(
373	$alo,
374	$i,
375	$blo,
376	$j
377	);
378	}
379
380	if($i + $k < $ahi && $j + $k < $bhi) {
381	$queue[] = array(
382	$i + $k,
383	$ahi,
384	$j + $k,
385	$bhi
386	);
387	}
388	}
389	}
390
391	usort($matchingBlocks, array($this, 'tupleSort'));
392
393	$i1 = 0;
394	$j1 = 0;
395	$k1 = 0;
396	$nonAdjacent = array();
397	foreach($matchingBlocks as $block) {
398	list($i2, $j2, $k2) = $block;
399	if($i1 + $k1 == $i2 && $j1 + $k1 == $j2) {
400	$k1 += $k2;
401	}
402	else {
403	if($k1) {
404	$nonAdjacent[] = array(
405	$i1,
406	$j1,
407	$k1
408	);
409	}
410
411	$i1 = $i2;
412	$j1 = $j2;
413	$k1 = $k2;
414	}
415	}
416
417	if($k1) {
418	$nonAdjacent[] = array(
419	$i1,
420	$j1,
421	$k1
422	);
423	}
424
425	$nonAdjacent[] = array(
426	$aLength,
427	$bLength,
428	0
429	);
430
431	$this->matchingBlocks = $nonAdjacent;
432	return $this->matchingBlocks;
433	}
434
435	/**
436	* Return a list of all of the opcodes for the differences between the
437	* two strings.
438	*
439	* The nested array returned contains an array describing the opcode
440	* which includes:
441	* 0 - The type of tag (as described below) for the opcode.
442	* 1 - The beginning line in the first sequence.
443	* 2 - The end line in the first sequence.
444	* 3 - The beginning line in the second sequence.
445	* 4 - The end line in the second sequence.
446	*
447	* The different types of tags include:
448	* replace - The string from $i1 to $i2 in $a should be replaced by
449	* the string in $b from $j1 to $j2.
450	* delete - The string in $a from $i1 to $j2 should be deleted.
451	* insert - The string in $b from $j1 to $j2 should be inserted at
452	* $i1 in $a.
453	* equal - The two strings with the specified ranges are equal.
454	*
455	* @return array Array of the opcodes describing the differences between the strings.
456	*/
457	public function getOpCodes()
458	{
459	if(!empty($this->opCodes)) {
460	return $this->opCodes;
461	}
462
463	$i = 0;
464	$j = 0;
465	$this->opCodes = array();
466
467	$blocks = $this->getMatchingBlocks();
468	foreach($blocks as $block) {
469	list($ai, $bj, $size) = $block;
470	$tag = '';
471	if($i < $ai && $j < $bj) {
472	$tag = 'replace';
473	}
474	else if($i < $ai) {
475	$tag = 'delete';
476	}
477	else if($j < $bj) {
478	$tag = 'insert';
479	}
480
481	if($tag) {
482	$this->opCodes[] = array(
483	$tag,
484	$i,
485	$ai,
486	$j,
487	$bj
488	);
489	}
490
491	$i = $ai + $size;
492	$j = $bj + $size;
493
494	if($size) {
495	$this->opCodes[] = array(
496	'equal',
497	$ai,
498	$i,
499	$bj,
500	$j
501	);
502	}
503	}
504	return $this->opCodes;
505	}
506
507	/**
508	* Return a series of nested arrays containing different groups of generated
509	* opcodes for the differences between the strings with up to $context lines
510	* of surrounding content.
511	*
512	* Essentially what happens here is any big equal blocks of strings are stripped
513	* out, the smaller subsets of changes are then arranged in to their groups.
514	* This means that the sequence matcher and diffs do not need to include the full
515	* content of the different files but can still provide context as to where the
516	* changes are.
517	*
518	* @param int $context The number of lines of context to provide around the groups.
519	* @return array Nested array of all of the grouped opcodes.
520	*/
521	public function getGroupedOpcodes($context=3)
522	{
523	$opCodes = $this->getOpCodes();
524	if(empty($opCodes)) {
525	$opCodes = array(
526	array(
527	'equal',
528	0,
529	1,
530	0,
531	1
532	)
533	);
534	}
535
536	if($opCodes[0][0] == 'equal') {
537	$opCodes[0] = array(
538	$opCodes[0][0],
539	max($opCodes[0][1], $opCodes[0][2] - $context),
540	$opCodes[0][2],
541	max($opCodes[0][3], $opCodes[0][4] - $context),
542	$opCodes[0][4]
543	);
544	}
545
546	$lastItem = count($opCodes) - 1;
547	if($opCodes[$lastItem][0] == 'equal') {
548	list($tag, $i1, $i2, $j1, $j2) = $opCodes[$lastItem];
549	$opCodes[$lastItem] = array(
550	$tag,
551	$i1,
552	min($i2, $i1 + $context),
553	$j1,
554	min($j2, $j1 + $context)
555	);
556	}
557
558	$maxRange = $context * 2;
559	$groups = array();
560	$group = array();
561	foreach($opCodes as $code) {
562	list($tag, $i1, $i2, $j1, $j2) = $code;
563	if($tag == 'equal' && $i2 - $i1 > $maxRange) {
564	$group[] = array(
565	$tag,
566	$i1,
567	min($i2, $i1 + $context),
568	$j1,
569	min($j2, $j1 + $context)
570	);
571	$groups[] = $group;
572	$group = array();
573	$i1 = max($i1, $i2 - $context);
574	$j1 = max($j1, $j2 - $context);
575	}
576	$group[] = array(
577	$tag,
578	$i1,
579	$i2,
580	$j1,
581	$j2
582	);
583	}
584
585	if(!empty($group) && !(count($group) == 1 && $group[0][0] == 'equal')) {
586	$groups[] = $group;
587	}
588
589	return $groups;
590	}
591
592	/**
593	* Return a measure of the similarity between the two sequences.
594	* This will be a float value between 0 and 1.
595	*
596	* Out of all of the ratio calculation functions, this is the most
597	* expensive to call if getMatchingBlocks or getOpCodes is yet to be
598	* called. The other calculation methods (quickRatio and realquickRatio)
599	* can be used to perform quicker calculations but may be less accurate.
600	*
601	* The ratio is calculated as (2 * number of matches) / total number of
602	* elements in both sequences.
603	*
604	* @return float The calculated ratio.
605	*/
606	public function Ratio()
607	{
608	$matches = array_reduce($this->getMatchingBlocks(), array($this, 'ratioReduce'), 0);
609	return $this->calculateRatio($matches, count ($this->a) + count ($this->b));
610	}
611
612	/**
613	* Helper function to calculate the number of matches for Ratio().
614	*
615	* @param int $sum The running total for the number of matches.
616	* @param array $triple Array containing the matching block triple to add to the running total.
617	* @return int The new running total for the number of matches.
618	*/
619	private function ratioReduce($sum, $triple)
620	{
621	return $sum + ($triple[count($triple) - 1]);
622	}
623
624	/**
625	* Quickly return an upper bound ratio for the similarity of the strings.
626	* This is quicker to compute than Ratio().
627	*
628	* @return float The calculated ratio.
629	*/
630	private function quickRatio()
631	{
632	if($this->fullBCount === null) {
633	$this->fullBCount = array();
634	$bLength = count ($b);
635	for($i = 0; $i < $bLength; ++$i) {
636	$char = $this->b[$i];
637	$this->fullBCount[$char] = $this->arrayGetDefault($this->fullBCount, $char, 0) + 1;
638	}
639	}
640
641	$avail = array();
642	$matches = 0;
643	$aLength = count ($this->a);
644	for($i = 0; $i < $aLength; ++$i) {
645	$char = $this->a[$i];
646	if(isset($avail[$char])) {
647	$numb = $avail[$char];
648	}
649	else {
650	$numb = $this->arrayGetDefault($this->fullBCount, $char, 0);
651	}
652	$avail[$char] = $numb - 1;
653	if($numb > 0) {
654	++$matches;
655	}
656	}
657
658	$this->calculateRatio($matches, count ($this->a) + count ($this->b));
659	}
660
661	/**
662	* Return an upper bound ratio really quickly for the similarity of the strings.
663	* This is quicker to compute than Ratio() and quickRatio().
664	*
665	* @return float The calculated ratio.
666	*/
667	private function realquickRatio()
668	{
669	$aLength = count ($this->a);
670	$bLength = count ($this->b);
671
672	return $this->calculateRatio(min($aLength, $bLength), $aLength + $bLength);
673	}
674
675	/**
676	* Helper function for calculating the ratio to measure similarity for the strings.
677	* The ratio is defined as being 2 * (number of matches / total length)
678	*
679	* @param int $matches The number of matches in the two strings.
680	* @param int $length The length of the two strings.
681	* @return float The calculated ratio.
682	*/
683	private function calculateRatio($matches, $length=0)
684	{
685	if($length) {
686	return 2 * ($matches / $length);
687	}
688	else {
689	return 1;
690	}
691	}
692
693	/**
694	* Helper function that provides the ability to return the value for a key
695	* in an array of it exists, or if it doesn't then return a default value.
696	* Essentially cleaner than doing a series of if(isset()) {} else {} calls.
697	*
698	* @param array $array The array to search.
699	* @param string $key The key to check that exists.
700	* @param mixed $default The value to return as the default value if the key doesn't exist.
701	* @return mixed The value from the array if the key exists or otherwise the default.
702	*/
703	private function arrayGetDefault($array, $key, $default)
704	{
705	if(isset($array[$key])) {
706	return $array[$key];
707	}
708	else {
709	return $default;
710	}
711	}
712
713	/**
714	* Sort an array by the nested arrays it contains. Helper function for getMatchingBlocks
715	*
716	* @param array $a First array to compare.
717	* @param array $b Second array to compare.
718	* @return int -1, 0 or 1, as expected by the usort function.
719	*/
720	private function tupleSort($a, $b)
721	{
722	$max = max(count($a), count($b));
723	for($i = 0; $i < $max; ++$i) {
724	if($a[$i] < $b[$i]) {
725	return -1;
726	}
727	else if($a[$i] > $b[$i]) {
728	return 1;
729	}
730	}
731
732	if(count($a) == $count($b)) {
733	return 0;
734	}
735	else if(count($a) < count($b)) {
736	return -1;
737	}
738	else {
739	return 1;
740	}
741	}
742	}