Los depsets son una estructura de datos especializada para medir eficientemente recopilar datos a través de las dependencias transitivas de un objetivo. Son un elemento esencial de procesamiento de reglas.
La característica que define el depset es su operación de unión eficiente en el tiempo y el espacio. El constructor de depset acepta una lista de elementos ("directos") y una lista de otras depsets (“transitivo”) y devuelve un depset que representa un conjunto que contiene todas las los elementos directos y la unión de todos los conjuntos transitivos. Conceptualmente, El constructor crea un nuevo nodo de grafo que contiene los nodos directos y transitivos. como sus sucesores. Los depsets tienen una semántica de orden bien definida, basada en recorrido de este grafo.
Estos son algunos ejemplos de usos de los depsets:
Almacenar las rutas de acceso de todos los archivos de objetos para las bibliotecas de un programa, que pueden y, luego, pasarse a una acción de vinculador a través de un proveedor.
Para un lenguaje interpretado, almacenar los archivos de origen transitivos se incluyen en los archivos runfiles de un ejecutable.
Descripción y operaciones
De forma conceptual, un depset es un grafo acíclico dirigido (DAG) que suele verse similar al gráfico objetivo. Se construye desde las hojas hasta la raíz. Cada objetivo en una cadena de dependencias puede agregar su propio contenido además del anterior sin tener que leerlos ni copiarlos.
Cada nodo del DAG contiene una lista de elementos directos y una lista de nodos secundarios. Los contenidos del depset son los elementos transitivos, como los elementos directos de todos los nodos. Se puede crear un depósito nuevo con el depset: acepta una lista de entradas directas. y otra lista de nodos secundarios.
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"])
Para recuperar el contenido de un depset, usa el to_list(). Devuelve una lista de todas las imágenes elementos, sin incluir los duplicados. No hay forma de inspeccionar directamente pero no tiene una estructura precisa del DAG, aunque esta sí afecta el orden en la que se devuelven los elementos.
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
Los elementos permitidos en un depósito se encuentran restringidos, al igual que las claves permitidas en diccionarios están restringidos. En particular, es posible que el contenido del depset no sea mutable.
Los depsets usan la igualdad de referencia: un depset es igual a sí mismo, pero desigual a cualquier que tienen el mismo contenido y la misma estructura interna.
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
Para comparar los depsets por su contenido, conviértelos en listas ordenadas.
s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list())) # True
No se pueden quitar elementos de un depósito. Si esto es necesario, debe leer todo el contenido del depset, filtrar los elementos que desees quitar y reconstruir un nuevo depósito. Esto no es particularmente eficiente.
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"])
Pedido
La operación to_list realiza un recorrido por el DAG. El tipo de recorrido
depende del orden que se especificó en el momento en que se estableció
construido. Es útil que Bazel admita varios pedidos porque, a veces,
las herramientas se preocupan por el orden de sus entradas. Por ejemplo, una acción del vinculador puede
debes asegurarte de que, si B depende de A, entonces A.o aparece antes de B.o en el
de la línea de comandos del vinculador. Otras herramientas pueden tener el requisito opuesto.
Se admiten tres pedidos de recorrido: postorder, preorder y
topological Las dos primeras funcionan exactamente como el árbol
recorridos
salvo que operan en DAG y omiten los nodos ya visitados. El tercer pedido
funciona como una ordenación topológica de la raíz a las hojas, esencialmente igual que
preorder, excepto que los publicadores secundarios compartidos solo aparecen después de todos los padres.
Los pedidos anticipados y después funcionan como recorridos de izquierda a derecha, pero deben tener en cuenta que
los elementos directos de cada nodo no tienen un orden relativo a los elementos secundarios. Para topología
no hay garantía de izquierda a derecha e incluso
la garantía "all-parents-before-child" no se aplica si hay
elementos duplicados en diferentes nodos del DAG.
# 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"]
Debido a la forma en que se implementan los recorridos, se debe especificar el orden en el momento
El depset se crea con el argumento de palabra clave order del constructor. Si esta
se omite, el depset tiene el orden default especial, en cuyo caso
no hay garantías sobre el orden de ninguno de sus elementos (excepto que
es determinista).
Ejemplo completo
Este ejemplo está disponible en https://github.com/bazelbuild/examples/tree/main/rules/depsets.
Supongamos que hay un lenguaje interpretado hipotéticamente como Foo. Para crear
cada foo_binary, debes conocer todos los archivos *.foo que este directamente o
depende indirectamente de ellas.
# //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())
Aquí, las fuentes transitivas del objeto binario d son todos los archivos *.foo de
los campos srcs de a, b, c y d. En el caso del foo_binary
objetivo para saber sobre cualquier archivo además de d.foo, los destinos de foo_library deben
y pasarlos a un proveedor. Cada biblioteca recibe los proveedores de su propio
dependencias, agrega sus propias fuentes inmediatas y pasa un nuevo proveedor con
los contenidos aumentados. La regla foo_binary hace lo mismo, pero
de mostrar un proveedor, usa la lista completa de fuentes para construir un
la línea de comandos para una acción.
Esta es una implementación completa de las reglas foo_library y foo_binary.
# //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"},
)
Para probar esto, copia estos archivos en un paquete nuevo, cámbiale el nombre a
etiqueta de forma adecuada, creando los archivos *.foo de origen con contenido ficticio
creando el objetivo d.
Rendimiento
Para ver la motivación por usar las depresiones, considera lo que sucedería si
get_transitive_srcs() recopiló sus fuentes en una lista.
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
Como no se tienen en cuenta los duplicados, los archivos fuente de a
aparecerá dos veces en la línea de comandos y dos veces en el contenido del resultado
.
Una alternativa es usar un conjunto general, que puede ser simulado por una
diccionario en el que las claves son los elementos y todas las claves se asignan a True.
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
Esto elimina los duplicados, pero hace que el orden de la línea de comandos argumentos (y, por lo tanto, el contenido de los archivos) sin especificar, aunque aún son deterministas.
Además, ambos enfoques son asintóticamente peores que el basado en enfoque. Considera el caso en el que hay una larga cadena de dependencias en bibliotecas Foo. Para procesar cada regla, es necesario copiar todos los datos transitivos fuentes anteriores a ellos en una nueva estructura de datos. Esto significa que el costo de tiempo y espacio para analizar una biblioteca individual o un objetivo binario es proporcional a su propia altura en la cadena. Para una cadena de longitud n, foolib_1 ← foolib_2 ← ... ← foolib_n, el costo general es efectivamente O(n^2).
En términos generales, los depsets se deben usar siempre que acumules a través de tus dependencias transitivas. Esto ayuda a garantizar que tu compilación escala bien a medida que crece tu gráfico objetivo.
Por último, es importante no recuperar el contenido del depósito
innecesariamente en las implementaciones de reglas. Una llamada a to_list()
al final en una regla binaria está bien, ya que el costo general es solo O(n). Es
cuando muchos objetivos no terminales intentan llamar a to_list() ese comportamiento cuadrático
o cuándo ocurre.
Si deseas obtener más información para usar las dependencias de forma eficiente, consulta la página de rendimiento.
Referencia de la API
Consulta aquí para obtener más detalles.