Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

executable file 2751 lines (2498 sloc) 101.805 kb
/*
* Diff Match and Patch
*
* Copyright 2010 geheimwerk.de.
* http://code.google.com/p/google-diff-match-patch/
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* Author: fraser@google.com (Neil Fraser)
* ObjC port: jan@geheimwerk.de (Jan Weiß)
*/
#import "DiffMatchPatch.h"
#import "NSString+JavaSubstring.h"
#import "NSString+UriCompatibility.h"
#import "NSMutableDictionary+DMPExtensions.h"
#import "DiffMatchPatchCFUtilities.h"
#if !defined(MAX_OF_CONST_AND_DIFF)
// Determines the maximum of two expressions:
// The first is a constant (first parameter) while the second expression is
// the difference between the second and third parameter. The way this is
// calculated prevents integer overflow in the result of the difference.
#define MAX_OF_CONST_AND_DIFF(A,B,C) ((B) <= (C) ? (A) : (B) - (C) + (A))
#endif
// JavaScript-style splice function
void splice(NSMutableArray *input, NSUInteger start, NSUInteger count, NSArray *objects);
/* NSMutableArray * */ void splice(NSMutableArray *input, NSUInteger start, NSUInteger count, NSArray *objects) {
NSRange deletionRange = NSMakeRange(start, count);
if (objects == nil) {
[input removeObjectsInRange:deletionRange];
} else {
[input replaceObjectsInRange:deletionRange withObjectsFromArray:objects];
}
}
@implementation Diff
@synthesize operation;
@synthesize text;
/**
* Constructor. Initializes the diff with the provided values.
* @param operation One of DIFF_INSERT, DIFF_DELETE or DIFF_EQUAL.
* @param text The text being applied.
*/
+ (id)diffWithOperation:(Operation)anOperation
andText:(NSString *)aText;
{
return [[[self alloc] initWithOperation:anOperation andText:aText] autorelease];
}
- (id)initWithOperation:(Operation)anOperation
andText:(NSString *)aText;
{
self = [super init];
if (self) {
self.operation = anOperation;
self.text = aText;
}
return self;
}
- (void)dealloc
{
self.text = nil;
[super dealloc];
}
- (id)copyWithZone:(NSZone *)zone
{
id newDiff = [[[self class] allocWithZone:zone]
initWithOperation:self.operation
andText:self.text];
return newDiff;
}
/**
* Display a human-readable version of this Diff.
* @return text version.
*/
- (NSString *)description
{
NSString *prettyText = [self.text stringByReplacingOccurrencesOfString:@"\n" withString:@"\u00b6"];
NSString *operationName = nil;
switch (self.operation) {
case DIFF_DELETE:
operationName = @"DIFF_DELETE";
break;
case DIFF_INSERT:
operationName = @"DIFF_INSERT";
break;
case DIFF_EQUAL:
operationName = @"DIFF_EQUAL";
break;
default:
break;
}
return [NSString stringWithFormat:@"Diff(%@,\"%@\")", operationName, prettyText];
}
/**
* Is this Diff equivalent to another Diff?
* @param obj Another Diff to compare against.
* @return YES or NO.
*/
- (BOOL)isEqual:(id)obj
{
// If parameter is nil return NO.
if (obj == nil) {
return NO;
}
// If parameter cannot be cast to Diff return NO.
if (![obj isKindOfClass:[Diff class]]) {
return NO;
}
// Return YES if the fields match.
Diff *p = (Diff *)obj;
return p.operation == self.operation && [p.text isEqualToString:self.text];
}
- (BOOL)isEqualToDiff:(Diff *)obj
{
// If parameter is nil return NO.
if (obj == nil) {
return NO;
}
// Return YES if the fields match.
return obj.operation == self.operation && [obj.text isEqualToString:self.text];
}
- (NSUInteger)hash
{
return ([text hash] ^ (NSUInteger)operation);
}
@end
@implementation Patch
@synthesize diffs;
@synthesize start1;
@synthesize start2;
@synthesize length1;
@synthesize length2;
- (id)init
{
self = [super init];
if (self) {
self.diffs = [NSMutableArray array];
}
return self;
}
- (void)dealloc
{
self.diffs = nil;
[super dealloc];
}
- (id)copyWithZone:(NSZone *)zone
{
Patch *newPatch = [[[self class] allocWithZone:zone] init];
newPatch.diffs = [[[NSMutableArray alloc] initWithArray:self.diffs copyItems:YES] autorelease];
newPatch.start1 = self.start1;
newPatch.start2 = self.start2;
newPatch.length1 = self.length1;
newPatch.length2 = self.length2;
return newPatch;
}
/**
* Emulate GNU diff's format.
* Header: @@ -382,8 +481,9 @@
* Indicies are printed as 1-based, not 0-based.
* @return The GNU diff NSString.
*/
- (NSString *)description
{
NSString *coords1;
NSString *coords2;
if (self.length1 == 0) {
coords1 = [NSString stringWithFormat:@"%lu,0",
(unsigned long)self.start1];
} else if (self.length1 == 1) {
coords1 = [NSString stringWithFormat:@"%lu",
(unsigned long)self.start1 + 1];
} else {
coords1 = [NSString stringWithFormat:@"%lu,%lu",
(unsigned long)self.start1 + 1, (unsigned long)self.length1];
}
if (self.length2 == 0) {
coords2 = [NSString stringWithFormat:@"%lu,0",
(unsigned long)self.start2];
} else if (self.length2 == 1) {
coords2 = [NSString stringWithFormat:@"%lu",
(unsigned long)self.start2 + 1];
} else {
coords2 = [NSString stringWithFormat:@"%lu,%lu",
(unsigned long)self.start2 + 1, (unsigned long)self.length2];
}
NSMutableString *text = [NSMutableString stringWithFormat:@"@@ -%@ +%@ @@\n",
coords1, coords2];
// Escape the body of the patch with %xx notation.
for (Diff *aDiff in self.diffs) {
switch (aDiff.operation) {
case DIFF_INSERT:
[text appendString:@"+"];
break;
case DIFF_DELETE:
[text appendString:@"-"];
break;
case DIFF_EQUAL:
[text appendString:@" "];
break;
}
[text appendString:[aDiff.text diff_stringByAddingPercentEscapesForEncodeUriCompatibility]];
[text appendString:@"\n"];
}
return text;
}
@end
@implementation DiffMatchPatch
@synthesize Diff_Timeout;
@synthesize Diff_EditCost;
@synthesize Match_Threshold;
@synthesize Match_Distance;
@synthesize Patch_DeleteThreshold;
@synthesize Patch_Margin;
- (id)init
{
self = [super init];
if (self) {
Diff_Timeout = 1.0f;
Diff_EditCost = 4;
Match_Threshold = 0.5f;
Match_Distance = 1000;
Patch_DeleteThreshold = 0.5f;
Patch_Margin = 4;
Match_MaxBits = 32;
}
return self;
}
- (void)dealloc
{
[super dealloc];
}
#pragma mark Diff Functions
// DIFF FUNCTIONS
/**
* Find the differences between two texts.
* Run a faster, slightly less optimal diff.
* This method allows the 'checklines' of diff_main() to be optional.
* Most of the time checklines is wanted, so default to YES.
* @param text1 Old NSString to be diffed.
* @param text2 New NSString to be diffed.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_mainOfOldString:(NSString *)text1
andNewString:(NSString *)text2;
{
return [self diff_mainOfOldString:text1 andNewString:text2 checkLines:YES];
}
/**
* Find the differences between two texts.
* @param text1 Old string to be diffed.
* @param text2 New string to be diffed.
* @param checklines Speedup flag. If NO, then don't run a
* line-level diff first to identify the changed areas.
* If YES, then run a faster slightly less optimal diff.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_mainOfOldString:(NSString *)text1
andNewString:(NSString *)text2
checkLines:(BOOL)checklines;
{
// Set a deadline by which time the diff must be complete.
NSTimeInterval deadline;
if (Diff_Timeout <= 0) {
deadline = [[NSDate distantFuture] timeIntervalSinceReferenceDate];
} else {
deadline = [[NSDate dateWithTimeIntervalSinceNow:Diff_Timeout] timeIntervalSinceReferenceDate];
}
return [self diff_mainOfOldString:text1 andNewString:text2 checkLines:checklines deadline:deadline];
}
/**
* Find the differences between two texts. Simplifies the problem by
* stripping any common prefix or suffix off the texts before diffing.
* @param text1 Old NSString to be diffed.
* @param text2 New NSString to be diffed.
* @param checklines Speedup flag. If NO, then don't run a
* line-level diff first to identify the changed areas.
* If YES, then run a faster slightly less optimal diff
* @param deadline Time when the diff should be complete by. Used
* internally for recursive calls. Users should set DiffTimeout
* instead.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_mainOfOldString:(NSString *)text1
andNewString:(NSString *)text2
checkLines:(BOOL)checklines
deadline:(NSTimeInterval)deadline;
{
// Check for null inputs.
if (text1 == nil || text2 == nil) {
NSLog(@"Null inputs. (diff_main)");
return nil;
}
// Check for equality (speedup).
NSMutableArray *diffs;
if ([text1 isEqualToString:text2]) {
diffs = [NSMutableArray array];
if (text1.length != 0) {
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:text1]];
}
return diffs;
}
// Trim off common prefix (speedup).
NSUInteger commonlength = (NSUInteger)diff_commonPrefix((CFStringRef)text1, (CFStringRef)text2);
NSString *commonprefix = [text1 substringToIndex:commonlength];
text1 = [text1 substringFromIndex:commonlength];
text2 = [text2 substringFromIndex:commonlength];
// Trim off common suffix (speedup).
commonlength = (NSUInteger)diff_commonSuffix((CFStringRef)text1, (CFStringRef)text2);
NSString *commonsuffix = [text1 substringFromIndex:text1.length - commonlength];
text1 = [text1 substringToIndex:(text1.length - commonlength)];
text2 = [text2 substringToIndex:(text2.length - commonlength)];
// Compute the diff on the middle block.
diffs = [self diff_computeFromOldString:text1 andNewString:text2 checkLines:checklines deadline:deadline];
// Restore the prefix and suffix.
if (commonprefix.length != 0) {
[diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL andText:commonprefix] atIndex:0];
}
if (commonsuffix.length != 0) {
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:commonsuffix]];
}
[self diff_cleanupMerge:diffs];
return diffs;
}
/**
* Determine the common prefix of two strings.
* @param text1 First string.
* @param text2 Second string.
* @return The number of characters common to the start of each string.
*/
- (NSUInteger)diff_commonPrefixOfFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
return (NSUInteger)diff_commonPrefix((CFStringRef)text1, (CFStringRef)text2);
}
/**
* Determine the common suffix of two strings.
* @param text1 First string.
* @param text2 Second string.
* @return The number of characters common to the end of each string.
*/
- (NSUInteger)diff_commonSuffixOfFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
return (NSUInteger)diff_commonSuffix((CFStringRef)text1, (CFStringRef)text2);
}
/**
* Determine if the suffix of one CFStringRef is the prefix of another.
* @param text1 First NSString.
* @param text2 Second NSString.
* @return The number of characters common to the end of the first
* CFStringRef and the start of the second CFStringRef.
*/
- (NSUInteger)diff_commonOverlapOfFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
return (NSUInteger)diff_commonOverlap((CFStringRef)text1, (CFStringRef)text2);
}
/**
* Do the two texts share a substring which is at least half the length of
* the longer text?
* This speedup can produce non-minimal diffs.
* @param text1 First NSString.
* @param text2 Second NSString.
* @return Five element NSString array, containing the prefix of text1, the
* suffix of text1, the prefix of text2, the suffix of text2 and the
* common middle. Or NULL if there was no match.
*/
- (NSArray *)diff_halfMatchOfFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
return [NSMakeCollectable(diff_halfMatchCreate((CFStringRef)text1, (CFStringRef)text2, Diff_Timeout)) autorelease];
}
/**
* Does a substring of shorttext exist within longtext such that the
* substring is at least half the length of longtext?
* @param longtext Longer NSString.
* @param shorttext Shorter NSString.
* @param i Start index of quarter length substring within longtext.
* @return Five element NSArray, containing the prefix of longtext, the
* suffix of longtext, the prefix of shorttext, the suffix of shorttext
* and the common middle. Or nil if there was no match.
*/
- (NSArray *)diff_halfMatchIOfLongString:(NSString *)longtext
andShortString:(NSString *)shorttext
index:(NSInteger)index;
{
return [NSMakeCollectable(diff_halfMatchICreate((CFStringRef)longtext, (CFStringRef)shorttext, (CFIndex)index)) autorelease];
}
/**
* Find the differences between two texts. Assumes that the texts do not
* have any common prefix or suffix.
* @param text1 Old NSString to be diffed.
* @param text2 New NSString to be diffed.
* @param checklines Speedup flag. If NO, then don't run a
* line-level diff first to identify the changed areas.
* If YES, then run a faster slightly less optimal diff.
* @param deadline Time the diff should be complete by.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_computeFromOldString:(NSString *)text1
andNewString:(NSString *)text2
checkLines:(BOOL)checklines
deadline:(NSTimeInterval)deadline;
{
NSMutableArray *diffs = [NSMutableArray array];
if (text1.length == 0) {
// Just add some text (speedup).
[diffs addObject:[Diff diffWithOperation:DIFF_INSERT andText:text2]];
return diffs;
}
if (text2.length == 0) {
// Just delete some text (speedup).
[diffs addObject:[Diff diffWithOperation:DIFF_DELETE andText:text1]];
return diffs;
}
NSString *longtext = text1.length > text2.length ? text1 : text2;
NSString *shorttext = text1.length > text2.length ? text2 : text1;
NSUInteger i = [longtext rangeOfString:shorttext].location;
if (i != NSNotFound) {
// Shorter text is inside the longer text (speedup).
Operation op = (text1.length > text2.length) ? DIFF_DELETE : DIFF_INSERT;
[diffs addObject:[Diff diffWithOperation:op andText:[longtext substringToIndex:i]]];
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:shorttext]];
[diffs addObject:[Diff diffWithOperation:op andText:[longtext substringFromIndex:(i + shorttext.length)]]];
return diffs;
}
if (shorttext.length == 1) {
// Single character string.
// After the previous speedup, the character can't be an equality.
[diffs addObject:[Diff diffWithOperation:DIFF_DELETE andText:text1]];
[diffs addObject:[Diff diffWithOperation:DIFF_INSERT andText:text2]];
return diffs;
}
// Check to see if the problem can be split in two.
NSArray *hm = [NSMakeCollectable(diff_halfMatchCreate((CFStringRef)text1, (CFStringRef)text2, Diff_Timeout)) autorelease];
if (hm != nil) {
NSAutoreleasePool *splitPool = [NSAutoreleasePool new];
// A half-match was found, sort out the return data.
NSString *text1_a = [hm objectAtIndex:0];
NSString *text1_b = [hm objectAtIndex:1];
NSString *text2_a = [hm objectAtIndex:2];
NSString *text2_b = [hm objectAtIndex:3];
NSString *mid_common = [hm objectAtIndex:4];
// Send both pairs off for separate processing.
NSMutableArray *diffs_a = [self diff_mainOfOldString:text1_a andNewString:text2_a checkLines:checklines deadline:deadline];
NSMutableArray *diffs_b = [self diff_mainOfOldString:text1_b andNewString:text2_b checkLines:checklines deadline:deadline];
// Merge the results.
diffs = [diffs_a retain];
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:mid_common]];
[diffs addObjectsFromArray:diffs_b];
[splitPool drain];
return [diffs autorelease];
}
if (checklines && text1.length > 100 && text2.length > 100) {
return [self diff_lineModeFromOldString:text1 andNewString:text2 deadline:deadline];
}
NSAutoreleasePool *bisectPool = [NSAutoreleasePool new];
diffs = [self diff_bisectOfOldString:text1 andNewString:text2 deadline:deadline];
[diffs retain];
[bisectPool drain];
return [diffs autorelease];
}
/**
* Do a quick line-level diff on both strings, then rediff the parts for
* greater accuracy.
* This speedup can produce non-minimal diffs.
* @param text1 Old NSString to be diffed.
* @param text2 New NSString to be diffed.
* @param deadline Time when the diff should be complete by.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_lineModeFromOldString:(NSString *)text1
andNewString:(NSString *)text2
deadline:(NSTimeInterval)deadline;
{
// Scan the text on a line-by-line basis first.
NSArray *b = [self diff_linesToCharsForFirstString:text1 andSecondString:text2];
text1 = (NSString *)[b objectAtIndex:0];
text2 = (NSString *)[b objectAtIndex:1];
NSMutableArray *linearray = (NSMutableArray *)[b objectAtIndex:2];
NSAutoreleasePool *recursePool = [NSAutoreleasePool new];
NSMutableArray *diffs = [self diff_mainOfOldString:text1 andNewString:text2 checkLines:NO deadline:deadline];
[diffs retain];
[recursePool drain];
[diffs autorelease];
// Convert the diff back to original text.
[self diff_chars:diffs toLines:linearray];
// Eliminate freak matches (e.g. blank lines)
[self diff_cleanupSemantic:diffs];
// Rediff any Replacement blocks, this time character-by-character.
// Add a dummy entry at the end.
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:@""]];
NSUInteger thisPointer = 0;
NSUInteger count_delete = 0;
NSUInteger count_insert = 0;
NSString *text_delete = @"";
NSString *text_insert = @"";
while (thisPointer < diffs.count) {
switch (((Diff *)[diffs objectAtIndex:thisPointer]).operation) {
case DIFF_INSERT:
count_insert++;
text_insert = [text_insert stringByAppendingString:((Diff *)[diffs objectAtIndex:thisPointer]).text];
break;
case DIFF_DELETE:
count_delete++;
text_delete = [text_delete stringByAppendingString:((Diff *)[diffs objectAtIndex:thisPointer]).text];
break;
case DIFF_EQUAL:
// Upon reaching an equality, check for prior redundancies.
if (count_delete >= 1 && count_insert >= 1) {
// Delete the offending records and add the merged ones.
NSMutableArray *a = [self diff_mainOfOldString:text_delete andNewString:text_insert checkLines:NO deadline:deadline];
[diffs removeObjectsInRange:NSMakeRange(thisPointer - count_delete - count_insert,
count_delete + count_insert)];
thisPointer = thisPointer - count_delete - count_insert;
NSUInteger insertionIndex = thisPointer;
for (Diff *thisDiff in a) {
[diffs insertObject:thisDiff atIndex:insertionIndex];
insertionIndex++;
}
thisPointer = thisPointer + a.count;
}
count_insert = 0;
count_delete = 0;
text_delete = @"";
text_insert = @"";
break;
}
thisPointer++;
}
[diffs removeLastObject]; // Remove the dummy entry at the end.
return diffs;
}
/**
* Split a text into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one line.
* @param text NSString to encode.
* @param lineArray NSMutableArray of unique strings.
* @param lineHash Map of strings to indices.
* @return Encoded string.
*/
- (NSString *)diff_linesToCharsMungeOfText:(NSString *)text
lineArray:(NSMutableArray *)lineArray
lineHash:(NSMutableDictionary *)lineHash;
{
return [NSMakeCollectable(diff_linesToCharsMungeCFStringCreate((CFStringRef)text,
(CFMutableArrayRef)lineArray,
(CFMutableDictionaryRef)lineHash)) autorelease];
}
/**
* Split a text into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one word (or boundary between words).
* @param text NSString to encode.
* @param wordArray NSMutableArray of unique strings.
* @param wordHash Map of strings to indices.
* @return Encoded string.
*/
- (NSString *)diff_wordsToCharsMungeOfText:(NSString *)text
wordArray:(NSMutableArray *)wordArray
wordHash:(NSMutableDictionary *)wordHash;
{
return [NSMakeCollectable(diff_wordsToCharsMungeCFStringCreate((CFStringRef)text,
(CFMutableArrayRef)wordArray,
(CFMutableDictionaryRef)wordHash)) autorelease];
}
/**
* Split a text into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one sentence.
* @param text NSString to encode.
* @param sentenceArray NSMutableArray of unique strings.
* @param sentenceHash Map of strings to indices.
* @return Encoded string.
*/
- (NSString *)diff_sentencesToCharsMungeOfText:(NSString *)text
sentenceArray:(NSMutableArray *)sentenceArray
sentenceHash:(NSMutableDictionary *)sentenceHash;
{
return [NSMakeCollectable(diff_sentencesToCharsMungeCFStringCreate((CFStringRef)text,
(CFMutableArrayRef)sentenceArray,
(CFMutableDictionaryRef)sentenceHash)) autorelease];
}
/**
* Split a text into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one paragraph.
* @param text NSString to encode.
* @param paragraphArray NSMutableArray of unique strings.
* @param paragraphHash Map of strings to indices.
* @return Encoded string.
*/
- (NSString *)diff_paragraphsToCharsMungeOfText:(NSString *)text
paragraphArray:(NSMutableArray *)paragraphArray
paragraphHash:(NSMutableDictionary *)paragraphHash;
{
return [NSMakeCollectable(diff_paragraphsToCharsMungeCFStringCreate((CFStringRef)text,
(CFMutableArrayRef)paragraphArray,
(CFMutableDictionaryRef)paragraphHash)) autorelease];
}
/**
* Split a text into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one text fragment delimitered by line breaks (including the trailing line break characters if any).
* In this context “line break” does not refere to “something you get when you press the return-key”.
* Instead it the refers to “line break boundaries” as defined in “UAX #14: Unicode Line Breaking Algorithm” (http://www.unicode.org/reports/tr14/).
* @param text NSString to encode.
* @param lineArray NSMutableArray of unique strings.
* @param lineHash Map of strings to indices.
* @return Encoded string.
*/
- (NSString *)diff_lineBreakDelimiteredToCharsMungeOfText:(NSString *)text
lineArray:(NSMutableArray *)lineArray
lineHash:(NSMutableDictionary *)lineHash;
{
return [NSMakeCollectable(diff_lineBreakDelimiteredToCharsMungeCFStringCreate((CFStringRef)text,
(CFMutableArrayRef)lineArray,
(CFMutableDictionaryRef)lineHash)) autorelease];
}
/**
* Find the 'middle snake' of a diff, split the problem in two
* and return the recursively constructed diff.
* See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
* @param text1 Old string to be diffed.
* @param text2 New string to be diffed.
* @param deadline Time at which to bail if not yet complete.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_bisectOfOldString:(NSString *)_text1
andNewString:(NSString *)_text2
deadline:(NSTimeInterval)deadline;
{
#define text1CharacterAtIndex(A) text1_chars[(A)]
#define text2CharacterAtIndex(A) text2_chars[(A)]
#define freeBuffers() if (text1_buffer != NULL) free(text1_buffer);\
if (text2_buffer != NULL) free(text2_buffer);\
free(v1);\
free(v2);
BOOL validDeadline = (deadline != [[NSDate distantFuture] timeIntervalSinceReferenceDate]);
CFStringRef text1 = (CFStringRef)_text1;
CFStringRef text2 = (CFStringRef)_text2;
// Cache the text lengths to prevent multiple calls.
CFIndex text1_length = CFStringGetLength(text1);
CFIndex text2_length = CFStringGetLength(text2);
CFIndex max_d = (text1_length + text2_length + 1) / 2;
CFIndex v_offset = max_d;
CFIndex v_length = 2 * max_d;
CFIndex *v1 = malloc(v_length * sizeof(CFIndex));
CFIndex *v2 = malloc(v_length * sizeof(CFIndex));
for (CFIndex x = 0; x < v_length; x++) {
v1[x] = -1;
v2[x] = -1;
}
v1[v_offset + 1] = 0;
v2[v_offset + 1] = 0;
CFIndex delta = text1_length - text2_length;
// Prepare access to chars arrays for text1 (massive speedup).
const UniChar *text1_chars;
UniChar *text1_buffer = NULL;
diff_CFStringPrepareUniCharBuffer(text1, &text1_chars, &text1_buffer, CFRangeMake(0, text1_length));
// Prepare access to chars arrays for text2 (massive speedup).
const UniChar *text2_chars;
UniChar *text2_buffer = NULL;
diff_CFStringPrepareUniCharBuffer(text2, &text2_chars, &text2_buffer, CFRangeMake(0, text2_length));
// If the total number of characters is odd, then the front path will
// collide with the reverse path.
BOOL front = (delta % 2 != 0);
// Offsets for start and end of k loop.
// Prevents mapping of space beyond the grid.
CFIndex k1start = 0;
CFIndex k1end = 0;
CFIndex k2start = 0;
CFIndex k2end = 0;
NSMutableArray *diffs;
for (CFIndex d = 0; d < max_d; d++) {
// Bail out if deadline is reached.
if (validDeadline && ([NSDate timeIntervalSinceReferenceDate] > deadline)) {
break;
}
// Walk the front path one step.
for (CFIndex k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
CFIndex k1_offset = v_offset + k1;
CFIndex x1;
if ( k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1]) ) {
x1 = v1[k1_offset + 1];
} else {
x1 = v1[k1_offset - 1] + 1;
}
CFIndex y1 = x1 - k1;
while (x1 < text1_length && y1 < text2_length
&& text1CharacterAtIndex(x1) == text2CharacterAtIndex(y1)) {
x1++;
y1++;
}
v1[k1_offset] = x1;
if (x1 > text1_length) {
// Ran off the right of the graph.
k1end += 2;
} else if (y1 > text2_length) {
// Ran off the bottom of the graph.
k1start += 2;
} else if (front) {
CFIndex k2_offset = v_offset + delta - k1;
if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
// Mirror x2 onto top-left coordinate system.
CFIndex x2 = text1_length - v2[k2_offset];
if (x1 >= x2) {
freeBuffers();
// Overlap detected.
return [self diff_bisectSplitOfOldString:_text1
andNewString:_text2
x:x1
y:y1
deadline:deadline];
}
}
}
}
// Walk the reverse path one step.
for (CFIndex k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
CFIndex k2_offset = v_offset + k2;
CFIndex x2;
if ( k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1]) ) {
x2 = v2[k2_offset + 1];
} else {
x2 = v2[k2_offset - 1] + 1;
}
CFIndex y2 = x2 - k2;
while (x2 < text1_length && y2 < text2_length
&& text1CharacterAtIndex(text1_length - x2 - 1)
== text2CharacterAtIndex(text2_length - y2 - 1)) {
x2++;
y2++;
}
v2[k2_offset] = x2;
if (x2 > text1_length) {
// Ran off the left of the graph.
k2end += 2;
} else if (y2 > text2_length) {
// Ran off the top of the graph.
k2start += 2;
} else if (!front) {
CFIndex k1_offset = v_offset + delta - k2;
if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
CFIndex x1 = v1[k1_offset];
CFIndex y1 = v_offset + x1 - k1_offset;
// Mirror x2 onto top-left coordinate system.
x2 = text1_length - x2;
if (x1 >= x2) {
// Overlap detected.
freeBuffers();
return [self diff_bisectSplitOfOldString:_text1
andNewString:_text2
x:x1
y:y1
deadline:deadline];
}
}
}
}
}
freeBuffers();
// Diff took too long and hit the deadline or
// number of diffs equals number of characters, no commonality at all.
diffs = [NSMutableArray array];
[diffs addObject:[Diff diffWithOperation:DIFF_DELETE andText:_text1]];
[diffs addObject:[Diff diffWithOperation:DIFF_INSERT andText:_text2]];
return diffs;
#undef freeTextBuffers
#undef text1CharacterAtIndex
#undef text2CharacterAtIndex
}
/**
* Given the location of the 'middle snake', split the diff in two parts
* and recurse.
* @param text1 Old string to be diffed.
* @param text2 New string to be diffed.
* @param x Index of split point in text1.
* @param y Index of split point in text2.
* @param deadline Time at which to bail if not yet complete.
* @return NSMutableArray of Diff objects.
*/
- (NSMutableArray *)diff_bisectSplitOfOldString:(NSString *)text1
andNewString:(NSString *)text2
x:(NSUInteger)x
y:(NSUInteger)y
deadline:(NSTimeInterval)deadline;
{
NSString *text1a = [text1 substringToIndex:x];
NSString *text2a = [text2 substringToIndex:y];
NSString *text1b = [text1 substringFromIndex:x];
NSString *text2b = [text2 substringFromIndex:y];
// Compute both diffs serially.
NSMutableArray *diffs = [self diff_mainOfOldString:text1a
andNewString:text2a
checkLines:NO
deadline:deadline];
NSMutableArray *diffsb = [self diff_mainOfOldString:text1b
andNewString:text2b
checkLines:NO
deadline:deadline];
[diffs addObjectsFromArray: diffsb];
return diffs;
}
/**
* Split two texts into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one line.
* @param text1 First NSString.
* @param text2 Second NSString.
* @return Three element NSArray, containing the encoded text1, the
* encoded text2 and the NSMutableArray of unique strings. The zeroth element
* of the NSArray of unique strings is intentionally blank.
*/
- (NSArray *)diff_linesToCharsForFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
NSMutableArray *lineArray = [NSMutableArray array]; // NSString objects
CFMutableDictionaryRef lineHash = CFDictionaryCreateMutable(kCFAllocatorDefault, 0, &kCFTypeDictionaryKeyCallBacks, NULL); // keys: NSString, values:raw CFIndex
// e.g. [lineArray objectAtIndex:4] == "Hello\n"
// e.g. [lineHash objectForKey:"Hello\n"] == 4
// "\x00" is a valid character, but various debuggers don't like it.
// So we'll insert a junk entry to avoid generating a nil character.
[lineArray addObject:@""];
NSString *chars1 = NSMakeCollectable(diff_linesToCharsMungeCFStringCreate((CFStringRef)text1,
(CFMutableArrayRef)lineArray,
lineHash));
NSString *chars2 = NSMakeCollectable(diff_linesToCharsMungeCFStringCreate((CFStringRef)text2,
(CFMutableArrayRef)lineArray,
lineHash));
NSArray *result = [NSArray arrayWithObjects:chars1, chars2, lineArray, nil];
[chars1 release];
[chars2 release];
CFRelease(lineHash);
return result;
}
/**
* Split two texts into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one token (or boundary between tokens).
* A token can be a type of text fragment: a word, sentence, paragraph or line.
* The type is determined by the mode object.
* @param text1 First NSString.
* @param text2 Second NSString.
* @param mode value determining the tokenization mode.
* @return Three element NSArray, containing the encoded text1, the
* encoded text2 and the NSMutableArray of unique strings. The zeroth element
* of the NSArray of unique strings is intentionally blank.
*/
- (NSArray *)diff_tokensToCharsForFirstString:(NSString *)text1
andSecondString:(NSString *)text2
mode:(DiffTokenMode)mode;
{
CFOptionFlags tokenizerOptions;
switch (mode) {
case DiffWordTokens:
tokenizerOptions = kCFStringTokenizerUnitWordBoundary;
break;
case DiffSentenceTokens:
tokenizerOptions = kCFStringTokenizerUnitSentence;
break;
case DiffLineBreakDelimiteredTokens:
tokenizerOptions = kCFStringTokenizerUnitLineBreak;
break;
case DiffParagraphTokens:
default:
tokenizerOptions = kCFStringTokenizerUnitParagraph;
break;
}
NSMutableArray *tokenArray = [NSMutableArray array]; // NSString objects
CFMutableDictionaryRef tokenHash = CFDictionaryCreateMutable(kCFAllocatorDefault, 0, &kCFTypeDictionaryKeyCallBacks, NULL); // keys: NSString, values:raw CFIndex
// e.g. [tokenArray objectAtIndex:4] == "Hello"
// e.g. [tokenHash objectForKey:"Hello"] == 4
// "\x00" is a valid character, but various debuggers don't like it.
// So we'll insert a junk entry to avoid generating a nil character.
[tokenArray addObject:@""];
NSString *tokens1 = NSMakeCollectable(diff_tokensToCharsMungeCFStringCreate((CFStringRef)text1,
(CFMutableArrayRef)tokenArray,
tokenHash,
tokenizerOptions));
NSString *tokens2 = NSMakeCollectable(diff_tokensToCharsMungeCFStringCreate((CFStringRef)text2,
(CFMutableArrayRef)tokenArray,
tokenHash,
tokenizerOptions));
NSArray *result = [NSArray arrayWithObjects:tokens1, tokens2, tokenArray, nil];
[tokens1 release];
[tokens2 release];
CFRelease(tokenHash);
return result;
}
/**
* Split two texts into a list of strings. Reduce the texts to a string of
* hashes where each Unicode character represents one word (or boundary between words).
* @param text1 First NSString.
* @param text2 Second NSString.
* @return Three element NSArray, containing the encoded text1, the
* encoded text2 and the NSMutableArray of unique strings. The zeroth element
* of the NSArray of unique strings is intentionally blank.
*/
- (NSArray *)diff_wordsToCharsForFirstString:(NSString *)text1
andSecondString:(NSString *)text2;
{
return [self diff_tokensToCharsForFirstString:text1
andSecondString:text2
mode:DiffWordTokens];
}
/**
* Adapter function.
* @param NSArray of Diff objects.
* @param NSMutableArray of unique strings.
*/
NS_INLINE NSString * diff_charsToTokenString(NSString *charsString, NSArray *tokenArray)
{
CFStringRef text = diff_charsToTokenCFStringCreate((CFStringRef)charsString, (CFArrayRef)tokenArray);
return [NSMakeCollectable(text) autorelease];
}
/**
* Rehydrate an NSString of token hashes to real text tokens.
* @param NSArray of Diff objects.
* @param NSArray of unique strings.
*/
- (NSString *)diff_charsToTokenString:(NSString *)charsString usingTokens:(NSArray *)tokenArray;
{
return diff_charsToTokenString(charsString, tokenArray);
}
/**
* Rehydrate the text in a diff from an NSString of line hashes to real lines
* of text.
* @param NSArray of Diff objects.
* @param NSArray of unique strings.
*/
- (void)diff_chars:(NSArray *)diffs toLines:(NSArray *)lineArray;
{
for (Diff *diff in diffs) {
diff.text = diff_charsToTokenString(diff.text, lineArray);
}
}
/**
* Rehydrate the text in a diff from an NSString of token hashes to real text tokens.
* @param NSArray of Diff objects.
* @param NSArray of unique strings.
*/
- (void)diff_chars:(NSArray *)diffs toTokens:(NSArray *)tokenArray;
{
for (Diff *diff in diffs) {
diff.text = diff_charsToTokenString(diff.text, tokenArray);
}
}
/**
* Reorder and merge like edit sections. Merge equalities.
* Any edit section can move as long as it doesn't cross an equality.
* @param diffs NSMutableArray of Diff objects.
*/
- (void)diff_cleanupMerge:(NSMutableArray *)diffs;
{
#define prevDiff ((Diff *)[diffs objectAtIndex:(thisPointer - 1)])
#define thisDiff ((Diff *)[diffs objectAtIndex:thisPointer])
#define nextDiff ((Diff *)[diffs objectAtIndex:(thisPointer + 1)])
if (diffs.count == 0) {
return;
}
// Add a dummy entry at the end.
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:@""]];
NSUInteger thisPointer = 0;
NSUInteger count_delete = 0;
NSUInteger count_insert = 0;
NSString *text_delete = @"";
NSString *text_insert = @"";
NSUInteger commonlength;
while (thisPointer < diffs.count) {
switch (thisDiff.operation) {
case DIFF_INSERT:
count_insert++;
text_insert = [text_insert stringByAppendingString:thisDiff.text];
thisPointer++;
break;
case DIFF_DELETE:
count_delete++;
text_delete = [text_delete stringByAppendingString:thisDiff.text];
thisPointer++;
break;
case DIFF_EQUAL:
// Upon reaching an equality, check for prior redundancies.
if (count_delete + count_insert > 1) {
if (count_delete != 0 && count_insert != 0) {
// Factor out any common prefixes.
commonlength = (NSUInteger)diff_commonPrefix((CFStringRef)text_insert, (CFStringRef)text_delete);
if (commonlength != 0) {
if ((thisPointer - count_delete - count_insert) > 0 &&
((Diff *)[diffs objectAtIndex:(thisPointer - count_delete - count_insert - 1)]).operation
== DIFF_EQUAL) {
((Diff *)[diffs objectAtIndex:(thisPointer - count_delete - count_insert - 1)]).text
= [((Diff *)[diffs objectAtIndex:(thisPointer - count_delete - count_insert - 1)]).text
stringByAppendingString:[text_insert substringToIndex:commonlength]];
} else {
[diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL
andText:[text_insert substringToIndex:commonlength]]
atIndex:0];
thisPointer++;
}
text_insert = [text_insert substringFromIndex:commonlength];
text_delete = [text_delete substringFromIndex:commonlength];
}
// Factor out any common suffixes.
commonlength = (NSUInteger)diff_commonSuffix((CFStringRef)text_insert, (CFStringRef)text_delete);
if (commonlength != 0) {
thisDiff.text = [[text_insert substringFromIndex:(text_insert.length
- commonlength)] stringByAppendingString:thisDiff.text];
text_insert = [text_insert substringWithRange:NSMakeRange(0,
text_insert.length - commonlength)];
text_delete = [text_delete substringWithRange:NSMakeRange(0,
text_delete.length - commonlength)];
}
}
// Delete the offending records and add the merged ones.
if (count_delete == 0) {
splice(diffs, thisPointer - count_insert,
count_delete + count_insert,
[NSMutableArray arrayWithObject:[Diff diffWithOperation:DIFF_INSERT andText:text_insert]]);
} else if (count_insert == 0) {
splice(diffs, thisPointer - count_delete,
count_delete + count_insert,
[NSMutableArray arrayWithObject:[Diff diffWithOperation:DIFF_DELETE andText:text_delete]]);
} else {
splice(diffs, thisPointer - count_delete - count_insert,
count_delete + count_insert,
[NSMutableArray arrayWithObjects:[Diff diffWithOperation:DIFF_DELETE andText:text_delete],
[Diff diffWithOperation:DIFF_INSERT andText:text_insert], nil]);
}
thisPointer = thisPointer - count_delete - count_insert +
(count_delete != 0 ? 1 : 0) + (count_insert != 0 ? 1 : 0) + 1;
} else if (thisPointer != 0 && prevDiff.operation == DIFF_EQUAL) {
// Merge this equality with the previous one.
prevDiff.text = [prevDiff.text stringByAppendingString:thisDiff.text];
[diffs removeObjectAtIndex:thisPointer];
} else {
thisPointer++;
}
count_insert = 0;
count_delete = 0;
text_delete = @"";
text_insert = @"";
break;
}
}
if (((Diff *)diffs.lastObject).text.length == 0) {
[diffs removeLastObject]; // Remove the dummy entry at the end.
}
// Second pass: look for single edits surrounded on both sides by
// equalities which can be shifted sideways to eliminate an equality.
// e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
BOOL changes = NO;
thisPointer = 1;
// Intentionally ignore the first and last element (don't need checking).
while (thisPointer < (diffs.count - 1)) {
if (prevDiff.operation == DIFF_EQUAL &&
nextDiff.operation == DIFF_EQUAL) {
// This is a single edit surrounded by equalities.
if ([thisDiff.text hasSuffix:prevDiff.text]) {
// Shift the edit over the previous equality.
thisDiff.text = [prevDiff.text stringByAppendingString:
[thisDiff.text substringToIndex:(thisDiff.text.length - prevDiff.text.length)]];
nextDiff.text = [prevDiff.text stringByAppendingString:nextDiff.text];
splice(diffs, thisPointer - 1, 1, nil);
changes = YES;
} else if ([thisDiff.text hasPrefix:nextDiff.text]) {
// Shift the edit over the next equality.
prevDiff.text = [prevDiff.text stringByAppendingString:nextDiff.text];
thisDiff.text = [[thisDiff.text substringFromIndex:nextDiff.text.length] stringByAppendingString:nextDiff.text];
splice(diffs, thisPointer + 1, 1, nil);
changes = YES;
}
}
thisPointer++;
}
// If shifts were made, the diff needs reordering and another shift sweep.
if (changes) {
[self diff_cleanupMerge:diffs];
}
#undef prevDiff
#undef thisDiff
#undef nextDiff
}
/**
* Look for single edits surrounded on both sides by equalities
* which can be shifted sideways to align the edit to a word boundary.
* e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.
* @param diffs NSMutableArray of Diff objects.
*/
- (void)diff_cleanupSemanticLossless:(NSMutableArray *)diffs;
{
#define prevDiff ((Diff *)[diffs objectAtIndex:(thisPointer - 1)])
#define thisDiff ((Diff *)[diffs objectAtIndex:thisPointer])
#define nextDiff ((Diff *)[diffs objectAtIndex:(thisPointer + 1)])
if (diffs.count == 0) {
return;
}
NSUInteger thisPointer = 1;
// Intentionally ignore the first and last element (don't need checking).
while (thisPointer < (diffs.count - 1)) {
if (prevDiff.operation == DIFF_EQUAL && nextDiff.operation == DIFF_EQUAL) {
// This is a single edit surrounded by equalities.
NSString *equality1 = prevDiff.text;
NSString *edit = thisDiff.text;
NSString *equality2 = nextDiff.text;
// First, shift the edit as far left as possible.
NSUInteger commonOffset = (NSUInteger)diff_commonSuffix((CFStringRef)equality1, (CFStringRef)edit);
if (commonOffset > 0) {
NSString *commonString = [edit substringFromIndex:(edit.length - commonOffset)];
equality1 = [equality1 substringToIndex:(equality1.length - commonOffset)];
edit = [commonString stringByAppendingString:[edit substringToIndex:(edit.length - commonOffset)]];
equality2 = [commonString stringByAppendingString:equality2];
}
// Second, step right character by character,
// looking for the best fit.
NSString *bestEquality1 = equality1;
NSString *bestEdit = edit;
NSString *bestEquality2 = equality2;
CFIndex bestScore = diff_cleanupSemanticScore((CFStringRef)equality1, (CFStringRef)edit) +
diff_cleanupSemanticScore((CFStringRef)edit, (CFStringRef)equality2);
while (edit.length != 0 && equality2.length != 0
&& [edit characterAtIndex:0] == [equality2 characterAtIndex:0]) {
equality1 = [equality1 stringByAppendingString:[edit substringToIndex:1]];
edit = [[edit substringFromIndex:1] stringByAppendingString:[equality2 substringToIndex:1]];
equality2 = [equality2 substringFromIndex:1];
CFIndex score = diff_cleanupSemanticScore((CFStringRef)equality1, (CFStringRef)edit) +
diff_cleanupSemanticScore((CFStringRef)edit, (CFStringRef)equality2);
// The >= encourages trailing rather than leading whitespace on edits.
if (score >= bestScore) {
bestScore = score;
bestEquality1 = equality1;
bestEdit = edit;
bestEquality2 = equality2;
}
}
if (prevDiff.text != bestEquality1) {
// We have an improvement, save it back to the diff.
if (bestEquality1.length != 0) {
prevDiff.text = bestEquality1;
} else {
[diffs removeObjectAtIndex:thisPointer - 1];
thisPointer--;
}
thisDiff.text = bestEdit;
if (bestEquality2.length != 0) {
nextDiff.text = bestEquality2;
} else {
[diffs removeObjectAtIndex:thisPointer + 1];
thisPointer--;
}
}
}
thisPointer++;
}
#undef prevDiff
#undef thisDiff
#undef nextDiff
}
/**
* Given two strings, comAdde a score representing whether the internal
* boundary falls on logical boundaries.
* Scores range from 6 (best) to 0 (worst).
* @param one First string.
* @param two Second string.
* @return The score.
*/
- (NSInteger)diff_cleanupSemanticScoreOfFirstString:(NSString *)one
andSecondString:(NSString *)two;
{
return diff_cleanupSemanticScore((CFStringRef)one, (CFStringRef)two);
}
/**
* Reduce the number of edits by eliminating operationally trivial
* equalities.
* @param diffs NSMutableArray of Diff objects.
*/
- (void)diff_cleanupEfficiency:(NSMutableArray *)diffs;
{
#define thisDiff ((Diff *)[diffs objectAtIndex:thisPointer])
#define equalitiesLastValue (diff_CFArrayLastValueAsCFIndex(equalities))
if (diffs.count == 0) {
return;
}
BOOL changes = NO;
// Stack of indices where equalities are found.
CFMutableArrayRef equalities = CFArrayCreateMutable(kCFAllocatorDefault, 0, NULL);
// Always equal to equalities.lastObject.text
NSString *lastequality = nil;
CFIndex thisPointer = 0; // Index of current position.
// Is there an insertion operation before the last equality.
BOOL pre_ins = NO;
// Is there a deletion operation before the last equality.
BOOL pre_del = NO;
// Is there an insertion operation after the last equality.
BOOL post_ins = NO;
// Is there a deletion operation after the last equality.
BOOL post_del = NO;
NSUInteger indexToChange;
Diff *diffToChange;
while (thisPointer < (CFIndex)diffs.count) {
if (thisDiff.operation == DIFF_EQUAL) { // Equality found.
if (thisDiff.text.length < Diff_EditCost && (post_ins || post_del)) {
// Candidate found.
CFArrayAppendValue(equalities, (void *)thisPointer);
pre_ins = post_ins;
pre_del = post_del;
lastequality = thisDiff.text;
} else {
// Not a candidate, and can never become one.
CFArrayRemoveAllValues(equalities);
lastequality = nil;
}
post_ins = post_del = NO;
} else { // An insertion or deletion.
if (thisDiff.operation == DIFF_DELETE) {
post_del = YES;
} else {
post_ins = YES;
}
/*
* Five types to be split:
* <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
* <ins>A</ins>X<ins>C</ins><del>D</del>
* <ins>A</ins><del>B</del>X<ins>C</ins>
* <ins>A</del>X<ins>C</ins><del>D</del>
* <ins>A</ins><del>B</del>X<del>C</del>
*/
if ((lastequality != nil)
&& ((pre_ins && pre_del && post_ins && post_del)
|| ((lastequality.length < Diff_EditCost / 2)
&& ((pre_ins ? 1 : 0) + (pre_del ? 1 : 0) + (post_ins ? 1 : 0)
+ (post_del ? 1 : 0)) == 3))) {
// Duplicate record.
[diffs insertObject:[Diff diffWithOperation:DIFF_DELETE andText:lastequality]
atIndex:equalitiesLastValue];
// Change second copy to insert.
indexToChange = equalitiesLastValue + 1;
diffToChange = [diffs objectAtIndex:indexToChange];
// The following assumes, that the diff we are changing is currently not used in a collection where its hash determines its position (e.g. a dictionary)
diffToChange.operation = DIFF_INSERT;
diff_CFArrayRemoveLastValue(equalities); // Throw away the equality we just deleted.
lastequality = nil;
if (pre_ins && pre_del) {
// No changes made which could affect previous entry, keep going.
post_ins = post_del = YES;
CFArrayRemoveAllValues(equalities);
} else {
if (CFArrayGetCount(equalities) > 0) {
diff_CFArrayRemoveLastValue(equalities);
}
thisPointer = CFArrayGetCount(equalities) > 0 ? equalitiesLastValue : -1;
post_ins = post_del = NO;
}
changes = YES;
}
}
thisPointer++;
}
if (changes) {
[self diff_cleanupMerge:diffs];
}
CFRelease(equalities);
#undef thisDiff
#undef equalitiesLastValue
}
/**
* Convert a Diff list into a pretty HTML report.
* @param diffs NSMutableArray of Diff objects.
* @return HTML representation.
*/
- (NSString *)diff_prettyHtml:(NSMutableArray *)diffs;
{
NSMutableString *html = [NSMutableString string];
for (Diff *aDiff in diffs) {
NSMutableString *text = [[aDiff.text mutableCopy] autorelease];
[text replaceOccurrencesOfString:@"&" withString:@"&amp;" options:NSLiteralSearch range:NSMakeRange(0, text.length)];
[text replaceOccurrencesOfString:@"<" withString:@"&lt;" options:NSLiteralSearch range:NSMakeRange(0, text.length)];
[text replaceOccurrencesOfString:@">" withString:@"&gt;" options:NSLiteralSearch range:NSMakeRange(0, text.length)];
[text replaceOccurrencesOfString:@"\n" withString:@"&para;<br>" options:NSLiteralSearch range:NSMakeRange(0, text.length)];
switch (aDiff.operation) {
case DIFF_INSERT:
[html appendFormat:@"<ins style=\"background:#e6ffe6;\">%@</ins>", text];
break;
case DIFF_DELETE:
[html appendFormat:@"<del style=\"background:#ffe6e6;\">%@</del>", text];
break;
case DIFF_EQUAL:
[html appendFormat:@"<span>%@</span>", text];
break;
}
}
return html;
}
/**
* Compute and return the source text (all equalities and deletions).
* @param diffs NSMutableArray of Diff objects.
* @return Source text.
*/
- (NSString *)diff_text1:(NSMutableArray *)diffs;
{
NSMutableString *text = [NSMutableString string];
for (Diff *aDiff in diffs) {
if (aDiff.operation != DIFF_INSERT) {
[text appendString:aDiff.text];
}
}
return text;
}
/**
* Compute and return the destination text (all equalities and insertions).
* @param diffs NSMutableArray of Diff objects.
* @return Destination text.
*/
- (NSString *)diff_text2:(NSMutableArray *)diffs;
{
NSMutableString *text = [NSMutableString string];
for (Diff *aDiff in diffs) {
if (aDiff.operation != DIFF_DELETE) {
[text appendString:aDiff.text];
}
}
return text;
}
/**
* Crush the diff into an encoded NSString which describes the operations
* required to transform text1 into text2.
* E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'.
* Operations are tab-separated. Inserted text is escaped using %xx
* notation.
* @param diffs NSMutableArray of Diff objects.
* @return Delta text.
*/
- (NSString *)diff_toDelta:(NSMutableArray *)diffs;
{
NSMutableString *delta = [NSMutableString string];
for (Diff *aDiff in diffs) {
switch (aDiff.operation) {
case DIFF_INSERT:
[delta appendFormat:@"+%@\t", [[aDiff.text diff_stringByAddingPercentEscapesForEncodeUriCompatibility]
stringByReplacingOccurrencesOfString:@"%20" withString:@" "]];
break;
case DIFF_DELETE:
[delta appendFormat:@"-%" PRId32 "\t", (int32_t)aDiff.text.length];
break;
case DIFF_EQUAL:
[delta appendFormat:@"=%" PRId32 "\t", (int32_t)aDiff.text.length];
break;
}
}
if (delta.length != 0) {
// Strip off trailing tab character.
return [delta substringToIndex:(delta.length-1)];
}
return delta;
}
/**
* Given the original text1, and an encoded NSString which describes the
* operations required to transform text1 into text2, compute the full diff.
* @param text1 Source NSString for the diff.
* @param delta Delta text.
* @param error NSError if invalid input.
* @return NSMutableArray of Diff objects or nil if invalid.
*/
- (NSMutableArray *)diff_fromDeltaWithText:(NSString *)text1
andDelta:(NSString *)delta
error:(NSError **)error;
{
NSMutableArray *diffs = [NSMutableArray array];
NSUInteger thisPointer = 0; // Cursor in text1
NSArray *tokens = [delta componentsSeparatedByString:@"\t"];
NSInteger n;
NSDictionary *errorDetail = nil;
for (NSString *token in tokens) {
if (token.length == 0) {
// Blank tokens are ok (from a trailing \t).
continue;
}
// Each token begins with a one character parameter which specifies the
// operation of this token (delete, insert, equality).
NSString *param = [token substringFromIndex:1];
switch ([token characterAtIndex:0]) {
case '+':
param = [param diff_stringByReplacingPercentEscapesForEncodeUriCompatibility];
if (param == nil) {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Invalid character in diff_fromDelta: %@", @"Error"), param],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:99 userInfo:errorDetail];
}
return nil;
}
[diffs addObject:[Diff diffWithOperation:DIFF_INSERT andText:param]];
break;
case '-':
// Fall through.
case '=':
n = [param integerValue];
if (n == 0) {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Invalid number in diff_fromDelta: %@", @"Error"), param],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:100 userInfo:errorDetail];
}
return nil;
} else if (n < 0) {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Negative number in diff_fromDelta: %@", @"Error"), param],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:101 userInfo:errorDetail];
}
return nil;
}
NSString *text;
NSRange text1Range = NSMakeRange(0, text1.length);
if (NSLocationInRange(thisPointer, text1Range) && NSLocationInRange(thisPointer+(NSUInteger)n-1, text1Range)) {
text = [text1 substringWithRange:NSMakeRange(thisPointer, (NSUInteger)n)];
thisPointer += (NSUInteger)n;
}
else {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Delta length (%lu) larger than source text length (%lu).", @"Error"),
(unsigned long)thisPointer, (unsigned long)text1.length],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:102 userInfo:errorDetail];
}
return nil;
}
if ([token characterAtIndex:0] == '=') {
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:text]];
} else {
[diffs addObject:[Diff diffWithOperation:DIFF_DELETE andText:text]];
}
break;
default:
// Anything else is an error.
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Invalid diff operation in diff_fromDelta: %C", @"Error"),
[token characterAtIndex:0]],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:102 userInfo:errorDetail];
}
return nil;
}
}
if (thisPointer != text1.length) {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Delta length (%lu) smaller than source text length (%lu).", @"Error"),
(unsigned long)thisPointer, (unsigned long)text1.length],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:103 userInfo:errorDetail];
}
return nil;
}
return diffs;
}
/**
* loc is a location in text1, compute and return the equivalent location in
* text2.
* e.g. "The cat" vs "The big cat", 1->1, 5->8
* @param diffs NSMutableArray of Diff objects.
* @param loc Location within text1.
* @return Location within text2.
*/
- (NSUInteger)diff_xIndexIn:(NSMutableArray *)diffs
location:(NSUInteger) loc;
{
NSUInteger chars1 = 0;
NSUInteger chars2 = 0;
NSUInteger last_chars1 = 0;
NSUInteger last_chars2 = 0;
Diff *lastDiff = nil;
for (Diff *aDiff in diffs) {
if (aDiff.operation != DIFF_INSERT) {
// Equality or deletion.
chars1 += aDiff.text.length;
}
if (aDiff.operation != DIFF_DELETE) {
// Equality or insertion.
chars2 += aDiff.text.length;
}
if (chars1 > loc) {
// Overshot the location.
lastDiff = aDiff;
break;
}
last_chars1 = chars1;
last_chars2 = chars2;
}
if (lastDiff != nil && lastDiff.operation == DIFF_DELETE) {
// The location was deleted.
return last_chars2;
}
// Add the remaining character length.
return last_chars2 + (loc - last_chars1);
}
/**
* Compute the Levenshtein distance; the number of inserted, deleted or
* substituted characters.
* @param diffs NSMutableArray of Diff objects.
* @return Number of changes.
*/
- (NSUInteger)diff_levenshtein:(NSMutableArray *)diffs;
{
NSUInteger levenshtein = 0;
NSUInteger insertions = 0;
NSUInteger deletions = 0;
for (Diff *aDiff in diffs) {
switch (aDiff.operation) {
case DIFF_INSERT:
insertions += aDiff.text.length;
break;
case DIFF_DELETE:
deletions += aDiff.text.length;
break;
case DIFF_EQUAL:
// A deletion and an insertion is one substitution.
levenshtein += MAX(insertions, deletions);
insertions = 0;
deletions = 0;
break;
}
}
levenshtein += MAX(insertions, deletions);
return levenshtein;
}
/**
* Reduce the number of edits by eliminating semantically trivial
* equalities.
* @param diffs NSMutableArray of Diff objects.
*/
- (void)diff_cleanupSemantic:(NSMutableArray *)diffs;
{
#define prevDiff ((Diff *)[diffs objectAtIndex:(thisPointer - 1)])
#define thisDiff ((Diff *)[diffs objectAtIndex:thisPointer])
#define nextDiff ((Diff *)[diffs objectAtIndex:(thisPointer + 1)])
#define equalitiesLastValue (diff_CFArrayLastValueAsCFIndex(equalities))
if (diffs == nil || diffs.count == 0) {
return;
}
BOOL changes = NO;
// Stack of indices where equalities are found.
CFMutableArrayRef equalities = CFArrayCreateMutable(kCFAllocatorDefault, 0, NULL);
// Always equal to [diffs objectAtIndex:equalitiesLastValue].text
NSString *lastequality = nil;
NSUInteger thisPointer = 0; // Index of current position.
// Number of characters that changed prior to the equality.
NSUInteger length_insertions1 = 0;
NSUInteger length_deletions1 = 0;
// Number of characters that changed after the equality.
NSUInteger length_insertions2 = 0;
NSUInteger length_deletions2 = 0;
NSUInteger indexToChange;
Diff *diffToChange;
while (thisPointer < diffs.count) {
if (thisDiff.operation == DIFF_EQUAL) { // Equality found.
CFArrayAppendValue(equalities, (void *)thisPointer);
length_insertions1 = length_insertions2;
length_deletions1 = length_deletions2;
length_insertions2 = 0;
length_deletions2 = 0;
lastequality = thisDiff.text;
} else { // an insertion or deletion
if (thisDiff.operation == DIFF_INSERT) {
length_insertions2 += thisDiff.text.length;
} else {
length_deletions2 += thisDiff.text.length;
}
// Eliminate an equality that is smaller or equal to the edits on both
// sides of it.
if (lastequality != nil
&& (lastequality.length <= MAX(length_insertions1, length_deletions1))
&& (lastequality.length <= MAX(length_insertions2, length_deletions2))) {
// Duplicate record.
[diffs insertObject:[Diff diffWithOperation:DIFF_DELETE andText:lastequality] atIndex:equalitiesLastValue];
// Change second copy to insert.
indexToChange = equalitiesLastValue + 1;
diffToChange = [diffs objectAtIndex:indexToChange];
// The following assumes, that the diff we are changing is currently not used in a collection where its hash determines its position (e.g. a dictionary)
diffToChange.operation = DIFF_INSERT;
// Throw away the equality we just deleted.
diff_CFArrayRemoveLastValue(equalities);
if (CFArrayGetCount(equalities) > 0) {
diff_CFArrayRemoveLastValue(equalities);
}
// Setting an unsigned value to -1 may seem weird to some,
// but we will pass thru a ++ below:
// => overflow => 0
thisPointer = CFArrayGetCount(equalities) > 0 ? equalitiesLastValue : -1;
length_insertions1 = 0; // Reset the counters.
length_deletions1 = 0;
length_insertions2 = 0;
length_deletions2 = 0;
lastequality = nil;
changes = YES;
}
}
thisPointer++;
}
// Normalize the diff.
if (changes) {
[self diff_cleanupMerge:diffs];
}
[self diff_cleanupSemanticLossless:diffs];
// Jan: someDiff.text will NOT retain and autorelease the NSString object.
// This is why “prevDiff.text = ” below can cause it’s previous value to be deallocated
// instead of just released as one would expect without taking the above into account.
// Thus we need to retain its previous value before “prevDiff.text = ” and release afterwards.
// Alternatively, we could remove the nonatomic from the “text” @property definition.
// This would cause much more of a perfomance hit then warranted, though.
// Find any overlaps between deletions and insertions.
// e.g: <del>abcxxx</del><ins>xxxdef</ins>
// -> <del>abc</del>xxx<ins>def</ins>
// e.g: <del>xxxabc</del><ins>defxxx</ins>
// -> <ins>def</ins>xxx<del>abc</del>
// Only extract an overlap if it is as big as the edit ahead or behind it.
thisPointer = 1;
while (thisPointer < diffs.count) {
if (prevDiff.operation == DIFF_DELETE && thisDiff.operation == DIFF_INSERT) {
NSString *deletion = prevDiff.text;
NSString *insertion = thisDiff.text;
NSUInteger overlap_length1 = (NSUInteger)diff_commonOverlap((CFStringRef)deletion, (CFStringRef)insertion);
NSUInteger overlap_length2 = (NSUInteger)diff_commonOverlap((CFStringRef)insertion, (CFStringRef)deletion);
if (overlap_length1 >= overlap_length2) {
if (overlap_length1 >= deletion.length / 2.0f ||
overlap_length1 >= insertion.length / 2.0f) {
// Overlap found.
// Insert an equality and trim the surrounding edits.
[diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL
andText:[insertion substringToIndex:overlap_length1]]
atIndex:thisPointer];
[insertion retain];
prevDiff.text = [deletion substringToIndex:(deletion.length - overlap_length1)];
nextDiff.text = [insertion substringFromIndex:overlap_length1];
[insertion release];
thisPointer++;
}
} else {
if (overlap_length2 >= deletion.length / 2.0f ||
overlap_length2 >= insertion.length / 2.0f) {
// Reverse overlap found.
// Insert an equality and swap and trim the surrounding edits.
[diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL
andText:[deletion substringToIndex:overlap_length2]]
atIndex:thisPointer];
[deletion retain];
prevDiff.operation = DIFF_INSERT;
prevDiff.text = [insertion substringToIndex:(insertion.length - overlap_length2)];
nextDiff.operation = DIFF_DELETE;
nextDiff.text = [deletion substringFromIndex:overlap_length2];
[deletion release];
thisPointer++;
}
}
thisPointer++;
}
thisPointer++;
}
CFRelease(equalities);
#undef prevDiff
#undef thisDiff
#undef nextDiff
#undef equalitiesLastValue
}
#pragma mark Match Functions
// MATCH FUNCTIONS
/**
* Locate the best instance of 'pattern' in 'text' near 'loc'.
* Returns NSNotFound if no match found.
* @param text The text to search.
* @param pattern The pattern to search for.
* @param loc The location to search around.
* @return Best match index or NSNotFound.
*/
- (NSUInteger)match_mainForText:(NSString *)text
pattern:(NSString *)pattern
near:(NSUInteger)loc;
{
// Check for null inputs.
if (text == nil || pattern == nil) {
NSLog(@"Null inputs. (match_main)");
return NSNotFound;
}
if (text.length == 0) {
NSLog(@"Empty text. (match_main)");
return NSNotFound;
}
NSUInteger new_loc;
new_loc = MIN(loc, text.length);
new_loc = MAX((NSUInteger)0, new_loc);
if ([text isEqualToString:pattern]) {
// Shortcut (potentially not guaranteed by the algorithm)
return 0;
} else if (text.length == 0) {
// Nothing to match.
return NSNotFound;
} else if (new_loc + pattern.length <= text.length
&& [[text substringWithRange:NSMakeRange(new_loc, pattern.length)] isEqualToString:pattern]) {
// Perfect match at the perfect spot! (Includes case of empty pattern)
return new_loc;
} else {
// Do a fuzzy compare.
return [self match_bitapOfText:text andPattern:pattern near:new_loc];
}
}
/**
* Locate the best instance of 'pattern' in 'text' near 'loc' using the
* Bitap algorithm. Returns NSNotFound if no match found.
* @param text The text to search.
* @param pattern The pattern to search for.
* @param loc The location to search around.
* @return Best match index or NSNotFound.
*/
- (NSUInteger)match_bitapOfText:(NSString *)text
andPattern:(NSString *)pattern
near:(NSUInteger)loc;
{
NSAssert((Match_MaxBits == 0 || pattern.length <= Match_MaxBits),
@"Pattern too long for this application.");
// Initialise the alphabet.
NSMutableDictionary *s = [self match_alphabet:pattern];
// Highest score beyond which we give up.
double score_threshold = Match_Threshold;
// Is there a nearby exact match? (speedup)
NSUInteger best_loc = [text rangeOfString:pattern options:NSLiteralSearch range:NSMakeRange(loc, text.length - loc)].location;
if (best_loc != NSNotFound) {
score_threshold = MIN([self match_bitapScoreForErrorCount:0 location:best_loc near:loc pattern:pattern], score_threshold);
// What about in the other direction? (speedup)
NSUInteger searchRangeLoc = MIN(loc + pattern.length, text.length);
NSRange searchRange = NSMakeRange(0, searchRangeLoc);
best_loc = [text rangeOfString:pattern options:(NSLiteralSearch | NSBackwardsSearch) range:searchRange].location;
if (best_loc != NSNotFound) {
score_threshold = MIN([self match_bitapScoreForErrorCount:0 location:best_loc near:loc pattern:pattern], score_threshold);
}
}
// Initialise the bit arrays.
NSUInteger matchmask = 1 << (pattern.length - 1);
best_loc = NSNotFound;
NSUInteger bin_min, bin_mid;
NSUInteger bin_max = pattern.length + text.length;
NSUInteger *rd = NULL;
NSUInteger *last_rd = NULL;
for (NSUInteger d = 0; d < pattern.length; d++) {
// Scan for the best match; each iteration allows for one more error.
// Run a binary search to determine how far from 'loc' we can stray at
// this error level.
bin_min = 0;
bin_mid = bin_max;
while (bin_min < bin_mid) {
double score = [self match_bitapScoreForErrorCount:d location:(loc + bin_mid) near:loc pattern:pattern];
if (score <= score_threshold) {
bin_min = bin_mid;
} else {
bin_max = bin_mid;
}
bin_mid = (bin_max - bin_min) / 2 + bin_min;
}
// Use the result from this iteration as the maximum for the next.
bin_max = bin_mid;
NSUInteger start = MAX_OF_CONST_AND_DIFF(1, loc, bin_mid);
NSUInteger finish = MIN(loc + bin_mid, text.length) + pattern.length;
rd = (NSUInteger *)calloc((finish + 2), sizeof(NSUInteger));
rd[finish + 1] = (1 << d) - 1;
for (NSUInteger j = finish; j >= start; j--) {
NSUInteger charMatch;
if (text.length <= j - 1 || ![s diff_containsObjectForUnicharKey:[text characterAtIndex:(j - 1)]]) {
// Out of range.
charMatch = 0;
} else {
charMatch = [s diff_unsignedIntegerForUnicharKey:[text characterAtIndex:(j - 1)]];
}
if (d == 0) {
// First pass: exact match.
rd[j] = (((rd[j + 1] << 1) | 1) & charMatch);
} else {
// Subsequent passes: fuzzy match.
rd[j] = (((rd[j + 1] << 1) | 1) & charMatch)
| (((last_rd[j + 1] | last_rd[j]) << 1) | 1) | last_rd[j + 1];
}
if ((rd[j] & matchmask) != 0) {
double score = [self match_bitapScoreForErrorCount:d location:(j - 1) near:loc pattern:pattern];
// This match will almost certainly be better than any existing match.
// But check anyway.
if (score <= score_threshold) {
// Told you so.
score_threshold = score;
best_loc = j - 1;
if (best_loc > loc) {
// When passing loc, don't exceed our current distance from loc.
start = MAX_OF_CONST_AND_DIFF(1, 2 * loc, best_loc);
} else {
// Already passed loc, downhill from here on in.
break;
}
}
}
}
if (last_rd != NULL) {
free(last_rd);
}
last_rd = rd;
if ([self match_bitapScoreForErrorCount:(d + 1) location:loc near:loc pattern:pattern] > score_threshold) {
// No hope for a (better) match at greater error levels.
break;
}
}
if (last_rd != NULL && last_rd != rd) {
free(last_rd);
}
if (rd != NULL) {
free(rd);
}
return best_loc;
}
/**
* Compute and return the score for a match with e errors and x location.
* @param e Number of errors in match.
* @param x Location of match.
* @param loc Expected location of match.
* @param pattern Pattern being sought.
* @return Overall score for match (0.0 = good, 1.0 = bad).
*/
- (double)match_bitapScoreForErrorCount:(NSUInteger)e
location:(NSUInteger)x
near:(NSUInteger)loc
pattern:(NSString *)pattern;
{
double score;
double accuracy = (double)e / pattern.length;
NSUInteger proximity = (NSUInteger)ABS((long long)loc - (long long)x);
if (Match_Distance == 0) {
// Dodge divide by zero error.
return proximity == 0 ? accuracy : 1.0;
}
score = accuracy + (proximity / (double) Match_Distance);
return score;
}
/**
* Initialise the alphabet for the Bitap algorithm.
* @param pattern The text to encode.
* @return Hash of character locations
* (NSMutableDictionary: keys:NSString/unichar, values:NSNumber/NSUInteger).
*/
- (NSMutableDictionary *)match_alphabet:(NSString *)pattern;
{
NSMutableDictionary *s = [NSMutableDictionary dictionary];
CFStringRef str = (CFStringRef)pattern;
CFStringInlineBuffer inlineBuffer;
CFIndex length;
CFIndex cnt;
length = CFStringGetLength(str);
CFStringInitInlineBuffer(str, &inlineBuffer, CFRangeMake(0, length));
UniChar ch;
CFStringRef c;
for (cnt = 0; cnt < length; cnt++) {
ch = CFStringGetCharacterFromInlineBuffer(&inlineBuffer, cnt);
c = diff_CFStringCreateFromUnichar(ch);
if (![s diff_containsObjectForKey:(NSString *)c]) {
[s diff_setUnsignedIntegerValue:0 forKey:(NSString *)c];
}
CFRelease(c);
}
NSUInteger i = 0;
for (cnt = 0; cnt < length; cnt++) {
ch = CFStringGetCharacterFromInlineBuffer(&inlineBuffer, cnt);
c = diff_CFStringCreateFromUnichar(ch);
NSUInteger value = [s diff_unsignedIntegerForKey:(NSString *)c] | (1 << (pattern.length - i - 1));
[s diff_setUnsignedIntegerValue:value forKey:(NSString *)c];
i++;
CFRelease(c);
}
return s;
}
#pragma mark Patch Functions
// PATCH FUNCTIONS
/**
* Increase the context until it is unique,
* but don't let the pattern expand beyond Match_MaxBits.
* @param patch The patch to grow.
* @param text Source text.
*/
- (void)patch_addContextToPatch:(Patch *)patch
sourceText:(NSString *)text;
{
if (text.length == 0) {
return;
}
NSString *pattern = [text substringWithRange:NSMakeRange(patch.start2, patch.length1)];
NSUInteger padding = 0;
// Look for the first and last matches of pattern in text. If two
// different matches are found, increase the pattern length.
while ([text rangeOfString:pattern options:NSLiteralSearch].location
!= [text rangeOfString:pattern options:(NSLiteralSearch | NSBackwardsSearch)].location
&& pattern.length < (Match_MaxBits - Patch_Margin - Patch_Margin)) {
padding += Patch_Margin;
pattern = [text diff_javaSubstringFromStart:MAX_OF_CONST_AND_DIFF(0, patch.start2, padding)
toEnd:MIN(text.length, patch.start2 + patch.length1 + padding)];
}
// Add one chunk for good luck.
padding += Patch_Margin;
// Add the prefix.
NSString *prefix = [text diff_javaSubstringFromStart:MAX_OF_CONST_AND_DIFF(0, patch.start2, padding)
toEnd:patch.start2];
if (prefix.length != 0) {
[patch.diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL andText:prefix] atIndex:0];
}
// Add the suffix.
NSString *suffix = [text diff_javaSubstringFromStart:(patch.start2 + patch.length1)
toEnd:MIN(text.length, patch.start2 + patch.length1 + padding)];
if (suffix.length != 0) {
[patch.diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:suffix]];
}
// Roll back the start points.
patch.start1 -= prefix.length;
patch.start2 -= prefix.length;
// Extend the lengths.
patch.length1 += prefix.length + suffix.length;
patch.length2 += prefix.length + suffix.length;
}
/**
* Compute a list of patches to turn text1 into text2.
* A set of diffs will be computed.
* @param text1 Old text.
* @param text2 New text.
* @return NSMutableArray of Patch objects.
*/
- (NSMutableArray *)patch_makeFromOldString:(NSString *)text1
andNewString:(NSString *)text2;
{
// Check for null inputs.
if (text1 == nil || text2 == nil) {
NSLog(@"Null inputs. (patch_make)");
return nil;
}
// No diffs provided, compute our own.
NSMutableArray *diffs = [self diff_mainOfOldString:text1 andNewString:text2 checkLines:YES];
if (diffs.count > 2) {
[self diff_cleanupSemantic:diffs];
[self diff_cleanupEfficiency:diffs];
}
return [self patch_makeFromOldString:text1 andDiffs:diffs];
}
/**
* Compute a list of patches to turn text1 into text2.
* text1 will be derived from the provided diffs.
* @param diffs NSMutableArray of Diff objects for text1 to text2.
* @return NSMutableArray of Patch objects.
*/
- (NSMutableArray *)patch_makeFromDiffs:(NSMutableArray *)diffs;
{
// Check for nil inputs not needed since nil can't be passed in C#.
// No origin NSString *provided, comAdde our own.
NSString *text1 = [self diff_text1:diffs];
return [self patch_makeFromOldString:text1 andDiffs:diffs];
}
/**
* Compute a list of patches to turn text1 into text2.
* text2 is ignored, diffs are the delta between text1 and text2.
* @param text1 Old text
* @param text2 New text
* @param diffs NSMutableArray of Diff objects for text1 to text2.
* @return NSMutableArray of Patch objects.
* @deprecated Prefer -patch_makeFromOldString:diffs:.
*/
- (NSMutableArray *)patch_makeFromOldString:(NSString *)text1
newString:(NSString *)text2
diffs:(NSMutableArray *)diffs;
{
// Check for null inputs.
if (text1 == nil || text2 == nil) {
NSLog(@"Null inputs. (patch_make)");
return nil;
}
return [self patch_makeFromOldString:text1 andDiffs:diffs];
}
/**
* Compute a list of patches to turn text1 into text2.
* text2 is not provided, diffs are the delta between text1 and text2.
* @param text1 Old text.
* @param diffs NSMutableArray of Diff objects for text1 to text2.
* @return NSMutableArray of Patch objects.
*/
- (NSMutableArray *)patch_makeFromOldString:(NSString *)text1
andDiffs:(NSMutableArray *)diffs;
{
// Check for null inputs.
if (text1 == nil) {
NSLog(@"Null inputs. (patch_make)");
return nil;
}
NSMutableArray *patches = [NSMutableArray array];
if (diffs.count == 0) {
return patches; // Get rid of the nil case.
}
Patch *patch = [[Patch new] autorelease];
NSUInteger char_count1 = 0; // Number of characters into the text1 NSString.
NSUInteger char_count2 = 0; // Number of characters into the text2 NSString.
// Start with text1 (prepatch_text) and apply the diffs until we arrive at
// text2 (postpatch_text). We recreate the patches one by one to determine
// context info.
NSString *prepatch_text = [text1 retain];
NSMutableString *postpatch_text = [text1 mutableCopy];
for (Diff *aDiff in diffs) {
if (patch.diffs.count == 0 && aDiff.operation != DIFF_EQUAL) {
// A new patch starts here.
patch.start1 = char_count1;
patch.start2 = char_count2;
}
switch (aDiff.operation) {
case DIFF_INSERT:
[patch.diffs addObject:aDiff];
patch.length2 += aDiff.text.length;
[postpatch_text insertString:aDiff.text atIndex:char_count2];
break;
case DIFF_DELETE:
patch.length1 += aDiff.text.length;
[patch.diffs addObject:aDiff];
[postpatch_text deleteCharactersInRange:NSMakeRange(char_count2, aDiff.text.length)];
break;
case DIFF_EQUAL:
if (aDiff.text.length <= 2 * Patch_Margin
&& [patch.diffs count] != 0 && aDiff != diffs.lastObject) {
// Small equality inside a patch.
[patch.diffs addObject:aDiff];
patch.length1 += aDiff.text.length;
patch.length2 += aDiff.text.length;
}
if (aDiff.text.length >= 2 * Patch_Margin) {
// Time for a new patch.
if (patch.diffs.count != 0) {
[self patch_addContextToPatch:patch sourceText:prepatch_text];
[patches addObject:patch];
patch = [[Patch new] autorelease];
// Unlike Unidiff, our patch lists have a rolling context.
// http://code.google.com/p/google-diff-match-patch/wiki/Unidiff
// Update prepatch text & pos to reflect the application of the
// just completed patch.
[prepatch_text release];
prepatch_text = [postpatch_text copy];
char_count1 = char_count2;
}
}
break;
}
// Update the current character count.
if (aDiff.operation != DIFF_INSERT) {
char_count1 += aDiff.text.length;
}
if (aDiff.operation != DIFF_DELETE) {
char_count2 += aDiff.text.length;
}
}
// Pick up the leftover patch if not empty.
if (patch.diffs.count != 0) {
[self patch_addContextToPatch:patch sourceText:prepatch_text];
[patches addObject:patch];
}
[prepatch_text release];
[postpatch_text release];
return patches;
}
/**
* Given an array of patches, return another array that is identical.
* @param patches NSArray of Patch objects.
* @return NSMutableArray of Patch objects.
*/
- (NSMutableArray *)patch_deepCopy:(NSArray *)patches;
{
NSMutableArray *patchesCopy = [[NSMutableArray alloc] initWithArray:patches copyItems:YES];
return patchesCopy;
}
/**
* Merge a set of patches onto the text. Return a patched text, as well
* as an array of YES/NO values indicating which patches were applied.
* @param patches NSMutableArray of Patch objects
* @param text Old text.
* @return Two element NSArray, containing the new text and an array of
* BOOL values.
*/
- (NSArray *)patch_apply:(NSArray *)sourcePatches
toString:(NSString *)text;
{
if (sourcePatches.count == 0) {
return [NSArray arrayWithObjects:text, [NSMutableArray array], nil];
}
// Deep copy the patches so that no changes are made to originals.
NSMutableArray *patches = [[self patch_deepCopy:sourcePatches] autorelease];
NSMutableString *textMutable = [[text mutableCopy] autorelease];
NSString *nullPadding = [self patch_addPadding:patches];
[textMutable insertString:nullPadding atIndex:0];
[textMutable appendString:nullPadding];
[self patch_splitMax:patches];
NSUInteger x = 0;
// delta keeps track of the offset between the expected and actual
// location of the previous patch. If there are patches expected at
// positions 10 and 20, but the first patch was found at 12, delta is 2
// and the second patch has an effective expected position of 22.
NSUInteger delta = 0;
BOOL *results = (BOOL *)calloc(patches.count, sizeof(BOOL));
for (Patch *aPatch in patches) {
NSUInteger expected_loc = aPatch.start2 + delta;
NSString *text1 = [self diff_text1:aPatch.diffs];
NSUInteger start_loc;
NSUInteger end_loc = NSNotFound;
if (text1.length > Match_MaxBits) {
// patch_splitMax will only provide an oversized pattern
// in the case of a monster delete.
start_loc = [self match_mainForText:textMutable
pattern:[text1 substringToIndex:Match_MaxBits]
near:expected_loc];
if (start_loc != NSNotFound) {
end_loc = [self match_mainForText:textMutable
pattern:[text1 substringFromIndex:text1.length - Match_MaxBits]
near:(expected_loc + text1.length - Match_MaxBits)];
if (end_loc == NSNotFound || start_loc >= end_loc) {
// Can't find valid trailing context. Drop this patch.
start_loc = NSNotFound;
}
}
} else {
start_loc = [self match_mainForText:textMutable pattern:text1 near:expected_loc];
}
if (start_loc == NSNotFound) {
// No match found. :(
results[x] = NO;
// Subtract the delta for this failed patch from subsequent patches.
delta -= aPatch.length2 - aPatch.length1;
} else {
// Found a match. :)
results[x] = YES;
delta = start_loc - expected_loc;
NSString *text2;
if (end_loc == NSNotFound) {
text2 = [textMutable diff_javaSubstringFromStart:start_loc
toEnd:MIN(start_loc + text1.length, textMutable.length)];
} else {
text2 = [textMutable diff_javaSubstringFromStart:start_loc
toEnd:MIN(end_loc + Match_MaxBits, textMutable.length)];
}
if (text1 == text2) {
// Perfect match, just shove the Replacement text in.
[textMutable replaceCharactersInRange:NSMakeRange(start_loc, text1.length) withString:[self diff_text2:aPatch.diffs]];
} else {
// Imperfect match. Run a diff to get a framework of equivalent
// indices.
NSMutableArray *diffs = [self diff_mainOfOldString:text1 andNewString:text2 checkLines:NO];
if (text1.length > Match_MaxBits
&& ([self diff_levenshtein:diffs] / (float)text1.length)
> Patch_DeleteThreshold) {
// The end points match, but the content is unacceptably bad.
results[x] = NO;
} else {
[self diff_cleanupSemanticLossless:diffs];
NSUInteger index1 = 0;
for (Diff *aDiff in aPatch.diffs) {
if (aDiff.operation != DIFF_EQUAL) {
NSUInteger index2 = [self diff_xIndexIn:diffs location:index1];
if (aDiff.operation == DIFF_INSERT) {
// Insertion
[textMutable insertString:aDiff.text atIndex:(start_loc + index2)];
} else if (aDiff.operation == DIFF_DELETE) {
// Deletion
[textMutable deleteCharactersInRange:NSMakeRange(start_loc + index2,
([self diff_xIndexIn:diffs
location:(index1 + aDiff.text.length)] - index2))];
}
}
if (aDiff.operation != DIFF_DELETE) {
index1 += aDiff.text.length;
}
}
}
}
}
x++;
}
NSMutableArray *resultsArray = [NSMutableArray arrayWithCapacity:patches.count];
for (NSUInteger i = 0; i < patches.count; i++) {
[resultsArray addObject:[NSNumber numberWithBool:(results[i])]];
}
if (results != NULL) {
free(results);
}
// Strip the padding off.
text = [textMutable substringWithRange:NSMakeRange(nullPadding.length,
textMutable.length - 2 * nullPadding.length)];
return [NSArray arrayWithObjects:text, resultsArray, nil];
}
/**
* Add some padding on text start and end so that edges can match something.
* Intended to be called only from within patch_apply.
* @param patches NSMutableArray of Patch objects.
* @return The padding NSString added to each side.
*/
- (NSString *)patch_addPadding:(NSMutableArray *)patches;
{
uint16_t paddingLength = Patch_Margin;
NSMutableString *nullPadding = [NSMutableString string];
for (UniChar x = 1; x <= paddingLength; x++) {
CFStringAppendCharacters((CFMutableStringRef)nullPadding, &x, 1);
}
// Bump all the patches forward.
for (Patch *aPatch in patches) {
aPatch.start1 += paddingLength;
aPatch.start2 += paddingLength;
}
// Add some padding on start of first diff.
Patch *patch = [patches objectAtIndex:0];
NSMutableArray *diffs = patch.diffs;
if (diffs.count == 0 || ((Diff *)[diffs objectAtIndex:0]).operation != DIFF_EQUAL) {
// Add nullPadding equality.
[diffs insertObject:[Diff diffWithOperation:DIFF_EQUAL andText:nullPadding] atIndex:0];
patch.start1 -= paddingLength; // Should be 0.
patch.start2 -= paddingLength; // Should be 0.
patch.length1 += paddingLength;
patch.length2 += paddingLength;
} else if (paddingLength > ((Diff *)[diffs objectAtIndex:0]).text.length) {
// Grow first equality.
Diff *firstDiff = [diffs objectAtIndex:0];
NSUInteger extraLength = paddingLength - firstDiff.text.length;
firstDiff.text = [[nullPadding substringFromIndex:(firstDiff.text.length)]
stringByAppendingString:firstDiff.text];
patch.start1 -= extraLength;
patch.start2 -= extraLength;
patch.length1 += extraLength;
patch.length2 += extraLength;
}
// Add some padding on end of last diff.
patch = patches.lastObject;
diffs = patch.diffs;
if (diffs.count == 0 || ((Diff *)diffs.lastObject).operation != DIFF_EQUAL) {
// Add nullPadding equality.
[diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:nullPadding]];
patch.length1 += paddingLength;
patch.length2 += paddingLength;
} else if (paddingLength > ((Diff *)diffs.lastObject).text.length) {
// Grow last equality.
Diff *lastDiff = diffs.lastObject;
NSUInteger extraLength = paddingLength - lastDiff.text.length;
lastDiff.text = [lastDiff.text stringByAppendingString:[nullPadding substringToIndex:extraLength]];
patch.length1 += extraLength;
patch.length2 += extraLength;
}
return nullPadding;
}
/**
* Look through the patches and break up any which are longer than the
* maximum limit of the match algorithm.
* Intended to be called only from within patch_apply.
* @param patches NSMutableArray of Patch objects.
*/
- (void)patch_splitMax:(NSMutableArray *)patches;
{
NSUInteger patch_size = Match_MaxBits;
for (NSUInteger x = 0; x < patches.count; x++) {
if (((Patch *)[patches objectAtIndex:x]).length1 <= patch_size) {
continue;
}
Patch *bigpatch = [[patches objectAtIndex:x] retain];
// Remove the big old patch.
splice(patches, x--, 1, nil);
NSUInteger start1 = bigpatch.start1;
NSUInteger start2 = bigpatch.start2;
NSString *precontext = @"";
while (bigpatch.diffs.count != 0) {
// Create one of several smaller patches.
Patch *patch = [[Patch new] autorelease];
BOOL empty = YES;
patch.start1 = start1 - precontext.length;
patch.start2 = start2 - precontext.length;
if (precontext.length != 0) {
patch.length1 = patch.length2 = precontext.length;
[patch.diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:precontext]];
}
while (bigpatch.diffs.count != 0
&& patch.length1 < patch_size - self.Patch_Margin) {
Operation diff_type = ((Diff *)[bigpatch.diffs objectAtIndex:0]).operation;
NSString *diff_text = ((Diff *)[bigpatch.diffs objectAtIndex:0]).text;
if (diff_type == DIFF_INSERT) {
// Insertions are harmless.
patch.length2 += diff_text.length;
start2 += diff_text.length;
[patch.diffs addObject:[bigpatch.diffs objectAtIndex:0]];
[bigpatch.diffs removeObjectAtIndex:0];
empty = NO;
} else if (diff_type == DIFF_DELETE && patch.diffs.count == 1
&& ((Diff *)[patch.diffs objectAtIndex:0]).operation == DIFF_EQUAL
&& diff_text.length > 2 * patch_size) {
// This is a large deletion. Let it pass in one chunk.
patch.length1 += diff_text.length;
start1 += diff_text.length;
empty = NO;
[patch.diffs addObject:[Diff diffWithOperation:diff_type andText:diff_text]];
[bigpatch.diffs removeObjectAtIndex:0];
} else {
// Deletion or equality. Only take as much as we can stomach.
diff_text = [diff_text substringWithRange:NSMakeRange(0,
MIN(diff_text.length,
(patch_size - patch.length1 - Patch_Margin)))];
patch.length1 += diff_text.length;
start1 += diff_text.length;
if (diff_type == DIFF_EQUAL) {
patch.length2 += diff_text.length;
start2 += diff_text.length;
} else {
empty = NO;
}
[patch.diffs addObject:[Diff diffWithOperation:diff_type andText:diff_text]];
if (diff_text == ((Diff *)[bigpatch.diffs objectAtIndex:0]).text) {
[bigpatch.diffs removeObjectAtIndex:0];
} else {
Diff *firstDiff = [bigpatch.diffs objectAtIndex:0];
firstDiff.text = [firstDiff.text substringFromIndex:diff_text.length];
}
}
}
// Compute the head context for the next patch.
precontext = [self diff_text2:patch.diffs];
precontext = [precontext substringFromIndex:MAX_OF_CONST_AND_DIFF(0, precontext.length, Patch_Margin)];
NSString *postcontext = nil;
// Append the end context for this patch.
if ([self diff_text1:bigpatch.diffs].length > Patch_Margin) {
postcontext = [[self diff_text1:bigpatch.diffs]
substringToIndex:Patch_Margin];
} else {
postcontext = [self diff_text1:bigpatch.diffs];
}
if (postcontext.length != 0) {
patch.length1 += postcontext.length;
patch.length2 += postcontext.length;
if (patch.diffs.count != 0
&& ((Diff *)[patch.diffs objectAtIndex:(patch.diffs.count - 1)]).operation
== DIFF_EQUAL) {
Diff *lastDiff = [patch.diffs lastObject];
lastDiff.text = [lastDiff.text stringByAppendingString:postcontext];
} else {
[patch.diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:postcontext]];
}
}
if (!empty) {
splice(patches, ++x, 0, [NSMutableArray arrayWithObject:patch]);
}
}
[bigpatch release];
}
}
/**
* Take a list of patches and return a textual representation.
* @param patches NSMutableArray of Patch objects.
* @return Text representation of patches.
*/
- (NSString *)patch_toText:(NSMutableArray *)patches;
{
NSMutableString *text = [NSMutableString string];
for (Patch *aPatch in patches) {
[text appendString:[aPatch description]];
}
return text;
}
/**
* Parse a textual representation of patches and return a NSMutableArray of
* Patch objects.
* @param textline Text representation of patches.
* @param error NSError if invalid input.
* @return NSMutableArray of Patch objects.
*/
- (NSMutableArray *)patch_fromText:(NSString *)textline
error:(NSError **)error;
{
NSMutableArray *patches = [NSMutableArray array];
if (textline.length == 0) {
return patches;
}
NSArray *text = [textline componentsSeparatedByString:@"\n"];
NSUInteger textPointer = 0;
Patch *patch;
//NSString *patchHeader = @"^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$";
NSString *patchHeaderStart = @"@@ -";
NSString *patchHeaderMid = @"+";
NSString *patchHeaderEnd = @"@@";
NSString *optionalValueDelimiter = @",";
BOOL scanSuccess, hasOptional;
NSInteger scannedValue, optionalValue;
NSDictionary *errorDetail = nil;
NSString *textAtTextPointer;
unichar sign;
NSString *line;
while (textPointer < text.count) {
NSString *thisLine = [text objectAtIndex:textPointer];
NSScanner *theScanner = [NSScanner scannerWithString:thisLine];
patch = [[Patch new] autorelease];
scanSuccess = ([theScanner scanString:patchHeaderStart intoString:NULL]
&& [theScanner scanInteger:&scannedValue]);
if (scanSuccess) {
patch.start1 = scannedValue;
hasOptional = [theScanner scanString:optionalValueDelimiter intoString:NULL];
if (hasOptional) {
// First set has an optional value.
scanSuccess = [theScanner scanInteger:&optionalValue];
if (scanSuccess) {
if (optionalValue == 0) {
patch.length1 = 0;
} else {
patch.start1--;
patch.length1 = optionalValue;
}
}
} else {
patch.start1--;
patch.length1 = 1;
}
if (scanSuccess) {
scanSuccess = ([theScanner scanString:patchHeaderMid intoString:NULL]
&& [theScanner scanInteger:&scannedValue]);
if (scanSuccess) {
patch.start2 = scannedValue;
hasOptional = [theScanner scanString:optionalValueDelimiter intoString:NULL];
if (hasOptional) {
// Second set has an optional value.
scanSuccess = [theScanner scanInteger:&optionalValue];
if (scanSuccess) {
if (optionalValue == 0) {
patch.length2 = 0;
} else {
patch.start2--;
patch.length2 = optionalValue;
}
}
} else {
patch.start2--;
patch.length2 = 1;
}
if (scanSuccess) {
scanSuccess = ([theScanner scanString:patchHeaderEnd intoString:NULL]
&& [theScanner isAtEnd] == YES);
}
}
}
}
if (!scanSuccess) {
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Invalid patch string: %@", @"Error"),
[text objectAtIndex:textPointer]],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:104 userInfo:errorDetail];
}
return nil;
}
[patches addObject:patch];
textPointer++;
while (textPointer < text.count) {
textAtTextPointer = [text objectAtIndex:textPointer];
if (textAtTextPointer.length > 0) {
sign = [textAtTextPointer characterAtIndex:0];
}
else {
// Blank line? Whatever.
textPointer++;
continue;
}
line = [[textAtTextPointer substringFromIndex:1]
diff_stringByReplacingPercentEscapesForEncodeUriCompatibility];
if (sign == '-') {
// Deletion.
[patch.diffs addObject:[Diff diffWithOperation:DIFF_DELETE andText:line]];
} else if (sign == '+') {
// Insertion.
[patch.diffs addObject:[Diff diffWithOperation:DIFF_INSERT andText:line]];
} else if (sign == ' ') {
// Minor equality.
[patch.diffs addObject:[Diff diffWithOperation:DIFF_EQUAL andText:line]];
} else if (sign == '@') {
// Start of next patch.
break;
} else {
// WTF?
if (error != NULL) {
errorDetail = [NSDictionary dictionaryWithObjectsAndKeys:
[NSString stringWithFormat:NSLocalizedString(@"Invalid patch mode '%C' in: %@", @"Error"), sign, line],
NSLocalizedDescriptionKey, nil];
*error = [NSError errorWithDomain:@"DiffMatchPatchErrorDomain" code:104 userInfo:errorDetail];
}
return nil;
}
textPointer++;
}
}
return patches;
}
@end
Jump to Line
Something went wrong with that request. Please try again.