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