[mkgmap-dev] [mkgmap-svn] Commit: r1488: RuleFileReader.optimiseAndSaveBinaryOp(): Try to be symmetric.

Mon Jan 18 12:47:10 GMT 2010

Hi Steve,

> There are lots more things that do not work, here are a few that I've
> just tried out:
> 
> 1. a~b        # doesn't work
> 2. a~b & c=d  # works
> 3. a~b & c~d & e=f    # doesn't work.
> 4. (a~b | c~d) & e=f  # works
> 5a (a~b | c~d) & e=f & g=h   # doesn't work
> 5b ((a~b | c~d) & e=f) & g=h # works!
> 6a e=f & g=h & (a~b | c~'d.*')    # works
> 6b (e=f & g=h) & (a~b | c~'d.*')  # doesn't work
but 6c would work, already before my patch:
(e=f | g=h) & (a~b | c~d)

> Just looking at first and second doesn't work at all in general.

We could get much further by shifting the "simplest" or "most selective"
operations (EQUALS, EXISTS) to the left branches of AndOp and OrOp trees.
Some simple left-recursivefying tree transformations should do the trick,
e.g., (a&b)&c would be transformed into A&(B&C) with some mapping between
a,b,c and A,B,C.  The A,B,C would be sorted by getType(), following the
order EQUALS < EXISTS < REGEX < NOT_EXISTS < ....

> Of course no-one uses anything that complex in their styles.

Right, it would probably be better to write simple rules than to figure out
what the parser did behind our backs.

That reminds me of the compiler course that I took in 1998.  I wrote a
compiler from a Pascal-like language to Digital Alpha assembler.  We
were given the code generator, in Java.  I implemented some expression
simplification (more than just constant folding).  I think it was mostly
about arithmetic operations, not logic.

	Marko