View Javadoc
1 /*
2 * Expression.java
3 * Created on August 19, 2003
4 *
5 * The Blues Framework - A lightweight application framework
6 * Copyright (C) 2003 Lonnie Pryor
7 * http://blues.lonniepryor.com
8 *
9 * This library is free software; you can redistribute it and/or modify it under the
10 * terms of the GNU Lesser General Public License as published by the Free Software
11 * Foundation; either version 2.1 of the License, or (at your option) any later
12 * version.
13 *
14 * This library is distributed in the hope that it will be useful, but WITHOUT ANY
15 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
16 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License along
19 * with this library; if not, write to:
20 *
21 * The Free Software Foundation, Inc.
22 * 59 Temple Place, Suite 330
23 * Boston, MA 02111-1307 USA
24 *
25 */
26 package com.lonniepryor.blues.util;
27
28 /***
29 * Helper class for parsing logical expressions and combining them using the AND,
30 * OR, and NOT operations. Expression parses according to the following format:
31 * <pre>
32 * expression ::= or
33 * or ::= and [ ( "|" | "||" ) and ]...
34 * and ::= not [ ( "&" | "&&" ) not ]...
35 * not ::= [ "!" ] statement
36 * statement ::= predicate | "(" expression ")"
37 * predicate ::= See below.
38 * </pre>
39 * The information in the "predicate" type must start with any non-whitespace
40 * character except parenthesis, '|', &', and '!'; but thereafter can use any
41 * characters, provided any of the aforementioned characters are contained in
42 * matching pairs of parenthesis. This allows nesting expressions in method-like
43 * grammars. Example:
44 * <pre>
45 * foo((him | her) & !me) & !bar | baz (This is my message)
46 * </pre>
47 * The above will be parsed into: "foo((him | her) & !me)", the AND operator, the
48 * NOT operator, "bar", the OR operator, and "baz (This is my message)".
49 *
50 * @author Lonnie Pryor
51 * @version $Revision: 1.1 $
52 */
53 public final class Expression {
54 /*** The content of the expression. */
55 private final String data;
56 /*** The current index in the scan. */
57 private int index = 0;
58
59 /***
60 * Creates a new Expression object.
61 *
62 * @param data The content of the expression.
63 */
64 private Expression (String data) {
65 this.data = data;
66 }
67
68 /***
69 * Parses the supplied expression string into objects provided by the specified
70 * Builder.
71 *
72 * @param expression The expression to parse.
73 * @param builder The Builder to construct objects with.
74 *
75 * @return The Builder-supplied value of the expression.
76 *
77 * @throws ParseException if the supplied string is invalid.
78 */
79 public static Object parse (String expression, Builder builder) {
80 if (expression == null)
81 throw new NullPointerException("expression");
82 if (builder == null)
83 throw new NullPointerException("builder");
84 return new Expression(expression).readExpression(builder);
85 }
86
87 /***
88 * Returns the index in the string of the first character past the end of the
89 * statement that begins at the supplied index.
90 *
91 * @param text The text to search.
92 * @param statementBegin The index of the first character in the statement.
93 * @param end The point at which to stop searching.
94 *
95 * @return The index in the string of the first character past the end of the
96 * statement that begins at the supplied index, or -1 if a matching
97 * parenthesis is not found.
98 */
99 public static int statementEndsAt (String text, int statementBegin, int end) {
100 return statementEndsAt(text, statementBegin, end, "");
101 }
102
103 /***
104 * Returns the index in the string of the first character past the end of the
105 * statement that begins at the supplied index, using the supplied statement
106 * terminators.
107 *
108 * @param text The text to search.
109 * @param statementBegin The index of the first character in the statement.
110 * @param end The point at which to stop searching.
111 * @param terminators Any characters that signal the end of the statement.
112 *
113 * @return The index in the string of the first character past the end of the
114 * statement that begins at the supplied index, or -1 if a matching
115 * parenthesis is not found.
116 */
117 public static int statementEndsAt (
118 String text, int statementBegin, int end, String terminators) {
119 if (text.charAt(statementBegin) == '(') {
120 int depth = 0;
121 for (int i = statementBegin + 1; i < end; ++i) {
122 if (text.charAt(i) == ')') {
123 if (depth == 0)
124 return i + 1;
125 --depth;
126 } else if (text.charAt(i) == '(')
127 ++depth;
128 }
129 return -1;
130 } else {
131 for (int i = statementBegin + 1; i < end; ++i) {
132 if (
133 Character.isWhitespace(text.charAt(i))
134 || (terminators.indexOf(text.charAt(i)) >= 0))
135 return i;
136 }
137 return end;
138 }
139 }
140
141 /***
142 * Returns the index in the string of the first character of the statement that
143 * ends at the supplied index.
144 *
145 * @param text The text to search.
146 * @param begin The point at which to stop searching.
147 * @param statementEnd The index of the character following the end of the
148 * statement.
149 *
150 * @return The index in the string of the first character of the statement that
151 * ends at the supplied index, or -1 if a matching parenthesis is not
152 * found.
153 */
154 public static int statementBeginsAt (String text, int begin, int statementEnd) {
155 return statementBeginsAt(text, begin, statementEnd, "");
156 }
157
158 /***
159 * Returns the index in the string of the first character of the statement that
160 * ends at the supplied index, using the supplied statement terminators.
161 *
162 * @param text The text to search.
163 * @param begin The point at which to stop searching.
164 * @param statementEnd The index of the character following the end of the
165 * statement.
166 * @param terminators Any characters that signal the end of the statement.
167 *
168 * @return The index in the string of the first character of the statement that
169 * ends at the supplied index, or -1 if a matching parenthesis is not
170 * found.
171 */
172 public static int statementBeginsAt (
173 String text, int begin, int statementEnd, String terminators) {
174 if (text.charAt(statementEnd - 1) == ')') {
175 int depth = 0;
176 for (int i = statementEnd - 2; i >= 0; --i) {
177 if (text.charAt(i) == '(') {
178 if (depth == 0)
179 return i;
180 --depth;
181 } else if (text.charAt(i) == ')')
182 ++depth;
183 }
184 return -1;
185 } else {
186 for (int i = statementEnd - 2; i >= 0; --i) {
187 if (
188 Character.isWhitespace(text.charAt(i))
189 || (terminators.indexOf(text.charAt(i)) >= 0))
190 return i + 1;
191 }
192 return begin;
193 }
194 }
195
196 /***
197 * Searches the string for the greatest index less than or equal to the end
198 * parameter that is not a whitespace character.
199 *
200 * @param text The text to search.
201 * @param start The beginning of the section to search.
202 * @param end The end of the section to search.
203 *
204 * @return The new start value.
205 */
206 public static int ltrim (String text, int start, int end) {
207 for (int i = start; i < end; ++i)
208 if (!Character.isWhitespace(text.charAt(i)))
209 return i;
210 return end;
211 }
212
213 /***
214 * Searches the string for the smallest index greater than or equal to the start
215 * parameter that is not a whitespace character.
216 *
217 * @param text The text to search.
218 * @param start The beginning of the section to search.
219 * @param end The end of the section to search.
220 *
221 * @return The new end value.
222 */
223 public static int rtrim (String text, int start, int end) {
224 for (int i = end; i > start; --i)
225 if (!Character.isWhitespace(text.charAt(i - 1)))
226 return i;
227 return start;
228 }
229
230 /***
231 * Reads the value of an expression.
232 *
233 * @param builder The Builder to construct objects with.
234 *
235 * @return The value of an expression.
236 *
237 * @throws ParseException if no expression is available.
238 */
239 private Object readExpression (Builder builder) {
240 if (!skipWhitespace())
241 throw new ParseException("No expression found in '" + data + "' at " + index);
242 return readBinaryOr(builder);
243 }
244
245 /***
246 * Reads the value of a binary OR.
247 *
248 * @param builder The Builder to construct objects with.
249 *
250 * @return The value of a binary OR.
251 *
252 * @throws ParseException if no inital OR term is available.
253 */
254 private Object readBinaryOr (Builder builder) {
255 if (!skipWhitespace())
256 throw new ParseException(
257 "No inital OR term found in '" + data + "' at " + index);
258 Object value = readBinaryAnd(builder);
259 while (skipWhitespace() && (data.charAt(index) == '|')) {
260 ++index;
261 if ((index < data.length()) && (data.charAt(index) == '|'))
262 ++index;
263 value = builder.or(value, readBinaryAnd(builder));
264 }
265 return value;
266 }
267
268 /***
269 * Reads the value of a binary AND.
270 *
271 * @param builder The Builder to construct objects with.
272 *
273 * @return The value of a binary AND.
274 *
275 * @throws ParseException if no inital AND term is available.
276 */
277 private Object readBinaryAnd (Builder builder) {
278 if (!skipWhitespace())
279 throw new ParseException(
280 "No inital AND term found in '" + data + "' at " + index);
281 Object value = readUnaryNot(builder);
282 while (skipWhitespace() && (data.charAt(index) == '&')) {
283 ++index;
284 if ((index < data.length()) && (data.charAt(index) == '&'))
285 ++index;
286 value = builder.and(value, readUnaryNot(builder));
287 }
288 return value;
289 }
290
291 /***
292 * Reads the value of a unary NOT.
293 *
294 * @param builder The Builder to construct objects with.
295 *
296 * @return The value of a unary NOT.
297 *
298 * @throws ParseException if no NOT term is available.
299 */
300 private Object readUnaryNot (Builder builder) {
301 if (!skipWhitespace())
302 throw new ParseException("No NOT term found in '" + data + "' at " + index);
303 boolean not = false;
304 if (data.charAt(index) == '!') {
305 ++index;
306 not = true;
307 }
308 Object value = readStatement(builder);
309 if (not)
310 value = builder.not(value);
311 return value;
312 }
313
314 /***
315 * Reads the value of a statement.
316 *
317 * @param builder The Builder to construct objects with.
318 *
319 * @return The value of a statement.
320 *
321 * @throws ParseException if no statement is available or an unmatched
322 * parenthesis occurrs.
323 */
324 private Object readStatement (Builder builder) {
325 if (!skipWhitespace())
326 throw new ParseException("No statement found in '" + data + "' at " + index);
327 if (data.charAt(index) == '(') {
328 ++index;
329 Object value = readExpression(builder);
330 if (!skipWhitespace() || (data.charAt(index) != ')'))
331 throw new ParseException(
332 "Unpatched parenthesis in '" + data + "' at " + index);
333 ++index;
334 return value;
335 } else
336 return readUserDefined(builder);
337 }
338
339 /***
340 * Reads the value of a user-defined string.
341 *
342 * @param builder The Builder to construct objects with.
343 *
344 * @return The value of a user-defined string.
345 *
346 * @throws ParseException if the user-defined predicate is empty.
347 */
348 private Object readUserDefined (Builder builder) {
349 int dataStart = index;
350 int parenDepth = 0;
351 while (index < data.length()) {
352 char current = data.charAt(index);
353 if ((current == '&') || (current == '|')) {
354 if (parenDepth == 0)
355 break;
356 } else if (current == ')') {
357 if (parenDepth == 0)
358 break;
359 else
360 --parenDepth;
361 } else if (current == '(')
362 ++parenDepth;
363 ++index;
364 }
365 index = rtrim(data, dataStart, index);
366 if (dataStart == index)
367 throw new ParseException(
368 "Empty user-defined predicate in '" + data + "' at " + index);
369 return builder.create(data.substring(dataStart, index));
370 }
371
372 /***
373 * Skips whitespace at the current index and returns true if more text is
374 * available.
375 *
376 * @return True if more text is available.
377 */
378 private boolean skipWhitespace () {
379 return (index = ltrim(data, index, data.length())) < data.length();
380 }
381
382 /***
383 * Strategy interface used to construct in-memory representations of an
384 * expression.
385 *
386 * @author Lonnie Pryor
387 * @version $Revision: 1.1 $
388 */
389 public interface Builder {
390 /***
391 * Returns an object that is the logical OR of the supplied objects.
392 *
393 * @param left The left-hand predicate object to OR.
394 * @param right The right-hand predicate object to OR.
395 *
396 * @return An object that is the logical OR of the supplied objects.
397 */
398 Object or (Object left, Object right);
399
400 /***
401 * Returns an object that is the logical AND of the supplied objects.
402 *
403 * @param left The left-hand predicate object to AND.
404 * @param right The right-hand predicate object to AND.
405 *
406 * @return An object that is the logical AND of the supplied objects.
407 */
408 Object and (Object left, Object right);
409
410 /***
411 * Returns an object that is the logical NOT of the supplied object.
412 *
413 * @param value The predicate object to NOT.
414 *
415 * @return An object that is the logical NOT of the supplied object.
416 */
417 Object not (Object value);
418
419 /***
420 * Creates a new predicate object from the supplied string.
421 *
422 * @param data The predicate declaration.
423 *
424 * @return A new predicate object.
425 */
426 Object create (String data);
427 }
428 }
This page was automatically generated by Maven