依存関係

<ph type="x-smartling-placeholder"></ph> 問題を報告する <ph type="x-smartling-placeholder"></ph> ソースを表示 夜間 · 7.3 · 7.2 · 7.1 · 7.0 · 6.5

Depset は、データセットを効率的に処理するための特殊なデータ構造です。 ターゲットの推移的依存関係全体でデータを収集します。これらの原則は 要素です。

depset の特徴は、時間効率とスペース効率に優れたユニオン演算です。 depset コンストラクタは、要素のリスト(「direct」)と、他の要素の depset("transitive")で、デプセット(depset)を すべての推移的集合の和集合です。概念的には、 コンストラクタは、直接ノードと推移的ノードを持つ新しいグラフノードを作成します。 あります。Depset には、順序のセマンティクスが明確に定義されています。 このグラフの走査を表します

依存関係の使用例を次に示します。

  • プログラムのライブラリのすべてのオブジェクト ファイルのパスを保存します。これにより、 プロバイダを介してリンカー アクションに渡されます。

  • インタプリタ言語の場合、一時的なソースファイルは 実行可能なファイルの run ファイルに含めます

説明とオペレーション

概念的には、depset は有向非巡回グラフ(DAG)であり、 ターゲットグラフのようになります葉から根までできています。 依存関係チェーン内の各ターゲットは、依存関係の上に独自のコンテンツを追加できます。 読み取ることもコピーも不要です

DAG 内の各ノードは、直接要素のリストと子ノードのリストを保持します。 depset の内容が推移的要素(直接要素など) 自動的に作成されます。新しい 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 はそれ自体と等しいが、いずれかとは等しくない other 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 を走査します。走査の種類 依存関係が指定された時点で指定された順序に依存する あります。Bazel は複数の注文をサポートすると便利です。次のような理由があります。 ツールは入力の順序を考慮します。たとえばリンカー アクションは BA に依存している場合は、A.oB.o よりも前に配置されるようにする必要があります。 表示されます。逆の要件があるツールもあります。

サポートされている 3 つの走査順序: postorderpreordertopological。最初の 2 つは、tree とまったく同じように 走査 DAG を操作し、すでに参照されているノードをスキップします。3 番目の注文 根から葉までのトポロジー的な並べ替えとして機能し、基本的には 予約します。ただし、共有された子は、親のすべての後にのみ表示されます。 preorder と postorder は左右のトラバーサルとして動作しますが、 各ノードの直接的な要素には子に対する順序はありません。トポロジや 左から右への保証はなく、さらに 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 内のすべての*.foo abcdsrcs フィールド。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 回表示されます。 表示されます。

もう 1 つの方法として、一般的なセットを使用してシミュレートできます。 キーが要素で、すべてのキーが 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) になります。

一般的に、デプセットは 推移的依存関係を使用して 情報を取得しますこれにより ビルドがスケールし ターゲットグラフが深くなります

最後に、depset のコンテンツを取得しないことが 不必要に注意を払うことができます。to_list() への通話 1 回 全体的なコストは O(n) なので、バイナリルールの最後には問題ありません。です。 多くの非終端ターゲットが、その二次的動作である to_list() を呼び出そうとしたとき 発生します。

依存関係を効率的に使用する方法については、パフォーマンス ページをご覧ください。

API リファレンス

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