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.