Depset 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ục tiêu. Đây là một thành phần thiết yếu của quá trình xử lý quy tắc.
Tính năng xác định của depset là thao tác hợp nhất hiệu quả về thời gian và không gian. Hàm khởi tạo depset chấp nhận một danh sách các phần tử ("trực tiếp") và một danh sách các depset khác ("bắc cầu") rồi 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à hợp nhất tất cả các tập hợp bắc cầu. Về mặt khái niệm, hàm khởi tạo sẽ tạo một nút biểu đồ mới có các nút trực tiếp và bắc cầu làm nút kế thừa. Depset có ngữ nghĩa sắp xếp được xác định rõ ràng, dựa trên việc di chuyển biểu đồ này.
Sau đây là một số ví dụ về cách sử dụng depset:
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 đó có thể được truyền đến một hành động trình liên kết thông qua một 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 đưa vào tệp thực thi.
Mô tả và thao tác
Về mặt khái niệm, depset là một biểu đồ có hướng không có chu kỳ (DAG) thường trông giống như biểu đồ mục tiêu. Biểu đồ này được xây dựng từ các nút lá lên đến nút gốc. Mỗi mục tiêu trong chuỗi phần phụ thuộc có thể thêm nội dung riêng lên trên nội dung trước đó mà không cần phải đọc hoặc sao chép.
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 depset mới bằng hàm khởi tạo depset: hàm này chấp nhận một danh sách các phần tử trực tiếp và một danh sách khác gồm các nút con.
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 depset, hãy sử dụng phương thức to_list(). Phương thức này trả về một 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 có ả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 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 depset có thể không thay đổi được.
Depset sử dụng đẳng thức tham chiếu: một depset bằng chính nó, nhưng không bằng bất kỳ depset nào khác, ngay cả khi chúng có cùng nội dung và cùng cấu trúc nội bộ.
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 depset theo nội dung, hãy chuyển đổi chúng 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 có khả năng xoá các phần tử khỏi 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ái cấu trúc một depset mới. Cách này không hiệu quả lắm.
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 hàng
Thao tác to_list thực hiện việc di chuyển trên DAG. Loại di chuyển phụ thuộc vào thứ tự được chỉ định tại thời điểm depset được xây dựng. Bazel hỗ trợ nhiều thứ tự vì đôi khi các công cụ quan tâm đến thứ tự của dữ liệu đầu vào. Ví dụ: một hành động 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.
Ba thứ tự di chuyển được hỗ trợ: postorder, preorder và topological. Hai thứ tự đầu tiên hoạt động giống như việc di chuyển cây
traversals
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 kiểu sắp xếp theo cấu trúc liên kết từ gốc đến lá, về cơ bản giống như thứ tự 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ẹ.
Thứ tự trước và thứ tự sau hoạt động như các thao tác di chuyển 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ự so 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ự đảm bảo từ trái sang phải và ngay cả sự đảm bảo tất cả phần tử mẹ trước phần tử 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 các thao tác di chuyển, nên bạn phải chỉ định thứ tự tại thời điểm tạo depset bằng đối số từ khoá order của hàm khởi tạo. Nếu bạn bỏ qua đối số này, depset sẽ có thứ tự default đặc biệt, trong trường hợp đó, không có sự đảm bảo nào về thứ tự của bất kỳ phần tử nào (ngoại trừ việc thứ tự đó là xác định).
Ví dụ đầy đủ
Bạn có thể xem ví dụ này 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. Để xây dựng từng foo_binary, bạn cần phải biết tất cả các tệp *.foo mà tệp đó phụ thuộc trực tiếp hoặc gián tiếp.
# //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 tệp nhị phân d là tất cả các tệp *.foo trong
các 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 đó trong một nhà cung cấp. Mỗi thư viện nhận các nhà cung cấp từ các phần phụ thuộc của riêng mình, thêm các nguồn trực tiếp của riêng mình và truyền một nhà cung cấp mới có nội dung được tăng cường. Quy tắc foo_binary cũng thực hiện tương tự, ngoại trừ việc thay vì trả về một nhà cung cấp, quy tắc này sử dụng danh sách nguồn hoàn chỉnh để tạo một dòng lệnh cho một hành động.
Sau đây là cách triển khai hoàn chỉnh các quy tắc foo_library và foo_binary.
# //depsets/foo.bzl
# A provider with one field, transitive_sources.
foo_files = 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[foo_files].transitive_sources for dep in deps])
def _foo_library_impl(ctx):
trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
return [foo_files(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ử 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
cho phù hợp, tạo các tệp nguồn *.foo có nội dung giả và
xây dựng mục tiêu d.
Hiệu suất
Để xem lý do 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 trong một danh sách.
def get_transitive_srcs(srcs, deps):
trans_srcs = []
for dep in deps:
trans_srcs += dep[foo_files].transitive_sources
trans_srcs += srcs
return trans_srcs
Điều này không tính đến các phần tử 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 lựa chọn thay thế là sử dụng một 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á đều ánh xạ đến True.
def get_transitive_srcs(srcs, deps):
trans_srcs = {}
for dep in deps:
for file in dep[foo_files].transitive_sources:
trans_srcs[file] = True
for file in srcs:
trans_srcs[file] = True
return trans_srcs
Điều này giúp loại bỏ các phần tử trùng lặp, nhưng khiến 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 xác định được.
Hơn nữa, cả hai phương pháp đều tệ hơn về mặt tiệm cận so với phương pháp dựa trên depset. Hãy xem xét trường hợp có một chuỗi dài các phần phụ thuộc trên thư viện Foo. Việc xử lý mọi quy tắc đòi hỏi phải sao chép tất cả các nguồn bắc cầu xuất hiện trước đó vào một cấu trúc dữ liệu mới. Điều này có nghĩa là chi phí thời gian và 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ệ thuận với chiều cao của chính nó 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ể thực tế là O(n^2).
Nói chung, bạn nên sử dụng depset bất cứ khi nào bạn 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 rằng bản dựng của bạn có thể mở rộng tốt khi biểu đồ mục tiêu của bạn 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 một quy tắc nhị phân là ổn, vì chi phí tổng thể chỉ là O(n). Khi nhiều mục tiêu không phải là mục tiêu cuối cùng cố gắng gọi to_list(), thì 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.