Commits

Liam Staskawicz committed b9aad9d

use indexes to track progress through our parsed strings, rather than slicing them each character. much more efficient, and easier to pass around an index rather than the modified string as our notion of progress between subroutines.

Comments (0)

Files changed (1)

 package osc
 
 import (
-// "fmt"
+	// "fmt"
+	"strings"
 )
 
 func PatternMatch(pattern, test string) bool {
 	// we try to iterate where possible, but for ease
 	// of implementation we recurse in several places.
 
-	// XXX: is there a better way to step through characters of a string?
+	// indexes into our strings
+	ipattern := 0
+	itest := 0
 
 	for {
 		// check for end of string, or just empty string
-		if len(pattern) == 0 {
-			return len(test) == 0
+		if ipattern == len(pattern) {
+			return itest == len(test)
 		}
 
-		c := pattern[0]
+		c := pattern[ipattern]
 
 		// check for end/empty test string
-		if len(test) == 0 {
+		if itest == len(test) {
 			// if there's anything else in pattern other than * or escape char, no match
 			if c != '*' && c != '\\' {
 				return false
 			}
 
-			pattern = pattern[1:]
+			ipattern++
 			continue
 		}
 
 		switch c {
 		case '?':
 			// matches any single character
-			pattern = pattern[1:]
-			test = test[1:]
+			ipattern++
+			itest++
 
 		case '*':
 			// matches zero or more characters
 			return false
 
 		case '[':
-			var result bool
-			if result, pattern = matchSet(pattern, rune(test[0])); !result {
+			result, numbytes := matchSet(pattern[ipattern:], rune(test[itest]))
+			if !result {
 				return false
 			}
-			test = test[1:]
+			ipattern += numbytes
+			itest++
 
 		case '{':
 			return false
 
 		case '\\':
 			// special case if this is the last character
-			if len(pattern) == 1 {
-				return len(test) == 0
-			} else if pattern[1] != test[0] {
-				// if the following character doesn't match, we're done
+			if ipattern == len(pattern)-1 {
+				return itest == len(test)
+			}
+
+			// if the following character doesn't match, we're done
+			if pattern[ipattern+1] != test[itest] {
 				return false
 			}
 
 			// continue via basic character match after the escaped character
-			pattern = pattern[2:]
-			test = test[1:]
+			ipattern += 2
+			itest++
 
 		default:
 			// basic character match - if these two characters match,
 			// continue to the next character, otherwise we're done
-			if c == test[0] {
-				pattern = pattern[1:]
-				test = test[1:]
-			} else {
+			if c != test[itest] {
 				return false
 			}
+
+			ipattern++
+			itest++
 		}
 	}
 
 
 // spec: "a string of characters in square brackets (e.g., "[string]")
 // in the OSC Address Pattern matches any character in the string."
-func matchSet(pattern string, test rune) (result bool, patternout string) {
+func matchSet(pattern string, test rune) (bool, int) {
 
 	// "An exclamation point at the beginning of a bracketed string
 	// negates the sense of the list, meaning that the list matches
 	// any character not in the list. (An exclamation point anywhere
 	// besides the first character after the open bracket has no special meaning.)"
-	negated := false
+	var negated bool
 	if pattern[1] == '!' {
 		negated = true
 		pattern = pattern[1:]
+	} else {
+		negated = false
 	}
 
 	for i, c := range pattern {
 		// if we got to the closing bracket without matching,
 		// 'negated' specifies whether that's what was actually asked for
 		if c == ']' {
-			return negated, ""
+			// account for one byte of '!' and one byte to step past the current ']'
+			return negated, i + 2
 		}
 
 		// "two characters separated by a minus sign indicate the
 		// ie, check for 'a-z' pattern and skip anything else up to the closing ]
 		if pattern[i+1] == '-' && i+3 < len(pattern) {
 			if test >= c && test <= rune(pattern[i+2]) {
-				if negated {
-					return false, ""
-				}
-				return incrementUntil(pattern[i+2:], ']')
+				result, offset := handleMatchInSet(negated, pattern[i+2:])
+				return result, i + offset + 2
 			}
 		}
 
 		// otherwise check for normal inclusion in the set
 		if c == test {
-			if negated {
-				return false, ""
-			}
-			return incrementUntil(pattern[i:], ']')
+			result, offset := handleMatchInSet(negated, pattern[i:])
+			return result, i + offset
 		}
 	}
 
 	// we didn't find the closing bracket
-	return false, ""
+	return false, 0
 }
 
-func incrementUntil(s string, b rune) (bool, string) {
+func handleMatchInSet(negated bool, pattern string) (bool, int) {
 
-	for i, c := range s {
-		if c == b {
-			return true, s[i+1:]
-		}
+	// if we matched when we were supposed to be negated, that's a failed match
+	if negated {
+		return false, 0
 	}
 
-	return false, ""
+	// ensure the closing bracket exists,
+	// and return the offset of the next byte beyond it
+	idx := strings.IndexRune(pattern, ']')
+	return idx >= 0, idx + 1
 }