Tập hợp là một cấu trúc dữ liệu chuyên biệt để thu thập dữ liệu một cách hiệu quả trên các phần phụ thuộc bắc cầu của một mục tiêu. Chúng là một yếu tố thiết yếu của quá trình xử lý quy tắc.
Đặc điểm xác định của depset là hoạt động hợp nhất tiết kiệm thời gian và không gian. Hàm khởi tạo depset chấp nhận danh sách các phần tử ("trực tiếp") và danh sách các depset khác ("chuyển tiếp") và trả về một depset đại diện cho một tập hợp chứa tất cả các phần tử trực tiếp và tập hợp của tất cả các tập hợp bắc cầu. Về mặt lý thuyết, hàm khởi tạo sẽ tạo một nút biểu đồ mới, trong đó có các nút trực tiếp và nút bắc cầu là các nút kế thừa. Depset có ngữ nghĩa thứ tự được xác định rõ ràng, dựa trên việc duyệt qua biểu đồ này.
Ví dụ về cách sử dụng phần phụ:
Lưu trữ đường dẫn của tất cả các tệp đối tượng cho thư viện của chương trình. Sau đó, hệ thống có thể chuyển đường dẫn này đến hành động liên kết thông qua một trình cung cấp.
Đối với ngôn ngữ được diễn giải, hãy lưu trữ các tệp nguồn bắc cầu có trong tệp chạy của tệp thực thi.
Nội dung mô tả và thao tác
Về mặt khái niệm, depset là một biểu đồ không tuần hoàn có hướng (DAG) thường trông giống như biểu đồ mục tiêu. Nó được làm từ lá cho đến gốc. Mỗi mục tiêu trong một chuỗi phần phụ thuộc có thể thêm nội dung riêng lên trên mục tiêu trước đó mà không cần đọc hoặc sao chép nội dung đó.
Mỗi nút trong DAG chứa một danh sách các phần tử trực tiếp và một danh sách các nút con. Nội dung của depset là các phần tử bắc cầu, chẳng hạn như các phần tử trực tiếp của tất cả các nút. Bạn có thể tạo một phần phụ thuộc mới bằng hàm khởi tạo depset: hàm này chấp nhận danh sách các phần tử trực tiếp và một danh sách các nút con khác.
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"])
Để truy xuất nội dung của phần phụ thuộc, hãy sử dụng phương thức to_list(). Hàm này trả về danh sách tất cả các phần tử bắc cầu, không bao gồm các phần tử trùng lặp. Không có cách nào để trực tiếp kiểm tra cấu trúc chính xác của DAG, mặc dù cấu trúc này ảnh hưởng đến thứ tự trả về các phần tử.
s = depset(["a", "b", "c"])
print("c" in s.to_list()) # True
print(s.to_list() == ["a", "b", "c"]) # True
Các mục được phép trong một depset bị hạn chế, giống như các khoá được phép trong từ điển bị hạn chế. Cụ thể, nội dung tách rời có thể không thay đổi được.
Các phần phụ sử dụng đẳng thức tham chiếu: một tập hợp có giá trị bằng chính nó nhưng không bằng bất kỳ tập nào khác, ngay cả khi các tập đó có cùng nội dung và cấu trúc bên trong giống nhau.
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
Để so sánh các nhóm phần phụ thuộc theo nội dung, hãy chuyển đổi các nhóm phần phụ thuộc đó thành danh sách đã sắp xếp.
s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list())) # True
Không thể xoá các phần tử khỏi một depset. Nếu cần, bạn phải đọc toàn bộ nội dung của depset, lọc các phần tử bạn muốn xoá và tạo lại một depset mới. Cách này không đặc biệt hiệu quả.
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"])
Đặt
Toán tử to_list thực hiện việc duyệt qua DAG. Loại truyền tải phụ thuộc vào thứ tự được chỉ định tại thời điểm tạo phần tách. Bazel rất hữu ích khi hỗ trợ nhiều đơn đặt hàng vì đôi khi các công cụ quan tâm đến thứ tự đầu vào. Ví dụ: một thao tác của trình liên kết có thể cần đảm bảo rằng nếu B phụ thuộc vào A, thì A.o sẽ xuất hiện trước B.o trên dòng lệnh của trình liên kết. Các công cụ khác có thể có yêu cầu ngược lại.
3 thứ tự truyền tải được hỗ trợ: postorder, preorder và topological. Hai phần tử đầu tiên hoạt động giống hệt như truyền tải qua cây, ngoại trừ việc chúng hoạt động trên DAG và bỏ qua các nút đã truy cập. Thứ tự thứ ba hoạt động như một thứ tự tôpô từ gốc đến lá, về cơ bản giống như thứ tự đặt hàng trước, ngoại trừ việc các phần tử con được chia sẻ chỉ được liệt kê sau tất cả các phần tử mẹ.
Lệnh gọi trước và lệnh gọi sau hoạt động như các lượt truy cập từ trái sang phải, nhưng lưu ý rằng trong mỗi nút, các phần tử trực tiếp không có thứ tự tương ứng với các phần tử con. Đối với thứ tự cấu trúc liên kết, không có sự bảo đảm từ trái sang phải và thậm chí bảo đảm toàn thể mẹ trước con cũng không áp dụng trong trường hợp có các phần tử trùng lặp trong các nút khác nhau của 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"]
Do cách triển khai hoạt động duyệt qua, bạn phải chỉ định thứ tự tại thời điểm tạo nhóm phần phụ thuộc bằng đối số từ khoá order của hàm khởi tạo. Nếu đối số này bị bỏ qua, tập hợp sẽ có thứ tự default đặc biệt. Trong trường hợp đó, không có gì đảm bảo về thứ tự của bất kỳ phần tử nào (ngoại trừ việc phần tử đó mang tính tất định).
Ví dụ đầy đủ
Ví dụ này có tại https://github.com/bazelbuild/examples/tree/main/rules/depsets.
Giả sử có một ngôn ngữ được diễn giải giả định là Foo. Để tạo từng foo_binary, bạn cần biết tất cả các tệp *.foo mà phương thức đó trực tiếp hoặc gián tiếp phụ thuộc.
# //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())
Ở đây, các nguồn bắc cầu của d nhị phân là tất cả các tệp *.foo trong trường srcs của a, b, c và d. Để mục tiêu foo_binary biết về bất kỳ tệp nào ngoài d.foo, các mục tiêu foo_library cần truyền các tệp đó vào một trình cung cấp. Mỗi thư viện nhận trình cung cấp từ các phần phụ thuộc riêng, thêm các nguồn tức thì riêng và chuyển sang một trình cung cấp mới có nội dung tăng cường. Quy tắc foo_binary cũng hoạt động tương tự, ngoại trừ việc thay vì trả về một trình cung cấp, quy tắc này sử dụng danh sách đầy đủ các nguồn để tạo một dòng lệnh cho một thao tác.
Dưới đây là cách triển khai đầy đủ các quy tắc foo_library và 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"},
)
Bạn có thể kiểm thử điều này bằng cách sao chép các tệp này vào một gói mới, đổi tên nhãn sao cho phù hợp, tạo tệp *.foo nguồn có nội dung giả và tạo mục tiêu d.
Hiệu suất
Để xem động lực sử dụng depset, hãy cân nhắc điều gì sẽ xảy ra nếu get_transitive_srcs() thu thập các nguồn của nó trong một danh sách.
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[FooFiles].transitive_sources
trans_srcs += srcs
return trans_srcs
Lệnh này không tính đến các tệp trùng lặp, vì vậy, các tệp nguồn cho a sẽ xuất hiện hai lần trên dòng lệnh và hai lần trong nội dung của tệp đầu ra.
Một giải pháp thay thế là sử dụng tập hợp chung, có thể được mô phỏng bằng một từ điển trong đó các khoá là các phần tử và tất cả các khoá ánh xạ đến 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
Thao tác này giúp loại bỏ các nội dung trùng lặp, nhưng làm cho thứ tự của các đối số dòng lệnh (và do đó là nội dung của các tệp) không được chỉ định, mặc dù vẫn có tính xác định.
Hơn nữa, cả hai phương pháp này đều kém hiệu quả hơn so với phương pháp dựa trên phần cài đặt. Hãy xem xét trường hợp có một chuỗi phần phụ thuộc dài trên thư viện Foo. Để xử lý mọi quy tắc, bạn cần sao chép tất cả các nguồn bắc cầu trước đó vào một cấu trúc dữ liệu mới. Điều này có nghĩa là thời gian và chi phí không gian để phân tích một thư viện hoặc mục tiêu nhị phân riêng lẻ tỷ lệ với chiều cao của chính thư viện hoặc mục tiêu đó trong chuỗi. Đối với một chuỗi có độ dài n, foolib_1 ← foolib_2 ← … ← foolib_n, chi phí tổng thể hiệu quả là O(n^2).
Nói chung, bạn nên sử dụng phần lồng ghép bất cứ khi nào bạn đang tích luỹ thông tin thông qua các phần phụ thuộc bắc cầu. Điều này giúp đảm bảo bản dựng điều chỉnh theo tỷ lệ khi biểu đồ mục tiêu phát triển sâu hơn.
Cuối cùng, điều quan trọng là không truy xuất nội dung của depset một cách không cần thiết trong quá trình triển khai quy tắc. Một lệnh gọi đến to_list() ở cuối trong quy tắc nhị phân là ổn, vì chi phí tổng thể chỉ là O(n). Đó là khi nhiều mục tiêu không phải là đích cuối cố gắng gọi to_list(), hành vi bậc hai sẽ xảy ra.
Để biết thêm thông tin về cách sử dụng depset một cách hiệu quả, hãy xem trang hiệu suất.
Tài liệu tham khảo API
Vui lòng xem tại đây để biết thêm thông tin chi tiết.