Lambda the Ultimate

In most existing code, unions are used primarily for data being passed through networks, files, and message passing systems. Such data, since it comes from external sources, seldom contains pointers.

I think that's true of non-discriminated unions where the union is just used for (not so portable and technically undefined) type punning. But with discriminated unions I suspect pointers in unions are pretty common.

How are you going to type strcat?

strcat is deprecated, for good cause.

strncat we can handle:
char (&strncat(char (&destination)[num], const char source[], size_t num))[num];


Except that "num" is a variable here, this is valid C++ syntax right now. (I didn't come up with that; that's the C++ standard.) The return type is the same as the input type for "destination". This maintains compatibility with the current API. Old calls will work in non-strict code. In strict mode, we might code something like this:

char dest[30] = "Hello";
char s1[] = "World";
auto ss = strncat(dest, s2, lengthof(dest)); // ss is a reference to dest
int stat = write(fd, ss, sizeof(ss)); // write to fd


Note that we have to pass the size of "dest" explicitly, just as we do now, but the compiler can check that we did it right. Probably at compile time. The compiler has to be able to verify that lengthof(dest) == lengthof(dest), and lengthof(ss)*sizeof(char) == sizeof(ss) to determine at run time that the checks are identities, are true, and can be optimized out.

Const arrays can be ambiguous as to size because there is only a risk of reading, not overwriting, invalid data. Clamping down on const arrays breaks too much existing code involving string constants. Projects writing security-critical code might want to restrict the use of the "[]" form, but making that mandatory would result in screams from the C programming community.

but making that mandatory would result in screams from the C programming community

And there you have it. You can have a new law passed sometimes under just one year affecting an entire country's people on whether they can or cannot be sent to jail based on the law's criteria applicability held in a couple sentences of the legal jargon, but ...

when it comes to just consider hard-deprecating, after decades past inception, a silly single syntax construct [or function] among hundreds or thousands [of a runtime library among thousands] of a computer language among thousands, though only used by a tiny(*) bunch of coders... the "weight of the legacy" makes for a whole different strength in its meaning.

Our curse, folks. But also an interesting challenge.

(*) (at least relatively to the expected-to be law-abiding general public population aforementioned, that is)

What are the precise semantics of an array's lengthof operator? Let's start with lengthof as applied to a C99 dynamic local array:

int n = 100;
int array[n];
n--;
assert(lengthof(array) == 100);

Does the assert fire? In a naive implementation, it would, but then lengthof(array) would not be a function that told you the length of an array! Or, you could squirrel away the value of n as (say) const int __array_lengthof - but then you're introducing hidden local variables which may not be politically correct in C.

We can extend this example to functions & structs.

void copybyref(int (&a)[n], const int (&b)[n], size_t n)
{
n--; // <== decrement n
for (int i = 0; i < lengthof(a); i++)
{ a[i] = b[i]; }
}

What happens here? Do the loops run one fewer iteration, or is the value of n on entry squirrelled away (perhaps twice, to __a_lengthof and __b_lengthof)?

Finally, the struct case, I think, ties your hands:

struct Array
{
int (&array)[length];
int length;
};

Array->length--; // <== now, surely, array is shorter?

Surely now array must be shorter, because you cannot introduce hidden constant fields into a struct? We must have lengthof(foo->array) === foo->length here, I think?

Should the length field therefore always be const (to match the const nature of the ref binding) to try to avoid some of these issues?

If C compiler wizards hang out here, I missed them. With your permission, I'll play low-key devil's advocate and just barely criticize. If you want more aggressive critical feedback you'll have to say so, because I'd rather be respectfully agreeable.

Preventing buffer overflows is a fine goal. But can static declarations give a compiler enough info to see buffer overflows? What if logic involved is quite dynamic, because you have your own memory management; it might require figuring out what complex code means to see if a write ever goes beyond the end of space you intended.

Do you only intend to detect buffer overflows in C's stack handling, rather than in user code memory management? I'm thinking: a C compiler might see where you declared space, and see you passed arguments allowing too large a write to occur, then warn you. But I can also imagine code for memory management a C compiler can't figure out, forcing it to shrug.

When you say "compatible with old code" you don't mean it compiles in old C compilers, do you? If I stick that read() declaration in a C header file and compile in my current environment, the compiler emits a message like this one:

In file included from foo.c:63:
foo.h:1234: error: expected `)' before `&' token
foo.h:1234: error: expected `;', `,' or `)' before `size_t'

I think you mean if folks upgrade their compilers, new headers will be understood and old code will still work without changes. Doesn't that make headers using new sytnax depend on new compilers?

I'll presume personal perspective is relevant and tell you how I try to avoid buffer overflow. Part of my point will be that it's not foolproof because some dynamic parts can defeat analysis. If lifetime of info describing arrays (and extents) is dynamic enough, you can't figure out whether it's stale by time of use, except indirectly.

I haven't done this recently, but I wrote a lot of scatter/gather code using clones of struct iovec, so each buffer is described by pointer and length, and arrays of iovecs are also explicitly annotated with length. (Somebody has to write such code in network stacks, and I did it for products I worked on; so if a buffer overflow happened, blame would be mine. Note I know more about software than networking.)

Using iovecs (or iovs for short) this way, one can aim to never write more bytes than a buffer describes. This works quite well, except when someone changes the iovecs while still in use, and this really happens before code is fully debugged.

Hypothetically, suppose we define an async version of readv() named areadv(), where the caller passes an iovec array as part of a request to fill those fragments of memory with the number of bytes requested. Part of the contract is this detail: until callback when complete, the caller of areadv() can neither free the iovec array nor change the size of any iovec in the array, since this would subvert the areadv() implementation. (We actually do this, but the streams are not files and the method is not named areadv(). Sometimes several coordinate systems are involved in dedup, and it gets interesting.)

Guess what happens? Sometimes the caller changes the iov_len fields while areadv() is still running, which is detected by seeing the sum of every iov_len field change between the call start and when writing is done. Naturally a fix is urgent. But how would changing C function declarations be able to find this problem's cause? I assume it's impossible, but I wouldn't mind learning otherwise.

I have trouble seeing how static analysis in a C compiler will prevent dynamic async lifetime problems with non-deterministic control flow.

But can static declarations give a compiler enough info to see buffer overflows?

Short of full proof of correctness systems, no. However, that's not what is proposed here. What is proposed is to be able to say, within the C language, how big an array is. This allows a compile time crosscheck between function caller and function callee. It allows run-time checking if desired. It allows programmers to access array size size information from within code.

When you say "compatible with old code" you don't mean it compiles in old C compilers, do you?

No. This is a proposal for a backwards compatible extension to the C language, for the next generation of the C standard.

I have trouble seeing how static analysis in a C compiler will prevent dynamic async lifetime problems with non-deterministic control flow.

Me too. Although Microsoft's Static Driver Verifier does do something comparable. However, if you were required to change the size of the object and the pointer to the buffer in one assignment or initialization operation, it would be harder to dig yourself into that hole.

To really solve thread-type async problems at the language level, you need something like Java "synchronized" or an Ada rendezvous. A fundamental problem with C asynchrony is that, while there are locks, the language has no way to say which lock locks what data. Fixing that would take the C language too far from existing C practice.

(At various times in my career, I have spent considerable effort fixing defects in asynchronous code written by others. I thus tend to take the position that one should not try to be too clever in asynchronous code.)

Now that this has been up for a few days, and no one has yet found a killer flaw, I'll say what I consider to be the major problems with the proposal.

There's an implicit style associated with this kind of safe programming. It wants you to package up your global variables into structs, with size information about those variables in the same struct. This is generally considered good programming practice today. In object-oriented languages, you're almost forced to program that way. It also wants you to declare and initialize variables at the same place, with local scope, almost in a single-assignment style. If you write that way, this proposal won't affect your programming style much.

But there are programmers, and programs, which use a large number of global variables. A long time ago, those were the people who came from FORTRAN. The style remains. There are programs with huge include files of global variables. A typical program in that style might obtain a default table size from a command line option, put that number in a global variable, and then allocate buffers accordingly. To express that safely, the pointers to those buffers need to go into a struct (not necessarily struct per buffer) so that the buffer can be tied to its size. We can't tie a size to a global non-const variable with this approach.

Arguably, what I'm proposing forces a bit of object orientation onto C programmers. There are programmers who just don't like that. It's not a performance issue; a reference to an element of a static struct is an address fixed at compile time, just like a global variable. But the programmer has to write structname.varname instead of varname, and some people will hate that.

Also, the initialization of a struct with an array of known size has to be done in a rather rigid way, so that the struct is initialized or assigned all at once. This is unnatural to people who don't think in terms of object-oriented programming. Some C programmers aren't even aware that structs are assignable.

This I see as the biggest practical problem. The people who read Lambda the Ultimate are unlikely to have trouble with these concepts, but there are many C programmers who aren't comfortable with even the more advanced concepts in C.

In response to everyone's comments, I've put up a new draft of the proposal: August draft. This looks almost ready to go out to a larger community. So I'd like to get more comments.

The main changes involve the primitives needed to use malloc in a way which is type-safe and memory-safe. Without constructors, that's a touchy area. The problem turns out to be solveable through the addition of a new built-in type, void_space, and a generic built-in function, init_space. The goal is to avoid using casts for routine operations.

I guess I frequent Ltu less often than I use to. Computer Security may have become enough of a concern (see CVE-Mitre for example) that one might be tempted to attempt to address some of these concerns at the language level.

I have a couple questions:

1) Can interprocedural analysis be used to infer the size of an array bound in a called function from the args list?

2) Could similar techniques be used for malloc, free when including type inference?

It would seem to me that if one take a liberal interpretation of C semantics one could in the worse case pass the size argument without the programmer knowing. SSA based compilers with graph coloring register allocators have already made certain keywords obselete like the register keyword.