Dependências

Os depsets são uma estrutura de dados especializada para coletar dados de maneira eficiente em todas as dependências transitivas de um destino. Eles são um elemento essencial do processamento de regras.

O recurso definidor de 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 com 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 na travessia desse gráfico.

Exemplos de uso de conjuntos de dependências:

• 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, armazena os arquivos de origem transitivos incluídos nos runfiles de um executável.

Descrição e operações

Conceitualmente, um depset é um gráfico acíclico dirigido (DAG) que geralmente se parece com o gráfico de destino. Ele é construído das folhas até a raiz. Cada destino em uma cadeia de dependências pode adicionar seu próprio conteúdo em cima do anterior sem precisar lê-lo ou copiá-lo.

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 construtor depset: 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 conjunto de dependências, use o método to_list(). Ela retorna uma lista de todos os elementos transitivos, sem incluir duplicados. Não é possível inspecionar diretamente a estrutura precisa do DAG, mas ela afeta 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. Em especial, o conteúdo de um depset não pode ser mutável.

As depset usam igualdade de referência: uma depset é igual a si mesma, mas diferente de qualquer outra 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 conjunto de dependências. Se isso for necessário, leia todo o conteúdo do conjunto de dependências, filtre os elementos que você quer remover e reconstrua um novo conjunto. Isso não é muito 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 realiza uma travessia no DAG. O tipo de travessia depende da ordem especificada quando o conjunto de dependências foi construído. É útil que o Bazel ofereça suporte a várias ordens porque, às vezes, as ferramentas se importam 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á três ordens de travessia compatíveis: postorder, preorder e topological. Os dois primeiros funcionam exatamente como percursos 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 até as folhas, essencialmente igual à pré-ordem, exceto que os filhos compartilhados são listados somente depois de todos os pais. As ordens prévia e posterior 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 diferentes nós 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 esse argumento for omitido, o conjunto de dependências terá a ordem especial default. Nesse caso, não há garantias sobre a ordem de nenhum dos elementos, exceto que ela é determinista.

Exemplo completo

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

Suponha que exista uma linguagem interpretada hipotética Foo. Para criar cada foo_binary, é preciso saber 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 destino foo_binary conheça qualquer arquivo além de d.foo, os destinos foo_library precisam transmiti-los em um provedor. Cada biblioteca recebe os provedores das próprias dependências, adiciona as próprias fontes imediatas e transmite um novo provedor com o conteúdo aumentado. A regra foo_binary faz o mesmo, mas, em vez de retornar um provedor, ela usa a lista completa de fontes para criar 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 adequadamente, crie os arquivos de origem *.foo com conteúdo fictício e crie o destino d.

Desempenho

Para entender a motivação do uso de depsets, considere o que aconteceria se get_transitive_srcs() coletasse as fontes 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 considera duplicatas. Portanto, os arquivos de origem para a aparecerão duas vezes na linha de comando e duas vezes no conteúdo do arquivo de saída.

Outra opção é 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 determinista.

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 nas bibliotecas Foo. Para processar cada regra, é necessário copiar todas as fontes 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 ou um destino binário individual é 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).

Em geral, os depsets devem 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 aumenta.

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). Isso acontece quando muitos destinos não terminais tentam chamar to_list().

Para mais informações sobre como usar depsets de maneira eficiente, consulte a página desempenho.

Referência da API

Consulte este link para mais detalhes.