Mercurial > hg > Members > kono > jpf-core

comparison src/main/gov/nasa/jpf/util/script/StringExpander.java @ 0:61d41facf527

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial v8 import (history reset)
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Fri, 23 Jan 2015 10:14:01 -0800
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:61d41facf527
1 /*
2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
4 * All rights reserved.
5 *
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0.
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18 package gov.nasa.jpf.util.script;
19
20
21 import java.util.LinkedList;
22 import java.util.List;
23
24 /**
25 * utility class to expand regular expression like strings. We support
26 * alternatives "<..|..>" and character categories "[.. X-Z ..]". Alternatives
27 * can be nested, char categories can include '-' ranges
28 *
29 * e.g. "a<B|X[0-1]Y>z" => aBz, aX0Yz, aX1Yz
30 *
31 * <2do> this is awfully connected to ESParser - we should really make it more generic
32 * (this is the reason why it was moved from the general gov.nasa.jpf.util to
33 * this package)
34 */
35 public class StringExpander {
36
37 public static final char META_CHAR = '`'; // starts a symbol
38
39 public static final char ALT_START_CHAR = '<';
40 public static final char ALT_END_CHAR = '>';
41 public static final char ALT_CHAR = '|';
42
43 public static final char CAT_START_CHAR = '[';
44 public static final char CAT_END_CHAR = ']';
45 public static final char CAT_CHAR = '-';
46
47 static class Exception extends RuntimeException {
48 Exception(String details){
49 super(details);
50 }
51 }
52
53 static class Token {
54 String value;
55
56 Token (String value){
57 this.value = value;
58 }
59 int length() {
60 return value.length();
61 }
62 boolean isSymbol() {
63 return false;
64 }
65 @Override
66 public String toString(){
67 return value;
68 }
69
70 }
71 static class Symbol extends Token {
72 Symbol (String s){
73 super(s);
74 }
75 @Override
76 boolean isSymbol(){
77 return true;
78 }
79 }
80
81 // our symbol tokens
82 static final Symbol CAT_START = new Symbol("CAT_START");
83 static final Symbol CAT_END = new Symbol("CAT_END");
84
85 static final Symbol ALT_START = new Symbol("ALT_START");
86 static final Symbol ALT_END = new Symbol("ALT_END");
87 static final Symbol ALT = new Symbol("ALT");
88 static final Symbol EOS = new Symbol("END");
89
90 final String src;
91 final int len;
92
93 Token token;
94 int pos;
95
96 /**
97 // a quoted symbol char version - doesn't look nice, but is more general
98 void nextToken () {
99
100 int i = pos;
101 int len = this.len;
102
103 if (i>=len){
104 token = EOS;
105
106 } else {
107 if (src.charAt(i) == META_CHAR){ // symbol
108 char c = src.charAt(++i);
109 switch (c){
110 case CAT_START_CHAR: token = CAT_START; break;
111 case CAT_END_CHAR: token = CAT_END; break;
112
113 case ALT_START_CHAR: token = ALT_START; break;
114 case ALT_CHAR: token = ALT; break;
115 case ALT_END_CHAR: token = ALT_END; break;
116 default:
117 error("illegal symbol: " + c);
118 }
119 pos += 2;
120
121 } else { // string literal
122 int j = i + 1;
123 for (; j < len && src.charAt(j) != META_CHAR; j++);
124 pos = j;
125 token = new Token(src.substring(i, j));
126 }
127 }
128 }
129 **/
130
131 private boolean isMetaChar(char c){
132 return ((c == CAT_START_CHAR) || (c == CAT_END_CHAR) ||
133 (c == ALT_START_CHAR) || (c == ALT_END_CHAR) || (c == ALT_CHAR));
134
135 }
136
137 void nextToken() {
138 int i = pos;
139 int len = this.len;
140
141 if (i>=len){
142 token = EOS;
143
144 } else {
145 char c = src.charAt(i);
146 switch (c){
147 case CAT_START_CHAR: token = CAT_START; pos++; break;
148 case CAT_END_CHAR: token = CAT_END; pos++; break;
149
150 case ALT_START_CHAR: token = ALT_START; pos++; break;
151 case ALT_CHAR: token = ALT; pos++; break;
152 case ALT_END_CHAR: token = ALT_END; pos++; break;
153
154 default:
155 int j = i + 1;
156 for (; j < len && !isMetaChar(src.charAt(j)); j++);
157 pos = j;
158 token = new Token(src.substring(i, j));
159 }
160 }
161 }
162
163 boolean match (Symbol sym){
164 if (token == sym){
165 nextToken();
166 return true;
167 } else {
168 return false;
169 }
170 }
171
172 public StringExpander (String src){
173 this.src = src;
174 this.len = src.length();
175 this.pos = 0;
176 }
177
178 List<String> addSeq (List<String> list, List<String> seq){
179 List<String> result = new LinkedList<String>();
180
181 if (list != null && list.size() > 0){
182 result.addAll(list);
183 }
184 result.addAll(seq);
185
186 return result;
187 }
188
189 List<String> addLiteral (List<String> list, String s){
190 List<String> result = new LinkedList<String>();
191
192 if (list == null || list.size() == 0){
193 result.add(s);
194
195 } else {
196 for (String e : list) {
197 result.add(e + s);
198 }
199 }
200
201 return result;
202 }
203
204 List<String> addAlt (List<String> list, List<String>alt){
205 List<String> result = new LinkedList<String>();
206
207 if (list == null || list.size() == 0){
208 result.addAll(alt);
209
210 } else {
211 for (String e : list) {
212 for (String p : alt) {
213 result.add(e + p);
214 }
215 }
216 }
217
218 return result;
219 }
220
221 List<String> addCat (List<String> list, char[] cat){
222 List<String> result = new LinkedList<String>();
223
224 if (list == null || list.size() == 0){
225 for (char c : cat){
226 result.add(Character.toString(c));
227 }
228
229 } else {
230 for (String e : list) {
231 for (char c : cat){
232 result.add(e + c);
233 }
234 }
235 }
236
237 return result;
238 }
239
240 void error (String msg){
241 throw new Exception(msg);
242 }
243
244 protected char[] createCategory(String cat){
245 char[] s = cat.toCharArray();
246 int l1 = s.length-1;
247 char[] d = s;
248
249
250 for (int i=0, j=0; i<s.length; i++){
251 char c = s[i];
252 if ((c == CAT_CHAR) && (i>0) && (i<l1)){
253 char c0 = s[i-1];
254 char c1 = s[i+1];
255 int n = c1 - c0;
256
257 int len = j + n + (s.length-i-2);
258 char[] dNew = new char[len];
259 System.arraycopy(d, 0, dNew, 0, j);
260 d = dNew;
261
262 for (int k=c0+1; k<=c1; k++){
263 d[j++] = (char)k;
264 }
265 i++;
266
267 } else {
268 d[j++] = c;
269 }
270 }
271
272 return d;
273 }
274
275 // seq := {LIT | cat | alt}*
276 // cat := `[ LIT `]
277 // alt := `< spec {`| spec}* `>
278
279 public List<String> expand() {
280 return seq();
281 }
282
283 List<String> seq() {
284 List<String> result = null;
285
286 for (nextToken(); token != EOS; ){
287 if (!token.isSymbol()){
288 result = addLiteral( result,token.value);
289 nextToken();
290
291 } else if (token == ALT_START){
292 result = addAlt( result, alt());
293
294 } else if (token == CAT_START){
295 result = addCat( result, cat());
296
297 } else {
298 break;
299 }
300 }
301
302 return result;
303 }
304
305
306 List<String> alt() {
307 List<String> result = null;
308
309 assert token == ALT_START;
310
311 do {
312 result = addSeq(result, seq());
313 } while (token == ALT);
314
315 if (!match(ALT_END)){
316 error("unterminated alternative");
317 }
318 return result;
319 }
320
321 char[] cat() {
322 char[] set = null;
323
324 assert token == CAT_START;
325
326 nextToken();
327 if (!token.isSymbol()){
328 set = createCategory(token.value);
329 nextToken();
330 }
331
332 if (!match(CAT_END)){
333 error("unterminated category");
334 }
335 return set;
336 }
337
338
339 public static void main (String[] args) {
340 //String a = "<B[0-3]C>";
341 String a = args[0];
342 System.out.println(a);
343
344 StringExpander ex = new StringExpander(a);
345
346 /**
347 for (ex.nextToken(); ex.token != EOS; ex.nextToken()){
348 System.out.println(ex.token);
349 }
350 **/
351 /**/
352 for (String s : ex.expand()) {
353 System.out.println(s);
354 }
355 /**/
356 /**
357 System.out.println(new String(ex.createCategory(args[0])));
358 **/
359 }
360 }