[tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class
Kirill Shcherbatov
kshcherbatov at tarantool.org
Wed Jan 23 11:23:51 MSK 2019
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
More information about the Tarantool-patches
mailing list