Experiments/Attic/Rook/Castle.Rook.Compiler/Parser/antlr/TokenStreamRewriteEngine.cs

   1 namespace antlr
   2 {
   3         /* ANTLR Translator Generator
   4          * Project led by Terence Parr at http://www.jGuru.com
   5          * Software rights: http://www.antlr.org/license.html
   6          */
   7
   8         //
   9         // ANTLR C# Code Generator by Micheal Jordan
  10         //                            Kunle Odutola       : kunle UNDERSCORE odutola AT hotmail DOT com
  11         //                            Anthony Oguntimehin
  12         //
  13
  14         using System;
  15         using IList             = System.Collections.IList;
  16         using IDictionary       = System.Collections.IDictionary;
  17         using ArrayList         = System.Collections.ArrayList;
  18         using Hashtable         = System.Collections.Hashtable;
  19         using IComparer         = System.Collections.IComparer;
  20         using StringBuilder = System.Text.StringBuilder;
  21         using BitSet            = antlr.collections.impl.BitSet;
  22
  23         /// <summary>
  24         /// This token stream tracks the *entire* token stream coming from
  25         /// a lexer, but does not pass on the whitespace (or whatever else
  26         /// you want to discard) to the parser.
  27         /// </summary>
  28         /// <remarks>
  29         /// <para>
  30         /// This class can then be asked for the ith token in the input stream.
  31         /// Useful for dumping out the input stream exactly after doing some
  32         /// augmentation or other manipulations.  Tokens are index from 0..n-1
  33         /// </para>
  34         /// <para>
  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         /// </para>
  44         /// <para>
  45         /// Since the operations are done lazily at toString-time, operations do not
  46         /// screw up the token index values.  That is, an insert operation at token
  47         /// index i does not change the index values for tokens i+1..n-1.
  48         /// </para>
  49         /// <para>
  50         /// Because operations never actually alter the buffer, you may always get
  51         /// the original token stream back without undoing anything.  Since
  52         /// the instructions are queued up, you can easily simulate transactions and
  53         /// roll back any changes if there is an error just by removing instructions.
  54         /// For example,
  55         /// </para>
  56         /// <example>For example:
  57         /// <code>
  58         /// TokenStreamRewriteEngine rewriteEngine = new TokenStreamRewriteEngine(lexer);
  59         /// JavaRecognizer           parser        = new JavaRecognizer(rewriteEngine);
  60         /// ...
  61         /// rewriteEngine.insertAfter("pass1", t, "foobar");}
  62         /// rewriteEngine.insertAfter("pass2", u, "start");}
  63         /// System.Console.Out.WriteLine(rewriteEngine.ToString("pass1"));
  64         /// System.Console.Out.WriteLine(rewriteEngine.ToString("pass2"));
  65         /// </code>
  66         /// </example>
  67         /// <para>
  68         /// You can also have multiple "instruction streams" and get multiple
  69         /// rewrites from a single pass over the input.  Just name the instruction
  70         /// streams and use that name again when printing the buffer.  This could be
  71         /// useful for generating a C file and also its header file--all from the
  72         /// same buffer.
  73         /// </para>
  74         /// <para>
  75         /// If you don't use named rewrite streams, a "default" stream is used.
  76         /// </para>
  77         /// <para>
  78         /// Terence Parr, parrt@cs.usfca.edu
  79         /// University of San Francisco
  80         /// February 2004
  81         /// </para>
  82         /// </remarks>
  83         public class TokenStreamRewriteEngine : TokenStream
  84         {
  85                 public const int MIN_TOKEN_INDEX = 0;
  86
  87                 protected class RewriteOperation
  88                 {
  89                         protected internal int          index;
  90                         protected internal string       text;
  91
  92                         protected RewriteOperation(int index, string text)
  93                         {
  94                                 this.index = index;
  95                                 this.text  = text;
  96                         }
  97
  98                         /// <summary>
  99                         /// Execute the rewrite operation by possibly adding to the buffer.
 100                         /// </summary>
 101                         /// <param name="buf">rewrite buffer</param>
 102                         /// <returns>The index of the next token to operate on.</returns>
 103                         public virtual int execute(StringBuilder buf)
 104                         {
 105                                 return index;
 106                         }
 107                 }
 108
 109                 protected class InsertBeforeOp : RewriteOperation
 110                 {
 111                         public InsertBeforeOp(int index, string text) : base(index, text)
 112                         {
 113                         }
 114
 115                         public override int execute(StringBuilder buf)
 116                         {
 117                                 buf.Append(text);
 118                                 return index;
 119                         }
 120                 }
 121
 122                 protected class ReplaceOp : RewriteOperation
 123                 {
 124                         protected int lastIndex;
 125
 126                         public ReplaceOp(int from, int to, string text) : base(from, text)
 127                         {
 128                                 lastIndex = to;
 129                         }
 130
 131                         public override int execute(StringBuilder buf)
 132                         {
 133                                 if ( text != null )
 134                                 {
 135                                         buf.Append(text);
 136                                 }
 137                                 return lastIndex+1;
 138                         }
 139                 }
 140
 141                 protected class DeleteOp : ReplaceOp
 142                 {
 143                         public DeleteOp(int from, int to) : base(from, to, null)
 144                         {
 145                         }
 146                 }
 147
 148                 public const string     DEFAULT_PROGRAM_NAME = "default";
 149                 public const int                PROGRAM_INIT_SIZE       = 100;
 150
 151                 /// <summary>
 152                 /// Track the incoming list of tokens
 153                 /// </summary>
 154                 protected IList tokens;
 155
 156                 /// <summary>
 157                 /// You may have multiple, named streams of rewrite operations.
 158                 /// I'm calling these things "programs."
 159                 /// Maps string (name) -> rewrite (List)
 160                 /// </summary>
 161                 protected IDictionary programs = null;
 162
 163                 /// <summary>
 164                 /// Map string (program name) -> Integer index
 165                 /// </summary>
 166                 protected IDictionary lastRewriteTokenIndexes = null;
 167
 168                 /// <summary>
 169                 /// track index of tokens
 170                 /// </summary>
 171                 protected int index = MIN_TOKEN_INDEX;
 172
 173                 /// <summary>
 174                 /// Who do we suck tokens from?
 175                 /// </summary>
 176                 protected TokenStream stream;
 177
 178                 /// <summary>
 179                 /// Which (whitespace) token(s) to throw out
 180                 /// </summary>
 181                 protected BitSet discardMask = new BitSet();
 182
 183                 public TokenStreamRewriteEngine(TokenStream upstream) : this(upstream, 1000)
 184                 {
 185                 }
 186
 187                 public TokenStreamRewriteEngine(TokenStream upstream, int initialSize)
 188                 {
 189                         stream   = upstream;
 190                         tokens   = new ArrayList(initialSize);
 191                         programs = new Hashtable();
 192                         programs[DEFAULT_PROGRAM_NAME]  = new ArrayList(PROGRAM_INIT_SIZE);
 193                         lastRewriteTokenIndexes                 = new Hashtable();
 194                 }
 195
 196                 public IToken nextToken()                               // throws TokenStreamException
 197                 {
 198                         TokenWithIndex t;
 199
 200                         // suck tokens until end of stream or we find a non-discarded token
 201                         do
 202                         {
 203                                 t = (TokenWithIndex) stream.nextToken();
 204                                 if ( t != null )
 205                                 {
 206                                         t.setIndex(index);  // what is t's index in list?
 207                                         if ( t.Type != Token.EOF_TYPE )
 208                                         {
 209                                                 tokens.Add(t);  // track all tokens except EOF
 210                                         }
 211                                         index++;                        // move to next position
 212                                 }
 213                         } while ( (t != null) && (discardMask.member(t.Type)) );
 214
 215                         return t;
 216                 }
 217
 218                 public void rollback(int instructionIndex)
 219                 {
 220                         rollback(DEFAULT_PROGRAM_NAME, instructionIndex);
 221                 }
 222
 223                 /// <summary>
 224                 /// Rollback the instruction stream for a program so that
 225                 /// the indicated instruction (via instructionIndex) is no
 226                 /// longer in the stream.
 227                 /// </summary>
 228                 /// <remarks>
 229                 /// UNTESTED!
 230                 /// </remarks>
 231                 /// <param name="programName"></param>
 232                 /// <param name="instructionIndex"></param>
 233                 public void rollback(string programName, int instructionIndex)
 234                 {
 235                         ArrayList il = (ArrayList) programs[programName];
 236                         if ( il != null )
 237                         {
 238                                 programs[programName] = il.GetRange(MIN_TOKEN_INDEX, (instructionIndex - MIN_TOKEN_INDEX));
 239                         }
 240                 }
 241
 242                 public void deleteProgram()
 243                 {
 244                         deleteProgram(DEFAULT_PROGRAM_NAME);
 245                 }
 246
 247                 /// <summary>
 248                 /// Reset the program so that no instructions exist
 249                 /// </summary>
 250                 /// <param name="programName"></param>
 251                 public void deleteProgram(string programName)
 252                 {
 253                         rollback(programName, MIN_TOKEN_INDEX);
 254                 }
 255
 256                 /// <summary>
 257                 /// If op.index > lastRewriteTokenIndexes, just add to the end.
 258                 /// Otherwise, do linear
 259                 /// </summary>
 260                 /// <param name="op"></param>
 261                 protected void addToSortedRewriteList(RewriteOperation op)
 262                 {
 263                         addToSortedRewriteList(DEFAULT_PROGRAM_NAME, op);
 264                 }
 265
 266                 protected void addToSortedRewriteList(string programName, RewriteOperation op)
 267                 {
 268                         ArrayList rewrites = (ArrayList) getProgram(programName);
 269                         // if at or beyond last op's index, just append
 270                         if ( op.index >= getLastRewriteTokenIndex(programName) )
 271                         {
 272                                 rewrites.Add(op); // append to list of operations
 273                                 // record the index of this operation for next time through
 274                                 setLastRewriteTokenIndex(programName, op.index);
 275                                 return;
 276                         }
 277                         // not after the last one, so must insert to ordered list
 278                         int pos = rewrites.BinarySearch(op, RewriteOperationComparer.Default);
 279                         if (pos < 0)
 280                         {
 281                                 rewrites.Insert(-pos-1, op);
 282                         }
 283                 }
 284
 285                 public void insertAfter(IToken t, string text)
 286                 {
 287                         insertAfter(DEFAULT_PROGRAM_NAME, t, text);
 288                 }
 289
 290                 public void insertAfter(int index, string text)
 291                 {
 292                         insertAfter(DEFAULT_PROGRAM_NAME, index, text);
 293                 }
 294
 295                 public void insertAfter(string programName, IToken t, string text)
 296                 {
 297                         insertAfter(programName,((TokenWithIndex) t).getIndex(), text);
 298                 }
 299
 300                 public void insertAfter(string programName, int index, string text)
 301                 {
 302                         // to insert after, just insert before next index (even if past end)
 303                         insertBefore(programName, index+1, text);
 304                 }
 305
 306                 public void insertBefore(IToken t, string text)
 307                 {
 308                         insertBefore(DEFAULT_PROGRAM_NAME, t, text);
 309                 }
 310
 311                 public void insertBefore(int index, string text)
 312                 {
 313                         insertBefore(DEFAULT_PROGRAM_NAME, index, text);
 314                 }
 315
 316                 public void insertBefore(string programName, IToken t, string text)
 317                 {
 318                         insertBefore(programName, ((TokenWithIndex) t).getIndex(), text);
 319                 }
 320
 321                 public void insertBefore(string programName, int index, string text)
 322                 {
 323                         addToSortedRewriteList(programName, new InsertBeforeOp(index, text));
 324                 }
 325
 326                 public void replace(int index, string text)
 327                 {
 328                         replace(DEFAULT_PROGRAM_NAME, index, index, text);
 329                 }
 330
 331                 public void replace(int from, int to, string text)
 332                 {
 333                         replace(DEFAULT_PROGRAM_NAME, from, to, text);
 334                 }
 335
 336                 public void replace(IToken indexT, string text)
 337                 {
 338                         replace(DEFAULT_PROGRAM_NAME, indexT, indexT, text);
 339                 }
 340
 341                 public void replace(IToken from, IToken to, string text)
 342                 {
 343                         replace(DEFAULT_PROGRAM_NAME, from, to, text);
 344                 }
 345
 346                 public void replace(string programName, int from, int to, string text)
 347                 {
 348                         addToSortedRewriteList(new ReplaceOp(from, to, text));
 349                 }
 350
 351                 public void replace(string programName, IToken from, IToken to, string text)
 352                 {
 353                         replace(programName,
 354                                 ((TokenWithIndex) from).getIndex(),
 355                                 ((TokenWithIndex) to).getIndex(),
 356                                 text);
 357                 }
 358
 359                 public void delete(int index)
 360                 {
 361                         delete(DEFAULT_PROGRAM_NAME, index, index);
 362                 }
 363
 364                 public void delete(int from, int to)
 365                 {
 366                         delete(DEFAULT_PROGRAM_NAME, from, to);
 367                 }
 368
 369                 public void delete(IToken indexT)
 370                 {
 371                         delete(DEFAULT_PROGRAM_NAME, indexT, indexT);
 372                 }
 373
 374                 public void delete(IToken from, IToken to)
 375                 {
 376                         delete(DEFAULT_PROGRAM_NAME, from, to);
 377                 }
 378
 379                 public void delete(string programName, int from, int to)
 380                 {
 381                         replace(programName, from, to, null);
 382                 }
 383
 384                 public void delete(string programName, IToken from, IToken to)
 385                 {
 386                         replace(programName, from, to, null);
 387                 }
 388
 389                 public void discard(int ttype)
 390                 {
 391                         discardMask.add(ttype);
 392                 }
 393
 394                 public TokenWithIndex getToken(int i)
 395                 {
 396                         return (TokenWithIndex) tokens[i];
 397                 }
 398
 399                 public int getTokenStreamSize()
 400                 {
 401                         return tokens.Count;
 402                 }
 403
 404                 public string ToOriginalString()
 405                 {
 406                         return ToOriginalString(MIN_TOKEN_INDEX, getTokenStreamSize()-1);
 407                 }
 408
 409                 public string ToOriginalString(int start, int end)
 410                 {
 411                         StringBuilder buf = new StringBuilder();
 412                         for (int i = start; (i >= MIN_TOKEN_INDEX) && (i <= end) && (i < tokens.Count); i++)
 413                         {
 414                                 buf.Append(getToken(i).getText());
 415                         }
 416                         return buf.ToString();
 417                 }
 418
 419                 public override string ToString()
 420                 {
 421                         return ToString(MIN_TOKEN_INDEX, getTokenStreamSize());
 422                 }
 423
 424                 public string ToString(string programName)
 425                 {
 426                         return ToString(programName, MIN_TOKEN_INDEX, getTokenStreamSize());
 427                 }
 428
 429                 public string ToString(int start, int end)
 430                 {
 431                         return ToString(DEFAULT_PROGRAM_NAME, start, end);
 432                 }
 433
 434                 public string ToString(string programName, int start, int end)
 435                 {
 436                         IList rewrites = (IList) programs[programName];
 437                         if (rewrites == null)
 438                         {
 439                                 return null; // invalid program
 440                         }
 441                         StringBuilder buf = new StringBuilder();
 442
 443                         // Index of first rewrite we have not done
 444                         int rewriteOpIndex = 0;
 445
 446                         int tokenCursor = start;
 447                         while ( (tokenCursor >= MIN_TOKEN_INDEX) &&
 448                                 (tokenCursor <= end) &&
 449                                 (tokenCursor < tokens.Count) )
 450                         {
 451                                 if (rewriteOpIndex < rewrites.Count)
 452                                 {
 453                                         RewriteOperation op = (RewriteOperation) rewrites[rewriteOpIndex];
 454                                         while ( (tokenCursor == op.index) && (rewriteOpIndex < rewrites.Count) )
 455                                         {
 456                                                 /*
 457                                                 Console.Out.WriteLine("execute op "+rewriteOpIndex+
 458                                                                                         " (type "+op.GetType().FullName+")"
 459                                                                                         +" at index "+op.index);
 460                                                 */
 461                                                 tokenCursor = op.execute(buf);
 462                                                 rewriteOpIndex++;
 463                                                 if (rewriteOpIndex < rewrites.Count)
 464                                                 {
 465                                                         op = (RewriteOperation) rewrites[rewriteOpIndex];
 466                                                 }
 467                                         }
 468                                 }
 469                                 if ( tokenCursor < end )
 470                                 {
 471                                         buf.Append(getToken(tokenCursor).getText());
 472                                         tokenCursor++;
 473                                 }
 474                         }
 475                         // now see if there are operations (append) beyond last token index
 476                         for (int opi = rewriteOpIndex; opi < rewrites.Count; opi++)
 477                         {
 478                                 RewriteOperation op = (RewriteOperation) rewrites[opi];
 479                                 op.execute(buf); // must be insertions if after last token
 480                         }
 481
 482                         return buf.ToString();
 483                 }
 484
 485                 public string ToDebugString()
 486                 {
 487                         return ToDebugString(MIN_TOKEN_INDEX, getTokenStreamSize());
 488                 }
 489
 490                 public string ToDebugString(int start, int end)
 491                 {
 492                         StringBuilder buf = new StringBuilder();
 493                         for (int i = start; (i >= MIN_TOKEN_INDEX) && (i <= end) && (i < tokens.Count); i++)
 494                         {
 495                                 buf.Append(getToken(i));
 496                         }
 497                         return buf.ToString();
 498                 }
 499
 500                 public int getLastRewriteTokenIndex()
 501                 {
 502                         return getLastRewriteTokenIndex(DEFAULT_PROGRAM_NAME);
 503                 }
 504
 505                 protected int getLastRewriteTokenIndex(string programName)
 506                 {
 507                         object i = lastRewriteTokenIndexes[programName];
 508                         if (i == null)
 509                         {
 510                                 return -1;
 511                         }
 512                         return (int) i;
 513                 }
 514
 515                 protected void setLastRewriteTokenIndex(string programName, int i)
 516                 {
 517                         lastRewriteTokenIndexes[programName] = (object) i;
 518                 }
 519
 520                 protected IList getProgram(string name)
 521                 {
 522                         IList il = (IList) programs[name];
 523                         if ( il == null )
 524                         {
 525                                 il = initializeProgram(name);
 526                         }
 527                         return il;
 528                 }
 529
 530                 private IList initializeProgram(string name)
 531                 {
 532                         IList il = new ArrayList(PROGRAM_INIT_SIZE);
 533                         programs[name] = il;
 534                         return il;
 535                 }
 536
 537                 public class RewriteOperationComparer : IComparer
 538                 {
 539                         public static readonly RewriteOperationComparer Default = new RewriteOperationComparer();
 540
 541                         public virtual int Compare(object o1, object o2)
 542                         {
 543                                 RewriteOperation rop1 = (RewriteOperation) o1;
 544                                 RewriteOperation rop2 = (RewriteOperation) o2;
 545
 546                                 if (rop1.index < rop2.index) return -1;
 547                                 if (rop1.index > rop2.index) return 1;
 548                                 return 0;
 549                         }
 550                 }
 551         }
 552 }