1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
//! # Misp - (My / Monad's / MIR) Lisp
//! This module provides a statically typed Lisp dialect that compiles to [`MIR`](super).
mod parse;
use ::core::convert::TryInto;
use ::core::iter;
use super::{MirGraph, MirNode, Region};
use ::id_arena::Id;
use ::petgraph::graph::NodeIndex;
use parse::Name;
/// The core MIR library, defined in Misp.
const CORE_SRC: &str = include_str!("core.lisp");
#[derive(Debug)]
pub(super) struct Core {
mir: MirGraph,
roll: NodeIndex,
simple_filter: NodeIndex,
explode: NodeIndex,
}
impl Core {
pub(super) fn compile() -> Self {
use parse::Term;
let mut ast = parse::parse_program(CORE_SRC).unwrap();
println!("{}", ast.fmt_sexpr());
macro_rules! name {
($name:tt) => {
parse::Path::ident(Name::lookup(&ast.names, stringify!($name)).unwrap())
};
}
macro_rules! t {
($id:expr) => {
ast.arena[$id].clone()
};
}
// We're guaranteed to have a List at the top level, since
// the parser sticks everything in an implicit progn.
let implicit_progn = ast.arena[ast.top].clone().unwrap_list();
let progn = parse::Path::hidden_magic(&mut ast.names, vec!["progn"]);
assert_eq!(
ast.arena[implicit_progn[0]].clone().unwrap_variable(),
progn
);
let mut mir = MirGraph::new();
// TODO: locals must be reachable from inside inner regions,
// which entails adding a chain of edges to draw them into new ports
/// Some piece of information that describes two things:
/// - Where inside of its containing region a node is
/// - Whether the current region is the containing region of that node,
/// in a way that can be checked in constant time.
struct InvariantNodeId {
node: NodeIndex,
region: usize,
}
impl InvariantNodeId {
fn new(region: &MirGraph, node: NodeIndex) -> Self {
Self {
node,
region: region as *const MirGraph as usize,
}
}
fn in_current(&self, region: &MirGraph) -> bool {
self.region == region as *const MirGraph as usize
}
}
let mut locals = ::quickscope::ScopeMap::<&str, InvariantNodeId>::new();
for elem in implicit_progn
.into_iter()
.skip(1)
.map(|elem| &ast.arena[elem])
{
// TODO: lower top level elements
match elem {
Term::List(elems) => {
let form = t![elems[0]].unwrap_variable();
// Pretty much the only permitted form here is `defun`, for now.
assert_eq!(form, name!(defun));
let name = t![elems[1]].unwrap_variable().into_ident().unwrap();
dbg!(&ast.names[*name.key()]);
let params = t![elems[2]]
.unwrap_list()
.into_iter()
.map(|param| {
let param = t![param].unwrap_list();
assert_eq!(param.len(), 2);
let name = t![param[0]].unwrap_variable().into_ident().unwrap();
let ty = param[1];
(name, ty)
})
.collect::<Vec<_>>();
println!(
"{:?}",
params
.iter()
.map(|(n, t)| { (&ast.names[*n.key()], ast.fmt_term(*t)) })
.collect::<Vec<_>>()
);
let return_ty = t![elems[3]].unwrap_list();
assert_eq!(t![return_ty[0]].unwrap_variable(), name!(->));
// Every function is required to return a value, at least for now.
let ret_val_ty = return_ty[1];
// Not every function returns intermediate results.
let ret_int_ty = return_ty.get(2);
println!(
"-> {:?}, {:?}",
ast.fmt_term(ret_val_ty),
ret_int_ty.map(|t| ast.fmt_term(*t))
);
// TODO: lower function body
enum LexicalScopeKind {
Function,
Let,
DoWhile,
If,
}
struct Scope<'a> {
scope_kind: LexicalScopeKind,
body_cursor: &'a [Id<Term>],
input_edges_queue: Vec<(u8, Name)>,
last_expression: Option<NodeIndex>,
}
let mut scope_stack = Vec::<Scope>::new();
let mut current_scope = Scope {
scope_kind: LexicalScopeKind::Function,
body_cursor: &elems[4..],
input_edges_queue: Vec::new(),
last_expression: None,
};
macro_rules! open_scope {
() => {{
scope_stack.push(current_scope);
locals.push_layer();
}};
}
// MIR regions are independent from lexical scope,
// so they get their own stack.
let mut region_stack = Vec::<MirGraph>::new();
let mut current_region = MirGraph::new();
loop {
let mut it = iter::from_fn({
// This would be unnecessary in 2021 Edition, but
// I'd like to put whatever migration work is necessary
// there off until I get this into a commit.
let body_cursor = &mut current_scope.body_cursor;
move || {
if let [x, rest @ ..] = body_cursor {
*body_cursor = rest;
Some(x)
} else {
None
}
}
});
while let Some((id, form)) = it.next().map(|id| (*id, &ast.arena[*id])) {
match form {
Term::CreateRef(_) => todo!("lowering references"),
Term::List(list) => {
let first = t![list[0]].unwrap_variable();
todo!("lowering lists")
}
Term::Variable(_) => todo!("lowering variable usage"),
Term::IntegerLiteral(int) => {
let node = current_region
.add_node(MirNode::Integer((*int).try_into().unwrap()));
current_scope.last_expression = Some(node);
}
Term::StringLiteral(_) => todo!("strings"),
Term::Comment(_) => todo!("probably dispose of comments"),
}
}
break;
}
assert!(region_stack.is_empty());
let end = current_region.add_node(MirNode::End);
let definition = MirNode::FunctionDefinition(Region {
graph: current_region,
end,
});
let func = mir.add_node(definition);
}
Term::CreateRef(_)
| Term::Variable(_)
| Term::IntegerLiteral(_)
| Term::StringLiteral(_) => {
// We do not permit lowering regular values at the top level,
// as the Core library is not an end program.
// It does not make sense to define a bare end value with no dependents.
todo!("reject regular values at the top level")
}
Term::Comment(_) => (),
}
}
Self {
mir,
roll: locals["roll"].node,
simple_filter: locals["simple_filter"].node,
explode: locals["explode"].node,
}
}
}