Simple Dynamic Strings library for C, compatible with null-terminated strings • Hacker News Board

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#31

Post by chrchang523 » Tue, Dec 03, 2019, 5:16 PM UTC

pingyong wrote: post #10

Just looking at the API "sds" seems to just be a typedef for char* - unfortunately, that means that accidentally passing a char* as an sds into any of the functions will be instant UB and not even a compiler warning. Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). I do have to wonder though if avoidin…

My preferred approach for handling this type of scenario is to write C code that is valid C++, while adding a bunch of C++-specific mostly-compile-time safety checks which can't be expressed in pure C. It's not perfect, but it has helped me reduce the impact of footguns without sacrificing the interoperability advantages of C.

(And as other commenters have noted, wrapping the char* in a struct addresses the immediate footgun in question.)

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#32

Post by jstimpfle » Tue, Dec 03, 2019, 5:18 PM UTC

Keyframe wrote: post #22

rurban wrote: post #20

Earlier quoted context omitted.

Exactly. You should not name a buffer lib "string", when it does not support the basic unicode operations: case fold, normalize => compare, search. In utf-8 of course. I'm also missing stack allocation support, needed for fast short strings. It should be even included in sdsnew, for len < 128.

Unfortunately, yes. Limited usefulness at best without unicode support, at least to a degree. Even UTF-16 or 32 internally would suffice, treating UTF-8 only as ser/de format is good enough these days.

UTF-8 is the preferred internal storage format for most applications. The reason is space efficiency.

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#33

Post by [deleted] » Tue, Dec 03, 2019, 5:22 PM UTC

pantalaimon wrote: post #28

pingyong wrote: post #10

Just looking at the API "sds" seems to just be a typedef for char* - unfortunately, that means that accidentally passing a char* as an sds into any of the functions will be instant UB and not even a compiler warning. Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). I do have to wonder though if avoidin…

> Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). typedef struct { char *s; } sds_t; will produce an error if you try to pass a char* instead. http://codepad.org/CmrskN9n

[deleted]

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#34

Post by asveikau » Tue, Dec 03, 2019, 5:23 PM UTC

Keyframe wrote: post #22

rurban wrote: post #20

Earlier quoted context omitted.

Exactly. You should not name a buffer lib "string", when it does not support the basic unicode operations: case fold, normalize => compare, search. In utf-8 of course. I'm also missing stack allocation support, needed for fast short strings. It should be even included in sdsnew, for len < 128.

Unfortunately, yes. Limited usefulness at best without unicode support, at least to a degree. Even UTF-16 or 32 internally would suffice, treating UTF-8 only as ser/de format is good enough these days.

I don't get entirely why people want or expect to store UTF-32 in memory for any substantial period. It makes more sense to me as: if you need to process codepoint at a time, parse from UTF-8 or UTF-16 in a codepoint-at-a-time fashion, leaving only ~1 codepoint decoded at a time.

People seem to think that 1 codepoint = 1 integer frees you from thinking Unicode is hard. But 1 codepoint is not 1 glyph. You have combining characters, zero-width joiners [used also in emojis], RTL markers, Han unification, probably more. So you can't really think of a Unicode string as a random-access, one-glyph-per-unit type of thing in any encoding.

So I hope when people say "UTF-32 support" they mean "decode UTF-8".

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#35

Post by antirez » Tue, Dec 03, 2019, 5:27 PM UTC

pingyong wrote: post #10

Just looking at the API "sds" seems to just be a typedef for char* - unfortunately, that means that accidentally passing a char* as an sds into any of the functions will be instant UB and not even a compiler warning. Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). I do have to wonder though if avoidin…

One of the main points of the library is the ability to pass SDSs where char* is expected without doing anything. So this is a "feature" in the author's spirit.

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#36

Post by faragon » Tue, Dec 03, 2019, 5:27 PM UTC

I wrote a library with similar functionality, also with variable-size header (smaller header for small strings, and bigger when growing). With both heap and stack allocation support (contiguous memory for headers and data), Unicode interoperability, and even data compression. Eventually I added support for other data types (vector, map, hash map, set, hash set, bit set). The SDS/SDS-2 is more suited for production, and this is not for recommending mine instead, but if someone wants to check a different implementation looking for ideas (BSD licensed, too):

https://github.com/faragon/libsrt

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#37

Post by electrograv » Tue, Dec 03, 2019, 5:34 PM UTC

chacham15 wrote: post #25

pingyong wrote: post #10

Just looking at the API "sds" seems to just be a typedef for char* - unfortunately, that means that accidentally passing a char* as an sds into any of the functions will be instant UB and not even a compiler warning. Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). I do have to wonder though if avoidin…

What you do is something like the following: typedef struct sds_s { char data[0]; } sds; Which makes them essentially equivalent, but not from a type perspective. Then to handle conversions, you add explicit functions a la char* sds_cstr(sds *str); Then you have full type checking to help you (and an additional advantage if your data format changes).

The downside to using a non-inlined conversion function is that (1) it will be slower than just accessing the member directly, and (2) it’s much more verbose.

Why not just use the member explicitly? This way, converting a STS string into a legacy C string could be as simple as writing “.cstr” (or if you just be as terse as possible, it could be defined as “.s” as another poster suggests).

In this case, compromise of increased code verbosity is extremely minor at worst (just a few characters). At best, this extra explicitness can actually be seen as a good thing for code readability (not to mention the huge benefits we’re discussing of type safety).

So the question then is: Why doesn’t SDS do this? The actual library uses a regular C typedef (which is unsafe for the reasons described above).

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#38

Post by electrograv » Tue, Dec 03, 2019, 5:39 PM UTC

antirez wrote: post #35

pingyong wrote: post #10

Just looking at the API "sds" seems to just be a typedef for char* - unfortunately, that means that accidentally passing a char* as an sds into any of the functions will be instant UB and not even a compiler warning. Considering this is C, there is no way to prevent this easily since you can't express a type that is one-way convertible (i.e. sds -> char* ok, char* -> sds not ok). I do have to wonder though if avoidin…

One of the main points of the library is the ability to pass SDSs where char* is expected without doing anything. So this is a "feature" in the author's spirit.

As another reply has suggested, you can design the wrapper struct so you can simply write:

  legacy_fn(my_text.s);

Versus the current:

  legacy_fn(my_text);

I don’t think saving two characters per legacy function call is even remotely worth the loss of static type safety (which risks serious memory corruption and/or security holes, which are entirely preventable at compile-time in this way).

In fact, I even find the explicitness more pleasantly and clearly readable: I like being able to know at-a-glance when types are changing, especially in a language as unsafe as C.

Lastly, if you can tolerate just using some of C++‘s features, you can define a no-compromise solution: A type (still represented by a single pointer under-the-hood) that will implicitly convert (with zero runtime cost) into a C string but not vice versa.

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#39

Post by dho85 » Tue, Dec 03, 2019, 6:02 PM UTC

aidenn0 wrote: post #29

paulsmith wrote: post #13

There is also Better String Library, similar self-contained library with C-style string compatibility: http://bstring.sourceforge.net/

TFA specifically names what is different between SDS and libraries like bstring: > Normally dynamic string libraries for C are implemented using a structure that defines the string. The structure has a pointer field that is managed by the string function, so it looks like this: struct yourAverageStringLibrary { char *buf; size_t len; ... possibly more fields here ... }; > SDS strings as already mentioned don't follow…

What the page doesn't really acknowledge is that its "single allocation with a prefix" design is significantly more dangerous than the "separate struct" design. Particularly in that it's incompatible with the address sanitizer.

Re: Simple Dynamic Strings library for C, compatible with null-terminated strings

#40

Post by adrianmonk » Tue, Dec 03, 2019, 6:04 PM UTC

> This is achieved using an alternative design in which instead of using a C structure to represent a string, we use a binary prefix that is stored before the actual pointer to the string that is returned by SDS to the user.

I'm not convinced of the advantage in returning a char* to the user.

I see how it's convenient to be able to use all the built-in and other functions that accept a char* as an argument, like printf() or your favorite logging library.

BUT, you can only use the ones that treat the string as read-only. (You can't use strncat(), etc.) And you have no protection against messing this up.

Seems like a better trade-off would be to have a user-visible type that isn't char, then a user-visible function that converts that to char when you need it.

So instead of this:

    /* sds is just a typedef to char* */
    sds mystring = sdsnew("Hello World!");
    printf("%s\n", mystring);
    sdsfree(mystring);

You'd have a function like this:

    /* get read-only C-style string from an sds */
    const char *sdsC(const sds s);

And code like this:

    /* sds is its own distinct type, not another name for char* */
    sds mystring = sdsnew("Hello World!");
    printf("%s\n", sdsC(mystring));
    sdsfree(mystring);

Yes, it's more keystrokes, but surely the safety is worth it considering it is only needed when bridging a compatibility gap. (Also, possibly the sds functions could be a tiny bit more efficient if they aren't always doing conversions on their arguments.)

(I do like the idea of putting header and characters into one struct. That's probably good for efficiency compared to a struct that points to a buffer and gives the system a layer of pointer indirection to go through.)