Как далеко видит lookup в C++?

• Проблема
• Name lookup
  • Unqualified name lookup
  • Qualified name lookup
  • Hidden friend
• Решение
• Заключение

Хорошей практикой в C++ считается размещение функций рядом с типами, для которых они предназначены. Однако, чтобы такой подход работал корректно, важно понимать механизмы поиска имён и знать, где можно размещать функции, не нарушая правил языка. Рассмотрим эту тему подробнее.

Язык C++ принёс нам довольно много новых конструкций, которых нет в языке C: перегрузки функций, классы, пространства имён и многое другое. В связи с этим добавилось ещё больше правил, благодаря которым всё это и работает. Сегодня предлагаю разобраться, как работает поиск имён — в частности поиск имени по аргументам.

Проблема

Недавно я писала статью про проверку проекта OpenCV и наткнулась на интересный фрагмент. Мы с коллегами не смогли сходу предложить решение этой проблемы, поэтому сегодня предлагаю разобрать её подробнее.

Приступим к изучению кода.

Предупреждение PVS-Studio: 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)
    << ")";
}
} // namespace

Расширение пространства имён std является нарушением стандарта C++ и ведёт к неопределённому поведению. Стандарт явно запрещает добавление собственных определений в std, за исключением специализаций шаблонов для пользовательских типов.

Здесь же в пространство std добавляется обычная функция PrintTo, что недопустимо. Такой код опасен, и его следует исправить.

Возможно, у вас возник вопрос, зачем была написана такая конструкция. Скорее всего, этот код служит выводом дополнительной отладочной информации при тестировании с использованием GoogleTest. В документации предлагается несколько способов размещения функции PrintTo. В нашем случае разработчик хотел спрятать функцию, но при этом обеспечить её видимость через механизм ADL (Argument-Dependent Lookup), о котором мы сегодня поговорим. Если кратко, то он позволяет сделать функцию доступной для компилятора через типы параметров.

Чтобы исправить проблему, нужно перенести функцию в другое пространство имён. А чтобы понять, в каких местах её будет видно, предлагаю рассмотреть подробнее механизм поиска имён.

Name lookup

Поиск имён — это набор правил для поиска используемого имени, включая имена шаблонов, пространств имён и классов. Различают несколько типов правил для поиска имени, некоторые из которых мы сейчас рассмотрим.

Unqualified name lookup

Неквалифицированный поиск имён используется, когда имя не содержит оператора разрешения области видимости ::, операторов . или ->. Поиск начинается с текущей области видимости и последовательно движется к внешним областям.

Поиск содержит много дополнительных правил, но схематически можно представить его такой последовательностью:

• поиск в текущем и внешних блоках, включающий поиск в пространствах имён, импортированных через using;
• поиск в текущем и базовых классах, включающий поиск в пространствах имён, импортированных через using.

Поиск идёт изнутри наружу от текущего пространства имён. Однако using обрабатывается как дополнительный путь поиска. Причём поиск будет начат не в том месте, где написан using, а так, будто бы он написан в ближайшем общем пространстве имён.

Пример:

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`?
}

Здесь переменной y будет присвоено значение 1, так как объявленная в namespace Y переменная a перекрывает переменную с таким же именем из namespace X.

Стоит учитывать, что using namespace X; не вносит имена из X в Y, а лишь делает их видимыми при неквалифицированном поиске. Но это работает наоборот, если мы говорим про конструкцию using X::a. Поэтому такой код не компилируется:

namespace Y
{
    const int a = 1;
    using X::a; // error: target of using declaration 
                //        conflicts with declaration already in scope

    int y = a;
}

С классами похожая история:

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`?
    }
};

Объявление using Another::value; перекрывает переменную с таким же именем из базового класса Base, поэтому здесь будет выведено значение 20.

Qualified name lookup

Квалифицированный поиск имени включает в себя указание конкретной области видимости, при которой используется оператор разрешения области видимости ::, операторы . или ->. Он "заглядывает" только в указанное пространство имён и ищет там подходящее имя. Рассмотрим некоторые примеры квалифицированного поиска.

Примечание. Оператор разрешения области видимости учитывает только пространства имён, типы и шаблоны, специализации которых являются типами.

Пример:

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
}

В первом случае оператор :: находит класс A, потому что ищет его только среди типов и пространств имён. Локальная переменная int A не рассматривается как тип и игнорируется.

Во втором случае возникает ошибка: компилятор использует обычный неквалифицированный поиск: он начинает с текущей области видимости и первым находит объявление переменной int A, которая не является классом. Из-за этого и возникает ошибка.

Рассмотрим другой пример:

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
  }
}

В первом случае происходит неквалифицированный поиск, который идёт изнутри наружу. Поэтому первым он находит объявление using ::A::value; и выводит значение 10.

Во втором случае мы явно указали, что переменную value нужно искать в пространстве имён C, которое, в свою очередь, находится в глобальном пространстве имён. Поиск начинается сразу там и находит декларацию using namespace ::A::B;, с помощью которой находит ::A::B::value.

Так же поиск учитывает базовые классы, например:

class Base
{
  public:
  static const int value = 15;
};

class Derived : public Base
{ 
    
};

void foo()  
{
  std::cout << Derived::value;    // 15
}

Согласно стандарту тут происходит комбинированный поиск. Когда встречается конструкция Derived::value, сначала в рассмотрение идёт левый операнд Derived. Так как слева от имени не находится оператор ::, то выполняется неквалифицированный поиск. Он идёт изнутри наружу от текущей области видимости функции foo до глобальной и уже там находит нужный класс. После того как класс был найден, в нём начинается квалифицированный поиск поля value. Класс Base является базовым для Derived, поэтому в его области публично доступно это поле.

Здесь же мы опять видим ситуацию, при которой переменные с именем Derived будут проигнорированы. Это происходит при парсинге конструкции Derived::value, однако сам value будет соблюдать обычные правила квалифицированного поиска.

Разумеется, это лишь верхушка айсберга. Мы рассмотрели лишь основные принципы работы квалифицированного поиска, полный набор правил значительно сложнее и объёмнее.

Argument-dependent name lookup

Наконец мы подошли к механизму, который и объясняет, как размещать функции рядом с типами, для которых они предназначены.

Поиск имён, зависимый от аргументов, называемый ещё поиском Кёнига, — это дополнительный набор правил, расширяющих неквалифицированный поиск для имён функций с параметрами. Если во время неквалифицированного поиска имя не было найдено, то он продолжится в пространствах имён их аргументов.

Чтобы использовался поиск, зависимый от аргументов, должны соблюдаться следующие условия:

• неквалифицированный поиск не нашёл подходящего имени;
• функция вызвана с аргументами;
• имя не заключено в скобки.

Когда все условия выполняются, поиск продолжается в связанных пространствах имён и классов/структур/объединений для каждого аргумента:

• если это встроенный тип, то никакие дополнительные пути поиска не добавляются;
• если это класс/структура/объединение, то поиск будет продолжаться внутри этих сущностей, в их базовых классах/структурах (для производных классов), в обрамляющих классах/структурах (для вложенных классов), а также в их обрамляющих пространствах имён;
• если это специализация шаблона класса/структуры/объединения, в дополнение к правилам поиска в классах/структурах/объединениях он будет продолжаться для типовых аргументов шаблона (type template arguments), а также в пространствах имён и классах, где объявлены шаблонные аргументы шаблона (template template arguments);
• если это перечисление, то поиск будет продолжаться в обрамляющем пространстве имён. Если перечисление объявлено в классе, то поиск будет продолжаться в этом классе;
• если это указатель на тип T или на массив типа T, то поиск будет продолжаться для типа T при помощи указанных ранее правил;
• если это функция, то поиск будет продолжаться для типов параметров и возвращаемого типа при помощи указанных ранее правил;
• если это указатель на нестатическое поле T класса/структуры X, то поиск будет продолжаться для типов T и X при помощи указанных ранее правил;
• если это указатель на функцию-член F класса/структуры X, то поиск будет продолжаться для типов параметров, возвращаемого типа и типа X при помощи указанных ранее правил;
• если это функция, имеющая перегрузки, то поиск будет продолжаться для каждой перегрузки при помощи указанных ранее правил;
• если это вложенные пространства имён, то поиск продолжается только в указанном, без включения вложенных;
• если пространство имён найдено поиском и было объявлено как inline, то поиск продолжается и в обрамляющем пространстве имён;
• если пространство имён X найдено поиском и напрямую содержит пространство имён Y, объявленное как inline, то поиск продолжается и в пространстве имён Y.

Пример:

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 находит функцию N::process, хотя при вызове не указан оператор области видимости N::. Это работает, потому что поиск продолжается в том же пространстве имён, что и первый аргумент — в структуре Data.

Именно благодаря механизму ADL работают перегруженные операторы. Рассмотрим на примере:

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);
}

В классе Vector2D реализован перегруженный оператор +. В главной функции приведены два способа его вызова. Первый — неявный вызов, и работает через ADL, а второй — явный, через объект класса. В первом случае компилятор находит перегрузку оператора через параметры. То есть он начал искать функцию неквалифицированным поиском, не нашёл нужной перегрузки, поэтому продолжил поиск с помощью ADL. Он посмотрел на тип параметров a и b и продолжил поиск в классе Vector2D, где и нашёл перегруженный оператор.

Кроме того, механизм ADL часто используют для вызова функции swap. Это необходимо для того, чтобы компилятор выбрал нужную перегрузку. Но иногда разработчики делают это неправильно. Например, как было в коде проекта CMake:

namespace std
{
  inline void swap(cmList& lhs, cmList& rhs) noexcept
  {
    lhs.swap(rhs); 
  }
}

Предупреждение PVS-Studio: V1061 Extending the 'std' namespace may result in undefined behavior. cmList.h 1322

Как мы уже знаем, поведение программы на C++ не определено, если в пространство имён std добавляются пользовательские функции. Как видно в примере, новая перегрузка функции std::swap была добавлена внутрь этого пространства имён.

Правильный способ реализовать эту функцию для пользовательского типа — объявить её в том же пространстве имён, что и сам тип:

class cmList
{
public:
  void swap(cmList& other) noexcept { /* implementation */ }
private:
  /* private data members */
};

inline void swap(cmList& lhs, cmList& rhs) noexcept
{
  lhs.swap(rhs);
}

А как компилятор будет понимать, что нужно достать именно эту функцию? Для этого разработчику стоит вызывать функцию с помощью неквалифицированного имени:

template <typename T> 
void foo(T &obj1, T &obj2)
{ 
  using std::swap;
  ....
  swap(obj1, obj2); 
  ....
}

В этом примере using std::swap; делает функцию std::swap доступной в текущей области видимости, а при неквалифицированном вызове swap(obj1, obj2); компилятору будет доступна как стандартная, так и пользовательская функции.

Hidden friend

Ещё одним интересным паттерном использования механизма ADL является его сочетание с дружественными функциями. Предлагаю рассмотреть подробнее.

Функция, объявленная и определённая внутри класса с ключевым словом friend, становится видимой только через ADL, если хотя бы один из её параметров имеет тип, связанный с этим классом. Это позволяет тесно связать её с классом, не загрязняя окружающее пространство имён:

namespace N {
  class Data {
  public: 
    friend void print(const Data & s) {
      std::cout << " print";
    }
  };
}

int main() {
  N::Data s;
  print(s);
}

В классе Data мы написали дружественную функцию print. Она считается объявленной в ближайшем обрамляющем пространстве имён класса Data, то есть в namespace N. Однако, так как это объявление расположено внутри класса Data, то найти её можно только через этот класс.

Компилятор находит эту функцию благодаря ADL. Когда он видит вызов print(s) и не находит print неквалифицированным поиском, то смотрит на пространства имён, ассоциированные с типом аргумента s (N::Data, N). ADL "заглядывает" во все связанные пространства имён, и в этом случае находит print в namespace N.

Хотя функция и объявлена в namespace N, квалифицированный поиск её не обнаружит, так как он не идёт изнутри наружу, поэтому найти функцию можно только неквалифицированным поиском через ADL. Из-за этого не получится вызвать её как-то так:

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'
}

Если же дружественная функция без параметров, то для доступа к ней требуется дополнительное объявление во внешнем пространстве имён:

namespace N 
{
  void print();
  
  class Data {
  public: 
    friend void print() {
      std::cout << "print";
    }
    void foo()
    {
      print();
    }
  };
}

Без объявления в пространстве имён N компилятор не cможет найти функцию для вызова даже внутри класса.

Решение

А что насчёт нашего примера из проекта OpenCV? Как найти решение? Освежим память и вновь взглянем на код:

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)
    << ")";
}
} // namespace

Сейчас функция расположена в пространстве имён std, что не соответствует правилам стандарта. Её видимость обеспечивается через механизм ADL: компилятор находит функцию через второй параметр std::ostream, который как раз таки расположен в пространстве имён std. Нам необходимо перенести эту функцию в другое пространство имён, чтобы убрать неопределённое поведение.

Изначально мы думали предложить решение с использованием скрытой дружественной функции в классе, которую рассматривали ранее. То есть перенести объявление PrintTo в тело класса первого параметра. Тогда бы изменения были минимальные: её тоже было бы видно только через механизм ADL, но уже без неопределённого поведения.

Однако тут возникли сложности. На самом деле тип String_FeatureDetector_DescriptorExtractor_Float_t — это не пользовательский класс, а большая заваруха. Смотрите сами:

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;
}
}

Мы бы могли положить функцию в то пространство имён, где объявлен этот псевдоним, но смысла в этом не будет, потому что псевдоним не является типом, и это пространство имён не участвует в поиске. А тип этого параметра раскрывается как-то так:

std::tuple<std::string,
           std::function<cv::Ptr<cv::Feature2D>()>,
           std::function<cv::Ptr<cv::Feature2D>()>,
           float>

А значит, поиск происходит только в пространствах имён std и cv, а также в классах tuple, string, Ptr, Feature2D, поэтому нужно вынести эту функцию из std в какое-то из этих мест.

Можно было бы перенести функцию в класс Feature2D, но тогда в базовый класс придётся добавлять код, необходимый только для тестов. Подобный подход выходит нерациональным, и вместо этого предлагаем такое решение:

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";
    };
  };
}}

Мы заменили псевдоним tuple обычным классом и прописали внутри него дружественную функцию PrintTo. Объявленные псевдонимы DetectorFactory и ExtractorFactory используются только в этой части программы, поэтому мы напрямую поместили их внутрь класса. Такой подход позволил избежать неопределённого поведения, при этом оставив функцию доступной для вызова.

При необходимости функцию можно вынести из класса в пространство имён, в которое он вложен, потому что теперь используется не псевдоним, а класс, и ADL будет учитывать его при поиске.

Заключение

ADL помогает писать более понятный код, позволяя автоматически находить нужные функции через типы аргументов. Однако этот механизм, как и любой другой, нужно использовать правильно, потому что игры с неопределённым поведением ни к чему хорошему не приведут.

А найти другие опасные места в коде поможет PVS-Studio, который вы можете бесплатно попробовать на своём проекте. Берегите себя и свой код!