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.

O atributo que define o depset é a operação de união com eficiência de tempo e espaço. O construtor depset aceita uma lista de elementos ("direct") e uma lista de outros depsets ("transitivos") 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 grafo 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.

Veja alguns exemplos de uso de depsets:

• Armazenamento dos caminhos de todos os arquivos de objeto das bibliotecas de um programa, que podem ser passados a uma ação do vinculador por meio de um provedor.

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

Descrição e operações

Conceitualmente, um depset é um gráfico acíclico dirigido (DAG, na sigla em inglês) que normalmente é 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 sobre o 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 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 dados, use o método to_list(). Ela retorna uma lista de todos os elementos transitivos, sem incluir os duplicados. Não há como inspecionar diretamente a estrutura precisa do DAG, embora ela 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 nos dicionários são restritas. Especificamente, o conteúdo depset pode não ser mutável.

Os dessets usam a igualdade de referência: um depset é igual a si mesmo, mas diferente de qualquer outro, mesmo que tenha 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 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 repositório. Se isso for necessário, leia todo o conteúdo do depset, filtre os elementos que você quer remover e reconstrua um novo depset. 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 sobre o DAG. O tipo de travessia depende da ordem especificada no momento em que a dependência foi construída. É útil que o Bazel ofereça suporte a vários pedidos porque, às vezes, as ferramentas se importam 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 aceitas: postorder, preorder e topological. Os dois primeiros funcionam exatamente como travessias em árvore, exceto que operam em DAGs e pulam nós já visitados. A terceira ordem funciona como uma classificação topológica da raiz às folhas, essencialmente igual à pré-venda, exceto pelo fato de que os filhos compartilhados são listados somente depois de todos os pais. A pré-venda e o pós-pedido funcionam como travessias da esquerda para a direita, mas, em cada nó, os elementos diretos não têm ordem em relação aos filhos. Em ordem topológica, não há garantia da esquerda para a direita, e até mesmo a garantia "all-pais-antes-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 os traversals são implementados, 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 depset terá a ordem especial default. Nesse caso, não há garantias sobre a ordem de qualquer um dos elementos, exceto que ele é determinístico.

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, 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, ela usa a lista completa de origens para criar uma linha de comando para uma ação.

Veja 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"},
)

É possível testar isso copiando esses arquivos em um novo pacote, renomeando os rótulos adequadamente, criando os arquivos *.foo de origem com conteúdo fictício e criando o destino d.

Performance

Para conferir 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[FooFiles].transitive_sources
  trans_srcs += srcs
  return trans_srcs

Isso não considera cópias. 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 cópias, mas deixa a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) não especificada, embora ainda determinista.

Além disso, ambas as abordagens são assintoticamente piores do que a abordagem baseada no abandono. Considere o caso em que há uma longa cadeia de dependências nas bibliotecas Foo. O processamento de cada regra requer 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 total é efetivamente O(n^2).

De modo geral, os repositórios precisam ser usados sempre que você estiver acumulando informações nas dependências transitivas. Isso ajuda a garantir que seu build seja dimensionado à medida que o gráfico de destino cresça.

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

Para ver mais informações sobre o uso eficiente de depsets, consulte a página Performance.

Referência da API

Clique aqui para ver mais detalhes.