Depsets

Depset ها یک ساختار داده تخصصی برای جمع آوری کارآمد داده ها در وابستگی های گذرای یک هدف هستند. آنها یک عنصر اساسی در پردازش قوانین هستند.

ویژگی تعیین کننده depset، عملیات اتحاد کارآمد آن در زمان و مکان است. سازنده depset یک لیست از عناصر ("مستقیم") و یک لیست از depset های دیگر ("transitive") را می پذیرد و یک depset را نشان می دهد که مجموعه ای را شامل تمام عناصر مستقیم و اتحاد همه مجموعه های انتقالی است. از نظر مفهومی، سازنده یک گره گراف جدید ایجاد می کند که گره های مستقیم و گذرا را به عنوان جانشین خود دارد. Depset ها بر اساس پیمایش این نمودار، معنایی نظم دهی به خوبی تعریف شده دارند.

نمونه هایی از کاربردهای دپست عبارتند از:

• ذخیره مسیرهای همه فایل‌های شی برای کتابخانه‌های یک برنامه، که سپس می‌تواند از طریق یک ارائه‌دهنده به یک اقدام پیوند دهنده منتقل شود.

• برای یک زبان تفسیر شده، ذخیره فایل‌های منبع انتقالی که در فایل‌های اجرایی یک فایل اجرایی گنجانده شده‌اند.

توضیحات و عملیات

از نظر مفهومی، depset یک گراف غیر چرخه ای جهت دار (DAG) است که معمولاً شبیه به نمودار هدف است. از برگ تا ریشه ساخته می شود. هر هدف در یک زنجیره وابستگی می‌تواند محتویات خود را بدون نیاز به خواندن یا کپی کردن آن‌ها در بالای محتوای قبلی اضافه کند.

هر گره در DAG فهرستی از عناصر مستقیم و لیستی از گره های فرزند را در خود دارد. محتویات depset عناصر متعدی هستند، مانند عناصر مستقیم همه گره ها. یک 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 دیگر نابرابر است، حتی اگر دارای محتویات یکسان و ساختار داخلی یکسان باشد.

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 را بخوانید، عناصری را که می خواهید حذف کنید فیلتر کنید و یک depset جدید را بازسازی کنید. این کارایی خاصی ندارد.

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 را انجام می دهد. نوع پیمایش بستگی به ترتیبی دارد که در زمان ساخت دیپست مشخص شده است. پشتیبانی از چندین سفارش برای Bazel مفید است زیرا گاهی اوقات ابزارها به ترتیب ورودی های خود اهمیت می دهند. به عنوان مثال، یک عمل پیوند دهنده ممکن است نیاز به اطمینان حاصل کند که اگر B به A بستگی دارد، Ao قبل از Bo در خط فرمان پیوند دهنده قرار می گیرد. ابزارهای دیگر ممکن است نیاز مخالف داشته باشند.

سه سفارش پیمایش پشتیبانی topological شود: سفارش پس از سفارش، preorder و postorder . دو مورد اول دقیقاً مانند پیمایش درخت کار می کنند با این تفاوت که روی DAG ها کار می کنند و از گره های قبلاً بازدید شده صرف نظر می کنند. مرتبه سوم به‌عنوان یک مرتب‌سازی توپولوژیکی از ریشه تا برگ عمل می‌کند، اساساً مانند پیش‌سفارش است، با این تفاوت که فرزندان مشترک فقط بعد از همه والدینشان فهرست می‌شوند. Preorder و Postorder به صورت پیمایش از چپ به راست عمل می کنند، اما توجه داشته باشید که در هر گره عناصر مستقیم هیچ ترتیبی نسبت به فرزندان ندارند. برای ترتیب توپولوژیکی، ضمانت چپ به راست وجود ندارد، و حتی ضمانت تمام والدین قبل از فرزند در موردی که عناصر تکراری در گره‌های مختلف 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"]

با توجه به نحوه پیاده‌سازی پیمایش‌ها، ترتیب باید در زمان ایجاد depset با آرگومان کلمه کلیدی 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 ، آن را آزمایش کنید.

کارایی

برای مشاهده انگیزه استفاده از depsets، در نظر بگیرید که اگر 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

این کار از شر موارد تکراری خلاص می‌شود، اما ترتیب آرگومان‌های خط فرمان (و در نتیجه محتویات فایل‌ها) را نامشخص می‌کند، اگرچه هنوز قطعی است.

علاوه بر این، هر دو رویکرد به طور مجانبی بدتر از رویکرد مبتنی بر عمق هستند. موردی را در نظر بگیرید که در آن زنجیره طولانی وابستگی به کتابخانه های Foo وجود دارد. پردازش هر قانون مستلزم کپی کردن همه منابع انتقالی است که قبل از آن آمده اند در یک ساختار داده جدید. این بدان معناست که هزینه زمان و مکان برای تجزیه و تحلیل یک کتابخانه یا هدف باینری منفرد با ارتفاع خود در زنجیره متناسب است. برای یک زنجیره به طول n، foolib_1 ← foolib_2 ← … ← foolib_n، هزینه کلی به طور موثر O(n^2) است.

به طور کلی، هر زمان که اطلاعاتی را از طریق وابستگی های گذرا جمع آوری می کنید، باید از depsets استفاده کنید. این کمک می کند تا اطمینان حاصل شود که مقیاس ساخت شما و نمودار هدف شما عمیق تر می شود.

در نهایت، مهم است که در اجرای قوانین، محتویات depset را به صورت غیر ضروری بازیابی نکنید. یک فراخوانی به to_list() در پایان در یک قانون باینری خوب است، زیرا هزینه کلی فقط O(n) است. زمانی که بسیاری از اهداف غیر پایانی سعی می to_list() را فراخوانی کنند، رفتار درجه دوم رخ می دهد.

برای اطلاعات بیشتر در مورد استفاده موثر از دیپست ها، به صفحه عملکرد مراجعه کنید.

مرجع API

لطفا برای جزئیات بیشتر اینجا را ببینید.