* [PATCH v4 10/14] box: introduce JSON indexes
2018-10-11 7:58 [PATCH v4 00/14] box: indexes by JSON path Kirill Shcherbatov
2018-10-11 7:58 ` [PATCH v4 01/14] box: refactor key_def_find routine Kirill Shcherbatov
@ 2018-10-11 7:58 ` Kirill Shcherbatov
2018-10-16 9:33 ` Vladimir Davydov
2018-10-11 7:58 ` [PATCH v4 11/14] box: introduce has_json_paths flag in templates Kirill Shcherbatov
` (11 subsequent siblings)
13 siblings, 1 reply; 24+ messages in thread
From: Kirill Shcherbatov @ 2018-10-11 7:58 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov
As we need to store user-defined JSON path in key_part
and key_part_def, we have introduced path and path_len
fields. JSON path is verified and transformed to canonical
form on index msgpack unpack.
Path string stored as a part of the key_def allocation:
+-------+---------+-------+---------+-------+-------+-------+
|key_def|key_part1| ... |key_partN| path1 | pathK | pathN |
+-------+---------+-------+---------+-------+-------+-------+
| ^
|-> path _________________|
To work with JSON-defined indexes we use json_tree class:
[2].FIO.fname -> field "fname" {type=str, off_slot=-1}
[2].FIO.sname -> field "sname" {type=str, off_slot=-2}
<Tree>: format->field[2] {type = map}
|
FIO {type = map}
|
"fname" | "sname"
{type=str,off_slot=-1} ____|____ {type = str,off_slot=-2}
All JSON paths stored at the end of format allocation:
+------------+------------+-------+------------+-------+
|tuple_format|tuple_field1| ... |tuple_fieldN| pathK |
+------------+------------+-------+------------+-------+
Part of #1012.
---
src/box/errcode.h | 2 +-
src/box/index_def.c | 6 +-
src/box/key_def.c | 189 +++++++++++++++--
src/box/key_def.h | 31 ++-
src/box/lua/space.cc | 5 +
src/box/memtx_engine.c | 2 +
src/box/tuple.c | 17 +-
src/box/tuple_compare.cc | 7 +-
| 21 +-
src/box/tuple_format.c | 496 ++++++++++++++++++++++++++++++++++++++-----
src/box/tuple_format.h | 65 +++++-
src/box/tuple_hash.cc | 2 +-
src/box/vinyl.c | 2 +
src/box/vy_log.c | 3 +-
src/box/vy_point_lookup.c | 2 -
src/box/vy_stmt.c | 184 +++++++++++++---
test/box/misc.result | 57 ++---
test/engine/tuple.result | 371 ++++++++++++++++++++++++++++++++
test/engine/tuple.test.lua | 106 +++++++++
19 files changed, 1415 insertions(+), 153 deletions(-)
diff --git a/src/box/errcode.h b/src/box/errcode.h
index 4115e6b..464f413 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -107,7 +107,7 @@ struct errcode_record {
/* 52 */_(ER_FUNCTION_EXISTS, "Function '%s' already exists") \
/* 53 */_(ER_BEFORE_REPLACE_RET, "Invalid return value of space:before_replace trigger: expected tuple or nil, got %s") \
/* 54 */_(ER_FUNCTION_MAX, "A limit on the total number of functions has been reached: %u") \
- /* 55 */_(ER_UNUSED4, "") \
+ /* 55 */_(ER_DATA_STRUCTURE_MISMATCH, "Tuple doesn't math document structure: %s") \
/* 56 */_(ER_USER_MAX, "A limit on the total number of users has been reached: %u") \
/* 57 */_(ER_NO_SUCH_ENGINE, "Space engine '%s' does not exist") \
/* 58 */_(ER_RELOAD_CFG, "Can't set option '%s' dynamically") \
diff --git a/src/box/index_def.c b/src/box/index_def.c
index 9cda63c..6e206b1 100644
--- a/src/box/index_def.c
+++ b/src/box/index_def.c
@@ -209,8 +209,10 @@ index_def_is_valid(struct index_def *index_def, const char *space_name)
* Courtesy to a user who could have made
* a typo.
*/
- if (index_def->key_def->parts[i].fieldno ==
- index_def->key_def->parts[j].fieldno) {
+ 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 &&
+ key_part_path_cmp(part_a, part_b) == 0) {
diag_set(ClientError, ER_MODIFY_INDEX,
index_def->name, space_name,
"same key part is indexed twice");
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 67b517f..1b32387 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -28,6 +28,8 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
+#include "fiber.h"
+#include "json/path.h"
#include "key_def.h"
#include "tuple_compare.h"
#include "tuple_extract_key.h"
@@ -41,6 +43,7 @@ const struct key_part_def key_part_def_default = {
field_type_MAX,
COLL_NONE,
false,
+ NULL
};
static int64_t
@@ -53,6 +56,7 @@ part_type_by_name_wrapper(const char *str, uint32_t len)
#define PART_OPT_FIELD "field"
#define PART_OPT_COLLATION "collation"
#define PART_OPT_NULLABILITY "is_nullable"
+#define PART_OPT_PATH "path"
const struct opt_def part_def_reg[] = {
OPT_DEF_ENUM(PART_OPT_TYPE, field_type, struct key_part_def, type,
@@ -61,6 +65,7 @@ const struct opt_def part_def_reg[] = {
OPT_DEF(PART_OPT_COLLATION, OPT_UINT32, struct key_part_def, coll_id),
OPT_DEF(PART_OPT_NULLABILITY, OPT_BOOL, struct key_part_def,
is_nullable),
+ OPT_DEF(PART_OPT_PATH, OPT_STRPTR, struct key_part_def, path),
OPT_END,
};
@@ -96,13 +101,25 @@ const uint32_t key_mp_type[] = {
struct key_def *
key_def_dup(const struct key_def *src)
{
- size_t sz = key_def_sizeof(src->part_count);
- struct key_def *res = (struct key_def *)malloc(sz);
+ const struct key_part *parts = src->parts;
+ const struct key_part *parts_end = parts + src->part_count;
+ size_t sz = 0;
+ for (; parts < parts_end; parts++)
+ sz += parts->path != NULL ? parts->path_len + 1 : 0;
+ sz = key_def_sizeof(src->part_count, sz);
+ struct key_def *res = (struct key_def *)calloc(1, sz);
if (res == NULL) {
diag_set(OutOfMemory, sz, "malloc", "res");
return NULL;
}
memcpy(res, src, sz);
+ /* Update paths to point to the new memory chunk.*/
+ for (uint32_t i = 0; i < src->part_count; i++) {
+ if (src->parts[i].path == NULL)
+ continue;
+ size_t path_offset = src->parts[i].path - (char *)src;
+ res->parts[i].path = (char *)res + path_offset;
+ }
return res;
}
@@ -110,8 +127,23 @@ void
key_def_swap(struct key_def *old_def, struct key_def *new_def)
{
assert(old_def->part_count == new_def->part_count);
- for (uint32_t i = 0; i < new_def->part_count; i++)
- SWAP(old_def->parts[i], new_def->parts[i]);
+ for (uint32_t i = 0; i < new_def->part_count; i++) {
+ if (old_def->parts[i].path == NULL) {
+ SWAP(old_def->parts[i], new_def->parts[i]);
+ } else {
+ /*
+ * Since the data is located in memory
+ * in the same order (otherwise rebuild
+ * would be called), just update the
+ * pointers.
+ */
+ size_t path_offset =
+ old_def->parts[i].path - (char *)old_def;
+ SWAP(old_def->parts[i], new_def->parts[i]);
+ old_def->parts[i].path = (char *)old_def + path_offset;
+ new_def->parts[i].path = (char *)new_def + path_offset;
+ }
+ }
SWAP(*old_def, *new_def);
}
@@ -133,23 +165,36 @@ key_def_set_cmp(struct key_def *def)
static void
key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
enum field_type type, bool is_nullable, struct coll *coll,
- uint32_t coll_id)
+ uint32_t coll_id, const char *path, uint32_t path_len)
{
assert(part_no < def->part_count);
assert(type < field_type_MAX);
def->is_nullable |= is_nullable;
+ def->has_json_paths |= path != NULL;
def->parts[part_no].is_nullable = is_nullable;
def->parts[part_no].fieldno = fieldno;
def->parts[part_no].type = type;
def->parts[part_no].coll = coll;
def->parts[part_no].coll_id = coll_id;
+ if (path != NULL) {
+ def->parts[part_no].path_len = path_len;
+ assert(def->parts[part_no].path != NULL);
+ memcpy(def->parts[part_no].path, path, path_len);
+ def->parts[part_no].path[path_len] = '\0';
+ } else {
+ def->parts[part_no].path_len = 0;
+ def->parts[part_no].path = NULL;
+ }
column_mask_set_fieldno(&def->column_mask, fieldno);
}
struct key_def *
key_def_new(const struct key_part_def *parts, uint32_t part_count)
{
- size_t sz = key_def_sizeof(part_count);
+ ssize_t sz = 0;
+ for (uint32_t i = 0; i < part_count; i++)
+ sz += parts[i].path != NULL ? strlen(parts[i].path) + 1 : 0;
+ sz = key_def_sizeof(part_count, sz);
struct key_def *def = calloc(1, sz);
if (def == NULL) {
diag_set(OutOfMemory, sz, "malloc", "struct key_def");
@@ -159,6 +204,7 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
def->part_count = part_count;
def->unique_part_count = part_count;
+ char *data = (char *)def + key_def_sizeof(part_count, 0);
for (uint32_t i = 0; i < part_count; i++) {
const struct key_part_def *part = &parts[i];
struct coll *coll = NULL;
@@ -172,15 +218,23 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
}
coll = coll_id->coll;
}
+ uint32_t path_len = 0;
+ if (part->path != NULL) {
+ path_len = strlen(part->path);
+ def->parts[i].path = data;
+ data += path_len + 1;
+ }
key_def_set_part(def, i, part->fieldno, part->type,
- part->is_nullable, coll, part->coll_id);
+ part->is_nullable, coll, part->coll_id,
+ part->path, path_len);
}
key_def_set_cmp(def);
return def;
}
-void
-key_def_dump_parts(const struct key_def *def, struct key_part_def *parts)
+int
+key_def_dump_parts(struct region *pool, const struct key_def *def,
+ struct key_part_def *parts)
{
for (uint32_t i = 0; i < def->part_count; i++) {
const struct key_part *part = &def->parts[i];
@@ -189,13 +243,27 @@ key_def_dump_parts(const struct key_def *def, struct key_part_def *parts)
part_def->type = part->type;
part_def->is_nullable = part->is_nullable;
part_def->coll_id = part->coll_id;
+ if (part->path != NULL) {
+ char *path = region_alloc(pool, part->path_len + 1);
+ if (path == NULL) {
+ diag_set(OutOfMemory, part->path_len + 1,
+ "region_alloc", "part_def->path");
+ return -1;
+ }
+ memcpy(path, part->path, part->path_len);
+ path[part->path_len] = '\0';
+ part_def->path = path;
+ } else {
+ part_def->path = NULL;
+}
}
+ return 0;
}
box_key_def_t *
box_key_def_new(uint32_t *fields, uint32_t *types, uint32_t part_count)
{
- size_t sz = key_def_sizeof(part_count);
+ size_t sz = key_def_sizeof(part_count, 0);
struct key_def *key_def = calloc(1, sz);
if (key_def == NULL) {
diag_set(OutOfMemory, sz, "malloc", "struct key_def");
@@ -208,7 +276,7 @@ box_key_def_new(uint32_t *fields, uint32_t *types, uint32_t part_count)
for (uint32_t item = 0; item < part_count; ++item) {
key_def_set_part(key_def, item, fields[item],
(enum field_type)types[item],
- false, NULL, COLL_NONE);
+ false, NULL, COLL_NONE, NULL, 0);
}
key_def_set_cmp(key_def);
return key_def;
@@ -255,6 +323,9 @@ key_part_cmp(const struct key_part *parts1, uint32_t part_count1,
if (part1->is_nullable != part2->is_nullable)
return part1->is_nullable <
part2->is_nullable ? -1 : 1;
+ int rc;
+ if ((rc = key_part_path_cmp(part1, part2)) != 0)
+ return rc;
}
return part_count1 < part_count2 ? -1 : part_count1 > part_count2;
}
@@ -286,8 +357,15 @@ key_def_snprint_parts(char *buf, int size, const struct key_part_def *parts,
for (uint32_t i = 0; i < part_count; i++) {
const struct key_part_def *part = &parts[i];
assert(part->type < field_type_MAX);
- SNPRINT(total, snprintf, buf, size, "%d, '%s'",
- (int)part->fieldno, field_type_strs[part->type]);
+ if (part->path != NULL) {
+ SNPRINT(total, snprintf, buf, size, "%d, '%s', '%s'",
+ (int)part->fieldno, part->path,
+ field_type_strs[part->type]);
+ } else {
+ SNPRINT(total, snprintf, buf, size, "%d, '%s'",
+ (int)part->fieldno,
+ field_type_strs[part->type]);
+ }
if (i < part_count - 1)
SNPRINT(total, snprintf, buf, size, ", ");
}
@@ -306,6 +384,8 @@ key_def_sizeof_parts(const struct key_part_def *parts, uint32_t part_count)
count++;
if (part->is_nullable)
count++;
+ if (part->path != NULL)
+ count++;
size += mp_sizeof_map(count);
size += mp_sizeof_str(strlen(PART_OPT_FIELD));
size += mp_sizeof_uint(part->fieldno);
@@ -320,6 +400,10 @@ key_def_sizeof_parts(const struct key_part_def *parts, uint32_t part_count)
size += mp_sizeof_str(strlen(PART_OPT_NULLABILITY));
size += mp_sizeof_bool(part->is_nullable);
}
+ if (part->path != NULL) {
+ size += mp_sizeof_str(strlen(PART_OPT_PATH));
+ size += mp_sizeof_str(strlen(part->path));
+ }
}
return size;
}
@@ -335,6 +419,8 @@ key_def_encode_parts(char *data, const struct key_part_def *parts,
count++;
if (part->is_nullable)
count++;
+ if (part->path != NULL)
+ count++;
data = mp_encode_map(data, count);
data = mp_encode_str(data, PART_OPT_FIELD,
strlen(PART_OPT_FIELD));
@@ -354,6 +440,12 @@ key_def_encode_parts(char *data, const struct key_part_def *parts,
strlen(PART_OPT_NULLABILITY));
data = mp_encode_bool(data, part->is_nullable);
}
+ if (part->path != NULL) {
+ data = mp_encode_str(data, PART_OPT_PATH,
+ strlen(PART_OPT_PATH));
+ data = mp_encode_str(data, part->path,
+ strlen(part->path));
+ }
}
return data;
}
@@ -414,6 +506,7 @@ key_def_decode_parts_166(struct key_part_def *parts, uint32_t part_count,
fields[part->fieldno].is_nullable :
key_part_def_default.is_nullable);
part->coll_id = COLL_NONE;
+ part->path = NULL;
}
return 0;
}
@@ -427,6 +520,7 @@ key_def_decode_parts(struct key_part_def *parts, uint32_t part_count,
return key_def_decode_parts_166(parts, part_count, data,
fields, field_count);
}
+ struct region *region = &fiber()->gc;
for (uint32_t i = 0; i < part_count; i++) {
struct key_part_def *part = &parts[i];
if (mp_typeof(**data) != MP_MAP) {
@@ -438,7 +532,7 @@ key_def_decode_parts(struct key_part_def *parts, uint32_t part_count,
*part = key_part_def_default;
if (opts_decode(part, part_def_reg, data,
ER_WRONG_INDEX_OPTIONS, i + TUPLE_INDEX_BASE,
- NULL) != 0)
+ region) != 0)
return -1;
if (part->type == field_type_MAX) {
diag_set(ClientError, ER_WRONG_INDEX_OPTIONS,
@@ -455,6 +549,34 @@ key_def_decode_parts(struct key_part_def *parts, uint32_t part_count,
"string and scalar parts");
return -1;
}
+ /*
+ * We should convert JSON path to canonical form
+ * to prevent indexing same field twice.
+ */
+ if (part->path != NULL) {
+ uint32_t path_len = strlen(part->path);
+ char *path_normalized =
+ region_alloc(region, 2.5 * path_len + 1);
+ if (path_normalized == NULL) {
+ diag_set(OutOfMemory, 2.5 * path_len + 1,
+ "region_alloc", "path");
+ return -1;
+ }
+ int rc = json_path_normalize(part->path, path_len,
+ path_normalized);
+ if (rc != 0) {
+ const char *err_msg =
+ tt_sprintf("invalid JSON path '%s': "
+ "path has invalid structure "
+ "(error at position %d)",
+ part->path, rc);
+ diag_set(ClientError, ER_WRONG_INDEX_OPTIONS,
+ part->fieldno + TUPLE_INDEX_BASE,
+ err_msg);
+ return -1;
+ }
+ part->path = path_normalized;
+ }
}
return 0;
}
@@ -479,6 +601,7 @@ key_def_decode_parts_160(struct key_part_def *parts, uint32_t part_count,
fields[part->fieldno].is_nullable :
key_part_def_default.is_nullable);
part->coll_id = COLL_NONE;
+ part->path = NULL;
}
return 0;
}
@@ -490,7 +613,8 @@ key_def_contains_part(const struct key_def *key_def,
const struct key_part *part = key_def->parts;
const struct key_part *end = part + key_def->part_count;
for (; part != end; part++) {
- if (part->fieldno == to_find->fieldno)
+ if (part->fieldno == to_find->fieldno &&
+ key_part_path_cmp(part, to_find) == 0)
return true;
}
return false;
@@ -516,18 +640,27 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
* Find and remove part duplicates, i.e. parts counted
* twice since they are present in both key defs.
*/
- const struct key_part *part = second->parts;
- const struct key_part *end = part + second->part_count;
+ size_t sz = 0;
+ const struct key_part *part = first->parts;
+ const struct key_part *end = part + first->part_count;
+ for (; part != end; part++) {
+ if (part->path != NULL)
+ sz += part->path_len + 1;
+ }
+ part = second->parts;
+ end = part + second->part_count;
for (; part != end; part++) {
if (key_def_contains_part(first, part))
--new_part_count;
+ else if (part->path != NULL)
+ sz += part->path_len + 1;
}
+ sz = key_def_sizeof(new_part_count, sz);
struct key_def *new_def;
- new_def = (struct key_def *)calloc(1, key_def_sizeof(new_part_count));
+ new_def = (struct key_def *)calloc(1, sz);
if (new_def == NULL) {
- diag_set(OutOfMemory, key_def_sizeof(new_part_count), "malloc",
- "new_def");
+ diag_set(OutOfMemory, sz, "malloc", "new_def");
return NULL;
}
new_def->part_count = new_part_count;
@@ -535,14 +668,21 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
new_def->is_nullable = first->is_nullable || second->is_nullable;
new_def->has_optional_parts = first->has_optional_parts ||
second->has_optional_parts;
+ /* Path data write position in the new key_def. */
+ char *data = (char *)new_def + key_def_sizeof(new_part_count, 0);
/* Write position in the new key def. */
uint32_t pos = 0;
/* Append first key def's parts to the new index_def. */
part = first->parts;
end = part + first->part_count;
for (; part != end; part++) {
+ if (part->path != NULL) {
+ new_def->parts[pos].path = data;
+ data += part->path_len + 1;
+ }
key_def_set_part(new_def, pos++, part->fieldno, part->type,
- part->is_nullable, part->coll, part->coll_id);
+ part->is_nullable, part->coll, part->coll_id,
+ part->path, part->path_len);
}
/* Set-append second key def's part to the new key def. */
@@ -551,8 +691,13 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
for (; part != end; part++) {
if (key_def_contains_part(first, part))
continue;
+ if (part->path != NULL) {
+ new_def->parts[pos].path = data;
+ data += part->path_len + 1;
+ }
key_def_set_part(new_def, pos++, part->fieldno, part->type,
- part->is_nullable, part->coll, part->coll_id);
+ part->is_nullable, part->coll, part->coll_id,
+ part->path, part->path_len);
}
key_def_set_cmp(new_def);
return new_def;
diff --git a/src/box/key_def.h b/src/box/key_def.h
index 37b9045..ca73015 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -54,6 +54,8 @@ struct key_part_def {
uint32_t coll_id;
/** True if a key part can store NULLs. */
bool is_nullable;
+ /** JSON path to data. */
+ const char *path;
};
extern const struct key_part_def key_part_def_default;
@@ -76,6 +78,13 @@ struct key_part {
struct coll *coll;
/** True if a part can store NULLs. */
bool is_nullable;
+ /**
+ * JSON path to data in 'canonical' form.
+ * Read json_path_normalize to get more details.
+ */
+ char *path;
+ /** The length of JSON path. */
+ uint32_t path_len;
};
struct key_def;
@@ -130,6 +139,8 @@ struct key_def {
uint32_t unique_part_count;
/** True, if at least one part can store NULL. */
bool is_nullable;
+ /** True, if some key part has JSON path. */
+ bool has_json_paths;
/**
* True, if some key parts can be absent in a tuple. These
* fields assumed to be MP_NIL.
@@ -223,9 +234,10 @@ box_tuple_compare_with_key(const box_tuple_t *tuple_a, const char *key_b,
/** \endcond public */
static inline size_t
-key_def_sizeof(uint32_t part_count)
+key_def_sizeof(uint32_t part_count, uint32_t paths_size)
{
- return sizeof(struct key_def) + sizeof(struct key_part) * part_count;
+ return sizeof(struct key_def) + sizeof(struct key_part) * part_count +
+ paths_size;
}
/**
@@ -238,8 +250,9 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count);
/**
* Dump part definitions of the given key def.
*/
-void
-key_def_dump_parts(const struct key_def *def, struct key_part_def *parts);
+int
+key_def_dump_parts(struct region *pool, const struct key_def *def,
+ struct key_part_def *parts);
/**
* Update 'has_optional_parts' of @a key_def with correspondence
@@ -351,6 +364,8 @@ key_validate_parts(const struct key_def *key_def, const char *key,
static inline bool
key_def_is_sequential(const struct key_def *key_def)
{
+ if (key_def->has_json_paths)
+ return false;
for (uint32_t part_id = 0; part_id < key_def->part_count; part_id++) {
if (key_def->parts[part_id].fieldno != part_id)
return false;
@@ -401,6 +416,14 @@ key_mp_type_validate(enum field_type key_type, enum mp_type mp_type,
return 0;
}
+static inline int
+key_part_path_cmp(const struct key_part *part1, const struct key_part *part2)
+{
+ if (part1->path_len != part2->path_len)
+ return part1->path_len - part2->path_len;
+ return memcmp(part1->path, part2->path, part1->path_len);
+}
+
/**
* Compare two key part arrays.
*
diff --git a/src/box/lua/space.cc b/src/box/lua/space.cc
index 25b7e36..875e51f 100644
--- a/src/box/lua/space.cc
+++ b/src/box/lua/space.cc
@@ -295,6 +295,11 @@ lbox_fillspace(struct lua_State *L, struct space *space, int i)
lua_pushnumber(L, part->fieldno + TUPLE_INDEX_BASE);
lua_setfield(L, -2, "fieldno");
+ if (part->path != NULL) {
+ lua_pushstring(L, part->path);
+ lua_setfield(L, -2, "path");
+ }
+
lua_pushboolean(L, part->is_nullable);
lua_setfield(L, -2, "is_nullable");
diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
index ae1f5a0..a35f5e7 100644
--- a/src/box/memtx_engine.c
+++ b/src/box/memtx_engine.c
@@ -1317,6 +1317,8 @@ memtx_index_def_change_requires_rebuild(struct index *index,
return true;
if (old_part->coll != new_part->coll)
return true;
+ if (key_part_path_cmp(old_part, new_part) != 0)
+ return true;
}
return false;
}
diff --git a/src/box/tuple.c b/src/box/tuple.c
index d7dbad3..2bc414f 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -161,10 +161,21 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
struct tuple_field *field = &format->fields[0];
uint32_t i = 0;
uint32_t defined_field_count = MIN(field_count, format->field_count);
+ size_t off_stack_size =
+ format->max_path_tree_depth * sizeof(const char *);
+ const char **off_stack = region_alloc(&fiber()->gc, off_stack_size);
+ if (off_stack == NULL) {
+ diag_set(OutOfMemory, off_stack_size, "region_alloc",
+ "off_stack");
+ return -1;
+ }
for (; i < defined_field_count; ++i, ++field) {
- if (key_mp_type_validate(field->type, mp_typeof(*tuple),
- ER_FIELD_TYPE, i + TUPLE_INDEX_BASE,
- field->is_nullable))
+ /*
+ * Don't fill field_map, just make types
+ * validations.
+ */
+ if (tuple_field_tree_parse_raw(field, tuple, NULL, i, NULL,
+ off_stack) != 0)
return -1;
mp_next(&tuple);
}
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index e21b009..9bff340 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -469,7 +469,8 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
struct key_part *part = key_def->parts;
const char *tuple_a_raw = tuple_data(tuple_a);
const char *tuple_b_raw = tuple_data(tuple_b);
- if (key_def->part_count == 1 && part->fieldno == 0) {
+ if (key_def->part_count == 1 && part->fieldno == 0 &&
+ part->path == NULL) {
/*
* First field can not be optional - empty tuples
* can not exist.
@@ -1027,7 +1028,7 @@ tuple_compare_create(const struct key_def *def)
}
}
assert(! def->has_optional_parts);
- if (!key_def_has_collation(def)) {
+ if (!key_def_has_collation(def) && !def->has_json_paths) {
/* Precalculated comparators don't use collation */
for (uint32_t k = 0;
k < sizeof(cmp_arr) / sizeof(cmp_arr[0]); k++) {
@@ -1247,7 +1248,7 @@ tuple_compare_with_key_create(const struct key_def *def)
}
}
assert(! def->has_optional_parts);
- if (!key_def_has_collation(def)) {
+ if (!key_def_has_collation(def) && !def->has_json_paths) {
/* Precalculated comparators don't use collation */
for (uint32_t k = 0;
k < sizeof(cmp_wk_arr) / sizeof(cmp_wk_arr[0]);
--git a/src/box/tuple_extract_key.cc b/src/box/tuple_extract_key.cc
index e9d7cac..cb4ae71 100644
--- a/src/box/tuple_extract_key.cc
+++ b/src/box/tuple_extract_key.cc
@@ -10,7 +10,8 @@ key_def_parts_are_sequential(const struct key_def *def, int i)
{
uint32_t fieldno1 = def->parts[i].fieldno + 1;
uint32_t fieldno2 = def->parts[i + 1].fieldno;
- return fieldno1 == fieldno2;
+ return fieldno1 == fieldno2 && def->parts[i].path == NULL &&
+ def->parts[i + 1].path == NULL;
}
/** True, if a key con contain two or more parts in sequence. */
@@ -241,7 +242,8 @@ tuple_extract_key_slowpath_raw(const char *data, const char *data_end,
if (!key_def_parts_are_sequential(key_def, i))
break;
}
- uint32_t end_fieldno = key_def->parts[i].fieldno;
+ const struct key_part *part = &key_def->parts[i];
+ uint32_t end_fieldno = part->fieldno;
if (fieldno < current_fieldno) {
/* Rewind. */
@@ -283,6 +285,17 @@ tuple_extract_key_slowpath_raw(const char *data, const char *data_end,
current_fieldno++;
}
}
+ const char *field_last, *field_end_last;
+ if (part->path != NULL) {
+ field_last = field;
+ field_end_last = field_end;
+ int rc = tuple_field_by_relative_path(&field,
+ part->path,
+ part->path_len);
+ assert(rc == 0);
+ field_end = field;
+ mp_next(&field_end);
+ }
memcpy(key_buf, field, field_end - field);
key_buf += field_end - field;
if (has_optional_parts && null_count != 0) {
@@ -291,6 +304,10 @@ tuple_extract_key_slowpath_raw(const char *data, const char *data_end,
} else {
assert(key_buf - key <= data_end - data);
}
+ if (part->path != NULL) {
+ field = field_last;
+ field_end = field_end_last;
+ }
}
if (key_size != NULL)
*key_size = (uint32_t)(key_buf - key);
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index a8aceef..30deac5 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -28,6 +28,7 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
+#include "fiber.h"
#include "json/path.h"
#include "tuple_format.h"
@@ -37,20 +38,17 @@ static intptr_t recycled_format_ids = FORMAT_ID_NIL;
static uint32_t formats_size = 0, formats_capacity = 0;
-static const struct tuple_field tuple_field_default = {
- FIELD_TYPE_ANY, TUPLE_OFFSET_SLOT_NIL, false, false,
-};
-
/**
* Calculate the size of tuple format allocation.
* @param field_count Count of tuple fields.
+ * @param path_size Size of paths extention.
* @retval Size of memory allocation.
*/
static inline uint32_t
-tuple_format_sizeof(uint32_t field_count)
+tuple_format_sizeof(uint32_t field_count, uint32_t paths_size)
{
return sizeof(struct tuple_format) +
- field_count * sizeof(struct tuple_field);
+ field_count * sizeof(struct tuple_field) + paths_size;
}
/**
@@ -134,6 +132,146 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
}
/**
+ * Initialize tuple_field with default values.
+ * @param field Fields definition.
+ * @param path_node JSON parser node to initialize JSON tree
+ * tuple_field. May be NULL for regular fields.
+ * @param path_node_hash Hash of @path_node calculated with
+ * json_path_node_hash.
+ */
+static inline void
+tuple_field_create(struct tuple_field *field, struct json_path_node *path_node,
+ uint32_t path_node_hash)
+{
+ memset(field, 0, sizeof(struct tuple_field));
+ field->type = FIELD_TYPE_ANY;
+ field->offset_slot = TUPLE_OFFSET_SLOT_NIL;
+ json_tree_node_create(&field->path_tree_node, path_node,
+ path_node_hash);
+}
+
+/**
+ * Release tuple_field resources.
+ * @param field Fields definition.
+ */
+static inline void
+tuple_field_destroy(struct tuple_field *field)
+{
+ json_tree_node_destroy(&field->path_tree_node);
+}
+
+/**
+ * Construct a new JSON tree path for tuple_field by path string.
+ * Make types checks for existent paths and initialize it with
+ * value allocated form offset_slot pool.
+ * @param parent Root field to build JSON path tree.
+ * @param path JSON path to data used to construct tree path.
+ * @param path_len Length of the path.
+ * @param fieldno Index of field used for error handling.
+ * @param field_type Tuple field type of leaf record.
+ * @param is_nullable Nullability of leaf record.
+ * @param current_slot Pointer to offset slot pool used to
+ * allocate leaf field offset_slot.
+ * @retval not NULL JSON tree leaf tuple record.
+ * @retval NULL on memory allocation or path conflict error.
+ * diag message is set.
+ */
+static struct tuple_field *
+tuple_field_tree_add_path(struct tuple_field *parent, const char *path,
+ uint32_t path_len, uint32_t fieldno,
+ enum field_type type, bool is_nullable,
+ int *current_slot)
+{
+ int rc;
+ enum field_type iterm_node_type = FIELD_TYPE_ANY;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct tuple_field *field = parent;
+ /* True if the last entry has just been allocated. */
+ bool is_last_new = false;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END) {
+ iterm_node_type = path_node.type == JSON_PATH_STR ?
+ FIELD_TYPE_MAP : FIELD_TYPE_ARRAY;
+ if (field->type != FIELD_TYPE_ANY &&
+ field->type != iterm_node_type)
+ goto error_type_mistmatch;
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct tuple_field *next_field =
+ json_tree_lookup_entry_by_path_node(field, &path_node,
+ path_node_hash,
+ struct tuple_field,
+ path_tree_node);
+ if (next_field == NULL) {
+ is_last_new = true;
+ next_field = malloc(sizeof(struct tuple_field));
+ if (next_field == NULL) {
+ diag_set(OutOfMemory,
+ sizeof(struct tuple_field),
+ "malloc", "next_field");
+ return NULL;
+ }
+ tuple_field_create(next_field, &path_node,
+ path_node_hash);
+ rc = json_tree_add(&field->path_tree_node,
+ &next_field->path_tree_node);
+ if (rc != 0) {
+ diag_set(OutOfMemory,
+ sizeof(struct json_tree_node),
+ "json_tree_add", "hashtable");
+ return NULL;
+ }
+ } else {
+ is_last_new = false;
+ }
+ field->type = iterm_node_type;
+ field = next_field;
+ }
+ /*
+ * Key parts path is already checked and normalized,
+ * so we don't need to handle parse error.
+ */
+ assert(rc == 0 && path_node.type == JSON_PATH_END);
+ assert(field != NULL);
+ if (!is_last_new) {
+ assert(field->offset_slot != TUPLE_OFFSET_SLOT_NIL);
+ /* Set up the strongest type and nullability. */
+ if (field->is_nullable != is_nullable)
+ field->is_nullable = false;
+ iterm_node_type = type;
+ if (field_type1_contains_type2(field->type, iterm_node_type)) {
+ field->type = iterm_node_type;
+ } else if (!field_type1_contains_type2(iterm_node_type,
+ field->type))
+ goto error_type_mistmatch;
+ } else {
+ field->is_nullable = is_nullable;
+ field->type = type;
+ field->offset_slot = (*current_slot = *current_slot - 1);
+
+ /* Update tree depths for path. */
+ uint32_t depth = 1;
+ for (struct json_tree_node *iter = field->path_tree_node.parent;
+ iter != NULL; iter = iter->parent, ++depth) {
+ struct tuple_field *record =
+ json_tree_entry(iter, struct tuple_field,
+ path_tree_node);
+ record->path_tree_depth =
+ MAX(record->path_tree_depth, depth);
+ }
+ }
+ return field;
+
+error_type_mistmatch: ;
+ diag_set(ClientError, ER_INDEX_PART_TYPE_MISMATCH,
+ tt_sprintf("%d", fieldno + TUPLE_INDEX_BASE),
+ field_type_strs[iterm_node_type],
+ field_type_strs[field->type]);
+ return NULL;
+}
+
+/**
* Add and initialize a new key_part to format.
* @param format Format to initialize.
* @param fields Fields definition if any.
@@ -141,6 +279,7 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
* @param part An index part to append.
* @param is_sequential Does this part sequential.
* @param current_slot Pointer to last offset slot.
+ * @param path_data Pointer to memory to store paths strings.
* @retval -1 On error.
* @retval 0 On success.
*/
@@ -148,10 +287,33 @@ static int
tuple_format_add_key_part(struct tuple_format *format,
const struct field_def *fields, uint32_t field_count,
const struct key_part *part, bool is_sequential,
- int *current_slot)
+ int *current_slot, char **path_data)
{
assert(part->fieldno < format->field_count);
struct tuple_field *field = &format->fields[part->fieldno];
+ if (part->path != NULL) {
+ field->is_key_part = true;
+ assert(!is_sequential);
+ /**
+ * Copy JSON path data to reserved area at the
+ * end of format allocation.
+ */
+ memcpy(*path_data, part->path, part->path_len);
+ (*path_data)[part->path_len] = '\0';
+ field = tuple_field_tree_add_path(field, *path_data,
+ part->path_len, part->fieldno,
+ part->type, part->is_nullable,
+ current_slot);
+ *path_data += part->path_len + 1;
+ if (field != NULL) {
+ format->max_path_tree_depth =
+ MAX(format->max_path_tree_depth,
+ field->path_tree_depth);
+ return 0;
+ } else {
+ return -1;
+ }
+ }
if (part->fieldno >= field_count) {
field->is_nullable = part->is_nullable;
} else if (field->is_nullable != part->is_nullable) {
@@ -214,18 +376,15 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
format->field_map_size = 0;
return 0;
}
- /* Initialize defined fields */
+ /* Update defined fields attributes. */
for (uint32_t i = 0; i < field_count; ++i) {
- format->fields[i].is_key_part = false;
format->fields[i].type = fields[i].type;
- format->fields[i].offset_slot = TUPLE_OFFSET_SLOT_NIL;
format->fields[i].is_nullable = fields[i].is_nullable;
}
- /* Initialize remaining fields */
- for (uint32_t i = field_count; i < format->field_count; i++)
- format->fields[i] = tuple_field_default;
int current_slot = 0;
+ char *paths_data =
+ (char *)format + tuple_format_sizeof(format->field_count, 0);
/* extract field type info */
for (uint16_t key_no = 0; key_no < key_count; ++key_no) {
@@ -238,7 +397,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
if (tuple_format_add_key_part(format, fields,
field_count, part,
is_sequential,
- ¤t_slot) != 0)
+ ¤t_slot,
+ &paths_data) != 0)
return -1;
}
}
@@ -305,6 +465,8 @@ static struct tuple_format *
tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
uint32_t space_field_count, struct tuple_dictionary *dict)
{
+ /* Size of area to store paths. */
+ uint32_t paths_size = 0;
uint32_t index_field_count = 0;
/* find max max field no */
for (uint16_t key_no = 0; key_no < key_count; ++key_no) {
@@ -314,10 +476,12 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
for (; part < pend; part++) {
index_field_count = MAX(index_field_count,
part->fieldno + 1);
+ if (part->path != NULL)
+ paths_size += part->path_len + 1;
}
}
uint32_t field_count = MAX(space_field_count, index_field_count);
- uint32_t total = tuple_format_sizeof(field_count);
+ uint32_t total = tuple_format_sizeof(field_count, paths_size);
struct tuple_format *format = (struct tuple_format *) malloc(total);
if (format == NULL) {
@@ -336,6 +500,10 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
format->dict = dict;
tuple_dictionary_ref(dict);
}
+ for (uint32_t i = 0; i < field_count; i++)
+ tuple_field_create(&format->fields[i], NULL, 0);
+ format->max_path_tree_depth = 1;
+ format->allocation_size = total;
format->refs = 0;
format->id = FORMAT_ID_NIL;
format->field_count = field_count;
@@ -349,6 +517,19 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
static inline void
tuple_format_destroy(struct tuple_format *format)
{
+ for (uint32_t i = 0; i < format->field_count; i++) {
+ struct tuple_field *field;
+ json_tree_foreach_entry_safe(field, &format->fields[i],
+ path_tree_node) {
+ tuple_field_destroy(field);
+ /*
+ * Root records has been allocated with
+ * format. Don't need to free them.
+ */
+ if (field != &format->fields[i])
+ free(field);
+ }
+ }
tuple_dictionary_unref(format->dict);
}
@@ -428,26 +609,201 @@ tuple_format1_can_store_format2_tuples(const struct tuple_format *format1,
return true;
}
+/**
+ * Build a copy of JSON tree that use a new source path string.
+ * Function use the assumption that format data was memcpy(ied)
+ * so new_data and old_data memory have similar paths order.
+ * @param new_root Root of a new JSON path tree.
+ * @param old_root Root of original JSON path tree to be copied.
+ * @param new_data Pointer to memory containing new paths strings.
+ * @param old_data Painter to memory containing old paths strings.
+ * @retval 0 On success, -1 On memory allocation error.
+ */
+static int
+tuple_field_tree_dup(struct tuple_field *new_root, struct tuple_field *old_root,
+ const char *new_data, const char *old_data)
+{
+ struct json_tree_node *new_prev = &new_root->path_tree_node;
+ struct json_tree_node *old_prev = &old_root->path_tree_node;
+ struct json_tree_node *old_curr;
+ json_tree_foreach_pre(old_curr, &old_root->path_tree_node) {
+ if (unlikely(old_curr == &old_root->path_tree_node))
+ continue;
+ struct tuple_field *new_field =
+ calloc(1, sizeof(struct tuple_field));
+ if (new_field == NULL) {
+ diag_set(OutOfMemory, sizeof(struct tuple_field),
+ "calloc", "new_field");
+ return -1;
+ }
+ *new_field = *json_tree_entry(old_curr, struct tuple_field,
+ path_tree_node);
+ /*
+ * Re-initialize JSON tree node with a new
+ * string pointer.
+ */
+ struct json_path_node node = old_curr->key;
+ if (node.type == JSON_PATH_STR)
+ node.str = new_data + (node.str - old_data);
+ assert(old_curr->key_hash == json_path_node_hash(&node));
+ json_tree_node_create(&new_field->path_tree_node, &node,
+ old_curr->key_hash);
+ /* Lookup for a valid parent node in new tree. */
+ while (old_prev != old_curr->parent) {
+ old_prev = old_prev->parent;
+ new_prev = new_prev->parent;
+ assert(old_prev != NULL);
+ }
+ assert(new_prev != NULL);
+ int rc = json_tree_add(new_prev, &new_field->path_tree_node);
+ if (rc != 0) {
+ diag_set(OutOfMemory, sizeof(struct json_tree_node),
+ "json_tree_add", "hashtable");
+ return -1;
+ }
+ old_prev = old_curr;
+ new_prev = &new_field->path_tree_node;
+ }
+ return 0;
+}
+
struct tuple_format *
tuple_format_dup(struct tuple_format *src)
{
- uint32_t total = sizeof(struct tuple_format) +
- src->field_count * sizeof(struct tuple_field);
+ uint32_t total = src->allocation_size;
struct tuple_format *format = (struct tuple_format *) malloc(total);
if (format == NULL) {
diag_set(OutOfMemory, total, "malloc", "tuple format");
return NULL;
}
memcpy(format, src, total);
+
+ char *src_data_begin =
+ (char *)src + tuple_format_sizeof(src->field_count, 0);
+ char *new_data_begin =
+ (char *)format + tuple_format_sizeof(format->field_count, 0);
+ /*
+ * Destroy references to source tree to prevent source
+ * corruption during resources release on dup failure.
+ */
+ for (uint32_t i = 0; i < src->field_count; i++)
+ json_tree_node_create(&format->fields[i].path_tree_node, NULL, 0);
+ for (uint32_t i = 0; i < src->field_count; i++) {
+ if (tuple_field_tree_dup(&format->fields[i], &src->fields[i],
+ new_data_begin, src_data_begin) != 0)
+ goto error;
+ }
tuple_dictionary_ref(format->dict);
format->id = FORMAT_ID_NIL;
format->refs = 0;
- if (tuple_format_register(format) != 0) {
- tuple_format_destroy(format);
- free(format);
- return NULL;
- }
+ if (tuple_format_register(format) != 0)
+ goto error;
return format;
+error:
+ tuple_format_destroy(format);
+ free(format);
+ return NULL;
+}
+
+int
+tuple_field_tree_parse_raw(struct tuple_field *field, const char *field_raw,
+ const char *tuple_raw, uint32_t fieldno,
+ uint32_t *field_map, const char **off_stack)
+{
+ /*
+ * Need to make root field type validation here to
+ * do not make prev != NULL ? prev->type : field->type
+ * each iteration.
+ */
+ if (key_mp_type_validate(field->type, mp_typeof(*field_raw),
+ ER_FIELD_TYPE, TUPLE_INDEX_BASE + fieldno,
+ field->is_nullable) != 0)
+ return -1;
+ const char *err_details = NULL;
+ /* Stack of JSON path nodes offsets. */
+ uint32_t off_stack_idx = 0;
+ const char *offset = field_raw;
+ struct tuple_field *prev = NULL;
+ struct tuple_field *curr;
+ json_tree_foreach_entry_pre(curr, field, path_tree_node) {
+ int rc = 0;
+ struct tuple_field *curr_parent =
+ json_tree_entry_safe(curr->path_tree_node.parent,
+ struct tuple_field,
+ path_tree_node);
+ /*
+ * If currect record parent is not previous
+ * record, there were a switch to other path tree
+ * path.
+ */
+ while (curr_parent != prev) {
+ assert(prev != NULL);
+ struct json_tree_node *prev_parent =
+ prev->path_tree_node.parent;
+ assert(prev_parent != NULL);
+ assert(off_stack_idx > 0);
+ prev = json_tree_entry(prev_parent, struct tuple_field,
+ path_tree_node);
+ /*
+ * Pop-up offset coresponding to the
+ * current field.
+ */
+ offset = off_stack[--off_stack_idx];
+ }
+ off_stack[off_stack_idx++] = offset;
+
+ struct json_path_node *key = &curr->path_tree_node.key;
+ if (key->type == JSON_PATH_NUM) {
+ assert(prev == NULL || prev->type == FIELD_TYPE_ARRAY);
+ rc = tuple_field_go_to_index(&offset, key->num);
+ if (rc != 0 && !curr->is_nullable) {
+ err_details =
+ tt_sprintf("array size %d is less than "
+ "size of %d defined in "
+ "index",
+ key->num, key->num + 1);
+ goto error_invalid_document;
+ }
+ } else if (key->type == JSON_PATH_STR) {
+ assert(prev == NULL || prev->type == FIELD_TYPE_MAP);
+ rc = tuple_field_go_to_key(&offset, key->str, key->len);
+ if (rc != 0 && !curr->is_nullable) {
+ err_details =
+ tt_sprintf("map doesn't contain key "
+ "'%.*s' defined in index",
+ key->len, key->str);
+ goto error_invalid_document;
+ }
+ }
+ /*
+ * We can't make this validation below as we
+ * didn't know, does this field present in tuple,
+ * as offset could point to the next field.
+ */
+ if (rc == 0 &&
+ key_mp_type_validate(curr->type, mp_typeof(*offset),
+ ER_FIELD_TYPE,
+ TUPLE_INDEX_BASE + fieldno,
+ curr->is_nullable) != 0)
+ return -1;
+ if (field_map != NULL &&
+ curr->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+ field_map[curr->offset_slot] =
+ rc == 0 ? (uint32_t)(offset - tuple_raw) : 0;
+ }
+ prev = curr;
+ }
+ return 0;
+
+error_invalid_document:
+ assert(err_details != NULL);
+ char *data_buff = tt_static_buf();
+ mp_snprint(data_buff, TT_STATIC_BUF_LEN, field_raw);
+ const char *err_msg =
+ tt_sprintf("invalid field %d document content '%s': %s",
+ fieldno + TUPLE_INDEX_BASE, data_buff, err_details);
+ diag_set(ClientError, ER_DATA_STRUCTURE_MISMATCH, err_msg);
+ return -1;
}
/** @sa declaration for details. */
@@ -477,34 +833,39 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
}
/* first field is simply accessible, so we do not store offset to it */
- enum mp_type mp_type = mp_typeof(*pos);
- const struct tuple_field *field = &format->fields[0];
- if (key_mp_type_validate(field->type, mp_type, ER_FIELD_TYPE,
- TUPLE_INDEX_BASE, field->is_nullable))
- return -1;
- mp_next(&pos);
- /* other fields...*/
- ++field;
- uint32_t i = 1;
- uint32_t defined_field_count = MIN(field_count, format->field_count);
- if (field_count < format->index_field_count) {
+ struct tuple_field *field = &format->fields[0];
+ uint32_t i = 0;
+ if (field_count < format->index_field_count ||
+ json_tree_node_children_count(&field->path_tree_node) == 0) {
/*
- * Nullify field map to be able to detect by 0,
- * which key fields are absent in tuple_field().
- */
+ * Nullify field map to be able to detect by 0,
+ * which key fields are absent in tuple_field().
+ */
memset((char *)field_map - format->field_map_size, 0,
- format->field_map_size);
+ format->field_map_size);
}
- for (; i < defined_field_count; ++i, ++field) {
- mp_type = mp_typeof(*pos);
+ if (json_tree_node_children_count(&field->path_tree_node) == 0) {
+ enum mp_type mp_type = mp_typeof(*pos);
if (key_mp_type_validate(field->type, mp_type, ER_FIELD_TYPE,
- i + TUPLE_INDEX_BASE,
- field->is_nullable))
+ TUPLE_INDEX_BASE, field->is_nullable))
+ return -1;
+ mp_next(&pos);
+ ++field;
+ ++i;
+ }
+ size_t off_stack_size =
+ format->max_path_tree_depth * sizeof(const char *);
+ const char **off_stack = region_alloc(&fiber()->gc, off_stack_size);
+ if (off_stack == NULL) {
+ diag_set(OutOfMemory, off_stack_size, "region_alloc",
+ "off_stack");
+ return -1;
+ }
+ uint32_t defined_field_count = MIN(field_count, format->field_count);
+ for (; i < defined_field_count; ++i, ++field) {
+ if (tuple_field_tree_parse_raw(field, pos, tuple, i, field_map,
+ off_stack) != 0)
return -1;
- if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
- field_map[field->offset_slot] =
- (uint32_t) (pos - tuple);
- }
mp_next(&pos);
}
return 0;
@@ -565,15 +926,7 @@ box_tuple_format_unref(box_tuple_format_t *format)
tuple_format_unref(format);
}
-/**
- * Retrieve field data by JSON path.
- * @param field Pointer to msgpack with data.
- * @param path The path to process.
- * @param path_len The length of the @path.
- * @retval 0 On success.
- * @retval >0 On path parsing error, invalid character position.
- */
-static inline int
+int
tuple_field_by_relative_path(const char **field, const char *path,
uint32_t path_len)
{
@@ -677,3 +1030,38 @@ error:
tt_sprintf("error in path on position %d", rc));
return -1;
}
+
+const char *
+tuple_field_by_part_raw(const struct tuple_format *format, const char *data,
+ const uint32_t *field_map, struct key_part *part)
+{
+ if (likely(part->path == NULL))
+ return tuple_field_raw(format, data, field_map, part->fieldno);
+
+ struct tuple_field *root_field =
+ unlikely(part->fieldno < format->field_count) ?
+ (struct tuple_field *)&format->fields[part->fieldno] : NULL;
+ struct tuple_field *field =
+ unlikely(root_field == NULL) ? NULL:
+ tuple_field_tree_lookup(root_field, part->path, part->path_len);
+ if (unlikely(field == NULL)) {
+ /*
+ * Legacy tuple having no field map for JSON
+ * index require full path parse.
+ */
+ const char *field_raw =
+ tuple_field_raw(format, data, field_map, part->fieldno);
+ if (unlikely(field_raw == NULL))
+ return NULL;
+ if (tuple_field_by_relative_path(&field_raw, part->path,
+ part->path_len) != 0)
+ return NULL;
+ return field_raw;
+ }
+ int32_t offset_slot = field->offset_slot;
+ assert(offset_slot < 0);
+ assert(-offset_slot * sizeof(uint32_t) <= format->field_map_size);
+ if (unlikely(field_map[offset_slot] == 0))
+ return NULL;
+ return data + field_map[offset_slot];
+}
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index 894620f..599e768 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -35,6 +35,7 @@
#include "field_def.h"
#include "errinj.h"
#include "tuple_dictionary.h"
+#include "json/tree.h"
#if defined(__cplusplus)
extern "C" {
@@ -108,6 +109,10 @@ struct tuple_field {
bool is_key_part;
/** True, if a field can store NULL. */
bool is_nullable;
+ /** JSON path tree max depth. */
+ uint32_t path_tree_depth;
+ /** JSON root path tree node for registered indexes. */
+ struct json_tree_node path_tree_node;
};
/**
@@ -157,6 +162,14 @@ struct tuple_format {
uint32_t min_field_count;
/* Length of 'fields' array. */
uint32_t field_count;
+ /** Size of format allocation. */
+ uint32_t allocation_size;
+ /**
+ * Maximum depth of JSON path tree. This value is used to
+ * allocate stack that used in pre order JSON path tree
+ * traversal.
+ */
+ uint32_t max_path_tree_depth;
/**
* Shared names storage used by all formats of a space.
*/
@@ -388,6 +401,38 @@ tuple_field_raw_by_name(struct tuple_format *format, const char *tuple,
}
/**
+ * Retrieve field data by JSON path.
+ * @param field Pointer to msgpack with data.
+ * @param path The path to process.
+ * @param path_len The length of the @path.
+ * @retval 0 On success.
+ * @retval >0 On path parsing error, invalid character position.
+ */
+int
+tuple_field_by_relative_path(const char **field, const char *path,
+ uint32_t path_len);
+
+/**
+ * Make tuple parsing doing JSON tree traversal. Make types
+ * validations. Init field_map for fields that have offset_slots.
+ * @param field Root field of path tree.
+ * @param field_raw Pointer to field data.
+ * @param tuple_raw Pointer to tuple data.
+ * May be NULL when field_map is NULL.
+ * @param fieldno Number of root field in tuple.
+ * @param field_map[out] Tuple field map to initialize.
+ * May be NULL if initialization is not
+ * required.
+ * @param off_stack Stack of intermediate nodes offsets.
+ * @retval 0 On success.
+ * @retval -1 On memory allocation or field parsing error.
+ */
+int
+tuple_field_tree_parse_raw(struct tuple_field *field, const char *field_raw,
+ const char *tuple_raw, uint32_t fieldno,
+ uint32_t *field_map, const char **off_stack);
+
+/**
* Get tuple field by its path.
* @param format Tuple format.
* @param tuple MessagePack tuple's body.
@@ -414,11 +459,25 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
* @param part Index part to use.
* @retval Field data if the field exists or NULL.
*/
-static inline const char *
+const char *
tuple_field_by_part_raw(const struct tuple_format *format, const char *data,
- const uint32_t *field_map, struct key_part *part)
+ const uint32_t *field_map, struct key_part *part);
+
+/**
+ * Lookup JSON path in tuple_field JSON paths tree.
+ * @param field Tuple field with JSON tree root.
+ * @param path JSON path string to lookup.
+ * @param path_len Length of path.
+ * @retval not NULL tuple_field pointer on success.
+ * @retval NULL On nothing has been found.
+ */
+static inline struct tuple_field *
+tuple_field_tree_lookup(struct tuple_field *field, const char *path,
+ uint32_t path_len)
{
- return tuple_field_raw(format, data, field_map, part->fieldno);
+ return json_tree_lookup_entry_by_path(field, path, path_len,
+ struct tuple_field,
+ path_tree_node);
}
#if defined(__cplusplus)
diff --git a/src/box/tuple_hash.cc b/src/box/tuple_hash.cc
index b394804..3486ce1 100644
--- a/src/box/tuple_hash.cc
+++ b/src/box/tuple_hash.cc
@@ -222,7 +222,7 @@ key_hash_slowpath(const char *key, struct key_def *key_def);
void
tuple_hash_func_set(struct key_def *key_def) {
- if (key_def->is_nullable)
+ if (key_def->is_nullable || key_def->has_json_paths)
goto slowpath;
/*
* Check that key_def defines sequential a key without holes
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index acfe86d..0a6ead9 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -975,6 +975,8 @@ vinyl_index_def_change_requires_rebuild(struct index *index,
return true;
if (!field_type1_contains_type2(new_part->type, old_part->type))
return true;
+ if (key_part_path_cmp(old_part, new_part) != 0)
+ return true;
}
return false;
}
diff --git a/src/box/vy_log.c b/src/box/vy_log.c
index fc8ede5..f396705 100644
--- a/src/box/vy_log.c
+++ b/src/box/vy_log.c
@@ -711,7 +711,8 @@ vy_log_record_dup(struct region *pool, const struct vy_log_record *src)
"struct key_part_def");
goto err;
}
- key_def_dump_parts(src->key_def, dst->key_parts);
+ if (key_def_dump_parts(pool, src->key_def, dst->key_parts) != 0)
+ goto err;
dst->key_part_count = src->key_def->part_count;
dst->key_def = NULL;
}
diff --git a/src/box/vy_point_lookup.c b/src/box/vy_point_lookup.c
index 7b704b8..9d5e220 100644
--- a/src/box/vy_point_lookup.c
+++ b/src/box/vy_point_lookup.c
@@ -196,8 +196,6 @@ vy_point_lookup(struct vy_lsm *lsm, struct vy_tx *tx,
const struct vy_read_view **rv,
struct tuple *key, struct tuple **ret)
{
- assert(tuple_field_count(key) >= lsm->cmp_def->part_count);
-
*ret = NULL;
double start_time = ev_monotonic_now(loop());
int rc = 0;
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index 08b8fb6..9c47b75 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -29,6 +29,7 @@
* SUCH DAMAGE.
*/
+#include "assoc.h"
#include "vy_stmt.h"
#include <stdlib.h>
@@ -349,6 +350,103 @@ vy_stmt_replace_from_upsert(const struct tuple *upsert)
return replace;
}
+/**
+ * Construct tuple field or calculate it's size. The fields_iov_ht
+ * is a hashtable that links leaf field records of field path
+ * tree and iovs that contain raw data. Function also fills the
+ * tuple field_map when write_data flag is set true.
+ */
+static void
+tuple_field_restore_raw(struct tuple_field *field, char *tuple_raw,
+ uint32_t *field_map, char **offset,
+ struct mh_i64ptr_t *fields_iov_ht, bool write_data)
+{
+ struct tuple_field *prev = NULL;
+ struct tuple_field *curr;
+ json_tree_foreach_entry_pre(curr, field, path_tree_node) {
+ struct json_tree_node *curr_node = &curr->path_tree_node;
+ uint32_t children_count =
+ json_tree_node_children_count(curr_node);
+ struct tuple_field *parent =
+ curr_node->parent == NULL ? NULL :
+ json_tree_entry(curr_node->parent, struct tuple_field,
+ path_tree_node);
+ if (parent != NULL && parent->type == FIELD_TYPE_ARRAY){
+ /*
+ * Fill unindexed array items with nulls.
+ * Gaps size calculated as a difference
+ * between sibling nodes.
+ */
+ uint32_t nulls_count = curr_node->key.num - 1;
+ if (prev != parent) {
+ struct json_tree_node *prev_node =
+ rlist_prev_entry(curr_node, sibling);
+ assert(prev_node != NULL);
+ nulls_count -= prev_node->key.num;
+ }
+ for (uint32_t i = 0; i < nulls_count; i++) {
+ *offset = !write_data ?
+ (*offset += mp_sizeof_nil()) :
+ mp_encode_nil(*offset);
+ }
+ } else if (parent != NULL && parent->type == FIELD_TYPE_MAP) {
+ const char *str = curr_node->key.str;
+ uint32_t len = curr_node->key.len;
+ *offset = !write_data ?
+ (*offset += mp_sizeof_str(len)) :
+ mp_encode_str(*offset, str, len);
+ }
+ /* Fill data. */
+ if (curr->type == FIELD_TYPE_ARRAY) {
+ /*
+ * As numeric records list is sorted in
+ * ascending order in JSON tree, last
+ * entry contain the biggest number
+ * matching the size of the array.
+ */
+ assert(children_count > 0);
+ struct json_tree_node *max_idx_node =
+ rlist_last_entry(&curr_node->children,
+ struct json_tree_node,
+ sibling);
+ uint32_t array_size = max_idx_node->key.num;
+ assert(array_size > 0);
+ *offset = !write_data ?
+ (*offset += mp_sizeof_array(array_size)) :
+ mp_encode_array(*offset, array_size);
+ } else if (curr->type == FIELD_TYPE_MAP) {
+ assert(children_count > 0);
+ *offset = !write_data ?
+ (*offset += mp_sizeof_map(children_count)) :
+ mp_encode_map(*offset, children_count);
+ } else {
+ /* Leaf record. */
+ assert(children_count == 0);
+ mh_int_t k = mh_i64ptr_find(fields_iov_ht,
+ (uint64_t)curr, NULL);
+ struct iovec *iov =
+ k != mh_end(fields_iov_ht) ?
+ mh_i64ptr_node(fields_iov_ht, k)->val : NULL;
+ if (iov == NULL) {
+ *offset = !write_data ?
+ (*offset += mp_sizeof_nil()) :
+ mp_encode_nil(*offset);
+ } else {
+ uint32_t data_offset = *offset - tuple_raw;
+ int32_t slot = curr->offset_slot;
+ if (write_data) {
+ memcpy(*offset, iov->iov_base,
+ iov->iov_len);
+ if (slot != TUPLE_OFFSET_SLOT_NIL)
+ field_map[slot] = data_offset;
+ }
+ *offset += iov->iov_len;
+ }
+ }
+ prev = curr;
+ }
+}
+
static struct tuple *
vy_stmt_new_surrogate_from_key(const char *key, enum iproto_type type,
const struct key_def *cmp_def,
@@ -357,51 +455,83 @@ vy_stmt_new_surrogate_from_key(const char *key, enum iproto_type type,
/* UPSERT can't be surrogate. */
assert(type != IPROTO_UPSERT);
struct region *region = &fiber()->gc;
+ struct tuple *stmt = NULL;
uint32_t field_count = format->index_field_count;
- struct iovec *iov = region_alloc(region, sizeof(*iov) * field_count);
+ uint32_t part_count = mp_decode_array(&key);
+ assert(part_count == cmp_def->part_count);
+ struct iovec *iov = region_alloc(region, sizeof(*iov) * part_count);
if (iov == NULL) {
- diag_set(OutOfMemory, sizeof(*iov) * field_count,
- "region", "iov for surrogate key");
+ diag_set(OutOfMemory, sizeof(*iov) * part_count, "region",
+ "iov for surrogate key");
return NULL;
}
- memset(iov, 0, sizeof(*iov) * field_count);
- uint32_t part_count = mp_decode_array(&key);
- assert(part_count == cmp_def->part_count);
- assert(part_count <= field_count);
- uint32_t nulls_count = field_count - cmp_def->part_count;
- uint32_t bsize = mp_sizeof_array(field_count) +
- mp_sizeof_nil() * nulls_count;
- for (uint32_t i = 0; i < part_count; ++i) {
- const struct key_part *part = &cmp_def->parts[i];
+ /* Hastable linking leaf field and corresponding iov. */
+ struct mh_i64ptr_t *fields_iov_ht = mh_i64ptr_new();
+ if (fields_iov_ht == NULL) {
+ diag_set(OutOfMemory, sizeof(struct mh_i64ptr_t),
+ "mh_i64ptr_new", "fields_iov_ht");
+ return NULL;
+ }
+ if (mh_i64ptr_reserve(fields_iov_ht, part_count, NULL) != 0) {
+ diag_set(OutOfMemory, part_count, "mh_i64ptr_reserve",
+ "fields_iov_ht");
+ goto end;
+ }
+ uint32_t bsize = mp_sizeof_array(field_count);
+ uint32_t nulls_count = field_count;
+ memset(iov, 0, sizeof(*iov) * part_count);
+ const struct key_part *part = cmp_def->parts;
+ for (uint32_t i = 0; i < part_count; ++i, ++part) {
assert(part->fieldno < field_count);
const char *svp = key;
- iov[part->fieldno].iov_base = (char *) key;
+ iov[i].iov_base = (char *) key;
mp_next(&key);
- iov[part->fieldno].iov_len = key - svp;
- bsize += key - svp;
+ iov[i].iov_len = key - svp;
+ struct tuple_field *field;
+ if (part->path == NULL) {
+ field = &format->fields[part->fieldno];
+ --nulls_count;
+ } else {
+ struct tuple_field *root_field =
+ &format->fields[part->fieldno];
+ field = tuple_field_tree_lookup(root_field, part->path,
+ part->path_len);
+ assert(field != NULL);
+ }
+ struct mh_i64ptr_node_t node = {(uint64_t)field, &iov[i]};
+ mh_int_t k = mh_i64ptr_put(fields_iov_ht, &node, NULL, NULL);
+ if (unlikely(k == mh_end(fields_iov_ht))) {
+ diag_set(OutOfMemory, part_count, "mh_i64ptr_put",
+ "fields_iov_ht");
+ goto end;
+ }
+ k = mh_i64ptr_find(fields_iov_ht, (uint64_t)field, NULL);
+ assert(k != mh_end(fields_iov_ht));
+ }
+ /* Calculate tuple size to make allocation. */
+ for (uint32_t i = 0; i < field_count; ++i) {
+ char *data = NULL;
+ tuple_field_restore_raw(&format->fields[i], NULL, NULL, &data,
+ fields_iov_ht, false);
+ bsize += data - (char *)NULL;
}
- struct tuple *stmt = vy_stmt_alloc(format, bsize);
+ stmt = vy_stmt_alloc(format, bsize);
if (stmt == NULL)
- return NULL;
+ goto end;
char *raw = (char *) tuple_data(stmt);
uint32_t *field_map = (uint32_t *) raw;
char *wpos = mp_encode_array(raw, field_count);
for (uint32_t i = 0; i < field_count; ++i) {
- const struct tuple_field *field = &format->fields[i];
- if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL)
- field_map[field->offset_slot] = wpos - raw;
- if (iov[i].iov_base == NULL) {
- wpos = mp_encode_nil(wpos);
- } else {
- memcpy(wpos, iov[i].iov_base, iov[i].iov_len);
- wpos += iov[i].iov_len;
- }
+ tuple_field_restore_raw(&format->fields[i], raw, field_map,
+ &wpos, fields_iov_ht, true);
}
- assert(wpos == raw + bsize);
+ assert(wpos <= raw + bsize);
vy_stmt_set_type(stmt, type);
+end:
+ mh_i64ptr_delete(fields_iov_ht);
return stmt;
}
diff --git a/test/box/misc.result b/test/box/misc.result
index 4ee4797..b1fda78 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -350,7 +350,7 @@ t;
- 'box.error.CANT_CREATE_COLLATION : 150'
- 'box.error.USER_EXISTS : 46'
- 'box.error.WAL_IO : 40'
- - 'box.error.PROC_RET : 21'
+ - 'box.error.RTREE_RECT : 101'
- 'box.error.PRIV_GRANTED : 89'
- 'box.error.CREATE_SPACE : 9'
- 'box.error.GRANT : 88'
@@ -361,7 +361,7 @@ t;
- 'box.error.VINYL_MAX_TUPLE_SIZE : 139'
- 'box.error.LOAD_FUNCTION : 99'
- 'box.error.INVALID_XLOG : 74'
- - 'box.error.READ_VIEW_ABORTED : 130'
+ - 'box.error.PRIV_NOT_GRANTED : 91'
- 'box.error.TRANSACTION_CONFLICT : 97'
- 'box.error.GUEST_USER_PASSWORD : 96'
- 'box.error.PROC_C : 102'
@@ -371,8 +371,8 @@ t;
- 'box.error.DROP_FUNCTION : 71'
- 'box.error.CFG : 59'
- 'box.error.NO_SUCH_FIELD : 37'
- - 'box.error.CONNECTION_TO_SELF : 117'
- - 'box.error.FUNCTION_MAX : 54'
+ - 'box.error.MORE_THAN_ONE_TUPLE : 41'
+ - 'box.error.PROC_LUA : 32'
- 'box.error.ILLEGAL_PARAMS : 1'
- 'box.error.PARTIAL_KEY : 136'
- 'box.error.SAVEPOINT_NO_TRANSACTION : 114'
@@ -400,34 +400,35 @@ t;
- 'box.error.UPDATE_ARG_TYPE : 26'
- 'box.error.CROSS_ENGINE_TRANSACTION : 81'
- 'box.error.FORMAT_MISMATCH_INDEX_PART : 27'
- - 'box.error.FUNCTION_TX_ACTIVE : 30'
- 'box.error.injection : table: <address>
- - 'box.error.ITERATOR_TYPE : 72'
+ - 'box.error.FUNCTION_TX_ACTIVE : 30'
+ - 'box.error.IDENTIFIER : 70'
+ - 'box.error.TRANSACTION_YIELD : 154'
- 'box.error.NO_SUCH_ENGINE : 57'
- 'box.error.COMMIT_IN_SUB_STMT : 122'
- - 'box.error.TRANSACTION_YIELD : 154'
- - 'box.error.UNSUPPORTED : 5'
- - 'box.error.LAST_DROP : 15'
+ - 'box.error.RELOAD_CFG : 58'
- 'box.error.SPACE_FIELD_IS_DUPLICATE : 149'
+ - 'box.error.LAST_DROP : 15'
+ - 'box.error.SEQUENCE_OVERFLOW : 147'
- 'box.error.DECOMPRESSION : 124'
- 'box.error.CREATE_SEQUENCE : 142'
- 'box.error.CREATE_USER : 43'
- - 'box.error.SEQUENCE_OVERFLOW : 147'
+ - 'box.error.FUNCTION_MAX : 54'
- 'box.error.INSTANCE_UUID_MISMATCH : 66'
- - 'box.error.RELOAD_CFG : 58'
+ - 'box.error.TUPLE_FORMAT_LIMIT : 16'
- 'box.error.SYSTEM : 115'
- 'box.error.KEY_PART_IS_TOO_LONG : 118'
- - 'box.error.MORE_THAN_ONE_TUPLE : 41'
- 'box.error.TRUNCATE_SYSTEM_SPACE : 137'
- - 'box.error.NO_SUCH_SAVEPOINT : 61'
- 'box.error.VY_QUOTA_TIMEOUT : 135'
- - 'box.error.PRIV_NOT_GRANTED : 91'
+ - 'box.error.NO_SUCH_SAVEPOINT : 61'
+ - 'box.error.PROTOCOL : 104'
+ - 'box.error.READ_VIEW_ABORTED : 130'
- 'box.error.WRONG_INDEX_OPTIONS : 108'
- 'box.error.INVALID_VYLOG_FILE : 133'
- 'box.error.INDEX_FIELD_COUNT_LIMIT : 127'
- - 'box.error.BEFORE_REPLACE_RET : 53'
+ - 'box.error.DATA_STRUCTURE_MISMATCH : 55'
- 'box.error.USER_MAX : 56'
- - 'box.error.INVALID_MSGPACK : 20'
+ - 'box.error.BEFORE_REPLACE_RET : 53'
- 'box.error.TUPLE_NOT_ARRAY : 22'
- 'box.error.KEY_PART_COUNT : 31'
- 'box.error.ALTER_SPACE : 12'
@@ -436,47 +437,47 @@ t;
- 'box.error.DROP_SEQUENCE : 144'
- 'box.error.INVALID_XLOG_ORDER : 76'
- 'box.error.UNKNOWN_REQUEST_TYPE : 48'
- - 'box.error.PROC_LUA : 32'
+ - 'box.error.PROC_RET : 21'
- 'box.error.SUB_STMT_MAX : 121'
- 'box.error.ROLE_NOT_GRANTED : 92'
- 'box.error.SPACE_EXISTS : 10'
- - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
+ - 'box.error.UNSUPPORTED : 5'
- 'box.error.MIN_FIELD_COUNT : 39'
- 'box.error.NO_SUCH_SPACE : 36'
- 'box.error.WRONG_INDEX_PARTS : 107'
- 'box.error.REPLICASET_UUID_MISMATCH : 63'
- 'box.error.UPDATE_FIELD : 29'
- 'box.error.INDEX_EXISTS : 85'
- - 'box.error.SPLICE : 25'
+ - 'box.error.DROP_SPACE : 11'
- 'box.error.COMPRESSION : 119'
- 'box.error.INVALID_ORDER : 68'
- - 'box.error.UNKNOWN : 0'
+ - 'box.error.SPLICE : 25'
- 'box.error.NO_SUCH_GROUP : 155'
- - 'box.error.TUPLE_FORMAT_LIMIT : 16'
+ - 'box.error.INVALID_MSGPACK : 20'
- 'box.error.DROP_PRIMARY_KEY : 17'
- 'box.error.NULLABLE_PRIMARY : 152'
- 'box.error.NO_SUCH_SEQUENCE : 145'
- 'box.error.INJECTION : 8'
- 'box.error.INVALID_UUID : 64'
- - 'box.error.IDENTIFIER : 70'
+ - 'box.error.NO_SUCH_ROLE : 82'
- 'box.error.TIMEOUT : 78'
+ - 'box.error.ITERATOR_TYPE : 72'
- 'box.error.REPLICA_MAX : 73'
- - 'box.error.NO_SUCH_ROLE : 82'
- - 'box.error.DROP_SPACE : 11'
+ - 'box.error.UNKNOWN : 0'
- 'box.error.MISSING_REQUEST_FIELD : 69'
- 'box.error.MISSING_SNAPSHOT : 93'
- 'box.error.WRONG_SPACE_OPTIONS : 111'
- 'box.error.READONLY : 7'
- - 'box.error.RTREE_RECT : 101'
+ - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
- 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
- 'box.error.NO_CONNECTION : 77'
- 'box.error.UNSUPPORTED_PRIV : 98'
- 'box.error.WRONG_SCHEMA_VERSION : 109'
- 'box.error.ROLLBACK_IN_SUB_STMT : 123'
- - 'box.error.PROTOCOL : 104'
- - 'box.error.INVALID_XLOG_TYPE : 125'
- - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
- 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
+ - 'box.error.CONNECTION_TO_SELF : 117'
+ - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+ - 'box.error.INVALID_XLOG_TYPE : 125'
...
test_run:cmd("setopt delimiter ''");
---
diff --git a/test/engine/tuple.result b/test/engine/tuple.result
index 35c700e..e551f1a 100644
--- a/test/engine/tuple.result
+++ b/test/engine/tuple.result
@@ -954,6 +954,377 @@ type(tuple:tomap().fourth)
s:drop()
---
...
+--
+-- gh-1012: Indexes for JSON-defined paths.
+--
+box.cfg()
+---
+...
+s = box.schema.space.create('withdata', {engine = engine})
+---
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO["fname"]'}, {3, 'str', path = '["FIO"].fname'}}})
+---
+- error: 'Can''t create or modify index ''test1'' in space ''withdata'': same key
+ part is indexed twice'
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 666}, {3, 'str', path = '["FIO"]["fname"]'}}})
+---
+- error: 'Wrong index options (field 2): ''path'' must be string'
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'map', path = 'FIO'}}})
+---
+- error: 'Can''t create or modify index ''test1'' in space ''withdata'': field type
+ ''map'' is not supported'
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'array', path = '[1]'}}})
+---
+- error: 'Can''t create or modify index ''test1'' in space ''withdata'': field type
+ ''array'' is not supported'
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO'}, {3, 'str', path = '["FIO"].fname'}}})
+---
+- error: Field 3 has type 'map' in one index, but type 'string' in another
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '[1].sname'}, {3, 'str', path = '["FIO"].fname'}}})
+---
+- error: Field 3 has type 'map' in one index, but type 'array' in another
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO....fname'}}})
+---
+- error: 'Wrong index options (field 3): invalid JSON path ''FIO....fname'': path
+ has invalid structure (error at position 5)'
+...
+idx = s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+---
+...
+assert(idx ~= nil)
+---
+- true
+...
+s:insert{7, 7, {town = 'London', FIO = 666}, 4, 5}
+---
+- error: 'Tuple field 3 type does not match one required by operation: expected map'
+...
+s:insert{7, 7, {town = 'London', FIO = {fname = 666, sname = 'Bond'}}, 4, 5}
+---
+- error: 'Tuple field 3 type does not match one required by operation: expected string'
+...
+s:insert{7, 7, {town = 'London', FIO = {fname = "James"}}, 4, 5}
+---
+- error: 'Tuple doesn''t math document structure: invalid field 3 document content
+ ''{"town": "London", "FIO": {"fname": "James"}}'': map doesn''t contain key ''sname''
+ defined in index'
+...
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+---
+- [7, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+---
+- error: Duplicate key exists in unique index 'test1' in space 'withdata'
+...
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond', data = "extra"}}, 4, 5}
+---
+- error: Duplicate key exists in unique index 'test1' in space 'withdata'
+...
+s:insert{7, 7, {town = 'Moscow', FIO = {fname = 'Max', sname = 'Isaev', data = "extra"}}, 4, 5}
+---
+- [7, 7, {'town': 'Moscow', 'FIO': {'fname': 'Max', 'data': 'extra', 'sname': 'Isaev'}},
+ 4, 5]
+...
+idx:select()
+---
+- - [7, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+ - [7, 7, {'town': 'Moscow', 'FIO': {'fname': 'Max', 'data': 'extra', 'sname': 'Isaev'}},
+ 4, 5]
+...
+idx:min()
+---
+- [7, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+idx:max()
+---
+- [7, 7, {'town': 'Moscow', 'FIO': {'fname': 'Max', 'data': 'extra', 'sname': 'Isaev'}},
+ 4, 5]
+...
+s:drop()
+---
+...
+s = box.schema.create_space('withdata', {engine = engine})
+---
+...
+parts = {}
+---
+...
+parts[1] = {1, 'unsigned', path='[2]'}
+---
+...
+pk = s:create_index('pk', {parts = parts})
+---
+...
+s:insert{{1, 2}, 3}
+---
+- [[1, 2], 3]
+...
+s:upsert({{box.null, 2}}, {{'+', 2, 5}})
+---
+...
+s:get(2)
+---
+- [[1, 2], 8]
+...
+s:drop()
+---
+...
+-- Create index on space with data
+s = box.schema.space.create('withdata', {engine = engine})
+---
+...
+pk = s:create_index('primary', { type = 'tree' })
+---
+...
+s:insert{1, 7, {town = 'London', FIO = 1234}, 4, 5}
+---
+- [1, 7, {'town': 'London', 'FIO': 1234}, 4, 5]
+...
+s:insert{2, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+---
+- [2, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+s:insert{3, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+---
+- [3, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+s:insert{4, 7, {town = 'London', FIO = {1,2,3}}, 4, 5}
+---
+- [4, 7, {'town': 'London', 'FIO': [1, 2, 3]}, 4, 5]
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+---
+- error: 'Tuple field 3 type does not match one required by operation: expected map'
+...
+_ = s:delete(1)
+---
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+---
+- error: Duplicate key exists in unique index 'test1' in space 'withdata'
+...
+_ = s:delete(2)
+---
+...
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+---
+- error: 'Tuple field 3 type does not match one required by operation: expected map'
+...
+_ = s:delete(4)
+---
+...
+idx = s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]', is_nullable = true}, {3, 'str', path = '["FIO"]["sname"]'}, {3, 'str', path = '["FIO"]["extra"]', is_nullable = true}}})
+---
+...
+assert(idx ~= nil)
+---
+- true
+...
+s:create_index('test2', {parts = {{2, 'number'}, {3, 'number', path = '["FIO"]["fname"]'}}})
+---
+- error: Field 3 has type 'number' in one index, but type 'string' in another
+...
+idx2 = s:create_index('test2', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}}})
+---
+...
+assert(idx2 ~= nil)
+---
+- true
+...
+t = s:insert{5, 7, {town = 'Matrix', FIO = {fname = 'Agent', sname = 'Smith'}}, 4, 5}
+---
+...
+idx:select()
+---
+- - [5, 7, {'town': 'Matrix', 'FIO': {'fname': 'Agent', 'sname': 'Smith'}}, 4, 5]
+ - [3, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+idx:min()
+---
+- [5, 7, {'town': 'Matrix', 'FIO': {'fname': 'Agent', 'sname': 'Smith'}}, 4, 5]
+...
+idx:max()
+---
+- [3, 7, {'town': 'London', 'FIO': {'fname': 'James', 'sname': 'Bond'}}, 4, 5]
+...
+idx:drop()
+---
+...
+s:drop()
+---
+...
+-- Test complex JSON indexes
+s = box.schema.space.create('withdata', {engine = engine})
+---
+...
+parts = {}
+---
+...
+parts[1] = {1, 'str', path='[3][2].a'}
+---
+...
+parts[2] = {1, 'unsigned', path = '[3][1]'}
+---
+...
+parts[3] = {2, 'str', path = '[2].d[1]'}
+---
+...
+pk = s:create_index('primary', { type = 'tree', parts = parts})
+---
+...
+s:insert{{1, 2, {3, {3, a = 'str', b = 5}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {1, 2, 3}}
+---
+- [[1, 2, [3, {1: 3, 'a': 'str', 'b': 5}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6,
+ [1, 2, 3]]
+...
+s:insert{{1, 2, {3, {a = 'str', b = 1}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6}
+---
+- error: Duplicate key exists in unique index 'primary' in space 'withdata'
+...
+parts = {}
+---
+...
+parts[1] = {4, 'unsigned', path='[1]', is_nullable = false}
+---
+...
+parts[2] = {4, 'unsigned', path='[2]', is_nullable = true}
+---
+...
+parts[3] = {4, 'unsigned', path='[4]', is_nullable = true}
+---
+...
+trap_idx = s:create_index('trap', { type = 'tree', parts = parts})
+---
+...
+s:insert{{1, 2, {3, {3, a = 'str2', b = 5}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {}}
+---
+- error: 'Tuple doesn''t math document structure: invalid field 4 document content
+ ''[]'': array size 1 is less than size of 2 defined in index'
+...
+parts = {}
+---
+...
+parts[1] = {1, 'unsigned', path='[3][2].b' }
+---
+...
+parts[2] = {3, 'unsigned'}
+---
+...
+crosspart_idx = s:create_index('crosspart', { parts = parts})
+---
+...
+s:insert{{1, 2, {3, {a = 'str2', b = 2}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {9, 2, 3}}
+---
+- [[1, 2, [3, {'a': 'str2', 'b': 2}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [9,
+ 2, 3]]
+...
+parts = {}
+---
+...
+parts[1] = {1, 'unsigned', path='[3][2].b'}
+---
+...
+num_idx = s:create_index('numeric', {parts = parts})
+---
+...
+s:insert{{1, 2, {3, {a = 'str3', b = 9}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {0}}
+---
+- [[1, 2, [3, {'a': 'str3', 'b': 9}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [0]]
+...
+num_idx:get(2)
+---
+- [[1, 2, [3, {'a': 'str2', 'b': 2}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [9,
+ 2, 3]]
+...
+num_idx:select()
+---
+- - [[1, 2, [3, {'a': 'str2', 'b': 2}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [
+ 9, 2, 3]]
+ - [[1, 2, [3, {1: 3, 'a': 'str', 'b': 5}]], ['c', {'d': ['e', 'f'], 'e': 'g'}],
+ 6, [1, 2, 3]]
+ - [[1, 2, [3, {'a': 'str3', 'b': 9}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [
+ 0]]
+...
+num_idx:max()
+---
+- [[1, 2, [3, {'a': 'str3', 'b': 9}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [0]]
+...
+num_idx:min()
+---
+- [[1, 2, [3, {'a': 'str2', 'b': 2}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [9,
+ 2, 3]]
+...
+assert(crosspart_idx:max() == num_idx:max())
+---
+- true
+...
+assert(crosspart_idx:min() == num_idx:min())
+---
+- true
+...
+trap_idx:max()
+---
+- [[1, 2, [3, {'a': 'str2', 'b': 2}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [9,
+ 2, 3]]
+...
+trap_idx:min()
+---
+- [[1, 2, [3, {'a': 'str3', 'b': 9}]], ['c', {'d': ['e', 'f'], 'e': 'g'}], 6, [0]]
+...
+s:drop()
+---
+...
+s = box.schema.space.create('withdata', {engine = engine})
+---
+...
+pk_simplified = s:create_index('primary', { type = 'tree', parts = {{1, 'unsigned'}}})
+---
+...
+assert(pk_simplified.path == box.NULL)
+---
+- true
+...
+idx = s:create_index('idx', {parts = {{2, 'integer', path = 'a'}}})
+---
+...
+s:insert{31, {a = 1, aa = -1}}
+---
+- [31, {'a': 1, 'aa': -1}]
+...
+s:insert{22, {a = 2, aa = -2}}
+---
+- [22, {'a': 2, 'aa': -2}]
+...
+s:insert{13, {a = 3, aa = -3}}
+---
+- [13, {'a': 3, 'aa': -3}]
+...
+idx:select()
+---
+- - [31, {'a': 1, 'aa': -1}]
+ - [22, {'a': 2, 'aa': -2}]
+ - [13, {'a': 3, 'aa': -3}]
+...
+idx:alter({parts = {{2, 'integer', path = 'aa'}}})
+---
+...
+idx:select()
+---
+- - [13, {'a': 3, 'aa': -3}]
+ - [22, {'a': 2, 'aa': -2}]
+ - [31, {'a': 1, 'aa': -1}]
+...
+s:drop()
+---
+...
engine = nil
---
...
diff --git a/test/engine/tuple.test.lua b/test/engine/tuple.test.lua
index edc3dab..e865c67 100644
--- a/test/engine/tuple.test.lua
+++ b/test/engine/tuple.test.lua
@@ -312,5 +312,111 @@ tuple:tomap().fourth
type(tuple:tomap().fourth)
s:drop()
+--
+-- gh-1012: Indexes for JSON-defined paths.
+--
+box.cfg()
+s = box.schema.space.create('withdata', {engine = engine})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO["fname"]'}, {3, 'str', path = '["FIO"].fname'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 666}, {3, 'str', path = '["FIO"]["fname"]'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'map', path = 'FIO'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'array', path = '[1]'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO'}, {3, 'str', path = '["FIO"].fname'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '[1].sname'}, {3, 'str', path = '["FIO"].fname'}}})
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = 'FIO....fname'}}})
+idx = s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+assert(idx ~= nil)
+s:insert{7, 7, {town = 'London', FIO = 666}, 4, 5}
+s:insert{7, 7, {town = 'London', FIO = {fname = 666, sname = 'Bond'}}, 4, 5}
+s:insert{7, 7, {town = 'London', FIO = {fname = "James"}}, 4, 5}
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+s:insert{7, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond', data = "extra"}}, 4, 5}
+s:insert{7, 7, {town = 'Moscow', FIO = {fname = 'Max', sname = 'Isaev', data = "extra"}}, 4, 5}
+idx:select()
+idx:min()
+idx:max()
+s:drop()
+
+s = box.schema.create_space('withdata', {engine = engine})
+parts = {}
+parts[1] = {1, 'unsigned', path='[2]'}
+pk = s:create_index('pk', {parts = parts})
+s:insert{{1, 2}, 3}
+s:upsert({{box.null, 2}}, {{'+', 2, 5}})
+s:get(2)
+s:drop()
+
+-- Create index on space with data
+s = box.schema.space.create('withdata', {engine = engine})
+pk = s:create_index('primary', { type = 'tree' })
+s:insert{1, 7, {town = 'London', FIO = 1234}, 4, 5}
+s:insert{2, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+s:insert{3, 7, {town = 'London', FIO = {fname = 'James', sname = 'Bond'}}, 4, 5}
+s:insert{4, 7, {town = 'London', FIO = {1,2,3}}, 4, 5}
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+_ = s:delete(1)
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+_ = s:delete(2)
+s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}, {3, 'str', path = '["FIO"]["sname"]'}}})
+_ = s:delete(4)
+idx = s:create_index('test1', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]', is_nullable = true}, {3, 'str', path = '["FIO"]["sname"]'}, {3, 'str', path = '["FIO"]["extra"]', is_nullable = true}}})
+assert(idx ~= nil)
+s:create_index('test2', {parts = {{2, 'number'}, {3, 'number', path = '["FIO"]["fname"]'}}})
+idx2 = s:create_index('test2', {parts = {{2, 'number'}, {3, 'str', path = '["FIO"]["fname"]'}}})
+assert(idx2 ~= nil)
+t = s:insert{5, 7, {town = 'Matrix', FIO = {fname = 'Agent', sname = 'Smith'}}, 4, 5}
+idx:select()
+idx:min()
+idx:max()
+idx:drop()
+s:drop()
+
+-- Test complex JSON indexes
+s = box.schema.space.create('withdata', {engine = engine})
+parts = {}
+parts[1] = {1, 'str', path='[3][2].a'}
+parts[2] = {1, 'unsigned', path = '[3][1]'}
+parts[3] = {2, 'str', path = '[2].d[1]'}
+pk = s:create_index('primary', { type = 'tree', parts = parts})
+s:insert{{1, 2, {3, {3, a = 'str', b = 5}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {1, 2, 3}}
+s:insert{{1, 2, {3, {a = 'str', b = 1}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6}
+parts = {}
+parts[1] = {4, 'unsigned', path='[1]', is_nullable = false}
+parts[2] = {4, 'unsigned', path='[2]', is_nullable = true}
+parts[3] = {4, 'unsigned', path='[4]', is_nullable = true}
+trap_idx = s:create_index('trap', { type = 'tree', parts = parts})
+s:insert{{1, 2, {3, {3, a = 'str2', b = 5}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {}}
+parts = {}
+parts[1] = {1, 'unsigned', path='[3][2].b' }
+parts[2] = {3, 'unsigned'}
+crosspart_idx = s:create_index('crosspart', { parts = parts})
+s:insert{{1, 2, {3, {a = 'str2', b = 2}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {9, 2, 3}}
+parts = {}
+parts[1] = {1, 'unsigned', path='[3][2].b'}
+num_idx = s:create_index('numeric', {parts = parts})
+s:insert{{1, 2, {3, {a = 'str3', b = 9}}}, {'c', {d = {'e', 'f'}, e = 'g'}}, 6, {0}}
+num_idx:get(2)
+num_idx:select()
+num_idx:max()
+num_idx:min()
+assert(crosspart_idx:max() == num_idx:max())
+assert(crosspart_idx:min() == num_idx:min())
+trap_idx:max()
+trap_idx:min()
+s:drop()
+
+s = box.schema.space.create('withdata', {engine = engine})
+pk_simplified = s:create_index('primary', { type = 'tree', parts = {{1, 'unsigned'}}})
+assert(pk_simplified.path == box.NULL)
+idx = s:create_index('idx', {parts = {{2, 'integer', path = 'a'}}})
+s:insert{31, {a = 1, aa = -1}}
+s:insert{22, {a = 2, aa = -2}}
+s:insert{13, {a = 3, aa = -3}}
+idx:select()
+idx:alter({parts = {{2, 'integer', path = 'aa'}}})
+idx:select()
+s:drop()
+
engine = nil
test_run = nil
--
2.7.4
^ permalink raw reply [flat|nested] 24+ messages in thread* [PATCH v4 13/14] box: introduce offset slot cache in key_part
2018-10-11 7:58 [PATCH v4 00/14] box: indexes by JSON path Kirill Shcherbatov
` (3 preceding siblings ...)
2018-10-11 7:58 ` [PATCH v4 12/14] box: tune tuple_field_raw_by_path for indexed data Kirill Shcherbatov
@ 2018-10-11 7:58 ` Kirill Shcherbatov
2018-10-11 7:58 ` [PATCH v4 14/14] box: specify indexes in user-friendly form Kirill Shcherbatov
` (8 subsequent siblings)
13 siblings, 0 replies; 24+ messages in thread
From: Kirill Shcherbatov @ 2018-10-11 7:58 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov
Same key_part could be used in different formats multiple
times, so different field->offset_slot would be allocated.
In most scenarios we work with series of tuples of same
format, and (in general) format lookup for field would be
expensive operation for JSON-paths defined in key_part.
New slot_cache field in key_part structure and epoch-based
mechanism to validate it actuality should be effective
approach to improve performance.
Part of #1012.
---
src/box/alter.cc | 7 +++--
src/box/blackhole.c | 5 ++--
src/box/engine.h | 11 ++++----
src/box/key_def.c | 12 +++++++--
src/box/key_def.h | 11 ++++++++
src/box/memtx_engine.c | 4 +--
src/box/memtx_space.c | 5 ++--
src/box/memtx_space.h | 2 +-
src/box/schema.cc | 4 +--
src/box/space.c | 4 +--
src/box/space.h | 8 +++---
src/box/sysview.c | 3 ++-
src/box/tuple.c | 4 +--
src/box/tuple_format.c | 60 ++++++++++++++++++++++++++---------------
src/box/tuple_format.h | 6 ++++-
src/box/vinyl.c | 7 ++---
src/box/vy_lsm.c | 40 +++++++++++++++++++++++++--
test/unit/vy_iterators_helper.c | 6 ++---
test/unit/vy_mem.c | 2 +-
test/unit/vy_point_lookup.c | 2 +-
20 files changed, 145 insertions(+), 58 deletions(-)
diff --git a/src/box/alter.cc b/src/box/alter.cc
index 4ac44c2..ded5f5b 100644
--- a/src/box/alter.cc
+++ b/src/box/alter.cc
@@ -883,7 +883,10 @@ alter_space_do(struct txn *txn, struct alter_space *alter)
* Create a new (empty) space for the new definition.
* Sic: the triggers are not moved over yet.
*/
- alter->new_space = space_new_xc(alter->space_def, &alter->key_list);
+ alter->new_space =
+ space_new_xc(alter->space_def, &alter->key_list,
+ alter->old_space->format != NULL ?
+ alter->old_space->format->epoch + 1 : 1);
/*
* Copy the replace function, the new space is at the same recovery
* phase as the old one. This hack is especially necessary for
@@ -1604,7 +1607,7 @@ on_replace_dd_space(struct trigger * /* trigger */, void *event)
auto def_guard =
make_scoped_guard([=] { space_def_delete(def); });
RLIST_HEAD(empty_list);
- struct space *space = space_new_xc(def, &empty_list);
+ struct space *space = space_new_xc(def, &empty_list, 0);
/**
* The new space must be inserted in the space
* cache right away to achieve linearisable
diff --git a/src/box/blackhole.c b/src/box/blackhole.c
index f979304..517daf9 100644
--- a/src/box/blackhole.c
+++ b/src/box/blackhole.c
@@ -135,7 +135,7 @@ blackhole_engine_shutdown(struct engine *engine)
static struct space *
blackhole_engine_create_space(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
if (!rlist_empty(key_list)) {
diag_set(ClientError, ER_UNSUPPORTED, "Blackhole", "indexes");
@@ -152,7 +152,8 @@ blackhole_engine_create_space(struct engine *engine, struct space_def *def,
/* Allocate tuples on runtime arena, but check space format. */
struct tuple_format *format;
format = tuple_format_new(&tuple_format_runtime->vtab, NULL, 0, 0,
- def->fields, def->field_count, def->dict);
+ def->fields, def->field_count, def->dict,
+ epoch);
if (format == NULL) {
free(space);
return NULL;
diff --git a/src/box/engine.h b/src/box/engine.h
index 5b96c74..0e8c76c 100644
--- a/src/box/engine.h
+++ b/src/box/engine.h
@@ -72,7 +72,8 @@ struct engine_vtab {
void (*shutdown)(struct engine *);
/** Allocate a new space instance. */
struct space *(*create_space)(struct engine *engine,
- struct space_def *def, struct rlist *key_list);
+ struct space_def *def, struct rlist *key_list,
+ uint64_t epoch);
/**
* Write statements stored in checkpoint @vclock to @stream.
*/
@@ -237,9 +238,9 @@ engine_find(const char *name)
static inline struct space *
engine_create_space(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
- return engine->vtab->create_space(engine, def, key_list);
+ return engine->vtab->create_space(engine, def, key_list, epoch);
}
static inline int
@@ -390,9 +391,9 @@ engine_find_xc(const char *name)
static inline struct space *
engine_create_space_xc(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
- struct space *space = engine_create_space(engine, def, key_list);
+ struct space *space = engine_create_space(engine, def, key_list, epoch);
if (space == NULL)
diag_raise();
return space;
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 1b32387..f0f0313 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -176,6 +176,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
def->parts[part_no].type = type;
def->parts[part_no].coll = coll;
def->parts[part_no].coll_id = coll_id;
+ def->parts[part_no].offset_slot = TUPLE_OFFSET_SLOT_NIL;
+ def->parts[part_no].offset_slot_epoch = 0;
if (path != NULL) {
def->parts[part_no].path_len = path_len;
assert(def->parts[part_no].path != NULL);
@@ -680,9 +682,12 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
new_def->parts[pos].path = data;
data += part->path_len + 1;
}
- key_def_set_part(new_def, pos++, part->fieldno, part->type,
+ key_def_set_part(new_def, pos, part->fieldno, part->type,
part->is_nullable, part->coll, part->coll_id,
part->path, part->path_len);
+ new_def->parts[pos].offset_slot_epoch = part->offset_slot_epoch;
+ new_def->parts[pos].offset_slot = part->offset_slot;
+ pos++;
}
/* Set-append second key def's part to the new key def. */
@@ -695,9 +700,12 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
new_def->parts[pos].path = data;
data += part->path_len + 1;
}
- key_def_set_part(new_def, pos++, part->fieldno, part->type,
+ key_def_set_part(new_def, pos, part->fieldno, part->type,
part->is_nullable, part->coll, part->coll_id,
part->path, part->path_len);
+ new_def->parts[pos].offset_slot_epoch = part->offset_slot_epoch;
+ new_def->parts[pos].offset_slot = part->offset_slot;
+ pos++;
}
key_def_set_cmp(new_def);
return new_def;
diff --git a/src/box/key_def.h b/src/box/key_def.h
index ca73015..8271cee 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -85,6 +85,17 @@ struct key_part {
char *path;
/** The length of JSON path. */
uint32_t path_len;
+ /**
+ * Epoch of offset slot cache. Initialized with
+ * incremental epoch of format on caching it's field's
+ * offset_slot via tuple_field_by_part_raw to speed up
+ * access on subsequent calls with same format.
+ * Cache is expected to use "the newest format is most
+ * relevant" strategy.
+ */
+ uint64_t offset_slot_epoch;
+ /** Cache with format's field offset slot. */
+ int32_t offset_slot;
};
struct key_def;
diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
index a35f5e7..6051cc7 100644
--- a/src/box/memtx_engine.c
+++ b/src/box/memtx_engine.c
@@ -358,10 +358,10 @@ memtx_engine_end_recovery(struct engine *engine)
static struct space *
memtx_engine_create_space(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
struct memtx_engine *memtx = (struct memtx_engine *)engine;
- return memtx_space_new(memtx, def, key_list);
+ return memtx_space_new(memtx, def, key_list, epoch);
}
static int
diff --git a/src/box/memtx_space.c b/src/box/memtx_space.c
index 08ae0da..3ac606f 100644
--- a/src/box/memtx_space.c
+++ b/src/box/memtx_space.c
@@ -884,7 +884,7 @@ static const struct space_vtab memtx_space_vtab = {
struct space *
memtx_space_new(struct memtx_engine *memtx,
- struct space_def *def, struct rlist *key_list)
+ struct space_def *def, struct rlist *key_list, uint64_t epoch)
{
struct memtx_space *memtx_space = malloc(sizeof(*memtx_space));
if (memtx_space == NULL) {
@@ -910,7 +910,8 @@ memtx_space_new(struct memtx_engine *memtx,
struct tuple_format *format =
tuple_format_new(&memtx_tuple_format_vtab, keys, key_count, 0,
- def->fields, def->field_count, def->dict);
+ def->fields, def->field_count, def->dict,
+ epoch);
if (format == NULL) {
free(memtx_space);
return NULL;
diff --git a/src/box/memtx_space.h b/src/box/memtx_space.h
index 7dc3410..b5bec0c 100644
--- a/src/box/memtx_space.h
+++ b/src/box/memtx_space.h
@@ -79,7 +79,7 @@ memtx_space_replace_all_keys(struct space *, struct tuple *, struct tuple *,
struct space *
memtx_space_new(struct memtx_engine *memtx,
- struct space_def *def, struct rlist *key_list);
+ struct space_def *def, struct rlist *key_list, uint64_t epoch);
#if defined(__cplusplus)
} /* extern "C" */
diff --git a/src/box/schema.cc b/src/box/schema.cc
index 67dbd8c..e5763fa 100644
--- a/src/box/schema.cc
+++ b/src/box/schema.cc
@@ -221,7 +221,7 @@ sc_space_new(uint32_t id, const char *name,
struct rlist key_list;
rlist_create(&key_list);
rlist_add_entry(&key_list, index_def, link);
- struct space *space = space_new_xc(def, &key_list);
+ struct space *space = space_new_xc(def, &key_list, 0);
(void) space_cache_replace(space);
if (replace_trigger)
trigger_add(&space->on_replace, replace_trigger);
@@ -380,7 +380,7 @@ schema_init()
space_def_delete(def);
});
RLIST_HEAD(key_list);
- struct space *space = space_new_xc(def, &key_list);
+ struct space *space = space_new_xc(def, &key_list, 0);
space_cache_replace(space);
init_system_space(space);
trigger_run_xc(&on_alter_space, space);
diff --git a/src/box/space.c b/src/box/space.c
index 871cc67..2e4df74 100644
--- a/src/box/space.c
+++ b/src/box/space.c
@@ -181,12 +181,12 @@ fail:
}
struct space *
-space_new(struct space_def *def, struct rlist *key_list)
+space_new(struct space_def *def, struct rlist *key_list, uint64_t epoch)
{
struct engine *engine = engine_find(def->engine_name);
if (engine == NULL)
return NULL;
- return engine_create_space(engine, def, key_list);
+ return engine_create_space(engine, def, key_list, epoch);
}
void
diff --git a/src/box/space.h b/src/box/space.h
index 8888ec8..068ea4b 100644
--- a/src/box/space.h
+++ b/src/box/space.h
@@ -378,10 +378,11 @@ struct field_def;
* Allocate and initialize a space.
* @param space_def Space definition.
* @param key_list List of index_defs.
+ * @param epoch Last epoch to initialize format.
* @retval Space object.
*/
struct space *
-space_new(struct space_def *space_def, struct rlist *key_list);
+space_new(struct space_def *space_def, struct rlist *key_list, uint64_t epoch);
/** Destroy and free a space. */
void
@@ -416,9 +417,10 @@ int generic_space_prepare_alter(struct space *, struct space *);
} /* extern "C" */
static inline struct space *
-space_new_xc(struct space_def *space_def, struct rlist *key_list)
+space_new_xc(struct space_def *space_def, struct rlist *key_list,
+ uint64_t epoch)
{
- struct space *space = space_new(space_def, key_list);
+ struct space *space = space_new(space_def, key_list, epoch);
if (space == NULL)
diag_raise();
return space;
diff --git a/src/box/sysview.c b/src/box/sysview.c
index a636c68..d35ff71 100644
--- a/src/box/sysview.c
+++ b/src/box/sysview.c
@@ -504,8 +504,9 @@ sysview_engine_shutdown(struct engine *engine)
static struct space *
sysview_engine_create_space(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
+ (void)epoch;
struct space *space = (struct space *)calloc(1, sizeof(*space));
if (space == NULL) {
diag_set(OutOfMemory, sizeof(*space),
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 2bc414f..6fbd9aa 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -234,7 +234,7 @@ tuple_init(field_name_hash_f hash)
* Create a format for runtime tuples
*/
tuple_format_runtime = tuple_format_new(&tuple_format_runtime_vtab,
- NULL, 0, 0, NULL, 0, NULL);
+ NULL, 0, 0, NULL, 0, NULL, 0);
if (tuple_format_runtime == NULL)
return -1;
@@ -406,7 +406,7 @@ box_tuple_format_new(struct key_def **keys, uint16_t key_count)
{
box_tuple_format_t *format =
tuple_format_new(&tuple_format_runtime_vtab,
- keys, key_count, 0, NULL, 0, NULL);
+ keys, key_count, 0, NULL, 0, NULL, 0);
if (format != NULL)
tuple_format_ref(format);
return format;
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 4738eb9..bdd802a 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -502,6 +502,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
}
for (uint32_t i = 0; i < field_count; i++)
tuple_field_create(&format->fields[i], NULL, 0);
+ format->epoch = 0;
format->max_path_tree_depth = 1;
format->allocation_size = total;
format->refs = 0;
@@ -545,7 +546,8 @@ struct tuple_format *
tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys,
uint16_t key_count, uint16_t extra_size,
const struct field_def *space_fields,
- uint32_t space_field_count, struct tuple_dictionary *dict)
+ uint32_t space_field_count, struct tuple_dictionary *dict,
+ uint64_t epoch)
{
struct tuple_format *format =
tuple_format_alloc(keys, key_count, space_field_count, dict);
@@ -555,6 +557,7 @@ tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys,
format->engine = NULL;
format->extra_size = extra_size;
format->is_temporary = false;
+ format->epoch = epoch;
if (tuple_format_register(format) < 0) {
tuple_format_destroy(format);
free(format);
@@ -1050,27 +1053,42 @@ tuple_field_by_part_raw(const struct tuple_format *format, const char *data,
if (likely(part->path == NULL))
return tuple_field_raw(format, data, field_map, part->fieldno);
- struct tuple_field *root_field =
- unlikely(part->fieldno < format->field_count) ?
- (struct tuple_field *)&format->fields[part->fieldno] : NULL;
- struct tuple_field *field =
- unlikely(root_field == NULL) ? NULL:
- tuple_field_tree_lookup(root_field, part->path, part->path_len);
- if (unlikely(field == NULL)) {
- /*
- * Legacy tuple having no field map for JSON
- * index require full path parse.
- */
- const char *field_raw =
- tuple_field_raw(format, data, field_map, part->fieldno);
- if (unlikely(field_raw == NULL))
- return NULL;
- if (tuple_field_by_relative_path(&field_raw, part->path,
- part->path_len) != 0)
- return NULL;
- return field_raw;
+ int32_t offset_slot;
+ if (likely(part->offset_slot_epoch == format->epoch)) {
+ assert(format->epoch != 0);
+ offset_slot = part->offset_slot;
+ } else {
+ struct tuple_field *root_field =
+ unlikely(part->fieldno < format->field_count) ?
+ (struct tuple_field *)&format->fields[part->fieldno] :
+ NULL;
+ struct tuple_field *field =
+ unlikely(root_field == NULL) ? NULL:
+ tuple_field_tree_lookup(root_field, part->path,
+ part->path_len);
+ if (unlikely(field == NULL)) {
+ /*
+ * Legacy tuple having no field map for JSON
+ * index require full path parse.
+ */
+ const char *field_raw =
+ tuple_field_raw(format, data, field_map,
+ part->fieldno);
+ if (unlikely(field_raw == NULL))
+ return NULL;
+ if (tuple_field_by_relative_path(&field_raw, part->path,
+ part->path_len) != 0)
+ return NULL;
+ return field_raw;
+ }
+ offset_slot = field->offset_slot;
+ /* Cache offset_slot if required. */
+ if (part->offset_slot_epoch < format->epoch) {
+ assert(format->epoch != 0);
+ part->offset_slot = offset_slot;
+ part->offset_slot_epoch = format->epoch;
+ }
}
- int32_t offset_slot = field->offset_slot;
assert(offset_slot < 0);
assert(-offset_slot * sizeof(uint32_t) <= format->field_map_size);
if (unlikely(field_map[offset_slot] == 0))
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index 599e768..005f70b 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -120,6 +120,8 @@ struct tuple_field {
* Tuple format describes how tuple is stored and information about its fields
*/
struct tuple_format {
+ /** Counter that grows incrementally on space rebuild. */
+ uint64_t epoch;
/** Virtual function table */
struct tuple_format_vtab vtab;
/** Pointer to engine-specific data. */
@@ -220,6 +222,7 @@ tuple_format_unref(struct tuple_format *format)
* @param extra_size Extra bytes to reserve in tuples metadata.
* @param space_fields Array of fields, defined in a space format.
* @param space_field_count Length of @a space_fields.
+ * @param epoch Epoch of new format.
*
* @retval not NULL Tuple format.
* @retval NULL Memory error.
@@ -228,7 +231,8 @@ struct tuple_format *
tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys,
uint16_t key_count, uint16_t extra_size,
const struct field_def *space_fields,
- uint32_t space_field_count, struct tuple_dictionary *dict);
+ uint32_t space_field_count, struct tuple_dictionary *dict,
+ uint64_t epoch);
/**
* Check, if @a format1 can store any tuples of @a format2. For
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 0a6ead9..807cd9e 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -578,7 +578,7 @@ vinyl_engine_check_space_def(struct space_def *def)
static struct space *
vinyl_engine_create_space(struct engine *engine, struct space_def *def,
- struct rlist *key_list)
+ struct rlist *key_list, uint64_t epoch)
{
struct space *space = malloc(sizeof(*space));
if (space == NULL) {
@@ -604,7 +604,8 @@ vinyl_engine_create_space(struct engine *engine, struct space_def *def,
struct tuple_format *format =
tuple_format_new(&vy_tuple_format_vtab, keys, key_count, 0,
- def->fields, def->field_count, def->dict);
+ def->fields, def->field_count, def->dict,
+ epoch);
if (format == NULL) {
free(space);
return NULL;
@@ -3025,7 +3026,7 @@ vy_send_lsm(struct vy_join_ctx *ctx, struct vy_lsm_recovery_info *lsm_info)
if (ctx->key_def == NULL)
goto out;
ctx->format = tuple_format_new(&vy_tuple_format_vtab, &ctx->key_def,
- 1, 0, NULL, 0, NULL);
+ 1, 0, NULL, 0, NULL, 0);
if (ctx->format == NULL)
goto out_free_key_def;
tuple_format_ref(ctx->format);
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index de5ad31..c549f4b 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -61,7 +61,7 @@ vy_lsm_env_create(struct vy_lsm_env *env, const char *path,
void *upsert_thresh_arg)
{
env->key_format = tuple_format_new(&vy_tuple_format_vtab,
- NULL, 0, 0, NULL, 0, NULL);
+ NULL, 0, 0, NULL, 0, NULL, 0);
if (env->key_format == NULL)
return -1;
tuple_format_ref(env->key_format);
@@ -155,9 +155,45 @@ vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
} else {
lsm->disk_format = tuple_format_new(&vy_tuple_format_vtab,
&cmp_def, 1, 0, NULL, 0,
- NULL);
+ NULL, format->epoch);
if (lsm->disk_format == NULL)
goto fail_format;
+ /*
+ * Tuple formats should be compatible to make
+ * epoch-based caching work.
+ */
+ int32_t min_offset_slot = 0;
+ struct tuple_field *dst_fields = lsm->disk_format->fields;
+ struct tuple_field *src_fields = format->fields;
+ struct key_part *part = cmp_def->parts;
+ struct key_part *part_end = part + cmp_def->part_count;
+ for (; part < part_end; part++) {
+ struct tuple_field *dst_field =
+ &dst_fields[part->fieldno];
+ struct tuple_field *src_field =
+ &src_fields[part->fieldno];
+ if (dst_field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+ src_field = &format->fields[part->fieldno];
+ } else if (part->path != NULL) {
+ src_field =
+ tuple_field_tree_lookup(src_field,
+ part->path,
+ part->path_len);
+ assert(src_field != NULL);
+ dst_field =
+ tuple_field_tree_lookup(dst_field,
+ part->path,
+ part->path_len);
+ assert(dst_field != NULL);
+ } else {
+ continue;
+ }
+ if (src_field->offset_slot == TUPLE_OFFSET_SLOT_NIL)
+ continue;
+ dst_field->offset_slot = src_field->offset_slot;
+ min_offset_slot = MIN(src_field->offset_slot, min_offset_slot);
+ }
+ lsm->disk_format->field_map_size = -min_offset_slot * sizeof(uint32_t);
}
tuple_format_ref(lsm->disk_format);
diff --git a/test/unit/vy_iterators_helper.c b/test/unit/vy_iterators_helper.c
index 40d8d6a..bfef6a2 100644
--- a/test/unit/vy_iterators_helper.c
+++ b/test/unit/vy_iterators_helper.c
@@ -22,7 +22,7 @@ vy_iterator_C_test_init(size_t cache_size)
vy_cache_env_create(&cache_env, cord_slab_cache());
vy_cache_env_set_quota(&cache_env, cache_size);
vy_key_format = tuple_format_new(&vy_tuple_format_vtab, NULL, 0, 0,
- NULL, 0, NULL);
+ NULL, 0, NULL, 0);
tuple_format_ref(vy_key_format);
size_t mem_size = 64 * 1024 * 1024;
@@ -210,7 +210,7 @@ create_test_mem(struct key_def *def)
struct key_def * const defs[] = { def };
struct tuple_format *format =
tuple_format_new(&vy_tuple_format_vtab, defs, def->part_count,
- 0, NULL, 0, NULL);
+ 0, NULL, 0, NULL, 0);
fail_if(format == NULL);
/* Create format with column mask */
@@ -234,7 +234,7 @@ create_test_cache(uint32_t *fields, uint32_t *types,
assert(*def != NULL);
vy_cache_create(cache, &cache_env, *def, true);
*format = tuple_format_new(&vy_tuple_format_vtab, def, 1, 0, NULL, 0,
- NULL);
+ NULL, 0);
tuple_format_ref(*format);
}
diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c
index 967aabe..d797b3d 100644
--- a/test/unit/vy_mem.c
+++ b/test/unit/vy_mem.c
@@ -78,7 +78,7 @@ test_iterator_restore_after_insertion()
/* Create format */
struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab,
&key_def, 1, 0, NULL, 0,
- NULL);
+ NULL, 0);
assert(format != NULL);
tuple_format_ref(format);
diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c
index dd33bbe..73afbd5 100644
--- a/test/unit/vy_point_lookup.c
+++ b/test/unit/vy_point_lookup.c
@@ -85,7 +85,7 @@ test_basic()
vy_cache_create(&cache, &cache_env, key_def, true);
struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab,
&key_def, 1, 0, NULL, 0,
- NULL);
+ NULL, 0);
isnt(format, NULL, "tuple_format_new is not NULL");
tuple_format_ref(format);
--
2.7.4
^ permalink raw reply [flat|nested] 24+ messages in thread* [PATCH v4 08/14] lib: implement JSON tree class for json library
2018-10-11 7:58 [PATCH v4 00/14] box: indexes by JSON path Kirill Shcherbatov
` (11 preceding siblings ...)
2018-10-11 7:58 ` [PATCH v4 07/14] box: drop format const qualifier in *init_field_map Kirill Shcherbatov
@ 2018-10-11 7:58 ` Kirill Shcherbatov
2018-10-16 8:26 ` Vladimir Davydov
2018-10-11 7:58 ` [PATCH v4 09/14] lib: introduce json_path_normalize routine Kirill Shcherbatov
13 siblings, 1 reply; 24+ messages in thread
From: Kirill Shcherbatov @ 2018-10-11 7:58 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov
New JSON tree class would store JSON paths for tuple fields
for registered non-plain indexes. It is a hierarchical data
structure that organize JSON nodes produced by parser.
Class provides API to lookup node by path and iterate over the
tree.
JSON Indexes patch require such functionality to make lookup
for tuple_fields by path, make initialization of field map and
build vynyl_stmt msgpack for secondary index via JSON tree
iteration.
Need for #1012.
---
src/lib/json/CMakeLists.txt | 2 +
src/lib/json/tree.c | 300 ++++++++++++++++++++++++++++++++++++++++++++
src/lib/json/tree.h | 260 ++++++++++++++++++++++++++++++++++++++
test/unit/json_path.c | 204 +++++++++++++++++++++++++++++-
test/unit/json_path.result | 48 ++++++-
5 files changed, 812 insertions(+), 2 deletions(-)
create mode 100644 src/lib/json/tree.c
create mode 100644 src/lib/json/tree.h
diff --git a/src/lib/json/CMakeLists.txt b/src/lib/json/CMakeLists.txt
index 203fe6f..9eaba37 100644
--- a/src/lib/json/CMakeLists.txt
+++ b/src/lib/json/CMakeLists.txt
@@ -1,6 +1,8 @@
set(lib_sources
path.c
+ tree.c
)
set_source_files_compile_flags(${lib_sources})
add_library(json_path STATIC ${lib_sources})
+target_link_libraries(json_path misc)
diff --git a/src/lib/json/tree.c b/src/lib/json/tree.c
new file mode 100644
index 0000000..2f82287
--- /dev/null
+++ b/src/lib/json/tree.c
@@ -0,0 +1,300 @@
+
+/*
+ * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <string.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "small/rlist.h"
+#include "trivia/util.h"
+#include "tree.h"
+#include "path.h"
+#include "third_party/PMurHash.h"
+
+
+/**
+ * Hash table: json_path_node => json_tree_node.
+ */
+struct mh_json_tree_node {
+ struct json_path_node key;
+ uint32_t key_hash;
+ struct json_tree_node *node;
+};
+
+/**
+ * Compare hash records of two json tree nodes. Return 0 if equal.
+ */
+static inline int
+mh_json_tree_node_cmp(const struct mh_json_tree_node *a,
+ const struct mh_json_tree_node *b)
+{
+ if (a->key.type != b->key.type)
+ return a->key.type - b->key.type;
+ if (a->key.type == JSON_PATH_STR) {
+ if (a->key.len != b->key.len)
+ return a->key.len - b->key.len;
+ return memcmp(a->key.str, b->key.str, a->key.len);
+ } else if (a->key.type == JSON_PATH_NUM) {
+ return a->key_hash - b->key_hash;
+ }
+ unreachable();
+}
+
+#define MH_SOURCE 1
+#define mh_name _json_tree_node
+#define mh_key_t struct mh_json_tree_node *
+#define mh_node_t struct mh_json_tree_node
+#define mh_arg_t void *
+#define mh_hash(a, arg) ((a)->key_hash)
+#define mh_hash_key(a, arg) ((a)->key_hash)
+#define mh_cmp(a, b, arg) (mh_json_tree_node_cmp((a), (b)))
+#define mh_cmp_key(a, b, arg) mh_cmp(a, b, arg)
+#include "salad/mhash.h"
+
+static const uint32_t json_path_node_hash_seed = 13U;
+
+uint32_t
+json_path_node_hash(struct json_path_node *key)
+{
+ uint32_t h = json_path_node_hash_seed;
+ uint32_t carry = 0;
+ const void *data;
+ uint32_t data_size;
+ if (key->type == JSON_PATH_STR) {
+ data = key->str;
+ data_size = key->len;
+ } else if (key->type == JSON_PATH_NUM) {
+ data = &key->num;
+ data_size = sizeof(key->num);
+ } else {
+ unreachable();
+ }
+ PMurHash32_Process(&h, &carry, data, data_size);
+ return PMurHash32_Result(h, carry, data_size);
+}
+
+void
+json_tree_node_create(struct json_tree_node *node,
+ struct json_path_node *path_node, uint32_t path_node_hash)
+{
+ assert(path_node == NULL ||
+ path_node_hash == json_path_node_hash(path_node));
+ memset(node, 0, sizeof(struct json_tree_node));
+ if (path_node != NULL) {
+ node->key = *path_node;
+ node->key_hash = path_node_hash;
+ } else {
+ node->key.type = JSON_PATH_END;
+ }
+ rlist_create(&node->sibling);
+ rlist_create(&node->children);
+}
+
+uint32_t
+json_tree_node_children_count(struct json_tree_node *node)
+{
+ return node->child_by_path_node != NULL ?
+ mh_size(node->child_by_path_node) : 0;
+}
+
+void
+json_tree_node_destroy(struct json_tree_node *node)
+{
+ if (node->child_by_path_node != NULL)
+ mh_json_tree_node_delete(node->child_by_path_node);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree_node *parent,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash)
+{
+ if (unlikely(parent->child_by_path_node == NULL))
+ return NULL;
+ struct mh_json_tree_node info;
+ info.key = *path_node;
+ info.key_hash = path_node_hash;
+ mh_int_t id =
+ mh_json_tree_node_find(parent->child_by_path_node, &info, NULL);
+ if (id == mh_end(parent->child_by_path_node))
+ return NULL;
+ struct mh_json_tree_node *ht_node =
+ mh_json_tree_node_node(parent->child_by_path_node, id);
+ assert(ht_node == NULL || ht_node->node != NULL);
+ struct json_tree_node *ret = ht_node != NULL ? ht_node->node : NULL;
+ assert(ret == NULL || ret->parent == parent);
+ return ret;
+}
+
+int
+json_tree_add(struct json_tree_node *parent, struct json_tree_node *node)
+{
+ assert(node->parent == NULL);
+ if (unlikely(parent->child_by_path_node == NULL)) {
+ parent->child_by_path_node = mh_json_tree_node_new();
+ if (parent->child_by_path_node == NULL)
+ return -1;
+ }
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == NULL);
+ struct mh_json_tree_node ht_node;
+ ht_node.key = node->key;
+ ht_node.key_hash = node->key_hash;
+ ht_node.node = node;
+ mh_int_t rc = mh_json_tree_node_put(parent->child_by_path_node,
+ &ht_node, NULL, NULL);
+ if (rc == mh_end(parent->child_by_path_node))
+ return -1;
+ node->parent = parent;
+ if (node->key.type == JSON_PATH_NUM) {
+ /*
+ * Insert an entry into the list, keeping the
+ * numerical values in ascending order.
+ */
+ struct json_tree_node *curr_entry = NULL;
+ struct rlist *prev_rlist_node = &parent->children;
+ rlist_foreach_entry(curr_entry, &parent->children, sibling) {
+ assert(curr_entry->key.type == JSON_PATH_NUM);
+ if (curr_entry->key.num >= node->key.num)
+ break;
+ prev_rlist_node = &curr_entry->sibling;
+ }
+ rlist_add(prev_rlist_node, &node->sibling);
+ } else {
+ rlist_add(&parent->children, &node->sibling);
+ }
+ return 0;
+}
+
+void
+json_tree_remove(struct json_tree_node *parent, struct json_tree_node *node)
+{
+ assert(node->parent == parent);
+ assert(parent->child_by_path_node != NULL);
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == node);
+ rlist_del(&node->sibling);
+ struct mh_json_tree_node info;
+ info.key = node->key;
+ info.key_hash = node->key_hash;
+ mh_int_t id =
+ mh_json_tree_node_find(parent->child_by_path_node, &info, NULL);
+ assert(id != mh_end(parent->child_by_path_node));
+ mh_json_tree_node_del(parent->child_by_path_node, id, NULL);
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == NULL);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree_node *parent, const char *path,
+ uint32_t path_len)
+{
+ if (unlikely(parent->child_by_path_node == NULL))
+ return NULL;
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct json_tree_node *ret = parent;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END && ret != NULL) {
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct json_tree_node *node =
+ json_tree_lookup_by_path_node(ret, &path_node,
+ path_node_hash);
+ assert(node == NULL || node->parent == ret);
+ ret = node;
+ }
+ if (rc != 0 || path_node.type != JSON_PATH_END)
+ return NULL;
+ return ret;
+}
+
+static struct json_tree_node *
+json_tree_next_child(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ struct json_tree_node *next;
+ if (pos == NULL) {
+ next = rlist_first_entry(&parent->children,
+ struct json_tree_node, sibling);
+ } else {
+ next = rlist_next_entry(pos, sibling);
+ }
+ if (&next->sibling != &parent->children)
+ return next;
+ return NULL;
+}
+
+static struct json_tree_node *
+json_tree_leftmost(struct json_tree_node *pos)
+{
+ struct json_tree_node *last;
+ do {
+ last = pos;
+ pos = json_tree_next_child(pos, NULL);
+ } while (pos != NULL);
+ return last;
+}
+
+struct json_tree_node *
+json_tree_next_pre(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ if (pos == NULL)
+ return parent;
+ struct json_tree_node *next = json_tree_next_child(pos, NULL);
+ if (next != NULL)
+ return next;
+ while (pos != parent) {
+ next = json_tree_next_child(pos->parent, pos);
+ if (next != NULL)
+ return next;
+ pos = pos->parent;
+ }
+ return NULL;
+}
+
+struct json_tree_node *
+json_tree_next_post(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ struct json_tree_node *next;
+ if (pos == NULL)
+ return json_tree_leftmost(parent);
+ if (pos == parent)
+ return NULL;
+ next = json_tree_next_child(pos->parent, pos);
+ if (next != NULL)
+ return json_tree_leftmost(next);
+ return pos->parent;
+}
diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h
new file mode 100644
index 0000000..45bf975
--- /dev/null
+++ b/src/lib/json/tree.h
@@ -0,0 +1,260 @@
+#ifndef TARANTOOL_JSON_TREE_H_INCLUDED
+#define TARANTOOL_JSON_TREE_H_INCLUDED
+/*
+ * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdbool.h>
+#include <stdint.h>
+#include "small/rlist.h"
+#include "path.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+struct mh_json_tree_node_t;
+
+/**
+ * JSON tree is a hierarchical data structure that organize JSON
+ * nodes produced by parser.
+ * 1. Numeric records are sorted in ascending order in sibling rlist.
+ * 2. Structure key records point to source strings memory.
+ * 3. Lookup by path complexity is O(path_len):
+ * path = path_token1 + .. + path_tokenN
+ * - Complexity of hash(path_tokenI) - O(strlen(path_tokenN))
+ * - Complexity of hash lookup - O(1) + strcmp on collision
+ */
+struct json_tree_node {
+ /** Path component represented by this node. */
+ struct json_path_node key;
+ /** Hash calculated for key field. */
+ uint32_t key_hash;
+ /**
+ * Children hashtable:
+ * json_path_node -> json_tree_node.
+ */
+ struct mh_json_tree_node_t *child_by_path_node;
+ /**
+ * Link in json_tree_node::children of the parent node.
+ */
+ struct rlist sibling;
+ /**
+ * List of child nodes, linked by
+ * json_tree_node::sibling.
+ */
+ struct rlist children;
+ /** Pointer to parent json_tree_node record. */
+ struct json_tree_node *parent;
+};
+
+/**
+ * Compute the hash value of a JSON path component.
+ * @param key JSON path component to compute the hash for.
+ * @retval Hash value.
+ */
+uint32_t
+json_path_node_hash(struct json_path_node *key);
+
+/**
+ * Init a JSON tree node.
+ * @param node JSON tree node to initialize.
+ * @param path_node JSON path component the new node will
+ * represent. May be NULL, in this case
+ * @node initialized as root record.
+ * @param path_node_hash Hash of @path_node, should be calculated
+ * with json_path_node_hash.
+ */
+void
+json_tree_node_create(struct json_tree_node *node,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Destroy a JSON tree node.
+ * @param node JSON tree node to destruct.
+ */
+void
+json_tree_node_destroy(struct json_tree_node *node);
+
+/**
+ * Return count of JSON tree node direct descendant.
+ * Matches the size of the child_by_path_node hashtable.
+ * @param node JSON tree node to analyze.
+ * @retval Count of descendant.
+ */
+uint32_t
+json_tree_node_children_count(struct json_tree_node *node);
+
+/**
+ * Look up a child of a JSON tree node by a path component.
+ * @param parent JSON tree node to start lookup with.
+ * @param path_node JSON parser node with data.
+ * @param path_node_hash Hash of @path_node.
+ * @retval not NULL pointer to JSON tree node if any.
+ * @retval NULL on nothing found.
+ */
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree_node *parent,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Add a new JSON tree node at the given position in the tree.
+ * The parent node must not have a child representing the same
+ * path component.
+ * @param parent JSON tree parent node.
+ * @param node JSON tree node to append.
+ * @retval 0 On success, -1 on memory allocation error.
+ */
+int
+json_tree_add(struct json_tree_node *parent,
+ struct json_tree_node *node);
+
+/**
+ * Delete a JSON tree node at the given position in the tree.
+ * The parent node must have such child.
+ * @param parent JSON tree parent node.
+ * @param node JSON tree node to add.
+ */
+void
+json_tree_remove(struct json_tree_node *parent,
+ struct json_tree_node *node);
+
+/**
+ * Lookup a field by path in given position in the JSON tree.
+ * @param parent JSON tree parent node.
+ * @param path JSON path string.
+ * @param path_len Length of @path.
+ * @retval not NULL pointer to leaf record if any.
+ */
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree_node *parent,
+ const char *path, uint32_t path_len);
+
+/**
+ * Make pre order traversal in JSON tree.
+ * @param parent The JSON path tree to walk parent.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_next_pre(struct json_tree_node *parent,
+ struct json_tree_node *pos);
+
+/**
+ * Make post order traversal in JSON tree.
+ * @param parent The JSON path tree to walk parent.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_next_post(struct json_tree_node *parent,
+ struct json_tree_node *pos);
+
+/** Return entry by json_tree_node item. */
+#define json_tree_entry(item, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (item); \
+ (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); })
+
+/** Return entry by json_tree_node item or NULL if item is NULL.*/
+#define json_tree_entry_safe(item, type, member) ({ \
+ (item) != NULL ? json_tree_entry((item), type, member) : NULL; })
+
+/** Make lookup in tree by path and return entry. */
+#define json_tree_lookup_entry_by_path(root, path, path_len, type, member) \
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup_by_path(&(root)->member, path, path_len); \
+ __tree_node != NULL ? json_tree_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make lookup in tree by path_node and return entry. */
+#define json_tree_lookup_entry_by_path_node(root, path_node, path_node_hash, \
+ type, member) \
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup_by_path_node(&(root)->member, path_node, \
+ path_node_hash); \
+ __tree_node != NULL ? json_tree_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make pre-order traversal in JSON tree. */
+#define json_tree_foreach_pre(item, root) \
+for ((item) = json_tree_next_pre((root), NULL); (item) != NULL; \
+ (item) = json_tree_next_pre((root), (item)))
+
+/** Make post-order traversal in JSON tree. */
+#define json_tree_foreach_post(item, root) \
+for ((item) = json_tree_next_post((root), NULL); (item) != NULL; \
+ (item) = json_tree_next_post((root), (item)))
+
+/**
+ * Make safe post-order traversal in JSON tree.
+ * Safe for building destructors.
+ */
+#define json_tree_foreach_safe(item, root) \
+for (struct json_tree_node *__iter = json_tree_next_post((root), NULL); \
+ (((item) = __iter) && (__iter = json_tree_next_post((root), (item))), \
+ (item) != NULL);)
+
+/** Make post-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_pre(item, root, member) \
+for (struct json_tree_node *__iter = \
+ json_tree_next_pre(&(root)->member, NULL); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)); \
+ __iter = json_tree_next_pre(&(root)->member, __iter))
+
+/** Make pre-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_post(item, root, member) \
+for (struct json_tree_node *__iter = \
+ json_tree_next_post(&(root)->member, NULL); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)); \
+ __iter = json_tree_next_post(&(root)->member, __iter))
+
+/**
+ * Make secure post-order traversal in JSON tree and return entry.
+ */
+#define json_tree_foreach_entry_safe(item, root, member) \
+for (struct json_tree_node *__tmp_iter, *__iter = \
+ json_tree_next_post(NULL, &(root)->member); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)) && \
+ (__iter != NULL && (__tmp_iter = \
+ json_tree_next_post(&(root)->member, __iter))), \
+ (__iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member))); \
+ __iter = __tmp_iter)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* TARANTOOL_JSON_TREE_H_INCLUDED */
diff --git a/test/unit/json_path.c b/test/unit/json_path.c
index 1d7e7d3..9a1de06 100644
--- a/test/unit/json_path.c
+++ b/test/unit/json_path.c
@@ -1,7 +1,9 @@
#include "json/path.h"
+#include "json/tree.h"
#include "unit.h"
#include "trivia/util.h"
#include <string.h>
+#include <stdbool.h>
#define reset_to_new_path(value) \
path = value; \
@@ -159,14 +161,214 @@ test_errors()
footer();
}
+struct test_struct {
+ int value;
+ struct json_tree_node tree_node;
+};
+
+struct test_struct *
+test_add_path(struct test_struct *root, const char *path, uint32_t path_len,
+ struct test_struct *records_pool, int *pool_idx)
+{
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct test_struct *parent = root;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END) {
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct test_struct *new_node =
+ json_tree_lookup_entry_by_path_node(parent, &path_node,
+ path_node_hash,
+ struct test_struct,
+ tree_node);
+ if (new_node == NULL) {
+ new_node = &records_pool[*pool_idx];
+ *pool_idx = *pool_idx + 1;
+ json_tree_node_create(&new_node->tree_node, &path_node,
+ path_node_hash);
+ rc = json_tree_add(&parent->tree_node,
+ &new_node->tree_node);
+ fail_if(rc != 0);
+ }
+ parent = new_node;
+ }
+ fail_if(rc != 0 || path_node.type != JSON_PATH_END);
+ return parent;
+}
+
+void
+test_tree()
+{
+ header();
+ plan(42);
+
+ struct test_struct records[6];
+ for (int i = 0; i < 6; i++)
+ records[i].value = i;
+ json_tree_node_create(&records[0].tree_node, NULL, 0);
+ fail_if(&records[0] != json_tree_entry(&records[0].tree_node,
+ struct test_struct, tree_node));
+
+ const char *path1 = "[1][10]";
+ const char *path2 = "[1][20].file";
+ const char *path3_to_remove = "[2]";
+ const char *path_unregistered = "[1][3]";
+
+ int records_idx = 1;
+ struct test_struct *node;
+ node = test_add_path(&records[0], path1, strlen(path1), records,
+ &records_idx);
+ is(node, &records[2], "add path '%s'", path1);
+
+ node = test_add_path(&records[0], path2, strlen(path2), records,
+ &records_idx);
+ is(node, &records[4], "add path '%s'", path2);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path1, strlen(path1),
+ struct test_struct, tree_node);
+ is(node, &records[2], "lookup path '%s'", path1);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path2, strlen(path2),
+ struct test_struct, tree_node);
+ is(node, &records[4], "lookup path '%s'", path2);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path_unregistered,
+ strlen(path_unregistered),
+ struct test_struct, tree_node);
+ is(node, NULL, "lookup unregistered path '%s'", path_unregistered);
+
+ node = test_add_path(&records[0], path3_to_remove,
+ strlen(path3_to_remove), records, &records_idx);
+ is(node, &records[5], "add path to remove '%s'", path3_to_remove);
+ if (node != NULL) {
+ json_tree_remove(&records[0].tree_node, &node->tree_node);
+ json_tree_node_destroy(&node->tree_node);
+ } else {
+ isnt(node, NULL, "can't remove empty node!");
+ }
+
+ /* Test iterators. */
+ struct json_tree_node *tree_record = NULL;
+ const struct json_tree_node *tree_nodes_preorder[] =
+ {&records[0].tree_node, &records[1].tree_node,
+ &records[2].tree_node, &records[3].tree_node,
+ &records[4].tree_node};
+ int cnt = sizeof(tree_nodes_preorder)/sizeof(tree_nodes_preorder[0]);
+ int idx = 0;
+ json_tree_foreach_pre(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_preorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_preorder[idx],
+ "test foreach pre order %d: have %d expected %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+
+ const struct json_tree_node *tree_nodes_postorder[] =
+ {&records[2].tree_node, &records[4].tree_node, &records[3].tree_node,
+ &records[1].tree_node,
+ &records[0].tree_node};
+ cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
+ idx = 0;
+ json_tree_foreach_post(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_postorder[idx],
+ "test foreach post order %d: have %d expected of %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_safe(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_postorder[idx],
+ "test foreach safe order %d: have %d expected of %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_pre(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_preorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_preorder[idx],
+ "test foreach entry pre order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_post(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_postorder[idx],
+ "test foreach entry post order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_safe(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_postorder[idx],
+ "test foreach entry safe order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ json_tree_node_destroy(&node->tree_node);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ check_plan();
+ footer();
+}
+
int
main()
{
header();
- plan(2);
+ plan(3);
test_basic();
test_errors();
+ test_tree();
int rc = check_plan();
footer();
diff --git a/test/unit/json_path.result b/test/unit/json_path.result
index a2a2f82..7bc9d37 100644
--- a/test/unit/json_path.result
+++ b/test/unit/json_path.result
@@ -1,5 +1,5 @@
*** main ***
-1..2
+1..3
*** test_basic ***
1..71
ok 1 - parse <[0]>
@@ -99,4 +99,50 @@ ok 1 - subtests
ok 20 - tab inside identifier
ok 2 - subtests
*** test_errors: done ***
+ *** test_tree ***
+ 1..42
+ ok 1 - add path '[1][10]'
+ ok 2 - add path '[1][20].file'
+ ok 3 - lookup path '[1][10]'
+ ok 4 - lookup path '[1][20].file'
+ ok 5 - lookup unregistered path '[1][3]'
+ ok 6 - add path to remove '[2]'
+ ok 7 - test foreach pre order 0: have 0 expected 0
+ ok 8 - test foreach pre order 1: have 1 expected 1
+ ok 9 - test foreach pre order 2: have 2 expected 2
+ ok 10 - test foreach pre order 3: have 3 expected 3
+ ok 11 - test foreach pre order 4: have 4 expected 4
+ ok 12 - records iterated count 5 of 5
+ ok 13 - test foreach post order 0: have 2 expected of 2
+ ok 14 - test foreach post order 1: have 4 expected of 4
+ ok 15 - test foreach post order 2: have 3 expected of 3
+ ok 16 - test foreach post order 3: have 1 expected of 1
+ ok 17 - test foreach post order 4: have 0 expected of 0
+ ok 18 - records iterated count 5 of 5
+ ok 19 - test foreach safe order 0: have 2 expected of 2
+ ok 20 - test foreach safe order 1: have 4 expected of 4
+ ok 21 - test foreach safe order 2: have 3 expected of 3
+ ok 22 - test foreach safe order 3: have 1 expected of 1
+ ok 23 - test foreach safe order 4: have 0 expected of 0
+ ok 24 - records iterated count 5 of 5
+ ok 25 - test foreach entry pre order 0: have 0 expected of 0
+ ok 26 - test foreach entry pre order 1: have 1 expected of 1
+ ok 27 - test foreach entry pre order 2: have 2 expected of 2
+ ok 28 - test foreach entry pre order 3: have 3 expected of 3
+ ok 29 - test foreach entry pre order 4: have 4 expected of 4
+ ok 30 - records iterated count 5 of 5
+ ok 31 - test foreach entry post order 0: have 2 expected of 2
+ ok 32 - test foreach entry post order 1: have 4 expected of 4
+ ok 33 - test foreach entry post order 2: have 3 expected of 3
+ ok 34 - test foreach entry post order 3: have 1 expected of 1
+ ok 35 - test foreach entry post order 4: have 0 expected of 0
+ ok 36 - records iterated count 5 of 5
+ ok 37 - test foreach entry safe order 0: have 2 expected of 2
+ ok 38 - test foreach entry safe order 1: have 4 expected of 4
+ ok 39 - test foreach entry safe order 2: have 3 expected of 3
+ ok 40 - test foreach entry safe order 3: have 1 expected of 1
+ ok 41 - test foreach entry safe order 4: have 0 expected of 0
+ ok 42 - records iterated count 5 of 5
+ok 3 - subtests
+ *** test_tree: done ***
*** main: done ***
--
2.7.4
^ permalink raw reply [flat|nested] 24+ messages in thread