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 ("direct") e uma lista de outras dependências ("transitivas") e retorna uma dependência que representa um conjunto que contém 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. As dependências têm uma semântica de ordenação bem definida, com base na travessia desse gráfico.
Exemplos de usos de depsets incluem:
Armazenamento dos caminhos de todos os arquivos de objetos das bibliotecas de um programa, que podem ser passadas para uma ação do vinculador 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ó do 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 precisa 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 são restritos. Especificamente, o conteúdo de desativação pode não ser mutável.
Os depsets usam a igualdade de referência: um depset é igual a si mesmo, mas diferente de qualquer outro, mesmo que 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 dispositivo. 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 armazenamento foi criado. É útil que o Bazel dê suporte a vários pedidos 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 travessias de árvores, exceto que operam em DAGs e ignoram os nós já visitados. A terceira ordem funciona como uma classificação topológica da raiz às folhas, essencialmente igual à pré-venda, exceto que os filhos compartilhados são listados somente depois de todos os pais.
As encomendas e as pós-vendas funcionam como travessias 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 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 qualquer um 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 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 d
binário 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.
Veja aqui 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"},
)
Teste 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
.
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 cópias, mas torna a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) não especificada, embora ainda seja determinista.
Além disso, ambas as abordagens são assintoticamente piores do que a baseada em desenvolvimento. Considere o caso em que há uma longa cadeia de dependências nas bibliotecas Foo. Para processar todas as regras, é preciso copiar todas as origens transitivas que vieram antes para uma nova estrutura de dados. Isso significa que o custo de tempo e espaço para analisar uma biblioteca individual ou 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 depssets precisam ser usados sempre que você estiver acumulando informações por meio das dependências transitivas. Isso ajuda a garantir que o build seja bem dimensionado à medida que o gráfico de destino cresce.
Por fim, é importante não recuperar o conteúdo do dispositivo
desnecessariamente em implementações de regras. Uma chamada para to_list()
no final em uma regra binária é adequada, já que o custo total é apenas de 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 detecções com eficiência, consulte a página de desempenho.
Referência da API
Clique aqui para mais detalhes.