מעמדים

מכונות ישיבה הן מבנה נתונים מיוחד המיועד לאיסוף יעיל של נתונים ביחסי התלות העקיפים של היעד. הם מרכיב חיוני בעיבוד כללים.

המאפיין העיקרי של depset הוא פעולת איחוד חסכונית בזמן ובמרחב. בנאי ה-depset מקבל רשימה של רכיבים ("direct") ורשימה של רכיבים אחרים ("transitive"), ומחזיר מערך נתונים שמכיל את כל הרכיבים הישירים והאיחוד של כל הרכיבים העקיפים קבוצות. באופן עקרוני, הבנאי יוצר צומת תרשים חדש שיש לו צמתים ישירים ועקיפים. לסמנטיקה של מערכי נתונים מוגדרת היטב, בהתבסס על מעבר של תרשים זה.

דוגמאות לשימושים בנכסים:

• אחסון הנתיבים של כל קובצי האובייקטים בספריות של התוכנית, שאותם ניתן להעביר לפעולת מקשר דרך ספק.

• עבור שפה שמתורגמת, אחסון קובצי המקור העקיפים הכלולים בקובצי הפעלה של קובץ הפעלה.

תיאור ופעולות

באופן עקרוני, depset הוא תרשים מחזורי ישיר (DAG) שנראה בדרך כלל דומה לתרשים היעד. המבנים בנויים מהעלים ועד לשורש. כל יעד בשרשרת תלות יכול להוסיף תוכן משלו על גבי הקודם, מבלי לקרוא או להעתיק אותו.

כל צומת ב-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"])

כדי לאחזר את התוכן של 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 הם מוגבלים, בדיוק כמו שהמפתחות המותרים במילונים מוגבלים. באופן ספציפי, ייתכן שתוכן דינמי לא יהיה ניתן לשינוי.

במערכות לשיתוף תמונות נעשה שימוש בשוויון בהפניה: תהליך טעימה שווה לעצמו, אבל אינו שווה לערך של דפוס אחר, גם אם הם מכילים את אותו התוכן ובאותו מבנה פנימי.

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, לסנן את הרכיבים שרוצים להסיר ולשחזר מערך חדש. אפשרות זו אינה יעילה במיוחד.

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. סוג המעבר תלוי בסדר שצוין בזמן יצירת ה-depset. בזל יכולה לתמוך במספר הזמנות, כי לפעמים לכל אחד מהכלים יש חשיבות לסדר הקלט שלו. לדוגמה, ייתכן שפעולת קישור צריכה לוודא שאם B תלוי ב-A, אז A.o יופיע לפני B.o בשורת הפקודה של המקשר. ייתכן שלכלים אחרים יש את ההפך.

יש תמיכה בשלושה סדרי מעבר: postorder , preorder ו-topological. שתי הפעולות הראשונות פועלות בדיוק כמו מעברי עץ חוץ מהעובדה שהן פועלות על DAG ומדלגות על צמתים שכבר ביקרו בהם. הסדר השלישי פועל כמו מיון טופולוגי, מהשורש ועד לעלים, בעיקר זהה להזמנה מראש, למעט העובדה שילדים משותפים מפורטים רק אחרי כל ההורים שלהם. הזמנות מראש ו-postorder פועלות כמעברים משמאל לימין, אך שים לב שבתוך כל רכיב ישיר של הצומת אין סדר יחסי לילדים. לגבי סדר טופולוגי, אין כל ערובה משמאל לימין, ואפילו התחייבות של כל ההורים לפני שהילדים לא חלה במקרה שיש רכיבים משוכפלים בצמתים שונים תרשים טבעות.

# 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/rule/depsets.

נניח שיש פה היפותזה של פרשנות היפותטית. כדי לבנות כל 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

פעולה זו מסירה את הכפילויות, אך מבטלת את קביעת הארגומנטים (ולכן את תוכן הקבצים) של שורת הפקודה, למרות שהיא עדיין דטרמיניסטית.

יתר על כן, שתי הגישות מחמירות יותר ללא גישה לעומת הגישה המבוססת על טכנולוגיה. קחו בחשבון את המקרים שבהם יש שרשרת תלות ארוכה בספריות של פו. לצורך עיבוד של כל כלל, נדרשים להעתיק את כל המקורות העקרוניים שקדמו לו למבנה נתונים חדש. משמעות הדבר היא שהעלות של הזמן והשטח לניתוח ספרייה יחידה או יעד בינארי היא יחסית לגובה שלה בשרשרת. בשרשרת באורך n, foolib_1 ← foolib_2 ← ... ← foolib_n, העלות הכוללת היא למעשה O(n^2).

באופן כללי, יש להשתמש בהפרעות בכל פעם שאתה צובר מידע באמצעות יחסי התלות העקיפים שלך. פעולה זו עוזרת להבטיח שהגרסה של ה-build מתרחבת, ככל שתרשים היעד גדל.

לסיום, חשוב לא לאחזר את התוכן של ה-depset שלא לצורך בהטמעות של כללים. קריאה אחת אל to_list() בסוף כלל בינארי היא בסדר, מאחר שהעלות הכוללת היא רק O(n). כאשר יעדים רבים אינם טרמינלים, הם קוראים ל-to_list() התנהגות ריבועית.

לקבלת מידע נוסף על שימוש יעיל בשקעים, כדאי לעיין בדף הביצועים.

הפניית API

עיינו כאן לקבלת פרטים נוספים.