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

   1 //! A lightweight S-expression parser intended for language implementation.
   2
   3 // #![warn(missing_docs)]
   4 #![deny(unsafe_code)]
   5
   6 use std::borrow::Cow;
   7
   8 /// A type representing arbitrary symbolic expressions. `Sexp` carries the
   9 /// source code location it came from along with it for later diagnostic
  10 /// purposes.
  11 #[derive(Debug, PartialEq, Clone, PartialOrd)]
  12 pub enum Sexp<'a, Loc=ByteSpan> where Loc: Span {
  13     /// A value representing a symbol.
  14     Sym(Cow<'a, str>, Loc),
  15     /// A value representing a string literal.
  16     Str(Cow<'a, str>, Loc),
  17     /// A value representing a single character.
  18     Char(char, Loc),
  19     /// A value representing an integer. Any number containing no decimal point
  20     /// will be parsed as an `Int`.
  21     Int(i64, Loc),
  22     /// A value representing a floating point number. Any number containing a
  23     /// decimal point will be parsed as a `Float`.
  24     Float(f64, Loc),
  25     /// A list of subexpressions.
  26     List(Vec<Sexp<'a, Loc>>, Loc),
  27 }
  28
  29 impl<'a, Loc> Sexp<'a, Loc> where Loc: Span {
  30     pub fn get_loc(&self) -> &Loc {
  31         match *self {
  32             Sexp::Sym(.., ref l) => l,
  33             Sexp::Str(.., ref l) => l,
  34             Sexp::Char(.., ref l) => l,
  35             Sexp::Int(.., ref l) => l,
  36             Sexp::Float(.., ref l) => l,
  37             Sexp::List(.., ref l) => l,
  38         }
  39     }
  40
  41     pub fn get_loc_mut(&mut self) -> &mut Loc {
  42         match *self {
  43             Sexp::Sym(.., ref mut l) => l,
  44             Sexp::Str(.., ref mut l) => l,
  45             Sexp::Char(.., ref mut l) => l,
  46             Sexp::Int(.., ref mut l) => l,
  47             Sexp::Float(.., ref mut l) => l,
  48             Sexp::List(.., ref mut l) => l,
  49         }
  50     }
  51 }
  52
  53 \f
  54 // General Parsing Types ///////////////////////////////////////////////////////
  55
  56 pub trait Span {
  57     type Begin;
  58
  59     fn offset(&self, begin: Self::Begin) -> Self;
  60     fn begin(&self) -> Self::Begin;
  61     fn union(&self, other: &Self) -> Self;
  62 }
  63
  64 #[derive(Debug, PartialEq, Eq, Clone)]
  65 pub enum ParseResult<'a, T, E> {
  66     Done(&'a str, T),
  67     Error(E),
  68 }
  69
  70 use ParseResult::*;
  71
  72 \f
  73 // Specific Parsing Types (ParseError, ByteSpan) ///////////////////////////////
  74
  75 /// Indicates how parsing failed.
  76 #[derive(Debug, PartialEq, Eq, Clone)]
  77 pub enum ParseError<Loc=ByteSpan> where Loc: Span {
  78     UnexpectedEof,
  79     List(Box<ParseError>, Loc),
  80     Sexp(Box<ParseError>, Loc),
  81     Char(Box<ParseError>, Loc),
  82     String(Box<ParseError>, Loc),
  83     Symbol(Box<ParseError>, Loc),
  84     Number(Box<ParseError>, Loc),
  85     Unexpected(char, Loc::Begin),
  86     Unimplemented,
  87 }
  88
  89 type ByteSpan = (usize, usize);
  90
  91 impl Span for ByteSpan {
  92     type Begin = usize;
  93
  94     fn offset(&self, begin: Self::Begin) -> Self {
  95         (self.0 + begin, self.1 + begin)
  96     }
  97
  98     fn begin(&self) -> Self::Begin {
  99         self.0
 100     }
 101
 102     fn union(&self, other: &Self) -> Self {
 103         use std::cmp::{min, max};
 104         (min(self.0, other.0), max(self.1, other.1))
 105     }
 106 }
 107
 108
 109 \f
 110 // Parsing Utilities ///////////////////////////////////////////////////////////
 111
 112 trait IsDelimeter {
 113     fn is_delimiter(&self) -> bool;
 114 }
 115
 116 impl IsDelimeter for char {
 117     fn is_delimiter(&self) -> bool {
 118         self.is_whitespace() || *self == ';'
 119             || *self == '(' || *self == ')'
 120             || *self == '[' || *self == ']'
 121             || *self == '{' || *self == '}'
 122             || *self == '"' || *self == '\''
 123             || *self == '`' || *self == ','
 124     }
 125 }
 126
 127 macro_rules! consume_whitespace {
 128     ($input:expr, $start_loc:expr, $ErrorFn:expr) => {
 129         if let Some(pos) = $input.find(|c: char| !c.is_whitespace()) {
 130             (&$input[pos..], $start_loc + pos)
 131         } else {
 132             return Error($ErrorFn(
 133                 Box::new(ParseError::UnexpectedEof),
 134                 ($input.len(), $input.len()).offset($start_loc)));
 135         }
 136     }
 137 }
 138
 139 \f
 140 // Parsers /////////////////////////////////////////////////////////////////////
 141
 142 pub fn parse_sexp(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 143     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Sexp);
 144
 145     match input.chars().next() {
 146         Some('0'...'9') => parse_number(input, start_loc),
 147         Some('(') => parse_list(input, start_loc),
 148         Some('#') => parse_character(input, start_loc),
 149         Some('"') => parse_string(input, start_loc),
 150         Some(_) => parse_symbol(input, start_loc),
 151         None => unreachable!(),
 152     }
 153 }
 154
 155 pub fn parse_list(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 156     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::List);
 157
 158     match input.chars().nth(0) {
 159         Some('(') => (),
 160         Some(c) =>
 161             return Error(ParseError::List(
 162                 Box::new(ParseError::Unexpected(c, 0)),
 163                 (0, 0).offset(start_loc))),
 164         None => unreachable!(),
 165     }
 166
 167     let mut input = &input[1..];
 168     let mut loc = start_loc + 1;
 169     let mut members = Vec::new();
 170     println!("!{}", loc);
 171     loop {
 172         {
 173             let (new_input, new_loc) = consume_whitespace!(input, loc, ParseError::List);
 174             input = new_input;
 175             loc = new_loc;
 176             println!("{}", loc);
 177         }
 178
 179         match input.chars().nth(0) {
 180             Some(')') =>
 181                 return Done(&input[1..],
 182                             Sexp::List(members, (start_loc, loc+1))),
 183             Some(_) => (),
 184             None => unreachable!(),
 185         }
 186
 187         match parse_sexp(input, loc) {
 188             Done(new_input, member) => {
 189                 loc = member.get_loc().1;
 190                 members.push(member);
 191                 input = new_input;
 192             }
 193             Error(err) =>
 194                 return Error(ParseError::List(
 195                     Box::new(err),
 196                     (0, 0).offset(loc)))
 197         }
 198     }
 199 }
 200
 201 pub fn parse_number(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 202     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Number);
 203
 204     match input.chars().next() {
 205         Some(c) if !c.is_digit(10) => {
 206             return Error(ParseError::Number(
 207                 Box::new(ParseError::Unexpected(c, start_loc)),
 208                 (0, c.len_utf8()).offset(start_loc)));
 209         }
 210         None => return Error(ParseError::Number(
 211             Box::new(ParseError::UnexpectedEof),
 212             (0, 0).offset(start_loc))),
 213         _ => (),
 214     }
 215
 216     let base = 10;
 217
 218     let mut end = 0;
 219     // Before the decimal point
 220     for (i, c) in input.char_indices() {
 221         if c == '.' {
 222             end = i + 1;
 223             break;
 224         }
 225
 226         if c.is_delimiter() {
 227             return Done(&input[i..],
 228                         Sexp::Int(input[..i].parse().expect("Already matched digits"),
 229                                   (0, i).offset(start_loc)));
 230         }
 231
 232         if !c.is_digit(base) {
 233             return Error(ParseError::Number(
 234                 Box::new(ParseError::Unexpected(c, start_loc + i)),
 235                 (i, i).offset(start_loc)));
 236         }
 237
 238         end = i + c.len_utf8();
 239     }
 240
 241     if input[end..].is_empty() {
 242         return Done(&input[end..],
 243                     Sexp::Int(input.parse().expect("Already matched digits"),
 244                               (0, end).offset(start_loc)));
 245     }
 246
 247     // After the decimal point
 248     for (i, c) in input[end..].char_indices() {
 249         if c.is_delimiter() {
 250             return Done(&input[i+end..],
 251                         Sexp::Float(input[..end+i].parse().expect("Already matched digits.digits"),
 252                                     (0, end+i).offset(start_loc)));
 253         }
 254
 255         if !c.is_digit(base) {
 256             return Error(ParseError::Number(
 257                 Box::new(ParseError::Unexpected(c, start_loc + i + end)),
 258                 (i+end, i+end).offset(start_loc)));
 259         }
 260     }
 261
 262     Done(&input[input.len()..],
 263          Sexp::Float(input.parse().expect("Already matched digits.digits"),
 264                      (0, input.len()).offset(start_loc)))
 265 }
 266
 267 pub fn parse_symbol(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 268     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Symbol);
 269
 270     match input.chars().next() {
 271         Some(c@'#') | Some(c@':') | Some(c@'0'...'9') =>
 272             return Error(ParseError::Symbol(
 273                 Box::new(ParseError::Unexpected(c, start_loc)),
 274                 (0, 0).offset(start_loc))),
 275         Some(c) if c.is_delimiter() =>
 276             return Error(ParseError::Symbol(
 277                 Box::new(ParseError::Unexpected(c, start_loc)),
 278                 (0, 0).offset(start_loc))),
 279         Some(_) => (),
 280         None => unreachable!(),
 281     }
 282
 283     for (i, c) in input.char_indices() {
 284         if c.is_delimiter() {
 285             return Done(&input[i..],
 286                         Sexp::Sym(input[..i].into(), (0, i).offset(start_loc)));
 287         }
 288     }
 289
 290     Done(&input[input.len()..],
 291          Sexp::Sym(input.into(), (0, input.len()).offset(start_loc)))
 292 }
 293
 294 pub fn parse_string(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 295     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::String);
 296
 297     match input.chars().next() {
 298         Some('"') => (),
 299         Some(c) =>
 300             return Error(ParseError::String(
 301                 Box::new(ParseError::Unexpected(c, start_loc)),
 302             (0, 0).offset(start_loc))),
 303         None => unreachable!(),
 304     }
 305
 306     for (i, c) in input[1..].char_indices() {
 307         if c == '"' {
 308             return Done(&input[2+i..],
 309             Sexp::Str(input[1..i+1].into(), (0, i+2).offset(start_loc)));
 310         }
 311     }
 312
 313     Error(ParseError::String(
 314         Box::new(ParseError::UnexpectedEof),
 315         (0, input.len()).offset(start_loc)))
 316 }
 317
 318 pub fn parse_character(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 319     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Char);
 320
 321     match input.chars().nth(0) {
 322         Some('#') => (),
 323         Some(c) =>
 324             return Error(ParseError::Char(
 325                 Box::new(ParseError::Unexpected(c, start_loc)),
 326                 (0, 0).offset(start_loc))),
 327         None =>
 328             return Error(ParseError::Char(
 329                 Box::new(ParseError::UnexpectedEof),
 330                 (0, 0).offset(start_loc))),
 331     }
 332
 333     match input.chars().nth(1) {
 334         Some('\\') => (),
 335         Some(c) =>
 336             return Error(ParseError::Char(
 337                 Box::new(ParseError::Unexpected(c, start_loc + 1)),
 338                 (1, 1).offset(start_loc))),
 339         None =>
 340             return Error(ParseError::Char(
 341                 Box::new(ParseError::UnexpectedEof),
 342                 (1, 1).offset(start_loc)))
 343     }
 344
 345     match input.chars().nth(2) {
 346         Some(c) =>
 347             Done(&input[3..], Sexp::Char(c, (0, 3).offset(start_loc))),
 348         None =>
 349             Error(ParseError::Char(
 350                 Box::new(ParseError::UnexpectedEof),
 351                 (2, 2).offset(start_loc)))
 352     }
 353 }
 354
 355 \f
 356 // Tests ///////////////////////////////////////////////////////////////////////
 357
 358 #[cfg(test)]
 359 mod test {
 360     use super::*;
 361     use super::ParseResult::*;
 362
 363     #[test]
 364     fn test_parse_sexp() {
 365         assert_eq!(parse_sexp(" 1", 0), Done("", Sexp::Int(1, (1, 2))));
 366         assert_eq!(parse_sexp("2.2", 0), Done("", Sexp::Float(2.2, (0, 3))));
 367         assert_eq!(parse_sexp(" a", 0), Done("", Sexp::Sym("a".into(), (1, 2))));
 368         assert_eq!(parse_sexp("#\\c", 0), Done("", Sexp::Char('c', (0, 3))));
 369         assert_eq!(parse_sexp(r#""hi""#, 0), Done("", Sexp::Str("hi".into(), (0, 4))));
 370         assert_eq!(parse_sexp("()", 0), Done("", Sexp::List(vec![], (0, 2))));
 371         assert_eq!(parse_sexp("( 1 2 3 )", 0), Done("", Sexp::List(vec![
 372             Sexp::Int(1, (2, 3)),
 373             Sexp::Int(2, (4, 5)),
 374             Sexp::Int(3, (6, 7)),
 375         ], (0, 9))));
 376
 377         assert_eq!(parse_sexp("", 0), Error(ParseError::Sexp(Box::new(ParseError::UnexpectedEof), (0, 0))));
 378     }
 379
 380     #[test]
 381     fn test_parse_list() {
 382         assert_eq!(parse_list("()", 0), Done("", Sexp::List(vec![], (0, 2))));
 383         assert_eq!(parse_list("(1)", 0), Done("", Sexp::List(vec![Sexp::Int(1, (1, 2))], (0, 3))));
 384         assert_eq!(parse_list("  ( 1    2  3 a )", 0), Done("", Sexp::List(vec![
 385             Sexp::Int(1, (4, 5)),
 386             Sexp::Int(2, (9, 10)),
 387             Sexp::Int(3, (12, 13)),
 388             Sexp::Sym("a".into(), (14, 15)),
 389         ], (2, 17))));
 390     }
 391
 392     #[test]
 393     fn test_parse_number() {
 394         assert_eq!(parse_number("1", 0), Done("", Sexp::Int(1, (0, 1))));
 395         assert_eq!(parse_number(" 13", 0), Done("", Sexp::Int(13, (1, 3))));
 396         assert_eq!(parse_number("1.2", 0), Done("", Sexp::Float(1.2, (0, 3))));
 397         assert_eq!(parse_number("\u{3000}4.2", 0), Done("", Sexp::Float(4.2, (0, 3).offset('\u{3000}'.len_utf8()))));
 398         assert_eq!(parse_number("       42 ", 0), Done(" ", Sexp::Int(42, (2, 4))));
 399         assert_eq!(parse_number(" 4.2  ", 0), Done("  ", Sexp::Float(4.2, (1, 4))));
 400         assert_eq!(parse_number("1()", 0), Done("()", Sexp::Int(1, (0, 1))));
 401         assert_eq!(parse_number("3.6()", 0), Done("()", Sexp::Float(3.6, (0, 3))));
 402
 403         assert_eq!(parse_number("", 0), Error(ParseError::Number(Box::new(ParseError::UnexpectedEof), (0, 0))));
 404         assert_eq!(parse_number("123a", 0), Error(ParseError::Number(Box::new(ParseError::Unexpected('a', 3)), (3, 3))));
 405         assert_eq!(parse_number("66.6+", 0), Error(ParseError::Number(Box::new(ParseError::Unexpected('+', 4)), (4, 4))));
 406     }
 407
 408     #[test]
 409     fn test_parse_ident() {
 410         assert_eq!(parse_symbol("+", 0), Done("", Sexp::Sym("+".into(), (0, 1))));
 411         assert_eq!(parse_symbol(" nil?", 0), Done("", Sexp::Sym("nil?".into(), (1, 5))));
 412         assert_eq!(parse_symbol(" ->socket", 0), Done("", Sexp::Sym("->socket".into(), (1, 9))));
 413         assert_eq!(parse_symbol("fib(", 0), Done("(", Sexp::Sym("fib".into(), (0, 3))));
 414         assert_eq!(parse_symbol("foo2", 0), Done("", Sexp::Sym("foo2".into(), (0, 4))));
 415
 416         // We reserve #foo for the implementation to do as it wishes
 417         assert_eq!(parse_symbol("#hi", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('#', 0)), (0, 0))));
 418         // We reserve :foo for keywords
 419         assert_eq!(parse_symbol(":hi", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected(':', 0)), (0, 0))));
 420
 421         assert_eq!(parse_symbol("", 0), Error(ParseError::Symbol(Box::new(ParseError::UnexpectedEof), (0, 0))));
 422         assert_eq!(parse_symbol("0", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('0', 0)), (0, 0))));
 423         assert_eq!(parse_symbol("()", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('(', 0)), (0, 0))));
 424     }
 425
 426     #[test]
 427     fn test_parse_string() {
 428         assert_eq!(parse_string(r#""""#, 0), Done("", Sexp::Str("".into(), (0, 2))));
 429         assert_eq!(parse_string(r#""hello""#, 0), Done("", Sexp::Str("hello".into(), (0, 7))));
 430         assert_eq!(parse_string(r#"  "this is a nice string
 431 with 0123 things in it""#, 0),
 432                    Done("", Sexp::Str("this is a nice string\nwith 0123 things in it".into(), (2, 48))));
 433
 434         assert_eq!(parse_string("", 0), Error(ParseError::String(Box::new(ParseError::UnexpectedEof), (0, 0))));
 435         assert_eq!(parse_string(r#""hi"#, 0), Error(ParseError::String(Box::new(ParseError::UnexpectedEof), (0, 3))));
 436     }
 437
 438     #[test]
 439     fn test_parse_char() {
 440         assert_eq!(parse_character(r#"#\""#, 0), Done("", Sexp::Char('"', (0, 3))));
 441         assert_eq!(parse_character(r#"#\ "#, 0), Done("", Sexp::Char(' ', (0, 3))));
 442         assert_eq!(parse_character(r#"  #\\"#, 0), Done("", Sexp::Char('\\', (2, 5))));
 443
 444         assert_eq!(parse_character("", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (0, 0))));
 445         assert_eq!(parse_character("#", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (1, 1))));
 446         assert_eq!(parse_character("#\\", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (2, 2))));
 447         assert_eq!(parse_character("a", 0), Error(ParseError::Char(Box::new(ParseError::Unexpected('a', 0)), (0, 0))));
 448     }
 449 }