GoのScope完全に理解した（かった）

はじめに

プログラミングを勉強すると，スコープというものを知ります．宣言された変数や関数がどこからどこまで参照できるかみたいなアレです．フワッと概念的なもののような気がしますが，もちろんちゃんと実装されています．今回はGoを題材に，スコープがどのように実装されているかを見ていきます．

`Scope`構造体

コード内を探してみると，src/go/types/scope.goでScope構造体が定義されていました．

// src/go/types/scope.go#L21-L33

// A Scope maintains a set of objects and links to its containing
// (parent) and contained (children) scopes. Objects may be inserted
// and looked up by name. The zero value for Scope is a ready-to-use
// empty scope.
type Scope struct {
	parent   *Scope
	children []*Scope
	number   int               // parent.children[number-1] is this scope; 0 if there is no parent
	elems    map[string]Object // lazily allocated
	pos, end token.Pos         // scope extent; may be invalid
	comment  string            // for debugging only
	isFunc   bool              // set if this is a function scope (internal use only)
}

parentとchildrenがあることから，スコープが木構造を成すことがわかります．個人的には，numberの説明

// parent.children[number-1] is this scope; 0 if there is no parent

が明快でとても好感が持てます．良い定義ですね．

また，elemsがこのスコープで宣言された変数や関数を持っています．posとendはソースコード上の位置を表します．

初期化

スコープの初期化は，次の関数で行われます．

// src/go/types/scope.go#L35-L45

// NewScope returns a new, empty scope contained in the given parent
// scope, if any. The comment is for debugging only.
func NewScope(parent *Scope, pos, end token.Pos, comment string) *Scope {
	s := &Scope{parent, nil, 0, nil, pos, end, comment, false}
	// don't add children to Universe scope!
	if parent != nil && parent != Universe {
		parent.children = append(parent.children, s)
		s.number = len(parent.children)
	}
	return s
}

空のスコープsを作成し，与えられた親スコープにそれを追加してsを返却します．universeはどこからでも参照できる，最上位のスコープのようなものです．

宣言

このスコープ内でで変数や関数を宣言したとき，Insertメソッドによってスコープにそのオブジェクトが挿入されます．

// src/go/types/scope.go#L102-L122

// Insert attempts to insert an object obj into scope s.
// If s already contains an alternative object alt with
// the same name, Insert leaves s unchanged and returns alt.
// Otherwise it inserts obj, sets the object's parent scope
// if not already set, and returns nil.
func (s *Scope) Insert(obj Object) Object {
	name := obj.Name()
	if alt := s.Lookup(name); alt != nil {
		return alt
	}
	s.insert(name, obj)
	// TODO(gri) Can we always set the parent to s (or is there
	// a need to keep the original parent or some race condition)?
	// If we can, than we may not need environment.lookupScope
	// which is only there so that we get the correct scope for
	// marking "used" dot-imported packages.
	if obj.Parent() == nil {
		obj.setParent(s)
	}
	return nil
}

Lookupはスコープ内にその名前のオブジェクトがあるか調べ，もしあればそのスコープを変更せずにそのオブジェクト自体を返します．そうでなければinsertでスコープにオブジェクトを追加し，そのオブジェクトの親をそのスコープに設定します．

Scope構造体に関する基本的な操作はこれでさらうことができました．

スコープ内のオブジェクト検索

check.goでは，enviroment構造体を通じてスコープ内の検索機能が提供されています．

// src/go/types/check.go#L92-L107

// lookupScope looks up name in the current environment and if an object
// is found it returns the scope containing the object and the object.
// Otherwise it returns (nil, nil).
//
// Note that obj.Parent() may be different from the returned scope if the
// object was inserted into the scope and already had a parent at that
// time (see Scope.Insert). This can only happen for dot-imported objects
// whose parent is the scope of the package that exported them.
func (env *environment) lookupScope(name string) (*Scope, Object) {
	for s := env.scope; s != nil; s = s.parent {
		if obj := s.Lookup(name); obj != nil && (!env.exprPos.IsValid() || cmpPos(obj.scopePos(), env.exprPos) <= 0) {
			return s, obj
		}
	}
	return nil, nil
}

for文を回し，現在のスコープから親スコープへと順に検索を行います．探しているオブジェクトが見つかったら，それが属するスコープとオブジェクトを返します．

if文の条件式が複雑ですが，ちょっと見てみましょう．

if obj := s.Lookup(name); obj != nil && (!env.exprPos.IsValid() || cmpPos(obj.scopePos(), env.exprPos) <= 0)

この条件は2つの部分に分かれます：

obj != nil: 指定された名前のオブジェクトがスコープ内に存在するか
(!env.exprPos.IsValid() || cmpPos(obj.scopePos(), env.exprPos) <= 0): 宣言順序の制約チェック

2つ目の条件が重要です．これは「オブジェクトが現在の式より前に宣言されているか」を確認しています.

env.exprPos.IsValid(): 現在の式の位置が有効か
obj.scopePos(): オブジェクトが宣言された位置
env.exprPos: 現在参照しようとしている式の位置
cmpPos(...) <= 0: 宣言が参照より前にあること

この制約により，以下のようなコードでエラーを発生させます．

func example() {
    x := y  // エラー: yはまだ宣言されていない
    y := 42
}

一方，以下は正常に動作します：

func example() {
    y := 42
    x := y  // OK: yは既に宣言されている
}

スコープがどうこうというよりは，単純に今参照している箇所の前で宣言されているかを見ているんですね．

これがCheckerのidentメソッドで呼ばれ，最終的にオブジェクトの型チェックが行われます．

感想

今回は，スコープが木構造を持つこと，オブジェクトの宣言がどのように検索されるかを見ました．型チェックに使われるCheck構造体（50行くらいある）でスコープがふんだんに使われているっぽいのですが，みる部分が多すぎて全然理解できていません．いつか理解したいです．

はじめに

Scope構造体

初期化

宣言

スコープ内のオブジェクト検索

感想

`Scope`構造体