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 kurucu, doğrudan ve geçişli düğümlerin yerini alacak 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.
Depset'lerin örnek kullanımları ş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 benzer görünen bir yönlendirilmiş asiklik grafiktir (DAG). Yapraklardan köke kadar oluşturulur. Bağımlılık zincirindeki her hedef, bunları okumak veya kopyalamak zorunda kalmadan bir öncekinin üzerine kendi içeriklerini 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 kümenin 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 olmasa da 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, indirilmiş içerikler değiştirilemeyebilir.
Depset'ler referans eşitliği kullanır: Depset kendisiyle eşittir, ancak aynı içeriklere ve aynı iç yapıya sahip olsa bile diğer dezavantajlara 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 kullanımdan öğ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ü, derinliğ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çlar için ise tam tersi bir gereklilik olabilir.
Üç geçiş siparişi desteklenir: postorder, preorder ve topological. İlk ikisi ağaç geçişleri gibi çalışır ancak DAG'ler üzerinde çalışır ve önceden ziyaret edilmiş düğümleri atlar. Üçüncü sıra, kökten yapraklara topolojik bir sıralama olarak işlev görür. Ön siparişle temelde aynıdır. Tek fark, paylaşılan çocukların yalnızca üst öğelerinden sonra listelenmesidir.
Ön sipariş ve son sipariş işlemleri soldan sağa geçişler olarak çalışır, ancak her düğümde doğrudan öğelerin alt öğelere göre sırası olmadığını unutmayın. Topolojik sıralamada soldan sağa doğru garanti verilmez.
# 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"]
Geçişlerin uygulanma şekli nedeniyle, sıra, oluşturucunun order anahtar kelime bağımsız değişkeniyle denetim oluşturulduğu anda 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ı ile ilgili 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 hakkında bilgi sahibi olması için foo_library hedeflerinin bunları bir sağlayıcıda iletmesi gerekir. Her kitaplık, sağlayıcıları kendi bağımlılıklarından alır, kendi birincil kaynaklarını ekler ve artırılmış içeriğe sahip yeni bir sağlayıcıya geçer. foo_binary kuralı da aynısını yapar. Ancak bir işlem için komut satırı oluşturmak amacıyla sağlayıcıyı döndürmek yerine, kaynakların tam listesini kullanır.
foo_library ve foo_binary kurallarının eksiksiz bir şekilde nasıl uygulandığını aşağıda görebilirsiniz.
# //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 işlemi, bu dosyaları yeni bir pakete kopyalayarak, etiketleri uygun şekilde yeniden adlandırarak, model içerikle kaynak *.foo dosyalarını oluşturarak ve d hedefini oluşturarak test edebilirsiniz.
Performans
Depsy'leri kullanma motivasyonunu görmek için get_transitive_srcs(), kaynaklarını bir listede toplarsa ne olacağı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 bir yöntem de, anahtarların öğeler olduğu ve tüm anahtarların True ile eşlendiği sözlük tarafından simüle edilebilecek genel bir küme kullanmaktır.
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, yinelemeleri 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.
Üstelik, her iki yaklaşım da düşüş temelli yaklaşımdan asimptotik derecede daha kötüdür. Foo kitaplıklarında uzun bir bağımlılık zincirinin olduğu senaryoyu düşünün. 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ık veya ikili hedefi analiz etmenin zaman ve alan maliyetinin, zincirdeki kendi yüksekliğiyle 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, Depsets'i geçişli bağımlılıklarınız üzerinden bilgi toplarken kullanmanız gerekir. Bu, derleme ölçeklerinizin ve hedef grafiğinizin daha derine inmesini sağlar.
Son olarak, kural uygulamalarında kötü amaçlı dosyanın içeriklerini gereksiz yere almamak ö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. Birçok terminal olmayan hedef to_list() işlemini çağırmaya çalıştığında ikinci dereceden davranış meydana gelir.
Uygulamaları verimli bir şekilde kullanma hakkında daha fazla bilgi için performans sayfasını inceleyin.
API Referansı
Daha fazla bilgiyi burada bulabilirsiniz.