blob: 78f1590277fb5d33b4e492d5d68e38f0c43b2c64 [file] [log] [blame]
// Copyright 2021 The Tint Authors.
//
// 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 FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_
#define FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_
#include <unordered_map>
#include "src/program.h"
namespace tint {
namespace fuzzers {
namespace ast_fuzzer {
/// Contains a one-to-one mapping between the nodes in the AST of the program
/// and their ids.
///
/// The motivation for having this mapping is:
/// - To be able to uniquely identify a node in the AST. This will be used
/// to record transformations in the protobuf messages.
/// - When the AST is being modified, only the mapping for the modified nodes
/// must be affected. That is, if some node is unchanged, it must have the
/// same id defined in this class.
///
/// This class achieves these goals partially. Concretely, the only way to
/// change the AST is by cloning it since all instances of `tint::ast::` classes
/// are immutable. This will invalidate all the pointers to the AST nodes which
/// are used in this class. To overcome this, a new instance of this class is
/// created with all the cloned nodes and the old instance is discarded.
class NodeIdMap {
public:
/// Type of the id used by this map.
using IdType = uint32_t;
/// Creates an empty map.
NodeIdMap();
/// @brief Initializes this instance with all the nodes in the `program`.
/// @param program - must be valid.
explicit NodeIdMap(const tint::Program& program);
/// @brief Returns a node for the given `id`.
/// @param id - any value is accepted.
/// @return a pointer to some node if `id` exists in this map.
/// @return `nullptr` otherwise.
ast::Node* GetNode(IdType id) const;
/// @brief Returns an id of the given `node`.
/// @param node - can be a `nullptr`.
/// @return not equal to 0 if `node` exists in this map.
/// @return 0 otherwise.
IdType GetId(const ast::Node* node) const;
/// @brief Adds a mapping from `node` to `id` to this map.
/// @param node - may not be a `nullptr` and can't be present in this map.
/// @param id - may not be 0 and can't be present in this map.
void Add(const ast::Node* node, IdType id);
/// @brief Returns whether the id is fresh by checking if it exists in
/// the id map and the id is not 0.
/// @param id - an id that is used to check in the map.
/// @return true the given id is fresh and valid (non-zero).
/// @return false otherwise.
bool IdIsFreshAndValid(IdType id);
/// @brief Returns an id that is guaranteed to be unoccupied in this map.
///
/// This will effectively increase the counter. This means that two
/// consecutive calls to this method will return different ids.
///
/// @return an unoccupied id.
IdType TakeFreshId();
private:
IdType fresh_id_ = 1;
std::unordered_map<ast::Node*, IdType> node_to_id_;
std::unordered_map<IdType, ast::Node*> id_to_node_;
};
} // namespace ast_fuzzer
} // namespace fuzzers
} // namespace tint
#endif // FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_