How do I track variable dependencies in Nashorn?

Question

I would like to use the Nashorn engine as a general computation engine. It is powerful, fast has plenty of built-in functions and new functions are very easy to add, using @FunctionalInterface or static methods. Even better, it also provides value-adds like cyclic dependency checking, syntax checking, etc.

However I need to automatically update "output" variables when a dependency changes.

The general idea is that in Java, I'll have something like:

class CalculationEngine {
   Data addData(String name, Number value){
       ...
   }
   Data addData(String name, String formula){
       ...
   }
   String getScript(){
       ...
   }
}

CalculationEngine engine = new CalculationEngine();
Data datum1 = engine.addData("datum1", 1); // Constant integer 1
Data datum2 = engine.addData("datum2", 2); // Constant integer 2
Data datum3 = engine.addData("datum3", "datum1*10");
Data datum4 = engine.addData("datum4", "datum3+datum2");

The CalculationEngine service class knows how to use Nashorn to create a script string out of the Data objects that looks like this:

final String script = engine.getScript(); // "var datum1=1; var datum2=2; var datum3=datum1*10; var datum4=datum3+datum2;"

I know I can parse the script with the Nashorn Parser:

final CompilationUnitTree tree = parser.parse("test", script, null);

But how do I extract the dependencies:

List<Data> whatDependsOn(Data input){
   // Process the parsed tree 
   return list;
}

such that whatDependsOn(datum2) returns [datum4] and whatDependsOn(datum1) returns [datum3, datum4] ?

Or the inverse function getReferencedVariables such that getReferencedVariables(datum3) returns [datum1] and getReferencedVariables(datum4) returns [datum2, datum3] (and I can recursively query getReferencedVariables until all referenced variables have been found).

Basically, when the "value" of one of my Data objects change (due to an external event), how I determine which of my script formulae are affected and need to be recomputed?

I know that the Nashorn script can be parsed but I can not figure out how to use the SimpleTreeVisitorES6 to build up a variable dependency graph:

    final CompilationUnitTree tree = parser.parse("test", script, null);

    if (tree != null) {
        tree.accept(new SimpleTreeVisitorES6<Void, Void>() {
            @Override
            public Void visitVariable(VariableTree tree, Void v) {
                final Kind kind = tree.getKind();
                System.out.println("Found a variable: " + kind);
                System.out.println(" name: " + kind.toString());
                IdentifierTree binding = (IdentifierTree) tree.getBinding();
                System.out.println(" kind: " + binding.getKind().name());
                System.out.println(" name: " + binding.getName());
                System.out.println(" val: " + kind.name());

                return null;
            }
         }, null);
    }  

Answer 1

one of Nashorn devs here. What you are trying to do is compute the so called def-use relations on source code (well, more likely their transitive closure, but I digress). That's a well-understood compiler theory concept. The good news is that CompilationUnitTree and friends should give you enough information to implement an algorithm for computing this information. The bad news is you'll have to roll up your sleeves and roll your own implementation, I'm afraid. You'll basically have to gather this information, produce merges at control flow join points (back edges and exits of loops, ends of if statements, but you'll also have to handle more exotic stuff like switch/case with their fallthrough semantics and also try/catch/finally, which is the least fun of these as basically control can transfer from anywhere in try block to a catch block.) Your algorithm will also have to repeatedly evaluate loop bodies until the static information you're gathering reaches a fixpoint.

FWIW, while writing Nashorn I had to implement these kinds of things few times using Nashorn's internal parser API (which is different but similar to the public one). If you want some inspiration, you can look into the source code for Nashorn static type analyzer for inferring types of local variables in a JavaScript function which is something I wrote some years ago. If nothing else, it'll give you an idea how to walk an AST tree and keep track of control flow edges and partially computed static analysis data at the edges.

I wish there were an easier way to do this… FWIW, a generalized static analyzer that helps you with bookeeping of flow control could be possible. Good luck.