This is very impressive.

> how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity.

I'm pretty sure that should say "the leftmost start paired with the leftmost end".

This also implies that the algorithm has to scan the entire input to find the first match, and the article goes on to confirm this. So the algorithm is a poor choice if you just want the first match in a very long text. But if you want all matches it is very good.

▲

mananaysiempre 5 hours ago | parent [-]

> I'm pretty sure that should say "the leftmost start paired with the leftmost end".

I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.

▲

masfuerte 5 hours ago | parent [-]

As originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.

▲

ieviev 4 hours ago | parent | next [-]

It goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end.

there's an implicit `.*` in front of the first pass but i felt it would've been a long tangent so i didn't want to get into it.

so given input 'aabbcc' and pattern `b+`,

first reverse pass (using `.*b+`) marks 'aa|b|bcc'<-

the forward pass starts from the first match:

'aa->b|b|cc' marking 2 ends

then enters a dead state after the first 'c' and returns the longest end: aa|bb|cc

i hope this explains it better

▲

masfuerte 3 hours ago | parent [-]

Cheers. I was more confused by how you were doing multiple matches. So I read the paper, which describes the AllEnds algorithm. If I understand correctly, the reverse pass captures all of the match starts and these need to be remembered for the forward pass. Which is what you were showing above, but I didn't follow it.

So, once it gets going, a traditional engine can produce matches iteratively with no further allocation, but RE# requires allocation proportional to the total number of matches. And in return, it's very much faster and much easier to use (with intersection and complement).

	▲	ieviev 3 hours ago \| parent [-]
		Yes, exactly correct It's also beneficial to merge some of the matching locations into ranges where possible, so when `a*` matches a long sequence of '\|a\|a\|a\|a\|a\|', it can be represented as a range of (0,5), we do this to keep the lookaround internal states smaller in the engine.

▲

mananaysiempre 3 hours ago | parent | prev [-]

Right, the explanation seems to be a bit oversimplified, but I don’t think it’s difficult to fix it up: you need to collect non-overlapping starts (with an RTL scan) and ends (with an LTR scan) and zip them together. The non-overlapping matches are the last ones you see before you need to reset the matcher (traverse a failing edge). This feels like it should work.

(I tried to write some pseudocode here but got annoyed dealing with edge cases like zero-length matches at EOF, sorry.)