					2006 Nov 14 makoto onizuka

The implementation of Lazy DFA is very complicated, so
I summaried the complicated part of Lazy DFA to clarify
- What is the idea of the implementation?
- Why it became so complicated?
Basically, the complexity is caused by the combination
of SIX, predicate processing for attributes, and 
efficient transition implementations (sinkDepth, stayDepth),
although each idea is simle.


1. Lazy DFA implementation
Basically, Lazy DFA is implemented as the way written in
xpathDFA/http://www.cs.washington.edu/homes/suciu/paper-tods2004.pdf
but there are several notices.

1.1 startContext/endContext of matched attribute() SAX event
We treat attribute() rather complicated way.
From users views, i.e. from toolkit programs, attribute(atr) 
is treated as a sequence of startElement(@atr),endElement(@atr).
So, we have startContext();attribute();endContext() events
when a registered query matched by input XML stream.

However, in the automaton implementation, attribute() is 
implemented as a fake nested element, such as
<book year="1999">
  <name/>
</book>
is implemented as if
<book>
  <year="1999">    <!-- this expression does not follow XML1.0  -->
    <name/>
  </year>
</book>
The idea behind the automaton implementation is to process 
XPath queries with predicates of attributes. This idea 
is the same idea with XSQ's predicate processing.
One of the issues we have in this implementation is
the automaton transition of endElement whose element
has attributes. For example in the above case, when
we receive endElement(book), we need process not only 
endElement(book), but also endElement(fake attribute).
It is simple by itself, but working with the sinkDepth 
and stayDepth, the implementation became very complicated.

In addition, if we have no corrsponding edges for
an attribute() SAX event, we don't make any transition
in the automaton as if we just ignore the attribute
event.
Once an attribute() event matches with an edge, we make 
transition to the corresponding state. 
However, since, there is no order between attributes, 
we must transit to an another state corresponding 
to another matched attribute() event. 
So, we added @* edge for every state with attribute 
transition.


1.2 DFAState::sinkDepth, LazyDFAState::sinkDepth
sinkDepth is efficient implementation of sink state
to which we transit when we have no states specified
by XPath expressions.

1.3 DFAState::stayDepth, LazyDFAState::stayDepth
In the similar way to sinkDepth, we use stayDepth
which is a counter indicating the times we transit
to the same state as the current state.
We use stayDepth only for startElement (not for attribute)
SAX events, because we must distinguish whether the 
stacked edges are caused by element or attribute.
A same state can be pushed in the estack which is a stack
of edges that matches from the XML root node to the current
context node, so the LazyDFAState::stayDepth is copied to/from
StackItem::stayDepth when its edge is pushed/poped. 


2. application event emitter implementation
We design the application event emitter to output
symimetric sequence of application events.

For example, 
XPath expression: //title
XML document:
<bib>
  <book>
    <title>Data on the web</title>
    ...
  </book>
</bib>
we have the following application events.
startContext(//title)
startElement(title)
characters(Data on the web)
endElement(title)
endContext(//title)

The design is reasonable but, accompanied with SIX,
streaming index, it requires buffering endContext 
events. 
