Added a Breadth-first top down walk function
to policy_walk.
Test: m droid dist
Change-Id: I678d2a2402c7c3ab446e8533c9f862cd8f54f889
diff --git a/tools/compliance/policy_walk_test.go b/tools/compliance/policy_walk_test.go
index c55e2f8..0bc37f8 100644
--- a/tools/compliance/policy_walk_test.go
+++ b/tools/compliance/policy_walk_test.go
@@ -16,9 +16,22 @@
import (
"bytes"
+ "fmt"
+ "os"
+ "strings"
"testing"
)
+func TestMain(m *testing.M) {
+ // Change into the cmd directory before running the tests
+ // so they can find the testdata directory.
+ if err := os.Chdir("cmd"); err != nil {
+ fmt.Printf("failed to change to testdata directory: %s\n", err)
+ os.Exit(1)
+ }
+ os.Exit(m.Run())
+}
+
func TestWalkResolutionsForCondition(t *testing.T) {
tests := []struct {
name string
@@ -1197,3 +1210,417 @@
})
}
}
+
+func TestWalkTopDownBreadthFirst(t *testing.T) {
+ tests := []struct {
+ name string
+ roots []string
+ edges []annotated
+ expectedResult []string
+ }{
+ {
+ name: "bin/bin1",
+ roots: []string{"bin/bin1.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin2",
+ roots: []string{"bin/bin2.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin3",
+ roots: []string{"bin/bin3.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin3.meta_lic",
+ },
+ },
+ {
+ name: "lib/liba.so",
+ roots: []string{"lib/liba.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/liba.so.meta_lic",
+ },
+ },
+ {
+ name: "lib/libb.so",
+ roots: []string{"lib/libb.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "lib/libc.so",
+ roots: []string{"lib/libc.a.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "lib/libd.so",
+ roots: []string{"lib/libd.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "highest.apex",
+ roots: []string{"highest.apex.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/highest.apex.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "container.zip",
+ roots: []string{"container.zip.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/container.zip.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "application",
+ roots: []string{"application.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/application.meta_lic",
+ "testdata/notice/bin/bin3.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin1&lib/liba",
+ roots: []string{"bin/bin1.meta_lic","lib/liba.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin2&lib/libd",
+ roots: []string{"bin/bin2.meta_lic", "lib/libd.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "application&bin/bin3",
+ roots: []string{"application.meta_lic", "bin/bin3.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/application.meta_lic",
+ "testdata/notice/bin/bin3.meta_lic",
+ "testdata/notice/bin/bin3.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "highest.apex&container.zip",
+ roots: []string{"highest.apex.meta_lic", "container.zip.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/highest.apex.meta_lic",
+ "testdata/notice/container.zip.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ stderr := &bytes.Buffer{}
+ actualOut := &bytes.Buffer{}
+
+ rootFiles := make([]string, 0, len(tt.roots))
+ for _, r := range tt.roots {
+ rootFiles = append(rootFiles, "testdata/notice/"+r)
+ }
+
+ lg, err := ReadLicenseGraph(GetFS(""), stderr, rootFiles)
+
+ if err != nil {
+ t.Errorf("unexpected test data error: got %s, want no error", err)
+ return
+ }
+
+ expectedRst := tt.expectedResult
+
+ WalkTopDownBreadthFirst(nil, lg, func(lg *LicenseGraph, tn *TargetNode, path TargetEdgePath) bool {
+ fmt.Fprintln(actualOut, tn.Name())
+ return true
+ })
+
+ actualRst := strings.Split(actualOut.String(), "\n")
+
+ if len(actualRst) > 0 {
+ actualRst = actualRst[:len(actualRst)-1]
+ }
+
+ t.Logf("actual nodes visited: %s", actualOut.String())
+ t.Logf("expected nodes visited: %s", strings.Join(expectedRst, "\n"))
+
+ if len(actualRst) != len(expectedRst) {
+ t.Errorf("WalkTopDownBreadthFirst: number of visited nodes is different: got %d, want %d", len(actualRst), len(expectedRst))
+ }
+
+ for i := 0; i < len(actualRst) && i < len(expectedRst); i++ {
+ if actualRst[i] != expectedRst[i] {
+ t.Errorf("WalkTopDownBreadthFirst: lines differ at index %d: got %q, want %q", i, actualRst[i], expectedRst[i])
+ break
+ }
+ }
+
+ if len(actualRst) < len(expectedRst) {
+ t.Errorf("WalkTopDownBreadthFirst: extra lines at %d: got %q, want nothing", len(actualRst), expectedRst[len(actualRst)])
+ }
+
+ if len(expectedRst) < len(actualRst) {
+ t.Errorf("WalkTopDownBreadthFirst: missing lines at %d: got nothing, want %q", len(expectedRst), actualRst[len(expectedRst)])
+ }
+ })
+ }
+}
+
+func TestWalkTopDownBreadthFirstWithoutDuplicates(t *testing.T) {
+ tests := []struct {
+ name string
+ roots []string
+ edges []annotated
+ expectedResult []string
+ }{
+ {
+ name: "bin/bin1",
+ roots: []string{"bin/bin1.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin2",
+ roots: []string{"bin/bin2.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin3",
+ roots: []string{"bin/bin3.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin3.meta_lic",
+ },
+ },
+ {
+ name: "lib/liba.so",
+ roots: []string{"lib/liba.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/liba.so.meta_lic",
+ },
+ },
+ {
+ name: "lib/libb.so",
+ roots: []string{"lib/libb.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "lib/libc.so",
+ roots: []string{"lib/libc.a.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "lib/libd.so",
+ roots: []string{"lib/libd.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "highest.apex",
+ roots: []string{"highest.apex.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/highest.apex.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "container.zip",
+ roots: []string{"container.zip.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/container.zip.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ {
+ name: "application",
+ roots: []string{"application.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/application.meta_lic",
+ "testdata/notice/bin/bin3.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin1&lib/liba",
+ roots: []string{"bin/bin1.meta_lic", "lib/liba.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ },
+ },
+ {
+ name: "bin/bin2&lib/libd",
+ roots: []string{"bin/bin2.meta_lic", "lib/libd.so.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "application&bin/bin3",
+ roots: []string{"application.meta_lic", "bin/bin3.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/application.meta_lic",
+ "testdata/notice/bin/bin3.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ },
+ },
+ {
+ name: "highest.apex&container.zip",
+ roots: []string{"highest.apex.meta_lic", "container.zip.meta_lic"},
+ expectedResult: []string{
+ "testdata/notice/highest.apex.meta_lic",
+ "testdata/notice/container.zip.meta_lic",
+ "testdata/notice/bin/bin1.meta_lic",
+ "testdata/notice/bin/bin2.meta_lic",
+ "testdata/notice/lib/liba.so.meta_lic",
+ "testdata/notice/lib/libb.so.meta_lic",
+ "testdata/notice/lib/libc.a.meta_lic",
+ "testdata/notice/lib/libd.so.meta_lic",
+ },
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ stderr := &bytes.Buffer{}
+ actualOut := &bytes.Buffer{}
+
+ rootFiles := make([]string, 0, len(tt.roots))
+ for _, r := range tt.roots {
+ rootFiles = append(rootFiles, "testdata/notice/"+r)
+ }
+
+ lg, err := ReadLicenseGraph(GetFS(""), stderr, rootFiles)
+
+ if err != nil {
+ t.Errorf("unexpected test data error: got %s, want no error", err)
+ return
+ }
+
+ expectedRst := tt.expectedResult
+
+ //Keeping track of the visited nodes
+ //Only add to actualOut if not visited
+ visitedNodes := make(map[string]struct{})
+ WalkTopDownBreadthFirst(nil, lg, func(lg *LicenseGraph, tn *TargetNode, path TargetEdgePath) bool {
+ if _, alreadyVisited := visitedNodes[tn.Name()]; alreadyVisited {
+ return false
+ }
+ fmt.Fprintln(actualOut, tn.Name())
+ visitedNodes[tn.Name()] = struct{}{}
+ return true
+ })
+
+ actualRst := strings.Split(actualOut.String(), "\n")
+
+ if len(actualRst) > 0 {
+ actualRst = actualRst[:len(actualRst)-1]
+ }
+
+ t.Logf("actual nodes visited: %s", actualOut.String())
+ t.Logf("expected nodes visited: %s", strings.Join(expectedRst, "\n"))
+
+ if len(actualRst) != len(expectedRst) {
+ t.Errorf("WalkTopDownBreadthFirst: number of visited nodes is different: got %d, want %d", len(actualRst), len(expectedRst))
+ }
+
+ for i := 0; i < len(actualRst) && i < len(expectedRst); i++ {
+ if actualRst[i] != expectedRst[i] {
+ t.Errorf("WalkTopDownBreadthFirst: lines differ at index %d: got %q, want %q", i, actualRst[i], expectedRst[i])
+ break
+ }
+ }
+
+ if len(actualRst) < len(expectedRst) {
+ t.Errorf("WalkTopDownBreadthFirst: extra lines at %d: got %q, want nothing", len(actualRst), expectedRst[len(actualRst)])
+ }
+
+ if len(expectedRst) < len(actualRst) {
+ t.Errorf("WalkTopDownBreadthFirst: missing lines at %d: got nothing, want %q", len(expectedRst), actualRst[len(expectedRst)])
+ }
+ })
+ }
+}