parserUnroll.h

/*
 * Copyright 2016 VMware, Inc.
 * SPDX-FileCopyrightText: 2016 VMware, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef MIDEND_PARSERUNROLL_H_
#define MIDEND_PARSERUNROLL_H_
 
#include <unordered_map>
 
#include "frontends/common/resolveReferences/referenceMap.h"
#include "frontends/p4/callGraph.h"
#include "frontends/p4/simplify.h"
#include "frontends/p4/typeChecking/typeChecker.h"
#include "frontends/p4/typeMap.h"
#include "interpreter.h"
#include "ir/ir.h"
 
namespace P4 {

const char outOfBoundsStateName[] = "stateOutOfBound";

// The following are for a single parser
 
// Represents a variable for storing indexes values for a header stack.
//
// This is a thin wrapper around a 'const IR::Member*' to (1) enforce invariants on which forms of
// Members can represent state variables and (2) enable the use of StackVariable as map keys.
//
// A Member can represent a StackVariable exactly when its qualifying variable
// (IR::Member::expr) either is a PathExpression or can represent a StackVariable.
class StackVariable {
    friend class StackVariableHash;
 
 public:
    static bool repOk(const IR::Expression *expr);
 
    // Implements comparisons so that StateVariables can be used as map keys.
    bool operator==(const StackVariable &other) const;
 
 private:
    const IR::Expression *variable;
 
 public:
    StackVariable(const IR::Expression *expr);  // NOLINT(runtime/explicit)
};

class StackVariableHash {
 public:
    size_t operator()(const StackVariable &var) const;
};
 
typedef std::unordered_map<StackVariable, size_t, StackVariableHash> StackVariableMap;
typedef std::unordered_map<StackVariable, const IR::Expression *, StackVariableHash>
    StackVariableIndexMap;

struct ParserStateInfo {
    friend class ParserStateRewriter;
    cstring name;  // new state name
    const IR::P4Parser *parser;
    const IR::ParserState *state;        // original state this is produced from
    const ParserStateInfo *predecessor;  // how we got here in the symbolic evaluation
    ValueMap *before;
    ValueMap *after;
    IR::ParserState *newState;  // pointer to a new state
    size_t currentIndex;
    StackVariableMap statesIndexes;  // global map in state indexes
    // set of parsers' states names with are in current path.
    std::unordered_set<cstring> scenarioStates;
    std::unordered_set<cstring> scenarioHS;    // scenario header stack's operations
    StackVariableIndexMap substitutedIndexes;  // values of the evaluated indexes
    ParserStateInfo(cstring name, const IR::P4Parser *parser, const IR::ParserState *state,
                    const ParserStateInfo *predecessor, ValueMap *before, size_t index)
        : name(name),
          parser(parser),
          state(state),
          predecessor(predecessor),
          before(before),
          after(nullptr),
          newState(nullptr),
          currentIndex(index) {
        CHECK_NULL(parser);
        CHECK_NULL(state);
        CHECK_NULL(before);
        if (predecessor) {
            statesIndexes = predecessor->statesIndexes;
            scenarioHS = predecessor->scenarioHS;
            substitutedIndexes = predecessor->substitutedIndexes;
        }
    }
};

class ParserInfo {
    friend class RewriteAllParsers;
    // for each original state a vector of states produced by unrolling
    std::vector<ParserStateInfo *> *ordered_states = new std::vector<ParserStateInfo *>();
    std::map<cstring, std::vector<ParserStateInfo *> *> states;
 
 public:
    std::vector<ParserStateInfo *> *get(ParserStateInfo *si) {
        cstring origState = si->state->name.name;
        std::vector<ParserStateInfo *> *vec;
        auto it = states.find(origState);
        if (it == states.end()) {
            vec = new std::vector<ParserStateInfo *>;
            states.emplace(origState, vec);
            ordered_states->push_back(si);
        } else {
            vec = it->second;
        }
        return vec;
    }
    void add(ParserStateInfo *si) {
        auto vec = get(si);
        vec->push_back(si);
    }
    std::map<cstring, std::vector<ParserStateInfo *> *> &getStates() { return states; }
};
 
typedef CallGraph<const IR::ParserState *> StateCallGraph;

class ParserStructure {
    friend class ParserStateRewriter;
    friend class ParserSymbolicInterpreter;
    friend class AnalyzeParser;
    std::map<cstring, const IR::ParserState *> stateMap;
 
 public:
    const IR::P4Parser *parser;
    const IR::ParserState *start;
    const ParserInfo *result;
    StateCallGraph *callGraph;
    std::map<cstring, std::set<cstring>> statesWithHeaderStacks;
    std::map<cstring, size_t> callsIndexes;  // map for curent calls of state insite current one
    void setParser(const IR::P4Parser *parser) {
        CHECK_NULL(parser);
        callGraph = new StateCallGraph(parser->name.name);
        this->parser = parser;
        start = nullptr;
    }
    void addState(const IR::ParserState *state) { stateMap.emplace(state->name, state); }
    const IR::ParserState *get(cstring state) const { return ::P4::get(stateMap, state); }
    void calls(const IR::ParserState *caller, const IR::ParserState *callee) {
        callGraph->calls(caller, callee);
    }
 
    bool analyze(ReferenceMap *refMap, TypeMap *typeMap, bool unroll, bool &wasError);
    bool reachableHSUsage(IR::ID id, const ParserStateInfo *state) const;
 
 protected:
    void evaluateReachability();
    void addStateHSUsage(const IR::ParserState *state, const IR::Expression *expression);
};
 
class AnalyzeParser : public Inspector {
    const ReferenceMap *refMap;
    ParserStructure *current;
    const IR::ParserState *currentState;
 
 public:
    AnalyzeParser(const ReferenceMap *refMap, ParserStructure *current)
        : refMap(refMap), current(current), currentState(nullptr) {
        CHECK_NULL(refMap);
        CHECK_NULL(current);
        setName("AnalyzeParser");
        visitDagOnce = false;
    }
 
    bool preorder(const IR::P4Parser *parser) override {
        LOG2("Scanning " << parser);
        current->setParser(parser);
        return true;
    }
    bool preorder(const IR::ParserState *state) override;
    void postorder(const IR::ParserState *state) override;
    void postorder(const IR::ArrayIndex *array) override;
    void postorder(const IR::Member *member) override;
    void postorder(const IR::PathExpression *expression) override;
};
 
// Applied to a P4Parser object.
class ParserRewriter : public PassManager {
    ParserStructure current;
    friend class RewriteAllParsers;
 
 public:
    bool hasOutOfboundState;
    bool wasError;
    ParserRewriter(ReferenceMap *refMap, TypeMap *typeMap, bool unroll) {
        CHECK_NULL(refMap);
        CHECK_NULL(typeMap);
        wasError = false;
        setName("ParserRewriter");
        addPasses({
            new AnalyzeParser(refMap, &current),
            [this, refMap, typeMap, unroll](void) {
                hasOutOfboundState = current.analyze(refMap, typeMap, unroll, wasError);
            },
        });
    }
};

// The following are applied to the entire program
 
struct ParserConfig {
    bool unroll = true;
    bool order_states = false;
};
 
class RewriteAllParsers : public Transform {
    ReferenceMap *refMap;
    ParserConfig config;
    TypeMap *typeMap;
 
 public:
    RewriteAllParsers(ReferenceMap *refMap, TypeMap *typeMap, ParserConfig config)
        : refMap(refMap), config(config), typeMap(typeMap) {
        CHECK_NULL(refMap);
        CHECK_NULL(typeMap);
        setName("RewriteAllParsers");
    }
 
    // start generation of a code
    const IR::Node *postorder(IR::P4Parser *parser) override {
        // making rewriting
        auto rewriter = new ParserRewriter(refMap, typeMap, config.unroll);
        rewriter->setCalledBy(this);
        parser->apply(*rewriter);
        if (rewriter->wasError) {
            return parser;
        }
        BUG_CHECK(rewriter->current.result,
                  "No result was found after unrolling of the parser loop");
        IR::P4Parser *newParser = parser->clone();
        IR::IndexedVector<IR::ParserState> states = newParser->states;
        newParser->states.clear();
        if (rewriter->hasOutOfboundState) {
            // generating state with verify(false, error.StackOutOfBounds)
            IR::Vector<IR::Argument> *arguments = new IR::Vector<IR::Argument>();
            arguments->push_back(new IR::Argument(IR::BoolLiteral::get(false)));
            arguments->push_back(new IR::Argument(
                new IR::Member(new IR::TypeNameExpression(new IR::Type_Name(IR::ID("error"))),
                               IR::ID("StackOutOfBounds"))));
            IR::IndexedVector<IR::StatOrDecl> components;
            IR::IndexedVector<IR::Parameter> parameters;
            parameters.push_back(
                new IR::Parameter(IR::ID("check"), IR::Direction::In, IR::Type::Boolean::get()));
            parameters.push_back(new IR::Parameter(IR::ID("toSignal"), IR::Direction::In,
                                                   new IR::Type_Name(IR::ID("error"))));
            components.push_back(new IR::MethodCallStatement(new IR::MethodCallExpression(
                IR::Type::Void::get(),
                new IR::PathExpression(
                    new IR::Type_Method(IR::Type::Void::get(), new IR::ParameterList(parameters),
                                        "*method"_cs),
                    new IR::Path(IR::ID("verify"))),
                arguments)));
            auto *outOfBoundsState = new IR::ParserState(
                IR::ID(outOfBoundsStateName), components,
                new IR::PathExpression(IR::Type_State::get(),
                                       new IR::Path(IR::ParserState::reject, false)));
            newParser->states.push_back(outOfBoundsState);
        }
 
        if (config.order_states) {
            if (rewriter->current.result->ordered_states) {
                for (auto &i : *rewriter->current.result->ordered_states) {
                    if (rewriter->hasOutOfboundState && i->name == "stateOutOfBound") {
                        continue;
                    }
                    newParser->states.push_back(i->state);
                }
            }
        } else {
            for (auto &i : rewriter->current.result->states) {
                for (auto &j : *i.second)
                    if (j->newState) {
                        if (rewriter->hasOutOfboundState &&
                            j->newState->name.name == "stateOutOfBound") {
                            continue;
                        }
                        newParser->states.push_back(j->newState);
                    }
            }
        }
        // adding accept/reject
        newParser->states.push_back(new IR::ParserState(IR::ParserState::accept, nullptr));
        newParser->states.push_back(new IR::ParserState(IR::ParserState::reject, nullptr));
 
        return newParser;
    }
};
 
class ParsersUnroll : public PassManager {
 public:
    ParsersUnroll(ParserConfig config, ReferenceMap *refMap, TypeMap *typeMap) {
        // remove block statements
        passes.push_back(new SimplifyControlFlow(typeMap, false));
        passes.push_back(new TypeChecking(refMap, typeMap));
        passes.push_back(new RewriteAllParsers(refMap, typeMap, config));
        setName("ParsersUnroll");
    }
};
 
}  // namespace P4
 
#endif /* MIDEND_PARSERUNROLL_H_ */