1 // Copyright 2021 The Tint Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_ 16 #define FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_ 17 18 #include <unordered_map> 19 20 #include "src/program.h" 21 22 namespace tint { 23 namespace fuzzers { 24 namespace ast_fuzzer { 25 26 /// Contains a one-to-one mapping between the nodes in the AST of the program 27 /// and their ids. 28 /// 29 /// The motivation for having this mapping is: 30 /// - To be able to uniquely identify a node in the AST. This will be used 31 /// to record transformations in the protobuf messages. 32 /// - When the AST is being modified, only the mapping for the modified nodes 33 /// must be affected. That is, if some node is unchanged, it must have the 34 /// same id defined in this class. 35 /// 36 /// This class achieves these goals partially. Concretely, the only way to 37 /// change the AST is by cloning it since all instances of `tint::ast::` classes 38 /// are immutable. This will invalidate all the pointers to the AST nodes which 39 /// are used in this class. To overcome this, a new instance of this class is 40 /// created with all the cloned nodes and the old instance is discarded. 41 class NodeIdMap { 42 public: 43 /// Type of the id used by this map. 44 using IdType = uint32_t; 45 46 /// Creates an empty map. 47 NodeIdMap(); 48 49 /// @brief Initializes this instance with all the nodes in the `program`. 50 /// @param program - must be valid. 51 explicit NodeIdMap(const Program& program); 52 53 /// @brief Returns a node for the given `id`. 54 /// @param id - any value is accepted. 55 /// @return a pointer to some node if `id` exists in this map. 56 /// @return `nullptr` otherwise. 57 const ast::Node* GetNode(IdType id) const; 58 59 /// @brief Returns an id of the given `node`. 60 /// @param node - can be a `nullptr`. 61 /// @return not equal to 0 if `node` exists in this map. 62 /// @return 0 otherwise. 63 IdType GetId(const ast::Node* node) const; 64 65 /// @brief Adds a mapping from `node` to `id` to this map. 66 /// @param node - may not be a `nullptr` and can't be present in this map. 67 /// @param id - may not be 0 and can't be present in this map. 68 void Add(const ast::Node* node, IdType id); 69 70 /// @brief Returns whether the id is fresh by checking if it exists in 71 /// the id map and the id is not 0. 72 /// @param id - an id that is used to check in the map. 73 /// @return true the given id is fresh and valid (non-zero). 74 /// @return false otherwise. 75 bool IdIsFreshAndValid(IdType id); 76 77 /// @brief Returns an id that is guaranteed to be unoccupied in this map. 78 /// 79 /// This will effectively increase the counter. This means that two 80 /// consecutive calls to this method will return different ids. 81 /// 82 /// @return an unoccupied id. 83 IdType TakeFreshId(); 84 85 private: 86 IdType fresh_id_ = 1; 87 88 std::unordered_map<const ast::Node*, IdType> node_to_id_; 89 std::unordered_map<IdType, const ast::Node*> id_to_node_; 90 }; 91 92 } // namespace ast_fuzzer 93 } // namespace fuzzers 94 } // namespace tint 95 96 #endif // FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_ 97