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
  18 // Parsing Types ///////////////////////////////////////////////////////////////
  19
  20 /// Represents what to do next in partially completed parsing.
  21 ///
  22 /// `ParseResult` is returned from all intermediate parsers. If you just want to
  23 /// get back parsed s-expressions, you won't need to worry about this type since
  24 /// the top level parsers just return a `Result`.
  25 ///
  26 /// If the parser failed to produce a result, it will return `Error`, and if it
  27 /// succeeded we'll get the `Done` variant containing the value produced and the
  28 /// rest of the text to work on.
  29 #[derive(Debug, PartialEq, Eq, Clone)]
  30 pub enum ParseResult<'a, T, E> {
  31     /// The parser succeeded, this contains first the un-consumed portion of the
  32     /// input then the result produced by parsing.
  33     Done(&'a str, T),
  34     /// The parser failed, the `E` represents the reason for the failure.
  35     Error(E),
  36 }
  37
  38 /// Indicates how parsing failed.
  39 ///
  40 /// Most `ParseError` variants contain a `Box<ParseError>` that represents the
  41 /// cause of that error. Using this, `ParseError` variants can be chained to
  42 /// produce a more complete picture of what exactly went wrong during parsing.
  43 #[derive(Debug, PartialEq, Eq, Clone)]
  44 pub enum ParseError<Loc = ByteSpan>
  45 where
  46     Loc: Span,
  47 {
  48     /// Parsing reached the end of input where not expecting to, usually this
  49     /// will be contained inside another `ParseError` like `String(box
  50     /// UnexpectedEof, ...)` which indicates that the closing quote was never
  51     /// found.
  52     UnexpectedEof,
  53     /// Some problem occurred while parsing a list, along with the cause of that
  54     /// error.
  55     List(Box<ParseError>, Loc),
  56     /// Some problem occurred while parsing an s-expression. This will only be
  57     /// generated if EOF is reached unexpectedly at the beginning of
  58     /// `parse_expression`, so it should probably be removed.
  59     Sexp(Box<ParseError>, Loc),
  60     /// Some problem occurred while parsing a character literal, along with the
  61     /// cause of the error.
  62     Char(Box<ParseError>, Loc),
  63     /// Some problem occurred while parsing a string literal, along with the
  64     /// cause of the error.
  65     String(Box<ParseError>, Loc),
  66     /// Some problem occurred while parsing a symbol, along with the cause of
  67     /// the error.
  68     Symbol(Box<ParseError>, Loc),
  69     /// Some problem occurred while parsing a number literal, along with the
  70     /// cause of the error.
  71     Number(Box<ParseError>, Loc),
  72     /// An unexpected character was found. This will usually be the root cause
  73     /// in some chain of `ParseError`s.
  74     Unexpected(char, Loc::Begin),
  75 }
  76 use self::ParseResult::*;
  77
  78 // Parsing Utilities ///////////////////////////////////////////////////////////
  79
  80 trait IsDelimeter {
  81     fn is_delimiter(&self) -> bool;
  82 }
  83
  84 impl IsDelimeter for char {
  85     fn is_delimiter(&self) -> bool {
  86         let delim_chars = r#";()[]{}"\`,"#;
  87         self.is_whitespace() || delim_chars.contains(*self)
  88     }
  89 }
  90
  91 fn consume_whitespace<'a>(input: &'a str, start_loc: usize) -> (&'a str, usize) {
  92     let mut buffer = input;
  93     let mut loc = start_loc;
  94     while !buffer.is_empty() && (buffer.starts_with(char::is_whitespace) || buffer.starts_with(';'))
  95     {
  96         if let Some(pos) = buffer.find(|c: char| !c.is_whitespace()) {
  97             buffer = &buffer[pos..];
  98             loc += pos;
  99         } else {
 100             buffer = &buffer[buffer.len()..];
 101             loc += buffer.len();
 102         }
 103
 104         if buffer.starts_with(';') {
 105             if let Some(pos) = buffer.find('\n') {
 106                 buffer = &buffer[pos + 1..];
 107                 loc += pos + 1;
 108             } else {
 109                 buffer = &buffer[buffer.len()..];
 110                 loc += buffer.len();
 111             }
 112         }
 113     }
 114     (&buffer, loc)
 115 }
 116
 117 macro_rules! consume_whitespace {
 118     ($input:expr, $start_loc:expr, $ErrorFn:expr) => {{
 119         let (text, loc) = consume_whitespace($input, $start_loc);
 120         if text.is_empty() {
 121             return Error($ErrorFn(Box::new(ParseError::UnexpectedEof), (loc, loc)));
 122         } else {
 123             (text, loc)
 124         }
 125     }};
 126 }
 127
 128 // Top Level Parsers ///////////////////////////////////////////////////////////
 129
 130 /// Parse a sequence of s-expressions.
 131 ///
 132 /// This function returns `(Vec<Sexp>, Option<ParseError>)` so that it can
 133 /// return partial results, for when some component parses successfully and a
 134 /// later part fails.
 135 ///
 136 /// # Errors
 137 ///
 138 /// If the text contains an invalid s-expression (imbalanced parenthesis,
 139 /// quotes, invalid numbers like 123q, etc.) then the parser will stop and
 140 /// return an error. Every s-expression before that point that successfully
 141 /// parsed will still be returned.
 142 ///
 143 /// # Examples
 144 ///
 145 /// We can get useful partial results
 146 ///
 147 /// ```rust
 148 /// # use ess::parser::parse;
 149 /// let (exprs, err) = parse("1 2 3 ( 4");
 150 /// assert_eq!(exprs.len(), 3);
 151 /// assert!(err.is_some());
 152 /// ```
 153 pub fn parse(mut input: &str) -> (Vec<Sexp>, Option<ParseError>) {
 154     let mut start_loc = 0;
 155     let mut results = Vec::new();
 156     loop {
 157         match parse_expression(input, start_loc) {
 158             Done(rest, result) => {
 159                 let (rest, loc) = consume_whitespace(rest, result.get_loc().1);
 160                 input = rest;
 161                 start_loc = loc;
 162                 results.push(result);
 163                 if rest.trim() == "" {
 164                     return (results, None);
 165                 }
 166             }
 167             Error(err) => {
 168                 return (results, Some(err));
 169             }
 170         }
 171     }
 172 }
 173
 174 /// Parses a single s-expression, ignoring any trailing text.
 175 ///
 176 /// This function returns a pair of the parsed s-expression and the tail of the text.
 177 ///
 178 /// # Errors
 179 ///
 180 /// If the text begins with an invalid s-expression (imbalanced parenthesis,
 181 /// quotes, invalid numbers like 123q, etc.) then the parser will return an
 182 /// error. Any text after the first s-expression doesn't affect the parsing.
 183
 184 ///
 185 /// # Examples
 186 ///
 187 /// ```rust
 188 /// # use ess::parser::parse_one;
 189 /// let (expr, rest) = parse_one("1 (").unwrap();
 190 /// assert_eq!(rest, " (");
 191 /// ```
 192 pub fn parse_one(input: &str) -> Result<(Sexp, &str), ParseError> {
 193     match parse_expression(input, 0) {
 194         Done(rest, result) => Ok((result, rest)),
 195         Error(err) => Err(err),
 196     }
 197 }
 198
 199 // Core Parsers ////////////////////////////////////////////////////////////////
 200
 201 // TODO: All of these parsers deserve docs, but since they're somewhat internal
 202 // parsers, it's less critical than the rest of the API.
 203
 204 #[allow(missing_docs)]
 205 pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 206     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Sexp);
 207
 208     match input.chars().next() {
 209         Some('0'...'9') => parse_number(input, start_loc),
 210         Some('(') | Some('{') | Some('[') => parse_list(input, start_loc),
 211         Some('#') => parse_character(input, start_loc),
 212         Some('"') => parse_string(input, start_loc),
 213         Some('\'') => match parse_expression(&input[1..], start_loc + 1) {
 214             Done(rest, result) => {
 215                 let span = *result.get_loc();
 216                 let quote_span = (0, 1).offset(start_loc);
 217                 Done(
 218                     rest,
 219                     Sexp::List(
 220                         vec![Sexp::Sym("quote".into(), quote_span), result],
 221                         quote_span.union(&span),
 222                     ),
 223                 )
 224             }
 225             err => err,
 226         },
 227         Some('`') => match parse_expression(&input[1..], start_loc + 1) {
 228             Done(rest, result) => {
 229                 let span = *result.get_loc();
 230                 let quote_span = (0, 1).offset(start_loc);
 231                 Done(
 232                     rest,
 233                     Sexp::List(
 234                         vec![Sexp::Sym("quasiquote".into(), quote_span), result],
 235                         quote_span.union(&span),
 236                     ),
 237                 )
 238             }
 239             err => err,
 240         },
 241         Some(',') => {
 242             if input[1..].starts_with('@') {
 243                 match parse_expression(&input[2..], start_loc + 2) {
 244                     Done(rest, result) => {
 245                         let span = *result.get_loc();
 246                         let quote_span = (0, 2).offset(start_loc);
 247                         Done(
 248                             rest,
 249                             Sexp::List(
 250                                 vec![Sexp::Sym("unquote-splicing".into(), quote_span), result],
 251                                 quote_span.union(&span),
 252                             ),
 253                         )
 254                     }
 255                     err => err,
 256                 }
 257             } else {
 258                 match parse_expression(&input[1..], start_loc + 1) {
 259                     Done(rest, result) => {
 260                         let span = *result.get_loc();
 261                         let quote_span = (0, 1).offset(start_loc);
 262                         Done(
 263                             rest,
 264                             Sexp::List(
 265                                 vec![Sexp::Sym("unquote".into(), quote_span), result],
 266                                 quote_span.union(&span),
 267                             ),
 268                         )
 269                     }
 270                     err => err,
 271                 }
 272             }
 273         }
 274         Some(_) => parse_symbol(input, start_loc),
 275         None => unreachable!(),
 276     }
 277 }
 278
 279 #[allow(missing_docs)]
 280 pub fn parse_list(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 281     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::List);
 282
 283     let first_char = match input.chars().nth(0) {
 284         Some(c @ '(') | Some(c @ '{') | Some(c @ '[') => c,
 285         Some(c) => {
 286             return Error(ParseError::List(
 287                 Box::new(ParseError::Unexpected(c, 0)),
 288                 (0, 0).offset(start_loc),
 289             ))
 290         }
 291         None => unreachable!(),
 292     };
 293
 294     let mut input = &input[1..];
 295     let mut loc = start_loc + 1;
 296     let mut members = Vec::new();
 297     loop {
 298         {
 299             let (new_input, new_loc) = consume_whitespace!(input, loc, ParseError::List);
 300             input = new_input;
 301             loc = new_loc;
 302         }
 303
 304         match input.chars().nth(0) {
 305             Some(c @ ')') | Some(c @ '}') | Some(c @ ']') => match (first_char, c) {
 306                 ('(', ')') | ('{', '}') | ('[', ']') => {
 307                     return Done(&input[1..], Sexp::List(members, (start_loc, loc + 1)))
 308                 }
 309                 _ => {
 310                     return Error(ParseError::List(
 311                         Box::new(ParseError::Unexpected(c, loc)),
 312                         (start_loc, loc),
 313                     ))
 314                 }
 315             },
 316             Some(_) => (),
 317             None => unreachable!(),
 318         }
 319
 320         match parse_expression(input, loc) {
 321             Done(new_input, member) => {
 322                 loc = member.get_loc().1;
 323                 members.push(member);
 324                 input = new_input;
 325             }
 326             Error(err) => return Error(ParseError::List(Box::new(err), (0, 0).offset(loc))),
 327         }
 328     }
 329 }
 330
 331 #[allow(missing_docs)]
 332 pub fn parse_number(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 333     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Number);
 334
 335     match input.chars().next() {
 336         Some(c) if !c.is_digit(10) => {
 337             return Error(ParseError::Number(
 338                 Box::new(ParseError::Unexpected(c, start_loc)),
 339                 (0, c.len_utf8()).offset(start_loc),
 340             ));
 341         }
 342         None => {
 343             return Error(ParseError::Number(
 344                 Box::new(ParseError::UnexpectedEof),
 345                 (0, 0).offset(start_loc),
 346             ))
 347         }
 348         _ => (),
 349     }
 350
 351     let base = 10;
 352
 353     let mut end = 0;
 354     // Before the decimal point
 355     for (i, c) in input.char_indices() {
 356         if c == '.' {
 357             end = i + 1;
 358             break;
 359         }
 360
 361         if c.is_delimiter() {
 362             return Done(
 363                 &input[i..],
 364                 Sexp::Int(
 365                     input[..i].parse().expect("Already matched digits"),
 366                     (0, i).offset(start_loc),
 367                 ),
 368             );
 369         }
 370
 371         if !c.is_digit(base) {
 372             return Error(ParseError::Number(
 373                 Box::new(ParseError::Unexpected(c, start_loc + i)),
 374                 (i, i).offset(start_loc),
 375             ));
 376         }
 377
 378         end = i + c.len_utf8();
 379     }
 380
 381     if input[end..].is_empty() {
 382         return Done(
 383             &input[end..],
 384             Sexp::Int(
 385                 input.parse().expect("Already matched digits"),
 386                 (0, end).offset(start_loc),
 387             ),
 388         );
 389     }
 390
 391     // After the decimal point
 392     for (i, c) in input[end..].char_indices() {
 393         if c.is_delimiter() {
 394             return Done(
 395                 &input[i + end..],
 396                 Sexp::Float(
 397                     input[..end + i]
 398                         .parse()
 399                         .expect("Already matched digits.digits"),
 400                     (0, end + i).offset(start_loc),
 401                 ),
 402             );
 403         }
 404
 405         if !c.is_digit(base) {
 406             return Error(ParseError::Number(
 407                 Box::new(ParseError::Unexpected(c, start_loc + i + end)),
 408                 (i + end, i + end).offset(start_loc),
 409             ));
 410         }
 411     }
 412
 413     Done(
 414         &input[input.len()..],
 415         Sexp::Float(
 416             input.parse().expect("Already matched digits.digits"),
 417             (0, input.len()).offset(start_loc),
 418         ),
 419     )
 420 }
 421
 422 #[allow(missing_docs)]
 423 pub fn parse_symbol(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 424     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Symbol);
 425
 426     match input.chars().next() {
 427         Some(c @ '#') | Some(c @ ':') | Some(c @ '0'...'9') => {
 428             return Error(ParseError::Symbol(
 429                 Box::new(ParseError::Unexpected(c, start_loc)),
 430                 (0, 0).offset(start_loc),
 431             ))
 432         }
 433         Some(c) if c.is_delimiter() => {
 434             return Error(ParseError::Symbol(
 435                 Box::new(ParseError::Unexpected(c, start_loc)),
 436                 (0, 0).offset(start_loc),
 437             ))
 438         }
 439         Some(_) => (),
 440         None => unreachable!(),
 441     }
 442
 443     for (i, c) in input.char_indices() {
 444         if c.is_delimiter() {
 445             return Done(
 446                 &input[i..],
 447                 Sexp::Sym(input[..i].into(), (0, i).offset(start_loc)),
 448             );
 449         }
 450     }
 451
 452     Done(
 453         &input[input.len()..],
 454         Sexp::Sym(input.into(), (0, input.len()).offset(start_loc)),
 455     )
 456 }
 457
 458 #[allow(missing_docs)]
 459 pub fn parse_string(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 460     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::String);
 461
 462     match input.chars().next() {
 463         Some('"') => (),
 464         Some(c) => {
 465             return Error(ParseError::String(
 466                 Box::new(ParseError::Unexpected(c, start_loc)),
 467                 (0, 0).offset(start_loc),
 468             ))
 469         }
 470         None => unreachable!(),
 471     }
 472
 473     for (i, c) in input[1..].char_indices() {
 474         if c == '"' {
 475             return Done(
 476                 &input[2 + i..],
 477                 Sexp::Str(input[1..=i].into(), (0, i + 2).offset(start_loc)),
 478             );
 479         }
 480     }
 481
 482     Error(ParseError::String(
 483         Box::new(ParseError::UnexpectedEof),
 484         (0, input.len()).offset(start_loc),
 485     ))
 486 }
 487
 488 #[allow(missing_docs)]
 489 pub fn parse_character(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 490     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Char);
 491
 492     match input.chars().nth(0) {
 493         Some('#') => (),
 494         Some(c) => {
 495             return Error(ParseError::Char(
 496                 Box::new(ParseError::Unexpected(c, start_loc)),
 497                 (0, 0).offset(start_loc),
 498             ))
 499         }
 500         None => {
 501             return Error(ParseError::Char(
 502                 Box::new(ParseError::UnexpectedEof),
 503                 (0, 0).offset(start_loc),
 504             ))
 505         }
 506     }
 507
 508     match input.chars().nth(1) {
 509         Some('\\') => (),
 510         Some(c) => {
 511             return Error(ParseError::Char(
 512                 Box::new(ParseError::Unexpected(c, start_loc + 1)),
 513                 (1, 1).offset(start_loc),
 514             ))
 515         }
 516         None => {
 517             return Error(ParseError::Char(
 518                 Box::new(ParseError::UnexpectedEof),
 519                 (1, 1).offset(start_loc),
 520             ))
 521         }
 522     }
 523
 524     match input.chars().nth(2) {
 525         Some(c) => Done(&input[3..], Sexp::Char(c, (0, 3).offset(start_loc))),
 526         None => Error(ParseError::Char(
 527             Box::new(ParseError::UnexpectedEof),
 528             (2, 2).offset(start_loc),
 529         )),
 530     }
 531 }
 532
 533 // Tests ///////////////////////////////////////////////////////////////////////
 534
 535 #[cfg(test)]
 536 mod test {
 537     use parser::ParseResult::*;
 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 }