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     /// We can't explain how the parsing failed.
  79     UnexpectedEof,
  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 \f
 128 // Parsers /////////////////////////////////////////////////////////////////////
 129
 130 macro_rules! consume_whitespace {
 131     ($input:expr, $start_loc:expr, $ErrorFn:expr) => {
 132         if let Some(pos) = $input.find(|c: char| !c.is_whitespace()) {
 133             (&$input[pos..], $start_loc + pos)
 134         } else {
 135             return Error($ErrorFn(
 136                 Box::new(ParseError::UnexpectedEof),
 137                 ($input.len(), $input.len()).offset($start_loc)));
 138         }
 139     }
 140 }
 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('(') => unimplemented!(),
 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_number(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 156     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Number);
 157
 158     match input.chars().next() {
 159         Some(c) if !c.is_digit(10) => {
 160             return Error(ParseError::Number(
 161                 Box::new(ParseError::Unexpected(c, start_loc)),
 162                 (0, c.len_utf8()).offset(start_loc)));
 163         }
 164         None => return Error(ParseError::Number(
 165             Box::new(ParseError::UnexpectedEof),
 166             (0, 0).offset(start_loc))),
 167         _ => (),
 168     }
 169
 170     let base = 10;
 171
 172     let mut end = 0;
 173     // Before the decimal point
 174     for (i, c) in input.char_indices() {
 175         if c == '.' {
 176             end = i + 1;
 177             break;
 178         }
 179
 180         if c.is_delimiter() {
 181             return Done(&input[i..],
 182                         Sexp::Int(input[..i].parse().expect("Already matched digits"),
 183                                   (0, i).offset(start_loc)));
 184         }
 185
 186         if !c.is_digit(base) {
 187             return Error(ParseError::Number(
 188                 Box::new(ParseError::Unexpected(c, start_loc + i)),
 189                 (i, i).offset(start_loc)));
 190         }
 191
 192         end = i + c.len_utf8();
 193     }
 194
 195     if input[end..].is_empty() {
 196         return Done(&input[end..],
 197                     Sexp::Int(input.parse().expect("Already matched digits"),
 198                               (0, end).offset(start_loc)));
 199     }
 200
 201     // After the decimal point
 202     for (i, c) in input[end..].char_indices() {
 203         if c.is_delimiter() {
 204             return Done(&input[i+end..],
 205                         Sexp::Float(input[..end+i].parse().expect("Already matched digits.digits"),
 206                                     (0, end+i).offset(start_loc)));
 207         }
 208
 209         if !c.is_digit(base) {
 210             return Error(ParseError::Number(
 211                 Box::new(ParseError::Unexpected(c, start_loc + i + end)),
 212                 (i+end, i+end).offset(start_loc)));
 213         }
 214     }
 215
 216     Done(&input[input.len()..],
 217          Sexp::Float(input.parse().expect("Already matched digits.digits"),
 218                      (0, input.len()).offset(start_loc)))
 219 }
 220
 221 pub fn parse_symbol(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 222     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Symbol);
 223
 224     match input.chars().next() {
 225         Some(c@'#') | Some(c@':') | Some(c@'0'...'9') =>
 226             return Error(ParseError::Symbol(
 227                 Box::new(ParseError::Unexpected(c, start_loc)),
 228                 (0, 0).offset(start_loc))),
 229         Some(c) if c.is_delimiter() =>
 230             return Error(ParseError::Symbol(
 231                 Box::new(ParseError::Unexpected(c, start_loc)),
 232                 (0, 0).offset(start_loc))),
 233         Some(_) => (),
 234         None => unreachable!(),
 235     }
 236
 237     for (i, c) in input.char_indices() {
 238         if c.is_delimiter() {
 239             return Done(&input[i..],
 240                         Sexp::Sym(input[..i].into(), (0, i).offset(start_loc)));
 241         }
 242     }
 243
 244     Done(&input[input.len()..],
 245          Sexp::Sym(input.into(), (0, input.len()).offset(start_loc)))
 246 }
 247
 248 pub fn parse_string(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 249     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::String);
 250
 251     match input.chars().next() {
 252         Some('"') => (),
 253         Some(c) =>
 254             return Error(ParseError::String(
 255                 Box::new(ParseError::Unexpected(c, start_loc)),
 256             (0, 0).offset(start_loc))),
 257         None => unreachable!(),
 258     }
 259
 260     for (i, c) in input[1..].char_indices() {
 261         if c == '"' {
 262             return Done(&input[2+i..],
 263             Sexp::Str(input[1..i+1].into(), (0, i+2).offset(start_loc)));
 264         }
 265     }
 266
 267     Error(ParseError::String(
 268         Box::new(ParseError::UnexpectedEof),
 269         (0, input.len()).offset(start_loc)))
 270 }
 271
 272 pub fn parse_character(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError> {
 273     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Char);
 274
 275     match input.chars().nth(0) {
 276         Some('#') => (),
 277         Some(c) =>
 278             return Error(ParseError::Char(
 279                 Box::new(ParseError::Unexpected(c, start_loc)),
 280                 (0, 0).offset(start_loc))),
 281         None =>
 282             return Error(ParseError::Char(
 283                 Box::new(ParseError::UnexpectedEof),
 284                 (0, 0).offset(start_loc))),
 285     }
 286
 287     match input.chars().nth(1) {
 288         Some('\\') => (),
 289         Some(c) =>
 290             return Error(ParseError::Char(
 291                 Box::new(ParseError::Unexpected(c, start_loc + 1)),
 292                 (1, 1).offset(start_loc))),
 293         None =>
 294             return Error(ParseError::Char(
 295                 Box::new(ParseError::UnexpectedEof),
 296                 (1, 1).offset(start_loc)))
 297     }
 298
 299     match input.chars().nth(2) {
 300         Some(c) =>
 301             Done(&input[3..], Sexp::Char(c, (0, 3).offset(start_loc))),
 302         None =>
 303             Error(ParseError::Char(
 304                 Box::new(ParseError::UnexpectedEof),
 305                 (2, 2).offset(start_loc)))
 306     }
 307 }
 308
 309 \f
 310 // Tests ///////////////////////////////////////////////////////////////////////
 311
 312 #[cfg(test)]
 313 mod test {
 314     use super::*;
 315     use super::ParseResult::*;
 316
 317     #[test]
 318     fn test_parse_sexp() {
 319         assert_eq!(parse_sexp(" 1", 0), Done("", Sexp::Int(1, (1, 2))));
 320         assert_eq!(parse_sexp("2.2", 0), Done("", Sexp::Float(2.2, (0, 3))));
 321         assert_eq!(parse_sexp(" a", 0), Done("", Sexp::Sym("a".into(), (1, 2))));
 322         assert_eq!(parse_sexp("#\\c", 0), Done("", Sexp::Char('c', (0, 3))));
 323         assert_eq!(parse_sexp(r#""hi""#, 0), Done("", Sexp::Str("hi".into(), (0, 4))));
 324
 325         assert_eq!(parse_sexp("", 0), Error(ParseError::Sexp(Box::new(ParseError::UnexpectedEof), (0, 0))));
 326     }
 327
 328     #[test]
 329     fn test_parse_number() {
 330         assert_eq!(parse_number("1", 0), Done("", Sexp::Int(1, (0, 1))));
 331         assert_eq!(parse_number(" 13", 0), Done("", Sexp::Int(13, (1, 3))));
 332         assert_eq!(parse_number("1.2", 0), Done("", Sexp::Float(1.2, (0, 3))));
 333         assert_eq!(parse_number("\u{3000}4.2", 0), Done("", Sexp::Float(4.2, (0, 3).offset('\u{3000}'.len_utf8()))));
 334         assert_eq!(parse_number("       42 ", 0), Done(" ", Sexp::Int(42, (2, 4))));
 335         assert_eq!(parse_number(" 4.2  ", 0), Done("  ", Sexp::Float(4.2, (1, 4))));
 336         assert_eq!(parse_number("1()", 0), Done("()", Sexp::Int(1, (0, 1))));
 337         assert_eq!(parse_number("3.6()", 0), Done("()", Sexp::Float(3.6, (0, 3))));
 338
 339         assert_eq!(parse_number("", 0), Error(ParseError::Number(Box::new(ParseError::UnexpectedEof), (0, 0))));
 340         assert_eq!(parse_number("123a", 0), Error(ParseError::Number(Box::new(ParseError::Unexpected('a', 3)), (3, 3))));
 341         assert_eq!(parse_number("66.6+", 0), Error(ParseError::Number(Box::new(ParseError::Unexpected('+', 4)), (4, 4))));
 342     }
 343
 344     #[test]
 345     fn test_parse_ident() {
 346         assert_eq!(parse_symbol("+", 0), Done("", Sexp::Sym("+".into(), (0, 1))));
 347         assert_eq!(parse_symbol(" nil?", 0), Done("", Sexp::Sym("nil?".into(), (1, 5))));
 348         assert_eq!(parse_symbol(" ->socket", 0), Done("", Sexp::Sym("->socket".into(), (1, 9))));
 349         assert_eq!(parse_symbol("fib(", 0), Done("(", Sexp::Sym("fib".into(), (0, 3))));
 350         assert_eq!(parse_symbol("foo2", 0), Done("", Sexp::Sym("foo2".into(), (0, 4))));
 351
 352         // We reserve #foo for the implementation to do as it wishes
 353         assert_eq!(parse_symbol("#hi", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('#', 0)), (0, 0))));
 354         // We reserve :foo for keywords
 355         assert_eq!(parse_symbol(":hi", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected(':', 0)), (0, 0))));
 356
 357         assert_eq!(parse_symbol("", 0), Error(ParseError::Symbol(Box::new(ParseError::UnexpectedEof), (0, 0))));
 358         assert_eq!(parse_symbol("0", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('0', 0)), (0, 0))));
 359         assert_eq!(parse_symbol("()", 0), Error(ParseError::Symbol(Box::new(ParseError::Unexpected('(', 0)), (0, 0))));
 360     }
 361
 362     #[test]
 363     fn test_parse_string() {
 364         assert_eq!(parse_string(r#""""#, 0), Done("", Sexp::Str("".into(), (0, 2))));
 365         assert_eq!(parse_string(r#""hello""#, 0), Done("", Sexp::Str("hello".into(), (0, 7))));
 366         assert_eq!(parse_string(r#"  "this is a nice string
 367 with 0123 things in it""#, 0),
 368                    Done("", Sexp::Str("this is a nice string\nwith 0123 things in it".into(), (2, 48))));
 369
 370         assert_eq!(parse_string("", 0), Error(ParseError::String(Box::new(ParseError::UnexpectedEof), (0, 0))));
 371         assert_eq!(parse_string(r#""hi"#, 0), Error(ParseError::String(Box::new(ParseError::UnexpectedEof), (0, 3))));
 372     }
 373
 374     #[test]
 375     fn test_parse_char() {
 376         assert_eq!(parse_character(r#"#\""#, 0), Done("", Sexp::Char('"', (0, 3))));
 377         assert_eq!(parse_character(r#"#\ "#, 0), Done("", Sexp::Char(' ', (0, 3))));
 378         assert_eq!(parse_character(r#"  #\\"#, 0), Done("", Sexp::Char('\\', (2, 5))));
 379
 380         assert_eq!(parse_character("", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (0, 0))));
 381         assert_eq!(parse_character("#", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (1, 1))));
 382         assert_eq!(parse_character("#\\", 0), Error(ParseError::Char(Box::new(ParseError::UnexpectedEof), (2, 2))));
 383         assert_eq!(parse_character("a", 0), Error(ParseError::Char(Box::new(ParseError::Unexpected('a', 0)), (0, 0))));
 384     }
 385 }
 386
 387
 388 // #[cfg(test)]
 389 // #[test]
 390 // fn test_parse_list() {
 391 //     assert_eq!(list("()"), IResult::Done("", vec![]));
 392 //     assert_eq!(list("(1)"), IResult::Done("", vec![Sexp::Int(1)]));
 393 //     assert_eq!(list("  ( 1    2  3 a )"), IResult::Done("", vec![
 394 //         Sexp::Int(1),
 395 //         Sexp::Int(2),
 396 //         Sexp::Int(3),
 397 //         Sexp::Sym("a".into()),
 398 //     ]));
 399 // }
 400
 401 // #[cfg(test)]
 402 // #[test]
 403 // fn test_parse_only_one() {
 404 //     assert!(parse_one("1 2").is_err());
 405 // }
 406
 407 // #[cfg(test)]
 408 // #[test]
 409 // fn test_parse_expression() {
 410 //     assert_eq!(parse_one(r#"
 411 // (def (main)
 412 //   (print (str "say " #\" "Hello, World" #\" " today!")))
 413 // "#),
 414 //                Ok(Sexp::List(vec![
 415 //                    Sexp::Sym("def".into()),
 416 //                    Sexp::List(
 417 //                        vec![Sexp::Sym("main".into())]
 418 //                    ),
 419 //                    Sexp::List(vec![
 420 //                        Sexp::Sym("print".into()),
 421 //                        Sexp::List(vec![
 422 //                            Sexp::Sym("str".into()),
 423 //                            Sexp::Str("say ".into()),
 424 //                            Sexp::Char('"'),
 425 //                            Sexp::Str("Hello, World".into()),
 426 //                            Sexp::Char('"'),
 427 //                            Sexp::Str(" today!".into()),
 428 //                        ])
 429 //                    ])
 430 //                ])));
 431 // }
 432
 433 // #[cfg(test)]
 434 // #[test]
 435 // fn test_parse_multi() {
 436 //     assert_eq!(parse(" 1 2 3 "),
 437 //                Ok(vec![Sexp::Int(1), Sexp::Int(2), Sexp::Int(3)]));
 438 // }