File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\model\DependencyGraph.java.html

1 /*
2 * The MIT License
3 *
4 * Copyright (c) 2004-2010, Sun Microsystems, Inc., Kohsuke Kawaguchi,
5 * Martin Eigenbrodt. Seiji Sogabe, Alan Harder
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 * THE SOFTWARE.
24 */
25 package hudson.model;
26
27 import jenkins.model.DependencyDeclarer;
28 import com.google.common.collect.ImmutableList;
29 import hudson.security.ACL;
30 import jenkins.model.Jenkins;
31 import org.acegisecurity.context.SecurityContext;
32 import org.acegisecurity.context.SecurityContextHolder;
33
34 import java.util.ArrayList;
35 import java.util.Collection;
36 import java.util.Collections;
37 import java.util.Comparator;
38 import java.util.HashMap;
39 import java.util.HashSet;
40 import java.util.LinkedHashSet;
41 import java.util.List;
42 import java.util.ListIterator;
43 import java.util.Map;
44 import java.util.Map.Entry;
45 import java.util.Set;
46 import java.util.Stack;
47
48 /**
49 * Maintains the build dependencies between {@link AbstractProject}s
50 * for efficient dependency computation.
51 *
52 * <p>
53 * The "master" data of dependencies are owned/persisted/maintained by
54 * individual {@link AbstractProject}s, but because of that, it's relatively
55 * slow to compute backward edges.
56 *
57 * <p>
58 * This class builds the complete bi-directional dependency graph
59 * by collecting information from all {@link AbstractProject}s.
60 *
61 * <p>
62 * Once built, {@link DependencyGraph} is immutable, and every time
63 * there's a change (which is relatively rare), a new instance
64 * will be created. This eliminates the need of synchronization.
65 *
66 * @see Jenkins#getDependencyGraph()
67 * @author Kohsuke Kawaguchi
68 */
69 public class DependencyGraph implements Comparator<AbstractProject> {
70
71 private Map<AbstractProject, List<DependencyGroup>> forward = new HashMap<AbstractProject, List<DependencyGroup>>();
72 private Map<AbstractProject, List<DependencyGroup>> backward = new HashMap<AbstractProject, List<DependencyGroup>>();
73
74 private transient Map<Class<?>, Object> computationalData;
75
76 private boolean built;
77
78 /**
79 * Builds the dependency graph.
80 */
81 public DependencyGraph() {
82 }
83
84 public void build() {
85 // Set full privileges while computing to avoid missing any projects the current user cannot see.
86 // Use setContext (NOT getContext().setAuthentication()) so we don't affect concurrent threads for same HttpSession.
87 SecurityContext saveCtx = ACL.impersonate(ACL.SYSTEM);
88 try {
89 this.computationalData = new HashMap<Class<?>, Object>();
90 for( AbstractProject p : getAllProjects() )
91 p.buildDependencyGraph(this);
92
93 forward = finalize(forward);
94 backward = finalize(backward);
95
96 this.computationalData = null;
97 built = true;
98 } finally {
99 SecurityContextHolder.setContext(saveCtx);
100 }
101 }
102
103 Collection<AbstractProject> getAllProjects() {
104 return Jenkins.getInstance().getAllItems(AbstractProject.class);
105 }
106
107 /**
108 * Special constructor for creating an empty graph
109 */
110 private DependencyGraph(boolean dummy) {
111 forward = backward = Collections.emptyMap();
112 built = true;
113 }
114
115 /**
116 * Adds data which is useful for the time when the dependency graph is built up.
117 * All this data will be cleaned once the dependency graph creation has finished.
118 */
119 public <T> void putComputationalData(Class<T> key, T value) {
120 this.computationalData.put(key, value);
121 }
122
123 /**
124 * Gets temporary data which is needed for building up the dependency graph.
125 */
126 public <T> T getComputationalData(Class<T> key) {
127 @SuppressWarnings("unchecked")
128 T result = (T) this.computationalData.get(key);
129 return result;
130 }
131
132 /**
133 * Gets all the immediate downstream projects (IOW forward edges) of the given project.
134 *
135 * @return
136 * can be empty but never null.
137 */
138 public List<AbstractProject> getDownstream(AbstractProject p) {
139 return get(forward,p,false);
140 }
141
142 /**
143 * Gets all the immediate upstream projects (IOW backward edges) of the given project.
144 *
145 * @return
146 * can be empty but never null.
147 */
148 public List<AbstractProject> getUpstream(AbstractProject p) {
149 return get(backward,p,true);
150 }
151
152 private List<AbstractProject> get(Map<AbstractProject, List<DependencyGroup>> map, AbstractProject src, boolean up) {
153 List<DependencyGroup> v = map.get(src);
154 if(v==null) return Collections.emptyList();
155 List<AbstractProject> result = new ArrayList<AbstractProject>(v.size());
156 for (DependencyGroup d : v) result.add(up ? d.getUpstreamProject() : d.getDownstreamProject());
157 return result;
158 }
159
160 /**
161 * @since 1.341
162 */
163 public List<Dependency> getDownstreamDependencies(AbstractProject p) {
164 return get(forward,p);
165 }
166
167 /**
168 * @since 1.341
169 */
170 public List<Dependency> getUpstreamDependencies(AbstractProject p) {
171 return get(backward,p);
172 }
173
174 private List<Dependency> get(Map<AbstractProject, List<DependencyGroup>> map, AbstractProject src) {
175 List<DependencyGroup> v = map.get(src);
176 if(v==null) {
177 return ImmutableList.of();
178 } else {
179 ImmutableList.Builder<Dependency> builder = ImmutableList.builder();
180 for (DependencyGroup dependencyGroup : v) {
181 builder.addAll(dependencyGroup.getGroup());
182 }
183 return builder.build();
184 }
185
186 }
187
188 /**
189 * @deprecated since 1.341; use {@link #addDependency(Dependency)}
190 */
191 @Deprecated
192 public void addDependency(AbstractProject upstream, AbstractProject downstream) {
193 addDependency(new Dependency(upstream,downstream));
194 }
195
196 /**
197 * Called during the dependency graph build phase to add a dependency edge.
198 */
199 public void addDependency(Dependency dep) {
200 if(built)
201 throw new IllegalStateException();
202 add(forward,dep.getUpstreamProject(),dep);
203 add(backward,dep.getDownstreamProject(),dep);
204 }
205
206 /**
207 * @deprecated since 1.341
208 */
209 @Deprecated
210 public void addDependency(AbstractProject upstream, Collection<? extends AbstractProject> downstream) {
211 for (AbstractProject p : downstream)
212 addDependency(upstream,p);
213 }
214
215 /**
216 * @deprecated since 1.341
217 */
218 @Deprecated
219 public void addDependency(Collection<? extends AbstractProject> upstream, AbstractProject downstream) {
220 for (AbstractProject p : upstream)
221 addDependency(p,downstream);
222 }
223
224 /**
225 * Lists up {@link DependencyDeclarer} from the collection and let them builds dependencies.
226 */
227 public void addDependencyDeclarers(AbstractProject upstream, Collection<?> possibleDependecyDeclarers) {
228 for (Object o : possibleDependecyDeclarers) {
229 if (o instanceof DependencyDeclarer) {
230 DependencyDeclarer dd = (DependencyDeclarer) o;
231 dd.buildDependencyGraph(upstream,this);
232 }
233 }
234 }
235
236 /**
237 * Returns true if a project has a non-direct dependency to another project.
238 * <p>
239 * A non-direct dependency is a path of dependency "edge"s from the source to the destination,
240 * where the length is greater than 1.
241 */
242 public boolean hasIndirectDependencies(AbstractProject src, AbstractProject dst) {
243 Set<AbstractProject> visited = new HashSet<AbstractProject>();
244 Stack<AbstractProject> queue = new Stack<AbstractProject>();
245
246 queue.addAll(getDownstream(src));
247 queue.remove(dst);
248
249 while(!queue.isEmpty()) {
250 AbstractProject p = queue.pop();
251 if(p==dst)
252 return true;
253 if(visited.add(p))
254 queue.addAll(getDownstream(p));
255 }
256
257 return false;
258 }
259
260 /**
261 * Gets all the direct and indirect upstream dependencies of the given project.
262 */
263 public Set<AbstractProject> getTransitiveUpstream(AbstractProject src) {
264 return getTransitive(backward,src,true);
265 }
266
267 /**
268 * Gets all the direct and indirect downstream dependencies of the given project.
269 */
270 public Set<AbstractProject> getTransitiveDownstream(AbstractProject src) {
271 return getTransitive(forward,src,false);
272 }
273
274 private Set<AbstractProject> getTransitive(Map<AbstractProject, List<DependencyGroup>> direction, AbstractProject src, boolean up) {
275 Set<AbstractProject> visited = new HashSet<AbstractProject>();
276 Stack<AbstractProject> queue = new Stack<AbstractProject>();
277
278 queue.add(src);
279
280 while(!queue.isEmpty()) {
281 AbstractProject p = queue.pop();
282
283 for (AbstractProject child : get(direction,p,up)) {
284 if(visited.add(child))
285 queue.add(child);
286 }
287 }
288
289 return visited;
290 }
291
292 private void add(Map<AbstractProject, List<DependencyGroup>> map, AbstractProject key, Dependency dep) {
293 List<DependencyGroup> set = map.get(key);
294 if(set==null) {
295 set = new ArrayList<DependencyGroup>();
296 map.put(key,set);
297 }
298 for (ListIterator<DependencyGroup> it = set.listIterator(); it.hasNext();) {
299 DependencyGroup d = it.next();
300 // Check for existing edge that connects the same two projects:
301 if (d.getUpstreamProject()==dep.getUpstreamProject() && d.getDownstreamProject()==dep.getDownstreamProject()) {
302 d.add(dep);
303 return;
304 }
305 }
306 // Otherwise add to list:
307 set.add(new DependencyGroup(dep));
308 }
309
310 private Map<AbstractProject, List<DependencyGroup>> finalize(Map<AbstractProject, List<DependencyGroup>> m) {
311 for (Entry<AbstractProject, List<DependencyGroup>> e : m.entrySet()) {
312 Collections.sort( e.getValue(), NAME_COMPARATOR );
313 e.setValue( Collections.unmodifiableList(e.getValue()) );
314 }
315 return Collections.unmodifiableMap(m);
316 }
317
318 private static final Comparator<DependencyGroup> NAME_COMPARATOR = new Comparator<DependencyGroup>() {
319 public int compare(DependencyGroup lhs, DependencyGroup rhs) {
320 int cmp = lhs.getUpstreamProject().getName().compareTo(rhs.getUpstreamProject().getName());
321 return cmp != 0 ? cmp : lhs.getDownstreamProject().getName().compareTo(rhs.getDownstreamProject().getName());
322 }
323 };
324
325 public static final DependencyGraph EMPTY = new DependencyGraph(false);
326
327 /**
328 * Compare to Projects based on the topological order defined by this Dependency Graph
329 */
330 public int compare(AbstractProject o1, AbstractProject o2) {
331 Set<AbstractProject> o1sdownstreams = getTransitiveDownstream(o1);
332 Set<AbstractProject> o2sdownstreams = getTransitiveDownstream(o2);
333 if (o1sdownstreams.contains(o2)) {
334 if (o2sdownstreams.contains(o1)) return 0; else return 1;
335 } else {
336 if (o2sdownstreams.contains(o1)) return -1; else return 0;
337 }
338 }
339
340 /**
341 * Represents an edge in the dependency graph.
342 * @since 1.341
343 */
344 public static class Dependency {
345 private AbstractProject upstream, downstream;
346
347 public Dependency(AbstractProject upstream, AbstractProject downstream) {
348 this.upstream = upstream;
349 this.downstream = downstream;
350 }
351
352 public AbstractProject getUpstreamProject() {
353 return upstream;
354 }
355
356 public AbstractProject getDownstreamProject() {
357 return downstream;
358 }
359
360 /**
361 * Decide whether build should be triggered and provide any Actions for the build.
362 * Default implementation always returns true (for backward compatibility), and
363 * adds no Actions. Subclasses may override to control how/if the build is triggered.
364 * @param build Build of upstream project that just completed
365 * @param listener For any error/log output
366 * @param actions Add Actions for the triggered build to this list; never null
367 * @return True to trigger a build of the downstream project
368 */
369 public boolean shouldTriggerBuild(AbstractBuild build, TaskListener listener,
370 List<Action> actions) {
371 return true;
372 }
373
374 /**
375 * Does this method point to itself?
376 */
377 public boolean pointsItself() {
378 return upstream==downstream;
379 }
380
381 @Override
382 public boolean equals(Object obj) {
383 if (obj == null) return false;
384 if (getClass() != obj.getClass()) return false;
385
386 final Dependency that = (Dependency) obj;
387 return this.upstream == that.upstream || this.downstream == that.downstream;
388 }
389
390 @Override
391 public int hashCode() {
392 int hash = 7;
393 hash = 23 * hash + this.upstream.hashCode();
394 hash = 23 * hash + this.downstream.hashCode();
395 return hash;
396 }
397 }
398
399 /**
400 * Collect multiple dependencies between the same two projects.
401 */
402 private static class DependencyGroup {
403 private Set<Dependency> group = new LinkedHashSet<Dependency>();
404
405 DependencyGroup(Dependency first) {
406 this.upstream = first.getUpstreamProject();
407 this.downstream= first.getDownstreamProject();
408 group.add(first);
409 }
410
411 private void add(Dependency next) {
412 group.add(next);
413 }
414
415 public Set<Dependency> getGroup() {
416 return group;
417 }
418
419 private AbstractProject upstream, downstream;
420
421 public AbstractProject getUpstreamProject() {
422 return upstream;
423 }
424
425 public AbstractProject getDownstreamProject() {
426 return downstream;
427 }
428 }
429 }
430