View Javadoc
1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.java.rule.strings;
5   
6   import java.util.ArrayList;
7   import java.util.HashMap;
8   import java.util.HashSet;
9   import java.util.List;
10  import java.util.Map;
11  import java.util.Set;
12  
13  import net.sourceforge.pmd.lang.ast.Node;
14  import net.sourceforge.pmd.lang.java.ast.ASTAdditiveExpression;
15  import net.sourceforge.pmd.lang.java.ast.ASTAllocationExpression;
16  import net.sourceforge.pmd.lang.java.ast.ASTBlockStatement;
17  import net.sourceforge.pmd.lang.java.ast.ASTCastExpression;
18  import net.sourceforge.pmd.lang.java.ast.ASTFieldDeclaration;
19  import net.sourceforge.pmd.lang.java.ast.ASTFormalParameter;
20  import net.sourceforge.pmd.lang.java.ast.ASTIfStatement;
21  import net.sourceforge.pmd.lang.java.ast.ASTLiteral;
22  import net.sourceforge.pmd.lang.java.ast.ASTMultiplicativeExpression;
23  import net.sourceforge.pmd.lang.java.ast.ASTName;
24  import net.sourceforge.pmd.lang.java.ast.ASTPrimaryExpression;
25  import net.sourceforge.pmd.lang.java.ast.ASTPrimaryPrefix;
26  import net.sourceforge.pmd.lang.java.ast.ASTPrimarySuffix;
27  import net.sourceforge.pmd.lang.java.ast.ASTSwitchLabel;
28  import net.sourceforge.pmd.lang.java.ast.ASTSwitchStatement;
29  import net.sourceforge.pmd.lang.java.ast.ASTType;
30  import net.sourceforge.pmd.lang.java.ast.ASTVariableDeclarator;
31  import net.sourceforge.pmd.lang.java.ast.ASTVariableDeclaratorId;
32  import net.sourceforge.pmd.lang.java.ast.ASTVariableInitializer;
33  import net.sourceforge.pmd.lang.java.rule.AbstractJavaRule;
34  import net.sourceforge.pmd.lang.java.symboltable.JavaNameOccurrence;
35  import net.sourceforge.pmd.lang.java.typeresolution.TypeHelper;
36  import net.sourceforge.pmd.lang.symboltable.NameOccurrence;
37  
38  /**
39   * This rule finds StringBuffers which may have been pre-sized incorrectly
40   *
41   * See http://sourceforge.net/forum/forum.php?thread_id=1438119&forum_id=188194
42   * @author Allan Caplan
43   */
44  public class InsufficientStringBufferDeclarationRule extends AbstractJavaRule {
45  
46      private final static Set<Class<? extends Node>> BLOCK_PARENTS;
47  
48      static {
49          BLOCK_PARENTS = new HashSet<Class<? extends Node>>(2);
50          BLOCK_PARENTS.add(ASTIfStatement.class);
51          BLOCK_PARENTS.add(ASTSwitchStatement.class);
52      }
53  
54      public static final int DEFAULT_BUFFER_SIZE = 16;	// as specified in StringBuffer & StringBuilder
55  
56      @Override
57      public Object visit(ASTVariableDeclaratorId node, Object data) {
58          if (!TypeHelper.isEither(node.getNameDeclaration(), StringBuffer.class, StringBuilder.class)) {
59              return data;
60          }
61          Node rootNode = node;
62          int anticipatedLength = 0;
63          int constructorLength = DEFAULT_BUFFER_SIZE;
64  
65          constructorLength = getConstructorLength(node, constructorLength);
66          anticipatedLength = getInitialLength(node);
67  
68          anticipatedLength += getConstructorAppendsLength(node);
69  
70          List<NameOccurrence> usage = node.getUsages();
71          Map<Node, Map<Node, Integer>> blocks = new HashMap<Node, Map<Node, Integer>>();
72          for (NameOccurrence no : usage) {
73              JavaNameOccurrence jno = (JavaNameOccurrence)no;
74              Node n = jno.getLocation();
75              if (!InefficientStringBufferingRule.isInStringBufferOperation(n, 3, "append")) {
76  
77                  if (!jno.isOnLeftHandSide() && !InefficientStringBufferingRule.isInStringBufferOperation(n, 3, "setLength")) {
78                      continue;
79                  }
80                  if (constructorLength != -1 && anticipatedLength > constructorLength) {
81                      anticipatedLength += processBlocks(blocks);
82                      String[] param = { String.valueOf(constructorLength), String.valueOf(anticipatedLength) };
83                      addViolation(data, rootNode, param);
84                  }
85                  constructorLength = getConstructorLength(n, constructorLength);
86                  rootNode = n;
87                  anticipatedLength = getInitialLength(node);
88              }
89              ASTPrimaryExpression s = n.getFirstParentOfType(ASTPrimaryExpression.class);
90              int numChildren = s.jjtGetNumChildren();
91              for (int jx = 0; jx < numChildren; jx++) {
92              	Node sn = s.jjtGetChild(jx);
93                  if (!(sn instanceof ASTPrimarySuffix) || sn.getImage() != null) {
94                      continue;
95                  }
96                  int thisSize = 0;
97                  Node block = getFirstParentBlock(sn);
98                  if (isAdditive(sn)) {
99                      thisSize = processAdditive(sn);
100                 } else {
101                     thisSize = processNode(sn);
102                 }
103                 if (block != null) {
104                     storeBlockStatistics(blocks, thisSize, block);
105                 } else {
106                     anticipatedLength += thisSize;
107                 }
108             }
109         }
110         anticipatedLength += processBlocks(blocks);
111         if (constructorLength != -1 && anticipatedLength > constructorLength) {
112             String[] param = { String.valueOf(constructorLength), String.valueOf(anticipatedLength) };
113             addViolation(data, rootNode, param);
114         }
115         return data;
116     }
117 
118     /**
119      * This rule is concerned with IF and Switch blocks. Process the block into
120      * a local Map, from which we can later determine which is the longest block
121      * inside
122      *
123      * @param blocks
124      *            The map of blocks in the method being investigated
125      * @param thisSize
126      *            The size of the current block
127      * @param block
128      *            The block in question
129      */
130     private void storeBlockStatistics(Map<Node, Map<Node, Integer>> blocks, int thisSize, Node block) {
131         Node statement = block.jjtGetParent();
132         if (block.jjtGetParent() instanceof ASTIfStatement) {
133             // Else Ifs are their own subnode in AST. So we have to
134             // look a little farther up the tree to find the IF statement
135             Node possibleStatement = statement.getFirstParentOfType(ASTIfStatement.class);
136             while (possibleStatement instanceof ASTIfStatement) {
137                 statement = possibleStatement;
138                 possibleStatement = possibleStatement.getFirstParentOfType(ASTIfStatement.class);
139             }
140         }
141         Map<Node, Integer> thisBranch = blocks.get(statement);
142         if (thisBranch == null) {
143             thisBranch = new HashMap<Node, Integer>();
144             blocks.put(statement, thisBranch);
145         }
146         Integer x = thisBranch.get(block);
147         if (x != null) {
148             thisSize += x;
149         }
150         thisBranch.put(statement, thisSize);
151     }
152 
153     private int processBlocks(Map<Node, Map<Node, Integer>> blocks) {
154         int anticipatedLength = 0;
155         int ifLength = 0;
156         for (Map.Entry<Node, Map<Node, Integer>> entry: blocks.entrySet()) {
157             ifLength = 0;
158             for (Map.Entry<Node, Integer> entry2: entry.getValue().entrySet()) {
159                 Integer value = entry2.getValue();
160                 ifLength = Math.max(ifLength, value.intValue());
161             }
162             anticipatedLength += ifLength;
163         }
164         return anticipatedLength;
165     }
166 
167     private int processAdditive(Node sn) {
168         ASTAdditiveExpression additive = sn.getFirstDescendantOfType(ASTAdditiveExpression.class);
169         if (additive == null) {
170             return 0;
171         }
172         int anticipatedLength = 0;
173         for (int ix = 0; ix < additive.jjtGetNumChildren(); ix++) {
174             Node childNode = additive.jjtGetChild(ix);
175             ASTLiteral literal = childNode.getFirstDescendantOfType(ASTLiteral.class);
176             if (literal != null && literal.getImage() != null) {
177                 anticipatedLength += literal.getImage().length() - 2;
178             }
179         }
180 
181         return anticipatedLength;
182     }
183 
184     private static final boolean isStringOrCharLiteral(ASTLiteral literal) {
185     	return literal.isStringLiteral() || literal.isCharLiteral();
186     }
187 
188     private int processNode(Node sn) {
189         int anticipatedLength = 0;
190         if ( sn != null ) {
191             ASTPrimaryPrefix xn = sn.getFirstDescendantOfType(ASTPrimaryPrefix.class);
192             if ( xn != null ) {
193                 if (xn.jjtGetNumChildren() != 0 && xn.jjtGetChild(0) instanceof ASTLiteral) {
194                 	ASTLiteral literal = (ASTLiteral) xn.jjtGetChild(0);
195                     String str = xn.jjtGetChild(0).getImage();
196                     if (str != null) {
197                         if (literal.isStringLiteral()) {
198                             anticipatedLength += str.length() - 2;
199                         } else if (literal.isCharLiteral()) {
200                             anticipatedLength += 1;
201 	                    } else if(literal.isIntLiteral() && str.startsWith("0x")){
202 	                    	// but only if we are not inside a cast expression
203 	                    	Node parentNode = literal.jjtGetParent().jjtGetParent().jjtGetParent();
204 							if (parentNode instanceof ASTCastExpression
205 	                    		&& parentNode.getFirstChildOfType(ASTType.class).getType() == char.class) {
206 	                    		anticipatedLength += 1;
207 	                    	} else {
208     	                    	// e.g. 0xdeadbeef -> will be converted to a base 10 integer string: 3735928559
209     	                    	anticipatedLength += String.valueOf(Long.parseLong(str.substring(2), 16)).length();
210 	                    	}
211 	                    } else {
212 	                        anticipatedLength += str.length();
213 	                    }
214                     }
215                 }
216             }
217         }
218         return anticipatedLength;
219     }
220 
221     private int getConstructorLength(Node node, int constructorLength) {
222         int iConstructorLength = constructorLength;
223         Node block = node.getFirstParentOfType(ASTBlockStatement.class);
224 
225         if (block == null) {
226             block = node.getFirstParentOfType(ASTFieldDeclaration.class);
227         }
228         if (block == null) {
229             block = node.getFirstParentOfType(ASTFormalParameter.class);
230             if (block != null) {
231                 iConstructorLength = -1;
232             } else {
233             	return DEFAULT_BUFFER_SIZE;
234             }
235         }
236 
237         //if there is any addition/subtraction going on then just use the default.
238         ASTAdditiveExpression exp = block.getFirstDescendantOfType(ASTAdditiveExpression.class);
239         if (exp != null){
240             return DEFAULT_BUFFER_SIZE;
241         }
242         ASTMultiplicativeExpression mult = block.getFirstDescendantOfType(ASTMultiplicativeExpression.class);
243         if (mult != null){
244             return DEFAULT_BUFFER_SIZE;
245         }
246 
247         List<ASTLiteral> literals;
248         ASTAllocationExpression constructorCall = block.getFirstDescendantOfType(ASTAllocationExpression.class);
249         if (constructorCall != null) {
250             // if this is a constructor call, only consider the literals within it.
251             literals = constructorCall.findDescendantsOfType(ASTLiteral.class);
252         } else {
253             // otherwise it might be a setLength call...
254             literals = block.findDescendantsOfType(ASTLiteral.class);
255         }
256         if (literals.isEmpty()) {
257             List<ASTName> name = block.findDescendantsOfType(ASTName.class);
258             if (!name.isEmpty()) {
259                 iConstructorLength = -1;
260             }
261         } else if (literals.size() == 1) {
262         	ASTLiteral literal = literals.get(0);
263             String str = literal.getImage();
264             if (str == null) {
265                 iConstructorLength = 0;
266             } else if (isStringOrCharLiteral(literal)) {
267                 // since it's not taken into account
268                 // anywhere. only count the extra 16
269                 // characters
270                 iConstructorLength = 14 + str.length(); // don't add the constructor's length,
271             } else if (literal.isIntLiteral() && str.startsWith("0x")) {
272             	// bug 3516101 - the string could be a hex number
273             	iConstructorLength = Integer.parseInt(str.substring(2), 16);
274             } else {
275                 iConstructorLength = Integer.parseInt(str);
276             }
277         } else {
278             iConstructorLength = -1;
279         }
280 
281         if (iConstructorLength == 0) {
282             if (constructorLength == -1) {
283         	iConstructorLength = DEFAULT_BUFFER_SIZE;
284             } else {
285         	iConstructorLength = constructorLength;
286             }
287         }
288 
289         return iConstructorLength;
290     }
291 
292 
293     private int getInitialLength(Node node) {
294 
295     	Node block = node.getFirstParentOfType(ASTBlockStatement.class);
296 
297         if (block == null) {
298             block = node.getFirstParentOfType(ASTFieldDeclaration.class);
299             if (block == null) {
300                 block = node.getFirstParentOfType(ASTFormalParameter.class);
301             }
302         }
303         List<ASTLiteral> literals = block.findDescendantsOfType(ASTLiteral.class);
304         if (literals.size() == 1) {
305         	ASTLiteral literal = literals.get(0);
306             String str = literal.getImage();
307             if (str != null && isStringOrCharLiteral(literal)) {
308                 return str.length() - 2; // take off the quotes
309             }
310         }
311 
312         return 0;
313     }
314 
315     private int getConstructorAppendsLength(final Node node) {
316       final Node parent = node.getFirstParentOfType(ASTVariableDeclarator.class);
317        int size = 0;
318        if (parent != null) {
319          final Node initializer = parent.getFirstChildOfType(ASTVariableInitializer.class);
320          if (initializer != null) {
321              final Node primExp = initializer.getFirstDescendantOfType(ASTPrimaryExpression.class);
322              if (primExp != null) {
323                  for (int i = 0; i < primExp.jjtGetNumChildren(); i++) {
324                    final Node sn = primExp.jjtGetChild(i);
325                    if (!(sn instanceof ASTPrimarySuffix) || sn.getImage() != null) {
326                      continue;
327                    }
328                    size += processNode(sn);
329                  }
330              }
331          }
332        }
333        return size;
334     }
335 
336     private boolean isAdditive(Node n) {
337         ASTAdditiveExpression add = n.getFirstDescendantOfType(ASTAdditiveExpression.class);
338         // if the first descendant additive expression is deeper than 4 levels,
339         // it belongs to a nested method call and not anymore to the append argument.
340         return add != null && add.getNthParent(4) == n;
341     }
342 
343     /**
344      * Locate the block that the given node is in, if any
345      *
346      * @param node
347      *            The node we're looking for a parent of
348      * @return Node - The node that corresponds to any block that may be a
349      *         parent of this object
350      */
351     private Node getFirstParentBlock(Node node) {
352         Node parentNode = node.jjtGetParent();
353 
354         Node lastNode = node;
355         while (parentNode != null && !BLOCK_PARENTS.contains(parentNode.getClass())) {
356             lastNode = parentNode;
357             parentNode = parentNode.jjtGetParent();
358         }
359         if (parentNode instanceof ASTIfStatement) {
360             parentNode = lastNode;
361         } else if (parentNode instanceof ASTSwitchStatement) {
362             parentNode = getSwitchParent(parentNode, lastNode);
363         }
364         return parentNode;
365     }
366 
367     /**
368      * Determine which SwitchLabel we belong to inside a switch
369      *
370      * @param parentNode
371      *            The parent node we're looking at
372      * @param lastNode
373      *            The last node processed
374      * @return The parent node for the switch statement
375      */
376     private static Node getSwitchParent(Node parentNode, Node lastNode) {
377         int allChildren = parentNode.jjtGetNumChildren();
378         ASTSwitchLabel label = null;
379         for (int ix = 0; ix < allChildren; ix++) {
380             Node n = parentNode.jjtGetChild(ix);
381             if (n instanceof ASTSwitchLabel) {
382                 label = (ASTSwitchLabel) n;
383             } else if (n.equals(lastNode)) {
384                 parentNode = label;
385                 break;
386             }
387         }
388         return parentNode;
389     }
390 
391 }