Fix index validation for nested $and (#1014)

mango_selector:has_required_fields checks that a list of
indexed fields is covered by a given selector. The implementation
recurses through the selector, tracking fields that encounters.

Unfortunately, this skipped peers of combination operators. For
example,

"selector": {
	"$and":[
		"$and":[
			"A": "foo"
		],
		"$and":[
			"B": "bar"
		]
	]
}

would skip the first nested "$and" operator and only return "B"
as a covered field.

This commit explicitly handles this situation (the only combination
operator we care about is $and), so for the above selector we
would correctly indentify "A" and "B" as covered fields.

2 files changed, 54 insertions, 13 deletions

diff --git a/src/mango/src/mango_selector.erl b/src/mango/src/mango_selector.erl
index 4ff36945a..2a546c9ba 100644
--- a/src/mango/src/mango_selector.erl
+++ b/src/mango/src/mango_selector.erl
@@ -578,36 +578,46 @@ match({[_, _ | _] = _Props} = Sel, _Value, _Cmp) ->
 % until we match then all or run out of selector to
 % match against.
 
+has_required_fields(Selector, RequiredFields) ->
+    Remainder = has_required_fields_int(Selector, RequiredFields),
+    Remainder == [].
+
 % Empty selector
-has_required_fields({[]}, _) ->
-    false;
+has_required_fields_int({[]}, Remainder) ->
+    Remainder;
 
 % No more required fields
-has_required_fields(_, []) ->
-    true;
+has_required_fields_int(_, []) ->
+    [];
 
 % No more selector
-has_required_fields([], _) ->
-    false;
+has_required_fields_int([], Remainder) ->
+    Remainder;
 
-has_required_fields(Selector, RequiredFields) when not is_list(Selector) ->
-    has_required_fields([Selector], RequiredFields);
+has_required_fields_int(Selector, RequiredFields) when not is_list(Selector) ->
+    has_required_fields_int([Selector], RequiredFields);
 
 % We can "see" through $and operator. We ignore other
 % combination operators because they can't be used to restrict
 % an index.
-has_required_fields([{[{<<"$and">>, Args}]}], RequiredFields) 
+has_required_fields_int([{[{<<"$and">>, Args}]}], RequiredFields) 
+        when is_list(Args) ->
+    has_required_fields_int(Args, RequiredFields);
+
+% Handle $and operator where it has peers
+has_required_fields_int([{[{<<"$and">>, Args}]} | Rest], RequiredFields) 
         when is_list(Args) ->
-    has_required_fields(Args, RequiredFields);
+    Remainder = has_required_fields_int(Args, RequiredFields),
+    has_required_fields_int(Rest, Remainder);
 
-has_required_fields([{[{Field, Cond}]} | Rest], RequiredFields) ->
+has_required_fields_int([{[{Field, Cond}]} | Rest], RequiredFields) ->
     case Cond of
         % $exists:false is a special case - this is the only operator
         % that explicitly does not require a field to exist
         {[{<<"$exists">>, false}]} ->
-            has_required_fields(Rest, RequiredFields);
+            has_required_fields_int(Rest, RequiredFields);
         _ ->
-            has_required_fields(Rest, lists:delete(Field, RequiredFields))
+            has_required_fields_int(Rest, lists:delete(Field, RequiredFields))
     end.
 
 
@@ -651,6 +661,27 @@ has_required_fields_and_true_test() ->
     Normalized = normalize(Selector),
     ?assertEqual(true, has_required_fields(Normalized, RequiredFields)).
 
+has_required_fields_nested_and_true_test() ->
+    RequiredFields = [<<"A">>, <<"B">>],
+    Selector1 = {[{<<"$and">>,
+          [
+              {[{<<"A">>, <<"foo">>}]}
+          ]
+    }]},
+    Selector2 = {[{<<"$and">>,
+          [
+              {[{<<"B">>, <<"foo">>}]}
+          ]
+    }]},
+    Selector = {[{<<"$and">>,
+          [
+              Selector1,
+              Selector2
+          ]
+    }]},
+
+    ?assertEqual(true, has_required_fields(Selector, RequiredFields)).
+
 has_required_fields_and_false_test() ->
     RequiredFields = [<<"A">>, <<"C">>],
     Selector = {[{<<"$and">>,
diff --git a/src/mango/test/05-index-selection-test.py b/src/mango/test/05-index-selection-test.py
index fe36257e3..f8cc82576 100644
--- a/src/mango/test/05-index-selection-test.py
+++ b/src/mango/test/05-index-selection-test.py
@@ -28,6 +28,16 @@ class IndexSelectionTests:
             }, explain=True)
         self.assertEqual(resp["index"]["type"], "json")
 
+    def test_with_nested_and(self):
+        resp = self.db.find({
+                "name.first": {
+                    "$gt": "a",
+                    "$lt": "z"
+                },
+                "name.last": "Foo"
+            }, explain=True)
+        self.assertEqual(resp["index"]["type"], "json")
+
     def test_use_most_columns(self):
         # ddoc id for the age index
         ddocid = "_design/ad3d537c03cd7c6a43cf8dff66ef70ea54c2b40f"