Start implementing a regular expression engine

So far, these are humble beginnings indeed. Based on the descriptions of

	http://swtch.com/%7Ersc/regexp/regexp2.html

I started implementing a Thompson NFA / Pike VM.

The idea being that eventually, regular expressions are to be compiled
into special-purpose bytecode for the Pike VM that executes a varying
number of threads in lock-step over each character of the text to match.
The thread count is bounded by the length of the program: two different
threads with identical instruction pointer at the same character-to-match
would yield exactly the same outcome (and therefore, we can execute just
one such thread instead of possibly many).

To allow for matching groups, each thread carries a state with it, saving
the group offsets acquired so far.

To ease development, the PikeVM class is embedded as package-local classes
into test/Regex.java (so that I can easily develop them using Eclipse,
leaning heavily on Eclipse's debugger).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Start implementing the Pattern and Matcher classes

Based on the just-implemented PikeVM, let's test it with a specific
regular expression. At this point, no parsing is implemented at this time
but instead an explicit program executing a(bb)?a is hardcoded.

For ease of development, the Pattern and Matcher classes are still
embedded as package-local classes into test/Regex.java.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
TO-UNDO: makefile target for Regex
Turn test/Regex into a real unit test

We still do not parse the regular expressions, but we can at least test
that the hardcoded 'a(bb)+a' works as expected.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: optimize matching characters

Instead of having an opcode 'CHAR', let's have the opcodes that fall
within the range of a char *be* the opcode 'match this character'.

While at it, break the ranges of the different types of opcodes apart a
litte and describe them, too.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support prioritized threads

If we want to match greedy or reluctant regular expressions, we have
to make sure that certain threads are split off with a higher priority
than others. We will use the ThreadQueues' natural order as priority
order: high to low.

To support splitting into different-priority threads, let's introduce
a second SPLIT opcode: SPLIT_JMP. The latter prefers to jump while the
former prefers to execute the opcode directly after the SPLIT opcode.

There is a subtle challenge here, though: let's assume that there are
two current threads and the higher-priority one wants to jump where
the lower-priority one is already. In the PikeVM implementation
before this change, queueImmediately() would see that there is
already a thread queued for that program counter and *not* queue the
higher-priority one.

Example: when matching the pattern '(a?)(a??)(a?)' against the string
'aa', after the first character, the first (high priority) thread
will have matched the first group while the second thread matched the
second group. In the following step, therefore, the first thread will
want to SPLIT_JMP to match the final 'a' to the third group but the
second thread already queued that program counter.

The proposed solution is to introduce a third thread queue: 'queued'.
When queuing threads to be executed after reading the next character
from the string to match, they are not directly queued into 'next' but
into 'queued'. Every thread requiring immediate execution (i.e. before
reading the next character) will be queued into 'current'. Whenever
'current' is drained, the next thread from 'queued' that has not been
queued to 'current' yet will be executed.

That way, we can guarantee that 1) no lower-priority thread can override
a higher-priority thread and 2) infinite loop are prevented.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: special-case a(a*?)(a?)(a??)(a+)(a*)a

Among other challenges, this regular expression is designed to demonstrate
that thread prioritization is finicky: Given the string 'aaaaaa' to match,
the first four threads will try to grab the second 'a', the third thread
(the one that matched the '(a??)' group) having scheduled the same
instruction pointer to the '(a+)' group that the second -- higher-priority
-- thread will try to advance to only after processing the '(a??)' group's
SPLIT. The second thread must override the third thread in that case,
essentially stopping the latter.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: test group matching

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: add a class for matching character classes

This will be used to match character classes (such as '[0-9a-f]'), but
it will also be used by the regular expression pattern parser to
determine whether a character is special.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: Implement compiler for regular expression patterns

Originally, this developer wanted to (ab)use the PikeVM with a
hand-crafted program and an added "callback" opcode to parse the regular
expressions.

However, this turned out to be completely unnecessary: there are no
ambiguities in regular expression patterns, so there is no need to do
anything else than parse the pattern, one character at a time, into a
nested expression that then knows how to write itself into a program for
the PikeVM.

While at it, we fix the preamble for find(): we implemented it initially
as (?:..*?) instead of (?:.*?) due to the lack of prioritization. But now
we have SPLIT_JMP, so we can do it correctly.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support the dot

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement * and + operators

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: Implement reluctant '?', '*' and '+'

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement find()

Now that we have non-greedy repeats, we can implement the find() (which
essentially prefixes the regular expression pattern with '.*?'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: add support for character classes

Now we support regular expression patterns a la '[0-9]'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement non-capturing groups

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement alternatives

Now we support regular expressions like 'A|B|C'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support lookaheads

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: add a method to reverse the PikeVM program

A program for the PikeVM corresponds to a regular expression pattern. The
program matches the character sequence in left-to-right order. However,
for look-behind expressions, we will want to match the character sequence
backwards.

To this end, it is nice that regular expression patterns can be reversed
in a straight-forward manner. However, it would be nice if we could avoid
multiple parsing passes and simply parse even look-behind expressions as
if they were look-ahead ones, and then simply reverse the program for that
part.

Happily, it is not difficult to reverse the program so it is equivalent to
matching the pattern backwards.

There is one catch, though. Imagine matching the sequence "a" against the
regular expression "(a?)a?". If we match forward, the group will match the
letter "a", when matching backwards, it will match the empty string. So,
while the reverse pattern is equivalent to the forward pattern in terms of
"does the pattern match that sequence", but not its sub-matches. For that
reason, Java simply ignores capturing groups in look-behind patterns (and
for consistency, the same holds for look-ahead patterns).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support look-behind patterns

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>