Use STL containers when requiring pointer/iterator stability
From https://abseil.io/about/design/btree:
When values are inserted or removed from a B-tree, nodes can be split or merged and values can be moved within and between nodes (for the purpose of maintaining tree balance). This means that when values are inserted or removed from a B-tree container, pointers and iterators to other values in the B-tree can be invalidated. Abseil B-trees therefore do not provide pointer stability or iterator stability - this is in contrast to STL sorted containers that do provide these guarantees.
BinDiff incorrectly relies on pointer stability and iterator stability when using btree data structures in a number of places:
indexed_fixed_points_is a vector of pointers toFixedPointInfos held in aabsl::btree_setindexed_flow_graphs1_andindexed_flow_graphs2_are vectors of pointers toFlowGraphInfos held in aabsl::btree_mapResults::DeleteMatchescallshistogram_.erasewhile iterating overhistogram_which is aabsl::btree_map, invalidating the iterator
You can see the effects of these incorrect assumptions by manually removing and adding matches in the IDA plugin. You will see duplicate matches appearing and functions being erased from the database entirely.
This PR fixes the issue by replacing the types that depend on pointer/iterator stability with their STL equivalents.
Thank you for your PR!
While replacing Abseil maps/sets with their STL equivalents will fix the issues you mentioned, we deliberately removed all/most uses of STL maps/sets from the code base.
It seems we did not read the API contracts carefully enough and there are not enough tests to catch these issues.
Let's first fix the obvious deficiency in Results::DeleteMatches() and then debug the others.
Switching back to std::map<>/std::set<> is not really a good option for us. We may need to add another indirection by having the containers store pointers instead.