The One-Definition Rule

We have been hit by the same bug twice already this year. It ends in a crash, and it took developers days to find it (in each case), even though it is reproducible on each run of unit tests. The code, after significant simplifications, looks like this:

namespace tests
{
  struct Fixture
  {
    std::vector<int> v1;
    std::vector<int> v2;

    static Fixture create();
  };

  TEST_CASE(test1)
  {
    auto fixture = Fixture::create();
    std::cout << "running test1";
  }
}

We are using a unit-testing framework that uses certain clever techniques, so that by only declaring the test, we are also registering it for being run. With this, anything related to testing one piece of functionality is neatly confined to a single file.

The problem is really not with macros. They basically expand to quite a simple construct, where the test is executed during the initialization of a global object. After further simplifications, the code looks like this.

namespace tests
{
  struct Fixture
  {
    std::vector<int> v1;
    std::vector<int> v2;

    static Fixture create();
  };

  // expanded from macro TEST_CASE(test1)
  struct UTF_test1_runner
  {
    UTF_test1_runner();               // test run here
  };

  UTF_test1_runner UTF_run_test1 {};  // init of a global

  UTF_test1_runner::UTF_test1_runner()
  {
    auto fixture = Fixture::create(); // test contents
    std::cout << "running test1" << std::endl;
  }
}

After the test contents have been run, the program crashes when the destructor of fixture is in progress. Can you see why?

It is hardly possible that the problem is in the implementation of a constructor or a destructor, because they are all compiler-generated. We cannot see the definition of function Fixture::create as it is defined in another file. So, it looks like the first culprit. But its definition, if we look at it, is in fact quite harmless:

Fixture Fixture::create()
{
  return Fixture{};
}

The bug is hard to track, because it cannot be observed by looking at one file. Not only is it difficult to humans. Also static analyzers that work on single translation unit at a time cannot observe the problem. The problem is in another file, also performing unit tests:

namespace tests
{
  struct Fixture
  {
    static Fixture create();
  };

  Fixture Fixture::create() { return Fixture{}; }

  TEST_CASE(test2)
  {
    auto fixture = Fixture::create();
    std::cout << "running test2" << std::endl;
  }
}

It also defines class Fixture, in the very same namespace tests. But with different members. But why should this be a problem?

By default, unless you make an effort to specify otherwise, compiler assumes that each class or function defined in a normal namespace (like namespace testing or namespace std or the global namespace) is meant to be used by anyone in the program, not necessarily in the current .cpp file (or translation unit). In more technical terms, by default, each class or function symbol in a normal namespace has external linkage. Anyone who wants, or also by accident, can link with them.

There is also a contract in C++ between you (the programmer) and the compiler. If a program contains more than one definition of a class (and also of an inline function, or a function template) with external linkage, all these definitions should be identical.

It might sound strange: this contract implies that we can legally have more than one definition of a class with the same name in the program. But this is what we often (perhaps even without being aware of it) need and do. This is exactly what happens when you put the definition of your class in a header file and then include this header in two .cpp files. Because of how the header inclusion works in C++ (by copy-and-paste), this renders the situation where the two .cpp files define the same class. There is no other way in C++ to share class definitions between files; therefore the compiler must accept the repeated definition of a given class in different files, but on provision that you do not try to do nasty tricks, like changing the definition of the same class from file to file. You are only expected to include the same header file in each .cpp file. Anything other than that is risky.

If you are willing to play by the rules, the fragile header inclusion model works in C++, and the compiler can safely assume that even if you provide the definition of the same class in another file it will be the very same definition as that seen (or to-be-seen) in another file, so it can pretend that there is in fact only one definition, but repeated in a number of files. It can just pick one and use it all around.

And this is exactly what happened in our example. When compiler observed that a function Fixture::create returns an object of type tests::Fixture in the second file, an empty class, it trusted the programmer to fulfill his part of the contract, that it will be the same tests::Fixture as in the first file. So, it generated code for constructing copying and destroying an empty class.

But when it compiled the first file, it observed the definition of tests::Fixture that contains two vectors. It assumed (from the same contract) that in the second file, it will always create, copy and destroy two vectors, so in the destructor of tests::Fixture it tries to invoke two destructors of vectors which were never there. And this causes memory access violations.

The compiler worked on the assumptions which, under the contract of One-Definition Rule, it is allowed to make. It was the programmer who violated the contract. But you might ask, if violating this contract has so severe consequences why is compiler not checking the programmer’s part of the deal? The reason is performance. We mainly choose C++ because we care for our programs’ performance. But often it is also the performance of the process of building our program that we must consider. Performance measured not only in terms of time, but also in memory consumed. If the process of the compilation of translation units alone has a linear complexity, the input size being measured in the number of translation units and the number of declarations inside them, the process of linkage has quadratic complexity. Making it even bigger, might make the linkage ineffective.

Precautions

The above example illustrates only one of many potential problems caused by the One-Definition Rule (ODR) violation. We have seen that it can cause a memory access violation, which on many systems causes an application halt. And this is perhaps one of the best things that can happen to you, because you and the user are immediately informed that something needs to be fixed. In general, the ODR violation is defined as undefined behavior, which in practice means that if we have two different definitions of the same function (or a member function) in the program, compiler is free to chose any of them at any place the name is used. This means a program may be invoking a different function than you think.

To avoid these problems one has to stick to one simple rule. Unless it is your intention to expose your function or class to everyone in the program, declare it with internal linkage. Having internal linkage means that a given function cannot be accessed from another translation unit, even if this other translation unit tries to use the same name. You do it by putting your declarations in an anonymous namespace. Thus, the fixed unit-test example looks like this:

namespace tests
{
  namespace
  {
    struct Fixture
    {
      std::vector<int> v1;
      std::vector<int> v2;

      static Fixture create();
    };
  }

  TEST_CASE(test1)
  {
    auto fixture = Fixture::create();
    std::cout << "running test1";
  }
}

The rule is simple: either a name is for everyone (and declared in a header file) or is translation-unit-local in an anonymous namespace.

Some technical details

If I fix the problem from this post like in the last example, I will start getting linker errors that function tests::<anonymous>::Fixture::create is declared but never defined. It is an improvement, because I am alerted by the problem by the linker rather than the end user.

In case of our bugs, the problem was somewhat different and more fascinating. Function create was defined inline in two translation units:

namespace tests
{
  struct Fixture
  {
    std::vector<int> v1;
    std::vector<int> v2;
    static Fixture create() { return Fixture{}; }
  };
}

Inline functions are subject to the same ODR violation problems as classes. I did not show it like this in the post because in a small example the problem with the crash does not appear any longer. This is one of the aspects of undefined behavior: you are not guaranteed that something will be wrong. Instead, I used my knowledge of Clang and GCC to fabricate an example that is quite easily reproducible. I think it is still convincing. Unit tests are the place where people often keep repeating the same names, like Helper.