Depset'ler, bir hedefin geçişli bağımlılıklarında verimli bir şekilde veri toplamak için kullanılan özel bir veri yapısıdır. Bunlar, kural işlemenin temel unsurlarından biridir.
Depset’in belirleyici özelliği, zaman ve alandan tasarruf sağlayan birleştirme işlemidir. Depset oluşturucu, bir öğe listesi ("doğrudan") ve diğer ayrıntılar listesini ("geçişli") kabul eder ve tüm doğrudan öğeleri ve tüm geçişli kümelerin birleşimini içeren bir grubu temsil eden bir depset döndürür. Kavramsal olarak, yapıcı, doğrudan ve geçişli düğümleri halefi olarak içeren yeni bir grafik düğümü oluşturur. Depset'ler, bu grafiğin taranmasına dayalı olarak iyi tanımlanmış bir sıralama semantiğine sahiptir.
Depset'lerin örnek kullanımları şunlardır:
Bir programın kitaplıkları için tüm nesne dosyalarının yollarını depolayarak daha sonra bir sağlayıcı aracılığıyla bir bağlayıcı işlemine iletilebilir.
Yorumlanan bir dil için yürütülebilir bir dosyanın çalıştırma dosyalarına dahil olan geçişli kaynak dosyalarını depolamak.
Açıklama ve işlemler
Kavramsal olarak depset, genellikle hedef grafiğe benzer görünen bir yönlendirilmiş asiklik grafiktir (DAG). Kökten yapraklara kadar inşa edilir. Bağımlılık zincirindeki her hedef, önceki hedefleri okumak veya kopyalamak zorunda kalmadan kendi içeriklerini bunların üzerine ekleyebilir.
DAG'deki her düğüm, doğrudan öğelerin ve alt düğümlerin bir listesini içerir. Depset'in içeriği, tüm düğümlerin doğrudan öğeleri gibi geçişli öğelerdir. depset kurucusu kullanılarak yeni bir küme oluşturulabilir: Bir doğrudan öğe listesini ve başka bir alt düğüm listesini kabul eder.
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"])
Bir depset'in içeriğini almak için to_list() yöntemini kullanın. Yinelenenler hariç tüm geçişli öğelerin listesini döndürür. DAG'nin tam yapısını doğrudan incelemenin bir yolu yoktur ancak bu yapı, öğelerin döndürülme sırasını etkiler.
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
Sözlüklerde izin verilen anahtarların kısıtlandığı gibi bir dışa aktarmada izin verilen öğeler de kısıtlanır. Özellikle depset içerikleri değiştirilemez.
Depsetler referans eşitliğini kullanır: Bir depset kendisine eşittir ancak aynı içeriğe ve aynı dahili yapıya sahip olsa bile diğer depsetlerle eşit değildir.
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
Depo kümelerini içeriklerine göre karşılaştırmak için bunları sıralanmış listelere dönüştürün.
s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list())) # True
Bir kümeden öğe kaldırmak mümkün değildir. Bu gerekirse, kaldırılan öğenin tüm içeriğini okumanız, kaldırmak istediğiniz öğeleri filtrelemeniz ve yeni bir depolama alanını yeniden oluşturmanız gerekir. Bu pek de faydalı değil.
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"])
Sipariş
to_list işlemi, DAG üzerinde bir geçiş gerçekleştirir. Geçiş türü, depset oluşturulurken belirtilen sıraya bağlıdır. Araçlar bazen girişlerin sırasını dikkate aldığından Bazel'in birden fazla siparişi desteklemesi faydalı olur. Örneğin, bir bağlayıcı işleminin, B A'a bağlıysa bağlayıcının komut satırında A.o'nin B.o'ten önce geldiğinden emin olması gerekebilir. Diğer araçlarda bunun tam tersi geçerli olabilir.
Üç gezinme sırası desteklenir: postorder, preorder ve topological. İlk ikisi, DAG'ler üzerinde çalışma ve önceden ziyaret edilmiş düğümleri atlamaları dışında, ağaç geçişleri ile tam olarak aynı şekilde çalışır. Üçüncü sıra, kökten dallara doğru topolojik bir sıralama olarak çalışır. Paylaşılan alt öğelerin yalnızca tüm üst öğelerinden sonra listelenmesiyle, temel olarak önce siparişle aynıdır.
Önceden sipariş ve sonradan sipariş, soldan sağa doğru traversal olarak çalışır ancak her düğümde doğrudan öğelerin alt öğelere göre bir sırasının olmadığını unutmayın. Topolojik sıralamada soldan sağa doğru garanti verilmez. Ayrıca DAG'nin farklı düğümlerinde yinelenen öğeler olduğunda tüm üst öğeler alt öğe garantisi de geçerli olmaz.
# 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"]
Gezinmelerin uygulanması nedeniyle, sıra, depset oluşturucunun order anahtar kelime bağımsız değişkeni kullanılarak depset oluşturulurken belirtilmelidir. Bu bağımsız değişken atlanırsa depset, özel default sırasına sahip olur. Bu durumda, öğelerinin herhangi birinin sırası hakkında garanti verilmez (belirleyici olması dışında).
Tam örnek
Bu örneği https://github.com/bazelbuild/examples/tree/main/rules/depsets adresinde bulabilirsiniz.
Foo varsayıma dayalı yorumlanmış bir dil bulunduğunu varsayalım. Her bir foo_binary öğesini oluşturmak için doğrudan veya dolaylı olarak bağımlı olduğu tüm *.foo dosyalarını bilmeniz gerekir.
# //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())
Burada d ikili programının geçişli kaynakları; a, b, c ve d öğelerinin srcs alanlarındaki tüm *.foo dosyalarıdır. foo_binary hedefinin d.foo dışındaki dosyaları bilmesi için foo_library hedeflerinin bunları bir sağlayıcıya iletmesi gerekir. Her kitaplık, sağlayıcıları kendi bağımlılıklarından alır, kendi doğrudan kaynaklarını ekler ve yeni bir sağlayıcıya, artırılmış içeriklerle birlikte iletir. foo_binary kuralı da aynı işlemi yapar. Tek fark, bir sağlayıcı döndürmek yerine bir işlem için komut satırı oluşturmak üzere kaynakların tam listesini kullanmasıdır.
foo_library ve foo_binary kurallarının eksiksiz bir uygulamasını aşağıda bulabilirsiniz.
# //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"},
)
Bu dosyaları yeni bir pakete kopyalayarak, etiketleri uygun şekilde yeniden adlandırarak, kaynak *.foo dosyalarını sahte içerikle oluşturarak ve d hedefini oluşturarak bunu test edebilirsiniz.
Performans
Depo kümelerini kullanmanın nedenini görmek için get_transitive_srcs()'in kaynaklarını bir listede topladığını düşünün.
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
Burada yinelenenler dikkate alınmaz. Bu nedenle, a kaynak dosyaları komut satırında ve çıkış dosyasının içeriğinde iki kez görünür.
Alternatif olarak, anahtarların öğeler olduğu ve tüm anahtarların True ile eşlendiği bir sözlükle simüle edilebilen genel bir küme kullanabilirsiniz.
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
Bu, yinelenen öğeleri ortadan kaldırır ancak komut satırı bağımsız değişkenlerinin sırasını (dolayısıyla da dosyaların içeriği) belirtilmeden ancak yine de deterministik hale getirir.
Ayrıca her iki yaklaşım da asymptotik olarak depset tabanlı yaklaşımdan daha kötüdür. Foo kitaplıklarında uzun bir bağımlılık zinciri olduğunu varsayalım. Her kuralın işlenmesi için kendisinden önce gelen tüm geçişli kaynakların yeni bir veri yapısına kopyalanması gerekir. Bu, tek bir kitaplığın veya ikili hedefin analiz edilmesinin zaman ve alan maliyetinin, zincirdeki kendi yüksekliğine orantılı olduğu anlamına gelir. n, uzunluğundaki bir zincir için foolib_1 ← foolib_2 ← ... ← foolib_n, toplam maliyet etkin bir şekilde O(n^2) olur.
Genel olarak, geçişli bağımlılıklarınız aracılığıyla bilgi toplarken depset'ler kullanılmalıdır. Bu, derleme ölçeklerinizin ve hedef grafiğinizin daha derine inmesini sağlar.
Son olarak, kural uygulamalarında depset içeriğinin gereksiz yere alınmaması önemlidir. Toplam maliyet yalnızca O(n) olduğundan, bir ikili kuralının sonunda to_list() için yapılan bir çağrı sorun yaratmaz. Bu karesel davranış, terminal olmayan birçok hedef to_list()'ü çağırmaya çalıştığında ortaya çıkar.
Uygulamaları verimli bir şekilde kullanma hakkında daha fazla bilgi için performans sayfasını inceleyin.
API Referansı
Daha ayrıntılı bilgi için lütfen burayı inceleyin.