Revision: 3859
Author: jasvir
Date: Sat Nov 21 17:43:39 2009
Log: Created wiki page through web user interface.
http://code.google.com/p/google-caja/source/detail?r=3859
Added:
/wiki/SourcesOfNonDeterminism.wiki
=======================================
--- /dev/null
+++ /wiki/SourcesOfNonDeterminism.wiki Sat Nov 21 17:43:39 2009
@@ -0,0 +1,30 @@
+#summary Document the sources of non-determinism in Javascript.
+#labels Phase-Design
+
+= Introduction =
+
+Almost all members of the global environment of a [Cajita] program are
immutable. The two exceptions are `new Date()` and `Math.random` which
give an otherwise isolated cajoled [Cajita] program ambient access to a
covert channel of communication. Further, the output of a call to a
function which has access to either `Date` or `Math` is not a deterministic
function of the messages it receives.
+
+A _deterministic object-capability system_ is one in which the ability to
cause side-effects and observe data that varies between executions is
conveyed by explicit object references that are propogated only by explicit
program statements.
+
+Once access to the `Date` constructor and to `Math.random()` is removed
from [Cajita], all objects that are globally or implicitly accessible to
[Cajita] programs are immutable. This is not sufficient to make [Cajita]
into a deterministic object-capability system because of other sources of
non-determinism which Cajita inherits from Javascript.
+
+== Sources of Non-Determinism in JavaScript ==
+
+ * Enumeration order of `for..in` loops
+ * Semantics of modifying a list that is being iterated over
+ * Stability of `Array.sort` on already sorted list of objects
+ * `Array.sort` of lists where the `valueOf` of elements in the array is
not constant
+ * `Array.sort(comparator)` where `comparator` does not consistently
compare values
+ * Order of callbacks queued using `setTimeout`
+ * Some information about running time of a piece of code inferable from
`setTimeout`
+
+== Sources of Non-determinism in Tamed Libraries ==
+
+When taming libraries, the author of taming must be careful that the tamed
code does not accidentally violate the security properties of the cajoled
program using it. Determinism is a particularly easy property to violate
in taming.
+
+== Sources of Non-determinism in Domita ==
+
+ * Fetching an external resource identified by a URL is not deterministic
+ * This can be addressed using a url policy which caches agressively
+ * Parse tree generated by setting `innerHTML` varies depending on the
browser
