sq / JSIL

CIL to Javascript Compiler
http://jsil.org/
Other
1.73k stars 241 forks source link

Incorrect work of SelectMany with covariance IEnumerable cast #353

Closed iskiselev closed 10 years ago

iskiselev commented 10 years ago

I found a problem in next example:

using System;
using System.Collections.Generic;
using System.Linq;

public static class Program {
    public static void Main (string[] args)
    {
        var items = GetItems()
            .SelectMany(item => new[] { item });

        foreach (var item in items)
        {
            Console.WriteLine(item.Id);
        }
    }

    private static IEnumerable<BaseClass> GetItems()
    {
        return new List<Class>() { new Class("TestItem") };
    }
}

public class BaseClass
{
    private string _id;

    public BaseClass(string id)
    {
        _id = id;
    }

    public string Id
    {
        get { return _id; }
    }}

public class Class : BaseClass
{
    public Class(string id) : base(id)
    {
    }
}

This test case fails with next error:

Error: Method 'BaseClass get_Current()' of interface 'System.Collections.Generic.IEnumerator`1[BaseClass]' is not implemented by object JSIL.ArrayEnumerator[System.Object]
(Looked for key(s): 'I47$get_Current$void=34', 
'I47$get_Current$void=53')

I'm still not sure, which implemented in JSIL libraries incorrectly (List or SelectMany method), but if I do SelectMany after covariance cast of List to IEnumerable I reproduce error. At the same time if I do the same with Class[] - it work normally.

iskiselev commented 10 years ago

Seems I found, why in this particular case I have problems. Inside SelectMany implementation there is next call:

state.currentSubsequence = JSIL.GetEnumerator(enumerable);

but inner enumerable in that case is just Array without type information (due to my item => new[] { item } inner selector). This call in that case return IEnumerator, that can't be cast to IEnumerator. If we change that string to:

state.currentSubsequence = JSIL.GetEnumerator(enumerable, TResult);

looks like it work good. I want to investigate it a little bit more (when I tried to use translated version of SelectMany function, instead of one that is implemented in JSIL.Bootstraper.LINQ.js, I had similar error, but at that time I hadn't so much simplified example). I want to look how JSIL.GetEnumerator is used in other parts of JSIL.Bootstraper.LINQ, looks like there may be similar error in other functions. After it I'll prepare fix and pull request.

kg commented 10 years ago

Second arg to GetEnumerator is a late addition, so yeah, it's probably being misused in various places.

iskiselev commented 10 years ago

I have two news:

  1. SelectMany looks like only method that should be modified in JSIL libraries.
  2. Cast method sometimes is not generated by JSIL in all times for Arrays. As JSIL.$PickFallbackMethodForInterfaceMethod always return IEnumerator for array, we still have problems when try to translate SelectMany from System.Core. Here is modified test case:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    
    public static class Program {
        public static void Main (string[] args)
        {
            var items = SelectManyIterator(GetItems(), item => new[] { item });
    
            foreach (var item in items)
            {
                Console.WriteLine(item.Id);
            }
        }
    
        private static IEnumerable<BaseClass> GetItems()
        {
            return new List<Class>() { new Class("TestItem") };
        }
    
        public static IEnumerable<TResult> SelectManyIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
        {
            foreach (TSource source1 in source)
            {
                foreach (TResult result in selector(source1))
                    yield return result;
            }
        }
    }
    
    public class BaseClass
    {
        private string _id;
    
        public BaseClass(string id)
        {
            _id = id;
        }
    
        public string Id
        {
            get { return _id; }
        }}
    
    public class Class : BaseClass
    {
        public Class(string id) : base(id)
        {
        }
    }

    In this test case, SelectManyIterator is translated next way:

      function $lSelectManyIterator$gd__3$b2_MoveNext ($exception) {
        var $im00 = $asm01.System.Collections.Generic.IEnumerable$b1.Of($thisType.TSource.get(this)).GetEnumerator;
        var $im01 = $asm01.System.Collections.Generic.IEnumerator$b1.Of($thisType.TResult.get(this)).get_Current;
        var $im02 = $asm01.System.Collections.Generic.IEnumerator$b1.Of($thisType.TSource.get(this)).get_Current;
        var $im03 = $asm01.System.Collections.Generic.IEnumerable$b1.Of($thisType.TResult.get(this)).GetEnumerator;
        try {
    
          var $label0 = 0;
        $labelgroup0: 
          while (true) {
            switch ($label0) {
              case 0: /* $entry0 */ 
                var num = this.$state;
                if (num === 0) {
                  this.$state = -1;
                  this.$wrap6 = $im00.Call(this.source, null);
                  this.$state = 1;
                  $label0 = 2 /* goto IL_BE */ ;
                  continue $labelgroup0;
                }
                if (num !== 3) {
                  $label0 = 3 /* goto IL_D8 */ ;
                  continue $labelgroup0;
                }
                this.$state = 2;
    
                $label0 = 1 /* goto IL_A7 */ ;
                continue $labelgroup0;
              case 1: /* IL_A7 */ 
                if ($IM01().Call(this.$wrap8, null)) {
                  this.result = JSIL.CloneParameter($thisType.TResult.get(this), $im01.Call(this.$wrap8, null));
                  this.$current = JSIL.CloneParameter($thisType.TResult.get(this), this.result);
                  this.$state = 3;
                  var result = true;
                  return result;
                }
                this.$l$gm__Finally9();
    
                $label0 = 2 /* goto IL_BE */ ;
                continue $labelgroup0;
              case 2: /* IL_BE */ 
                if ($IM01().Call(this.$wrap6, null)) {
                  this.source1 = JSIL.CloneParameter($thisType.TSource.get(this), $im02.Call(this.$wrap6, null));
                  this.$wrap8 = $im03.Call(this.selector(JSIL.CloneParameter($thisType.TSource.get(this), this.source1)), null);
                  this.$state = 2;
                  $label0 = 1 /* goto IL_A7 */ ;
                  continue $labelgroup0;
                }
                this.$l$gm__Finally7();
    
                $label0 = 3 /* goto IL_D8 */ ;
                continue $labelgroup0;
              case 3: /* IL_D8 */ 
                result = false;
    
                break $labelgroup0;
            }
          }
        } catch ($exception) {
          this.System_IDisposable_Dispose();
          throw $exception;
        }
        return result;
      };

    Next, we should look at lines:

    var $im03 = $asm01.System.Collections.Generic.IEnumerable$b1.Of($thisType.TResult.get(this)).GetEnumerator;
    var $im01 = $asm01.System.Collections.Generic.IEnumerator$b1.Of($thisType.TResult.get(this)).get_Current;
    this.$wrap8 = $im03.Call(this.selector(JSIL.CloneParameter($thisType.TSource.get(this), this.source1)), null);
    this.result = JSIL.CloneParameter($thisType.TResult.get(this), $im01.Call(this.$wrap8, null));

    As this.selector returns array (without type information), next call of IEnumerable.GetEnumerator() will be processed as fallback and return IEnumerator. Next call for IEnumerator.get_Current will be failed after it.

    iskiselev commented 10 years ago

    I've simplified test case a little bit more for resolving second problem (I'm not sure if I should create a new bug for it. I can't even verbalize all conditions of problem)

    using System;
    using System.Collections.Generic;
    
    public static class Program {
        public static void Main (string[] args)
        {
            var item = TestInnerArrayCast(GetItems(), it => new[] { it });
            Console.WriteLine(item.GetType().FullName);
        }
    
        private static IEnumerable<BaseClass> GetItems()
        {
            return new List<DerivedClass>() { new DerivedClass() };
        }
    
        public static BaseClass TestInnerArrayCast(IEnumerable<BaseClass> source, Func<BaseClass, IEnumerable<BaseClass>> selector)
        {
            var outerEnumerator = source.GetEnumerator();
            outerEnumerator.MoveNext();
    
            var inner = selector(outerEnumerator.Current);
            var innerEnumerator = inner.GetEnumerator();
            innerEnumerator.MoveNext();
    
            return innerEnumerator.Current;
        }
    }
    
    public class BaseClass
    {
    }
    
    public class DerivedClass : BaseClass
    {
    }
    iskiselev commented 10 years ago

    Looks like fixing of #354 also fix my last suggested test case, but I'm still sure, that it only hides problem of untyped array passing. I can suggest next fix for GetEnumerator fallback here:

    1. In JSIL.InterfaceMethod.prototype.LookupMethod replace
      if (!result)
        result = this.fallbackMethod;

    with

      if (!result)
        result = this.fallbackMethod ? this.fallbackMethod(this.typeObject) : null;
    1. Change $GetEnumeratorFallback in such way:
    JSIL.$GetEnumeratorFallback = function (thisTypeObject) {
        var interfaceTypeObject = thisTypeObject;
        return function() {
            if (typeof(this) === "string")
                return JSIL.GetEnumerator(this, $jsilcore.System.Char.__Type__, true);
            else if (JSIL.IsArray(this)) {
                if (interfaceTypeObject.IsGenericType) {
                    // Looks like we find correct type ???
                    return JSIL.GetEnumerator(this, thisTypeObject.__GenericArgumentValues__[0], true);
                }
                // HACK: Too hard to detect the correct element type here.
                return JSIL.GetEnumerator(this, $jsilcore.System.Object.__Type__, true);
            } else
                JSIL.RuntimeError("Object of type '" + JSIL.GetType(this) + "' has no implementation of GetEnumerator");
        };
    };
    kg commented 10 years ago

    I really wish the JS type system wasn't garbage so we could just put type annotations on arrays. ;_;

    iskiselev commented 10 years ago

    As I understand, in Harmony we will :) I've also checked LINQ method implementation one more time (now with knowledge, that we sometimes can get simple array as input, without typed wrapper). So now I can state, that we should add type ref to JSIL.GetEnumerrator in next cases: 1) "Select" 2) "SelectMany" - 2 times 3) 3 "Sum" methods.

    I'll submit a pull request for it.

    kg commented 10 years ago

    Thank you very much for the fix contributions!

    And yeah, once the future is here we can type annotate arrays with WeakMap. Sadly Chrome still isn't shipping the damn thing (it's been years! UGH) so we can't do that. Putting a data property on an Array still deopts it into a dictionary in too many JS implementations, so that's out of the question... :(

    iskiselev commented 10 years ago

    Done. Thank you for this great tool! It saves our team great amount of time :)