Depset

Laporkan masalahopen_in_new Lihat sumberopen_in_new Per Malam · 7,3 · 7,2 · 7,1 · 7,0 · 6,5

Depset adalah struktur data khusus untuk mengumpulkan data di seluruh dependensi transitif target. Prototipe fidelitas rendah dari pemrosesan aturan.

Fitur penentu depset adalah operasi union yang hemat waktu dan ruang. Konstruktor depset menerima daftar elemen ("direct") dan daftar elemen lain depset ("transitif"), dan menampilkan depset yang mewakili satu set yang berisi semua elemen langsung dan penyatuan dari semua himpunan transitif. Secara konseptual, membuat simpul grafik baru yang memiliki simpul 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 dapat kemudian diteruskan ke tindakan penaut melalui penyedia.

• Untuk bahasa pemrograman tafsiran, menyimpan file sumber transitif yang termasuk dalam {i> runfile<i} yang dapat dieksekusi.

Deskripsi dan operasi

Secara konseptual, depset adalah {i>direct acyclic graph<i} (DAG) yang biasanya terlihat mirip dengan target grafik. Tersusun mulai dari daun hingga ke akar. Setiap target dalam rantai dependensi dapat menambahkan kontennya sendiri ke sebelumnya tanpa harus membaca atau menyalinnya.

Setiap node di DAG menyimpan daftar elemen langsung dan daftar node turunan. Isi depset adalah elemen transitif, seperti elemen langsung dari semua node. Depset baru dapat dibuat menggunakan depset: konstruktor menerima daftar langsung dan daftar lain dari simpul anak.

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 isi depset, gunakan metode to_list(). Metode ini mengembalikan daftar semua lain, tidak termasuk duplikasi. Tidak ada cara untuk memeriksa secara langsung DAG yang lebih akurat, meskipun struktur ini mempengaruhi 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 di kamus dibatasi. Khususnya, konten hasil depset mungkin tidak dapat berubah.

Depset menggunakan kesetaraan referensi: depset sama dengan dirinya sendiri, tetapi tidak sama dengan depset lain, meskipun memiliki isi 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 depset 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 isi depset, memfilter elemen yang ingin Anda menghapus, 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 traversal bergantung pada urutan yang ditentukan pada saat depset dibuat. Hal ini berguna bagi Bazel untuk mendukung banyak pesanan karena terkadang {i>tool<i} peduli dengan urutan {i>input<i} mereka. Misalnya, tindakan penaut dapat perlu memastikan bahwa jika B bergantung pada A, maka A.o harus ditempatkan sebelum B.o pada command line linker. Alat lainnya mungkin memiliki persyaratan yang berlawanan.

Tiga urutan traversal didukung: postorder, preorder, dan topological. Dua yang pertama berfungsi sama seperti pohon traversal kecuali bahwa node tersebut beroperasi di DAG dan melewati node yang sudah dikunjungi. Urutan ketiga berfungsi sebagai urutan topologis dari akar ke daun, pada dasarnya sama dengan praorder kecuali bahwa turunan bersama hanya tercantum setelah semua orang tuanya. Praorder dan postorder beroperasi sebagai traversal kiri-ke-kanan, tetapi perhatikan bahwa dalam setiap elemen langsung node tidak memiliki urutan relatif terhadap turunan. Untuk topologi urutannya, tidak ada jaminan dari kiri-ke-kanan, dan bahkan jaminan {i>all-parents-before-child<i} tidak berlaku jika elemen duplikat di 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"]

Karena cara penerapan traversal, urutan harus ditentukan pada saat depset dibuat dengan argumen kata kunci order konstruktor. Jika ini dihilangkan, depset memiliki urutan default khusus, dalam hal ini tidak ada jaminan tentang urutan setiap elemennya (kecuali jika bersifat determenistik).

Contoh lengkap

Contoh ini tersedia di https://github.com/bazelbuild/examples/tree/main/rules/depsets.

Misalkan ada bahasa tafsiran hipotetis Foo. Untuk membangun setiap foo_binary, Anda perlu mengetahui semua file *.foo yang secara langsung atau bergantung secara 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 d biner adalah semua file *.foo di kolom srcs dari a, b, c, dan d. Agar foo_binary target untuk mengetahui tentang file apa pun selain d.foo, target foo_library harus meneruskannya dalam penyedia. Setiap library menerima penyedia dari dependensi, menambahkan sumber langsungnya sendiri, dan meneruskan penyedia baru dengan konten yang telah ditingkatkan. Aturan foo_binary melakukan hal yang sama, hanya saja sebagai gantinya untuk mengembalikan penyedia, ia menggunakan daftar lengkap sumber untuk menyusun baris perintah untuk sebuah tindakan.

Berikut adalah penerapan 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-file ini ke dalam paket baru, dengan mengganti nama label dengan tepat, membuat file *.foo sumber dengan konten contoh, dan membangun target d.

Performa

Untuk melihat motivasi dalam menggunakan {i>depset<i}, 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

Ini tidak memperhitungkan duplikat, sehingga file sumber untuk a akan muncul dua kali pada baris perintah dan dua kali di isi {i>output<i} .

Alternatifnya adalah menggunakan seperangkat umum, yang dapat disimulasikan oleh kamus dengan kunci sebagai 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

Ini menghilangkan duplikasi, tetapi membuat urutan baris perintah argumen (dan karenanya isi file) tidak ditentukan, meskipun determenistik.

Terlebih lagi, kedua pendekatan tersebut secara asimtot lebih buruk dibandingkan dengan pendekatan berbasis depset. pendekatan. Pertimbangkan kasus di mana ada rantai panjang dependensi Library Foo. Pemrosesan setiap aturan mengharuskan penyalinan semua sumber yang muncul sebelumnya ke dalam struktur data baru. Ini berarti bahwa biaya waktu dan ruang untuk menganalisis {i>library<i} individu atau target biner sebanding dengan tingginya sendiri dalam rantai. Untuk rantai dengan panjang n, foolib_1 ← foolib_2 ... ← foolib_n, biaya keseluruhan secara efektif O(n^2).

Secara umum, depset harus digunakan setiap kali Anda mengakumulasi informasi melalui dependensi transitif Anda. Hal ini membantu memastikan bahwa build Anda diskalakan serta grafik target tumbuh lebih dalam.

Terakhir, penting untuk tidak mengambil isi depset secara tidak perlu dalam penerapan aturan. Satu panggilan ke to_list() di akhir dalam aturan biner tidak masalah, karena biaya keseluruhan hanya O(n). Penting saat banyak target non-terminal mencoba memanggil to_list() perilaku kuadrat tersebut apa yang terjadi.

Untuk mengetahui informasi selengkapnya tentang cara menggunakan depset secara efisien, lihat halaman performa.

Referensi API

Lihat di sini untuk mengetahui detail selengkapnya.