Depset เป็นโครงสร้างข้อมูลเฉพาะสำหรับการรวบรวมข้อมูลอย่างมีประสิทธิภาพ ในทรัพยากร Dependency แบบทรานซิทีฟของเป้าหมาย ซึ่งเป็นองค์ประกอบสำคัญ ของการประมวลผลกฎ
ฟีเจอร์ที่สำคัญของ Depset คือการดำเนินการรวมที่มีประสิทธิภาพด้านเวลาและพื้นที่ ตัวสร้าง depset จะยอมรับรายการองค์ประกอบ ("โดยตรง") และรายการ depset อื่นๆ ("ทรานซิทีฟ") และจะแสดงผล depset ที่แสดงถึงชุดที่มีองค์ประกอบโดยตรงทั้งหมดและการรวมชุดทรานซิทีฟทั้งหมด ในเชิงแนวคิด คอนสตรัคเตอร์จะสร้างโหนดกราฟใหม่ที่มีโหนดโดยตรงและโหนดแบบทรานซิทีฟ เป็นโหนดที่ต่อจากโหนดนั้น Depset มีตรรกะการจัดลำดับที่กำหนดไว้อย่างดีโดยอิงตาม การข้ามกราฟนี้
ตัวอย่างการใช้งานชุดทรัพยากรมีดังนี้
จัดเก็บเส้นทางของไฟล์ออบเจ็กต์ทั้งหมดสำหรับไลบรารีของโปรแกรม ซึ่งสามารถ ส่งไปยังการดำเนินการของ Linker ผ่านผู้ให้บริการได้
สำหรับภาษาที่ตีความ การจัดเก็บไฟล์ต้นฉบับแบบทรานซิทีฟที่ รวมอยู่ในไฟล์รันของไฟล์ปฏิบัติการ
คำอธิบายและการดำเนินการ
ในเชิงแนวคิดแล้ว Depset คือ Directed Acyclic Graph (DAG) ที่มักจะมีลักษณะ คล้ายกับกราฟเป้าหมาย โดยสร้างจากใบไม้ไปจนถึงราก แต่ละเป้าหมายในห่วงโซ่การพึ่งพาสามารถเพิ่มเนื้อหาของตัวเองไว้ด้านบนของเป้าหมายก่อนหน้าได้โดยไม่ต้องอ่านหรือคัดลอก
แต่ละโหนดใน DAG จะมีรายการขององค์ประกอบโดยตรงและรายการของโหนดย่อย เนื้อหาของชุดการขึ้นต่อกันคือองค์ประกอบแบบทรานซิทีฟ เช่น องค์ประกอบโดยตรง ของโหนดทั้งหมด คุณสร้าง 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 อื่น แม้ว่าจะมีเนื้อหาและโครงสร้างภายในเหมือนกันก็ตาม
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 ประเภทการข้าม
ขึ้นอยู่กับลำดับที่ระบุไว้ในขณะที่สร้างชุดการอ้างอิง
Bazel ควรรองรับลำดับหลายรายการเนื่องจากบางครั้งเครื่องมือต่างๆ
จะสนใจลำดับของอินพุต ตัวอย่างเช่น การดำเนินการของ Linker อาจต้องตรวจสอบว่าหาก B ขึ้นอยู่กับ A แล้ว A.o จะต้องอยู่ก่อน B.o ในบรรทัดคำสั่งของ Linker
เครื่องมืออื่นๆ อาจมีข้อกำหนดที่ตรงกันข้าม
ระบบรองรับลำดับการข้าม 3 แบบ ได้แก่ postorder, preorder และ
topological โดย 2 วิธีแรกจะทำงานเหมือนการสำรวจแบบต้นไม้
ทุกประการ เพียงแต่จะทำงานบน 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 ของตัวสร้าง หากละเว้นอาร์กิวเมนต์นี้ ชุดทรัพยากร Dependency จะมีลำดับ default พิเศษ ในกรณีนี้จะไม่มีการรับประกันเกี่ยวกับลำดับขององค์ประกอบใดๆ (ยกเว้นว่าจะเป็นแบบกำหนด)
ตัวอย่างแบบเต็ม
ตัวอย่างนี้มีอยู่ที่ https://github.com/bazelbuild/examples/tree/main/rules/depsets
สมมติว่ามีภาษาที่แปลโดยอินเทอร์พรีเตอร์สมมติชื่อ Foo หากต้องการสร้างfoo_binaryแต่ละรายการ คุณต้องทราบไฟล์*.fooทั้งหมดที่foo_binaryนั้นๆ ต้องใช้โดยตรงหรือโดยอ้อม
# //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 จะต้อง
ส่งต่อไฟล์เหล่านั้นในผู้ให้บริการ โดยแต่ละไลบรารีจะรับผู้ให้บริการจาก
การอ้างอิงของตัวเอง เพิ่มแหล่งที่มาของตัวเอง และส่งต่อผู้ให้บริการใหม่พร้อม
เนื้อหาที่เพิ่ม foo_binary กฎจะทําเช่นเดียวกัน แต่จะใช้รายการแหล่งที่มาทั้งหมดเพื่อสร้าง
บรรทัดคําสั่งสําหรับการกระทําแทนที่จะแสดงผู้ให้บริการ
ต่อไปนี้คือการใช้งานกฎ foo_library และ foo_binary อย่างสมบูรณ์
# //depsets/foo.bzl
# A provider with one field, transitive_sources.
foo_files = 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[foo_files].transitive_sources for dep in deps])
def _foo_library_impl(ctx):
trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
return [foo_files(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[foo_files].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[foo_files].transitive_sources:
trans_srcs[file] = True
for file in srcs:
trans_srcs[file] = True
return trans_srcs
ซึ่งจะช่วยกำจัดรายการที่ซ้ำกัน แต่จะทำให้ลำดับของอาร์กิวเมนต์ในบรรทัดคำสั่ง (และเนื้อหาของไฟล์) ไม่ได้ระบุไว้ แม้ว่ายังคง กำหนดได้ก็ตาม
นอกจากนี้ ทั้ง 2 วิธีนี้ยังแย่กว่าวิธีที่ใช้ชุดการพึ่งพา แบบไม่จำกัด พิจารณากรณีที่มีการขึ้นต่อกันเป็นลูกโซ่ยาวกับไลบรารี Foo การประมวลผลทุกกฎต้องมีการคัดลอกแหล่งที่มาแบบทรานซิทีฟทั้งหมดที่อยู่ก่อนหน้ากฎนั้นลงในโครงสร้างข้อมูลใหม่ ซึ่งหมายความว่าต้นทุนด้านเวลาและพื้นที่สําหรับการวิเคราะห์ไลบรารีหรือเป้าหมายไบนารีแต่ละรายการ จะแปรผันตามความสูงของไลบรารีหรือเป้าหมายไบนารีนั้นๆ ในห่วงโซ่ สำหรับเชนที่มีความยาว n, foolib_1 ← foolib_2 ← … ← foolib_n ค่าใช้จ่ายโดยรวมจะอยู่ที่ O(n^2)
โดยทั่วไปแล้ว คุณควรใช้ชุดการพึ่งพาเมื่อใดก็ตามที่สะสมข้อมูลผ่านการพึ่งพาแบบทรานซิทีฟ ซึ่งจะช่วยให้มั่นใจได้ว่าบิลด์ของคุณจะปรับขนาดได้ดีเมื่อกราฟเป้าหมายมีขนาดใหญ่ขึ้น
สุดท้ายนี้ สิ่งสำคัญคืออย่าดึงเนื้อหาของ depset
โดยไม่จำเป็นในการใช้งานกฎ การเรียกใช้ฟังก์ชัน to_list()
ที่ส่วนท้ายในกฎไบนารีก็ใช้ได้ เนื่องจากต้นทุนโดยรวมเป็นเพียง O(n) โดยจะเกิดขึ้นเมื่อเป้าหมายที่ไม่ใช่เทอร์มินัลจำนวนมากพยายามเรียกใช้ to_list() ซึ่งทำให้เกิดลักษณะการทำงานแบบกำลังสอง
ดูข้อมูลเพิ่มเติมเกี่ยวกับการใช้ชุดทรัพยากรอย่างมีประสิทธิภาพได้ที่หน้าประสิทธิภาพ
เอกสารอ้างอิง API
โปรดดูรายละเอียดเพิ่มเติมที่นี่