treeplot

   1 #!/usr/bin/python3
   2 #
   3 # git log --pretty="%H %P" | this program
   4 # See option descriptions at bottom
   5 #
   6 # This little program cranks through a series of patches, trying to determine
   7 # which trees each flowed through on its way to the mainline.  It does a
   8 # 'git describe' on each, so don't expect it to be fast for large numbers
   9 # of patches.
  10 #
  11 # One warning: it is easily confused by local branches, tags, etc.  For
  12 # best results, run it on a mainline tree with no added frobs.  Using
  13 # "git clone --reference" is a relatively easy way to come up with such
  14 # a tree without redownloading the whole mess.
  15 #
  16 import sys, subprocess, argparse, pickle
  17 import graphviz
  18 import patterns
  19
  20 Mergepat = patterns.patterns['ExtMerge']
  21 IntMerge = patterns.patterns['IntMerge']
  22 IntMerge2 = patterns.patterns['IntMerge2']
  23 Mergelist = { }
  24
  25 class Merge:
  26     def __init__(self, id, tree = None, signed = False):
  27         self.id = id
  28         self.commits = [ ]
  29         self.merges = [ ]
  30         self.tree = tree or '?'
  31         self.internal = False
  32         self.signed = signed
  33         if tree is None:
  34             self.getdesc()
  35         Mergelist[id] = self
  36
  37     def normalize_tree(self, tree):
  38         colonslash = tree.find('://')
  39         if colonslash > 0:
  40             tree = tree[colonslash+3:]
  41         if tree.find('git.kernel.org') >= 0:
  42             stree = tree.split('/')
  43             return '$KORG/%s/%s' % (stree[-2], stree[-1])
  44         return tree
  45
  46     def getdesc(self):
  47         command = ['git', 'log', '-1', '--show-signature', self.id]
  48         p = subprocess.run(command, cwd = Repo, capture_output = True,
  49                            encoding='utf8')
  50         #
  51         # Sometimes we don't match a pattern; that means that the
  52         # committer radically modified the merge message.  A certain
  53         # Eric makes them look like ordinary commits...  Others use
  54         # it to justify backmerges of the mainline.  Either way, the
  55         # best response is to treat it like an internal merge.
  56         #
  57         self.internal = True
  58         for line in p.stdout.split('\n'):
  59             #
  60             # Note if there's a GPG signature
  61             #
  62             if line.startswith('gpg:'):
  63                 self.signed = True
  64                 continue
  65             #
  66             # Maybe it's a merge of an external tree.
  67             #
  68             m = Mergepat.search(line)
  69             if m:
  70                 self.tree = self.normalize_tree(m.group(3))
  71                 self.internal = False
  72                 break
  73             #
  74             # Or maybe it's an internal merge.
  75             #
  76             m = IntMerge.search(line) or IntMerge2.search(line)
  77             if m:
  78                 self.internal = True
  79                 break
  80
  81     def add_commit(self, id):
  82         self.commits.append(id)
  83
  84     def add_merge(self, merge):
  85         self.merges.append(merge)
  86
  87 #
  88 # Read the list of commits from the input stream and find which
  89 # merge brought in each.
  90 #
  91 def ingest_commits(src):
  92     count = 0
  93     expected = 'nothing yet'
  94     for line in src.readlines():
  95         sline = line[:-1].split()
  96         commit = sline[0]
  97         is_merge = (len(sline) > 2)
  98         if (commit == expected) and not is_merge:
  99             mc = last_merge
 100         else:
 101             mc = Mergelist[find_merge(sline[0])]  # Needs try
 102         if is_merge:
 103             mc.add_merge(Merge(commit))
 104         else:
 105             mc.add_commit(commit)
 106         count += 1
 107         if (count % 50) == 0:
 108             sys.stderr.write('\r%5d ' % (count))
 109             sys.stderr.flush()
 110         expected = sline[1]
 111         last_merge = mc
 112     print()
 113 #
 114 # Figure out which merge brought in a commit.
 115 #
 116 MergeIDs = { }
 117
 118 def find_merge(commit):
 119     command = ['git', 'describe', '--contains', commit]
 120     p = subprocess.run(command, cwd = Repo, capture_output = True,
 121                        encoding = 'utf8')
 122     desc = p.stdout.strip()
 123     #
 124     # The description line has the form:
 125     #
 126     #      tag~N^M~n...
 127     #
 128     # the portion up to the last ^ describes the merge we are after;
 129     # in the absence of an ^, assume it's on the main branch.
 130     #
 131     uparrow = desc.rfind('^')
 132     if uparrow < 0:
 133         return 'mainline'
 134     #
 135     # OK, now get the real commit ID of the merge.  Maybe we have
 136     # it stashed?
 137     #
 138     try:
 139         return MergeIDs[desc[:uparrow]]
 140     except KeyError:
 141         pass
 142     #
 143     # Nope, we have to dig it out the hard way.
 144     #
 145     command = ['git', 'log', '--pretty=%H', '-1', desc[:uparrow]]
 146     p = subprocess.run(command, cwd = Repo, capture_output = True,
 147                        encoding = 'utf8')
 148     merge = p.stdout.strip()
 149     #
 150     # If we get back the same commit, we're looking at one of Linus's
 151     # version number tags.
 152     #
 153     if merge == commit:
 154         merge = 'mainline'
 155     MergeIDs[desc[:uparrow]] = merge
 156     return merge
 157
 158 #
 159 # Internal merges aren't interesting from our point of view.  So go through,
 160 # find them all, and move any commits from such into the parent.
 161 #
 162 def zorch_internals(merge):
 163     new_merges = [ ]
 164     for m in merge.merges:
 165         zorch_internals(m)
 166         if m.internal:
 167             merge.commits += m.commits
 168             new_merges += m.merges
 169         else:
 170             new_merges.append(m)
 171     merge.merges = new_merges
 172
 173 #
 174 # Figure out how many commits flowed at each stage.
 175 #
 176 def count_commits(merge):
 177     merge.ccount = len(merge.commits) + 1  # +1 to count the merge itself
 178     for m in merge.merges:
 179         merge.ccount += count_commits(m)
 180     return merge.ccount
 181
 182 #
 183 # ...and how many flowed between each pair of trees
 184 #
 185 Treecounts = { }
 186 SignedTrees = set()
 187
 188 def tree_stats(merge):
 189     SignedTrees.add('mainline')
 190     try:
 191         tcount = Treecounts[merge.tree]
 192     except KeyError:
 193         tcount = Treecounts[merge.tree] = { }
 194     for m in merge.merges:
 195         if m.signed:
 196             SignedTrees.add(m.tree)
 197         mcount = tcount.get(m.tree, 0)
 198         tcount[m.tree] = mcount + m.ccount
 199         tree_stats(m)
 200
 201 #
 202 # Maybe we only want so many top-level trees
 203 #
 204 def trim_trees(limit):
 205     srcs = Treecounts['mainline']
 206     srcnames = srcs.keys()
 207     srcnames = sorted(srcnames, key = lambda i: srcs[i], reverse = True)
 208     nextra = len(srcnames) - limit
 209     zapped = 0
 210     for extra in srcnames[limit:]:
 211         zapped += srcs[extra]
 212         del srcs[extra]
 213     srcs['%d other trees' % (nextra)] = zapped
 214 #
 215 # Take our map of the commit structure and boil it down to how many commits
 216 # moved from one tree to the next.
 217 #
 218
 219 def dumptree(start, indent = ''):
 220     int = ''
 221     if start.internal:
 222         int = 'I: '
 223     print('%s%s%s: %d/%d %s' % (indent, int, start.id[:10],
 224                                  len(start.merges), len(start.commits),
 225                                  start.tree))
 226     for merge in start.merges:
 227         dumptree(merge, indent + '  ')
 228
 229 def dumpflow(tree, indent = '', seen = []):
 230     try:
 231         srcs = Treecounts[tree]
 232     except KeyError:
 233         return
 234     srctrees = sorted(srcs.keys(), key = lambda i: srcs[i], reverse = True)
 235     for src in srctrees:
 236         if src in seen:
 237             print('Skip', src, srcs[src], seen)
 238         else:
 239             if src in SignedTrees:
 240                 print('%s%4d ** %s' % (indent, srcs[src], src))
 241             else:
 242                 print('%s%4d %s' % (indent, srcs[src], src))
 243             dumpflow(src, indent = indent + '  ', seen = seen + [tree])
 244
 245 def totalsignedstats(tree, signed = [ ], unsigned = [ ]):
 246     try:
 247         srcs = Treecounts[tree]
 248     except KeyError:
 249         return 0
 250     for src in sorted(srcs.keys(), key = lambda i: srcs[i], reverse = True):
 251         if (src in signed) or (src in unsigned):
 252             continue
 253         if src in SignedTrees:
 254             signed.append(src)
 255         else:
 256             unsigned.append(src)
 257         return 'stopped here'
 258
 259 def SigStats(tree):
 260     srcs = Treecounts[tree]
 261     spulls = upulls = scommits = ucommits = 0
 262     for src in srcs.keys():
 263         if src in SignedTrees:
 264             spulls += 1
 265             scommits += srcs[src]
 266         else:
 267             upulls += 1
 268             ucommits += srcs[src]
 269     print('%d repos total, %d signed, %d unsigned' % (spulls + upulls,
 270                                                       spulls, upulls))
 271     print('   %d commits from signed, %d from unsigned' % (scommits, ucommits))
 272     print(len(srcs))
 273     print(len(SignedTrees), len(Treecounts.keys()))
 274
 275 #
 276 # Graphviz.
 277 #
 278 def GV_out(file):
 279     graph = graphviz.Digraph('mainline', filename = file, format = 'svg')
 280     graph.body.extend(['label="Patch flow into the mainline"',
 281                        'concentrate=true',
 282                        'rankdir=LR' ])
 283     graph.attr('node', fontsize="20", color="blue", penwidth='4',
 284                shape='ellipse')
 285     graph.node('mainline')
 286     graph.attr('node', fontsize="14", color="black", shape='polygon',
 287                sides='4')
 288     if DoSigned:
 289         GV_out_node_signed(graph, 'mainline')
 290     else:
 291         GV_out_node(graph, 'mainline')
 292     graph.view()
 293
 294 def GV_fixname(name):
 295     return name.replace(':', '/') # or Graphviz chokes
 296
 297 def GV_color(count):
 298     if count >= RedThresh:
 299         return 'red'
 300     if count >= YellowThresh:
 301         return 'orange'
 302     return 'black'
 303
 304 #
 305 # Output nodes with traffic coloring
 306 #
 307 def GV_out_node(graph, node, seen = []):
 308     try:
 309         srcs = Treecounts[node]
 310     except KeyError:  # "applied by linus"
 311         return
 312     srctrees = sorted(srcs.keys(), key = lambda i: srcs[i], reverse = True)
 313     for src in srctrees:
 314         if src not in seen:
 315             graph.edge(GV_fixname(src), GV_fixname(node),
 316                        taillabel='%d' % srcs[src], labelfontsize="14",
 317                        color = GV_color(srcs[src]), penwidth='2')
 318             GV_out_node(graph, src, seen + [node])
 319
 320 #
 321 # Output nodes showing signature status
 322 #
 323 def GV_out_node_signed(graph, node, seen = []):
 324     try:
 325         srcs = Treecounts[node]
 326     except KeyError:  # "applied by linus"
 327         return
 328     srctrees = sorted(srcs.keys(), key = lambda i: srcs[i], reverse = True)
 329     for src in srctrees:
 330         color = 'red'
 331         if src in SignedTrees:
 332             color = 'black'
 333         if src not in seen:
 334             graph.attr('node', color=color)
 335             graph.edge(GV_fixname(src), GV_fixname(node),
 336                        taillabel='%d' % srcs[src], labelfontsize="14",
 337                        color = color, penwidth='2')
 338             GV_out_node_signed(graph, src, seen + [node])
 339 #
 340 # argument parsing stuff.
 341 #
 342 def setup_args():
 343     p = argparse.ArgumentParser()
 344     p.add_argument('-d', '--dump', help = 'Dump merge list to file',
 345                    required = False, default = '')
 346     p.add_argument('-g', '--gvoutput', help = 'Graphviz output',
 347                    required = False, default = '')
 348     p.add_argument('-l', '--load', help = 'Load merge list from file',
 349                    required = False, default = '')
 350     p.add_argument('-o', '--output', help = 'Output file',
 351                    required = False, default = '-')
 352     p.add_argument('-r', '--repo', help = 'Repository location',
 353                    required = False, default = '/home/corbet/kernel')
 354     p.add_argument('-t', '--trim', help = 'Trim top level to this many trees',
 355                    required = False, default = 0, type = int)
 356     p.add_argument('-R', '--red', help = 'Red color threshold',
 357                    required = False, default = 800, type = int)
 358     p.add_argument('-Y', '--yellow', help = 'Yellow color threshold',
 359                    required = False, default = 200, type = int)
 360     p.add_argument('-s', '--signed', help = 'Display signed trees',
 361                    action='store_true', default = False)
 362     return p
 363
 364
 365 p = setup_args()
 366 args = p.parse_args()
 367 Repo = args.repo
 368 RedThresh = args.red
 369 YellowThresh = args.yellow
 370 DoSigned = args.signed
 371 #
 372 # Find our commits.
 373 #
 374 if args.load:
 375     dumpfile = open(args.load, 'rb')
 376     Mergelist = pickle.loads(dumpfile.read())
 377     dumpfile.close
 378     Mainline = Mergelist['mainline']
 379 else:
 380     Mainline = Merge('mainline', tree = 'mainline', signed = True)
 381     ingest_commits(sys.stdin)
 382     if args.dump:
 383         dumpfile = open(args.dump, 'wb')
 384         dumpfile.write(pickle.dumps(Mergelist))
 385         dumpfile.close()
 386 #
 387 # Now generate the flow graph.
 388 #
 389 #dumptree(Mainline)
 390 zorch_internals(Mainline)
 391 #dumptree(Mainline)
 392 Treecounts['mainline'] = { 'Applied by Linus': len(Mainline.commits) }
 393 print('total commits', count_commits(Mainline))
 394 tree_stats(Mainline)
 395 if args.trim:
 396     trim_trees(args.trim)
 397 print('Tree flow')
 398 dumpflow('mainline')
 399 if args.gvoutput:
 400     GV_out(args.gvoutput)
 401 if DoSigned:
 402     SigStats('mainline')