Grcov report - io

1

//!

2

//! # The streamable ldd format:

3

//!

4

//! Every LDD is traversed in order and assigned a unique number. Whenever traversal

5

//! encounters an LDD for which all children have been visited it is written to the stream

6

//! as `0:[value, down_index, right_index]`. Every output LDD is written as `1:index`, and

7

//! will be returned by `read_ldd()`.

8

//!

9

10

use std::cell::RefCell;

11

12

use merc_aterm::ATerm;

13

use merc_aterm::ATermRead;

14

use merc_collections::IndexedSet;

15

use merc_io::BitStreamRead;

16

use merc_io::BitStreamWrite;

17

use merc_number::bits_for_value;

18

use merc_utilities::MercError;

19

20

use crate::Data;

21

use crate::Ldd;

22

use crate::Storage;

23

use crate::iterators::iter_nodes;

24

25

///  The magic value for a binary LDD format stream.

26

const BLF_MAGIC: u64 = 0x8baf;

27

const BLF_VERSION: u64 = 0x8306;

28

29

/// \brief Writes ldds in a streamable binary format to an output stream.

30

pub struct BinaryLddWriter<W: BitStreamWrite> {

31

    writer: W,

32

    nodes: RefCell<IndexedSet<Ldd>>,

33

34

35

impl<W: BitStreamWrite> BinaryLddWriter<W> {

36

100

    pub fn new(mut writer: W, storage: &mut Storage) -> Result<Self, MercError> {

37

        // Write the header of the binary LDD format.

38

100

        writer.write_bits(BLF_MAGIC, 16)?;

39

100

        writer.write_bits(BLF_VERSION, 16)?;

40

41

        // Add the true and false constants

42

100

        let mut nodes = IndexedSet::new();

43

100

        nodes.insert(storage.empty_set().clone());

44

100

        nodes.insert(storage.empty_vector().clone());

45

46

100

        Ok(Self {

47

100

            writer,

48

100

            nodes: RefCell::new(nodes),

49

100

})

50

100

51

52

    /// Writes an LDD to the stream.

53

2000

    pub fn write_ldd(&mut self, ldd: &Ldd, storage: &Storage) -> Result<(), MercError> {

54

898676

        for (node, Data(value, down, right)) in iter_nodes(storage, ldd, |node| {

55

            // Skip any LDD that we have already inserted in the stream

56

898676

            !self.nodes.borrow().contains(node)

57

898676

        }) {

58

449338

            let mut nodes = self.nodes.borrow_mut();

59

449338

            let (index, inserted) = nodes.insert(node.clone());

60

449338

            if inserted {

61

                // New LDD that must be written to stream

62

449338

                self.writer.write_bits(0, 1)?;

63

449338

                self.writer.write_integer(value as u64)?;

64

449338

                self.writer.write_bits(

65

449338

                    *nodes

66

449338

                        .index(&down)

67

449338

                        .expect("The down node must have already been written") as u64,

68

449338

                    Self::ldd_index_width(&nodes),

69

)?;

70

449338

                self.writer.write_bits(

71

449338

                    *nodes

72

449338

                        .index(&right)

73

449338

                        .expect("The right node must have already been written") as u64,

74

449338

                    Self::ldd_index_width(&nodes),

75

)?;

76

77

78

449338

            if node == *ldd {

79

                // Write output LDD

80

2000

                self.writer.write_bits(1, 1)?;

81

2000

                self.writer.write_bits(*index as u64, Self::ldd_index_width(&nodes))?;

82

447338

83

84

85

2000

        Ok(())

86

2000

87

88

    /// Returns the number of bits required to represent an LDD index.

89

    /// This matches the reader: when writing a node definition we've already

90

    /// inserted the current node, so we use the current number of nodes.

91

900676

    fn ldd_index_width(nodes: &IndexedSet<Ldd>) -> u8 {

92

900676

        bits_for_value(nodes.len())

93

900676

94

95

96

pub struct BinaryLddReader<R: BitStreamRead> {

97

    reader: R,

98

    nodes: Vec<Ldd>,

99

100

101

impl<R: BitStreamRead> BinaryLddReader<R> {

102

    /// Inserts the header into the stream and initializes the reader.

103

101

    pub fn new(mut reader: R) -> Result<Self, MercError> {

104

        // Read and verify the header of the binary LDD format.

105

101

        let magic = reader.read_bits(16)?;

106

101

        if magic != BLF_MAGIC {

107

            return Err("Invalid magic number in binary LDD stream".into());

108

101

109

110

101

        let version = reader.read_bits(16)?;

111

101

        if version != BLF_VERSION {

112

            return Err(format!("The BLF version ({version}) of the input file is incompatible with the version ({BLF_VERSION}) of this tool. The input file must be regenerated.").into());

113

101

114

115

        // Add the true and false constants

116

101

        let nodes = vec![

117

101

            Storage::default().empty_set().clone(),

118

101

            Storage::default().empty_vector().clone(),

119

];

120

101

        Ok(Self { reader, nodes })

121

101

122

123

    /// Reads an LDD from the stream.

124

2103

    pub fn read_ldd(&mut self, storage: &mut Storage) -> Result<Ldd, MercError> {

125

        loop {

126

461115

            let is_output = self.reader.read_bits(1)? == 1;

127

128

461115

            if is_output {

129

                // The output is simply an index of the LDD

130

2103

                let index = self.reader.read_bits(self.ldd_index_width(false))? as usize;

131

2103

                return Ok(self

132

2103

                    .nodes

133

2103

                    .get(index)

134

2103

                    .ok_or(format!("Read invalid ldd index {index}, length {}", self.nodes.len()))?

135

2103

                    .clone());

136

459012

137

138

459012

            let value = self.reader.read_integer()?;

139

459012

            let down_index = self.reader.read_bits(self.ldd_index_width(true))? as usize;

140

459012

            let right_index = self.reader.read_bits(self.ldd_index_width(true))? as usize;

141

459012

            let ldd = storage.insert(

142

459012

                value as u32,

143

459012

                self.nodes.get(down_index).ok_or(format!(

144

                    "Read invalid down ldd index {down_index}, length {}",

145

459012

                    self.nodes.len()

146

                ))?,

147

459012

                self.nodes.get(right_index).ok_or(format!(

148

                    "Read invalid right ldd index {right_index}, length {}",

149

459012

                    self.nodes.len()

150

                ))?,

151

);

152

459012

            self.nodes.push(ldd);

153

154

2103

155

156

    /// Returns the number of bits required to represent an LDD index.

157

920127

    fn ldd_index_width(&self, input: bool) -> u8 {

158

920127

        bits_for_value(self.nodes.len() + input as usize) // Assume that size is one larger to contain the input ldd.

159

920127

160

161

162

impl<R: BitStreamRead + ATermRead> ATermRead for BinaryLddReader<R> {

163

    delegate::delegate! {

164

        to self.reader {

165

999

            fn read_aterm(&mut self) -> Result<Option<ATerm>, MercError>;

166

5

            fn read_aterm_iter(&mut self) -> Result<impl ExactSizeIterator<Item = Result<ATerm, MercError>>, MercError>;

167

168

169

170

171

impl<R: BitStreamRead> BitStreamRead for BinaryLddReader<R> {

172

    delegate::delegate! {

173

        to self.reader {

174

            fn read_bits(&mut self, num_bits: u8) -> Result<u64, MercError>;

175

234

            fn read_integer(&mut self) -> Result<u64, MercError>;

176

            fn read_string(&mut self) -> Result<String, MercError>;

177

178

179

180

181

#[cfg(test)]

182

mod tests {

183

    use merc_io::BitStreamReader;

184

    use merc_io::BitStreamWriter;

185

    use merc_utilities::random_test;

186

187

    use crate::test_utility::from_iter;

188

    use crate::test_utility::random_vector_set;

189

190

    use super::*;

191

192

    #[test]

193

    #[cfg_attr(miri, ignore)]

194

1

    fn test_binary_ldd_stream() {

195

100

        random_test(100, |rng| {

196

100

            let mut storage = Storage::new();

197

198

100

            let input: Vec<_> = (0..20)

199

2000

                .map(|_| {

200

2000

                    let input = random_vector_set(rng, 32, 10, 10);

201

2000

                    from_iter(&mut storage, input.iter())

202

2000

})

203

100

                .collect();

204

205

100

            let mut vector: Vec<u8> = Vec::new();

206

100

            let stream = BitStreamWriter::new(&mut vector);

207

208

100

            let mut output_stream = BinaryLddWriter::new(stream, &mut storage).unwrap();

209

2000

            for term in &input {

210

2000

                output_stream.write_ldd(term, &storage).unwrap();

211

2000

212

100

            drop(output_stream); // Explicitly drop to release the mutable borrow

213

214

100

            let mut input_stream = BinaryLddReader::new(BitStreamReader::new(&vector[..])).unwrap();

215

2000

            for term in &input {

216

2000

                debug_assert_eq!(

217

                    *term,

218

2000

                    input_stream.read_ldd(&mut storage).unwrap(),

219

                    "The read LDD must match the LDD that we have written"

220

);

221

222

100

});

223

1

224