Chốt

Báo cáo sự cố Xem nguồn

Phần phụ thuộc 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. Chúng là một yếu tố thiết yếu trong quá trình xử lý quy tắc.

Đặc điểm định nghĩa của phần phụ thuộc 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 phần phụ thuộc chấp nhận danh sách các phần tử ("direct") và danh sách các phần phụ thuộc khác ("transitive") và trả về một phần phụ thuộc đại diện cho một tập hợp chứa mọi phần tử trực tiếp và phần hợp nhất của mọi tập hợp bắc cầu. Về mặt lý thuyết, hàm khởi tạo 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. Các phần phụ thuộc có ngữ nghĩa có thứ tự được xác định rõ ràng, dựa trên việc truyền tải biểu đồ này.

Ví dụ về cách sử dụng phần phụ thuộc:

  • Lưu trữ đường dẫn của mọi tệp đối tượng cho thư viện của một chương trình, thư viện này sau đó có thể được truyền đến hành động của trình liên kết thông qua nhà cung cấp.

  • Đối với ngôn ngữ thông dịch, hãy lưu trữ các tệp nguồn bắc cầu được đưa vào các tệp chạy của tệp thực thi.

Mô tả và thao tác

Về mặt lý thuyết, phần phụ thuộc là một biểu đồ tuần hoàn có hướng (DAG) thường trông giống như biểu đồ mục tiêu. Nó được xây dựng từ lá lên đế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 của riêng mục tiêu đó vào mục trước mà không cần phải đọc hoặc sao chép các mục tiêu đó.

Mỗi nút trong DAG chứa một danh sách các thành phần trực tiếp và một danh sách các nút con. Nội dung của phần phụ thuộc là các phần tử bắc cầu, chẳng hạn như 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 Desetset (phần phụ thuộc): chấp nhận danh sách các phần tử trực tiếp 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 một phần phụ thuộc, hãy sử dụng phương thức to_list(). Phương thức 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 phần phụ thuộc 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 phụ thuộc không thể thay đổi được.

Các phần phụ thuộc sử dụng đẳng thức tham chiếu: một phần phụ thuộc bằng chính nó, nhưng không giống với mọi phần phụ thuộc 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 các phần phụ thuộc theo nội dung, hãy chuyển đổi các phần phụ thuộc đó 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 phần phụ thuộc. Nếu cần, bạn phải đọc 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 một 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

Thao tác to_list thực hiện truyền tải qua DAG. Loại truyền tải này phụ thuộc vào thứ tự được chỉ định tại thời điểm xây dựng phần phụ thuộc. Việc hỗ trợ nhiều đơn đặt hàng rất hữu ích vì Bazel đôi khi, các công cụ quan tâm đến thứ tự nhập. Ví dụ: một hành động 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.

Ba thứ tự truyền tải được hỗ trợ: postorder, preordertopological. 2 tính năng đầu tiên hoạt động giống hệt như truyền tải 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 sắp xếp cấu trúc liên kết từ gốc đến lá, về cơ bản giống như đặt hàng trước, ngoại trừ các phần tử con dùng chung chỉ được liệt kê sau tất cả bố cục mẹ. Tính năng đặt hàng trước và sau thứ tự hoạt động như 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ự nào so với thành phần 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à thậm chí là đảm bảo toàn bộ cha mẹ trước khi 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 truyền tải, bạn phải chỉ định thứ tự tại thời điểm tạo nhóm 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, thì phần phụ thuộc sẽ có thứ tự default đặc biệt. Trong trường hợp đó, không có đảm bảo về thứ tự của các phần tử trong đối số đó (ngoại trừ thứ tự 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 thông dịch 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à chúng 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, 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, cd. Để 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 trình cung cấp từ các phần phụ thuộc riêng, thêm nguồn tức thì riêng và truyền một nhà cung cấp mới có nội dung tăng cường. Quy tắc foo_binary cũng tương tự như vậy, 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à hoạt động triển khai đầy đủ các quy tắc 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"},
)

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 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 các phần phụ thuộc, hãy xem xét đ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

Điều này không tính đến các tệp trùng lặp, vì vậy, các tệp nguồn của a sẽ xuất hiện 2 lần trên dòng lệnh và 2 lần trong nội dung của tệp đầu ra.

Một cách khác là sử dụng một tập hợp chung (có thể được mô phỏng bằng một cuốn từ điển), trong đó các khoá là các phần tử và tất cả các phím đều ánh xạ tới 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 nội dung trùng lặp, nhưng sẽ làm cho thứ tự của các đối số dòng lệnh (và 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 đều kém không có triệu chứng so với phương pháp dựa trên phần phụ thuộc. Hãy cân nhắc 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ả các nguồn bắc cầu trước quy tắc đó vào một cấu trúc dữ liệu mới. Tức là thời gian và chi phí không gian để phân tích một thư viện riêng lẻ hoặc mục tiêu nhị phân sẽ tỷ lệ thuận với chiều cao của thư viện đó trong chuỗi. Đối với chuỗi có độ dài n, foolib_1 ← foolib_2 ← ... ← foolib_n, chi phí tổng thể là O(n^2).

Nói chung, bạn nên sử dụng phần phụ thuộc 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 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, bạn không cần truy xuất nội dung của phần phụ thuộc một cách không cần thiết trong quá trình triển khai quy tắc. Bạn có thể thực hiện một lệnh gọi đến to_list() ở cuối theo quy tắc nhị phân, vì chi phí tổng thể chỉ là O(n). Đó là khi nhiều mục tiêu không đầu cuối cố gắng gọi to_list() sẽ xảy ra hành vi bậc hai.

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