4 ms·

In my experience it is very easy to accidentally introduce iterator invalidation: it starts with calling a callback while iterating, add some layers of indirect

In my experience it is very easy to accidentally introduce iterator invalidation: it starts with calling a callback while iterating, add some layers of indirection, and eventually somebody will add some innocent looking code deep down the call stack which ends up mutating the collection while it's being iterated.

layer8 2y ago
I can tell you that this happens in Java as well, which doesn’t have undefined behavior. That’s just the nature of mutable state in combination with algorithms that only work while the state remains unmodified.
- School-Cotton 2y ago
  Okay, but that’s the point. This is UB in C/C++, but not in Java, illustrating the fact that C and C++ have an unusually large amount of UB compared to other languages.
usefulcat 2y ago
I'm familiar with that very sort of bug, but I don't see how it's a failure of the language. To be convinced of that I think I'd at least need to be shown what a good solution to that problem would look like (at the level of the language and/or standard library).
- demurgos 2y ago
  Rust statically enforces that you have exclusive access to a collection to mutate it. This prevents also having an active iterator. You also have languages using immutable or persistent data structures in their std lib to side-step the problem.
kriiuuu 2y ago
That is not UB. That is simply mutable data. The solution here is static analysis (Rust) or immutable persistent collections.
- MindSpunk 2y ago
  Depending on your collection iterator invalidation _is_ UB. Pushing to a vector while iterating with an iterator will eventually lead to dereferencing freed memory as any push may cause the vector to grow and move the allocation. The standard iterator for std::vector is a pointer to somewhere in the vector's allocation when the iterator is created, which will be left dangling after the vector reallocates.
- pjmlp 2y ago
  In the context of C++ and STL it is UB. They are in the process of rewording such cases as erroneous instead of UB, but it will take time.
  - saagarjha 2y ago
    …what’s the difference?
    - tsimionescu 2y ago
      If it is UB, the compiler is allowed to optimize based on the assumption that it can't happen. For example, if you have an if in which one branch leads to UB and the other doesn't, the compiler can assume that the branch that led to UB will never happen and remove it from the program, and even remove other branches based on "knowing" that the branch condition didn't happen. If it's simply erroneous, then it behaves like in every other language outside C and C++: it leaves memory in a bad state if it happens at runtime, but it doesn't have any effect at compile time.
      - saagarjha 2y ago
        What exactly does "a bad state" mean?
        tsimionescu 2y ago
        A state in which memory is not expected to be based on the theoretical semantics of the program. For example, if you do an out of bounds write in C, you can set some part of an object to a value it never should have according to the text of the program, simply because that object happened to be placed in memory next to the array that you wrote past the end of. According to the semantics of the C abstract machine, the value of a non-volatile object can only change when it is written to. But in a real program, writes to arbitrary memory (which are not valid programs in C's formal semantics) can also modify C objects, which would be called a "bad state". For example, take this program, and assume it is compiled exactly as written, with no optimizations at all: void foo() { int x = 10; char y[3]; y[4] = 1; printf("x = %d", x); } In principle, this program should print "10". But, the OOB write to y[4] might overwrite one byte of x with the value 1, leading to the program possibly printing 1, or printing 266 (0x010A), or 16777226 (0x0100000A), depending on how many bytes an int has and how they are laid out in memory. Even worse, the OOB write may replace a byte from the return address instead, causing the program to jump to a random address in memory when hitting the end of the function. Either way, your program's memory is in a bad state after that instruction runs.

layer8 2y ago

I can tell you that this happens in Java as well, which doesn’t have undefined behavior. That’s just the nature of mutable state in combination with algorithms that only work while the state remains unmodified.

School-Cotton 2y ago
Okay, but that’s the point. This is UB in C/C++, but not in Java, illustrating the fact that C and C++ have an unusually large amount of UB compared to other languages.

usefulcat 2y ago

I'm familiar with that very sort of bug, but I don't see how it's a failure of the language. To be convinced of that I think I'd at least need to be shown what a good solution to that problem would look like (at the level of the language and/or standard library).

demurgos 2y ago
Rust statically enforces that you have exclusive access to a collection to mutate it. This prevents also having an active iterator. You also have languages using immutable or persistent data structures in their std lib to side-step the problem.

kriiuuu 2y ago

That is not UB. That is simply mutable data. The solution here is static analysis (Rust) or immutable persistent collections.

MindSpunk 2y ago
Depending on your collection iterator invalidation _is_ UB. Pushing to a vector while iterating with an iterator will eventually lead to dereferencing freed memory as any push may cause the vector to grow and move the allocation. The standard iterator for std::vector is a pointer to somewhere in the vector's allocation when the iterator is created, which will be left dangling after the vector reallocates.
pjmlp 2y ago
In the context of C++ and STL it is UB. They are in the process of rewording such cases as erroneous instead of UB, but it will take time.
- saagarjha 2y ago
  …what’s the difference?
  - tsimionescu 2y ago
    If it is UB, the compiler is allowed to optimize based on the assumption that it can't happen. For example, if you have an if in which one branch leads to UB and the other doesn't, the compiler can assume that the branch that led to UB will never happen and remove it from the program, and even remove other branches based on "knowing" that the branch condition didn't happen. If it's simply erroneous, then it behaves like in every other language outside C and C++: it leaves memory in a bad state if it happens at runtime, but it doesn't have any effect at compile time.
    - saagarjha 2y ago
      What exactly does "a bad state" mean?
      - tsimionescu 2y ago
        A state in which memory is not expected to be based on the theoretical semantics of the program. For example, if you do an out of bounds write in C, you can set some part of an object to a value it never should have according to the text of the program, simply because that object happened to be placed in memory next to the array that you wrote past the end of. According to the semantics of the C abstract machine, the value of a non-volatile object can only change when it is written to. But in a real program, writes to arbitrary memory (which are not valid programs in C's formal semantics) can also modify C objects, which would be called a "bad state". For example, take this program, and assume it is compiled exactly as written, with no optimizations at all: void foo() { int x = 10; char y[3]; y[4] = 1; printf("x = %d", x); } In principle, this program should print "10". But, the OOB write to y[4] might overwrite one byte of x with the value 1, leading to the program possibly printing 1, or printing 266 (0x010A), or 16777226 (0x0100000A), depending on how many bytes an int has and how they are laid out in memory. Even worse, the OOB write may replace a byte from the return address instead, causing the program to jump to a random address in memory when hitting the end of the function. Either way, your program's memory is in a bad state after that instruction runs.