Grcov report - submap.rs

1

use std::fmt;

2

use std::ops::Index;

3

4

use merc_symbolic::FormatConfigSet;

5

use merc_symbolic::minus_edge;

6

use oxidd::BooleanFunction;

7

use oxidd::Function;

8

use oxidd::ManagerRef;

9

use oxidd::bdd::BDDFunction;

10

use oxidd::bdd::BDDManagerRef;

11

use oxidd_core::util::EdgeDropGuard;

12

13

use merc_utilities::MercError;

14

15

use crate::VertexIndex;

16

17

/// A mapping from vertices to configurations.

18

///

19

/// # Details

20

///

21

/// Internally this implementation uses the manager and the `edge` functions

22

/// directly for efficiency reasons. Every BDDFunction typically calls

23

/// `with_manager_shared` internally, which induces significant overhead for

24

/// many vertices/operations.

25

#[derive(Clone, PartialEq, Eq)]

26

pub struct Submap {

27

    /// The mapping from vertex indices to BDD functions.

28

    mapping: Vec<BDDFunction>,

29

30

    /// Invariant: counts the number of non-empty positions in the mapping.

31

    non_empty_count: usize,

32

33

    /// A cached reference to the false BDD function.

34

    false_bdd: BDDFunction,

35

36

37

impl Submap {

38

    /// Creates a new empty Submap for the given number of vertices.

39

2035

    pub fn new(manager_ref: &BDDManagerRef, initial: BDDFunction, num_of_vertices: usize) -> Self {

40

        Self {

41

2035

            mapping: vec![initial.clone(); num_of_vertices],

42

2035

            non_empty_count: if initial.satisfiable() {

43

248

                num_of_vertices // If the initial function is satisfiable, all entries are non-empty.

44

            } else {

45

1787

46

},

47

2035

            false_bdd: manager_ref.with_manager_shared(|manager| BDDFunction::f(manager)),

48

49

2035

50

51

    /// Returns an iterator over the vertices in the submap whose configuration is satisfiable.

52

5326

    pub fn iter_vertices<'a, 'id: 'a>(

53

5326

        &'a self,

54

5326

        manager: &'a <BDDFunction as Function>::Manager<'id>,

55

5326

    ) -> impl Iterator<Item = VertexIndex> + 'a {

56

5326

        let f_edge = self.false_bdd.as_edge(manager);

57

58

117172

        self.mapping.iter().enumerate().filter_map(move |(i, func)| {

59

117172

            if func.as_edge(manager) != f_edge {

60

54940

                Some(VertexIndex::new(i))

61

            } else {

62

62232

                None

63

64

117172

})

65

5326

66

67

    /// Returns the number of non-empty entries in the submap.

68

    pub fn number_of_non_empty(&self) -> usize {

69

        self.non_empty_count

70

71

72

    /// Sets the function for the given vertex index.

73

///

74

    /// Takes an internal manager to avoid repeated calls to `oxidd::Manager::with_manager_shared`.

75

18342

    pub fn set<'id>(

76

18342

        &mut self,

77

18342

        manager: &<BDDFunction as Function>::Manager<'id>,

78

18342

        index: VertexIndex,

79

18342

        func: BDDFunction,

80

18342

) {

81

18342

        let was_empty = self.mapping[*index].as_edge(manager) == self.false_bdd.as_edge(manager);

82

18342

        let is_empty = func.as_edge(manager) == self.false_bdd.as_edge(manager);

83

84

18342

        self.mapping[*index] = func;

85

86

        // Update the non-empty count invariant.

87

18342

        if was_empty && !is_empty {

88

14688

            self.non_empty_count += 1;

89

14688

        } else if !was_empty && is_empty {

90

            self.non_empty_count -= 1;

91

3654

92

18342

93

94

    /// Returns true iff the submap is empty.

95

4507

    pub fn is_empty(&self) -> bool {

96

4507

        self.non_empty_count == 0

97

4507

98

99

    /// Returns the number of entries in the submap.

100

1

    pub fn len(&self) -> usize {

101

1

        self.mapping.len()

102

1

103

104

    /// Clears the submap, setting all entries to the empty function.

105

    pub fn clear(&mut self, manager_ref: &BDDManagerRef) -> Result<(), MercError> {

106

        manager_ref.with_manager_shared(|manager| {

107

            for func in self.mapping.iter_mut() {

108

                *func = BDDFunction::f(manager);

109

110

            self.non_empty_count = 0;

111

});

112

113

        Ok(())

114

115

116

    /// Computes the difference between this submap and another submap.

117

2473

    pub fn minus(mut self, manager_ref: &BDDManagerRef, other: &Submap) -> Result<Submap, MercError> {

118

2473

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

119

2473

            let f_edge = EdgeDropGuard::new(manager, BDDFunction::f_edge(manager));

120

54406

            for (i, func) in self.mapping.iter_mut().enumerate() {

121

54406

                let was_satisfiable = *func.as_edge(manager) != *f_edge;

122

54406

                if was_satisfiable {

123

34209

                    *func = BDDFunction::from_edge(

124

34209

                        manager,

125

34209

                        BDDFunction::imp_strict_edge(

126

34209

                            manager,

127

34209

                            other.mapping[i].as_edge(manager),

128

34209

                            func.as_edge(manager),

129

)?,

130

);

131

34209

                    let is_satisfiable = *func.as_edge(manager) != *f_edge;

132

133

34209

                    if was_satisfiable && !is_satisfiable {

134

17784

                        self.non_empty_count -= 1;

135

17784

136

20197

137

138

139

2473

            Ok(())

140

2473

        })?;

141

142

2473

        Ok(self)

143

2473

144

145

    /// Computes the union between this submap and another submap.

146

2433

    pub fn or(mut self, manager_ref: &BDDManagerRef, other: &Submap) -> Result<Submap, MercError> {

147

2433

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

148

2433

            let f_edge = EdgeDropGuard::new(manager, BDDFunction::f_edge(manager));

149

150

53526

            for (i, func) in self.mapping.iter_mut().enumerate() {

151

53526

                let func_edge = func.as_edge(manager);

152

153

53526

                let was_satisfiable = *func_edge != *f_edge;

154

53526

                let new_func = BDDFunction::or_edge(manager, func_edge, other.mapping[i].as_edge(manager))?;

155

53526

                let is_satisfiable = new_func != *f_edge;

156

157

53526

                *func = BDDFunction::from_edge(manager, new_func);

158

159

53526

                if !was_satisfiable && is_satisfiable {

160

15558

                    self.non_empty_count += 1;

161

37968

162

163

164

2433

            Ok(())

165

2433

        })?;

166

167

2433

        Ok(self)

168

2433

169

170

    /// Computes the intersection between this submap and another function.

171

    pub fn and_function(

172

        mut self,

173

        manager_ref: &BDDManagerRef,

174

        configuration: &BDDFunction,

175

    ) -> Result<Submap, MercError> {

176

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

177

            let f_edge = EdgeDropGuard::new(manager, BDDFunction::f_edge(manager));

178

179

            for func in self.mapping.iter_mut() {

180

                let func_edge = func.as_edge(manager);

181

182

                let was_satisfiable = *func_edge != *f_edge;

183

                let new_func = BDDFunction::and_edge(manager, func_edge, configuration.as_edge(manager))?;

184

                let is_satisfiable = new_func != *f_edge;

185

186

                *func = BDDFunction::from_edge(manager, new_func);

187

188

                if was_satisfiable && !is_satisfiable {

189

                    self.non_empty_count -= 1;

190

191

192

193

            Ok(())

194

        })?;

195

196

        Ok(self)

197

198

199

    /// Computes the difference between this submap and another function.

200

1711

    pub fn minus_function(

201

1711

        mut self,

202

1711

        manager_ref: &BDDManagerRef,

203

1711

        configuration: &BDDFunction,

204

1711

    ) -> Result<Submap, MercError> {

205

1711

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

206

1711

            let f_edge = EdgeDropGuard::new(manager, BDDFunction::f_edge(manager));

207

1711

            let conf_edge = configuration.as_edge(manager);

208

209

37642

            for func in self.mapping.iter_mut() {

210

37642

                let func_edge = func.as_edge(manager);

211

212

37642

                let was_satisfiable = *func_edge != *f_edge;

213

37642

                let new_func = minus_edge(manager, func_edge, conf_edge)?;

214

37642

                let is_satisfiable = new_func != *f_edge;

215

216

37642

                *func = BDDFunction::from_edge(manager, new_func);

217

218

37642

                if was_satisfiable && !is_satisfiable {

219

4228

                    self.non_empty_count -= 1;

220

33414

221

222

223

1711

            Ok(())

224

1711

        })?;

225

226

1711

        Ok(self)

227

1711

228

229

    /// Returns an iterator over all entries.

230

233

    pub fn iter(&self) -> impl Iterator<Item = (VertexIndex, &BDDFunction)> {

231

233

        self.mapping

232

233

            .iter()

233

            .enumerate()

234

5126

            .map(|(i, func)| (VertexIndex::new(i), func))

235

233

236

237

238

impl Index<VertexIndex> for Submap {

239

    type Output = BDDFunction;

240

241

430984

    fn index(&self, index: VertexIndex) -> &Self::Output {

242

430984

        &self.mapping[*index]

243

430984

244

245

246

impl fmt::Debug for Submap {

247

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

248

        for (i, func) in self.mapping.iter().enumerate() {

249

            if func.satisfiable() {

250

                write!(f, " {} ({})", i, FormatConfigSet(func))?;

251

252

253

        Ok(())

254

255

256

257

#[cfg(test)]

258

mod tests {

259

    use merc_macros::merc_test;

260

    use oxidd::BooleanFunction;

261

    use oxidd::Manager;

262

    use oxidd::ManagerRef;

263

    use oxidd::bdd::BDDFunction;

264

    use oxidd::util::AllocResult;

265

266

    use crate::Submap;

267

    use crate::VertexIndex;

268

269

    #[merc_test]

270

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

271

    fn test_submap() {

272

        let manager_ref = oxidd::bdd::new_manager(2048, 1024, 1);

273

        let vars: Vec<BDDFunction> = manager_ref

274

1

            .with_manager_exclusive(|manager| {

275

3

                AllocResult::from_iter(manager.add_vars(3).map(|i| BDDFunction::var(manager, i)))

276

1

})

277

            .expect("Could not create variables");

278

279

1

        let false_bdd = manager_ref.with_manager_shared(|manager| BDDFunction::f(manager));

280

        let mut submap = Submap::new(&manager_ref, false_bdd.clone(), 3);

281

282

        assert_eq!(submap.len(), 3);

283

        assert_eq!(submap.non_empty_count, 0);

284

285

1

        manager_ref.with_manager_shared(|manager| {

286

1

            submap.set(manager, VertexIndex::new(0), vars[0].clone());

287

1

});

288

289

        assert_eq!(submap.non_empty_count, 1);

290

291