mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.Analysis.Numerical/GenericExpressionVisitor.cs

   1 //
   2 // GenericExpressionVisitor.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2012 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
  31 using Mono.CodeContracts.Static.DataStructures;
  32
  33 using Op = Mono.CodeContracts.Static.Analysis.Numerical.ExpressionOperator;
  34
  35 namespace Mono.CodeContracts.Static.Analysis.Numerical {
  36         abstract class GenericExpressionVisitor<In, Out, Var, Expr> {
  37                 protected readonly IExpressionDecoder<Var, Expr> Decoder;
  38
  39                 protected GenericExpressionVisitor (IExpressionDecoder<Var, Expr> decoder)
  40                 {
  41                         Decoder = decoder;
  42                 }
  43
  44                 public virtual Out Visit (Expr expr, In data)
  45                 {
  46                         var op = Decoder.OperatorFor (expr);
  47                         switch (op) {
  48                         case Op.Constant:
  49                                 return VisitConstant (expr, data);
  50                         case Op.Variable:
  51                                 return VisitVariable (Decoder.UnderlyingVariable (expr), expr, data);
  52                         case Op.Not:
  53                                 return DispatchVisitNot (Decoder.LeftExpressionFor (expr), data);
  54                         case Op.And:
  55                                 return VisitAnd (Decoder.LeftExpressionFor (expr), Decoder.RightExpressionFor (expr),
  56                                                  expr, data);
  57                         case Op.Or:
  58                                 return VisitOr (Decoder.LeftExpressionFor (expr), Decoder.RightExpressionFor (expr),
  59                                                 expr, data);
  60                         case Op.Xor:
  61                                 return VisitXor (Decoder.LeftExpressionFor (expr), Decoder.RightExpressionFor (expr),
  62                                                  expr, data);
  63                         case Op.LogicalAnd:
  64                                 return VisitLogicalAnd (Decoder.LeftExpressionFor (expr),
  65                                                         Decoder.RightExpressionFor (expr), expr, data);
  66                         case Op.LogicalOr:
  67                                 return VisitLogicalOr (Decoder.LeftExpressionFor (expr),
  68                                                        Decoder.RightExpressionFor (expr), expr, data);
  69                         case Op.NotEqual:
  70                                 return VisitNotEqual (Decoder.LeftExpressionFor (expr),
  71                                                       Decoder.RightExpressionFor (expr), expr, data);
  72
  73                         case Op.Equal:
  74                         case Op.Equal_Obj:
  75                                 return DispatchVisitEqual (op, Decoder.LeftExpressionFor (expr),
  76                                                            Decoder.RightExpressionFor (expr), expr, data);
  77
  78                         case Op.LessThan:
  79                                 return DispatchCompare (VisitLessThan, Decoder.LeftExpressionFor (expr),
  80                                                         Decoder.RightExpressionFor (expr), expr, data);
  81                         case Op.LessEqualThan:
  82                                 return DispatchCompare (VisitLessEqualThan, Decoder.LeftExpressionFor (expr),
  83                                                         Decoder.RightExpressionFor (expr), expr, data);
  84                         case Op.GreaterThan:
  85                                 return DispatchCompare (VisitGreaterThan, Decoder.LeftExpressionFor (expr),
  86                                                         Decoder.RightExpressionFor (expr), expr, data);
  87                         case Op.GreaterEqualThan:
  88                                 return DispatchCompare (VisitGreaterEqualThan, Decoder.LeftExpressionFor (expr),
  89                                                         Decoder.RightExpressionFor (expr), expr, data);
  90
  91                         case Op.Add:
  92                                 return VisitAddition (Decoder.LeftExpressionFor (expr),
  93                                                       Decoder.RightExpressionFor (expr), expr, data);
  94                         case Op.Div:
  95                                 return VisitDivision (Decoder.LeftExpressionFor (expr),
  96                                                       Decoder.RightExpressionFor (expr), expr, data);
  97                         case Op.Sub:
  98                                 return VisitSubtraction (Decoder.LeftExpressionFor (expr),
  99                                                          Decoder.RightExpressionFor (expr), expr, data);
 100                         case Op.Mod:
 101                                 return VisitModulus (Decoder.LeftExpressionFor (expr), Decoder.RightExpressionFor (expr),
 102                                                      expr, data);
 103                         case Op.Mult:
 104                                 return VisitMultiply (Decoder.LeftExpressionFor (expr),
 105                                                       Decoder.RightExpressionFor (expr), expr, data);
 106
 107                         case Op.SizeOf:
 108                                 return VisitSizeOf (Decoder.LeftExpressionFor (expr), data);
 109                         case Op.UnaryMinus:
 110                                 return VisitUnaryMinus (Decoder.LeftExpressionFor (expr), expr, data);
 111                         case Op.LogicalNot:
 112                                 return VisitLogicalNot (Decoder.LeftExpressionFor (expr), expr, data);
 113                         case Op.Unknown:
 114                                 return VisitUnknown (expr, data);
 115                         default:
 116                                 throw new ArgumentOutOfRangeException ();
 117                         }
 118                 }
 119
 120                 public virtual Out VisitVariable (Var var, Expr expr, In data)
 121                 {
 122                         return Default (data);
 123                 }
 124
 125                 public virtual Out VisitConstant (Expr expr, In data)
 126                 {
 127                         return Default (data);
 128                 }
 129
 130                 public virtual Out VisitLogicalNot (Expr left, Expr original, In data)
 131                 {
 132                         return Default (data);
 133                 }
 134
 135                 public virtual Out VisitUnaryMinus (Expr left, Expr original, In data)
 136                 {
 137                         return Default (data);
 138                 }
 139
 140                 public virtual Out VisitNot (Expr expr, In data)
 141                 {
 142                         return Default (data);
 143                 }
 144
 145                 public virtual Out VisitSizeOf (Expr expr, In data)
 146                 {
 147                         return Default (data);
 148                 }
 149
 150                 public virtual Out VisitUnknown (Expr expr, In data)
 151                 {
 152                         return Default (data);
 153                 }
 154
 155                 public virtual Out VisitLessThan (Expr left, Expr right, Expr original, In data)
 156                 {
 157                         return Default (data);
 158                 }
 159
 160                 public virtual Out VisitLessEqualThan (Expr left, Expr right, Expr original, In data)
 161                 {
 162                         return Default (data);
 163                 }
 164
 165                 public virtual Out VisitGreaterThan (Expr left, Expr right, Expr original, In data)
 166                 {
 167                         return DispatchCompare (VisitLessEqualThan, right, left, original, data);
 168                 }
 169
 170                 public virtual Out VisitGreaterEqualThan (Expr left, Expr right, Expr original, In data)
 171                 {
 172                         return DispatchCompare (VisitLessThan, right, left, original, data);
 173                 }
 174
 175                 public virtual Out VisitNotEqual (Expr left, Expr right, Expr original, In data)
 176                 {
 177                         return Default (data);
 178                 }
 179
 180                 public virtual Out VisitAddition (Expr left, Expr right, Expr original, In data)
 181                 {
 182                         return Default (data);
 183                 }
 184
 185                 public virtual Out VisitSubtraction (Expr left, Expr right, Expr original, In data)
 186                 {
 187                         return Default (data);
 188                 }
 189
 190                 public virtual Out VisitMultiply (Expr left, Expr right, Expr original, In data)
 191                 {
 192                         return Default (data);
 193                 }
 194
 195                 public virtual Out VisitModulus (Expr left, Expr right, Expr original, In data)
 196                 {
 197                         return Default (data);
 198                 }
 199
 200                 public virtual Out VisitDivision (Expr left, Expr right, Expr original, In data)
 201                 {
 202                         return Default (data);
 203                 }
 204
 205                 public virtual Out VisitEqual (Expr left, Expr right, Expr original, In data)
 206                 {
 207                         return Default (data);
 208                 }
 209
 210                 public virtual Out VisitLogicalOr (Expr left, Expr right, Expr original, In data)
 211                 {
 212                         return Default (data);
 213                 }
 214
 215                 public virtual Out VisitLogicalAnd (Expr left, Expr right, Expr original, In data)
 216                 {
 217                         return Default (data);
 218                 }
 219
 220                 public virtual Out VisitXor (Expr left, Expr right, Expr original, In data)
 221                 {
 222                         return Default (data);
 223                 }
 224
 225                 public virtual Out VisitOr (Expr left, Expr right, Expr original, In data)
 226                 {
 227                         return Default (data);
 228                 }
 229
 230                 public virtual Out VisitAnd (Expr left, Expr right, Expr original, In data)
 231                 {
 232                         return Default (data);
 233                 }
 234
 235                 protected virtual bool TryPolarity (Expr expr, In data, out bool shouldNegate)
 236                 {
 237                         if (Decoder.IsConstant (expr)) {
 238                                 int intValue;
 239                                 if (Decoder.TryValueOf (expr, ExpressionType.Int32, out intValue))
 240                                         return true.With (intValue == 0, out shouldNegate);
 241
 242                                 bool boolValue;
 243                                 if (Decoder.TryValueOf (expr, ExpressionType.Bool, out boolValue))
 244                                         return true.With (boolValue, out shouldNegate);
 245                         }
 246
 247                         return false.Without (out shouldNegate);
 248                 }
 249
 250                 protected delegate Out CompareVisitor (Expr left, Expr right, Expr original, In data);
 251
 252                 protected virtual Out DispatchCompare (CompareVisitor cmp, Expr left, Expr right, Expr original, In data)
 253                 {
 254                         if (Decoder.IsConstant (left) && Decoder.OperatorFor (right) == ExpressionOperator.Sub)
 255                                 // const OP (a - b)
 256                         {
 257                                 int num;
 258                                 if (Decoder.TryValueOf (left, ExpressionType.Int32, out num) && num == 0)
 259                                         // 0 OP (a-b) ==> b OP a
 260                                         return cmp (Decoder.RightExpressionFor (right),
 261                                                     Decoder.LeftExpressionFor (right), right, data);
 262                         }
 263                         else if (Decoder.IsConstant (right) && Decoder.OperatorFor (left) == ExpressionOperator.Sub)
 264                                 // (a-b) OP const
 265                         {
 266                                 int num;
 267                                 if (Decoder.TryValueOf (right, ExpressionType.Int32, out num) && num == 0)
 268                                         // (a-b) OP 0 ==> a OP b
 269                                         return cmp (Decoder.LeftExpressionFor (left),
 270                                                     Decoder.RightExpressionFor (left), left, data);
 271                         }
 272
 273                         return cmp (left, right, original, data);
 274                 }
 275
 276                 protected abstract Out Default (In data);
 277
 278                 Out DispatchVisitNot (Expr expr, In data)
 279                 {
 280                         switch (Decoder.OperatorFor (expr)) {
 281                         case ExpressionOperator.Equal:
 282                         case ExpressionOperator.Equal_Obj:
 283                                 return VisitNotEqual (Decoder.LeftExpressionFor (expr),
 284                                                       Decoder.RightExpressionFor (expr), expr, data);
 285                         case ExpressionOperator.LessThan: // a < b ==>  b <= a
 286                                 return DispatchCompare (VisitLessEqualThan, Decoder.RightExpressionFor (expr),
 287                                                         Decoder.LeftExpressionFor (expr), expr, data);
 288                         case ExpressionOperator.LessEqualThan: // a <= b ==> b < a
 289                                 return DispatchCompare (VisitLessThan, Decoder.LeftExpressionFor (expr),
 290                                                         Decoder.RightExpressionFor (expr), expr, data);
 291                         case ExpressionOperator.GreaterThan: // a > b ==> b < a
 292                                 return DispatchCompare (VisitLessThan, Decoder.RightExpressionFor (expr),
 293                                                         Decoder.LeftExpressionFor (expr), expr, data);
 294                         case ExpressionOperator.GreaterEqualThan: // a >= b ==> b <= a
 295                                 return DispatchCompare (VisitLessEqualThan, Decoder.RightExpressionFor (expr),
 296                                                         Decoder.LeftExpressionFor (expr), expr, data);
 297                         default:
 298                                 return VisitNot (expr, data);
 299                         }
 300                 }
 301
 302                 Out DispatchVisitEqual (ExpressionOperator eqKind, Expr left, Expr right, Expr original, In data)
 303                 {
 304                         // { left :eq: right }
 305                         switch (Decoder.OperatorFor (left)) {
 306                         case Op.GreaterEqualThan:
 307                         case Op.GreaterThan:
 308                         case Op.LessThan:
 309                         case Op.LessEqualThan:
 310                         case Op.Equal:
 311                         case Op.Equal_Obj:
 312                                 // { ( a ?= b ) :eq: right }
 313                                 bool shouldNegate;
 314                                 if (TryPolarity (right, data, out shouldNegate))
 315                                         // { (a ?= b) :eq: true => (a ?= b) }; (a ?= b) :eq: false => !(a ?= b) }
 316                                         return shouldNegate ? DispatchVisitNot (left, data) : Visit (left, data);
 317                                 break;
 318                         }
 319
 320                         switch (Decoder.OperatorFor (right)) {
 321                         case Op.GreaterEqualThan:
 322                         case Op.GreaterThan:
 323                         case Op.LessThan:
 324                         case Op.LessEqualThan:
 325                         case Op.Equal:
 326                         case Op.Equal_Obj:
 327                                 // { left :eq: (a ?= b) }
 328                                 bool shouldNegate;
 329                                 if (TryPolarity (left, data, out shouldNegate))
 330                                         // { true :eq: (a ?= b) => (a ?= b) }; false :eq: (a ?= b) => !(a ?= b) }
 331                                         return shouldNegate ? DispatchVisitNot (right, data) : Visit (right, data);
 332                                 break;
 333                         }
 334
 335                         return VisitEqual (left, right, original, data);
 336                 }
 337         }
 338 }