5 // Alexander Chebaturkin (chebaturkin@gmail.com)
7 // Copyright (C) 2011 Alexander Chebaturkin
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:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
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.
30 using System.Collections.Generic;
31 using Mono.CodeContracts.Static.AST;
32 using Mono.CodeContracts.Static.AST.Visitors;
33 using Mono.CodeContracts.Static.ControlFlow;
34 using Mono.CodeContracts.Static.DataStructures;
36 namespace Mono.CodeContracts.Static.Analysis.StackAnalysis {
37 struct StackDecoder<TContext, TData, TResult, TVisitor> : IILVisitor<APC, Dummy, Dummy, TData, TResult>
38 where TContext : IMethodContextProvider
39 where TVisitor : IILVisitor<APC, int, int, TData, TResult>
41 private readonly StackDepthProvider<TContext> parent;
42 private readonly TVisitor visitor;
44 public StackDecoder(StackDepthProvider<TContext> parent,
48 this.visitor = visitor;
51 private int Pop(APC label, int count)
53 return this.parent.GlobalStackDepth (label) - 1 - count;
56 private SequenceGenerator PopSequence(APC pc, int args, int offset)
58 return new SequenceGenerator (this.parent.GlobalStackDepth (pc) - args - offset, args);
61 private int Push(APC label, int count)
63 return this.parent.GlobalStackDepth (label) - count;
66 private int Push(APC label, int args, TypeNode returnType)
68 if (this.parent.MetaDataProvider.IsVoid (returnType))
71 return Push (label, args);
74 private int GetParametersCount(Method ctor, int extraVarargs)
76 int result = extraVarargs + this.parent.MetaDataProvider.Parameters (ctor).Count;
77 if (!this.parent.MetaDataProvider.IsStatic (ctor))
82 private bool RemapParameterToLoadStack(APC pc, ref Parameter param, out bool isLoadResult, out int loadStackOffset, out bool isOld, out APC lookupPC)
84 if (pc.SubroutineContext == null) {
92 if (pc.Block.Subroutine.IsRequires) {
96 for (LispList<Edge<CFGBlock, EdgeTag>> list = pc.SubroutineContext; list != null; list = list.Tail) {
97 EdgeTag edgeTag = list.Head.Tag;
98 if (edgeTag == EdgeTag.Entry) {
99 param = RemapParameter (param, list.Head.From, pc.Block);
103 if (edgeTag.Is (EdgeTag.BeforeMask)) {
104 int stackDepth = this.parent.LocalStackDepth (pc);
105 loadStackOffset = this.parent.MetaDataProvider.ParameterStackIndex (param) + stackDepth;
109 throw new InvalidOperationException ();
112 if (pc.Block.Subroutine.IsEnsuresOrOldValue) {
114 for (LispList<Edge<CFGBlock, EdgeTag>> ctx = pc.SubroutineContext; ctx != null; ctx = ctx.Tail) {
115 EdgeTag tag = ctx.Head.Tag;
116 if (tag == EdgeTag.Exit) {
117 param = RemapParameter (param, ctx.Head.From, pc.Block);
118 isLoadResult = false;
124 if (tag == EdgeTag.AfterCall) {
125 loadStackOffset = this.parent.MetaDataProvider.ParameterStackIndex (param);
126 isLoadResult = false;
127 lookupPC = new APC (ctx.Head.From, 0, ctx.Tail);
131 if (tag == EdgeTag.AfterNewObj) {
132 if (this.parent.MetaDataProvider.ParameterIndex (param) == 0) {
133 loadStackOffset = this.parent.LocalStackDepth (pc);
140 loadStackOffset = this.parent.MetaDataProvider.ParameterIndex (param);
141 isLoadResult = false;
142 lookupPC = new APC (ctx.Head.From, 0, ctx.Tail);
145 if (tag == EdgeTag.OldManifest) {
146 param = RemapParameter (param, ctx.Tail.Head.From, pc.Block);
148 isLoadResult = false;
154 throw new InvalidOperationException ();
157 if (pc.Block.Subroutine.IsInvariant) {
158 for (LispList<Edge<CFGBlock, EdgeTag>> list = pc.SubroutineContext; list != null; list = list.Tail) {
159 EdgeTag tag = list.Head.Tag;
160 if (tag == EdgeTag.Entry || tag == EdgeTag.Exit) {
162 if (pc.TryGetContainingMethod (out method)) {
163 param = this.parent.MetaDataProvider.This (method);
164 isLoadResult = false;
166 isOld = tag == EdgeTag.Exit;
170 isLoadResult = false;
176 if (tag == EdgeTag.AfterCall) {
180 list.Head.From.IsMethodCallBlock (out calledMethod, out isNewObj, out isVirtual);
181 int count = this.parent.MetaDataProvider.Parameters (calledMethod).Count;
182 loadStackOffset = count;
183 isLoadResult = false;
185 lookupPC = new APC (list.Head.From, 0, list.Tail);
188 if (tag == EdgeTag.AfterNewObj) {
190 loadStackOffset = this.parent.LocalStackDepth (pc);
195 if (tag.Is (EdgeTag.BeforeMask))
196 throw new InvalidOperationException ("this should never happen");
198 throw new InvalidOperationException ("this should never happen");
201 isLoadResult = false;
208 private Parameter RemapParameter(Parameter p, CFGBlock parentMethodBlock, CFGBlock subroutineBlock)
210 Method parentMethod = ((IMethodInfo) parentMethodBlock.Subroutine).Method;
211 Method method = ((IMethodInfo) subroutineBlock.Subroutine).Method;
213 if (this.parent.MetaDataProvider.Equal (method, parentMethod))
216 int index = this.parent.MetaDataProvider.ParameterIndex (p);
217 if (this.parent.MetaDataProvider.IsStatic (parentMethod) || index != 0)
218 return this.parent.MetaDataProvider.Parameters (parentMethod)[index];
220 return this.parent.MetaDataProvider.This (parentMethod);
223 private bool IsReferenceType(APC pc, TypeNode type)
225 return this.parent.MetaDataProvider.IsReferenceType (type);
228 private TypeNode GetSpecializedType(APC pc, TypeNode type)
230 var methodInfo = pc.Block.Subroutine as IMethodInfo;
231 if (methodInfo == null)
234 throw new NotImplementedException ();
237 #region Implementation of IExpressionILVisitor<APC,Type,Dummy,Dummy,Data,Result>
238 public TResult Binary(APC pc, BinaryOperator op, Dummy dest, Dummy operand1, Dummy operand2, TData data)
240 return this.visitor.Binary (pc, op, Push (pc, 2), Pop (pc, 1), Pop (pc, 0), data);
243 public TResult Isinst(APC pc, TypeNode type, Dummy dest, Dummy obj, TData data)
245 return this.visitor.Isinst (pc, type, Push (pc, 1), Pop (pc, 0), data);
248 public TResult LoadNull(APC pc, Dummy dest, TData polarity)
250 return this.visitor.LoadNull (pc, Push (pc, 0), polarity);
253 public TResult LoadConst(APC pc, TypeNode type, object constant, Dummy dest, TData data)
255 return this.visitor.LoadConst (pc, type, constant, Push (pc, 0), data);
258 public TResult Sizeof(APC pc, TypeNode type, Dummy dest, TData data)
260 return this.visitor.Sizeof (pc, type, Push (pc, 0), data);
263 public TResult Unary(APC pc, UnaryOperator op, bool unsigned, Dummy dest, Dummy source, TData data)
265 return this.visitor.Unary (pc, op, unsigned, Push (pc, 1), Pop (pc, 0), data);
269 #region Implementation of ISyntheticILVisitor<APC,Method,Field,Type,Dummy,Dummy,Data,Result>
270 public TResult Entry(APC pc, Method method, TData data)
272 return this.visitor.Entry (pc, method, data);
275 public TResult Assume(APC pc, EdgeTag tag, Dummy condition, TData data)
277 return this.visitor.Assume (pc, tag, Pop (pc, 0), data);
280 public TResult Assert(APC pc, EdgeTag tag, Dummy condition, TData data)
282 return this.visitor.Assert (pc, tag, Pop (pc, 0), data);
285 public TResult BeginOld(APC pc, APC matchingEnd, TData data)
287 return this.visitor.BeginOld (pc, matchingEnd, data);
290 public TResult EndOld(APC pc, APC matchingBegin, TypeNode type, Dummy dest, Dummy source, TData data)
292 if (pc.InsideOldManifestation)
293 return this.visitor.LoadStack (pc, 1, Push (matchingBegin, 0), Pop (pc, 0), false, data);
295 return this.visitor.EndOld (pc, matchingBegin, type, Push (matchingBegin, 0), Pop (pc, 0), data);
298 public TResult LoadStack(APC pc, int offset, Dummy dest, Dummy source, bool isOld, TData data)
300 return this.visitor.LoadStack (pc, offset, Push (pc, 0), Pop (pc, offset), isOld, data);
303 public TResult LoadStackAddress(APC pc, int offset, Dummy dest, Dummy source, TypeNode type, bool isOld, TData data)
305 return this.visitor.LoadStackAddress (pc, offset, Push (pc, 0), Pop (pc, offset), type, isOld, data);
308 public TResult LoadResult(APC pc, TypeNode type, Dummy dest, Dummy source, TData data)
310 int offset = this.parent.LocalStackDepth (pc);
311 return this.visitor.LoadResult (pc, type, Push (pc, 0), Pop (pc, offset), data);
315 #region Implementation of IILVisitor<APC,Local,Parameter,Method,Field,Type,Dummy,Dummy,Data,Result>
316 public TResult Arglist(APC pc, Dummy dest, TData data)
318 return this.visitor.Arglist (pc, Push (pc, 0), data);
321 public TResult Branch(APC pc, APC target, bool leavesExceptionBlock, TData data)
323 return this.visitor.Branch (pc, target, leavesExceptionBlock, data);
326 public TResult BranchCond(APC pc, APC target, BranchOperator bop, Dummy value1, Dummy value2, TData data)
328 return this.visitor.BranchCond (pc, target, bop, Pop (pc, 1), Pop (pc, 0), data);
331 public TResult BranchTrue(APC pc, APC target, Dummy cond, TData data)
333 return this.visitor.BranchTrue (pc, target, Pop (pc, 0), data);
336 public TResult BranchFalse(APC pc, APC target, Dummy cond, TData data)
338 return this.visitor.BranchFalse (pc, target, Pop (pc, 0), data);
341 public TResult Break(APC pc, TData data)
343 return this.visitor.Break (pc, data);
346 public TResult Call<TypeList, ArgList>(APC pc, Method method, bool virt, TypeList extraVarargs, Dummy dest, ArgList args, TData data)
347 where TypeList : IIndexable<TypeNode>
348 where ArgList : IIndexable<Dummy>
350 int argsCount = GetParametersCount (method, extraVarargs == null ? 0 : extraVarargs.Count);
351 return this.visitor.Call (pc, method, virt, extraVarargs, Push (pc, argsCount, this.parent.MetaDataProvider.ReturnType (method)), PopSequence (pc, argsCount, 0), data);
354 public TResult Calli<TypeList, ArgList>(APC pc, TypeNode returnType, TypeList argTypes, bool instance, Dummy dest, Dummy functionPointer, ArgList args, TData data)
355 where TypeList : IIndexable<TypeNode>
356 where ArgList : IIndexable<Dummy>
358 int argsCount = argTypes.Count + (instance ? 1 : 0);
359 return this.visitor.Calli (pc, returnType, argTypes, instance, Push (pc, argsCount + 1, returnType), Pop (pc, 0), PopSequence (pc, argsCount, 1), data);
362 public TResult CheckFinite(APC pc, Dummy dest, Dummy source, TData data)
364 return this.visitor.CheckFinite (pc, Push (pc, 1), Pop (pc, 0), data);
367 public TResult CopyBlock(APC pc, Dummy destAddress, Dummy srcAddress, Dummy len, TData data)
369 return this.visitor.CopyBlock (pc, Pop (pc, 2), Pop (pc, 1), Pop (pc, 0), data);
372 public TResult EndFilter(APC pc, Dummy decision, TData data)
374 return this.visitor.EndFilter (pc, Pop (pc, 0), data);
377 public TResult EndFinally(APC pc, TData data)
379 return this.visitor.EndFinally (pc, data);
382 public TResult Jmp(APC pc, Method method, TData data)
384 return this.visitor.Jmp (pc, method, data);
387 public TResult LoadArg(APC pc, Parameter argument, bool dummyOld, Dummy dest, TData data)
389 Parameter p = argument;
394 if (RemapParameterToLoadStack (pc, ref argument, out isLdResult, out loadStackOffset, out isOld, out lookupPC))
395 return this.visitor.LoadStack (pc, loadStackOffset, Push (pc, 0), Pop (lookupPC, loadStackOffset), isOld, data);
397 if (argument == null)
401 if (this.parent.MetaDataProvider.IsStruct (this.parent.MetaDataProvider.DeclaringType (this.parent.MetaDataProvider.DeclaringMethod (argument))))
402 return this.visitor.LoadStackAddress (pc, loadStackOffset, Push (pc, 0), Pop (pc, loadStackOffset), this.parent.MetaDataProvider.ParameterType (argument), isOld, data);
404 return this.visitor.LoadResult (pc, this.parent.MetaDataProvider.ParameterType (argument), Push (pc, 0), Pop (pc, loadStackOffset), data);
407 return this.visitor.LoadArg (pc, argument, isOld, Push (pc, 0), data);
410 public TResult LoadArgAddress(APC pc, Parameter argument, bool dummyOld, Dummy dest, TData data)
416 if (RemapParameterToLoadStack (pc, ref argument, out isLoadResult, out loadStackOffset, out isOld, out lookupPC))
417 return this.visitor.LoadStackAddress (pc, loadStackOffset, Push (pc, 0), Pop (lookupPC, loadStackOffset), this.parent.MetaDataProvider.ParameterType (argument), isOld, data);
420 throw new InvalidOperationException ();
422 return this.visitor.LoadArgAddress (pc, argument, isOld, Push (pc, 0), data);
425 public TResult LoadLocal(APC pc, Local local, Dummy dest, TData data)
427 return this.visitor.LoadLocal (pc, local, Push (pc, 0), data);
430 public TResult LoadLocalAddress(APC pc, Local local, Dummy dest, TData data)
432 return this.visitor.LoadLocalAddress (pc, local, Push (pc, 0), data);
435 public TResult Nop(APC pc, TData data)
437 return this.visitor.Nop (pc, data);
440 public TResult Pop(APC pc, Dummy source, TData data)
442 return this.visitor.Pop (pc, Pop (pc, 0), data);
445 public TResult Return(APC pc, Dummy source, TData data)
447 return this.visitor.Nop (pc, data);
450 public TResult StoreArg(APC pc, Parameter argument, Dummy source, TData data)
452 return this.visitor.StoreArg (pc, argument, Pop (pc, 0), data);
455 public TResult StoreLocal(APC pc, Local local, Dummy source, TData data)
457 return this.visitor.StoreLocal (pc, local, Pop (pc, 0), data);
460 public TResult Switch(APC pc, TypeNode type, IEnumerable<Pair<object, APC>> cases, Dummy value, TData data)
462 return this.visitor.Switch (pc, type, cases, Pop (pc, 0), data);
465 public TResult Box(APC pc, TypeNode type, Dummy dest, Dummy source, TData data)
467 type = GetSpecializedType (pc, type);
468 if (IsReferenceType (pc, type))
469 return this.visitor.Nop (pc, data);
471 return this.visitor.Box (pc, type, Push (pc, 1), Pop (pc, 0), data);
474 public TResult ConstrainedCallvirt<TypeList, ArgList>(APC pc, Method method, TypeNode constraint, TypeList extraVarargs, Dummy dest, ArgList args, TData data)
475 where TypeList : IIndexable<TypeNode>
476 where ArgList : IIndexable<Dummy>
478 int argsCount = GetParametersCount (method, extraVarargs == null ? 0 : extraVarargs.Count);
479 return this.visitor.ConstrainedCallvirt (pc, method, constraint, extraVarargs, Push (pc, argsCount, this.parent.MetaDataProvider.ReturnType (method)), PopSequence (pc, argsCount, 0), data);
482 public TResult CastClass(APC pc, TypeNode type, Dummy dest, Dummy obj, TData data)
484 return this.visitor.CastClass (pc, type, Push (pc, 1), Pop (pc, 0), data);
487 public TResult CopyObj(APC pc, TypeNode type, Dummy destPtr, Dummy sourcePtr, TData data)
489 return this.visitor.CopyObj (pc, type, Pop (pc, 1), Pop (pc, 0), data);
492 public TResult Initobj(APC pc, TypeNode type, Dummy ptr, TData data)
494 return this.visitor.Initobj (pc, type, Pop (pc, 0), data);
497 public TResult LoadElement(APC pc, TypeNode type, Dummy dest, Dummy array, Dummy index, TData data)
499 return this.visitor.LoadElement (pc, type, Push (pc, 2), Pop (pc, 1), Pop (pc, 0), data);
502 public TResult LoadField(APC pc, Field field, Dummy dest, Dummy obj, TData data)
504 return this.visitor.LoadField (pc, field, Push (pc, 1), Pop (pc, 0), data);
507 public TResult LoadFieldAddress(APC pc, Field field, Dummy dest, Dummy obj, TData data)
509 return this.visitor.LoadFieldAddress (pc, field, Push (pc, 1), Pop (pc, 0), data);
512 public TResult LoadLength(APC pc, Dummy dest, Dummy array, TData data)
514 return this.visitor.LoadLength (pc, Push (pc, 1), Pop (pc, 0), data);
517 public TResult LoadStaticField(APC pc, Field field, Dummy dest, TData data)
519 return this.visitor.LoadStaticField (pc, field, Push (pc, 0), data);
522 public TResult LoadStaticFieldAddress(APC pc, Field field, Dummy dest, TData data)
524 return this.visitor.LoadStaticFieldAddress (pc, field, Push (pc, 0), data);
527 public TResult LoadTypeToken(APC pc, TypeNode type, Dummy dest, TData data)
529 return this.visitor.LoadTypeToken (pc, type, Push (pc, 0), data);
532 public TResult LoadFieldToken(APC pc, Field field, Dummy dest, TData data)
534 return this.visitor.LoadFieldToken (pc, field, Push (pc, 0), data);
537 public TResult LoadMethodToken(APC pc, Method method, Dummy dest, TData data)
539 return this.visitor.LoadMethodToken (pc, method, Push (pc, 0), data);
542 public TResult NewArray<ArgList>(APC pc, TypeNode type, Dummy dest, ArgList lengths, TData data)
543 where ArgList : IIndexable<Dummy>
545 return this.visitor.NewArray (pc, type, Push (pc, 1), PopSequence (pc, lengths.Count, 0), data);
548 public TResult NewObj<ArgList>(APC pc, Method ctor, Dummy dest, ArgList args, TData data)
549 where ArgList : IIndexable<Dummy>
551 int argsCount = GetParametersCount (ctor, 0) - 1;
552 return this.visitor.NewObj (pc, ctor, Push (pc, argsCount), PopSequence (pc, argsCount, 0), data);
555 public TResult MkRefAny(APC pc, TypeNode type, Dummy dest, Dummy obj, TData data)
557 return this.visitor.MkRefAny (pc, type, Push (pc, 1), Pop (pc, 0), data);
560 public TResult RefAnyType(APC pc, Dummy dest, Dummy source, TData data)
562 return this.visitor.RefAnyType (pc, Push (pc, 1), Pop (pc, 0), data);
565 public TResult RefAnyVal(APC pc, TypeNode type, Dummy dest, Dummy source, TData data)
567 return this.visitor.RefAnyVal (pc, type, Push (pc, 1), Pop (pc, 0), data);
570 public TResult Rethrow(APC pc, TData data)
572 return this.visitor.Rethrow (pc, data);
575 public TResult StoreElement(APC pc, TypeNode type, Dummy array, Dummy index, Dummy value, TData data)
577 return this.visitor.StoreElement (pc, type, Pop (pc, 2), Pop (pc, 1), Pop (pc, 0), data);
580 public TResult StoreField(APC pc, Field field, Dummy obj, Dummy value, TData data)
582 return this.visitor.StoreField (pc, field, Pop (pc, 1), Pop (pc, 0), data);
585 public TResult StoreStaticField(APC pc, Field field, Dummy value, TData data)
587 return this.visitor.StoreStaticField (pc, field, Pop (pc, 0), data);
590 public TResult Throw(APC pc, Dummy exception, TData data)
592 return this.visitor.Throw (pc, Pop (pc, 0), data);
595 public TResult Unbox(APC pc, TypeNode type, Dummy dest, Dummy obj, TData data)
597 return this.visitor.Unbox (pc, type, Push (pc, 1), Pop (pc, 0), data);
600 public TResult UnboxAny(APC pc, TypeNode type, Dummy dest, Dummy obj, TData data)
602 return this.visitor.UnboxAny (pc, type, Push (pc, 1), Pop (pc, 0), data);