Mercurial > projects > dil

annotate trunk/src/docgen/graphutils/writer.d @ 451:3f44c38bf870

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Page templates, more flexible writer interfaces, small fixes.
author Jari-Matti M?kel? <jmjm@iki.fi>
date Wed, 24 Oct 2007 17:25:52 +0300
parents c82b36b9cadf
children dbdc9fa5d479
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;
451
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
9 public import docgen.document.writer;
395
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 {
451
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
13 void generateGraph(Vertex[] vertices, Edge[] edges, OutputStream imageFile);
395
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
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
16 /**
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
17 * Marks all cycles in the graph.
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
18 *
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
19 * May have bugs, but is a bit simpler than the previous version.
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
20 */
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
21 void findCycles(Vertex[] vertices, Edge[] edges) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
22 debug void p() {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
23 foreach(e; edges) Stderr(e.type)(" "c);
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
24 Stderr.newline;
395
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
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
27 bool visit(Edge edge) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
28 if (edge.type == EdgeType.Reserved) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
29 edge.type = EdgeType.CyclicDependency;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
30 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
31 return true;
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
32 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
33
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
34 bool wasCyclic = edge.isCyclic();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
35 edge.type = EdgeType.Reserved;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
36 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
37
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
38 foreach(edge2; edge.incoming.outgoingEdges)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
39 if (visit(edge2)) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
40 if (edge.isCyclic()) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
41 edge.type = EdgeType.Reserved;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
42 wasCyclic = true;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
43 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
44 continue;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
45 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
46 edge.type = EdgeType.CyclicDependency;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
47 return true;
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
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
50 edge.type = wasCyclic ? EdgeType.CyclicDependency : EdgeType.Dependency;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
51 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
52 return false;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
53 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
54
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
55 foreach(vertex; vertices)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
56 foreach(edge; vertex.outgoingEdges)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
57 if (edge.type == EdgeType.Unspecified) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
58 visit(edge);
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
59 debug Stderr("*\n");
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
60 }
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
61 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
62
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
63 /+
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
64 void analyzeGraph(Vertex[] vertices, Edge[] edges)
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 void recursive(Vertex[] modules)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
67 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
68 foreach (idx, vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
69 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
70 uint outgoing, incoming;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
71 foreach (j, edge; edges)
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 if (edge.outgoing is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
74 outgoing++;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
75 if (edge.incoming is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
76 incoming++;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
77 }
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 if (outgoing == 0)
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 if (incoming != 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
82 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
83 // Vertex is a sink.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
84 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
85 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
86 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
87 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
88 if (edges[i].incoming !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
89 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
90 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
91 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
92 return recursive(modules);
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 else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
95 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
96 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
97 else if (incoming == 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
98 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
99 // Vertex is a source
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
100 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
101 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
102 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
103 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
104 if (edges[i].outgoing !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
105 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
106 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
107 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
108 return recursive(modules);
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 // else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
111 // {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
112 // // source && sink
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
113 // }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
114 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
115
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
116 // 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
117 foreach (vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
118 vertex.isCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
119 foreach (edge; edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
120 if (edge)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
121 edge.isCyclic = true;
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 recursive(vertices);
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
446
49f3afd6a0e8 Refactored writers.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 395
diff changeset
127 interface GraphWriterFactory : WriterFactory {
451
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
128 GraphWriter createGraphWriter(DocumentWriter writer);
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
129 }
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
130
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
131 abstract class AbstractGraphWriter : AbstractWriter!(GraphWriterFactory), GraphWriter {
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
132 DocumentWriter writer;
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
133
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
134 this(GraphWriterFactory factory, DocumentWriter writer) {
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
135 super(factory);
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
136 this.writer = writer;
3f44c38bf870 Page templates, more flexible writer interfaces, small fixes.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 448
diff changeset
137 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
138 }