Tuesday, February 19, 2013

Memorizing method results with PostSharp (part 3)

This is the 3rd episode of a series of posts on how to cache statically method results.
In the first post we discussed what is postsharp, and how can it be used to create an attribute that will cache the results.
In the second post we removed hard references to the ibject instance, and to the arguments.
In this third post, we will focus on the missing limitations, namely generics and null parameters.
Lets jump right into it then.

Generic methods

Well, to make sure that generic methods do not mess up the picture, lets create a generic method inside our TestClass:
        public class TestClass
        {
            // previous code
            [...]

            public Dictionary<Type, int> NrOfGenericExecutions = new Dictionary<Type,int>();
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoubleTheNumber<T>(int i)
            {
                if (!NrOfGenericExecutions.ContainsKey(typeof(T)))
                {
                    NrOfGenericExecutions.Add(typeof(T), 0);
                }
                NrOfGenericExecutions[typeof(T)] = NrOfGenericExecutions[typeof(T)] + 1;
                return i * 2;
            }
        }
and then write a test for it:
        [TestMethod]
        public void TestGenericMethods()
        {
            var t = new TestClass();
            Assert.AreEqual(0, t.NrOfGenericExecutions.Count);
            t.DoubleTheNumber<int>(2);
            Assert.AreEqual(1, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(1, t.NrOfGenericExecutions[typeof(int)]);
            t.DoubleTheNumber<int>(3);
            Assert.AreEqual(1, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(int)]);
            t.DoubleTheNumber<int>(2);
            Assert.AreEqual(1, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(int)]);

            t.DoubleTheNumber<string>(2);
            Assert.AreEqual(2, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(int)]);
            Assert.AreEqual(1, t.NrOfGenericExecutions[typeof(string)]);
            t.DoubleTheNumber<string>(3);
            Assert.AreEqual(2, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(int)]);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(string)]);
            t.DoubleTheNumber<string>(2);
            Assert.AreEqual(2, t.NrOfGenericExecutions.Count);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(int)]);
            Assert.AreEqual(2, t.NrOfGenericExecutions[typeof(string)]);
        }
Now running this test will fail. Why is that? well, since we are having an instance attribute, i guess the attribute is the same for all methods of DoubleTheNumber<T>. So all we need to do here, is save the results in a dictionary, that has the method definition as its base. The changes are minimal. We change our methodCache private field to
        private IDictionary<MethodBase, object> methodCache = new Dictionary<MethodBase, object>();
of course we need to initialize this field for new instances, so the implementaion of IInstanceScopedAspect changes with the initialization of this field:
        void IInstanceScopedAspect.RuntimeInitializeInstance()
        {
            this.methodCache = new Dictionary<MethodBase, object>();
        }
Then we change our onEntry and onExit methods, to use the dictionary value according to the exact method definition, instead of just a simple object. But everything else stays the same
        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {

            if (!this.methodCache.ContainsKey(args.Method))
            {
                this.methodCache.Add(args.Method, null);
            }

            //remaining initialization
            [...]
            object resultDictionary = this.methodCache[args.Method];
            [...]

        }
And voila, our tests pass. Great. Generic arguments nailed.
Now what about null value arguments?

null values as arguments

So do we support null values? Lets see in a test. We are using here our TestClass2 from the 2nd post.
        [TestMethod]
        public void TestNullArguments()
        {
            var t = new TestClass2();
            var ta = new TestClass();
            Assert.AreEqual(0, t.NrOfExecutions);
            t.DoSomething(ta);
            Assert.AreEqual(1, t.NrOfExecutions);
            t.DoSomething(ta);
            Assert.AreEqual(1, t.NrOfExecutions);
            t.DoSomething(null);
            Assert.AreEqual(2, t.NrOfExecutions);
            t.DoSomething(null);
            Assert.AreEqual(2, t.NrOfExecutions);
            t.DoSomething(ta);
            Assert.AreEqual(2, t.NrOfExecutions);
            
        }
Well, this test fails miserably. The ConditionalWeakTable will throw an exception, if you try to add a null key. Actually if you think about it, it kinda misses the point. The structure is there, so if the key object is garbage collected, so the whole entry will disappear. Now since null cannot be garbage collected...
So it seems that we will need an additional way of storing values for nulls. But is that so difficult? We already differentiate arguments that can be null (IsValueType cannot be null), so lets just store the values for atguments like that in a bit extended structure. We create a wrapper around ConditionalWeakTable. I dont want to implement any special methods, and i will just expose the fields directly, but you could even try to implement IDictionary, or just pull some of the methods from the internal field to the object itself, its up to you. I just did:
    public class WeakNullableKeyValueCollection<TKey, TValue>
        where TKey: class
        where TValue : class
    {
        /// <summary>
        /// the table for the keys
        /// </summary>
        public ConditionalWeakTable<TKey, TValue> ConditionalWeakTable { get; private set; }

        private TValue _ValueForNull;
        /// <summary>
        /// the value for null
        /// </summary>
        public TValue ValueForNull { get { return _ValueForNull; } set { _ValueForNull = value; IsNullValueSet = true; } }

        /// <summary>
        /// whether the null value is set
        /// </summary>
        public bool IsNullValueSet { get; private set; }


        public WeakNullableKeyValueCollection()
        {
            ConditionalWeakTable = new ConditionalWeakTable<TKey, TValue>();
        }
    }
Using this class instead of simply a ConditionalWeakTable class should do the trick:
        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            //existing code
            [...]
                        if (!types[i].IsValueType)
                        {
                            if (arg == null)
                            {
                                if ((resultDictionary as WeakNullableKeyValueCollection<object, object>).IsNullValueSet)
                                {
                                    resultDictionary = (resultDictionary as WeakNullableKeyValueCollection<object, object>).ValueForNull;
                                }
                                else
                                {
                                    isMissingKey = true;
                                    break;
                                }
                            }
                            else
                            {
                                if ((resultDictionary as WeakNullableKeyValueCollection<object, object>).ConditionalWeakTable.TryGetValue(arg, out result))
                                {
                                    resultDictionary = result;
                                }
                                else
                                {
                                    isMissingKey = true;
                                    break;
                                }

                            }
                        }
            //existing code
            [...]
        }

        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            //existing code
            [...]
                    if (!types[i].IsValueType)
                    {
                        if (getter() == null)
                        {
                            setter(new WeakNullableKeyValueCollection<object, object>());
                        }
                        var currenttable = getter();

                        getter = () =>
                        {
                            if (arg == null)
                            {
                                return (currenttable as WeakNullableKeyValueCollection<object, object>).ValueForNull;
                            }
                            else
                            {
                                object temp;
                                (currenttable as WeakNullableKeyValueCollection<object, object>).ConditionalWeakTable.TryGetValue(arg, out temp);
                                return temp;
                            }
                        };
                        setter = o =>
                        {
                            if (arg == null)
                            {
                                (currenttable as WeakNullableKeyValueCollection<object, object>).ValueForNull = o;
                            }
                            else
                            {
                                (currenttable as WeakNullableKeyValueCollection<object, object>).ConditionalWeakTable.Add(arg, o);
                            }
                        };

                    }
            //existing code
            [...]
        }
Now run the unit tests, and we get them all passed. Cool null support added.

Generic classes

Now what about generic classes? Lets write a small testclass,
        public class TestClass<T>
        {
            public static int StaticNrOfExecutions = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public static int StaticDoubleTheNumber(int i)
            {
                StaticNrOfExecutions++;
                return i * 2;
            }

            public int CallStaticDoubleTheNumber(int i)
            {
                return StaticDoubleTheNumber(i);
            }


            public int NrOfExecutions = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoubleTheNumber(int i)
            {
                NrOfExecutions++;
                return i * 2;
            }
        }
and a test for it:
        [TestMethod]
        public void TestGenericClasses()
        {
            var ti = new TestClass<int>();
            var ts = new TestClass<string>();
            Assert.AreEqual(0, ti.NrOfExecutions);
            Assert.AreEqual(0, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(0, TestClass<string>.StaticNrOfExecutions);

            ti.DoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(0, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(0, TestClass<string>.StaticNrOfExecutions);

            ti.CallStaticDoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(1, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(0, TestClass<string>.StaticNrOfExecutions);

            TestClass<int>.StaticDoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(1, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(0, TestClass<string>.StaticNrOfExecutions);

            TestClass<string>.StaticDoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(1, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(1, TestClass<string>.StaticNrOfExecutions);

            ts.CallStaticDoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(1, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(0, ts.NrOfExecutions);
            Assert.AreEqual(1, TestClass<string>.StaticNrOfExecutions);

            ts.DoubleTheNumber(1);
            Assert.AreEqual(1, ti.NrOfExecutions);
            Assert.AreEqual(1, TestClass<int>.StaticNrOfExecutions);
            Assert.AreEqual(1, ts.NrOfExecutions);
            Assert.AreEqual(1, TestClass<string>.StaticNrOfExecutions);
        }
Well running the test passes, so it seems that somewhere along the way we already implemented this feature.
Actually the reason why we dont get collisions, is that the MethodBase, that we use as a key for method return value caching, is different between 2 generic classes with different Generic parameter. So we dont run into any collision.

Well, this concludes the functionality we set off for. The source code can be downloaded here
Please dont forget about the limitations mentioned in the second post, that were not addressed in this one.
If you have any comments or notes, please feel free to add them.
Have a nice day!

Monday, February 18, 2013

Memorizing method results with PostSharp (part 2)

This post is the continuation of the previous post Memorizing method results with PostSharp (part 1).
In the previous post we created an attribute, that allowed caching method results. The caching was implemented with a static dictionary object, that stored a reference to the objects and the method atguments as well. That solution is harly a good one for a production environment, as it might lead to memory leaks, the dictionary just growing and having more n more elements, withou allowing the GC to collect the objects that we dont use.

Reference to the object instance

Help from PostSharp

Now PostSharp has a solution for the first problem of our, having a reference to the object itself.
In the PostSharp documentation you can read about the lifecycle and scope of the postsharp aspects. The instance-scoped aspects seem to be exactly what we need. It creates one instance ofthe attribute for an instance of the class it is used on. In addition it automatically has an instance for static methods.
The documentation states that we only need to implement the IInstanceScopedAspect interface, and the magic will happen.
This interface has 2 methods:
object IInstanceScopedAspect.CreateInstance(AdviceArgs adviceArgs)
void IInstanceScopedAspect.RuntimeInitializeInstance()
The first one is called on to create the aspect when a new instance of the class is created. The second one is called on the newly created aspect.
We will simply copy over all the data from our aspect, and that should do. Since we are creating an instance aspect, we should be able to remove the first 2 keys from the dictionary, and just use the arguments as keys, and the return value as value.

Unit tests

Lets start first extending our test class with a static and a second instance method, and then write some tests for static, and 2 different instance methods.
        public class TestClass
        {
            public static int StaticNrOfExecutions = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public static int StaticDoubleTheNumber(int i)
            {
                StaticNrOfExecutions++;
                return i * 2;
            }

            public int CallStaticDoubleTheNumber(int i)
            {
                return StaticDoubleTheNumber(i);
            }
            
            public int NrOfExecutions = 0;
            public int NrOfExecutions2 = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoubleTheNumber(int i)
            {
                NrOfExecutions++;
                return i * 2;
            }
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoubleTheNumber2(int i)
            {
                NrOfExecutions2++;
                return i * 2;
            }
        }
So now having this class, lets write a test for static methods:
        [TestMethod]
        public void TestStaticResultCached()
        {
            var sa = new TestClass();
            var sb = new TestClass();
            Assert.AreEqual(0, TestClass.StaticNrOfExecutions);
            TestClass.StaticDoubleTheNumber(1);
            Assert.AreEqual(1, TestClass.StaticNrOfExecutions);
            TestClass.StaticDoubleTheNumber(2);
            Assert.AreEqual(2, TestClass.StaticNrOfExecutions);
            TestClass.StaticDoubleTheNumber(1);
            Assert.AreEqual(2, TestClass.StaticNrOfExecutions);
            sa.CallStaticDoubleTheNumber(4);
            Assert.AreEqual(3, TestClass.StaticNrOfExecutions);
            sa.CallStaticDoubleTheNumber(2);
            Assert.AreEqual(3, TestClass.StaticNrOfExecutions);
            sb.CallStaticDoubleTheNumber(4);
            Assert.AreEqual(3, TestClass.StaticNrOfExecutions);
        }
One for the 2 instance methods
[TestMethod]
        public void MethodsCachedSeparately()
        {
            var sa = new TestClass();
            Assert.AreEqual(0, sa.NrOfExecutions);
            Assert.AreEqual(0, sa.NrOfExecutions2);
            sa.DoubleTheNumber(1);
            Assert.AreEqual(1, sa.NrOfExecutions);
            Assert.AreEqual(0, sa.NrOfExecutions2);
            sa.DoubleTheNumber(2);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(0, sa.NrOfExecutions2);
            sa.DoubleTheNumber(1);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(0, sa.NrOfExecutions2);
            sa.DoubleTheNumber2(1);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(1, sa.NrOfExecutions2);
            sa.DoubleTheNumber2(2);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(2, sa.NrOfExecutions2);
            sa.DoubleTheNumber2(1);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(2, sa.NrOfExecutions2);

        }
and then a test for the same method on 2 objects.
[TestMethod]
        public void TestDifferentObjectsCached()
        {
            var sa = new TestClass();
            var sb = new TestClass();
            Assert.AreEqual(0, sa.NrOfExecutions);
            Assert.AreEqual(0, sb.NrOfExecutions);
            sa.DoubleTheNumber(1);
            Assert.AreEqual(1, sa.NrOfExecutions);
            Assert.AreEqual(0, sb.NrOfExecutions);
            sa.DoubleTheNumber(2);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(0, sb.NrOfExecutions);
            sa.DoubleTheNumber(1);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(0, sb.NrOfExecutions);
            sb.DoubleTheNumber(1);
            Assert.AreEqual(2, sa.NrOfExecutions);
            Assert.AreEqual(1, sb.NrOfExecutions);
        }
We trust PostSharp, that the instance attribute will go away with the object itself, so we dont do a test for that

The implementation

With the implementation we dont have a lot to change. We implement the required interface, and change our dictionary to only hold reference to the arguments.
    public class CacheResultAttribute : PostSharp.Aspects.OnMethodBoundaryAspect, IInstanceScopedAspect
    {
        private IDictionary methodCache = new Dictionary();

        // previous code
        [...]

        #region IInstanceScopedAspect implementation
        object IInstanceScopedAspect.CreateInstance(AdviceArgs adviceArgs)
        {
            var result = this.MemberwiseClone() as CacheResultAttribute;
            result.methodCache = new Dictionary();
            return result;
        }

        void IInstanceScopedAspect.RuntimeInitializeInstance()
        {
        }
        #endregion IInstanceScopedAspect implementation
    }
As you can see, we totally removed the necessity of storing anything static. Since the aspect lives as long as the object, and for static methods statically, no more implementation is required.
Also with this our methods get shorter as well, since we need less dictionary key lookups.
        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");
            var item = args.Instance ?? args.Method.ReflectedType;
            object argsKey = args.Arguments.Count == 0 ? string.Empty : tupleCreator(args.Method.GetParameters().Select(x => x.ParameterType).ToArray(), args.Arguments.ToArray());
            if (methodCache.ContainsKey(argsKey))
            {
                args.ReturnValue = methodCache[argsKey];
                args.FlowBehavior = PostSharp.Aspects.FlowBehavior.Return;
            }

            base.OnEntry(args);
        }

        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");
            var item = args.Instance ?? args.Method.ReflectedType;
            object argsKey = args.Arguments.Count == 0 ? string.Empty : tupleCreator(args.Method.GetParameters().Select(x => x.ParameterType).ToArray(), args.Arguments.ToArray());
            methodCache.Add(argsKey, args.ReturnValue);

            base.OnExit(args);
        }
Great, now running our unit tests, we get them all passed. Amazing! First problem resolved, thank you PostSharp.

Reference to arguments

Now the other problem we are having, is hard references to arguments. Lets create a new TestClass2, with a method that takes TestClass as an argument.
        public class TestClass2
        {
            public int NrOfExecutions = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoSomething(TestClass tc)
            {
                NrOfExecutions++;
                return 4;
            }
        }
Now we want to make sure, that the caching does not hold a reference to our argument object. Lets write a test:
        [TestMethod]
        public void TestReferenceToArgumentsNotRemembered()
        {
            var ta = new TestClass();
            var t2 = new TestClass2();
            Assert.AreEqual(0, t2.NrOfExecutions);
            t2.DoSomething(ta);
            Assert.AreEqual(1, t2.NrOfExecutions);
            t2.DoSomething(ta);
            Assert.AreEqual(1, t2.NrOfExecutions);
            var wr = new WeakReference(ta);
            ta = null;
            GC.Collect();
            Assert.AreEqual(null, wr.Target);
        }
Here we simply create the instance ta, then use it to call the method. Then create a WeakReference to it. WeakReference is a builtin framework class, that allows an optional reference to an object, as long as the object has a reference somewhere else. But WeakReference does not block the garbage collection on that object.
We remove our reference to ta, and we force a garbage collection, which should normally result in the ta to be garbage collected. If you run this test, you will see it fail, as the Dictionary inside our attribute has a strong reference to ta, and prevent the GC from collecting it.

The help again comes from outside. The framework provides a class with similar functionality as WeakReference, just in a table like form. It is called ConditionalWeakTable.
Lets try to use this class instead of the dictionary we had.
Well, in reality, we were using Tuple<> to wrap the arguments, and it is actually the tuple that has the reference to the object, and the dictionary has a reference to the tuple. We will rewrite our dictionary to use the keys directly, and use the ConditionalWeakTable class. We will need to handle the argumentless case separately, but otherwise we will store a ConditionalWeakTable for each argument, so an arg list of (string, int, Type) will be ConditionalWeakTable<object, ConditionalWeakTable<object, ConditionalWeakTable<object, object>>>. As you can see we store everything as objects. This might cause a problem, but lets see.
        /// <summary>
        /// the result in case there are no arguments
        /// </summary>
        private object noArgResult;
        /// <summary>
        /// whether the no argument result has been calculated
        /// this is required, as the result can be null
        /// </summary>
        private bool isNoArgResultInitialized = false;

        [NonSerialized]
        private ConditionalWeakTable<object, object> methodCache = new ConditionalWeakTable<object, object>();

        //previous code
        [...]

        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");

            if (args.Arguments.Count == 0)
            {
                if (isNoArgResultInitialized)
                {
                    args.ReturnValue = noArgResult;
                    args.FlowBehavior = FlowBehavior.Return;
                }
            }
            else
            {
                var types = args.Method.GetParameters().Select(x => x.ParameterType).ToList();
                bool isMissingKey = false;
                var resultDictionary = this.methodCache;
                for (int i = 0; i < args.Arguments.Count - 1; i++)
                {
                    var arg = args.Arguments[i];
                    object result;
                    if (resultDictionary.TryGetValue(arg, out result))
                    {
                        resultDictionary = result as ConditionalWeakTable<object, object>;
                    }
                    else
                    {
                        isMissingKey = true;
                        break;
                    }
                }
                object finalresult;
                if (!isMissingKey && resultDictionary.TryGetValue(args.Arguments.Last(), out finalresult))
                {
                    args.ReturnValue = finalresult;
                    args.FlowBehavior = FlowBehavior.Return;
                }

            }

            base.OnEntry(args);
        }

        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");

            if (args.Arguments.Count == 0)
            {
                isNoArgResultInitialized = true;
                noArgResult = args.ReturnValue;
            }
            else
            {
                var table = methodCache;
                for (int i = 0; i < args.Arguments.Count - 1; i++)
                {
                    var arg = args.Arguments[i];
                    object nextTable;
                    if (table.TryGetValue(arg, out nextTable))
                    {
                        table = nextTable as ConditionalWeakTable<object, object>;
                    }
                    else
                    {
                        var nextTable2 = new ConditionalWeakTable<object, object>();
                        table.Add(arg, nextTable2);
                        table = nextTable2;
                    }
                }
                table.Add(args.Arguments.Last(), args.ReturnValue);
            }

            base.OnExit(args);
        }
Well, looks a bit more complicated, but it is not that much. We simply go through the arguments, and if another argument found, we add a new ConditionalWeaktable.

Cool, lets run our unit tests, and .... BANG. The last one passes, but the previoud ones all fail. Whaaaaat? What just happened?
To understand what happened, we need to have a look at the ConditionalWeakTable documentation, and see the note at the middle of the page: "ConditionalWeakTable class supports one attached value per managed object. Two keys are equal if passing them to the Object.ReferenceEquals method returns true". Hmm, ok but we didnt really passed in objects in our failed tests. We passed in and integer of 3, why did it fail?
Well the answer is boxing. C# allows boxing of any value into an obejct. This allows you to add an integer to an object list, like
var list = new List<object>();
int i = 8;
list.Add(i);
Here the compiler is actually boxing the value 8 to an object, and add it to the list.
Combining this with the fact, that the ConditionalWeakTable checks for object.ReferenceEquals, we now understand what happened. We have 2 different object, which both are the same integer, but do not say true to object.ReferenceEquals.
A quick test confirms it.

        [TestMethod]
        public void Test()
        {
            int i = 6;
            object a = i;
            object b = i;
            Assert.IsFalse(Object.ReferenceEquals(a, b));
        }
So now what? What we really want to, is not to have memory used up when it will not be required anymore. How do we know it is not required anymore? Well for an object it is easy, if no references exist to it, we dont need it. But with a number? or a string? Is it even our responsability to care about this?
Well, i would argue about this. The functionality we are trying to achieve, is to cache method results. Now if you cache a result for the number 3, do you want to hold on to that result forever? Well, with our intention, of having the cache static, it is probably what you want. So for simple types, it is probably not an issue to have them stored in the dictionary directly. The problem might arise, when you start to use quite complex tructs as arguments, as those will not be garbage collected ever. This is actually a limitation, that we will just accept, as for the time being, it is good enough.
So for the not reference types, we will just use a dictionary, and we will use the ConditionalWeakReference for the rest.
Implementing this gives us the code:

        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");

            if (!this.methodCache.ContainsKey(args.Method))
            {
                this.methodCache.Add(args.Method, null);
            }

            if (args.Arguments.Count == 0)
            {
                if (isNoArgResultInitialized)
                {
                    args.ReturnValue = methodCache[args.Method];
                    args.FlowBehavior = FlowBehavior.Return;
                }
            }
            else
            {
                var types = args.Method.GetParameters().Select(x => x.ParameterType).ToList();
                bool isMissingKey = false;
                object resultDictionary = this.methodCache;
                if (resultDictionary != null)
                {
                    for (int i = 0; i < args.Arguments.Count; i++)
                    {
                        object result;
                        var arg = args.Arguments[i];
                        if (!types[i].IsValueType)
                        {
                            if ((resultDictionary as ConditionalWeakTable<object, object>).TryGetValue(arg, out result))
                            {
                                resultDictionary = result;
                            }
                            else
                            {
                                isMissingKey = true;
                                break;
                            }
                        }
                        else
                        {
                            if ((resultDictionary as IDictionary).Contains(arg))
                            {
                                resultDictionary = (resultDictionary as IDictionary)[arg];
                            }
                            else
                            {
                                isMissingKey = true;
                                break;
                            }
                        }

                    }
                    if (!isMissingKey)
                    {
                        args.ReturnValue = resultDictionary;
                        args.FlowBehavior = FlowBehavior.Return;
                    }
                }
            }

            base.OnEntry(args);
        }

        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");

            if (args.Arguments.Count == 0)
            {
                isNoArgResultInitialized = true;
                methodCache[args.Method] = args.ReturnValue;
            }
            else
            {
                var types = args.Method.GetParameters().Select(x => x.ParameterType).ToList();
                Func<object> getter = () => methodCache;
                Action<object> setter = o => methodCache = o;
                object table = getter();
                for (int i = 0; i < args.Arguments.Count; i++)
                {
                    var arg = args.Arguments[i];
                    if (!types[i].IsValueType)
                    {
                        if (getter() == null)
                        {
                            setter(new ConditionalWeakTable<object, object>());
                        }
                        var currenttable = getter();

                        getter = () =>
                        {
                            object temp;
                            (currenttable as ConditionalWeakTable<object, object>).TryGetValue(arg, out temp);
                            return temp;
                        };
                        setter = o =>
                        {
                            (currenttable as ConditionalWeakTable<object, object>).Add(arg, o);
                        };
                    }
                    else
                    {
                        if (getter() == null)
                        {
                            setter(new Hashtable());
                        }
                        var currenttable = getter();
                        getter = () => (currenttable as Hashtable)[arg];
                        setter = o =>
                        {
                            (currenttable as Hashtable).Add(arg, o);
                        };
                    }

                }
                setter(args.ReturnValue);
            }

            base.OnExit(args);
        }


Now when running our unit tests, we have all of them passed. So we managed what we set out for.

Limitations

Well, as we saw above, we might have some memory leak when using large value type objects, like complex structs as parameters. This is a VERY IMPORTANT limitaion, and you do have to be aware of this, when you use this attribute extensively.

Generics

Well what bout generic methods and generic types? Well, the above implementation does not really support them, so you have to keep that in mind. But the implementaion can be extended to support those concepts too.

Null values

Im not sure, but i think ConditionalWeakTable does not support null values, so an extra implementation is required to handle those too.

Another limitaiton i can think of comes up, when you have a reference type parameter after a value type parameter in the arguments list order. For example having [CacheResult] int Method(int number, TestClass testClass) Now when we first call this with 0 and ta (where ta is a TestClass instance), then the the result is cached in a HashTable, for 0 it has a value of a ConditionalWeakTable<object, object>, that has a weak reference to ta.
Now when ta goes out of scope, the ConditionalWeakTable will loose the reference to it, but the HashTable will still have in it an empty ConditionalWeakTable object. This is obviously some memory loss, even though it is less then having a reference to the class itself, if you use this attribute extensively, you should consider addressing that issue as well.

If you are curious how to remove some of these limitations, please follow onto the next post.

Sunday, February 17, 2013

Memorizing method results with PostSharp (part 1)

Now regularly when I require a new functionality of some sort, and I try to think of the problem in general, outside of the current problem context, I run into the need of caching the result of a specific method, in order to speed up the code if someone (even me) would decide to use it extensively.

The problem

I mean, how may times did you see a code like this in your life:
    public class SomeClass
    {
        private static Dictionary<Tuple<Argument1Type, Argument2Type>, MyResultType> someExpensiveMethodsomeMethodResultCache = new Dictionary<Tuple<Argument1Type, Argument2Type>, MyResultType>();

        public MyResultType SomeExpensiveMethod(Argument1Type arg1, Argument2Type arg2)
        {
            var key = Tuple.Create(arg1, arg2);
            if (!someExpensiveMethodsomeMethodResultCache.ContainsKey(key))
            {
                MyResultType result = null;
                // fill result;
                [...]
                someExpensiveMethodsomeMethodResultCache.Add(key, result);
            }
            return someExpensiveMethodsomeMethodResultCache[key];
        }

    }

Now, obviously you could cache the result not statically, but in an object cache, or any other way, but the bottom line is, it seems to be quite a lot of code and responsability for a functionality, that i would much prefer just to 'attach' to the method, right?

The goal

As we all know, there is a mechanism in the .Net framework, to 'attach' functionality to the code elements, and they are called attributes.
Now what i'd really like to do, is say simply:
    public class SomeClass
    {
        [CacheResult(CacheLocations.Static)]
        public MyResultType SomeExpensiveMethod(Argument1Type arg1, Argument2Type arg2)
        {
            MyResultType result = null;
            // fill result;
            [...]
            return result;
        }
    }
Well, i do think so, so lets try to create an attribute like that.

The solution

Now one major thing to understand here is, that we want to interfere with the normal execution of the program, and hijack it. Basically, if we already have the cached verion, we just return that, and do not execute the code again.
Here is where a new concept comes in called aspects.
If you are not familiar with the term aspects, you should read more about it on Wikipedia here, or here, or just google for it!! It is a truly exceptional field, and can do really amazing things, for example what we are doing here :)
Now a very nice and tool for such things is PostSharp, which has a free license for 1 developer. It is a limited edition, but it gets you enough to accomplish what we want here.

A few words on PostSharp

Well, it is useful to understand how PostSharp works, and what can it do for you. PostSharp is basically a library, that gets into the build pipeline. Once your code is compiled to IL, PostSharp will go through the compiled code, and look for attributes, that derive from their attributes. It will then change the method implementations according to what the attributes should do.
It can intercept method calls and property calls, and a lot more. You can read about the capabilities on the SharpCrafter's website

Ok, so now that we have a general idea of the tools we can use, lets jump into the unit tests.

Unit Tests

Generally when creating a unit test for a functionality, you also need to come up with the interfaces and classes that you will use to interact with the functionality.
So first we will need an attribute, lets say CacheResultAttribute.
    [AttributeUsage(AttributeTargets.Method, AllowMultiple=false)]
    public class CacheResultAttribute : Attribute
    {
    }
Now for the sake of future requirements, when you will not want to cahce the results statically, but in another way, lets allow the specification of the cache location, with an enum called CacheLocations.
    public enum CacheLocations
    {
        Static,
    }
and also add this as a contructor parameter for the attribute:
        private readonly CacheLocations cacheLocation;
        public CacheResultAttribute(CacheLocations location)
        {
            cacheLocation = location;
        }
Now we can create a test class that will count the method execution, and return the amount of time executed.
    [TestClass]
    public class CacheResultAttributeTest
    {
        public class TestClass
        {
            public int NrOfExecutions = 0;
            [CacheResultAttribute.CacheResult(CacheLocations.Static)]
            public int DoubleTheNumber(int i)
            {
                NrOfExecutions++;
                return i * 2;
            }
        }
    }
As you can see, I already decorated the DoubleTheNumber method with the attribute i just created above. I know public fields are not a good idea, but for the sake of keeping the test code short, its not a big deal.
Now in our tests we simply want to see if the DoubleTheNumber method is not called for parameters that were already passed in. The test method if fairly simple,
        [TestMethod]
        public void TestResultCached()
        {
            var subject = new TestClass();
            Assert.AreEqual(0, subject.NrOfExecutions);
            var result = subject.DoubleTheNumber(3);
            // we dont care if the method is actually ok, so this is not needed
            //Assert.AreEqual(6, result);

            //but we want to check if the execution count went up
            Assert.AreEqual(1, subject.NrOfExecutions);

            // now lets see if it is called with other parameter
            result = subject.DoubleTheNumber(2);
            //again check that execution nr went up
            Assert.AreEqual(2, subject.NrOfExecutions);

            //now get the result for 3 again
            result = subject.DoubleTheNumber(3);
            // and make sure we didnt execute the method
            Assert.AreEqual(2, subject.NrOfExecutions);
        }
it doesnt even need explanation.

Great, now we have a test, lets run it, and we have the first test result : "Result Message: Assert.AreEqual failed. Expected:<2>. Actual:<3>."
Of course since we didnt implement anything yet, the 3rd call just calls the function, and it is executed the 3rd time as well. So lets have a look at how this will be done.

The implementation

The first thing you have to do is get and install PostSharp. Please follow the steps on the website if you dont have it yet.
Oncc you have postsharp, and reference to the dlls, we can start extending an attribute called OnMethodBoundaryAspect which is in the postsharp dlls. This aspect allows you to intercept metod calls. You have 3 methods you can override:
bool CompileTimeValidate(MethodBase method)
void OnEntry(MethodExecutionArgs args)
void OnExit(MethodExecutionArgs args)
The first one is executed, when PostSharp recompiles the code. This means that the code here is only executed at build time, it does not have an influence at runtime, so this can be as heavy as you want. Obviously you will have a longer compile time, but it will not be visible to the code users.
The second and third methods are called when entering and exiting a method.
The MethodExecutionArgs class contains all necessary data, that you will require at runtime to decide what to do. So lets jump in.
    [Serializable]  // required by PostSharp
    [AttributeUsage(AttributeTargets.Method, AllowMultiple=false)]
    public class CacheResultAttribute : PostSharp.Aspects.OnMethodBoundaryAspect
    {
        private readonly CacheLocations cacheLocation;
        public CacheResultAttribute(CacheLocations location)
        {
            cacheLocation = location;
        }

        public override bool CompileTimeValidate(System.Reflection.MethodBase method)
        {
            return base.CompileTimeValidate(method);
        }

        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            base.OnEntry(args);
        }

        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            base.OnExit(args);
        }

    }
Now lets start with the first. We really dont need to do anything here, but just for the same of understanding, lets not allow applying this attribute to void methods and constructors. That would be misleading anyways. So lets check if we are a void method, and if so, throw the error.
        public override bool CompileTimeValidate(System.Reflection.MethodBase method)
        {
            if (method == null)
            {
                PostSharp.Extensibility.Message error = new PostSharp.Extensibility.Message(MessageLocation.Explicit("CacheResultAttribute", 25, 0), SeverityType.Error, "AOP0001", "Method is null", "#", "CacheResultAttribute.cs", null);
                MessageSource.MessageSink.Write(error);
                return false;
            }
            if(method.IsConstructor)
            {
                PostSharp.Extensibility.Message error = new PostSharp.Extensibility.Message(MessageLocation.Explicit("CacheResultAttribute", 25, 0), SeverityType.Error, "AOP0001", "Attribute cannot be applied to constructors", "#", "CacheResultAttribute.cs", null);
                MessageSource.MessageSink.Write(error);
                return false;
            }
            if (!(method is MethodInfo))
            {
                PostSharp.Extensibility.Message error = new PostSharp.Extensibility.Message(MessageLocation.Explicit("CacheResultAttribute", 25, 0), SeverityType.Error, "AOP0001", string.Format("Attribute cannot be applied to method {0} because it cannot be cast to a MethodInfo", method.Name), "#", "CacheResultAttribute.cs", null);
                MessageSource.MessageSink.Write(error);
                return false;
            }
            if((method as MethodInfo).ReturnType == typeof(void))
            {
                PostSharp.Extensibility.Message error = new PostSharp.Extensibility.Message(MessageLocation.Explicit("CacheResultAttribute", 25, 0), SeverityType.Error, "AOP0001", string.Format("Attribute cannot be applied to method {0} because it has a void return type", method.Name), "#", "CacheResultAttribute.cs", null);
                MessageSource.MessageSink.Write(error);
                return false;
            }
            return base.CompileTimeValidate(method);
        }

Really not much interesting here. So lets get to the next one, what do we want to do in the OnEntry and OnExit methods?
Well, postsharp allows you to hijack method execution, and do not actually run the method by setting the args.FlowBehavior = FlowBehavior.Return. This will be very handy, since we will do just that, when we find a cached value.
So we have all the arguments in the args.Arguments property, we have the methodInfo in the args.Method property, and the instance (if not static method) in the args.Instance property.
Now one convention we will use, is, that if we encounter a static method, then we will store it to the type on which it is defined. Otherwise we will store the results for the cached object. Since System.Type does not use our attribute (we are just creating it), we should have no problems about duplicate dictionary keys. So we will index our static cache by the following keys:
1) Object instance or type
2) MethodBase
3) arguments
With these assumptions we have the follwoing code:
        private static readonly IDictionary<object, IDictionary<MethodBase, IDictionary<object, object>>> staticMethodCache = new Dictionary<object, IDictionary<MethodBase, IDictionary<object, object>>>();

        public override void OnEntry(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");
            var item = args.Instance ?? args.Method.ReflectedType;
            if (staticMethodCache.ContainsKey(item)
                && staticMethodCache[item] != null
                && staticMethodCache[item].ContainsKey(args.Method)
                && staticMethodCache[item][args.Method] != null)
            {
                object argsKey = args.Arguments.Count == 0 ? string.Empty : tupleCreator(args.Method.GetParameters().Select(x => x.ParameterType).ToArray(), args.Arguments.ToArray());
                if (staticMethodCache[item][args.Method].ContainsKey(argsKey))
                {
                    args.ReturnValue = staticMethodCache[item][args.Method][argsKey];
                    args.FlowBehavior = PostSharp.Aspects.FlowBehavior.Return;
                }
            }
            base.OnEntry(args);
        }
We simply checked if we have the value in the dictionary, and if yes, then we set the return value, and break the flow.
We used here a helper method tupleCreator. This essentially creates a tuple from the arguments. The tuple is of type (for example for arguments (int, string, Type) it is Tuple<Type, Tuple<string, Tuple<int>>>).
        /// 
        /// creates a tuple of the arguments
        /// 
        /// 
        /// 
        /// 
        private object tupleCreator(Type[] types, object[] arguments)
        {
            if (types == null)
                throw new ArgumentNullException("types");
            if (arguments == null)
                throw new ArgumentNullException("arguments");
            if (types.Length == 0)
                throw new ArgumentOutOfRangeException("types", "The specified type list needs at least 1 type");
            if (types.Length != arguments.Length)
                throw new ArgumentException("The specified argument count does not equal the type count", "arguments");
            var tupleCreator1 = typeof(Tuple).GetMethods(BindingFlags.Static | BindingFlags.Public).Where(x => x.Name == "Create" && x.GetGenericArguments().Length == 1).Single();
            var tupleCreator2 = typeof(Tuple).GetMethods(BindingFlags.Static | BindingFlags.Public).Where(x => x.Name == "Create" && x.GetGenericArguments().Length == 2).Single();

            var result = tupleCreator1.MakeGenericMethod(types[types.Length -1]).Invoke(null, new object[]{arguments[types.Length -1]});
            for (int i = types.Length -2; i > -1; i++)
            {
                result = tupleCreator2.MakeGenericMethod(types[i], result.GetType()).Invoke(null, new object[] { arguments[i], result });
            }
            return result;
        }

The method is quite straightforward, it can be improved by statically caching the two method infos for getting the Tuple factory methods. It can be also decreased with the number of calls to Invoke, since there are Tuple methods with more arguments, but for now this will do.
Now for the exit, we basically need to store the result in the dictionary, and we are done.
        public override void OnExit(PostSharp.Aspects.MethodExecutionArgs args)
        {
            if (this.cacheLocation != CacheLocations.Static)
                throw new NotImplementedException("Only static cache location is implemented for method return cache");
            var item = args.Instance ?? args.Method.ReflectedType;
            if (!staticMethodCache.ContainsKey(item))
            {
                staticMethodCache.Add(item, new Dictionary<MethodBase, IDictionary<object, object>>());
            }
            if (!staticMethodCache[item].ContainsKey(args.Method))
            {
                staticMethodCache[item].Add(args.Method, new Dictionary<object, object>());
            }
            object argsKey = args.Arguments.Count == 0 ? string.Empty : tupleCreator(args.Method.GetParameters().Select(x => x.ParameterType).ToArray(), args.Arguments.ToArray());
            staticMethodCache[item][args.Method].Add(argsKey, args.ReturnValue);
            base.OnExit(args);
        }
We create the dictionaries, and we insert the value. This would by the way throw an exception, if we managed somehow to get here again, with the same parameters.

Well, now lets run our unit tests, and wohooo. It passes. So with just a couple of line of code, we managed to move the caching code from the actual place to an aspect, that now we can apply anywhere.

Room for improvement

As you can see, there is only 1 caching method implementaion, the one for static caching. I use this type of caching a lot, when i create type maps, and other methods, that operate mostly on types. You could implement other caching mechanisms, and extend the above.

Problems

DO NOT USE THIS CODE IN PRODUCTION!!!
Why do I say that?

Well, lets take a look at our dictionaries. The first key is the object itself. That means, that any time this aspect is hit, there will be a reference to that object created in your dictionary, which will prevent garbage collection for that object. This is a massive issue, if you want to use this attribute on instances. As long as you use it on static methods, there is no major memory loss, but with instance methods this will result in you using up more n more memory. We will discuss this issue in an upcoming post.

The same problem then with object instances, comes up with the arguments. The dictionaries will have references to those arguments as well, which will do the same harm as above. As above, this will be addressed in the next post.
Cheers for reading.

Continue reading on the second part of this post

Thursday, February 14, 2013

Synchronizing two ObservableCollections

I have had the problem of observable collection synchronization for quite a while, and always got around it somehow, but never really had the time to create a fully functional and satisafactory solution. Now the time has come :)

So lets suppose, we have a WorkspaceViewModel, that contains a PageManager which is responsible for handling the pages and setting the active one. The pagemanager has a Pages property that is an ObservableCollection, but we need on the WorkspaceViewModel a Pages property that has the same property with a different type, lets say IPageViewModel.
The classes can be seen below.

The framework classes, that we can use, but dont want to modify:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BITStuff.Wpf.Interfaces
{
    public interface IPage
    {
    }
}

namespace BITStuff.Wpf.BaseClasses
{
    public class PageManager
    {

        #region properties
        /// 
        /// the collection of pages
        /// 
        protected System.Collections.ObjectModel.ObservableCollection<IPage> _Pages = new System.Collections.ObjectModel.ObservableCollection<IPage>();
        #endregion properties

        public System.Collections.ObjectModel.ObservableCollection<IPage> Pages
        {
            get { return _Pages; }
        }
    }
}
The application classes, where we have slightly different requirements:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UserInterface.Interfaces.ViewModels
{
    public interface IPageViewModel : BITStuff.Wpf.Interfaces.IPage
    {
        string Title { get; }
    }
}

namespace UserInterface.BaseClasses
{
    public abstract class WorkspaceViewModel
    {
        public ObservableCollection<IPageViewModel> Pages { get; }

        protected PageManager PageManager { get; set; }

    }
}
And now i want to expose the PageManager's Pages collection as the WorkspaveViewModel's Page collection.
A WRONG approach is to create a new ObservableCollection in the getter:
        public ObservableCollection<IPageViewModel> Pages { get { return new ObservableCollection<IPageViewModel>(PageManager.Pages.OfType<IPageViewModel>()); }
This is WRONG because like this all change notifications will go to an independent object, the lastly created ObservableCollection, which is obviosly not what we would want.
So what our requirement is actually to create a bond between the two collections, that if one of them changes, then the other does as well. As you might already know, Microsoft provided the INotifyCollectionChanged interface, which exposes the CollectionChanged event to notify interested parties, that the collection has changed. We will use this interface, which ObservableCollection already implements.

The following code uses the MemberInfo helper class, which is explained in this blog post. It also uses the WithParams extension method on strings, which is simply a more fluent way of string.Format having the following code:
        public static string WithParams(this string text, params object[] parameters)
        {
            return string.Format(text, parameters);
        }
I also use the Moq framework for the unit tests. You can get it at google codeplex here
Other requirements might be to be able to stop the synchronization and to restart it after a time.
The synchronization token, that actually represents the synchronization itself will get in its constructor the source and destination collections, and two converter functions between the tpes. The second converter function should be allowed to be null, which means that the synchronization shall be only one way.
Now a very important thing is the way we convert items. The class should check for potential errors while for example removing items from the second collection. If we have a one-way synchronization, and the second collection has different elements than the synchronization source, then we should probably throw an error, then to remove another element just by index.
!!!IMPORTANT!!!
The comparisions are done using the .Equals() method, so the converter functions should make sure that convert(x).Equals(convert(x)), and that convertBack(x).Equals(convertBack). This is especially important, because for example when wrapping a type into another, then you cannot simply create a new wrapped type on the convert, because the object equality will fail. You should in this case override the .Equals() function, to return for example equality on the wrapped object.
Do not overlook this, because it can cause you a lot of headache to figure out why the code throws errors or has unexpected results!!
Lets start by writing a unit test for the functionality.

------------- Test -------------


First we create a unit test calss.
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Moq;

namespace CollectionSyncronizationTokenTest
{
    [TestClass]
    public class CollectionSyncronizationTokenTest
    {
        [TestMethod]
        public void TestMethod1()
        {
        }
    }
}
Now we dont need TestMethod1(). We can remove it.
We will write the tests against an int and a string collection. We will convert with the .ToString() method, and we will convert back trying to parse, and return 0 if failing. In the tests we dont test for the correctness of the convert functions, and we will not pass in wrong results for the convertBack method.
        private ObservableCollection<int> sourceCollection = new ObservableCollection<int>();
        private ObservableCollection<string> destCollection = new ObservableCollection<string>();
        private Func<int, string> converterFunc;
        private Func<string, int> convertBackFunc;
        CollectionSyncronizationToken<int, string> subject;


        [TestInitialize]
        public void Init()
        {
            this.converterFunc = (i) =>
            {
                return i.ToString();
            };

            this.convertBackFunc = (s) =>
            {
                int temp;
                if (Int32.TryParse(s, out temp))
                {
                    return temp;
                }
                return 0;
            };

        }
Now we should create some test methods, that will make sure that our requirements are met. The NotifyCollectionChangedAction enum is the action representing what has changed in the source collection has 5 possile values. We will make a test for each of these actions. Since we want to test the synchronization both ways, we will make these tests generic, so they can be invked on any of the collections.
First we start Adding items. We simply make sure the initial count is ok, and then add an elem from the exampleList (randomly), and make sure that the item was added to the other collection as well. We need the example list, because of the generic argument, as i cannot just create a new() object of TSource, since might for example in the case of test not be different enough in subsequential runs.
        /// <summary>
        /// checks if adding is syncronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsAddSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, Func<TSource, TDestination> converter, IEnumerable<TSource> exampleList)
        {
            Assert.AreEqual(source.Count, destination.Count);

            var list = exampleList.ToList();
            var testItem = list[new Random().Next(list.Count)];
            var convertedItem = converter(testItem);

            source.Add(testItem);
            Assert.AreEqual(source.Count, destination.Count);
            Assert.AreEqual(convertedItem, destination.Last());
        }
Then we test remove and removeAt.
        /// <summary>
        /// checks if removing is synchronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsRemoveSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, Func<TSource, TDestination> converter)
        {
            Assert.AreEqual(source.Count, destination.Count);
            Assert.IsTrue(source.Count > 1);

            // test remove
            var testItem = source[new Random().Next(source.Count)];
            var convertedItem = converter(testItem);

            var index = source.IndexOf(testItem);
            source.Remove(testItem);
            Assert.AreEqual(source.Count, destination.Count);

            // test removeat
            testItem = source[new Random().Next(source.Count)];
            convertedItem = converter(testItem);

            index = source.IndexOf(testItem);
            source.RemoveAt(index);
            Assert.AreEqual(source.Count, destination.Count);
        }

The next is a move, which is supported by ObservableCollection.
        /// <summary>
        /// checks if moving is synchronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsMoveSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, Func<TSource, TDestination> converter)
        {
            Assert.AreEqual(source.Count, destination.Count);
            Assert.IsTrue(source.Count > 1);

            // get the 2 items to move
            var idx1 = new Random().Next(source.Count);
            var idx2 = new Random().Next(source.Count - 1);
            idx2 = idx2 >= idx1 ? idx2 + 1 : idx2;

            var item = source[idx1];
            var convertedItem = converter(item);
            source.Move(idx1, idx2);

            Assert.AreEqual(source.Count, destination.Count);
            Assert.AreEqual(convertedItem, destination[idx2]);
            // test removeat
        }
Now check the replace.
        /// <summary>
        /// checks if relacing is synchronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsReplaceSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, Func<TSource, TDestination> converter, IEnumerable<TSource> testItems)
        {
            Assert.AreEqual(source.Count, destination.Count);
            Assert.IsTrue(source.Count > 0);

            var list = testItems.ToList();
            var item = list[new Random().Next(list.Count)];
            var convertedItem = converter(item);
            var idx = new Random().Next(source.Count);

            source[idx] = item;
            Assert.AreEqual(source.Count, destination.Count);
            Assert.AreEqual(convertedItem, destination[idx]);
        }
And finally the clear method.
        /// <summary>
        /// checks if clear is synchronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsClearSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination)
        {
            Assert.AreEqual(source.Count, destination.Count);
            Assert.IsTrue(source.Count > 0);

            source.Clear();
            Assert.AreEqual(0, destination.Count);
        }

I am not aware of any other functions, but you may add them if you find. Please let me know if I missed something.

Now we also need a helper method, that tests that 2 collections are atm synchronized. (The .ForEach() method simply takes an action with the item, and its index)
        /// <summary>
        /// checks if collections are syncronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, Func<TSource, TDestination> converter)
        {
            Assert.AreEqual(source.Count, destination.Count);

            source.ForEach((item, idx) =>
            {
                Assert.AreEqual(converter(item), destination[idx]);
            });
        }

We will create also one to make sure that a collection is not syncronized with another. Here we just test for all operations.
        /// <summary>
        /// checks if 2 collections are not synchronized
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TDestination"></typeparam>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        private void IsNotSynced<TSource, TDestination>(ObservableCollection<TSource> source, ObservableCollection<TDestination> destination, IEnumerable<TSource> testItems)
        {
            var iscalled = false;
            NotifyCollectionChangedEventHandler handler = (s, e) =>
            {
                iscalled = true;
            };
            destination.CollectionChanged += handler;

            var list = testItems.ToList();
            Func<TSource> getNext = () => list[new Random().Next(list.Count)];


            source.Add(getNext());
            Assert.IsFalse(iscalled);
            source.Add(getNext());
            source.Add(getNext());
            source.Add(getNext());

            source.Remove(source.Skip(2).FirstOrDefault());
            Assert.IsFalse(iscalled);
            source.RemoveAt(new Random().Next(source.Count));
            Assert.IsFalse(iscalled);

            // get the 2 items to move
            var idx1 = new Random().Next(source.Count);
            var idx2 = new Random().Next(source.Count - 1);
            idx2 = idx2 >= idx1 ? idx2 + 1 : idx2;
            source.Move(idx1, idx2);
            Assert.IsFalse(iscalled);

            source[new Random().Next(source.Count)] = getNext();
            Assert.IsFalse(iscalled);

            source.Clear();

            Assert.IsFalse(iscalled);
            destCollection.CollectionChanged -= handler;

        }



Great. So now that we have some helper methods, lets write the tests for the string and int collections. We have 6 test case. First we want to check if the oneway synchronization works, so that it creates an initial synchronization, and then changes are propagated. The to see if stopping the synch results in no more change propagation. The we test if after restarting the functionality is back.
The other 3 tests are the same, but with 2 way binding.
The code is as follows:
        [TestMethod]
        public void TestSyncWith()
        {
            var collection1 = this.sourceCollection;
            var collection2 = this.destCollection;
            var converter = this.converterFunc;
            var convertBack = this.convertBackFunc;

            collection1.Add(2);
            collection1.Add(5);

            var token = this.subject = new CollectionSyncronizationToken<int, string>(collection1, collection2, converter, convertBack);


            IsSynced(collection1, collection2, converter);
            IsAddSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            IsAddSynced(collection2, collection1, convertBack, Enumerable.Range(10, 20).Select(x => x.ToString()));
            // remove removes 2 items, so just add 2 more
            collection1.Add(22);
            collection1.Add(33);

            IsRemoveSynced(collection1, collection2, converter);
            IsRemoveSynced(collection2, collection1, convertBack);

            IsMoveSynced(collection1, collection2, converter);
            IsMoveSynced(collection2, collection1, convertBack);

            IsReplaceSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            IsReplaceSynced(collection2, collection1, convertBack, Enumerable.Range(10, 20).Select(x => x.ToString()));

            IsClearSynced(collection1, collection2);
            collection1.Add(44);
            collection1.Add(55);
            IsClearSynced(collection2, collection1);

        }

        [TestMethod]
        public void TestStopSync()
        {
            this.sourceCollection.Add(1);
            this.sourceCollection.Add(22);
            this.sourceCollection.Add(33);
            this.sourceCollection.Add(44);

            var token = this.subject = new CollectionSyncronizationToken<int, string>(this.sourceCollection, this.destCollection, this.converterFunc, this.convertBackFunc);

            token.StopSync();

            IsNotSynced(this.sourceCollection, this.destCollection, Enumerable.Range(10, 20));
            IsNotSynced(this.destCollection, this.sourceCollection, Enumerable.Range(10, 20).Select(x => x.ToString()));

        }



        [TestMethod]
        public void TestRestartSync()
        {
            var collection1 = this.sourceCollection;
            var collection2 = this.destCollection;
            var converter = this.converterFunc;
            var convertBack = this.convertBackFunc;

            collection1.Add(2);
            collection1.Add(5);

            var token = this.subject = new CollectionSyncronizationToken<int, string>(this.sourceCollection, this.destCollection, this.converterFunc, this.convertBackFunc);

            token.StopSync();
            collection1.Add(102);
            collection1.Add(105);

            token.RestartSync();


            IsSynced(collection1, collection2, converter);
            IsAddSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            IsAddSynced(collection2, collection1, convertBack, Enumerable.Range(10, 20).Select(x => x.ToString()));
            // remove removes 2 items, so just add 2 more
            collection1.Add(22);
            collection1.Add(33);

            IsRemoveSynced(collection1, collection2, converter);
            IsRemoveSynced(collection2, collection1, convertBack);

            IsMoveSynced(collection1, collection2, converter);
            IsMoveSynced(collection2, collection1, convertBack);

            IsReplaceSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            IsReplaceSynced(collection2, collection1, convertBack, Enumerable.Range(10, 20).Select(x => x.ToString()));

            IsClearSynced(collection1, collection2);
            collection1.Add(44);
            collection1.Add(55);
            IsClearSynced(collection2, collection1);

        }

        [TestMethod]
        public void TestSyncOneWay()
        {
            this.sourceCollection.Add(33);
            this.sourceCollection.Add(44);
            this.subject = new CollectionSyncronizationToken<int, string>(this.sourceCollection, this.destCollection, this.converterFunc);

            var collection1 = this.sourceCollection;
            var collection2 = this.destCollection;
            var converter = this.converterFunc;

            IsSynced(collection1, collection2, converter);
            IsAddSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            // remove removes 2 items, so just add 2 more
            collection1.Add(22);
            collection1.Add(33);

            IsRemoveSynced(collection1, collection2, converter);

            IsMoveSynced(collection1, collection2, converter);

            IsReplaceSynced(collection1, collection2, converter, Enumerable.Range(10, 20));

            IsClearSynced(collection1, collection2);

            IsNotSynced(collection2, collection1, Enumerable.Range(10, 20).Select(x => x.ToString()));
        }

        [TestMethod]
        public void TestStopSyncOneWay()
        {
            this.sourceCollection.Add(1);
            this.sourceCollection.Add(22);
            this.sourceCollection.Add(33);
            this.sourceCollection.Add(44);

            var token = this.subject = new CollectionSyncronizationToken<int, string>(this.sourceCollection, this.destCollection, this.converterFunc);

            token.StopSync();

            IsNotSynced(this.sourceCollection, this.destCollection, Enumerable.Range(10, 20));
            IsNotSynced(this.destCollection, this.sourceCollection, Enumerable.Range(10, 20).Select(x => x.ToString()));

        }

        [TestMethod]
        public void TestSyncOneWayRestart()
        {
            this.sourceCollection.Add(33);
            this.sourceCollection.Add(44);
            this.subject = new CollectionSyncronizationToken<int, string>(this.sourceCollection, this.destCollection, this.converterFunc);

            var collection1 = this.sourceCollection;
            var collection2 = this.destCollection;
            var converter = this.converterFunc;


            this.subject.StopSync();
            collection1.Add(102);
            collection1.Add(105);

            this.subject.RestartSync();

            IsSynced(collection1, collection2, converter);
            IsAddSynced(collection1, collection2, converter, Enumerable.Range(10, 20));
            // remove removes 2 items, so just add 2 more
            collection1.Add(22);
            collection1.Add(33);

            IsRemoveSynced(collection1, collection2, converter);

            IsMoveSynced(collection1, collection2, converter);

            IsReplaceSynced(collection1, collection2, converter, Enumerable.Range(10, 20));

            IsClearSynced(collection1, collection2);

            IsNotSynced(collection2, collection1, Enumerable.Range(10, 20).Select(x => x.ToString()));
        }
Hehe, quite a long test class, but we are done with the worse. We have the tests, now its just the development of the class. Lets create the class now.


------------- Class -------------

We start off by creating our classm and createing the default constructor. We save all dependencies in private fields. We also add an IsSynchronizing readonly property, and handle it internally later. We also define an isActive prvate property. The goal of this property is to avoid cycles. When we subscribe a two way notification, then change in collecrtion 1 would raise a change in collection 2 which in turn would do the same to collection 1, and so on. To avoid these cycles, we will use this field.
We also added the public methods StopSync() and RestartSync(). With all this code, your unittests should finally compile, and fail. (well, since there is no code yet, the stop methods actually already work, wohooo :) )
using CollectionSyncronizationToken.HelperClasses;
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CollectionSyncronizationToken
{
    public class CollectionSynchronizationToken<TSource, TDestination>
    {

        #region properties
        /// <summary>
        /// whether the syncronization is turned on
        /// </summary>
        public bool IsSyncing { get { return _IsSyncing; } }
        #endregion properties

        #region fields
        private bool _IsSyncing = true;
        private Func<TSource, TDestination> _converter;
        private Func<TDestination, TSource> _backConverter;
        private ObservableCollection<TSource> _sourceCollection;
        private ObservableCollection<TDestination> _destinationCollection;
        /// <summary>
        /// this field turns the effective syncronization off, so that the handlers do not start calling each other in an unlimited way
        /// </summary>
        private bool isActive = true;
        #endregion fields

        #region ctor
        public CollectionSynchronizationToken(ObservableCollection<TSource> sourceCollection, ObservableCollection<TDestination> destinationCollection, Func<TSource, TDestination> converter, Func<TDestination, TSource> backConverter = null)
        {
            #region parameter check
            if (sourceCollection == null)
                throw new ArgumentNullException(MemberName.Param(() => sourceCollection));
            if (destinationCollection == null)
                throw new ArgumentNullException(MemberName.Param(() => destinationCollection));
            if (converter == null)
                throw new ArgumentNullException(MemberName.Param(() => converter));
            #endregion parameter check

            this._sourceCollection = sourceCollection;
            this._destinationCollection = destinationCollection;
            this._converter = converter;
            this._backConverter = backConverter;
            InitDestinationCollectionValues();
            AddHandlers();

        }
        #endregion ctor

        #region public methods
        /// 
        /// stops the syncronization
        /// 
        public void StopSync()
        {

        }

        /// 
        /// starts again the syncronization
        /// 
        public void RestartSync()
        {
        }
        #endregion public methods
    }
}
Now start to fill the gaps. The object starts with a synch state, so we need to do an initial synchronization, and create the event handlers and attach them to the collection. On stop we just remove the handlers, and on restart we reattach them.
So we call in the constructor and the restart the same, and in the stop remove the handlers
        public CollectionSyncronizationToken(ObservableCollection<TSource> sourceCollection, ObservableCollection<TDestination> destinationCollection, Func<TSource, TDestination> converter, Func<TDestination, TSource> backConverter = null)
        {
            //.. previous code here
            InitDestinationCollectionValues();
            AddHandlers();
        }

        #region public methods
        /// 
        /// stops the syncronization
        /// 
        public void StopSync()
        {
            if (_IsSyncing)
            {
                RemoveHandlers();
            }
        }

        /// 
        /// starts again the syncronization
        /// 
        public void RestartSync()
        {
            if (!_IsSyncing)
            {
                InitDestinationCollectionValues();
                AddHandlers();
            }
        }
        #endregion public methods
Ok, we just created some work for ourselves, but lets see the units.
Lets create quickly a Convert and a ConvertBack method. These are good apart, cause this allows you to do any error handling, if you want, on the conversions (which is a good idea, since those are delegates passed from calling code.
        private TDestination Convert(TSource item)
        {
            return this._converter(item);
        }

        private TSource ConvertBack(TDestination item)
        {
            return this._backConverter(item);
        }
The InitDestinationCollectionValues() should just update the destination collection with values from the first collection.
        /// 
        /// sets the correct values on the destination collection to begin a syncronized state
        /// 
        private void InitDestinationCollectionValues()
        {
            this._sourceCollection.ForEach((item, index) =>
            {
                var convertedItem = this.Convert(item);
                if (this._destinationCollection.Count > index)
                {
                    if (!convertedItem.Equals(this._destinationCollection[index]))
                    {
                        this._destinationCollection[index] = convertedItem;
                    }
                }
                else // we just add the item, as the index should be right
                {
                    this._destinationCollection.Add(convertedItem);
                }
            });
        }
Great. Now we need to implement the add and remove handlers.
The handlers will be simple handler functions in this token.
        /// 
        /// adds the collection change handlers to the collections
        /// 
        private void AddHandlers()
        {
            this._sourceCollection.CollectionChanged += _sourceCollection_CollectionChanged;
            if (this._backConverter != null)
            {
                this._destinationCollection.CollectionChanged += _destinationCollection_CollectionChanged;
            }
            this._IsSyncing = true;
        }

        /// 
        /// removes the handlers
        /// 
        private void RemoveHandlers()
        {
            this._sourceCollection.CollectionChanged -= _sourceCollection_CollectionChanged;
            if (this._backConverter != null)
            {
                this._destinationCollection.CollectionChanged -= _destinationCollection_CollectionChanged;
            }
            this._IsSyncing = false;
        }
 

        #region handlers
        void _destinationCollection_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
        {
        }

        void _sourceCollection_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
        {
        }
        #endregion handlers
Cool. So all that is left, is the handling of the collection changed. Now essentially whether we are synchronizing from the first, or the second collection, there should be not much difference. So lets create a helper method, that will handle the synchronization. It will recieve the collection that raised the event, the collection where the change has to be propagated, and string names for the source and destination collections, that will be included in the errors.
Fisrt lets create a helper class, that will format our exceptions. Obviously if you prefer, you can use any other method of error handling.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using CollectionSyncronizationToken.Extenders;

namespace CollectionSyncronizationToken.HelperClasses
{
    public class ExceptionHelper
    {
        /// <summary>
        /// creates a collection sync conversion exception
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TResult"></typeparam>
        /// <param name="ex"></param>
        /// <param name="sourceCollection"></param>
        /// <param name="destinationCollection"></param>
        /// <param name="isNormalDirection"></param>
        /// <returns></returns>
        public static Exception CollectionSyncronizationException<TSource, TResult>(string message, Exception ex, ObservableCollection<TSource> sourceCollection, ObservableCollection<TResult> destinationCollection)
        {
            return new Exception("An error occured while trying to syncronize two collections of type {0} and {1}: {2}".WithParams(typeof(TSource).Name, typeof(TResult).Name, message), ex);
        }

        /// <summary>
        /// creates a collection sync conversion exception
        /// </summary>
        /// <typeparam name="TSource"></typeparam>
        /// <typeparam name="TResult"></typeparam>
        /// <param name="ex"></param>
        /// <param name="sourceCollection"></param>
        /// <param name="destinationCollection"></param>
        /// <param name="isNormalDirection"></param>
        /// <returns></returns>
        public static Exception CollectionSyncronizationConvertException<TSource, TResult>(Exception ex, ObservableCollection<TSource> sourceCollection, ObservableCollection<TResult> destinationCollection, bool isNormalDirection)
        {
            return new Exception(
                "An error occured while trying to syncronize two collections of type {0} and {1}. The conversion from {2} to {3} failed."
                    .WithParams(typeof(TSource).Name, typeof(TResult).Name,
                        isNormalDirection ? typeof(TSource).Name : typeof(TResult).Name,
                        isNormalDirection ? typeof(TResult).Name : typeof(TSource).Name),
                ex);
        }
    }
}
Ok, and now comes the hard part. Lets create the handling method, and start a switch statement over what we have to do (its in the eventArgs.Action field).
        /// <summary>
        /// handles the collection changed event
        /// </summary>
        /// <typeparam name="TItemSource"></typeparam>
        /// <typeparam name="TItemDest"></typeparam>
        /// <param name="sourceCollectionName"></param>
        /// <param name="destinationCollectionName"></param>
        /// <param name="sourceCollection"></param>
        /// <param name="destinationCollection"></param>
        private void HandleCollectionChanged<TItemSource, TItemDest>(NotifyCollectionChangedEventArgs e, string sourceCollectionName, string destinationCollectionName,
            ObservableCollection<TItemSource> sourceCollection, ObservableCollection<TItemDest> destinationCollection, Func<TItemSource, TItemDest> converter)
        {
            switch (e.Action)
            {
                case System.Collections.Specialized.NotifyCollectionChangedAction.Add:
                    break;
                case System.Collections.Specialized.NotifyCollectionChangedAction.Move:
                    break;
                case System.Collections.Specialized.NotifyCollectionChangedAction.Remove:
                    break;
                case System.Collections.Specialized.NotifyCollectionChangedAction.Replace:
                    break;
                case System.Collections.Specialized.NotifyCollectionChangedAction.Reset:
                    break;
                default:
                    throw ExceptionHelper.CollectionSyncronizationException("The {0} collection raised an {1} action which was not understood (oldItemCount:{2}, olditemIndex:{3}, newItemCount:{4}, newItemIndex{5})".WithParams(sourceCollectionName, e.Action, e.OldItems.Count, e.OldStartingIndex, e.NewItems.Count, e.NewStartingIndex), null, _sourceCollection, _destinationCollection);
            }

        }
On NotifyCollectionChangedAction.Add the collection should have aquired new items in the given position of the collection, so we just add the given items there after some error checking.
                case System.Collections.Specialized.NotifyCollectionChangedAction.Add:
                    // we can move only one item
                    if (e.NewItems.Count + e.NewStartingIndex > sourceCollection.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("The {3} collection of {0} elements raised an add of {1} elements from position {2}, which is not possible".WithParams(sourceCollection.Count, e.NewItems.Count, e.NewStartingIndex, sourceCollectionName), null, this._sourceCollection, this._destinationCollection);
                    }
                    if(e.NewStartingIndex > destinationCollection.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("The {3} collection of {0} elements raised an add of {1} elements from position {2}, but the {4} collection has only {5} elmenents so inserting at the given index is not possible".WithParams(sourceCollection.Count, e.NewItems.Count, e.NewStartingIndex, sourceCollectionName, destinationCollectionName, destinationCollection.Count), null, this._sourceCollection, this._destinationCollection);
                    }

                    e.NewItems.OfType<TItemSource>().ForEach((item, idx) =>
                    {
                        destinationCollection.Insert(e.NewStartingIndex + idx, converter(item));
                    });
                        
                    break;
When we NotifyCollectionChangedAction.Move an item, it should happen with the .Move command of the ObservableCollection. It should have exactly 1 item in the NewItems collection, and the Old and new starting index should specify from where to where move them. So we do some error checking, and if all is ok, we do the same method call on the destination collection
                case System.Collections.Specialized.NotifyCollectionChangedAction.Move:
                    // we can move only one item
                    if (e.NewItems.Count != 1)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("Not exactly one({0}) item moved in the {1} collection".WithParams(e.NewItems.Count, sourceCollectionName), null, this._sourceCollection, this._destinationCollection);
                    }
                    if (e.NewStartingIndex >= destinationCollection.Count || e.OldStartingIndex >= destinationCollection.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("The oldIndex({0}) or the newIndex({1}) are larger then the {3} collection size({2}) during move".WithParams(e.OldStartingIndex, e.NewStartingIndex, destinationCollection.Count, destinationCollectionName), null, _sourceCollection, _destinationCollection);
                    }
                    if (e.NewStartingIndex >= sourceCollection.Count || e.OldStartingIndex >= sourceCollection.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("The oldIndex({0}) or the newIndex({1}) are larger then the {3} collection size({2}) during move".WithParams(e.OldStartingIndex, e.NewStartingIndex, sourceCollection.Count, sourceCollectionName), null, this._sourceCollection, this._destinationCollection);
                    }
                    if (e.NewStartingIndex != e.OldStartingIndex)
                    {
                        // the item in the destination that has been moved
                        var convertedItem = converter(sourceCollection[e.NewStartingIndex]);
                        if (!convertedItem.Equals(destinationCollection[e.OldStartingIndex]))
                        {
                            throw ExceptionHelper.CollectionSyncronizationException("The moved item (from pos {0} to {1}) does not match the item on position {0} in the {2} collection".WithParams(e.OldStartingIndex, e.NewStartingIndex, destinationCollectionName), null, this._sourceCollection, this._destinationCollection);
                        }

                        // move the item
                        destinationCollection.Move(e.OldStartingIndex, e.NewStartingIndex);
                    }
                    break;
When items are removed from the collection(NotifyCollectionChangedAction.Remove), then we have to do the same. We need some error checking that the items are the same, and that the indexes are valid, then we can remove from index. Unfortunately there is no bulk remove from ObservableCollection, so we call it one at a time.
                case System.Collections.Specialized.NotifyCollectionChangedAction.Remove:
                    if (destinationCollection.Count < sourceCollection.Count + e.OldItems.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("A remove of {0} items from position {1} has been initiated on the {2}, but the {3} has only {4} items".WithParams(e.OldItems.Count, e.OldStartingIndex, sourceCollectionName, destinationCollectionName, destinationCollection.Count), null, this._sourceCollection, this._destinationCollection);
                    }
                    var index = 0;
                    foreach (var item in e.OldItems.OfType<TItemSource>())
                    {
                        var convertedItem = converter(item);
                        if (!convertedItem.Equals(destinationCollection[e.OldStartingIndex]))
                        {
                            throw ExceptionHelper.CollectionSyncronizationException("The removed item (startingindex: {0}, position in list: {1}) from the {2} collection does not match the item in the {3} collection".WithParams(e.OldStartingIndex, index, sourceCollectionName, destinationCollectionName), null, this._sourceCollection, this._destinationCollection);
                        }
                        destinationCollection.RemoveAt(e.OldStartingIndex);
                        index++;
                    }
                    break;
When we specify a value by indexing the collection, then the NotifyCollectionChangedAction.Replace action is called. We need to make sure the replaced item is the correct one, and that the indexes are ok. Then:
                case System.Collections.Specialized.NotifyCollectionChangedAction.Replace:
                    if (e.NewStartingIndex + e.NewItems.Count > destinationCollection.Count)
                    {
                        throw ExceptionHelper.CollectionSyncronizationException("The replaced item count is too big (starting at position {0} with {1} elements, but the {3} collection has only {2} elements".WithParams(e.NewStartingIndex, e.NewItems.Count, destinationCollection.Count, destinationCollectionName), null, this._sourceCollection, this._destinationCollection);
                    }
                    e.NewItems.OfType<TItemSource>().ForEach((item, idx) =>
                    {
                        var convertedItem = converter(item);
                        if (!convertedItem.Equals(destinationCollection[idx + e.NewStartingIndex]))
                        {
                            destinationCollection[idx + e.NewStartingIndex] = convertedItem;
                        }
                    });
                    break;
Now the NotifyCollectionChangedAction.Reset action is a bit more problematic. This essentially means to the handlers, that: "all your prior knowledge about the list is invalid now". So in order for this destaintion collection to raise the same event, we first clear it, and then essentially refill with he correct values.
                case System.Collections.Specialized.NotifyCollectionChangedAction.Reset:
                    // now when a reset happens, it essentially means to the handlers, that: "all your prior knowledge about the list is invalid now"
                    // so we could either clear the list, and readd all items from source, or simply make sure they are synced now
                    // the second is probably a bit faster, but will not raise the reset event, so we will implement the first way
                    destinationCollection.Clear();
                    sourceCollection.ForEach((item, idx) => destinationCollection.Add(converter(item)));
                    break;
And now we are done implementing the handler. Just plug it into the the actual event handlers with the isActive flag check:
        void _destinationCollection_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
        {
            if (isActive)
            {
                isActive = false;

                HandleCollectionChanged(e, "destination", "source", this._destinationCollection, this._sourceCollection, this.ConvertBack);

                isActive = true;
            }
        }

        void _sourceCollection_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
        {
            if (isActive)
            {
                isActive = false;

                HandleCollectionChanged(e, "source", "destination", this._sourceCollection, this._destinationCollection, this.Convert);

                isActive = true;
            }
        }
  
And we are done.
Running the unit tests will make sure we did not make a mistake. It is a bit longer than I originally expected, but hopefully it will be useful to all of you who are interested.

And then finally you can create your extension method, and hide all this code behind a simple call to: .SyncFrom(collection, converter) with:
        public static CollectionSyncronizationToken<TSource, TResult> SyncFrom<TSource, TResult>(this ObservableCollection<TResult> destinationCollection, ObservableCollection<TSource> sourecCollection, Func<TSource, TResult> converter, Func<TResult, TSource> convertBack = null)
        {
            return new CollectionSyncronizationToken<TSource, TResult>(sourecCollection, destinationCollection, converter, convertBack);
        }

Room for improvement

Well as you can see from the code, if we handle the synchronization only one way, we dont need an ObservableCollection. Actually any object implementing INotifyCollectionChanged will do. As for the target collection, we need the Add(T), Insert(int, T), Remove(T), RemoveAt(int), Move(), [int](indexer) and Clear() methods. SO any interface implementing all these methods can be a potential target, you just need to change the types, and it should all work.

If you want two way synchronization, you could still create an interface, that implements INotifyCollectionChanged, IList, and the Move method, and then you can use simply that interface instead of ObservableCollection. Unfortunately ObservableCollection wil not implement your interface, so you might need to have 4 different signateures for the extension method, but hey that's not a biggie.

You could also create an interface for the token, and then allow others to create their own implementation, but as long as you have the source, it is fine.

If you have any suggestions regarding the above, please do not hesitate to comment or to contact me.

You can download the source code from here.