Add a usable string type to the standard library about wybe HOT 6 CLOSED

I would recommend using sds, but then I realized that it might be conflict with the GC. SDS returns a shifted pointer to user.

from wybe.

What I had in mind was a rope type, with four constructors:

• Empty string (maybe we could do without this one)
• C string (null terminated), with its length
• A concatenation of two strings
• A slice, consisting of a string, an offset to the start, and a length

In addition, once the language supports the ability to ensure a structure is unaliased, it would be good to add a fifth constructor:

• A string buffer, which is basically the same as a slice, except that it also knows the size of the buffer, and allows concatenation by copying into the buffer.

Sds looks good for C, where everything is done by mutation, but I don't think it would be so good for wybe, where we usually can't mutate. This type allows constant time substring and concatenation.

from wybe.

I had a quick look at immutable stings in python and go. I think we only need string buffer and slice, maybe merge them into one data structure. I don't think it's necessary to have "a concatenation of two strings". As far as I know, the most common update on string is appending to the end. That will create a unblanced tree structure and cause other operations to be inefficient.

The concatenation is done by copying into the buffer. The buffer size is increased by a factor every time it's full. The only exception is that the string is a slice then we need to make a copy.

from wybe.

But a string buffer is not immutable, so to handle this for Wybe, we would need to introduce new low-level instructions that have a destructive flag, like the existing mutate, and generalise the destructive update transformation to modify them, too. That's probably a good idea anyway, but designing and implementing a generalisation of mutate is a research project of its own. Until then, the string buffer approach will require copying two whole strings for every concatenation.

from wybe.

That is true. I personally prefer having a nice and simple minimum working version (MVP), then optimize it when we actually hit the bottleneck (so we will have some benchmarks at that time). I think one of the current problem is lack of read function?

from wybe.

Sure, simple is good. But I think in Wybe, having separate constructors for concatenation and substring probably is simpler than copying strings around (even though there's an LLVM intrinsic to do the actual copying).

One nice thing in Wybe is that constructors can be reimplemented as functions, and vice versa, without changing callers, so it can be relatively easy to change our minds later about the implementation.

from wybe.