[tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class
Vladimir Davydov
vdavydov.dev at gmail.com
Mon Jan 21 23:25:29 MSK 2019
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();
> }
More information about the Tarantool-patches
mailing list