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