pintos-os.org Git - pspp/blob - rust/src/sack.rs

   1 use float_next_after::NextAfter;
   2 use num::{Bounded, Zero};
   3 use ordered_float::OrderedFloat;
   4 use std::{
   5     collections::{hash_map::Entry, HashMap},
   6     error::Error as StdError,
   7     fmt::{Display, Formatter, Result as FmtResult},
   8     iter::repeat,
   9 };
  10
  11 use crate::endian::{Endian, ToBytes};
  12
  13 pub type Result<T, F = Error> = std::result::Result<T, F>;
  14
  15 #[derive(Debug)]
  16 pub struct Error {
  17     pub file_name: Option<String>,
  18     pub line_number: Option<usize>,
  19     pub token: Option<String>,
  20     pub message: String,
  21 }
  22
  23 impl Error {
  24     fn new(
  25         file_name: Option<&str>,
  26         line_number: Option<usize>,
  27         token: Option<&str>,
  28         message: String,
  29     ) -> Error {
  30         Error {
  31             file_name: file_name.map(String::from),
  32             line_number,
  33             token: token.map(String::from),
  34             message,
  35         }
  36     }
  37 }
  38
  39 impl StdError for Error {}
  40
  41 impl Display for Error {
  42     fn fmt(&self, f: &mut Formatter) -> FmtResult {
  43         match (self.file_name.as_ref(), self.line_number) {
  44             (Some(ref file_name), Some(line_number)) => write!(f, "{file_name}:{line_number}: ")?,
  45             (Some(ref file_name), None) => write!(f, "{file_name}: ")?,
  46             (None, Some(line_number)) => write!(f, "line {line_number}: ")?,
  47             (None, None) => (),
  48         }
  49         if let Some(ref token) = self.token {
  50             write!(f, "at '{token}': ")?;
  51         }
  52         write!(f, "{}", self.message)
  53     }
  54 }
  55
  56 pub fn sack(input: &str, input_file_name: Option<&str>, endian: Endian) -> Result<Vec<u8>> {
  57     let mut symbol_table = HashMap::new();
  58     let output = _sack(input, input_file_name, endian, &mut symbol_table)?;
  59     let output = if !symbol_table.is_empty() {
  60         for (k, v) in symbol_table.iter() {
  61             println!("{k} => {v:?}");
  62         }
  63         for (k, v) in symbol_table.iter() {
  64             if v.is_none() {
  65                 Err(Error::new(
  66                     input_file_name,
  67                     None,
  68                     None,
  69                     format!("label {k} used but never defined"),
  70                 ))?
  71             }
  72         }
  73         _sack(input, input_file_name, endian, &mut symbol_table)?
  74     } else {
  75         output
  76     };
  77     Ok(output)
  78 }
  79
  80 fn _sack(
  81     input: &str,
  82     input_file_name: Option<&str>,
  83     endian: Endian,
  84     symbol_table: &mut HashMap<String, Option<u32>>,
  85 ) -> Result<Vec<u8>> {
  86     let mut lexer = Lexer::new(input, input_file_name, endian)?;
  87     let mut output = Vec::new();
  88     while parse_data_item(&mut lexer, &mut output, symbol_table)? {}
  89     Ok(output)
  90 }
  91
  92 fn parse_data_item(
  93     lexer: &mut Lexer,
  94     output: &mut Vec<u8>,
  95     symbol_table: &mut HashMap<String, Option<u32>>,
  96 ) -> Result<bool> {
  97     if lexer.token.is_none() {
  98         return Ok(false);
  99     };
 100
 101     let initial_len = output.len();
 102     match lexer.take()? {
 103         Token::Integer(integer) => {
 104             let Ok(integer): Result<i32, _> = integer.try_into() else {
 105                 Err(lexer.error(format!(
 106                     "{integer} is not in the valid range [{},{}]",
 107                     u32::min_value(),
 108                     u32::max_value()
 109                 )))?
 110             };
 111             output.extend_from_slice(&lexer.endian.to_bytes(integer))},
 112         Token::Float(float) => output.extend_from_slice(&lexer.endian.to_bytes(float.0)),
 113         Token::PcSysmis => {
 114             output.extend_from_slice(&[0xf5, 0x1e, 0x26, 0x02, 0x8a, 0x8c, 0xed, 0xff])
 115         }
 116         Token::I8 => put_integers::<u8, 1>(lexer, "i8", output)?,
 117         Token::I16 => put_integers::<u16, 2>(lexer, "i16", output)?,
 118         Token::I64 => put_integers::<i64, 8>(lexer, "i64", output)?,
 119         Token::String(string) => output.extend_from_slice(string.as_bytes()),
 120         Token::S(size) => {
 121             let Some((Token::String(ref string), _)) = lexer.token else {
 122                 Err(lexer.error(format!("string expected after 's{size}'")))?
 123             };
 124             let len = string.len();
 125             if len > size {
 126                 Err(lexer.error(format!(
 127                     "{len}-byte string is longer than pad length {size}"
 128                 )))?
 129             }
 130             output.extend_from_slice(string.as_bytes());
 131             output.extend(repeat(b' ').take(size - len));
 132             lexer.get()?;
 133         }
 134         Token::LParen => {
 135             while !matches!(lexer.token, Some((Token::RParen, _))) {
 136                 parse_data_item(lexer, output, symbol_table)?;
 137             }
 138             lexer.get()?;
 139         }
 140         Token::Count => put_counted_items::<u32, 4>(lexer, "COUNT", output, symbol_table)?,
 141         Token::Count8 => put_counted_items::<u8, 1>(lexer, "COUNT8", output, symbol_table)?,
 142         Token::Hex => {
 143             let Some((Token::String(ref string), _)) = lexer.token else {
 144                 Err(lexer.error(String::from("string expected after 'hex'")))?
 145             };
 146             let mut i = string.chars();
 147             loop {
 148                 let Some(c0) = i.next() else { return Ok(true) };
 149                 let Some(c1) = i.next() else {
 150                     Err(lexer.error(String::from("hex string has odd number of characters")))?
 151                 };
 152                 let (Some(digit0), Some(digit1)) = (c0.to_digit(16), c1.to_digit(16)) else {
 153                     Err(lexer.error(String::from("invalid digit in hex string")))?
 154                 };
 155                 let byte = digit0 * 16 + digit1;
 156                 output.push(byte as u8);
 157             }
 158         }
 159         Token::Label(name) => {
 160             println!("define {name}");
 161             let value = output.len() as u32;
 162             match symbol_table.entry(name.clone()) {
 163                 Entry::Vacant(v) => {
 164                     v.insert(Some(value));
 165                 }
 166                 Entry::Occupied(mut o) => {
 167                     match o.get() {
 168                         Some(v) => {
 169                             if *v != value {
 170                                 Err(lexer.error(format!("{name}: can't redefine label for offset {:#x} with offset {:#x}", *v, value)))?
 171                             }
 172                         }
 173                         None => drop(o.insert(Some(value))),
 174                     }
 175                 }
 176             };
 177             return Ok(true);
 178         }
 179         Token::At(name) => {
 180             let mut value = symbol_table
 181                 .entry(name.clone())
 182                 .or_insert(None)
 183                 .unwrap_or(0);
 184             println!("{name} has value {value}");
 185             loop {
 186                 let plus = match lexer.token {
 187                     Some((Token::Plus, _)) => true,
 188                     Some((Token::Minus, _)) => false,
 189                     _ => break,
 190                 };
 191                 lexer.get()?;
 192
 193                 let operand = match lexer.token {
 194                     Some((Token::At(ref name), _)) => if let Some(value) = symbol_table.get(name) {
 195                         *value
 196                     } else {
 197                         symbol_table.insert(name.clone(), None);
 198                         None
 199                     }
 200                     .unwrap_or(0),
 201                     Some((Token::Integer(integer), _)) => integer
 202                         .try_into()
 203                         .map_err(|msg| lexer.error(format!("bad offset literal ({msg})")))?,
 204                     _ => Err(lexer.error(String::from("expecting @label or integer literal")))?,
 205                 };
 206                 lexer.get()?;
 207
 208                 value = if plus {
 209                     value.checked_add(operand)
 210                 } else {
 211                     value.checked_sub(operand)
 212                 }
 213                 .ok_or_else(|| lexer.error(String::from("overflow in offset arithmetic")))?;
 214             }
 215             output.extend_from_slice(&lexer.endian.to_bytes(value));
 216         }
 217         _ => (),
 218     };
 219     if let Some((Token::Asterisk, _)) = lexer.token {
 220         lexer.get()?;
 221         let Token::Integer(count) = lexer.take()? else {
 222             Err(lexer.error(String::from("positive integer expected after '*'")))?
 223         };
 224         if count < 1 {
 225             Err(lexer.error(String::from("positive integer expected after '*'")))?
 226         };
 227         let final_len = output.len();
 228         for _ in 1..count {
 229             output.extend_from_within(initial_len..final_len);
 230         }
 231     }
 232     match lexer.token {
 233         Some((Token::Semicolon, _)) => {
 234             lexer.get()?;
 235         }
 236         Some((Token::RParen, _)) => (),
 237         _ => Err(lexer.error(String::from("';' expected")))?,
 238     }
 239     Ok(true)
 240 }
 241
 242 fn put_counted_items<T, const N: usize>(
 243     lexer: &mut Lexer,
 244     name: &str,
 245     output: &mut Vec<u8>,
 246     symbol_table: &mut HashMap<String, Option<u32>>,
 247 ) -> Result<()>
 248 where
 249     T: Zero + TryFrom<usize>,
 250     Endian: ToBytes<T, N>,
 251 {
 252     let old_size = output.len();
 253     output.extend_from_slice(&lexer.endian.to_bytes(T::zero()));
 254     let start = output.len();
 255     if !matches!(lexer.token, Some((Token::LParen, _))) {
 256         Err(lexer.error(format!("'(' expected after '{name}'")))?
 257     }
 258     lexer.get()?;
 259     while !matches!(lexer.token, Some((Token::RParen, _))) {
 260         parse_data_item(lexer, output, symbol_table)?;
 261     }
 262     lexer.get()?;
 263     let delta = output.len() - start;
 264     let Ok(delta): Result<T, _> = delta.try_into() else {
 265         Err(lexer.error(format!("{delta} bytes is too much for '{name}'")))?
 266     };
 267     let dest = &mut output[old_size..old_size + N];
 268     dest.copy_from_slice(&lexer.endian.to_bytes(delta));
 269     Ok(())
 270 }
 271
 272 fn put_integers<T, const N: usize>(
 273     lexer: &mut Lexer,
 274     name: &str,
 275     output: &mut Vec<u8>,
 276 ) -> Result<()>
 277 where
 278     T: Bounded + Display + TryFrom<i64> + Copy,
 279     Endian: ToBytes<T, N>,
 280 {
 281     println!("put_integers {:?}", lexer.token);
 282     let mut n = 0;
 283     while let Some(integer) = lexer.take_if(|t| match t {
 284         Token::Integer(integer) => Some(*integer),
 285         _ => None,
 286     })? {
 287         println!("got integer {integer}");
 288         let Ok(integer) = integer.try_into() else {
 289             Err(lexer.error(format!(
 290                 "{integer} is not in the valid range [{},{}]",
 291                 T::min_value(),
 292                 T::max_value()
 293             )))?
 294         };
 295         output.extend_from_slice(&lexer.endian.to_bytes(integer));
 296         n += 1;
 297     }
 298     println!("put_integers {:?} {n}", lexer.token);
 299     if n == 0 {
 300         Err(lexer.error(format!("integer expected after '{name}'")))?
 301     }
 302     Ok(())
 303 }
 304
 305 #[derive(PartialEq, Eq, Clone, Debug)]
 306 enum Token {
 307     Integer(i64),
 308     Float(OrderedFloat<f64>),
 309     PcSysmis,
 310     String(String),
 311     Semicolon,
 312     Asterisk,
 313     LParen,
 314     RParen,
 315     I8,
 316     I16,
 317     I64,
 318     S(usize),
 319     Count,
 320     Count8,
 321     Hex,
 322     Label(String),
 323     At(String),
 324     Minus,
 325     Plus,
 326 }
 327
 328 struct Lexer<'a> {
 329     input: &'a str,
 330     token: Option<(Token, &'a str)>,
 331     input_file_name: Option<&'a str>,
 332     line_number: usize,
 333     endian: Endian,
 334 }
 335
 336 fn skip_comments(mut s: &str) -> (&str, usize) {
 337     let mut n_newlines = 0;
 338     let s = loop {
 339         s = s.trim_start_matches([' ', '\t', '\r', '<', '>']);
 340         if let Some(remainder) = s.strip_prefix('#') {
 341             let Some((_, remainder)) = remainder.split_once('\n') else {
 342                 break "";
 343             };
 344             s = remainder;
 345             n_newlines += 1;
 346         } else if let Some(remainder) = s.strip_prefix('\n') {
 347             s = remainder;
 348             n_newlines += 1;
 349         } else {
 350             break s;
 351         }
 352     };
 353     (s, n_newlines)
 354 }
 355
 356 impl<'a> Lexer<'a> {
 357     fn new(input: &'a str, input_file_name: Option<&'a str>, endian: Endian) -> Result<Lexer<'a>> {
 358         let mut lexer = Lexer {
 359             input,
 360             token: None,
 361             input_file_name,
 362             line_number: 1,
 363             endian,
 364         };
 365         lexer.token = lexer.next()?;
 366         Ok(lexer)
 367     }
 368     fn error(&self, message: String) -> Error {
 369         let repr = self.token.as_ref().map(|(_, repr)| *repr);
 370         Error::new(self.input_file_name, Some(self.line_number), repr, message)
 371     }
 372     fn take(&mut self) -> Result<Token> {
 373         let Some(token) = self.token.take() else {
 374             Err(self.error(String::from("unexpected end of input")))?
 375         };
 376         self.token = self.next()?;
 377         Ok(token.0)
 378     }
 379     fn take_if<F, T>(&mut self, condition: F) -> Result<Option<T>>
 380     where
 381         F: FnOnce(&Token) -> Option<T>,
 382     {
 383         let Some(ref token) = self.token else {
 384             return Ok(None);
 385         };
 386         match condition(&token.0) {
 387             Some(value) => {
 388                 self.token = self.next()?;
 389                 Ok(Some(value))
 390             }
 391             None => Ok(None),
 392         }
 393     }
 394     fn get(&mut self) -> Result<Option<&Token>> {
 395         if self.token.is_none() {
 396             Err(self.error(String::from("unexpected end of input")))?
 397         } else {
 398             self.token = self.next()?;
 399             match self.token {
 400                 Some((ref token, _)) => Ok(Some(token)),
 401                 None => Ok(None),
 402             }
 403         }
 404     }
 405
 406     fn next(&mut self) -> Result<Option<(Token, &'a str)>> {
 407         // Get the first character of the token, skipping past white space and
 408         // comments.
 409         let (s, n_newlines) = skip_comments(self.input);
 410         self.line_number += n_newlines;
 411         self.input = s;
 412
 413         let start = s;
 414         let mut iter = s.chars();
 415         let Some(c) = iter.next() else {
 416             return Ok(None);
 417         };
 418         let (token, rest) = match c {
 419             c if c.is_ascii_digit() || c == '-' => {
 420                 let len = s
 421                     .find(|c: char| {
 422                         !(c.is_ascii_digit() || c.is_alphabetic() || c == '.' || c == '-')
 423                     })
 424                     .unwrap_or_else(|| s.len());
 425                 let (number, rest) = s.split_at(len);
 426                 let token = if number == "-" {
 427                     Token::Minus
 428                 } else if let Some(digits) = number.strip_prefix("0x") {
 429                     Token::Integer(i64::from_str_radix(digits, 16).map_err(|msg| {
 430                         self.error(format!("bad integer literal '{number}' ({msg})"))
 431                     })?)
 432                 } else if !number.contains('.') {
 433                     Token::Integer(number.parse().map_err(|msg| {
 434                         self.error(format!("bad integer literal '{number}' ({msg})"))
 435                     })?)
 436                 } else {
 437                     Token::Float(number.parse().map_err(|msg| {
 438                         self.error(format!("bad float literal '{number}' ({msg})"))
 439                     })?)
 440                 };
 441                 (token, rest)
 442             }
 443             '"' => {
 444                 let s = iter.as_str();
 445                 let Some(len) = s.find(['\n', '"']) else {
 446                     Err(self.error(String::from("end-of-file inside string")))?
 447                 };
 448                 let (string, rest) = s.split_at(len);
 449                 let Some(rest) = rest.strip_prefix('"') else {
 450                     Err(self.error(format!("new-line inside string ({string}...{rest})")))?
 451                 };
 452                 (Token::String(string.into()), rest)
 453             }
 454             ';' => (Token::Semicolon, iter.as_str()),
 455             '*' => (Token::Asterisk, iter.as_str()),
 456             '+' => (Token::Plus, iter.as_str()),
 457             '(' => (Token::LParen, iter.as_str()),
 458             ')' => (Token::RParen, iter.as_str()),
 459             c if c.is_alphabetic() || c == '@' || c == '_' => {
 460                 let len = s
 461                     .find(|c: char| {
 462                         !(c.is_ascii_digit()
 463                             || c.is_alphabetic()
 464                             || c == '@'
 465                             || c == '.'
 466                             || c == '_')
 467                     })
 468                     .unwrap_or_else(|| s.len());
 469                 let (s, rest) = s.split_at(len);
 470                 if let Some(rest) = rest.strip_prefix(':') {
 471                     (Token::Label(s.into()), rest)
 472                 } else if let Some(name) = s.strip_prefix('@') {
 473                     (Token::At(name.into()), rest)
 474                 } else if let Some(count) = s.strip_prefix('s') {
 475                     let token =
 476                         Token::S(count.parse().map_err(|msg| {
 477                             self.error(format!("bad counted string '{s}' ({msg})"))
 478                         })?);
 479                     (token, rest)
 480                 } else {
 481                     let token = match &s[..] {
 482                         "i8" => Token::I8,
 483                         "i16" => Token::I16,
 484                         "i64" => Token::I64,
 485                         "SYSMIS" => Token::Float(OrderedFloat(-f64::MAX)),
 486                         "PCSYSMIS" => Token::PcSysmis,
 487                         "LOWEST" => Token::Float((-f64::MAX).next_after(0.0).into()),
 488                         "HIGHEST" => Token::Float(f64::MAX.into()),
 489                         "ENDIAN" => Token::Integer(if self.endian == Endian::Big { 1 } else { 2 }),
 490                         "COUNT" => Token::Count,
 491                         "COUNT8" => Token::Count8,
 492                         "hex" => Token::Hex,
 493                         _ => Err(self.error(format!("invalid token '{s}'")))?,
 494                     };
 495                     (token, rest)
 496                 }
 497             }
 498             _ => Err(self.error(format!("invalid input byte '{c}'")))?,
 499         };
 500         self.input = rest;
 501         let repr = &start[..start.len() - rest.len()];
 502         println!("{token:?} {repr}");
 503         Ok(Some((token, repr)))
 504     }
 505 }
 506
 507 #[cfg(test)]
 508 mod test {
 509     use crate::endian::Endian;
 510     use crate::sack::sack;
 511     use anyhow::Result;
 512     use hexplay::HexView;
 513
 514     #[test]
 515     fn basic_sack() -> Result<()> {
 516         let input = r#"
 517 "$FL2"; s60 "$(#) SPSS DATA FILE PSPP synthetic test file";
 518 2; # Layout code
 519 28; # Nominal case size
 520 0; # Not compressed
 521 0; # Not weighted
 522 1; # 1 case.
 523 100.0; # Bias.
 524 "01 Jan 11"; "20:53:52";
 525 "PSPP synthetic test file: "; i8 244; i8 245; i8 246; i8 248; s34 "";
 526 i8 0 *3;
 527 "#;
 528         let output = sack(input, None, Endian::Big)?;
 529         HexView::new(&output).print()?;
 530         Ok(())
 531     }
 532
 533     #[test]
 534     fn pcp_sack() -> Result<()> {
 535         let input = r#"
 536 # File header.
 537 2; 0;
 538 @MAIN; @MAIN_END - @MAIN;
 539 @VARS; @VARS_END - @VARS;
 540 @LABELS; @LABELS_END - @LABELS;
 541 @DATA; @DATA_END - @DATA;
 542 (0; 0) * 11;
 543 i8 0 * 128;
 544
 545 MAIN:
 546     i16 1;         # Fixed.
 547     s62 "PCSPSS PSPP synthetic test product";
 548     PCSYSMIS;
 549     0; 0; i16 1;   # Fixed.
 550     i16 0;
 551     i16 15;
 552     1;
 553     i16 0;         # Fixed.
 554     1;
 555     s8 "11/28/14";
 556     s8 "15:11:00";
 557     s64 "PSPP synthetic test file";
 558 MAIN_END:
 559
 560 VARS:
 561     0; 0; 0; 0x050800; s8 "$CASENUM"; PCSYSMIS;
 562     0; 0; 0; 0x010800; s8 "$DATE"; PCSYSMIS;
 563     0; 0; 0; 0x050802; s8 "$WEIGHT"; PCSYSMIS;
 564
 565     # Numeric variable, no label or missing values.
 566     0; 0; 0; 0x050800; s8 "NUM1"; PCSYSMIS;
 567
 568     # Numeric variable, variable label.
 569     0; 0; @NUM2_LABEL - @LABELS_OFS; 0x050800; s8 "NUM2"; PCSYSMIS;
 570
 571     # Numeric variable with missing value.
 572     0; 0; 0; 0x050800; s8 "NUM3"; 1.0;
 573
 574     # Numeric variable, variable label and missing value.
 575     0; 0; @NUM4_LABEL - @LABELS_OFS; 0x050800; s8 "NUM4"; 2.0;
 576
 577     # String variable, no label or missing values.
 578     0; 0; 0; 0x010800; s8 "STR1"; PCSYSMIS;
 579
 580     # String variable, variable label.
 581     0; 0; @STR2_LABEL - @LABELS_OFS; 0x010400; s8 "STR2"; PCSYSMIS;
 582
 583     # String variable with missing value.
 584     0; 0; 0; 0x010500; s8 "STR3"; s8 "MISS";
 585
 586     # String variable, variable label and missing value.
 587     0; 0; @STR4_LABEL - @LABELS_OFS; 0x010100; s8 "STR4"; s8 "OTHR";
 588
 589     # Long string variable
 590     0; 0; 0; 0x010b00; s8 "STR5"; PCSYSMIS;
 591     0 * 8;
 592
 593     # Long string variable with variable label
 594     0; 0; @STR6_LABEL - @LABELS_OFS; 0x010b00; s8 "STR6"; PCSYSMIS;
 595     0 * 8;
 596 VARS_END:
 597
 598 LABELS:
 599     3; i8 0 0 0; LABELS_OFS: i8 0;
 600     NUM2_LABEL: COUNT8("Numeric variable 2's label");
 601     NUM4_LABEL: COUNT8("Another numeric variable label");
 602     STR2_LABEL: COUNT8("STR2's variable label");
 603     STR4_LABEL: COUNT8("STR4's variable label");
 604     STR6_LABEL: COUNT8("Another string variable's label");
 605 LABELS_END:
 606
 607 DATA:
 608     0.0; "11/28/14"; 1.0;
 609     0.0; 1.0; 2.0; PCSYSMIS; s8 "abcdefgh"; s8 "ijkl"; s8 "mnopq"; s8 "r";
 610     s16 "stuvwxyzAB"; s16 "CDEFGHIJKLM";
 611 DATA_END:
 612 "#;
 613         let output = sack(input, None, Endian::Big)?;
 614         HexView::new(&output).print()?;
 615         Ok(())
 616     }
 617 }