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 greedy and non-greedy matching, the threads are executed in a
priority order.

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>
TO-UNDO: assertions

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
fixup! Start implementing a regular expression engine
Regex: add some code for debugging

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>
fixup! Start implementing a regular expression engine
fixup! Start implementing the Pattern and Matcher classes
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>
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>
WIP: test group matching

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,
all 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: add support for character classes

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.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
fixup! Start implementing a regular expression engine
Regex: introduce debug mode

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>
wip

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