Depset'ler, bir hedefin geçişli bağımlılıkları genelinde verileri verimli bir şekilde toplamak için özel bir veri yapısıdır. Kurallar, kural işlemenin temel bir unsurudur.
depset işlevinin ayırt edici özelliği, zaman ve alan açısından verimli bir birleştirme işlemi olmasıdır. Depset kurucusu, bir öğe listesi ("doğrudan") ve diğer depsetlerin 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 kümeyi 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.
Depo setlerinin örnek kullanım alanları ş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.
Yorumlanmış bir dil için, yürütülebilir dosyanın çalıştırma dosyalarına dahil edilen geçişli kaynak dosyalarını depolama.
Açıklama ve işlemler
Kavramsal olarak, depset genellikle hedef grafiğe benzeyen bir yönlendirilmiş düz ağaçtır (DAG). Kökten yapraklara kadar inşa edilir. Bağımlılık zincirindeki her hedef, önceki hedefleri okumak veya kopyalamak zorunda kalmadan kendi içeriğini öncekilerin üzerine ekleyebilir.
DAG'daki 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 depset oluşturulabilir: Doğrudan öğelerin 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 kısıtlandığı gibi, depsetlerde 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
Öğeler depsetten kaldırılamaz. Bu durumda, depsetin tüm içeriğini okumanız, kaldırmak istediğiniz öğeleri filtrelemeniz ve yeni bir depset oluşturmanız gerekir. Bu yöntem pek verimli değildir.
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'de bir tarama gerçekleştirir. Geçiş türü, depset oluşturulurken belirtilen sıraya bağlıdır. Bazen araçlar, girişlerinin sırasını önemsediği için Bazel'in birden fazla siparişi desteklemesi yararlıdır. Ö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'lerde çalıştıkları ve daha önce ziyaret edilmiş düğümleri atladıkları dışında ağaç gezinmeleri gibi ç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ıra için soldan sağa doğru bir garanti yoktur ve DAG'nin farklı düğümlerinde yinelenen öğeler varsa tüm üst öğeler alt öğeden önce garantisi bile geçerli değildir.
# 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 atlanmazsa depset özel default sırasına sahiptir. Bu durumda, öğelerinin sırası hakkında hiçbir garanti yoktur (deterministik olması dışında).
Tam örnek
Bu örneği https://github.com/bazelbuild/examples/tree/main/rules/depsets adresinde bulabilirsiniz.
Foo adlı varsayımsal bir yorumlanmış dil olduğunu varsayalım. Her foo_binary dosyasını derlemek 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, ikili d dosyasının geçişli kaynakları a, b, c ve d dosyalarının srcs alanlarında bulunan 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 işlem, yinelenenleri ortadan kaldırır ancak komut satırı bağımsız değişkenlerinin sırasını (ve dolayısıyla dosyaların içeriğini) yine de belirlenebilir olsa da belirsiz 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 etkili 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 sayede, hedef grafiğiniz derinleştikçe derlemenizin iyi ölçeklendirilmesini sağlayabilirsiniz.
Son olarak, kural uygulamalarında depset içeriğinin gereksiz yere alınmaması önemlidir. Genel maliyet yalnızca O(n) olduğu için, ikili bir kuralın sonunda to_list() çağrısı yapmak sorun oluşturmaz. Terminal olmayan birçok hedef to_list()'ü çağırmaya çalıştığında bu ikinci dereceden davranış ortaya çıkar.
Depo kümelerini verimli bir şekilde kullanma hakkında daha fazla bilgi için performans sayfasına bakın.
API Referansı
Daha fazla bilgi için lütfen burayı inceleyin.