Re: [PATCH 3/3 v2] use cache for function names in hunk headers
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Sep 30, 2010, 18:33 UTC
- Message-ID
- <7v62xnjd3j.fsf@alter.siamese.dyndns.org>
- In-Reply-To
- <4C9F7450.9060208@lsrfire.ath.cx>
René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
Show 12 quoted lines
> Am 23.09.2010 09:04, schrieb Clemens Buchacher: >> For each hunk, xdl_find_func searches the preimage >> for a function name until the beginning of the >> file. If the file does not contain any function >> names, this search has complexity O(n2) in the >> number of hunks n. > ... > How about something like this? It also removes an outdated comment. The > inlining part should probably split out in its own patch.. > > xdiff/xemit.c | 38 ++++++++++++++------------------------ > 1 files changed, 14 insertions(+), 24 deletions(-)
I had to wonder if this optimization closes a door for us to extend the function header patterns to allow inspecting multiple lines.
Suppose that a rule says that a header line is a first non-blank line that follows two or more blank lines. E.g.
... the end of a paragraph that is not followed by two blank lines.
(blank line)
This is not a header, but is part of the previous paragraph group.
... body of the paragraph here ...
and this is the tail of the paragraph group.
(blank line)
(blank line)
This begins a new paragraph group.
And this is the second line of it.Under such a rule, "This begins a new paragraph group." is a header line. If the first hunk begins at the second blank line before that header, we will scan down to the beginning of the file and will find a header that comes before that header line, and remember it in funclen/funcbuf[]. The next scan will stop after looking at one blank line before "This begins a new paragraph group.", instead of going down to the beginning, and would not to have a chance to notice that "This begins a new paragraph group." indeed has two blank lines before it. It would instead keep returning the header we found before this header.
I do not think this is such a big issue, though. In order to allow such a multi-line matching, the loop in xdl_find_func(), now inlined, needs to be restructured anyway, and whoever is doing such an enhancement hopefully will notice that s/he needs to look behind beyond (s1-1) at that point.
So an Ack from me.
Thanks.
Show 63 quoted lines
> diff --git a/xdiff/xemit.c b/xdiff/xemit.c
> index c4bedf0..a663f21 100644
> --- a/xdiff/xemit.c
> +++ b/xdiff/xemit.c
> @@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)
> return -1;
> }
>
> -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
> - find_func_t ff, void *ff_priv) {
> -
> - /*
> - * Be quite stupid about this for now. Find a line in the old file
> - * before the start of the hunk (and context) which starts with a
> - * plausible character.
> - */
> -
> - const char *rec;
> - long len;
> -
> - while (i-- > 0) {
> - len = xdl_get_rec(xf, i, &rec);
> - if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)
> - return;
> - }
> - *ll = 0;
> -}
> -
> -
> static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
> xdemitconf_t const *xecfg) {
> xdfile_t *xdf = &xe->xdf1;
> @@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
> xdchange_t *xch, *xche;
> char funcbuf[80];
> long funclen = 0;
> + long funclineprev = -1;
> find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff;
>
> if (xecfg->flags & XDL_EMIT_COMMON)
> @@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
> */
>
> if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
> - xdl_find_func(&xe->xdf1, s1, funcbuf,
> - sizeof(funcbuf), &funclen,
> - ff, xecfg->find_func_priv);
> + long l;
> + for (l = s1 - 1; l >= 0 && l > funclineprev; l--) {
> + const char *rec;
> + long reclen = xdl_get_rec(&xe->xdf1, l, &rec);
> + long newfunclen = ff(rec, reclen, funcbuf,
> + sizeof(funcbuf),
> + xecfg->find_func_priv);
> + if (newfunclen >= 0) {
> + funclen = newfunclen;
> + break;
> + }
> + }
> + funclineprev = s1 - 1;
> }
> if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
> funcbuf, funclen, ecb) < 0)