디셋

컬렉션을 사용해 정리하기 내 환경설정을 기준으로 콘텐츠를 저장하고 분류하세요.
문제 신고 출처 보기

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

depset의 정의 기능은 시간과 공간을 절약하는 유니온 연산입니다. depset 생성자는 요소 목록('direct')과 다른 Depset 목록('transitive')을 허용하고 모든 직접 요소 및 모든 전이적 집합의 합집합을 포함하는 집합을 반환합니다. 개념적으로 생성자는 직접 및 전환 노드가 후속 버전으로 포함된 새 그래프 노드를 만듭니다. 디셋에는 이 그래프의 순회를 기반으로 하는 순서 지정 시맨틱스가 잘 정의되어 있습니다.

디셋 사용의 예는 다음과 같습니다.

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

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

설명 및 작업

개념적으로 디셋은 일반적으로 타겟 그래프와 유사한 방향성 비순환 그래프 (DAG)입니다. 잎부터 뿌리까지 구성됩니다. 종속 항목 체인의 각 대상은 읽거나 복사할 필요 없이 이전 항목 위에 자체 콘텐츠를 추가할 수 있습니다.

DAG의 각 노드에는 직접 요소 목록과 하위 노드 목록이 있습니다. 디셋의 콘텐츠는 모든 노드의 직접 요소와 같은 전이 요소입니다. 새 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과 같지만 같지 않습니다.

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

콘텐츠를 기준으로 디플레이를 비교하려면 정렬된 목록으로 변환합니다.

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

디셋에서 요소를 삭제할 수 있는 기능은 없습니다. 이 작업이 필요하면 오프셋의 전체 내용을 읽고, 삭제하려는 요소를 필터링한 후 새 오프셋을 재구성해야 합니다. 이는 특히 비효율적입니다.

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를 순회합니다. 순회 종류는 디셋이 구성될 때 지정된 순서에 따라 다릅니다. 도구는 입력 순서를 중시하는 경우가 많으므로 Bazel이 여러 주문을 지원하는 데 유용합니다. 예를 들어 링커 작업이 BA에 종속된 경우 A.o이 링커의 명령줄에서 B.o 앞에 오도록 해야 할 수 있습니다. 다른 도구의 요구사항은 반대일 수 있습니다.

세 가지 순회 순서 postorder, preorder, topological가 지원됩니다. 처음 두 개는 트리 순회와 동일하게 작동하며 DAG에서 작동하고 이미 방문한 노드를 건너뜁니다. 세 번째 순서는 루트에서 나뭇잎까지 토폴로지로 정렬되며, 기본적으로 모든 하위 요소가 상위 요소 다음에 표시된다는 점을 제외하면 선주문과 동일합니다. 선주문과 사후 주문은 왼쪽에서 오른쪽으로 순회하는 것처럼 작동하지만 각 노드 내에는 하위 요소의 상대적인 요소에는 순서가 없습니다. 토폴로지 주문의 경우 왼쪽에서 오른쪽으로 보장되는 기능이 없으며 DAG의 여러 노드에 중복된 요소가 있는 경우 all-parents-before-child도 적용되지 않습니다.

# 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에 특수한 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의 전이적 소스는 a, b, c, dsrcs 필드에 있는 모든 *.foo 파일입니다. foo_binary 타겟이 d.foo 이외의 파일을 알 수 있도록 foo_library 타겟은 제공자에 이러한 파일을 전달해야 합니다. 각 라이브러리는 자체 종속 항목에서 제공업체를 수신하고 고유한 자체 소스를 추가하며 증강 콘텐츠가 포함된 새 제공업체를 전달합니다. foo_binary 규칙은 제공자를 반환하는 대신 작업의 전체 목록을 사용하여 작업의 명령줄을 생성한다는 점을 제외하고는 동일합니다.

다음은 foo_libraryfoo_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 타겟을 빌드하여 이를 테스트할 수 있습니다.

실적

디셋을 사용하는 동기를 확인하려면 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

이렇게 하면 중복이 제거되지만 명령줄 인수 (및 파일의 콘텐츠)의 순서가 확정되지만 여전히 지정되지 않습니다.

게다가 두 접근 방식 모두 디셋 기반 접근 방식보다 점근적이 좋지 않습니다. Foo 라이브러리에 종속 항목 체인이 긴 경우를 생각해 보세요. 모든 규칙을 처리하려면 규칙 대신 이전에 추가된 모든 전환 소스를 새 데이터 구조로 복사해야 합니다. 즉, 개별 라이브러리나 바이너리 타겟을 분석하는 데 걸리는 시간과 공간 비용은 체인의 자체 높이에 비례합니다. 연이어 n인 foolib_1 ← foolib_2 ← ← foolib_n의 경우 전체 비용은 사실상 O(n^2)입니다.

일반적으로 전이 종속 항목을 통해 정보를 축적할 때마다 depset을 사용해야 합니다. 이렇게 하면 타겟 그래프가 깊어질 때 빌드가 잘 확장됩니다.

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

디셋을 효율적으로 사용하는 방법에 대한 자세한 내용은 성능 페이지를 참조하세요.

API 참조

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