Remacs: Emacs internal string encoding

[db48x]

Currently some of the ported functions (like the error! macro) are using Rust's strings to handle data from an Emacs string or buffer. Rust's strings are quite nice, but Emacs has a subtly different requirements that make them the wrong choice in almost all cases.

If we look in the Emacs manual, section 22.2 says:

Internally, Emacs uses its own multibyte character encoding, which is
a superset of the “Unicode” standard. This internal encoding allows
characters from almost every known script to be intermixed in a single
buffer or string. Emacs translates between the multibyte character
encoding and various other coding systems when reading and writing
files, and when exchanging data with subprocesses.

The Elisp manual, in section 32.1, elaborates:

Emacs buffers and strings support a large repertoire of characters from
many different scripts, allowing users to type and display text in
almost any known written language.

To support this multitude of characters and scripts, Emacs closely
follows the “Unicode Standard”. The Unicode Standard assigns a unique
number, called a “codepoint”, to each and every character. The range of
codepoints defined by Unicode, or the Unicode “codespace”, is
‘0..#x10FFFF’ (in hexadecimal notation), inclusive. Emacs extends this
range with codepoints in the range ‘#x110000..#x3FFFFF’, which it uses
for representing characters that are not unified with Unicode and “raw
8-bit bytes” that cannot be interpreted as characters. Thus, a
character codepoint in Emacs is a 22-bit integer.

To conserve memory, Emacs does not hold fixed-length 22-bit numbers
that are codepoints of text characters within buffers and strings.
Rather, Emacs uses a variable-length internal representation of
characters, that stores each character as a sequence of 1 to 5 8-bit
bytes, depending on the magnitude of its codepoint(1). For example, any
ASCII character takes up only 1 byte, a Latin-1 character takes up 2
bytes, etc. We call this representation of text “multibyte”.

To summarize, Emacs internally stores strings in a format which is exactly like UTF-8 except that the allowed range of codepoints is larger. Thus while the largest codepoints in UTF-8 are encoded in 4 bytes, in Emacs the largest codepoints need 5 bytes. It uses these extra codepoints to encode characters which don't have any unicode equivalent. This allows an Emacs buffer to hold text from multiple character sets during editing (they all get reencoded to a common character set when the buffer is written to disk). We need to implement a string type which follows these rules, and use it instead of the built-in str and String types.

Emacs also sometimes uses "unibyte" strings or buffers, which are just byte arrays with no associated encoding. These are equivalent to &[u8], so there's really nothing we need to implement ourselves, but note that most of Emacs' high-level string and buffer operations work on both unibyte and multibyte strings and buffers, so probably we would want a unified Rust type for both.

[db48x]

I did some more research on this a few weeks back, and have some actual details.

First, src/character.h has a comment which details the encoding scheme used by Emacs, reproduced here:

character code    1st byte   byte sequence
--------------    --------   -------------
     0-7F     00..7F     0xxxxxxx
    80-7FF        C2..DF     110xxxxx 10xxxxxx
   800-FFFF       E0..EF     1110xxxx 10xxxxxx 10xxxxxx
 10000-1FFFFF F0..F7     11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
200000-3FFF7F F8     11111000 1000xxxx 10xxxxxx 10xxxxxx 10xxxxxx
3FFF80-3FFFFF C0..C1     1100000x 10xxxxxx (for eight-bit-char)
400000-...        invalid

invalid 1st byte  80..BF     10xxxxxx
                   F9..FF    11111xxx (xxx != 000)

As you can see, raw byte values are assigned to Codepoint values between 0x3FFF80 and 0x3FFFFF. When encoded into a string, they occupy the gap between the single-byte characters and the two-byte characters.

Note that although the comment suggests that 8 bits will fit into this gap, but actually only seven will really fit. If you do stuff a value in here which has the high bit set, it will be decoded later as a normal two-byte UTF-8 character, and thus the value will be lost. Nothing I've seen in the Emacs code seems to check for this case, or make it clear that they're preventing it from happening. We'll probably want to be sure to add tests for this specific case; it'll be especially interesting to see if they fail in Emacs or not... In our implementation we'll probably want to use one of the larger gaps in the UTF-8 encoding; these values are pretty rare in practice, and we don't care if they take a few extra bytes in memory.

Finally, Emacs supports five-byte characters, which are completely useless. UTF-8 originally supported five and six-byte characters, but for compatibility all five and six-byte characters were dropped, as where the majority of the four-byte characters (we're a fair way off from needing codepoint values that high anyway). We can simplify this to just support the normal range of Codepoint values, plus some extras for raw bytes.

This file also defines two C macros for converting between raw bytes and a Codepoint value, BYTE8_TO_CHAR, and CHAR_TO_BYTE8. Note that because of the deficient typing, both values might be u32s; it's up to the user of the macro to decide what types are in play. The UNIBYTE_TO_CHAR and MAKE_CHAR_UNIBYTE call these macros if the character is a non-ascii character, which means calling these macros on values with the high bit set. Awesome.

It also defines two macros for testing whether something is a raw byte. CHAR_BYTE8_P tests to see if a Codepoint represents a raw byte, while CHAR_BYTE8_HEAD_P tests to see if the argument is the first byte of a two-byte sequence which encodes a raw byte.

[db48x]

So I've been thinking about how we should implement this ourselves. I think we have to bite the bullet and write our own type to replace String. We would still be able to use String and str in many places (such as error messages which are static values), but they would get converted to our replacement type whenever they become Lisp values, or whenever they're inserted into a buffer. For convenience, our replacement type should have exactly the same methods as the native String type, with only a few additions for handling raw bytes. I'm happy to just copy and paste these methods from the Rust standard library (or rather liballoc and libcore, where the standard library gets them from), but I don't actually know how the Rust standard library is licensed. It's probably fine, but someone should check. There are a number of macros for native strings that we'll have to reimplement for our own type as well, such as format!.

It's not very original but EmacsString seems to be the only possible name for the thing, unless you can think of something better.

Like the native String type, the EmacsString needs only to be a struct with a single member which is a Vec<u8>, so it won't occupy any more memory than a normal String or even a C string.

[shaleh]

Go with EmacsString. If we change our minds it is easy to replace.

[shaleh]

As for licenses, Rust is MIT licensed. Ideally, we place EmacsString in a crate also MIT licensed and just use the crate.

[shaleh]

I just remembered the other name we have used.

UTFE (utf emacs)

[Wilfred]

We already have Lisp_String, do we need a separate ElispString? Could we just define methods on Lisp_String?

FWIW it's a little bit more than a Vec<u8> as Emacs stores two lengths plus text properties:

struct GCALIGNED Lisp_String
  {
    ptrdiff_t size;
    ptrdiff_t size_byte;
    INTERVAL intervals;     /* Text properties in this string.  */
    unsigned char *data;
  };

[db48x]

We need a type to replace the various uses of char* in Emacs, in addition to Lisp_String. Lisp_String would become something like this:

pub struct LispString
{
  Vec<Interval> intervals,
  EmacsString data
}

(It may also need to keep track of the number of characters in the data, I don't recall if the standard string does that or not.)

The various string functions available in C and Lisp would take either LispString or EmacsString as appropriate (or references to them), and would tend to be implemented using methods on the EmacsString. For example, decode_coding_sjis would read from a Vec<u8> of input bytes, and write into a &mut EmacsString, both given to it by its caller. I'll include some notes that I have on this and similar functions shortly.

[Wilfred]

OK, so something like an EmacsEncodedStr. We can bike shed further, but as it'll be allocated by the Emacs runtime the name should perhaps end -Str.

[db48x]

Oh wow, I completely forgot about that. I have no idea how Emacs grows strings, so putting a Vec inside a Lisp_String is probably wrong.