From af73844b975f45b339bc22fb735a09f0384cf08f Mon Sep 17 00:00:00 2001 From: Dodji Seketeli Date: Mon, 3 Sep 2018 11:10:25 +0200 Subject: [PATCH] Add option to avoid walking abigail::ir nodes twice When the ir_traversable_base::traverse() walks the IR graph, it happens that it can visit a type node that was already visited before. For instance, it visits the 'struct S' once and later, as part of its visit of struct S*, it can visit struct S again. There are use cases where we want the walker to avoid visiting a given type node again. This patch adds the option to do so. Basically the ir_node_visitor class can now be configured to tell the walker to avoid re-visiting a node. The test-ir-walker.cc example is amended to avoid re-visiting type nodes as well. * include/abg-ir.h (struct ir_node_visitor): Make this be a class. Add a private data member to it, following the 'pimpl' idiom. (ir_node_visitor::{allow_visiting_already_visited_type_node, mark_type_node_as_visited, forget_visited_type_nodes, type_node_has_been_visited}): Declare new member functions. * src/abg-ir.cc ({type_base, type_decl, scope_type_decl, qualified_type_decl, pointer_type_def, reference_type_def, array_type_def, enum_type_decl, typedef_decl, class_or_union, class_decl, union_decl}::traverse): Avoid re-visiting the type node if the visitor was configured as such. (struct ir_node_visitor::priv): Define new struct. (ir_node_visitor::{allow_visiting_already_visited_type_node, mark_type_node_as_visited, forget_visited_type_nodes, type_node_has_been_visited}): Define new member functions. * tests/test-ir-walker.cc (name_printing_visitor::name_printing_visitor): Avoid visiting a type node twice. Signed-off-by: Dodji Seketeli --- include/abg-ir.h | 20 +++- src/abg-ir.cc | 201 +++++++++++++++++++++++++++++++++++++--- tests/test-ir-walker.cc | 6 +- 3 files changed, 212 insertions(+), 15 deletions(-) diff --git a/include/abg-ir.h b/include/abg-ir.h index bdd6526c..85a7d050 100644 --- a/include/abg-ir.h +++ b/include/abg-ir.h @@ -107,6 +107,9 @@ namespace ir // Inject some std::tr1 types in here. using std::tr1::unordered_map; +/// A convenience typedef fo r an ordered set of size_t. +typedef unordered_set pointer_set; + /// This is an abstraction of the set of resources necessary to manage /// several aspects of the internal representations of the Abigail /// library. @@ -4348,8 +4351,23 @@ struct class_tdecl::shared_ptr_hash /// That new visitor class would then be passed to e.g, /// translation_unit::traverse or to the traverse method of any type /// where the traversal is supposed to start from. -struct ir_node_visitor : public node_visitor_base +class ir_node_visitor : public node_visitor_base { + struct priv; + typedef shared_ptr priv_sptr; + + priv_sptr priv_; + +public: + + ir_node_visitor(); + + void allow_visiting_already_visited_type_node(bool); + bool allow_visiting_already_visited_type_node() const; + void mark_type_node_as_visited(type_base *); + void forget_visited_type_nodes(); + bool type_node_has_been_visited(type_base*) const; + virtual bool visit_begin(decl_base*); virtual bool visit_end(decl_base*); diff --git a/src/abg-ir.cc b/src/abg-ir.cc index ec9bd4ed..c49070a7 100644 --- a/src/abg-ir.cc +++ b/src/abg-ir.cc @@ -10821,8 +10821,14 @@ type_base::get_alignment_in_bits() const bool type_base::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + v.visit_begin(this); - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + + return result; } type_base::~type_base() @@ -11328,9 +11334,14 @@ type_decl::get_pretty_representation(bool internal) const bool type_decl::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + v.visit_begin(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); - return v.visit_end(this); + return result; } type_decl::~type_decl() @@ -11454,6 +11465,9 @@ scope_type_decl::traverse(ir_node_visitor& v) if (visiting()) return true; + if (v.type_node_has_been_visited(this)) + return true; + if (v.visit_begin(this)) { visiting(true); @@ -11466,7 +11480,10 @@ scope_type_decl::traverse(ir_node_visitor& v) visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + + return result; } scope_type_decl::~scope_type_decl() @@ -11877,6 +11894,9 @@ qualified_type_def::get_qualified_name(bool internal) const bool qualified_type_def::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -11887,7 +11907,9 @@ qualified_type_def::traverse(ir_node_visitor& v) t->traverse(v); visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } qualified_type_def::~qualified_type_def() @@ -12252,6 +12274,9 @@ pointer_type_def::get_qualified_name(bool internal) const bool pointer_type_def::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -12262,7 +12287,10 @@ pointer_type_def::traverse(ir_node_visitor& v) t->traverse(v); visiting(false); } - return v.visit_end(this); + + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } pointer_type_def::~pointer_type_def() @@ -12496,6 +12524,9 @@ reference_type_def::get_qualified_name(bool internal) const bool reference_type_def::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -12506,7 +12537,10 @@ reference_type_def::traverse(ir_node_visitor& v) t->traverse(v); visiting(false); } - return v.visit_end(this); + + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } reference_type_def::~reference_type_def() @@ -12915,6 +12949,9 @@ array_type_def::subrange_type::get_pretty_representation(bool) const bool array_type_def::subrange_type::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (v.visit_begin(this)) { visiting(true); @@ -12923,7 +12960,9 @@ array_type_def::subrange_type::traverse(ir_node_visitor& v) visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } // @@ -13248,6 +13287,9 @@ array_type_def::get_qualified_name(bool internal) const bool array_type_def::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -13258,7 +13300,10 @@ array_type_def::traverse(ir_node_visitor& v) t->traverse(v); visiting(false); } - return v.visit_end(this); + + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } const location& @@ -13369,6 +13414,9 @@ enum_type_decl::get_pretty_representation(bool internal) const bool enum_type_decl::traverse(ir_node_visitor &v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -13379,7 +13427,10 @@ enum_type_decl::traverse(ir_node_visitor &v) t->traverse(v); visiting(false); } - return v.visit_end(this); + + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } /// Destructor for the enum type declaration. @@ -13949,6 +14000,9 @@ typedef_decl::get_underlying_type() const bool typedef_decl::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -13959,7 +14013,10 @@ typedef_decl::traverse(ir_node_visitor& v) t->traverse(v); visiting(false); } - return v.visit_end(this); + + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } typedef_decl::~typedef_decl() @@ -14970,6 +15027,10 @@ function_type::get_pretty_representation(bool internal) const bool function_type::traverse(ir_node_visitor& v) { + // TODO: should we allow the walker to avoid visiting function type + // twice? I think that if we do, then ir_node_visitor needs an + // option to specifically disallow this feature for function types. + if (visiting()) return true; @@ -16465,6 +16526,9 @@ class_or_union::class_or_union(const environment* env, const string& name, bool class_or_union::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -16527,7 +16591,9 @@ class_or_union::traverse(ir_node_visitor& v) visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } /// Destrcutor of the @ref class_or_union type. @@ -17955,6 +18021,7 @@ class_decl::base_spec::traverse(ir_node_visitor& v) get_base_class()->traverse(v); visiting(false); } + return v.visit_end(this); } @@ -18913,6 +18980,9 @@ operator!=(const class_decl_sptr& l, const class_decl_sptr& r) bool class_decl::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -18986,7 +19056,9 @@ class_decl::traverse(ir_node_visitor& v) visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } /// Destructor of the @ref class_decl type. @@ -19512,6 +19584,9 @@ union_decl::operator==(const union_decl& other) const bool union_decl::traverse(ir_node_visitor& v) { + if (v.type_node_has_been_visited(this)) + return true; + if (visiting()) return true; @@ -19574,7 +19649,9 @@ union_decl::traverse(ir_node_visitor& v) visiting(false); } - return v.visit_end(this); + bool result = v.visit_end(this); + v.mark_type_node_as_visited(this); + return result; } /// Destructor of the @ref union_decl type. @@ -20917,6 +20994,102 @@ bool ir_traversable_base::traverse(ir_node_visitor&) {return true;} +// + +/// The private data structure of the ir_node_visitor type. +struct ir_node_visitor::priv +{ + pointer_set visited_ir_nodes; + bool allow_visiting_already_visited_type_node; + + priv() + : allow_visiting_already_visited_type_node(true) + {} +}; // end struct ir_node_visitory::priv + +/// Default Constructor of the ir_node_visitor type. +ir_node_visitor::ir_node_visitor() + : priv_(new priv) +{} + +/// Set if the walker using this visitor is allowed to re-visit a type +/// node that was previously visited or not. +/// +/// @param f if true, then the walker using this visitor is allowed to +/// re-visit a type node that was previously visited. +void +ir_node_visitor::allow_visiting_already_visited_type_node(bool f) +{priv_->allow_visiting_already_visited_type_node = f;} + +/// Get if the walker using this visitor is allowed to re-visit a type +/// node that was previously visited or not. +/// +/// @return true iff the walker using this visitor is allowed to +/// re-visit a type node that was previously visited. +bool +ir_node_visitor::allow_visiting_already_visited_type_node() const +{return priv_->allow_visiting_already_visited_type_node;} + +/// Mark a given type node as having been visited. +/// +/// Note that for this function to work, the type node must have been +/// canonicalized. Otherwise the process is aborted. +/// +/// @param p the type to mark as having been visited. +void +ir_node_visitor::mark_type_node_as_visited(type_base *p) +{ + if (allow_visiting_already_visited_type_node()) + return; + + if (p == 0 || type_node_has_been_visited(p)) + return; + + type_base* canonical_type = p->get_naked_canonical_type(); + assert(canonical_type); + + size_t canonical_ptr_value = reinterpret_cast(canonical_type); + priv_->visited_ir_nodes.insert(canonical_ptr_value); +} + +/// Un-mark all visited type nodes. +/// +/// That is, no type node is going to be considered as having been +/// visited anymore. +/// +/// In other words, after invoking this funciton, +/// ir_node_visitor::type_node_has_been_visited() is going to return +/// false on all type nodes. +void +ir_node_visitor::forget_visited_type_nodes() +{priv_->visited_ir_nodes.clear();} + +/// Test if a given type node has been marked as visited. +/// +/// @param p the type node to consider. +/// +/// @return true iff the type node @p p has been marked as visited by +/// the function ir_node_visitor::mark_type_node_as_visited. +bool +ir_node_visitor::type_node_has_been_visited(type_base* p) const +{ + if (allow_visiting_already_visited_type_node()) + return false; + + if (p == 0) + return false; + + type_base *canonical_type = p->get_naked_canonical_type(); + assert(canonical_type); + + size_t ptr_value = reinterpret_cast(canonical_type); + pointer_set::iterator it = priv_->visited_ir_nodes.find(ptr_value); + if (it == priv_->visited_ir_nodes.end()) + return false; + + return true; +} + bool ir_node_visitor::visit_begin(decl_base*) {return true;} @@ -21117,6 +21290,8 @@ bool ir_node_visitor::visit_end(member_class_template* d) {return visit_end(static_cast(d));} +// + // /// Generate a different string at each invocation. diff --git a/tests/test-ir-walker.cc b/tests/test-ir-walker.cc index 8e434d6a..eebe121f 100644 --- a/tests/test-ir-walker.cc +++ b/tests/test-ir-walker.cc @@ -67,7 +67,11 @@ struct name_printing_visitor : public abigail::ir_node_visitor name_printing_visitor() : level_() - {} + { + // Using this visitor, the IR walker will visit each type only + // once. + allow_visiting_already_visited_type_node(false); + } void build_level_prefix(string& str) -- 2.43.5