Rev 2390: Start work on GraphDelta support. in file:///home/robertc/source/baz/netsim/

[Robert Collins]

At file:///home/robertc/source/baz/netsim/

------------------------------------------------------------
revno: 2390
revision-id: robertc at robertcollins.net-20070401061938-xzhb1m77i7fzzkb6
parent: robertc at robertcollins.net-20070401021622-c63kkszulpt30wae
committer: Robert Collins <robertc at robertcollins.net>
branch nick: netsim
timestamp: Sun 2007-04-01 16:19:38 +1000
message:
  Start work on GraphDelta support.
modified:
  bzrlib/errors.py               errors.py-20050309040759-20512168c4e14fbd
  bzrlib/graph.py                graph.py-20050905070950-b47dce53236c5e48
  bzrlib/tests/test_errors.py    test_errors.py-20060210110251-41aba2deddf936a8
  bzrlib/tests/test_graph.py     testgraph.py-20050905070950-42e6c958106610fd
=== modified file 'bzrlib/errors.py'
--- a/bzrlib/errors.py	2007-03-29 16:23:49 +0000
+++ b/bzrlib/errors.py	2007-04-01 06:19:38 +0000
@@ -255,6 +255,15 @@
         self.url = url
 
 
+class NotSubGraph(BzrError):
+
+    _fmt = "'%(to)s' is not a subgraph of '%(from_)s'."
+
+    def __init__(self, from_, to):
+        self.from_ = from_
+        self.to = to
+
+
 class WorkingTreeAlreadyPopulated(BzrError):
 
     _fmt = """Working tree already populated in %(base)s"""

=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2006-10-05 05:37:25 +0000
+++ b/bzrlib/graph.py	2007-04-01 06:19:38 +0000
@@ -15,6 +15,7 @@
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
 
+from bzrlib import errors
 from bzrlib.tsort import topo_sort
 
 
@@ -118,6 +119,9 @@
         self._graph_ancestors = {}
         self._graph_descendants = {}
 
+    def __eq__(self, other):
+        return isinstance(other, Graph) and self.__dict__ == other.__dict__
+
     def add_ghost(self, node_id):
         """Add a ghost to the graph."""
         self.ghosts.add(node_id)
@@ -132,7 +136,19 @@
         for parent in parent_ids:
             self._ensure_descendant(parent)
             self._graph_descendants[parent][node_id] = 1
-        
+
+    def apply_changes(self, delta):
+        """Apply a delta obtained from a changes_from call.
+
+        :return: A new graph which is the result of applying delta to this
+        graph.
+        """
+        return Graph()
+
+    def changes_from(self, graph_from):
+        """Create a GraphDelta from graph_from to self."""
+        return GraphDelta._changes_from(graph_from, self)
+
     def _ensure_descendant(self, node_id):
         """Ensure that a descendant lookup for node_id will work."""
         if not node_id in self._graph_descendants:
@@ -160,3 +176,21 @@
     def get_descendants(self):
         """Return a dictionary of graph node:child_node:distance entries."""
         return dict(self._graph_descendants.items())
+
+
+class GraphDelta(object):
+    """A delta between two DAG's. 
+
+    Currently this requires that the from DAG be a supergraph of the to DAG.
+    This restriction may be lifted in the future.
+    """
+
+    @classmethod
+    def _changes_from(cls, from_, to):
+        """Construct a delta from from_ to to."""
+        result = GraphDelta()
+        from_nodes = set(from_.get_ancestors())
+        to_nodes = set(to.get_ancestors())
+        if to_nodes.difference(from_nodes):
+            raise errors.NotSubGraph(from_, to)
+        return result

=== modified file 'bzrlib/tests/test_errors.py'
--- a/bzrlib/tests/test_errors.py	2007-03-14 20:47:17 +0000
+++ b/bzrlib/tests/test_errors.py	2007-04-01 06:19:38 +0000
@@ -99,6 +99,10 @@
             str(error))
         self.assertIsInstance(error, errors.NoSuchRevision)
 
+    def test_not_sub_graph(self):
+        error = errors.NotSubGraph("from", "to")
+        self.assertEqualDiff("'to' is not a subgraph of 'from'.", str(error))
+
     def test_not_write_locked(self):
         error = errors.NotWriteLocked('a thing to repr')
         self.assertEqualDiff("'a thing to repr' is not write locked but needs "

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2006-10-11 23:08:27 +0000
+++ b/bzrlib/tests/test_graph.py	2007-04-01 06:19:38 +0000
@@ -14,8 +14,9 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
+from bzrlib.errors import NotSubGraph
 from bzrlib.tests import TestCase
-from bzrlib.graph import node_distances, nodes_by_distance, Graph
+from bzrlib.graph import node_distances, nodes_by_distance, Graph, GraphDelta
 
 
 class TestBase(TestCase):
@@ -78,3 +79,21 @@
         # check the result contains ghosts:
         self.assertEqual({'ghost': {'rev1': 1}, 'rev1': {}},
                          graph.get_descendants())
+
+
+class TestGraphDelta(TestCase):
+
+    def testEmptyEmptyGraph(self):
+        graph_from = Graph()
+        graph_to = Graph()
+        delta = graph_to.changes_from(graph_from)
+        self.assertIsInstance(delta, GraphDelta)
+        new_to = graph_from.apply_changes(delta)
+        self.assertEqual(graph_to, new_to)
+
+    def testTargetNotSubGraph(self):
+        """When the target is not a sub-graph of the source, get an exception."""
+        graph_from = Graph()
+        graph_to = Graph()
+        graph_to.add_node('A', [])
+        self.assertRaises(NotSubGraph, graph_to.changes_from, graph_from)