org.spearce.jgit/src/org/spearce/jgit/util/RawSubStringPattern.java

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.util;
  39
  40 import java.io.UnsupportedEncodingException;
  41
  42 /**
  43  * Searches text using only substring search.
  44  * <p>
  45  * Instances are thread-safe. Multiple concurrent threads may perform matches on
  46  * different character sequences at the same time.
  47  */
  48 public class RawSubStringPattern {
  49         private final String needleString;
  50
  51         private final byte[] needle;
  52
  53         /**
  54          * Construct a new substring pattern.
  55          *
  56          * @param patternText
  57          *            text to locate. This should be a literal string, as no
  58          *            meta-characters are supported by this implementation. The
  59          *            string may not be the empty string.
  60          */
  61         public RawSubStringPattern(final String patternText) {
  62                 if (patternText.length() == 0)
  63                         throw new IllegalArgumentException("Cannot match on empty string.");
  64                 needleString = patternText;
  65
  66                 final byte[] b;
  67                 try {
  68                         b = patternText.getBytes("UTF-8");
  69                 } catch (UnsupportedEncodingException e) {
  70                         throw new IllegalStateException("JVM lacks UTF-8 support.", e);
  71                 }
  72
  73                 needle = new byte[b.length];
  74                 for (int i = 0; i < b.length; i++)
  75                         needle[i] = lc(b[i]);
  76         }
  77
  78         /**
  79          * Match a character sequence against this pattern.
  80          *
  81          * @param rcs
  82          *            the sequence to match. Must not be null but the length of the
  83          *            sequence is permitted to be 0.
  84          * @return offset within <code>rcs</code> of the first occurrence of this
  85          *         pattern; -1 if this pattern does not appear at any position of
  86          *         <code>rcs</code>.
  87          */
  88         public int match(final RawCharSequence rcs) {
  89                 final int needleLen = needle.length;
  90                 final byte first = needle[0];
  91
  92                 final byte[] text = rcs.buffer;
  93                 int matchPos = rcs.startPtr;
  94                 final int maxPos = rcs.endPtr - needleLen;
  95
  96                 OUTER: for (; matchPos < maxPos; matchPos++) {
  97                         if (neq(first, text[matchPos])) {
  98                                 while (++matchPos < maxPos && neq(first, text[matchPos])) {
  99                                         /* skip */
 100                                 }
 101                                 if (matchPos == maxPos)
 102                                         return -1;
 103                         }
 104
 105                         int si = ++matchPos;
 106                         for (int j = 1; j < needleLen; j++, si++) {
 107                                 if (neq(needle[j], text[si]))
 108                                         continue OUTER;
 109                         }
 110                         return matchPos - 1;
 111                 }
 112                 return -1;
 113         }
 114
 115         private static final boolean neq(final byte a, final byte b) {
 116                 return a != b && a != lc(b);
 117         }
 118
 119         private static final byte lc(final byte q) {
 120                 return (byte) Character.toLowerCase((char) (q & 0xff));
 121         }
 122
 123         /**
 124          * Get the literal pattern string this instance searches for.
 125          *
 126          * @return the pattern string given to our constructor.
 127          */
 128         public String pattern() {
 129                 return needleString;
 130         }
 131
 132         @Override
 133         public String toString() {
 134                 return pattern();
 135         }
 136 }