diff options
Diffstat (limited to 'vendor/varisat-dimacs')
| -rw-r--r-- | vendor/varisat-dimacs/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/varisat-dimacs/Cargo.toml | 48 | ||||
| -rw-r--r-- | vendor/varisat-dimacs/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | vendor/varisat-dimacs/LICENSE-MIT | 25 | ||||
| -rw-r--r-- | vendor/varisat-dimacs/README.md | 26 | ||||
| -rw-r--r-- | vendor/varisat-dimacs/src/lib.rs | 573 |
6 files changed, 874 insertions, 0 deletions
diff --git a/vendor/varisat-dimacs/.cargo-checksum.json b/vendor/varisat-dimacs/.cargo-checksum.json new file mode 100644 index 000000000..cb80780cf --- /dev/null +++ b/vendor/varisat-dimacs/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"64ae0eebf5a2ff697a604a1e051221bad6a6514e5290be1f546dc53426d113e0","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"2259cbb177661977dd5510c05a8670da3cb28aa7f4ff74c193798db496fe92d8","README.md":"dc02e9e134a279bf0dd9a84aff8a3f8a935840c8f06a850a80da9c33705e397d","src/lib.rs":"40e7a41ad70120cc53402842af7d66fe80b826fc05b5e68eb8d2f5d3736ad532"},"package":"3d1dee4e21be1f04c0a939f7ae710cced47233a578de08a1b3c7d50848402636"}
\ No newline at end of file diff --git a/vendor/varisat-dimacs/Cargo.toml b/vendor/varisat-dimacs/Cargo.toml new file mode 100644 index 000000000..c44c54d63 --- /dev/null +++ b/vendor/varisat-dimacs/Cargo.toml @@ -0,0 +1,48 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +edition = "2018" +name = "varisat-dimacs" +version = "0.2.2" +authors = ["Jannis Harder <me@jix.one>"] +description = "DIMCAS CNF parser and writer for the Varisat SAT solver" +homepage = "https://jix.one/project/varisat/" +readme = "README.md" +license = "MIT/Apache-2.0" +repository = "https://github.com/jix/varisat" +[dependencies.anyhow] +version = "1.0.32" + +[dependencies.itoa] +version = "0.4.4" + +[dependencies.thiserror] +version = "1.0.20" + +[dependencies.varisat-formula] +version = "=0.2.2" +[dev-dependencies.env_logger] +version = "0.7.1" + +[dev-dependencies.proptest] +version = "0.10.1" + +[dev-dependencies.rand] +version = "0.7.3" + +[dev-dependencies.tempfile] +version = "3.0.8" + +[dev-dependencies.varisat-formula] +version = "=0.2.2" +features = ["proptest-strategies", "internal-testing"] diff --git a/vendor/varisat-dimacs/LICENSE-APACHE b/vendor/varisat-dimacs/LICENSE-APACHE new file mode 100644 index 000000000..16fe87b06 --- /dev/null +++ b/vendor/varisat-dimacs/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/vendor/varisat-dimacs/LICENSE-MIT b/vendor/varisat-dimacs/LICENSE-MIT new file mode 100644 index 000000000..4fd1cb2ff --- /dev/null +++ b/vendor/varisat-dimacs/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2017-2019 Jannis Harder + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/vendor/varisat-dimacs/README.md b/vendor/varisat-dimacs/README.md new file mode 100644 index 000000000..a28a60c14 --- /dev/null +++ b/vendor/varisat-dimacs/README.md @@ -0,0 +1,26 @@ +# Varisat - DIMACS + +DIMCAS CNF parser and writer for the [Varisat SAT solver][crate-varisat]. + +The functionality of this crate is re-exported by the [main Varisat +crate][crate-varisat]. + +## License + +The Varisat source code is licensed under either of + + * Apache License, Version 2.0 + ([LICENSE-APACHE](LICENSE-APACHE) or + http://www.apache.org/licenses/LICENSE-2.0) + * MIT license + ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) + +at your option. + +### Contribution + +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in Varisat by you, as defined in the Apache-2.0 license, shall be +dual licensed as above, without any additional terms or conditions. + +[crate-varisat]: https://crates.io/crates/varisat diff --git a/vendor/varisat-dimacs/src/lib.rs b/vendor/varisat-dimacs/src/lib.rs new file mode 100644 index 000000000..dc56230b6 --- /dev/null +++ b/vendor/varisat-dimacs/src/lib.rs @@ -0,0 +1,573 @@ +//! DIMCAS CNF parser and writer for the Varisat SAT solver. + +use std::{borrow::Borrow, io, mem::replace}; + +use varisat_formula::{CnfFormula, ExtendFormula, Lit, Var}; + +use anyhow::Error; +use thiserror::Error; + +/// Possible errors while parsing a DIMACS CNF formula. +#[derive(Debug, Error)] +pub enum ParserError { + #[error( + "line {}: Unexpected character in DIMACS CNF input: '{}'", + line, + unexpected + )] + UnexpectedInput { line: usize, unexpected: char }, + #[error( + "line {}: Literal index is too large: {}{}...", + line, + index, + final_digit + )] + LiteralTooLarge { + line: usize, + index: usize, + final_digit: usize, + }, + #[error("line {}: Invalid header syntax: {}", line, header)] + InvalidHeader { line: usize, header: String }, + #[error("line {}: Unterminated clause", line)] + UnterminatedClause { line: usize }, + #[error( + "Formula has {} variables while the header specifies {} variables", + var_count, + header_var_count + )] + VarCount { + var_count: usize, + header_var_count: usize, + }, + #[error( + "Formula has {} clauses while the header specifies {} clauses", + clause_count, + header_clause_count + )] + ClauseCount { + clause_count: usize, + header_clause_count: usize, + }, + #[error("Parser invoked after a previous error")] + PreviousError, +} + +/// Variable and clause count present in a DIMACS CNF header. +#[derive(Copy, Clone, Debug)] +pub struct DimacsHeader { + pub var_count: usize, + pub clause_count: usize, +} + +/// Parser for DIMACS CNF files. +/// +/// This parser can consume the input in chunks while also producing the parsed result in chunks. +#[derive(Default)] +pub struct DimacsParser { + formula: CnfFormula, + partial_clause: Vec<Lit>, + header: Option<DimacsHeader>, + + line_number: usize, + clause_count: usize, + partial_lit: usize, + negate_next_lit: bool, + + in_lit: bool, + in_comment_or_header: bool, + in_header: bool, + start_of_line: bool, + error: bool, + + header_line: Vec<u8>, +} + +impl DimacsParser { + /// Create a new DIMACS CNF parser. + pub fn new() -> DimacsParser { + DimacsParser { + formula: CnfFormula::new(), + partial_clause: vec![], + header: None, + + line_number: 1, + clause_count: 0, + partial_lit: 0, + negate_next_lit: false, + + in_lit: false, + in_comment_or_header: false, + in_header: false, + start_of_line: true, + error: false, + + header_line: vec![], + } + } + + /// Parse the given input and check the header if present. + /// + /// This parses the whole input into a single [`CnfFormula`](varisat_formula::CnfFormula). + /// Incremental parsing is possible using [`parse_incremental`](DimacsParser::parse_incremental) + /// or the [`parse_chunk`](DimacsParser::parse_chunk) method. + pub fn parse(input: impl io::Read) -> Result<CnfFormula, Error> { + Ok(Self::parse_incremental(input, |_| Ok(()))?.take_formula()) + } + + /// Parse the given input incrementally and check the header if present. + /// + /// The callback is invoked repeatedly with a reference to the parser. The callback can process + /// the formula incrementally by calling [`take_formula`](DimacsParser::take_formula) on the + /// passed argument. + pub fn parse_incremental( + input: impl io::Read, + mut callback: impl FnMut(&mut DimacsParser) -> Result<(), Error>, + ) -> Result<DimacsParser, Error> { + use io::BufRead; + + let mut buffer = io::BufReader::new(input); + let mut parser = Self::new(); + + loop { + let data = buffer.fill_buf()?; + if data.is_empty() { + break; + } + parser.parse_chunk(data)?; + let len = data.len(); + buffer.consume(len); + + callback(&mut parser)?; + } + parser.eof()?; + callback(&mut parser)?; + parser.check_header()?; + + Ok(parser) + } + + /// Parse a chunk of input. + /// + /// After parsing the last chunk call the [`eof`](DimacsParser::eof) method. + /// + /// If this method returns an error, the parser is in an invalid state and cannot parse further + /// chunks. + pub fn parse_chunk(&mut self, chunk: &[u8]) -> Result<(), ParserError> { + if self.error { + return Err(ParserError::PreviousError); + } + for &byte in chunk.iter() { + if byte == b'\n' { + self.line_number += 1; + } + match byte { + b'\n' | b'\r' if self.in_comment_or_header => { + if self.in_header { + self.in_header = false; + self.parse_header_line()?; + } + self.in_comment_or_header = false; + self.start_of_line = true + } + _ if self.in_comment_or_header => { + if self.in_header { + self.header_line.push(byte); + } + } + b'0'..=b'9' => { + self.in_lit = true; + let digit = (byte - b'0') as usize; + + const CAN_OVERFLOW: usize = Var::max_count() / 10; + const OVERFLOW_DIGIT: usize = Var::max_count() % 10; + + // Overflow check that is fast but still works if LitIdx has the same size as + // usize + if CAN_OVERFLOW <= self.partial_lit { + let carry = (digit <= OVERFLOW_DIGIT) as usize; + + if CAN_OVERFLOW + carry <= self.partial_lit { + self.error = true; + return Err(ParserError::LiteralTooLarge { + line: self.line_number, + index: self.partial_lit, + final_digit: digit, + }); + } + } + + self.partial_lit = self.partial_lit * 10 + digit; + + self.start_of_line = false + } + b'-' if !self.negate_next_lit && !self.in_lit => { + self.negate_next_lit = true; + self.start_of_line = false + } + b' ' | b'\n' | b'\r' if !self.negate_next_lit || self.in_lit => { + self.finish_literal(); + self.negate_next_lit = false; + self.in_lit = false; + self.partial_lit = 0; + self.start_of_line = byte != b' '; + } + b'c' if self.start_of_line => { + self.in_comment_or_header = true; + } + b'p' if self.start_of_line && self.header.is_none() => { + self.in_comment_or_header = true; + self.in_header = true; + self.header_line.push(b'p'); + } + _ => { + self.error = true; + return Err(ParserError::UnexpectedInput { + line: self.line_number, + unexpected: byte as char, + }); + } + } + } + + Ok(()) + } + + /// Finish parsing the input. + /// + /// This does not check whether the header information was correct, call + /// [`check_header`](DimacsParser::check_header) for this. + pub fn eof(&mut self) -> Result<(), ParserError> { + if self.in_header { + self.parse_header_line()?; + } + + self.finish_literal(); + + if !self.partial_clause.is_empty() { + return Err(ParserError::UnterminatedClause { + line: self.line_number, + }); + } + + Ok(()) + } + + /// Verifies the header information when present. + /// + /// Does nothing when the input doesn't contain a header. + pub fn check_header(&self) -> Result<(), ParserError> { + if let Some(header) = self.header { + let var_count = self.formula.var_count(); + if var_count != header.var_count { + return Err(ParserError::VarCount { + var_count, + header_var_count: header.var_count, + }); + } + + if self.clause_count != header.clause_count { + return Err(ParserError::ClauseCount { + clause_count: self.clause_count, + header_clause_count: header.clause_count, + }); + } + } + + Ok(()) + } + + /// Returns the subformula of everything parsed since the last call to this method. + /// + /// To parse the whole input into a single [`CnfFormula`](varisat_formula::CnfFormula), simply + /// call this method once after calling [`eof`](DimacsParser::eof). For incremental parsing this + /// method can be invoked after each call of [`parse_chunk`](DimacsParser::parse_chunk). + /// + /// The variable count of the returned formula will be the maximum of the variable count so far + /// and the variable count of the header if present. + pub fn take_formula(&mut self) -> CnfFormula { + let mut new_formula = CnfFormula::new(); + new_formula.set_var_count(self.formula.var_count()); + replace(&mut self.formula, new_formula) + } + + /// Return the DIMACS CNF header data if present. + pub fn header(&self) -> Option<DimacsHeader> { + self.header + } + + /// Number of clauses parsed. + pub fn clause_count(&self) -> usize { + self.clause_count + } + + /// Number of variables in the parsed formula. + pub fn var_count(&self) -> usize { + self.formula.var_count() + } + + fn finish_literal(&mut self) { + if self.in_lit { + if self.partial_lit == 0 { + self.formula.add_clause(&self.partial_clause); + self.partial_clause.clear(); + self.clause_count += 1; + } else { + self.partial_clause + .push(Var::from_dimacs(self.partial_lit as isize).lit(!self.negate_next_lit)); + } + } + } + + fn parse_header_line(&mut self) -> Result<(), ParserError> { + let header_line = String::from_utf8_lossy(&self.header_line).into_owned(); + + if !header_line.starts_with("p ") { + return self.invalid_header(header_line); + } + + let mut header_values = header_line[2..].split_whitespace(); + + if header_values.next() != Some("cnf") { + return self.invalid_header(header_line); + } + + let var_count: usize = match header_values + .next() + .and_then(|value| str::parse(value).ok()) + { + None => return self.invalid_header(header_line), + Some(value) => value, + }; + + if var_count > Var::max_count() { + self.error = true; + return Err(ParserError::LiteralTooLarge { + line: self.line_number, + index: var_count / 10, + final_digit: var_count % 10, + }); + } + + let clause_count: usize = match header_values + .next() + .and_then(|value| str::parse(value).ok()) + { + None => return self.invalid_header(header_line), + Some(value) => value, + }; + + if header_values.next().is_some() { + return self.invalid_header(header_line); + } + + self.header = Some(DimacsHeader { + var_count, + clause_count, + }); + + self.formula.set_var_count(var_count); + + Ok(()) + } + + fn invalid_header(&mut self, header_line: String) -> Result<(), ParserError> { + self.error = true; + Err(ParserError::InvalidHeader { + line: self.line_number, + header: header_line, + }) + } +} + +/// Write a DIMACS CNF header. +/// +/// Can be used with [`write_dimacs_clauses`] to implement incremental writing. +pub fn write_dimacs_header(target: &mut impl io::Write, header: DimacsHeader) -> io::Result<()> { + writeln!( + target, + "p cnf {var_count} {clause_count}", + var_count = header.var_count, + clause_count = header.clause_count + ) +} + +/// Write an iterator of clauses as headerless DIMACS CNF. +/// +/// Can be used with [`write_dimacs_header`] to implement incremental writing. +pub fn write_dimacs_clauses( + target: &mut impl io::Write, + clauses: impl IntoIterator<Item = impl IntoIterator<Item = impl Borrow<Lit>>>, +) -> io::Result<()> { + for clause in clauses.into_iter() { + for lit in clause.into_iter() { + itoa::write(&mut *target, lit.borrow().to_dimacs())?; + target.write_all(b" ")?; + } + target.write_all(b"0\n")?; + } + Ok(()) +} + +/// Write a formula as DIMACS CNF. +/// +/// Use [`write_dimacs_header`] and [`write_dimacs_clauses`] to implement incremental writing. +pub fn write_dimacs(target: &mut impl io::Write, formula: &CnfFormula) -> io::Result<()> { + write_dimacs_header( + &mut *target, + DimacsHeader { + var_count: formula.var_count(), + clause_count: formula.len(), + }, + )?; + write_dimacs_clauses(&mut *target, formula.iter()) +} + +#[cfg(test)] +mod tests { + use super::*; + + use anyhow::Error; + use proptest::{test_runner::TestCaseError, *}; + + use varisat_formula::{cnf::strategy::*, cnf_formula}; + + #[test] + fn odd_whitespace() -> Result<(), Error> { + let parsed = DimacsParser::parse( + b"p cnf 4 3 \n 1 \n 2 3\n0 -4 0 2\nccomment \n\n0\n\n" as &[_], + )?; + + let expected = cnf_formula![ + 1, 2, 3; + -4; + 2; + ]; + + assert_eq!(parsed, expected); + + Ok(()) + } + + macro_rules! expect_error { + ( $input:expr, $( $cases:tt )* ) => { + match DimacsParser::parse($input as &[_]) { + Ok(parsed) => panic!("Expexcted errror but got {:?}", parsed), + Err(err) => match err.downcast_ref() { + Some(casted_err) => match casted_err { + $( $cases )*, + _ => panic!("Unexpected error {:?}", casted_err), + }, + None => panic!("Unexpected error type {:?}", err), + } + } + }; + } + + #[test] + fn invalid_headers() { + expect_error!(b"pcnf 1 3", ParserError::InvalidHeader { .. } => ()); + expect_error!(b"p notcnf 1 3", ParserError::InvalidHeader { .. } => ()); + expect_error!(b"p cnf 1", ParserError::InvalidHeader { .. } => ()); + expect_error!(b"p cnf 1 2 3", ParserError::InvalidHeader { .. } => ()); + expect_error!(b"p cnf foo bar", ParserError::InvalidHeader { .. } => ()); + expect_error!(b"p cnf -3 -6", ParserError::InvalidHeader { .. } => ()); + + expect_error!( + format!("p cnf {} 4", Var::max_var().to_dimacs() + 1).as_bytes(), + ParserError::LiteralTooLarge { .. } => () + ); + DimacsParser::parse(format!("p cnf {} 0", Var::max_var().to_dimacs()).as_bytes()).unwrap(); + + expect_error!(b"p cnf 4 18446744073709551616", ParserError::InvalidHeader { .. } => ()); + + expect_error!( + b"p cnf 1 2\np cnf 1 2\n", + ParserError::UnexpectedInput { unexpected: 'p', .. } => () + ); + } + + #[test] + fn invalid_header_data() { + expect_error!( + b"p cnf 1 1\n 2 0", + ParserError::VarCount { var_count: 2, header_var_count: 1 } => () + ); + + expect_error!( + b"p cnf 10 1\n 1 0 0", + ParserError::ClauseCount { clause_count: 2, header_clause_count: 1 } => () + ); + + expect_error!( + b"p cnf 10 4\n 1 0", + ParserError::ClauseCount { clause_count: 1, header_clause_count: 4 } => () + ); + } + + #[test] + fn syntax_errors() { + expect_error!( + b"1 2 ?foo", + ParserError::UnexpectedInput { unexpected: '?', .. } => () + ); + + expect_error!( + b"1 2 - 3 0", + ParserError::UnexpectedInput { unexpected: ' ', .. } => () + ); + + expect_error!( + b"1 2 -\n3 0", + ParserError::UnexpectedInput { unexpected: '\n', .. } => () + ); + + expect_error!( + b"1 2 --3 0", + ParserError::UnexpectedInput { unexpected: '-', .. } => () + ); + + expect_error!( + b"1 2-3 0", + ParserError::UnexpectedInput { unexpected: '-', .. } => () + ); + } + + #[test] + fn unterminated_clause() { + expect_error!( + b"1 2 3", + ParserError::UnterminatedClause { .. } => () + ); + } + + #[test] + fn literal_too_large() { + expect_error!( + format!("1 {} 2 0", Var::max_var().to_dimacs() + 1).as_bytes(), + ParserError::LiteralTooLarge { .. } => () + ); + + assert_eq!( + DimacsParser::parse(format!("1 {} 2 0", Var::max_var().to_dimacs()).as_bytes()) + .unwrap(), + cnf_formula![ + 1, Var::max_var().to_dimacs(), 2; + ] + ); + } + + proptest! { + + #[test] + fn roundtrip(input in cnf_formula(1..100usize, 0..1000, 0..10)) { + let mut buf = vec![]; + + write_dimacs(&mut buf, &input)?; + + let parsed = DimacsParser::parse(&buf[..]).map_err(|e| TestCaseError::fail(e.to_string()))?; + + prop_assert_eq!(parsed, input); + } + } +} |