org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/util/StringMatcher.java

   1 /*******************************************************************************
   2  * Copyright (c) 2000, 2008 IBM Corporation and others.
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Eclipse Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *     IBM Corporation - initial API and implementation
  10  *     QNX Software System
  11  *     Markus Schorn (Wind River Systems)
  12  *******************************************************************************/
  13 package org.eclipse.cdt.internal.ui.util;
  14
  15 import java.util.Vector;
  16
  17 public class StringMatcher {
  18         protected String fPattern;
  19         protected int fLength; // pattern length
  20         protected boolean fIgnoreWildCards;
  21         protected boolean fIgnoreCase;
  22         protected boolean fHasLeadingStar;
  23         protected boolean fHasTrailingStar;
  24         protected String fSegments[]; //the given pattern is split into * separated segments
  25
  26         /* boundary value beyond which we don't need to search in the text */
  27         protected int fBound= 0;
  28
  29         protected static final char fSingleWildCard= '\u0000';
  30
  31         public static class Position {
  32                 int start; //inclusive
  33                 int end; //exclusive
  34                 public Position(int start, int end) {
  35                         this.start= start;
  36                         this.end= end;
  37                 }
  38                 public int getStart() {
  39                         return start;
  40                 }
  41                 public int getEnd() {
  42                         return end;
  43                 }
  44         }
  45
  46         /**
  47          * Find the first occurrence of the pattern between <code>start</code)(inclusive)
  48          * and <code>end</code>(exclusive).
  49          * @param text the String object to search in
  50          * @param start the starting index of the search range, inclusive
  51          * @param end the ending index of the search range, exclusive
  52          * @return an <code>StringMatcher.Position</code> object that keeps the starting
  53          * (inclusive) and ending positions (exclusive) of the first occurrence of the
  54          * pattern in the specified range of the text; return null if not found or subtext
  55          * is empty (start==end). A pair of zeros is returned if pattern is empty string
  56          * Note that for pattern like "*abc*" with leading and trailing stars, position of "abc"
  57          * is returned. For a pattern like"*??*" in text "abcdf", (1,3) is returned
  58          */
  59
  60         public StringMatcher.Position find(String text, int start, int end) {
  61                 if (fPattern == null || text == null)
  62                         throw new IllegalArgumentException();
  63
  64                 int tlen= text.length();
  65                 if (start < 0)
  66                         start= 0;
  67                 if (end > tlen)
  68                         end= tlen;
  69                 if (end < 0 || start >= end)
  70                         return null;
  71                 if (fLength == 0)
  72                         return new Position(start, start);
  73                 if (fIgnoreWildCards) {
  74                         int x= posIn(text, start, end);
  75                         if (x < 0)
  76                                 return null;
  77                         return new Position(x, x + fLength);
  78                 }
  79
  80                 int segCount= fSegments.length;
  81                 if (segCount == 0) //pattern contains only '*'(s)
  82                         return new Position(start, end);
  83
  84                 int curPos= start;
  85                 int matchStart= -1;
  86                 for (int i= 0; i < segCount && curPos < end; ++i) {
  87                         String current= fSegments[i];
  88                         int nextMatch= regExpPosIn(text, curPos, end, current);
  89                         if (nextMatch < 0)
  90                                 return null;
  91                         if (i == 0)
  92                                 matchStart= nextMatch;
  93                         curPos= nextMatch + current.length();
  94                 }
  95                 return new Position(matchStart, curPos);
  96         }
  97         /**
  98          * StringMatcher constructor takes in a String object that is a simple
  99          * pattern which may contain  \18* \19 for 0 and many characters and
 100          *  \18? \19 for exactly one character. Also takes as parameter a boolean object
 101          * specifying if case should be ignored
 102          * @deprecated Use StringMatcher(pattern, ignoreCase, ignoreWildCards).
 103          */
 104         @Deprecated
 105         public StringMatcher(String aPattern, boolean ignoreCase) {
 106                 this(aPattern, ignoreCase, false);
 107         }
 108         /**
 109          * StringMatcher constructor takes in a String object that is a simple
 110          * pattern which may contain  \18* \19 for 0 and many characters and
 111          *  \18? \19 for exactly one character.
 112          *
 113          * Literal '*' and '?' characters must be escaped in the pattern
 114          * e.g., "\*" means literal "*", etc.
 115          *
 116          * Escaping any other character (including the escape character itself),
 117          * just results in that character in the pattern.
 118          * e.g., "\a" means "a" and "\\" means "\"
 119          *
 120          * If invoking the StringMatcher with string literals in Java, don't forget
 121          * escape characters are represented by "\\".
 122          *
 123          * @param aPattern the pattern to match text against
 124          * @param ignoreCase if true, case is ignored
 125          * @param ignoreWildCards if true, wild cards and their escape sequences are ignored
 126          *                (everything is taken literally).
 127          */
 128         public StringMatcher(String aPattern, boolean ignoreCase, boolean ignoreWildCards) {
 129                 fIgnoreCase= ignoreCase;
 130                 fIgnoreWildCards= ignoreWildCards;
 131                 fLength= aPattern.length();
 132
 133                 /* convert case */
 134                 if (fIgnoreCase) {
 135                         char[] chars= aPattern.toCharArray();
 136                         for (int i = 0; i < chars.length; i++) {
 137                                 chars[i]= Character.toUpperCase(chars[i]);
 138                         }
 139                         fPattern= new String(chars);
 140                 } else {
 141                         fPattern= aPattern;
 142                 }
 143
 144                 if (fIgnoreWildCards) {
 145                         parseNoWildCards();
 146                 } else {
 147                         parseWildCards();
 148                 }
 149         }
 150         /**
 151          * Given the starting (inclusive) and the ending (exclusive) poisitions in the
 152          * <code>text</code>, determine if the given substring matches with aPattern
 153          * @return true if the specified portion of the text matches the pattern
 154          * @param text  a String object that contains the substring to match
 155          * @param start marks the starting position (inclusive) of the substring
 156          * @param end marks the ending index (exclusive) of the substring
 157          */
 158         public boolean match(String text, int start, int end) {
 159                 if (null == fPattern || null == text)
 160                         throw new IllegalArgumentException();
 161
 162                 if (start > end)
 163                         return false;
 164
 165                 if (fIgnoreWildCards)
 166                         return fPattern.regionMatches(fIgnoreCase, 0, text, start, fLength);
 167                 int segCount= fSegments.length;
 168                 if (segCount == 0) //pattern contains only '*'(s) or empty pattern
 169                         return true;
 170                 if (start == end)
 171                         return fLength == 0;
 172                 if (fLength == 0)
 173                         return start == end;
 174
 175                 int tlen= text.length();
 176                 if (start < 0)
 177                         start= 0;
 178                 if (end > tlen)
 179                         end= tlen;
 180
 181                 int tCurPos= start;
 182                 int bound= end - fBound;
 183                 if (bound < 0)
 184                         return false;
 185                 int i= 0;
 186                 String current= fSegments[i];
 187                 int segLength= current.length();
 188
 189                 /* process first segment */
 190                 if (!fHasLeadingStar) {
 191                         if (!regExpRegionMatches(text, start, current, 0, segLength)) {
 192                                 return false;
 193                         }
 194                         ++i;
 195                         tCurPos= tCurPos + segLength;
 196                 }
 197
 198                 /* process middle segments */
 199                 for (; i < segCount && tCurPos <= bound; ++i) {
 200                         current= fSegments[i];
 201                         int currentMatch;
 202                         int k= current.indexOf(fSingleWildCard);
 203                         if (k < 0) {
 204                                 currentMatch= textPosIn(text, tCurPos, end, current);
 205                                 if (currentMatch < 0)
 206                                         return false;
 207                         } else {
 208                                 currentMatch= regExpPosIn(text, tCurPos, end, current);
 209                                 if (currentMatch < 0)
 210                                         return false;
 211                         }
 212                         tCurPos= currentMatch + current.length();
 213                 }
 214
 215                 /* process final segment */
 216                 if (!fHasTrailingStar && tCurPos != end) {
 217                         int clen= current.length();
 218                         return regExpRegionMatches(text, end - clen, current, 0, clen);
 219                 }
 220                 return i == segCount;
 221         }
 222         /**
 223          * match the given <code>text</code> with the pattern
 224          * @return true if matched eitherwise false
 225          * @param text a String object
 226          */
 227         public boolean match(String text) {
 228                 return match(text, 0, text.length());
 229         }
 230         /**
 231          * This method parses the given pattern into segments seperated by wildcard '*' characters.
 232          * Since wildcards are not being used in this case, the pattern consists of a single segment.
 233          */
 234         private void parseNoWildCards() {
 235                 fSegments= new String[1];
 236                 fSegments[0]= fPattern;
 237                 fBound= fLength;
 238         }
 239         /**
 240          *  This method parses the given pattern into segments seperated by wildcard '*' characters.
 241          */
 242         private void parseWildCards() {
 243                 if (fPattern.startsWith("*")) //$NON-NLS-1$
 244                         fHasLeadingStar= true;
 245                 if (fPattern.endsWith("*")) { //$NON-NLS-1$
 246                         /* make sure it's not an escaped wildcard */
 247                         if (fLength > 1 && fPattern.charAt(fLength - 2) != '\\') {
 248                                 fHasTrailingStar= true;
 249                         }
 250                 }
 251
 252                 Vector<String> temp= new Vector<String>();
 253
 254                 int pos= 0;
 255                 StringBuffer buf= new StringBuffer();
 256                 while (pos < fLength) {
 257                         char c= fPattern.charAt(pos++);
 258                         switch (c) {
 259                                 case '\\' :
 260                                         if (pos >= fLength) {
 261                                                 buf.append(c);
 262                                         } else {
 263                                                 char next= fPattern.charAt(pos++);
 264                                                 /* if it's an escape sequence */
 265                                                 if (next == '*' || next == '?' || next == '\\') {
 266                                                         buf.append(next);
 267                                                 } else {
 268                                                         /* not an escape sequence, just insert literally */
 269                                                         buf.append(c);
 270                                                         buf.append(next);
 271                                                 }
 272                                         }
 273                                         break;
 274                                 case '*' :
 275                                         if (buf.length() > 0) {
 276                                                 /* new segment */
 277                                                 temp.addElement(buf.toString());
 278                                                 fBound += buf.length();
 279                                                 buf.setLength(0);
 280                                         }
 281                                         break;
 282                                 case '?' :
 283                                         /* append special character representing single match wildcard */
 284                                         buf.append(fSingleWildCard);
 285                                         break;
 286                                 default :
 287                                         buf.append(c);
 288                         }
 289                 }
 290
 291                 /* add last buffer to segment list */
 292                 if (buf.length() > 0) {
 293                         temp.addElement(buf.toString());
 294                         fBound += buf.length();
 295                 }
 296
 297                 fSegments= new String[temp.size()];
 298                 temp.copyInto(fSegments);
 299         }
 300         /**
 301          * @param text a string which contains no wildcard
 302          * @param start the starting index in the text for search, inclusive
 303          * @param end the stopping point of search, exclusive
 304          * @return the starting index in the text of the pattern , or -1 if not found
 305          */
 306         protected int posIn(String text, int start, int end) { //no wild card in pattern
 307                 int max= end - fLength;
 308
 309                 if (!fIgnoreCase) {
 310                         int i= text.indexOf(fPattern, start);
 311                         if (i == -1 || i > max)
 312                                 return -1;
 313                         return i;
 314                 }
 315
 316                 for (int i= start; i <= max; ++i) {
 317                         if (text.regionMatches(true, i, fPattern, 0, fLength))
 318                                 return i;
 319                 }
 320
 321                 return -1;
 322         }
 323         /**
 324          * @param text a simple regular expression that may only contain '?'(s)
 325          * @param start the starting index in the text for search, inclusive
 326          * @param end the stopping point of search, exclusive
 327          * @param p a simple regular expression that may contains '?'
 328          * @return the starting index in the text of the pattern , or -1 if not found
 329          */
 330         protected int regExpPosIn(String text, int start, int end, String p) {
 331                 int plen= p.length();
 332
 333                 int max= end - plen;
 334                 for (int i= start; i <= max; ++i) {
 335                         if (regExpRegionMatches(text, i, p, 0, plen))
 336                                 return i;
 337                 }
 338                 return -1;
 339         }
 340
 341         protected boolean regExpRegionMatches(String text, int tStart, String p, int pStart, int plen) {
 342                 while (plen-- > 0) {
 343                         char tchar= text.charAt(tStart++);
 344                         char pchar= p.charAt(pStart++);
 345
 346                         /* process wild cards */
 347                         if (!fIgnoreWildCards) {
 348                                 /* skip single wild cards */
 349                                 if (pchar == fSingleWildCard) {
 350                                         continue;
 351                                 }
 352                         }
 353                         if (pchar == tchar)
 354                                 continue;
 355                         if (fIgnoreCase) {
 356                                 char tc= Character.toUpperCase(tchar);
 357                                 if (tc == pchar)
 358                                         continue;
 359                         }
 360                         return false;
 361                 }
 362                 return true;
 363         }
 364         /**
 365          * @param text the string to match
 366          * @param start the starting index in the text for search, inclusive
 367          * @param end the stopping point of search, exclusive
 368          * @param p a string that has no wildcard
 369          * @return the starting index in the text of the pattern , or -1 if not found
 370          */
 371         protected int textPosIn(String text, int start, int end, String p) {
 372
 373                 int plen= p.length();
 374                 int max= end - plen;
 375
 376                 if (!fIgnoreCase) {
 377                         int i= text.indexOf(p, start);
 378                         if (i == -1 || i > max)
 379                                 return -1;
 380                         return i;
 381                 }
 382
 383                 for (int i= 0; i <= max; ++i) {
 384                         if (text.regionMatches(true, i, p, 0, plen))
 385                                 return i;
 386                 }
 387
 388                 return -1;
 389         }
 390 }