ast.rs 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. use std::fmt;
  2. pub type Name = string_interner::DefaultSymbol;
  3. pub struct ASTArena {
  4. strings: string_interner::StringInterner,
  5. exprs: Vec<Expr>,
  6. }
  7. impl Default for ASTArena {
  8. fn default() -> Self {
  9. Self::new()
  10. }
  11. }
  12. impl ASTArena {
  13. pub fn new() -> ASTArena {
  14. ASTArena {
  15. strings: string_interner::StringInterner::new(),
  16. exprs: vec![Expr::Nil],
  17. }
  18. }
  19. pub fn expr_nil(&self) -> ExprRef {
  20. ExprRef { idx: 0 }
  21. }
  22. pub fn add_expr(&mut self, e: Expr) -> ExprRef {
  23. let idx = self.exprs.len();
  24. self.exprs.push(e);
  25. ExprRef { idx }
  26. }
  27. pub fn add_string(&mut self, s: &str) -> Name {
  28. self.strings.get_or_intern(s)
  29. }
  30. pub fn show_stmt(&self, stmt: &Stmt, f: &mut fmt::Formatter) -> fmt::Result {
  31. match stmt {
  32. Stmt::Puts(expr) => {
  33. write!(f, "Puts ")?;
  34. self.show_expr(&self[*expr], f, 0)
  35. }
  36. Stmt::Fix(name) => writeln!(f, "Fix {}", &self[*name]),
  37. Stmt::Assn(fixed, name, expr) => {
  38. write!(
  39. f,
  40. "Assn {} {} ",
  41. if *fixed { "fixed" } else { "" },
  42. &self[*name]
  43. )?;
  44. self.show_expr(&self[*expr], f, 0)
  45. }
  46. Stmt::LitAssn(fixed, name, strs) => {
  47. write!(
  48. f,
  49. "LitAssn {} {}, [ ",
  50. if *fixed { "fixed" } else { "" },
  51. &self[*name],
  52. )?;
  53. for str in strs.iter() {
  54. write!(f, " {} ", str)?;
  55. }
  56. writeln!(f, "]")
  57. }
  58. }
  59. }
  60. fn indent(&self, f: &mut fmt::Formatter, depth: usize) -> fmt::Result {
  61. for _ in 0..depth {
  62. write!(f, " ")?;
  63. }
  64. Ok(())
  65. }
  66. fn show_pat(&self, pat: &Pat, f: &mut fmt::Formatter) -> fmt::Result {
  67. match pat {
  68. Pat::Var(n) => write!(f, "{}", &self[*n]),
  69. Pat::Lit(Literal::Atom(n)) => write!(f, "{}", &self[*n]),
  70. Pat::Lit(lit) => write!(f, "{:?}", lit),
  71. Pat::Tup(tup) => {
  72. write!(f, "Tup( ")?;
  73. for t in tup {
  74. self.show_pat(t, f)?;
  75. write!(f, " ")?;
  76. }
  77. write!(f, ")")
  78. }
  79. }
  80. }
  81. fn show_expr(&self, expr: &Expr, f: &mut fmt::Formatter, depth: usize) -> fmt::Result {
  82. match expr {
  83. Expr::Nil => writeln!(f, "Nil"),
  84. Expr::Var(v) => writeln!(f, "Var({})", &self[*v]),
  85. Expr::Lit(Literal::Atom(n)) => writeln!(f, "Lit(Atom({}))", &self[*n]),
  86. Expr::Lit(lit) => writeln!(f, "{:?}", lit),
  87. Expr::Range(from, to) => {
  88. writeln!(f, "Range(")?;
  89. self.indent(f, depth + 2)?;
  90. self.show_expr(&self[*from], f, depth + 2)?;
  91. self.indent(f, depth + 2)?;
  92. self.show_expr(&self[*to], f, depth + 2)?;
  93. self.indent(f, depth)?;
  94. writeln!(f, ")")
  95. }
  96. Expr::Ap(func, arg) => {
  97. writeln!(f, "Ap(")?;
  98. self.indent(f, depth + 2)?;
  99. self.show_expr(&self[*func], f, depth + 2)?;
  100. self.indent(f, depth + 2)?;
  101. self.show_expr(&self[*arg], f, depth + 2)?;
  102. self.indent(f, depth)?;
  103. writeln!(f, ")")
  104. }
  105. Expr::Tup(expr) => {
  106. writeln!(f, "Tup(")?;
  107. for e in expr {
  108. self.indent(f, depth + 2)?;
  109. self.show_expr(&self[*e], f, depth + 2)?;
  110. }
  111. self.indent(f, depth)?;
  112. writeln!(f, ")")
  113. }
  114. Expr::Cat(expr) => {
  115. writeln!(f, "Cat(")?;
  116. for e in expr {
  117. self.indent(f, depth + 2)?;
  118. self.show_expr(&self[*e], f, depth + 2)?;
  119. }
  120. self.indent(f, depth)?;
  121. writeln!(f, ")")
  122. }
  123. Expr::Chc(expr) => {
  124. writeln!(f, "Chc(")?;
  125. for e in expr {
  126. if let Some(s) = e.weight {
  127. self.indent(f, depth + 2)?;
  128. writeln!(f, "{}:", s)?;
  129. self.indent(f, depth + 4)?;
  130. self.show_expr(&self[e.value], f, depth + 4)?;
  131. } else {
  132. self.indent(f, depth + 2)?;
  133. self.show_expr(&self[e.value], f, depth + 2)?;
  134. }
  135. }
  136. self.indent(f, depth)?;
  137. writeln!(f, ")")
  138. }
  139. Expr::Let(name, expr, body) => {
  140. writeln!(f, "Let({}", &self[*name])?;
  141. self.indent(f, depth + 2)?;
  142. self.show_expr(&self[*expr], f, depth + 2)?;
  143. self.indent(f, depth + 2)?;
  144. self.show_expr(&self[*body], f, depth + 2)?;
  145. self.indent(f, depth)?;
  146. writeln!(f, ")")
  147. }
  148. Expr::Fun(cases) => {
  149. writeln!(f, "Fun(")?;
  150. for case in cases {
  151. self.indent(f, depth + 2)?;
  152. self.show_pat(&case.pat, f)?;
  153. writeln!(f, " =>")?;
  154. self.indent(f, depth + 4)?;
  155. self.show_expr(&self[case.expr], f, depth + 4)?;
  156. }
  157. self.indent(f, depth)?;
  158. writeln!(f, ")")
  159. }
  160. }
  161. }
  162. }
  163. impl std::ops::Index<string_interner::DefaultSymbol> for ASTArena {
  164. type Output = str;
  165. fn index(&self, sf: string_interner::DefaultSymbol) -> &str {
  166. self.strings.resolve(sf).unwrap()
  167. }
  168. }
  169. impl std::ops::Index<ExprRef> for ASTArena {
  170. type Output = Expr;
  171. fn index(&self, rf: ExprRef) -> &Self::Output {
  172. &self.exprs[rf.idx]
  173. }
  174. }
  175. /// A `Printable` struct is a bundle of another value and an
  176. /// `ASTArena`, which allows us to fetch the various indices and
  177. /// dereference the interned strings.
  178. pub struct Printable<'a, T> {
  179. arena: &'a ASTArena,
  180. value: &'a T,
  181. }
  182. impl<'a> std::fmt::Debug for Printable<'a, Stmt> {
  183. fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  184. self.arena.show_stmt(self.value, f)
  185. }
  186. }
  187. impl<'a> std::fmt::Debug for Printable<'a, Expr> {
  188. fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  189. self.arena.show_expr(self.value, f, 0)
  190. }
  191. }
  192. /// A top-level Matzo statement
  193. #[derive(Debug, Clone, PartialEq, Eq)]
  194. pub enum Stmt {
  195. /// evaluate and print the value of an expression
  196. Puts(ExprRef),
  197. /// replace a named item with the forced version of that item
  198. Fix(Name),
  199. /// assign a value to a name which may or may not be forced
  200. Assn(bool, Name, ExprRef),
  201. /// assign one of a set of strings to a name, which may or may not
  202. /// be forced
  203. LitAssn(bool, Name, Vec<String>),
  204. }
  205. impl Stmt {
  206. pub fn show<'a>(&'a self, ast: &'a ASTArena) -> Printable<'a, Stmt> {
  207. Printable {
  208. arena: ast,
  209. value: self,
  210. }
  211. }
  212. }
  213. /// A Matzo expression
  214. #[derive(Debug, Clone, PartialEq, Eq)]
  215. pub enum Expr {
  216. Var(Name),
  217. Cat(Vec<ExprRef>),
  218. Chc(Vec<Choice>),
  219. Lit(Literal),
  220. Ap(ExprRef, ExprRef),
  221. Tup(Vec<ExprRef>),
  222. Let(Name, ExprRef, ExprRef),
  223. Fun(Vec<Case>),
  224. Range(ExprRef, ExprRef),
  225. Nil,
  226. }
  227. #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  228. pub struct ExprRef {
  229. idx: usize,
  230. }
  231. /// A single case in an anonymous function or `case` statement
  232. #[derive(Debug, Clone, PartialEq, Eq)]
  233. pub struct Case {
  234. pub pat: Pat,
  235. pub expr: ExprRef,
  236. }
  237. /// A pattern, e.g. in an anonymous function or `case` statement
  238. #[derive(Debug, Clone, PartialEq, Eq)]
  239. pub enum Pat {
  240. Var(Name),
  241. Lit(Literal),
  242. Tup(Vec<Pat>),
  243. }
  244. /// A single element in a choice, with an optional weight (which
  245. /// defaults to 1) and a value
  246. #[derive(Debug, Clone, PartialEq, Eq)]
  247. pub struct Choice {
  248. pub weight: Option<i64>,
  249. pub value: ExprRef,
  250. }
  251. impl Choice {
  252. /// Fetch a weight from a `Choice`, defaulting to 1
  253. pub fn weight(&self) -> i64 {
  254. self.weight.unwrap_or(1)
  255. }
  256. }
  257. /// An atomic literal: a string, a number, or an atom
  258. #[derive(Debug, Clone, PartialEq, Eq)]
  259. pub enum Literal {
  260. Str(String),
  261. Atom(Name),
  262. Num(i64),
  263. }