The Tor Browser / file comparison

comparison: js/src/jit-test/tests/v8-v5/check-deltablue.js

js/src/jit-test/tests/v8-v5/check-deltablue.js

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial