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

   1 use anyhow::{anyhow, Result};
   2 use float_next_after::NextAfter;
   3 use num::{Bounded, Zero};
   4 use ordered_float::OrderedFloat;
   5 use std::{
   6     collections::{hash_map::Entry, HashMap},
   7     fmt::Display,
   8     iter::{repeat, Peekable},
   9     str::Chars,
  10 };
  11
  12 use crate::endian::{Endian, ToBytes};
  13
  14 pub fn sack(input: &str, endian: Endian) -> Result<Vec<u8>> {
  15     let mut lexer = Lexer::new(input, endian)?;
  16     while let Some(ref token) = lexer.token {
  17         println!("{token:?}");
  18         lexer.get()?;
  19     }
  20
  21     let mut symbol_table = HashMap::new();
  22     let output = _sack(input, endian, &mut symbol_table)?;
  23     let output = if !symbol_table.is_empty() {
  24         for (k, v) in symbol_table.iter() {
  25             if v.is_none() {
  26                 return Err(anyhow!("label {k} used but never defined"));
  27             }
  28         }
  29         _sack(input, endian, &mut symbol_table)?
  30     } else {
  31         output
  32     };
  33     Ok(output)
  34 }
  35
  36 fn _sack(
  37     input: &str,
  38     endian: Endian,
  39     symbol_table: &mut HashMap<String, Option<u32>>,
  40 ) -> Result<Vec<u8>> {
  41     let mut lexer = Lexer::new(input, endian)?;
  42     let mut output = Vec::new();
  43     while parse_data_item(&mut lexer, &mut output, symbol_table)? {}
  44     Ok(output)
  45 }
  46
  47 fn parse_data_item(
  48     lexer: &mut Lexer,
  49     output: &mut Vec<u8>,
  50     symbol_table: &mut HashMap<String, Option<u32>>,
  51 ) -> Result<bool> {
  52     if lexer.token.is_none() {
  53         return Ok(false);
  54     };
  55
  56     let initial_len = output.len();
  57     match lexer.take()? {
  58         Token::Integer(integer) => output.extend_from_slice(&lexer.endian.to_bytes(integer)),
  59         Token::Float(float) => output.extend_from_slice(&lexer.endian.to_bytes(float.0)),
  60         Token::PcSysmis => {
  61             output.extend_from_slice(&[0xf5, 0x1e, 0x26, 0x02, 0x8a, 0x8c, 0xed, 0xff])
  62         }
  63         Token::I8 => put_integers::<u8, 1>(lexer, "i8", output)?,
  64         Token::I16 => put_integers::<u16, 2>(lexer, "i16", output)?,
  65         Token::I64 => put_integers::<i64, 8>(lexer, "i64", output)?,
  66         Token::String(string) => output.extend_from_slice(string.as_bytes()),
  67         Token::S(size) => {
  68             let Some(Token::String(ref string)) = lexer.token else {
  69                 return Err(anyhow!("string expected after 's{size}'"));
  70             };
  71             let len = string.len();
  72             if len > size {
  73                 return Err(anyhow!(
  74                     "{len}-byte string is longer than pad length {size}"
  75                 ));
  76             }
  77             output.extend_from_slice(string.as_bytes());
  78             output.extend(repeat(b' ').take(size - len));
  79             lexer.get()?;
  80         }
  81         Token::LParen => {
  82             while lexer.token != Some(Token::RParen) {
  83                 parse_data_item(lexer, output, symbol_table)?;
  84             }
  85             lexer.get()?;
  86         }
  87         Token::Count => put_counted_items::<u32, 4>(lexer, "COUNT", output, symbol_table)?,
  88         Token::Count8 => put_counted_items::<u8, 1>(lexer, "COUNT8", output, symbol_table)?,
  89         Token::Hex => {
  90             let Some(Token::String(ref string)) = lexer.token else {
  91                 return Err(anyhow!("string expected after 'hex'"));
  92             };
  93             let mut i = string.chars();
  94             loop {
  95                 let Some(c0) = i.next() else { return Ok(true) };
  96                 let Some(c1) = i.next() else {
  97                     return Err(anyhow!("hex string has odd number of characters"));
  98                 };
  99                 let (Some(digit0), Some(digit1)) = (c0.to_digit(16), c1.to_digit(16)) else {
 100                     return Err(anyhow!("invalid digit in hex string"));
 101                 };
 102                 let byte = digit0 * 16 + digit1;
 103                 output.push(byte as u8);
 104             }
 105         }
 106         Token::Label(name) => {
 107             let value = output.len() as u32;
 108             match symbol_table.entry(name) {
 109                 Entry::Vacant(v) => {
 110                     v.insert(Some(value));
 111                 }
 112                 Entry::Occupied(o) => {
 113                     if let Some(v) = o.get() {
 114                         if *v != value {
 115                             return Err(anyhow!("syntax error"));
 116                         }
 117                     }
 118                 }
 119             };
 120         }
 121         Token::At(name) => {
 122             let mut value = symbol_table.entry(name).or_insert(None).unwrap_or(0);
 123             lexer.get()?;
 124             loop {
 125                 let plus = match lexer.token {
 126                     Some(Token::Plus) => true,
 127                     Some(Token::Minus) => false,
 128                     _ => break,
 129                 };
 130                 lexer.get()?;
 131
 132                 let operand = match lexer.token {
 133                     Some(Token::At(ref name)) => if let Some(value) = symbol_table.get(name) {
 134                         *value
 135                     } else {
 136                         symbol_table.insert(name.clone(), None);
 137                         None
 138                     }
 139                     .unwrap_or(0),
 140                     Some(Token::Integer(integer)) => integer
 141                         .try_into()
 142                         .map_err(|msg| anyhow!("bad offset literal ({msg})"))?,
 143                     _ => return Err(anyhow!("expecting @label or integer literal")),
 144                 };
 145                 lexer.get()?;
 146
 147                 value = if plus {
 148                     value.checked_add(operand)
 149                 } else {
 150                     value.checked_sub(operand)
 151                 }
 152                 .ok_or_else(|| anyhow!("overflow in offset arithmetic"))?;
 153             }
 154             output.extend_from_slice(&lexer.endian.to_bytes(value));
 155         }
 156         _ => (),
 157     };
 158     if lexer.token == Some(Token::Asterisk) {
 159         lexer.get()?;
 160         let Token::Integer(count) = lexer.take()? else {
 161             return Err(anyhow!("positive integer expected after '*'"));
 162         };
 163         if count < 1 {
 164             return Err(anyhow!("positive integer expected after '*'"));
 165         };
 166         let final_len = output.len();
 167         for _ in 1..count {
 168             output.extend_from_within(initial_len..final_len);
 169         }
 170     }
 171     match lexer.token {
 172         Some(Token::Semicolon) => {
 173             lexer.get()?;
 174         }
 175         Some(Token::RParen) => (),
 176         _ => return Err(anyhow!("';' expected")),
 177     }
 178     Ok(true)
 179 }
 180
 181 fn put_counted_items<T, const N: usize>(
 182     lexer: &mut Lexer,
 183     name: &str,
 184     output: &mut Vec<u8>,
 185     symbol_table: &mut HashMap<String, Option<u32>>,
 186 ) -> Result<()>
 187 where
 188     T: Zero + TryFrom<usize>,
 189     Endian: ToBytes<T, N>,
 190 {
 191     let old_size = output.len();
 192     output.extend_from_slice(&lexer.endian.to_bytes(T::zero()));
 193     if lexer.token != Some(Token::LParen) {
 194         return Err(anyhow!("'(' expected after '{name}'"));
 195     }
 196     lexer.get()?;
 197     while lexer.token != Some(Token::RParen) {
 198         parse_data_item(lexer, output, symbol_table)?;
 199     }
 200     lexer.get()?;
 201     let delta = output.len() - old_size;
 202     let Ok(delta): Result<T, _> = delta.try_into() else {
 203         return Err(anyhow!("{delta} bytes is too much for '{name}'"));
 204     };
 205     let dest = &mut output[old_size..old_size + N];
 206     dest.copy_from_slice(&lexer.endian.to_bytes(delta));
 207     Ok(())
 208 }
 209
 210 fn put_integers<T, const N: usize>(
 211     lexer: &mut Lexer,
 212     name: &str,
 213     output: &mut Vec<u8>,
 214 ) -> Result<()>
 215 where
 216     T: Bounded + Display + TryFrom<i64> + Copy,
 217     Endian: ToBytes<T, N>,
 218 {
 219     let mut n = 0;
 220     while let Some(integer) = lexer.take_if(|t| match t {
 221         Token::Integer(integer) => Some(*integer),
 222         _ => None,
 223     })? {
 224         let Ok(integer) = integer.try_into() else {
 225             return Err(anyhow!(
 226                 "{integer} is not in the valid range [{},{}]",
 227                 T::min_value(),
 228                 T::max_value()
 229             ));
 230         };
 231         output.extend_from_slice(&lexer.endian.to_bytes(integer));
 232         n += 1;
 233     }
 234     if n == 0 {
 235         return Err(anyhow!("integer expected after '{name}'"));
 236     }
 237     Ok(())
 238 }
 239
 240 #[derive(PartialEq, Eq, Clone, Debug)]
 241 enum Token {
 242     Integer(i64),
 243     Float(OrderedFloat<f64>),
 244     PcSysmis,
 245     String(String),
 246     Semicolon,
 247     Asterisk,
 248     LParen,
 249     RParen,
 250     I8,
 251     I16,
 252     I64,
 253     S(usize),
 254     Count,
 255     Count8,
 256     Hex,
 257     Label(String),
 258     At(String),
 259     Minus,
 260     Plus,
 261 }
 262
 263 struct Lexer<'a> {
 264     iter: Peekable<Chars<'a>>,
 265     token: Option<Token>,
 266     line_number: usize,
 267     endian: Endian,
 268 }
 269
 270 impl<'a> Lexer<'a> {
 271     fn new(input: &'a str, endian: Endian) -> Result<Lexer<'a>> {
 272         let mut lexer = Lexer {
 273             iter: input.chars().peekable(),
 274             token: None,
 275             line_number: 1,
 276             endian,
 277         };
 278         lexer.token = lexer.next()?;
 279         Ok(lexer)
 280     }
 281     fn take(&mut self) -> Result<Token> {
 282         let Some(token) = self.token.take() else {
 283             return Err(anyhow!("unexpected end of input"));
 284         };
 285         self.token = self.next()?;
 286         Ok(token)
 287     }
 288     fn take_if<F, T>(&mut self, condition: F) -> Result<Option<T>>
 289     where
 290         F: FnOnce(&Token) -> Option<T>,
 291     {
 292         let Some(ref token) = self.token else {
 293             return Ok(None);
 294         };
 295         match condition(token) {
 296             Some(value) => {
 297                 self.token = self.next()?;
 298                 Ok(Some(value))
 299             }
 300             None => Ok(None),
 301         }
 302     }
 303     fn get(&mut self) -> Result<Option<&Token>> {
 304         if self.token.is_none() {
 305             Err(anyhow!("unexpected end of input"))
 306         } else {
 307             self.token = self.next()?;
 308             Ok((&self.token).into())
 309         }
 310     }
 311
 312     fn next(&mut self) -> Result<Option<Token>> {
 313         // Get the first character of the token, skipping past white space and
 314         // comments.
 315         let c = loop {
 316             let Some(c) = self.iter.next() else {
 317                 return Ok(None);
 318             };
 319             let c = if c == '#' {
 320                 loop {
 321                     match self.iter.next() {
 322                         None => return Ok(None),
 323                         Some('\n') => break,
 324                         _ => (),
 325                     }
 326                 }
 327                 '\n'
 328             } else {
 329                 c
 330             };
 331             if c == '\n' {
 332                 self.line_number += 1
 333             } else if !c.is_whitespace() && c != '<' && c != '>' {
 334                 break c;
 335             }
 336         };
 337
 338         let token = match c {
 339             c if c.is_ascii_digit() || c == '-' => {
 340                 let mut s = String::from(c);
 341                 while let Some(c) = self
 342                     .iter
 343                     .next_if(|&c| c.is_ascii_digit() || c.is_alphabetic() || c == '.')
 344                 {
 345                     s.push(c);
 346                 }
 347
 348                 if s == "-" {
 349                     Token::Minus
 350                 } else if !s.contains('.') {
 351                     Token::Integer(
 352                         s.parse()
 353                             .map_err(|msg| anyhow!("bad integer literal '{s}' ({msg})"))?,
 354                     )
 355                 } else {
 356                     Token::Float(
 357                         s.parse()
 358                             .map_err(|msg| anyhow!("bad float literal '{s}' ({msg})"))?,
 359                     )
 360                 }
 361             }
 362             '"' => {
 363                 let mut s = String::new();
 364                 loop {
 365                     match self.iter.next() {
 366                         None => return Err(anyhow!("end-of-file inside string")),
 367                         Some('\n') => return Err(anyhow!("new-line inside string")),
 368                         Some('"') => break,
 369                         Some(c) => s.push(c),
 370                     }
 371                 }
 372                 Token::String(s)
 373             }
 374             ';' => Token::Semicolon,
 375             '*' => Token::Asterisk,
 376             '+' => Token::Plus,
 377             '(' => Token::LParen,
 378             ')' => Token::RParen,
 379             c if c.is_alphabetic() || c == '@' || c == '_' => {
 380                 let mut s = String::from(c);
 381                 while let Some(c) = self
 382                     .iter
 383                     .next_if(|&c| c.is_ascii_digit() || c.is_alphabetic() || c == '.' || c == '_')
 384                 {
 385                     s.push(c);
 386                 }
 387                 if self.iter.next_if_eq(&':').is_some() {
 388                     Token::Label(s)
 389                 } else if s.starts_with('@') {
 390                     Token::At(s)
 391                 } else if let Some(count) = s.strip_prefix('s') {
 392                     Token::S(
 393                         count
 394                             .parse()
 395                             .map_err(|msg| anyhow!("bad counted string '{s}' ({msg})"))?,
 396                     )
 397                 } else {
 398                     match &s[..] {
 399                         "i8" => Token::I8,
 400                         "i16" => Token::I16,
 401                         "i64" => Token::I64,
 402                         "SYSMIS" => Token::Float(OrderedFloat(-f64::MAX)),
 403                         "PCSYSMIS" => Token::PcSysmis,
 404                         "LOWEST" => Token::Float((-f64::MAX).next_after(0.0).into()),
 405                         "HIGHEST" => Token::Float(f64::MAX.into()),
 406                         "ENDIAN" => Token::Integer(if self.endian == Endian::Big { 1 } else { 2 }),
 407                         "COUNT" => Token::Count,
 408                         "COUNT8" => Token::Count8,
 409                         "hex" => Token::Hex,
 410                         _ => return Err(anyhow!("invalid token '{s}'")),
 411                     }
 412                 }
 413             }
 414             _ => return Err(anyhow!("invalid input byte '{c}'")),
 415         };
 416         Ok(Some(token))
 417     }
 418 }
 419
 420 #[cfg(test)]
 421 mod test {
 422     use crate::endian::Endian;
 423     use crate::sack::sack;
 424     use anyhow::Result;
 425     use hexplay::HexView;
 426
 427     #[test]
 428     fn basic_sack() -> Result<()> {
 429         let input = r#"
 430 "$FL2"; s60 "$(#) SPSS DATA FILE PSPP synthetic test file";
 431 2; # Layout code
 432 28; # Nominal case size
 433 0; # Not compressed
 434 0; # Not weighted
 435 1; # 1 case.
 436 100.0; # Bias.
 437 "01 Jan 11"; "20:53:52";
 438 "PSPP synthetic test file: "; i8 244; i8 245; i8 246; i8 248; s34 "";
 439 i8 0 *3;
 440 "#;
 441         let output = sack(input, Endian::Big)?;
 442         HexView::new(&output).print()?;
 443         Ok(())
 444     }
 445 }