001// *************************************************************************************************************************** 002// * Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file * 003// * distributed with this work for additional information regarding copyright ownership. The ASF licenses this file * 004// * to you under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance * 005// * with the License. You may obtain a copy of the License at * 006// * * 007// * http://www.apache.org/licenses/LICENSE-2.0 * 008// * * 009// * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an * 010// * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the * 011// * specific language governing permissions and limitations under the License. * 012// *************************************************************************************************************************** 013package org.apache.juneau.utils; 014 015import java.text.ParseException; 016import java.util.*; 017import java.util.regex.*; 018 019import org.apache.juneau.internal.*; 020 021import static org.apache.juneau.internal.StateMachineState.*; 022 023/** 024 * Utility class for matching strings against string expressions. 025 * 026 * <p> 027 * Supports the following string constructs: 028 * <ul> 029 * <li><js>"foo"</js> - Single arguments. 030 * <li><js>"foo,bar,baz"</js> - Multiple OR'ed arguments. 031 * <li><js>"foo | bar | bqz"</js> - Multiple OR'ed arguments, pipe syntax. 032 * <li><js>"foo || bar || bqz"</js> - Multiple OR'ed arguments, Java-OR syntax. 033 * <li><js>"fo*"</js> - Patterns including <js>'*'</js> and <js>'?'</js>. 034 * <li><js>"fo* & *oo"</js> - Multiple AND'ed arguments, ampersand syntax. 035 * <li><js>"fo* && *oo"</js> - Multiple AND'ed arguments, Java-AND syntax. 036 * <li><js>"fo* || (*oo || bar)"</js> - Parenthesis. 037 * </ul> 038 * 039 * <ul class='notes'> 040 * <li>AND operations take precedence over OR operations (as expected). 041 * <li>Whitespace is ignored. 042 * <li><jk>null</jk> or empty expressions always match as <jk>false</jk>. 043 * </ul> 044 */ 045public class StringExpressionMatcher { 046 047 private final Exp exp; 048 private static final AsciiSet 049 WS = AsciiSet.create(" \t"), 050 OP = AsciiSet.create(",|&"), 051 META = AsciiSet.create("*?"); 052 053 /** 054 * Constructor. 055 * 056 * @param expression The string expression. 057 * @throws ParseException Malformed input encountered. 058 */ 059 public StringExpressionMatcher(String expression) throws ParseException { 060 this.exp = parse(expression); 061 } 062 063 /** 064 * Returns <jk>true</jk> if the specified string matches this expression. 065 * 066 * @param input The input string. 067 * @return 068 * <jk>true</jk> if the specified string matches this expression. 069 * <br>Always <jk>false</jk> if the string is <jk>null</jk>. 070 */ 071 public boolean matches(String input) { 072 return input != null && exp.matches(input); 073 } 074 075 @Override /* Object */ 076 public String toString() { 077 return exp.toString(); 078 } 079 080 /** 081 * Returns all the tokens used in this expression. 082 * 083 * @return All the tokens used in this expression. 084 */ 085 public Set<String> getTokens() { 086 Set<String> set = new TreeSet<>(); 087 exp.appendTokens(set); 088 return set; 089 } 090 091 private Exp parse(String expression) throws ParseException { 092 if (StringUtils.isEmptyOrBlank(expression)) 093 return new Never(); 094 095 expression = expression.trim(); 096 097 List<Exp> ors = new ArrayList<>(); 098 List<Exp> ands = new ArrayList<>(); 099 100 StateMachineState state = S01; 101 int i = 0, mark = -1; 102 int pDepth = 0; 103 boolean error = false; 104 105 for (i = 0; i < expression.length(); i++) { 106 char c = expression.charAt(i); 107 if (state == S01) { 108 // S01 = Looking for start 109 if (! WS.contains(c)) { 110 if (c == '(') { 111 state = S02; 112 pDepth = 0; 113 mark = i+1; 114 } else if (OP.contains(c)) { 115 error = true; 116 break; 117 } else { 118 state = S03; 119 mark = i; 120 } 121 } 122 } else if (state == S02) { 123 // S02 = Found [(], looking for [)]. 124 if (c == '(') 125 pDepth++; 126 if (c == ')') { 127 if (pDepth > 0) 128 pDepth--; 129 else { 130 ands.add(parse(expression.substring(mark, i))); 131 mark = -1; 132 state = S04; 133 } 134 } 135 } else if (state == S03) { 136 // S03 = Found [A], looking for end of A. 137 if (WS.contains(c) || OP.contains(c)) { 138 ands.add(parseOperand(expression.substring(mark, i))); 139 mark = -1; 140 if (WS.contains(c)) { 141 state = S04; 142 } else { 143 i--; 144 state = S05; 145 } 146 } 147 } else if (state == S04) { 148 // S04 = Found [A ], looking for & or | or ,. 149 if (! WS.contains(c)) { 150 if (OP.contains(c)) { 151 i--; 152 state = S05; 153 } else { 154 error = true; 155 break; 156 } 157 } 158 } else if (state == S05) { 159 // S05 = Found & or | or ,. 160 if (c == '&') { 161 //ands.add(operand); 162 state = S06; 163 } else /* (c == '|' || c == ',') */ { 164 if (ands.size() == 1) { 165 ors.add(ands.get(0)); 166 } else { 167 ors.add(new And(ands)); 168 } 169 ands.clear(); 170 if (c == '|') { 171 state = S07; 172 } else { 173 state = S01; 174 } 175 } 176 } else if (state == S06) { 177 // S06 = Found &, looking for & or other 178 if (! WS.contains(c)) { 179 if (c != '&') 180 i--; 181 state = S01; 182 } 183 } else /* (state == S07) */ { 184 // S07 = Found |, looking for | or other 185 if (! WS.contains(c)) { 186 if (c != '|') 187 i--; 188 state = S01; 189 } 190 } 191 } 192 193 if (error) 194 throw new ParseException("Invalid character in expression '"+expression+"' at position " + i + ". state=" + state, i); 195 196 if (state == S01) 197 throw new ParseException("Could not find beginning of clause in '"+expression+"'", i); 198 if (state == S02) 199 throw new ParseException("Could not find matching parenthesis in expression '"+expression+"'", i); 200 if (state == S05 || state == S06 || state == S07) 201 throw new ParseException("Dangling clause in expression '"+expression+"'", i); 202 203 if (mark != -1) 204 ands.add(parseOperand(expression.substring(mark, expression.length()))); 205 if (ands.size() == 1) 206 ors.add(ands.get(0)); 207 else 208 ors.add(new And(ands)); 209 210 if (ors.size() == 1) 211 return ors.get(0); 212 return new Or(ors); 213 } 214 215 private static Exp parseOperand(String operand) { 216 boolean hasMeta = false; 217 for (int i = 0; i < operand.length() && ! hasMeta; i++) { 218 char c = operand.charAt(i); 219 hasMeta |= META.contains(c); 220 } 221 return hasMeta ? new Match(operand) : new Eq(operand); 222 } 223 224 //----------------------------------------------------------------------------------------------------------------- 225 // Expression classes 226 //----------------------------------------------------------------------------------------------------------------- 227 228 abstract static class Exp { 229 abstract boolean matches(String input); 230 void appendTokens(Set<String> set) {} 231 } 232 233 static class Never extends Exp { 234 @Override 235 boolean matches(String input) { 236 return false; 237 } 238 239 @Override /* Object */ 240 public String toString() { 241 return "(NEVER)"; 242 } 243 } 244 245 static class And extends Exp { 246 Exp[] clauses; 247 248 And(List<Exp> clauses) { 249 this.clauses = clauses.toArray(new Exp[clauses.size()]); 250 } 251 252 @Override /* Exp */ 253 boolean matches(String input) { 254 for (Exp e : clauses) 255 if (! e.matches(input)) 256 return false; 257 return true; 258 } 259 260 @Override /* Exp */ 261 void appendTokens(Set<String> set) { 262 for (Exp clause : clauses) 263 clause.appendTokens(set); 264 } 265 266 @Override /* Object */ 267 public String toString() { 268 return "(& " + StringUtils.join(clauses, " ") + ')'; 269 } 270 } 271 272 static class Or extends Exp { 273 Exp[] clauses; 274 275 Or(List<Exp> clauses) { 276 this.clauses = clauses.toArray(new Exp[clauses.size()]); 277 } 278 279 @Override 280 boolean matches(String input) { 281 for (Exp e : clauses) 282 if (e.matches(input)) 283 return true; 284 return false; 285 } 286 287 @Override /* Exp */ 288 void appendTokens(Set<String> set) { 289 for (Exp clause : clauses) 290 clause.appendTokens(set); 291 } 292 293 @Override /* Object */ 294 public String toString() { 295 return "(| " + StringUtils.join(clauses, " ") + ')'; 296 } 297 } 298 299 static class Eq extends Exp { 300 final String operand; 301 302 Eq(String operand) { 303 this.operand = operand; 304 } 305 306 @Override /* Exp */ 307 boolean matches(String input) { 308 return operand.equals(input); 309 } 310 311 @Override /* Exp */ 312 void appendTokens(Set<String> set) { 313 set.add(operand); 314 } 315 316 @Override /* Object */ 317 public String toString() { 318 return "[= " + operand + "]"; 319 } 320 } 321 322 static class Match extends Exp { 323 final Pattern p; 324 final String operand; 325 326 Match(String operand) { 327 this.operand = operand; 328 p = StringUtils.getMatchPattern(operand); 329 } 330 331 @Override /* Exp */ 332 boolean matches(String input) { 333 return p.matcher(input).matches(); 334 } 335 336 @Override /* Exp */ 337 void appendTokens(Set<String> set) { 338 set.add(operand); 339 } 340 341 @Override /* Object */ 342 public String toString() { 343 return "[* " + p.pattern().replaceAll("\\\\[QE]", "") + "]"; 344 } 345 } 346} 347