From: Christian Couder <christian.couder@gmail.com>
To: git@vger.kernel.org
Cc: "Junio C Hamano" <gitster@pobox.com>,
"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
"Nguyen Thai Ngoc Duy" <pclouds@gmail.com>,
"Stefan Beller" <sbeller@google.com>,
"Eric Sunshine" <sunshine@sunshineco.com>,
"Ramsay Jones" <ramsay@ramsayjones.plus.com>,
"Jeff King" <peff@peff.net>,
"Karsten Blees" <karsten.blees@gmail.com>,
"Matthieu Moy" <Matthieu.Moy@grenoble-inp.fr>,
"Christian Couder" <chriscool@tuxfamily.org>
Subject: [PATCH v3 05/49] builtin/apply: extract line_by_line_fuzzy_match() from match_fragment()
Date: Tue, 24 May 2016 10:10:42 +0200 [thread overview]
Message-ID: <20160524081126.16973-6-chriscool@tuxfamily.org> (raw)
In-Reply-To: <20160524081126.16973-1-chriscool@tuxfamily.org>
The match_fragment() function is very big and contains a big special case
algorithm that does line by line fuzzy matching. So let's extract this
algorithm in a separate line_by_line_fuzzy_match() function.
Reviewed-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
builtin/apply.c | 126 +++++++++++++++++++++++++++++++-------------------------
1 file changed, 71 insertions(+), 55 deletions(-)
diff --git a/builtin/apply.c b/builtin/apply.c
index bb8bf7f..7bab466 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -2242,6 +2242,74 @@ static void update_pre_post_images(struct image *preimage,
postimage->nr -= reduced;
}
+static int line_by_line_fuzzy_match(struct image *img,
+ struct image *preimage,
+ struct image *postimage,
+ unsigned long try,
+ int try_lno,
+ int preimage_limit)
+{
+ int i;
+ size_t imgoff = 0;
+ size_t preoff = 0;
+ size_t postlen = postimage->len;
+ size_t extra_chars;
+ char *buf;
+ char *preimage_eof;
+ char *preimage_end;
+ struct strbuf fixed;
+ char *fixed_buf;
+ size_t fixed_len;
+
+ for (i = 0; i < preimage_limit; i++) {
+ size_t prelen = preimage->line[i].len;
+ size_t imglen = img->line[try_lno+i].len;
+
+ if (!fuzzy_matchlines(img->buf + try + imgoff, imglen,
+ preimage->buf + preoff, prelen))
+ return 0;
+ if (preimage->line[i].flag & LINE_COMMON)
+ postlen += imglen - prelen;
+ imgoff += imglen;
+ preoff += prelen;
+ }
+
+ /*
+ * Ok, the preimage matches with whitespace fuzz.
+ *
+ * imgoff now holds the true length of the target that
+ * matches the preimage before the end of the file.
+ *
+ * Count the number of characters in the preimage that fall
+ * beyond the end of the file and make sure that all of them
+ * are whitespace characters. (This can only happen if
+ * we are removing blank lines at the end of the file.)
+ */
+ buf = preimage_eof = preimage->buf + preoff;
+ for ( ; i < preimage->nr; i++)
+ preoff += preimage->line[i].len;
+ preimage_end = preimage->buf + preoff;
+ for ( ; buf < preimage_end; buf++)
+ if (!isspace(*buf))
+ return 0;
+
+ /*
+ * Update the preimage and the common postimage context
+ * lines to use the same whitespace as the target.
+ * If whitespace is missing in the target (i.e.
+ * if the preimage extends beyond the end of the file),
+ * use the whitespace from the preimage.
+ */
+ extra_chars = preimage_end - preimage_eof;
+ strbuf_init(&fixed, imgoff + extra_chars);
+ strbuf_add(&fixed, img->buf + try, imgoff);
+ strbuf_add(&fixed, preimage_eof, extra_chars);
+ fixed_buf = strbuf_detach(&fixed, &fixed_len);
+ update_pre_post_images(preimage, postimage,
+ fixed_buf, fixed_len, postlen);
+ return 1;
+}
+
static int match_fragment(struct image *img,
struct image *preimage,
struct image *postimage,
@@ -2331,61 +2399,9 @@ static int match_fragment(struct image *img,
* fuzzy matching. We collect all the line length information because
* we need it to adjust whitespace if we match.
*/
- if (ws_ignore_action == ignore_ws_change) {
- size_t imgoff = 0;
- size_t preoff = 0;
- size_t postlen = postimage->len;
- size_t extra_chars;
- char *preimage_eof;
- char *preimage_end;
- for (i = 0; i < preimage_limit; i++) {
- size_t prelen = preimage->line[i].len;
- size_t imglen = img->line[try_lno+i].len;
-
- if (!fuzzy_matchlines(img->buf + try + imgoff, imglen,
- preimage->buf + preoff, prelen))
- return 0;
- if (preimage->line[i].flag & LINE_COMMON)
- postlen += imglen - prelen;
- imgoff += imglen;
- preoff += prelen;
- }
-
- /*
- * Ok, the preimage matches with whitespace fuzz.
- *
- * imgoff now holds the true length of the target that
- * matches the preimage before the end of the file.
- *
- * Count the number of characters in the preimage that fall
- * beyond the end of the file and make sure that all of them
- * are whitespace characters. (This can only happen if
- * we are removing blank lines at the end of the file.)
- */
- buf = preimage_eof = preimage->buf + preoff;
- for ( ; i < preimage->nr; i++)
- preoff += preimage->line[i].len;
- preimage_end = preimage->buf + preoff;
- for ( ; buf < preimage_end; buf++)
- if (!isspace(*buf))
- return 0;
-
- /*
- * Update the preimage and the common postimage context
- * lines to use the same whitespace as the target.
- * If whitespace is missing in the target (i.e.
- * if the preimage extends beyond the end of the file),
- * use the whitespace from the preimage.
- */
- extra_chars = preimage_end - preimage_eof;
- strbuf_init(&fixed, imgoff + extra_chars);
- strbuf_add(&fixed, img->buf + try, imgoff);
- strbuf_add(&fixed, preimage_eof, extra_chars);
- fixed_buf = strbuf_detach(&fixed, &fixed_len);
- update_pre_post_images(preimage, postimage,
- fixed_buf, fixed_len, postlen);
- return 1;
- }
+ if (ws_ignore_action == ignore_ws_change)
+ return line_by_line_fuzzy_match(img, preimage, postimage,
+ try, try_lno, preimage_limit);
if (ws_error_action != correct_ws_error)
return 0;
--
2.8.3.443.gaeee61e
next prev parent reply other threads:[~2016-05-24 8:16 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-05-24 8:10 [PATCH v3 00/49] libify apply and use lib in am, part 1 Christian Couder
2016-05-24 8:10 ` [PATCH v3 01/49] builtin/apply: make gitdiff_verify_name() return void Christian Couder
2016-05-24 8:10 ` [PATCH v3 02/49] builtin/apply: avoid parameter shadowing 'p_value' global Christian Couder
2016-05-24 8:10 ` [PATCH v3 03/49] builtin/apply: avoid parameter shadowing 'linenr' global Christian Couder
2016-05-24 8:10 ` [PATCH v3 04/49] builtin/apply: avoid local variable shadowing 'len' parameter Christian Couder
2016-05-24 8:10 ` Christian Couder [this message]
2016-05-24 8:10 ` [PATCH v3 06/49] builtin/apply: move 'options' variable into cmd_apply() Christian Couder
2016-05-24 8:10 ` [PATCH v3 07/49] builtin/apply: move 'read_stdin' global " Christian Couder
2016-05-24 8:10 ` [PATCH v3 08/49] builtin/apply: introduce 'struct apply_state' to start libifying Christian Couder
2016-05-24 8:10 ` [PATCH v3 09/49] builtin/apply: move 'state' init into init_apply_state() Christian Couder
2016-05-24 8:10 ` [PATCH v3 10/49] builtin/apply: move 'unidiff_zero' global into 'struct apply_state' Christian Couder
2016-05-24 8:10 ` [PATCH v3 11/49] builtin/apply: move 'check' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 12/49] builtin/apply: move 'check_index' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 13/49] builtin/apply: move 'apply_in_reverse' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 14/49] builtin/apply: move 'apply_with_reject' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 15/49] builtin/apply: move 'apply_verbosely' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 16/49] builtin/apply: move 'update_index' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 17/49] builtin/apply: move 'allow_overlap' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 18/49] builtin/apply: move 'cached' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 19/49] builtin/apply: move 'diffstat' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 20/49] builtin/apply: move 'numstat' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 21/49] builtin/apply: move 'summary' " Christian Couder
2016-05-24 8:10 ` [PATCH v3 22/49] builtin/apply: move 'threeway' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 23/49] builtin/apply: move 'no_add' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 24/49] builtin/apply: move 'unsafe_paths' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 25/49] builtin/apply: move 'line_termination' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 26/49] builtin/apply: move 'fake_ancestor' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 27/49] builtin/apply: move 'p_context' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 28/49] builtin/apply: move 'apply' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 29/49] builtin/apply: move 'patch_input_file' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 30/49] builtin/apply: move 'limit_by_name' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 31/49] builtin/apply: move 'has_include' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 32/49] builtin/apply: move 'p_value' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 33/49] builtin/apply: move 'p_value_known' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 34/49] builtin/apply: move 'root' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 35/49] builtin/apply: move 'whitespace_error' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 36/49] builtin/apply: move 'whitespace_option' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 37/49] builtin/apply: remove whitespace_option arg from set_default_whitespace_mode() Christian Couder
2016-05-24 8:11 ` [PATCH v3 38/49] builtin/apply: move 'squelch_whitespace_errors' into 'struct apply_state' Christian Couder
2016-05-24 8:11 ` [PATCH v3 39/49] builtin/apply: move 'applied_after_fixing_ws' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 40/49] builtin/apply: move 'ws_error_action' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 41/49] builtin/apply: move 'ws_ignore_action' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 42/49] builtin/apply: move 'max_change' and 'max_len' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 43/49] builtin/apply: move 'state_linenr' global " Christian Couder
2016-05-24 8:11 ` [PATCH v3 44/49] builtin/apply: move 'fn_table' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 45/49] builtin/apply: move 'symlink_changes' " Christian Couder
2016-05-24 8:11 ` [PATCH v3 46/49] builtin/apply: move 'state' check into check_apply_state() Christian Couder
2016-05-24 8:11 ` [PATCH v3 47/49] builtin/apply: move applying patches into apply_all_patches() Christian Couder
2016-05-24 8:11 ` [PATCH v3 48/49] builtin/apply: move 'lock_file' global into 'struct apply_state' Christian Couder
2016-06-01 17:23 ` Junio C Hamano
2016-06-03 9:42 ` Christian Couder
2016-05-24 8:11 ` [PATCH v3 49/49] builtin/apply: move 'newfd' " Christian Couder
2016-05-24 8:59 ` [PATCH v3 00/49] libify apply and use lib in am, part 1 Christian Couder
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160524081126.16973-6-chriscool@tuxfamily.org \
--to=christian.couder@gmail.com \
--cc=Matthieu.Moy@grenoble-inp.fr \
--cc=avarab@gmail.com \
--cc=chriscool@tuxfamily.org \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=karsten.blees@gmail.com \
--cc=pclouds@gmail.com \
--cc=peff@peff.net \
--cc=ramsay@ramsayjones.plus.com \
--cc=sbeller@google.com \
--cc=sunshine@sunshineco.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).