[Users] [PATCH 2/3] Do not allow search cost to explode in case of bad message parsing in textview_make_clickable_parts_later();

[Igor Mammedov]

Searching all patterns inside for(walk) loop in worst case could lead to an expontential like
search cost if 'walk' is incremented by a character on each iteration. Rewriting pattern loop
from inner to outer loop will fix issue and yeld only O(n) complexity.

it reduces cost of textview_make_clickable_parts_later() from 99% to 17% for big bad-case message

Signed-off-by: Igor Mammedov <imammedo at redhat.com>
---
 src/textview.c | 78 ++++++++++++++++++++--------------------------------------
 1 file changed, 26 insertions(+), 52 deletions(-)

diff --git a/src/textview.c b/src/textview.c
index 8c4b6e7..c1f06e0 100644
--- a/src/textview.c
+++ b/src/textview.c
@@ -1361,34 +1361,21 @@ static void textview_make_clickable_parts(TextView *textview,
 	gtk_text_buffer_get_end_iter(buffer, &iter);
 
 	/* parse for clickable parts, and build a list of begin and end positions  */
-	for (walk = mybuf;;) {
-		gint last_index = PARSE_ELEMS;
-		gchar *scanpos = NULL;
-
-		/* FIXME: this looks phony. scanning for anything in the parse table */
-		for (n = 0; n < PARSE_ELEMS; n++) {
-			gchar *tmp;
-
-			tmp = parser[n].search(walk, parser[n].needle);
-			if (tmp) {
-				if (scanpos == NULL || tmp < scanpos) {
-					scanpos = tmp;
-					last_index = n;
-				}
-			}					
-		}
-
-		if (scanpos) {
-			/* check if URI can be parsed */
-			if (parser[last_index].parse(walk, scanpos, &bp, &ep, hdr)
-			    && (size_t) (ep - bp - 1) > strlen(parser[last_index].needle)) {
-					ADD_TXT_POS(bp, ep, last_index);
+	for (n = 0; n < PARSE_ELEMS; n++) {
+		for (walk = mybuf;;) {
+			gchar *scanpos = parser[n].search(walk, parser[n].needle);
+			if (scanpos) {
+				/* check if URI can be parsed */
+				if (parser[n].parse(walk, scanpos, &bp, &ep, hdr)
+						&& (size_t) (ep - bp - 1) > strlen(parser[n].needle)) {
+					ADD_TXT_POS(bp, ep, n);
 					walk = ep;
+				} else
+					walk = scanpos +
+						strlen(parser[n].needle);
 			} else
-				walk = scanpos +
-					strlen(parser[last_index].needle);
-		} else
-			break;
+				break;
+		}
 	}
 
 	/* colorize this line */
@@ -1481,34 +1468,21 @@ static void textview_make_clickable_parts_later(TextView *textview,
 	offset = gtk_text_iter_get_offset(&start_iter);
 
 	/* parse for clickable parts, and build a list of begin and end positions  */
-	for (walk = mybuf;;) {
-		gint last_index = PARSE_ELEMS;
-		gchar *scanpos = NULL;
-
-		/* FIXME: this looks phony. scanning for anything in the parse table */
-		for (n = 0; n < PARSE_ELEMS; n++) {
-			gchar *tmp;
-
-			tmp = parser[n].search(walk, parser[n].needle);
-			if (tmp) {
-				if (scanpos == NULL || tmp < scanpos) {
-					scanpos = tmp;
-					last_index = n;
-				}
-			}					
-		}
-
-		if (scanpos) {
-			/* check if URI can be parsed */
-			if (parser[last_index].parse(walk, scanpos, &bp, &ep, FALSE)
-			    && (size_t) (ep - bp - 1) > strlen(parser[last_index].needle)) {
-					ADD_TXT_POS_LATER(bp, ep, last_index);
+	for (n = 0; n < PARSE_ELEMS; n++) {
+		for (walk = mybuf;;) {
+			gchar *scanpos = parser[n].search(walk, parser[n].needle);
+			if (scanpos) {
+				/* check if URI can be parsed */
+				if (parser[n].parse(walk, scanpos, &bp, &ep, FALSE)
+						&& (size_t) (ep - bp - 1) > strlen(parser[n].needle)) {
+					ADD_TXT_POS_LATER(bp, ep, n);
 					walk = ep;
+				} else
+					walk = scanpos +
+						strlen(parser[n].needle);
 			} else
-				walk = scanpos +
-					strlen(parser[last_index].needle);
-		} else
-			break;
+				break;
+		}
 	}
 
 	/* colorize this line */
-- 
1.7.11.7