This is not a complexity issue with the function. The function is linear to the input, as it should be. The problem is that the implementation does more work then it needs to (it doesn't need the length of the string). It should be linear to the end of parsing not the end of string. The complexity in this case comes from the loops calling it.

Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements.

No, that's complete nonsense.

Here's the latest revision of the standard: https://www.iso.org/standard/74528.html

C has had a well-defined memory model since C11, I believe (re: "ordering of statements").

> ISO-C11 specifies 203 circumstances that cause undefined behaviors.

203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used.

Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11.

[1] https://resources.tasking.com/p/undefined-behaviors-iso-c-th...

> 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used.

This is hyperbole to the point of being nonsensical.

> Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11.

This sentence doesn't make any sense. If your C code has UB, it is wrong. The behavior of particular environments around certain UB is irrelevant to standards-conforming code, because standards-conforming code doesn't have UB.

> This is hyperbole to the point of being nonsensical.

I think you can only say this if you've never had aggressive compiler optimizations introduce security issues into perfectly reasonable-looking code.

Quiz, what's wrong with the following code?

    int buflen, untrusted;
    char buf[MAX];

    /* `untrusted` comes from an untrusted source */

    if (buflen + untrusted > MAX) {
        return -EINVAL;
    }

The answer of course is that integer overflow is undefined; so if buflen + untrusted is greater than INT_MAX, the compiler is allowed to do absolutely anything it wants; and making sure it's only allowed to do something sensible turns out to be extremely difficult.

EDIT For instance, in an earlier age, people might have done something like this:

    if (buflen + untrusted > MAX || buflen + untrusted < buflen)

But the second clause relies on overflow. The compiler is perfectly justified in saying, "Well, overflow is UB anyway, so if it happens, I'm allowed to not do anything; so I'll just make this code more efficient by removing that check entirely."

> If your C code has UB, it is wrong.

This goes against the sheer notion of UB. If some code was wrong, the standard would say it is not allowed and it would result in a compile error, or at least a runtime error. As it is, the language standards choose to leave it open almost as if to concede that the standard can’t cover every base. UB isn’t wrong, almost by definition. It’s just implementation specific, and that’s my point. We don’t have an overarching C language, we have a hundred or so C dialects.

One problem here is that correct code relies on valid inputs in order to avoid UB -- Undefined behaviour is a runtime property of a running program, rather than (necessarily) a static property of an isolated unit of code.

In this way, UB is essentially the converse of Rust's `unsafe` -- we must assume that our caller won't pass in values that would trigger undefined behaviour, and we don't necessarily have the local context to be able to tell at runtime whether our behaviour is well-defined or not.

There definitely are instances where local checks can avoid UB, but it's also perfectly possible to write a correct program where a change in one module causes UB to manifest via different module -- use after free is a classic here. So we can have two modules which in isolation couldn't be said to have any bugs, but which still exhibit UB when they interact with each other.

And that's before we start getting into the processing of untrusted input.

A C compiler -- and especially the optimiser -- assumes[1] that the conditions for provoking UB won't occur, while the Rust compiler (activate RESF[0]) mostly has defined behaviour that's either the same as common C compilers would give for a local UB case[2] in practice or have enough available context to prove that the UB case genuinely doesn't happen.

[0] https://enet4.github.io/rust-tropes/rust-evangelism-strike-f...

[1] Proof by appeal to authority: I was a compiler engineer, back in the day.

[2] Signed integer wrap-around is the classic here: C assumes it can't happen, Rust assumes it might but is much less likely to encounter code where there's a question about it happening.

I always though that code with UB is wrong, and UB allows implementation to deal with it on its own way (it is allowed to ignore it, stop program, corrupt memory, delete hard drive contents...).

So if your code has UB then it is wrong, one thing not specified in standard is exact consequences of that.

(yes, in some hacks one may rely on UB behaving in some way in some circumstances - it will be hack)

Suppose it is wrong, though; that implies a good chunk of C code out there is wrong code. Yet it compiles and people are using it, which means that their code does not conform to the standard. Just as wrong math isn’t math at all, wrong C is not C. People are therefore writing code whose runtime characteristics are not defined by any standard. Thus it is not actually C, it’s whatever compiler they’re using’s language.

Working and usable program typically contains wrong code of various kinds.

Nontrivial bugfree programs are extreme rarity.

> wrong C is not C

buggy C is still C, if on discovering undefined behavior people treat it as a bug - then it is just C program with some bugs in it.

If on discovering undefined behavior people treat it acceptable people treat it differently "on my compiler it does XYZ, therefore I will knowingly do ABC" then it is becoming something else.

It's not really a bug if it works as the way it was intended by the developer. It just exists in a world outside the law, makes its own laws based on what works, a renegade program. Most people don't read the C standard or care what it says (and it costs money, so it's almost as if reading it is discouraged), so it seems very likely the default human behavior is just to use this UB.

There's "implementation-defined" behavior, and then there is "undefined behavior". I think you're conflating the two.

I still think undefined behavior is the wrong choice here. It should have been implementation-defined, like what happens if you bit shift a negative integer to the right. They could pick two's complement or trap on overflow or whatever is most convenient on their platform, but not just assume it will never happen.

A good argument for compiling your debug builds with "-fsanitize=undefined".

There is always a fix for your own code but that’s not the problem. The issue is all the millions of lines of code in the wild that are intended to be compiled without that option.

Sure, or use Rust! Rust is great! We can criticize C for its faults without making baseless claims.

There is a standard, sure. But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.

> But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.

Your statement is broadly reasonable. Here's the GP:

> Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements.

It's just a string of incorrect statements, or at best, extreme hyperbole.

1. There is a C standard.

2. There's only one C language. Implementations differ, but not "completely," and are mostly interoperable. They all have in common the standard language, of course.

3. The C standard provides a fairly strong mental model for reasoning about code. Especially in later revisions, but even in C99. "Almost no ability to reason about" is false.

If you think C is fragmented or difficult to reason about, let me introduce you to Python (Python3, Jython, PyPy), Java (Oracle, OpenJDK, Dalvik), C# (Mono, .NET Core, .NET on Windows...), C++ (if you think implementing C99-C18 is hard, check out the stdlib required by modern versions of C++), etc.

You are right of course. I was thinking specifically about the early PIC Microchip compilers for "C" where the weird banked memory and Harvard RISC architecture made the "C" you wrote for those essentially non-portable even to other 8-bit micros. I think the Microchip marketing was very carefully trumpeting C but not claiming to follow any version of the standard though.

And, the of course, the community around PIC's where almost uniformly on board with writing in assembly anyway.

Don't know about C, but

In Java/C#/Python, you have a standard, a dominant implementation which is compliant to that standard. Few more independent/niche implementations which may not be 100% compliant. Do we have a similar implementation in C?

I think you're maybe overstating the degree of homogeneity in Java/C#/Python. E.g., CPython3 cannot run Python2 code at all, and there are a lot of platform-specific modules and behaviors in the stdlib ("import os"). I don't think Python has any real single standard to the level of detail that C does, although I may be mistaken.

For C, on approximately the same platforms, to approximately the same degree: either GCC or Clang would be the corresponding standard-compliant implementation.

CPython is looked to as the canonical Python. IronPython and PyPy are all modeled after it and aim to behave as closely to it as possible, while CPython is considered the gold standard. Comparing CPython3 and CPython2 is orthogonal to that; one is not trying to implement or emulate the other. You have similar situations with Mono C# imitating Microsoft C# and IronRuby imitating Ruby. If there is a difference, it is considered a deviation from Ruby which is the reference implementation.