Re: [PATCH 2/4] trailer: avoid unnecessary splitting on lines
Jonathan Tan <jonathantanmy@google.com> writes:
Show 18 quoted lines
> diff --git a/trailer.c b/trailer.c
> index 6d8375b..d4d9e10 100644
> --- a/trailer.c
> +++ b/trailer.c
> @@ -102,12 +102,12 @@ static int same_trailer(struct trailer_item *a, struct arg_item *b)
> return same_token(a, b) && same_value(a, b);
> }
>
> -static inline int contains_only_spaces(const char *str)
> +static inline int is_blank_line(const char *str)
> {
> const char *s = str;
> - while (*s && isspace(*s))
> + while (*s && *s != '\n' && isspace(*s))
> s++;
> - return !*s;
> + return !*s || *s == '\n';
> }This used to be fed a single line and did not have to worry about stopping at the end of a line, but now it does have to, and does so correctly. OK.
And the updated function name certainly reflects the fact that this is (now) about a line-oriented processing better, and this renaming makes sense.
Show 14 quoted lines
> @@ -566,13 +566,18 @@ static int token_matches_item(const char *tok, struct arg_item *item, int tok_le
> }
>
> /*
> - * Return the location of the first separator in line, or -1 if there is no
> - * separator.
> + * Return the location of the first separator in the given line, or -1 if there
> + * is no separator.
> + *
> + * The interests parameter must contain the acceptable separators and may
> + * contain '\n'. If interests contains '\n', the input line is considered to
> + * end at the first newline encountered. Otherwise, the input line is
> + * considered to end at its null terminator.
> */
The name of that terminating byte is NUL, not NULL.
Show 10 quoted lines
> -static int find_separator(const char *line, const char *separators)
> +static int find_separator(const char *line, const char *interests)
> {
> - int loc = strcspn(line, separators);
> - if (!line[loc])
> + int loc = strcspn(line, interests);
> + if (!line[loc] || line[loc] == '\n')
> return -1;
> return loc;
> }I am not sure interests is a better name than separators. If the original used "interests", I do not think it is worth renaming it to "separators", and I doubt that the renaming of the parameter in this patch is an improvement.
Show 17 quoted lines
> @@ -688,51 +693,71 @@ static void process_command_line_args(struct list_head *arg_head,
> -static struct strbuf **read_input_file(const char *file)
> +static void read_input_file(struct strbuf *sb, const char *file)
> {
> - struct strbuf **lines;
> - struct strbuf sb = STRBUF_INIT;
> -
> if (file) {
> - if (strbuf_read_file(&sb, file, 0) < 0)
> + if (strbuf_read_file(sb, file, 0) < 0)
> die_errno(_("could not read input file '%s'"), file);
> } else {
> - if (strbuf_read(&sb, fileno(stdin), 0) < 0)
> + if (strbuf_read(sb, fileno(stdin), 0) < 0)
> die_errno(_("could not read from stdin"));
> }
> +}The original used to return an array of strbufs but we now just read into a single strbuf. The caller may need to do more, or perhaps the early split into array of strbufs was mostly wasteful use of more flexible data structure. We'll find out when we read what happens to the data read here.
Show 5 quoted lines
> +static const char *next_line(const char *str)
> +{
> + const char *nl = strchrnul(str, '\n');
> + return nl + !!*nl;
> +}"next_line()" gives a pointer to either the beginning of the next line, or points at the NUL that terminates the whole buffer. OK.
Show 16 quoted lines
> +/*
> + * Return the position of the start of the last line. If len is 0, return -1.
> + */
> +static int last_line(const char *buf, size_t len)
> +{
> + int i;
> + if (len == 0)
> + return -1;
> + if (len == 1)
> + return 0;
> + /*
> + * Skip the last character (in addition to the null terminator),
> + * because if the last character is a newline, it is considered as part
> + * of the last line anyway.
> + */
> + i = len - 2;... and if the last character is not a newline, the line is an incomplete last line. OK.
Show 7 quoted lines
> - return lines;
> + for (; i >= 0; i--) {
> + if (buf[i] == '\n')
> + return i + 1;
> + }
> + return 0;
> }Show 24 quoted lines
> /*
> - * Return the (0 based) index of the start of the patch or the line
> - * count if there is no patch in the message.
> + * Return the position of the start of the patch or the length of str if there
> + * is no patch in the message.
> */
> -static int find_patch_start(struct strbuf **lines, int count)
> +static int find_patch_start(const char *str)
> {
> - int i;
> + const char *s;
>
> - /* Get the start of the patch part if any */
> - for (i = 0; i < count; i++) {
> - if (starts_with(lines[i]->buf, "---"))
> - return i;
> + for (s = str; *s; s = next_line(s)) {
> + if (starts_with(s, "---"))
> + return s - str;
> }
>
> - return count;
> + return s - str;
> }The original assumed that the input was first split into an array of strbufs and found the index that begins with a line "---". We have a flat buffer of input, and find a line that begins with "---". The returned value is different (i.e. used to be line-number, now it is the byte offset). OK.
Show 7 quoted lines
> /*
> - * Return the (0 based) index of the first trailer line or count if
> - * there are no trailers. Trailers are searched only in the lines from
> - * index (count - 1) down to index 0.
> + * Return the position of the first trailer line or len if there are no
> + * trailers.
> */
OK, the idea is the same as the above; it used to be line-based, but now it is counted in byte-offset.
Show 6 quoted lines
> -static int find_trailer_start(struct strbuf **lines, int count)
> +static int find_trailer_start(const char *buf, size_t len)
> {
> - int start, end_of_title, only_spaces = 1;
> + const char *s;
> + int title_end, l, only_spaces = 1;between end-of-title and title-end, I have slight preference for the former over the latter, but just like separators vs interests, this rename is probably more distracting than is worth.
Show 23 quoted lines
> int recognized_prefix = 0, trailer_lines = 0, non_trailer_lines = 0;
> /*
> * Number of possible continuation lines encountered. This will be
> @@ -742,15 +767,18 @@ static int find_trailer_start(struct strbuf **lines, int count)
> * are to be considered non-trailers).
> */
> int possible_continuation_lines = 0;
> + int ret;
> +
> + char *sep_nl = xstrfmt("%s\n", separators);
>
> /* The first paragraph is the title and cannot be trailers */
> - for (start = 0; start < count; start++) {
> - if (lines[start]->buf[0] == comment_line_char)
> + for (s = buf; s < buf + len; s = next_line(s)) {
> + if (s[0] == comment_line_char)
> continue;
> - if (contains_only_spaces(lines[start]->buf))
> + if (is_blank_line(s))
> break;
> }
> - end_of_title = start;
> + title_end = s - buf;OK, we skipped to find the first blank line. The original had an array of strbufs to iterate over and didn't have to look for LF but now we do, but it is just the matter of calling next_line() that is simple enough.
Show 6 quoted lines
> @@ -758,30 +786,33 @@ static int find_trailer_start(struct strbuf **lines, int count)
> * trailers, or (ii) contains at least one Git-generated trailer and
> * consists of at least 25% trailers.
> */
> - for (start = count - 1; start >= end_of_title; start--) {
> + for (l = last_line(buf, len); l >= title_end; l = last_line(buf, l)) {The iteration is conceptually the same. We used to iterate from the last line in the input down to the first blank line that ends the title paragraph. We do the same but now we are byte-offset based, so we start from last_line() of the entire buffer, and go back one-line-at-a-time by calling last_line(buf, l). OK.
Show 22 quoted lines
> + const char *bol = buf + l;
> const char **p;
> int separator_pos;
>
> - if (lines[start]->buf[0] == comment_line_char) {
> + if (bol[0] == comment_line_char) {
> non_trailer_lines += possible_continuation_lines;
> possible_continuation_lines = 0;
> continue;
> }
> - if (contains_only_spaces(lines[start]->buf)) {
> + if (is_blank_line(bol)) {
> if (only_spaces)
> continue;
> non_trailer_lines += possible_continuation_lines;
> if (recognized_prefix &&
> trailer_lines * 3 >= non_trailer_lines)
> - return start + 1;
> - if (trailer_lines && !non_trailer_lines)
> - return start + 1;
> - return count;
> + ret = next_line(bol) - buf;The original called the line we are looking at as "start"; the corresponding byte-offset is "l", and "bol" is the pointer to the beginning of the current line. Returning next_line(bol)-buf is equivalent to returning "start + 1" in the original. OK.
> + else if (trailer_lines && !non_trailer_lines)
> + ret = next_line(bol) - buf;
> + else
> + ret = len;
> + goto cleanup;
We are no longer "return"ing directly from this part of the code, and instead saving the return value in "ret" and jumping there where the real "return" is. We need cleanup because we have an extra allocation of separator + LF thing up above.
> ...
The changes to the remainder of this function shows that the original lines[] were accessed read-only and it only used lines[]->buf without lines[]->len, which is a strong indication that an array of strbuf was an overkill.
The rewrite looks to be a logical equivalent, which is good.
Show 18 quoted lines
> @@ -817,88 +848,73 @@ static int find_trailer_start(struct strbuf **lines, int count)
> ...
> -/* Get the index of the end of the trailers */
> -static int find_trailer_end(struct strbuf **lines, int patch_start)
> +/* Return the position of the end of the trailers. */
> +static int find_trailer_end(const char *buf, size_t len)
> {
> - struct strbuf sb = STRBUF_INIT;
> - int i, ignore_bytes;
> -
> - for (i = 0; i < patch_start; i++)
> - strbuf_addbuf(&sb, lines[i]);
> - ignore_bytes = ignore_non_trailer(sb.buf, sb.len);
> - strbuf_release(&sb);
> - for (i = patch_start - 1; i >= 0 && ignore_bytes > 0; i--)
> - ignore_bytes -= lines[i]->len;
> -
> - return i + 1;That indeed was grossly wasteful. Things split into lines[] are concatenated back only to call a single helper function that reports a byte offset, and then lines[]->len is counted separately to find the line that the byte offset falls in.
> + return len - ignore_non_trailer(buf, len);
Using the byte-offset based data structure throughout the code makes it a lot simpler. Good.
Show 23 quoted lines
> }
>
> -static int has_blank_line_before(struct strbuf **lines, int start)
> +static int ends_with_blank_line(const char *buf, size_t len)
> {
> - for (;start >= 0; start--) {
> - if (lines[start]->buf[0] == comment_line_char)
> - continue;
> - return contains_only_spaces(lines[start]->buf);
> - }
> - return 0;
> -}
> -
> -static void print_lines(FILE *outfile, struct strbuf **lines, int start, int end)
> -{
> - int i;
> - for (i = start; lines[i] && i < end; i++)
> - fprintf(outfile, "%s", lines[i]->buf);
> + int ll = last_line(buf, len);
> + if (ll < 0)
> + return 0;
> + return is_blank_line(buf + ll);
> }Two helpers "has-blank-line-before" and "print-lines" are gone. Let's see how updated code does things without them.
Show 27 quoted lines
> static int process_input_file(FILE *outfile,
> - struct strbuf **lines,
> + const char *str,
> struct list_head *head)
> {
> - int count = 0;
> - int patch_start, trailer_start, trailer_end, i;
> + int patch_start, trailer_start, trailer_end;
> struct strbuf tok = STRBUF_INIT;
> struct strbuf val = STRBUF_INIT;
> struct trailer_item *last = NULL;
> + struct strbuf *trailer, **trailer_lines, **ptr;
>
> - /* Get the line count */
> - while (lines[count])
> - count++;
> -
> - patch_start = find_patch_start(lines, count);
> - trailer_end = find_trailer_end(lines, patch_start);
> - trailer_start = find_trailer_start(lines, trailer_end);
> + patch_start = find_patch_start(str);
> + trailer_end = find_trailer_end(str, patch_start);
> + trailer_start = find_trailer_start(str, trailer_end);
>
> /* Print lines before the trailers as is */
> - print_lines(outfile, lines, 0, trailer_start);
> + fwrite(str, 1, trailer_start, outfile);Ah, of course, if you don't split into an array of strbuf then you do not need a helper that iterates over the array and prints.
> - if (!has_blank_line_before(lines, trailer_start - 1))
> + if (!ends_with_blank_line(str, trailer_start))
> fprintf(outfile, "\n");
Then if the part before the trailer doesn't end with a blank, we force a blank.
This is not a new issue, but this makes me wonder what happens when there is no trailer to emit after this. Do we end up with an extra blank line?
Show 6 quoted lines
> /* Parse trailer lines */
> - for (i = trailer_start; i < trailer_end; i++) {
> + trailer_lines = strbuf_split_buf(str + trailer_start,
> + trailer_end - trailer_start,
> + '\n',
> + 0);We want each line NUL terminated while going over the trailer part line-by-line so that it is easy to do _addf(&buf, "%s"). Use of strbuf_split_buf() to split them into an array of strbufs is close to the way the original did it, so that is why it is done here.
OK. If we had a helper function that would split into an array of "const char *"s, I suspect it would have worked equally well. In the loop, we only look at ->buf of the strbuf instances and do not take advantage of the fact that the length of each line is known. But that is better left as a further clean-up to the future.
Thanks. This step looks like a regression-free rewrite.
