src/torque/instance-type-generator.cc

// Copyright 2019 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/torque/implementation-visitor.h"

namespace v8 {
namespace internal {
namespace torque {

namespace {

// Contains all necessary state for a single class type during the process of
// assigning instance types, and provides a convenient way to access the list of
// types that inherit from this one.
struct InstanceTypeTree {
  explicit InstanceTypeTree(const ClassType* type)
      : type(type),
        start(INT_MAX),
        end(INT_MIN),
        value(-1),
        num_values(0),
        num_own_values(0) {}
  const ClassType* type;
  std::vector<std::unique_ptr<InstanceTypeTree>> children;
  int start;  // Start of range for this and subclasses, or INT_MAX.
  int end;    // End of range for this and subclasses, or INT_MIN.
  int value;  // Assigned value for this class itself, or -1 when unassigned.
  int num_values;      // Number of values assigned for this and subclasses.
  int num_own_values;  // How many values this needs (not including subclasses).
};

// Assembles all class types into a tree, but doesn't yet attempt to assign
// instance types for them.
std::unique_ptr<InstanceTypeTree> BuildInstanceTypeTree() {
  // First, build InstanceTypeTree instances for every class but don't try to
  // attach them to their subclasses yet.
  std::unordered_map<const ClassType*, InstanceTypeTree*> map_by_type;
  std::vector<std::unique_ptr<InstanceTypeTree>> unparented_types;
  for (auto& p : GlobalContext::AllDeclarables()) {
    if (const TypeAlias* alias = TypeAlias::DynamicCast(p.get())) {
      const Type* type = alias->type();
      const ClassType* class_type = ClassType::DynamicCast(type);
      if (class_type == nullptr) {
        continue;
      }
      auto& map_slot = map_by_type[class_type];
      if (map_slot != nullptr) {
        continue;  // We already encountered this type.
      }
      std::unique_ptr<InstanceTypeTree> type_tree =
          std::make_unique<InstanceTypeTree>(class_type);
      map_slot = type_tree.get();
      unparented_types.push_back(std::move(type_tree));
    }
  }

  // Second, assemble them all into a tree following the inheritance hierarchy.
  std::unique_ptr<InstanceTypeTree> root;
  for (auto& type_tree : unparented_types) {
    const ClassType* parent = type_tree->type->GetSuperClass();
    if (parent == nullptr) {
      if (root != nullptr)
        Error("Expected only one root class type. Found: ", root->type->name(),
              " and ", type_tree->type->name())
            .Position(type_tree->type->GetPosition());
      root = std::move(type_tree);
    } else {
      map_by_type[parent]->children.push_back(std::move(type_tree));
    }
  }
  return root;
}

// Propagates constraints about instance types from children to their parents.
void PropagateInstanceTypeConstraints(InstanceTypeTree* root) {
  for (auto& child : root->children) {
    PropagateInstanceTypeConstraints(child.get());
    if (child->start < root->start) root->start = child->start;
    if (child->end > root->end) root->end = child->end;
    root->num_values += child->num_values;
  }
  const InstanceTypeConstraints& constraints =
      root->type->GetInstanceTypeConstraints();
  if (!root->type->IsAbstract() && !root->type->HasSameInstanceTypeAsParent()) {
    root->num_own_values = 1;
  }
  root->num_values += root->num_own_values;
  if (constraints.num_flags_bits != -1) {
    // Children won't get any types assigned; must be done manually in C++.
    root->children.clear();
    root->num_values = 1 << constraints.num_flags_bits;
    root->num_own_values = root->num_values;
    root->start = 0;
    root->end = root->num_values - 1;
  }
  if (constraints.value != -1) {
    if (root->num_own_values != 1) {
      Error("Instance type value requested for abstract class ",
            root->type->name())
          .Position(root->type->GetPosition());
    }
    root->value = constraints.value;
    if (constraints.value < root->start) root->start = constraints.value;
    if (constraints.value > root->end) root->end = constraints.value;
  }
}

// Assigns values for the type itself, not including any children. Returns the
// next available value.
int SelectOwnValues(InstanceTypeTree* root, int start_value) {
  if (root->value == -1) {
    root->value = start_value;
  } else if (root->value < start_value) {
    Error("Failed to assign instance type ", root->value, " to ",
          root->type->name())
        .Position(root->type->GetPosition());
  }
  return root->value + root->num_own_values;
}

// Sorting function for types that don't have specific values they must include.
// Prioritizes bigger type ranges (those with more subtypes) first, and
// then sorts alphabetically within each size category.
struct CompareUnconstrainedTypes {
  constexpr bool operator()(const InstanceTypeTree* a,
                            const InstanceTypeTree* b) const {
    return (a->num_values > b->num_values)
               ? true
               : (a->num_values < b->num_values)
                     ? false
                     : std::less<std::string>()(a->type->name(),
                                                b->type->name());
  }
};

// Assigns concrete values for every instance type range, and sorts the children
// at each layer of the tree into increasing order. Appends the newly-assigned
// tree to the destination vector. Returns the first unassigned value after
// those that have been used.
int SolveInstanceTypeConstraints(
    std::unique_ptr<InstanceTypeTree> root, int start_value,
    std::vector<std::unique_ptr<InstanceTypeTree>>* destination) {
  if (root->start < start_value) {
    Error("Failed to assign instance type ", root->start, " to ",
          root->type->name())
        .Position(root->type->GetPosition());
  }

  // First, separate the children into four groups:
  // - The one child that must go first, if it exists;
  // - Children with specific value requirements ("constrained");
  // - Children without specific value requirements ("unconstrained");
  // - The one child that must go last, if it exists.
  std::unique_ptr<InstanceTypeTree> lowest_child;
  std::unique_ptr<InstanceTypeTree> highest_child;
  std::multimap<int, std::unique_ptr<InstanceTypeTree>>
      constrained_children_by_start;
  // Using std::map because you can't std::move out of a std::set until C++17.
  std::map<InstanceTypeTree*, std::unique_ptr<InstanceTypeTree>,
           CompareUnconstrainedTypes>
      unconstrained_children_by_size;
  for (auto& child : root->children) {
    if (child->type->IsHighestInstanceTypeWithinParent()) {
      if (highest_child) {
        Error("Two classes requested to be the highest instance type: ",
              highest_child->type->name(), " and ", child->type->name(),
              " within range for parent class ", root->type->name())
            .Position(child->type->GetPosition());
      }
      if (child->type->IsLowestInstanceTypeWithinParent()) {
        Error(
            "Class requested to be both highest and lowest instance type "
            "within its parent range: ",
            child->type->name())
            .Position(child->type->GetPosition());
      }
      highest_child = std::move(child);
    } else if (child->type->IsLowestInstanceTypeWithinParent()) {
      if (lowest_child) {
        Error("Two classes requested to be the lowest instance type: ",
              lowest_child->type->name(), " and ", child->type->name(),
              " within range for parent class ", root->type->name())
            .Position(child->type->GetPosition());
      }
      lowest_child = std::move(child);
    } else if (child->start > child->end) {
      unconstrained_children_by_size.insert(
          std::make_pair(child.get(), std::move(child)));
    } else {
      constrained_children_by_start.insert(
          std::make_pair(child->start, std::move(child)));
    }
  }
  root->children.clear();

  bool own_type_pending = root->num_own_values > 0;

  // Second, iterate and place the children in ascending order.
  if (lowest_child != nullptr) {
    start_value = SolveInstanceTypeConstraints(std::move(lowest_child),
                                               start_value, &root->children);
  }
  for (auto& constrained_child_pair : constrained_children_by_start) {
    // Select the next constrained child type in ascending order.
    std::unique_ptr<InstanceTypeTree> constrained_child =
        std::move(constrained_child_pair.second);

    // Try to place the root type before the constrained child type if it fits.
    if (own_type_pending) {
      if ((root->value != -1 && root->value < constrained_child->start) ||
          (root->value == -1 &&
           start_value + root->num_own_values <= constrained_child->start)) {
        start_value = SelectOwnValues(root.get(), start_value);
        own_type_pending = false;
      }
    }

    // Try to find any unconstrained children that fit before the constrained
    // one. This simple greedy algorithm just puts the biggest unconstrained
    // children in first, which might not fill the space as efficiently as
    // possible but is good enough for our needs.
    for (auto it = unconstrained_children_by_size.begin();
         it != unconstrained_children_by_size.end();) {
      if (it->second->num_values + start_value <= constrained_child->start) {
        start_value = SolveInstanceTypeConstraints(
            std::move(it->second), start_value, &root->children);
        it = unconstrained_children_by_size.erase(it);
      } else {
        ++it;
      }
    }

    // Place the constrained child type.
    start_value = SolveInstanceTypeConstraints(std::move(constrained_child),
                                               start_value, &root->children);
  }
  if (own_type_pending) {
    start_value = SelectOwnValues(root.get(), start_value);
    own_type_pending = false;
  }
  for (auto& child_pair : unconstrained_children_by_size) {
    start_value = SolveInstanceTypeConstraints(std::move(child_pair.second),
                                               start_value, &root->children);
  }
  if (highest_child != nullptr) {
    start_value = SolveInstanceTypeConstraints(std::move(highest_child),
                                               start_value, &root->children);
  }

  // Finally, set the range for this class to include all placed subclasses.
  root->end = start_value - 1;
  root->start =
      root->children.empty() ? start_value : root->children.front()->start;
  if (root->value != -1 && root->value < root->start) {
    root->start = root->value;
  }
  root->num_values = root->end - root->start + 1;
  root->type->InitializeInstanceTypes(
      root->value == -1 ? base::Optional<int>{} : root->value,
      std::make_pair(root->start, root->end));

  if (root->num_values > 0) {
    destination->push_back(std::move(root));
  }
  return start_value;
}

std::unique_ptr<InstanceTypeTree> SolveInstanceTypeConstraints(
    std::unique_ptr<InstanceTypeTree> root) {
  std::vector<std::unique_ptr<InstanceTypeTree>> destination;
  SolveInstanceTypeConstraints(std::move(root), 0, &destination);
  return destination.empty() ? nullptr : std::move(destination.front());
}

std::unique_ptr<InstanceTypeTree> AssignInstanceTypes() {
  std::unique_ptr<InstanceTypeTree> root = BuildInstanceTypeTree();
  if (root != nullptr) {
    PropagateInstanceTypeConstraints(root.get());
    root = SolveInstanceTypeConstraints(std::move(root));
  }
  return root;
}

// Prints items in macro lists for the given type and its descendants.
// - definitions: This list is pairs of instance type name and assigned value,
//   such as V(ODDBALL_TYPE, 67). It includes FIRST_* and LAST_* items for each
//   type that has more than one associated InstanceType. Items within those
//   ranges are indented for readability.
// - values: This list is just instance type names, like V(ODDBALL_TYPE). It
//   does not include any FIRST_* and LAST_* range markers.
// - fully_defined_single_instance_types: This list is pairs of class name and
//   instance type, for classes which have defined layouts and a single
//   corresponding instance type.
// - fully_defined_multiple_instance_types: This list is pairs of class name and
//   instance type, for classes which have defined layouts and subclasses.
// - only_declared_single_instance_types: This list is pairs of class name and
//   instance type, for classes which have a single corresponding instance type
//   and do not have layout definitions in Torque.
// - fully_defined_range_instance_types: This list is triples of class name,
//   first instance type, and last instance type, for classes which have defined
//   layouts and multiple corresponding instance types.
// - only_declared_range_instance_types: This list is triples of class name,
//   first instance type, and last instance type, for classes which have
//   multiple corresponding instance types and do not have layout definitions in
//   Torque.
void PrintInstanceTypes(InstanceTypeTree* root, std::ostream& definitions,
                        std::ostream& values,
                        std::ostream& fully_defined_single_instance_types,
                        std::ostream& fully_defined_multiple_instance_types,
                        std::ostream& only_declared_single_instance_types,
                        std::ostream& fully_defined_range_instance_types,
                        std::ostream& only_declared_range_instance_types,
                        const std::string& indent) {
  std::string type_name =
      CapifyStringWithUnderscores(root->type->name()) + "_TYPE";
  std::string inner_indent = indent;

  if (root->num_values > 1) {
    definitions << indent << "V(FIRST_" << type_name << ", " << root->start
                << ") \\\n";
    inner_indent += "  ";
  }
  if (root->num_own_values == 1) {
    definitions << inner_indent << "V(" << type_name << ", " << root->value
                << ") \\\n";
    values << "  V(" << type_name << ") \\\n";
    if (root->num_values == 1) {
      std::ostream& single_instance_types =
          root->type->HasUndefinedLayout()
              ? only_declared_single_instance_types
              : fully_defined_single_instance_types;
      single_instance_types << "  V(" << root->type->name() << ", " << type_name
                            << ") \\\n";
    }
  }
  for (auto& child : root->children) {
    PrintInstanceTypes(
        child.get(), definitions, values, fully_defined_single_instance_types,
        fully_defined_multiple_instance_types,
        only_declared_single_instance_types, fully_defined_range_instance_types,
        only_declared_range_instance_types, inner_indent);
  }
  if (root->num_values > 1) {
    // We can't emit LAST_STRING_TYPE because it's not a valid flags
    // combination. So if the class type has multiple own values, which only
    // happens when using ANNOTATION_RESERVE_BITS_IN_INSTANCE_TYPE, then omit
    // the end marker.
    if (root->num_own_values <= 1) {
      definitions << indent << "V(LAST_" << type_name << ", " << root->end
                  << ") \\\n";
    }

    // Only output the instance type range for things other than the root type.
    if (root->type->GetSuperClass() != nullptr) {
      std::ostream& range_instance_types =
          root->type->HasUndefinedLayout() ? only_declared_range_instance_types
                                           : fully_defined_range_instance_types;
      range_instance_types << "  V(" << root->type->name() << ", FIRST_"
                           << type_name << ", LAST_" << type_name << ") \\\n";
      if (!root->type->IsExtern() && !root->type->IsAbstract() &&
          !root->type->HasUndefinedLayout()) {
        fully_defined_multiple_instance_types << "  V(" << root->type->name()
                                              << ", " << type_name << ") \\\n";
      }
    }
  }
}

}  // namespace

void ImplementationVisitor::GenerateInstanceTypes(
    const std::string& output_directory) {
  std::stringstream header;
  std::string file_name = "instance-types-tq.h";
  {
    IncludeGuardScope guard(header, file_name);

    header << "// Instance types for all classes except for those that use "
              "InstanceType as flags.\n";
    header << "#define TORQUE_ASSIGNED_INSTANCE_TYPES(V) \\\n";
    std::unique_ptr<InstanceTypeTree> instance_types = AssignInstanceTypes();
    std::stringstream values_list;
    std::stringstream fully_defined_single_instance_types;
    std::stringstream fully_defined_multiple_instance_types;
    std::stringstream only_declared_single_instance_types;
    std::stringstream fully_defined_range_instance_types;
    std::stringstream only_declared_range_instance_types;
    if (instance_types != nullptr) {
      PrintInstanceTypes(instance_types.get(), header, values_list,
                         fully_defined_single_instance_types,
                         fully_defined_multiple_instance_types,
                         only_declared_single_instance_types,
                         fully_defined_range_instance_types,
                         only_declared_range_instance_types, "  ");
    }
    header << "\n";

    header << "// Instance types for all classes except for those that use\n";
    header << "// InstanceType as flags.\n";
    header << "#define TORQUE_ASSIGNED_INSTANCE_TYPE_LIST(V) \\\n";
    header << values_list.str();
    header << "\n";

    header << "// Pairs of (ClassName, INSTANCE_TYPE) for classes that have\n";
    header << "// full Torque definitions.\n";
    header << "#define TORQUE_INSTANCE_CHECKERS_SINGLE_FULLY_DEFINED(V) \\\n";
    header << fully_defined_single_instance_types.str();
    header << "\n";

    header << "// Pairs of (ClassName, INSTANCE_TYPE) for classes that have\n";
    header << "// full Torque definitions and subclasses.\n";
    header << "#define TORQUE_INSTANCE_CHECKERS_MULTIPLE_FULLY_DEFINED(V) \\\n";
    header << fully_defined_multiple_instance_types.str();
    header << "\n";

    header << "// Pairs of (ClassName, INSTANCE_TYPE) for classes that are\n";
    header << "// declared but not defined in Torque. These classes may\n";
    header << "// correspond with actual C++ classes, but they are not\n";
    header << "// guaranteed to.\n";
    header << "#define TORQUE_INSTANCE_CHECKERS_SINGLE_ONLY_DECLARED(V) \\\n";
    header << only_declared_single_instance_types.str();
    header << "\n";

    header << "// Triples of (ClassName, FIRST_TYPE, LAST_TYPE) for classes\n";
    header << "// that have full Torque definitions.\n";
    header << "#define TORQUE_INSTANCE_CHECKERS_RANGE_FULLY_DEFINED(V) \\\n";
    header << fully_defined_range_instance_types.str();
    header << "\n";

    header << "// Triples of (ClassName, FIRST_TYPE, LAST_TYPE) for classes\n";
    header << "// that are declared but not defined in Torque. These classes\n";
    header << "// may correspond with actual C++ classes, but they are not\n";
    header << "// guaranteed to.\n";
    header << "#define TORQUE_INSTANCE_CHECKERS_RANGE_ONLY_DECLARED(V) \\\n";
    header << only_declared_range_instance_types.str();
    header << "\n";

    std::stringstream torque_defined_class_list;
    std::stringstream torque_defined_varsize_instance_type_list;
    std::stringstream torque_defined_fixed_instance_type_list;
    std::stringstream torque_defined_map_csa_list;
    std::stringstream torque_defined_map_root_list;

    for (const ClassType* type : TypeOracle::GetClasses()) {
      std::string upper_case_name = type->name();
      std::string lower_case_name = SnakeifyString(type->name());
      std::string instance_type_name =
          CapifyStringWithUnderscores(type->name()) + "_TYPE";

      if (type->IsExtern()) continue;
      torque_defined_class_list << "  V(" << upper_case_name << ") \\\n";

      if (type->IsAbstract()) continue;
      torque_defined_map_csa_list << "  V(_, " << upper_case_name << "Map, "
                                  << lower_case_name << "_map, "
                                  << upper_case_name << ") \\\n";
      torque_defined_map_root_list << "  V(Map, " << lower_case_name << "_map, "
                                   << upper_case_name << "Map) \\\n";
      std::stringstream& list = type->HasStaticSize()
                                    ? torque_defined_fixed_instance_type_list
                                    : torque_defined_varsize_instance_type_list;
      list << "  V(" << instance_type_name << ", " << upper_case_name << ", "
           << lower_case_name << ") \\\n";
    }

    header << "// Fully Torque-defined classes (both internal and exported).\n";
    header << "#define TORQUE_DEFINED_CLASS_LIST(V) \\\n";
    header << torque_defined_class_list.str();
    header << "\n";
    header << "#define TORQUE_DEFINED_VARSIZE_INSTANCE_TYPE_LIST(V) \\\n";
    header << torque_defined_varsize_instance_type_list.str();
    header << "\n";
    header << "#define TORQUE_DEFINED_FIXED_INSTANCE_TYPE_LIST(V) \\\n";
    header << torque_defined_fixed_instance_type_list.str();
    header << "\n";
    header << "#define TORQUE_DEFINED_INSTANCE_TYPE_LIST(V) \\\n";
    header << "  TORQUE_DEFINED_VARSIZE_INSTANCE_TYPE_LIST(V) \\\n";
    header << "  TORQUE_DEFINED_FIXED_INSTANCE_TYPE_LIST(V) \\\n";
    header << "\n";
    header << "#define TORQUE_DEFINED_MAP_CSA_LIST_GENERATOR(V, _) \\\n";
    header << torque_defined_map_csa_list.str();
    header << "\n";
    header << "#define TORQUE_DEFINED_MAP_ROOT_LIST(V) \\\n";
    header << torque_defined_map_root_list.str();
    header << "\n";
  }
  std::string output_header_path = output_directory + "/" + file_name;
  WriteFile(output_header_path, header.str());

  GlobalContext::SetInstanceTypesInitialized();
}

}  // namespace torque
}  // namespace internal
}  // namespace v8