6 декабря 2010 г.

Clang API: обход AST (clang-2.8)

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


Исходный файл такой же, как и в предыдущем примере. Взять его можно здесь. Используется Clang версии 2.8.

Clang предоставляет набор базовых классов, реализующих механизм доступа к узлам дерева. Сам механизм довольно простой — нужно определить класс-потребитель, унаследованный от абстрактного интерфейса clang::ASTConsumer, и имплементировать метод HandleTranslationUnit, который будет вызван при завершении анализа входного файла. В этот метод будет передан объект контекста, содержащий ссылку на корневой узел дерева. Для самостоятельного обхода дерева нужно создать собственную имплементацию паттерна Visitor. Программист должен просто унаследовать свой класс от базового Visitor'а, предоставляемого clang'ом, и переопределить виртуальные функции, ответственные за обработку тех или иных типов узлов синтаксического дерева.

В двух словах порядок действий:
  1. Создать экземпляр класса clang::Preprocessor, который инкапсулирует в себя функциональность, связанную с анализом исходного файла. Задать входной файл для анализа.
  2. Создать экземпляр класса clang::ASTContext, который хранит узлы дерева.
  3. Создать экземпляр своего собственного класса-потребителя, имплементирующий обход дерева.
  4. Вызвать функцию clang::ParseAST(), которая выполнит разбор входного файла с помощью Preprocessor, построит AST, положит его в ASTContext и вызовет функцию HandleTranslationUnit класса-потребителя для обработки дерева.

Создание и инициализация экземпляра Preprocessor

Для создания экземпляра класса Preprocessor нам потребуются экземпляры классов Diagnostic, LangOptions, TargetInfo, SourceManager и HeaderSearch.

Создадим экземпляр класса диагностики, использующий для вывода текстовый буфер. Также создадим и инициализируем классы LangOptions и TargetInfo:

Diagnostic diagnostic(new TextDiagnosticBuffer);

LangOptions langOptions;
langOptions.CPlusPlus = 1; // We will parse a C++ file.

TargetOptions targetOptions;
targetOptions.Triple = "x86_64"; // x86, ppc, ...

auto_ptr<TargetInfo> targetInfo(
  TargetInfo::CreateTargetInfo(diagnostic, targetOptions));
assert(0 == diagnostic.getNumErrors());
assert(0 != targetInfo.get());

Теперь создадим экземпляры классов SourceManager и HeaderSearch. SourceManager — класс, отвечающий за поиск и буферизацию входных файлов для анализа. HeaderSearch обеспечивает поиск заголовочных файлов:

SourceManager sourceManager(diagnostic);
FileManager fileManager;
HeaderSearch headerSearch(fileManager);

Теперь можно создать экземпляр класса-препроцессора:

Preprocessor preprocessor(diagnostic,
                          langOptions,
                          *targetInfo,
                          sourceManager,
                          headerSearch);

Зададим входной файл для анализа:

const FileEntry* file = fileManager.getFile("a.cpp");
assert(0 != file);
sourceManager.createMainFileID(file);

Создание экземпляра ASTContext

Экземпляр класса контекста создается очень просто. Описание используемых классов можно посмотреть в заголовочных файлах clang'а.

IdentifierTable identifierTable(langOptions);
SelectorTable selectorTable;
clang::Builtin::Context builtinContext(*targetInfo);
const unsigned int NumReserved = 10; // зарезервированный размер

ASTContext astContext(langOptions,
                      sourceManager,
                      *targetInfo,
                      identifierTable,
                      selectorTable,
                      builtinContext,
                      NumReserved);

Реализация класса-потребителя и класса-визитёра

Итак, теперь нужно сделать основную работу — определить класс-потребитель и имплементировать механизм обхода дерева.

Реализация класса-потребителя будет простой, потому что нам нужно имплементировать всего одну функцию HandleTranslationUnit. В ней мы берем корневой элемент дерева (TranslationUnit) и "посещаем" его с помощью класса-визитёра, который мы имплементируем чуть позже:

class MyAstConsumer : public ASTConsumer
{
public:
  virtual void HandleTranslationUnit (ASTContext &ctx)
  {
    TranslationUnitDecl *translationUnit = ctx.getTranslationUnitDecl();
    MyDeclVisitor().Visit(translationUnit);
  }
};

Класс-посетитель немного сложнее в реализации. В первую очередь необходимо реализовать обработчик посещения узла TranslationUnitDecl. Затем нужно реализовать обход всех его дочерних узлов. Для нашего удобства любой узел, который содержит дочерние узлы, может быть обработан как DeclContext, поэтому далее нужно реализовать обработчик для типа узла DeclContext и вызвать эту функцию, передав в нее наш translation unit. В этом обработчике выполняется "посещение" всех дочерних узлов, поэтому для каждого интересующего нас типа узла в классе-визитёре должен быть создан соответствующий обработчик (VisitCXXRecordDecl, VisitFieldDecl, VisitCXXMethod, ...). В нашей реализации класс-визитёр выводит в stderr названия типов узлов, которые он посещает:

class MyDeclVisitor : public clang::DeclVisitor<MyDeclVisitor>
{
  llvm::raw_ostream &_out;

public:
  MyDeclVisitor () : _out(llvm::errs())
  {
  }

  void VisitTranslationUnitDecl (clang::TranslationUnitDecl *D)
  {
    _out << D->Decl::getDeclKindName() << "\n";
    // A translation unit has child nodes, so consider that as a context.
    VisitDeclContext(D);
  }

  void VisitDeclContext (clang::DeclContext *DC)
  {
    // NOTE: The lines below were taken from Clang source code.
    // This code tries to skip any service information which is
    // unnecessary for an end-user in this case.

    clang::DeclContext::decl_iterator DBegin = DC->decls_begin();
    clang::DeclContext::decl_iterator DEnd = DC->decls_end();

    for (clang::DeclContext::decl_iterator i = DBegin; i != DEnd; ++i)
    {
      // Skip over implicit declarations
      if ((*i)->isImplicit())
      {
        continue;
      }

      if (clang::NamedDecl *ND = llvm::dyn_cast<clang::NamedDecl>(*i))
      {
        if (clang::IdentifierInfo *II = ND->getIdentifier())
        {
          if (II->isStr("__builtin_va_list")
              || II->isStr("__int128_t")
              || II->isStr("__uint128_t"))
          {
            continue;
          }
        }
      }

      _out << __FUNCTION__ << ": " << (*i)->getDeclKindName() << "\n";

      Visit(*i); // Visit all the child nodes.
    }

  }

  void VisitCXXRecordDecl (clang::CXXRecordDecl *D)
  {
    // process c++ class

    _out << "CXXRecord: " << D->getKindName();
    if (D->getIdentifier())
    {
      _out << ' ' << D;
    }
    _out << "\n";

    // A class has child nodes, so consider that as a context.
    VisitDeclContext(D);
  }

  void VisitFieldDecl (clang::FieldDecl *D)
  {
    // process a field here
  }

  void VisitCXXConstructorDecl (clang::CXXConstructorDecl *D)
  {
    // process a class constructor here
  }

  void VisitCXXMethodDecl (clang::CXXMethodDecl *D)
  {
    // process a class method here
  }
};

Выполнение анализа файла и обход дерева

Теперь необходимо создать экземпляр класса-потребителя и вызвать функцию ParseAST:

MyAstConsumer consumer;

clang::ParseAST(preprocessor, &consumer, astContext);
assert(0 == diagnostic.getNumErrors());

После выполнения программы в stderr должно быть выведено что-то вроде:
TranslationUnit
VisitDeclContext: CXXRecord
CXXRecord: struct MyAnotherClass
VisitDeclContext: Field
VisitDeclContext: Field
VisitDeclContext: CXXConstructor
VisitDeclContext: CXXMethod

Обход дерева успешно завершен!

Исходный код (немного расширенный и дополненный) для этой и для прошлой статьи можно взять здесь.

8 комментариев:

  1. А каким образом можно скомпилировать данный файл?

    ОтветитьУдалить
    Ответы
    1. Думаю, что компилятором :) Попробуйте gcc.

      Удалить
    2. На всякий случай проверил - при компиляции GСС особых проблем нет для любой версии от 4.4 до 4.6. А вот линковать лучше gcc-4.4.

      Удалить
    3. Видимо я неправильно сформулировал вопрос. Меня интересовало с какими аргументами необходимо вызывать компилятор.

      Удалить
    4. Давайте попробуем с другой стороны :)
      С какими аргументами запускаете Вы и в чем у Вас возникает проблема?

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

    /usr/local/include/clang/AST/DeclNodes.inc: In member function 'RetTy clang::DeclVisitor::Visit(clang::Decl*) [with ImplClass = clang::MyDeclVisitor, RetTy = void]':
    DeclVisitor.cpp:48: instantiated from here
    /usr/local/include/clang/AST/DeclNodes.inc:15: error: 'clang::DeclVisitor' is an inaccessible base of 'clang::MyDeclVisitor'
    /usr/local/include/clang/AST/DeclNodes.inc:15: error: return-statement with a value, in function returning 'void'
    /usr/local/include/clang/AST/DeclNodes.inc:21: error: 'clang::DeclVisitor' is an inaccessible base of 'clang::MyDeclVisitor'
    /usr/local/include/clang/AST/DeclNodes.inc:21: error: return-statement with a value, in function returning 'void'
    /usr/local/include/clang/AST/DeclNodes.inc:27: error: 'clang::DeclVisitor' is an inaccessible base of 'clang::MyDeclVisitor'
    /usr/local/include/clang/AST/DeclNodes.inc:27: error: return-statement with a value, in function returning 'void'

    При этом, если закомментировать вызов Visit(*i) в функции VisitDeclContext, то программа компилируется без ошибок, но проход осуществляется только по декларациям верхнего уровня.
    Не подскажете почему возникает такая ситуация?

    ОтветитьУдалить
    Ответы
    1. Скорее всего у Вас другая версия библиотеки, не та, которой пользовался я. Вам нужно разобраться в семантике методов используемых классов и реализовать наследников в соответствии.

      Удалить
    2. Я честно разбирался, а потом спросил :)
      В итоге воспользовался другими возможностями API для решения той же задачи.

      Удалить