Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We were discussing the porting effort involved with Jigsaw and how the surrogate log and fail stop exceptions on private property access made it easy to identify legacy code properties that needed to be marked public. PortMash and Caja were other two software examples cited for comparison with jigsaw. Unlike PortMash, jigsaw does not have to change asynchronous calls and unlike Caja jigsaw does not have to do object sanitization on boundary crossing. Jigsaw automatically wraps objects with a proxy in such cases. Moreover jigsaw enables pass by reference for all objects and this significantly reduces the marshaling otherwise. When large object trees have to be passed across isolation barriers, jigsaw creates surrogates lazily on first access to a sharing object. Initially only the root of the object tree gets a surrogate by this example.
In pass by value the entire object tree is recreated  that said, the surrogates introduce getters and setters that have more overhead than property access. However, this is acceptable because of three reasons:
First, this cost is only paid on access to external objects and not paid otherwise.
Second, jigsaw's initial sharing cost is a constant with respect to the size of the graph  thus is orders of magnitude better than pass by value. It is in fact very common to have large object graphs.
Third, jigsaw allows mashups to communicate synchronously with pass by reference as opposed to the asynchronous required in large object graph pass by value that may have significant latencies.
#codejam
In yesterday's post, we were solving a code jam problem
This involved a graph with N vertices and M edges where guards traverse from a source to destination node and we can obstruct upto K vertices. Each edge takes a unit time to traverse and each obstruction takes an additional unit time to clear. What is the minimum time for the guards to reach destination. ?
We discussed the solution. Today we look at a few steps 
First the breadth first traversal:
 Void bfs ()
{
  // initialize a list q for nodes to be visited and add the source 
// initialize a list for distances and set the first to be zero and all else unreachable.
While we have nodes to visit in q:
       Pick a node x and for each edge associated with x
         If distance has not been set and node y is not blocked :
             Add y to q;
             Distance of y = distance of x +1;
             Parent of y = x;
              
}
Void getTime ()
{
  bfs ();
  Int time = distance of destination node d [n-1]
  K--;
  While (k)
   {
        bfs ();
        If  d [n-1]  > time or n-1 is unreachable
           return time+2;
        Int z = n-1; 
        While  (z){
              If (Z!= n-1)
                  Blocked [z] = true;
              Z = parent of z;
         }
        K--;
   }
   bfs ();
   If  d [n-1]  > time or n-1 is unreachable
           return time+2;
   Return time +1;
}