Swiftの型システムを読む その24 - PotentialBinding周辺の用語・関数

December 31, 2017

Swiftの型推論では、型変数に適切なBindingを決めて試すことを繰り返す ことで制約の単一化を行う。今回はその際に使われるPotentialBindingやそれに関連する関数を見ていく。ファイルとしてはCSBindings.cpp

PotentialBinding / PotentialBindings

型変数が取りうる具体的な型へのBindingをPotentialBindingという構造体で表している。

/// A potential binding from the type variable to a particular type,
/// along with information that can be used to construct related
/// bindings, e.g., the supertypes of a given type.
struct PotentialBinding {
  /// The type to which the type variable can be bound.
  Type BindingType;
  ...
}

型変数が取りうるBindingは複数考えられるので、PotentialBindingsという構造体に型変数と具体的な型の配列を持っている。

struct PotentialBindings {
  TypeVariableType *TypeVar;

  /// The set of potential bindings.
  SmallVector<PotentialBinding, 4> Bindings;
  ...
}

また、その型変数を持っているConstraintをBindingSourceという名前でPotentialBiningに持っている。

/// The kind of the constraint this binding came from.
ConstraintKind BindingSource;

AllowedBindingKind

PotentialBindingには「そのBindingが適用できる条件」のようなものがある。それがAllowedBindingKindで表されている。

/// The kind of bindings that are permitted.
enum class AllowedBindingKind : unsigned char {
  /// Only the exact type.
  Exact,
  /// Supertypes of the specified type.
  Supertypes,
  /// Subtypes of the specified type.
  Subtypes
};

それぞれ「完全に一致する型として」「スーパータイプとして」「サブタイプとして」使えることを表している。 これをPotentialBindingKindという形で持っている。

 /// The kind of bindings permitted.
 AllowedBindingKind Kind;

DefaultedProtocol

Constarintが以下のKindを持つ場合にProtocolDeclが取得できる。

ProtocolDecl *Constraint::getProtocol() const {
  assert((Kind == ConstraintKind::ConformsTo ||
          Kind == ConstraintKind::LiteralConformsTo ||
          Kind == ConstraintKind::SelfObjectOfProtocol)
          && "Not a conformance constraint");
  return Types.Second->castTo<ProtocolType>()->getDecl();
}

このConstraintが型変数を含み、それをPotentialBindingとして採用する場合、PotentialBindingDefaultedProtocolという名前で保持される。

/// The defaulted protocol associated with this binding.
Optional<ProtocolDecl *> DefaultedProtocol;

DefaultableConstraint

ConstraintKind::Defaultable を持つConstraintは例えば以下のようなときに使われる。

  • return文が省略されたClosure式のの返り値の型はデフォルトで()
  • Arrayリテラルがヘテロな場合など、ArrayのElementの型はデフォルトでAny

この制約を元にPotentialBindingが作られる場合、DefaultableBindingに記録される。

/// If this is a binding that comes from a \c Defaultable constraint,
/// the locator of that constraint.
ConstraintLocator *DefaultableBinding = nullptr;

このPotentialBindingが採用される場合、ConstraintSystemDefaultedConstraintsに記録される。

addConstraint(ConstraintKind::Bind, typeVar, type,
              typeVar->getImpl().getLocator());

// If this was from a defaultable binding note that.
if (binding.isDefaultableBinding()) {
      DefaultedConstraints.push_back(binding.DefaultableBinding);
}

ConstraintSystem::PotentialBindings::addPotentialBinding

void ConstraintSystem::PotentialBindings::addPotentialBinding(
    PotentialBinding binding, bool allowJoinMeet) { ... }

基本的にはPotentialBindingsBindingsに追加するのだが、同じ型変数へのSupertypePotentialBindingが追加された場合は結び(join)を計算してから追加する。

ConstraintSystem::determineBestBindings

名前の通りBestPotentialBindingsを決める。PotentialBindingではないことに注意、つまり「どの型変数に対してBindingを決めるのが良いのか」を決めている。

Optional<ConstraintSystem::PotentialBindings>
ConstraintSystem::determineBestBindings() { ... }

決める方法はBindingScoreというスコアで決めている。ConstraintSystemScoreとは別。

typedef std::tuple<bool, bool, bool, bool, unsigned char, unsigned int>
    BindingScor

少しだけ中身を見ると、DefaultableなBinding以外のBindingがあるか、型変数の有無等によってスコアが決まっているみたい。

static BindingScore formBindingScore(const PotentialBindings &b) {
  return std::make_tuple(!b.hasNonDefaultableBindings(),
                         b.FullyBound,
                         b.SubtypeOfExistentialType,
                         b.InvolvesTypeVariables,
                         static_cast<unsigned char>(b.LiteralBinding),
                         -(b.Bindings.size() - b.NumDefaultableBindings));
}

ConstraintSystem::getPotentialBindings

上のdetermineBestBindingsの中で使われる。ある型変数に対するPotentialBindingsを取得する。詳細な実装は次回以降読む。

/// \brief Retrieve the set of potential type bindings for the given
/// representative type variable, along with flags indicating whether
/// those types should be opened.
ConstraintSystem::PotentialBindings
ConstraintSystem::getPotentialBindings(TypeVariableType *typeVar) { ... }

ざっくりとは

  • ConstraintGraphから必要な制約を集めてくる
  • リテラルやDefaultableなものを元にPotentialBindingsを作る。

まとめ

とりあえずざっと読んでみてわからなかった用語などをまとめてみた。 getPotentialBindingsCSBinding.cppのほとんどを占め、型推論の根幹でもありあそうなので、次回ちゃんと読む。

このエントリーをはてなブックマークに追加