Skip to content

Instantly share code, notes, and snippets.

@bittercoder
Created September 15, 2011 12:04
Show Gist options
  • Save bittercoder/1219079 to your computer and use it in GitHub Desktop.
Save bittercoder/1219079 to your computer and use it in GitHub Desktop.
My first stab at a DeMorgans visitor + tests
// ---------------------------------------------------------------
// Uses DeMorgans Law of formal logic to remove NOT's from the AST
// (This is advantageous when running queries against Lucene)
// http://en.wikipedia.org/wiki/De_Morgans_laws
// ---------------------------------------------------------------
public class DeMorgansExprVisitor : IExprVisitor<Expr>
{
int _notCount;
bool Negate
{
get { return (_notCount%2) == 1; }
}
public Expr Visit(AndExpr expr)
{
Expr lhs = expr.LHS.Accept(this);
Expr rhs = expr.RHS.Accept(this);
return Negate ? (Expr) new OrExpr(lhs, rhs) : new AndExpr(lhs, rhs);
}
public Expr Visit(OrExpr expr)
{
Expr lhs = expr.LHS.Accept(this);
Expr rhs = expr.RHS.Accept(this);
return Negate ? (Expr) new AndExpr(lhs, rhs) : new OrExpr(lhs, rhs);
}
public Expr Visit(NotExpr expr)
{
try
{
_notCount++;
return expr.Expression.Accept(this);
}
finally
{
_notCount--;
}
}
public Expr Visit(Group expr)
{
return expr.Expression.Accept(this);
}
public Expr Visit(TerminalExpr expr)
{
return Negate ? new TerminalExpr(expr.Identifier, GetInverseOfOperator(expr.Operator), expr.Operand) : expr;
}
public Expr Visit(Empty expr)
{
return expr;
}
static Operator GetInverseOfOperator(Operator op)
{
switch (op)
{
case Operator.Is:
return Operator.IsNot;
case Operator.IsNot:
return Operator.Is;
case Operator.In:
return Operator.NotIn;
case Operator.NotIn:
return Operator.In;
case Operator.Contains:
return Operator.DoesNotContain;
case Operator.DoesNotContain:
return Operator.Contains;
case Operator.Eq:
return Operator.NotEq;
case Operator.NotEq:
return Operator.Eq;
case Operator.Gt:
return Operator.Lte;
case Operator.Gte:
return Operator.Lt;
case Operator.Lt:
return Operator.Gte;
case Operator.Lte:
return Operator.Gt;
default:
throw new Exception("Unexpected operator: " + op);
}
}
}
public class DeMorgansVisitorTests
{
readonly DeMorgansExprVisitor visitor = new DeMorgansExprVisitor();
[Fact]
public void no_nots_retains_same_structure()
{
TerminalExpr a = TerminalExpr.Eq("t1", "v1");
TerminalExpr b = TerminalExpr.Lt("t2", "v2");
TerminalExpr c = TerminalExpr.Gte("t3", "v3");
TerminalExpr d = TerminalExpr.Contains("t4", "v4");
var original = new AndExpr(new OrExpr(a, b), new OrExpr(c, d));
Assert.Equal(original, original.Accept(visitor));
}
[Theory]
[InlineData(Operator.Eq, Operator.NotEq)]
[InlineData(Operator.NotEq, Operator.Eq)]
[InlineData(Operator.Gt, Operator.Lte)]
[InlineData(Operator.Gte, Operator.Lt)]
[InlineData(Operator.Lt, Operator.Gte)]
[InlineData(Operator.Lte, Operator.Gt)]
[InlineData(Operator.Contains, Operator.DoesNotContain)]
[InlineData(Operator.DoesNotContain, Operator.Contains)]
[InlineData(Operator.Is, Operator.IsNot)]
[InlineData(Operator.IsNot, Operator.Is)]
[InlineData(Operator.In, Operator.NotIn)]
[InlineData(Operator.NotIn, Operator.In)]
public void not_single_value_with_operator_translated_to_expected_operator(Operator originalOp, Operator expectedOp)
{
var input = new NotExpr(new TerminalExpr("t", originalOp, new Value(new QuotedValue("v"))));
var expected = new TerminalExpr("t", expectedOp, new Value(new QuotedValue("v")));
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void not_and_becomes_or()
{
var input = new NotExpr(new AndExpr(TerminalExpr.Eq("t1", "v1"), TerminalExpr.Eq("t2", "v2")));
var expected = new OrExpr(TerminalExpr.NotEq("t1", "v1"), TerminalExpr.NotEq("t2", "v2"));
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void not_or_becomes_and()
{
var input = new NotExpr(new OrExpr(TerminalExpr.Eq("t1", "v1"), TerminalExpr.Eq("t2", "v2")));
var expected = new AndExpr(TerminalExpr.NotEq("t1", "v1"), TerminalExpr.NotEq("t2", "v2"));
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void not_within_a_not_is_just_the_term()
{
var input = new NotExpr(new NotExpr(TerminalExpr.Eq("t", "v")));
TerminalExpr expected = TerminalExpr.Eq("t", "v");
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void not_within_not_within_not_behaves_like_single_not()
{
var input = new NotExpr(new NotExpr(new NotExpr(TerminalExpr.Contains("t", "v"))));
TerminalExpr expected = TerminalExpr.DoesNotContain("t", "v");
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void two_levels_of_not_returns_expected()
{
TerminalExpr t1 = TerminalExpr.Contains("t", "v");
TerminalExpr t2 = TerminalExpr.Lt("t1", "v1");
var notAnd = new NotExpr(new AndExpr(t1, t2));
TerminalExpr t3 = TerminalExpr.Gte("t", "v");
TerminalExpr t4 = TerminalExpr.Eq("t1", "v1");
var notOr = new NotExpr(new OrExpr(t3, t4));
var input = new NotExpr(new AndExpr(notOr, notAnd));
var expAnd = new AndExpr(t1, t2);
var expOr = new OrExpr(t3, t4);
var expected = new OrExpr(expOr, expAnd);
Assert.Equal(expected, input.Accept(visitor));
}
[Fact]
public void not_two_levels_deep_correctly_reverses_infix_ops_and_term_operators()
{
TerminalExpr t1 = TerminalExpr.Contains("t", "v");
TerminalExpr t2 = TerminalExpr.Lt("t1", "v1");
var notAnd = new NotExpr(new AndExpr(t1, t2));
TerminalExpr t3 = TerminalExpr.Gte("t", "v");
TerminalExpr t4 = TerminalExpr.Eq("t1", "v1");
var notOr = new NotExpr(new OrExpr(t3, t4));
var input = new AndExpr(notOr, notAnd);
TerminalExpr notLiked = TerminalExpr.DoesNotContain("t", "v");
TerminalExpr e1 = TerminalExpr.Gte("t1", "v1");
var expOr = new OrExpr(notLiked, e1);
TerminalExpr e3 = TerminalExpr.Lt("t", "v");
TerminalExpr e4 = TerminalExpr.NotEq("t1", "v1");
var expAnd = new AndExpr(e3, e4);
var expected = new AndExpr(expAnd, expOr);
Assert.Equal(expected, input.Accept(visitor));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment