Dependências

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

A característica definidora do depset é a operação de união com economia de tempo e espaço. O construtor depset aceita uma lista de elementos ("direto") e uma lista de outros depsets ("transitivo") e retorna um depset que representa um conjunto contendo 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 conjuntos de dependências têm uma semântica de ordenação bem definida, com base na transposição desse gráfico.

Confira alguns exemplos de uso de depsets:

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

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

Descrição e operações

Conceitualmente, uma desativação é um gráfico acíclico dirigido (DAG, na sigla em inglês) que normalmente é semelhante ao gráfico de destino. Ela é construída das folhas até a raiz. Cada destino em uma cadeia de dependências pode adicionar o próprio conteúdo sobre o anterior sem precisar ler ou copiar o conteúdo.

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 depset, use o método to_list(). Ela retorna uma lista de todos os elementos transitivos, sem incluir cópias. Não há como inspecionar diretamente a estrutura exata 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. Em particular, o conteúdo depset não pode ser mutável.

Os conjuntos de dependências usam igualdade de referência: um conjunto de dependências é igual a si mesmo, mas não é igual a nenhum outro conjunto, mesmo que eles 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 os recursos 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, leia todo o conteúdo do dispositivo, filtre os elementos que você quer remover e reconstrua uma nova desativação. 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 executa uma travessia no DAG. O tipo de travessia depende da ordem especificada no momento em que o depset foi criado. É ú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 do 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.

Três ordens de travessia são compatíveis: postorder, preorder e topological. As duas primeiras funcionam exatamente como percursos de árvores, exceto que operam em DAGs e pulam 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 as crianças compartilhadas são listadas somente depois de todos os pais. A pré-ordem e a pós-ordem operam como transições da esquerda para a direita, mas observe que, em cada nó, os elementos diretos não têm ordem relativa aos filhos. Na ordem topológica, não há garantia da esquerda para a direita, e até mesmo a garantia de todos os pais antes do filho não se aplica caso haja 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 armazenamento é criado com o argumento de palavra-chave order do construtor. Se esse argumento for omitido, o depset terá a ordem default especial. Nesse caso, não há garantias sobre a ordem de nenhum dos elementos, exceto que é determinista.

Exemplo completo

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

Suponha que haja uma linguagem hipotética interpretada Foo. Para criar cada foo_binary, você precisa conhecer todos os arquivos *.foo de que ela 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 saiba sobre 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, exceto que, em vez de retornar um provedor, ele usa a lista completa de origens 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.
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 testar isso, 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 conferir a motivação para usar dependências, 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[FooFiles].transitive_sources
  trans_srcs += srcs
  return trans_srcs

Isso não leva em conta duplicatas, portanto, os arquivos de origem de a aparecerão duas vezes na linha de comando e duas vezes no conteúdo do arquivo de saída.

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[FooFiles].transitive_sources:
      trans_srcs[file] = True
  for file in srcs:
    trans_srcs[file] = True
  return trans_srcs

Isso elimina as duplicatas, mas faz com que a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) seja não especificado, embora ainda determinístico.

Além disso, as duas abordagens são assintóticamente piores do que a abordagem baseada em depset. Considere o caso em que há uma longa cadeia de dependências nas 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(n2).

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

Por fim, é importante não recuperar o conteúdo do dispositivo desnecessariamente em 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 ocorre um comportamento quadrático.

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

Referência da API

Clique aqui para mais detalhes.