[Mono-bugs] [Bug 58303][Nor] New - mcs mistakenly reports that types can unify
bugzilla-daemon@bugzilla.ximian.com
bugzilla-daemon@bugzilla.ximian.com
Mon, 10 May 2004 18:35:51 -0400 (EDT)
Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.
Changed by sestoft@dina.kvl.dk.
http://bugzilla.ximian.com/show_bug.cgi?id=58303
--- shadow/58303 2004-05-10 18:35:51.000000000 -0400
+++ shadow/58303.tmp.10884 2004-05-10 18:35:51.000000000 -0400
@@ -0,0 +1,158 @@
+Bug#: 58303
+Product: Mono: Compilers
+Version: unspecified
+OS:
+OS Details:
+Status: NEW
+Resolution:
+Severity:
+Priority: Normal
+Component: C#
+AssignedTo: mono-bugs@ximian.com
+ReportedBy: sestoft@dina.kvl.dk
+QAContact: mono-bugs@ximian.com
+TargetMilestone: ---
+URL:
+Cc:
+Summary: mcs mistakenly reports that types can unify
+
+Description of Problem:
+
+mcs mistakenly reports that types can unify, but they cannot (missing
+occurs/circularity check in type checker?).
+
+
+Steps to reproduce the problem:
+1. Compile the program below
+
+Actual Results:
+
+Mono C# Compiler 0.91.0.0 for Generics
+ex-gen-class-polynomial.cs(22) error CS0695: `Polynomial!1<E>' cannot
+implement both `AddMul!2[Polynomial!1[E],Polynomial!1[E]]' and
+`AddMul!2[E,Polynomial!1[E]]' because they may unify for some type
+parameter substitutions
+
+
+Expected Results:
+
+Program compiles correctly.
+
+
+Additional Information:
+
+Program text (a little involved, I'm afraid):
+
+using System;
+
+// A type implements AddMul<A,R> if one can add an A to it, giving an R:
+
+interface AddMul<A,R> {
+ R Add(A e); // Addition with A, giving R
+ R Mul(A e); // Multiplication with A, giving R
+}
+
+// Polynomials over E, Polynomial<E>:
+
+// The base type E of the polynomial must support addition,
+// multiplication and zero (via the nullary constructor). That's what
+// the type parameter constraint on E says.
+
+// In return, one can add an E or a polynomial over E to a polynomial
+// over E. Similarly, a polynomial over E can be multiplied by an E
+// or by a polynomial over E. That's what the interface clauses say.
+
+class Polynomial<E> : AddMul<E,Polynomial<E>>,
+ AddMul<Polynomial<E>,Polynomial<E>>
+ where E : AddMul<E,E>, new() {
+ // cs contains coefficients of x^0, x^1, ...; absent coefficients are zero.
+ // Invariant: cs != null && cs.Length >= 0; cs.Length==0 represents zero.
+ private readonly E[] cs;
+
+ public Polynomial() {
+ this.cs = new E[0];
+ }
+
+ public Polynomial(E[] cs) {
+ this.cs = cs;
+ }
+
+ public Polynomial<E> Add(Polynomial<E> that) {
+ int newlen = Math.Max(this.cs.Length, that.cs.Length);
+ int minlen = Math.Min(this.cs.Length, that.cs.Length);
+ E[] newcs = new E[newlen];
+ if (this.cs.Length <= that.cs.Length) {
+ for (int i=0; i<minlen; i++)
+ newcs[i] = this.cs[i].Add(that.cs[i]);
+ for (int i=minlen; i<newlen; i++)
+ newcs[i] = that.cs[i];
+ } else {
+ for (int i=0; i<minlen; i++)
+ newcs[i] = this.cs[i].Add(that.cs[i]);
+ for (int i=minlen; i<newlen; i++)
+ newcs[i] = this.cs[i];
+ }
+ return new Polynomial<E>(newcs);
+ }
+
+ public Polynomial<E> Add(E that) {
+ return this.Add(new Polynomial<E>(new E[] { that }));
+ }
+
+ public Polynomial<E> Mul(E that) {
+ E[] newcs = new E[cs.Length];
+ for (int i=0; i<cs.Length; i++)
+ newcs[i] = that.Mul(cs[i]);
+ return new Polynomial<E>(newcs);
+ }
+
+ public Polynomial<E> Mul(Polynomial<E> that) {
+ int newlen = Math.Max(1, this.cs.Length + that.cs.Length - 1);
+ E[] newcs = new E[newlen];
+ for (int i=0; i<newlen; i++) {
+ E sum = new E(); // Permitted by constraint E : new()
+ int start = Math.Max(0, i-that.cs.Length+1);
+ int stop = Math.Min(i, this.cs.Length-1);
+ for (int j=start; j<=stop; j++) {
+ // assert 0<=j && j<this.cs.Length && 0<=i-j && i-j<that.cs.Length;
+ sum = sum.Add(this.cs[j].Mul(that.cs[i-j]));
+ }
+ newcs[i] = sum;
+ }
+ return new Polynomial<E>(newcs);
+ }
+
+ public E Eval(E x) {
+ E res = new E(); // Permitted by constraint E : new()
+ for (int j=cs.Length-1; j>=0; j--)
+ res = res.Mul(x).Add(cs[j]);
+ return res;
+ }
+}
+
+struct Int : AddMul<Int,Int> {
+ private readonly int i;
+ public Int(int i) {
+ this.i = i;
+ }
+ public Int Add(Int that) {
+ return new Int(this.i + that.i);
+ }
+ public Int Mul(Int that) {
+ return new Int(this.i * that.i);
+ }
+ public override String ToString() {
+ return i.ToString();
+ }
+}
+
+class TestPolynomial {
+ public static void Main(String[] args) {
+ // The integer polynomial 2 + 5x + x^2
+ Polynomial<Int> ip =
+ new Polynomial<Int>(new Int[] { new Int(2), new Int(5), new Int(1) });
+ Console.WriteLine(ip.Eval(new Int(10))); // 152
+ Console.WriteLine(ip.Add(ip).Eval(new Int(10))); // 304 = 152 + 152
+ Console.WriteLine(ip.Mul(ip).Eval(new Int(10))); // 23104 = 152 * 152
+ }
+}