1 files changed, 313 insertions, 0 deletions
diff --git a/tools/dev/mergegraph/mergegraph.py b/tools/dev/mergegraph/mergegraph.py
new file mode 100644
index 0000000..834b164
--- /dev/null
+++ b/tools/dev/mergegraph/mergegraph.py
@@ -0,0 +1,313 @@
+#!/usr/bin/env python
+
+# ====================================================================
+#    Licensed to the Apache Software Foundation (ASF) under one
+#    or more contributor license agreements.  See the NOTICE file
+#    distributed with this work for additional information
+#    regarding copyright ownership.  The ASF licenses this file
+#    to you under the Apache License, Version 2.0 (the
+#    "License"); you may not use this file except in compliance
+#    with the License.  You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing,
+#    software distributed under the License is distributed on an
+#    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+#    KIND, either express or implied.  See the License for the
+#    specific language governing permissions and limitations
+#    under the License.
+# ====================================================================
+
+# Config file format:
+example = """
+  [graph]
+  filename = merge-sync-1.png
+  title = Sync Merge: CC vs SVN
+  # Branches: (branch name, branched from node, first rev, last rev).
+  branches = [
+    ('A', 'O0', 1, 4),
+    ('O', None, 0, 0),
+    ('B', 'O0', 1, 5)
+    ]
+  # Changes: nodes in which a change was committed; merge targets need not
+  # be listed here.
+  changes = [
+    'A1', 'A2', 'A3', 'A4',
+    'B1', 'B2', 'B3', 'B4', 'B5'
+    ]
+  # Merges: (base node, source-right node, target node, label).
+  # Base is also known as source-left.
+  merges = [
+    ('O0', 'A:1', 'B3', 'sync'),
+    ('A2', 'A:3', 'B5', 'sync'),
+    ]
+  # Annotations for nodes: (node, annotation text).
+  annotations = [
+    ('A2', 'cc:YCA')
+    ]
+"""
+
+# Notes about different kinds of merge.
+#
+# A basic 3-way merge is ...
+#
+# The ClearCase style of merge is a 3-way merge.
+#
+# The Subversion style of merge (that is, one phase of a Subversion merge)
+# is a three-way merge with its base (typically the YCA) on the source branch.
+
+
+import sys
+import pydot
+from pydot import Node, Edge
+
+
+def mergeinfo_to_node_list(mi):
+  """Convert a mergeinfo string such as '/foo:1,3-5*' into a list of
+     node names such as ['foo1', 'foo3', 'foo4', 'foo5'].
+  """
+  ### Doesn't yet strip the leading slash.
+  l = []
+  if mi:
+    for mi_str in mi.split(' '):
+      path, ranges = mi_str.split(':')
+      for r in ranges.split(','):
+        if r.endswith('*'):
+          # TODO: store & use this 'non-inheritable' flag
+          # Remove the flag
+          r = r[:-1]
+        rlist = r.split('-')
+        r1 = int(rlist[0])
+        if len(rlist) == 2:
+          r2 = int(rlist[1])
+        else:
+          r2 = r1
+        for rev in range(r1, r2 + 1):
+          l.append(path + str(rev))
+  return l
+
+
+class MergeGraph(pydot.Graph):
+  """Base class, not intended for direct use.  Use MergeDot for the main
+     graph and MergeSubgraph for a subgraph.
+  """
+
+  def mk_origin_node(graph, name, label):
+    """Add a node to the graph"""
+    graph.add_node(Node(name, label=label, shape='plaintext'))
+
+  def mk_invis_node(graph, name):
+    """Add a node to the graph"""
+    graph.add_node(Node(name, style='invis'))
+
+  def mk_node(graph, name, label=None):
+    """Add a node to the graph, if not already present"""
+    if not graph.get_node(name):
+      if not label:
+        label = name
+      if name in graph.changes:
+        graph.add_node(Node(name, label=label))
+      else:
+        graph.add_node(Node(name, color='grey', label=''))
+
+  def mk_merge_target(graph, target_node, important):
+    """Add a merge target node to the graph."""
+    if important:
+      color = 'red'
+    else:
+      color = 'black'
+    graph.add_node(Node(target_node, color=color, fontcolor=color, style='bold'))
+
+  def mk_edge(graph, name1, name2, **attrs):
+    """Add an ordinary edge to the graph"""
+    graph.add_edge(Edge(name1, name2, dir='none', style='dotted', color='grey', **attrs))
+
+  def mk_br_edge(graph, name1, name2):
+    """Add a branch-creation edge to the graph"""
+    # Constraint=false to avoid the Y-shape skewing the nice parallel branch lines
+    graph.mk_edge(name1, name2, constraint='false')
+
+  def mk_merge_edge(graph, src_node, tgt_node, kind, label, important):
+    """Add a merge edge to the graph"""
+    if important:
+      color = 'red'
+    else:
+      color = 'grey'
+    e = Edge(src_node, tgt_node, constraint='false',
+             label='"' + label + '"',
+             color=color, fontcolor=color,
+             style='bold')
+    if kind.startswith('cherry'):
+      e.set_style('dashed')
+    graph.add_edge(e)
+
+  def mk_mergeinfo_edge(graph, base_node, src_node, important):
+    """"""
+    if important:
+      color = 'red'
+    else:
+      color = 'grey'
+    graph.add_edge(Edge(base_node, src_node,
+                        dir='both', arrowtail='odot', arrowhead='tee',
+                        color=color, constraint='false'))
+
+  def mk_invis_edge(graph, name1, name2):
+    """Add an invisible edge to the graph"""
+    graph.add_edge(Edge(name1, name2, style='invis'))
+
+  def add_merge(graph, merge, important):
+    """Add a merge"""
+    base_node, src_node, tgt_node, kind = merge
+
+    if base_node and src_node:  # and not kind.startwith('cherry'):
+      graph.mk_mergeinfo_edge(base_node, src_node, important)
+
+    # Merge target node
+    graph.mk_merge_target(tgt_node, important)
+
+    # Merge edge
+    graph.mk_merge_edge(src_node, tgt_node, kind, kind, important)
+
+  def add_annotation(graph, node, label, color='lightblue'):
+    """Add a graph node that serves as an annotation to a normal node.
+       More than one annotation can be added to the same normal node.
+    """
+    subg_name = node + '_annotations'
+
+    def get_subgraph(graph, name):
+      """Equivalent to pydot.Graph.get_subgraph() when there is no more than
+         one subgraph of the given name, but working aroung a bug in
+         pydot.Graph.get_subgraph().
+      """
+      for subg in graph.get_subgraph_list():
+        if subg.get_name() == name:
+          return subg
+      return None
+
+    g = get_subgraph(graph, subg_name)
+    if not g:
+      g = pydot.Subgraph(subg_name, rank='same')
+      graph.add_subgraph(g)
+
+    ann_node = node + '_'
+    while g.get_node(ann_node):
+      ann_node = ann_node + '_'
+    g.add_node(Node(ann_node, shape='box', style='filled', color=color,
+                    label='"' + label + '"'))
+    g.add_edge(Edge(ann_node, node, style='solid', color=color,
+                    dir='none', constraint='false'))
+
+class MergeSubgraph(MergeGraph, pydot.Subgraph):
+  """"""
+  def __init__(graph, **attrs):
+    """"""
+    MergeGraph.__init__(graph)
+    pydot.Subgraph.__init__(graph, **attrs)
+
+class MergeDot(MergeGraph, pydot.Dot):
+  """
+  # TODO: In the 'merges' input, find the predecessor automatically.
+  """
+  def __init__(graph, config_filename=None,
+               filename=None, title=None, branches=None, changes=None,
+               merges=[], annotations=[], **attrs):
+    """Return a new MergeDot graph generated from a config file or args."""
+    MergeGraph.__init__(graph)
+    pydot.Dot.__init__(graph, **attrs)
+
+    if config_filename:
+      graph.read_config(config_filename)
+    else:
+      graph.filename = filename
+      graph.title = title
+      graph.branches = branches
+      graph.changes = changes
+      graph.merges = merges
+      graph.annotations = annotations
+
+    graph.construct()
+
+  def read_config(graph, config_filename):
+    """Initialize a MergeDot graph's input data from a config file."""
+    import ConfigParser
+    if config_filename.endswith('.txt'):
+      default_basename = config_filename[:-4]
+    else:
+      default_basename = config_filename
+
+    config = ConfigParser.SafeConfigParser({ 'basename': default_basename,
+                                             'title': None,
+                                             'merges': '[]',
+                                             'annotations': '[]' })
+    files_read = config.read(config_filename)
+    if len(files_read) == 0:
+      print >> sys.stderr, 'graph: unable to read graph config from "' + config_filename + '"'
+      sys.exit(1)
+    graph.basename = config.get('graph', 'basename')
+    graph.title = config.get('graph', 'title')
+    graph.branches = eval(config.get('graph', 'branches'))
+    graph.changes = eval(config.get('graph', 'changes'))
+    graph.merges = eval(config.get('graph', 'merges'))
+    graph.annotations = eval(config.get('graph', 'annotations'))
+
+  def construct(graph):
+    """"""
+    # Origin nodes (done first, in an attempt to set the order)
+    for br, orig, r1, head in graph.branches:
+      name = br + '0'
+      if r1 > 0:
+        graph.mk_origin_node(name, br)
+      else:
+        graph.mk_node(name, label=br)
+
+    # Edges and target nodes for merges
+    for merge in graph.merges:
+      # Emphasize the last merge, as it's the important one
+      important = (merge == graph.merges[-1])
+      graph.add_merge(merge, important)
+
+    # Parallel edges for basic lines of descent
+    for br, orig, r1, head in graph.branches:
+      sub_g = MergeSubgraph(ordering='out')
+      for i in range(1, head + 1):
+        prev_n = br + str(i - 1)
+        this_n = br + str(i)
+
+        # Normal edges and nodes
+        if i < r1:
+          graph.mk_invis_node(this_n)
+        else:
+          graph.mk_node(this_n)
+        if i <= r1:
+          graph.mk_invis_edge(prev_n, this_n)
+        else:
+          graph.mk_edge(prev_n, this_n)
+
+      # Branch creation edges
+      if orig:
+        sub_g.mk_br_edge(orig, br + str(r1))
+
+      graph.add_subgraph(sub_g)
+
+    # Annotations
+    for node, label in graph.annotations:
+      graph.add_annotation(node, label)
+
+    # A title for the graph (added last so it goes at the top)
+    if graph.title:
+      graph.add_node(Node('title', shape='plaintext', label='"' + graph.title + '"'))
+
+  def save(graph, format='png', filename=None):
+    """Save this merge graph to the given file format. If filename is None,
+       construct a filename from the basename of the original file (as passed
+       to the constructor and then stored in graph.basename) and the suffix
+       according to the given format.
+    """
+    if not filename:
+      filename = graph.basename + '.' + format
+    if format == 'sh':
+      import save_as_sh
+      save_as_sh.write_sh_file(graph, filename)
+    else:
+      pydot.Dot.write(graph, filename, format=format)