Mon Jun 15 14:46:28 2020 UTC ()

make(1): fix performance problem in specially crafted :M modifier

This fix was previously suspected to make the vax build fail.  The next
build succeeded though, and it started 2 hours before this fix was
reverted.


(rillig)

diff -r1.47 -r1.48 src/usr.bin/make/str.c
diff -r1.5 -r1.6 src/usr.bin/make/unit-tests/modmatch.mk

--- src/usr.bin/make/str.c 2020/06/14 23:13:21	1.47
+++ src/usr.bin/make/str.c 2020/06/15 14:46:28	1.48

 @@ -1,14 +1,14 @@
-/*	$NetBSD: str.c,v 1.47 2020/06/14 23:13:21 rillig Exp $	*/
+/*	$NetBSD: str.c,v 1.48 2020/06/15 14:46:28 rillig Exp $	*/
 /*-
  * Copyright (c) 1988, 1989, 1990, 1993
  *	The Regents of the University of California.  All rights reserved.
+ *
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
 @@ -59,34 +59,34 @@
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
 #ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: str.c,v 1.47 2020/06/14 23:13:21 rillig Exp $";
+static char rcsid[] = "$NetBSD: str.c,v 1.48 2020/06/15 14:46:28 rillig Exp $";
 #else
 #include <sys/cdefs.h>
 #ifndef lint
 #if 0
 static char     sccsid[] = "@(#)str.c	5.8 (Berkeley) 6/1/90";
 #else
-__RCSID("$NetBSD: str.c,v 1.47 2020/06/14 23:13:21 rillig Exp $");
+__RCSID("$NetBSD: str.c,v 1.48 2020/06/15 14:46:28 rillig Exp $");
 #endif
 #endif				/* not lint */
 #endif
 #include "make.h"
 /*-
  * str_concat --
  *	concatenate the two strings, inserting a space or slash between them,
  *	freeing them if requested.
+ *
  * returns --
  *	the resulting string in allocated space.
 @@ -345,26 +345,28 @@ Str_Match(const char *string, const char
 		 */
 		if (*pattern == 0)
 			return !*string;
 		if (*string == 0 && *pattern != '*')
 			return 0;
 		/*
 		 * Check for a "*" as the next pattern character.  It matches
 		 * any substring.  We handle this by calling ourselves
 		 * recursively for each postfix of string, until either we
 		 * match or we reach the end of the string.
 		 */
 		if (*pattern == '*') {
 			pattern++;
 			while (*pattern == '*')
 				pattern++;
 			if (*pattern == 0)
 				return 1;
 			while (*string != 0) {
 				if (Str_Match(string, pattern))
 					return 1;
 				++string;
+			}
 			return 0;
+		}
 		/*
 		 * Check for a "?" as the next pattern character.  It matches
 		 * any single character.
 		 */

--- src/usr.bin/make/unit-tests/Attic/modmatch.mk 2020/06/14 23:13:21	1.5
+++ src/usr.bin/make/unit-tests/Attic/modmatch.mk 2020/06/15 14:46:28	1.6

 @@ -26,14 +26,14 @@ show:
 	@echo 'LIB=${LIB} X_LIBS:M*/lib$${LIB}.a is "${X_LIBS:M*/lib${LIB}.a}"'
 	@echo 'LIB=${LIB} X_LIBS:M*/lib$${LIB}.a:tu is "${X_LIBS:M*/lib${LIB}.a:tu}"'
 LIST= One Two Three Four five six seven
 check-cclass:
 	@echo Upper=${LIST:M[A-Z]*}
 	@echo Lower=${LIST:M[^A-Z]*}
 	@echo nose=${LIST:M[^s]*[ex]}
 # Before 2020-06-13, this expression took quite a long time in Str_Match,
 # calling itself 601080390 times for 16 asterisks.
 slow: .PHONY
-#	@:;: ${:U****************:M****************b:Q}
+	@:;: ${:U****************:M****************b:Q}