treeplot

   1 #!/usr/bin/python
   2 #
   3 # Create a graph of patch flow into the mainline.
   4 #
   5 import sys
   6 import patterns
   7
   8 #
   9 # The various types of commit we understand.
  10 #
  11 class Commit:
  12     def __init__(self, id, parent):
  13         self.id = id
  14         self.parent = parent
  15         self.ismerge = 0
  16         self.treepriority = 0
  17 #
  18 # Merges are special
  19 #
  20 class Merge (Commit):
  21     def __init__(self, id, parent):
  22         Commit.__init__(self, id, parent)
  23         self.ismerge = 1
  24         self.internal = 1 # Two branches within a repo?
  25         self.parents = [ parent ]
  26
  27     def addparent(self, parentid):
  28         self.parents.append(parentid)
  29
  30     def addtree(self, tree):
  31         self.tree = tree
  32         self.internal = 0
  33
  34 #
  35 # Trees: where the commits come from.
  36 #
  37 class Tree:
  38     def __init__(self, name, url):
  39         self.name = name
  40         self.url = url
  41         self.inputs = [ ]
  42         self.commits = [ ]
  43
  44     def addcommit(self, id):
  45         self.commits.append(id)
  46
  47     def addinput(self, tree):
  48         if tree not in self.inputs:
  49             self.inputs.append(tree)
  50             # print '%s -> %s' % (tree.name, self.name)
  51
  52 Mainline = Tree('Mainline',
  53                 'git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git')
  54 KnownTrees = { Mainline.url: Mainline }
  55
  56 def NormalizeURL(url):
  57     if url[:4] == 'git:':
  58         return url
  59     if url == '../net-2.6/':
  60         url = 'git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6'
  61     url = url.replace('master.kernel.org:', 'git://git.kernel.org')
  62     if url[-18:] == 'torvalds/linux-2.6':
  63         url += '.git'
  64     if url[:8] == '/pub/scm':
  65         url = 'git://git.kernel.org' + url
  66     return url
  67
  68 def LookupTree(url):
  69     url = NormalizeURL(url)
  70     try:
  71         return KnownTrees[url]
  72     except KeyError:
  73         tree = Tree(url, url)
  74         KnownTrees[url] = tree
  75         return tree
  76
  77 #
  78 # We track which tree every commit belongs to.
  79 #
  80 CommitTrees = { }
  81 class CTEntry:
  82     def __init__ (self, tree, priority, path):
  83         self.tree = tree
  84         self.priority = priority
  85         self.path = path
  86
  87 def AddCommitTree(id, entry):
  88 #    print 'add: ', id, '[',
  89 #    for tree in entry.path:
  90 #        print tree.name,
  91 #    print ']'
  92     try:
  93         oldentry = CommitTrees[id]
  94         if entry.priority < oldentry.priority:
  95             CommitTrees[id] = entry
  96     except KeyError:
  97         CommitTrees[id] = entry
  98
  99
 100 def LookupCommitTree(id):
 101     try:
 102         return CommitTrees[id]
 103     except KeyError:
 104         print 'Unfound commit %s' % (id)
 105         return CTEntry (Mainline, 0, [])
 106
 107 #
 108 # Input handling with one-line pushback.
 109 #
 110 SavedLine = None
 111 Input = sys.stdin
 112
 113 def GetLine():
 114     global SavedLine
 115     if SavedLine:
 116         ret = SavedLine
 117         SavedLine = None
 118         return ret
 119     return Input.readline()
 120
 121 def SaveLine(line):
 122     global SavedLine
 123     SavedLine = line
 124
 125 #
 126 # Pull in a commit and see what it is.
 127 #
 128 def GetCommit():
 129     #
 130     # Skip junk up to the next commit.
 131     #
 132     while 1:
 133         line = GetLine()
 134         if not line:
 135             return None
 136         m = patterns.Pcommit.match(line)
 137         if m:
 138             break
 139
 140     #
 141     # Look at the commit and see how many parents we have.
 142     #
 143     ids = m.group(1).split()
 144     if len(ids) <= 1:
 145         if len(CommitTrees.values()) > 0:
 146             print 'No-Parent commit:', ids[0]
 147             return GetCommit()
 148         print 'Did you run git with --parents?'
 149         print ids
 150         sys.exit(1)
 151     if len(ids) == 2:  # Simple commit
 152         return Commit(ids[0], ids[1])
 153     #
 154     # OK, we have a merge.
 155     #
 156     merge = Merge(ids[0], ids[1])
 157     for id in ids[2:]:
 158         merge.addparent(id)
 159     #
 160     # We need to figure out what kind of merge it is, so read through the
 161     # descriptive text to the merge line.
 162     #
 163     while 1:
 164         line = GetLine()
 165         if not line:
 166             print 'EOF looking for merge line'
 167             return None
 168         #
 169         # Maybe it's an external merge?
 170         #
 171         m = patterns.PExtMerge.match(line)
 172         if m:
 173             merge.addtree(LookupTree(m.group(2)))
 174             return merge
 175         #
 176         # OK, maybe it's internal
 177         #
 178         if patterns.PIntMerge.match(line) or patterns.PIntMerge2.match(line):
 179             #print 'Internal:', line[:-1]
 180             merge.internal = 1
 181             return merge
 182         m = patterns.Pcommit.match(line)
 183         if m:
 184             print 'Hit next commit (%s) looking for merge line' % (m.group(1))
 185             SaveLine(line)
 186             return GetCommit()
 187
 188 #
 189 # Print out a tree and its inputs
 190 #
 191 def PrintTree(tree, indent = ''):
 192     print '%s%4d %s' % (indent, len(tree.commits), tree.name)
 193     for input in tree.inputs:
 194         PrintTree(input, indent + '    ')
 195
 196 #
 197 # Let's try to build a data structure giving the patch flows.
 198 #
 199 class FlowNode:
 200     def __init__(self, tree):
 201         self.tree = tree
 202         self.inputs = { }
 203         self.commits = 0
 204
 205 def BuildFlowTree():
 206     rootnode = FlowNode(Mainline)
 207     for centry in CommitTrees.values():
 208         FillFlowPath(centry.path, rootnode)
 209     return rootnode
 210
 211 def FillFlowPath(path, node):
 212     node.commits += 1
 213     if len(path) == 0:
 214         return
 215     next, rest = path[0], path[1:]
 216     try:
 217         nextnode = node.inputs[next.name]
 218     except KeyError:
 219         nextnode = node.inputs[next.name] = FlowNode(next)
 220     return FillFlowPath(rest, nextnode)
 221
 222 def PrintFlowTree(ftree, indent = ''):
 223     print '%s%3d %s' % (indent, ftree.commits, ftree.tree.name)
 224     for input in ftree.inputs.values():
 225         PrintFlowTree(input, indent + '  ')
 226
 227 #
 228 # Something for graphviz
 229 #
 230 GVHeader = '''digraph "runtree" {
 231 graph [ label = "Patch flow into the mainline",
 232         concentrate = true,
 233         nodesep = 0.1,
 234         rankdir = LR ];
 235 node [shape = polygon,
 236       sides = 4,
 237       height = 0.3
 238       fontsize = 8];
 239 '''
 240
 241
 242 MainlineCommits = 0
 243
 244 def GVTree(ftree):
 245     global MainlineCommits
 246     MainlineCommits = ftree.commits
 247     gvf = open('runtree.gv', 'w')
 248     gvf.write(GVHeader)
 249     inputs = ftree.inputs.values()
 250     inputs.sort(GVSort)
 251     for input in inputs:
 252         GVPrintNode(gvf, input, 'Mainline')
 253     gvf.write('}\n')
 254
 255 def GVNodeName(treename):
 256     sname = treename.split('/')
 257     if treename.find('kernel.org') >= 0:
 258         return '%s/%s' % (sname[-2], sname[-1])
 259     sep = treename.find ('://')
 260     if sep > 0:
 261         return treename[sep+3:]
 262     return treename
 263
 264 def GVSort(n1, n2):
 265     return n2.commits - n1.commits
 266
 267 def GVPrintNode(gvf, node, parent):
 268     name = GVNodeName(node.tree.name)
 269     gvf.write ('"%s" -> "%s" [taillabel = "%d", labelfontsize = 8' % (name, parent, node.commits))
 270     gvf.write (', arrowsize = 0.5')
 271     if MainlineCommits/node.commits < 20:
 272         gvf.write(', color = red')
 273     elif MainlineCommits/node.commits < 100:
 274         gvf.write(', color = orange');
 275     gvf.write(']\n')
 276     inputs = node.inputs.values()
 277     if inputs:
 278         inputs.sort(GVSort)
 279         for input in inputs:
 280             GVPrintNode(gvf, input, name)
 281
 282 #
 283 # Main code.
 284 #
 285 commit = GetCommit()
 286 ncommits = 0
 287 while commit:
 288     ncommits += 1
 289     entry = LookupCommitTree(commit.id)
 290     tree = entry.tree
 291     priority = entry.priority
 292     tree.addcommit(commit.id)
 293     #
 294     # For regular commits, just remember the tree involved
 295     #
 296     if not commit.ismerge:
 297         AddCommitTree(commit.parent, entry)
 298     #
 299     # For merges we have to deal with all the parents.
 300     #
 301     else:
 302         AddCommitTree(commit.parents[0], CTEntry (tree, priority, entry.path))
 303         if commit.internal:
 304             for p in commit.parents[1:]:
 305                 path = entry.path + [tree]
 306                 AddCommitTree(p, CTEntry (tree, priority, entry.path))
 307         else:
 308             for p in commit.parents[1:]:
 309                 path = entry.path + [commit.tree]
 310                 AddCommitTree(p, CTEntry (commit.tree, priority + 1,  path))
 311                 if commit.tree is not Mainline:
 312                     tree.addinput(commit.tree)
 313     commit = GetCommit()
 314
 315 #PrintTree(Mainline)
 316 ftree = BuildFlowTree()
 317 PrintFlowTree(ftree)
 318 GVTree(ftree)
 319 print '%d commits total, %d trees' % (MainlineCommits, len (KnownTrees.keys()))