blob: 405c45bff5a1d14b37ace85a3253866c2793b5e4 [file] [log] [blame]
//===--- ConstraintGraph.h - Constraint Graph -------------------*- C++ -*-===//
// This source file is part of the 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 for license information
// See for the list of Swift project authors
// This file defines the \c ConstraintGraph class, which describes the
// relationships among the type variables within a constraint system.
#include "swift/Basic/Debug.h"
#include "swift/Basic/LLVM.h"
#include "swift/AST/Identifier.h"
#include "swift/AST/Type.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Support/Compiler.h"
#include <functional>
#include <utility>
namespace swift {
class Type;
class TypeBase;
class TypeVariableType;
namespace constraints {
class Constraint;
class ConstraintGraph;
class ConstraintGraphScope;
class ConstraintSystem;
/// A single node in the constraint graph, which represents a type variable.
class ConstraintGraphNode {
explicit ConstraintGraphNode(TypeVariableType *typeVar) : TypeVar(typeVar) { }
ConstraintGraphNode(const ConstraintGraphNode&) = delete;
ConstraintGraphNode &operator=(const ConstraintGraphNode&) = delete;
/// Retrieve the type variable this node represents.
TypeVariableType *getTypeVariable() const { return TypeVar; }
/// Retrieve the set of constraints that mention this type variable.
/// These are the hyperedges of the graph, connecting this node to
/// various other nodes.
ArrayRef<Constraint *> getConstraints() const { return Constraints; }
/// Retrieve the set of type variables that are adjacent due to fixed
/// bindings.
ArrayRef<TypeVariableType *> getFixedBindings() const {
return FixedBindings;
/// Retrieve all of the type variables in the same equivalence class
/// as this type variable.
ArrayRef<TypeVariableType *> getEquivalenceClass() const;
/// Retrieve all of the type variables in the same equivalence class
/// as this type variable.
ArrayRef<TypeVariableType *> getEquivalenceClassUnsafe() const;
/// Add a constraint to the list of constraints.
void addConstraint(Constraint *constraint);
/// Remove a constraint from the list of constraints.
/// Note that this only removes the constraint itself; it does not
/// remove the corresponding adjacencies.
void removeConstraint(Constraint *constraint);
/// Add the given type variables to this node's equivalence class.
void addToEquivalenceClass(ArrayRef<TypeVariableType *> typeVars);
/// Add a type variable related to this type variable through fixed
/// bindings.
void addFixedBinding(TypeVariableType *typeVar);
/// Remove a type variable from the fixed-binding relationship.
void removeFixedBinding(TypeVariableType *typeVar);
/// The type variable this node represents.
TypeVariableType *TypeVar;
/// The vector of constraints that mention this type variable, in a stable
/// order for iteration.
SmallVector<Constraint *, 2> Constraints;
/// A mapping from the set of constraints that mention this type variable
/// to the index within the vector of constraints.
llvm::SmallDenseMap<Constraint *, unsigned, 2> ConstraintIndex;
/// The set of type variables that occur within the fixed binding of
/// this type variable.
SmallVector<TypeVariableType *, 2> FixedBindings;
/// All of the type variables in the same equivalence class as this
/// representative type variable.
/// Note that this field is only valid for type variables that
/// are representatives of their equivalence classes.
mutable SmallVector<TypeVariableType *, 2> EquivalenceClass;
/// Print this graph node.
void print(llvm::raw_ostream &out, unsigned indent,
PrintOptions PO = PrintOptions()) const;
/// Verify the invariants of this node within the given constraint graph.
void verify(ConstraintGraph &cg);
friend class ConstraintGraph;
/// A graph that describes the relationships among the various type variables
/// and constraints within a constraint system.
/// The constraint graph is a hypergraph where the nodes are type variables and
/// the edges are constraints. Any given constraint connects a type variable to
/// zero or more other type variables. Because these adjacencies are as
/// important as the edges themselves and are expensive to calculate from the
/// constraints, each node in the graph tracks both its edges (constraints) and
/// its adjacencies (the type variables) separately.
class ConstraintGraph {
/// Constraint a constraint graph for the given constraint system.
ConstraintGraph(ConstraintSystem &cs);
/// Destroy the given constraint graph.
ConstraintGraph(const ConstraintGraph &) = delete;
ConstraintGraph &operator=(const ConstraintGraph &) = delete;
/// Retrieve the constraint system this graph describes.
ConstraintSystem &getConstraintSystem() const { return CS; }
/// Access the node corresponding to the given type variable.
ConstraintGraphNode &operator[](TypeVariableType *typeVar) {
return lookupNode(typeVar).first;
/// Retrieve the node and index corresponding to the given type variable.
std::pair<ConstraintGraphNode &, unsigned>
lookupNode(TypeVariableType *typeVar);
/// Add a new constraint to the graph.
void addConstraint(Constraint *constraint);
/// Remove a constraint from the graph.
void removeConstraint(Constraint *constraint);
/// Merge the two nodes for the two given type variables.
/// The type variables must actually have been merged already; this
/// operation merges the two nodes.
void mergeNodes(TypeVariableType *typeVar1, TypeVariableType *typeVar2);
/// Bind the given type variable to the given fixed type.
void bindTypeVariable(TypeVariableType *typeVar, Type fixedType);
/// Describes which constraints \c gatherConstraints should gather.
enum class GatheringKind {
/// Gather constraints associated with all of the variables within the
/// same equivalence class as the given type variable, as well as its
/// immediate fixed bindings.
/// Gather all constraints that mention this type variable or type variables
/// that it is a fixed binding of. Unlike EquivalenceClass, this looks
/// through transitive fixed bindings. This can be used to find all the
/// constraints that may be affected when binding a type variable.
/// Gather the set of constraints that involve the given type variable,
/// i.e., those constraints that will be affected when the type variable
/// gets merged or bound to a fixed type.
llvm::TinyPtrVector<Constraint *>
gatherConstraints(TypeVariableType *typeVar,
GatheringKind kind,
llvm::function_ref<bool(Constraint *)> acceptConstraint =
[](Constraint *constraint) { return true; });
/// Retrieve the type variables that correspond to nodes in the graph.
/// The subscript operator can be used to retrieve the nodes that
/// correspond to these type variables.
ArrayRef<TypeVariableType *> getTypeVariables() const {
return TypeVariables;
/// Describes a single component, as produced by the connected components
/// algorithm.
struct Component {
/// The type variables in this component.
TinyPtrVector<TypeVariableType *> typeVars;
/// The original index of this component in the list of components,
/// used to provide the index of where the partial solutions will occur.
/// FIXME: This is needed due to some ordering dependencies in the
/// merging of partial solutions, which appears to also be related
/// DisjunctionStep::pruneOverloads() short-circuiting. It should be
/// removed.
unsigned solutionIndex;
/// The number of disjunctions in this component.
unsigned numDisjunctions = 0;
/// The constraints in this component.
TinyPtrVector<Constraint *> constraints;
/// The set of components that this component depends on, such that
/// the partial solutions of the those components need to be available
/// before this component can be solved.
SmallVector<unsigned, 2> dependencies;
Component(unsigned solutionIndex) : solutionIndex(solutionIndex) { }
/// Whether this component represents an orphaned constraint.
bool isOrphaned() const {
return typeVars.empty();
/// Add a constraint.
void addConstraint(Constraint *constraint);
const TinyPtrVector<Constraint *> &getConstraints() const {
return constraints;
/// Records a component which this component depends on.
void recordDependency(const Component &component);
ArrayRef<unsigned> getDependencies() const { return dependencies; }
unsigned getNumDisjunctions() const { return numDisjunctions; }
/// Compute the connected components of the graph.
/// \param typeVars The type variables that should be included in the
/// set of connected components that are returned.
/// \returns the connected components of the graph, where each component
/// contains the type variables and constraints specific to that component.
SmallVector<Component, 1> computeConnectedComponents(
ArrayRef<TypeVariableType *> typeVars);
/// Retrieve the set of "orphaned" constraints, which are known to the
/// constraint graph but have no type variables to anchor them.
ArrayRef<Constraint *> getOrphanedConstraints() const {
return OrphanedConstraints;
/// Replace the orphaned constraints with the constraints in the given list,
/// returning the old set of orphaned constraints.
SmallVector<Constraint *, 4> takeOrphanedConstraints() {
auto result = std::move(OrphanedConstraints);
return result;
/// Set the orphaned constraints.
void setOrphanedConstraints(SmallVector<Constraint *, 4> &&newConstraints) {
OrphanedConstraints = std::move(newConstraints);
/// Set the list of orphaned constraints to a single constraint.
/// If \c orphaned is null, just clear out the list.
void setOrphanedConstraint(Constraint *orphaned) {
if (orphaned)
/// Print the graph.
void print(ArrayRef<TypeVariableType *> typeVars, llvm::raw_ostream &out);
void dump(llvm::raw_ostream &out);
// FIXME: Potentially side-effectful.
SWIFT_DEBUG_HELPER(void dump());
/// Print the connected components of the graph.
void printConnectedComponents(ArrayRef<TypeVariableType *> typeVars,
llvm::raw_ostream &out);
// FIXME: Potentially side-effectful.
SWIFT_DEBUG_HELPER(void dumpConnectedComponents());
/// Verify the invariants of the graph.
void verify();
/// Optimize the constraint graph by eliminating simple transitive
/// connections between nodes.
void optimize();
/// Remove the node corresponding to the given type variable.
/// This operation assumes that the any constraints that refer to
/// this type variable have been or will be removed before other
/// graph queries are performed.
/// Note that this change is not recorded and cannot be undone. Use with
/// caution.
void removeNode(TypeVariableType *typeVar);
/// Unbind the given type variable from the given fixed type.
/// Note that this change is not recorded and cannot be undone. Use with
/// caution.
void unbindTypeVariable(TypeVariableType *typeVar, Type fixedType);
/// Perform edge contraction on the constraint graph, merging equivalence
/// classes until a fixed point is reached.
bool contractEdges();
/// The constraint system.
ConstraintSystem &CS;
/// The type variables in this graph, in stable order.
std::vector<TypeVariableType *> TypeVariables;
/// Constraints that are "orphaned" because they contain no type variables.
SmallVector<Constraint *, 4> OrphanedConstraints;
/// Increment the number of constraints considered per attempt
/// to contract constrant graph edges.
void incrementConstraintsPerContractionCounter();
/// The kind of change made to the graph.
enum class ChangeKind {
/// Added a type variable.
/// Added a new constraint.
/// Removed an existing constraint
/// Extended the equivalence class of a type variable.
/// Added a fixed binding for a type variable.
/// A change made to the constraint graph.
/// Each change can be undone (once, and in reverse order) by calling the
/// undo() method.
class Change {
/// The kind of change.
ChangeKind Kind;
union {
TypeVariableType *TypeVar;
Constraint *TheConstraint;
struct {
/// The type variable whose equivalence class was extended.
TypeVariableType *TypeVar;
/// The previous size of the equivalence class.
unsigned PrevSize;
} EquivClass;
struct {
/// The type variable being bound to a fixed type.
TypeVariableType *TypeVar;
/// The fixed type to which the type variable was bound.
TypeBase *FixedType;
} Binding;
Change() : Kind(ChangeKind::AddedTypeVariable), TypeVar(nullptr) { }
/// Create a change that added a type variable.
static Change addedTypeVariable(TypeVariableType *typeVar);
/// Create a change that added a constraint.
static Change addedConstraint(Constraint *constraint);
/// Create a change that removed a constraint.
static Change removedConstraint(Constraint *constraint);
/// Create a change that extended an equivalence class.
static Change extendedEquivalenceClass(TypeVariableType *typeVar,
unsigned prevSize);
/// Create a change that bound a type variable to a fixed type.
static Change boundTypeVariable(TypeVariableType *typeVar, Type fixed);
/// Undo this change, reverting the constraint graph to the state it
/// had prior to this change.
/// Changes must be undone in stack order.
void undo(ConstraintGraph &cg);
/// The currently active scope, or null if we aren't tracking changes made
/// to the constraint graph.
ConstraintGraphScope *ActiveScope = nullptr;
/// The set of changes made to this constraint graph.
/// As the constraint graph is extended and mutated, additional changes are
/// introduced into this vector. Each scope
llvm::SmallVector<Change, 4> Changes;
friend class ConstraintGraphScope;
} // end namespace constraints
} // end namespace swift