From eac6a71e79797e6d37b620a91acb3c0541f1c07e Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Thu, 16 Aug 2018 01:27:37 +0300
Subject: [PATCH] Check for and prune non-viable branches in the condition tree

---
 source/category.cpp     |  8 +++--
 source/condition.cpp    | 74 ++++++++++++++++++++++++++++++++++++-----
 source/condition.h      |  3 ++
 source/rangecondition.h |  1 +
 4 files changed, 75 insertions(+), 11 deletions(-)

diff --git a/source/category.cpp b/source/category.cpp
index 5e454bb..0f6eb3f 100644
--- a/source/category.cpp
+++ b/source/category.cpp
@@ -49,8 +49,12 @@ void Category::create_statements(list<FilterStatement> &st) const
 	if(condition)
 	{
 		Condition *flat = condition->flatten();
-		flat->add_lines(st);
-		delete flat;
+		if(flat)
+		{
+			flat->add_lines(st);
+			delete flat;
+		}
+		// TODO handle the case of the entire condition being non-viable
 	}
 }
 
diff --git a/source/condition.cpp b/source/condition.cpp
index a8a5a90..4d00b6c 100644
--- a/source/condition.cpp
+++ b/source/condition.cpp
@@ -49,11 +49,15 @@ Condition *CompoundCondition::flatten() const
 			Condition *sub = (*i)->flatten();
 			if(!result)
 				result = sub;
-			else
+			else if(sub)
 				result = dispatch_flatten(result, sub);
 		}
 
-		return result;
+		if(result && result->is_viable())
+			return result;
+
+		delete result;
+		return 0;
 	}
 }
 
@@ -98,16 +102,25 @@ Condition *CompoundCondition::merge_two(Condition *cond1, Condition *cond2, bool
 	parts.push_back(cond1);
 	parts.push_back(cond2);
 	Condition *result = cond1->merge(parts, *this);
+
 	if(del)
 	{
 		delete cond1;
 		delete cond2;
+
+		if(!result->is_viable())
+		{
+			delete result;
+			return 0;
+		}
 	}
+
 	return result;
 }
 
 Condition *CompoundCondition::add_merged_to(Condition *cond, CompoundCondition *target, bool del) const
 {
+	bool merged = false;
 	for(vector<Condition *>::iterator i=target->conditions.begin(); i!=target->conditions.end(); ++i)
 		if((*i)->can_merge(*cond, *target))
 		{
@@ -116,10 +129,19 @@ Condition *CompoundCondition::add_merged_to(Condition *cond, CompoundCondition *
 			if(del)
 				delete cond;
 			*i = m;
-			return target;
+			merged = true;
+			break;
 		}
 
-	target->add(del ? cond : cond->clone());
+	if(!merged)
+		target->add(del ? cond : cond->clone());
+
+	if(del && !target->is_viable())
+	{
+		delete target;
+		return 0;
+	}
+
 	return target;
 }
 
@@ -129,7 +151,12 @@ Condition *CompoundCondition::merge_contents_to(CompoundCondition *cond, Compoun
 		add_merged_to(*i, target, false);
 
 	delete cond;
-	return target;
+
+	if(target->is_viable())
+		return target;
+
+	delete target;
+	return 0;
 }
 
 
@@ -166,9 +193,15 @@ Condition *AndCondition::flatten(OrCondition *cond1, Condition *cond2) const
 	OrCondition *result = new OrCondition;
 	unsigned count = cond1->count();
 	for(unsigned i=0; i<count; ++i)
-		result->add(dispatch_flatten(cond1->get(i)->clone(), (i+1<count ? cond2->clone() : cond2)));
+		if(Condition *sub = dispatch_flatten(cond1->get(i)->clone(), (i+1<count ? cond2->clone() : cond2)))
+			result->add(sub);
 	delete cond1;
-	return result;
+
+	if(result->is_viable())
+		return result;
+
+	delete result;
+	return 0;
 }
 
 Condition *AndCondition::flatten(OrCondition *cond1, AndCondition *cond2) const
@@ -183,10 +216,25 @@ Condition *AndCondition::flatten(OrCondition *cond1, OrCondition *cond2) const
 	OrCondition *result = new OrCondition;
 	for(unsigned i=0; i<count1; ++i)
 		for(unsigned j=0; j<count2; ++j)
-			result->add(dispatch_flatten(cond1->get(i)->clone(), cond2->get(j)->clone()));
+			if(Condition *sub = dispatch_flatten(cond1->get(i)->clone(), cond2->get(j)->clone()))
+				result->add(sub);
+
 	delete cond1;
 	delete cond2;
-	return result;
+
+	if(result->is_viable())
+		return result;
+
+	delete result;
+	return 0;
+}
+
+bool AndCondition::is_viable() const
+{
+	for(vector<Condition *>::const_iterator i=conditions.begin(); i!=conditions.end(); ++i)
+		if(!(*i)->is_viable())
+			return false;
+	return !conditions.empty();
 }
 
 void AndCondition::add_lines(list<FilterStatement> &st) const
@@ -239,6 +287,14 @@ Condition *OrCondition::flatten(OrCondition *cond1, OrCondition *cond2) const
 	return merge_contents_to(cond2, cond1);
 }
 
+bool OrCondition::is_viable() const
+{
+	for(vector<Condition *>::const_iterator i=conditions.begin(); i!=conditions.end(); ++i)
+		if((*i)->is_viable())
+			return true;
+	return false;
+}
+
 void OrCondition::add_lines(list<FilterStatement> &st) const
 {
 	list<FilterStatement> result;
diff --git a/source/condition.h b/source/condition.h
index 979f1e9..163c9c8 100644
--- a/source/condition.h
+++ b/source/condition.h
@@ -21,6 +21,7 @@ public:
 	virtual Condition *flatten() const { return clone(); }
 	virtual bool can_merge(const Condition &, const CompoundCondition &) const { return false; }
 	virtual Condition *merge(const std::vector<Condition *> &, const CompoundCondition &) const { return 0; }
+	virtual bool is_viable() const { return true; }
 	virtual void add_lines(std::list<FilterStatement> &) const = 0;
 };
 
@@ -71,6 +72,7 @@ protected:
 	virtual Condition *flatten(OrCondition *, AndCondition *) const;
 	virtual Condition *flatten(OrCondition *, OrCondition *) const;
 public:
+	virtual bool is_viable() const;
 	virtual void add_lines(std::list<FilterStatement> &) const;
 };
 
@@ -87,6 +89,7 @@ protected:
 	virtual Condition *flatten(OrCondition *, AndCondition *) const;
 	virtual Condition *flatten(OrCondition *, OrCondition *) const;
 public:
+	virtual bool is_viable() const;
 	virtual void add_lines(std::list<FilterStatement> &) const;
 };
 
diff --git a/source/rangecondition.h b/source/rangecondition.h
index 8355135..beba0dd 100644
--- a/source/rangecondition.h
+++ b/source/rangecondition.h
@@ -22,6 +22,7 @@ public:
 	virtual RangeCondition<T> *clone() const;
 	virtual bool can_merge(const Condition &, const CompoundCondition &) const;
 	virtual RangeCondition<T> *merge(const std::vector<Condition *> &, const CompoundCondition &) const;
+	virtual bool is_viable() const { return min<=max; }
 	virtual void add_lines(std::list<FilterStatement> &) const;
 };
 
-- 
2.45.2