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

2225

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

40

        Self {

41

2225

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

42

2225

            non_empty_count: if initial.satisfiable() {

43

278

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

44

            } else {

45

1947

46

},

47

2225

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

48

49

2225

50

51

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

52

5878

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

53

5878

        &'a self,

54

5878

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

55

5878

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

56

5878

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

57

58

129316

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

59

129316

            if func.as_edge(manager) != f_edge {

60

60564

                Some(VertexIndex::new(i))

61

            } else {

62

68752

                None

63

64

129316

})

65

5878

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

20298

    pub fn set<'id>(

76

20298

        &mut self,

77

20298

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

78

20298

        index: VertexIndex,

79

20298

        func: BDDFunction,

80

20298

) {

81

20298

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

82

20298

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

83

84

20298

        self.mapping[*index] = func;

85

86

        // Update the non-empty count invariant.

87

20298

        if was_empty && !is_empty {

88

16314

            self.non_empty_count += 1;

89

16314

        } else if !was_empty && is_empty {

90

            self.non_empty_count -= 1;

91

3984

92

20298

93

94

    /// Returns true iff every vertex maps to the empty configuration.

95

4965

    pub fn is_all_empty_set(&self) -> bool {

96

4965

        self.non_empty_count == 0

97

4965

98

99

    /// Returns the number of entries in the submap, i.e. the number of vertices.

100

1

    pub fn len(&self) -> usize {

101

1

        self.mapping.len()

102

1

103

104

    /// Returns true iff the submap has no entries.

105

    pub fn is_empty(&self) -> bool {

106

        self.mapping.is_empty()

107

108

109

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

110

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

111

        manager_ref.with_manager_shared(|manager| {

112

            for func in self.mapping.iter_mut() {

113

                *func = BDDFunction::f(manager);

114

115

            self.non_empty_count = 0;

116

});

117

118

        Ok(())

119

120

121

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

122

2741

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

123

2741

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

124

2741

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

125

60302

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

126

60302

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

127

60302

                if was_satisfiable {

128

37754

                    *func = BDDFunction::from_edge(

129

37754

                        manager,

130

37754

                        BDDFunction::imp_strict_edge(

131

37754

                            manager,

132

37754

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

133

37754

                            func.as_edge(manager),

134

)?,

135

);

136

37754

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

137

138

                    // `was_satisfiable` is already true in this branch.

139

37754

                    if !is_satisfiable {

140

19719

                        self.non_empty_count -= 1;

141

19719

142

22548

143

144

145

2741

            Ok(())

146

2741

        })?;

147

148

2741

        Ok(self)

149

2741

150

151

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

152

2737

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

153

2737

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

154

2737

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

155

156

60214

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

157

60214

                let func_edge = func.as_edge(manager);

158

159

60214

                let was_satisfiable = *func_edge != *f_edge;

160

60214

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

161

60214

                let is_satisfiable = new_func != *f_edge;

162

163

60214

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

164

165

60214

                if !was_satisfiable && is_satisfiable {

166

17062

                    self.non_empty_count += 1;

167

43152

168

169

170

2737

            Ok(())

171

2737

        })?;

172

173

2737

        Ok(self)

174

2737

175

176

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

177

    pub fn and_function(

178

        mut self,

179

        manager_ref: &BDDManagerRef,

180

        configuration: &BDDFunction,

181

    ) -> Result<Submap, MercError> {

182

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

183

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

184

185

            for func in self.mapping.iter_mut() {

186

                let func_edge = func.as_edge(manager);

187

188

                let was_satisfiable = *func_edge != *f_edge;

189

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

190

                let is_satisfiable = new_func != *f_edge;

191

192

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

193

194

                if was_satisfiable && !is_satisfiable {

195

                    self.non_empty_count -= 1;

196

197

198

199

            Ok(())

200

        })?;

201

202

        Ok(self)

203

204

205

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

206

1993

    pub fn minus_function(

207

1993

        mut self,

208

1993

        manager_ref: &BDDManagerRef,

209

1993

        configuration: &BDDFunction,

210

1993

    ) -> Result<Submap, MercError> {

211

1993

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

212

1993

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

213

1993

            let conf_edge = configuration.as_edge(manager);

214

215

43846

            for func in self.mapping.iter_mut() {

216

43846

                let func_edge = func.as_edge(manager);

217

218

43846

                let was_satisfiable = *func_edge != *f_edge;

219

43846

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

220

43846

                let is_satisfiable = new_func != *f_edge;

221

222

43846

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

223

224

43846

                if was_satisfiable && !is_satisfiable {

225

4860

                    self.non_empty_count -= 1;

226

38986

227

228

229

1993

            Ok(())

230

1993

        })?;

231

232

1993

        Ok(self)

233

1993

234

235

    /// Returns an iterator over all entries.

236

271

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

237

271

        self.mapping

238

271

            .iter()

239

271

            .enumerate()

240

5962

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

241

271

242

243

244

impl Index<VertexIndex> for Submap {

245

    type Output = BDDFunction;

246

247

463131

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

248

463131

        &self.mapping[*index]

249

463131

250

251

252

impl fmt::Debug for Submap {

253

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

254

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

255

            if func.satisfiable() {

256

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

257

258

259

        Ok(())

260

261

262

263

#[cfg(test)]

264

mod tests {

265

    use merc_macros::merc_test;

266

    use oxidd::BooleanFunction;

267

    use oxidd::Manager;

268

    use oxidd::ManagerRef;

269

    use oxidd::bdd::BDDFunction;

270

    use oxidd::util::AllocResult;

271

272

    use crate::Submap;

273

    use crate::VertexIndex;

274

275

    #[merc_test]

276

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

277

    fn test_submap() {

278

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

279

        let vars: Vec<BDDFunction> = manager_ref

280

1

            .with_manager_exclusive(|manager| {

281

3

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

282

1

})

283

            .expect("Could not create variables");

284

285

1

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

286

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

287

288

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

289

        assert_eq!(submap.non_empty_count, 0);

290

291

1

        manager_ref.with_manager_shared(|manager| {

292

1

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

293

1

});

294

295

        assert_eq!(submap.non_empty_count, 1);

296

297