mvdan.cc
1// Copyright 2020 CUE Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package flow
16
17import (
18 "fmt"
19 "slices"
20 "strings"
21
22 "cuelang.org/go/cue"
23 "cuelang.org/go/cue/errors"
24 "cuelang.org/go/cue/token"
25)
26
27// checkCycle checks for cyclic dependencies between tasks.
28func checkCycle(a []*Task) errors.Error {
29 cc := cycleChecker{
30 visited: make([]bool, len(a)),
31 stack: make([]*Task, 0, len(a)),
32 }
33 if slices.ContainsFunc(a, cc.isCyclic) {
34
35 }
36 return cc.err
37}
38
39type cycleChecker struct {
40 visited []bool
41 stack []*Task
42 err errors.Error
43}
44
45func (cc *cycleChecker) isCyclic(t *Task) bool {
46 i := t.index
47 if !cc.visited[i] {
48 cc.visited[i] = true
49 cc.stack = append(cc.stack, t)
50
51 for _, d := range t.depTasks {
52 if !cc.visited[d.index] && cc.isCyclic(d) {
53 return true
54 } else if cc.visited[d.index] {
55 cc.addCycleError(t)
56 return true
57 }
58 }
59 }
60 cc.stack = cc.stack[:len(cc.stack)-1]
61 cc.visited[i] = false
62 return false
63}
64
65func (cc *cycleChecker) addCycleError(start *Task) {
66 err := &cycleError{}
67
68 for _, t := range cc.stack {
69 err.path = append(err.path, t.v.Path())
70 err.positions = append(err.positions, t.v.Pos())
71 }
72
73 cc.err = errors.Append(cc.err, err)
74}
75
76type cycleError struct {
77 path []cue.Path
78 positions []token.Pos
79}
80
81func (e *cycleError) Error() string {
82 msg, args := e.Msg()
83 return fmt.Sprintf(msg, args...)
84}
85
86func (e *cycleError) Path() []string { return nil }
87
88func (e *cycleError) Msg() (format string, args []interface{}) {
89 w := &strings.Builder{}
90 for _, p := range e.path {
91 fmt.Fprintf(w, "\n\ttask %s refers to", p)
92 }
93 fmt.Fprintf(w, "\n\ttask %s", e.path[0])
94
95 return "cyclic task dependency:%v", []interface{}{w.String()}
96}
97
98func (e *cycleError) Position() token.Pos {
99 if len(e.positions) == 0 {
100 return token.NoPos
101 }
102 return e.positions[0]
103}
104
105func (e *cycleError) InputPositions() []token.Pos {
106 return e.positions
107}