디프 세트는 대상의 전이 종속 항목 간에 데이터를 효율적으로 수집하기 위한 특수한 데이터 구조입니다. 규칙 처리의 필수 요소이며
depset의 핵심 특징은 시간 및 공간 효율적인 유니온 연산입니다. depset 생성자는 요소 목록 ('direct') 및 다른 desets 목록 ('transitive')을 허용하고 모든 직접 요소와 모든 전이 요소의 통합을 포함하는 집합을 나타내는 depset를 반환합니다. 설정합니다. 개념적으로 생성자는 직접 노드와 전환 노드가 후속 작업으로 포함된 새로운 그래프 노드를 만듭니다. 종속 항목은 이 그래프의 순회를 기반으로 잘 정의된 순서 의미 체계를 갖습니다.
depset의 사용 예시는 다음과 같습니다.
프로그램 라이브러리의 모든 객체 파일 경로를 저장하여 제공자를 통해 링커 작업에 전달할 수 있습니다.
해석된 언어의 경우 실행 파일의 실행 파일에 포함된 전이 소스 파일을 저장합니다.
설명 및 작업
개념적으로 depset은 DAG (Directed Acyclic Graph)입니다. 일반적으로 대상 그래프와 유사합니다. 나 from에서 루트까지 생성됩니다. 종속 항목 체인의 각 타겟은 읽거나 복사하지 않고도 이전 콘텐츠 위에 자체 콘텐츠를 추가할 수 있습니다.
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은 자체와 같지만, 동일한 콘텐츠 및 동일한 내부 구조를 갖고 있더라도 다른 어떤 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의 전체 콘텐츠를 읽고 삭제할 요소를 필터링한 다음 새 deset를 다시 구성해야 합니다. 이는 비효율적입니다.
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를 순회합니다. 순회 종류는 deset가 구성될 때 지정된 순서에 따라 다릅니다. Bazel에서 입력 순서를 중요하게 여기는 경우가 많으므로 Bazel이 여러 주문을 지원하는 것이 유용합니다. 예를 들어 링커 작업이 B이 A에 종속되면 링커의 명령줄에서 B.o가 A.o 앞에 오도록 해야 할 수 있습니다. 다른 도구에는 반대 요구사항이 있을 수 있습니다.
postorder, preorder, topological의 3가지 순회 순서가 지원됩니다. 처음 두 개는 트리 순회와 동일하게 작동하며, DAG에서 작동하고 이미 방문한 노드를 건너뜁니다. 세 번째 순서는 루트에서 토폴로지로의 위상 정렬로 작동하며, 공유된 하위 요소가 모든 상위 요소 다음에 나열된다는 점만 제외하면 선주문과 동일합니다.
선주문과 사후 주문은 왼쪽에서 오른쪽으로 순회하지만 각 노드 내에서는 직접 하위 요소에 상대적인 순서가 없습니다. 토폴로지의 경우
왼쪽에서 오른쪽으로 보증이 적용되지 않으며, 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에 특수 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의 콘텐츠를 검색하지 않는 것이 중요합니다. 전체 비용은 O(n)이므로 바이너리 규칙의 끝에서 to_list()를 한 번 호출해도 괜찮습니다. 비터미널 대상이 to_list()를 호출하려고 할 때 2차 행동이 발생하는 경우입니다.
depset를 효율적으로 사용하는 방법에 대한 자세한 내용은 성능 페이지를 참조하세요.
API 참조
자세한 내용은 여기를 참고하세요.