dextool.plugin.mutate.backend.analyze.pass

1 /**
2 Copyright: Copyright (c) 2020, 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 module dextool.plugin.mutate.backend.analyze.pass_clang;
11 
12 import logger = std.experimental.logger;
13 import std.algorithm : among, map, sort, filter;
14 import std.array : empty, array, appender, Appender;
15 import std.exception : collectException;
16 import std.format : formattedWrite;
17 import std.meta : AliasSeq;
18 import std.typecons : Nullable;
19 
20 import blob_model : Blob;
21 import my.container.vector : vector, Vector;
22 import my.gc.refc : RefCounted;
23 import my.optional;
24 
25 static import colorlog;
26 
27 import clang.Cursor : Cursor;
28 import clang.Eval : Eval;
29 import clang.Type : Type;
30 import clang.c.Index : CXTypeKind, CXCursorKind, CXEvalResultKind, CXTokenKind;
31 
32 import libclang_ast.ast : Visitor;
33 import libclang_ast.cursor_logger : logNode, mixinNodeLog;
34 
35 import dextool.clang_extensions : getUnderlyingExprNode;
36 
37 import dextool.type : Path, AbsolutePath;
38 
39 import dextool.plugin.mutate.backend.analyze.ast : Interval, Location, TypeKind,
40     Node, Ast, BreathFirstRange;
41 import dextool.plugin.mutate.backend.analyze.extensions;
42 import dextool.plugin.mutate.backend.analyze.utility;
43 import dextool.plugin.mutate.backend.interface_ : FilesysIO, InvalidPathException, ValidateLoc;
44 import dextool.plugin.mutate.backend.type : Language, SourceLoc, Offset, SourceLocRange;
45 
46 import analyze = dextool.plugin.mutate.backend.analyze.ast;
47 
48 alias accept = dextool.plugin.mutate.backend.analyze.extensions.accept;
49 
50 alias log = colorlog.log!"analyze.pass_clang";
51 
52 shared static this() {
53     colorlog.make!(colorlog.SimpleLogger)(logger.LogLevel.info, "analyze.pass_clang");
54 }
55 
56 /** Translate a clang AST to a mutation AST.
57  */
58 ClangResult toMutateAst(const Cursor root, FilesysIO fio, ValidateLoc vloc) @safe {
59     import libclang_ast.ast;
60 
61     auto visitor = new BaseVisitor(fio, vloc);
62     scope (exit)
63         visitor.dispose;
64     auto ast = ClangAST!BaseVisitor(root);
65     ast.accept(visitor);
66     visitor.ast.get.releaseCache;
67 
68     auto rval = ClangResult(visitor.ast, visitor.includes.data);
69     return rval;
70 }
71 
72 struct ClangResult {
73     RefCounted!(analyze.Ast) ast;
74 
75     /// All dependencies that the root has.
76     Path[] dependencies;
77 }
78 
79 private:
80 
81 struct OperatorCursor {
82     analyze.Expr astOp;
83 
84     // true if the operator is overloaded.
85     bool isOverload;
86 
87     // the whole expression
88     analyze.Location exprLoc;
89     DeriveCursorTypeResult exprTy;
90 
91     // the operator itself
92     analyze.Operator operator;
93     analyze.Location opLoc;
94 
95     Cursor lhs;
96     Cursor rhs;
97 
98     /// Add the result to the AST and astOp to the parent.
99     /// astOp is set to have two children, lhs and rhs.
100     void put(analyze.Node parent, ref analyze.Ast ast) @safe {
101         ast.put(astOp, exprLoc);
102         ast.put(operator, opLoc);
103 
104         exprTy.put(ast);
105 
106         if (exprTy.type !is null)
107             ast.put(astOp, exprTy.id);
108 
109         if (exprTy.symbol !is null)
110             ast.put(astOp, exprTy.symId);
111 
112         parent.children ~= astOp;
113     }
114 }
115 
116 Nullable!OperatorCursor operatorCursor(T)(ref Ast ast, T node) {
117     import dextool.clang_extensions : getExprOperator, OpKind, ValueKind, getUnderlyingExprNode;
118 
119     auto op = getExprOperator(node.cursor);
120     if (!op.isValid)
121         return typeof(return)();
122 
123     auto path = op.cursor.location.path.Path;
124     if (path.empty)
125         return typeof(return)();
126 
127     OperatorCursor res;
128 
129     void sidesPoint() {
130         auto sides = op.sides;
131         if (sides.lhs.isValid) {
132             res.lhs = getUnderlyingExprNode(sides.lhs);
133         }
134         if (sides.rhs.isValid) {
135             res.rhs = getUnderlyingExprNode(sides.rhs);
136         }
137     }
138 
139     // the operator itself
140     void opPoint() {
141         auto loc = op.location;
142         auto sr = loc.spelling;
143         res.operator = ast.make!(analyze.Operator);
144         res.opLoc = analyze.Location(path, Interval(sr.offset,
145                 cast(uint)(sr.offset + op.length)), SourceLocRange(SourceLoc(loc.line,
146                 loc.column), SourceLoc(loc.line, cast(uint)(loc.column + op.length))));
147     }
148 
149     // the arguments and the operator
150     void exprPoint() {
151         auto sr = op.cursor.extent;
152         res.exprLoc = analyze.Location(path, Interval(sr.start.offset,
153                 sr.end.offset), SourceLocRange(SourceLoc(sr.start.line,
154                 sr.start.column), SourceLoc(sr.end.line, sr.end.column)));
155         res.exprTy = deriveCursorType(ast, op.cursor);
156         switch (op.kind) with (OpKind) {
157         case OO_Star: // "*"
158             res.isOverload = true;
159             goto case;
160         case Mul: // "*"
161             res.astOp = ast.make!(analyze.OpMul);
162             break;
163         case OO_Slash: // "/"
164             res.isOverload = true;
165             goto case;
166         case Div: // "/"
167             res.astOp = ast.make!(analyze.OpDiv);
168             break;
169         case OO_Percent: // "%"
170             res.isOverload = true;
171             goto case;
172         case Rem: // "%"
173             res.astOp = ast.make!(analyze.OpMod);
174             break;
175         case OO_Plus: // "+"
176             res.isOverload = true;
177             goto case;
178         case Add: // "+"
179             res.astOp = ast.make!(analyze.OpAdd);
180             break;
181         case OO_Minus: // "-"
182             res.isOverload = true;
183             goto case;
184         case Sub: // "-"
185             res.astOp = ast.make!(analyze.OpSub);
186             break;
187         case OO_Less: // "<"
188             res.isOverload = true;
189             goto case;
190         case LT: // "<"
191             res.astOp = ast.make!(analyze.OpLess);
192             break;
193         case OO_Greater: // ">"
194             res.isOverload = true;
195             goto case;
196         case GT: // ">"
197             res.astOp = ast.make!(analyze.OpGreater);
198             break;
199         case OO_LessEqual: // "<="
200             res.isOverload = true;
201             goto case;
202         case LE: // "<="
203             res.astOp = ast.make!(analyze.OpLessEq);
204             break;
205         case OO_GreaterEqual: // ">="
206             res.isOverload = true;
207             goto case;
208         case GE: // ">="
209             res.astOp = ast.make!(analyze.OpGreaterEq);
210             break;
211         case OO_EqualEqual: // "=="
212             res.isOverload = true;
213             goto case;
214         case EQ: // "=="
215             res.astOp = ast.make!(analyze.OpEqual);
216             break;
217         case OO_Exclaim: // "!"
218             res.isOverload = true;
219             goto case;
220         case LNot: // "!"
221             res.astOp = ast.make!(analyze.OpNegate);
222             break;
223         case OO_ExclaimEqual: // "!="
224             res.isOverload = true;
225             goto case;
226         case NE: // "!="
227             res.astOp = ast.make!(analyze.OpNotEqual);
228             break;
229         case OO_AmpAmp: // "&&"
230             res.isOverload = true;
231             goto case;
232         case LAnd: // "&&"
233             res.astOp = ast.make!(analyze.OpAnd);
234             break;
235         case OO_PipePipe: // "||"
236             res.isOverload = true;
237             goto case;
238         case LOr: // "||"
239             res.astOp = ast.make!(analyze.OpOr);
240             break;
241         case OO_Amp: // "&"
242             res.isOverload = true;
243             goto case;
244         case And: // "&"
245             res.astOp = ast.make!(analyze.OpAndBitwise);
246             break;
247         case OO_Pipe: // "|"
248             res.isOverload = true;
249             goto case;
250         case Or: // "|"
251             res.astOp = ast.make!(analyze.OpOrBitwise);
252             break;
253         case OO_StarEqual: // "*="
254             res.isOverload = true;
255             goto case;
256         case MulAssign: // "*="
257             res.astOp = ast.make!(analyze.OpAssignMul);
258             break;
259         case OO_SlashEqual: // "/="
260             res.isOverload = true;
261             goto case;
262         case DivAssign: // "/="
263             res.astOp = ast.make!(analyze.OpAssignDiv);
264             break;
265         case OO_PercentEqual: // "%="
266             res.isOverload = true;
267             goto case;
268         case RemAssign: // "%="
269             res.astOp = ast.make!(analyze.OpAssignMod);
270             break;
271         case OO_PlusEqual: // "+="
272             res.isOverload = true;
273             goto case;
274         case AddAssign: // "+="
275             res.astOp = ast.make!(analyze.OpAssignAdd);
276             break;
277         case OO_MinusEqual: // "-="
278             res.isOverload = true;
279             goto case;
280         case SubAssign: // "-="
281             res.astOp = ast.make!(analyze.OpAssignSub);
282             break;
283         case OO_AmpEqual: // "&="
284             res.isOverload = true;
285             goto case;
286         case AndAssign: // "&="
287             res.astOp = ast.make!(analyze.OpAssignAndBitwise);
288             break;
289         case OO_PipeEqual: // "|="
290             res.isOverload = true;
291             goto case;
292         case OrAssign: // "|="
293             res.astOp = ast.make!(analyze.OpAssignOrBitwise);
294             break;
295         case OO_CaretEqual: // "^="
296             res.isOverload = true;
297             goto case;
298         case OO_Equal: // "="
299             goto case;
300         case ShlAssign: // "<<="
301             goto case;
302         case ShrAssign: // ">>="
303             goto case;
304         case XorAssign: // "^="
305             goto case;
306         case Assign: // "="
307             res.astOp = ast.make!(analyze.OpAssign);
308             break;
309             //case Xor: // "^"
310             //case OO_Caret: // "^"
311             //case OO_Tilde: // "~"
312         default:
313             res.astOp = ast.make!(analyze.BinaryOp);
314         }
315     }
316 
317     exprPoint;
318     opPoint;
319     sidesPoint;
320     return typeof(return)(res);
321 }
322 
323 @safe:
324 
325 Location toLocation(scope const Cursor c) {
326     auto e = c.extent;
327     // there are unexposed nodes with invalid locations.
328     if (!e.isValid)
329         return Location.init;
330 
331     auto interval = Interval(e.start.offset, e.end.offset);
332     auto begin = e.start;
333     auto end = e.end;
334     return Location(e.path.Path, interval, SourceLocRange(SourceLoc(begin.line,
335             begin.column), SourceLoc(end.line, end.column)));
336 }
337 
338 /** Find all mutation points that affect a whole expression.
339  *
340  * TODO change the name of the class. It is more than just an expression
341  * visitor.
342  *
343  * # Usage of kind_stack
344  * All usage of the kind_stack shall be documented here.
345  *  - track assignments to avoid generating unary insert operators for the LHS.
346  */
347 final class BaseVisitor : ExtendedVisitor {
348     import clang.c.Index : CXCursorKind, CXTypeKind;
349     import libclang_ast.ast;
350     import dextool.clang_extensions : getExprOperator, OpKind;
351     import my.set;
352 
353     alias visit = ExtendedVisitor.visit;
354 
355     // the depth the visitor is at.
356     uint indent;
357     // A stack of the nodes that are generated up to the current one.
358     Stack!(analyze.Node) nstack;
359 
360     // A stack of visited cursors up to the current one.
361     Stack!(CXCursorKind) cstack;
362 
363     /// The elements that where removed from the last decrement.
364     Vector!(analyze.Node) lastDecr;
365 
366     /// If >0, all mutants inside a function should be blacklisted from schematan
367     int blacklistFunc;
368 
369     RefCounted!(analyze.Ast) ast;
370     Appender!(Path[]) includes;
371 
372     /// Keep track of visited nodes to avoid circulare references.
373     Set!size_t isVisited;
374 
375     FilesysIO fio;
376     ValidateLoc vloc;
377 
378     Blacklist blacklist;
379 
380     this(FilesysIO fio, ValidateLoc vloc) nothrow {
381         this.fio = fio;
382         this.vloc = vloc;
383         this.ast = analyze.Ast.init;
384     }
385 
386     void dispose() {
387         ast.release;
388     }
389 
390     /// Returns: the depth (1+) if any of the parent nodes is `k`.
391     uint isParent(K...)(auto ref K k) {
392         return cstack.isParent(k);
393     }
394 
395     /// Returns: if the previous nodes is a CXCursorKind `k`.
396     bool isDirectParent(CXCursorKind k) {
397         if (cstack.empty)
398             return false;
399         return cstack[$ - 1].data == k;
400     }
401 
402     /** If a node should be visited and in that case mark it as visited to
403      * block infinite recursion. */
404     bool shouldSkipOrMark(size_t h) @safe {
405         if (h in isVisited)
406             return true;
407         isVisited.add(h);
408         return false;
409     }
410 
411     override void incr() scope @safe {
412         ++indent;
413         lastDecr.clear;
414     }
415 
416     override void decr() scope @trusted {
417         --indent;
418         lastDecr = nstack.popUntil(indent);
419         cstack.popUntil(indent);
420     }
421 
422     // `cursor` must be at least a cursor in the correct file.
423     private bool isBlacklist(scope Cursor cursor, analyze.Location l) @trusted {
424         return blacklist.isBlacklist(cursor, l);
425     }
426 
427     private void pushStack(scope Cursor cursor, analyze.Node n, analyze.Location l,
428             const CXCursorKind cKind) @trusted {
429         n.blacklist = n.blacklist || isBlacklist(cursor, l);
430         n.schemaBlacklist = n.blacklist || n.schemaBlacklist;
431         n.covBlacklist = n.blacklist || n.schemaBlacklist || n.covBlacklist;
432         if (!nstack.empty)
433             n.schemaBlacklist = n.schemaBlacklist || nstack[$ - 1].data.schemaBlacklist;
434         nstack.put(n, indent);
435         cstack.put(cKind, indent);
436         ast.get.put(n, l);
437     }
438 
439     /// Returns: true if it is OK to modify the cursor
440     private void pushStack(AstT, ClangT)(AstT n, ClangT c) @trusted {
441         nstack.back.children ~= n;
442         static if (is(ClangT == Cursor)) {
443             auto loc = c.toLocation;
444             pushStack(c, n, loc, c.kind);
445         } else {
446             auto loc = c.cursor.toLocation;
447             pushStack(c.cursor, n, loc, c.cursor.kind);
448         }
449     }
450 
451     override void visit(scope const TranslationUnit v) @trusted {
452         import clang.c.Index : CXLanguageKind;
453 
454         mixin(mixinNodeLog!());
455 
456         blacklist = Blacklist(v.cursor);
457 
458         ast.get.root = ast.get.make!(analyze.TranslationUnit);
459         ast.get.root.context = true;
460         auto loc = v.cursor.toLocation;
461         pushStack(v.cursor, ast.get.root, loc, v.cursor.kind);
462 
463         // it is most often invalid
464         switch (v.cursor.language) {
465         case CXLanguageKind.c:
466             ast.get.lang = Language.c;
467             break;
468         case CXLanguageKind.cPlusPlus:
469             ast.get.lang = Language.cpp;
470             break;
471         default:
472             ast.get.lang = Language.assumeCpp;
473         }
474 
475         v.accept(this);
476     }
477 
478     override void visit(scope const Attribute v) {
479         mixin(mixinNodeLog!());
480         v.accept(this);
481     }
482 
483     override void visit(scope const Declaration v) {
484         mixin(mixinNodeLog!());
485         v.accept(this);
486     }
487 
488     override void visit(scope const VarDecl v) @trusted {
489         mixin(mixinNodeLog!());
490         visitVar(v);
491         v.accept(this);
492     }
493 
494     override void visit(scope const ParmDecl v) @trusted {
495         mixin(mixinNodeLog!());
496         visitVar(v);
497         v.accept(this);
498     }
499 
500     override void visit(scope const DeclStmt v) @trusted {
501         mixin(mixinNodeLog!());
502 
503         // this, in clang-11, is one of the patterns in the AST when struct
504         // binding is used:
505         // declStmt
506         //   | unexposedDecl
507         //     | unexposedDecl
508         //       | unexposedDecl
509         //       | unexposedDecl
510         //       | unexposedDecl
511         //       | unexposedDecl
512         //         | callExpr
513         // it can't be assumed to be the only one.
514         // by injecting a Poison node for a DeclStmt it signal that there are
515         // hidden traps thus any mutation and schemata should be careful.
516         auto n = ast.get.make!(analyze.Poison);
517         pushStack(n, v);
518 
519         v.accept(this);
520     }
521 
522     // This note covers ClassTemplate, ClassTemplatePartialSpecialization and
523     // FunctionTemplate.
524     // NOTE: to future self. I tried to block scheman inside template
525     // classes but it turned out to be a bad idea. Most of the time they
526     // actually work OK. If it is turned modern c++ code takes a loooong
527     // time to run mutation testing on. There are some corner cases wherein
528     // an infinite recursion loop can occur which I haven't been able to
529     // figure out why.
530     // With the introduction of ML for schema generation the tool will adapt
531     // how scheman are composed based on the compilation failures.
532 
533     override void visit(scope const ClassTemplate v) @trusted {
534         mixin(mixinNodeLog!());
535         // by adding the node it is possible to search for it in cstack
536         auto n = ast.get.make!(analyze.Poison);
537         n.context = true;
538         n.covBlacklist = true;
539         n.schemaBlacklist = n.schemaBlacklist
540             || isParent(CXCursorKind.functionTemplate, CXCursorKind.functionDecl);
541         pushStack(n, v);
542         v.accept(this);
543     }
544 
545     override void visit(scope const ClassTemplatePartialSpecialization v) @trusted {
546         mixin(mixinNodeLog!());
547         // by adding the node it is possible to search for it in cstack
548         auto n = ast.get.make!(analyze.Poison);
549         n.context = true;
550         n.covBlacklist = true;
551         n.schemaBlacklist = n.schemaBlacklist
552             || isParent(CXCursorKind.functionTemplate, CXCursorKind.functionDecl);
553         pushStack(n, v);
554         v.accept(this);
555     }
556 
557     override void visit(scope const ClassDecl v) @trusted {
558         mixin(mixinNodeLog!());
559         // by adding the node it is possible to search for it in cstack
560         auto n = ast.get.make!(analyze.Poison);
561         n.context = true;
562         n.schemaBlacklist = n.schemaBlacklist
563             || isParent(CXCursorKind.functionTemplate, CXCursorKind.functionDecl);
564         pushStack(n, v);
565         v.accept(this);
566     }
567 
568     override void visit(scope const StructDecl v) @trusted {
569         mixin(mixinNodeLog!());
570         // by adding the node it is possible to search for it in cstack
571         auto n = ast.get.make!(analyze.Poison);
572         n.context = true;
573         n.schemaBlacklist = n.schemaBlacklist
574             || isParent(CXCursorKind.functionTemplate, CXCursorKind.functionDecl);
575         pushStack(n, v);
576         v.accept(this);
577     }
578 
579     override void visit(scope const FunctionTemplate v) @trusted {
580         mixin(mixinNodeLog!());
581         if (auto n = visitFunc(v))
582             n.context = true;
583     }
584 
585     override void visit(scope const TemplateTypeParameter v) {
586         mixin(mixinNodeLog!());
587         // block mutants inside template parameters
588     }
589 
590     override void visit(scope const TemplateTemplateParameter v) {
591         mixin(mixinNodeLog!());
592         // block mutants inside template parameters
593     }
594 
595     override void visit(scope const NonTypeTemplateParameter v) {
596         mixin(mixinNodeLog!());
597         // block mutants inside template parameters
598     }
599 
600     override void visit(scope const TypeAliasDecl v) {
601         mixin(mixinNodeLog!());
602         // block mutants inside template parameters
603     }
604 
605     override void visit(scope const CxxBaseSpecifier v) {
606         mixin(mixinNodeLog!());
607         // block mutants inside template parameters.
608         // the only mutants that are inside an inheritance is template
609         // parameters and such.
610     }
611 
612     private void visitVar(T)(T v) @trusted {
613         pushStack(ast.get.make!(analyze.VarDecl), v);
614     }
615 
616     override void visit(scope const Directive v) {
617         mixin(mixinNodeLog!());
618         v.accept(this);
619     }
620 
621     override void visit(scope const InclusionDirective v) @trusted {
622         import std.file : exists;
623         import std.path : buildPath, dirName;
624 
625         mixin(mixinNodeLog!());
626 
627         const spell = v.cursor.spelling;
628         const file = v.cursor.location.file.name;
629         const p = buildPath(file.dirName, spell);
630         if (exists(p))
631             includes.put(Path(p));
632         else
633             includes.put(Path(spell));
634 
635         v.accept(this);
636     }
637 
638     override void visit(scope const Reference v) {
639         mixin(mixinNodeLog!());
640         v.accept(this);
641     }
642 
643     // TODO overlapping logic with Expression. deduplicate
644     override void visit(scope const DeclRefExpr v) @trusted {
645         import libclang_ast.ast : dispatch;
646         import clang.SourceRange : intersects;
647 
648         mixin(mixinNodeLog!());
649 
650         if (shouldSkipOrMark(v.cursor.toHash))
651             return;
652 
653         auto n = ast.get.make!(analyze.Expr);
654         n.schemaBlacklist = isParent(CXCursorKind.classTemplate,
655                 CXCursorKind.classTemplatePartialSpecialization, CXCursorKind.functionTemplate) != 0;
656 
657         auto ue = deriveCursorType(ast.get, v.cursor);
658         ue.put(ast.get);
659         if (ue.type !is null) {
660             ast.get.put(n, ue.id);
661         }
662 
663         // only deref a node which is a self-reference
664         auto r = v.cursor.referenced;
665         if (r.isValid && r != v.cursor && intersects(v.cursor.extent, r.extent)
666                 && r.toHash !in isVisited) {
667             isVisited.add(r.toHash);
668             pushStack(n, v);
669 
670             incr;
671             scope (exit)
672                 decr;
673             dispatch(r, this);
674         } else if (ue.expr.isValid && ue.expr != v.cursor && ue.expr.toHash !in isVisited) {
675             isVisited.add(ue.expr.toHash);
676             pushStack(n, ue.expr);
677 
678             incr;
679             scope (exit)
680                 decr;
681             dispatch(ue.expr, this);
682         } else {
683             pushStack(n, v);
684             v.accept(this);
685         }
686     }
687 
688     override void visit(scope const Statement v) {
689         mixin(mixinNodeLog!());
690         v.accept(this);
691     }
692 
693     override void visit(scope const LabelRef v) {
694         mixin(mixinNodeLog!());
695         // a label cannot be duplicated thus mutant scheman aren't possible to generate
696         blacklistFunc = true;
697     }
698 
699     override void visit(scope const ArraySubscriptExpr v) {
700         mixin(mixinNodeLog!());
701         // block schematan inside subscripts because some lead to compilation
702         // errors. Need to investigate more to understand why and how to avoid.
703         // For now they are blocked.
704         auto n = ast.get.make!(analyze.Poison);
705         n.schemaBlacklist = true;
706         pushStack(n, v);
707         v.accept(this);
708     }
709 
710     override void visit(scope const Expression v) {
711         mixin(mixinNodeLog!());
712 
713         if (shouldSkipOrMark(v.cursor.toHash))
714             return;
715 
716         auto n = ast.get.make!(analyze.Expr);
717         n.schemaBlacklist = isParent(CXCursorKind.classTemplate,
718                 CXCursorKind.classTemplatePartialSpecialization, CXCursorKind.functionTemplate) != 0;
719 
720         auto ue = deriveCursorType(ast.get, v.cursor);
721         ue.put(ast.get);
722         if (ue.type !is null) {
723             ast.get.put(n, ue.id);
724         }
725 
726         pushStack(n, v);
727         v.accept(this);
728     }
729 
730     override void visit(scope const IntegerLiteral v) {
731         mixin(mixinNodeLog!());
732         pushStack(ast.get.make!(analyze.Literal), v);
733         v.accept(this);
734     }
735 
736     override void visit(scope const FloatingLiteral v) {
737         mixin(mixinNodeLog!());
738         pushStack(ast.get.make!(analyze.Literal), v);
739         v.accept(this);
740     }
741 
742     override void visit(scope const Preprocessor v) {
743         mixin(mixinNodeLog!());
744 
745         const bool isCpp = v.cursor.spelling == "__cplusplus";
746 
747         if (isCpp)
748             ast.get.lang = Language.cpp;
749         else if (!isCpp && ast.get.lang != Language.cpp)
750             ast.get.lang = Language.c;
751 
752         v.accept(this);
753     }
754 
755     override void visit(scope const EnumDecl v) @trusted {
756         mixin(mixinNodeLog!());
757 
758         // extract the boundaries of the enum to update the type db.
759         scope vis = new EnumVisitor(ast.ptr, indent);
760         vis.visit(v);
761         ast.get.types.set(vis.id, vis.toType);
762     }
763 
764     override void visit(scope const FunctionDecl v) @trusted {
765         mixin(mixinNodeLog!());
766         if (auto n = visitFunc(v))
767             n.context = true;
768     }
769 
770     override void visit(scope const Constructor v) @trusted {
771         mixin(mixinNodeLog!());
772 
773         auto n = ast.get.make!(analyze.Poison);
774         n.schemaBlacklist = isConstExpr(v);
775         pushStack(n, v);
776 
777         // skip all "= default"
778         if (!v.cursor.isDefaulted)
779             v.accept(this);
780     }
781 
782     override void visit(scope const Destructor v) @trusted {
783         mixin(mixinNodeLog!());
784 
785         auto n = ast.get.make!(analyze.Poison);
786         n.schemaBlacklist = isConstExpr(v);
787         pushStack(n, v);
788 
789         // skip all "= default"
790         if (!v.cursor.isDefaulted)
791             v.accept(this);
792         // TODO: no test covers this case where = default is used for a
793         // destructor. For some versions of clang a CompoundStmt is generated
794     }
795 
796     override void visit(scope const CxxMethod v) {
797         mixin(mixinNodeLog!());
798 
799         // model C++ methods as functions. It should be enough to know that it
800         // is a function and the return type when generating mutants.
801 
802         // skip all "= default"
803         if (!v.cursor.isDefaulted) {
804             auto n = visitFunc(v);
805             // context only set for methods defined outside of a class.
806             if (n && isParent(CXCursorKind.classDecl, CXCursorKind.structDecl) == 0) {
807                 n.context = true;
808             }
809         }
810     }
811 
812     override void visit(scope const BreakStmt v) {
813         mixin(mixinNodeLog!());
814         v.accept(this);
815     }
816 
817     override void visit(scope const BinaryOperator v) @trusted {
818         mixin(mixinNodeLog!());
819 
820         visitOp(v, v.cursor.kind);
821     }
822 
823     override void visit(scope const UnaryOperator v) @trusted {
824         mixin(mixinNodeLog!());
825         visitOp(v, v.cursor.kind);
826     }
827 
828     override void visit(scope const CompoundAssignOperator v) {
829         mixin(mixinNodeLog!());
830         // TODO: implement all aor assignment such as +=
831         pushStack(ast.get.make!(analyze.OpAssign), v);
832         v.accept(this);
833     }
834 
835     override void visit(scope const CallExpr v) {
836         mixin(mixinNodeLog!());
837 
838         if (!visitOp(v, v.cursor.kind)) {
839             visitCall(v);
840         }
841     }
842 
843     override void visit(scope const CxxThrowExpr v) {
844         mixin(mixinNodeLog!());
845         // model a C++ exception as a return expression because that is
846         // "basically" what happens.
847         auto n = ast.get.make!(analyze.Return);
848         n.blacklist = true;
849         pushStack(n, v);
850         v.accept(this);
851     }
852 
853     override void visit(scope const InitListExpr v) {
854         mixin(mixinNodeLog!());
855         pushStack(ast.get.make!(analyze.Constructor), v);
856         v.accept(this);
857     }
858 
859     override void visit(scope const LambdaExpr v) {
860         mixin(mixinNodeLog!());
861 
862         // model C++ lambdas as functions. It should be enough to know that it
863         // is a function and the return type when generating mutants.
864         visitFunc(v);
865     }
866 
867     override void visit(scope const ReturnStmt v) {
868         mixin(mixinNodeLog!());
869         pushStack(ast.get.make!(analyze.Return), v);
870         v.accept(this);
871     }
872 
873     override void visit(scope const CompoundStmt v) {
874         import std.algorithm : min;
875 
876         mixin(mixinNodeLog!());
877 
878         static uint findBraketOffset(Blob file, const uint begin, const uint end, const ubyte letter) {
879             for (uint i = begin; i < end; ++i) {
880                 if (file.content[i] == letter) {
881                     return i;
882                 }
883             }
884             return begin;
885         }
886 
887         if (isDirectParent(CXCursorKind.switchStmt)) {
888             // the CompoundStmt statement {} directly inside a switch statement
889             // isn't useful to manipulate as a block. The useful part is the
890             // smaller blocks that the case and default break down the block
891             // into thus this avoid generating useless blocks that lead to
892             // equivalent or unproductive mutants.
893         } else
894             try {
895                 auto loc = v.cursor.toLocation;
896                 // there are unexposed nodes which has range [0,0]
897                 if (loc.interval.begin < loc.interval.end) {
898                     auto n = ast.get.make!(analyze.Block);
899 
900                     // important because it triggers an invalid path if the
901                     // file shouldn't be manipulated
902                     auto file = fio.makeInput(loc.file);
903 
904                     // if the loc is inside a macro it may be impossible to
905                     // textually find matching brackets.
906                     if (!isBlacklist(v.cursor, loc)) {
907                         const maxEnd = file.content.length;
908 
909                         // The block that can be modified is the inside of it thus the
910                         // a CompoundStmt that represent a "{..}" can for example be the
911                         // body of a function or the block that a try statement encompase.
912                         // done then a SDL can't be generated that delete the inside of
913                         // e.g. void functions.
914 
915                         auto end = min(findBraketOffset(file, loc.interval.end == 0
916                                 ? loc.interval.end : loc.interval.end - 1,
917                                 cast(uint) maxEnd, cast(ubyte) '}'), maxEnd);
918                         auto begin = findBraketOffset(file, loc.interval.begin, end, cast(ubyte) '{');
919 
920                         if (begin < end)
921                             begin = begin + 1;
922 
923                         // TODO: need to adjust sloc too
924                         loc.interval = Interval(begin, end);
925                     }
926 
927                     nstack.back.children ~= n;
928                     pushStack(v.cursor, n, loc, v.cursor.kind);
929                 }
930             } catch (InvalidPathException e) {
931             } catch (Exception e) {
932                 log.trace(e.msg).collectException;
933             }
934 
935         v.accept(this);
936     }
937 
938     override void visit(scope const CaseStmt v) @trusted {
939         import libclang_ast.ast : dispatch;
940         import dextool.clang_extensions;
941 
942         mixin(mixinNodeLog!());
943 
944         auto stmt = getCaseStmt(v.cursor);
945         if (stmt.isValid && stmt.subStmt.isValid) {
946             dispatch(stmt.subStmt, this);
947         } else {
948             v.accept(this);
949         }
950     }
951 
952     override void visit(scope const DefaultStmt v) {
953         mixin(mixinNodeLog!());
954         v.accept(this);
955     }
956 
957     override void visit(scope const ForStmt v) {
958         mixin(mixinNodeLog!());
959         pushStack(ast.get.make!(analyze.Loop), v);
960 
961         scope visitor = new FindVisitor!CompoundStmt;
962         v.accept(visitor);
963 
964         if (visitor.node !is null) {
965             this.visit(visitor.node);
966         }
967     }
968 
969     override void visit(scope const CxxForRangeStmt v) {
970         mixin(mixinNodeLog!());
971         pushStack(ast.get.make!(analyze.Loop), v);
972 
973         scope visitor = new FindVisitor!CompoundStmt;
974         v.accept(visitor);
975 
976         if (visitor.node !is null) {
977             this.visit(visitor.node);
978         }
979     }
980 
981     override void visit(scope const WhileStmt v) {
982         mixin(mixinNodeLog!());
983         pushStack(ast.get.make!(analyze.Loop), v);
984         v.accept(this);
985     }
986 
987     override void visit(scope const DoStmt v) {
988         mixin(mixinNodeLog!());
989         pushStack(ast.get.make!(analyze.Loop), v);
990         v.accept(this);
991     }
992 
993     override void visit(scope const SwitchStmt v) {
994         mixin(mixinNodeLog!());
995         auto n = ast.get.make!(analyze.BranchBundle);
996         pushStack(n, v);
997         v.accept(this);
998 
999         scope caseVisitor = new FindVisitor!CaseStmt;
1000         v.accept(caseVisitor);
1001 
1002         if (caseVisitor.node is null) {
1003             log.warning(
1004                     "switch without any case statements may result in a high number of mutant scheman that do not compile");
1005         } else {
1006             incr;
1007             scope (exit)
1008                 decr;
1009             auto block = ast.get.make!(analyze.Block);
1010             auto l = ast.get.location(n);
1011             l.interval.end = l.interval.begin;
1012             pushStack(v.cursor, block, l, CXCursorKind.unexposedDecl);
1013             rewriteSwitch(ast.get, n, block, caseVisitor.node.cursor.toLocation);
1014         }
1015     }
1016 
1017     override void visit(scope const ConditionalOperator v) {
1018         mixin(mixinNodeLog!());
1019         // need to push a node because a ternery can contain function calls.
1020         // Without a node for the op it seems like it is in the body, which it
1021         // isn't, and then can be removed.
1022         pushStack(ast.get.make!(analyze.Poison), v);
1023         v.accept(this);
1024     }
1025 
1026     override void visit(scope const IfStmt v) @trusted {
1027         mixin(mixinNodeLog!());
1028         // to avoid infinite recursion, which may occur in e.g. postgresql, block
1029         // segfault on 300
1030         if (indent > 200) {
1031             throw new Exception("max analyze depth reached (200)");
1032         }
1033 
1034         auto n = ast.get.make!(analyze.BranchBundle);
1035         if (isConstExpr(v))
1036             n.schemaBlacklist = true;
1037         pushStack(n, v);
1038         dextool.plugin.mutate.backend.analyze.extensions.accept(v, this);
1039     }
1040 
1041     override void visit(scope const IfStmtInit v) @trusted {
1042         mixin(mixinNodeLog!());
1043         auto n = ast.get.make!(analyze.Poison);
1044         n.schemaBlacklist = true;
1045         pushStack(n, v);
1046         v.accept(this);
1047     }
1048 
1049     override void visit(scope const IfStmtCond v) {
1050         mixin(mixinNodeLog!());
1051 
1052         auto n = ast.get.make!(analyze.Condition);
1053         pushStack(n, v);
1054 
1055         if (!visitOp(v, v.cursor.kind)) {
1056             v.accept(this);
1057         }
1058 
1059         if (!n.children.empty) {
1060             auto tyId = ast.get.typeId(n.children[0]);
1061             if (tyId.hasValue) {
1062                 ast.get.put(n, tyId.orElse(analyze.TypeId.init));
1063             }
1064         }
1065 
1066         rewriteCondition(ast.get, n);
1067     }
1068 
1069     override void visit(scope const IfStmtCondVar v) {
1070         mixin(mixinNodeLog!());
1071         auto n = ast.get.make!(analyze.Poison);
1072         n.schemaBlacklist = true;
1073         pushStack(n, v);
1074     }
1075 
1076     override void visit(scope const IfStmtThen v) {
1077         mixin(mixinNodeLog!());
1078         visitIfBranch(v);
1079     }
1080 
1081     override void visit(scope const IfStmtElse v) {
1082         mixin(mixinNodeLog!());
1083         visitIfBranch(v);
1084     }
1085 
1086     private void visitIfBranch(T)(scope const T v) @trusted {
1087         pushStack(ast.get.make!(analyze.Branch), v);
1088         v.accept(this);
1089     }
1090 
1091     /// Returns: true if the node where visited
1092     private bool visitOp(T)(scope const T v, const CXCursorKind cKind) @trusted {
1093         auto op = operatorCursor(ast.get, v);
1094         if (op.isNull)
1095             return false;
1096 
1097         // it was meant to be visited but has already been visited so skipping.
1098         if (shouldSkipOrMark(v.cursor.toHash))
1099             return true;
1100 
1101         if (visitBinaryOp(v.cursor, op.get, cKind))
1102             return true;
1103         return visitUnaryOp(v.cursor, op.get, cKind);
1104     }
1105 
1106     /// Returns: true if it added a binary operator, false otherwise.
1107     private bool visitBinaryOp(scope Cursor cursor, ref OperatorCursor op, const CXCursorKind cKind) @trusted {
1108         import libclang_ast.ast : dispatch;
1109 
1110         auto astOp = cast(analyze.BinaryOp) op.astOp;
1111         if (astOp is null)
1112             return false;
1113 
1114         const blockSchema = op.isOverload || isBlacklist(cursor, op.opLoc) || isParent(CXCursorKind.classTemplate,
1115                 CXCursorKind.classTemplatePartialSpecialization, CXCursorKind.functionTemplate) != 0;
1116 
1117         astOp.schemaBlacklist = blockSchema;
1118         astOp.operator = op.operator;
1119         astOp.operator.blacklist = isBlacklist(cursor, op.opLoc);
1120         astOp.operator.schemaBlacklist = blockSchema;
1121 
1122         op.put(nstack.back, ast.get);
1123         pushStack(cursor, astOp, op.exprLoc, cKind);
1124         incr;
1125         scope (exit)
1126             decr;
1127 
1128         if (op.lhs.isValid) {
1129             incr;
1130             scope (exit)
1131                 decr;
1132             dispatch(op.lhs, this);
1133             auto b = () {
1134                 if (!lastDecr.empty)
1135                     return cast(analyze.Expr) lastDecr[$ - 1];
1136                 return null;
1137             }();
1138             if (b !is null && b != astOp) {
1139                 astOp.lhs = b;
1140                 auto ty = deriveCursorType(ast.get, op.lhs);
1141                 ty.put(ast.get);
1142                 if (ty.type !is null) {
1143                     ast.get.put(b, ty.id);
1144                 }
1145                 if (ty.symbol !is null) {
1146                     ast.get.put(b, ty.symId);
1147                 }
1148             }
1149         }
1150         if (op.rhs.isValid) {
1151             incr;
1152             scope (exit)
1153                 decr;
1154             dispatch(op.rhs, this);
1155             auto b = () {
1156                 if (!lastDecr.empty)
1157                     return cast(analyze.Expr) lastDecr[$ - 1];
1158                 return null;
1159             }();
1160             if (b !is null && b != astOp) {
1161                 astOp.rhs = b;
1162                 auto ty = deriveCursorType(ast.get, op.rhs);
1163                 ty.put(ast.get);
1164                 if (ty.type !is null) {
1165                     ast.get.put(b, ty.id);
1166                 }
1167                 if (ty.symbol !is null) {
1168                     ast.get.put(b, ty.symId);
1169                 }
1170             }
1171         }
1172 
1173         return true;
1174     }
1175 
1176     /// Returns: true if it added a binary operator, false otherwise.
1177     private bool visitUnaryOp(scope Cursor cursor, ref OperatorCursor op, CXCursorKind cKind) @trusted {
1178         import libclang_ast.ast : dispatch;
1179 
1180         auto astOp = cast(analyze.UnaryOp) op.astOp;
1181         if (astOp is null)
1182             return false;
1183 
1184         const blockSchema = op.isOverload || isBlacklist(cursor, op.opLoc) || isParent(CXCursorKind.classTemplate,
1185                 CXCursorKind.classTemplatePartialSpecialization, CXCursorKind.functionTemplate) != 0;
1186 
1187         astOp.operator = op.operator;
1188         astOp.operator.blacklist = isBlacklist(cursor, op.opLoc);
1189         astOp.operator.schemaBlacklist = blockSchema;
1190 
1191         op.put(nstack.back, ast.get);
1192         pushStack(cursor, astOp, op.exprLoc, cKind);
1193         incr;
1194         scope (exit)
1195             decr;
1196 
1197         if (op.lhs.isValid) {
1198             incr;
1199             scope (exit)
1200                 decr;
1201             dispatch(op.lhs, this);
1202             auto b = () {
1203                 if (!lastDecr.empty)
1204                     return cast(analyze.Expr) lastDecr[$ - 1];
1205                 return null;
1206             }();
1207             if (b !is null && b != astOp) {
1208                 astOp.expr = b;
1209                 auto ty = deriveCursorType(ast.get, op.lhs);
1210                 ty.put(ast.get);
1211                 if (ty.type !is null)
1212                     ast.get.put(b, ty.id);
1213                 if (ty.symbol !is null)
1214                     ast.get.put(b, ty.symId);
1215             }
1216         }
1217         if (op.rhs.isValid) {
1218             incr;
1219             scope (exit)
1220                 decr;
1221             dispatch(op.rhs, this);
1222             auto b = () {
1223                 if (!lastDecr.empty)
1224                     return cast(analyze.Expr) lastDecr[$ - 1];
1225                 return null;
1226             }();
1227             if (b !is null && b != astOp) {
1228                 astOp.expr = b;
1229                 auto ty = deriveCursorType(ast.get, op.rhs);
1230                 ty.put(ast.get);
1231                 if (ty.type !is null)
1232                     ast.get.put(b, ty.id);
1233                 if (ty.symbol !is null)
1234                     ast.get.put(b, ty.symId);
1235             }
1236         }
1237 
1238         return true;
1239     }
1240 
1241     private auto visitFunc(T)(scope const T v) @trusted {
1242         auto oldBlacklistFn = blacklistFunc;
1243         scope (exit)
1244             blacklistFunc = oldBlacklistFn;
1245 
1246         auto loc = v.cursor.toLocation;
1247         // no use in visiting a function that should never be mutated.
1248         if (!vloc.shouldMutate(loc.file))
1249             return null;
1250 
1251         auto n = ast.get.make!(analyze.Function);
1252         n.schemaBlacklist = isConstExpr(v);
1253         nstack.back.children ~= n;
1254         pushStack(v.cursor, n, loc, v.cursor.kind);
1255 
1256         auto fRetval = ast.get.make!(analyze.Return);
1257         auto rty = deriveType(ast.get, v.cursor.func.resultType);
1258         rty.put(ast.get);
1259         if (rty.type !is null) {
1260             ast.get.put(fRetval, loc);
1261             n.return_ = fRetval;
1262             ast.get.put(fRetval, rty.id);
1263         }
1264         if (rty.symbol !is null)
1265             ast.get.put(fRetval, rty.symId);
1266 
1267         v.accept(this);
1268 
1269         if (blacklistFunc != 0) {
1270             foreach (c; BreathFirstRange(n))
1271                 c.schemaBlacklist = true;
1272         }
1273 
1274         return n;
1275     }
1276 
1277     private void visitCall(T)(scope const T v) @trusted {
1278         if (shouldSkipOrMark(v.cursor.toHash))
1279             return;
1280 
1281         auto n = ast.get.make!(analyze.Call);
1282         pushStack(n, v);
1283 
1284         auto ty = deriveType(ast.get, v.cursor.type);
1285         ty.put(ast.get);
1286         if (ty.type !is null)
1287             ast.get.put(n, ty.id);
1288         if (ty.symbol !is null)
1289             ast.get.put(n, ty.symId);
1290 
1291         // TODO: there is a recursion bug wherein the visitor end up in a loop.
1292         // Adding the nodes to isVisited do not work because they seem to
1293         // always have a new checksum.  This is thus an ugly fix to just block
1294         // when it is too deep.
1295         if (indent < 200) {
1296             v.accept(this);
1297         }
1298     }
1299 }
1300 
1301 final class EnumVisitor : ExtendedVisitor {
1302     import libclang_ast.ast;
1303 
1304     alias visit = ExtendedVisitor.visit;
1305 
1306     mixin generateIndentIncrDecr;
1307 
1308     analyze.Ast* ast;
1309     analyze.TypeId id;
1310     Nullable!long minValue;
1311     Nullable!long maxValue;
1312 
1313     this(scope analyze.Ast* ast, const uint indent) @trusted {
1314         this.ast = ast;
1315         this.indent = indent;
1316     }
1317 
1318     override void visit(scope const EnumDecl v) @trusted {
1319         mixin(mixinNodeLog!());
1320         id = make!(analyze.TypeId)(v.cursor);
1321         v.accept(this);
1322     }
1323 
1324     override void visit(scope const EnumConstantDecl v) @trusted {
1325         mixin(mixinNodeLog!());
1326 
1327         long value = v.cursor.enum_.signedValue;
1328 
1329         if (minValue.isNull) {
1330             minValue = value;
1331             maxValue = value;
1332         }
1333 
1334         if (value < minValue.get)
1335             minValue = value;
1336         if (value > maxValue.get)
1337             maxValue = value;
1338 
1339         v.accept(this);
1340     }
1341 
1342     analyze.Type toType() {
1343         auto l = () {
1344             if (minValue.isNull)
1345                 return analyze.Value(analyze.Value.NegInf.init);
1346             return analyze.Value(analyze.Value.Int(minValue.get));
1347         }();
1348         auto u = () {
1349             if (maxValue.isNull)
1350                 return analyze.Value(analyze.Value.PosInf.init);
1351             return analyze.Value(analyze.Value.Int(maxValue.get));
1352         }();
1353 
1354         return ast.make!(analyze.DiscreteType)(analyze.Range(l, u));
1355     }
1356 }
1357 
1358 /// Find first occurences of the node type `T`.
1359 final class FindVisitor(T) : Visitor {
1360     import libclang_ast.ast;
1361 
1362     alias visit = Visitor.visit;
1363 
1364     const(T)[] nodes;
1365 
1366     const(T) node() @safe pure nothrow const @nogc {
1367         if (nodes.empty)
1368             return null;
1369         return nodes[0];
1370     }
1371 
1372     //uint indent;
1373     //override void incr() @safe {
1374     //    ++indent;
1375     //}
1376     //
1377     //override void decr() @safe {
1378     //    --indent;
1379     //}
1380 
1381     override void visit(scope const Statement v) {
1382         //mixin(mixinNodeLog!());
1383         if (nodes.empty)
1384             v.accept(this);
1385     }
1386 
1387     override void visit(scope const T v) @trusted {
1388         //mixin(mixinNodeLog!());
1389         // nodes are scope allocated thus it needs to be duplicated.
1390         if (nodes.empty)
1391             nodes = [new T(v.cursor)];
1392     }
1393 }
1394 
1395 /** Rewrite the position of a condition to perfectly match the parenthesis.
1396  *
1397  * The source code:
1398  * ```
1399  * if (int x = 42) y = 43;
1400  * ```
1401  *
1402  * Results in something like this in the AST.
1403  *
1404  * `-Condition
1405  *   `-Expr
1406  *     `-Expr
1407  *       `-VarDecl
1408  *         `-OpGreater
1409  *           `-Operator
1410  *           `-Expr
1411  *           `-Expr
1412  *
1413  * The problem is that the location of the Condition node will be OpGreater and
1414  * not the VarDecl.
1415  */
1416 void rewriteCondition(ref analyze.Ast ast, analyze.Condition root) {
1417     import sumtype;
1418     import dextool.plugin.mutate.backend.analyze.ast : TypeId, VarDecl, Kind;
1419 
1420     // set the type of the Condition to the first expression with a type.
1421     foreach (ty; BreathFirstRange(root).map!(a => ast.typeId(a))
1422             .filter!(a => a.hasValue)) {
1423         sumtype.match!((Some!TypeId a) => ast.put(root, a), (None a) {})(ty);
1424         break;
1425     }
1426 }
1427 
1428 void rewriteSwitch(ref analyze.Ast ast, analyze.BranchBundle root,
1429         analyze.Block block, Location firstCase) {
1430     import std.range : enumerate;
1431     import std.typecons : tuple;
1432 
1433     Node[] beforeCase = root.children;
1434     Node[] rest;
1435 
1436     foreach (n; root.children
1437             .map!(a => tuple!("node", "loc")(a, ast.location(a)))
1438             .enumerate
1439             .filter!(a => a.value.loc.interval.begin > firstCase.interval.begin)) {
1440         beforeCase = root.children[0 .. n.index];
1441         rest = root.children[n.index .. $];
1442         break;
1443     }
1444 
1445     root.children = beforeCase ~ block;
1446     block.children = rest;
1447 }
1448 
1449 enum discreteCategory = AliasSeq!(CXTypeKind.charU, CXTypeKind.uChar, CXTypeKind.char16,
1450             CXTypeKind.char32, CXTypeKind.uShort, CXTypeKind.uInt, CXTypeKind.uLong, CXTypeKind.uLongLong,
1451             CXTypeKind.uInt128, CXTypeKind.charS, CXTypeKind.sChar, CXTypeKind.wChar, CXTypeKind.short_,
1452             CXTypeKind.int_, CXTypeKind.long_, CXTypeKind.longLong,
1453             CXTypeKind.int128, CXTypeKind.enum_,);
1454 enum floatCategory = AliasSeq!(CXTypeKind.float_, CXTypeKind.double_,
1455             CXTypeKind.longDouble, CXTypeKind.float128, CXTypeKind.half, CXTypeKind.float16,);
1456 enum pointerCategory = AliasSeq!(CXTypeKind.nullPtr, CXTypeKind.pointer,
1457             CXTypeKind.blockPointer, CXTypeKind.memberPointer, CXTypeKind.record);
1458 enum boolCategory = AliasSeq!(CXTypeKind.bool_);
1459 
1460 enum voidCategory = AliasSeq!(CXTypeKind.void_);
1461 
1462 struct DeriveTypeResult {
1463     analyze.TypeId id;
1464     analyze.Type type;
1465     analyze.SymbolId symId;
1466     analyze.Symbol symbol;
1467 
1468     void put(ref analyze.Ast ast) @safe {
1469         if (type !is null) {
1470             ast.types.require(id, type);
1471         }
1472         if (symbol !is null) {
1473             ast.symbols.require(symId, symbol);
1474         }
1475     }
1476 }
1477 
1478 DeriveTypeResult deriveType(ref Ast ast, Type cty) {
1479     DeriveTypeResult rval;
1480 
1481     if (!cty.isValid)
1482         return rval;
1483 
1484     auto ctydecl = cty.declaration;
1485     if (ctydecl.isValid) {
1486         rval.id = make!(analyze.TypeId)(ctydecl);
1487     } else {
1488         rval.id = make!(analyze.TypeId)(cty.cursor);
1489     }
1490 
1491     if (cty.isEnum) {
1492         rval.type = ast.make!(analyze.DiscreteType)(analyze.Range.makeInf);
1493         if (!cty.isSigned) {
1494             rval.type.range.low = analyze.Value(analyze.Value.Int(0));
1495         }
1496     } else if (cty.kind.among(floatCategory)) {
1497         rval.type = ast.make!(analyze.ContinuesType)(analyze.Range.makeInf);
1498     } else if (cty.kind.among(pointerCategory)) {
1499         rval.type = ast.make!(analyze.UnorderedType)(analyze.Range.makeInf);
1500     } else if (cty.kind.among(boolCategory)) {
1501         rval.type = ast.make!(analyze.BooleanType)(analyze.Range.makeBoolean);
1502     } else if (cty.kind.among(discreteCategory)) {
1503         rval.type = ast.make!(analyze.DiscreteType)(analyze.Range.makeInf);
1504         if (!cty.isSigned) {
1505             rval.type.range.low = analyze.Value(analyze.Value.Int(0));
1506         }
1507     } else if (cty.kind.among(voidCategory)) {
1508         rval.type = ast.make!(analyze.VoidType)();
1509     } else {
1510         // unknown such as an elaborated
1511         rval.type = ast.make!(analyze.Type)();
1512     }
1513 
1514     return rval;
1515 }
1516 
1517 struct DeriveCursorTypeResult {
1518     Cursor expr;
1519     DeriveTypeResult typeResult;
1520     alias typeResult this;
1521 }
1522 
1523 /** Analyze a cursor to derive the type of it and if it has a concrete value
1524  * and what it is in that case.
1525  *
1526  * This is intended for expression nodes in the clang AST.
1527  */
1528 DeriveCursorTypeResult deriveCursorType(ref Ast ast, scope const Cursor baseCursor) {
1529     auto c = Cursor(getUnderlyingExprNode(baseCursor));
1530     if (!c.isValid)
1531         return DeriveCursorTypeResult.init;
1532 
1533     auto rval = DeriveCursorTypeResult(c);
1534     auto cty = c.type.canonicalType;
1535     rval.typeResult = deriveType(ast, cty);
1536 
1537     // evaluate the cursor to add a value for the symbol
1538     void eval(const ref Eval e) {
1539         if (!e.kind.among(CXEvalResultKind.int_))
1540             return;
1541 
1542         const long value = () {
1543             if (e.isUnsignedInt) {
1544                 const v = e.asUnsigned;
1545                 if (v < long.max)
1546                     return cast(long) v;
1547             }
1548             return e.asLong;
1549         }();
1550 
1551         rval.symId = make!(analyze.SymbolId)(c);
1552         rval.symbol = ast.make!(analyze.DiscretSymbol)(analyze.Value(analyze.Value.Int(value)));
1553     }
1554 
1555     if (cty.isEnum) {
1556         // TODO: check if c.eval give the same result. If so it may be easier
1557         // to remove this special case of an enum because it is covered by the
1558         // generic branch for discretes.
1559 
1560         auto ctydecl = cty.declaration;
1561         if (!ctydecl.isValid)
1562             return rval;
1563 
1564         const cref = c.referenced;
1565         if (!cref.isValid)
1566             return rval;
1567 
1568         if (cref.kind == CXCursorKind.enumConstantDecl) {
1569             const long value = cref.enum_.signedValue;
1570             rval.symId = make!(analyze.SymbolId)(c);
1571             rval.symbol = ast.make!(analyze.DiscretSymbol)(
1572                     analyze.Value(analyze.Value.Int(value)));
1573         }
1574     } else if (cty.kind.among(discreteCategory)) {
1575         // crashes in clang 7.x. Investigate why.
1576         //const e = c.eval;
1577         //if (e.isValid)
1578         //    eval(e);
1579     }
1580 
1581     return rval;
1582 }
1583 
1584 auto make(T)(const Cursor c) if (is(T == analyze.TypeId) || is(T == analyze.SymbolId)) {
1585     const usr = c.usr;
1586     if (usr.empty) {
1587         return T(c.toHash);
1588     }
1589     return analyze.makeId!T(usr);
1590 }
1591 
1592 /// trusted: trusting the impl in clang.
1593 uint findTokenOffset(T)(T toks, Offset sr, CXTokenKind kind) @trusted {
1594     foreach (ref t; toks) {
1595         if (t.location.offset >= sr.end) {
1596             if (t.kind == kind) {
1597                 return t.extent.end.offset;
1598             }
1599             break;
1600         }
1601     }
1602 
1603     return sr.end;
1604 }
1605 
1606 import dextool.clang_extensions : dex_isPotentialConstExpr, dex_isFunctionTemplateConstExpr;
1607 import libclang_ast.ast : FunctionTemplate, FunctionDecl, IfStmt, Constructor,
1608     Destructor, CxxMethod, LambdaExpr;
1609 
1610 bool isConstExpr(scope const Constructor v) @trusted {
1611     return dex_isPotentialConstExpr(v.cursor);
1612 }
1613 
1614 bool isConstExpr(scope const Destructor v) @trusted {
1615     return dex_isPotentialConstExpr(v.cursor);
1616 }
1617 
1618 bool isConstExpr(scope const CxxMethod v) @trusted {
1619     return dex_isPotentialConstExpr(v.cursor);
1620 }
1621 
1622 bool isConstExpr(scope const LambdaExpr v) @trusted {
1623     return dex_isPotentialConstExpr(v.cursor);
1624 }
1625 
1626 bool isConstExpr(scope const FunctionDecl v) @trusted {
1627     return dex_isPotentialConstExpr(v.cursor);
1628 }
1629 
1630 bool isConstExpr(scope const IfStmt v) @trusted {
1631     return dex_isPotentialConstExpr(v.cursor);
1632 }
1633 
1634 bool isConstExpr(scope const FunctionTemplate v) @trusted {
1635     return dex_isFunctionTemplateConstExpr(v.cursor);
1636 }
1637 
1638 /// Locations that should not be mutated with scheman
1639 struct Blacklist {
1640     import clang.TranslationUnit : clangTranslationUnit = TranslationUnit;
1641     import dextool.plugin.mutate.backend.analyze.utility : Index;
1642 
1643     clangTranslationUnit rootTu;
1644     bool[size_t] cache_;
1645     Index!string macros;
1646 
1647     this(const Cursor root) {
1648         rootTu = root.translationUnit;
1649 
1650         Interval[][string] macros;
1651 
1652         foreach (c, parent; root.all) {
1653             if (!c.kind.among(CXCursorKind.macroExpansion,
1654                     CXCursorKind.macroDefinition) || c.isMacroBuiltin)
1655                 continue;
1656             add(c, macros);
1657         }
1658 
1659         foreach (k; macros.byKey)
1660             macros[k] = macros[k].sort.array;
1661 
1662         this.macros = Index!string(macros);
1663     }
1664 
1665     static void add(ref const Cursor c, ref Interval[][string] idx) {
1666         const file = c.location.path;
1667         if (file.empty)
1668             return;
1669         const e = c.extent;
1670         const interval = Interval(e.start.offset, e.end.offset);
1671 
1672         auto absFile = AbsolutePath(file);
1673         if (auto v = absFile in idx) {
1674             (*v) ~= interval;
1675         } else {
1676             idx[absFile.toString] = [interval];
1677         }
1678     }
1679 
1680     bool isBlacklist(const Cursor cursor, const analyze.Location l) @trusted {
1681         import dextool.clang_extensions;
1682         import clang.c.Index;
1683 
1684         bool clangPass() {
1685             if (!cursor.isValid)
1686                 return false;
1687 
1688             auto hb = l.file.toHash + l.interval.begin;
1689             if (auto v = hb in cache_)
1690                 return *v;
1691             auto he = l.file.toHash + l.interval.end;
1692             if (auto v = he in cache_)
1693                 return *v;
1694 
1695             auto file = cursor.location.file;
1696             if (!file.isValid)
1697                 return false;
1698 
1699             auto cxLoc = clang_getLocationForOffset(rootTu, file, l.interval.begin);
1700             if (cxLoc is CXSourceLocation.init)
1701                 return false;
1702             auto res = dex_isAnyMacro(cxLoc);
1703             cache_[hb] = res;
1704             if (res)
1705                 return true;
1706 
1707             cxLoc = clang_getLocationForOffset(rootTu, file, l.interval.end);
1708             if (cxLoc is CXSourceLocation.init)
1709                 return false;
1710             res = dex_isAnyMacro(cxLoc);
1711             cache_[he] = res;
1712 
1713             return res;
1714         }
1715 
1716         return clangPass() || macros.overlap(l.file.toString, l.interval);
1717     }
1718 }