How do I rewrite paths in an AST's import tree?

I'm writing a program that will update a Rust project's imports to be from their new locations after a breaking change in a library. In this instance, I'd like to flatten all imports from vexide::devices::item to just vexide::item.

So far, I've tried using the ra_ap_syntax crate¹, which has a data structure for representing Rust's use construct as tree of paths and sub-paths. For example, the following imports are parsed like this:

use vexide::{devices::smart::*, prelude::*};
use vexide::devices::*;
use vexide::devices::smart::Motor;
use vexide::{devices, fs};
use vexide::devices;
use vexide::devices::{smart, adi};
use {vexide::{devices, fs}, core::borrow};

// (path)? (*)? -> [ sub-items, ... ]
"vexide" -> [ "devices::smart" *, "prelude" * ]
"vexide::devices" *
"vexide::devices::smart::Motor"
"vexide" -> [ "devices", "fs" ]
"vexide::devices"
"vexide::devices" -> [ "smart", "adi" ]
-> ["vexide" -> [ "devices", "fs" ], "core::borrow" ]

It seems to me that I will need to do a depth-first search and keep track of the full path of the import as I enter and leave each item. But, what's the best way to write my logic when visiting each node of the import tree? To me it seems like there are so many edge cases it's overwhelming: in the case of vexide::devices::smart I need to rewrite the path to vexide::smart, but if it were vexide::{device::{smart, adi}} I would have to delete the node and move all the children up a layer, and so on.

_{1. I chose this library because it preserves comments and formatting in the file I'm editing.}

Here is what I have tentatively started with, but I'm primarily concerned with what logic I need to implement rather than exactly how to do so.

use ra_ap_syntax::{*, ast::{*, make::path_from_str}};

// Find all imports in a file and rewrite them.
pub fn rewrite_imports(root: SyntaxNode) {
    for use_item in root.descendants().filter_map(Use::cast) {
        let mut ancestors = String::new();

        let Some(tree) = old_use.use_tree() else {
            continue;
        };

        rewrite_use_tree(&root, &tree);
        println!();
    }
}

// Rewrite a single `use` and its sub-paths
fn rewrite_use_tree(root: &SyntaxNode, tree: &UseTree) {
    // ???

    // Possible implementation...?
    // Get old path, replace import, write it back.
    let path = tree.path().unwrap();
    let new_path = path.to_string().replace("vexide::devices", "vexide");
    root.replace(path.syntax(), path_from_str(new_path).syntax()));

    // Recurse
    if let Some(list) = tree.use_tree_list() {
        for tree in list.use_trees() {
            rewrite_use_tree(&tree, moved_items, ancestors);
        }
    }
}

The easiest way I can think of to perform an operation like this is to create a custom data structure better suited for transformations alongside conversion routines to and from the original syntax data.

struct ImportTree {
    storage: slab::Slab<ImportNode>,
}

struct ImportNode {
    kind: ImportKind,
    /// Index in the slab
    parent_id: Option<usize>,
    syntax: Option<ra_ap_syntax::SyntaxNode>,
}

enum ImportKind {
    /// ::*;
    Star,
    /// ::module[::tail];
    Module {
        ident: Arc<String>, // (no "::" allowed)
        tail_id: Option<usize>,
    },
    /// ::{ [[subnode], ...] };
    List {
        subnode_ids: Vec<usize>,
    },
    /// Syntax nodes which don't neatly fall into any of these categories.
    /// These won't compile but removing them could be unintentional.
    Unknown,
}

With this, you could flatten a module import by simply 1. moving all subnode_ids to the parent and 2. removing the current node from the tree. (You could also add some additional logic like automatically converting between ImportKind::Module and ImportKind::List depending on how many imports there are.)

I recommend storing the original syntax item to avoid losing comment/formatting data for nodes that aren't modified directly.