dextool.plugin.mutate.backend.generate

1 /**
2 Copyright: Copyright (c) 2017, Joakim Brännström. All rights reserved.
3 License: MPL-2
4 Author: Joakim Brännström (joakim.brannstrom@gmx.com)
5 
6 This Source Code Form is subject to the terms of the Mozilla Public License,
7 v.2.0. If a copy of the MPL was not distributed with this file, You can obtain
8 one at http://mozilla.org/MPL/2.0/.
9 
10 This file contains functionality to take an unprocessed mutation point and
11 generate a mutant for it.
12 */
13 module dextool.plugin.mutate.backend.generate_mutant;
14 
15 import logger = std.experimental.logger;
16 import std.exception : collectException;
17 import std.path : buildPath;
18 import std.typecons : Nullable;
19 import std.utf : validate;
20 
21 import dextool.type : AbsolutePath, ExitStatusType, FileName, DirName;
22 import dextool.plugin.mutate.backend.database : Database, MutationEntry, MutationId, spinSqlQuery;
23 import dextool.plugin.mutate.backend.type : Language;
24 import dextool.plugin.mutate.backend.interface_ : FilesysIO, SafeOutput, ValidateLoc;
25 import dextool.plugin.mutate.type : MutationKind;
26 
27 import blob_model : Blob, Edit, change, Interval, Uri, merge;
28 
29 enum GenerateMutantStatus {
30     error,
31     filesysError,
32     databaseError,
33     checksumError,
34     noMutation,
35     ok
36 }
37 
38 ExitStatusType runGenerateMutant(ref Database db, MutationKind[] kind,
39         Nullable!long user_mutation, FilesysIO fio, ValidateLoc val_loc) @safe nothrow {
40     import dextool.plugin.mutate.backend.utility : toInternal;
41 
42     Nullable!MutationEntry mutp;
43     if (!user_mutation.isNull) {
44         mutp = spinSqlQuery!(() {
45             return db.getMutation(MutationId(user_mutation.get));
46         });
47         logger.error(mutp.isNull, "No such mutation id: ", user_mutation.get).collectException;
48     } else {
49         auto next_m = spinSqlQuery!(() { return db.nextMutation(kind.toInternal); });
50         mutp = next_m.entry;
51     }
52     if (mutp.isNull)
53         return ExitStatusType.Errors;
54 
55     AbsolutePath mut_file;
56     try {
57         mut_file = AbsolutePath(FileName(mutp.file), DirName(fio.getOutputDir));
58     } catch (Exception e) {
59         logger.error(e.msg).collectException;
60         return ExitStatusType.Errors;
61     }
62 
63     Blob content;
64     try {
65         content = fio.makeInput(mut_file);
66     } catch (Exception e) {
67         collectException(logger.error(e.msg));
68         return ExitStatusType.Errors;
69     }
70 
71     ExitStatusType exit_st;
72     try {
73         auto ofile = makeOutputFilename(val_loc, fio, mut_file);
74         auto fout = fio.makeOutput(ofile);
75         auto res = generateMutant(db, mutp, content, fout);
76         if (res.status == GenerateMutantStatus.ok) {
77             logger.infof("%s Mutate from '%s' to '%s' in %s", mutp.id,
78                     cast(const(char)[]) res.from, cast(const(char)[]) res.to, ofile);
79             exit_st = ExitStatusType.Ok;
80         }
81     } catch (Exception e) {
82         collectException(logger.error(e.msg));
83     }
84 
85     return exit_st;
86 }
87 
88 private AbsolutePath makeOutputFilename(ValidateLoc val_loc, FilesysIO fio, AbsolutePath file) @safe {
89     import std.path;
90     import dextool.type : FileName;
91 
92     if (val_loc.shouldMutate(file))
93         return file;
94 
95     return AbsolutePath(FileName(buildPath(fio.getOutputDir, file.baseName)));
96 }
97 
98 struct GenerateMutantResult {
99     GenerateMutantStatus status;
100     const(ubyte)[] from;
101     const(ubyte)[] to;
102 }
103 
104 auto generateMutant(ref Database db, MutationEntry mutp, Blob original, ref SafeOutput fout) @safe nothrow {
105     import dextool.plugin.mutate.backend.utility : checksum, Checksum;
106 
107     if (mutp.mp.mutations.length == 0)
108         return GenerateMutantResult(GenerateMutantStatus.noMutation);
109 
110     Nullable!Checksum db_checksum;
111     try {
112         db_checksum = db.getFileChecksum(mutp.file);
113     } catch (Exception e) {
114         logger.warning(e.msg).collectException;
115         return GenerateMutantResult(GenerateMutantStatus.databaseError);
116     }
117 
118     Checksum f_checksum;
119     try {
120         f_checksum = checksum(original.content);
121     } catch (Exception e) {
122         logger.warning(e.msg).collectException;
123         return GenerateMutantResult(GenerateMutantStatus.filesysError);
124     }
125 
126     if (db_checksum.isNull) {
127         logger.errorf("Database contains erroneous data. A mutation point for %s exist but the file has no checksum",
128                 mutp.file).collectException;
129         return GenerateMutantResult(GenerateMutantStatus.databaseError);
130     } else if (db_checksum != f_checksum) {
131         logger.errorf(
132                 "Unable to mutate %s (%s%s) because the checksum is different from the one in the database (%s%s)",
133                 mutp.file, f_checksum.c0,
134                 f_checksum.c1, db_checksum.c0, db_checksum.c1).collectException;
135         return GenerateMutantResult(GenerateMutantStatus.checksumError);
136     }
137 
138     auto mut = makeMutation(mutp.mp.mutations[0].kind, mutp.lang);
139 
140     try {
141         Edit[] edits;
142         edits ~= new Edit(Interval(0, 0), mut.top());
143 
144         auto from_ = original.content[mutp.mp.offset.begin .. mutp.mp.offset.end];
145         auto to_ = mut.mutate(from_);
146 
147         edits ~= new Edit(Interval(mutp.mp.offset.begin, mutp.mp.offset.end), to_);
148 
149         // #SPC-file_security-header_as_warning
150         edits ~= new Edit(Interval.append, "\n/* DEXTOOL: THIS FILE IS MUTATED */");
151 
152         auto blob = new Blob(original.uri, original.content);
153         auto m = merge(blob, edits);
154         blob = change(blob, m.edits);
155 
156         fout.write(blob.content);
157 
158         return GenerateMutantResult(GenerateMutantStatus.ok, from_, to_);
159     } catch (Exception e) {
160         return GenerateMutantResult(GenerateMutantStatus.filesysError);
161     }
162 }
163 
164 auto makeMutation(Mutation.Kind kind, Language lang) {
165     import std.format : format;
166 
167     static auto toB(string s) @safe {
168         return cast(const(ubyte)[]) s;
169     }
170 
171     MutateImpl m;
172     m.top = () { return null; };
173     m.mutate = (const(ubyte)[] from) { return null; };
174 
175     auto clangTrue(const(ubyte)[]) {
176         if (lang == Language.c)
177             return toB("1");
178         else
179             return toB("true");
180     }
181 
182     auto clangFalse(const(ubyte)[]) {
183         if (lang == Language.c)
184             return cast(const(ubyte)[]) "0";
185         else
186             return cast(const(ubyte)[]) "false";
187     }
188 
189     final switch (kind) with (Mutation.Kind) {
190         /// the kind is not initialized thus can only ignore the point
191     case none:
192         break;
193         /// Relational operator replacement
194     case rorLT:
195         goto case;
196     case rorpLT:
197         m.mutate = (const(ubyte)[] expr) { return toB("<"); };
198         break;
199     case rorLE:
200         goto case;
201     case rorpLE:
202         m.mutate = (const(ubyte)[] expr) { return toB("<="); };
203         break;
204     case rorGT:
205         goto case;
206     case rorpGT:
207         m.mutate = (const(ubyte)[] expr) { return toB(">"); };
208         break;
209     case rorGE:
210         goto case;
211     case rorpGE:
212         m.mutate = (const(ubyte)[] expr) { return toB(">="); };
213         break;
214     case rorEQ:
215         goto case;
216     case rorpEQ:
217         m.mutate = (const(ubyte)[] expr) { return toB("=="); };
218         break;
219     case rorNE:
220         goto case;
221     case rorpNE:
222         m.mutate = (const(ubyte)[] expr) { return toB("!="); };
223         break;
224     case rorTrue:
225         m.mutate = &clangTrue;
226         break;
227     case rorFalse:
228         m.mutate = &clangFalse;
229         break;
230         /// Logical connector replacement
231         /// #SPC-mutation_lcr
232     case lcrAnd:
233         m.mutate = (const(ubyte)[] expr) { return toB("&&"); };
234         break;
235     case lcrOr:
236         m.mutate = (const(ubyte)[] expr) { return toB("||"); };
237         break;
238     case lcrLhs:
239         goto case;
240     case lcrRhs:
241         m.mutate = (const(ubyte)[] expr) { return toB(""); };
242         break;
243     case lcrTrue:
244         m.mutate = &clangTrue;
245         break;
246     case lcrFalse:
247         m.mutate = &clangFalse;
248         break;
249         /// Arithmetic operator replacement
250         /// #SPC-mutation_aor
251     case aorMul:
252         m.mutate = (const(ubyte)[] expr) { return toB("*"); };
253         break;
254     case aorDiv:
255         m.mutate = (const(ubyte)[] expr) { return toB("/"); };
256         break;
257     case aorRem:
258         m.mutate = (const(ubyte)[] expr) { return toB("%"); };
259         break;
260     case aorAdd:
261         m.mutate = (const(ubyte)[] expr) { return toB("+"); };
262         break;
263     case aorSub:
264         m.mutate = (const(ubyte)[] expr) { return toB("-"); };
265         break;
266     case aorMulAssign:
267         m.mutate = (const(ubyte)[] expr) { return toB("*="); };
268         break;
269     case aorDivAssign:
270         m.mutate = (const(ubyte)[] expr) { return toB("/="); };
271         break;
272     case aorRemAssign:
273         m.mutate = (const(ubyte)[] expr) { return toB("%="); };
274         break;
275     case aorAddAssign:
276         m.mutate = (const(ubyte)[] expr) { return toB("+="); };
277         break;
278     case aorSubAssign:
279         m.mutate = (const(ubyte)[] expr) { return toB("-="); };
280         break;
281     case aorLhs:
282         goto case;
283     case aorRhs:
284         m.mutate = (const(ubyte)[] expr) { return toB(""); };
285         break;
286         /// Unary operator insert on an lvalue
287         /// #SPC-mutation_uoi
288     case uoiPostInc:
289         m.mutate = (const(ubyte)[] expr) { return expr ~ toB("++"); };
290         break;
291     case uoiPostDec:
292         m.mutate = (const(ubyte)[] expr) { return expr ~ toB("--"); };
293         break;
294         // these work for rvalue
295     case uoiPreInc:
296         m.mutate = (const(ubyte)[] expr) { return toB("++") ~ expr; };
297         break;
298     case uoiPreDec:
299         m.mutate = (const(ubyte)[] expr) { return toB("--") ~ expr; };
300         break;
301     case uoiAddress:
302         m.mutate = (const(ubyte)[] expr) { return toB("&") ~ expr; };
303         break;
304     case uoiIndirection:
305         m.mutate = (const(ubyte)[] expr) { return toB("*") ~ expr; };
306         break;
307     case uoiPositive:
308         m.mutate = (const(ubyte)[] expr) { return toB("+") ~ expr; };
309         break;
310     case uoiNegative:
311         m.mutate = (const(ubyte)[] expr) { return toB("-") ~ expr; };
312         break;
313     case uoiComplement:
314         m.mutate = (const(ubyte)[] expr) { return toB("~") ~ expr; };
315         break;
316     case uoiNegation:
317         m.mutate = (const(ubyte)[] expr) { return toB("!") ~ expr; };
318         break;
319     case uoiSizeof_:
320         m.mutate = (const(ubyte)[] expr) { return toB("sizeof(") ~ expr ~ toB(")"); };
321         break;
322         /// Absolute value replacement
323         /// #SPC-mutation_abs
324     case absPos:
325         m.top = () { return toB(preambleAbs); };
326         m.mutate = (const(ubyte)[] b) { return toB("abs_dextool(") ~ b ~ toB(")"); };
327         break;
328     case absNeg:
329         m.top = () { return toB(preambleAbs); };
330         m.mutate = (const(ubyte)[] b) { return toB("-abs_dextool(") ~ b ~ toB(")"); };
331         break;
332     case absZero:
333         m.top = () { return toB(preambleAbs); };
334         m.mutate = (const(ubyte)[] b) {
335             return toB("fail_on_zero_dextool(") ~ b ~ toB(")");
336         };
337         break;
338     case stmtDel:
339         /// #SPC-mutations_statement_del
340         // delete by commenting out the code block
341         m.mutate = (const(ubyte)[] expr) { return toB(""); };
342         break;
343         /// Conditional Operator Replacement (reduced set)
344         /// #SPC-mutation_cor
345     case corAnd:
346         assert(0);
347     case corOr:
348         assert(0);
349     case corFalse:
350         m.mutate = &clangFalse;
351         break;
352     case corLhs:
353         m.mutate = (const(ubyte)[] expr) { return toB(""); };
354         break;
355     case corRhs:
356         m.mutate = (const(ubyte)[] expr) { return toB(""); };
357         break;
358     case corEQ:
359         m.mutate = (const(ubyte)[] expr) { return toB("=="); };
360         break;
361     case corNE:
362         m.mutate = (const(ubyte)[] expr) { return toB("!="); };
363         break;
364     case corTrue:
365         m.mutate = &clangTrue;
366         break;
367     case dccTrue:
368         m.mutate = &clangTrue;
369         break;
370     case dccFalse:
371         m.mutate = &clangFalse;
372         break;
373     case dccBomb:
374         // assigning null should crash the program, thus a 'bomb'
375         m.mutate = (const(ubyte)[] expr) { return toB(`*((char*)0)='x';break;`); };
376         break;
377     case dcrCaseDel:
378         m.mutate = (const(ubyte)[] expr) { return toB(""); };
379         break;
380     case lcrbAnd:
381         m.mutate = (const(ubyte)[] expr) { return toB("&"); };
382         break;
383     case lcrbOr:
384         m.mutate = (const(ubyte)[] expr) { return toB("|"); };
385         break;
386     case lcrbAndAssign:
387         m.mutate = (const(ubyte)[] expr) { return toB("&="); };
388         break;
389     case lcrbOrAssign:
390         m.mutate = (const(ubyte)[] expr) { return toB("|="); };
391         break;
392     case lcrbLhs:
393         goto case;
394     case lcrbRhs:
395         m.mutate = (const(ubyte)[] expr) { return toB(""); };
396         break;
397     }
398 
399     return m;
400 }
401 
402 @safe struct MakeMutationTextResult {
403     import std.utf : validate;
404 
405     static immutable originalIsCorrupt = "Dextool: unable to open the file or it has changed since mutation where performed";
406 
407     const(ubyte)[] rawOriginal = cast(const(ubyte)[]) originalIsCorrupt;
408     const(ubyte)[] rawMutation;
409 
410     const(char)[] original() const {
411         auto r = cast(const(char)[]) rawOriginal;
412         validate(r);
413         return r;
414     }
415 
416     const(char)[] mutation() const {
417         auto r = cast(const(char)[]) rawMutation;
418         validate(r);
419         return r;
420     }
421 
422     size_t toHash() nothrow @safe const {
423         import dextool.hash;
424 
425         BuildChecksum128 hash;
426         hash.put(rawOriginal);
427         hash.put(rawMutation);
428         return hash.toChecksum128.toHash;
429     }
430 
431     bool opEquals(const typeof(this) o) const nothrow @safe {
432         return rawOriginal == o.rawOriginal && rawMutation == o.rawMutation;
433     }
434 }
435 
436 /// Returns: a snippet of the mutation if it is OK otherwise an empty snippet.
437 auto makeMutationText(Blob file_, const Offset offs, Mutation.Kind kind, Language lang) @safe {
438     import dextool.plugin.mutate.backend.generate_mutant : makeMutation;
439 
440     MakeMutationTextResult rval;
441 
442     if (offs.begin < offs.end && offs.end < file_.content.length) {
443         rval.rawOriginal = file_.content[offs.begin .. offs.end];
444     }
445 
446     auto mut = makeMutation(kind, lang);
447     rval.rawMutation = mut.mutate(rval.rawOriginal);
448 
449     return rval;
450 }
451 
452 private:
453 @safe:
454 
455 import dextool.plugin.mutate.backend.type : Offset, Mutation;
456 
457 struct MutateImpl {
458     alias CallbackTop = const(ubyte)[]delegate() @safe;
459     alias CallbackMut = const(ubyte)[]delegate(const(ubyte)[] from) @safe;
460 
461     /// Called before any other data has been written to the file.
462     CallbackTop top;
463 
464     /// Called at the mutation point.
465     CallbackMut mutate;
466 }
467 
468 immutable string preambleAbs;
469 
470 shared static this() {
471     // this is ugly but works for now
472     preambleAbs = `
473 #ifndef DEXTOOL_INJECTED_ABS_FUNCTION
474 #define DEXTOOL_INJECTED_ABS_FUNCTION
475 #define abs_dextool(v) (v < 0 ? -v : v)
476 #endif
477 #ifndef DEXTOOL_INJECTED_FAIL_ON_ZERO_FUNCTION
478 #define DEXTOOL_INJECTED_FAIL_ON_ZERO_FUNCTION
479 #define fail_on_zero_dextool(v) (!v && (*((char*)0) = 'x') ? v : v)
480 #endif
481 `;
482 }
483 
484 auto drop(T = void[])(T content, const Offset offset) {
485     return DropRange!T(content[0 .. offset.begin], content[offset.end .. $]);
486 }
487 
488 struct DropRange(T) {
489     private {
490         T[2] data;
491         size_t idx;
492     }
493 
494     this(T d0, T d1) {
495         data = [d0, d1];
496     }
497 
498     T front() @safe pure nothrow {
499         assert(!empty, "Can't get front of an empty range");
500         return data[idx];
501     }
502 
503     void popFront() @safe pure nothrow {
504         assert(!empty, "Can't pop front of an empty range");
505         ++idx;
506     }
507 
508     bool empty() @safe pure nothrow const @nogc {
509         return idx == data.length;
510     }
511 }