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 */ 28package org.antlr.runtime; 29 30import 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 */ 83public 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 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 public String toString() { 112 String opName = getClass().getName(); 113 int $index = opName.indexOf('$'); 114 opName = opName.substring($index+1, opName.length()); 115 return "<"+opName+"@"+tokens.get(index)+ 116 ":\""+text+"\">"; 117 } 118 } 119 120 class InsertBeforeOp extends RewriteOperation { 121 public InsertBeforeOp(int index, Object text) { 122 super(index,text); 123 } 124 public int execute(StringBuffer buf) { 125 buf.append(text); 126 if ( tokens.get(index).getType()!=Token.EOF ) { 127 buf.append(tokens.get(index).getText()); 128 } 129 return index+1; 130 } 131 } 132 133 /** I'm going to try replacing range from x..y with (y-x)+1 ReplaceOp 134 * instructions. 135 */ 136 class ReplaceOp extends RewriteOperation { 137 protected int lastIndex; 138 public ReplaceOp(int from, int to, Object text) { 139 super(from,text); 140 lastIndex = to; 141 } 142 public int execute(StringBuffer buf) { 143 if ( text!=null ) { 144 buf.append(text); 145 } 146 return lastIndex+1; 147 } 148 public String toString() { 149 if ( text==null ) { 150 return "<DeleteOp@"+tokens.get(index)+ 151 ".."+tokens.get(lastIndex)+">"; 152 } 153 return "<ReplaceOp@"+tokens.get(index)+ 154 ".."+tokens.get(lastIndex)+":\""+text+"\">"; 155 } 156 } 157 158 /** You may have multiple, named streams of rewrite operations. 159 * I'm calling these things "programs." 160 * Maps String (name) -> rewrite (List) 161 */ 162 protected Map programs = null; 163 164 /** Map String (program name) -> Integer index */ 165 protected Map lastRewriteTokenIndexes = null; 166 167 public TokenRewriteStream() { 168 init(); 169 } 170 171 protected void init() { 172 programs = new HashMap(); 173 programs.put(DEFAULT_PROGRAM_NAME, new ArrayList(PROGRAM_INIT_SIZE)); 174 lastRewriteTokenIndexes = new HashMap(); 175 } 176 177 public TokenRewriteStream(TokenSource tokenSource) { 178 super(tokenSource); 179 init(); 180 } 181 182 public TokenRewriteStream(TokenSource tokenSource, int channel) { 183 super(tokenSource, channel); 184 init(); 185 } 186 187 public void rollback(int instructionIndex) { 188 rollback(DEFAULT_PROGRAM_NAME, instructionIndex); 189 } 190 191 /** Rollback the instruction stream for a program so that 192 * the indicated instruction (via instructionIndex) is no 193 * longer in the stream. UNTESTED! 194 */ 195 public void rollback(String programName, int instructionIndex) { 196 List is = (List)programs.get(programName); 197 if ( is!=null ) { 198 programs.put(programName, is.subList(MIN_TOKEN_INDEX,instructionIndex)); 199 } 200 } 201 202 public void deleteProgram() { 203 deleteProgram(DEFAULT_PROGRAM_NAME); 204 } 205 206 /** Reset the program so that no instructions exist */ 207 public void deleteProgram(String programName) { 208 rollback(programName, MIN_TOKEN_INDEX); 209 } 210 211 public void insertAfter(Token t, Object text) { 212 insertAfter(DEFAULT_PROGRAM_NAME, t, text); 213 } 214 215 public void insertAfter(int index, Object text) { 216 insertAfter(DEFAULT_PROGRAM_NAME, index, text); 217 } 218 219 public void insertAfter(String programName, Token t, Object text) { 220 insertAfter(programName,t.getTokenIndex(), text); 221 } 222 223 public void insertAfter(String programName, int index, Object text) { 224 // to insert after, just insert before next index (even if past end) 225 insertBefore(programName,index+1, text); 226 } 227 228 public void insertBefore(Token t, Object text) { 229 insertBefore(DEFAULT_PROGRAM_NAME, t, text); 230 } 231 232 public void insertBefore(int index, Object text) { 233 insertBefore(DEFAULT_PROGRAM_NAME, index, text); 234 } 235 236 public void insertBefore(String programName, Token t, Object text) { 237 insertBefore(programName, t.getTokenIndex(), text); 238 } 239 240 public void insertBefore(String programName, int index, Object text) { 241 RewriteOperation op = new InsertBeforeOp(index,text); 242 List rewrites = getProgram(programName); 243 op.instructionIndex = rewrites.size(); 244 rewrites.add(op); 245 } 246 247 public void replace(int index, Object text) { 248 replace(DEFAULT_PROGRAM_NAME, index, index, text); 249 } 250 251 public void replace(int from, int to, Object text) { 252 replace(DEFAULT_PROGRAM_NAME, from, to, text); 253 } 254 255 public void replace(Token indexT, Object text) { 256 replace(DEFAULT_PROGRAM_NAME, indexT, indexT, text); 257 } 258 259 public void replace(Token from, Token to, Object text) { 260 replace(DEFAULT_PROGRAM_NAME, from, to, text); 261 } 262 263 public void replace(String programName, int from, int to, Object text) { 264 if ( from > to || from<0 || to<0 || to >= tokens.size() ) { 265 throw new IllegalArgumentException("replace: range invalid: "+from+".."+to+"(size="+tokens.size()+")"); 266 } 267 RewriteOperation op = new ReplaceOp(from, to, text); 268 List rewrites = getProgram(programName); 269 op.instructionIndex = rewrites.size(); 270 rewrites.add(op); 271 } 272 273 public void replace(String programName, Token from, Token to, Object text) { 274 replace(programName, 275 from.getTokenIndex(), 276 to.getTokenIndex(), 277 text); 278 } 279 280 public void delete(int index) { 281 delete(DEFAULT_PROGRAM_NAME, index, index); 282 } 283 284 public void delete(int from, int to) { 285 delete(DEFAULT_PROGRAM_NAME, from, to); 286 } 287 288 public void delete(Token indexT) { 289 delete(DEFAULT_PROGRAM_NAME, indexT, indexT); 290 } 291 292 public void delete(Token from, Token to) { 293 delete(DEFAULT_PROGRAM_NAME, from, to); 294 } 295 296 public void delete(String programName, int from, int to) { 297 replace(programName,from,to,null); 298 } 299 300 public void delete(String programName, Token from, Token to) { 301 replace(programName,from,to,null); 302 } 303 304 public int getLastRewriteTokenIndex() { 305 return getLastRewriteTokenIndex(DEFAULT_PROGRAM_NAME); 306 } 307 308 protected int getLastRewriteTokenIndex(String programName) { 309 Integer I = (Integer)lastRewriteTokenIndexes.get(programName); 310 if ( I==null ) { 311 return -1; 312 } 313 return I.intValue(); 314 } 315 316 protected void setLastRewriteTokenIndex(String programName, int i) { 317 lastRewriteTokenIndexes.put(programName, new Integer(i)); 318 } 319 320 protected List getProgram(String name) { 321 List is = (List)programs.get(name); 322 if ( is==null ) { 323 is = initializeProgram(name); 324 } 325 return is; 326 } 327 328 private List initializeProgram(String name) { 329 List is = new ArrayList(PROGRAM_INIT_SIZE); 330 programs.put(name, is); 331 return is; 332 } 333 334 public String toOriginalString() { 335 fill(); 336 return toOriginalString(MIN_TOKEN_INDEX, size()-1); 337 } 338 339 public String toOriginalString(int start, int end) { 340 StringBuffer buf = new StringBuffer(); 341 for (int i=start; i>=MIN_TOKEN_INDEX && i<=end && i<tokens.size(); i++) { 342 if ( get(i).getType()!=Token.EOF ) buf.append(get(i).getText()); 343 } 344 return buf.toString(); 345 } 346 347 public String toString() { 348 fill(); 349 return toString(MIN_TOKEN_INDEX, size()-1); 350 } 351 352 public String toString(String programName) { 353 fill(); 354 return toString(programName, MIN_TOKEN_INDEX, size()-1); 355 } 356 357 public String toString(int start, int end) { 358 return toString(DEFAULT_PROGRAM_NAME, start, end); 359 } 360 361 public String toString(String programName, int start, int end) { 362 List rewrites = (List)programs.get(programName); 363 364 // ensure start/end are in range 365 if ( end>tokens.size()-1 ) end = tokens.size()-1; 366 if ( start<0 ) start = 0; 367 368 if ( rewrites==null || rewrites.size()==0 ) { 369 return toOriginalString(start,end); // no instructions to execute 370 } 371 StringBuffer buf = new StringBuffer(); 372 373 // First, optimize instruction stream 374 Map indexToOp = reduceToSingleOperationPerIndex(rewrites); 375 376 // Walk buffer, executing instructions and emitting tokens 377 int i = start; 378 while ( i <= end && i < tokens.size() ) { 379 RewriteOperation op = (RewriteOperation)indexToOp.get(new Integer(i)); 380 indexToOp.remove(new Integer(i)); // remove so any left have index size-1 381 Token t = (Token) tokens.get(i); 382 if ( op==null ) { 383 // no operation at that index, just dump token 384 if ( t.getType()!=Token.EOF ) buf.append(t.getText()); 385 i++; // move to next token 386 } 387 else { 388 i = op.execute(buf); // execute operation and skip 389 } 390 } 391 392 // include stuff after end if it's last index in buffer 393 // So, if they did an insertAfter(lastValidIndex, "foo"), include 394 // foo if end==lastValidIndex. 395 if ( end==tokens.size()-1 ) { 396 // Scan any remaining operations after last token 397 // should be included (they will be inserts). 398 Iterator it = indexToOp.values().iterator(); 399 while (it.hasNext()) { 400 RewriteOperation op = (RewriteOperation)it.next(); 401 if ( op.index >= tokens.size()-1 ) buf.append(op.text); 402 } 403 } 404 return buf.toString(); 405 } 406 407 /** We need to combine operations and report invalid operations (like 408 * overlapping replaces that are not completed nested). Inserts to 409 * same index need to be combined etc... Here are the cases: 410 * 411 * I.i.u I.j.v leave alone, nonoverlapping 412 * I.i.u I.i.v combine: Iivu 413 * 414 * R.i-j.u R.x-y.v | i-j in x-y delete first R 415 * R.i-j.u R.i-j.v delete first R 416 * R.i-j.u R.x-y.v | x-y in i-j ERROR 417 * R.i-j.u R.x-y.v | boundaries overlap ERROR 418 * 419 * Delete special case of replace (text==null): 420 * D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) 421 * 422 * I.i.u R.x-y.v | i in (x+1)-y delete I (since insert before 423 * we're not deleting i) 424 * I.i.u R.x-y.v | i not in (x+1)-y leave alone, nonoverlapping 425 * R.x-y.v I.i.u | i in x-y ERROR 426 * R.x-y.v I.x.u R.x-y.uv (combine, delete I) 427 * R.x-y.v I.i.u | i not in x-y leave alone, nonoverlapping 428 * 429 * I.i.u = insert u before op @ index i 430 * R.x-y.u = replace x-y indexed tokens with u 431 * 432 * First we need to examine replaces. For any replace op: 433 * 434 * 1. wipe out any insertions before op within that range. 435 * 2. Drop any replace op before that is contained completely within 436 * that range. 437 * 3. Throw exception upon boundary overlap with any previous replace. 438 * 439 * Then we can deal with inserts: 440 * 441 * 1. for any inserts to same index, combine even if not adjacent. 442 * 2. for any prior replace with same left boundary, combine this 443 * insert with replace and delete this replace. 444 * 3. throw exception if index in same range as previous replace 445 * 446 * Don't actually delete; make op null in list. Easier to walk list. 447 * Later we can throw as we add to index -> op map. 448 * 449 * Note that I.2 R.2-2 will wipe out I.2 even though, technically, the 450 * inserted stuff would be before the replace range. But, if you 451 * add tokens in front of a method body '{' and then delete the method 452 * body, I think the stuff before the '{' you added should disappear too. 453 * 454 * Return a map from token index to operation. 455 */ 456 protected Map reduceToSingleOperationPerIndex(List rewrites) { 457// System.out.println("rewrites="+rewrites); 458 459 // WALK REPLACES 460 for (int i = 0; i < rewrites.size(); i++) { 461 RewriteOperation op = (RewriteOperation)rewrites.get(i); 462 if ( op==null ) continue; 463 if ( !(op instanceof ReplaceOp) ) continue; 464 ReplaceOp rop = (ReplaceOp)rewrites.get(i); 465 // Wipe prior inserts within range 466 List inserts = getKindOfOps(rewrites, InsertBeforeOp.class, i); 467 for (int j = 0; j < inserts.size(); j++) { 468 InsertBeforeOp iop = (InsertBeforeOp) inserts.get(j); 469 if ( iop.index == rop.index ) { 470 // E.g., insert before 2, delete 2..2; update replace 471 // text to include insert before, kill insert 472 rewrites.set(iop.instructionIndex, null); 473 rop.text = iop.text.toString() + (rop.text!=null?rop.text.toString():""); 474 } 475 else if ( iop.index > rop.index && iop.index <= rop.lastIndex ) { 476 // delete insert as it's a no-op. 477 rewrites.set(iop.instructionIndex, null); 478 } 479 } 480 // Drop any prior replaces contained within 481 List prevReplaces = getKindOfOps(rewrites, ReplaceOp.class, i); 482 for (int j = 0; j < prevReplaces.size(); j++) { 483 ReplaceOp prevRop = (ReplaceOp) prevReplaces.get(j); 484 if ( prevRop.index>=rop.index && prevRop.lastIndex <= rop.lastIndex ) { 485 // delete replace as it's a no-op. 486 rewrites.set(prevRop.instructionIndex, null); 487 continue; 488 } 489 // throw exception unless disjoint or identical 490 boolean disjoint = 491 prevRop.lastIndex<rop.index || prevRop.index > rop.lastIndex; 492 boolean same = 493 prevRop.index==rop.index && prevRop.lastIndex==rop.lastIndex; 494 // Delete special case of replace (text==null): 495 // D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) 496 if ( prevRop.text==null && rop.text==null && !disjoint ) { 497 //System.out.println("overlapping deletes: "+prevRop+", "+rop); 498 rewrites.set(prevRop.instructionIndex, null); // kill first delete 499 rop.index = Math.min(prevRop.index, rop.index); 500 rop.lastIndex = Math.max(prevRop.lastIndex, rop.lastIndex); 501 System.out.println("new rop "+rop); 502 } 503 else if ( !disjoint && !same ) { 504 throw new IllegalArgumentException("replace op boundaries of "+rop+ 505 " overlap with previous "+prevRop); 506 } 507 } 508 } 509 510 // WALK INSERTS 511 for (int i = 0; i < rewrites.size(); i++) { 512 RewriteOperation op = (RewriteOperation)rewrites.get(i); 513 if ( op==null ) continue; 514 if ( !(op instanceof InsertBeforeOp) ) continue; 515 InsertBeforeOp iop = (InsertBeforeOp)rewrites.get(i); 516 // combine current insert with prior if any at same index 517 List prevInserts = getKindOfOps(rewrites, InsertBeforeOp.class, i); 518 for (int j = 0; j < prevInserts.size(); j++) { 519 InsertBeforeOp prevIop = (InsertBeforeOp) prevInserts.get(j); 520 if ( prevIop.index == iop.index ) { // combine objects 521 // convert to strings...we're in process of toString'ing 522 // whole token buffer so no lazy eval issue with any templates 523 iop.text = catOpText(iop.text,prevIop.text); 524 // delete redundant prior insert 525 rewrites.set(prevIop.instructionIndex, null); 526 } 527 } 528 // look for replaces where iop.index is in range; error 529 List prevReplaces = getKindOfOps(rewrites, ReplaceOp.class, i); 530 for (int j = 0; j < prevReplaces.size(); j++) { 531 ReplaceOp rop = (ReplaceOp) prevReplaces.get(j); 532 if ( iop.index == rop.index ) { 533 rop.text = catOpText(iop.text,rop.text); 534 rewrites.set(i, null); // delete current insert 535 continue; 536 } 537 if ( iop.index >= rop.index && iop.index <= rop.lastIndex ) { 538 throw new IllegalArgumentException("insert op "+iop+ 539 " within boundaries of previous "+rop); 540 } 541 } 542 } 543 // System.out.println("rewrites after="+rewrites); 544 Map m = new HashMap(); 545 for (int i = 0; i < rewrites.size(); i++) { 546 RewriteOperation op = (RewriteOperation)rewrites.get(i); 547 if ( op==null ) continue; // ignore deleted ops 548 if ( m.get(new Integer(op.index))!=null ) { 549 throw new Error("should only be one op per index"); 550 } 551 m.put(new Integer(op.index), op); 552 } 553 //System.out.println("index to op: "+m); 554 return m; 555 } 556 557 protected String catOpText(Object a, Object b) { 558 String x = ""; 559 String y = ""; 560 if ( a!=null ) x = a.toString(); 561 if ( b!=null ) y = b.toString(); 562 return x+y; 563 } 564 protected List getKindOfOps(List rewrites, Class kind) { 565 return getKindOfOps(rewrites, kind, rewrites.size()); 566 } 567 568 /** Get all operations before an index of a particular kind */ 569 protected List getKindOfOps(List rewrites, Class kind, int before) { 570 List ops = new ArrayList(); 571 for (int i=0; i<before && i<rewrites.size(); i++) { 572 RewriteOperation op = (RewriteOperation)rewrites.get(i); 573 if ( op==null ) continue; // ignore deleted 574 if ( op.getClass() == kind ) ops.add(op); 575 } 576 return ops; 577 } 578 579 public String toDebugString() { 580 return toDebugString(MIN_TOKEN_INDEX, size()-1); 581 } 582 583 public String toDebugString(int start, int end) { 584 StringBuffer buf = new StringBuffer(); 585 for (int i=start; i>=MIN_TOKEN_INDEX && i<=end && i<tokens.size(); i++) { 586 buf.append(get(i)); 587 } 588 return buf.toString(); 589 } 590} 591