[PATCH v5 2/9] lib: implement JSON tree class for json library

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

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/box/lua/tuple.c         |   2 +-
 src/box/tuple_format.c      |  24 ++-
 src/lib/json/CMakeLists.txt |   3 +-
 src/lib/json/json.c         | 509 ++++++++++++++++++++++++++++++++++++++++++++
 src/lib/json/json.h         | 285 +++++++++++++++++++++++++
 src/lib/json/path.c         | 243 ---------------------
 src/lib/json/path.h         | 111 ----------
 test/unit/json_path.c       | 210 +++++++++++++++++-
 test/unit/json_path.result  |  41 +++-
 9 files changed, 1052 insertions(+), 376 deletions(-)
 create mode 100644 src/lib/json/json.c
 create mode 100644 src/lib/json/json.h
 delete mode 100644 src/lib/json/path.c
 delete mode 100644 src/lib/json/path.h

diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 65660ce..cbe71da 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -41,7 +41,7 @@
 #include "box/tuple.h"
 #include "box/tuple_convert.h"
 #include "box/errcode.h"
-#include "json/path.h"
+#include "json/json.h"
 #include "mpstream.h"
 
 /** {{{ box.tuple Lua library
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index cf05cc8..d184dba 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -28,7 +28,7 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
-#include "json/path.h"
+#include "json/json.h"
 #include "tuple_format.h"
 #include "coll_id_cache.h"
 
@@ -584,15 +584,16 @@ tuple_field_go_to_path(const char **data, const char *path, uint32_t path_len)
 	struct json_token token;
 	json_lexer_create(&lexer, path, path_len);
 	while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
-		switch (token.type) {
+		switch (token.key.type) {
 		case JSON_TOKEN_NUM:
-			rc = tuple_field_go_to_index(data, token.num);
+			rc = tuple_field_go_to_index(data, token.key.num);
 			break;
 		case JSON_TOKEN_STR:
-			rc = tuple_field_go_to_key(data, token.str, token.len);
+			rc = tuple_field_go_to_key(data, token.key.str,
+						   token.key.len);
 			break;
 		default:
-			assert(token.type == JSON_TOKEN_END);
+			assert(token.key.type == JSON_TOKEN_END);
 			return 0;
 		}
 		if (rc != 0) {
@@ -628,9 +629,9 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 	int rc = json_lexer_next_token(&lexer, &token);
 	if (rc != 0)
 		goto error;
-	switch(token.type) {
+	switch(token.key.type) {
 	case JSON_TOKEN_NUM: {
-		int index = token.num;
+		int index = token.key.num;
 		if (index == 0) {
 			*field = NULL;
 			return 0;
@@ -644,7 +645,7 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 	case JSON_TOKEN_STR: {
 		/* First part of a path is a field name. */
 		uint32_t name_hash;
-		if (path_len == (uint32_t) token.len) {
+		if (path_len == (uint32_t) token.key.len) {
 			name_hash = path_hash;
 		} else {
 			/*
@@ -653,17 +654,18 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 			 * used. A tuple dictionary hashes only
 			 * name, not path.
 			 */
-			name_hash = field_name_hash(token.str, token.len);
+			name_hash = field_name_hash(token.key.str,
+						    token.key.len);
 		}
 		*field = tuple_field_raw_by_name(format, tuple, field_map,
-						 token.str, token.len,
+						 token.key.str, token.key.len,
 						 name_hash);
 		if (*field == NULL)
 			return 0;
 		break;
 	}
 	default:
-		assert(token.type == JSON_TOKEN_END);
+		assert(token.key.type == JSON_TOKEN_END);
 		*field = NULL;
 		return 0;
 	}
diff --git a/src/lib/json/CMakeLists.txt b/src/lib/json/CMakeLists.txt
index 203fe6f..51a1f02 100644
--- a/src/lib/json/CMakeLists.txt
+++ b/src/lib/json/CMakeLists.txt
@@ -1,6 +1,7 @@
 set(lib_sources
-    path.c
+    json.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/json.c b/src/lib/json/json.c
new file mode 100644
index 0000000..9198dca
--- /dev/null
+++ b/src/lib/json/json.c
@@ -0,0 +1,509 @@
+/*
+ * 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 <ctype.h>
+#include <stdbool.h>
+#include <unicode/uchar.h>
+#include <unicode/utf8.h>
+#include "json.h"
+#include "trivia/util.h"
+#include "third_party/PMurHash.h"
+
+/**
+ * Read a single symbol from a string starting from an offset.
+ * @param lexer JSON path lexer.
+ * @param[out] UChar32 Read symbol.
+ *
+ * @retval   0 Success.
+ * @retval > 0 1-based position of a syntax error.
+ */
+static inline int
+json_read_symbol(struct json_lexer *lexer, UChar32 *out)
+{
+	if (lexer->offset == lexer->src_len) {
+		*out = U_SENTINEL;
+		return lexer->symbol_count + 1;
+	}
+	U8_NEXT(lexer->src, lexer->offset, lexer->src_len, *out);
+	if (*out == U_SENTINEL)
+		return lexer->symbol_count + 1;
+	++lexer->symbol_count;
+	return 0;
+}
+
+/**
+ * Rollback one symbol offset.
+ * @param lexer JSON path lexer.
+ * @param offset Offset to the previous symbol.
+ */
+static inline void
+json_revert_symbol(struct json_lexer *lexer, int offset)
+{
+	lexer->offset = offset;
+	--lexer->symbol_count;
+}
+
+/** Fast forward when it is known that a symbol is 1-byte char. */
+static inline void
+json_skip_char(struct json_lexer *lexer)
+{
+	++lexer->offset;
+	++lexer->symbol_count;
+}
+
+/** Get a current symbol as a 1-byte char. */
+static inline char
+json_current_char(const struct json_lexer *lexer)
+{
+	return *(lexer->src + lexer->offset);
+}
+
+/**
+ * Parse string identifier in quotes. Lexer either stops right
+ * after the closing quote, or returns an error position.
+ * @param lexer JSON path lexer.
+ * @param[out] token JSON token to store result.
+ * @param quote_type Quote by that a string must be terminated.
+ *
+ * @retval   0 Success.
+ * @retval > 0 1-based position of a syntax error.
+ */
+static inline int
+json_parse_string(struct json_lexer *lexer, struct json_token *token,
+		  UChar32 quote_type)
+{
+	assert(lexer->offset < lexer->src_len);
+	assert(quote_type == json_current_char(lexer));
+	/* The first symbol is always char  - ' or ". */
+	json_skip_char(lexer);
+	int str_offset = lexer->offset;
+	UChar32 c;
+	int rc;
+	while ((rc = json_read_symbol(lexer, &c)) == 0) {
+		if (c == quote_type) {
+			int len = lexer->offset - str_offset - 1;
+			if (len == 0)
+				return lexer->symbol_count;
+			token->key.type = JSON_TOKEN_STR;
+			token->key.str = lexer->src + str_offset;
+			token->key.len = len;
+			return 0;
+		}
+	}
+	return rc;
+}
+
+/**
+ * Parse digit sequence into integer until non-digit is met.
+ * Lexer stops right after the last digit.
+ * @param lexer JSON lexer.
+ * @param[out] token JSON token to store result.
+ *
+ * @retval   0 Success.
+ * @retval > 0 1-based position of a syntax error.
+ */
+static inline int
+json_parse_integer(struct json_lexer *lexer, struct json_token *token)
+{
+	const char *end = lexer->src + lexer->src_len;
+	const char *pos = lexer->src + lexer->offset;
+	assert(pos < end);
+	int len = 0;
+	uint64_t value = 0;
+	char c = *pos;
+	if (! isdigit(c))
+		return lexer->symbol_count + 1;
+	do {
+		value = value * 10 + c - (int)'0';
+		++len;
+	} while (++pos < end && isdigit((c = *pos)));
+	lexer->offset += len;
+	lexer->symbol_count += len;
+	token->key.type = JSON_TOKEN_NUM;
+	token->key.num = value;
+	return 0;
+}
+
+/**
+ * Check that a symbol can be part of a JSON path not inside
+ * ["..."].
+ */
+static inline bool
+json_is_valid_identifier_symbol(UChar32 c)
+{
+	return u_isUAlphabetic(c) || c == (UChar32)'_' || u_isdigit(c);
+}
+
+/**
+ * Parse identifier out of quotes. It can contain only alphas,
+ * digits and underscores. And can not contain digit at the first
+ * position. Lexer is stoped right after the last non-digit,
+ * non-alpha and non-underscore symbol.
+ * @param lexer JSON lexer.
+ * @param[out] token JSON token to store result.
+ *
+ * @retval   0 Success.
+ * @retval > 0 1-based position of a syntax error.
+ */
+static inline int
+json_parse_identifier(struct json_lexer *lexer, struct json_token *token)
+{
+	assert(lexer->offset < lexer->src_len);
+	int str_offset = lexer->offset;
+	UChar32 c;
+	int rc = json_read_symbol(lexer, &c);
+	if (rc != 0)
+		return rc;
+	/* First symbol can not be digit. */
+	if (!u_isalpha(c) && c != (UChar32)'_')
+		return lexer->symbol_count;
+	int last_offset = lexer->offset;
+	while ((rc = json_read_symbol(lexer, &c)) == 0) {
+		if (! json_is_valid_identifier_symbol(c)) {
+			json_revert_symbol(lexer, last_offset);
+			break;
+		}
+		last_offset = lexer->offset;
+	}
+	token->key.type = JSON_TOKEN_STR;
+	token->key.str = lexer->src + str_offset;
+	token->key.len = lexer->offset - str_offset;
+	return 0;
+}
+
+int
+json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
+{
+	if (lexer->offset == lexer->src_len) {
+		token->key.type = JSON_TOKEN_END;
+		return 0;
+	}
+	UChar32 c;
+	int last_offset = lexer->offset;
+	int rc = json_read_symbol(lexer, &c);
+	if (rc != 0)
+		return rc;
+	switch(c) {
+	case (UChar32)'[':
+		/* Error for '[\0'. */
+		if (lexer->offset == lexer->src_len)
+			return lexer->symbol_count;
+		c = json_current_char(lexer);
+		if (c == '"' || c == '\'')
+			rc = json_parse_string(lexer, token, c);
+		else
+			rc = json_parse_integer(lexer, token);
+		if (rc != 0)
+			return rc;
+		/*
+		 * Expression, started from [ must be finished
+		 * with ] regardless of its type.
+		 */
+		if (lexer->offset == lexer->src_len ||
+		    json_current_char(lexer) != ']')
+			return lexer->symbol_count + 1;
+		/* Skip ] - one byte char. */
+		json_skip_char(lexer);
+		return 0;
+	case (UChar32)'.':
+		if (lexer->offset == lexer->src_len)
+			return lexer->symbol_count + 1;
+		return json_parse_identifier(lexer, token);
+	default:
+		json_revert_symbol(lexer, last_offset);
+		return json_parse_identifier(lexer, token);
+	}
+}
+
+/** Compare JSON tokens keys. */
+static int
+json_token_key_cmp(const struct json_token *a, const struct json_token *b)
+{
+	if (a->key.type != b->key.type)
+		return a->key.type - b->key.type;
+	int ret = 0;
+	if (a->key.type == JSON_TOKEN_STR) {
+		if (a->key.len != b->key.len)
+			return a->key.len - b->key.len;
+		ret = memcmp(a->key.str, b->key.str, a->key.len);
+	} else if (a->key.type == JSON_TOKEN_NUM) {
+		ret = a->key.num - b->key.num;
+	} else {
+		unreachable();
+	}
+	return ret;
+}
+
+/**
+ * Compare hash records of two json tree nodes. Return 0 if equal.
+ */
+static inline int
+mh_json_cmp(const struct json_token *a, const struct json_token *b)
+{
+	if (a->parent != b->parent)
+		return a->parent - b->parent;
+	return json_token_key_cmp(a, b);
+}
+
+#define MH_SOURCE 1
+#define mh_name _json
+#define mh_key_t struct json_token **
+#define mh_node_t struct json_token *
+#define mh_arg_t void *
+#define mh_hash(a, arg) ((*a)->rolling_hash)
+#define mh_hash_key(a, arg) ((*a)->rolling_hash)
+#define mh_cmp(a, b, arg) (mh_json_cmp((*a), (*b)))
+#define mh_cmp_key(a, b, arg) mh_cmp(a, b, arg)
+#include "salad/mhash.h"
+
+static const uint32_t hash_seed = 13U;
+
+/** Compute the hash value of a JSON token. */
+static uint32_t
+json_token_hash(struct json_token *token, uint32_t seed)
+{
+	uint32_t h = seed;
+	uint32_t carry = 0;
+	const void *data;
+	uint32_t data_size;
+	if (token->key.type == JSON_TOKEN_STR) {
+		data = token->key.str;
+		data_size = token->key.len;
+	} else if (token->key.type == JSON_TOKEN_NUM) {
+		data = &token->key.num;
+		data_size = sizeof(token->key.num);
+	} else {
+		unreachable();
+	}
+	PMurHash32_Process(&h, &carry, data, data_size);
+	return PMurHash32_Result(h, carry, data_size);
+}
+
+int
+json_tree_create(struct json_tree *tree)
+{
+	memset(tree, 0, sizeof(struct json_tree));
+	tree->root.rolling_hash = hash_seed;
+	tree->root.key.type = JSON_TOKEN_END;
+	tree->hash = mh_json_new();
+	return tree->hash == NULL ? -1 : 0;
+}
+
+static void
+json_token_destroy(struct json_token *token)
+{
+	free(token->children);
+}
+
+void
+json_tree_destroy(struct json_tree *tree)
+{
+	assert(tree->hash != NULL);
+	json_token_destroy(&tree->root);
+	mh_json_delete(tree->hash);
+}
+
+struct json_token *
+json_tree_lookup(struct json_tree *tree, struct json_token *parent,
+		 struct json_token *token)
+{
+	if (parent == NULL)
+		parent = &tree->root;
+	struct json_token *ret = NULL;
+	if (token->key.type == JSON_TOKEN_STR) {
+		struct json_token key = *token;
+		key.rolling_hash = json_token_hash(token, parent->rolling_hash);
+		key.parent = parent;
+		token = &key;
+		mh_int_t id = mh_json_find(tree->hash, &token, NULL);
+		if (unlikely(id == mh_end(tree->hash)))
+			return NULL;
+		struct json_token **entry = mh_json_node(tree->hash, id);
+		assert(entry == NULL || (*entry)->parent == parent);
+		return entry != NULL ? *entry : NULL;
+	} else if (token->key.type == JSON_TOKEN_NUM) {
+		uint32_t idx =  token->key.num - 1;
+		ret = idx < parent->child_size ? parent->children[idx] : NULL;
+	} else {
+		unreachable();
+	}
+	return ret;
+}
+
+int
+json_tree_add(struct json_tree *tree, struct json_token *parent,
+	      struct json_token *token)
+{
+	if (parent == NULL)
+		parent = &tree->root;
+	uint32_t rolling_hash =
+	       json_token_hash(token, parent->rolling_hash);
+	assert(json_tree_lookup(tree, parent, token) == NULL);
+	uint32_t insert_idx = (token->key.type == JSON_TOKEN_NUM) ?
+			      (uint32_t)token->key.num - 1 :
+			      parent->child_size;
+	if (insert_idx >= parent->child_size) {
+		uint32_t new_size =
+			parent->child_size == 0 ? 1 : 2 * parent->child_size;
+		while (insert_idx >= new_size)
+			new_size *= 2;
+		struct json_token **children =
+			realloc(parent->children, new_size*sizeof(void *));
+		if (unlikely(children == NULL))
+			return -1;
+		memset(children + parent->child_size, 0,
+		       (new_size - parent->child_size)*sizeof(void *));
+		parent->children = children;
+		parent->child_size = new_size;
+	}
+	assert(parent->children[insert_idx] == NULL);
+	parent->children[insert_idx] = token;
+	parent->child_count = MAX(parent->child_count, insert_idx + 1);
+	token->sibling_idx = insert_idx;
+	token->rolling_hash = rolling_hash;
+	token->parent = parent;
+
+	const struct json_token **key =
+		(const struct json_token **)&token;
+	mh_int_t rc = mh_json_put(tree->hash, key, NULL, NULL);
+	if (unlikely(rc == mh_end(tree->hash))) {
+		parent->children[insert_idx] = NULL;
+		return -1;
+	}
+	assert(json_tree_lookup(tree, parent, token) == token);
+	return 0;
+}
+
+void
+json_tree_del(struct json_tree *tree, struct json_token *token)
+{
+	struct json_token *parent = token->parent;
+	assert(json_tree_lookup(tree, parent, token) == token);
+	struct json_token **child_slot = NULL;
+	if (token->key.type == JSON_TOKEN_NUM) {
+		child_slot = &parent->children[token->key.num - 1];
+	} else {
+		uint32_t idx = 0;
+		while (idx < parent->child_size &&
+		       parent->children[idx] != token) { idx++; }
+		if (idx < parent->child_size &&
+		       parent->children[idx] == token)
+			child_slot = &parent->children[idx];
+	}
+	assert(child_slot != NULL && *child_slot == token);
+	*child_slot = NULL;
+
+	mh_int_t id = mh_json_find(tree->hash, &token, NULL);
+	assert(id != mh_end(tree->hash));
+	mh_json_del(tree->hash, id, NULL);
+	json_token_destroy(token);
+	assert(json_tree_lookup(tree, parent, token) == NULL);
+}
+
+struct json_token *
+json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
+		      const char *path, uint32_t path_len)
+{
+	int rc;
+	struct json_lexer lexer;
+	struct json_token token;
+	struct json_token *ret = parent != NULL ? parent : &tree->root;
+	json_lexer_create(&lexer, path, path_len);
+	while ((rc = json_lexer_next_token(&lexer, &token)) == 0 &&
+	       token.key.type != JSON_TOKEN_END && ret != NULL) {
+		ret = json_tree_lookup(tree, ret, &token);
+	}
+	if (rc != 0 || token.key.type != JSON_TOKEN_END)
+		return NULL;
+	return ret;
+}
+
+static struct json_token *
+json_tree_child_next(struct json_token *parent, struct json_token *pos)
+{
+	assert(pos == NULL || pos->parent == parent);
+	struct json_token **arr = parent->children;
+	uint32_t arr_size = parent->child_size;
+	if (arr == NULL)
+		return NULL;
+	uint32_t idx = pos != NULL ? pos->sibling_idx + 1 : 0;
+	while (idx < arr_size && arr[idx] == NULL)
+		idx++;
+	if (idx >= arr_size)
+		return NULL;
+	return arr[idx];
+}
+
+static struct json_token *
+json_tree_leftmost(struct json_token *pos)
+{
+	struct json_token *last;
+	do {
+		last = pos;
+		pos = json_tree_child_next(pos, NULL);
+	} while (pos != NULL);
+	return last;
+}
+
+struct json_token *
+json_tree_preorder_next(struct json_token *root, struct json_token *pos)
+{
+	if (pos == NULL)
+		pos = root;
+	struct json_token *next = json_tree_child_next(pos, NULL);
+	if (next != NULL)
+		return next;
+	while (pos != root) {
+		next = json_tree_child_next(pos->parent, pos);
+		if (next != NULL)
+			return next;
+		pos = pos->parent;
+	}
+	return NULL;
+}
+
+struct json_token *
+json_tree_postorder_next(struct json_token *root, struct json_token *pos)
+{
+	struct json_token *next;
+	if (pos == NULL) {
+		next = json_tree_leftmost(root);
+		return next != root ? next : NULL;
+	}
+	if (pos == root)
+		return NULL;
+	next = json_tree_child_next(pos->parent, pos);
+	if (next != NULL) {
+		next = json_tree_leftmost(next);
+		return next != root ? next : NULL;
+	}
+	return pos->parent != root ? pos->parent : NULL;
+}
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
new file mode 100644
index 0000000..dd09f5a
--- /dev/null
+++ b/src/lib/json/json.h
@@ -0,0 +1,285 @@
+#ifndef TARANTOOL_JSON_JSON_H_INCLUDED
+#define TARANTOOL_JSON_JSON_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 <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Lexer for JSON paths:
+ * <field>, <.field>, <[123]>, <['field']> and their combinations.
+ */
+struct json_lexer {
+	/** Source string. */
+	const char *src;
+	/** Length of string. */
+	int src_len;
+	/** Current lexer's offset in bytes. */
+	int offset;
+	/** Current lexer's offset in symbols. */
+	int symbol_count;
+};
+
+enum json_token_type {
+	JSON_TOKEN_NUM,
+	JSON_TOKEN_STR,
+	/** Lexer reached end of path. */
+	JSON_TOKEN_END,
+};
+
+/**
+ * Element of a JSON path. It can be either string or number.
+ * String idenfiers are in ["..."] and between dots. Numbers are
+ * indexes in [...]. May be used to organize a JSON tree.
+ */
+struct json_token {
+	struct {
+		enum json_token_type type;
+		union {
+			struct {
+				/** String identifier. */
+				const char *str;
+				/** Length of @a str. */
+				int len;
+			};
+			/** Index value. */
+			uint64_t num;
+		};
+	} key;
+	/** Rolling hash for node used to lookup in json_tree. */
+	uint32_t rolling_hash;
+	/**
+	 * Array of child records. Indexes in this array
+	 * follows array indexe-1 for JSON_TOKEN_NUM token type
+	 * and are allocated sequently for JSON_TOKEN_NUM child
+	 * tokens. NULLs initializations are performed with new
+	 * entries allocation.
+	 */
+	struct json_token **children;
+	/** Allocation size of children array. */
+	uint32_t child_size;
+	/**
+	 * Count of defined children array items. Equal the
+	 * maximum index of inserted item.
+	 */
+	uint32_t child_count;
+	/** Index of node in parent children array. */
+	uint32_t sibling_idx;
+	/** Pointer to parent node. */
+	struct json_token *parent;
+};
+
+struct mh_json_t;
+
+/** JSON tree object to manage tokens relations. */
+struct json_tree {
+	/** JSON tree root node. */
+	struct json_token root;
+	/** Hashtable af all tree nodes. */
+	struct mh_json_t *hash;
+};
+
+/**
+ * Create @a lexer.
+ * @param[out] lexer Lexer to create.
+ * @param src Source string.
+ * @param src_len Length of @a src.
+ */
+static inline void
+json_lexer_create(struct json_lexer *lexer, const char *src, int src_len)
+{
+	lexer->src = src;
+	lexer->src_len = src_len;
+	lexer->offset = 0;
+	lexer->symbol_count = 0;
+}
+
+/**
+ * Get a next path token.
+ * @param lexer Lexer.
+ * @param[out] token Token to store parsed result.
+ * @retval   0 Success. For result see @a token.str, token.len,
+ *             token.num.
+ * @retval > 0 Position of a syntax error. A position is 1-based
+ *             and starts from a beginning of a source string.
+ */
+int
+json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
+
+/** Create a JSON tree object to manage data relations. */
+int
+json_tree_create(struct json_tree *tree);
+
+/**
+ * Destroy JSON tree object. This routine doesn't destroy attached
+ * subtree so it should be called at the end of manual destroy.
+ */
+void
+json_tree_destroy(struct json_tree *tree);
+
+/**
+ * Make child lookup in JSON tree by token at position specified
+ * with parent. The parent may be set NULL to use tree root
+ * record.
+ */
+struct json_token *
+json_tree_lookup(struct json_tree *tree, struct json_token *parent,
+		 struct json_token *token);
+
+/**
+ * Append token to the given parent position in a JSON tree. The
+ * parent mustn't have a child with such content. The parent may
+ * be set NULL to use tree root record.
+ */
+int
+json_tree_add(struct json_tree *tree, struct json_token *parent,
+	      struct json_token *token);
+
+/**
+ * Delete a JSON tree token at the given parent position in JSON
+ * tree. Token entry shouldn't have subtree.
+ */
+void
+json_tree_del(struct json_tree *tree, struct json_token *token);
+
+/** Make child lookup by path in JSON tree. */
+struct json_token *
+json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
+		      const char *path, uint32_t path_len);
+
+/** Make pre order traversal in JSON tree. */
+struct json_token *
+json_tree_preorder_next(struct json_token *root, struct json_token *pos);
+
+/** Make post order traversal in JSON tree. */
+struct json_token *
+json_tree_postorder_next(struct json_token *root, struct json_token *pos);
+
+/**
+ * Make safe post-order traversal in JSON tree.
+ * May be used for destructors.
+ */
+#define json_tree_foreach_safe(node, root)				     \
+for (struct json_token *__next = json_tree_postorder_next((root), NULL);     \
+     (((node) = __next) &&						     \
+     (__next = json_tree_postorder_next((root), (node))), (node) != NULL);)
+
+#ifndef typeof
+/* TODO: 'typeof' is a GNU extension */
+#define typeof __typeof__
+#endif
+
+/** Return container entry by json_tree_node node. */
+#define json_tree_entry(node, type, member) ({ 				     \
+	const typeof( ((type *)0)->member ) *__mptr = (node);		     \
+	(type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );	     \
+})
+
+/**
+ * Return container entry by json_tree_node or NULL if
+ * node is NULL.
+ */
+#define json_tree_entry_safe(node, type, member) ({			     \
+	(node) != NULL ? json_tree_entry((node), type, member) : NULL;	     \
+})
+
+/** Make entry pre order traversal in JSON tree  */
+#define json_tree_preorder_next_entry(node, root, type, member) ({	     \
+	struct json_token *__next =					     \
+		json_tree_preorder_next((root), (node));		     \
+	json_tree_entry_safe(__next, type, member);			     \
+})
+
+/** Make entry post order traversal in JSON tree  */
+#define json_tree_postorder_next_entry(node, root, type, member) ({	     \
+	struct json_token *__next =					     \
+		json_tree_postorder_next((root), (node));		     \
+	json_tree_entry_safe(__next, type, member);			     \
+})
+
+/** Make lookup in tree by path and return entry. */
+#define json_tree_lookup_path_entry(tree, parent, path, path_len, type,	     \
+				    member)				     \
+({struct json_token *__node =						     \
+	json_tree_lookup_path((tree), (parent), path, path_len);	     \
+	json_tree_entry_safe(__node, type, member); })
+
+/** Make lookup in tree by token and return entry. */
+#define json_tree_lookup_entry(tree, parent, token, type, member)	     \
+({struct json_token *__node =						     \
+	json_tree_lookup((tree), (parent), token);			     \
+	json_tree_entry_safe(__node, type, member);			     \
+})
+
+/** Make pre-order traversal in JSON tree. */
+#define json_tree_foreach_preorder(node, root)				     \
+for ((node) = json_tree_preorder_next((root), NULL); (node) != NULL;	     \
+     (node) = json_tree_preorder_next((root), (node)))
+
+/** Make post-order traversal in JSON tree. */
+#define json_tree_foreach_postorder(node, root)				     \
+for ((node) = json_tree_postorder_next((root), NULL); (node) != NULL;	     \
+     (node) = json_tree_postorder_next((root), (node)))
+
+/** Make post-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_preorder(node, root, type, member)	     \
+for ((node) = json_tree_preorder_next_entry(NULL, (root), type, member);     \
+     (node) != NULL;							     \
+     (node) = json_tree_preorder_next_entry(&(node)->member, (root), type,   \
+					    member))
+
+/** Make pre-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_postorder(node, root, type, member)	     \
+for ((node) = json_tree_postorder_next_entry(NULL, (root), type, member);    \
+     (node) != NULL;							     \
+     (node) = json_tree_postorder_next_entry(&(node)->member, (root), type,  \
+     					     member))
+
+/**
+ * Make secure post-order traversal in JSON tree and return entry.
+ */
+#define json_tree_foreach_entry_safe(node, root, type, member)		     \
+for (type *__next = json_tree_postorder_next_entry(NULL, (root), type,	     \
+						   member);		     \
+     (((node) = __next) &&						     \
+     (__next = json_tree_postorder_next_entry(&(node)->member, (root), type, \
+					      member)),			     \
+     (node) != NULL);)
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* TARANTOOL_JSON_JSON_H_INCLUDED */
diff --git a/src/lib/json/path.c b/src/lib/json/path.c
deleted file mode 100644
index dfd7d5c..0000000
--- a/src/lib/json/path.c
+++ /dev/null
@@ -1,243 +0,0 @@
-/*
- * 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 "path.h"
-#include <ctype.h>
-#include <stdbool.h>
-#include <unicode/uchar.h>
-#include <unicode/utf8.h>
-#include "trivia/util.h"
-
-/**
- * Read a single symbol from a string starting from an offset.
- * @param lexer JSON path lexer.
- * @param[out] UChar32 Read symbol.
- *
- * @retval   0 Success.
- * @retval > 0 1-based position of a syntax error.
- */
-static inline int
-json_read_symbol(struct json_lexer *lexer, UChar32 *out)
-{
-	if (lexer->offset == lexer->src_len) {
-		*out = U_SENTINEL;
-		return lexer->symbol_count + 1;
-	}
-	U8_NEXT(lexer->src, lexer->offset, lexer->src_len, *out);
-	if (*out == U_SENTINEL)
-		return lexer->symbol_count + 1;
-	++lexer->symbol_count;
-	return 0;
-}
-
-/**
- * Rollback one symbol offset.
- * @param lexer JSON path lexer.
- * @param offset Offset to the previous symbol.
- */
-static inline void
-json_revert_symbol(struct json_lexer *lexer, int offset)
-{
-	lexer->offset = offset;
-	--lexer->symbol_count;
-}
-
-/** Fast forward when it is known that a symbol is 1-byte char. */
-static inline void
-json_skip_char(struct json_lexer *lexer)
-{
-	++lexer->offset;
-	++lexer->symbol_count;
-}
-
-/** Get a current symbol as a 1-byte char. */
-static inline char
-json_current_char(const struct json_lexer *lexer)
-{
-	return *(lexer->src + lexer->offset);
-}
-
-/**
- * Parse string identifier in quotes. Lexer either stops right
- * after the closing quote, or returns an error position.
- * @param lexer JSON path lexer.
- * @param[out] token JSON token to store result.
- * @param quote_type Quote by that a string must be terminated.
- *
- * @retval   0 Success.
- * @retval > 0 1-based position of a syntax error.
- */
-static inline int
-json_parse_string(struct json_lexer *lexer, struct json_token *token,
-		  UChar32 quote_type)
-{
-	assert(lexer->offset < lexer->src_len);
-	assert(quote_type == json_current_char(lexer));
-	/* The first symbol is always char  - ' or ". */
-	json_skip_char(lexer);
-	int str_offset = lexer->offset;
-	UChar32 c;
-	int rc;
-	while ((rc = json_read_symbol(lexer, &c)) == 0) {
-		if (c == quote_type) {
-			int len = lexer->offset - str_offset - 1;
-			if (len == 0)
-				return lexer->symbol_count;
-			token->type = JSON_TOKEN_STR;
-			token->str = lexer->src + str_offset;
-			token->len = len;
-			return 0;
-		}
-	}
-	return rc;
-}
-
-/**
- * Parse digit sequence into integer until non-digit is met.
- * Lexer stops right after the last digit.
- * @param lexer JSON lexer.
- * @param[out] token JSON token to store result.
- *
- * @retval   0 Success.
- * @retval > 0 1-based position of a syntax error.
- */
-static inline int
-json_parse_integer(struct json_lexer *lexer, struct json_token *token)
-{
-	const char *end = lexer->src + lexer->src_len;
-	const char *pos = lexer->src + lexer->offset;
-	assert(pos < end);
-	int len = 0;
-	uint64_t value = 0;
-	char c = *pos;
-	if (! isdigit(c))
-		return lexer->symbol_count + 1;
-	do {
-		value = value * 10 + c - (int)'0';
-		++len;
-	} while (++pos < end && isdigit((c = *pos)));
-	lexer->offset += len;
-	lexer->symbol_count += len;
-	token->type = JSON_TOKEN_NUM;
-	token->num = value;
-	return 0;
-}
-
-/**
- * Check that a symbol can be part of a JSON path not inside
- * ["..."].
- */
-static inline bool
-json_is_valid_identifier_symbol(UChar32 c)
-{
-	return u_isUAlphabetic(c) || c == (UChar32)'_' || u_isdigit(c);
-}
-
-/**
- * Parse identifier out of quotes. It can contain only alphas,
- * digits and underscores. And can not contain digit at the first
- * position. Lexer is stoped right after the last non-digit,
- * non-alpha and non-underscore symbol.
- * @param lexer JSON lexer.
- * @param[out] token JSON token to store result.
- *
- * @retval   0 Success.
- * @retval > 0 1-based position of a syntax error.
- */
-static inline int
-json_parse_identifier(struct json_lexer *lexer, struct json_token *token)
-{
-	assert(lexer->offset < lexer->src_len);
-	int str_offset = lexer->offset;
-	UChar32 c;
-	int rc = json_read_symbol(lexer, &c);
-	if (rc != 0)
-		return rc;
-	/* First symbol can not be digit. */
-	if (!u_isalpha(c) && c != (UChar32)'_')
-		return lexer->symbol_count;
-	int last_offset = lexer->offset;
-	while ((rc = json_read_symbol(lexer, &c)) == 0) {
-		if (! json_is_valid_identifier_symbol(c)) {
-			json_revert_symbol(lexer, last_offset);
-			break;
-		}
-		last_offset = lexer->offset;
-	}
-	token->type = JSON_TOKEN_STR;
-	token->str = lexer->src + str_offset;
-	token->len = lexer->offset - str_offset;
-	return 0;
-}
-
-int
-json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
-{
-	if (lexer->offset == lexer->src_len) {
-		token->type = JSON_TOKEN_END;
-		return 0;
-	}
-	UChar32 c;
-	int last_offset = lexer->offset;
-	int rc = json_read_symbol(lexer, &c);
-	if (rc != 0)
-		return rc;
-	switch(c) {
-	case (UChar32)'[':
-		/* Error for '[\0'. */
-		if (lexer->offset == lexer->src_len)
-			return lexer->symbol_count;
-		c = json_current_char(lexer);
-		if (c == '"' || c == '\'')
-			rc = json_parse_string(lexer, token, c);
-		else
-			rc = json_parse_integer(lexer, token);
-		if (rc != 0)
-			return rc;
-		/*
-		 * Expression, started from [ must be finished
-		 * with ] regardless of its type.
-		 */
-		if (lexer->offset == lexer->src_len ||
-		    json_current_char(lexer) != ']')
-			return lexer->symbol_count + 1;
-		/* Skip ] - one byte char. */
-		json_skip_char(lexer);
-		return 0;
-	case (UChar32)'.':
-		if (lexer->offset == lexer->src_len)
-			return lexer->symbol_count + 1;
-		return json_parse_identifier(lexer, token);
-	default:
-		json_revert_symbol(lexer, last_offset);
-		return json_parse_identifier(lexer, token);
-	}
-}
diff --git a/src/lib/json/path.h b/src/lib/json/path.h
deleted file mode 100644
index 7f41fb4..0000000
--- a/src/lib/json/path.h
+++ /dev/null
@@ -1,111 +0,0 @@
-#ifndef TARANTOOL_JSON_PATH_H_INCLUDED
-#define TARANTOOL_JSON_PATH_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 <stdint.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
- * Lexer for JSON paths:
- * <field>, <.field>, <[123]>, <['field']> and their combinations.
- */
-struct json_lexer {
-	/** Source string. */
-	const char *src;
-	/** Length of string. */
-	int src_len;
-	/** Current lexer's offset in bytes. */
-	int offset;
-	/** Current lexer's offset in symbols. */
-	int symbol_count;
-};
-
-enum json_token_type {
-	JSON_TOKEN_NUM,
-	JSON_TOKEN_STR,
-	/** Lexer reached end of path. */
-	JSON_TOKEN_END,
-};
-
-/**
- * Element of a JSON path. It can be either string or number.
- * String idenfiers are in ["..."] and between dots. Numbers are
- * indexes in [...].
- */
-struct json_token {
-	enum json_token_type type;
-	union {
-		struct {
-			/** String identifier. */
-			const char *str;
-			/** Length of @a str. */
-			int len;
-		};
-		/** Index value. */
-		uint64_t num;
-	};
-};
-
-/**
- * Create @a lexer.
- * @param[out] lexer Lexer to create.
- * @param src Source string.
- * @param src_len Length of @a src.
- */
-static inline void
-json_lexer_create(struct json_lexer *lexer, const char *src, int src_len)
-{
-	lexer->src = src;
-	lexer->src_len = src_len;
-	lexer->offset = 0;
-	lexer->symbol_count = 0;
-}
-
-/**
- * Get a next path token.
- * @param lexer Lexer.
- * @param[out] token Token to store parsed result.
- * @retval   0 Success. For result see @a token.str, token.len,
- *             token.num.
- * @retval > 0 Position of a syntax error. A position is 1-based
- *             and starts from a beginning of a source string.
- */
-int
-json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* TARANTOOL_JSON_PATH_H_INCLUDED */
diff --git a/test/unit/json_path.c b/test/unit/json_path.c
index bb6e5ca..f6b0472 100644
--- a/test/unit/json_path.c
+++ b/test/unit/json_path.c
@@ -1,7 +1,8 @@
-#include "json/path.h"
+#include "json/json.h"
 #include "unit.h"
 #include "trivia/util.h"
 #include <string.h>
+#include <stdbool.h>
 
 #define reset_to_new_path(value) \
 	path = value; \
@@ -12,15 +13,15 @@
 	path = lexer.src + lexer.offset; \
 	is(json_lexer_next_token(&lexer, &token), 0, "parse <%." #value_len "s>", \
 	   path); \
-	is(token.type, JSON_TOKEN_NUM, "<%." #value_len "s> is num", path); \
-	is(token.num, value, "<%." #value_len "s> is " #value, path);
+	is(token.key.type, JSON_TOKEN_NUM, "<%." #value_len "s> is num", path); \
+	is(token.key.num, value, "<%." #value_len "s> is " #value, path);
 
 #define is_next_key(value) \
 	len = strlen(value); \
 	is(json_lexer_next_token(&lexer, &token), 0, "parse <" value ">"); \
-	is(token.type, JSON_TOKEN_STR, "<" value "> is str"); \
-	is(token.len, len, "len is %d", len); \
-	is(strncmp(token.str, value, len), 0, "str is " value);
+	is(token.key.type, JSON_TOKEN_STR, "<" value "> is str"); \
+	is(token.key.len, len, "len is %d", len); \
+	is(strncmp(token.key.str, value, len), 0, "str is " value);
 
 void
 test_basic()
@@ -62,7 +63,7 @@ test_basic()
 	/* Empty path. */
 	reset_to_new_path("");
 	is(json_lexer_next_token(&lexer, &token), 0, "parse empty path");
-	is(token.type, JSON_TOKEN_END, "is str");
+	is(token.key.type, JSON_TOKEN_END, "is str");
 
 	/* Path with no '.' at the beginning. */
 	reset_to_new_path("field1.field2");
@@ -159,14 +160,207 @@ test_errors()
 	footer();
 }
 
+struct test_struct {
+	int value;
+	struct json_token node;
+};
+
+struct test_struct *
+test_struct_alloc(struct test_struct *records_pool, int *pool_idx)
+{
+	struct test_struct *ret = &records_pool[*pool_idx];
+	*pool_idx = *pool_idx + 1;
+	memset(&ret->node, 0, sizeof(ret->node));
+	return ret;
+}
+
+struct test_struct *
+test_add_path(struct json_tree *tree, const char *path, uint32_t path_len,
+	      struct test_struct *records_pool, int *pool_idx)
+{
+	int rc;
+	struct json_lexer lexer;
+	struct json_token *parent = NULL;
+	json_lexer_create(&lexer, path, path_len);
+	struct test_struct *field = test_struct_alloc(records_pool, pool_idx);
+	while ((rc = json_lexer_next_token(&lexer, &field->node)) == 0 &&
+		field->node.key.type != JSON_TOKEN_END) {
+		struct json_token *next =
+			json_tree_lookup(tree, parent, &field->node);
+		if (next == NULL) {
+			rc = json_tree_add(tree, parent, &field->node);
+			fail_if(rc != 0);
+			next = &field->node;
+			field = test_struct_alloc(records_pool, pool_idx);
+		}
+		parent = next;
+	}
+	fail_if(rc != 0 || field->node.key.type != JSON_TOKEN_END);
+	*pool_idx = *pool_idx - 1;
+	/* release field */
+	return json_tree_entry(parent, struct test_struct, node);
+}
+
+void
+test_tree()
+{
+	header();
+	plan(35);
+
+	struct json_tree tree;
+	int rc = json_tree_create(&tree);
+	fail_if(rc != 0);
+
+	struct test_struct records[6];
+	for (int i = 0; i < 6; i++)
+		records[i].value = i;
+
+	const char *path1 = "[1][10]";
+	const char *path2 = "[1][20].file";
+	const char *path_unregistered = "[1][3]";
+
+	int records_idx = 1;
+	struct test_struct *node;
+	node = test_add_path(&tree, path1, strlen(path1), records,
+			     &records_idx);
+	is(node, &records[2], "add path '%s'", path1);
+
+	node = test_add_path(&tree, path2, strlen(path2), records,
+			     &records_idx);
+	is(node, &records[4], "add path '%s'", path2);
+
+	node = json_tree_lookup_path_entry(&tree, NULL, path1, strlen(path1),
+					   struct test_struct, node);
+	is(node, &records[2], "lookup path '%s'", path1);
+
+	node = json_tree_lookup_path_entry(&tree, NULL, path2, strlen(path2),
+					   struct test_struct, node);
+	is(node, &records[4], "lookup path '%s'", path2);
+
+	node = json_tree_lookup_path_entry(&tree, NULL, path_unregistered,
+					   strlen(path_unregistered),
+					   struct test_struct, node);
+	is(node, NULL, "lookup unregistered path '%s'", path_unregistered);
+
+	/* Test iterators. */
+	struct json_token *token = NULL;
+	const struct json_token *tokens_preorder[] =
+		{&records[1].node, &records[2].node,
+		 &records[3].node, &records[4].node};
+	int cnt = sizeof(tokens_preorder)/sizeof(tokens_preorder[0]);
+	int idx = 0;
+
+	json_tree_foreach_preorder(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tokens_preorder[idx],
+					struct test_struct, node);
+		is(token, tokens_preorder[idx],
+		   "test foreach pre order %d: have %d expected of %d",
+		   idx, t1->value, t2->value);
+		++idx;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+
+	const struct json_token *tree_nodes_postorder[] =
+		{&records[2].node, &records[4].node,
+		 &records[3].node, &records[1].node};
+	cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
+	idx = 0;
+	json_tree_foreach_postorder(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(token, tree_nodes_postorder[idx],
+		   "test foreach post order %d: have %d expected of %d",
+		   idx, t1->value, t2->value);
+		++idx;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_safe(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(token, tree_nodes_postorder[idx],
+		   "test foreach safe order %d: have %d expected of %d",
+		   idx, t1->value, t2->value);
+		++idx;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_preorder(node, &tree.root, struct test_struct,
+					 node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tokens_preorder[idx],
+					struct test_struct, node);
+		is(&node->node, tokens_preorder[idx],
+		   "test foreach entry pre order %d: have %d expected of %d",
+		   idx, node->value, t->value);
+		idx++;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_postorder(node, &tree.root, struct test_struct,
+					  node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(&node->node, tree_nodes_postorder[idx],
+		   "test foreach entry post order %d: have %d expected of %d",
+		   idx, node->value, t->value);
+		idx++;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(&node->node, tree_nodes_postorder[idx],
+		   "test foreach entry safe order %d: have %d expected of %d",
+		   idx, node->value, t->value);
+		json_tree_del(&tree, &node->node);
+		idx++;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+	json_tree_destroy(&tree);
+
+	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..df68210 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,43 @@ ok 1 - subtests
     ok 20 - tab inside identifier
 ok 2 - subtests
 	*** test_errors: done ***
+	*** test_tree ***
+    1..35
+    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 - test foreach pre order 0: have 1 expected of 1
+    ok 7 - test foreach pre order 1: have 2 expected of 2
+    ok 8 - test foreach pre order 2: have 3 expected of 3
+    ok 9 - test foreach pre order 3: have 4 expected of 4
+    ok 10 - records iterated count 4 of 4
+    ok 11 - test foreach post order 0: have 2 expected of 2
+    ok 12 - test foreach post order 1: have 4 expected of 4
+    ok 13 - test foreach post order 2: have 3 expected of 3
+    ok 14 - test foreach post order 3: have 1 expected of 1
+    ok 15 - records iterated count 4 of 4
+    ok 16 - test foreach safe order 0: have 2 expected of 2
+    ok 17 - test foreach safe order 1: have 4 expected of 4
+    ok 18 - test foreach safe order 2: have 3 expected of 3
+    ok 19 - test foreach safe order 3: have 1 expected of 1
+    ok 20 - records iterated count 4 of 4
+    ok 21 - test foreach entry pre order 0: have 1 expected of 1
+    ok 22 - test foreach entry pre order 1: have 2 expected of 2
+    ok 23 - test foreach entry pre order 2: have 3 expected of 3
+    ok 24 - test foreach entry pre order 3: have 4 expected of 4
+    ok 25 - records iterated count 4 of 4
+    ok 26 - test foreach entry post order 0: have 2 expected of 2
+    ok 27 - test foreach entry post order 1: have 4 expected of 4
+    ok 28 - test foreach entry post order 2: have 3 expected of 3
+    ok 29 - test foreach entry post order 3: have 1 expected of 1
+    ok 30 - records iterated count 4 of 4
+    ok 31 - test foreach entry safe order 0: have 2 expected of 2
+    ok 32 - test foreach entry safe order 1: have 4 expected of 4
+    ok 33 - test foreach entry safe order 2: have 3 expected of 3
+    ok 34 - test foreach entry safe order 3: have 1 expected of 1
+    ok 35 - records iterated count 4 of 4
+ok 3 - subtests
+	*** test_tree: done ***
 	*** main: done ***
-- 
2.7.4