mozart/mozart2 — pull request #4 by kennytm (2012-06-17 20:15:02+00:00)
Title: Basic support of Strings, Virtual String and Byte String.

This is a big set of commits, and also involves some fundamental changes to the VM. The following describes the major changes involved, starting from the lowest level.

`nchar` type and `NSTR` 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 `NSTR()` to factor out the underlying UTF encoding. Currently, the two are defined as

```c++
typedef char16_t nchar;
#define NSTR(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 `NSTR()`, but the others are left as `u"..."` as not to create too much disturbance.

`LString` and `FreeableLString` types
===========================================

The `LString` type is a raw type as a thin 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.

`FreeableLString` is a subclass of `LString`, which supports deterministic destruction.

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`.

Cons
====

In the final version I did not implement a separate String nor Character type.

The problem of a separate Character type is a potential need to support some complex algebraic structure the current type system does not handle yet (basically, char + char = error, char - char = int, char ± int = char), and is very incompatible with VM 1.4 unless we tweak the unification system to allow strings to match a char. The problem of a separate String type is also unification.

Therefore, to avoid making big changes to the unification system, the Cons type is empowered to support a compact String storage as well.

The content of the Cons type is now briefly

```c++
class Implementation {
StableNode _head;
StableNode _tail;
LString _string;
};
```

where one of the `_head`/`_tail` pair, or the `_string` member may be empty. When one builds a string, it type can be expressed simply by

{_head: null, _tail: null, _string: NSTR("hello")}

instead of the singly linked list

{_head: 'h', _tail: {
_head: 'e', _tail: {
_head: 'l', _tail: {
_head: 'l', _tail: {
_head: 'o', _tail: Atom(nil)
}
}
}
}

This new representation should be totally hidden to an Oz user, for example, one should still able to use the 1.4-era code

fun {ToUpper S}
case S
of nil then nil
[] H|T then (H-32)|{ToUpper T}
end
end

as a buggy :grin: way to change a string to uppercase.

To an Oz programming, a string is now considered as a list of Unicode code points, i.e. integers in the range 0–0x10ffff (excluding 0xd800–0xdfff). In 1.4 a string is only a list of ISO-8859-1 code points, in the range 0–255. Therefore, some integer lists previously not considered as strings, will now be considered as strings.

The conversion between Head/Tail representation and String representation should be transparent to the user, but for now there is one point of abstraction leak: `printReprToStream()`. If the programmer calls

C = [72 69 76 76 79]
{Show C}
{Show {String.is C}}
{Show C}

currently they will see

72|69|76|76|79|'nil'
true
"HELLO"

because the call of `String.is` caused the data type to know that itself is a string. This will be plugged in the future when `Value.toVirtualString` is implemented (the current `printReprToStream()` is insufficient anyway, because it does not support the `Width` argument.)

Due to the unification, the Cons interface is also changed a bit. The original `getHead()` and `getTail()` functions now return UnstableNode, because in string representation new UnstableNodes are generated on the fly. And there is now a `getStableHeadAndTail()` function to get both head and tail simultaneously as StableNodes, mainly used in unification.

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.
> `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`.
* `IntegerDottableHelper::getValueAt()` is changed to return `OpResult` instead of `void` because of potential exceptions thrown by decoding a UTF string.
* Cons is pulled out of `records.hh`, into its own `cons.hh`, due to its large size.

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. `ByteString.toStringWithTail`
3. `ByteString.cmp` (and it seems undocumented in 1.4...)
4. `String.isAtom`
5. `String.toInt`, `isInt`, `toFloat` and `isFloat`
6. `String.token` and `tokens`
7. Specialization of some List functions (e.g. `Append`, `Length`, `Nth`, ...) which would be more efficient when the list is known to be a string
8. 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 `buildString()` for best efficiency. This may mean an additional opcode in the emulator.

Disclaimers
===========

* I have only tested the VM on Linux 64-bit.
* While most C++ code are automatically tested, I did not check whether all Oz code are correct.

Thanks.