Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement a reverse post-order iterator in CfgInterface #4

Open
oyeb opened this issue Jun 14, 2020 · 0 comments
Open

Implement a reverse post-order iterator in CfgInterface #4

oyeb opened this issue Jun 14, 2020 · 0 comments
Assignees
Labels
enhancement New feature or request
Milestone

Comments

@oyeb
Copy link
Owner

oyeb commented Jun 14, 2020

This is not very straight forward.

Cache traversal with begin() (or end())

  1. The iterator can be a typedef of the STL cache container type.
  2. The first call to either begin() or end() constructs the cache. This also implies that the cache is owned by the CfgInterface, which can edit the cache at its will -- invalidating existing iterators.
  3. Whenever the cache is empty/null, it must be (re-)constructed.
  4. The iterators obtained from begin() and end() are incomparable as the graph may have been edited between the two calls.

Iterator holds the traversal stack

  1. The iterator is not a simple typedef
  2. begin() returns an object which has the traversal stack inside.
  3. end() is a sentinel instance of the iterator, allowing any call to end() to be comparable to any call to begin() -- given that they are iterators over the same CfgInterface.
  4. Editing the graph while traversing via an iterator leads to undefined behaviour, but it should never crash. A naive implementation can lead to crash when some unvisited worklist node is deleted from the graph (but not from the worklist).
@oyeb oyeb added the enhancement New feature or request label Jun 14, 2020
@oyeb oyeb added this to the v0.1 milestone Jun 14, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants