-
Notifications
You must be signed in to change notification settings - Fork 68
/
DBPlanner.class.st
247 lines (212 loc) · 7.87 KB
/
DBPlanner.class.st
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
"
This benchmark is an implementation of the DeltaBlue Constraint Solver described in `The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver'', by Bjorn N. Freeman-Benson and John Maloney, Communications of the ACM, January 1990 (also as University of Washington TR 89-08-06).
"
Class {
#name : #DBPlanner,
#superclass : #Object,
#instVars : [
'currentMark'
],
#classInstVars : [
'currentPlanner'
],
#category : #'CogBenchmarks-DeltaBlue'
}
{ #category : #accessing }
DBPlanner class >> current [
^ currentPlanner
]
{ #category : #'instance creation' }
DBPlanner class >> new [
^ currentPlanner := super new
]
{ #category : #private }
DBPlanner >> addConstraintsConsuming: v to: aCollection [
| determiningC |
determiningC := v determinedBy.
v constraints do:
[ :c |
(c == determiningC or: [c isSatisfied not]) ifFalse:
[aCollection add: c]].
]
{ #category : #private }
DBPlanner >> addPropagate: c mark: mark [
"Recompute the walkabout strengths and stay flags of all variables
downstream of the given constraint and recompute the actual values
of all variables whose stay flag is true. If a cycle is detected,
remove the given constraint and answer false. Otherwise, answer true.
Details: Cycles are detected when a marked variable is encountered
downstream of the given constraint. The sender is assumed to have
marked the inputs of the given constraint with the given mark. Thus,
encountering a marked node downstream of the output constraint means
that there is a path from the constraint's output to one of its
inputs."
| todo d |
todo := OrderedCollection with: c.
[todo isEmpty] whileFalse:
[d := todo removeFirst.
(d output mark = mark) ifTrue:
[self incrementalRemove: c.
^ false].
d recalculate.
self addConstraintsConsuming: d output to: todo].
^ true
]
{ #category : #private }
DBPlanner >> changeVar: aVariable newValue: newValue [
| editConstraint plan |
editConstraint := DBEditConstraint var: aVariable strength: #preferred.
plan := self extractPlanFromConstraints: (Array with: editConstraint).
10 timesRepeat: [
aVariable value: newValue.
plan execute].
editConstraint destroyConstraint.
]
{ #category : #private }
DBPlanner >> constraintsConsuming: v do: aBlock [
| determiningC |
determiningC := v determinedBy.
v constraints do:
[ :c |
(c == determiningC or: [c isSatisfied not]) ifFalse:
[aBlock value: c]].
]
{ #category : #planning }
DBPlanner >> extractPlanFromConstraints: constraints [
"Extract a plan for resatisfaction starting from the outputs of the
given constraints, usually a set of input constraints."
| sources |
sources := OrderedCollection new.
constraints do:
[: c | (c isInput and: [c isSatisfied]) ifTrue: [sources add: c]].
^self makePlan: sources
]
{ #category : #planning }
DBPlanner >> extractPlanFromVariables: variables [
"Extract a plan from the dataflow graph having the given variables. It
is assumed that the given set of variables is complete, or at least
that it contains all the input variables."
| sources |
sources := OrderedCollection new.
variables do:
[: v |
(v constraints) do:
[: c | (c isInput and: [c isSatisfied]) ifTrue: [sources add: c]]].
^self makePlan: sources
]
{ #category : #adding }
DBPlanner >> incrementalAdd: c [
"Attempt to satisfy the given constraint and, if successful,
incrementally update the dataflow graph.
Details: If satifying the constraint is successful, it may override a
weaker constraint on its output. The algorithm attempts to resatisfy
that constraint using some other method. This process is repeated
until either a) it reaches a variable that was not previously
determined by any constraint or b) it reaches a constraint that
is too weak to be satisfied using any of its methods. The variables
of constraints that have been processed are marked with a unique mark
value so that we know where we've been. This allows the algorithm to
avoid getting into an infinite loop even if the constraint graph has
an inadvertent cycle."
| mark overridden |
mark := self newMark.
overridden := c satisfy: mark.
[overridden isNil] whileFalse:
[overridden := overridden satisfy: mark].
]
{ #category : #adding }
DBPlanner >> incrementalRemove: c [
"Entry point for retracting a constraint. Remove the given constraint,
which should be satisfied, and incrementally update the dataflow
graph.
Details: Retracting the given constraint may allow some currently
unsatisfiable downstream constraint be satisfied. We thus collect a
list of unsatisfied downstream constraints and attempt to satisfy
each one in turn. This list is sorted by constraint strength,
strongest first, as a heuristic for avoiding unnecessarily adding
and then overriding weak constraints."
| out unsatisfied |
out := c output.
c markUnsatisfied.
c removeFromGraph.
unsatisfied := self removePropagateFrom: out.
unsatisfied do: [: u | self incrementalAdd: u].
]
{ #category : #initialize }
DBPlanner >> initialize [
super initialize.
currentMark := 1.
]
{ #category : #planning }
DBPlanner >> makePlan: sources [
"Extract a plan for resatisfaction starting from the given satisfied
source constraints, usually a set of input constraints. This method
assumes that stay optimization is desired; the plan will contain only
constraints whose output variables are not stay. Constraints that do
no computation, such as stay and edit constraints, are not included
in the plan.
Details: The outputs of a constraint are marked when it is added to
the plan under construction. A constraint may be appended to the plan
when all its input variables are known. A variable is known if either
a) the variable is marked (indicating that has been computed by a
constraint appearing earlier in the plan), b) the variable is 'stay'
(i.e. it is a constant at plan execution time), or c) the variable
is not determined by any constraint. The last provision is for past
states of history variables, which are not stay but which are also
not computed by any constraint."
| mark plan todo c |
mark := self newMark.
plan := DBPlan new.
todo := sources.
[todo isEmpty] whileFalse:
[c := todo removeFirst.
((c output mark ~= mark) and: "not in plan already and..."
[c inputsKnown: mark]) ifTrue: "eligible for inclusion"
[plan addLast: c.
c output mark: mark.
self addConstraintsConsuming: c output to: todo]].
^ plan
]
{ #category : #private }
DBPlanner >> newMark [
"Select a previously unused mark value.
Details: We just keep incrementing. If necessary, the counter will
turn into a LargePositiveInteger. In that case, it will be a bit
slower to compute the next mark but the algorithms will all behave
correctly. We reserve the value '0' to mean 'unmarked'. Thus, this
generator starts at '1' and will never produce '0' as a mark value."
^currentMark := currentMark + 1
]
{ #category : #planning }
DBPlanner >> propagateFrom: v [
"The given variable has changed. Propagate new values downstream."
| todo c |
todo := OrderedCollection new.
self addConstraintsConsuming: v to: todo.
[todo isEmpty] whileFalse:
[c := todo removeFirst.
c execute.
self addConstraintsConsuming: c output to: todo].
]
{ #category : #private }
DBPlanner >> removePropagateFrom: out [
"Update the walkabout strengths and stay flags of all variables
downstream of the given constraint. Answer a collection of unsatisfied
constraints sorted in order of decreasing strength."
| unsatisfied todo v |
unsatisfied := SortedCollection sortBlock:
[ :c1 :c2 | c1 strength stronger: c2 strength].
out determinedBy: nil.
out walkStrength: DBStrength absoluteWeakest.
out stay: true.
todo := OrderedCollection with: out.
[todo isEmpty] whileFalse:
[v := todo removeFirst.
v constraints do:
[ :c | c isSatisfied ifFalse: [unsatisfied add: c]].
self constraintsConsuming: v do:
[ :c |
c recalculate.
todo add: c output]].
^ unsatisfied
]