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

Оглавление серии

  1. Лексический и синтаксический анализ

  2. Семантический анализ

  3. Генерация кода

  4. Поддержка составных типов

  5. Поддержка классов и перегрузки функций

Введение

Для начала рассмотри кратко, что именно будет реализовано в результате:

  1. Добавим новый тип для классов, который в отличие от структур имеет дополнительные свойства:

  • Может содержать функции члены (методы), которые могут работать с переменным членами класса или производить различные другие действия;

  • Могут иметь родительский класс или структуру, от которых класс может наследовать поведение;

  • Методы класса могут быть виртуальными. И тогда при вызове этих методов через переменные типа указателя на экземпляр этого класса, реализация метода будет выбираться во время выполнения программы, что позволяет вызывать корректные методы даже при вызове этих методов через указатель на объект родительского класса;

  • Могут иметь специальные методы класса — конструкторы (инициализируют начальное состояние объекта) и деструкторы (производит очистку состояния объекта), причем деструкторы могут быть виртуальными.

  1. Добавим поддержку автоматического вызова конструкторов и деструкторов класса для их объектов при выходе объектов класса из области их видимости;

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

Далее будем последовательно рассматривать все правки, которые нужно внести в каждую из частей нашего интерпретатора.

Лексический и синтаксический анализ

Единственные изменения, которые нужно применить в лексическом анализаторе, это:

Добавить поддержку новых ключевых слов в include/Basic/Name.h

KEYWORD(Class, "class") 
KEYWORD(Extends, "extends") 
KEYWORD(This, "this") 
KEYWORD(Super, "super") 
KEYWORD(Virtual, "virt") 
KEYWORD(Override, "impl") 

Добавить новые переменные для работы с некоторыми из новых ключевых слов (для использования их в семантическом анализе для служебных методов и специальных конструкций, например для вызова методов базового класса):

Hidden text
struct Name { 
  ...
  static Name *Super;  ///< Имя для ключевого слова "super" 
  static Name *This;   ///< Имя для ключевого слова "this" 
  static Name *Ctor;   ///< Имя для конструктора
  static Name *Dtor;   ///< Имя для деструктора
}; 
// lib/Basic/Name.cpp" 
Name *Name::Super = nullptr; 
Name *Name::This = nullptr; 
Name *Name::Ctor = nullptr; 
Name *Name::Dtor = nullptr; 

// lib/Lexer/Lexer.cpp
void NamesMap::addKeywords() { 
  if (IsInit) { 
    return; 
  } 

#define KEYWORD(NAME, TEXT)                               \ 
  addName(StringRef(TEXT), tok::NAME); 
#include "simple/Basic/TokenKinds.def" 

  Name::This = getName("this"); 
  Name::Super = getName("super"); 
  Name::New = getName("new"); 
  Name::Delete = getName("delete"); 
  Name::Ctor = addName("__ctor", tok::Identifier); 
  Name::Dtor = addName("__dtor", tok::Identifier); 

  IsInit = true; 
} 

Правок в синтаксическом анализаторе будет побольше.

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

Hidden text
/// primary-expr 
///   ::= floating-point-literal 
///   ::= integral-literal 
///   ::= '.'? identifier 
///   ::= char-literal 
///   ::= string-literal 
///   ::= '(' expr ')' 
///   ::= 'this' 
///   ::= 'super'
ExprAST *Parser::parsePrimaryExpr() { 
  ExprAST *result = nullptr; 

  switch (CurPos->getKind()) { 
    ...
    case tok::Super: 
      result = new IdExprAST(CurPos.getLocation(), Name::Super); 
      ++CurPos; 
      return result; 

    case tok::This: 
      result = new IdExprAST(CurPos.getLocation(), Name::This); 
      ++CurPos; 
      return result; 
     ...
  } 
}

Поддержка создания экземпляра класса через оператор "new":

Hidden text
/// unary-expr 
///   ::= postfix-expr 
///   ::= '+' unary-expr 
///   ::= '-' unary-expr 
///   ::= '++' unary-expr 
///   ::= '--' unary-expr 
///   ::= '~' unary-expr 
///   ::= '!' unary-expr 
///   ::= '*' unary-expr 
///   ::= '&' unary-expr 
///   ::= 'del' unary-expr 
///   ::= new-expr 
/// new-expr 
///   ::= 'new' type [' assign-expr ']' 
///   ::= 'new' type ('(' call-arguments? ')') ?
ExprAST *Parser::parseUnaryExpr() { 
  ExprAST *result = nullptr; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (int op = CurPos->getKind()) { 
    ...
    case tok::New: { 
      // Это операция выделения памяти. Пропускаем "new"
      ++CurPos; 
      // Считываем тип
      TypeAST *type = parseType(); 
      ExprList args; 
      ExprAST *dynamicSize = nullptr; 

      // Проверяем "[" expression "]" , т. к. "[" integral-literal
      // "]" может быть обработано ранее в parseType 
      if (CurPos == tok::OpenBrace) { 
        // Проверяем, что слева от "[" у нас нету структуры или 
        // класса, т. к. мы их не поддерживаем
        if (isa<QualifiedTypeAST>(type)) { 
          getDiagnostics().report(CurPos.getLocation(), 
                                  diag::ERR_DynArrayAggregate); 
        } 
       // Пропускаем "[" и считываем выражение между "[" и "]"
        ++CurPos; 
        dynamicSize = parseAssignExpr(); 
        // Проверяем наличие "]"
        check(tok::CloseBrace); 
      }
      // Если тип является полным (может быть именем класса или 
      // структуры), а так же текущий токен является "(", то нужно 
      // считать аргументы для конструктора
      if (isa<QualifiedTypeAST>(type) && CurPos == tok::OpenParen) { 
        // Пропустить "("
        ++CurPos; 

        // Проверяем наличие аргументов (может быть вызов 
        // конструктора без аргументов)
        if (CurPos != tok::CloseParen) { 
          for (;;) { 
            // Считываем выражение аргумента
            ExprAST *arg = parseAssignExpr(); 
            args.push_back(arg); 
            // Проверяем на наличие ","
            if (CurPos != tok::Comma) { 
              // Нет, завершаем разбор аргументов
              break; 
            } 
            // Считываем "," и переходим к следующему аргументу
            ++CurPos; 
          } 
        } 
        // Проверяем на наличие ")"
        check(tok::CloseParen); 
      } 
      // Создаем ветку дерева
      return new NewExprAST(loc, type, dynamicSize, args); 
    } 

    default: 
      return parsePostfixExpr(); 
  } 
} 

Небольшая правка в разборе прототипа функции, для поддержки нового конструктора:

Hidden text
SymbolAST *Parser::parseFuncProto() { 
  ...
  return new FuncDeclAST(loc, returnType, name, nullptr, false, Tok); 
}

Добавляем поддержку методов класса:

Hidden text
/// func-decl ::= func-decl-kwd func-proto block-stmt 
/// func-decl-kwd 
///   ::= 'fn' 
///   ::= 'virt' 
///   ::= 'impl'
SymbolList Parser::parseFuncDecl(bool isClassMember)) { 
  // Чтение прототипа функции
  SymbolList result; 
  FuncDeclAST *decl = (FuncDeclAST *)parseFuncProto(); 
 
  if (CurPos != tok::BlockStart) { 
    // Отсутствие "{" является ошибкой
    getDiagnostics().report(CurPos.getLocation(),
                            diag::ERR_ExpectedFuncBody); 
  } else { 
    // Считываем тело функции
    StmtAST *body = parseStmt(); 
    // Добавляем тело к прототипу функции
    decl->Body = body;
    // Сохраняем флаг того, что это метод класса или нет
    decl->NeedThis = isClassMember; 
    // Добавляем созданное объявление функции к результирующим 
    // объявлениям
    result.push_back(decl); 
  } 

  return result; 
} 

Поддержка классов и специальных функций:

Hidden text
/// decl 
///  ::= func-decl 
///  ::= dtor-decl 
///  ::= struct-decl 
///  ::= class-decl 
/// 
/// decls 
///  ::= decl 
///  ::= decls decl 
/// 
/// struct-decl 
///  ::= 'struct' identifier '{' decl-stmt * '}' 
/// 
/// class-decl 
///  ::= 'class' identifier ( 'extends' type ) ? '{' decls '}' 
/// 
/// dtor-decl ::= ('virt' | 'impl')? 'del' '(' ')' block-stmt
/// ctor-decl
///   ::= 'new' '(' parameters-list ? ')' base-ctor-call ? block-stmt 
/// base-ctor-call ::= ':' 'super' '(' call-arguments ? ')'
SymbolList Parser::parseDecls(bool isClassMember) { 
  SymbolList result; 
  // Производим анализ всех доступных объявлений
  for (;;) { 
    SymbolList tmp; 
    llvm::SMLoc loc = CurPos.getLocation(); 

    switch (int Tok = CurPos->getKind()) { 
      // Проверяем на виртуальные функции
      case tok::Virtual: 
      case tok::Override: 
        // Диагностируем об ошибке, если мы не разбираем класс
        if (!isClassMember) { 
          getDiagnostics().report(CurPos.getLocation(), 
            diag::ERR_VirtOverAsNonClassMember); 
          return result; 
        } 
        // Пропускаем ключевое слово "virt" или "impl"
        ++CurPos; 
        // Если это не "del", то мы должны обработать как обычную
        // функцию
        if (CurPos != tok::Delete) { 
          --CurPos; 
          tmp = parseFuncDecl(isClassMember); 
          result.push_back(tmp.pop_back_val()); 
          continue; 
        } 
      // Это "del" (может быть виртуальным)
      case tok::Delete: { 
        // Диагностируем об ошибке, если мы не разбираем класс
        if (!isClassMember) { 
          getDiagnostics().report(CurPos.getLocation(), 
            diag::ERR_UnexpectedDestructorDecl); 
          return result; 
        } 
        // Проверяем наличие "del" "(" ")"
        check(tok::Delete); 
        check(tok::OpenParen); 
        check(tok::CloseParen); 
        // Диагностируем об ошибке, если отсутствует тело 
        // деструктора
        if (CurPos != tok::BlockStart) { 
          getDiagnostics().report(CurPos.getLocation(), 
                                  diag::ERR_ExpectedDestructorBody); 
          return result; 
        } 
        // Считываем тело деструктора
        StmtAST *body = parseStmt(); 
        ParameterList params; 
        // Создаем тип функции для деструктора и создание ветви 
        // дерева
        TypeAST *funcType = new FuncTypeAST(
          BuiltinTypeAST::get(TypeAST::TI_Void),
          params
        ); 
        result.push_back( 
            new FuncDeclAST(
              loc,
              funcType,
              Name::Dtor,
              body,
              true,
              Tok
            )
        ); 
        continue; 
      } 
 
      case tok::Def: 
        // Объявление функции. Считываем объявление функции и 
        // добавляем в список объявлений
        tmp = parseFuncDecl(isClassMember); 
        result.push_back(tmp.pop_back_val()); 
        continue; 
      // Проверяем на конструктор
      case tok::New: { 
        // Диагностируем об ошибке, если мы не разбираем класс
        if (!isClassMember) { 
          getDiagnostics().report(CurPos.getLocation(), 
            diag::ERR_UnexpectedConstructorDecl); 
          return result; 
        } 

        ExprAST *superCtorCall = nullptr; 
        ParameterList params; 
        // Пропускаем "new" и проверяем наличие "("
        ++CurPos; 
        check(tok::OpenParen); 
        // Проверяем на наличие параметров
        if (CurPos != tok::CloseParen) { 
          for (;;) { 
            Name *paramName = nullptr; 
            // Проверяем на наличие имени параметра
            if (CurPos == tok::Identifier) { 
              // Сохраняем имя параметра переходим к следующему 
              // токену
              paramName = CurPos->getIdentifier(); 
              ++CurPos; 

              // Проверяем на то, что это анонимный параметр
              if (strcmp(paramName->Id, "_") == 0) { 
                paramName = nullptr; 
              } 
            } else { 
              // Диагностика ошибки, т. к. отсутствует 
              // идентификатор
              check(tok::Identifier); 
            } 
            // Проверяем ":" и считываем тип параметра
            check(tok::Colon); 

            TypeAST *type = parseType(); 
            // Добавляем параметр к списку параметров
            params.push_back(new ParameterAST(type, paramName)); 
            // Проверяем на наличие ","
            if (CurPos != tok::Comma) { 
              // Нет, завершаем разбор параметров
              break; 
            } 
            // Считываем "," и переходим к следующему параметру
            ++CurPos; 
          } 
        } 
        // Проверяем на наличие ")"
        check(tok::CloseParen); 
        // Проверяем на наличие ":", для вызова конструктора 
        // родительского класса
        if (CurPos == tok::Colon) { 
          check(tok::Colon); 
          // Диагностируем ошибку в случае отсутствия "super"
          if (CurPos != tok::Super) { 
            getDiagnostics().report(CurPos.getLocation(), 
              diag::ERR_ExpectedSuperAfterNew); 
            return result; 
          } else { 
             // Пропускаем "super"
            ++CurPos; 
            // Проверяем на наличие "(", для аргументов 
            // конструктора
            if (CurPos != tok::OpenParen) { 
              getDiagnostics().report(CurPos.getLocation(), 
                diag::ERR_ExpectedFuncArguments); 
              return result; 
            } 
            // Пропускаем ","
            ++CurPos; 

            ExprList args; 

            // Проверяем на наличие аргументов для конструктора
            if (CurPos != tok::CloseParen) { 
              for (;;) { 
                // Считываем выражения для аргумента и добавляем 
                // его к списку аргументов
                ExprAST *arg = parseAssignExpr(); 
                args.push_back(arg); 

                // Проверяем на наличие ","
                if (CurPos != tok::Comma) { 
                  // Нет, завершаем разбор аргументов
                  break; 
                } 
                // Считываем "," и переходим к следующему 
                // аргументу
                ++CurPos; 
              } 
            } 
            // Проверяем на наличие "("
            check(tok::CloseParen); 
            // Создаем выражение для вызова конструктора 
            // родительского класса
            superCtorCall = new CallExprAST( 
              loc, 
              new MemberAccessExprAST(
                loc,
                new IdExprAST(loc, Name::Super),                       
                Name::Ctor
              ), 
              args); 
          } 
        } 
        // Проверка на наличие тела конструктора
        if (CurPos != tok::BlockStart) { 
          getDiagnostics().report(CurPos.getLocation(), 
            diag::ERR_ExpectedConstructorBody); 
          return result; 
        } 
        // Считываем тело конструктора
        StmtAST *body = parseStmt(); 

        // Создаем функцию с телом вида: 
        // { 
        //   opt super.__ctor(args); 
        //   body 
        // } 
        StmtList ctorBody; 
        // Добавляем вызов конструктора родительского класса (если
        // он был указан)
        if (superCtorCall) { 
          ctorBody.push_back(new ExprStmtAST(loc, superCtorCall)); 
        } 
        // Создаем ветку для объявления конструктора
        ctorBody.push_back(body); 
        body = new BlockStmtAST(loc, ctorBody); 
        TypeAST *funcType = new FuncTypeAST(
          BuiltinTypeAST::get(TypeAST::TI_Void),
          params
        ); 
        result.push_back( 
            new FuncDeclAST(
              loc,
              funcType,
              Name::Ctor,
              body,
              true,
              tok::New
            )
        ); 
        continue; 
      } 
      ...
      // Считываем объявление класса
      case tok::Class: { 
        // Пропускаем "class"
        ++CurPos; 
        Name *name = nullptr; 
        TypeAST *baseType = nullptr; 

        if (CurPos == tok::Identifier) { 
          // Сохраняем имя класса, если оно есть
          name = CurPos->getIdentifier(); 
        } 
        // Проверяем наличие идентификатора или диагностируем об 
        // ошибке
        check(tok::Identifier); 
        // Проверяем наличия указания родительского класса
        if (CurPos == tok::Extends) { 
          // Пропускаем "extends"
          check(tok::Extends); 
          // Диагностируем об ошибки, если это не идентификатор или 
          // точка
          if (CurPos != tok::Identifier && CurPos != tok::Dot) { 
            getDiagnostics().report(CurPos.getLocation(), 
              diag::ERR_ExpectedQualifiedNameAsBase); 
            return result; 
          } 
          // Считываем тип базового класса
          baseType = parseType(); 
        } 
        // Проверяем на наличие тела класса
        check(tok::BlockStart); 
        // Считываем все объявления внутри класса
        while (CurPos != tok::BlockEnd && CurPos != tok::EndOfFile) {
          SymbolList tmp2 = parseDecls(true); 
          tmp.append(tmp2.begin(), tmp2.end()); 
        } 
        // Проверяем наличие "}" и создаем ветвь дерева
        check(tok::BlockEnd); 
        result.push_back(new ClassDeclAST(loc, name, baseType, tmp)); 
        continue; 
      } 
      // Проверяем на выходы из чтения объявлений
      case tok::BlockEnd: 
      case tok::EndOfFile: 
        break; 

      default: 
        if (isClassMember) { 
          // Если это объявление класса, то считываем объявление 
          // переменных
          SymbolList tmp2 = parseDecl(true, isClassMember); 
          result.append(tmp2.begin(), tmp2.end()); 
          continue; 
        } 
        break; 
    } 

    break; 
  } 

  return result; 
} 

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

Hidden text
/// module-decl ::= decls 
ModuleDeclAST *Parser::parseModule() { 
  SymbolList decls = parseDecls(false); 

  if (CurPos != tok::EndOfFile) { 
    getDiagnostics().report(CurPos.getLocation(),
                            diag::ERR_ExpectedEndOfFile); 
    return nullptr; 
  } 

  return new ModuleDeclAST(getDiagnostics(), decls); 
} 

Поддержка инициализации объектов класса с помощью вызова конструктора класса:

Hidden text
/// var-init 
///   ::= '=' assign-expr 
///   ::= '(' call-arguments ? ')' 
/// var-decl ::= identifier ':' type var-init? 
/// var-decls 
///   ::= var-decl 
///   ::= var-decls ',' var-decl 
/// decl-stmt ::= var-decls ';'
SymbolList Parser::parseDecl(bool needSemicolon, bool isClassMember) { 
  SymbolList result; 
 // Производим анализ списка объявлений переменных
  for (;;) { 
    llvm::SMLoc loc = CurPos.getLocation(); 

    if (CurPos != tok::Identifier) { 
      // Объявление всегда должно начинаться с идентификатора, если
      // это что-то другое, то сообщаем об ошибке
      getDiagnostics().report(CurPos.getLocation(),
                              diag::ERR_ExpectedIdentifierInDecl); 
    } else { 
      // Сохраняем имя переменной
      Name *name = CurPos->getIdentifier(); 
      ExprAST *value = nullptr; 
     // Переходим к следующему токену
      ++CurPos; 
      // Проверяем на наличие ":"
      check(tok::Colon); 
      // Считываем тип переменной
      TypeAST *type = parseType(); 

      if (CurPos == tok::Assign) { 
        // Запрещаем инициализаторы для массивов и структур/классов
        if (isa<ArrayTypeAST>(type) || isa<QualifiedTypeAST>(type)) { 
          getDiagnostics().report(CurPos.getLocation(), 
            diag::ERR_AggregateOrArrayInitializer); 
          return result; 
        } 
        // Если у переменной есть инициализатор, то считываем "=" и 
        // инициализирующее значение
        ++CurPos; 
        value = parseAssignExpr(); 
      } 
      // Проверяем, что тип является именем класса и есть "("
      if (isa<QualifiedTypeAST>(type) && CurPos == tok::OpenParen) { 
        // Пропускаем "("
        ++CurPos; 

        ExprList args; 

        // Проверяем на наличие аргументов для конструктора
        if (CurPos != tok::CloseParen) { 
          for (;;) { 
            // Считываем выражения для аргумента и добавляем его к 
            // списку аргументов
            ExprAST *arg = parseAssignExpr(); 
            args.push_back(arg); 

            // Проверяем на наличие ","
            if (CurPos != tok::Comma) { 
              // Нет, завершаем разбор аргументов
              break; 
            } 
            // Считываем "," и переходим к следующему аргументу
            ++CurPos; 
          } 
        } 
        // Проверяем на наличие "("
        check(tok::CloseParen); 
        // Создаем вызов конструктора класса
        value = new CallExprAST( 
          loc, 
          new MemberAccessExprAST(
            loc,
            new IdExprAST(loc, name),
            Name::Ctor
          ), 
          args); 
      } 
      // Добавляем новое объявление переменной
      result.push_back(
        new VarDeclAST(loc, type, name, value, isClassMember)
      ); 
      // Проверяем на наличие ","
      if (CurPos != tok::Comma) { 
        // Нет, завершаем разбор объявлений переменных
        break; 
      } 
      // Считываем "," и переходим к следующему объявлению
      ++CurPos; 
    } 
  } 
  // Считываем ";", если нужно
  if (needSemicolon) { 
    check(tok::Semicolon); 
  } 

  return result; 
} 

Добавляем поддержку новых выражений:

Hidden text
/// block-stmt ::= '{' stmt* '}' 
/// for-init 
///   ::= 'let' decl-stmt 
///   ::= expr 
/// for-stmt ::= 'for' for-init? ';' expr? ';' expr? block-stmt 
/// stmt 
///   ::= expr? ';' 
///   ::= 'let' decl-stmt 
///   ::= 'if' expr block-stmt ( 'else' block-stmt )? 
///   ::= 'while' expr block-stmt 
///   ::= for-stmt 
///   ::= 'break' 
///   ::= 'continue' 
///   ::= 'return' expr? ';' 
///   ::= block-stmt 
StmtAST *Parser::parseStmt() { 
  StmtAST *result = nullptr; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (CurPos->getKind()) { 
    ...
    case tok::Plus: 
    case tok::Minus: 
    case tok::PlusPlus: 
    case tok::MinusMinus: 
    case tok::Tilda: 
    case tok::Not: 
    case tok::Identifier: 
    case tok::IntNumber: 
    case tok::FloatNumber: 
    case tok::Super: 
    case tok::This: 
    case tok::OpenParen: 
    case tok::Delete: 
    case tok::Mul: 
    case tok::BitAnd: 
    case tok::New: 
    case tok::Dot: { 
      ExprAST *expr = parseExpr(); 
      check(tok::Semicolon); 
      return new ExprStmtAST(loc, expr); 
    } 
    ...
  } 
} 

Семантический анализ

Для начала рассмотрим правки, которые нужно внести в структуре дерева:

Добавить поддержку нового типа:

struct TypeAST { 
  enum TypeId { 
    TI_Void,     ///< void 
    TI_Bool,     ///< булево значение 
    TI_Int,      ///< int
    TI_Float,    ///< float 
    TI_Char,     ///< char
    TI_String,   ///< string 
    TI_Pointer,  ///< указатель 
    TI_Array,    ///< массив 
    TI_Class,    ///< класс
    TI_Struct,   ///< структура 
    TI_Function, ///< функция 
    TI_Qualified ///< квалифицированное имя (полное имя класса или структуры)
  }; 
  ...
  /// Проверка на то, что это тип структуры или класса
  bool isAggregate() { 
    return TypeKind == TI_Class || TypeKind == TI_Struct; 
  } 
  ...
  /// Проверка на то, что данный тип является базовым для type 
  virtual bool isBaseOf(TypeAST* type); 
}; 

Для объявлений:

struct SymbolAST { 
  enum SymbolId { 
    SI_Variable,    ///< переменная
    SI_Struct,      ///< структура

    SI_Class,       ///< класс
    SI_Function,    ///< функция 
    SI_Module,      ///< модуль 
    SI_Parameter,   ///< параметр функции 
    SI_OverloadSet, ///< набор перегруженных функций
    SI_Block        ///< блочная декларация
    SI_Variable,    ///< variable declaration 
    SI_Struct,      ///< structure declaration 
    SI_Function,    ///< function declaration 
    SI_Module,      ///< module declaration 
    SI_Parameter,   ///< function's parameter declaration 
    SI_Block        ///< scope declaration 
  }; 
  ...
  /// Проверка на то, что символ является структурой или классом
  bool isAggregate() { 
    return SymbolKind == SI_Struct || SymbolKind == SI_Class; 
  } 
  ...
}; 

Добавить новую ветку для типов:

Hidden text
struct ClassTypeAST : TypeAST { 
  ClassTypeAST(SymbolAST* thisDecl) ;

  TypeAST* semantic(Scope* scope); 
  bool implicitConvertTo(TypeAST* newType); 
  void toMangleBuffer(llvm::raw_ostream& output); 
  bool isBaseOf(TypeAST* type); 
  SymbolAST* getSymbol(); 

  llvm::Type* getType(); 

  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Class; 
  } 

  SymbolAST* ThisDecl; ///< Объявление данного класса
}; 

Поддержку методов класса:

Hidden text
struct FuncTypeAST : TypeAST {
 ...
  bool HasThis; ///< true — Если это метод класса 
};

Поддержка вызова конструкторов и деструкторов для вызовов "new" и "del":

Hidden text
struct MemberAccessExprAST : ExprAST { 
  MemberAccessExprAST(llvm::SMLoc loc, ExprAST *val, Name *memberName) ;
  MemberAccessExprAST(llvm::SMLoc loc, SymbolAST *aggrSym, 
    ExprAST* forcedThis, Name* memberName) ;
  ...
  /// true — если "this" задан извне (используется для вызова 
  /// конструкторов и деструкторов после вызова операторов
  /// "new" и "del")
  bool ForceThis;
}; 

Поддержка вызовов деструкторов в блоках:

Hidden text
struct BlockStmtAST : StmtAST { 
  ~BlockStmtAST() { 
    for (StmtList::iterator it = Body.begin(), end = Body.end();
         it != end; ++it) { 
      delete *it; 
    } 

    delete ThisBlock; 
    delete LandingPad; 

    for (ExprList::iterator it = CleanupList.begin(),
         end = CleanupList.end(); it != end; ++it) { 
      delete *it; 
    } 
  } 
 ...
  /// Список объектов для которых нужно вызвать деструкторы по выходу
  /// из блока
  ExprList CleanupList; 
}; 

Поддержка объявления классов:

Hidden text
/// Класс для хранения информации о виртуальных методах
struct VTableAST { 
  VTableAST(SymbolAST* parent) 
    : Parent(parent), 
      CurOffset(0), 
      CodeValue(nullptr), 
      VTblType(nullptr) { 
  } 

  /// Проверка на то, что функция существует в таблице виртуальных
  /// методов
  /// \param[in] func — функция для поиска
  bool isExist(SymbolAST* func); 
  /// Создать копию таблицы виртуальных методов родительского класса
  VTableAST* clone(SymbolAST* parent); 
  /// Добавить новый метод в таблицу виртуальных методов или 
  /// заменить версию родительского класса
  void addOrReplace(Scope *scope, SymbolAST* func); 
  /// Сгенерировать код для таблицы виртуальных методов
  /// \param[in] Context - контекст
  llvm::Value* generateCode(SLContext& Context); 

  SymbolAST* Parent; ///< Класс владелец 
  /// Таблица виртуальных методов
  typedef std::map< Name*, SymbolAST* > SymbolMap; 
  SymbolMap Decls; ///< Объявленные виртуальные методы
  int CurOffset; ///< Последний свободный слот в таблице
  llvm::Value* CodeValue; ///< Сгенерированная таблица
  llvm::Type* VTblType; ///< Тип для сгенерированной таблицы 

private: 
  /// Конструктор 
  /// \param[in] other — таблица для копирования
  /// \param[in] parent — класс владелец
  VTableAST(const VTableAST& other, SymbolAST* parent) 
    : Parent(parent), 
      Decls(other.Decls), 
      CurOffset(other.CurOffset), 
      CodeValue(nullptr), 
      VTblType(nullptr) { 
  } 
}; 
Создать ветку дерева для класса:
struct ClassDeclAST : ScopeSymbol { 
  /// Конструктор
  /// \param[in] loc — расположение в исходном коде
  /// \param[in] id — имя класса
  /// \param[in] baseClass — родительский класс (может быть nullptr)
  /// \param[in] vars — список членов класса
  ClassDeclAST(llvm::SMLoc loc, Name *id, TypeAST *baseClass, 
    const SymbolList& vars) 
    : ScopeSymbol(loc, SI_Class, id), 
      BaseClass(baseClass), 
      Vars(vars), 
      ThisType(nullptr), 
      Ctor(false), 
      Dtor(false), 
      VTbl(nullptr), 
      OwnVTable(false) { 
    ThisType = new ClassTypeAST(this); 
  } 

  ~ClassDeclAST() { 
    for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
      it != end; ++it) { 
      delete *it; 
    } 

    if (OwnVTable) { 
      delete VTbl; 
    } 
  } 

  TypeAST* getType(); 
  void doSemantic(Scope* scope); 
  void doSemantic2(Scope* scope); 
  void doSemantic3(Scope* scope); 
  void doSemantic4(Scope* scope); 
  void doSemantic5(Scope* scope); 
  bool contain(TypeAST* type); 

  llvm::Value* getValue(SLContext& Context); 
  llvm::Value* generateCode(SLContext& Context); 

  SymbolAST* find(Name* id, int flags = 0); 

  static bool classof(const SymbolAST *T) { 
    return T->SymbolKind == SI_Class; 
  } 

  TypeAST* BaseClass; ///< базовый класс
  SymbolList Vars; ///< список членов класса
  TypeAST* ThisType; ///< сгенерированный тип
  bool Ctor; ///< true — если был объявлен хотя бы один конструктор
  bool Dtor; ///< true — если был объявлен деструктор
  /// таблица виртуальных методов (может быть nullptr) 
  VTableAST* VTbl;
  /// true — если имеет свою VTable (отличную от родительского
  /// класса) 
  bool OwnVTable;
}; 

Поддержку методов класса:

Hidden text
struct FuncDeclAST : ScopeSymbol { 
  FuncDeclAST(llvm::SMLoc loc, TypeAST *funcType, Name *id, 
    StmtAST* body, bool inClass, int tok = tok::Def) ;
  ...
  /// Это объявление виртуального метода 
  bool isVirtual() { 
    return Tok == tok::Virtual; 
  } 
  /// Это объявление переопределенного виртуального метода
  bool isOverride() { 
    return Tok == tok::Override; 
  } 
  /// Конструктор класса
  bool isCtor() { 
    return Id == Name::Ctor; 
  } 
  /// Деструктор класса 
  bool isDtor() { 
    return Id == Name::Dtor; 
  } 

  bool needThis(); 
  ...
  bool NeedThis; ///< true — метод класса
  int OffsetOf; ///< индекс метода в таблице виртуальных методов
  SymbolAST* AggregateSym; ///< родительский класс
}; 

Поддержка перегрузки функций:

Hidden text
struct OverloadSetAST : SymbolAST { 
  OverloadSetAST(Name* name);

  /// Добавить новую функцию к списку перегруженных функций 
  void push(Scope *scope, SymbolAST* func); 

  OverloadSetAST* clone();

  static bool classof(const SymbolAST *T) { 
    return T->SymbolKind == SI_OverloadSet; 
  } 

  SymbolList Vars; ///< список всех перегруженных функций 
  /// набор уникальных перегрузок, для исключения дублей
  llvm::StringSet< > OverloadsUsed;
}; 

Правки для LandingPadAST (более подробно будем рассматривать дальше):

struct LandingPadAST { 
  LandingPadAST(LandingPadAST* prev, bool needCleanup);
  LandingPadAST();
  ... 
  /// Получить переменную со статусом очистки
  llvm::Value* getCleanupValue(); 
  ...
  bool NeedCleanup; ///< true — если нужно произвести очистку
  /// статус очистки (необходимо вызывать getCleanupValue) 
  llvm::Value* CleanupValue;
  llvm::BasicBlock* CleanupLoc; ///< блок очистки
}; 

Семантика типов

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

Hidden text
bool TypeAST::isBaseOf(TypeAST* ) {
  return false;
}

TypeAST* ArrayTypeAST::semantic(Scope* scope) {
  // Проверить семантику базового типа
  Next = Next->semantic(scope);

  // Запрешаем массивы объектов классов
  if (isa<ClassTypeAST>(Next)) {
    scope->report(SMLoc(), diag::ERR_SemaArrayOfClassUnsupported);
    return nullptr;
  }

  // создаем MangleName
  calcMangle();
  return this;
}


bool PointerTypeAST::implicitConvertTo(TypeAST* newType) {
  // Разрешаем преобразование указателя в bool
  if (newType->isBool()) {
    return true;
  }
  
  // Разрешаем преобразование char* в string
  if (Next->isChar() && newType->isString()) {
    return true;
  }
  
  // Запрещаем любое преобразование в тип отличный от указателя
  if (!isa<PointerTypeAST>(newType)) {
    return false;
  }

  PointerTypeAST* ptr2 = (PointerTypeAST*)newType;
  // Получаем базовый тип для newType
  TypeAST* next2 = ptr2->Next;

  // Разрешаем преобразование, если типы совпадают
  if (Next->equal(next2)) {
    return true;
  }

  // Если оба типа на которые указывают указатели являются
  // агрегатами, то нужно проверить, что тип, в который нужно
  // произвести преобразование является базовым для текущего
  if (Next->isAggregate() && next2->isAggregate()) {
    return next2->isBaseOf(Next);
  }

  TypeAST* next1 = Next;

  // Разрешаем преобразование указателя любого типа в void*
  if (next2->isVoid()) {
    return true;
  }

  return false;
}

bool StructTypeAST::isBaseOf(TypeAST* type) {
  // Только классы могут иметь родительский класс или структуру
  if (!isa<ClassTypeAST>(type)) {
    return false;
  }

  ClassTypeAST* classType = (ClassTypeAST*)type;
  ClassDeclAST* classDecl = (ClassDeclAST*)classType->ThisDecl;

  // Если этот тип и базовый совпадают, то возвращаем "true"
  if (classDecl->BaseClass && this->equal(classDecl->BaseClass)) {
    return true;
  }

  // Если класс имеет базовый класс, то вызываем метод повторно,
  // но для родительского класса
  if (classDecl->BaseClass) {
    return isBaseOf(classDecl->BaseClass);
  }

  return false;
}

Добавляем тип для классов:

Hidden text
TypeAST* ClassTypeAST::semantic(Scope* scope) {
  calcMangle();
  return this;
}

bool ClassTypeAST::implicitConvertTo(TypeAST* newType) {
  if (newType->equal(this)) {
    return true;
  }
  
  return false;
}

void ClassTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
  mangleAggregateName(output, ThisDecl);
}

bool ClassTypeAST::isBaseOf(TypeAST* type) {
  // Только классы могут иметь родительский класс или структуру
  if (!isa<ClassTypeAST>(type)) {
    return false;
  }

  ClassTypeAST* classType = (ClassTypeAST*)type;
  ClassDeclAST* classDecl = (ClassDeclAST*)classType->ThisDecl;

  // Если этот тип и родительский совпадают, то возвращаем "true"
  if (classDecl->BaseClass && this->equal(classDecl->BaseClass)) {
    return true;
  }

  // Если класс имеет базовый класс, то вызываем метод повторно,
  // но для родительский класса
  if (classDecl->BaseClass) {
    return isBaseOf(classDecl->BaseClass);
  }

  return false;
}

SymbolAST* ClassTypeAST::getSymbol() {
  return ThisDecl;
}

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

Hidden text
void FuncTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
  // Добавляем "v", если у функции нет параметров
  if (Params.empty()) {
    output << "v";
    return;
  }

  ParameterList::iterator it = Params.begin(), end = Params.end();
  // Пропускаем параметр для "this"
  if (HasThis) {
    ++it;
  }
  // Добавляем "v", если у функции нет параметров, кроме "this"
  if (it == end) {
    output << "v";
    return;
  }
  // Произвести декорацию имен для всех параметров
  for ( ; it != end; ++it) {
    (*it)->Param->toMangleBuffer(output);
  }
}

Семантика выражений для поддержки классов и перегрузки функций

Поддержка классов для оператора "new":

Hidden text
ExprAST* NewExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (ExprType) {
    return this;
  }

  // Производим семантический анализ для типа
  NewType = NewType->semantic(scope);

  // Проверяем на то, что это массив с фиксированным размером
  if (isa<ArrayTypeAST>(NewType) && !DynamicSize) {
    // Мы выделяем память как для массива, но результирующий тип
    // будет указателем
    ArrayTypeAST* arrayType = (ArrayTypeAST*)NewType;
    ExprType = new PointerTypeAST(arrayType->Next, false);
    ExprType = ExprType->semantic(scope);
  } else {
    // Результирующий тип будет указателем
    ExprType = new PointerTypeAST(NewType, false);
    ExprType = ExprType->semantic(scope);
  }

  // Создаем новое выражение для хранения размера NewType на целевой 
  // платформе и оборачиваем его в прокси, т. к. реальный размер 
  // будет известен только во время генерации кода
  SizeExpr = new IntExprAST(Loc, 0);
  ExprAST* proxy = new ProxyExprAST(Loc, SizeExpr);

  if (DynamicSize) {
    proxy = new BinaryExprAST(Loc, tok::Mul, DynamicSize, proxy);
  }

  // Создаем вызов функции allocMem для выделения блока памяти
  // нужного размера
  ExprList args;
  args.push_back(proxy);
  CallExpr = new CallExprAST(
    Loc,
    new IdExprAST(Loc, Name::New),
    args
  );

  // Для классов мы должны произвести вызов конструктора, если он 
  // есть
  if (isa<ClassTypeAST>(NewType)) {
    ClassDeclAST* classDecl = (ClassDeclAST*)NewType->getSymbol();

    if (classDecl->Ctor) {
      // Если класс имеет конструктор, то нужно сгенерировать его
      // вызов
      // Замечание: в качестве "this" для вызова конструктора, мы 
      // должны использовать результат вызова "allocMem"
      CallExpr = new CallExprAST(
        Loc,
        new MemberAccessExprAST(
          Loc,
          classDecl,
          CallExpr,
          Name::Ctor
        ), 
        Args);
      // Нам не нужно производить преобразование типа, т. к. 
      // конструктор вернет указатель нужного типа
      NeedCast = false;
    }
  }

  // Производим семантический анализ только что созданного вызова 
  // функции
  CallExpr = CallExpr->semantic(scope);

  return this;
}

Поддержка классов для оператора "del":

Hidden text
ExprAST* DeleteExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (DeleteCall) {
    return this;
  }

  // Производим семантический анализ выражения для очистки
  Val = Val->semantic(scope);

  // Запрещаем удаление выражений с типом void
  if (!Val->ExprType || Val->ExprType->isVoid()) {
    scope->report(Loc, diag::ERR_SemaCantDeleteVoid);
    return nullptr;
  }

  // Мы можем производить очистку только для указателей
  if (!isa<PointerTypeAST>(Val->ExprType)) {
    scope->report(Loc, diag::ERR_SemaCantDeleteNonPointer);
    return nullptr;
  }

  PointerTypeAST* ptrType = (PointerTypeAST*)Val->ExprType;

  ExprAST* deleteArg = Val->clone();
  ExprList args;
  
  // Для классов с деструкторами, мы должны произвести его вызов
  if (isa<ClassTypeAST>(ptrType->Next)) {
    ClassDeclAST* classDecl =
      (ClassDeclAST*)ptrType->Next->getSymbol();

    if (classDecl->Dtor) {
      // Создаем вызов деструктора
      // Замечание: В качестве "this" мы используем результат 
      // кодогенерации для Val
      deleteArg = new CallExprAST(
        Loc,
        new MemberAccessExprAST(
          Loc,
          classDecl, 
          deleteArg, 
          Name::Dtor
        ),
        args);
    }
  }

  // Создаем список аргументов для вызова freeMem
  // Замечание: Это может быть либо Val, либо результат вызова 
  // деструктора
  args.push_back(deleteArg);
  
  // Создание вызова freeMem и проверка его семантики
  DeleteCall = new CallExprAST(
    Loc, 
    new IdExprAST(Loc, Name::Delete), 
    args
  );
  DeleteCall = DeleteCall->semantic(scope);

  ExprType = BuiltinTypeAST::get(TypeAST::TI_Void);

  return this;
}

Поддержка обращения к членам класса без явного указания объекта класса в его методах:

Hidden text
ExprAST* IdExprAST::semantic(Scope* scope) {
  // Если "ThisSym" задан, то семантический анализ над данным
  // выражением уже был ранее завершен
  if (!ThisSym) {
    // Ищем объявление в текущей области видимости
    ThisSym = scope->find(Val);

    if (!Val) {
      return this;
    }

    if (!ThisSym) {
      // Объявление не найдено, возвращаем ошибку
      scope->report(Loc, diag::ERR_SemaUndefinedIdentifier, Val->Id);
      return nullptr;
    }
    // Если это член класса, то мы должны произвести специальную 
    // обработку
    if (ThisSym->needThis()) {
      // Заменить выражение на this . a
      IdExprAST* thisExpr = new IdExprAST(Loc, Name::This);
      PointerAccessExprAST* memberExpr =
        new PointerAccessExprAST(Loc, thisExpr, Val);
      // Производим семантический анализ нового выражения и удаляем
      // старое
      ExprAST* resultExpr = memberExpr->semantic(scope);
      delete this;
      return resultExpr;
    }
    // Устанавливаем тип данного выражения в соответствии с типом
    // объявленной переменной (за исключением набора перегруженных
    // функций, т. к. реальный тип мы можем узнать только во время
    // вызова функции)
    if (!isa<OverloadSetAST>(ThisSym)) {
      ExprType = ThisSym->getType();
    }
  }

  return this;
}

Поддержка новых возможностей для обращения к методам и переменным агрегатов:

Hidden text
ExprAST* MemberAccessExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (SemaDone) {
    return this;
  }
  // Проверяем семантику левого операнда
  Val = Val->semantic(scope);

  // Специальная обработка для символа в глобальной области
  // видимости
  if (isa<IdExprAST>(Val) && !((IdExprAST*)Val)->Val) {
    // Получить объявление модуля
    SymbolAST* moduleSym = scope->find(0);
    assert(moduleSym);
    // Поиск объявления в модуле
    SymbolAST* thisSym = moduleSym->find(MemberName);

    // Диагностика ошибки, если символ не найден
    if (!thisSym) {
      scope->report(Loc, diag::ERR_SemaUndefinedMember,
                    MemberName->Id);
      return nullptr;
    }

    // Заменяем MemberAccessExprAST на IdExprAST с 
    // предопределенными значениями
    IdExprAST* newExpr = new IdExprAST(Loc, MemberName);

    // Устанавливаем тип найденного символа (за исключением 
    // набора перегруженных функций, т. к. реальный тип мы можем 
    // узнать только во время вызова функции)
    if (!isa<OverloadSetAST>(thisSym)) {
      newExpr->ExprType = thisSym->getType();
    }

    newExpr->ThisSym = thisSym;
    delete this;
    return newExpr;
  }

  // Специальная обработка для вариантов, когда "this", был явно 
  // указан извне
  if (ForceThis) {
    // Проверяем, что это агрегат
    if (!ThisAggr->isAggregate()) {
      scope->report(Loc, diag::ERR_SemaNonAggregateForFocedThis);
      return nullptr;
    }

    // Пытаемся найти символ в агрегате
    ThisSym = ThisAggr->find(MemberName);
    // Диагностируем об ошибке, в случае его отсутствия
    if (!ThisSym) {
      scope->report(Loc, diag::ERR_SemaUndefinedMember,
                    MemberName->Id);
      return nullptr;
    }
    // Устанавливаем тип найденного символа (за исключением набора 
    // перегруженных функций, т. к. реальный тип мы можем узнать 
    // только во время вызова функции)
    if (!isa<OverloadSetAST>(ThisSym)) {
      ExprType = ThisSym->getType();
    }

    SemaDone = true;
    return this;
  }
  
  // Проверяем на корректность типа операнда
  if (!Val->ExprType) {
    scope->report(Loc, diag::ERR_SemaInvalidOperandForMemberAccess);
    return nullptr;
  }

  // Если Val является указателем на агрегат, то нам нужно 
  // произвести разыменование указателя. Т.е. в семантики C++, 
  // мы считаем agg->a эквивалентом (*agg).a
  if (isa<PointerTypeAST>(Val->ExprType) && 
    ((PointerTypeAST*)Val->ExprType)->Next->isAggregate()) {
    Val = new DerefExprAST(Loc, Val);
    Val = Val->semantic(scope);
  }

  // Val должно быть lvalue
  if (!Val->isLValue()) {
    scope->report(Loc, diag::ERR_SemaNonLValueForMemberAccess);
    return nullptr;
  }

  // Получить агрегат
  SymbolAST* aggSym = Val->getAggregate(scope);

  // Запрещаем использование A.b, где A — класс или структура. 
  // Это должно быть a.b, где a экземпляр A
  if (isa<IdExprAST>(Val) && aggSym && aggSym->isAggregate()) {
    // Check special case for base class function or variable
    scope->report(Loc, diag::ERR_SemaMemberAccessOnAggregateType);
    return nullptr;
  }

  // Исключаем операции над не агрегатами
  if (!aggSym || !aggSym->getType()->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaNonAggregateDotOperand);
    return nullptr;
  }

  // Получить объявление агрегата
  if (!aggSym->isAggregate()) {
    aggSym = aggSym->getType()->getSymbol();
  }

  // Поиск символа в агрегате
  ThisSym = aggSym->find(MemberName);
  ThisAggr = aggSym;

  // Проверка на то, что данный агрегат имеет член с таким именем
  if (!ThisSym) {
    scope->report(Loc, diag::ERR_SemaUndefinedMember,
                  MemberName->Id);
    return nullptr;
  }
  
  // Запрет конструкции вида a.A, где A это агрегат
  if (ThisSym->isAggregate()) {
    scope->report(Loc,
                  diag::ERR_SemaAggregateTypeAsMemberAccessOperand);
    return nullptr;
  }
  // Устанавливаем тип результата (за исключением набора 
  // перегруженных функций, т. к. реальный тип мы можем узнать 
  // только во время вызова функции)
  if (!isa<OverloadSetAST>(ThisSym)) {
    ExprType = ThisSym->getType();
  }

  SemaDone = true;

  return this;
}

Поддержка клонирования с учетом новой логики работы обращению к членам агрегата:

Hidden text
ExprAST* MemberAccessExprAST::clone() {
  if (ForceThis) {
    return new MemberAccessExprAST(Loc, ThisAggr, Val->clone(),
                                   MemberName);
  } else {
    return new MemberAccessExprAST(Loc, Val->clone(), MemberName);
  }
}

Выбор функции для вызова при перегрузке функций

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

Для начала нам нужно объявить два типа перечислений.

  1. Для указания того что функция или параметр функции является лучшим, худшим вариантом из 2-х предоставленных или выбор не может быть сделан (например варианты равнозначны);

  2. Для типа преобразования на основе которого уже можно будет производить сравнение параметров.

enum class OverloadCompareKind {
  Better = -1,      // функция/параметр является лучшим кандидатом
  Unknown = 0, // определить нельзя
  Worse = 1        // функция/параметр является худшим кандидатом
};

enum class OverloadConversionType {
  Same = 0,                  ///< типы параметра и аргумента идентичны
  /// преобразование является приведения указателя к указателю на "void"
  PointerToVoid = 1,
  /// преобразование является приведение дочернего типа к родительскому типу
  DerivedToBase = 2,
  /// базовое преобразование языка (например int -> float)
  Implicit = 3,             
};

Дальше нам нужен механизм для определения того, какой тип преобразования необходим для преобразования типа аргумента для вызова к типу параметра функции:

Hidden text
static OverloadConversionType getConversionLevel(
  TypeAST *arg, TypeAST *param) {
  // Типы совпадают
  if (arg->equal(param)) {
    return OverloadConversionType::Same;
  }

  // Проверка для указателей
  if (isa<PointerTypeAST>(param)) {
    TypeAST* ptr1 = ((PointerTypeAST*)param)->Next;
    TypeAST* ptr2 = ((PointerTypeAST*)arg)->Next;

    // Проверяем на преобразование указателя в указатель на "void"
    if (ptr1->isVoid()) {
      return OverloadConversionType::PointerToVoid;
    }
    // Если это агрегатный тип, то необходимо проверить приведение к
    // родительскому типу
    if (ptr1->isAggregate() && ptr1->isBaseOf(ptr2)) {
      return OverloadConversionType::DerivedToBase;
    }
  }
  // Базовое преобразование
  return OverloadConversionType::Implicit;
}

Дальше нам нужен механизм проверки одного параметра 2-х кандидатов:

Hidden text
static OverloadCompareKind compareConversion(
  TypeAST *arg,
  TypeAST *left,
  TypeAST *right
) {
  // Получаем типа преобразования для каждого кандидата
  OverloadConversionType
    Level1 = getConversionLevel(arg, left),
    Level2 = getConversionLevel(arg, right);
  // Проверяем особые варианты, если типы преобразования не 
  // совпадают для обоих кандидатов
  if (Level1 != Level2) {
    // Если типы аргумента и параметра 1-го кандидата совпадают, 
    // то 1-й кандидат лучше
    if (Level1 == OverloadConversionType::Same) {
      return OverloadCompareKind::Better;
    }
    // Если типы аргумента и параметра 2-го кандидата совпадают, 
    // то 1-й кандидат хуже
    if (Level2 == OverloadConversionType::Same) {
      return OverloadCompareKind::Worse;
    }
  }

  // Сравниваем типы преобразований обоих кандидатов с 
  // преобразованием указателя в указатель на "void"
  bool ConversionToVoid1 =
    Level1 == OverloadConversionType::PointerToVoid;
  bool ConversionToVoid2 =
    Level2 == OverloadConversionType::PointerToVoid;

  // Проверяем, что один из кандидатов имеет лучшее преобразование, 
  // чем преобразование указателя к указателю на "void"
  if (ConversionToVoid1 != ConversionToVoid2) {
    // Если 2-й кандидат является преобразованием указателя к 
    // указателю на "void", то 1-й кандидат является лучшим, 
    // иначе 1-й кандидат хуже
    return ConversionToVoid2
      ? OverloadCompareKind::Better
      : OverloadCompareKind::Worse;
  }

  // Сравниваем типы преобразований обоих кандидатов с 
  // преобразованием указателя на дочерний класс в указатель на
  // родительский класс
  bool ConversionToBase1 =
    Level1 == OverloadConversionType::DerivedToBase;
  bool ConversionToBase2 =
    Level2 == OverloadConversionType::DerivedToBase;

  // Проверяем вариант, когда типы преобразований обоих кандидатов
  // является преобразованием дочернего класса к родительскому 
  // классу
  if (ConversionToBase1 && ConversionToBase1 == ConversionToBase2) {
    TypeAST *to1 = ((PointerTypeAST*)left)->Next;
    TypeAST *to2 = ((PointerTypeAST*)right)->Next;

    // Если оба типа совпадают, то мы не можем однозначно определить
    // какой из кандидатов лучше
    if (to1->equal(to2)) {
      return OverloadCompareKind::Unknown;
    }
    // Замечание: Если у нас есть иерархия типов C -> B -> A, то 
    // преобразование C -> В лучше, чем преобразование C -> A
    // Проверяем на С -> A
    if (to1->isBaseOf(to2)) {
      return OverloadCompareKind::Worse;
    }
    // Это C -> B
    return OverloadCompareKind::Better;
  }
  // Мы не можем однозначно определить какой из кандидатов лучше
  return OverloadCompareKind::Unknown;
}

Теперь, когда мы можем сравнивать преобразование для параметра обоих кандидатов между собой, мы можем написать алгоритм, для сравнения двух функций между собой:

Hidden text
static bool isMoreSpecialized(
  CallExprAST *Call, SymbolAST* func1, SymbolAST* func2) {
  // Получаем типы обоих кандидатов
  FuncTypeAST* type1 = (FuncTypeAST*)((FuncDeclAST*)func1)->ThisType;
  FuncTypeAST* type2 = (FuncTypeAST*)((FuncDeclAST*)func2)->ThisType;

  // Получаем список аргументы и типы для вызова
  ExprList::iterator arg = Call->Args.begin();
  ParameterList::iterator it1 = type1->Params.begin();
  ParameterList::iterator it2 = type2->Params.begin();
  ParameterList::iterator end = type1->Params.end();

  // Если это функции методы класса, то игнорируем "this" при
  // сравнении кандидатов
  if (type1->HasThis) {
    ++arg;
    ++it1;
    ++it2;
  }

  // Проверяем все параметры кандидатов
  bool IsWorse = false;
  bool IsBetter = false;

  for ( ; it1 != end; ++arg, ++it1, ++it2) {
    OverloadCompareKind Kind = compareConversion(
      (*arg)->ExprType,
      (*it1)->Param,
      (*it2)->Param);
    // Определяем является ли текущий параметром первого кандидата
    // лучшим или худшим вариантом для вызова
    if (Kind == OverloadCompareKind::Better) {
      IsBetter = true;
    } else if (Kind == OverloadCompareKind::Worse) {
      IsWorse = true;
    }
  }

  // Если кандидат имеет хотя бы одно преобразование лучше, чем 2-й 
  // кандидат и не имеет ни одного преобразования хуже, то это 
  // лучший кандидат для вызова
  if (IsBetter && !IsWorse) {
    return true;
  }

  // Либо хуже, либо оба кандидаты равнозначны
  return false;
}

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

Hidden text
/// Предикат для сортировки кандидатов на вызов
struct OverloadSetSort: std::binary_function<
  SymbolAST*, SymbolAST*, bool
> {
  OverloadSetSort(CallExprAST *args): Args(args) {}
  OverloadSetSort(const OverloadSetSort &right): Args(right.Args) {}

  bool operator()(SymbolAST* left, SymbolAST* right) const {
    // Мы должны переместить все более специализированные функции в
    // начало. Для этого мы должны произвести обмен элементов 
    // только, если левый кандидат лучше, чем 2-й и 2-й не лучше,
    // чем первый
    return isMoreSpecialized(Args, left, right) && 
      !isMoreSpecialized(Args, right, left);
  }

private:
  CallExprAST* Args;
};

static SymbolAST* resolveFunctionCall(
  Scope *scope, SymbolAST* func, CallExprAST* args) {
  // Набор потенциальных кандидатов для вызова
  SymbolList listOfValidOverloads;

  // У нас есть специальная обработка для варианта, когда есть 
  // только один кандидат для вызова
  if (isa<FuncDeclAST>(func)) {
    FuncDeclAST* fnc = static_cast< FuncDeclAST* >(func);
    FuncTypeAST* type = static_cast< FuncTypeAST* >(fnc->ThisType);

    // Количество аргументов должно совпадать с количеством 
    // параметров у функции
    if (args->Args.size() != type->Params.size()) {
      scope->report(args->Loc, 
                    diag::ERR_SemaInvalidNumberOfArgumentsInCall);
      return nullptr;
    }

    ExprList::iterator arg = args->Args.begin();
    ParameterList::iterator it = type->Params.begin();

    // Если это вызов метода класса, то игнорируем параметр для 
    // "this"
    if (isa<MemberAccessExprAST>(args->Callee)) {
      ++it;
      ++arg;
    }

    // Проверяем все аргументы
    for (ParameterList::iterator end = type->Params.end();
      it != end; ++it, ++arg) {
      // Проверяем, что аргумент может быть использован для вызова
      // и диагностируем об ошибке, если нет
      if (!(*arg)->ExprType->implicitConvertTo((*it)->Param)) {
        scope->report(args->Loc,
                      diag::ERR_SemaInvalidTypesOfArgumentsInCall);
        return nullptr;
      }
    }

    // Вызов функции может быть произведен с данными аргументами
    return func;
  }

  // Это набор перегруженных функций, необходимо произвести выбор
  // лучшего кандидата для вызова
  OverloadSetAST* overloadSet = (OverloadSetAST*)func;
  size_t numArgs = args->Args.size();

  // Проверяем все функции из набора
  for (SymbolList::iterator it = overloadSet->Vars.begin(),
    end = overloadSet->Vars.end(); it != end; ++it) {
    FuncDeclAST* fnc = static_cast< FuncDeclAST* >(*it);
    FuncTypeAST* type = static_cast< FuncTypeAST* >(fnc->ThisType);

    // Если количество параметров и аргументов не совпадают, то
    // игнорируем данную функцию-кандидат
    if (numArgs != type->Params.size()) {
      continue;
    }

    ExprList::iterator arg = args->Args.begin();
    ParameterList::iterator param = type->Params.begin();

    // Если это вызов метода класса, то игнорируем параметр для 
    // "this"
    if (isa<MemberAccessExprAST>(args->Callee)) {
      ++param;
      ++arg;
    }

    // Помечаем кандидат как пригодный и полное совпадение типов
    // аргументов и параметров
    bool isValid = true;
    bool isExact = true;

    // Проверяем каждый аргумент
    for (ParameterList::iterator end = type->Params.end();
      param != end; ++param, ++arg) {
      // Проверяем, что типы совпадают
      if (!(*arg)->ExprType->equal((*param)->Param)) {
        // Типы не совпадают, помечаем это
        isExact = false;
        
        // Проверяем, что есть доступное преобразование для типов
        if (!(*arg)->ExprType->implicitConvertTo((*param)->Param)) {
          // Кандидат не пригоден для вызова, помечаем и игнорируем 
          // все последующие аргументы
          isValid = false;
          break;
        }
      }
    }

    // Предпочитаем полное совпадение по типам
    if (isExact) {
      return fnc;
    }

    // Добавляем фукнции-кандидаты, которые пригодны для вызова
    if (isValid) {
      listOfValidOverloads.push_back(fnc);
    }
  }

  // Если у нас больше чем 1 кандидат, необходимо это обработать
  if (listOfValidOverloads.size() > 1) {
    // Сортируем все кандидаты в порядке их пригодности
    std::sort(
      listOfValidOverloads.begin(),
      listOfValidOverloads.end(),
      OverloadSetSort(args)
    );

    SymbolList::iterator it1 = listOfValidOverloads.begin();
    SymbolList::iterator it2 = listOfValidOverloads.begin() + 1;

    // Если 1-я функция-кандидат лучше, чем 2-я и 2-я не лучше 1-й, 
    // то необходимо удалить из набора все функции, кроме 1-й. 
    // Иначе сообщаем об ошибке ниже
    if (isMoreSpecialized(args, *it1, *it2) && 
      !isMoreSpecialized(args, *it2, *it1)) {
      listOfValidOverloads.erase(it2, listOfValidOverloads.end());
    }
  }

  // Если у нас осталось больше 1-й функции, то сообщаем об ошибке
  if (listOfValidOverloads.size() > 1) {
    scope->report(args->Loc, diag::ERR_SemaAmbiguousCall);
    return nullptr;
  // Если у нас не осталось ни 1-й функции, то сообщаем об ошибке
  } else if (listOfValidOverloads.empty()) {
    scope->report(args->Loc,
                  diag::ERR_SemaInvalidNumberOfArgumentsInCall);
    return nullptr;
  }

  // Осталась только одна, возвращаем ее
  return listOfValidOverloads.pop_back_val();
}

ExprAST* CallExprAST::semantic(Scope* scope) {
  if (ExprType) {
    return this;
  }

  // Производим семантический анализ выражения до "("
  Callee = Callee->semantic(scope);

  // Мы можем использовать только IdExprAST и MemberAccessExprAST
  // в качестве выражения для вызова
  if (isa<IdExprAST>(Callee) || isa<MemberAccessExprAST>(Callee)) {
    SymbolAST* sym = (isa<IdExprAST>(Callee)
      ? ((IdExprAST*)Callee)->ThisSym
      : ((MemberAccessExprAST*)Callee)->ThisSym);

    // Val должна ссылаться на функцию или набор перегруженных 
    // функций
    if (isa<FuncDeclAST>(sym) || isa<OverloadSetAST>(sym)) {
      TypeAST* returnType = nullptr;

      // Специальная обработка для методов класса
      if (isa<MemberAccessExprAST>(Callee)) {
        MemberAccessExprAST* memAccess = 
          (MemberAccessExprAST*)Callee;
        
        // Необходимо добавить аргумент для параметра "this"
        ExprAST* thisArg = memAccess->Val->clone();
        Args.insert(Args.begin(), thisArg);

        // Для методов, у которых предопределен тип возвращаемого 
        // значения мы также должны указать тип результата
        if (memAccess->ForceThis) {
          returnType = memAccess->Val->ExprType;
        }
      }

      // Производим семантический анализ для всех аргументов 
      // функции
      for (ExprList::iterator arg = Args.begin(), end = Args.end();
        arg != end; ++arg) {
        *arg = (*arg)->semantic(scope);
      }
      
      // Ищем функцию для вызова
      if (SymbolAST* newSym = resolveFunctionCall(scope, sym, this)) {
        FuncDeclAST* fnc = static_cast< FuncDeclAST* >(newSym);
        FuncTypeAST* type = 
          static_cast< FuncTypeAST* >(fnc->ThisType);

        ExprList::iterator arg = Args.begin();
        ParameterList::iterator it = type->Params.begin();

        // Для вызова метода класса игнорируем аргумент для
        // параметра "this"
        if (isa<MemberAccessExprAST>(Callee)) {
          ++arg;
          ++it;
        }

        // Производим сопоставление аргументов и параметров
        for (ParameterList::iterator end = type->Params.end();
          it != end; ++it, ++arg) {
          // Если тип аргумента отличается от типа параметра, 
          // производим преобразование типа
          if (!(*arg)->ExprType->equal((*it)->Param)) {
            ExprAST* oldArg = (*arg);
            *arg = new CastExprAST(
              oldArg->Loc,
              oldArg->clone(),
              (*it)->Param
            );
            *arg = (*arg)->semantic(scope);
            delete oldArg;
          }
        }

        // Определяем тип возвращаемого значения и устанавливаем 
        // тип для результата вызова функции
        if (!returnType) {
          ExprType = ((FuncDeclAST*)newSym)->ReturnType;
        } else {
          ExprType = returnType;
        }

        // Устанавливаем объявление функции для вызова для
        // дальнейшей работы
        CallFunc = newSym;
        return this;
      }
    }
  }

  // Диагностируем ошибку
  scope->report(Loc, diag::ERR_SemaInvalidArgumentsForCall);
  return nullptr;
}

ExprAST* CallExprAST::clone() {
  ExprList exprs;
  ExprList::iterator it = Args.begin();
  ExprList::iterator end = Args.end();

  // Для методов члена мы должны игнорировать аргумент для
  // параметра "this", т. к. он будет повторно добавлен во
  // время проверки семантики
  if (isa<MemberAccessExprAST>(Callee)) {
    ++it;
  }

  for ( ; it != end; ++it) {
    exprs.push_back((*it)->clone());
  }

  return new CallExprAST(Loc, Callee->clone(), exprs);
}

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

Hidden text
/// Проверка на то, что для инструкции нужно создать новый блок
/// \param[in] oldStmt — текущая инструкция
/// \param[in] scope — область видимости
bool needPromoteBodyToBlock(StmtAST* oldStmt, Scope* scope) {
  // Только объявления могут создавать новые блоки
  if (!isa<DeclStmtAST>(oldStmt)) {
    return false;
  }

  // Производим семантический анализ для инструкции, т. к. нам 
  // необходимо, что бы тип переменной был уже известен
  DeclStmtAST* declStmt = (DeclStmtAST*)oldStmt->semantic(scope);
  SymbolList::iterator it = declStmt->Decls.begin();
  assert(isa<VarDeclAST>(*it));
  VarDeclAST* var = (VarDeclAST*)*it;

  // Только объекты классов могут создавать новые блоки
  if (isa<ClassTypeAST>(var->ThisType)) {
    ClassDeclAST* classDecl =
      (ClassDeclAST*)var->ThisType->getSymbol();

    // Только объекты классов с деструкторами могут создавать 
    // новые блоки
    if (classDecl->Dtor) {
      return true;
    }
  }

  // Создавать новый блок не нужно
  return false;
}

StmtAST* BlockStmtAST::doSemantic(Scope* scope) {
  // Для блока мы должны создать новую область видимости
  ThisBlock = new ScopeSymbol(Loc, SymbolAST::SI_Block, nullptr);
  Scope* s = scope->push((ScopeSymbol*)ThisBlock);
  
  // Создать LandingPadAST для данного блока
  // Замечание: Позже мы должны установить NeedCleanup, если 
  // это будет необходимо
  LandingPad = new LandingPadAST(s->LandingPad, false);
  LandingPad->OwnerBlock = this;
  LandingPad->NeedCleanup = s->LandingPad->NeedCleanup;
  s->LandingPad = LandingPad;

  bool atStart = true; // Необходимо для создания новых блоков
  ExprList args;

  // Проверяем все ветви дерева принадлежащие данному блоку
  for (StmtList::iterator it = Body.begin(), end = Body.end();
       it != end; ++it) {
    // Если в предыдущей инструкции был "break", "continue" или 
    // "return", то диагностируем об ошибке (предотвращаем
    // появление кода, который не может быть достижимым
    if (HasJump) {
      scope->report(Loc, diag::ERR_SemaDeadCode);
      return nullptr;
    }

    // Проверяем, что должен быть создан новый блок
    if (needPromoteBodyToBlock(*it, s)) {
      // В данном блоке есть деструкторы, которые должны быть
      // вызваны
      LandingPad->NeedCleanup = true;

      // Проверяем, что это середина блока
      if (!atStart) {
        // Создаем новый блок и переносим в него все инструкции с
        // текущей и до конца блока (удаляя их из текущего блока)
        StmtList body(it, end);
        BlockStmtAST* newBlockStmt = new BlockStmtAST(Loc, body);
        Body.erase(it, end);
        Body.push_back(newBlockStmt);
        // Помечаем блок, как автоматически созданный и производим
        // семантический анализ для него, а так же устанавливаем
        // флаги HasJump и HasReturn
        newBlockStmt->IsPromoted = true;
        newBlockStmt->semantic(s);
        HasJump = newBlockStmt->HasJump;
        HasReturn = newBlockStmt->HasReturn;
        break;
      }

      DeclStmtAST* decls = (DeclStmtAST*)*it;
      
      for (SymbolList::iterator it2 = decls->Decls.begin(),
        end2 = decls->Decls.end(); it2 != end2; ++it2) {
        VarDeclAST* var = (VarDeclAST*)*it2;
        // Создаем вызов деструктора для данного объекта
        ExprAST* cleanupExpr = new CallExprAST(
          Loc,
          new MemberAccessExprAST(
            Loc,
            new IdExprAST(Loc, var->Id),
            Name::Dtor),
          args);
        // Произвести семантический анализ для вызова деструктора
        cleanupExpr = cleanupExpr->semantic(s);
        // Добавляем вызов деструктора к списку блока очистки
        CleanupList.push_back(cleanupExpr);
      }
    } else if (!isa<DeclStmtAST>(*it)) {
      // Это не объявление, устанавливаем atStart в false
      atStart = false;
    }

    // Проверяем семантику вложенной инструкции
    *it = (*it)->semantic(s);

    // Проверяем, что это "break", "continue" или "return" 
    if ((*it)->isJump()) {
      HasJump = true;

      // Проверяем, что это "return"
      if ((*it)->hasReturn()) {
        HasReturn = true;
      }
    } else {
      // Это обычная инструкция, но все равно проверяем, наличие 
      // "break", "continue" или "return" в дочерних ветках 
      // инструкции
      HasJump = (*it)->hasJump();
      HasReturn = (*it)->hasReturn();
    }
  }

  // Если нам нужно произвести очистку ресурсов
  if (LandingPad->NeedCleanup) {
    // Получаем родительскую функцию и устанавливаем флаг 
    // NeedCleanup
    FuncDeclAST* fncDecl = (s->EnclosedFunc);
    fncDecl->LandingPad->NeedCleanup = true;

    if (!LandingPad->Prev->OwnerBlock) {
      // Если предыдущий LandingPadAST не является блоком, 
      // то устанавливаем флаг NeedCleanup в true
      LandingPad->Prev->NeedCleanup = true;
    } else {
      // Предыдущий LandingPadAST является блоком, то нужно 
      // установить флаг NeedCleanup только если есть наличие 
      // "break", "continue" или "return" в дочерних ветках
      // инструкции
      if (LandingPad->Returns || LandingPad->Continues ||
        LandingPad->Breaks) {
        LandingPad->Prev->NeedCleanup = true;
      }
    }
  }

  // Удаляем область видимости
  s->pop();

  return this;
}

Так же нужно внести небольшие правки в циклах "while" и "if", которые связаны с вызовом деструкторов:

Hidden text
StmtAST* WhileStmtAST::doSemantic(Scope* scope) {
  ...
  // Создаем новую LandingPadAST для всех вложенных инструкций
  LandingPad = new LandingPadAST(scope->LandingPad, false);
  LandingPad->NeedCleanup = scope->LandingPad->NeedCleanup;
  ...
}

StmtAST* IfStmtAST::doSemantic(Scope* scope) {
  ...
  // Создаем новый LandingPadAST
  LandingPad = new LandingPadAST(scope->LandingPad, false);
  LandingPad->NeedCleanup = scope->LandingPad->NeedCleanup;
  ...
}

Семантика объявлений

Для объявлений переменных или членов класса нам нужно произвести особую обработку для вызова конструкторов по умолчанию, если для них не заданы инициализаторы и есть конструктор:

Hidden text
void VarDeclAST::doSemantic3(Scope* scope) {
  // При отсутствии инициализатора переменной, мы генерируем 
  // инициализатор по умолчанию
  if (!Val) {
    // Отключаем стандартную обработку, если это член класса или 
    // структуры
    if (needThis()) {
      return;
    }

    // Игнорируем, если это массив
    if (isa<ArrayTypeAST>(ThisType)) {
      return;
    }

    // У нас есть специальная обработка для агрегатов
    if (ThisType->isAggregate()) {
      if (isa<ClassTypeAST>(ThisType)) {
        ClassDeclAST* thisClass =
          (ClassDeclAST*)ThisType->getSymbol();
        // Для классов с конструктором, необходимо сгенерировать
        // вызов конструктора по умолчанию
        if (thisClass->Ctor) {
          ExprList args;
          Val = new CallExprAST(
            Loc,
            new MemberAccessExprAST(
              Loc,
              new IdExprAST(Loc, Id),
              Name::Ctor),
            args);
          // проверка семантики для вызова конструктора
          Val = Val->semantic(scope);
        }
      }

      return;
    // Специальная обработка для указателей и строк
    } else if (isa<PointerTypeAST>(ThisType) ||
      ThisType->isString())
      Val = new IntExprAST(Loc, 0);
    // Специальная обработка для "int"
    else if (ThisType->isInt())
      Val = new IntExprAST(Loc, 0);
    // Специальная обработка для "char"
    else if (ThisType->isChar()) {
      Val = new IntExprAST(Loc, 0);
      Val = new CastExprAST(
        Loc,
        Val,
        BuiltinTypeAST::get(TypeAST::TI_Char)
      );
    } else {
      // Инициализация для "float"
      Val = new FloatExprAST(Loc, 0.0);
    }

    // Производим семантический анализ для созданного 
    // инициализирующего выражения
    Val = Val->semantic(scope);

    return;
  }
  
  // Производим семантический анализ инициализирующего выражения
  Val = Val->semantic(scope);

  if (isa<ClassTypeAST>(ThisType)) {
    return;
  }
  ...
}

Проверка циклов в объявлениях:

Hidden text
bool VarDeclAST::contain(TypeAST* type) {
  // Возвращаем true, если тип совпадает или type является
  // родительским классом для типа данного объекта
  if (ThisType->equal(type) || type->isBaseOf(ThisType)) {
    return true;
  }

  return false;
}

bool VarDeclAST::canBeNull() {
  // "super" или тип отличный от указателя не могут быть nullptr
  if (Id == Name::Super || !isa<PointerTypeAST>(ThisType)) {
    return false;
  }

  return true;
}

Специальная обработка для очистки ресурсов для OverloadSetAST:

Hidden text
ScopeSymbol::~ScopeSymbol() {
  for (SymbolMap::iterator it = Decls.begin(), end = Decls.end();
    it != end; ++it) {
    if (isa<OverloadSetAST>(it->second)) {
      delete it->second;
    }
  }
}

Запрет использования объектов класса в полях в структурах:

Hidden text
void StructDeclAST::doSemantic3(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);
  int curOffset = 0;

  // Проверка всех дочерних объявлений
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    VarDeclAST* var = (VarDeclAST*)(*it);
    
    // Производим семантическую проверку для члена структуры
    // и получаем индекс для данного члена
    var->semantic(s);
    var->OffsetOf = curOffset++;

    // Запрещаем использование объектов класса в качестве полей 
    // структур
    if (isa<ClassTypeAST>(var->getType())) {
      scope->report(Loc, diag::ERR_SemaClassAsStructMember);
      return;
    }
  }

  // Проверка на наличие циклических зависимостей
  if (contain(ThisType)) {
    scope->report(Loc, diag::ERR_SemaCricularReference, Id->Id);
    return;
  }

  // Удаляем область видимости для данного объявления
  s->pop();
}

Поддержка динамической диспетчеризации вызовов методов класса:

Hidden text
// Проверка на то, что метод уже существует в таблице виртуальных 
// методов
bool VTableAST::isExist(SymbolAST* func) {
  assert(isa<FuncDeclAST>(func));
  FuncDeclAST* fncDecl = (FuncDeclAST*)func;
  SymbolMap::iterator pos = Decls.find(func->Id);

  // Если ничего не найдено, то возвращаем false
  if (pos == Decls.end()) {
    return false;
  }

  // Проверка на то, что найденный символ является функцией или
  // набором перегруженных функций
  if (isa<FuncDeclAST>(pos->second)) {
    // Функция
    FuncDeclAST* existDecl = (FuncDeclAST*)pos->second;

    // Если типы функций совпадают, то возвращаем true
    if (existDecl->ThisType->equal(fncDecl->ThisType)) {
      return true;
    }
    // Такой функции еще нет таблице
    return false;
  } else {
    // Это набор перегруженных функций
    assert(isa<OverloadSetAST>(pos->second));
    OverloadSetAST* existDecls = (OverloadSetAST*)pos->second;

    // Пытаемся найти функцию в наборе перегруженных функций
    return existDecls->OverloadsUsed.find(
      fncDecl->ThisType->MangleName
    ) != existDecls->OverloadsUsed.end();
  }
}
// Добавить или заменить функцию в таблице виртуальных методов
void VTableAST::addOrReplace(Scope* scope, SymbolAST* func) {
  assert(isa<FuncDeclAST>(func));
  FuncDeclAST* fncDecl = (FuncDeclAST*)func;
  SymbolMap::iterator pos = Decls.find(func->Id);
  
  if (pos == Decls.end()) {
    // Функция не найдена, добавляем ее в таблицу виртуальных 
    // методов
    fncDecl->OffsetOf = CurOffset++;
    Decls[fncDecl->Id] = func;
    return;
  } else {
    // Проверяем, что это набор перегруженных функций
    if (isa<OverloadSetAST>(pos->second)) {
      OverloadSetAST* overloadSet = (OverloadSetAST*)pos->second;
      
      // Проверяем была ли данная функция добавлена в таблицу или
      // нет
      if (overloadSet->OverloadsUsed.find(
          fncDecl->ThisType->MangleName
        ) != overloadSet->OverloadsUsed.end()) {
        // Ранее была добавлена. Находим старый слот и заменяем 
        // новой
        for (SymbolList::iterator it = overloadSet->Vars.begin(),
          end = overloadSet->Vars.end(); it != end; ++it) {
          FuncDeclAST* oldFnc = (FuncDeclAST*)*it;
          if (oldFnc->ThisType->equal(fncDecl->ThisType)) {
            // Замена старой функции в слоте
            fncDecl->OffsetOf = oldFnc->OffsetOf;
            (*it) = fncDecl;

            // Проверяем, что типы возвращаемого значения совпадают
            if (!fncDecl->ReturnType->equal(oldFnc->ReturnType)) {
              scope->report(
                fncDecl->Loc,
                diag::ERR_SemaVirtualFunctionReturnTypeOverload,
                fncDecl->Id->Id,
                Parent->Id->Id
              );
            }
            return;
          }
        }
      } else {
        // Это новая функция. Добавляем ее
        fncDecl->OffsetOf = CurOffset++;
        overloadSet->push(scope, func);
        return;
      }
    } else {
      // Это обычная функция
      assert(isa<FuncDeclAST>(pos->second));
      FuncDeclAST* oldFnc = (FuncDeclAST*)pos->second;

      // Проверка на то, что прототипы функций совпадают
      if (oldFnc->ThisType->equal(fncDecl->ThisType)) {
        // Замена старой функции в слоте
        fncDecl->OffsetOf = oldFnc->OffsetOf;
        Decls[fncDecl->Id] = func;

        // Проверяем, что типы возвращаемого значения совпадают
        if (!fncDecl->ReturnType->equal(oldFnc->ReturnType)) {
          scope->report(
            fncDecl->Loc,
            diag::ERR_SemaVirtualFunctionReturnTypeOverload,
            fncDecl->Id->Id,
            Parent->Id->Id
          );
        }
        return;
      } else {
        // Функции еще нет в таблице, создаем набор перегруженных
        // функций с именем данной функции и добавляем ее в слот
        OverloadSetAST* newSet = new OverloadSetAST(fncDecl->Id);
        fncDecl->OffsetOf = CurOffset++;
        newSet->push(scope, oldFnc);
        newSet->push(scope, fncDecl);
        Decls[fncDecl->Id] = newSet;
        return;
      }
    }
  }
}
// Клонирование таблицы виртуальных методов
VTableAST* VTableAST::clone(SymbolAST* parent) {
  return new VTableAST(*this, parent);
}

Семантический анализ для классов:

Hidden text
/// Генерация списка инициализирующих выражений по умолчанию для
/// полей класса
/// \param[in] classDecl — класс, для которого нужно произвести 
///   генерацию
ExprList generateDefaultInitializer(ClassDeclAST* classDecl) {
  ExprList result;

  // Проверяем каждое объявление на наличие инициализирующих 
  // выражений
  for (SymbolList::iterator it = classDecl->Vars.begin(),
    end = classDecl->Vars.end(); it != end; ++it) {
    // Проверяем только объявление переменных членов класса
    if (isa<VarDeclAST>(*it)) {
      VarDeclAST* var = (VarDeclAST*)*it;

      // Если есть значение для инициализации, то генерируем 
      // инструкцию присвоения
      if (var->Val) {
        ExprAST* expr = new BinaryExprAST(
          classDecl->Loc,
          tok::Assign, 
          new IdExprAST(classDecl->Loc, var->Id),
          var->Val->clone()
        );
        result.push_back(expr);
      }
      // Специальная проверка для объектов класса
      else if (isa<ClassTypeAST>(var->ThisType)) {
        ClassDeclAST* innerDecl = 
          (ClassDeclAST*)var->ThisType->getSymbol();
        // Если у класса есть конструктор, то нужно сгенерировать
        // его вызов
        if (innerDecl->Ctor) {
          // var.__ctor()
          ExprAST* expr = new MemberAccessExprAST(classDecl->Loc,
            new IdExprAST(classDecl->Loc, (*it)->Id), Name::Ctor);
          ExprList args;
          expr = new CallExprAST(classDecl->Loc, expr, args);
          result.push_back(expr);
        }
      }
    }
  }

  return result;
}

/// Генерация конструктора по умолчанию для класса (если это 
/// необходимо)
/// \param[in] classDecl — класс для которого нужно сгенерировать
///  конструктор
FuncDeclAST* generateDefaultConstructor(ClassDeclAST* classDecl) {
  // Получить список выражений для инициализации переменных членов
  // класса
  ExprList valsInit = generateDefaultInitializer(classDecl);

  ParameterList params;
  StmtList body;
  StmtAST* ctorCall = nullptr;

  // Проверяем родительский класс на наличие конструкторов
  if (classDecl->BaseClass &&
    isa<ClassTypeAST>(classDecl->BaseClass)) {
    ClassDeclAST* baseClass =
      (ClassDeclAST*)classDecl->BaseClass->getSymbol();
    // Если есть конструктор, то нужно произвести его вызов
    if (baseClass->Ctor) {
      // super.__ctor()
      ExprAST* expr = new MemberAccessExprAST(classDecl->Loc, 
        new IdExprAST(classDecl->Loc, Name::Super), Name::Ctor);
      ExprList args;
      expr = new CallExprAST(classDecl->Loc, expr, args);
      ctorCall = new ExprStmtAST(classDecl->Loc, expr);
    }
  }

  // Если есть хотя бы одна переменная с инициализирующим выражением, то
  // нужно создать инструкции для 
  if (!valsInit.empty()) {
    for (ExprList::iterator it = valsInit.begin(),
      end = valsInit.end(); it != end; ++it) {
      body.push_back(new ExprStmtAST(classDecl->Loc, *it));
    }
  }

  // Если нет ни таблицы виртуальных методов, ни конструктора
  // родительского класса, ни переменных для инициализации, то
  // возвращаем nullptr
  if (!classDecl->VTbl && body.empty() && !ctorCall) {
    return nullptr;
  }

  StmtList ctorBody;

  // Добавляем вызов конструктора базового класса
  if (ctorCall) {
    ctorBody.push_back(ctorCall);
  }

  // Добавляем инициализацию членов класса
  ctorBody.push_back(new BlockStmtAST(classDecl->Loc, body));

  // Создаем конструктор по умолчанию для класса
  FuncTypeAST* ctorType = new FuncTypeAST(nullptr, params);
  FuncDeclAST* ctorDecl = new FuncDeclAST(
    classDecl->Loc,
    ctorType,
    Name::Ctor, 
    new BlockStmtAST(classDecl->Loc, ctorBody),
    true,
    tok::New
  );
  return ctorDecl;
}

/// Генерация действий по умолчанию для вызова деструкторов 
/// переменных членов класса
/// \param[in] classDecl — класс для которого нужно произвести
///  генерацию
StmtList generateCleanupList(ClassDeclAST* classDecl) {
  StmtList result;

  // Проверяем каждое объявление и генерирурем вызовы деструкторов,
  // для тех членов класса, у которых они есть (деструкторы должны
  // вызваться в обратном порядке)
  for (SymbolList::reverse_iterator it = classDecl->Vars.rbegin(),
    end = classDecl->Vars.rend(); it != end; ++it) {
    // Пропускаем все объявления отличные от переменных
    if (!isa<VarDeclAST>(*it)) {
      continue;
    }

    VarDeclAST* var = (VarDeclAST*)*it;

    // Пропускаем все переменные не являющимеся объектами классов
    if (!isa<ClassTypeAST>(var->ThisType)) {
      continue;
    }

    ClassDeclAST* innerDecl = 
      (ClassDeclAST*)var->ThisType->getSymbol();
    // Если класс имеет деструктор, но необходимо сгенерировать
    // его вызов
    if (innerDecl->Dtor) {
      // var.__dtor()
      ExprAST* expr = new MemberAccessExprAST(classDecl->Loc,
        new IdExprAST(classDecl->Loc, (*it)->Id), Name::Dtor);
      ExprList args;
      expr = new CallExprAST(classDecl->Loc, expr, args);
      result.push_back(new ExprStmtAST(classDecl->Loc, expr));
    }
  }

  return result;
}

Для корректной работы программы нам необходимо:

  1. Для всех переменных членов класса у которых есть конструкторы, мы должны сгенерировать код для вызова их конструкторов, что бы они все были корректно инициализированы. Поэтому мы должны добавить их инициализацию для каждого конструктора, который объявлен в классе;

  2. Для всех переменных членов класса у которых есть деструкторы, мы должны произвести очистку ресурсов путем вызова нужных деструкторов. Поэтому мы должны добавить очистку ресурсов в деструктор класса;

  3. Если п.1 или п.2 соблюдены, но у самого класса нет ни одного явно объявленного конструктора или деструктора (или если у класса есть виртуальные методы), то для данного класса должны быть автоматически сгенерированы конструктор/деструктор.

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

Ниже рассмотрим семантический анализ для классов с учетом всех этих дополнений:

Hidden text
TypeAST* ClassDeclAST::getType() {
  return ThisType;
}

void ClassDeclAST::doSemantic(Scope* scope) {
  // Запрещаем переопределение
  if (scope->find(Id)) {
    scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
    return;
  }

  // Создаем новую область видимости
  Scope* s = scope->push(this);

  // Производим семантический анализ для типа текущего класса
  ThisType = ThisType->semantic(s);
  // Добавляем объявление в родительскую область видимости
  ((ScopeSymbol*)scope->CurScope)->Decls[Id] = this;
  Parent = scope->CurScope;

  // Производим семантический анализ для всех вложенных агрегатов
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    if ((*it)->isAggregate()) {
      (*it)->semantic(s);
    }
  }

  // Удаляем область видимости
  s->pop();
}

void ClassDeclAST::doSemantic2(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);

  // Если у класса есть родительский класс, то нужно это обработать
  if (BaseClass) {
    // Произвести семантический анализ типа родительского класса
    BaseClass = BaseClass->semantic(s);

    // Тип родительского класса должен быть агрегатом
    if (!BaseClass->isAggregate()) {
      scope->report(Loc, diag::ERR_SemaInvalidBaseClass, Id->Id);
      return;
    }

    // Проверяем на циклические зависимости
    if (BaseClass->equal(ThisType) ||
      ThisType->isBaseOf(BaseClass)) {
      scope->report(Loc, diag::ERR_SemaCricularReference, Id->Id);
      return;
    }
  }

  // Удаляем область видимости
  s->pop();
}

void ClassDeclAST::doSemantic3(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);

  // Проверяем все методы класс на специальные методы
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    // Обрабатываем только методы класса
    if (!isa<FuncDeclAST>(*it)) {
      continue;
    }

    FuncDeclAST* fncDecl = (FuncDeclAST*)*it;

    // Если это конструктор, то устанавливаем флаг, что класс
    // имеет конструктор
    if (fncDecl->isCtor()) {
      Ctor = true;
      continue;
    }

    // Если это деструктор, то устанавливаем флаг, что класс
    // имеет деструктор
    if (fncDecl->isDtor()) {
      Dtor = true;
      continue;
    }
  }

  // Производим семантический анализ для каждой объявленной 
  // переменной члена класса
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    // Обрабатываем только переменные члены
    if (!isa<VarDeclAST>(*it)) {
      continue;
    }

    // Производим семантический анализ объявления
    (*it)->semantic(s);

    // Игнорируем не объекты классов
    if (!isa<ClassTypeAST>((*it)->getType())) {
      continue;
    }

    ClassDeclAST* classDecl =
      (ClassDeclAST*)((*it)->getType()->getSymbol());

    // Для того, что бы корректно сгенерировать конструкторы и 
    // деструкторы необходимо убедится, что все переменные члены
    // класса являющимися объектами классов должны пройти 4 стадии
    // семантического анализа, если это не так, то запускаем
    // семантический анализ всех нужных стадий
    if (classDecl->SemaState < 4) {
      // Воссоздаем область видимости для данного члена класса
      Scope* memberScope = Scope::recreateScope(scope, classDecl);

      // Запускаем 2, 3 и 4 стадии семантического анализа
      classDecl->semantic2(memberScope);
      classDecl->semantic3(memberScope);
      classDecl->semantic4(memberScope);
      
      // Очищаем все лишние области видимости, оставляем только
      // область видимости модуля
      Scope::clearAllButModule(memberScope);
    }
  }

  // Проверяем на наличие циклических зависимостей
  if (contain(ThisType)) {
    scope->report(Loc, diag::ERR_SemaCricularReference, Id->Id);
    return;
  }

  // Убеждаемся, что родительский класс знает все о своих 
  // конструкторах
  if (BaseClass && isa<ClassTypeAST>(BaseClass)) {
    ClassDeclAST* baseDecl = (ClassDeclAST*)BaseClass->getSymbol();

    // Проверяем, что 4 проход семантического анализа был запущен
    // ранее
    if (baseDecl->SemaState < 4) {
      // Нет. Воссоздаем область видимости для данного члена класса
      Scope* parenScope = Scope::recreateScope(scope, baseDecl);

      // Запускаем 2, 3 и 4 стадии семантического анализа
      baseDecl->semantic2(parenScope);
      baseDecl->semantic3(parenScope);
      baseDecl->semantic4(parenScope);
          
      // Очищаем все лишние области видимости, оставляем только
      // область видимости модуля
      Scope::clearAllButModule(parenScope);
    }
  }

  ExprList valsInit;
  
  // Если есть конструктор, то генерируем список инициализирующих
  // выражений для переменных членов класса
  if (Ctor) {
    valsInit = generateDefaultInitializer(this);
  }

  // Теперь мы можем произвести семантический анализ для методов 
  // класса
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    // Пропускаем все не методы класса
    if (!isa<FuncDeclAST>(*it)) {
      continue;
    }

    FuncDeclAST* fncDecl = (FuncDeclAST*)*it;

    // Специальная обработка для конструкторов
    if (fncDecl->isCtor()) {
      StmtList initBody;

      // Генерируем блок инициализации переменных членов класса
      // на основе ранее сгенерированого списка
      for (ExprList::iterator it = valsInit.begin(),
        end = valsInit.end(); it != end; ++it) {
        initBody.push_back(new ExprStmtAST(Loc, (*it)->clone()));
      }

      // Получаем тело конструктора
      BlockStmtAST* fncBody = (BlockStmtAST*)fncDecl->Body;

      // Проверяем наличие вызова конструктора родительского класса
      if (isa<ExprStmtAST>(fncBody->Body[0])) {
        // Мы должны добавить блок инициализации сразу после вызова
        // конструктора родительского класса
        fncBody->Body.insert(
          fncBody->Body.begin() + 1,
          new BlockStmtAST(fncDecl->Loc, initBody)
        );
      } else {
        // Мы должны добавить блок инициализации в самое начало
        // тела конструктора
        fncBody->Body.insert(
          fncBody->Body.begin(),
          new BlockStmtAST(fncDecl->Loc, initBody)
        );
      }
    // Специальная обработка для деструктора
    } else if (fncDecl->isDtor()) {
      // Пробуем сгенерировать список очистки для переменных
      // членов класса
      StmtList defaultCleanup = generateCleanupList(this);

      if (!defaultCleanup.empty()) {
        // Если список не пуст, то нужно добавить очистку в 
        // конец тела деструктора
        BlockStmtAST* fncBody = (BlockStmtAST*)fncDecl->Body;
        fncBody->Body.insert(
          fncBody->Body.end(),
          defaultCleanup.begin(),
          defaultCleanup.end()
        );
      }
    }

    // Проверка наличия родительского класса
    if (BaseClass && isa<ClassTypeAST>(BaseClass)) {
      Name* memberId = (*it)->Id;

      // Пытаемся найти данное определение в родительском классе
      SymbolAST* foundInBase = 
        ((ClassTypeAST*)BaseClass)->ThisDecl->find(memberId);

      // Если символ найден и это не конструктор или деструктор, 
      // то нужно произвести специальную обработку
      if (foundInBase && memberId != Name::Ctor &&
        memberId != Name::Dtor) {
        if (isa<FuncDeclAST>(foundInBase)) {
          // Это метод класса, копируем его в список объявлений 
          // данного класса для поддержки перегрузки функций
          Decls[memberId] = foundInBase;
        } else if (isa<OverloadSetAST>(foundInBase)) {
          // Это набор перегруженных функций. Клонируем его для 
          // поддержки перегрузки функций из родительского класса
          Decls[memberId] = ((OverloadSetAST*)foundInBase)->clone();
        }
      }
    }

    // Производим семантический анализ метода класса
    (*it)->semantic(s);
  }

  // Если ранее были созданы инициализирующие выражения, то
  // удаляем их
  if (!valsInit.empty()) {
    for (ExprList::iterator it = valsInit.begin(),
      end = valsInit.end(); it != end; ++it) {
      delete *it;
    }
  }

  // Удаляем область видимости
  s->pop();
}

void ClassDeclAST::doSemantic4(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);

  // Если VTable была создана в данном классе, не в родительском
  // классе
  bool vtableOwner = true; 
  VTableAST* vtbl = nullptr;
  int curOffset = 0; // Текущий слот для переменных
  // true — если нужно сгенерировать деструктор
  bool generateDtor = false; 
  bool baseHasVtbl = false;
  StmtList defaultDtorBody;
  
  // Если класс не имеет явных деструкторов, то пробуем создать
  // список для очистки переменных членов класса
  if (!Dtor) {
    defaultDtorBody = generateCleanupList(this);
  }

  // Пытаемся найти VTable в родительском классе
  if (BaseClass) {
    // Проверяем, что это класс
    if (isa<ClassTypeAST>(BaseClass)) {
      ClassDeclAST* baseDecl =
        (ClassDeclAST*)BaseClass->getSymbol();

      if (baseDecl->VTbl) {
        // Базовый класс имеет свою таблиц виртуальных методов. Мы 
        // должны взять Vtable за основу и установить все нужные 
        // флаги
        vtableOwner = false;
        vtbl = baseDecl->VTbl;
        baseHasVtbl = true;
      }

      // Если у класса нет деструктора, но родительский класс имеет
      // деструктор то мы должны сгенерировать деструктор
      if (!Dtor && baseDecl->Dtor) {
        generateDtor = true;
      }

      // Увеличиваем слот для переменных членов, т. к. 1 слот — 
      // экземпляр родительского класса
      ++curOffset;
    } else {
      // Это структура. Увеличиваем слот для переменных членов, 
      // т. к. 1 слот — экземпляр родительского класса
      ++curOffset;
    }
  }

  // Если у класса нет деструктора и есть переменные для очистки, 
  // то мы должны сгенерировать деструктор
  if (!Dtor && !defaultDtorBody.empty()) {
    generateDtor = true;
  }

  // Если VTable еще не было установленно (т. е. у родительского
  // класса нет виртуальных методов), то создаем свою таблицу
  // виртуальных методов
  if (!vtbl) {
    vtbl = new VTableAST(this);
  }

  // Проверяем все объявление на наличие виртуальных методов
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    // Пропускаем не методы
    if (!isa<FuncDeclAST>(*it)) {
      continue;
    }
    
    FuncDeclAST* fncDecl = (FuncDeclAST*)*it;

    // Пропускаем конструкторы
    if (fncDecl->isCtor()) {
      continue;
    }

    // Проверяем, существует ли метод в таблице виртуальных 
    // методов или нет
    if (vtbl->isExist(fncDecl)) {
      // Присутствует. Это должно быть "impl"
      if (!fncDecl->isOverride()) {
        scope->report(Loc, diag::ERR_SemaVirtualFunctionExists);
        return;
      }
    } else {
      // Отсутствует. Это должно быть "virt"
      if (fncDecl->isOverride()) {
        scope->report(Loc,
                      diag::ERR_SemaOverrideFunctionDoesntExists);
        return;
      }
    }

    // Если это виртуальный или переопределенный метод, то нам
    // нужно его добавить
    if (fncDecl->isVirtual() || fncDecl->isOverride()) {
      // Если у нас нет своей VTable, то клонируем таблицу
      // виртуальных методов родительского класса и берем ее
      // за основу
      if (vtableOwner == false) {
        vtbl = vtbl->clone(this);
        vtableOwner = true;
      }

      // Добавляем или перезаписываем функцию в таблице 
      // виртуальных методов
      vtbl->addOrReplace(scope, fncDecl);
    }
  }

  // Если VTable имеет хотя бы 1 виртуальный метод, то мы должны
  // его добавить
  if (vtbl->CurOffset > 0) {
    VTbl = vtbl;
    OwnVTable = vtableOwner;

    // Если родительский класс не имеет своей таблицы виртуальных
    // методов, то мы должны добавить слот для нее
    if (!baseHasVtbl) {
      ++curOffset;
    }
  }

  // Теперь мы должны рассчитать слот для каждой переменной 
  // члена класса
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    if (isa<VarDeclAST>(*it)) {
      ((VarDeclAST*)(*it))->OffsetOf = curOffset++;
    }
  }

  // Если нет явного конструктора, то пробуем создать конструктор
  // по умолчанию
  if (!Ctor) {
    // Пробуем создать конструктор по умолчанию
    SymbolAST* ctorDecl = generateDefaultConstructor(this);

    // Конструктор был сгенерирован. Производим его семантический
    // анализ и добавляем его к списку объявлений данного класса
    if (ctorDecl) {
      ctorDecl->semantic(s);
      Vars.push_back(ctorDecl);
      Ctor = true;
    }
  }

  // Проверяем нужен ли нам деструктор или нет
  if (generateDtor) {
    // Генерируем деструктор с пустым телом. Все необходимое 
    // будет сгенерировано во время семантического анализа
    ParameterList params;
    FuncTypeAST* dtorType = new FuncTypeAST(
      BuiltinTypeAST::get(TypeAST::TI_Void),
      params
    );
    SymbolAST* dtorDecl = new FuncDeclAST(
      Loc,
      dtorType,
      Name::Dtor, 
      new BlockStmtAST(Loc, defaultDtorBody), 
      true, 
      tok::Def
    );

    // Производим семантический анализ деструктора
    dtorDecl->semantic(s);

    // Если деструктор базового класса был виртуальным, то нам 
    // нужно его заменить
    if (VTbl && VTbl->isExist(dtorDecl)) {
      ((FuncDeclAST*)dtorDecl)->Tok = tok::Override;

      // Если у нас нет своей VTable, то клонируем таблицу 
      // виртуальных методов родительского класса и берем ее
      // за основу
      if (!vtableOwner) {
        VTbl = VTbl->clone(this);
      }

      // Заменяем деструтор в таблице виртуальных методов
      VTbl->addOrReplace(scope, dtorDecl);
    }

    Vars.push_back(dtorDecl);
    Dtor = true;
  }

  // Удаляем область видимости
  s->pop();
}

void ClassDeclAST::doSemantic5(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);

  // Запускаем 2-ю стадию семантического анализа для всех дочерних
  // объявлений
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    (*it)->semantic2(s);
  }

  // Запускаем 3-ю и 4-ю стадии семантического анализа для всех
  // дочерних объявлений
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    (*it)->semantic3(s);
    (*it)->semantic4(s);
  }

  // Запускаем финальную 5-ю стадию семантического анализа для
  // всех дочерних объявлений
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    (*it)->semantic5(s);
  }

  // Удаляем область видимости
  s->pop();
}

SymbolAST* ClassDeclAST::find(Name* id, int flags) {
  // Ищем объявление в данном классе
  SymbolAST* res = ScopeSymbol::find(id, flags);

  // Если нашли, то возвращаем его
  if (res) {
    return res;
  }

  // Если нужно, то пытаемся найти в родительском классе
  if ((flags & 1) == 0) {
    if (BaseClass && BaseClass->isAggregate()) {
      return BaseClass->getSymbol()->find(id, flags);
    }
  }

  return res;
}

bool ClassDeclAST::contain(TypeAST* type) {
  // Пробуем найти циклические зависимости в членах класса
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    if ((*it)->contain(type)) {
      return true;
    }
  }

  // Если есть родительский класс, то необходимо проверить наличие
  // циклов в нем
  if (BaseClass && BaseClass->isAggregate()) {
    return BaseClass->getSymbol()->contain(type);
  }

  return false;
}

Для параметров функции необходимо обновить функцию член класса canBeNull:

Hidden text
bool ParameterSymbolAST::canBeNull() {
  // Если это "this" или не указатель, то параметр не может быть 
  // "null"
  if (Param->Id == Name::This || !isa<PointerTypeAST>(Param->Param)) {
    return false;
  }

  // Это указатель, может быть "null"
  return true;
}

Семантика для функций также должна быть обновлена, т. к. нам необходимо добавить поддержку конструкторов, деструкторов, а так же поддержку перегрузки функций, так же нам нужно учитывать, что в методах класса могут быть специальные параметры и переменные, которые отвечают за "this" и "super":

Hidden text
bool FuncDeclAST::needThis() {
  return NeedThis;
}

void FuncDeclAST::doSemantic(Scope* scope) {
  // Методы класса имеют специальную обработку
  if (needThis()) {
    assert(isa<ClassDeclAST>(scope->CurScope));
    ClassDeclAST* classDecl = ((ClassDeclAST*)scope->CurScope);
    // Создаем параметр для "this", как неизменяемый указатель 
    // на объект класса
    ParameterAST* thisParam = new ParameterAST(
      new PointerTypeAST(classDecl->ThisType, true),
      Name::This);
    // Получаем тип текущей функции
    FuncTypeAST* thisType = (FuncTypeAST*)ThisType;
    // Указываем, что у функции есть "this"
    thisType->HasThis = true;
    // Добавляем "this" в качестве первого параметра функции
    thisType->Params.insert(thisType->Params.begin(), thisParam);
    AggregateSym = classDecl;

    // Добавляем особую обработку только, если у функции уже есть
    // тело
    if (Body) {
      BlockStmtAST* body = (BlockStmtAST*)Body;
      
      // Проверяем, что это конструктор
      if (isCtor()) {
        // Проверяем, что у нас есть вызов конструктор
        // родительского класса, но у нас либо нет родительского
        // класса, либо он не имеет конструктора
        if (!body->Body.empty() &&
          isa<ExprStmtAST>(*body->Body.begin())) {
          // Сообщаем об ошибке, если нет родительского класса или
          // он есть, но это структура
          if (!classDecl->BaseClass ||
            !isa<ClassTypeAST>(classDecl->BaseClass)) {
            scope->report(Loc,
              diag::ERR_SemaBaseClassNoConstructorToCall);
            return;
          }

          ClassDeclAST* baseDecl = 
            (ClassDeclAST*)classDecl->BaseClass->getSymbol();
          
          // Сообщаем об ошибке, если родительский класс не имеет 
          // конструктора
          if (!baseDecl->Ctor) {
            scope->report(Loc,
              diag::ERR_SemaBaseClassNoConstructorToCall);
            return;
          }
        } else {
          // У конструктора пока нет вызова конструктора 
          // родительского класса, мы должны сгенерировать вызов
          // конструктора по умолчанию, если необходимо
          if (classDecl->BaseClass &&
            isa<ClassTypeAST>(classDecl->BaseClass)) {
            // Родительский класс есть
            ClassDeclAST* baseDecl =
              (ClassDeclAST*)classDecl->BaseClass->getSymbol();

            // Проверяем, что у родительского класса есть 
            // конструктор
            if (baseDecl->Ctor) {
              // Генерируем вызов конструктора по умолчанию
              // родительского класса
              ExprList args;
              ExprStmtAST* exprStmt = new ExprStmtAST(
                Loc,
                new CallExprAST(
                  Loc,
                  new MemberAccessExprAST(
                    Loc,
                    new IdExprAST(Loc, Name::Super),
                    Name::Ctor), 
                  args));
              // Добавляем вызов конструктора родительского класса,
              // как 1-ю инструкцию в тело функции
              // Замечание: объявление переменной "super" будет
              // добавлен позже
              body->Body.insert(body->Body.begin(), exprStmt);
            }
          }
        }
      // Проверка деструктора
      } else if (isDtor()) {
        // Если у класса есть родительский класс и у него есть 
        // деструктор, то мы должны добавить его вызов
        if (classDecl->BaseClass &&
          isa<ClassTypeAST>(classDecl->BaseClass)) {
          ClassDeclAST* baseDecl = 
            (ClassDeclAST*)classDecl->BaseClass->getSymbol();

          // Проверка на то, что родительский класс имеет деструктор
          if (baseDecl->Dtor) {
            // Генерируем вызов деструктора базового класса
            ExprList args;
            ExprStmtAST* exprStmt = new ExprStmtAST(
              Loc,
              new CallExprAST(
                Loc,
                new MemberAccessExprAST(
                  Loc,
                  new IdExprAST(Loc, Name::Super),
                  Name::Dtor), 
                args));
            // Добавляем вызов деструктора в тело деструктора в
            // качестве последней инструкции
            body->Body.push_back(exprStmt);
          }
        }
      }

      // Если у класса есть родительский класс, то нам нужно 
      // объявить "super", как ссылка на экземпляр родительского
      // класса
      if (classDecl->BaseClass) {
        // Создаем объявление переменной "super", с типом
        // неизменяемого указателя на родительский класс
        VarDeclAST* superVar = new VarDeclAST(
          Loc, 
          new PointerTypeAST(classDecl->BaseClass, true), 
          Name::Super,
          new IdExprAST(Loc, Name::This),
          false);
        SymbolList tmp;
        // Добавляем объявление как 1-ю инструкцию в теле
        // конструктора
        tmp.push_back(superVar);
        body->Body.insert(
          body->Body.begin(),
          new DeclStmtAST(Loc, tmp)
        );
      }
    }
  }

  // Производим семантический анализ для прототипа функции
  ThisType = ThisType->semantic(scope);
  Parent = scope->CurScope;
  // Настраиваем тип возвращаемого значения
  ReturnType = ((FuncTypeAST*)ThisType)->ReturnType;
  
  // Отдельная проверка для функции "main"
  if (Id->Length == 4 && memcmp(Id->Id, "main", 4) == 0) {
    FuncTypeAST* thisType = (FuncTypeAST*)ThisType;

    // Должна не иметь параметров
    if (thisType->Params.size()) {
      scope->report(Loc, diag::ERR_SemaMainParameters);
      return;
    }

    // Должна возвращать "float"
    if (ReturnType != BuiltinTypeAST::get(TypeAST::TI_Float)) {
      scope->report(Loc, diag::ERR_SemaMainReturnType);
      return;
    }
  }

  // Ищем объявление функции в текущей области видимости
  if (SymbolAST* fncOverload = scope->findMember(Id, 1)) {
    // Проверяем, что это объявление функции
    if (isa<FuncDeclAST>(fncOverload)) {
      // Создаем набор перегруженных функций
      OverloadSetAST* newOverloadSet = new OverloadSetAST(Id);
      
      // Устанавливаем родительскую область видимости и добавляем
      // обе функции в него
      newOverloadSet->Parent = Parent;
      newOverloadSet->push(scope, fncOverload);
      newOverloadSet->push(scope, this);

      // Заменяем старое объявление в родительской области
      // видимости на только что созданный набор
      ((ScopeSymbol*)Parent)->Decls[Id] = newOverloadSet;
      return;
    }

    // Проверяем, что это набор перегруженных функций
    if (isa<OverloadSetAST>(fncOverload)) {
      // Да. Добавляем новую функции в набор
      ((OverloadSetAST*)fncOverload)->push(scope, this);
      return;
    }
    
    // Выдаем ошибку, т. к. имя было использовано для другого
    // объявления
    scope->report(Loc, diag::ERR_SemaFunctionRedefined, Id->Id);
    return;
  }

  // Добавляем функцию к списку объявлений
  ((ScopeSymbol*)Parent)->Decls[Id] = this;
}

Объявление для набора перегруженных функций:

Hidden text
void OverloadSetAST::push(Scope *scope, SymbolAST* func) {
  assert(isa<FuncDeclAST>(func));
  FuncDeclAST* funcDecl = (FuncDeclAST*)func;

  // Если у функции еще нет уникального сгенерируемого имени, то 
  // генерируем его
  if (!funcDecl->ThisType->MangleName.empty()) {
    funcDecl->ThisType->calcMangle();
  }

  // Пытаемся добавить функцию в список используемых перегрузок
  std::pair<llvm::StringSet< >::iterator, bool> res =
    OverloadsUsed.insert(funcDecl->ThisType->MangleName);

  // Проверяем была ли она добавлена ранее или нет
  if (!res.second) {
    // Да. Просматриваем все функции в наборе перегруженных функций
    for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
      it != end; ++it) {
      FuncDeclAST* oldFn = (FuncDeclAST*)(*it);
      
      // Проверяем на совпадение протатипов
      if (oldFn->ThisType->equal(funcDecl->ThisType)) {
        // Проверяем, что это функция объявленная в дочернем классе,
        // которая заменяет аналогичную функцию в родительском
        // классе
        if (oldFn->Parent != func->Parent) {
          // Заменяем функцию из базового класса 
          (*it) = func;
          return;
        }

        // Это дублирующая функция, выходим из цикла и сообщаем об
        // ошибке
        break;
      }
    }

    // Сообщаем об ошибке
    scope->report(
      funcDecl->Loc, 
      diag::ERR_SemaDuplicateFunctions, 
      funcDecl->Id->Id
    );
    return;
  }

  // Добавляем функцию в набор
  Vars.push_back(func);
}

OverloadSetAST* OverloadSetAST::clone() {
  // Создаем новый набор перегруженных функций
  OverloadSetAST* newSet = new OverloadSetAST(Id);

  // Переносим все значимые поля в копию
  newSet->Parent = Parent;
  newSet->Vars.assign(Vars.begin(), Vars.end());
  newSet->OverloadsUsed = OverloadsUsed;

  // Возвращаем копию
  return newSet;
}

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

Hidden text
void initRuntimeFuncs(ModuleDeclAST* modDecl) {
  addDynamicFunc(
    "fn print(_: char)",
    "lle_X_printChar",
    modDecl,
    (void*)lle_X_printChar
  );
  addDynamicFunc(
    "fn print(_: int)", 
    "lle_X_printInt",
    modDecl, 
    (void*)lle_X_printInt
  ;
  addDynamicFunc(
    "fn print(_: float)", 
    "lle_X_printDouble",
    modDecl, 
    (void*)lle_X_printDouble
  );
  addDynamicFunc(
    "fn print(_: string)", 
    "lle_X_printString", 
    modDecl,
    (void*)lle_X_printString
  );
  addDynamicFunc(
    "fn printLn(_: string)",
    "lle_X_printLine",
    modDecl, 
    (void*)lle_X_printLine
  );
  addDynamicFunc(
    "fn new(_: int) : void*",
    "lle_X_new", 
    modDecl,
    (void*)lle_X_new
  );
  addDynamicFunc(
    "fn delete(_: void*)", 
    "lle_X_delete",
    modDecl, 
    (void*)lle_X_delete
  );
}

Генерация кода

В генерации кода для типов у нас появился новый тип — ClassTypeAST:

Hidden text
Type* ClassTypeAST::getType() {
  // Исключаем повторную генерацию
  if (ThisType) {
    return ThisType;
  }

  llvm::SmallString< 128 > s;
  llvm::raw_svector_ostream output(s);

  // Для классов мы всегда добавляем "class." в начале имени
  output << "class.";
  calcAggregateName(output, ThisDecl);

  // Замечание: Мы должны создать новый тип и инициализировать им
  // ThisType, т. к. поля класса могут ссылаться на этот тип
  ThisType = StructType::create(getGlobalContext(), output.str());

  std::vector< Type* > vars;
  ClassDeclAST* classDecl = (ClassDeclAST*)ThisDecl;
  VTableAST* baseVtbl = nullptr;
  Type* baseType = nullptr;

  // Проверяем, есть ли у данного класса родительский класс или нет
  if (classDecl->BaseClass) {
    // Проверяем, что родительский класс является классом, а не 
    // структурой
    if (isa<ClassTypeAST>(classDecl->BaseClass)) {
      // Сохраняем таблицу виртуальных методов родительского класса,
      // если она есть
      ClassDeclAST* baseDecl = 
        (ClassDeclAST*)classDecl->BaseClass->getSymbol();
      baseVtbl = baseDecl->VTbl;
    }

    // Сохраняем тип родительского класса
    baseType = classDecl->BaseClass->getType();
  }

  // Если у класса есть таблица виртуальных методов, а у 
  // родительского класса ее не было, то у нас для этого есть
  // специальная обработка
  if (classDecl->VTbl && !baseVtbl) {
    // Добавляем слот для таблицы виртуальных методов
    // Замечание: Мы хотим, что бы таблица виртуальных методов
    // всегда была первым слотом в структуре класса
    vars.push_back(
      PointerType::get(
        getGlobalContext(),
        getSLContext().TheTarget->getProgramAddressSpace()
      )
    );
  }

  // Если у класса есть родительский класс, то добавляем его как
  // отдельный слот
  // Пример:
  //   class A { int a; }
  //   class B : A { int b; }
  // будет
  //   class.A = { int32 }
  //   class.B = { class.A, int32 }
  if (baseType) {
    vars.push_back(baseType);
  }

  // Мы должны обработать все дочерние объявления
  for (SymbolList::iterator it = classDecl->Vars.begin(),
    end = classDecl->Vars.end(); it != end; ++it) {
    // Добавляем в результирующую структуру только переменные
    if (isa<VarDeclAST>(*it)) {
      vars.push_back(((VarDeclAST*)(*it))->ThisType->getType());
    }
  }

  // Если у класса 0 членов, то мы должны добавить одно поле 
  // размером в 1 байт, иначе размер класса будет равен 0, что
  // нам не нужно
  if (vars.empty()) {
    vars.push_back(Type::getInt8Ty(getGlobalContext()));
  }

  // Добавляем все только что созданные члены к телу ранее 
  // созданной структуры класса
  ((StructType*)ThisType)->setBody(vars);
  return ThisType;
}

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

Hidden text
/// \param[in] Context - контекст
/// \param[in] val — указатель для преобразования
/// \param[in] var — объявление класса к которому нужно 
///   преобразовать
/// \param[in] agg — объявление класса из которого нужно
///   преобразовать
/// \param[in] canBeNull - true — если указатель может быть 
///   nullptr
Value* convertToBase(
  SLContext& Context, Value* val, SymbolAST* var, 
  SymbolAST* agg, bool canBeNull) {
  ClassDeclAST* thisDecl = (ClassDeclAST*)agg;
  SymbolAST* baseDecl = thisDecl->BaseClass->getSymbol();
  bool baseHasVTable = false;

  // Если родительский класс является классом, а не структурой, 
  // то нужно определить имеет ли он таблицу виртуальных методов
  // или нет
  if (isa<ClassDeclAST>(baseDecl)) {
    ClassDeclAST* baseClassDecl = (ClassDeclAST*)baseDecl;
    baseHasVTable = baseClassDecl->VTbl != nullptr;
  }
  
  // Если родительский класс не имеет собственной таблицы
  // виртуальных методов, то нам нужно произвести специальную 
  // обработку для приведения типов
  if (thisDecl->VTbl && baseHasVTable == false) {
    // Если значение может быть nullptr, то нам нужно произвести
    // дополнительные проверки
    if (canBeNull) {
      // Сейчас val содержит указатель на дочерний класс. Нам нужно
      // произвести проверку для безопасного преобразования,
      // если он равен nullptr
      Value* tmp = ConstantPointerNull::get(
        (PointerType*)val->getType()
      );
      // Сравниваем значение val с nullptr
      tmp = Context.TheBuilder->CreateICmpNE(val, tmp);

      // Создаем блоки для проверки
      BasicBlock* thenBlock = BasicBlock::Create(
        getGlobalContext(),
        "then",
        Context.TheFunction
      );
      BasicBlock* elseBlock = BasicBlock::Create(
        getGlobalContext(), 
        "else"
      );
      BasicBlock* contBlock = BasicBlock::Create(
        getGlobalContext(), 
        "ifcont"
      );

      // Производим условный переход в зависимости от результата 
      // сравнения с nullptr
      tmp = Context.TheBuilder->CreateCondBr(tmp, thenBlock, 
                                             elseBlock);
      Context.TheBuilder->SetInsertPoint(thenBlock);

      // 1. Корректируем указатель и пропускаем таблицу виртуальных
      // методов
      val = Context.TheBuilder->CreateGEP(
        Type::getInt8Ty(getGlobalContext()),
        val,
        getConstInt(
          Context.TheTarget->getTypeAllocSize(
            PointerType::get(
              getGlobalContext(),
              getSLContext().TheTarget->getProgramAddressSpace()
            )
          )
        )
      );

      // 2. Получаем реальный адрес родительского класса
      if (var != baseDecl) {
        // Тип результата не совпадаем с родительским классом 
        // текущего класса, значит результирующий класс является
        // родительским классом для класса результата, производим
        // преобразование еще раз
        val = convertToBase(Context, val, var, baseDecl, canBeNull);
      }

      // Сохраняем реальное значение для ветки "then", т. к. оно
      // могло измениться 
      thenBlock = Context.TheBuilder->GetInsertBlock();
      // Генерируем безусловный переход на "ifcont"
      Context.TheBuilder->CreateBr(contBlock);

      // Замечание: elseBlock не содержит никакого кода, только
      // безусловный переход на "ifcont"
      Context.TheFunction->getBasicBlockList().push_back(elseBlock);
      Context.TheBuilder->SetInsertPoint(elseBlock);

      Context.TheBuilder->CreateBr(contBlock);

      // В качестве текущего блока устанавливаем "ifcont"
      Context.TheFunction->getBasicBlockList().push_back(contBlock);
      Context.TheBuilder->SetInsertPoint(contBlock);

      // Создаем узел PHI с результатом операции
      PHINode* PN = Context.TheBuilder->CreatePHI(val->getType(), 2);

      // Добавляем значения для PHI, либо результат операции 
      // в "then", либо nullptr
      PN->addIncoming(val, thenBlock);
      PN->addIncoming(
        ConstantPointerNull::get((PointerType*)val->getType()), 
        elseBlock
      );

      // Возвращаем созданный узел PHI
      return PN;
    } else {
      // Значение указателя не может быть nullptr, поэтому нам не
      // нужны дополнительные проверки

      // 1. Корректируем указатель и пропускаем таблицу виртуальных
      // методов
      val = Context.TheBuilder->CreateGEP(
        Type::getInt8Ty(getGlobalContext()),
        val,
        getConstInt(
          Context.TheTarget->getTypeAllocSize(
            PointerType::get(
              getGlobalContext(),
              getSLContext().TheTarget->getProgramAddressSpace()
            )
          )
        )
      );

      // 2. Получаем реальный адрес родительского класса
      if (var != baseDecl) {
        // Тип результата не совпадаем с родительским классом 
        // текущего класса, значит результирующий класс является 
        // родительским классом для класса результата, производим
        // преобразование еще раз
        return convertToBase(Context, val, var, baseDecl, canBeNull);
      }

      // Возвращаем результат преобразования
      return val;
    }
  } else {
    // У нас либо нет таблицы виртуальных методов, либо оба класса
    // имеют ее

    // Если класс класс результата и класс родителя совпадают, то
    // возвращаем полученное значение "как есть"
    if (var == baseDecl) {
      return val;
    }

    // Тип результата не совпадаем с родительским классом текущего
    // класса, значит результирующий класс является родительским
    // классом для класса результата, производим преобразование
    // еще раз
    return convertToBase(Context, val, var, baseDecl, canBeNull);
  }
}

Для оператора обращения к члену класса нам нужно добавить поддержку того, что само объявление принадлежит родительскому классу, а не самому объекту:

Hidden text
Value* MemberAccessExprAST::getLValue(SLContext& Context) {
  // Для функций просто возвращаем ее тип
  if (isa<FuncTypeAST>(ExprType)) {
    return ThisSym->getValue(Context);
  }

  // Получаем lvalue для левой части (this)
  Value* val = Val->getLValue(Context);

  // Если член класса принадлежит родительскому классу, то нужно 
  // произвести преобразование типов 
  if (ThisSym->Parent != ThisAggr) {
    val = convertToBase(Context, val, ThisSym->Parent, ThisAggr, 
                        false);
  }

  // Генерирум индекс на основе индекса члена класса/структуры
  Value* index = getConstInt(((VarDeclAST*)ThisSym)->OffsetOf);

  std::vector< Value* > idx;

  idx.push_back(getConstInt(0));
  idx.push_back(index);

  // Создаем инструкцию GetElementPtr
  return Context.TheBuilder->CreateGEP(
    ThisSym->Parent->getType()->getType(),
    val,
    idx
  );
}

Value* CastExprAST::getRValue(SLContext& Context) {
  ...
  // Проверка на преобразования к указателю
  } else if (isa<PointerTypeAST>(ExprType)) {
    // Проверяем на приведение указателя
    if (isa<PointerTypeAST>(Val->ExprType)) {
      // Получаем rvalue для выражения
      Value* val = Val->getRValue(Context);

      // Получаем типы на которые указывают оба указателя
      TypeAST* next1 = ((PointerTypeAST*)ExprType)->Next;
      TypeAST* next2 = ((PointerTypeAST*)Val->ExprType)->Next;

      // У нас есть специальная обработка для классов и приведение к 
      // родительскому классу
      if (next1->isAggregate() && next1->isBaseOf(next2)) {
        // Получаем объявление для обоих классов
        SymbolAST* s1 = next1->getSymbol();
        SymbolAST* s2 = next2->getSymbol();

        // Производим преобразование
        return convertToBase(Context, val, s1, s2, Val->canBeNull());
      }

      // Возвращаем "как есть"
      return val;
    // Проверяем на приведение массива
    } else if (isa<ArrayTypeAST>(Val->ExprType)) {
    ...
}

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

Hidden text
Value* CallExprAST::getRValue(SLContext& Context) {
  Value* callee = nullptr;
  std::vector< Value* > args;
  ExprList::iterator it = Args.begin();
  Value* forcedReturn = nullptr;

  assert(isa<FuncDeclAST>(CallFunc));
  FuncDeclAST* funcDecl = (FuncDeclAST*)CallFunc;
  Type* funcRawType = CallFunc->getType()->getType();
  assert(isa<FunctionType>(funcRawType));
  FunctionType* funcType = static_cast<FunctionType*>(funcRawType);

  // Проверяем, является ли функция виртуальным методом или нет
  if (funcDecl->isVirtual() || funcDecl->isOverride()) {
    // Это виртуальный метод, производим динамическую 
    // диспетчиризацию
    assert(isa<MemberAccessExprAST>(Callee));
    MemberAccessExprAST* memAccess = (MemberAccessExprAST*)Callee;

    // Проверяем является ли Callee указателем или нет
    if (isa<DerefExprAST>(memAccess->Val)) {
      // Это разыменование указателя
      DerefExprAST* derefExpr = (DerefExprAST*)memAccess->Val;

      // Проверяем, что это "super", т. к. для "super" вызов 
      // должен быть обычным, а не динамическим
      if ((isa<IdExprAST>(derefExpr->Val) && 
        ((IdExprAST*)derefExpr->Val)->Val == Name::Super)) {
        // Это "super" в качестве параметра "this", делаем вызов
        // не виртуальным
        callee = CallFunc->getValue(Context);
      } else {
        // Этот вызов должен быть динамическим

        // Получаем "this"
        callee = memAccess->Val->getLValue(Context);

        // Получаем тип указателя
        PointerType* ptrType = PointerType::get(
          getGlobalContext(),
          getSLContext().TheTarget->getProgramAddressSpace()
        );

        // Загружаем таблицу виртуальных методов
        callee = Context.TheBuilder->CreateLoad(ptrType, callee);
        // Получаем виртуальный метод из таблицы по его индексу
        callee = Context.TheBuilder->CreateGEP(
          ptrType,
          callee,
          getConstInt(((FuncDeclAST*)CallFunc)->OffsetOf)
        );
        // Получаем адрес реального метода для вызова
        callee = Context.TheBuilder->CreateLoad(ptrType, callee);
      }
    } else {
      // Был ли "this" задан явно извне или нет
      if (memAccess->ForceThis) {
        // Этот вызов должен быть динамическим

        // Получаем "this"
        callee = memAccess->Val->getRValue(Context);

        // Получаем тип указателя
        PointerType* ptrType = PointerType::get(
          getGlobalContext(),
          getSLContext().TheTarget->getProgramAddressSpace()
        );

        // Загружаем таблицу виртуальных методов
        callee = Context.TheBuilder->CreateLoad(ptrType, callee);
        // Получаем виртуальный метод из таблицы по его индексу
        callee = Context.TheBuilder->CreateGEP(
          ptrType,
          callee,
          getConstInt(((FuncDeclAST*)CallFunc)->OffsetOf)
        );
        // Получаем адрес реального метода для вызова
        callee = Context.TheBuilder->CreateLoad(ptrType, callee);
      } else {
        // Это обычная функция, получаем ее адрес
        callee = CallFunc->getValue(Context);
      }
    }
  } else {
    // Это обычная функция, получаем ее адрес
    callee = CallFunc->getValue(Context);
  }
  
  // Для методов классов у нас есть специальная обработка
  if (isa<MemberAccessExprAST>(Callee)) {
    MemberAccessExprAST* memAccess = (MemberAccessExprAST*)Callee;
      // Был ли "this" задан явно извне или нет
    if (!memAccess->ForceThis) {
      // Нет. Получаем lvalue для левого операнда
      Value* val = (*it)->getLValue(Context);
      MemberAccessExprAST* memAccess = (MemberAccessExprAST*)Callee;

      // Производим преобразование указателя класса в указатель на 
      // родительский класс, если это необходимо
      if (memAccess->ThisSym->Parent != memAccess->ThisAggr) {
        val = convertToBase(
          Context,
          val,
          memAccess->ThisSym->Parent,
          memAccess->ThisAggr,
          false
        );
      }

      // Добавляем аргумент для "this"
      args.push_back(val);
      ++it;
    } else {
      // Специальная обработка для случае когда "this" был явно
      // задан извне
      MemberAccessExprAST* memAccess = (MemberAccessExprAST*)Callee;
      assert(memAccess->ThisSym->Parent == memAccess->ThisAggr);
      // Получаем rvalue и устанавливаем тип результат вызова явно
      forcedReturn = (*it)->getRValue(Context);

      // Добавляем аргумент для "this"
      args.push_back(forcedReturn);
      ++it;
    }
  }

  // Производим генерацию кода для каждого аргумента функции и 
  // добавляем их к списку аргументов функции
  for (ExprList::iterator end = Args.end(); it != end; ++it) {
    Value* v = (*it)->getRValue(Context);
    args.push_back(v);
  }

  // Если у нас тип результата вызова был указан явно
  if (forcedReturn) {
    // "this" был явно задан извне. Генерируем вызов функции, а в 
    // качестве результата возвращаем значение полученное ранее
    Context.TheBuilder->CreateCall(funcType, callee, args);
    return forcedReturn;
  } 
  
  // Генерируем вызов функции
  return Context.TheBuilder->CreateCall(funcType, callee, args);
}

Генерация кода для инструкций

Т.к. в функции в различных местах ее тела могут объявляться переменные, которые могут быть объектами классов у которых есть деструктор, то необходимо для этих переменных делать вызов деструкторов этих объектов, что бы произвести очистку ресурсов. Так же язык поддерживает различные управляющие конструкции, которые могут усложнить эту задачу. Рассмотрим варианты решения данной задачи на следующем примере программы на языке С++ (A — класс, у которого есть объявленный деструктор, который нужно вызвать для очистки ресурсов занимаемых данным объектом):

Hidden text
void foo(int z) {
  A a;
  for (int i = 0; i < 10; ++i) {
    A b;
    if (i == 4) {
      continue;
    }
    if (i == 6) {
      break;
    }
    if (i == z) {
      return;
    }
  }
}

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

Hidden text
void foo(int z) {
  A a;
  {
    int i = 0;
    
loopcond:
    if (i < 10) {
      goto loopbody;
    } else {
      goto loopend;
    }
    
loopbody:
    A b;
    
    if (i == 4) {
      b.~A();
      goto loopcont;
    }
    
    if (i == 6) {
      b.~A();
      goto loopend;
    }
    
    if (i == z) {
      b.~A();
      a.~A();
      return;
    }
    
loopcont:
    ++i;
    goto loopcond;
    
loopend:
  }
  
  a.~A();
  return;
}

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

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

Опишем список дополнений:

  1. Если в функции есть переменные для которых нужно будет вызвать деструкторы, то мы вводим новую переменную cleanupValue;

  2. Для каждого блока, где мы имеем переменные с деструкторами (и если в нем есть "break", "continue" или "return"), мы будем создавать новую метку CleanupLoc, на которую будет передаваться управление в не зависимости от того, были ли вызваны инструкции изменения стандартного потока выполнения программы или нет. После этой метки мы производим вызов деструкторов всех объектов объявленных в этом блоке, для которых их нужно вызвать, в обратном порядке их объявления. После этого мы создаем инструкцию switch, которая делает следующее:

  • Если значение cleanupValue равно 0, то мы переводим управление на FallthorughLoc родительского блока;

  • Если значение cleanupValue равно 2, то мы переводим управление на ContinueLoc родительского блока (доступно только в циклах);

  • Если значение cleanupValue равно 3, то мы переводим управление на BreakLoc родительского блока (доступно только в циклах);

  • Во всех остальных случаях переводим управление на CleanupLoc родительской функции, либо на ReturnLoc (если это блок самого верхнего уровня, у которого есть переменные для очистки).

  1. Если блок, для которого мы генерируем код является телом цикла (и в теле цикла есть "break", "continue" или "return"), то после всего кода цикла (и перед выполнения кода по метке CleanupLoc), мы должны сделать следующее:

  • Записать в cleanupValue значение 0;

  • Перейти на метку CleanupLoc.

  1. Для каждой инструкции "continue", если должна произведена очистка в данном блоке, мы должны будем сделать следующее:

  • Записать в cleanupValue значение 2;

  • Перейти на метку CleanupLoc.

  1. Для каждой инструкции "break", если должна произведена очистка в данном блоке, мы должны будем сделать следующее:

  • Записать в cleanupValue значение 2;

  • Перейти на метку CleanupLoc.

  1. Для каждой инструкции "return", если должна произведена очистка в данном блоке, мы должны будем сделать следующее:

  • Записать в cleanupValue значение 1;

  • Перейти на метку CleanupLoc.

Ниже рассмотрим псевдокод исходной функции, если к ней применить алгоритм приведенный выше:

Hidden text
void foo(int z) {
  int cleanupValue;
  A a;
  {
    int i = 0;
    
loopcond:
    if (i < 10) {
      goto loopbody;
    } else {
      goto loopend;
    }
    
loopbody:
    A b;
    
    if (i == 4) {
      cleanupValue = 2;
      goto cleanupLoc2;
    }
    
    if (i == 6) {
      cleanupValue = 3;
      goto cleanupLoc2;
    }
    
    if (i == z) {
      cleanupValue = 1;
      goto cleanupLoc2;
    }
    
    cleanupValue = 0;
    goto cleanupLoc2;
    
cleanupLoc2:
    b.~A();
    switch (cleanupValue) {
      case 0: goto loopcont;
      case 2: goto loopcont;
      case 3: goto loopend;
      default: goto cleanupLoc1;
    }

loopcont:
    ++i;
    goto loopcond;

loopend:
  }
  
cleanupLoc1:
  a.~A();
  goto returnLoc;

returnLoc:
  return;
}

Из приведенного кода выше видно, что несмотря на то, что он стал немного громоздким, но исчезло дублирование вызовов деструкторов и код стал более структурированным (Clang генерирует схожий код).

Примечание: В коде ниже есть еще одна оптимизация, которая исключает генерацию конструкций вида:

  br label1;
label1:
  br label2;
label2:
  br label3;
label3:
  br someLabel;

данная оптимизация приведет к генерации кода вида (все пустые блоки будет позже удалены после генерации тела всей функции):

  br someLabel;
label1:
label2:
label3:

Рассмотрим реализацию алгоритма описанного выше:

Hidden text
llvm::Value* BlockStmtAST::generatePartialCode(SLContext& Context, 
  StmtList::iterator it, StmtList::iterator end) {
  // Инициализируем блоки "break", "continue" и "return" для 
  // LandingPadAST текущего блока на основе родительского блока
  LandingPadAST* parent = LandingPad->Prev;
  LandingPad->BreakLoc = parent->BreakLoc;
  LandingPad->ContinueLoc = parent->ContinueLoc;
  LandingPad->ReturnLoc = parent->ReturnLoc;
  
  // CleanupLoc должна быть задана по разному, в зависимости от
  // того, нужно ли произвести очистку ресурсов или нет
  if (!LandingPad->NeedCleanup || CleanupList.empty()) {
    // Нет. Установить на основе родительского блока
    LandingPad->CleanupLoc = parent->CleanupLoc;
  } else {
    // Да. Создать новый блок
    LandingPad->CleanupLoc = BasicBlock::Create(getGlobalContext());
  }

  // Создаем новый блок FallthroughLoc (этот блок может быть 
  // использован в дочерних инструкциях, в качестве точки возврата
  // (например для выхода из цикла))
  LandingPad->FallthroughLoc = BasicBlock::Create(
    getGlobalContext(),
    "block"
  );
  
  // Нам нужно сохранять состояние последнего обработанного блока, 
  // а именно:
  // 1. Инструкция, которая была сгенерирвана последней;
  // 2. Последний использованный блок для возврата;
  // 3. Последняя точка вставки кода.
  StmtAST* lastStmt = nullptr;
  BasicBlock* lastFallThrough = nullptr;
  BasicBlock* lastInsertionPoint = nullptr;

  // Генерация кода для всех вложенных инструкций
  for (; it != end; ++it) {
    // Сохраняем FallthroughLoc (т. к. при использовании его
    // вложенная инструкция должна будет его обнулить)
    BasicBlock* fallthroughBB = LandingPad->FallthroughLoc;
    lastFallThrough = LandingPad->FallthroughLoc;

    // Генерируем код для вложенной инструкции
    lastStmt = *it;
    lastStmt->generateCode(Context);

    // Проверяем была ли FallthroughLoc использована во вложенной
    // инструкции или нет
    if (!LandingPad->FallthroughLoc) {
      // Была. Поэтому нужно добавить данный блок в конец функции,
      // как ее часть и задать его в качестве точки для вставки
      // нового кода
      lastInsertionPoint = Context.TheBuilder->GetInsertBlock();
      Context.TheFunction->getBasicBlockList().push_back(
        fallthroughBB
      );
      Context.TheBuilder->SetInsertPoint(fallthroughBB);

      // Записать в FallthroughLoc новый созданный блок, для
      // последующего использования во вложенных инструкциях
      LandingPad->FallthroughLoc = BasicBlock::Create(
        getGlobalContext(),
        "block"
      );
    }
  }

  // Делаем подсчет количество "break" "continue" и "return" 
  // инструкций в данном блоке (в последующих статьях будет 
  // ясно зачем они нужны)
  parent->Breaks += LandingPad->Breaks;
  parent->Continues += LandingPad->Continues;
  parent->Returns += LandingPad->Returns;

  // Проверяем нужно ли нам генерировать вызовы деструкторов или
  // нет
  if (LandingPad->NeedCleanup) {
    // Нужно

    // Если FallthroughLoc, которую мы создали для вложенных
    // инструкций не была использована, то производим ее очистку
    if (!LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
      delete LandingPad->FallthroughLoc;
    }

    // Если список переменных для очистки пуст, то нам ничего не
    // нужно делать
    if (CleanupList.empty()) {
      // Проверяем, что текущий блок имеет инструкцию завершения
      // блока (условный или безусловный переход)
      if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
        // Генерируем инструкцию перехода на FallthroughLoc 
        // родительского блока и помечаем, ее как использованную
        // (путем присвоения nullptr)
        Context.TheBuilder->CreateBr(parent->FallthroughLoc);
        parent->FallthroughLoc = nullptr;
        return nullptr;
      }

      return nullptr;
    }

    // Проверяем, что текущий блок имеет инструкцию завершения блока (условный
    // или безусловный переход)
    if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
      // Проверяем была ли последняя сгенерированная инструкция
      // блоком, который был создан на основе объявления 
      // объекта класса
      if (lastStmt && isa<BlockStmtAST>(lastStmt) && 
        ((BlockStmtAST*)lastStmt)->IsPromoted) {
        // Создаем безусловный переход на блок очистки
        Context.TheBuilder->CreateBr(LandingPad->CleanupLoc);
      } else {
        // Необходимо установить значение 0 в переменную статуса
        // очистки, а так же создать безусловный переход на блок
        // очистки
        Context.TheBuilder->CreateStore(
          getConstInt(0), 
          parent->getCleanupValue()
        );
        Context.TheBuilder->CreateBr(LandingPad->CleanupLoc);
      }
    }

    // Добавляем блок для очистки в конец функции и устанавливаем 
    // ее, как точку для генерации кода
    Context.TheFunction->getBasicBlockList().push_back(
      LandingPad->CleanupLoc
    );
    Context.TheBuilder->SetInsertPoint(LandingPad->CleanupLoc);
    LandingPad->CleanupLoc->setName("cleanup.block");

    // Генерируем вызовы деструкторов для всех созданных объектов
    // в данном блоке (мы должны их вызвать в обратном порядке
    // их объявления)
    for (ExprList::reverse_iterator it = CleanupList.rbegin(),
      end = CleanupList.rend(); it != end; ++it) {
      (*it)->getRValue(Context);
    }

    // Проверяем были ли у нас "break", "continue" и "return"
    // инструкции в данном блоке или нет
    if (!LandingPad->Returns && !LandingPad->Breaks &&
      !LandingPad->Continues) {
      // Нет, их не было. Генерируем инструкцию перехода на
      // FallthroughLoc родительского блока и помечаем, ее как
      // использованную (путем присвоения nullptr)
      Context.TheBuilder->CreateBr(parent->FallthroughLoc);
      parent->FallthroughLoc = nullptr;
    } else {
      // Да, есть. Определяем имеет ли родительский блок CleanupLoc 
      // или нет
      if (parent->CleanupLoc) {
        // Да. Определяем был ли блок создан из объявления объекта
        // или нет
        if (IsPromoted) {
          // Да.  Генерируем инструкцию перехода на FallthroughLoc
          // родительского блока
          Context.TheBuilder->CreateBr(parent->FallthroughLoc);
        } else {
          // Нет. Нам нужно создать "switch", который будет 
          // перенаправлять либо на родительский блок очистки,
          // либо на родительский блок FallthroughLoc, в 
          // зависимости от статуса очистки
          Value* val = Context.TheBuilder->CreateLoad(
            Type::getInt32Ty(getGlobalContext()),
            LandingPad->getCleanupValue()
          );
          SwitchInst* switchBB = Context.TheBuilder->CreateSwitch(
            val,
            parent->CleanupLoc
          );

          switchBB->addCase(getConstInt(0), parent->FallthroughLoc);
        }        
      } else {
        // Это блок очистки самого высокого уровня
        LandingPadAST* prev = parent;

        // Пытаемся найти предыдущий блок у которого есть блок
        // очистки
        while (prev->Prev) {
          if (prev->CleanupLoc) {
            break;
          }

          prev = prev->Prev;
        }

        // Определяем имеет ли родительский блок CleanupLoc или нет
        if (prev->CleanupLoc) {
          // Да. Нам нужно создать "switch", который будет 
          // перенаправлять либо на родительский блок очистки, 
          // либо на родительский блок FallthroughLoc, в зависимости
          // от статуса очистки, так же мы могли иметь вызовы
          // инструкций "break", "continue", которые тоже должны
          // быть добавлены в "switch"
          Value* val = Context.TheBuilder->CreateLoad(
            Type::getInt32Ty(getGlobalContext()),
            LandingPad->getCleanupValue()
          );
          SwitchInst* switchBB = Context.TheBuilder->CreateSwitch(
            val,
            prev->CleanupLoc
          );

          switchBB->addCase(getConstInt(0), parent->FallthroughLoc);

          // Если есть "continue", то добавляем новую ветку в 
          // "switch" с переходом на ContinueLoc
          if (LandingPad->Continues) {
            switchBB->addCase(getConstInt(2), parent->ContinueLoc);
          }

          // Если есть "break", то добавляем новую ветку в 
          // "switch" с переходом на BreakLoc
          if (LandingPad->Breaks) {
            switchBB->addCase(getConstInt(3), parent->BreakLoc);
          }
        } else {
          // Проверяем были ли у нас "break", "continue" и "return"
          // инструкции в данном блоке или нет
          if (LandingPad->Returns || LandingPad->Breaks ||
            LandingPad->Continues) {
            // Проверяем, что это не были "break" и "continue" и
            // блок возврата из функции отличается от блока 
            // FallthroughLoc родительского блока
            if (prev->ReturnLoc == parent->FallthroughLoc &&
              !LandingPad->Breaks && !LandingPad->Continues) {
              // Генерируем безусловный переход на выход из функции
              Context.TheBuilder->CreateBr(prev->ReturnLoc);
            } else {
              // Нам нужно создать "switch", который будет
              // перенаправлять либо на выход из функции, либо 
              // на родительский блок FallthroughLoc, в зависимости
              // от статуса очистки, так же мы могли иметь вызовы
              // инструкций "break", "continue", которые тоже должны
              // быть добавлены в "switch"
              Value* val = Context.TheBuilder->CreateLoad(
                Type::getInt32Ty(getGlobalContext()),
                LandingPad->getCleanupValue()
              );
              SwitchInst* switchBB =
                Context.TheBuilder->CreateSwitch(
                  val, 
                  prev->ReturnLoc
                );

              switchBB->addCase(
                getConstInt(0),
                parent->FallthroughLoc
              );

              // Если есть "continue", то добавляем новую ветку в
              // "switch" с переходом на ContinueLoc
              if (LandingPad->Continues) {
                switchBB->addCase(
                  getConstInt(2),
                  parent->ContinueLoc
                );
              }

              // Если есть "break", то добавляем новую ветку в 
              // "switch" с переходом на BreakLoc
              if (LandingPad->Breaks) {
                switchBB->addCase(getConstInt(3), parent->BreakLoc);
              }
            }
          } else {
            // Нет, их не было. Генерируем инструкцию перехода на 
            // FallthroughLoc родительского блока и помечаем, ее
            // как использованную (путем присвоения nullptr)
            Context.TheBuilder->CreateBr(parent->FallthroughLoc);
          }
        }
      }

      parent->FallthroughLoc = nullptr;
    }
  } else {
    // У нас нет блока для очистки

    // Проверяем, что текущий блок имеет инструкцию завершения 
    // блока (условный или безусловный переход)
    if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
      // Получаем количество инструкций в текущем блоке
      const unsigned u =
        Context.TheBuilder->GetInsertBlock()->size();

      // У нас есть оптимизация для варианта, когда блок пуст
      if (u == 0) {
        // Получить текущий блок
        BasicBlock *thisBlock = Context.TheBuilder->GetInsertBlock();

        // Если на этот блок есть только одна ссылка
        if (thisBlock->hasNUses(1)) {
          // Получаем блок, который ссылается на этот, а так же
          // инструкцию терминатор из него
          BasicBlock *prevBlock = thisBlock->getSinglePredecessor();
          Instruction *prevTerminator = prevBlock->getTerminator();

          // Если родительский блок цикл, то нам необходимо 
          // заменить все использования текущего блока на
          // FallthroughLoc родительского блока
          if (parent->IsLoop) {
            thisBlock->replaceAllUsesWith(parent->FallthroughLoc);
          }

          // Если FallthroughLoc, которую мы создали для вложенных
          // инструкций не была использована, то производим ее
          // очистку
          if (!LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
            delete LandingPad->FallthroughLoc;
          }

          return nullptr;
        }
      }

      // Генерируем инструкцию перехода на FallthroughLoc 
      // родительского блока и помечаем, ее как использованную 
      // (путем присвоения nullptr)
      Context.TheBuilder->CreateBr(parent->FallthroughLoc);
      parent->FallthroughLoc = nullptr;
      
      // Если FallthroughLoc, которую мы создали для вложенных
      // инструкций не была использована, то производим ее очистку
      if (!LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
        delete LandingPad->FallthroughLoc;
      }
    // Проверяем, что  FallthroughLoc был использован во вложенных
    // инструкциях
    } else if (LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
      // Был использован, нужно добавить его в конец функции,
      // установить его в качестве места вставки нового кода, а
      // также создаем безусловный переход на FallthroughLoc
      // родительского блока, а так же помечаем его как
      // использованную (путем присвоения nullptr)
      Context.TheFunction->getBasicBlockList().push_back(
        LandingPad->FallthroughLoc
      );
      Context.TheBuilder->SetInsertPoint(LandingPad->FallthroughLoc);
      Context.TheBuilder->CreateBr(parent->FallthroughLoc);
      parent->FallthroughLoc = nullptr;
    } else {
      // Нет. Производим ее очистку
      delete LandingPad->FallthroughLoc;
    }
  }

  return nullptr;
}

Value* LandingPadAST::getCleanupValue() {
  LandingPadAST* prev = this;

  // Находим корневой LandingPadAST
  while (prev->Prev) {
    prev = prev->Prev;
  }

  // Возвращаем ее CleanupValue
  return prev->CleanupValue;
}

Value* BreakStmtAST::generateCode(SLContext& Context) {
  // Есть ли у нас блок для очистки?
  if (BreakLoc->NeedCleanup) {
    // Да. Нужно сохранить значение 3 в переменную статус очистки
    // и произвести безусловный переход на CleanupLoc
    Context.TheBuilder->CreateStore(
      getConstInt(3),
      BreakLoc->getCleanupValue()
    );
    Context.TheBuilder->CreateBr(BreakLoc->CleanupLoc);
    return nullptr;
  }

  // Создать безусловный переход на  BreakLoc
  Context.TheBuilder->CreateBr(BreakLoc->BreakLoc);
  return nullptr;
}

Value* ContinueStmtAST::generateCode(SLContext& Context) {
  // Есть ли у нас блок для очистки?
  if (ContinueLoc->NeedCleanup) {
    // Да. Нужно сохранить значение 2 в переменную статус очистки
    // и произвести безусловный переход на CleanupLoc
    Context.TheBuilder->CreateStore(
      getConstInt(2), 
      ContinueLoc->getCleanupValue()
    );
    Context.TheBuilder->CreateBr(ContinueLoc->CleanupLoc);
    return nullptr;
  }

  // Создать безусловный переход на  ContinueLoc
  Context.TheBuilder->CreateBr(ContinueLoc->ContinueLoc);
  return nullptr;
}

Value* ReturnStmtAST::generateCode(SLContext& Context) {
  // Есть ли у нас блок для очистки?
  if (ReturnLoc->NeedCleanup) {
    // Да. Нужно сохранить значение 1 в переменную статус очистки
    // и произвести безусловный переход на CleanupLoc
    Context.TheBuilder->CreateStore(
      getConstInt(1),
      ReturnLoc->getCleanupValue()
    );

    // Проверяем, что у нас есть возвращаемое значение
    if (Expr) {
      // Генерируем код для выражения с возвращаемым значением 
      Value* retVal = Expr->getRValue(Context);
      // Создаем инструкцию "store" для сохранения возвращаемого
      // значения в переменной, для хранения результата выполнения
      // функции
      Context.TheBuilder->CreateStore(
        retVal, 
        ReturnLoc->getReturnValue()
      );
    }

    // Создаем безусловный переход на CleanupLoc
    Context.TheBuilder->CreateBr(ReturnLoc->CleanupLoc);
    return nullptr;
  }
  ...
}

llvm::Value* IfStmtAST::generateCode(SLContext& Context) {
  // Инициализируем блоки "break", "continue" и "return", а так 
  // же блок очистки для LandingPadAST текущего блока на основе
  // родительского блока
  LandingPadAST* prev = LandingPad->Prev;
  LandingPad->CleanupLoc = prev->CleanupLoc;
  LandingPad->ReturnLoc = prev->ReturnLoc;
  LandingPad->FallthroughLoc = prev->FallthroughLoc;
  LandingPad->ContinueLoc = prev->ContinueLoc;
  LandingPad->BreakLoc = prev->BreakLoc;
  ...
}

Генерация кода для объявлений

Поддержка объектов класса в объявлениях:

Hidden text
Value* VarDeclAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Получаем адрес переменной (т. к. память под саму переменную 
  // уже должна была выделена ранее во время генерации кода для
  // функции)
  Value* val = getValue(Context);

  // Специальная обработка для классов с конструктором
  if (Val && isa<ClassTypeAST>(ThisType)) {
    Val->getRValue(Context);
    return val;
  }
  ...
}

Таблица виртуальных методов:

Hidden text
Value* VTableAST::generateCode(SLContext& Context) {
  // Исключаем повторную генерацию кода
  if (CodeValue) {
    return CodeValue;
  }

  // Создаем таблицу виртуальных методов (все слоты будут заполнены 
  // позже)
  std::vector< Constant* > vtblEntries(CurOffset);

  // Обрабатываем все методы и наборы перегруженных методов в
  // таблице виртуальных методов
  for (SymbolMap::iterator it = Decls.begin(), end = Decls.end();
    it != end; ++it) {
    if (isa<OverloadSetAST>(it->second)) {
      // Это набор перегруженных функций
      OverloadSetAST* overloadSet = (OverloadSetAST*)it->second;

      // Обрабатываем все методы в наборе перегруженных функций
      for (SymbolList::iterator it2 = overloadSet->Vars.begin(),
        end2 = overloadSet->Vars.end(); it2 != end2; ++it2) {
        FuncDeclAST* fnc = (FuncDeclAST*)*it2;
        // Добавляем метод в соответствующий слот
        vtblEntries[fnc->OffsetOf] = ConstantExpr::getBitCast(
          (Function*)fnc->getValue(Context),
          PointerType::get(
            getGlobalContext(),
            getSLContext().TheTarget->getProgramAddressSpace()
          )
        );
      }
    } else {
      // Это обычная функция
      FuncDeclAST* fnc = (FuncDeclAST*)it->second;
      // Добавляем метод в соответствующий слот
      vtblEntries[fnc->OffsetOf] = ConstantExpr::getBitCast(
        (Function*)fnc->getValue(Context),
        PointerType::get(
          getGlobalContext(),
          getSLContext().TheTarget->getProgramAddressSpace()
        )
      );
    }
  }

  llvm::SmallString< 128 > s;
  llvm::raw_svector_ostream output(s);

  // Генерируем имя для таблицы виртуальных методов для класса
  output << "_PTV";
  mangleAggregateName(output, Parent);

  // Создаем массив указателей
  ArrayType* tableType = ArrayType::get(
    PointerType::get(
      getGlobalContext(),
      getSLContext().TheTarget->getProgramAddressSpace()
    ),
    CurOffset
  );
  // Добавляем таблицу виртуальных методов к списку глобальных
  // объявлений
  GlobalVariable* val =
    (GlobalVariable*)Context.TheModule->getOrInsertGlobal(
      output.str(), 
      tableType
    );
  // Инициализируем виртуальную таблицу данными
  val->setInitializer(ConstantArray::get(tableType, vtblEntries));
  // Сохраняем тип для этой таблицы
  VTblType = tableType;

  // Возвращаем только что сгенерированую глобальную переменную
  return CodeValue = val;
}

Генерация кода для объявлений классов:

Hidden text
llvm::Value* ClassDeclAST::getValue(SLContext& Context) {
  // Генерируем тип для класса
  ThisType->getType();

  // Генерируем тип для родительского класса, если он есть
  if (BaseClass) {
    BaseClass->getType();
  }

  return nullptr;
}

llvm::Value* ClassDeclAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Генерируем код для класса
  getValue(Context);

  // Генерируем таблицу виртуальных методов, если она нужна
  if (VTbl) {
    VTbl->generateCode(Context);
  }

  // Генерация кода для всех классов/структур и методов 
  // объявленных в классе
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    if (!isa<VarDeclAST>(*it)) {
      (*it)->generateCode(Context);
    }
  }

  return nullptr;
}

В генерации кода функций у нас появилась специальная обработка для конструкторов, деструкторов, а также поддержка статуса очистки (если в функции существуют объявления объектов класса с деструкторами, которые должны быть автоматически вызваны при выходе из блоков):

Hidden text
Value* FuncDeclAST::getValue(SLContext& Context) {
  // Генерируем код для объявления только один раз
  if (CodeValue) {
    return CodeValue;
  }

  SmallString< 128 > str;
  raw_svector_ostream output(str);

  // Производим генерацию имени функции (для "main" у нас есть 
  // специальная обработка)
  if (!(Id->Length == 4 && memcmp(Id->Id, "main", 4) == 0)) {
    // Генерация функций для методов класса чуть отличается
    if (needThis()) {
      // Для методов класса необходимо к имени функции добавить
      // полное имя агрегата
      assert(AggregateSym);
      output << "_P";
      mangleAggregateName(output, AggregateSym);
      output << Id->Length << StringRef(Id->Id, Id->Length);
      ThisType->toMangleBuffer(output);
    } else {
      // Генерация уникального декорированного имени функции
      output << "_P" << Id->Length << StringRef(Id->Id, Id->Length);
      ThisType->toMangleBuffer(output);
    }
  } else {
    output << "main";
  }

  // Создать функцию с внешним видом связанности для данного 
  // объявления
  CodeValue = Function::Create((FunctionType*)ThisType->getType(), 
    Function::ExternalLinkage, output.str(), nullptr);
  Context.TheModule->getFunctionList().push_back(CodeValue);

  return CodeValue;
}

Value* FuncDeclAST::generateCode(SLContext& Context) {
  ...
  // Создать блок для возврата из функции и установить его в 
  // качестве FallthroughLoc
  LandingPad->ReturnLoc = BasicBlock::Create(
    getGlobalContext(),
    "return.block"
  );
  LandingPad->FallthroughLoc = LandingPad->ReturnLoc;

  // Создаем переменную со статусом очистки, если она необходима
  if (LandingPad->NeedCleanup) {
    LandingPad->CleanupValue = Context.TheBuilder->CreateAlloca(
      Type::getInt32Ty(getGlobalContext()),
      0U,
      "cleanup.value"
    );
  }

  Function* oldFunction = Context.TheFunction;
  Context.TheFunction = CodeValue;

  if (isCtor()) {
    // Специальная обработка для конструктора
    assert(isa<BlockStmtAST>(Body));
    assert(isa<ClassDeclAST>(Parent));
    BlockStmtAST* blockStmt = (BlockStmtAST*)Body;
    ClassDeclAST* classDecl = (ClassDeclAST*)Parent;
    VTableAST* parentVtbl = nullptr;

    StmtList::iterator it = blockStmt->Body.begin();
    StmtList::iterator end = blockStmt->Body.end();

    // Если у класса есть родительский класс, то мы должны
    // произвести специальную обработку
    if (classDecl->BaseClass) {
      // 1-я инструкция в теле конструкция — объявление переменной
      // "super". Генерируем ее и переходим к следующей инструкции
      (*it)->generateCode(Context);
      ++it;
      
      // Если родительский класс является классом, а не структурой,
      // то мы должны произвести специальную обработку  
      if (isa<ClassTypeAST>(classDecl->BaseClass)) {
        ClassDeclAST* baseDecl =
          (ClassDeclAST*)classDecl->BaseClass->getSymbol();
        parentVtbl = baseDecl->VTbl;

        // Проверяем, что у родительского класса есть конструктор
        if (baseDecl->Ctor) {
          // Он есть. Генерируем код для его вызова и переходим к
          // следующей инструкции
          (*it)->generateCode(Context);
          ++it;
        }
      }
    }

    // Если у класса есть таблица виртуальных методов и она 
    // отличается от таблицы класса родителя, то мы должны 
    // сделать специальную обработку
    if (classDecl->VTbl != parentVtbl) {
      SymbolAST* thisParam = find(Name::This);
      assert(thisParam != nullptr);
      // Генерируем код для параметра "this" и производим загрузку
      // параметра
      Value* val = thisParam->getValue(Context);

      val = Context.TheBuilder->CreateLoad(
        PointerType::get(
          getGlobalContext(),
          getSLContext().TheTarget->getProgramAddressSpace()
        ),
        val
      );
      
      // Генерируем код для таблицы виртуальных методов
      Value* vtblVal = classDecl->VTbl->generateCode(Context);

      std::vector< Value* > idx;

      idx.push_back(getConstInt(0));
      idx.push_back(getConstInt(0));

      // Генерируем инструкцию GetElementPtr для загрузки адреса
      // таблицы виртуальных методов из глобальной переменной
      vtblVal = Context.TheBuilder->CreateInBoundsGEP(
        classDecl->VTbl->VTblType,
        vtblVal,
        idx
      );
      // Сохраняем указатель на таблицу виртуальных методов в 
      // экземпляре класса
      val = Context.TheBuilder->CreateStore(vtblVal, val);
    }

    // Генерируем код для оставшейся части тела функции
    blockStmt->generatePartialCode(Context, it, end);
  } else if (isDtor()) {
    // У нас есть специальная обработка для деструкторов
    assert(isa<BlockStmtAST>(Body));
    assert(isa<ClassDeclAST>(Parent));
    BlockStmtAST* blockStmt = (BlockStmtAST*)Body;
    ClassDeclAST* classDecl = (ClassDeclAST*)Parent;

    // Если у класса есть родительский класс и это класс, а не 
    // структура, то нам нужно произвести специальную обработку
    if (classDecl->BaseClass &&
      isa<ClassTypeAST>(classDecl->BaseClass)) {
      ClassDeclAST* baseDecl = 
        (ClassDeclAST*)classDecl->BaseClass->getSymbol();

      // Обрабатываем случай, когда у родительского класса есть
      // деструктор
      if (baseDecl->Dtor) {
        // Получаем первую и последнюю инструкции тела деструктора
        StmtList::iterator it = blockStmt->Body.begin();
        StmtList::iterator end = blockStmt->Body.end();
        // Последняя инструкция будет вызов деструктора
        // родительского класса, генерацию которого мы произведем
        // позже, поэтому мы должны исключить его из генерации
        --end;

        // Для деструктора мы должны создать новый блок 
        // для FallthroughLoc, т. к. он может быть использован
        // в generatePartialCode
        BasicBlock* falthroughBB = BasicBlock::Create(
          getGlobalContext()
        );
        LandingPad->FallthroughLoc = falthroughBB;

        // Генерируем код для всех инструкций, кроме вызова 
        // деструктора родительского класса
        blockStmt->generatePartialCode(Context, it, end);

        // Либо добавляем блок FallthroughLoc, либо удаляем в
        // зависимости от того был ли он использован или нет
        if (falthroughBB->hasNUsesOrMore(1)) {
          CodeValue->getBasicBlockList().push_back(falthroughBB);
          Context.TheBuilder->SetInsertPoint(falthroughBB);
        } else {
          delete falthroughBB;
        }

        // Устанавливаем в качестве FallthroughLoc блок ReturnLoc
        LandingPad->FallthroughLoc = LandingPad->ReturnLoc;

        // Текущая инструкция для генерации — вызов деструктора
        // родительского класса. Но перед его вызовом нам 
        // необходимо сгенерировать установить в качестве таблицы
        // виртуальных методов таблицу родительского класса
        // (если они отличаются, но родительский класс ее имеет)
        if (classDecl->VTbl != baseDecl->VTbl && baseDecl->VTbl) {
          SymbolAST* thisParam = find(Name::This);
          assert(!thisParam);
          // Генерируем код для параметра "this" и производим 
          // загрузку параметра
          Value* val = thisParam->getValue(Context);
          val = Context.TheBuilder->CreateLoad(
            PointerType::get(
              getGlobalContext(),
              getSLContext().TheTarget->getProgramAddressSpace()
            ),
            val
          );
          // Генерируем код для таблицы виртуальных методов 
          // родительского класса
          Value* vtblVal = baseDecl->VTbl->generateCode(Context);

          std::vector< Value* > idx;

          idx.push_back(getConstInt(0));
          idx.push_back(getConstInt(0));

          // Генерируем инструкцию GetElementPtr для загрузки адреса
          // таблицы виртуальных методов родительского класса из
          // глобальной переменной
          vtblVal = Context.TheBuilder->CreateInBoundsGEP(
            baseDecl->VTbl->VTblType, 
            vtblVal, 
            idx
          );
          // Сохраняем указатель на таблицу виртуальных методов в 
          // экземпляре класса
          val = Context.TheBuilder->CreateStore(vtblVal, val);
        }

        // Генерация кода для вызова деструктора родительского 
        // класса
        (*end)->generateCode(Context);
      } else {
        // У нас нет никаких специальных обработок. Генерируем 
        // код "как есть"
        Body->generateCode(Context);
      }
    } else {
      // У нас нет никаких специальных обработок. Генерируем 
      // код "как есть"
      Body->generateCode(Context);
    }
  } else {
    // Генерация кода для тела функции
    Body->generateCode(Context);
  }
 
  Context.TheFunction = oldFunction;

  // Добавляем условный переход на блок выхода из функции, если
  // он еще не был сгенерирован
  if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
    Context.TheBuilder->CreateBr(LandingPad->ReturnLoc);
  }

  // Добавить блок для возврата из функции в конец функции и
  // установить его в качестве точки генерации кода
  CodeValue->getBasicBlockList().push_back(LandingPad->ReturnLoc);
  Context.TheBuilder->SetInsertPoint(LandingPad->ReturnLoc);
  
  if (!ReturnType->isVoid()) {
    // Тип возвращаемого значение не "void". Создаем инструкцию 
    // "load" для загрузки возвращаемого значения
    Value* ret = Context.TheBuilder->CreateLoad(
      ReturnType->getType(),
      LandingPad->ReturnValue
    );
    // Генерация инструкции возврата из функции
    Context.TheBuilder->CreateRet(ret);
  } else {
    // Генерация инструкции возврата из функции для "void"
    Context.TheBuilder->CreateRetVoid();
  }

  // Восстановление предыдущей точки генерации кода (если нужно)
  if (oldBlock) {
    Context.TheBuilder->SetInsertPoint(oldBlock);
  }

  Function::BasicBlockListType &blocksList = 
    CodeValue->getBasicBlockList();

  // Небольшая оптимизация. Мы удаляем все блоки из функции, у 
  // которых нет инструкции завершения
  for (Function::BasicBlockListType::iterator it = 
    blocksList.begin(), lastBlock = blocksList.end();
    it != lastBlock; ) {
    if (!it->getTerminator()) {
      Function::BasicBlockListType::iterator cur = it;

      ++it;

      blocksList.erase(cur);
    } else {
      ++it;
    }
  }

  // Проверка кода функции и оптимизация (если она включена)
  verifyFunction(*CodeValue, &llvm::errs());
  
  Compiled = true;

  return CodeValue;
}

Заключение

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

Полный исходный код доступен на github.

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

Возможно, если серия будет интересна, то она получит продолжение. Всем успехов в мире разработки языков программирования коммерческих и для души.

Комментарии (4)


  1. nimishin
    21.04.2023 09:46
    -1

    Класс, всегда мечтал написать свой язык программирования))


  1. rsashka
    21.04.2023 09:46

    Возможно, если серия будет интересна, то она получит продолжение. Всем успехов в мире разработки языков программирования коммерческих и для души.

    Очень актуальная серия для тех, что сам хочет или уже разрабатывает собственный язык программирования (например, как я :-) ). И хотя я с некоторыми вещами не согласен или считают их пережитком прошлого, но сам материал очень полезен. Очень надеюсь, что продолжение все же будет, так как задумка мало того, что интересна само по себе, но еще и полезна в плане примеров и дополнительного опыта.


    1. DCSinpo Автор
      21.04.2023 09:46

      Спасибо. Было бы интересно узнать, с чем именно вы не согласны, всегда интересно услышать мнения со стороны)


      1. rsashka
        21.04.2023 09:46

        Мое не согласие относится скорее не к реализации, а только к семантике языка. Он у вас практически повторяет С++ со всеми его наворотами и сопутствующими проблемами.

        Мне кажется, что создавая новый язык можно было бы исправить некоторые из них, которые С++ просто вынужден поддерживать для обратной совместимости. Ведь в новом языке обратная совместимость не требуется.

        Но так как ваша цель больше показать пример реализации языка с использованием LLVM, то мое замечание не принципиальное, так как свою задачу ваши статьи выполняют хорошо. А для целей обучения, даже правильно делать семантику похожую на С++, чтобы можно было с чем сравнивать.