git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 05/49] builtin/apply: extract line_by_line_fuzzy_match() from match_fragment()

From
Christian Couder <christian.couder@gmail.com>
Date
May 24, 2016, 08:10 UTC
Message-ID
<20160524081126.16973-6-chriscool@tuxfamily.org>
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
Previous: Christian CouderNext: Christian Couder
Message 6 of 53 in “libify apply and use lib in am, part 1”
  1. 00/49 libify apply and use lib in am, part 1Christian Couder, May 24, 2016
  2. 01/49 builtin/apply: make gitdiff_verify_name() return voidChristian Couder, May 24, 2016
  3. 02/49 builtin/apply: avoid parameter shadowing 'p_value' globalChristian Couder, May 24, 2016
  4. 03/49 builtin/apply: avoid parameter shadowing 'linenr' globalChristian Couder, May 24, 2016
  5. 04/49 builtin/apply: avoid local variable shadowing 'len' parameterChristian Couder, May 24, 2016
  6. 05/49 builtin/apply: extract line_by_line_fuzzy_match() from match_fragment()Christian Couder, May 24, 2016
  7. 06/49 builtin/apply: move 'options' variable into cmd_apply()Christian Couder, May 24, 2016
  8. 07/49 builtin/apply: move 'read_stdin' global into cmd_apply()Christian Couder, May 24, 2016
  9. 08/49 builtin/apply: introduce 'struct apply_state' to start libifyingChristian Couder, May 24, 2016
  10. 09/49 builtin/apply: move 'state' init into init_apply_state()Christian Couder, May 24, 2016
  11. 10/49 builtin/apply: move 'unidiff_zero' global into 'struct apply_state'Christian Couder, May 24, 2016
  12. 11/49 builtin/apply: move 'check' global into 'struct apply_state'Christian Couder, May 24, 2016
  13. 12/49 builtin/apply: move 'check_index' global into 'struct apply_state'Christian Couder, May 24, 2016
  14. 13/49 builtin/apply: move 'apply_in_reverse' global into 'struct apply_state'Christian Couder, May 24, 2016
  15. 14/49 builtin/apply: move 'apply_with_reject' global into 'struct apply_state'Christian Couder, May 24, 2016
  16. 15/49 builtin/apply: move 'apply_verbosely' global into 'struct apply_state'Christian Couder, May 24, 2016
  17. 16/49 builtin/apply: move 'update_index' global into 'struct apply_state'Christian Couder, May 24, 2016
  18. 17/49 builtin/apply: move 'allow_overlap' global into 'struct apply_state'Christian Couder, May 24, 2016
  19. 18/49 builtin/apply: move 'cached' global into 'struct apply_state'Christian Couder, May 24, 2016
  20. 19/49 builtin/apply: move 'diffstat' global into 'struct apply_state'Christian Couder, May 24, 2016
  21. 20/49 builtin/apply: move 'numstat' global into 'struct apply_state'Christian Couder, May 24, 2016
  22. 21/49 builtin/apply: move 'summary' global into 'struct apply_state'Christian Couder, May 24, 2016
  23. 22/49 builtin/apply: move 'threeway' global into 'struct apply_state'Christian Couder, May 24, 2016
  24. 23/49 builtin/apply: move 'no_add' global into 'struct apply_state'Christian Couder, May 24, 2016
  25. 24/49 builtin/apply: move 'unsafe_paths' global into 'struct apply_state'Christian Couder, May 24, 2016
  26. 25/49 builtin/apply: move 'line_termination' global into 'struct apply_state'Christian Couder, May 24, 2016
  27. 26/49 builtin/apply: move 'fake_ancestor' global into 'struct apply_state'Christian Couder, May 24, 2016
  28. 27/49 builtin/apply: move 'p_context' global into 'struct apply_state'Christian Couder, May 24, 2016
  29. 28/49 builtin/apply: move 'apply' global into 'struct apply_state'Christian Couder, May 24, 2016
  30. 29/49 builtin/apply: move 'patch_input_file' global into 'struct apply_state'Christian Couder, May 24, 2016
  31. 30/49 builtin/apply: move 'limit_by_name' global into 'struct apply_state'Christian Couder, May 24, 2016
  32. 31/49 builtin/apply: move 'has_include' global into 'struct apply_state'Christian Couder, May 24, 2016
  33. 32/49 builtin/apply: move 'p_value' global into 'struct apply_state'Christian Couder, May 24, 2016
  34. 33/49 builtin/apply: move 'p_value_known' global into 'struct apply_state'Christian Couder, May 24, 2016
  35. 34/49 builtin/apply: move 'root' global into 'struct apply_state'Christian Couder, May 24, 2016
  36. 35/49 builtin/apply: move 'whitespace_error' global into 'struct apply_state'Christian Couder, May 24, 2016
  37. 36/49 builtin/apply: move 'whitespace_option' into 'struct apply_state'Christian Couder, May 24, 2016
  38. 37/49 builtin/apply: remove whitespace_option arg from set_default_whitespace_mode()Christian Couder, May 24, 2016
  39. 38/49 builtin/apply: move 'squelch_whitespace_errors' into 'struct apply_state'Christian Couder, May 24, 2016
  40. 39/49 builtin/apply: move 'applied_after_fixing_ws' into 'struct apply_state'Christian Couder, May 24, 2016
  41. 40/49 builtin/apply: move 'ws_error_action' into 'struct apply_state'Christian Couder, May 24, 2016
  42. 41/49 builtin/apply: move 'ws_ignore_action' into 'struct apply_state'Christian Couder, May 24, 2016
  43. 42/49 builtin/apply: move 'max_change' and 'max_len' into 'struct apply_state'Christian Couder, May 24, 2016
  44. 43/49 builtin/apply: move 'state_linenr' global into 'struct apply_state'Christian Couder, May 24, 2016
  45. 44/49 builtin/apply: move 'fn_table' global into 'struct apply_state'Christian Couder, May 24, 2016
  46. 45/49 builtin/apply: move 'symlink_changes' global into 'struct apply_state'Christian Couder, May 24, 2016
  47. 46/49 builtin/apply: move 'state' check into check_apply_state()Christian Couder, May 24, 2016
  48. 47/49 builtin/apply: move applying patches into apply_all_patches()Christian Couder, May 24, 2016
  49. 48/49 builtin/apply: move 'lock_file' global into 'struct apply_state'Christian Couder, May 24, 2016
  50. Junio C HamanoJun 1, 2016
  51. Christian CouderJun 3, 2016
  52. 49/49 builtin/apply: move 'newfd' global into 'struct apply_state'Christian Couder, May 24, 2016
  53. Christian CouderMay 24, 2016

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.