Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

IndexOutOfBoundsException on search for implicit =:= #3399

Closed
scabug opened this issue May 6, 2010 · 4 comments
Closed

IndexOutOfBoundsException on search for implicit =:= #3399

scabug opened this issue May 6, 2010 · 4 comments
Assignees
@adriaanm
Labels
implicit
Milestone
2.8.1

Comments

@scabug
Copy link

scabug commented May 6, 2010

With 2.8.0.r21826. From the call to transpose in the stack trace, it might be related to #3397. The fix for that doesn't help, though. Speculating, it might be because transpose is being called on an irregular "matrix".

The code:

object Nats {
    sealed trait Nat {
        // fold right on N, N-1, ..., 1
        type FoldR[Init <: Type, Type, F <: Fold[Nat, Type]] <: Type
    }
    sealed trait _0 extends Nat {
        type FoldR[Init <: Type, Type, F <: Fold[Nat, Type]] = Init
    }
    sealed trait Succ[N <: Nat] extends Nat {
        type FoldR[Init <: Type, Type, F <: Fold[Nat, Type]] =
          F#Apply[Succ[N], N#FoldR[Init, Type, F]]
    }
    
    type Add[A <: Nat, B <: Nat] = A#FoldR[B, Nat, Inc]
    trait Fold[-Elem, Value] {
        type Apply[N <: Elem, Acc <: Value] <: Value
    }
    type Inc = Fold[Any, Nat] {
        type Apply[N <: Any, Acc <: Nat] = Succ[Acc]
    }
    
    type _1 = Succ[_0]
    implicitly[ Add[_1, _1] =:= _1]
}

First part of the exception (can provide the full trace if it is useful)

java.lang.IndexOutOfBoundsException: 1                                                                                                             
        at scala.collection.immutable.Vector.checkRangeConvert(Vector.scala:105)                                                                   
        at scala.collection.immutable.Vector.apply(Vector.scala:95)                                                                                
        at scala.collection.generic.GenericTraversableTemplate$$$$anonfun$$transpose$$1$$$$anonfun$$apply$$1.apply(GenericTraversableTemplate.scala:115)   
        at scala.collection.generic.GenericTraversableTemplate$$$$anonfun$$transpose$$1$$$$anonfun$$apply$$1.apply(GenericTraversableTemplate.scala:114)   
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.collection.generic.GenericTraversableTemplate$$$$anonfun$$transpose$$1.apply(GenericTraversableTemplate.scala:114)                    
        at scala.collection.generic.GenericTraversableTemplate$$$$anonfun$$transpose$$1.apply(GenericTraversableTemplate.scala:112)                    
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.collection.generic.GenericTraversableTemplate$$class.transpose(GenericTraversableTemplate.scala:112)                               
        at scala.collection.immutable.List.transpose(List.scala:46)                                                                                
        at scala.tools.nsc.symtab.Types$$class.mergePrefixAndArgs(Types.scala:5092)                                                                 
        at scala.tools.nsc.symtab.SymbolTable.mergePrefixAndArgs(SymbolTable.scala:14)                                                             
        at scala.tools.nsc.symtab.Types$$class.lubList(Types.scala:4721)                                                                            
        at scala.tools.nsc.symtab.Types$$class.lubBaseTypeSeq(Types.scala:4727)                                                                     
        at scala.tools.nsc.symtab.Types$$class.lub0$$1(Types.scala:4880)                                                                             
        at scala.tools.nsc.symtab.Types$$class.lub(Types.scala:4942)                                                                                
        at scala.tools.nsc.symtab.SymbolTable.lub(SymbolTable.scala:14)                                                                            
        at scala.tools.nsc.symtab.Types$$class.solveOne$$1(Types.scala:4674)                                                                         
        at scala.tools.nsc.symtab.Types$$$$anonfun$$solve$$1.apply(Types.scala:4683)                                                                   
        at scala.tools.nsc.symtab.Types$$$$anonfun$$solve$$1.apply(Types.scala:4682)                                                                   
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.tools.nsc.symtab.Types$$class.solve(Types.scala:4682)                                                                              
        at scala.tools.nsc.symtab.SymbolTable.solve(SymbolTable.scala:14)                                                                          
        at scala.tools.nsc.typechecker.Infer$$class.solvedTypes(Infer.scala:153)                                                                    
        at scala.tools.nsc.Global$$analyzer$$.solvedTypes(Global.scala:291)                                                                          
        at scala.tools.nsc.typechecker.Infer$$Inferencer.exprTypeArgs(Infer.scala:464)                                                              
        at scala.tools.nsc.typechecker.Infer$$Inferencer.inferExprInstance(Infer.scala:1158)                                                        
        at scala.tools.nsc.typechecker.Typers$$Typer.instantiate(Typers.scala:1003)                                                                 
        at scala.tools.nsc.typechecker.Typers$$Typer.adapt(Typers.scala:939)                                                                        
        at scala.tools.nsc.typechecker.Typers$$Typer.adapt(Typers.scala:800)                                                                        
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.typedImplicit0(Implicits.scala:459)                                                
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.typedImplicit(Implicits.scala:354)                                                 
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.tryImplicit$$1(Implicits.scala:604)                                                 
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch$$$$anonfun$$addAppInfos$$1$$1.apply(Implicits.scala:612)                                
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch$$$$anonfun$$addAppInfos$$1$$1.apply(Implicits.scala:609)                                
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.addAppInfos$$1(Implicits.scala:609)                                                 
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch$$$$anonfun$$applicableInfos$$1.apply(Implicits.scala:621)                              
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch$$$$anonfun$$applicableInfos$$1.apply(Implicits.scala:621)                              
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.applicableInfos(Implicits.scala:621)                                               
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.searchImplicit(Implicits.scala:645)                                                
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.implicitManifestOrOfExpectedType(Implicits.scala:862)                              
        at scala.tools.nsc.typechecker.Implicits$$ImplicitSearch.bestImplicit(Implicits.scala:887)                                                  
        at scala.tools.nsc.typechecker.Implicits$$class.inferImplicit(Implicits.scala:52)                                                           
        at scala.tools.nsc.Global$$analyzer$$.inferImplicit(Global.scala:291)                                                                        
        at scala.tools.nsc.typechecker.Typers$$Typer$$$$anonfun$$applyImplicitArgs$$1.apply(Typers.scala:188)                                           
        at scala.tools.nsc.typechecker.Typers$$Typer$$$$anonfun$$applyImplicitArgs$$1.apply(Typers.scala:183)                                           
        at scala.collection.LinearSeqOptimized$$class.foreach(LinearSeqOptimized.scala:62)                                                          
        at scala.collection.immutable.List.foreach(List.scala:46)                                                                                  
        at scala.tools.nsc.typechecker.Typers$$Typer.applyImplicitArgs(Typers.scala:183)                                                            
        at scala.tools.nsc.typechecker.Typers$$Typer.adapt(Typers.scala:822)                                                                        
        at scala.tools.nsc.typechecker.Typers$$Typer.typed(Typers.scala:4051)                                                                       
        at scala.tools.nsc.typechecker.Typers$$Typer.typedStat$$1(Typers.scala:2036)                                                                 
        at scala.tools.nsc.typechecker.Typers$$Typer$$$$anonfun$$20.apply(Typers.scala:2104)                                                           
        at scala.tools.nsc.typechecker.Typers$$Typer$$$$anonfun$$20.apply(Typers.scala:2104)
@scabug
Copy link
Author

scabug commented May 6, 2010

Imported From: https://issues.scala-lang.org/browse/SI-3399?orig=1
Reporter: @harrah

@scabug
Copy link
Author

scabug commented May 6, 2010

@paulp said:
Without really looking, I'm sure a transpose call is the root cause if it's irregular, because it assumes the size of the head is the size of every element. I would definitely prefer throwing an exception in transpose to any attempt to accommodate irregular sizes. (In fact I intend to do that unless someone says otherwise.)

@scabug
Copy link
Author

scabug commented May 7, 2010

@paulp said:
Adriaan (since I figure this is you) I patched transpose to fail fast and here's what it says with the above program:

Exception in thread "main" java.lang.IllegalArgumentException: traverse arguments are irregular:
  first was List(Nats._0) (length 1)
  later was List(Nats._1, Nats.Nat, Nats.Inc) (length 3)

@scabug
Copy link
Author

scabug commented Jul 8, 2010

@adriaanm said:
(In r22513) closes #3399. mergePrefixAndArgs expects types that have equal type symbols (modulo normalization) but did not normalize these types before retrieving their typeArgs

this broke the invariant that argss is a regular matrix

review by odersky

@scabug scabug closed this as completed May 18, 2011
@scabug scabug added this to the 2.8.1 milestone Apr 7, 2017
This was referenced Apr 7, 2017
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@adriaanm adriaanm

Labels
implicit
Projects
None yet
Milestone
2.8.1
Development

No branches or pull requests
2 participants
@adriaanm @scabug