Chốt

Báo cáo vấn đề Xem nguồn Hằng đêm · 7,3 · 7,2 · 7.1 · 7 · 6,5

Tập hợp là một cấu trúc dữ liệu chuyên biệt để thu thập dữ liệu thông qua các phần phụ thuộc bắc cầu của một mục tiêu. Chúng là 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 gỡ cài đặt chấp nhận danh sách các phần tử ("trực tiếp") và danh sách các phần tử khác phần phân tách ("chuyển tiếp") và trả về một tập hợp đạ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 bắc cầu. Về mặt lý thuyết, hàm khởi tạo tạo một nút đồ thị mới có các nút trực tiếp và nút bắc cầu với tư cách người kế thừa. Các phần phụ thuộc có ngữ nghĩa thứ tự được xác định rõ ràng, dựa trên 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. Việc này có thể sau đó sẽ được chuyển đến hành động của trình liên kết thông qua một trình cung cấp.
Đối với ngôn ngữ thông dịch, việc lưu trữ các tệp nguồn bắc cầu có được đưa vào trong các tệp chạy của tệp thực thi.

Mô tả và hoạt động

Về mặt lý thuyết, tập dữ liệu là một đồ thị không chu trình có hướng (DAG) thường có tương tự như biểu đồ mục tiêu. Nó được làm từ lá cho đến 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 ở đầu chuỗi trước đó mà không phải đọc hoặc sao chép chúng.

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 tập hợp 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 mới bằng cách sử dụng Hàm khởi tạo depset: hàm này chấp nhận danh sách các hàm và một danh sách 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 to_list(). Phương thức này trả về một danh sách tất cả ngoại động các phần tử, không bao gồm các phần tử trùng lặp. Không có cách nào để kiểm tra trực tiếp 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ự mà các phần tử được trả về.

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 tập hợp 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 lệ bằng chính nó, nhưng không bằng bất kỳ phần phụ thuộc khác, ngay cả khi chúng 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 phần giảm theo nội dung, hãy chuyển đổi chúng thành danh sách được 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 tập hợp. Nếu cần thiết, bạn phải đọc to toàn bộ nội dung của phần phụ thuộc, lọc các phần tử bạn muốn xoá và tạo lại phần phụ thuộc mới. Điều 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 truyền tải qua DAG. Loại truyền tải phụ thuộc vào thứ tự được chỉ định tại thời điểm thiết lập tạo. Việc Bazel hỗ trợ nhiều đơn đặt hàng sẽ rất hữu ích vì đôi khi các công cụ quan tâm đến thứ tự đầu vào. Ví dụ: một hành động trong 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ự truyền tải được hỗ trợ: postorder, preorder và topological. Hai thuộc tính đầu tiên hoạt động giống hệt như cây truyền tải ngoại trừ việc chúng hoạt động trên DAG và bỏ qua các nút đã được truy cập. Đơn đặt hàng thứ ba hoạt động như một kiểu cấu trúc liên kết từ gốc đến lá, về cơ bản giống với đặt hàng trước, trừ trường hợp trẻ em dùng chung chỉ được liệt kê sau tất cả cha mẹ của trẻ. Nội dung đặt hàng trước và đặt hàng sau hoạt động như các hoạt động truyền tải từ trái sang phải, nhưng xin lưu ý rằng trong mỗi phần tử trực tiếp của nút không có thứ tự tương ứng với các phần tử con. Cho 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 có toàn bộ tài khoản mẹ trước con không áp dụng trong trường hợp có 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 hoạt động truyền tải, bạn phải chỉ định thứ tự tại thời điểm này Phần phụ thuộc được tạo bằng đối số từ khoá order của hàm khởi tạo. Nếu trường hợp này đối số bị bỏ qua, phần phụ thuộc có thứ tự default đặc biệt. Trong trường hợp đó, không đảm bảo về thứ tự của bất kỳ phần tử nào trong số đó (ngoại trừ việc 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ữ thông dịch giả định Foo. Để tạo mỗi foo_binary bạn cần biết tất cả các tệp *.foo mà nó trực tiếp hoặc gián tiếp phụ thuộc vào.

# //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. Để foo_binary cần biết về bất kỳ tệp nào ngoài d.foo, thì các mục tiêu foo_library cần phải chuyển chúng đến một nhà cung cấp. Mỗi thư viện nhận các trình cung cấp từ riêng thư viện đó các phần phụ thuộc, thêm các nguồn tức thì riêng và truyền vào trình cung cấp mới bằng các nội dung tăng cường. Quy tắc foo_binary cũng hoạt động tương tự, ngoại trừ điều đó trả về một trình cung cấp, nó sẽ sử dụng danh sách đầy đủ các nguồn để tạo một dòng lệnh cho một hành động.

Dưới đây là 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 tra đ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 thành phần nhãn một cách 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

Để biết động lực sử dụng phần tách, 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[FooFiles].transitive_sources
  trans_srcs += srcs
  return trans_srcs

Việc này không tính đến vấn đề trùng lặp, do đó, 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 .

Phương án thay thế là sử dụng tập hợp chung, có thể được mô phỏng bằng từ điển trong đó khoá là các phần tử và mọi 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 sẽ loại bỏ các bản sao, nhưng tạo thứ tự của dòng lệnh đối số (và do đó là nội dung của các tệp) không được chỉ định, mặc dù vẫn thuật toán tất định.

Hơn nữa, cả hai phương pháp đều kém hiệu quả hơn so với phương pháp dựa trên phần cài đặt phương pháp tiếp cận. 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. Việc xử lý mọi quy tắc yêu cầu sao chép tất cả nội dung bắc cầu trước nó 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à 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 nó trong chuỗi. Đối với chuỗi có độ dài n, foolib_1 ← foolib_2 ← ... ← foolib_n, chi phí tổng thể có hiệu quả O(n^2).

Nói chung, bạn nên sử dụng phần tách bất cứ khi nào bạn tích luỹ 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 sẽ điều chỉnh theo tỷ lệ cũng như biểu đồ mục tiêu phát triển sâu hơn.

Cuối cùng, quan trọng là không truy xuất nội dung của phần tách không cần thiết trong quá trình triển khai quy tắc. Một cuộc gọi đến to_list() cuối cùng trong quy tắc nhị phân vẫn ổn, vì tổng chi phí chỉ là O(n). Đó là khi nhiều mục tiêu không phải đầu cuối cố gắng gọi to_list() có hành vi bậc hai xảy ra.

Để biết thêm thông tin về cách sử dụng hiệu quả phần tách, 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 chi tiết.