Depset adalah struktur data khusus untuk mengumpulkan data secara efisien di seluruh dependensi transitif target. Elemen tersebut merupakan elemen penting dari pemrosesan aturan.
Fitur yang menentukan depset adalah operasi serikat yang hemat waktu dan ruang. Konstruktor depset menerima daftar elemen ("langsung") dan daftar depset lainnya ("transitif"), dan menampilkan depset yang mewakili kumpulan yang berisi semua elemen langsung dan penyatuan semua kumpulan transitif. Secara konseptual, konstruktor membuat node grafik baru yang memiliki node langsung dan transitif sebagai penerusnya. Depset memiliki semantik pengurutan yang terdefinisi dengan baik, berdasarkan lintasan grafik ini.
Contoh penggunaan depset meliputi:
Menyimpan jalur semua file objek untuk library program, yang kemudian dapat diteruskan ke tindakan penaut melalui penyedia.
Untuk bahasa yang ditafsirkan, menyimpan file sumber transitif yang disertakan dalam runfile file yang dapat dieksekusi.
Deskripsi dan operasi
Secara konseptual, depset merupakan grafik asiklik terarah (DAG) yang biasanya terlihat mirip dengan grafik target. Struktur ini dibuat dari daun hingga root. Setiap target dalam rantai dependensi dapat menambahkan kontennya sendiri selain yang sebelumnya tanpa harus membaca atau menyalinnya.
Setiap node di DAG menyimpan daftar elemen langsung dan daftar node turunan. Konten depset adalah elemen transitif, seperti elemen langsung dari semua node. Depset baru dapat dibuat menggunakan konstruktor depset: menerima daftar elemen langsung dan daftar node turunan lainnya.
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"])
Untuk mengambil konten depset, gunakan metode to_list(). Metode ini menampilkan daftar semua elemen transitif, tidak termasuk duplikat. Anda tidak dapat memeriksa struktur DAG yang akurat secara langsung, meskipun struktur ini memengaruhi urutan elemen yang ditampilkan.
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
Item yang diizinkan dalam dependensi dibatasi, seperti halnya kunci yang diizinkan dalam kamus dibatasi. Secara khusus, konten depset mungkin tidak dapat berubah.
Depset menggunakan kesetaraan referensi: depset sama dengan dirinya sendiri, tetapi tidak sama dengan depset lainnya, meskipun memiliki konten dan struktur internal yang sama.
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
Untuk membandingkan depset berdasarkan kontennya, konversikan menjadi daftar yang diurutkan.
s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list())) # True
Tidak ada kemampuan untuk menghapus elemen dari depset. Jika diperlukan, Anda harus membaca seluruh konten depset, memfilter elemen yang ingin dihapus, dan membuat ulang depset baru. Ini tidak efisien.
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"])
Susunan
Operasi to_list melakukan traversal melalui DAG. Jenis traversal bergantung pada urutan yang ditentukan pada saat depset dibuat. Hal ini berguna bagi Bazel untuk mendukung beberapa pesanan karena terkadang
alat memperhatikan urutan inputnya. Misalnya, tindakan penaut mungkin perlu memastikan bahwa jika B bergantung pada A, A.o akan berada sebelum B.o pada command line penaut. Alat lainnya mungkin memiliki persyaratan yang berlawanan.
Tiga pesanan traversal didukung: postorder, preorder, dan topological. Dua pekerjaan pertama persis seperti lintasan
hierarki
kecuali bahwa keduanya beroperasi di DAG dan melewati node yang sudah dikunjungi. Urutan ketiga
berfungsi sebagai urutan topologi dari root ke daun, yang pada dasarnya sama dengan
praorder, kecuali bahwa turunan bersama hanya dicantumkan setelah semua orang tuanya.
Preorder dan postorder beroperasi sebagai traversal kiri ke kanan, tetapi perhatikan bahwa dalam setiap elemen langsung node tidak ada urutan yang relatif terhadap turunan. Untuk urutan
topologi, tidak ada jaminan kiri-ke-kanan, dan bahkan
jaminan semua-orang tua-sebelum-turunan tidak berlaku jika terdapat
elemen duplikat di berbagai node 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"]
Karena cara traversal diterapkan, urutan harus ditentukan pada saat depset dibuat dengan argumen kata kunci order konstruktor. Jika argumen ini dihilangkan, depset memiliki urutan khusus default, dalam hal ini tidak ada jaminan terkait urutan elemennya (kecuali jika bersifat deterministik).
Contoh lengkap
Contoh ini tersedia di https://github.com/bazelbuild/examples/tree/main/rules/depsets.
Misalnya ada hipotesis bahasa Foo. Untuk mem-build setiap foo_binary, Anda perlu mengetahui semua file *.foo yang menjadi dependensi langsung atau tidak langsung.
# //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())
Di sini, sumber transitif biner d adalah semua file *.foo dalam
kolom srcs pada a, b, c, dan d. Agar target foo_binary mengetahui tentang file apa pun selain d.foo, target foo_library harus meneruskannya dalam penyedia. Setiap library menerima penyedia dari
dependensinya sendiri, menambahkan sumber langsungnya sendiri, dan meneruskan penyedia baru dengan
konten yang ditingkatkan. Aturan foo_binary melakukan hal yang sama, tetapi alih-alih menampilkan penyedia, aturan tersebut menggunakan daftar lengkap sumber untuk membuat command line untuk tindakan.
Berikut adalah implementasi lengkap dari aturan foo_library dan 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"},
)
Anda dapat mengujinya dengan menyalin file ini ke dalam paket baru, mengganti nama
label dengan tepat, membuat file *.foo sumber dengan konten tiruan, dan
mem-build target d.
Performa
Untuk melihat motivasi penggunaan depset, pertimbangkan apa yang akan terjadi jika
get_transitive_srcs() mengumpulkan sumbernya dalam daftar.
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
Hal ini tidak memperhitungkan duplikat, sehingga file sumber untuk a
akan muncul dua kali pada command line dan dua kali di isi file
output.
Alternatifnya adalah menggunakan kumpulan umum, yang dapat disimulasikan oleh kamus dengan kunci yang merupakan elemen dan semua kunci dipetakan ke 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
Tindakan ini akan menghapus duplikat, tetapi membuat urutan argumen command line (dan oleh karena itu konten file) tidak ditentukan, meskipun masih deterministik.
Selain itu, kedua pendekatan tersebut secara asimtotik lebih buruk daripada pendekatan berbasis depset. Pertimbangkan kasus saat ada rantai dependensi yang panjang pada library Foo. Pemrosesan setiap aturan mengharuskan penyalinan semua sumber transitif yang datang sebelum ke struktur data baru. Artinya, biaya waktu dan ruang untuk menganalisis masing-masing library atau target biner sebanding dengan tingginya sendiri dalam rantai. Untuk rantai panjang n, foolib_1 ← foolib_2 ← ... ← foolib_n, biaya keseluruhannya secara efektif adalah O(n^2).
Secara umum, depset harus digunakan setiap kali Anda mengumpulkan informasi melalui dependensi transitif. Hal ini membantu memastikan bahwa build Anda diskalakan dengan baik seiring bertambahnya grafik target.
Terakhir, penting untuk tidak mengambil konten depset
yang tidak perlu dalam penerapan aturan. Satu panggilan ke to_list()
di akhir aturan biner tidak masalah, karena biaya keseluruhannya hanya O(n). Ketika banyak target non-terminal mencoba memanggil to_list(), perilaku kuadrat terjadi.
Untuk mengetahui informasi selengkapnya tentang penggunaan depset secara efisien, lihat halaman performa.
Referensi API
Harap lihat di sini untuk mengetahui detail selengkapnya.