package hudson.model;
import org.kohsuke.stapler.StaplerRequest;
import org.kohsuke.stapler.StaplerResponse;
import org.kohsuke.graph_layouter.Layout;
import org.kohsuke.graph_layouter.Navigator;
import org.kohsuke.graph_layouter.Direction;
import javax.servlet.ServletOutputStream;
import javax.imageio.ImageIO;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;
import java.util.Stack;
import java.util.Map.Entry;
import java.io.IOException;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Rectangle;
import java.awt.Graphics2D;
import java.awt.Color;
import java.awt.Point;
import java.awt.HeadlessException;
import java.awt.FontMetrics;
import java.awt.geom.AffineTransform;
import java.awt.image.BufferedImage;
/**
* Maintains the build dependencies between {@link AbstractProject}s
* for efficient dependency computation.
*
*
* The "master" data of dependencies are owned/persisted/maintained by
* individual {@link AbstractProject}s, but because of that, it's relatively
* slow to compute backward edges.
*
*
* This class builds the complete bi-directional dependency graph
* by collecting information from all {@link AbstractProject}s.
*
*
* Once built, {@link DependencyGraph} is immutable, and every time
* there's a change (which is relatively rare), a new instance
* will be created. This eliminates the need of synchronization.
*
* @author Kohsuke Kawaguchi
*/
public final class DependencyGraph {
private Map> forward = new HashMap>();
private Map> backward = new HashMap>();
private boolean built;
/**
* Builds the dependency graph.
*/
public DependencyGraph() {
for( AbstractProject p : Hudson.getInstance().getAllItems(AbstractProject.class) )
p.buildDependencyGraph(this);
forward = finalize(forward);
backward = finalize(backward);
built = true;
}
/**
* Special constructor for creating an empty graph
*/
private DependencyGraph(boolean dummy) {
forward = backward = Collections.emptyMap();
built = true;
}
/**
* Gets all the immediate downstream projects (IOW forward edges) of the given project.
*
* @return
* can be empty but never null.
*/
public List getDownstream(AbstractProject p) {
return get(forward,p);
}
/**
* Gets all the immediate upstream projects (IOW backward edges) of the given project.
*
* @return
* can be empty but never null.
*/
public List getUpstream(AbstractProject p) {
return get(backward,p);
}
private List get(Map> map, AbstractProject src) {
List v = map.get(src);
if(v!=null) return v;
else return Collections.emptyList();
}
/**
* Called during the dependency graph build phase to add a dependency edge.
*/
public void addDependency(AbstractProject from, AbstractProject to) {
if(built)
throw new IllegalStateException();
add(forward,from,to);
add(backward,to,from);
}
public void addDependency(AbstractProject from, Collection extends AbstractProject> to) {
for (AbstractProject p : to)
addDependency(from,p);
}
public void addDependency(Collection extends AbstractProject> from, AbstractProject to) {
for (AbstractProject p : from)
addDependency(p,to);
}
/**
* Returns true if a project has a non-direct dependency to another project.
*
* A non-direct dependency is a path of dependency "edge"s from the source to the destination,
* where the length is greater than 1.
*/
public boolean hasIndirectDependencies(AbstractProject src, AbstractProject dst) {
Set visited = new HashSet();
Stack queue = new Stack();
queue.addAll(getDownstream(src));
queue.remove(dst);
while(!queue.isEmpty()) {
AbstractProject p = queue.pop();
if(p==dst)
return true;
if(visited.add(p))
queue.addAll(getDownstream(p));
}
return false;
}
/**
* Gets all the direct and indirect upstream dependencies of the given project.
*/
public Set getTransitiveUpstream(AbstractProject src) {
return getTransitive(backward,src);
}
/**
* Gets all the direct and indirect downstream dependencies of the given project.
*/
public Set getTransitiveDownstream(AbstractProject src) {
return getTransitive(forward,src);
}
private Set getTransitive(Map> direction, AbstractProject src) {
Set visited = new HashSet();
Stack queue = new Stack();
queue.add(src);
while(!queue.isEmpty()) {
AbstractProject p = queue.pop();
for (AbstractProject child : get(direction,p)) {
if(visited.add(child))
queue.add(child);
}
}
return visited;
}
private void add(Map> map, AbstractProject src, AbstractProject dst) {
List set = map.get(src);
if(set==null) {
set = new ArrayList();
map.put(src,set);
}
set.add(dst);
}
private Map> finalize(Map> m) {
for (Entry> e : m.entrySet()) {
Collections.sort( e.getValue(), NAME_COMPARATOR );
e.setValue( Collections.unmodifiableList(e.getValue()) );
}
return Collections.unmodifiableMap(m);
}
/**
* Experimental visualization of project dependencies.
*/
public void doGraph( StaplerRequest req, StaplerResponse rsp ) throws IOException {
try {
// creates a dummy graphics just so that we can measure font metrics
BufferedImage emptyImage = new BufferedImage(1,1, BufferedImage.TYPE_INT_RGB );
Graphics2D graphics = emptyImage.createGraphics();
graphics.setFont(FONT);
final FontMetrics fontMetrics = graphics.getFontMetrics();
// TODO: timestamp check
Layout layout = new Layout(new Navigator() {
public Collection vertices() {
// only include projects that have some dependency
List r = new ArrayList();
for (AbstractProject p : Hudson.getInstance().getAllItems(AbstractProject.class)) {
if(!getDownstream(p).isEmpty() || !getUpstream(p).isEmpty())
r.add(p);
}
return r;
}
public Collection edge(AbstractProject p) {
return getDownstream(p);
}
public Dimension getSize(AbstractProject p) {
int w = fontMetrics.stringWidth(p.getDisplayName()) + MARGIN*2;
return new Dimension(w, fontMetrics.getHeight() + MARGIN*2);
}
}, Direction.LEFTRIGHT);
Rectangle area = layout.calcDrawingArea();
area.grow(4,4); // give it a bit of margin
BufferedImage image = new BufferedImage(area.width, area.height, BufferedImage.TYPE_INT_RGB );
Graphics2D g2 = image.createGraphics();
g2.setTransform(AffineTransform.getTranslateInstance(-area.x,-area.y));
g2.setPaint(Color.WHITE);
g2.fill(area);
g2.setFont(FONT);
g2.setPaint(Color.BLACK);
for( AbstractProject p : layout.vertices() ) {
final Point sp = center(layout.vertex(p));
for (AbstractProject q : layout.edges(p)) {
Point cur=sp;
for( Point pt : layout.edge(p,q) ) {
g2.drawLine(cur.x, cur.y, pt.x, pt.y);
cur=pt;
}
final Point ep = center(layout.vertex(q));
g2.drawLine(cur.x, cur.y, ep.x, ep.y);
}
}
int diff = fontMetrics.getAscent()+fontMetrics.getLeading()/2;
for( AbstractProject p : layout.vertices() ) {
Rectangle r = layout.vertex(p);
g2.setPaint(Color.WHITE);
g2.fillRect(r.x, r.y, r.width, r.height);
g2.setPaint(Color.BLACK);
g2.drawRect(r.x, r.y, r.width, r.height);
g2.drawString(p.getDisplayName(), r.x+MARGIN, r.y+MARGIN+ diff);
}
rsp.setContentType("image/png");
ServletOutputStream os = rsp.getOutputStream();
ImageIO.write(image, "PNG", os);
os.close();
} catch(HeadlessException e) {
// not available. send out error message
rsp.sendRedirect2(req.getContextPath()+"/images/headless.png");
}
}
private Point center(Rectangle r) {
return new Point(r.x+r.width/2,r.y+r.height/2);
}
private static final Font FONT = new Font("TimesRoman", Font.PLAIN, 10);
/**
* Margins between the project name and its bounding box.
*/
private static final int MARGIN = 4;
private static final Comparator NAME_COMPARATOR = new Comparator() {
public int compare(AbstractProject lhs, AbstractProject rhs) {
return lhs.getName().compareTo(rhs.getName());
}
};
public static final DependencyGraph EMPTY = new DependencyGraph(false);
}