1 // Copyright 2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 // Simple framework for running the benchmark suites and
30 // computing a score based on the timing measurements.
33 // A benchmark has a name (string) and a function that will be run to
34 // do the performance measurement. The optional setup and tearDown
35 // arguments are functions that will be invoked before and after
36 // running the benchmark, but the running time of these functions will
37 // not be accounted for in the benchmark score.
38 function Benchmark(name, run, setup, tearDown) {
41 this.Setup = setup ? setup : function() { };
42 this.TearDown = tearDown ? tearDown : function() { };
46 // Benchmark results hold the benchmark and the measured time used to
47 // run the benchmark. The benchmark score is computed later once a
48 // full benchmark suite has run to completion.
49 function BenchmarkResult(benchmark, time) {
50 this.benchmark = benchmark;
55 // Automatically convert results to numbers. Used by the geometric
57 BenchmarkResult.prototype.valueOf = function() {
62 // Suites of benchmarks consist of a name and the set of benchmarks in
63 // addition to the reference timing that the final score will be based
64 // on. This way, all scores are relative to a reference run and higher
65 // scores implies better performance.
66 function BenchmarkSuite(name, reference, benchmarks) {
68 this.reference = reference;
69 this.benchmarks = benchmarks;
70 BenchmarkSuite.suites.push(this);
74 // Keep track of all declared benchmark suites.
75 BenchmarkSuite.suites = [];
78 // Scores are not comparable across versions. Bump the version if
79 // you're making changes that will affect that scores, e.g. if you add
80 // a new benchmark or change an existing one.
81 BenchmarkSuite.version = '5';
84 // To make the benchmark results predictable, we replace Math.random
85 // with a 100% deterministic alternative.
86 Math.random = (function() {
89 // Robert Jenkins' 32 bit integer hash function.
90 seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff;
91 seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
92 seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff;
93 seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff;
94 seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff;
95 seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
96 return (seed & 0xfffffff) / 0x10000000;
101 // Runs all registered benchmark suites and optionally yields between
102 // each individual benchmark to avoid running for too long in the
103 // context of browsers. Once done, the final score is reported to the
105 BenchmarkSuite.RunSuites = function(runner) {
106 var continuation = null;
107 var suites = BenchmarkSuite.suites;
108 var length = suites.length;
109 BenchmarkSuite.scores = [];
112 while (continuation || index < length) {
114 continuation = continuation();
116 var suite = suites[index++];
117 if (runner.NotifyStart) runner.NotifyStart(suite.name);
118 continuation = suite.RunStep(runner);
120 if (continuation && typeof window != 'undefined' && window.setTimeout) {
121 window.setTimeout(RunStep, 25);
125 if (runner.NotifyScore) {
126 var score = BenchmarkSuite.GeometricMean(BenchmarkSuite.scores);
127 var formatted = BenchmarkSuite.FormatScore(100 * score);
128 runner.NotifyScore(formatted);
135 // Counts the total number of registered benchmarks. Useful for
136 // showing progress as a percentage.
137 BenchmarkSuite.CountBenchmarks = function() {
139 var suites = BenchmarkSuite.suites;
140 for (var i = 0; i < suites.length; i++) {
141 result += suites[i].benchmarks.length;
147 // Computes the geometric mean of a set of numbers.
148 BenchmarkSuite.GeometricMean = function(numbers) {
150 for (var i = 0; i < numbers.length; i++) {
151 log += Math.log(numbers[i]);
153 return Math.pow(Math.E, log / numbers.length);
157 // Converts a score value to a string with at least three significant
159 BenchmarkSuite.FormatScore = function(value) {
161 return value.toFixed(0);
163 return value.toPrecision(3);
167 // Notifies the runner that we're done running a single benchmark in
168 // the benchmark suite. This can be useful to report progress.
169 BenchmarkSuite.prototype.NotifyStep = function(result) {
170 this.results.push(result);
171 if (this.runner.NotifyStep) this.runner.NotifyStep(result.benchmark.name);
175 // Notifies the runner that we're done with running a suite and that
176 // we have a result which can be reported to the user if needed.
177 BenchmarkSuite.prototype.NotifyResult = function() {
178 var mean = BenchmarkSuite.GeometricMean(this.results);
179 var score = this.reference / mean;
180 BenchmarkSuite.scores.push(score);
181 if (this.runner.NotifyResult) {
182 var formatted = BenchmarkSuite.FormatScore(100 * score);
183 this.runner.NotifyResult(this.name, formatted);
188 // Notifies the runner that running a benchmark resulted in an error.
189 BenchmarkSuite.prototype.NotifyError = function(error) {
190 if (this.runner.NotifyError) {
191 this.runner.NotifyError(this.name, error);
193 if (this.runner.NotifyStep) {
194 this.runner.NotifyStep(this.name);
199 // Runs a single benchmark for at least a second and computes the
200 // average time it takes to run a single iteration.
201 BenchmarkSuite.prototype.RunSingleBenchmark = function(benchmark) {
203 var start = new Date();
204 for (var n = 0; elapsed < 200; n++) {
206 elapsed = new Date() - start;
208 var usec = (elapsed * 1000) / n;
209 this.NotifyStep(new BenchmarkResult(benchmark, usec));
213 // This function starts running a suite, but stops between each
214 // individual benchmark in the suite and returns a continuation
215 // function which can be invoked to run the next benchmark. Once the
216 // last benchmark has been executed, null is returned.
217 BenchmarkSuite.prototype.RunStep = function(runner) {
219 this.runner = runner;
220 var length = this.benchmarks.length;
224 // Run the setup, the actual benchmark, and the tear down in three
225 // separate steps to allow the framework to yield between any of the
228 function RunNextSetup() {
229 if (index < length) {
231 suite.benchmarks[index].Setup();
233 suite.NotifyError(e);
236 return RunNextBenchmark;
238 suite.NotifyResult();
242 function RunNextBenchmark() {
244 suite.RunSingleBenchmark(suite.benchmarks[index]);
246 suite.NotifyError(e);
249 return RunNextTearDown;
252 function RunNextTearDown() {
254 suite.benchmarks[index++].TearDown();
256 suite.NotifyError(e);
262 // Start out running the setup.
263 return RunNextSetup();
267 // Copyright 2008 Google Inc. All Rights Reserved.
268 // Copyright 1996 John Maloney and Mario Wolczko.
270 // This program is free software; you can redistribute it and/or modify
271 // it under the terms of the GNU General Public License as published by
272 // the Free Software Foundation; either version 2 of the License, or
273 // (at your option) any later version.
275 // This program is distributed in the hope that it will be useful,
276 // but WITHOUT ANY WARRANTY; without even the implied warranty of
277 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
278 // GNU General Public License for more details.
280 // You should have received a copy of the GNU General Public License
281 // along with this program; if not, write to the Free Software
282 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
285 // This implementation of the DeltaBlue benchmark is derived
286 // from the Smalltalk implementation by John Maloney and Mario
287 // Wolczko. Some parts have been translated directly, whereas
288 // others have been modified more aggresively to make it feel
289 // more like a JavaScript program.
292 var DeltaBlue = new BenchmarkSuite('DeltaBlue', 71104, [
293 new Benchmark('DeltaBlue', deltaBlue)
298 * A JavaScript implementation of the DeltaBlue constrain-solving
299 * algorithm, as described in:
301 * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
302 * Bjorn N. Freeman-Benson and John Maloney
303 * January 1990 Communications of the ACM,
304 * also available as University of Washington TR 89-08-06.
306 * Beware: this benchmark is written in a grotesque style where
307 * the constraint model is built by side-effects from constructors.
308 * I've kept it this way to avoid deviating too much from the original
313 /* --- O b j e c t M o d e l --- */
315 Object.prototype.inherits = function (shuper) {
316 function Inheriter() { }
317 Inheriter.prototype = shuper.prototype;
318 this.prototype = new Inheriter();
319 this.superConstructor = shuper;
322 function OrderedCollection() {
323 this.elms = new Array();
326 OrderedCollection.prototype.add = function (elm) {
330 OrderedCollection.prototype.at = function (index) {
331 return this.elms[index];
334 OrderedCollection.prototype.size = function () {
335 return this.elms.length;
338 OrderedCollection.prototype.removeFirst = function () {
339 return this.elms.pop();
342 OrderedCollection.prototype.remove = function (elm) {
343 var index = 0, skipped = 0;
345 for (var i = 0; i < this.elms.length; i++) {
346 var value = this.elms[i];
348 this.elms[index] = value;
356 for (var i = 0; i < skipped; i++)
366 * Strengths are used to measure the relative importance of constraints.
367 * New strengths may be inserted in the strength hierarchy without
368 * disrupting current constraints. Strengths cannot be created outside
369 * this class, so pointer comparison can be used for value comparison.
371 function Strength(strengthValue, name) {
372 this.strengthValue = strengthValue;
376 Strength.stronger = function (s1, s2) {
377 return s1.strengthValue < s2.strengthValue;
380 Strength.weaker = function (s1, s2) {
381 return s1.strengthValue > s2.strengthValue;
384 Strength.weakestOf = function (s1, s2) {
385 return this.weaker(s1, s2) ? s1 : s2;
388 Strength.strongest = function (s1, s2) {
389 return this.stronger(s1, s2) ? s1 : s2;
392 Strength.prototype.nextWeaker = function () {
393 switch (this.strengthValue) {
394 case 0: return Strength.WEAKEST;
395 case 1: return Strength.WEAK_DEFAULT;
396 case 2: return Strength.NORMAL;
397 case 3: return Strength.STRONG_DEFAULT;
398 case 4: return Strength.PREFERRED;
399 case 5: return Strength.REQUIRED;
403 // Strength constants.
404 Strength.REQUIRED = new Strength(0, "required");
405 Strength.STONG_PREFERRED = new Strength(1, "strongPreferred");
406 Strength.PREFERRED = new Strength(2, "preferred");
407 Strength.STRONG_DEFAULT = new Strength(3, "strongDefault");
408 Strength.NORMAL = new Strength(4, "normal");
409 Strength.WEAK_DEFAULT = new Strength(5, "weakDefault");
410 Strength.WEAKEST = new Strength(6, "weakest");
413 * C o n s t r a i n t
417 * An abstract class representing a system-maintainable relationship
418 * (or "constraint") between a set of variables. A constraint supplies
419 * a strength instance variable; concrete subclasses provide a means
420 * of storing the constrained variables and other information required
421 * to represent a constraint.
423 function Constraint(strength) {
424 this.strength = strength;
428 * Activate this constraint and attempt to satisfy it.
430 Constraint.prototype.addConstraint = function () {
432 planner.incrementalAdd(this);
436 * Attempt to find a way to enforce this constraint. If successful,
437 * record the solution, perhaps modifying the current dataflow
438 * graph. Answer the constraint that this constraint overrides, if
439 * there is one, or nil, if there isn't.
440 * Assume: I am not already satisfied.
442 Constraint.prototype.satisfy = function (mark) {
443 this.chooseMethod(mark);
444 if (!this.isSatisfied()) {
445 if (this.strength == Strength.REQUIRED)
446 alert("Could not satisfy a required constraint!");
449 this.markInputs(mark);
450 var out = this.output();
451 var overridden = out.determinedBy;
452 if (overridden != null) overridden.markUnsatisfied();
453 out.determinedBy = this;
454 if (!planner.addPropagate(this, mark))
455 alert("Cycle encountered");
460 Constraint.prototype.destroyConstraint = function () {
461 if (this.isSatisfied()) planner.incrementalRemove(this);
462 else this.removeFromGraph();
466 * Normal constraints are not input constraints. An input constraint
467 * is one that depends on external state, such as the mouse, the
468 * keybord, a clock, or some arbitraty piece of imperative code.
470 Constraint.prototype.isInput = function () {
475 * U n a r y C o n s t r a i n t
479 * Abstract superclass for constraints having a single possible output
482 function UnaryConstraint(v, strength) {
483 UnaryConstraint.superConstructor.call(this, strength);
485 this.satisfied = false;
486 this.addConstraint();
489 UnaryConstraint.inherits(Constraint);
492 * Adds this constraint to the constraint graph
494 UnaryConstraint.prototype.addToGraph = function () {
495 this.myOutput.addConstraint(this);
496 this.satisfied = false;
500 * Decides if this constraint can be satisfied and records that
503 UnaryConstraint.prototype.chooseMethod = function (mark) {
504 this.satisfied = (this.myOutput.mark != mark)
505 && Strength.stronger(this.strength, this.myOutput.walkStrength);
509 * Returns true if this constraint is satisfied in the current solution.
511 UnaryConstraint.prototype.isSatisfied = function () {
512 return this.satisfied;
515 UnaryConstraint.prototype.markInputs = function (mark) {
520 * Returns the current output variable.
522 UnaryConstraint.prototype.output = function () {
523 return this.myOutput;
527 * Calculate the walkabout strength, the stay flag, and, if it is
528 * 'stay', the value for the current output of this constraint. Assume
529 * this constraint is satisfied.
531 UnaryConstraint.prototype.recalculate = function () {
532 this.myOutput.walkStrength = this.strength;
533 this.myOutput.stay = !this.isInput();
534 if (this.myOutput.stay) this.execute(); // Stay optimization
538 * Records that this constraint is unsatisfied
540 UnaryConstraint.prototype.markUnsatisfied = function () {
541 this.satisfied = false;
544 UnaryConstraint.prototype.inputsKnown = function () {
548 UnaryConstraint.prototype.removeFromGraph = function () {
549 if (this.myOutput != null) this.myOutput.removeConstraint(this);
550 this.satisfied = false;
554 * S t a y C o n s t r a i n t
558 * Variables that should, with some level of preference, stay the same.
559 * Planners may exploit the fact that instances, if satisfied, will not
560 * change their output during plan execution. This is called "stay
563 function StayConstraint(v, str) {
564 StayConstraint.superConstructor.call(this, v, str);
567 StayConstraint.inherits(UnaryConstraint);
569 StayConstraint.prototype.execute = function () {
570 // Stay constraints do nothing
574 * E d i t C o n s t r a i n t
578 * A unary input constraint used to mark a variable that the client
581 function EditConstraint(v, str) {
582 EditConstraint.superConstructor.call(this, v, str);
585 EditConstraint.inherits(UnaryConstraint);
588 * Edits indicate that a variable is to be changed by imperative code.
590 EditConstraint.prototype.isInput = function () {
594 EditConstraint.prototype.execute = function () {
595 // Edit constraints do nothing
599 * B i n a r y C o n s t r a i n t
602 var Direction = new Object();
604 Direction.FORWARD = 1;
605 Direction.BACKWARD = -1;
608 * Abstract superclass for constraints having two possible output
611 function BinaryConstraint(var1, var2, strength) {
612 BinaryConstraint.superConstructor.call(this, strength);
615 this.direction = Direction.NONE;
616 this.addConstraint();
619 BinaryConstraint.inherits(Constraint);
622 * Decides if this constratint can be satisfied and which way it
623 * should flow based on the relative strength of the variables related,
624 * and record that decision.
626 BinaryConstraint.prototype.chooseMethod = function (mark) {
627 if (this.v1.mark == mark) {
628 this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength))
632 if (this.v2.mark == mark) {
633 this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength))
637 if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) {
638 this.direction = Strength.stronger(this.strength, this.v1.walkStrength)
642 this.direction = Strength.stronger(this.strength, this.v2.walkStrength)
649 * Add this constraint to the constraint graph
651 BinaryConstraint.prototype.addToGraph = function () {
652 this.v1.addConstraint(this);
653 this.v2.addConstraint(this);
654 this.direction = Direction.NONE;
658 * Answer true if this constraint is satisfied in the current solution.
660 BinaryConstraint.prototype.isSatisfied = function () {
661 return this.direction != Direction.NONE;
665 * Mark the input variable with the given mark.
667 BinaryConstraint.prototype.markInputs = function (mark) {
668 this.input().mark = mark;
672 * Returns the current input variable
674 BinaryConstraint.prototype.input = function () {
675 return (this.direction == Direction.FORWARD) ? this.v1 : this.v2;
679 * Returns the current output variable
681 BinaryConstraint.prototype.output = function () {
682 return (this.direction == Direction.FORWARD) ? this.v2 : this.v1;
686 * Calculate the walkabout strength, the stay flag, and, if it is
687 * 'stay', the value for the current output of this
688 * constraint. Assume this constraint is satisfied.
690 BinaryConstraint.prototype.recalculate = function () {
691 var ihn = this.input(), out = this.output();
692 out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
694 if (out.stay) this.execute();
698 * Record the fact that this constraint is unsatisfied.
700 BinaryConstraint.prototype.markUnsatisfied = function () {
701 this.direction = Direction.NONE;
704 BinaryConstraint.prototype.inputsKnown = function (mark) {
705 var i = this.input();
706 return i.mark == mark || i.stay || i.determinedBy == null;
709 BinaryConstraint.prototype.removeFromGraph = function () {
710 if (this.v1 != null) this.v1.removeConstraint(this);
711 if (this.v2 != null) this.v2.removeConstraint(this);
712 this.direction = Direction.NONE;
716 * S c a l e C o n s t r a i n t
720 * Relates two variables by the linear scaling relationship: "v2 =
721 * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain
722 * this relationship but the scale factor and offset are considered
725 function ScaleConstraint(src, scale, offset, dest, strength) {
726 this.direction = Direction.NONE;
728 this.offset = offset;
729 ScaleConstraint.superConstructor.call(this, src, dest, strength);
732 ScaleConstraint.inherits(BinaryConstraint);
735 * Adds this constraint to the constraint graph.
737 ScaleConstraint.prototype.addToGraph = function () {
738 ScaleConstraint.superConstructor.prototype.addToGraph.call(this);
739 this.scale.addConstraint(this);
740 this.offset.addConstraint(this);
743 ScaleConstraint.prototype.removeFromGraph = function () {
744 ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this);
745 if (this.scale != null) this.scale.removeConstraint(this);
746 if (this.offset != null) this.offset.removeConstraint(this);
749 ScaleConstraint.prototype.markInputs = function (mark) {
750 ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark);
751 this.scale.mark = this.offset.mark = mark;
755 * Enforce this constraint. Assume that it is satisfied.
757 ScaleConstraint.prototype.execute = function () {
758 if (this.direction == Direction.FORWARD) {
759 this.v2.value = this.v1.value * this.scale.value + this.offset.value;
761 this.v1.value = (this.v2.value - this.offset.value) / this.scale.value;
766 * Calculate the walkabout strength, the stay flag, and, if it is
767 * 'stay', the value for the current output of this constraint. Assume
768 * this constraint is satisfied.
770 ScaleConstraint.prototype.recalculate = function () {
771 var ihn = this.input(), out = this.output();
772 out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
773 out.stay = ihn.stay && this.scale.stay && this.offset.stay;
774 if (out.stay) this.execute();
778 * E q u a l i t y C o n s t r a i n t
782 * Constrains two variables to have the same value.
784 function EqualityConstraint(var1, var2, strength) {
785 EqualityConstraint.superConstructor.call(this, var1, var2, strength);
788 EqualityConstraint.inherits(BinaryConstraint);
791 * Enforce this constraint. Assume that it is satisfied.
793 EqualityConstraint.prototype.execute = function () {
794 this.output().value = this.input().value;
802 * A constrained variable. In addition to its value, it maintain the
803 * structure of the constraint graph, the current dataflow graph, and
804 * various parameters of interest to the DeltaBlue incremental
807 function Variable(name, initialValue) {
808 this.value = initialValue || 0;
809 this.constraints = new OrderedCollection();
810 this.determinedBy = null;
812 this.walkStrength = Strength.WEAKEST;
818 * Add the given constraint to the set of all constraints that refer
821 Variable.prototype.addConstraint = function (c) {
822 this.constraints.add(c);
826 * Removes all traces of c from this variable.
828 Variable.prototype.removeConstraint = function (c) {
829 this.constraints.remove(c);
830 if (this.determinedBy == c) this.determinedBy = null;
838 * The DeltaBlue planner
841 this.currentMark = 0;
845 * Attempt to satisfy the given constraint and, if successful,
846 * incrementally update the dataflow graph. Details: If satifying
847 * the constraint is successful, it may override a weaker constraint
848 * on its output. The algorithm attempts to resatisfy that
849 * constraint using some other method. This process is repeated
850 * until either a) it reaches a variable that was not previously
851 * determined by any constraint or b) it reaches a constraint that
852 * is too weak to be satisfied using any of its methods. The
853 * variables of constraints that have been processed are marked with
854 * a unique mark value so that we know where we've been. This allows
855 * the algorithm to avoid getting into an infinite loop even if the
856 * constraint graph has an inadvertent cycle.
858 Planner.prototype.incrementalAdd = function (c) {
859 var mark = this.newMark();
860 var overridden = c.satisfy(mark);
862 while (overridden != null)
863 overridden = overridden.satisfy(mark);
868 * Entry point for retracting a constraint. Remove the given
869 * constraint and incrementally update the dataflow graph.
870 * Details: Retracting the given constraint may allow some currently
871 * unsatisfiable downstream constraint to be satisfied. We therefore collect
872 * a list of unsatisfied downstream constraints and attempt to
873 * satisfy each one in turn. This list is traversed by constraint
874 * strength, strongest first, as a heuristic for avoiding
875 * unnecessarily adding and then overriding weak constraints.
876 * Assume: c is satisfied.
878 Planner.prototype.incrementalRemove = function (c) {
879 var out = c.output();
882 var unsatisfied = this.removePropagateFrom(out);
883 var strength = Strength.REQUIRED;
887 for (var i = 0; i < unsatisfied.size(); i++) {
888 var u = unsatisfied.at(i);
889 if (u.strength == strength)
890 this.incrementalAdd(u);
893 strength = strength.nextWeaker();
894 } while (strength != Strength.WEAKEST);
899 * Select a previously unused mark value.
901 Planner.prototype.newMark = function () {
902 return ++this.currentMark;
906 * Extract a plan for resatisfaction starting from the given source
907 * constraints, usually a set of input constraints. This method
908 * assumes that stay optimization is desired; the plan will contain
909 * only constraints whose output variables are not stay. Constraints
910 * that do no computation, such as stay and edit constraints, are
911 * not included in the plan.
912 * Details: The outputs of a constraint are marked when it is added
913 * to the plan under construction. A constraint may be appended to
914 * the plan when all its input variables are known. A variable is
915 * known if either a) the variable is marked (indicating that has
916 * been computed by a constraint appearing earlier in the plan), b)
917 * the variable is 'stay' (i.e. it is a constant at plan execution
918 * time), or c) the variable is not determined by any
919 * constraint. The last provision is for past states of history
920 * variables, which are not stay but which are also not computed by
922 * Assume: sources are all satisfied.
924 Planner.prototype.makePlan = function (sources) {
925 var mark = this.newMark();
926 var plan = new Plan();
929 while (todo.size() > 0) {
930 var c = todo.removeFirst();
931 if (c.output().mark != mark && c.inputsKnown(mark)) {
932 plan.addConstraint(c);
933 c.output().mark = mark;
934 this.addConstraintsConsumingTo(c.output(), todo);
942 * Extract a plan for resatisfying starting from the output of the
943 * given constraints, usually a set of input constraints.
945 Planner.prototype.extractPlanFromConstraints = function (constraints) {
946 var sources = new OrderedCollection();
948 for (var i = 0; i < constraints.size(); i++) {
949 var c = constraints.at(i);
950 if (c.isInput() && c.isSatisfied())
951 // not in plan already and eligible for inclusion
955 return this.makePlan(sources);
959 * Recompute the walkabout strengths and stay flags of all variables
960 * downstream of the given constraint and recompute the actual
961 * values of all variables whose stay flag is true. If a cycle is
962 * detected, remove the given constraint and answer
963 * false. Otherwise, answer true.
964 * Details: Cycles are detected when a marked variable is
965 * encountered downstream of the given constraint. The sender is
966 * assumed to have marked the inputs of the given constraint with
967 * the given mark. Thus, encountering a marked node downstream of
968 * the output constraint means that there is a path from the
969 * constraint's output to one of its inputs.
971 Planner.prototype.addPropagate = function (c, mark) {
972 var todo = new OrderedCollection();
975 while (todo.size() > 0) {
976 var d = todo.removeFirst();
977 if (d.output().mark == mark) {
978 this.incrementalRemove(c);
982 this.addConstraintsConsumingTo(d.output(), todo);
990 * Update the walkabout strengths and stay flags of all variables
991 * downstream of the given constraint. Answer a collection of
992 * unsatisfied constraints sorted in order of decreasing strength.
994 Planner.prototype.removePropagateFrom = function (out) {
995 out.determinedBy = null;
996 out.walkStrength = Strength.WEAKEST;
998 var unsatisfied = new OrderedCollection();
999 var todo = new OrderedCollection();
1002 while (todo.size() > 0) {
1003 var v = todo.removeFirst();
1005 for (var i = 0; i < v.constraints.size(); i++) {
1006 var c = v.constraints.at(i);
1007 if (!c.isSatisfied())
1011 var determining = v.determinedBy;
1013 for (var i = 0; i < v.constraints.size(); i++) {
1014 var next = v.constraints.at(i);
1015 if (next != determining && next.isSatisfied()) {
1017 todo.add(next.output());
1026 Planner.prototype.addConstraintsConsumingTo = function (v, coll) {
1027 var determining = v.determinedBy;
1028 var cc = v.constraints;
1030 for (var i = 0; i < cc.size(); i++) {
1032 if (c != determining && c.isSatisfied())
1043 * A Plan is an ordered list of constraints to be executed in sequence
1044 * to resatisfy all currently satisfiable constraints in the face of
1045 * one or more changing inputs.
1048 this.v = new OrderedCollection();
1051 Plan.prototype.addConstraint = function (c) {
1055 Plan.prototype.size = function () {
1056 return this.v.size();
1059 Plan.prototype.constraintAt = function (index) {
1060 return this.v.at(index);
1063 Plan.prototype.execute = function () {
1065 for (var i = 0; i < this.size(); i++) {
1066 var c = this.constraintAt(i);
1077 * This is the standard DeltaBlue benchmark. A long chain of equality
1078 * constraints is constructed with a stay constraint on one end. An
1079 * edit constraint is then added to the opposite end and the time is
1080 * measured for adding and removing this constraint, and extracting
1081 * and executing a constraint satisfaction plan. There are two cases.
1082 * In case 1, the added constraint is stronger than the stay
1083 * constraint and values must propagate down the entire length of the
1084 * chain. In case 2, the added constraint is weaker than the stay
1085 * constraint so it cannot be accomodated. The cost in this case is,
1086 * of course, very low. Typical situations lie somewhere between these
1089 function chainTest(n) {
1090 planner = new Planner();
1091 var prev = null, first = null, last = null;
1093 // Build chain of n equality constraints
1095 for (var i = 0; i <= n; i++) {
1097 var v = new Variable(name);
1099 new EqualityConstraint(prev, v, Strength.REQUIRED);
1100 if (i == 0) first = v;
1101 if (i == n) last = v;
1106 new StayConstraint(last, Strength.STRONG_DEFAULT);
1107 var edit = new EditConstraint(first, Strength.PREFERRED);
1108 var edits = new OrderedCollection();
1110 var plan = planner.extractPlanFromConstraints(edits);
1112 for (var i = 0; i < 100; i++) {
1115 if (last.value != i)
1116 alert("Chain test failed.");
1122 * This test constructs a two sets of variables related to each
1123 * other by a simple linear transformation (scale and offset). The
1124 * time is measured to change a variable on either side of the
1125 * mapping and to change the scale and offset factors.
1127 function projectionTest(n) {
1128 planner = new Planner();
1129 var scale = new Variable("scale", 10);
1130 var offset = new Variable("offset", 1000);
1131 var src = null, dst = null;
1133 var dests = new OrderedCollection();
1135 for (var i = 0; i < n; i++) {
1136 src = new Variable("src" + i, i);
1137 dst = new Variable("dst" + i, i);
1139 new StayConstraint(src, Strength.NORMAL);
1140 new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED);
1145 if (dst.value != 1170) alert("Projection 1 failed");
1147 if (src.value != 5) alert("Projection 2 failed");
1150 for (var i = 0; i < n - 1; i++) {
1151 if (dests.at(i).value != i * 5 + 1000)
1152 alert("Projection 3 failed");
1155 change(offset, 2000);
1157 for (var i = 0; i < n - 1; i++) {
1158 if (dests.at(i).value != i * 5 + 2000)
1159 alert("Projection 4 failed");
1164 function change(v, newValue) {
1165 var edit = new EditConstraint(v, Strength.PREFERRED);
1166 var edits = new OrderedCollection();
1168 var plan = planner.extractPlanFromConstraints(edits);
1170 for (var i = 0; i < 10; i++) {
1175 edit.destroyConstraint();
1178 // Global variable holding the current planner.
1181 function deltaBlue() {
1183 projectionTest(100);
1186 function PrintResult(name, result) {
1190 function PrintScore(score) {
1194 BenchmarkSuite.RunSuites({ NotifyResult: PrintResult,
1195 NotifyScore: PrintScore });