Swiftの型システムを読む その22 - ConstraintGraphの理論と実装

December 27, 2017

ConstraintGraphは制約のSolveの際に型変数を管理するためのクラス。 名前の通りグラフなのだが、ハイパーグラフ(hyper graph)と呼ばれる一般的なグラフを少し拡張したような物になっている。

今回はハイパーグラフについて調べ、実装を読んでみる。

ハイパーグラフ(hyper graph)とその周辺用語の整理

ハイパーグラフは一般的なグラフと同じようにノードとエッジから構成されるが、エッジに特徴がある。

一般的なグラフのエッジは2つのノード間を結ぶが、ハイパーグラフにおけるエッジはハイパーエッジ(hyper edge)と呼ばれ、N個のノードを結ぶ。 (Nは1でもOK)

1.png (83.7 kB)

形式的にはノードの集合と、エッジを構成するノードの集合の集合のペアからなる。

隣接(Adjacency)

隣接はあるノードからエッジで結ばれているノードのこと。 ハイパーグラフでも大体同じ意味だが、ConstraintGraphでは少し性質がことなる。(後述)

2.png (57.1 kB)

連結成分(Connected Component)

単にComponentとも。非連結グラフを構成する連結グラフのこと。 要はエッジによって結ばれたかたまり。ハイパーグラフでも同じ。

3.png (46.6 kB)

縮約(Contraction)

一般的なグラフにおいては、グラフからあるエッジをを取り除きそのエッジの両端を一つのノードにまとめることを縮約(Contraction)という。

4.png (45.6 kB)

ハイパーグラフにおいては正確な定義はわからないけど、エッジが結んでいるノードの一部を一つのノードのまとめることを言うみたい。

5.png (69.7 kB)

グラフについてはここまでわかればよさそう。 グラフ関係ないけど、同値類(Equivalence Class)とか代表元(Representative)とかもし知らなければ調べておくと読みやすいかも。

ハイパーグラフとしてのConstraintGraph

ConstraintGraphではノード・エッジが以下のものに対応している。

  • ノードは型変数
  • エッジはその型変数を含むConstraintの集合

6.png (56.3 kB)

具体的に実装を見ていく。ノードについてはそのままConstraintGraphNodeというクラスで実装されている。

/// A single node in the constraint graph, which represents a type variable.
class ConstraintGraphNode { ... }

各ノードが持っている情報は大まかにこんな感じ。

// このノードが表す型変数
TypeVariableType *TypeVar;

// この型変数をもつ制約。
// これがエッジを表す。
SmallVector<Constraint *, 2> Constraints;

// 隣接ノード
SmallVector<TypeVariableType *, 2> Adjacencies;

// 隣接ノードの情報
llvm::SmallDenseMap<TypeVariableType *, Adjacency, 2> AdjacencyInfo;

// 同値類
mutable SmallVector<TypeVariableType *, 2> EquivalenceClass;

また、ConstraintGraphにおけるエッジは「あるNode(型変数)を中心として、その隣接の集まり」で表される。

ConstraintGraph自身は主に以下の2つの情報を管理している。

// このグラフで扱っている型変数
SmallVector<TypeVariableType *, 4> TypeVariables;

// Orphanedは孤立したみたいな意味
// addConstraintされたものの、型変数を持たないときにここに入ってくる。
// (ただ...それはどんなとき?)
SmallVector<Constraint *, 4> OrphanedConstraints;

ConstraintGraphに対する主な操作一覧

  • ConstraintGraph::lookupNode
  • ConstraintGraph::addConstraint
  • ConstraintGraph::removeConstraint
  • ConstraintGraph::computeConnectedComponents
  • ConstraintGraph::optimize
  • ConstraintGraph::getOrphanedConstraints
  • ConstraintGraph::takeOrphanedConstraints
  • ConstraintGraph::setOrphanedConstraint
  • ConstraintGraph::mergeNodes
  • ConstraintGraph::bindTypeVariables
  • ConstraintGraph::gatherConstraints

ここからいくつかピックアップして挙動をみてみる。

lookupNode / addConstraint

lookupNodeは名前の通り型変数を使って対象のノードを引いてくる。 その際に、その型変数がまだノードして存在しなければ追加してからそれを返す。 実際には型変数を表すクラスTypeVariableTypeimplがノードを持っている形らしい。

// Allocate the new node.
auto nodePtr = new ConstraintGraphNode(typeVar);
unsigned index = TypeVariables.size();
impl.setGraphNode(nodePtr);
impl.setGraphIndex(index);

// Record this type variable.
TypeVariables.push_back(typeVar);

また[]オペレータでもこれが使われる。 addConstraintによってConstraintGraphに制約が追加されると、まず上のlookupNodeが呼ばれてノードが用意される。

そしてそのノードに対してConstraintが追加される。 エッジが拡張されるようなイメージ。

node.addConstraint(constraint);

両方とも型変数の場合には隣接ノードとしても登録される。

7.png (70.4 kB)

optimize / contractEdges / mergeEquivalenceClasses

ソルバーの中ではoptimizeが呼ばれているだけなので実態が分かりづらいが、やっていることはシンプルでひたすらcontractEdges()を呼んで可能な限り縮約しているだけ。

void ConstraintGraph::optimize() {
  // Merge equivalence classes until a fixed point is reached.
  while (contractEdges()) {}
}

contractEdgesでは、ConstraintがBind系もしくはEqualの場合にそのConstraintを取り除いた後、Constraintの2つの型を同値類として登録する。

removeEdge(constraint);
if (rep1 != rep2)
  CS.mergeEquivalenceClasses(rep1, rep2, /*updateWorkList*/ false);

mergeEquivalenceClassesは名前の通り2つの型変数をマージする。

5.png (69.7 kB)

bindTypeVariable

solutionを1つ受け取る方のapplySolutionで使われる。 (applySolutionsolveSimplifyの過程で使われるものと、TypeCheckerで最終的に使われるものの2つがあって、前者)

void ConstraintSystem::applySolution(const Solution &solution) { ... }

ここでConstarintSystem::assignFixedTypeが呼ばれ、さらにそこからbindTypeVariableが呼ばれる。

assignFixedType(binding.first, binding.second, /*updateState=*/false);
// Notify the constraint graph.
CG.bindTypeVariable(typeVar, type);

そうするとNodeのFixedBindingというフラグがたつ。 (どう使われる?)

まとめ

だいたいどんなものかはわかったので、実際の使われ方を次回見てみる。

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