디셋

Nightly · 9.1 · 9.0 · 8.7 · 8.6 · 8.5 · 8.4 · 8.3 · 8.2 · 8.1

Depset은 대상의 전이 종속 항목에서 데이터를 효율적으로 수집하기 위한 특수 데이터 구조입니다. 이는 규칙 처리의 필수 요소입니다.

depset의 정의 기능은 시간 및 공간 효율적인 합집합 작업입니다. depset 생성자는 요소 목록('직접')과 다른 depset 목록('전이')을 허용하고 모든 직접 요소와 모든 전이 집합의 결합을 포함하는 집합을 나타내는 depset을 반환합니다. 개념적으로 생성자는 직접 및 전이 노드를 후속 노드로 갖는 새 그래프 노드를 만듭니다. Depset은 이 그래프의 순회에 따라 잘 정의된 순서 지정 시맨틱스를 갖습니다.

depset 사용 예는 다음과 같습니다.

  • 프로그램 라이브러리의 모든 객체 파일 경로를 저장합니다. 그런 다음 제공자를 통해 링커 작업에 전달할 수 있습니다.

  • 해석된 언어의 경우 실행 파일의 실행 파일에 포함된 전이 소스 파일을 저장합니다.

설명 및 작업

개념적으로 depset은 일반적으로 대상 그래프와 유사한 방향성 비순환 그래프 (DAG)입니다. 리프에서 루트까지 구성됩니다. 종속 항목 체인의 각 대상은 이전 콘텐츠를 읽거나 복사하지 않고도 자체 콘텐츠를 추가할 수 있습니다.

DAG의 각 노드는 직접 요소 목록과 하위 노드 목록을 보유합니다. depset의 콘텐츠는 모든 노드의 직접 요소와 같은 전이 요소입니다. depset 생성자를 사용하여 새 depset을 만들 수 있습니다. 직접 요소 목록과 하위 노드 목록을 허용합니다.

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"])

depset의 콘텐츠를 가져오려면 to_list() 메서드를 사용하세요. 중복을 포함하지 않고 모든 전이 요소 목록을 반환합니다. 이 구조는 요소가 반환되는 순서에 영향을 주지만 DAG의 정확한 구조를 직접 검사할 방법은 없습니다.

s = depset(["a", "b", "c"])

print("c" in s.to_list())              # True
print(s.to_list() == ["a", "b", "c"])  # True

depset에서 허용되는 항목은 딕셔너리에서 허용되는 키와 마찬가지로 제한됩니다. 특히 depset 콘텐츠는 변경할 수 없습니다.

Depset은 참조 동등성을 사용합니다. depset은 자체적으로 동일하지만 콘텐츠와 내부 구조가 동일하더라도 다른 depset과 동일하지 않습니다.

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

콘텐츠별로 depset을 비교하려면 정렬된 목록으로 변환하세요.

s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list()))  # True

depset에서 요소를 삭제할 수 없습니다. 이 작업이 필요한 경우 depset의 전체 콘텐츠를 읽고 삭제할 요소를 필터링한 후 새 depset을 재구성해야 합니다. 특히 효율적이지는 않습니다.

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"])

주문

to_list 작업은 DAG를 순회합니다. 순회 유형은 depset이 구성될 때 지정된 순서 에 따라 다릅니다. 도구가 입력 순서를 고려하는 경우가 있으므로 Bazel에서 여러 순서를 지원하는 것이 유용합니다. 예를 들어 링커 작업은 B가 A에 종속되는 경우 링커의 명령줄에서 A.o가 B.o 앞에 오도록 해야 할 수 있습니다. 다른 도구에는 반대 요구사항이 있을 수 있습니다.

세 가지 순회 순서(postorder, preorder, topological)가 지원됩니다. 처음 두 개는 트리 순회 에서 작동하고 이미 방문한 노드를 건너뛴다는 점을 제외하고는 트리 순회와 정확히 동일하게 작동합니다. 세 번째 순서는 루트에서 리프까지의 위상 정렬로 작동하며, 기본적으로 공유 하위 요소가 모든 상위 요소 뒤에만 나열된다는 점을 제외하고는 사전 순서와 동일합니다. 사전 순서 및 사후 순서는 왼쪽에서 오른쪽으로 순회로 작동하지만 각 노드 내에서 직접 요소는 하위 요소와 관련된 순서가 없습니다. 위상 순서의 경우 왼쪽에서 오른쪽으로 보장되지 않으며 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"]

순회가 구현되는 방식 때문에 생성자의 order 키워드 인수를 사용하여 depset이 생성될 때 순서를 지정해야 합니다. 이 인수가 생략되면 depset에는 특수한 default 순서가 있습니다. 이 경우 요소의 순서에 대한 보장이 없습니다 (결정적이라는 점 제외).

전체 예

이 예는 https://github.com/bazelbuild/examples/tree/main/rules/depsets에서 확인할 수 있습니다.

가상의 해석된 언어 Foo가 있다고 가정해 보겠습니다. 각 foo_binary를 빌드하려면 직접 또는 간접적으로 종속되는 모든 *.foo 파일을 알아야 합니다.

# //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())

여기서 바이너리 d의 전이 소스는 *.foo 파일의 srcs 필드에 있는 모든 a, b, c, d입니다. foo_binary 대상이 d.foo 외의 파일을 인식하려면 foo_library 대상이 제공자를 통해 전달해야 합니다. 각 라이브러리는 자체 종속 항목에서 제공자를 수신하고 자체 직접 소스를 추가하며 증강된 콘텐츠가 포함된 새 제공자를 전달합니다. foo_binary 규칙도 동일한 작업을 수행하지만 제공자를 반환하는 대신 소스의 전체 목록을 사용하여 작업의 명령줄을 구성합니다.

foo_library 및 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"},
)

이러한 파일을 새 패키지에 복사하고 라벨 이름을 적절하게 변경하고 더미 콘텐츠가 포함된 소스 *.foo 파일을 만든 후 d 대상을 빌드하여 테스트할 수 있습니다.

성능

depset을 사용하는 동기를 확인하려면 get_transitive_srcs()가 목록에서 소스를 수집하는 경우 어떻게 되는지 고려해 보세요.

def get_transitive_srcs(srcs, deps):
  trans_srcs = []
  for dep in deps:
    trans_srcs += dep[FooFiles].transitive_sources
  trans_srcs += srcs
  return trans_srcs

이렇게 하면 중복이 고려되지 않으므로 a의 소스 파일이 명령줄에 두 번, 출력 파일의 콘텐츠에 두 번 표시됩니다.

대안은 일반 집합을 사용하는 것입니다. 키가 요소이고 모든 키가 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

이렇게 하면 중복이 제거되지만 명령줄 인수의 순서 (따라서 파일의 콘텐츠)가 결정적이지만 지정되지 않습니다.

또한 두 접근 방식 모두 depset 기반 접근 방식보다 점근적으로 더 나쁩니다. Foo 라이브러리에 긴 종속 항목 체인이 있는 경우를 고려해 보세요. 모든 규칙을 처리하려면 그 앞에 있는 모든 전이 소스를 새 데이터 구조에 복사해야 합니다. 즉, 개별 라이브러리 또는 바이너리 대상을 분석하는 데 드는 시간과 공간 비용은 체인에서 자체 높이에 비례합니다. 길이가 n인 체인 foolib_1 ← foolib_2 ← … ← foolib_n의 경우 전체 비용은 효과적으로 O(n^2)입니다.

일반적으로 전이 종속 항목을 통해 정보를 누적할 때는 depset을 사용해야 합니다. 이렇게 하면 대상 그래프가 깊어짐에 따라 빌드가 잘 확장됩니다.

마지막으로 규칙 구현에서 depset의 콘텐츠를 불필요하게 가져오지 않는 것이 중요합니다. 바이너리 규칙의 끝에 to_list()를 한 번 호출하는 것은 괜찮습니다. 전체 비용은 O(n)이기 때문입니다. 많은 비터미널 대상이 to_list()를 호출하려고 할 때 이차 동작이 발생합니다.

depset을 효율적으로 사용하는 방법에 관한 자세한 내용은 성능 페이지를 참고하세요.

API 참조

자세한 내용은 여기를 참고하세요.