diff options
Diffstat (limited to 'ICSharpCode.Decompiler/Ast/Transforms/AddCheckedBlocks.cs')
-rw-r--r-- | ICSharpCode.Decompiler/Ast/Transforms/AddCheckedBlocks.cs | 368 |
1 files changed, 368 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/Ast/Transforms/AddCheckedBlocks.cs b/ICSharpCode.Decompiler/Ast/Transforms/AddCheckedBlocks.cs new file mode 100644 index 00000000..dc018eb1 --- /dev/null +++ b/ICSharpCode.Decompiler/Ast/Transforms/AddCheckedBlocks.cs @@ -0,0 +1,368 @@ +// Copyright (c) 2011 AlphaSierraPapa for the SharpDevelop Team +// +// Permission is hereby granted, free of charge, to any person obtaining a copy of this +// software and associated documentation files (the "Software"), to deal in the Software +// without restriction, including without limitation the rights to use, copy, modify, merge, +// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons +// to whom the Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all copies or +// substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, +// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR +// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE +// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR +// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +// DEALINGS IN THE SOFTWARE. + +using System; +using System.Linq; +using ICSharpCode.Decompiler.ILAst; +using ICSharpCode.NRefactory.CSharp; + +namespace ICSharpCode.Decompiler.Ast.Transforms +{ + /// <summary> + /// Add checked/unchecked blocks. + /// </summary> + public class AddCheckedBlocks : IAstTransform + { + #region Annotation + sealed class CheckedUncheckedAnnotation { + /// <summary> + /// true=checked, false=unchecked + /// </summary> + public bool IsChecked; + } + + public static readonly object CheckedAnnotation = new CheckedUncheckedAnnotation { IsChecked = true }; + public static readonly object UncheckedAnnotation = new CheckedUncheckedAnnotation { IsChecked = false }; + #endregion + + /* + We treat placing checked/unchecked blocks as an optimization problem, with the following goals: + 1. Use minimum number of checked blocks+expressions + 2. Prefer checked expressions over checked blocks + 3. Make the scope of checked expressions as small as possible + 4. Open checked blocks as late as possible, and close checked blocks as late as possible + (where goal 1 has the highest priority) + + Goal 4a (open checked blocks as late as possible) is necessary so that we don't move variable declarations + into checked blocks, as the variable might still be used after the checked block. + (this could cause DeclareVariables to omit the variable declaration, producing incorrect code) + Goal 4b (close checked blocks as late as possible) makes the code look nicer in this case: + checked { + int c = a + b; + int r = a + c; + return r; + } + If the checked block was closed as early as possible, the variable r would have to be declared outside + (this would work, but look badly) + */ + + #region struct Cost + struct Cost + { + // highest possible cost so that the Blocks+Expressions addition doesn't overflow + public static readonly Cost Infinite = new Cost(0x3fffffff, 0x3fffffff); + + public readonly int Blocks; + public readonly int Expressions; + + public Cost(int blocks, int expressions) + { + Blocks = blocks; + Expressions = expressions; + } + + public static bool operator <(Cost a, Cost b) + { + return a.Blocks + a.Expressions < b.Blocks + b.Expressions + || a.Blocks + a.Expressions == b.Blocks + b.Expressions && a.Blocks < b.Blocks; + } + + public static bool operator >(Cost a, Cost b) + { + return a.Blocks + a.Expressions > b.Blocks + b.Expressions + || a.Blocks + a.Expressions == b.Blocks + b.Expressions && a.Blocks > b.Blocks; + } + + public static bool operator <=(Cost a, Cost b) + { + return a.Blocks + a.Expressions < b.Blocks + b.Expressions + || a.Blocks + a.Expressions == b.Blocks + b.Expressions && a.Blocks <= b.Blocks; + } + + public static bool operator >=(Cost a, Cost b) + { + return a.Blocks + a.Expressions > b.Blocks + b.Expressions + || a.Blocks + a.Expressions == b.Blocks + b.Expressions && a.Blocks >= b.Blocks; + } + + public static Cost operator +(Cost a, Cost b) + { + return new Cost(a.Blocks + b.Blocks, a.Expressions + b.Expressions); + } + + public override string ToString() + { + return string.Format("[{0} + {1}]", Blocks, Expressions); + } + } + #endregion + + #region class InsertedNode + /// <summary> + /// Holds the blocks and expressions that should be inserted + /// </summary> + abstract class InsertedNode + { + public static InsertedNode operator +(InsertedNode a, InsertedNode b) + { + if (a == null) + return b; + if (b == null) + return a; + return new InsertedNodeList(a, b); + } + + public abstract void Insert(); + } + + class InsertedNodeList : InsertedNode + { + readonly InsertedNode child1, child2; + + public InsertedNodeList(InsertedNode child1, InsertedNode child2) + { + this.child1 = child1; + this.child2 = child2; + } + + public override void Insert() + { + child1.Insert(); + child2.Insert(); + } + } + + class InsertedExpression : InsertedNode + { + readonly Expression expression; + readonly bool isChecked; + + public InsertedExpression(Expression expression, bool isChecked) + { + this.expression = expression; + this.isChecked = isChecked; + } + + public override void Insert() + { + if (isChecked) + expression.ReplaceWith(e => new CheckedExpression { Expression = e }); + else + expression.ReplaceWith(e => new UncheckedExpression { Expression = e }); + } + } + + class ConvertCompoundAssignment : InsertedNode + { + readonly Expression expression; + readonly bool isChecked; + + public ConvertCompoundAssignment(Expression expression, bool isChecked) + { + this.expression = expression; + this.isChecked = isChecked; + } + + public override void Insert() + { + AssignmentExpression assign = expression.Annotation<ReplaceMethodCallsWithOperators.RestoreOriginalAssignOperatorAnnotation>().Restore(expression); + expression.ReplaceWith(assign); + if (isChecked) + assign.Right = new CheckedExpression { Expression = assign.Right.Detach() }; + else + assign.Right = new UncheckedExpression { Expression = assign.Right.Detach() }; + } + } + + class InsertedBlock : InsertedNode + { + readonly Statement firstStatement; // inclusive + readonly Statement lastStatement; // exclusive + readonly bool isChecked; + + public InsertedBlock(Statement firstStatement, Statement lastStatement, bool isChecked) + { + this.firstStatement = firstStatement; + this.lastStatement = lastStatement; + this.isChecked = isChecked; + } + + public override void Insert() + { + BlockStatement newBlock = new BlockStatement(); + // Move all statements except for the first + Statement next; + for (Statement stmt = firstStatement.GetNextStatement(); stmt != lastStatement; stmt = next) { + next = stmt.GetNextStatement(); + newBlock.Add(stmt.Detach()); + } + // Replace the first statement with the new (un)checked block + if (isChecked) + firstStatement.ReplaceWith(new CheckedStatement { Body = newBlock }); + else + firstStatement.ReplaceWith(new UncheckedStatement { Body = newBlock }); + // now also move the first node into the new block + newBlock.Statements.InsertAfter(null, firstStatement); + } + } + #endregion + + #region class Result + /// <summary> + /// Holds the result of an insertion operation. + /// </summary> + class Result + { + public Cost CostInCheckedContext; + public InsertedNode NodesToInsertInCheckedContext; + public Cost CostInUncheckedContext; + public InsertedNode NodesToInsertInUncheckedContext; + } + #endregion + + public void Run(AstNode node) + { + BlockStatement block = node as BlockStatement; + if (block == null) { + for (AstNode child = node.FirstChild; child != null; child = child.NextSibling) { + Run(child); + } + } else { + Result r = GetResultFromBlock(block); + if (r.NodesToInsertInUncheckedContext != null) + r.NodesToInsertInUncheckedContext.Insert(); + } + } + + Result GetResultFromBlock(BlockStatement block) + { + // For a block, we are tracking 4 possibilities: + // a) context is checked, no unchecked block open + Cost costCheckedContext = new Cost(0, 0); + InsertedNode nodesCheckedContext = null; + // b) context is checked, an unchecked block is open + Cost costCheckedContextUncheckedBlockOpen = Cost.Infinite; + InsertedNode nodesCheckedContextUncheckedBlockOpen = null; + Statement uncheckedBlockStart = null; + // c) context is unchecked, no checked block open + Cost costUncheckedContext = new Cost(0, 0); + InsertedNode nodesUncheckedContext = null; + // d) context is unchecked, a checked block is open + Cost costUncheckedContextCheckedBlockOpen = Cost.Infinite; + InsertedNode nodesUncheckedContextCheckedBlockOpen = null; + Statement checkedBlockStart = null; + + Statement statement = block.Statements.FirstOrDefault(); + while (true) { + // Blocks can be closed 'for free'. We use '<=' so that blocks are closed as late as possible (goal 4b) + if (costCheckedContextUncheckedBlockOpen <= costCheckedContext) { + costCheckedContext = costCheckedContextUncheckedBlockOpen; + nodesCheckedContext = nodesCheckedContextUncheckedBlockOpen + new InsertedBlock(uncheckedBlockStart, statement, false); + } + if (costUncheckedContextCheckedBlockOpen <= costUncheckedContext) { + costUncheckedContext = costUncheckedContextCheckedBlockOpen; + nodesUncheckedContext = nodesUncheckedContextCheckedBlockOpen + new InsertedBlock(checkedBlockStart, statement, true); + } + if (statement == null) + break; + // Now try opening blocks. We use '<=' so that blocks are opened as late as possible. (goal 4a) + if (costCheckedContext + new Cost(1, 0) <= costCheckedContextUncheckedBlockOpen) { + costCheckedContextUncheckedBlockOpen = costCheckedContext + new Cost(1, 0); + nodesCheckedContextUncheckedBlockOpen = nodesCheckedContext; + uncheckedBlockStart = statement; + } + if (costUncheckedContext + new Cost(1, 0) <= costUncheckedContextCheckedBlockOpen) { + costUncheckedContextCheckedBlockOpen = costUncheckedContext + new Cost(1, 0); + nodesUncheckedContextCheckedBlockOpen = nodesUncheckedContext; + checkedBlockStart = statement; + } + // Now handle the statement + Result stmtResult = GetResult(statement); + + costCheckedContext += stmtResult.CostInCheckedContext; + nodesCheckedContext += stmtResult.NodesToInsertInCheckedContext; + costCheckedContextUncheckedBlockOpen += stmtResult.CostInUncheckedContext; + nodesCheckedContextUncheckedBlockOpen += stmtResult.NodesToInsertInUncheckedContext; + costUncheckedContext += stmtResult.CostInUncheckedContext; + nodesUncheckedContext += stmtResult.NodesToInsertInUncheckedContext; + costUncheckedContextCheckedBlockOpen += stmtResult.CostInCheckedContext; + nodesUncheckedContextCheckedBlockOpen += stmtResult.NodesToInsertInCheckedContext; + + statement = statement.GetNextStatement(); + } + + return new Result { + CostInCheckedContext = costCheckedContext, NodesToInsertInCheckedContext = nodesCheckedContext, + CostInUncheckedContext = costUncheckedContext, NodesToInsertInUncheckedContext = nodesUncheckedContext + }; + } + + Result GetResult(AstNode node) + { + if (node is BlockStatement) + return GetResultFromBlock((BlockStatement)node); + Result result = new Result(); + for (AstNode child = node.FirstChild; child != null; child = child.NextSibling) { + Result childResult = GetResult(child); + result.CostInCheckedContext += childResult.CostInCheckedContext; + result.NodesToInsertInCheckedContext += childResult.NodesToInsertInCheckedContext; + result.CostInUncheckedContext += childResult.CostInUncheckedContext; + result.NodesToInsertInUncheckedContext += childResult.NodesToInsertInUncheckedContext; + } + Expression expr = node as Expression; + if (expr != null) { + CheckedUncheckedAnnotation annotation = expr.Annotation<CheckedUncheckedAnnotation>(); + if (annotation != null) { + // If the annotation requires this node to be in a specific context, add a huge cost to the other context + // That huge cost gives us the option to ignore a required checked/unchecked expression when there wouldn't be any + // solution otherwise. (e.g. "for (checked(M().x += 1); true; unchecked(M().x += 2)) {}") + if (annotation.IsChecked) + result.CostInUncheckedContext += new Cost(10000, 0); + else + result.CostInCheckedContext += new Cost(10000, 0); + } + // Embed this node in an checked/unchecked expression: + if (expr.Parent is ExpressionStatement) { + // We cannot use checked/unchecked for top-level-expressions. + // However, we could try converting a compound assignment (checked(a+=b);) or unary operator (checked(a++);) + // back to its old form. + if (expr.Annotation<ReplaceMethodCallsWithOperators.RestoreOriginalAssignOperatorAnnotation>() != null) { + // We use '<' so that expressions are introduced on the deepest level possible (goal 3) + if (result.CostInCheckedContext + new Cost(1, 1) < result.CostInUncheckedContext) { + result.CostInUncheckedContext = result.CostInCheckedContext + new Cost(1, 1); + result.NodesToInsertInUncheckedContext = result.NodesToInsertInCheckedContext + new ConvertCompoundAssignment(expr, true); + } else if (result.CostInUncheckedContext + new Cost(1, 1) < result.CostInCheckedContext) { + result.CostInCheckedContext = result.CostInUncheckedContext + new Cost(1, 1); + result.NodesToInsertInCheckedContext = result.NodesToInsertInUncheckedContext + new ConvertCompoundAssignment(expr, false); + } + } + } else if (expr.Role.IsValid(Expression.Null)) { + // We use '<' so that expressions are introduced on the deepest level possible (goal 3) + if (result.CostInCheckedContext + new Cost(0, 1) < result.CostInUncheckedContext) { + result.CostInUncheckedContext = result.CostInCheckedContext + new Cost(0, 1); + result.NodesToInsertInUncheckedContext = result.NodesToInsertInCheckedContext + new InsertedExpression(expr, true); + } else if (result.CostInUncheckedContext + new Cost(0, 1) < result.CostInCheckedContext) { + result.CostInCheckedContext = result.CostInUncheckedContext + new Cost(0, 1); + result.NodesToInsertInCheckedContext = result.NodesToInsertInUncheckedContext + new InsertedExpression(expr, false); + } + } + } + return result; + } + } +} |