依存関係は、ターゲットの推移的な依存関係全体でデータを効率的に収集するための特殊なデータ構造です。これらはルール処理に不可欠な要素です。
depset を定義する特徴は、時間とスペースを効率的に使用するユニオン演算です。depset コンストラクタは、要素のリスト（「direct」）と他の依存関係セットのリスト（「推移的」）を受け取り、すべての Direct 要素とすべての推移的セットの和集合を含むセットを表す depset を返します。概念的には、コンストラクタは、直接ノードと推移ノードを後継ノードとする新しいグラフノードを作成します。依存関係には、このグラフの走査に基づいて明確に定義された順序付けのセマンティクスがあります。
依存関係の使用例は次のとおりです。
プログラムのライブラリ用のすべてのオブジェクト ファイルのパスを保存し、プロバイダを介してリンカー アクションに渡すことができる。
インタプリタ言語の場合、実行可能ファイルのランファイルに含まれる推移的なソースファイルを保存します。
説明と操作
概念的には、depset は有向非巡回グラフ（DAG）で、通常はターゲット グラフに似ています。皮から根まで積み上げられています。依存関係チェーン内の各ターゲットは、以前のコンテンツを読み取ったりコピーしたりすることなく、そこに独自のコンテンツを追加できます。
DAG 内の各ノードは、直接要素のリストと子ノードのリストを保持します。依存関係は、すべてのノードの直接要素などの推移的な要素です。新しい depset を作成するには、depset コンストラクタを使用します。このコンストラクタは、直接要素のリストと子ノードの別のリストを受け入れます。
s = depset(["a", "b", "c"])
t = depset(["d", "e"], transitive = [s])
print(s) # depset(["a", "b", "c"])
print(t) # depset(["d", "e", "a", "b", "c"])
依存関係セットの内容を取得するには、to_list() メソッドを使用します。すべての推移的要素（重複は含まれません）のリストを返します。DAG の正確な構造を直接検査する方法はありませんが、この構造は要素が返される順序に影響します。
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
辞書で許可されているキーが制限されるように、依存関係内の許可されたアイテムは制限されます。特に、depset の内容が変更できない場合があります。
depset は参照等価を使用します。つまり、同じ内容と内部構造を持っていても、他の depset とは等しくありません。
s = depset(["a", "b", "c"])
t = s
print(s == t) # True
t = depset(["a", "b", "c"])
print(s == t) # False
d = {}
d[s] = None
d[t] = None
print(len(d)) # 2
依存関係をコンテンツで比較するには、並べ替えたリストに変換します。
s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list())) # True
依存関係の要素を削除することはできません。必要な場合は、デプセットの内容全体を読み取り、削除する要素をフィルタリングして、新しいデプセットを再構築する必要があります。これは特に効率的ではありません。
s = depset(["a", "b", "c"])
t = depset(["b", "c"])
# Compute set difference s - t. Precompute t.to_list() so it's not done
# in a loop, and convert it to a dictionary for fast membership tests.
t_items = {e: None for e in t.to_list()}
diff_items = [x for x in s.to_list() if x not in t_items]
# Convert back to depset if it's still going to be used for union operations.
s = depset(diff_items)
print(s) # depset(["a"])
順序
to_list オペレーションは、DAG に対して走査を実行します。走査の種類は、depset の作成時に指定された順序によって異なります。ツールでは入力の順序が考慮される場合があるため、Bazel では複数の順序をサポートすると便利です。たとえば、リンカー アクションでは、B が A に依存している場合、リンカーのコマンドラインで A.o が B.o の前に来るようにする必要があります。他のツールでは逆の要件があるかもしれません。
postorder、preorder、topological の 3 つの走査順序がサポートされています。最初の 2 つは、ツリー トラバーサルとまったく同じように機能しますが、DAG 上で動作し、アクセス済みのノードをスキップします。3 番目の順序はルートからリーフまでのトポロジソートとして機能し、共有の子がすべての親の後にのみリストされる点を除き、予約と基本的に同じです。preorder と postorder は左から右への走査として機能しますが、各ノード内で直接要素は子に対して順序付けられていないことに注意してください。トポロジの順序については、左から右への保証はなく、DAG の異なるノードに重複する要素がある場合、all-parents-before-child の保証は適用されません。
# This demonstrates different traversal orders.
def create(order):
cd = depset(["c", "d"], order = order)
gh = depset(["g", "h"], order = order)
return depset(["a", "b", "e", "f"], transitive = [cd, gh], order = order)
print(create("postorder").to_list()) # ["c", "d", "g", "h", "a", "b", "e", "f"]
print(create("preorder").to_list()) # ["a", "b", "e", "f", "c", "d", "g", "h"]
# This demonstrates different orders on a diamond graph.
def create(order):
a = depset(["a"], order=order)
b = depset(["b"], transitive = [a], order = order)
c = depset(["c"], transitive = [a], order = order)
d = depset(["d"], transitive = [b, c], order = order)
return d
print(create("postorder").to_list()) # ["a", "b", "c", "d"]
print(create("preorder").to_list()) # ["d", "b", "a", "c"]
print(create("topological").to_list()) # ["d", "b", "c", "a"]
走査の実装方法により、コンストラクタの order キーワード引数を使用して、依存関係の作成時に順序を指定する必要があります。この引数を省略すると、depset には特殊な default の順序があります。この場合、要素の順序は保証されません（ただし、確定的である場合を除きます）。
完全な例
この例は https://github.com/bazelbuild/examples/tree/main/rules/depsets で入手できます。
架空の解釈言語 Foo があるとします。各 foo_binary をビルドするには、直接または間接的に依存するすべての *.foo ファイルを把握している必要があります。
# //depsets:BUILD
load(":foo.bzl", "foo_library", "foo_binary")
# Our hypothetical Foo compiler.
py_binary(
name = "foocc",
srcs = ["foocc.py"],
)
foo_library(
name = "a",
srcs = ["a.foo", "a_impl.foo"],
)
foo_library(
name = "b",
srcs = ["b.foo", "b_impl.foo"],
deps = [":a"],
)
foo_library(
name = "c",
srcs = ["c.foo", "c_impl.foo"],
deps = [":a"],
)
foo_binary(
name = "d",
srcs = ["d.foo"],
deps = [":b", ":c"],
)
# //depsets:foocc.py
# "Foo compiler" that just concatenates its inputs to form its output.
import sys
if __name__ == "__main__":
assert len(sys.argv) >= 1
output = open(sys.argv[1], "wt")
for path in sys.argv[2:]:
input = open(path, "rt")
output.write(input.read())
ここで、バイナリ d の推移的ソースは、a、b、c、d の srcs フィールド内のすべての *.foo ファイルです。foo_binary ターゲットが d.foo 以外のファイルを認識するためには、foo_library ターゲットがファイルをプロバイダに渡す必要があります。各ライブラリは、独自の依存関係からプロバイダを受け取り、独自の即時ソースを追加して、拡張されたコンテンツを含む新しいプロバイダを渡します。foo_binary ルールは、プロバイダを返すのではなく、ソースの完全なリストを使用してアクションのコマンドラインを作成する点を除いて、同じ処理を行います。
foo_library ルールと foo_binary ルールの完全な実装を次に示します。
# //depsets/foo.bzl
# A provider with one field, transitive_sources.
FooFiles = provider(fields = ["transitive_sources"])
def get_transitive_srcs(srcs, deps):
"""Obtain the source files for a target and its transitive dependencies.
Args:
srcs: a list of source files
deps: a list of targets that are direct dependencies
Returns:
a collection of the transitive sources
"""
return depset(
srcs,
transitive = [dep[FooFiles].transitive_sources for dep in deps])
def _foo_library_impl(ctx):
trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
return [FooFiles(transitive_sources=trans_srcs)]
foo_library = rule(
implementation = _foo_library_impl,
attrs = {
"srcs": attr.label_list(allow_files=True),
"deps": attr.label_list(),
},
)
def _foo_binary_impl(ctx):
foocc = ctx.executable._foocc
out = ctx.outputs.out
trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
srcs_list = trans_srcs.to_list()
ctx.actions.run(executable = foocc,
arguments = [out.path] + [src.path for src in srcs_list],
inputs = srcs_list + [foocc],
outputs = [out])
foo_binary = rule(
implementation = _foo_binary_impl,
attrs = {
"srcs": attr.label_list(allow_files=True),
"deps": attr.label_list(),
"_foocc": attr.label(default=Label("//depsets:foocc"),
allow_files=True, executable=True, cfg="host")
},
outputs = {"out": "%{name}.out"},
)
これをテストするには、これらのファイルを新しいパッケージにコピーし、ラベルを適切に変更して、ダミー コンテンツを含むソース *.foo ファイルを作成し、d ターゲットをビルドします。
パフォーマンス
依存関係セットを使用する動機を確認するには、get_transitive_srcs() がソースをリストに収集した場合にどうなるかを検討してください。
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
ここでは重複が考慮されないため、a のソースファイルはコマンドラインに 2 回、出力ファイルの内容に 2 回表示されます。
別の方法として、キーが要素ですべてのキーが True にマッピングされている辞書でシミュレートできる、一般的なセットを使用できます。
def get_transitive_srcs(srcs, deps):
trans_srcs = {}
for dep in deps:
for file in dep[FooFiles].transitive_sources:
trans_srcs[file] = True
for file in srcs:
trans_srcs[file] = True
return trans_srcs
これにより重複は取り除かれますが、コマンドライン引数の順序（したがってファイルの内容）は確定的ですが、まだ指定されません。
さらに、どちらの方法も、depset に基づくアプローチよりも漸近的に悪化します。Foo ライブラリに長い依存関係チェーンがある場合について考えてみましょう。すべてのルールを処理するには、その前のすべての推移的ソースを新しいデータ構造にコピーする必要があります。つまり、個々のライブラリまたはバイナリ ターゲットを分析する時間とスペース コストは、チェーン内のその高さに比例します。長さ n のチェーンの場合、foolib_1 ← foolib_2 ← ... ← foolib_n の場合、全体のコストは実質的に O(n^2) となります。
一般的に、推移的依存関係を介して情報を蓄積する場合は常に、depset を使用する必要があります。これにより、ターゲットグラフが深くなったときに、ビルドも適切にスケーリングできます。
最後に、ルールの実装では、依存関係セットのコンテンツを不必要に取得しないことが重要です。全体のコストは O(n) だけであるため、バイナリルールの最後に to_list() を 1 回呼び出しても問題ありません。そのとき、多くの非終端ターゲットが to_list() を呼び出そうとすると、二次的動作が発生します。
依存関係を効率的に使用する方法については、パフォーマンスのページをご覧ください。
API リファレンス
詳しくは、こちらをご覧ください。