Это продолжение темы начатой в статье Важны ли компилятору имена, и продолженой в Ночью все кошки серы, а using’и одинаковы, и если вам нужна полная картина, как компилятор превращает текст в программу, то без понимания поиска имён (name lookup) дальше двигаться уже не получится.
Имена в тексте исходника это просто удобные ярлыки для людей: переменные, функции, типы. Но для компилятора имя являеются точкой входа в довольно сложный алгоритм, который должен однозначно определить, что именно вы имели в виду. И вот здесь начинается самое интересное: одинаково написанное имя в разных контекстах может означать совершенно разные вещи, а иногда даже не означать ничего вовсе, в зависимости от того, где и как оно используется.
C++ в этом месте особенно коварен. Язык рос десятилетиями, и правила поиска имён эволюционировали вместе с ним: добавлялись пространства имён, шаблоны, ADL, двухфазный поиск. Всё это не просто усложнило модель, оно сделало её местами неинтуитивной даже для опытных разработчиков, добавим сюда еще, что разные компиляторы исторически реализовывали эти правила (по-своему) по-разному, и часть этих различий до сих пор всплывает в коде.
Не нужно воспринимать компилятор как чёрный ящик, хотя порою поиск имён действительно выглядит как магия, но если разобрать его на отдельные шаги, то становится видно, что за этой «магией» стоит вполне строгая (хоть и исторически нагруженная) система правил. Попробую о ней рассказать.
Чтобы разобраться как работает поиск имён, сначала нужно понять систему описания тех имён, которые мы пишем в коде. На самом базовом уровне у нас есть идентификатор, который по сути просто последовательность букв, цифр и подчеркиваний, например speed, foo или my_var.
Когда мы используем шаблон, его имя тоже является идентификатором, но когда мы добавляем аргументы шаблона, например my<T, 1>, то получаем не просто имя шаблона, а квалифицированное имя шаблона или template-id.
Чтобы объединить эти понятия, вводится термин unqualified-id — неквалифицированный идентификатор. Это общее понятие, которое включает в себя не только обычные идентификаторы, но и более сложные формы имён, такие как операторы, деструкторы или пользовательские литералы.
Когда же мы добавляем оператор разрешения области видимости ::, мы получаем qualified-id( квалифицированное имя), например, std::vector, Foo::~Foo и тому подобное. При этом важно понимать, что в выражении Foo::bar имя bar является квалифицированным, а Foo само по себе является квалификатором, но само становится уже неквалифицированным именем.
// Неквалифицированное имя // просто идентификаторvector<int> v; // 'vector' — неквалифицированное имяsort(v.begin(), v.end()); // 'sort' — неквалифицированное имя// Квалифицированное имя (qualified-id) // с оператором ::std::vector<int> v; // 'vector' — квалифицированное, // 'std' — квалификаторstd::sort(v.begin(), v.end());struct Foo { ~Foo() {} static void bar() {}};Foo::bar(); // 'bar' — квалифицированное имя// 'Foo' — квалификаторFoo::~Foo(); //'~Foo' — квалифицированное имя // деструктора// template-id — имя шаблона с явными аргументамиstd::vector<int> v1; // 'vector<int>' — template-idstd::pair<int, float> p; // 'pair<int, float>' — template-id
Остается ключевое понятие для поиска имён — терминальное имя. Это последнее лексическое имя, которое алгоритм поиска в итоге пытается найти. Например, в выражении obj->f терминальным именем является f и именно его компилятор ищет в результате всех этапов поиска.
// Терминальное имя - последнее имя которое компилятор ищетobj->f(); // терминальное имя: 'f'std::vector<int>::size_type x; // терминальное имя: 'size_type'Foo::bar(); // терминальное имя: 'bar'ns::Foo::bar();// терминальное имя: 'bar', квалификаторы: 'ns', 'Foo'// Где это важно: поиск в зависимых контекстахtemplate<typename T>void wrapper(T& obj) { obj.size(); // 'size' - терминальное неквалифицированное имя // компилятор ищет его в типе T в момент инстанциации T::value_type x; // 'value_type' - терминальное квалифицированное имя // без 'typename' компилятор может не понять что это тип typename T::value_type y; // так правильнее}
Понимание терминов «идентификатор», «template-id», «qualified-id» и особенно «терминальное имя» и становится ключом к пониманию как стандарта так и поведения компилятора в целом. Общее правило поиска имён в C++ несложное, но запутанное, потому что развивалось прыжками от стандарта к стандарту, а вендоры и крупные компании и даже именитые разработчики вносили свою лепту.
MSVC до 2017 года не поддерживал (two-phase name lookup) двух-фазный поиск (об этом чуть ниже) и при разборе шаблона компилятор откладывал поиск всех имён до инстанциации, тогда как стандарт требовал разделить поиск на два этапа ещё при определении шаблона. GCC и Clang более строго следовали стандарту, MSVC игнорировал это требование более 20 лет.
Эндрю Кёниг предложил модификацию правил поиска имён связанных с пространствами имён, которая вошла в стандарт под названием «Koenig lookup» и официально закреплена в стандарте как [basic.lookup.koenig], хотя в обиходе чаще называется ADL — argument-dependent lookup.
С ADL вообще получилась интересная история, потому что Кёниг не изобретал ADL, а лишь сформулировал и протолкнул решение уже существующей проблемы. В начале 90-х комитет добавлял пространства имён в черновик стандарта, но выяснилось что они конфликтуют с перегрузкой операторов. Требовалось понять как сделать так, чтобы перегруженные операторы для пользовательских типов находились автоматически, без явного указания пространства имён.
Конкретная точка боли выглядела так:
namespace sak { struct BigNum { int value; }; // operator<< определён в namespace sak, рядом с типом std::ostream& operator<<(std::ostream& os, const BigNum& n) { return os << "BigNum(" << n.value << ")"; }}int main() { sak::BigNum n(42); // ADL: компилятор видит что n имеет тип sak::BigNum, // ищет operator<< в namespace sak и находит его std::cout << n << "\n"; // Без ADL пришлось бы писать как-то так: sak::operator<<(std::cout, n) << "\n"; // Или так — но тогда теряется весь смысл перегрузки операторов: // std::operator<<(std::cout, n); // не скомпилируется, ибо нет такого в std}
Без ADL компилятор сообщил бы об ошибке, что не может найти operator<<, потому что в вызове не указано явно что он находится в пространстве имён std. Проблему видели и до Кёнига, просто решения не было, и Бьярне Страуструп описал проблему в документе P0262 «Name Space Management in C++» (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/1993/N0262.pdf) еще в 1993 году, в приложении D (Appendix D: Overloading and Namespaces) которого можно увидеть каким был мир до ADL.
// явный вызов убивает весь смысл перегрузки операторовmylib::operator<<(cout, s);// или тащить operator<< в глобальное пространство через usingusing mylib::operator<<;cout << s; // теперь работает, но using надо писать везде
ADL часто приписывают Эндрю Кёнигу, хотя он не является её изобретателем, но Кёниг опубликовал документ N0645 «Reconciling overloaded operators with namespaces» (https://www.open-std.org/jtc1/SC22/wg21/docs/papers/1995/N0645.pdf) в январе 1995 года, где изложил конкретное решение, и первоначально его предложение распространялось только на перегруженные операторы, а не на все функции. Кёниг работал в AT&T Bell Labs, где к тому времени уже существовала устоявшаяся практика подобного поиска в собственных наработках компании, и он скорее формализовал и довёл до комитета то, что уже применялось на практике. Альтернативой было требовать явной квалификации везде, то есть писать std::operator<<(std::cout, obj) вместо std::cout << obj. Это технически корректно, но полностью убивает смысл перегрузки операторов и делает код “грязным”.
Но ADL принесла и побочные эффекты, которые комитет не до конца предвидел, делая пространство имён менее строгими и требую явной квалификации там, где она иначе не нужна, а зависимость от ADL может приводить к семантическим проблемам, когда две библиотеки ожидают разного поведения от одного неквалифицированного имени.
На данный момент алгоритм выглядит так: в любой области сначала выполняется обычный неквалифицированный поиск, затем поиск по базовым классам если применимо, и для вызовов функций дополнительно запускается ADL, который расширяет набор кандидатов именами из пространств имён аргументов. Если имя квалифицированное, выполняется квалифицированный поиск в указанном пространстве имён или классе, без ADL и без обычного неквалифицированного поиска (идем снизу вверх)
В шаблонном коде поиск разбивается на две фазы: независимые имена ищутся в момент определения шаблона, а зависимые в момент инстанциации, и именно во второй фазе для зависимых имён подключается ADL.
GCC
Историческая особенность GCC в шаблонном коде проявлялась в том, что границы между первой и второй фазой поиска трактовались иначе, чем у Clang и требованиями стандарта, из-за чего ADL для зависимых имён срабатывал не всегда в нужный момент. Код, который должен был компилироваться мог не скомпилироваться, или наоборот компилировался там, где не должен был.
GCC реализовал шаблоны раньше, чем стандарт окончательно сформулировал эти правила, и исторически использовал так называемый «lazy parsing», при котором тело шаблона при первом разборе фактически не анализировалось полностью, а откладывалось до инстанциации. Это означало, что первая фаза поиска по сути не выполнялась вовсе, и все имена, включая независимые, искались в момент инстанциации.
Практическое следствие было такое:
void foo(int) {} // глобальная footemplate<typename T>void bar(T x) { foo(x); // зависимое имя - ищется в фазе 2 через ADL, всё верно foo(42); // НЕзависимое имя - должно искаться в фазе 1 // GCC: откладывал до инстанциации и находил foo(int) - ok // Clang: искал в фазе 1 и не находил подходящей foo - error}namespace myns { struct MyType {}; void foo(MyType) {}}bar(myns::MyType{});// GCC: компилировал без проблем// Clang: error: use of undeclared identifier 'foo'
Clang
Когда в C++98 формализовали двух-фазный поиск (two-phase lookup), комитет столкнулся с концептуальным вопросом: что делать с именами из базового класса если базовый класс сам является шаблоном?
Если база Base<T> не известна полностью в момент определения Derived<T> и зависит от параметра T, то разные специализации могут содержать совершенно разные наборы членов.
Комитет решил, что зависимые базовые классы не участвуют в первой фазе неквалифицированного поиска по той причине, что если разрешить поиск в зависимой базе в первой фазе, то добавление нового члена в специализацию базового класса может изменить смысл кода в производном классе, что нарушает принцип предсказуемости шаблона (т.е. он будет зависеть от того с какими аргументами он инстанциируется).
// Почему комитет запретил поиск в зависимой базе в фазе 1:template<typename T>struct Base { // в общей версии нет метода process};// специализация для int - есть processtemplate<>struct Base<int> { void process() {}};template<typename T>struct Derived : Base<T> { void run() { process(); // если разрешить поиск в зависимой базе: // для T=int - найдёт Base<int>::process, скомпилируется // для T=float - не найдёт ничего и упадёт // при одинаковом код шаблона имеем разное поведение }};
MSVC
Исторически MSVC имел нестандартное поведение при поиске имён в шаблонах, двухфазный поиск (two-phase name lookup) долгое время не был реализован в соотвествии со стандартом и до версии VS 2017 с флагом /permissive- зависимые имена в шаблонах искались только в момент инстанцирования, но не в момент определения, что давало другой набор кандидатов по сравнению с GCC и Clang.
Это реальная проблема совместимости, хорошо известная в C++-сообществе, но отложенный парсинг, как это происходит в случае MSVC не просто выбор алгоритма поиска имён. Это архитектурное решение вендора о том, когда компилятор вообще смотрит внутрь тела шаблона и переделать это поведение значит на 80% переписать парсер.
Команда MSVC публично признала, что старый парсер физически не позволял реализовать двухфазный поиск, поэтому пришлось разрабатывать новый, что заняло несколько лет и фактически означало замену одного из центральных компонентов компилятора маек.
Если вас заинтересовал вопрос, а почему MS сразу не реализовали правильный парсер при наличии стандарта, то этот вопрос опять нас уводит в историю компании, и как ни странно к корням UI библиотеки. На MFC (Microsoft Foundation Classes) библиотеке строился весь стек разработки Windows-приложений в 1990-х, и часть особенностей её реализации и фичей влияли на компилятор, добавляя ему особенностей, которые в свою очеред активно эксплуатировались в MFC. Это создавало взаимное усиление, не давая возможности MSVC стать по-настоящему стандартным, потому что он сломал бы MFC, а MFC не мог стать переносимым, потому что опирался на нестандартный MSVC. Но внутри Microsoft эта связка была политически защищена, потому что MFC был основой экосистемы разработчиков под Windows.
Это классическая история технического долга в масштабах платформы, который перерос в масштаб компании и стал влиять на выпускаемые продукты, а некогда быстрое и прагматичное решение 1993 года превратилось в архитектурное ограничение на 25 лет, которое нельзя было исправить без одновременного переписывания парсера, правки тысяч компонентов Windows SDK и исправления MFC, без поломки обратной совместимости с кодом сотен тысяч разработчиков.
template <typename T>void call_foo(T x) { foo(x); // зависимое, но MSVC решал это по-своему}void foo(int x) { } // объявлено ПОСЛЕ шаблонаint main() { call_foo(42); // GCC: error - foo не видна в точке определения шаблона // MSVC: ok - находим foo при инстанцировании}
По стандарту foo(x) будет зависимым именем (зависит от T), поэтому должно искаться при инстанцировании, но только через ADL. Но foo(int) не находится через ADL для int (нет связанного namespace), так что GCC правильно даёт ошибку, MSVC просто искал всё при инстанцировании и находил.
Что дальше…
Как я говорил в первой статье, поиск имён в C++ все ще еще та часть языка, которая кажутся очевидной ровно до того момента, пока не начинаешь разбираться в деталях. За привычными foo, bar и vector скрывается не просто сопоставление строк, а сложная и местами исторически странная система правил, компромиссов и расширений, появлявшихся по мере развития языка.
Я постарался разобрать базовые строительные блоки этой системы: идентификаторы, как из них формируются unqualified-id и qualified-id, где появляется template-id и почему имеет смысл выделять «терминальное имя» как точку, в которую в итоге упирается весь алгоритм поиска. Эти понятия сами по себе не решают всех вопросов, но без них невозможно понять ни ADL, ни двухфазный поиск, ни поведение шаблонов.
Надеюсь после этих статей вы понимаете почему в C++ не существует единого «алгоритма поиска имён», который просто проходит шаги один за другим, но есть несколько разных механизмов, которые включаются в зависимости от формы имени и контекста.
Если держать в голове эту модель как систему из нескольких пересекающихся механизмов, то многие «странности» C++ начинают выглядеть вполне «логично». И вот с этой точки можно уже двигаться дальше и разбирать конкретные случаи, где эти правила пересекаются и начинают вести себя неочевидно. В следующей статье расскажу про самый базовый механизм ( неквалифицированный поиск) и посмотрим, как даже он один способен создавать довольно нетривиальные ситуации.
ссылка на оригинал статьи https://habr.com/ru/articles/1023334/