デプト

問題を報告する ソースを表示

デプトは、ターゲットの推移的依存関係全体で効率的にデータを収集するための特別なデータ構造です。これらはルール処理に欠かせない要素です。

depset の定義機能は、時間とスペースを効率的に使用する union オペレーションです。 depset コンストラクタは、要素のリスト(「direct」)と他のデプトのリスト(「transitive」)を受け取り、すべての直接要素とすべての推移的セットのユニオンを含むセットを表す 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

DEPSET から要素を削除することはできません。必要な場合は、デプセットのコンテンツ全体を読み取って、削除する要素をフィルタし、新しいデプセットを再構築する必要があります。これは特に効率的ではありません。

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 では複数の注文をサポートすると便利です。たとえば、リンカー アクションでは、BA に依存している場合に、A.o がリンカーのコマンドラインで B.o の前に来るようにする必要があります。他のツールでは要件が逆になることがあります。

postorderpreordertopological の 3 つの走査順序がサポートされています。最初の 2 つは、ツリー トラバーサルとまったく同じように機能しますが、DAG が動作し、すでにアクセスしたノードをスキップする点が異なります。3 番目の順序はルートから出発までのトポロジの並べ替えとして機能します。基本的に、予約子と同じですが、共有の子はすべての親の後にのみリストされます。予約購入と事後注文は左から右への走査として動作しますが、各ノード内のダイレクト要素には子に対する順序はありません。トポロジの順序については、左から右への保証はありません。また、DAG の異なるノードに重複する要素がある場合、すべての親前保証は適用されません。

# 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 キーワード引数で順序セットを作成するときに順序を指定する必要があります。この引数を省略すると、依存関係には特別な 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 の推移的ソースは、abcdsrcs フィールド内のすべての *.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

これにより重複が排除されますが、コマンドライン引数の順序(つまり、ファイルの内容)は未指定のままになります。

さらに、どちらのアプローチも、デプセットに基づくアプローチよりも漸進的に悪いものとなっています。Foo ライブラリの依存関係の長いチェーンがある場合を考えてみましょう。すべてのルールを処理するには、その前に存在したすべての推移的ソースを新しいデータ構造にコピーする必要があります。つまり、個々のライブラリまたはバイナリ ターゲットを分析する時間と時間とコストは、チェーン自体の高さに比例します。長さが n のチェーンの場合、foolib_1 ← foolib_2 ← ... ← foolib_n の場合、全体のコストは実質的に O(n^2) です。

一般的に、デプセットは、推移的な依存関係を介して情報を蓄積する場合に使用してください。これにより、ターゲット グラフが深くなるにつれてビルドが適切にスケーリングされます。

最後に、ルール実装で不要なデプスの内容を取得しないようにすることが重要です。全体的なコストは O(n) だけなので、バイナリルールで末尾に to_list() を 1 回呼び出すのは問題ありません。非終端ターゲットの多くは、2 次動作が発生する to_list() を呼び出そうとします。

デプスを効率的に使用する方法について詳しくは、パフォーマンスのページをご覧ください。

API リファレンス

詳しくは、こちらをご覧ください。