/* OpenTally: Open-source election vote counting * Copyright © 2021–2022 Lee Yingtong Li (RunasSudo) * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Affero General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Affero General Public License for more details. * * You should have received a copy of the GNU Affero General Public License * along with this program. If not, see . */ use crate::election::{Ballot, Candidate, Election}; use crate::numbers::Number; #[cfg(not(target_arch = "wasm32"))] use utf8_chars::BufReadCharsExt; use std::fmt; use std::iter::Peekable; #[cfg(not(target_arch = "wasm32"))] use std::fs::File; #[cfg(not(target_arch = "wasm32"))] use std::io::BufReader; #[cfg(not(target_arch = "wasm32"))] use std::path::Path; /// Utility for parsing a BLT file pub struct BLTParser> { /// The peekable iterator of chars representing the BLT file chars: Peekable, /// Temporary buffer for parsing ballot values ballot_value_buf: String, /// Whether the current ballot has equal preferences ballot_has_equal_rankings: bool, /// Current line number line_no: u32, /// Current column number col_no: u32, /// Number of candidates num_candidates: usize, /// Parsed [Election] election: Election, } /// An error when parsing a BLT file pub enum ParseError { /// Unexpected character Unexpected(u32, u32, char), /// Unexpected character, expected ... Expected(u32, u32, char, &'static str), } impl fmt::Display for ParseError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { ParseError::Unexpected(line_no, col_no, char) => { f.write_fmt(format_args!("Line {} col {}, unexpected '{}'", line_no, col_no, char))?; } ParseError::Expected(line_no, col_no, char, expected) => { f.write_fmt(format_args!("Line {} col {}, unexpected '{}', expected {}", line_no, col_no, char, expected))?; } } return Ok(()); } } impl fmt::Debug for ParseError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { return fmt::Display::fmt(self, f); } } impl> BLTParser { // NON-TERMINALS - HIGHER LEVEL /// Parse the BLT file pub fn parse_blt(&mut self) -> Result<(), ParseError> { self.delimiter(); self.header()?; self.withdrawn_candidates()?; self.ballots()?; self.strings()?; return Ok(()); } /// Parse the header fn header(&mut self) -> Result<(), ParseError> { self.num_candidates = self.usize()?; self.delimiter(); self.election.seats = self.usize()?; self.delimiter(); return Ok(()); } /// Parse the withdrawn candidates (if any) fn withdrawn_candidates(&mut self) -> Result<(), ParseError> { while self.lookahead() == '-' { self.accept(); // Minus sign let index = self.usize()? - 1; self.election.withdrawn_candidates.push(index); self.delimiter(); } return Ok(()); } /// Parse the list of ballots fn ballots(&mut self) -> Result<(), ParseError> { loop { if self.lookahead() == '0' { // End of ballots, or start of decimal? self.accept(); if self.lookahead() == '.' { // Decimal self.ballot_value_buf.clear(); self.ballot_value_buf.push('0'); self.ballot()?; } else { // End of ballots self.delimiter(); break; } } else { self.ballot_value_buf.clear(); self.ballot()?; } } return Ok(()); } /// Parse a ballot fn ballot(&mut self) -> Result<(), ParseError> { self.ballot_has_equal_rankings = false; self.ballot_value()?; self.delimiter_not_nl(); // Read preferences let mut preferences: Vec> = Vec::new(); loop { if self.lookahead() == '0' || self.lookahead() == '\n' { // End of preferences self.accept(); break; } else if self.lookahead() == '=' { // Equal preference self.ballot_has_equal_rankings = true; self.accept(); preferences.last_mut().unwrap().push(self.usize()? - 1); self.delimiter_not_nl(); } else { // No equal preference preferences.push(vec![self.usize()? - 1]); self.delimiter_not_nl(); } } self.delimiter(); let ballot = Ballot { orig_value: N::parse(&self.ballot_value_buf), preferences, has_equal_rankings: self.ballot_has_equal_rankings, }; self.election.ballots.push(ballot); return Ok(()); } /// Parse the list of strings at the end of the BLT file fn strings(&mut self) -> Result<(), ParseError> { for index in 0..self.num_candidates { let name = self.string()?; self.election.candidates.push(Candidate { index, name, is_dummy: false, }); } let name = self.string()?; self.election.name = name; return Ok(()); } // NON-TERMINALS - LOWER LEVEL /// Parse an integer into a [usize] fn usize(&mut self) -> Result { // return Ok(self.integer()?.parse().expect("Invalid usize")); // Use a separate implementation to avoid allocating String let mut result = self.digit_nonzero()?.to_digit(10).unwrap() as usize; loop { match self.digit() { Err(_) => { break; } Ok(d) => { result = result.checked_mul(10).expect("Integer overflows usize"); result = result.checked_add(d.to_digit(10).unwrap() as usize).expect("Integer overflows usize"); } } } return Ok(result); } /*/// Parse an integer as a [String] fn integer(&mut self) -> Result { let mut result = String::from(self.digit_nonzero()?); loop { match self.digit() { Err(_) => { break; } Ok(d) => { result.push(d); } } } return Ok(result); }*/ /// Parse a number as an instance of N fn ballot_value(&mut self) -> Result<(), ParseError> { loop { match self.ballot_value_element() { Err(_) => { break; } Ok(d) => { self.ballot_value_buf.push(d); } } } return Ok(()); } /// Parse a quoted or raw string fn string(&mut self) -> Result { if let Ok(s) = self.quoted_string() { return Ok(s); } if let Ok(s) = self.raw_string() { return Ok(s); } return Err(ParseError::Expected(self.line_no, self.col_no, self.lookahead(), "string")); } /// Parse a quoted string fn quoted_string(&mut self) -> Result { if self.lookahead() == '"' { self.accept(); // Opening quotation mark let mut result = String::new(); loop { // Read string contents if self.lookahead() == '"' { break; } else if self.lookahead() == '\\' { // Escape sequence self.accept(); if self.lookahead() == '"' || self.lookahead() == '\\' { result.push(self.accept()); } else { return Err(ParseError::Unexpected(self.line_no, self.col_no, self.lookahead())); } } else { result.push(self.accept()); } } while self.lookahead() != '"' { // TODO: BufRead::read_until ? } self.accept(); // Closing quotation mark if !self.eof() { self.delimiter(); } return Ok(result); } else { return Err(ParseError::Expected(self.line_no, self.col_no, self.lookahead(), "'\"'")); } } /// Parse a raw (unquoted) string fn raw_string(&mut self) -> Result { let mut result = String::new(); while !self.lookahead().is_whitespace() && !self.eof() { result.push(self.accept()); } if !self.eof() { self.delimiter(); } return Ok(result); } /// Skip any sequence of whitespace or comments fn delimiter(&mut self) { loop { if self.eof() { break; } else if self.lookahead() == '#' { self.dnl(); if !self.eof() { self.accept(); // Trailing newline } } else if self.lookahead().is_whitespace() { self.accept(); while !self.eof() && self.lookahead().is_whitespace() { self.accept(); } } else { break; } } } /// Skip any sequence of whitespace or comments, but do not accept any newline and leave it trailing fn delimiter_not_nl(&mut self) { loop { if self.eof() { break; } else if self.lookahead() == '#' { self.dnl(); } else if self.lookahead().is_whitespace() && self.lookahead() != '\n' { self.accept(); while !self.eof() && self.lookahead().is_whitespace() && self.lookahead() != '\n' { self.accept(); } } else { break; } } } /// Skip to the next newline fn dnl(&mut self) { while !self.eof() && self.lookahead() != '\n' { // TODO: BufRead::read_until ? self.accept(); } } // TERMINALS /// Read a nonzero digit fn digit_nonzero(&mut self) -> Result { if self.lookahead() >= '1' && self.lookahead() <= '9' { return Ok(self.accept()); } else { return Err(ParseError::Expected(self.line_no, self.col_no, self.lookahead(), "nonzero digit")); } } /// Read any digit fn digit(&mut self) -> Result { if self.lookahead() >= '0' && self.lookahead() <= '9' { return Ok(self.accept()); } else { return Err(ParseError::Expected(self.line_no, self.col_no, self.lookahead(), "digit")); } } /// Read any element of a valid number, i.e. a digit, decimal point or slash fn ballot_value_element(&mut self) -> Result { if (self.lookahead() >= '0' && self.lookahead() <= '9') || self.lookahead() == '.' || self.lookahead() == '/' { return Ok(self.accept()); } else { return Err(ParseError::Expected(self.line_no, self.col_no, self.lookahead(), "number")); } } // UTILITIES /// Return if this is the end of the file fn eof(&mut self) -> bool { return self.chars.peek().is_none(); } /// Peek at the next character in the stream fn lookahead(&mut self) -> char { return *self.chars.peek().expect("Unexpected EOF"); } /// Read and return one character from the stream fn accept(&mut self) -> char { let result = self.chars.next().expect("Unexpected EOF"); if result == '\n' { self.line_no += 1; self.col_no = 1; } else { self.col_no += 1; } return result; } // PUBLIC API /// Return a new [BLTParser] pub fn new(chars: Peekable) -> Self { Self { chars, ballot_value_buf: String::new(), ballot_has_equal_rankings: false, line_no: 1, col_no: 1, num_candidates: 0, election: Election { name: String::new(), seats: 0, candidates: Vec::new(), withdrawn_candidates: Vec::new(), ballots: Vec::new(), total_votes: None, constraints: None, }, } } /// Return the parsed [Election] pub fn as_election(self) -> Election { return self.election; } } /// Parse the given BLT file and return an [Election] pub fn parse_iterator, N: Number>(input: Peekable) -> Result, ParseError> { let mut parser = BLTParser::new(input); parser.parse_blt()?; return Ok(parser.as_election()); } /// Parse the BLT file at the given path and return an [Election] #[cfg(not(target_arch = "wasm32"))] pub fn parse_path, N: Number>(path: P) -> Result, ParseError> { let mut reader = BufReader::new(File::open(path).expect("IO Error")); let chars = reader.chars().map(|r| r.expect("IO Error")).peekable(); return parse_iterator(chars); }