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