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. Depsets, bu grafiğin geçişi temel alınarak iyi tanımlanmış bir sıralama anlamına sahiptir.
Depo setlerinin örnek kullanım alanları şunlardır:
Bir programın kitaplıkları için tüm nesne dosyalarının yollarını depolama. Bu yollar, 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 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çeriklerini bunların ü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: Bu kurucu, 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
Denemeleri 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 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'in oluşturulduğu sırada belirtilen sıralamaya 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 işlevinin A öğesine bağlı olması durumunda, bağlayıcının komut satırında A.o öğesinin B.o öncesinde yer almasını sağlamak 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 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 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 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
Bu durumda yinelenen içerikler dikkate alınmaz. Bu nedenle a için kaynak dosyalar, komut satırında iki kez, çıkış dosyasının içeriğinde de 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, ondan önce gelen tüm geçişli kaynakların yeni bir veri yapısına kopyalanmasını gerektirir. 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 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. Bu karesel davranış, terminal olmayan birçok hedef to_list()'ü çağırmaya çalıştığında ortaya çıkar.
Depo setlerini verimli bir şekilde kullanma hakkında daha fazla bilgi için performans sayfasına bakın.
API Referansı
Daha ayrıntılı bilgi için lütfen burayı inceleyin.