p4RuntimeSymbolTable.h

/*
Copyright 2013-present Barefoot Networks, Inc.
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
    http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
 
#ifndef CONTROL_PLANE_P4RUNTIMESYMBOLTABLE_H_
#define CONTROL_PLANE_P4RUNTIMESYMBOLTABLE_H_
 
#include "lib/cstring.h"
#include "p4RuntimeArchHandler.h"
#include "typeSpecConverter.h"
 
namespace p4 {
namespace config {
namespace v1 {
class P4Info;
}  // namespace v1
}  // namespace config
namespace v1 {
class WriteRequest;
}  // namespace v1
}  // namespace p4
 
namespace P4::IR {
class P4Program;
}  // namespace P4::IR
 
namespace P4 {
 
namespace ControlPlaneAPI {
 
const p4rt_id_t INVALID_ID = ::p4::config::v1::P4Ids::UNSPECIFIED;
 
bool isControllerHeader(const IR::Type_Header *type);
 
bool isHidden(const IR::IAnnotated *node);
 
std::optional<p4rt_id_t> getIdAnnotation(const IR::IAnnotated *node);
 
struct P4SymbolSuffixSet {
    void addSymbol(const cstring &symbol);
 
    cstring shortestUniqueSuffix(const cstring &symbol) const;
 
 private:
    // All symbols in the set. We store these separately to make sure that no
    // symbol is added to the tree of suffixes more than once.
    std::set<cstring> symbols;
 
    // A node in the tree of suffixes. The tree of suffixes is a directed graph
    // of path components, with the edges pointing from the each component to
    // its predecessor, so that every suffix of every symbol corresponds to a
    // path through the tree. For example, "foo.bar[1].baz" would be represented
    // as "baz" -> "bar[1]" -> "foo".
    struct SuffixNode {
        // How many suffixes pass through this node? This includes suffixes that
        // terminate at this node.
        unsigned instances = 0;
 
        // Outgoing edges from this node. The SuffixNode should never be null.
        std::map<cstring, SuffixNode *> edges;
    };
 
    // The root of our tree of suffixes. Note that this is *not* the data
    // structure known as a suffix tree.
    SuffixNode *suffixesRoot = new SuffixNode;
};
 
class P4RuntimeSymbolTable : public P4RuntimeSymbolTableIface {
 public:
    template <typename Func>
    static P4RuntimeSymbolTable *create(Func function) {
        // Create and initialize the symbol table. At this stage, ids aren't
        // available, because computing ids requires global knowledge of all the
        // P4Runtime symbols in the program.
        auto *symbols = new P4RuntimeSymbolTable();
        function(*symbols);
 
        // Now that the symbol table is initialized, we can compute ids.
        for (auto &table : symbols->symbolTables) {
            symbols->computeIdsForSymbols(table.first);
        }
 
        return symbols;
    }
 
    static P4RuntimeSymbolTable *generateSymbols(const IR::P4Program *program,
                                                 const IR::ToplevelBlock *evaluatedProgram,
                                                 ReferenceMap *refMap, TypeMap *typeMap,
                                                 P4RuntimeArchHandlerIface *archHandler);
 
    void add(P4RuntimeSymbolType type, const IR::IDeclaration *declaration) override;
 
    void add(P4RuntimeSymbolType type, cstring name,
             std::optional<p4rt_id_t> id = std::nullopt) override;
 
    p4rt_id_t getId(P4RuntimeSymbolType type, const IR::IDeclaration *declaration) const override;
 
    p4rt_id_t getId(P4RuntimeSymbolType type, cstring name) const override;
 
    cstring getAlias(cstring name) const override;
 
 private:
    // Rather than call this constructor, use P4RuntimeSymbolTable::create().
    P4RuntimeSymbolTable() = default;
 
    p4rt_id_t tryToAssignId(std::optional<p4rt_id_t> id);
 
    void computeIdsForSymbols(P4RuntimeSymbolType type);
 
    template <typename ConstructIdFunc>
    std::optional<p4rt_id_t> probeForId(const uint32_t sourceValue, ConstructIdFunc constructId) {
        uint32_t value = sourceValue;
        while (assignedIds.find(constructId(value)) != assignedIds.end()) {
            ++value;
            if (value == sourceValue) {
                return std::nullopt;  // We wrapped around; there's no unassigned
                                      // id left.
            }
        }
 
        return constructId(value);
    }
 
    // The hash function used for resource names.
    // Taken from: https://en.wikipedia.org/wiki/Jenkins_hash_function
    static uint32_t jenkinsOneAtATimeHash(const char *key, size_t length);
 
    // All the ids we've assigned so far. Used to avoid id collisions; this is
    // especially crucial since ids can be set manually via the '@id'
    // annotation.
    std::set<p4rt_id_t> assignedIds;
 
    // Symbol tables, mapping symbols to P4Runtime ids.
    using SymbolTable = std::map<cstring, p4rt_id_t>;
    std::map<P4RuntimeSymbolType, SymbolTable> symbolTables{};
 
    // A set which contains all the symbols in the program. It's used to compute
    // the shortest unique suffix of each symbol, which is the default alias we
    // use for P4Runtime objects.
    P4SymbolSuffixSet suffixSet;
};
 
void collectControlSymbols(P4RuntimeSymbolTable &symbols, P4RuntimeArchHandlerIface *archHandler,
                           const IR::ControlBlock *controlBlock, ReferenceMap *refMap,
                           TypeMap *typeMap);
 
void collectExternSymbols(P4RuntimeSymbolTable &symbols, P4RuntimeArchHandlerIface *archHandler,
                          const IR::ExternBlock *externBlock);
 
void collectTableSymbols(P4RuntimeSymbolTable &symbols, P4RuntimeArchHandlerIface *archHandler,
                         const IR::TableBlock *tableBlock);
 
void collectParserSymbols(P4RuntimeSymbolTable &symbols, const IR::ParserBlock *parserBlock);
 
}  // namespace ControlPlaneAPI
 
}  // namespace P4
 
#endif /* CONTROL_PLANE_P4RUNTIMESYMBOLTABLE_H_ */