Dependências

Depsets são uma estrutura de dados especializada para coletar dados com eficiência nas dependências transitivas de um destino. Eles são um elemento essencial do processamento de regras.

O recurso de definição do depset é a operação de união eficiente em tempo e espaço. O construtor de depset aceita uma lista de elementos ("diretos") e uma lista de outros depsets ("transitivos") e retorna um depset que representa um conjunto que contém todos os elementos diretos e a união de todos os conjuntos transitivos. Conceitualmente, o construtor cria um novo nó de gráfico que tem os nós diretos e transitivos como sucessores. Os depsets têm uma semântica de ordenação bem definida, com base em travessia desse gráfico.

Exemplos de usos de depsets incluem:

• Armazenar os caminhos de todos os arquivos de objeto para as bibliotecas de um programa, que podem ser transmitidos a uma ação de vinculador por um provedor.

• Para uma linguagem interpretada, armazenar os arquivos de origem transitivos que estão incluídos nos runfiles de um executável.

Descrição e operações

Conceitualmente, um depset é um gráfico acíclico direcionado (DAG) que geralmente é semelhante ao gráfico de destino. Ele é construído das folhas até a raiz. Cada destino em uma cadeia de dependências pode adicionar o próprio conteúdo na parte de cima do anterior sem precisar ler ou copiar.

Cada nó no DAG contém uma lista de elementos diretos e uma lista de nós filhos. O conteúdo do depset são os elementos transitivos, como os elementos diretos de todos os nós. Um novo depset pode ser criado usando o depset construtor: ele aceita uma lista de elementos diretos e outra lista de nós filhos.

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 o conteúdo de um depset, use o to_list() método. Ele retorna uma lista de todos os elementos transitivos, sem incluir duplicados. Não há como inspecionar diretamente a estrutura precisa do DAG, embora essa estrutura afete a ordem em que os elementos são retornados.

s = depset(["a", "b", "c"])

print("c" in s.to_list())              # True
print(s.to_list() == ["a", "b", "c"])  # True

Os itens permitidos em um depset são restritos, assim como as chaves permitidas em dicionários são restritos. Em particular, o conteúdo do depset não pode ser mutável.

Os depsets usam igualdade de referência: um depset é igual a si mesmo, mas desigual a qualquer outro depset, mesmo que tenham o mesmo conteúdo e a mesma estrutura 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 depsets pelo conteúdo, converta-os em listas classificadas.

s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list()))  # True

Não é possível remover elementos de um depset. Se isso for necessário, você deve ler todo o conteúdo do depset, filtrar os elementos que você quer remover e reconstruir um novo depset. Isso não é 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

A operação to_list executa uma travessia no DAG. O tipo de travessia depende da ordem especificada no momento em que o depset foi construído. É útil para o Bazel oferecer suporte a várias ordens porque, às vezes, as ferramentas se preocupam com a ordem das entradas. Por exemplo, uma ação de vinculador pode precisar garantir que, se B depender de A, A.o venha antes de B.o na linha de comando do vinculador. Outras ferramentas podem ter o requisito oposto.

Há suporte para três ordens de travessia: postorder, preorder e topological. Os dois primeiros funcionam exatamente como travessias de árvore exceto que operam em DAGs e ignoram nós já visitados. A terceira ordem funciona como uma classificação topológica da raiz para as folhas, essencialmente a mesma que a pré-ordem, exceto que os filhos compartilhados são listados somente depois de todos os pais. A pré-ordem e a pós-ordem operam como travessias da esquerda para a direita, mas observe que, em cada nó, os elementos diretos não têm ordem em relação aos filhos. Para a ordem topológica, não há garantia da esquerda para a direita, e mesmo a garantia de todos os pais antes do filho não se aplica no caso de haver elementos duplicados em nós diferentes do 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"]

Devido à forma como as travessias são implementadas, a ordem precisa ser especificada no momento em que o depset é criado com o argumento de palavra-chave order do construtor. Se este argumento for omitido, o depset terá a ordem especial default, caso em que não há garantias sobre a ordem de nenhum dos elementos (exceto que ela é determinística).

Exemplo completo

Este exemplo está disponível em https://github.com/bazelbuild/examples/tree/main/rules/depsets.

Suponha que haja uma linguagem interpretada hipotética Foo. Para criar cada foo_binary, é necessário conhecer todos os arquivos *.foo de que ele depende direta ou indiretamente.

# //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())

Aqui, as origens transitivas do binário d são todos os arquivos *.foo nos campos srcs de a, b, c e d. Para que o foo_binary destino conheça qualquer arquivo além de d.foo, os foo_library destinos precisam transmiti-los em um provedor. Cada biblioteca recebe os provedores das próprias dependências, adiciona as próprias origens imediatas e transmite um novo provedor com o conteúdo aumentado. A regra foo_binary faz o mesmo, exceto que, em vez de retornar um provedor, ela usa a lista completa de origens para construir uma linha de comando para uma ação.

Confira uma implementação completa das regras foo_library e 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 testar, copie esses arquivos para um novo pacote, renomeie os rótulos de maneira adequada, crie os arquivos de origem *.foo com conteúdo fictício e crie o destino d.

Desempenho

Para entender a motivação para usar depsets, considere o que aconteceria se get_transitive_srcs() coletasse as origens em uma 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

Isso não leva em consideração duplicados, então os arquivos de origem de a vão aparecer duas vezes na linha de comando e duas vezes no conteúdo do arquivo de saída file.

Uma alternativa é usar um conjunto geral, que pode ser simulado por um dicionário em que as chaves são os elementos e todas as chaves são mapeadas para 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

Isso elimina os duplicados, mas torna a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) não especificada, embora ainda determinística.

Além disso, as duas abordagens são assintoticamente piores do que a abordagem baseada em depset. Considere o caso em que há uma longa cadeia de dependências em bibliotecas Foo. O processamento de cada regra exige a cópia de todas as origens transitivas que vieram antes dela em uma nova estrutura de dados. Isso significa que o custo de tempo e espaço para analisar uma biblioteca individual ou um destino binário é proporcional à própria altura na cadeia. Para uma cadeia de comprimento n, foolib_1 ← foolib_2 ← … ← foolib_n, o custo geral é efetivamente O(n^2).

De modo geral, os depsets precisam ser usados sempre que você estiver acumulando informações pelas dependências transitivas. Isso ajuda a garantir que seu build seja bem dimensionado à medida que o gráfico de destino se aprofunda.

Por fim, é importante não recuperar o conteúdo do depset desnecessariamente nas implementações de regras. Uma chamada para to_list() no final de uma regra binária é aceitável, já que o custo geral é apenas O(n). É quando muitos destinos não terminais tentam chamar to_list() que o comportamento quadrático ocorre.

Para mais informações sobre como usar depsets com eficiência, consulte a página de desempenho.

Referência da API

Consulte este link para mais detalhes.