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

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

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.
Reworked mp_snprint and mp_fprint routines to use mp_stack
instead of recursion.

Needed for #1012
---
 msgpuck.c      |  63 ++++++++++---------
 msgpuck.h      | 167 +++++++++++++++++++++++++++++++++++++++++++++++++
 test/msgpuck.c |  35 ++++++++++-
 3 files changed, 235 insertions(+), 30 deletions(-)

diff --git a/msgpuck.c b/msgpuck.c
index 72b800c..e77ad5b 100644
--- a/msgpuck.c
+++ b/msgpuck.c
@@ -232,8 +232,12 @@ mp_format(char *data, size_t data_size, const char *format, ...)
 	return res;
 }
 
-#define MP_PRINT(SELF, PRINTF) \
+#define MP_PRINT(PRINTF) \
 {										\
+	struct mp_frame frames[MP_PRINT_MAX_DEPTH];				\
+	struct mp_stack stack;							\
+	mp_stack_create(&stack, MP_PRINT_MAX_DEPTH, frames);			\
+next:										\
 	switch (mp_typeof(**data)) {						\
 	case MP_NIL:								\
 		mp_decode_nil(data);						\
@@ -266,31 +270,21 @@ mp_format(char *data, size_t data_size, const char *format, ...)
 		break;								\
 	}									\
 	case MP_ARRAY:								\
-	{									\
-		uint32_t count = mp_decode_array(data);				\
-		PRINTF("[");							\
-		uint32_t i;							\
-		for (i = 0; i < count; i++) {					\
-			if (i)							\
-				PRINTF(", ");					\
-			SELF(data);						\
-		}								\
-		PRINTF("]");							\
-		break;								\
-	}									\
 	case MP_MAP:								\
 	{									\
-		uint32_t count = mp_decode_map(data);				\
-		PRINTF("{");							\
-		uint32_t i;							\
-		for (i = 0; i < count; i++) {					\
-			if (i)							\
-				PRINTF(", ");					\
-			SELF(data);						\
-			PRINTF(": ");						\
-			SELF(data);						\
+		enum mp_type type = mp_typeof(**data);				\
+		if (!mp_stack_is_full(&stack)) {				\
+			uint32_t count = type == MP_ARRAY ?			\
+				mp_decode_array(data) : 2*mp_decode_map(data);	\
+			mp_stack_push(&stack, type, count);			\
+		} else {							\
+			/*							\
+			* Skip msgpack items that do not			\
+			* fit onto the stack.					\
+			*/							\
+			PRINTF(type == MP_ARRAY ? "[...]" : "{...}");		\
+			mp_next(data);						\
 		}								\
-		PRINTF("}");							\
 		break;								\
 	}									\
 	case MP_BOOL:								\
@@ -310,6 +304,21 @@ mp_format(char *data, size_t data_size, const char *format, ...)
 		mp_unreachable();						\
 		return -1;							\
 	}									\
+	while (!mp_stack_is_empty(&stack)) {					\
+		struct mp_frame *frame = mp_stack_top(&stack);			\
+		if (!mp_stack_advance(&stack)) {				\
+			PRINTF(frame->type == MP_ARRAY ? "]" : "}");		\
+			mp_stack_pop(&stack);					\
+		} else {							\
+			if (frame->curr == 1)					\
+				PRINTF(frame->type == MP_ARRAY ? "[" : "{");	\
+			else if (frame->type == MP_MAP && frame->curr % 2 == 0)	\
+				PRINTF(": ");					\
+			else							\
+				PRINTF(", ");					\
+			goto next;						\
+		}								\
+	}									\
 }
 
 static inline int
@@ -323,10 +332,8 @@ mp_fprint_internal(FILE *file, const char **data)
 	total_bytes += bytes;							\
 } while (0)
 #define PRINT(...) HANDLE(fprintf, __VA_ARGS__)
-#define SELF(...) HANDLE(mp_fprint_internal, __VA_ARGS__)
-MP_PRINT(SELF, PRINT)
+MP_PRINT(PRINT)
 #undef HANDLE
-#undef SELF
 #undef PRINT
 	return total_bytes;
 }
@@ -359,10 +366,8 @@ mp_snprint_internal(char *buf, int size, const char **data)
 	}									\
 } while (0)
 #define PRINT(...) HANDLE(snprintf, __VA_ARGS__)
-#define SELF(...) HANDLE(mp_snprint_internal, __VA_ARGS__)
-MP_PRINT(SELF, PRINT)
+MP_PRINT(PRINT)
 #undef HANDLE
-#undef SELF
 #undef PRINT
 	return total_bytes;
 }
diff --git a/msgpuck.h b/msgpuck.h
index b0d4967..e2a90fa 100644
--- a/msgpuck.h
+++ b/msgpuck.h
@@ -1176,6 +1176,122 @@ mp_next(const char **data);
 MP_PROTO int
 mp_check(const char **data, const char *end);
 
+/**
+ * The maximum msgpack nesting depth supported by mp_snprint().
+ * Everything beyond that will be omitted (replaced with "...").
+ */
+#ifndef MP_PRINT_MAX_DEPTH
+#define MP_PRINT_MAX_DEPTH 32
+#endif
+
+/** Message pack MP_MAP or MP_ARRAY container descriptor. */
+struct mp_frame {
+	/** MP frame type calculated with mp_typeof(). */
+	enum mp_type type;
+	/**
+	 * Total number of 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 than 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
+ * decoding nested MP_ARRAY and MP_MAP msgpack containers without
+ * recursion. This allows 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 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_create(struct mp_stack *stack, uint32_t size, struct mp_frame *frames);
+
+/**
+ * \brief Test if mp_stack \a stack is empty.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ * \retval true if mp_stack is empty, false otherwise.
+ */
+MP_PROTO bool
+mp_stack_is_empty(struct mp_stack *stack);
+
+/**
+ * \brief Test if mp_stack \a stack is full.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ * \retval true if mp_stack is full, false otherwise.
+ */
+MP_PROTO bool
+mp_stack_is_full(struct mp_stack *stack);
+
+/**
+ * \brief Pop the top mp_stack \a stack frame.
+ * \param stack - the pointer to a mp_stack to operate with.
+ * \pre mp_stack_is_empty(stack) == false
+ */
+MP_PROTO void
+mp_stack_pop(struct mp_stack *stack);
+
+/**
+ * \brief Get a pointer to a top mp_stack \a stack frame.
+ * \param stack - the pointer to a mp_stack to operate with.
+ * \retval a pointer to a top stack frame.
+ * \pre mp_stack_is_empty(stack) == false
+ */
+MP_PROTO struct mp_frame *
+mp_stack_top(struct mp_stack *stack);
+
+/**
+ * \brief Construct a new mp_frame and push it on to mp_stack
+ * \a stack.
+ * \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.
+ * \pre mp_stack_is_full(stack) == false
+ */
+MP_PROTO void
+mp_stack_push(struct mp_stack *stack, enum mp_type type, uint32_t size);
+
+/**
+ * \brief Advance a mp_stack_top()::\a curr attribute of the
+ * \a stack. The function also signals when it moves over the
+ * last item.
+ * \param stack - the pointer to a stack to operate with
+ * \retval false if the top stack frame has been fully processed:
+ *         mp_stack_top()::\a curr > mp_stack_top()::\a size;
+ *         true otherwise.
+ * \pre mp_stack_is_empty(stack) == false
+ */
+MP_PROTO bool
+mp_stack_advance(struct mp_stack *stack);
+
 /*
  * }}}
  */
@@ -2176,6 +2292,57 @@ mp_check(const char **data, const char *end)
 	return 0;
 }
 
+MP_IMPL void
+mp_stack_create(struct mp_stack *stack, uint32_t size, struct mp_frame *frames)
+{
+	stack->frames = frames;
+	stack->size = size;
+	stack->used = 0;
+}
+
+MP_IMPL bool
+mp_stack_is_empty(struct mp_stack *stack)
+{
+	return stack->used == 0;
+}
+
+MP_IMPL bool
+mp_stack_is_full(struct mp_stack *stack)
+{
+	return stack->used >= stack->size;
+}
+
+MP_IMPL void
+mp_stack_pop(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	--stack->used;
+}
+
+MP_IMPL struct mp_frame *
+mp_stack_top(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	return &stack->frames[stack->used - 1];
+}
+
+MP_IMPL 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;
+}
+
+MP_IMPL bool
+mp_stack_advance(struct mp_stack *stack)
+{
+	struct mp_frame *frame = mp_stack_top(stack);
+	return ++frame->curr <= frame->size;
+}
+
 /** \endcond */
 
 /*
diff --git a/test/msgpuck.c b/test/msgpuck.c
index 9265453..73ace19 100644
--- a/test/msgpuck.c
+++ b/test/msgpuck.c
@@ -764,7 +764,7 @@ test_format(void)
 int
 test_mp_print()
 {
-	plan(10);
+	plan(12);
 	header();
 
 	char msgpack[128];
@@ -838,6 +838,39 @@ test_mp_print()
 	int rc = mp_fprint(stdin, msgpack);
 	is(rc, -1, "mp_fprint I/O error");
 
+	/* Test mp_snprint max nesting depth. */
+	int mp_buff_sz = MP_PRINT_MAX_DEPTH * mp_sizeof_array(1) +
+			 mp_sizeof_uint(1);
+	int template_sz = 2 * (MP_PRINT_MAX_DEPTH + 1) + 3 + 1;
+	char *mp_buff = malloc(mp_buff_sz);
+	char *template = malloc(template_sz);
+	char *decoded = malloc(template_sz);
+	if (mp_buff == NULL || template == NULL || decoded == NULL) {
+		fail("Failed to malloc memory");
+		goto end;
+	}
+	char *buf_wptr = mp_buff;
+	char *template_wptr = template;
+	for (int i = 0; i <= 2 * (MP_PRINT_MAX_DEPTH + 1); i++) {
+		if (i < MP_PRINT_MAX_DEPTH + 1) {
+			buf_wptr = mp_encode_array(buf_wptr, 1);
+			*(template_wptr++) = '[';
+		} else if (i == MP_PRINT_MAX_DEPTH + 1) {
+			buf_wptr = mp_encode_uint(buf_wptr, 1);
+			template_wptr += sprintf(template_wptr, "...");
+		} else {
+			*(template_wptr++) = ']';
+		}
+	}
+	*(template_wptr++) = '\0';
+	rc = mp_snprint(decoded, template_sz, mp_buff);
+	ok(rc == template_sz - 1, "mp_snprint max nesting depth return value");
+	ok(memcmp(decoded, template, template_sz - 1) == 0,
+	   "mp_snprint max nesting depth result");
+end:
+	free(decoded);
+	free(template);
+	free(mp_buff);
 	footer();
 	return check_plan();
 }
-- 
2.19.2