1 /* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 Terence Parr 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 1. Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in the 13 documentation and/or other materials provided with the distribution. 14 3. The name of the author may not be used to endorse or promote products 15 derived from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.runtime; 29 30 import java.util.*; 31 32 /** Useful for dumping out the input stream after doing some 33 * augmentation or other manipulations. 34 * 35 * You can insert stuff, replace, and delete chunks. Note that the 36 * operations are done lazily--only if you convert the buffer to a 37 * String. This is very efficient because you are not moving data around 38 * all the time. As the buffer of tokens is converted to strings, the 39 * toString() method(s) check to see if there is an operation at the 40 * current index. If so, the operation is done and then normal String 41 * rendering continues on the buffer. This is like having multiple Turing 42 * machine instruction streams (programs) operating on a single input tape. :) 43 * 44 * Since the operations are done lazily at toString-time, operations do not 45 * screw up the token index values. That is, an insert operation at token 46 * index i does not change the index values for tokens i+1..n-1. 47 * 48 * Because operations never actually alter the buffer, you may always get 49 * the original token stream back without undoing anything. Since 50 * the instructions are queued up, you can easily simulate transactions and 51 * roll back any changes if there is an error just by removing instructions. 52 * For example, 53 * 54 * CharStream input = new ANTLRFileStream("input"); 55 * TLexer lex = new TLexer(input); 56 * TokenRewriteStream tokens = new TokenRewriteStream(lex); 57 * T parser = new T(tokens); 58 * parser.startRule(); 59 * 60 * Then in the rules, you can execute 61 * Token t,u; 62 * ... 63 * input.insertAfter(t, "text to put after t");} 64 * input.insertAfter(u, "text after u");} 65 * System.out.println(tokens.toString()); 66 * 67 * Actually, you have to cast the 'input' to a TokenRewriteStream. :( 68 * 69 * You can also have multiple "instruction streams" and get multiple 70 * rewrites from a single pass over the input. Just name the instruction 71 * streams and use that name again when printing the buffer. This could be 72 * useful for generating a C file and also its header file--all from the 73 * same buffer: 74 * 75 * tokens.insertAfter("pass1", t, "text to put after t");} 76 * tokens.insertAfter("pass2", u, "text after u");} 77 * System.out.println(tokens.toString("pass1")); 78 * System.out.println(tokens.toString("pass2")); 79 * 80 * If you don't use named rewrite streams, a "default" stream is used as 81 * the first example shows. 82 */ 83 public class TokenRewriteStream extends CommonTokenStream { 84 public static final String DEFAULT_PROGRAM_NAME = "default"; 85 public static final int PROGRAM_INIT_SIZE = 100; 86 public static final int MIN_TOKEN_INDEX = 0; 87 88 // Define the rewrite operation hierarchy 89 90 public class RewriteOperation { 91 /** What index into rewrites List are we? */ 92 protected int instructionIndex; 93 /** Token buffer index. */ 94 protected int index; 95 protected Object text; 96 97 protected RewriteOperation(int index) { 98 this.index = index; 99 } 100 101 protected RewriteOperation(int index, Object text) { 102 this.index = index; 103 this.text = text; 104 } 105 /** Execute the rewrite operation by possibly adding to the buffer. 106 * Return the index of the next token to operate on. 107 */ 108 public int execute(StringBuffer buf) { 109 return index; 110 } 111 @Override 112 public String toString() { 113 String opName = getClass().getName(); 114 int $index = opName.indexOf('$'); 115 opName = opName.substring($index+1, opName.length()); 116 return "<"+opName+"@"+tokens.get(index)+ 117 ":\""+text+"\">"; 118 } 119 } 120 121 class InsertBeforeOp extends RewriteOperation { 122 public InsertBeforeOp(int index, Object text) { 123 super(index,text); 124 } 125 @Override 126 public int execute(StringBuffer buf) { 127 buf.append(text); 128 if ( tokens.get(index).getType()!=Token.EOF ) { 129 buf.append(tokens.get(index).getText()); 130 } 131 return index+1; 132 } 133 } 134 135 /** I'm going to try replacing range from x..y with (y-x)+1 ReplaceOp 136 * instructions. 137 */ 138 class ReplaceOp extends RewriteOperation { 139 protected int lastIndex; 140 public ReplaceOp(int from, int to, Object text) { 141 super(from,text); 142 lastIndex = to; 143 } 144 @Override 145 public int execute(StringBuffer buf) { 146 if ( text!=null ) { 147 buf.append(text); 148 } 149 return lastIndex+1; 150 } 151 @Override 152 public String toString() { 153 if ( text==null ) { 154 return "<DeleteOp@"+tokens.get(index)+ 155 ".."+tokens.get(lastIndex)+">"; 156 } 157 return "<ReplaceOp@"+tokens.get(index)+ 158 ".."+tokens.get(lastIndex)+":\""+text+"\">"; 159 } 160 } 161 162 /** You may have multiple, named streams of rewrite operations. 163 * I'm calling these things "programs." 164 * Maps String (name) → rewrite (List) 165 */ 166 protected Map<String, List<RewriteOperation>> programs = null; 167 168 /** Map String (program name) → Integer index */ 169 protected Map<String, Integer> lastRewriteTokenIndexes = null; 170 171 public TokenRewriteStream() { 172 init(); 173 } 174 175 protected void init() { 176 programs = new HashMap<String, List<RewriteOperation>>(); 177 programs.put(DEFAULT_PROGRAM_NAME, new ArrayList<RewriteOperation>(PROGRAM_INIT_SIZE)); 178 lastRewriteTokenIndexes = new HashMap<String, Integer>(); 179 } 180 181 public TokenRewriteStream(TokenSource tokenSource) { 182 super(tokenSource); 183 init(); 184 } 185 186 public TokenRewriteStream(TokenSource tokenSource, int channel) { 187 super(tokenSource, channel); 188 init(); 189 } 190 191 public void rollback(int instructionIndex) { 192 rollback(DEFAULT_PROGRAM_NAME, instructionIndex); 193 } 194 195 /** Rollback the instruction stream for a program so that 196 * the indicated instruction (via instructionIndex) is no 197 * longer in the stream. UNTESTED! 198 */ 199 public void rollback(String programName, int instructionIndex) { 200 List<RewriteOperation> is = programs.get(programName); 201 if ( is!=null ) { 202 programs.put(programName, is.subList(MIN_TOKEN_INDEX,instructionIndex)); 203 } 204 } 205 206 public void deleteProgram() { 207 deleteProgram(DEFAULT_PROGRAM_NAME); 208 } 209 210 /** Reset the program so that no instructions exist */ 211 public void deleteProgram(String programName) { 212 rollback(programName, MIN_TOKEN_INDEX); 213 } 214 215 public void insertAfter(Token t, Object text) { 216 insertAfter(DEFAULT_PROGRAM_NAME, t, text); 217 } 218 219 public void insertAfter(int index, Object text) { 220 insertAfter(DEFAULT_PROGRAM_NAME, index, text); 221 } 222 223 public void insertAfter(String programName, Token t, Object text) { 224 insertAfter(programName,t.getTokenIndex(), text); 225 } 226 227 public void insertAfter(String programName, int index, Object text) { 228 // to insert after, just insert before next index (even if past end) 229 insertBefore(programName,index+1, text); 230 } 231 232 public void insertBefore(Token t, Object text) { 233 insertBefore(DEFAULT_PROGRAM_NAME, t, text); 234 } 235 236 public void insertBefore(int index, Object text) { 237 insertBefore(DEFAULT_PROGRAM_NAME, index, text); 238 } 239 240 public void insertBefore(String programName, Token t, Object text) { 241 insertBefore(programName, t.getTokenIndex(), text); 242 } 243 244 public void insertBefore(String programName, int index, Object text) { 245 RewriteOperation op = new InsertBeforeOp(index,text); 246 List<? super RewriteOperation> rewrites = getProgram(programName); 247 op.instructionIndex = rewrites.size(); 248 rewrites.add(op); 249 } 250 251 public void replace(int index, Object text) { 252 replace(DEFAULT_PROGRAM_NAME, index, index, text); 253 } 254 255 public void replace(int from, int to, Object text) { 256 replace(DEFAULT_PROGRAM_NAME, from, to, text); 257 } 258 259 public void replace(Token indexT, Object text) { 260 replace(DEFAULT_PROGRAM_NAME, indexT, indexT, text); 261 } 262 263 public void replace(Token from, Token to, Object text) { 264 replace(DEFAULT_PROGRAM_NAME, from, to, text); 265 } 266 267 public void replace(String programName, int from, int to, Object text) { 268 if ( from > to || from<0 || to<0 || to >= tokens.size() ) { 269 throw new IllegalArgumentException("replace: range invalid: "+from+".."+to+"(size="+tokens.size()+")"); 270 } 271 RewriteOperation op = new ReplaceOp(from, to, text); 272 List<? super RewriteOperation> rewrites = getProgram(programName); 273 op.instructionIndex = rewrites.size(); 274 rewrites.add(op); 275 } 276 277 public void replace(String programName, Token from, Token to, Object text) { 278 replace(programName, 279 from.getTokenIndex(), 280 to.getTokenIndex(), 281 text); 282 } 283 284 public void delete(int index) { 285 delete(DEFAULT_PROGRAM_NAME, index, index); 286 } 287 288 public void delete(int from, int to) { 289 delete(DEFAULT_PROGRAM_NAME, from, to); 290 } 291 292 public void delete(Token indexT) { 293 delete(DEFAULT_PROGRAM_NAME, indexT, indexT); 294 } 295 296 public void delete(Token from, Token to) { 297 delete(DEFAULT_PROGRAM_NAME, from, to); 298 } 299 300 public void delete(String programName, int from, int to) { 301 replace(programName,from,to,null); 302 } 303 304 public void delete(String programName, Token from, Token to) { 305 replace(programName,from,to,null); 306 } 307 308 public int getLastRewriteTokenIndex() { 309 return getLastRewriteTokenIndex(DEFAULT_PROGRAM_NAME); 310 } 311 312 protected int getLastRewriteTokenIndex(String programName) { 313 Integer I = lastRewriteTokenIndexes.get(programName); 314 if ( I==null ) { 315 return -1; 316 } 317 return I; 318 } 319 320 protected void setLastRewriteTokenIndex(String programName, int i) { 321 lastRewriteTokenIndexes.put(programName, i); 322 } 323 324 protected List<RewriteOperation> getProgram(String name) { 325 List<RewriteOperation> is = programs.get(name); 326 if ( is==null ) { 327 is = initializeProgram(name); 328 } 329 return is; 330 } 331 332 private List<RewriteOperation> initializeProgram(String name) { 333 List<RewriteOperation> is = new ArrayList<RewriteOperation>(PROGRAM_INIT_SIZE); 334 programs.put(name, is); 335 return is; 336 } 337 338 public String toOriginalString() { 339 fill(); 340 return toOriginalString(MIN_TOKEN_INDEX, size()-1); 341 } 342 343 public String toOriginalString(int start, int end) { 344 StringBuilder buf = new StringBuilder(); 345 for (int i=start; i>=MIN_TOKEN_INDEX && i<=end && i<tokens.size(); i++) { 346 if ( get(i).getType()!=Token.EOF ) buf.append(get(i).getText()); 347 } 348 return buf.toString(); 349 } 350 351 @Override 352 public String toString() { 353 fill(); 354 return toString(MIN_TOKEN_INDEX, size()-1); 355 } 356 357 public String toString(String programName) { 358 fill(); 359 return toString(programName, MIN_TOKEN_INDEX, size()-1); 360 } 361 362 @Override 363 public String toString(int start, int end) { 364 return toString(DEFAULT_PROGRAM_NAME, start, end); 365 } 366 367 public String toString(String programName, int start, int end) { 368 List<RewriteOperation> rewrites = programs.get(programName); 369 370 // ensure start/end are in range 371 if ( end>tokens.size()-1 ) end = tokens.size()-1; 372 if ( start<0 ) start = 0; 373 374 if ( rewrites==null || rewrites.isEmpty() ) { 375 return toOriginalString(start,end); // no instructions to execute 376 } 377 StringBuffer buf = new StringBuffer(); 378 379 // First, optimize instruction stream 380 Map<Integer, ? extends RewriteOperation> indexToOp = reduceToSingleOperationPerIndex(rewrites); 381 382 // Walk buffer, executing instructions and emitting tokens 383 int i = start; 384 while ( i <= end && i < tokens.size() ) { 385 RewriteOperation op = indexToOp.get(i); 386 indexToOp.remove(i); // remove so any left have index size-1 387 Token t = tokens.get(i); 388 if ( op==null ) { 389 // no operation at that index, just dump token 390 if ( t.getType()!=Token.EOF ) buf.append(t.getText()); 391 i++; // move to next token 392 } 393 else { 394 i = op.execute(buf); // execute operation and skip 395 } 396 } 397 398 // include stuff after end if it's last index in buffer 399 // So, if they did an insertAfter(lastValidIndex, "foo"), include 400 // foo if end==lastValidIndex. 401 if ( end==tokens.size()-1 ) { 402 // Scan any remaining operations after last token 403 // should be included (they will be inserts). 404 for (RewriteOperation op : indexToOp.values()) { 405 if ( op.index >= tokens.size()-1 ) buf.append(op.text); 406 } 407 } 408 return buf.toString(); 409 } 410 411 /** We need to combine operations and report invalid operations (like 412 * overlapping replaces that are not completed nested). Inserts to 413 * same index need to be combined etc... Here are the cases: 414 * 415 * I.i.u I.j.v leave alone, nonoverlapping 416 * I.i.u I.i.v combine: Iivu 417 * 418 * R.i-j.u R.x-y.v | i-j in x-y delete first R 419 * R.i-j.u R.i-j.v delete first R 420 * R.i-j.u R.x-y.v | x-y in i-j ERROR 421 * R.i-j.u R.x-y.v | boundaries overlap ERROR 422 * 423 * Delete special case of replace (text==null): 424 * D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) 425 * 426 * I.i.u R.x-y.v | i in (x+1)-y delete I (since insert before 427 * we're not deleting i) 428 * I.i.u R.x-y.v | i not in (x+1)-y leave alone, nonoverlapping 429 * R.x-y.v I.i.u | i in x-y ERROR 430 * R.x-y.v I.x.u R.x-y.uv (combine, delete I) 431 * R.x-y.v I.i.u | i not in x-y leave alone, nonoverlapping 432 * 433 * I.i.u = insert u before op @ index i 434 * R.x-y.u = replace x-y indexed tokens with u 435 * 436 * First we need to examine replaces. For any replace op: 437 * 438 * 1. wipe out any insertions before op within that range. 439 * 2. Drop any replace op before that is contained completely within 440 * that range. 441 * 3. Throw exception upon boundary overlap with any previous replace. 442 * 443 * Then we can deal with inserts: 444 * 445 * 1. for any inserts to same index, combine even if not adjacent. 446 * 2. for any prior replace with same left boundary, combine this 447 * insert with replace and delete this replace. 448 * 3. throw exception if index in same range as previous replace 449 * 450 * Don't actually delete; make op null in list. Easier to walk list. 451 * Later we can throw as we add to index → op map. 452 * 453 * Note that I.2 R.2-2 will wipe out I.2 even though, technically, the 454 * inserted stuff would be before the replace range. But, if you 455 * add tokens in front of a method body '{' and then delete the method 456 * body, I think the stuff before the '{' you added should disappear too. 457 * 458 * Return a map from token index to operation. 459 */ 460 protected Map<Integer, ? extends RewriteOperation> reduceToSingleOperationPerIndex(List<? extends RewriteOperation> rewrites) { 461 // System.out.println("rewrites="+rewrites); 462 463 // WALK REPLACES 464 for (int i = 0; i < rewrites.size(); i++) { 465 RewriteOperation op = rewrites.get(i); 466 if ( op==null ) continue; 467 if ( !(op instanceof ReplaceOp) ) continue; 468 ReplaceOp rop = (ReplaceOp)rewrites.get(i); 469 // Wipe prior inserts within range 470 List<? extends InsertBeforeOp> inserts = getKindOfOps(rewrites, InsertBeforeOp.class, i); 471 for (int j = 0; j < inserts.size(); j++) { 472 InsertBeforeOp iop = inserts.get(j); 473 if ( iop.index == rop.index ) { 474 // E.g., insert before 2, delete 2..2; update replace 475 // text to include insert before, kill insert 476 rewrites.set(iop.instructionIndex, null); 477 rop.text = iop.text.toString() + (rop.text!=null?rop.text.toString():""); 478 } 479 else if ( iop.index > rop.index && iop.index <= rop.lastIndex ) { 480 // delete insert as it's a no-op. 481 rewrites.set(iop.instructionIndex, null); 482 } 483 } 484 // Drop any prior replaces contained within 485 List<? extends ReplaceOp> prevReplaces = getKindOfOps(rewrites, ReplaceOp.class, i); 486 for (int j = 0; j < prevReplaces.size(); j++) { 487 ReplaceOp prevRop = prevReplaces.get(j); 488 if ( prevRop.index>=rop.index && prevRop.lastIndex <= rop.lastIndex ) { 489 // delete replace as it's a no-op. 490 rewrites.set(prevRop.instructionIndex, null); 491 continue; 492 } 493 // throw exception unless disjoint or identical 494 boolean disjoint = 495 prevRop.lastIndex<rop.index || prevRop.index > rop.lastIndex; 496 boolean same = 497 prevRop.index==rop.index && prevRop.lastIndex==rop.lastIndex; 498 // Delete special case of replace (text==null): 499 // D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) 500 if ( prevRop.text==null && rop.text==null && !disjoint ) { 501 //System.out.println("overlapping deletes: "+prevRop+", "+rop); 502 rewrites.set(prevRop.instructionIndex, null); // kill first delete 503 rop.index = Math.min(prevRop.index, rop.index); 504 rop.lastIndex = Math.max(prevRop.lastIndex, rop.lastIndex); 505 System.out.println("new rop "+rop); 506 } 507 else if ( !disjoint && !same ) { 508 throw new IllegalArgumentException("replace op boundaries of "+rop+ 509 " overlap with previous "+prevRop); 510 } 511 } 512 } 513 514 // WALK INSERTS 515 for (int i = 0; i < rewrites.size(); i++) { 516 RewriteOperation op = rewrites.get(i); 517 if ( op==null ) continue; 518 if ( !(op instanceof InsertBeforeOp) ) continue; 519 InsertBeforeOp iop = (InsertBeforeOp)rewrites.get(i); 520 // combine current insert with prior if any at same index 521 List<? extends InsertBeforeOp> prevInserts = getKindOfOps(rewrites, InsertBeforeOp.class, i); 522 for (int j = 0; j < prevInserts.size(); j++) { 523 InsertBeforeOp prevIop = prevInserts.get(j); 524 if ( prevIop.index == iop.index ) { // combine objects 525 // convert to strings...we're in process of toString'ing 526 // whole token buffer so no lazy eval issue with any templates 527 iop.text = catOpText(iop.text,prevIop.text); 528 // delete redundant prior insert 529 rewrites.set(prevIop.instructionIndex, null); 530 } 531 } 532 // look for replaces where iop.index is in range; error 533 List<? extends ReplaceOp> prevReplaces = getKindOfOps(rewrites, ReplaceOp.class, i); 534 for (int j = 0; j < prevReplaces.size(); j++) { 535 ReplaceOp rop = prevReplaces.get(j); 536 if ( iop.index == rop.index ) { 537 rop.text = catOpText(iop.text,rop.text); 538 rewrites.set(i, null); // delete current insert 539 continue; 540 } 541 if ( iop.index >= rop.index && iop.index <= rop.lastIndex ) { 542 throw new IllegalArgumentException("insert op "+iop+ 543 " within boundaries of previous "+rop); 544 } 545 } 546 } 547 // System.out.println("rewrites after="+rewrites); 548 Map<Integer, RewriteOperation> m = new HashMap<Integer, RewriteOperation>(); 549 for (int i = 0; i < rewrites.size(); i++) { 550 RewriteOperation op = rewrites.get(i); 551 if ( op==null ) continue; // ignore deleted ops 552 if ( m.get(op.index)!=null ) { 553 throw new Error("should only be one op per index"); 554 } 555 m.put(op.index, op); 556 } 557 //System.out.println("index to op: "+m); 558 return m; 559 } 560 561 protected String catOpText(Object a, Object b) { 562 String x = ""; 563 String y = ""; 564 if ( a!=null ) x = a.toString(); 565 if ( b!=null ) y = b.toString(); 566 return x+y; 567 } 568 protected <T extends RewriteOperation> List<? extends T> getKindOfOps(List<? extends RewriteOperation> rewrites, Class<T> kind) { 569 return getKindOfOps(rewrites, kind, rewrites.size()); 570 } 571 572 /** Get all operations before an index of a particular kind */ 573 protected <T extends RewriteOperation> List<? extends T> getKindOfOps(List<? extends RewriteOperation> rewrites, Class<T> kind, int before) { 574 List<T> ops = new ArrayList<T>(); 575 for (int i=0; i<before && i<rewrites.size(); i++) { 576 RewriteOperation op = rewrites.get(i); 577 if ( op==null ) continue; // ignore deleted 578 if ( kind.isInstance(op) ) ops.add(kind.cast(op)); 579 } 580 return ops; 581 } 582 583 public String toDebugString() { 584 return toDebugString(MIN_TOKEN_INDEX, size()-1); 585 } 586 587 public String toDebugString(int start, int end) { 588 StringBuilder buf = new StringBuilder(); 589 for (int i=start; i>=MIN_TOKEN_INDEX && i<=end && i<tokens.size(); i++) { 590 buf.append(get(i)); 591 } 592 return buf.toString(); 593 } 594 } 595
