I just ran into a thought-provoking little issue in the source code of HyperRogue, and I thought I’d share it here.

HyperRogue is quite possibly the most mind-expanding roguelike in existence. And it’s written 100% in C++! Even the web version is compiled with Emscripten. Okay, there’s about 2000 lines of Java for the Android version, but the bulk of the code — 135,000 lines — is C++.

The code’s native language is C++11; that is, it uses lots of C++11 (unordered_map, std::move, variadic templates) but it doesn’t use any C++14 features (it used one generic lambda for a while, but I submitted a patch to remove it, and the patch was accepted). So it’s C++11, and also it’s C++14.

But it’s not quite C++17.

Because it does this:

using namespace std;

template<class T> int size(const T& x) {
    return x.size();
}

And then it does things like this:

for(int i=0; i<size(cl.lst); i++)
  vptr[cl.lst[i]] = addRugpoint(shmup::ggmatrix(cl.lst[i])*C0, cl.dists[i]);

Okay, it’s C++11, but it’s not quite idiomatic C++11. It’s quite dense, and has a bit of a phobia about ranged for-loops.

But then, everyone’s codebase has its idiosyncrasies. When the end result is this good, you can’t complain too much about the author’s whitespace.

So what’s the problem?

The problem is that C++17 introduces std::size. So Clang complains:

./rug.cpp:585:18: error: call to 'size' is ambiguous
  for(int i=0; i<size(cl.lst); i++)
                 ^~~~
/usr/include/c++/v1/iterator:1584:16: note: candidate
      function [with _Cont = std::__1::vector<hr::cell *, std::__1::allocator<hr::cell *> >]
constexpr auto size(const _Cont& __c) -> decltype(__c.size()) { return __c.size(); }
               ^
./hyper.h:400:23: note: candidate function [with T = std::__1::vector<hr::cell *, std::__1::allocator<hr::cell *> >]
template<class T> int size(const T& x) {return x.size(); }
                      ^

Clang complains about 600 times:

$ git grep '[^.>a-zA-Z0-9_]size(' | wc -l
     587

So the author tried replacing using namespace std; with a list of explicit using-directives. Unfortunately, this doesn’t help. We’re getting something we don’t expect out of namespace std, but it’s not because we usinged the namespace. It’s because of argument-dependent lookup (ADL). We made an unqualified call to size, where one of the arguments was a std::vector. This unqualified call, by ADL, naturally finds any function named size in any associated namespace of the argument type std::vector (and, incidentally, also considers namespace hr, although this has been widely regarded as a bad move.)

So eliminating the using namespace std; directive is a great idea but doesn’t help at all.

Possible solutions

I thought of a bunch of alternatives.

(A), we could change the name of our size function from size to Size (or sz, or hrsize, or whatever). Update all the call-sites, and we’re done. This continues performing ADL on every call-site, but now ADL doesn’t find any functions named Size (or whatever) except for the one we intend, so we’re good.

for(int i=0; i<Size(cl.lst); i++)

(B), we could leave our size function alone, and fully-qualify every call to it:

for(int i=0; i<::size(cl.lst); i++)

This says, “Please look only in the global namespace for size” — that is, it turns off ADL entirely. So we’re good.

Minor digression: Super C++ geeks might have noticed that <: is a digraph, so that in C++03 the above code would have been parsed as a syntax error:

for(int i=0; i[:size(cl.lst); i++)

This has been fixed since C++11: <:: is a sort of a “trigraph” that overrides the usual meaning of <: in the same way as <: overrides the usual meaning of <. The underlying mechanism is similar to how C++11 doesn’t get confused by the >> in set<set<int>>.

(C), we could simply ifdef out our global size whenever we’re in C++17 mode. Then our call sites will do ADL lookup on size, and find only one candidate: std::size. So they’ll be happy. But this comes with two downsides.

First, it’s surprisingly hard to detect “C++17 mode” in this case. The system Clang on my MacBook doesn’t support -std=c++17 yet; it only has -std=c++1z, which doesn’t increase the value of the __cplusplus macro. So we can’t reliably test for __cplusplus >= 201703L. But we can work around this by adding a config macro -DUSE_STDSIZE or whatever.

Second, HyperRogue’s global function template size is not a drop-in replacement for std::size! std::size returns size_t; our global size returns int.

./rug.cpp:585:17: warning: comparison of integers of different signs: 'int' and 'decltype(__c.size())' (aka 'unsigned long') [-Wsign-compare]
  for(int i=0; i<size(cl.lst); i++)
               ~^~~~~~~~~~~~~

We could work around that by passing -Wno-sign-compare, but then we’d miss bugs. Or we could add an explicit cast to int in any of several ways:

  for(int i=0; i<(int)size(cl.lst); i++)

  for(int i=0; i<int(size(cl.lst)); i++)

  for(int i=0; i<static_cast<int>(size(cl.lst)); i++)

Notice that we’d need to add those explicit casts even in places the compiler didn’t complain. Otherwise Murphy’s Law says that we’d hit at least one instance of something like this:

auto i = size(vec);
double d = foo();
double negated_if_empty = d * (i - 1);

And we don’t want to audit all 587 call-sites looking for things like that.

(D) — an improvement on (C) — we could eliminate our global size and all its call-sites. Just inline what it would have done, in C++17 and C++11 alike.

  for(int i=0; i<(int)cl.lst.size(); i++)

This is my preferred solution, since it turns out that we can implement it as a series of mechanical replacements using sed:

sed -i -e 's/size(\*it)/it->size()/g' langen.cpp
sed -i -e 's/\([^a-z]\)size(\([a-zA-Z0-9_.:][][a-zA-Z0-9_.:]*\))/\1(int)\2.size()/g' `find . -name '*.cpp'` *.h
sed -i -e 's/\([^a-z]\)size(\([a-zA-Z0-9_.:]*->[a-zA-Z0-9_.:][][a-zA-Z0-9_.:]*\))/\1(int)\2.size()/g' *.cpp
sed -i -e 's/size(currentmap->allcells())/(int)currentmap->allcells().size()/g' *.cpp

This does introduce a lot of redundancy; for example, it rewrites

if(size(str) == 0) return 0;

into

if((int)str.size() == 0) return 0;

when a human being would have rewritten it as

if(str.empty()) return 0;

But at least it gets the thing compiling in C++17 mode without breaking C++11 mode, and we can go back and fix up individual call-sites on an ad-hoc basis the next time that particular area of the code is being worked on.

(E), we could do that ad-hoc work right now. For example, our original example

for(int i=0; i<size(cl.lst); i++)
  vptr[cl.lst[i]] = addRugpoint(shmup::ggmatrix(cl.lst[i])*C0, cl.dists[i]);

could be rewritten by hand into

for (auto ld : hr::zip(cl.lst, cl.dists)) {
  vptr[ld[0]] = addRugpoint(shmup::ggmatrix(ld[0])*C0, ld[1]);
}

with an appropriate definition of zip. (And notice that we’re ::-qualifying the call, so that we won’t have to do this whole thing over again when std::zip inevitably arrives in a future standard!)

But this is basically saying “let’s do a code audit on 587 ad-hoc call sites,” which isn’t super enticing.

Don’t do that then

In our case we actually got lucky that our code failed to compile. The absolute worst case would have been if our global size (returning a signed type) were silently a worse match than C++17’s std::size (returning an unsigned type), so that all our math silently went wrong.

Unfortunately, C++ doesn’t have a really great solution here. Future standards can add names into namespace std, which can then break your existing code’s unqualified calls by causing unwanted ADL.

The only answer I can really think of is — Don’t do that, then. Just like in my zip example above: in our C++ programs, we need to maintain a good intuitive sense for when some unqualified name (like begin, or size, or zip) is likely to get stepped on in a future standard, and avoid using that name today, even if it has not yet been stepped on. This is arguably a very unfortunate state of affairs… but it’s the state of affairs we’ve got.

Avoid making ADL calls to functions with common names.

UPDATE, 2019-05-20: LLVM/Clang just ran into the same issue with a function named apply.