Aladdin - Scala Bugtracking
[#852] project: compiler priority: medium category: bug
submitter assigned to status date submitted
Sean Martin fixed 2006-11-30 12:11:46.0
subject new isSubType magic number is too small
code 
package lampion.scalax;

trait HasTreeXXX {
  type Node <: NodeImpl;
  trait NodeImpl { def self : Node; }
  type TreeNode <: Node with TreeNodeImpl;
  trait TreeNodeImpl extends NodeImpl { def self : TreeNode; }
  type NonRootNode <: TreeNode with NonRootNodeImpl;
  trait NonRootNodeImpl extends TreeNodeImpl { def self : NonRootNode; }
}
trait ScalaScannerXXX extends HasTreeXXX {
  type Expression <: Node with NonRootNode;
  trait ExpressionImpl extends NonRootNodeImpl  { def self : Expression; }
  type BeginsStatement <: Expression with BeginsStatementImpl;       
  trait BeginsStatementImpl extends ExpressionImpl { def self : BeginsStatement; }
  type AbstractDef <: BeginsStatement with AbstractDefImpl;
  trait AbstractDefImpl extends BeginsStatementImpl { def self : AbstractDef; }
  type DefValVar <: AbstractDef with DefValVarImpl;
  trait DefValVarImpl extends AbstractDefImpl { def self : DefValVar; }
  type ValVar <: DefValVar with ValVarImpl;
  trait ValVarImpl extends DefValVarImpl { def self : ValVar; }
  type Val <: ValVar with ValImpl;
  trait ValImpl extends ValVarImpl { def self : Val; }
}
what happened 
sean-mcdirmid:~/workspace/test38/src mcdirmid$ ../../scala/build/quick/bin/scalac -d ../bin/ -sourcepath . \
test/ScalaTyperXXX.scala
Exception in thread "main" java.lang.Error: recursive <:<
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1869)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.tools.nsc.symtab.Types$$anonfun$35.apply(Types.scala:1956)
	at scala.List.exists(List.scala:872)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1956)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1950)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1914)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.symtab.Types$class.isSubType0(Types.scala:1936)
	at scala.tools.nsc.symtab.SymbolTable.isSubType0(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$class.isSubType(Types.scala:1870)
	at scala.tools.nsc.symtab.SymbolTable.isSubType(SymbolTable.scala:10)
	at scala.tools.nsc.symtab.Types$Type.$less$colon$less(Types.scala:266)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.overridesType$0(RefChecks.scala:111)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.checkOverride$0(RefChecks.scala:201)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.checkAllOverrides(RefChecks.scala:211)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:547)
	at scala.tools.nsc.ast.Trees$Transformer.transformTemplate(Trees.scala:1182)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$17.apply(Trees.scala:1082)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$17.apply(Trees.scala:1081)
	at scala.tools.nsc.ast.Trees$Transformer.atOwner(Trees.scala:1202)
	at scala.tools.nsc.ast.Trees$Transformer.transform(Trees.scala:1080)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:601)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStat(RefChecks.scala:482)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.List.flatMap(List.scala:970)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStats(RefChecks.scala:437)
	at scala.tools.nsc.ast.Trees$Transformer.transform(Trees.scala:1114)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:601)
	at scala.tools.nsc.ast.Trees$Transformer.transformTemplate(Trees.scala:1182)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$17.apply(Trees.scala:1082)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$17.apply(Trees.scala:1081)
	at scala.tools.nsc.ast.Trees$Transformer.atOwner(Trees.scala:1202)
	at scala.tools.nsc.ast.Trees$Transformer.transform(Trees.scala:1080)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:601)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStat(RefChecks.scala:482)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.List.flatMap(List.scala:970)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStats(RefChecks.scala:437)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$16.apply(Trees.scala:1077)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$16.apply(Trees.scala:1077)
	at scala.tools.nsc.ast.Trees$Transformer.atOwner(Trees.scala:1202)
	at scala.tools.nsc.ast.Trees$Transformer.transform(Trees.scala:1076)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:601)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStat(RefChecks.scala:482)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer$$anonfun$9.apply(RefChecks.scala:437)
	at scala.List.flatMap(List.scala:970)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transformStats(RefChecks.scala:437)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$16.apply(Trees.scala:1077)
	at scala.tools.nsc.ast.Trees$Transformer$$anonfun$16.apply(Trees.scala:1077)
	at scala.tools.nsc.ast.Trees$Transformer.atOwner(Trees.scala:1202)
	at scala.tools.nsc.ast.Trees$Transformer.transform(Trees.scala:1076)
	at scala.tools.nsc.typechecker.RefChecks$RefCheckTransformer.transform(RefChecks.scala:601)
	at scala.tools.nsc.ast.Trees$Transformer.transformUnit(Trees.scala:1197)
	at scala.tools.nsc.transform.Transform$Phase.apply(Transform.scala:30)
	at scala.tools.nsc.Global$GlobalPhase.applyPhase(Global.scala:220)
	at scala.tools.nsc.Global$GlobalPhase$$anonfun$1.apply(Global.scala:209)
	at scala.tools.nsc.Global$GlobalPhase$$anonfun$1.apply(Global.scala:209)
	at scala.Iterator$class.foreach(Iterator.scala:341)
	at scala.collection.mutable.ListBuffer$$anon$0.foreach(ListBuffer.scala:244)
	at scala.tools.nsc.Global$GlobalPhase.run(Global.scala:209)
	at scala.tools.nsc.Global$Run.compileSources(Global.scala:475)
	at scala.tools.nsc.Global$Run.compile(Global.scala:547)
	at scala.tools.nsc.Main$.process(Main.scala:74)
	at scala.tools.nsc.Main$.main(Main.scala:96)
	at scala.tools.nsc.Main.main(Main.scala)


The culprit is Type.isSubType (Types.scala:1866):


  def isSubType(tp1: Type, tp2: Type): boolean =
    try {
      stc = stc + 1
      if (stc == 20) throw new Error("recursive <:<")
      isSubType0(tp1, tp2)
    } finally {
      stc = stc - 1

    

If I bump the magical 20 number up to something like 42 (a real magical number), my code will actually compile a\
gain.



I have no idea what the other implications of this change will be, however. I guess we are limited to some numbe\
r of <: relationships, and of course in Lampion <: is used a lot to do virtual classes...
what expected All these hardcoded number limits in NSC are really annoying. It took me forever (which is about 3 hours, but I'm ranting right now so...) to track down this crash because the compiler was crashing on random pieces of code. Everywhere in NSC where we have hardcoded limits, things are bound to break. And how would we ever specify this (type hierarchies can only be 20 levels deep?)? Ugh.

There has to be a more robust way of detecting recursive relationships. Why not use a set and detect cycles directly?
[back to overview]
Changes of this bug report
Martin  edited on  2006-12-01 09:45:18.0
Bumped up to 100. It's a crutch anyway, to guard against non-termination of <:<. We should put in Andrews techniques to rule it out from the start.