-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathGirDependencyGraph.java
More file actions
194 lines (160 loc) · 5.9 KB
/
GirDependencyGraph.java
File metadata and controls
194 lines (160 loc) · 5.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
package gir2java;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import nu.xom.Document;
/**
* Takes .gir Documents, and performs dependency-related operations on them.
* @author relek
*
*/
public class GirDependencyGraph {
protected Map<NamespaceDescriptor, Document> namespaceToGir;
protected Map<Document, NamespaceDescriptor> girToNamespace;
protected Map<Document, List<NamespaceDescriptor>> girToIncludedNamespaces = new HashMap<Document, List<NamespaceDescriptor>>();
private GirParser parser;
private class WithRemovableIncludes extends GirDependencyGraph {
public WithRemovableIncludes(GirDependencyGraph graph) {
super(graph.parser);
//Deep copy the include map so we can work on it independently of the original
for (Document doc : graph.girToIncludedNamespaces.keySet()) {
List<NamespaceDescriptor> includesList = new ArrayList<NamespaceDescriptor>();
includesList.addAll(graph.girToIncludedNamespaces.get(doc));
girToIncludedNamespaces.put(doc, includesList);
}
//Shallow copy everything else, we don't want to alter them
namespaceToGir = graph.namespaceToGir;
girToNamespace = graph.girToNamespace;
}
private void removeInclude(Document gir, NamespaceDescriptor include) {
girToIncludedNamespaces.get(gir).remove(include);
}
}
public GirDependencyGraph(GirParser parser) {
this.parser = parser;
namespaceToGir = new HashMap<NamespaceDescriptor, Document>();
girToNamespace = new HashMap<Document, NamespaceDescriptor>();
}
public void addGir(Document gir) {
NamespaceDescriptor definedNamespace = parser.getDefinedNamespace(gir);
List<NamespaceDescriptor> includedNamespaces = parser.getIncludedNamespaces(gir);
namespaceToGir.put(definedNamespace, gir);
girToNamespace.put(gir, definedNamespace);
girToIncludedNamespaces.put(gir, includedNamespaces);
}
public Set<Document> getIncluders(Document doc) {
Set<Document> ret = new HashSet<Document>();
NamespaceDescriptor docNs = girToNamespace.get(doc);
for (Document candidate : girToIncludedNamespaces.keySet()) {
List<NamespaceDescriptor> includes = girToIncludedNamespaces.get(candidate);
if (includes.contains(docNs)) {
ret.add(candidate);
}
}
return ret;
}
public Set<Document> getIncludees(Document doc) {
Set<Document> ret = new HashSet<Document>();
List<NamespaceDescriptor> includesList = girToIncludedNamespaces.get(doc);
if (includesList == null) {
return ret;
}
for (NamespaceDescriptor ns : includesList) {
ret.add(namespaceToGir.get(ns));
}
return ret;
}
public boolean hasIncludes() {
for (Document doc : girToIncludedNamespaces.keySet()) {
List<NamespaceDescriptor> includesList = girToIncludedNamespaces.get(doc);
if ( (includesList != null) && (!includesList.isEmpty()) ) {
return true;
}
}
return false;
}
/**
* Get a list of the .gir Documents tracked by this instance in topologically sorted order.
* The basis of the sorting is the include dependency graph. In other words, if Document A
* includes the namespace defined in Document B, then Document B will precede Document A in
* the returned list.
* @return
*/
public List<Document> getGirsTopoSorted() {
List<Document> ret = new ArrayList<Document>();
Set<Document> startingNodes = new HashSet<Document>(girToNamespace.keySet());
//find all the documents that are not included from anywhere
//Note: this might make this solution less efficient than reversing all edges, then toposorting
Set<Document> includedDocs = new HashSet<Document>();
for (Document doc : girToIncludedNamespaces.keySet()) {
for (NamespaceDescriptor include : girToIncludedNamespaces.get(doc)) {
includedDocs.add(namespaceToGir.get(include));
}
}
startingNodes.removeAll(includedDocs);
GirDependencyGraph.WithRemovableIncludes workingCopy = new GirDependencyGraph.WithRemovableIncludes(this);
while (!startingNodes.isEmpty()) {
Document nextDoc = startingNodes.iterator().next();
startingNodes.remove(nextDoc);
ret.add(nextDoc);
for(Document includee : workingCopy.getIncludees(nextDoc)) {
workingCopy.removeInclude(nextDoc, girToNamespace.get(includee));
if (workingCopy.getIncluders(includee).isEmpty()) {
startingNodes.add(includee);
}
}
}
if (workingCopy.hasIncludes()) {
throw new IllegalArgumentException("The include graph seems to contain one or more cycles. This is bad. Working copy: " + workingCopy);
}
//reverse the list
for (int i = 0; i < (ret.size() / 2); i++) {
Document tmp = ret.get(i);
ret.set(i, ret.get(ret.size() - 1 - i));
ret.set(ret.size() - 1 - i, tmp);
}
return ret;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("Dependency graph summary:\n");
Set<NamespaceDescriptor> referredNamespaces = new HashSet<NamespaceDescriptor>();
sb.append("Namespace dependencies:\n");
for (Document doc : girToIncludedNamespaces.keySet()) {
sb.append(girToNamespace.get(doc));
sb.append('\n');
List<NamespaceDescriptor> dependencies = girToIncludedNamespaces.get(doc);
if (dependencies == null) {
continue;
}
for (NamespaceDescriptor ns : dependencies) {
referredNamespaces.add(ns);
sb.append(" - ");
sb.append(ns);
sb.append('\n');
}
}
sb.append("\nNamespace to document bindings:\n");
for (NamespaceDescriptor ns : namespaceToGir.keySet()) {
sb.append(ns);
sb.append(" -> ");
sb.append(namespaceToGir.get(ns).getBaseURI());
sb.append('\n');
}
referredNamespaces.removeAll(namespaceToGir.keySet());
sb.append('\n');
if (referredNamespaces.isEmpty()) {
sb.append("No unbound namespaces");
} else {
sb.append("Unbound namespaces:\n");
for (NamespaceDescriptor ns : referredNamespaces) {
sb.append(ns);
sb.append('\n');
}
}
return sb.toString();
}
}