Los depsets son una estructura de datos especializada para recopilar datos de manera eficiente a través de las dependencias transitivas de un objetivo. Son un elemento esencial del 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 otros depósitos ("transitivos"), y muestra un depósito que representa un conjunto que contiene todos los elementos directos y la unión de todos los conjuntos transitivos. De forma conceptual, el constructor crea un nodo de grafo nuevo que tiene los nodos directos y transitivos como sus sucesores. Los depsets tienen una semántica de orden bien definida, basada en el 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 luego se pueden pasar a una acción del vinculador a través de un proveedor.
Para un lenguaje interpretado, almacenar los archivos fuente transitivos que se incluyen en los archivos de ejecución de un ejecutable.
Descripción y operaciones
De forma conceptual, un depset es un grafo acíclico dirigido (DAG) que, por lo general, es similar al grafo de destino. Se construye desde las hojas hasta la raíz. Cada destino en una cadena de dependencias puede agregar su propio contenido además del anterior sin tener que leerlo ni copiarlo.
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 constructor depset, que acepta una lista de elementos directos 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 depósito, usa el método to_list(). Muestra una lista de todos los elementos transitivos, sin incluir los duplicados. No hay forma de inspeccionar directamente la estructura precisa del DAG, aunque esta sí afecta el orden en el que se muestran 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 están restringidos, al igual que las claves permitidas en los diccionarios. 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 no igual a cualquier otro, incluso si 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, debes leer todo el contenido del depset, filtrar los elementos que deseas quitar y reconstruir un depset nuevo. 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"])
Pedidos
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 construyó el depósito. Es útil que Bazel admita varios pedidos porque, a veces,
las herramientas se preocupan por el orden de sus entradas. Por ejemplo, es posible que una acción del vinculador deba garantizar que, si B depende de A, entonces A.o aparecerá antes de B.o en 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 de la misma manera que los recorridos de árbol, excepto que operan en DAG y omiten los nodos ya visitados. El tercer orden funciona como una ordenación topológica desde la raíz hasta las hojas, en esencia, al igual que el pedido por adelantado, con la excepción de que los elementos secundarios compartidos solo se enumeran después de todos los elementos superiores.
Los pedidos previos y posteriores funcionan como recorridos de izquierda a derecha, pero debes tener en cuenta que, dentro de cada nodo, los elementos directos no tienen un orden relativo a los elementos secundarios. Para el orden topológico, no hay una garantía de izquierda a derecha, y ni siquiera la garantía "all-parents-before-child" se aplica en el caso de que haya 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 en que se crea el depset con el argumento de palabra clave order del constructor. Si se omite este argumento, el depset tiene el orden default especial, en cuyo caso no hay garantías sobre el orden de cualquiera 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 compilar cada foo_binary, debes conocer todos los archivos *.foo de los que depende directa o indirectamente.
# //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 en los campos srcs de a, b, c y d. Para que el destino foo_binary conozca cualquier archivo además de d.foo, los destinos foo_library deben pasarlos en un proveedor. Cada biblioteca recibe a los proveedores de sus propias dependencias, agrega sus propias fuentes inmediatas y pasa un proveedor nuevo con el contenido aumentado. La regla foo_binary hace lo mismo, excepto que, en lugar de mostrar un proveedor, usa la lista completa de fuentes para construir una 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, cambia el nombre de las etiquetas según corresponda, crea los archivos *.foo de origen con contenido ficticio y compila el destino d.
Rendimiento
Para ver la motivación para usar las dependencias, considera lo que sucedería si get_transitive_srcs() recopilara 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
Esto no considera los duplicados, por lo que los archivos de origen de a aparecerán dos veces en la línea de comandos y dos veces en el contenido del archivo de salida.
Una alternativa es usar un conjunto general, que puede simularse con un 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 deja sin especificar el orden de los argumentos de la línea de comandos (y, por lo tanto, el contenido de los archivos), aunque sigue siendo determinista.
Además, ambos enfoques son asintóticamente peor que el enfoque basado en depset. Considera el caso en el que hay una larga cadena de dependencias en las bibliotecas de Foo. Para procesar cada regla, se deben copiar todas las fuentes transitivas anteriores a ellas en una estructura de datos nueva. Esto significa que el costo de tiempo y espacio para analizar una biblioteca o un destino binario individual 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 general, los depsets deben usarse siempre que acumulas información a través de tus dependencias transitivas. Esto ayuda a garantizar que la compilación se escale bien a medida que el gráfico de destino crezca más.
Por último, es importante no recuperar el contenido del depósito de forma innecesaria 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() que se produce un
comportamiento cuadrático.
Si deseas obtener más información para usar las dependencias de forma eficiente, consulta la página de rendimiento.
Referencia de las APIs
Consulta aquí para obtener más detalles.