From 8ebc48041ab1c6e2b5a5532304ab6acdb3a2b63d Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 17:33:57 -0800
Subject: Avoid VLA for lower_{needle,haystack}

---
 src/match.c | 24 +++++++++++++-----------
 1 file changed, 13 insertions(+), 11 deletions(-)

diff --git a/src/match.c b/src/match.c
index 2a0b058..1081be3 100644
--- a/src/match.c
+++ b/src/match.c
@@ -56,6 +56,8 @@ void mat_print(score_t *mat, char name, const char *needle, const char *haystack
 }
 #endif
 
+#define MATCH_MAX_LEN 1024
+
 static void precompute_bonus(const char *haystack, score_t *match_bonus) {
 	/* Which positions are beginning of words */
 	int m = strlen(haystack);
@@ -74,6 +76,15 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	int n = strlen(needle);
 	int m = strlen(haystack);
 
+	if (m > MATCH_MAX_LEN || n > MATCH_MAX_LEN) {
+		/*
+		 * Unreasonably large candidate: return no score
+		 * If it is a valid match it will still be returned, it will
+		 * just be ranked below any reasonably sized candidates
+		 */
+		return SCORE_MIN;
+	}
+
 	if (n == m) {
 		/* Since this method can only be called with a haystack which
 		 * matches needle. If the lengths of the strings are equal the
@@ -85,17 +96,8 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		return SCORE_MAX;
 	}
 
-	if (m > 1024) {
-		/*
-		 * Unreasonably large candidate: return no score
-		 * If it is a valid match it will still be returned, it will
-		 * just be ranked below any reasonably sized candidates
-		 */
-		return SCORE_MIN;
-	}
-
-	char lower_needle[n];
-	char lower_haystack[m];
+	char lower_needle[MATCH_MAX_LEN];
+	char lower_haystack[MATCH_MAX_LEN];
 
 	for (int i = 0; i < n; i++)
 		lower_needle[i] = tolower(needle[i]);
-- 
cgit v1.2.3


From eb4cbd4e2f7480e100d0c16280035989f88d7911 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 17:38:22 -0800
Subject: Avoid VLA for match_bonus

---
 src/match.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/match.c b/src/match.c
index 1081be3..d784a0b 100644
--- a/src/match.c
+++ b/src/match.c
@@ -105,7 +105,7 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	for (int i = 0; i < m; i++)
 		lower_haystack[i] = tolower(haystack[i]);
 
-	score_t match_bonus[m];
+	score_t match_bonus[MATCH_MAX_LEN];
 	score_t D[n][m], M[n][m];
 
 	/*
-- 
cgit v1.2.3


From 8402394d36ef7b1a1617bb683a897bb74d016d7c Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 17:47:32 -0800
Subject: Work with row pointers

---
 src/match.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)

diff --git a/src/match.c b/src/match.c
index d784a0b..8a71df9 100644
--- a/src/match.c
+++ b/src/match.c
@@ -108,6 +108,9 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	score_t match_bonus[MATCH_MAX_LEN];
 	score_t D[n][m], M[n][m];
 
+	score_t *last_D, *last_M;
+	score_t *curr_D, *curr_M;
+
 	/*
 	 * D[][] Stores the best score for this position ending with a match.
 	 * M[][] Stores the best possible score at this position.
@@ -118,6 +121,9 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		score_t prev_score = SCORE_MIN;
 		score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;
 
+		curr_D = &D[i][0];
+		curr_M = &M[i][0];
+
 		for (int j = 0; j < m; j++) {
 			if (lower_needle[i] == lower_haystack[j]) {
 				score_t score = SCORE_MIN;
@@ -125,18 +131,21 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 					score = (j * SCORE_GAP_LEADING) + match_bonus[j];
 				} else if (j) { /* i > 0 && j > 0*/
 					score = max(
-					    M[i - 1][j - 1] + match_bonus[j],
+					    last_M[j - 1] + match_bonus[j],
 
 					    /* consecutive match, doesn't stack with match_bonus */
-					    D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE);
+					    last_D[j - 1] + SCORE_MATCH_CONSECUTIVE);
 				}
-				D[i][j] = score;
-				M[i][j] = prev_score = max(score, prev_score + gap_score);
+				curr_D[j] = score;
+				curr_M[j] = prev_score = max(score, prev_score + gap_score);
 			} else {
-				D[i][j] = SCORE_MIN;
-				M[i][j] = prev_score = prev_score + gap_score;
+				curr_D[j] = SCORE_MIN;
+				curr_M[j] = prev_score = prev_score + gap_score;
 			}
 		}
+
+		last_D = curr_D;
+		last_M = curr_M;
 	}
 
 #ifdef DEBUG_VERBOSE
-- 
cgit v1.2.3


From 2afbce950e820f6d1f479f5809149390a59db76a Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 17:49:38 -0800
Subject: Combine early-return if as else if

---
 src/match.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/src/match.c b/src/match.c
index 8a71df9..c028b87 100644
--- a/src/match.c
+++ b/src/match.c
@@ -83,9 +83,7 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		 * just be ranked below any reasonably sized candidates
 		 */
 		return SCORE_MIN;
-	}
-
-	if (n == m) {
+	} else if (n == m) {
 		/* Since this method can only be called with a haystack which
 		 * matches needle. If the lengths of the strings are equal the
 		 * strings themselves must also be equal (ignoring case).
-- 
cgit v1.2.3


From 77d3a20d7fba0f5642b2e73222a4cca34de5e8ef Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 17:54:34 -0800
Subject: Break early if strlen(neddle) > strlen(haystack)

This should never happen if this is called properly (match only returns
valid results if there IS a match), but it's nice to double check here.
---
 src/match.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/match.c b/src/match.c
index c028b87..38b26e1 100644
--- a/src/match.c
+++ b/src/match.c
@@ -76,7 +76,7 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	int n = strlen(needle);
 	int m = strlen(haystack);
 
-	if (m > MATCH_MAX_LEN || n > MATCH_MAX_LEN) {
+	if (m > MATCH_MAX_LEN || n > m) {
 		/*
 		 * Unreasonably large candidate: return no score
 		 * If it is a valid match it will still be returned, it will
-- 
cgit v1.2.3


From e975f0b919a4b7037b6669cc009588804090c194 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:08:40 -0800
Subject: Move some temporary storage into match_struct

---
 src/match.c | 56 +++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 39 insertions(+), 17 deletions(-)

diff --git a/src/match.c b/src/match.c
index 38b26e1..282d020 100644
--- a/src/match.c
+++ b/src/match.c
@@ -58,6 +58,16 @@ void mat_print(score_t *mat, char name, const char *needle, const char *haystack
 
 #define MATCH_MAX_LEN 1024
 
+struct match_struct {
+	int needle_len;
+	int haystack_len;
+
+	char lower_needle[MATCH_MAX_LEN];
+	char lower_haystack[MATCH_MAX_LEN];
+
+	score_t match_bonus[MATCH_MAX_LEN];
+};
+
 static void precompute_bonus(const char *haystack, score_t *match_bonus) {
 	/* Which positions are beginning of words */
 	int m = strlen(haystack);
@@ -69,12 +79,32 @@ static void precompute_bonus(const char *haystack, score_t *match_bonus) {
 	}
 }
 
+static void setup_match_struct(struct match_struct *match, const char *needle, const char *haystack) {
+	match->needle_len = strlen(needle);
+	match->haystack_len = strlen(haystack);
+
+	if (match->needle_len > MATCH_MAX_LEN || match->needle_len > match->haystack_len) {
+		return;
+	}
+
+	for (int i = 0; i < match->needle_len; i++)
+		match->lower_needle[i] = tolower(needle[i]);
+
+	for (int i = 0; i < match->haystack_len; i++)
+		match->lower_haystack[i] = tolower(haystack[i]);
+
+	precompute_bonus(haystack, match->match_bonus);
+}
+
 score_t match_positions(const char *needle, const char *haystack, size_t *positions) {
 	if (!*needle)
 		return SCORE_MIN;
 
-	int n = strlen(needle);
-	int m = strlen(haystack);
+	struct match_struct match;
+	setup_match_struct(&match, needle, haystack);
+
+	int n = match.needle_len;
+	int m = match.haystack_len;
 
 	if (m > MATCH_MAX_LEN || n > m) {
 		/*
@@ -94,26 +124,18 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		return SCORE_MAX;
 	}
 
-	char lower_needle[MATCH_MAX_LEN];
-	char lower_haystack[MATCH_MAX_LEN];
-
-	for (int i = 0; i < n; i++)
-		lower_needle[i] = tolower(needle[i]);
-
-	for (int i = 0; i < m; i++)
-		lower_haystack[i] = tolower(haystack[i]);
-
-	score_t match_bonus[MATCH_MAX_LEN];
-	score_t D[n][m], M[n][m];
-
-	score_t *last_D, *last_M;
-	score_t *curr_D, *curr_M;
+	const char *lower_needle = match.lower_needle;
+	const char *lower_haystack = match.lower_haystack;
+	const score_t *match_bonus = match.match_bonus;
 
 	/*
 	 * D[][] Stores the best score for this position ending with a match.
 	 * M[][] Stores the best possible score at this position.
 	 */
-	precompute_bonus(haystack, match_bonus);
+	score_t D[n][m], M[n][m];
+
+	score_t *last_D, *last_M;
+	score_t *curr_D, *curr_M;
 
 	for (int i = 0; i < n; i++) {
 		score_t prev_score = SCORE_MIN;
-- 
cgit v1.2.3


From ab1fd85a1b9995ca00077e6cdc1fc9e9647e0a10 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:16:48 -0800
Subject: Extract row matching into own method

---
 src/match.c | 60 ++++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 34 insertions(+), 26 deletions(-)

diff --git a/src/match.c b/src/match.c
index 282d020..8f4a475 100644
--- a/src/match.c
+++ b/src/match.c
@@ -96,6 +96,39 @@ static void setup_match_struct(struct match_struct *match, const char *needle, c
 	precompute_bonus(haystack, match->match_bonus);
 }
 
+static inline void match_row(const struct match_struct *match, int row, score_t *curr_D, score_t *curr_M, const score_t *last_D, const score_t *last_M) {
+	int n = match->needle_len;
+	int m = match->haystack_len;
+	int i = row;
+
+	const char *lower_needle = match->lower_needle;
+	const char *lower_haystack = match->lower_haystack;
+	const score_t *match_bonus = match->match_bonus;
+
+	score_t prev_score = SCORE_MIN;
+	score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;
+
+	for (int j = 0; j < m; j++) {
+		if (lower_needle[i] == lower_haystack[j]) {
+			score_t score = SCORE_MIN;
+			if (!i) {
+				score = (j * SCORE_GAP_LEADING) + match_bonus[j];
+			} else if (j) { /* i > 0 && j > 0*/
+				score = max(
+						last_M[j - 1] + match_bonus[j],
+
+						/* consecutive match, doesn't stack with match_bonus */
+						last_D[j - 1] + SCORE_MATCH_CONSECUTIVE);
+			}
+			curr_D[j] = score;
+			curr_M[j] = prev_score = max(score, prev_score + gap_score);
+		} else {
+			curr_D[j] = SCORE_MIN;
+			curr_M[j] = prev_score = prev_score + gap_score;
+		}
+	}
+}
+
 score_t match_positions(const char *needle, const char *haystack, size_t *positions) {
 	if (!*needle)
 		return SCORE_MIN;
@@ -124,10 +157,6 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		return SCORE_MAX;
 	}
 
-	const char *lower_needle = match.lower_needle;
-	const char *lower_haystack = match.lower_haystack;
-	const score_t *match_bonus = match.match_bonus;
-
 	/*
 	 * D[][] Stores the best score for this position ending with a match.
 	 * M[][] Stores the best possible score at this position.
@@ -138,31 +167,10 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	score_t *curr_D, *curr_M;
 
 	for (int i = 0; i < n; i++) {
-		score_t prev_score = SCORE_MIN;
-		score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;
-
 		curr_D = &D[i][0];
 		curr_M = &M[i][0];
 
-		for (int j = 0; j < m; j++) {
-			if (lower_needle[i] == lower_haystack[j]) {
-				score_t score = SCORE_MIN;
-				if (!i) {
-					score = (j * SCORE_GAP_LEADING) + match_bonus[j];
-				} else if (j) { /* i > 0 && j > 0*/
-					score = max(
-					    last_M[j - 1] + match_bonus[j],
-
-					    /* consecutive match, doesn't stack with match_bonus */
-					    last_D[j - 1] + SCORE_MATCH_CONSECUTIVE);
-				}
-				curr_D[j] = score;
-				curr_M[j] = prev_score = max(score, prev_score + gap_score);
-			} else {
-				curr_D[j] = SCORE_MIN;
-				curr_M[j] = prev_score = prev_score + gap_score;
-			}
-		}
+		match_row(&match, i, curr_D, curr_M, last_D, last_M);
 
 		last_D = curr_D;
 		last_M = curr_M;
-- 
cgit v1.2.3


From d2e0be2197e7b4e5db23ab7fd2d46c966640a3d0 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:35:49 -0800
Subject: Split match and match_postitions

---
 src/match.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 48 insertions(+), 4 deletions(-)

diff --git a/src/match.c b/src/match.c
index 8f4a475..8dd98c3 100644
--- a/src/match.c
+++ b/src/match.c
@@ -4,6 +4,7 @@
 #include <stdio.h>
 #include <float.h>
 #include <math.h>
+#include <stdlib.h>
 
 #include "match.h"
 #include "bonus.h"
@@ -129,6 +130,53 @@ static inline void match_row(const struct match_struct *match, int row, score_t
 	}
 }
 
+score_t match(const char *needle, const char *haystack) {
+	if (!*needle)
+		return SCORE_MIN;
+
+	struct match_struct match;
+	setup_match_struct(&match, needle, haystack);
+
+	int n = match.needle_len;
+	int m = match.haystack_len;
+
+	if (m > MATCH_MAX_LEN || n > m) {
+		/*
+		 * Unreasonably large candidate: return no score
+		 * If it is a valid match it will still be returned, it will
+		 * just be ranked below any reasonably sized candidates
+		 */
+		return SCORE_MIN;
+	} else if (n == m) {
+		/* Since this method can only be called with a haystack which
+		 * matches needle. If the lengths of the strings are equal the
+		 * strings themselves must also be equal (ignoring case).
+		 */
+		return SCORE_MAX;
+	}
+
+	/*
+	 * D[][] Stores the best score for this position ending with a match.
+	 * M[][] Stores the best possible score at this position.
+	 */
+	score_t D[n][m], M[n][m];
+
+	score_t *last_D, *last_M;
+	score_t *curr_D, *curr_M;
+
+	for (int i = 0; i < n; i++) {
+		curr_D = &D[i][0];
+		curr_M = &M[i][0];
+
+		match_row(&match, i, curr_D, curr_M, last_D, last_M);
+
+		last_D = curr_D;
+		last_M = curr_M;
+	}
+
+	return M[n - 1][m - 1];
+}
+
 score_t match_positions(const char *needle, const char *haystack, size_t *positions) {
 	if (!*needle)
 		return SCORE_MIN;
@@ -214,7 +262,3 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 
 	return M[n - 1][m - 1];
 }
-
-score_t match(const char *needle, const char *haystack) {
-	return match_positions(needle, haystack, NULL);
-}
-- 
cgit v1.2.3


From 2d4251b17d81f774e1c00dff3bdbae73d2251295 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:39:01 -0800
Subject: Reduce memory and avoid VLA in match()

When we're matching without recording positions, we only need to keep
two rows in memory at a time.
---
 src/match.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)

diff --git a/src/match.c b/src/match.c
index 8dd98c3..6cf9c3a 100644
--- a/src/match.c
+++ b/src/match.c
@@ -28,6 +28,8 @@ int has_match(const char *needle, const char *haystack) {
 	return 1;
 }
 
+#define SWAP(x, y, T) do { T SWAP = x; x = y; y = SWAP; } while (0)
+
 #define max(a, b) (((a) > (b)) ? (a) : (b))
 
 #ifdef DEBUG_VERBOSE
@@ -159,22 +161,24 @@ score_t match(const char *needle, const char *haystack) {
 	 * D[][] Stores the best score for this position ending with a match.
 	 * M[][] Stores the best possible score at this position.
 	 */
-	score_t D[n][m], M[n][m];
+	score_t D[2][MATCH_MAX_LEN], M[2][MATCH_MAX_LEN];
 
 	score_t *last_D, *last_M;
 	score_t *curr_D, *curr_M;
 
-	for (int i = 0; i < n; i++) {
-		curr_D = &D[i][0];
-		curr_M = &M[i][0];
+	last_D = D[0];
+	last_M = M[0];
+	curr_D = D[1];
+	curr_M = M[1];
 
+	for (int i = 0; i < n; i++) {
 		match_row(&match, i, curr_D, curr_M, last_D, last_M);
 
-		last_D = curr_D;
-		last_M = curr_M;
+		SWAP(curr_D, last_D, score_t *);
+		SWAP(curr_M, last_M, score_t *);
 	}
 
-	return M[n - 1][m - 1];
+	return last_M[m - 1];
 }
 
 score_t match_positions(const char *needle, const char *haystack, size_t *positions) {
-- 
cgit v1.2.3


From b76efa71c6b33439e098d66e1e08be665622d7a3 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:42:25 -0800
Subject: Remove DEBUG_VERBOSE

---
 src/match.c | 34 ----------------------------------
 1 file changed, 34 deletions(-)

diff --git a/src/match.c b/src/match.c
index 6cf9c3a..e0cae96 100644
--- a/src/match.c
+++ b/src/match.c
@@ -32,33 +32,6 @@ int has_match(const char *needle, const char *haystack) {
 
 #define max(a, b) (((a) > (b)) ? (a) : (b))
 
-#ifdef DEBUG_VERBOSE
-/* print one of the internal matrices */
-void mat_print(score_t *mat, char name, const char *needle, const char *haystack) {
-	int n = strlen(needle);
-	int m = strlen(haystack);
-	int i, j;
-	fprintf(stderr, "%c   ", name);
-	for (j = 0; j < m; j++) {
-		fprintf(stderr, "     %c", haystack[j]);
-	}
-	fprintf(stderr, "\n");
-	for (i = 0; i < n; i++) {
-		fprintf(stderr, " %c |", needle[i]);
-		for (j = 0; j < m; j++) {
-			score_t val = mat[i * m + j];
-			if (val == SCORE_MIN) {
-				fprintf(stderr, "    -\u221E");
-			} else {
-				fprintf(stderr, " %.3f", val);
-			}
-		}
-		fprintf(stderr, "\n");
-	}
-	fprintf(stderr, "\n\n");
-}
-#endif
-
 #define MATCH_MAX_LEN 1024
 
 struct match_struct {
@@ -228,13 +201,6 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		last_M = curr_M;
 	}
 
-#ifdef DEBUG_VERBOSE
-	fprintf(stderr, "\"%s\" =~ \"%s\"\n", needle, haystack);
-	mat_print(&D[0][0], 'D', needle, haystack);
-	mat_print(&M[0][0], 'M', needle, haystack);
-	fprintf(stderr, "\n");
-#endif
-
 	/* backtrace to find the positions of optimal matching */
 	if (positions) {
 		int match_required = 0;
-- 
cgit v1.2.3


From 9dfb287b86b431d57dd67464aaa1a5863d63e078 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:43:46 -0800
Subject: Use malloc in match_positions to avoid VLA

---
 src/match.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/src/match.c b/src/match.c
index e0cae96..b5c134b 100644
--- a/src/match.c
+++ b/src/match.c
@@ -186,7 +186,9 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 	 * D[][] Stores the best score for this position ending with a match.
 	 * M[][] Stores the best possible score at this position.
 	 */
-	score_t D[n][m], M[n][m];
+	score_t (*D)[MATCH_MAX_LEN], (*M)[MATCH_MAX_LEN];
+	M = malloc(sizeof(score_t) * MATCH_MAX_LEN * n);
+	D = malloc(sizeof(score_t) * MATCH_MAX_LEN * n);
 
 	score_t *last_D, *last_M;
 	score_t *curr_D, *curr_M;
@@ -230,5 +232,10 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi
 		}
 	}
 
-	return M[n - 1][m - 1];
+	score_t result = M[n - 1][m - 1];
+
+	free(M);
+	free(D);
+
+	return result;
 }
-- 
cgit v1.2.3


From e1a48d0808cfc0c817ec78ab6b9e891676a2e62b Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 19:09:11 -0800
Subject: Remove strlen in precompute_bonus

Pretty sure this was optimized out anyways, but this is cleaner IMO.
---
 src/match.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/src/match.c b/src/match.c
index b5c134b..4aaf1b4 100644
--- a/src/match.c
+++ b/src/match.c
@@ -46,9 +46,8 @@ struct match_struct {
 
 static void precompute_bonus(const char *haystack, score_t *match_bonus) {
 	/* Which positions are beginning of words */
-	int m = strlen(haystack);
 	char last_ch = '/';
-	for (int i = 0; i < m; i++) {
+	for (int i = 0; haystack[i]; i++) {
 		char ch = haystack[i];
 		match_bonus[i] = COMPUTE_BONUS(last_ch, ch);
 		last_ch = ch;
-- 
cgit v1.2.3


From f7a62107b72152cd19dab1c13c027e4190a1997c Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 19:39:50 -0800
Subject: Avoid VLA in tty_interface

---
 src/match.c         | 2 --
 src/match.h         | 2 ++
 src/tty_interface.c | 4 ++--
 3 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/match.c b/src/match.c
index 4aaf1b4..a0c0785 100644
--- a/src/match.c
+++ b/src/match.c
@@ -32,8 +32,6 @@ int has_match(const char *needle, const char *haystack) {
 
 #define max(a, b) (((a) > (b)) ? (a) : (b))
 
-#define MATCH_MAX_LEN 1024
-
 struct match_struct {
 	int needle_len;
 	int haystack_len;
diff --git a/src/match.h b/src/match.h
index 0fa7b6f..d4f292c 100644
--- a/src/match.h
+++ b/src/match.h
@@ -7,6 +7,8 @@ typedef double score_t;
 #define SCORE_MAX INFINITY
 #define SCORE_MIN -INFINITY
 
+#define MATCH_MAX_LEN 1024
+
 int has_match(const char *needle, const char *haystack);
 score_t match_positions(const char *needle, const char *haystack, size_t *positions);
 score_t match(const char *needle, const char *haystack);
diff --git a/src/tty_interface.c b/src/tty_interface.c
index 225f33a..e87301d 100644
--- a/src/tty_interface.c
+++ b/src/tty_interface.c
@@ -36,8 +36,8 @@ static void draw_match(tty_interface_t *state, const char *choice, int selected)
 	char *search = state->last_search;
 
 	int n = strlen(search);
-	size_t positions[n + 1];
-	for (int i = 0; i < n + 1; i++)
+	size_t positions[MATCH_MAX_LEN];
+	for (int i = 0; i < n + 1 && i < MATCH_MAX_LEN; i++)
 		positions[i] = -1;
 
 	score_t score = match_positions(search, choice, &positions[0]);
-- 
cgit v1.2.3


From 66316266df901eab81ae116c6e0728d10d0214e4 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john@hawthorn.email>
Date: Fri, 27 Dec 2019 18:44:01 -0800
Subject: Error on usage of VLA

---
 Makefile            | 2 +-
 test/test_choices.c | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/Makefile b/Makefile
index c1f6234..746994f 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 VERSION=1.0
 
 CPPFLAGS=-DVERSION=\"${VERSION}\" -D_GNU_SOURCE
-CFLAGS+=-Wall -Wextra -g -std=c99 -O3 -pedantic -Ideps
+CFLAGS+=-Wall -Wextra -g -std=c99 -O3 -pedantic -Ideps -Werror=vla
 PREFIX?=/usr/local
 MANDIR?=$(PREFIX)/share/man
 BINDIR?=$(PREFIX)/bin
diff --git a/test/test_choices.c b/test/test_choices.c
index 3ad7d6a..d86bc12 100644
--- a/test/test_choices.c
+++ b/test/test_choices.c
@@ -135,8 +135,8 @@ TEST test_choices_unicode() {
 }
 
 TEST test_choices_large_input() {
-	int N = 100000;
-	char *strings[N];
+	const int N = 100000;
+	char *strings[100000];
 
 	for(int i = 0; i < N; i++) {
 		asprintf(&strings[i], "%i", i);
-- 
cgit v1.2.3