Added an internal algorithm for fuzzy string matching

* This works similar to a regex matching "abc" as /a.*b.*c/ (ie. all characters of $needle need to be contained in $haystack in the correct order but not neccesarily consecutive). Additionaly some unicode equivalencies are handled.
* Changed a tiny helper function from ObjC to plain C

2 files changed, 70 insertions, 0 deletions

diff --git a/UnitTests/SPStringAdditionsTests.h b/UnitTests/SPStringAdditionsTests.h
index d6854dbe..56b5c6f9 100644
--- a/UnitTests/SPStringAdditionsTests.h
+++ b/UnitTests/SPStringAdditionsTests.h
@@ -35,5 +35,6 @@
 - (void)testStringByRemovingCharactersInSet;
 - (void)testStringWithNewUUID;
 - (void)testCreateViewSyntaxPrettifier;
+- (void)testNonConsecutivelySearchStringMatchingRanges;
 
 @end
diff --git a/UnitTests/SPStringAdditionsTests.m b/UnitTests/SPStringAdditionsTests.m
index af22df77..f455066f 100644
--- a/UnitTests/SPStringAdditionsTests.m
+++ b/UnitTests/SPStringAdditionsTests.m
@@ -86,4 +86,73 @@
 	STAssertEqualObjects([actualSyntax description], [expectedSyntax description], @"Actual view syntax '%@' does not equal expected syntax '%@'", actualSyntax, expectedSyntax);
 }
 
+- (void)testNonConsecutivelySearchStringMatchingRanges
+{
+	//basic tests
+	{
+		NSArray *matches = nil;
+		STAssertTrue([@"" nonConsecutivelySearchString:@"" matchingRanges:&matches], @"Equality of empty strings");
+		STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 0), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in empty string");
+	}
+	
+	{
+		NSArray *matches = (void *)0xdeadbeef;
+		STAssertFalse([@"" nonConsecutivelySearchString:@"R" matchingRanges:&matches], @"Inequality with empty left side");
+		STAssertTrue((matches == (void *)0xdeadbeef), @"out variable not touched by mismatch");
+	}
+	
+	STAssertFalse([@"L" nonConsecutivelySearchString:@"" matchingRanges:NULL], @"Inequality with empty right side");
+	
+	{
+		NSArray *matches = nil;
+		STAssertTrue([@"left" nonConsecutivelySearchString:@"le" matchingRanges:&matches], @"Anchored match left");
+		STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 2), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in anchored left match");
+	}
+	
+	{
+		NSArray *matches = nil;
+		STAssertTrue([@"right" nonConsecutivelySearchString:@"ht" matchingRanges:&matches], @"Anchored match right");
+		STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(3, 2), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in anchroed right match");
+	}
+	
+	STAssertFalse([@"ht" nonConsecutivelySearchString:@"right" matchingRanges:NULL], @"Left and Right are not commutative");
+	
+	//real tests
+	{
+		NSArray *matches = nil;
+		STAssertTrue([@"... is not secure anymore!" nonConsecutivelySearchString:@"NSA"  matchingRanges:&matches], @"Non-consecutive match, ignoring case");
+		STAssertTrue(([matches count] == 3) &&
+					 (NSEqualRanges(NSMakeRange(7, 1), [(NSValue *)[matches objectAtIndex:0] rangeValue])) &&
+					 (NSEqualRanges(NSMakeRange(11, 1), [(NSValue *)[matches objectAtIndex:1] rangeValue])) &&
+					 (NSEqualRanges(NSMakeRange(18, 1), [(NSValue *)[matches objectAtIndex:2] rangeValue])), @"Returned matches in non-consecutive string");
+	}
+	
+	STAssertFalse([@"Deoxyribonucleic Acid" nonConsecutivelySearchString:@"DNS"  matchingRanges:NULL], @"Non-consecutive mismatch");
+	
+	{
+		NSArray *matches = nil;
+		STAssertTrue([@"Turn left, then right at the corner" nonConsecutivelySearchString:@"left right" matchingRanges:&matches], @"Partly consecutive match");
+		STAssertTrue(([matches count] == 3) &&
+					 (NSEqualRanges(NSMakeRange(5, 4), [(NSValue *)[matches objectAtIndex:0] rangeValue])) &&
+					 (NSEqualRanges(NSMakeRange(10, 1), [(NSValue *)[matches objectAtIndex:1] rangeValue])) &&
+					 (NSEqualRanges(NSMakeRange(16, 5), [(NSValue *)[matches objectAtIndex:2] rangeValue])), @"Returned matches in partly-consecutive string");
+	}
+	
+	//advanced tests
+	
+	// LATIN CAPITAL LETTER A              == LATIN SMALL LETTER A
+	// LATIN SMALL LETTER O WITH DIAERESIS == LATIN SMALL LETTER O
+	// FULLWIDTH LATIN SMALL LETTER b      == LATIN SMALL LETTER B
+	STAssertTrue([@"A:\xC3\xB6:\xEF\xBD\x82" nonConsecutivelySearchString:@"aob" matchingRanges:NULL], @"Fuzzy matching of defined characters");
+	
+	//all bytes on the right are contained on the left, but on a character level "ä" is not contained in "Hütte Ф"
+	STAssertFalse([@"H\xC3\xBCtte \xD0\xA4" nonConsecutivelySearchString:@"\xC3\xA4" matchingRanges:NULL], @"Mismatch of composed characters with same prefix");
+	
+	// ":😥:𠘄:" vs "😄" (according to wikipedia "𠘄" is the arachic variant of "印")
+	// TECHNICALLY THIS SHOULD NOT MATCH!
+	// However Apple doesn't correctly handle characters in the 4-Byte UTF range, so let's use this test to check for changes in Apples behaviour :)
+	STAssertTrue([@":\xF0\x9F\x98\x84:\xF0\xA0\x98\x84:" nonConsecutivelySearchString:@"\xF0\x9F\x98\x84" matchingRanges:NULL], @"Mismatch of composed characters (4-byte) with same prefix");
+	
+}
+
 @end