parser.java

OSGI 的 源码实现,采用JAVA书写

/*
 * Oscar - An implementation of the OSGi framework.
 * Copyright (c) 2004, Richard S. Hall
 * All rights reserved.
 *  
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *  
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * 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.
 *   * Neither the name of the ungoverned.org nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *  
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS 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 COPYRIGHT
 * OWNER OR 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.
 * 
 * Contact: Richard S. Hall ([e-mail])
 * Contributor(s):
 * Dennis Heimbigner
 * Humberto Cervantes
 *
**/
package org.ungoverned.oscar.ldap;

import java.io.IOException;
import java.io.PrintStream;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class Parser
{
    //
    // Parser contants.
    //

    // End of file.
    public static final int EOF = -1;

    // Special characters in parse
    public static final char LPAREN = '(';
    public static final char RPAREN = ')';
    public static final char STAR = '*';

    // Define the list of legal leading and trailing
    // characters in an attribute name.
    public static final String ATTRIBUTECHARS0 =
        ".abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
    // Define the list of legal internal characters in an attribute name.
    public static final String ATTRIBUTECHARS1 =
        ".abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_ ";

    // Define an enum for substring procedure
    public static final int SIMPLE = 0;
    public static final int PRESENT = 1;
    public static final int SUBSTRING = 2;

    // different from =|>|<|~
    public static final int NOOP = 0;

    // Comparison operators.
    public static final int EQUAL = 0;
    public static final int GREATER_EQUAL = 1;
    public static final int LESS_EQUAL = 2;
    public static final int APPROX = 3;

    // Criteria in % to accept something as approximate.
    public static final int APPROX_CRITERIA = 10;

    // Flag indicating presense of BigInteger/Decimal.
    private static boolean m_hasBigNumbers = false;

    static 
    {
        try
        {
            Class.forName("java.math.BigDecimal");
            m_hasBigNumbers = true;
        }
        catch (Exception ex)
        {
            // Ignore.
        }
    }
    //
    // Instance variables.
    //

    private LdapLexer lexer = null;
    private List program;

    public Parser()
    {
        reset();
    }

    public Parser(LdapLexer l)
    {
        reset(l);
    }

    public void reset()
    {
        lexer = null;
        if (program == null)
        {
            program = new ArrayList();
        }
        program.clear();
    }

    public void reset(LdapLexer l)
    {
        reset();
        lexer = l;
    }

    public Object[] getProgram()
    {
        return program.toArray(new Object[program.size()]);
    }

    // Define the recursive descent procedures

    /*
    <start>::= <filter> <EOF>
    */
    public boolean start() throws ParseException, IOException
    {
        boolean ok = filter();
        if (!ok)
        {
            return ok;
        }
        int ch = lexer.get();
        if (ch != EOF)
        {
            throw new ParseException(
                "expected <EOF>; found '" + ((char) ch) + "'");
        }
        return ok;
    }

    /*
    <filter> ::= '(' <filtercomp> ')'
     */
    boolean filter() throws ParseException, IOException
    {
        debug("filter");
        if (lexer.peeknw() != LPAREN)
        {
            return false;
        }
        lexer.get();
        if (!filtercomp())
        {
            throw new ParseException("expected filtercomp");
        }
        if (lexer.getnw() != RPAREN)
        {
            throw new ParseException("expected )");
        }
        return true;
    }

    /*
    <filtercomp> ::= <and> | <or> | <not> | <item>
    <and> ::= '&' <filterlist>
    <or> ::= '|' <filterlist>
    <not> ::= '!' <filter>
    */
    boolean filtercomp() throws ParseException, IOException
    {
        debug("filtercomp");
        int c = lexer.peeknw();
        switch (c)
        {
            case '&' :
            case '|' :
                lexer.get();
                int cnt = filterlist();
                if (cnt == 0)
                {
                    return false;
                }
                // Code: [And|Or](cnt)
                program.add(
                    c == '&'
                        ? (Operator) new AndOperator(cnt)
                        : (Operator) new OrOperator(cnt));
                return true;
            case '!' :
                lexer.get();
                if (!filter())
                {
                    return false;
                }
                // Code: Not()
                program.add(new NotOperator());
                return true;
            case EOF :
                return false;
            default :
                // check for key
                if (ATTRIBUTECHARS0.indexOf(c) <= 0)
                {
                    return false;
                }
                boolean b = item();
                return b;
        }
    }

    /*
    <filterlist> ::= <filter> | <filter> <filterlist>
    */
    int filterlist() throws ParseException, IOException
    {
        debug("filterlist");
        int cnt = 0;
        if (filter())
        {
            do
            {
                cnt++;
            }
            while (filter());
        }
        return (cnt);
    }

    /*
    <item> ::= <simple> | <present> | <substring>
    <simple> ::= <attr> <filtertype> <value>
    <filtertype> ::= <equal> | <approx> | <greater> | <less>
    <present> ::= <attr> '=*'
    <substring> ::= <attr> '=' <initial> <any> <final>
    */
    boolean item() throws ParseException, IOException
    {
        debug("item");

        StringBuffer attr = new StringBuffer();
        if (!attribute(attr))
        {
            return false;
        }

        lexer.skipwhitespace(); // assume allowable before equal operator
        // note: I treat the =* case as = followed by a special substring
        int op = equalop();
        if (op == NOOP)
        {
            String oplist = "=|~=|>=|<=";
            throw new ParseException("expected " + oplist);
        }
        ArrayList pieces = new ArrayList();
        int kind = substring(pieces);
        // Get some of the illegal cases out of the way
        if (op != '=' && kind != SIMPLE)
        {
            // We assume that only the = operator can work
            // with right sides containing stars.  If not correct
            // then this code must change.
            throw new ParseException("expected value|substring|*");
        }

        switch (kind)
        {
            case SIMPLE :
                // Code: Push(attr); Constant(pieces.get(0)); <operator>();
                program.add(new PushOperator(attr.toString()));
                program.add(new ConstOperator(pieces.get(0)));
                switch (op)
                {
                    case '<' :
                        program.add(new LessEqualOperator());
                        break;
                    case '>' :
                        program.add(new GreaterEqualOperator());
                        break;
                    case '~' :
                        program.add(new ApproxOperator());
                        break;
                    case '=' :
                    default :
                        program.add(new EqualOperator());
                }
                break;
            case PRESENT :
                // Code: Present(attr);
                program.add(new PresentOperator(attr.toString()));
                break;
            case SUBSTRING :
                generateSubStringCode(attr.toString(), pieces);
                break;
            default :
                throw new ParseException("expected value|substring|*");
        }
        return true;
    }

    // Generating code for substring right side is mildly
    // complicated.

    void generateSubStringCode(String attr, ArrayList pieces)
    {
        // Code: Push(attr)
        program.add(new PushOperator(attr.toString()));

        // Convert the pieces arraylist to a String[]
        String[] list =
            (String[]) pieces.toArray(new String[pieces.size()]);

        // Code: SubString(list)
        program.add(new SubStringOperator(list));
    }

    /*
    <attr> is a string representing an attributte,
    or key, in the properties
    objects of the registered services. Attribute names are not case
    sensitive; that is cn and CN both refer to the same attribute.
    Attribute names may have embedded spaces, but not leading or
    trailing spaces.
    */
    boolean attribute(StringBuffer buf) throws ParseException, IOException
    {
        debug("attribute");
        lexer.skipwhitespace();
        buf.setLength(0);
        int c = lexer.peek(); // need to make sure there
        // is at least one KEYCHAR
        if (c == EOF)
        {
            return false;
        }
        if (ATTRIBUTECHARS0.indexOf(c) < 0)
        {
            return false;
        }

        do
        {
            buf.append((char) lexer.get());
        }
        while (ATTRIBUTECHARS1.indexOf(lexer.peek()) >= 0);

        // The above may have accumulated trailing blanks that must be removed
        int i = buf.length() - 1;
        while (i > 0 && buf.charAt(i) == ' ')
        {
            i--;
        }
        buf.setLength(i + 1);
        return true;
    }

    /*
       <equal> ::= '='
       <approx> ::= '~='
       <greater> ::= '>='
       <less> ::= '<='
       <present> ::= <attr> '=*'
    */
    int equalop() throws ParseException, IOException
    {
        debug("equalop");
        lexer.skipwhitespace();
        int op = lexer.peek();
        switch (op)
        {
            case '=' :
                lexer.get();
                break;
            case '~' :
            case '<' :
            case '>' :
                // skip main operator char
                int c = lexer.get();
                // make sure that the next char is '='
                c = lexer.get();
                if (c != '=')
                {
                    throw new ParseException("expected ~=|>=|<=");
                }
                break;
            default :
                op = NOOP;
        }
        return op;
    }

    /*
    <substring> ::= <attr> '=' <initial> <any> <final>
    <initial> ::= NULL | <value>
    <any> ::= '*' <starval>
    <starval> ::= NULL | <value> '*' <starval>
    <final> ::= NULL | <value>
    <value> ::= ...
    */
    /*
    This procedure handles all cases on right side of an item
    */
    int substring(ArrayList pieces) throws ParseException, IOException
    {
        debug("substring");

        pieces.clear();
        StringBuffer ss = new StringBuffer();
        //        int kind = SIMPLE; // assume until proven otherwise
        boolean wasStar = false; // indicates last piece was a star
        boolean leftstar = false; // track if the initial piece is a star