Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
From: Bart Schaefer <schaefer@brasslantern.com>
Message-Id: <160605121020.ZM7727@torch.brasslantern.com>
Date: Sun, 5 Jun 2016 12:10:20 -0700
In-Reply-To: <CAKc7PVC=AES1LhY7tYTXrPsefX3CXgtUsxiVbDaxmc5o2iHnVw@mail.gmail.com>
Comments: In reply to Sebastian Gniazdowski <sgniazdowski@gmail.com>
        "[BUG] Long line makes pattern matching (by //) hog Zsh" (Jun  5,  4:36pm)
References: <CAKc7PVC=AES1LhY7tYTXrPsefX3CXgtUsxiVbDaxmc5o2iHnVw@mail.gmail.com>
To: Zsh hackers list <zsh-workers@zsh.org>
Subject: Re: [BUG] Long line makes pattern matching (by //) hog Zsh
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii

On Jun 5,  4:36pm, Sebastian Gniazdowski wrote:
}
} 1. not backslash nor slash nor space [^ /\\\\]##
} 2. not number, slash, backslash, space [^0-9/\\\\ ]##
} 3. not slash, backslash [^/\\\\]#
} 4. end of line (#e)

It's in the block in pattern.c:patchmatch() that begins with the
comment:

		/*
		 * Lookahead to avoid useless matches. This is not possible
		 * with approximation.
		 */

Specifically, in the "if (no >= min) for (;;) ..." loop, at each charater
in the input string patmatch() is called recursively to look at the rest
of the string, which again enters this same loop because the next thing
is also a one-or-more expression, which calls recursively and again
enters the loop because the thing after that is a zero-or-more.

It consumes a LOT of memory while doing this, even if I add a hack to
prevent it from recursively re-entering lookahead (or to skip the
lookahead entirely).