Depsetler, bir hedefin geçişli bağımlılıkları genelinde verileri verimli bir şekilde toplamak için kullanılan özel bir veri yapısıdır. Bunlar, kural işlemenin temel bir unsurudur.
Depset'in belirleyici özelliği, zamandan ve alandan tasarruf sağlayan birleştirme işlemidir. Depsset oluşturucu, bir öğe listesi ("direct") ve diğer depset'lerin bir listesini ("transitive") 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, oluşturucu, doğrudan ve geçişli düğümleri halefleri olarak içeren yeni bir grafik düğümü oluşturur. Depset'ler, bu grafiğin geçişine dayalı olarak iyi tanımlanmış bir sıralama semantiğine sahiptir.
Depset'lerin örnek kullanımları:
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 bağlayıcı işlemine aktarılabilir.
Yorumlanmış bir dil için, yürütülebilir dosyanın çalışma dosyalarına dahil edilen geçişli kaynak dosyalarını depolama.
Açıklama ve işlemler
Kavramsal olarak, bir depset genellikle hedef grafiğe benzeyen bir yönlü düz ağaçtır (DAG). Yapraklardan köke doğru oluşturulur. Bağımlılık zincirindeki her hedef, önceki içerikleri okumak veya kopyalamak zorunda kalmadan kendi içeriklerini ekleyebilir.
DAG'deki her düğüm, doğrudan öğelerin ve alt düğümlerin listesini içerir. Depshet'in içeriği, tüm düğümlerin doğrudan öğeleri gibi geçişli öğelerdir. depset oluşturucusu kullanılarak yeni bir depset oluşturulabilir: Doğrudan öğelerin listesini ve alt düğümlerin başka bir 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ç olmak üzere tüm geçişli öğelerin listesini döndürür. Öğelerin döndürülme sırasını etkilese de DAG'nin tam yapısını doğrudan incelemenin bir yolu yoktur.
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
Bir depset'teki izin verilen öğeler, sözlüklerdeki izin verilen anahtarlar gibi kısıtlanır. Özellikle depset içerikleri değiştirilemez.
Depset'ler referans eşitliği kullanır: Bir depset kendisiyle eşittir ancak aynı içeriğe ve aynı iç yapıya sahip olsa bile başka bir depset ile 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
Bağımlılık 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, depsetlerden kaldırılamaz. Bu işlem gerekirse 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 üzerinde geçiş gerçekleştirir. Geçiş türü, depset oluşturulurken belirtilen sıraya bağlıdır. Bazı araçlar girişlerinin sırasına önem verdiğinden Bazel'in birden fazla sırayı desteklemesi faydalıdır. Örneğin, bir bağlayıcı işlemi, B öğesinin A öğesine bağlı olması durumunda A.o öğesinin bağlayıcının komut satırında B.o öğesinden önce gelmesini sağlaması gerekebilir. Diğer araçlarda tam tersi bir gereklilik olabilir.
Üç geçiş sırası desteklenir: postorder, preorder ve topological. İlk iki yöntem, DAG'lerde çalışması ve daha önce ziyaret edilen düğümleri atlaması dışında tam olarak ağaç geçişleri gibi çalışır. Üçüncü sıra, kökten yapraklara doğru topolojik sıralama olarak çalışır. Paylaşılan alt öğeler yalnızca tüm üst öğelerinden sonra listelenmesi dışında, ön sıralamayla aynıdır.
Ön sipariş ve son sipariş, soldan sağa geçişler olarak çalışır ancak her düğümdeki doğrudan öğelerin alt öğelere göre herhangi bir sırası olmadığını unutmayın. Topolojik sıralamada soldan sağa sıralama garantisi yoktur ve DAG'nin farklı düğümlerinde yinelenen öğeler olması durumunda tüm üst öğelerden önce alt öğe 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"]
Geçişlerin uygulanma şekli nedeniyle, sıra, depset oluşturulurken oluşturucunun order anahtar kelime bağımsız değişkeniyle belirtilmelidir. Bu bağımsız değişken atlanırsa depset, özel default sırasına sahip olur. Bu durumda, öğelerinin sırası hakkında herhangi bir garanti verilmez (sıranın deterministik olması dışında).
Tam örnek
Bu örneğe https://github.com/bazelbuild/examples/tree/main/rules/depsets adresinden ulaşabilirsiniz.
Foo adlı, yorumlanmış bir dil olduğunu varsayalım. Her foo_binary öğesini oluşturmak için doğrudan veya dolaylı olarak bağlı 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 program d'nın geçişli kaynakları, a, b, c ve d'nın srcs alanlarındaki tüm *.foo dosyalarıdır. foo_binary
Hedefin d.foo dışındaki dosyalar hakkında bilgi sahibi olabilmesi için foo_library hedeflerinin bunları bir sağlayıcıda iletmesi gerekir. Her kitaplık, kendi bağımlılıklarındaki sağlayıcıları alır, kendi doğrudan kaynaklarını ekler ve artırılmış içeriklerle yeni bir sağlayıcıyı iletir. foo_binary kuralı da aynı işlemi yapar ancak sağlayıcı döndürmek yerine bir işlem için komut satırı oluşturmak üzere kaynakların tam listesini kullanır.
foo_library ve foo_binary kurallarının eksiksiz bir uygulamasını burada bulabilirsiniz.
# //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"},
)
Bu dosyaları yeni bir pakete kopyalayıp etiketleri uygun şekilde yeniden adlandırarak, sahte içeriklerle kaynak *.foo dosyaları oluşturarak ve d hedefi oluşturarak bunu test edebilirsiniz.
Performans
Depset kullanmanın nedenini anlamak için get_transitive_srcs() kaynaklarını bir listede toplasaydı ne olacağını düşünün.
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
Bu işlemde 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, genel bir küme kullanabilirsiniz. Bu küme, anahtarların öğeler olduğu ve tüm anahtarların True ile eşlendiği bir sözlükle simüle edilebilir.
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
Bu işlem, yinelenenleri kaldırır ancak komut satırı bağımsız değişkenlerinin (ve dolayısıyla dosyaların içeriğinin) sırasını belirtilmemiş hale getirir. Yine de sıra, deterministik olmaya devam eder.
Ayrıca, her iki yaklaşım da depset tabanlı yaklaşımdan asimptotik olarak daha kötüdür. Foo kitaplıklarında uzun bir bağımlılık zinciri olduğunu düşünelim. Her kuralın işlenmesi, kendisinden ö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 hedefinin analiz edilmesinin 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) genel maliyet etkili bir şekilde O(n^2) olur.
Genel olarak, geçişli bağımlılıklarınız aracılığıyla bilgi topladığınız her durumda bağımlılık kümeleri kullanılmalıdır. Bu, hedef grafiğiniz derinleştikçe derlemenizin iyi ölçeklenmesini sağlar.
Son olarak, kural uygulamalarında depset'in içeriğinin gereksiz yere alınmaması önemlidir. Genel maliyet yalnızca O(n) olduğundan, ikili bir kuralın sonunda to_list() işlevi bir kez çağrılabilir. Karesel davranış, sonlandırıcı olmayan birçok hedef to_list() işlevini çağırmaya çalıştığında ortaya çıkar.
Bağımlılık 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 buraya göz atın.