Hi Marko
I produced the attached patch which makes all the previous examples
compile (apart from the plain a~b example).
..Steve
Index: src/uk/me/parabola/mkgmap/osmstyle/RuleFileReader.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/RuleFileReader.java (revision 1490)
+++ src/uk/me/parabola/mkgmap/osmstyle/RuleFileReader.java Mon Jan 18
16:19:11 GMT 2010
@@ -25,22 +25,18 @@
import uk.me.parabola.mkgmap.general.LevelInfo;
import uk.me.parabola.mkgmap.osmstyle.actions.Action;
import uk.me.parabola.mkgmap.osmstyle.actions.ActionReader;
+import uk.me.parabola.mkgmap.osmstyle.eval.AndOp;
import uk.me.parabola.mkgmap.osmstyle.eval.BinaryOp;
import uk.me.parabola.mkgmap.osmstyle.eval.ExpressionReader;
import uk.me.parabola.mkgmap.osmstyle.eval.Op;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.AND;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.EQUALS;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.EXISTS;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.NOT_EXISTS;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.OR;
-import static uk.me.parabola.mkgmap.osmstyle.eval.Op.VALUE;
-import uk.me.parabola.mkgmap.osmstyle.eval.SyntaxException;
-import uk.me.parabola.mkgmap.osmstyle.eval.AndOp;
import uk.me.parabola.mkgmap.osmstyle.eval.OrOp;
+import uk.me.parabola.mkgmap.osmstyle.eval.SyntaxException;
import uk.me.parabola.mkgmap.reader.osm.GType;
import uk.me.parabola.mkgmap.reader.osm.Rule;
import uk.me.parabola.mkgmap.scan.TokenScanner;
+import static uk.me.parabola.mkgmap.osmstyle.eval.Op.*;
+
/**
* Read a rules file. A rules file contains a list of rules and the
* resulting garmin type, should the rule match.
@@ -115,54 +111,139 @@
private void saveRule(Op op, List<Action> actions, GType gt) {
log.info("EXP", op, ", type=", gt);
- // E1 | E2 {type...} is exactly the same as the two rules:
- // E1 {type...}
- // E2 {type...}
- // so just recurse on each term, throwing away the original OR.
- if (op.isType(OR)) {
- saveRule(op.getFirst(), actions, gt);
- saveRule(((BinaryOp) op).getSecond(), actions, gt);
- return;
- }
+ //System.out.println("From: " + op);
+ Op op2 = rearrangeExpression(op);
+ //System.out.println("RE: " + op2);
- if (op instanceof BinaryOp) {
- optimiseAndSaveBinaryOp((BinaryOp) op, actions, gt);
+ if (op2 instanceof BinaryOp) {
+ optimiseAndSaveBinaryOp((BinaryOp) op2, actions, gt);
} else {
- optimiseAndSaveOtherOp(op, actions, gt);
- //throw new SyntaxException(scanner, "Invalid operation
'" + op.getType() + "' at top level");
+ optimiseAndSaveOtherOp(op2, actions, gt);
}
}
- private void optimiseAndSaveOtherOp(Op op, List<Action> actions, GType
gt) {
- if (op.isType(EXISTS)) {
- createAndSaveRule(op.value() + "=*", null, actions, gt);
+ /**
+ * Rearrange the expression so that it is solvable, that is it starts
with
+ * an EQUALS or an EXISTS.
+ * @param op The expression to be rearranged.
+ * @return An equivelent expression re-arranged so that it starts with
an
+ * indexable term. If that is not possible then the original expression
is
+ * returned.
+ */
+ private Op rearrangeExpression(Op op) {
+ if (isFinished(op))
+ return op;
+
+ if (op.isType(AND)) {
+ // If the first term is and EQUALS or EXISTS then this
subtree is
+ // already solved and we need to do no more.
+ Op op1 = rearrangeExpression(op.getFirst());
+ Op op2 = rearrangeExpression(((BinaryOp)
op).getSecond());
+
+ if (isSolved(op1)) {
+ return rearrangeAnd((BinaryOp) op, op1, op2);
+ } else if (isSolved(op2)) {
+ return rearrangeAnd((BinaryOp) op, op2, op1);
+ }
+ }
+
+ return op;
+ }
+
+ /**
+ * Rearrange an AND expression so that it can be executed with indexable
+ * terms at the front.
+ * @param top This will be an AndOp.
+ * @param op1 This is a child of top that is guaranteed to be
+ * solved already.
+ * @param op2 This expression is the other child of top.
+ * @return A re-arranged expression with an indexable term at the
beginning
+ * or several such expressions ORed together.
+ */
+ private Op rearrangeAnd(BinaryOp top, Op op1, Op op2) {
+ if (isIndexable(op1)) {
+ top.setFirst(op1);
+ top.setSecond(op2);
+ return top;
+ } else if (op1.isType(AND)) {
+ // If the first term is AND and its first is EQUALS or
EXIST,
+ // then make that our first term.
+ Op first = op1.getFirst();
+ if (isIndexable(first)) {
+ top.setFirst(first);
+ op1.setFirst(op2);
+ top.setSecond(op1);
+ return top;
- } else {
+ } else {
- throw new SyntaxException(scanner, "Invalid operation
'" + op.getType() + "' at top level");
+ assert false;
- }
+ }
+ } else if (op1.isType(OR)) {
+ Op first = op1.getFirst();
+ OrOp orOp = new OrOp();
+
+ Op topSecond = top.getSecond();
+
+ AndOp and1 = new AndOp();
+ and1.setFirst(first);
+ and1.setSecond(topSecond);
+
+ AndOp and2 = new AndOp();
+ Op second = rearrangeExpression(((BinaryOp)
op1).getSecond());
+ and2.setFirst(second);
+ and2.setSecond(topSecond);
+
+ orOp.setFirst(and1);
+ orOp.setSecond(and2);
+ return orOp;
+ } else {
+ // This shouldn't happen
+ throw new SyntaxException("X3" + op1.getType());
- }
+ }
+ return top;
+ }
/**
- * Translate (a=b|a=c) & d~f
- * into (a=b&d~f) | (a=c&d~f)
- * @param first an OrOp that is the operand of an AndOp
- * @param second the other operand of the AndOp
- * @param actions list of actions to execute on match
- * @param gt the Garmin type of the element
+ * True if this operation can be indexed. It is a plain equality or
+ * Exists operation.
*/
- private void optimiseAndSaveAndOr(OrOp first, Op second, List<Action>
actions, GType gt) {
- // (a=b|a=c) & d~f => (a=b&d~f) | (a=c&d~f) => solved
- BinaryOp and1 = new AndOp();
- and1.setFirst(first.getFirst());
- and1.setSecond(second);
- optimiseAndSaveBinaryOp(and1, actions, gt);
+ private boolean isIndexable(Op op) {
+ return op.isType(EQUALS) || op.isType(EXISTS);
+ }
- BinaryOp and2 = new AndOp();
- and2.setFirst(first.getSecond());
- and2.setSecond(second);
- optimiseAndSaveBinaryOp(and2, actions, gt);
+ /**
+ * True if this expression is 'solved'. This means that the first term
+ * is indexable or it is indexable itself.
+ */
+ private boolean isSolved(Op op) {
+ return isIndexable(op) || isIndexable(op.getFirst());
}
/**
+ * True if there is nothing more that we can do to rearrange this
expression.
+ * It is either solved or it cannot be solved.
+ */
+ private boolean isFinished(Op op) {
+ if (isSolved(op))
+ return true;
+ char type = op.getType();
+ switch (type) {
+ case AND:
+ case OR: // possibly not required
+ return false;
+ default:
+ return true;
+ }
+ }
+
+ private void optimiseAndSaveOtherOp(Op op, List<Action> actions, GType
gt) {
+ if (op.isType(EXISTS)) {
+ createAndSaveRule(op.value() + "=*", null, actions, gt);
+ } else {
+ throw new SyntaxException(scanner, "Invalid operation
'" + op.getType() + "' at top level");
+ }
+ }
+
+ /**
* Optimise the expression tree, extract the primary key and
* save it as a rule.
* @param op a binary expression
@@ -195,27 +276,20 @@
if (first.isType(EQUALS)) {
keystring = first.toString();
expr = second;
- } else if (second.isType(EQUALS)) {
- // Swap the terms and everything will be fine.
- keystring = second.toString();
- expr = first;
+
} else if (first.isType(EXISTS)) {
keystring = first.value() + "=*";
expr = second;
- } else if (second.isType(EXISTS)) {
- keystring = second.value() + "=*";
- expr = first;
- } else if (first.isType(OR)) {
- optimiseAndSaveAndOr((OrOp) first, second,
actions, gt);
- return;
- } else if (second.isType(OR)) {
- optimiseAndSaveAndOr((OrOp) second, first,
actions, gt);
- return;
+
} else if (first.isType(NOT_EXISTS)) {
throw new SyntaxException(scanner, "Cannot
start rule with tag!=*");
} else {
throw new SyntaxException(scanner, "Invalid
rule file (expr " + op.getType() +')');
}
+ } else if (op.isType(OR)) {
+ saveRule(first, actions, gt);
+ saveRule(second, actions, gt);
+ return;
} else {
throw new SyntaxException(scanner, "Invalid operation
'" + op.getType() + "' at top level");
}
Index: test/uk/me/parabola/mkgmap/osmstyle/RuleFileReaderTest.java
===================================================================
--- test/uk/me/parabola/mkgmap/osmstyle/RuleFileReaderTest.java (revision 1159)
+++ test/uk/me/parabola/mkgmap/osmstyle/RuleFileReaderTest.java Mon Jan 18
16:19:11 GMT 2010
@@ -26,10 +26,11 @@
import uk.me.parabola.mkgmap.reader.osm.Rule;
import uk.me.parabola.mkgmap.reader.osm.Way;
-import static org.junit.Assert.*;
import org.junit.Test;
+import static org.junit.Assert.*;
+
public class RuleFileReaderTest {
/**
* Test of a file containing a number of different rules, with varying
@@ -58,9 +59,10 @@
assertEquals("rough footway", "[0x2 level 2]", type.toString());
el.addTag("oneway", "true");
- rule = ruleMap.get("oneway=true");
+ el.addTag("highway", "primary");
+ rule = ruleMap.get("highway=*");
type = rule.resolveType(el);
- assertEquals("oneway footway", "[0x6 level 1]",
type.toString());
+ assertEquals("oneway primary", "[0x6 level 1]",
type.toString());
}
/**
@@ -391,6 +393,32 @@
}
/**
+ * The main point of this test is to ensure that all the examples
compile.
+ */
+ @Test
+ public void testComplexRegex() {
+ RuleSet rs = makeRuleSet(
+ //"a~b [0x0] # doesn't work\n" +
+ "a~b & c=d [0x1]# works\n" +
+ "a~b & c~d & e=f [0x2] # doesn't work.\n" +
+ "(a~b | c~d) & e=f [0x3]# works\n" +
+ "(a~b | c~d) & e=f & g=h [0x4] # doesn't
work\n" +
+ "((a~b | c~d) & e=f) & g=h [0x5]# works!\n" +
+ "e=f & g=h & (a~b | c~'d.*') [0x6] # works\n"
+
+ "(e=f & g=h) & (a~b | c~'d.*') [0x7]# doesn't
work" +
+ ""
+ );
+
+ Way el = new Way(1);
+ el.addTag("c", "df");
+ el.addTag("g", "h");
+ el.addTag("e", "f");
+
+ GType type = rs.resolveType(el);
+ assertNotNull("matches a rule", type);
+ }
+
+ /**
* Create a rule set out of a string. The string is processed
* as if it were in a file and the levels spec had been set.
*/
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
