4 ms·
I just want you to know that I find your comments to be interesting, they're really forcing me to find words for why I wrote the function this way! Oh, and igno
by saagarjha 5y ago
I just want you to know that I find your comments to be interesting, they're really forcing me to find words for why I wrote the function this way! Oh, and ignore 'userbinator; I'm pretty sure I understand their point but they know better than to be expressing their views like that.
Anyways, to address your points: I suspect we are reading this function at different "levels". You see it as a mess of mutation and increment operators, but it is written that way on purpose! The reason for this are the "idioms" I mentioned above. You might be aware of some in C already, like
struct foo f = { 0 };
To someone who is unfamiliar with the syntax this is can be confusing: "it's assigning 0 to the struct…what?!" Logically, this zero-initializes the first member of the struct, then implicitly zero-initializes all the other members. But an experienced reader isn't going to read it like that, they're going to read it like "clear out the struct"–they could probably tell you how the C standard makes this work and why this is better than memset, but in their brain when they read it they just know the idiom " = { 0 }" and what it does without going through all that. Similarly, in functional languages you might see code like
let product = [1, 2, 3, 4].fold(*)
which computes the product of all the numbers. Again, someone can explain how the whole thing works, and * is a binary operator that is being coerced into a closure argument, or whatever, but at some point you just see ".fold(*)" and think "product". At some point you may even prefer seeing ".fold(*)" over
var product = 0
for i in [1, 2, 3, 4] {
product *= i
}
because it's concise and doesn't leave room for error (did you spot the bug? I've done this more than once. It's easy to find and fix, but still, hopefully it illustrates how these kinds of things happen.) Now, with that in mind, we have some idioms in my code. These are what they are:
while ((*dst++ = *src++));
I "know" this idiom as a strcpy. I also "know" that the loop invariant on this is that dst and src always point to the next character to copy: this is true at the start of the loop, while it's running, and at the end except at that point you're done copying so you don't want to run this loop anymore. I don't futz around with the increment operators, I just have internalized this to be true and read it as such. Similarly,
while (--len);
is just an idiom to run a loop len - 1 times (I made a typo in the first reply, heh). At the end len is zero because it's also the condition. With that done, I think the algorithm I implemented becomes clear:
1. If the buffer has no space, return early. (You can see this is a special case bailout–you'll see why it exists in just a second.)
2. Do a strcpy. But, before we copy any character, we need to also check to make sure you haven't run more than len - 1 times (Why? Again, see below). This check actually has to happen "first" so put it in front of the &&, to make sure we bail before writing a character.
3. Ok, so the loop is over. Since we have two conditions, this means there are two possible cases: either we hit the limit, or we finished copying the string. Actually there are three, since both could happen at once. If len is zero we ran out the buffer, so we need to null-terminate. Because we got rid of that pesky empty buffer case at the beginning, and we've copied len - 1 bytes, we have a guaranteed invariant here: we need to write one last NUL byte, and we have the space for it. Because we used the strcpy idiom, we know that dst has been pointing at the next spot to write to all this time, so we use it now. And src is pointing at the next character we want to write, so it lets us conveniently fill that case where the string fits perfectly, because we can figure this out from the input. The other side of the if is simpler, we simply finished copying without problems, so we can return dst as-is.
Ok, that was a lot of words, but when I am reading it these stuff just comes automatically. This is why I brought up correctness: readability and correctness go hand-in-hand here. The readability principles you bring up are generally good ideas, but I chose to eschew them here precisely because the idioms give much powerful invariants that I think they are just more readable. Your function breaks out of the middle of a loop to ensure it doesn't overrun the string, mine just naturally rolls it into the loop condition. Your program increments dst past the end, goes "whoops", then goes back and writes in the NUL byte; mine only moves forwards and ensures that dst points to the place I want to write next from the moment the function starts all the way to the points of return. There is one edge case where I don't write a NUL (which 'saurik also noticed because he also tried to implement this function), but I bail out of that one immediately so the rest of the function can assume that it can write to the end of the buffer.
So, in summary: I know how the increment idioms work. I don't see loops or mutation or side effects, I see the code as "this is the high-level thing that this sequence of characters will do", and then I structure my function around it so that the guarantees I know it can provide apply to my program.
- dataflow 5y agoThanks for fleshing this out. Before I address the larger point, lemme just mention one thing regarding the Your program increments dst past the end, goes "whoops", then goes back and writes in the NUL byte bit: it's not really going "whoops", it's just (a) copying everything except the null terminator, then (b) tacking on the null-terminator. The reason I bring this up is that your characterization actually misses the single most important aspect of that code. Notice that in your own implementation, it's not obvious in the last branch whether the buffer will end up null-terminated or not. To infer that, the reader will have to jump around the code while performing the following mental gymnastics to execute the program backwards: (a) !!len == true in the final branch, (b) therefore --len > 0 earlier, (c) therefore that condition was inactive in the loop, (d) therefore the loop terminated because of the other condition (i.e. because dst had a NUL written into it), (e) therefore therefore dst is NUL-terminated because it is not advanced afterward. I'm not saying people can't do this, but it requires people to focus on the code and concentrate to figure it out. It's essentially a puzzle they need to solve, and that's before maintenance. There's no indication to the maintainer that this logic is implicitly there, so you're really just hoping that every step of this multi-step chain stays intact during maintenance. Contrast this with the index-based solution, where it is blatantly obvious that the returned string is NUL-terminated... the return value is &dst[i] and the very line before it literally tells you dst[i - 1] = '\0' when i > 0! So you can verify the most important property of that function by simple inspection. So now that I have that out of the way, regarding your larger point: what you're saying is essentially "this is a composition of well-understood primitives", i.e. the primitives are while (--len) and while (*dst++ = *src++) and your brain "parses" them as the high-level operations they are, and then simply reads them as compositions of those high-level operations, rather than as a bunch of pointer manipulation operation. I guess it explains why you wrote it this way (thanks for that). What I'm saying is that when you force yourself to combine primitives like this, the solution ends up being more complicated than it needs to be. If you still don't see this the same way, imagine what the logical continuation of what you're saying would be for n >= 2 primitives: while (--len && (*dst++ = *src++) && *++ptr && (*foo-- = *bar--) && ...) ; Surely at this point it's obvious that the whole is more complicated than the sum of its parts, right? Maybe one way to see it is that the composition of these n primitives doesn't just have n termination conditions; it has an exponential number (at least 2^n) of them. That's objectively exponentially worse. The only way you (or or your future reader) can dismiss differences in each of those states is by actually spending time analyzing the structure of the problem beforehand; it's by no means a given for an arbitrary problem. And n = 2 isn't exempt from this complexity growth. Stepping back a bit, and this is a little bit tongue in cheek, but I'm reminded of a joke that seems kind of relevant... it's been years, but if I recall, it went something like this: A mathematician and an engineer are presented with a problem to solve. Each of them is separately brought into a kitchen, where they see a curtain catching fire. They're asked to put it out. They think for a while, frantically looking around for something useful, and suddenly see there's a pot of water boiling on the stove. They look around, find some mittens, grab the pot, and dump the water on the curtain to put out the fire. The next day, they're asked to put out a similar fire again, except this time the stove is off. The engineer sees the pot of water, starts looking for a mitten, but then notices the stove is off. So he just picks the pot up with his bare hands and dumps the water on the curtain. The mathematician instead just notices the stove is off, then turns it on to boil the water so he can finish the rest of the problem with the solution he figured out yesterday. It's exaggerated, but I think a similar idea applies here. Essentially, you don't want to treat everything like a nail just because you have a hammer. Even in a hypothetical world where we could assume the primitives are perfect in isolation and your composition is 100% guaranteed to be bug-free code, this kind of "have idioms -> will use" approach to writing software would merely be guaranteed to give correct code with an upper bound on the required complexity. It would by no means guarantee the final solution is anywhere as simple or readable as it could or should be for that problem, and in this case, IMHO it just isn't.