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