bitsy_lang/
expr.rs

1mod typecheck;
2
3use super::*;
4use crate::sim::NetId;
5use std::collections::BTreeSet;
6use std::sync::Arc;
7use once_cell::sync::OnceCell;
8
9/// An expression.
10#[derive(Clone, Debug)]
11pub enum Expr {
12    /// A referenec to a port, reg, or node.
13    Reference(Loc, OnceCell<Type>, Path),
14    /// A referenec to a net. Used only in [`crate::sim::Sim`].
15    Net(Loc, OnceCell<Type>, NetId),
16    /// A literal Word.
17    Word(Loc, OnceCell<Type>, Option<Width>, u64),
18    /// A literal enum value.
19    Enum(Loc, OnceCell<Type>, Type, String),
20    /// Constructor (for `Valid<T>`)
21    Ctor(Loc, OnceCell<Type>, String, Vec<Arc<Expr>>),
22    /// Constructor for structs. Eg, `{ x = 0, y = 0}`.
23    Struct(Loc, OnceCell<Type>, Vec<(String, Arc<Expr>)>),
24    /// Let binding. Eg, `let x = a + b in x + x`.
25    Let(Loc, OnceCell<Type>, String, Arc<Expr>, Arc<Expr>),
26    /// A unary operation. Eg, `!0b101w3`.
27    UnOp(Loc, OnceCell<Type>, UnOp, Arc<Expr>),
28    /// A binary operation. Eg, `1w8 + 1w8`.
29    BinOp(Loc, OnceCell<Type>, BinOp, Arc<Expr>, Arc<Expr>),
30    /// An `if` expression.
31    If(Loc, OnceCell<Type>, Arc<Expr>, Arc<Expr>, Arc<Expr>),
32    /// A `match` expression.
33    Match(Loc, OnceCell<Type>, Arc<Expr>, Vec<MatchArm>),
34    /// A multiplexer. Eg, `mux(cond, a, b)`.
35    Mux(Loc, OnceCell<Type>, Arc<Expr>, Arc<Expr>, Arc<Expr>),
36    /// A concatenate expression. Eg, `cat(foo, 0w1)`.
37    Cat(Loc, OnceCell<Type>, Vec<Arc<Expr>>),
38    /// A sign extension expression.
39    Sext(Loc, OnceCell<Type>, Arc<Expr>),
40    /// A word expression. Used to cast user-defined `enum` types to their bit values.
41    ToWord(Loc, OnceCell<Type>, Arc<Expr>),
42    /// A vector constructor expression. Eg, `[0w2, 1w2, 2w2]`.
43    Vec(Loc, OnceCell<Type>, Vec<Arc<Expr>>),
44    IdxField(Loc, OnceCell<Type>, Arc<Expr>, String),
45    /// A static index. Eg, `foo[0]`.
46    Idx(Loc, OnceCell<Type>, Arc<Expr>, u64),
47    /// A static index range. Eg, `foo[8..4]`.
48    IdxRange(Loc, OnceCell<Type>, Arc<Expr>, u64, u64),
49    /// A function call. Eg, `foo(x, y)`.
50    Call(Loc, OnceCell<Type>, Arc<FnDef>, Vec<Arc<Expr>>),
51    /// A hole. Eg, `?foo`.
52    Hole(Loc, OnceCell<Type>, Option<String>),
53}
54
55/// A [`MatchArm`] is a case in a `match` expression.
56///
57/// In the expression:
58///
59/// ``` bitsy
60/// match v {
61///     @Valid(n) => n;
62///     @Invalid => 0;
63/// }
64/// ```
65///
66/// The two match arms are `@Valid(n) => n;` and `@Invalid => 0;`.
67#[derive(Clone, Debug)]
68pub struct MatchArm(pub Pat, pub Arc<Expr>);
69
70/// A [`Pat`] is a pattern for a `match` expression.
71///
72/// Notably different about Bitsy from other languages with a `match` or `case` statement,
73/// constructors and constant patterns are prefixed by an `@` symbol to distinguish them
74/// from variable bindings. For instance:
75///
76/// * `@Valid(n)`
77/// * `@Invalid`
78/// * `@Opcode::OP`
79#[derive(Clone, Debug)]
80pub enum Pat {
81    At(String, Vec<Pat>),
82    Bind(String),
83    Otherwise,
84}
85
86impl Pat {
87    pub fn bound_vars(&self) -> Vec<Path> {
88        let mut results = vec![];
89        match self {
90            Pat::At(_s, pats) => {
91                for pat in pats {
92                    results.extend(pat.bound_vars());
93                }
94            },
95            Pat::Bind(x) => results.push(x.clone().into()),
96            Pat::Otherwise => (),
97        }
98        results.sort();
99        results.dedup();
100        results
101    }
102}
103
104impl MatchArm {
105    fn free_vars(&self) -> Vec<Path> {
106        let mut results = vec![];
107        let MatchArm(pat, e) = self;
108        let bound_vars = pat.bound_vars();
109        for x in e.free_vars().iter() {
110            if !bound_vars.contains(x) {
111                results.push(x.clone());
112            }
113        }
114        results.sort();
115        results.dedup();
116        results
117
118    }
119}
120
121impl HasLoc for Expr {
122    fn loc(&self) -> Loc {
123        match self {
124            Expr::Net(loc, _typ, _netid) => loc.clone(),
125            Expr::Reference(loc, _typ, _path) => loc.clone(),
126            Expr::Word(loc, _typ, _width, _val) => loc.clone(),
127            Expr::Enum(loc, _typ, _typedef, _name) => loc.clone(),
128            Expr::Ctor(loc, _typ, _name, _e) => loc.clone(),
129            Expr::Struct(loc, _typ, _fields) => loc.clone(),
130            Expr::Let(loc, _typ, _name, _e, _b) => loc.clone(),
131            Expr::UnOp(loc, _typ, _op, _e) => loc.clone(),
132            Expr::BinOp(loc, _typ, _op, _e1, _e2) => loc.clone(),
133            Expr::If(loc, _typ, _cond, _e1, _e2) => loc.clone(),
134            Expr::Match(loc, _typ, _e, _arms) => loc.clone(),
135            Expr::Mux(loc, _typ, _cond, _e1, _e2) => loc.clone(),
136            Expr::Cat(loc, _typ, _es) => loc.clone(),
137            Expr::Sext(loc, _typ, _e) => loc.clone(),
138            Expr::ToWord(loc, _typ, _e) => loc.clone(),
139            Expr::Vec(loc, _typ, _es) => loc.clone(),
140            Expr::IdxField(loc, _typ, _e, _field) => loc.clone(),
141            Expr::Idx(loc, _typ, _e, _i) => loc.clone(),
142            Expr::IdxRange(loc, _typ, _e, _j, _i) => loc.clone(),
143            Expr::Call(loc, _typ, _fndef, _es) => loc.clone(),
144            Expr::Hole(loc, _typ, _opt_name) => loc.clone(),
145        }
146    }
147}
148
149impl HasLoc for Arc<Expr> {
150    fn loc(&self) -> Loc {
151        let e: &Expr = &*self;
152        e.loc()
153    }
154}
155
156#[derive(Debug, Eq, PartialEq, Clone, Copy)]
157pub enum UnOp {
158    Not,
159}
160
161#[derive(Debug, Eq, PartialEq, Clone, Copy)]
162pub enum BinOp {
163    Add,
164    AddCarry,
165    Sub,
166//    SubBorrow,
167    And,
168    Or,
169    Xor,
170    Eq,
171    Neq,
172    Lt,
173}
174
175impl Expr {
176    pub fn assert_has_types(&self) {
177        let mut func = |e: &Expr| {
178            if let Expr::Word(_loc, typ, _width, _n) = e {
179                typ.get().expect(&format!("Expression was not typechecked: {e:?}"));
180            }
181        };
182        self.with_subexprs(&mut func);
183    }
184
185    /// Walk the expression tree in-order, calling `callback` for each subexpression.
186    pub fn with_subexprs(&self, callback: &mut dyn FnMut(&Expr)) {
187        match self {
188            Expr::Reference(_loc, _typ, _path) => callback(self),
189            Expr::Net(_loc, _typ, _netid) => callback(self),
190            Expr::Word(_loc, _typ, _width, _value) => callback(self),
191            Expr::Enum(_loc, _typ, _typedef, _name) => callback(self),
192            Expr::Ctor(_loc, _typ, _name, es) => {
193                callback(self);
194                for e in es {
195                    e.with_subexprs(callback);
196                }
197            },
198            Expr::Struct(_loc, _typ, fields) => {
199                callback(self);
200                for (_name, e) in fields {
201                    e.with_subexprs(callback);
202                }
203            },
204            Expr::Let(_loc, _typ, _name, e, b) => {
205                callback(self);
206                e.with_subexprs(callback);
207                b.with_subexprs(callback);
208            },
209            Expr::UnOp(_loc, _typ, _op, e) => {
210                callback(self);
211                e.with_subexprs(callback);
212            }
213            Expr::BinOp(_loc, _typ, _op, e1, e2) => {
214                callback(self);
215                e1.with_subexprs(callback);
216                e2.with_subexprs(callback);
217            },
218            Expr::If(_loc, _typ, cond, e1, e2) => {
219                callback(self);
220                cond.with_subexprs(callback);
221                e1.with_subexprs(callback);
222                e2.with_subexprs(callback);
223            },
224            Expr::Match(_loc, _typ, e, arms) => {
225                callback(self);
226                callback(e);
227                for MatchArm(_pat, arm_e) in arms {
228                    arm_e.with_subexprs(callback);
229                }
230            }
231            Expr::Mux(_loc, _typ, cond, e1, e2) => {
232                callback(self);
233                cond.with_subexprs(callback);
234                e1.with_subexprs(callback);
235                e2.with_subexprs(callback);
236            },
237            Expr::Cat(_loc, _typ, es) => {
238                callback(self);
239                for e in es {
240                    e.with_subexprs(callback);
241                }
242            },
243            Expr::Sext(_loc, _typ, e) => {
244                callback(self);
245                e.with_subexprs(callback);
246            },
247            Expr::ToWord(_loc, _typ, e) => {
248                callback(self);
249                e.with_subexprs(callback);
250            },
251            Expr::Vec(_loc, _typ, es) => {
252                callback(self);
253                for e in es {
254                    e.with_subexprs(callback);
255                }
256            },
257            Expr::IdxField(_loc, _typ, e, _field) => {
258                callback(self);
259                e.with_subexprs(callback);
260            },
261            Expr::Idx(_loc, _typ, e, _i) => {
262                callback(self);
263                e.with_subexprs(callback);
264            },
265            Expr::IdxRange(_loc, _typ, e, _j, _i) => {
266                callback(self);
267                e.with_subexprs(callback);
268            },
269            Expr::Call(_loc, _typ, _fndef, es) => {
270                callback(self);
271                for e in es {
272                    e.with_subexprs(callback);
273                }
274            },
275            Expr::Hole(_loc, _typ, _name) => {
276                callback(self);
277            },
278        }
279    }
280
281    pub fn paths(&self) -> Vec<Path> {
282        let paths = std::cell::RefCell::new(vec![]);
283        let mut func = |e: &Expr| {
284            if let Expr::Reference(_loc, _typ, path) = e {
285                paths.borrow_mut().push(path.clone());
286            } else if let Expr::Net(_loc, _typ, _netid) = e {
287                panic!("paths() only works on symbolic expressions.");
288            }
289        };
290        self.with_subexprs(&mut func);
291
292        let mut results = paths.into_inner();
293        results.sort();
294        results.dedup();
295        results
296    }
297
298    pub fn is_constant(&self) -> bool {
299        self.free_vars().is_empty()
300    }
301
302    pub fn free_vars(&self) -> BTreeSet<Path> {
303        match self {
304            Expr::Reference(_loc, _typ, path) => vec![path.clone()].iter().cloned().collect(),
305            Expr::Net(_loc, _typ, _netid) => BTreeSet::new(),
306            Expr::Word(_loc, _typ, _width, _value) => BTreeSet::new(),
307            Expr::Enum(_loc, _typ, _typedef, _name) => BTreeSet::new(),
308            Expr::Ctor(_loc, _typ, _name, es) => {
309                let mut result = BTreeSet::new();
310                for e in es {
311                    result.extend(e.free_vars())
312                }
313                result
314            },
315            Expr::Struct(_loc, _typ, fields) => {
316                let mut result = BTreeSet::new();
317                for (_name, e) in fields {
318                    result.extend(e.free_vars())
319                }
320                result
321            },
322            Expr::Let(_loc, _typ, x, e, b) => {
323                let mut result = b.free_vars();
324                result.remove(&x.to_string().into());
325                result.union(&e.free_vars()).cloned().collect()
326            },
327            Expr::UnOp(_loc, _typ, _op, e) => e.free_vars(),
328            Expr::BinOp(_loc, _typ, _op, e1, e2) => e1.free_vars().union(&e2.free_vars()).cloned().collect(),
329            Expr::If(_loc, _typ, cond, e1, e2) => {
330                cond.free_vars()
331                    .union(&e1.free_vars())
332                    .cloned()
333                    .collect::<BTreeSet<_>>()
334                    .union(&e2.free_vars())
335                    .cloned()
336                    .collect()
337            },
338            Expr::Match(_loc, _typ, e, arms) => {
339                let mut free_vars: Vec<_> = e.free_vars().into_iter().collect();
340                for arm in arms {
341                    free_vars.extend(arm.free_vars());
342                }
343                free_vars.into_iter().collect()
344            },
345            Expr::Mux(_loc, _typ, cond, e1, e2) => {
346                cond.free_vars()
347                    .union(&e1.free_vars())
348                    .cloned()
349                    .collect::<BTreeSet<_>>()
350                    .union(&e2.free_vars())
351                    .cloned()
352                    .collect()
353            },
354            Expr::Cat(_loc, _typ, es) => {
355                let mut result = BTreeSet::new();
356                for e in es {
357                    result.extend(e.free_vars())
358                }
359                result
360            },
361            Expr::ToWord(_loc, _typ, e) => e.free_vars(),
362            Expr::Vec(_loc, _typ, es) => {
363                let mut result = BTreeSet::new();
364                for e in es {
365                    result.extend(e.free_vars())
366                }
367                result
368            },
369            Expr::Sext(_loc, _typ, e) => e.free_vars(),
370            Expr::IdxField(_loc, _typ, e, _field) => e.free_vars(),
371            Expr::Idx(_loc, _typ, e, _i) => e.free_vars(),
372            Expr::IdxRange(_loc, _typ, e, _j, _i) => e.free_vars(),
373            Expr::Call(_loc, _typ, _fndef, es) => {
374                let mut result = BTreeSet::new();
375                for e in es {
376                    result.extend(e.free_vars())
377                }
378                result
379            },
380            Expr::Hole(_loc, _typ, _name) => BTreeSet::new(),
381        }
382    }
383
384    pub fn depends_on(&self, path: Path) -> bool {
385        self.paths().contains(&path)
386    }
387
388    pub fn depends_on_net(&self, net_id: NetId) -> bool {
389        match self {
390            Expr::Reference(_loc, _typ, _path) => false,
391            Expr::Net(_loc, _typ, other_netid) => net_id == *other_netid,
392            Expr::Word(_loc, _typ, _width, _value) => false,
393            Expr::Enum(_loc, _typ, _typedef, _name) => false,
394            Expr::Ctor(_loc, _typ, _name, es) => es.iter().any(|e| e.depends_on_net(net_id)),
395            Expr::Struct(_loc, _typ, fields) => fields.iter().any(|(_name, e)| e.depends_on_net(net_id)),
396            Expr::Let(_loc, _typ, _name, e, b) => e.depends_on_net(net_id) || b.depends_on_net(net_id),
397            Expr::Match(_loc, _typ, e, arms) => e.depends_on_net(net_id) || arms.iter().any(|MatchArm(_pat, arm_e)| arm_e.depends_on_net(net_id)),
398            Expr::UnOp(_loc, _typ, _op, e) => e.depends_on_net(net_id),
399            Expr::BinOp(_loc, _typ, _op, e1, e2) => e1.depends_on_net(net_id) || e2.depends_on_net(net_id),
400            Expr::If(_loc, _typ, cond, e1, e2) => cond.depends_on_net(net_id) || e1.depends_on_net(net_id) || e2.depends_on_net(net_id),
401            Expr::Mux(_loc, _typ, cond, e1, e2) => cond.depends_on_net(net_id) || e1.depends_on_net(net_id) || e2.depends_on_net(net_id),
402            Expr::Cat(_loc, _typ, es) => es.iter().any(|e| e.depends_on_net(net_id)),
403            Expr::Sext(_loc, _typ, e) => e.depends_on_net(net_id),
404            Expr::ToWord(_loc, _typ, e) => e.depends_on_net(net_id),
405            Expr::Vec(_loc, _typ, es) => es.iter().any(|e| e.depends_on_net(net_id)),
406            Expr::IdxField(_loc, _typ, e, _field) => e.depends_on_net(net_id),
407            Expr::Idx(_loc, _typ, e, _i) => e.depends_on_net(net_id),
408            Expr::IdxRange(_loc, _typ, e, _j, _i) => e.depends_on_net(net_id),
409            Expr::Call(_loc, _typ, _fndef, es) => es.iter().any(|e| e.depends_on_net(net_id)),
410            Expr::Hole(_loc, _typ, _name) => false,
411        }
412    }
413
414    pub fn type_of(&self) -> Type {
415        self.type_of_cell().unwrap().get().unwrap().clone()
416    }
417
418    fn type_of_cell(&self) -> Option<&OnceCell<Type>> {
419        match self {
420            Expr::Net(_loc, typ, _netid) => Some(typ),
421            Expr::Reference(_loc, typ, _path) => Some(typ),
422            Expr::Word(_loc, typ, _width, _val) => Some(typ),
423            Expr::Enum(_loc, typ, _typedef, _name) => Some(typ),
424            Expr::Ctor(_loc, typ, _name, _e) => Some(typ),
425            Expr::Struct(_loc, typ, _fields) => Some(typ),
426            Expr::Let(_loc, typ, _name, _e, _b) => Some(typ),
427            Expr::UnOp(_loc, typ, _op, _e) => Some(typ),
428            Expr::BinOp(_loc, typ, _op, _e1, _e2) => Some(typ),
429            Expr::If(_loc, typ, _cond, _e1, _e2) => Some(typ),
430            Expr::Match(_loc, typ, _e, _arms) => Some(typ),
431            Expr::Mux(_loc, typ, _cond, _e1, _e2) => Some(typ),
432            Expr::Cat(_loc, typ, _es) => Some(typ),
433            Expr::Sext(_loc, typ, _e) => Some(typ),
434            Expr::ToWord(_loc, typ, _e) => Some(typ),
435            Expr::Vec(_loc, typ, _es) => Some(typ),
436            Expr::Idx(_loc, typ, _e, _i) => Some(typ),
437            Expr::IdxField(_loc, typ, _e, _field) => Some(typ),
438            Expr::IdxRange(_loc, typ, _e, _j, _i) => Some(typ),
439            Expr::Call(_loc, typ, _fndef, _es) => Some(typ),
440            Expr::Hole(_loc, typ, _opt_name) => Some(typ),
441        }
442    }
443}
bitsy_lang/expr.rs

bitsy_lang/
expr.rs
