14

The purpose of this is to synchronize two collections, sender-side & receiver-side, containing a graph edge, so that when something happens (remove edge, add edge, etc) both sides are notified.

To do so, (back-)references to the collections were included in the element in collections

class EdgeBase {
    EdgeBase(ICollection<EdgeBase> rCol, ICollection<EdgeBase> sCol)     
    { RecvCol=rCol;  SendCol=sCol; }      
    ICollection<EdgeBase> RecvCol;      
    ICollection<EdgeBase> SendCol;       
    public virtual void Disconnect() // Synchronized deletion         
    { RecvCol.Remove(this);  SendCol.Remove(this); }                 
}         
class Edge : EdgeBase {       
    Edge(ICollection<EdgeBase> rCol, ICollection<EdgeBase> sCol)     
    : base(rCol, sCol) {}
    int Weight;     
}

Deletion (Disconnect) was ok , but the problem occurred during creation:

HashSet<Edge> receiverSet, senderSet;
var edge = new Edge(receiverSet, senderSet); // Can't convert Edge to EdgeBase!

Although Edge is derived from EdgeBase, this is illegal. (The problem is Edge part, not HashSet<> part.)

After writing hundreds of lines I found out ICollection<> is not covariant as is IEnumerable<>.

What could be a workaround?

EDIT:

If I wrote the code above while not breaking the C#'s covariance rules it would have been like this:

public class EdgeBase<T, U>
    where T : ICollection<U<T>> // illegal
    where U : EdgeBase<T, U>    // legal, but introduces self-reference
{
    public EdgeBase(T recvCol, T sendCol) {...}
    protected T ReceiverCollection;
    protected T SenderCollection;
    public virtual void Disconnect() {...}
}

But this is illegal; 'U' can't be used with formal parameter T.

nawfal
  • 70,104
  • 56
  • 326
  • 368
Jeffrey Goines
  • 935
  • 1
  • 11
  • 30
  • 1
    receiverSet.Cast() – Daniel Möller Jun 08 '13 at 12:32
  • The cause: [question-about-c-sharp-covariance](http://stackoverflow.com/questions/4034495/question-about-c-sharp-covariance) which you acknowledge. The solution: [why-can-i-not-assign-a-list-of-concrete-types-to-a-list-of-that-concrete's-interface](http://stackoverflow.com/questions/1772606/why-can-i-not-assign-a-list-of-concrete-types-to-a-list-of-that-concretes-inter). The second part is quite frequently asked on SO. – nawfal Jun 10 '13 at 17:17
  • The answer posted on the link above suggests using generic method but can it be used for constructors? – Jeffrey Goines Jun 12 '13 at 13:52
  • @JeffreyGoines it is possible. I will make a *generic* answer *:)* – nawfal Jun 12 '13 at 17:57

2 Answers2

26

Eric Lippert said that C# will only support type-safe covariance and contravariance. If you would think of it, making ICollection covariant is not type-safe.

Let's say you have

ICollection<Dog> dogList = new List<Dog>();
ICollection<Mammal> mammalList = dogList; //illegal but for the sake of showing, do it
mammalList.Add(new Cat());

Your mammalList (which is actually a dogList) would now then contain a Cat.

IEnumerable<T> is covariant because you cannot Add to it... you can only read from it -- which, in turn, preserves type-safety.

Shimmy Weitzhandler
  • 101,809
  • 122
  • 424
  • 632
aiapatag
  • 3,355
  • 20
  • 24
  • 9
    And going the other way, an `ICollection` might contain a `Cat`, which means it cannot be safely converted to `ICollection`. So it cannot be safely made contravariant either. – Eric Lippert Jun 11 '13 at 06:35
  • It's worthwhile to note that while it would have been awkward for `IList` to implement `IList` in type-safe fashion (it would have the non-generic interface to provide read-only access, but having the two interfaces report conflicting values for `IsReadOnly` would have been confusing), there would have been no such problem with `ICollection`, and I consider it unfortunate that `ICollection` doesn't inherit `ICollection`, since it means there's no nice way for code which expects an `IEnumerable` but is given an `IList` to determine how many items are in it. – supercat Jun 11 '13 at 16:00
  • The only member of non-generic `ICollection` which would be even slightly dubious from a type-safety standpoint would have been `CopyTo`, and while the generic `ICollection.CopyTo` can offer better performance when using value types, it's no more type-safe than the non-generic version. A collection of `Cat` could be successfully copied to an `Object[]`, `Animal[]`, or `Cat[]`, even if only the non-generic `ICollection` would accept the first two. Both methods would allow an attempt to copy to a `SiameseCat[]`; such an attempt's success or failure could depend upon collection contents. – supercat Jun 11 '13 at 16:10
  • @supercat Really, there should be an `IEnumerableWithCount` or otherwise `ReadOnlyCollection` that didn't implement `Add`. – Alxandr May 21 '14 at 11:20
  • @Alxandr: IMHO, what would have been best would have been for `IEnumerable` to have a large number of methods, but include within the type loader a facility such that if a class declares itself as implementing an interface but doesn't declare all the members, the type loader would generate stubs that chain to methods of a static class affiliated with the interface. Almost any implementation of `Enumerable` could implement e.g. a `Snapshot` method which would return an `IEnumerable` that would, if not modified *by a recipient*, would always return the same sequence... – supercat May 22 '14 at 18:47
  • @Alxandr: ...and for those few that couldn't, it would be better to have an implementation throws an immediate exception than have code which wants a snapshot call `ToList()` on an infinite sequence. Many operations with things like `Linq` could be orders of magnitude more efficient if `IEnumerable` were more powerful. Note that the methods would need to be within `IEnumerable`, along with properties to say which ones should be considered "useful". Having separate interfaces is not sufficient, since there would be no way for e.g. a `Concat` method to take two sequences... – supercat May 22 '14 at 18:50
  • ...and return something which could e.g. sensibly perform a `Tail(10)` operation on a collection composed of a 1,000,000-item list and a five-item iterator (proper behavior should be to read through the iterator, then read the last five items form the list). – supercat May 22 '14 at 18:52
2

You're messing with type safety basically. Your backing collection is an ICollection<EdgeBase> (which means you can add any EdgeBase into it) but what you're passing a very specific type, HashSet<Edge>. How would you add (or remove) AnotherEdgeBaseDerived into HashSet<Edge>? If that is the case then this should be possible:

edge.Add(anotherEdgeBaseDerived); // which is weird, and rightly not compilable

If you perform a cast yourself and pass a separate list then that's compilable. Something like:

HashSet<Edge> receiverSet, senderSet;
var edge = new Edge(receiverSet.Cast<EdgeBase>().ToList(), 
                    senderSet.Cast<EdgeBase>().ToList());

which means your receiverSet and senderSet are now out of sync with base list in Edge. You can either have type safety or sync (same reference), you cant have both.

I worry if there exist no good solution to this, but for a good reason. Either pass HashSet<EdgeBase> to Edge constructor (better) or let EdgeBase collections be ICollection<Edge> (which seems very odd to do).

Or, the best you can have given the design constraints imo is generic 

class EdgeBase<T> where T : EdgeBase<T>
{

}

class Edge : EdgeBase<Edge>
{
    public Edge(ICollection<Edge> rCol, ICollection<Edge> sCol) : base(rCol, sCol)
    {

    }
}

Now you can call as usual:

HashSet<Edge> receiverSet = new HashSet<Edge>(), senderSet = new HashSet<Edge>();
var edge = new Edge(receiverSet, senderSet);

To me the fundamental problem is the fuzzy and smelly design. An EdgeBase instance holding a lot of similar instances, including more derived ones? Why not EdgeBase, Edge and EdgeCollection separately? But you know your design better.

nawfal
  • 70,104
  • 56
  • 326
  • 368