LogicalExpressionConverter.java
/*
** Module : LogicalExpressionConverter.java
** Abstract : Conversion of the logical expression accepted by CONTAINS operator to the
** Reverse Polish Notation(RPN), Conjunctive Normal Form (CNF),
** or Disjunctive Normal Form (DNF)
**
** Copyright (c) 2020-2025, Golden Code Development Corporation.
**
** -#- -I- --Date-- ---------------------------------------Description---------------------------------------
** 001 IAS 20201011 Created initial version.
** IAS 20210306 Added ordering of CNF
** IAS 20210310 Fixed ordering of CNF
** IAS 20210315 Collect and export terms of the initial expressions
** OM 20210423 Avoid NPE when token list is empty.
** IAS 20211208 Fixed logical expression parsing: treat 'a b' as 'a & b'.
** 002 SP 20240612 Improved word split logic used in Lexer.readNextToken().
** Added Lexer.isToBeSkipped(char) to check if a character
** should be skipped when reading next token.
** 003 OM 20240801 Asterisk is a special character used as wildcard and must be processed later.
** 004 RNC 20250204 Signal that we should exit the enclosing block when encountering a wildcard error.
** 005 SP 20250311 Performance improvements. Javadoc fixes.
** 006 RNC 20250328 Improved wildcard handling in the tokenization.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.util;
import java.io.*;
import java.util.*;
import java.util.regex.*;
/**
* Conversion of the logical expression accepted by CONTAINS operator to the
* Reverse Polish Notation(RPN), Conjunctive Normal Form (CNF), or Disjunctive Normal Form (DNF)
*/
public class LogicalExpressionConverter
{
/** Regular expression pattern used to identify delimiters for splitting words. */
private final Pattern delimiterPattern;
/** Should matches be checked case-sensitively? */
private final boolean caseSensitive;
/** Logical expression to be converted. */
private final String expr;
/** Distinct terms found in the expression. */
private Map<String, Term> terms = new LinkedHashMap<>();
/**
* Constructor.
*
* @param expr
* Logical expression to be converted.
* @param caseSensitive
* Should matches be checked case-sensitively?
*/
public LogicalExpressionConverter(String expr, boolean caseSensitive)
{
this(expr, caseSensitive, null);
}
/**
* Constructor
*
* @param expr
* Logical expression to be converted.
* @param caseSensitive
* Should matches be checked case-sensitively?
* @param codePage
* Character encoding used.
*/
public LogicalExpressionConverter(String expr, boolean caseSensitive, String codePage)
{
this.delimiterPattern = I18nOps.getDelimiterPattern(codePage);
this.caseSensitive = caseSensitive;
this.expr = expr;
}
/**
* Get distinct terms found in the expression.
*
* @return distinct terms found in the expression
*/
public Map<String, Term> getTerms()
{
return terms;
}
/**
* Convert to Reverse Polish Notation (RPN).
*
* @param debug
* Print tokens as they are provided by lexer.
*
* @return RPN representation of the expression
*/
public List<EToken> toRPN(boolean debug)
{
Deque<EToken> stack = new ArrayDeque<>();
List<EToken> rpn = new ArrayList<>();
try (Reader reader = new StringReader(expr))
{
Lexer lexer = new Lexer(reader, delimiterPattern, caseSensitive);
EToken token;
boolean wasTerm = false;
while ((token = lexer.token()) != null)
{
if (debug)
{
System.out.println(token);
}
if (token instanceof Term)
{
if (wasTerm)
{
processOp(Op.AND, stack, rpn);
}
rpn.add(token);
wasTerm = true;
}
else if (token == Brackets.LPARENS)
{
if (wasTerm)
{
processOp(Op.AND, stack, rpn);
}
stack.push(token);
wasTerm = false;
}
else if (token instanceof Op)
{
wasTerm = false;
processOp(token, stack, rpn);
}
else if (token == Brackets.RPARENS)
{
while (!stack.isEmpty())
{
EToken top = stack.pop();
if (top == Brackets.LPARENS)
{
break;
}
rpn.add(top);
}
wasTerm = true;
}
else
{
throw new ErrorConditionException("Invalid expression");
}
lexer.consume();
}
while (!stack.isEmpty())
{
EToken top = stack.pop();
if (top instanceof Op)
{
rpn.add(top);
}
else
{
throw new ErrorConditionException("Invalid expression");
}
}
this.terms = lexer.terms;
}
catch (IOException e)
{
throw new ErrorConditionException(e);
}
return rpn;
}
/**
* Process operation token.
*
* @param token
* Operation token.
* @param stack
* RPN stack.
* @param rpn
* RPN expression.
*/
private void processOp(EToken token, Deque<EToken> stack, List<EToken> rpn)
{
while (!stack.isEmpty())
{
EToken top = stack.peek();
if (token instanceof Op)
{
if (top instanceof Op && ((Op) token).priority >= ((Op) top).priority)
{
top = stack.pop();
rpn.add(top);
}
else
{
break;
}
}
}
stack.push(token);
}
/**
* Convert to Conjunctive Normal Form (CNF)
*
* @param debug
* Enables printing of tokens as they are provided by lexer and intermediate data.
*
* @return CNF representation of the expression
*/
public List<List<Term>> toCNF(boolean debug)
{
return toNormalForm(Op.OR, Op.AND, debug);
}
/**
* Convert to Disjunctive Normal Form (DNF).
*
* @param debug
* Print tokens as they are provided by lexer and intermediate data.
*
* @return DNF representation of the expression
*/
public List<List<Term>> toDNF(boolean debug)
{
return toNormalForm(Op.AND, Op.OR, debug);
}
/**
* Convert to Normal Form (CNF or DNF)
*
* @param op1
* The innermost operation (OR or AND).
* @param op2
* The outermost operation (OR or AND).
* @param debug
* Enables printing of tokens as they are provided by lexer and intermediate data.
*
* @return CNF or DNF representation of the expression
*/
public List<List<Term>> toNormalForm(Op op1, Op op2, boolean debug)
{
List<List<Term>> cnf = new ArrayList<>();
List<EToken> rpn = toRPN(debug);
Deque<Node> stack = new ArrayDeque<>();
for (EToken token: rpn)
{
if (token instanceof Term)
{
stack.push(new Node((Term)token));
}
else if (token instanceof Op)
{
switch ((Op)token)
{
case NOT:
stack.push(new Node(Op.NOT, stack.pop()));
break;
case AND:
case OR:
stack.push(new Node(stack.pop(), (Op)token, stack.pop()));
break;
}
}
}
if (stack.isEmpty())
{
return cnf;
}
Node exprTree = stack.pop();
Node cnfTree = distribute(op1, op2, pushNots(exprTree));
List<EToken> cnfExpr = toList(cnfTree, new ArrayList<>());
if (debug)
{
System.out.println(cnfExpr);
}
List<Term> inner = new ArrayList<>();
for (EToken t : cnfExpr)
{
if (t == Brackets.LPARENS || t == Brackets.RPARENS || t == op1)
{
continue;
}
if( t == op2)
{
cnf.add(inner);
inner = new ArrayList<>();
}
else
{
inner.add((Term)t);
}
}
cnf.add(inner);
cnf.forEach(Collections::sort);
cnf.sort(lexicographicalComparator());
return cnf;
}
/**
* Lexicographical comparator for lists of Comparable.
*
* @param <T>
* Type parameter.
*
* @return comparator
*/
private static <T extends Comparable<T>> Comparator<List<T>> lexicographicalComparator(){
return (l1, l2) -> {
Iterator<T> i1 = l1.iterator();
Iterator<T> i2 = l2.iterator();
while(i1.hasNext() && i2.hasNext())
{
T v1 = i1.next();
T v2 = i2.next();
int rc = v1.compareTo(v2);
if (rc != 0)
{
return rc;
}
}
return i1.hasNext() ? 1 : i2.hasNext() ? -1 : 0;
};
}
/**
* Recursively convert expression tree to linear representation.
*
* @param t
* Tree to be converted.
* @param list
* List to hold a linear representation.
*
* @return linear representation of a tree
*/
private List<EToken> toList(Node t, List<EToken> list)
{
if (t != null)
{
if (t.value instanceof Term)
{
list.add(t.value);
}
else if (t.value == Op.AND || t.value == Op.OR)
{
list.add(Brackets.LPARENS);
toList(t.leftNode, list);
list.add(t.value);
toList(t.rightNode, list);
list.add(Brackets.RPARENS);
}
else if (t.value == Op.NOT)
{
list.add(t.value);
toList(t.negatedExpression, list);
}
}
return list;
}
/**
* Apply De Morgan's law and eliminate double negation.
*
* @param t
* Source tree.
*
* @return converted tree
*
*/
private Node pushNots(Node t) {
if (t.value == Op.NOT)
{
if (t.negatedExpression.value == Op.AND) {
t = new Node(
pushNots(new Node(Op.NOT, t.negatedExpression.leftNode)),
Op.OR,
pushNots(new Node(Op.NOT, t.negatedExpression.rightNode)));
}
else if (t.negatedExpression.value == Op.OR)
{
t = new Node(
pushNots(new Node(Op.NOT, t.negatedExpression.leftNode)),
Op.AND,
pushNots(new Node(Op.NOT, t.negatedExpression.rightNode)));
}
else if (t.negatedExpression.value == Op.NOT)
{
t = pushNots(t.negatedExpression.negatedExpression);
}
}
else if (t.value == Op.AND || t.value == Op.OR)
{
t.leftNode = pushNots(t.leftNode);
t.rightNode = pushNots(t.rightNode);
}
return t;
}
/**
* Apply distributive law.
*
* @param op1
* Innermost operation (OR or AND).
* @param op2
* Outermost operation (OR or AND).
* @param t
* Source tree.
*
* @return converted tree
*
*/
private Node distribute(Op op1, Op op2, Node t)
{
if (t.value == op2)
{
t.leftNode = distribute(op1, op2, t.leftNode);
t.rightNode = distribute(op1, op2, t.rightNode);
}
else if (t.value == op1)
{
Node p = distribute(op1, op2, t.leftNode);
Node q = distribute(op1, op2, t.rightNode);
if (p.value == op2)
{
t = new Node(distribute(op1, op2, new Node(p.leftNode, op1, q)), op2,
distribute(op1, op2, new Node(p.rightNode, op1, q)));
}
else if (q.value == op2)
{
t = new Node(distribute(op1, op2, new Node(p, op1, q.leftNode)), op2,
distribute(op1, op2, new Node(p, op1, q.rightNode)));
}
else
{
t.leftNode = p;
t.rightNode = q;
}
}
return t;
}
/**
* Expression tree node.
*/
public static class Node
{
/** Node value (operation or term) */
public final EToken value;
/** Left child (for binary operations) */
public Node leftNode;
/** Right child (for binary operations) */
public Node rightNode;
/** Single child (for negation) */
public final Node negatedExpression;
/**
* Constructor.
*
* @param value
* Node value (operation or term).
* @param leftNode
* Left child (for binary operations).
* @param rightNode
* Right child (for binary operations).
* @param negatedExpression
* Single child (for negation).
*/
private Node(EToken value, Node leftNode, Node rightNode, Node negatedExpression)
{
super();
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
this.negatedExpression = negatedExpression;
}
/**
* Constructor for a binary operation node.
*
* @param leftNode
* Left operand.
* @param op
* Operation.
* @param rightNode
* Right operand.
*/
public Node(Node leftNode, Op op, Node rightNode)
{
this(op, leftNode, rightNode, null);
}
/**
* Constructor for a unary operation (negation) node.
*
* @param op
* Operation.
* @param negatedExpression
* Operation argument.
*/
public Node(Op op, Node negatedExpression)
{
this(op, null, null, negatedExpression);
}
/**
* Constructor for a leaf node.
*
* @param term
* Node value.
*/
public Node(Term term)
{
this(term, null, null, null);
}
}
/**
* Base interface for all tokens.
*/
public interface EToken
{
}
/**
* Lexer which builds a token stream from the match expression.
*/
private static class Lexer
{
/** A list o special characters that must be processed later on. */
private static final String SPECIAL_CHARS = "*&|^!()";
/** Cache of characters to be skipped during tokenization. */
private static final BitSet SKIP_CHARS = new BitSet(128);
/** Cache of characters to not be skipped during tokenization. */
private static final BitSet NOT_SKIP_CHARS = new BitSet(128);
/** Regular expression pattern defining characters to be ignored by {@link #readNextToken()}. */
private final Pattern skipPattern;
/** String reader stream. */
private final Reader reader;
/** Should matches be checked case-sensitively? */
private final boolean caseSensitive;
/** Token most recently read from the expression. */
private EToken current = null;
/** Distinct terms found in the expression. */
private final Map<String, Term> terms = new LinkedHashMap<>();
/** The ordinal for a next found term. */
private int ord = 0;
/** Used to signal the presence of an asterisk in the current token. */
private boolean hasAsterisk = false;
/**
* Used to indicate if the token has normal characters between the asterisk and the
* first {@link #SKIP_CHARS} encountered. True only if {@link #hasAsterisk} was true.
*/
private boolean hasCharAfterAsterisk = false;
/**
* Constructor.
*
* @param reader
* Reader stream on the match expression text.
* @param delimiterPattern
* Regular expression pattern used to identify delimiters for splitting words.
* @param caseSensitive
* {@code true} to perform word match comparisons
* case-sensitively, {@code false} to ignore case.
*/
private Lexer(Reader reader, Pattern delimiterPattern, boolean caseSensitive)
{
this.reader = reader;
this.caseSensitive = caseSensitive;
this.skipPattern = delimiterPattern;
}
/**
* Return the most recently read token, or {@code null} if no more tokens are
* available.
*
* @return Current token or {@code null}.
*
* @throws IOException
* If there is an I/O error reading from the stream.
*/
EToken token() throws IOException
{
if (current == null)
{
readNextToken();
}
return current;
}
/**
* Mark the current token as having been consumed.
*/
void consume()
{
current = null;
}
/**
* Check if a character is to be skipped when reading the next token. The method will be influenced
* by the state of the current token (i.e. if the special asterisk mode is active or not).
* <p>
* Rules:
* <ul>
* <li>Delimiters are skipped, except for {@link #SPECIAL_CHARS}</li>
* <li>Characters in [-,.] are part of a word only if followed by a digit and earlier in the token
* there wasn't any asterisk [*].</li>
* </ul>
*
* @param c
* The character to be checked.
*
* @return {@code true} if the character should be skipped taking into account the current
* token state, or {@code false} otherwise.
*
* @throws IOException
* If there is an I/O error reading from the stream.
*/
private boolean isToBeSkipped(char c)
throws IOException
{
if (SPECIAL_CHARS.indexOf(c) != -1)
{
if (c == '*')
{
hasAsterisk = true;
}
// special characters that must be processed later on
return false;
}
// chars in "-,." are part of a word only if followed by a digit
// if these chars are after an asterisk, then they are ignored and the above rule is canceled
if (c == '-' || c == '.' || c == ',')
{
if (hasAsterisk)
{
hasCharAfterAsterisk = true;
return true;
}
if (hasCharAfterAsterisk)
{
return true;
}
reader.mark(1);
int lookAhead = reader.read();
if (lookAhead == '*')
{
hasAsterisk = true;
}
// reset reader to the previous character before lookAhead was read
reader.reset();
return lookAhead < '0' || lookAhead > '9';
}
if (NOT_SKIP_CHARS.get(c))
{
return false;
}
if (SKIP_CHARS.get(c))
{
hasAsterisk = false;
return true;
}
boolean shouldSkip = skipPattern.matcher(String.valueOf(c)).matches();
if (shouldSkip)
{
hasAsterisk = false;
SKIP_CHARS.set(c);
}
else
{
NOT_SKIP_CHARS.set(c);
}
return shouldSkip;
}
/**
* Read the next token from the match expression. This will attempt to throw an early wildcard error
* for the current token if normal chars (a, b, c, 1, etc...) are encountered after an asterisk [*].
* The case of multiple asterisks is handled only after reading the full token.
*
* @throws IOException
* If there is an I/O error reading from the stream.
*/
private void readNextToken() throws IOException
{
StringBuilder buf = new StringBuilder();
int next;
boolean more = true;
while (more)
{
reader.mark(1);
if ((next = reader.read()) < 0)
{
break;
}
char c = (char) next;
if (isToBeSkipped(c))
{
boolean shouldBreak = buf.length() > 0 &&
(!hasAsterisk && !hasCharAfterAsterisk || SKIP_CHARS.get(c));
if (shouldBreak)
{
break;
}
continue;
}
switch (c)
{
case '&':
case '|':
case '^':
case '!':
case '(':
case ')':
// case '~': // This is *not* accepted by CONTAINS, added for
// // implementation testing
more = false;
hasAsterisk = false;
hasCharAfterAsterisk = false;
if (buf.length() > 0)
{
// if a token is not finished being processed when we encounter this
// character, we reset the reader to just before this character and
// process that token first; the next time through, we'll process this
// character in the else block below
reader.reset();
}
else
{
switch (c)
{
case '&':
current = Op.AND;
break;
case '|':
case '!':
case '^':
current = Op.OR;
break;
// case '~': // This is *not* accepted by CONTAINS, added for
// // implementation testing
// current = Op.NOT;
// break;
case '(':
current = Brackets.LPARENS;
break;
case ')':
current = Brackets.RPARENS;
break;
}
}
break;
default:
if (c != '*' && (hasAsterisk || hasCharAfterAsterisk))
{
// previously we had an asterisk in the word, and we are trying to append a char which
// is a normal one, like 'a', 'b', '1', etc... . The case of multiple asterisks
// is handled by the if statement below
wildcardError();
}
buf.append(c);
break;
}
}
if (buf.length() > 0)
{
String s = buf.toString();
if (!caseSensitive)
{
s = s.toUpperCase();
}
if (s.endsWith("*"))
{
if (s.length() == 1)
{
wildcardError();
return;
}
s = s.substring(0, s.length() - 1);
if (s.indexOf('*') >= 0)
{
wildcardError();
return;
}
String key = s + "%";
current = terms.get(key);
if (current == null)
{
ord++;
current = new StartsWith(s, ord);
terms.put(key, (Term)current);
}
}
else
{
current = terms.get(s);
if (current == null)
{
ord++;
current = new Equals(s, ord);
terms.put(s, (Term)current);
}
}
}
}
/**
* Record or throw an error about incorrect wildcard syntax.
*
* @throws ErrorConditionException always.
*/
private void wildcardError()
{
String msg = "QBW syntax error - An asterisk (*) is allowed only at the end of a word";
throw new ErrorConditionException(true, 4686, msg);
}
}
/**
* Logical operations
*/
public enum Op implements EToken
{
NOT(1), AND(2), OR(3);
/** Operation priority */
public final int priority;
/**
* Constructor
*
* @param priority
* Operation priority
*/
Op(int priority)
{
this.priority = priority;
}
}
/**
* Brackets
*/
public enum Brackets implements EToken
{
LPARENS, RPARENS
}
/**
* Base class for expression terms
*/
public abstract static class Term implements EToken, Comparable<Term>
{
/** String to be compared with */
private final String value;
/** Order if the term */
private final int order;
/**
* Evaluate predicate for a set of words
*
* @param words
* Given set of words.
*
* @return <code>true</code> if any of the words satisfy the predicate
*/
public abstract boolean evaluate(Set<String> words);
/**
* Get SQL expression for the term.
*
* @return SQL expression for the term.
*/
public abstract String expr();
/**
* Get CONTAINS expression for the term.
*
* @return CONTAINS expression for the term.
*/
public abstract String containsExpr();
/**
* Constructor.
*
* @param value
* String to be compared with.
* @param order
* Order if the term.
*/
public Term(String value, int order)
{
super();
this.value = value;
this.order = order;
}
/**
* Get the String to be compared with.
*
* @return String to be compared with
*/
public String getValue()
{
return value;
}
/**
* Get the term order in the original expression.
*
* @return The term order in the original expression
*/
public int getOrder()
{
return order;
}
/**
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(Term o)
{
return Integer.compare(this.order, o.order);
}
}
/**
* "Equals" predicate
*/
public static class Equals extends Term
{
/**
* Constructor
*
* @param value
* String to be compared with.
* @param order
* Order if the term.
*/
public Equals(String value, int order)
{
super(value, order);
}
/**
* Convert to String.
*/
@Override
public String toString()
{
return "Equals(" + getValue() + ")";
}
/**
* Get SQL expression for the term.
*
* @return SQL expression for the term.
*/
public String expr()
{
return getValue();
}
/**
* Evaluate predicate for a set of words
*
* @param words
* Given set of words.
*
* @return <code>true</code> if any of the words satisfy the predicate
*/
@Override
public boolean evaluate(Set<String> words)
{
return words.contains(getValue());
}
/**
* Get CONTAINS expression for the term.
*
* @return CONTAINS expression for the term.
*/
@Override
public String containsExpr()
{
return getValue();
}
}
/**
* "StartsWith" predicate
*/
public static class StartsWith extends Term
{
/**
* Constructor
*
* @param value
* String to be compared with.
* @param order
* Order if the term.
*/
public StartsWith(String value, int order)
{
super(value, order);
}
/**
* Convert to String.
*/
@Override
public String toString()
{
return "StartsWith(" + getValue() + ")";
}
/**
* Get SQL expression for the term.
*
* @return SQL expression for the term.
*/
public String expr()
{
return getValue() + "%";
}
/**
* Get CONTAINS expression for the term.
*
* @return CONTAINS expression for the term.
*/
@Override
public String containsExpr()
{
return getValue() + "*";
}
/**
* Evaluate predicate for a set of words.
*
* @param words
* Given set of words.
*
* @return <code>true</code> if any of the words satisfy the predicate
*/
@Override
public boolean evaluate(Set<String> words)
{
return words.stream().anyMatch(w -> w.startsWith(getValue()));
}
}
/**
* Test program
*
* @param args command line arguments
*
* @throws Exception if error
*/
public static void main(String... args) throws Exception
{
System.out.println(args[0]);
LogicalExpressionConverter lexp = new LogicalExpressionConverter(args[0], true);
List<EToken> rpn = lexp.toRPN(true);
System.out.printf("RPN: %s\n", rpn);
List<List<Term>> cnf = lexp.toCNF(false);
System.out.printf("CNF: %s\n", cnf);
List<List<Term>> dnf = lexp.toDNF(false);
System.out.printf("DNF: %s\n", dnf);
}
}