include/swift/Demangling/TypeDecoder.h

//===--- TypeDecoder.h - Decode mangled type names --------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file provides facilities to \c TypeDecoder, which decodes a mangled
// type name into a structured type representation.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_DEMANGLING_TYPEDECODER_H
#define SWIFT_DEMANGLING_TYPEDECODER_H

#include "TypeLookupError.h"
#include "swift/ABI/MetadataValues.h"
#include "swift/Basic/LLVM.h"
#include "swift/Demangling/Demangler.h"
#include "swift/Demangling/NamespaceMacros.h"
#include "swift/Runtime/Portability.h"
#include "swift/Basic/Unreachable.h"
#include "swift/Strings.h"
#include "llvm/ADT/ArrayRef.h"
#include <vector>

namespace swift {
namespace Demangle {
SWIFT_BEGIN_INLINE_NAMESPACE

enum class ImplMetatypeRepresentation {
  Thin,
  Thick,
  ObjC,
};

/// Describe a function parameter, parameterized on the type
/// representation.
template <typename BuiltType>
class FunctionParam {
  StringRef Label;
  BuiltType Type;
  ParameterFlags Flags;

  FunctionParam(StringRef label, BuiltType type, ParameterFlags flags)
      : Label(label), Type(type), Flags(flags) {}

public:
  explicit FunctionParam() {}

  FunctionParam(BuiltType type) : Type(type) {}

  StringRef getLabel() const { return Label; }
  BuiltType getType() const { return Type; }
  ParameterFlags getFlags() const { return Flags; }

  void setLabel(StringRef label) { Label = label; }
  void setType(BuiltType type) { Type = type; }

  void setVariadic() { Flags = Flags.withVariadic(true); }
  void setAutoClosure() { Flags = Flags.withAutoClosure(true); }
  void setValueOwnership(ValueOwnership ownership) {
    Flags = Flags.withValueOwnership(ownership);
  }
  void setFlags(ParameterFlags flags) { Flags = flags; };

  FunctionParam withLabel(StringRef label) const {
    return FunctionParam(label, Type, Flags);
  }

  FunctionParam withType(BuiltType type) const {
    return FunctionParam(Label, type, Flags);
  }

  FunctionParam withFlags(ParameterFlags flags) const {
    return FunctionParam(Label, Type, flags);
  }
};

enum class ImplParameterConvention {
  Indirect_In,
  Indirect_In_Constant,
  Indirect_In_Guaranteed,
  Indirect_Inout,
  Indirect_InoutAliasable,
  Direct_Owned,
  Direct_Unowned,
  Direct_Guaranteed,
};

enum class ImplParameterDifferentiability {
  DifferentiableOrNotApplicable,
  NotDifferentiable
};

/// Describe a lowered function parameter, parameterized on the type
/// representation.
template <typename BuiltType>
class ImplFunctionParam {
  BuiltType Type;
  ImplParameterConvention Convention;
  ImplParameterDifferentiability Differentiability;

public:
  using ConventionType = ImplParameterConvention;
  using DifferentiabilityType = ImplParameterDifferentiability;

  static llvm::Optional<ConventionType>
  getConventionFromString(StringRef conventionString) {
    if (conventionString == "@in")
      return ConventionType::Indirect_In;
    if (conventionString == "@in_constant")
      return ConventionType::Indirect_In_Constant;
    if (conventionString == "@in_guaranteed")
      return ConventionType::Indirect_In_Guaranteed;
    if (conventionString == "@inout")
      return ConventionType::Indirect_Inout;
    if (conventionString == "@inout_aliasable")
      return ConventionType::Indirect_InoutAliasable;
    if (conventionString == "@owned")
      return ConventionType::Direct_Owned;
    if (conventionString == "@unowned")
      return ConventionType::Direct_Unowned;
    if (conventionString == "@guaranteed")
      return ConventionType::Direct_Guaranteed;

    return None;
  }

  static llvm::Optional<DifferentiabilityType>
  getDifferentiabilityFromString(StringRef string) {
    if (string.empty())
      return DifferentiabilityType::DifferentiableOrNotApplicable;
    if (string == "@noDerivative")
      return DifferentiabilityType::NotDifferentiable;
    return None;
  }

  ImplFunctionParam(BuiltType type, ImplParameterConvention convention,
                    ImplParameterDifferentiability diffKind)
      : Type(type), Convention(convention), Differentiability(diffKind) {}

  ImplParameterConvention getConvention() const { return Convention; }

  ImplParameterDifferentiability getDifferentiability() const {
    return Differentiability;
  }

  BuiltType getType() const { return Type; }
};

enum class ImplResultConvention {
  Indirect,
  Owned,
  Unowned,
  UnownedInnerPointer,
  Autoreleased,
};

enum class ImplResultDifferentiability {
  DifferentiableOrNotApplicable,
  NotDifferentiable
};

/// Describe a lowered function result, parameterized on the type
/// representation.
template <typename BuiltType>
class ImplFunctionResult {
  BuiltType Type;
  ImplResultConvention Convention;
  ImplResultDifferentiability Differentiability;

public:
  using ConventionType = ImplResultConvention;
  using DifferentiabilityType = ImplResultDifferentiability;

  static llvm::Optional<ConventionType>
  getConventionFromString(StringRef conventionString) {
    if (conventionString == "@out")
      return ConventionType::Indirect;
    if (conventionString == "@owned")
      return ConventionType::Owned;
    if (conventionString == "@unowned")
      return ConventionType::Unowned;
    if (conventionString == "@unowned_inner_pointer")
      return ConventionType::UnownedInnerPointer;
    if (conventionString == "@autoreleased")
      return ConventionType::Autoreleased;

    return None;
  }

  static llvm::Optional<DifferentiabilityType>
  getDifferentiabilityFromString(StringRef string) {
    if (string.empty())
      return DifferentiabilityType::DifferentiableOrNotApplicable;
    if (string == "@noDerivative")
      return DifferentiabilityType::NotDifferentiable;
    return None;
  }

  ImplFunctionResult(
      BuiltType type, ImplResultConvention convention,
      ImplResultDifferentiability diffKind =
          ImplResultDifferentiability::DifferentiableOrNotApplicable)
      : Type(type), Convention(convention), Differentiability(diffKind) {}

  ImplResultConvention getConvention() const { return Convention; }

  ImplResultDifferentiability getDifferentiability() const {
    return Differentiability;
  }

  BuiltType getType() const { return Type; }
};

enum class ImplFunctionRepresentation {
  Thick,
  Block,
  Thin,
  CFunctionPointer,
  Method,
  ObjCMethod,
  WitnessMethod,
  Closure
};

enum class ImplFunctionDifferentiabilityKind {
  NonDifferentiable,
  Normal,
  Linear
};

class ImplFunctionTypeFlags {
  unsigned Rep : 3;
  unsigned Pseudogeneric : 1;
  unsigned Escaping : 1;
  unsigned Async : 1;
  unsigned DifferentiabilityKind : 2;

public:
  ImplFunctionTypeFlags()
      : Rep(0), Pseudogeneric(0), Escaping(0), Async(0),
        DifferentiabilityKind(0) {}

  ImplFunctionTypeFlags(ImplFunctionRepresentation rep, bool pseudogeneric,
                        bool noescape, bool async,
                        ImplFunctionDifferentiabilityKind diffKind)
      : Rep(unsigned(rep)), Pseudogeneric(pseudogeneric), Escaping(noescape),
        Async(async), DifferentiabilityKind(unsigned(diffKind)) {}

  ImplFunctionTypeFlags
  withRepresentation(ImplFunctionRepresentation rep) const {
    return ImplFunctionTypeFlags(
        rep, Pseudogeneric, Escaping, Async,
        ImplFunctionDifferentiabilityKind(DifferentiabilityKind));
  }

  ImplFunctionTypeFlags
  withAsync() const {
    return ImplFunctionTypeFlags(
        ImplFunctionRepresentation(Rep), Pseudogeneric, Escaping, true,
        ImplFunctionDifferentiabilityKind(DifferentiabilityKind));
  }

  ImplFunctionTypeFlags
  withEscaping() const {
    return ImplFunctionTypeFlags(
        ImplFunctionRepresentation(Rep), Pseudogeneric, true, Async,
        ImplFunctionDifferentiabilityKind(DifferentiabilityKind));
  }
  
  ImplFunctionTypeFlags
  withPseudogeneric() const {
    return ImplFunctionTypeFlags(
        ImplFunctionRepresentation(Rep), true, Escaping, Async,
        ImplFunctionDifferentiabilityKind(DifferentiabilityKind));
  }

  ImplFunctionTypeFlags
  withDifferentiabilityKind(ImplFunctionDifferentiabilityKind diffKind) const {
    return ImplFunctionTypeFlags(ImplFunctionRepresentation(Rep), Pseudogeneric,
                                 Escaping, Async, diffKind);
  }

  ImplFunctionRepresentation getRepresentation() const {
    return ImplFunctionRepresentation(Rep);
  }

  bool isAsync() const { return Async; }

  bool isEscaping() const { return Escaping; }

  bool isPseudogeneric() const { return Pseudogeneric; }

  ImplFunctionDifferentiabilityKind getDifferentiabilityKind() const {
    return ImplFunctionDifferentiabilityKind(DifferentiabilityKind);
  }
};

#if SWIFT_OBJC_INTEROP
/// For a mangled node that refers to an Objective-C class or protocol,
/// return the class or protocol name.
static inline llvm::Optional<StringRef>
getObjCClassOrProtocolName(NodePointer node) {
  if (node->getKind() != Demangle::Node::Kind::Class &&
      node->getKind() != Demangle::Node::Kind::Protocol)
    return None;

  if (node->getNumChildren() != 2)
    return None;

  // Check whether we have the __ObjC module.
  auto moduleNode = node->getChild(0);
  if (moduleNode->getKind() != Demangle::Node::Kind::Module ||
      moduleNode->getText() != MANGLING_MODULE_OBJC)
    return None;

  // Check whether we have an identifier.
  auto nameNode = node->getChild(1);
  if (nameNode->getKind() != Demangle::Node::Kind::Identifier)
    return None;

  return nameNode->getText();
}
#endif

#define MAKE_NODE_TYPE_ERROR(Node, Fmt, ...)                                   \
  TypeLookupError("TypeDecoder.h:%d: Node kind %u \"%.*s\" - " Fmt, __LINE__,  \
                  Node->getKind(),                                             \
                  Node->hasText() ? (int)Node->getText().size() : 0,           \
                  Node->hasText() ? Node->getText().data() : "", __VA_ARGS__)

#define MAKE_NODE_TYPE_ERROR0(Node, Str) MAKE_NODE_TYPE_ERROR(Node, "%s", Str)

/// Decode a mangled type to construct an abstract type, forming such
/// types by invoking a custom builder.
template <typename BuilderType>
class TypeDecoder {
  using BuiltType = typename BuilderType::BuiltType;
  using BuiltTypeDecl = typename BuilderType::BuiltTypeDecl;
  using BuiltProtocolDecl = typename BuilderType::BuiltProtocolDecl;
  using NodeKind = Demangle::Node::Kind;

  BuilderType &Builder;

public:
  explicit TypeDecoder(BuilderType &Builder) : Builder(Builder) {}

  /// Given a demangle tree, attempt to turn it into a type.
  TypeLookupErrorOr<BuiltType> decodeMangledType(NodePointer Node) {
    if (!Node)
      return TypeLookupError("Node is NULL");

    using NodeKind = Demangle::Node::Kind;
    switch (Node->getKind()) {
    case NodeKind::Global:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children.");

      return decodeMangledType(Node->getChild(0));
    case NodeKind::TypeMangling:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children.");

      return decodeMangledType(Node->getChild(0));
    case NodeKind::Type:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children.");

      return decodeMangledType(Node->getChild(0));
    case NodeKind::Class:
    {
#if SWIFT_OBJC_INTEROP
      if (auto mangledName = getObjCClassOrProtocolName(Node))
        return Builder.createObjCClassType(mangledName->str());
#endif
      LLVM_FALLTHROUGH;
    }
    case NodeKind::Enum:
    case NodeKind::Structure:
    case NodeKind::TypeAlias:
    case NodeKind::TypeSymbolicReference:
    {
      BuiltTypeDecl typeDecl = BuiltTypeDecl();
      BuiltType parent = BuiltType();
      bool typeAlias = false;
      if (auto error = decodeMangledTypeDecl(Node, typeDecl, parent, typeAlias))
        return *error;

      if (typeAlias)
        return Builder.createTypeAliasType(typeDecl, parent);

      return Builder.createNominalType(typeDecl, parent);
    }

    case NodeKind::BoundGenericEnum:
    case NodeKind::BoundGenericStructure:
    case NodeKind::BoundGenericClass:
    case NodeKind::BoundGenericTypeAlias:
    case NodeKind::BoundGenericOtherNominalType: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      llvm::SmallVector<BuiltType, 8> args;

      const auto &genericArgs = Node->getChild(1);
      if (genericArgs->getKind() != NodeKind::TypeList)
        return MAKE_NODE_TYPE_ERROR0(genericArgs, "is not TypeList");

      for (auto genericArg : *genericArgs) {
        auto paramType = decodeMangledType(genericArg);
        if (paramType.isError())
          return paramType;
        args.push_back(paramType.getType());
      }

      auto ChildNode = Node->getChild(0);
      if (ChildNode->getKind() == NodeKind::Type &&
          ChildNode->getNumChildren() > 0)
        ChildNode = ChildNode->getChild(0);

#if SWIFT_OBJC_INTEROP
      if (auto mangledName = getObjCClassOrProtocolName(ChildNode))
        return Builder.createBoundGenericObjCClassType(mangledName->str(),
                                                       args);
#endif

      BuiltTypeDecl typeDecl = BuiltTypeDecl();
      BuiltType parent = BuiltType();
      bool typeAlias = false;
      if (auto error =
              decodeMangledTypeDecl(ChildNode, typeDecl, parent, typeAlias))
        return *error;

      return Builder.createBoundGenericType(typeDecl, args, parent);
    }
    case NodeKind::BoundGenericProtocol: {
      // This is a special case. When you write a protocol typealias with a
      // concrete type base, for example:
      //
      // protocol P { typealias A<T> = ... }
      // struct S : P {}
      // let x: S.A<Int> = ...
      //
      // The mangling tree looks like this:
      //
      // BoundGenericProtocol ---> BoundGenericTypeAlias
      // |                         |
      // |                         |
      // --> Protocol: P           --> TypeAlias: A
      // |                         |
      // --> TypeList:             --> TypeList:
      //     |                         |
      //     --> Structure: S          --> Structure: Int
      //
      // When resolving the mangling tree to a decl, we strip off the
      // BoundGenericProtocol's *argument*, leaving behind only the
      // protocol reference.
      //
      // But when resolving it to a type, we want to *keep* the argument
      // so that the parent type becomes 'S' and not 'P'.
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      const auto &genericArgs = Node->getChild(1);
      if (genericArgs->getNumChildren() != 1)
        return MAKE_NODE_TYPE_ERROR(genericArgs,
                                    "expected 1 generic argument, saw %u",
                                    genericArgs->getNumChildren());

      return decodeMangledType(genericArgs->getChild(0));
    }
    case NodeKind::BuiltinTypeName: {
      auto mangledName = Demangle::mangleNode(Node);
      return Builder.createBuiltinType(Node->getText().str(), mangledName);
    }
    case NodeKind::Metatype:
    case NodeKind::ExistentialMetatype: {
      unsigned i = 0;
      llvm::Optional<ImplMetatypeRepresentation> repr;

      // Handle lowered metatypes in a hackish way. If the representation
      // was not thin, force the resulting typeref to have a non-empty
      // representation.
      if (Node->getNumChildren() >= 2) {
        auto reprNode = Node->getChild(i++);
        if (reprNode->getKind() != NodeKind::MetatypeRepresentation ||
            !reprNode->hasText())
          return MAKE_NODE_TYPE_ERROR0(reprNode, "wrong node kind or no text");
        if (reprNode->getText() == "@thin")
          repr = ImplMetatypeRepresentation::Thin;
        else if (reprNode->getText() == "@thick")
          repr = ImplMetatypeRepresentation::Thick;
        else if (reprNode->getText() == "@objc_metatype")
          repr = ImplMetatypeRepresentation::ObjC;
      } else if (Node->getNumChildren() < 1) {
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");
      }

      auto instance = decodeMangledType(Node->getChild(i));
      if (instance.isError())
        return instance;
      if (Node->getKind() == NodeKind::Metatype) {
        return Builder.createMetatypeType(instance.getType(), repr);
      } else if (Node->getKind() == NodeKind::ExistentialMetatype) {
        return Builder.createExistentialMetatypeType(instance.getType(), repr);
      } else {
        assert(false);
        return MAKE_NODE_TYPE_ERROR0(Node,
                                     "Metatype/ExistentialMetatype Node "
                                     "had a different kind when re-checked");
      }
    }
    case NodeKind::ProtocolList:
    case NodeKind::ProtocolListWithAnyObject:
    case NodeKind::ProtocolListWithClass: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      // Find the protocol list.
      llvm::SmallVector<BuiltProtocolDecl, 8> Protocols;
      auto TypeList = Node->getChild(0);
      if (TypeList->getKind() == NodeKind::ProtocolList &&
          TypeList->getNumChildren() >= 1) {
        TypeList = TypeList->getChild(0);
      }

      // Demangle the protocol list.
      for (auto componentType : *TypeList) {
        if (auto Protocol = decodeMangledProtocolType(componentType))
          Protocols.push_back(Protocol);
        else
          return MAKE_NODE_TYPE_ERROR0(componentType,
                                       "failed to decode protocol type");
      }

      // Superclass or AnyObject, if present.
      bool IsClassBound = false;
      auto Superclass = BuiltType();
      if (Node->getKind() == NodeKind::ProtocolListWithClass) {
        if (Node->getNumChildren() < 2)
          return MAKE_NODE_TYPE_ERROR(Node,
                                      "fewer children (%u) than required (2)",
                                      Node->getNumChildren());

        auto superclassNode = Node->getChild(1);
        auto result = decodeMangledType(superclassNode);
        if (result.isError())
          return result;
        Superclass = result.getType();

        IsClassBound = true;
      } else if (Node->getKind() == NodeKind::ProtocolListWithAnyObject) {
        IsClassBound = true;
      }

      return Builder.createProtocolCompositionType(Protocols, Superclass,
                                                   IsClassBound);
    }

    case NodeKind::Protocol:
    case NodeKind::ProtocolSymbolicReference: {
      if (auto Proto = decodeMangledProtocolType(Node)) {
        return Builder.createProtocolCompositionType(Proto, BuiltType(),
                                                     /*IsClassBound=*/false);
      }

      return MAKE_NODE_TYPE_ERROR0(Node, "failed to decode protocol type");
    }
    case NodeKind::DynamicSelf: {
      if (Node->getNumChildren() != 1)
        return MAKE_NODE_TYPE_ERROR(Node, "expected 1 child, saw %u",
                                    Node->getNumChildren());

      auto selfType = decodeMangledType(Node->getChild(0));
      if (selfType.isError())
        return selfType;

      return Builder.createDynamicSelfType(selfType.getType());
    }
    case NodeKind::DependentGenericParamType: {
      auto depth = Node->getChild(0)->getIndex();
      auto index = Node->getChild(1)->getIndex();
      return Builder.createGenericTypeParameterType(depth, index);
    }
    case NodeKind::EscapingObjCBlock:
    case NodeKind::ObjCBlock:
    case NodeKind::CFunctionPointer:
    case NodeKind::ThinFunctionType:
    case NodeKind::NoEscapeFunctionType:
    case NodeKind::AutoClosureType:
    case NodeKind::EscapingAutoClosureType:
    case NodeKind::DifferentiableFunctionType:
    case NodeKind::EscapingDifferentiableFunctionType:
    case NodeKind::LinearFunctionType:
    case NodeKind::EscapingLinearFunctionType:
    case NodeKind::FunctionType: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      FunctionTypeFlags flags;
      if (Node->getKind() == NodeKind::ObjCBlock ||
          Node->getKind() == NodeKind::EscapingObjCBlock) {
        flags = flags.withConvention(FunctionMetadataConvention::Block);
      } else if (Node->getKind() == NodeKind::CFunctionPointer) {
        flags =
          flags.withConvention(FunctionMetadataConvention::CFunctionPointer);
      } else if (Node->getKind() == NodeKind::ThinFunctionType) {
        flags = flags.withConvention(FunctionMetadataConvention::Thin);
      } else if (Node->getKind() == NodeKind::DifferentiableFunctionType ||
               Node->getKind() ==
                   NodeKind::EscapingDifferentiableFunctionType) {
        flags = flags.withDifferentiabilityKind(
            FunctionMetadataDifferentiabilityKind::Normal);
      } else if (Node->getKind() == NodeKind::LinearFunctionType ||
                 Node->getKind() == NodeKind::EscapingLinearFunctionType) {
        flags = flags.withDifferentiabilityKind(
            FunctionMetadataDifferentiabilityKind::Linear);
      }

      unsigned firstChildIdx = 0;
      if (Node->getChild(firstChildIdx)->getKind() == NodeKind::ClangType) {
        // [TODO: synthesize-Clang-type-from-mangled-name] Use the first child
        // to create a ClangTypeInfo.
        ++firstChildIdx;
      }

      bool isThrow = false;
      if (Node->getChild(firstChildIdx)->getKind()
            == NodeKind::ThrowsAnnotation) {
        isThrow = true;
        ++firstChildIdx;
      }

      bool isAsync = false;
      if (Node->getChild(firstChildIdx)->getKind()
            == NodeKind::AsyncAnnotation) {
        isAsync = true;
        ++firstChildIdx;
      }

      flags = flags.withAsync(isAsync).withThrows(isThrow);

      if (Node->getNumChildren() < firstChildIdx + 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (%u)",
                                    Node->getNumChildren(), firstChildIdx + 2);

      bool hasParamFlags = false;
      llvm::SmallVector<FunctionParam<BuiltType>, 8> parameters;
      if (!decodeMangledFunctionInputType(Node->getChild(firstChildIdx),
                                          parameters, hasParamFlags))
        return MAKE_NODE_TYPE_ERROR0(Node->getChild(firstChildIdx),
                                     "failed to decode function type");
      flags =
          flags.withNumParameters(parameters.size())
              .withParameterFlags(hasParamFlags)
              .withEscaping(
                          Node->getKind() == NodeKind::FunctionType ||
                          Node->getKind() == NodeKind::EscapingAutoClosureType ||
                          Node->getKind() == NodeKind::EscapingObjCBlock ||
                          Node->getKind() ==
                              NodeKind::EscapingDifferentiableFunctionType ||
                          Node->getKind() ==
                              NodeKind::EscapingLinearFunctionType);

      auto result = decodeMangledType(Node->getChild(firstChildIdx+1));
      if (result.isError())
        return result;
      return Builder.createFunctionType(parameters, result.getType(), flags);
    }
    case NodeKind::ImplFunctionType: {
      auto calleeConvention = ImplParameterConvention::Direct_Unowned;
      llvm::SmallVector<ImplFunctionParam<BuiltType>, 8> parameters;
      llvm::SmallVector<ImplFunctionResult<BuiltType>, 8> results;
      llvm::SmallVector<ImplFunctionResult<BuiltType>, 8> errorResults;
      ImplFunctionTypeFlags flags;

      for (unsigned i = 0; i < Node->getNumChildren(); i++) {
        auto child = Node->getChild(i);

        if (child->getKind() == NodeKind::ImplConvention) {
          if (!child->hasText())
            return MAKE_NODE_TYPE_ERROR0(child, "expected text");

          if (child->getText() == "@convention(thin)") {
            flags =
              flags.withRepresentation(ImplFunctionRepresentation::Thin);
          } else if (child->getText() == "@callee_guaranteed") {
            calleeConvention = ImplParameterConvention::Direct_Guaranteed;
          }
        } else if (child->getKind() == NodeKind::ImplFunctionConvention) {
          if (child->getNumChildren() == 0)
            return MAKE_NODE_TYPE_ERROR0(child, "expected grandchildren");
          if ((child->getFirstChild()->getKind() !=
               NodeKind::ImplFunctionConventionName) ||
              !child->getFirstChild()->hasText())
            return MAKE_NODE_TYPE_ERROR0(child, "expected convention name");

          // [TODO: synthesize-Clang-type-from-mangled-name] If there are two
          // grand-children, the second is going to be the mangled Clang type.
          StringRef text = child->getFirstChild()->getText();
          if (text == "c") {
            flags =
              flags.withRepresentation(ImplFunctionRepresentation::CFunctionPointer);
          } else if (text == "block") {
            flags =
              flags.withRepresentation(ImplFunctionRepresentation::Block);
          }
        } else if (child->getKind() == NodeKind::ImplFunctionAttribute) {
          if (!child->hasText())
            return MAKE_NODE_TYPE_ERROR0(child, "expected text");
          if (child->getText() == "@async") {
            flags = flags.withAsync();
          }
        } else if (child->getKind() == NodeKind::ImplDifferentiable) {
          flags = flags.withDifferentiabilityKind(
              ImplFunctionDifferentiabilityKind::Normal);
        } else if (child->getKind() == NodeKind::ImplLinear) {
          flags = flags.withDifferentiabilityKind(
              ImplFunctionDifferentiabilityKind::Linear);
        } else if (child->getKind() == NodeKind::ImplEscaping) {
          flags = flags.withEscaping();
        } else if (child->getKind() == NodeKind::ImplParameter) {
          if (decodeImplFunctionParam(child, parameters))
            return MAKE_NODE_TYPE_ERROR0(child,
                                         "failed to decode function parameter");
        } else if (child->getKind() == NodeKind::ImplResult) {
          if (decodeImplFunctionParam(child, results))
            return MAKE_NODE_TYPE_ERROR0(child,
                                         "failed to decode function parameter");
        } else if (child->getKind() == NodeKind::ImplErrorResult) {
          if (decodeImplFunctionPart(child, errorResults))
            return MAKE_NODE_TYPE_ERROR0(child,
                                         "failed to decode function part");
        } else {
          return MAKE_NODE_TYPE_ERROR0(child, "unexpected kind");
        }
      }

      llvm::Optional<ImplFunctionResult<BuiltType>> errorResult;
      switch (errorResults.size()) {
      case 0:
        break;
      case 1:
        errorResult = errorResults.front();
        break;
      default:
        return MAKE_NODE_TYPE_ERROR(Node, "got %zu errors",
                                    errorResults.size());
      }

      // TODO: Some cases not handled above, but *probably* they cannot
      // appear as the types of values in SIL (yet?):
      // - functions with yield returns
      // - functions with generic signatures
      // - foreign error conventions
      return Builder.createImplFunctionType(calleeConvention,
                                            parameters, results,
                                            errorResult, flags);
    }

    case NodeKind::ArgumentTuple:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      return decodeMangledType(Node->getChild(0));

    case NodeKind::ReturnType:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      return decodeMangledType(Node->getChild(0));

    case NodeKind::Tuple: {
      llvm::SmallVector<BuiltType, 8> elements;
      std::string labels;
      for (auto &element : *Node) {
        if (element->getKind() != NodeKind::TupleElement)
          return MAKE_NODE_TYPE_ERROR0(Node, "unexpected kind");

        // If the tuple element is labeled, add its label to 'labels'.
        unsigned typeChildIndex = 0;
        if (element->getChild(typeChildIndex)->getKind() == NodeKind::VariadicMarker) {
          return MAKE_NODE_TYPE_ERROR0(element->getChild(typeChildIndex),
                                       "no children");
        }
        if (element->getChild(typeChildIndex)->getKind() == NodeKind::TupleElementName) {
          // Add spaces to terminate all the previous labels if this
          // is the first we've seen.
          if (labels.empty()) labels.append(elements.size(), ' ');

          // Add the label and its terminator.
          labels += element->getChild(typeChildIndex)->getText();
          labels += ' ';
          typeChildIndex++;

        // Otherwise, add a space if a previous element had a label.
        } else if (!labels.empty()) {
          labels += ' ';
        }

        // Decode the element type.
        auto elementType = decodeMangledType(element->getChild(typeChildIndex));
        if (elementType.isError())
          return elementType;

        elements.push_back(elementType.getType());
      }
      return Builder.createTupleType(elements, std::move(labels));
    }
    case NodeKind::TupleElement:
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      if (Node->getChild(0)->getKind() == NodeKind::TupleElementName) {
        if (Node->getNumChildren() < 2)
          return MAKE_NODE_TYPE_ERROR(Node,
                                      "fewer children (%u) than required (2)",
                                      Node->getNumChildren());

        return decodeMangledType(Node->getChild(1));
      }
      return decodeMangledType(Node->getChild(0));

    case NodeKind::DependentGenericType: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      return decodeMangledType(Node->getChild(1));
    }
    case NodeKind::DependentMemberType: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;
      auto assocTypeChild = Node->getChild(1);
      auto member = assocTypeChild->getFirstChild()->getText();
      if (assocTypeChild->getNumChildren() < 2)
        return Builder.createDependentMemberType(member.str(), base.getType());

      auto protocol = decodeMangledProtocolType(assocTypeChild->getChild(1));
      if (!protocol)
        return BuiltType();
      return Builder.createDependentMemberType(member.str(), base.getType(),
                                               protocol);
    }
    case NodeKind::DependentAssociatedTypeRef: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      return decodeMangledType(Node->getChild(1));
    }
    case NodeKind::Unowned: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;
      return Builder.createUnownedStorageType(base.getType());
    }
    case NodeKind::Unmanaged: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;
      return Builder.createUnmanagedStorageType(base.getType());
    }
    case NodeKind::Weak: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;
      return Builder.createWeakStorageType(base.getType());
    }
    case NodeKind::SILBoxType: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;
      return Builder.createSILBoxType(base.getType());
    }
    case NodeKind::SILBoxTypeWithLayout: {
      // TODO: Implement SILBoxTypeRefs with layout. As a stopgap, specify the
      // NativeObject type ref.
      return Builder.createBuiltinType("Builtin.NativeObject", "Bo");
    }
    case NodeKind::SugaredOptional: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;

      return Builder.createOptionalType(base.getType());
    }
    case NodeKind::SugaredArray: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;

      return Builder.createArrayType(base.getType());
    }
    case NodeKind::SugaredDictionary: {
      if (Node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (2)",
                                    Node->getNumChildren());

      auto key = decodeMangledType(Node->getChild(0));
      if (key.isError())
        return key;

      auto value = decodeMangledType(Node->getChild(1));
      if (value.isError())
        return value;

      return Builder.createDictionaryType(key.getType(), value.getType());
    }
    case NodeKind::SugaredParen: {
      if (Node->getNumChildren() < 1)
        return MAKE_NODE_TYPE_ERROR0(Node, "no children");

      auto base = decodeMangledType(Node->getChild(0));
      if (base.isError())
        return base;

      return Builder.createParenType(base.getType());
    }
    case NodeKind::OpaqueType: {
      if (Node->getNumChildren() < 3)
        return MAKE_NODE_TYPE_ERROR(Node,
                                    "fewer children (%u) than required (3)",
                                    Node->getNumChildren());
      auto descriptor = Node->getChild(0);
      auto ordinalNode = Node->getChild(1);

      if (ordinalNode->getKind() != NodeKind::Index
          || !ordinalNode->hasIndex())
        return MAKE_NODE_TYPE_ERROR0(ordinalNode,
                                     "unexpected kind or no index");
      auto ordinal = ordinalNode->getIndex();

      std::vector<BuiltType> genericArgsBuf;
      std::vector<unsigned> genericArgsLevels;
      auto boundGenerics = Node->getChild(2);
      for (unsigned i = 0; i < boundGenerics->getNumChildren(); ++i) {
        genericArgsLevels.push_back(genericArgsBuf.size());
        auto genericsNode = boundGenerics->getChild(i);
        if (genericsNode->getKind() != NodeKind::TypeList)
          break;
        for (auto argNode : *genericsNode) {
          auto arg = decodeMangledType(argNode);
          if (arg.isError())
            return arg;
          genericArgsBuf.push_back(arg.getType());
        }
      }
      genericArgsLevels.push_back(genericArgsBuf.size());
      std::vector<llvm::ArrayRef<BuiltType>> genericArgs;
      for (unsigned i = 0; i < genericArgsLevels.size() - 1; ++i) {
        auto start = genericArgsLevels[i], end = genericArgsLevels[i+1];
        genericArgs.emplace_back(genericArgsBuf.data() + start,
                                 end - start);
      }
      
      return Builder.resolveOpaqueType(descriptor, genericArgs, ordinal);
    }
    // TODO: Handle OpaqueReturnType, when we're in the middle of reconstructing
    // the defining decl
    default:
      return MAKE_NODE_TYPE_ERROR0(Node, "unexpected kind");
    }
  }

private:
  template <typename T>
  bool decodeImplFunctionPart(Demangle::NodePointer node,
                              llvm::SmallVectorImpl<T> &results) {
    if (node->getNumChildren() != 2)
      return true;
    
    if (node->getChild(0)->getKind() != Node::Kind::ImplConvention ||
        node->getChild(1)->getKind() != Node::Kind::Type)
      return true;

    StringRef conventionString = node->getChild(0)->getText();
    llvm::Optional<typename T::ConventionType> convention =
        T::getConventionFromString(conventionString);
    if (!convention)
      return true;
    auto type = decodeMangledType(node->getChild(1));
    if (type.isError())
      return true;

    results.emplace_back(type.getType(), *convention);
    return false;
  }

  template <typename T>
  bool decodeImplFunctionParam(Demangle::NodePointer node,
                               llvm::SmallVectorImpl<T> &results) {
    // Children: `convention, differentiability?, type`
    if (node->getNumChildren() != 2 && node->getNumChildren() != 3)
      return true;

    auto *conventionNode = node->getChild(0);
    auto *typeNode = node->getLastChild();
    if (conventionNode->getKind() != Node::Kind::ImplConvention ||
        typeNode->getKind() != Node::Kind::Type)
      return true;

    StringRef conventionString = conventionNode->getText();
    auto convention = T::getConventionFromString(conventionString);
    if (!convention)
      return true;
    auto result = decodeMangledType(typeNode);
    if (result.isError())
      return true;

    auto diffKind = T::DifferentiabilityType::DifferentiableOrNotApplicable;
    if (node->getNumChildren() == 3) {
      auto diffKindNode = node->getChild(1);
      if (diffKindNode->getKind() != Node::Kind::ImplDifferentiability)
        return true;
      auto optDiffKind =
          T::getDifferentiabilityFromString(diffKindNode->getText());
      if (!optDiffKind)
        return true;
      diffKind = *optDiffKind;
    }

    results.emplace_back(result.getType(), *convention, diffKind);
    return false;
  }

  llvm::Optional<TypeLookupError>
  decodeMangledTypeDecl(Demangle::NodePointer node, BuiltTypeDecl &typeDecl,
                        BuiltType &parent, bool &typeAlias) {
    if (node->getKind() == NodeKind::Type)
      return decodeMangledTypeDecl(node->getChild(0), typeDecl,
                                   parent, typeAlias);

    Demangle::NodePointer declNode;
    if (node->getKind() == NodeKind::TypeSymbolicReference) {
      // A symbolic reference can be directly resolved to a nominal type.
      declNode = node;
    } else {
      if (node->getNumChildren() < 2)
        return MAKE_NODE_TYPE_ERROR(
            node, "Number of node children (%u) less than required (2)",
            node->getNumChildren());

      auto parentContext = node->getChild(0);

      // Nested types are handled a bit funny here because a
      // nominal typeref always stores its full mangled name,
      // in addition to a reference to the parent type. The
      // mangled name already includes the module and parent
      // types, if any.
      declNode = node;
      switch (parentContext->getKind()) {
      case Node::Kind::Module:
        break;
      case Node::Kind::Extension:
        // Decode the type being extended.
        if (parentContext->getNumChildren() < 2)
          return MAKE_NODE_TYPE_ERROR(parentContext,
                                      "Number of parentContext children (%u) "
                                      "less than required (2)",
                                      node->getNumChildren());
        parentContext = parentContext->getChild(1);
        LLVM_FALLTHROUGH;
      default:
        parent = decodeMangledType(parentContext).getType();
        // Remove any generic arguments from the context node, producing a
        // node that references the nominal type declaration.
        declNode = Demangle::getUnspecialized(node, Builder.getNodeFactory());
        break;
      }
    }
    typeDecl = Builder.createTypeDecl(declNode, typeAlias);
    if (!typeDecl)
      return TypeLookupError("Failed to create type decl");

    return llvm::None;
  }

  BuiltProtocolDecl decodeMangledProtocolType(Demangle::NodePointer node) {
    if (node->getKind() == NodeKind::Type)
      return decodeMangledProtocolType(node->getChild(0));

    if ((node->getNumChildren() < 2 || node->getKind() != NodeKind::Protocol)
        && node->getKind() != NodeKind::ProtocolSymbolicReference)
      return BuiltProtocolDecl();

#if SWIFT_OBJC_INTEROP
    if (auto objcProtocolName = getObjCClassOrProtocolName(node))
      return Builder.createObjCProtocolDecl(objcProtocolName->str());
#endif

    return Builder.createProtocolDecl(node);
  }

  bool decodeMangledFunctionInputType(
      Demangle::NodePointer node,
      llvm::SmallVectorImpl<FunctionParam<BuiltType>> &params,
      bool &hasParamFlags) {
    // Look through a couple of sugar nodes.
    if (node->getKind() == NodeKind::Type ||
        node->getKind() == NodeKind::ArgumentTuple) {
      return decodeMangledFunctionInputType(node->getFirstChild(), params,
                                            hasParamFlags);
    }

    auto decodeParamTypeAndFlags =
        [&](Demangle::NodePointer typeNode,
            FunctionParam<BuiltType> &param) -> bool {
      Demangle::NodePointer node = typeNode;

      auto setOwnership = [&](ValueOwnership ownership) {
        param.setValueOwnership(ownership);
        node = node->getFirstChild();
        hasParamFlags = true;
      };
      switch (node->getKind()) {
      case NodeKind::InOut:
        setOwnership(ValueOwnership::InOut);
        break;

      case NodeKind::Shared:
        setOwnership(ValueOwnership::Shared);
        break;

      case NodeKind::Owned:
        setOwnership(ValueOwnership::Owned);
        break;

      case NodeKind::AutoClosureType:
      case NodeKind::EscapingAutoClosureType: {
        param.setAutoClosure();
        hasParamFlags = true;
        break;
      }

      default:
        break;
      }

      auto paramType = decodeMangledType(node);
      if (paramType.isError())
        return false;

      param.setType(paramType.getType());
      return true;
    };

    auto decodeParam =
        [&](NodePointer paramNode) -> llvm::Optional<FunctionParam<BuiltType>> {
      if (paramNode->getKind() != NodeKind::TupleElement)
        return None;

      FunctionParam<BuiltType> param;
      for (const auto &child : *paramNode) {
        switch (child->getKind()) {
        case NodeKind::TupleElementName:
          param.setLabel(child->getText());
          break;

        case NodeKind::VariadicMarker:
          param.setVariadic();
          hasParamFlags = true;
          break;

        case NodeKind::Type:
          if (!decodeParamTypeAndFlags(child->getFirstChild(), param))
            return None;
          break;

        default:
          return None;
        }
      }

      return param;
    };

    // Expand a single level of tuple.
    if (node->getKind() == NodeKind::Tuple) {
      // Decode all the elements as separate arguments.
      for (const auto &elt : *node) {
        auto param = decodeParam(elt);
        if (!param)
          return false;

        params.push_back(std::move(*param));
      }

      return true;
    }

    // Otherwise, handle the type as a single argument.
    FunctionParam<BuiltType> param;
    if (!decodeParamTypeAndFlags(node, param))
      return false;

    params.push_back(std::move(param));
    return true;
  }
};

template <typename BuilderType>
inline TypeLookupErrorOr<typename BuilderType::BuiltType>
decodeMangledType(BuilderType &Builder, NodePointer Node) {
  return TypeDecoder<BuilderType>(Builder).decodeMangledType(Node);
}

SWIFT_END_INLINE_NAMESPACE
} // end namespace Demangle
} // end namespace swift

#endif // SWIFT_DEMANGLING_TYPEDECODER_H