C# Expression visitor, how to negate build filters

Question

I'm building my own IQueryable implementation for a third party API.

This API accepts filters as a list of OR's containing a list of AND statements and filters accordingly, like this:

public class Or 
{
    List<And> ands
}

public class And 
{
   field, operator, value..
}

Filters = new List<Or>();

Now building these filters goes fine, whenever I have an or statement I explode all current filters over or and whenever I get and statement I add this to all the or's. These seems to work fine except now whenever I have a unary not expression over multiple fields, I get lost.

Say I have: (a and b) or (c and d)

This would turn into filters:

 a, b  // list of ands, vertical list of or
 c, d

Negating this would result in: (!a or !b) and (!c or !d)

!a, !c
!a, !d
!b, !c
!b, !d

This would still be possible, but what I'm trying to figure out is, how I would be able to revert this if it would be double negated, which would result into (a and b) or (c and d) again. But I can't seem to figure it out. Maybe I should use a different intermediary filter structure before turning them into these and or lists. How would I be able to achieve this?

Answer 1

When you invert your example, it becomes a much larger list, as you have noted:

!((a & b) | (c & d))
!(a & b) & !(c & d)                           // De Morgan's laws
(!a | !b) & (!c | !d)                         // De Morgan's laws
(!a & !c) | (!a & !d) | (!b & !c) | (!b & !d) // Normalization

When you invert that again, the list grows even larger:

!((!a & !c) | (!a & !d) | (!b & !c) | (!b & !d))
!(!a & !c) & !(!a & !d) & !(!b & !c) & !(!b & !d)     // De Morgan's laws
(!!a | !!c) & (!!a | !!d) & (!!b | !!c) & (!!b | !!d) // De Morgan's laws
(a | c) & (a | d) & (b | c) & (b | d)                 // Double negation
(a & a & b & b) | (a & a & b & d) | (a & a & c & b) | (a & a & c & d) | (a & d & b & b) | (a & d & b & d) | (a & d & c & b) | (a & d & c & d) | (c & a & b & b) | (c & a & b & d) | (c & a & c & b) | (c & a & c & d) | (c & d & b & b) | (c & d & b & d) | (c & d & c & b) | (c & d & c & d) // Normalization

Wow, that last line sure is long! You'll have noticed some of the conjunctive clauses have duplication, i.e. a & a & b & b. So, the first step is to remove the duplicate predicates:

(a & b) | (a & b & d) | (a & c & b) | (a & c & d) | (a & d & b) | (a & d & b) | (a & d & c & b) | (a & d & c) | (c & a & b) | (c & a & b & d) | (c & a & b) | (c & a & d) | (c & d & b) | (c & d & b) | (c & d & b) | (c & d)

Now we can order the predicates within each conjunction, and remove duplicate conjunctions:

(a & b) | (a & b & c) | (a & b & c & d) | (a & b & d) | (a & c & d) | (b & c & d) | (c & d)

Okay, that cleared out a lot! But, we've still got more in this expression than we started with. If you look closely though, some of these conjunctions are redundant - e.g. a & b & c => a & b. So, if one conjunction is the super-set of another conjunction, we can remove it:

(a & b) | (c & d)

The original clause! Since you didn't include any code in your question, I won't include any in my answer - implementing the steps above is up to you. However, I would recommend you simplify your model:

public class Predicate
{
    public string Field { get; set; }
    public Operator Operator { get; set; }
    public string Value { get; set; }
}

public enum NormalForm
{
    Conjunctive,
    Disjunctive
}

public class Filter
{
    public NormalForm NormalForm { get; set; }
    public List<List<Predicate>> Predicates { get; set; }
}

This is a more flexible representation, and will make the inversion easier, because after you have applied De Morgan's laws you end up with conjunctive normal form and have to convert back.