raig 0.2.0

A library for boolean logic verification using And-Inverter Graphs (AIGs)
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
//! AIGER parsing support.
//!
//! Use [`run_parser_with_options`] to parse ASCII `.aag` or binary `.aig`
//! input from any [`BufRead`] source into an [`AigGraph`].
//!
//! ```
//! use raig::aiger::run_parser_with_options;
//! use raig::graph::Value;
//! use std::io::BufReader;
//!
//! let aiger = b"aag 1 1 0 1 0\n2\n2\n";
//! let mut reader = BufReader::new(&aiger[..]);
//! let (graph, _, _) = run_parser_with_options(&mut reader, true)?;
//!
//! let inputs = vec![vec![Value::MAX]];
//! let trace = graph.simulate(inputs.as_slice());
//! assert_eq!(trace[0].outputs[0], Value::MAX);
//! # Ok::<(), std::io::Error>(())
//! ```

use std::io::{self, BufRead, Error};

mod ascii_parser;
mod binary_parser;
mod serializer;

use crate::graph::{AigBuilder, AigGraph, NodeId, SymbolKind, SymbolTable};
use ascii_parser::parse_ascii_aiger_into_graph;
use binary_parser::parse_binary_aiger_into_graph;

pub use serializer::*;

/// Parsed metadata from an AIGER header line.
#[derive(Debug)]
pub struct AigerHeader {
    /// ASCII AIGER (`aag`) or binary AIGER (`aig`).
    pub mode: AigerMode,

    /// Maximum variable index (`M` in the AIGER header).
    pub max_var: usize,

    /// Number of primary inputs.
    pub num_inputs: usize,

    /// Number of latches.
    pub num_latches: usize,

    /// Number of primary outputs.
    pub num_outputs: usize,

    /// Number of AND gates.
    pub num_and_gates: usize,

    /// Number of bad-state properties from the AIGER 1.9 extension.
    pub num_bad_states: usize,

    /// Number of invariant constraints from the AIGER 1.9 extension.
    pub num_invariants: usize,

    /// Number of justice properties from the AIGER 1.9 extension.
    pub num_justice: usize,

    /// Number of fairness constraints from the AIGER 1.9 extension.
    pub num_fairness: usize,
}

#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub enum AigerMode {
    /// `.aag`
    Ascii,
    /// `.aig`
    Binary,
}

impl AigerMode {
    pub const fn ext(&self) -> &'static str {
        match self {
            AigerMode::Ascii => "aag",
            AigerMode::Binary => "aig",
        }
    }
}

impl AigerHeader {
    /// Returns the total number of outputs, bad_states, invariants, justice and fairness properties
    pub fn num_labels(&self) -> usize {
        self.num_outputs
            + self.num_bad_states
            + self.num_invariants
            + self.num_justice
            + self.num_fairness
    }
}

/// Parse an AIGER stream into an [`AigGraph`].
///
/// The parser accepts ASCII AIGER (`aag`) and binary AIGER (`aig`) input. When
/// `pre_optimize` is `true`, common Boolean identities are simplified while the
/// graph is constructed.
pub fn run_parser_with_options(
    reader: &mut impl BufRead,
    pre_optimize: bool,
) -> io::Result<(AigGraph, SymbolTable, String)> {
    let header: AigerHeader = verify_aiger_header(reader)?;
    match header.mode {
        AigerMode::Ascii => parse_ascii_aiger_into_graph(header, reader, pre_optimize),
        AigerMode::Binary => parse_binary_aiger_into_graph(header, reader, pre_optimize),
    }
}

/// Parse an optional AIGER header field, which defaults to zero.
fn parse_optional_field(parser: &mut LineParser) -> usize {
    let val = parser.parse_int().unwrap_or(0);
    parser.skip_whitespace();
    val
}

/// Read and validate an AIGER header.
///
/// This consumes only the header line. It panics if the header is malformed or
/// violates the basic AIGER size constraints.
pub fn verify_aiger_header(reader: &mut impl BufRead) -> Result<AigerHeader, Error> {
    let mut parser = LineParser::default();
    parser.read_line(reader)?;
    let tag = parser.parse_word();
    let mode = match tag {
        b"aag" => AigerMode::Ascii,
        b"aig" => AigerMode::Binary,
        _ => panic!("Invalid tag, must be either 'aag' or 'aig'"),
    };
    debug_assert_eq!(mode.ext().as_bytes(), tag);

    // The basic header fields.
    let [max_var, num_inputs, num_latches, num_outputs, num_and_gates] = parser
        .parse_ints()
        .expect("Header must have format: aag/aig M I L O A [B C J F]");
    parser.skip_whitespace();

    // The extension header fields. The AIGER 1.9 spec says that all these
    // fields are optional; omitting them is equivalent to setting them to 0.
    let num_bad_states = parse_optional_field(&mut parser);
    let num_invariants = parse_optional_field(&mut parser);
    let num_justice = parse_optional_field(&mut parser);
    let num_fairness = parse_optional_field(&mut parser);

    assert!(parser.rest().is_empty(), "extra data on header line");

    let expected_max_var: usize = num_inputs + num_latches + num_and_gates;

    if max_var < expected_max_var {
        panic!(
            "ASCII AIGER requires M >= I + L + A, Binary requires M = I + L + A, got M={} and I+L+A={}",
            max_var, expected_max_var
        )
    }

    if max_var != expected_max_var && mode == AigerMode::Binary {
        panic!(
            "Binary AIGER requires M = I + L + A, got M={} and I+L+A={}",
            max_var, expected_max_var
        );
    }

    Ok(AigerHeader {
        mode,
        max_var,
        num_inputs,
        num_latches,
        num_outputs,
        num_and_gates,
        num_bad_states,
        num_invariants,
        num_justice,
        num_fairness,
    })
}

fn resolve_labels_and_latches(
    mut label_lits: Vec<usize>,
    latch_inputs: Vec<(NodeId, usize)>,
    header: &AigerHeader,
    graph: &mut AigBuilder,
    literals: &Literals,
) {
    for (latch_id, latch_input_lit) in latch_inputs {
        let latch_input_id: NodeId = literals.get(latch_input_lit);
        graph.node(latch_id).set_latch_input(latch_input_id);
    }

    // resolve labels
    label_lits.reverse();
    for _ in 0..header.num_outputs {
        graph.add_output(literals.get(label_lits.pop().unwrap()));
    }
    for _ in 0..header.num_bad_states {
        graph.add_bad_state(literals.get(label_lits.pop().unwrap()));
    }
    for _ in 0..header.num_invariants {
        graph.add_invariant(literals.get(label_lits.pop().unwrap()));
    }
    for _ in 0..header.num_justice {
        graph.add_justice(literals.get(label_lits.pop().unwrap()));
    }
    for _ in 0..header.num_fairness {
        graph.add_fairness(literals.get(label_lits.pop().unwrap()));
    }
    debug_assert!(label_lits.is_empty());
}

/// A mapping from AIGER literal indices to our internal `NodeId`s.
#[derive(Default)]
struct Literals(Vec<NodeId>);

impl Literals {
    fn new(max_var: usize) -> Self {
        // We store one entry per *variable*: i.e., one entry in this mapping
        // covers both the regular and inverted literals corresponding to the
        // same node.
        let mut map = vec![NodeId::NONE; max_var + 1];
        map[0] = NodeId::FALSE;
        Self(map)
    }

    /// Split a literal into a variable index and an inverted flag.
    fn split(literal: usize) -> (usize, bool) {
        (literal >> 1, literal & 1 == 1)
    }

    /// Record that a given AIGER literal corresponds to a given fresh `NodeID`.
    fn add(&mut self, literal: usize, id: NodeId) {
        let (var_idx, inverted) = Self::split(literal);
        self.0[var_idx] = if inverted { id.invert() } else { id };
    }

    /// Get the `NodeID` corresponding to a given AIGER literal.
    ///
    /// Panic if the literal is not present.
    fn get(&self, literal: usize) -> NodeId {
        let (var_idx, inverted) = Self::split(literal);
        match self.0[var_idx] {
            NodeId::NONE => panic!("Unknown aiger literal: {}", literal),
            regular_node => {
                if inverted {
                    regular_node.invert()
                } else {
                    regular_node
                }
            }
        }
    }
}

/// A low-level parser for integers and words in a single ASCII line.
#[derive(Default)]
pub struct LineParser {
    /// The line buffer being parsed.
    pub buf: Vec<u8>,

    /// The current byte position in `buf`.
    pub pos: usize,
}

impl LineParser {
    /// Create a parser from an existing line buffer.
    pub fn new(buf: Vec<u8>) -> Self {
        Self { buf, pos: 0 }
    }

    /// Empty the line buffer.
    pub fn clear(&mut self) {
        self.buf.clear();
        self.pos = 0;
    }

    /// Get all the data remaining in the line buffer.
    pub fn rest(&self) -> &[u8] {
        &self.buf[self.pos..]
    }

    /// Read a line from a text-file stream. Return a flag indicating EOF.
    pub fn read_line<R: BufRead>(&mut self, reader: &mut R) -> std::io::Result<bool> {
        self.clear();
        reader.read_until(b'\n', &mut self.buf)?;
        Ok(self.buf.is_empty())
    }

    fn peek(&self) -> Option<u8> {
        self.buf.get(self.pos).copied()
    }

    fn skip(&mut self) {
        debug_assert!(self.pos < self.buf.len());
        self.pos += 1;
    }

    fn pop_if(&mut self, pred: impl Fn(u8) -> bool) -> Option<u8> {
        if let Some(byte) = self.peek()
            && pred(byte)
        {
            self.skip();
            Some(byte)
        } else {
            None
        }
    }

    /// Consume a single ASCII integer from the current point in the line buffer.
    pub fn parse_int(&mut self) -> Option<usize> {
        let mut out: Option<usize> = None;

        while let Some(byte) = self.pop_if(|b| b.is_ascii_digit()) {
            let value = byte - b'0';
            out = Some(match out {
                Some(old) => old * 10 + (value as usize),
                None => value as usize,
            });
        }

        out
    }

    /// Advance the line buffer to consume a sequence of ASCII whitespace.
    pub fn skip_whitespace(&mut self) {
        while self.pop_if(|b| b.is_ascii_whitespace()).is_some() {}
    }

    /// Consume a sequence of whitespace-separated integers.
    pub fn parse_ints<const N: usize>(&mut self) -> Option<[usize; N]> {
        // Sadly, `std::array::try_from_fn` is unstable. We fake it by setting a
        // flag on parsing errors and, on failure, wastefully continuing to
        // construct an array that we will eventually throw away.
        let mut failed = false;
        let arr = std::array::from_fn(|_| {
            self.skip_whitespace();
            match self.parse_int() {
                Some(i) => i,
                None => {
                    failed = true;
                    0
                }
            }
        });
        if failed { None } else { Some(arr) }
    }

    /// Consume a sequence of non-whitespace bytes.
    pub fn parse_word(&mut self) -> &[u8] {
        let start_pos = self.pos;
        while self.pop_if(|b| !b.is_ascii_whitespace()).is_some() {}
        &self.buf[start_pos..self.pos]
    }
}

/// A utility for reading integers from lines in a text stream.
///
/// This wraps `LineReader` in utilities for consuming lines directly from a
/// `BufRead` stream.
struct LineReader<'a, R: BufRead> {
    reader: &'a mut R,
    parser: LineParser,
}

impl<'a, R: BufRead> LineReader<'a, R> {
    fn new(reader: &'a mut R) -> Self {
        LineReader {
            reader,
            parser: LineParser::default(),
        }
    }

    /// Read a line containing a single integer.
    fn read_int(&mut self) -> std::io::Result<Option<usize>> {
        self.parser.read_line(self.reader)?;
        Ok(self.parser.parse_int())
    }

    /// Read a line containing a whitespace-separated list of integers.
    fn read_ints<const N: usize>(&mut self) -> std::io::Result<Option<[usize; N]>> {
        self.parser.read_line(self.reader)?;
        Ok(self.parser.parse_ints())
    }
}

fn parse_symbol_table_and_comments<R: BufRead>(
    reader: &mut LineReader<R>,
) -> Result<(SymbolTable, String), Error> {
    let st = parse_symbol_table(reader)?;
    let mut comments = "".to_string();
    if !reader.parser.rest().is_empty() && reader.parser.rest().trim_ascii() == b"c" {
        reader.reader.read_to_string(&mut comments)?;
    }
    Ok((st, comments))
}

fn parse_symbol_table<R: BufRead>(reader: &mut LineReader<R>) -> Result<SymbolTable, Error> {
    reader.parser.clear();
    let mut st = SymbolTable::default();
    reader.parser.read_line(reader.reader)?;
    while let Some(kind) = reader.parser.pop_if(SymbolKind::is_tag) {
        let index = reader.parser.parse_int().expect("expected an index");
        reader.parser.skip_whitespace();
        let name = std::str::from_utf8(reader.parser.rest())
            .expect("expected valid utf-8")
            .trim_ascii();
        let kind = SymbolKind::from_tag(kind).unwrap();
        st.name_symbol(kind, index, name);
        reader.parser.read_line(reader.reader)?;
    }
    Ok(st)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn just_int() {
        let mut parser = LineParser::new("42".as_bytes().to_vec());
        assert_eq!(parser.parse_int(), Some(42));
        assert!(parser.rest().is_empty());
    }

    #[test]
    fn int_with_stuff() {
        let mut parser = LineParser::new("42x".as_bytes().to_vec());
        assert_eq!(parser.parse_int(), Some(42));
        assert_eq!(parser.rest().len(), 1);
    }

    #[test]
    fn two_ints() {
        let mut parser = LineParser::new("42 27 x".as_bytes().to_vec());
        assert_eq!(parser.parse_ints(), Some([42, 27]));
        assert_eq!(parser.rest().len(), 2);
    }
}