This is an automated email from the ASF dual-hosted git repository. wusheng pushed a commit to branch fix/contains-distinct-matching in repository https://gitbox.apache.org/repos/asf/skywalking-infra-e2e.git
commit 15723afbdf3c4e5ef9a8ff43e00b68d9dd281227 Author: Wu Sheng <[email protected]> AuthorDate: Sun Apr 12 21:58:00 2026 +0800 fix: enforce distinct matching in contains and add containsOnce with backtracking Fix a bug where one actual item could satisfy multiple expected entries in `contains`, causing false-positive test results (apache/skywalking#8752). Now each actual item can only be claimed once (greedy distinct matching). Add `containsOnce` keyword that uses backtracking to find optimal assignment between expected entries and actual items, solving cases where greedy ordering fails. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]> --- CLAUDE.md | 11 +- docs/en/setup/Configuration-File.md | 22 ++- internal/components/verifier/verifier_test.go | 230 ++++++++++++++++++++++++++ third-party/go/template/exec.go | 168 ++++++++++++++++++- third-party/go/template/parse/lex.go | 6 +- third-party/go/template/parse/node.go | 20 +++ third-party/go/template/parse/parse.go | 11 ++ 7 files changed, 460 insertions(+), 8 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 04a5049..59dc732 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -152,4 +152,13 @@ verify: ### GitHub Actions Integration - `action.yaml` at project root defines the composite action -- Inputs: e2e-file, log-dir, plus matrix vars for log isolation \ No newline at end of file +- Inputs: e2e-file, log-dir, plus matrix vars for log isolation + +## GitHub Actions Allow List + +Apache enforces an allow list for third-party GitHub Actions. All third-party actions must be pinned to an approved SHA from: +https://github.com/apache/infrastructure-actions/blob/main/approved_patterns.yml + +If a PR is blocked by "action is not allowed" errors, check the approved list and update `.github/workflows/` files to use the approved SHA pin instead of a version tag. + +Actions owned by `actions/*` (GitHub), `github/*`, and `apache/*` are always allowed (enterprise-owned). \ No newline at end of file diff --git a/docs/en/setup/Configuration-File.md b/docs/en/setup/Configuration-File.md index 587fd6a..fd4c77a 100644 --- a/docs/en/setup/Configuration-File.md +++ b/docs/en/setup/Configuration-File.md @@ -220,9 +220,13 @@ Verify that the number fits the range. ##### List Matches -Verify the data in the condition list, Currently, it is only supported when all the conditions in the list are executed, it is considered as successful. +Two keywords are available for verifying lists: `contains` and `containsOnce`. -Here is an example, It's means the list values must have value is greater than 0, also have value greater than 1, Otherwise verify is failure. +**`contains`** checks that each expected entry matches a distinct actual item using greedy matching (first-come, first-served order). +Each expected entry can only claim one actual item, and each actual item can only be claimed once. +Extra actual items beyond the expected entries are allowed. + +Here is an example, it means the list values must have an item with value greater than 0 and another item with value greater than 1. Otherwise verification fails. ```yaml {{- contains .list }} - key: {{ gt .value 0 }} @@ -230,6 +234,20 @@ Here is an example, It's means the list values must have value is greater than 0 {{- end }} ``` +**`containsOnce`** provides the same semantics as `contains` but uses backtracking to find a valid assignment. +This is useful when the greedy order of `contains` cannot find a valid match but one exists. +For example, if a generic expected entry (e.g., `notEmpty`) appears before a specific one (e.g., a hardcoded value), +`contains` might greedily claim the wrong actual item, while `containsOnce` will try all combinations to find a valid assignment. + +```yaml +{{- containsOnce .list }} +- name: {{ notEmpty .name }} + language: {{ notEmpty .language }} +- name: {{ notEmpty .name }} + language: JAVA +{{- end }} +``` + ##### Encoding In order to make the program easier for users to read and use, some code conversions are provided. diff --git a/internal/components/verifier/verifier_test.go b/internal/components/verifier/verifier_test.go index 167b5d1..dfa5634 100644 --- a/internal/components/verifier/verifier_test.go +++ b/internal/components/verifier/verifier_test.go @@ -272,6 +272,236 @@ metrics: }, wantErr: false, }, { + name: "contains should require distinct actual items for each expected entry", + args: args{ + actualData: ` +metrics: + - name: service-A + id: abc +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} +{{- end }} +`, + }, + wantErr: true, // expected 2 entries but actual only has 1 + }, + { + name: "contains should not pass when extra expected entries are added with echo-only conditions", + args: args{ + actualData: ` +metrics: + - name: service-A + id: abc + - name: service-B + id: def +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} +{{- end }} +`, + }, + wantErr: true, // expected 3 entries but actual only has 2 + }, + { + name: "contains greedy cannot solve reordered assignment", + args: args{ + actualData: ` +- name: service-A + language: JAVA +- name: service-B + language: GO +`, + expectedTemplate: ` +{{- contains . }} +- name: {{ notEmpty .name }} + language: {{ notEmpty .language }} +- name: {{ notEmpty .name }} + language: JAVA +{{- end }} +`, + }, + wantErr: true, // greedy contains can't solve this; containsOnce with backtracking will + }, + { + name: "containsOnce should backtrack to find valid assignment", + args: args{ + actualData: ` +- name: service-A + language: JAVA +- name: service-B + language: GO +`, + expectedTemplate: ` +{{- containsOnce . }} +- name: {{ notEmpty .name }} + language: {{ notEmpty .language }} +- name: {{ notEmpty .name }} + language: JAVA +{{- end }} +`, + }, + wantErr: false, // backtracking finds: expected[0]→actual[1], expected[1]→actual[0] + }, + { + name: "containsOnce should require distinct actual items", + args: args{ + actualData: ` +metrics: + - name: service-A + id: abc +`, + expectedTemplate: ` +metrics: +{{- containsOnce .metrics }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} +{{- end }} +`, + }, + wantErr: true, // 1 actual item cannot satisfy 2 expected entries + }, + { + name: "containsOnce should pass when enough distinct items match", + args: args{ + actualData: ` +metrics: + - name: service-A + id: abc + - name: service-B + id: def + - name: service-C + id: ghi +`, + expectedTemplate: ` +metrics: +{{- containsOnce .metrics }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} + - name: {{ notEmpty .name }} + id: {{ notEmpty .id }} +{{- end }} +`, + }, + wantErr: false, // 3 actual items, 2 expected → enough distinct matches + }, + { + name: "containsOnce should fail when specific value missing", + args: args{ + actualData: ` +- name: service-B + value: "200" +- name: service-C + value: "300" +`, + expectedTemplate: ` +{{- containsOnce . }} +- name: service-A + value: "100" +{{- end }} +`, + }, + wantErr: true, // service-A does not exist + }, + { + name: "contains should match specific values in reversed order", + args: args{ + actualData: ` +metrics: + - name: service-B + value: "200" + - name: service-A + value: "100" +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: service-A + value: "100" + - name: service-B + value: "200" +{{- end }} +`, + }, + wantErr: false, // both exist, order shouldn't matter + }, + { + name: "contains should fail when one specific value is wrong", + args: args{ + actualData: ` +metrics: + - name: service-A + value: "100" + - name: service-B + value: "200" +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: service-A + value: "100" + - name: service-C + value: "300" +{{- end }} +`, + }, + wantErr: true, // service-C does not exist in actual + }, + { + name: "contains should match unordered actual data correctly", + args: args{ + actualData: ` +metrics: + - name: service-B + value: 200 + - name: service-A + value: 100 +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: service-A + value: 100 +{{- end }} +`, + }, + wantErr: false, // service-A exists in actual, order shouldn't matter + }, + { + name: "contains should fail when specific expected value is missing from actual", + args: args{ + actualData: ` +metrics: + - name: service-B + value: 200 + - name: service-C + value: 300 +`, + expectedTemplate: ` +metrics: +{{- contains .metrics }} + - name: service-A + value: 100 +{{- end }} +`, + }, + wantErr: true, // service-A does not exist in actual + }, + { name: "notEmpty with nil", args: args{ actualData: ` diff --git a/third-party/go/template/exec.go b/third-party/go/template/exec.go index da23dbc..e12ca1c 100644 --- a/third-party/go/template/exec.go +++ b/third-party/go/template/exec.go @@ -279,6 +279,8 @@ func (s *state) walk(dot reflect.Value, node parse.Node) { s.walkIfOrWith(parse.NodeWith, dot, node.Pipe, node.List, node.ElseList) case *parse.ContainsNode: s.walkContains(dot, node) + case *parse.ContainsOnceNode: + s.walkContainsOnce(dot, node) default: s.errorf("unknown node: %s", node) } @@ -440,6 +442,8 @@ func (s *state) walkContains(dot reflect.Value, r *parse.ContainsNode) { expectedSize := 0 // matched stores the matched pair of indices <expected index>: <actual index> matched := make(map[int]int) + // claimedActual tracks which actual items have already been claimed by an expected entry + claimedActual := make(map[int]bool) output := make([]any, val.Len()) notMatched := make(map[int]any) for i := 0; i < val.Len(); i++ { @@ -449,10 +453,17 @@ func (s *state) walkContains(dot reflect.Value, r *parse.ContainsNode) { actual, _ := printableValue(val.Index(i)) for j, expected := range expectedArr { if fmt.Sprint(actual) == fmt.Sprint(expected) { - matched[j] = i - output[i] = actual + if !claimedActual[i] { + if _, alreadyMatched := matched[j]; !alreadyMatched { + matched[j] = i + claimedActual[i] = true + output[i] = actual + } + } } else { - notMatched[j] = expected + if _, alreadyMatched := matched[j]; !alreadyMatched { + notMatched[j] = expected + } output[i] = expected } } @@ -513,6 +524,157 @@ func (s *state) walkContains(dot reflect.Value, r *parse.ContainsNode) { } } +func (s *state) walkContainsOnce(dot reflect.Value, r *parse.ContainsOnceNode) { + s.at(r) + defer s.pop(s.mark()) + val, _ := indirect(s.evalPipeline(dot, r.Pipe)) + // mark top of stack before any variables in the body are pushed. + mark := s.mark() + oneIteration := func(index, elem reflect.Value) []any { + var b bytes.Buffer + ob := s.wr + s.wr = &b + + // Set top var (lexically the second if there are two) to the element. + if len(r.Pipe.Decl) > 0 { + s.setTopVar(1, elem) + } + // Set next var (lexically the first if there are two) to the index. + if len(r.Pipe.Decl) > 1 { + s.setTopVar(2, index) + } + s.walk(elem, r.List) + s.pop(mark) + + s.wr = ob + + // the contents inside `containsOnce` must be an array + var re []any + if err := yaml.Unmarshal(b.Bytes(), &re); err != nil { + logger.Log.Errorf("failed to unmarshal index: %v, %v", index, err) + } + return re + } + switch val.Kind() { + case reflect.Array, reflect.Slice: + if val.Len() == 0 { + break + } + expectedSize := 0 + // Build match matrix: matchable[j][i] = true means expected[j] can match actual[i] + // Also store the rendered expected values for error reporting + type renderedEntry struct { + actual any + expected []any + } + entries := make([]renderedEntry, val.Len()) + for i := 0; i < val.Len(); i++ { + expectedArr := oneIteration(reflect.ValueOf(i), val.Index(i)) + expectedSize = len(expectedArr) + actual, _ := printableValue(val.Index(i)) + entries[i] = renderedEntry{actual: actual, expected: expectedArr} + } + + // matchable[j] contains the list of actual indices that can satisfy expected[j] + matchable := make([][]int, expectedSize) + // lastExpected[j] stores a rendered expected value for error reporting + lastExpected := make(map[int]any) + for j := 0; j < expectedSize; j++ { + for i := 0; i < val.Len(); i++ { + lastExpected[j] = entries[i].expected[j] + if fmt.Sprint(entries[i].actual) == fmt.Sprint(entries[i].expected[j]) { + matchable[j] = append(matchable[j], i) + } + } + } + + // Backtracking to find a valid assignment: each expected[j] maps to a distinct actual[i] + assignment := make([]int, expectedSize) // assignment[j] = actual index for expected[j] + for j := range assignment { + assignment[j] = -1 + } + claimedActual := make(map[int]bool) + + var backtrack func(j int) bool + backtrack = func(j int) bool { + if j == expectedSize { + return true // all expected entries matched + } + for _, i := range matchable[j] { + if !claimedActual[i] { + claimedActual[i] = true + assignment[j] = i + if backtrack(j + 1) { + return true + } + claimedActual[i] = false + assignment[j] = -1 + } + } + return false + } + + var addRootIndent = func(b []byte, n int) []byte { + prefix := append([]byte("\n"), bytes.Repeat([]byte(" "), n)...) + b = append(prefix[1:], b...) // Indent first line + return bytes.ReplaceAll(b, []byte("\n"), prefix) + } + var marshal []byte + if backtrack(0) { + value, _ := printableValue(val) + marshal, _ = yaml.Marshal(value) + } else { + // Build output: actual items plus unmatched expected items for error reporting + output := make([]any, val.Len()) + for i := 0; i < val.Len(); i++ { + output[i] = entries[i].actual + } + for j := 0; j < expectedSize; j++ { + if assignment[j] == -1 { + if exp, ok := lastExpected[j]; ok { + output = append(output, exp) + } + } + } + marshal, _ = yaml.Marshal(output) + } + + listTokenIndex := strings.Index(strings.TrimPrefix(r.List.Nodes[0].String(), "\n"), "-") + marshal = addRootIndent(marshal, listTokenIndex) + _, _ = s.wr.Write(append([]byte("\n"), marshal...)) + return + case reflect.Map: + if val.Len() == 0 { + break + } + om := fmtsort.Sort(val) + for i, key := range om.Key { + oneIteration(key, om.Value[i]) + } + return + case reflect.Chan: + if val.IsNil() { + break + } + i := 0 + for ; ; i++ { + elem, ok := val.Recv() + if !ok { + break + } + oneIteration(reflect.ValueOf(i), elem) + } + if i == 0 { + break + } + return + case reflect.Invalid: + break // An invalid value is likely a nil map, etc. and acts like an empty map. + default: + s.errorf("containsOnce can't iterate over %v", val) + } +} + func (s *state) walkTemplate(dot reflect.Value, t *parse.TemplateNode) { s.at(t) tmpl := s.tmpl.tmpl[t.Name] diff --git a/third-party/go/template/parse/lex.go b/third-party/go/template/parse/lex.go index c1876b2..8f552cf 100644 --- a/third-party/go/template/parse/lex.go +++ b/third-party/go/template/parse/lex.go @@ -70,7 +70,8 @@ const ( itemRange // range keyword itemTemplate // template keyword itemWith // with keyword - itemContains // contains keyword + itemContains // contains keyword + itemContainsOnce // containsOnce keyword ) var key = map[string]itemType{ @@ -84,7 +85,8 @@ var key = map[string]itemType{ "nil": itemNil, "template": itemTemplate, "with": itemWith, - "contains": itemContains, + "contains": itemContains, + "containsOnce": itemContainsOnce, } const eof = -1 diff --git a/third-party/go/template/parse/node.go b/third-party/go/template/parse/node.go index 938d5bf..6551fa0 100644 --- a/third-party/go/template/parse/node.go +++ b/third-party/go/template/parse/node.go @@ -71,6 +71,7 @@ const ( NodeVariable // A $ variable. NodeWith // A with action. NodeContains // A contains action. + NodeContainsOnce // A containsOnce action. ) // Nodes. @@ -831,6 +832,8 @@ func (b *BranchNode) writeTo(sb *strings.Builder) { name = "with" case NodeContains: name = "contains" + case NodeContainsOnce: + name = "containsOnce" default: panic("unknown branch type") } @@ -861,6 +864,8 @@ func (b *BranchNode) Copy() Node { return b.tr.newWith(b.Pos, b.Line, b.Pipe, b.List, b.ElseList) case NodeContains: return b.tr.newContains(b.Pos, b.Line, b.Pipe, b.List, b.ElseList) + case NodeContainsOnce: + return b.tr.newContainsOnce(b.Pos, b.Line, b.Pipe, b.List, b.ElseList) default: panic("unknown branch type") } @@ -918,6 +923,21 @@ func (w *ContainsNode) Copy() Node { return w.tr.newContains(w.Pos, w.Line, w.Pipe.CopyPipe(), w.List.CopyList(), w.ElseList.CopyList()) } +// ContainsOnceNode represents a {{containsOnce}} action and its commands. +// It uses backtracking to find a valid assignment where each expected entry +// matches a distinct actual item. +type ContainsOnceNode struct { + BranchNode +} + +func (t *Tree) newContainsOnce(pos Pos, line int, pipe *PipeNode, list *ListNode, elseList *ListNode) *ContainsOnceNode { + return &ContainsOnceNode{BranchNode{tr: t, NodeType: NodeContainsOnce, Pos: pos, Line: line, Pipe: pipe, List: list}} +} + +func (w *ContainsOnceNode) Copy() Node { + return w.tr.newContainsOnce(w.Pos, w.Line, w.Pipe.CopyPipe(), w.List.CopyList(), w.ElseList.CopyList()) +} + // TemplateNode represents a {{template}} action. type TemplateNode struct { NodeType diff --git a/third-party/go/template/parse/parse.go b/third-party/go/template/parse/parse.go index 914bd96..bfe4f88 100644 --- a/third-party/go/template/parse/parse.go +++ b/third-party/go/template/parse/parse.go @@ -367,6 +367,8 @@ func (t *Tree) action() (n Node) { return t.withControl() case itemContains: return t.containsControl() + case itemContainsOnce: + return t.containsOnceControl() } t.backup() token := t.peek() @@ -513,6 +515,15 @@ func (t *Tree) containsControl() Node { return t.newContains(t.parseControl(false, "contains")) } +// ContainsOnce: +// +// {{containsOnce pipeline}} itemList {{end}} +// +// ContainsOnce keyword is past. +func (t *Tree) containsOnceControl() Node { + return t.newContainsOnce(t.parseControl(false, "containsOnce")) +} + // End: // {{end}} // End keyword is past.
