diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/TokenRewriteStream.cs')
| -rw-r--r-- | runtime/CSharp3/Sources/Antlr3.Runtime/TokenRewriteStream.cs | 729 |
1 files changed, 729 insertions, 0 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/TokenRewriteStream.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/TokenRewriteStream.cs new file mode 100644 index 0000000..e9ab4a9 --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/TokenRewriteStream.cs @@ -0,0 +1,729 @@ +/* + * [The "BSD licence"] + * Copyright (c) 2005-2008 Terence Parr + * All rights reserved. + * + * Conversion to C#: + * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +namespace Antlr.Runtime +{ + using System.Collections.Generic; + + using ArgumentException = System.ArgumentException; + using Console = System.Console; + using Math = System.Math; + using DebuggerDisplay = System.Diagnostics.DebuggerDisplayAttribute; + using Exception = System.Exception; + using StringBuilder = System.Text.StringBuilder; + using Type = System.Type; + + /** Useful for dumping out the input stream after doing some + * augmentation or other manipulations. + * + * You can insert stuff, replace, and delete chunks. Note that the + * operations are done lazily--only if you convert the buffer to a + * String. This is very efficient because you are not moving data around + * all the time. As the buffer of tokens is converted to strings, the + * toString() method(s) check to see if there is an operation at the + * current index. If so, the operation is done and then normal String + * rendering continues on the buffer. This is like having multiple Turing + * machine instruction streams (programs) operating on a single input tape. :) + * + * Since the operations are done lazily at toString-time, operations do not + * screw up the token index values. That is, an insert operation at token + * index i does not change the index values for tokens i+1..n-1. + * + * Because operations never actually alter the buffer, you may always get + * the original token stream back without undoing anything. Since + * the instructions are queued up, you can easily simulate transactions and + * roll back any changes if there is an error just by removing instructions. + * For example, + * + * CharStream input = new ANTLRFileStream("input"); + * TLexer lex = new TLexer(input); + * TokenRewriteStream tokens = new TokenRewriteStream(lex); + * T parser = new T(tokens); + * parser.startRule(); + * + * Then in the rules, you can execute + * Token t,u; + * ... + * input.insertAfter(t, "text to put after t");} + * input.insertAfter(u, "text after u");} + * System.out.println(tokens.toString()); + * + * Actually, you have to cast the 'input' to a TokenRewriteStream. :( + * + * You can also have multiple "instruction streams" and get multiple + * rewrites from a single pass over the input. Just name the instruction + * streams and use that name again when printing the buffer. This could be + * useful for generating a C file and also its header file--all from the + * same buffer: + * + * tokens.insertAfter("pass1", t, "text to put after t");} + * tokens.insertAfter("pass2", u, "text after u");} + * System.out.println(tokens.toString("pass1")); + * System.out.println(tokens.toString("pass2")); + * + * If you don't use named rewrite streams, a "default" stream is used as + * the first example shows. + */ + [System.Serializable] + [DebuggerDisplay( "TODO: TokenRewriteStream debugger display" )] + public class TokenRewriteStream : CommonTokenStream + { + public const string DEFAULT_PROGRAM_NAME = "default"; + public const int PROGRAM_INIT_SIZE = 100; + public const int MIN_TOKEN_INDEX = 0; + + // Define the rewrite operation hierarchy + + protected class RewriteOperation + { + /** <summary>What index into rewrites List are we?</summary> */ + public int instructionIndex; + /** <summary>Token buffer index.</summary> */ + public int index; + public object text; + // outer + protected TokenRewriteStream stream; + + protected RewriteOperation(TokenRewriteStream stream, int index) + { + this.stream = stream; + this.index = index; + } + + protected RewriteOperation( TokenRewriteStream stream, int index, object text ) + { + this.index = index; + this.text = text; + this.stream = stream; + } + + /** <summary> + * Execute the rewrite operation by possibly adding to the buffer. + * Return the index of the next token to operate on. + * </summary> + */ + public virtual int Execute( StringBuilder buf ) + { + return index; + } + + public override string ToString() + { + string opName = this.GetType().Name; + int dindex = opName.IndexOf( '$' ); + opName = opName.Substring( dindex + 1 ); + return string.Format("<{0}@{1}:\"{2}\">", opName, stream._tokens[index], text); + } + } + + private class InsertBeforeOp : RewriteOperation + { + public InsertBeforeOp( TokenRewriteStream stream, int index, object text ) : + base( stream, index, text ) + { + } + + public override int Execute( StringBuilder buf ) + { + buf.Append( text ); + if (stream._tokens[index].Type != CharStreamConstants.EndOfFile) + buf.Append(stream._tokens[index].Text); + return index + 1; + } + } + + /** <summary> + * I'm going to try replacing range from x..y with (y-x)+1 ReplaceOp + * instructions. + * </summary> + */ + private class ReplaceOp : RewriteOperation + { + public int lastIndex; + public ReplaceOp( TokenRewriteStream stream, int from, int to, object text ) + : base( stream, from, text ) + { + lastIndex = to; + } + + public override int Execute( StringBuilder buf ) + { + if ( text != null ) + { + buf.Append( text ); + } + return lastIndex + 1; + } + + public override string ToString() + { + if (text == null) + { + return string.Format("<DeleteOp@{0}..{1}>", stream._tokens[index], stream._tokens[lastIndex]); + } + + return string.Format("<ReplaceOp@{0}..{1}:\"{2}\">", stream._tokens[index], stream._tokens[lastIndex], text); + } + } + + /** <summary> + * You may have multiple, named streams of rewrite operations. + * I'm calling these things "programs." + * Maps String (name) -> rewrite (List) + * </summary> + */ + protected IDictionary<string, IList<RewriteOperation>> programs = null; + + /** <summary>Map String (program name) -> Integer index</summary> */ + protected IDictionary<string, int> lastRewriteTokenIndexes = null; + + public TokenRewriteStream() + { + Init(); + } + + protected void Init() + { + programs = new Dictionary<string, IList<RewriteOperation>>(); + programs[DEFAULT_PROGRAM_NAME] = new List<RewriteOperation>( PROGRAM_INIT_SIZE ); + lastRewriteTokenIndexes = new Dictionary<string, int>(); + } + + public TokenRewriteStream( ITokenSource tokenSource ) + : base( tokenSource ) + { + Init(); + } + + public TokenRewriteStream( ITokenSource tokenSource, int channel ) + : base( tokenSource, channel ) + { + Init(); + } + + public virtual void Rollback( int instructionIndex ) + { + Rollback( DEFAULT_PROGRAM_NAME, instructionIndex ); + } + + /** <summary> + * Rollback the instruction stream for a program so that + * the indicated instruction (via instructionIndex) is no + * longer in the stream. UNTESTED! + * </summary> + */ + public virtual void Rollback( string programName, int instructionIndex ) + { + IList<RewriteOperation> @is; + if ( programs.TryGetValue( programName, out @is ) && @is != null ) + { + List<RewriteOperation> sublist = new List<RewriteOperation>(); + for ( int i = MIN_TOKEN_INDEX; i <= instructionIndex; i++ ) + sublist.Add( @is[i] ); + + programs[programName] = sublist; + } + } + + public virtual void DeleteProgram() + { + DeleteProgram( DEFAULT_PROGRAM_NAME ); + } + + /** <summary>Reset the program so that no instructions exist</summary> */ + public virtual void DeleteProgram( string programName ) + { + Rollback( programName, MIN_TOKEN_INDEX ); + } + + public virtual void InsertAfter( IToken t, object text ) + { + InsertAfter( DEFAULT_PROGRAM_NAME, t, text ); + } + + public virtual void InsertAfter( int index, object text ) + { + InsertAfter( DEFAULT_PROGRAM_NAME, index, text ); + } + + public virtual void InsertAfter( string programName, IToken t, object text ) + { + InsertAfter( programName, t.TokenIndex, text ); + } + + public virtual void InsertAfter( string programName, int index, object text ) + { + // to insert after, just insert before next index (even if past end) + InsertBefore( programName, index + 1, text ); + } + + public virtual void InsertBefore( IToken t, object text ) + { + InsertBefore( DEFAULT_PROGRAM_NAME, t, text ); + } + + public virtual void InsertBefore( int index, object text ) + { + InsertBefore( DEFAULT_PROGRAM_NAME, index, text ); + } + + public virtual void InsertBefore( string programName, IToken t, object text ) + { + InsertBefore( programName, t.TokenIndex, text ); + } + + public virtual void InsertBefore( string programName, int index, object text ) + { + RewriteOperation op = new InsertBeforeOp( this, index, text ); + IList<RewriteOperation> rewrites = GetProgram( programName ); + op.instructionIndex = rewrites.Count; + rewrites.Add( op ); + } + + public virtual void Replace( int index, object text ) + { + Replace( DEFAULT_PROGRAM_NAME, index, index, text ); + } + + public virtual void Replace( int from, int to, object text ) + { + Replace( DEFAULT_PROGRAM_NAME, from, to, text ); + } + + public virtual void Replace( IToken indexT, object text ) + { + Replace( DEFAULT_PROGRAM_NAME, indexT, indexT, text ); + } + + public virtual void Replace( IToken from, IToken to, object text ) + { + Replace( DEFAULT_PROGRAM_NAME, from, to, text ); + } + + public virtual void Replace( string programName, int from, int to, object text ) + { + if ( from > to || from < 0 || to < 0 || to >= _tokens.Count ) + { + throw new ArgumentException( "replace: range invalid: " + from + ".." + to + "(size=" + _tokens.Count + ")" ); + } + RewriteOperation op = new ReplaceOp( this, from, to, text ); + IList<RewriteOperation> rewrites = GetProgram( programName ); + op.instructionIndex = rewrites.Count; + rewrites.Add( op ); + } + + public virtual void Replace( string programName, IToken from, IToken to, object text ) + { + Replace( programName, + from.TokenIndex, + to.TokenIndex, + text ); + } + + public virtual void Delete( int index ) + { + Delete( DEFAULT_PROGRAM_NAME, index, index ); + } + + public virtual void Delete( int from, int to ) + { + Delete( DEFAULT_PROGRAM_NAME, from, to ); + } + + public virtual void Delete( IToken indexT ) + { + Delete( DEFAULT_PROGRAM_NAME, indexT, indexT ); + } + + public virtual void Delete( IToken from, IToken to ) + { + Delete( DEFAULT_PROGRAM_NAME, from, to ); + } + + public virtual void Delete( string programName, int from, int to ) + { + Replace( programName, from, to, null ); + } + + public virtual void Delete( string programName, IToken from, IToken to ) + { + Replace( programName, from, to, null ); + } + + public virtual int GetLastRewriteTokenIndex() + { + return GetLastRewriteTokenIndex( DEFAULT_PROGRAM_NAME ); + } + + protected virtual int GetLastRewriteTokenIndex( string programName ) + { + int value; + if ( lastRewriteTokenIndexes.TryGetValue( programName, out value ) ) + return value; + + return -1; + } + + protected virtual void SetLastRewriteTokenIndex( string programName, int i ) + { + lastRewriteTokenIndexes[programName] = i; + } + + protected virtual IList<RewriteOperation> GetProgram( string name ) + { + IList<RewriteOperation> @is; + if ( !programs.TryGetValue( name, out @is ) || @is == null ) + { + @is = InitializeProgram( name ); + } + return @is; + } + + private IList<RewriteOperation> InitializeProgram( string name ) + { + IList<RewriteOperation> @is = new List<RewriteOperation>( PROGRAM_INIT_SIZE ); + programs[name] = @is; + return @is; + } + + public virtual string ToOriginalString() + { + Fill(); + return ToOriginalString( MIN_TOKEN_INDEX, Count - 1 ); + } + + public virtual string ToOriginalString( int start, int end ) + { + StringBuilder buf = new StringBuilder(); + for ( int i = start; i >= MIN_TOKEN_INDEX && i <= end && i < _tokens.Count; i++ ) + { + if (Get(i).Type != CharStreamConstants.EndOfFile) + buf.Append(Get(i).Text); + } + return buf.ToString(); + } + + public override string ToString() + { + Fill(); + return ToString( MIN_TOKEN_INDEX, Count - 1 ); + } + + public virtual string ToString( string programName ) + { + Fill(); + return ToString(programName, MIN_TOKEN_INDEX, Count - 1); + } + + public override string ToString( int start, int end ) + { + return ToString( DEFAULT_PROGRAM_NAME, start, end ); + } + + public virtual string ToString( string programName, int start, int end ) + { + IList<RewriteOperation> rewrites; + if ( !programs.TryGetValue( programName, out rewrites ) ) + rewrites = null; + + // ensure start/end are in range + if ( end > _tokens.Count - 1 ) + end = _tokens.Count - 1; + if ( start < 0 ) + start = 0; + + if ( rewrites == null || rewrites.Count == 0 ) + { + return ToOriginalString( start, end ); // no instructions to execute + } + StringBuilder buf = new StringBuilder(); + + // First, optimize instruction stream + IDictionary<int, RewriteOperation> indexToOp = ReduceToSingleOperationPerIndex( rewrites ); + + // Walk buffer, executing instructions and emitting tokens + int i = start; + while ( i <= end && i < _tokens.Count ) + { + RewriteOperation op; + bool exists = indexToOp.TryGetValue( i, out op ); + + if ( exists ) + { + // remove so any left have index size-1 + indexToOp.Remove( i ); + } + + if ( !exists || op == null ) + { + IToken t = _tokens[i]; + // no operation at that index, just dump token + if (t.Type != CharStreamConstants.EndOfFile) + buf.Append(t.Text); + i++; // move to next token + } + else + { + i = op.Execute( buf ); // execute operation and skip + } + } + + // include stuff after end if it's last index in buffer + // So, if they did an insertAfter(lastValidIndex, "foo"), include + // foo if end==lastValidIndex. + if ( end == _tokens.Count - 1 ) + { + // Scan any remaining operations after last token + // should be included (they will be inserts). + foreach ( RewriteOperation op in indexToOp.Values ) + { + if ( op.index >= _tokens.Count - 1 ) + buf.Append( op.text ); + } + } + return buf.ToString(); + } + + /** We need to combine operations and report invalid operations (like + * overlapping replaces that are not completed nested). Inserts to + * same index need to be combined etc... Here are the cases: + * + * I.i.u I.j.v leave alone, nonoverlapping + * I.i.u I.i.v combine: Iivu + * + * R.i-j.u R.x-y.v | i-j in x-y delete first R + * R.i-j.u R.i-j.v delete first R + * R.i-j.u R.x-y.v | x-y in i-j ERROR + * R.i-j.u R.x-y.v | boundaries overlap ERROR + * + * Delete special case of replace (text==null): + * D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) + * + * I.i.u R.x-y.v | i in (x+1)-y delete I (since insert before + * we're not deleting i) + * I.i.u R.x-y.v | i not in (x+1)-y leave alone, nonoverlapping + * R.x-y.v I.i.u | i in x-y ERROR + * R.x-y.v I.x.u R.x-y.uv (combine, delete I) + * R.x-y.v I.i.u | i not in x-y leave alone, nonoverlapping + * + * I.i.u = insert u before op @ index i + * R.x-y.u = replace x-y indexed tokens with u + * + * First we need to examine replaces. For any replace op: + * + * 1. wipe out any insertions before op within that range. + * 2. Drop any replace op before that is contained completely within + * that range. + * 3. Throw exception upon boundary overlap with any previous replace. + * + * Then we can deal with inserts: + * + * 1. for any inserts to same index, combine even if not adjacent. + * 2. for any prior replace with same left boundary, combine this + * insert with replace and delete this replace. + * 3. throw exception if index in same range as previous replace + * + * Don't actually delete; make op null in list. Easier to walk list. + * Later we can throw as we add to index -> op map. + * + * Note that I.2 R.2-2 will wipe out I.2 even though, technically, the + * inserted stuff would be before the replace range. But, if you + * add tokens in front of a method body '{' and then delete the method + * body, I think the stuff before the '{' you added should disappear too. + * + * Return a map from token index to operation. + */ + protected virtual IDictionary<int, RewriteOperation> ReduceToSingleOperationPerIndex( IList<RewriteOperation> rewrites ) + { + //System.out.println("rewrites="+rewrites); + + // WALK REPLACES + for ( int i = 0; i < rewrites.Count; i++ ) + { + RewriteOperation op = rewrites[i]; + if ( op == null ) + continue; + if ( !( op is ReplaceOp ) ) + continue; + ReplaceOp rop = (ReplaceOp)rewrites[i]; + // Wipe prior inserts within range + var inserts = GetKindOfOps( rewrites, typeof( InsertBeforeOp ), i ); + for ( int j = 0; j < inserts.Count; j++ ) + { + InsertBeforeOp iop = (InsertBeforeOp)inserts[j]; + if (iop.index == rop.index) + { + // E.g., insert before 2, delete 2..2; update replace + // text to include insert before, kill insert + rewrites[iop.instructionIndex] = null; + rop.text = iop.text.ToString() + (rop.text != null ? rop.text.ToString() : string.Empty); + } + else if (iop.index > rop.index && iop.index <= rop.lastIndex) + { + // delete insert as it's a no-op. + rewrites[iop.instructionIndex] = null; + } + } + // Drop any prior replaces contained within + var prevReplaces = GetKindOfOps( rewrites, typeof( ReplaceOp ), i ); + for ( int j = 0; j < prevReplaces.Count; j++ ) + { + ReplaceOp prevRop = (ReplaceOp)prevReplaces[j]; + if ( prevRop.index >= rop.index && prevRop.lastIndex <= rop.lastIndex ) + { + // delete replace as it's a no-op. + rewrites[prevRop.instructionIndex] = null; + continue; + } + // throw exception unless disjoint or identical + bool disjoint = + prevRop.lastIndex < rop.index || prevRop.index > rop.lastIndex; + bool same = + prevRop.index == rop.index && prevRop.lastIndex == rop.lastIndex; + // Delete special case of replace (text==null): + // D.i-j.u D.x-y.v | boundaries overlap combine to max(min)..max(right) + if (prevRop.text == null && rop.text == null && !disjoint) + { + //System.out.println("overlapping deletes: "+prevRop+", "+rop); + rewrites[prevRop.instructionIndex] = null; // kill first delete + rop.index = Math.Min(prevRop.index, rop.index); + rop.lastIndex = Math.Max(prevRop.lastIndex, rop.lastIndex); + Console.WriteLine("new rop " + rop); + } + else if ( !disjoint && !same ) + { + throw new ArgumentException( "replace op boundaries of " + rop + + " overlap with previous " + prevRop ); + } + } + } + + // WALK INSERTS + for ( int i = 0; i < rewrites.Count; i++ ) + { + RewriteOperation op = (RewriteOperation)rewrites[i]; + if ( op == null ) + continue; + if ( !( op is InsertBeforeOp ) ) + continue; + InsertBeforeOp iop = (InsertBeforeOp)rewrites[i]; + // combine current insert with prior if any at same index + var prevInserts = GetKindOfOps( rewrites, typeof( InsertBeforeOp ), i ); + for ( int j = 0; j < prevInserts.Count; j++ ) + { + InsertBeforeOp prevIop = (InsertBeforeOp)prevInserts[j]; + if ( prevIop.index == iop.index ) + { // combine objects + // convert to strings...we're in process of toString'ing + // whole token buffer so no lazy eval issue with any templates + iop.text = CatOpText( iop.text, prevIop.text ); + // delete redundant prior insert + rewrites[prevIop.instructionIndex] = null; + } + } + // look for replaces where iop.index is in range; error + var prevReplaces = GetKindOfOps( rewrites, typeof( ReplaceOp ), i ); + for ( int j = 0; j < prevReplaces.Count; j++ ) + { + ReplaceOp rop = (ReplaceOp)prevReplaces[j]; + if ( iop.index == rop.index ) + { + rop.text = CatOpText( iop.text, rop.text ); + rewrites[i] = null; // delete current insert + continue; + } + if ( iop.index >= rop.index && iop.index <= rop.lastIndex ) + { + throw new ArgumentException( "insert op " + iop + + " within boundaries of previous " + rop ); + } + } + } + // System.out.println("rewrites after="+rewrites); + IDictionary<int, RewriteOperation> m = new Dictionary<int, RewriteOperation>(); + for ( int i = 0; i < rewrites.Count; i++ ) + { + RewriteOperation op = (RewriteOperation)rewrites[i]; + if ( op == null ) + continue; // ignore deleted ops + + RewriteOperation existing; + if ( m.TryGetValue( op.index, out existing ) && existing != null ) + { + throw new Exception( "should only be one op per index" ); + } + m[op.index] = op; + } + //System.out.println("index to op: "+m); + return m; + } + + protected virtual string CatOpText( object a, object b ) + { + return string.Concat( a, b ); + } + protected virtual IList<RewriteOperation> GetKindOfOps( IList<RewriteOperation> rewrites, Type kind ) + { + return GetKindOfOps( rewrites, kind, rewrites.Count ); + } + + /** <summary>Get all operations before an index of a particular kind</summary> */ + protected virtual IList<RewriteOperation> GetKindOfOps( IList<RewriteOperation> rewrites, Type kind, int before ) + { + IList<RewriteOperation> ops = new List<RewriteOperation>(); + for ( int i = 0; i < before && i < rewrites.Count; i++ ) + { + RewriteOperation op = rewrites[i]; + if ( op == null ) + continue; // ignore deleted + if ( op.GetType() == kind ) + ops.Add( op ); + } + return ops; + } + + public virtual string ToDebugString() + { + return ToDebugString( MIN_TOKEN_INDEX, Count - 1 ); + } + + public virtual string ToDebugString( int start, int end ) + { + StringBuilder buf = new StringBuilder(); + for ( int i = start; i >= MIN_TOKEN_INDEX && i <= end && i < _tokens.Count; i++ ) + { + buf.Append( Get( i ) ); + } + return buf.ToString(); + } + } +} |