حلقات

البُنى هي بنية بيانات مخصّصة لجمع البيانات بكفاءة عبر العناصر الاعتمادية العابرة التي يستهدفها الهدف. وهي من العناصر الأساسية في معالجة القاعدة.

تتمثل ميزة التعريف في الإعداد في عملية اتحاد موحّدة للوقت وفضاء. تقبل أداة إنشاء depset قائمة بالعناصر ("مباشر") وقائمة أخرى من العناصر الوصفية ("تحويلية")، وتعرض مجموعة تعريف تمثل مجموعة تحتوي على جميع العناصر المباشرة واتحاد جميع العناصر الانتقالية غُرَب من الناحية النظرية، تنشئ أداة الإنشاء عُقدة رسم بياني جديدة تحتوي على عُقد مباشرة وعابرة خلفها. تحتوي الدعائم على دلالات ترتيبية مُحدّدة جيدًا، وذلك اعتمادًا على اجتياز هذا الرسم البياني.

تتضمن أمثلة استخدام المبيّنات:

• تخزين مسارات جميع ملفات الكائنات لمكتبات البرنامج، والتي يمكن بعد ذلك تمريرها إلى إجراء الرابط من خلال موفّر خدمة.

• بالنسبة إلى اللغة المفسّرة، يمكن تخزين ملفات المصدر الانتقالية التي تم تضمينها في ملفات تشغيل قابلة للتنفيذ.

الوصف والعمليات

من الناحية النظرية، يُقصد بالدقّة الرسم البياني الدائري (DAG) الذي يظهر عادةً على الرسم البياني المستهدف. يتم إنشاؤها من أوراق الأشجار إلى الجذر. يمكن لكل هدف في سلسلة التبعية إضافة محتوى خاص به في أعلى السابق بدون الحاجة إلى قراءته أو نسخه.

تحتوي كل عُقدة في مزوّد البيانات العامة على قائمة بالعناصر المباشرة وقائمة بالعُقد الفرعية. محتوى مجموعة العناصر هو العناصر العابرة، مثل العناصر المباشرة في جميع العُقد. يمكن إنشاء مجموعة تحكّم جديدة باستخدام أداة إنشاء 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"])

لاسترداد محتوى الإعداد، استخدِم الطريقة to_list(). إنها تعرض قائمة بجميع العناصر عابرة، بما في ذلك العناصر المكرّرة. ولا تتوفّر طريقة لفحص البنية الدقيقة لأداة مزامنة دليل Google Cloud مباشرةً، ولكن هذه البنية تؤثر في ترتيب إرجاع العناصر.

s = depset(["a", "b", "c"])

print("c" in s.to_list())              # True
print(s.to_list() == ["a", "b", "c"])  # True

يتم حظر العناصر المسموح بها في عملية الضبط، تمامًا مثل المفاتيح المسموح بها في القواميس. وعلى وجه الخصوص، قد لا يكون محتوى الإزالة غير قابل للتغيير.

تستخدم الدعائم "التساوي" المرجعي: يساوي الضبط نفسه، ولكنه لا يساوي أي تحليل آخر، حتى إذا تضمّن المحتوى نفسه والبنية الداخلية نفسها.

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

لا يمكن إزالة عناصر من الإعداد. إذا كان ذلك ضروريًا، عليك قراءة المحتوى الكامل في مجموعة البيانات، وفلترة العناصر التي تريد إزالتها، وإعادة إنشاء مجموعة بيانات جديدة. ولا يكون هذا الإجراء فعّالاً على وجه الخصوص.

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، ثم يأتي A.o قبل B.o في سطر أوامر الرابط. وقد يكون هناك متطلبات أخرى للأدوات الأخرى.

تتوفّر ثلاثة طلبات للمسح: postorder وpreorder وtopological. ويتم تنفيذ أول إجراءين تمامًا مثل اجتيازات الأشجار باستثناء أنّها تعمل على DAG وتتخطّى العُقد التي تمت زيارتها. أما الترتيب الثالث، فهو عبارة عن ترتيب طوبولوجي من الجذر إلى اليسار، وهو في الأساس يعمل مسبقًا باستثناء أنّ العناصر المشتركة لا تُدرَج إلا بعد جميع الوالدَين. يعمل الطلب المسبق والطلب البعدي كمسح من اليسار إلى اليمين، لكن تجدر الإشارة إلى أن العناصر المباشرة في كل عُقدة لا يوجد بها ترتيب مقارنة بالعناصر الفرعية. بالنسبة إلى الترتيب الهيكلي، لا يتوفر ضمان من اليسار إلى اليمين، كما لا يسري ضمان جميع أولياء الأمور قبل المدرسة في حال وجود عناصر مكررة في عُقد مختلفة 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"]

بسبب كيفية تنفيذ الاجتياز، يجب تحديد الترتيب في الوقت الذي يتم فيه إنشاء التركيبة باستخدام وسيطة الكلمة الرئيسية order للدالة. في حال حذف هذه الوسيطة، سيرتبط الترتيب default الخاص، وفي هذه الحالة لا تتوفّر أي ضمانات بشأن ترتيب أي من عناصره (باستثناء أنه محدّد).

مثال كامل

هذا المثال متاح على https://github.com/bazelbuild/examples/tree/main/rules/depses.

لنفترض أن هناك 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.

الأداء

للاطّلاع على الدافع وراء استخدام العناصر المصوّرة، فكِّر في ما سيحدث إذا جمع 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) بشكل فعّال.

بوجه عام، يجب استخدام ملفات تعريف الارتباط عند تجميع المعلومات من خلال البرامج الاعتمادية العابرة. وهذا يساعد على ضمان توسعة بنية الرسم البياني بالإضافة إلى نمو الرسم البياني المستهدف.

أخيرًا، من المهم عدم استرداد محتوى عمليّة الإعداد بدون داعٍ في عمليات تنفيذ القواعد. هناك استدعاء واحد لـ to_list() في النهاية بقاعدة ثنائية، وذلك نظرًا لأن التكلفة الإجمالية هي O(n) فقط. يحدث ذلك عندما يحاول العديد من الأهداف غير النهائية استدعاء to_list() ليتم هذا السلوك التربيعي.

لمزيد من المعلومات حول استخدام برامج الترميز بكفاءة، راجع صفحة الأداء.

مرجع واجهة برمجة تطبيقات

يُرجى الاطّلاع هنا على مزيد من التفاصيل.