לפני כמה ימים סיפרתי כאן על Datomic, בסיס נתונים שמאחסן "עובדות" ומציע שפת שאילתות בשם Datalog כדי לחפש מידע ומסקנות שקשור לעובדות אלה. אחד השימושים המדליקים ב Datomic הוא היכולת לחפש בצורה רקורסיבית במבני נתונים מקושרים כמו גרפים או עצים. בזכות Datalog, שאילתות שהיו יכולות להיות מסובכות מאוד ב SQL הופכות לכמה שורות. בפוסט זה נראה דוגמה לאחסון מידע על מערכת קבצים ב Datomic, ואיך אחסון כזה עוזר לנו לחשב מהר גדלים בצורה רקורסיבית.

1. האתגר

לקחתי את התרגיל שפורסם ב Advent Of Code Day 7 בשביל דוגמה למשימה על גרפים. התרגיל בגדול נותן לנו מידע על קבצים, תיקיות וגדלים ואחרי זה שולח אותנו לחפש תיקיות בגדלים מסוימים. המידע מגיע בפורמט הבא:

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

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

1. שורות שמתחילות בדולר מסמנות שפה יש "פקודה" ואחריה יבואו השורות שמתאימות לפלט שלה. אחרי פקודת ls נקבל את רשימת הקבצים והתיקיות בתיקיה הנוכחית, אחרי פקודת cd אין פלט אבל התיקיה תשתנה.

2. שורות שמתחילות במספר מסמנות שיש קובץ בגודל מסוים בתיקיה הנוכחית. המספר הוא הגודל והטקסט הוא שם הקובץ.

3. שורות שמתחילות במילה dir אומרות שיש תיקיה בשם מסוים בתיקיה הנוכחית.

אחרי שנפענח את הקלט נצטרך לענות על שתי שאלות שקשורות לגדלים:

1. נרצה למצוא את סכום הגדלים בכל התיקיות שגודלן קטן או שווה ל 100000

2. נרצה למצוא את התיקיה הקטנה ביותר שגודלה גדול מ 8381165

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

2. סכימה לייצוג המידע

בסיס נתונים Datomic משתמש בסכימה כדי להגיד איזה עובדות אפשר להכניס למערכת. הסכימה שלי נראית כך:

(def schema
  [
   {:db/ident :entry/type
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/name
    :db/valueType :db.type/string
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/link-to
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry-link}
   {:db/ident :entry-file}
   {:db/ident :entry-dir}
   {:db/ident :entry/parent
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/size
    :db/valueType :db.type/long
    :db/cardinality :db.cardinality/one}
   {:db/ident :fs/id
    :db/cardinality :db.cardinality/one
    :db/unique :db.unique/identity
    :db/valueType :db.type/string}
   {:db/ident :fs/cwd
    :db/cardinality :db.cardinality/one
    :db/valueType :db.type/ref}
   ])

במערכת יש שני סוגים של "דברים", לדבר אחד אפשר לקרוא "מערכת קבצים", וזה משהו ששומר את התיקיה הנוכחית. לדבר השני קראתי entry וזה יכול להיות קובץ, תיקיה או לינק בתוך מערכת הקבצים. לכל entry יש שם, יש את הסוג שלו ויש parent שזה ה entry שמכיל אותו.

3. הכנסת מידע לבסיס הנתונים

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

(dir "a")
(file "b.txt" 14848514)
(file "c.dat" 8504156)
(dir "d")
(cd "a")
(dir "e")
(file "f" 29116)
(file "g" 2557)
(file "h.lst" 62596)
(cd "e")
(file "i" 584)
(cd "..")
(cd "..")
(cd "d")
(file "j" 4060174)
(file "d.log" 8033020)
(file "d.ext" 5626152)
(file "k" 7214296)

בשביל שזה יעבוד צריך להגדיר את הפונקציות dir, file ו cd. בשבילן גיליתי שמאוד עוזר להגדיר פונקציה בשם cwd שמחזירה את התיקיה הנוכחית. נתחיל עם הקוד שלה כי כל הפונקציות האחרות ישתמשו בה:

(defn cwd []
  (let [db (d/db conn)]
    (d/q '[:find ?cwd .
           :where
           [?fs :fs/id "/"]
           [?fs :fs/cwd ?cwd]] db)))

והנה אינטרקציה ראשונה עם Datomic. התיקיה הנוכחית נשמרת בבסיס הנתונים בתור הערך של מאפיין :fs/cwd. בסיס הנתונים תומך במספר מערכות קבצים במקביל אבל בתוכנית שלי השתמשתי רק במערכת קבצים אחת ונתתי לה את המזהה /. בהמשך נצטרך לראות איך להכניס את מערכת הקבצים הזו לבסיס הנתונים.

הפונקציה הבאה היא file והיא יוצרת קובץ בתיקיה הנוכחית:

(defn file [name size]
  @(d/transact conn [
                     {:entry/type :entry-file
                      :entry/name name
                      :entry/size size
                      :entry/parent (cwd)}
                     ]))

הפקודה transact של Datomic מגדירה טרנזאקציה וזו בעצם עובדה חדשה שאני מכניס לבסיס הנתונים - העובדה שיש דבר בשם name, שה parent שלו הוא התיקיה הנוכחית, שהגודל שלו הוא size ושהסוג שלו הוא :entry-file.

הפונקציה הבאה היא dir והיא קצת יותר מסובכת מ file, בגלל שבכל תיקיה יש לנו שני לינקים מיוחדים - הקישור . שמחבר אותה לעצמה והקישור .. שמחבר אותה לתיקיה שמעליה:

(defn dir [name]
  @(d/transact conn [
                     {:entry/type :entry-link
                      :entry/parent "d"
                      :entry/name ".."
                      :entry/link-to (cwd)}
                     {:entry/type :entry-link
                      :entry/parent "d"
                      :entry/name "."
                      :entry/link-to "d"}
                     {:db/id "d"
                      :entry/type :entry-dir
                      :entry/name name
                      :entry/parent (cwd)}
                     ]))

לכן הטרנזאקציה הפעם מספרת שלוש עובדות חדשות:

1. יש תיקיה בשם name וההורה שלה הוא parent

2. יש לינק בשם . וההורה שלו הוא התיקיה החדשה שתיווצר. הלינק מוביל לאותה תיקיה חדשה.

3. יש לינק בשם .. וההורה שלו הוא התיקיה החדשה שתיווצר. הלינק מוביל ל parent.

הגדרת המזהה d בתוך הטרנזאקציה היא שמאפשרת בקלות לכמה עובדות להתיחס לאותה ישות.

והפונקציה המסובכת ביותר בקוד היא פונקציית cd. מקור הסיבוך הוא התמיכה בלינקים, כי אם אני עושה cd ללינק אני מצפה להגיע לדבר שהלינק מצביע אליו. הקוד בדוגמה תומך גם בלינק שמפנה ללינק, אבל ייכשל בצורה אומללה עם מעגלים:

(defn cd [name]
  (let [db (d/db conn)
        to (d/q '[:find ?e .
                  :in $ ?cwd ?name
                  :where
                  [?e :entry/name ?name]
                  [?e :entry/parent ?cwd]]
                db
                (cwd) name)
        toe (d/entity db to)
        tod (if (= (:entry/type toe) :entry-link)
              (:db/id (first (filter #(= (:entry/type %1) :entry-dir) (iterate :entry/link-to toe))))
              to)]
    @(d/transact conn [{:fs/id "/"
                        :fs/cwd tod}])))

ב Datomic, בשביל לקחת משהו שחוזר מ find ולחפש מאפיינים נוספים שלו אני צריך להשתמש בפונקציה שנקראת entity. הפונקציה מחזירה אוביקט מידע מלא מבסיס הנתונים שכבר כולל גם את כל האוביקטים שמקושרים אליו, וכך אפשר "לטייל" בעץ עד שמאפיין link-to מביא אותי לתיקיה.

אחרי שהגדרנו את פוקנציות העזר אפשר לאתחל את מערכת הקבצים עם:

(def data [
           {:db/id "root" :entry/name "" :entry/type :entry-dir}
           {:fs/id "/" :fs/cwd "root"}
           ])

@(d/transact conn data)

ולהפעיל את התוכנית.

4. הצגת כל התיקיות והגדלים בצורה רקורסיבית

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

(def rules
'[[(belongs-to ?entry ?parent)
   [?entry :entry/parent ?parent]]
  [(inside ?entry ?parent)
   (belongs-to ?entry ?parent)]
  [(inside ?entry ?parent)
   (belongs-to ?entry ?middle)
   (inside ?middle ?parent)]])

הביטוי rules מייצג סט של ״חוקים״ שאיתם אפשר לגזור מידע חדש מהעובדות שלנו. משמעות החוקים שהגדרתי היא:

1. יש יחס במערכת שנקרא belongs-to. כשמשהו belongs-to משהו אחר זה אומר שמשהו אחר הוא ה parent של משהו.

2. יש יחס במערכת שנקרא inside. כשמשהו inside משהו אחר זה אומר שהוא belongs-to הדבר האחר, או שה parent שלו הוא inside הדבר האחר.

וכן ההגדרה רקורסיבית והכל בסדר.

עכשיו השאילתה משתמשת בהגדרה כדי למצוא את כל התיקיות והגדלים שלהן:

(d/q '[:find ?name (sum ?size)
       :in $ %
       :where
       [?dir :entry/name ?name]
       [?dir :entry/type :entry-dir]
       (inside ?child ?dir)
       [?child :entry/size ?size]] (d/db conn) rules)

;; returns [["" 48381165] ["a" 94853] ["d" 24933642] ["e" 584]]

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

קוד התוכנית המלא בקלוז'ר הוא:

(ns main
  (:require [datomic.api :as d]))

(def db-uri "datomic:mem://fs99")

(d/create-database db-uri)

(def conn (d/connect db-uri))

(def schema
  [
   {:db/ident :entry/type
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/name
    :db/valueType :db.type/string
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/link-to
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry-link}
   {:db/ident :entry-file}
   {:db/ident :entry-dir}
   {:db/ident :entry/parent
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one}
   {:db/ident :entry/size
    :db/valueType :db.type/long
    :db/cardinality :db.cardinality/one}
   {:db/ident :fs/id
    :db/cardinality :db.cardinality/one
    :db/unique :db.unique/identity
    :db/valueType :db.type/string}
   {:db/ident :fs/cwd
    :db/cardinality :db.cardinality/one
    :db/valueType :db.type/ref}
   ])

@(d/transact conn schema)

(defn cwd []
  (let [db (d/db conn)]
    (d/q '[:find ?cwd .
           :where
           [?fs :fs/id "/"]
           [?fs :fs/cwd ?cwd]] db)))

(defn file [name size]
  @(d/transact conn [
                     {:entry/type :entry-file
                      :entry/name name
                      :entry/size size
                      :entry/parent (cwd)}
                     ]))

(defn dir [name]
  @(d/transact conn [
                     {:entry/type :entry-link
                      :entry/parent "d"
                      :entry/name ".."
                      :entry/link-to (cwd)}
                     {:entry/type :entry-link
                      :entry/parent "d"
                      :entry/name "."
                      :entry/link-to "d"}
                     {:db/id "d"
                      :entry/type :entry-dir
                      :entry/name name
                      :entry/parent (cwd)}
                     ]))


(defn cd [name]
  (let [db (d/db conn)
        to (d/q '[:find ?e .
                  :in $ ?cwd ?name
                  :where
                  [?e :entry/name ?name]
                  [?e :entry/parent ?cwd]]
                db
                (cwd) name)
        toe (d/entity db to)
        tod (if (= (:entry/type toe) :entry-link)
              (:db/id (first (filter #(= (:entry/type %1) :entry-dir) (iterate :entry/link-to toe))))
              to)]
    @(d/transact conn [{:fs/id "/"
                        :fs/cwd tod}])))

(def data [
           {:db/id "root" :entry/name "" :entry/type :entry-dir}
           {:fs/id "/" :fs/cwd "root"}
           ])

@(d/transact conn data)

(dir "a")
(file "b.txt" 14848514)
(file "c.dat" 8504156)
(dir "d")
(cd "a")
(dir "e")
(file "f" 29116)
(file "g" 2557)
(file "h.lst" 62596)
(cd "e")
(file "i" 584)
(cd "..")
(cd "..")
(cd "d")
(file "j" 4060174)
(file "d.log" 8033020)
(file "d.ext" 5626152)
(file "k" 7214296)

(d/q '[:find ?name :where
       [?e :entry/type :entry-file]
       [?e :entry/name ?name]] (d/db conn))

(def rules
'[[(belongs-to ?entry ?parent)
   [?entry :entry/parent ?parent]]
  [(inside ?entry ?parent)
   (belongs-to ?entry ?parent)]
  [(inside ?entry ?parent)
   (belongs-to ?entry ?middle)
   (inside ?middle ?parent)]])

(d/q '[:find ?name (sum ?size)
       :in $ %
       :where
       [?dir :entry/name ?name]
       [?dir :entry/type :entry-dir]
       (inside ?child ?dir)
       [?child :entry/size ?size]] (d/db conn) rules)