C# Expression visitor, how to negate build filters

Question

Im building my own IQuerable implementation for a third party api.

This Api accepts filters as a list of OR's contaiing a list of AND statements and fitlers 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 into: (!a or !b) and (!c or !d)

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

this would still be possible, but what im 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 intermediar 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.