String offsets should always be in bytes

[marijnh]

Things like str::index and str::find currently return a character offset, and str::slice takes character offsets. As by-char indexing is O(n), this will fall down horribly in any kind of code that needs to be fast.

I think the way to do this is to always use byte offsets. This complicates the mental model of our strings a bit, and is not safe (you can pass a bogus middle-of-multibyte-char offset to slice), but it certainly beats O(n) access.

(If we are so concerned about safety, we should not be representing strings as UTF8 byte sequences.)

[kud1ing]

str currently seems to be used as a mixture of "a string of characters" and "a vector of bytes". The latter

• exposes the string's implementation details
• makes it possible to skrew up the internal string state.

When you need access to a byte-vector, what is str giving that vec lacks?

[marijnh]

To be clear: I am not advocating actually changing our string representation. UTF8 strings have a lot of brilliant properties. They just don't to mesh all that well with the cargo-cult form of 'safe programming' that some people have lately been advocating.

[kud1ing]

To make myself clearer, too:
We have two data types for handling characters and bytes:

• vec for handling bytes
• str for handling characters

Can you explain the necessity to make str's interface byte-based instead of just using vec?

[nikomatsakis]

One thought: could we have str::slice assert that slice() (and similar functions) do not divide a UTF-8 character in half? I think this check can be done without any context, which is one of the strengths of UTF-8 as I understand.

[kevina]

@nikomatsakis, yes it can be done without any context, just check the bit pattern, see http://en.wikipedia.org/wiki/UTF-8.

[graydon]

str is not a "mixture of a string of characters and a vector of bytes" any more than an int is a mixture of a set of bits and a Pythagorean integer. A str is a unicode string in its most common and practical encoding, UTF-8.

We expose the encoding because it matters for a lot of operations, and the str APIs should be byte-oriented because that's much faster than counting characters. If you're worried about accidentally grabbing the middle of a UTF-8 code sequence, do as @kevina suggests and just take a look at the bit pattern of the boundary. Assert that you're not starting or stopping with a byte that has 10 as its high bits. UTF-8 is very well-designed for byte-access.

Programmers working in this sort of language are mature enough to know what UTF-8 is and accept its structure, just as they do the structure of int, float, pointers, and various other memory-resident entities. This is not a language of pure abstraction; concrete details matter.

We can (perhaps should) add a module wstr that deals with the other sometimes-desirable encoding [char], that is, a vector of UCS4 codepoints. I doubt anyone aside from "those interacting with the win32 API" will want UTF-16, the other monstrous encoding you see in the wild. By far the most common (and practical) encoding is UTF-8, so it's what we chose for our str representation.

As far as this being "unsafe" for slicing, you can always pass an invalid index to any vector-slice operator, say past-the-end or such. Bytes have nothing to do with it. You could decide to "eat errors" by wrapping around the string or something (is a silently-eaten error an error? very philosophical) but you could equally make up some kind of error-eating treatment for UTF-8 like "start at the next char boundary". I don't like error-eating behavior and would prefer to just tell programmers when they make mistakes.

[brson]

If string operations are byte-oriented without verifying that they are maintaining a utf-8 invariant, then it won't be true that strings are utf-8 encoded. They will be vectors of bytes that are usually utf-8 encoded.

[marijnh]

As mentioned above, all it takes is a very cheap assert during slicing to maintain the invariant of UTF-8 encoded content.

[killerswan]

Some of the changes I've been making have been geared towards keeping pairs of functions, such as:

• len / len_bytes,
• find / find_bytes,
• slice / slice_bytes, and so on.
  I also want both rindex / rindex_bytes and substr / substr_bytes, though they aren't there at the moment.

I'll gladly flip (len, len_bytes) to (len_chars, len), etc., or put one set into a submodule. How does str::bytes::find or str::chars::find look?. Having the byte access in the [] operator and bytestring functions will continue to be useful, but I imagine wanting to avoid thinking about bytes most of the time.

The exported stuff in str::unsafe, however, has its days numbered, especially given that we can, as you're suggesting, export less reliable but still trustworthy versions of those.

I have a high tolerance for a large vocabulary of functions, so long as they can be named properly...

[jruderman]

The assert can be made even cheaper by putting it in typestate, and giving find_bytes a postcondition that that the index it returns is a valid offset into the string.

[marijnh]

How does str::bytes::find or str::chars::find look?

No, no. This isn't what I intended -- we should be using chars as things to look for and act on, almost always, and a single set of operators is probably enough (fast paths can be baked in for when arguments are <128). Just the offsets that are returned should be byte offsets, with a few utilities to convert between byte and char offsets for the (rare) cases where you need characters (say, counting the # of chars between two byte offsets).

[killerswan]

Now I see what you meant. OK.

[kevina]

I agree completely with both @graydon and @marijnh. The only suggestion I would add is to consider making the type for the byte offset distinct and maybe opaque. Something like:

enum byte_offset = uint;

would do it.

[brson]

Are there specific things we can address here for 0.2? This upcoming release is intended to stabilize some core APIs (to whatever degree we can), and core::str is a big one. Does flipping the char/bytes versions of the functions such that the bytewise versions are the default solve the bulk of the problem?

[marijnh]

Not really. I'll spend some time on this tomorrow.