[PATCH v1 1/1] lib: implement JSON tree class for json library

[Vladimir Davydov]

See my comments inline. The most annoying part is comments to the code.
They are either confusing or useless or both. Plus grammar mistakes,
which are driving me mad. Please apply yourself when writing comments.

On Mon, Oct 01, 2018 at 03:27:02PM +0300, Kirill Shcherbatov wrote:
> New JSON tree class would store JSON paths for tuple fields
> for registered non-plain indexes.

Bad comment. Please elaborate what a json tree is and what it can be
used for regardless of the json path index feature. Then mention why
it's needed for json indexes.

> 
> Part of #1012.

I'd rather say 'Needed for', because it's an independent class.

> ---
> Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-1012-json-tree-class
> Issue: https://github.com/tarantool/tarantool/issues/1012

Please don't prefix the branch and issue names with 'Branch:' and
'Issue:' - it's apparent what is what without it.

> 
>  src/lib/json/CMakeLists.txt |   2 +
>  src/lib/json/tree.c         | 272 ++++++++++++++++++++++++++++++++++++++++++++
>  src/lib/json/tree.h         | 207 +++++++++++++++++++++++++++++++++
>  test/unit/json_path.c       | 210 +++++++++++++++++++++++++++++++++-
>  4 files changed, 690 insertions(+), 1 deletion(-)
>  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..9702b79 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 salad small)

Do you really need all these dependencies? AFAICS you only use header
files (rlist.h and mhash.h) so no new dependencies should be introduced.

> diff --git a/src/lib/json/tree.c b/src/lib/json/tree.c
> new file mode 100644
> index 0000000..a393d5b
> --- /dev/null
> +++ b/src/lib/json/tree.c
> @@ -0,0 +1,272 @@
> +
> +/*
> + * 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 <unicode/uchar.h>
> +#include <unicode/utf8.h>

Why do you include ctype and unicode?

The following headers are missing:

stddef.h
stdint.h
small/rlist.h

(you ought to include all headers that are used in the file, even those
that are included indirectly)

> +
> +#include "tree.h"
> +#include "path.h"
> +#include "third_party/PMurHash.h"
> +
> +/** Hash record representing json_tree_node. */

A simple comment:

/**
 * Hash table: json_path_node => json_tree_node.
 */

would be much more helpful here.

> +struct mh_json_tree_node {
> +	struct json_path_node key;
> +	uint32_t key_hash;
> +	struct json_tree_node *node;
> +};
> +
> +/**
> + * Compare json_tree_node hash bindings @a and @b.
> + * @param a Hash record to compare.
> + * @param b Hash record to compare.
> + * @retval 0 On equal, not 0 otherwise.

if equal

No need to write doxygen comments for all functions. The most important
thing is a comment should be helpful and understandable. Sometimes,
annotating each argument is simply pointless and would only make the
comment look bulky, like in this case. I'd rewrite this as

/**
 * Compare hash records of two json tree nodes. Return 0 if equal.
 */

Or even delete it at all, because it's obvious that this is a comparator
function needed for the hash table defined right below.

Personally, I prefer to avoid writing doxygen comments at all and only
write them if
 - other comments in the same file are formatted as doxygen
 - the function has a lot of arguments and it makes sense annotating
   them all
 - this is a public API of a library

> + */
> +bool

static inline

> +mh_json_tree_node_cmp(const struct mh_json_tree_node *a,
> +		      const struct mh_json_tree_node *b)
> +{
> +	return (a->key.type != b->key.type) ||
> +		((a->key.type != JSON_PATH_STR ||
> +		a->key.len != b->key.len ||
> +		memcmp(a->key.str, b->key.str,
> +		       a->key.len) != 0) &&
> +		(a->key.type != JSON_PATH_NUM ||
> +		a->key_hash != b->key_hash));

This is very difficult for understanding. Please rewrite with ifs.

> +}
> +
> +/** Define tree record hashtable. */

This comment is rather useless. A comment to mh_json_tree_node would be
enough.

> +#define MH_SOURCE 1
> +#define mh_name _json_tree_node
> +#define mh_key_t struct mh_json_tree_node *

Shouldn't we use json_path_node for a key?

> +#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;
> +	uint8_t *data;

Should you define it as void *, you wouldn't need type conversions
below.

> +	uint32_t data_size;
> +	if (key->type == JSON_PATH_STR) {
> +		data = (uint8_t *)key->str;
> +		data_size = key->len;
> +	} else if (key->type == JSON_PATH_NUM) {
> +		data = (uint8_t *)&key->num;
> +		data_size = sizeof(key->num);
> +	} else {
> +		assert(0);

unreachable()

> +	}
> +	PMurHash32_Process(&h, &carry, data, data_size);
> +	return PMurHash32_Result(h, carry, data_size);
> +}
> +
> +int
> +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));
> +	node->children_ht = mh_json_tree_node_new();
> +	if (node->children_ht == NULL)
> +		return -1;
> +	if (path_node != NULL) {
> +		memcpy(&node->key, path_node, sizeof(struct json_path_node));

I'd rather you used

	node->key = *path_node;

here and everywhere else in the patch (it's easier to read the code that
way IMO).

> +		node->key_hash = path_node_hash;
> +	} else {
> +		node->key.type = JSON_PATH_END;
> +	}
> +	rlist_create(&node->siblings);
> +	rlist_create(&node->children);
> +	return 0;
> +}
> +
> +void
> +json_tree_node_destroy(struct json_tree_node *node)
> +{
> +	mh_json_tree_node_delete(node->children_ht);
> +}
> +
> +struct json_tree_node *
> +json_tree_lookup(struct json_tree_node *root, struct json_path_node *path_node,
> +		 uint32_t path_node_hash)
> +{
> +	struct mh_json_tree_node info;
> +	memcpy(&info.key, path_node, sizeof(struct json_path_node));
> +	info.key_hash = path_node_hash;
> +	mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL);
> +	if (id == mh_end(root->children_ht))
> +		return NULL;
> +	struct mh_json_tree_node *ht_node =
> +		mh_json_tree_node_node(root->children_ht, 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 == root);
> +	return ret;
> +}
> +
> +int
> +json_tree_add(struct json_tree_node *root, struct json_tree_node *node)
> +{
> +	assert(node->parent == NULL);
> +	assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL);
> +	struct mh_json_tree_node ht_node;
> +	memcpy(&ht_node.key, &node->key, sizeof(struct json_path_node));
> +	ht_node.key_hash = node->key_hash;
> +	ht_node.node = node;
> +	mh_int_t rc = mh_json_tree_node_put(root->children_ht, &ht_node, NULL,
> +					    NULL);
> +	if (rc == mh_end(node->children_ht))
> +		return -1;
> +	node->parent = root;
> +	rlist_add(&root->children, &node->siblings);
> +	return 0;
> +}
> +
> +void
> +json_tree_remove(struct json_tree_node *root, struct json_tree_node *node)
> +{
> +	assert(node->parent == root);
> +	assert(json_tree_lookup(root, &node->key, node->key_hash) == node);
> +	rlist_del_entry(node, siblings);

Please, use rlist_del() here for consistency with rlist_add() above.

> +	struct mh_json_tree_node info;
> +	memcpy(&info.key, &node->key,
> +	       sizeof(struct json_path_node));
> +	info.key_hash = node->key_hash;
> +	mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL);
> +	assert(id != mh_end(root->children_ht));
> +	mh_json_tree_node_del(root->children_ht, id, NULL);
> +	assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL);
> +}
> +
> +struct json_tree_node *
> +json_tree_lookup_path(struct json_tree_node *root, const char *path,
> +		      uint32_t path_len)
> +{
> +	int rc;
> +	struct json_path_parser parser;
> +	struct json_path_node path_node;
> +	json_path_parser_create(&parser, path, path_len);
> +	while ((rc = json_path_next(&parser, &path_node)) == 0 &&
> +	       path_node.type != JSON_PATH_END && root != NULL) {
> +		uint32_t path_node_hash = json_path_node_hash(&path_node);
> +		struct json_tree_node *node =
> +			json_tree_lookup(root, &path_node, path_node_hash);
> +		assert(node == NULL || node->parent == root);
> +		root = node;

It looks kinda weird the way you use 'root' as a loop variable.
May be, it's worth using some local variables instead.

> +	}
> +	if (rc != 0 || path_node.type != JSON_PATH_END)
> +		return NULL;
> +	return root;
> +}
> +
> +/**
> + * Get JSON tree node next child.

This is grammatically incorrect. What about

  Return the next child of a JSON tree node.

> + * @param pos JSON tree node iterator.

There's no such entity as "JSON tree node iterator" in the code so this
comment is confusing. Please fix.

> + * @param parent Parent of @pos record.
> + * @retval not NULL pointer to next item if exists.
> + */
> +static struct json_tree_node *
> +json_tree_next_child(struct json_tree_node *pos,
> +		     struct json_tree_node *parent)

I'd swap 'parent' and 'pos' here, because

  json_tree_next_child(NULL, node)

looks unnatural to me.

> +{
> +	struct json_tree_node *next;
> +	if (pos == NULL) {
> +		next = rlist_first_entry(&parent->children,
> +					 struct json_tree_node, siblings);
> +	} else {
> +		next = rlist_next_entry(pos, siblings);

I wouldn't use _entry variants here, because 'next' may be not a list
entry, but a list head, which you check below.

> +	}
> +	if (&next->siblings != &parent->children)
> +		return next;
> +	return NULL;
> +}
> +
> +/**
> + * Find leftmost child rellative for iterator @pos.

rellative => relative, please enable spell checking in your editor.

Also, "relative for" is a solecism, should be "relative to".
Please always make sure that the preposition matches the verb.

Also, this function finds not a child, but a descendant so I'd rewrite
the comment as "Find the leftmost descendant of a JSON tree node".

> + * @param pos JSON tree node iterator.

Again, there's no such thing as iterator. What this function does is
find the leftmost descendant of a tree node. Please rewrite the comment
accordingly.

> + * @retval not NULL pointer to next item if exists.
> + */
> +static struct json_tree_node *
> +json_tree_leftmost_descendant(struct json_tree_node *pos)

I don't like that you use 'descendant' in some function names, but not
in others, e.g. json_tree_preorder_next. Please be consistent. I'd drop
'descendant' from all function names so that this function would turn
into json_tree_leftmost.

> +{
> +	struct json_tree_node *last;
> +	do {
> +		last = pos;
> +		pos = json_tree_next_child(NULL, pos);
> +	} while (pos);

This is against our coding style, should be (pos != NULL).

> +	return last;
> +}
> +
> +struct json_tree_node *
> +json_tree_preorder_next(struct json_tree_node *pos, struct json_tree_node *root)
> +{
> +	if (pos == NULL)
> +		return root;
> +	struct json_tree_node *next = json_tree_next_child(NULL, pos);
> +	if (next != NULL)
> +		return next;
> +	while (pos != root) {
> +		next = json_tree_next_child(pos, pos->parent);
> +		if (next != NULL)
> +			return next;
> +		pos = pos->parent;
> +	}
> +	return NULL;
> +}
> +
> +struct json_tree_node *
> +json_tree_postorder_next(struct json_tree_node *pos,
> +			 struct json_tree_node *root)

Again, I'd swap 'root' and 'pos' for these two functions.

Also, I don't quite like the names. What about json_tree_next_pre and
json_tree_next_post?

> +{
> +	struct json_tree_node *next;
> +	if (pos == NULL)
> +		return json_tree_leftmost_descendant(root);
> +	if (pos == root)
> +		return NULL;
> +	next = json_tree_next_child(pos, pos->parent);
> +	if (next != NULL)
> +		return json_tree_leftmost_descendant(next);
> +	return pos->parent;
> +}
> diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h
> new file mode 100644
> index 0000000..aa77b51
> --- /dev/null
> +++ b/src/lib/json/tree.h
> @@ -0,0 +1,207 @@
> +#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 <stdint.h>
> +#include "small/rlist.h"
> +#include "path.h"
> +
> +#ifdef __cplusplus
> +extern "C"
> +{

extern "C" {

> +#endif
> +
> +/** JSON path tree hash structure. */

We usually don't add comments to type declarations. This one is useless
anyway, so please remove.

> +struct mh_json_tree_node_t;
> +
> +/** JSON path tree record structure. */

This comment is useless, because it simply repeats the structure name.
Please try to elaborate what a json tree is and what it can be used for.

> +struct json_tree_node {
> +	/** JSON parser node path. */

Again, repeating function/type names in comments looks bad. At least,
you could say that this is a path component represented by this node.

> +	struct json_path_node key;
> +	/** Hash calculated for key field. */
> +	uint32_t key_hash;
> +	/** Childs hashtable: json_path_node -> json_tree_node. */

There's no word 'childs', should be 'children'.

> +	struct mh_json_tree_node_t *children_ht;

'ht' is confusing, better call it child_by_path, child_by_path_node, or
child_by_name IMO.

> +	/** Siblings nodes list. */
> +	struct rlist siblings;

IMO, better call it 'sibling' (singular) to emphasize that it's a link
in a list, not a list head.

> +	/** Child nodes list. */
> +	struct rlist children;

It'd be helpful to mention how the list is linked, e.g.

/** 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. */

/** Pointer to the parent node. */

> +	struct json_tree_node *parent;
> +};
> +
> +/**
> + * Calculate json_path_node hash.

I don't like when type names are referred in comments like this.
What about "Compute the hash value of a JSON path component"?

> + * @param key JSON parser node to calculate hash.

It's not a parser node. It's a path component. Also, the preposition is
missing, should be

  JSON path component to compute the hash for.

> + * @retval Hash value.
> + */
> +uint32_t
> +json_path_node_hash(struct json_path_node *key);

May be, this function should be defined in json/path.h?

> +
> +/**
> + * Init JSON tree node.

Init *a* JSON tree node.

> + * @param node JSON tree node to initialize.
> + * @param path_node Source JSON parser node to use on initialize.

What is "Source JSON parser"? Unclear. May be, simply rewrite it as

  JSON path component the new node will represent

Also, you should mention what happens if it's NULL.

> + * @param path_node_hash Hash of @path_node.

You should mention that the hash must be computed with
json_path_node_hash.

> + * @retval 0 On success, -1 otherwise.

What does 'otherwise' mean here? An error? What kind of error?
Memory allocation error I assume. Should be mentioned in the comment.

> + */
> +int
> +json_tree_node_create(struct json_tree_node *node,
> +		      struct json_path_node *path_node,
> +		      uint32_t path_node_hash);
> +
> +/**
> + * Destroy JSON tree node.

Destroy *a* JSON tree node.

> + * @param node JSON tree node to destruct.
> + * @retval 0 On success, -1 on error.

What retval? It returns void.

> + */
> +void
> +json_tree_node_destroy(struct json_tree_node *node);
> +
> +/**
> + * Lookup record with data @path_node having hash @path_node_hash
> + * in JSON tree @node childs.

This is barely understandable...

Why not simply write something like this:

  Look up a child of a JSON tree node by a path component.

> + * @param node JSON tree root node.

The variable is called 'root' while the comment is for 'node'. Anyway,
it's not necessarily a root node, it may be any node.

> + * @param path_node JSON parser node with data.
> + * @param path_node_hash Hash of @path_node.

Should be mentioned that the hash must be computed with
json_path_node_hash.

> + * @retval not NULL pointer to JSON tree node if any.

Can it return NULL? I suppose it can. Hence it should be in the comment.

> + */
> +struct json_tree_node *
> +json_tree_lookup(struct json_tree_node *root,
> +		 struct json_path_node *path_node,
> +		 uint32_t path_node_hash);
> +
> +/**
> + * Append JSON tree node @node to @root. Root JSON tree node @root
> + * shouldn't have childs with same content.

Please try not to use @ in the summary, especially when it's not
necessary:

  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 root JSON tree root node.

Not necessarily a root. Should be called 'parent', I guess.

I stop reviewing comments at this point, but you should now feel how
ugly they look to me. Please self-review them and make them look good.
Sorry for being so meticulous.

> + * @param node JSON tree node to append.
> + * @retval 0 On success, -1 on memory allocation error.
> + */
> +int
> +json_tree_add(struct json_tree_node *root,
> +	      struct json_tree_node *node);
> +
> +/**
> + * Detach JSON tree node @node by @root. Root JSON tree node @root
> + * should have such child.
> + * @param root JSON tree root node.
> + * @param node JSON tree node to add.
> + */
> +void
> +json_tree_remove(struct json_tree_node *root,
> +		 struct json_tree_node *node);
> +
> +/**
> + * Lookup JSON path @path having length @path_len in JSON
> + * tree @root.
> + * @param root JSON tree root 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_path(struct json_tree_node *root,
> +		      const char *path, uint32_t path_len);

This function doesn't look up a path, it looks up a JSON tree node *by*
path. May be, call it json_tree_lookup_by_path then? Not sure. Don't
really like how the lookup function names play along.

  json_tree_lookup - by path component
  json_tree_lookup_by_path - by full path

  json_tree_lookup_child
  json_tree_lookup

  json_tree_lookup_by_path_node
  json_tree_lookup_by_path

Which one is better? Don't know...

> +
> +/**
> + * Make pre order traversal iterator @pos step.
> + * @param pos Iterator pointer, NULL for initialization.
> + * @param root The JSON path tree to walk root.
> + * @retval not NULL pointer to next node. NULL if nothing found.
> + */
> +struct json_tree_node *
> +json_tree_preorder_next(struct json_tree_node *pos,
> +			struct json_tree_node *root);
> +
> +/**
> + * Make post order traversal iterator @pos step.
> + * @param pos Iterator pointer, NULL for initialization.
> + * @param root The JSON path tree to walk root.
> + * @retval not NULL pointer to next node. NULL if nothing found.
> + */
> +struct json_tree_node *
> +json_tree_postorder_next(struct json_tree_node *pos,
> +			 struct json_tree_node *root);
> +
> +
> +/**
> + * Define macros to operate with containers.
> + */

Useless comment.

> +
> +/** Return entry by json_tree_node item. */
> +#define json_tree_node_entry(item, type, member) ({			     \

json_tree_entry?

> +	const typeof( ((type *)0)->member ) *__mptr = (item);		     \
> +	(type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); })
> +
> +/** Make lookup in tree by path and return entry on found. */
> +#define json_tree_lookup_path_entry(root, path, path_len, type, member)      \

json_tree_lookup_entry_by_path?

> +({struct json_tree_node *__tree_node =					     \
> +	json_tree_lookup_path(&(root)->member, path, path_len);		     \
> + __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) :     \
> +		       NULL; })
> +
> +/** Make lookup in tree by path_node and return entry on found. */
> +#define json_tree_lookup_entry(root, path_node, path_node_hash, type, member)\
> +({struct json_tree_node *__tree_node =					     \
> +	json_tree_lookup(&(root)->member, path_node, path_node_hash);	     \
> + __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) :     \
> +		       NULL; })
> +
> +/** Make traversal in JSON tree. */
> +#define json_tree_foreach_entry(order, item, root, member)		     \

Apart from _entry variants, there should be json_tree_foreach_pre,
json_tree_foreach_post, and json_tree_foreach_safe. The latter must use
post-order traversal, because pre-order traversal is unsafe against node
removal.

IMO _entry variants should be called

  json_tree_foreach_entry_pre
  json_tree_foreach_entry_post
  json_tree_foreach_entry_safe

> +for (struct json_tree_node *__iter =					     \
> +     json_tree_##order##_next(NULL, &(root)->member);			     \
> +     __iter != NULL && (item = json_tree_node_entry(__iter, typeof(*root),   \
> +						    member));		     \
> +     __iter = json_tree_##order##_next(__iter, &(root)->member))
> +
> +/**
> + * Make secure traversal in JSON tree that works even on
> + * destruction under iterator.
> + */
> +#define json_tree_foreach_entry_safe(order, item, root, member)		     \
> +for (struct json_tree_node *__tmp_iter, *__iter =			     \
> +     json_tree_##order##_next(NULL, &(root)->member);			     \
> +     __iter != NULL && ((item) = json_tree_node_entry(__iter, typeof(*root), \
> +						      member)) &&	     \
> +     (__iter != NULL && (__tmp_iter =					     \
> +			 json_tree_##order##_next(__iter,		     \
> +						  &(root)->member))),	     \
> +     (__iter != NULL && ((item) = json_tree_node_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..fb16162 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,220 @@ test_errors()
>  	footer();
>  }
>  
> +enum tuple_field_type {
> +	TUPLE_FIELD_TYPE_ANY,
> +	TUPLE_FIELD_TYPE_MAP,
> +	TUPLE_FIELD_TYPE_ARRAY,
> +	TUPLE_FIELD_TYPE_OTHER,
> +};

Please rewrite the test without any reference to tuple fields.
All you need is check all functions so I expect the test to be
simple and clear.