[インデックス 17552] ファイルの概要

このコミットは、Goコマンドラインツール（cmd/go）におけるパッケージ探索の効率化を目的としています。具体的には、パターンマッチングに基づいてファイルツリーのウォーク（走査）を枝刈り（prune）する機能を追加し、不要なディレクトリの探索をスキップすることで、go listなどのコマンドのパフォーマンスを向上させています。

コミット

commit e6a49555a723e176dbcc45ca9201006575fd3e56
Author: Russ Cox <rsc@golang.org>
Date:   Wed Sep 11 09:57:05 2013 -0400

    cmd/go: use pattern to prune file tree walk

    For example, if the pattern is m... there is
    no need to look in directories not beginning with m.

    Fixes #5214.

    R=golang-dev, adg
    CC=golang-dev
    https://golang.org/cl/13253049

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/e6a49555a723e176dbcc45ca9201006575fd3e56

元コミット内容

cmd/go: use pattern to prune file tree walk

このコミットは、cmd/goツールがファイルツリーを走査する際に、指定されたパターンに基づいて不要な探索を枝刈りするように変更します。例えば、パターンがm...（mで始まる任意のパッケージ）である場合、mで始まらないディレクトリを探索する必要がなくなります。

この変更は、Issue #5214 を修正します。

変更の背景

Goのパッケージ管理システムでは、go listやgo buildなどのコマンドが、GOPATHやGOROOT配下のディレクトリを走査してパッケージを探します。この走査は、特に大規模なプロジェクトや多数のパッケージが存在する環境では、時間がかかるボトルネックとなる可能性がありました。

元の実装では、パッケージのパターンマッチングを行う際に、すべてのディレクトリを走査してから、その結果に対してパターンを適用していました。これは、パターンに合致しないことが明らかなディレクトリであっても、無駄に走査してしまうことを意味します。

このコミットの背景にあるのは、このような非効率性を解消し、パッケージ探索のパフォーマンスを向上させることです。具体的には、パターンが与えられた場合に、そのパターンに合致する可能性がないディレクトリを早期にスキップすることで、ファイルシステムへのアクセス回数を減らし、コマンドの実行時間を短縮することを目指しています。

Issue #5214 は、まさにこのパフォーマンスの問題を指摘しており、go list ...のようなコマンドが非常に遅いという報告がなされていました。このコミットは、その問題に対する直接的な解決策を提供します。

前提知識の解説

Goコマンド (cmd/go)

cmd/goは、Go言語のビルド、テスト、パッケージ管理などを行うための公式コマンドラインツールです。開発者はこのツールを使って、Goプログラムのコンパイル、依存関係の管理、テストの実行などを行います。

go listコマンド

go listコマンドは、Goパッケージに関する情報を表示するために使用されます。例えば、go list allはすべての利用可能なパッケージをリストアップし、go list <pattern>は指定されたパターンに合致するパッケージをリストアップします。このコマンドは、パッケージの依存関係の解析や、ビルドシステムの自動化など、様々な場面で利用されます。

パッケージパターン

Goコマンドでは、パッケージを指定する際にパターンを使用できます。

• . : 現在のディレクトリのパッケージ
• ... : 現在のディレクトリとそのサブディレクトリ内のすべてのパッケージ
• net : netパッケージ
• net/http : net/httpパッケージ
• net... : netで始まるすべてのパッケージ（例: net, net/http, netchanなど）
• net/... : netディレクトリとそのサブディレクトリ内のすべてのパッケージ（例: net/http, net/rpcなど）

ファイルツリーウォーク (File Tree Walk)

ファイルツリーウォークとは、ファイルシステム上のディレクトリ構造を再帰的に探索する処理のことです。Go言語では、filepath.Walk関数などがこの目的で使用されます。この処理は、特定のファイルやディレクトリを探したり、ファイルシステム全体の情報を収集したりする際に必要となります。

枝刈り (Pruning)

枝刈りとは、探索アルゴリズムにおいて、不要な探索パスを早期に打ち切る最適化手法です。ファイルツリーウォークにおいては、特定の条件に基づいて、そのディレクトリ以下を探索しても目的の結果が得られないことが分かった場合に、そのディレクトリの探索をスキップすることを指します。これにより、探索範囲が大幅に削減され、パフォーマンスが向上します。

技術的詳細

このコミットの主要な変更点は、cmd/go/main.goにhasPathPrefixとtreeCanMatchPatternという2つの新しいヘルパー関数を導入し、これらをmatchPackages関数内で利用することで、ファイルツリーウォークの枝刈りを実現している点です。

1. hasPathPrefix(s, prefix string) bool: この関数は、文字列sがprefixで始まるかどうかを報告します。ただし、単なるstrings.HasPrefixとは異なり、パスのセパレータ（/）を考慮して、パスの要素としてprefixがsのプレフィックスになっているかを厳密にチェックします。 例えば、hasPathPrefix("net/http", "net")はtrueを返しますが、hasPathPrefix("netchan", "net")はfalseを返します。これは、netchanがnetで始まるものの、netが独立したパス要素ではないためです。

2. treeCanMatchPattern(pattern string) func(name string) bool: この関数は、与えられたpatternに基づいて、特定のname（ディレクトリ名またはパッケージ名）またはその子孫がパターンに合致する可能性があるかどうかを判断するクロージャを返します。

   • パターンに...（ワイルドカード）が含まれる場合、wildCardフラグがtrueになります。
   • 返されるクロージャは、以下のいずれかの条件が満たされる場合にtrueを返します。
     • nameの長さがpatternの長さ以下であり、かつpatternがnameのパスプレフィックスである場合。これは、patternがnameの親ディレクトリであるか、name自身である場合に該当します。例えば、pattern="net/http"、name="net"の場合など。
     • wildCardがtrueであり、かつnameがpatternのプレフィックスである場合。これは、patternがnet...のような形式で、nameがnetで始まる場合に該当します。

3. matchPackages関数での利用: matchPackages関数は、go listコマンドなどでパッケージを探索する際に使用される主要な関数です。この関数内で、patternが"all"や"std"でない場合に、matchPatternに加えてtreeCanMatchPatternが初期化されます。 ファイルツリーを走査するfilepath.Walkのコールバック関数内で、treeCanMatch(name)がfalseを返した場合、filepath.SkipDirを返すように変更されました。filepath.SkipDirを返すと、filepath.Walkはそのディレクトリの探索をスキップし、そのサブディレクトリにも入らなくなります。

この変更により、例えばgo list m...というコマンドが実行された場合、treeCanMatchPattern("m...")はmで始まらないディレクトリに対してfalseを返します。これにより、filepath.Walkはmで始まらないディレクトリを早期にスキップし、不要なファイルシステムアクセスを削減します。

コアとなるコードの変更箇所

src/cmd/go/main.go

• hasPathPrefix関数の追加
• treeCanMatchPattern関数の追加
• matchPackages関数内でtreeCanMatchPatternを初期化し、filepath.Walkのコールバック内でtreeCanMatch(name)がfalseの場合にfilepath.SkipDirを返すロジックを追加。

--- a/src/cmd/go/main.go
+++ b/src/cmd/go/main.go
@@ -434,6 +434,37 @@ func matchPattern(pattern string) func(name string) bool {
 	}\n}\n
+
+// hasPathPrefix reports whether the path s begins with the
+// elements in prefix.
+func hasPathPrefix(s, prefix string) bool {
+	switch {
+	default:
+		return false
+	case len(s) == len(prefix):
+		return s == prefix
+	case len(s) > len(prefix):
+		if prefix != "" && prefix[len(prefix)-1] == '/' {
+			return strings.HasPrefix(s, prefix)
+		}
+		return s[len(prefix)] == '/' && s[:len(prefix)] == prefix
+	}
+}
+
+// treeCanMatchPattern(pattern)(name) reports whether
+// name or children of name can possibly match pattern.
+// Pattern is the same limited glob accepted by matchPattern.
+func treeCanMatchPattern(pattern string) func(name string) bool {
+	wildCard := false
+	if i := strings.Index(pattern, "..."); i >= 0 {
+		wildCard = true
+		pattern = pattern[:i]
+	}
+	return func(name string) bool {
+		return len(name) <= len(pattern) && hasPathPrefix(pattern, name) ||
+			wildCard && strings.HasPrefix(name, pattern)
+	}
+}
+
 // allPackages returns all the packages that can be found
 // under the $GOPATH directories and $GOROOT matching pattern.
 // The pattern is either "all" (all packages), "std" (standard packages)
@@ -448,8 +479,10 @@ func allPackages(pattern string) []string {
 
 func matchPackages(pattern string) []string {
 	match := func(string) bool { return true }
+	treeCanMatch := func(string) bool { return true }
 	if pattern != "all" && pattern != "std" {
 		match = matchPattern(pattern)
+		treeCanMatch = treeCanMatchPattern(pattern)
 	}
 
 	have := map[string]bool{
@@ -467,6 +500,9 @@ func matchPackages(pattern string) []string {
 			return nil
 		}
 		name := path[len(cmd):]
+		if !treeCanMatch(name) {
+			return filepath.SkipDir
+		}
 		// Commands are all in cmd/, not in subdirectories.
 		if strings.Contains(name, string(filepath.Separator)) {
 			return filepath.SkipDir
@@ -512,6 +548,9 @@ func matchPackages(pattern string) []string {
 			if pattern == "std" && strings.Contains(name, ".") {
 				return filepath.SkipDir
 			}
+			if !treeCanMatch(name) {
+				return filepath.SkipDir
+			}
 			if have[name] {
 				return nil
 			}

src/cmd/go/match_test.go

• TestMatchPatternのテスト構造体をstringPairTest型に統一し、testStringPairsヘルパー関数を使用するように変更。
• treeCanMatchPatternTestsという新しいテストケース群と、それらをテストするためのTestChildrenCanMatchPattern関数を追加。
• hasPathPrefixTestsという新しいテストケース群と、それらをテストするためのTestHasPathPrefix関数を追加。
• stringPairTest構造体とtestStringPairsヘルパー関数を追加。

src/cmd/go/test.bash

• ワイルドカードパターンが不要なディレクトリを探索しないことを確認するための新しいシェルテストケースを追加。このテストは、badpkgという存在しないパッケージを含むディレクトリが、m...のようなパターンで探索されないことを検証します。

src/cmd/go/testdata/src/badpkg/x.go

• テストのためにbadpkgというダミーのパッケージファイルを追加。

コアとなるコードの解説

このコミットの核心は、treeCanMatchPattern関数と、それがmatchPackages関数内でfilepath.Walkの枝刈りにどのように利用されているかです。

treeCanMatchPattern関数

この関数は、与えられたパターン（例: net..., net/http, x/y/z/...）と、現在走査中のディレクトリ名（name）を受け取り、そのディレクトリまたはそのサブディレクトリがパターンに合致する可能性があるかどうかを判断します。

• ワイルドカードの処理: パターンに...が含まれる場合、wildCardフラグが立てられ、パターンから...が取り除かれます。これにより、net...はnetとして扱われ、netで始まるすべてのパスにマッチする可能性を考慮します。
• クロージャの返却: 実際のチェックロジックは、返される無名関数（クロージャ）内にカプセル化されています。このクロージャは、filepath.Walkによって各ディレクトリが走査されるたびに呼び出されます。
• マッチングロジック:
  1. len(name) <= len(pattern) && hasPathPrefix(pattern, name): これは、現在のディレクトリ名nameが、パターンpatternの「親」または「自身」である場合にtrueを返します。例えば、pattern="net/http"でname="net"の場合、netディレクトリはnet/httpを含む可能性があるため、trueを返します。hasPathPrefixはパスのセパレータを考慮するため、netchanのようなケースとは区別されます。
  2. wildCard && strings.HasPrefix(name, pattern): これは、パターンが...を含むワイルドカードパターン（例: net...）であり、かつ現在のディレクトリ名nameがそのワイルドカードのプレフィックス（例: net）で始まる場合にtrueを返します。これにより、netで始まるすべてのディレクトリ（net, net/http, netchanなど）が探索対象となる可能性を考慮します。

これらの条件のいずれかが満たされれば、そのディレクトリはパターンに合致する可能性があると判断され、探索が続行されます。そうでなければ、そのディレクトリ以下はパターンに合致する可能性がないと判断されます。

matchPackages関数での利用

matchPackages関数は、filepath.Walkを使用してGOPATHやGOROOT配下のディレクトリを走査します。この走査中に、各ディレクトリに対してtreeCanMatchクロージャが呼び出されます。

		if !treeCanMatch(name) {
			return filepath.SkipDir
		}

このコードスニペットが、枝刈りの肝となる部分です。

• nameは、現在走査中のディレクトリのパッケージ名（GOPATHやGOROOTからの相対パス）です。
• treeCanMatch(name)がfalseを返した場合、つまり、現在のディレクトリnameまたはその子孫が、指定されたパッケージパターンに合致する可能性が全くないと判断された場合、filepath.SkipDirが返されます。
• filepath.SkipDirを返すと、filepath.Walkは現在のディレクトリの残りの処理をスキップし、そのディレクトリのサブディレクトリへの再帰的な探索も行いません。これにより、不要なディレクトリの走査が完全に回避され、ファイルシステムへのアクセスが大幅に削減されます。

この最適化は、特にgo list ...のように広範囲を探索するコマンドや、GOPATHに多数のプロジェクトや依存関係が存在する環境において、顕著なパフォーマンス改善をもたらします。

関連リンク

• Go Issue #5214: go list ... is very slow: https://code.google.com/p/go/issues/detail?id=5214 (現在はGitHubに移行)
• Go CL 13253049: cmd/go: use pattern to prune file tree walk: https://golang.org/cl/13253049

参考にした情報源リンク

• Go言語の公式ドキュメント: go help list
• Go言語の公式ドキュメント: filepathパッケージ
• Go言語のソースコード: src/cmd/go/main.go
• Go言語のソースコード: src/cmd/go/match_test.go
• Go言語のIssueトラッカー: Issue 5214
• Go言語のコードレビューシステム: CL 13253049