4 ms·
NUL terminated strings are a great representation. We can take a suffix of a non-empty NUL-terminated string just by incrementing the pointer, which is great fo
by kazinator 7y ago
NUL terminated strings are a great representation. We can take a suffix of a non-empty NUL-terminated string just by incrementing the pointer, which is great for recursion. A pointer to a NUL is itself a valid string.
E.g. tail recursive strchr:
const char *strchr_rec(const char *str, int ch)
{
if (*str == 0)
return NULL;
if (*str == ch)
return str;
else return strchr_rec(str + 1, ch);
}
strrchr (rightmost match):
const char *strrchr_tail(const char *str,
int ch,
const char *seen)
{
if (*str == 0)
return seen;
if (*str == ch)
return strchr_tail(str + 1, str, ch);
return strchr_tail(str + 1, seen, ch);
}
const char *strchr_rec(const char *str, int ch)
{
return strchr_tail(str, ch, 0);
}
That kind of thing makes me feel that null terminated strings are the shiznit compared to some clunky header + data or whatever.
The only problem is that NUL-terminated strings are so darn easy to program with, everyone who comes into contact with them wants their share of the action, instead of using someone else's well-tested code.
As we speak, someone is likely writing yet another loop that builds up a NUL-terminated string directly, and will forget to write the final NUL in some case, or go past the end of the buffer in another.
Want to break a string into tokens on delimiters? Just overwrite the delimiters with null bytes and you're done. (Oops, the caller didn't expect their string mutated. Worse, it was a literal ...).
If you make programmers maintain a length field followed by data, or some such thing, they will quickly go off scampering for library functions to everything.
What we should never do is compare unencapsulated NUL-terminated string manipulation with the manipulation of another representation using a robust, debugged library.
Compare open-coded to open-coded, wrapped to wrapped.
- Thorrez 7y agoIs open-coded that much of a benefit over wrapped? With something like std::string_view you can take any substring without new allocations, not just suffixes.
- chrismorgan 7y agoNUL-terminated strings are a poor representation, feature-poor and directly responsible for a great many entirely avoidable bugs. I much prefer the approach used by languages like Rust, where &str and &[T] are (pointer, length) rather than just a pointer. Usage can be identical to your classic NUL-terminated string, depending on the language. (It is in Rust, with CStr.) There is only one potential disadvantage: pointers use twice as much memory; but in practice, this disadvantage is entirely theoretical. But there are several serious advantages: it lets you represent zero values (U+0000 for &str, integer zero for &[u8], &c.), take slices that aren’t suffixes (reducing either code complexity or memory usage, sometimes drastically), calculate the string length in constant time (and that’s regularly a big deal), and avoid a pitfall that has been the cause of many critical security vulnerabilities (buffer overrun). Want to break a string into tokens on delimiters? Easy, regardless of the length of the delimiter (it could be zero, two, seventeen—while with NUL-terminated strings it had to be one), without needing to worry about whether it’s safe to mutate the string.
- clarry 7y ago> You speak as though programmers scampering off for library functions to do everything is a bad thing. I consider it a wonderful thing. No, that's not what they are saying. They're just saying that to blame the representation for user mistakes and then present an alternative representation where user mistakes are prevented by library functions is comparing apples to oranges.
- chrismorgan 7y agoAh yes, I did misread it there; thanks for the correction. Line deleted, the rest stands without it.
- kazinator 7y agoPointer and length representations are available in C, and we can find programs that get them wrong somewhere. "Such and such a data structure ... in the middle of Rust" is not a discussion about string representation per se any more. Rust must have null terminated strings at some level, because it has to integrate with platforms where null terminated strings are the API currency for text. Yet, Rust programs don't fall down because of null-terminated strings. Likewise, if you have a pointer and length, but no language or library support for it, just a "high level assembly language", you will screw it up. The pointer has to point to something. There will be cases where that something is a fixed buffer on the stack or in a dynamic object. Out of a hundred programmers coding their pointer and length with fixed buffers, a good many will cause overflows, and a good many will write memory-safe code that causes consequences due to silent truncation. In C, we can cause problems like: * returning a pointer to a stack-allocated { length, ptr } structure, which turns to garbage. * leak dynamically-allocated { length, ptr } objects, or use them after freeing. * making copies of a { length, ptr } structure (e.g. pass by value), and not keeping all of them in sync when ptr and/or length are updated. * sticking a literal "string" into ptr, but then treating it as dynamic elsewhere and trying to free it * sticking a literal "string" into ptr, and then somewhere trying to modify a character.
- swiley 7y agoI love screwing around with NULL terminated strings, but doing it correctly is a lot harder. NULL and the delimiter might not be the same length if the string is UTF-8 encoded for example. IMO: if it’s not a hobby project just use a library for slicing and manipulating strings. Really you should think twice before doing it at all.