Dependencias

Los depset son una estructura de datos especializada para recopilar datos de manera eficiente en las dependencias transitivas de un destino. Son un elemento esencial del procesamiento de reglas.

La característica definitoria de depset es su operación de unión eficiente en tiempo y espacio. El constructor de depset acepta una lista de elementos ("directos") y una lista de otros depsets ("transitivos"), y muestra un depset que representa un conjunto que contiene todos los elementos directos y la unión de todos los conjuntos transitivos. Conceptualmente, el constructor crea un nuevo nodo de gráfico que tiene los nodos directos y transitivos como sus sucesores. Los depset tienen una semántica de orden bien definida, basada en el recorrido de este gráfico.

Entre los ejemplos de uso de depset, se incluyen los siguientes:

• Almacenar las rutas de acceso de todos los archivos de objeto para las bibliotecas de un programa, que luego se pueden pasar a una acción de 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

Conceptualmente, un depset es un grafo acíclico dirigido (DAG) que suele ser similar al gráfico de destino. Se construye desde las hojas hasta la raíz. Cada destino de una cadena de dependencias puede agregar su propio contenido sobre el anterior sin tener que leerlo ni copiarlo.

Cada nodo del DAG contiene una lista de elementos directos y una lista de nodos secundarios. El contenido del depset son los elementos transitivos, como los elementos directos de todos los nodos. Se puede crear un depset nuevo con el depset constructor: 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 depset, usa el to_list() método. Muestra una lista de todos los elementos transitivos, sin incluir duplicados. No hay forma de inspeccionar directamente la estructura precisa del DAG, aunque esta estructura afecta el orden en 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 depset están restringidos, al igual que las claves permitidas en los diccionarios están restringidas. En particular, el contenido de depset no puede ser mutable.

Los depset usan la igualdad de referencia: un depset es igual a sí mismo, pero desigual a cualquier otro depset, 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 depset 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 depset. Si 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"])

Pedido

La operación to_list realiza un recorrido sobre el DAG. El tipo de recorrido depende del orden que se especificó cuando se construyó el depset. 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 de vinculador puede necesitar asegurarse de que, si B depende de A, entonces A.o aparezca antes que B.o en la línea de comandos del vinculador. Otras herramientas podrían tener el requisito opuesto.

Se admiten tres órdenes de recorrido: postorder, preorder y topological. Los dos primeros funcionan exactamente como los recorridos de árbol excepto que operan en DAG y omiten los nodos ya visitados. El tercer orden funciona como una clasificación topológica de raíz a hojas, esencialmente igual que el orden previo, excepto que los elementos secundarios compartidos se enumeran solo después de todos sus elementos superiores. El orden previo y el orden posterior operan como recorridos de izquierda a derecha, pero ten en cuenta que, dentro de cada nodo, los elementos directos no tienen ningún orden en relación con los elementos secundarios. Para el orden topológico, no hay garantía de izquierda a derecha, y ni siquiera la garantía de todos los elementos superiores antes del elemento secundario 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, el orden debe especificarse cuando se crea el depset con el argumento de palabra clave order del constructor. Si este argumento se omite, el depset tiene el orden especial default, 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 existe un lenguaje interpretado hipotético 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 foo_binary destino conozca cualquier archivo además de d.foo, los foo_library destinos deben pasarlos en un proveedor. Cada biblioteca recibe 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.
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"},
)

Para probarlo, copia estos archivos en un paquete nuevo, cambia el nombre de las etiquetas de forma adecuada, crea los archivos fuente *.foo con contenido ficticio y compila el destino d.

Rendimiento

Para ver la motivación para usar depset, considera qué 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[foo_files].transitive_sources
  trans_srcs += srcs
  return trans_srcs

Esto no tiene en cuenta los duplicados, por lo que los archivos fuente 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 se puede simular 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[foo_files].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 los argumentos de la línea de comandos (y, por lo tanto, el contenido de los archivos) no se especifique, aunque sigue siendo determinista.

Además, ambos enfoques son asintóticamente peores que el enfoque basado en depset enfoque. Considera el caso en el que hay una larga cadena de dependencias en las bibliotecas de Foo. El procesamiento de cada regla requiere copiar todas las fuentes transitivas que la precedieron en una nueva estructura de datos. Esto significa que el costo de tiempo y espacio para analizar una biblioteca individual o un destino 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 general, se deben usar depset siempre que acumules información a través de tus dependencias transitivas. Esto ayuda a garantizar que tu compilación se escale bien a medida que tu gráfico de destino se profundiza.

Por último, es importante no recuperar el contenido del depset de forma innecesaria en las implementaciones de reglas. Una llamada a to_list() al final de una regla binaria está bien, ya que el costo general es solo O(n). Cuando muchos destinos no terminales intentan llamar a to_list(), se produce un comportamiento cuadrático.

Para obtener más información sobre el uso eficiente de depset, consulta la página de rendimiento.

Referencia de la API

Consulta aquí para obtener más detalles.