mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.Analysis.HeapAnalysis.SymbolicGraph/MergeInfo.cs

   1 //
   2 // MergeInfo.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2011 Alexander Chebaturkin
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections.Generic;
  31 using System.Linq;
  32 using Mono.CodeContracts.Static.DataStructures;
  33 using Mono.CodeContracts.Static.Extensions;
  34
  35 namespace Mono.CodeContracts.Static.Analysis.HeapAnalysis.SymbolicGraph {
  36         class MergeInfo<TFunc, TADomain> : IMergeInfo
  37                 where TFunc : IEquatable<TFunc>, IConstantInfo
  38                 where TADomain : IAbstractDomainForEGraph<TADomain>, IEquatable<TADomain> {
  39
  40                 public readonly SymGraph<TFunc, TADomain> Result;
  41                 public readonly SymGraph<TFunc, TADomain> Graph1;
  42                 public readonly SymGraph<TFunc, TADomain> Graph2;
  43
  44                 public readonly int LastCommonVariable;
  45                 public readonly bool Widen;
  46
  47                 private readonly HashSet<SymValue> manifested;
  48                 private readonly DoubleDictionary<SymValue, SymValue, int> pending_counts;
  49                 private readonly HashSet<Tuple<SymValue, SymValue, MultiEdge<TFunc, TADomain>>> visited_multi_edges;
  50
  51                 private DoubleImmutableMap<SymValue, SymValue, SymValue> mappings;
  52                 private IImmutableSet<SymValue> visited_key1;
  53                 private LispList<Tuple<SymValue, SymValue, SymValue>> merge_triples;
  54
  55                 public MergeInfo (SymGraph<TFunc, TADomain> result,
  56                                   SymGraph<TFunc, TADomain> g1,
  57                                   SymGraph<TFunc, TADomain> g2, bool widen)
  58                 {
  59                         this.mappings = DoubleImmutableMap<SymValue, SymValue, SymValue>.Empty (SymValue.GetUniqueKey);
  60                         this.visited_key1 = ImmutableSet<SymValue>.Empty (SymValue.GetUniqueKey);
  61                         this.visited_multi_edges = new HashSet<Tuple<SymValue, SymValue, MultiEdge<TFunc, TADomain>>> ();
  62                         this.pending_counts = new DoubleDictionary<SymValue, SymValue, int> ();
  63                         this.manifested = new HashSet<SymValue> ();
  64
  65                         this.LastCommonVariable = result.IdGenerator;
  66                         this.Widen = widen;
  67                         this.Result = result;
  68                         this.Graph1 = g1;
  69                         this.Graph2 = g2;
  70
  71                         this.Changed = false;
  72                 }
  73
  74                 #region IMergeInfo Members
  75                 public bool Changed { get; set; }
  76
  77                 public IEnumerable<Tuple<SymValue, SymValue, SymValue>> MergeTriples
  78                 {
  79                         get { return this.merge_triples.AsEnumerable (); }
  80                 }
  81
  82                 public IImmutableMap<SymValue, LispList<SymValue>> ForwardG1Map
  83                 {
  84                         get { return GetForwardGraphMap ((t) => t.Item1); }
  85                 }
  86
  87                 public IImmutableMap<SymValue, LispList<SymValue>> ForwardG2Map
  88                 {
  89                         get { return GetForwardGraphMap ((t) => t.Item2); }
  90                 }
  91
  92                 public bool IsResultGraph<TFunc1, TAbstractDomain> (SymGraph<TFunc1, TAbstractDomain> graph)
  93                         where TFunc1 : IEquatable<TFunc1>, IConstantInfo
  94                         where TAbstractDomain : IAbstractDomainForEGraph<TAbstractDomain>, IEquatable<TAbstractDomain>
  95                 {
  96                         return Equals (graph, this.Result);
  97                 }
  98
  99                 public bool IsGraph1<TFunc1, TAbstractDomain> (SymGraph<TFunc1, TAbstractDomain> graph)
 100                         where TFunc1 : IEquatable<TFunc1>, IConstantInfo
 101                         where TAbstractDomain : IAbstractDomainForEGraph<TAbstractDomain>, IEquatable<TAbstractDomain>
 102                 {
 103                         return (Equals (this.Graph1, graph) || Equals (this.Graph1.Parent, graph) && Equals (this.Graph1.Updates, graph.Updates));
 104                 }
 105
 106                 public bool IsGraph2<TFunc1, TAbstractDomain> (SymGraph<TFunc1, TAbstractDomain> graph)
 107                         where TFunc1 : IEquatable<TFunc1>, IConstantInfo
 108                         where TAbstractDomain : IAbstractDomainForEGraph<TAbstractDomain>, IEquatable<TAbstractDomain>
 109                 {
 110                         return (Equals (this.Graph2, graph) || Equals (this.Graph2.Parent, graph) && Equals (this.Graph2.Updates, graph.Updates));
 111                 }
 112                 #endregion
 113
 114                 public void AddMapping (SymValue v1, SymValue v2, SymValue result)
 115                 {
 116                         if (v1 != null && v2 != null)
 117                                 this.mappings = this.mappings.Add (v1, v2, result);
 118                         else if (v2 == null)
 119                                 this.visited_key1 = this.visited_key1.Add (v1);
 120                         else
 121                                 this.visited_key1 = this.visited_key1.Add (v2);
 122
 123                         AddMergeTriple (v1, v2, result);
 124                 }
 125
 126                 public SymValue AddJointEdge (SymValue v1Target, SymValue v2Target, TFunc function, SymValue resultArg)
 127                 {
 128                         SymValue result = LookupMapping (v1Target, v2Target);
 129                         bool newEdge = false;
 130                         if (result == null)
 131                         {
 132                                 if (IsMappingAlreadyAdded (v1Target, v2Target))
 133                                 {
 134                                         if (DebugOptions.Debug)
 135                                                 Console.WriteLine ("---SymGraph changed due to pre-existing mapping in G1 of {0}", v1Target);
 136                                         Changed = true;
 137                                         if (v1Target == null)
 138                                         {
 139                                                 if (this.manifested.Contains (v2Target))
 140                                                         return null;
 141                                                 this.manifested.Add (v2Target);
 142                                         }
 143                                         if (v2Target == null)
 144                                         {
 145                                                 if (this.manifested.Contains (v1Target))
 146                                                         return null;
 147                                                 this.manifested.Add (v1Target);
 148                                         }
 149                                 }
 150                                 newEdge = true;
 151                                 result = v1Target == null || v1Target.UniqueId > this.LastCommonVariable || v1Target != v2Target ? this.Result.FreshSymbol () : v1Target;
 152                                 AddMapping (v1Target, v2Target, result);
 153                         }
 154                         else if (this.Result.LookupWithoutManifesting (resultArg, function) == result)
 155                                 return null;
 156                         this.Result[function, resultArg] = result;
 157                         TADomain val1 = Graph1ADomain (v1Target);
 158                         TADomain val2 = Graph2ADomain (v2Target);
 159
 160                         bool weaker;
 161                         TADomain join = val1.Join (val2, this.Widen, out weaker);
 162                         this.Result[result] = join;
 163
 164                         if (weaker)
 165                         {
 166                                 if (DebugOptions.Debug)
 167                                 {
 168                                         Console.WriteLine ("----SymGraph changed due to join of abstract values of [{0}, {1}] " +
 169                                                            "(prev {2}, new {3}, join {4}", v1Target, v2Target, val1, val2, join);
 170                                 }
 171                                 Changed = true;
 172                         }
 173
 174                         return newEdge ? result : null;
 175                 }
 176
 177                 public SymValue AddJointEdge (SymValue v1Target, SymValue v2Target, TFunc function, SymValue[] resultArgs)
 178                 {
 179                         SymValue result = LookupMapping (v1Target, v2Target);
 180                         bool newEdge = false;
 181                         if (result == null)
 182                         {
 183                                 if (IsMappingAlreadyAdded (v1Target, v2Target))
 184                                 {
 185                                         if (DebugOptions.Debug)
 186                                                 Console.WriteLine ("---SymGraph changed due to pre-existing mapping in G1 of {0}", v1Target);
 187                                         Changed = true;
 188                                         if (v1Target == null || v2Target == null)
 189                                                 return null;
 190                                 }
 191                                 newEdge = true;
 192                                 result = v1Target == null || v1Target.UniqueId > this.LastCommonVariable || v1Target != v2Target ? this.Result.FreshSymbol () : v1Target;
 193                                 AddMapping (v1Target, v2Target, result);
 194                         }
 195                         else if (this.Result.LookupWithoutManifesting (resultArgs, function) == result)
 196                                 return null;
 197                         this.Result[resultArgs, function] = result;
 198                         TADomain val1 = Graph1ADomain (v1Target);
 199                         TADomain val2 = Graph2ADomain (v2Target);
 200
 201                         bool weaker;
 202                         TADomain joinValue = val1.Join (val2, this.Widen, out weaker);
 203
 204                         this.Result[result] = joinValue;
 205                         if (weaker)
 206                         {
 207                                 if (DebugOptions.Debug)
 208                                         Console.WriteLine ("----SymGraph changed due to join of abstract values of [{0}, {1}] (prev {2}, new {3}, join {4}",
 209                                                            v1Target, v2Target,
 210                                                            val1, val2, joinValue);
 211                                 Changed = true;
 212                         }
 213
 214                         if (DebugOptions.Debug)
 215                         {
 216                                 Console.WriteLine ("AddJointEdge: ({0}) -{1} -> [{2},{3},{4}]",
 217                                                    resultArgs.ToString (", "), function,
 218                                                    v1Target, v2Target, result);
 219                         }
 220                         return newEdge ? result : null;
 221                 }
 222
 223                 public bool IsCommon (SymValue sv)
 224                 {
 225                         return sv.UniqueId <= this.LastCommonVariable;
 226                 }
 227
 228                 public bool AreCommon (SymValue[] svs)
 229                 {
 230                         return svs.All (sv => IsCommon (sv));
 231                 }
 232
 233                 public void JoinSymbolicValue (SymValue sv1, SymValue sv2, SymValue r)
 234                 {
 235                         if (this.Graph2.HasAllBottomFields (sv2)) {
 236                                 if (sv1 != null) {
 237                                         foreach (TFunc function in this.Graph1.TermMap.Keys2 (sv1)) {
 238                                                 SymValue v1 = this.Graph1.LookupWithoutManifesting (sv1, function);
 239                                                 bool isPlaceHolder;
 240                                                 SymValue v2 = this.Graph2.LookupOrBottomPlaceHolder (sv2, function, out isPlaceHolder);
 241                                                 if (!isPlaceHolder || function.KeepAsBottomField) {
 242                                                         SymValue r1 = AddJointEdge (v1, v2, function, r);
 243                                                         if (r1 != null)
 244                                                                 JoinSymbolicValue (v1, v2, r1);
 245                                                 }
 246                                         }
 247                                 }
 248                         } else if (!this.Widen && this.Graph1.HasAllBottomFields (sv1)) {
 249                                 if (DebugOptions.Debug)
 250                                         Console.WriteLine ("---SymGraph changed due to an all bottom field value in G1 changing to non-bottom");
 251                                 Changed = true;
 252                                 if (sv2 != null) {
 253                                         foreach (TFunc function in this.Graph2.TermMap.Keys2 (sv2)) {
 254                                                 bool isPlaceHolder;
 255                                                 SymValue v1 = this.Graph1.LookupOrBottomPlaceHolder (sv1, function, out isPlaceHolder);
 256                                                 SymValue v2 = this.Graph2.LookupWithoutManifesting (sv2, function);
 257                                                 if (!isPlaceHolder || function.KeepAsBottomField) {
 258                                                         SymValue r1 = AddJointEdge (v1, v2, function, r);
 259                                                         if (r1 != null)
 260                                                                 JoinSymbolicValue (v1, v2, r1);
 261                                                 }
 262                                         }
 263                                 }
 264                         } else {
 265                                 IEnumerable<TFunc> functions;
 266                                 if (this.Widen) {
 267                                         if (this.Graph1.TermMap.Keys2Count (sv1) <= this.Graph2.TermMap.Keys2Count (sv2))
 268                                                 functions = this.Graph1.TermMap.Keys2 (sv1);
 269                                         else {
 270                                                 functions = this.Graph2.TermMap.Keys2 (sv2);
 271                                                 if (DebugOptions.Debug)
 272                                                         Console.WriteLine ("---SymGraph changed because G2 has fewer keys for {0} than {1} in G1", sv2, sv1);
 273                                                 Changed = true;
 274                                         }
 275                                 } else {
 276                                         if (this.Graph1.TermMap.Keys2Count (sv1) < this.Graph2.TermMap.Keys2Count (sv2)) {
 277                                                 functions = this.Graph2.TermMap.Keys2 (sv2);
 278                                                 if (DebugOptions.Debug)
 279                                                         Console.WriteLine ("---SymGraph changed because G1 has fewer keys for {0} than {1} in G2", sv1, sv2);
 280                                                 Changed = true;
 281                                         } else
 282                                                 functions = this.Graph1.TermMap.Keys2 (sv1);
 283                                 }
 284
 285                                 foreach (TFunc function in functions) {
 286                                         SymValue v1 = this.Graph1.LookupWithoutManifesting (sv1, function);
 287                                         SymValue v2 = this.Graph2.LookupWithoutManifesting (sv2, function);
 288
 289                                         if (v1 == null) {
 290                                                 if (!this.Widen && function.ManifestField) {
 291                                                         if (DebugOptions.Debug)
 292                                                                 Console.WriteLine ("---SymGraph changed due to manifestation of a top edge in G1");
 293                                                         Changed = true;
 294
 295                                                 } else
 296                                                         continue;
 297                                         }
 298                                         if (v2 == null && (this.Widen || !function.ManifestField)) {
 299                                                 if (DebugOptions.Debug)
 300                                                         Console.WriteLine ("---SymGraph changed due to absence of map {0}-{1} -> in G2", sv2, function);
 301                                                 Changed = true;
 302                                         }
 303
 304                                         if (v1 != null && v2 != null)
 305                                         {
 306                                                 //we have to joint ends of edges
 307                                                 SymValue r1 = AddJointEdge (v1, v2, function, r);
 308                                                 if (r1 != null)
 309                                                         JoinSymbolicValue (v1, v2, r1);
 310                                         }
 311                                 }
 312                         }
 313
 314                         JoinMultiEdges (sv1, sv2);
 315                 }
 316
 317                 public void JoinMultiEdge (SymValue sv1, SymValue sv2, MultiEdge<TFunc, TADomain> edge)
 318                 {
 319                         var key = new Tuple<SymValue, SymValue, MultiEdge<TFunc, TADomain>> (sv1, sv2, edge);
 320                         if (!this.visited_multi_edges.Add (key))
 321                                 return;
 322
 323                         LispList<SymValue> list1 = this.Graph1.MultiEdgeMap [sv1, edge];
 324                         LispList<SymValue> list2 = this.Graph2.MultiEdgeMap [sv2, edge];
 325                         if (list2.IsEmpty ())
 326                                 return;
 327                         foreach (SymValue v1 in list1.AsEnumerable ()) {
 328                                 foreach (SymValue v2 in list2.AsEnumerable ()) {
 329                                         if (UpdatePendingCount (v1, v2, edge.Arity)) {
 330                                                 SymGraphTerm<TFunc> term1 = this.Graph1.EqualMultiTermsMap [v1];
 331                                                 SymGraphTerm<TFunc> term2 = this.Graph2.EqualMultiTermsMap [v2];
 332                                                 if (term1.Args != null && term2.Args != null) {
 333                                                         var resultRoots = new SymValue[term1.Args.Length];
 334                                                         for (int i = 0; i < resultRoots.Length; i++)
 335                                                                 resultRoots [i] = this.mappings [term1.Args [i], term2.Args [i]];
 336                                                         SymValue r = AddJointEdge (v1, v2, edge.Function, resultRoots);
 337                                                         if (r != null)
 338                                                                 JoinSymbolicValue (sv1, sv2, r);
 339                                                 } else
 340                                                         break;
 341                                         }
 342                                 }
 343                         }
 344                 }
 345
 346                 public void Replay (SymGraph<TFunc, TADomain> common)
 347                 {
 348                         PrimeMapWithCommon ();
 349                         Replay (this.Graph1.Updates, common.Updates);
 350                         Replay (this.Graph2.Updates, common.Updates);
 351                 }
 352
 353                 public void ReplayEliminations (SymGraph<TFunc, TADomain> common)
 354                 {
 355                         ReplayEliminations (this.Graph1.Updates, common.Updates);
 356                         ReplayEliminations (this.Graph2.Updates, common.Updates);
 357                 }
 358
 359                 public void Commit ()
 360                 {
 361                         if (Changed)
 362                                 return;
 363
 364                         bool needContinue = false;
 365                         foreach (var edge in this.Graph1.ValidMultiTerms)
 366                         {
 367                                 SymGraphTerm<TFunc> term = edge.Value;
 368                                 var args = new SymValue[term.Args.Length];
 369
 370                                 for (int i = 0; i < args.Length; ++i)
 371                                 {
 372                                         SymValue sv = term.Args[i];
 373                                         if (IsMappingAlreadyAdded (sv, null))
 374                                         {
 375                                                 if (this.mappings.Keys2 (sv) != null && this.mappings.Keys2 (sv).Count () == 1)
 376                                                         args[i] = this.mappings[sv, this.mappings.Keys2 (sv).First ()];
 377                                         }
 378                                         else
 379                                         {
 380                                                 needContinue = true;
 381                                                 break;
 382                                         }
 383
 384                                         if (args[i] == null)
 385                                         {
 386                                                 Changed = true;
 387                                                 return;
 388                                         }
 389                                 }
 390
 391                                 if (needContinue)
 392                                         continue;
 393
 394                                 SymValue symbol = this.Result.LookupWithoutManifesting (args, term.Function);
 395                                 if (symbol != null)
 396                                 {
 397                                         SymValue key = edge.Key;
 398                                         if (this.mappings.Keys2 (key) != null && this.mappings.Keys2 (key).Count () == 1 && this.mappings[key, this.mappings.Keys2 (key).First ()] == symbol)
 399                                                 continue;
 400                                 }
 401
 402                                 Changed = true;
 403                                 return;
 404                         }
 405                 }
 406
 407                 private IImmutableMap<SymValue, LispList<SymValue>> GetForwardGraphMap (Func<Tuple<SymValue, SymValue, SymValue>, SymValue> sourceSelector)
 408                 {
 409                         IImmutableMap<SymValue, LispList<SymValue>> res = ImmutableIntKeyMap<SymValue, LispList<SymValue>>.Empty (SymValue.GetUniqueKey);
 410                         foreach (var tuple in this.merge_triples.AsEnumerable ()) {
 411                                 SymValue sv = sourceSelector (tuple);
 412                                 if (sv != null)
 413                                         res = res.Add (sv, res [sv].Cons (tuple.Item3));
 414                         }
 415                         return res;
 416                 }
 417
 418                 private bool UpdatePendingCount (SymValue xi, SymValue yi, int arity)
 419                 {
 420                         int result;
 421                         this.pending_counts.TryGetValue (xi, yi, out result);
 422                         result = result + 1;
 423
 424                         this.pending_counts [xi, yi] = result;
 425                         if (result == arity)
 426                                 return true;
 427
 428                         return false;
 429                 }
 430
 431                 private void JoinMultiEdges (SymValue sv1, SymValue sv2)
 432                 {
 433                         if (sv1 == null || sv2 == null)
 434                                 return;
 435
 436                         IEnumerable<MultiEdge<TFunc, TADomain>> edges =
 437                                 this.Graph1.MultiEdgeMap.Keys2Count (sv1) > this.Graph2.MultiEdgeMap.Keys2Count (sv2)
 438                                         ? this.Graph2.MultiEdgeMap.Keys2 (sv2)
 439                                         : this.Graph1.MultiEdgeMap.Keys2 (sv1);
 440                         foreach (var edge in edges)
 441                                 JoinMultiEdge (sv1, sv2, edge);
 442                 }
 443
 444                 private TADomain Graph1ADomain (SymValue sv)
 445                 {
 446                         if (sv != null)
 447                                 return this.Graph1 [sv];
 448                         return this.Graph1.UnderlyingTopValue.ForManifestedField ();
 449                 }
 450
 451                 private TADomain Graph2ADomain (SymValue sv)
 452                 {
 453                         if (sv != null)
 454                                 return this.Graph2 [sv];
 455                         return this.Graph2.UnderlyingTopValue.ForManifestedField ();
 456                 }
 457
 458                 private void AddMergeTriple (SymValue v1, SymValue v2, SymValue result)
 459                 {
 460                         this.merge_triples = this.merge_triples.Cons (new Tuple<SymValue, SymValue, SymValue> (v1, v2, result));
 461                 }
 462
 463                 private bool IsMappingAlreadyAdded (SymValue v1, SymValue v2)
 464                 {
 465                         if (v1 != null)
 466                                 return this.visited_key1.Contains (v1) || this.mappings.ContainsKey1 (v1);
 467
 468                         return this.visited_key1.Contains (v2);
 469                 }
 470
 471                 private SymValue LookupMapping (SymValue v1, SymValue v2)
 472                 {
 473                         if (v1 == null || v2 == null)
 474                                 return null;
 475
 476                         return this.mappings [v1, v2];
 477                 }
 478
 479                 private void PrimeMapWithCommon ()
 480                 {
 481                         LispList<SymValue> rest = null;
 482                         foreach (SymValue sv in this.Graph1.EqualTermsMap.Keys) {
 483                                 if (IsCommon (sv) && (this.Graph2.EqualTermsMap.ContainsKey (sv) || this.Graph2.EqualMultiTermsMap.ContainsKey (sv))) {
 484                                         if (this.Graph1.MultiEdgeMap.ContainsKey1 (sv))
 485                                                 rest = rest.Cons (sv);
 486                                         AddMapping (sv, sv, sv);
 487                                 }
 488                         }
 489                         foreach (SymValue sv in this.Graph1.EqualMultiTermsMap.Keys) {
 490                                 if (IsCommon (sv) && (this.Graph2.EqualTermsMap.ContainsKey (sv) || this.Graph2.EqualMultiTermsMap.ContainsKey (sv)) && this.mappings [sv, sv] == null) {
 491                                         if (this.Graph1.MultiEdgeMap.ContainsKey1 (sv))
 492                                                 rest = rest.Cons (sv);
 493                                         AddMapping (sv, sv, sv);
 494                                 }
 495                         }
 496                         while (rest != null) {
 497                                 SymValue sv = rest.Head;
 498                                 rest = rest.Tail;
 499                                 foreach (var edge in this.Graph1.MultiEdgeMap.Keys2 (sv))
 500                                         JoinMultiEdge (sv, sv, edge);
 501                         }
 502                 }
 503
 504                 private void Replay (LispList<Update<TFunc, TADomain>> updates, LispList<Update<TFunc, TADomain>> common)
 505                 {
 506                         for (Update<TFunc, TADomain> update = Update<TFunc, TADomain>.Reverse (updates, common); update != null; update = update.Next)
 507                                 update.Replay (this);
 508                 }
 509
 510                 private void ReplayEliminations (LispList<Update<TFunc, TADomain>> updates, LispList<Update<TFunc, TADomain>> common)
 511                 {
 512                         for (Update<TFunc, TADomain> update = Update<TFunc, TADomain>.Reverse (updates, common); update != null; update = update.Next)
 513                                 update.ReplayElimination (this);
 514                 }
 515         }
 516 }