Re: [PATCH 3/3 v2] use cache for function names in hunk headers
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:49:40
René Scharfe [off-list ref] writes:
Am 23.09.2010 09:04, schrieb Clemens Buchacher:quoted
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.
quoted hunk
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)