Depset adalah struktur data khusus untuk mengumpulkan data secara efisien di seluruh dependensi transitif target. Mereka adalah elemen penting dalam pemrosesan aturan.
Fitur utama depset adalah operasi gabungannya yang efisien dalam waktu dan ruang. Konstruktor depset menerima daftar elemen ("langsung") dan daftar depset lainnya ("transitif"), serta menampilkan depset yang merepresentasikan set yang berisi semua elemen langsung dan gabungan semua set 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 traversal grafik ini.
Contoh penggunaan depset meliputi:
Menyimpan jalur semua file objek untuk library program, yang kemudian dapat diteruskan ke tindakan linker melalui penyedia.
Untuk bahasa yang ditafsirkan, menyimpan file sumber transitif yang disertakan dalam file runfile yang dapat dieksekusi.
Deskripsi dan operasi
Secara konseptual, depset adalah directed acyclic graph (DAG) yang biasanya terlihat mirip dengan target graph. Objek ini dibuat dari daun hingga root. Setiap target dalam rantai dependensi dapat menambahkan kontennya sendiri di atas target sebelumnya tanpa harus membaca atau menyalinnya.
Setiap node dalam DAG menyimpan daftar elemen langsung dan daftar node turunan. Isi depset adalah elemen transitif, seperti elemen langsung dari semua node. Kumpulan depset baru dapat dibuat menggunakan konstruktor depset: konstruktor ini menerima daftar elemen langsung dan daftar lain dari node turunan.
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(). Tindakan ini menampilkan daftar semua elemen transitif, tidak termasuk duplikat. Tidak ada cara untuk memeriksa secara langsung struktur DAG yang tepat, 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 depset dibatasi, sama seperti kunci yang diizinkan dalam kamus dibatasi. Secara khusus, konten depset mungkin tidak dapat diubah.
Depset menggunakan persamaan referensi: depset sama dengan dirinya sendiri, tetapi tidak sama dengan depset lain, 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 isinya, konversikan ke 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 merekonstruksi depset baru. Hal ini tidak terlalu 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"])
Pesan
Operasi to_list melakukan traversal melalui DAG. Jenis penelusuran
bergantung pada urutan yang ditentukan pada saat depset
dibuat. Bazel mendukung beberapa urutan karena terkadang alat memperhatikan urutan inputnya. Misalnya, tindakan linker mungkin
perlu memastikan bahwa jika B bergantung pada A, maka A.o berada sebelum B.o di
command line linker. Alat lain mungkin memiliki persyaratan yang berlawanan.
Tiga urutan penelusuran didukung: postorder, preorder, dan
topological. Dua yang pertama berfungsi persis seperti penelusuran
pohon
kecuali bahwa keduanya beroperasi pada DAG dan melewati node yang sudah dikunjungi. Urutan ketiga
berfungsi sebagai pengurutan topologi dari root ke leaf, pada dasarnya sama dengan
preorder, kecuali bahwa turunan bersama hanya dicantumkan setelah semua induknya.
Preorder dan postorder beroperasi sebagai traversal kiri-ke-kanan, tetapi perhatikan bahwa dalam setiap elemen langsung node tidak memiliki urutan relatif terhadap turunan. Untuk urutan
topologi, tidak ada jaminan kiri-ke-kanan, dan bahkan jaminan
semua induk sebelum turunan tidak berlaku jika ada
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 penerapan traversal, urutan harus ditentukan pada saat
depset dibuat dengan argumen kata kunci order konstruktor. Jika argumen ini tidak disertakan, depset memiliki urutan default khusus, yang dalam hal ini tidak ada jaminan tentang urutan elemennya (kecuali bahwa urutannya deterministik).
Contoh lengkap
Contoh ini tersedia di https://github.com/bazelbuild/examples/tree/main/rules/depsets.
Misalkan ada bahasa Foo yang ditafsirkan secara hipotetis. Untuk membuat
setiap foo_binary, Anda perlu mengetahui semua file *.foo yang secara langsung atau
tidak langsung menjadi dependensinya.
# //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 di
kolom srcs dari a, b, c, dan d. Agar target foo_binary
mengetahui file 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 telah di-augmentasi. Aturan foo_binary melakukan hal yang sama, kecuali bahwa alih-alih menampilkan penyedia, aturan ini menggunakan daftar lengkap sumber untuk membuat command line untuk suatu tindakan.
Berikut adalah implementasi lengkap aturan foo_library dan 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"},
)
Anda dapat mengujinya dengan menyalin file ini ke dalam paket baru, mengganti nama
label dengan tepat, membuat file sumber *.foo dengan konten dummy, dan
membangun target d.
Performa
Untuk melihat motivasi penggunaan depsets, 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[foo_files].transitive_sources
trans_srcs += srcs
return trans_srcs
Hal ini tidak memperhitungkan duplikat, sehingga file sumber untuk a
akan muncul dua kali di command line dan dua kali dalam isi file
output.
Alternatifnya adalah menggunakan set umum, yang dapat disimulasikan oleh
kamus dengan kunci adalah elemen dan semua kunci dipetakan ke 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
Hal ini akan menghapus duplikat, tetapi membuat urutan argumen command line (dan oleh karena itu, isi file) tidak ditentukan, meskipun masih deterministik.
Selain itu, kedua pendekatan ini secara asimtotik lebih buruk daripada pendekatan berbasis depset. Pertimbangkan kasus saat ada rantai panjang dependensi pada library Foo. Memproses setiap aturan memerlukan penyalinan semua sumber transitif yang mendahuluinya ke dalam struktur data baru. Artinya, biaya waktu dan ruang untuk menganalisis target biner atau library individual 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, depsets harus digunakan setiap kali Anda mengumpulkan informasi melalui dependensi transitif. Hal ini membantu memastikan bahwa build Anda diskalakan dengan baik saat grafik target Anda bertambah dalam.
Terakhir, penting untuk tidak mengambil konten depset
secara tidak perlu dalam penerapan aturan. Satu panggilan ke to_list()
di akhir dalam aturan biner tidak masalah, karena biaya keseluruhannya hanya O(n). Perilaku kuadrat terjadi saat banyak target non-terminal mencoba memanggil to_list().
Untuk mengetahui informasi selengkapnya tentang penggunaan depsets secara efisien, lihat halaman performa.
Referensi API
Lihat di sini untuk mengetahui detail selengkapnya.