Depset 是特殊的資料結構,用於有效率地收集目標的遞移依附元件中的資料。是規則處理中不可或缺的元素
depset 的定義功能是它兼具時間和空間的聯集作業。depset 建構函式接受元素清單 (「direct」) 和其他依附元件清單 (「遞移」),並傳回代表集合,其中含有所有直接元素和所有遞移集的聯集。從概念上來說,建構函式會建立新的圖形節點,並將直接和遞移節點做為後續節點。依據這張圖表的遍歷,定義會具有定義明確的排序語意。
解碼器的使用範例包括:
儲存程式程式庫的所有物件檔案路徑,隨後即可透過供應器傳遞至連結器動作。
如為解譯語言,儲存包含在執行檔的執行檔案中的遞移來源檔案。
說明與作業
從概念上來說,偏移值是有向非循環圖 (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 使用參照相等:解碼器等於本身,但其他依附元件不等同,即使兩者的內容和內部結構都相同。
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。這樣就沒有效率。
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 執行週遊。週遊的種類取決於建構模式時指定的 order。這對 Bazel 來說非常實用,因為有時工具需要重視輸入的順序。舉例來說,連結器動作可能需要確保如果 B
依附 A
,那麼 A.o
要位於連結器指令列的 B.o
之前。其他工具則可能有相反需求。
系統支援三種週遊訂單:postorder
、preorder
和 topological
。前兩個工作與樹木週遊完全相同,只是前者在 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
關鍵字引數指定順序。如果省略這個引數,表示集合會有特殊的 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
的來源檔案會在指令列中出現兩次,並在輸出檔案的內容中顯示兩次。
另一種方法是使用一般集合,可透過字典模擬,其中鍵為元素,且所有按鍵都對應至 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()
呼叫可以執行,因為整體成本只有 O(n)。會有許多非終端目標嘗試呼叫 to_list()
,以便發生二次行為。
如要進一步瞭解如何有效使用解碼器,請參閱效能頁面。
API 參考資料
詳情請參閱這裡。