[PATCH] regex: support non-greedy quantifiers

[PATCH] regex: support non-greedy quantifiers

[Julien Ramseier]

Here's a tiny patch to enable non-greedy regex quantifiers.
This is not specified by POSIX, but I think it's a useful
extension, and all the code for supporting it is already present.

I tested this against the TRE and AT&T test suites (from NetBSD)
and didn't found any regressions.
However I don't know all the ins and outs of the implementation
and I may have missed something obvious.

- Julien

diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
index 5fad98b..cc7d633 100644
--- a/src/regex/regcomp.c
+++ b/src/regex/regcomp.c
@@ -979,6 +979,7 @@ static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
 	parse_iter:
 		for (;;) {
 			int min, max;
+			int minimal = 0;
 
 			if (*s!='\\' && *s!='*') {
 				if (!ere)
@@ -1014,11 +1015,16 @@ static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
 				if (*s == '?')
 					max = 1;
 				s++;
+				/* Non-greedy */
+				if (ere && *s == '?') {
+					minimal = 1;
+					s++;
+				}
 			}
 			if (max == 0)
 				ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
 			else
-				ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
+				ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, minimal);
 			if (!ctx->n)
 				return REG_ESPACE;
 		}
-- 
2.7.2

Re: [PATCH] regex: support non-greedy quantifiers

[Julien Ramseier]

> Le 13 mars 2016 à 12:06, Julien Ramseier <j.ramseier@gmail.com> a écrit :
> 
> Here's a tiny patch to enable non-greedy regex quantifiers.
> This is not specified by POSIX, but I think it's a useful
> extension, and all the code for supporting it is already present.
> 
> I tested this against the TRE and AT&T test suites (from NetBSD)
> and didn't found any regressions.
> However I don't know all the ins and outs of the implementation
> and I may have missed something obvious.
> 
> - Julien
> 
> diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
> index 5fad98b..cc7d633 100644
> --- a/src/regex/regcomp.c
> +++ b/src/regex/regcomp.c
> @@ -979,6 +979,7 @@ static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
> 	parse_iter:
> 		for (;;) {
> 			int min, max;
> +			int minimal = 0;
> 
> 			if (*s!='\\' && *s!='*') {
> 				if (!ere)
> @@ -1014,11 +1015,16 @@ static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
> 				if (*s == '?')
> 					max = 1;
> 				s++;
> +				/* Non-greedy */
> +				if (ere && *s == '?') {
> +					minimal = 1;
> +					s++;
> +				}
> 			}
> 			if (max == 0)
> 				ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
> 			else
> -				ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
> +				ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, minimal);
> 			if (!ctx->n)
> 				return REG_ESPACE;
> 		}
> -- 
> 2.7.2

Ping?

Re: Re: [PATCH] regex: support non-greedy quantifiers

[Szabolcs Nagy]

* Julien Ramseier <j.ramseier@gmail.com> [2016-06-16 17:33:48 +0200]:
> > Le 13 mars 2016 à 12:06, Julien Ramseier <j.ramseier@gmail.com> a écrit :
> > 
> > Here's a tiny patch to enable non-greedy regex quantifiers.
> > This is not specified by POSIX, but I think it's a useful
> > extension, and all the code for supporting it is already present.
...
> 
> Ping?

musl is conservative about its regex syntax since extensions
are not portable across impementations so users cannot rely
on them.

i think this extension is not available in glibc and other
posix regex implementations either, it's a perl invention,
so it would be wrong to add it to musl, those who want perl
syntax can use the pcre lib.

Re: Re: [PATCH] regex: support non-greedy quantifiers

[Rich Felker]

On Thu, Jun 16, 2016 at 09:10:50PM +0200, Szabolcs Nagy wrote:
> * Julien Ramseier <j.ramseier@gmail.com> [2016-06-16 17:33:48 +0200]:
> > > Le 13 mars 2016 à 12:06, Julien Ramseier <j.ramseier@gmail.com> a écrit :
> > > 
> > > Here's a tiny patch to enable non-greedy regex quantifiers.
> > > This is not specified by POSIX, but I think it's a useful
> > > extension, and all the code for supporting it is already present.
> ...
> > 
> > Ping?
> 
> musl is conservative about its regex syntax since extensions
> are not portable across impementations so users cannot rely
> on them.
> 
> i think this extension is not available in glibc and other
> posix regex implementations either, it's a perl invention,
> so it would be wrong to add it to musl, those who want perl
> syntax can use the pcre lib.

Indeed, and beyond the general principle of not adding extensions
without strong precedent and justification, I really do not want to be
adding new dubious extensions to something we're considering rewriting
completely. It would add implementation burden and constraints on the
new implementation.

Rich