底盤組

7.3 · 7.2 · 7.1 · 7.0 · 6.5

Depset 是特殊的資料結構,用於有效率地收集目標的遞移依附元件中的資料。這是規則處理作業的重要元素。

depset 的定義功能是其時間和空間效率高的聯合運算。依賴集合建構函式會接受元素清單 (「直接」) 和其他依賴集合清單 (「傳遞」),並傳回代表包含所有直接元素和所有傳遞集合的集合的依賴集合。從概念上來說,建構函式會建立新的圖形節點,並將直接和間接節點設為後續節點。Depset 會根據此圖表的遍歷,提供明確的排序語意。

解碼器的使用範例包括:

  • 儲存程式程式庫的所有物件檔案路徑,然後可透過提供者將其傳遞至連結器動作。

  • 如為解譯語言,儲存包含在執行檔的執行檔案中的遞移來源檔案。

說明和運算

從概念上來說,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"])

如要擷取 depset 的內容,請使用 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 會使用參照相等性: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

如要依內容內容比較 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 執行周遊。檢視的類型取決於建構 depset 時指定的順序。Bazel 支援多個順序很有用,因為有時工具會在意輸入內容的順序。舉例來說,連結器動作可能需要確保如果 B 依附於 A,則 A.o 會在連結器指令列中出現在 B.o 之前。其他工具則可能有相反需求。

系統支援三種遍歷順序:postorderpreordertopological。前兩個運作方式與樹狀檢視完全相同,唯一的差異是它們會在 DAG 上運作,並略過已造訪的節點。第三個順序會從根節點到葉節點,以拓樸排序的方式運作,基本上與預先順序相同,只是共用子項只會列在所有父項之後。預序和後序會以從左到右的順序進行,但請注意,在每個節點中,直接元素與子項之間並無相對順序。針對拓撲順序,沒有由左至右的保證,即使 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 關鍵字引數建立 depset 時指定順序。如果省略這個引數,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 的傳遞來源是 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

這會移除重複項目,但這會讓指令列引數 (以及檔案的內容) 的順序未指定,但仍無法確定。

此外,這兩種方法的收斂速度都比以 depset 為基礎的方法還要慢。請考慮以下情況:Foo 程式庫有長長的依附元件鏈結。處理每項規則時,都必須將先前所有傳遞來源複製到新的資料結構中。也就是說,分析個別程式庫或二進位目標所需的時間和空間成本,會與該程式庫或二進位目標在鏈結中的高度成正比。對於長度為 n 的鏈結,foolib_1 ← foolib_2 ← … ← foolib_n,整體成本實際上是 O(n^2)。

一般來說,只要您透過間接依附元件累積資訊,就應使用 depset。這有助於確保在目標圖表變得更深入時,您的建構作業能順利擴充。

最後,請務必不要在規則實作中不必要地擷取 depset 的內容。在二元規則中,結尾處呼叫 to_list() 是可以接受的做法,因為整體成本僅為 O(n)。當許多非終端目標嘗試呼叫 to_list() 時,就會發生二次方行為。

如要進一步瞭解如何有效使用 depset,請參閱「效能」頁面。

API 參考資料

詳情請參閱這篇文章