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

   1 //
   2 // Analysis.GenericValueAnalysis.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 using System.Collections.Generic;
  31 using System.IO;
  32
  33 using Mono.CodeContracts.Static.AST;
  34 using Mono.CodeContracts.Static.AST.Visitors;
  35 using Mono.CodeContracts.Static.Analysis.Drivers;
  36 using Mono.CodeContracts.Static.ControlFlow;
  37 using Mono.CodeContracts.Static.DataFlowAnalysis;
  38 using Mono.CodeContracts.Static.DataStructures;
  39 using Mono.CodeContracts.Static.Lattices;
  40 using Mono.CodeContracts.Static.Providers;
  41 using Mono.CodeContracts.Static.Proving;
  42
  43 namespace Mono.CodeContracts.Static.Analysis.Numerical {
  44         static partial class AnalysisFacade {
  45                 static partial class Bind<TVar, TExpr> where TExpr : IEquatable<TExpr> where TVar : IEquatable<TVar> {
  46                         abstract class GenericValueAnalysis<TDomain> :
  47                                 ILVisitorBase<APC, TVar, TVar, TDomain, TDomain>,
  48                                 IAbstractAnalysis<TDomain, TVar>,
  49                                 IMethodResult<TVar>
  50                                 where TDomain : IEnvironmentDomain<TDomain, BoxedVariable<TVar>, BoxedExpression> {
  51                                 readonly IMethodDriver<TExpr, TVar> method_driver;
  52                                 //readonly string method_name;
  53
  54                                 protected ConstantEvaluator EvaluatorOfConstants;
  55
  56                                 protected IFixPointInfo<APC, TDomain> FixPointInfo;
  57                                 BoxedExpressionDecoder<TVar, TExpr> expression_decoder;
  58
  59                                 protected GenericValueAnalysis (string methodName,
  60                                                                 IMethodDriver<TExpr, TVar> methodDriver)
  61                                 {
  62                                         ThresholdDB.Reset ();
  63                                         BoxedVariable<TVar>.ResetFreshVariableCounter ();
  64
  65                                 //        method_name = methodName;
  66                                         method_driver = methodDriver;
  67
  68                                         EvaluatorOfConstants = new ConstantEvaluator (ContextProvider,
  69                                                                                       MetaDataProvider);
  70                                 }
  71
  72                                 protected IExpressionContextProvider<TExpr, TVar> ContextProvider { get { return method_driver.ContextProvider; } }
  73                                 protected IMetaDataProvider MetaDataProvider { get { return method_driver.MetaDataProvider; } }
  74
  75                                 protected BoxedExpressionDecoder<TVar, TExpr> ExpressionDecoder
  76                                 {
  77                                         get
  78                                         {
  79                                                 if (expression_decoder == null)
  80                                                         expression_decoder =
  81                                                                 new BoxedExpressionDecoder<TVar, TExpr> (
  82                                                                         new ValueExpressionDecoder<TVar, TExpr> (
  83                                                                                 MetaDataProvider,
  84                                                                                 ContextProvider));
  85                                                 return expression_decoder;
  86                                         }
  87                                 }
  88
  89                                 public IILVisitor<APC, TVar, TVar, TDomain, TDomain> GetVisitor ()
  90                                 {
  91                                         return this;
  92                                 }
  93
  94                                 public TDomain Join (Pair<APC, APC> edge, TDomain newstate, TDomain prevstate,
  95                                                      out bool weaker, bool widen)
  96                                 {
  97                                         TDomain result;
  98                                         if (!widen) {
  99                                                 result = Join (newstate, prevstate, edge);
 100                                                 weaker = true;
 101                                         }
 102                                         else {
 103                                                 result = Widen (newstate, prevstate, edge);
 104                                                 weaker = !result.LessEqual (prevstate);
 105                                         }
 106
 107                                         return result;
 108                                 }
 109
 110                                 public TDomain ImmutableVersion (TDomain arg)
 111                                 {
 112                                         return arg;
 113                                 }
 114
 115                                 public TDomain MutableVersion (TDomain arg)
 116                                 {
 117                                         return arg.Clone ();
 118                                 }
 119
 120                                 public virtual TDomain EdgeConversion (APC @from, APC to, bool isJoinPoint,
 121                                                                        IImmutableMap<TVar, Sequence<TVar>>
 122                                                                                sourceTargetMap, TDomain state)
 123                                 {
 124                                         return state;
 125                                 }
 126
 127                                 public bool IsBottom (APC pc, TDomain state)
 128                                 {
 129                                         return state.IsBottom;
 130                                 }
 131
 132                                 public Predicate<APC> SaveFixPointInfo (IFixPointInfo<APC, TDomain> fixPointInfo)
 133                                 {
 134                                         FixPointInfo = fixPointInfo;
 135                                         return a => false;
 136                                 }
 137
 138                                 public void Dump (Pair<TDomain, TextWriter> pair)
 139                                 {
 140                                         pair.Value.WriteLine (pair.Key.ToString ());
 141                                 }
 142
 143                                 public abstract TDomain TopValue ();
 144
 145                                 public TDomain BottomValue ()
 146                                 {
 147                                         return TopValue ().Bottom;
 148                                 }
 149
 150                                 public abstract IFactQuery<BoxedExpression, TVar> FactQuery (
 151                                         IFixPointInfo<APC, TDomain> fixpoint);
 152
 153                                 IFactQuery<BoxedExpression, TVar> IMethodAnalysisFixPoint<TVar>.FactQuery { get { return FactQuery (FixPointInfo); } }
 154
 155                                 public FlatDomain<bool> ValidateExplicitAssertion (APC pc, TVar value)
 156                                 {
 157                                         return FlatDomain<bool>.TopValue;
 158                                 }
 159
 160                                 public IMethodAnalysis MethodAnalysis { get; set; }
 161
 162                                 public void ValidateImplicitAssertions (IFactQuery<BoxedExpression, TVar> facts,
 163                                                                         List<string> proofResults)
 164                                 {
 165                                 }
 166
 167                                 protected virtual TDomain Widen (TDomain newState, TDomain prevState,
 168                                                                  Pair<APC, APC> edge)
 169                                 {
 170                                         return newState.Widen (prevState);
 171                                 }
 172
 173                                 protected virtual TDomain Join (TDomain newState, TDomain prevState, Pair<APC, APC> edge)
 174                                 {
 175                                         return newState.Join (prevState);
 176                                 }
 177
 178                                 public override TDomain Assume (APC pc, EdgeTag tag, TVar condition, TDomain data)
 179                                 {
 180                                         var boxed = ToBoxedExpression (pc, condition);
 181                                         if (tag != EdgeTag.False) {
 182                                                 bool value;
 183                                                 if (boxed.IsTrivialCondition (out value))
 184                                                         return !value ? data.Bottom : data;
 185                                         }
 186
 187                                         List<int> thresholds;
 188                                         if (ThresholdDB.TryGetAThreshold (boxed, expression_decoder, out thresholds))
 189                                                 ThresholdDB.Add (thresholds);
 190
 191                                         TDomain result;
 192                                         switch (tag) {
 193                                         case EdgeTag.True:
 194                                         case EdgeTag.Requires:
 195                                         case EdgeTag.Assume:
 196                                         case EdgeTag.Invariant:
 197                                                 result = data.AssumeTrue (boxed);
 198                                                 break;
 199                                         case EdgeTag.False:
 200                                                 result = data.AssumeFalse (boxed);
 201                                                 break;
 202                                         default:
 203                                                 result = data;
 204                                                 break;
 205                                         }
 206
 207                                         if (tag != EdgeTag.False) {
 208                                                 var abstractType =
 209                                                         ContextProvider.ValueContext.GetType (
 210                                                                 ContextProvider.MethodContext.CFG.Post (pc), condition);
 211                                                 if (abstractType.IsNormal () &&
 212                                                     MetaDataProvider.Equal (abstractType.Value,
 213                                                                             MetaDataProvider.System_Boolean)) {
 214                                                         var guard =
 215                                                                 BoxedExpression.Binary (BinaryOperator.Ceq, boxed,
 216                                                                                         BoxedExpression.Const (1,
 217                                                                                                                MetaDataProvider
 218                                                                                                                        .
 219                                                                                                                        System_Int32));
 220
 221                                                         result = result.AssumeTrue (guard);
 222                                                 }
 223                                         }
 224
 225                                         return result;
 226                                 }
 227
 228                                 public override TDomain Assert (APC pc, EdgeTag tag, TVar condition, TDomain data)
 229                                 {
 230                                         var boxed = ToBoxedExpression (pc, condition);
 231
 232                                         bool result;
 233                                         if (boxed.IsTrivialCondition (out result))
 234                                                 return result ? data : data.Bottom;
 235
 236                                         data = data.AssumeTrue (boxed);
 237
 238                                         var type =
 239                                                 ContextProvider.ValueContext.GetType (
 240                                                         ContextProvider.MethodContext.CFG.Post (pc), condition);
 241                                         if (type.IsNormal () &&
 242                                             MetaDataProvider.Equal (type.Value, MetaDataProvider.System_Boolean)) {
 243                                                 var guard =
 244                                                         BoxedExpression.Binary (BinaryOperator.Ceq, boxed,
 245                                                                                 BoxedExpression.Const (1,
 246                                                                                                        MetaDataProvider.
 247                                                                                                                System_Int32));
 248
 249                                                 data = data.AssumeTrue (guard);
 250                                         }
 251
 252                                         return data;
 253                                 }
 254
 255                                 public override TDomain DefaultVisit (APC pc, TDomain data)
 256                                 {
 257                                         return data;
 258                                 }
 259
 260                                 protected BoxedExpression ToBoxedExpression (APC pc, TVar condition)
 261                                 {
 262                                         return
 263                                                 BoxedExpression.For (
 264                                                         ContextProvider.ExpressionContext.Refine (pc, condition),
 265                                                         ExpressionDecoder.ExternalDecoder);
 266                                 }
 267
 268                                 public IFactQuery<BoxedExpression, TVar> FactQuery ()
 269                                 {
 270                                         return FactQuery (FixPointInfo);
 271                                 }
 272                         }
 273                 }
 274         }
 275 }