Repository: theupdateframework/go-tuf
Pull request #144 (2021-08-24 20:53:50)

Move delegations iterator to internal package
This PR moves the delegations iterator from the client package (private) to public internal packages. This will allow us to reuse the iterator in other packages when we implement writing to delegated targets.

Split into a separate PR to keep review easy, as this is mostly copy & paste and capitalization changes.

coveralls: ## Pull Request Test Coverage Report for [Build 1164151002](https://coveralls.io/builds/42382918)

* **57** of **57**   **(100.0%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **69.512%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/42382918/badge)](https://coveralls.io/builds/42382918) |
| :-- | --: |
| Change from base [Build 1098580196](https://coveralls.io/builds/41906507): |  0.0% |
| Covered Lines: | 1808 |
| Relevant Lines: | 2601 |

---
##### 💛  - [Coveralls](https://coveralls.io)

trishankatdatadog: @hosseinsia 
trishankatdatadog: @raphaelgavache 

Patch:
diff --git a/ALUMNI b/ALUMNI
new file mode 100644
index 0000000..294df41
--- /dev/null
+++ b/ALUMNI
@@ -0,0 +1,4 @@
+Christian Rebischke <chris@shibumi.dev> (github: shibumi)
+Erick Tryzelaar <etryzelaar@google.com> (github: erickt)
+Jonathan Rudenberg <jonathan@flynn.io> (github: titanous)
+Lewis Marshall <lewis@flynn.io> (github: lmars)
\ No newline at end of file
diff --git a/MAINTAINERS b/MAINTAINERS
index 03e8f0b..6c81fce 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -1,4 +1,5 @@
-Christian Rebischke <chris@shibumi.dev> (github: shibumi)
-Erick Tryzelaar <etryzelaar@google.com> (github: erickt)
-Jonathan Rudenberg <jonathan@flynn.io> (github: titanous)
-Lewis Marshall <lewis@flynn.io> (github: lmars)
+Asra Ali <asraa@google.com> (github: asraa)
+Trishank Karthik Kuppusamy <trishank.kuppusamy@datadoghq.com> (github: trishankatdatadog)
+Joshua Lock <jlock@vmware.com> (github: joshuagl)
+Marina Moore <mm9693@nyu.edu> (github: mnm678)
+Hossein Siadati <hossein.siadati@datadoghq.com> (github: hosseinsia)
diff --git a/client/delegations.go b/client/delegations.go
index 9bc6d41..f66a302 100644
--- a/client/delegations.go
+++ b/client/delegations.go
@@ -2,6 +2,7 @@ package client
 
 import (
 	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/internal/targets"
 	"github.com/theupdateframework/go-tuf/verify"
 )
 
@@ -19,15 +20,15 @@ func (c *Client) getTargetFileMeta(target string) (data.TargetFileMeta, error) {
 	// - filter delegations with paths or path_hash_prefixes matching searched target
 	// - 5.6.7.1 cycles protection
 	// - 5.6.7.2 terminations
-	delegations := newDelegationsIterator(target)
+	delegations := targets.NewDelegationsIterator(target)
 	for i := 0; i < c.MaxDelegations; i++ {
-		d, ok := delegations.next()
+		d, ok := delegations.Next()
 		if !ok {
 			return data.TargetFileMeta{}, ErrUnknownTarget{target, snapshot.Version}
 		}
 
 		// covers 5.6.{1,2,3,4,5,6}
-		targets, err := c.loadDelegatedTargets(snapshot, d.delegatee.Name, d.verifier)
+		targets, err := c.loadDelegatedTargets(snapshot, d.Delegatee.Name, d.Verifier)
 		if err != nil {
 			return data.TargetFileMeta{}, err
 		}
@@ -42,7 +43,7 @@ func (c *Client) getTargetFileMeta(target string) (data.TargetFileMeta, error) {
 			if err != nil {
 				return data.TargetFileMeta{}, err
 			}
-			err = delegations.add(targets.Delegations.Roles, d.delegatee.Name, delegationsVerifier)
+			err = delegations.Add(targets.Delegations.Roles, d.Delegatee.Name, delegationsVerifier)
 			if err != nil {
 				return data.TargetFileMeta{}, err
 			}
@@ -114,77 +115,3 @@ func (c *Client) loadDelegatedTargets(snapshot *data.Snapshot, role string, veri
 	}
 	return targets, nil
 }
-
-type delegation struct {
-	delegator string
-	verifier  verify.DelegationsVerifier
-	delegatee data.DelegatedRole
-}
-
-type delegationsIterator struct {
-	stack        []delegation
-	target       string
-	visitedRoles map[string]struct{}
-}
-
-// newDelegationsIterator initialises an iterator with a first step
-// on top level targets
-func newDelegationsIterator(target string) *delegationsIterator {
-	i := &delegationsIterator{
-		target: target,
-		stack: []delegation{
-			{
-				delegatee: data.DelegatedRole{Name: "targets"},
-			},
-		},
-		visitedRoles: make(map[string]struct{}),
-	}
-	return i
-}
-
-func (d *delegationsIterator) next() (value delegation, ok bool) {
-	if len(d.stack) == 0 {
-		return delegation{}, false
-	}
-	delegation := d.stack[len(d.stack)-1]
-	d.stack = d.stack[:len(d.stack)-1]
-
-	// 5.6.7.1: If this role has been visited before, then skip this role (so
-	// that cycles in the delegation graph are avoided).
-	roleName := delegation.delegatee.Name
-	if _, ok := d.visitedRoles[roleName]; ok {
-		return d.next()
-	}
-	d.visitedRoles[roleName] = struct{}{}
-
-	// 5.6.7.2 trim delegations to visit, only the current role and its delegations
-	// will be considered
-	// https://github.com/theupdateframework/specification/issues/168
-	if delegation.delegatee.Terminating {
-		// Empty the stack.
-		d.stack = d.stack[0:0]
-	}
-	return delegation, true
-}
-
-func (d *delegationsIterator) add(roles []data.DelegatedRole, delegator string, verifier verify.DelegationsVerifier) error {
-	for i := len(roles) - 1; i >= 0; i-- {
-		// Push the roles onto the stack in reverse so we get an preorder traversal
-		// of the delegations graph.
-		r := roles[i]
-		matchesPath, err := r.MatchesPath(d.target)
-		if err != nil {
-			return err
-		}
-		if matchesPath {
-			delegation := delegation{
-				delegator: delegator,
-				delegatee: r,
-				verifier:  verifier,
-			}
-			d.stack = append(d.stack, delegation)
-		}
-	}
-
-	return nil
-}
diff --git a/internal/targets/delegation.go b/internal/targets/delegation.go
new file mode 100644
index 0000000..8e09c05
--- /dev/null
+++ b/internal/targets/delegation.go
@@ -0,0 +1,80 @@
+package targets
+
+import (
+	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/verify"
+)
+
+type Delegation struct {
+	Delegator string
+	Verifier  verify.DelegationsVerifier
+	Delegatee data.DelegatedRole
+}
+
+type delegationsIterator struct {
+	stack        []Delegation
+	target       string
+	visitedRoles map[string]struct{}
+}
+
+// NewDelegationsIterator initialises an iterator with a first step
+// on top level targets
+func NewDelegationsIterator(target string) *delegationsIterator {
+	i := &delegationsIterator{
+		target: target,
+		stack: []Delegation{
+			{
+				Delegatee: data.DelegatedRole{Name: "targets"},
+			},
+		},
+		visitedRoles: make(map[string]struct{}),
+	}
+	return i
+}
+
+func (d *delegationsIterator) Next() (value Delegation, ok bool) {
+	if len(d.stack) == 0 {
+		return Delegation{}, false
+	}
+	delegation := d.stack[len(d.stack)-1]
+	d.stack = d.stack[:len(d.stack)-1]
+
+	// 5.6.7.1: If this role has been visited before, then skip this role (so
+	// that cycles in the delegation graph are avoided).
+	roleName := delegation.Delegatee.Name
+	if _, ok := d.visitedRoles[roleName]; ok {
+		return d.Next()
+	}
+	d.visitedRoles[roleName] = struct{}{}
+
+	// 5.6.7.2 trim delegations to visit, only the current role and its delegations
+	// will be considered
+	// https://github.com/theupdateframework/specification/issues/168
+	if delegation.Delegatee.Terminating {
+		// Empty the stack.
+		d.stack = d.stack[0:0]
+	}
+	return delegation, true
+}
+
+func (d *delegationsIterator) Add(roles []data.DelegatedRole, delegator string, verifier verify.DelegationsVerifier) error {
+	for i := len(roles) - 1; i >= 0; i-- {
+		// Push the roles onto the stack in reverse so we get an preorder traversal
+		// of the delegations graph.
+		r := roles[i]
+		matchesPath, err := r.MatchesPath(d.target)
+		if err != nil {
+			return err
+		}
+		if matchesPath {
+			delegation := Delegation{
+				Delegator: delegator,
+				Delegatee: r,
+				Verifier:  verifier,
+			}
+			d.stack = append(d.stack, delegation)
+		}
+	}
+
+	return nil
+}


Test patch:
diff --git a/client/delegations_test.go b/client/delegations_test.go
index ff9b1de..6adda84 100644
--- a/client/delegations_test.go
+++ b/client/delegations_test.go
@@ -16,190 +16,6 @@ import (
 	"github.com/theupdateframework/go-tuf/verify"
 )
 
-var (
-	defaultPathPatterns = []string{"tmp", "*"}
-	noMatchPathPatterns = []string{"vars", "null"}
-)
-
-func TestDelegationsIterator(t *testing.T) {
-	var iteratorTests = []struct {
-		testName    string
-		roles       map[string][]data.DelegatedRole
-		file        string
-		resultOrder []string
-		err         error
-	}{
-		{
-			testName: "no termination",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: defaultPathPatterns},
-					{Name: "e", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "c", Paths: defaultPathPatterns},
-				},
-				"c": {
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-				"e": {
-					{Name: "f", Paths: defaultPathPatterns},
-					{Name: "g", Paths: defaultPathPatterns},
-				},
-				"g": {
-					{Name: "h", Paths: defaultPathPatterns},
-					{Name: "i", Paths: defaultPathPatterns},
-					{Name: "j", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "b", "c", "d", "e", "f", "g", "h", "i", "j"},
-		},
-		{
-			testName: "terminated in b",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: defaultPathPatterns, Terminating: true},
-					{Name: "e", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "c", Paths: defaultPathPatterns},
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "b", "c", "d"},
-		},
-		{
-			testName: "path does not match b",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: noMatchPathPatterns},
-					{Name: "e", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "c", Paths: defaultPathPatterns},
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "e"},
-		},
-		{
-			testName: "path does not match b - path prefixes",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", PathHashPrefixes: []string{"33472a4909"}},
-					{Name: "c", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633"}},
-				},
-				"c": {
-					{Name: "d", PathHashPrefixes: []string{"8baf"}},
-					{Name: "e", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633472a49096ed87f8f764bd597831eac371f40ac39"}},
-				},
-			},
-			file:        "/e/f/g.txt",
-			resultOrder: []string{"targets", "c", "e"},
-		},
-		{
-			testName: "err paths and pathHashPrefixes are set",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: defaultPathPatterns, PathHashPrefixes: defaultPathPatterns},
-				},
-				"b": {},
-			},
-			file:        "",
-			resultOrder: []string{"targets"},
-			err:         data.ErrPathsAndPathHashesSet,
-		},
-		{
-			testName: "cycle avoided 1",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: defaultPathPatterns},
-					{Name: "e", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "targets", Paths: defaultPathPatterns},
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "b", "d", "e"},
-		},
-		{
-			testName: "cycle avoided 2",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "targets", Paths: defaultPathPatterns},
-					{Name: "b", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "targets", Paths: defaultPathPatterns},
-					{Name: "b", Paths: defaultPathPatterns},
-					{Name: "c", Paths: defaultPathPatterns},
-				},
-				"c": {
-					{Name: "c", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "b", "c"},
-		},
-		{
-			testName: "diamond delegation",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "b", Paths: defaultPathPatterns},
-					{Name: "c", Paths: defaultPathPatterns},
-				},
-				"b": {
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-				"c": {
-					{Name: "d", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "b", "d", "c"},
-		},
-		{
-			testName: "simple cycle",
-			roles: map[string][]data.DelegatedRole{
-				"targets": {
-					{Name: "a", Paths: defaultPathPatterns},
-				},
-				"a": {
-					{Name: "a", Paths: defaultPathPatterns},
-				},
-			},
-			file:        "",
-			resultOrder: []string{"targets", "a"},
-		},
-	}
-
-	for _, tt := range iteratorTests {
-		t.Run(tt.testName, func(t *testing.T) {
-			d := newDelegationsIterator(tt.file)
-			var iterationOrder []string
-			for {
-				r, ok := d.next()
-				if !ok {
-					break
-				}
-				iterationOrder = append(iterationOrder, r.delegatee.Name)
-				delegations, ok := tt.roles[r.delegatee.Name]
-				if !ok {
-					continue
-				}
-				err := d.add(delegations, r.delegatee.Name, verify.DelegationsVerifier{})
-				assert.Equal(t, tt.err, err)
-			}
-			assert.Equal(t, tt.resultOrder, iterationOrder)
-		})
-	}
-}
-
 func TestGetTargetMeta(t *testing.T) {
 	verify.IsExpired = func(t time.Time) bool { return false }
 	c, closer := initTestDelegationClient(t, "testdata/php-tuf-fixtures/TUFTestFixture3LevelDelegation")
diff --git a/internal/targets/delegation_test.go b/internal/targets/delegation_test.go
new file mode 100644
index 0000000..bb460b1
--- /dev/null
+++ b/internal/targets/delegation_test.go
@@ -0,0 +1,193 @@
+package targets
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/verify"
+)
+
+var (
+	defaultPathPatterns = []string{"tmp", "*"}
+	noMatchPathPatterns = []string{"vars", "null"}
+)
+
+func TestDelegationsIterator(t *testing.T) {
+	var iteratorTests = []struct {
+		testName    string
+		roles       map[string][]data.DelegatedRole
+		file        string
+		resultOrder []string
+		err         error
+	}{
+		{
+			testName: "no termination",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns},
+					{Name: "e", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns},
+				},
+				"c": {
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+				"e": {
+					{Name: "f", Paths: defaultPathPatterns},
+					{Name: "g", Paths: defaultPathPatterns},
+				},
+				"g": {
+					{Name: "h", Paths: defaultPathPatterns},
+					{Name: "i", Paths: defaultPathPatterns},
+					{Name: "j", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "c", "d", "e", "f", "g", "h", "i", "j"},
+		},
+		{
+			testName: "terminated in b",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, Terminating: true},
+					{Name: "e", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns},
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "c", "d"},
+		},
+		{
+			testName: "path does not match b",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: noMatchPathPatterns},
+					{Name: "e", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns},
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "e"},
+		},
+		{
+			testName: "path does not match b - path prefixes",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", PathHashPrefixes: []string{"33472a4909"}},
+					{Name: "c", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633"}},
+				},
+				"c": {
+					{Name: "d", PathHashPrefixes: []string{"8baf"}},
+					{Name: "e", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633472a49096ed87f8f764bd597831eac371f40ac39"}},
+				},
+			},
+			file:        "/e/f/g.txt",
+			resultOrder: []string{"targets", "c", "e"},
+		},
+		{
+			testName: "err paths and pathHashPrefixes are set",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, PathHashPrefixes: defaultPathPatterns},
+				},
+				"b": {},
+			},
+			file:        "",
+			resultOrder: []string{"targets"},
+			err:         data.ErrPathsAndPathHashesSet,
+		},
+		{
+			testName: "cycle avoided 1",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns},
+					{Name: "e", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "targets", Paths: defaultPathPatterns},
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "d", "e"},
+		},
+		{
+			testName: "cycle avoided 2",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "targets", Paths: defaultPathPatterns},
+					{Name: "b", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "targets", Paths: defaultPathPatterns},
+					{Name: "b", Paths: defaultPathPatterns},
+					{Name: "c", Paths: defaultPathPatterns},
+				},
+				"c": {
+					{Name: "c", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "c"},
+		},
+		{
+			testName: "diamond delegation",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns},
+					{Name: "c", Paths: defaultPathPatterns},
+				},
+				"b": {
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+				"c": {
+					{Name: "d", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "d", "c"},
+		},
+		{
+			testName: "simple cycle",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "a", Paths: defaultPathPatterns},
+				},
+				"a": {
+					{Name: "a", Paths: defaultPathPatterns},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "a"},
+		},
+	}
+
+	for _, tt := range iteratorTests {
+		t.Run(tt.testName, func(t *testing.T) {
+			d := NewDelegationsIterator(tt.file)
+			var iterationOrder []string
+			for {
+				r, ok := d.Next()
+				if !ok {
+					break
+				}
+				iterationOrder = append(iterationOrder, r.Delegatee.Name)
+				delegations, ok := tt.roles[r.Delegatee.Name]
+				if !ok {
+					continue
+				}
+				err := d.Add(delegations, r.Delegatee.Name, verify.DelegationsVerifier{})
+				assert.Equal(t, tt.err, err)
+			}
+			assert.Equal(t, tt.resultOrder, iterationOrder)
+		})
+	}
+}