I imagine a fancier version would be to compare the Abstract Syntax Trees.

I've always thought it would make sense for formatters to be baked into the toolchain so that they can reuse the language's parser (presumably exposed as a library) and then be implemented via parsing to AST and then formatted back out so that they're guaranteed to be correct and normalized. This doesn't seem to be how most formatters work in practice though, although I'm not sure if it's because of performance reasons or a lack of support for the parser being exposed in language toolchains.

That is essentially what clang-format is.

The only issue is then you're at the mercy of whatever parser your formatter uses to construct the AST

Well, if any (common, non-hobby) parser is thrown off by the reformatting, then it's probably not a safe reformatting either way.