Depset

Depset adalah struktur data khusus untuk mengumpulkan data secara efisien di seluruh dependensi transitif target. Depset adalah elemen penting dalam pemrosesan aturan.

Fitur yang menentukan depset adalah operasi gabungan yang efisien dari segi waktu dan ruang. Konstruktor depset menerima daftar elemen ("langsung") dan daftar depset lainnya ("transitif"), serta menampilkan depset yang mewakili kumpulan yang berisi semua elemen langsung dan gabungan dari semua kumpulan 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 depset mencakup:

• 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 runfile yang dapat dieksekusi.

Deskripsi dan operasi

Secara konseptual, depset adalah directed acyclic graph (DAG) yang biasanya terlihat mirip dengan grafik target. Depset dibuat dari daun hingga akar. Setiap target dalam rantai dependensi dapat menambahkan kontennya sendiri di atas konten sebelumnya tanpa harus membaca atau menyalinnya.

Setiap node dalam 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: 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, tanpa menyertakan duplikat. Tidak ada cara untuk memeriksa struktur DAG yang tepat 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 depset dibatasi, seperti halnya kunci yang diizinkan dalam kamus. Secara khusus, konten depset mungkin tidak dapat diubah.

Depset menggunakan persamaan 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 depset 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"])

Urutan

Operasi to_list melakukan traversal melalui DAG. Jenis traversal bergantung pada urutan yang ditentukan pada saat depset dibuat. Bazel berguna untuk mendukung beberapa urutan karena terkadang alat memperhatikan urutan inputnya. Misalnya, tindakan linker mungkin perlu memastikan bahwa jika B bergantung pada A, maka A.o akan muncul sebelum B.o di command line linker. Alat lain mungkin memiliki persyaratan yang berlawanan.

Tiga urutan traversal didukung: postorder, preorder, dan topological. Dua urutan pertama berfungsi persis seperti traversal pohon kecuali bahwa keduanya beroperasi pada DAG dan melewati node yang sudah dikunjungi. Urutan ketiga berfungsi sebagai pengurutan topologi dari akar ke daun, 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 node, elemen langsung 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 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 traversal diimplementasikan, urutan harus ditentukan pada saat depset dibuat dengan argumen kata kunci order konstruktor. Jika argumen ini dihilangkan, depset akan memiliki urutan default khusus, yang dalam hal ini tidak ada jaminan tentang urutan elemennya (kecuali bahwa urutan tersebut bersifat 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 harus mengetahui semua file *.foo yang bergantung secara 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 dari 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 ditambah. Aturan foo_binary melakukan hal yang sama, kecuali bahwa aturan tersebut menggunakan daftar sumber lengkap untuk membuat command line untuk suatu tindakan, bukan menampilkan penyedia.

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 membuat d target.

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[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 konten file output.

Alternatifnya adalah menggunakan kumpulan 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[foo_files].transitive_sources:
      trans_srcs[file] = True
  for file in srcs:
    trans_srcs[file] = True
  return trans_srcs

Hal ini akan menghilangkan 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 panjang dependensi pada library Foo. Memproses setiap aturan memerlukan penyalinan semua sumber transitif yang ada sebelumnya ke dalam struktur data baru. Artinya, biaya waktu dan ruang untuk menganalisis target library atau biner individual sebanding dengan tingginya sendiri dalam rantai. Untuk rantai dengan 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 build Anda dapat diskalakan dengan baik saat grafik target Anda semakin dalam.

Terakhir, penting untuk tidak mengambil konten depset secara tidak perlu dalam implementasi 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 depset secara efisien, lihat halaman performa.

Referensi API

Lihat di sini untuk mengetahui detail selengkapnya.