Repository: VKCOM/noverify
Pull request #834 (2020-12-06 20:41:41)

phpgrep: implement matching backtracking
It doesn't affect performance that much in most cases,
but makes patterns behave in a more expected way
so they match what they *should* match.

See linked examples and tests for cases that worked
incorrectly due to the lack of backtracking.

It's possible to match some of these patterns without backtracking,
but it would require more efforts during the pattern compilation
to recognize special cases. We may do that in the future.

Fixes https://github.com/quasilyte/phpgrep/issues/63
Fixes https://github.com/quasilyte/phpgrep/issues/42


Patch:
diff --git a/src/phpgrep/matcher.go b/src/phpgrep/matcher.go
index 5392b01..2a10361 100644
--- a/src/phpgrep/matcher.go
+++ b/src/phpgrep/matcher.go
@@ -65,6 +65,16 @@ func (m *matcher) eqArrayItemSlice(state *matcherState, xs, ys []*ir.ArrayItemEx
 
 	matchAny := false
 
+	var backXS []*ir.ArrayItemExpr
+	var backYS []*ir.ArrayItemExpr
+
+	maybeBacktrack := func(matched bool) bool {
+		if !matched && backXS != nil {
+			return m.eqArrayItemSlice(state, backXS, backYS)
+		}
+		return matched
+	}
+
 	i := 0
 	for i < len(xs) {
 		x := xs[i]
@@ -81,6 +91,8 @@ func (m *matcher) eqArrayItemSlice(state *matcherState, xs, ys []*ir.ArrayItemEx
 				i++
 			// Lookahead for non-greedy matching.
 			case i+1 < len(xs) && m.eqNode(state, xs[i+1], ys[0]):
+				backXS = xs
+				backYS = ys[1:]
 				matchAny = false
 				i += 2
 				ys = ys[1:]
@@ -91,13 +103,13 @@ func (m *matcher) eqArrayItemSlice(state *matcherState, xs, ys []*ir.ArrayItemEx
 		}
 
 		if len(ys) == 0 || !m.eqNode(state, x, ys[0]) {
-			return false
+			return maybeBacktrack(false)
 		}
 		i++
 		ys = ys[1:]
 	}
 
-	return len(ys) == 0
+	return maybeBacktrack(len(ys) == 0)
 }
 
 func (m *matcher) eqNodeSlice(state *matcherState, xs, ys []ir.Node) bool {
@@ -107,6 +119,16 @@ func (m *matcher) eqNodeSlice(state *matcherState, xs, ys []ir.Node) bool {
 
 	matchAny := false
 
+	var backXS []ir.Node
+	var backYS []ir.Node
+
+	maybeBacktrack := func(matched bool) bool {
+		if !matched && backXS != nil {
+			return m.eqNodeSlice(state, backXS, backYS)
+		}
+		return matched
+	}
+
 	i := 0
 	for i < len(xs) {
 		x := xs[i]
@@ -123,6 +145,8 @@ func (m *matcher) eqNodeSlice(state *matcherState, xs, ys []ir.Node) bool {
 				i++
 			// Lookahead for non-greedy matching.
 			case i+1 < len(xs) && m.eqNode(state, xs[i+1], ys[0]):
+				backXS = xs
+				backYS = ys[1:]
 				matchAny = false
 				i += 2
 				ys = ys[1:]
@@ -133,13 +157,13 @@ func (m *matcher) eqNodeSlice(state *matcherState, xs, ys []ir.Node) bool {
 		}
 
 		if len(ys) == 0 || !m.eqNode(state, x, ys[0]) {
-			return false
+			return maybeBacktrack(false)
 		}
 		i++
 		ys = ys[1:]
 	}
 
-	return len(ys) == 0
+	return maybeBacktrack(len(ys) == 0)
 }
 
 func (m *matcher) eqEncapsedStringPartSlice(state *matcherState, xs, ys []ir.Node) bool {


Test patch:
diff --git a/src/phpgrep/matcher_test.go b/src/phpgrep/matcher_test.go
index e3ab9fc..50333a8 100644
--- a/src/phpgrep/matcher_test.go
+++ b/src/phpgrep/matcher_test.go
@@ -394,6 +394,22 @@ func TestMatch(t *testing.T) {
 
 		{`$_ ?: $_`, `1 ?: 2`},
 
+		{`[${"*"}, $_]`, `[1]`},
+		{`[${"*"}, $_]`, `[1, 2]`},
+		{`[${"*"}, $_]`, `[1, 2, 3]`},
+		{`[${"*"}, 1, 1, ${"*"}]`, `[0, 1, 0, 1, 0, 1, 1, 0, 1, 0]`},
+		{`[${"*"}, $_]`, `[1,]`},
+		{`[${"*"}, $_]`, `[1, 2,]`},
+		{`f(${"*"}, $_)`, `f(1)`},
+		{`f(${"*"}, $_)`, `f(1, 2)`},
+		{`f(${"*"}, $_)`, `f(1, 2, 3)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(1, 1, 1)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(1, 1)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(0, 1, 0, 1, 1, 0)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(1, 0, 1, 0, 1, 0, 1, 1, 0, 1)`},
+		{`f(${"*"}, $_)`, `f(1,)`},
+		{`f(${"*"}, $_)`, `f(1, 2,)`},
+
 		{`isset($x)`, `isset($v)`},
 		{`isset($x, $y)`, `isset($k, $v[$k])`},
 		{`empty($x)`, `empty($v)`},
@@ -544,6 +560,13 @@ func TestMatchNegative(t *testing.T) {
 		{`$x ? $x : $y`, `1 ?: 2`},
 		{`$x ? $y : $z`, `1 ?: 2`},
 
+		{`[${"*"}, $_]`, `[]`},
+
+		{`[${"*"}, 1, 1, ${"*"}]`, `[0, 1, 0, 1, 0, 1, 0, 1, 0]`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(1, 2, 1, 2)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(1)`},
+		{`f(${"*"}, 1, 1, ${"*"})`, `f(0, 1, 0, 1, 0)`},
+
 		{`$x->$_ = $x`, `$this->self = $y`},
 
 		{`$_[0]`, `$v[1]`},
@@ -659,6 +682,10 @@ func BenchmarkMatch(b *testing.B) {
 		{"positive/with-1-named", `$x + 1 * $x`, `$a[0] + 1 * $a[0]`},
 		{"negative/with-1-named", `$x + 1 * $x`, `$a[0] + 1 * $a[1]`},
 		{"positive/with-5-named", `$x1 + $x2 + $x3 + $x4 + $x5`, `1 + 2 + 3 + 4 + 5`},
+
+		{"positive/backtrack-ys", `f(${"*"}, 1, 1, ${"*"})`, `f(1, 0, 1, 0, 1, 0, 1, 1, 0, 1)`},
+		{"positive/backtrack-xs", `f(${"*"}, 1, 2)`, `f(1, 1)`},
+		{"negative/backtrack-ys", `f(${"*"}, 1, 1, ${"*"})`, `f(1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1)`},
 	}
 
 	for _, bench := range benchmarks {