src/git_stats/branch.py

   1 #!/usr/bin/env python
   2
   3 import os
   4 import sys
   5
   6 from optparse import OptionParser
   7 from git import Repo
   8
   9 from git_stats import parse
  10
  11 def prettyName(branch, pretty_names={}):
  12   """Looks up the name of a branch and returns it
  13
  14   Returns only the last part of the branchname.
  15
  16   Args:
  17     branch: The branch to print
  18     pretty_names: A dictionary with commits and their names
  19   """
  20
  21   if not branch in pretty_names:
  22     git = Repo(".").git
  23     name = git.describe("--all", branch)
  24     splitname = name.split('/')
  25     name = splitname[-1]
  26     pretty_names[branch] = name
  27   else:
  28     name = pretty_names[branch]
  29
  30   return name
  31
  32 class Metric:
  33   """This class represents a metric
  34
  35   It is meant to store arbitrary data related to a specific metric.
  36   """
  37
  38   def __init__(self):
  39     self.branch = ""
  40     self.commit = ""
  41     self.dilution = ""
  42
  43   def __str__(self):
  44     res = ("Branch %s, dilution: %d." %
  45         (prettyName(self.branch), self.dilution))
  46
  47     return res
  48
  49 def _bestMetric(metrics):
  50   """Finds the best metric from a set
  51
  52   Iterates the metrics and selects the ones with the lowest dilution.
  53   All the returned metrics are guaranteed to have the same dilution.
  54
  55   Args:
  56     metrics: The metrics to pick the best ones from.
  57
  58   Returns: A list with the best metrics.
  59   """
  60
  61   champs = []
  62
  63   # Find the best metric
  64   for metric in metrics:
  65     # Store the current value for easy access
  66     dilution = metric.dilution
  67
  68     # First element, set the minimum to the current
  69     if not champs:
  70       min = dilution
  71
  72     # Worse than our best, not interesting
  73     if dilution > min:
  74       continue
  75
  76     # Clear the old ones if we have a better minimum
  77     if dilution < min:
  78       champs = []
  79       min = dilution
  80
  81     champs.append(metric)
  82
  83   return min, champs
  84
  85 def _calculateDilution(target, start, parent_lists, global_memory, ignore=[]):
  86   """Calculates the dilution for the specified commit.
  87
  88   Args:
  89     target: The commit to calculate the dilution for.
  90     start: The initial metric information.
  91     parent_list: A dictionary with commits and their parents.
  92     global_memory: A dictionary with all commits and their parents.
  93     ignore: The parent commits of the target commit which should be ignored.
  94   """
  95
  96   metrics = []
  97
  98   memory = {}
  99   stack = []
 100   stack.append(start)
 101
 102   git = Repo(".").git
 103
 104   while stack:
 105     current = stack.pop()
 106
 107     # We found what we are looking for
 108     if target == current.commit:
 109       metrics.append(current)
 110       continue
 111
 112     # Ignore commits that are past the target
 113     if current.commit in ignore:
 114       continue
 115
 116     # If we already checked this commit, don't add it again
 117     if current.commit in memory:
 118       dilution = memory[current.commit]
 119       if dilution <= current.dilution:
 120         continue
 121
 122     # Nor when already checked in a better branch
 123     if current.commit in global_memory:
 124       dilution = global_memory[current.commit]
 125       if dilution < current.dilution:
 126         continue
 127
 128     # Remember this commit
 129     memory[current.commit] = current.dilution
 130     global_memory[current.commit] = current.dilution
 131
 132     # Defaulting to None in the case we only have a partial parent listing
 133     parents = parent_lists.get(current.commit, None)
 134
 135     # Root commit, we can't go any further
 136     if not parents:
 137       continue
 138
 139     # Check all the parents and give only the first one 0 extra dilution
 140     for parent in parents:
 141       if parent == parents[0]:
 142         newdilution = current.dilution
 143       else:
 144         newdilution = current.dilution + 1
 145
 146       # Create the next target
 147       next = Metric()
 148       next.commit = parent
 149       next.branch = current.branch
 150       next.dilution = newdilution
 151
 152       # Add it to the stack to be examined
 153       stack.append(next)
 154
 155   # Nothing new was found here
 156   if not metrics:
 157     return []
 158
 159   # Return only the best metric
 160   min, champs = _bestMetric(metrics)
 161   return champs
 162
 163 def debugPrint(debug, text):
 164   """Only print the specified text if debug is on
 165
 166   debug: Whether debug is on.
 167   text: The text to print
 168   """
 169
 170   if debug:
 171     print(text)
 172
 173 def getBranchMap(branches):
 174   """Creates a branchMap from the specified branches and returns it
 175
 176   The hash of each branch is retreived and stored in a
 177   dictionary with the condition that all values in the map
 178   are unique. As such if multiple branches map to one hash,
 179   only one of those branches (the first one) will be in the
 180   returned map.
 181
 182   Args:
 183     branches: A list of branches that should be in the map.
 184
 185   Returns: A dictionary with branch names and their hashes.
 186   """
 187
 188   git = Repo(".").git
 189
 190   branch_map = {}
 191
 192   for branch in branches:
 193     # Retreive the hash of each branch
 194     branch_hash = git.rev_parse(branch)
 195
 196     if branch_hash in branch_map.values():
 197       continue
 198
 199     branch_map[branch] = branch_hash
 200
 201   return branch_map
 202
 203 def getParentList(commits):
 204   """Retreives the parents of the specified commits and their parents
 205
 206   The parents for all the specified commits, and for the
 207   parents of those commits, are retreived and stored in
 208   a dictionary.
 209
 210   Args:
 211     commits: A list of commits for which the parents should be retreived.
 212
 213   Returns: A dictionary with commits and their parents.
 214   """
 215
 216   git = Repo(".").git
 217
 218   # First mine some data
 219   result = git.rev_list("--parents", *commits)
 220   data = result.split('\n')
 221
 222   parent_list = {}
 223
 224   for item in data:
 225     # Each line contains the commit first, and then all it's parents
 226     splitline = item.split(' ')
 227     first = splitline[0]
 228
 229     # This commit has no parents at all
 230     if len(splitline) == 1:
 231       parent_list[first] = []
 232     #  This commits has no parents either
 233     elif splitline[1] == '':
 234       parent_list[first] = []
 235     # Store all the parents
 236     else:
 237       parent_list[first] = splitline[1:]
 238
 239   return parent_list
 240
 241 def belongsTo(commit,
 242               branch_map,
 243               parent_list,
 244               pretty_names={},
 245               debug=False,
 246               ignore_parents=False):
 247   """Returns which branches the specified commit belongs to
 248
 249   Args:
 250     commit: The commit to examine.
 251     branch_map: A dictionary of all refs and their hashes.
 252     parent_list: A dictionary with tuples of refs and their rev-lists.
 253     pretty_names: A dictionary with commits and their names
 254     debug: Whether to return debug information as well.
 255
 256   Returns: A list of branches that the commit belongs to.
 257   """
 258
 259   git = Repo(".").git
 260
 261   if commit in branch_map:
 262     debugPrint(debug, "Easy as pie, that's a branch head!")
 263     name = branch_map[commit]
 264     return [name]
 265
 266   metrics = []
 267
 268   # Retreive the parents of the target commit and ignore them
 269   if ignore_parents:
 270     result = git.rev_list(commit)
 271     ignore = set(result.split('\n'))
 272   else:
 273     ignore = []
 274
 275   debugPrint(debug, "Checking branches now:")
 276
 277   memory = {}
 278
 279   # Collect the metric for all branches
 280   for branch_name, branch_hash in branch_map.iteritems():
 281     debugPrint(debug, branch_name)
 282
 283     # Create the first metric
 284     metric = Metric()
 285     metric.branch = branch_hash
 286     metric.commit = branch_hash
 287     metric.dilution = 0
 288
 289     # Find the dilution for this branch
 290     metric = _calculateDilution(commit, metric, parent_list, memory, ignore)
 291     metrics = metrics + metric
 292
 293   debugPrint(debug, "Done.\n")
 294
 295   if debug:
 296     print("Listing found metrics:")
 297     for metric in metrics:
 298       print(metric)
 299
 300   min, champs = _bestMetric(metrics)
 301
 302   debugPrint(debug, "Done.\n")
 303
 304   results = []
 305
 306   if debug:
 307     results.append("The minimal dilution is: " + str(min))
 308
 309   # Loop over all the champs and get their name
 310   for metric in champs:
 311     results.append(prettyName(metric.branch, pretty_names))
 312
 313   return results
 314
 315 def branchcontains(branch, commit):
 316   """returns whether the specified branch contains the specified commit.
 317
 318   params:
 319     branch: the branch.
 320     commit: the commit.
 321
 322   returns:
 323     whether the branch contains the commit.
 324   """
 325
 326   git = git(".")
 327   arg = branch + ".." + commit
 328   result = git.rev_list(arg)
 329
 330   if result:
 331     # if there is a difference between these sets, the commit is not in the branch
 332     return false
 333   else:
 334     # there is no difference between the two, thus the branch contains the commit
 335     return true
 336
 337 def branchList(commitFilter, includeRemotes=False):
 338   """Returns all branches that contain the specified commit
 339
 340   Args:
 341     commitFilter: The commit to filter by.
 342     includeRemotes: Whether to search remote branches as well.
 343   """
 344
 345   git = Repo(".").git
 346
 347   args = []
 348
 349   if includeRemotes:
 350     args.append("-a")
 351
 352   if commitFilter:
 353     args.append("--contains")
 354     args.append(commitFilter)
 355
 356   result = git.branch(*args)
 357
 358   branches = result.split('\n')
 359
 360   result = []
 361
 362   for branch in branches:
 363     result.append(branch[2:])
 364
 365   return result
 366
 367 def dispatch(*args):
 368   """Dispatches branch related commands
 369   """
 370
 371   progname = os.path.basename(sys.argv[0]) + " branch"
 372
 373   parser = OptionParser(option_class=parse.GitOption, prog=progname)
 374
 375
 376   parser.add_option(
 377       "-b", "--belongs-to",
 378       type="commit",
 379       metavar="COMMIT",
 380       help="find out which branch the specified commit belongs to")
 381
 382   parser.add_option(
 383       "-d", "--debug",
 384       action="store_true",
 385       help="print debug information on the found metrics")
 386
 387   parser.add_option(
 388       "-c", "--contains",
 389       type="commit",
 390       help="show only branches that contain the specified commit")
 391
 392   parser.add_option(
 393       "-r", "--remotes",
 394       action="store_true",
 395       help="include remotes in the listing")
 396
 397   parser.set_default("debug", False)
 398   parser.set_default("remotes", False)
 399
 400   (options, args) = parser.parse_args(list(args))
 401
 402   if options.belongs_to:
 403     branches = branchList(options.belongs_to, includeRemotes=options.remotes)
 404
 405     branch_map = getBranchMap(branches)
 406     parent_list = getParentList(branch_map.values())
 407
 408     result = belongsTo( options.belongs_to,
 409                         branch_map,
 410                         parent_list,
 411                         debug=options.debug)
 412   else:
 413     result = branchList(commitFilter=options.contains,
 414                         includeRemotes=options.remotes)
 415
 416   print("Matching branches:")
 417
 418   for branch in result:
 419     print(branch)
 420