From: adam <adam@megacz.com>
Date: Sun, 27 May 2007 20:27:38 +0000 (-0400)
Subject: allow lifts on any position
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=584cef55d8811e3215858fde22e708d2a3d1cf70

allow lifts on any position

darcs-hash:20070527202738-5007d-d4059b9394ec68669c0ab779c8dcef80d58f78eb.gz
---

diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
index 34982bd..795f3a0 100644
--- a/src/edu/berkeley/sbp/Forest.java
+++ b/src/edu/berkeley/sbp/Forest.java
@@ -28,22 +28,13 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
 
     // Package-Private //////////////////////////////////////////////////////////////////////////////
 
-    static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
-                                              boolean lift) {
-        if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
-        return new One<NodeType>(region, head, children, lift);
-    }
-
-    static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
-                                              boolean lift, boolean liftLeft) {
+    public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children) {
+        return create(region, head, children, new boolean[children==null ? 0 : children.length]); }
+    public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children, boolean[] lifts) {
         if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
-        return new One<NodeType>(region, head, children, lift, liftLeft);
+        return new One<NodeType>(region, head, children, lifts);
     }
 
-    /** create a new forest */
-    public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children) {
-        return Forest.create(region, head, children, false); }
-
     abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
     abstract void gather(HashSet<Forest<NodeType>> ignore);
     abstract void edges(GraphViz.Node n);
@@ -59,29 +50,24 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
         private final Forest<NodeType>[]       children;
 
         /** if true, the last child's children are considered children of this node */
-        private final boolean           lift;
-        private final boolean           liftLeft;
+        private final boolean[]         lifts;
 
         public Input.Region getRegion() { return location; }
 
-        private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift) {
-            this(loc, head, children, lift, false);
-        }
-        private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift, boolean liftLeft) {
+        private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean[] lifts) {
             this.location = loc;
             this.head = head;
             if (head==null) throw new RuntimeException("invoked Forest.create(,null,,,) -- this should never happen");
             this.children = children==null ? emptyForestArray : new Forest[children.length];
             if (children != null) System.arraycopy(children, 0, this.children, 0, children.length);
             if (children != null) for(int i=0; i<children.length; i++) if (children[i]==null) throw new Error(i+"");
-            this.lift = lift;
-            this.liftLeft = liftLeft;
+            this.lifts = lifts;
         }
 
         public Tree<NodeType> expand1() throws Ambiguous {
             Tree<NodeType>[] ret = new Tree[children.length];
             for(int i=0; i<children.length; i++) ret[i] = children[i].expand1();
-            return new Tree<NodeType>(location, head, ret, lift, liftLeft);
+            return new Tree<NodeType>(location, head, ret, lifts);
         }
 
         void gather(HashSet<Forest<NodeType>> hf) {
@@ -95,7 +81,7 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
         private void expand(final int i, Tree<NodeType>[] ta, HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore,
                             Tree<NodeType> bogus) {
             if (i==children.length) {
-                ht.add(new Tree<NodeType>(location, head, ta, lift, liftLeft));
+                ht.add(new Tree<NodeType>(location, head, ta, lifts));
             } else {
                 HashSet<Tree<NodeType>> ht2 = new HashSet<Tree<NodeType>>();
                 children[i].expand(ht2, ignore, bogus);
@@ -124,7 +110,7 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
             if (edges) return;
             edges = true;
             for(int i=0; i<children.length; i++) {
-                if (i==children.length-1 && lift && !children[i].ambiguous()) {
+                if (lifts[i] && !children[i].ambiguous()) {
                     children[i].edges(n);
                 } else {
                     n.edge(children[i], null);
diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index c41be4f..1c76aef 100644
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -34,10 +34,18 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
     public static Sequence create(Element e) { return create(new Element[] { e }, 0); }
 
     /** create a sequence which drops the result of all but one of its element */
-    public static Sequence create(Element[] e, int which) { return new Singleton(e, which); }
+    public static Sequence create(Element[] e, int which) {
+        return new Singleton(e, which); }
 
     /** create a sequence which always evaluates to a constant result  */
-    public static Sequence create(Element[] e, Object result) { return new Constant(e, result); }
+    public static Sequence create(Object result, Element[] e) {
+        return new RewritingSequence(result, e, trues(e.length)); }
+
+    private static boolean[] trues(int length) {
+        boolean[] ret = new boolean[length];
+        for(int i=0; i<ret.length; i++) ret[i] = true;
+        return ret;
+    }
 
     /**
      *  create a sequence (general form)
@@ -45,19 +53,13 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
      *  @param e      the elements to match
      *  @param drop   only elements of <tt>e</tt> whose corresponding <tt>boolean</tt> in <tt>drops</tt>
      *                is <i>false</i> will be included in the output tree
-     *  @param foster if true, all children of the last child (ie
-     *                grandchildren) are promoted to children of this
-     *                node; this is very useful for matching repetitions
+     *  @param lifts  which (if any) child trees to lift
      **/
-    public static Sequence create(Object head, Element[] e, boolean[] drop, boolean foster) {
-        return foster
-            ? new Unwrap(e, head, drop)
-            : new RewritingSequence(head, e, drop);
-    }
-    public static Sequence createLeft(Object head, Element[] e, boolean[] drop, boolean foster) {
-        return foster
-            ? new UnwrapLeft(e, head, drop)
-            : new RewritingSequence(head, e, drop);
+    public static Sequence create(Object head, Element[] e, boolean[] drop) {
+        return create(head, e, drop, new boolean[e.length]); }
+    public static Sequence create(Object head, Element[] e, boolean[] drop, boolean[] lifts) {
+        if (lifts==null) lifts = new boolean[e.length];
+        return new RewritingSequence(head, e, drop, lifts);
     }
 
     /** return a new sequence identical to this one, but with a positive conjunct <tt>s</tt> */
@@ -240,66 +242,31 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
         }
     }
 
-    static class Unwrap extends Sequence {
-        private boolean[] drops;
-        private final Object tag;
-        public Unwrap(Element[] e, Object tag)                  { this(e, tag, null); }
-        public Unwrap(Element[] e, Object tag, boolean[] drops) { super(e); this.drops = drops; this.tag = tag; }
-        Sequence _clone() { return new Unwrap(elements, tag, drops); }
-        public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
-            for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
-            if (drops==null) return Forest.create(loc, (T)tag, args, true);
-            int count = 0;
-            for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
-            Forest<T>[] args2 = new Forest[count];
-            int j = 0;
-            for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
-            return Forest.create(loc, (T)tag, args2, true);
-        }
-        Forest epsilonForm(Input.Region loc, Grammar cache) {
-            return Forest.create(loc, tag, new Forest[0], false);
-        }
-    }
-
-    static class UnwrapLeft extends Sequence {
-        private boolean[] drops;
-        private final Object tag;
-        public UnwrapLeft(Element[] e, Object tag)                  { this(e, tag, null); }
-        public UnwrapLeft(Element[] e, Object tag, boolean[] drops) { super(e); this.drops = drops; this.tag = tag; }
-        Sequence _clone() { return new UnwrapLeft(elements, tag, drops); }
-        public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
-            for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
-            if (drops==null) return Forest.create(loc, (T)tag, args, false, true);
-            int count = 0;
-            for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
-            Forest<T>[] args2 = new Forest[count];
-            int j = 0;
-            for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
-            return Forest.create(loc, (T)tag, args2, false, true);
-        }
-        Forest epsilonForm(Input.Region loc, Grammar cache) {
-            return Forest.create(loc, tag, new Forest[0], false);
-        }
-    }
-
     static class RewritingSequence extends Sequence {
         private Object tag;
         private final boolean[] drops;
-        private int count = 0;
+        private final boolean[] lifts;
         Sequence _clone() { return new RewritingSequence(tag, elements, drops); }
         public RewritingSequence(Object tag, Element[] e) { this(tag, e, null); }
-        public RewritingSequence(Object tag, Element[] e, boolean[] drops) {
+        public RewritingSequence(Object tag, Element[] e, boolean[] drops) { this(tag, e, drops, new boolean[e.length]); }
+        public RewritingSequence(Object tag, Element[] e, boolean[] drops, boolean[] lifts) {
             super(e);
             if (tag==null) throw new Error();
             this.tag = tag;
             this.drops = drops == null ? new boolean[e.length] : drops;
+            int count = 0;
             for(int i=0; i<this.drops.length; i++) if (!this.drops[i]) count++;
+            this.lifts = new boolean[count];
+            int j = 0;
+            for(int i=0; i<this.drops.length; i++)
+                if (!this.drops[i])
+                    this.lifts[j++] = lifts[i];
         }
         public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
-            Forest<T>[] args2 = new Forest[count];
+            Forest<T>[] args2 = new Forest[lifts.length];
             int j = 0;
             for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
-            return Forest.create(loc, (T)tag, args2, false);
+            return Forest.create(loc, (T)tag, args2, lifts);
         }
         public StringBuffer toString(StringBuffer sb, boolean spacing) {
             int len = sb.length();
@@ -311,8 +278,7 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
             return sb;
         }
         Forest epsilonForm(Input.Region loc, Grammar cache) {
-            return Forest.create(loc, tag, new Forest[0], false);
+            return Forest.create(loc, tag, new Forest[0], lifts);
         }
     }
-
 }
diff --git a/src/edu/berkeley/sbp/Tree.java b/src/edu/berkeley/sbp/Tree.java
index 1f55a90..5f7f73d 100644
--- a/src/edu/berkeley/sbp/Tree.java
+++ b/src/edu/berkeley/sbp/Tree.java
@@ -35,32 +35,27 @@ public class Tree<NodeType>
     /** get the input region that this tree was parsed from */
     public Input.Region    getRegion() { return location; }
 
-    public Tree(Input.Region loc, NodeType head)                            { this(loc, head, null); }
-    public Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children) { this(loc, head, children, false); }
+    public Tree(Input.Region loc, NodeType head)                            { this(loc, head, new Tree[0]); }
+    public Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children) { this(loc, head, children, new boolean[children==null?0:children.length]); }
 
     // FIXME: fairly inefficient because we keep copying arrays
     /** package-private constructor, allows setting the "lift" bit */
-    Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean lift) {
-        this(loc, head, children, lift, false);
-    }
-    Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean lift, boolean liftLeft) {
+    Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean[] lifts) {
         this.location = loc;
         this.ihead = head;
-        // FIXME: lift+liftLeft togheter
-        if (liftLeft && children != null && children.length > 0) {
-            Tree<NodeType> last = children[0];
-            this.children = new Tree[(children.length-1)+last.children.length];
-            System.arraycopy(children, 1, this.children, last.children.length, children.length-1);
-            if (last.children.length > 0)
-                System.arraycopy(last.children, 0, this.children, 0, last.children.length);
-        } else if (lift && children != null && children.length > 0) {
-            Tree<NodeType> last = children[children.length-1];
-            this.children = new Tree[(children.length-1)+last.children.length];
-            System.arraycopy(children, 0, this.children, 0, children.length-1);
-            if (last.children.length > 0)
-                System.arraycopy(last.children, 0, this.children, children.length-1, last.children.length);
-        } else {
-            this.children = ArrayUtil.clone(children, Tree.class);
+
+        int count = 0;
+        for(int i=0; i<children.length; i++)
+            count += lifts[i] ? children[i].size() : 1;
+
+        this.children = new Tree[count];
+        int j = 0;
+        for(int i=0; i<children.length; i++) {
+            if (!lifts[i])
+                this.children[j++] = children[i];
+            else
+                for(int k=0; k<children[i].size(); k++)
+                    this.children[j++] = children[i].child(k);
         }
     }
 
diff --git a/src/edu/berkeley/sbp/chr/CharAtom.java b/src/edu/berkeley/sbp/chr/CharAtom.java
index ee31675..f0b7a9e 100644
--- a/src/edu/berkeley/sbp/chr/CharAtom.java
+++ b/src/edu/berkeley/sbp/chr/CharAtom.java
@@ -45,7 +45,7 @@ public class CharAtom extends Atom<Character> {
                     public String toString() { return escapified; } };
             Element[] refs = new Element[s.length()];
             for(int i=0; i<refs.length; i++) refs[i] = new CharAtom(s.charAt(i));
-            ret2.add(Sequence.create(refs, s));
+            ret2.add(Sequence.create(s, refs));
             ret = ret2;
         }
         return ret;
@@ -54,7 +54,7 @@ public class CharAtom extends Atom<Character> {
     private static Union emptyString = new Union("()");
     static {
         // FIXME: force this to be dropped wherever used!
-        emptyString.add(Sequence.create(new Element[0], ""));
+        emptyString.add(Sequence.create("", new Element[0]));
     }
 
     public Topology<Atom<Character>>       unwrap() { return this; }
diff --git a/src/edu/berkeley/sbp/meta/GrammarAST.java b/src/edu/berkeley/sbp/meta/GrammarAST.java
index 997d0b6..19f12a3 100644
--- a/src/edu/berkeley/sbp/meta/GrammarAST.java
+++ b/src/edu/berkeley/sbp/meta/GrammarAST.java
@@ -79,26 +79,24 @@ public class GrammarAST {
         if (head.equals("Word")) return stringifyChildren(t);
         if (head.equals("Elements")) return seq2((ElementNode[])Reflection.rebuild(walkChildren(t), ElementNode[].class));
         if (head.equals("NonTerminalReference")) return new ReferenceNode(stringifyChildren(t.child(0)));
-        //if (head.equals(")")) return new ReferenceNode(stringifyChildren(t.child(0)));
-        if (head.equals("{")) return new XTree((Seq)walk(t.child(0)));
-        if (head.equals("::")) return tag((String)walk(t.child(0)), (Seq)walk(t.child(1)));
-        if (head.equals("++")) return plusmax((ElementNode)walk(t.child(0)));
-        if (head.equals("...")) return star(new TildeNode(new AtomNode()));
-        if (head.equals("+")) return plus((ElementNode)walk(t.child(0)));
-        if (head.equals("++/")) return plusmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
-        if (head.equals("+/")) return plusfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
-        if (head.equals("**")) return starmax((ElementNode)walk(t.child(0)));
-        if (head.equals("*")) return star((ElementNode)walk(t.child(0)));
-        if (head.equals("**/")) return starmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
-        if (head.equals("*/")) return starfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
-        if (head.equals("?")) return question((ElementNode)walk(t.child(0)));
-        if (head.equals("!")) return new DropNode((ElementNode)walk(t.child(0)));
-        if (head.equals("^")) return new LiteralNode((String)walk(t.child(0)), true);
-        if (head.equals("`")) {
-            ElementNode ret = (ElementNode)walk(t.child(0));
-            ret.lifted = true;
-            return ret;
-        }
+        if (head.equals(")"))   return new ReferenceNode(stringifyChildren(t.child(0)), true);
+        if (head.equals("{"))   return new BracedNode(walkSeq(t.child(0)));
+        if (head.equals("::"))  return walkSeq(t.child(1)).tag(walkString(t.child(0)));
+        if (head.equals("...")) return new DropNode(new RepeatNode(new TildeNode(new AtomNode()), null, true,  true,  false));
+
+        if (head.equals("++"))  return new RepeatNode(walkElement(t.child(0)), null,                      false, true,  true);
+        if (head.equals("+"))   return new RepeatNode(walkElement(t.child(0)), null,                      false, true,  false);
+        if (head.equals("++/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   false, true,  true);
+        if (head.equals("+/"))  return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   false, true,  false);
+        if (head.equals("**"))  return new RepeatNode(walkElement(t.child(0)), null,                      true,  true,  true);
+        if (head.equals("*"))   return new RepeatNode(walkElement(t.child(0)), null,                      true,  true,  false);
+        if (head.equals("**/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   true,  true,  true);
+        if (head.equals("*/"))  return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   true,  true,  false);
+        if (head.equals("?"))   return new RepeatNode(walkElement(t.child(0)), null,                      true,  false, false);
+
+        if (head.equals("!"))   return new DropNode(walkElement(t.child(0)));
+        if (head.equals("^"))   return new LiteralNode(walkString(t.child(0)), true);
+        if (head.equals("`"))   return walkElement(t.child(0)).lifted();
         if (head.equals("Quoted")) return stringifyChildren(t);
         if (head.equals("Literal")) return new LiteralNode(walkString(t.child(0)));
         if (head.equals("->")) return walkSeq(t.child(0)).follow(walkElement(t.child(1)));
@@ -198,7 +196,7 @@ public class GrammarAST {
         public Union build(String rootNonterminal) {
             Context cx = new Context(this);
             Union u = null;
-            for(GrammarBuilder.NonTerminalNode nt : values())
+            for(GrammarAST.NonTerminalNode nt : values())
                 if (nt.name.equals(rootNonterminal))
                     return (Union)cx.get(nt.name);
             return null;
@@ -347,20 +345,20 @@ public class GrammarAST {
                     els[i] = elements[i].build(cx, cnt, dropall);
             }
             if (tag==null && multiNonDrop)
-                throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create(els, ""));
-            boolean lift = false;
-            if (elements.length > 0 && elements[0].lifted)
-                lift = true;
+                throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create("", els));
+            boolean[] lifts = new boolean[elements.length];
+            for(int i=0; i<elements.length; i++)
+                lifts[i] = elements[i].lifted;
             if (!multiNonDrop) {
                 if (idx == -1) 
                     ret = tag==null
-                        ? Sequence.create(els, illegalTag)
-                        : Sequence.createLeft(tag, els, drops, lift);
+                        ? Sequence.create(illegalTag, els)
+                        : Sequence.create(tag, els, drops, lifts);
                 else if (tag==null) ret = Sequence.create(els, idx);
-                else ret = Sequence.createLeft(tag, els, drops, lift);
+                else ret = Sequence.create(tag, els, drops, lifts);
             }
             if (multiNonDrop)
-                ret = Sequence.createLeft(tag, els, drops, lift);
+                ret = Sequence.create(tag, els, drops, lifts);
             if (this.follow != null)
                 ret = ret.followedBy(this.follow.toAtom(cx));
             return ret;
diff --git a/src/edu/berkeley/sbp/misc/Demo2.java b/src/edu/berkeley/sbp/misc/Demo2.java
index c31a9df..a7c2545 100644
--- a/src/edu/berkeley/sbp/misc/Demo2.java
+++ b/src/edu/berkeley/sbp/misc/Demo2.java
@@ -19,8 +19,8 @@ public class Demo2 {
         Element[] mult  = new Element[] { expr, atom('*'), expr };
         Element[] paren = new Element[] { atom('('), expr, atom(')') };
         
-        Sequence addSequence = Sequence.create("add", add, null, false);
-        Sequence multSequence = Sequence.create("mult", mult, null, false);
+        Sequence addSequence = Sequence.create("add", add, null);
+        Sequence multSequence = Sequence.create("mult", mult, null);
 
         // uncomment this line to disambiguate
         //multSequence = multSequence.andnot(Sequence.create("add", add, null, false));