Os Depsets são uma estrutura de dados especializada para coletar dados de forma eficiente nas dependências transitivas de um destino. Elas são um elemento essencial do processamento de regras.
O recurso que define o depset é a operação de união eficiente em termos 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 objeto 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 que sã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) que normalmente é semelhante ao gráfico de destino. Ela é construída das folhas até a raiz. Cada destino em uma cadeia de dependência 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 extrair o conteúdo de um depset, use o método to_list(). Ele retorna uma lista de todos os elementos transitivos, sem incluir duplicatas. 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 pode não 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 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 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 realiza uma passagem pelo 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 de vinculação pode
precisar garantir que, se B depender de A, A.o vai aparecer 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. Para a ordem topológica, não há garantia da esquerda para a direita, e nem mesmo a garantia de que todos os pais estão antes dos filhos se aplica no caso de 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 esse
argumento for omitido, o depset terá a ordem especial default. Nesse caso,
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 exista uma linguagem interpretada hipotética Foo. Para criar
cada foo_binary, você precisa saber todos os arquivos *.foo em 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
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 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.
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 entender o motivo de 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[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
Isso não leva em conta os duplicados, portanto, 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.
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 duplicações, mas torna a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) não especificados, 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 à altura dele 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 fica mais profundo.
Por fim, é importante não recuperar o conteúdo do depset
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). Esse comportamento
ocorre 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 performance.
Referência da API
Confira mais detalhes neste link.