ocaml/ocaml-re — pull request #48 by nojb (2014-12-20 21:53:43+00:00)
Title: [RFC] Add Unicode support

This is a first try to adding Unicode support to `ocaml-re`. The
approach is the one suggested at the end of #24. Namely,
translate *unicode* regular expressions into *byte*-oriented regular
expressions that match UTF-8-encoded strings.

This patchset adds a new module, `Re_unicode` which defines the type of
unicode regular expressions. A new type is needed because it is not
safe to mix unicode and byte-oriented regular expressions. The
interface is a slightly modified version of the existing interface in
`Re`. There is also a corresponding findlib library `re.unicode`.

On the implementation side, `Re_unicode` uses the same implementation as
`Re`, but overloading the `Set` variant to mean sets of *unicode* code
points. Before compilation the unicode regular expression is
traversed (see `handle_unicode` in `re_unicode.ml`) to translate it into
a byte-oriented one and then everything goes through as before.

The same POSIX character classes (`alnum`, `digit`, etc.) present in
`Re` are offered by this module, but implemented in terms of unicode as
suggested by [UTS #18](http://www.unicode.org/reports/tr18/#Compatibility_Properties).
More fine-grained unicode character sets can be added easily. The
definition of unicode character sets depends on static data contained in
the module `Unicode_groups`. This module can be regenerated from the
Unicode Character Database by a tool called `gen_unicode_groups` found
in the `tools/` directory. The tool itself depends on the
[`uucd`](http://erratique.ch/software/uucd) library. No extra
dependency is required for `re`.

There are some difficulties in integrating unicode elegantly to the
current code base arising from the fact that this library makes some
assumptions about the character set when compiling and interpreting REs:

- The `bol`, `eol`, `eow`, `bow` combinators are ASCII-specific and
handled specially in the RE engine. These are not currently present
in the `Re_unicode` interface.

- (**BREAKING CHANGE**) The `case`, `no_case` combinators have different
semantics for unicode because a single unicode character can change
case to a *sequence* of unicode characters, so it is no longer true
that applying one of these combinators to a character set gives a
character set. In the present patchset the result of applying one of
these combinators to a character set is no longer considered to be a
character set (which is the right behaviour for unicode, I think).
This can be reverted back to the old behaviour for the `Re` module
with a little bit of refactoring.

- The `~pos` and `~len` arguments in the `exec*`, `all*`, `split*`
functions require indexing into a UTF-8 string which takes time linear
on the length of the string. These arguments are not present in the
current changeset, but could be easily added.

In summary, I think the best course of action would be to refactor the
library so that the core is completely independent of the character sets
and deals only with arbitrary bytes. Both ASCII and unicode engines
should be added on top. There is some special handling of the `bol`,
`eol`, `eow`, `bow` combinators in the RE engine that would have to be
factored out, but someone more knowledgeable about the internals needs
to explain what is involved in this.

Lastly, this changeset has only been tested very lightly and more
thorough testing is required, but I wanted to put it out now in order to
receive feedback from those interested.

Any and all comments welcome!