1 //          Copyright Brian Schott (Hackerpilot) 2014-2015.
2 // Distributed under the Boost Software License, Version 1.0.
3 //    (See accompanying file LICENSE_1_0.txt or copy at
4 //          http://www.boost.org/LICENSE_1_0.txt)
5 module dscanner.analysis.unused;
6 
7 import dparse.ast;
8 import dparse.lexer;
9 import dscanner.analysis.base;
10 import std.container;
11 import std.regex : Regex, regex, matchAll;
12 import dsymbol.scope_ : Scope;
13 import std.algorithm : all;
14 
15 /**
16  * Checks for unused variables.
17  */
18 abstract class UnusedIdentifierCheck : BaseAnalyzer
19 {
20 	alias visit = BaseAnalyzer.visit;
21 
22 	/**
23 	 * Params:
24 	 *     fileName = the name of the file being analyzed
25 	 */
26 	this(string fileName, const(Scope)* sc, bool skipTests = false)
27 	{
28 		super(fileName, sc, skipTests);
29 		re = regex("[\\p{Alphabetic}_][\\w_]*");
30 	}
31 
32 	override void visit(const Module mod)
33 	{
34 		pushScope();
35 		mod.accept(this);
36 		popScope();
37 	}
38 
39 	override void visit(const Declaration declaration)
40 	{
41 		if (!isOverride)
42 			foreach (attribute; declaration.attributes)
43 				isOverride = isOverride || (attribute.attribute == tok!"override");
44 		declaration.accept(this);
45 		isOverride = false;
46 	}
47 
48 	override void visit(const FunctionDeclaration functionDec)
49 	{
50 		pushScope();
51 		if (functionDec.functionBody && functionDec.functionBody.specifiedFunctionBody)
52 		{
53 			immutable bool ias = inAggregateScope;
54 			inAggregateScope = false;
55 			if (!isOverride)
56 				functionDec.parameters.accept(this);
57 			functionDec.functionBody.accept(this);
58 			inAggregateScope = ias;
59 		}
60 		popScope();
61 	}
62 
63 	mixin PartsUseVariables!AliasInitializer;
64 	mixin PartsUseVariables!ArgumentList;
65 	mixin PartsUseVariables!AssertExpression;
66 	mixin PartsUseVariables!ClassDeclaration;
67 	mixin PartsUseVariables!FunctionBody;
68 	mixin PartsUseVariables!FunctionCallExpression;
69 	mixin PartsUseVariables!FunctionDeclaration;
70 	mixin PartsUseVariables!IndexExpression;
71 	mixin PartsUseVariables!Initializer;
72 	mixin PartsUseVariables!InterfaceDeclaration;
73 	mixin PartsUseVariables!NewExpression;
74 	mixin PartsUseVariables!StaticIfCondition;
75 	mixin PartsUseVariables!StructDeclaration;
76 	mixin PartsUseVariables!TemplateArgumentList;
77 	mixin PartsUseVariables!ThrowStatement;
78 	mixin PartsUseVariables!CastExpression;
79 
80 	override void visit(const SwitchStatement switchStatement)
81 	{
82 		if (switchStatement.expression !is null)
83 		{
84 			interestDepth++;
85 			switchStatement.expression.accept(this);
86 			interestDepth--;
87 		}
88 		switchStatement.accept(this);
89 	}
90 
91 	override void visit(const WhileStatement whileStatement)
92 	{
93 		if (whileStatement.expression !is null)
94 		{
95 			interestDepth++;
96 			whileStatement.expression.accept(this);
97 			interestDepth--;
98 		}
99 		if (whileStatement.declarationOrStatement !is null)
100 			whileStatement.declarationOrStatement.accept(this);
101 	}
102 
103 	override void visit(const DoStatement doStatement)
104 	{
105 		if (doStatement.expression !is null)
106 		{
107 			interestDepth++;
108 			doStatement.expression.accept(this);
109 			interestDepth--;
110 		}
111 		if (doStatement.statementNoCaseNoDefault !is null)
112 			doStatement.statementNoCaseNoDefault.accept(this);
113 	}
114 
115 	override void visit(const ForStatement forStatement)
116 	{
117 		if (forStatement.initialization !is null)
118 			forStatement.initialization.accept(this);
119 		if (forStatement.test !is null)
120 		{
121 			interestDepth++;
122 			forStatement.test.accept(this);
123 			interestDepth--;
124 		}
125 		if (forStatement.increment !is null)
126 		{
127 			interestDepth++;
128 			forStatement.increment.accept(this);
129 			interestDepth--;
130 		}
131 		if (forStatement.declarationOrStatement !is null)
132 			forStatement.declarationOrStatement.accept(this);
133 	}
134 
135 	override void visit(const IfStatement ifStatement)
136 	{
137 		if (ifStatement.expression !is null)
138 		{
139 			interestDepth++;
140 			ifStatement.expression.accept(this);
141 			interestDepth--;
142 		}
143 		if (ifStatement.thenStatement !is null)
144 			ifStatement.thenStatement.accept(this);
145 		if (ifStatement.elseStatement !is null)
146 			ifStatement.elseStatement.accept(this);
147 	}
148 
149 	override void visit(const ForeachStatement foreachStatement)
150 	{
151 		if (foreachStatement.low !is null)
152 		{
153 			interestDepth++;
154 			foreachStatement.low.accept(this);
155 			interestDepth--;
156 		}
157 		if (foreachStatement.high !is null)
158 		{
159 			interestDepth++;
160 			foreachStatement.high.accept(this);
161 			interestDepth--;
162 		}
163 		foreachStatement.accept(this);
164 	}
165 
166 	override void visit(const AssignExpression assignExp)
167 	{
168 		interestDepth++;
169 		assignExp.accept(this);
170 		interestDepth--;
171 	}
172 
173 	override void visit(const TemplateDeclaration templateDeclaration)
174 	{
175 		immutable inAgg = inAggregateScope;
176 		inAggregateScope = true;
177 		templateDeclaration.accept(this);
178 		inAggregateScope = inAgg;
179 	}
180 
181 	override void visit(const IdentifierOrTemplateChain chain)
182 	{
183 		if (interestDepth > 0 && chain.identifiersOrTemplateInstances[0].identifier != tok!"")
184 			variableUsed(chain.identifiersOrTemplateInstances[0].identifier.text);
185 		chain.accept(this);
186 	}
187 
188 	override void visit(const TemplateSingleArgument single)
189 	{
190 		if (single.token != tok!"")
191 			variableUsed(single.token.text);
192 	}
193 
194 	override void visit(const UnaryExpression unary)
195 	{
196 		const bool interesting = unary.prefix == tok!"*" || unary.unaryExpression !is null;
197 		interestDepth += interesting;
198 		unary.accept(this);
199 		interestDepth -= interesting;
200 	}
201 
202 	override void visit(const MixinExpression mix)
203 	{
204 		interestDepth++;
205 		mixinDepth++;
206 		mix.accept(this);
207 		mixinDepth--;
208 		interestDepth--;
209 	}
210 
211 	override void visit(const PrimaryExpression primary)
212 	{
213 		if (interestDepth > 0)
214 		{
215 			const IdentifierOrTemplateInstance idt = primary.identifierOrTemplateInstance;
216 
217 			if (idt !is null)
218 			{
219 				if (idt.identifier != tok!"")
220 					variableUsed(idt.identifier.text);
221 				else if (idt.templateInstance && idt.templateInstance.identifier != tok!"")
222 					variableUsed(idt.templateInstance.identifier.text);
223 			}
224 			if (mixinDepth > 0 && primary.primary == tok!"stringLiteral"
225 					|| primary.primary == tok!"wstringLiteral"
226 					|| primary.primary == tok!"dstringLiteral")
227 			{
228 				foreach (part; matchAll(primary.primary.text, re))
229 				{
230 					void checkTree(in size_t treeIndex)
231 					{
232 						auto uu = UnUsed(part.hit);
233 						auto r = tree[treeIndex].equalRange(&uu);
234 						if (!r.empty)
235 							r.front.uncertain = true;
236 					}
237 					checkTree(tree.length - 1);
238 					if (tree.length >= 2)
239 						checkTree(tree.length - 2);
240 				}
241 			}
242 		}
243 		primary.accept(this);
244 	}
245 
246 	override void visit(const ReturnStatement retStatement)
247 	{
248 		if (retStatement.expression !is null)
249 		{
250 			interestDepth++;
251 			visit(retStatement.expression);
252 			interestDepth--;
253 		}
254 	}
255 
256 	override void visit(const BlockStatement blockStatement)
257 	{
258 		immutable bool sb = inAggregateScope;
259 		inAggregateScope = false;
260 		if (blockStatementIntroducesScope)
261 			pushScope();
262 		blockStatement.accept(this);
263 		if (blockStatementIntroducesScope)
264 			popScope();
265 		inAggregateScope = sb;
266 	}
267 
268 	override void visit(const Type2 tp)
269 	{
270 		if (tp.typeIdentifierPart &&
271 			tp.typeIdentifierPart.identifierOrTemplateInstance)
272 		{
273 			const IdentifierOrTemplateInstance idt = tp.typeIdentifierPart.identifierOrTemplateInstance;
274 			if (idt.identifier != tok!"")
275 				variableUsed(idt.identifier.text);
276 			else if (idt.templateInstance)
277 			{
278 				const TemplateInstance ti = idt.templateInstance;
279 				if (ti.identifier != tok!"")
280 					variableUsed(idt.templateInstance.identifier.text);
281 				if (ti.templateArguments && ti.templateArguments.templateSingleArgument)
282 					variableUsed(ti.templateArguments.templateSingleArgument.token.text);
283 			}
284 		}
285 		tp.accept(this);
286 	}
287 
288 	override void visit(const WithStatement withStatetement)
289 	{
290 		interestDepth++;
291 		if (withStatetement.expression)
292 			withStatetement.expression.accept(this);
293 		interestDepth--;
294 		if (withStatetement.declarationOrStatement)
295 			withStatetement.declarationOrStatement.accept(this);
296 	}
297 
298 	override void visit(const StructBody structBody)
299 	{
300 		immutable bool sb = inAggregateScope;
301 		inAggregateScope = true;
302 		foreach (dec; structBody.declarations)
303 			visit(dec);
304 		inAggregateScope = sb;
305 	}
306 
307 	override void visit(const ConditionalStatement conditionalStatement)
308 	{
309 		immutable bool cs = blockStatementIntroducesScope;
310 		blockStatementIntroducesScope = false;
311 		conditionalStatement.accept(this);
312 		blockStatementIntroducesScope = cs;
313 	}
314 
315 	override void visit(const AsmPrimaryExp primary)
316 	{
317 		if (primary.token != tok!"")
318 			variableUsed(primary.token.text);
319 		if (primary.identifierChain !is null)
320 			variableUsed(primary.identifierChain.identifiers[0].text);
321 	}
322 
323 	override void visit(const TraitsExpression)
324 	{
325 		// issue #266: Ignore unused variables inside of `__traits` expressions
326 	}
327 
328 	override void visit(const TypeofExpression)
329 	{
330 		// issue #270: Ignore unused variables inside of `typeof` expressions
331 	}
332 
333 	abstract protected void popScope();
334 
335 	protected uint interestDepth;
336 
337 	protected Tree[] tree;
338 
339 	protected void variableDeclared(string name, size_t line, size_t column, bool isRef)
340 	{
341 		if (inAggregateScope || name.all!(a => a == '_'))
342 			return;
343 		tree[$ - 1].insert(new UnUsed(name, line, column, isRef));
344 	}
345 
346 	protected void pushScope()
347 	{
348 		tree ~= new Tree;
349 	}
350 
351 private:
352 
353 	struct UnUsed
354 	{
355 		string name;
356 		size_t line;
357 		size_t column;
358 		bool isRef;
359 		bool uncertain;
360 	}
361 
362 	alias Tree = RedBlackTree!(UnUsed*, "a.name < b.name");
363 
364 	mixin template PartsUseVariables(NodeType)
365 	{
366 		override void visit(const NodeType node)
367 		{
368 			interestDepth++;
369 			node.accept(this);
370 			interestDepth--;
371 		}
372 	}
373 
374 	void variableUsed(string name)
375 	{
376 		size_t treeIndex = tree.length - 1;
377 		auto uu = UnUsed(name);
378 		while (true)
379 		{
380 			if (tree[treeIndex].removeKey(&uu) != 0 || treeIndex == 0)
381 				break;
382 			treeIndex--;
383 		}
384 	}
385 
386 	Regex!char re;
387 
388 	bool inAggregateScope;
389 
390 	uint mixinDepth;
391 
392 	bool isOverride;
393 
394 	bool blockStatementIntroducesScope = true;
395 }
396 
397 /// Base class for unused parameter/variables checks
398 abstract class UnusedStorageCheck : UnusedIdentifierCheck
399 {
400 	alias visit = UnusedIdentifierCheck.visit;
401 
402 	/**
403 	Ignore declarations which are allowed to be unused, e.g. inside of a
404 	speculative compilation: __traits(compiles, { S s = 0; })
405 	**/
406 	uint ignoreDeclarations = 0;
407 
408 	/// Kind of declaration for error messages e.g. "Variable"
409 	const string publicType;
410 
411 	/// Kind of declaration for error reports e.g. "unused_variable"
412 	const string reportType;
413 
414 	/**
415 	 * Params:
416 	 *      fileName	= the name of the file being analyzed
417 	 *		sc			= the scope
418 	 *		skipTest	= whether tests should be analyzed
419 	 *		publicType	= declaration kind used in error messages, e.g. "Variable"s
420 	 *		reportType	= declaration kind used in error reports, e.g. "unused_variable"
421 	 */
422 	this(string fileName, const(Scope)* sc, bool skipTests = false, string publicType = null, string reportType = null)
423 	{
424 		super(fileName, sc, skipTests);
425 		this.publicType = publicType;
426 		this.reportType = reportType;
427 	}
428 
429 	override void visit(const TraitsExpression traitsExp)
430 	{
431 		// issue #788: Enum values might be used inside of `__traits` expressions, e.g.:
432 		// enum name = "abc";
433 		// __traits(hasMember, S, name);
434 		ignoreDeclarations++;
435 		traitsExp.templateArgumentList.accept(this);
436 		ignoreDeclarations--;
437 	}
438 
439 	override final protected void popScope()
440 	{
441 		if (!ignoreDeclarations)
442 		{
443 			foreach (uu; tree[$ - 1])
444 			{
445 				if (!uu.isRef && tree.length > 1)
446 				{
447 					if (uu.uncertain)
448 						continue;
449 					immutable string errorMessage = publicType ~ ' ' ~ uu.name ~ " is never used.";
450 					addErrorMessage(uu.line, uu.column,
451 							"dscanner.suspicious." ~ reportType, errorMessage);
452 				}
453 			}
454 		}
455 		tree = tree[0 .. $ - 1];
456 	}
457 }