Page MenuHomePhabricator

[GraphDiff] Extend GraphDiff to track a list of updates.

Authored by asbirlea on Mar 31 2020, 1:22 PM.



This patch includes two extensions:

  1. It extends the GraphDiff to also keep the original list of updates

after legalization, not just the deletes/insert vectors.
It also provides an API to pop the first update (the updates are store
in reverse, such that the first update is at the end of the list)

  1. It adds a bool to mark whether the given updates should be applied as

given, or applied in reverse. This moves the task of reversing the
updates (when the caller needs this) to a functionality inside
GraphDiff, versus having the caller do this.

The two changes could be split into two patches, but they seemed
reasonably small to be reviewed together.

Diff Detail

Event Timeline

asbirlea created this revision.Mar 31 2020, 1:22 PM
asbirlea updated this revision to Diff 253981.Mar 31 2020, 1:23 PM


kuhar accepted this revision.Mar 31 2020, 2:02 PM



nit: to apply these updates forward/as-is/...?


I don't think it makes any difference whatsoever, but maybe set the size to 0 here? There's a SmallVector specialization for that case.




nit: getNumLegalizedUpdates


nit: this if-else spans 13 lines, consider adding braces


nit: this looks weird; did clang-format split it like this?

This revision is now accepted and ready to land.Mar 31 2020, 2:02 PM
dblaikie added inline comments.Apr 1 2020, 2:13 PM

Perhaps making a struct { Succ, Pred } & then you could even have an array of [2] of these and index into it with isInsert, so delete ones are at index zero and the succeess ones are at index 1. Could make the existing code and the new use of these maps a bit tidier (that if/else around line 156 -separates the initialization from the declarations and duplicates a fair bit of text between the two sides, making it less obvious what's different on either side)


I'd /probably/ rephrase this as:

sort(Result, [&] (...) {
  const auto &OpA = Operations...;
  const auto &OpB = ...;
  return ReverseResultOrder ? OpA < OpB
       OpA > OpB;

Or something roughly like that - as it'd make it easier to see the difference between the two cases rather than trying to look at two blocks of very similar code and spot the </> difference in amongst all the other content.

Should this have any tests (unit or otherwise)?

asbirlea updated this revision to Diff 254624.Apr 2 2020, 2:35 PM
asbirlea marked 8 inline comments as done.

Address comments.
Update condition to filter nullptr in clang.

dblaikie added inline comments.Apr 2 2020, 3:02 PM

These two variables are uninitialized & used later, guess the uses should be changed to Edges[IsInsert], etc...

(or since they're used in a few places, you could: const auto &E = Edges[IsInsert]; .... E.Pred(..), E.Succ(...))

asbirlea updated this revision to Diff 254635.Apr 2 2020, 3:46 PM
asbirlea marked an inline comment as done.

Address comment. Thanks for noticing!

dblaikie accepted this revision.Apr 2 2020, 4:35 PM

Sounds good :)

This revision was automatically updated to reflect the committed changes.