From: Bart Schaefer <schaefer@brasslantern.com>
To: Bart Schaefer <schaefer@brasslantern.com>,
Johan Grande <nahoj@crans.org>,
zsh-workers@zsh.org
Subject: Re: Pattern bug on (a*|)~^(*b)
Date: Fri, 28 Jul 2023 18:35:38 -0700 [thread overview]
Message-ID: <CAH+w=7Z9+VHUc3h_ZULpcnmqReQoQOQ03GuJtTCsBWFKK5Tf5Q@mail.gmail.com> (raw)
In-Reply-To: <20230728064106.ufcfaqondhn3wge7@chazelas.org>
On Thu, Jul 27, 2023 at 11:41 PM Stephane Chazelas
<stephane@chazelas.org> wrote:
>
> I have to say I'm with the OP and don't understand that
> explanation either.
In the absence of a direct response from PWS, I'll just point you to
his comments in pattern.c, some of which date from before we had a git
repository:
* The strategy is to test the asserted pattern,
* recording via P_EXCSYNC how far the part to
* be excluded matched. We then set the
* length of the test string to that
* point and see if the exclusion as far as
* P_EXCEND also matches that string.
* We need to keep testing the asserted pattern
* by backtracking, since the first attempt
* may be excluded while a later attempt may not.
* For this we keep a pointer just after
* the P_EXCLUDE which is tested by the P_EXCSYNC
* to see if we matched there last time, in which
* case we fail. If there is nothing to backtrack
* over, that doesn't matter: we should fail anyway.
* The pointer also tells us where the asserted
* pattern matched for use by the exclusion.
* P.S. in case you were wondering, this code
* is horrible.
* This is where we make sure that we are not
* repeatedly matching zero-length strings in
* a closure, which would cause an infinite loop,
* and also remove exponential behaviour in
* backtracking nested closures.
* If we come round to the same branch again, and
* there is already a 1, then the test fails.
By my reading, zero-length matches may be short-circuited to avoid
pathological behavior.
next prev parent reply other threads:[~2023-07-29 1:36 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-25 13:19 Johan Grande
2023-07-25 18:35 ` Bart Schaefer
2023-07-25 18:47 ` Johan Grande
2023-07-28 1:02 ` Bart Schaefer
2023-07-28 6:41 ` Stephane Chazelas
2023-07-29 1:35 ` Bart Schaefer [this message]
2023-08-01 13:19 ` Johan Grande
2023-08-01 13:30 ` Peter Stephenson
2023-08-01 13:46 ` Johan Grande
2023-08-02 8:31 ` Johan Grande
2023-08-02 9:37 ` Peter Stephenson
2023-07-31 11:36 ` Peter Stephenson
2023-07-31 15:21 ` Peter Stephenson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAH+w=7Z9+VHUc3h_ZULpcnmqReQoQOQ03GuJtTCsBWFKK5Tf5Q@mail.gmail.com' \
--to=schaefer@brasslantern.com \
--cc=nahoj@crans.org \
--cc=zsh-workers@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).