Grcov report - io

1

use std::cell::RefCell;

2

3

use oxidd::ManagerRef;

4

use oxidd::ldd::LDDFunction;

5

use oxidd::ldd::LDDManagerRef;

6

7

use merc_aterm::ATerm;

8

use merc_aterm::ATermRead;

9

use merc_collections::IndexedSet;

10

use merc_io::BitStreamRead;

11

use merc_io::BitStreamWrite;

12

use merc_number::bits_for_value;

13

use merc_utilities::MercError;

14

15

use crate::Data;

16

use crate::iter_nodes;

17

18

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

19

const BLF_MAGIC: u64 = 0x8baf;

20

const BLF_VERSION: u64 = 0x8306;

21

22

/// Writes LDDs in a streamable binary format to an output stream.

23

///

24

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

25

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

26

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

27

/// will be returned by [BinaryLddReader::read_ldd].

28

pub struct BinaryLddWriter<W: BitStreamWrite> {

29

    writer: W,

30

    nodes: RefCell<IndexedSet<LDDFunction>>,

31

32

33

impl<W: BitStreamWrite> BinaryLddWriter<W> {

34

102

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

35

        // Write the header of the binary LDD format.

36

102

        writer.write_bits(BLF_MAGIC, 16)?;

37

102

        writer.write_bits(BLF_VERSION, 16)?;

38

39

        // Add the true and false constants

40

102

        let mut nodes = IndexedSet::new();

41

102

        manager.with_manager_shared(|m| -> Result<(), MercError> {

42

102

            nodes.insert(LDDFunction::empty_set(m)?);

43

102

            nodes.insert(LDDFunction::empty_vector(m)?);

44

102

            Ok(())

45

102

        })?;

46

47

102

        Ok(Self {

48

102

            writer,

49

102

            nodes: RefCell::new(nodes),

50

102

})

51

102

52

53

    /// Writes an LDD to the stream.

54

2002

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

55

510228

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

56

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

57

510228

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

58

510228

        }) {

59

449228

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

60

449228

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

61

449228

            if inserted {

62

                // New LDD that must be written to stream

63

449228

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

64

449228

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

65

449228

                self.writer.write_bits(

66

449228

                    *nodes

67

449228

                        .index(&down)

68

449228

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

69

449228

                    Self::ldd_index_width(&nodes),

70

)?;

71

449228

                self.writer.write_bits(

72

449228

                    *nodes

73

449228

                        .index(&right)

74

449228

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

75

449228

                    Self::ldd_index_width(&nodes),

76

)?;

77

78

79

449228

            if node == *ldd {

80

                // Write output LDD

81

2000

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

82

2000

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

83

447228

84

85

86

        // iter_nodes yields nothing for terminals; emit the output marker directly.

87

2002

        if ldd.node().is_none() {

88

2

            let nodes = self.nodes.borrow();

89

2

            let index = nodes.index(ldd).expect("terminals are pre-inserted in new()");

90

2

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

91

2

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

92

2000

93

94

2002

        Ok(())

95

2002

96

97

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

98

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

99

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

100

900458

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

101

900458

        bits_for_value(nodes.len())

102

900458

103

104

105

pub struct BinaryLddReader<R: BitStreamRead> {

106

    reader: R,

107

    nodes: Vec<LDDFunction>,

108

109

110

impl<R: BitStreamRead> BinaryLddReader<R> {

111

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

112

108

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

113

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

114

108

        let magic = reader.read_bits(16)?;

115

108

        if magic != BLF_MAGIC {

116

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

117

108

118

119

108

        let version = reader.read_bits(16)?;

120

108

        if version != BLF_VERSION {

121

            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());

122

108

123

124

        // Add the true and false constants

125

108

        let nodes = storage.with_manager_shared(|m| -> Result<_, MercError> {

126

108

            Ok(vec![LDDFunction::empty_set(m)?, LDDFunction::empty_vector(m)?])

127

108

        })?;

128

108

        Ok(Self { reader, nodes })

129

108

130

131

    /// Reads an LDD from the stream.

132

2207

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

133

        loop {

134

464511

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

135

136

464511

            if is_output {

137

                // The output is simply an index of the LDD

138

2207

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

139

2207

                return Ok(self

140

2207

                    .nodes

141

2207

                    .get(index)

142

2207

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

143

2207

                    .clone());

144

462304

145

146

462304

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

147

462304

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

148

462304

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

149

462304

            let down = self

150

462304

                .nodes

151

462304

                .get(down_index)

152

462304

                .ok_or(format!(

153

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

154

462304

                    self.nodes.len()

155

))?

156

462304

                .clone();

157

462304

            let right = self

158

462304

                .nodes

159

462304

                .get(right_index)

160

462304

                .ok_or(format!(

161

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

162

462304

                    self.nodes.len()

163

))?

164

462304

                .clone();

165

462304

            let ldd = storage.with_manager_shared(|m| LDDFunction::make_node(m, value as u32, &down, &right))?;

166

462304

            self.nodes.push(ldd);

167

168

2207

169

170

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

171

926815

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

172

926815

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

173

926815

174

175

176

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

177

    delegate::delegate! {

178

        to self.reader {

179

2041

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

180

30

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

181

182

183

184

185

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

186

    delegate::delegate! {

187

        to self.reader {

188

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

189

484

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

190

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

191

192

193

194

195

#[cfg(test)]

196

mod tests {

197

    use merc_io::BitStreamReader;

198

    use merc_io::BitStreamWriter;

199

    use merc_utilities::random_test;

200

201

    use crate::from_iter;

202

    use crate::random_vector_set;

203

204

    use super::*;

205

206

    #[test]

207

    #[cfg_attr(miri, ignore)] // Oxidd does not work with miri

208

1

    fn test_binary_ldd_stream_terminals() {

209

1

        let manager = oxidd::ldd::new_manager(2048, 1024, 1);

210

211

1

        let terminals = manager.with_manager_shared(|m| {

212

1

213

1

                LDDFunction::empty_set(m).unwrap(),

214

1

                LDDFunction::empty_vector(m).unwrap(),

215

1

216

1

});

217

2

        for term in terminals {

218

2

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

219

2

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

220

2

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

221

2

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

222

2

            drop(output_stream);

223

224

2

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

225

2

            assert!(

226

2

                term == input_stream.read_ldd(&manager).unwrap(),

227

                "terminal round-trip failed"

228

);

229

230

1

231

232

    #[test]

233

    #[cfg_attr(miri, ignore)]

234

1

    fn test_binary_ldd_stream() {

235

100

        random_test(100, |rng| {

236

100

            let manager = oxidd::ldd::new_manager(2048, 1024, 1);

237

238

100

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

239

2000

                .map(|_| {

240

2000

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

241

2000

                    from_iter(&manager, input.iter())

242

2000

})

243

100

                .collect();

244

245

100

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

246

100

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

247

248

100

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

249

2000

            for term in &input {

250

2000

                output_stream.write_ldd(term).unwrap();

251

2000

252

100

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

253

254

100

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

255

2000

            for term in &input {

256

2000

                assert!(

257

2000

                    *term == input_stream.read_ldd(&manager).unwrap(),

258

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

259

);

260

261

100

});

262

1

263