Merge lp:~pedronis/u1db/whats_changed_sorted_last_edits into lp:u1db

[Samuele Pedroni]

have whats_changed return information about the generation of a change sorted, return only the last change for a given doc_id. (the idea is that it should be possible to make sync incremental by sending document across in the implied order)

[lp:~pedronis/u1db/whats_changed_sorted_last_edits]

147. By Samuele Pedroni on 2011-12-12

pep8 fix

[John A Meinel (jameinel)]

A few small comments, everything would be fine to land the way it is. Just some thoughts:

38 + cur_generation = len(self._transaction_log)
39 + changes = []
40 + relevant_tail = self._transaction_log[old_generation:]
41 + relevant_tail.reverse()

If we want to be in-memory race safe, then doing:

relevant_tail = self._transaction_log[old_generation:]
cur_generation = old_generation + len(relevant_tail)

In the SQL implementation, you use changes[0][1] which is also getting it from the queried data, rather than assuming things don't change.

Also, instead of relevant_tail.reverse() and then iterating, just do:

for doc_id in reversed(relevant_tail):

That generates a reverse iterator, rather than the O(n) for actually reversing each item in the list.

review: Approve

[lp:~pedronis/u1db/whats_changed_sorted_last_edits]

148. By Samuele Pedroni on 2011-12-13

suggested improvements

=== modified file 'u1db/__init__.py'
--- u1db/__init__.py	2011-12-06 20:13:48 +0000
+++ u1db/__init__.py	2011-12-13 09:31:23 +0000
@@ -47,17 +47,18 @@
     """
 
     def whats_changed(self, old_generation):
-        """Return a list of entries that have changed since old_generation.
+        """Return a list of documents that have changed since old_generation.
         This allows APPS to only store a db generation before going
         'offline', and then when coming back online they can use this
         data to update whatever extra data they are storing.
 
         :param old_generation: The generation of the database in the old
             state.
-        :return: (cur_generation, set([doc_id]))
-            The current generation of the database, and the set of
-            document ids that were changed in between old_generation and
-            cur_generation
+        :return: (cur_generation, [(doc_id, generation),...])
+            The current generation of the database, and a list of of
+            changed documents since old_generation, represented by tuples
+            with for each document its doc_id and the generation corresponding
+            to the last intervening change and sorted by generation
         """
         raise NotImplementedError(self.whats_changed)
 

=== modified file 'u1db/backends/inmemory.py'
--- u1db/backends/inmemory.py	2011-12-06 15:34:12 +0000
+++ u1db/backends/inmemory.py	2011-12-13 09:31:23 +0000
@@ -168,8 +168,18 @@
         return result
 
     def whats_changed(self, old_generation=0):
-        return (len(self._transaction_log),
-                set(self._transaction_log[old_generation:]))
+        changes = []
+        relevant_tail = self._transaction_log[old_generation:]
+        cur_generation = old_generation + len(relevant_tail)
+        seen = set()
+        generation = cur_generation
+        for doc_id in reversed(relevant_tail):
+            if doc_id not in seen:
+                changes.append((doc_id, generation))
+                seen.add(doc_id)
+            generation -= 1
+        changes.reverse()
+        return (cur_generation, changes)
 
     def force_doc_sync_conflict(self, doc):
         my_doc = self._get_doc(doc.doc_id)

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py	2011-12-06 20:13:48 +0000
+++ u1db/backends/sqlite_backend.py	2011-12-13 09:31:23 +0000
@@ -354,15 +354,20 @@
     def whats_changed(self, old_generation=0):
         c = self._db_handle.cursor()
         c.execute("SELECT generation, doc_id FROM transaction_log"
-                  " WHERE generation > ?", (old_generation,))
+                  " WHERE generation > ? ORDER BY generation DESC",
+                  (old_generation,))
         results = c.fetchall()
         cur_gen = old_generation
-        doc_ids = set()
-        for gen, doc_id in results:
-            if gen > cur_gen:
-                cur_gen = gen
-            doc_ids.add(doc_id)
-        return cur_gen, doc_ids
+        seen = set()
+        changes = []
+        for generation, doc_id in results:
+            if doc_id not in seen:
+                changes.append((doc_id, generation))
+                seen.add(doc_id)
+        if changes:
+            cur_gen = changes[0][1]  # max generation
+            changes.reverse()
+        return cur_gen, changes
 
     def delete_doc(self, doc):
         with self._db_handle:

=== modified file 'u1db/sync.py'
--- u1db/sync.py	2011-12-06 16:14:56 +0000
+++ u1db/sync.py	2011-12-13 09:31:23 +0000
@@ -92,7 +92,8 @@
         (other_replica_uid, other_gen,
          others_my_gen) = sync_target.get_sync_info(self.source._replica_uid)
         # what's changed since that generation and this current gen
-        my_gen, changed_doc_ids = self.source.whats_changed(others_my_gen)
+        my_gen, changes = self.source.whats_changed(others_my_gen)
+        changed_doc_ids = set(doc_id for doc_id, _ in changes)
         # prepare to send all the changed docs
         docs_to_send = self.source.get_docs(changed_doc_ids,
             check_for_conflicts=False)
@@ -169,7 +170,8 @@
             processing the returned documents.
         """
         self._last_known_generation = last_known_generation  # for tests
-        gen, changed_doc_ids = self._db.whats_changed(last_known_generation)
+        gen, changes = self._db.whats_changed(last_known_generation)
+        changed_doc_ids = set(doc_id for doc_id, _ in changes)
         self.new_gen = gen
         seen_ids = self.seen_ids
         # changed docs that weren't superseded by or converged with

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2011-12-06 15:34:12 +0000
+++ u1db/tests/test_backends.py	2011-12-13 09:31:23 +0000
@@ -341,13 +341,13 @@
         self.db.put_doc(doc)
         self.assertEqual([doc.doc_id, doc.doc_id],
                          self.db._get_transaction_log())
-        self.assertEqual((2, set([doc.doc_id])), self.db.whats_changed())
+        self.assertEqual((2, [(doc.doc_id, 2)]), self.db.whats_changed())
 
     def test_delete_updates_transaction_log(self):
         doc = self.db.create_doc(simple_doc)
         db_gen, _ = self.db.whats_changed()
         self.db.delete_doc(doc)
-        self.assertEqual((2, set([doc.doc_id])), self.db.whats_changed(db_gen))
+        self.assertEqual((2, [(doc.doc_id, 2)]), self.db.whats_changed(db_gen))
 
     def test_delete_then_put(self):
         doc = self.db.create_doc(simple_doc)
@@ -358,14 +358,23 @@
         self.assertGetDoc(self.db, doc.doc_id, doc.rev, nested_doc, False)
 
     def test_whats_changed_initial_database(self):
-        self.assertEqual((0, set()), self.db.whats_changed())
+        self.assertEqual((0, []), self.db.whats_changed())
 
     def test_whats_changed_returns_one_id_for_multiple_changes(self):
         doc = self.db.create_doc(simple_doc)
         doc.content = '{"new": "contents"}'
         self.db.put_doc(doc)
-        self.assertEqual((2, set([doc.doc_id])), self.db.whats_changed())
-        self.assertEqual((2, set()), self.db.whats_changed(2))
+        self.assertEqual((2, [(doc.doc_id, 2)]), self.db.whats_changed())
+        self.assertEqual((2, []), self.db.whats_changed(2))
+
+    def test_whats_changed_returns_last_edits_ascending(self):
+        doc = self.db.create_doc(simple_doc)
+        doc1 = self.db.create_doc(simple_doc)
+        doc.content = '{"new": "contents"}'
+        self.db.delete_doc(doc1)
+        self.db.put_doc(doc)
+        self.assertEqual((4, [(doc1.doc_id, 3), (doc.doc_id, 4)]),
+                         self.db.whats_changed())
 
 
 class DatabaseIndexTests(tests.DatabaseBaseTests):