Depsets เป็นโครงสร้างข้อมูลเฉพาะเพื่อ รวบรวมข้อมูลในทรัพยากร 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 มีค่าเท่ากับตัวเอง แต่ไม่เท่ากับ อื่นๆ แม้ว่าจะมีเนื้อหาและโครงสร้างภายในเหมือนกันก็ตาม
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 ประเภทการส่งผ่าน
ขึ้นอยู่กับ order ที่ระบุไว้ในเวลาที่ Depset คือ
ขึ้น มีประโยชน์สำหรับ Bazel ในการรองรับคำสั่งซื้อหลายรายการ เนื่องจากบางครั้ง
ให้ความสำคัญกับลำดับอินพุต ตัวอย่างเช่น การดำเนินการ Linker อาจ
ต้องตรวจสอบว่า B ขึ้นอยู่กับ A หรือไม่ A.o จะต้องมาก่อน B.o ใน
บรรทัดคำสั่งของ Linker เครื่องมืออื่นๆ อาจมีความต้องการในทางตรงกันข้าม
รองรับลำดับการส่งผ่าน 3 ลำดับ ได้แก่ 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"]
เนื่องจากวิธีใช้การข้ามผ่าน จึงต้องระบุลำดับ ณ เวลา
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
ซึ่งจะเป็นการนำรายการซ้ำออกไป แต่จะจัดลำดับของบรรทัดคำสั่ง อาร์กิวเมนต์ (และเนื้อหาของไฟล์) ไม่ได้ระบุ แม้ว่าจะยัง เชิงกำหนด
ยิ่งไปกว่านั้น ทั้ง 2 แนวทางนี้แย่กว่าแบบอิงตาม Depset ของเรา พิจารณากรณีที่มีห่วงโซ่ของทรัพยากร Dependency ยาว ห้องสมุด Foo การประมวลผลกฎทุกกฎต้องมีการคัดลอกทรานซิทีฟทั้งหมด ที่มามาก่อนโครงสร้างข้อมูลใหม่ ซึ่งหมายความว่า ต้นทุนด้านเวลาและพื้นที่สําหรับการวิเคราะห์ไลบรารีหรือเป้าหมายไบนารีแต่ละรายการ จะเป็นสัดส่วนกับความสูงของตัวเองในห่วงโซ่ สำหรับห่วงโซ่ความยาว n foolib_1 ← foolib_2 ← ... ← foolib_n ต้นทุนโดยรวมคือ O(n^2) ได้อย่างมีประสิทธิภาพ
กล่าวโดยทั่วไปคือ ควรใช้ช่วงเวลาในการสะสม ผ่านทรัพยากร Dependency แบบสับเปลี่ยน วิธีนี้ช่วยให้มั่นใจได้ว่า งานสร้างของคุณปรับขนาดได้ และกราฟเป้าหมายก็ขยายลึกขึ้น
สุดท้ายนี้ สิ่งสำคัญคือคุณไม่ควรเรียกเนื้อหาของค่ากำหนด
ในการใช้งานกฎโดยไม่จำเป็น โทรหา to_list() 1 ครั้ง
ต่อท้ายในกฎไบนารีได้ดี เนื่องจากต้นทุนโดยรวมมีเพียง O(n) เวลา
เมื่อเป้าหมายที่ไม่ใช่เทอร์มินัลจำนวนมากพยายามเรียก to_list() ว่าพฤติกรรมกำลังสอง
เกิดขึ้น
ดูข้อมูลเพิ่มเติมเกี่ยวกับการใช้การแยกได้อย่างมีประสิทธิภาพในหน้าประสิทธิภาพ
เอกสารอ้างอิง API
โปรดดูรายละเอียดเพิ่มเติมที่นี่