Os depsets são uma estrutura de dados especializada para otimizar coletar dados nas dependências transitivas de um destino. Elas são essenciais elemento 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 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, a O construtor cria um novo nó de gráfico que tem os nós diretos e transitivos como sucessores. Os depsets têm uma semântica de ordenação bem definida, com base em travessia desse gráfico.
Exemplos de usos de depsets incluem:
Armazenar os caminhos de todos os arquivos de objetos das bibliotecas de um programa, que podem e, em seguida, passada para uma ação do vinculador por meio de um provedor.
Para uma linguagem interpretada, armazenar os arquivos de origem transitivos que são incluída nos arquivos de execução de um executável.
Descrição e operações
Conceitualmente, um desligamento é um gráfico acíclico dirigido (DAG) que normalmente tem a aparência semelhantes 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 à anterior sem ter que ler ou copiar.
Cada nó do DAG contém uma lista de elementos diretos e uma lista de nós filhos. O conteúdo do componente são os elementos transitivos, como os elementos diretos de todos os nós. Um novo dispositivo pode ser criado usando construtor depset: ele aceita uma lista de objetos 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 to_list(). Ela retorna uma lista de todas as chaves , sem incluir duplicatas. Não é possível inspecionar diretamente a estrutura precisa do DAG, embora essa estrutura não 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 ele mesmo, mas diferente de qualquer outro dispositivo, 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, deve ler todo o conteúdo do dispositivo, filtrar os elementos que você deseja remover e reconstruir uma nova instalaçã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 do order especificado no momento em que o dispositivo foi
construídas. É útil para o Bazel aceitar vários pedidos porque, às vezes,
se preocupam com a ordem das entradas. Por exemplo, uma ação de vinculador pode
é necessário 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 tree
travessias
exceto por operar em DAGs e ignorar os nós já visitados. A terceira ordem
funciona como uma classificação topológica da raiz às folhas, essencialmente da mesma forma que
pré-venda, exceto que as crianças compartilhadas são listadas somente depois de todos os pais.
As encomendas e as pós-encomendas funcionam como travessias da esquerda para a direita, mas observe
cada elemento direto de nó não tem ordem em relação aos filhos. Para topologia
não há garantia da esquerda para a direita, e até mesmo
a garantia all-parents-before-child não se aplica caso haja
duplicar elementos 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
o depset é criado com o argumento de palavra-chave order do construtor. Se esse
for omitido, o depset terá a ordem default especial, caso em que
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 saber todos os arquivos *.foo que ele ou
depende 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 em
os campos srcs de a, b, c e d. Para que foo_binary
para saber sobre qualquer arquivo além de d.foo, os destinos foo_library precisam
e transmiti-los em um provedor. Cada biblioteca recebe os provedores da própria
dependências, adiciona suas próprias origens 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"},
)
Você pode testar isso copiando esses arquivos em um novo pacote, renomeando o
rotule adequadamente, criando os arquivos *.foo de origem com conteúdo fictício e
criar o destino d.
Desempenho
Para entender a motivação para usar os recursos, considere o que aconteceria se
get_transitive_srcs() coletou 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 duplicatas, portanto, os arquivos de origem de a
vai aparecer duas vezes na linha de comando e duas vezes no conteúdo da 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 torna a ordem da linha de comando argumentos (e, portanto, o conteúdo dos arquivos) não especificados, embora ainda determinista.
Além disso, ambas as abordagens são assintoticamente piores do que as baseadas em abordagem humilde. Considere o caso em que há uma longa cadeia de dependências Bibliotecas Foo. O processamento de todas as regras requer a cópia de todas as fontes de dados que vieram antes para uma nova estrutura de dados. Isso significa que custo de tempo e espaço para analisar uma biblioteca individual ou um alvo 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, use os depssets sempre que você estiver acumulando informações por meio das dependências transitivas. Isso ajuda a garantir seu build escalona bem à medida que o gráfico de destino fica mais profundo.
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, porque o custo total é de apenas O(n). É
quando muitos destinos não terminais tentam chamar to_list() para um comportamento quadrático
de segurança.
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.