Repository: uber-go/dig
Pull request #398 (2023-10-18 14:40:48)

Fix false positives in cycle detection with child scopes.
Currently, cycle detection works by assigning each constructor node an "order"/index for the scope it was given in. If a path exists between an index and itself, a cycle is detected.

When we create a subscope, we copy all of the parent's nodes to the child scope, but we do not copy their orders. This causes all root scope constructors to effectively have order 0 in the child scope (zero value for a mapping to int). This causes false positives when doing cycle detection as an edge from order 0 to order 0 gets detected.

This PR fixes this bug by copying the order for constructor nodes from parent to child scope when a child scope is created.

The added test case fails before this PR, passes with it.

Ref: https://github.com/uber-go/dig/issues/397

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/uber-go/dig/pull/398?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go) Report
> Merging [#398](https://app.codecov.io/gh/uber-go/dig/pull/398?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go) (f5533e4) into [master](https://app.codecov.io/gh/uber-go/dig/commit/119025f574864a443118bf269f470fe1fac66d0b?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go) (119025f) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

```diff
@@           Coverage Diff           @@
##           master     #398   +/-   ##
=======================================
  Coverage   98.40%   98.40%           
=======================================
  Files          22       22           
  Lines        1502     1505    +3     
=======================================
+ Hits         1478     1481    +3     
  Misses         15       15           
  Partials        9        9           
```


| [Files](https://app.codecov.io/gh/uber-go/dig/pull/398?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go) | Coverage Δ | |
|---|---|---|
| [constructor.go](https://app.codecov.io/gh/uber-go/dig/pull/398?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go#diff-Y29uc3RydWN0b3IuZ28=) | `97.50% <100.00%> (+0.03%)` | :arrow_up: |
| [scope.go](https://app.codecov.io/gh/uber-go/dig/pull/398?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go#diff-c2NvcGUuZ28=) | `98.92% <100.00%> (+0.02%)` | :arrow_up: |

:mega: We’re building smart automated test selection to slash your CI/CD build times. [Learn more](https://about.codecov.io/iterative-testing/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uber-go)


Patch:
diff --git a/constructor.go b/constructor.go
index 208659d..034c41c 100644
--- a/constructor.go
+++ b/constructor.go
@@ -129,6 +129,11 @@ func (n *constructorNode) CType() reflect.Type        { return n.ctype }
 func (n *constructorNode) Order(s *Scope) int         { return n.orders[s] }
 func (n *constructorNode) OrigScope() *Scope          { return n.origS }
 
+// CopyOrder copies the order for the given parent scope to the given child scope.
+func (n *constructorNode) CopyOrder(parent, child *Scope) {
+	n.orders[child] = n.orders[parent]
+}
+
 func (n *constructorNode) String() string {
 	return fmt.Sprintf("deps: %v, ctor: %v", n.paramList, n.ctype)
 }
diff --git a/scope.go b/scope.go
index 216cf18..dc0c7ac 100644
--- a/scope.go
+++ b/scope.go
@@ -121,7 +121,12 @@ func (s *Scope) Scope(name string, opts ...ScopeOption) *Scope {
 	child.recoverFromPanics = s.recoverFromPanics
 
 	// child copies the parent's graph nodes.
-	child.gh.nodes = append(child.gh.nodes, s.gh.nodes...)
+	for _, node := range s.gh.nodes {
+		child.gh.nodes = append(child.gh.nodes, node)
+		if ctrNode, ok := node.Wrapped.(*constructorNode); ok {
+			ctrNode.CopyOrder(s, child)
+		}
+	}
 
 	for _, opt := range opts {
 		opt.noScopeOption()


Test patch:
diff --git a/scope_test.go b/scope_test.go
index 433f036..ff5db69 100644
--- a/scope_test.go
+++ b/scope_test.go
@@ -397,3 +397,20 @@ func TestScopeValueGroups(t *testing.T) {
 		child.RequireInvoke(func(T1) {})
 	})
 }
+
+// This tests that a child scope correctly copies its parent's graph,
+// including information about the order of each node.
+// Otherwise, during cycle detection, constructor nodes might
+// return 0 as the order for all functions in the root scope,
+// causing cycle detection to detect cycles that don't exist.
+func TestFalsePositiveScopeCycleDetection(t *testing.T) {
+	t.Run("single provide", func(t *testing.T) {
+		root := digtest.New(t)
+		root.RequireProvide(func(val string) int { return 0 })
+		root.RequireProvide(func() string { return "sample" })
+		child := root.Scope("child")
+		// Cycle detection would error here because previous two provides
+		// would both have order 0 for child scope.
+		child.RequireProvide(func() float32 { return 0 })
+	})
+}