Source code

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