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

[Vladimir Davydov <vdavydov.dev@gmail.com>]

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();
>  }