Included optimization for top-level switches on...

Included optimization for top-level switches on expressions of type Int.
It is switched off in the checked in version.

5 files changed, 222 insertions, 16 deletions

diff --git a/sources/scalac/ast/printer/TextTreePrinter.java b/sources/scalac/ast/printer/TextTreePrinter.java
index 50ff615b6d..a956bcb8ee 100644
--- a/sources/scalac/ast/printer/TextTreePrinter.java
+++ b/sources/scalac/ast/printer/TextTreePrinter.java
@@ -456,6 +456,30 @@ public class TextTreePrinter implements TreePrinter {
             printType(tree);
             break;
 
+		case Switch(Tree expr, int[] tags, Tree[] bodies, Tree defaultBody):
+			print("<switch>");
+			print(Text.Space);
+            print(TXT_LEFT_PAREN);
+            print(expr);
+            print(TXT_RIGHT_PAREN);
+            print(Text.Space);
+            indent();
+            print(TXT_BLOCK_BEGIN);
+			for (int i = 0; i < tags.length; i++) {
+				print(KW_CASE);
+				print("" + i);
+				print(Text.Space);
+            	print(TXT_RIGHT_ARROW);
+            	print(Text.Space);
+            	print(bodies[i]);
+            	print(Text.Newline);
+            }
+            print("<default> => ");
+            print(defaultBody);
+            undent();
+        	print(TXT_BLOCK_END);
+			break;
+
         case New(Tree.Template templ):
             printTemplate(KW_NEW, templ, false);
             printType(tree);
diff --git a/sources/scalac/transformer/Erasure.java b/sources/scalac/transformer/Erasure.java
index b6493859c6..c2690a9c67 100644
--- a/sources/scalac/transformer/Erasure.java
+++ b/sources/scalac/transformer/Erasure.java
@@ -522,6 +522,7 @@ public class Erasure extends Transformer implements Modifiers {
         case This(_):
         case Literal(_):
         case TypeTerm():
+        case Switch(_, _, _, _):  // MZ: this this right?
 	    return super.transform(tree).setType(owntype);
 
         case Bad():
diff --git a/sources/scalac/transformer/matching/CodeFactory.java b/sources/scalac/transformer/matching/CodeFactory.java
index db644a681d..25d6af5fa4 100644
--- a/sources/scalac/transformer/matching/CodeFactory.java
+++ b/sources/scalac/transformer/matching/CodeFactory.java
@@ -145,6 +145,13 @@ class CodeFactory extends PatternTool {
 	return result ;
     }
 
+	Tree Switch(Tree selector,
+	            int[] tags,
+	            Tree[] bodies,
+	            Tree defaultBody) {
+		return make.Switch(selector.pos, selector, tags, bodies, defaultBody);
+	}
+
     /** returns `List[ elemType ]' */
       Type SeqListType( Type elemType ) {
             return Type.TypeRef( defs.SCALA_TYPE,
diff --git a/sources/scalac/transformer/matching/PatternMatcher.java b/sources/scalac/transformer/matching/PatternMatcher.java
index 7960bdabcd..399e366afe 100644
--- a/sources/scalac/transformer/matching/PatternMatcher.java
+++ b/sources/scalac/transformer/matching/PatternMatcher.java
@@ -24,6 +24,8 @@ import java.util.Iterator ;
 
 public class PatternMatcher extends PatternTool {
 
+    private static boolean OPTIMIZE = false;
+
     /** the owner of the pattern matching expression
      */
     Symbol owner;
@@ -614,6 +616,169 @@ public class PatternMatcher extends PatternTool {
 //////////// generator methods
 
     public Tree toTree() {
+    	if (OPTIMIZE && isTopLevelIntSwitch())
+    		return intSwitchToTree();
+    	else
+    		return generalSwitchToTree();
+    }
+
+    protected boolean isTopLevelIntSwitch() {
+    	if (selector.type.widen().isSameAs(defs.INT_TYPE)) {
+    		PatternNode patNode = root.and;
+    		while (patNode != null) {
+   				PatternNode node = patNode;
+  				while ((node = node.or) != null)
+     				switch (node.and) {
+     					case Body(ValDef[][] bound, Tree[] guard, _):
+     						if ((guard.length > 1) ||
+     						    (guard[0] != Tree.Empty) ||
+     						    (bound[0].length > 0))
+     							return false;
+     						break;
+     					default:
+     						return false;
+     				}
+         		patNode = patNode.next();
+      		}
+      		return true;
+    	} else
+    		return false;
+    }
+
+    static class TagBodyPair {
+    	int tag;
+    	Tree body;
+    	TagBodyPair next;
+
+    	TagBodyPair(int tag, Tree body, TagBodyPair next) {
+    		this.tag = tag;
+    		this.body = body;
+    		this.next = next;
+    	}
+
+    	int length() {
+    		return (next == null) ? 1 : (next.length() + 1);
+    	}
+    }
+
+    static TagBodyPair insert(int tag, Tree body, TagBodyPair current) {
+    	if (current == null)
+    		return new TagBodyPair(tag, body, null);
+    	else if (tag > current.tag)
+    		return new TagBodyPair(current.tag, current.body, insert(tag, body, current.next));
+    	else
+    		return new TagBodyPair(tag, body, current);
+    }
+
+    protected int numCases(PatternNode patNode) {
+    	int n = 0;
+  		while ((patNode = patNode.or) != null)
+     		switch (patNode) {
+ 				case DefaultPat():
+        			break;
+          		default:
+          			n++;
+         	}
+      	return n;
+    }
+
+  	protected Tree defaultBody(PatternNode patNode, Tree otherwise) {
+   		while (patNode != null) {
+   			PatternNode node = patNode;
+  			while ((node = node.or) != null)
+     			switch (node) {
+ 					case DefaultPat():
+        				return bodyToTree(patNode.and);
+         		}
+         	patNode = patNode.next();
+      	}
+      	return otherwise;
+    }
+
+    /** This method translates pattern matching expressions that match
+     *  on integers on the top level.
+     */
+    public Tree intSwitchToTree() {
+    	print();
+    	int ncases = numCases(root.and);
+    	Tree matchError = cf.ThrowMatchError(selector.pos, typeOf(resultVar));
+    	// without a case, we return a match error if there is no default case
+    	if (ncases == 0)
+    		return defaultBody(root.and, matchError);
+    	// for one case we use a normal if-then-else instruction
+    	else if (ncases == 1) {
+    		switch (root.and.or) {
+    			case ConstantPat(Object value):
+    				return cf.If(
+    					cf.Equals(selector,
+    						make.Literal(root.and.or.pos, value).setType(root.and.or.type)),
+    					bodyToTree(root.and.or.and),
+    					defaultBody(root.and, matchError)).
+    						setType(typeOf(resultVar));
+    			default:
+    				return generalSwitchToTree();
+    		}
+		}
+    	// if we have more than 2 cases than use a switch statement
+    	switch (root.and) {
+    		case Header(_, Header next):
+    			TagBodyPair mappings = null;
+    			Tree defaultBody = null;
+    			PatternNode patNode = root.and;
+    			while (patNode != null) {
+    				PatternNode node = patNode.or;
+    				while (node != null) {
+    					switch (node) {
+    						case DefaultPat():
+    							if (defaultBody != null)
+    								throw new ApplicationError();
+    							defaultBody = bodyToTree(node.and);
+                				node = node.or;
+                				break;
+               				case ConstantPat(Object value):
+               					mappings = insert(
+               						((Integer)value).intValue(),
+               						bodyToTree(node.and),
+               						mappings);
+								node = node.or;
+								break;
+            				default:
+            					throw new ApplicationError(node.toString());
+    					}
+    				}
+    				patNode = patNode.next();
+    			}
+    			if (defaultBody == null)
+    				defaultBody = cf.ThrowMatchError(selector.pos, typeOf(resultVar));
+    			if (mappings == null) {
+    				return cf.Switch(selector, new int[0], new Tree[0], defaultBody).setType(typeOf(resultVar));
+    			} else {
+    				int n = mappings.length();
+    				int[] tags = new int[n];
+    				Tree[] bodies = new Tree[n];
+    				n = 0;
+    				while (mappings != null) {
+    					tags[n] = mappings.tag;
+    					bodies[n++] = mappings.body;
+    					mappings = mappings.next;
+    				}
+    				return cf.Switch(selector, tags, bodies, defaultBody).setType(typeOf(resultVar));;
+    			}
+            default:
+            	throw new ApplicationError();
+    	}
+    }
+
+    protected Tree bodyToTree(PatternNode node) {
+       switch (node) {
+       		case Body(_, _, Tree[] body):
+       			return body[0];
+       		default:
+   				throw new ApplicationError();
+		}
+    }
+
+    public Tree generalSwitchToTree() {
         TreeList ts = new TreeList();
         ts.append(
             make.ValDef(selector.pos,
diff --git a/sources/scalac/transformer/matching/PatternNode.java b/sources/scalac/transformer/matching/PatternNode.java
index a1f6f38863..da028b2a6d 100644
--- a/sources/scalac/transformer/matching/PatternNode.java
+++ b/sources/scalac/transformer/matching/PatternNode.java
@@ -23,46 +23,55 @@ public class PatternNode {
     public PatternNode or;
     public PatternNode and;
 
-    public case Header( Tree selector, Header next );
-    public case Body( Tree.ValDef[][] bound, Tree[] guard, Tree[] body );
+    public case Header(Tree selector, Header next);
+    public case Body(Tree.ValDef[][] bound, Tree[] guard, Tree[] body);
     public case DefaultPat();
-    public case ConstrPat( Symbol casted );
-    public case SequencePat( Symbol casted, int len ); // only used in PatternMatcher
-    public case SeqContainerPat( Symbol casted, Tree seqpat ); //   in AlgebraicMatcher
-    public case ConstantPat( Object value );
-    public case VariablePat( Tree tree );
+    public case ConstrPat(Symbol casted);
+    public case SequencePat(Symbol casted, int len); // only used in PatternMatcher
+    public case SeqContainerPat(Symbol casted, Tree seqpat); //   in AlgebraicMatcher
+    public case ConstantPat(Object value);
+    public case VariablePat(Tree tree);
 
 
     public Symbol symbol() {
         switch (this) {
-            case ConstrPat( Symbol casted ):
+            case ConstrPat(Symbol casted):
                 return casted;
-            case SequencePat( Symbol casted, _ ):
+            case SequencePat(Symbol casted, _):
                 return casted;
-            case SeqContainerPat( Symbol casted, _ ):
+            case SeqContainerPat(Symbol casted, _):
                 return casted;
             default:
                 return Symbol.NONE;
         }
     }
 
+    public PatternNode next() {
+    	switch (this) {
+    		case Header(_, Header next):
+    			return next;
+    		default:
+    			return null;
+    	}
+    }
+
     public String toString() {
         switch (this) {
-            case Header( Tree selector, Header next ):
+            case Header(Tree selector, Header next):
                 return "Header(" + selector + ")";
             case Body( _, _, _ ):
                 return "Body";
             case DefaultPat():
                 return "DefaultPat";
-            case ConstrPat( Symbol casted ):
+            case ConstrPat(Symbol casted):
                 return "ConstrPat(" + casted + ")";
-            case SequencePat( Symbol casted, int len ):
+            case SequencePat(Symbol casted, int len):
                 return "SequencePat(" + casted + ", " + len + "...)";
-            case SeqContainerPat( Symbol casted, Tree seqpat ):
+            case SeqContainerPat(Symbol casted, Tree seqpat):
                 return "SeqContainerPat(" + casted + ", " + seqpat + ")";
-            case ConstantPat( Object value ):
+            case ConstantPat(Object value):
                 return "ConstantPat(" + value + ")";
-            case VariablePat( Tree tree ):
+            case VariablePat(Tree tree):
                 return "VariablePat";
             default:
                 return "<unknown pat>";