Introduce DomWalker

DomWalker is a helper class/framework for writing rewriters that take the very typical form of walking a DOM tree and manipulating nodes as you go.

It supports multiple Visitors at the same time, reducing the need for multiple DOM walks depending on the semantics.

As of this CL the framework isn't used -- it sets up several follow-up CLs to come.

[zhoresh, 2010-02-18 19:23:44]

Looks promising. See some structural comments below.

http://codereview.appspot.com/214044/diff/1/3
File
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java
(right):

http://codereview.appspot.com/214044/diff/1/3#newcode53
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:53:
public interface Visitor {
This is the actual rewriter. Maybe a better name: DomNodeRewriter

http://codereview.appspot.com/214044/diff/1/3#newcode65
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:65:
* modify unreserved nodes. Other append and delete operations are acceptable
I am not sure I understand "do not modify unreserved node", is that imply MODIFY
will be returned only by revisit?

We might be also limiting ourself with the limitation of delete/move of one
visitor and only in revisit.
How would you implement optimization of joining multiple script blocks, and then
run them through closer compiler?

http://codereview.appspot.com/214044/diff/1/3#newcode103
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:103:
public static class Rewriter implements GadgetRewriter, RequestRewriter {
Instead of a sub class, merge it with DomWalker and rename it as
DomWalkerRewriter.

http://codereview.appspot.com/214044/diff/1/3#newcode120
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:120:
return ImmutableList.<Visitor>of();
Just return visitors, 
Let override class check for visitors existence if needed.

http://codereview.appspot.com/214044/diff/1/3#newcode128
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:128:
DomWalker.rewrite(visitors != null ? visitors :
Just call makeVisitors

http://codereview.appspot.com/214044/diff/1/3#newcode136
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:136:
return DomWalker.rewrite(visitors != null ? visitors :
Same as above

http://codereview.appspot.com/214044/diff/1/3#newcode143
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:143:
public static boolean rewrite(List<Visitor> visitors, Gadget gadget,
MutableContent content)
Why is that static? it make more sense to me to be a method of Rewriter

http://codereview.appspot.com/214044/diff/1/3#newcode145
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:145:
Map<Visitor, List<Node>> reservations = Maps.newHashMap();
Change to List< Pair<Node, Visitor>>
this way you promise revisiting order to be same as scan order.

http://codereview.appspot.com/214044/diff/1/3#newcode156
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:156:
for (int i = 0; !nodeReserved && !treeReserved && i < visitors.size(); ++i) {
visitors is a list, so use foreach loop:
for (Visitor visitor : visitors) {
  ...
  if (nodeReserved || treeReserved) break;
}

http://codereview.appspot.com/214044/diff/1/3#newcode187
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:187:
toVisit.add(child);
This implement BFS scan of the tree.
I think it would be better to do DFS which would be the same order of reading
the doc as text.
Use Stack (lifo) instead of queue.

[johnfargo, 2010-02-19 19:52:32]

Thanks for the review! Comments provided here. Patch coming in a moment.

http://codereview.appspot.com/214044/diff/1/3
File
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java
(right):

http://codereview.appspot.com/214044/diff/1/3#newcode53
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:53:
public interface Visitor {
My main goal is to distinguish between the top-level Rewriters we have (Gadget,
Request, Content [Gadget+Request], Image) and these sub-components. I chose
Visitor since this pattern is pretty typical for DOM operations and Visitor is
typical the name used. Any names you like that don't include "Rewriter"?

http://codereview.appspot.com/214044/diff/1/3#newcode65
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:65:
* modify unreserved nodes. Other append and delete operations are acceptable
On 2010/02/18 19:23:44, zhoresh wrote:
> I am not sure I understand "do not modify unreserved node", is that imply
MODIFY
> will be returned only by revisit?

No, it just means that revisit(...) only modifies nodes that are
reserved/revisited. In other words, nothing like this:

reservedNode.getNextSibling().getNextSibling().appendChild(...);

Added some commentary to this effect.

> 
> We might be also limiting ourself with the limitation of delete/move of one
> visitor and only in revisit.
> How would you implement optimization of joining multiple script blocks, and
then
> run them through closer compiler?

Separate rewriters. One joins, and the next compiles. They wouldn't be part of a
single DomWalker.Rewriter - this framework isn't meant to be comprehensive or to
replace the entire Rewriter mechanism, just to supply some helpers for common
operations.

http://codereview.appspot.com/214044/diff/1/3#newcode103
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:103:
public static class Rewriter implements GadgetRewriter, RequestRewriter {
Kept Rewriter as a subclass for now since DomWalker is intended as a namespace
(and renaming would lose comments for the benefit of a "." while adding
verbosity to Visitor decls).

http://codereview.appspot.com/214044/diff/1/3#newcode120
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:120:
return ImmutableList.<Visitor>of();
Good idea, done.

http://codereview.appspot.com/214044/diff/1/3#newcode128
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:128:
DomWalker.rewrite(visitors != null ? visitors :
On 2010/02/18 19:23:44, zhoresh wrote:
> Just call makeVisitors

Done.

http://codereview.appspot.com/214044/diff/1/3#newcode136
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:136:
return DomWalker.rewrite(visitors != null ? visitors :
On 2010/02/18 19:23:44, zhoresh wrote:
> Same as above

Done.

http://codereview.appspot.com/214044/diff/1/3#newcode143
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:143:
public static boolean rewrite(List<Visitor> visitors, Gadget gadget,
MutableContent content)
I was playing around with class structure for a while and made it static to
allow others to call directly. With the above changes to Rewriter, now made
private and non-static.

http://codereview.appspot.com/214044/diff/1/3#newcode145
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:145:
Map<Visitor, List<Node>> reservations = Maps.newHashMap();
Hm, interesting. Doing that would ensure that revisiting order is the same as
the first-reserved order, which seems a little arbitrary to me. I've changed the
code to revisit in visitors-order, which seems more useful. Thoughts?

On 2010/02/18 19:23:44, zhoresh wrote:
> Change to List< Pair<Node, Visitor>>
> this way you promise revisiting order to be same as scan order.
>

http://codereview.appspot.com/214044/diff/1/3#newcode156
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:156:
for (int i = 0; !nodeReserved && !treeReserved && i < visitors.size(); ++i) {
With slight modification, done.

On 2010/02/18 19:23:44, zhoresh wrote:
> visitors is a list, so use foreach loop:
> for (Visitor visitor : visitors) {
>   ...
>   if (nodeReserved || treeReserved) break;
> }

http://codereview.appspot.com/214044/diff/1/3#newcode187
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:187:
toVisit.add(child);
DFS sounds good, but Stack is generally frowned-upon since it extends the
similarly generally-frowned-upon Vector, for which all access is synchronized.

Ideally we'd use Deque, but we're still in Java 1.5-land. I've changed to a
direct LinkedList using addFirst and removeFirst methods.

[henry.saputra, 2010-02-19 19:55:06]

http://codereview.appspot.com/214044/diff/1/3
File
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java
(right):

http://codereview.appspot.com/214044/diff/1/3#newcode53
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:53:
public interface Visitor {
I think this is fine since John is using Visitor pattern to manipulate the DOM
elements. Maybe changing it to NodeVisitor would be better just in case we need
other kind of Visitor.

On 2010/02/18 19:23:44, zhoresh wrote:
> This is the actual rewriter. Maybe a better name: DomNodeRewriter

[johnfargo, 2010-02-19 20:06:00]

Accommodating current comments.

[zhoresh, 2010-02-19 23:26:39]

http://codereview.appspot.com/214044/diff/1/3
File
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java
(right):

http://codereview.appspot.com/214044/diff/1/3#newcode53
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:53:
public interface Visitor {
On 2010/02/19 19:55:06, henry.saputra wrote:
> I think this is fine since John is using Visitor pattern to manipulate the DOM
> elements. Maybe changing it to NodeVisitor would be better just in case we
need
> other kind of Visitor.
> 
> On 2010/02/18 19:23:44, zhoresh wrote:
> > This is the actual rewriter. Maybe a better name: DomNodeRewriter
> 
> 

Fine by me.

http://codereview.appspot.com/214044/diff/1/3#newcode145
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:145:
Map<Visitor, List<Node>> reservations = Maps.newHashMap();
On 2010/02/19 19:52:32, johnfargo wrote:
> Hm, interesting. Doing that would ensure that revisiting order is the same as
> the first-reserved order, which seems a little arbitrary to me. I've changed
the
> code to revisit in visitors-order, which seems more useful. Thoughts?
> 
> On 2010/02/18 19:23:44, zhoresh wrote:
> > Change to List< Pair<Node, Visitor>>
> > this way you promise revisiting order to be same as scan order.
> > 

I guess my question here is why revisit is done on list of nodes and not just
one like visit?
I am not sure I see the advantage, and maybe do revisit on a node might simplify
things.

[johnfargo, 2010-02-20 03:59:02]

On Fri, Feb 19, 2010 at 3:26 PM, <zhoresh@gmail.com> wrote:

>
> http://codereview.appspot.com/214044/diff/1/3
> File
>
> java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java
> (right):
>
> http://codereview.appspot.com/214044/diff/1/3#newcode53
>
>
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:53:
> public interface Visitor {
> On 2010/02/19 19:55:06, henry.saputra wrote:
>
>> I think this is fine since John is using Visitor pattern to manipulate
>>
> the DOM
>
>> elements. Maybe changing it to NodeVisitor would be better just in
>>
> case we need
>
>> other kind of Visitor.
>>
>
>  On 2010/02/18 19:23:44, zhoresh wrote:
>> > This is the actual rewriter. Maybe a better name: DomNodeRewriter
>>
>
>
>
> Fine by me.
>
>
> http://codereview.appspot.com/214044/diff/1/3#newcode145
>
>
java/gadgets/src/main/java/org/apache/shindig/gadgets/rewrite/DomWalker.java:145:
> Map<Visitor, List<Node>> reservations = Maps.newHashMap();
> On 2010/02/19 19:52:32, johnfargo wrote:
>
>> Hm, interesting. Doing that would ensure that revisiting order is the
>>
> same as
>
>> the first-reserved order, which seems a little arbitrary to me. I've
>>
> changed the
>
>> code to revisit in visitors-order, which seems more useful. Thoughts?
>>
>
>  On 2010/02/18 19:23:44, zhoresh wrote:
>> > Change to List< Pair<Node, Visitor>>
>> > this way you promise revisiting order to be same as scan order.
>> >
>>
>
> I guess my question here is why revisit is done on list of nodes and not
> just one like visit?
> I am not sure I see the advantage, and maybe do revisit on a node might
> simplify things.


The follow-up CLs would make this a lot more clear :)

To give an example, consider the concatenation operation. In this paradigm,
it's implemented by visit(...) reserving all nodes whose previous or next
sibling is a same-typed external reference. When revisit(...)ing, it's the
job of the Visitor to take *all* the reserved nodes at once and push them
together. If revisit(...) simply used a single node (which was the original
impl), then the Visitor would have to remember all the nodes it reserved and
only perform a modification action when it gets to the last one, and at that
it would have to maintain its own list of reserved nodes. Changing to
List<Node>, though somewhat odd, easily fixed that.


>
>
> http://codereview.appspot.com/214044/show
>