Rev 2630: Create an InMemoryGraphIndex for temporary indexing. in http://people.ubuntu.com/~robertc/baz2.0/index

[Robert Collins]

At http://people.ubuntu.com/~robertc/baz2.0/index

------------------------------------------------------------
revno: 2630
revision-id: robertc at robertcollins.net-20070714072312-alys3q6a5211eegq
parent: robertc at robertcollins.net-20070714060702-fnpyy4ogd1q8zzpt
committer: Robert Collins <robertc at robertcollins.net>
branch nick: index
timestamp: Sat 2007-07-14 17:23:12 +1000
message:
  Create an InMemoryGraphIndex for temporary indexing.
modified:
  bzrlib/index.py                index.py-20070712131115-lolkarso50vjr64s-1
  bzrlib/tests/test_index.py     test_index.py-20070712131115-lolkarso50vjr64s-2
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py	2007-07-14 06:07:02 +0000
+++ b/bzrlib/index.py	2007-07-14 07:23:12 +0000
@@ -16,7 +16,12 @@
 
 """Indexing facilities."""
 
-__all__ = ['CombinedGraphIndex', 'GraphIndex', 'GraphIndexBuilder']
+__all__ = [
+    'CombinedGraphIndex',
+    'GraphIndex',
+    'GraphIndexBuilder',
+    'InMemoryGraphIndex',
+    ]
 
 from cStringIO import StringIO
 import re
@@ -74,15 +79,17 @@
             raise errors.BadIndexValue(value)
         if len(references) != self.reference_lists:
             raise errors.BadIndexValue(references)
+        node_refs = []
         for reference_list in references:
             for reference in reference_list:
                 if _whitespace_re.search(reference) is not None:
                     raise errors.BadIndexKey(reference)
                 if reference not in self._nodes:
-                    self._nodes[reference] = ('a', [], '')
+                    self._nodes[reference] = ('a', (), '')
+            node_refs.append(tuple(reference_list))
         if key in self._nodes and self._nodes[key][0] == '':
             raise errors.BadIndexDuplicateKey(key, self)
-        self._nodes[key] = ('', references, value)
+        self._nodes[key] = ('', tuple(node_refs), value)
 
     def finish(self):
         lines = [_SIGNATURE]
@@ -321,3 +328,48 @@
         """Validate that everything in the index can be accessed."""
         for index in self._indices:
             index.validate()
+
+
+class InMemoryGraphIndex(GraphIndexBuilder):
+    """A GraphIndex which operates entirely out of memory and is mutable.
+
+    This is designed to allow the accumulation of GraphIndex entries during a
+    single write operation, where the accumulated entries need to be immediately
+    available - for example via a CombinedGraphIndex.
+    """
+
+    def add_nodes(self, nodes):
+        """Add nodes to the index.
+
+        :param nodes: An iterable of (key, node_refs, value) entries to add.
+        """
+        for (key, node_refs, value) in nodes:
+            self.add_node(key, node_refs, value)
+
+    def iter_all_entries(self):
+        """Iterate over all keys within the index
+
+        :return: An iterable of (key, reference_lists, value). There is no
+            defined order for the result iteration - it will be in the most
+            efficient order for the index (in this case dictionary hash order).
+        """
+        for key, (absent, references, value) in self._nodes.iteritems():
+            if not absent:
+                yield key, references, value
+
+    def iter_entries(self, keys):
+        """Iterate over keys within the index.
+
+        :param keys: An iterable providing the keys to be retrieved.
+        :return: An iterable of (key, reference_lists, value). There is no
+            defined order for the result iteration - it will be in the most
+            efficient order for the index (keys iteration order in this case).
+        """
+        keys = set(keys)
+        for key in keys.intersection(self._nodes):
+            node = self._nodes[key]
+            if not node[0]:
+                yield key, node[1], node[2]
+
+    def validate(self):
+        """In memory index's have no known corruption at the moment."""

=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py	2007-07-14 06:07:02 +0000
+++ b/bzrlib/tests/test_index.py	2007-07-14 07:23:12 +0000
@@ -17,7 +17,7 @@
 """Tests for indices."""
 
 from bzrlib import errors
-from bzrlib.index import CombinedGraphIndex, GraphIndexBuilder, GraphIndex
+from bzrlib.index import *
 from bzrlib.tests import TestCaseWithMemoryTransport
 
 
@@ -445,3 +445,73 @@
     def test_validate_empty(self):
         index = CombinedGraphIndex([])
         index.validate()
+
+
+class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
+
+    def make_index(self, ref_lists=0, nodes=[]):
+        result = InMemoryGraphIndex(ref_lists)
+        result.add_nodes(nodes)
+        return result
+
+    def test_add_nodes(self):
+        index = self.make_index(1)
+        index.add_nodes([('name', ([],), 'data')])
+        index.add_nodes([('name2', ([],), ''), ('name3', (['r'],), '')])
+        self.assertEqual(set([
+            ('name', ((),), 'data'),
+            ('name2', ((),), ''),
+            ('name3', (('r',),), ''),
+            ]), set(index.iter_all_entries()))
+
+    def test_iter_all_entries_empty(self):
+        index = self.make_index()
+        self.assertEqual([], list(index.iter_all_entries()))
+
+    def test_iter_all_entries_simple(self):
+        index = self.make_index(nodes=[('name', (), 'data')])
+        self.assertEqual([('name', (), 'data')],
+            list(index.iter_all_entries()))
+
+    def test_iter_all_entries_references(self):
+        index = self.make_index(1, nodes=[
+            ('name', (['ref'], ), 'data'),
+            ('ref', ([], ), 'refdata')])
+        self.assertEqual(set([('name', (('ref',),), 'data'),
+            ('ref', ((), ), 'refdata')]),
+            set(index.iter_all_entries()))
+
+    def test_iteration_absent_skipped(self):
+        index = self.make_index(1, nodes=[
+            ('name', (['ref'], ), 'data')])
+        self.assertEqual(set([('name', (('ref',),), 'data')]),
+            set(index.iter_all_entries()))
+        self.assertEqual(set([('name', (('ref',),), 'data')]),
+            set(index.iter_entries(['name'])))
+        self.assertEqual([], list(index.iter_entries(['ref'])))
+
+    def test_iter_all_keys(self):
+        index = self.make_index(1, nodes=[
+            ('name', (['ref'], ), 'data'),
+            ('ref', ([], ), 'refdata')])
+        self.assertEqual(set([('name', (('ref',),), 'data'),
+            ('ref', ((), ), 'refdata')]),
+            set(index.iter_entries(['name', 'ref'])))
+
+    def test_iter_nothing_empty(self):
+        index = self.make_index()
+        self.assertEqual([], list(index.iter_entries([])))
+
+    def test_iter_missing_entry_empty(self):
+        index = self.make_index()
+        self.assertEqual([], list(index.iter_entries(['a'])))
+
+    def test_validate_empty(self):
+        index = self.make_index()
+        index.validate()
+
+    def test_validate_no_refs_content(self):
+        index = self.make_index(nodes=[('key', (), 'value')])
+        index.validate()
+
+