디셋

<ph type="x-smartling-placeholder"></ph> 문제 신고 <ph type="x-smartling-placeholder"></ph> 소스 보기 1박 · 7.3 · 7.2 · 7.1 · 7.0 · 6.5

Depset은 효율적으로 사용하기 위한 특수 데이터 구조입니다. 대상의 전이 종속 항목에서 데이터를 수집합니다 Kubernetes는 확인할 수 있습니다.

depset의 결정적인 특징은 시간과 공간 효율적인 union 연산입니다. depset 생성자는 요소 목록('direct') 및 다른 depsets('transitive')를 포함하고, 모든 직접 요소와 모든 전이 집합의 합집합입니다. 개념적으로 생성자는 직접 노드와 전이 노드가 있는 새 그래프 노드를 만듭니다. 역할을 맡고 있습니다. 종속 항목은 잘 정의된 순서 시맨틱을 가지고 있으며 이 그래프의 순회입니다.

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() 메서드에 전달합니다. 이 함수는 모든 과도기적 유형 목록을 반환합니다. 요소가 포함됩니다. SSL을 직접 검사할 수 있는 방법은 이 구조는 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

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

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를 통해 순회합니다. 순회 유형 배포 시 지정된 order에 따라 다름 있습니다. Bazel이 여러 주문을 지원하는 것이 유용한 이유는 도구는 입력의 순서에 신경을 쓰는 것입니다. 예를 들어 링커 작업은 BA에 종속되는 경우 A.oB.o 앞에 오도록 해야 사용할 수 있습니다 다른 도구의 요구사항은 반대일 수도 있습니다.

세 가지 순회 순서(postorder, preorder, topological입니다. 처음 두 개의 함수는 tree와 정확히 비슷합니다. 순회 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"]

순회가 구현되는 방식으로 인해 순서가 지정된 시점에 지정되어야 합니다. depset은 생성자의 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의 전이 소스는 *.foo a, b, c, dsrcs 필드 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 타겟 빌드

성능

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

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

게다가 두 접근 방식 모두 디플셋 기반 접근 방식보다 점근적으로 더 나쁘다. 접근하는 것입니다. 한 프로젝트에 긴 종속 항목 체인이 있는 경우를 생각해 봅시다. Foo 라이브러리 모든 규칙을 처리하려면 전이 규칙을 모두 복사해야 함 데이터를 새로운 데이터 구조로 변환할 수 있습니다. 즉, 개별 라이브러리 또는 바이너리 타겟을 분석하는 데 드는 시간 및 공간 비용 체인의 자체 높이에 비례합니다. 길이 n 체인의 경우, foolib_1 ← foolib_2 ← ... ← foolib_n, 전체 비용은 사실상 O(n^2)입니다.

일반적으로, 축적될 때마다 depset를 사용해야 합니다. 정보를 제공합니다 이렇게 하면 대상 그래프가 더 깊어질수록 빌드가 확장됩니다.

마지막으로, depset의 콘텐츠를 검색하지 않는 것이 중요합니다. 사용할 수 있습니다. to_list()번으로 거는 전화 1건 전체 비용이 O(n)이기 때문에 괜찮습니다. 그것은 터미널이 아닌 많은 타겟이 이차 동작인 to_list()를 호출하려고 할 때 발생합니다

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

API 참조

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