Implementing tree pattern matching

Writing down random thoughts as I have them.

Imagine rules with strategy name, order name, and apply name:


a downup down once
b downup up once
c downup up once
d downup up repeat

strategy has visit order and pattern application rule

default is


	strategy: downup, order={down, up}, apply={once,repeat}
	up, order=up, apply=repeat
	reverse, order={pre,post}, apply={once,repeat,rewriteSubtrees}

collect all rules with same strategy into rule


downup_down_once_patterns
	:	a
	;
downup_up_once_patterns
	:	b
	|	c
	;
downup_up_repeat
	:	d
	;

gen applyOnce() for each generated rule


	applyOnce_downup_down_once_patterns(t)
	applyOnce_downup_up_once_patterns(t)
	applyOnce_downup_up_repeat(t)

This creates node stream for t from existing buffer if possible and then
calls the pattern grouping rule. Easy if we don't do replaces. Replace on way up: we have to walk new tree. On way down, we also have to walk new tree.

We're rewriting tree, perhaps we should update node stream buffer as we go using a rewrite engine approach. Hmm...messes with node indexes.

Can we walk trees without creating buffer of entire tree? Perhaps we can make an on-demand buffer that doesn't go into subtrees unless the parser does. The wildcard would tell it to skip. Only problem is lookahead. Maybe we let LT(i) do the on-demand loading. We could add a skipOverSubtree() method to node stream so wildcard could avoid descending.

Patter ^( VAR . ID ) yields:


match(input,VAR,FOLLOW_VAR_in_a13); 
match(input, Token.DOWN, null); 
matchAny(input); 
match(input,ID,FOLLOW_ID_in_a17); 
match(input, Token.UP, null);

On-demand serialization of a tree in java (no continuations) would be a pain. Would have to maintain a stack. Might be better for deep tree anyway. skip in node stream would skip over DOWN...UP sequence or just one token if not DOWN.