[JSC] Clean up Object.entries implementation
[WebKit-https.git] / JSTests / microbenchmarks / deltablue-varargs.js
1 // Copyright 2008 the V8 project authors. All rights reserved.
2 // Copyright 1996 John Maloney and Mario Wolczko.
3
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation; either version 2 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
18
19 // This implementation of the DeltaBlue benchmark is derived
20 // from the Smalltalk implementation by John Maloney and Mario
21 // Wolczko. Some parts have been translated directly, whereas
22 // others have been modified more aggresively to make it feel
23 // more like a JavaScript program.
24
25 /**
26  * A JavaScript implementation of the DeltaBlue constraint-solving
27  * algorithm, as described in:
28  *
29  * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
30  *   Bjorn N. Freeman-Benson and John Maloney
31  *   January 1990 Communications of the ACM,
32  *   also available as University of Washington TR 89-08-06.
33  *
34  * Beware: this benchmark is written in a grotesque style where
35  * the constraint model is built by side-effects from constructors.
36  * I've kept it this way to avoid deviating too much from the original
37  * implementation.
38  */
39
40 // This thing is an evil hack that we use throughout this benchmark so that we can use this benchmark to
41 // stress our varargs implementation. We also have tests for specific features of the varargs code, but
42 // having a somewhat large-ish benchmark that uses varargs a lot (even if it's in a silly way) is great
43 // for shaking out bugs.
44 function args() {
45     var array = [];
46     for (var i = 0; i < arguments.length; ++i)
47         array.push(arguments[i]);
48     return array;
49 }
50
51
52 /* --- O b j e c t   M o d e l --- */
53
54 Object.prototype.inheritsFrom = function (shuper) {
55   function Inheriter() { }
56   Inheriter.prototype = shuper.prototype;
57   this.prototype = new Inheriter(...args());
58   this.superConstructor = shuper;
59 }
60
61 function OrderedCollection() {
62   this.elms = new Array(...args());
63 }
64
65 OrderedCollection.prototype.add = function (elm) {
66   this.elms.push(...args(elm));
67 }
68
69 OrderedCollection.prototype.at = function (index) {
70   return this.elms[index];
71 }
72
73 OrderedCollection.prototype.size = function () {
74   return this.elms.length;
75 }
76
77 OrderedCollection.prototype.removeFirst = function () {
78   return this.elms.pop(...args());
79 }
80
81 OrderedCollection.prototype.remove = function (elm) {
82   var index = 0, skipped = 0;
83   for (var i = 0; i < this.elms.length; i++) {
84     var value = this.elms[i];
85     if (value != elm) {
86       this.elms[index] = value;
87       index++;
88     } else {
89       skipped++;
90     }
91   }
92   for (var i = 0; i < skipped; i++)
93     this.elms.pop(...args());
94 }
95
96 /* --- *
97  * S t r e n g t h
98  * --- */
99
100 /**
101  * Strengths are used to measure the relative importance of constraints.
102  * New strengths may be inserted in the strength hierarchy without
103  * disrupting current constraints.  Strengths cannot be created outside
104  * this class, so pointer comparison can be used for value comparison.
105  */
106 function Strength(strengthValue, name) {
107   this.strengthValue = strengthValue;
108   this.name = name;
109 }
110
111 Strength.stronger = function (s1, s2) {
112   return s1.strengthValue < s2.strengthValue;
113 }
114
115 Strength.weaker = function (s1, s2) {
116   return s1.strengthValue > s2.strengthValue;
117 }
118
119 Strength.weakestOf = function (s1, s2) {
120   return this.weaker(...args(s1, s2)) ? s1 : s2;
121 }
122
123 Strength.strongest = function (s1, s2) {
124   return this.stronger(...args(s1, s2)) ? s1 : s2;
125 }
126
127 Strength.prototype.nextWeaker = function () {
128   switch (this.strengthValue) {
129     case 0: return Strength.WEAKEST;
130     case 1: return Strength.WEAK_DEFAULT;
131     case 2: return Strength.NORMAL;
132     case 3: return Strength.STRONG_DEFAULT;
133     case 4: return Strength.PREFERRED;
134     case 5: return Strength.REQUIRED;
135   }
136 }
137
138 // Strength constants.
139 Strength.REQUIRED        = new Strength(...args(0, "required"));
140 Strength.STONG_PREFERRED = new Strength(...args(1, "strongPreferred"));
141 Strength.PREFERRED       = new Strength(...args(2, "preferred"));
142 Strength.STRONG_DEFAULT  = new Strength(...args(3, "strongDefault"));
143 Strength.NORMAL          = new Strength(...args(4, "normal"));
144 Strength.WEAK_DEFAULT    = new Strength(...args(5, "weakDefault"));
145 Strength.WEAKEST         = new Strength(...args(6, "weakest"));
146
147 /* --- *
148  * C o n s t r a i n t
149  * --- */
150
151 /**
152  * An abstract class representing a system-maintainable relationship
153  * (or "constraint") between a set of variables. A constraint supplies
154  * a strength instance variable; concrete subclasses provide a means
155  * of storing the constrained variables and other information required
156  * to represent a constraint.
157  */
158 function Constraint(strength) {
159   this.strength = strength;
160 }
161
162 /**
163  * Activate this constraint and attempt to satisfy it.
164  */
165 Constraint.prototype.addConstraint = function () {
166   this.addToGraph(...args());
167   planner.incrementalAdd(...args(this));
168 }
169
170 /**
171  * Attempt to find a way to enforce this constraint. If successful,
172  * record the solution, perhaps modifying the current dataflow
173  * graph. Answer the constraint that this constraint overrides, if
174  * there is one, or nil, if there isn't.
175  * Assume: I am not already satisfied.
176  */
177 Constraint.prototype.satisfy = function (mark) {
178   this.chooseMethod(...args(mark));
179   if (!this.isSatisfied(...args())) {
180     if (this.strength == Strength.REQUIRED)
181       alert(...args("Could not satisfy a required constraint!"));
182     return null;
183   }
184   this.markInputs(...args(mark));
185   var out = this.output(...args());
186   var overridden = out.determinedBy;
187   if (overridden != null) overridden.markUnsatisfied(...args());
188   out.determinedBy = this;
189   if (!planner.addPropagate(...args(this, mark)))
190     alert(...args("Cycle encountered"));
191   out.mark = mark;
192   return overridden;
193 }
194
195 Constraint.prototype.destroyConstraint = function () {
196   if (this.isSatisfied(...args())) planner.incrementalRemove(...args(this));
197   else this.removeFromGraph(...args());
198 }
199
200 /**
201  * Normal constraints are not input constraints.  An input constraint
202  * is one that depends on external state, such as the mouse, the
203  * keybord, a clock, or some arbitraty piece of imperative code.
204  */
205 Constraint.prototype.isInput = function () {
206   return false;
207 }
208
209 /* --- *
210  * U n a r y   C o n s t r a i n t
211  * --- */
212
213 /**
214  * Abstract superclass for constraints having a single possible output
215  * variable.
216  */
217 function UnaryConstraint(v, strength) {
218   UnaryConstraint.superConstructor.call(this, strength);
219   this.myOutput = v;
220   this.satisfied = false;
221   this.addConstraint(...args());
222 }
223
224 UnaryConstraint.inheritsFrom(...args(Constraint));
225
226 /**
227  * Adds this constraint to the constraint graph
228  */
229 UnaryConstraint.prototype.addToGraph = function () {
230   this.myOutput.addConstraint(...args(this));
231   this.satisfied = false;
232 }
233
234 /**
235  * Decides if this constraint can be satisfied and records that
236  * decision.
237  */
238 UnaryConstraint.prototype.chooseMethod = function (mark) {
239   this.satisfied = (this.myOutput.mark != mark)
240     && Strength.stronger(...args(this.strength, this.myOutput.walkStrength));
241 }
242
243 /**
244  * Returns true if this constraint is satisfied in the current solution.
245  */
246 UnaryConstraint.prototype.isSatisfied = function () {
247   return this.satisfied;
248 }
249
250 UnaryConstraint.prototype.markInputs = function (mark) {
251   // has no inputs
252 }
253
254 /**
255  * Returns the current output variable.
256  */
257 UnaryConstraint.prototype.output = function () {
258   return this.myOutput;
259 }
260
261 /**
262  * Calculate the walkabout strength, the stay flag, and, if it is
263  * 'stay', the value for the current output of this constraint. Assume
264  * this constraint is satisfied.
265  */
266 UnaryConstraint.prototype.recalculate = function () {
267   this.myOutput.walkStrength = this.strength;
268   this.myOutput.stay = !this.isInput(...args());
269   if (this.myOutput.stay) this.execute(...args()); // Stay optimization
270 }
271
272 /**
273  * Records that this constraint is unsatisfied
274  */
275 UnaryConstraint.prototype.markUnsatisfied = function () {
276   this.satisfied = false;
277 }
278
279 UnaryConstraint.prototype.inputsKnown = function () {
280   return true;
281 }
282
283 UnaryConstraint.prototype.removeFromGraph = function () {
284   if (this.myOutput != null) this.myOutput.removeConstraint(...args(this));
285   this.satisfied = false;
286 }
287
288 /* --- *
289  * S t a y   C o n s t r a i n t
290  * --- */
291
292 /**
293  * Variables that should, with some level of preference, stay the same.
294  * Planners may exploit the fact that instances, if satisfied, will not
295  * change their output during plan execution.  This is called "stay
296  * optimization".
297  */
298 function StayConstraint(v, str) {
299   StayConstraint.superConstructor.call(this, v, str);
300 }
301
302 StayConstraint.inheritsFrom(...args(UnaryConstraint));
303
304 StayConstraint.prototype.execute = function () {
305   // Stay constraints do nothing
306 }
307
308 /* --- *
309  * E d i t   C o n s t r a i n t
310  * --- */
311
312 /**
313  * A unary input constraint used to mark a variable that the client
314  * wishes to change.
315  */
316 function EditConstraint(v, str) {
317   EditConstraint.superConstructor.call(this, v, str);
318 }
319
320 EditConstraint.inheritsFrom(...args(UnaryConstraint));
321
322 /**
323  * Edits indicate that a variable is to be changed by imperative code.
324  */
325 EditConstraint.prototype.isInput = function () {
326   return true;
327 }
328
329 EditConstraint.prototype.execute = function () {
330   // Edit constraints do nothing
331 }
332
333 /* --- *
334  * B i n a r y   C o n s t r a i n t
335  * --- */
336
337 var Direction = new Object(...args());
338 Direction.NONE     = 0;
339 Direction.FORWARD  = 1;
340 Direction.BACKWARD = -1;
341
342 /**
343  * Abstract superclass for constraints having two possible output
344  * variables.
345  */
346 function BinaryConstraint(var1, var2, strength) {
347   BinaryConstraint.superConstructor.call(this, strength);
348   this.v1 = var1;
349   this.v2 = var2;
350   this.direction = Direction.NONE;
351   this.addConstraint(...args());
352 }
353
354 BinaryConstraint.inheritsFrom(...args(Constraint));
355
356 /**
357  * Decides if this constraint can be satisfied and which way it
358  * should flow based on the relative strength of the variables related,
359  * and record that decision.
360  */
361 BinaryConstraint.prototype.chooseMethod = function (mark) {
362   if (this.v1.mark == mark) {
363     this.direction = (this.v2.mark != mark && Strength.stronger(...args(this.strength, this.v2.walkStrength)))
364       ? Direction.FORWARD
365       : Direction.NONE;
366   }
367   if (this.v2.mark == mark) {
368     this.direction = (this.v1.mark != mark && Strength.stronger(...args(this.strength, this.v1.walkStrength)))
369       ? Direction.BACKWARD
370       : Direction.NONE;
371   }
372   if (Strength.weaker(...args(this.v1.walkStrength, this.v2.walkStrength))) {
373     this.direction = Strength.stronger(...args(this.strength, this.v1.walkStrength))
374       ? Direction.BACKWARD
375       : Direction.NONE;
376   } else {
377     this.direction = Strength.stronger(...args(this.strength, this.v2.walkStrength))
378       ? Direction.FORWARD
379       : Direction.BACKWARD
380   }
381 }
382
383 /**
384  * Add this constraint to the constraint graph
385  */
386 BinaryConstraint.prototype.addToGraph = function () {
387   this.v1.addConstraint(...args(this));
388   this.v2.addConstraint(...args(this));
389   this.direction = Direction.NONE;
390 }
391
392 /**
393  * Answer true if this constraint is satisfied in the current solution.
394  */
395 BinaryConstraint.prototype.isSatisfied = function () {
396   return this.direction != Direction.NONE;
397 }
398
399 /**
400  * Mark the input variable with the given mark.
401  */
402 BinaryConstraint.prototype.markInputs = function (mark) {
403   this.input(...args()).mark = mark;
404 }
405
406 /**
407  * Returns the current input variable
408  */
409 BinaryConstraint.prototype.input = function () {
410   return (this.direction == Direction.FORWARD) ? this.v1 : this.v2;
411 }
412
413 /**
414  * Returns the current output variable
415  */
416 BinaryConstraint.prototype.output = function () {
417   return (this.direction == Direction.FORWARD) ? this.v2 : this.v1;
418 }
419
420 /**
421  * Calculate the walkabout strength, the stay flag, and, if it is
422  * 'stay', the value for the current output of this
423  * constraint. Assume this constraint is satisfied.
424  */
425 BinaryConstraint.prototype.recalculate = function () {
426   var ihn = this.input(...args()), out = this.output(...args());
427   out.walkStrength = Strength.weakestOf(...args(this.strength, ihn.walkStrength));
428   out.stay = ihn.stay;
429   if (out.stay) this.execute(...args());
430 }
431
432 /**
433  * Record the fact that this constraint is unsatisfied.
434  */
435 BinaryConstraint.prototype.markUnsatisfied = function () {
436   this.direction = Direction.NONE;
437 }
438
439 BinaryConstraint.prototype.inputsKnown = function (mark) {
440   var i = this.input(...args());
441   return i.mark == mark || i.stay || i.determinedBy == null;
442 }
443
444 BinaryConstraint.prototype.removeFromGraph = function () {
445   if (this.v1 != null) this.v1.removeConstraint(...args(this));
446   if (this.v2 != null) this.v2.removeConstraint(...args(this));
447   this.direction = Direction.NONE;
448 }
449
450 /* --- *
451  * S c a l e   C o n s t r a i n t
452  * --- */
453
454 /**
455  * Relates two variables by the linear scaling relationship: "v2 =
456  * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain
457  * this relationship but the scale factor and offset are considered
458  * read-only.
459  */
460 function ScaleConstraint(src, scale, offset, dest, strength) {
461   this.direction = Direction.NONE;
462   this.scale = scale;
463   this.offset = offset;
464   ScaleConstraint.superConstructor.call(this, src, dest, strength);
465 }
466
467 ScaleConstraint.inheritsFrom(...args(BinaryConstraint));
468
469 /**
470  * Adds this constraint to the constraint graph.
471  */
472 ScaleConstraint.prototype.addToGraph = function () {
473   ScaleConstraint.superConstructor.prototype.addToGraph.call(this);
474   this.scale.addConstraint(...args(this));
475   this.offset.addConstraint(...args(this));
476 }
477
478 ScaleConstraint.prototype.removeFromGraph = function () {
479   ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this);
480   if (this.scale != null) this.scale.removeConstraint(...args(this));
481   if (this.offset != null) this.offset.removeConstraint(...args(this));
482 }
483
484 ScaleConstraint.prototype.markInputs = function (mark) {
485   ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark);
486   this.scale.mark = this.offset.mark = mark;
487 }
488
489 /**
490  * Enforce this constraint. Assume that it is satisfied.
491  */
492 ScaleConstraint.prototype.execute = function () {
493   if (this.direction == Direction.FORWARD) {
494     this.v2.value = this.v1.value * this.scale.value + this.offset.value;
495   } else {
496     this.v1.value = (this.v2.value - this.offset.value) / this.scale.value;
497   }
498 }
499
500 /**
501  * Calculate the walkabout strength, the stay flag, and, if it is
502  * 'stay', the value for the current output of this constraint. Assume
503  * this constraint is satisfied.
504  */
505 ScaleConstraint.prototype.recalculate = function () {
506   var ihn = this.input(...args()), out = this.output(...args());
507   out.walkStrength = Strength.weakestOf(...args(this.strength, ihn.walkStrength));
508   out.stay = ihn.stay && this.scale.stay && this.offset.stay;
509   if (out.stay) this.execute(...args());
510 }
511
512 /* --- *
513  * E q u a l i t  y   C o n s t r a i n t
514  * --- */
515
516 /**
517  * Constrains two variables to have the same value.
518  */
519 function EqualityConstraint(var1, var2, strength) {
520   EqualityConstraint.superConstructor.call(this, var1, var2, strength);
521 }
522
523 EqualityConstraint.inheritsFrom(...args(BinaryConstraint));
524
525 /**
526  * Enforce this constraint. Assume that it is satisfied.
527  */
528 EqualityConstraint.prototype.execute = function () {
529   this.output(...args()).value = this.input(...args()).value;
530 }
531
532 /* --- *
533  * V a r i a b l e
534  * --- */
535
536 /**
537  * A constrained variable. In addition to its value, it maintain the
538  * structure of the constraint graph, the current dataflow graph, and
539  * various parameters of interest to the DeltaBlue incremental
540  * constraint solver.
541  **/
542 function Variable(name, initialValue) {
543   this.value = initialValue || 0;
544   this.constraints = new OrderedCollection(...args());
545   this.determinedBy = null;
546   this.mark = 0;
547   this.walkStrength = Strength.WEAKEST;
548   this.stay = true;
549   this.name = name;
550 }
551
552 /**
553  * Add the given constraint to the set of all constraints that refer
554  * this variable.
555  */
556 Variable.prototype.addConstraint = function (c) {
557   this.constraints.add(...args(c));
558 }
559
560 /**
561  * Removes all traces of c from this variable.
562  */
563 Variable.prototype.removeConstraint = function (c) {
564   this.constraints.remove(...args(c));
565   if (this.determinedBy == c) this.determinedBy = null;
566 }
567
568 /* --- *
569  * P l a n n e r
570  * --- */
571
572 /**
573  * The DeltaBlue planner
574  */
575 function Planner() {
576   this.currentMark = 0;
577 }
578
579 /**
580  * Attempt to satisfy the given constraint and, if successful,
581  * incrementally update the dataflow graph.  Details: If satifying
582  * the constraint is successful, it may override a weaker constraint
583  * on its output. The algorithm attempts to resatisfy that
584  * constraint using some other method. This process is repeated
585  * until either a) it reaches a variable that was not previously
586  * determined by any constraint or b) it reaches a constraint that
587  * is too weak to be satisfied using any of its methods. The
588  * variables of constraints that have been processed are marked with
589  * a unique mark value so that we know where we've been. This allows
590  * the algorithm to avoid getting into an infinite loop even if the
591  * constraint graph has an inadvertent cycle.
592  */
593 Planner.prototype.incrementalAdd = function (c) {
594   var mark = this.newMark(...args());
595   var overridden = c.satisfy(...args(mark));
596   while (overridden != null)
597     overridden = overridden.satisfy(...args(mark));
598 }
599
600 /**
601  * Entry point for retracting a constraint. Remove the given
602  * constraint and incrementally update the dataflow graph.
603  * Details: Retracting the given constraint may allow some currently
604  * unsatisfiable downstream constraint to be satisfied. We therefore collect
605  * a list of unsatisfied downstream constraints and attempt to
606  * satisfy each one in turn. This list is traversed by constraint
607  * strength, strongest first, as a heuristic for avoiding
608  * unnecessarily adding and then overriding weak constraints.
609  * Assume: c is satisfied.
610  */
611 Planner.prototype.incrementalRemove = function (c) {
612   var out = c.output(...args());
613   c.markUnsatisfied(...args());
614   c.removeFromGraph(...args());
615   var unsatisfied = this.removePropagateFrom(...args(out));
616   var strength = Strength.REQUIRED;
617   do {
618     for (var i = 0; i < unsatisfied.size(...args()); i++) {
619       var u = unsatisfied.at(...args(i));
620       if (u.strength == strength)
621         this.incrementalAdd(...args(u));
622     }
623     strength = strength.nextWeaker(...args());
624   } while (strength != Strength.WEAKEST);
625 }
626
627 /**
628  * Select a previously unused mark value.
629  */
630 Planner.prototype.newMark = function () {
631   return ++this.currentMark;
632 }
633
634 /**
635  * Extract a plan for resatisfaction starting from the given source
636  * constraints, usually a set of input constraints. This method
637  * assumes that stay optimization is desired; the plan will contain
638  * only constraints whose output variables are not stay. Constraints
639  * that do no computation, such as stay and edit constraints, are
640  * not included in the plan.
641  * Details: The outputs of a constraint are marked when it is added
642  * to the plan under construction. A constraint may be appended to
643  * the plan when all its input variables are known. A variable is
644  * known if either a) the variable is marked (indicating that has
645  * been computed by a constraint appearing earlier in the plan), b)
646  * the variable is 'stay' (i.e. it is a constant at plan execution
647  * time), or c) the variable is not determined by any
648  * constraint. The last provision is for past states of history
649  * variables, which are not stay but which are also not computed by
650  * any constraint.
651  * Assume: sources are all satisfied.
652  */
653 Planner.prototype.makePlan = function (sources) {
654   var mark = this.newMark(...args());
655   var plan = new Plan(...args());
656   var todo = sources;
657   while (todo.size(...args()) > 0) {
658     var c = todo.removeFirst(...args());
659     if (c.output(...args()).mark != mark && c.inputsKnown(...args(mark))) {
660       plan.addConstraint(...args(c));
661       c.output(...args()).mark = mark;
662       this.addConstraintsConsumingTo(...args(c.output(...args()), todo));
663     }
664   }
665   return plan;
666 }
667
668 /**
669  * Extract a plan for resatisfying starting from the output of the
670  * given constraints, usually a set of input constraints.
671  */
672 Planner.prototype.extractPlanFromConstraints = function (constraints) {
673   var sources = new OrderedCollection(...args());
674   for (var i = 0; i < constraints.size(...args()); i++) {
675     var c = constraints.at(...args(i));
676     if (c.isInput(...args()) && c.isSatisfied(...args()))
677       // not in plan already and eligible for inclusion
678       sources.add(...args(c));
679   }
680   return this.makePlan(...args(sources));
681 }
682
683 /**
684  * Recompute the walkabout strengths and stay flags of all variables
685  * downstream of the given constraint and recompute the actual
686  * values of all variables whose stay flag is true. If a cycle is
687  * detected, remove the given constraint and answer
688  * false. Otherwise, answer true.
689  * Details: Cycles are detected when a marked variable is
690  * encountered downstream of the given constraint. The sender is
691  * assumed to have marked the inputs of the given constraint with
692  * the given mark. Thus, encountering a marked node downstream of
693  * the output constraint means that there is a path from the
694  * constraint's output to one of its inputs.
695  */
696 Planner.prototype.addPropagate = function (c, mark) {
697   var todo = new OrderedCollection(...args());
698   todo.add(...args(c));
699   while (todo.size(...args()) > 0) {
700     var d = todo.removeFirst(...args());
701     if (d.output(...args()).mark == mark) {
702       this.incrementalRemove(...args(c));
703       return false;
704     }
705     d.recalculate(...args());
706     this.addConstraintsConsumingTo(...args(d.output(...args()), todo));
707   }
708   return true;
709 }
710
711
712 /**
713  * Update the walkabout strengths and stay flags of all variables
714  * downstream of the given constraint. Answer a collection of
715  * unsatisfied constraints sorted in order of decreasing strength.
716  */
717 Planner.prototype.removePropagateFrom = function (out) {
718   out.determinedBy = null;
719   out.walkStrength = Strength.WEAKEST;
720   out.stay = true;
721   var unsatisfied = new OrderedCollection(...args());
722   var todo = new OrderedCollection(...args());
723   todo.add(...args(out));
724   while (todo.size(...args()) > 0) {
725     var v = todo.removeFirst(...args());
726     for (var i = 0; i < v.constraints.size(...args()); i++) {
727       var c = v.constraints.at(...args(i));
728       if (!c.isSatisfied(...args()))
729         unsatisfied.add(...args(c));
730     }
731     var determining = v.determinedBy;
732     for (var i = 0; i < v.constraints.size(...args()); i++) {
733       var next = v.constraints.at(...args(i));
734       if (next != determining && next.isSatisfied(...args())) {
735         next.recalculate(...args());
736         todo.add(...args(next.output(...args())));
737       }
738     }
739   }
740   return unsatisfied;
741 }
742
743 Planner.prototype.addConstraintsConsumingTo = function (v, coll) {
744   var determining = v.determinedBy;
745   var cc = v.constraints;
746   for (var i = 0; i < cc.size(...args()); i++) {
747     var c = cc.at(...args(i));
748     if (c != determining && c.isSatisfied(...args()))
749       coll.add(...args(c));
750   }
751 }
752
753 /* --- *
754  * P l a n
755  * --- */
756
757 /**
758  * A Plan is an ordered list of constraints to be executed in sequence
759  * to resatisfy all currently satisfiable constraints in the face of
760  * one or more changing inputs.
761  */
762 function Plan() {
763   this.v = new OrderedCollection(...args());
764 }
765
766 Plan.prototype.addConstraint = function (c) {
767   this.v.add(...args(c));
768 }
769
770 Plan.prototype.size = function () {
771   return this.v.size(...args());
772 }
773
774 Plan.prototype.constraintAt = function (index) {
775   return this.v.at(...args(index));
776 }
777
778 Plan.prototype.execute = function () {
779   for (var i = 0; i < this.size(...args()); i++) {
780     var c = this.constraintAt(...args(i));
781     c.execute(...args());
782   }
783 }
784
785 /* --- *
786  * M a i n
787  * --- */
788
789 /**
790  * This is the standard DeltaBlue benchmark. A long chain of equality
791  * constraints is constructed with a stay constraint on one end. An
792  * edit constraint is then added to the opposite end and the time is
793  * measured for adding and removing this constraint, and extracting
794  * and executing a constraint satisfaction plan. There are two cases.
795  * In case 1, the added constraint is stronger than the stay
796  * constraint and values must propagate down the entire length of the
797  * chain. In case 2, the added constraint is weaker than the stay
798  * constraint so it cannot be accomodated. The cost in this case is,
799  * of course, very low. Typical situations lie somewhere between these
800  * two extremes.
801  */
802 function chainTest(n) {
803   planner = new Planner(...args());
804   var prev = null, first = null, last = null;
805
806   // Build chain of n equality constraints
807   for (var i = 0; i <= n; i++) {
808     var name = "v" + i;
809     var v = new Variable(...args(name));
810     if (prev != null)
811       new EqualityConstraint(...args(prev, v, Strength.REQUIRED));
812     if (i == 0) first = v;
813     if (i == n) last = v;
814     prev = v;
815   }
816
817   new StayConstraint(...args(last, Strength.STRONG_DEFAULT));
818   var edit = new EditConstraint(...args(first, Strength.PREFERRED));
819   var edits = new OrderedCollection(...args());
820   edits.add(...args(edit));
821   var plan = planner.extractPlanFromConstraints(...args(edits));
822   for (var i = 0; i < 100; i++) {
823     first.value = i;
824     plan.execute(...args());
825     if (last.value != i)
826       alert(...args("Chain test failed."));
827   }
828 }
829
830 /**
831  * This test constructs a two sets of variables related to each
832  * other by a simple linear transformation (scale and offset). The
833  * time is measured to change a variable on either side of the
834  * mapping and to change the scale and offset factors.
835  */
836 function projectionTest(n) {
837   planner = new Planner(...args());
838   var scale = new Variable(...args("scale", 10));
839   var offset = new Variable(...args("offset", 1000));
840   var src = null, dst = null;
841
842   var dests = new OrderedCollection(...args());
843   for (var i = 0; i < n; i++) {
844     src = new Variable(...args("src" + i, i));
845     dst = new Variable(...args("dst" + i, i));
846     dests.add(...args(dst));
847     new StayConstraint(...args(src, Strength.NORMAL));
848     new ScaleConstraint(...args(src, scale, offset, dst, Strength.REQUIRED));
849   }
850
851   change(...args(src, 17));
852   if (dst.value != 1170) alert(...args("Projection 1 failed"));
853   change(...args(dst, 1050));
854   if (src.value != 5) alert(...args("Projection 2 failed"));
855   change(...args(scale, 5));
856   for (var i = 0; i < n - 1; i++) {
857     if (dests.at(...args(i)).value != i * 5 + 1000)
858       alert(...args("Projection 3 failed"));
859   }
860   change(...args(offset, 2000));
861   for (var i = 0; i < n - 1; i++) {
862     if (dests.at(...args(i)).value != i * 5 + 2000)
863       alert(...args("Projection 4 failed"));
864   }
865 }
866
867 function change(v, newValue) {
868   var edit = new EditConstraint(...args(v, Strength.PREFERRED));
869   var edits = new OrderedCollection(...args());
870   edits.add(...args(edit));
871   var plan = planner.extractPlanFromConstraints(...args(edits));
872   for (var i = 0; i < 10; i++) {
873     v.value = newValue;
874     plan.execute(...args());
875   }
876   edit.destroyConstraint(...args());
877 }
878
879 // Global variable holding the current planner.
880 var planner = null;
881
882 function deltaBlue() {
883   chainTest(...args(25));
884   projectionTest(...args(25));
885 }
886
887 for (var i = 0; i < 5; ++i)
888     deltaBlue(...args());