Witch of Git - ess/blob - src/parser.rs

   1 //! Functions to parse s-expressions and expression atoms.
   2 //!
   3 //! This module contains the core parsing machinery.
   4 //!
   5 //! * If you're interested in getting a parsed s-expression that you can use,
   6 //!   then looking at [`parse`] and [`parse_one`] are your best bet.
   7 //! * If you want to write your own parsers that contain s-expressions,
   8 //!   [`ParseResult`] and [`parse_expression`] will be the most useful to you.
   9 //!
  10 //! [`parse`]: fn.parse.html
  11 //! [`parse_one`]: fn.parse_one.html
  12 //! [`ParseResult`]: enum.ParseResult.html
  13 //! [`parse_expression`]: fn.parse_expression.html
  14
  15 use sexp::Sexp;
  16 use span::{ByteSpan, Span};
  17 use std::borrow::Cow;
  18
  19 // Parsing Types ///////////////////////////////////////////////////////////////
  20
  21 /// Represents what to do next in partially completed parsing.
  22 ///
  23 /// `ParseResult` is returned from all intermediate parsers. If you just want to
  24 /// get back parsed s-expressions, you won't need to worry about this type since
  25 /// the top level parsers just return a `Result`.
  26 ///
  27 /// If the parser failed to produce a result, it will return `Error`, and if it
  28 /// succeeded we'll get the `Done` variant containing the value produced and the
  29 /// rest of the text to work on.
  30 #[derive(Debug, PartialEq, Eq, Clone)]
  31 pub enum ParseResult<'a, T, E> {
  32     /// The parser succeeded, this contains first the un-consumed portion of the
  33     /// input then the result produced by parsing.
  34     Done(&'a str, T),
  35     /// The parser failed, the `E` represents the reason for the failure.
  36     Error(E),
  37 }
  38
  39 /// Indicates how parsing failed.
  40 ///
  41 /// Most `ParseError` variants contain a `Box<ParseError>` that represents the
  42 /// cause of that error. Using this, `ParseError` variants can be chained to
  43 /// produce a more complete picture of what exactly went wrong during parsing.
  44 #[derive(Debug, PartialEq, Eq, Clone)]
  45 pub enum ParseError<Loc = ByteSpan>
  46 where
  47     Loc: Span,
  48 {
  49     /// Parsing reached the end of input where not expecting to, usually this
  50     /// will be contained inside another `ParseError` like `String(box
  51     /// UnexpectedEof, ...)` which indicates that the closing quote was never
  52     /// found.
  53     UnexpectedEof,
  54     /// Some problem occurred while parsing a list, along with the cause of that
  55     /// error.
  56     List(Box<ParseError>, Loc),
  57     /// Some problem occurred while parsing an s-expression. This will only be
  58     /// generated if EOF is reached unexpectedly at the beginning of
  59     /// `parse_expression`, so it should probably be removed.
  60     Sexp(Box<ParseError>, Loc),
  61     /// Some problem occurred while parsing a character literal, along with the
  62     /// cause of the error.
  63     Char(Box<ParseError>, Loc),
  64     /// Some problem occurred while parsing a string literal, along with the
  65     /// cause of the error.
  66     String(Box<ParseError>, Loc),
  67     /// Some problem occurred while parsing a symbol, along with the cause of
  68     /// the error.
  69     Symbol(Box<ParseError>, Loc),
  70     /// Some problem occurred while parsing a number literal, along with the
  71     /// cause of the error.
  72     Number(Box<ParseError>, Loc),
  73     /// An unexpected character was found. This will usually be the root cause
  74     /// in some chain of `ParseError`s.
  75     Unexpected(char, Loc::Begin),
  76 }
  77 use self::ParseResult::*;
  78
  79 // Parsing Utilities ///////////////////////////////////////////////////////////
  80
  81 trait IsDelimeter {
  82     fn is_delimiter(&self) -> bool;
  83 }
  84
  85 impl IsDelimeter for char {
  86     fn is_delimiter(&self) -> bool {
  87         let delim_chars = r#";()[]{}"\`,"#;
  88         self.is_whitespace() || delim_chars.contains(*self)
  89     }
  90 }
  91
  92 fn consume_whitespace<'a>(input: &'a str, start_loc: usize) -> (&'a str, usize) {
  93     let mut buffer = input;
  94     let mut loc = start_loc;
  95     while !buffer.is_empty() && (buffer.starts_with(char::is_whitespace) || buffer.starts_with(';'))
  96     {
  97         if let Some(pos) = buffer.find(|c: char| !c.is_whitespace()) {
  98             buffer = &buffer[pos..];
  99             loc += pos;
 100         } else {
 101             buffer = &buffer[buffer.len()..];
 102             loc += buffer.len();
 103         }
 104
 105         if buffer.starts_with(';') {
 106             if let Some(pos) = buffer.find('\n') {
 107                 buffer = &buffer[pos + 1..];
 108                 loc += pos + 1;
 109             } else {
 110                 buffer = &buffer[buffer.len()..];
 111                 loc += buffer.len();
 112             }
 113         }
 114     }
 115     (&buffer, loc)
 116 }
 117
 118 macro_rules! consume_whitespace {
 119     ($input:expr, $start_loc:expr, $ErrorFn:expr) => {{
 120         let (text, loc) = consume_whitespace($input, $start_loc);
 121         if text.is_empty() {
 122             return Error($ErrorFn(Box::new(ParseError::UnexpectedEof), (loc, loc)));
 123         } else {
 124             (text, loc)
 125         }
 126     }};
 127 }
 128
 129 // Top Level Parsers ///////////////////////////////////////////////////////////
 130
 131 /// Parse a sequence of s-expressions.
 132 ///
 133 /// This function returns `(Vec<Sexp>, Option<ParseError>)` so that it can
 134 /// return partial results, for when some component parses successfully and a
 135 /// later part fails.
 136 ///
 137 /// # Errors
 138 ///
 139 /// If the text contains an invalid s-expression (imbalanced parenthesis,
 140 /// quotes, invalid numbers like 123q, etc.) then the parser will stop and
 141 /// return an error. Every s-expression before that point that successfully
 142 /// parsed will still be returned.
 143 ///
 144 /// # Examples
 145 ///
 146 /// We can get useful partial results
 147 ///
 148 /// ```rust
 149 /// # use ess::parser::parse;
 150 /// let (exprs, err) = parse("1 2 3 ( 4");
 151 /// assert_eq!(exprs.len(), 3);
 152 /// assert!(err.is_some());
 153 /// ```
 154 pub fn parse(mut input: &str) -> (Vec<Sexp>, Option<ParseError>) {
 155     let mut start_loc = 0;
 156     let mut results = Vec::new();
 157     loop {
 158         match parse_expression(input, start_loc) {
 159             Done(rest, result) => {
 160                 let (rest, loc) = consume_whitespace(rest, result.get_loc().1);
 161                 input = rest;
 162                 start_loc = loc;
 163                 results.push(result);
 164                 if rest.trim() == "" {
 165                     return (results, None);
 166                 }
 167             }
 168             Error(err) => {
 169                 return (results, Some(err));
 170             }
 171         }
 172     }
 173 }
 174
 175 /// Parses a single s-expression, ignoring any trailing text.
 176 ///
 177 /// This function returns a pair of the parsed s-expression and the tail of the text.
 178 ///
 179 /// # Errors
 180 ///
 181 /// If the text begins with an invalid s-expression (imbalanced parenthesis,
 182 /// quotes, invalid numbers like 123q, etc.) then the parser will return an
 183 /// error. Any text after the first s-expression doesn't affect the parsing.
 184
 185 ///
 186 /// # Examples
 187 ///
 188 /// ```rust
 189 /// # use ess::parser::parse_one;
 190 /// let (expr, rest) = parse_one("1 (").unwrap();
 191 /// assert_eq!(rest, " (");
 192 /// ```
 193 pub fn parse_one(input: &str) -> Result<(Sexp, &str), ParseError> {
 194     match parse_expression(input, 0) {
 195         Done(rest, result) => Ok((result, rest)),
 196         Error(err) => Err(err),
 197     }
 198 }
 199
 200 // Core Parsers ////////////////////////////////////////////////////////////////
 201
 202 // TODO: All of these parsers deserve docs, but since they're somewhat internal
 203 // parsers, it's less critical than the rest of the API.
 204
 205 #[allow(missing_docs)]
 206 pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 207     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Sexp);
 208
 209     match input.chars().next() {
 210         Some('0'..='9') => parse_number(input, start_loc),
 211         Some('(') | Some('{') | Some('[') => parse_list(input, start_loc),
 212         Some('#') => parse_character(input, start_loc),
 213         Some('"') => parse_string(input, start_loc),
 214         Some('\'') => match parse_expression(&input[1..], start_loc + 1) {
 215             Done(rest, result) => {
 216                 let span = *result.get_loc();
 217                 let quote_span = (0, 1).offset(start_loc);
 218                 Done(
 219                     rest,
 220                     Sexp::List(
 221                         Cow::from(vec![Sexp::Sym("quote".into(), quote_span), result]),
 222                         quote_span.union(&span),
 223                     ),
 224                 )
 225             }
 226             err => err,
 227         },
 228         Some('`') => match parse_expression(&input[1..], start_loc + 1) {
 229             Done(rest, result) => {
 230                 let span = *result.get_loc();
 231                 let quote_span = (0, 1).offset(start_loc);
 232                 Done(
 233                     rest,
 234                     Sexp::List(
 235                         Cow::from(vec![Sexp::Sym("quasiquote".into(), quote_span), result]),
 236                         quote_span.union(&span),
 237                     ),
 238                 )
 239             }
 240             err => err,
 241         },
 242         Some(',') => {
 243             if input[1..].starts_with('@') {
 244                 match parse_expression(&input[2..], start_loc + 2) {
 245                     Done(rest, result) => {
 246                         let span = *result.get_loc();
 247                         let quote_span = (0, 2).offset(start_loc);
 248                         Done(
 249                             rest,
 250                             Sexp::List(
 251                                 Cow::from(vec![Sexp::Sym("unquote-splicing".into(), quote_span), result]),
 252                                 quote_span.union(&span),
 253                             ),
 254                         )
 255                     }
 256                     err => err,
 257                 }
 258             } else {
 259                 match parse_expression(&input[1..], start_loc + 1) {
 260                     Done(rest, result) => {
 261                         let span = *result.get_loc();
 262                         let quote_span = (0, 1).offset(start_loc);
 263                         Done(
 264                             rest,
 265                             Sexp::List(
 266                                 Cow::from(vec![Sexp::Sym("unquote".into(), quote_span), result]),
 267                                 quote_span.union(&span),
 268                             ),
 269                         )
 270                     }
 271                     err => err,
 272                 }
 273             }
 274         }
 275         Some(_) => parse_symbol(input, start_loc),
 276         None => unreachable!(),
 277     }
 278 }
 279
 280 #[allow(missing_docs)]
 281 pub fn parse_list(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 282     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::List);
 283
 284     let first_char = match input.chars().nth(0) {
 285         Some(c @ '(') | Some(c @ '{') | Some(c @ '[') => c,
 286         Some(c) => {
 287             return Error(ParseError::List(
 288                 Box::new(ParseError::Unexpected(c, 0)),
 289                 (0, 0).offset(start_loc),
 290             ))
 291         }
 292         None => unreachable!(),
 293     };
 294
 295     let mut input = &input[1..];
 296     let mut loc = start_loc + 1;
 297     let mut members = Vec::new();
 298     loop {
 299         {
 300             let (new_input, new_loc) = consume_whitespace!(input, loc, ParseError::List);
 301             input = new_input;
 302             loc = new_loc;
 303         }
 304
 305         match input.chars().nth(0) {
 306             Some(c @ ')') | Some(c @ '}') | Some(c @ ']') => match (first_char, c) {
 307                 ('(', ')') | ('{', '}') | ('[', ']') => {
 308                     return Done(&input[1..], Sexp::List(Cow::from(members), (start_loc, loc + 1)))
 309                 }
 310                 _ => {
 311                     return Error(ParseError::List(
 312                         Box::new(ParseError::Unexpected(c, loc)),
 313                         (start_loc, loc),
 314                     ))
 315                 }
 316             },
 317             Some(_) => (),
 318             None => unreachable!(),
 319         }
 320
 321         match parse_expression(input, loc) {
 322             Done(new_input, member) => {
 323                 loc = member.get_loc().1;
 324                 members.push(member);
 325                 input = new_input;
 326             }
 327             Error(err) => return Error(ParseError::List(Box::new(err), (0, 0).offset(loc))),
 328         }
 329     }
 330 }
 331
 332 #[allow(missing_docs)]
 333 pub fn parse_number(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 334     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Number);
 335
 336     match input.chars().next() {
 337         Some(c) if !c.is_digit(10) => {
 338             return Error(ParseError::Number(
 339                 Box::new(ParseError::Unexpected(c, start_loc)),
 340                 (0, c.len_utf8()).offset(start_loc),
 341             ));
 342         }
 343         None => {
 344             return Error(ParseError::Number(
 345                 Box::new(ParseError::UnexpectedEof),
 346                 (0, 0).offset(start_loc),
 347             ))
 348         }
 349         _ => (),
 350     }
 351
 352     let base = 10;
 353
 354     let mut end = 0;
 355     // Before the decimal point
 356     for (i, c) in input.char_indices() {
 357         if c == '.' {
 358             end = i + 1;
 359             break;
 360         }
 361
 362         if c.is_delimiter() {
 363             return Done(
 364                 &input[i..],
 365                 Sexp::Int(
 366                     input[..i].parse().expect("Already matched digits"),
 367                     (0, i).offset(start_loc),
 368                 ),
 369             );
 370         }
 371
 372         if !c.is_digit(base) {
 373             return Error(ParseError::Number(
 374                 Box::new(ParseError::Unexpected(c, start_loc + i)),
 375                 (i, i).offset(start_loc),
 376             ));
 377         }
 378
 379         end = i + c.len_utf8();
 380     }
 381
 382     if input[end..].is_empty() {
 383         return Done(
 384             &input[end..],
 385             Sexp::Int(
 386                 input.parse().expect("Already matched digits"),
 387                 (0, end).offset(start_loc),
 388             ),
 389         );
 390     }
 391
 392     // After the decimal point
 393     for (i, c) in input[end..].char_indices() {
 394         if c.is_delimiter() {
 395             return Done(
 396                 &input[i + end..],
 397                 Sexp::Float(
 398                     input[..end + i]
 399                         .parse()
 400                         .expect("Already matched digits.digits"),
 401                     (0, end + i).offset(start_loc),
 402                 ),
 403             );
 404         }
 405
 406         if !c.is_digit(base) {
 407             return Error(ParseError::Number(
 408                 Box::new(ParseError::Unexpected(c, start_loc + i + end)),
 409                 (i + end, i + end).offset(start_loc),
 410             ));
 411         }
 412     }
 413
 414     Done(
 415         &input[input.len()..],
 416         Sexp::Float(
 417             input.parse().expect("Already matched digits.digits"),
 418             (0, input.len()).offset(start_loc),
 419         ),
 420     )
 421 }
 422
 423 #[allow(missing_docs)]
 424 pub fn parse_symbol(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 425     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Symbol);
 426
 427     match input.chars().next() {
 428         Some(c @ '#') | Some(c @ ':') | Some(c @ '0'..='9') => {
 429             return Error(ParseError::Symbol(
 430                 Box::new(ParseError::Unexpected(c, start_loc)),
 431                 (0, 0).offset(start_loc),
 432             ))
 433         }
 434         Some(c) if c.is_delimiter() => {
 435             return Error(ParseError::Symbol(
 436                 Box::new(ParseError::Unexpected(c, start_loc)),
 437                 (0, 0).offset(start_loc),
 438             ))
 439         }
 440         Some(_) => (),
 441         None => unreachable!(),
 442     }
 443
 444     for (i, c) in input.char_indices() {
 445         if c.is_delimiter() {
 446             return Done(
 447                 &input[i..],
 448                 Sexp::Sym(input[..i].into(), (0, i).offset(start_loc)),
 449             );
 450         }
 451     }
 452
 453     Done(
 454         &input[input.len()..],
 455         Sexp::Sym(input.into(), (0, input.len()).offset(start_loc)),
 456     )
 457 }
 458
 459 #[allow(missing_docs)]
 460 pub fn parse_string(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 461     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::String);
 462
 463     match input.chars().next() {
 464         Some('"') => (),
 465         Some(c) => {
 466             return Error(ParseError::String(
 467                 Box::new(ParseError::Unexpected(c, start_loc)),
 468                 (0, 0).offset(start_loc),
 469             ))
 470         }
 471         None => unreachable!(),
 472     }
 473
 474     for (i, c) in input[1..].char_indices() {
 475         if c == '"' {
 476             return Done(
 477                 &input[2 + i..],
 478                 Sexp::Str(input[1..=i].into(), (0, i + 2).offset(start_loc)),
 479             );
 480         }
 481     }
 482
 483     Error(ParseError::String(
 484         Box::new(ParseError::UnexpectedEof),
 485         (0, input.len()).offset(start_loc),
 486     ))
 487 }
 488
 489 #[allow(missing_docs)]
 490 pub fn parse_character(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 491     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Char);
 492
 493     match input.chars().nth(0) {
 494         Some('#') => (),
 495         Some(c) => {
 496             return Error(ParseError::Char(
 497                 Box::new(ParseError::Unexpected(c, start_loc)),
 498                 (0, 0).offset(start_loc),
 499             ))
 500         }
 501         None => {
 502             return Error(ParseError::Char(
 503                 Box::new(ParseError::UnexpectedEof),
 504                 (0, 0).offset(start_loc),
 505             ))
 506         }
 507     }
 508
 509     match input.chars().nth(1) {
 510         Some('\\') => (),
 511         Some(c) => {
 512             return Error(ParseError::Char(
 513                 Box::new(ParseError::Unexpected(c, start_loc + 1)),
 514                 (1, 1).offset(start_loc),
 515             ))
 516         }
 517         None => {
 518             return Error(ParseError::Char(
 519                 Box::new(ParseError::UnexpectedEof),
 520                 (1, 1).offset(start_loc),
 521             ))
 522         }
 523     }
 524
 525     match input.chars().nth(2) {
 526         Some(c) => Done(&input[3..], Sexp::Char(c, (0, 3).offset(start_loc))),
 527         None => Error(ParseError::Char(
 528             Box::new(ParseError::UnexpectedEof),
 529             (2, 2).offset(start_loc),
 530         )),
 531     }
 532 }
 533
 534 // Tests ///////////////////////////////////////////////////////////////////////
 535
 536 #[cfg(test)]
 537 mod test {
 538     use parser::*;
 539     use sexp::Sexp;
 540     use span::Span;
 541
 542     #[test]
 543     fn test_parse() {
 544         assert_eq!(
 545             parse("1 2 3"),
 546             (
 547                 vec![
 548                     Sexp::Int(1, (0, 1)),
 549                     Sexp::Int(2, (2, 3)),
 550                     Sexp::Int(3, (4, 5))
 551                 ],
 552                 None
 553             )
 554         );
 555         assert_eq!(
 556             parse("1 2 )"),
 557             (
 558                 vec![Sexp::Int(1, (0, 1)), Sexp::Int(2, (2, 3))],
 559                 Some(ParseError::Symbol(
 560                     Box::new(ParseError::Unexpected(')', 4)),
 561                     (4, 4)
 562                 ))
 563             )
 564         );
 565     }
 566
 567     #[test]
 568     fn test_parse_one() {
 569         assert_eq!(parse_one("1 2"), Ok((Sexp::Int(1, (0, 1)), " 2")));
 570     }
 571
 572     #[test]
 573     fn test_parse_expression() {
 574         assert_eq!(parse_expression("   1", 0), Done("", Sexp::Int(1, (1, 2))));
 575         assert_eq!(
 576             parse_expression("2.2", 0),
 577             Done("", Sexp::Float(2.2, (0, 3)))
 578         );
 579         assert_eq!(
 580             parse_expression(" a", 0),
 581             Done("", Sexp::Sym("a".into(), (1, 2)))
 582         );
 583         assert_eq!(
 584             parse_expression("#\\c", 0),
 585             Done("", Sexp::Char('c', (0, 3)))
 586         );
 587         assert_eq!(
 588             parse_expression(r#""hi""#, 0),
 589             Done("", Sexp::Str("hi".into(), (0, 4)))
 590         );
 591         assert_eq!(
 592             parse_expression("()", 0),
 593             Done("", Sexp::List(vec![], (0, 2)))
 594         );
 595         assert_eq!(
 596             parse_expression("( 1 2 3 )", 0),
 597             Done(
 598                 "",
 599                 Sexp::List(
 600                     vec![
 601                         Sexp::Int(1, (2, 3)),
 602                         Sexp::Int(2, (4, 5)),
 603                         Sexp::Int(3, (6, 7)),
 604                     ],
 605                     (0, 9)
 606                 )
 607             )
 608         );
 609
 610         assert_eq!(
 611             parse_expression("", 0),
 612             Error(ParseError::Sexp(
 613                 Box::new(ParseError::UnexpectedEof),
 614                 (0, 0)
 615             ))
 616         );
 617     }
 618
 619     #[test]
 620     fn test_parse_expr_quote() {
 621         assert_eq!(
 622             parse_expression("'a", 0),
 623             Done(
 624                 "",
 625                 Sexp::List(
 626                     vec![
 627                         Sexp::Sym("quote".into(), (0, 1)),
 628                         Sexp::Sym("a".into(), (1, 2)),
 629                     ],
 630                     (0, 2)
 631                 )
 632             )
 633         );
 634         assert_eq!(
 635             parse_expression("'1", 0),
 636             Done(
 637                 "",
 638                 Sexp::List(
 639                     vec![Sexp::Sym("quote".into(), (0, 1)), Sexp::Int(1, (1, 2)),],
 640                     (0, 2)
 641                 )
 642             )
 643         );
 644         assert_eq!(
 645             parse_expression("' (1 2 3)", 0),
 646             Done(
 647                 "",
 648                 Sexp::List(
 649                     vec![
 650                         Sexp::Sym("quote".into(), (0, 1)),
 651                         Sexp::List(
 652                             vec![
 653                                 Sexp::Int(1, (3, 4)),
 654                                 Sexp::Int(2, (5, 6)),
 655                                 Sexp::Int(3, (7, 8)),
 656                             ],
 657                             (2, 9)
 658                         ),
 659                     ],
 660                     (0, 9)
 661                 )
 662             )
 663         );
 664
 665         assert_eq!(
 666             parse_expression("'", 0),
 667             Error(ParseError::Sexp(
 668                 Box::new(ParseError::UnexpectedEof),
 669                 (1, 1)
 670             ))
 671         );
 672         assert_eq!(
 673             parse_expression("`'", 0),
 674             Error(ParseError::Sexp(
 675                 Box::new(ParseError::UnexpectedEof),
 676                 (2, 2)
 677             ))
 678         );
 679     }
 680
 681     #[test]
 682     fn test_parse_expr_quasiquote() {
 683         assert_eq!(
 684             parse_expression("`a", 0),
 685             Done(
 686                 "",
 687                 Sexp::List(
 688                     vec![
 689                         Sexp::Sym("quasiquote".into(), (0, 1)),
 690                         Sexp::Sym("a".into(), (1, 2)),
 691                     ],
 692                     (0, 2)
 693                 )
 694             )
 695         );
 696         assert_eq!(
 697             parse_expression("`1", 0),
 698             Done(
 699                 "",
 700                 Sexp::List(
 701                     vec![Sexp::Sym("quasiquote".into(), (0, 1)), Sexp::Int(1, (1, 2)),],
 702                     (0, 2)
 703                 )
 704             )
 705         );
 706         assert_eq!(
 707             parse_expression("` (1 2 3)", 0),
 708             Done(
 709                 "",
 710                 Sexp::List(
 711                     vec![
 712                         Sexp::Sym("quasiquote".into(), (0, 1)),
 713                         Sexp::List(
 714                             vec![
 715                                 Sexp::Int(1, (3, 4)),
 716                                 Sexp::Int(2, (5, 6)),
 717                                 Sexp::Int(3, (7, 8)),
 718                             ],
 719                             (2, 9)
 720                         ),
 721                     ],
 722                     (0, 9)
 723                 )
 724             )
 725         );
 726         assert_eq!(
 727             parse_expression("`'a", 0),
 728             Done(
 729                 "",
 730                 Sexp::List(
 731                     vec![
 732                         Sexp::Sym("quasiquote".into(), (0, 1)),
 733                         Sexp::List(
 734                             vec![
 735                                 Sexp::Sym("quote".into(), (1, 2)),
 736                                 Sexp::Sym("a".into(), (2, 3)),
 737                             ],
 738                             (1, 3)
 739                         ),
 740                     ],
 741                     (0, 3)
 742                 )
 743             )
 744         );
 745
 746         assert_eq!(
 747             parse_expression("`", 0),
 748             Error(ParseError::Sexp(
 749                 Box::new(ParseError::UnexpectedEof),
 750                 (1, 1)
 751             ))
 752         );
 753     }
 754
 755     #[test]
 756     fn test_parse_expr_unquote() {
 757         assert_eq!(
 758             parse_expression(",a", 0),
 759             Done(
 760                 "",
 761                 Sexp::List(
 762                     vec![
 763                         Sexp::Sym("unquote".into(), (0, 1)),
 764                         Sexp::Sym("a".into(), (1, 2)),
 765                     ],
 766                     (0, 2)
 767                 )
 768             )
 769         );
 770         assert_eq!(
 771             parse_expression(",1", 0),
 772             Done(
 773                 "",
 774                 Sexp::List(
 775                     vec![Sexp::Sym("unquote".into(), (0, 1)), Sexp::Int(1, (1, 2)),],
 776                     (0, 2)
 777                 )
 778             )
 779         );
 780         assert_eq!(
 781             parse_expression(", (1 2 3)", 0),
 782             Done(
 783                 "",
 784                 Sexp::List(
 785                     vec![
 786                         Sexp::Sym("unquote".into(), (0, 1)),
 787                         Sexp::List(
 788                             vec![
 789                                 Sexp::Int(1, (3, 4)),
 790                                 Sexp::Int(2, (5, 6)),
 791                                 Sexp::Int(3, (7, 8)),
 792                             ],
 793                             (2, 9)
 794                         ),
 795                     ],
 796                     (0, 9)
 797                 )
 798             )
 799         );
 800         assert_eq!(
 801             parse_expression("`,a", 0),
 802             Done(
 803                 "",
 804                 Sexp::List(
 805                     vec![
 806                         Sexp::Sym("quasiquote".into(), (0, 1)),
 807                         Sexp::List(
 808                             vec![
 809                                 Sexp::Sym("unquote".into(), (1, 2)),
 810                                 Sexp::Sym("a".into(), (2, 3)),
 811                             ],
 812                             (1, 3)
 813                         ),
 814                     ],
 815                     (0, 3)
 816                 )
 817             )
 818         );
 819         assert_eq!(
 820             parse_expression("`(,@a)", 0),
 821             Done(
 822                 "",
 823                 Sexp::List(
 824                     vec![
 825                         Sexp::Sym("quasiquote".into(), (0, 1)),
 826                         Sexp::List(
 827                             vec![Sexp::List(
 828                                 vec![
 829                                     Sexp::Sym("unquote-splicing".into(), (2, 4)),
 830                                     Sexp::Sym("a".into(), (4, 5)),
 831                                 ],
 832                                 (2, 5)
 833                             ),],
 834                             (1, 6)
 835                         ),
 836                     ],
 837                     (0, 6)
 838                 )
 839             )
 840         );
 841
 842         assert_eq!(
 843             parse_expression(",", 0),
 844             Error(ParseError::Sexp(
 845                 Box::new(ParseError::UnexpectedEof),
 846                 (1, 1)
 847             ))
 848         );
 849         assert_eq!(
 850             parse_expression(",@", 0),
 851             Error(ParseError::Sexp(
 852                 Box::new(ParseError::UnexpectedEof),
 853                 (2, 2)
 854             ))
 855         );
 856     }
 857
 858     #[test]
 859     fn test_parse_list() {
 860         assert_eq!(parse_list("()", 0), Done("", Sexp::List(vec![], (0, 2))));
 861         assert_eq!(
 862             parse_list("(1)", 0),
 863             Done("", Sexp::List(vec![Sexp::Int(1, (1, 2))], (0, 3)))
 864         );
 865         assert_eq!(
 866             parse_list("  ( 1    2  3 a )", 0),
 867             Done(
 868                 "",
 869                 Sexp::List(
 870                     vec![
 871                         Sexp::Int(1, (4, 5)),
 872                         Sexp::Int(2, (9, 10)),
 873                         Sexp::Int(3, (12, 13)),
 874                         Sexp::Sym("a".into(), (14, 15)),
 875                     ],
 876                     (2, 17)
 877                 )
 878             )
 879         );
 880     }
 881
 882     #[test]
 883     fn test_parse_number() {
 884         assert_eq!(parse_number("1", 0), Done("", Sexp::Int(1, (0, 1))));
 885         assert_eq!(parse_number(" 13", 0), Done("", Sexp::Int(13, (1, 3))));
 886         assert_eq!(parse_number("1.2", 0), Done("", Sexp::Float(1.2, (0, 3))));
 887         assert_eq!(
 888             parse_number("\u{3000}4.2", 0),
 889             Done("", Sexp::Float(4.2, (0, 3).offset('\u{3000}'.len_utf8())))
 890         );
 891         assert_eq!(parse_number("       42 ", 0), Done(" ", Sexp::Int(42, (2, 4))));
 892         assert_eq!(
 893             parse_number(" 4.2  ", 0),
 894             Done("  ", Sexp::Float(4.2, (1, 4)))
 895         );
 896         assert_eq!(parse_number("1()", 0), Done("()", Sexp::Int(1, (0, 1))));
 897         assert_eq!(
 898             parse_number("3.6()", 0),
 899             Done("()", Sexp::Float(3.6, (0, 3)))
 900         );
 901
 902         assert_eq!(
 903             parse_number("", 0),
 904             Error(ParseError::Number(
 905                 Box::new(ParseError::UnexpectedEof),
 906                 (0, 0)
 907             ))
 908         );
 909         assert_eq!(
 910             parse_number("123a", 0),
 911             Error(ParseError::Number(
 912                 Box::new(ParseError::Unexpected('a', 3)),
 913                 (3, 3)
 914             ))
 915         );
 916         assert_eq!(
 917             parse_number("66.6+", 0),
 918             Error(ParseError::Number(
 919                 Box::new(ParseError::Unexpected('+', 4)),
 920                 (4, 4)
 921             ))
 922         );
 923     }
 924
 925     #[test]
 926     fn test_parse_ident() {
 927         assert_eq!(
 928             parse_symbol("+", 0),
 929             Done("", Sexp::Sym("+".into(), (0, 1)))
 930         );
 931         assert_eq!(
 932             parse_symbol(" nil?", 0),
 933             Done("", Sexp::Sym("nil?".into(), (1, 5)))
 934         );
 935         assert_eq!(
 936             parse_symbol(" ->socket", 0),
 937             Done("", Sexp::Sym("->socket".into(), (1, 9)))
 938         );
 939         assert_eq!(
 940             parse_symbol("fib(", 0),
 941             Done("(", Sexp::Sym("fib".into(), (0, 3)))
 942         );
 943         assert_eq!(
 944             parse_symbol("foo2", 0),
 945             Done("", Sexp::Sym("foo2".into(), (0, 4)))
 946         );
 947
 948         // We reserve #foo for the implementation to do as it wishes
 949         assert_eq!(
 950             parse_symbol("#hi", 0),
 951             Error(ParseError::Symbol(
 952                 Box::new(ParseError::Unexpected('#', 0)),
 953                 (0, 0)
 954             ))
 955         );
 956         // We reserve :foo for keywords
 957         assert_eq!(
 958             parse_symbol(":hi", 0),
 959             Error(ParseError::Symbol(
 960                 Box::new(ParseError::Unexpected(':', 0)),
 961                 (0, 0)
 962             ))
 963         );
 964
 965         assert_eq!(
 966             parse_symbol("", 0),
 967             Error(ParseError::Symbol(
 968                 Box::new(ParseError::UnexpectedEof),
 969                 (0, 0)
 970             ))
 971         );
 972         assert_eq!(
 973             parse_symbol("0", 0),
 974             Error(ParseError::Symbol(
 975                 Box::new(ParseError::Unexpected('0', 0)),
 976                 (0, 0)
 977             ))
 978         );
 979         assert_eq!(
 980             parse_symbol("()", 0),
 981             Error(ParseError::Symbol(
 982                 Box::new(ParseError::Unexpected('(', 0)),
 983                 (0, 0)
 984             ))
 985         );
 986     }
 987
 988     #[test]
 989     fn test_parse_string() {
 990         assert_eq!(
 991             parse_string(r#""""#, 0),
 992             Done("", Sexp::Str("".into(), (0, 2)))
 993         );
 994         assert_eq!(
 995             parse_string(r#""hello""#, 0),
 996             Done("", Sexp::Str("hello".into(), (0, 7)))
 997         );
 998         assert_eq!(
 999             parse_string(
1000                 r#"  "this is a nice string
1001 with 0123 things in it""#,
1002                 0
1003             ),
1004             Done(
1005                 "",
1006                 Sexp::Str(
1007                     "this is a nice string\nwith 0123 things in it".into(),
1008                     (2, 48)
1009                 )
1010             )
1011         );
1012
1013         assert_eq!(
1014             parse_string("", 0),
1015             Error(ParseError::String(
1016                 Box::new(ParseError::UnexpectedEof),
1017                 (0, 0)
1018             ))
1019         );
1020         assert_eq!(
1021             parse_string(r#""hi"#, 0),
1022             Error(ParseError::String(
1023                 Box::new(ParseError::UnexpectedEof),
1024                 (0, 3)
1025             ))
1026         );
1027     }
1028
1029     #[test]
1030     fn test_parse_char() {
1031         assert_eq!(
1032             parse_character(r#"#\""#, 0),
1033             Done("", Sexp::Char('"', (0, 3)))
1034         );
1035         assert_eq!(
1036             parse_character(r#"#\ "#, 0),
1037             Done("", Sexp::Char(' ', (0, 3)))
1038         );
1039         assert_eq!(
1040             parse_character(r#"  #\\"#, 0),
1041             Done("", Sexp::Char('\\', (2, 5)))
1042         );
1043
1044         assert_eq!(
1045             parse_character("", 0),
1046             Error(ParseError::Char(
1047                 Box::new(ParseError::UnexpectedEof),
1048                 (0, 0)
1049             ))
1050         );
1051         assert_eq!(
1052             parse_character("#", 0),
1053             Error(ParseError::Char(
1054                 Box::new(ParseError::UnexpectedEof),
1055                 (1, 1)
1056             ))
1057         );
1058         assert_eq!(
1059             parse_character("#\\", 0),
1060             Error(ParseError::Char(
1061                 Box::new(ParseError::UnexpectedEof),
1062                 (2, 2)
1063             ))
1064         );
1065         assert_eq!(
1066             parse_character("a", 0),
1067             Error(ParseError::Char(
1068                 Box::new(ParseError::Unexpected('a', 0)),
1069                 (0, 0)
1070             ))
1071         );
1072     }
1073
1074     #[test]
1075     fn test_parse_comments() {
1076         assert_eq!(
1077             parse(
1078                 r#"(;hello
1079     ;hi
1080 ;hey ;how are you doing?
1081 ) ;hi"#
1082             ),
1083             (vec![Sexp::List(vec![], (0, 42))], None)
1084         )
1085     }
1086 }