Changeset 4318 for trunk/ProjectFortress

Timestamp:

11/06/09 14:37:52 (3 weeks ago)

Author:

jmaessen

Message:

[compiler, tests] Some refactoring on TreapAndTest. Fixed #362 and
added a test for it. Some misc cleanups on AbstractMethodChecker
that didn't make it into the last commit [Still looking to fix this to
avoid O(n^{2) behavior].}

Location:

trunk/ProjectFortress

Files:

• compiler_tests/EmptyDoEnd.fss (added)
• compiler_tests/EmptyDoEnd.test (added)
• compiler_tests/TreapAndTest.fss (modified) (17 diffs)
• src/com/sun/fortress/compiler/codegen/CodeGen.java (modified) (5 diffs)
• src/com/sun/fortress/scala_src/typechecker/AbstractMethodChecker.scala (modified) (3 diffs)

trunk/ProjectFortress/compiler_tests/TreapAndTest.fss

@@ +1 @@
+(*******************************************************************************
+    Copyright 2009 Sun Microsystems, Inc.,
+    4150 Network Circle, Santa Clara, California 95054, U.S.A.
+    All rights reserved.
+
+    U.S. Government Rights - Commercial software.
+    Government users are subject to the Sun Microsystems, Inc. standard
+    license agreement and applicable provisions of the FAR and its supplements.
+
+    Use is subject to license terms.
+
+    This distribution may include materials developed by third parties.
+
+    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
+    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
+ ******************************************************************************)
+
 export Executable
 
@@ -55 +72 @@
 
 
-
-
-Min_HK : ZZ32 = -1
+Min_W : ZZ32 = -1
 
 (* We organize the treap as a max-treap; a min-treap would work just as well. *)
@@ -67 +82 @@
     getter min(): Treap = Treap(root.min)
     getter max(): Treap = Treap(root.max)
+    (* Union and intersection are left-biased *)
     opr UNION(self, other: Treap): Treap = Treap(root.combine(UnionOp, other.root))
     opr INTERSECTION(self, other: Treap): Treap = Treap(root.combine(IntersectionOp, other.root))
@@ -73 +89 @@
     opr SYMDIFF(self, other: Treap): Treap =
         Treap(root.combine(SymdiffOp, other.root))
+    containsKey(key:ZZ32): Boolean = NOT root.nodeWithKey(key).isEmpty
     replace(key:ZZ32, val:String): Treap = singleton(key,val) UNION self
     add(key:ZZ32, val:String): Treap = self UNION singleton(key,val)
-    remove(key:ZZ32): Treap = self DIFFERENCE Treap(Leaf1(Min_HK,key,""))
+    remove(key:ZZ32): Treap = self DIFFERENCE Treap(Leaf1(Min_W,key,""))
     lookup(key:ZZ32, defaultValue:String): String =
         root.nodeWithKey(key).rootValue(defaultValue)
@@ -88 +105 @@
 trait TreapNode comprises { NonEmpty, Empty }
     getter isEmpty(): Boolean
-    getter hk(): ZZ32
+    getter w(): ZZ32
     getter min(): TreapNode
     getter max(): TreapNode
@@ -121 +138 @@
 object Empty extends TreapNode
     getter isEmpty(): Boolean = true
-    getter hk(): ZZ32 = Min_HK
+    getter w(): ZZ32 = Min_W
     getter min(): TreapNode = self
     getter max(): TreapNode = self
@@ -140 +157 @@
     joinNE(l: NonEmpty): NonEmpty = l
 
-    combine(c: CombiningOp, r: TreapNode): TreapNode = c.leftEmpty(r)
-    combineNE(l: NonEmpty, c: CombiningOp): TreapNode = c.rightEmpty(l)
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.rightEmpty(lr)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.leftEmpty(rr)
+    combine(c: CombiningOp, r: TreapNode): TreapNode = c.rightAlone(r)
+    combineNE(l: NonEmpty, c: CombiningOp): TreapNode = c.leftAlone(l)
+
+    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.leftAlone(lr)
+    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.rightAlone(rr)
 
     rootKey(defaultKey: ZZ32): ZZ32 = defaultKey
@@ -151 +168 @@
 
 trait NonEmpty extends TreapNode comprises { Leaf1, Node }
+    getter isEmpty(): Boolean = false
     getter k(): ZZ32
     getter v(): String
     getter root(): Leaf1
+
+    join(r: TreapNode): TreapNode = r.joinNE(self)
     (* Join this treap (on left) to r (on right);
-       assumes hk > r.hk *)
+       assumes w > r.w *)
     joinNEH(r: NonEmpty): NonEmpty
 
+    combine(c: CombiningOp, r: TreapNode): TreapNode =
+        r.combineNE(self,c)
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode
-end
-
-object Leaf1(hk0: ZZ32, k0: ZZ32, v0: String) extends NonEmpty
-    getter isEmpty(): Boolean = false
+
+    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self.root)
+    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self.root,rr)
+
+    rootKey(defaultKey: ZZ32): ZZ32 = self.k
+    rootValue(defaultValue: String): String = self.v
+end
+
+object Leaf1(w0: ZZ32, k0: ZZ32, v0: String) extends NonEmpty
     getter k(): ZZ32 = k0
     getter v(): String = v0
     getter root(): Leaf1 = self
-    getter hk(): ZZ32 = hk0
+    getter w(): ZZ32 = w0
     getter min(): TreapNode = self
     getter max(): TreapNode = self
@@ -172 +199 @@
     mkString(withParens: Boolean): String =
         if withParens then
-            "<" hk0.asString ">" self.asString
+            "<" w0.asString ">" self.asString
         else
             self.asString
@@ -197 +224 @@
         if key < k0 then self else Empty end
 
-    join(r: TreapNode): TreapNode = r.joinNE(self)
     joinNE(l: NonEmpty): NonEmpty =
-        if hk0 > l.hk then
-            Node(l, hk0, k0, v0, Empty)
+        if w0 > l.w then
+            Node(l, w0, k0, v0, Empty)
         else
             l.joinNEH(self)
         end
     joinNEH(r: NonEmpty): NonEmpty =
-        Node(Empty, hk0, k0, v0, r)
-
-    combine(c: CombiningOp, r: TreapNode): TreapNode =
-        r.combineNE(self,c)
+        Node(Empty, w0, k0, v0, r)
+
     combineNE(l: NonEmpty, c: CombiningOp): TreapNode =
-        if hk0 < l.hk then
+        if w0 > l.w then
+            (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
+            c.leftAlone(lt).join(m.combineRootR(c, self)).join(c.leftAlone(rt))
+        else
             l.combineNEH(c,self)
-        else
-            (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
-            c.rightEmpty(lt).join(m.combineRootR(c, self)).join(c.rightEmpty(rt))
         end
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode = do
             (lt, m, rt) = (r.splitL(k0), r.nodeWithKey(k0), r.splitR(k0))
-            c.leftEmpty(lt).join(m.combineRootL(self, c)).join(c.leftEmpty(rt))
-        end
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self,rr)
-
-    rootKey(defaultKey: ZZ32): ZZ32 = k0
-    rootValue(defaultValue: String): String = v0
+            c.rightAlone(lt).join(m.combineRootL(self, c)).join(c.rightAlone(rt))
+        end
 end
 
@@ -231 +249 @@
     Leaf1(randomZZ32(2147483647), key, val)
 
-object Node(left: TreapNode, hk0: ZZ32, k0: ZZ32, v0: String, right: TreapNode)
+object Node(left: TreapNode, w0: ZZ32, k0: ZZ32, v0: String, right: TreapNode)
         extends NonEmpty
-    getter isEmpty(): Boolean = false
     getter k(): ZZ32 = k0
     getter v(): String = v0
-    getter root(): Leaf1 = Leaf1(hk0, k0, v0)
-    getter hk(): ZZ32 = hk0
+    getter root(): Leaf1 = Leaf1(w0, k0, v0)
+    getter w(): ZZ32 = w0
     getter min(): TreapNode =
         if left.isEmpty then self.root else left.min end
@@ -247 +264 @@
         (l,r) = (left.mkString(withParens), right.mkString(withParens))
         if withParens then
-            "(" l ") <" hk0.asString ">" mid " (" r ")"
+            "(" l ") <" w0.asString ">" mid " (" r ")"
         else
             lh = if l.isEmpty then mid else l " " mid end
@@ -258 +275 @@
         if key < k0 then
             (l, match, r) = left.split(key)
-            (l, match, node(r, hk0, k0, v0, right))
+            (l, match, node(r, w0, k0, v0, right))
         elif key > k0 then
             (l, match, r) = right.split(key)
-            (node(left, hk0, k0, v0, l), match, r)
+            (node(left, w0, k0, v0, l), match, r)
         else
             (left, self, right)
@@ -271 +288 @@
             left.splitL(key)
         elif key > k0 then
-            Node(left, hk0, k0, v0, right.splitL(key))
+            Node(left, w0, k0, v0, right.splitL(key))
         else
             left
@@ -287 +304 @@
     splitR(key:ZZ32): TreapNode =
         if key < k0 then
-            Node(left.splitR(key), hk0, k0, v0, right)
+            Node(left.splitR(key), w0, k0, v0, right)
         elif key > k0 then
             right.splitR(key)
@@ -294 +311 @@
         end
 
-    join(r: TreapNode): TreapNode = r.joinNE(self)
     joinNE(l: NonEmpty): NonEmpty =
-        if hk0 > l.hk then
-            Node(l.join(left), hk0, k0, v0, right)
+        if w0 > l.w then
+            Node(l.join(left), w0, k0, v0, right)
         else
             l.joinNEH(self)
         end
     joinNEH(r: NonEmpty): NonEmpty =
-        Node(left, hk0, k0, v0, right.join(r))
-
-    combine(c: CombiningOp, r: TreapNode): TreapNode =
-        r.combineNE(self,c)
+        Node(left, w0, k0, v0, right.join(r))
+
     combineNE(l: NonEmpty, c: CombiningOp): TreapNode =
-        if hk0 < l.hk then
-            l.combineNEH(c,self)
-        else
+        if w0 > l.w then
             (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
             lt.combine(c,left).join(m.combineRootR(c, self.root)).join(rt.combine(c,right))
+        else
+            l.combineNEH(c,self)
         end
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode = do
@@ -317 +331 @@
             left.combine(c,lt).join(m.combineRootL(self.root, c)).join(right.combine(c,rt))
         end
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self.root)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self.root,rr)
-
-    rootKey(defaultKey: ZZ32): ZZ32 = k0
-    rootValue(defaultValue: String): String = v0
 end
 
 trait CombiningOp
-    leftEmpty(right: TreapNode): TreapNode
-    rightEmpty(left: TreapNode): TreapNode
+    rightAlone(right: TreapNode): TreapNode
+    leftAlone(left: TreapNode): TreapNode
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode
 end
 
 object UnionOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = right
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = right
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = leftArg
 end
 
 object IntersectionOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = Empty
-    rightEmpty(left: TreapNode): TreapNode = Empty
+    rightAlone(right: TreapNode): TreapNode = Empty
+    leftAlone(left: TreapNode): TreapNode = Empty
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = leftArg
 end
 
 object DifferenceOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = Empty
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = Empty
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = Empty
 end
 
 object SymdiffOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = right
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = right
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = Empty
 end

trunk/ProjectFortress/src/com/sun/fortress/compiler/codegen/CodeGen.java

@@ -524 +524 @@
     private void doStatements(List<Expr> stmts) {
         int onStack = 0;
+        if (stmts.isEmpty()) {
+            pushVoid();
+            return;
+        }
         for ( Expr e : stmts ) {
             popAll(onStack);
@@ -555 +559 @@
         inABlock=oldInABlock;
     }
+
     public void forChainExpr(ChainExpr x) {
         debug( "forChainExpr", x);
@@ -651 +656 @@
 
         dumpClass( packageAndClassName );
-        
+
         try {
             jos.close();
@@ -2410 +2415 @@
         Type receiverType = exprType(obj);
         if (!(receiverType instanceof TraitType)) {
-            sayWhat(x, "receiver type is not TraitType in " + x);
+            sayWhat(x, "receiver type "+receiverType+" is not TraitType in " + x);
         }
 
@@ -2482 +2487 @@
     public void for_RewriteFnApp(_RewriteFnApp x) {
         debug("for_RewriteFnApp ", x,
-                     " args = ", x.getArgument(), " function = ", x.getFunction(), 
+                     " args = ", x.getArgument(), " function = ", x.getFunction(),
               " function class = ", x.getFunction());
         // This is a little weird.  If a function takes no arguments the parser gives me a void literal expr

trunk/ProjectFortress/src/com/sun/fortress/scala_src/typechecker/AbstractMethodChecker.scala

@@ -74 +74 @@
         val inherited = inheritedMethods(traits, extendsC, Set(), typeAnalyzer)
                         .map(t => t._1.asInstanceOf[IdOrOp].getText)
-        for ( d <- decls ; if d.isInstanceOf[FnDecl] ) {
-          if ( NU.isFunctionalMethod(NU.getParams(d.asInstanceOf[FnDecl])) &&
-               ! inherited.exists(NU.getName(d.asInstanceOf[FnDecl]).asInstanceOf[IdOrOp].getText.equals(_)) )
-            error(span, "Object expressions should not define any new " +
-                  "functional methods.")
-        }
+        for {
+          d <- decls;
+          if d.isInstanceOf[FnDecl];
+          if NU.isFunctionalMethod(NU.getParams(d.asInstanceOf[FnDecl]));
+          if !inherited.exists(NU.getName(d.asInstanceOf[FnDecl]).asInstanceOf[IdOrOp]
+                               .getText.equals(_))
+        } error(span, "Object expressions should not define any new " +
+                      "functional methods.")
 
       case _ => super.walk(node)
@@ -95 +97 @@
     typeAnalyzer = typeAnalyzer.extend(sparams, None)
     val toCheck = inheritedAbstractMethods(extendsC)
-    for ( (owner, d) <- toCheck ) {
-      if ( ! implement(d, decls, owner) ) {
+    for ( (owner, d) <- toCheck; if (!implement(d, decls, owner)) ) {
         error(span,
               "The inherited abstract method " + d + " from the trait " + owner +
               "\n    in the object " + name +
               " is not defined in the component " + componentName + ".")
-      }
     }
     typeAnalyzer = oldTypeAnalyzer
@@ -129 +129 @@
   private def collectAbstractMethods(name: IdOrOp, decls: List[Decl]) = {
     val set = new HashSet[FnDecl]
-    decls.foreach( (d: Decl) => d match {
-                   case fd@SFnDecl(_,SFnHeader(_,mods,_,_,_,_,_,_),_,body,_) =>
-                     if ( component.typeConses.containsKey(name) ) {
-                       if ( ! body.isDefined ) set += fd
-                     } else if ( mods.isAbstract ) set += fd
-                   case _ => })
+    for ( fd@SFnDecl(_,SFnHeader(_,mods,_,_,_,_,_,_),_,body,_) <- decls ) {
+      if ( component.typeConses.containsKey(name) ) {
+        if ( ! body.isDefined ) set += fd
+      } else if ( mods.isAbstract ) set += fd
+    }
     set
   }