[prev in list] [next in list] [prev in thread] [next in thread]
List: antlr-dev
Subject: Re: [antlr-dev] Some More Potential Issues with TokenRewriteStream
From: Jeff Saremi <jeffsaremi () yahoo ! com>
Date: 2008-05-29 10:58:39
Message-ID: 999869.83981.qm () web88102 ! mail ! re2 ! yahoo ! com
[Download RAW message or body]
this should be basically ignored. See the thread titled "[antlr-dev] TokenRewriteStream 2nd question: targeted for Terence"
jeff
----- Original Message ----
> From: Jeff Saremi <jeffsaremi@yahoo.com>
> To: ANTLR-dev Dev <antlr-dev@antlr.org>
> Sent: Tuesday, May 27, 2008 7:32:23 PM
> Subject: [antlr-dev] Some More Potential Issues with TokenRewriteStream and a Suggested Rewrite
>
> This is most probably my last post on this subject. As you may know Joey Hurst
> has already done the JS version of the runtime so there's no need for me to try
> to do the same.
>
> However, i wanted to just capture my observations on this Class. If the
> observations seem correct, then you may want to look at how I addressed these
> "problems" in a different (and in my opinion simplified) version of this Class.
>
> Issue 1. the insertion of "insertOps" seems to be FILO versus the intended?
> FIFO. Mentioned in another thread but not confirmed.
> Issue 2. ReplaceOps before the "start" do not take effect. I mentioned this in
> another thread.
> Issue 3. The Inserts beyond the last token in the stream are injected anyway.
> This is from the following piece of code and the test case
> "testInsertAfterLastIndex" verifies it. If this observation is true and the
> feature is intended, one can assume that it should also be valid when an "end"
> is supplied to toString(start,end); however, this is not the case:
>
> // now see if there are operations (append) beyond last token index
> for (int opi=rewriteOpIndex; opi
> RewriteOperation op =
> (RewriteOperation)rewrites.get(opi);
> if ( op.index>=size() ) {
> op.execute(buf); // must be insertions if after last token
> }
> //System.out.println("execute "+op+" at "+opi);
> //op.execute(buf); // must be insertions if after last token
> }
>
> Issue 4. If the assumption in Issue 3 is valid, again one can assume, by
> analogy, that the same should apply to insertions before "start". This is not
> the case.
>
> Assuming that the above are indications of issues within TokenRewriteStream, the
> following show how they can be overcome:
>
> 1. The insertions all follow a simple logic: At an index, all insertions are
> recorded and executed in the order they were received. A simple List, Stack,
> Array/Vector can provide this implementation easily.
> 2. At an index, Replace operations, including Deletes, overwrite each other.
> Therefore, all I would need to maintain is one single ReplaceOp.
> 3. If i then create a structure that has insertions grouped together along with
> one single ReplaceOp I could handle the Rewrite operations for that index. A
> simple grouping (Class) of an array (for insertions) and a single op (for the
> replace) could meet my requirements for a specific index.
> 4. All i need now is to ensure that this structure can easily be inserted and
> retrieved for a given index. This implies a Map of some sort, in which the key
> is the "index" and the value is the structure mentioned above.
> 5. Based on the above my "rewrites" would become a Map. Here's how I implemented
> it as a SortedMap (using TreeMap). Sorted is for looping that we'll see later. I
> have provided helper methods in my structure just to encapsulate the logic
> further. But i avoided over-encapsulation so the code can still be examined
> easily:
>
> static class OpsAtIndexEntry {
> public int index;
> public Vectorinserts;
> public ReplaceOp replace;
>
> public OpsAtIndexEntry(int index){
> this.index = index;
> this.inserts = new Vector();
> }
>
> public void addInsertOp(RewriteOperation insertOp) {
> // inserts is a FIFO list so just add to the end
> if(this.index == insertOp.index) this.inserts.add(insertOp);
>
> }
> public void addReplaceOp(ReplaceOp replaceOp) {
> // replace operations (replace or delete) just overwrite the
> previous one
> if(this.index == replaceOp.index) this.replace = replaceOp;
> }
> public void addOperation(RewriteOperation op) {
> if(op instanceof ReplaceOp) this.addReplaceOp((ReplaceOp)op);
> else this.addInsertOp(op);
> }
> }
>
> and then the method "addToSortedRewriteList" would turn into:
>
> protected void addToSortedRewriteList(String programName, RewriteOperation
> op) {
> TreeMaprewrites = getProgram(programName);
> OpsAtIndexEntry entry = rewrites.get(op.index);
> if(entry == null) {
> entry = new OpsAtIndexEntry(op.index);
> rewrites.put(op.index, entry);
> }
> entry.addOperation(op);
> }
>
> 6. Now it comes to executing these operations into the output. This is in the
> toString() method. Assuming that my issues 2 through 4 are features that are
> needed: that is I need to be able to execute operations beyond the start and
> end, this method then would have to perform three tasks. I call these segments:
>
> Segment 1: Pre-start -- This segment executes all insertions that fall
> before the "start". ReplaceOps are ignored unless they have a "lastIndex" that
> is beyond "start". In that case, the replacement is done and the loop is ended.
> This is to address Issues 2 and 4:
>
> subMap = rewrites.headMap(start);
> for (OpsAtIndexEntry entry :
> (Collection)subMap.values()) {
> // output all inserts regardless
> for (int i=0; i
> entry.inserts.get(i).execute(buf);
> }
> if(entry.replace != null // if we do have
> a replace operation
> && entry.replace.lastIndex >= start) // and start falls
> in the replace range
> {
> start = entry.replace.execute(buf);
> break;
>
> }
> }
>
> Segment 2: The main segment. This is where we loop between start and end. Do
> our insertions. Replaces cause the counter to shift. If there is no Replace in a
> cycle, the token is inserted. This is pretty much the business as usual. No
> surprises here:
>
> int tokenCursor=start;
> for (; tokenCursor <=end; )
> {
> OpsAtIndexEntry entry = (OpsAtIndexEntry)rewrites.get(tokenCursor);
> if (entry != null) {
> for (int i = 0; i < entry.inserts.size(); i++) {
> entry.inserts.get(i).execute(buf);
> }
> if(entry.replace != null) {
> tokenCursor = entry.replace.execute(buf);
> continue;
> }
> }
>
> // dump the token at this index
> buf.append(this.get(tokenCursor).getText());
> tokenCursor++;
> }
>
> Segment 3: The Post-end Segment: This kind of corresponds to Issue 3:
>
> subMap = rewrites.tailMap(tokenCursor);
> for (OpsAtIndexEntry entry :
> (Collection)subMap.values()) {
> // output all inserts regardless
> for (int i=0; i
> entry.inserts.get(i).execute(buf);
> }
> // replace operations have no effect in this segment
> }
>
>
> That's it. And a few minor changes here and there to change the rewrites from
> the existing List to the TreeMap.
> It is very possible that we could get away without creating the SortedMap and
> just used a normal Map. This is if toString() is called once and not repeatedly.
> In this case, we could get a sorted list of the Map's keys just before starting
> the loops.
>
> I added a few more test cases to the unit test file as well (see the end of the
> file) and a few tweaks to account for Issue1.
>
> I hope i haven't wasted anybody's time.
> Regards,
> Jeff
_______________________________________________
antlr-dev mailing list
antlr-dev@antlr.org
http://www.antlr.org:8080/mailman/listinfo/antlr-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic