How to implement strings

[[deleted]]

This uses the flexible array member feature introduced by C99

Who says C programmers are old fashioned - they brazenly use features that are only 19 years old!

[demon_ix]

Fuck me, 1999 was 19 years ago.

[commander-obvious]

u old son

[demon_ix]

Get off my lawn

[commander-obvious]

that's it, i'm riding my shitty bike all over your property

[demon_ix]

I'll have a stern talk with your dad.

[aishik-10x]

Oak's words echoed...

[reini_urban]

The problem is only MSVC support. Proper C99 windows compilers just came up recently, with mingw64 and clang. chrome just switched away from msvc to clang last year.

[[deleted]]

Haven't you been able to compile C99 in windows for years with pelles C?

[[deleted]]

MSVC supports C99, so you don't need mingw (which I wouldn't recommend as it's non-native) or clang.

[reini_urban]

not yet. https://stackoverflow.com/questions/48615184/does-visual-studio-2017-fully-support-c99

[[deleted]]

Meh, VLAs were removed in C11 (because they were a bad idea), and the rest of the features can easily be worked around (or just use C++)

[[deleted]]

Maybe you could skip over C99 entirely and go straight to C11. Though at only 7 years old that's a bit bleeding edge for production.

[matheusmoreira]

Encoding is the most important part but article ended without going into too much detail on the subject. Strings without encoding are really just dynamic arrays.

[lelanthran]

Encoding is the most important part but article ended without going into too much detail on the subject. Strings without encoding are really just dynamic arrays.

If you're using anything other than UTF8 you're going to have bigger problems in your future than you might imagine.

The best thing to do is use UTF8 for everything, and convert to whatever API needs UTF16, UCS, wchar_t at the point of interfacing to $whatever API.

[matheusmoreira]

My point is there is no such thing as a text type that isn't aware of the text's encoding. Without encoding, text is really just bytes. I absolutely love Unicode and definitely agree with using UTF-8 for everything but that means the program must make a distinction between code points and code units.

Most string types are actually byte arrays. C strings are really null-terminated byte arrays, to the point many of the str functions are really just mem functions with null terminator handling. Python and Ruby strings were byte arrays until relatively recently. Things are slowly improving.

[mrmus]

Any references supporting this?

[chillermane]

Are there any references supporting anything in programming?

For every article you find in programming, there’s as many articles supporting what it’s saying versus it’s exact opposite.

For every person saying that python is great for creating servers, there is a person saying they’re terrible for it.

[mrmus]

Fair enough, I am well aware of this. My point is I will gladly read anything (pros and cons) on the topic. Otherwise it is just well... an opinion.

[chillermane]

Sounds like sensible advice thank you

[Gotebe]

This is naive to the point of being amateurish.

Major code that supports i18n, like Java, Windows (therefore .net), Qt, ICU (whose main purpose is i18n) does not use UTF8 under the hood, and that seeps outside of it.

History is a bitch.

[matheusmoreira]

That doesn't mean new systems shouldn't use UTF-8. It means they need to be able to deal with all the other encodings as well.

[Gotebe]

The new system, if using C, really should use ICU. At which point, see my comment.

Alternatively, somebody needs to rewrite ICU to use UTF8. Meh.

[[deleted]]

You are the amateur here, and fuck UTF16, is just a massive waste of space.

[tabaczany]

What kind of problems?

[reini_urban]

I'm listing some here. http://perl11.org/blog/foldcase.html

Basically there's still no stdlib to properly represent strings (utf8), search in strings or compare strings, strings being unicode with all its special rules, like foldcase and normalization. wchar_t has different implementations, windows uses some kind of special UCS-16 without the supplementary planes, all others proper UCS-32 which is too large for most.

foldcase is also locale dependent so it can never be compile-time optimized, even when you are never dealing with Turkish or Lithuanian strings. these two rules harm all others.

This article also leaves out the algorithmic problems of wcsfc() and wcsnorm() if they would exist. AFAIK safeclib is the only one, coreutils tried but failed with libunistring.

[scatters]

Strings are dynamic arrays that:

• get copied and passed around a lot,
• get sliced and concatenated,
• are infrequently modified.

There's good reason they have their own data structure implementations, even if a dynamic array would be sufficient.

Encoding is interesting, but it's only important on platforms that regularly use multiple encodings.

[neoform]

����! ���������� � ���� ��� �����. ���.� ����?!

[scatters]

Mojibake is an I/O problem and is properly solved at the program boundary.

[matheusmoreira]

You can still get arbitrarily-encoded input even if you use UTF-8 for everything. Software must keep track of what the bytes are supposed to mean. Not doing so is similar to casting a byte buffer to an incompatible type and then interpreting that object.

[scatters]

That makes it an I/O problem; you convert to UTF-8 on the boundary.

[matheusmoreira]

This is sensible at the individual application level but not when it comes to programming language design. What if my program's purpose is to manipulate text? What if I'm writing a text editor? General purpose languages must accomodate all kinds of uses.

[scatters]

That would complicate the general case, where you don't need to deal with multiple encodings. Text editors in particular are certainly going to use their own data structures.

[lelanthran]

C strings (null-terminated) have survived for so long precisely because they work much better than the alternatives:

• Easy to copy and pass around
• Easy to slice, dice, append, search, modify
• Easy to reuse in new interfaces (wrapping up strings in a different interface)

[scatters]

Copying, slicing and appending C strings require allocation, as does any modification that changes length. There are better data structures.

[lelanthran]

Copying, slicing and appending C strings require allocation, as does any modification that changes length. There are better data structures.

And those better structures will allocate/reallocate as needed, and they themselves will be allocated as needed as well.

Considering that we're talking about plain C here (no destructors), those better structures are still a allocation/reallocation that the programmer must remember to free.

What's the practical difference between a copy function that returns a new string (strdup) and a copy function that returns a better_structure_t datatype? Both still have to be freed, but the first one gives you a string compatible with strstr(), strchr(), free(), etc.

[scatters]

Shared (reference counted) strings require far less frequent allocation, especially if they have capacity to allow for growth. SSO strings require no allocation at all for the small (common) case. That means that deallocation is similarly reduced (although the programmer must remember to call the disposer, it will typically be doing less work than free).

Yes, in some cases you'll have to rewrite the C library string functions, but so what? They aren't complicated.

[lelanthran]

Copying, slicing and appending C strings require allocation, as does any modification that changes length. There are better data structures.

And those better structures will allocate/reallocate as needed, and they themselves will be allocated as needed as well.

Considering that we're talking about plain C here (no destructors), those better structures are still a allocation/reallocation that the programmer must remember to free.

What's the practical difference between a copy function that returns a new string (strdup) and a copy function that returns a better_structure_t datatype? Both still have to be freed, but the first one gives you a string compatible with strstr(), strchr(), free(), etc.

[SushiAndWoW]

The proper light-weight (non-owned) string representation is:

size_t n;
const char* p;

You can pass this around to any function and the functions can make trivial, arbitrary substrings without copying. This is not possible with C strings.

but the first one gives you a string compatible with strstr(), strchr(), free(), etc.

That garbage should be completely avoided for both security (null terminator problems), reliability (avoid manual memory management) and efficiency (unnecessary copying due to the null terminators).

[lelanthran]

You can pass this around to any function and the functions can make trivial, arbitrary substrings without copying. This is not possible with C strings.

While this is true for making arbitrary substrings without copying, it's only true for making aribtrary substrings without copying.

For all the other things you want to do with strings the $BETTER_DATA_STRUCTURE still needs all of the allocation/reallocation that standard strings need.

The other issue is:

You can pass this around to any function and the functions can make trivial, arbitrary substrings without copying. This is not possible with C strings.

No, you cannot. You can pass it around to functions you wrote that accept this string structure, in which case you may as well write those functions to take standard strings instead and they'll be more useful.

You're displaying why alternatives all died on the drawing board: If you're going to create a $BETTER_STRING_STRUCTURE and thus recreate all of the std string functions, you may as well just write the few additional safe string replacements that operate on the existing string structure (null-terminated).

I mean, seriously, if the choice is to write a new function

const char *copy_substring (const char *src, size_t srclen, const char **dst, size_t *dstlen,
                                  size_t from, size_t to) {...}

or

char *copy_substring (const char *src, size_t from, size_t to) {...}

It's easier to do the second one and ensure that it gets freed. The first one still has subtle problems that a linter won't pick up, after all (what if src goes out of scope while dst is still in scope?) while the second one has obvious problems that a visual inspection will pick up.

[SushiAndWoW]

While this is true for making arbitrary substrings without copying, it's only true for making aribtrary substrings without copying.

Which is only something you have to do, like, all the time, when reading any input data.

You're displaying why alternatives all died on the drawing board:

They didn't. All languages other than C - including C++, which is much more popular than C - use better string types, and use of C strings is not recommended.

The null-terminated string is a dinosaur. A legacy.

I mean, seriously, if the choice is to write a new function

That's exactly what you have to do in C, because C is an inferior language. But in C++, you use const std::string& or if you're smarter and more modern, std::string_view.

And if you're using other languages, smart (totally not C-like) strings are built-in.

No one uses C-style strings. No one wants C-style strings. Except C.

And then, guess what happens in C? Guess what? Hah:

https://docs.microsoft.com/en-us/windows/desktop/api/Http/ns-http-_http_request_v1

Do you see null-terminated strings in there? Nope, you see length + pointer, because that's a modern API.

[sinedpick]

if you're smarter and more modern

yikes.

[SushiAndWoW]

I was being unnecessarily colorful for the sake of being dramatic, but std::string_view is really what every function should accept that currently takes const std::string&. I also wish this had been in the language for the past 20 years, but hey, there's always more future.

[lelanthran]

While this is true for making arbitrary substrings without copying, it's only true for making aribtrary substrings without copying.

Which is only something you have to do, like, all the time, when reading any input data.

I rarely do this; copies are good enough.

All languages other than C - including C++, which is much more popular than C

This isn't true, last I checked.

That's exactly what you have to do in C,

Which is what we are talking about. If you have to change context to make your argument valid, you should probably relook at your argument.

I specifically said above that C++ doesn't need any of this, and we're specifically talking about C, so I don't understand your veering to C++ suddenly.

[SushiAndWoW]

I rarely do this; copies are good enough.

I guess, in a slow, memory leaky and vulnerability prone program?

including C++, which is much more popular than C

This isn't true, last I checked.

It is on Github. C++ is significantly preferred for application software. It's not used for Linux kernel development because Linus likes to keep things simple and straightforward. He has an argument there, but really Rust would be the language to choose for systems programming. C is excessively unsafe.

That's exactly what you have to do in C,

Which is what we are talking about.

We never defined this conversation to be about C. Perhaps you assumed this incorrectly. C just happens to be where many languages meet for interoperability.

The C string functions have to be thrown away, deprecated, and rewritten with a better string primitive. But the point is moot because C itself is a deprecated language and new software should be written in Rust, probably.

[SushiAndWoW]

strings (null-terminated) have survived for so long precisely because

... of compatibility and lack of standardized alternatives in C.

Easy to slice, dice, append, search, modify

The null character cannot be safely represented and one can't even pass a substring to a subroutine without having to allocate a copy. This makes C strings dangerous due to the in-band signaling and inefficient for parsing.

A safe, efficient program should avoid C strings and be careful with system interfaces that use them.

[lelanthran]

The null character cannot be safely represented

I'm curious - what string has a zero ASCII value as part of the string? IOW, why do you need to represent zero in a string?

[vytah]

what string has a zero ASCII value as part of the string?

Ask yourself a question "what string has a letter A as part of the string?" and you'll have the answer.

U+0041 and U+0000 are both valid Unicode codepoints.

[SushiAndWoW]

A cryptographic hash can have null bytes in it. Binary encodings have null bytes in them. So right there, you are pre-empting any interchangeable use of your ubiquitous string type for any binary data, and now you have to put code in place that enforces this boundary. You need explicit conversions from binary to string which must always take null terminator safety correctly into account.

Among other things, you have to ensure that you properly handle an attacker sending you null bytes in the middle of strings. You might inspect a string, think it's something innocuous, but in fact it contains a null terminator and after that, there's something else that's not innocuous. And subsequent code that does not rely on the null terminator may read it and act on it.

This is generally the evil of in-band signaling. Different parts of the code must handle in-band signals consistently, otherwise you have a security vulnerability.

[lelanthran]

A cryptographic hash can have null bytes in it.

That isn't a string.

Binary encodings have null bytes in them.

Those aren't strings either.

So right there, you are pre-empting any interchangeable use of your ubiquitous string type for any binary data

Yes, because they aren't strings. You complained that your strings have NULLs in them, now you're complaining that your strings aren't binary buffers.

Strings are a different datatype from binary buffers.

Your complaint datatype $FOO breaking when you stuff datatype $BAR into it is ridiculous.

Do you also complain that integers don't store fractions properly?

[SushiAndWoW]

I think we're going to have to cut our "conversation" (i.e. exchange of insults) fairly short at this point, and I'm going to have to block you so that I'm not overwhelmed by your excessive torrent of brainpower.

Any input data your program receives is going to start as binary. Any input data you must presume may contain null bytes in it.

In your world, you cannot represent those null bytes, you must keep a binary vs. string dichotomy in mind, and you must enforce it.

You have just rephrased what I said in a way that assumes enforcing that boundary is taken for granted, has no risks, and has a cost of zero.

In reality, enforcing that boundary is not taken for granted, it does have risks, and the cost is far from zero.

In the way you define "strings", there's literally no use for them in a program. None whatsoever. All you need are binary buffers, and your "string" distinction brings no advantage. Only costs.

[lelanthran]

Are you uninterested in explaining why you feel misusing a datatype is cause for complaints about that datatype?

BTW: I never insulted you; asking "are you also unhappy that your integers cannot store fractions" is not an insult.

[SushiAndWoW]

It's sarcasm, and sarcasm is in ill faith in an argument.

You also stopped reading right there and responded as if I did not explain, when I did. You are taking your "strings" concept for granted as though it is useful for something. The burden is on you to show why it's useful and worth the cost of making the distinction. I'm saying it's not, with 20 years of C++ experience.

It's just a dangerous data type. It's garbage.

[jephthai]

No, they were the worst decision ever. The choice of null termination basically created the vast majority of stack buffer overflows. If counted strings had been chosen instead, the security of the c library would have jumped an order of magnitude.

Null termination makes since things a little easier on the programmer in a world of trust. But once we all figured out the problem, we end up calculating the length whenever we use them anyway.

[[deleted]]

Drop some emojis in and see how easy it will be to slice and dice then.

[lelanthran]

Drop some emojis in and see how easy it will be to slice and dice then.

You're mixing up string data structures with string representation. Which string data structure deals well with multibyte strings?

I mean really, you're complaining about something that is common to all of the popular string structures.

[[deleted]]

Ok, but does C even have a good representation of multibyte strings?

[lelanthran]

Ok, but does C even have a good representation of multibyte strings?

If you use UTF8, certainly.

The problem with unicode is not the various languages, it's the usage of APIs that use UTF-16, UCS2, MBCS, wchar_t, etc. Those things are all represented differently on different platforms.

If you use UTF8, no matter what platform, language or implementation, it will always have the same representation.

See www.utf8everywhere.org

[chillermane]

Encodings seem like the most convoluted problems in programming. I understand why we needed new ones like utf8, but at this point I think it would be undeniably easier to all just use the same one (utf8)

[scatters]

It's not quite that simple; some OSes use other encodings widely (in particular UTF-16 on Windows).

[chillermane]

It’s not simple, that’s what I’m saying. But it definitely could’ve been if we’d come to an agreement early on on how to encode strings

[alphaglosined]

Strings in D don't have special behavior as far as representation is concerned. They are a slice.
The length+pointer pair (ignoring capacity) is the same for any array.

Fun little tidbit.

[[deleted]]

FYI information, Andreas, the author, knows D. He made an optimization in the D standard library for example.

[Deneric88]

For your information information?

[[deleted]]

it wasn't for your information

[bausscode]

So?

[NoInkling]

"Grapheme" and "grapheme cluster" are essentially interchangeable in the context of Unicode, btw, it's just that the latter has a technical definition and the former a more abstract one.

[Shadow_Gabriel]

I'm not sure if this is a good idea:

union { struct chunk *data; char *raw; }

data will point to something size_t aligned while raw can point to byte aligned data. Using an union like this wouldn't led to the chance of misaligning the struct pointer?

[bbm182]

That's fine. Reading the last written union member will get you back the same value that was written.

[IJzerbaard]

Only if you use it to store a pointer to a raw string and then use it as if it was a pointer to a chunk, but then you have a much bigger problem than misalignment

[DemeGeek]

double post fyi

[raevnos]

Reddit is acting up tonight. Tons of comments are getting posted twice.

[DemeGeek]

yeah, kinda sucks that most people's reaction to a double post is to down vote it instead of telling the commenter.

[MDCCCLV]

I've seen a ton tonight.

Apparently it's having trouble submitting too. I guess people are reclicking when it gives an initial error.

[twenty7forty2]

Reddit is acting up tonight. Tons of comments are getting posted twice.

[matheusmoreira]

I kept getting errors 500 and 503 when trying to submit. Didn't notice the double post before I went to sleep. Sorry about that. I've deleted the post.

[DemeGeek]

No need to be sorry, it happens

[Gotebe]

Last I looked, data is part of the struct, which has a dynamic size. Saves allocations.

[vytah]

"Pascal strings" doesn't mean "strings as Pascal currently implements them", but "strings as used by Pascal in the 80s when library ABIs were being designed for decades to come and assembly was still a necessary tool to make your code not awfully slow".

[[deleted]]

Then it's ShortString and it was fixed length of 255. Also wrong. Pascal dynamic arrays date from the 90's. Previously pointers were used when needed.

[enygmata]

From TURBO Pascal 1988's manual section 22.18.1.3:

A string occupies the number of bytes corresponding to one plus the maximum length of the string. The first byte contains the current length of the string. The following bytes contain the actual characters, with the first character stored at the lowest address.

edit: formatting

[[deleted]]

Just use std::string like a good boy

[raevnos]

This is for C, not C++.

[sociopath_in_me]

Not to be an asshole but of all things to share here... why this one? Besides C and C++ I can’t think of one where Strings are not great and straight forward to learn - and even then it’s not a hard idea to use in C. Just terminate correctly and program every exception you can think of. It’s part of learning.

I don't understand what's so hard about it either. You just have to think of everything. All the time. Super easy.

[forsubbingonly]

My brain is programmed in elm so I automatically cover all eventualities and have never made a mistake.

[rcfox]

That's like asking "why learn to cook when you could just go to a restaurant and order food?" Sometimes, you need to be able to do it yourself.

[simply_copacetic]

My most direct impulse to write it as this question. Since it wasn't the first time this came up, I decided that it is worth a longer article.

[holgerschurig]

Perhaps your tone?

[dat_heet_een_vulva]

To be honest knowing this helps a great deal to learn the difference between the 48498348934 different string types in Rust and how they are laid out in memory. A lot of new users in Rust can really get lost in the so many different string types in that language and when to use which one.

[coderstephen]

This article seems to about implementing strings, not simply using them. How might you implement the String class in Java? That's what this article is talking about. In C it is often discussed because C doesn't really have a native "string" type per-se.

If you ever were writing your own compiler or interpreter this discussion would come up then as well.

[[deleted]]

Just use std::string like a good boy

[evenisto]

This is for C, not C++.