Pull to refresh

Как компилятор C++ находит правильную функцию

Reading time 13 min
Views 14K
Original author: Jeff Preshing

Увлекательный пересказ того, как компилятор C++ находит правильную функцию, которую надо вызвать, когда в коде вызывается функция. По сути, это просто сжатое объяснение алгоритма, уже описанного на cppreference.com, который, в свою очередь, является сокращенной версией стандарта C++.


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



Мне нравятся все эти возможности C++. С помощью них можно заставить str1 + str2 возвращать результат конкатенации двух строк. Вы можете иметь пару 2D точек и другую пару 3D точек, и перегрузить dot(a, b) для работы с каждой из них. Вы можете иметь кучу классов, подобных массиву, и написать одну шаблонную функцию sort для работы со всеми из них.


Но когда вы пользуетесь всеми этими возможностями, легко зайти слишком далеко. В какой-то момент компилятор может неожиданно отклонить ваш код с ошибками вроде:


error C2666: 'String::operator ==': 2 overloads have similar conversions
note: could be 'bool String::operator ==(const String &) const'
note: or       'built-in C++ operator==(const char *, const char *)'
note: while trying to match the argument list '(const String, const char *)'

Как и многие программисты на C++, я боролся с такими ошибками на протяжении всей своей карьеры. Каждый раз, как это происходило, я обычно чесал затылок, искал в Интернете лучшее понимание ошибки, а затем менял код до тех пор, пока он не скомпилируется. Но совсем недавно, при разработке новой библиотеки для Plywood, я снова и снова сталкивался с такими ошибками. Стало ясно, что, несмотря на весь мой предыдущий опыт работы с C++, в моем понимании чего-то не хватало, и я не знал, чего именно.


К счастью, сейчас 2021 год, и информация о C++ более обширна, чем когда-либо. Отдельная благодарность cppreference.com, благодаря которому теперь я знаю, чего мне так не хватало: четкой картины скрытого алгоритма, который используется для каждого вызова функции во время компиляции.


Вот так компилятор точно определяет, какую функцию следует вызвать:



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


Я предполагаю, что общая цель алгоритма — «делать то, что ожидает программист», и до некоторой степени он в этом преуспевает. Вы можете довольно далеко зайти, полностью игнорируя этот алгоритм. Но когда вы начинаете использовать все возможности C++, как при разработке библиотеки, то лучше знать эти правила.


Итак, давайте пройдемся по алгоритму от начала и до конца. Многое из того, что мы рассмотрим, будет знакомо опытным программистам C++. Тем не менее, это может быть весьма захватывающи наблюдать, как все этапы сочетаются друг с другом. (По крайней мере, так это было для меня.) Попутно мы затронем несколько продвинутых подтем C++, таких как поиск, зависящий от аргумента (ADL), и SFINAE, но мы не будем углубляться в какую-либо конкретную подтему. Таким образом, даже если вы больше ничего не знаете о подтеме, по крайней мере, будете знать, как она вписывается в общую стратегию C++ по нахождению правильного вызова функции во время компиляции. Я бы сказал, что это самое главное.


Поиск по имени


Наше путешествие начинается с выражения вызова функции. Возьмем, к примеру, выражение blast(ast, 100) из кода ниже. Это выражение явно предназначено для вызова функции с именем blast. Но какой?


namespace galaxy {
    struct Asteroid {
        float radius = 12;
    };
    void blast(Asteroid* ast, float force);
}

struct Target {
    galaxy::Asteroid* ast;
    Target(galaxy::Asteroid* ast) : ast{ast} {}
    operator galaxy::Asteroid*() const { return ast; }
};

bool blast(Target target);
template <typename T> void blast(T* obj, float force);

void play(galaxy::Asteroid* ast) {
    blast(ast, 100);
}

Первый шаг к ответу на этот вопрос — поиск функции по имени (name lookup). На этом этапе компилятор просматривает все функции и шаблоны функций, которые были объявлены до этого момента, и выбирает те, которые могли бы соответствовать заданному имени.



Как видно из блок-схемы, существует три основных типа поиска имени, каждый со своим собственным набором правил.


  • Поиск имени по методам (Member name lookup) происходит, когда имя находится справа от токена . или ->, как в foo->bar. Этот тип поиска используется для поиска методов класса.


  • Поиск квалифицированного имени (Qualified name lookup) происходит, когда имя содержит токен ::, например, std::sort. Этот тип имени является явным для компилятора. Часть справа от токена :: ищется только в области видимости, обозначенной в левой части.


  • Поиск неквалифицированных имён (Unqualified name lookup) не является ни тем, ни другим. Когда компилятор видит неквалифицированное имя, например blast, он ищет совпадающие декларации функций в множестве различных областей в зависимости от контекста. Существует подробный набор правил, который точно определяет, где должен искать компилятор.



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



Первый кандидат заслуживает особого внимания, потому что он демонстрирует особенность C++, которую легко пропустить: поиск, зависящий от аргумента, или argument-dependent lookup или ADL для краткости. Признаюсь, большую часть своей карьеры C++ я не знал о роли ADL в поиске имен. Вот краткое изложение на тот случай, если вы находитесь в одной лодке со мной. Обычно вы не ожидаете, что эта функция будет кандидатом на этот конкретный вызов, так как она была объявлена ​​внутри пространства имен galaxy, а вызов происходит снаружи — за пределами пространства имен galaxy. В коде также нет директивы using namespace galaxy, чтобы сделать эту функцию видимой в текущем месте. Так почему эта функция является кандидатом?


Причина в том, что каждый раз, когда вы используете неквалифицированное имя в вызове функции — и имя, помимо прочего, не относится к методу класса, — срабатывает ADL, и поиск имени становится более жадным. В частности, в дополнение к обычным местам, компилятор ищет функции-кандидаты в пространствах имен типов аргументов — отсюда и название «поиск, зависимый от аргументов».



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


Интересно, что бывают случаи, когда поиск по методу может найти кандидатов, которых не может найти неквалифицированный поиск имени. См. этот пост Eli Bendersky для получения подробной информации об этом.


Специальная обработка шаблонов функций


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



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


template <typename T> void blast(T* obj, float force)

Этот шаблон функции имеет единственный параметр шаблона, T. Таким образом, он ожидает одного аргумента шаблона. Программист не указал никаких аргументов шаблона для blast(ast, 100), поэтому, чтобы превратить этот шаблон функции в настоящию функцию, компилятор должен определить тип T. Тут на помощь приходит вывод аргумента шаблона (template argument deduction). На этом этапе компилятор сравнивает типы аргументов функции, переданных вызывающей стороной (на диаграмме слева внизу), с типами параметров функции, ожидаемых шаблоном функции (справа). Если какие-либо неуказанные аргументы шаблона упоминаются справа, например T, компилятор пытается вывести их, используя информацию слева.



В нашем случае компилятор выводит T как galaxy::Asteroid, потому что это делает первый параметр функции T * совместимым с аргументом ast. Правила, регулирующие вывод аргументов шаблона, сами по себе являются большой темой, но в простых примерах, подобных этому, они обычно делают то, что мы от них ожидаем. Если вывод аргументов шаблона не работает — другими словами, если компилятор не может вывести аргументы шаблона таким образом, чтобы параметры функции были совместимы с аргументами вызывающего объекта, — то шаблон функции удаляется из списка кандидатов.


Любые шаблоны функций в нашем списке кандидатов, которые продержались до этого момента, подлежат следующему шагу: подстановка аргумента шаблона (template argument substitution). На этом этапе компилятор берёт объявления шаблона функции и заменяет каждый параметр шаблона на соответствующий аргумент шаблона. В нашем примере параметр шаблона T заменяется выведенным аргументом шаблона galaxy::Asteroid. Как только этот шаг завершится успешно, у нас появиться сигнатура реальной функции, которую теперь можно вызвать, а не просто шаблон функции!



Конечно, бывают случаи, когда подстановка аргументов шаблона может не сработать. Предположим на мгновение, что тот же шаблон функции принял третий аргумент, например:


template <typename T> void blast(T* obj, float force, typename T::Units mass = 5000);

Если бы это было так, компилятор попытался бы заменить T в T::Units на galaxy::Asteroid. Получившийся спецификатор типа, galaxy::Asteroid::Units, будет неверно сформирован (ill-formed), потому что структура galaxy::Asteroid на самом деле не имеет поля с именем Units. Следовательно, подстановка аргументов шаблона завершится ошибкой.


Когда подстановка аргументов шаблона терпит неудачу, шаблон функции просто удаляется из списка кандидатов — но в какой-то момент истории C++ программисты поняли, что это возможность, которую они могут использовать! Это открытие привело к целому набору самостоятельных методов метапрограммирования, которые вместе именуются SFINAE (substitution failure is not an error). SFINAE — сложная и громоздкая тема, о которой я скажу только две вещи. Во-первых, это, по сути, способ настроить процесс разрешения вызовов функций для выбора нужного кандидата. Во-вторых, со временем он, вероятно, потеряет свою популярность, поскольку программисты все чаще обращаются к современным методам метапрограммирования C++, которые достигают того же, таким как constraints и constexpr if.


Находим жизнеспособные функции


На этом этапе все шаблоны функций, найденные ранее, исчезли, и у нас остался красивый аккуратный набор функций-кандидатов. Его также иногда называют набором перегрузки (overload set). Вот обновленный список функций-кандидатов для нашего примера:



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



Возможно, наиболее очевидным требованием является то, что аргументы должны быть совместимы; то есть жизнеспособная функция должна быть способна принимать аргументы вызывающего. Если типы аргументов вызывающего объекта не совпадают в точности с типами параметров функции, должна быть, по крайней мере, возможность неявно преобразовать (implicit) каждый аргумент в соответствующий тип параметра. Давайте посмотрим на каждую из функций-кандидатов нашего примера на совместимость её параметров:



Кандидат 1

      Тип первого аргумента вызывающего объекта galaxy::Asteroid* является точным совпадением. Второй тип аргумента вызывающей стороны int неявно преобразуется во второй тип параметра функции float, поскольку int в float является стандартным преобразованием. Следовательно, параметры кандидата 1 совместимы.


Кандидат 2

      Тип первого аргумента вызывающего объекта galaxy::Asteroid* неявно преобразуется в первый тип параметра функции Target, потому что Target имеет конструктор преобразования, который принимает аргументы типа galaxy::Asteroid*. (Между прочим, эти типы также могут быть преобразованы в другую сторону, поскольку Target имеет определяемую пользователем функцию преобразования обратно в galaxy::Asteroid*.) Однако вызывающая сторона передала два аргумента, а кандидат 2 принимает только один. Следовательно, кандидат 2 нежизнеспособен.



Кандидат 3

      Типы параметров кандидата 3 идентичны параметрам кандидата 1, поэтому он также совместим.


Как и все остальное в этом процессе, правила, управляющие неявным преобразованием сами по себе являются отдельной темой. Самое примечательное правило заключается в том, что вы можете избежать участия конструкторов и операторов преобразования в неявном преобразовании, пометив их как explicit.


После фильтрации несовместимых кандидатов по аргументам вызывающей функции, компилятор переходит к проверке соответствия ограничений (constraints) каждой функции, если такие имеются. Ограничения — это нововведение в C++20. Они позволяют использовать настраиваемую логику для исключения функций-кандидатов (приходящих из шаблона класса или шаблона функции) без необходимости прибегать к SFINAE. Они также должны помочь улучшить сообщения об ошибках. В нашем примере не используются ограничения, поэтому мы можем пропустить этот шаг. (Технически в стандарте говорится, что ограничения также проверяются раньше, во время вывода аргументов шаблона, но я пропустил эту деталь. Проверка в обоих местах помогает в отображение наиболее точного сообщения об ошибке.)


Последний раунд


На данный момент в нашем примере осталось две жизнеспособные функции. Любая из них могла бы нормально справиться с исходным вызовом функции:



В самом деле, если одна из вышеперечисленных функций была бы единственной жизнеспособной, она могла быть той, которая в результате и обработает вызов функции. Но поскольку их две, компилятор должен делать то, что он делает всегда, когда имеются несколько жизнеспособных функций: он должен определить, какая из них является лучшей жизнеспособной функцией (best viable function). Чтобы быть наиболее жизнеспособной функцией, одна из них должна «побеждать» над всеми остальными жизнеспособными функциями, как определено последовательностью правил разрешения конфликтов.



Давайте посмотрим на первые три правила.


Правило 1: Лучшее соответствие параметров выигрывает

Компилятор C++ придает наибольшее значение тому, насколько хорошо типы аргументов в месте вызова соответствуют типам параметров функции. Грубо говоря, он предпочитает функции, которые требуют меньшего количества неявных преобразований из заданных аргументов. Если обе функции требуют преобразования, то некоторые преобразования считаются «лучше», чем другие. Например, имеется правило, которое решает, вызывать ли const или не-const версию для std::vector::operator[].


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


Правило 2: Побеждает функция, не являющаяся шаблоном

Если первое правило не разрешает конфликта, то C++ предпочитает вызывать не шаблонные функции. Это правило определяет победителя в нашем примере; функция 1 — это не шаблонная функция, а функция 2 появилась из шаблона. Следовательно, наша лучшая жизнеспособная функция — это та, которая пришла из пространства имен galaxy:



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


Правило 3: Побеждает более специализированный шаблон

В нашем примере лучшая жизнеспособная функция уже найдена, но если это не так, мы перейдем к третьему правилу. В этом разрешении конфликтов C++ предпочитает вызывать «более специализированные» шаблонные функции, а не «менее специализированные». Например, рассмотрим следующие две шаблоные функции:


template <typename T> void blast(T obj, float force);
template <typename T> void blast(T* obj, float force);

Когда для этих двух шаблонов функций выполняется вывод аргументов шаблона, первый шаблон функции принимает любой тип в качестве своего первого аргумента, но второй шаблон функции принимает только типы указателей. Следовательно, второй шаблон функции считается более специализированным. Если бы эти два шаблона функций были единственными результатами поиска имени для нашего вызова blast(ast, 100), и оба привели бы к жизнеспособным функциям, текущее правило разрешения конфликтов привело бы к выбору второго из них. Это еще одна большая важная тема — правила, определяющие, какой шаблон функции более специализирован, чем другой.


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


В дополнение к перечисленным здесь, есть еще несколько правил. Например, если оператор космический корабль <=> и перегруженные операторы сравнения (такие как >) допустимы, компилятор предпочтёт оператор сравнения. Или если кандидатами являются определяемые пользователем функции преобразования, есть другие правила, которые имеют более высокий приоритет, чем те, которые я показал. Тем не менее, я считаю, что лучше всего запомнить три показанных мною правила.


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


После разрешения вызова функции


Мы подошли к концу нашего пути. Теперь компилятор точно знает, какую функцию следует вызывать с помощью выражения blast(ast, 100). Однако во многих случаях компилятор должен выполнить больше работы после разрешения вызова функции:


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

Ничего из этого не применимо к нашему примеру. Кроме того, они выходят за рамки этой публикации.


Этот пост не содержит какую либо новую информации. По сути, это просто сжатое объяснение алгоритма, уже описанного на cppreference.com, который, в свою очередь, является сокращенной версией стандарта C++. Однако целью этого поста было передать основные шаги, не вдаваясь в детали. Давайте оглянемся назад, чтобы увидеть, сколько деталей было пропущено. Это действительно замечательно:



Да, C++ сложен. Если вы хотите потратить больше времени на изучение этих деталей, Stephan T. Lavavej создал очень смотрибельную серию видео на Channel 9 еще в 2012 году. В частности, обратите внимание на первые три. (Спасибо Стефану за просмотр черновика этого поста.)


Теперь, когда я точно узнал, как C++ разрешает вызов функции, я чувствую себя более компетентным как разработчик библиотеки. Ошибки компиляции более очевидны. Я могу лучше обосновать дизайнерские решения API. Мне даже удалось выделить из правил небольшой набор советов и уловок. Но это тема для другого поста.

Tags:
Hubs:
+21
Comments 3
Comments Comments 3

Articles