1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
// Copyright 2015 Matthew Holt and The Caddy Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package caddyfile
import (
"fmt"
)
type adjacency map[string][]string
type importGraph struct {
nodes map[string]bool
edges adjacency
}
func (i *importGraph) addNode(name string) {
if i.nodes == nil {
i.nodes = make(map[string]bool)
}
if _, exists := i.nodes[name]; exists {
return
}
i.nodes[name] = true
}
func (i *importGraph) addNodes(names []string) {
for _, name := range names {
i.addNode(name)
}
}
func (i *importGraph) removeNode(name string) {
delete(i.nodes, name)
}
func (i *importGraph) removeNodes(names []string) {
for _, name := range names {
i.removeNode(name)
}
}
func (i *importGraph) addEdge(from, to string) error {
if !i.exists(from) || !i.exists(to) {
return fmt.Errorf("one of the nodes does not exist")
}
if i.willCycle(to, from) {
return fmt.Errorf("a cycle of imports exists between %s and %s", from, to)
}
if i.areConnected(from, to) {
// if connected, there's nothing to do
return nil
}
if i.nodes == nil {
i.nodes = make(map[string]bool)
}
if i.edges == nil {
i.edges = make(adjacency)
}
i.edges[from] = append(i.edges[from], to)
return nil
}
func (i *importGraph) addEdges(from string, tos []string) error {
for _, to := range tos {
err := i.addEdge(from, to)
if err != nil {
return err
}
}
return nil
}
func (i *importGraph) areConnected(from, to string) bool {
al, ok := i.edges[from]
if !ok {
return false
}
for _, v := range al {
if v == to {
return true
}
}
return false
}
func (i *importGraph) willCycle(from, to string) bool {
collector := make(map[string]bool)
var visit func(string)
visit = func(start string) {
if !collector[start] {
collector[start] = true
for _, v := range i.edges[start] {
visit(v)
}
}
}
for _, v := range i.edges[from] {
visit(v)
}
for k := range collector {
if to == k {
return true
}
}
return false
}
func (i *importGraph) exists(key string) bool {
_, exists := i.nodes[key]
return exists
}
|
