Re: [musl] Re: Regression: git no longer works with musl libc's regex impl
- From
- Szabolcs Nagy <nsz@port70.net>
- Date
- Oct 5, 2016, 13:01 UTC
- Message-ID
- <20161005130130.GM1280@port70.net>
- In-Reply-To
- <alpine.DEB.2.20.1610051250080.35196@virtualbox>
* 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.