Hacker News Reader

Comment by munchbunny | Hacker News Reader

The decision to make C strings null terminated with implied length instead of length + blob continues to trip us up, 30+ years later. There's a good reason the "safe" versions of those functions all take length parameters. But way back when this approach was chosen, I don't think the state of the art could fully predict this outcome.

But also, "strings" and "time" are actually very complex concepts, and these functions operate on often outdated assumptions about those underlying abstractions.

View on HN

I would argue that C's fundamental mistake (well, more like limitation due to hardware of the time) was allowing arrays to decay to pointers; arrays hold valuable type information (the length!) that is lost once converted to a pointer.

C99 came so very very close with VLAs. You can declare a function like:

  int main(int argc, char *argv[argc]) { ... }

But C99 requires the compiler to discard the type annotations and treat the declaration as equivalent to:

  int main(int argc, char **argv) { ... }

Imagine a world where the C string functions were declared as:

  char *strndup(s, n)
    const char *s[n];
    size_t n;
  {
    /* now we can do sizeof(s) and bounds checking! */
  }

(You'd have to use K&R style declarations to get around the fact that the pointer argument comes before the length argument, alas.)

Edit: and then C11 made VLA support optional, since the feature didn't get used much, because the feature was only half-baked to begin with... sigh.

It's because to get that to actually work you need dependent types. Which—it's not gonna happen.

But the caller to strnlen() has already provided both the (pointer to the) array and the length! Note that C99 does permit declaring a VLA in the body of the function:

  char *strndup(size_t n; const char *s[n], size_t n) {
    char buf[n];                /* alloc a temporary VLA */
    assert(sizeof(buf) == n);   /* yep! */
    assert(sizeof(s) == n);     /* nope, sizeof(s) == 1 */
  }

So there's absolutely no reason (other than being in violation of the C99 specification) for the compiler to refuse to let you make the assertion that sizeof(s) == n.

And given the prototype for this VLA-enhanced strndup(), a smart C compiler could catch errors like this:

  char * bugged_func() {
    char buf[20];
    /* do stuff with buf, e.g. snprintf() into it */
    return strndup(buf, 30);    /* error: 30 > sizeof(buf) */
  }

Since of course within a function the C type system is already tracking the size of an array -- so no additional type information is required, and certainly not dependent types!

With standard VLAs, you always have a guarantee of being able to access sizeof(buf) bytes from buf, for any variable buf. With your syntax, that guarantee would no longer hold, unless c had dependent types that could prove said guarantee.

Well, given that C is fundamentally about separate compilation and external linkage, most "guarantees" in the language are really just promises or contracts. As demonstrated in david2ndaccount's comment, standard C already handles VLA function arguments just fine (without any need for dependent types).

The only issue is that C99 insists that the first dimension of an array argument must decay to a pointer, discarding the associated type information of that array's dimension.

We wouldn't need to go all the way to dependent types, which would guarantee at compile-time that array accesses are safe. Even if all the bounds checking happened at run-time it would still be tremendously helpful.

Bounds checking can be done, and it doesn't need any special language features. Tcc does it, as do some of the sanitizers (present in gcc and clang).

Can you bounds check dynamically sized arrays? For example, a function that receives the size as a separate argument?

    double f(double *xs, int n){
        return xs[g()];
    }

Yes. In my hypothetical world where the C compiler makes use of the VLA declaration in the function arguments, it would certainly be possible for the compiler to insert automatic bounds checking in this case:

  double f(xs, n)
    double xs[n];
    size_t n;
  {
    size_t _tmp0 = g();   /* temporary var created by compiler */
    assert(_tmp0 < n);    /* bounds check inserted by compiler */
    return xs[_tmp0];
  }

The key to making this possible is telling the compiler about the relationship between double* xs and size_t n; once the compiler has the knowledge that the type of xs is double [n] (array of double with first dimension n) it would be able to automatically insert dynamic bounds checks.

> dynamically sized arrays

Yes. What you can't do is associate bounds information with some specific pointer to an array, but this will work, for instance:

  int *x = malloc(2 * sizeof(int));
  x[1]; //ok
  x[2]; //runtime error

See WalterBright's 2009 blog post, C’s Biggest Mistake, about exactly this.

https://digitalmars.com/articles/C-biggest-mistake.html

Ah, indeed! Thanks for the link.

I think many of the "safe C" variants get tripped up by starting with fat pointers (length + pointer as an atomic value) and then have trouble (rightly so!) when trying to squeeze them through the C standard ABI; it's a square peg in round hole sort of situation.

The key observation from WalterBright's post is that the C standard ABI already has a way to pass fat pointers, using a pair of arguments (size_t and char *) in an ad-hoc manner.

It's the not-useful-but-legal C99 VLA declaration in the function prototype that could, if one is willing to violate the C99 spec, allow a compiler to automatically derive a fat pointer inside the body of a function in a manner that is backwards-compatible with the C standard ABI.

What you want works, you just used the wrong syntax:

    #include <stdio.h>
    
    void foo(int len, const char (*str)[len]){
        printf("%zu\n", sizeof(*str));
        printf("%.*s", len, *str);
    }
    
    int main(void){
        // note: not nul-terminated
        const char text[] = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!', '\n'};
        // prints 13, then 'hello world!'
        foo(sizeof(text), &text);
        return 0;
    }

Why yes, yes it does! I did know (but seem to have forgotten) that it's only the first level of array-ness that decays to a pointer.

It's unfortunate that the resulting VLA-enhanced function is no longer compatible with the original:

  /* original function */
  void foo(size_t len, const char *str);
  /* compatible signature but str[] decays to sizeless pointer */
  void foo(size_t len, const char str[len]);
  /* allowed but signature is no longer compatible with original */
  void foo_improved(size_t len, const char (*str)[len]);
  /* (this is how the non-VLA caller would see the signature) */
  void foo_improved(size_t len, const char **str);

So what your example does show is that existing compilers already support this concept (no need for fancy dependent types) but the C99 standard explicitly prohibits compilers from acting on the VLA information contained within the const char str[len] declaration.

It wasn't a limitation due to hardware of the time. It was a deliberate choice due to C's ancestry as a derivative of B.

In B, thee was only one data type: machine word. The actual meaning was determined by the operators used on it. Thus, given x, (x + 1) would be integer addition, but *x would dereference it as a pointer (to another word). There was no need to distinguish between integer and pointer arithmetic, because their semantics was the same - pointers were not memory addresses of bytes, but of words, and thus (x + 1) would also mean "the next element after x", if x is actually a pointer.

When it came to arrays, B didn't have them as a type at all. It did have array declarations - but what they did was allocate the memory, and give you a variable of the usual word type pointing at that memory (which could be reassigned!). Thus, arrays "decayed" to pointers, but in a broader sense they did in C.

This all works fine on machine where everything is a word, and only words are addressable. But C needed to run on byte-addressable architectures, hence why it needed different types, and specifically pointer types to allow for pointer arithmetic - as something like (p + 1) needs to shift the address by more than 1 byte, depending on the type of p. But they still tried to preserve the original B behavior of being able to treat arrays as pointers seamlessly, hence the decay semantics.

BTW, this ancestry explains some other idiosyncracies of C. For example, the fact that array/pointer indexing operator can have its operands ordered either way - both a[42] and 42[a] are equally valid - is also straight from B. A more obvious example, the reason why C originally allowed you to omit variable types altogether, and assumed int in that case, is because int is basically the "word type" of B, and thus C code written in this manner very much resembles B. And then there's "auto" which was needed in B to declare locals because there was no type, but became redundant (and yet preserved) in C.

https://en.wikipedia.org/wiki/B_(programming_language)#Examp...

For reasons that were never clearly articulated, the prefix approach was considered odd, backwards, and to have numerous downsides, at least where I learned C. In hindsight, I can only cringe at that attitude. Strings as added in later Pascal, about 40 years ago now, were memory safe in a way that C strings still are not.

Hey, languages used length,blob even when C was invented. HP Access BASIC used that kind.

It was a limitation, because they chose a byte length (to save space). So strings up to 255 characters only. It was decades before folks were comfortable with 32-bit length fields. And that still limited you to 4GB strings. In the bad old days, memory usage was king.

The funny thing is that you can just use the topmost bit of the length to indicate that the string length is >127, and chain as many length bytes as you want before you begin the string proper (to save space). It would be still a better encoding than a null at the end.

This way you would trade in a null-byte-terminated variable length string for essentially a null-bit-terminated variable length number (plus the remaining string). I am not convinced that this actually would be much safer.

This is just the LEB128 format, which is used commonly used and I don't think there's any serious problems with it.

Interesting. Thank you for sharing this!

At least you don't have (obvious) performance problems with it, because you will effectively never need more than 9 (usually 2 or 3) of these bytes.

But sure on modern 64 bit systems just using a 64 bit integer makes much more sense. On a small embedded 8 bit oder 16 bit microcontroller it might make sense.

You are correct, I was trying to show that such a scheme was practical even in the early 1980s when zero-termination was beginning to dominate. This could well be used on 64-bit systems (just with a larger word size than a byte), though the utility of such a thing is questionable.

Unicode does variable length bit strings too, so I'm not a visionary or anything. It would be safer for no other reason than that such a pattern could only occur at the start of the string, with zero special handling, while a null could occur anywhere in a zero-terminated string.

In a toy language I once wrote I got around that by encoding binary values as quaternary values and using a ternary system on top of that with a termination character: 11 = 1; 01 = 0; 00 = end; 10 was unused.

Having truly unbounded integers was rather fun. Of course performance was abysmal.

Pascal compilers of the time when Pascal was popular typically had a switch that disabled range checks for speed reasons.

Such a system would effectively remove that feature. Yes, you could disable range checks when indexing into a string, but you still would have to figure out how many length bytes there are. That would only be a little bit faster than a full range check.

Because of that, I don’t see how that would have been useful at the time.

The prefix approach turns the neat "strings are just character arrays are just pointers" pattern into something a lot more clunky, because now you've got this really basic data type that is actually a struct and now you have to have an opinion on how wide the length value is and short strings get a lot of memory overhead in just lengths, and so on.

In hindsight, I think the complexity is worth the safety, but I could see why it felt more elegant to use null-terminated strings at the time.

It's a classic case of moving the complexity from one part of the system to another. "Strings are just character arrays" seems simple and elegant, but in reality is a giant mess, because strings are not just character arrays, any more than dates are just an offset from an epoch.

Human concepts are inherently messy. "Elegant" solutions just shove the mess down the road.

On the contrary, I think "Strings are just character arrays are just pointers" is the solution, not the problem. As with non-character arrays, you must always pair the pointer with a length. (I don't like the idea of prefixing the length because it prevents su stringing).

The problem is the null termination, which is not general to arrays (though it is sometimes used with arrays of pointers).

You sometimes see sentinel values used with varargs (only if they're all the same type), which is basically just an array with more boilerplate.

That being said. Length as a first parameter and the rest of the arguments being the variadic bit is also quite normal.

You're just moving the complexity from strings into unsigned integers. Your strings are limited by the size of whatever you put in the head of the string.

Sure 16 exabytes sounds like a lot today, but so did 4 billion ip addresses. Differently bad is not better.

I didn’t say anything about unsigned integers, or any specific approach to encoding strings at all, so I’m not sure what you’re trying to say here.

It doesn't just buy safety. It also makes it possible to include null bytes inside of strings.

and with length+array you don't need 2 copies of so many functions (array input vs string input)

No matter how you slice it, null termination was a mistake.

This is the part that boggles my mind. It's not like fat pointers just didn't exist at the time. You need fat pointers any time you do anything with dynamic non-string binary data.

Null is always 1 byte minimum so at best you save size_t-1 bytes per string. Ignoring clever structures like LEB128 varint length.

This is a classic case of "simple is actually complex". How many billions of dollars has null terminal strings cost? Hope that 3 bytes of overhead per string saved is worth it.

Oh Pascal, why couldn't we have had you instead.

You can, it's called Delphi.

Or Nim [1]. :-) It's hard to describe succinctly, but "Pascal meets Ada meets Python meets Lisp-like syntax macros" starts to convey it. Forget operator overloading trying to square peg-round hole whatever the operator set is - Nim has user-defined operators. And a dozen other nice things.

https://nim-lang.org

"Oh Pascal" reminded me of a book titled, "Oh! Pascal!" by Doug Cooper. I used it to learn Pascal.

Best programming book I ever read. His later "Condensed Pascal" isn't quite as good -- a little too, well, condensed. Too bad that's the only one I could find to buy after having had to return Oh, Pascal to the city library.

(OK, it's hard to compare; Code Complete and other much later stuff might be just as good. Too many decades between when I read them to say for sure.)

Pascal strings are not inherently memory safe:

   cat_pascal_strings(pascalstr *uninited_memory,
                      pascalstr *left,
                      pascalstr *right);

how big is uninited_memory? Can left and right fit into it?

You need to design language constructs around Pascal srings to make them actually safe. Such as, oh, make it impossible to have an uninitialized such object. The object has o know both its allocation size and the actual size of the string stored in it.

What is unsafe is constructing new objects in an anonymous block of memory that knows nothing about its size.

C programs run aground there not just with strings!

   struct foo *ptr = malloc(sizeof ptr);  // should be sizeof *ptr!!

   if (ptr) {
      ptr->name = name;
      ptr->frobosity = fr;

Oops! The wrong size of allocated only the size of a pointer: 4 or 8 bytes, typically nowadays, but the structure is 48 bytes wide.

"struct foo" itself isn't inferior to a Pascal RECORD; the problem is coming from the wild and loose allocation side of things.

Working with strings in Pascal is relatively safe, but painfully limiting. It's a dead end. You can't build anything on top of it. Can you imagine trying to make a run-time for a high level language in Pascal? You need to be in the driver's seat regarding how strings work.

"Can you imagine trying to make a run-time for a high level language in Pascal"

You mean like the strings in Delphi? Yeah, I can since I use them daily. Strings in Delphi nowadays are actually more like classes in java than Old Pascal strings. Then depending on your intend either get them to be arrays or old strings after linker goes over your code. Best of both worlds, and on top of it, if you really want, you can definitely shoot yourself in your leg with unsafe operations. So in the end is best of both worlds and worse of 3rd world. Though the 3rd one you really need to go out of your way to have it as bad as C strings are.

I can totally imagine trying to make a run-time for a high-level language in any sensible Pascal dialect, such as Turbo/Borland Pascal. I mean, forget strings - that thing had syntax specifically to implement interrupt handlers, or access absolute memory addresses.

Better yet, how about Modula-2? I can't help but think that the programming language landscape would be much better if that language occupied the niche that C does today.

In the Pascal that I remember, strings were always 256 bytes and the first byte tracked the length, meaning they were always safe, though might get truncated. The LongString just did allocations whenever it needed, and was also safe, as long as you weren’t rolling your own pointer math.

> Working with strings in Pascal is relatively safe, but painfully limiting. It's a dead end. You can't build anything on top of it. Can you imagine trying to make a run-time for a high level language in Pascal? You need to be in the driver's seat regarding how strings work.

I doubt string representation is really the blocker here since C-strings are now pretty much just used by some but not all C programmers. QString and GString and C++ std::string and Rust strings and Go strings and Java strings and so on are not null terminated

> struct foo ptr = malloc(sizeof ptr); // should be sizeof ptr!!

This is why whenever I use sizeof, I pass a type, not a variable.

Strings as they existed in standard Pascal were extremely limited in how you could work with them, since it didn't have true dynamic arrays.

Strings as implemented in e.g. Borland Pascal were better. But then, the length-prefixed implementation had its own downsides. For example, it had to decide how many bits to use for length. 16-bit Pascal would generally use a single byte, and in BP at least, you could even access it as a character via S[0]. Thus, strings were limited to 256 bytes max - and because this was baked into the ABI, it wasn't something that could be easily changed later.

Hence when Delphi decided to fix it, they basically had to introduce a whole new string type, leaving the old one as is. And then they added a bunch of compiler switches so that "string" could be an alias for the new type or the old, as needed in that particular code file.

On platforms with limited register sets, keeping length around burns a register that could be used for something else. From the mindset of assembler programmers wanting a high level language that suits them, a sentinel that doesn't consume extra machine resources was preferable. Not to mention all the precious RAM those multi-byte lengths squander.

Ok, I hadn't considered the registers thing. That almost makes sense. Almost. But variable length arrays are so useful I think it warrants adding a register just for dealing with fat pointers.

Like I get why it happened. It is just crazy how long it has stuck around.

(Many of) The trade-offs were known to Richie et al; writing in 1993:

> None of BCPL, B, or C supports character data strongly in the language; each treats strings much like vectors of integers and supplements general rules by a few conventions. In both BCPL and B a string literal denotes the address of a static area initialized with the characters of the string, packed into cells. In BCPL, the first packed byte contains the number of characters in the string; in B, there is no count and strings are terminated by a special character, which B spelled `*e'. This change was made partially to avoid the limitation on the length of a string caused by holding the count in an 8- or 9-bit slot, and partly because maintaining the count seemed, in our experience, less convenient than using a terminator.

[…]

> C treats strings as arrays of characters conventionally terminated by a marker. Aside from one special rule about initialization by string literals, the semantics of strings are fully subsumed by more general rules governing all arrays, and as a result the language is simpler to describe and to translate than one incorporating the string as a unique data type. Some costs accrue from its approach: certain string operations are more expensive than in other designs because application code or a library routine must occasionally search for the end of a string, because few built-in operations are available, and because the burden of storage management for strings falls more heavily on the user. Nevertheless, C's approach to strings works well.

* https://www.bell-labs.com/usr/dmr/www/chist.html

He mentions Algol 68 and Pascal [Jensen 74].

Thank you (and the others) in this thread. Very insightful, particularly with what motivated the thinking then.

Thanks for the reference!

I personally don't think that the qualitative pros/cons of the chosen approach or alternatives that we're discussing today, 30-ish years later, would be all that new to the designers of C in 1993. The difference is that we've had 30-ish years to watch those decisions play out over millions of lines of code in software running at scales and levels of complexity that programmers in 1993 could only dream of.

Also, software security was barely an issue in 1993. Today, it's a massive issue.

> Also, software security was barely an issue in 1993. Today, it's a massive issue.

That was him reflecting on things in 1993, but the C team designed things in ~1970. That was basically the Stone or Iron Age of computing.

We could say that a string in C is an implicit type like a list in Lisp.

> But also, "strings" and "time" are actually very complex concepts, and these functions operate on often outdated assumptions about those underlying abstractions.

Even in safer languages such as Rust, there are often quæstions as to why certain string operations are either impossible, or need to be quite complicated for a rather simple operation and are then met with responses such as “*Did you know that the length of a string can grow from a capitalization operation depending on locale settings of environment variables?

P.s.: In fact, I would argue that strings are not necessarily all that complicated, but simply that many assume that they are simpler than they are, and that code that handles them is thus written on such assumptions that the length of a string remain the same after capitalization, or that the result not be under influence of environment variables.

> locale settings of environment variables

Also known as "why does my code that parses floats fail in Turkey?"

Also also known as the discrepancy between a string's length-as-in-bytes, its length-as-in-code-points, and its length-as-in-how-humans-count-glyphs.

Strings are hard.

Edit to respond to your addendum:

> P.s.: In fact, I would argue that strings are not necessarily all that complicated, but simply that many assume that they are simpler than they are, and that code that handles them is thus written on such assumptions that the length of a string remain the same after capitalization, or that the result not be under influence of environment variables.

I don't think I agree with that, though we may just be disagreeing on semantics. I think the big mistake many of us make is confusing two different abstractions for the same one. We've got this high level abstraction for "text" that includes issues like locale and encoding and several other things. And then we've got this low level abstraction for "text" that is just a blob of bytes. And we often mix the abstractions because it often turns out okay anyway. Otherwise we have to confront demons like "a UTF-8 string containing 10 characters can be anywhere between 10 and 40 bytes long".

> Why does my code that parses floats fail in Turkey

Because you, or someone, called

  fuck_my_program();

which is defined in "idiot.h" as

  #define fuck_my_program() setlocale(LC_ALL, "")

and the project is missing:

  #define setlocale(x, y) BANNED(setlocale)

Hope that helps!

I agreee with you but it would be much better if every locale-dependent function had an argument for an explicit locale object.

The problem is you'd have to pass an annoying extra argument (even if just a NULL) to numerous functions which have no alternative without that argument.

Technically it would be better, especially from a multi-threading point of view. The locale stuff was designed in the 1980's, before multi-threading was a mainstream technique.

Say you have a multi-threaded global server which has to localize something in the context of a session, to the locale of the user making the request.

Still, for thread support, you don't necessarily need a cluttering argument. The locale can be made into a thread-specific variable. In Lisp I would almost certainly prefer for the local to be a dynamic variable. (It would be pretty silly to be passing an argument to influence whether he decimal point is a comma, while the radix of integers is being controlled by *print-base*.)

What you want is for the locale stuff to be broken out into a complete separate library: a whole separate set of loc_* functions: loc_strtod, loc_printf, and so on.*

The threading aspect is one thing yes, but I think programmers forgetting or never realizing that these functions will magically behave differently for some of their users is a bigger problem.

I don't think having to pass a locale arguments would be that big of a problem - you could always have wrapper functions for the C locale, although they should be implemented directly for performance.

> What you want is for the locale stuff to be broken out into a complete separate library: a whole separate set of loc_* functions: loc_strtod, loc_printf, and so on.*

Yes, that would be ideal.

> Also known as "why does my code that parses floats fail in Turkey?"

I am quite certain that I have produced code that lowercases or uppercases and then checks for “i” in them, that I now realize would fail under Turkish locale settings as under that “i” does not uppercase to “I”, as one might expect.

I think 30-40 years ago it was perfectly appropriate to null-terminate strings. Every byte actually counted.

I remember thinking about setting the high bit to denote the end of string to save space.

Nowadays the binary for "hello world" might be as big as a whole operating system of the past.

(though honestly I can't recall the size of the OS on a boot floppy, but the original floppies were 160k)

Just a surreal reminder that 30 years ago was 1991. By that time it already didn't make sense to null terminate strings (except perhaps on embedded platforms).

To be fair, in 1991, 1mb of RAM was a substantial amount for a PC, so a single word per string instead of a byte per string could still add up quickly.

30+ years -> 50+ years

Funny mind thing to forget to increment counters each year.

C89 was 32 years ago, so I think saying 30+ years is fair.

Some of us learned C off of the original K&R book.

The reason that the safe functions take length parameters is that they produce a new object in uninitialized memory, a pointer to which is specified by the caller.

It has nothing to do with null termination.

And that uninitialized memory is not self-describing in any way in the C language. Which is that way in machine language also.

This is a problem you have to bootstrap yourself somehow if you are to have any higher level language.

The machine just gives you a way to carve out blocks of memory that don't know their own type or size. C doesn't improve on that, but it is not the root cause of the situation. Without C, you still have to somehow go from that chaos to order.

Copying two null terminated strings into an existing null-terminated string can be perfectly safe without any size parameters.

   void replace_str(char *dest_str, const char *src_left, const char *src_right);

If dest_str is a string of 17 characters, we know we have 18 bytes in which to catenate src_left and src_right.

This is not very useful though.

Now what might be a bit more useful would be if dest_str had two sizes: the length of string currently stored in it, and the size of the underlying storage. This particular operation would ignore the former, and use the latter. It could replace a string of three characters with a 27 character one.

Null terminated strings are remnants of an era when computers had little memory available. So, at the time it seemed smart to discard the length field and use a single byte-sized terminator (null). If you are writing an operating system for a machine with little memory to spare, this seems like a good decision. Of course things are very different now when memory is not a problem and the goal is safety.

> If you are writing an operating system for a machine with little memory to spare, this seems like a good decision.

Also registers! Especially in syscall interface, consider eg:

  int renameat(int olddirfd,char* oldpath,int newdirfd,char* newpath); /* first example I found that had 2 paths */

If you have registers edx,ecx,esi,edi,ebx available, nul-terminated strings make this fit into:

  edx olddirfd,ecx oldpath,
  esi newdirfd,edi newpath

If you need separate length fields, there simply aren't enough registers:

  edx olddirfd,ecx oldpath.ptr,esi oldpath.len,
  edi newdirfd,ebx newpath.ptr,??? newpath.len

> memory is not a problem and the goal is safety.

People keep repeating this. What about embedded systems? For instance, I have to know how an object is structured and how is allocated, exactly and without surprises. The behavior has to be predictable and as simple and fast as possible. You can (likely) achieve that with C.

Reply on news.ycombinator.com