From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: Re: [tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class References: <9613f79e65d9838763422aae0bfb3ca9e2901a32.1547645639.git.kshcherbatov@gmail.com> <20190117115843.nqellm5mmsglqnlf@tkn_work_nb> <842c55cd-5d3f-e857-42f4-94d648c88273@tarantool.org> <20190117163409.hvga32kxxgcc5sat@tkn_work_nb> From: Kirill Shcherbatov Message-ID: <1ba698d1-8450-f2d3-7717-11adbf0d5f4f@tarantool.org> Date: Fri, 18 Jan 2019 13:32:28 +0300 MIME-Version: 1.0 In-Reply-To: <20190117163409.hvga32kxxgcc5sat@tkn_work_nb> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org, Alexander Turenko Cc: vdavydov.dev@gmail.com, Kirill Shcherbatov List-ID: 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 | 136 +++++++++++++++++++++++++++++++++++++++++++++++++ test/msgpuck.c | 79 +++++++++++++++++++++++++++- 2 files changed, 214 insertions(+), 1 deletion(-) diff --git a/msgpuck.h b/msgpuck.h index b0d4967..b9bbe78 100644 --- a/msgpuck.h +++ b/msgpuck.h @@ -359,6 +359,45 @@ 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 service contexts 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 mp_frames descriptors having at least + * mp_stack::size items. + */ + struct mp_frame *frames; +}; + /** * \brief Determine MsgPack type by a first byte \a c of encoded data. * @@ -1184,6 +1223,103 @@ 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 service context allocation to use, + * must have at least \a size 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. + * \retval a pointer to a top stack frame. + */ +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..6d5a7a5 100644 --- a/test/msgpuck.c +++ b/test/msgpuck.c @@ -1093,10 +1093,86 @@ test_overflow() return check_plan(); } +static inline bool +mp_stack_top_is_internal_item(struct mp_stack *mp_stack) +{ + struct mp_frame *frame = mp_stack_top(mp_stack); + return frame->curr > 0 && frame->curr < frame->size; +} + +static int +test_mpstack() +{ + plan(1); + header(); + + char tuple[1024]; + char *wptr = tuple; + const char *descr = "{\"first\", {\"key1\": \"one\", \"key2\": {2}}, {3}}"; + wptr = mp_encode_array(wptr, 3); + wptr = mp_encode_str(wptr, "first", 5); + wptr = mp_encode_map(wptr, 2); + wptr = mp_encode_str(wptr, "key1", 4); + wptr = mp_encode_str(wptr, "one", 3); + wptr = mp_encode_str(wptr, "key2", 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); + const char *rptr = tuple; + char buff[1024]; + wptr = buff; + + struct mp_frame mp_frames[3]; + struct mp_stack mp_stack; + mp_stack_init(&mp_stack, 3, mp_frames); + while (1) { + uint32_t len; + if (!mp_stack_is_empty(&mp_stack) && + mp_stack_top(&mp_stack)->type == MP_MAP) { + const char *key = mp_decode_str(&rptr, &len); + wptr += sprintf(wptr, "\"%.*s\": ", len, key); + } + enum mp_type type = mp_typeof(*rptr); + if (type == MP_ARRAY || type == 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, "{"); + } else { + if (type == MP_STR) { + const char *str = mp_decode_str(&rptr, &len); + wptr += sprintf(wptr, "\"%.*s\"", len, str); + } else if (type == MP_UINT) { + uint64_t num = mp_decode_uint(&rptr); + wptr += sprintf(wptr, "%u", (unsigned)num); + } else { + mp_unreachable(); + } + if (mp_stack_top_is_internal_item(&mp_stack)) + wptr += sprintf(wptr, ", "); + } + while (mp_stack_advance(&mp_stack)) { + mp_stack_pop(&mp_stack); + wptr += sprintf(wptr, "}"); + if (mp_stack_is_empty(&mp_stack)) + goto end; + if (mp_stack_top_is_internal_item(&mp_stack)) + wptr += sprintf(wptr, ", "); + } + } +end: + 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 +1193,7 @@ int main() test_mp_check(); test_numbers(); test_overflow(); + test_mpstack(); return check_plan(); } -- 2.19.2