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.