Subject: variables: greedy or non-greedy matching

From: Kjetil Torgrim Homme <[email-masked]>
Date: 24 Apr 2003 14:08:45 +0200

I can not find any precedence for greedy/non-greedy matching in the
RFC's (I only checked NNTP, I don't know where else to look).  it
seems to me that previously, we have only been interested in
TRUE/FALSE, _how_ the match was performed can not be observed.  the
variables extension introduces ${<n>} which allows us to observe
matching behaviour, and therefore whether to do greedy/non-greedy
matching must be part of the variables specification.

Jutta points out in private e-mail that greedy matching does not
follow the prinicple of least surprise for ordinary users.  e.g., in

  string :matches "<[email-masked]>, <[email-masked]>" "<[email-masked]>*"

most users will probably expect ${1} to contain "alice", not
"[email-masked]>, <bob".  change it into:

  string :matches "<[email-masked]>, <[email-masked]>" "*<[email-masked]>*"
                                                    ^
and ${2} is now "bob"...  not intuitive, right?

this issue was raised here earlier, and by analogy with regular
expressions, I claimed the wildcard "*" in :matches should match
greedily.  this allows an implementation to convert a match string to
a regular expression very easily, but is potentially confusing for
users.

non-greedy matching requires implementers to write their own matching
code, or to use a regexp library which supports non-greedy matching.

what do you think?

if we go for non-greedy, Jutta suggested using "**" as a special case
to get greedy matching.  (actually, I think the rule should be that
"*" followed by another wildcard is greedy.)  I'm not sure it is worth
it, after all a site supporting variables will most likely also offer
regex.
-- 
Kjetil T.

---

From: [email-masked]
Date: Thu, 24 Apr 2003 07:14:43 -0700 (PDT)

> and ${2} is now "bob"...  not intuitive, right?

Um, no. For the very small subset of users sophisticated enough to
write this sort of code themselves, I believe their expectation will
be set by past experience with other matching systems, and these
systems tend to default to greedy matching.

> what do you think?

I prefer greedy matching.

> it, after all a site supporting variables will most likely also offer

I don't think it is worth it either.

				Ned

---

From: Jutta Degener <[email-masked]>
Date: Thu, 24 Apr 2003 10:35:57 -0700

> systems tend to default to greedy matching.

I think even in that sophisticated subset, most people just live
their pattern-matching lives without really thinking about the
difference.

But admittedly, my own expectations are muddy, and, worse,
seem to change with the lexical structure of the pattern. 
Speaking naively -- I know that this isn't how things work
or should work --

* If the end of my pattern is part of a grammatical whole, I want
  the wildcard to  be greedy; certainly, I, too, would expect
  "f*o" to fully match "foo", not to stop after the first "o".

* But if the end of my pattern is a delimiter, I tend to implicitly
  expect the expression be defined as something that doesn't
  contain that delimiter, as in the example Kjetil quoted where few
  people would expect the * before a closing > in an e-mail address
  to itself contain another >.

I think what this all says is that what felt to me like a problem
with greed is really a problem with globbing and insufficient
expressiveness of * (regexps have problems, too, once you get
to comments and quoting, but one has to work a little harder to
make things fail.)

So let's stay greedy; thanks for setting me straight! 

Jutta

---

From: [email-masked]
Date: Sun, 27 Apr 2003 13:33:49 -0700 (PDT)

> So let's stay greedy; thanks for setting me straight!

No problem ;-) And let's also remember that a necessary corollary here
is that the regexp we end up choosing needs to support both greedy and
non-greedy matching.

				Ned

---

From: Kjetil Torgrim Homme <[email-masked]>
Date: 30 Apr 2003 01:13:50 +0200

[Ned Freed]:
>   [Jutta Degener]:
>   No problem ;-) And let's also remember that a necessary corollary
>   here is that the regexp we end up choosing needs to support both
>   greedy and non-greedy matching.

why?  I thought we only needed that if :matches was non-greedy.

I wouldn't mind having non-greedy regexps, but they're not in POSIX.2
which the regex draft refers to.

-- 
Kjetil T.

---

From: [email-masked]
Date: Tue, 29 Apr 2003 18:01:19 -0700 (PDT)

> which the regex draft refers to.

Jutta's argument, which I believe is valid, is that expectations can only
be met by having both types available. As for the reference to POSIX, I thought
that had already been determined to be unsufficient and there was a suggestion
to replace it with something else (ECMAScript maybe?).

				Ned

---

From: Jutta Degener <[email-masked]>
Date: Wed, 30 Apr 2003 10:58:57 -0700

On Tue, Apr 29, 2003 at 06:01:19PM -0700, [email-masked] wrote:
> be met by having both types available.

Most cases of it can also be met with character classes.

That's why I said "let's stay greedy" in the piece you quote above --
I realized that I wanted to solve problems with non-greed that can
be solved with regexes.

Jutta