/**
Copyright: Copyright (c) 2020, Joakim Brännström. All rights reserved.
License: MPL-2
Author: Joakim Brännström (joakim.brannstrom@gmx.com)

This Source Code Form is subject to the terms of the Mozilla Public License,
v.2.0. If a copy of the MPL was not distributed with this file, You can obtain
one at http://mozilla.org/MPL/2.0/.
*/
module dextool.plugin.mutate.backend.analyze.pass_schemata;

import logger = std.experimental.logger;
import std.algorithm : among, map, sort, filter, canFind, copy, uniq, any;
import std.array : appender, empty, array, Appender;
import std.conv : to;
import std.exception : collectException;
import std.format : formattedWrite, format;
import std.meta : AliasSeq;
import std.range : ElementType, only;
import std.traits : EnumMembers;
import std.typecons : tuple, Tuple, scoped;

import automem : vector, Vector;
import my.gc.refc : RefCounted;
import my.set;

import dextool.type : AbsolutePath, Path;

import dextool.plugin.mutate.backend.analyze.ast : Interval, Location;
import dextool.plugin.mutate.backend.analyze.extensions;
import dextool.plugin.mutate.backend.analyze.internal;
import dextool.plugin.mutate.backend.analyze.utility;
import dextool.plugin.mutate.backend.database.type : SchemataFragment;
import dextool.plugin.mutate.backend.interface_ : FilesysIO;
import dextool.plugin.mutate.backend.type : Language, SourceLoc, Offset,
    Mutation, SourceLocRange, CodeMutant, SchemataChecksum, Checksum;

import dextool.plugin.mutate.backend.analyze.ast;
import dextool.plugin.mutate.backend.analyze.pass_mutant : CodeMutantsResult;

// constant defined by the schemata that test_mutant uses too
/// The global variable that a mutant reads to see if it should activate.
immutable schemataMutantIdentifier = "gDEXTOOL_MUTID";
/// The environment variable that is read to set the current active mutant.
immutable schemataMutantEnvKey = "DEXTOOL_MUTID";

/// Translate a mutation AST to a schemata.
SchemataResult toSchemata(RefCounted!Ast ast, FilesysIO fio,
        CodeMutantsResult cresult, long mutantsPerSchema) @trusted {
    auto rval = new SchemataResult(fio, mutantsPerSchema);
    auto index = scoped!CodeMutantIndex(cresult);

    final switch (ast.lang) {
    case Language.c:
        goto case;
    case Language.assumeCpp:
        goto case;
    case Language.cpp:
        auto visitor = scoped!CppSchemataVisitor(ast, index, fio, rval);
        ast.accept(cast(CppSchemataVisitor) visitor);
        break;
    }

    return rval;
}

@safe:

/// Converts a checksum to a 32-bit ID that can be used to activate a mutant.
uint checksumToId(Checksum cs) @safe pure nothrow @nogc {
    return checksumToId(cs.c0);
}

uint checksumToId(ulong cs) @safe pure nothrow @nogc {
    return cast(uint) cs;
}

/// Language generic
class SchemataResult {
    import dextool.plugin.mutate.backend.database.type : SchemataFragment;
    import dextool.plugin.mutate.backend.analyze.utility : Index;

    static struct Fragment {
        Offset offset;
        const(ubyte)[] text;
        CodeMutant[] mutants;
    }

    static struct Schemata {
        Fragment[] fragments;
    }

    private {
        Schemata[MutantGroup][AbsolutePath] schematas;
        FilesysIO fio;
        const long mutantsPerSchema;
    }

    this(FilesysIO fio, long mutantsPerSchema) {
        this.fio = fio;
        this.mutantsPerSchema = mutantsPerSchema;
    }

    SchematasRange getSchematas() @safe {
        return SchematasRange(fio, schematas, mutantsPerSchema);
    }

    /// Assuming that all fragments for a file should be merged to one huge.
    private void putFragment(AbsolutePath file, MutantGroup g, Fragment sf) {
        if (auto v = file in schematas) {
            (*v)[g].fragments ~= sf;
        } else {
            foreach (a; [EnumMembers!MutantGroup]) {
                schematas[file][a] = Schemata.init;
            }
            schematas[file][g] = Schemata([sf]);
        }
    }

    override string toString() @safe {
        import std.range : put;
        import std.utf : byUTF;

        auto w = appender!string();

        void toBuf(Schemata s) {
            foreach (f; s.fragments) {
                formattedWrite(w, "%(  %s\n%)\n", f.mutants);
                formattedWrite(w, "  %s: %s\n", f.offset,
                        (cast(const(char)[]) f.text).byUTF!(const(char)));
            }
        }

        void toBufGroups(Schemata[MutantGroup] s) {
            foreach (a; s.byKeyValue) {
                formattedWrite(w, "Group %s\n", a.key);
                toBuf(a.value);
            }
        }

        foreach (k; schematas.byKey.array.sort) {
            try {
                formattedWrite(w, "%s:\n", k);
                toBufGroups(schematas[k]);
            } catch (Exception e) {
            }
        }

        return w.data;
    }
}

private:

/** All mutants for a file that is part of the same group are merged to one schemata.
 *
 * Each file can have multiple groups.
 */
enum MutantGroup {
    none,
    aor,
    ror,
    lcr,
    lcrb,
    // the operator mutants that replace the whole expression. The schema have
    // a high probability of working because it isn't dependent on the
    // operators being implemented for lhs/rhs
    opExpr,
    dcc,
    dcr,
    uoi,
    sdl,
}

auto defaultHeader(Path f) {
    enum code = import("schemata_header.c");
    return SchemataFragment(f, Offset(0, 0), cast(const(ubyte)[]) code);
}

struct SchematasRange {
    alias ET = Tuple!(SchemataFragment[], "fragments", CodeMutant[], "mutants",
            SchemataChecksum, "checksum");

    private {
        FilesysIO fio;
        ET[] values;
    }

    this(FilesysIO fio, SchemataResult.Schemata[MutantGroup][AbsolutePath] raw,
            long mutantsPerSchema) {
        this.fio = fio;

        // TODO: maybe accumulate the fragments for more files? that would make
        // it possible to easily create a large schemata.
        auto values_ = appender!(ET[])();

        SchemataResult.Fragment[] makeSchema(SchemataResult.Fragment[] fragments, Path relp) {
            // overlapping mutants is not supported "yet" thus make sure no
            // fragment overlap with another fragment.
            Index!int index;
            auto spillOver = appender!(SchemataResult.Fragment[])();

            auto app = appender!(SchemataFragment[])();

            app.put(defaultHeader(relp));

            Set!CodeMutant mutants;
            foreach (a; fragments) {
                // conservative to only allow up to <user defined> mutants per
                // schemata but it reduces the chance that one failing schemata
                // is "fatal", loosing too many muntats.
                if (index.inside(0, a.offset) || mutants.length >= mutantsPerSchema) {
                    spillOver.put(a);
                    continue;
                }

                // if any of the mutants in the schema has already been added
                // then the new fragment is also overlapping
                if (any!(a => a in mutants)(a.mutants)) {
                    spillOver.put(a);
                    continue;
                }

                app.put(SchemataFragment(relp, a.offset, a.text));
                mutants.add(a.mutants);
                index.put(0, a.offset);
            }

            ET v;
            v.fragments = app.data;

            v.mutants = mutants.toArray;
            v.checksum = toSchemataChecksum(v.mutants);
            values_.put(v);

            return spillOver.data;
        }

        foreach (group; raw.byKeyValue) {
            auto relp = fio.toRelativeRoot(group.key);
            foreach (a; group.value.byValue) {
                auto spillOver = makeSchema(a.fragments, relp);
                while (!spillOver.empty) {
                    spillOver = makeSchema(spillOver, relp);
                }
            }
        }
        this.values = values_.data;
    }

    ET front() @safe pure nothrow {
        assert(!empty, "Can't get front of an empty range");
        return values[0];
    }

    void popFront() @safe {
        assert(!empty, "Can't pop front of an empty range");
        values = values[1 .. $];
    }

    bool empty() @safe pure nothrow const @nogc {
        return values.empty;
    }
}

// An index over the mutants and the interval they apply for.
class CodeMutantIndex {
    CodeMutant[][Offset][AbsolutePath] index;

    this(CodeMutantsResult result) {
        foreach (p; result.points.byKeyValue) {
            CodeMutant[][Offset] e;
            foreach (mp; p.value) {
                if (auto v = mp.offset in e) {
                    (*v) ~= mp.mutants;
                } else {
                    e[mp.offset] = mp.mutants;
                }
            }
            index[p.key] = e;
        }
    }

    CodeMutant[] get(AbsolutePath file, Offset o) {
        if (auto v = file in index) {
            if (auto w = o in *v) {
                return *w;
            }
        }
        return null;
    }
}

class CppSchemataVisitor : DepthFirstVisitor {
    import dextool.plugin.mutate.backend.generate_mutant : makeMutation;
    import dextool.plugin.mutate.backend.mutation_type.aor : aorMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.dcc : dccMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.dcr : dcrMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.lcr : lcrMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.lcrb : lcrbMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.ror : rorMutationsAll, rorpMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.sdl : stmtDelMutationsRaw;

    RefCounted!Ast ast;
    CodeMutantIndex index;
    SchemataResult result;
    FilesysIO fio;

    private {
        Stack!(Node) nstack;
        uint depth;
    }

    this(RefCounted!Ast ast, CodeMutantIndex index, FilesysIO fio, SchemataResult result) {
        assert(!ast.empty);

        this.ast = ast;
        this.index = index;
        this.fio = fio;
        this.result = result;
    }

    override void visitPush(Node n) {
        nstack.put(n, ++depth);
    }

    override void visitPop(Node n) {
        nstack.pop;
        --depth;
    }

    alias visit = DepthFirstVisitor.visit;

    override void visit(Branch n) {
        if (n.inside !is null) {
            visitBlock!BlockChain(n, MutantGroup.dcr, dcrMutationsAll);
            visitBlock!BlockChain(n.inside, MutantGroup.dcc, dccMutationsAll);
        }
        accept(n, this);
    }

    override void visit(Condition n) {
        visitCondition(n, MutantGroup.dcr, dcrMutationsAll);
        visitCondition(n, MutantGroup.dcc, dccMutationsAll);
        accept(n, this);
    }

    override void visit(VarDecl n) {
        // block schematas if the visitor is inside a const declared variable.
        // a schemata is dependent on a runtime variable but a const
        // declaration requires its expression to be resolved at compile time.
        // Thus if a schema mutant is injected inside this part of the tree it
        // will result in a schema that do not compile.
        if (!n.isConst) {
            accept(n, this);
        }
    }

    override void visit(Expr n) {
        accept(n, this);
    }

    override void visit(Block n) {
        visitBlock!(BlockChain)(n, MutantGroup.sdl, stmtDelMutationsRaw);
        accept(n, this);
    }

    override void visit(Call n) {
        visitBlock!(BlockChain)(n, MutantGroup.sdl, stmtDelMutationsRaw);
        accept(n, this);
    }

    override void visit(OpAssign n) {
        visitBlock!(BlockChain)(n, MutantGroup.sdl, stmtDelMutationsRaw);
        accept(n, this);
    }

    override void visit(Return n) {
        visitBlock!(BlockChain)(n, MutantGroup.sdl, stmtDelMutationsRaw);
        accept(n, this);
    }

    override void visit(BinaryOp n) {
        // these are operators such as x += 2
        visitBlock!(BlockChain)(n, MutantGroup.sdl, stmtDelMutationsRaw);
        accept(n, this);
    }

    override void visit(OpNegate n) {
        import dextool.plugin.mutate.backend.mutation_type.uoi : uoiLvalueMutationsRaw;

        visitUnaryOp(n, MutantGroup.uoi, uoiLvalueMutationsRaw);
        accept(n, this);
    }

    override void visit(OpAndBitwise n) {
        visitBinaryOp(n);
    }

    override void visit(OpAnd n) {
        visitBinaryOp(n);
    }

    override void visit(OpOrBitwise n) {
        visitBinaryOp(n);
    }

    override void visit(OpOr n) {
        visitBinaryOp(n);
    }

    override void visit(OpLess n) {
        visitBinaryOp(n);
    }

    override void visit(OpLessEq n) {
        visitBinaryOp(n);
    }

    override void visit(OpGreater n) {
        visitBinaryOp(n);
    }

    override void visit(OpGreaterEq n) {
        visitBinaryOp(n);
    }

    override void visit(OpEqual n) {
        visitBinaryOp(n);
    }

    override void visit(OpNotEqual n) {
        visitBinaryOp(n);
    }

    override void visit(OpAdd n) {
        visitBinaryOp(n);
    }

    override void visit(OpSub n) {
        visitBinaryOp(n);
    }

    override void visit(OpMul n) {
        visitBinaryOp(n);
    }

    override void visit(OpMod n) {
        visitBinaryOp(n);
    }

    override void visit(OpDiv n) {
        visitBinaryOp(n);
    }

    private void visitCondition(T)(T n, const MutantGroup group, const Mutation.Kind[] kinds) @trusted {
        // The schematas from the code below are only needed for e.g. function
        // calls such as if (fn())...

        auto loc = ast.location(n);
        auto mutants = index.get(loc.file, loc.interval)
            .filter!(a => canFind(kinds, a.mut.kind)).array;

        if (loc.interval.isZero)
            return;

        if (mutants.empty)
            return;

        auto fin = fio.makeInput(loc.file);
        auto schema = ExpressionChain(fin.content[loc.interval.begin .. loc.interval.end]);
        foreach (const mutant; mutants) {
            // dfmt off
            schema.put(mutant.id.c0,
                makeMutation(mutant.mut.kind, ast.lang).mutate(fin.content[loc.interval.begin .. loc.interval.end]),
                );
            // dfmt on
        }

        result.putFragment(loc.file, group, rewrite(loc, schema.generate, mutants));
    }

    private void visitBlock(ChainT, T)(T n, const MutantGroup group, const Mutation.Kind[] kinds) {
        auto loc = ast.location(n);
        auto offs = loc.interval;
        auto mutants = index.get(loc.file, offs).filter!(a => canFind(kinds, a.mut.kind)).array;

        if (loc.interval.isZero)
            return;

        if (mutants.empty)
            return;

        auto fin = fio.makeInput(loc.file);

        auto content = () {
            // TODO: why does it crash when null is returned? it shuld work...
            // switch statements with fallthrough case-branches have an
            // offs.begin == offs.end
            if (offs.begin >= offs.end) {
                return " ".rewrite;
            }
            // this is just defensive code. not proven to be a problem.
            if (any!(a => a >= fin.content.length)(only(offs.begin, offs.end))) {
                return " ".rewrite;
            }
            return fin.content[offs.begin .. offs.end];
        }();

        auto schema = ChainT(content);
        foreach (const mutant; mutants) {
            schema.put(mutant.id.c0, makeMutation(mutant.mut.kind, ast.lang).mutate(content));
        }

        result.putFragment(loc.file, group, rewrite(loc, schema.generate, mutants));
    }

    private void visitUnaryOp(T)(T n, const MutantGroup group, const Mutation.Kind[] kinds) {
        auto loc = ast.location(n.operator);
        auto locExpr = ast.location(n);

        if (loc.interval.isZero || locExpr.interval.isZero)
            return;

        auto mutants = index.get(loc.file, loc.interval)
            .filter!(a => canFind(kinds, a.mut.kind)).array;

        if (mutants.empty)
            return;

        auto fin = fio.makeInput(loc.file);
        auto schema = ExpressionChain(fin.content[locExpr.interval.begin .. locExpr.interval.end]);
        foreach (const mutant; mutants) {
            schema.put(mutant.id.c0, makeMutation(mutant.mut.kind, ast.lang)
                    .mutate(fin.content[loc.interval.begin .. loc.interval.end]),
                    fin.content[loc.interval.end .. locExpr.interval.end]);
        }

        result.putFragment(loc.file, group, rewrite(locExpr, schema.generate, mutants));
    }

    private void visitBinaryOp(T)(T n) @trusted {
        try {
            auto v = scoped!BinaryOpVisitor(ast, &index, fio, n);
            v.startVisit(n);

            foreach (a; v.schema.byKeyValue.filter!(a => !a.value.empty)) {
                result.putFragment(v.rootLoc.file, a.key, rewrite(v.rootLoc,
                        a.value.generate, v.mutants[a.key].toArray));
            }
        } catch (Exception e) {
        }
    }
}

class BinaryOpVisitor : DepthFirstVisitor {
    import dextool.plugin.mutate.backend.generate_mutant : makeMutation;
    import dextool.plugin.mutate.backend.mutation_type.aor : aorMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.dcc : dccMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.dcr : dcrMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.lcr : lcrMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.lcrb : lcrbMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.ror : rorMutationsAll, rorpMutationsAll;
    import dextool.plugin.mutate.backend.mutation_type.sdl : stmtDelMutationsRaw;

    RefCounted!Ast ast;
    CodeMutantIndex* index;
    FilesysIO fio;

    // the root of the expression that is being mutated
    Location rootLoc;
    Interval root;

    /// Content of the file that contains the mutant.
    const(ubyte)[] content;

    /// The resulting fragments of the expression.
    ExpressionChain[MutantGroup] schema;
    Set!(CodeMutant)[MutantGroup] mutants;

    this(T)(RefCounted!Ast ast, CodeMutantIndex* index, FilesysIO fio, T root) {
        this.ast = ast;
        this.index = index;
        this.fio = fio;
    }

    void startVisit(T)(T n) {
        rootLoc = ast.location(n);
        root = rootLoc.interval;

        if (root.begin >= root.end) {
            // can happen for C macros
            return;
        }

        content = fio.makeInput(rootLoc.file).content;

        if (content.empty)
            return;

        foreach (mg; [EnumMembers!MutantGroup]) {
            schema[mg] = ExpressionChain(content[root.begin .. root.end]);
            mutants[mg] = Set!CodeMutant.init;
        }

        visit(n);
    }

    alias visit = DepthFirstVisitor.visit;

    override void visit(OpAndBitwise n) {
        visitBinaryOp(n, MutantGroup.lcrb, lcrbMutationsAll);
        accept(n, this);
    }

    override void visit(OpAnd n) {
        visitBinaryOp(n, MutantGroup.lcr, lcrMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpOrBitwise n) {
        visitBinaryOp(n, MutantGroup.lcrb, lcrbMutationsAll);
        accept(n, this);
    }

    override void visit(OpOr n) {
        visitBinaryOp(n, MutantGroup.lcr, lcrMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpLess n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpLessEq n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpGreater n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpGreaterEq n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpEqual n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpNotEqual n) {
        visitBinaryOp(n, MutantGroup.ror, rorMutationsAll ~ rorpMutationsAll);
        visitBinaryOp(n, MutantGroup.dcc, dccMutationsAll);
        visitBinaryOp(n, MutantGroup.dcr, dcrMutationsAll);
        accept(n, this);
    }

    override void visit(OpAdd n) {
        visitBinaryOp(n, MutantGroup.aor, aorMutationsAll);
        accept(n, this);
    }

    override void visit(OpSub n) {
        visitBinaryOp(n, MutantGroup.aor, aorMutationsAll);
        accept(n, this);
    }

    override void visit(OpMul n) {
        visitBinaryOp(n, MutantGroup.aor, aorMutationsAll);
        accept(n, this);
    }

    override void visit(OpMod n) {
        visitBinaryOp(n, MutantGroup.aor, aorMutationsAll);
        accept(n, this);
    }

    override void visit(OpDiv n) {
        visitBinaryOp(n, MutantGroup.aor, aorMutationsAll);
        accept(n, this);
    }

    private void visitBinaryOp(T)(T n, const MutantGroup group, const Mutation.Kind[] opKinds_) {
        auto locExpr = ast.location(n);
        auto locOp = ast.location(n.operator);

        if (locExpr.interval.isZero || locOp.interval.isZero) {
            return;
        }

        auto left = contentOrNull(root.begin, locExpr.interval.begin, content);

        // must check otherwise it crash on intervals that have zero length e.g. [9, 9].
        auto right = contentOrNull(locExpr.interval.end, root.end, content);

        auto opKinds = opKinds_.dup.sort.uniq.array;

        auto opMutants = index.get(locOp.file, locOp.interval)
            .filter!(a => canFind(opKinds, a.mut.kind)).array;

        auto exprMutants = index.get(locOp.file, locExpr.interval)
            .filter!(a => canFind(opKinds, a.mut.kind)).array;

        auto offsLhs = Offset(locExpr.interval.begin, locOp.interval.end);
        auto lhsMutants = index.get(locOp.file, offsLhs)
            .filter!(a => canFind(opKinds, a.mut.kind)).array;

        auto offsRhs = Offset(locOp.interval.begin, locExpr.interval.end);
        auto rhsMutants = index.get(locOp.file, offsRhs)
            .filter!(a => canFind(opKinds, a.mut.kind)).array;

        if (opMutants.empty && lhsMutants.empty && rhsMutants.empty && exprMutants.empty)
            return;

        foreach (const mutant; opMutants) {
            // dfmt off
            schema[group].
                put(mutant.id.c0,
                    left,
                    content[locExpr.interval.begin .. locOp.interval.begin],
                    makeMutation(mutant.mut.kind, ast.lang).mutate(content[locOp.interval.begin .. locOp.interval.end]),
                    content[locOp.interval.end .. locExpr.interval.end],
                    right);
            // dfmt on
        }

        foreach (const mutant; lhsMutants) {
            // dfmt off
            schema[MutantGroup.opExpr]
                .put(mutant.id.c0,
                    schema[group].put(mutant.id.c0,
                        left,
                        makeMutation(mutant.mut.kind, ast.lang).mutate(content[offsLhs.begin .. offsLhs.end]),
                        content[offsLhs.end .. locExpr.interval.end],
                        right));
            // dfmt on
        }

        foreach (const mutant; rhsMutants) {
            // dfmt off
            schema[MutantGroup.opExpr]
                .put(mutant.id.c0,
                    schema[group].put(mutant.id.c0,
                        left,
                        content[locExpr.interval.begin .. offsRhs.begin],
                        makeMutation(mutant.mut.kind, ast.lang).mutate(content[offsRhs.begin .. offsRhs.end]),
                        right));
            // dfmt on
        }

        foreach (const mutant; exprMutants) {
            // dfmt off
            schema[MutantGroup.opExpr]
                .put(mutant.id.c0,
                    schema[group].put(mutant.id.c0,
                        left,
                        makeMutation(mutant.mut.kind, ast.lang).mutate(content[locExpr.interval.begin .. locExpr.interval.end]),
                        right));
            // dfmt on
        }

        mutants[group].add(opMutants ~ lhsMutants ~ rhsMutants ~ exprMutants);
        mutants[MutantGroup.opExpr].add(exprMutants);
    }
}

const(ubyte)[] rewrite(string s) {
    return cast(const(ubyte)[]) s;
}

SchemataResult.Fragment rewrite(Location loc, string s, CodeMutant[] mutants) {
    return rewrite(loc, cast(const(ubyte)[]) s, mutants);
}

/// Create a fragment that rewrite a source code location to `s`.
SchemataResult.Fragment rewrite(Location loc, const(ubyte)[] s, CodeMutant[] mutants) {
    return SchemataResult.Fragment(loc.interval, s, mutants);
}

/** A schemata is uniquely identified by the mutants that it contains.
 *
 * The order of the mutants are irrelevant because they are always sorted by
 * their value before the checksum is calculated.
 *
 */
SchemataChecksum toSchemataChecksum(CodeMutant[] mutants) {
    import dextool.plugin.mutate.backend.utility : BuildChecksum, toChecksum, toBytes;
    import dextool.utility : dextoolBinaryId;

    BuildChecksum h;
    // this make sure that schematas for a new version av always added to the
    // database.
    h.put(dextoolBinaryId.toBytes);
    foreach (a; mutants.sort!((a, b) => a.id.value < b.id.value)
            .map!(a => a.id.value)) {
        h.put(a.c0.toBytes);
        h.put(a.c1.toBytes);
    }

    return SchemataChecksum(toChecksum(h));
}

/** Accumulate multiple modifications for an expression to then generate a via
 * ternery operator that activate one mutant if necessary.
 *
 * A id can only be added once to the chain. This ensure that there are no
 * duplications. This can happen when e.g. adding rorFalse and dccFalse to an
 * expression group. They both result in the same source code mutation thus
 * only one of them is actually needed. This deduplications this case.
 */
struct ExpressionChain {
    alias Mutant = Tuple!(ulong, "id", const(ubyte)[], "value");
    Appender!(Mutant[]) mutants;
    Set!ulong mutantIds;
    const(ubyte)[] original;

    this(const(ubyte)[] original) {
        this.original = original;
    }

    bool empty() @safe pure nothrow const @nogc {
        return mutants.data.empty;
    }

    /// Returns: `value`
    const(ubyte)[] put(ulong id, const(ubyte)[] value) {
        if (id !in mutantIds) {
            mutantIds.add(id);
            mutants.put(Mutant(id, value));
        }
        return value;
    }

    /// Returns: the merge of `values`
    const(ubyte)[] put(T...)(ulong id, auto ref T values) {
        auto app = appender!(const(ubyte)[])();
        static foreach (a; values) {
            app.put(a);
        }
        return this.put(id, app.data);
    }

    /// Returns: the generated chain that can replace the original expression.
    const(ubyte)[] generate() {
        auto app = appender!(const(ubyte)[])();
        app.put("(".rewrite);
        foreach (const mutant; mutants.data) {
            app.put(format!"(%s == "(schemataMutantIdentifier).rewrite);
            app.put(mutant.id.checksumToId.to!string.rewrite);
            app.put("u".rewrite);
            app.put(") ? (".rewrite);
            app.put(mutant.value);
            app.put(") : ".rewrite);
        }
        app.put("(".rewrite);
        app.put(original);
        app.put("))".rewrite);
        return app.data;
    }
}

/** Accumulate block modification of the program to then generate a
 * if-statement chain that activates them if the mutant is set. The last one is
 * the original.
 *
 * A id can only be added once to the chain. This ensure that there are no
 * duplications. This can happen when e.g. adding rorFalse and dccFalse to an
 * expression group. They both result in the same source code mutation thus
 * only one of them is actually needed. This deduplications this case.
 */
struct BlockChain {
    alias Mutant = Tuple!(ulong, "id", const(ubyte)[], "value");
    Set!ulong mutantIds;
    Appender!(Mutant[]) mutants;
    const(ubyte)[] original;

    this(const(ubyte)[] original) {
        this.original = original;
    }

    bool empty() @safe pure nothrow const @nogc {
        return mutants.data.empty;
    }

    /// Returns: `value`
    const(ubyte)[] put(ulong id, const(ubyte)[] value) {
        if (id !in mutantIds) {
            mutantIds.add(id);
            mutants.put(Mutant(id, value));
        }
        return value;
    }

    /// Returns: the merge of `values`
    const(ubyte)[] put(T...)(ulong id, auto ref T values) {
        auto app = appender!(const(ubyte)[])();
        static foreach (a; values) {
            app.put(a);
        }
        return this.put(id, app.data);
    }

    /// Returns: the generated chain that can replace the original expression.
    const(ubyte)[] generate() {
        auto app = appender!(const(ubyte)[])();
        bool isFirst = true;
        foreach (const mutant; mutants.data) {
            if (isFirst) {
                app.put("if (".rewrite);
            } else {
                app.put(" else if (".rewrite);
            }
            isFirst = false;

            app.put(format!"%s == "(schemataMutantIdentifier).rewrite);
            app.put(mutant.id.checksumToId.to!string.rewrite);
            app.put("u".rewrite);
            app.put(") {".rewrite);
            app.put(mutant.value);
            app.put("} ".rewrite);
        }

        app.put("else {".rewrite);
        app.put(original);
        if (original[$ - 1 .. $] != ";".rewrite) {
            app.put(";".rewrite);
        }
        app.put("}".rewrite);

        return app.data;
    }
}

auto contentOrNull(uint begin, uint end, const(ubyte)[] content) {
    if (begin >= end)
        return null;
    return content[begin .. end];
}