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