相约 2023 年 BazelCon 将于 10 月 24 日至 25 日在 Google 慕尼黑举办!了解详情

属性值

报告问题 查看源代码

Depsets 是一种专门的数据结构,用于高效地跨目标的传递依赖项收集数据。它们是规则处理过程中不可或缺的一部分

depset 的特征是其时间和省时联合操作。depset 构造函数可接受元素列表(“direct”)和一系列其他依赖项(“transitive”),并返回表示一个集的集合,该集合包含所有直接元素以及所有传递集的并集。从概念上讲,该构造函数会创建一个新的图节点,该节点将直接节点和传递节点作为其后续节点。依赖项具有根据此图的遍历明确定义的排序语义。

依赖项的使用示例包括:

  • 存储程序库的所有对象文件的路径,然后这些文件可通过提供程序传递给链接器操作。

  • 对于解释型语言,存储可执行文件的运行文件中包含的传递源文件。

说明和操作

从概念上讲,偏移是一种有向无环图 (DAG),通常看起来与目标图类似。它是从叶到根构造的。依赖项链中的每个目标都可以在它前面添加自己的内容,而无需读取或复制它们。

DAG 中的每个节点包含直接元素列表和子节点列表。 偏移的内容是传递元素,例如所有节点的直接元素。您可以使用 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

系统会限制项中允许的项,就像字典中允许的键一样。特别是,偏移内容是不可变的。

依赖项使用的是引用等式:偏移量等于自身,但不等于任何其他依赖项,即使它们具有相同的内容和相同的内部结构也是如此。

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

如需按内容比较 Depset,请将其转换为已排序的列表。

s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list()))  # True

无法从偏移中移除元素。如果需要,您必须读出 depset 的全部内容,过滤要移除的元素,并重建新的 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 执行遍历。遍历的类型取决于构造依赖项时指定的顺序。对 Bazel 支持多个顺序很有用,因为有时工具关注输入的顺序。例如,链接器操作可能需要确保如果 B 依赖于 A,则 A.o 会出现在链接器命令行中的 B.o 前面。其他工具可能恰恰相反。

支持三种遍历顺序:postorderpreordertopological。前两个函数的工作原理与树遍历完全一样,只不过它们会针对 DAG 执行操作并跳过已访问的节点。第三顺序为从根到左的拓扑排序,基本与预订基本相同,不同之处在于共享子项仅列在其所有父项之后。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 关键字参数创建依赖项时指定顺序。如果省略此参数,则偏移量具有特殊 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_libraryfoo_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 目标。

性能

如需了解使用 Depset 的动机,请考虑如果 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 的源文件将在命令行中出现两次,在输出文件的内容中会出现两次。

另一种方法是使用通用集,可通过字典模拟,其中键是元素,所有键都映射到 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)。

一般而言,当您通过传递依赖项累积信息时,应使用偏移。这有助于确保您的 build 随着目标图的扩大而扩展。

最后,请勿在规则实现中不必要地检索 Depset 的内容。可以在二进制文件规则末尾调用 to_list(),因为总费用仅为 O(n)。这是因为许多非终端目标尝试调用 to_list() 时就会出现二次行为。

如需详细了解如何高效地使用依赖项,请参阅性能页面。

API 参考文档

如需了解详情,请参阅此处