/* **************************************************************************

  $Archive: /njcl/src/com/novell/service/rfc1960/Rfc1960Parser.java $
  $Revision: 4 $
  $Modtime: 4/02/99 3:33p $
 
  Copyright (c) 1998 Novell, Inc.  All Rights Reserved.

  THIS WORK IS  SUBJECT  TO  U.S.  AND  INTERNATIONAL  COPYRIGHT  LAWS  AND
  TREATIES.   NO  PART  OF  THIS  WORK MAY BE  USED,  PRACTICED,  PERFORMED
  COPIED, DISTRIBUTED, REVISED, MODIFIED, TRANSLATED,  ABRIDGED, CONDENSED,
  EXPANDED,  COLLECTED,  COMPILED,  LINKED,  RECAST, TRANSFORMED OR ADAPTED
  WITHOUT THE PRIOR WRITTEN CONSENT OF NOVELL, INC. ANY USE OR EXPLOITATION
  OF THIS WORK WITHOUT AUTHORIZATION COULD SUBJECT THE PERPETRATOR TO
  CRIMINAL AND CIVIL LIABILITY.

****************************************************************************/

package com.novell.service.rfc1960;

import java.util.*;

/**@Internal
 * RFC1960 (LDAP) Search String Parser
 *
 * <p>This class takes a RFC1960 formated search string (passed into the
 * constructor) and breaks it into the components that the user of this class
 * will need to do his compares.  Each component of the search string has the
 * following items that the user is interested in;
 * </p>
 *    <i>Attribute Id</i>
 *    <i>operation</i>
 *    <i>compared</i>
 *    <i>example:           fileSize>=1024</i>
 *
 *
 * <p>The user should always call the isValid method right after
 * instantiation to determine if the search string was given to the
 * constructor was ok.  If this method returns false, no other methods in the
 * class should be used.</p>
 *
 * <p>Get Accessor methods are provided to return the Attribute Id and the
 * operation.  After the user does his compare, he will use the
 * setCompareResult (or eoSetCompareResult) set accessor to record his
 * results.  After a setCompareResult has been called for all components, the
 * user can then call the compared (or eoCompared) method to determine the
 * overall result of the search.
 * </p>
 */

/*
     <filter> ::= '(' <filtercomp> ')'
     <filtercomp> ::= <and> | <or> | <not> | <item>
     <and> ::= '&' <filterlist>
     <or> ::= '|' <filterlist>
     <not> ::= '!' <filter>      (this is to say, only one component)
     <filterlist> ::= <filter> | <filter> <filterlist>
     <item> ::= <simple> | <present> | <substring>
     <simple> ::= <attr> <filtertype> <value>
     <filtertype> ::= <equal> | <approx> | <greater> | <less>
     <equal> ::= '='
     <approx> ::= '~='
     <greater> ::= '>='
     <less> ::= '<='
     <present> ::= <attr> '=*'
     <substring> ::= <attr> '=' <initial> <any> <final>
     <initial> ::= NULL | <value>
     <any> ::= '*' <starval>
     <starval> ::= NULL | <value> '*' <starval>
     <final> ::= NULL | <value>

   <attr> is a string representing an AttributeType, and has the format
   defined in [1].  <value> is a string representing an AttributeValue,
   or part of one, and has the form defined in [2].  If a <value> must
   contain one of the characters '*' or '(' or ')', these characters
   should be escaped by preceding them with the backslash '\' character.

   Note that although both the <substring> and <present> productions can
   produce the 'attr=*' construct, this construct is used only to denote
   a presence filter.

     (cn=Babs Jensen)
     (!(cn=Tim Howes))
     (&(objectClass=Person)(|(sn=Jensen)(cn=Babs J*)))
     (o=univ*of*mich*)

*/

public class Rfc1960Parser implements Enumeration
{
   private String searchString;
   private int ssLength;
   private int ssIndex = -1;

   private Vector components = new Vector();
   private Vector operations = new Vector();
   private Vector stack = new Vector();

   private int stackIndex = 0;
   private int lastStackIndex = 0;
   private int currentLevel = 0;
   private  boolean runningResult;

   private int enumerationIndex = 0;
   private boolean compareResultSet = true;    // enable the first next ok

   /**
    * Rfc1960Parser Constructor
    *
    * <p>This constructor expects a RFC1960 formated search string as input.
    * It will then attempt to parse this string into components that the user
    * will need to do his searches.  The constructor will throw a
    * java.lang.IllegalArgumentException if the string can not be parsed.
    * </p>
    *
    * @param ss                  The RFC1960 Search String
    *
    * @exception java.lang.IllegalArgumentException
    */

   public Rfc1960Parser(String ss)
   {
      if (ss.length () == 0)
      {
         throw new IllegalArgumentException (ss);
      }
      searchString = new String(ss);
      ssLength = searchString.length();

      nextSSCharacter(true, true);

      Operation op = new Operation(' ', 0);
      operations.addElement(op);
      stack.addElement(op);

      do
      {
         /*
            if the <filter> has only one <filtercomp> which is an <item> you can
            only have one component.  If this level is a '!' you can only
            have zero or one component.
         */
         op = (Operation) stack.elementAt(currentLevel);
         if (op.op == ' ' || op.op == '!')
         {
            if (op.count > 0)
            {
               throw new IllegalArgumentException(
                           searchString.substring(ssIndex, ssLength));
            }
         }

         // look for beginning of the filter
         if (searchString.charAt(ssIndex) == '(')
            parseFilterComp();
         else
         {
            throw new IllegalArgumentException(
                        searchString.substring(ssIndex, ssLength));
         }
      }while(ssIndex < ssLength);
      if (currentLevel != 0)
         throw new IllegalArgumentException(
                     searchString.substring(ssIndex, ssLength));
   }

   /**
    * reports the current enumeration interfaces status
    *
    * <p>Returns true if the enumeration interfaces next method will return a
    * SearchStringComponent.  Returns false if the enumeration interfaces
    * next method will throw a NoMoreElementsException
    * </p>
    *
    * @return                    True if more SearchStringComponents are
    *                            available.  Returns false otherwise.
    */

   public boolean hasMoreElements()
   {
      if (enumerationIndex == -1)
         return false;

      return true;
   }

   /**
    * Returns the next SearchStringComponent that the user should compare
    *
    * <p>The user should call this method to obtain the SearchStringComponent
    * to compare, do the compare, and then call the setCompareResult method
    * before calling this method again.  This method can throw a
    * NoMoreElements exception, and will throw an IllegalStateException if
    * the setCompareResult method is not called inbetween interations.
    * </p>
    *
    * @return                    SearchStringComponent that should be
    *                            compared next.
    *
    * @exception java.util.NoMoreElementsException
    * @exception java.lang.IllegalStateException
    */

   public SearchStringComponent next()
   {
      if (enumerationIndex == -1)
         throw new java.util.NoSuchElementException();

      if (!compareResultSet)
         throw new IllegalStateException();
//            "Rfc1960Parser.setCompareResult must be called between iterations");

      compareResultSet = false;
      return (SearchStringComponent) components.elementAt(enumerationIndex);
   }

   /**
    * Returns the next SearchStringComponent as an object
    *
    * <p>Simply calls the next method, and returns the SearchStringComponent
    * as an Object.
    * </p>
    *
    * @return                    SearchStringComponent that should be
    *                            compared next.
    *
    * @exception java.util.NoMoreElementsException
    * @exception java.lang.IllegalStateException
    */

   public Object nextElement()
   {
      return next();
   }

   /**
    * Returns the number of components.
    *
    * <p>This method returns the number of components parsed from the RFC1960
    * search string used during construction of the object.
    * </p>
    *
    * @return                    The number of components available
    *
    */

   /**
    * Returns an enumeration of all the components
    *
    * <p>This method returns an enumeration of all the components that where
    * parsed from the search string for this object.  This enumeration will
    * return the components in the same order as they are found in the
    * original search string (from left to right).
    * </p>
    *
    * @return                    SSComponentEnumerator
    */

   public SSComponentEnumerator getComponents()
   {
      return new SSComponentEnumerator(components);
   }

   public int count()
   {
      return components.size();
   }

   /**
    * Returns the original Search String
    *
    * <p>This method returns the search string that has handed into the
    * constructor.
    * </p>
    *
    * @return                    The original search string
    *
    */

   public String getSearchString()
   {
      return searchString;
   }

   /**
    * Sets the compare result and returns the next index to compare
    *
    * <p>This method sets the compare result into the requested component.
    * it then evaluates the effect of this result on the overall RFC1960
    * search string. If the value being set into the requested component is
    * known to determine the overall result of the compare, this method will
    * flag the enumeration interface that will are done (don't bother
    * comparing any more).  If this can not yet be determined, this method
    * will setup the next enumeration interface index of the next component
    * that will be returned for you to compare (unneeded compares are
    * skipped, so values returned may not be contiguous).
    * </p>
    * <p>For example, if the first operation is a &, and we get a false,
    * there is no need in checking any further, the overall operation has
    * failed.  If the current operation is a |, and we get a true, all
    * remaining compares at this level are no longer needed and this method
    * will return the index of the next needed component to test (or -1 if we
    * are at the outer most level).
    * </p>
    * <p>You must call the compared method to obtain the overall compared
    * results after enumerating through the sequence.
    * </p>
    *
    * @param component           The component to set the compare 
    *                            results for.
    *
    * @param compared            results of users compare.  This value
    *                            should be true if the corrisponding 
    *                            components operation was true, it should be
    *                            false otherwise.
    *
    */

   public void setCompareResult(SearchStringComponent component, boolean compared)
   {
      component.compared = compared;

      enumerationIndex = evaluateResults(component.getOffset());
      compareResultSet = true;
   }

   /**
    * Returns the overall compare results based on early out
    *
    * <p>This method is only valid when the user has followed the proper
    * sequence of compares as returned by the enumeration interface.
    * This method simply returns the current running state of the compares
    * that have been set by setCompareResult.  Remember,
    * </p>
    *
    * @return                    The overall compare results
    *
    */

   public boolean compared()
   {
      return runningResult;
   }

/* *************************************************************************/

   private void parseFilterComp()
   {
/*
   (& (c1) (| (c2) (c3) ) (! (& (c4) (| (c5) (c6) ) ) ) )

   This is a complex example that was used to model this parser.  The c1..c6
   elements are referred to as a component in this program.  Each component
   is the equivalent of a RFC1960 <item>.  This program also refers to
   RFC1960 <filtercomp>'s that are not an <item> as an operation.

   As a component is found, it is stored in the components vector as a
   Component class (see end of this file).  Since the evaluation of each
   component is not known at this time the operations are also stored in the
   operations vector.  As each component is found and stored, the current
   index of the last operation found is also stored with the component.

   As the end of each component is found, if it is immediately followed with
   closing parentheses for outstanding operations, these closing parentheses
   are counted and stored with the component.  This allows the operation
   vector to be used as a stack at a later time.

   Using the above example:

                   (starts @ -1)                     Current
      Component      pushLevel      popCount        Operation
         c1             0              0              and
         c2             1              0              or
         c3             1              1              or
         c4             3              0              and
         c5             4              0              or
         c6             4              4              or

   Notice that in this example, the not operation will only be found during
   evaluation when the c6 popCounts are processed.
*/

      // <filtercomp> ::= <and> | <or> | <not> | <item>

      char c = nextSSCharacter(true, true);
      if (c == '&' || c == '|' || c== '!')
      {
         // we will have multiple filter/filterlists, store this operation
         Operation op = new Operation(c, 0);
         operations.addElement(op);
         stack.addElement(op);
         ++stackIndex;
         ++currentLevel;

         c = nextSSCharacter(true, true);
         if (c != '(')
         {
            throw new IllegalArgumentException(
                        searchString.substring(ssIndex, ssLength));
         }
         c = nextSSCharacter(true, true);
      }

      if (c == '&' || c == '|' || c== '!')
      {
         // it's a new filter, backup and handle afresh
         ssIndex -= 2;
         c = nextSSCharacter(true, true);
         return;
      }

      Operation op = (Operation)operations.elementAt(currentLevel);
      ++op.count;

      int componentStart = ssIndex;
      boolean stripClosing = false;
      int popCount = 0;
      SearchStringComponent comp = null;

      while (ssIndex < ssLength)
      {
         if (c == ')')
         {
            if (!stripClosing)
            {
               // this is the first closing parentheses
               try
               {
                  comp = new SearchStringComponent(
                              searchString.substring(componentStart, ssIndex),
                              stackIndex - lastStackIndex,
                              components.size());

               } catch (IllegalArgumentException e)
               {
                  throw new IllegalArgumentException(
                              searchString.substring(ssIndex, ssLength));
               }
               lastStackIndex = stackIndex;
               components.addElement(comp);
               stripClosing = true;
            }else
            {
               ++comp.popCount;
               stack.removeElementAt(currentLevel);
               --currentLevel;
             }

            c = nextSSCharacter(true, false);
            continue;
         }
         if (stripClosing)
            return;
         c = nextSSCharacter(true, false);
      }
      if (!stripClosing)
      {
         throw new IllegalArgumentException(
                     searchString.substring(ssIndex, ssLength));
      }
      return ;
   }

   private int popStack(SearchStringComponent comp, int index)
   {
      /*
         pop the stack back out, and keep the runningResult up to date
         as it backs out.  The only thing you need to watch for is nots
         just let and/or's runningResult float out.
      */
      Operation op = null;
      for (int i=0; i < comp.popCount; i++)
      {
         op = (Operation)stack.elementAt(currentLevel);
         if (op.op == '!')
         {
            if (runningResult)
               runningResult = false;
            else
               runningResult = true;
         }
         stack.removeElementAt(currentLevel--);
      }
      /*
         now you've carried your result out to the proper outer level  See
         if the result floated out to this level, can once again do another
         early-out
      */
      op = (Operation)stack.elementAt(currentLevel);
      switch(op.op)
      {
         case '&':
            if (!runningResult)
               index = skipRestOfLevel(index);
            break;
         case '|':
            if (runningResult)
               index = skipRestOfLevel(index);
            break;
         case '!':
               index = skipRestOfLevel(index);
            break;
      }

      return index;
   }

   private int skipRestOfLevel(int index)
   {
      /*
         This methods main job is to find the first popCount that results in
         currentLevel == currentLevel - 1.  It will step down through all of
         the components, maintaining the stack (pushes and pops), until it
         finds the appropriate stack level.

         The first stack element is a noop.  This is a special case for the
         filter that only contains a single component - "(a=b)".  Because of
         this, there will never be a component with a popCount that would
         leave you at currentLevel == 0.  When you hit currentLevel == 1,
         you are done.
      */

      if (currentLevel == 1)
         return -1;

      int neededLevel = currentLevel - 1;

      while(index < components.size())
      {
         SearchStringComponent comp = (SearchStringComponent)
                                          components.elementAt(++index);

         // keep the stack straight
         for (int i=0; i < comp.pushCount; i++)
         {
            stack.addElement(operations.elementAt(stackIndex++));
            ++currentLevel;
         }

         if (comp.popCount > 0)
         {
            index = popStack(comp, index);
            if (currentLevel <= neededLevel)
               break;
         }
      }

      if (index >= components.size())
         return -1;
      return index;
   }

   private int evaluateResults(int index)
   {
      /*
         First, setup an operations stack to the requested index's level.
         Simply push and pop the counts on each component until we reach
         our component (but don't pop the requested component yet)
      */
      stack.removeAllElements();
      stack.addElement(operations.elementAt(0));
      stackIndex = 1;
      currentLevel = 0;
      SearchStringComponent comp = null;

      for (int i=0; i <= index; i++)
      {
         comp = (SearchStringComponent) components.elementAt(i);
         for (int j=0; j < comp.pushCount; j++)
         {
            stack.addElement(operations.elementAt(stackIndex++));
            ++currentLevel;
         }
         if (i != index) // don't pop the requested components count
         {
            for (int j=0; j < comp.popCount; j++)
               stack.removeElementAt(currentLevel--);
         }
      }

      /*
         Get the operation that is active for this component, then based on
         the compared flag of the component, see if this operation level can
         be determined at this point, if it can, skip the rest of the
         components that are at this stack level.  Otherwise return the next
         index number in the sequence (index++);
      */

      Operation currentOp = (Operation)stack.elementAt(currentLevel);

      boolean skipLevel = true;
      switch (currentOp.op)
      {
         case '&':
            // if true, we must keep going, if false, skip the rest of level
            if (comp.compared)
            {
               runningResult = true;
               skipLevel = false;
            }else
               runningResult = false;
            break;
         case '|':
            // if false, we must keep going, if true, skip the rest of level
            if (!comp.compared)
            {
               runningResult = false;
               skipLevel = false;
            }else
               runningResult = true;
            break;
         case '!':
            // if false, we must keep going, if true, skip the rest of level
            if (!comp.compared)
            {
               runningResult = false;
               skipLevel = false;
            }else
               runningResult = true;
            break;
         case ' ':
            // you are done, there was only one component
            runningResult = comp.compared;
            skipLevel = false;
            index = -1;
            break;
      }

      /*
         Not filters can exist that simply contain other filters,
         resulting in no more components, but still having an outstanding
         stack, pop the stack, to pick up any of these nots.  Since popStack
         will handle the skipLevel as needed, cancel it if it's been set here.
      */

      if (comp.popCount > 0)
      {
         index = popStack(comp, index);
         skipLevel = false;
      }

      if (skipLevel)
         index = skipRestOfLevel(index);

      /*
         Set the index to the next component that will need to be evaluated.
      */
      if (index != -1)
      {
         ++index;
         if (index >= components.size())
            index = -1;
      }
      return index;
   }


   private char nextSSCharacter(boolean eatWhiteSpace, boolean invalidate)
   {
      char nextChar;

      do
      {
         if (++ssIndex >= ssLength)
         {
            if (invalidate)
               throw new IllegalArgumentException(
                           searchString.substring(ssIndex, ssLength));
            return ' ';
         }
         nextChar = searchString.charAt(ssIndex);
         if (!eatWhiteSpace)
            return nextChar;
      }while(nextChar == ' ' || nextChar == '\t');
      return nextChar;
   }
/*
   protected void debug(int index)
   {
      SearchStringComponent comp = (SearchStringComponent) components.elementAt(index);
      System.out.print("[" + index + "] " + comp.getAttributeId());
      switch (comp.getOperationType())
      {
         case SearchStringComponent.EQUALS:
            System.out.print("=");
            break;
         case SearchStringComponent.APPROXIMATE:
            System.out.print("~=");
            break;
         case SearchStringComponent.GREATER_OR_EQUAL:
            System.out.print(">=");
            break;
         case SearchStringComponent.LESS_OR_EQUAL:
            System.out.print("<=");
            break;
      }
      System.out.println(
         comp.getOperand() + ".\t" +
         comp.pushCount + " " + comp.popCount + "\t(" +
         comp.getComponent() + ", " + comp.getOperation() + ") " +
         comp.operandReplacement());
   }

/* *************************************************************************

   public final static void main(String[] argv)
   {
      Rfc1960Parser ssp = new Rfc1960Parser(new String(
//         "(& (a = a) (| (b ~= b )(c >= c)  ) (! (& (d <= d) (| (e = ?)(f = f))) ))"));
//       "(&(!(&(a = a)(|(b ~= b)(c >= c))(d <= d)))(e = e)(f = f))"));
//         "(a=a)(b=b)"));
//         "(!(a=a)(b=b))"));
//         "(!(!(a=a)))"));
//         "(a=a)"));
//         "(a=?)"));
            "(! (& (a=a) (b<=b) (| (c>=c) (d~=d) ) (e=*) (f=*text*more*) ) )"));

      boolean[] compares =
      {
         false,
         true,
         true,
         false,
         true,
         false
      };

      int count = ssp.count();
      System.out.println(ssp.getSearchString());
      for (int i=0; i < count; i++)
      {
         ssp.debug(i);
      }

      while (ssp.hasMoreElements())
      {
         SearchStringComponent ssc = ssp.next();
         ssp.setCompareResult(ssc, compares[ssc.getOffset()]);
         System.out.println(
            "in[" + ssc.getOffset() + "]: " + compares[ssc.getOffset()]);
      }
      System.out.println("result: " + ssp.compared());
   }
*/
}

class Operation
{
   protected char op;      // '&' or '|' or '!' or ' '
   protected int count;    // number of components at this level
   protected boolean result;

   protected Operation(char op, int count)
   {
      this.op = op;
      this.count = count;
      result = false;
   }
}

