Subversion Repositories openrisc

/* gnu/regexp/RETokenRepeated.java

   Copyright (C) 2006 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 2, or (at your option)

any later version.

GNU Classpath 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 GNU Classpath; see the file COPYING.  If not, write to the

Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301 USA.

Linking this library statically or dynamically with other modules is

making a combined work based on this library.  Thus, the terms and

conditions of the GNU General Public License cover the whole

combination.

As a special exception, the copyright holders of this library give you

permission to link this library with independent modules to produce an

executable, regardless of the license terms of these independent

modules, and to copy and distribute the resulting executable under

terms of your choice, provided that you also meet, for each linked

independent module, the terms and conditions of the license of that

module.  An independent module is a module which is not derived from

or based on this library.  If you modify this library, you may extend

this exception to your version of the library, but you are not

obligated to do so.  If you do not wish to do so, delete this

exception statement from your version. */

package gnu.java.util.regex;

import gnu.java.lang.CPStringBuilder;

import java.util.ArrayDeque;

import java.util.Deque;

final class RETokenRepeated extends REToken

{

  private REToken token;

  private int min, max;

  private boolean stingy;

  private boolean possessive;

  private int tokenFixedLength;

    RETokenRepeated (int subIndex, REToken token, int min, int max)

  {

    super (subIndex);

    this.token = token;

    this.min = min;

    this.max = max;

    if (token.returnsFixedLengthMatches ())

      {

        tokenFixedLength = token.getMaximumLength ();

      }

    else

      {

        tokenFixedLength = -1;

      }

  }

    /** Sets the minimal matching mode to true. */

  void makeStingy ()

  {

    stingy = true;

  }

    /** Queries if this token has minimal matching enabled. */

  boolean isStingy ()

  {

    return stingy;

  }

    /** Sets possessive matching mode to true. */

  void makePossessive ()

  {

    possessive = true;

  }

    /** Queries if this token has possessive matching enabled. */

  boolean isPossessive ()

  {

    return possessive;

  }

    /**

     * The minimum length of a repeated token is the minimum length

     * of the token multiplied by the minimum number of times it must

     * match.

     */

  int getMinimumLength ()

  {

    return (min * token.getMinimumLength ());

  }

  int getMaximumLength ()

  {

    if (max == Integer.MAX_VALUE)

      return Integer.MAX_VALUE;

    int tmax = token.getMaximumLength ();

    if (tmax == Integer.MAX_VALUE)

      return tmax;

    return (max * tmax);

  }

  // The comment "MUST make a clone" below means that some tests

  // failed without doing clone(),

  private static class DoablesFinder

  {

    private REToken tk;

    private CharIndexed input;

    private REMatch rematch;

    private boolean findFirst;

    private DoablesFinder (REToken tk, CharIndexed input, REMatch mymatch)

    {

      this.tk = tk;

      this.input = input;

      this.rematch = (REMatch) mymatch.clone ();        // MUST make a clone

      this.rematch.backtrackStack = new BacktrackStack ();

      findFirst = true;

    }

    private REMatch find ()

    {

      int origin = rematch.index;

      REMatch rem;

      if (findFirst)

        {

          rem = tk.findMatch (input, rematch);

          findFirst = false;

        }

      else

        {

          while (true)

            {

              if (rematch.backtrackStack.empty ())

                {

                  rem = null;

                  break;

                }

              BacktrackStack.Backtrack bt = rematch.backtrackStack.pop ();

              rem = bt.token.backtrack (bt.input, bt.match, bt.param);

              if (rem != null)

                break;

            }

        }

      if (rem == null)

        return null;

      if (rem.index == origin)

        rem.empty = true;

      rematch = rem;

      return (REMatch) rem.clone ();    // MUST make a clone.

    }

    boolean noMore ()

    {

      return rematch.backtrackStack.empty ();

    }

  }

  REMatch findMatch (CharIndexed input, REMatch mymatch)

  {

    if (tokenFixedLength >= 0)

      return findMatchFixedLength (input, mymatch);

    BacktrackStack stack = new BacktrackStack ();

    stack.push (new StackedInfo (input, 0, mymatch, null, null));

    return findMatch (stack);

  }

  REMatch backtrack (CharIndexed input, REMatch mymatch, Object param)

  {

    if (tokenFixedLength >= 0)

      return backtrackFixedLength (input, mymatch, param);

    return findMatch ((BacktrackStack) param);

  }

  private static class StackedInfo extends BacktrackStack.Backtrack

  {

    int numRepeats;

    int[] visited;

    DoablesFinder finder;

      StackedInfo (CharIndexed input, int numRepeats, REMatch match,

                   int[]visited, DoablesFinder finder)

    {

      super (null, input, match, null);

      this.numRepeats = numRepeats;

      this.visited = visited;

      this.finder = finder;

    }

  }

  private static class FindMatchControl

  {

    DoablesFinder finder;

      FindMatchControl (DoablesFinder finder)

    {

      this.finder = finder;

    }

  }

  private REMatch findMatch (BacktrackStack stack)

  {

    return findMatch (stack, new ArrayDeque < FindMatchControl > ());

  }

  private REMatch findMatch (BacktrackStack stack,

                             Deque < FindMatchControl > controlStack)

  {

    REMatch result = null;

    StackedInfo si = null;

    CharIndexed input = null;

    int numRepeats = 0;

    REMatch mymatch = null;

    int[] visited = null;

    DoablesFinder finder = null;

    // Avoid using recursive calls because a match can be very long.

    // This is the first entry point of this method.

    // If you want to call this method recursively and you need the

    // result returned, save necessary information in a FindMatchControl

    // object and push it to controlStack, then continue from this point.

    // You can check the result after exiting MAIN_LOOP.

  MAIN_LOOP0:

    while (true)

      {

        // This is the second entry point of this method.

        // If you want to call this method recursively but you do not need the

        // result returned, just continue from this point.

      MAIN_LOOP:

        while (true)

          {

            if (stack.empty ())

              break MAIN_LOOP;

            si = (StackedInfo) (stack.peek ());

            input = si.input;

            numRepeats = si.numRepeats;

            mymatch = si.match;

            visited = si.visited;

            finder = si.finder;

            if (mymatch.backtrackStack == null)

              mymatch.backtrackStack = new BacktrackStack ();

            if (numRepeats >= max)

              {

                stack.pop ();

                REMatch m1 = matchRest (input, mymatch);

                if (m1 != null)

                  {

                    if (!stack.empty ())

                      {

                        m1.backtrackStack.push (new BacktrackStack.

                                                Backtrack (this, input,

                                                           mymatch, stack));

                      }

                    result = m1;

                    break MAIN_LOOP;

                  }

                if (stingy)

                  {

                    continue MAIN_LOOP;

                  }

                break MAIN_LOOP;

              }

            if (finder == null)

              {

                finder = new DoablesFinder (token, input, mymatch);

                si.finder = finder;

              }

            if (numRepeats < min)

              {

                while (true)

                  {

                    REMatch doable = finder.find ();

                    if (doable == null)

                      {

                        if (stack.empty ())

                          return null;

                        stack.pop ();

                        continue MAIN_LOOP;

                      }

                    if (finder.noMore ())

                      stack.pop ();

                    int newNumRepeats = (doable.empty ? min : numRepeats + 1);

                    stack.

                      push (new

                            StackedInfo (input, newNumRepeats, doable,

                                         visited, null));

                    continue MAIN_LOOP;

                  }

              }

            if (visited == null)

              visited = initVisited ();

            if (stingy)

              {

                REMatch nextMatch = finder.find ();

                if (nextMatch != null && !nextMatch.empty)

                  {

                    stack.

                      push (new

                            StackedInfo (input, numRepeats + 1, nextMatch,

                                         visited, null));

                  }

                else

                  {

                    stack.pop ();

                  }

                REMatch m1 = matchRest (input, mymatch);

                if (m1 != null)

                  {

                    if (!stack.empty ())

                      {

                        m1.backtrackStack.push (new BacktrackStack.

                                                Backtrack (this, input,

                                                           mymatch, stack));

                      }

                    result = m1;

                    break MAIN_LOOP;

                  }

                else

                  {

                    continue MAIN_LOOP;

                  }

              }

            visited = addVisited (mymatch.index, visited);

            TryAnotherResult taresult =

              tryAnother (stack, input, mymatch, numRepeats, finder, visited);

            visited = taresult.visited;

            switch (taresult.status)

              {

              case TryAnotherResult.TRY_FURTHER:

                controlStack.push (new FindMatchControl (finder));

                continue MAIN_LOOP0;

              case TryAnotherResult.RESULT_FOUND:

                result = taresult.result;

                break MAIN_LOOP;

              }

            if (!stack.empty ())

              {

                stack.pop ();

              }

            if (possessive)

              {

                stack.clear ();

              }

            REMatch m1 = matchRest (input, mymatch);

            if (m1 != null)

              {

                if (!stack.empty ())

                  {

                    m1.backtrackStack.push (new BacktrackStack.

                                            Backtrack (this, input, mymatch,

                                                       stack));

                  }

                result = m1;

                break MAIN_LOOP;

              }

          }                     // MAIN_LOOP

        if (controlStack.isEmpty ())

          return result;

        FindMatchControl control = controlStack.pop ();

        if (possessive)

          {

            return result;

          }

        if (result != null)

          {

            result.backtrackStack.push (new BacktrackStack.

                                        Backtrack (this, input, mymatch,

                                                   stack));

            return result;

          }

        finder = control.finder;

        TryAnotherResult taresult =

          tryAnother (stack, input, mymatch, numRepeats, finder, visited);

        visited = taresult.visited;

        switch (taresult.status)

          {

          case TryAnotherResult.TRY_FURTHER:

            controlStack.push (new FindMatchControl (finder));

            continue MAIN_LOOP0;

          case TryAnotherResult.RESULT_FOUND:

            return taresult.result;

          }

        continue MAIN_LOOP0;

      }                         // MAIN_LOOP0

  }

  private static class TryAnotherResult

  {

    REMatch result;

    int status;

    static final int RESULT_FOUND = 1;

    static final int TRY_FURTHER = 2;

    static final int NOTHING_FOUND = 3;

    int[] visited;

  }

  private TryAnotherResult tryAnother (BacktrackStack stack,

                                       CharIndexed input, REMatch mymatch,

                                       int numRepeats, DoablesFinder finder,

                                       int[]visited)

  {

    TryAnotherResult taresult = new TryAnotherResult ();

    taresult.visited = visited;

  DO_THIS:

    {

      boolean emptyMatchFound = false;

    DO_ONE_DOABLE:

      while (true)

        {

          REMatch doable = finder.find ();

          if (doable == null)

            {

              break DO_THIS;

            }

          if (doable.empty)

            emptyMatchFound = true;

          if (!emptyMatchFound)

            {

              int n = doable.index;

              if (visitedContains (n, visited))

                {

                  continue DO_ONE_DOABLE;

                }

              visited = addVisited (n, visited);

              stack.

                push (new

                      StackedInfo (input, numRepeats + 1, doable, visited,

                                   null));

              taresult.visited = visited;

              taresult.status = TryAnotherResult.TRY_FURTHER;

              return taresult;

            }

          else

            {

              REMatch m1 = matchRest (input, doable);

              if (possessive)

                {

                  taresult.result = m1;

                  taresult.status = TryAnotherResult.RESULT_FOUND;

                  return taresult;

                }

              if (m1 != null)

                {

                  if (!stack.empty ())

                    {

                      m1.backtrackStack.push (new BacktrackStack.

                                              Backtrack (this, input, mymatch,

                                                         stack));

                    }

                  taresult.result = m1;

                  taresult.status = TryAnotherResult.RESULT_FOUND;

                  return taresult;

                }

            }

        }                       // DO_ONE_DOABLE

    }                           // DO_THIS

    taresult.status = TryAnotherResult.NOTHING_FOUND;

    return taresult;

  }

  boolean match (CharIndexed input, REMatch mymatch)

  {

    setHitEnd (input, mymatch);

    REMatch m1 = findMatch (input, mymatch);

    if (m1 != null)

      {

        mymatch.assignFrom (m1);

        return true;

      }

    return false;

  }

  // Array visited is an array of character positions we have already

  // visited. visited[0] is used to store the effective length of the

  // array.

  private static int[] initVisited ()

  {

    int[] visited = new int[32];

    visited[0] = 0;

    return visited;

  }

  private static boolean visitedContains (int n, int[]visited)

  {

    // Experience tells that for a small array like this,

    // simple linear search is faster than binary search.

    for (int i = 1; i < visited[0]; i++)

      {

        if (n == visited[i])

          return true;

      }

    return false;

  }

  private static int[] addVisited (int n, int[]visited)

  {

    if (visitedContains (n, visited))

      return visited;

    if (visited[0] >= visited.length - 1)

      {

        int[] newvisited = new int[visited.length + 32];

        System.arraycopy (visited, 0, newvisited, 0, visited.length);

        visited = newvisited;

      }

    visited[0]++;

    visited[visited[0]] = n;

    return visited;

  }

  private REMatch matchRest (CharIndexed input, final REMatch newMatch)

  {

    if (next (input, newMatch))

      {

        return newMatch;

      }

    return null;

  }

  private REMatch findMatchFixedLength (CharIndexed input, REMatch mymatch)

  {

    if (mymatch.backtrackStack == null)

      mymatch.backtrackStack = new BacktrackStack ();

    int numRepeats =

      token.findFixedLengthMatches (input, (REMatch) mymatch.clone (), max);

    if (numRepeats == Integer.MAX_VALUE)

      numRepeats = min;

    int count = numRepeats - min + 1;

    if (count <= 0)

      return null;

    int index = 0;

    if (!stingy)

      index = mymatch.index + (tokenFixedLength * numRepeats);

    else

      index = mymatch.index + (tokenFixedLength * min);

    return findMatchFixedLength (input, mymatch, index, count);

  }

  private REMatch backtrackFixedLength (CharIndexed input, REMatch mymatch,

                                        Object param)

  {

    int[] params = (int[]) param;

    int index = params[0];

    int count = params[1];

    return findMatchFixedLength (input, mymatch, index, count);

  }

  private REMatch findMatchFixedLength (CharIndexed input, REMatch mymatch,

                                        int index, int count)

  {

    REMatch tryMatch = (REMatch) mymatch.clone ();

    while (true)

      {

        tryMatch.index = index;

        REMatch m = matchRest (input, tryMatch);

        count--;

        if (stingy)

          index += tokenFixedLength;

        else

          index -= tokenFixedLength;

        if (possessive)

          return m;

        if (m != null)

          {

            if (count > 0)

              {

                m.backtrackStack.push (new BacktrackStack.

                                       Backtrack (this, input, mymatch,

                                                  new int[]

                                                  {

                                                  index, count}));

              }

            return m;

          }

        if (count <= 0)

          return null;

      }

  }

  void dump (CPStringBuilder os)

  {

    os.append ("(?:");

    token.dumpAll (os);

    os.append (')');

    if ((max == Integer.MAX_VALUE) && (min <= 1))

      os.append ((min == 0) ? '*' : '+');

    else if ((min == 0) && (max == 1))

      os.append ('?');

    else

      {

        os.append ('{').append (min);

        if (max > min)

          {

            os.append (',');

            if (max != Integer.MAX_VALUE)

              os.append (max);

          }

        os.append ('}');

      }

    if (stingy)

      os.append ('?');

  }

}