part 2 of the dependent method refactoring: imp...

part 2 of the dependent method refactoring: improved interaction with
implicit search (needed for oopsla paper)

more to come in this area, see e.g. #3346 (stanford edsl stuff)

reopens #13, which wasn't fixed properly before imo, anyway (have a look at -Xprint:typer output before this commit: a type that's not expressible in surface syntax is inferred -- also removed duplicate test file)

closes #3731: co-evolve type alias type symbols when their rhs is
updated and they are referenced by type selections (see typemap)

review by odersky

17 files changed, 331 insertions, 33 deletions

diff --git a/test/files/pos/bug0013.scala b/test/files/pos/bug0013.scala
deleted file mode 100644
index 999a2ab61c..0000000000
--- a/test/files/pos/bug0013.scala
+++ /dev/null
@@ -1,31 +0,0 @@
-// covariant linked list
-abstract class M { self =>
-
-    type T
-    final type selfType = M {type T <: self.T}
-    type actualSelfType >: self.type <: selfType
-
-    def next: selfType
-
-    // I don't understand why this doesn't compile, but that's a separate matter
-    // error: method all2 cannot be accessed in M.this.selfType
-    // because its instance type => Stream[M{type T <: M.this.selfType#T}]
-    // contains a malformed type: M.this.selfType#T
-    // def all2: Stream[M {type T <: self.T}] = Stream.cons(self: actualSelfType, next.all2)
-
-
-    // compiles successfully
-    // def all3: Stream[M {type T <: self.T}] = all3Impl(self: actualSelfType)
-    // private def all3Impl(first: M {type T <: self.T}): Stream[M {type T <: self.T}] = Stream.cons(first, all3Impl(first.next))
-
-
-
-    def all4: Stream[M {type T <: self.T}] = Unrelated.all4Impl[T](self: actualSelfType)
-}
-
-object Unrelated {
-    def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))
-
-    // compiles successfully
-    // def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl[U](first.next))
-}
\ No newline at end of file
diff --git a/test/files/pos/bug1279a.scala b/test/files/pos/bug1279a.scala
index 7568d3afcd..9212b583d4 100644
--- a/test/files/pos/bug1279a.scala
+++ b/test/files/pos/bug1279a.scala
@@ -1,3 +1,4 @@
+// see #13
 // providing the type parameter in the recursive call to all4Impl
 // avoids the problem
 
@@ -31,8 +32,9 @@ abstract class M
 
 object Unrelated
 {
-   def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))
+  // TODO!!! fix this bug for real, it compiles successfully, but weird types are inferred
+   // def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl(first.next))
 
 // compiles successfully
-//      def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl[U](first.next))
+     def all4Impl[U](first: M {type T <: U}): Stream[M {type T <: U}] = Stream.cons(first, all4Impl[U](first.next))
 }
diff --git a/test/files/pos/depmet_implicit_chaining_zw.flags b/test/files/pos/depmet_implicit_chaining_zw.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_chaining_zw.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_chaining_zw.scala b/test/files/pos/depmet_implicit_chaining_zw.scala
new file mode 100644
index 0000000000..e3a145ab38
--- /dev/null
+++ b/test/files/pos/depmet_implicit_chaining_zw.scala
@@ -0,0 +1,28 @@
+trait Zero
+trait Succ[N]
+
+trait ZipWith[N, S] {
+  type T
+  val x: T = error("")
+}
+
+object ZipWith {
+  implicit def ZeroZipWith[S] = new ZipWith[Zero, S] {
+    type T = Stream[S]
+  }
+
+  implicit def SuccZipWith[N, S, R](implicit zWith : ZipWith[N, R]) = new ZipWith[Succ[N], S => R] {
+    type T = Stream[S] => zWith.T // dependent types replace the associated types functionality
+  }
+
+  // can't use implicitly[ZipWith[Succ[Succ[Zero]], Int => String => Boolean]],
+  // since that will chop of the {type T = ... } refinement in adapt (pt = ZipWith[Succ[Succ[Zero]], Int => String => Boolean])
+  // this works
+  // def zipWith(implicit zw: ZipWith[Succ[Succ[Zero]], Int => String => Boolean]): zw.T = zw.x
+  // thus, I present ?: implicitly on steroids!
+  def ?[T <: AnyRef](implicit w: T): w.type = w
+
+  type _2 = Succ[Succ[Zero]]
+  val zw = ?[ZipWith[_2, Int => String => Boolean]].x // : Stream[Int] => Stream[String] => Stream[Boolean]
+  // val zw = implicitly[ZipWith[Succ[Succ[Zero]], Int => String => Boolean]{type T = Stream[Int] => Stream[String] => Stream[Boolean]}].x
+}
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_norm_ret.flags b/test/files/pos/depmet_implicit_norm_ret.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_norm_ret.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_norm_ret.scala b/test/files/pos/depmet_implicit_norm_ret.scala
new file mode 100644
index 0000000000..4cdb2931c6
--- /dev/null
+++ b/test/files/pos/depmet_implicit_norm_ret.scala
@@ -0,0 +1,29 @@
+object Test{
+  def ?[S <: AnyRef](implicit w : S) : w.type = w
+
+  // fallback, lower priority (overloading rules apply: pick alternative in subclass lowest in subtyping lattice)
+  class ZipWithDefault {
+    implicit def ZeroZipWith[S] = new ZipWith[S] {
+      type T = Stream[S]
+    }
+  }
+
+  object ZipWith extends ZipWithDefault {
+    // def apply[S: ZipWith](s : S) = ?[ZipWith[S]].zipWith(s) // TODO: bug return type should be inferred
+    def apply[S](s : S)(implicit zw: ZipWith[S]): zw.T = zw.zipWith(s)
+
+    implicit def SuccZipWith[S,R](implicit zWith : ZipWith[R]) = new ZipWith[S => R] {
+      type T = Stream[S] => zWith.T // dependent types replace the associated types functionality
+    }
+  }
+
+  trait ZipWith[S] {
+    type T
+    def zipWith : S => T = error("")
+  }
+
+  // bug: inferred return type = (Stream[A]) => java.lang.Object with Test.ZipWith[B]{type T = Stream[B]}#T
+  // this seems incompatible with vvvvvvvvvvvvvvvvvvvvvv   -- #3731
+  def map[A,B](f : A => B)   /* : Stream[A] => Stream[B]*/ = ZipWith(f)
+  val tst: Stream[Int] = map{x: String => x.length}(Stream("a"))
+}
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session.flags b/test/files/pos/depmet_implicit_oopsla_session.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session.scala b/test/files/pos/depmet_implicit_oopsla_session.scala
new file mode 100644
index 0000000000..21588a56ad
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session.scala
@@ -0,0 +1,63 @@
+object Sessions {
+  trait Session[This] {
+    type Dual
+    type HasDual[D] = Session[This]{type Dual=D}
+    def run(p: This, dp: Dual): Unit
+  }
+
+  implicit object StopSession extends Session[Stop] {
+    type Dual = Stop
+
+    def run(p: Stop, dp: Stop): Unit = {}
+  }
+
+  implicit def InDual[A, B](implicit sessionDIn: Session[B]) =
+    new Session[In[A, B]] {
+      type Dual = Out[A, sessionDIn.Dual]
+
+      def run(p: In[A, B], dp: Dual): Unit =
+        sessionDIn.run(p.func(dp.x), dp.y)
+  }
+
+  implicit def OutDual[A, B](implicit sessionDOut: Session[B]) =
+    new Session[Out[A, B]] {
+     type Dual = In[A, sessionDOut.Dual]
+
+     def run(p: Out[A, B], dp: Dual): Unit =
+       sessionDOut.run(p.y, dp.func(p.x))
+  }
+
+  sealed case class Stop()
+  sealed case class In[-A, +B](func: A => B)
+  sealed case class Out[+A, +B](x: A, y: B)
+
+  def addServer =
+    In{x: Int =>
+    In{y: Int => System.out.println("Thinking")
+    Out(x+y,
+    Stop())}}
+
+  def addClient =
+    Out(3,
+    Out(4, { System.out.println("Waiting")
+    In{z: Int => System.out.println(z)
+    Stop()}}))
+
+  def runSession[S, D: Session[S]#HasDual](p: S, dp: D) =
+    implicitly[Session[S]#HasDual[D]].run(p, dp)
+
+  // def runSession[S, D](p: S, dp: D)(implicit s: Session[S]#HasDual[D]) =
+  //   s.run(p, dp)
+  //
+  // def runSession[S, D](p: S, dp: D)(implicit s: Session[S]{type Dual=D}) =
+  //   s.run(p, dp)
+
+  // TODO: can we relax the ordering restrictions on dependencies so that we can use
+  // def runSession[S](p: S, dp: s.Dual)(implicit s: Session[S]) =
+  //   s.run(p, dp)
+  // to emphasise similarity of type parameters and implicit arguments:
+  // def runSession[S][val s: Session[S]](p: S, dp: s.Dual) =
+  //   s.run(p, dp)
+
+  def myRun = runSession(addServer, addClient)
+}
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session_2.flags b/test/files/pos/depmet_implicit_oopsla_session_2.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session_2.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session_2.scala b/test/files/pos/depmet_implicit_oopsla_session_2.scala
new file mode 100644
index 0000000000..5c3b78e3f5
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session_2.scala
@@ -0,0 +1,87 @@
+object Sessions {
+  def ?[T <: AnyRef](implicit w: T): w.type = w
+
+  // session states
+  sealed case class Stop()
+  sealed case class In[-Data, +Cont](recv: Data => Cont)
+  sealed case class Out[+Data, +Cont](data: Data, cont: Cont)
+
+  // the type theory of communicating sessions:
+
+  // an instance of type Session[S]{type Dual=D} is evidence that S and D are duals
+  // such a value witnesses this fact by describing how to compose an instance of S with an instance of D (through the run method)
+  trait Session[S] { type Self = S
+    type Dual
+    type HasDual[D] = Session[Self]{type Dual=D}
+    def run(self: Self, dual: Dual): Unit
+  }
+
+  // friendly interface to the theory
+  def runSession[S, D: Session[S]#HasDual](session: S, dual: D) =
+    ?[Session[S]#HasDual[D]].run(session, dual)
+
+  // facts in the theory:
+
+  // ------------------------[StopDual]
+  // Stop is the dual of Stop
+  implicit object StopDual extends Session[Stop] {
+    type Dual = Stop
+
+    def run(self: Self, dual: Dual): Unit = {}
+  }
+
+  //            CD is the dual of Cont
+  // -------------------------------------------[InDual]
+  // Out[Data, CD] is the dual of In[Data, Cont]
+  implicit def InDual[Data, Cont](implicit cont: Session[Cont]) = new Session[In[Data, Cont]] {
+    type Dual = Out[Data, cont.Dual]
+
+    def run(self: Self, dual: Dual): Unit =
+      cont.run(self.recv(dual.data), dual.cont)
+  }
+
+  //            CD is the dual of Cont
+  // -------------------------------------------[OutDual]
+  // In[Data, CD] is the dual of Out[Data, Cont]
+  implicit def OutDual[Data, Cont](implicit cont: Session[Cont]) = new Session[Out[Data, Cont]] {
+    type Dual = In[Data, cont.Dual]
+
+    def run(self: Self, dual: Dual): Unit =
+      cont.run(self.cont, dual.recv(self.data))
+  }
+
+  // a concrete session
+  def addServer =
+    In{x: Int =>
+    In{y: Int => System.out.println("Thinking")
+    Out(x+y,
+    Stop())}}
+
+  def addClient =
+    Out(3,
+    Out(4, { System.out.println("Waiting")
+    In{z: Int => System.out.println(z)
+    Stop()}}))
+
+  def myRun = runSession(addServer, addClient)
+}
+
+/* future improvements:
+
+
+  // def runSession[S, D](p: S, dp: D)(implicit s: Session[S]#HasDual[D]) =
+  //   s.run(p, dp)
+  //
+  // def runSession[S, D](p: S, dp: D)(implicit s: Session[S]{type Dual=D}) =
+  //   s.run(p, dp)
+
+  // TODO: can we relax the ordering restrictions on dependencies so that we can write
+  //  one possibility: graph of dependencies between arguments must be acyclic
+  // def runSession[S](p: S, dp: s.Dual)(implicit s: Session[S]) =
+  //   s.run(p, dp)
+  // to emphasise similarity of type parameters and implicit arguments:
+  // def runSession[S][val s: Session[S]](p: S, dp: s.Dual) =
+  //   s.run(p, dp)
+
+
+*/
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session_simpler.flags b/test/files/pos/depmet_implicit_oopsla_session_simpler.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session_simpler.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_session_simpler.scala b/test/files/pos/depmet_implicit_oopsla_session_simpler.scala
new file mode 100644
index 0000000000..37bc0958d3
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_session_simpler.scala
@@ -0,0 +1,44 @@
+object Sessions {
+  trait Session {
+    type Dual <: Session
+
+    def run(dp: Dual): Unit
+  }
+
+  sealed case class Stop extends Session {
+    type Dual = Stop
+
+    def run(dp: Dual): Unit = {}
+  }
+
+  // can't write B <: Session{type Dual = BDual} due to limitations in type inference algorithm
+  // (type variables cannot occur on both sides of <:)
+  // using B#Dual instead of BDual is too imprecise, since it is disconnected from the actual argument that is passed for B
+  // would be nice if we could introduce a universal quantification over BDual that is not part of the
+  // type parameter list
+  sealed case class In[A, B <: Session, BDual <: Session](recv: A => B)(implicit dual: B <:< Session{type Dual=BDual}) extends Session {
+    type Dual = Out[A, BDual]
+
+    def run(dp: Dual): Unit = recv(dp.data) run dp.cont
+  }
+
+  sealed case class Out[A, B <: Session](data: A, cont: B) extends Session {
+     type Dual = In[A, cont.Dual, cont.Dual#Dual]
+
+     def run(dp: Dual): Unit = cont run dp.recv(data)
+  }
+
+  def addServer =
+    In{x: Int =>
+    In{y: Int => System.out.println("Thinking")
+    Out(x+y,
+    Stop())}}
+
+  def addClient =
+    Out(3,
+    Out(4, { System.out.println("Waiting")
+    In{z: Int => System.out.println(z)
+    Stop()}}))
+
+  def myRun = addServer run addClient
+}
diff --git a/test/files/pos/depmet_implicit_oopsla_zipwith.flags b/test/files/pos/depmet_implicit_oopsla_zipwith.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_zipwith.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_oopsla_zipwith.scala b/test/files/pos/depmet_implicit_oopsla_zipwith.scala
new file mode 100644
index 0000000000..c76d02c1ae
--- /dev/null
+++ b/test/files/pos/depmet_implicit_oopsla_zipwith.scala
@@ -0,0 +1,44 @@
+case class Zero()
+case class Succ[N](x: N)
+import Stream.{cons, continually}
+
+trait ZipWith[N, S] {
+  type T
+
+  def manyApp: N => Stream[S] => T
+  def zipWith: N => S => T = n => f => manyApp(n)(continually(f))
+}
+object ZipWith {
+  implicit def ZeroZipWith[S] = new ZipWith[Zero, S] {
+    type T = Stream[S]
+
+    def manyApp = n => xs => xs
+  }
+
+  implicit def SuccZipWith[N, S, R](implicit zw: ZipWith[N, R]) =
+    new ZipWith[Succ[N],S => R] {
+      type T = Stream[S] => zw.T
+
+      def zapp[A, B](xs: Stream[A => B], ys: Stream[A]): Stream[B] = (xs, ys) match {
+        case (cons(f, fs), cons(s, ss)) => cons(f(s),zapp(fs, ss))
+        case (_, _) => Stream.empty
+      }
+
+      def manyApp = n => xs => ss => n match {
+        case Succ(i) => zw.manyApp(i)(zapp(xs, ss))
+      }
+    }
+}
+
+object Test {
+  def zWith[N, S](n: N, s: S)(implicit zw: ZipWith[N, S]): zw.T = zw.zipWith(n)(s)
+
+  def zipWith0: Stream[Int] = zWith(Zero(),0)
+
+// (Stream[A]) => java.lang.Object with ZipWith[Zero,B]{type T = Stream[B]}#T
+// should normalise to: Stream[A] => Stream[B]
+  def map[A, B](f: A => B) = zWith(Succ(Zero()),f)
+
+  def zipWith3[A, B, C, D](f: A => B => C => D) = //: Stream[A] => Stream[B] => Stream[C] => Stream[D] = // BUG why do we need a return type?
+    zWith(Succ(Succ(Succ(Zero()))),f)
+}
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_tpbetareduce.flags b/test/files/pos/depmet_implicit_tpbetareduce.flags
new file mode 100644
index 0000000000..1c26b24745
--- /dev/null
+++ b/test/files/pos/depmet_implicit_tpbetareduce.flags
@@ -0,0 +1 @@
+-Ydependent-method-types
\ No newline at end of file
diff --git a/test/files/pos/depmet_implicit_tpbetareduce.scala b/test/files/pos/depmet_implicit_tpbetareduce.scala
new file mode 100644
index 0000000000..35d260683b
--- /dev/null
+++ b/test/files/pos/depmet_implicit_tpbetareduce.scala
@@ -0,0 +1,12 @@
+trait HOSeq {
+  trait Accumulator[+coll[x], elT]
+  trait Iterable[+t] {
+    type m[+x]
+    def accumulator[t]: Accumulator[m, t]
+  }
+  implicit def listAccumulator[elT]: Accumulator[List, elT] = new Accumulator[List, elT] {}
+  trait List[+t] extends Iterable[t] {
+    type m[+x] = List[x]
+    def accumulator[t]: Accumulator[List, t] = listAccumulator[t]
+  }
+}
\ No newline at end of file
diff --git a/test/files/pos/t3731.scala b/test/files/pos/t3731.scala
new file mode 100644
index 0000000000..9a617012b3
--- /dev/null
+++ b/test/files/pos/t3731.scala
@@ -0,0 +1,13 @@
+object Test{
+  trait ZW[S]{type T}
+  def ZipWith[S, M <: ZW[S]]: M#T = error("ZW")
+
+  // meh must be parameterised to force an asSeenFrom that
+  // duplicates the refinement in the TR's pre without updating its sym
+  def meh[A] = ZipWith[A, ZW[A]{type T=Stream[A]}]
+
+  meh[Int]: Stream[Int]
+}
+// debugging output in coevolveSym should say:
+// coevolved type T#11029 : Stream#3234[A#9228] to type T#11277 : Stream#3234[A#9227]
+// with Test.ZW#9219[A#9228]{type T#11029 = Stream#3234[A#9228]} -> Test.ZW#9219[A#9227]{type T#11277 = Stream#3234[A#9227]}