Repository: VKCOM/noverify
Pull request #836 (2020-12-06 22:03:39)

phpgrep: add backtracking trace tests


Patch:
diff --git a/src/phpgrep/matcher.go b/src/phpgrep/matcher.go
index 2a10361..fcb00e1 100644
--- a/src/phpgrep/matcher.go
+++ b/src/phpgrep/matcher.go
@@ -70,6 +70,9 @@ func (m *matcher) eqArrayItemSlice(state *matcherState, xs, ys []*ir.ArrayItemEx
 
 	maybeBacktrack := func(matched bool) bool {
 		if !matched && backXS != nil {
+			if tracingEnabled && m.tracingBuf != nil {
+				fmt.Fprintf(m.tracingBuf, "%*sbacktrack!\n", m.tracingDepth, " • ")
+			}
 			return m.eqArrayItemSlice(state, backXS, backYS)
 		}
 		return matched
@@ -124,6 +127,9 @@ func (m *matcher) eqNodeSlice(state *matcherState, xs, ys []ir.Node) bool {
 
 	maybeBacktrack := func(matched bool) bool {
 		if !matched && backXS != nil {
+			if tracingEnabled && m.tracingBuf != nil {
+				fmt.Fprintf(m.tracingBuf, "%*sbacktrack!\n", m.tracingDepth, " • ")
+			}
 			return m.eqNodeSlice(state, backXS, backYS)
 		}
 		return matched


Test patch:
diff --git a/src/phpgrep/tracing_test.go b/src/phpgrep/tracing_test.go
index 187fd4a..c30a5a2 100644
--- a/src/phpgrep/tracing_test.go
+++ b/src/phpgrep/tracing_test.go
@@ -215,6 +215,94 @@ func TestTracing(t *testing.T) {
 				" •  •  • eqNode x=*ir.ArrayItemExpr y=*ir.ArrayItemExpr",
 			},
 		},
+
+		// Backtracking.
+		{
+			pattern: `f(${"*"}, 1, 1, ${"*"})`,
+			input:   `f(1, 0, 1, 1)`,
+			trace: []string{
+				"eqNode x=*ir.FunctionCallExpr y=*ir.FunctionCallExpr",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+			},
+		},
+		{
+			pattern: `f(${"*"}, 1, 1, ${"*"})`,
+			input:   `f(1, 0, 1, 0, 1, 1)`,
+			trace: []string{
+				"eqNode x=*ir.FunctionCallExpr y=*ir.FunctionCallExpr",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+			},
+		},
+		{
+			pattern: `f(${"*"}, 1, 1, ${"*"})`,
+			input:   `f(1, 0, 1, 0, 1, 0, 1)`,
+			trace: []string{
+				"eqNode x=*ir.FunctionCallExpr y=*ir.FunctionCallExpr",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • eqNode x=*ir.Argument y=*ir.Argument",
+				" •  • eqNode x=*ir.Lnumber y=*ir.Lnumber",
+				" • backtrack!",
+			},
+		},
+		{
+			pattern: `[${"*"}, $_]`,
+			input:   `[1, 1]`,
+			trace: []string{
+				"eqNode x=*ir.ArrayExpr y=*ir.ArrayExpr",
+				" • eqNode x=*ir.ArrayItemExpr y=*ir.ArrayItemExpr",
+				" •  • eqNode x=*ir.SimpleVar y=*ir.Lnumber",
+				" • backtrack!",
+				" • eqNode x=*ir.ArrayItemExpr y=*ir.ArrayItemExpr",
+				" •  • eqNode x=*ir.SimpleVar y=*ir.Lnumber",
+			},
+		},
 	}
 
 	var c Compiler