Merge lp:~thisfred/u1db/c-nested_index into lp:u1db

[Eric Casteleijn]

Added support for nested indexes.

Added support for nested indexes.

[Eric Casteleijn (thisfred)]

This is a very rough attempt to get the tests to pass. Please turn review harshness up to 11, as there may be performance issues or even memory management bugs. I added some XXX comments where I had questions, which I'll remove once they're addressed.

[lp:~thisfred/u1db/c-nested_index]

222. By Eric Casteleijn on 2012-03-06

initialize

223. By Eric Casteleijn on 2012-03-06

strtok_r is threadsafe

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 3/6/2012 7:45 PM, Eric Casteleijn wrote:
> Eric Casteleijn has proposed merging
> lp:~thisfred/u1db/c-nested_index into lp:u1db.
>
> Requested reviews: John A Meinel (jameinel)
>
> For more details, see:
> https://code.launchpad.net/~thisfred/u1db/c-nested_index/+merge/96215
>
> Added support for nested indexes.

+ val = int(self.db._replica_uid, 16) # XXX missing assert?

The assert is effectively that a ValueError is not raised because uid
is a valid hex string.

You can put a comment to that fact if you prefer. The uid is going to
be random, so we can't assert what value it has, but we are asserting
that it is a hex string.

- - val = json_object_object_get(ctx->obj, expression);
+ tmp_expression = strdup(expression); // XXX: need to test for out
of mem?
+ result = strtok(tmp_expression, DOT); // XXX: strtok thread safety?
+ val = ctx->obj;
+ while (result != NULL) {
+ val = json_object_object_get(val, result);
+ result = strtok(NULL, DOT);
+ }
+ free(tmp_expression);

I'm not a big fan of strtok, because the state is kept within the
function, rather than being exposed and passed back.
Plus it mutates the buffer you're working with, etc. Though we
probably don't have much choice on the latter, because libjson doesn't
have a get that you can pass the length of the string (it has to be
null-terminated).

I see that you switched to strtok_r in a follow up patch that doesn't
show up in the email diff. Which I thought was a good idea from "man
strtok", except strtok_r doesn't exist for MSVC.. :(

It isn't particularly hard to write our own strtok_r, or even do the
parsing manually, since we don't need to support a set of characters,
just one. So strchr is a pretty easy substitute.

// Not actually tested:
tmp_expression = strdup(expression);
result = tmp_expression;
while (result != NULL) {
  dot_chr = strchr(result, '.');
  if (dot_chr != NULL) {
    *dot_chr = '\0';
    dot_chr ++;
  }
  val = json_object_object_get(val, result);
  result = dot_chr;
}
free(tmp_expression);

Oh, we'll also want to trap for 'val' become non-existent, I believe
[while (result != NULL && val != NULL)]. I think we need another test
case for:

def tested_nested_nonexistent(self):
  doc = self.db.create_doc(nested_doc)
  # sub exists, but sub.foo does not:
  self.db.create_index('test-idx', ['sub.foo'])
  self.assertEqual([], self.db.get_from_index('test-idx', [('*',)]))

I'm not 100% sure how json_object_object_get works for keys that don't
exist, but that's why we test it :).

This is the sort of test that *could* be a specific implementation
test, but it works well enough to be tested at the API level, and all
implementations shouldn't crash if an index requests an attribute that
doesn't exist.

Otherwise, I think this idea is pretty good.

 review: needsfixing

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk9XHJQACgkQJdeBCYSNAAPQsQCgrjWv7cKhyw/Uu4DZmXd6p0OH
pdMAoKsheZPbqs+r1pfNKLpQAQ6y3FV4
=oLyS
-----END PGP SIGNATURE-----

review: Needs Fixing

[Eric Casteleijn (thisfred)]

Thanks, will fix, when mulling this over last night I realized we only tested for the happy path, and it probably breaks horribly when the subfield does not exist.

[Eric Casteleijn (thisfred)]

The above test passes with the current code, because the final val being NULL was already caught by the

if (val != NULL)

below, so I added another test which looks for a value that is nested deeper, and that indeed blew up the code, which your proposed extra check fixed.

[lp:~thisfred/u1db/c-nested_index]

224. By Eric Casteleijn on 2012-03-07

removed use of strtok, added a test for nonexistent nested fields, and fixed the code so it doesn't blow up in the face of that

[John A Meinel (jameinel)]

138 + def tested_nested_nonexistent(self):
139 + doc = self.db.create_doc(nested_doc)
140 + # sub exists, but sub.foo does not:
141 + self.db.create_index('test-idx', ['sub.foo'])
142 + self.assertEqual([], self.db.get_from_index('test-idx', [('*',)]))
143 +
144 + def tested_nested_nonexistent(self):
145 + doc = self.db.create_doc(nested_doc)
146 + # sub exists, but sub.foo does not:
147 + self.db.create_index('test-idx', ['sub.foo.bar.baz.qux.fnord'])
148 + self.assertEqual([], self.db.get_from_index('test-idx', [('*',)]))

You have the test name duplicated. I don't know if you just want the second test, or if you want both of them. Otherwise this is good.

review: Needs Fixing

[Eric Casteleijn (thisfred)]

Oops, fixed.

[lp:~thisfred/u1db/c-nested_index]

225. By Eric Casteleijn on 2012-03-08

fixed test name

=== modified file 'src/u1db.c'
--- src/u1db.c	2012-03-07 08:07:40 +0000
+++ src/u1db.c	2012-03-08 13:47:22 +0000
@@ -355,15 +355,15 @@
     int status;
 
     if (is_update) {
-        status = sqlite3_prepare_v2(db->sql_handle, 
+        status = sqlite3_prepare_v2(db->sql_handle,
             "UPDATE document SET doc_rev = ?, content = ? WHERE doc_id = ?", -1,
-            &statement, NULL); 
+            &statement, NULL);
         if (status != SQLITE_OK) { goto finish; }
         status = delete_old_fields(db, doc_id);
     } else {
-        status = sqlite3_prepare_v2(db->sql_handle, 
+        status = sqlite3_prepare_v2(db->sql_handle,
             "INSERT INTO document (doc_rev, content, doc_id) VALUES (?, ?, ?)", -1,
-            &statement, NULL); 
+            &statement, NULL);
     }
     if (status != SQLITE_OK) {
         return status;
@@ -386,7 +386,7 @@
     sqlite3_finalize(statement);
     if (status != SQLITE_OK) { goto finish; }
     status = u1db__update_indexes(db, doc_id, content);
-    status = sqlite3_prepare_v2(db->sql_handle, 
+    status = sqlite3_prepare_v2(db->sql_handle,
         "INSERT INTO transaction_log(doc_id) VALUES (?)", -1,
         &statement, NULL);
     if (status != SQLITE_OK) {
@@ -414,9 +414,9 @@
     sqlite3_stmt *statement;
     int status;
 
-    status = sqlite3_prepare_v2(db->sql_handle, 
+    status = sqlite3_prepare_v2(db->sql_handle,
         "SELECT 1 FROM conflicts WHERE doc_id = ? LIMIT 1", -1,
-        &statement, NULL); 
+        &statement, NULL);
     if (status != SQLITE_OK) {
         return status;
     }
@@ -446,9 +446,9 @@
     sqlite3_stmt *statement;
     int status;
 
-    status = sqlite3_prepare_v2(db->sql_handle, 
+    status = sqlite3_prepare_v2(db->sql_handle,
         "INSERT INTO conflicts VALUES (?, ?, ?)", -1,
-        &statement, NULL); 
+        &statement, NULL);
     if (status != SQLITE_OK) {
         return status;
     }
@@ -1223,7 +1223,7 @@
     if (result == NULL) {
         return NULL;
     }
-    status = sqlite3_prepare_v2(db->sql_handle, sql, n, &statement, NULL); 
+    status = sqlite3_prepare_v2(db->sql_handle, sql, n, &statement, NULL);
     if (status != SQLITE_OK) {
         result->status = status;
         return result;
@@ -1592,9 +1592,9 @@
     if (db == NULL || index_name == NULL) {
         return U1DB_INVALID_PARAMETER;
     }
-    status = sqlite3_prepare_v2(db->sql_handle, 
+    status = sqlite3_prepare_v2(db->sql_handle,
         "DELETE FROM index_definitions WHERE name = ?", -1,
-        &statement, NULL); 
+        &statement, NULL);
     if (status != SQLITE_OK) { goto finish; }
     status = sqlite3_bind_text(statement, 1, index_name, -1, SQLITE_TRANSIENT);
     if (status != SQLITE_OK) { goto finish; }

=== modified file 'src/u1db_query.c'
--- src/u1db_query.c	2012-03-08 08:08:27 +0000
+++ src/u1db_query.c	2012-03-08 13:47:22 +0000
@@ -360,12 +360,28 @@
     json_object *val;
     const char *str_val;
     int status = U1DB_OK;
+    char *result = NULL;
+    char *tmp_expression = NULL;
+    char *progress = NULL;
+    char *dot_chr = NULL;
 
     ctx = (struct evaluate_index_context *)context;
     if (ctx->obj == NULL || !json_object_is_type(ctx->obj, json_type_object)) {
         return U1DB_INVALID_JSON;
     }
-    val = json_object_object_get(ctx->obj, expression);
+    tmp_expression = strdup(expression);
+    result = tmp_expression;
+    val = ctx->obj;
+    while (result != NULL && val != NULL) {
+        dot_chr = strchr(result, '.');
+        if (dot_chr != NULL) {
+            *dot_chr = '\0';
+            dot_chr++;
+        }
+        val = json_object_object_get(val, result);
+        result = dot_chr;
+    }
+    free(tmp_expression);
     if (val != NULL) {
         str_val = json_object_get_string(val);
         if (str_val != NULL) {

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2012-03-06 12:51:24 +0000
+++ u1db/tests/test_backends.py	2012-03-08 13:47:22 +0000
@@ -348,6 +348,7 @@
         self.assertEqual([no_conflict_doc, doc2],
                          self.db.get_docs([doc1.doc_id, doc2.doc_id],
                                           check_for_conflicts=False))
+
     def test_get_doc_conflicts(self):
         doc = self.db.create_doc(simple_doc)
         alt_doc = self.make_document(doc.doc_id, 'alternate:1', nested_doc)
@@ -713,9 +714,6 @@
         self.assertEqual(sorted([doc1, doc2, doc3]),
             sorted(self.db.get_from_index('test-idx', [("v1", "*")])))
 
-
-class PyDatabaseIndexTests(tests.DatabaseBaseTests):
-
     def test_nested_index(self):
         doc = self.db.create_doc(nested_doc)
         self.db.create_index('test-idx', ['sub.doc'])
@@ -726,6 +724,21 @@
             sorted([doc, doc2]),
             sorted(self.db.get_from_index('test-idx', [('underneath',)])))
 
+    def test_nested_nonexistent(self):
+        doc = self.db.create_doc(nested_doc)
+        # sub exists, but sub.foo does not:
+        self.db.create_index('test-idx', ['sub.foo'])
+        self.assertEqual([], self.db.get_from_index('test-idx', [('*',)]))
+
+    def test_nested_nonexistent2(self):
+        doc = self.db.create_doc(nested_doc)
+        # sub exists, but sub.foo does not:
+        self.db.create_index('test-idx', ['sub.foo.bar.baz.qux.fnord'])
+        self.assertEqual([], self.db.get_from_index('test-idx', [('*',)]))
+
+
+class PyDatabaseIndexTests(tests.DatabaseBaseTests):
+
     def test_get_from_index_case_sensitive(self):
         self.db.create_index('test-idx', ['key'])
         doc1 = self.db.create_doc(simple_doc)
@@ -837,8 +850,10 @@
         new_content = '{"key": "altval"}'
         other_rev = 'test:1|z:2'
         st = self.db.get_sync_target()
+
         def ignore(doc_id, doc_rev, doc):
             pass
+
         doc_other = self.make_document(doc.doc_id, other_rev, new_content)
         docs_by_gen = [(doc_other, 10)]
         result = st.sync_exchange(docs_by_gen, 'other-replica',

=== modified file 'u1db/tests/test_c_backend.py'
--- u1db/tests/test_c_backend.py	2012-03-07 13:09:34 +0000
+++ u1db/tests/test_c_backend.py	2012-03-08 13:47:22 +0000
@@ -79,6 +79,7 @@
         self.db = c_backend_wrapper.CDatabase(':memory:')
         self.assertIsNot(None, self.db._replica_uid)
         self.assertEqual(32, len(self.db._replica_uid))
+        # casting to an int from the uid *is* the check for correct behavior.
         val = int(self.db._replica_uid, 16)
 
     def test_get_conflicts_with_borked_data(self):
@@ -102,11 +103,6 @@
         self.db = c_backend_wrapper.CDatabase(':memory:')
         doc = self.db.create_doc(tests.nested_doc)
         self.db.create_index("multi-idx", ["key", "sub.doc"])
-        # TODO: The current backend doesn't support nested fields, so we push
-        #       that data in manually.
-        self.db._run_sql("INSERT INTO document_fields"
-                         " VALUES ('%s', 'sub.doc', 'underneath')"
-                         % (doc.doc_id,))
         docs = self.db.get_from_index('multi-idx', [('value', 'underneath')])
         self.assertEqual([doc], docs)