package org.dbxml.core.query;

/*
 * dbXML License, Version 1.0
 *
 *
 * Copyright (c) 1999-2001 The dbXML Group, L.L.C.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by
 *        The dbXML Group (http://www.dbxml.com/)."
 *    Alternately, this acknowledgment may appear in the software
 *    itself, if and wherever such third-party acknowledgments normally
 *    appear.
 *
 * 4. The names "dbXML" and "The dbXML Group" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    info@dbxml.com.
 *
 * 5. Products derived from this software may not be called "dbXML",
 *    nor may "dbXML" appear in their name, without prior written
 *    permission of The dbXML Group.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE DBXML GROUP OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $Id: XPathQueryResolver.java,v 1.105 2001/08/11 00:31:57 tom Exp $
 */

import org.dbxml.core.*;
import org.dbxml.core.Collection;
import org.dbxml.core.data.*;
import org.dbxml.core.data.NodeSet;
import org.dbxml.core.indexer.*;
import org.dbxml.core.indexer.helpers.*;
import org.dbxml.server.*;
import org.dbxml.server.util.*;
import org.dbxml.xml.*;
import org.dbxml.xml.dom.*;

import org.w3c.dom.*;

import java.util.*;

import javax.xml.transform.*;

import org.apache.xpath.*;
import org.apache.xpath.compiler.*;
import org.apache.xpath.compiler.Compiler;
import org.apache.xml.utils.*;
import org.apache.xpath.objects.*;

/**
 * XPathQueryResolver
 */

public final class XPathQueryResolver extends SimpleConfigurable implements QueryResolver {
   private static final Key[] EmptyKeys = new Key[0];
   private static final Key[][] EmptyKeySet = new Key[0][0];
   private static final String WILDCARD = "*";
   private static final String THISNODE = ".";
   private static final String PARENTNODE = "..";

   private static final String AUTOINDEX = "autoindex";

   public static final String STYLE_XPATH = "XPath";

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

   // Maps XPath Functions To Internal IDs (These are Xalan IDs)
   public static final int FUNC_NOT = 11;
   public static final int FUNC_TRUE = 12;
   public static final int FUNC_FALSE = 13;
   public static final int FUNC_BOOLEAN = 14;
   public static final int FUNC_NUMBER = 15;
   public static final int FUNC_FLOOR = 16;
   public static final int FUNC_CEILING = 17;
   public static final int FUNC_ROUND = 18;
   public static final int FUNC_STRING = 20;
   public static final int FUNC_STARTS_WITH = 21;
   public static final int FUNC_CONTAINS = 22;
   public static final int FUNC_SUBSTRING_BEFORE = 23;
   public static final int FUNC_SUBSTRING_AFTER = 24;
   public static final int FUNC_NORMALIZE_SPACE = 25;
   public static final int FUNC_TRANSLATE = 26;
   public static final int FUNC_CONCAT = 27;
   public static final int FUNC_SUBSTRING = 29;
   public static final int FUNC_STRING_LENGTH = 30;

   private QueryEngine engine;
   private DefaultErrorHandler errorListener = new DefaultErrorHandler();
   private boolean autoIndex = false;

   public void setConfig(Configuration config) throws dbXMLException {
      super.setConfig(config);
      autoIndex = config.getBooleanAttribute(AUTOINDEX, autoIndex);
   }

   public String getQueryStyle() {
      return STYLE_XPATH;
   }

   public void setQueryEngine(QueryEngine engine) {
      this.engine = engine;
   }

   public Query compileQuery(Collection context, String query, NamespaceMap nsMap, Key[] keys) throws QueryException {
      return new XPathQuery(context, query, nsMap, keys);
   }
   
   public NodeSet query(Collection context, String query, NamespaceMap nsMap, Key[] keys) throws QueryException {
      XPathQuery xq = new XPathQuery(context, query, nsMap, keys);
      return xq.execute();
   }
   

   /**
    * XPathQuery
    */

   private class XPathQuery implements Query {
      public Collection context;
      public IndexManager idxMgr;
      public NamespaceMap nsMap;
      public PrefixResolver pr;
      public SymbolTable symbols;
      public String query;
      public Compiler cmp;
      public XPath xp;
      public Key[] keys;

      public XPathQuery(Collection context, String query, NamespaceMap nsMap, Key[] keys) throws QueryException {
         this.context = context;
         this.query = query;
         this.nsMap = nsMap;
         this.keys = keys;

         Expression ex = null;
         
         try {
            if ( nsMap != null ) {
               Node n = nsMap.getContextNode();
               pr = new PrefixResolverDefault(n);
            }
         
            XPathParser parser = new XPathParser(errorListener, null);
            cmp = new Compiler(errorListener, null);
            parser.initXPath(cmp, query, pr);
            ex = cmp.compile(0);
            
            symbols = context.getSymbols();
            idxMgr = context.getIndexManager();
         }
         catch ( Exception e ) {
            throw new CompilationException("Error Compiling XPath Expression");
         }
         if ( ex == null )
            throw new CompilationException("Error Compiling XPath Expression");
      }
      
      public String getQueryStyle() {
         return STYLE_XPATH;
      }

      public String getQueryString() {
         return query;
      }

      public Collection getQueryContext() {
         return context;
      }
      
      public NamespaceMap getNamespaceMap() {
         return nsMap;
      }
      
      public Key[] getKeySet() {
         return keys;
      }

      public NodeSet execute() throws QueryException {
         try {
            Key[] keySet = keys;

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

            if ( keySet == null ) {
               // Fall back to a Collection scan
               SortedSet set = new TreeSet();
               RecordSet rs = context.getFiler().getRecordSet();
               while ( rs.hasMoreRecords() )
                  set.add(rs.getNextKey());
               keySet = (Key[])set.toArray(EmptyKeys);
            }

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

      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
       */
      private Object evaluate(String owner, int pos) throws Exception {
         int op = cmp.getOp(pos);
         if ( op == -1 )
            return null;

         switch ( op ) {

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

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

            case OpCodes.OP_OR:
            case OpCodes.OP_AND:
               return evalSetComparison(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(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(op, owner, pos);

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

            case OpCodes.OP_UNION:
               break;

            case OpCodes.OP_VARIABLE:
               break;

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

            case OpCodes.OP_EXTFUNCTION:
               break;

            case OpCodes.OP_FUNCTION:
               return evalFunction(op, 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(op, owner, pos);

            case OpCodes.NODENAME:
            case OpCodes.OP_LITERAL:
            case OpCodes.OP_NUMBERLIT:
               return evalLiteral(op, 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:
               org.dbxml.Debug.println("Unknown: "+op);

         }
         return null;
      }

      private Object evalLocationPath(int op, String owner, int pos) throws Exception {
         int lp = cmp.getFirstChildPos(pos);
         List ks = new ArrayList();
         String name = null;
         boolean attr = false;
         while ( cmp.getOp(lp) != -1 ) {
            Object obj = evaluate(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(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(int op, String owner, int pos) throws Exception {
         int l = cmp.getFirstChildPos(pos);
         int r = cmp.getNextOpPos(l);
         Object left = evaluate(owner, l);
         Object right = evaluate(owner, r);

         NamedKeys nkl = left instanceof NamedKeys ? (NamedKeys)left : null;
         NamedKeys nkr = right instanceof NamedKeys ? (NamedKeys)right : null;
         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 nkl.keys;
               else if ( nkr != null && nkr.keys != null )
                  return nkr.keys;
            }
            return null;
         }
      }

      private Object evalValComparison(int op, String owner, int pos) throws Exception {
         int l = cmp.getFirstChildPos(pos);
         int r = cmp.getNextOpPos(l);
         Object left = evaluate(owner, l);
         Object right = evaluate(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(op, owner, left, right);
      }

      private strictfp Object evalMathOperation(int op, String owner, int pos) throws Exception {
         int lc = cmp.getFirstChildPos(pos);
         int rc = cmp.getNextOpPos(lc);
         XObject left = (XObject)evaluate(owner, lc);
         XObject right = (XObject)evaluate(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(int op, String owner, int pos) throws Exception {
         XObject val = (XObject)evaluate(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(int op, String owner, int pos) throws Exception {
         int idx = cmp.getFirstChildPos(pos);
         int id = cmp.getOp(idx);
         int endFunc = pos + cmp.getOpMap()[pos+1] - 1;

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

         switch ( id ) {
            case FUNC_BOOLEAN:
               return funcBoolean(owner, args);
            case FUNC_CEILING:
               return funcCeiling(owner, args);
            case FUNC_CONCAT:
               return funcConcat(owner, args);
            case FUNC_CONTAINS:
               return funcContains(owner, args);
            case FUNC_FALSE:
               return XBoolean.S_FALSE;
            case FUNC_FLOOR:
               return funcFloor(owner, args);
            case FUNC_NORMALIZE_SPACE:
               return funcNormalizeSpace(owner, args);
            case FUNC_NOT:
               return funcNot(owner, args);
            case FUNC_NUMBER:
               return funcNumber(owner, args);
            case FUNC_ROUND:
               return funcRound(owner, args);
            case FUNC_STARTS_WITH:
               return funcStartsWith(owner, args);
            case FUNC_STRING:
               return funcString(owner, args);
            case FUNC_STRING_LENGTH:
               return funcStringLength(owner, args);
            case FUNC_SUBSTRING:
               return funcSubstring(owner, args);
            case FUNC_SUBSTRING_AFTER:
               return funcSubstringAfter(owner, args);
            case FUNC_SUBSTRING_BEFORE:
               return funcSubstringBefore(owner, args);
            case FUNC_TRANSLATE:
               return funcTranslate(owner, args);
            case FUNC_TRUE:
               return XBoolean.S_TRUE;
            default:
               return null;
         }
      }

      private Object evalAxis(int op, String owner, int pos) throws Exception {
         String nsURI = cmp.getStepNS(pos);
         owner = (String)evaluate(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.keySet().iterator();
            while ( i.hasNext() ) {
               String p = (String)i.next();
               if ( nsMap.getNamespaceURI(p).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();
         while ( rp < pos+cmp.getOp(pos+1) ) {
            Object obj = evaluate(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(int op, 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(String owner, 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(String owner, 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(String owner, 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(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().indexOf(((XObject)s).str()) != -1 )
                  return XBoolean.S_TRUE;
               else
                  return XBoolean.S_FALSE;
            }
         }
         return null;
      }

      private Object funcFloor(String owner, 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(String owner, 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(String owner, 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(String owner, 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(String owner, 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(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(nk, iq, ps, obj.getType());
            }
         }
         return null;
      }

      private Object funcString(String owner, 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(String owner, 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(String owner, 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(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 ) {
               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(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 ) {
               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(String owner, 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(NamedKeys nk, IndexQuery iq, String ps, int objType) {
         try {
            IndexPattern pattern = iq.getPattern();

            Indexer idx = context.getIndexManager().getBestIndexer(Indexer.STYLE_NODEVALUE, pattern);
            if ( idx != null )
               return new NamedKeys(nk.name, nk.attribute, QueryEngine.getUniqueKeys(idx.queryMatches(iq)));
            else if ( autoIndex ) {
               // TODO: This has to *not* be hardcoded
               Element e = new DocumentImpl().createElement("index");
               e.setAttribute("class", "org.dbxml.core.indexer.ValueIndexer");
               e.setAttribute("name", "xp_"+ps);
               e.setAttribute("pattern", ps);

               // Set the type for the index
               String type = null;
               switch ( objType ) {
                  case XObject.CLASS_BOOLEAN: type = "boolean"; break;
                  case XObject.CLASS_NUMBER:  type = "double";  break;
                  case XObject.CLASS_STRING:
                     if ( ps.indexOf('@') != -1 )
                        type = "string";
                     else
                        type = "trimmed";
                     break;
               }
               if ( type != null )
                  e.setAttribute("type", type);

               idxMgr.create(new Configuration(e));
            }
         }
         catch ( Exception e ) {
            org.dbxml.Debug.printStackTrace(e);
         }
         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(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.GEQ
              || op == IndexQuery.LEQ )
               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);
         String 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.LEQ: iq = new IndexQueryLEQ(pattern, value); break;
            case IndexQuery.LT:  iq = new IndexQueryLT(pattern, value);  break;
            case IndexQuery.GEQ: iq = new IndexQueryGEQ(pattern, value); break;
            case IndexQuery.GT:  iq = new IndexQueryGT(pattern, value);  break;
            default:             iq = null; // Won't happen
         }

         return queryIndexes(nk, iq, ps, obj.getType());
      }
   }


   /**
    * NamedKeys
    */

   private class NamedKeys {
      public boolean attribute = false;
      public String name;
      public Key[] keys;

      public NamedKeys(String name, boolean attribute, Key[] keys) {
         this.name = name;
         this.attribute = attribute;
         this.keys = keys;
      }
   }
   

   /**
    * ResultSet
    */
   
   private class ResultSet implements NodeSet {
      public XPathContext xpc = new XPathContext();
      
      public Collection context;
      public String query;
      public ErrorListener errors;
      public PrefixResolver pr;
      public XPath xp;
      
      public Key[] keySet;
      public int keyPos = 0;
      public NodeList nl;
      public int nlPos = 0;
      public int nlSize = 0;
      public Node node;
            
      public ResultSet(Collection context, PrefixResolver pr, Key[] keySet, String query) {
//System.out.println("Query: "+query);
         this.context = context;
         this.pr = pr;
         this.keySet = keySet;
         this.query = query;
         
         errors = new ErrorListener() {
            public void fatalError(TransformerException te) {
               org.dbxml.Debug.println(te);
            }
            
            public void error(TransformerException te) {
               org.dbxml.Debug.println(te);
            }
            
            public void warning(TransformerException te) {
               org.dbxml.Debug.println(te);
            }
         };
         
         prepareNextNode();
      }
            
      private void prepareNextNode() {
         node = null;
         while ( keyPos < keySet.length ) {
            try {
//System.out.println("  Key: "+keySet[keyPos]);
               DBDocument d = (DBDocument)context.getDocument(keySet[keyPos++]);
               if ( d == null )
                  continue;
                         
               Node n = d.getDocumentElement();
               
               PrefixResolver pfx;
               if ( pr == null ) {
                  pfx = new PrefixResolverDefault(d.getDocumentElement());
                  xp = new XPath(query, null, pfx, XPath.SELECT, errors);
               }
               else {
                  pfx = pr;
                  if ( xp == null )
                     xp = new XPath(query, null, pfx, XPath.SELECT, errors);
               }

               nl = xp.execute(xpc, n, pfx).mutableNodeset();

               nlSize = nl.getLength();
               if ( nlSize == 0 )
                  continue;
               else {
                  nlPos = 1;
                  node = nl.item(0);
                  break;
               }
            }
            catch ( Exception e ) {
               org.dbxml.Debug.printStackTrace(e);
            }
         }
      }
      
      public boolean hasMoreNodes() {
         return node != null;
      }
   
      public Node getNextNode() {
         Node n = node;
         
         if ( nlPos < nlSize )
            node = nl.item(nlPos++);
         else
            prepareNextNode();

         return n;
      }
   }
}






