Depset adalah struktur data khusus untuk mengumpulkan data secara efisien di seluruh dependensi transitif target. Mereka adalah elemen penting dalam pemrosesan aturan.
Fitur utama dari dependensi adalah operasi penggabungan yang hemat waktu dan ruang. Konstruktor dependensi menerima daftar elemen ("langsung") dan daftar dependensi lainnya ("transitif"), serta menampilkan dependensi yang mewakili set yang berisi semua elemen langsung dan gabungan dari semua set transitif. Secara konseptual, konstruktor membuat node grafik baru yang memiliki node langsung dan transitif sebagai penerusnya. Depset memiliki semantik pengurutan yang ditentukan dengan baik, berdasarkan traversal grafik ini.
Contoh penggunaan dependensi 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 executable.
Deskripsi dan operasi
Secara konseptual, dependensi adalah directed acyclic graph (DAG) yang biasanya terlihat mirip dengan grafik target. Hal ini dibangun dari daun hingga akar. Setiap target dalam rantai dependensi dapat menambahkan kontennya sendiri di atas yang sebelumnya tanpa harus membaca atau menyalinnya.
Setiap node dalam DAG menyimpan daftar elemen langsung dan daftar node turunan. Konten dependensi adalah elemen transitif, seperti elemen langsung dari semua node. Depset baru dapat dibuat menggunakan konstruktor depset: dependensi ini 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 dependensi, gunakan metode to_list(). Metode ini menampilkan daftar semua elemen transitif, tidak termasuk duplikat. Tidak ada cara untuk memeriksa struktur akurat DAG 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, begitu juga dengan kunci yang diizinkan dalam kamus yang dibatasi. Secara khusus, konten dependensi mungkin tidak dapat diubah.
Depset menggunakan kesetaraan referensi: dependensi sama dengan dirinya sendiri, tetapi tidak setara dengan dependensi 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 dependensi berdasarkan kontennya, 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 dependensi. Jika diperlukan, Anda harus membaca seluruh konten dependensi, memfilter elemen yang ingin dihapus, dan merekonstruksi dependensi 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 pada DAG. Jenis traversal bergantung pada order yang ditentukan pada saat dependensi dibuat. Bazel dapat mendukung beberapa pesanan karena terkadang
alat memperhatikan urutan inputnya. Misalnya, tindakan penaut mungkin perlu memastikan bahwa jika B bergantung pada A, maka A.o akan ditempatkan sebelum B.o pada command line linker. Alat lainnya mungkin memiliki persyaratan yang sebaliknya.
Tiga urutan traversal didukung: postorder, preorder, dan topological. Dua yang pertama berfungsi persis seperti tree traversal kecuali bahwa keduanya beroperasi pada DAG dan melewati node yang sudah dikunjungi. Urutan ketiga berfungsi sebagai pengurutan topologi dari root hingga daun, pada dasarnya sama dengan praorder kecuali turunan bersama dicantumkan hanya setelah semua induk mereka.
Praorder dan pascaorder 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 dari kiri ke kanan, dan bahkan
jaminan all-parents-before-child tidak berlaku jika ada
elemen duplikat dalam node DAG yang berbeda.
# 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"]
Sehubungan dengan cara penerapan traversal, urutan harus ditentukan pada saat
dependensi dibuat dengan argumen kata kunci order konstruktor. Jika argumen ini
dihapus, dependensi memiliki urutan default khusus, sehingga
tidak ada jaminan urutan elemennya (kecuali jika argumen tersebut
deterministik).
Contoh lengkap
Contoh ini tersedia di https://github.com/bazelbuild/examples/tree/main/rules/depsets.
Misalkan ada bahasa Foo yang diinterpretasikan hipotetis. Untuk mem-build
setiap foo_binary, Anda perlu mengetahui semua file *.foo yang menjadi dependensi langsung atau
tidak langsungnya.
# //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 d biner adalah semua file *.foo di kolom srcs untuk a, b, c, dan d. Agar target foo_binary
mengetahui tentang file selain d.foo, target foo_library harus
meneruskannya di penyedia. Setiap library menerima penyedia dari
dependensinya sendiri, menambahkan sumber langsungnya sendiri, dan meneruskan penyedia baru dengan
konten yang diperkaya. Aturan foo_binary melakukan hal yang sama, tetapi alih-alih menampilkan penyedia, aturan tersebut 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.
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 menggunakan dependensi, pertimbangkan hal 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
Ini tidak memperhitungkan duplikat, sehingga file sumber untuk a
akan muncul dua kali pada command line dan dua kali dalam konten file
output.
Alternatifnya adalah menggunakan kumpulan 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[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 juga konten file) tidak ditentukan, meskipun masih deterministik.
Selain itu, kedua pendekatan tersebut secara asimtotik lebih buruk daripada pendekatan berbasis dependensi. Pertimbangkan kasus ketika ada rantai dependensi panjang pada library Foo. Untuk memproses setiap aturan, Anda harus menyalin semua sumber transitif yang datang sebelumnya ke struktur data baru. Artinya, biaya waktu dan ruang untuk menganalisis setiap library atau target biner sebanding dengan ketinggiannya sendiri dalam rantai. Untuk rantai dengan panjang n, foolib_1 ← foolib_2 ← ... ← foolib_n, biaya keseluruhannya efektif O(n^2).
Secara umum, dependensi harus digunakan setiap kali Anda mengumpulkan informasi melalui dependensi transitif. Hal ini membantu memastikan bahwa build Anda diskalakan dengan baik seiring grafik target Anda semakin dalam.
Terakhir, penting untuk tidak mengambil konten dependensi
yang tidak perlu dalam penerapan aturan. Satu panggilan ke to_list() di akhir aturan biner tidak masalah, karena biaya keseluruhan hanya O(n). Ketika banyak target non-terminal mencoba memanggil to_list(), maka perilaku kuadrat akan terjadi.
Untuk informasi selengkapnya tentang penggunaan dependensi secara efisien, lihat halaman performance.
Referensi API
Lihat di sini untuk detail selengkapnya.