Our website uses cookies to enhance your browsing experience.
In C++, it's good practice to place functions next to the types they operate on. To apply this approach correctly, we need to understand how name lookup mechanisms work and spot where functions can be placed without violating language rules. The article explores the topic.
The C++ language brought us many new constructs that C didn't have: function overloading, classes, namespaces, and much more, and so the language required additional rules to ensure everything worked as intended. Today, we figure out how name lookup works, focusing specifically on ADL (Argument-Dependent Lookup).
I recently wrote an article about analyzing the OpenCV project and came across an interesting code fragment. My colleagues and I couldn't immediately come up with a solution to this problem, so today we examine it in more detail.
Let's start reviewing the code.
The PVS-Studio warning: V1061 Extending the 'std' namespace may result in undefined behavior. test_descriptors_invariance.impl.hpp 195
namespace std {
using namespace opencv_test;
static inline void PrintTo(
const String_FeatureDetector_DescriptorExtractor_Float_t& v,
std::ostream* os)
{
*os << "(\"" << get<0>(v)
<< "\", " << get<3>(v)
<< ")";
}
} // namespaceExtending the std namespace violates the C++ standard and results in undefined behavior. The standard explicitly prohibits adding custom definitions to std, except for template specializations for user-defined types.
16.4.5.2.1 Namespace std
Unless otherwise specified, the behavior of a C++ program is undefined if it adds declarations or definitions to namespace std or to a namespace within namespace std.
Unless explicitly prohibited, a program may add a template specialization for any standard library class template to namespace std provided that (a) the added declaration depends on at least one program-defined type and (b) the specialization meets the standard library requirements for the original template.
The behavior of a C++ program is undefined if it declares an explicit or partial specialization of any standard library variable template, except where explicitly permitted by the specification of that variable template.
The behavior of a C++ program is undefined if it declares
— an explicit specialization of any member function of a standard library class template, or
— an explicit specialization of any member function template of a standard library class or class template, or
— an explicit or partial specialization of any member class template of a standard library class or class template, or
— a deduction guide for any standard library class template.
In the code, the regular PrintTo function is added to the std namespace, which is prohibited. However, this code is unsafe and needs to be fixed.
Someone might wonder why this code was written this way. Most likely, it's purpose to output additional debug information during GoogleTest execution. The docs suggest several ways to place the PrintTo function. In our case, the developer would like to hide the function while still making it discoverable through ADL, which we cover today. In brief, it allows a compiler to get access to the function through parameter types.
To address the problem, we should move the function to another namespace. And to understand where it will be visible, let's take a closer look at how the name lookup mechanism works in detail.
Name lookup is a set of rules the compiler locates the declaration associated with the name, including template names, namespaces, and classes. There are several types of rules, and now we'll walk through some of them.
Unqualified name lookup is used when a name does not contain the scope resolution operator :: or operators . / ->. In this case, the compiler first searches in the current scope and then moves sequentially to enclosing scopes.
The unqualified name lookup follows many additional rules, but in brief:
using;using.The lookup proceeds outward from the current namespace, but using declarations are treated as an additional path for lookup. Yet, the lookup does not start at the point whereusing is declared, but rather as if it were placed in the nearest common namespace.
Let's take a look at the example:
namespace X
{
const int a = 42;
}
// this is point of lookup
namespace Y
{
const int a = 1;
using namespace X; // this is not a point of lookup
int y = a; // which is `a`?
}Here, the y variable will be assigned the 1 value, since the a variable declared in namespace Y hides the variable with the same name from namespace X.
It's worth noting that using namespace X; doesn't import names from X into Y, but only reveals them in unqualified lookup. But it works the other way around for the using X::a construct. Thus, this code doesn't compile:
namespace Y
{
const int a = 1;
using X::a; // error: target of using declaration
// conflicts with declaration already in scope
int y = a;
}There's a similar case with classes:
class Base {
public:
int value = 10;
};
class Another {
public:
int value = 20;
};
class Derived : public Base, public Another {
public:
using Another::value;
void show() {
std::cout << value << std::endl; // which is `value`?
}
};By declaring using Another::value;, we hide the variable with the same name from Base, so the 20 value will be output.
Qualified name lookup is used when we want to specify a specific scope using the scope resolution operator :: or the operators . / ->. It "looks up" only in the specified namespace and searches for a necessary name there. Let's look at some examples of qualified lookup.
Note. The scope resolution operator only considers namespaces, types, and templates whose specializations are types.
Let's take a look at the example:
class A {
public:
static int n;
};
int main ( ){
int A;
A::n = 42; // OK
A b; // error: must use 'class' tag to refer
// to type 'A' in this scope
}In the first case, the operator :: finds the A class because it searches only among types and namespaces. The int A local variable isn't treated as a type, so it's ignored.
In the second case, the compiler reports an error: it performs basic unqualified lookup, starting from the current scope, and first finds the declaration of the int A variable, which isn't a class. This is what causes the error.
Another example:
namespace A {
namespace B {
int value = 5;
}
int value = 10;
}
namespace C {
using namespace ::A::B;
void foo()
{
using ::A::value;
std::cout << value << std::endl; // 10
std::cout << ::C::value << std::endl; // 5
}
}In the first case, we have unqualified lookup which starts in the inner scope and works its way outward. Therefore, it first finds the using ::A::value; declaration and outputs the 10 value.
In the second case, we explicitly specified that the value variable should be searched for in the C namespace, which, in turn, is located in the global namespace. The lookup starts right there and finds the using namespace ::A::B; declaration, which it then uses to find ::A::B::value.
Name lookup also checks base classes, for example:
class Base
{
public:
static const int value = 15;
};
class Derived : public Base
{
};
void foo()
{
std::cout << Derived::value; // 15
}According to the standard, we can see how two types of lookup occur here. When the Derived::value construct is encountered, the compiler first considers the Derived left-hand operand, and as there is no operator :: to the left of the name, unqualified lookup is performed. It goes from the inside out, starting at the current scope of the foo function and continuing outward to the global scope, where it then finds the required class. Once the class has been found, qualified lookup for the value data member begins within it. The Base class is the base class for the Derived, so this data member is publicly accessible in its scope.
Here again, we see a situation where variables named Derived will be ignored. This occurs when parsing the Derived::value construct, but value itself will follow the usual rules for qualified name lookup.
Indeed, this is just the tip of the iceberg. We have only covered the basic principles of qualified name lookup; the full set of rules is much more complex and extensive.
Finally, we've arrived at the mechanism that explains how to place functions next to the types for which they're intended.
Argument-dependent name lookup, also known as Koenig lookup, is an additional set of rules that extends unqualified lookup for function names with arguments. If unqualified lookup doesn't find the name, ADL will continue the search in the argument namespaces.
To leverage the argument-dependent lookup, the conditions should be met:
When all conditions are satisfied, the compiler continues lookup in the associated namespaces and classes/structures/unions for each argument:
T type or to an array of the T type: lookup will continue for T using the rules specified earlier;T data member of the X class/structure: lookup will continue for T and X using the rules specified earlier;F member function of the X class/structure: lookup will continue for parameter types, return types, and the X type using the rules specified earlier;inline: lookup continues in the enclosing namespace;X namespace that directly contains the Y namespace, declared as inline: lookup continues in the Y namespace.Let's take a peek at the example:
namespace N {
struct Data {};
void process(Data){}
}
int main() {
N::Data d;
process(d); // ok
// (process)(d); // error: use of undeclared identifier 'process'
int process = 42;
// process(d); // error: called object type 'int' is not a function
}ADL finds the N::process function, even though the N:: scope specifier isn't included in the call. This works because the search continues in the same namespace as the first argument—in the Data structure.
It's thanks to the ADL mechanism that overloaded operators work as expected. Let's inspect it with this example:
class Vector2D {
private:
double x, y;
public:
Vector2D(double x = 0, double y = 0) : x(x), y(y) {}
Vector2D operator+(const Vector2D& other) const {
return Vector2D(x + other.x, y + other.y);
}
};
int main() {
Vector2D a(1, 2), b(3, 4);
Vector2D c = a + b;
Vector2D d = a.operator+(b);
}The Vector2D class implements an overloaded + operator. The main function provides two ways to call it. The first is an implicit call, which works through ADL, while the second calls the operator explicitly through the class object. In the first case, the compiler finds the operator overload through the parameters. That is, it starts by performing unqualified lookup for the function, doesn't find the necessary overload, and then continues the search using ADL. The compiler examines the types of the a and b parameters and continues searching in the Vector2D class, where it has found the overloaded operator.
ADL is also commonly used when calling the swap function, allowing the compiler to select the correct overload. However, developers sometimes misuse it. For example, this happens in the CMake codebase:
namespace std
{
inline void swap(cmList& lhs, cmList& rhs) noexcept
{
lhs.swap(rhs);
}
}The PVS-Studio warning: V1061 Extending the 'std' namespace may result in undefined behavior. cmList.h 1322
As we already know, the behavior of a C++ program is undefined if user-defined functions are added to the std namespace. Here, we can see that a new overload of the std::swap function has been added inside that namespace.
The correct way to implement this function for a user-defined type is to declare it in the same namespace as the type itself:
class cmList
{
public:
void swap(cmList& other) noexcept { /* implementation */ }
private:
/* private data members */
};
inline void swap(cmList& lhs, cmList& rhs) noexcept
{
lhs.swap(rhs);
}But how will the compiler understand that it needs to take this function? To make this happen, the developer should call the function using an unqualified name:
template <typename T>
void foo(T &obj1, T &obj2)
{
using std::swap;
....
swap(obj1, obj2);
....
}In this example, using std::swap; makes the std::swap function available in the current scope. When calling swap(obj1, obj2); without a qualifier, the compiler will see both the standard and user-defined functions.
Another interesting pattern for using the ADL mechanism is combining it with friend functions. Let's take a closer look.
The function declared and defined inside a class with the friend keyword becomes visible only through ADL if at least one of its parameters has a type associated with that class. This allows us to closely bind the function to the class without leaking into the surrounding namespace:
namespace N {
class Data {
public:
friend void print(const Data & s) {
std::cout << " print";
}
};
}
int main() {
N::Data s;
print(s);
}In the Data class, we wrote the print friend function that will be considered as if it were declared in the nearest enclosing namespace of the Data class, i.e., in namespace N. However, since this declaration is located inside the Data class, it can only be found through this class.
Thanks to ADL, the compiler is capable of finding this function. When it encounters the print(s) call and unqualified lookup fails to locate print, at the compiler checks the namespaces associated with the type of the s argument (N::Data, N). ADL effectively "peeks" into all associated namespaces, and in this case, it discovers print inside namespace N.
Although the function is technically declared in namespace N, qualified lookup won't find it. Qualified lookup doesn't search outward from inner scopes in the same way, so the function remains accessible only through the unqualified lookup combined with ADL. That's why you can't call it like this:
int main() {
s.print(s); // error: no member named 'print' in 'N::Data'
N::Data::print(s); // error: no member named 'print' in 'N::Data'
N::print(s); // error: no type named 'print' in namespace 'N'
}If the friend function has no parameters, we'll need an additional declaration in the external namespace to access it:
namespace N
{
void print();
class Data {
public:
friend void print() {
std::cout << "print";
}
void foo()
{
print();
}
};
}Without a declaration in the N namespace, the compiler won't be able to resolve the function call—even from within the class itself
What about that example from the OpenCV project? How to solve this problem? Let's refresh our memory and take another look at the code:
namespace std {
using namespace opencv_test;
static inline void PrintTo(
const String_FeatureDetector_DescriptorExtractor_Float_t& v,
std::ostream* os)
{
*os << "(\"" << get<0>(v)
<< "\", " << get<3>(v)
<< ")";
}
} // namespaceAt the moment, the function is placed inside the std namespace, which violates the standard rules. Its visibility is ensured through the ADL mechanism: the compiler finds the function through the second std::ostream parameter, which is located in the std namespace. We need to move this function to another namespace to avoid undefined behavior.
At first, we thought about using the hidden friend function in the class that we discussed earlier, i.e., we could just move the PrintTo declaration to the body of the first parameter class. That way, the changes would be minimal: it'd also be visible only via ADL, but with no risk of causing undefined behavior.
But then things would got messy: the String_FeatureDetector_DescriptorExtractor_Float_t type isn't actually a user-defined class, but a huge havoc. See for yourself:
namespace cv
{
template<typename T>
struct Ptr : public std::shared_ptr<T>
{
// ....
};
class Algorithm
{
// ....
};
class Feature2D : public Algorithm
{
// ....
};
typedef Feature2D FeatureDetector;
typedef Feature2D DescriptorExtractor;
}
namespace opencv_test { namespace {
typedef std::function<cv::Ptr<cv::FeatureDetector>()> DetectorFactory;
typedef std::function<cv::Ptr<cv::DescriptorExtractor>()> ExtractorFactory;
typedef std::tuple<std::string, DetectorFactory, ExtractorFactory, float>
String_FeatureDetector_DescriptorExtractor_Float_t;
}
}We could place the function in the namespace where this alias is declared, but that would be pointless because the alias isn't a type, and this namespace doesn't participate in lookup. And the type of this parameter is revealed as follows:
std::tuple<std::string,
std::function<cv::Ptr<cv::Feature2D>()>,
std::function<cv::Ptr<cv::Feature2D>()>,
float>This means that lookup is performed only in the std and cv namespaces, as well as in the tuple, string, Ptr, and Feature2D classes. Therefore, this function needs to be moved from std to one of these locations.
We could move the function to the Feature2D class, but we'd have to add code to the base class that solely for testing purposes—it's hardly a clean solution, so instead we opted for the following approach:
namespace opencv_test { namespace {
class String_FeatureDetector_DescriptorExtractor_Float_t
{
private:
std::string m_str;
std::function<cv::Ptr<cv::DescriptorExtractor>()> m_extractorFactory;
std::function<cv::Ptr<cv::FeatureDetector>()> m_detectorFactory;
float m_float;
public:
friend inline void PrintTo
(const String_FeatureDetector_DescriptorExtractor_Float_t& v,
std::ostream* os)
{
*os<<"PrintTo";
};
};
}}We replaced the tuple alias with a regular class and implemented the PrintTo friend function inside it. The declared DetectorFactory and ExtractorFactory aliases are only used in this part of the program, so we placed them directly inside the class. This approach helps avoid undefined behavior while keeping the function available for calling.
If needed, we can move the function from the class to the namespace where it's nested, because now the class is used instead of the alias, and ADL will handle it correctly during lookup.
ADL can help write clearer code by allowing the compiler to automatically find the right functions based on argument types. However, like any other mechanism, it should be used correctly. Undefined behavior is no toy and can lead to bad consequences.
If you want help spotting other risky patterns in your code, PVS-Studio has you covered. You can try it on your project for free. Take care of yourself and your code!
0
0
0
85
0
0