[PATCH v1 0/4] box: JSON preparatory patchset

[PATCH v1 0/4] box: JSON preparatory patchset

[Kirill Shcherbatov]

Preparatory patch set for JSON indexes:
- Implemented a new json_token_path_snprint routine able to print
  JSON path to field by field specified working like cannonical
    snprintf routine
- New json_token_is_leaf helper to test node is JSON tree leaf
- Implemented a new bitmap_majority_test routine to check if the
  passed bitmap a "majorates" bitmap b (test that a contains at
  least all b bits).
- Reworked tuple_init_field_map with required fields bitmap -
  a scallable approach able to work with JSON multilevel fields
  tree.

http://github.com/tarantool/tarantool/tree/kshch/gh-3908-fix-ast-alter-memleak
https://github.com/tarantool/tarantool/issues/3908

Kirill Shcherbatov (4):
  lib: introduce json_tree_snprint_path
  lib: introduce json_token_is_leaf helper
  box: introduce bitmap_majority_test routine
  box: refactor tuple_init_field_map to use bitmap

 src/box/errcode.h                 |   2 +-
 src/box/tuple_format.c            | 103 ++++++++++++++++++++++++++--
 src/box/tuple_format.h            |  18 +++++
 src/lib/bit/bit.h                 |  45 ++++++++++++
 src/lib/json/json.c               |  68 ++++++++++++++++++
 src/lib/json/json.h               |  21 ++++++
 test/box/alter_limits.result      |   6 +-
 test/box/ddl.result               |  18 ++---
 test/box/misc.result              |   2 +-
 test/box/sql.result               |   9 +--
 test/box/tree_pk_multipart.result |   6 +-
 test/engine/ddl.result            |  21 ++----
 test/engine/null.result           |  39 ++++-------
 test/unit/bit.c                   |  52 ++++++++++++++
 test/unit/bit.result              |   2 +
 test/unit/json.c                  | 110 +++++++++++++++++++++++++++++-
 test/unit/json.result             |  32 ++++++++-
 test/vinyl/constraint.result      |   9 +--
 test/vinyl/errinj.result          |   9 +--
 test/vinyl/savepoint.result       |   6 +-
 20 files changed, 485 insertions(+), 93 deletions(-)

-- 
2.19.2

[PATCH v1 1/4] lib: introduce json_tree_snprint_path

[Kirill Shcherbatov]

Implemented a helper function for getting a path to a json_token
in a json_tree. When routine is called with size=0, return value
(as always) as the number of characters that would have been
written in case the output string has been large enough.
We will use this function for reporting tuple format violations
in further patches.

Needed for #1012
---
 src/lib/json/json.c   | 68 ++++++++++++++++++++++++++++++++++++++++
 src/lib/json/json.h   | 10 ++++++
 test/unit/json.c      | 73 ++++++++++++++++++++++++++++++++++++++++++-
 test/unit/json.result | 24 +++++++++++++-
 4 files changed, 173 insertions(+), 2 deletions(-)

diff --git a/src/lib/json/json.c b/src/lib/json/json.c
index c7909fde2..6bee024a9 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -317,6 +317,74 @@ json_path_validate(const char *path, int path_len, int index_base)
 	return rc;
 }
 
+/**
+ * An snprint-style helper to print an individual token key.
+ */
+static int
+json_token_snprint(char *buf, int size, const struct json_token *token,
+		   int index_base)
+{
+	enum json_token_type type = token->type;
+	assert(type == JSON_TOKEN_NUM || type == JSON_TOKEN_STR);
+	int len = 0;
+	if (type == JSON_TOKEN_NUM)
+		len = snprintf(buf, size, "[%d]", token->num + index_base);
+	else if (type == JSON_TOKEN_STR)
+		len = snprintf(buf, size, "[\"%.*s\"]", token->len, token->str);
+	return len;
+}
+
+int
+json_tree_snprint_path(char *buf, int size, const struct json_token *root,
+		       const struct json_token *token, int index_base)
+{
+	/*
+	 * Calculate JSON path string length passing 0-buffer in
+	 * json_token_snprint routine.
+	 */
+	int len = 0;
+	const struct json_token *ptr = token;
+	while (ptr != root && ptr->type != JSON_TOKEN_END) {
+		len += json_token_snprint(NULL, 0, ptr, index_base);
+		ptr = ptr->parent;
+	}
+	if (size == 0)
+		return len;
+
+	/*
+	 * Write to the memory buffer buf as many tokens,
+	 * starting with the root, as it can fit. If the fragment
+	 * of the token does not fit into the buffer, it would be
+	 * truncated.
+	 */
+	int pos = len;
+	char last = '\0';
+	ptr = token;
+	while (ptr != root && ptr->type != JSON_TOKEN_END) {
+		pos -= json_token_snprint(NULL, 0, ptr, index_base);
+		assert(pos >= 0);
+		if (pos < size) {
+			int rc = json_token_snprint(buf + pos, size - pos, ptr,
+						    index_base);
+			rc = MIN(rc, size - pos);
+			/*
+			 * The json_token_snprint writes a
+			 * '\0'-terminated string in memory
+			 * buffer. The first character in
+			 * token string representation would be
+			 * overwritten on next cycle iteration.
+			 * Let's keep it in 'last' variable to
+			 * restore next time.
+			 */
+			buf[pos + rc] = last;
+			last = buf[pos];
+		}
+		ptr = ptr->parent;
+	}
+	assert(buf[MIN(len, size - 1)] == '\0');
+	return len;
+}
+
 #define MH_SOURCE 1
 #define mh_name _json
 #define mh_key_t struct json_token *
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index 7ce10ce2c..c0adca450 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -253,6 +253,16 @@ json_path_cmp(const char *a, int a_len, const char *b, int b_len,
 int
 json_path_validate(const char *path, int path_len, int index_base);
 
+/**
+ * An snprint-style function to print path to a token in a JSON
+ * tree. The root node doesn't necessarily have to be the tree
+ * root - it may be any ascendant of the given token, in which
+ * case a path from the given ascendant to the token will be
+ * printed.
+ */
+int
+json_tree_snprint_path(char *buf, int size, const struct json_token *root,
+		       const struct json_token *token, int index_base);
 /**
  * Initialize a new empty JSON tree.
  *
diff --git a/test/unit/json.c b/test/unit/json.c
index e553ff23c..26cc5088b 100644
--- a/test/unit/json.c
+++ b/test/unit/json.c
@@ -438,16 +438,87 @@ test_path_cmp()
 	footer();
 }
 
+
+struct snprintf_test_case {
+	struct json_token *root;
+	struct json_token *token;
+	int buf_size;
+	int retval;
+	const char *str;
+	int str_len;
+	const char *descr;
+};
+
+void
+test_path_snprintf()
+{
+	struct json_tree tree;
+	int rc = json_tree_create(&tree);
+	fail_if(rc != 0);
+	struct test_struct records[5];
+	const char *path = "[1][20][\"file\"][8]";
+	int path_len = strlen(path); // 18
+
+	int records_idx = 0;
+	struct test_struct *node, *node_tmp;
+	node = test_add_path(&tree, path, path_len, records, &records_idx);
+	fail_if(&node->node != &records[3].node);
+
+	/* Test size estimation. */
+	char buff[64];
+	const struct snprintf_test_case tests[] = {
+		{&tree.root, &node->node, path_len + 1, path_len, path,
+		 path_len, "Full path"},
+		{&records[0].node, &node->node, path_len + 1, path_len - 3,
+		 path + 3, path_len - 3, "Non-tree-root root token"},
+		{&tree.root, &node->node, path_len - 5, path_len, path,
+		 path_len - 6, "Not enough space in buffer, all tokens fit in"},
+		{&tree.root, &node->node, path_len - 5, path_len, path,
+		 path_len - 6,
+		 "Not enough space in buffer, part of token doesn't fit in"},
+		{&tree.root, &node->node, 2, path_len, path, 1,
+		 "2-byte size buffer"},
+		{&tree.root, &node->node, 1, path_len, path, 0,
+		 "1-byte size buffer"},
+	};
+	header();
+	plan(3 * lengthof(tests));
+
+	for (size_t i = 0; i < lengthof(tests); ++i) {
+		rc = json_tree_snprint_path(buff, tests[i].buf_size,
+					    tests[i].root, tests[i].token,
+					    INDEX_BASE);
+		is(memcmp(buff, tests[i].str, tests[i].str_len), 0,
+		   "\"%s\" - correct partial JSON path: have \"%.*s\" expected \"%.*s\"",
+		   tests[i].descr, tests[i].buf_size, buff, tests[i].str_len,
+		   tests[i].str);
+		is(buff[tests[i].str_len], '\0',
+		   "\"%s\" - terminating '\\0' at appropriate place",
+		   tests[i].descr);
+		is(rc, tests[i].retval, "\"%s\" - correct rc: have %d expected %d",
+		   tests[i].descr, rc, tests[i].retval);
+	}
+
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node, node_tmp)
+		json_tree_del(&tree, &node->node);
+	json_tree_destroy(&tree);
+
+	check_plan();
+	footer();
+}
+
 int
 main()
 {
 	header();
-	plan(4);
+	plan(5);
 
 	test_basic();
 	test_errors();
 	test_tree();
 	test_path_cmp();
+	test_path_snprintf();
 
 	int rc = check_plan();
 	footer();
diff --git a/test/unit/json.result b/test/unit/json.result
index a17451099..a73203154 100644
--- a/test/unit/json.result
+++ b/test/unit/json.result
@@ -1,5 +1,5 @@
 	*** main ***
-1..4
+1..5
 	*** test_basic ***
     1..71
     ok 1 - parse <[1]>
@@ -169,4 +169,26 @@ ok 3 - subtests
     ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6
 ok 4 - subtests
 	*** test_path_cmp: done ***
+	*** test_path_snprintf ***
+    1..18
+    ok 1 - "Full path" - correct partial JSON path: have "[1][20]["file"][8]" expected "[1][20]["file"][8]"
+    ok 2 - "Full path" - terminating '\0' at appropriate place
+    ok 3 - "Full path" - correct rc: have 18 expected 18
+    ok 4 - "Non-tree-root root token" - correct partial JSON path: have "[20]["file"][8]" expected "[20]["file"][8]"
+    ok 5 - "Non-tree-root root token" - terminating '\0' at appropriate place
+    ok 6 - "Non-tree-root root token" - correct rc: have 15 expected 15
+    ok 7 - "Not enough space in buffer, all tokens fit in" - correct partial JSON path: have "[1][20]["fil" expected "[1][20]["fil"
+    ok 8 - "Not enough space in buffer, all tokens fit in" - terminating '\0' at appropriate place
+    ok 9 - "Not enough space in buffer, all tokens fit in" - correct rc: have 18 expected 18
+    ok 10 - "Not enough space in buffer, part of token doesn't fit in" - correct partial JSON path: have "[1][20]["fil" expected "[1][20]["fil"
+    ok 11 - "Not enough space in buffer, part of token doesn't fit in" - terminating '\0' at appropriate place
+    ok 12 - "Not enough space in buffer, part of token doesn't fit in" - correct rc: have 18 expected 18
+    ok 13 - "2-byte size buffer" - correct partial JSON path: have "[" expected "["
+    ok 14 - "2-byte size buffer" - terminating '\0' at appropriate place
+    ok 15 - "2-byte size buffer" - correct rc: have 18 expected 18
+    ok 16 - "1-byte size buffer" - correct partial JSON path: have "" expected ""
+    ok 17 - "1-byte size buffer" - terminating '\0' at appropriate place
+    ok 18 - "1-byte size buffer" - correct rc: have 18 expected 18
+ok 5 - subtests
+	*** test_path_snprintf: done ***
 	*** main: done ***
-- 
2.19.2

[PATCH v1 2/4] lib: introduce json_token_is_leaf helper

[Kirill Shcherbatov]

A new json_token_is_leaf routine tests if the passed JSON token
is a JSON tree leaf(has no child record).

Needed for #1012
---
 src/lib/json/json.h   | 11 +++++++++++
 test/unit/json.c      | 39 ++++++++++++++++++++++++++++++++++++++-
 test/unit/json.result | 10 +++++++++-
 3 files changed, 58 insertions(+), 2 deletions(-)

diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index c0adca450..0bc99474b 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -30,6 +30,7 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
+#include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
 #include "trivia/util.h"
@@ -253,6 +254,16 @@ json_path_cmp(const char *a, int a_len, const char *b, int b_len,
 int
 json_path_validate(const char *path, int path_len, int index_base);
 
+/**
+ * Test if the passed JSON token is a JSON tree leaf
+ * (has no child records).
+ */
+static inline bool
+json_token_is_leaf(struct json_token *token)
+{
+	return token->max_child_idx == -1;
+}
+
 /**
  * An snprint-style function to print path to a token in a JSON
  * tree. The root node doesn't necessarily have to be the tree
diff --git a/test/unit/json.c b/test/unit/json.c
index 26cc5088b..6dac688d1 100644
--- a/test/unit/json.c
+++ b/test/unit/json.c
@@ -508,17 +508,54 @@ test_path_snprintf()
 	footer();
 }
 
+void
+test_json_helpers()
+{
+	struct json_tree tree;
+	int rc = json_tree_create(&tree);
+	fail_if(rc != 0);
+	struct test_struct records[5];
+	const char *path0 = "[1][20][\"file\"]";
+	int path0_len = strlen(path0);
+	const char *path = "[1][20][\"file\"][8]";
+	int path_len = strlen(path);
+
+	header();
+	plan(4);
+
+	int records_idx = 0;
+	struct test_struct *node, *node_tmp;
+	node = test_add_path(&tree, path0, path0_len, records, &records_idx);
+	fail_if(&node->node != &records[2].node);
+	is(json_token_is_leaf(&records[1].node), false, "interm node is not leaf");
+	is(json_token_is_leaf(&records[2].node), true, "last node is leaf");
+
+	node = test_add_path(&tree, path, path_len, records, &records_idx);
+	fail_if(&node->node != &records[3].node);
+	is(json_token_is_leaf(&records[2].node), false,
+	   "last node became interm - it can't be leaf anymore");
+	is(json_token_is_leaf(&records[3].node), true, "last node is leaf");
+
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     node, node_tmp)
+		json_tree_del(&tree, &node->node);
+	json_tree_destroy(&tree);
+	check_plan();
+	footer();
+}
+
 int
 main()
 {
 	header();
-	plan(5);
+	plan(6);
 
 	test_basic();
 	test_errors();
 	test_tree();
 	test_path_cmp();
 	test_path_snprintf();
+	test_json_helpers();
 
 	int rc = check_plan();
 	footer();
diff --git a/test/unit/json.result b/test/unit/json.result
index a73203154..ea2d1af8e 100644
--- a/test/unit/json.result
+++ b/test/unit/json.result
@@ -1,5 +1,5 @@
 	*** main ***
-1..5
+1..6
 	*** test_basic ***
     1..71
     ok 1 - parse <[1]>
@@ -191,4 +191,12 @@ ok 4 - subtests
     ok 18 - "1-byte size buffer" - correct rc: have 18 expected 18
 ok 5 - subtests
 	*** test_path_snprintf: done ***
+	*** test_json_helpers ***
+    1..4
+    ok 1 - interm node is not leaf
+    ok 2 - last node is leaf
+    ok 3 - last node became interm - it can't be leaf anymore
+    ok 4 - last node is leaf
+ok 6 - subtests
+	*** test_json_helpers: done ***
 	*** main: done ***
-- 
2.19.2

[PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Kirill Shcherbatov]

A new routine bitmap_majority_test allows to test that bitmap
a "majorates" bitmap b, i.e. test that a have at least all b bits.
We need it to test compatibility of required fields bitmap with
another one that is built for tuple on tuple_init_field_map.

Needed for #1012
---
 src/lib/bit/bit.h    | 45 ++++++++++++++++++++++++++++++++++++++
 test/unit/bit.c      | 52 ++++++++++++++++++++++++++++++++++++++++++++
 test/unit/bit.result |  2 ++
 3 files changed, 99 insertions(+)

diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
index 370a0cc5d..2146a0452 100644
--- a/src/lib/bit/bit.h
+++ b/src/lib/bit/bit.h
@@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it)
 	return it->word_base + bit;
 }
 
+/**
+ * Check if the passed bitmap a "majorates" bitmap b (test that
+ * a contains at least all b bits). Compare first len memory
+ * blocks of sizeof(uint32_t).
+ * Return 0 when a majorates b. Otherwise -1 is returned and
+ * diff_bit_id is set - the index of first bit that present in
+ * bitmap b, but doesn't present in bitmap a.
+ */
+static inline int
+bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id)
+{
+	int match_cnt = 0;
+	uint32_t *a_ptr = a, *b_ptr = b;
+	uint32_t neg_impl;
+	/*
+	 * "Inverted material implication" ~(~x | y) = x & ~y test
+	 * is used to find the first bit that differ
+	 *
+	 * Example:
+	 * step 0 -- skip compatible bytes
+	 * x:      0b01111101
+	 * y:      0b00111101
+	 * x & ~y: 0b00000000 == 0 -- next, goto step 0
+	 *
+	 * step 1 -- the first byte that differ:
+	 * x:      0b01011001
+	 * y:      0b00111101
+	 * x & ~y: 0b00100100
+	 *
+	 * step 2 -- calculate relative bit index with ctz:
+	 * bit_ctz_u32(0b00100100) = 2 -- return diff_bit_id
+	 */
+	while (bit_likely((neg_impl = *b_ptr & ~*a_ptr) == 0)) {
+		if (bit_unlikely(++match_cnt >= len)) {
+			return 0;
+		}
+		a_ptr++;
+		b_ptr++;
+	}
+	assert(neg_impl != 0);
+	uint32_t trailing_zeros = bit_ctz_u32(neg_impl);
+	*diff_bit_id = match_cnt * sizeof(uint32_t) * CHAR_BIT + trailing_zeros;
+	return -1;
+}
+
 #undef ITER_CTZ
 #undef ITER_UINT
 
diff --git a/test/unit/bit.c b/test/unit/bit.c
index beb89a7e4..10074c412 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -206,6 +206,57 @@ test_bit_iter_empty(void)
 	footer();
 }
 
+static void
+test_bitmap_majority(void)
+{
+	header();
+
+	uint32_t id;
+	uint32_t req_bitmap[5];
+	memset(req_bitmap, 0, sizeof(req_bitmap));
+	bit_set(req_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(req_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(req_bitmap, 8);
+	fail_if(bitmap_majority_test(req_bitmap, req_bitmap, 5, &id) != 0);
+
+	/*
+	 * Verify that bitmap_majority_test returns difference
+	 * bits ids in incremental order ignoring test extra bits.
+	 */
+	uint32_t test_bitmap[5];
+	memset(test_bitmap, 0, sizeof(test_bitmap));
+	bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 8);
+	bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 8);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 8);
+	bit_set(&test_bitmap, 8);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+	bit_set(&test_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+	fail_unless(id == 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(&test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+	/* All different bits have been fixed. */
+	fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 4, &id) != 0);
+
+	footer();
+}
+
 int
 main(void)
 {
@@ -216,4 +267,5 @@ main(void)
 	test_index();
 	test_bit_iter();
 	test_bit_iter_empty();
+	test_bitmap_majority();
 }
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..6123bc58a 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3
 	*** test_bit_iter: done ***
 	*** test_bit_iter_empty ***
 	*** test_bit_iter_empty: done ***
+	*** test_bitmap_majority ***
+	*** test_bitmap_majority: done ***
-- 
2.19.2

[PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Kirill Shcherbatov]

Refactored tuple_init_field_map to fill a local bitmap and
compare it with template required_fields bitmap containing
information about required fields. Each field is mapped to
bitmap with field:id - unique field identifier.
This approach to check the required fields will work even after
the introduction of JSON paths, when the field tree becomes
multilevel.

Needed for #1012
---
 src/box/errcode.h                 |   2 +-
 src/box/tuple_format.c            | 103 ++++++++++++++++++++++++++++--
 src/box/tuple_format.h            |  18 ++++++
 test/box/alter_limits.result      |   6 +-
 test/box/ddl.result               |  18 ++----
 test/box/misc.result              |   2 +-
 test/box/sql.result               |   9 +--
 test/box/tree_pk_multipart.result |   6 +-
 test/engine/ddl.result            |  21 ++----
 test/engine/null.result           |  39 ++++-------
 test/vinyl/constraint.result      |   9 +--
 test/vinyl/errinj.result          |   9 +--
 test/vinyl/savepoint.result       |   6 +-
 13 files changed, 157 insertions(+), 91 deletions(-)

diff --git a/src/box/errcode.h b/src/box/errcode.h
index 94381f9f7..f7dbb948e 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -91,7 +91,7 @@ struct errcode_record {
 	/* 36 */_(ER_NO_SUCH_SPACE,		"Space '%s' does not exist") \
 	/* 37 */_(ER_NO_SUCH_FIELD,		"Field %d was not found in the tuple") \
 	/* 38 */_(ER_EXACT_FIELD_COUNT,		"Tuple field count %u does not match space field count %u") \
-	/* 39 */_(ER_MIN_FIELD_COUNT,		"Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \
+	/* 39 */_(ER_FIELD_MISSING,		"Tuple field %s required by space format is missing") \
 	/* 40 */_(ER_WAL_IO,			"Failed to write to disk") \
 	/* 41 */_(ER_MORE_THAN_ONE_TUPLE,	"Get() doesn't support partial keys and non-unique indexes") \
 	/* 42 */_(ER_ACCESS_DENIED,		"%s access to %s '%s' is denied for user '%s'") \
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index d7489dcd0..a2b7fc7e6 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -28,6 +28,8 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
+#include "bit/bit.h"
+#include "fiber.h"
 #include "json/json.h"
 #include "tuple_format.h"
 #include "coll_id_cache.h"
@@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 		return -1;
 	}
 	format->field_map_size = field_map_size;
+
+	/* Allocate required fields bitmap. */
+	uint32_t required_fields_sz =
+		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) *
+		sizeof(uint32_t);
+	format->required_fields = calloc(1, required_fields_sz);
+	if (format->required_fields == NULL) {
+		diag_set(OutOfMemory, required_fields_sz, "calloc",
+			 "format->required_fields");
+		return -1;
+	}
+	struct tuple_field *field;
+	struct json_token *root = (struct json_token *)&format->fields.root;
+	json_tree_foreach_entry_preorder(field, root, struct tuple_field,
+					 token) {
+		/*
+		 * Mark all leaf non-nullable fields as required
+		 * setting corresponding bit 1 in format
+		 * required_fields.
+		 */
+		if (json_token_is_leaf(&field->token) &&
+		    !tuple_field_is_nullable(field))
+			bit_set(format->required_fields, field->id);
+	}
 	return 0;
 }
 
@@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 		struct tuple_field *field = tuple_field_new();
 		if (field == NULL)
 			goto error;
+		field->id = fieldno;
 		field->token.num = fieldno;
 		field->token.type = JSON_TOKEN_NUM;
 		if (json_tree_add(&format->fields, &format->fields.root,
@@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 		format->dict = dict;
 		tuple_dictionary_ref(dict);
 	}
+	format->total_field_count = field_count;
+	format->required_fields = NULL;
 	format->refs = 0;
 	format->id = FORMAT_ID_NIL;
 	format->index_field_count = index_field_count;
@@ -340,6 +369,7 @@ error:
 static inline void
 tuple_format_destroy(struct tuple_format *format)
 {
+	free(format->required_fields);
 	tuple_format_destroy_fields(format);
 	tuple_dictionary_unref(format->dict);
 }
@@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
 	return true;
 }
 
+/**
+ * Return meta information of a tuple field given a format
+ * and a unique field identifier.
+ * Typically used on error handling so it is not
+ * performance-critical and may use full-tree-traverse on lookup.
+ */
+static struct tuple_field *
+tuple_format_field_by_id(struct tuple_format *format, uint32_t id)
+{
+	struct tuple_field *field;
+	json_tree_foreach_entry_preorder(field, &format->fields.root,
+					 struct tuple_field, token) {
+		if (field->id == id)
+			return field;
+	}
+	return NULL;
+}
+
+/**
+ * Analyze required_fields to ensure that all required fields
+ * present in tuple. Routine relies on required_fields is
+ * initialized on tuple_format_create and all required field's
+ * bits ids are set 1.
+ */
+static int
+tuple_format_required_fields_test(struct tuple_format *format,
+				  uint32_t *required_fields)
+{
+	uint32_t bitmap_len =
+		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t));
+	uint32_t missed_field_id;
+	if (likely(bitmap_majority_test(required_fields, format->required_fields,
+					bitmap_len, &missed_field_id) == 0))
+		return 0;
+	assert(missed_field_id < format->total_field_count);
+	struct tuple_field *missed_field =
+		tuple_format_field_by_id(format, missed_field_id);
+	assert(missed_field != NULL);
+	diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field));
+	return -1;
+}
+
 /** @sa declaration for details. */
 int
 tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
@@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
 			 (unsigned) format->exact_field_count);
 		return -1;
 	}
-	if (validate && field_count < format->min_field_count) {
-		diag_set(ClientError, ER_MIN_FIELD_COUNT,
-			 (unsigned) field_count,
-			 (unsigned) format->min_field_count);
-		return -1;
-	}
 
 	/* first field is simply accessible, so we do not store offset to it */
 	struct tuple_field *field = tuple_format_field(format, 0);
+	/*
+	 * Allocate fields_bitmap - a bitmap of fields that are
+	 * present in tuple.
+	 */
+	struct region *region = &fiber()->gc;
+	uint32_t *fields_bitmap = NULL;
+	if (validate) {
+		uint32_t fields_bitmap_sz =
+			DIV_ROUND_UP(format->total_field_count,
+				     sizeof(uint32_t)) * sizeof(uint32_t);
+		fields_bitmap = region_alloc(region, fields_bitmap_sz);
+		if (fields_bitmap == NULL) {
+			diag_set(OutOfMemory, fields_bitmap_sz, "calloc",
+				"required_fields");
+			return -1;
+		}
+		memset(fields_bitmap, 0, fields_bitmap_sz);
+		if (field_count > 0)
+			bit_set(fields_bitmap, field->id);
+	}
 	if (validate &&
 	    !field_mp_type_is_compatible(field->type, mp_typeof(*pos),
 					 tuple_field_is_nullable(field))) {
@@ -484,9 +570,12 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
 			field_map[field->offset_slot] =
 				(uint32_t) (pos - tuple);
 		}
+		if (validate)
+			bit_set(fields_bitmap, field->id);
 		mp_next(&pos);
 	}
-	return 0;
+	return validate ?
+	       tuple_format_required_fields_test(format, fields_bitmap) : 0;
 }
 
 uint32_t
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index 21f314126..48201c085 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -114,6 +114,8 @@ struct tuple_field {
 	struct coll *coll;
 	/** Collation identifier. */
 	uint32_t coll_id;
+	/** Field unique identifier in tuple_format. */
+	uint32_t id;
 	/** Link in tuple_format::fields. */
 	struct json_token token;
 };
@@ -173,6 +175,22 @@ struct tuple_format {
 	 * Shared names storage used by all formats of a space.
 	 */
 	struct tuple_dictionary *dict;
+	/**
+	 * This bitmap of "required fields" contains information
+	 * about fields that must present in tuple to be inserted.
+	 * Fields are mapped in bitmap with unique identifier
+	 * field::id used as bit index to set.
+	 * Look for tuple_format_required_fields_test comment for
+	 * more details.
+	 */
+	uint32_t *required_fields;
+	/**
+	 * Total count of format fields in fields subtree.
+	 * Used to allocate temporary bitmap of intialized fields
+	 * during tuple_init_field_map call to verify that all
+	 * required_fields are initialized.
+	 */
+	uint32_t total_field_count;
 	/**
 	 * Fields comprising the format, organized in a tree.
 	 * First level nodes correspond to tuple fields.
diff --git a/test/box/alter_limits.result b/test/box/alter_limits.result
index 4fd80a374..4fb33dd67 100644
--- a/test/box/alter_limits.result
+++ b/test/box/alter_limits.result
@@ -842,8 +842,7 @@ index = s:create_index('string', { type = 'tree', unique =  false, parts = { 2,
 -- create index on a non-existing field
 index = s:create_index('nosuchfield', { type = 'tree', unique = true, parts = { 3, 'string'}})
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 s.index.year:drop()
 ---
@@ -864,8 +863,7 @@ s:replace{'Der Baader Meinhof Komplex'}
 ...
 index = s:create_index('year', { type = 'tree', unique = false, parts = { 2, 'unsigned'}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:drop()
 ---
diff --git a/test/box/ddl.result b/test/box/ddl.result
index d3b0d1e0e..3d6d07f43 100644
--- a/test/box/ddl.result
+++ b/test/box/ddl.result
@@ -326,33 +326,27 @@ box.internal.collation.drop('test')
 ...
 box.space._collation:auto_increment{'test'}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 3 required by space format is missing
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU'}
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 5 required by space format is missing
 ...
 box.space._collation:auto_increment{'test', 'ADMIN', 'ICU', 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 3 type does not match one required by operation: expected unsigned'
 ...
 box.space._collation:auto_increment{42, 0, 'ICU', 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 2 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 42, 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 4 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU', 42}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 5 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU', 'ru_RU', setmap{}} --ok
 ---
diff --git a/test/box/misc.result b/test/box/misc.result
index 9fecbce76..c3cabcc8a 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -369,7 +369,7 @@ t;
   36: box.error.NO_SUCH_SPACE
   37: box.error.NO_SUCH_FIELD
   38: box.error.EXACT_FIELD_COUNT
-  39: box.error.MIN_FIELD_COUNT
+  39: box.error.FIELD_MISSING
   40: box.error.WAL_IO
   41: box.error.MORE_THAN_ONE_TUPLE
   42: box.error.ACCESS_DENIED
diff --git a/test/box/sql.result b/test/box/sql.result
index 1818b294d..78dc47167 100644
--- a/test/box/sql.result
+++ b/test/box/sql.result
@@ -299,8 +299,7 @@ s:truncate()
 -- get away with it.
 space:insert{'Britney'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 sorted(space.index.secondary:select('Anything'))
 ---
@@ -308,8 +307,7 @@ sorted(space.index.secondary:select('Anything'))
 ...
 space:insert{'Stephanie'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 sorted(space.index.secondary:select('Anything'))
 ---
@@ -638,8 +636,7 @@ sorted(space.index.secondary:select('Britney'))
 -- try to insert the incoplete tuple
 space:replace{'Spears'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 -- check that nothing has been updated
 space:select{'Spears'}
diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result
index 28cab3f94..93219f666 100644
--- a/test/box/tree_pk_multipart.result
+++ b/test/box/tree_pk_multipart.result
@@ -490,13 +490,11 @@ i1 = space:create_index('primary', { type = 'tree', parts = {1, 'unsigned', 3, '
 ...
 space:insert{1, 1}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 space:replace{1, 1}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 space:drop()
 ---
diff --git a/test/engine/ddl.result b/test/engine/ddl.result
index 272ff7618..8d34d5ef4 100644
--- a/test/engine/ddl.result
+++ b/test/engine/ddl.result
@@ -77,8 +77,7 @@ index = space:create_index('primary', {type = 'tree', parts = {1, 'unsigned', 2,
 ...
 space:insert({13})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:drop()
 ---
@@ -844,13 +843,11 @@ s:replace{1, '2', {3, 3}, 4.4, -5, true, {7}, 8, 9}
 ...
 s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}}
 ---
-- error: Tuple field count 7 is less than required by space format or defined indexes
-    (expected at least 9)
+- error: Tuple field 8 required by space format is missing
 ...
 s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}, 8}
 ---
-- error: Tuple field count 8 is less than required by space format or defined indexes
-    (expected at least 9)
+- error: Tuple field 9 required by space format is missing
 ...
 s:truncate()
 ---
@@ -1334,8 +1331,7 @@ s:format(format)
 -- Fail, not enough fields.
 s:replace{2, 2, 2, 2, 2}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 6 required by space format is missing
 ...
 s:replace{2, 2, 2, 2, 2, 2, 2}
 ---
@@ -1347,8 +1343,7 @@ format[7] = {name = 'field7', type = 'unsigned'}
 -- Fail, the tuple {1, ... 1} is invalid for a new format.
 s:format(format)
 ---
-- error: Tuple field count 6 is less than required by space format or defined indexes
-    (expected at least 7)
+- error: Tuple field 7 required by space format is missing
 ...
 s:drop()
 ---
@@ -2012,8 +2007,7 @@ s:create_index('sk', {parts = {4, 'unsigned'}}) -- error: field type
 ...
 s:create_index('sk', {parts = {4, 'integer', 5, 'string'}}) -- error: field missing
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 i1 = s:create_index('i1', {parts = {2, 'string'}, unique = false})
 ---
@@ -2065,8 +2059,7 @@ i3:alter{parts = {4, 'unsigned'}} -- error: field type
 ...
 i3:alter{parts = {4, 'integer', 5, 'string'}} -- error: field missing
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 i3:alter{parts = {2, 'string', 4, 'integer'}} -- ok
 ---
diff --git a/test/engine/null.result b/test/engine/null.result
index 757e63185..d55bc05bd 100644
--- a/test/engine/null.result
+++ b/test/engine/null.result
@@ -458,8 +458,7 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}})
 ...
 s:replace{1, 2} -- error
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 t1 = s:replace{2, 3, 4}
 ---
@@ -530,18 +529,15 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}})
 ...
 s:replace{1, 2} -- error
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 3 required by space format is missing
 ...
 s:replace{2, 3, 4} -- error
 ---
-- error: Tuple field count 3 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 s:replace{3, 4, 5, 6} -- error
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 t1 = s:replace{4, 5, 6, 7, 8}
 ---
@@ -1069,8 +1065,7 @@ sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}})
 -- Test tuple_compare_slowpath, tuple_compare_with_key_slowpath.
 s:replace{} -- Fail
 ---
-- error: Tuple field count 0 is less than required by space format or defined indexes
-    (expected at least 1)
+- error: Tuple field 1 required by space format is missing
 ...
 -- Compare full vs not full.
 s:replace{2}
@@ -1769,8 +1764,7 @@ s:format(format)
 -- Field 2 is not nullable.
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:insert{5, box.NULL}
 ---
@@ -1786,8 +1780,7 @@ s:insert{5, box.NULL}
 ...
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}}
 ---
@@ -1805,8 +1798,7 @@ s:insert{5, box.NULL}
 ...
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=true}}}
 ---
@@ -1849,13 +1841,11 @@ _ = s:delete{5}
 ...
 s:format(format) -- Still fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} -- Still fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 -- Now check we can set nullability to false step by step.
 _ = s:delete{6}
@@ -1873,8 +1863,7 @@ s:insert{5, box.NULL} -- Fail.
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 format[2].is_nullable = true
 ---
@@ -1891,8 +1880,7 @@ s:insert{5, box.NULL} -- Fail.
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 format[2].is_nullable = false
 ---
@@ -1906,8 +1894,7 @@ s:select{}
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:insert{9, 10} -- Success.
 ---
diff --git a/test/vinyl/constraint.result b/test/vinyl/constraint.result
index 46ed1c9eb..520a0f8aa 100644
--- a/test/vinyl/constraint.result
+++ b/test/vinyl/constraint.result
@@ -83,13 +83,11 @@ index = space:create_index('primary', { type = 'tree', parts = {1,'unsigned',2,'
 ...
 space:insert{1}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:replace{1}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:delete{1}
 ---
@@ -101,8 +99,7 @@ space:update(1, {{'=', 1, 101}})
 ...
 space:upsert({1}, {{'+', 1, 10}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:get{1}
 ---
diff --git a/test/vinyl/errinj.result b/test/vinyl/errinj.result
index a081575be..23ab845b3 100644
--- a/test/vinyl/errinj.result
+++ b/test/vinyl/errinj.result
@@ -1634,8 +1634,7 @@ errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0.001)
 ...
 s:create_index('sk', {parts = {2, 'unsigned'}}) -- must fail
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0)
 ---
@@ -2087,8 +2086,7 @@ fiber.sleep(0)
 ...
 s:format{{'key', 'unsigned'}, {'value', 'unsigned'}} -- must fail
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:select()
 ---
@@ -2112,8 +2110,7 @@ fiber.sleep(0)
 ...
 s:create_index('sk', {parts = {2, 'unsigned'}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:select()
 ---
diff --git a/test/vinyl/savepoint.result b/test/vinyl/savepoint.result
index d7b57a775..a62f2ea80 100644
--- a/test/vinyl/savepoint.result
+++ b/test/vinyl/savepoint.result
@@ -124,8 +124,7 @@ index2 = space:create_index('secondary', { parts = {2, 'int', 3, 'str'} })
 ...
 space:insert({1})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 2 required by space format is missing
 ...
 space:insert({1, 1, 'a'})
 ---
@@ -623,8 +622,7 @@ space:insert({4, 2, 'b'})
 ...
 space:upsert({2}, {{'=', 4, 1000}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 2 required by space format is missing
 ...
 index3:delete({3, 'a'})
 ---
-- 
2.19.2

Re: [tarantool-patches] [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Konstantin Osipov]

* Kirill Shcherbatov <kshcherbatov@tarantool.org> [18/12/27 14:19]:
> Refactored tuple_init_field_map to fill a local bitmap and
> compare it with template required_fields bitmap containing
> information about required fields. Each field is mapped to
> bitmap with field:id - unique field identifier.
> This approach to check the required fields will work even after
> the introduction of JSON paths, when the field tree becomes
> multilevel.
> 
> Needed for #1012
> ---
>  src/box/errcode.h                 |   2 +-
>  src/box/tuple_format.c            | 103 ++++++++++++++++++++++++++++--
>  src/box/tuple_format.h            |  18 ++++++
>  test/box/alter_limits.result      |   6 +-
>  test/box/ddl.result               |  18 ++----
>  test/box/misc.result              |   2 +-
>  test/box/sql.result               |   9 +--
>  test/box/tree_pk_multipart.result |   6 +-
>  test/engine/ddl.result            |  21 ++----
>  test/engine/null.result           |  39 ++++-------
>  test/vinyl/constraint.result      |   9 +--
>  test/vinyl/errinj.result          |   9 +--
>  test/vinyl/savepoint.result       |   6 +-
>  13 files changed, 157 insertions(+), 91 deletions(-)
> 
> diff --git a/src/box/errcode.h b/src/box/errcode.h
> index 94381f9f7..f7dbb948e 100644
> --- a/src/box/errcode.h
> +++ b/src/box/errcode.h
> @@ -91,7 +91,7 @@ struct errcode_record {
>  	/* 36 */_(ER_NO_SUCH_SPACE,		"Space '%s' does not exist") \
>  	/* 37 */_(ER_NO_SUCH_FIELD,		"Field %d was not found in the tuple") \
>  	/* 38 */_(ER_EXACT_FIELD_COUNT,		"Tuple field count %u does not match space field count %u") \
> -	/* 39 */_(ER_MIN_FIELD_COUNT,		"Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \
> +	/* 39 */_(ER_FIELD_MISSING,		"Tuple field %s required by space format is missing") \
>  	/* 40 */_(ER_WAL_IO,			"Failed to write to disk") \
>  	/* 41 */_(ER_MORE_THAN_ONE_TUPLE,	"Get() doesn't support partial keys and non-unique indexes") \
>  	/* 42 */_(ER_ACCESS_DENIED,		"%s access to %s '%s' is denied for user '%s'") \
> diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
> index d7489dcd0..a2b7fc7e6 100644
> --- a/src/box/tuple_format.c
> +++ b/src/box/tuple_format.c
> @@ -28,6 +28,8 @@
>   * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
>   * SUCH DAMAGE.
>   */
> +#include "bit/bit.h"
> +#include "fiber.h"
>  #include "json/json.h"
>  #include "tuple_format.h"
>  #include "coll_id_cache.h"
> @@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
>  		return -1;
>  	}
>  	format->field_map_size = field_map_size;
> +
> +	/* Allocate required fields bitmap. */
> +	uint32_t required_fields_sz =
> +		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) *
> +		sizeof(uint32_t);
> +	format->required_fields = calloc(1, required_fields_sz);
> +	if (format->required_fields == NULL) {
> +		diag_set(OutOfMemory, required_fields_sz, "calloc",
> +			 "format->required_fields");
> +		return -1;
> +	}
> +	struct tuple_field *field;
> +	struct json_token *root = (struct json_token *)&format->fields.root;
> +	json_tree_foreach_entry_preorder(field, root, struct tuple_field,
> +					 token) {
> +		/*
> +		 * Mark all leaf non-nullable fields as required
> +		 * setting corresponding bit 1 in format
> +		 * required_fields.
> +		 */
> +		if (json_token_is_leaf(&field->token) &&
> +		    !tuple_field_is_nullable(field))
> +			bit_set(format->required_fields, field->id);
> +	}
>  	return 0;
>  }
>  
> @@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
>  		struct tuple_field *field = tuple_field_new();
>  		if (field == NULL)
>  			goto error;
> +		field->id = fieldno;
>  		field->token.num = fieldno;
>  		field->token.type = JSON_TOKEN_NUM;
>  		if (json_tree_add(&format->fields, &format->fields.root,
> @@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
>  		format->dict = dict;
>  		tuple_dictionary_ref(dict);
>  	}
> +	format->total_field_count = field_count;
> +	format->required_fields = NULL;
>  	format->refs = 0;
>  	format->id = FORMAT_ID_NIL;
>  	format->index_field_count = index_field_count;
> @@ -340,6 +369,7 @@ error:
>  static inline void
>  tuple_format_destroy(struct tuple_format *format)
>  {
> +	free(format->required_fields);
>  	tuple_format_destroy_fields(format);
>  	tuple_dictionary_unref(format->dict);
>  }
> @@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
>  	return true;
>  }
>  
> +/**
> + * Return meta information of a tuple field given a format
> + * and a unique field identifier.
> + * Typically used on error handling so it is not
> + * performance-critical and may use full-tree-traverse on lookup.
> + */
> +static struct tuple_field *
> +tuple_format_field_by_id(struct tuple_format *format, uint32_t id)
> +{
> +	struct tuple_field *field;
> +	json_tree_foreach_entry_preorder(field, &format->fields.root,
> +					 struct tuple_field, token) {
> +		if (field->id == id)
> +			return field;
> +	}
> +	return NULL;
> +}
> +
> +/**
> + * Analyze required_fields to ensure that all required fields
> + * present in tuple. Routine relies on required_fields is
> + * initialized on tuple_format_create and all required field's
> + * bits ids are set 1.
> + */
> +static int
> +tuple_format_required_fields_test(struct tuple_format *format,
> +				  uint32_t *required_fields)
> +{
> +	uint32_t bitmap_len =
> +		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t));
> +	uint32_t missed_field_id;
> +	if (likely(bitmap_majority_test(required_fields, format->required_fields,
> +					bitmap_len, &missed_field_id) == 0))
> +		return 0;
> +	assert(missed_field_id < format->total_field_count);
> +	struct tuple_field *missed_field =
> +		tuple_format_field_by_id(format, missed_field_id);
> +	assert(missed_field != NULL);
> +	diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field));
> +	return -1;
> +}
> +
>  /** @sa declaration for details. */
>  int
>  tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
> @@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
>  			 (unsigned) format->exact_field_count);
>  		return -1;
>  	}
> -	if (validate && field_count < format->min_field_count) {
> -		diag_set(ClientError, ER_MIN_FIELD_COUNT,
> -			 (unsigned) field_count,
> -			 (unsigned) format->min_field_count);
> -		return -1;
> -	}
>  
>  	/* first field is simply accessible, so we do not store offset to it */
>  	struct tuple_field *field = tuple_format_field(format, 0);
> +	/*
> +	 * Allocate fields_bitmap - a bitmap of fields that are

Please rename fields_bitmap to field_bitmap. When a noun is used
as an adjective, it is used in singular form.


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [PATCH v1 1/4] lib: introduce json_tree_snprint_path

[Vladimir Davydov]

On Thu, Dec 27, 2018 at 02:15:52PM +0300, Kirill Shcherbatov wrote:
> +int
> +json_tree_snprint_path(char *buf, int size, const struct json_token *root,
> +		       const struct json_token *token, int index_base)

I guess you were right and I was wrong after all - if we require to pass
the root to this routine, we'll have to pass tuple_format to
tuple_field_path(), which will look rather awkward. I removed the root
argument altogether and pushed the patch to 2.1.

Re: [PATCH v1 2/4] lib: introduce json_token_is_leaf helper

[Vladimir Davydov]

On Thu, Dec 27, 2018 at 02:15:53PM +0300, Kirill Shcherbatov wrote:
>  int
>  main()
>  {
>  	header();
> -	plan(5);
> +	plan(6);
>  
>  	test_basic();
>  	test_errors();
>  	test_tree();
>  	test_path_cmp();
>  	test_path_snprintf();
> +	test_json_helpers();

This should be a part of test_tree(). I moved the tests there and pushed
the patch to 2.1.

Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Vladimir Davydov]

On Thu, Dec 27, 2018 at 02:15:54PM +0300, Kirill Shcherbatov wrote:
> A new routine bitmap_majority_test allows to test that bitmap
> a "majorates" bitmap b, i.e. test that a have at least all b bits.
> We need it to test compatibility of required fields bitmap with
> another one that is built for tuple on tuple_init_field_map.
> 
> Needed for #1012
> ---
>  src/lib/bit/bit.h    | 45 ++++++++++++++++++++++++++++++++++++++
>  test/unit/bit.c      | 52 ++++++++++++++++++++++++++++++++++++++++++++
>  test/unit/bit.result |  2 ++
>  3 files changed, 99 insertions(+)
> 
> diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
> index 370a0cc5d..2146a0452 100644
> --- a/src/lib/bit/bit.h
> +++ b/src/lib/bit/bit.h
> @@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it)
>  	return it->word_base + bit;
>  }
>  
> +/**
> + * Check if the passed bitmap a "majorates" bitmap b (test that
> + * a contains at least all b bits). Compare first len memory
> + * blocks of sizeof(uint32_t).
> + * Return 0 when a majorates b. Otherwise -1 is returned and
> + * diff_bit_id is set - the index of first bit that present in
> + * bitmap b, but doesn't present in bitmap a.
> + */
> +static inline int
> +bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id)

This function looks artificial to me, especially the fact that in case
of error it returns the first different bit in diff_bit_id (why only the
first one?).

Why do you need it, anyway? All you need to do in the next patch is:
 1. Allocate required_fields bitmap on region.
 2. Initialize it with tuple_format->required_fields.
 3. Clear bits in it as you find that corresponding tuple fields are
    present.
 4. Finally, check that the bitmap is empty. If it is not report an
    error for the first set bit.

To achieve that, you need a much simpler primitive, bit_find(), which
would find the first set bit in a bitmap. This primitive could be reused
in future, in contrast to this new function.

I just looked at bit.c and I see that it already has a bit iterator.
May be, we can simply use it for finding the first bit? It looks pretty
efficient to me.

Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Vladimir Davydov]

On Thu, Dec 27, 2018 at 02:15:55PM +0300, Kirill Shcherbatov wrote:
> Refactored tuple_init_field_map to fill a local bitmap and
> compare it with template required_fields bitmap containing
> information about required fields. Each field is mapped to
> bitmap with field:id - unique field identifier.
> This approach to check the required fields will work even after
> the introduction of JSON paths, when the field tree becomes
> multilevel.
> 
> Needed for #1012
> ---
>  src/box/errcode.h                 |   2 +-
>  src/box/tuple_format.c            | 103 ++++++++++++++++++++++++++++--
>  src/box/tuple_format.h            |  18 ++++++
>  test/box/alter_limits.result      |   6 +-
>  test/box/ddl.result               |  18 ++----
>  test/box/misc.result              |   2 +-
>  test/box/sql.result               |   9 +--
>  test/box/tree_pk_multipart.result |   6 +-
>  test/engine/ddl.result            |  21 ++----
>  test/engine/null.result           |  39 ++++-------
>  test/vinyl/constraint.result      |   9 +--
>  test/vinyl/errinj.result          |   9 +--
>  test/vinyl/savepoint.result       |   6 +-
>  13 files changed, 157 insertions(+), 91 deletions(-)
> 
> diff --git a/src/box/errcode.h b/src/box/errcode.h
> index 94381f9f7..f7dbb948e 100644
> --- a/src/box/errcode.h
> +++ b/src/box/errcode.h
> @@ -91,7 +91,7 @@ struct errcode_record {
>  	/* 36 */_(ER_NO_SUCH_SPACE,		"Space '%s' does not exist") \
>  	/* 37 */_(ER_NO_SUCH_FIELD,		"Field %d was not found in the tuple") \
>  	/* 38 */_(ER_EXACT_FIELD_COUNT,		"Tuple field count %u does not match space field count %u") \
> -	/* 39 */_(ER_MIN_FIELD_COUNT,		"Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \
> +	/* 39 */_(ER_FIELD_MISSING,		"Tuple field %s required by space format is missing") \
>  	/* 40 */_(ER_WAL_IO,			"Failed to write to disk") \
>  	/* 41 */_(ER_MORE_THAN_ONE_TUPLE,	"Get() doesn't support partial keys and non-unique indexes") \
>  	/* 42 */_(ER_ACCESS_DENIED,		"%s access to %s '%s' is denied for user '%s'") \
> diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
> index d7489dcd0..a2b7fc7e6 100644
> --- a/src/box/tuple_format.c
> +++ b/src/box/tuple_format.c
> @@ -28,6 +28,8 @@
>   * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
>   * SUCH DAMAGE.
>   */
> +#include "bit/bit.h"
> +#include "fiber.h"
>  #include "json/json.h"
>  #include "tuple_format.h"
>  #include "coll_id_cache.h"
> @@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
>  		return -1;
>  	}
>  	format->field_map_size = field_map_size;
> +
> +	/* Allocate required fields bitmap. */
> +	uint32_t required_fields_sz =
> +		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) *
> +		sizeof(uint32_t);

let total_field_count = 31
sizeof(uint32_t) = 4
DIV_ROUND_UP(total_field_count, sizeof(uint32_t)) = 8
required_fields_sz = 9 * 4 = 32 bytes

while you only need 4 bytes to store the bitmap...

> +	format->required_fields = calloc(1, required_fields_sz);
> +	if (format->required_fields == NULL) {
> +		diag_set(OutOfMemory, required_fields_sz, "calloc",
> +			 "format->required_fields");
> +		return -1;
> +	}
> +	struct tuple_field *field;
> +	struct json_token *root = (struct json_token *)&format->fields.root;
> +	json_tree_foreach_entry_preorder(field, root, struct tuple_field,
> +					 token) {
> +		/*
> +		 * Mark all leaf non-nullable fields as required
> +		 * setting corresponding bit 1 in format
> +		 * required_fields.
> +		 */
> +		if (json_token_is_leaf(&field->token) &&
> +		    !tuple_field_is_nullable(field))
> +			bit_set(format->required_fields, field->id);
> +	}
>  	return 0;
>  }
>  
> @@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
>  		struct tuple_field *field = tuple_field_new();
>  		if (field == NULL)
>  			goto error;
> +		field->id = fieldno;
>  		field->token.num = fieldno;
>  		field->token.type = JSON_TOKEN_NUM;
>  		if (json_tree_add(&format->fields, &format->fields.root,
> @@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
>  		format->dict = dict;
>  		tuple_dictionary_ref(dict);
>  	}
> +	format->total_field_count = field_count;
> +	format->required_fields = NULL;
>  	format->refs = 0;
>  	format->id = FORMAT_ID_NIL;
>  	format->index_field_count = index_field_count;
> @@ -340,6 +369,7 @@ error:
>  static inline void
>  tuple_format_destroy(struct tuple_format *format)
>  {
> +	free(format->required_fields);
>  	tuple_format_destroy_fields(format);
>  	tuple_dictionary_unref(format->dict);
>  }
> @@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
>  	return true;
>  }
>  
> +/**
> + * Return meta information of a tuple field given a format
> + * and a unique field identifier.
> + * Typically used on error handling so it is not

Typically? There's just one place where this function is used.

> + * performance-critical and may use full-tree-traverse on lookup.
> + */
> +static struct tuple_field *
> +tuple_format_field_by_id(struct tuple_format *format, uint32_t id)
> +{
> +	struct tuple_field *field;
> +	json_tree_foreach_entry_preorder(field, &format->fields.root,
> +					 struct tuple_field, token) {
> +		if (field->id == id)
> +			return field;
> +	}
> +	return NULL;
> +}
> +
> +/**
> + * Analyze required_fields to ensure that all required fields
> + * present in tuple. Routine relies on required_fields is
> + * initialized on tuple_format_create and all required field's
> + * bits ids are set 1.
> + */
> +static int
> +tuple_format_required_fields_test(struct tuple_format *format,
> +				  uint32_t *required_fields)
> +{
> +	uint32_t bitmap_len =
> +		DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t));

This one looks different from required_fields_sz calculation in
tuple_format_create(). What's going on?

Looks like it would be a good idea to hide this calculation behind
a helper function.

> +	uint32_t missed_field_id;
> +	if (likely(bitmap_majority_test(required_fields, format->required_fields,
> +					bitmap_len, &missed_field_id) == 0))
> +		return 0;
> +	assert(missed_field_id < format->total_field_count);
> +	struct tuple_field *missed_field =

missing_field

> +		tuple_format_field_by_id(format, missed_field_id);
> +	assert(missed_field != NULL);
> +	diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field));
> +	return -1;
> +}
> +
>  /** @sa declaration for details. */
>  int
>  tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
> @@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
>  			 (unsigned) format->exact_field_count);
>  		return -1;
>  	}
> -	if (validate && field_count < format->min_field_count) {
> -		diag_set(ClientError, ER_MIN_FIELD_COUNT,
> -			 (unsigned) field_count,
> -			 (unsigned) format->min_field_count);
> -		return -1;
> -	}
>  
>  	/* first field is simply accessible, so we do not store offset to it */
>  	struct tuple_field *field = tuple_format_field(format, 0);
> +	/*
> +	 * Allocate fields_bitmap - a bitmap of fields that are
> +	 * present in tuple.
> +	 */
> +	struct region *region = &fiber()->gc;
> +	uint32_t *fields_bitmap = NULL;
> +	if (validate) {
> +		uint32_t fields_bitmap_sz =
> +			DIV_ROUND_UP(format->total_field_count,
> +				     sizeof(uint32_t)) * sizeof(uint32_t);
> +		fields_bitmap = region_alloc(region, fields_bitmap_sz);
> +		if (fields_bitmap == NULL) {
> +			diag_set(OutOfMemory, fields_bitmap_sz, "calloc",
> +				"required_fields");
> +			return -1;
> +		}
> +		memset(fields_bitmap, 0, fields_bitmap_sz);
> +		if (field_count > 0)

field_count can't be 0 - otherwise we would bail out early.

> +			bit_set(fields_bitmap, field->id);
> +	}
>  	if (validate &&
>  	    !field_mp_type_is_compatible(field->type, mp_typeof(*pos),
>  					 tuple_field_is_nullable(field))) {
> @@ -484,9 +570,12 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
>  			field_map[field->offset_slot] =
>  				(uint32_t) (pos - tuple);
>  		}
> +		if (validate)
> +			bit_set(fields_bitmap, field->id);
>  		mp_next(&pos);
>  	}
> -	return 0;
> +	return validate ?
> +	       tuple_format_required_fields_test(format, fields_bitmap) : 0;
>  }

Re: [PATCH v1 0/4] box: JSON preparatory patchset

[Vladimir Davydov]

v1? I thought it at least v2

On Thu, Dec 27, 2018 at 02:15:51PM +0300, Kirill Shcherbatov wrote:
> Preparatory patch set for JSON indexes:
> - Implemented a new json_token_path_snprint routine able to print
>   JSON path to field by field specified working like cannonical
>     snprintf routine
> - New json_token_is_leaf helper to test node is JSON tree leaf
> - Implemented a new bitmap_majority_test routine to check if the
>   passed bitmap a "majorates" bitmap b (test that a contains at
>   least all b bits).
> - Reworked tuple_init_field_map with required fields bitmap -
>   a scallable approach able to work with JSON multilevel fields
>   tree.
> 
> http://github.com/tarantool/tarantool/tree/kshch/gh-3908-fix-ast-alter-memleak

Bad link.

> https://github.com/tarantool/tarantool/issues/3908
> 
> Kirill Shcherbatov (4):
>   lib: introduce json_tree_snprint_path
>   lib: introduce json_token_is_leaf helper
>   box: introduce bitmap_majority_test routine
>   box: refactor tuple_init_field_map to use bitmap
> 
>  src/box/errcode.h                 |   2 +-
>  src/box/tuple_format.c            | 103 ++++++++++++++++++++++++++--
>  src/box/tuple_format.h            |  18 +++++
>  src/lib/bit/bit.h                 |  45 ++++++++++++
>  src/lib/json/json.c               |  68 ++++++++++++++++++
>  src/lib/json/json.h               |  21 ++++++
>  test/box/alter_limits.result      |   6 +-
>  test/box/ddl.result               |  18 ++---
>  test/box/misc.result              |   2 +-
>  test/box/sql.result               |   9 +--
>  test/box/tree_pk_multipart.result |   6 +-
>  test/engine/ddl.result            |  21 ++----
>  test/engine/null.result           |  39 ++++-------
>  test/unit/bit.c                   |  52 ++++++++++++++
>  test/unit/bit.result              |   2 +
>  test/unit/json.c                  | 110 +++++++++++++++++++++++++++++-
>  test/unit/json.result             |  32 ++++++++-
>  test/vinyl/constraint.result      |   9 +--
>  test/vinyl/errinj.result          |   9 +--
>  test/vinyl/savepoint.result       |   6 +-
>  20 files changed, 485 insertions(+), 93 deletions(-)

Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Kirill Shcherbatov]

> This function looks artificial to me, especially the fact that in case
> of error it returns the first different bit in diff_bit_id (why only the
> first one?).
> 
> Why do you need it, anyway? All you need to do in the next patch is:
>  1. Allocate required_fields bitmap on region.
>  2. Initialize it with tuple_format->required_fields.
>  3. Clear bits in it as you find that corresponding tuple fields are
>     present.
>  4. Finally, check that the bitmap is empty. If it is not report an
>     error for the first set bit.
> 
> To achieve that, you need a much simpler primitive, bit_find(), which
> would find the first set bit in a bitmap. This primitive could be reused
> in future, in contrast to this new function.
> 
> I just looked at bit.c and I see that it already has a bit iterator.
> May be, we can simply use it for finding the first bit? It looks pretty
> efficient to me.

You are right. Your approach is much better.
====================================

A new bit_find helper returns the index of the first bit set in
bitmap, bitmap_size returns size of bitmap allocation by count
of bits to work with.
We need it to test compatibility of required fields bitmap with
another one that is built for tuple on tuple_init_field_map.

Needed for #1012
---
 src/lib/bit/bit.h    | 25 +++++++++++++++++++++++++
 test/unit/bit.c      | 33 +++++++++++++++++++++++++++++++++
 test/unit/bit.result |  2 ++
 3 files changed, 60 insertions(+)

diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
index 370a0cc5d..fc3a5ba21 100644
--- a/src/lib/bit/bit.h
+++ b/src/lib/bit/bit.h
@@ -614,6 +614,31 @@ bit_iterator_next(struct bit_iterator *it)
 	return it->word_base + bit;
 }
 
+/**
+ * Return a number of a first set bit in data or SIZE_MAX
+ * if no bits are set in data.
+ */
+static inline size_t
+bit_find(const void *data, size_t size)
+{
+	struct bit_iterator it;
+	bit_iterator_init(&it, data, size, true);
+	return bit_iterator_next(&it);
+}
+
+/** Return size of bitmap by bit_count - count of bits to set. */
+static inline size_t
+bitmap_size(size_t bit_count)
+{
+	/*
+	 * Memory size must be sizeof(uint32_t)-aligned as
+	 * bit_sit/bit_clear operations use unt32_t words to
+	 * setup bits.
+	 */
+	return DIV_ROUND_UP(DIV_ROUND_UP(bit_count, CHAR_BIT),
+			    sizeof(unsigned long)) * sizeof(unsigned long);
+}
+
 #undef ITER_CTZ
 #undef ITER_UINT
 
diff --git a/test/unit/bit.c b/test/unit/bit.c
index beb89a7e4..8f68a6a83 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -206,6 +206,38 @@ test_bit_iter_empty(void)
 	footer();
 }
 
+static void
+test_bitmap(void)
+{
+	header();
+
+	fail_if(bitmap_size(0) != 0);
+	fail_if(bitmap_size(1) != sizeof(unsigned long));
+	fail_if(bitmap_size(4) != sizeof(unsigned long));
+	fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long)) !=
+		sizeof(unsigned long));
+	fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long) + 1) !=
+		2 * sizeof(unsigned long));
+
+	uint32_t test[5];
+	memset(test, 0, sizeof(test));
+	bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(test, 8);
+
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) != 8);
+	bit_clear(test, 8);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) !=
+		2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) !=
+		2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) != SIZE_MAX);
+
+	footer();
+}
+
 int
 main(void)
 {
@@ -216,4 +248,5 @@ main(void)
 	test_index();
 	test_bit_iter();
 	test_bit_iter_empty();
+	test_bitmap();
 }
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..ab9ae9d92 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3
 	*** test_bit_iter: done ***
 	*** test_bit_iter_empty ***
 	*** test_bit_iter_empty: done ***
+	*** test_bitmap ***
+	*** test_bitmap: done ***
-- 
2.19.2

Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Kirill Shcherbatov]

Hi! Thank you for review.

> let total_field_count = 31
> sizeof(uint32_t) = 4
> DIV_ROUND_UP(total_field_count, sizeof(uint32_t)) = 8
> required_fields_sz = 9 * 4 = 32 bytes
> 
> while you only need 4 bytes to store the bitmap...
> This one looks different from required_fields_sz calculation in
> tuple_format_create(). What's going on?
> 
> Looks like it would be a good idea to hide this calculation behind
> a helper function.
Implemented as a part of prev. patch.

>> +		if (field_count > 0)
> 
> field_count can't be 0 - otherwise we would bail out early.
It is not so, try paste assert here and run 

s = box.schema.space.create('test', {engine = engine})
pk = s:create_index('pk')
sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}})
s:replace{} -- Fail

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

Refactored tuple_init_field_map to fill a local bitmap and
compare it with template required_fields bitmap containing
information about required fields. Each field is mapped to
bitmap with field:id - unique field identifier.
This approach to check the required fields will work even after
the introduction of JSON paths, when the field tree becomes
multilevel.

Needed for #1012
---
 src/box/errcode.h                 |  2 +-
 src/box/tuple_format.c            | 91 ++++++++++++++++++++++++++++---
 src/box/tuple_format.h            | 20 +++++++
 test/box/alter_limits.result      |  6 +-
 test/box/ddl.result               | 18 ++----
 test/box/misc.result              |  2 +-
 test/box/sql.result               |  9 +--
 test/box/tree_pk_multipart.result |  6 +-
 test/engine/ddl.result            | 21 +++----
 test/engine/null.result           | 39 +++++--------
 test/vinyl/constraint.result      |  9 +--
 test/vinyl/errinj.result          |  9 +--
 test/vinyl/savepoint.result       |  6 +-
 13 files changed, 147 insertions(+), 91 deletions(-)

diff --git a/src/box/errcode.h b/src/box/errcode.h
index 94381f9f7..f7dbb948e 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -91,7 +91,7 @@ struct errcode_record {
 	/* 36 */_(ER_NO_SUCH_SPACE,		"Space '%s' does not exist") \
 	/* 37 */_(ER_NO_SUCH_FIELD,		"Field %d was not found in the tuple") \
 	/* 38 */_(ER_EXACT_FIELD_COUNT,		"Tuple field count %u does not match space field count %u") \
-	/* 39 */_(ER_MIN_FIELD_COUNT,		"Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \
+	/* 39 */_(ER_FIELD_MISSING,		"Tuple field %s required by space format is missing") \
 	/* 40 */_(ER_WAL_IO,			"Failed to write to disk") \
 	/* 41 */_(ER_MORE_THAN_ONE_TUPLE,	"Get() doesn't support partial keys and non-unique indexes") \
 	/* 42 */_(ER_ACCESS_DENIED,		"%s access to %s '%s' is denied for user '%s'") \
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index d7489dcd0..f4ac9e083 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -28,6 +28,8 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
+#include "bit/bit.h"
+#include "fiber.h"
 #include "json/json.h"
 #include "tuple_format.h"
 #include "coll_id_cache.h"
@@ -207,6 +209,26 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 		return -1;
 	}
 	format->field_map_size = field_map_size;
+
+	uint32_t required_fields_sz = bitmap_size(format->total_field_count);
+	format->required_fields = calloc(1, required_fields_sz);
+	if (format->required_fields == NULL) {
+		diag_set(OutOfMemory, required_fields_sz, "calloc",
+			 "format->required_fields");
+		return -1;
+	}
+	struct tuple_field *field;
+	json_tree_foreach_entry_preorder(field, &format->fields.root,
+					 struct tuple_field, token) {
+		/*
+		 * Mark all leaf non-nullable fields as "required"
+		 * setting corresponding bit 1 in bitmap
+		 * format:required_fields.
+		 */
+		if (json_token_is_leaf(&field->token) &&
+		    !tuple_field_is_nullable(field))
+			bit_set(format->required_fields, field->id);
+	}
 	return 0;
 }
 
@@ -305,6 +327,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 		struct tuple_field *field = tuple_field_new();
 		if (field == NULL)
 			goto error;
+		field->id = fieldno;
 		field->token.num = fieldno;
 		field->token.type = JSON_TOKEN_NUM;
 		if (json_tree_add(&format->fields, &format->fields.root,
@@ -324,6 +347,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 		format->dict = dict;
 		tuple_dictionary_ref(dict);
 	}
+	format->total_field_count = field_count;
+	format->required_fields = NULL;
 	format->refs = 0;
 	format->id = FORMAT_ID_NIL;
 	format->index_field_count = index_field_count;
@@ -340,6 +365,7 @@ error:
 static inline void
 tuple_format_destroy(struct tuple_format *format)
 {
+	free(format->required_fields);
 	tuple_format_destroy_fields(format);
 	tuple_dictionary_unref(format->dict);
 }
@@ -421,6 +447,24 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
 	return true;
 }
 
+/**
+ * Return meta information of a tuple field given a format
+ * and a unique field identifier.
+ * Used for error handling, so it is not performance-critical and
+ * may use full-tree-traverse on lookup.
+ */
+static struct tuple_field *
+tuple_format_field_by_id(struct tuple_format *format, uint32_t id)
+{
+	struct tuple_field *field;
+	json_tree_foreach_entry_preorder(field, &format->fields.root,
+					 struct tuple_field, token) {
+		if (field->id == id)
+			return field;
+	}
+	return NULL;
+}
+
 /** @sa declaration for details. */
 int
 tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
@@ -440,15 +484,30 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
 			 (unsigned) format->exact_field_count);
 		return -1;
 	}
-	if (validate && field_count < format->min_field_count) {
-		diag_set(ClientError, ER_MIN_FIELD_COUNT,
-			 (unsigned) field_count,
-			 (unsigned) format->min_field_count);
-		return -1;
-	}
 
 	/* first field is simply accessible, so we do not store offset to it */
 	struct tuple_field *field = tuple_format_field(format, 0);
+	/*
+	 * Allocate fields_bitmap - a copy of the initialized
+	 * format:required_fields bitmap. The field:id bits would
+	 * be nullified for founded fields during tuple parse to
+	 * raise an error when some required field is missing.
+	 */
+	struct region *region = &fiber()->gc;
+	char *fields_bitmap = NULL;
+	uint32_t fields_bitmap_sz = bitmap_size(format->total_field_count);
+	if (validate) {
+		fields_bitmap = region_alloc(region, fields_bitmap_sz);
+		if (fields_bitmap == NULL) {
+			diag_set(OutOfMemory, fields_bitmap_sz, "calloc",
+				"required_fields");
+			return -1;
+		}
+		memcpy(fields_bitmap, format->required_fields,
+		       fields_bitmap_sz);
+		if (field_count > 0)
+			bit_clear(fields_bitmap, field->id);
+	}
 	if (validate &&
 	    !field_mp_type_is_compatible(field->type, mp_typeof(*pos),
 					 tuple_field_is_nullable(field))) {
@@ -484,9 +543,27 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
 			field_map[field->offset_slot] =
 				(uint32_t) (pos - tuple);
 		}
+		if (validate)
+			bit_clear(fields_bitmap, field->id);
 		mp_next(&pos);
 	}
-	return 0;
+	if (!validate)
+		return 0;
+
+	/**
+	 * Test whether all required fields bits has been
+	 * overwritten with 0. Otherwise raise an error.
+	 */
+	size_t missing_field_id = bit_find(fields_bitmap, fields_bitmap_sz);
+	if (missing_field_id == SIZE_MAX)
+		return 0;
+	assert(missing_field_id < format->total_field_count);
+	struct tuple_field *missing_field =
+		tuple_format_field_by_id(format, missing_field_id);
+	assert(missing_field != NULL);
+	diag_set(ClientError, ER_FIELD_MISSING,
+		 tuple_field_path(missing_field));
+	return -1;
 }
 
 uint32_t
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index 21f314126..5e7cbdb8c 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -114,6 +114,8 @@ struct tuple_field {
 	struct coll *coll;
 	/** Collation identifier. */
 	uint32_t coll_id;
+	/** Field unique identifier in tuple_format. */
+	uint32_t id;
 	/** Link in tuple_format::fields. */
 	struct json_token token;
 };
@@ -173,6 +175,24 @@ struct tuple_format {
 	 * Shared names storage used by all formats of a space.
 	 */
 	struct tuple_dictionary *dict;
+	/**
+	 * Bitmap of "required fields" containing information
+	 * about fields that must present in tuple to be inserted.
+	 * Fields are mapped in bitmap with unique identifier
+	 * field::id used as index of bit to set. Bitmap is
+	 * initialized on tuple_format_create for all leaf
+	 * non-nullable fields.
+	 */
+	char *required_fields;
+	/**
+	 * Total count of format fields in fields subtree.
+	 * Used to allocate per-field memory chunks: a temporary
+	 * modifiable copy of format:required_fields on region to
+	 * test that all required fields are present in tuple
+	 * setting founded fields null on tuple_init_field_map
+	 * parse.
+	 */
+	uint32_t total_field_count;
 	/**
 	 * Fields comprising the format, organized in a tree.
 	 * First level nodes correspond to tuple fields.
diff --git a/test/box/alter_limits.result b/test/box/alter_limits.result
index 4fd80a374..4fb33dd67 100644
--- a/test/box/alter_limits.result
+++ b/test/box/alter_limits.result
@@ -842,8 +842,7 @@ index = s:create_index('string', { type = 'tree', unique =  false, parts = { 2,
 -- create index on a non-existing field
 index = s:create_index('nosuchfield', { type = 'tree', unique = true, parts = { 3, 'string'}})
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 s.index.year:drop()
 ---
@@ -864,8 +863,7 @@ s:replace{'Der Baader Meinhof Komplex'}
 ...
 index = s:create_index('year', { type = 'tree', unique = false, parts = { 2, 'unsigned'}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:drop()
 ---
diff --git a/test/box/ddl.result b/test/box/ddl.result
index d3b0d1e0e..3d6d07f43 100644
--- a/test/box/ddl.result
+++ b/test/box/ddl.result
@@ -326,33 +326,27 @@ box.internal.collation.drop('test')
 ...
 box.space._collation:auto_increment{'test'}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 3 required by space format is missing
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU'}
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 5 required by space format is missing
 ...
 box.space._collation:auto_increment{'test', 'ADMIN', 'ICU', 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 3 type does not match one required by operation: expected unsigned'
 ...
 box.space._collation:auto_increment{42, 0, 'ICU', 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 2 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 42, 'ru_RU'}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 4 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU', 42}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: 'Tuple field 5 type does not match one required by operation: expected string'
 ...
 box.space._collation:auto_increment{'test', 0, 'ICU', 'ru_RU', setmap{}} --ok
 ---
diff --git a/test/box/misc.result b/test/box/misc.result
index 9fecbce76..c3cabcc8a 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -369,7 +369,7 @@ t;
   36: box.error.NO_SUCH_SPACE
   37: box.error.NO_SUCH_FIELD
   38: box.error.EXACT_FIELD_COUNT
-  39: box.error.MIN_FIELD_COUNT
+  39: box.error.FIELD_MISSING
   40: box.error.WAL_IO
   41: box.error.MORE_THAN_ONE_TUPLE
   42: box.error.ACCESS_DENIED
diff --git a/test/box/sql.result b/test/box/sql.result
index 1818b294d..78dc47167 100644
--- a/test/box/sql.result
+++ b/test/box/sql.result
@@ -299,8 +299,7 @@ s:truncate()
 -- get away with it.
 space:insert{'Britney'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 sorted(space.index.secondary:select('Anything'))
 ---
@@ -308,8 +307,7 @@ sorted(space.index.secondary:select('Anything'))
 ...
 space:insert{'Stephanie'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 sorted(space.index.secondary:select('Anything'))
 ---
@@ -638,8 +636,7 @@ sorted(space.index.secondary:select('Britney'))
 -- try to insert the incoplete tuple
 space:replace{'Spears'}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 -- check that nothing has been updated
 space:select{'Spears'}
diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result
index 28cab3f94..93219f666 100644
--- a/test/box/tree_pk_multipart.result
+++ b/test/box/tree_pk_multipart.result
@@ -490,13 +490,11 @@ i1 = space:create_index('primary', { type = 'tree', parts = {1, 'unsigned', 3, '
 ...
 space:insert{1, 1}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 space:replace{1, 1}
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 space:drop()
 ---
diff --git a/test/engine/ddl.result b/test/engine/ddl.result
index 272ff7618..8d34d5ef4 100644
--- a/test/engine/ddl.result
+++ b/test/engine/ddl.result
@@ -77,8 +77,7 @@ index = space:create_index('primary', {type = 'tree', parts = {1, 'unsigned', 2,
 ...
 space:insert({13})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:drop()
 ---
@@ -844,13 +843,11 @@ s:replace{1, '2', {3, 3}, 4.4, -5, true, {7}, 8, 9}
 ...
 s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}}
 ---
-- error: Tuple field count 7 is less than required by space format or defined indexes
-    (expected at least 9)
+- error: Tuple field 8 required by space format is missing
 ...
 s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}, 8}
 ---
-- error: Tuple field count 8 is less than required by space format or defined indexes
-    (expected at least 9)
+- error: Tuple field 9 required by space format is missing
 ...
 s:truncate()
 ---
@@ -1334,8 +1331,7 @@ s:format(format)
 -- Fail, not enough fields.
 s:replace{2, 2, 2, 2, 2}
 ---
-- error: Tuple field count 5 is less than required by space format or defined indexes
-    (expected at least 6)
+- error: Tuple field 6 required by space format is missing
 ...
 s:replace{2, 2, 2, 2, 2, 2, 2}
 ---
@@ -1347,8 +1343,7 @@ format[7] = {name = 'field7', type = 'unsigned'}
 -- Fail, the tuple {1, ... 1} is invalid for a new format.
 s:format(format)
 ---
-- error: Tuple field count 6 is less than required by space format or defined indexes
-    (expected at least 7)
+- error: Tuple field 7 required by space format is missing
 ...
 s:drop()
 ---
@@ -2012,8 +2007,7 @@ s:create_index('sk', {parts = {4, 'unsigned'}}) -- error: field type
 ...
 s:create_index('sk', {parts = {4, 'integer', 5, 'string'}}) -- error: field missing
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 i1 = s:create_index('i1', {parts = {2, 'string'}, unique = false})
 ---
@@ -2065,8 +2059,7 @@ i3:alter{parts = {4, 'unsigned'}} -- error: field type
 ...
 i3:alter{parts = {4, 'integer', 5, 'string'}} -- error: field missing
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 i3:alter{parts = {2, 'string', 4, 'integer'}} -- ok
 ---
diff --git a/test/engine/null.result b/test/engine/null.result
index 757e63185..d55bc05bd 100644
--- a/test/engine/null.result
+++ b/test/engine/null.result
@@ -458,8 +458,7 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}})
 ...
 s:replace{1, 2} -- error
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 3 required by space format is missing
 ...
 t1 = s:replace{2, 3, 4}
 ---
@@ -530,18 +529,15 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}})
 ...
 s:replace{1, 2} -- error
 ---
-- error: Tuple field count 2 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 3 required by space format is missing
 ...
 s:replace{2, 3, 4} -- error
 ---
-- error: Tuple field count 3 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 s:replace{3, 4, 5, 6} -- error
 ---
-- error: Tuple field count 4 is less than required by space format or defined indexes
-    (expected at least 5)
+- error: Tuple field 5 required by space format is missing
 ...
 t1 = s:replace{4, 5, 6, 7, 8}
 ---
@@ -1069,8 +1065,7 @@ sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}})
 -- Test tuple_compare_slowpath, tuple_compare_with_key_slowpath.
 s:replace{} -- Fail
 ---
-- error: Tuple field count 0 is less than required by space format or defined indexes
-    (expected at least 1)
+- error: Tuple field 1 required by space format is missing
 ...
 -- Compare full vs not full.
 s:replace{2}
@@ -1769,8 +1764,7 @@ s:format(format)
 -- Field 2 is not nullable.
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:insert{5, box.NULL}
 ---
@@ -1786,8 +1780,7 @@ s:insert{5, box.NULL}
 ...
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}}
 ---
@@ -1805,8 +1798,7 @@ s:insert{5, box.NULL}
 ...
 s:insert{5}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=true}}}
 ---
@@ -1849,13 +1841,11 @@ _ = s:delete{5}
 ...
 s:format(format) -- Still fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} -- Still fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 -- Now check we can set nullability to false step by step.
 _ = s:delete{6}
@@ -1873,8 +1863,7 @@ s:insert{5, box.NULL} -- Fail.
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 format[2].is_nullable = true
 ---
@@ -1891,8 +1880,7 @@ s:insert{5, box.NULL} -- Fail.
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 format[2].is_nullable = false
 ---
@@ -1906,8 +1894,7 @@ s:select{}
 ...
 s:insert{5} -- Fail.
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:insert{9, 10} -- Success.
 ---
diff --git a/test/vinyl/constraint.result b/test/vinyl/constraint.result
index 46ed1c9eb..520a0f8aa 100644
--- a/test/vinyl/constraint.result
+++ b/test/vinyl/constraint.result
@@ -83,13 +83,11 @@ index = space:create_index('primary', { type = 'tree', parts = {1,'unsigned',2,'
 ...
 space:insert{1}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:replace{1}
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:delete{1}
 ---
@@ -101,8 +99,7 @@ space:update(1, {{'=', 1, 101}})
 ...
 space:upsert({1}, {{'+', 1, 10}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 space:get{1}
 ---
diff --git a/test/vinyl/errinj.result b/test/vinyl/errinj.result
index a081575be..23ab845b3 100644
--- a/test/vinyl/errinj.result
+++ b/test/vinyl/errinj.result
@@ -1634,8 +1634,7 @@ errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0.001)
 ...
 s:create_index('sk', {parts = {2, 'unsigned'}}) -- must fail
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0)
 ---
@@ -2087,8 +2086,7 @@ fiber.sleep(0)
 ...
 s:format{{'key', 'unsigned'}, {'value', 'unsigned'}} -- must fail
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:select()
 ---
@@ -2112,8 +2110,7 @@ fiber.sleep(0)
 ...
 s:create_index('sk', {parts = {2, 'unsigned'}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 2)
+- error: Tuple field 2 required by space format is missing
 ...
 s:select()
 ---
diff --git a/test/vinyl/savepoint.result b/test/vinyl/savepoint.result
index d7b57a775..a62f2ea80 100644
--- a/test/vinyl/savepoint.result
+++ b/test/vinyl/savepoint.result
@@ -124,8 +124,7 @@ index2 = space:create_index('secondary', { parts = {2, 'int', 3, 'str'} })
 ...
 space:insert({1})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 2 required by space format is missing
 ...
 space:insert({1, 1, 'a'})
 ---
@@ -623,8 +622,7 @@ space:insert({4, 2, 'b'})
 ...
 space:upsert({2}, {{'=', 4, 1000}})
 ---
-- error: Tuple field count 1 is less than required by space format or defined indexes
-    (expected at least 3)
+- error: Tuple field 2 required by space format is missing
 ...
 index3:delete({3, 'a'})
 ---
-- 
2.19.2

Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Vladimir Davydov]

On Sat, Dec 29, 2018 at 03:58:32PM +0300, Kirill Shcherbatov wrote:
> > This function looks artificial to me, especially the fact that in case
> > of error it returns the first different bit in diff_bit_id (why only the
> > first one?).
> > 
> > Why do you need it, anyway? All you need to do in the next patch is:
> >  1. Allocate required_fields bitmap on region.
> >  2. Initialize it with tuple_format->required_fields.
> >  3. Clear bits in it as you find that corresponding tuple fields are
> >     present.
> >  4. Finally, check that the bitmap is empty. If it is not report an
> >     error for the first set bit.
> > 
> > To achieve that, you need a much simpler primitive, bit_find(), which
> > would find the first set bit in a bitmap. This primitive could be reused
> > in future, in contrast to this new function.
> > 
> > I just looked at bit.c and I see that it already has a bit iterator.
> > May be, we can simply use it for finding the first bit? It looks pretty
> > efficient to me.
> 
> You are right. Your approach is much better.
> ====================================
> 
> A new bit_find helper returns the index of the first bit set in
> bitmap, bitmap_size returns size of bitmap allocation by count
> of bits to work with.
> We need it to test compatibility of required fields bitmap with
> another one that is built for tuple on tuple_init_field_map.
> 
> Needed for #1012
> ---
>  src/lib/bit/bit.h    | 25 +++++++++++++++++++++++++
>  test/unit/bit.c      | 33 +++++++++++++++++++++++++++++++++
>  test/unit/bit.result |  2 ++
>  3 files changed, 60 insertions(+)
> 
> diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
> index 370a0cc5d..fc3a5ba21 100644
> --- a/src/lib/bit/bit.h
> +++ b/src/lib/bit/bit.h
> @@ -614,6 +614,31 @@ bit_iterator_next(struct bit_iterator *it)
>  	return it->word_base + bit;
>  }
>  
> +/**
> + * Return a number of a first set bit in data or SIZE_MAX
> + * if no bits are set in data.
> + */
> +static inline size_t
> +bit_find(const void *data, size_t size)
> +{
> +	struct bit_iterator it;
> +	bit_iterator_init(&it, data, size, true);
> +	return bit_iterator_next(&it);
> +}

Ouch, you seems to have misunderstood me. What I meant when I talked
about the need of bit_find() was: *if* bit_iterator is not fast enough,
introduce an efficient bit_find() helper, *otherwise* use bit_iterator -
there's no point wrapping bit_iterator_next() in a new helper function.
Sorry for misunderstanding.

> +
> +/** Return size of bitmap by bit_count - count of bits to set. */
> +static inline size_t
> +bitmap_size(size_t bit_count)

This helper should be closer to the beginning of the file, because
header files are typically organized as follows: first macros and
trivial inline helpers, then more complex structures and functions.

> +{
> +	/*
> +	 * Memory size must be sizeof(uint32_t)-aligned as

sizeof(uint32_t)? But you align by (long). Please fix the comment.
I guess we can say that the size of a bitmap should be word-aligned.

> +	 * bit_sit/bit_clear operations use unt32_t words to
> +	 * setup bits.
> +	 */
> +	return DIV_ROUND_UP(DIV_ROUND_UP(bit_count, CHAR_BIT),
> +			    sizeof(unsigned long)) * sizeof(unsigned long);

This is correct indeed, and I guess it's OK to leave it as is, but to me
first converting bit count to byte count and only then to word count
looks confusing. Why not convert bit count to word count directly?

	size_t word_count = DIV_ROUND_UP(bit_count, CHAR_BIT * sizeof(long));
	return word_count * sizeof(long);

> +}
> +
>  #undef ITER_CTZ
>  #undef ITER_UINT
>  
> diff --git a/test/unit/bit.c b/test/unit/bit.c
> index beb89a7e4..8f68a6a83 100644
> --- a/test/unit/bit.c
> +++ b/test/unit/bit.c
> @@ -206,6 +206,38 @@ test_bit_iter_empty(void)
>  	footer();
>  }
>  
> +static void
> +test_bitmap(void)
> +{
> +	header();
> +
> +	fail_if(bitmap_size(0) != 0);
> +	fail_if(bitmap_size(1) != sizeof(unsigned long));
> +	fail_if(bitmap_size(4) != sizeof(unsigned long));
> +	fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long)) !=

I think we should use is() for testing bitmap_size().

Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Vladimir Davydov]

On Sat, Dec 29, 2018 at 03:58:34PM +0300, Kirill Shcherbatov wrote:
> > field_count can't be 0 - otherwise we would bail out early.
> It is not so, try paste assert here and run 
> 
> s = box.schema.space.create('test', {engine = engine})
> pk = s:create_index('pk')
> sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}})
> s:replace{} -- Fail

OK, I confused tuple field count with format field count.

Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Kirill Shcherbatov]

Hi! Ok... Also changed the only place in following patch.

===============================
A new bitmap_size routine returns size of bitmap allocation
aligned by sizeof(unsigned long) words by count of bits to work
with. Memory chunk must be aligned as bit_set/bit_clear
functions use unsigned long words to setup bits.
We need bitmap_size to make an allocation for format:fields to
test compatibility of required fields bitmap with another one
that is built for parsed tuple on tuple_init_field_map.

Needed for #1012
---
 src/lib/bit/bit.h        | 13 +++++++++++++
 test/unit/CMakeLists.txt |  2 +-
 test/unit/bit.c          | 27 +++++++++++++++++++++++++++
 test/unit/bit.result     |  8 ++++++++
 4 files changed, 49 insertions(+), 1 deletion(-)

diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
index 370a0cc5d..04be818b2 100644
--- a/src/lib/bit/bit.h
+++ b/src/lib/bit/bit.h
@@ -238,6 +238,19 @@ bit_clear(void *data, size_t pos)
 	return prev;
 }
 
+/**
+ * Return sizeof(unsigned long)-words aligned size of bitmap by
+ * bit_count - count of bits to set. Size must be aligned, as
+ * bit_sit/bit_clear operations use unsigned long words to setup
+ * bit.
+ */
+static inline size_t
+bitmap_size(size_t bit_count)
+{
+	size_t word_count = DIV_ROUND_UP(bit_count, CHAR_BIT * sizeof(long));
+	return word_count * sizeof(long);
+}
+
 /**
  * @cond false
  * @brief Naive implementation of ctz.
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 0025d3611..5b2f152e3 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -36,7 +36,7 @@ add_executable(rope.test rope.c)
 target_link_libraries(rope.test salad)
 add_executable(int96.test int96.cc)
 add_executable(bit.test bit.c bit.c)
-target_link_libraries(bit.test bit)
+target_link_libraries(bit.test bit unit)
 add_executable(bitset_basic.test bitset_basic.c)
 target_link_libraries(bitset_basic.test bitset)
 add_executable(bitset_iterator.test bitset_iterator.c)
diff --git a/test/unit/bit.c b/test/unit/bit.c
index beb89a7e4..67a7ccd63 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -206,6 +206,32 @@ test_bit_iter_empty(void)
 	footer();
 }
 
+static void
+test_bitmap(void)
+{
+	header();
+	plan(5);
+
+	size_t rc = bitmap_size(0);
+	is(rc, 0, "empty bitmap: have %zu expected %d", rc, 0);
+	rc = bitmap_size(1);
+	is(rc, sizeof(unsigned long), "1-item bitmap: have %zu expected %lu",
+	   rc, sizeof(unsigned long));
+	rc = bitmap_size(4);
+	is(rc, sizeof(unsigned long), "4-items bitmap: have %zu expected %lu",
+	   rc, sizeof(unsigned long));
+	rc = bitmap_size(CHAR_BIT * sizeof(unsigned long));
+	is(rc, sizeof(unsigned long), "%lu-items bitmap: have %zu expected %lu",
+	   CHAR_BIT * sizeof(unsigned long), rc, sizeof(unsigned long));
+	rc = bitmap_size(CHAR_BIT * sizeof(unsigned long) + 1);
+	is(rc, 2 * sizeof(unsigned long),
+	   "%lu-items bitmap: have %zu expected %lu",
+	   CHAR_BIT * sizeof(unsigned long) + 1, rc, 2 * sizeof(unsigned long));
+
+	check_plan();
+	footer();
+}
+
 int
 main(void)
 {
@@ -216,4 +242,5 @@ main(void)
 	test_index();
 	test_bit_iter();
 	test_bit_iter_empty();
+	test_bitmap();
 }
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..d99cfbf01 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -891,3 +891,11 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3
 	*** test_bit_iter: done ***
 	*** test_bit_iter_empty ***
 	*** test_bit_iter_empty: done ***
+	*** test_bitmap ***
+1..5
+ok 1 - empty bitmap: have 0 expected 0
+ok 2 - 1-item bitmap: have 8 expected 8
+ok 3 - 4-items bitmap: have 8 expected 8
+ok 4 - 64-items bitmap: have 8 expected 8
+ok 5 - 65-items bitmap: have 16 expected 16
+	*** test_bitmap: done ***
-- 
2.19.2

Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Vladimir Davydov]

On Sat, Dec 29, 2018 at 04:57:00PM +0300, Kirill Shcherbatov wrote:
> +/**
> + * Return sizeof(unsigned long)-words aligned size of bitmap by
> + * bit_count - count of bits to set. Size must be aligned, as
> + * bit_sit/bit_clear operations use unsigned long words to setup
> + * bit.
> + */

Changed the comment to

/**
 * @brief Returns the size of memory needed to store a bitmap
 * of \a bit_count bits.
 * The function rounds the size up to a multiple of the word
 * size, which is required by bit_set() and bit_clear().
 * @param bit_count number of bits in the bitmap
 * @retval bitmap size, in bytes
 */

(used doxygen, because all other comments in the file are formated in
the same way)

> +1..5
> +ok 1 - empty bitmap: have 0 expected 0
> +ok 2 - 1-item bitmap: have 8 expected 8
> +ok 3 - 4-items bitmap: have 8 expected 8
> +ok 4 - 64-items bitmap: have 8 expected 8
> +ok 5 - 65-items bitmap: have 16 expected 16
> +	*** test_bitmap: done ***

OK, now I see why you used fail_unless in the previous version - because
all other tests in the file use it. Then you should've told me that
instead of blindly following my instructions - I can make mistakes too.
Changed the test back to fail_unless for consistency and pushed the
patch to 2.1.

Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Vladimir Davydov]

On Sat, Dec 29, 2018 at 03:58:34PM +0300, Kirill Shcherbatov wrote:
> Refactored tuple_init_field_map to fill a local bitmap and

It's not refactoring, it's a rework.

> compare it with template required_fields bitmap containing
> information about required fields. Each field is mapped to
> bitmap with field:id - unique field identifier.
> This approach to check the required fields will work even after
> the introduction of JSON paths, when the field tree becomes
> multilevel.
> 
> Needed for #1012

> @@ -440,15 +484,30 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map,
>  			 (unsigned) format->exact_field_count);
>  		return -1;
>  	}
> -	if (validate && field_count < format->min_field_count) {
> -		diag_set(ClientError, ER_MIN_FIELD_COUNT,
> -			 (unsigned) field_count,
> -			 (unsigned) format->min_field_count);
> -		return -1;
> -	}
>  
>  	/* first field is simply accessible, so we do not store offset to it */
>  	struct tuple_field *field = tuple_format_field(format, 0);
> +	/*
> +	 * Allocate fields_bitmap - a copy of the initialized
> +	 * format:required_fields bitmap. The field:id bits would
> +	 * be nullified for founded fields during tuple parse to
> +	 * raise an error when some required field is missing.
> +	 */
> +	struct region *region = &fiber()->gc;
> +	char *fields_bitmap = NULL;
> +	uint32_t fields_bitmap_sz = bitmap_size(format->total_field_count);
> +	if (validate) {
> +		fields_bitmap = region_alloc(region, fields_bitmap_sz);
> +		if (fields_bitmap == NULL) {
> +			diag_set(OutOfMemory, fields_bitmap_sz, "calloc",

s/calloc/region

Memory allocated on the region isn't freed when the function returns...

> +				"required_fields");
> +			return -1;
> +		}
> +		memcpy(fields_bitmap, format->required_fields,
> +		       fields_bitmap_sz);
> +		if (field_count > 0)
> +			bit_clear(fields_bitmap, field->id);
> +	}
>  	if (validate &&
>  	    !field_mp_type_is_compatible(field->type, mp_typeof(*pos),
>  					 tuple_field_is_nullable(field))) {

If field_count is 0, then you'll access uninitialized memory here ^^^

I'm kinda tired of reviewing this simple patch so I fixed these issues
by myself, fixed grammar in the comments, and pushed the patch to 2.1.