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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
// Copyright 2014 The Bazel Authors. All rights reserved.
//
// 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 com.google.devtools.build.skyframe;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Function;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicates;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
* Data for a single cycle in the graph, together with the path to the cycle. For any value, the
* head of path to the cycle should be the value itself, or, if the value is actually in the cycle,
* the cycle should start with the value.
*/
public class CycleInfo {
private final ImmutableList<SkyKey> cycle;
private final ImmutableList<SkyKey> pathToCycle;
@VisibleForTesting
public CycleInfo(Iterable<SkyKey> cycle) {
this(ImmutableList.<SkyKey>of(), cycle);
}
public CycleInfo(Iterable<SkyKey> pathToCycle, Iterable<SkyKey> cycle) {
this.pathToCycle = ImmutableList.copyOf(pathToCycle);
this.cycle = ImmutableList.copyOf(cycle);
}
// If a cycle is already known, but we are processing a value in the middle of the cycle, we need
// to shift the cycle so that the value is at the head.
private CycleInfo(Iterable<SkyKey> cycle, int cycleStart) {
Preconditions.checkState(cycleStart >= 0, cycleStart);
ImmutableList.Builder<SkyKey> cycleTail = ImmutableList.builder();
ImmutableList.Builder<SkyKey> cycleHead = ImmutableList.builder();
int index = 0;
for (SkyKey key : cycle) {
if (index >= cycleStart) {
cycleHead.add(key);
} else {
cycleTail.add(key);
}
index++;
}
Preconditions.checkState(cycleStart < index, "%s >= %s ??", cycleStart, index);
this.cycle = cycleHead.addAll(cycleTail.build()).build();
this.pathToCycle = ImmutableList.of();
}
public ImmutableList<SkyKey> getCycle() {
return cycle;
}
public ImmutableList<SkyKey> getPathToCycle() {
return pathToCycle;
}
// Given a cycle and a value, if the value is part of the cycle, shift the cycle. Otherwise,
// prepend the value to the head of pathToCycle.
private static CycleInfo normalizeCycle(final SkyKey value, CycleInfo cycle) {
int index = cycle.cycle.indexOf(value);
if (index > -1) {
if (!cycle.pathToCycle.isEmpty()) {
// The head value we are considering is already part of a cycle, but we have reached it by a
// roundabout way. Since we should have reached it directly as well, filter this roundabout
// way out. Example (c has a dependence on top):
// top
// / ^
// a |
// / \ /
// b-> c
// In the traversal, we start at top, visit a, then c, then top. This yields the
// cycle {top,a,c}. Then we visit b, getting (b, {top,a,c}). Then we construct the full
// error for a. The error should just be the cycle {top,a,c}, but we have an extra copy of
// it via the path through b.
return null;
}
return new CycleInfo(cycle.cycle, index);
}
return new CycleInfo(Iterables.concat(ImmutableList.of(value), cycle.pathToCycle),
cycle.cycle);
}
/**
* Normalize multiple cycles. This includes removing multiple paths to the same cycle, so that
* a value does not depend on the same cycle multiple ways through the same child value. Note that
* a value can still depend on the same cycle multiple ways, it's just that each way must be
* through a different child value (a path with a different first element).
*/
static Iterable<CycleInfo> prepareCycles(final SkyKey value, Iterable<CycleInfo> cycles) {
final Set<ImmutableList<SkyKey>> alreadyDoneCycles = new HashSet<>();
return Iterables.filter(Iterables.transform(cycles,
new Function<CycleInfo, CycleInfo>() {
@Override
public CycleInfo apply(CycleInfo input) {
CycleInfo normalized = normalizeCycle(value, input);
if (normalized != null && alreadyDoneCycles.add(normalized.cycle)) {
return normalized;
}
return null;
}
}), Predicates.notNull());
}
@Override
public int hashCode() {
return Objects.hash(cycle, pathToCycle);
}
@Override
public boolean equals(Object that) {
if (this == that) {
return true;
}
if (!(that instanceof CycleInfo)) {
return false;
}
CycleInfo thatCycle = (CycleInfo) that;
return thatCycle.cycle.equals(this.cycle) && thatCycle.pathToCycle.equals(this.pathToCycle);
}
@Override
public String toString() {
return Iterables.toString(pathToCycle) + " -> " + Iterables.toString(cycle);
}
}
|
