From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Mon, 21 Jan 2019 23:25:29 +0300 From: Vladimir Davydov Subject: Re: [tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class Message-ID: <20190121202529.r7wwnzcesdh34sda@esperanza> References: <9613f79e65d9838763422aae0bfb3ca9e2901a32.1547645639.git.kshcherbatov@gmail.com> <20190117115843.nqellm5mmsglqnlf@tkn_work_nb> <842c55cd-5d3f-e857-42f4-94d648c88273@tarantool.org> <20190117163409.hvga32kxxgcc5sat@tkn_work_nb> <1ba698d1-8450-f2d3-7717-11adbf0d5f4f@tarantool.org> <20190121112541.hkqylj7hwcjeq526@tkn_work_nb> <2259a346-76dd-f721-176f-bfad39b25b5e@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <2259a346-76dd-f721-176f-bfad39b25b5e@gmail.com> To: Kirill Shcherbatov Cc: Kirill Shcherbatov , Alexander Turenko , tarantool-patches@freelists.org List-ID: On Mon, Jan 21, 2019 at 03:35:39PM +0300, Kirill Shcherbatov wrote: > > 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 Total number of items > + * calculated with mp_decode_map() or mp_decode_array(). > + */ > + uint32_t size; > + /** > + * Count of items already processed. Must be less or less than > + * 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 'the' before decoding is redundant > + decoding nested MP_ARRAY and MP_MAP msgpack containers without Bad comment formatting (* missing). > + * recursion. This allows you to determine that the parsing of Please avoid using 'you' in comments. > + * 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_PROTO is used only for function prototypes. For bodies you should use MP_IMPL. Please take a look at any other function, say mp_decode_array, and implement your methods in the same fashion. > +mp_stack_init(struct mp_stack *stack, uint32_t size, struct mp_frame *frames) We typically call constructors _create. > +{ > + 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. \retval is missing > + */ > +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. \retval > + */ > +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. There's \pre tag for pre-conditions. Please take a look at mp_check_array description. > + * \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. \pre > + * \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. \pre > + * \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 \pre > + * 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: s/have/has s/when/if Don't use comma (,) before 'if' or 'when'. Parsed what? Has been parsed, you wanted to say? > + * 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) { I just looked at msgpuck.c - it turns out we have a very similar function called mp_snprint, which we use for debug output. What about reimplementing it without recursion using the new mp_stack API? It would make the purpose of mp_stack clear by giving a usage example right in the msgpuck code. Besides we wouldn't need to write any additional tests. What do you think? > + 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(); > }