package com.dbxml.db.common.xpath;

/*
 * dbXML - Native XML Database
 * Copyright (C) 1999-2004  The dbXML Group, L.L.C.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Pugeblic License
 * as published by the Free Software Foundation; either version 2
 * 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Id: XPathQuery.java,v 1.8 2004/02/12 00:17:56 bradford Exp $
 */

import com.dbxml.db.core.indexer.helpers.*;
import com.dbxml.db.core.query.*;
import org.w3c.dom.*;

import com.dbxml.db.common.query.QueryBase;
import com.dbxml.db.core.Collection;
import com.dbxml.db.core.data.Key;
import com.dbxml.db.core.data.Value;
import com.dbxml.db.core.indexer.IndexMatch;
import com.dbxml.db.core.indexer.IndexPattern;
import com.dbxml.db.core.indexer.IndexQuery;
import com.dbxml.db.core.indexer.Indexer;
import com.dbxml.db.core.transaction.Transaction;
import com.dbxml.xml.NamespaceMap;
import com.dbxml.xml.dom.DOMHelper;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import org.apache.xml.utils.PrefixResolver;
import org.apache.xml.utils.PrefixResolverDefault;
import org.apache.xpath.Expression;
import org.apache.xpath.compiler.Compiler;
import org.apache.xpath.compiler.FunctionTable;
import org.apache.xpath.compiler.OpCodes;
import org.apache.xpath.compiler.XPathParser;
import org.apache.xpath.objects.XBoolean;
import org.apache.xpath.objects.XNumber;
import org.apache.xpath.objects.XObject;
import org.apache.xpath.objects.XString;
import org.xml.sax.SAXException;

/**
 * XPathQuery
 */

final class XPathQuery extends QueryBase {
   private static final int KEYSET_LIMIT = 1024;

   private static final String XPATH = "xpath";

   private static final Key[] EmptyKeys = new Key[0];
   private static final Key[][] EmptyKeySet = new Key[0][0];

   private static final String WILDCARD = "*";

   // Maps Xalan Comparisons To IndexQuery
   private static final int[] OpMap = {
      IndexQuery.NEQ,
      IndexQuery.EQ,
      IndexQuery.LTE,
      IndexQuery.LT,
      IndexQuery.GTE,
      IndexQuery.GT
   };

   // Maps XPath Functions To Internal IDs (These are Xalan IDs)
   private static final int FUNC_NOT = FunctionTable.FUNC_NOT;
   private static final int FUNC_TRUE = FunctionTable.FUNC_TRUE;
   private static final int FUNC_FALSE = FunctionTable.FUNC_FALSE;
   private static final int FUNC_BOOLEAN = FunctionTable.FUNC_BOOLEAN;
   private static final int FUNC_NUMBER = FunctionTable.FUNC_NUMBER;
   private static final int FUNC_FLOOR = FunctionTable.FUNC_FLOOR;
   private static final int FUNC_CEILING = FunctionTable.FUNC_CEILING;
   private static final int FUNC_ROUND = FunctionTable.FUNC_ROUND;
   private static final int FUNC_SUM = FunctionTable.FUNC_SUM;
   private static final int FUNC_STRING = FunctionTable.FUNC_STRING;
   private static final int FUNC_STARTS_WITH = FunctionTable.FUNC_STARTS_WITH;
   private static final int FUNC_CONTAINS = FunctionTable.FUNC_CONTAINS;
   private static final int FUNC_SUBSTRING_BEFORE = FunctionTable.FUNC_SUBSTRING_BEFORE;
   private static final int FUNC_SUBSTRING_AFTER = FunctionTable.FUNC_SUBSTRING_AFTER;
   private static final int FUNC_NORMALIZE_SPACE = FunctionTable.FUNC_NORMALIZE_SPACE;
   private static final int FUNC_TRANSLATE = FunctionTable.FUNC_TRANSLATE;
   private static final int FUNC_CONCAT = FunctionTable.FUNC_CONCAT;
   private static final int FUNC_SUBSTRING = FunctionTable.FUNC_SUBSTRING;
   private static final int FUNC_STRING_LENGTH = FunctionTable.FUNC_STRING_LENGTH;

   private PrefixResolver pr;
   private String xpath;
   private Compiler cmp;

   public XPathQuery(Collection context, String query, NamespaceMap nsMap, Key[] keys) throws QueryException {
      super(context, query, nsMap, keys);
   }

   public void compileQuery() throws CompilationException {
      Expression ex = null;
      Element nsNode = null;

      if ( nsMap != null )
         nsNode = nsMap.getContextNode();

      xpath = query;
      if ( query.trim().startsWith("<") ) {
         try {
            // Try to parse the query as XML
            Document doc = DOMHelper.parseText(query);
            Element root = doc.getDocumentElement();

            if ( !root.getNamespaceURI().equals(Query.NSURI) )
               throw new CompilationException("Invalid Namespace '" + root.getNamespaceURI() + "'");

            if ( !root.getLocalName().equals(XPATH) )
               throw new CompilationException("Unknown Tag '" + root.getLocalName() + "'");

            if ( nsNode == null )
               nsNode = root;
            else {
               // Have to pull them over
               NamedNodeMap nm = root.getAttributes();
               for ( int i = 0; i < nm.getLength(); i++ ) {
                  Attr attr = (Attr)nm.item(i);
                  if ( NamespaceMap.isNamespaceDeclaration(attr) )
                     nsNode.setAttribute(attr.getName(), attr.getValue());
               }
            }

            StringBuffer sb = new StringBuffer(64);
            NodeList nl = root.getChildNodes();
            for ( int i = 0; i < nl.getLength(); i++ ) {
               Node n = nl.item(i);
               switch ( n.getNodeType() ) {
                  case Node.ELEMENT_NODE:
                  case Node.PROCESSING_INSTRUCTION_NODE:
                     throw new CompilationException("Only text is allowed for XPath source");

                  case Node.TEXT_NODE:
                     sb.append(((Text)n).getData());
                     break;
               }
            }
            xpath = sb.toString();
         }
         catch ( SAXException e ) {
         }
         catch ( IOException e ) {
            /** @todo Through a CompilationException? */
         }
      }

      try {
         if ( nsNode != null )
            pr = new PrefixResolverDefault(nsNode);

         XPathParser parser = new XPathParser(null, null);
         cmp = new Compiler(null, null);

         parser.initXPath(cmp, xpath, pr);
         ex = cmp.compile(0);

         symbols = context.getSymbols();
         idxMgr = context.getIndexManager();
      }
      catch ( Exception e ) {
         throw new CompilationException("Error Compiling XPath Expression", e);
      }

      if ( ex == null )
         throw new CompilationException("Error Compiling XPath Expression");
   }

   public String getQueryStyle() {
      return XPathQueryResolver.STYLE_XPATH;
   }

   public ResultSet execute(Transaction tx) throws QueryException {
      try {
         Key[] keySet = keys;

         if ( keySet != null && keySet.length > KEYSET_LIMIT ) {
            /** @todo Add logic to do an indexed check on provided
                      keySets that are larger than a certain minimum */
         }

         if ( keySet == null && idxMgr != null ) {
            // Issue the query using Indexes
            try {
               Object obj = evaluate(tx, null, 0);
               if ( obj instanceof NamedKeys )
                  keySet = ((NamedKeys)obj).keys;
            }
            catch ( Exception e ) {
               e.printStackTrace(System.err);
            }
         }

         if ( keySet == null ) {
            // Fall back to a Collection scan
            keySet = context.listKeys(tx);
         }

         return new XPathResultSet(tx, context, this, keySet, pr, xpath);
      }
      catch ( Exception e ) {
         throw new ProcessingException("Error executing XPath query", e);
      }
   }

   private Key[] andKeys(List list) {
      if ( !list.isEmpty() ) {
         if ( list.size() > 1 ) {
            Key[][] keys = (Key[][])list.toArray(EmptyKeySet);
            return QueryEngine.andKeySets(keys);
         }
         else
            return (Key[])list.get(0);
      }
      else
         return null;
   }


   // Evaluation Methods

   /**
    * evaluate does a partial evaluation of the XPath in
    * order to determine the optimal indexes to prepare for
    * the query and retrieve the Document subset that will be
    * used for the actual XPath query.
    * <br><br>
    * This will return an instance of one of the following classes:
    * <pre>
    *    String    If the sub-expression resolves to a Node Name
    *    XNumber   If the sub-expression resolves to a Number
    *    XString   If the sub-expression resolves to a String
    *    XBoolean  If the sub-expression resolves to a Boolean
    *    NamedKeys If the sub-expression resolves to a Key set
    * </pre>
    *
    * @param owner The parent node name for this context
    * @param pos The position to start at (recursively called)
    * @return Some Object result
    * @throws Exception if an Exception occurs
    */
   private Object evaluate(Transaction tx, String owner, int pos) throws Exception {
      int op = cmp.getOp(pos);
      if ( op == -1 )
         return null;

      switch ( op ) {

         case OpCodes.OP_LOCATIONPATH:
            return evalLocationPath(tx, owner, pos);

         case OpCodes.OP_ARGUMENT:
         case OpCodes.OP_XPATH:
         case OpCodes.OP_PREDICATE:
            return evaluate(tx, owner, cmp.getFirstChildPos(pos));

         case OpCodes.OP_OR:
         case OpCodes.OP_AND:
            return evalSetComparison(tx, op, owner, pos);

         case OpCodes.OP_NOTEQUALS:
         case OpCodes.OP_EQUALS:
         case OpCodes.OP_LTE:
         case OpCodes.OP_LT:
         case OpCodes.OP_GTE:
         case OpCodes.OP_GT:
            return evalValComparison(tx, op, owner, pos);

         case OpCodes.OP_PLUS:
         case OpCodes.OP_MINUS:
         case OpCodes.OP_MULT:
         case OpCodes.OP_DIV:
         case OpCodes.OP_MOD:
         case OpCodes.OP_QUO:
            return evalMathOperation(tx, op, owner, pos);

         case OpCodes.OP_NEG:
         case OpCodes.OP_STRING:
         case OpCodes.OP_BOOL:
         case OpCodes.OP_NUMBER:
            return evalUnaryOperation(tx, op, owner, pos);

         case OpCodes.OP_UNION:
            break;

         case OpCodes.OP_VARIABLE:
            break;

         case OpCodes.OP_GROUP:
            return evaluate(tx, owner, cmp.getFirstChildPos(pos));

         case OpCodes.OP_EXTFUNCTION:
            break;

         case OpCodes.OP_FUNCTION:
            return evalFunction(tx, owner, pos);

         case OpCodes.FROM_ANCESTORS:
         case OpCodes.FROM_ANCESTORS_OR_SELF:
         case OpCodes.FROM_ATTRIBUTES:
         case OpCodes.FROM_CHILDREN:
         case OpCodes.FROM_DESCENDANTS:
         case OpCodes.FROM_DESCENDANTS_OR_SELF:
         case OpCodes.FROM_FOLLOWING:
         case OpCodes.FROM_FOLLOWING_SIBLINGS:
         case OpCodes.FROM_PARENT:
         case OpCodes.FROM_PRECEDING:
         case OpCodes.FROM_PRECEDING_SIBLINGS:
         case OpCodes.FROM_NAMESPACE:
         case OpCodes.FROM_SELF:
         case OpCodes.FROM_ROOT:
            return evalAxis(tx, op, owner, pos);

         case OpCodes.NODENAME:
         case OpCodes.OP_LITERAL:
         case OpCodes.OP_NUMBERLIT:
            return evalLiteral(owner, pos);

         case OpCodes.NODETYPE_TEXT:
         case OpCodes.NODETYPE_NODE:
            return owner;

         case OpCodes.NODETYPE_ANYELEMENT:
         case OpCodes.ELEMWILDCARD:
            return WILDCARD;

         case OpCodes.NODETYPE_ROOT:
         case OpCodes.NODETYPE_COMMENT:
         case OpCodes.NODETYPE_PI:
         case OpCodes.NODETYPE_FUNCTEST:
            break;

         default:
            System.err.println("Unknown: " + op);

      }
      return null;
   }

   private Object evalLocationPath(Transaction tx, String owner, int pos) throws Exception {
      int lp = cmp.getFirstChildPos(pos);
      List ks = new ArrayList(128);
      String name = null;
      boolean attr = false;
      while ( cmp.getOp(lp) != -1 ) {
         Object obj = evaluate(tx, owner, lp);
         if ( obj instanceof NamedKeys ) {
            NamedKeys nk = (NamedKeys)obj;
            if ( nk.name != null ) {
               attr = nk.attribute;
               if ( attr && name != null ) {
                  StringBuffer sb = new StringBuffer(32);
                  sb.append(name);
                  sb.append('@');
                  sb.append(nk.name);
                  name = sb.toString();
               }
               else
                  name = nk.name;
            }
            if ( nk.keys != null )
               ks.add(nk.keys);
            else if ( name != null ) {
               // Try to use a NameIndex to resolve the path component
               IndexPattern pattern = new IndexPattern(symbols, name, nsMap);
               Indexer idx = context.getIndexManager().getBestIndexer(Indexer.STYLE_NODENAME, pattern);
               if ( idx != null ) {
                  IndexMatch[] matches = idx.queryMatches(tx, new IndexQueryANY(pattern));
                  Key[] keys = QueryEngine.getUniqueKeys(matches);
                  ks.add(keys);
               }
            }
         }
         lp = cmp.getNextOpPos(lp);
      }
      return new NamedKeys(name, attr, andKeys(ks));
   }

   private Object evalSetComparison(Transaction tx, int op, String owner, int pos) throws Exception {
      int l = cmp.getFirstChildPos(pos);
      int r = cmp.getNextOpPos(l);
      Object left = evaluate(tx, owner, l);
      Object right = evaluate(tx, owner, r);

      NamedKeys nkl = null;
      if ( left instanceof NamedKeys )
         nkl =(NamedKeys)left;

      NamedKeys nkr = null;
      if ( right instanceof NamedKeys )
         nkr =(NamedKeys)right;

      if ( nkl != null && nkr != null && nkl.keys != null && nkr.keys != null ) {
         Key[][] keys = new Key[][]{nkl.keys, nkr.keys};
         if ( op == OpCodes.OP_OR )
            return new NamedKeys(null, false, QueryEngine.orKeySets(keys));
         else
            return new NamedKeys(null, false, QueryEngine.andKeySets(keys));
      }
      else if ( op == OpCodes.OP_AND ) {
         if ( nkl != null && nkl.keys != null )
            return new NamedKeys(null, false, nkl.keys);
         else if ( nkr != null && nkr.keys != null )
            return new NamedKeys(null, false, nkr.keys);
      }
      return null;
   }

   private Object evalValComparison(Transaction tx, int op, String owner, int pos) throws Exception {
      int l = cmp.getFirstChildPos(pos);
      int r = cmp.getNextOpPos(l);
      Object left = evaluate(tx, owner, l);
      Object right = evaluate(tx, owner, r);

      if ( (left instanceof XObject) && (right instanceof XObject) ) {
         switch ( op ) {
            case OpCodes.OP_NOTEQUALS:
               return new XBoolean(((XObject)left).notEquals((XObject)right));

            case OpCodes.OP_EQUALS:
               return new XBoolean(((XObject)left).equals((XObject)right));

            case OpCodes.OP_LTE:
               return new XBoolean(((XObject)left).lessThanOrEqual((XObject)right));

            case OpCodes.OP_LT:
               return new XBoolean(((XObject)left).lessThan((XObject)right));

            case OpCodes.OP_GTE:
               return new XBoolean(((XObject)left).greaterThanOrEqual((XObject)right));

            case OpCodes.OP_GT:
               return new XBoolean(((XObject)left).greaterThan((XObject)right));

            default:
               return null; // Won't happen
         }
      }
      else
         return queryComparison(tx, op, owner, left, right);
   }

   private strictfp Object evalMathOperation(Transaction tx, int op, String owner, int pos) throws Exception {
      int lc = cmp.getFirstChildPos(pos);
      int rc = cmp.getNextOpPos(lc);
      XObject left = (XObject)evaluate(tx, owner, lc);
      XObject right = (XObject)evaluate(tx, owner, rc);

      switch ( op ) {
         case OpCodes.OP_PLUS:
            return new XNumber(left.num() + right.num());

         case OpCodes.OP_MINUS:
            return new XNumber(left.num() - right.num());

         case OpCodes.OP_MULT:
            return new XNumber(left.num() * right.num());

         case OpCodes.OP_DIV:
            return new XNumber(left.num() / right.num());

         case OpCodes.OP_MOD:
            return new XNumber(left.num() % right.num());

         case OpCodes.OP_QUO:
            return new XNumber(left.num() / right.num());

         default:
            return null; // Won't happen
      }
   }

   private Object evalUnaryOperation(Transaction tx, int op, String owner, int pos) throws Exception {
      XObject val = (XObject)evaluate(tx, owner, cmp.getFirstChildPos(pos));
      switch ( op ) {
         case OpCodes.OP_NEG:
            return new XNumber(-val.num());

         case OpCodes.OP_STRING:
            return new XString(val.str());

         case OpCodes.OP_BOOL:
            return new XBoolean(val.bool());

         case OpCodes.OP_NUMBER:
            return new XNumber(val.num());

         default:
            return null; // Won't happen
      }
   }

   private Object evalFunction(Transaction tx, String owner, int pos) throws Exception {
      int idx = cmp.getFirstChildPos(pos);
      int id = cmp.getOp(idx);
      //int endFunc = pos + cmp.getOpMap()[pos+1]-1;
      int endFunc = pos + cmp.getOpMap().elementAt(pos+1)-1;

      List args = new ArrayList();
      int lp = idx + 1;
      while ( lp < endFunc ) {
         args.add(evaluate(tx, owner, lp));
         lp = cmp.getNextOpPos(lp);
      }

      switch ( id ) {
         case FUNC_BOOLEAN:
            return funcBoolean(args);

         case FUNC_CEILING:
            return funcCeiling(args);

         case FUNC_CONCAT:
            return funcConcat(args);

         case FUNC_CONTAINS:
            return funcContains(args);

         case FUNC_FALSE:
            return XBoolean.S_FALSE;

         case FUNC_FLOOR:
            return funcFloor(args);

         case FUNC_NORMALIZE_SPACE:
            return funcNormalizeSpace(args);

         case FUNC_NOT:
            return funcNot(args);

         case FUNC_NUMBER:
            return funcNumber(args);

         case FUNC_ROUND:
            return funcRound(args);

         case FUNC_STARTS_WITH:
            return funcStartsWith(tx, owner, args);

         case FUNC_STRING:
            return funcString(args);

         case FUNC_STRING_LENGTH:
            return funcStringLength(args);

         case FUNC_SUBSTRING:
            return funcSubstring(args);

         case FUNC_SUBSTRING_AFTER:
            return funcSubstringAfter(args);

         case FUNC_SUBSTRING_BEFORE:
            return funcSubstringBefore(args);

         case FUNC_TRANSLATE:
            return funcTranslate(args);

         case FUNC_TRUE:
            return XBoolean.S_TRUE;

         default:
            return null;
      }
   }

   private Object evalAxis(Transaction tx, int op, String owner, int pos) throws Exception {
      String nsURI = cmp.getStepNS(pos);
      owner = (String)evaluate(tx, owner, cmp.getFirstChildPosOfStep(pos));
      //owner = cmp.getStepLocalName(pos);

      if ( nsURI != null && nsMap != null ) {
         // We have to determine the prefix that was used
         // There has to be an easier way to do this with Xalan
         String pfx = null;
         Iterator i = nsMap.entrySet().iterator();
         while ( i.hasNext() ) {
            Map.Entry entry = (Map.Entry)i.next();
            String p = (String)entry.getKey();
            String u = (String)entry.getValue();
            if ( u.equals(nsURI) ) {
               pfx = p;
               break;
            }
         }
         if ( pfx != null ) {
            StringBuffer sb = new StringBuffer(32);
            sb.append(pfx);
            sb.append(':');
            sb.append(owner);
            owner = sb.toString();
         }
      }

      int rp = cmp.getFirstPredicateOpPos(pos);

      List ks = new ArrayList(128);
      while ( rp < pos + cmp.getOp(pos + 1) ) {
         Object obj = evaluate(tx, owner, rp);
         if ( obj instanceof NamedKeys ) {
            NamedKeys nk = (NamedKeys)obj;
            if ( nk.keys != null )
               ks.add(nk.keys);
         }
         rp = cmp.getNextOpPos(rp);
      }
      return new NamedKeys(owner, (op == OpCodes.FROM_ATTRIBUTES), andKeys(ks));
   }

   private Object evalLiteral(String owner, int pos) throws Exception {
      int idx = cmp.getOp(cmp.getFirstChildPos(pos));
      switch ( idx ) {
         case OpCodes.EMPTY:
            return owner;
         case OpCodes.ELEMWILDCARD:
            return WILDCARD;
         default:
            return cmp.getToken(idx);
      }
   }


   // XPath Functions

   private Object funcBoolean(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject ) {
            if ( ((XObject)o).bool() )
               return XBoolean.S_TRUE;
            else
               return XBoolean.S_FALSE;
         }
         else
            return o;
      }
      return null;
   }

   private Object funcCeiling(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XNumber(Math.ceil(((XObject)o).num()));
      }
      return null;
   }

   private Object funcConcat(List args) {
      StringBuffer sb = new StringBuffer();
      for ( int i = 0; i < args.size(); i++ ) {
         Object o = args.get(i);
         if ( o instanceof XObject )
            sb.append(((XObject)o).str());
      }
      return new XString(sb.toString());
   }

   private Object funcContains(List args) {
      if ( args.size() == 2 ) {
         Object o = args.get(0);
         Object s = args.get(1);
         if ( o instanceof XObject && s instanceof XObject ) {
            if ( ((XObject)o).str().indexOf(((XObject)s).str()) != -1 )
               return XBoolean.S_TRUE;
            else
               return XBoolean.S_FALSE;
         }
      }
      return null;
   }

   private Object funcFloor(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XNumber(Math.floor(((XObject)o).num()));
      }
      return null;
   }

   private Object funcNormalizeSpace(List args) {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XString(QueryEngine.normalizeString(((XObject)o).str()));
         else
            return o;
      }
      return null;
   }

   private Object funcNot(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject ) {
            if ( ((XObject)o).bool() )
               return XBoolean.S_FALSE;
            else
               return XBoolean.S_TRUE;
         }
      }
      return null;
   }

   private Object funcNumber(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XNumber(((XObject)o).num());
         else
            return o;
      }
      return null;
   }

   private Object funcRound(List args) throws Exception {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XNumber(Math.round(((XObject)o).num()));
      }
      return null;
   }

   private Object funcStartsWith(Transaction tx, String owner, List args) {
      if ( args.size() == 2 ) {
         Object o = args.get(0);
         Object s = args.get(1);

         if ( o instanceof XObject && s instanceof XObject ) {
            if ( ((XObject)o).str().startsWith(((XObject)s).str()) )
               return XBoolean.S_TRUE;
            else
               return XBoolean.S_FALSE;
         }
         else if ( o instanceof NamedKeys && s instanceof XObject ) {
            NamedKeys nk = (NamedKeys)o;
            String ps;
            if ( nk.attribute && nk.name.indexOf('@') == -1 )
               ps = owner + "@" + nk.name;
            else
               ps = nk.name;

            IndexPattern pattern = new IndexPattern(symbols, ps, nsMap);

            XObject obj = (XObject)s;
            Value val1 = new Value(obj.str());

            IndexQuery iq = new IndexQuerySW(pattern, val1);
            return queryIndexes(tx, nk, iq);
         }
      }
      return null;
   }

   private Object funcString(List args) {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XString(((XObject)o).str());
         else
            return o;
      }
      return null;
   }

   private Object funcStringLength(List args) {
      if ( args.size() == 1 ) {
         Object o = args.get(0);
         if ( o instanceof XObject )
            return new XNumber(((XObject)o).str().length());
      }
      return null;
   }

   private Object funcSubstring(List args) throws Exception {
      if ( args.size() == 2 || args.size() == 3 ) {
         Object o = args.get(0);
         Object pos = args.get(1);
         Object len = args.get(2);
         if ( o instanceof XObject && pos instanceof XObject && (len == null || len instanceof XObject) ) {
            int ipos = (int)((XObject)pos).num() - 1;
            if ( len != null ) {
               int ilen = (int)((XObject)len).num();
               return new XString(((XObject)o).str().substring(ipos, ipos + ilen));
            }
            else
               return new XString(((XObject)o).str().substring(ipos));
         }
      }
      return null;
   }

   private Object funcSubstringAfter(List args) {
      if ( args.size() == 2 ) {
         Object o = args.get(0);
         Object s = args.get(1);
         if ( o instanceof XObject && s instanceof XObject ) {
            String val = ((XObject)o).str();
            String sub = ((XObject)s).str();
            int i = val.indexOf(sub);
            if ( i == -1 )
               return new XString("");
            else
               return new XString(val.substring(i + sub.length()));
         }
      }
      return null;
   }

   private Object funcSubstringBefore(List args) {
      if ( args.size() == 2 ) {
         Object o = args.get(0);
         Object s = args.get(1);
         if ( o instanceof XObject && s instanceof XObject ) {
            String val = ((XObject)o).str();
            String sub = ((XObject)s).str();
            int i = val.indexOf(sub);
            if ( i == -1 )
               return new XString("");
            else
               return new XString(val.substring(0, i));
         }
      }
      return null;
   }

   private Object funcTranslate(List args) {
      if ( args.size() == 3 ) {
         Object o = args.get(0);
         Object c1 = args.get(1);
         Object c2 = args.get(2);
         if ( o instanceof XObject && c1 instanceof XObject && c2 instanceof XObject ) {
            char ch1 = ((XObject)c1).str().charAt(0);
            char ch2 = ((XObject)c2).str().charAt(0);
            return new XString(((XObject)o).str().replace(ch1, ch2));
         }
      }
      return null;
   }


   // The Actual Querying Methods

   /**
    * queryIndexes actually performs index-based querying on behalf of
    * the evaluation methods.
    *
    * @param nk The NamedKeys instance to use for matches
    * @param iq The actual IndexQuery to use for resolution
    * @param ps The pattern String to possibly use for index gen
    * @param objType The object type to possibly use for index gen
    * @return The resulting Keys (if any)
    */
   private Object queryIndexes(Transaction tx, NamedKeys nk, IndexQuery iq) {
      try {
         IndexPattern pattern = iq.getPattern();
         if ( pattern.isInvalid() )
            return null;

         Indexer idx = context.getIndexManager().getBestIndexer(Indexer.STYLE_NODEVALUE, pattern);
         if ( idx != null ) {
            IndexMatch[] matches = idx.queryMatches(tx, iq);
            Key[] keys = QueryEngine.getUniqueKeys(matches);
            return new NamedKeys(nk.name, nk.attribute, keys);
         }
      }
      catch ( Exception e ) {
         e.printStackTrace(System.err);
      }
      return null;
   }

   /**
    * queryComparison performs a comparison query use the operands that
    * are passed to it, and returns the resulting Keys.
    *
    * @param op The Operator
    * @param owner The Owner Node
    * @param left The left Operand
    * @param right The right Operand
    * @return The resulting Keys (if any)
    */
   private Object queryComparison(Transaction tx, int op, String owner, Object left, Object right) {
      if ( !((left instanceof NamedKeys) && (right instanceof XObject)
             || (left instanceof XObject) && (right instanceof NamedKeys)) )
         return null; // How'd we get here?

      op = OpMap[op - OpCodes.OP_NOTEQUALS];

      if ( left instanceof XObject ) {
         // Check if we have to switch the operation
         if ( op == IndexQuery.GT
              || op == IndexQuery.LT
              || op == IndexQuery.GTE
              || op == IndexQuery.LTE )
            op = -op;
         // Swap the operands
         Object tmp = left;
         left = right;
         right = tmp;
      }

      NamedKeys nk = (NamedKeys)left;
      XObject obj = (XObject)right;

      String ps;
      if ( nk.attribute && nk.name.indexOf('@') == -1 )
         ps = owner + "@" + nk.name;
      else
         ps = nk.name;

      IndexQuery iq;
      IndexPattern pattern = new IndexPattern(symbols, ps, nsMap);

      Value value = new Value(obj.str());

      switch ( op ) {
         case IndexQuery.NEQ:
            iq = new IndexQueryNEQ(pattern, value);
            break;

         case IndexQuery.EQ:
            iq = new IndexQueryEQ(pattern, value);
            break;

         case IndexQuery.LTE:
            iq = new IndexQueryLEQ(pattern, value);
            break;

         case IndexQuery.LT:
            iq = new IndexQueryLT(pattern, value);
            break;

         case IndexQuery.GTE:
            iq = new IndexQueryGEQ(pattern, value);
            break;

         case IndexQuery.GT:
            iq = new IndexQueryGT(pattern, value);
            break;

         default:
            iq = null; // Won't happen
      }

      return queryIndexes(tx, nk, iq);
   }
}



