mozart/mozart2 — pull request #5 by kennytm (2012-06-27 18:51:00+00:00)
Title: Basic support of Strings, Virtual String and Byte String, second round.

The old request is in #4. The old branch and comments are still retrievable from the [strings-as-lists](https://github.com/kennytm/mozart2/tree/strings-as-lists) tag.

Changes since #4
================

* Rebased on the latest master branch.
* String is now a distinct type again, and implements Dottable.
* Eliminated ByteStringLike, merging it with StringLike
* Rewritten StringLike to support more primitives at native speed.
* Migrated a bunch of List methods to the String module, since a String is no longer a List.
* Added a `StringOffset` datatype to allow efficient indexing without exposing the underlying UTF encoding
* Removed `VirtualString.vsChangeSign`, implemented in Oz code.
* ByteString and String now implement Comparable.
* The general `LString` is now immutable --- although it doesn't simplify anything :)
* Some coding style changes, moving stuff to the `internal` namespace, use `patternmatching` if viable, etc.

---------

And the complete changelog:

`nchar` type and `MOZART_STR` macro
=============================

From http://lists.gforge.info.ucl.ac.be/pipermail/mozart-hackers/2012/003468.html:

> For Strings, that's not so obvious. I guess all of UTF-8, UTF-16 and UTF-32 are acceptable and have their merits. It seems to me, however, that both Strings and Atoms should follow the same encoding (yes, this sentence implies that I am open to changing the encoding of Atoms). Which one of these is, from my point of view, the only unknown in the design, and the only thing I have no strong position on.

Therefore, I have created a new type `nchar` and a new macro `MOZART_STR()` to factor out the underlying UTF encoding. Currently, the two are defined as

```c++
typedef char16_t nchar;
#define MOZART_STR(S) u##S
```

so at least they are compatible with the current settings. The name is chosen as "nchar" because of Unicode. It is not "uchar" because typically "uchar" means "unsigned char". Besides, `nchar` is used for Unicode string in Transact-SQL.

All new string literals I created, and some old ones which are involved in this pull request, are written as `MOZART_STR()`, but the others are left as `u"..."` as not to create too much disturbance.

The `LString` types
=================

The `LString` type is a raw type as a thin and immutable wrapper and unique owner of a string `const C*` and its length. Standard C++'s `std::basic_string` is not used, because this type does not match with the VM's GC very well.

The story would have been simple if we only need one memory management scheme to care about. But the VM need to support and convert between memory management of the garbage-collected Mozart/Oz and deterministic C++, so the simple wrapper type is expanded into a class hierarchy with 3 members.

`LString` is an immutable wrapper of a GC-ed or permanent string. It is only used for the String and ByteString datatypes.

`ContainedLString` is a *mutable* wrapper of a C++ container `V`, which exposes itself only as an array of `C`. It is used only when it is more efficient to move the whole container around.

`BaseLString` is the base class of the two classes above. It is also an immutable wrapper of a temporary (e.g. stack-allocated) string.

This is the simplest approach I can think of, without sacrificing performance for unnecessary copying.

UTF and ISO 8859-1 conversion functions
=======================================

Functions are provided to convert between different UTF encodings, and between ISO 8859-1 (Latin-1) and `LString`. These are implemented manually, instead of reusing the standard C++ conversion methods in [``](http://en.cppreference.com/w/cpp/locale/codecvt), nor reusing the [ICU](http://icu-project.org/apiref/icu4c/ustring_8h.html) functions, because:

1. The UTF-related `` [does not work in libstdc++ yet](http://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2011).
2. I don't want to add ICU as another dependency yet.

These conversion functions have been tested in `vm/test/utftest.cc` and `vm/test/coderstest.cc`.

StringOffset
=========

A new data type StringOffset is added to the system. This type represents the number of *code units* starting from the beginning to a specified character. For instance, in UTF-16, the StringOffset of the character "X" would be 7, although it its character index is 4:

\U00010000\U00020000\U00030000WX

This datatype is added mainly to avoid an O(N) slowdown of some algorithms when only the character index is available. This data type is not needed if strings are UTF-32.

StringLike
========

Strings are implemented as a distinct type, unlike in VM 1.4 where String and Cons are conflated. Furthermore, strings in VM 2.0 adapt an array-like data structure by implementing Dottable. The StringLike interface is written to support both String and ByteString.

Since String and ByteString share the same interface, many String methods can be applied on ByteString as well. For those methods I am not going to write the distinct ByteString Oz procedures. The usage is explained below.

The Oz modules
============

1. Enabled `IntToString`, `FloatToString` and `AtomToString`. They all forward to `VirtualString.toString`.
2. Added the `String` module. This module contains the following methods:

1. The 1.4 primitive methods `String.is = IsString`, `String.toAtom = StringToAtom`
2. The new primitive methods

```tex
{String.append +S1 +S2 ?ResultS}
% Concatenate S1 and S2, to give a new string ResultS.

{String.slice +S +FromOffset +ToOffset ?Substring}
% Extract a substring within the range [FromOffset, ToOffset).

{String.search +S +FromOffset +NeedleS ?NeedleBeginOffset ?NeedleEndOffset}
% Search for a substring NeedleS in S, starting from FromOffset (inclusive). The resulting
% range will be assigned as [NeedleBeginOffset, NeedleEndOffset). If the substring is
% not found, both NeedleBeginOffset and NeedleEndOffset will be bound to `false`.
%
% NeedleS can be a string or an integer (for a Unicode code point).

{String.'end' +S ?EndOffset}
% Returns the offset pointing beyond the last character of S.

{String.isPrefix +PrefixS +S ?B}
% Returns whether S has the prefix PrefixS.

{String.isSuffix +SuffixS +S ?B}
% Returns whether S has the suffix SuffixS.

{String.length +S ?LengthI}
% Returns the number of Unicode code points in S.
% This function simply forwards to `VirtualString.length`.
```

3. The 1.4 derived methods

```tex
{String.token +S1 X ?S2 ?S3}
{String.tokens +S X ?Ss}
% Similar to the existing methods, but with two changes:
% 1. The X can be either an integer (Unicode code point) or a string
% 2. {String.tokens "121" &1} == ["", "2", ""] in 2.0, instead of ["", "2"] in 1.4.
```

4. The new derived methods

```tex
{String.foldLInd +S +P InitVal ?ResVal} % {P Offset CurVal CharI ?NewVal}
{String.foldRInd +S +P InitVal ?ResVal} % {P Offset CharI CurVal ?NewVal}
{String.foldL +S +P InitVal ?ResVal} % {P CurVal CharI ?NewVal}
{String.foldR +S +P InitVal ?ResVal} % {P CharI CurVal ?NewVal}
{String.forAllInd +S +P} % {P Offset CharI}
{String.forAll +S +P} % {P CharI}
{String.allInd +S +P ?B} % {P Offset CharI ?B}
{String.someInd +S +P ?B} % {P Offset CharI ?B}
{String.all +S +P ?B} % {P CharI ?B}
{String.some +S +P ?B} % {P CharI ?B}
% Some functional methods, taken from the List module.

{String.toList +S ?L}
% converts "hello" to [&h &e &l &l &o]

{String.toTuple +Label +S ?T}
% converts "hello" to T(&h &e &l &l &o)

{String.toArray +S ?A}
% converts "hello" to an array [&h &e &l &l &o] with the low index set to 0.
```

3. Added the `VirtualString.oz` module, with the same interface as 1.4.
4. Added the `ByteString.oz` module, with almost the same interface as 1.4, except that `ByteString.toStringWithTail` is missing, and added the `ByteString.encode` and `ByteString.decode` methods as described in the next section. Since ByteString and String share the string primitives, it is possible to use most String methods on a ByteString instance, e.g.

```tex
BS = {ByteString.make "1234"}
{String.forAll BS System.show}
```

ByteString
==========

As discussed in the mailing list, a byte string still exists as a string of bytes, and two new methods are added to the ByteString type: `encode` and `decode`.

> ### encode
>
> {ByteString.encode +EncodingL +V ?ByteString}
>
> Encode a virtual string into a byte string according to the encoding scheme in `EncodingL`. This is a list of atoms, with the meanings listed below:
>
> Atom | Meaning
> ---------------|--------------------------------------------------------------------------------
> `latin1` | Encode as ISO 5589-1 (Latin-1). Out-of-range characters will be replaced by '?'.
> `iso8859_1` | Same as `latin1`.
> `utf8` | Encode as UTF-8 (the default).
> `utf16` | Encode as UTF-16.
> `utf32` | Encode as UTF-32.
> `bom` | Encode a byte-order-mark (BOM, U+FEFF) at the beginning of the string.
> `littleEndian` | Use little-endian byte ordering. This is the default.
> `bigEndian` | Use big-endian byte ordering.
>
> For example:
>
> B = {ByteString.encode [utf8] "foo"} % Encode "foo" using UTF-8.
> C = {ByteString.encode [utf32 littleEndian] "bar"} % Encode "bar" using UTF-32-LE.
> D = {ByteString.encode [utf16 bigEndian bom] "baz"} % Encode "baz" using UTF-16-BE with BOM.
>
> ### decode
>
> {ByteString.decode +EncodingL +ByteString ?S}
>
> Reverse operation of `encode`. Decode a byte string into a string. The meaning of `EncodingL` is the same as in `encode`.

The old functions, `make` and `toString`, are equivalent to using `encode` and `decode` with the option `[latin1]`.

[]()

MozartTest
==========

A large number of test cases are added in this pull request. Therefore, I have also refactored the unit-testing code.

A new base class, `mozart::MozartTest`, is added. New unit test modules should inherit from `mozart::MozartTest`, instead of `testing::Test`. This base class serves two purposes:

1. Define the `vm` member and initialize it accordingly. This factors out the common boilerplates in `smallinttest.cc` and `floattest.cc`.
2. Define many common `EXPECT_xxxx` methods directly in the class. For instance, `EXPECT_EQ_INT`, `EXPECT_EQ_ATOM`, etc. are used not only in small-int or atom tests.

Miscellaneous changes
=====================

* The crit-bit trie in the atom table is modified to adapt for any kind of UTF code unit size (`char`, `char16_t` or `char32_t`). This have been tested in `vm/test/atomtest.cc`.
* Added `ozListForEach()` in `vm/main/utils.hh`. The signature is a bit different from the one in `boostenv/main/boostenv.hh`.
* Added `mozart::function_traits` for extracting argument types.
* Modified two asserts in `vm/main/emulate.cc` and `vm/main/objects.hh` to solve the signed/unsigned comparison warning.

Features not implemented in this pull request
=============================================

This pull request is made only to set up the basic infrastructure of strings, virtual strings and byte strings. Some features are omitted, and I think that is better done after the foundation is set first:

1. `Value.toVirtualString`
2. `String.isAtom`
3. `String.toInt`, `isInt`, `toFloat` and `isFloat`
4. Anything related to the Unicode character database (UCD), i.e. the whole `Char` module

Changes needed in the bootstrap compiler and/or the emulator
============================================================

The current bootstrap compiler generate string literals as a list of characters. This needs to be changed to a call to `String::build()` for the correct type. This may mean an additional opcode in the emulator.