-
Notifications
You must be signed in to change notification settings - Fork 42
JavaScript Tests Module
Hi there! The JS tests bit here is quite a big undertaking and will probably never be 100% reliable or 100% accurate (I would be incredibly surprised if it even got above 90%). Granted, it’s better than using Regexs to do this stuff, it’s much slower, uses a lot more memory, and leaves a bad taste in the mouth of anyone that believes in purity of JavaScript.
Installing Spidermonkey can be challenging depending on what platform you’re running. Fortunately, there’s a wiki page detailing installation instructions.
The last step (which isn’t bad at all) is to configure the validator to use the installation of Spidermonkey for its business. This is super easy.
If you used homebrew to install spidermonkey, you’re in luck! The validator should automatically detect the installation and pick it up right away. If it does, skip the rest of this step (you’re done). The shell should be at /usr/bin/js.
If you installed everything line-for-line like I have above, everything is already good. Your Mozilla code should all be in /moz/mozilla-central/. If it is, and you built it line-for-line like I showed you, you’re good as gold. The validator should automatically know where your Spidermonkey installation is. Pat yourself on the back and chalk it up to doing what you’re told.
If you decided to meander your own route through the installation, you’re going to want to learn where you put the binaries for Spidermonkey. In the commands that I listed above, the compiled code ended up in /moz/mozilla-central/js/src/build-release. The shell should be named js. Once you’ve located the shell, create a file called constants_local.py that looks like this in the /validator folder of your validator’s installation:
from validator.constants import *
SPIDERMONKEY_INSTALLATION = "/wherever/your/binary/is/js"If you want to take a less hands-on approach, you can also add the path to the shell to your $PATH. The validator will try to find an executable named js in all of the directories listed in $PATH, so simply setting that up will get you up and running as well, no manual configuration needed.
And that’s it!
The problem with AST trees is that the nodes are not homogenous. For instance, CallExpression nodes will contain more nodes in the “callee” and “arguments” properties, while MemberExpression nodes will contain more nodes in its “object” and “property” nodes.
This problem prevents simple recursion to iterate the tree. Because the nodes are also indicative of the scope of the objects being referred to, it is also difficult to accurately target the use of prohibited objects and functions. I’ll talk about that in a second.
The method for traversing the AST tree that the validator uses boils down the a giant dict in validator.testcases.javascript.nodedefinitions that lists each node type, the potential types of node branches, and some other information about the node type. Based on this, each node may be processed with a custom chunk of code as it is encountered and all code branches and control flows are visited.
In order to actually test the JS, determinations about the code that is being iterated over need to be made. In nodedefinitions, there is a value for each node type that identifies whether the object is block-level (so we can track variables created with let) and a value that identifies whether the object declares a scope. These values add a JSContext object to the top of the traverser’s context stack. When an assignment or declaration node is encountered, these contexts are populated.
Some elements, however, are not as simple to scan with this technique. Things like function declarations are especially tricky, where the declaration of the function, assignment of the function to the scope, and the content traversal happen in the same node. In order to handle this, there is a value available in nodedefinitions that allows a lambda function (or reference to a function in validator.testcases.javascript.actions) to run before the branches are executed. For this function, if there is a return value, execution of the branches is skipped. Simply returning True will skip the execution step.
Two arguments are passed to the aforementioned function. The first is a reference to the traverser object. This contains the error bundler (handy for reporting errors) and the AST node.
Lastly, there is a value in the nodedefinitions file for each node type that returns whether the node returns a value. Setting this to true will cause the _traverse_node function to return the value of the lambda function from above.
While visiting every node is indeed useful, it is not entirely practical to assume that all code is procedural. More importantly, complex structures and flow devices (such as loops and conditionals) will add a degree of uncertainty to the analysis. For instance, in this code block, an iterative approach will generate one value, though it will not be correct:
var x = 4;
if(x > 4) {
x += 3;
} else {
x /= 2;
}
// Interpreted answer: x = 2
// Iterative answer: x = 3.5
The problems here become immediately apparent. There are a number of solutions, however.
Particularly with regard to conditions, a clever solution is to “fork” the state of the engine: at a conditional or other n-ary control flow, deep copy the current scope and iterate one branch with one copy of the scope and the other branch with the other copy. At the end of the structure, some sort of reconstitution of the states will need to take place, or multiple-value static analysis will need to be implemented.
var x = 4;
if(x > 4) {
x += 3;
} else {
x /= 2;
}
// Interpreted answer: x = 2
// Fork 1 answer: x = 7
// Fork 2 answer: x = 2
// Reconstituted answer: x = 7|2
In this example, the answer may either be 7 or 2. All future analyses which involve x will need to test both values. This can get even more complicated in situations where multiple variables which may have multiple possible values. E.g.:
var x = 2;
if(foo())
x += 1;
else
x -= 1;
var y = 3;
if(bar())
y += 1;
else
y -= 1;
// x = 1|3;
// y = 2|4;
var z = x * y;
// z = 2|4|6|12
Ideally, however, a more simple reconstitution can take place:
var x = 4;
if(x > 4) {
x -= 4;
} else {
x *= 0;
}
// Interpreted answer: x = 0
// Fork 1 answer: x = 0
// Fork 2 answer: x = 0
// Reconstituted answer: x = 0
Not only is this answer correct, but it means that future analyses can be simplified.
If no else construct exists, the state should still be forked. After the conditional body has been evaluated, it should be reconstituted with the unchanged copy of the state. For example:
var x = 4;
if(x > 4) {
x -= 4;
}
// Interpreted answer: x = 4
// Fork answer: x = 0
// "Unchanged" answer: x = 4
// Reconstituted answer: x = 0|4
Loops are much more difficult to deal with using state forking. Because there is a chance that the state will change with each iteration (in an infinite loop), it is impossible to fully predict the outcome.
The best way to handle loops is to perform the state fork after each iteration of the loop. The state should then be saved. If an exact version of that state has already been saved by a previous iteration of the loop, iteration of the loop can end and the fork can terminate. At this point, resolution of all of the saved states should occur.
This approach is somewhat unpractical, however, because most loops will not ever resolve to a common state between iterations (leading to an infinite number of forks).
var x = 1;
var list = foo(); // Assumed to return an array
for(var e in list) {
x++;
}
// It is ambiguous where this loop should stop executing.
In this case, a more careful analysis of the loop should be made. If the changes between states in iterations of the loop are made to variables not read outside of the loop, their change should not be considered.
Until a better mechanism can be devised, the iteration should end after a fixed number of iterations. This number should be sufficiently high that the test it thorough but not too high that excessive resources are consumed.
Continues should cause the state to fork from within conditionals. One fork should process the loop as if the continue had taken place. The other fork should skip the rest of the conditional node and continue processing the loop. The fork should happen such that the “normal” fork (that behaves as the JS code would) still performs the normal state fork as if the end of the loop’s block had been reached. The other other (“abnormal”) fork should do the same, however, it should also continue processing the loop separately with the alternate state that it has developed. The abnormal fork should also deal with all reconstitution that must occur with the conditional that the continue was thrown in.
var x = foo();
var a = 3, b = 4;
for(var e in x) {
a++;
if(e == "bar")
continue;
// The abnormal fork must reconstitute with the alternate conditional fork here.
b *= 2;
// The normal fork will skip to here.
}
Breaks should be treated exactly as continues are treated.