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 Token.Location getLocation() { return new CharToken.CartesianLocation(_row, _col); }
  44     public CharToken next() throws IOException {
  45         if (cur==null) return null;
  46         if (s != null) {
  47             if (spos < s.length()) {
  48                 char c = s.charAt(spos++);
  49                 if (c=='\n') { _row++; _col = 0; }
  50                 else _col++;
  51                 return new CharToken(c);
  52             }
  53             s = null;
  54         }
  55         if (pos >= cur.size()) {
  56             pos = cur.iip+1;
  57             _row = cur.endrow;
  58             _col = cur.endcol;
  59             cur = cur.parent;
  60             if (cur==null) return null;
  61             return CharToken.right;
  62         }
  63         Object o = cur.child(pos++);
  64         if (o instanceof String) {
  65             spos = 0;
  66             s = (String)o;
  67             return next();
  68         }
  69         if (o instanceof Block) {
  70             Block b = (Block)o;
  71             _row = b.row;
  72             _col = b.col;
  73         }
  74         if (((Block)o).isLiteral()) {
  75             spos = 0;
  76             s = ((Block.Literal)o).text();
  77             return next();
  78         }
  79         cur = (Block)o;
  80         pos = 0;
  81         return CharToken.left;
  82     }
  83
  84     public static Block parse(BufferedReader br) throws Invalid, IOException {
  85         int row=0, col=0;
  86         try {
  87             boolean blankLine = false;
  88             Block top = new Block.Root();
  89             for(String s = br.readLine(); s != null; s = br.readLine()) {
  90                 row++;
  91                 col=0;
  92                 while (s.length() > 0 &&
  93                        s.charAt(0) == ' ' &&
  94                        (!(top instanceof Block.Literal) || col < top.col)) { col++; s = s.substring(1); }
  95                 if ((top instanceof Block.Literal) && col >= top.col) { top.add(s); continue; }
  96                 if (s.length()==0)                                    { blankLine = true; continue; }
  97                 while (col < top.col) {
  98                     if (s.startsWith("{}") && top instanceof Block.Literal && ((Block.Literal)top).braceCol == col) break;
  99                     blankLine = false;
 100                     top.endrow = row;
 101                     top.endcol = col;
 102                     top = top.closeIndent();
 103                 }
 104                 if (s.startsWith("{}")) {
 105                     int bc = col;
 106                     boolean append = top instanceof Block.Literal && ((Block.Literal)top).braceCol == bc;
 107                     s = s.substring(2);
 108                     col += 2;
 109                     while (s.length() > 0 && s.charAt(0) == ' ' && !(append && col >= top.col) ) { col++; s = s.substring(1); }
 110                     if (append) top.add(s); else (top = new Block.Literal(top, row, col, bc)).add(s);
 111                     continue;
 112                 }
 113                 while (s.length() > 0 && s.charAt(s.length()-1)==' ') { s = s.substring(0, s.length()-1); }
 114                 if (col > top.col) top = new Block.Indent(top, row, col);
 115                 else if (blankLine) { top.endrow=row; top.endcol=col; top = top.closeIndent(); top = new Block.Indent(top, row, col); }
 116                 blankLine = false;
 117                 for(int i=0; i<s.length(); i++) {
 118                     top.add(s.charAt(i));
 119                     switch(s.charAt(i)) {
 120                         case '{':  top = new Block.Brace(top, row, col);   break;
 121                         case '}':  top.endrow=row; top.endcol=col; top = top.closeBrace();                 break;
 122                     }
 123                 }
 124                 top.add('\n');
 125                 top.finishWord();
 126             }
 127             // FIXME
 128             Block ret = top;
 129             while (ret.parent != null) ret = ret.parent;
 130             return ret;
 131         } catch (InternalException ie) {
 132             throw new Invalid(ie, row, col);
 133         }
 134     }
 135
 136     public static class Block {
 137                       Block  parent;
 138         public  final int    row;
 139         public  final int    col;
 140         public   int    endrow;
 141         public   int    endcol;
 142         public final int iip;
 143         private final Vector children = new Vector();
 144         private       String pending  = "";
 145
 146         public int    size() { return children.size(); }
 147         public Object child(int i) { return children.elementAt(i); }
 148         public boolean isLiteral() {  return false; }
 149
 150         protected Block(int row, int col)                {
 151             this.row=row;
 152             this.col=col;
 153             this.iip = -1;
 154             parent = null;
 155         }
 156         public    Block(Block parent, int row, int col)  {
 157             this.row=row;
 158             this.col=col;
 159             this.iip = parent.size();
 160             (this.parent = parent).add(this);
 161         }
 162
 163         public void    add(String s)        { children.addElement(s); }
 164         public void    add(char c)          {
 165             if (c == '{' || c == '}') { finishWord(); return; }
 166             if (c != ' ') { pending += c; return; }
 167             if (pending.length() > 0) { finishWord(); add(" "); return; }
 168             if (size()==0) return;
 169             if (child(size()-1).equals(" ")) return;
 170             add(" ");
 171             return;
 172         }
 173
 174         public void    add(Block  b)        { children.addElement(b); }
 175         public Block   promote()            { parent.parent.replaceLast(this); return close(); }
 176         public Object  lastChild()          { return children.lastElement(); }
 177         public Block   lastChildAsBlock()   { return (Block)lastChild(); }
 178         public void    replaceLast(Block b) { children.setElementAt(b, children.size()-1); b.parent = this; }
 179
 180         public void    finishWord()         { if (pending.length() > 0) { add(pending); pending = ""; } }
 181
 182         public Block   closeBrace()         { throw new InternalException("attempt to closeBrace() a "+getClass().getName()); }
 183         public Block   closeIndent()        { throw new InternalException("attempt to closeIndent() a "+getClass().getName()); }
 184         public Block   close() {
 185             while(size() > 0 && child(size()-1).equals(" ")) children.setSize(children.size()-1);
 186             if (size()==0) throw new InternalException("PARSER BUG: attempt to close an empty block (should never happen)");
 187             if (size() > 1 || !(lastChild() instanceof Block)) return parent;
 188             return lastChildAsBlock().promote();
 189         }
 190         public String toString() { return toString(80); }
 191         public String toString(int justificationLimit) { return toString(0, 80); }
 192         protected String toString(int indent, int justificationLimit) {
 193             StringBuffer ret = new StringBuffer();
 194             StringBuffer line = new StringBuffer();
 195             for(int i=0; i<children.size(); i++) {
 196                 Object o = children.elementAt(i);
 197                 if (i>0 && children.elementAt(i-1) instanceof Block && justificationLimit!=-1) ret.append("\n");
 198                 if (o instanceof Block) {
 199                     ret.append(justify(line.toString(), indent, justificationLimit));
 200                     line.setLength(0);
 201                     if (justificationLimit==-1) {
 202                         ret.append("{");
 203                         ret.append(((Block)o).toString(indent+2, justificationLimit));
 204                         ret.append("}");
 205                     } else {
 206                         ret.append(((Block)o).toString(indent+2, justificationLimit));
 207                     }
 208                 } else {
 209                     line.append(o.toString());
 210                 }
 211             }
 212             ret.append(justify(line.toString(), indent, justificationLimit));
 213             return ret.toString();
 214         }
 215
 216         private static class Root extends Block {
 217             public Root() { super(0, Integer.MIN_VALUE); }
 218             public Block close() { throw new InternalException("attempted to close top block"); }
 219             public String toString(int justificationLimit) { return toString(-2, justificationLimit); }
 220         }
 221
 222         private static class Brace  extends Block {
 223             public Brace(Block parent, int row, int col) { super(parent, row, col); }
 224             public Block closeBrace() { return super.close(); }
 225         }
 226
 227         private static class Indent extends Block {
 228             public Indent(Block parent, int row, int col) { super(parent, row, col); }
 229             public Block closeIndent() { return super.close(); }
 230         }
 231
 232         private static class Literal extends Block {
 233             private StringBuffer content = new StringBuffer();
 234             public final int braceCol;
 235             public    Literal(Block parent, int row, int col, int braceCol) { super(parent,row,col); this.braceCol = braceCol; }
 236             public    boolean isLiteral() {  return true; }
 237             public    int size() { return 1; }
 238             public    Object child(int i) { return i==0 ? content.toString() : null; }
 239             public    Block  close() { return parent; }
 240             public    Block  closeIndent() { return close(); }
 241             public    void   add(String s) { if (content.length()>0) content.append('\n'); content.append(s); }
 242             public    String text() { return content.toString(); }
 243             protected String toString(int indent, int justificationLimit) {
 244                 StringBuffer ret = new StringBuffer();
 245                 String s = content.toString();
 246                 while(s.length() > 0) {
 247                     int nl = s.indexOf('\n');
 248                     if (nl==-1) nl = s.length();
 249                     ret.append(spaces(indent));
 250                     ret.append("{}  ");
 251                     ret.append(s.substring(0, nl));
 252                     s = s.substring(Math.min(s.length(),nl+1));
 253                     ret.append('\n');
 254                 }
 255                 return ret.toString();
 256             }
 257         }
 258     }
 259
 260
 261     // Exceptions //////////////////////////////////////////////////////////////////////////////
 262
 263     private static class InternalException extends RuntimeException { public InternalException(String s) { super(s); } }
 264     public static class Invalid extends /*IOException*/RuntimeException {
 265         public Invalid(InternalException ie, int row, int col) {
 266             super(ie.getMessage() + " at " + row + ":" + col);
 267         }
 268     }
 269
 270     // Testing //////////////////////////////////////////////////////////////////////////////
 271
 272     public static void main(String[] s) throws Exception {
 273         System.out.println(parse(new BufferedReader(new InputStreamReader(System.in))).toString(-1)); }
 274
 275     // Utilities //////////////////////////////////////////////////////////////////////////////
 276
 277     public static String spaces(int i) { if (i<=0) return ""; return " " + spaces(i-1); }
 278
 279     private static String justify(String s, int indent, int justificationLimit) {
 280         if (s.length() == 0) return "";
 281         if (justificationLimit==-1) return s;
 282         StringBuffer ret = new StringBuffer();
 283         while(s.length() > 0) {
 284             if (s.charAt(0) == ' ') { s = s.substring(1); continue; }
 285             ret.append(spaces(indent));
 286             int i = s.indexOf(' ');
 287             if (i==-1) i = s.length();
 288             while(s.indexOf(' ', i+1) != -1 && s.indexOf(' ', i+1) < justificationLimit-indent) i = s.indexOf(' ', i+1);
 289             if (s.length() + indent < justificationLimit) i = s.length();
 290             ret.append(s.substring(0, i));
 291             s = s.substring(i);
 292             ret.append('\n');
 293         }
 294         return ret.toString();
 295     }
 296
 297     // Grammar //////////////////////////////////////////////////////////////////////////////
 298
 299     public static class Grammar extends MetaGrammar {
 300         private int anon = 0;
 301         private final Element ws = Repeat.maximal0(nonTerminal("w"));
 302         public Grammar() { dropAll.add(ws); }
 303         public Object walk(Tree<String> tree) {
 304             String head = tree.head();
 305             if (tree.numChildren()==0) return super.walk(tree);
 306             if ("{".equals(head)) {
 307                 String s = "braced"+(anon++);
 308                 Union u = nonTerminal(s);
 309                 Union u2 = ((PreSequence)walk(tree, 0)).sparse(ws).buildUnion();
 310                 u2.add(Sequence.singleton(new Element[] { u }, 0, null, null));
 311                 return nonTerminal(s,
 312                                    new PreSequence[][] {
 313                                        new PreSequence[] {
 314                                            new PreSequence(new Element[] { CharToken.leftBrace,
 315                                                                            ws,
 316                                                                            u2,
 317                                                                            ws,
 318                                                                            CharToken.rightBrace
 319                                            })
 320                                        }
 321                                    },
 322                                    false,
 323                                    false);
 324             }
 325             return super.walk(tree);
 326         }
 327     }
 328
 329 }
 330