1use super::form::Form;
2use super::reader::{Position, Reader};
3
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct Span {
6 pub start: Position,
7 pub end: Position,
8}
9
10#[derive(Debug, Clone, PartialEq)]
11pub struct SpannedForm {
12 pub form: Form,
13 pub span: Span,
14 pub children: Vec<SpannedForm>,
15}
16impl SpannedForm {
17 pub fn descendants(&self) -> Box<dyn Iterator<Item = &SpannedForm> + '_> {
18 Box::new(
19 self.children
20 .iter()
21 .flat_map(|child| std::iter::once(child).chain(child.descendants())),
22 )
23 }
24}
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub struct ParseError {
27 pub message: String,
28 pub position: Position,
29}
30impl std::fmt::Display for ParseError {
31 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
32 write!(
33 f,
34 "{} [line {}, column {}]",
35 self.message, self.position.line, self.position.column
36 )
37 }
38}
39impl std::error::Error for ParseError {}
40
41type Result<T> = std::result::Result<T, ParseError>;
42
43fn anonymous_arguments(
44 form: &Form,
45 maximum: &mut usize,
46 variadic: &mut bool,
47) -> std::result::Result<(), String> {
48 match form {
49 Form::Symbol(name) if name == "%" => *maximum = (*maximum).max(1),
50 Form::Symbol(name) if name == "%&" => *variadic = true,
51 Form::Symbol(name) if name.starts_with('%') => {
52 let index = name[1..]
53 .parse::<usize>()
54 .map_err(|_| format!("Invalid anonymous function argument: {name}"))?;
55 if index == 0 {
56 return Err("Anonymous function arguments begin at %1".into());
57 }
58 *maximum = (*maximum).max(index);
59 }
60 Form::List(values) | Form::Vector(values) | Form::Set(values) => {
61 for value in values {
62 anonymous_arguments(value, maximum, variadic)?;
63 }
64 }
65 Form::Map(entries) => {
66 for (key, value) in entries {
67 anonymous_arguments(key, maximum, variadic)?;
68 anonymous_arguments(value, maximum, variadic)?;
69 }
70 }
71 Form::Metadata(metadata, value) => {
72 anonymous_arguments(metadata, maximum, variadic)?;
73 anonymous_arguments(value, maximum, variadic)?;
74 }
75 Form::Tagged(_, value) => anonymous_arguments(value, maximum, variadic)?,
76 _ => {}
77 }
78 Ok(())
79}
80
81fn rewrite_anonymous_arguments(form: Form, id: u64) -> Form {
82 match form {
83 Form::Symbol(name) if name == "%" || name == "%1" => {
84 Form::Symbol(format!("__reader_fn_{id}_1"))
85 }
86 Form::Symbol(name) if name == "%&" => Form::Symbol(format!("__reader_fn_{id}_rest")),
87 Form::Symbol(name) if name.starts_with('%') => {
88 Form::Symbol(format!("__reader_fn_{id}_{}", &name[1..]))
89 }
90 Form::List(values) => Form::List(
91 values
92 .into_iter()
93 .map(|value| rewrite_anonymous_arguments(value, id))
94 .collect(),
95 ),
96 Form::Vector(values) => Form::Vector(
97 values
98 .into_iter()
99 .map(|value| rewrite_anonymous_arguments(value, id))
100 .collect(),
101 ),
102 Form::Set(values) => Form::Set(
103 values
104 .into_iter()
105 .map(|value| rewrite_anonymous_arguments(value, id))
106 .collect(),
107 ),
108 Form::Map(entries) => Form::Map(
109 entries
110 .into_iter()
111 .map(|(key, value)| {
112 (
113 rewrite_anonymous_arguments(key, id),
114 rewrite_anonymous_arguments(value, id),
115 )
116 })
117 .collect(),
118 ),
119 Form::Metadata(metadata, value) => Form::Metadata(
120 Box::new(rewrite_anonymous_arguments(*metadata, id)),
121 Box::new(rewrite_anonymous_arguments(*value, id)),
122 ),
123 Form::Tagged(tag, value) => {
124 Form::Tagged(tag, Box::new(rewrite_anonymous_arguments(*value, id)))
125 }
126 value => value,
127 }
128}
129
130pub struct Parser<'a> {
131 reader: Reader<'a>,
132 anonymous_function_id: u64,
133}
134impl<'a> Parser<'a> {
135 pub fn new(source: &'a str) -> Self {
136 Self {
137 reader: Reader::new(source),
138 anonymous_function_id: 0,
139 }
140 }
141 fn error<T>(&self, message: impl Into<String>) -> Result<T> {
142 Err(ParseError {
143 message: message.into(),
144 position: self.reader.position(),
145 })
146 }
147 fn whitespace(&mut self) {
148 loop {
149 self.reader.read_while(|ch| ch.is_whitespace() || ch == ',');
150 if self.reader.peek_char() == Some(';') {
151 self.reader.read_until(|ch| ch == '\n');
152 } else {
153 break;
154 }
155 }
156 }
157 fn symbol_token(&mut self, first: char) -> String {
158 let mut token = String::from(first);
159 token.push_str(&self.reader.read_while(|ch| {
160 !ch.is_whitespace()
161 && ch as u32 != 44
162 && !matches!(
163 ch as u32,
164 34 | 59 | 94 | 40 | 41 | 91 | 93 | 123 | 125 | 92 | 64 | 96 | 126
165 )
166 }));
167 token
168 }
169
170 fn number_token(&mut self, first: char) -> String {
171 let mut token = String::from(first);
172 token.push_str(&self.reader.read_while(|ch| {
173 !ch.is_whitespace()
174 && ch as u32 != 44
175 && !matches!(
176 ch as u32,
177 34 | 59 | 94 | 40 | 41 | 91 | 93 | 123 | 125 | 92 | 35 | 39 | 64 | 96 | 126
178 )
179 }));
180 token
181 }
182 fn string(&mut self) -> Result<String> {
183 let mut out = String::new();
184 loop {
185 match self.reader.read_char() {
186 None => return self.error("EOF while reading string"),
187 Some('"') => return Ok(out),
188 Some('\\') => {
189 let escaped = self.reader.read_char().ok_or_else(|| ParseError {
190 message: "EOF while reading string escape".into(),
191 position: self.reader.position(),
192 })?;
193 match escaped {
194 'n' => out.push('\n'),
195 'r' => out.push('\r'),
196 't' => out.push('\t'),
197 'b' => out.push('\u{0008}'),
198 'f' => out.push('\u{000c}'),
199 '\\' => out.push('\\'),
200 '"' => out.push('"'),
201 'u' => {
202 let mut digits = String::new();
203 for _ in 0..4 {
204 let digit = self.reader.read_char().ok_or_else(|| ParseError {
205 message: "EOF in Unicode escape".into(),
206 position: self.reader.position(),
207 })?;
208 if !digit.is_ascii_hexdigit() {
209 return self.error(format!("Invalid digit: {digit}"));
210 }
211 digits.push(digit);
212 }
213 let value = u32::from_str_radix(&digits, 16).expect("validated hex");
214 out.push(char::from_u32(value).ok_or_else(|| ParseError {
215 message: "Invalid Unicode scalar".into(),
216 position: self.reader.position(),
217 })?);
218 }
219 first @ '0'..='7' => {
220 let mut digits = String::from(first);
221 for _ in 0..2 {
222 match self.reader.peek_char() {
223 Some(next @ '0'..='7') => {
224 self.reader.read_char();
225 digits.push(next);
226 }
227 _ => break,
228 }
229 }
230 let value = u32::from_str_radix(&digits, 8).expect("validated octal");
231 out.push(char::from_u32(value).ok_or_else(|| ParseError {
232 message: "Invalid octal scalar".into(),
233 position: self.reader.position(),
234 })?);
235 }
236 other => {
237 return self.error(format!("Unsupported escape character: \\{other}"))
238 }
239 }
240 }
241 Some(ch) => out.push(ch),
242 }
243 }
244 }
245 fn regex(&mut self) -> Result<String> {
246 let mut out = String::new();
247 loop {
248 match self.reader.read_char() {
249 None => return self.error("EOF while reading regex"),
250 Some('"') => return Ok(out),
251 Some('\\') => {
252 out.push('\\');
253 out.push(self.reader.read_char().ok_or_else(|| ParseError {
254 message: "EOF while reading regex".into(),
255 position: self.reader.position(),
256 })?);
257 }
258 Some(ch) => out.push(ch),
259 }
260 }
261 }
262
263 fn metadata(&self, meta: Form, value: Form) -> Result<Form> {
264 let normalized = match meta {
265 Form::Keyword(name) => Form::Map(vec![(Form::Keyword(name), Form::Bool(true))]),
266 tag @ (Form::Symbol(_) | Form::String(_)) => {
267 Form::Map(vec![(Form::Keyword("tag".into()), tag)])
268 }
269 map @ Form::Map(_) => map,
270 _ => return self.error("Metadata must be Symbol, Keyword, String or Map"),
271 };
272
273 if matches!(value, Form::Keyword(_)) {
274 return Ok(value);
275 }
276 if let Form::Metadata(existing, inner) = value {
277 let (Form::Map(mut old), Form::Map(new)) = (*existing, normalized) else {
278 unreachable!("reader metadata is normalized to a map")
279 };
280 for (key, value) in new {
281 if let Some((_, prior)) = old.iter_mut().find(|(candidate, _)| *candidate == key) {
282 *prior = value;
283 } else {
284 old.push((key, value));
285 }
286 }
287 return Ok(Form::Metadata(Box::new(Form::Map(old)), inner));
288 }
289 if !matches!(
290 value,
291 Form::Symbol(_) | Form::List(_) | Form::Vector(_) | Form::Map(_) | Form::Set(_)
292 ) {
293 return self.error("Metadata can only be applied to object forms");
294 }
295 Ok(Form::Metadata(Box::new(normalized), Box::new(value)))
296 }
297 fn delimited(&mut self, close: char, kind: &str) -> Result<Vec<SpannedForm>> {
298 let mut forms = Vec::new();
299 loop {
300 self.whitespace();
301 match self.reader.peek_char() {
302 None => return self.error(format!("EOF while reading {kind}")),
303 Some(ch) if ch == close => {
304 self.reader.read_char();
305 return Ok(forms);
306 }
307 _ => match self.read_one()? {
308 Some(form) => forms.push(form),
309 None => {}
310 },
311 }
312 }
313 }
314 fn prefixed(&mut self, name: &str) -> Result<(Form, Vec<SpannedForm>)> {
315 let value = self.read_required(name)?;
316 let form = Form::List(vec![Form::Symbol(name.into()), value.form.clone()]);
317 Ok((form, vec![value]))
318 }
319
320 fn anonymous_function(&mut self) -> Result<(Form, Vec<SpannedForm>)> {
321 let body = Form::List(
322 self.delimited(')', "anonymous function")?
323 .into_iter()
324 .map(|form| form.form)
325 .collect(),
326 );
327 let mut maximum = 0usize;
328 let mut variadic = false;
329 anonymous_arguments(&body, &mut maximum, &mut variadic).map_err(|message| ParseError {
330 message,
331 position: self.reader.position(),
332 })?;
333 let id = self.anonymous_function_id;
334 self.anonymous_function_id = self.anonymous_function_id.wrapping_add(1);
335 let parameters = (1..=maximum)
336 .map(|index| Form::Symbol(format!("__reader_fn_{id}_{index}")))
337 .chain(
338 variadic
339 .then(|| {
340 [
341 Form::Symbol("&".into()),
342 Form::Symbol(format!("__reader_fn_{id}_rest")),
343 ]
344 })
345 .into_iter()
346 .flatten(),
347 )
348 .collect();
349 Ok((
350 Form::List(vec![
351 Form::Symbol("fn".into()),
352 Form::Vector(parameters),
353 rewrite_anonymous_arguments(body, id),
354 ]),
355 Vec::new(),
356 ))
357 }
358 fn read_required(&mut self, context: &str) -> Result<SpannedForm> {
359 self.whitespace();
360 self.read_one()?.ok_or_else(|| ParseError {
361 message: format!("EOF after {context}"),
362 position: self.reader.position(),
363 })
364 }
365 fn dispatch(&mut self) -> Result<Option<(Form, Vec<SpannedForm>)>> {
366 match self.reader.read_char() {
367 Some('(') => self.anonymous_function().map(Some),
368 Some(ch @ (':' | '=' | '?' | '|')) => {
369 self.error(format!("No dispatch macro for: {ch}"))
370 }
371 Some('{') => {
372 let children = self.delimited('}', "set")?;
373 let forms = children
374 .iter()
375 .map(|child| child.form.clone())
376 .collect::<Vec<_>>();
377 if forms
378 .iter()
379 .enumerate()
380 .any(|(i, value)| forms[..i].contains(value))
381 {
382 return self.error("Duplicate item");
383 }
384 Ok(Some((Form::Set(forms), children)))
385 }
386 Some('_') => {
387 self.read_required("#_")?;
388 Ok(None)
389 }
390 Some('\'') => {
391 let value = self.read_required("var quote")?;
392 if !matches!(value.form, Form::Symbol(_)) {
393 return self.error("Var quote expects a symbol");
394 }
395 let form = Form::List(vec![Form::Symbol("var".into()), value.form.clone()]);
396 Ok(Some((form, vec![value])))
397 }
398 Some('"') => Ok(Some((Form::Regex(self.regex()?), Vec::new()))),
399 Some('<') => self.error("Unreadable form"),
400 Some('^') => {
401 let meta = self.read_required("metadata")?;
402 let value = self.read_required("metadata")?;
403 let form = self.metadata(meta.form.clone(), value.form.clone())?;
404 Ok(Some((form, vec![meta, value])))
405 }
406 Some('#') => {
407 let value = self.read_required("symbolic value")?;
408 match &value.form {
409 Form::Symbol(name) if matches!(name.as_str(), "Inf" | "-Inf" | "NaN") => {
410 self.error("non-finite number")
411 }
412 Form::Symbol(name) => self.error(format!("Unknown symbolic value: ##{name}")),
413 _ => self.error("Invalid symbolic value"),
414 }
415 }
416
417 Some(ch) => {
418 if !ch.is_alphabetic() {
419 return self.error(format!("No dispatch macro for: {ch}"));
420 }
421 let tag = self.symbol_token(ch);
422 if tag.is_empty() {
423 return self.error(format!("No dispatch macro for: {ch}"));
424 }
425 let value = self.read_required("tagged literal")?;
426 let form = Form::Tagged(tag, Box::new(value.form.clone()));
427 Ok(Some((form, vec![value])))
428 }
429 None => self.error("EOF while reading hash dispatch"),
430 }
431 }
432 fn atom(&self, token: String) -> Result<Form> {
433 match token.as_str() {
434 "nil" => return Ok(Form::Nil),
435 "true" => return Ok(Form::Bool(true)),
436 "false" => return Ok(Form::Bool(false)),
437 _ => {}
438 }
439 if let Some(keyword) = token.strip_prefix(':') {
440 let slashes = keyword.bytes().filter(|byte| *byte == b'/').count();
441 let error = if keyword.is_empty() {
442 Some("Keyword name cannot be empty.")
443 } else if keyword == "/" {
444 Some("Keyword name cannot be a single slash.")
445 } else if slashes > 1 {
446 Some("Keyword name can only contain one slash.")
447 } else if keyword.starts_with('/') {
448 Some("Keyword name cannot start with a slash.")
449 } else if keyword.ends_with('/') {
450 Some("Keyword name cannot end with a slash.")
451 } else {
452 None
453 };
454 if let Some(error) = error {
455 return self.error(error);
456 }
457 return Ok(Form::Keyword(keyword.into()));
458 }
459 let body = token.strip_prefix(['+', '-']).unwrap_or(&token);
460 if body.contains('/')
461 && body.split_once('/').is_some_and(|(n, d)| {
462 !n.is_empty()
463 && !d.is_empty()
464 && n.chars().all(|ch| ch.is_ascii_digit())
465 && d.chars().all(|ch| ch.is_ascii_digit())
466 })
467 {
468 return self.error("Ratios are not supported");
469 }
470 let numeric = body.chars().next().is_some_and(|ch| ch.is_ascii_digit());
471 if numeric {
472 use crate::numeric::{parse_integer_digits, CanonicalInteger};
473
474 if token.ends_with(['N', 'M']) {
475 return self.error(format!(
476 "Legacy numeric suffixes N and M are not supported: {token}"
477 ));
478 }
479 let negative = token.starts_with('-');
480 let integer_form = |integer: CanonicalInteger| match integer {
481 CanonicalInteger::Small(value) => Form::Number(value),
482 CanonicalInteger::Big(value) => Form::BigInteger(value),
483 };
484 if body.contains(['.', 'e', 'E']) {
485 let float = token.parse::<f64>().map_err(|_| ParseError {
486 message: format!("Invalid number: {token}"),
487 position: self.reader.position(),
488 })?;
489 if !float.is_finite() {
490 return self.error("non-finite number");
491 }
492 return Ok(Form::Float(float));
493 }
494 let parsed = if let Some(hex) =
495 body.strip_prefix("0x").or_else(|| body.strip_prefix("0X"))
496 {
497 parse_integer_digits(hex, 16, negative)
498 } else if let Some((radix_text, digits)) = body.split_once(['r', 'R']) {
499 let radix = radix_text.parse::<u32>().map_err(|_| ParseError {
500 message: format!("Invalid number: {token}"),
501 position: self.reader.position(),
502 })?;
503 if !(2..=36).contains(&radix) {
504 return self.error(format!("Radix out of range: {radix}"));
505 }
506 if digits.is_empty() {
507 return self.error(format!("Invalid number: {token}"));
508 }
509 if let Some(digit) = digits.chars().find(|digit| digit.to_digit(radix).is_none()) {
510 return self.error(format!("Invalid digit {digit} under radix {radix}"));
511 }
512 parse_integer_digits(digits, radix, negative)
513 } else if body.len() > 1
514 && body.starts_with('0')
515 && body.chars().all(|ch| ch.is_ascii_digit())
516 {
517 if body.chars().any(|ch| !('0'..='7').contains(&ch)) {
518 None
519 } else {
520 parse_integer_digits(body, 8, negative)
521 }
522 } else if body.chars().all(|ch| ch.is_ascii_digit()) {
523 parse_integer_digits(body, 10, negative)
524 } else {
525 None
526 };
527 return parsed.map(integer_form).ok_or_else(|| ParseError {
528 message: format!("Invalid number: {token}"),
529 position: self.reader.position(),
530 });
531 }
532 Ok(Form::Symbol(token))
533 }
534 fn read_one(&mut self) -> Result<Option<SpannedForm>> {
535 self.whitespace();
536 if self.reader.is_eof() {
537 return Ok(None);
538 }
539 let start = self.reader.position();
540 let ch = self.reader.read_char().expect("checked EOF");
541 let form = match ch {
542 '(' => {
543 let children = self.delimited(')', "list")?;
544 let forms = children.iter().map(|child| child.form.clone()).collect();
545 Some((Form::List(forms), children))
546 }
547 '[' => {
548 let children = self.delimited(']', "vector")?;
549 let forms = children.iter().map(|child| child.form.clone()).collect();
550 Some((Form::Vector(forms), children))
551 }
552 '{' => {
553 let children = self.delimited('}', "map")?;
554 if children.len() % 2 != 0 {
555 return self.error("Map literal requires an even number of forms");
556 }
557 {
558 let entries = children
559 .chunks(2)
560 .map(|pair| (pair[0].form.clone(), pair[1].form.clone()))
561 .collect::<Vec<_>>();
562 if entries
563 .iter()
564 .enumerate()
565 .any(|(i, (key, _))| entries[..i].iter().any(|(prior, _)| prior == key))
566 {
567 return self.error("Duplicate key");
568 }
569 Some((Form::Map(entries), children))
570 }
571 }
572 ')' | ']' | '}' => return self.error(format!("Unmatched delimiter: {ch}")),
573 '"' => Some((Form::String(self.string()?), Vec::new())),
574 '\'' => Some(self.prefixed("quote")?),
575 '@' => Some(self.prefixed("deref")?),
576 '`' => Some(self.prefixed("syntax-quote")?),
577 '~' => {
578 if self.reader.peek_char() == Some('@') {
579 self.reader.read_char();
580 Some(self.prefixed("unquote-splicing")?)
581 } else {
582 Some(self.prefixed("unquote")?)
583 }
584 }
585 '^' => {
586 let meta = self.read_required("metadata")?;
587 let value = self.read_required("metadata")?;
588 let form = self.metadata(meta.form.clone(), value.form.clone())?;
589 Some((form, vec![meta, value]))
590 }
591 '\\' => {
592 let token = if self
593 .reader
594 .peek_char()
595 .is_some_and(|c| "()[]{}".contains(c))
596 {
597 self.reader
598 .read_char()
599 .map(|value| value.to_string())
600 .unwrap_or_default()
601 } else {
602 self.reader
603 .read_while(|c| !c.is_whitespace() && !"()[]{}".contains(c))
604 };
605 if let Some(digit) = token
606 .strip_prefix('u')
607 .filter(|digits| digits.len() == 4)
608 .and_then(|digits| digits.chars().find(|ch| !ch.is_ascii_hexdigit()))
609 {
610 return self.error(format!("Invalid digit: {digit}"));
611 }
612 if let Some(digit) = token
613 .strip_prefix('o')
614 .filter(|digits| (1..=3).contains(&digits.len()))
615 .and_then(|digits| digits.chars().find(|ch| !(('0'..='7').contains(ch))))
616 {
617 return self.error(format!("Invalid digit: {digit}"));
618 }
619 let value = match token.as_str() {
620 "newline" => Some('\n'),
621 "space" => Some(' '),
622 "tab" => Some('\t'),
623 "backspace" => Some('\u{0008}'),
624 "formfeed" => Some('\u{000c}'),
625 "return" => Some('\r'),
626 _ if token.starts_with('u') && token.len() == 5 => {
627 u32::from_str_radix(&token[1..], 16)
628 .ok()
629 .and_then(char::from_u32)
630 }
631 _ if token.starts_with('o') && (2..=4).contains(&token.len()) => {
632 u32::from_str_radix(&token[1..], 8)
633 .ok()
634 .and_then(char::from_u32)
635 }
636 _ if token.chars().count() == 1 => token.chars().next(),
637 _ => None,
638 };
639 Some((
640 Form::Character(value.ok_or_else(|| ParseError {
641 message: format!("Invalid character: \\{token}"),
642 position: self.reader.position(),
643 })?),
644 Vec::new(),
645 ))
646 }
647 '#' => self.dispatch()?,
648 other => {
649 let numeric = other.is_ascii_digit()
650 || ((other == '+' || other == '-')
651 && self
652 .reader
653 .peek_char()
654 .is_some_and(|ch| ch.is_ascii_digit()));
655 let token = if numeric {
656 self.number_token(other)
657 } else {
658 self.symbol_token(other)
659 };
660 Some((self.atom(token)?, Vec::new()))
661 }
662 };
663 Ok(form.map(|(form, children)| SpannedForm {
664 form,
665 span: Span {
666 start,
667 end: self.reader.position(),
668 },
669 children,
670 }))
671 }
672 pub fn read_all(mut self) -> Result<Vec<SpannedForm>> {
673 let mut forms = Vec::new();
674 loop {
675 self.whitespace();
676 if self.reader.is_eof() {
677 break;
678 }
679 if let Some(form) = self.read_one()? {
680 forms.push(form);
681 }
682 }
683 if forms.is_empty() {
684 return self.error("source contains no forms");
685 }
686 Ok(forms)
687 }
688}
689pub fn read_forms(source: &str) -> Result<Vec<SpannedForm>> {
690 Parser::new(source).read_all()
691}
692pub fn parse_forms(source: &str) -> std::result::Result<Vec<Form>, String> {
693 read_forms(source)
694 .map(|forms| forms.into_iter().map(|f| f.form).collect())
695 .map_err(|e| e.to_string())
696}
697pub fn parse(source: &str) -> std::result::Result<Form, String> {
698 let mut forms = parse_forms(source)?;
699 if forms.len() != 1 {
700 return Err("source contains multiple forms; use eval_text".into());
701 }
702 Ok(forms.remove(0))
703}
704
705#[cfg(test)]
706#[path = "parser_tests.rs"]
707mod tests;