Source code

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