🤔 I could've sworn I commented on this already, but it looks like I forgot to press the big green submit button.

This is still WIP, and the code is full of untold horrors that I need to go back through and rethink/clean up (and remove my local working commits, like adding roots() to revsets, etc), but I think it's implementing the gist of what you asked about in #448 (comment)

It's been a long time since I've seriously thought about big O notation, so I'm hesitant to make any guesses about my get_connected_components implementations, but I have 2 of them just for fun. I think the second one is more efficient, and may operate in O(n), but if you factor in all of the DAG queries then it becomes O(over my head). 😄 Any comments you have on these would be great; thank you. (I figure we'd just keep 1, but I put in 2 in case 1 was more correct or performant or something.)

Working on this w/ connected components vs my previous approach (that only considered semi-linear "ranges") turned up a bunch of interesting edge cases, many of them involving merge commits. I've tried to document some or all of them in tests, and they may need further attention as this PR solidifies.

There are a few more edge cases that I need to code for (eg moving and inserting multiple components with various "non-stick" structures) but at this point I think I need to just dogfood it for a while to see how it feels and works, updating this as I do.

Thank you!

Sorry for the false start and all of the WIP artifacts you had to wade through on this. I still consider this WIP pending some more dogfooding and proofreading, but I think I've addressed all of your initial comments.

This has been a joy to use locally, but I have mostly been moving single commits. I haven't found myself moving multiple commits, ranges or "range trees" yet. I mean ... the tests say that it works, but I'll be interested in feedback on what happens IRL. 😄

I've been using this for a bit and I haven't noticed any issues so far. What do you say we merge it and fix any issues in follow-up commits?

I think the second one is more efficient, and may operate in O(n)

I never answered this. I think both implementations are O(n^2) because you have one loop over the commits and a nested loop over the existing components to merge any intersecting components. You can do better with a data structure which can merge intersecting components efficiently (disjoint set), but otherwise I think you're likely to have O(n^2) complexity. Mostly we're hoping that we won't have to compute connected components for a large number of commits. If that happens, we can update it to use a better data structure in the future.

Thanks for the nudge. I've read through this again, pushed some clean up and I think it's good enough for now. A couple of notes on what I just pushed:

• Mostly formatting and comments.
• Moved some error checking earlier in the process (checking for 1 parent/component is now consistent w/ checking for 1 root and 1 head).
• I've added a test for moving non-connected components, such as D&F in the following example.
  I'm still 😬 about merging my own code, but since you've signed off on this already, and what I pushed are just minor fixes, I've set it to rebase/merge when CI finishes. Thank you!

One thing that sticks out at me that I'd like to fix in a follow up is that I think the restriction to "only move components with 1 head" is lazy. I don't see any reason we can't move --exact the pink commits in something like this:

graph RL
D --> C --> B --> A
F --> E --> B

classDef pink fill:#f9f;
class B,C,E pink;

I think that restriction predates the component approach and will be straightforward to support. I'll see what I can do. *cracks knuckles*