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