Depsets

รายงานปัญหา ดูแหล่งที่มา

Depsets เป็นโครงสร้างข้อมูลพิเศษสำหรับการรวบรวมข้อมูลในทรัพยากร Depsets ทางอ้อมของเป้าหมายอย่างมีประสิทธิภาพ และเป็นองค์ประกอบสำคัญ ของการประมวลผลกฎ

คุณลักษณะที่กำหนดของ Depset คือการดำเนินการรวมเป็นหนึ่งเดียวอย่างมีประสิทธิภาพด้านเวลาและพื้นที่ว่าง ตัวสร้าง Depset ยอมรับรายการองค์ประกอบ ("โดยตรง") และรายการของ Depsets อื่นๆ ("สกรรมกริยา") และส่งคืน Depset ที่แสดงถึงชุดที่มีองค์ประกอบโดยตรงทั้งหมดและการรวมชุดสกรรมกริยาทั้งหมด โดยหลักการแล้ว ตัวสร้างจะสร้างโหนดกราฟใหม่ที่มีโหนดโดยตรงและโหนดส่งต่อเป็นลำดับสืบเนื่อง ค่ามีความหมายในการเรียงลำดับที่กำหนดไว้เป็นอย่างดี โดยอิงตามการส่งผ่านของกราฟนี้

ตัวอย่างการใช้งาน Depsets ได้แก่

  • การจัดเก็บเส้นทางของไฟล์ออบเจ็กต์ทั้งหมดสำหรับไลบรารีของโปรแกรม ซึ่งจะส่งไปยังการดำเนินการของ Linker ผ่านผู้ให้บริการได้

  • สำหรับภาษาที่แปลโดยอินเตอร์พรีเตอร์ จะเป็นการจัดเก็บไฟล์ต้นฉบับทางอ้อมที่รวมอยู่ใน Runfile ของไฟล์ปฏิบัติการ

คำอธิบายและการดำเนินการ

โดยหลักการแล้ว Depset คือกราฟแบบวนซ้ำที่มีทิศทาง (DAG) ซึ่งโดยทั่วไปแล้วจะมีหน้าตาคล้ายกับกราฟเป้าหมาย สร้างขึ้นจากใบไปถึงราก เป้าหมายแต่ละรายการในเชนทรัพยากร Dependency เพิ่มเนื้อหาของตนเองทับเนื้อหาก่อนหน้านี้ได้โดยไม่ต้องอ่านหรือคัดลอก

แต่ละโหนดใน DAG จะมีรายการองค์ประกอบโดยตรงและรายการโหนดย่อย เนื้อหาของดีพเซ็ตคือองค์ประกอบสับเปลี่ยน เช่น องค์ประกอบโดยตรงของโหนดทั้งหมด คุณสร้างดีเซตใหม่ได้โดยใช้ตัวสร้าง 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 จะไม่สามารถเปลี่ยนแปลงได้

Depsets ใช้ความเท่ากันของการอ้างอิง โดย 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 งานแรกเหมือนกับการข้ามผ่านต้นไม้ทุกประการ ยกเว้นว่าทำงานกับ DAG และข้ามโหนดที่เข้าชมแล้ว ลำดับที่ 3 เป็นการจัดเรียงแบบโทโพโลยีจากรากถึงใบ โดยพื้นฐานแล้วจะเหมือนกับสั่งซื้อล่วงหน้า เว้นแต่ว่าเด็กที่แชร์จะแสดงหลังจากผู้ปกครองทั้งหมดเท่านั้น Preorder และ Postorder ทำงานเป็นแบบข้ามผ่านจากซ้ายไปขวา แต่โปรดทราบว่าในองค์ประกอบโดยตรงของโหนดแต่ละองค์ประกอบไม่มีลำดับที่สัมพันธ์กับรายการย่อย สำหรับลำดับแบบลำดับชั้นจะไม่มีการรับประกันจากซ้ายไปขวา และแม้แต่การรับประกันจากผู้ปกครองทั้งหมดก่อนเด็กก็จะไม่มีผลในกรณีที่มีองค์ประกอบซ้ำกันในโหนดต่างๆ ของ 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 จะมีคำสั่ง 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 จะต้องส่งต่อไฟล์ดังกล่าวในผู้ให้บริการ ห้องสมุดแต่ละแห่งจะได้รับผู้ให้บริการจากการขึ้นต่อกันของตัวเอง เพิ่มแหล่งที่มาของตนเองในทันที และส่งต่อผู้ให้บริการใหม่ด้วยเนื้อหาเพิ่มเติม กฎ 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 แนวทางนี้ยังแย่กว่าวิธีการที่อิงตามการลดลงอย่างเห็นได้ชัด ลองพิจารณากรณีที่มีการพึ่งพิงกันอย่างยาวนานในไลบรารี Foo การประมวลผลทุกกฎต้องมีการคัดลอกแหล่งที่มาแบบสับเปลี่ยนทั้งหมดก่อนหน้าที่มาก่อนลงในโครงสร้างข้อมูลใหม่ ซึ่งหมายความว่าต้นทุนด้านเวลาและพื้นที่ในการวิเคราะห์ไลบรารีหรือเป้าหมายไบนารีแต่ละรายการจะเป็นสัดส่วนกับความสูงของแต่ละไลบรารีในห่วงโซ่ สำหรับห่วงโซ่ความยาว n, foolib_1 ← foolib_2 ← ... ← foolib_n ต้นทุนโดยรวมจะเป็น O(n^2)

โดยทั่วไปแล้ว คุณควรใช้ Depsets ทุกครั้งที่รวบรวมข้อมูลผ่านทรัพยากร Dependency แบบสกรรม วิธีนี้ช่วยให้มั่นใจได้ว่างานสร้างจะปรับขนาดและกราฟเป้าหมายขยายใหญ่ขึ้น

และสุดท้าย ต้องไม่ดึงเนื้อหาของ Depset โดยไม่จำเป็นในการใช้งานกฎ การเรียกใช้ to_list() ในตอนท้ายของกฎเลขฐานสองถือว่าใช้ได้ เนื่องจากต้นทุนโดยรวมคือ O(n) เกิดขึ้นเมื่อเป้าหมายที่ไม่ใช่เทอร์มินัลจำนวนมากพยายามเรียกใช้ to_list() ซึ่งจะมีลักษณะการทำงานแบบกำลังสองเกิดขึ้น

ดูข้อมูลเพิ่มเติมเกี่ยวกับการใช้การลดระดับอย่างมีประสิทธิภาพได้ที่หน้าประสิทธิภาพ

เอกสารอ้างอิง API

โปรดดูรายละเอียดเพิ่มเติมที่นี่