OLD | NEW |
(Empty) | |
| 1 <html> |
| 2 <head> |
| 3 <script src="../htmlrunner.js"></script> |
| 4 <script> |
| 5 // Copyright 2008 the V8 project authors. All rights reserved. |
| 6 // Copyright 1996 John Maloney and Mario Wolczko. |
| 7 |
| 8 // This program is free software; you can redistribute it and/or modify |
| 9 // it under the terms of the GNU General Public License as published by |
| 10 // the Free Software Foundation; either version 2 of the License, or |
| 11 // (at your option) any later version. |
| 12 // |
| 13 // This program is distributed in the hope that it will be useful, |
| 14 // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 16 // GNU General Public License for more details. |
| 17 // |
| 18 // You should have received a copy of the GNU General Public License |
| 19 // along with this program; if not, write to the Free Software |
| 20 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 21 |
| 22 |
| 23 // This implementation of the DeltaBlue benchmark is derived |
| 24 // from the Smalltalk implementation by John Maloney and Mario |
| 25 // Wolczko. Some parts have been translated directly, whereas |
| 26 // others have been modified more aggresively to make it feel |
| 27 // more like a JavaScript program. |
| 28 |
| 29 |
| 30 /** |
| 31 * A JavaScript implementation of the DeltaBlue constrain-solving |
| 32 * algorithm, as described in: |
| 33 * |
| 34 * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" |
| 35 * Bjorn N. Freeman-Benson and John Maloney |
| 36 * January 1990 Communications of the ACM, |
| 37 * also available as University of Washington TR 89-08-06. |
| 38 * |
| 39 * Beware: this benchmark is written in a grotesque style where |
| 40 * the constraint model is built by side-effects from constructors. |
| 41 * I've kept it this way to avoid deviating too much from the original |
| 42 * implementation. |
| 43 */ |
| 44 |
| 45 |
| 46 /* --- O b j e c t M o d e l --- */ |
| 47 |
| 48 function inherits(orig, shuper) { |
| 49 function Inheriter() { } |
| 50 Inheriter.prototype = shuper.prototype; |
| 51 orig.prototype = new Inheriter(); |
| 52 orig.superConstructor = shuper; |
| 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 inherits(UnaryConstraint,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 inherits(StayConstraint,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 inherits(EditConstraint,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 inherits(BinaryConstraint,Constraint); |
| 349 |
| 350 /** |
| 351 * Decides if this constratint 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.v1.mark != mark && Strength.stronger(this.strength, t
his.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, t
his.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 inherits(ScaleConstraint,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 inherits(EqualityConstraint,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 window.onload = function(){ startTest("v8-deltablue", ''); |
| 877 |
| 878 test("Constraint Solving", function deltaBlue() { |
| 879 chainTest(100); |
| 880 projectionTest(100); |
| 881 }); |
| 882 |
| 883 endTest(); }; |
| 884 </script> |
| 885 </head> |
| 886 <body></body> |
| 887 </html> |
OLD | NEW |