Re: [tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class

[Kirill Shcherbatov <kshcherbatov@gmail.com>]

> If you doubt on some wording comments ask me and engage Vladimir into
> discussion.

Introduced a new mp_stack class to make complex msgpack parsing.
The structure is needed in order to facilitate the decoding
nested MP_ARRAY and MP_MAP msgpack containers without recursion.
This allows you to determine that the parsing of the current
container is complete.

Needed for #1012
---
 msgpuck.h      | 134 +++++++++++++++++++++++++++++++++++++++++++++++++
 test/msgpuck.c |  92 ++++++++++++++++++++++++++++++++-
 2 files changed, 225 insertions(+), 1 deletion(-)

diff --git a/msgpuck.h b/msgpuck.h
index b0d4967..98c5b25 100644
--- a/msgpuck.h
+++ b/msgpuck.h
@@ -359,6 +359,44 @@ enum mp_type {
 	MP_EXT
 };
 
+/** Message pack MP_MAP or MP_ARRAY container descriptor. */
+struct mp_frame {
+	/** MP frame type calculated with mp_typeof(). */
+	enum mp_type type;
+	/**
+	 * Total items in MP_MAP or MP_ARRAY container
+	 * calculated with mp_decode_map() or mp_decode_array().
+	 */
+	uint32_t size;
+	/**
+	 * Count of items already processed. Must be less or
+	 * equal to mp_frame::size member.
+	 */
+	uint32_t curr;
+};
+
+/**
+ * Stack of map/array descriptors mp_frame to do complex msgpack
+   parse. The structure is needed in order to facilitate the
+   decoding nested MP_ARRAY and MP_MAP msgpack containers without
+ * recursion. This allows you to determine that the parsing of
+ * the current container is complete.
+*/
+struct mp_stack {
+	/** The maximum stack depth. */
+	uint32_t size;
+	/**
+	 * Count of used stack frames. Corresponds to the index
+	 * in the array to perform the push operation. Must be
+	 * less or equal to mp_stack::size member.
+	 */
+	uint32_t used;
+	/**
+	 * Array of size mp_stack::size of mp_frames.
+	 */
+	struct mp_frame *frames;
+};
+
 /**
  * \brief Determine MsgPack type by a first byte \a c of encoded data.
  *
@@ -1184,6 +1222,102 @@ mp_check(const char **data, const char *end);
  * {{{ Implementation
  */
 
+/**
+ * \brief Initialize mp_stack \a stack of specified size \a size
+ * and user-allocated array \a frames.
+ * The \a frames allocation must have at least \a size mp_frame
+ * items.
+ * \param stack - the pointer to a mp_stack to initialize.
+ * \param size - stack size, count of stack::frames to use.
+ * \param frames - mp_frame preallocated array of size \a size
+ *                 of struct mp_frame items
+ */
+MP_PROTO void
+mp_stack_init(struct mp_stack *stack, uint32_t size, struct mp_frame *frames)
+{
+	stack->frames = frames;
+	stack->size = size;
+	stack->used = 0;
+}
+
+/**
+ * \brief Test if mp_stack \a stack is empty.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ */
+MP_PROTO bool
+mp_stack_is_empty(struct mp_stack *stack)
+{
+	return stack->used == 0;
+}
+
+/**
+ * \brief Test if mp_stack \a stack is full.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ */
+MP_PROTO bool
+mp_stack_is_full(struct mp_stack *stack)
+{
+	return stack->used >= stack->size;
+}
+
+/**
+ * \brief Pop the top mp_stack \a stack frame.
+ * The \a stack must not be empty.
+ * \param stack - the pointer to a mp_stack to operate with.
+ */
+MP_PROTO void
+mp_stack_pop(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	--stack->used;
+}
+
+/**
+ * \brief Get a pointer to a top mp_stack \a stack frame.
+ * \param stack - the pointer to a mp_stack to operate with.
+ * The \a stack must not be empty.
+ * \retval a pointer to a top stack frame.
+ */
+MP_PROTO struct mp_frame *
+mp_stack_top(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	return &stack->frames[stack->used - 1];
+}
+
+/**
+ * \brief Construct a new mp_frame and push it on to mp_stack
+ * \a stack. The \a stack must not be full.
+ * \param stack - the pointer to a stack to operate with.
+ * \param type - the type of mp_frame to create.
+ * \param size - size size of mp_frame to create.
+ */
+MP_PROTO void
+mp_stack_push(struct mp_stack *stack, enum mp_type type, uint32_t size)
+{
+	assert(!mp_stack_is_full(stack));
+	uint32_t idx = stack->used++;
+	stack->frames[idx].type = type;
+	stack->frames[idx].size = size;
+	stack->frames[idx].curr = 0;
+}
+
+/**
+ * \brief Advance a mp_stack_top()::\a curr attribute of the
+ * \a stack. The \a stack must not be empty. The function also
+ * signals when it moves over the last item.
+ * \param stack - the pointer to a stack to operate with
+ * \retval true, when the top frame have already parsed:
+ *         mp_stack_top()::\a curr > mp_stack_top()::\a size;
+ *         false otherwise.
+ */
+MP_PROTO bool
+mp_stack_advance(struct mp_stack *stack)
+{
+	struct mp_frame *frame = mp_stack_top(stack);
+	return ++frame->curr > frame->size;
+}
+
 /** \cond false */
 extern const enum mp_type mp_type_hint[];
 extern const int8_t mp_parser_hint[];
diff --git a/test/msgpuck.c b/test/msgpuck.c
index 9265453..80a9def 100644
--- a/test/msgpuck.c
+++ b/test/msgpuck.c
@@ -1093,10 +1093,99 @@ test_overflow()
 	return check_plan();
 }
 
+static inline bool
+mp_stack_advance_and_print(struct mp_stack *mp_stack, char **wptr)
+{
+	struct mp_frame *frame = mp_stack_top(mp_stack);
+	if (frame->curr > 0 && frame->curr < frame->size)
+		*wptr += sprintf(*wptr, ", ");
+	return mp_stack_advance(mp_stack);
+}
+
+static void
+mp_stack_json_print(struct mp_stack *mp_stack, const char *tuple, char *buff)
+{
+	const char *rptr = tuple;
+	char *wptr = buff;
+	while (true) {
+		uint32_t len;
+		const char *str;
+		if (!mp_stack_is_empty(mp_stack) &&
+		    mp_stack_top(mp_stack)->type == MP_MAP) {
+			str = mp_decode_str(&rptr, &len);
+			wptr += sprintf(wptr, "\"%.*s\": ", len, str);
+		}
+		enum mp_type type = mp_typeof(*rptr);
+		switch (type) {
+		case MP_ARRAY:
+		case MP_MAP: {
+			uint32_t size = type == MP_ARRAY ?
+					mp_decode_array(&rptr) :
+					mp_decode_map(&rptr);
+			mp_stack_push(mp_stack, type, size);
+			wptr += sprintf(wptr, type == MP_ARRAY ? "[" : "{");
+			break;
+		}
+		case MP_STR: {
+			str = mp_decode_str(&rptr, &len);
+			wptr += sprintf(wptr, "\"%.*s\"", len, str);
+			break;
+		}
+		case MP_UINT: {
+			uint64_t num = mp_decode_uint(&rptr);
+			wptr += sprintf(wptr, "%u", (unsigned)num);
+			break;
+		}
+		default:
+			mp_unreachable();
+		}
+		while (mp_stack_advance_and_print(mp_stack, &wptr)) {
+			enum mp_type type = mp_stack_top(mp_stack)->type;
+			assert(type == MP_ARRAY || type == MP_MAP);
+			mp_stack_pop(mp_stack);
+			wptr += sprintf(wptr, type == MP_ARRAY ? "]" : "}");
+			if (mp_stack_is_empty(mp_stack))
+				return;
+		}
+	}
+}
+
+static int
+test_mpstack()
+{
+	plan(1);
+	header();
+
+	char tuple[1024];
+	char *wptr = tuple;
+	const char *descr = "[\"one\", {\"k1\": \"two\", \"k2\": [2]}, [3]]";
+	wptr = mp_encode_array(wptr, 3);
+	wptr = mp_encode_str(wptr, "one", 5);
+	wptr = mp_encode_map(wptr, 2);
+	wptr = mp_encode_str(wptr, "k1", 4);
+	wptr = mp_encode_str(wptr, "two", 3);
+	wptr = mp_encode_str(wptr, "k2", 4);
+	wptr = mp_encode_array(wptr, 1);
+	wptr = mp_encode_uint(wptr, 2);
+	wptr = mp_encode_array(wptr, 1);
+	wptr = mp_encode_uint(wptr, 3);
+
+	struct mp_frame mp_frames[3];
+	struct mp_stack mp_stack;
+	mp_stack_init(&mp_stack, 3, mp_frames);
+	char buff[1024];
+	mp_stack_json_print(&mp_stack, tuple, buff);
+
+	is(strcmp(buff, descr), 0, "valid mpstack json description: "
+	   "have \"%s\" expected \"%s\"", buff, descr);
+
+	footer();
+	return check_plan();
+}
 
 int main()
 {
-	plan(20);
+	plan(21);
 	test_uints();
 	test_ints();
 	test_bools();
@@ -1117,6 +1206,7 @@ int main()
 	test_mp_check();
 	test_numbers();
 	test_overflow();
+	test_mpstack();
 
 	return check_plan();
 }