uber-go / dig
1
// Copyright (c) 2019 Uber Technologies, Inc.
2
//
3
// Permission is hereby granted, free of charge, to any person obtaining a copy
4
// of this software and associated documentation files (the "Software"), to deal
5
// in the Software without restriction, including without limitation the rights
6
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7
// copies of the Software, and to permit persons to whom the Software is
8
// furnished to do so, subject to the following conditions:
9
//
10
// The above copyright notice and this permission notice shall be included in
11
// all copies or substantial portions of the Software.
12
//
13
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19
// THE SOFTWARE.
20

21
package dig
22

23
import (
24
	"bytes"
25
	"fmt"
26

27
	"go.uber.org/dig/internal/digreflect"
28
)
29

30
type cycleEntry struct {
31
	Key  key
32
	Func *digreflect.Func
33
}
34

35
type errCycleDetected struct {
36
	Path []cycleEntry
37
}
38

39
func (e errCycleDetected) Error() string {
40
	// We get something like,
41
	//
42
	//   foo provided by "path/to/package".NewFoo (path/to/file.go:42)
43
	//   	depends on bar provided by "another/package".NewBar (somefile.go:1)
44
	//   	depends on baz provided by "somepackage".NewBar (anotherfile.go:2)
45
	//   	depends on foo provided by "path/to/package".NewFoo (path/to/file.go:42)
46
	//
47 2
	b := new(bytes.Buffer)
48

49
	for i, entry := range e.Path {
50 2
		if i > 0 {
51 2
			b.WriteString("\n\tdepends on ")
52
		}
53 2
		fmt.Fprintf(b, "%v provided by %v", entry.Key, entry.Func)
54
	}
55 2
	return b.String()
56
}
57

58
// IsCycleDetected returns a boolean as to whether the provided error indicates
59
// a cycle was detected in the container graph.
60
func IsCycleDetected(err error) bool {
61 2
	_, ok := RootCause(err).(errCycleDetected)
62 2
	return ok
63
}
64

65
func verifyAcyclic(c containerStore, n provider, k key) error {
66 2
	visited := make(map[key]struct{})
67 2
	err := detectCycles(n, c, []cycleEntry{
68 2
		{Key: k, Func: n.Location()},
69 2
	}, visited)
70 2
	if err != nil {
71 2
		err = errf("this function introduces a cycle", err)
72
	}
73 2
	return err
74
}
75

76
func detectCycles(n provider, c containerStore, path []cycleEntry, visited map[key]struct{}) error {
77 2
	var err error
78 2
	walkParam(n.ParamList(), paramVisitorFunc(func(param param) bool {
79 2
		if err != nil {
80 2
			return false
81
		}
82

83 2
		var (
84 2
			k         key
85 2
			providers []provider
86 2
		)
87 2
		switch p := param.(type) {
88 2
		case paramSingle:
89 2
			k = key{name: p.Name, t: p.Type}
90 2
			if _, ok := visited[k]; ok {
91
				// We've already checked the dependencies for this type.
92 2
				return false
93
			}
94 2
			providers = c.getValueProviders(p.Name, p.Type)
95 2
		case paramGroupedSlice:
96
			// NOTE: The key uses the element type, not the slice type.
97 2
			k = key{group: p.Group, t: p.Type.Elem()}
98 2
			if _, ok := visited[k]; ok {
99
				// We've already checked the dependencies for this type.
100 2
				return false
101
			}
102 2
			providers = c.getGroupProviders(p.Group, p.Type.Elem())
103 2
		default:
104
			// Recurse for non-edge params.
105 2
			return true
106
		}
107

108 2
		entry := cycleEntry{Func: n.Location(), Key: k}
109

110 2
		if len(path) > 0 {
111
			// Only mark a key as visited if path exists, i.e. this is not the
112
			// first iteration through the c.verifyAcyclic() check. Otherwise the
113
			// early exit from checking visited above will short circuit the
114
			// cycle check below.
115 2
			visited[k] = struct{}{}
116

117
			// If it exists, the first element of path is the new addition to the
118
			// graph, therefore it must be in any cycle that exists, assuming
119
			// verifyAcyclic has been run for every previous Provide.
120
			//
121
			// Alternatively, if deferAcyclicVerification was set and detectCycles
122
			// is only being called before the first Invoke, each node in the
123
			// graph will be tested as the first element of the path, so any
124
			// cycle that exists is guaranteed to trip the following condition.
125 2
			if path[0].Key == k {
126 2
				err = errCycleDetected{Path: append(path, entry)}
127 2
				return false
128
			}
129
		}
130

131
		for _, n := range providers {
132 2
			if e := detectCycles(n, c, append(path, entry), visited); e != nil {
133 2
				err = e
134 2
				return false
135
			}
136
		}
137

138 2
		return true
139
	}))
140

141 2
	return err
142
}

Read our documentation on viewing source code .

Loading