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(storage: &mut Storage, mut writer: W) -> 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

898626

        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

898626

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

57

898626

        }) {

58

449313

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

59

449313

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

60

449313

            if inserted {

61

                // New LDD that must be written to stream

62

449313

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

63

449313

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

64

449313

                self.writer.write_bits(

65

449313

                    *nodes

66

449313

                        .index(&down)

67

449313

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

68

449313

                    Self::ldd_index_width(&nodes),

69

)?;

70

449313

                self.writer.write_bits(

71

449313

                    *nodes

72

449313

                        .index(&right)

73

449313

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

74

449313

                    Self::ldd_index_width(&nodes),

75

)?;

76

77

78

449313

            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

447313

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

900626

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

92

900626

        bits_for_value(nodes.len())

93

900626

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

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

104

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

105

103

        let magic = reader.read_bits(16)?;

106

103

        if magic != BLF_MAGIC {

107

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

108

103

109

110

103

        let version = reader.read_bits(16)?;

111

103

        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

103

114

115

        // Add the true and false constants

116

103

        let nodes = vec![storage.empty_set().clone(), storage.empty_vector().clone()];

117

103

        Ok(Self { reader, nodes })

118

103

119

120

    /// Reads an LDD from the stream.

121

2127

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

122

        loop {

123

461644

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

124

125

461644

            if is_output {

126

                // The output is simply an index of the LDD

127

2127

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

128

2127

                return Ok(self

129

2127

                    .nodes

130

2127

                    .get(index)

131

2127

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

132

2127

                    .clone());

133

459517

134

135

459517

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

136

459517

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

137

459517

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

138

459517

            let ldd = storage.insert(

139

459517

                value as u32,

140

459517

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

141

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

142

459517

                    self.nodes.len()

143

                ))?,

144

459517

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

145

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

146

459517

                    self.nodes.len()

147

                ))?,

148

);

149

459517

            self.nodes.push(ldd);

150

151

2127

152

153

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

154

921161

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

155

921161

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

156

921161

157

158

159

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

160

    delegate::delegate! {

161

        to self.reader {

162

1229

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

163

15

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

164

165

166

167

168

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

169

    delegate::delegate! {

170

        to self.reader {

171

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

172

300

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

173

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

174

175

176

177

178

#[cfg(test)]

179

mod tests {

180

    use merc_io::BitStreamReader;

181

    use merc_io::BitStreamWriter;

182

    use merc_utilities::random_test;

183

184

    use crate::test_utility::from_iter;

185

    use crate::test_utility::random_vector_set;

186

187

    use super::*;

188

189

    #[test]

190

    #[cfg_attr(miri, ignore)]

191

1

    fn test_binary_ldd_stream() {

192

100

        random_test(100, |rng| {

193

100

            let mut storage = Storage::new();

194

195

100

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

196

2000

                .map(|_| {

197

2000

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

198

2000

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

199

2000

})

200

100

                .collect();

201

202

100

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

203

100

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

204

205

100

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

206

2000

            for term in &input {

207

2000

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

208

2000

209

100

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

210

211

100

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

212

2000

            for term in &input {

213

2000

                debug_assert_eq!(

214

                    *term,

215

2000

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

216

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

217

);

218

219

100

});

220

1

221