[PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Kirill Shcherbatov]

Introduced a new JSON_TOKEN_ANY json token that makes possible to
perform anonymous lookup in marked tree nodes. This feature is
required to implement multikey indexes.
Since the token entered into the parser becomes available to user,
additional server-side check is introduced so that an error
occurs when trying to create a multikey index.

Needed for #1260

With the introduction of multikey indexes, the key_parts_are_compatible
function will not change significantly: here
https://gist.github.com/kshcherbatov/c0e48138fc16678ad9a82646f00c1881
you can see how the check is made that the multikey indexes are compatible
with each other.

https://github.com/tarantool/tarantool/tree/kshch/gh-1257-multikey-index-json-any-token
https://github.com/tarantool/tarantool/issues/1257
---
 src/box/index_def.c       | 60 +++++++++++++++++++++++++++++++++------
 src/lib/json/json.c       | 38 +++++++++++++++++++------
 src/lib/json/json.h       | 21 ++++++++++++--
 test/engine/json.result   | 21 ++++++++++++++
 test/engine/json.test.lua |  8 ++++++
 test/unit/json.c          | 52 +++++++++++++++++++++++++++++----
 test/unit/json.result     | 10 +++++--
 7 files changed, 184 insertions(+), 26 deletions(-)

diff --git a/src/box/index_def.c b/src/box/index_def.c
index 6c37f9f1d..0f99f1759 100644
--- a/src/box/index_def.c
+++ b/src/box/index_def.c
@@ -244,6 +244,56 @@ index_def_cmp(const struct index_def *key1, const struct index_def *key2)
 			    key2->key_def->parts, key2->key_def->part_count);
 }
 
+/**
+ * Test whether key_parts a and b are compatible:
+ *  + field numbers are differ OR
+ *  + json paths are differ
+ * Also perform integrity check: parts must not define multikey
+ * index.
+ */
+static bool
+key_parts_are_compatible(struct key_part *a, struct key_part *b,
+			 struct index_def *index_def, const char *space_name)
+{
+	if (a->fieldno != b->fieldno)
+		return true;
+	struct json_lexer lexer_a, lexer_b;
+	json_lexer_create(&lexer_a, a->path, a->path_len, TUPLE_INDEX_BASE);
+	json_lexer_create(&lexer_b, b->path, b->path_len, TUPLE_INDEX_BASE);
+	struct json_token token_a, token_b;
+	/* For the sake of json_token_cmp(). */
+	token_a.parent = NULL;
+	token_b.parent = NULL;
+	int a_rc, b_rc;
+	int token_idx = 0,  differ_token_idx = 0;
+	int a_multikey_rank = 0, b_multikey_rank = 0;
+	while ((a_rc = json_lexer_next_token(&lexer_a, &token_a)) == 0 &&
+	       (b_rc = json_lexer_next_token(&lexer_b, &token_b)) == 0 &&
+	       token_a.type != JSON_TOKEN_END &&
+	       token_b.type != JSON_TOKEN_END) {
+		token_idx++;
+		if (differ_token_idx == 0) {
+			if (json_token_cmp(&token_a, &token_b) != 0)
+				differ_token_idx = token_idx;
+		}
+		if (token_a.type == JSON_TOKEN_ANY)
+			a_multikey_rank = token_idx;
+		if (token_b.type == JSON_TOKEN_ANY)
+			b_multikey_rank = token_idx;
+	}
+	if (a_multikey_rank > 0 || b_multikey_rank > 0) {
+		diag_set(ClientError, ER_MODIFY_INDEX,
+			 index_def->name, space_name,
+			 "multikey index feature is not supported yet");
+		return false;
+	}
+	if (differ_token_idx > 0 || token_b.type != token_a.type)
+		return true;
+	diag_set(ClientError, ER_MODIFY_INDEX, index_def->name, space_name,
+		"same key part is indexed twice");
+	return false;
+}
+
 bool
 index_def_is_valid(struct index_def *index_def, const char *space_name)
 
@@ -282,15 +332,9 @@ index_def_is_valid(struct index_def *index_def, const char *space_name)
 			 */
 			struct key_part *part_a = &index_def->key_def->parts[i];
 			struct key_part *part_b = &index_def->key_def->parts[j];
-			if (part_a->fieldno == part_b->fieldno &&
-			    json_path_cmp(part_a->path, part_a->path_len,
-					  part_b->path, part_b->path_len,
-					  TUPLE_INDEX_BASE) == 0) {
-				diag_set(ClientError, ER_MODIFY_INDEX,
-					 index_def->name, space_name,
-					 "same key part is indexed twice");
+			if (!key_parts_are_compatible(part_a, part_b, index_def,
+						      space_name))
 				return false;
-			}
 		}
 	}
 	return true;
diff --git a/src/lib/json/json.c b/src/lib/json/json.c
index 1b1a3ec2c..019917825 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -146,18 +146,25 @@ json_parse_integer(struct json_lexer *lexer, struct json_token *token)
 	int len = 0;
 	int value = 0;
 	char c = *pos;
-	if (! isdigit(c))
-		return lexer->symbol_count + 1;
+	if (!isdigit(c)) {
+		if (c != '*')
+			return lexer->symbol_count + 1;
+		token->type = JSON_TOKEN_ANY;
+		++len;
+		++pos;
+		goto end;
+	}
 	do {
 		value = value * 10 + c - (int)'0';
 		++len;
 	} while (++pos < end && isdigit((c = *pos)));
 	if (value < lexer->index_base)
 		return lexer->symbol_count + 1;
-	lexer->offset += len;
-	lexer->symbol_count += len;
 	token->type = JSON_TOKEN_NUM;
 	token->num = value - lexer->index_base;
+end:
+	lexer->offset += len;
+	lexer->symbol_count += len;
 	return 0;
 }
 
@@ -252,10 +259,7 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 	}
 }
 
-/**
- * Compare JSON token keys.
- */
-static int
+int
 json_token_cmp(const struct json_token *a, const struct json_token *b)
 {
 	if (a->parent != b->parent)
@@ -270,7 +274,7 @@ json_token_cmp(const struct json_token *a, const struct json_token *b)
 	} else if (a->type == JSON_TOKEN_NUM) {
 		ret = a->num - b->num;
 	} else {
-		unreachable();
+		assert(a->type == JSON_TOKEN_ANY);
 	}
 	return ret;
 }
@@ -332,6 +336,9 @@ json_token_snprint(char *buf, int size, const struct json_token *token,
 	case JSON_TOKEN_STR:
 		len = snprintf(buf, size, "[\"%.*s\"]", token->len, token->str);
 		break;
+	case JSON_TOKEN_ANY:
+		len = snprintf(buf, size, "[*]");
+		break;
 	default:
 		unreachable();
 	}
@@ -420,6 +427,9 @@ json_token_hash(struct json_token *token)
 	} else if (token->type == JSON_TOKEN_NUM) {
 		data = &token->num;
 		data_size = sizeof(token->num);
+	} else if (token->type == JSON_TOKEN_ANY) {
+		data = "*";
+		data_size = 1;
 	} else {
 		unreachable();
 	}
@@ -435,6 +445,7 @@ json_tree_create(struct json_tree *tree)
 	tree->root.type = JSON_TOKEN_END;
 	tree->root.max_child_idx = -1;
 	tree->root.sibling_idx = -1;
+	tree->root.is_multikey = false;
 	tree->hash = mh_json_new();
 	return tree->hash == NULL ? -1 : 0;
 }
@@ -479,11 +490,14 @@ json_tree_add(struct json_tree *tree, struct json_token *parent,
 	      struct json_token *token)
 {
 	assert(json_tree_lookup(tree, parent, token) == NULL);
+	assert(token->type != JSON_TOKEN_ANY ||
+	       (!parent->is_multikey && json_token_is_leaf(parent)));
 	token->parent = parent;
 	token->children = NULL;
 	token->children_capacity = 0;
 	token->max_child_idx = -1;
 	token->hash = json_token_hash(token);
+	token->is_multikey = false;
 	int insert_idx = token->type == JSON_TOKEN_NUM ?
 			 (int)token->num : parent->max_child_idx + 1;
 	/*
@@ -520,6 +534,8 @@ json_tree_add(struct json_tree *tree, struct json_token *parent,
 	assert(parent->children[insert_idx] == NULL);
 	parent->children[insert_idx] = token;
 	parent->max_child_idx = MAX(parent->max_child_idx, insert_idx);
+	if (token->type == JSON_TOKEN_ANY)
+		parent->is_multikey = true;
 	token->sibling_idx = insert_idx;
 	assert(json_tree_lookup(tree, parent, token) == token);
 	return 0;
@@ -532,11 +548,15 @@ json_tree_del(struct json_tree *tree, struct json_token *token)
 	assert(token->sibling_idx >= 0);
 	assert(parent->children[token->sibling_idx] == token);
 	assert(json_tree_lookup(tree, parent, token) == token);
+	assert(token->type != JSON_TOKEN_ANY ||
+	       (parent->is_multikey && parent->max_child_idx == 0));
 	/*
 	 * Clear the entry corresponding to this token in parent's
 	 * children array and update max_child_idx if necessary.
 	 */
 	parent->children[token->sibling_idx] = NULL;
+	if (token->type == JSON_TOKEN_ANY)
+		parent->is_multikey = false;
 	token->sibling_idx = -1;
 	while (parent->max_child_idx >= 0 &&
 	       parent->children[parent->max_child_idx] == NULL)
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index 66cddd026..ff4ab7d91 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -66,6 +66,7 @@ struct json_lexer {
 enum json_token_type {
 	JSON_TOKEN_NUM,
 	JSON_TOKEN_STR,
+	JSON_TOKEN_ANY,
 	/** Lexer reached end of path. */
 	JSON_TOKEN_END,
 };
@@ -113,6 +114,10 @@ struct json_token {
 	 * a JSON tree root.
 	 */
 	int sibling_idx;
+	/**
+	 * True when it has the only child token JSON_TOKEN_ANY.
+	 */
+	bool is_multikey;
 	/**
 	 * Hash value of the token. Used for lookups in a JSON tree.
 	 * For more details, see the comment to json_tree::hash.
@@ -236,6 +241,12 @@ json_lexer_create(struct json_lexer *lexer, const char *src, int src_len,
 int
 json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
 
+/**
+ * Compare JSON token keys.
+ */
+int
+json_token_cmp(const struct json_token *a, const struct json_token *b);
+
 /**
  * Compare two JSON paths using Lexer class.
  * - in case of paths that have same token-sequence prefix,
@@ -307,10 +318,16 @@ json_tree_lookup(struct json_tree *tree, struct json_token *parent,
 		 const struct json_token *token)
 {
 	struct json_token *ret = NULL;
+	if (unlikely(parent->is_multikey &&
+		     (token->type == JSON_TOKEN_NUM ||
+		      token->type == JSON_TOKEN_ANY))) {
+		assert(parent->max_child_idx == 0);
+		return parent->children[0];
+	}
 	if (likely(token->type == JSON_TOKEN_NUM)) {
-		ret = (int)token->num < parent->children_capacity ?
+		ret = token->num <= parent->max_child_idx ?
 		      parent->children[token->num] : NULL;
-	} else {
+	} else if (token->type == JSON_TOKEN_STR) {
 		ret = json_tree_lookup_slowpath(tree, parent, token);
 	}
 	return ret;
diff --git a/test/engine/json.result b/test/engine/json.result
index 1bac85edd..e280a770c 100644
--- a/test/engine/json.result
+++ b/test/engine/json.result
@@ -683,3 +683,24 @@ town:select()
 s:drop()
 ---
 ...
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+---
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[1].a'}, {3, 'str', path = '["FIO"][*]["fname"][*].b'}}})
+---
+- error: 'Can''t create or modify index ''idx'' in space ''withdata'': multikey index
+    feature is not supported yet'
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[*].a'}, {3, 'str', path = '["FIO"][*]["fname"][*].b'}}})
+---
+- error: 'Can''t create or modify index ''idx'' in space ''withdata'': multikey index
+    feature is not supported yet'
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[1].a'}, {3, 'str', path = '["FIO"][*]["fname"][2].b'}}})
+---
+- error: 'Can''t create or modify index ''idx'' in space ''withdata'': multikey index
+    feature is not supported yet'
+...
diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
index 9afa3daa2..ef554247e 100644
--- a/test/engine/json.test.lua
+++ b/test/engine/json.test.lua
@@ -192,3 +192,11 @@ town:select()
 name:drop()
 town:select()
 s:drop()
+
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[1].a'}, {3, 'str', path = '["FIO"][*]["fname"][*].b'}}})
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[*].a'}, {3, 'str', path = '["FIO"][*]["fname"][*].b'}}})
+idx = s:create_index('idx', {parts = {{3, 'str', path = 'FIO[*].fname[1].a'}, {3, 'str', path = '["FIO"][*]["fname"][2].b'}}})
diff --git a/test/unit/json.c b/test/unit/json.c
index 6448a3210..8b141f54a 100644
--- a/test/unit/json.c
+++ b/test/unit/json.c
@@ -211,7 +211,7 @@ void
 test_tree()
 {
 	header();
-	plan(58);
+	plan(63);
 
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
@@ -411,6 +411,41 @@ test_tree()
 	   "last node became interm - it can't be leaf anymore");
 	is(json_token_is_leaf(&records[3].node), true, "last node is leaf");
 
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node, node_tmp)
+		json_tree_del(&tree, &node->node);
+
+	/* Test multikey tokens. */
+	records_idx = 0;
+	char *path_multikey = "[*][\"data\"]";
+	node = test_add_path(&tree, path_multikey, strlen(path_multikey),
+			     records, &records_idx);
+	is(node, &records[1], "add path '%s'", path_multikey);
+
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path_multikey,
+					   strlen(path_multikey), INDEX_BASE,
+					   struct test_struct, node);
+	is(node, &records[1], "lookup path '%s'", path_multikey);
+
+	token = &records[records_idx++].node;
+	token->type = JSON_TOKEN_NUM;
+	token->num = 3;
+	node = json_tree_lookup_entry(&tree, &tree.root, token,
+				      struct test_struct, node);
+	is(node, &records[0], "lookup numeric token in multikey node");
+
+	token->type = JSON_TOKEN_ANY;
+	node = json_tree_lookup_entry(&tree, &tree.root, token,
+				      struct test_struct, node);
+	is(node, &records[0], "lookup any token in multikey node");
+
+	token->type = JSON_TOKEN_STR;
+	token->str = "invalid";
+	token->len = strlen("invalid");
+	node = json_tree_lookup_entry(&tree, &tree.root, token,
+				      struct test_struct, node);
+	is(node, NULL, "lookup string token in multikey node");
+
 	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
 				     node, node_tmp)
 		json_tree_del(&tree, &node->node);
@@ -433,7 +468,7 @@ test_path_cmp()
 		{"Data[1][\"Info\"].fname[1]", -1},
 	};
 	header();
-	plan(lengthof(rc) + 2);
+	plan(lengthof(rc) + 3);
 	for (size_t i = 0; i < lengthof(rc); ++i) {
 		const char *path = rc[i].path;
 		int errpos = rc[i].errpos;
@@ -450,6 +485,13 @@ test_path_cmp()
 	ret = json_path_validate(invalid, strlen(invalid), INDEX_BASE);
 	is(ret, 6, "path %s error pos %d expected %d", invalid, ret, 6);
 
+	char *multikey_a = "Data[*][\"FIO\"].fname[*]";
+	char *multikey_b = "[\"Data\"][*].FIO[\"fname\"][*]";
+	ret = json_path_cmp(multikey_a, strlen(multikey_a), multikey_b,
+			    strlen(multikey_b), INDEX_BASE);
+	is(ret, 0, "path cmp result \"%s\" with \"%s\": have %d, expected %d",
+	   multikey_a, multikey_b, ret, 0);
+
 	check_plan();
 	footer();
 }
@@ -463,14 +505,14 @@ test_path_snprint()
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
 	fail_if(rc != 0);
-	struct test_struct records[5];
-	const char *path = "[1][20][\"file\"][8]";
+	struct test_struct records[6];
+	const char *path = "[1][*][20][\"file\"][8]";
 	int path_len = strlen(path);
 
 	int records_idx = 0;
 	struct test_struct *node, *node_tmp;
 	node = test_add_path(&tree, path, path_len, records, &records_idx);
-	fail_if(&node->node != &records[3].node);
+	fail_if(&node->node != &records[4].node);
 
 	char buf[64];
 	int bufsz = sizeof(buf);
diff --git a/test/unit/json.result b/test/unit/json.result
index ee54cbe0e..8a6c7db73 100644
--- a/test/unit/json.result
+++ b/test/unit/json.result
@@ -101,7 +101,7 @@ ok 1 - subtests
 ok 2 - subtests
 	*** test_errors: done ***
 	*** test_tree ***
-    1..58
+    1..63
     ok 1 - add path '[1][10]'
     ok 2 - add path '[1][20].file'
     ok 3 - add path '[1][20].file[2]'
@@ -160,10 +160,15 @@ ok 2 - subtests
     ok 56 - last node is leaf
     ok 57 - last node became interm - it can't be leaf anymore
     ok 58 - last node is leaf
+    ok 59 - add path '[*]["data"]'
+    ok 60 - lookup path '[*]["data"]'
+    ok 61 - lookup numeric token in multikey node
+    ok 62 - lookup any token in multikey node
+    ok 63 - lookup string token in multikey node
 ok 3 - subtests
 	*** test_tree: done ***
 	*** test_path_cmp ***
-    1..7
+    1..8
     ok 1 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["FIO"].fname": have 0, expected 0
     ok 2 - path cmp result "Data[1]["FIO"].fname" with "["Data"][1].FIO["fname"]": have 0, expected 0
     ok 3 - path cmp result "Data[1]["FIO"].fname" with "Data[1]": have 1, expected 1
@@ -171,6 +176,7 @@ ok 3 - subtests
     ok 5 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["Info"].fname[1]": have -1, expected -1
     ok 6 - path Data[1]["FIO"].fname is valid
     ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6
+    ok 8 - path cmp result "Data[*]["FIO"].fname[*]" with "["Data"][*].FIO["fname"][*]": have 0, expected 0
 ok 4 - subtests
 	*** test_path_cmp: done ***
 	*** test_path_snprint ***
-- 
2.20.1

Re: [PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Vladimir Davydov]

On Tue, Feb 19, 2019 at 01:31:43PM +0300, Kirill Shcherbatov wrote:
> Introduced a new JSON_TOKEN_ANY json token that makes possible to
> perform anonymous lookup in marked tree nodes. This feature is
> required to implement multikey indexes.
> Since the token entered into the parser becomes available to user,
> additional server-side check is introduced so that an error
> occurs when trying to create a multikey index.
> 
> Needed for #1260
> 
> With the introduction of multikey indexes, the key_parts_are_compatible
> function will not change significantly: here
> https://gist.github.com/kshcherbatov/c0e48138fc16678ad9a82646f00c1881
> you can see how the check is made that the multikey indexes are compatible
> with each other.
> 
> https://github.com/tarantool/tarantool/tree/kshch/gh-1257-multikey-index-json-any-token
> https://github.com/tarantool/tarantool/issues/1257
> ---
>  src/box/index_def.c       | 60 +++++++++++++++++++++++++++++++++------
>  src/lib/json/json.c       | 38 +++++++++++++++++++------
>  src/lib/json/json.h       | 21 ++++++++++++--
>  test/engine/json.result   | 21 ++++++++++++++
>  test/engine/json.test.lua |  8 ++++++
>  test/unit/json.c          | 52 +++++++++++++++++++++++++++++----
>  test/unit/json.result     | 10 +++++--
>  7 files changed, 184 insertions(+), 26 deletions(-)
> 
> diff --git a/src/box/index_def.c b/src/box/index_def.c
> index 6c37f9f1d..0f99f1759 100644
> --- a/src/box/index_def.c
> +++ b/src/box/index_def.c
> @@ -244,6 +244,56 @@ index_def_cmp(const struct index_def *key1, const struct index_def *key2)
>  			    key2->key_def->parts, key2->key_def->part_count);
>  }
>  
> +/**
> + * Test whether key_parts a and b are compatible:
> + *  + field numbers are differ OR
> + *  + json paths are differ
> + * Also perform integrity check: parts must not define multikey
> + * index.
> + */
> +static bool
> +key_parts_are_compatible(struct key_part *a, struct key_part *b,
> +			 struct index_def *index_def, const char *space_name)
> +{
> +	if (a->fieldno != b->fieldno)
> +		return true;
> +	struct json_lexer lexer_a, lexer_b;
> +	json_lexer_create(&lexer_a, a->path, a->path_len, TUPLE_INDEX_BASE);
> +	json_lexer_create(&lexer_b, b->path, b->path_len, TUPLE_INDEX_BASE);
> +	struct json_token token_a, token_b;

> +	/* For the sake of json_token_cmp(). */
> +	token_a.parent = NULL;
> +	token_b.parent = NULL;

Violates encapsulation :-/

> +	int a_rc, b_rc;
> +	int token_idx = 0,  differ_token_idx = 0;
> +	int a_multikey_rank = 0, b_multikey_rank = 0;
> +	while ((a_rc = json_lexer_next_token(&lexer_a, &token_a)) == 0 &&
> +	       (b_rc = json_lexer_next_token(&lexer_b, &token_b)) == 0 &&
> +	       token_a.type != JSON_TOKEN_END &&
> +	       token_b.type != JSON_TOKEN_END) {

What if a->path is longer than b->path?

> +		token_idx++;
> +		if (differ_token_idx == 0) {
> +			if (json_token_cmp(&token_a, &token_b) != 0)
> +				differ_token_idx = token_idx;
> +		}
> +		if (token_a.type == JSON_TOKEN_ANY)
> +			a_multikey_rank = token_idx;
> +		if (token_b.type == JSON_TOKEN_ANY)
> +			b_multikey_rank = token_idx;
> +	}
> +	if (a_multikey_rank > 0 || b_multikey_rank > 0) {
> +		diag_set(ClientError, ER_MODIFY_INDEX,
> +			 index_def->name, space_name,
> +			 "multikey index feature is not supported yet");

Should be ER_UNSUPPORTED and should live in check_index_def engine
callbacks. This implies that we should set has_multikey somewhere in
key_def_new. Probably, this check should be moved there as well - after
all, it's about key def, not index def.

Anyway, I don't think that this should be a business of this particular
patch. Let's start with patching json library only and add a simple stub
that raises error on any * in key_def.

> +		return false;
> +	}
> +	if (differ_token_idx > 0 || token_b.type != token_a.type)
> +		return true;
> +	diag_set(ClientError, ER_MODIFY_INDEX, index_def->name, space_name,
> +		"same key part is indexed twice");
> +	return false;
> +}
> +
>  bool
>  index_def_is_valid(struct index_def *index_def, const char *space_name)
>  
> @@ -282,15 +332,9 @@ index_def_is_valid(struct index_def *index_def, const char *space_name)
>  			 */

The comment right above this line is obsoleted by this patch.

>  			struct key_part *part_a = &index_def->key_def->parts[i];
>  			struct key_part *part_b = &index_def->key_def->parts[j];
> -			if (part_a->fieldno == part_b->fieldno &&
> -			    json_path_cmp(part_a->path, part_a->path_len,
> -					  part_b->path, part_b->path_len,
> -					  TUPLE_INDEX_BASE) == 0) {
> -				diag_set(ClientError, ER_MODIFY_INDEX,
> -					 index_def->name, space_name,
> -					 "same key part is indexed twice");
> +			if (!key_parts_are_compatible(part_a, part_b, index_def,
> +						      space_name))
>  				return false;
> -			}
>  		}
>  	}
>  	return true;
> diff --git a/src/lib/json/json.c b/src/lib/json/json.c
> index 1b1a3ec2c..019917825 100644
> --- a/src/lib/json/json.c
> +++ b/src/lib/json/json.c
> @@ -146,18 +146,25 @@ json_parse_integer(struct json_lexer *lexer, struct json_token *token)
>  	int len = 0;
>  	int value = 0;
>  	char c = *pos;
> -	if (! isdigit(c))
> -		return lexer->symbol_count + 1;
> +	if (!isdigit(c)) {
> +		if (c != '*')
> +			return lexer->symbol_count + 1;
> +		token->type = JSON_TOKEN_ANY;
> +		++len;
> +		++pos;
> +		goto end;
> +	}

This should live in json_lexer_next_token, not in json_parse_integer,
because * is not an integer.

>  	do {
>  		value = value * 10 + c - (int)'0';
>  		++len;
>  	} while (++pos < end && isdigit((c = *pos)));
>  	if (value < lexer->index_base)
>  		return lexer->symbol_count + 1;
> -	lexer->offset += len;
> -	lexer->symbol_count += len;
>  	token->type = JSON_TOKEN_NUM;
>  	token->num = value - lexer->index_base;
> +end:
> +	lexer->offset += len;
> +	lexer->symbol_count += len;
>  	return 0;
>  }
>  
> diff --git a/src/lib/json/json.h b/src/lib/json/json.h
> index 66cddd026..ff4ab7d91 100644
> --- a/src/lib/json/json.h
> +++ b/src/lib/json/json.h
> @@ -66,6 +66,7 @@ struct json_lexer {
>  enum json_token_type {
>  	JSON_TOKEN_NUM,
>  	JSON_TOKEN_STR,
> +	JSON_TOKEN_ANY,
>  	/** Lexer reached end of path. */
>  	JSON_TOKEN_END,
>  };
> @@ -113,6 +114,10 @@ struct json_token {
>  	 * a JSON tree root.
>  	 */
>  	int sibling_idx;
> +	/**
> +	 * True when it has the only child token JSON_TOKEN_ANY.
> +	 */
> +	bool is_multikey;

I don't think that we really need this flag, because we can introduce
a simple helper function instead:

	bool json_token_is_multikey(token)
	{
		return token->max_child_idx == 0 &&
			token->children[0].type == JSON_TOKEN_ANY;
	}

Also, please update the comment to children array to point out what it
stores in case of a multikey token.

>  	/**
>  	 * Hash value of the token. Used for lookups in a JSON tree.
>  	 * For more details, see the comment to json_tree::hash.
> @@ -236,6 +241,12 @@ json_lexer_create(struct json_lexer *lexer, const char *src, int src_len,
>  int
>  json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
>  
> +/**
> + * Compare JSON token keys.
> + */
> +int
> +json_token_cmp(const struct json_token *a, const struct json_token *b);
> +
>  /**
>   * Compare two JSON paths using Lexer class.
>   * - in case of paths that have same token-sequence prefix,
> @@ -307,10 +318,16 @@ json_tree_lookup(struct json_tree *tree, struct json_token *parent,
>  		 const struct json_token *token)
>  {
>  	struct json_token *ret = NULL;
> +	if (unlikely(parent->is_multikey &&
> +		     (token->type == JSON_TOKEN_NUM ||
> +		      token->type == JSON_TOKEN_ANY))) {

I don't think there's much point in checking token->type here.
We can return ANY for JSON_TOKEN_STR as well. Moreover, this would
look more logical IMO.

> +		assert(parent->max_child_idx == 0);
> +		return parent->children[0];
> +	}
>  	if (likely(token->type == JSON_TOKEN_NUM)) {
> -		ret = (int)token->num < parent->children_capacity ?
> +		ret = token->num <= parent->max_child_idx ?
>  		      parent->children[token->num] : NULL;
> -	} else {
> +	} else if (token->type == JSON_TOKEN_STR) {
>  		ret = json_tree_lookup_slowpath(tree, parent, token);
>  	}
>  	return ret;

If we look up ANY, shouldn't we be given any token rather than NULL?

Re: [tarantool-patches] Re: [PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Kirill Shcherbatov]

> If we look up ANY, shouldn't we be given any token rather than NULL?
Yep. Let's return 
if (likely(parent->max_child_idx >= 0))
	ret = parent->children[parent->max_child_idx];

=====================================================	

Introduced a new JSON_TOKEN_ANY json token that makes possible to
perform anonymous lookup in marked tree nodes. This feature is
required to implement multikey indexes.
Since the token entered into the parser becomes available to user,
additional server-side check is introduced so that an error
occurs when trying to create a multikey index.

Needed for #1257

https://github.com/tarantool/tarantool/tree/kshch/gh-1257-multikey-index-new-field-map-alloc
https://github.com/tarantool/tarantool/issues/1257
---
 src/box/key_def.c         | 27 ++++++++++++++--
 src/lib/json/json.c       | 25 ++++++++++-----
 src/lib/json/json.h       | 40 +++++++++++++++++++++---
 test/engine/json.result   | 13 ++++++++
 test/engine/json.test.lua |  7 +++++
 test/unit/json.c          | 65 ++++++++++++++++++++++++++++++++++++---
 test/unit/json.result     | 12 ++++++--
 7 files changed, 168 insertions(+), 21 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index 432b72a97..6e818f20a 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -196,12 +196,30 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
 			if (coll_id == NULL) {
 				diag_set(ClientError, ER_WRONG_INDEX_OPTIONS,
 					 i + 1, "collation was not found by ID");
-				key_def_delete(def);
-				return NULL;
+				goto error;
 			}
 			coll = coll_id->coll;
 		}
-		uint32_t path_len = part->path != NULL ? strlen(part->path) : 0;
+		uint32_t path_len = 0;
+		if (part->path != NULL) {
+			path_len = strlen(part->path);
+			int rc;
+			struct json_lexer lexer;
+			struct json_token token;
+			json_lexer_create(&lexer, part->path, path_len,
+					  TUPLE_INDEX_BASE);
+			while ((rc = json_lexer_next_token(&lexer,
+							   &token)) == 0) {
+				if (token.type == JSON_TOKEN_ANY) {
+					diag_set(ClientError, ER_UNSUPPORTED,
+						 "Index", "multikey path yet");
+					goto error;
+				} else if (token.type == JSON_TOKEN_END) {
+					break;
+				}
+			}
+			assert(rc == 0 && token.type == JSON_TOKEN_END);
+		}
 		key_def_set_part(def, i, part->fieldno, part->type,
 				 part->nullable_action, coll, part->coll_id,
 				 part->sort_order, part->path, path_len,
@@ -210,6 +228,9 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
 	assert(path_pool == (char *)def + sz);
 	key_def_set_func(def);
 	return def;
+error:
+	key_def_delete(def);
+	return NULL;
 }
 
 int
diff --git a/src/lib/json/json.c b/src/lib/json/json.c
index 1b1a3ec2c..2a28d5d8e 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -226,10 +226,14 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 		if (lexer->offset == lexer->src_len)
 			return lexer->symbol_count;
 		c = json_current_char(lexer);
-		if (c == '"' || c == '\'')
+		if (c == '"' || c == '\'') {
 			rc = json_parse_string(lexer, token, c);
-		else
+		} else if (c == '*') {
+			json_skip_char(lexer);
+			token->type = JSON_TOKEN_ANY;
+		} else {
 			rc = json_parse_integer(lexer, token);
+		}
 		if (rc != 0)
 			return rc;
 		/*
@@ -252,10 +256,7 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 	}
 }
 
-/**
- * Compare JSON token keys.
- */
-static int
+int
 json_token_cmp(const struct json_token *a, const struct json_token *b)
 {
 	if (a->parent != b->parent)
@@ -270,7 +271,7 @@ json_token_cmp(const struct json_token *a, const struct json_token *b)
 	} else if (a->type == JSON_TOKEN_NUM) {
 		ret = a->num - b->num;
 	} else {
-		unreachable();
+		assert(a->type == JSON_TOKEN_ANY);
 	}
 	return ret;
 }
@@ -332,6 +333,9 @@ json_token_snprint(char *buf, int size, const struct json_token *token,
 	case JSON_TOKEN_STR:
 		len = snprintf(buf, size, "[\"%.*s\"]", token->len, token->str);
 		break;
+	case JSON_TOKEN_ANY:
+		len = snprintf(buf, size, "[*]");
+		break;
 	default:
 		unreachable();
 	}
@@ -420,6 +424,9 @@ json_token_hash(struct json_token *token)
 	} else if (token->type == JSON_TOKEN_NUM) {
 		data = &token->num;
 		data_size = sizeof(token->num);
+	} else if (token->type == JSON_TOKEN_ANY) {
+		data = "*";
+		data_size = 1;
 	} else {
 		unreachable();
 	}
@@ -479,6 +486,8 @@ json_tree_add(struct json_tree *tree, struct json_token *parent,
 	      struct json_token *token)
 {
 	assert(json_tree_lookup(tree, parent, token) == NULL);
+	assert(token->type != JSON_TOKEN_ANY ||
+	       (!json_token_is_multikey(parent) && json_token_is_leaf(parent)));
 	token->parent = parent;
 	token->children = NULL;
 	token->children_capacity = 0;
@@ -532,6 +541,8 @@ json_tree_del(struct json_tree *tree, struct json_token *token)
 	assert(token->sibling_idx >= 0);
 	assert(parent->children[token->sibling_idx] == token);
 	assert(json_tree_lookup(tree, parent, token) == token);
+	assert(token->type != JSON_TOKEN_ANY ||
+	       (json_token_is_multikey(parent) && parent->max_child_idx == 0));
 	/*
 	 * Clear the entry corresponding to this token in parent's
 	 * children array and update max_child_idx if necessary.
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index 66cddd026..c1c61c447 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -66,6 +66,7 @@ struct json_lexer {
 enum json_token_type {
 	JSON_TOKEN_NUM,
 	JSON_TOKEN_STR,
+	JSON_TOKEN_ANY,
 	/** Lexer reached end of path. */
 	JSON_TOKEN_END,
 };
@@ -98,6 +99,8 @@ struct json_token {
 	 * array match [token.num] index for JSON_TOKEN_NUM type
 	 * and are allocated sequentially for JSON_TOKEN_STR child
 	 * tokens.
+	 * If in case of "multikey entry", children array has the
+	 * only child JSON_TOKEN_ANY with index 0.
 	 */
 	struct json_token **children;
 	/** Allocation size of children array. */
@@ -236,6 +239,12 @@ json_lexer_create(struct json_lexer *lexer, const char *src, int src_len,
 int
 json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
 
+/**
+ * Compare JSON token keys.
+ */
+int
+json_token_cmp(const struct json_token *a, const struct json_token *b);
+
 /**
  * Compare two JSON paths using Lexer class.
  * - in case of paths that have same token-sequence prefix,
@@ -264,6 +273,16 @@ json_token_is_leaf(struct json_token *token)
 	return token->max_child_idx < 0;
 }
 
+/**
+ * Test if a given JSON token is multikey.
+ */
+static inline bool
+json_token_is_multikey(struct json_token *token)
+{
+	return token->max_child_idx == 0 &&
+	       token->children[0]->type == JSON_TOKEN_ANY;
+}
+
 /**
  * An snprint-style function to print the path to a token in
  * a JSON tree.
@@ -307,11 +326,24 @@ json_tree_lookup(struct json_tree *tree, struct json_token *parent,
 		 const struct json_token *token)
 {
 	struct json_token *ret = NULL;
-	if (likely(token->type == JSON_TOKEN_NUM)) {
-		ret = (int)token->num < parent->children_capacity ?
-		      parent->children[token->num] : NULL;
-	} else {
+	if (unlikely(json_token_is_multikey(parent))) {
+		assert(parent->max_child_idx == 0);
+		return parent->children[0];
+	}
+	switch (token->type) {
+	case JSON_TOKEN_NUM:
+		if (likely(token->num <= parent->max_child_idx))
+			ret = parent->children[token->num];
+		break;
+	case JSON_TOKEN_ANY:
+		if (likely(parent->max_child_idx >= 0))
+			ret = parent->children[parent->max_child_idx];
+		break;
+	case JSON_TOKEN_STR:
 		ret = json_tree_lookup_slowpath(tree, parent, token);
+		break;
+	default:
+		unreachable();
 	}
 	return ret;
 }
diff --git a/test/engine/json.result b/test/engine/json.result
index 1bac85edd..c25fe5ce3 100644
--- a/test/engine/json.result
+++ b/test/engine/json.result
@@ -683,3 +683,16 @@ town:select()
 s:drop()
 ---
 ...
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+---
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+---
+- error: Index does not support multikey path yet
+...
+s:drop()
+---
+...
diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
index 9afa3daa2..f9a7180b1 100644
--- a/test/engine/json.test.lua
+++ b/test/engine/json.test.lua
@@ -192,3 +192,10 @@ town:select()
 name:drop()
 town:select()
 s:drop()
+
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+s:drop()
diff --git a/test/unit/json.c b/test/unit/json.c
index 6448a3210..2e24d60f1 100644
--- a/test/unit/json.c
+++ b/test/unit/json.c
@@ -211,7 +211,7 @@ void
 test_tree()
 {
 	header();
-	plan(58);
+	plan(65);
 
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
@@ -411,6 +411,54 @@ test_tree()
 	   "last node became interm - it can't be leaf anymore");
 	is(json_token_is_leaf(&records[3].node), true, "last node is leaf");
 
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node, node_tmp)
+		json_tree_del(&tree, &node->node);
+
+	/* Test multikey tokens. */
+	records_idx = 0;
+	char *path_problem = "base[3]";
+	node = test_add_path(&tree, path_problem, strlen(path_problem),
+			     records, &records_idx);
+	is(node, &records[1], "add path '%s'", path_problem);
+	token->type = JSON_TOKEN_ANY;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node->node.num, 2, "lookup any token in non-multikey node");
+
+	/* Can't attay ANY token to non-leaf parent. Cleanup. */
+	json_tree_del(&tree, &records[1].node);
+	records_idx--;
+
+	char *path_multikey = "base[*][\"data\"]";
+	node = test_add_path(&tree, path_multikey, strlen(path_multikey),
+			     records, &records_idx);
+	is(node, &records[2], "add path '%s'", path_multikey);
+
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path_multikey,
+					   strlen(path_multikey), INDEX_BASE,
+					   struct test_struct, node);
+	is(node, &records[2], "lookup path '%s'", path_multikey);
+
+	token = &records[records_idx++].node;
+	token->type = JSON_TOKEN_NUM;
+	token->num = 3;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup numeric token in multikey node");
+
+	token->type = JSON_TOKEN_ANY;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup any token in multikey node");
+
+	token->type = JSON_TOKEN_STR;
+	token->str = "str";
+	token->len = strlen("str");
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup string token in multikey node");
+
 	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
 				     node, node_tmp)
 		json_tree_del(&tree, &node->node);
@@ -433,7 +481,7 @@ test_path_cmp()
 		{"Data[1][\"Info\"].fname[1]", -1},
 	};
 	header();
-	plan(lengthof(rc) + 2);
+	plan(lengthof(rc) + 3);
 	for (size_t i = 0; i < lengthof(rc); ++i) {
 		const char *path = rc[i].path;
 		int errpos = rc[i].errpos;
@@ -450,6 +498,13 @@ test_path_cmp()
 	ret = json_path_validate(invalid, strlen(invalid), INDEX_BASE);
 	is(ret, 6, "path %s error pos %d expected %d", invalid, ret, 6);
 
+	char *multikey_a = "Data[*][\"FIO\"].fname[*]";
+	char *multikey_b = "[\"Data\"][*].FIO[\"fname\"][*]";
+	ret = json_path_cmp(multikey_a, strlen(multikey_a), multikey_b,
+			    strlen(multikey_b), INDEX_BASE);
+	is(ret, 0, "path cmp result \"%s\" with \"%s\": have %d, expected %d",
+	   multikey_a, multikey_b, ret, 0);
+
 	check_plan();
 	footer();
 }
@@ -463,14 +518,14 @@ test_path_snprint()
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
 	fail_if(rc != 0);
-	struct test_struct records[5];
-	const char *path = "[1][20][\"file\"][8]";
+	struct test_struct records[6];
+	const char *path = "[1][*][20][\"file\"][8]";
 	int path_len = strlen(path);
 
 	int records_idx = 0;
 	struct test_struct *node, *node_tmp;
 	node = test_add_path(&tree, path, path_len, records, &records_idx);
-	fail_if(&node->node != &records[3].node);
+	fail_if(&node->node != &records[4].node);
 
 	char buf[64];
 	int bufsz = sizeof(buf);
diff --git a/test/unit/json.result b/test/unit/json.result
index ee54cbe0e..02080f93a 100644
--- a/test/unit/json.result
+++ b/test/unit/json.result
@@ -101,7 +101,7 @@ ok 1 - subtests
 ok 2 - subtests
 	*** test_errors: done ***
 	*** test_tree ***
-    1..58
+    1..65
     ok 1 - add path '[1][10]'
     ok 2 - add path '[1][20].file'
     ok 3 - add path '[1][20].file[2]'
@@ -160,10 +160,17 @@ ok 2 - subtests
     ok 56 - last node is leaf
     ok 57 - last node became interm - it can't be leaf anymore
     ok 58 - last node is leaf
+    ok 59 - add path 'base[3]'
+    ok 60 - lookup any token in non-multikey node
+    ok 61 - add path 'base[*]["data"]'
+    ok 62 - lookup path 'base[*]["data"]'
+    ok 63 - lookup numeric token in multikey node
+    ok 64 - lookup any token in multikey node
+    ok 65 - lookup string token in multikey node
 ok 3 - subtests
 	*** test_tree: done ***
 	*** test_path_cmp ***
-    1..7
+    1..8
     ok 1 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["FIO"].fname": have 0, expected 0
     ok 2 - path cmp result "Data[1]["FIO"].fname" with "["Data"][1].FIO["fname"]": have 0, expected 0
     ok 3 - path cmp result "Data[1]["FIO"].fname" with "Data[1]": have 1, expected 1
@@ -171,6 +178,7 @@ ok 3 - subtests
     ok 5 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["Info"].fname[1]": have -1, expected -1
     ok 6 - path Data[1]["FIO"].fname is valid
     ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6
+    ok 8 - path cmp result "Data[*]["FIO"].fname[*]" with "["Data"][*].FIO["fname"][*]": have 0, expected 0
 ok 4 - subtests
 	*** test_path_cmp: done ***
 	*** test_path_snprint ***
-- 
2.20.1

Re: [tarantool-patches] Re: [PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Vladimir Davydov]

On Wed, Feb 27, 2019 at 05:07:30PM +0300, Kirill Shcherbatov wrote:
> diff --git a/src/box/key_def.c b/src/box/key_def.c
> index 432b72a97..6e818f20a 100644
> --- a/src/box/key_def.c
> +++ b/src/box/key_def.c
> @@ -196,12 +196,30 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
>  			if (coll_id == NULL) {
>  				diag_set(ClientError, ER_WRONG_INDEX_OPTIONS,
>  					 i + 1, "collation was not found by ID");
> -				key_def_delete(def);
> -				return NULL;
> +				goto error;
>  			}
>  			coll = coll_id->coll;
>  		}
> -		uint32_t path_len = part->path != NULL ? strlen(part->path) : 0;
> +		uint32_t path_len = 0;
> +		if (part->path != NULL) {
> +			path_len = strlen(part->path);
> +			int rc;
> +			struct json_lexer lexer;
> +			struct json_token token;
> +			json_lexer_create(&lexer, part->path, path_len,
> +					  TUPLE_INDEX_BASE);
> +			while ((rc = json_lexer_next_token(&lexer,
> +							   &token)) == 0) {
> +				if (token.type == JSON_TOKEN_ANY) {
> +					diag_set(ClientError, ER_UNSUPPORTED,
> +						 "Index", "multikey path yet");

ER_UNSUPPORTED, "Tarantool", "multikey indexes".

> +					goto error;
> +				} else if (token.type == JSON_TOKEN_END) {
> +					break;
> +				}
> +			}
> +			assert(rc == 0 && token.type == JSON_TOKEN_END);
> +		}

This is a bit too much for a simple stub forbidding multikey indexes.
Let's add JSON_TOKEN_ANY check to tuple_format_add_field() for now.
It will be more compact, because we already parse a path there, hence
it will be easier to remove it.

>  		key_def_set_part(def, i, part->fieldno, part->type,
>  				 part->nullable_action, coll, part->coll_id,
>  				 part->sort_order, part->path, path_len,
> diff --git a/src/lib/json/json.c b/src/lib/json/json.c
> index 1b1a3ec2c..2a28d5d8e 100644
> --- a/src/lib/json/json.c
> +++ b/src/lib/json/json.c
> @@ -252,10 +256,7 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
>  	}
>  }
>  
> -/**
> - * Compare JSON token keys.
> - */
> -static int
> +int

You don't need to export this function any more. Please be more careful
and thoroughly self-review your patches before submitting them for
review.

>  json_token_cmp(const struct json_token *a, const struct json_token *b)
>  {
>  	if (a->parent != b->parent)
> @@ -479,6 +486,8 @@ json_tree_add(struct json_tree *tree, struct json_token *parent,
>  	      struct json_token *token)
>  {
>  	assert(json_tree_lookup(tree, parent, token) == NULL);
> +	assert(token->type != JSON_TOKEN_ANY ||
> +	       (!json_token_is_multikey(parent) && json_token_is_leaf(parent)));

AFAIU you don't need this assertion - (json_token_lookup == NULL) check
should be enough, no?

>  	token->parent = parent;
>  	token->children = NULL;
>  	token->children_capacity = 0;
> @@ -532,6 +541,8 @@ json_tree_del(struct json_tree *tree, struct json_token *token)
>  	assert(token->sibling_idx >= 0);
>  	assert(parent->children[token->sibling_idx] == token);
>  	assert(json_tree_lookup(tree, parent, token) == token);
> +	assert(token->type != JSON_TOKEN_ANY ||
> +	       (json_token_is_multikey(parent) && parent->max_child_idx == 0));

Ditto.

>  	/*
>  	 * Clear the entry corresponding to this token in parent's
>  	 * children array and update max_child_idx if necessary.
> diff --git a/src/lib/json/json.h b/src/lib/json/json.h
> index 66cddd026..c1c61c447 100644
> --- a/src/lib/json/json.h
> +++ b/src/lib/json/json.h
> @@ -98,6 +99,8 @@ struct json_token {
>  	 * array match [token.num] index for JSON_TOKEN_NUM type
>  	 * and are allocated sequentially for JSON_TOKEN_STR child
>  	 * tokens.
> +	 * If in case of "multikey entry", children array has the
> +	 * only child JSON_TOKEN_ANY with index 0.

Please always add an empty line between paragraphs. Anyway, let's
rewrite this appendix to the comment as follows:

	JSON_TOKEN_ANY is exclusive. If it's present, it must
	be the only one and have index 0 in the children array.
	It will be returned by lookup by any key.

>  	 */
>  	struct json_token **children;
>  	/** Allocation size of children array. */
> diff --git a/test/unit/json.c b/test/unit/json.c
> index 6448a3210..2e24d60f1 100644
> --- a/test/unit/json.c
> +++ b/test/unit/json.c
> @@ -411,6 +411,54 @@ test_tree()
>  	   "last node became interm - it can't be leaf anymore");
>  	is(json_token_is_leaf(&records[3].node), true, "last node is leaf");
>  
> +	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
> +				     node, node_tmp)
> +		json_tree_del(&tree, &node->node);
> +
> +	/* Test multikey tokens. */
> +	records_idx = 0;
> +	char *path_problem = "base[3]";

Why 'path_problem'? The variable name is confusing. Let's please simply
reuse 'path' variable defined above in the code.

> +	node = test_add_path(&tree, path_problem, strlen(path_problem),
> +			     records, &records_idx);
> +	is(node, &records[1], "add path '%s'", path_problem);
> +	token->type = JSON_TOKEN_ANY;
> +	node = json_tree_lookup_entry(&tree, &records[0].node, token,
> +				      struct test_struct, node);
> +	is(node->node.num, 2, "lookup any token in non-multikey node");
> +
> +	/* Can't attay ANY token to non-leaf parent. Cleanup. */

s/attay/attach
s/parent/node

> +	json_tree_del(&tree, &records[1].node);
> +	records_idx--;
> +
> +	char *path_multikey = "base[*][\"data\"]";

Again, let's please reuse 'path' and 'path_len' defined in the beginning
of this function rather than adding a new local variable.

> +	node = test_add_path(&tree, path_multikey, strlen(path_multikey),
> +			     records, &records_idx);
> +	is(node, &records[2], "add path '%s'", path_multikey);
> +
> +	node = json_tree_lookup_path_entry(&tree, &tree.root, path_multikey,
> +					   strlen(path_multikey), INDEX_BASE,
> +					   struct test_struct, node);
> +	is(node, &records[2], "lookup path '%s'", path_multikey);
> +
> +	token = &records[records_idx++].node;
> +	token->type = JSON_TOKEN_NUM;
> +	token->num = 3;
> +	node = json_tree_lookup_entry(&tree, &records[0].node, token,
> +				      struct test_struct, node);
> +	is(node, &records[1], "lookup numeric token in multikey node");
> +
> +	token->type = JSON_TOKEN_ANY;
> +	node = json_tree_lookup_entry(&tree, &records[0].node, token,
> +				      struct test_struct, node);
> +	is(node, &records[1], "lookup any token in multikey node");
> +
> +	token->type = JSON_TOKEN_STR;
> +	token->str = "str";
> +	token->len = strlen("str");
> +	node = json_tree_lookup_entry(&tree, &records[0].node, token,
> +				      struct test_struct, node);
> +	is(node, &records[1], "lookup string token in multikey node");
> +
>  	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
>  				     node, node_tmp)
>  		json_tree_del(&tree, &node->node);
> diff --git a/test/unit/json.result b/test/unit/json.result
> index ee54cbe0e..02080f93a 100644
> --- a/test/unit/json.result
> +++ b/test/unit/json.result
> @@ -160,10 +160,17 @@ ok 2 - subtests
>      ok 56 - last node is leaf
>      ok 57 - last node became interm - it can't be leaf anymore
>      ok 58 - last node is leaf
> +    ok 59 - add path 'base[3]'
> +    ok 60 - lookup any token in non-multikey node
> +    ok 61 - add path 'base[*]["data"]'
> +    ok 62 - lookup path 'base[*]["data"]'
> +    ok 63 - lookup numeric token in multikey node
> +    ok 64 - lookup any token in multikey node
> +    ok 65 - lookup string token in multikey node
>  ok 3 - subtests
>  	*** test_tree: done ***
>  	*** test_path_cmp ***
> -    1..7
> +    1..8
>      ok 1 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["FIO"].fname": have 0, expected 0
>      ok 2 - path cmp result "Data[1]["FIO"].fname" with "["Data"][1].FIO["fname"]": have 0, expected 0
>      ok 3 - path cmp result "Data[1]["FIO"].fname" with "Data[1]": have 1, expected 1
> @@ -171,6 +178,7 @@ ok 3 - subtests
>      ok 5 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["Info"].fname[1]": have -1, expected -1
>      ok 6 - path Data[1]["FIO"].fname is valid
>      ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6
> +    ok 8 - path cmp result "Data[*]["FIO"].fname[*]" with "["Data"][*].FIO["fname"][*]": have 0, expected 0

Nit: Let's please move this test case a bit above so that all 'path cmp'
are gathered together.

Re: [tarantool-patches] Re: [PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Kirill Shcherbatov]

>> +	char *path_multikey = "base[*][\"data\"]";
> 
> Again, let's please reuse 'path' and 'path_len' defined in the beginning
> of this function rather than adding a new local variable.
I really prefer to introduce a new variable here instead of override existent one.

===============================================

Introduced a new JSON_TOKEN_ANY json token that makes possible to
perform anonymous lookup in marked tree nodes. This feature is
required to implement multikey indexes.
Since the token entered into the parser becomes available to user,
additional server-side check is introduced so that an error
occurs when trying to create a multikey index.

Needed for #1257
---
 src/box/tuple_format.c    |  5 +++
 src/lib/json/json.c       | 16 ++++++++--
 src/lib/json/json.h       | 36 +++++++++++++++++++---
 test/engine/json.result   | 13 ++++++++
 test/engine/json.test.lua |  7 +++++
 test/unit/json.c          | 65 +++++++++++++++++++++++++++++++++++----
 test/unit/json.result     | 16 +++++++---
 7 files changed, 141 insertions(+), 17 deletions(-)

diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 1c9b3c20d..4439ce3e0 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -233,6 +233,11 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
 	while ((rc = json_lexer_next_token(&lexer, &field->token)) == 0 &&
 	       field->token.type != JSON_TOKEN_END) {
+		if (field->token.type == JSON_TOKEN_ANY) {
+			diag_set(ClientError, ER_UNSUPPORTED,
+				"Tarantool", "multikey indexes");
+			goto fail;
+		}
 		enum field_type expected_type =
 			field->token.type == JSON_TOKEN_STR ?
 			FIELD_TYPE_MAP : FIELD_TYPE_ARRAY;
diff --git a/src/lib/json/json.c b/src/lib/json/json.c
index 1b1a3ec2c..854158f63 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -226,10 +226,14 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 		if (lexer->offset == lexer->src_len)
 			return lexer->symbol_count;
 		c = json_current_char(lexer);
-		if (c == '"' || c == '\'')
+		if (c == '"' || c == '\'') {
 			rc = json_parse_string(lexer, token, c);
-		else
+		} else if (c == '*') {
+			json_skip_char(lexer);
+			token->type = JSON_TOKEN_ANY;
+		} else {
 			rc = json_parse_integer(lexer, token);
+		}
 		if (rc != 0)
 			return rc;
 		/*
@@ -270,7 +274,7 @@ json_token_cmp(const struct json_token *a, const struct json_token *b)
 	} else if (a->type == JSON_TOKEN_NUM) {
 		ret = a->num - b->num;
 	} else {
-		unreachable();
+		assert(a->type == JSON_TOKEN_ANY);
 	}
 	return ret;
 }
@@ -332,6 +336,9 @@ json_token_snprint(char *buf, int size, const struct json_token *token,
 	case JSON_TOKEN_STR:
 		len = snprintf(buf, size, "[\"%.*s\"]", token->len, token->str);
 		break;
+	case JSON_TOKEN_ANY:
+		len = snprintf(buf, size, "[*]");
+		break;
 	default:
 		unreachable();
 	}
@@ -420,6 +427,9 @@ json_token_hash(struct json_token *token)
 	} else if (token->type == JSON_TOKEN_NUM) {
 		data = &token->num;
 		data_size = sizeof(token->num);
+	} else if (token->type == JSON_TOKEN_ANY) {
+		data = "*";
+		data_size = 1;
 	} else {
 		unreachable();
 	}
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index 6927d2d90..c1de3e579 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -66,6 +66,7 @@ struct json_lexer {
 enum json_token_type {
 	JSON_TOKEN_NUM,
 	JSON_TOKEN_STR,
+	JSON_TOKEN_ANY,
 	/** Lexer reached end of path. */
 	JSON_TOKEN_END,
 };
@@ -98,6 +99,10 @@ struct json_token {
 	 * array match [token.num] index for JSON_TOKEN_NUM type
 	 * and are allocated sequentially for JSON_TOKEN_STR child
 	 * tokens.
+	 *
+	 * JSON_TOKEN_ANY is exclusive. If it's present, it must
+	 * be the only one and have index 0 in the children array.
+	 * It will be returned by lookup by any key.
 	 */
 	struct json_token **children;
 	/** Allocation size of children array. */
@@ -264,6 +269,16 @@ json_token_is_leaf(struct json_token *token)
 	return token->max_child_idx < 0;
 }
 
+/**
+ * Test if a given JSON token is multikey.
+ */
+static inline bool
+json_token_is_multikey(struct json_token *token)
+{
+	return token->max_child_idx == 0 &&
+	       token->children[0]->type == JSON_TOKEN_ANY;
+}
+
 /**
  * An snprint-style function to print the path to a token in
  * a JSON tree.
@@ -307,11 +322,24 @@ json_tree_lookup(struct json_tree *tree, struct json_token *parent,
 		 const struct json_token *token)
 {
 	struct json_token *ret = NULL;
-	if (likely(token->type == JSON_TOKEN_NUM)) {
-		ret = (int)token->num < parent->children_capacity ?
-		      parent->children[token->num] : NULL;
-	} else {
+	if (unlikely(json_token_is_multikey(parent))) {
+		assert(parent->max_child_idx == 0);
+		return parent->children[0];
+	}
+	switch (token->type) {
+	case JSON_TOKEN_NUM:
+		if (likely(token->num <= parent->max_child_idx))
+			ret = parent->children[token->num];
+		break;
+	case JSON_TOKEN_ANY:
+		if (likely(parent->max_child_idx >= 0))
+			ret = parent->children[parent->max_child_idx];
+		break;
+	case JSON_TOKEN_STR:
 		ret = json_tree_lookup_slowpath(tree, parent, token);
+		break;
+	default:
+		unreachable();
 	}
 	return ret;
 }
diff --git a/test/engine/json.result b/test/engine/json.result
index 1bac85edd..a790cdfbc 100644
--- a/test/engine/json.result
+++ b/test/engine/json.result
@@ -683,3 +683,16 @@ town:select()
 s:drop()
 ---
 ...
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+---
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+---
+- error: Tarantool does not support multikey indexes
+...
+s:drop()
+---
+...
diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
index 9afa3daa2..f9a7180b1 100644
--- a/test/engine/json.test.lua
+++ b/test/engine/json.test.lua
@@ -192,3 +192,10 @@ town:select()
 name:drop()
 town:select()
 s:drop()
+
+--
+-- gh-1260: Multikey indexes
+--
+s = box.schema.space.create('withdata')
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+s:drop()
diff --git a/test/unit/json.c b/test/unit/json.c
index 6448a3210..fd320c9eb 100644
--- a/test/unit/json.c
+++ b/test/unit/json.c
@@ -211,7 +211,7 @@ void
 test_tree()
 {
 	header();
-	plan(58);
+	plan(65);
 
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
@@ -411,6 +411,52 @@ test_tree()
 	   "last node became interm - it can't be leaf anymore");
 	is(json_token_is_leaf(&records[3].node), true, "last node is leaf");
 
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node, node_tmp)
+		json_tree_del(&tree, &node->node);
+
+	/* Test multikey tokens. */
+	records_idx = 0;
+	node = test_add_path(&tree, path1, strlen(path1), records, &records_idx);
+	is(node, &records[1], "add path '%s'", path1);
+	token->type = JSON_TOKEN_ANY;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node->node.num, 9, "lookup any token in non-multikey node");
+
+	/* Can't attach ANY token to non-leaf node. Cleanup. */
+	json_tree_del(&tree, &records[1].node);
+	records_idx--;
+
+	const char *path_multikey = "[1][*][\"data\"]";
+	node = test_add_path(&tree, path_multikey, strlen(path_multikey),
+			     records, &records_idx);
+	is(node, &records[2], "add path '%s'", path_multikey);
+
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path_multikey,
+					   strlen(path_multikey), INDEX_BASE,
+					   struct test_struct, node);
+	is(node, &records[2], "lookup path '%s'", path_multikey);
+
+	token = &records[records_idx++].node;
+	token->type = JSON_TOKEN_NUM;
+	token->num = 3;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup numeric token in multikey node");
+
+	token->type = JSON_TOKEN_ANY;
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup any token in multikey node");
+
+	token->type = JSON_TOKEN_STR;
+	token->str = "str";
+	token->len = strlen("str");
+	node = json_tree_lookup_entry(&tree, &records[0].node, token,
+				      struct test_struct, node);
+	is(node, &records[1], "lookup string token in multikey node");
+
 	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
 				     node, node_tmp)
 		json_tree_del(&tree, &node->node);
@@ -433,7 +479,7 @@ test_path_cmp()
 		{"Data[1][\"Info\"].fname[1]", -1},
 	};
 	header();
-	plan(lengthof(rc) + 2);
+	plan(lengthof(rc) + 3);
 	for (size_t i = 0; i < lengthof(rc); ++i) {
 		const char *path = rc[i].path;
 		int errpos = rc[i].errpos;
@@ -444,8 +490,15 @@ test_path_cmp()
 		is(rc, errpos, "path cmp result \"%s\" with \"%s\": "
 		   "have %d, expected %d", a, path, rc, errpos);
 	}
+	char *multikey_a = "Data[*][\"FIO\"].fname[*]";
+	char *multikey_b = "[\"Data\"][*].FIO[\"fname\"][*]";
+	int ret = json_path_cmp(multikey_a, strlen(multikey_a), multikey_b,
+				strlen(multikey_b), INDEX_BASE);
+	is(ret, 0, "path cmp result \"%s\" with \"%s\": have %d, expected %d",
+	   multikey_a, multikey_b, ret, 0);
+
 	const char *invalid = "Data[[1][\"FIO\"].fname";
-	int ret = json_path_validate(a, strlen(a), INDEX_BASE);
+	ret = json_path_validate(a, strlen(a), INDEX_BASE);
 	is(ret, 0, "path %s is valid", a);
 	ret = json_path_validate(invalid, strlen(invalid), INDEX_BASE);
 	is(ret, 6, "path %s error pos %d expected %d", invalid, ret, 6);
@@ -463,14 +516,14 @@ test_path_snprint()
 	struct json_tree tree;
 	int rc = json_tree_create(&tree);
 	fail_if(rc != 0);
-	struct test_struct records[5];
-	const char *path = "[1][20][\"file\"][8]";
+	struct test_struct records[6];
+	const char *path = "[1][*][20][\"file\"][8]";
 	int path_len = strlen(path);
 
 	int records_idx = 0;
 	struct test_struct *node, *node_tmp;
 	node = test_add_path(&tree, path, path_len, records, &records_idx);
-	fail_if(&node->node != &records[3].node);
+	fail_if(&node->node != &records[4].node);
 
 	char buf[64];
 	int bufsz = sizeof(buf);
diff --git a/test/unit/json.result b/test/unit/json.result
index ee54cbe0e..3a15e84bb 100644
--- a/test/unit/json.result
+++ b/test/unit/json.result
@@ -101,7 +101,7 @@ ok 1 - subtests
 ok 2 - subtests
 	*** test_errors: done ***
 	*** test_tree ***
-    1..58
+    1..65
     ok 1 - add path '[1][10]'
     ok 2 - add path '[1][20].file'
     ok 3 - add path '[1][20].file[2]'
@@ -160,17 +160,25 @@ ok 2 - subtests
     ok 56 - last node is leaf
     ok 57 - last node became interm - it can't be leaf anymore
     ok 58 - last node is leaf
+    ok 59 - add path '[1][10]'
+    ok 60 - lookup any token in non-multikey node
+    ok 61 - add path '[1][*]["data"]'
+    ok 62 - lookup path '[1][*]["data"]'
+    ok 63 - lookup numeric token in multikey node
+    ok 64 - lookup any token in multikey node
+    ok 65 - lookup string token in multikey node
 ok 3 - subtests
 	*** test_tree: done ***
 	*** test_path_cmp ***
-    1..7
+    1..8
     ok 1 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["FIO"].fname": have 0, expected 0
     ok 2 - path cmp result "Data[1]["FIO"].fname" with "["Data"][1].FIO["fname"]": have 0, expected 0
     ok 3 - path cmp result "Data[1]["FIO"].fname" with "Data[1]": have 1, expected 1
     ok 4 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["FIO"].fname[1]": have -1, expected -1
     ok 5 - path cmp result "Data[1]["FIO"].fname" with "Data[1]["Info"].fname[1]": have -1, expected -1
-    ok 6 - path Data[1]["FIO"].fname is valid
-    ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6
+    ok 6 - path cmp result "Data[*]["FIO"].fname[*]" with "["Data"][*].FIO["fname"][*]": have 0, expected 0
+    ok 7 - path Data[1]["FIO"].fname is valid
+    ok 8 - path Data[[1]["FIO"].fname error pos 6 expected 6
 ok 4 - subtests
 	*** test_path_cmp: done ***
 	*** test_path_snprint ***
-- 
2.21.0

Re: [tarantool-patches] Re: [PATCH v1 1/1] lib: introduce a new JSON_TOKEN_ANY json token

[Vladimir Davydov]

On Fri, Mar 01, 2019 at 04:50:02PM +0300, Kirill Shcherbatov wrote:
> Introduced a new JSON_TOKEN_ANY json token that makes possible to
> perform anonymous lookup in marked tree nodes. This feature is
> required to implement multikey indexes.
> Since the token entered into the parser becomes available to user,
> additional server-side check is introduced so that an error
> occurs when trying to create a multikey index.
> 
> Needed for #1257
> ---
>  src/box/tuple_format.c    |  5 +++
>  src/lib/json/json.c       | 16 ++++++++--
>  src/lib/json/json.h       | 36 +++++++++++++++++++---
>  test/engine/json.result   | 13 ++++++++
>  test/engine/json.test.lua |  7 +++++
>  test/unit/json.c          | 65 +++++++++++++++++++++++++++++++++++----
>  test/unit/json.result     | 16 +++++++---
>  7 files changed, 141 insertions(+), 17 deletions(-)

Pushed to 2.1.