Dependências

Informar um problema Ver fonte Nightly · 8.3 · 8.2 · 8.1 · 8.0 · 7.6

Depsets são uma estrutura de dados especializada para coletar dados de maneira eficiente em todas as dependências transitivas de um destino. Eles são um elemento essencial do processamento de regras.

O recurso definidor de depset é a operação de união eficiente em tempo e espaço. O construtor de depset aceita uma lista de elementos ("diretos") e uma lista de outros depsets ("transitivos") e retorna um depset que representa um conjunto com 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 depsets têm uma semântica de ordenação bem definida, com base na travessia desse gráfico.

Exemplos de usos de conjuntos de dependências:

  • Armazenar os caminhos de todos os arquivos de objeto para as bibliotecas de um programa, que podem ser transmitidos para uma ação de vinculador por um provedor.

  • Para uma linguagem interpretada, armazene os arquivos de origem transitivos incluídos nos runfiles de um executável.

Descrição e operações

Conceitualmente, um depset é um gráfico acíclico direcionado (DAG) que normalmente se parece com o gráfico de destino. Ela é construída das folhas até a raiz. Cada destino em uma cadeia de dependências pode adicionar seu próprio conteúdo em cima do anterior sem precisar lê-lo ou copiá-lo.

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 dependências, use o método to_list(). Ela retorna uma lista de todos os elementos transitivos, sem incluir duplicados. Não é possível inspecionar diretamente a estrutura precisa do DAG, mas ela afeta 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 conjunto de dependências são restritos, assim como as chaves permitidas em dicionários. Em especial, o conteúdo de um conjunto de dependências não pode ser mutável.

Os depsets usam igualdade de referência: um depset é igual a si mesmo, mas diferente de qualquer outro depset, 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 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 isso for necessário, leia todo o conteúdo do conjunto de dependências, filtre os elementos que você quer remover e reconstrua um novo conjunto. 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 travessia no DAG. O tipo de travessia depende da ordem especificada quando o conjunto de dependências foi construído. É útil que o Bazel ofereça suporte a várias ordens porque, às vezes, as ferramentas se importam com a ordem das entradas. Por exemplo, uma ação de 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.

Há três ordens de travessia compatíveis: postorder, preorder e topological. Os dois primeiros funcionam exatamente como percursos de árvore, exceto que operam em DAGs e ignoram nós já visitados. A terceira ordem funciona como uma classificação topológica da raiz até as folhas, essencialmente a mesma que a pré-ordem, exceto que os filhos compartilhados são listados somente depois de todos os pais. As ordens prévia e posterior operam como travessias da esquerda para a direita, mas observe que, em cada nó, os elementos diretos não têm ordem em relação aos filhos. Para a 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 no caso de elementos duplicados em diferentes nós 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 conjunto de dependências é 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 é determinista.

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, é preciso saber 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 binário d são todos os arquivos *.foo nos campos srcs de a, b, c e d. Para que o destino foo_binary conheça 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, mas, em vez de retornar um provedor, ela usa a lista completa de fontes 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.
foo_files = 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[foo_files].transitive_sources for dep in deps])

def _foo_library_impl(ctx):
  trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
  return [foo_files(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, copie esses arquivos para um novo pacote, renomeie os rótulos de maneira adequada, crie os arquivos de origem *.foo com conteúdo fictício e crie a meta d.

Desempenho

Para entender 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[foo_files].transitive_sources
  trans_srcs += srcs
  return trans_srcs

Isso não considera 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.

Outra opção é 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[foo_files].transitive_sources:
      trans_srcs[file] = True
  for file in srcs:
    trans_srcs[file] = True
  return trans_srcs

Isso elimina os duplicados, mas torna a ordem dos argumentos da linha de comando (e, portanto, o conteúdo dos arquivos) não especificada, embora ainda determinista.

Além disso, as duas abordagens são assintoticamente piores do que a abordagem baseada em depset. Considere o caso em que há uma longa cadeia de dependências nas bibliotecas Foo. Para processar cada regra, é necessário copiar todas as fontes transitivas anteriores em uma nova estrutura de dados. Isso significa que o custo de tempo e espaço para analisar uma biblioteca ou um destino binário individual é proporcional à altura dele na cadeia. Para uma cadeia de comprimento n, foolib_1 ← foolib_2 ← … ← foolib_n, o custo geral é efetivamente O(n^2).

Em geral, os depsets devem ser usados sempre que você estiver acumulando informações pelas dependências transitivas. Isso ajuda a garantir que seu build seja bem dimensionado à medida que o gráfico de destino aumenta.

Por fim, é importante não recuperar o conteúdo do depset desnecessariamente nas 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). Isso acontece 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 desempenho.

Referência da API

Consulte este link para mais detalhes.