Skip to content

Commit f2be243

Browse files
octachoronoctachoron
committed
Add a gir include dependency graph tracking class
This is required because we want to parse a gir file that defines a type before parsing those who use that type. This means the gir files to be parsed must be topologically sorted in reverse order based on the include dependency graph before parsing begins. The main role of the new GirDependencyGraph class is exactly this sorting.
1 parent 958d59e commit f2be243

1 file changed

Lines changed: 198 additions & 0 deletions

File tree

‎src/gir2java/GirDependencyGraph.java‎

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

0 commit comments

Comments
 (0)