Version 1.2.4.

Improved performance of floating point number allocation for ARM platforms.

Fixed crash when using the instanceof operator on functions with number values in their prototype chain (issue 341).

Optimized virtual frame operations in the code generator to speed up compilation time and allocated the frames in the zone.

Made the representation of virtual frames and jump targets in the code generator much more compact.

Avoided linear search for non-locals in scope code when resolving variables inside with and eval scopes.

Optimized lexical scanner by dealing with whitespace as part of the token scanning instead of as a separate step before it.

Changed the scavenging collector so that promoted objects do not reside in the old generation while their remembered set is being swept for pointers into the young generation.

Fixed numeric overflow handling when compiling count operations.


git-svn-id: http://v8.googlecode.com/svn/trunk@1983 ce2b1a6d-e550-0410-aec6-3dcde31c8c00

10 files changed, 472 insertions, 2531 deletions

diff --git a/benchmarks/README.txt b/benchmarks/README.txt
index 46aa57328..7531157c3 100644
--- a/benchmarks/README.txt
+++ b/benchmarks/README.txt
@@ -40,3 +40,15 @@ pages where it occurs and the number of times it is executed while
 loading each page.  Finally the literal letters in the data are
 encoded using ROT13 in a way that does not affect how the regexps
 match their input.
+
+
+Changes from Version 3 to Version 4
+===================================
+
+The Splay benchmark is a newcomer in version 4.  It manipulates a
+splay tree by adding and removing data nodes, thus exercising the
+memory management subsystem of the JavaScript engine.
+
+Furthermore, all the unused parts of the Prototype library were
+removed from the RayTrace benchmark. This does not affect the running
+of the benchmark.
diff --git a/benchmarks/base.js b/benchmarks/base.js
index 261733208..a22920b53 100644
--- a/benchmarks/base.js
+++ b/benchmarks/base.js
@@ -31,10 +31,15 @@
 
 
 // A benchmark has a name (string) and a function that will be run to
-// do the performance measurement.
-function Benchmark(name, run) {
+// do the performance measurement. The optional setup and tearDown
+// arguments are functions that will be invoked before and after
+// running the benchmark, but the running time of these functions will
+// not be accounted for in the benchmark score.
+function Benchmark(name, run, setup, tearDown) {
   this.name = name;
   this.run = run;
+  this.Setup = setup ? setup : function() { };
+  this.TearDown = tearDown ? tearDown : function() { };
 }
 
 
@@ -73,7 +78,7 @@ BenchmarkSuite.suites = [];
 // Scores are not comparable across versions. Bump the version if
 // you're making changes that will affect that scores, e.g. if you add
 // a new benchmark or change an existing one.
-BenchmarkSuite.version = '3';
+BenchmarkSuite.version = '4';
 
 
 // To make the benchmark results predictable, we replace Math.random
@@ -114,7 +119,7 @@ BenchmarkSuite.RunSuites = function(runner) {
         continuation = suite.RunStep(runner);
       }
       if (continuation && typeof window != 'undefined' && window.setTimeout) {
-        window.setTimeout(RunStep, 100);
+        window.setTimeout(RunStep, 25);
         return;
       }
     }
@@ -194,7 +199,7 @@ BenchmarkSuite.prototype.NotifyError = function(error) {
 
 // Runs a single benchmark for at least a second and computes the
 // average time it takes to run a single iteration.
-BenchmarkSuite.prototype.RunSingle = function(benchmark) {
+BenchmarkSuite.prototype.RunSingleBenchmark = function(benchmark) {
   var elapsed = 0;
   var start = new Date();
   for (var n = 0; elapsed < 1000; n++) {
@@ -216,18 +221,45 @@ BenchmarkSuite.prototype.RunStep = function(runner) {
   var length = this.benchmarks.length;
   var index = 0;
   var suite = this;
-  function RunNext() {
+
+  // Run the setup, the actual benchmark, and the tear down in three
+  // separate steps to allow the framework to yield between any of the
+  // steps.
+
+  function RunNextSetup() {
     if (index < length) {
       try {
-        suite.RunSingle(suite.benchmarks[index++]);
+        suite.benchmarks[index].Setup();
       } catch (e) {
         suite.NotifyError(e);
         return null;
       }
-      return RunNext;
+      return RunNextBenchmark;
     }
     suite.NotifyResult();
     return null;
   }
-  return RunNext();
+
+  function RunNextBenchmark() {
+    try {
+      suite.RunSingleBenchmark(suite.benchmarks[index]);
+    } catch (e) {
+      suite.NotifyError(e);
+      return null;
+    }
+    return RunNextTearDown;
+  }
+
+  function RunNextTearDown() {
+    try {
+      suite.benchmarks[index++].TearDown();
+    } catch (e) {
+      suite.NotifyError(e);
+      return null;
+    }
+    return RunNextSetup;
+  }
+
+  // Start out running the setup.
+  return RunNextSetup();
 }
diff --git a/benchmarks/deltablue.js b/benchmarks/deltablue.js
index b51afd1d2..253046f80 100644
--- a/benchmarks/deltablue.js
+++ b/benchmarks/deltablue.js
@@ -16,10 +16,10 @@
 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
 
-// This implementation of the DeltaBlue benchmark is derived 
-// from the Smalltalk implementation by John Maloney and Mario 
-// Wolczko. Some parts have been translated directly, whereas 
-// others have been modified more aggresively to make it feel 
+// This implementation of the DeltaBlue benchmark is derived
+// from the Smalltalk implementation by John Maloney and Mario
+// Wolczko. Some parts have been translated directly, whereas
+// others have been modified more aggresively to make it feel
 // more like a JavaScript program.
 
 
diff --git a/benchmarks/earley-boyer.js b/benchmarks/earley-boyer.js
index 9016a137a..3c7f922c4 100644
--- a/benchmarks/earley-boyer.js
+++ b/benchmarks/earley-boyer.js
@@ -4682,4 +4682,3 @@ function RunBenchmark(name, count, run, warn) {
 }
 
 var BgL_runzd2benchmarkzd2 = RunBenchmark;
-
diff --git a/benchmarks/raytrace.js b/benchmarks/raytrace.js
index 925d0ed35..c68b0383a 100644
--- a/benchmarks/raytrace.js
+++ b/benchmarks/raytrace.js
@@ -5,7 +5,7 @@
 //
 // It has been modified slightly by Google to work as a standalone
 // benchmark, but the all the computational code remains
-// untouched. This file also contains a copy of the Prototype
+// untouched. This file also contains a copy of parts of the Prototype
 // JavaScript framework which is used by the ray tracer.
 
 var RayTrace = new BenchmarkSuite('RayTrace', 932666, [
@@ -13,39 +13,22 @@ var RayTrace = new BenchmarkSuite('RayTrace', 932666, [
 ]);
 
 
+// Variable used to hold a number that can be used to verify that
+// the scene was ray traced correctly.
 var checkNumber;
 
-// Create dummy objects if we're not running in a browser.
-if (typeof document == 'undefined') {
-  document = { };
-  window = { opera: null };
-  navigator = { userAgent: null, appVersion: "" };
-}
-
 
 // ------------------------------------------------------------------------
 // ------------------------------------------------------------------------
 
+// The following is a copy of parts of the Prototype JavaScript library:
+
+// Prototype JavaScript framework, version 1.5.0
+// (c) 2005-2007 Sam Stephenson
+//
+// Prototype is freely distributable under the terms of an MIT-style license.
+// For details, see the Prototype web site: http://prototype.conio.net/
 
-/*  Prototype JavaScript framework, version 1.5.0
- *  (c) 2005-2007 Sam Stephenson
- *
- *  Prototype is freely distributable under the terms of an MIT-style license.
- *  For details, see the Prototype web site: http://prototype.conio.net/
- *
-/*--------------------------------------------------------------------------*/
-
-//--------------------
-var Prototype = {
-  Version: '1.5.0',
-  BrowserFeatures: {
-    XPath: !!document.evaluate
-  },
-
-  ScriptFragment: '(?:<script.*?>)((\n|\r|.)*?)(?:<\/script>)',
-  emptyFunction: function() {},
-  K: function(x) { return x }
-}
 
 var Class = {
   create: function() {
@@ -53,2497 +36,16 @@ var Class = {
       this.initialize.apply(this, arguments);
     }
   }
-}
+};
 
-var Abstract = new Object();
 
 Object.extend = function(destination, source) {
   for (var property in source) {
     destination[property] = source[property];
   }
   return destination;
-}
-
-Object.extend(Object, {
-  inspect: function(object) {
-    try {
-      if (object === undefined) return 'undefined';
-      if (object === null) return 'null';
-      return object.inspect ? object.inspect() : object.toString();
-    } catch (e) {
-      if (e instanceof RangeError) return '...';
-      throw e;
-    }
-  },
-
-  keys: function(object) {
-    var keys = [];
-    for (var property in object)
-      keys.push(property);
-    return keys;
-  },
-
-  values: function(object) {
-    var values = [];
-    for (var property in object)
-      values.push(object[property]);
-    return values;
-  },
-
-  clone: function(object) {
-    return Object.extend({}, object);
-  }
-});
-
-Function.prototype.bind = function() {
-  var __method = this, args = $A(arguments), object = args.shift();
-  return function() {
-    return __method.apply(object, args.concat($A(arguments)));
-  }
-}
-
-Function.prototype.bindAsEventListener = function(object) {
-  var __method = this, args = $A(arguments), object = args.shift();
-  return function(event) {
-    return __method.apply(object, [( event || window.event)].concat(args).concat($A(arguments)));
-  }
-}
-
-Object.extend(Number.prototype, {
-  toColorPart: function() {
-    var digits = this.toString(16);
-    if (this < 16) return '0' + digits;
-    return digits;
-  },
-
-  succ: function() {
-    return this + 1;
-  },
-
-  times: function(iterator) {
-    $R(0, this, true).each(iterator);
-    return this;
-  }
-});
-
-var Try = {
-  these: function() {
-    var returnValue;
-
-    for (var i = 0, length = arguments.length; i < length; i++) {
-      var lambda = arguments[i];
-      try {
-        returnValue = lambda();
-        break;
-      } catch (e) {}
-    }
-
-    return returnValue;
-  }
-}
-
-/*--------------------------------------------------------------------------*/
-
-var PeriodicalExecuter = Class.create();
-PeriodicalExecuter.prototype = {
-  initialize: function(callback, frequency) {
-    this.callback = callback;
-    this.frequency = frequency;
-    this.currentlyExecuting = false;
-
-    this.registerCallback();
-  },
-
-  registerCallback: function() {
-    this.timer = setInterval(this.onTimerEvent.bind(this), this.frequency * 1000);
-  },
-
-  stop: function() {
-    if (!this.timer) return;
-    clearInterval(this.timer);
-    this.timer = null;
-  },
-
-  onTimerEvent: function() {
-    if (!this.currentlyExecuting) {
-      try {
-        this.currentlyExecuting = true;
-        this.callback(this);
-      } finally {
-        this.currentlyExecuting = false;
-      }
-    }
-  }
-}
-String.interpret = function(value){
-  return value == null ? '' : String(value);
-}
-
-Object.extend(String.prototype, {
-  gsub: function(pattern, replacement) {
-    var result = '', source = this, match;
-    replacement = arguments.callee.prepareReplacement(replacement);
-
-    while (source.length > 0) {
-      if (match = source.match(pattern)) {
-        result += source.slice(0, match.index);
-        result += String.interpret(replacement(match));
-        source  = source.slice(match.index + match[0].length);
-      } else {
-        result += source, source = '';
-      }
-    }
-    return result;
-  },
-
-  sub: function(pattern, replacement, count) {
-    replacement = this.gsub.prepareReplacement(replacement);
-    count = count === undefined ? 1 : count;
-
-    return this.gsub(pattern, function(match) {
-      if (--count < 0) return match[0];
-      return replacement(match);
-    });
-  },
-
-  scan: function(pattern, iterator) {
-    this.gsub(pattern, iterator);
-    return this;
-  },
-
-  truncate: function(length, truncation) {
-    length = length || 30;
-    truncation = truncation === undefined ? '...' : truncation;
-    return this.length > length ?
-      this.slice(0, length - truncation.length) + truncation : this;
-  },
-
-  strip: function() {
-    return this.replace(/^\s+/, '').replace(/\s+$/, '');
-  },
-
-  stripTags: function() {
-    return this.replace(/<\/?[^>]+>/gi, '');
-  },
-
-  stripScripts: function() {
-    return this.replace(new RegExp(Prototype.ScriptFragment, 'img'), '');
-  },
-
-  extractScripts: function() {
-    var matchAll = new RegExp(Prototype.ScriptFragment, 'img');
-    var matchOne = new RegExp(Prototype.ScriptFragment, 'im');
-    return (this.match(matchAll) || []).map(function(scriptTag) {
-      return (scriptTag.match(matchOne) || ['', ''])[1];
-    });
-  },
-
-  evalScripts: function() {
-    return this.extractScripts().map(function(script) { return eval(script) });
-  },
-
-  escapeHTML: function() {
-    var div = document.createElement('div');
-    var text = document.createTextNode(this);
-    div.appendChild(text);
-    return div.innerHTML;
-  },
-
-  unescapeHTML: function() {
-    var div = document.createElement('div');
-    div.innerHTML = this.stripTags();
-    return div.childNodes[0] ? (div.childNodes.length > 1 ?
-      $A(div.childNodes).inject('',function(memo,node){ return memo+node.nodeValue }) :
-      div.childNodes[0].nodeValue) : '';
-  },
-
-  toQueryParams: function(separator) {
-    var match = this.strip().match(/([^?#]*)(#.*)?$/);
-    if (!match) return {};
-
-    return match[1].split(separator || '&').inject({}, function(hash, pair) {
-      if ((pair = pair.split('='))[0]) {
-        var name = decodeURIComponent(pair[0]);
-        var value = pair[1] ? decodeURIComponent(pair[1]) : undefined;
-
-        if (hash[name] !== undefined) {
-          if (hash[name].constructor != Array)
-            hash[name] = [hash[name]];
-          if (value) hash[name].push(value);
-        }
-        else hash[name] = value;
-      }
-      return hash;
-    });
-  },
-
-  toArray: function() {
-    return this.split('');
-  },
-
-  succ: function() {
-    return this.slice(0, this.length - 1) +
-      String.fromCharCode(this.charCodeAt(this.length - 1) + 1);
-  },
-
-  camelize: function() {
-    var parts = this.split('-'), len = parts.length;
-    if (len == 1) return parts[0];
-
-    var camelized = this.charAt(0) == '-'
-      ? parts[0].charAt(0).toUpperCase() + parts[0].substring(1)
-      : parts[0];
-
-    for (var i = 1; i < len; i++)
-      camelized += parts[i].charAt(0).toUpperCase() + parts[i].substring(1);
-
-    return camelized;
-  },
-
-  capitalize: function(){
-    return this.charAt(0).toUpperCase() + this.substring(1).toLowerCase();
-  },
-
-  underscore: function() {
-    return this.gsub(/::/, '/').gsub(/([A-Z]+)([A-Z][a-z])/,'#{1}_#{2}').gsub(/([a-z\d])([A-Z])/,'#{1}_#{2}').gsub(/-/,'_').toLowerCase();
-  },
-
-  dasherize: function() {
-    return this.gsub(/_/,'-');
-  },
-
-  inspect: function(useDoubleQuotes) {
-    var escapedString = this.replace(/\\/g, '\\\\');
-    if (useDoubleQuotes)
-      return '"' + escapedString.replace(/"/g, '\\"') + '"';
-    else
-      return "'" + escapedString.replace(/'/g, '\\\'') + "'";
-  }
-});
-
-String.prototype.gsub.prepareReplacement = function(replacement) {
-  if (typeof replacement == 'function') return replacement;
-  var template = new Template(replacement);
-  return function(match) { return template.evaluate(match) };
-}
-
-String.prototype.parseQuery = String.prototype.toQueryParams;
-
-var Template = Class.create();
-Template.Pattern = /(^|.|\r|\n)(#\{(.*?)\})/;
-Template.prototype = {
-  initialize: function(template, pattern) {
-    this.template = template.toString();
-    this.pattern  = pattern || Template.Pattern;
-  },
-
-  evaluate: function(object) {
-    return this.template.gsub(this.pattern, function(match) {
-      var before = match[1];
-      if (before == '\\') return match[2];
-      return before + String.interpret(object[match[3]]);
-    });
-  }
-}
-
-var $break    = new Object();
-var $continue = new Object();
-
-var Enumerable = {
-  each: function(iterator) {
-    var index = 0;
-    try {
-      this._each(function(value) {
-        try {
-          iterator(value, index++);
-        } catch (e) {
-          if (e != $continue) throw e;
-        }
-      });
-    } catch (e) {
-      if (e != $break) throw e;
-    }
-    return this;
-  },
-
-  eachSlice: function(number, iterator) {
-    var index = -number, slices = [], array = this.toArray();
-    while ((index += number) < array.length)
-      slices.push(array.slice(index, index+number));
-    return slices.map(iterator);
-  },
-
-  all: function(iterator) {
-    var result = true;
-    this.each(function(value, index) {
-      result = result && !!(iterator || Prototype.K)(value, index);
-      if (!result) throw $break;
-    });
-    return result;
-  },
-
-  any: function(iterator) {
-    var result = false;
-    this.each(function(value, index) {
-      if (result = !!(iterator || Prototype.K)(value, index))
-        throw $break;
-    });
-    return result;
-  },
-
-  collect: function(iterator) {
-    var results = [];
-    this.each(function(value, index) {
-      results.push((iterator || Prototype.K)(value, index));
-    });
-    return results;
-  },
-
-  detect: function(iterator) {
-    var result;
-    this.each(function(value, index) {
-      if (iterator(value, index)) {
-        result = value;
-        throw $break;
-      }
-    });
-    return result;
-  },
-
-  findAll: function(iterator) {
-    var results = [];
-    this.each(function(value, index) {
-      if (iterator(value, index))
-        results.push(value);
-    });
-    return results;
-  },
-
-  grep: function(pattern, iterator) {
-    var results = [];
-    this.each(function(value, index) {
-      var stringValue = value.toString();
-      if (stringValue.match(pattern))
-        results.push((iterator || Prototype.K)(value, index));
-    })
-    return results;
-  },
-
-  include: function(object) {
-    var found = false;
-    this.each(function(value) {
-      if (value == object) {
-        found = true;
-        throw $break;
-      }
-    });
-    return found;
-  },
-
-  inGroupsOf: function(number, fillWith) {
-    fillWith = fillWith === undefined ? null : fillWith;
-    return this.eachSlice(number, function(slice) {
-      while(slice.length < number) slice.push(fillWith);
-      return slice;
-    });
-  },
-
-  inject: function(memo, iterator) {
-    this.each(function(value, index) {
-      memo = iterator(memo, value, index);
-    });
-    return memo;
-  },
-
-  invoke: function(method) {
-    var args = $A(arguments).slice(1);
-    return this.map(function(value) {
-      return value[method].apply(value, args);
-    });
-  },
-
-  max: function(iterator) {
-    var result;
-    this.each(function(value, index) {
-      value = (iterator || Prototype.K)(value, index);
-      if (result == undefined || value >= result)
-        result = value;
-    });
-    return result;
-  },
-
-  min: function(iterator) {
-    var result;
-    this.each(function(value, index) {
-      value = (iterator || Prototype.K)(value, index);
-      if (result == undefined || value < result)
-        result = value;
-    });
-    return result;
-  },
-
-  partition: function(iterator) {
-    var trues = [], falses = [];
-    this.each(function(value, index) {
-      ((iterator || Prototype.K)(value, index) ?
-        trues : falses).push(value);
-    });
-    return [trues, falses];
-  },
-
-  pluck: function(property) {
-    var results = [];
-    this.each(function(value, index) {
-      results.push(value[property]);
-    });
-    return results;
-  },
-
-  reject: function(iterator) {
-    var results = [];
-    this.each(function(value, index) {
-      if (!iterator(value, index))
-        results.push(value);
-    });
-    return results;
-  },
-
-  sortBy: function(iterator) {
-    return this.map(function(value, index) {
-      return {value: value, criteria: iterator(value, index)};
-    }).sort(function(left, right) {
-      var a = left.criteria, b = right.criteria;
-      return a < b ? -1 : a > b ? 1 : 0;
-    }).pluck('value');
-  },
-
-  toArray: function() {
-    return this.map();
-  },
-
-  zip: function() {
-    var iterator = Prototype.K, args = $A(arguments);
-    if (typeof args.last() == 'function')
-      iterator = args.pop();
-
-    var collections = [this].concat(args).map($A);
-    return this.map(function(value, index) {
-      return iterator(collections.pluck(index));
-    });
-  },
-
-  size: function() {
-    return this.toArray().length;
-  },
-
-  inspect: function() {
-    return '#<Enumerable:' + this.toArray().inspect() + '>';
-  }
-}
-
-Object.extend(Enumerable, {
-  map:     Enumerable.collect,
-  find:    Enumerable.detect,
-  select:  Enumerable.findAll,
-  member:  Enumerable.include,
-  entries: Enumerable.toArray
-});
-var $A = Array.from = function(iterable) {
-  if (!iterable) return [];
-  if (iterable.toArray) {
-    return iterable.toArray();
-  } else {
-    var results = [];
-    for (var i = 0, length = iterable.length; i < length; i++)
-      results.push(iterable[i]);
-    return results;
-  }
-}
-
-Object.extend(Array.prototype, Enumerable);
-
-if (!Array.prototype._reverse)
-  Array.prototype._reverse = Array.prototype.reverse;
-
-Object.extend(Array.prototype, {
-  _each: function(iterator) {
-    for (var i = 0, length = this.length; i < length; i++)
-      iterator(this[i]);
-  },
-
-  clear: function() {
-    this.length = 0;
-    return this;
-  },
-
-  first: function() {
-    return this[0];
-  },
-
-  last: function() {
-    return this[this.length - 1];
-  },
-
-  compact: function() {
-    return this.select(function(value) {
-      return value != null;
-    });
-  },
-
-  flatten: function() {
-    return this.inject([], function(array, value) {
-      return array.concat(value && value.constructor == Array ?
-        value.flatten() : [value]);
-    });
-  },
-
-  without: function() {
-    var values = $A(arguments);
-    return this.select(function(value) {
-      return !values.include(value);
-    });
-  },
-
-  indexOf: function(object) {
-    for (var i = 0, length = this.length; i < length; i++)
-      if (this[i] == object) return i;
-    return -1;
-  },
-
-  reverse: function(inline) {
-    return (inline !== false ? this : this.toArray())._reverse();
-  },
-
-  reduce: function() {
-    return this.length > 1 ? this : this[0];
-  },
-
-  uniq: function() {
-    return this.inject([], function(array, value) {
-      return array.include(value) ? array : array.concat([value]);
-    });
-  },
-
-  clone: function() {
-    return [].concat(this);
-  },
-
-  size: function() {
-    return this.length;
-  },
-
-  inspect: function() {
-    return '[' + this.map(Object.inspect).join(', ') + ']';
-  }
-});
-
-Array.prototype.toArray = Array.prototype.clone;
-
-function $w(string){
-  string = string.strip();
-  return string ? string.split(/\s+/) : [];
-}
-
-if(window.opera){
-  Array.prototype.concat = function(){
-    var array = [];
-    for(var i = 0, length = this.length; i < length; i++) array.push(this[i]);
-    for(var i = 0, length = arguments.length; i < length; i++) {
-      if(arguments[i].constructor == Array) {
-        for(var j = 0, arrayLength = arguments[i].length; j < arrayLength; j++)
-          array.push(arguments[i][j]);
-      } else {
-        array.push(arguments[i]);
-      }
-    }
-    return array;
-  }
-}
-var Hash = function(obj) {
-  Object.extend(this, obj || {});
-};
-
-Object.extend(Hash, {
-  toQueryString: function(obj) {
-    var parts = [];
-
-	  this.prototype._each.call(obj, function(pair) {
-      if (!pair.key) return;
-
-      if (pair.value && pair.value.constructor == Array) {
-        var values = pair.value.compact();
-        if (values.length < 2) pair.value = values.reduce();
-        else {
-        	key = encodeURIComponent(pair.key);
-          values.each(function(value) {
-            value = value != undefined ? encodeURIComponent(value) : '';
-            parts.push(key + '=' + encodeURIComponent(value));
-          });
-          return;
-        }
-      }
-      if (pair.value == undefined) pair[1] = '';
-      parts.push(pair.map(encodeURIComponent).join('='));
-	  });
-
-    return parts.join('&');
-  }
-});
-
-Object.extend(Hash.prototype, Enumerable);
-Object.extend(Hash.prototype, {
-  _each: function(iterator) {
-    for (var key in this) {
-      var value = this[key];
-      if (value && value == Hash.prototype[key]) continue;
-
-      var pair = [key, value];
-      pair.key = key;
-      pair.value = value;
-      iterator(pair);
-    }
-  },
-
-  keys: function() {
-    return this.pluck('key');
-  },
-
-  values: function() {
-    return this.pluck('value');
-  },
-
-  merge: function(hash) {
-    return $H(hash).inject(this, function(mergedHash, pair) {
-      mergedHash[pair.key] = pair.value;
-      return mergedHash;
-    });
-  },
-
-  remove: function() {
-    var result;
-    for(var i = 0, length = arguments.length; i < length; i++) {
-      var value = this[arguments[i]];
-      if (value !== undefined){
-        if (result === undefined) result = value;
-        else {
-          if (result.constructor != Array) result = [result];
-          result.push(value)
-        }
-      }
-      delete this[arguments[i]];
-    }
-    return result;
-  },
-
-  toQueryString: function() {
-    return Hash.toQueryString(this);
-  },
-
-  inspect: function() {
-    return '#<Hash:{' + this.map(function(pair) {
-      return pair.map(Object.inspect).join(': ');
-    }).join(', ') + '}>';
-  }
-});
-
-function $H(object) {
-  if (object && object.constructor == Hash) return object;
-  return new Hash(object);
-};
-ObjectRange = Class.create();
-Object.extend(ObjectRange.prototype, Enumerable);
-Object.extend(ObjectRange.prototype, {
-  initialize: function(start, end, exclusive) {
-    this.start = start;
-    this.end = end;
-    this.exclusive = exclusive;
-  },
-
-  _each: function(iterator) {
-    var value = this.start;
-    while (this.include(value)) {
-      iterator(value);
-      value = value.succ();
-    }
-  },
-
-  include: function(value) {
-    if (value < this.start)
-      return false;
-    if (this.exclusive)
-      return value < this.end;
-    return value <= this.end;
-  }
-});
-
-var $R = function(start, end, exclusive) {
-  return new ObjectRange(start, end, exclusive);
-}
-
-var Ajax = {
-  getTransport: function() {
-    return Try.these(
-      function() {return new XMLHttpRequest()},
-      function() {return new ActiveXObject('Msxml2.XMLHTTP')},
-      function() {return new ActiveXObject('Microsoft.XMLHTTP')}
-    ) || false;
-  },
-
-  activeRequestCount: 0
-}
-
-Ajax.Responders = {
-  responders: [],
-
-  _each: function(iterator) {
-    this.responders._each(iterator);
-  },
-
-  register: function(responder) {
-    if (!this.include(responder))
-      this.responders.push(responder);
-  },
-
-  unregister: function(responder) {
-    this.responders = this.responders.without(responder);
-  },
-
-  dispatch: function(callback, request, transport, json) {
-    this.each(function(responder) {
-      if (typeof responder[callback] == 'function') {
-        try {
-          responder[callback].apply(responder, [request, transport, json]);
-        } catch (e) {}
-      }
-    });
-  }
 };
 
-Object.extend(Ajax.Responders, Enumerable);
-
-Ajax.Responders.register({
-  onCreate: function() {
-    Ajax.activeRequestCount++;
-  },
-  onComplete: function() {
-    Ajax.activeRequestCount--;
-  }
-});
-
-Ajax.Base = function() {};
-Ajax.Base.prototype = {
-  setOptions: function(options) {
-    this.options = {
-      method:       'post',
-      asynchronous: true,
-      contentType:  'application/x-www-form-urlencoded',
-      encoding:     'UTF-8',
-      parameters:   ''
-    }
-    Object.extend(this.options, options || {});
-
-    this.options.method = this.options.method.toLowerCase();
-    if (typeof this.options.parameters == 'string')
-      this.options.parameters = this.options.parameters.toQueryParams();
-  }
-}
-
-Ajax.Request = Class.create();
-Ajax.Request.Events =
-  ['Uninitialized', 'Loading', 'Loaded', 'Interactive', 'Complete'];
-
-Ajax.Request.prototype = Object.extend(new Ajax.Base(), {
-  _complete: false,
-
-  initialize: function(url, options) {
-    this.transport = Ajax.getTransport();
-    this.setOptions(options);
-    this.request(url);
-  },
-
-  request: function(url) {
-    this.url = url;
-    this.method = this.options.method;
-    var params = this.options.parameters;
-
-    if (!['get', 'post'].include(this.method)) {
-      // simulate other verbs over post
-      params['_method'] = this.method;
-      this.method = 'post';
-    }
-
-    params = Hash.toQueryString(params);
-    if (params && /Konqueror|Safari|KHTML/.test(navigator.userAgent)) params += '&_='
-
-    // when GET, append parameters to URL
-    if (this.method == 'get' && params)
-      this.url += (this.url.indexOf('?') > -1 ? '&' : '?') + params;
-
-    try {
-      Ajax.Responders.dispatch('onCreate', this, this.transport);
-
-      this.transport.open(this.method.toUpperCase(), this.url,
-        this.options.asynchronous);
-
-      if (this.options.asynchronous)
-        setTimeout(function() { this.respondToReadyState(1) }.bind(this), 10);
-
-      this.transport.onreadystatechange = this.onStateChange.bind(this);
-      this.setRequestHeaders();
-
-      var body = this.method == 'post' ? (this.options.postBody || params) : null;
-
-      this.transport.send(body);
-
-      /* Force Firefox to handle ready state 4 for synchronous requests */
-      if (!this.options.asynchronous && this.transport.overrideMimeType)
-        this.onStateChange();
-
-    }
-    catch (e) {
-      this.dispatchException(e);
-    }
-  },
-
-  onStateChange: function() {
-    var readyState = this.transport.readyState;
-    if (readyState > 1 && !((readyState == 4) && this._complete))
-      this.respondToReadyState(this.transport.readyState);
-  },
-
-  setRequestHeaders: function() {
-    var headers = {
-      'X-Requested-With': 'XMLHttpRequest',
-      'X-Prototype-Version': Prototype.Version,
-      'Accept': 'text/javascript, text/html, application/xml, text/xml, */*'
-    };
-
-    if (this.method == 'post') {
-      headers['Content-type'] = this.options.contentType +
-        (this.options.encoding ? '; charset=' + this.options.encoding : '');
-
-      /* Force "Connection: close" for older Mozilla browsers to work
-       * around a bug where XMLHttpRequest sends an incorrect
-       * Content-length header. See Mozilla Bugzilla #246651.
-       */
-      if (this.transport.overrideMimeType &&
-          (navigator.userAgent.match(/Gecko\/(\d{4})/) || [0,2005])[1] < 2005)
-            headers['Connection'] = 'close';
-    }
-
-    // user-defined headers
-    if (typeof this.options.requestHeaders == 'object') {
-      var extras = this.options.requestHeaders;
-
-      if (typeof extras.push == 'function')
-        for (var i = 0, length = extras.length; i < length; i += 2)
-          headers[extras[i]] = extras[i+1];
-      else
-        $H(extras).each(function(pair) { headers[pair.key] = pair.value });
-    }
-
-    for (var name in headers)
-      this.transport.setRequestHeader(name, headers[name]);
-  },
-
-  success: function() {
-    return !this.transport.status
-        || (this.transport.status >= 200 && this.transport.status < 300);
-  },
-
-  respondToReadyState: function(readyState) {
-    var state = Ajax.Request.Events[readyState];
-    var transport = this.transport, json = this.evalJSON();
-
-    if (state == 'Complete') {
-      try {
-        this._complete = true;
-        (this.options['on' + this.transport.status]
-         || this.options['on' + (this.success() ? 'Success' : 'Failure')]
-         || Prototype.emptyFunction)(transport, json);
-      } catch (e) {
-        this.dispatchException(e);
-      }
-
-      if ((this.getHeader('Content-type') || 'text/javascript').strip().
-        match(/^(text|application)\/(x-)?(java|ecma)script(;.*)?$/i))
-          this.evalResponse();
-    }
-
-    try {
-      (this.options['on' + state] || Prototype.emptyFunction)(transport, json);
-      Ajax.Responders.dispatch('on' + state, this, transport, json);
-    } catch (e) {
-      this.dispatchException(e);
-    }
-
-    if (state == 'Complete') {
-      // avoid memory leak in MSIE: clean up
-      this.transport.onreadystatechange = Prototype.emptyFunction;
-    }
-  },
-
-  getHeader: function(name) {
-    try {
-      return this.transport.getResponseHeader(name);
-    } catch (e) { return null }
-  },
-
-  evalJSON: function() {
-    try {
-      var json = this.getHeader('X-JSON');
-      return json ? eval('(' + json + ')') : null;
-    } catch (e) { return null }
-  },
-
-  evalResponse: function() {
-    try {
-      return eval(this.transport.responseText);
-    } catch (e) {
-      this.dispatchException(e);
-    }
-  },
-
-  dispatchException: function(exception) {
-    (this.options.onException || Prototype.emptyFunction)(this, exception);
-    Ajax.Responders.dispatch('onException', this, exception);
-  }
-});
-
-Ajax.Updater = Class.create();
-
-Object.extend(Object.extend(Ajax.Updater.prototype, Ajax.Request.prototype), {
-  initialize: function(container, url, options) {
-    this.container = {
-      success: (container.success || container),
-      failure: (container.failure || (container.success ? null : container))
-    }
-
-    this.transport = Ajax.getTransport();
-    this.setOptions(options);
-
-    var onComplete = this.options.onComplete || Prototype.emptyFunction;
-    this.options.onComplete = (function(transport, param) {
-      this.updateContent();
-      onComplete(transport, param);
-    }).bind(this);
-
-    this.request(url);
-  },
-
-  updateContent: function() {
-    var receiver = this.container[this.success() ? 'success' : 'failure'];
-    var response = this.transport.responseText;
-
-    if (!this.options.evalScripts) response = response.stripScripts();
-
-    if (receiver = $(receiver)) {
-      if (this.options.insertion)
-        new this.options.insertion(receiver, response);
-      else
-        receiver.update(response);
-    }
-
-    if (this.success()) {
-      if (this.onComplete)
-        setTimeout(this.onComplete.bind(this), 10);
-    }
-  }
-});
-
-Ajax.PeriodicalUpdater = Class.create();
-Ajax.PeriodicalUpdater.prototype = Object.extend(new Ajax.Base(), {
-  initialize: function(container, url, options) {
-    this.setOptions(options);
-    this.onComplete = this.options.onComplete;
-
-    this.frequency = (this.options.frequency || 2);
-    this.decay = (this.options.decay || 1);
-
-    this.updater = {};
-    this.container = container;
-    this.url = url;
-
-    this.start();
-  },
-
-  start: function() {
-    this.options.onComplete = this.updateComplete.bind(this);
-    this.onTimerEvent();
-  },
-
-  stop: function() {
-    this.updater.options.onComplete = undefined;
-    clearTimeout(this.timer);
-    (this.onComplete || Prototype.emptyFunction).apply(this, arguments);
-  },
-
-  updateComplete: function(request) {
-    if (this.options.decay) {
-      this.decay = (request.responseText == this.lastText ?
-        this.decay * this.options.decay : 1);
-
-      this.lastText = request.responseText;
-    }
-    this.timer = setTimeout(this.onTimerEvent.bind(this),
-      this.decay * this.frequency * 1000);
-  },
-
-  onTimerEvent: function() {
-    this.updater = new Ajax.Updater(this.container, this.url, this.options);
-  }
-});
-function $(element) {
-  if (arguments.length > 1) {
-    for (var i = 0, elements = [], length = arguments.length; i < length; i++)
-      elements.push($(arguments[i]));
-    return elements;
-  }
-  if (typeof element == 'string')
-    element = document.getElementById(element);
-  return Element.extend(element);
-}
-
-if (Prototype.BrowserFeatures.XPath) {
-  document._getElementsByXPath = function(expression, parentElement) {
-    var results = [];
-    var query = document.evaluate(expression, $(parentElement) || document,
-      null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
-    for (var i = 0, length = query.snapshotLength; i < length; i++)
-      results.push(query.snapshotItem(i));
-    return results;
-  };
-}
-
-document.getElementsByClassName = function(className, parentElement) {
-  if (Prototype.BrowserFeatures.XPath) {
-    var q = ".//*[contains(concat(' ', @class, ' '), ' " + className + " ')]";
-    return document._getElementsByXPath(q, parentElement);
-  } else {
-    var children = ($(parentElement) || document.body).getElementsByTagName('*');
-    var elements = [], child;
-    for (var i = 0, length = children.length; i < length; i++) {
-      child = children[i];
-      if (Element.hasClassName(child, className))
-        elements.push(Element.extend(child));
-    }
-    return elements;
-  }
-};
-
-/*--------------------------------------------------------------------------*/
-
-if (!window.Element)
-  var Element = new Object();
-
-Element.extend = function(element) {
-  if (!element || _nativeExtensions || element.nodeType == 3) return element;
-
-  if (!element._extended && element.tagName && element != window) {
-    var methods = Object.clone(Element.Methods), cache = Element.extend.cache;
-
-    if (element.tagName == 'FORM')
-      Object.extend(methods, Form.Methods);
-    if (['INPUT', 'TEXTAREA', 'SELECT'].include(element.tagName))
-      Object.extend(methods, Form.Element.Methods);
-
-    Object.extend(methods, Element.Methods.Simulated);
-
-    for (var property in methods) {
-      var value = methods[property];
-      if (typeof value == 'function' && !(property in element))
-        element[property] = cache.findOrStore(value);
-    }
-  }
-
-  element._extended = true;
-  return element;
-};
-
-Element.extend.cache = {
-  findOrStore: function(value) {
-    return this[value] = this[value] || function() {
-      return value.apply(null, [this].concat($A(arguments)));
-    }
-  }
-};
-
-Element.Methods = {
-  visible: function(element) {
-    return $(element).style.display != 'none';
-  },
-
-  toggle: function(element) {
-    element = $(element);
-    Element[Element.visible(element) ? 'hide' : 'show'](element);
-    return element;
-  },
-
-  hide: function(element) {
-    $(element).style.display = 'none';
-    return element;
-  },
-
-  show: function(element) {
-    $(element).style.display = '';
-    return element;
-  },
-
-  remove: function(element) {
-    element = $(element);
-    element.parentNode.removeChild(element);
-    return element;
-  },
-
-  update: function(element, html) {
-    html = typeof html == 'undefined' ? '' : html.toString();
-    $(element).innerHTML = html.stripScripts();
-    setTimeout(function() {html.evalScripts()}, 10);
-    return element;
-  },
-
-  replace: function(element, html) {
-    element = $(element);
-    html = typeof html == 'undefined' ? '' : html.toString();
-    if (element.outerHTML) {
-      element.outerHTML = html.stripScripts();
-    } else {
-      var range = element.ownerDocument.createRange();
-      range.selectNodeContents(element);
-      element.parentNode.replaceChild(
-        range.createContextualFragment(html.stripScripts()), element);
-    }
-    setTimeout(function() {html.evalScripts()}, 10);
-    return element;
-  },
-
-  inspect: function(element) {
-    element = $(element);
-    var result = '<' + element.tagName.toLowerCase();
-    $H({'id': 'id', 'className': 'class'}).each(function(pair) {
-      var property = pair.first(), attribute = pair.last();
-      var value = (element[property] || '').toString();
-      if (value) result += ' ' + attribute + '=' + value.inspect(true);
-    });
-    return result + '>';
-  },
-
-  recursivelyCollect: function(element, property) {
-    element = $(element);
-    var elements = [];
-    while (element = element[property])
-      if (element.nodeType == 1)
-        elements.push(Element.extend(element));
-    return elements;
-  },
-
-  ancestors: function(element) {
-    return $(element).recursivelyCollect('parentNode');
-  },
-
-  descendants: function(element) {
-    return $A($(element).getElementsByTagName('*'));
-  },
-
-  immediateDescendants: function(element) {
-    if (!(element = $(element).firstChild)) return [];
-    while (element && element.nodeType != 1) element = element.nextSibling;
-    if (element) return [element].concat($(element).nextSiblings());
-    return [];
-  },
-
-  previousSiblings: function(element) {
-    return $(element).recursivelyCollect('previousSibling');
-  },
-
-  nextSiblings: function(element) {
-    return $(element).recursivelyCollect('nextSibling');
-  },
-
-  siblings: function(element) {
-    element = $(element);
-    return element.previousSiblings().reverse().concat(element.nextSiblings());
-  },
-
-  match: function(element, selector) {
-    if (typeof selector == 'string')
-      selector = new Selector(selector);
-    return selector.match($(element));
-  },
-
-  up: function(element, expression, index) {
-    return Selector.findElement($(element).ancestors(), expression, index);
-  },
-
-  down: function(element, expression, index) {
-    return Selector.findElement($(element).descendants(), expression, index);
-  },
-
-  previous: function(element, expression, index) {
-    return Selector.findElement($(element).previousSiblings(), expression, index);
-  },
-
-  next: function(element, expression, index) {
-    return Selector.findElement($(element).nextSiblings(), expression, index);
-  },
-
-  getElementsBySelector: function() {
-    var args = $A(arguments), element = $(args.shift());
-    return Selector.findChildElements(element, args);
-  },
-
-  getElementsByClassName: function(element, className) {
-    return document.getElementsByClassName(className, element);
-  },
-
-  readAttribute: function(element, name) {
-    element = $(element);
-    if (document.all && !window.opera) {
-      var t = Element._attributeTranslations;
-      if (t.values[name]) return t.values[name](element, name);
-      if (t.names[name])  name = t.names[name];
-      var attribute = element.attributes[name];
-      if(attribute) return attribute.nodeValue;
-    }
-    return element.getAttribute(name);
-  },
-
-  getHeight: function(element) {
-    return $(element).getDimensions().height;
-  },
-
-  getWidth: function(element) {
-    return $(element).getDimensions().width;
-  },
-
-  classNames: function(element) {
-    return new Element.ClassNames(element);
-  },
-
-  hasClassName: function(element, className) {
-    if (!(element = $(element))) return;
-    var elementClassName = element.className;
-    if (elementClassName.length == 0) return false;
-    if (elementClassName == className ||
-        elementClassName.match(new RegExp("(^|\\s)" + className + "(\\s|$)")))
-      return true;
-    return false;
-  },
-
-  addClassName: function(element, className) {
-    if (!(element = $(element))) return;
-    Element.classNames(element).add(className);
-    return element;
-  },
-
-  removeClassName: function(element, className) {
-    if (!(element = $(element))) return;
-    Element.classNames(element).remove(className);
-    return element;
-  },
-
-  toggleClassName: function(element, className) {
-    if (!(element = $(element))) return;
-    Element.classNames(element)[element.hasClassName(className) ? 'remove' : 'add'](className);
-    return element;
-  },
-
-  observe: function() {
-    Event.observe.apply(Event, arguments);
-    return $A(arguments).first();
-  },
-
-  stopObserving: function() {
-    Event.stopObserving.apply(Event, arguments);
-    return $A(arguments).first();
-  },
-
-  // removes whitespace-only text node children
-  cleanWhitespace: function(element) {
-    element = $(element);
-    var node = element.firstChild;
-    while (node) {
-      var nextNode = node.nextSibling;
-      if (node.nodeType == 3 && !/\S/.test(node.nodeValue))
-        element.removeChild(node);
-      node = nextNode;
-    }
-    return element;
-  },
-
-  empty: function(element) {
-    return $(element).innerHTML.match(/^\s*$/);
-  },
-
-  descendantOf: function(element, ancestor) {
-    element = $(element), ancestor = $(ancestor);
-    while (element = element.parentNode)
-      if (element == ancestor) return true;
-    return false;
-  },
-
-  scrollTo: function(element) {
-    element = $(element);
-    var pos = Position.cumulativeOffset(element);
-    window.scrollTo(pos[0], pos[1]);
-    return element;
-  },
-
-  getStyle: function(element, style) {
-    element = $(element);
-    if (['float','cssFloat'].include(style))
-      style = (typeof element.style.styleFloat != 'undefined' ? 'styleFloat' : 'cssFloat');
-    style = style.camelize();
-    var value = element.style[style];
-    if (!value) {
-      if (document.defaultView && document.defaultView.getComputedStyle) {
-        var css = document.defaultView.getComputedStyle(element, null);
-        value = css ? css[style] : null;
-      } else if (element.currentStyle) {
-        value = element.currentStyle[style];
-      }
-    }
-
-    if((value == 'auto') && ['width','height'].include(style) && (element.getStyle('display') != 'none'))
-      value = element['offset'+style.capitalize()] + 'px';
-
-    if (window.opera && ['left', 'top', 'right', 'bottom'].include(style))
-      if (Element.getStyle(element, 'position') == 'static') value = 'auto';
-    if(style == 'opacity') {
-      if(value) return parseFloat(value);
-      if(value = (element.getStyle('filter') || '').match(/alpha\(opacity=(.*)\)/))
-        if(value[1]) return parseFloat(value[1]) / 100;
-      return 1.0;
-    }
-    return value == 'auto' ? null : value;
-  },
-
-  setStyle: function(element, style) {
-    element = $(element);
-    for (var name in style) {
-      var value = style[name];
-      if(name == 'opacity') {
-        if (value == 1) {
-          value = (/Gecko/.test(navigator.userAgent) &&
-            !/Konqueror|Safari|KHTML/.test(navigator.userAgent)) ? 0.999999 : 1.0;
-          if(/MSIE/.test(navigator.userAgent) && !window.opera)
-            element.style.filter = element.getStyle('filter').replace(/alpha\([^\)]*\)/gi,'');
-        } else if(value == '') {
-          if(/MSIE/.test(navigator.userAgent) && !window.opera)
-            element.style.filter = element.getStyle('filter').replace(/alpha\([^\)]*\)/gi,'');
-        } else {
-          if(value < 0.00001) value = 0;
-          if(/MSIE/.test(navigator.userAgent) && !window.opera)
-            element.style.filter = element.getStyle('filter').replace(/alpha\([^\)]*\)/gi,'') +
-              'alpha(opacity='+value*100+')';
-        }
-      } else if(['float','cssFloat'].include(name)) name = (typeof element.style.styleFloat != 'undefined') ? 'styleFloat' : 'cssFloat';
-      element.style[name.camelize()] = value;
-    }
-    return element;
-  },
-
-  getDimensions: function(element) {
-    element = $(element);
-    var display = $(element).getStyle('display');
-    if (display != 'none' && display != null) // Safari bug
-      return {width: element.offsetWidth, height: element.offsetHeight};
-
-    // All *Width and *Height properties give 0 on elements with display none,
-    // so enable the element temporarily
-    var els = element.style;
-    var originalVisibility = els.visibility;
-    var originalPosition = els.position;
-    var originalDisplay = els.display;
-    els.visibility = 'hidden';
-    els.position = 'absolute';
-    els.display = 'block';
-    var originalWidth = element.clientWidth;
-    var originalHeight = element.clientHeight;
-    els.display = originalDisplay;
-    els.position = originalPosition;
-    els.visibility = originalVisibility;
-    return {width: originalWidth, height: originalHeight};
-  },
-
-  makePositioned: function(element) {
-    element = $(element);
-    var pos = Element.getStyle(element, 'position');
-    if (pos == 'static' || !pos) {
-      element._madePositioned = true;
-      element.style.position = 'relative';
-      // Opera returns the offset relative to the positioning context, when an
-      // element is position relative but top and left have not been defined
-      if (window.opera) {
-        element.style.top = 0;
-        element.style.left = 0;
-      }
-    }
-    return element;
-  },
-
-  undoPositioned: function(element) {
-    element = $(element);
-    if (element._madePositioned) {
-      element._madePositioned = undefined;
-      element.style.position =
-        element.style.top =
-        element.style.left =
-        element.style.bottom =
-        element.style.right = '';
-    }
-    return element;
-  },
-
-  makeClipping: function(element) {
-    element = $(element);
-    if (element._overflow) return element;
-    element._overflow = element.style.overflow || 'auto';
-    if ((Element.getStyle(element, 'overflow') || 'visible') != 'hidden')
-      element.style.overflow = 'hidden';
-    return element;
-  },
-
-  undoClipping: function(element) {
-    element = $(element);
-    if (!element._overflow) return element;
-    element.style.overflow = element._overflow == 'auto' ? '' : element._overflow;
-    element._overflow = null;
-    return element;
-  }
-};
-
-Object.extend(Element.Methods, {childOf: Element.Methods.descendantOf});
-
-Element._attributeTranslations = {};
-
-Element._attributeTranslations.names = {
-  colspan:   "colSpan",
-  rowspan:   "rowSpan",
-  valign:    "vAlign",
-  datetime:  "dateTime",
-  accesskey: "accessKey",
-  tabindex:  "tabIndex",
-  enctype:   "encType",
-  maxlength: "maxLength",
-  readonly:  "readOnly",
-  longdesc:  "longDesc"
-};
-
-Element._attributeTranslations.values = {
-  _getAttr: function(element, attribute) {
-    return element.getAttribute(attribute, 2);
-  },
-
-  _flag: function(element, attribute) {
-    return $(element).hasAttribute(attribute) ? attribute : null;
-  },
-
-  style: function(element) {
-    return element.style.cssText.toLowerCase();
-  },
-
-  title: function(element) {
-    var node = element.getAttributeNode('title');
-    return node.specified ? node.nodeValue : null;
-  }
-};
-
-Object.extend(Element._attributeTranslations.values, {
-  href: Element._attributeTranslations.values._getAttr,
-  src:  Element._attributeTranslations.values._getAttr,
-  disabled: Element._attributeTranslations.values._flag,
-  checked:  Element._attributeTranslations.values._flag,
-  readonly: Element._attributeTranslations.values._flag,
-  multiple: Element._attributeTranslations.values._flag
-});
-
-Element.Methods.Simulated = {
-  hasAttribute: function(element, attribute) {
-    var t = Element._attributeTranslations;
-    attribute = t.names[attribute] || attribute;
-    return $(element).getAttributeNode(attribute).specified;
-  }
-};
-
-// IE is missing .innerHTML support for TABLE-related elements
-if (document.all && !window.opera){
-  Element.Methods.update = function(element, html) {
-    element = $(element);
-    html = typeof html == 'undefined' ? '' : html.toString();
-    var tagName = element.tagName.toUpperCase();
-    if (['THEAD','TBODY','TR','TD'].include(tagName)) {
-      var div = document.createElement('div');
-      switch (tagName) {
-        case 'THEAD':
-        case 'TBODY':
-          div.innerHTML = '<table><tbody>' +  html.stripScripts() + '</tbody></table>';
-          depth = 2;
-          break;
-        case 'TR':
-          div.innerHTML = '<table><tbody><tr>' +  html.stripScripts() + '</tr></tbody></table>';
-          depth = 3;
-          break;
-        case 'TD':
-          div.innerHTML = '<table><tbody><tr><td>' +  html.stripScripts() + '</td></tr></tbody></table>';
-          depth = 4;
-      }
-      $A(element.childNodes).each(function(node){
-        element.removeChild(node)
-      });
-      depth.times(function(){ div = div.firstChild });
-
-      $A(div.childNodes).each(
-        function(node){ element.appendChild(node) });
-    } else {
-      element.innerHTML = html.stripScripts();
-    }
-    setTimeout(function() {html.evalScripts()}, 10);
-    return element;
-  }
-};
-
-Object.extend(Element, Element.Methods);
-
-var _nativeExtensions = false;
-
-if(/Konqueror|Safari|KHTML/.test(navigator.userAgent))
-  ['', 'Form', 'Input', 'TextArea', 'Select'].each(function(tag) {
-    var className = 'HTML' + tag + 'Element';
-    if(window[className]) return;
-    var klass = window[className] = {};
-    klass.prototype = document.createElement(tag ? tag.toLowerCase() : 'div').__proto__;
-  });
-
-Element.addMethods = function(methods) {
-  Object.extend(Element.Methods, methods || {});
-
-  function copy(methods, destination, onlyIfAbsent) {
-    onlyIfAbsent = onlyIfAbsent || false;
-    var cache = Element.extend.cache;
-    for (var property in methods) {
-      var value = methods[property];
-      if (!onlyIfAbsent || !(property in destination))
-        destination[property] = cache.findOrStore(value);
-    }
-  }
-
-  if (typeof HTMLElement != 'undefined') {
-    copy(Element.Methods, HTMLElement.prototype);
-    copy(Element.Methods.Simulated, HTMLElement.prototype, true);
-    copy(Form.Methods, HTMLFormElement.prototype);
-    [HTMLInputElement, HTMLTextAreaElement, HTMLSelectElement].each(function(klass) {
-      copy(Form.Element.Methods, klass.prototype);
-    });
-    _nativeExtensions = true;
-  }
-}
-
-var Toggle = new Object();
-Toggle.display = Element.toggle;
-
-/*--------------------------------------------------------------------------*/
-
-Abstract.Insertion = function(adjacency) {
-  this.adjacency = adjacency;
-}
-
-Abstract.Insertion.prototype = {
-  initialize: function(element, content) {
-    this.element = $(element);
-    this.content = content.stripScripts();
-
-    if (this.adjacency && this.element.insertAdjacentHTML) {
-      try {
-        this.element.insertAdjacentHTML(this.adjacency, this.content);
-      } catch (e) {
-        var tagName = this.element.tagName.toUpperCase();
-        if (['TBODY', 'TR'].include(tagName)) {
-          this.insertContent(this.contentFromAnonymousTable());
-        } else {
-          throw e;
-        }
-      }
-    } else {
-      this.range = this.element.ownerDocument.createRange();
-      if (this.initializeRange) this.initializeRange();
-      this.insertContent([this.range.createContextualFragment(this.content)]);
-    }
-
-    setTimeout(function() {content.evalScripts()}, 10);
-  },
-
-  contentFromAnonymousTable: function() {
-    var div = document.createElement('div');
-    div.innerHTML = '<table><tbody>' + this.content + '</tbody></table>';
-    return $A(div.childNodes[0].childNodes[0].childNodes);
-  }
-}
-
-var Insertion = new Object();
-
-Insertion.Before = Class.create();
-Insertion.Before.prototype = Object.extend(new Abstract.Insertion('beforeBegin'), {
-  initializeRange: function() {
-    this.range.setStartBefore(this.element);
-  },
-
-  insertContent: function(fragments) {
-    fragments.each((function(fragment) {
-      this.element.parentNode.insertBefore(fragment, this.element);
-    }).bind(this));
-  }
-});
-
-Insertion.Top = Class.create();
-Insertion.Top.prototype = Object.extend(new Abstract.Insertion('afterBegin'), {
-  initializeRange: function() {
-    this.range.selectNodeContents(this.element);
-    this.range.collapse(true);
-  },
-
-  insertContent: function(fragments) {
-    fragments.reverse(false).each((function(fragment) {
-      this.element.insertBefore(fragment, this.element.firstChild);
-    }).bind(this));
-  }
-});
-
-Insertion.Bottom = Class.create();
-Insertion.Bottom.prototype = Object.extend(new Abstract.Insertion('beforeEnd'), {
-  initializeRange: function() {
-    this.range.selectNodeContents(this.element);
-    this.range.collapse(this.element);
-  },
-
-  insertContent: function(fragments) {
-    fragments.each((function(fragment) {
-      this.element.appendChild(fragment);
-    }).bind(this));
-  }
-});
-
-Insertion.After = Class.create();
-Insertion.After.prototype = Object.extend(new Abstract.Insertion('afterEnd'), {
-  initializeRange: function() {
-    this.range.setStartAfter(this.element);
-  },
-
-  insertContent: function(fragments) {
-    fragments.each((function(fragment) {
-      this.element.parentNode.insertBefore(fragment,
-        this.element.nextSibling);
-    }).bind(this));
-  }
-});
-
-/*--------------------------------------------------------------------------*/
-
-Element.ClassNames = Class.create();
-Element.ClassNames.prototype = {
-  initialize: function(element) {
-    this.element = $(element);
-  },
-
-  _each: function(iterator) {
-    this.element.className.split(/\s+/).select(function(name) {
-      return name.length > 0;
-    })._each(iterator);
-  },
-
-  set: function(className) {
-    this.element.className = className;
-  },
-
-  add: function(classNameToAdd) {
-    if (this.include(classNameToAdd)) return;
-    this.set($A(this).concat(classNameToAdd).join(' '));
-  },
-
-  remove: function(classNameToRemove) {
-    if (!this.include(classNameToRemove)) return;
-    this.set($A(this).without(classNameToRemove).join(' '));
-  },
-
-  toString: function() {
-    return $A(this).join(' ');
-  }
-};
-
-Object.extend(Element.ClassNames.prototype, Enumerable);
-var Selector = Class.create();
-Selector.prototype = {
-  initialize: function(expression) {
-    this.params = {classNames: []};
-    this.expression = expression.toString().strip();
-    this.parseExpression();
-    this.compileMatcher();
-  },
-
-  parseExpression: function() {
-    function abort(message) { throw 'Parse error in selector: ' + message; }
-
-    if (this.expression == '')  abort('empty expression');
-
-    var params = this.params, expr = this.expression, match, modifier, clause, rest;
-    while (match = expr.match(/^(.*)\[([a-z0-9_:-]+?)(?:([~\|!]?=)(?:"([^"]*)"|([^\]\s]*)))?\]$/i)) {
-      params.attributes = params.attributes || [];
-      params.attributes.push({name: match[2], operator: match[3], value: match[4] || match[5] || ''});
-      expr = match[1];
-    }
-
-    if (expr == '*') return this.params.wildcard = true;
-
-    while (match = expr.match(/^([^a-z0-9_-])?([a-z0-9_-]+)(.*)/i)) {
-      modifier = match[1], clause = match[2], rest = match[3];
-      switch (modifier) {
-        case '#':       params.id = clause; break;
-        case '.':       params.classNames.push(clause); break;
-        case '':
-        case undefined: params.tagName = clause.toUpperCase(); break;
-        default:        abort(expr.inspect());
-      }
-      expr = rest;
-    }
-
-    if (expr.length > 0) abort(expr.inspect());
-  },
-
-  buildMatchExpression: function() {
-    var params = this.params, conditions = [], clause;
-
-    if (params.wildcard)
-      conditions.push('true');
-    if (clause = params.id)
-      conditions.push('element.readAttribute("id") == ' + clause.inspect());
-    if (clause = params.tagName)
-      conditions.push('element.tagName.toUpperCase() == ' + clause.inspect());
-    if ((clause = params.classNames).length > 0)
-      for (var i = 0, length = clause.length; i < length; i++)
-        conditions.push('element.hasClassName(' + clause[i].inspect() + ')');
-    if (clause = params.attributes) {
-      clause.each(function(attribute) {
-        var value = 'element.readAttribute(' + attribute.name.inspect() + ')';
-        var splitValueBy = function(delimiter) {
-          return value + ' && ' + value + '.split(' + delimiter.inspect() + ')';
-        }
-
-        switch (attribute.operator) {
-          case '=':       conditions.push(value + ' == ' + attribute.value.inspect()); break;
-          case '~=':      conditions.push(splitValueBy(' ') + '.include(' + attribute.value.inspect() + ')'); break;
-          case '|=':      conditions.push(
-                            splitValueBy('-') + '.first().toUpperCase() == ' + attribute.value.toUpperCase().inspect()
-                          ); break;
-          case '!=':      conditions.push(value + ' != ' + attribute.value.inspect()); break;
-          case '':
-          case undefined: conditions.push('element.hasAttribute(' + attribute.name.inspect() + ')'); break;
-          default:        throw 'Unknown operator ' + attribute.operator + ' in selector';
-        }
-      });
-    }
-
-    return conditions.join(' && ');
-  },
-
-  compileMatcher: function() {
-    this.match = new Function('element', 'if (!element.tagName) return false; \
-      element = $(element); \
-      return ' + this.buildMatchExpression());
-  },
-
-  findElements: function(scope) {
-    var element;
-
-    if (element = $(this.params.id))
-      if (this.match(element))
-        if (!scope || Element.childOf(element, scope))
-          return [element];
-
-    scope = (scope || document).getElementsByTagName(this.params.tagName || '*');
-
-    var results = [];
-    for (var i = 0, length = scope.length; i < length; i++)
-      if (this.match(element = scope[i]))
-        results.push(Element.extend(element));
-
-    return results;
-  },
-
-  toString: function() {
-    return this.expression;
-  }
-}
-
-Object.extend(Selector, {
-  matchElements: function(elements, expression) {
-    var selector = new Selector(expression);
-    return elements.select(selector.match.bind(selector)).map(Element.extend);
-  },
-
-  findElement: function(elements, expression, index) {
-    if (typeof expression == 'number') index = expression, expression = false;
-    return Selector.matchElements(elements, expression || '*')[index || 0];
-  },
-
-  findChildElements: function(element, expressions) {
-    return expressions.map(function(expression) {
-      return expression.match(/[^\s"]+(?:"[^"]*"[^\s"]+)*/g).inject([null], function(results, expr) {
-        var selector = new Selector(expr);
-        return results.inject([], function(elements, result) {
-          return elements.concat(selector.findElements(result || element));
-        });
-      });
-    }).flatten();
-  }
-});
-
-function $$() {
-  return Selector.findChildElements(document, $A(arguments));
-}
-var Form = {
-  reset: function(form) {
-    $(form).reset();
-    return form;
-  },
-
-  serializeElements: function(elements, getHash) {
-    var data = elements.inject({}, function(result, element) {
-      if (!element.disabled && element.name) {
-        var key = element.name, value = $(element).getValue();
-        if (value != undefined) {
-          if (result[key]) {
-            if (result[key].constructor != Array) result[key] = [result[key]];
-            result[key].push(value);
-          }
-          else result[key] = value;
-        }
-      }
-      return result;
-    });
-
-    return getHash ? data : Hash.toQueryString(data);
-  }
-};
-
-Form.Methods = {
-  serialize: function(form, getHash) {
-    return Form.serializeElements(Form.getElements(form), getHash);
-  },
-
-  getElements: function(form) {
-    return $A($(form).getElementsByTagName('*')).inject([],
-      function(elements, child) {
-        if (Form.Element.Serializers[child.tagName.toLowerCase()])
-          elements.push(Element.extend(child));
-        return elements;
-      }
-    );
-  },
-
-  getInputs: function(form, typeName, name) {
-    form = $(form);
-    var inputs = form.getElementsByTagName('input');
-
-    if (!typeName && !name) return $A(inputs).map(Element.extend);
-
-    for (var i = 0, matchingInputs = [], length = inputs.length; i < length; i++) {
-      var input = inputs[i];
-      if ((typeName && input.type != typeName) || (name && input.name != name))
-        continue;
-      matchingInputs.push(Element.extend(input));
-    }
-
-    return matchingInputs;
-  },
-
-  disable: function(form) {
-    form = $(form);
-    form.getElements().each(function(element) {
-      element.blur();
-      element.disabled = 'true';
-    });
-    return form;
-  },
-
-  enable: function(form) {
-    form = $(form);
-    form.getElements().each(function(element) {
-      element.disabled = '';
-    });
-    return form;
-  },
-
-  findFirstElement: function(form) {
-    return $(form).getElements().find(function(element) {
-      return element.type != 'hidden' && !element.disabled &&
-        ['input', 'select', 'textarea'].include(element.tagName.toLowerCase());
-    });
-  },
-
-  focusFirstElement: function(form) {
-    form = $(form);
-    form.findFirstElement().activate();
-    return form;
-  }
-}
-
-Object.extend(Form, Form.Methods);
-
-/*--------------------------------------------------------------------------*/
-
-Form.Element = {
-  focus: function(element) {
-    $(element).focus();
-    return element;
-  },
-
-  select: function(element) {
-    $(element).select();
-    return element;
-  }
-}
-
-Form.Element.Methods = {
-  serialize: function(element) {
-    element = $(element);
-    if (!element.disabled && element.name) {
-      var value = element.getValue();
-      if (value != undefined) {
-        var pair = {};
-        pair[element.name] = value;
-        return Hash.toQueryString(pair);
-      }
-    }
-    return '';
-  },
-
-  getValue: function(element) {
-    element = $(element);
-    var method = element.tagName.toLowerCase();
-    return Form.Element.Serializers[method](element);
-  },
-
-  clear: function(element) {
-    $(element).value = '';
-    return element;
-  },
-
-  present: function(element) {
-    return $(element).value != '';
-  },
-
-  activate: function(element) {
-    element = $(element);
-    element.focus();
-    if (element.select && ( element.tagName.toLowerCase() != 'input' ||
-      !['button', 'reset', 'submit'].include(element.type) ) )
-      element.select();
-    return element;
-  },
-
-  disable: function(element) {
-    element = $(element);
-    element.disabled = true;
-    return element;
-  },
-
-  enable: function(element) {
-    element = $(element);
-    element.blur();
-    element.disabled = false;
-    return element;
-  }
-}
-
-Object.extend(Form.Element, Form.Element.Methods);
-var Field = Form.Element;
-var $F = Form.Element.getValue;
-
-/*--------------------------------------------------------------------------*/
-
-Form.Element.Serializers = {
-  input: function(element) {
-    switch (element.type.toLowerCase()) {
-      case 'checkbox':
-      case 'radio':
-        return Form.Element.Serializers.inputSelector(element);
-      default:
-        return Form.Element.Serializers.textarea(element);
-    }
-  },
-
-  inputSelector: function(element) {
-    return element.checked ? element.value : null;
-  },
-
-  textarea: function(element) {
-    return element.value;
-  },
-
-  select: function(element) {
-    return this[element.type == 'select-one' ?
-      'selectOne' : 'selectMany'](element);
-  },
-
-  selectOne: function(element) {
-    var index = element.selectedIndex;
-    return index >= 0 ? this.optionValue(element.options[index]) : null;
-  },
-
-  selectMany: function(element) {
-    var values, length = element.length;
-    if (!length) return null;
-
-    for (var i = 0, values = []; i < length; i++) {
-      var opt = element.options[i];
-      if (opt.selected) values.push(this.optionValue(opt));
-    }
-    return values;
-  },
-
-  optionValue: function(opt) {
-    // extend element because hasAttribute may not be native
-    return Element.extend(opt).hasAttribute('value') ? opt.value : opt.text;
-  }
-}
-
-/*--------------------------------------------------------------------------*/
-
-Abstract.TimedObserver = function() {}
-Abstract.TimedObserver.prototype = {
-  initialize: function(element, frequency, callback) {
-    this.frequency = frequency;
-    this.element   = $(element);
-    this.callback  = callback;
-
-    this.lastValue = this.getValue();
-    this.registerCallback();
-  },
-
-  registerCallback: function() {
-    setInterval(this.onTimerEvent.bind(this), this.frequency * 1000);
-  },
-
-  onTimerEvent: function() {
-    var value = this.getValue();
-    var changed = ('string' == typeof this.lastValue && 'string' == typeof value
-      ? this.lastValue != value : String(this.lastValue) != String(value));
-    if (changed) {
-      this.callback(this.element, value);
-      this.lastValue = value;
-    }
-  }
-}
-
-Form.Element.Observer = Class.create();
-Form.Element.Observer.prototype = Object.extend(new Abstract.TimedObserver(), {
-  getValue: function() {
-    return Form.Element.getValue(this.element);
-  }
-});
-
-Form.Observer = Class.create();
-Form.Observer.prototype = Object.extend(new Abstract.TimedObserver(), {
-  getValue: function() {
-    return Form.serialize(this.element);
-  }
-});
-
-/*--------------------------------------------------------------------------*/
-
-Abstract.EventObserver = function() {}
-Abstract.EventObserver.prototype = {
-  initialize: function(element, callback) {
-    this.element  = $(element);
-    this.callback = callback;
-
-    this.lastValue = this.getValue();
-    if (this.element.tagName.toLowerCase() == 'form')
-      this.registerFormCallbacks();
-    else
-      this.registerCallback(this.element);
-  },
-
-  onElementEvent: function() {
-    var value = this.getValue();
-    if (this.lastValue != value) {
-      this.callback(this.element, value);
-      this.lastValue = value;
-    }
-  },
-
-  registerFormCallbacks: function() {
-    Form.getElements(this.element).each(this.registerCallback.bind(this));
-  },
-
-  registerCallback: function(element) {
-    if (element.type) {
-      switch (element.type.toLowerCase()) {
-        case 'checkbox':
-        case 'radio':
-          Event.observe(element, 'click', this.onElementEvent.bind(this));
-          break;
-        default:
-          Event.observe(element, 'change', this.onElementEvent.bind(this));
-          break;
-      }
-    }
-  }
-}
-
-Form.Element.EventObserver = Class.create();
-Form.Element.EventObserver.prototype = Object.extend(new Abstract.EventObserver(), {
-  getValue: function() {
-    return Form.Element.getValue(this.element);
-  }
-});
-
-Form.EventObserver = Class.create();
-Form.EventObserver.prototype = Object.extend(new Abstract.EventObserver(), {
-  getValue: function() {
-    return Form.serialize(this.element);
-  }
-});
-if (!window.Event) {
-  var Event = new Object();
-}
-
-Object.extend(Event, {
-  KEY_BACKSPACE: 8,
-  KEY_TAB:       9,
-  KEY_RETURN:   13,
-  KEY_ESC:      27,
-  KEY_LEFT:     37,
-  KEY_UP:       38,
-  KEY_RIGHT:    39,
-  KEY_DOWN:     40,
-  KEY_DELETE:   46,
-  KEY_HOME:     36,
-  KEY_END:      35,
-  KEY_PAGEUP:   33,
-  KEY_PAGEDOWN: 34,
-
-  element: function(event) {
-    return event.target || event.srcElement;
-  },
-
-  isLeftClick: function(event) {
-    return (((event.which) && (event.which == 1)) ||
-            ((event.button) && (event.button == 1)));
-  },
-
-  pointerX: function(event) {
-    return event.pageX || (event.clientX +
-      (document.documentElement.scrollLeft || document.body.scrollLeft));
-  },
-
-  pointerY: function(event) {
-    return event.pageY || (event.clientY +
-      (document.documentElement.scrollTop || document.body.scrollTop));
-  },
-
-  stop: function(event) {
-    if (event.preventDefault) {
-      event.preventDefault();
-      event.stopPropagation();
-    } else {
-      event.returnValue = false;
-      event.cancelBubble = true;
-    }
-  },
-
-  // find the first node with the given tagName, starting from the
-  // node the event was triggered on; traverses the DOM upwards
-  findElement: function(event, tagName) {
-    var element = Event.element(event);
-    while (element.parentNode && (!element.tagName ||
-        (element.tagName.toUpperCase() != tagName.toUpperCase())))
-      element = element.parentNode;
-    return element;
-  },
-
-  observers: false,
-
-  _observeAndCache: function(element, name, observer, useCapture) {
-    if (!this.observers) this.observers = [];
-    if (element.addEventListener) {
-      this.observers.push([element, name, observer, useCapture]);
-      element.addEventListener(name, observer, useCapture);
-    } else if (element.attachEvent) {
-      this.observers.push([element, name, observer, useCapture]);
-      element.attachEvent('on' + name, observer);
-    }
-  },
-
-  unloadCache: function() {
-    if (!Event.observers) return;
-    for (var i = 0, length = Event.observers.length; i < length; i++) {
-      Event.stopObserving.apply(this, Event.observers[i]);
-      Event.observers[i][0] = null;
-    }
-    Event.observers = false;
-  },
-
-  observe: function(element, name, observer, useCapture) {
-    element = $(element);
-    useCapture = useCapture || false;
-
-    if (name == 'keypress' &&
-        (navigator.appVersion.match(/Konqueror|Safari|KHTML/)
-        || element.attachEvent))
-      name = 'keydown';
-
-    Event._observeAndCache(element, name, observer, useCapture);
-  },
-
-  stopObserving: function(element, name, observer, useCapture) {
-    element = $(element);
-    useCapture = useCapture || false;
-
-    if (name == 'keypress' &&
-        (navigator.appVersion.match(/Konqueror|Safari|KHTML/)
-        || element.detachEvent))
-      name = 'keydown';
-
-    if (element.removeEventListener) {
-      element.removeEventListener(name, observer, useCapture);
-    } else if (element.detachEvent) {
-      try {
-        element.detachEvent('on' + name, observer);
-      } catch (e) {}
-    }
-  }
-});
-
-/* prevent memory leaks in IE */
-if (navigator.appVersion.match(/\bMSIE\b/))
-  Event.observe(window, 'unload', Event.unloadCache, false);
-var Position = {
-  // set to true if needed, warning: firefox performance problems
-  // NOT neeeded for page scrolling, only if draggable contained in
-  // scrollable elements
-  includeScrollOffsets: false,
-
-  // must be called before calling withinIncludingScrolloffset, every time the
-  // page is scrolled
-  prepare: function() {
-    this.deltaX =  window.pageXOffset
-                || document.documentElement.scrollLeft
-                || document.body.scrollLeft
-                || 0;
-    this.deltaY =  window.pageYOffset
-                || document.documentElement.scrollTop
-                || document.body.scrollTop
-                || 0;
-  },
-
-  realOffset: function(element) {
-    var valueT = 0, valueL = 0;
-    do {
-      valueT += element.scrollTop  || 0;
-      valueL += element.scrollLeft || 0;
-      element = element.parentNode;
-    } while (element);
-    return [valueL, valueT];
-  },
-
-  cumulativeOffset: function(element) {
-    var valueT = 0, valueL = 0;
-    do {
-      valueT += element.offsetTop  || 0;
-      valueL += element.offsetLeft || 0;
-      element = element.offsetParent;
-    } while (element);
-    return [valueL, valueT];
-  },
-
-  positionedOffset: function(element) {
-    var valueT = 0, valueL = 0;
-    do {
-      valueT += element.offsetTop  || 0;
-      valueL += element.offsetLeft || 0;
-      element = element.offsetParent;
-      if (element) {
-        if(element.tagName=='BODY') break;
-        var p = Element.getStyle(element, 'position');
-        if (p == 'relative' || p == 'absolute') break;
-      }
-    } while (element);
-    return [valueL, valueT];
-  },
-
-  offsetParent: function(element) {
-    if (element.offsetParent) return element.offsetParent;
-    if (element == document.body) return element;
-
-    while ((element = element.parentNode) && element != document.body)
-      if (Element.getStyle(element, 'position') != 'static')
-        return element;
-
-    return document.body;
-  },
-
-  // caches x/y coordinate pair to use with overlap
-  within: function(element, x, y) {
-    if (this.includeScrollOffsets)
-      return this.withinIncludingScrolloffsets(element, x, y);
-    this.xcomp = x;
-    this.ycomp = y;
-    this.offset = this.cumulativeOffset(element);
-
-    return (y >= this.offset[1] &&
-            y <  this.offset[1] + element.offsetHeight &&
-            x >= this.offset[0] &&
-            x <  this.offset[0] + element.offsetWidth);
-  },
-
-  withinIncludingScrolloffsets: function(element, x, y) {
-    var offsetcache = this.realOffset(element);
-
-    this.xcomp = x + offsetcache[0] - this.deltaX;
-    this.ycomp = y + offsetcache[1] - this.deltaY;
-    this.offset = this.cumulativeOffset(element);
-
-    return (this.ycomp >= this.offset[1] &&
-            this.ycomp <  this.offset[1] + element.offsetHeight &&
-            this.xcomp >= this.offset[0] &&
-            this.xcomp <  this.offset[0] + element.offsetWidth);
-  },
-
-  // within must be called directly before
-  overlap: function(mode, element) {
-    if (!mode) return 0;
-    if (mode == 'vertical')
-      return ((this.offset[1] + element.offsetHeight) - this.ycomp) /
-        element.offsetHeight;
-    if (mode == 'horizontal')
-      return ((this.offset[0] + element.offsetWidth) - this.xcomp) /
-        element.offsetWidth;
-  },
-
-  page: function(forElement) {
-    var valueT = 0, valueL = 0;
-
-    var element = forElement;
-    do {
-      valueT += element.offsetTop  || 0;
-      valueL += element.offsetLeft || 0;
-
-      // Safari fix
-      if (element.offsetParent==document.body)
-        if (Element.getStyle(element,'position')=='absolute') break;
-
-    } while (element = element.offsetParent);
-
-    element = forElement;
-    do {
-      if (!window.opera || element.tagName=='BODY') {
-        valueT -= element.scrollTop  || 0;
-        valueL -= element.scrollLeft || 0;
-      }
-    } while (element = element.parentNode);
-
-    return [valueL, valueT];
-  },
-
-  clone: function(source, target) {
-    var options = Object.extend({
-      setLeft:    true,
-      setTop:     true,
-      setWidth:   true,
-      setHeight:  true,
-      offsetTop:  0,
-      offsetLeft: 0
-    }, arguments[2] || {})
-
-    // find page position of source
-    source = $(source);
-    var p = Position.page(source);
-
-    // find coordinate system to use
-    target = $(target);
-    var delta = [0, 0];
-    var parent = null;
-    // delta [0,0] will do fine with position: fixed elements,
-    // position:absolute needs offsetParent deltas
-    if (Element.getStyle(target,'position') == 'absolute') {
-      parent = Position.offsetParent(target);
-      delta = Position.page(parent);
-    }
-
-    // correct by body offsets (fixes Safari)
-    if (parent == document.body) {
-      delta[0] -= document.body.offsetLeft;
-      delta[1] -= document.body.offsetTop;
-    }
-
-    // set position
-    if(options.setLeft)   target.style.left  = (p[0] - delta[0] + options.offsetLeft) + 'px';
-    if(options.setTop)    target.style.top   = (p[1] - delta[1] + options.offsetTop) + 'px';
-    if(options.setWidth)  target.style.width = source.offsetWidth + 'px';
-    if(options.setHeight) target.style.height = source.offsetHeight + 'px';
-  },
-
-  absolutize: function(element) {
-    element = $(element);
-    if (element.style.position == 'absolute') return;
-    Position.prepare();
-
-    var offsets = Position.positionedOffset(element);
-    var top     = offsets[1];
-    var left    = offsets[0];
-    var width   = element.clientWidth;
-    var height  = element.clientHeight;
-
-    element._originalLeft   = left - parseFloat(element.style.left  || 0);
-    element._originalTop    = top  - parseFloat(element.style.top || 0);
-    element._originalWidth  = element.style.width;
-    element._originalHeight = element.style.height;
-
-    element.style.position = 'absolute';
-    element.style.top    = top + 'px';
-    element.style.left   = left + 'px';
-    element.style.width  = width + 'px';
-    element.style.height = height + 'px';
-  },
-
-  relativize: function(element) {
-    element = $(element);
-    if (element.style.position == 'relative') return;
-    Position.prepare();
-
-    element.style.position = 'relative';
-    var top  = parseFloat(element.style.top  || 0) - (element._originalTop || 0);
-    var left = parseFloat(element.style.left || 0) - (element._originalLeft || 0);
-
-    element.style.top    = top + 'px';
-    element.style.left   = left + 'px';
-    element.style.height = element._originalHeight;
-    element.style.width  = element._originalWidth;
-  }
-}
-
-// Safari returns margins on body which is incorrect if the child is absolutely
-// positioned.  For performance reasons, redefine Position.cumulativeOffset for
-// KHTML/WebKit only.
-if (/Konqueror|Safari|KHTML/.test(navigator.userAgent)) {
-  Position.cumulativeOffset = function(element) {
-    var valueT = 0, valueL = 0;
-    do {
-      valueT += element.offsetTop  || 0;
-      valueL += element.offsetLeft || 0;
-      if (element.offsetParent == document.body)
-        if (Element.getStyle(element, 'position') == 'absolute') break;
-
-      element = element.offsetParent;
-    } while (element);
-
-    return [valueL, valueT];
-  }
-}
-
-Element.addMethods();
-
 
 // ------------------------------------------------------------------------
 // ------------------------------------------------------------------------
@@ -3431,4 +933,3 @@ function renderScene(){
 
     raytracer.renderScene(scene, null, 0);
 }
-
diff --git a/benchmarks/revisions.html b/benchmarks/revisions.html
index bba53dc60..f94d20614 100644
--- a/benchmarks/revisions.html
+++ b/benchmarks/revisions.html
@@ -20,6 +20,20 @@ the benchmark suite.
 
 </p>
 
+<div class="subtitle"><h3>Version 4 (<a href="http://v8.googlecode.com/svn/data/benchmarks/v4/run.html">link</a>)</h3></div>
+
+<p>The <i>Splay</i> benchmark is a newcomer in version 4.  It
+manipulates a splay tree by adding and removing data nodes, thus
+exercising the memory management subsystem of the JavaScript engine.
+</p>
+
+<p>
+Furthermore, all the unused parts of the Prototype library were
+removed from the RayTrace benchmark. This does not affect the running
+of the benchmark.
+</p>
+
+
 <div class="subtitle"><h3>Version 3 (<a href="http://v8.googlecode.com/svn/data/benchmarks/v3/run.html">link</a>)</h3></div>
 
 <p>Version 3 adds a new benchmark, <i>RegExp</i>.  The RegExp
@@ -32,9 +46,10 @@ encoded using ROT13 in a way that does not affect how the regexps
 match their input.
 </p>
 
+
 <div class="subtitle"><h3>Version 2 (<a href="http://v8.googlecode.com/svn/data/benchmarks/v2/run.html">link</a>)</h3></div>
 
-<p>For version 2 the crypto benchmark was fixed.  Previously, the
+<p>For version 2 the Crypto benchmark was fixed.  Previously, the
 decryption stage was given plaintext as input, which resulted in an
 error.  Now, the decryption stage is given the output of the
 encryption stage as input.  The result is checked against the original
@@ -49,6 +64,7 @@ results of their calculations.  This is to avoid accidentally
 obtaining scores that are the result of an incorrect JavaScript engine
 optimization.</p>
 
+
 <div class="subtitle"><h3>Version 1 (<a href="http://v8.googlecode.com/svn/data/benchmarks/v1/run.html">link</a>)</h3></div>
 
 <p>Initial release.</p>
diff --git a/benchmarks/richards.js b/benchmarks/richards.js
index bb88623cd..c9368eff9 100644
--- a/benchmarks/richards.js
+++ b/benchmarks/richards.js
@@ -30,7 +30,7 @@
 // benchmark from:
 //
 //    http://www.cl.cam.ac.uk/~mr10/Bench.html
-// 
+//
 // The benchmark was originally implemented in BCPL by
 // Martin Richards.
 
diff --git a/benchmarks/run.html b/benchmarks/run.html
index 8663cf10e..6adb6d27a 100644
--- a/benchmarks/run.html
+++ b/benchmarks/run.html
@@ -8,6 +8,7 @@
 <script type="text/javascript" src="raytrace.js"></script>
 <script type="text/javascript" src="earley-boyer.js"></script>
 <script type="text/javascript" src="regexp.js"></script>
+<script type="text/javascript" src="splay.js"></script>
 <link type="text/css" rel="stylesheet" href="style.css"></link>
 <script type="text/javascript">
 var completed = 0;
@@ -72,12 +73,13 @@ higher scores means better performance: <em>Bigger is better!</em>
 <ul>
 <li><b>Richards</b><br/>OS kernel simulation benchmark, originally written in BCPL by Martin Richards (<i>539 lines</i>).</li>
 <li><b>DeltaBlue</b><br/>One-way constraint solver, originally written in Smalltalk by John Maloney and Mario Wolczko (<i>880 lines</i>).</li>
-<li><b>Crypto</b><br/>Encryption and decryption benchmark based on code by Tom Wu (<i>1689 lines</i>).</li>
-<li><b>RayTrace</b><br/>Ray tracer benchmark based on code by <a href="http://flog.co.nz/">Adam Burmister</a> (<i>3418 lines</i>).</li>
-<li><b>EarleyBoyer</b><br/>Classic Scheme benchmarks, translated to JavaScript by Florian Loitsch's Scheme2Js compiler (<i>4682 lines</i>).</li>
+<li><b>Crypto</b><br/>Encryption and decryption benchmark based on code by Tom Wu (<i>1698 lines</i>).</li>
+<li><b>RayTrace</b><br/>Ray tracer benchmark based on code by <a href="http://flog.co.nz/">Adam Burmister</a> (<i>935 lines</i>).</li>
+<li><b>EarleyBoyer</b><br/>Classic Scheme benchmarks, translated to JavaScript by Florian Loitsch's Scheme2Js compiler (<i>4685 lines</i>).</li>
 <li><b>RegExp</b><br/>Regular expression benchmark generated by extracting regular expression operations from 50 of the most popular web pages
-(<i>4758 lines</i>).
+(<i>1614 lines</i>).
 </li>
+<li><b>Splay</b><br/>Data manipulation benchmark that deals with splay trees and exercises the automatic memory management subsystem (<i>378 lines</i>).</li>
 </ul>
 
 <p>
@@ -90,7 +92,7 @@ the <a href="http://v8.googlecode.com/svn/data/benchmarks/current/revisions.html
 
 </td><td style="text-align: center">
 <div class="run">
-  <div id="status" style="text-align: center; margin-top: 60px; font-size: 120%; font-weight: bold;">Starting...</div>
+  <div id="status" style="text-align: center; margin-top: 50px; font-size: 120%; font-weight: bold;">Starting...</div>
   <div style="text-align: left; margin: 30px 0 0 90px;" id="results">
   <div>
 </div>
diff --git a/benchmarks/run.js b/benchmarks/run.js
index bdf1fb1ff..da95fb498 100644
--- a/benchmarks/run.js
+++ b/benchmarks/run.js
@@ -33,6 +33,7 @@ load('crypto.js');
 load('raytrace.js');
 load('earley-boyer.js');
 load('regexp.js');
+load('splay.js');
 
 var success = true;
 
diff --git a/benchmarks/splay.js b/benchmarks/splay.js
new file mode 100644
index 000000000..53fc72793
--- /dev/null
+++ b/benchmarks/splay.js
@@ -0,0 +1,378 @@
+// Copyright 2009 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// This benchmark is based on a JavaScript log processing module used
+// by the V8 profiler to generate execution time profiles for runs of
+// JavaScript applications, and it effectively measures how fast the
+// JavaScript engine is at allocating nodes and reclaiming the memory
+// used for old nodes. Because of the way splay trees work, the engine
+// also has to deal with a lot of changes to the large tree object
+// graph.
+
+var Splay = new BenchmarkSuite('Splay', 126125, [
+  new Benchmark("Splay", SplayRun, SplaySetup, SplayTearDown)
+]);
+
+
+// Configuration.
+var kSplayTreeSize = 8000;
+var kSplayTreeModifications = 80;
+var kSplayTreePayloadDepth = 5;
+
+var splayTree = null;
+
+
+function GeneratePayloadTree(depth, key) {
+  if (depth == 0) {
+    return {
+      array  : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
+      string : 'String for key ' + key + ' in leaf node'
+    };
+  } else {
+    return {
+      left:  GeneratePayloadTree(depth - 1, key),
+      right: GeneratePayloadTree(depth - 1, key)
+    };
+  }
+}
+
+
+function GenerateKey() {
+  // The benchmark framework guarantees that Math.random is
+  // deterministic; see base.js.
+  return Math.random();
+}
+
+
+function InsertNewNode() {
+  // Insert new node with a unique key.
+  var key;
+  do {
+    key = GenerateKey();
+  } while (splayTree.find(key) != null);
+  splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key));
+  return key;
+}
+
+
+
+function SplaySetup() {
+  splayTree = new SplayTree();
+  for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode();
+}
+
+
+function SplayTearDown() {
+  // Allow the garbage collector to reclaim the memory
+  // used by the splay tree no matter how we exit the
+  // tear down function.
+  var keys = splayTree.exportKeys();
+  splayTree = null;
+
+  // Verify that the splay tree has the right size.
+  var length = keys.length;
+  if (length != kSplayTreeSize) {
+    throw new Error("Splay tree has wrong size");
+  }
+
+  // Verify that the splay tree has sorted, unique keys.
+  for (var i = 0; i < length - 1; i++) {
+    if (keys[i] >= keys[i + 1]) {
+      throw new Error("Splay tree not sorted");
+    }
+  }
+}
+
+
+function SplayRun() {
+  // Replace a few nodes in the splay tree.
+  for (var i = 0; i < kSplayTreeModifications; i++) {
+    var key = InsertNewNode();
+    var greatest = splayTree.findGreatestLessThan(key);
+    if (greatest == null) splayTree.remove(key);
+    else splayTree.remove(greatest.key);
+  }
+}
+
+
+/**
+ * Constructs a Splay tree.  A splay tree is a self-balancing binary
+ * search tree with the additional property that recently accessed
+ * elements are quick to access again. It performs basic operations
+ * such as insertion, look-up and removal in O(log(n)) amortized time.
+ *
+ * @constructor
+ */
+function SplayTree() {
+};
+
+
+/**
+ * Pointer to the root node of the tree.
+ *
+ * @type {SplayTree.Node}
+ * @private
+ */
+SplayTree.prototype.root_ = null;
+
+
+/**
+ * @return {boolean} Whether the tree is empty.
+ */
+SplayTree.prototype.isEmpty = function() {
+  return !this.root_;
+};
+
+
+/**
+ * Inserts a node into the tree with the specified key and value if
+ * the tree does not already contain a node with the specified key. If
+ * the value is inserted, it becomes the root of the tree.
+ *
+ * @param {number} key Key to insert into the tree.
+ * @param {*} value Value to insert into the tree.
+ */
+SplayTree.prototype.insert = function(key, value) {
+  if (this.isEmpty()) {
+    this.root_ = new SplayTree.Node(key, value);
+    return;
+  }
+  // Splay on the key to move the last node on the search path for
+  // the key to the root of the tree.
+  this.splay_(key);
+  if (this.root_.key == key) {
+    return;
+  }
+  var node = new SplayTree.Node(key, value);
+  if (key > this.root_.key) {
+    node.left = this.root_;
+    node.right = this.root_.right;
+    this.root_.right = null;
+  } else {
+    node.right = this.root_;
+    node.left = this.root_.left;
+    this.root_.left = null;
+  }
+  this.root_ = node;
+};
+
+
+/**
+ * Removes a node with the specified key from the tree if the tree
+ * contains a node with this key. The removed node is returned. If the
+ * key is not found, an exception is thrown.
+ *
+ * @param {number} key Key to find and remove from the tree.
+ * @return {SplayTree.Node} The removed node.
+ */
+SplayTree.prototype.remove = function(key) {
+  if (this.isEmpty()) {
+    throw Error('Key not found: ' + key);
+  }
+  this.splay_(key);
+  if (this.root_.key != key) {
+    throw Error('Key not found: ' + key);
+  }
+  var removed = this.root_;
+  if (!this.root_.left) {
+    this.root_ = this.root_.right;
+  } else {
+    var right = this.root_.right;
+    this.root_ = this.root_.left;
+    // Splay to make sure that the new root has an empty right child.
+    this.splay_(key);
+    // Insert the original right child as the right child of the new
+    // root.
+    this.root_.right = right;
+  }
+  return removed;
+};
+
+
+/**
+ * Returns the node having the specified key or null if the tree doesn't contain
+ * a node with the specified key.
+ *
+ * @param {number} key Key to find in the tree.
+ * @return {SplayTree.Node} Node having the specified key.
+ */
+SplayTree.prototype.find = function(key) {
+  if (this.isEmpty()) {
+    return null;
+  }
+  this.splay_(key);
+  return this.root_.key == key ? this.root_ : null;
+};
+
+
+/**
+ * @return {SplayTree.Node} Node having the maximum key value that
+ *     is less or equal to the specified key value.
+ */
+SplayTree.prototype.findGreatestLessThan = function(key) {
+  if (this.isEmpty()) {
+    return null;
+  }
+  // Splay on the key to move the node with the given key or the last
+  // node on the search path to the top of the tree.
+  this.splay_(key);
+  // Now the result is either the root node or the greatest node in
+  // the left subtree.
+  if (this.root_.key <= key) {
+    return this.root_;
+  } else if (this.root_.left) {
+    return this.findMax(this.root_.left);
+  } else {
+    return null;
+  }
+};
+
+
+/**
+ * @return {Array<*>} An array containing all the keys of tree's nodes.
+ */
+SplayTree.prototype.exportKeys = function() {
+  var result = [];
+  if (!this.isEmpty()) {
+    this.root_.traverse_(function(node) { result.push(node.key); });
+  }
+  return result;
+};
+
+
+/**
+ * Perform the splay operation for the given key. Moves the node with
+ * the given key to the top of the tree.  If no node has the given
+ * key, the last node on the search path is moved to the top of the
+ * tree. This is the simplified top-down splaying algorithm from:
+ * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
+ *
+ * @param {number} key Key to splay the tree on.
+ * @private
+ */
+SplayTree.prototype.splay_ = function(key) {
+  if (this.isEmpty()) {
+    return;
+  }
+  // Create a dummy node.  The use of the dummy node is a bit
+  // counter-intuitive: The right child of the dummy node will hold
+  // the L tree of the algorithm.  The left child of the dummy node
+  // will hold the R tree of the algorithm.  Using a dummy node, left
+  // and right will always be nodes and we avoid special cases.
+  var dummy, left, right;
+  dummy = left = right = new SplayTree.Node(null, null);
+  var current = this.root_;
+  while (true) {
+    if (key < current.key) {
+      if (!current.left) {
+        break;
+      }
+      if (key < current.left.key) {
+        // Rotate right.
+        var tmp = current.left;
+        current.left = tmp.right;
+        tmp.right = current;
+        current = tmp;
+        if (!current.left) {
+          break;
+        }
+      }
+      // Link right.
+      right.left = current;
+      right = current;
+      current = current.left;
+    } else if (key > current.key) {
+      if (!current.right) {
+        break;
+      }
+      if (key > current.right.key) {
+        // Rotate left.
+        var tmp = current.right;
+        current.right = tmp.left;
+        tmp.left = current;
+        current = tmp;
+        if (!current.right) {
+          break;
+        }
+      }
+      // Link left.
+      left.right = current;
+      left = current;
+      current = current.right;
+    } else {
+      break;
+    }
+  }
+  // Assemble.
+  left.right = current.left;
+  right.left = current.right;
+  current.left = dummy.right;
+  current.right = dummy.left;
+  this.root_ = current;
+};
+
+
+/**
+ * Constructs a Splay tree node.
+ *
+ * @param {number} key Key.
+ * @param {*} value Value.
+ */
+SplayTree.Node = function(key, value) {
+  this.key = key;
+  this.value = value;
+};
+
+
+/**
+ * @type {SplayTree.Node}
+ */
+SplayTree.Node.prototype.left = null;
+
+
+/**
+ * @type {SplayTree.Node}
+ */
+SplayTree.Node.prototype.right = null;
+
+
+/**
+ * Performs an ordered traversal of the subtree starting at
+ * this SplayTree.Node.
+ *
+ * @param {function(SplayTree.Node)} f Visitor function.
+ * @private
+ */
+SplayTree.Node.prototype.traverse_ = function(f) {
+  var current = this;
+  while (current) {
+    var left = current.left;
+    if (left) left.traverse_(f);
+    f(current);
+    current = current.right;
+  }
+};