Copy git tooling into testing_support.

testing_support/git/schema.py

Index: testing_support/git/schema.py
diff --git a/testing_support/git/schema.py b/testing_support/git/schema.py
new file mode 100644
index 0000000000000000000000000000000000000000..b5e171a6eb848fe31fbad69344654b01e5b72e96
--- /dev/null
+++ b/testing_support/git/schema.py
@@ -0,0 +1,124 @@
+# Copyright 2014 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import collections
+import copy
+
+
+from testing_support.git.util import OrderedSet
+
+
+class GitRepoSchema(object):
+  """A declarative git testing repo.
+
+  Pass a schema to __init__ in the form of:
+     A B C D
+       B E D
+
+  This is the repo
+
+     A - B - C - D
+           \ E /
+
+  Whitespace doesn't matter. Each line is a declaration of which commits come
+  before which other commits.
+
+  Every commit gets a tag 'tag_%(commit)s'
+  Every unique terminal commit gets a branch 'branch_%(commit)s'
+  Last commit in First line is the branch 'master'
+  Root commits get a ref 'root_%(commit)s'
+
+  Timestamps are in topo order, earlier commits (as indicated by their presence
+  in the schema) get earlier timestamps. Stamps start at the Unix Epoch, and
+  increment by 1 day each.
+  """
+  COMMIT = collections.namedtuple('COMMIT', 'name parents is_branch is_root')
+
+  def __init__(self, repo_schema='',
+               content_fn=lambda v: {v: {'data': v}}):
+    """Builds a new GitRepoSchema.
+
+    Args:
+      repo_schema (str) - Initial schema for this repo. See class docstring for
+        info on the schema format.
+      content_fn ((commit_name) -> commit_data) - A function which will be
+        lazily called to obtain data for each commit. The results of this
+        function are cached (i.e. it will never be called twice for the same
+        commit_name). See the docstring on the GitRepo class for the format of
+        the data returned by this function.
+    """
+    self.master = None
+    self.par_map = {}
+    self.data_cache = {}
+    self.content_fn = content_fn
+    self.add_commits(repo_schema)
+
+  def walk(self):
+    """(Generator) Walks the repo schema from roots to tips.
+
+    Generates GitRepoSchema.COMMIT objects for each commit.
+
+    Throws an AssertionError if it detects a cycle.
+    """
+    is_root = True
+    par_map = copy.deepcopy(self.par_map)
+    while par_map:
+      empty_keys = set(k for k, v in par_map.iteritems() if not v)
+      assert empty_keys, 'Cycle detected! %s' % par_map
+
+      for k in sorted(empty_keys):
+        yield self.COMMIT(k, self.par_map[k],
+                          not any(k in v for v in self.par_map.itervalues()),
+                          is_root)
+        del par_map[k]
+      for v in par_map.itervalues():
+        v.difference_update(empty_keys)
+      is_root = False
+
+  def add_partial(self, commit, parent=None):
+    if commit not in self.par_map:
+      self.par_map[commit] = OrderedSet()
+    if parent is not None:
+      self.par_map[commit].add(parent)
+
+  def add_commits(self, schema):
+    """Adds more commits from a schema into the existing Schema.
+
+    Args:
+      schema (str) - See class docstring for info on schema format.
+
+    Throws an AssertionError if it detects a cycle.
+    """
+    for commits in (l.split() for l in schema.splitlines() if l.strip()):
+      parent = None
+      for commit in commits:
+        self.add_partial(commit, parent)
+        parent = commit
+      if parent and not self.master:
+        self.master = parent
+    for _ in self.walk():  # This will throw if there are any cycles.
+      pass
+
+  def data_for(self, commit):
+    """Obtains the data for |commit|.
+
+    See the docstring on the GitRepo class for the format of the returned data.
+
+    Caches the result on this GitRepoSchema instance.
+    """
+    if commit not in self.data_cache:
+      self.data_cache[commit] = self.content_fn(commit)
+    return self.data_cache[commit]
+
+  def simple_graph(self):
+    """Returns a dictionary of {commit_subject: {parent commit_subjects}}
+
+    This allows you to get a very simple connection graph over the whole repo
+    for comparison purposes. Only commit subjects (not ids, not content/data)
+    are considered
+    """
+    ret = {}
+    for commit in self.walk():
+      ret.setdefault(commit.name, set()).update(commit.parents)
+    return ret