Mercurial > projects > dil

annotate trunk/src/docgen/graphutils/writer.d @ 446:49f3afd6a0e8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Refactored writers.
author Jari-Matti M?kel? <jmjm@iki.fi>
date Wed, 17 Oct 2007 18:41:46 +0300
parents ac9cd48151b6
children c82b36b9cadf
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
1 /**
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
2 * Author: Jari-Matti Mäkelä
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
3 * License: GPL3
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
4 */
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
5 module docgen.graphutils.writer;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
6
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
7 public import docgen.misc.misc;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
8 public import docgen.graphutils.primitives;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
9 import tango.io.model.IConduit : OutputStream;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
10 debug import tango.io.Stdout;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
11
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
12 interface GraphWriter {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
13 void generateGraph(Vertex[], Edge[]);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
14 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
15
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
16 alias void delegate(Vertex[], Edge[]) GraphWriterDg;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
17
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
18 abstract class AbstractGraphWriter : GraphWriter {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
19 protected GraphWriterFactory factory;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
20 protected OutputStream[] outputs;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
21
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
22 this(GraphWriterFactory factory, OutputStream[] outputs) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
23 this.factory = factory;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
24 this.outputs = outputs;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
25 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
26
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
27 /**
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
28 * Marks all cycles in the graph.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
29 *
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
30 * May have bugs, but is a bit simpler than the previous version.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
31 */
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
32 protected static void findCycles(Vertex[] vertices, Edge[] edges) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
33 debug void p() {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
34 foreach(e; edges) Stderr(e.type)(" "c);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
35 Stderr.newline;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
36 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
37
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
38 bool visit(Edge edge) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
39 if (edge.type == EdgeType.Reserved) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
40 edge.type = EdgeType.CyclicDependency;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
41 debug p();
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
42 return true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
43 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
44
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
45 bool wasCyclic = edge.isCyclic();
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
46 edge.type = EdgeType.Reserved;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
47 debug p();
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
48
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
49 foreach(edge2; edge.incoming.outgoingEdges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
50 if (visit(edge2)) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
51 if (edge.isCyclic()) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
52 edge.type = EdgeType.Reserved;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
53 wasCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
54 debug p();
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
55 continue;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
56 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
57 edge.type = EdgeType.CyclicDependency;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
58 return true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
59 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
60
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
61 edge.type = wasCyclic ? EdgeType.CyclicDependency : EdgeType.Dependency;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
62 debug p();
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
63 return false;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
64 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
65
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
66 foreach(vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
67 foreach(edge; vertex.outgoingEdges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
68 if (edge.type == EdgeType.Unspecified) {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
69 visit(edge);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
70 debug Stderr("*\n");
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
71 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
72 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
73
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
74 /+
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
75 void analyzeGraph(Vertex[] vertices, Edge[] edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
76 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
77 void recursive(Vertex[] modules)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
78 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
79 foreach (idx, vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
80 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
81 uint outgoing, incoming;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
82 foreach (j, edge; edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
83 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
84 if (edge.outgoing is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
85 outgoing++;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
86 if (edge.incoming is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
87 incoming++;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
88 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
89
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
90 if (outgoing == 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
91 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
92 if (incoming != 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
93 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
94 // Vertex is a sink.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
95 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
96 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
97 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
98 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
99 if (edges[i].incoming !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
100 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
101 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
102 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
103 return recursive(modules);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
104 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
105 else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
106 assert(0, "orphaned module: "~vertex.getFQN()~" (has no edges in graph)"); // orphaned vertex (module) in graph
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
107 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
108 else if (incoming == 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
109 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
110 // Vertex is a source
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
111 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
112 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
113 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
114 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
115 if (edges[i].outgoing !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
116 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
117 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
118 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
119 return recursive(modules);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
120 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
121 // else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
122 // {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
123 // // source && sink
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
124 // }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
125 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
126
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
127 // When reaching this point it means only cylic edges and vertices are left.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
128 foreach (vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
129 vertex.isCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
130 foreach (edge; edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
131 if (edge)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
132 edge.isCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
133 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
134 recursive(vertices);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
135 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
136 +/
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
137 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
138
446
49f3afd6a0e8 Refactored writers.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 395
diff changeset
139 interface GraphWriterFactory : WriterFactory {
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
140 GraphWriterDg createGraphWriter(OutputStream[] outputs);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
141 }