← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/tool/import_graph.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/tool/import_graph.py
 
1
from __future__ import division
 
2
import autopath
 
3
import py
 
4
 
 
5
import math
 
6
import random
 
7
import sets
 
8
 
 
9
exclude_files = ["__init__.py", "autopath.py", "conftest.py"]
 
10
 
 
11
def include_file(path):
 
12
    if ("test" in str(path) or "tool" in str(path) or
 
13
        "documentation" in str(path) or "pyrex" in str(path) or
 
14
        "_cache" in str(path)):
 
15
        return False
 
16
    if path.basename in exclude_files:
 
17
        return False
 
18
    return True
 
19
 
 
20
def get_mod_from_path(path):
 
21
    dirs = path.get("dirname")[0].split("/")
 
22
    pypyindex = dirs.index("pypy")
 
23
    return ".".join(dirs[pypyindex:] + path.get("purebasename"))
 
24
 
 
25
 
 
26
def find_references(path):
 
27
    refs = []
 
28
    for line in path.open("r"):
 
29
        if line.startswith("    "): # ignore local imports to reduce graph size
 
30
            continue
 
31
        if "\\" in line: #ignore line continuations
 
32
            continue
 
33
        line = line.strip()
 
34
        line = line.split("#")[0].strip()
 
35
        if line.startswith("import pypy."): # import pypy.bla.whatever
 
36
            if " as " not in line:
 
37
                refs.append((line[7:].strip(), None))
 
38
            else: # import pypy.bla.whatever as somethingelse
 
39
                assert line.count(" as ") == 1
 
40
                line = line.split(" as ")
 
41
                refs.append((line[0][7:].strip(), line[1].strip()))
 
42
        elif line.startswith("from ") and "pypy" in line: #from pypy.b import a
 
43
            line = line[5:]
 
44
            if " as " not in line:
 
45
                line = line.split(" import ")
 
46
                what = line[1].split(",")
 
47
                for w in what:
 
48
                    refs.append((line[0].strip() + "." + w.strip(), None))
 
49
            else: # prom pypy.b import a as c
 
50
                if line.count(" as ") != 1 or "," in line:
 
51
                    print"can't handle this: " + line
 
52
                    continue
 
53
                line = line.split(" as ")
 
54
                what = line[0].replace(" import ", ".").replace(" ", "")
 
55
                refs.append((what, line[1].strip()))
 
56
    return refs
 
57
 
 
58
def get_module(ref, imports):
 
59
    ref = ref.split(".")
 
60
    i = len(ref)
 
61
    while i:
 
62
        possible_mod = ".".join(ref[:i])
 
63
        if possible_mod in imports:
 
64
            return possible_mod
 
65
        i -= 1
 
66
    return None
 
67
 
 
68
def casteljeau(points, t):
 
69
    points = points[:]
 
70
    while len(points) > 1:
 
71
        for i in range(len(points) - 1):
 
72
            points[i] = points[i] * (1 - t) + points[i + 1] * t
 
73
        del points[-1]
 
74
    return points[0]
 
75
 
 
76
def color(t):
 
77
    points = [0, 0, 1, 0, 0]
 
78
    casteljeau([0, 0, 1, 0, 0], t) / 0.375
 
79
 
 
80
class ModuleGraph(object):
 
81
    def __init__(self, path):
 
82
        self.imports = {}
 
83
        self.clusters = {}
 
84
        self.mod_to_cluster = {}
 
85
        for f in path.visit("*.py"):
 
86
            if include_file(f):
 
87
                self.imports[get_mod_from_path(f)] = find_references(f)
 
88
        self.remove_object_refs()
 
89
        self.remove_double_refs()
 
90
        self.incoming = {}
 
91
        for mod in self.imports:
 
92
            self.incoming[mod] = sets.Set()
 
93
        for mod, refs in self.imports.iteritems():
 
94
            for ref in refs:
 
95
                if ref[0] in self.incoming:
 
96
                    self.incoming[ref[0]].add(mod)
 
97
        self.remove_single_nodes()
 
98
        self.topgraph_properties = ["rankdir=LR"]
 
99
 
 
100
    def remove_object_refs(self):
 
101
        # reduces cases like import pypy.translator.genc.basetype.CType to
 
102
        # import pypy.translator.genc.basetype
 
103
        for mod, refs in self.imports.iteritems():
 
104
            i = 0
 
105
            while i < len(refs):
 
106
                if refs[i][0] in self.imports:
 
107
                    i += 1
 
108
                else:
 
109
                    nref = get_module(refs[i][0], self.imports)
 
110
                    if nref is None:
 
111
                        print "removing", repr(refs[i])
 
112
                        del refs[i]
 
113
                    else:
 
114
                        refs[i] = (nref, None)
 
115
                        i += 1
 
116
 
 
117
    def remove_double_refs(self):
 
118
        # remove several references to the same module
 
119
        for mod, refs in self.imports.iteritems():
 
120
            i = 0
 
121
            seen_refs = sets.Set()
 
122
            while i < len(refs):
 
123
                if refs[i] not in seen_refs:
 
124
                    seen_refs.add(refs[i])
 
125
                    i += 1
 
126
                else:
 
127
                    del refs[i]
 
128
 
 
129
    def remove_single_nodes(self):
 
130
        # remove nodes that have no attached edges
 
131
        rem = []
 
132
        for mod, refs in self.imports.iteritems():
 
133
            if len(refs) == 0 and len(self.incoming[mod]) == 0:
 
134
                rem.append(mod)
 
135
        for m in rem:
 
136
            del self.incoming[m]
 
137
            del self.imports[m]
 
138
 
 
139
    def create_clusters(self):
 
140
        self.topgraph_properties.append("compound=true;")
 
141
        self.clustered = True
 
142
        hierarchy = [sets.Set() for i in range(6)]
 
143
        for mod in self.imports:
 
144
            for i, d in enumerate(mod.split(".")):
 
145
                hierarchy[i].add(d)
 
146
        for i in range(6):
 
147
            if len(hierarchy[i]) != 1:
 
148
                break
 
149
        for mod in self.imports:
 
150
            cluster = mod.split(".")[i]
 
151
            if i == len(mod.split(".")) - 1:
 
152
                continue
 
153
            if cluster not in self.clusters:
 
154
                self.clusters[cluster] = sets.Set()
 
155
            self.clusters[cluster].add(mod)
 
156
            self.mod_to_cluster[mod] = cluster
 
157
 
 
158
    def remove_tangling_randomly(self):
 
159
        # remove edges to nodes that have a lot incoming edges randomly
 
160
        tangled = []
 
161
        for mod, incoming in self.incoming.iteritems():
 
162
            if len(incoming) > 10:
 
163
                tangled.append(mod)
 
164
        for mod in tangled:
 
165
            remove = sets.Set()
 
166
            incoming = self.incoming[mod]
 
167
            while len(remove) < len(incoming) * 0.80:
 
168
                remove.add(random.choice(list(incoming)))
 
169
            for rem in remove:
 
170
                for i in range(len(self.imports[rem])):
 
171
                    if self.imports[rem][i][1] == mod:
 
172
                        break
 
173
                del self.imports[rem][i]
 
174
                incoming.remove(rem)
 
175
                print "removing", mod, "<-", rem
 
176
        self.remove_single_nodes()
 
177
 
 
178
    def dotfile(self, dot):
 
179
        f = dot.open("w")
 
180
        f.write("digraph G {\n")
 
181
        for prop in self.topgraph_properties:
 
182
            f.write("\t%s\n" % prop)
 
183
        #write clusters and inter-cluster edges
 
184
        for cluster, nodes in self.clusters.iteritems():
 
185
            f.write("\tsubgraph cluster_%s {\n" % cluster)
 
186
            f.write("\t\tstyle=filled;\n\t\tcolor=lightgrey\n")
 
187
            for node in nodes:
 
188
                f.write('\t\t"%s";\n' % node[5:])
 
189
            for mod, refs in self.imports.iteritems():
 
190
                for ref in refs:
 
191
                    if mod in nodes and ref[0] in nodes:
 
192
                        f.write('\t\t"%s" -> "%s";\n' % (mod[5:], ref[0][5:]))
 
193
            f.write("\t}\n")
 
194
        #write edges between clusters
 
195
        for mod, refs in self.imports.iteritems():
 
196
            try:
 
197
                nodes = self.clusters[self.mod_to_cluster[mod]]
 
198
            except KeyError:
 
199
                nodes = sets.Set()
 
200
            for ref in refs:
 
201
                if ref[0] not in nodes:
 
202
                    f.write('\t"%s" -> "%s";\n' % (mod[5:], ref[0][5:]))
 
203
        f.write("}")
 
204
        f.close()
 
205
 
 
206
if __name__ == "__main__":
 
207
    import sys
 
208
    if len(sys.argv) > 1:
 
209
        path = py.path.local(sys.argv[1])
 
210
    else:
 
211
        path = py.path.local(".")
 
212
    gr = ModuleGraph(path)
 
213
    gr.create_clusters()
 
214
    dot = path.join("import_graph.dot")
 
215
    gr.dotfile(dot)