-
Notifications
You must be signed in to change notification settings - Fork 21
/
solver.go
124 lines (101 loc) · 3.44 KB
/
solver.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package solver
import (
"context"
"errors"
"github.com/operator-framework/deppy/internal/solver"
"github.com/operator-framework/deppy/pkg/deppy"
"github.com/operator-framework/deppy/pkg/deppy/input"
)
// TODO: should disambiguate between solver errors due to constraints
// and other generic errors (e.g. entity source not reachable, etc.)
// Solution is returned by the Solver when the internal solver executed successfully.
// A successful execution of the solver can still end in an error when no solution can
// be found.
type Solution struct {
err error
selection map[deppy.Identifier]deppy.Variable
variables []deppy.Variable
}
// Error returns the resolution error in case the problem is unsat
// on successful resolution, it will return nil
func (s *Solution) Error() error {
return s.err
}
// SelectedVariables returns the variables that were selected by the solver
// as part of the solution
func (s *Solution) SelectedVariables() map[deppy.Identifier]deppy.Variable {
return s.selection
}
// IsSelected returns true if the variable identified by the identifier was selected
// in the solution by the resolver. It will return false otherwise.
func (s *Solution) IsSelected(identifier deppy.Identifier) bool {
_, ok := s.selection[identifier]
return ok
}
// AllVariables returns all the variables that were considered by the solver to obtain (or not)
// a solution. Note: This is only be present if the AddAllVariablesToSolution option is passed in to the
// Solve call that generated the solution.
func (s *Solution) AllVariables() []deppy.Variable {
return s.variables
}
type solutionOptions struct {
addVariablesToSolution bool
}
func (s *solutionOptions) apply(options ...Option) *solutionOptions {
for _, applyOption := range options {
applyOption(s)
}
return s
}
func defaultSolutionOptions() *solutionOptions {
return &solutionOptions{
addVariablesToSolution: false,
}
}
type Option func(solutionOptions *solutionOptions)
// AddAllVariablesToSolution is a Solve option that instructs the solver to include
// all the variables considered to the Solution it produces
func AddAllVariablesToSolution() Option {
return func(solutionOptions *solutionOptions) {
solutionOptions.addVariablesToSolution = true
}
}
// DeppySolver is a simple solver implementation that takes an entity source group and a constraint aggregator
// to produce a Solution (or error if no solution can be found)
type DeppySolver struct {
variableSource input.VariableSource
}
func NewDeppySolver(variableSource input.VariableSource) *DeppySolver {
return &DeppySolver{
variableSource: variableSource,
}
}
func (d DeppySolver) Solve(ctx context.Context, options ...Option) (*Solution, error) {
solutionOpts := defaultSolutionOptions().apply(options...)
vars, err := d.variableSource.GetVariables(ctx)
if err != nil {
return nil, err
}
satSolver, err := solver.NewSolver(solver.WithInput(vars))
if err != nil {
return nil, err
}
selection, err := satSolver.Solve(ctx)
if err != nil && !errors.As(err, &deppy.NotSatisfiable{}) {
return nil, err
}
selectionMap := map[deppy.Identifier]deppy.Variable{}
for _, variable := range selection {
selectionMap[variable.Identifier()] = variable
}
solution := &Solution{selection: selectionMap}
if err != nil {
unsatError := deppy.NotSatisfiable{}
errors.As(err, &unsatError)
solution.err = unsatError
}
if solutionOpts.addVariablesToSolution {
solution.variables = vars
}
return solution, nil
}