//============================================================================== // QueryExpr.java //============================================================================== package tribble.parse.sql; // System imports import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStream; import java.io.PrintWriter; import java.io.Writer; import java.lang.Character; import java.lang.Cloneable; import java.lang.CloneNotSupportedException; import java.lang.Integer; import java.lang.Exception; import java.lang.String; import java.lang.StringBuffer; import java.util.HashMap; // Local imports import tribble.io.ParseTreeI; /******************************************************************************* * Query expression tree. * *

* An object of this type is produced by a {@link QueryParser} object, which * parses an SQL-like expression (i.e., an expression similar to an SQL * 'SELECT WHERE' clause) and produces an expression tree * in the form of a {@link QueryExpr} object. * * *

* * Expression Trees * *

* Some example query expressions and the expression trees resulting from parsing * them: * *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Query Expression Tree
* 
* exists
*
* 		* 
* val
*   "exists"
*
*
* 
* not directory
*
* 		* 
* not
*   val
*     "directory"
*
*
* 
* not directory or writable
*
* 		* 
* or
*   not
*     val
*       "directory"
*   val
*     "writable"
*
*
* 
* name like "Sarah%Conner" and
*   ( birth_date >= '1996-06-14' )
*
* 		* 
* and
*   like
*     "name"
*     "\"Sarah%Conner\""
*   ge
*     "birth_date"
*     "'1996-06-14'"
*
*
* 
* interest >= 5.000  and
*   interest < 10.000
*
* 		* 
* and
*   ge
*     "interest"
*     "5.000"
*   lt
*     "interest"
*     "10.000"
*
*
* 
* rec.id between 'A000' and 'B999'
*
* 		* 
* between
*   "rec.id"
*   and
*     "'A000'"
*     "'B999'"
*
*
* 
* pay-type in ( 'WK' 'HR' 'YR' )
*
* 		* 
* in
*   "pay-type"
*   list
*     "'WK'"
*     list
*       "'HR'"
*       list
*         "'YR'"
*
*
* 
* addr is not null
*
* 		* 
* not
*   is
*     "addr"
*     "null"
*
*
* 
* rec.pay[mon]
*
* 		* 
* subscr
*   member
*     "rec"
*     "pay"
*   "mon"
*
*
* * * @version $Revision: 1.10 $ $Date: 2007/08/01 03:14:02 $ * @since 2001-03-24 * @author David R. Tribble (david@tribble.com). *

* Copyright ©2001 by David R. Tribble, all rights reserved.
* Permission is granted to any person or entity except those designated by * by the United States Department of State as a terrorist, or terrorist * government or agency, to use and distribute this source code provided * that the original copyright notice remains present and unaltered. * * @see QueryParser */ public class QueryExpr ///+TEMP: implements tribble.io.ParseTreeI, java.lang.Cloneable implements java.lang.Cloneable { // Identification /** Revision information. */ static final String REV = "@(#)tribble/parse/sql/QueryExpr.java $Revision: 1.10 $ $Date: 2007/08/01 03:14:02 $\n"; public static final int SERIES = 200; // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Public constants //---------------------------------- // Operator types public static final String OP_NOP = "nop"; // Ext public static final String OP_VALUE = "val"; public static final String OP_NOT = "not"; public static final String OP_AND = "and"; public static final String OP_OR = "or"; public static final String OP_LIST = "list"; public static final String OP_IS = "is"; public static final String OP_EQ = "eq"; public static final String OP_NE = "ne"; public static final String OP_LT = "lt"; public static final String OP_LE = "le"; public static final String OP_GT = "gt"; public static final String OP_GE = "ge"; public static final String OP_EXPO = "exp"; public static final String OP_MUL = "mul"; public static final String OP_DIV = "div"; public static final String OP_MOD = "mod"; public static final String OP_ADD = "add"; public static final String OP_SUB = "sub"; public static final String OP_CONCAT = "concat"; public static final String OP_POS = "pos"; public static final String OP_NEG = "neg"; public static final String OP_MEMBER = "member"; public static final String OP_SUBSCR = "subscr"; public static final String OP_CONTAINS = "contains"; public static final String OP_LIKE = "like"; public static final String OP_LIKEFILE = "likefile"; // Ext public static final String OP_IN = "in"; public static final String OP_BETWEEN = "between"; public static final String OP_NULL = "null"; // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Package private constants static final String OP_LP = "("; static final String OP_RP = ")"; static final String OP_SUBSCR2 = "]"; // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Public static methods /*************************************************************************** * Determine if a string matches a pattern string. * * @param pat * An SQL pattern string. * A pattern is composed of regular characters and * special pattern matching characters, which are: *

*
*
*
_ (underscore) * - Matches any single character. * *
% * - Matches zero or more characters. * *
\ * - Removes (escapes) the special meaning of the next character. * *
*
*
* * @param s * A string to compare against pattern pat. * * @return * True if string s matches pattern pat, otherwise false. * * @since 1.2, 2001-03-28 */ public static boolean matchPattern(String pat, String s) { int r; r = matchSubpattern(pat, 0, s, 0); return (r >= 0); } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Protected static methods /*************************************************************************** * Determine if a substring matches a pattern substring. * * @param pat * A pattern string. * * @param patOff * The index of the first (leftmost) character within pattern string * pat to match. * * @param str * A string to compare against pattern pat. * * @param strOff * The index of the first (leftmost) character within string str to * match. * * @return * The index of one character past the last (rightmost) character within * string str that matches pattern pat, or -1 if the * substring does not match the pattern substring. * * @see #matchPattern * * @since 1.2, 2001-03-28 */ protected static int matchSubpattern(String pat, int patOff, String str, int strOff) { int patLen; int strLen; int pi; int si; // Attempt to match the string, one pattern character at a time patLen = pat.length(); strLen = str.length(); for (pi = patOff, si = strOff; pi < patLen; pi++) { char pCh; int sCh; sCh = -1; if (si < strLen) sCh = str.charAt(si); pCh = pat.charAt(pi); switch (pCh) { case '%': // Match zero or more characters for (int j = strLen; j >= si; j--) { // Assume a match of substring 'str[si...j-1]', // attempt to match the rest of the pattern if (matchSubpattern(pat, pi+1, str, j) >= 0) { // Successful submatch return (j); } } // Submatch failed return (-1); case '_': // Match any single character if (sCh < 0) return (-1); // Submatch succeeded si++; break; case '\\': // Escape the next pattern character if (pi+1 < patLen) pCh = pat.charAt(++pi); if (pCh != sCh) return (-1); // Submatch succeeded si++; break; default: // Match a single character exactly if (sCh < 0) return (-1); if (pCh != sCh) return (-1); // Submatch succeeded si++; break; } } // Match the end of the string if (si == strLen) return (si); // Pattern match failed return (-1); } /*************************************************************************** * Add enclosing quotes to a string if necessary to make it a valid SQL * token. * * @param s * A string. * * @return * The contents of string s, either unchanged or enclosed within * quotes ("). * * @since 1.9, 2001-04-16 */ protected static String asQuotedOperand(String s) { int len; char ch; StringBuffer text; boolean needsQuotes = false; // Check for quotes len = s.length(); ch = s.charAt(0); if (ch == '"' || ch == '\'') return (s); // Rebuild the string with enclosing quotes text = new StringBuffer(len+2+8); text.append('`'); for (int i = 0; i < len; i++) { ch = s.charAt(i); if (ch == '"') { text.append('\\'); needsQuotes = true; } else if (!Character.isJavaIdentifierPart(ch)) needsQuotes = true; text.append(ch); } if (needsQuotes) { text.append('`'); s = text.toString(); } return (s); } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Public variables /** Operator, one of the OP_XXX constants. */ public String m_op = OP_NOP; /** First (left) argument, * typically either a {@link QueryExpr} or a String. */ public Object m_arg1; /** Second (right) argument, * typically either a {@link QueryExpr} or a String. */ public Object m_arg2; // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Public constructors /*************************************************************************** * Default constructor. * * @since 1.1, 2001-03-13 */ public QueryExpr() { // Do nothing } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Public methods /*************************************************************************** * Convert this expression tree into a printable text string. * * @return * A text string representing this expression. * (Note that the string is generated directly from the expression tree, and * may not necessarily look the same as the original query expression that * the tree was derived from.) * * @since 1.1, 2001-03-26 */ public String toString() //overrides java.lang.Object { StringBuffer text; // Build a string from this expression tree text = new StringBuffer(80); buildString(text); return (text.toString()); } /*************************************************************************** * Create a duplicate of this query expression tree. * * @return * A deep-copy duplicate of this expression tree. * * @throws CloneNotSupportedException * Thrown if any of the node in this expression tree cannot be cloned. * * @since 1.5, 2001-04-01 */ public Object clone() throws CloneNotSupportedException //implements java.lang.Cloneable { QueryExpr dup; // Create a clone of this node dup = new QueryExpr(); dup.m_op = m_op; if (m_arg1 instanceof String) dup.m_arg1 = m_arg1; else if (m_arg1 instanceof QueryExpr) dup.m_arg1 = ((QueryExpr) m_arg1).clone(); /*+++NOT IMPLEMENTED else if (m_arg1 instanceof Cloneable) dup.m_arg1 = m_arg1.clone(); +++*/ else throw new CloneNotSupportedException("Can't clone node, type: " + m_arg1.getClass().getName()); if (m_arg2 instanceof String) dup.m_arg2 = m_arg2; else if (m_arg2 instanceof QueryExpr) dup.m_arg2 = ((QueryExpr) m_arg1).clone(); /*+++NOT IMPLEMENTED else if (m_arg2 instanceof Cloneable) dup.m_arg2 = m_arg2.clone(); +++*/ else throw new CloneNotSupportedException("Can't clone node, type: " + m_arg2.getClass().getName()); return (dup); } /*************************************************************************** * Print this query expression tree as XML. * *

* For example, given the query expression: * 

    *    len > 80 and rec.type not = 'T'
* * the following XML is generated for it: * 
    *    <query>
    *      <and>
    *        <gt>
    *          <arg>len</arg>
    *          <arg>80</arg>
    *        </gt>
    *        <not>
    *          <eq>
    *            <member>
    *              <arg>rec</arg>
    *              <arg>type</arg>
    *            </member>
    *            <arg>'T'</arg>
    *          </eq>
    *        </not>
    *      </and>
    *    </query>
* * * @param out * Output stream to write to. * * @throws IOException * Thrown if an I/O (write) error occurs. * * @since 1.6, 2001-04-02 */ public void writeAsXml(Writer out) throws IOException { BufferedWriter os; if (out instanceof BufferedWriter) os = (BufferedWriter) out; else os = new BufferedWriter(out); // Write this expression tree as XML os.write(""); os.newLine(); writeAsXml(os, " "); os.write(""); os.newLine(); os.flush(); } /*************************************************************************** * Print the structure of this expression tree. * * @param out * An output stream to write to. * * @since 1.1, 2001-03-12 */ public void dump(Writer out) { PrintWriter outw; // Check args if (out == null) return; if (out instanceof PrintWriter) outw = (PrintWriter) out; else outw = new PrintWriter(out, true); // Dump the expression tree dumpTree(outw, ""); outw.flush(); } /*************************************************************************** * Print the structure of this expression tree. * * @param out * An output stream to write to. * * @since 1.1, 2001-03-12 */ public void dump(OutputStream out) { PrintWriter outw; // Check args if (out == null) return; // Dump the expression tree outw = new PrintWriter(out, true); dumpTree(new PrintWriter(out, true), ""); outw.flush(); } /*************************************************************************** * Simplify this query expression tree. * *

* Replaces the following query subexpressions with equivalent, but simpler, * subexpressions: * 

    *    "X between A and B"   replaced with   "X >= A and X <= B"
    *    "X in ( A, B, C )"    replaced with   "X = A or X = B or X = C"
    *    "not X = A"           replaced with   "X <> A"
    *    "not not X = A"       replaced with   "X = A"
* *

* In other words, the following subexpression trees are replaced with * simpler equivalent subtrees: * *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Before After
* 
    * between
    *   "rec_id"
    *   and
    *     "'A000'"
    *     "'B999'"
    *
* 		* 
    * and
    *   ge
    *     "rec_id"
    *     "'A000'"
    *   le
    *     "rec_id"
    *     "'B999'"
    *
*
* 
    * in
    *   "pay-type"
    *   list
    *     "'WK'"
    *     list
    *       "'HR'"
    *       list
    *         "'YR'"
    *
* 		* 
    * or
    *   eq
    *     "pay-type"
    *     "'WK'"
    *   or
    *     eq
    *       "pay-type"
    *       "'HR'"
    *     eq
    *       "pay-type"
    *       "'YR'"
    *
*
* 
    * not
    *   gt
    *     "Amt"
    *     "25.00"
    *
* 		* 
    * le
    *   "Amt"
    *   "25.00"
    *
*
* 
    * not
    *   not
    *     eq
    *       "Amt"
    *       "50.00"
    *
* 		* 
    * eq
    *   "Amt"
    *   "50.00"
    *
*
* * * @throws Exception * Thrown if this expression tree is malformed. * * @since 1.7, 2001-04-03 */ public void simplify() throws Exception { // Simplify this expression tree if (m_op == OP_BETWEEN) { QueryExpr sub; QueryExpr cmp; // Replace this "X between A and B" expression // with the equivalent "X >= A and X <= B" sub = (QueryExpr) m_arg2; if (sub.m_op != OP_AND) throw new Exception("Malformed BETWEEN expression, op='" + sub.m_op + "'"); // Build an "X >= A" subtree cmp = new QueryExpr(); cmp.m_op = OP_GE; cmp.m_arg1 = this.m_arg1; cmp.m_arg2 = sub.m_arg1; // Build an "X <= B" subtree sub.m_op = OP_LE; sub.m_arg1 = this.m_arg1; // Replace this "between" tree with an "and" tree this.m_op = OP_AND; this.m_arg1 = cmp; } else if (m_op == OP_IN) { QueryExpr sub; // Replace this "X IN ( A, B, C )" expression // with the equivalent "X = A or X = B or X = C" sub = (QueryExpr) m_arg2; if (sub.m_op != OP_LIST) throw new Exception("Malformed IN expression, op='" + sub.m_op + "'"); while (sub != null && sub.m_op == OP_LIST) { // Build an "X = A" subtree if (sub.m_arg2 != null) { QueryExpr cmp; cmp = new QueryExpr(); cmp.m_op = OP_EQ; cmp.m_arg1 = this.m_arg1; // X cmp.m_arg2 = sub.m_arg1; // A/B sub.m_op = OP_OR; sub.m_arg1 = cmp; sub = (QueryExpr) sub.m_arg2; // OP_LIST or null } else { sub.m_op = OP_EQ; sub.m_arg2 = sub.m_arg1; // C sub.m_arg1 = this.m_arg1; // X sub = null; } } // Replace the extra OP_IN node sub = (QueryExpr) m_arg2; // OP_OR, was OP_LIST this.m_op = sub.m_op; this.m_arg1 = sub.m_arg1; this.m_arg2 = sub.m_arg2; } else if (m_op == OP_NOT && m_arg1 instanceof QueryExpr) { QueryExpr sub; // Examine the negated subexpression sub = (QueryExpr) m_arg1; sub.simplify(); if (sub.m_op == OP_NOT) { // Replace this 'NOT NOT X' expression // with the equivalent 'X' if (sub.m_arg1 instanceof QueryExpr) { sub = (QueryExpr) sub.m_arg1; this.m_op = sub.m_op; this.m_arg1 = sub.m_arg1; this.m_arg2 = sub.m_arg2; } else if (sub.m_arg1 instanceof String) // SNO { this.m_op = OP_VALUE; this.m_arg1 = (String) sub.m_arg1; } } else { String op = null; // Replace this 'NOT X = A' expression // with the equivalent 'X <> A', et al if (sub.m_op == OP_EQ) op = OP_NE; else if (sub.m_op == OP_NE) op = OP_EQ; else if (sub.m_op == OP_LT) op = OP_GE; else if (sub.m_op == OP_LE) op = OP_GT; else if (sub.m_op == OP_GT) op = OP_LE; else if (sub.m_op == OP_GE) op = OP_LT; if (op != null) { this.m_op = op; this.m_arg1 = sub.m_arg1; this.m_arg2 = sub.m_arg2; } } } else { // Recursively simplify the left subexpression if (m_arg1 instanceof QueryExpr) ((QueryExpr) m_arg1).simplify(); // Recursively simplify the right subexpression if (m_arg2 instanceof QueryExpr) ((QueryExpr) m_arg2).simplify(); } } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Protected methods /*************************************************************************** * Print the structure of this expression tree. * *

* This method is called by methods {@link #dump(Writer)} and * {@link #dump(OutputStream)}. * *

* Example *

* Parsing the expression: * 

    *    name like "sarah%conner" and ( birth.date >= '1996-06-14' )
* results in an expression tree that is printed like this: * 
    *    and
    *      like
    *        name
    *        "sarah%conner"
    *      ge
    *        birth.date
    *        '1996-06-14'
* * * @param out * An output stream to write to. * * @param indent * Leading indentation. * * @see #dump(Writer) * @see #dump(OutputStream) * * @since 1.1, 2001-03-12 */ protected void dumpTree(PrintWriter out, String indent) { // Print the node operator out.println(indent + (m_op == null ? "op:" : m_op)); indent += " "; // Print arg1 if (m_arg1 == null) out.println(indent + "arg1:"); else if (m_arg1 instanceof String) out.println(indent + asQuotedOperand((String) m_arg1)); else if (m_arg1 instanceof QueryExpr) ((QueryExpr) m_arg1).dumpTree(out, indent); else out.println(indent + "? " + m_arg1.getClass().getName()); // Print arg2 if (m_arg2 == null) ; // Print nothing else if (m_arg2 instanceof String) out.println(indent + asQuotedOperand((String) m_arg2)); else if (m_arg2 instanceof QueryExpr) ((QueryExpr) m_arg2).dumpTree(out, indent); else out.println(indent + "? " + m_arg2.getClass().getName()); } /*************************************************************************** * Convert this expression subtree into a printable text string, appending * it to a string buffer. * *

* This method is called by method {@link #toString}. * * @param text * A string buffer to append the text string representation of this * subexpression to. * * @see #toString * * @since 1.1, 2001-03-26 */ protected void buildString(StringBuffer text) { // Stringize and append this expression subtree to the text string if (m_op == OP_VALUE && m_arg2 == null) { buildString(m_arg1, text); } else if (m_op == OP_NOT) { text.append("not ("); if (m_arg1 != null) buildString(m_arg1, text); else text.append("null?"); if (m_arg2 != null) { text.append("("); buildString(m_arg2, text); text.append(")?"); } text.append(")"); } else if (m_op == OP_AND) { if (m_arg1 != null) { if (m_arg1 instanceof QueryExpr && ((QueryExpr) m_arg1).m_op == OP_OR) { text.append('('); buildString(m_arg1, text); text.append(')'); } else buildString(m_arg1, text); } else text.append("null?"); text.append(" and "); if (m_arg2 != null) { if (m_arg2 instanceof QueryExpr && ((QueryExpr) m_arg2).m_op == OP_OR) { text.append('('); buildString(m_arg2, text); text.append(')'); } else buildString(m_arg2, text); } } else if (m_op == OP_POS || m_op == OP_NEG) { text.append(m_op == OP_POS ? "+" : "-"); if (m_arg1 != null) buildString(m_arg1, text); else text.append("null?"); } else { String op; String op2 = null; if (m_op == null) op = " nullop? "; else if (m_op == OP_EQ) op = " = "; else if (m_op == OP_NE) op = " <> "; else if (m_op == OP_LT) op = " < "; else if (m_op == OP_LE) op = " <= "; else if (m_op == OP_GT) op = " > "; else if (m_op == OP_GE) op = " >= "; else if (m_op == OP_ADD) op = " + "; else if (m_op == OP_SUB) op = " - "; else if (m_op == OP_CONCAT) op = " || "; else if (m_op == OP_MUL) op = " * "; else if (m_op == OP_DIV) op = " / "; else if (m_op == OP_MOD) op = " mod "; else if (m_op == OP_EXPO) op = " ** "; else if (m_op == OP_MEMBER) op = "."; else if (m_op == OP_SUBSCR) { op = "["; op2 = "]"; } else if (m_op == OP_IN) { op = " in ("; op2 = ")"; } else if (m_op == OP_LIST) { op = ""; if (m_arg2 != null) op = ", "; } else op = ' ' + m_op + ' '; if (m_arg1 != null) buildString(m_arg1, text); else text.append("null?"); text.append(op); if (m_arg2 != null) buildString(m_arg2, text); if (op2 != null) text.append(op2); } } /*************************************************************************** * Format an operand, appending it to a string buffer. * *

* This method is called by method {@link #toString}. * * @param arg * An operand to append, which is either a String or an * {@link QueryExpr} subtree. if it is a String, it will be * delimited with quotes as necessary. * * @param text * A string buffer to append the text string representation of this * subexpression to. * * @see #toString * @see #buildString(StringBuffer) * * @since 1.3, 2001-03-30 */ protected void buildString(Object arg, StringBuffer text) { if (arg instanceof String) { String s; // Append the string literal operand to the text string s = (String) arg; text.append(asQuotedOperand(s)); } else ((QueryExpr) arg).buildString(text); } /*************************************************************************** * Print this query expression tree as XML. * *

* This method is called by method {@link #writeAsXml(Writer) writeAsXml()}. * * @param out * Output stream to write to. * * @param indent * Indentation prefix for each line of XML text output. * * @throws IOException * Thrown if an I/O (write) error occurs. * * @see #writeAsXml(Writer) writeAsXml * * @since 1.6, 2001-04-02 */ protected void writeAsXml(BufferedWriter out, String indent) throws IOException { // Write this expression tree as XML out.write(indent); out.write('<'); out.write(m_op); out.write('>'); out.newLine(); if (m_arg1 != null || m_arg2 != null) { String indent2; indent2 = indent + " "; if (m_arg1 != null) { if (m_arg1 instanceof String) writeStringAsXml(out, indent2, (String) m_arg1); else if (m_arg1 instanceof QueryExpr) ((QueryExpr) m_arg1).writeAsXml(out, indent2); } if (m_arg2 != null) { if (m_arg2 instanceof String) writeStringAsXml(out, indent2, (String) m_arg2); else if (m_arg2 instanceof QueryExpr) ((QueryExpr) m_arg2).writeAsXml(out, indent2); } } out.write(indent); out.write("'); out.newLine(); } /*************************************************************************** * Print a query expression string argument tree as XML. * *

* This method is called by method {@link #writeAsXml(Writer) writeAsXml()}. * * @param out * Output stream to write to. * * @param indent * Indentation prefix for each line of XML text output. * * @param arg * An expression operand from a query expression tree. * * @throws IOException * Thrown if an I/O (write) error occurs. * * @see #writeAsXml(Writer) writeAsXml * * @since 1.6, 2001-04-02 */ protected void writeStringAsXml(BufferedWriter out, String indent, String arg) throws IOException { int len; char quote = '"'; // Write a single expression operand as XML text out.write(indent); out.write(""); len = arg.length(); if (len > 0) quote = arg.charAt(0); for (int i = 0; i < len; i++) { int ch; ch = arg.charAt(i); switch (ch) { case '<': out.write("<"); break; case '>': out.write(">"); break; case '&': out.write("&"); break; case '\'': if (ch == quote && i > 0 && i < len-1) out.write('\\'); out.write((char) ch); break; case '"': if (ch == quote && i > 0 && i < len-1) out.write('\\'); out.write((char) ch); break; default: if (ch <= 0x0020 || ch >= 0x0080 && ch <= 0x00A0) { out.write("&#"); out.write(Integer.toString(ch)); out.write(';'); } else out.write((char) ch); break; } } out.write(""); out.newLine(); } } // End QueryExpr.java