Grcov report - builder.rs

1

#![forbid(unsafe_code)]

2

3

use oxidd::BooleanFunction;

4

use oxidd::bdd::BDDFunction;

5

use oxidd::bdd::BDDManagerRef;

6

7

use crate::ParityGame;

8

use crate::Player;

9

use crate::Priority;

10

use crate::VariabilityParityGame;

11

use crate::VertexIndex;

12

13

/// A builder for parity games that accepts edges one by one and can remove

14

/// duplicates.

15

pub struct ParityGameBuilder {

16

    /// The edges of the parity game.

17

    edges: Vec<(VertexIndex, VertexIndex)>,

18

19

    /// The owner of each vertex, indexed by vertex index.

20

    owners: Vec<Player>,

21

22

    /// The priority of each vertex, indexed by vertex index.

23

    priorities: Vec<Priority>,

24

25

    /// The initial vertex of the game.

26

    initial_vertex: VertexIndex,

27

28

    /// The number of vertices discovered so far.

29

    num_of_vertices: usize,

30

31

32

impl ParityGameBuilder {

33

    /// Initializes a new empty builder with the given initial vertex.

34

1500

    pub fn new(initial_vertex: VertexIndex) -> Self {

35

1500

        Self::with_capacity(initial_vertex, 0)

36

1500

37

38

    /// Initializes the builder with pre-allocated capacity for edges.

39

1601

    pub fn with_capacity(initial_vertex: VertexIndex, num_of_edges: usize) -> Self {

40

1601

        let num_of_vertices = initial_vertex.value() + 1;

41

1601

        Self {

42

1601

            edges: Vec::with_capacity(num_of_edges),

43

1601

            owners: vec![Player::Even; num_of_vertices],

44

1601

            priorities: vec![Priority::new(0); num_of_vertices],

45

1601

            initial_vertex,

46

1601

            num_of_vertices,

47

1601

48

1601

49

50

    /// Adds a vertex to the builder with its owner and priority.

51

76103

    pub fn add_vertex(&mut self, vertex: VertexIndex, owner: Player, priority: Priority) {

52

76103

        let num_of_vertices = vertex.value() + 1;

53

76103

        self.ensure_vertex_capacity(num_of_vertices);

54

76103

        self.owners[vertex.value()] = owner;

55

76103

        self.priorities[vertex.value()] = priority;

56

76103

        self.num_of_vertices = self.num_of_vertices.max(num_of_vertices);

57

76103

58

59

    /// Adds an edge to the builder.

60

107659

    pub fn add_edge(&mut self, from: VertexIndex, to: VertexIndex) {

61

107659

        self.edges.push((from, to));

62

107659

        let num_of_vertices = self.num_of_vertices.max(from.value() + 1).max(to.value() + 1);

63

107659

        self.ensure_vertex_capacity(num_of_vertices);

64

107659

        self.num_of_vertices = num_of_vertices;

65

107659

66

67

    /// Returns the number of edges added to the builder.

68

    pub fn num_of_edges(&self) -> usize {

69

        self.edges.len()

70

71

72

    /// Returns the number of vertices that the builder currently found.

73

    pub fn num_of_vertices(&self) -> usize {

74

        self.num_of_vertices

75

76

77

    /// Finalizes the builder and returns the constructed parity game.

78

1601

    pub fn finish(mut self, make_total: bool, remove_duplicates: bool) -> ParityGame {

79

1601

        if remove_duplicates {

80

1601

            self.remove_duplicates();

81

1601

82

83

1601

        self.ensure_vertex_capacity(self.num_of_vertices);

84

85

        // Destructure so the edge closure can borrow `edges` while `owners` and

86

        // `priorities` are moved into `from_edges`, avoiding a full edge clone.

87

        let Self {

88

1601

            edges,

89

1601

            owners,

90

1601

            priorities,

91

1601

            initial_vertex,

92

..

93

1601

        } = self;

94

3202

        ParityGame::from_edges(initial_vertex, owners, priorities, make_total, || edges.iter().cloned())

95

1601

96

97

    /// Ensures that the owners and priorities vectors have enough capacity for the given number of vertices.

98

185363

    fn ensure_vertex_capacity(&mut self, num_of_vertices: usize) {

99

185363

        if self.owners.len() < num_of_vertices {

100

66601

            self.owners.resize(num_of_vertices, Player::Even);

101

118762

102

185363

        if self.priorities.len() < num_of_vertices {

103

66601

            self.priorities.resize(num_of_vertices, Priority::new(0));

104

118762

105

185363

106

107

    /// Removes duplicated edges from the added edges.

108

1601

    fn remove_duplicates(&mut self) {

109

1601

        self.edges.sort();

110

1601

        self.edges.dedup();

111

1601

112

113

114

/// A builder for variability parity games that accepts edges with BDD configurations

115

/// one by one and can remove duplicates.

116

pub struct VariabilityParityGameBuilder {

117

    /// The edges of the variability parity game with their configurations.

118

    edges: Vec<(VertexIndex, oxidd::bdd::BDDFunction, VertexIndex)>,

119

120

    /// The owner of each vertex, indexed by vertex index.

121

    owners: Vec<Player>,

122

123

    /// The priority of each vertex, indexed by vertex index.

124

    priorities: Vec<Priority>,

125

126

    /// The initial vertex of the game.

127

    initial_vertex: VertexIndex,

128

129

    /// The number of vertices discovered so far.

130

    num_of_vertices: usize,

131

132

133

impl VariabilityParityGameBuilder {

134

    /// Initializes a new empty builder with the given initial vertex.

135

    pub fn new(initial_vertex: VertexIndex) -> Self {

136

        Self::with_capacity(initial_vertex, 0)

137

138

139

    /// Initializes the builder with pre-allocated capacity for edges.

140

302

    pub fn with_capacity(initial_vertex: VertexIndex, num_of_edges: usize) -> Self {

141

302

        let num_of_vertices = initial_vertex.value() + 1;

142

302

        Self {

143

302

            edges: Vec::with_capacity(num_of_edges),

144

302

            owners: vec![Player::Even; num_of_vertices],

145

302

            priorities: vec![Priority::new(0); num_of_vertices],

146

302

            initial_vertex,

147

302

            num_of_vertices,

148

302

149

302

150

151

    /// Adds a vertex to the builder with its owner and priority.

152

8627

    pub fn add_vertex(&mut self, vertex: VertexIndex, owner: Player, priority: Priority) {

153

8627

        let num_of_vertices = vertex.value() + 1;

154

8627

        self.ensure_vertex_capacity(num_of_vertices);

155

8627

        self.owners[vertex.value()] = owner;

156

8627

        self.priorities[vertex.value()] = priority;

157

8627

        self.num_of_vertices = self.num_of_vertices.max(num_of_vertices);

158

8627

159

160

    /// Adds an edge to the builder with its configuration.

161

16510

    pub fn add_edge(&mut self, from: VertexIndex, configuration: oxidd::bdd::BDDFunction, to: VertexIndex) {

162

16510

        self.edges.push((from, configuration, to));

163

16510

        let num_of_vertices = self.num_of_vertices.max(from.value() + 1).max(to.value() + 1);

164

16510

        self.ensure_vertex_capacity(num_of_vertices);

165

16510

        self.num_of_vertices = num_of_vertices;

166

16510

167

168

    /// Returns the number of edges added to the builder.

169

    pub fn num_of_edges(&self) -> usize {

170

        self.edges.len()

171

172

173

    /// Returns the number of vertices that the builder currently found.

174

601

    pub fn num_of_vertices(&self) -> usize {

175

601

        self.num_of_vertices

176

601

177

178

    /// Consumes the builder and returns the constructed variability parity game.

179

302

    pub fn finish(

180

302

        mut self,

181

302

        manager_ref: &BDDManagerRef,

182

302

        configuration: BDDFunction,

183

302

        variables: Vec<BDDFunction>,

184

302

        remove_duplicates: bool,

185

302

    ) -> VariabilityParityGame {

186

302

        if remove_duplicates {

187

1

            self.remove_duplicates();

188

301

189

190

302

        self.ensure_vertex_capacity(self.num_of_vertices);

191

192

        // Destructure so the edge closure can borrow `edges` while `owners` and

193

        // `priorities` are moved into `from_edges`, avoiding a full edge clone.

194

        let Self {

195

302

            edges,

196

302

            owners,

197

302

            priorities,

198

302

            initial_vertex,

199

..

200

302

        } = self;

201

302

        VariabilityParityGame::from_edges(

202

302

            manager_ref,

203

302

            initial_vertex,

204

302

            owners,

205

302

            priorities,

206

302

            configuration,

207

302

            variables,

208

604

            || edges.iter().cloned(),

209

210

302

211

212

    /// Ensures that the owners and priorities vectors have enough capacity for the given number of vertices.

213

25439

    fn ensure_vertex_capacity(&mut self, num_of_vertices: usize) {

214

25439

        if self.owners.len() < num_of_vertices {

215

5324

            self.owners.resize(num_of_vertices, Player::Even);

216

20115

217

25439

        if self.priorities.len() < num_of_vertices {

218

5324

            self.priorities.resize(num_of_vertices, Priority::new(0));

219

20115

220

25439

221

222

    /// Removes duplicated edges from the added edges.

223

1

    fn remove_duplicates(&mut self) {

224

77638

        self.edges.sort_by_key(|(from, _, to)| (*from, *to));

225

226

1

        let mut merged: Vec<(VertexIndex, BDDFunction, VertexIndex)> = Vec::with_capacity(self.edges.len());

227

4409

        for (from, configuration, to) in self.edges.drain(..) {

228

4409

            if let Some((last_from, last_configuration, last_to)) = merged.last_mut()

229

4408

                && *last_from == from

230

1407

                && *last_to == to

231

232

1

                *last_configuration = last_configuration

233

1

                    .or(&configuration)

234

1

                    .expect("Duplicate edges should have compatible BDD managers");

235

1

                continue;

236

4408

237

238

4408

            merged.push((from, configuration, to));

239

240

241

1

        self.edges = merged;

242

1

243