Grcov report - instantiate.rs

1

use crate::{

2

    Model,

3

    ast::{DeclarationKind, DeclarationPtr, Literal, declaration::Declaration, eval_constant},

4

};

5

use anyhow::anyhow;

6

7

/// Instantiate a problem model with values from a parameter model.

8

///

9

/// For each `given` declaration in `problem_model`, this looks for a corresponding value `letting`

10

/// in `param_model`, checks it is a constant and within the given domain, and replaces the `given`

11

/// with a value-letting in the returned model.

12

168456

pub fn instantiate_model(mut problem_model: Model, param_model: Model) -> anyhow::Result<Model> {

13

168456

    let symbol_table = problem_model.symbols_ptr_unchecked().write();

14

168456

    let param_table = param_model.symbols_ptr_unchecked().write();

15

168456

    let mut pending_givens = symbol_table

16

168456

        .iter_local()

17

535693

        .filter_map(|(name, decl)| decl.as_given().map(|_| name.clone()))

18

        .collect::<Vec<_>>();

19

20

168456

    while !pending_givens.is_empty() {

21

166426

        let mut next_pending = Vec::new();

22

166426

        let mut made_progress = false;

23

24

166426

        for name in pending_givens {

25

242788

            let mut decl = symbol_table

26

242788

                .lookup_local(&name)

27

                .ok_or_else(|| anyhow!("Given declaration `{name}` not found in problem model"))?;

28

29

242788

            let Some(domain) = decl.as_given() else {

30

                continue;

31

};

32

33

242788

            let param_decl = param_table.lookup(&name);

34

242788

            let expr = param_decl

35

242788

                .as_ref()

36

242788

                .and_then(DeclarationPtr::as_value_letting)

37

66

                .ok_or_else(|| {

38

66

                    anyhow!(

39

66

                        "Given declaration `{name}` does not have corresponding letting in parameter file"

40

41

66

                })?;

42

43

242722

            let expr_value = eval_constant(&expr)

44

                .ok_or_else(|| anyhow!("Letting expression `{expr}` cannot be evaluated"))?;

45

46

242722

            let Ok(ground_domain) = domain.resolve() else {

47

                next_pending.push(name);

48

                continue;

49

};

50

51

242722

            if !ground_domain.contains(&expr_value)? {

52

8

                return Err(anyhow!(

53

8

                    "Domain of given statement `{name}` does not contain letting value"

54

8

));

55

242714

56

57

            // The given domain is a validity check, but after instantiation the parameter is a

58

            // constant. Keep the tighter domain inferred from its value when possible so bounds

59

            // derived from instantiated parameters (for example optimisation auxiliaries) stay

60

            // finite.

61

242714

            let instantiated_domain = expr.domain_of().unwrap_or_else(|| domain.clone());

62

242714

            let new_decl = Declaration::new(

63

242714

                name.clone(),

64

242714

                DeclarationKind::ValueLetting(expr.clone(), Some(instantiated_domain)),

65

242714

);

66

242714

            drop(domain);

67

242714

            decl.replace(new_decl);

68

242714

            made_progress = true;

69

70

242714

            tracing::info!("Replaced {name} given with letting.");

71

72

73

166352

        if next_pending.is_empty() {

74

166352

            break;

75

76

77

        if !made_progress {

78

            return Err(anyhow!(

79

                "Domain of given statement `{}` cannot be resolved",

80

                next_pending[0]

81

));

82

83

84

        pending_givens = next_pending;

85

86

87

168382

    drop(symbol_table);

88

168382

    ground_collection_valued_domains(&mut problem_model);

89

168382

    validate_instantiation_conditions(&mut problem_model)?;

90

168382

    Ok(problem_model)

91

168456

92

93

/// Evaluate and remove all top-level `where` conditions after parameter instantiation.

94

1215464

pub fn validate_instantiation_conditions(model: &mut Model) -> anyhow::Result<()> {

95

1215464

    for condition in model.take_instantiation_conditions() {

96

232

        match eval_constant(&condition) {

97

232

            Some(Literal::Bool(true)) => {}

98

            Some(Literal::Bool(false)) => {

99

                return Err(anyhow!(

100

                    "invalid instance: where condition `{condition}` evaluated to false"

101

));

102

103

            Some(value) => {

104

                return Err(anyhow!(

105

                    "where condition `{condition}` evaluated to non-boolean value `{value}`"

106

));

107

108

            None => {

109

                return Err(anyhow!(

110

                    "could not evaluate where condition `{condition}` after parameter instantiation"

111

));

112

113

114

115

1215464

    Ok(())

116

1215464

117

118

#[cfg(test)]

119

mod tests {

120

    use super::*;

121

    use crate::ast::{

122

        Atom, Domain, Expression, GroundDomain, IntVal, Metadata, Name, Objective,

123

        OptimiseDirection, Range, Reference,

124

};

125

126

    #[test]

127

1

    fn instantiated_given_uses_the_tighter_value_domain() {

128

1

        let name = Name::user("n");

129

1

        let mut problem = Model::default();

130

1

        problem

131

1

            .add_symbol(DeclarationPtr::new_given(

132

1

                name.clone(),

133

1

                Domain::int(vec![Range::UnboundedR(1)]),

134

1

))

135

1

            .unwrap();

136

137

1

        let mut parameters = Model::default();

138

1

        parameters

139

1

            .add_symbol(DeclarationPtr::new_value_letting(

140

1

                name.clone(),

141

1

                crate::ast::Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Int(7))),

142

1

))

143

1

            .unwrap();

144

145

1

        let instantiated = instantiate_model(problem, parameters).unwrap();

146

1

        let declaration = instantiated

147

1

            .symbols()

148

1

            .lookup(&name)

149

1

            .expect("instantiated parameter should exist");

150

151

1

        assert_eq!(

152

1

            declaration.domain().unwrap().resolve().unwrap().as_ref(),

153

1

            &GroundDomain::Int(vec![Range::Single(7)], None)

154

);

155

1

156

157

    #[test]

158

1

    fn instantiation_invalidates_cached_expression_domains() {

159

1

        let parameter_name = Name::user("n");

160

1

        let parameter = DeclarationPtr::new_given(

161

1

            parameter_name.clone(),

162

1

            Domain::int(vec![Range::UnboundedR(1)]),

163

1

);

164

1

        let variable = DeclarationPtr::new_find(

165

1

            Name::user("x"),

166

1

            Domain::int(vec![Range::Bounded(

167

1

                IntVal::Const(1),

168

1

                IntVal::Reference(Reference::new(parameter.clone())),

169

1

            )]),

170

1

);

171

1

        let reference = Expression::Atomic(Metadata::new(), Atom::new_ref(variable.clone()));

172

173

1

        let mut problem = Model::default();

174

1

        problem.add_symbol(parameter).unwrap();

175

1

        problem.add_symbol(variable).unwrap();

176

1

        problem.objective = Some(Objective {

177

1

            direction: OptimiseDirection::Minimising,

178

1

            expression: reference,

179

1

});

180

181

1

        let cached_domain = problem

182

1

            .objective

183

1

            .as_ref()

184

1

            .unwrap()

185

1

            .expression

186

1

            .domain_of()

187

1

            .unwrap();

188

1

        assert!(cached_domain.resolve().is_err());

189

190

1

        let mut parameters = Model::default();

191

1

        parameters

192

1

            .add_symbol(DeclarationPtr::new_value_letting(

193

1

                parameter_name,

194

1

                Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Int(7))),

195

1

))

196

1

            .unwrap();

197

198

1

        let instantiated = instantiate_model(problem, parameters).unwrap();

199

1

        let objective_domain = instantiated

200

1

            .objective

201

1

            .as_ref()

202

1

            .unwrap()

203

1

            .expression

204

1

            .domain_of()

205

1

            .unwrap();

206

207

1

        assert_eq!(

208

1

            objective_domain.resolve().unwrap().as_ref(),

209

1

            &GroundDomain::Int(vec![Range::Bounded(1, 7)], None)

210

);

211

1

212

213

214

/// Grounds declaration domains that take their values from a collection expression.

215

///

216

/// `int([i | i <- nums])` stays an expression until the parameters arrive, and resolving it means

217

/// evaluating the collection afresh -- which the rewriter would otherwise do on every domain

218

/// query, per node per rule attempt. Doing it once here is the difference between a second and

219

/// twenty minutes.

220

///

221

/// Only these domains are grounded. Resolving every domain is not safe to do blindly: a full-width

222

/// `int` resolves to an enormous ground domain.

223

168382

fn ground_collection_valued_domains(model: &mut Model) {

224

168382

    for (_, decl) in model.symbols_mut().iter_local_mut() {

225

        // Only decision variables, and reached through `as_find_mut` rather than `domain()`:

226

        // the latter computes a domain for every declaration, which for a value letting over a

227

        // large expression is itself expensive.

228

535545

        let Some(mut var) = decl.as_find_mut() else {

229

289219

            continue;

230

};

231

246326

        if !crate::ast::domain_has_int_from_values(&var.domain) {

232

246326

            continue;

233

234

        let Ok(ground) = var.domain.resolve() else {

235

            continue;

236

};

237

        var.domain = ground.into();

238

239

168382