removed illegal use of double-star
[sbp.git] / src / edu / berkeley / sbp / tib / Tib.java
1 // Copyright 2005 the Contributors, as shown in the revision logs.
2 // Licensed under the Apache Public Source License 2.0 ("the License").
3 // You may not use this file except in compliance with the License.
4
5 package edu.berkeley.sbp.tib;
6 import edu.berkeley.sbp.*;
7 import edu.berkeley.sbp.misc.*;
8 import java.util.*;
9 import java.io.*;
10
11 // TODO: multiple {{ }} for superquotation
12 // TODO: strings
13 // TODO: comments
14
15 /**
16  *   A slow, ugly, inefficient, inelegant, ad-hoc parser for TIB files.
17  *
18  *   Despite being inelegant, this parser keeps all internal state on
19  *   the stack (the only heap objects created are those which are
20  *   returned).
21  *
22  *   This was written as an ad-hoc parser to facilitate
23  *   experimentation with the TIB spec.  Once the spec is finalized it
24  *   should probably be rewritten.
25  */
26 public class Tib implements Token.Stream<CharToken> {
27
28     public Tib(String s) throws IOException, Invalid { this(new StringReader(s)); }
29     public Tib(Reader r) throws IOException, Invalid { this(new BufferedReader(r)); }
30     public Tib(InputStream is) throws IOException, Invalid { this(new BufferedReader(new InputStreamReader(is))); }
31     public Tib(BufferedReader br) throws IOException, Invalid {
32         cur = parse(br);
33         System.out.println("\rparsing: \"" + cur.toString(0, -1) + "\"");
34     }
35
36     private Block cur;
37     private String s = null;
38     int pos = 0;
39     int spos = 0;
40
41     int _row = 0;
42     int _col = 0;
43     public CharToken next() throws IOException {
44         if (cur==null) return null;
45         if (s != null) {
46             if (spos < s.length()) {
47                 char c = s.charAt(spos++);
48                 if (c=='\n') { _row++; _col = 0; }
49                 else _col++;
50                 return new CharToken(c, _row, _col);
51             }
52             s = null;
53         }
54         if (pos >= cur.size()) {
55             pos = cur.iip+1;
56             cur = cur.parent;
57             if (cur==null) return null;
58             return CharToken.right(_row, _col);
59         }
60         Object o = cur.child(pos++);
61         if (o instanceof String) {
62             spos = 0;
63             s = (String)o;
64             return next();
65         }
66         if (o instanceof Block) {
67             Block b = (Block)o;
68             _row = b.row;
69             _col = b.col;
70         }
71         if (((Block)o).isLiteral()) {
72             spos = 0;
73             s = ((Block.Literal)o).text();
74             return next();
75         }
76         cur = (Block)o;
77         pos = 0;
78         return CharToken.left(_row, _col);
79     }
80
81     public static Block parse(BufferedReader br) throws Invalid, IOException {
82         int row=0, col=0;
83         try {
84             boolean blankLine = false;
85             Block top = new Block.Root();
86             for(String s = br.readLine(); s != null; s = br.readLine()) {
87                 col = 0;
88                 while (s.length() > 0 &&
89                        s.charAt(0) == ' ' &&
90                        (!(top instanceof Block.Literal) || col < top.col)) { col++; s = s.substring(1); }
91                 if ((top instanceof Block.Literal) && col >= top.col) { top.add(s); continue; }
92                 if (s.length()==0)                                    { blankLine = true; continue; }
93                 while (col < top.col) {
94                     if (s.startsWith("{}") && top instanceof Block.Literal && ((Block.Literal)top).braceCol == col) break;
95                     blankLine = false;
96                     top = top.closeIndent();
97                 }
98                 if (s.startsWith("{}")) {
99                     int bc = col;
100                     boolean append = top instanceof Block.Literal && ((Block.Literal)top).braceCol == bc;
101                     s = s.substring(2);
102                     col += 2;
103                     while (s.length() > 0 && s.charAt(0) == ' ' && !(append && col >= top.col) ) { col++; s = s.substring(1); }
104                     if (append) top.add(s); else (top = new Block.Literal(top, row, col, bc)).add(s);
105                     continue;
106                 }
107                 while (s.length() > 0 && s.charAt(s.length()-1)==' ') { s = s.substring(0, s.length()-1); }
108                 if (col > top.col) top = new Block.Indent(top, row, col);
109                 else if (blankLine) { top = top.closeIndent(); top = new Block.Indent(top, row, col); }
110                 blankLine = false;
111                 for(int i=0; i<s.length(); i++) {
112                     top.add(s.charAt(i));
113                     switch(s.charAt(i)) {
114                         case '{':  top = new Block.Brace(top, row, col);   break;
115                         case '}':  top = top.closeBrace();                 break;
116                     }
117                 }
118                 top.add(' ');
119                 top.finishWord();
120             }
121             // FIXME
122             Block ret = top;
123             while (ret.parent != null) ret = ret.parent;
124             return ret;
125         } catch (InternalException ie) {
126             throw new Invalid(ie, row, col);
127         }
128     }
129
130     public static class Block {
131                       Block  parent;
132         public  final int    row;
133         public  final int    col;
134         public final int iip;
135         private final Vector children = new Vector();
136         private       String pending  = "";
137
138         public int    size() { return children.size(); }
139         public Object child(int i) { return children.elementAt(i); }
140         public boolean isLiteral() {  return false; }
141
142         protected Block(int row, int col)                {
143             this.row=row;
144             this.col=col;
145             this.iip = -1;
146             parent = null;
147         }
148         public    Block(Block parent, int row, int col)  {
149             this.row=row;
150             this.col=col;
151             this.iip = parent.size();
152             (this.parent = parent).add(this);
153         }
154
155         public void    add(String s)        { children.addElement(s); }
156         public void    add(char c)          {
157             if (c == '{' || c == '}') { finishWord(); return; }
158             if (c != ' ') { pending += c; return; }
159             if (pending.length() > 0) { finishWord(); add(" "); return; }
160             if (size()==0) return;
161             if (child(size()-1).equals(" ")) return;
162             add(" ");
163             return;
164         }
165
166         public void    add(Block  b)        { children.addElement(b); }
167         public Block   promote()            { parent.parent.replaceLast(this); return close(); }
168         public Object  lastChild()          { return children.lastElement(); }
169         public Block   lastChildAsBlock()   { return (Block)lastChild(); }
170         public void    replaceLast(Block b) { children.setElementAt(b, children.size()-1); b.parent = this; }
171
172         public void    finishWord()         { if (pending.length() > 0) { add(pending); pending = ""; } }
173
174         public Block   closeBrace()         { throw new InternalException("attempt to closeBrace() a "+getClass().getName()); }
175         public Block   closeIndent()        { throw new InternalException("attempt to closeIndent() a "+getClass().getName()); }
176         public Block   close() {
177             while(size() > 0 && child(size()-1).equals(" ")) children.setSize(children.size()-1);
178             if (size()==0) throw new InternalException("PARSER BUG: attempt to close an empty block (should never happen)");
179             if (size() > 1 || !(lastChild() instanceof Block)) return parent;
180             return lastChildAsBlock().promote();
181         }
182         public String toString() { return toString(80); }
183         public String toString(int justificationLimit) { return toString(0, 80); }
184         protected String toString(int indent, int justificationLimit) {
185             StringBuffer ret = new StringBuffer();
186             StringBuffer line = new StringBuffer();
187             for(int i=0; i<children.size(); i++) {
188                 Object o = children.elementAt(i);
189                 if (i>0 && children.elementAt(i-1) instanceof Block && justificationLimit!=-1) ret.append("\n");
190                 if (o instanceof Block) {
191                     ret.append(justify(line.toString(), indent, justificationLimit));
192                     line.setLength(0);
193                     if (justificationLimit==-1) {
194                         ret.append("{");
195                         ret.append(((Block)o).toString(indent+2, justificationLimit));
196                         ret.append("}");
197                     } else {
198                         ret.append(((Block)o).toString(indent+2, justificationLimit));
199                     }
200                 } else {
201                     line.append(o.toString());
202                 }
203             }
204             ret.append(justify(line.toString(), indent, justificationLimit));
205             return ret.toString();
206         }
207
208         private static class Root extends Block {
209             public Root() { super(0, Integer.MIN_VALUE); }
210             public Block close() { throw new InternalException("attempted to close top block"); }
211             public String toString(int justificationLimit) { return toString(-2, justificationLimit); }
212         }
213
214         private static class Brace  extends Block {
215             public Brace(Block parent, int row, int col) { super(parent, row, col); }
216             public Block closeBrace() { return super.close(); }
217         }
218     
219         private static class Indent extends Block {
220             public Indent(Block parent, int row, int col) { super(parent, row, col); }
221             public Block closeIndent() { return super.close(); }
222         }
223
224         private static class Literal extends Block {
225             private StringBuffer content = new StringBuffer();
226             public final int braceCol;
227             public    Literal(Block parent, int row, int col, int braceCol) { super(parent,row,col); this.braceCol = braceCol; }
228             public    boolean isLiteral() {  return true; }
229             public    int size() { return 1; }
230             public    Object child(int i) { return i==0 ? content.toString() : null; }
231             public    Block  close() { return parent; }
232             public    Block  closeIndent() { return close(); }
233             public    void   add(String s) { if (content.length()>0) content.append('\n'); content.append(s); }
234             public    String text() { return content.toString(); }
235             protected String toString(int indent, int justificationLimit) {
236                 StringBuffer ret = new StringBuffer();
237                 String s = content.toString();
238                 while(s.length() > 0) {
239                     int nl = s.indexOf('\n');
240                     if (nl==-1) nl = s.length();
241                     ret.append(spaces(indent));
242                     ret.append("{}  ");
243                     ret.append(s.substring(0, nl));
244                     s = s.substring(Math.min(s.length(),nl+1));
245                     ret.append('\n');
246                 }
247                 return ret.toString();
248             }
249         }
250     }
251
252
253     // Exceptions //////////////////////////////////////////////////////////////////////////////
254
255     private static class InternalException extends RuntimeException { public InternalException(String s) { super(s); } }
256     public static class Invalid extends /*IOException*/RuntimeException {
257         public Invalid(InternalException ie, int row, int col) {
258             super(ie.getMessage() + " at " + row + ":" + col);
259         }
260     }
261
262     // Testing //////////////////////////////////////////////////////////////////////////////
263
264     public static void main(String[] s) throws Exception { System.out.println(parse(new BufferedReader(new InputStreamReader(System.in))).toString(-1)); }
265     
266     // Utilities //////////////////////////////////////////////////////////////////////////////
267
268     public static String spaces(int i) { if (i<=0) return ""; return " " + spaces(i-1); }
269
270     private static String justify(String s, int indent, int justificationLimit) {
271         if (s.length() == 0) return "";
272         if (justificationLimit==-1) return s;
273         StringBuffer ret = new StringBuffer();
274         while(s.length() > 0) {
275             if (s.charAt(0) == ' ') { s = s.substring(1); continue; }
276             ret.append(spaces(indent));
277             int i = s.indexOf(' ');
278             if (i==-1) i = s.length();
279             while(s.indexOf(' ', i+1) != -1 && s.indexOf(' ', i+1) < justificationLimit-indent) i = s.indexOf(' ', i+1);
280             if (s.length() + indent < justificationLimit) i = s.length();
281             ret.append(s.substring(0, i));
282             s = s.substring(i);
283             ret.append('\n');
284         }
285         return ret.toString();
286     }
287
288     // Grammar //////////////////////////////////////////////////////////////////////////////
289
290     public static class Grammar extends MetaGrammar {
291         private int anon = 0;
292         private final Element ws = Repeat.maximal(Repeat.many0(nonTerminal("w")));
293         public Grammar() {
294             dropAll.add(ws);
295         }
296         public Object walk(Tree<String> tree) {
297             String head = tree.head();
298             if (tree.numChildren()==0) return super.walk(tree);
299             if ("{".equals(head)) {
300                 String s = "braced"+(anon++);
301                 Union u = nonTerminal(s);
302                 Union u2 = ((PreSequence)walk(tree, 0)).sparse(ws).buildUnion();
303                 u2.add(Sequence.singleton(new Element[] { u }, 0, null, null));
304                 return nonTerminal(s,
305                                    new PreSequence[][] {
306                                        new PreSequence[] {
307                                            new PreSequence(new Element[] { CharToken.leftBrace,
308                                                                            ws,
309                                                                            u2,
310                                                                            ws,
311                                                                            CharToken.rightBrace
312                                            })
313                                        }
314                                    },
315                                    false,
316                                    false);
317             }
318             return super.walk(tree);
319         }
320     }
321
322 }
323