From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/10575
Path: news.gmane.org!.POSTED!not-for-mail
From: Szabolcs Nagy <nsz@port70.net>
Newsgroups: gmane.linux.lib.musl.general,gmane.comp.version-control.git
Subject: Re: Re: Regression: git no longer works with musl libc's
 regex impl
Date: Wed, 5 Oct 2016 15:01:31 +0200
Message-ID: <20161005130130.GM1280@port70.net>
References: <20161004150848.GA7949@brightrain.aerifal.cx>
 <20161004152722.ex2nox43oj5ak4yi@sigill.intra.peff.net>
 <20161004154045.GT19318@brightrain.aerifal.cx>
 <alpine.DEB.2.20.1610041802310.35196@virtualbox>
 <20161004173926.GA19318@brightrain.aerifal.cx>
 <alpine.DEB.2.20.1610051250080.35196@virtualbox>
Reply-To: musl@lists.openwall.com
NNTP-Posting-Host: blaine.gmane.org
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: blaine.gmane.org 1475672514 15555 195.159.176.226 (5 Oct 2016 13:01:54 GMT)
X-Complaints-To: usenet@blaine.gmane.org
NNTP-Posting-Date: Wed, 5 Oct 2016 13:01:54 +0000 (UTC)
User-Agent: Mutt/1.6.0 (2016-04-01)
Cc: Rich Felker <dalias@libc.org>, Jeff King <peff@peff.net>,
	git@vger.kernel.org, musl@lists.openwall.com
To: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Original-X-From: musl-return-10588-gllmg-musl=m.gmane.org@lists.openwall.com Wed Oct 05 15:01:49 2016
Return-path: <musl-return-10588-gllmg-musl=m.gmane.org@lists.openwall.com>
Envelope-to: gllmg-musl@m.gmane.org
Original-Received: from mother.openwall.net ([195.42.179.200])
	by blaine.gmane.org with smtp (Exim 4.84_2)
	(envelope-from <musl-return-10588-gllmg-musl=m.gmane.org@lists.openwall.com>)
	id 1brlpP-0002gq-IQ
	for gllmg-musl@m.gmane.org; Wed, 05 Oct 2016 15:01:43 +0200
Original-Received: (qmail 15392 invoked by uid 550); 5 Oct 2016 13:01:43 -0000
Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm
Precedence: bulk
List-Post: <mailto:musl@lists.openwall.com>
List-Help: <mailto:musl-help@lists.openwall.com>
List-Unsubscribe: <mailto:musl-unsubscribe@lists.openwall.com>
List-Subscribe: <mailto:musl-subscribe@lists.openwall.com>
List-ID: <musl.lists.openwall.com>
Original-Received: (qmail 15374 invoked from network); 5 Oct 2016 13:01:43 -0000
Mail-Followup-To: Johannes Schindelin <Johannes.Schindelin@gmx.de>,
	Rich Felker <dalias@libc.org>, Jeff King <peff@peff.net>,
	git@vger.kernel.org, musl@lists.openwall.com
Content-Disposition: inline
In-Reply-To: <alpine.DEB.2.20.1610051250080.35196@virtualbox>
Xref: news.gmane.org gmane.linux.lib.musl.general:10575 gmane.comp.version-control.git:306190
Archived-At: <http://permalink.gmane.org/gmane.linux.lib.musl.general/10575>

* Johannes Schindelin <Johannes.Schindelin@gmx.de> [2016-10-05 13:17:49 +0200]:
> I had a brief look at the source code (you use backtracking... hopefully
> nobody uses musl to parse regular expressions from untrusted, or
> inexperienced, sources [*1*]), and it seems that the regex code might

does git use BRE?

a conforming BRE implementation has to use back tracking
if the pattern has back references.

usually ERE implementations may also use back tracking
since they support back references as an extension.

musl does not support this extension (and many others) so
it never uses back tracking for ERE matches, note however
that match complexity and memory usage of a conforming
ERE implementation is still exponential in pattern
length because of repetition counts.