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

2329

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

40

        Self {

41

2329

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

42

2329

            non_empty_count: if initial.satisfiable() {

43

298

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

44

            } else {

45

2031

46

},

47

2329

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

48

49

2329

50

51

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

52

6149

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

53

6149

        &'a self,

54

6149

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

55

6149

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

56

6149

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

57

58

135278

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

59

135278

            if func.as_edge(manager) != f_edge {

60

57380

                Some(VertexIndex::new(i))

61

            } else {

62

77898

                None

63

64

135278

})

65

6149

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

21173

    pub fn set<'id>(

76

21173

        &mut self,

77

21173

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

78

21173

        index: VertexIndex,

79

21173

        func: BDDFunction,

80

21173

) {

81

21173

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

82

21173

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

83

84

21173

        self.mapping[*index] = func;

85

86

        // Update the non-empty count invariant.

87

21173

        if was_empty && !is_empty {

88

15846

            self.non_empty_count += 1;

89

15846

        } else if !was_empty && is_empty {

90

            self.non_empty_count -= 1;

91

5327

92

21173

93

94

    /// Returns true iff the submap is empty.

95

5194

    pub fn is_empty(&self) -> bool {

96

5194

        self.non_empty_count == 0

97

5194

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

2866

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

118

2866

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

119

2866

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

120

63052

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

121

63052

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

122

63052

                if was_satisfiable {

123

35956

                    *func = BDDFunction::from_edge(

124

35956

                        manager,

125

35956

                        BDDFunction::imp_strict_edge(

126

35956

                            manager,

127

35956

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

128

35956

                            func.as_edge(manager),

129

)?,

130

);

131

35956

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

132

133

35956

                    if was_satisfiable && !is_satisfiable {

134

19766

                        self.non_empty_count -= 1;

135

19766

136

27096

137

138

139

2866

            Ok(())

140

2866

        })?;

141

142

2866

        Ok(self)

143

2866

144

145

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

146

2862

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

147

2862

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

148

2862

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

149

150

62964

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

151

62964

                let func_edge = func.as_edge(manager);

152

153

62964

                let was_satisfiable = *func_edge != *f_edge;

154

62964

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

155

62964

                let is_satisfiable = new_func != *f_edge;

156

157

62964

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

158

159

62964

                if !was_satisfiable && is_satisfiable {

160

15313

                    self.non_empty_count += 1;

161

47651

162

163

164

2862

            Ok(())

165

2862

        })?;

166

167

2862

        Ok(self)

168

2862

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

2063

    pub fn minus_function(

201

2063

        mut self,

202

2063

        manager_ref: &BDDManagerRef,

203

2063

        configuration: &BDDFunction,

204

2063

    ) -> Result<Submap, MercError> {

205

2063

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

206

2063

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

207

2063

            let conf_edge = configuration.as_edge(manager);

208

209

45386

            for func in self.mapping.iter_mut() {

210

45386

                let func_edge = func.as_edge(manager);

211

212

45386

                let was_satisfiable = *func_edge != *f_edge;

213

45386

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

214

45386

                let is_satisfiable = new_func != *f_edge;

215

216

45386

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

217

218

45386

                if was_satisfiable && !is_satisfiable {

219

4479

                    self.non_empty_count -= 1;

220

40907

221

222

223

2063

            Ok(())

224

2063

        })?;

225

226

2063

        Ok(self)

227

2063

228

229

    /// Returns an iterator over all entries.

230

278

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

231

278

        self.mapping

232

278

            .iter()

233

278

            .enumerate()

234

6116

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

235

278

236

237

238

impl Index<VertexIndex> for Submap {

239

    type Output = BDDFunction;

240

241

332661

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

242

332661

        &self.mapping[*index]

243

332661

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