Depset เป็นโครงสร้างข้อมูลแบบพิเศษเพื่อการรวบรวมข้อมูลอย่างมีประสิทธิภาพในทรัพยากร Dependency แบบทรานซิทีฟของเป้าหมาย ซึ่งเป็นองค์ประกอบสำคัญของ การประมวลผลกฎ
คุณลักษณะเด่นของ Depset คือการใช้งานสหภาพประหยัดพื้นที่และเวลา ตัวสร้าง Depset ยอมรับรายการองค์ประกอบ ("โดยตรง") และรายการของ Depset อื่นๆ ("สกรรมกราย") และแสดงผล Depset ที่แสดงถึงชุดที่มีเอลิเมนต์โดยตรงทั้งหมดและการรวมของชุดทางอ้อมทั้งหมด โดยหลักการแล้ว ตัวสร้างจะสร้างโหนดกราฟใหม่ที่มีโหนดโดยตรงและโหนดทรานซิทีฟเป็นตัวสืบทอด Depset มีการเรียงลำดับความหมายที่กำหนดไว้แล้ว โดยอิงตามการข้ามผ่านของกราฟนี้
ตัวอย่างการใช้ Depsets ได้แก่
การจัดเก็บเส้นทางของไฟล์ออบเจ็กต์ทั้งหมดสำหรับไลบรารีของโปรแกรม ซึ่งจะส่งผ่านไปยังการดำเนินการของ Linker ผ่านผู้ให้บริการได้
สำหรับภาษาที่แปลโดยอินเทอร์พรีเตอร์ ให้จัดเก็บไฟล์ต้นทางทรานซิทีฟที่รวมอยู่ในไฟล์การเรียกใช้ไฟล์ปฏิบัติการ
คำอธิบายและการดำเนินการ
โดยหลักการแล้ว กราฟ Depset จะเป็นกราฟแบบอินไซเคิลที่มีทิศทางโดยตรง (DAG) ซึ่งโดยทั่วไปจะมีลักษณะคล้ายกับกราฟเป้าหมาย สร้างขึ้นจากใบไปจนถึงราก เป้าหมายแต่ละรายการในสายทรัพยากร Dependency จะเพิ่มเนื้อหาของตนเองซ้อนทับเป้าหมายก่อนหน้าได้โดยไม่ต้องอ่านหรือคัดลอกเนื้อหา
แต่ละโหนดใน 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 จะเท่ากับตัวมันเอง แต่ไม่เท่ากับค่าเดี่ยวอื่นๆ แม้ว่าจะมีเนื้อหาและโครงสร้างภายในเหมือนกันก็ตาม
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 กรององค์ประกอบที่ต้องการนำออก และสร้าง 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 ในการรองรับคำสั่งซื้อหลายรายการเพราะบางครั้งเครื่องมือจะดูแลลำดับอินพุต เช่น การดำเนินการ Linker อาจต้องตรวจสอบว่าหาก B ใช้ A แล้ว A.o จะต้องมาก่อน B.o ในบรรทัดคำสั่งของ Linker เครื่องมืออื่นๆ อาจมีความต้องการในทางตรงกันข้าม
รองรับคำสั่งซื้อแบบข้ามผ่าน 3 ลำดับ ได้แก่ postorder, preorder และ topological 2 รายการแรกนั้นทำงานเหมือนกับ Tree Traversal ทุกประการ เว้นแต่ว่าจะทำงานบน 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"]
เนื่องจากวิธีใช้การข้ามผ่าน ลำดับต้องระบุ ณ เวลาที่สร้าง Depset ด้วยอาร์กิวเมนต์คีย์เวิร์ด 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 ทั้งหมดในช่อง srcs ของ a, b, c และ d เพื่อให้เป้าหมาย foo_binary ทราบเกี่ยวกับไฟล์อื่นนอกเหนือจาก d.foo เป้าหมาย foo_library จะต้องส่งผ่านไฟล์ดังกล่าวในผู้ให้บริการ ห้องสมุดแต่ละแห่งจะรับผู้ให้บริการจากทรัพยากร Dependency ของตนเอง เพิ่มแหล่งที่มาโดยตรงของตนเอง และส่งต่อผู้ให้บริการรายใหม่ที่มีเนื้อหาเสริม กฎ 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
การดำเนินการนี้จะลบไฟล์ที่ซ้ำกัน แต่จะทำให้ระบุลำดับของอาร์กิวเมนต์บรรทัดคำสั่ง (รวมถึงเนื้อหาของไฟล์) ไม่ได้ แม้ว่าจะมีการกำหนด URL ก็ตาม
ยิ่งไปกว่านั้น ทั้ง 2 แนวทางนี้แย่กว่าวิธีการจัดการแบบไม่เป็นผล ลองพิจารณากรณีที่มีห่วงโซ่ทรัพยากร Dependency ยาวๆ ในไลบรารี Foo การประมวลผลกฎทุกกฎต้องมีการคัดลอกแหล่งที่มาทรานซิชันทั้งหมดที่อยู่ก่อนหน้าไปยังโครงสร้างข้อมูลใหม่ ซึ่งหมายความว่าเวลาและค่าใช้จ่ายด้านพื้นที่สำหรับการวิเคราะห์ไลบรารีหรือเป้าหมายไบนารีแต่ละรายการจะเป็นสัดส่วนกับความสูงในเชนของตัวเอง สำหรับห่วงโซ่ความยาว n foolib_1 ← foolib_2 ← ... ← foolib_n ต้นทุนโดยรวมคือ O(n^2)
โดยทั่วไปแล้ว ควรใช้ Depsets เมื่อใดก็ตามที่คุณสะสมข้อมูลผ่านทรัพยากร Dependency แบบทรานซิชัน ซึ่งจะช่วยให้มั่นใจว่าการสร้างของคุณปรับขนาดและกราฟเป้าหมายมีขนาดใหญ่ขึ้น
สุดท้าย คุณต้องไม่เรียกเนื้อหาของค่ากำหนดโดยไม่จำเป็นในการใช้งานกฎ การเรียก to_list() ในตอนท้ายของกฎไบนารีถือว่าใช้ได้ เนื่องจากค่าใช้จ่ายโดยรวมมีเพียง O(n) เกิดขึ้นเมื่อเป้าหมายที่ไม่ใช่เทอร์มินัลหลายรายการพยายามเรียก to_list() ซึ่งเกิดขึ้น
ดูข้อมูลเพิ่มเติมเกี่ยวกับการใช้การแยกได้อย่างมีประสิทธิภาพในหน้าประสิทธิภาพ
เอกสารอ้างอิง API
โปรดดูรายละเอียดเพิ่มเติมที่นี่