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

2267

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

40

        Self {

41

2267

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

42

2267

            non_empty_count: if initial.satisfiable() {

43

281

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

44

            } else {

45

1986

46

},

47

2267

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

48

49

2267

50

51

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

52

6000

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

53

6000

        &'a self,

54

6000

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

55

6000

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

56

6000

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

57

58

132000

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

59

132000

            if func.as_edge(manager) != f_edge {

60

61453

                Some(VertexIndex::new(i))

61

            } else {

62

70547

                None

63

64

132000

})

65

6000

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

21024

    pub fn set<'id>(

76

21024

        &mut self,

77

21024

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

78

21024

        index: VertexIndex,

79

21024

        func: BDDFunction,

80

21024

) {

81

21024

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

82

21024

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

83

84

21024

        self.mapping[*index] = func;

85

86

        // Update the non-empty count invariant.

87

21024

        if was_empty && !is_empty {

88

16916

            self.non_empty_count += 1;

89

16916

        } else if !was_empty && is_empty {

90

            self.non_empty_count -= 1;

91

4108

92

21024

93

94

    /// Returns true iff the submap is empty.

95

5065

    pub fn is_empty(&self) -> bool {

96

5065

        self.non_empty_count == 0

97

5065

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

2799

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

118

2799

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

119

2799

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

120

61578

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

121

61578

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

122

61578

                if was_satisfiable {

123

38260

                    *func = BDDFunction::from_edge(

124

38260

                        manager,

125

38260

                        BDDFunction::imp_strict_edge(

126

38260

                            manager,

127

38260

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

128

38260

                            func.as_edge(manager),

129

)?,

130

);

131

38260

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

132

133

38260

                    if was_satisfiable && !is_satisfiable {

134

19944

                        self.non_empty_count -= 1;

135

19944

136

23318

137

138

139

2799

            Ok(())

140

2799

        })?;

141

142

2799

        Ok(self)

143

2799

144

145

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

146

2809

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

147

2809

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

148

2809

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

149

150

61798

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

151

61798

                let func_edge = func.as_edge(manager);

152

153

61798

                let was_satisfiable = *func_edge != *f_edge;

154

61798

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

155

61798

                let is_satisfiable = new_func != *f_edge;

156

157

61798

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

158

159

61798

                if !was_satisfiable && is_satisfiable {

160

17440

                    self.non_empty_count += 1;

161

44358

162

163

164

2809

            Ok(())

165

2809

        })?;

166

167

2809

        Ok(self)

168

2809

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

2069

    pub fn minus_function(

201

2069

        mut self,

202

2069

        manager_ref: &BDDManagerRef,

203

2069

        configuration: &BDDFunction,

204

2069

    ) -> Result<Submap, MercError> {

205

2069

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

206

2069

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

207

2069

            let conf_edge = configuration.as_edge(manager);

208

209

45518

            for func in self.mapping.iter_mut() {

210

45518

                let func_edge = func.as_edge(manager);

211

212

45518

                let was_satisfiable = *func_edge != *f_edge;

213

45518

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

214

45518

                let is_satisfiable = new_func != *f_edge;

215

216

45518

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

217

218

45518

                if was_satisfiable && !is_satisfiable {

219

5090

                    self.non_empty_count -= 1;

220

40428

221

222

223

2069

            Ok(())

224

2069

        })?;

225

226

2069

        Ok(self)

227

2069

228

229

    /// Returns an iterator over all entries.

230

281

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

231

281

        self.mapping

232

281

            .iter()

233

281

            .enumerate()

234

6182

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

235

281

236

237

238

impl Index<VertexIndex> for Submap {

239

    type Output = BDDFunction;

240

241

478385

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

242

478385

        &self.mapping[*index]

243

478385

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