Defective Language

The Infernal Loop Iterator

Collection iteration is perhaps the most insidious language construct. Simple to create and easy to understand. Yet lurking within lies the ability to create random non-local defects. Monstrous bugs that you’ll spend hours, if not days, trying to find, if you even notice them.

Here is a prime example of a defective loop, found in the source of my Leaf compiler. It’s in C++, but rest assured the same problem code can be written just as easily in any language.

1
2
3
for( auto & mb : all_blocks ) {
    complete_block( mb );
}

In the general form this code is not safe. It doesn’t matter if you are using the above form, explicit iterators, or manual indexing. Which items the loop itself iterates depends on the behaviour of complete_block. What happens if all_blocks is modified within the loop? The interplay between the language specification, the type of collection, and exact manner in which it is changed, is complex enough that we might as well consider it undefined.

Why it’s undefined

Let’s first give an expanded view of the loop to better see what is happening.

1
2
3
for( auto iter = all_blocks.begin(); iter != all_blocks.end(); ++iter ) {
    complete_block( *iter );
}

This is the form that ultimately all loops take. There is an iteration variable that starts at the beginning of the collection. Each iteration steps to the next location. Once the end is reached the iteration is stopped.

It breaks if complete_block modifies the collection. But not always. Many C++ container operations have the property of “invalidating iterators”: after such an operation any iterator to the container is invalid, and using it results in undefined behaviour.

For example, inserting a value into a vector may invalidate iterators. This is required since the iterators may actually be pointers to a location in memory. If inserting a value into the collection causes reallocation, those pointers are left pointing to the old location. Accessing such a pointer is undefined.

Traditional syntax can skip or duplicate elements

The traditional loop syntax doesn’t have exactly the same problem. It won’t have invalid iterators but it may skip or duplicate elements.

1
2
3
for( int i=0; i < all_blocks.size(); ++i ) {
    complete_block( all_blocks[i] );
}

When a new item is inserted into the collection the loop does one of two things. If the value is inserted prior to the current index, the current value will be pushed to position i+1, and then used again in the next loop operation. The newly inserted value will not be iterated. If the value is inserted after the current position it will simply be iterated and no issue arise.

When the current item is used after complete_block a strange mismatch can occur. If a value was inserted or deleted, it’s not longer certain to which element i refers. It could even be past the end of the collection and result in undefined behaviour.

1
2
3
4
for( int i=0; i < all_blocks.size(); ++i ) {
    complete_block( all_blocks[i] );
    something_else( all_blocks[i] );
}

Always undefined, even if safe

Now let’s use an example from Python.

1
2
for mb in all_blocks:
    complete_block( mb )

I really have no idea what happens if all_blocks is modified by complete_block. I know from a few situations that my code doesn’t crash, but that’s it. I choose Python for this reason only: that I don’t know. Other than for C++ it’s about the level understanding I have for all languages. To be fair, in C++ the rules are so complex that I generally have to assume I don’t understand it either.

Even if the above is entirely safe, it doesn’t crash nor corrupt memory, it’s uncertain what should happen. If the all_blocks container is modified, should new elements also be iterated? If an element is removed should the iteration just cover the remainder of the collection? Or maybe the iteration should just raise an exception of its modified status. I really can’t think of a sane behaviour.

Just don’t do it…

The only safe solution is to never modify a container will iterating it. If modification is unavoidable then a copy of the container must be created prior to iteration. This is a common pattern I have in my code.

1
2
3
4
5
std::vector<block> dup;
dup.swap( all_blocks );
for( auto & mb : dup ) {
    complete_block( mb );
}

This only works though because I have a queue-like collection here. It won’t work in all cases. Indeed, there are several ways to handle modification within the loop. Each depending on the circumstances. This is kind of disconcerting since every loop in your program may end up looking different.

Finding a solution assume we know there is a problem. For tight loops performing a minimum of operations it can be clear. But if complete_block is a complex operation then it’s simply too difficult to know. So long as all_blocks is not a local variable then it can modified somewhere else.

It’s also possible that when you first wrote the loop it was fine. Later a colleague changes the behaviour of complete_block to modify all_blocks. They don’t even know about your loop and thus are unaware they are introducing a defect.

The solution

The overhead of having to duplicate the collection to iterate is often undesired. But I repeat my last point, unless you can guarantee it isn’t modified in the loop, it isn’t safe to loop directly. One language that has potential here is Haskell. By using the monad system you can actually track the side-effects done by a function. However, so many functions will be marked IO (meaning they modify global state) that we end up in the same situation quite quickly.

Immutable containers are another approach. If the container can’t be modified there is never a problem with a loop. Attempting to work with immutable containers is however a challenge all on its own.

I once tried a locking container solution. To iterate requires a lock on the container. No modifications can be done so long as a lock is held. It worked. Errors were unfortunately not detectable at compile-time, but at least at run-time I got nice clear exceptions about the problem. The biggest problem is that suddenly I lost access to all the standard containers and iteration syntax. It was too much of a burden to use this approach. I think it is a good approach, but it really requires full cooperation from the language.

At the moment we’re left with one of the fundamental programming constructs being terribly unsafe. I have tracked a lot of defects to such loops. I bet that most applications have this issue lurking in at a least a couple of their loops. It’s hard to detect and hard to avoid. If you have ideas on how to address this problem, then please let me know.

23 replies »

  1. You could iterate over a proxy that could read the original container, but would throw errors on attempts to add/remove/reorder elements. This would be the obvious thing to do in Lua, for example. It might be possible to make a C++ template that would create a correctly typed proxy for any given container. With such a C++ template, you might even be able get compile time errors, and use the various C++ iteration syntaxes.

    • The problem comes in trying to enforce accessing thr container strictly through the wrappers. It’s not just the person iterating that has to behave, but all the code in the entire program that might touch that collection.

    • Note the problem is that the called code has a reference to the data via some other mechanism. It is either part of the same class isntance, a global variable, in some cache, or otherwise. Thus a const-pointer at the point of iteration won’t help.

    • This is precisely what is enforced in Objective-C for NSFastEnumeration (for in) and block (closure-based) enumeration over a mutable container from the standard library. An exception is thrown if the underlying container is changed during iteration.

      Of course you’re still free to use nextObject to step through them and the C-style for loop at your own peril.

    • If the check is only done during enumeration you still aren’t protected from the `something_else` example. Though you are definitely far better off, and will most likely find the defect quicker.

  2. Rust provides the guarantee that the iterator won’t be modified in the loop, without giving up mutability. This is necessary for it to prevent reference invalidation in general since it has lightweight references without garbage collection, like C and C++.

    • It prevents reference invalidation in general, and iterators are built on references. You can have any number of usable immutable references to an object, but only one mutable one. Lifetimes of variables and the references to them are an enforced part of the type system. It needs this to provide memory safety without requiring garbage collection.

      Mutable tagged unions / sum types are another easy way to hit this issue in C++ (boost::variant, boost::optional) since changing the stored type will invalidate any references.

    • I see I messed up the original comment. I meant to say that the *container* can’t be modified in the loop, since the iterator causes the compiler to statically ‘freeze’ it until immutable references are no longer going to observe changes to it.

    • What happens when an attempt to modify a frozen container is made?

      I like the approach of freezing the container.

    • In most Rust code, the compiler is either aware of an object’s single unique owner or has a reference to it. An immutable references implies that it is immutable (frozen further up the stack) while a mutable one has the guarantee of being the single usable handle for that object.

      Shared ownership is explicit via the Rc and Gc types, and they’re immutable by default. The RefCell type provides dynamic mutability by throwing a failure (catchable at a task boundary) on a violation of the single non-aliasing mutable reference invariant.

      http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

  3. To be honest I have no idea how a function that takes a single index (or iterator) of a container can change the container. If the function accesses the container through some global reference (or both the function and container object are members of a class) this is just bad practice.

    I have seen a lot of code where a simple and innocent-looking function taking 3 parameters turned out to be a monster modifying global state in non-trivial way through global variables. This taught me a lesson: a function should access stuff only by its parameters. If a (member) function needs to modify a container at some index, it should get the index and the container as parameters. This is how I came to preferring non-member functions. I even think implementing member functions in terms of non-member functions just for the sake of making it clear what the function accesses makes sense.

    This of course doesn’t fix the original problem, but at least makes it apparent:

    for( auto & mb : all_blocks ) {
    complete_block( all_blocks, mb );
    }

    If all_blocks is taken by a non-const reference, it is clear that this loop is not safe.

    • The issue commonly comes up with state machines. The variables aren’t necessarily global, but contained within a class. So the variable `all_blocks` and the function `complete_block` are part of that same class. This is how the function gains access to the collection.

      The collection is maintaining some list of things to be done, or the state of several objects in the class (the state machine).Since processing may lead to changes of the state it’s normal that this contained collection is modified.

      Another example I had once is connection management. I had several client connections maintained in a list. The server was threaded, but dealing with thread safety was relatively easy. The problem was that a few places needed to iterate over the list of client connections. It simply wasn’t possible to lock the collection during iteration. The solution there was to use shared_ptr and take copies of the list each time a loop was needed. There was a cost overhead, but no other solution was found.

  4. The following is wrong:
    > for(auto iter = all_blocks.begin(); iter != all_blocks.end(); ++iter) {
    > complete_block( *iter );
    > }

    From ISO C++11 Standard 6.5.4.1, this is what you get:

    > {
    > auto && __range = range-init;
    > for ( auto __begin = begin-expr, __end = end-expr; __begin != __end; ++__begin ) > {
    > for-range-declaration = *__begin;
    > statement
    > }
    > }

    The main difference is that end is computed only once, when entering the loop.
    It is a subtle but important difference since it assumes that your range’s end remains constant.

    Pushing back elements to a vector with enough capacity within the loop doesn’t mutate the range you took, since the new elements are appended outside from this range. Invalidating your range within the loop is, however, not a good idea, since it results in undefined behavior.

    • Yes, you have the correct expansion. I did not wish to complicate the article here by showing the full c++ expansion. The reduced form communicates roughly what is happening. In either form, my short form, or the proper form, the same types of errors can happen — though manifest slightly differently.

      The problem with iterator invalidation rules in C++ is that they are distinct for each collection and it depends not only on which operations are called, but the internal state of the collection as well. I don’t expect programmers, myself included, to have to remember all those details.

    • Some other points
      – in the next loop, you can also write:
      for(std::size_t i = 0, e = v.size(); i != e; ++i) { …}
      to achieve the same effect as above.

      > The only safe solution is to never modify a container will iterating it.
      > […]
      > It’s also possible that when you first wrote the loop it was fine. Later a colleague changes the behaviour of complete_block to modify all_blocks. They don’t even know about your loop and thus are unaware they are introducing a defect.
      > […]
      > If you have ideas on how to address this problem, then please let me know.

      Modifying the container is fine. What you shouldn’t do is invalidate iterators.

      The best solution to this is to be a const nazi. In C++11 const means thread-safe (or free of observable side-effects). Use const member functions, const references, and you’ll be fine. I also syntactically distinguish between const and non-const member functions by appending an underscore at the end and making them private:

      private:
      std::vector vector__;
      public:
      auto vector() const { return vector__; }
      private:
      decltype(auto) vector_() { return vector__; }

      If someone wants to modify the vector, or get non-const iterators,
      they have to write for(auto i& : vector_()) instead of for(auto i& : vector()) or do
      a const_cast which is even more explicit.

      Furthermore, remember that const is transitive, so even if someone tries to change the code to do something unsafe, that person will need to either cast or remove const all the way through the chain.

      It is not as good as Haskell, but if you use const everywhere, these errors that you are mentioning just don’t show up since it is impossible to forget that you are doing something wrong when you have to write const_cast.

    • A const reference/pointer/iterator can still be mutated through an alias. It doesn’t mean that the data it points at is immutable – only that it can’t be modified through *that* reference.

      I think most of these reference invalidation bugs are going to occur when you’re invalidating the reference by writing through *another* variable/field.

  5. int x = 5;
    int &a = x;
    const int &b = x;

    concurrent_read(a);
    concurrent_write(b);

    The concurrent_read function takes const &int, but is still going to have a data race. This a somewhat contrived example, but stuff like this is incredibly common when you’re using shared_ptr. You may have a const reference into it, but it doesn’t mean that reading is thread-safe.

  6. In languages like Haskell, the language syntax makes working with immutable collections pretty painless. So in the (unsafe) assumption you were starting a new project from nothing, that’s one way to handle it.

    Also with Haskell, the best practice is to keep the use of the IO Monad as small as possible. So for a trivial example instead of five different functions that each print output or send data over a socket, you would have four functions that assemble the data to print or send out and one function that takes the data and prints it or sends it over a socket.

    I am not a Haskell expert, just a novice – so it’s possible that in practice most Haskell code ends up with IO Monad in use everywhere. But in theory, that’s how you’re supposed to keep the subset of your code that works with global state small.

  7. The problem is that the simplest loop of reading/writing to/from a stream involves the IO monad. So while there are definitely some cases which can be fixed, the general case is still left unresolved.

    • Right. The general case can never be resolved. The idea behind Haskell – and I’m not sure I am totally onboard with it, but I understand the basic advantages – is to use immutable data structures, use a very flexible but tight type system, and restrict your code that interacts with the rest of the world to the smallest feasible subset of your application. A disk failure or network connection disruption or out of memory error will still crash your application, as easily as it crashes something kludged together by a total newbie in any programming language. But for many other common classes of errors, you’re safe.

      That may be the best it’s feasible to do in any language.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s