Mercurial > projects > dil

annotate trunk/src/docgen/graphutils/writer.d @ 448:c82b36b9cadf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Simpler writer hierarchy.
author Jari-Matti M?kel? <jmjm@iki.fi>
date Wed, 17 Oct 2007 19:23:56 +0300
parents 49f3afd6a0e8
children 3f44c38bf870
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 debug import tango.io.Stdout;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
10
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
11 interface GraphWriter {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
12 void generateGraph(Vertex[], Edge[]);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
13 }
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 alias void delegate(Vertex[], Edge[]) GraphWriterDg;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
16
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
17 /**
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
18 * Marks all cycles in the graph.
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
19 *
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
20 * 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
21 */
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
22 void findCycles(Vertex[] vertices, Edge[] edges) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
23 debug void p() {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
24 foreach(e; edges) Stderr(e.type)(" "c);
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
25 Stderr.newline;
395
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
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
28 bool visit(Edge edge) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
29 if (edge.type == EdgeType.Reserved) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
30 edge.type = EdgeType.CyclicDependency;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
31 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
32 return true;
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
33 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
34
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
35 bool wasCyclic = edge.isCyclic();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
36 edge.type = EdgeType.Reserved;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
37 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
38
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
39 foreach(edge2; edge.incoming.outgoingEdges)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
40 if (visit(edge2)) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
41 if (edge.isCyclic()) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
42 edge.type = EdgeType.Reserved;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
43 wasCyclic = true;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
44 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
45 continue;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
46 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
47 edge.type = EdgeType.CyclicDependency;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
48 return true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
49 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
50
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
51 edge.type = wasCyclic ? EdgeType.CyclicDependency : EdgeType.Dependency;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
52 debug p();
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
53 return false;
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
54 }
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
55
448
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
56 foreach(vertex; vertices)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
57 foreach(edge; vertex.outgoingEdges)
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
58 if (edge.type == EdgeType.Unspecified) {
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
59 visit(edge);
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
60 debug Stderr("*\n");
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
61 }
c82b36b9cadf Simpler writer hierarchy.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 446
diff changeset
62 }
395
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 /+
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
65 void analyzeGraph(Vertex[] vertices, Edge[] edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
66 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
67 void recursive(Vertex[] modules)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
68 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
69 foreach (idx, vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
70 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
71 uint outgoing, incoming;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
72 foreach (j, edge; edges)
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 if (edge.outgoing is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
75 outgoing++;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
76 if (edge.incoming is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
77 incoming++;
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
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
80 if (outgoing == 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
81 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
82 if (incoming != 0)
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 // Vertex is a sink.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
85 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
86 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
87 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
88 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
89 if (edges[i].incoming !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
90 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
91 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
92 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
93 return recursive(modules);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
94 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
95 else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
96 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
97 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
98 else if (incoming == 0)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
99 {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
100 // Vertex is a source
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
101 alias outgoing i; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
102 alias incoming j; // Reuse
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
103 // Remove edges.
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
104 for (i=j=0; i < edges.length; i++)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
105 if (edges[i].outgoing !is vertex)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
106 edges[j++] = edges[i];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
107 edges.length = j;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
108 vertices = vertices[0..idx] ~ vertices[idx+1..$];
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
109 return recursive(modules);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
110 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
111 // else
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
112 // {
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
113 // // source && sink
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
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
117 // 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
118 foreach (vertex; vertices)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
119 vertex.isCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
120 foreach (edge; edges)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
121 if (edge)
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
122 edge.isCyclic = true;
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
123 }
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
124 recursive(vertices);
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
446
49f3afd6a0e8 Refactored writers.
Jari-Matti M?kel? <jmjm@iki.fi>
parents: 395
diff changeset
128 interface GraphWriterFactory : WriterFactory {
395
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
129 GraphWriterDg createGraphWriter(OutputStream[] outputs);
ac9cd48151b6 Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff changeset
130 }