anchor.diff:  
   [<CompiledName("Fold")>]
   let fold<'Key,'T,'State when 'Key : comparison> f (z:'State) (m:Map<'Key,'T>) =
  -   let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
  -   MapTree.fold f z m.Tree
  +    let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
  +    MapTree.fold f z m.Tree
   
   [<CompiledName("FoldBack")>]
   let foldBack<'Key,'T,'State  when 'Key : comparison> f (m:Map<'Key,'T>) (z:'State) =
  -   let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
  -   MapTree.foldBack  f m.Tree z
  +    let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
  +    MapTree.foldBack  f m.Tree z
   
   [<CompiledName("ToSeq")>]
   let toSeq (m:Map<_,_>) = m |> Seq.map (fun kvp -> kvp.Key, kvp.Value)
  
positive.code: 
  [<CompiledName("OfArray")>]
  let ofArray (array: ('Key * 'Value) array) =
     let comparer = GenericComparer<'Key>()
     new Map<_,_>(comparer,MapTree.ofArray comparer array)
  
  [<CompiledName("ToList")>]
  let toList (m:Map<_,_>) = m.ToList()
  
negative.code: 
  open System.Collections.Generic
  
  // TODO: We can probably replace with Util.comparePrimitives
  type GenericComparer<'T when 'T : equality and 'T : comparison>() =
      interface IComparer<'T> with
          member __.Compare(x, y) =
              if x = y then
                  0
              else if x < y then
                  -1
              else
                  1
  
  // [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
  // [<NoEquality; NoComparison>]
  type MapTree<'Key,'Value when 'Key : comparison > =
      | MapEmpty
      | MapOne of 'Key * 'Value
      | MapNode of 'Key * 'Value * MapTree<'Key,'Value> *  MapTree<'Key,'Value> * int
      // REVIEW: performance rumour has it that the data held in MapNode and MapOne should be
      // exactly one cache line. It is currently ~7 and 4 words respectively.
  
  [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
  module MapTree =
  
      let rec sizeAux acc m =
          match m with
          | MapEmpty -> acc
          | MapOne _ -> acc + 1
          | MapNode(_,_,l,r,_) -> sizeAux (sizeAux (acc+1) l) r
  
      let size x = sizeAux 0 x
  
      let empty = MapEmpty
  
      let height  = function
          | MapEmpty -> 0
          | MapOne _ -> 1
          | MapNode(_,_,_,_,h) -> h
  
      let isEmpty m =
          match m with
          | MapEmpty -> true
          | _ -> false
  
      let mk l k v r =
          match l,r with
          | MapEmpty,MapEmpty -> MapOne(k,v)
          | _ ->
              let hl = height l
              let hr = height r
              let m = if hl < hr then hr else hl
              MapNode(k,v,l,r,m+1)
  
      let rebalance t1 k v t2 =
          let t1h = height t1
          let t2h = height t2
          if  t2h > t1h + 2 then (* right is heavier than left *)
              match t2 with
              | MapNode(t2k,t2v,t2l,t2r,_) ->
                  (* one of the nodes must have height > height t1 + 1 *)
                  if height t2l > t1h + 1 then  (* balance left: combination *)
                      match t2l with
                      | MapNode(t2lk,t2lv,t2ll,t2lr,_) ->
                          mk (mk t1 k v t2ll) t2lk t2lv (mk t2lr t2k t2v t2r)
                      | _ -> failwith "rebalance"
                  else (* rotate left *)
                      mk (mk t1 k v t2l) t2k t2v t2r
              | _ -> failwith "rebalance"
          else
              if  t1h > t2h + 2 then (* left is heavier than right *)
                  match t1 with
                  | MapNode(t1k,t1v,t1l,t1r,_) ->
                      (* one of the nodes must have height > height t2 + 1 *)
                      if height t1r > t2h + 1 then
                          (* balance right: combination *)
                          match t1r with
                          | MapNode(t1rk,t1rv,t1rl,t1rr,_) ->
                              mk (mk t1l t1k t1v t1rl) t1rk t1rv (mk t1rr k v t2)
                          | _ -> failwith "re  balance"
                      else
                          mk t1l t1k t1v (mk t1r k v t2)
                  | _ -> failwith "rebalance"
              else mk t1 k v t2
  
      let rec add (comparer: IComparer<'Value>) k v m =
          match m with
          | MapEmpty -> MapOne(k,v)
          | MapOne(k2,_) ->
              let c = comparer.Compare(k,k2)
              if c < 0   then MapNode (k,v,MapEmpty,m,2)
              elif c = 0 then MapOne(k,v)
              else            MapNode (k,v,m,MapEmpty,2)
          | MapNode(k2,v2,l,r,h) ->
              let c = comparer.Compare(k,k2)
              if c < 0 then rebalance (add comparer k v l) k2 v2 r
              elif c = 0 then MapNode(k,v,l,r,h)
              else rebalance l k2 v2 (add comparer k v r)
  
      let rec find (comparer: IComparer<'Value>) k m =
          match m with
          | MapEmpty -> failwith "key not found"
          | MapOne(k2,v2) ->
              let c = comparer.Compare(k,k2)
              if c = 0 then v2
              else failwith "key not found"
          | MapNode(k2,v2,l,r,_) ->
              let c = comparer.Compare(k,k2)
              if c < 0 then find comparer k l
              elif c = 0 then v2
              else find comparer k r
  
      let rec tryFind (comparer: IComparer<'Value>) k m =
          match m with
          | MapEmpty -> None
          | MapOne(k2,v2) ->
              let c = comparer.Compare(k,k2)
              if c = 0 then Some v2
              else None
          | MapNode(k2,v2,l,r,_) ->
              let c = comparer.Compare(k,k2)
              if c < 0 then tryFind comparer k l
              elif c = 0 then Some v2
              else tryFind comparer k r
  
      let partition1 (comparer: IComparer<'Value>) f k v (acc1,acc2) =
          if f k v then (add comparer k v acc1,acc2) else (acc1,add comparer k v acc2)
  
      let rec partitionAux (comparer: IComparer<'Value>) f s acc =
          match s with
          | MapEmpty -> acc
          | MapOne(k,v) -> partition1 comparer f k v acc
          | MapNode(k,v,l,r,_) ->
              let acc = partitionAux comparer f r acc
              let acc = partition1 comparer f k v acc
              partitionAux comparer f l acc
  
      let partition (comparer: IComparer<'Value>) f s = partitionAux comparer f s (empty,empty)
  
      let filter1 (comparer: IComparer<'Value>) f k v acc = if f k v then add comparer k v acc else acc
  
      let rec filterAux (comparer: IComparer<'Value>) f s acc =
          match s with
          | MapEmpty -> acc
          | MapOne(k,v) -> filter1 comparer f k v acc
          | MapNode(k,v,l,r,_) ->
              let acc = filterAux comparer f l acc
              let acc = filter1 comparer f k v acc
              filterAux comparer f r acc
  
      let filter (comparer: IComparer<'Value>) f s = filterAux comparer f s empty
  
      let rec spliceOutSuccessor m =
          match m with
          | MapEmpty -> failwith "internal error: Map.spliceOutSuccessor"
          | MapOne(k2,v2) -> k2,v2,MapEmpty
          | MapNode(k2,v2,l,r,_) ->
              match l with
              | MapEmpty -> k2,v2,r
              | _ -> let k3,v3,l' = spliceOutSuccessor l in k3,v3,mk l' k2 v2 r
  
      let rec remove (comparer: IComparer<'Value>) k m =
          match m with
          | MapEmpty -> empty
          | MapOne(k2,_) ->
              let c = comparer.Compare(k,k2)
              if c = 0 then MapEmpty else m
          | MapNode(k2,v2,l,r,_) ->
              let c = comparer.Compare(k,k2)
              if c < 0 then rebalance (remove comparer k l) k2 v2 r
              elif c = 0 then
                  match l,r with
                  | MapEmpty,_ -> r
                  | _,MapEmpty -> l
                  | _ ->
                      let sk,sv,r' = spliceOutSuccessor r
                      mk l sk sv r'
                      else rebalance l k2 v2 (remove comparer k r)
  
      let rec mem (comparer: IComparer<'Value>) k m =
          match m with
          | MapEmpty -> false
          | MapOne(k2,_) -> (comparer.Compare(k,k2) = 0)
          | MapNode(k2,_,l,r,_) ->
              let c = comparer.Compare(k,k2)
              if c < 0 then mem comparer k l
              else (c = 0 || mem comparer k r)
  
      let rec iter f m =
          match m with
          | MapEmpty -> ()
          | MapOne(k2,v2) -> f k2 v2
          | MapNode(k2,v2,l,r,_) -> iter f l; f k2 v2; iter f r
  
      let rec tryPick f m =
          match m with
          | MapEmpty -> None
          | MapOne(k2,v2) -> f k2 v2
          | MapNode(k2,v2,l,r,_) ->
              match tryPick f l with
              | Some _ as res -> res
              | None ->
                  match f k2 v2 with
                  | Some _ as res -> res
                  | None ->
                      tryPick f r
  
      let rec exists f m =
          match m with
          | MapEmpty -> false
          | MapOne(k2,v2) -> f k2 v2
          | MapNode(k2,v2,l,r,_) -> exists f l || f k2 v2 || exists f r
  
      let rec forall f m =
          match m with
          | MapEmpty -> true
          | MapOne(k2,v2) -> f k2 v2
          | MapNode(k2,v2,l,r,_) -> forall f l && f k2 v2 && forall f r
  
      let rec map f m =
          match m with
          | MapEmpty -> empty
          | MapOne(k,v) -> MapOne(k,f v)
          | MapNode(k,v,l,r,h) ->
              let l2 = map f l
              let v2 = f v
              let r2 = map f r
              MapNode(k,v2,l2, r2,h)
  
      let rec mapi f m =
          match m with
          | MapEmpty -> empty
          | MapOne(k,v) -> MapOne(k,f k v)
          | MapNode(k,v,l,r,h) ->
              let l2 = mapi f l
              let v2 = f k v
              let r2 = mapi f r
              MapNode(k,v2, l2, r2,h)
  
      let rec foldBack (f:OptimizedClosures.FSharpFunc<_,_,_,_>) m x =
          match m with
          | MapEmpty -> x
          | MapOne(k,v) -> f.Invoke(k,v,x)
          | MapNode(k,v,l,r,_) ->
              let x = foldBack f r x
              let x = f.Invoke(k,v,x)
              foldBack f l x
  
      let rec fold (f:OptimizedClosures.FSharpFunc<_,_,_,_>) x m  =
          match m with
          | MapEmpty -> x
          | MapOne(k,v) -> f.Invoke(x,k,v)
          | MapNode(k,v,l,r,_) ->
              let x = fold f x l
              let x = f.Invoke(x,k,v)
              fold f x r
  
      let rec foldFromTo (comparer: IComparer<'Value>) lo hi f m x =
          match m with
          | MapEmpty -> x
          | MapOne(k,v) ->
              let cLoKey = comparer.Compare(lo,k)
              let cKeyHi = comparer.Compare(k,hi)
              let x = if cLoKey <= 0 && cKeyHi <= 0 then f k v x else x
              x
          | MapNode(k,v,l,r,_) ->
              let cLoKey = comparer.Compare(lo,k)
              let cKeyHi = comparer.Compare(k,hi)
              let x = if cLoKey < 0                then foldFromTo comparer lo hi f l x else x
              let x = if cLoKey <= 0 && cKeyHi <= 0 then f k v x                     else x
              let x = if cKeyHi < 0                then foldFromTo comparer lo hi f r x else x
              x
  
      let foldSection (comparer: IComparer<'Value>) lo hi f m x =
          if comparer.Compare(lo,hi) = 1 then x else foldFromTo comparer lo hi f m x
  
      let rec loop m acc =
          match m with
          | MapEmpty -> acc
          | MapOne(k,v) -> (k,v)::acc
          | MapNode(k,v,l,r,_) -> loop l ((k,v)::loop r acc)
  
      let toList m =
          loop m []
  
      let toArray m = m |> toList |> Array.ofList
  
      let ofList comparer l = List.fold (fun acc (k,v) -> add comparer k v acc) empty l
  
      let rec mkFromEnumerator comparer acc (e : IEnumerator<_>) =
          if e.MoveNext() then
              let (x,y) = e.Current
              mkFromEnumerator comparer (add comparer x y acc) e
          else acc
  
      let ofArray comparer (arr : array<_>) =
          let mutable res = empty
          for i = 0 to arr.Length - 1 do
              let x,y = arr.[i]
              res <- add comparer x y res
          res
  
      let ofSeq comparer (c : seq<'Key * 'T>) =
      //      match c with
      //      | :? array<'Key * 'T> as xs -> ofArray comparer xs
      //      | :? list<'Key * 'T> as xs -> ofList comparer xs
      //      | _ ->
          use ie = c.GetEnumerator()
          mkFromEnumerator comparer empty ie
  
  
      let copyToArray s (arr: _[]) i =
          let j = ref i
          s |> iter (fun x y -> arr.[!j] <- KeyValuePair(x,y); j := !j + 1)
  
  
      /// Imperative left-to-right iterators.
      [<NoEquality; NoComparison>]
      type MapIterator<'Key,'Value when 'Key : comparison > =
          { /// invariant: always collapseLHS result
            mutable stack: MapTree<'Key,'Value> list;
            /// true when MoveNext has been called
            mutable started : bool }
  
      // collapseLHS:
      // a) Always returns either [] or a list starting with MapOne.
      // b) The "fringe" of the set stack is unchanged.
      let rec collapseLHS stack =
          match stack with
          | []                           -> []
          | MapEmpty             :: rest -> collapseLHS rest
          | MapOne _         :: _ -> stack
          | (MapNode(k,v,l,r,_)) :: rest -> collapseLHS (l :: MapOne (k,v) :: r :: rest)
  
      let mkIterator s = { stack = collapseLHS [s]; started = false }
  
      let notStarted() = failwith "enumeration not started"
  
      let alreadyFinished() = failwith "enumeration already finished"
  
      let current i =
          if i.started then
              match i.stack with
              | MapOne (k,v) :: _ -> KeyValuePair<_,_>(k,v)
              | []            -> alreadyFinished()
              | _             -> failwith "Please report error: Map iterator, unexpected stack for current"
          else
              notStarted()
  
      let rec moveNext i =
          if i.started then
              match i.stack with
              | MapOne _ :: rest ->
                  i.stack <- collapseLHS rest
                  not i.stack.IsEmpty
              | [] -> false
              | _ -> failwith "Please report error: Map iterator, unexpected stack for moveNext"
          else
              i.started <- true;  (* The first call to MoveNext "starts" the enumeration. *)
              not i.stack.IsEmpty
  
      type mkIEnumerator'<'Key,'Value when 'Key: comparison>(s) =
          let i = ref (mkIterator s)
          interface IEnumerator<KeyValuePair<'Key,'Value>> with
              member __.Current = current !i
          interface System.Collections.IEnumerator with
              member __.Current = box (current !i)
              member __.MoveNext() = moveNext !i
              member __.Reset() = i :=  mkIterator s
          interface System.IDisposable with
              member __.Dispose() = ()
  
      let mkIEnumerator s = new mkIEnumerator'<_,_>(s) :> _ IEnumerator
  
  [<CompiledName("FSharpMap")>]
  type Map<[<EqualityConditionalOn>]'Key,[<EqualityConditionalOn;ComparisonConditionalOn>]'Value when 'Key : comparison >
          (comparer: IComparer<'Key>, tree: MapTree<'Key,'Value>) =
  
      [<System.NonSerialized>]
      // This type is logically immutable. This field is only mutated during deserialization.
      let mutable comparer = comparer
  
      [<System.NonSerialized>]
      // This type is logically immutable. This field is only mutated during deserialization.
      let mutable tree = tree
  
      static member Empty : Map<'Key,'Value> =
          let comparer = GenericComparer<'Key>()
          new Map<'Key,'Value>(comparer,MapTree<_,_>.MapEmpty)
  
      static member Create(ie : IEnumerable<_>) : Map<'Key,'Value> =
          let comparer = GenericComparer<'Key>()
          new Map<_,_>(comparer,MapTree.ofSeq comparer ie)
  
      static member Create() : Map<'Key,'Value> = Map.Empty
  
      static member From(ie : seq<_>) =
          let comparer = GenericComparer<'Key>()
          new Map<_,_>(comparer,MapTree.ofSeq comparer ie)
  
      member internal __.Comparer = comparer
      //[<DebuggerBrowsable(DebuggerBrowsableState.Never)>]
      member internal __.Tree = tree
      member __.Add(k,v) : Map<'Key,'Value> =
          new Map<'Key,'Value>(comparer,MapTree.add comparer k v tree)
      member __.IsEmpty = MapTree.isEmpty tree
      member __.Item
          with get(k : 'Key) =
              MapTree.find comparer k tree
      member __.TryPick(f) = MapTree.tryPick f tree
      member __.Exists(f) = MapTree.exists f tree
      member __.Filter(f)  : Map<'Key,'Value> = new Map<'Key,'Value>(comparer ,MapTree.filter comparer f tree)
      member __.ForAll(f) = MapTree.forall f tree
      member __.Fold f acc =
          let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
          MapTree.foldBack f tree acc
  
      member __.FoldSection (lo:'Key) (hi:'Key) f (acc:'z) = MapTree.foldSection comparer lo hi f tree acc
  
      member __.Iterate f = MapTree.iter f tree
  
      member __.MapRange f  = new Map<'Key,'b>(comparer,MapTree.map f tree)
  
      member __.Map f  = new Map<'Key,'b>(comparer,MapTree.mapi f tree)
  
      member __.Partition(f)  : Map<'Key,'Value> * Map<'Key,'Value> =
          let r1,r2 = MapTree.partition comparer f tree  in
          new Map<'Key,'Value>(comparer,r1), new Map<'Key,'Value>(comparer,r2)
  
      member __.Count = MapTree.size tree
  
      member __.ContainsKey(k) =
          MapTree.mem comparer k tree
  
      member __.Remove(k)  : Map<'Key,'Value> =
          new Map<'Key,'Value>(comparer,MapTree.remove comparer k tree)
  
      member __.TryFind(k) =
          MapTree.tryFind comparer k tree
  
      member __.ToList() = MapTree.toList tree
  
      member __.ToArray() = MapTree.toArray tree
  
      static member ofList(l) : Map<'Key,'Value> =
          let comparer = GenericComparer<'Key>()
          new Map<_,_>(comparer,MapTree.ofList comparer l)
  
      //        member this.ComputeHashCode() =
      //            let combineHash x y = (x <<< 1) + y + 631
      //            let mutable res = 0
      //            for (KeyValue(x,y)) in this do
      //                res <- combineHash res (hash x)
      //                res <- combineHash res (Unchecked.hash y)
      //            abs res
  
      override __.Equals(that) = false
      //            match that with
      //            | :? Map<'Key,'Value> as that ->
      //                use e1 = (this :> seq<_>).GetEnumerator()
      //                use e2 = (that :> seq<_>).GetEnumerator()
      //                let rec loop () =
      //                    let m1 = e1.MoveNext()
      //                    let m2 = e2.MoveNext()
      //                    (m1 = m2) && (not m1 || ((e1.Current.Key = e2.Current.Key) && (Unchecked.equals e1.Current.Value e2.Current.Value) && loop()))
      //                loop()
      //            | _ -> false
  
      override __.GetHashCode() = 0//this.ComputeHashCode()
  
      interface IEnumerable<KeyValuePair<'Key, 'Value>> with
          member __.GetEnumerator() = MapTree.mkIEnumerator tree
  
      interface System.Collections.IEnumerable with
          member __.GetEnumerator() = (MapTree.mkIEnumerator tree :> System.Collections.IEnumerator)
  
  
      interface System.IComparable with
          member m.CompareTo(obj: obj) =
              let m2 = obj :?> Map<'Key,'Value>
              Seq.compareWith
                  (fun (kvp1 : KeyValuePair<_,_>)
                      (kvp2 : KeyValuePair<_,_>)->
                          let c = comparer.Compare(kvp1.Key,kvp2.Key) in
                          if c <> 0 then c else Unchecked.compare kvp1.Value kvp2.Value)
                  m m2
  
  [<CompiledName("IsEmpty")>]
  let isEmpty (m:Map<_,_>) = m.IsEmpty
  