commit 442e240
shrub
·
2026-10-26 00:21:48 +0000 UTC
parent 1d15784
construct graph and print graphviz
M
Makefile
+4,
-3
1@@ -3,7 +3,7 @@
2 ATSCC = patscc
3 ATSFLAGS = -DATS_MEMALLOC_LIBC
4 LDLIBS = -L"$(PATSHOME)/ccomp/atslib/lib" -latslib
5-OBJ = main.o scan.o parse.o
6+OBJ = main.o scan.o parse.o graph.o
7
8 monk: $(OBJ)
9 $(ATSCC) $(ATSFLAGS) -o $@ $(OBJ) $(LDLIBS)
10@@ -12,8 +12,9 @@ monk: $(OBJ)
11 .dats.o:
12 $(ATSCC) $(ATSFLAGS) -c -o $@ $<
13
14-main.o scan.o parse.o: scan.sats
15-main.o parse.o: parse.sats
16+main.o scan.o parse.o graph.o: scan.sats
17+main.o parse.o graph.o: parse.sats
18+main.o graph.o: graph.sats types.sats
19
20 .PHONY: clean
21 clean:
M
README
+2,
-0
1@@ -2,3 +2,5 @@ monk
2 ----
3
4 (wip) implementation of ninja in ATS2!
5+
6+right now it accepts a subset of ninja syntax and emits graphviz.
+7,
-10
1@@ -1,12 +1,9 @@
2-# this is for testing!
3-#comment
4-rule cc
5- command = cc $
6- $in -o $out
7- deps = gcc
8+rule foo
9+ command = foo $in -o $out
10
11-rule shit
12- command = shit
13-
14-build poop: shit in
15+rule blah
16+ command = blah $in -o $out
17
18+build poop piss: foo in
19+build thing: blah poop stuff
20+build out: foo piss thing
+235,
-0
1@@ -0,0 +1,235 @@
2+#include "share/atspre_staload.hats"
3+#define ATS_DYNLOADFLAG 0
4+
5+staload "graph.sats"
6+staload "types.sats"
7+staload "parse.sats"
8+staload "libats/SATS/dynarray.sats"
9+staload _ = "libats/DATS/dynarray.dats"
10+staload "libats/SATS/hashtbl_linprb.sats"
11+staload _ = "libats/DATS/hashtbl_linprb.dats"
12+staload _ = "libats/DATS/hashfun.dats"
13+staload UN = "prelude/SATS/unsafe.sats"
14+
15+exception GraphErr of ()
16+
17+assume node_id = usize
18+assume action_id = usize
19+
20+vtypedef thegraph = @{
21+ nodes = dynarray(node),
22+ actions = dynarray(action),
23+ paths = hashtbl(string, node_id)
24+}
25+
26+assume graph = thegraph
27+
28+implement mkgraph() =
29+ let
30+ val n = dynarray_make_nil<node> (i2sz (64))
31+ val a = dynarray_make_nil<action> (i2sz (64))
32+ val p = hashtbl_make_nil<string, node_id> (i2sz(128))
33+ in
34+ @{nodes = n, actions = a, paths = p}
35+ end
36+
37+fun node_free(n: node): void =
38+ let
39+ val @{path = p, producer = pr, consumers = c} = n
40+ in
41+ strptr_free(p);
42+ list_vt_free(c)
43+ end
44+
45+fun action_free(a: action): void =
46+ let
47+ val @{inp = i, out = o, rule = r, bindings = b } = a
48+ in
49+ list_vt_free(o);
50+ list_vt_free(i);
51+ strptr_free(r);
52+ bindings_free(b)
53+ end
54+
55+(* define how to destroy one element for array node *)
56+implement array_uninitize$clear<node>(i, node) =
57+ let
58+ val () = node_free(node)
59+ (* mark as no longer containing anything*)
60+ prval () = topize(node)
61+ in ()
62+ end
63+
64+(* for array action *)
65+implement array_uninitize$clear<action>(i, action) =
66+ let
67+ val () = action_free(action)
68+ prval () = topize(action)
69+ in ()
70+ end
71+
72+implement graph_free(g) =
73+ let
74+ val @{nodes = n, actions = a, paths = p} = g
75+ var ncount: usize
76+ var acount: usize
77+ (* consume a dynarray and transfer into an arrayptr *)
78+ val nstorage = dynarray_getfree_arrayptr(n, ncount)
79+ val astorage = dynarray_getfree_arrayptr(a, acount)
80+ in
81+ (* this calls array_uninitize$clear *)
82+ arrayptr_freelin<node>(nstorage, ncount);
83+ arrayptr_freelin<action>(astorage, acount);
84+ hashtbl_free(p)
85+ end
86+
87+(* ideally we dont search + insert if absent (seeing as hashtbl_insert_opt returns the presence
88+ * of the id again) it would be better to have
89+ *
90+ * exists -> return id
91+ * doesent exist -> insert *)
92+(*if a node exists: return it, if it doesnet ,create it and return it*)
93+fun mknode(g: &graph, path: Strptr1): node_id =
94+ let
95+ (*XXX unsafe*)
96+ val found = hashtbl_search_opt<string, node_id>(g.paths, $UN.strptr2string(path))
97+ in
98+ case+ found of
99+ | ~Some_vt(id) => ( (*the node exists*)
100+ strptr_free(path); (*free the path we're searching for *)
101+ id (*return the node id*) )
102+ | ~None_vt() => ( (* the node doesnt exist *)
103+ let val newid = dynarray_get_size(g.nodes) (*the id will be the size of the node array *)
104+ val key = $UN.strptr2string(path) (*borrow key before putting path in the new node*)
105+ val newnode : node = @{path = path, producer = None(), consumers = nil_vt()}
106+ val () = dynarray_insert_atend_exn<node>(g.nodes, newnode)
107+ val prev = hashtbl_insert_opt<string, node_id>(g.paths, key, newid)
108+ in
109+ case+ prev of
110+ | ~None_vt( ) => newid
111+ | ~Some_vt(id) => $raise GraphErr
112+ end )
113+ end
114+
115+(* call mknode on a list of paths *)
116+fun intern_paths {n:nat} (g: &graph, paths: list_vt(Strptr1, n)): list_vt(node_id, n) =
117+ case+ paths of
118+ | ~nil_vt() => nil_vt()
119+ | ~cons_vt(path, rest) =>
120+ let
121+ val id = mknode(g, path)
122+ val ids = intern_paths(g, rest)
123+ val all = cons_vt(id, ids)
124+ in
125+ all
126+ end
127+
128+fun setprod(g: &graph, nid: node_id, aid: action_id): void =
129+ let
130+ var n: node = dynarray_takeout_at_exn<node>(g.nodes, nid) (*probably slow to takeout and reinsert*)
131+ val hasprod =
132+ case+ n.producer of
133+ | None( ) => false
134+ | Some(_) => true
135+ val () =
136+ if hasprod then () else n.producer := Some(aid)
137+ val () = dynarray_insert_at_exn<node>(g.nodes, nid, n)
138+ in
139+ if hasprod then $raise GraphErr else ()
140+ end
141+
142+fun setcons(g: &graph, nid: node_id, aid: action_id): void =
143+ let
144+ var n: node = dynarray_takeout_at_exn<node>(g.nodes, nid) (*probably slow to takeout and reinsert*)
145+ val ncs = cons_vt(aid, n.consumers)
146+ val () = n.consumers := ncs
147+ val () = dynarray_insert_at_exn<node>(g.nodes, nid, n)
148+ in
149+ ()
150+ end
151+
152+fun producers(g: &graph, ids: !List0_vt(node_id), aid: action_id): void =
153+ case+ ids of
154+ | nil_vt() => ()
155+ | @cons_vt(entry, rest) => (
156+ setprod(g, entry, aid);
157+ producers(g, rest, aid);
158+ fold@(ids) )
159+
160+fun consumers(g: &graph, ids: !List0_vt(node_id), aid: action_id): void =
161+ case+ ids of
162+ | nil_vt() => ()
163+ | @cons_vt(entry, rest) => (
164+ setcons(g, entry, aid);
165+ consumers(g, rest, aid);
166+ fold@(ids) )
167+
168+
169+fun mkedge(g: &graph, e: edge): void =
170+ let
171+ val @{output = o, rule = r, input = i, bindings = b} = e
172+ val no = intern_paths(g, o)
173+ val ni = intern_paths(g, i)
174+ val nextid = dynarray_get_size(g.actions)
175+ val () = producers(g, no, nextid)
176+ val () = consumers(g, ni, nextid)
177+ val newaction : action = @{inp = ni, out = no, rule = r, bindings = b}
178+ val () = dynarray_insert_atend_exn<action>(g.actions, newaction)
179+ in
180+ ()
181+ end
182+
183+(* fun mkedges(g: &graph, edges: List0_vt(edge)): void = *)
184+implement mkedges(g, edges) =
185+ case+ edges of
186+ | ~nil_vt() => ()
187+ | ~cons_vt(edge, rest) => (
188+ mkedge (g, edge);
189+ mkedges(g, rest) )
190+
191+fun dotnodes(g: &graph, i: usize): void =
192+ if i < dynarray_get_size(g.nodes) then
193+ let
194+ val n = dynarray_takeout_at_exn<node>(g.nodes, i)
195+ val () = println!(" n", i, " [shape=box, label=\"", n.path, "\"];")
196+ val () = dynarray_insert_at_exn<node>(g.nodes, i, n)
197+ in
198+ dotnodes(g, i + i2sz(1))
199+ end
200+ else ()
201+
202+fun inputarrows(nodes: !List0_vt(node_id), aid: action_id): void =
203+ case+ nodes of
204+ | nil_vt() => ()
205+ | @cons_vt(nid, rest) => (
206+ println!(" n", nid, " -> a", aid, ";");
207+ inputarrows(rest, aid);
208+ fold@(nodes) )
209+
210+fun outputarrows(nodes: !List0_vt(node_id), aid: action_id): void =
211+ case+ nodes of
212+ | nil_vt() => ()
213+ | @cons_vt(nid, rest) => (
214+ println!(" a", aid, " -> n", nid, ";");
215+ outputarrows(rest, aid);
216+ fold@(nodes) )
217+
218+fun dotactions(g: &graph, i: usize): void =
219+ if i < dynarray_get_size(g.actions) then
220+ let
221+ val a = dynarray_takeout_at_exn<action>(g.actions, i)
222+ val () = println!(" a", i, "[shape=ellipse, label=\"", a.rule, "\"];");
223+ val () = inputarrows (a.inp, i)
224+ val () = outputarrows(a.out, i)
225+ val () = dynarray_insert_at_exn<action>(g.actions, i, a)
226+ in
227+ dotactions(g, i + i2sz(1))
228+ end
229+ else()
230+
231+implement dot(g) = (
232+ println!("digraph build {");
233+ dotnodes(g, i2sz(0));
234+ dotactions(g, i2sz(0));
235+ println!("}") )
236+
+30,
-0
1@@ -0,0 +1,30 @@
2+staload "types.sats"
3+staload "parse.sats"
4+
5+(* abstract type *)
6+abst@ype node_id = usize
7+abst@ype action_id = usize
8+
9+absvt@ype graph = @{
10+ nodes = ptr,
11+ actions = ptr,
12+ paths = ptr
13+}
14+
15+vtypedef node = @{
16+ path = Strptr1,
17+ producer = Option(action_id),
18+ consumers = List0_vt(action_id)
19+}
20+
21+vtypedef action = @{
22+ inp = List0_vt(node_id), (* fucking reserved keywords *)
23+ out = List1_vt(node_id), (* every action must produce atleast 1 thing *)
24+ rule = Strptr1,
25+ bindings = List0_vt(binding)
26+}
27+
28+fun mkgraph(): graph
29+fun graph_free(g: graph): void
30+fun mkedges(g: &graph, edges: List0_vt(edge)): void
31+fun dot(g: &graph): void
+10,
-4
1@@ -4,6 +4,7 @@ staload "libats/SATS/stringbuf.sats"
2 staload "libats/DATS/stringbuf.dats"
3 staload "scan.sats"
4 staload "parse.sats"
5+staload "graph.sats"
6
7 implement main0 () =
8 let
9@@ -15,10 +16,15 @@ let
10 cur = fgetc0(manifest),
11 line = 1,
12 col = 1 }
13- val result = parse(s, nil_vt(), nil_vt(), nil_vt())
14-in
15- printrule(result.rules);
16- manifest_free(result);
17+ val parseres = parse(s, nil_vt(), nil_vt(), nil_vt())
18+ val @{rules = r, edges = e, variables = v} = parseres
19+ var g : graph = mkgraph()
20+ val () = mkedges(g, e)
21+in
22+ dot(g);
23+ (*mkedges takes ownership of e so just pass nothing*)
24+ manifest_free(@{rules = r, edges = nil_vt(), variables = v});
25+ graph_free(g);
26 let
27 val @{file = _, buf = buf, cur = _, line = _, col = _} = s
28 in
+4,
-4
1@@ -14,7 +14,7 @@ fun parts_free(p: List0_vt(stringpart)): void =
2 | ~Variable(text) => strptr_free(text) );
3 parts_free(rest) )
4
5-fun bindings_free(b: List0_vt(binding)): void =
6+implement bindings_free(b) =
7 case+ b of
8 (* tilde means destroy the list wrapper*)
9 | ~nil_vt() => ()
10@@ -272,7 +272,7 @@ in
11 in
12 parse(s, more, edges, variables)
13 end)
14- | ~TOKbuild(line,col) => (println!("build at: ", line,":", col);
15+ | ~TOKbuild(line,col) => ((*println!("build at: ", line,":", col);*)
16 (let
17 val b = build(s)
18 in
19@@ -290,14 +290,14 @@ in
20 edge_free(edges);
21 $raise ParseErr)
22 end))
23- | ~TOKvar (text, line,col) => (println!("var ", text, " at ", line,":", col);
24+ | ~TOKvar (text, line,col) => ((*println!("var ", text, " at ", line,":", col);*)
25 let
26 val entry = variable(s, text);
27 val more = cons_vt(entry, variables)
28 in
29 parse(s, rules, edges, more)
30 end)
31- | ~TOKeof(line,col) => (println!("eof at: ", line,":", col);
32+ | ~TOKeof(line,col) => ((*println!("eof at: ", line,":", col);*)
33 @{
34 rules = list_vt_reverse(rules),
35 edges = list_vt_reverse(edges),
+1,
-0
1@@ -23,6 +23,7 @@ vtypedef manifest = @{
2 variables = List0_vt(binding)
3 }
4
5+fun bindings_free(b: List0_vt(binding)): void
6 fun manifest_free(m: manifest): void
7 fun printrule(rules: !List0_vt(rule)): void
8 fun parse(s: &scanner, rules: List0_vt(rule), edges: List0_vt(edge), variables: List0_vt(binding)): manifest
+4,
-0
1@@ -0,0 +1,4 @@
2+typedef usize = size_t
3+typedef u8 = uint8
4+typedef u32 = uint32
5+typedef i64 = int64