  Computing differences between tree-structured data is a critical but
challenging problem in software analysis. In this paper, we propose a novel
tree diffing approach called SatDiff, which reformulates the structural diffing
problem into a MaxSAT problem. By encoding the necessary transformations from
the source tree to the target tree, SatDiff generates correct, minimal, and
type safe low-level edit scripts with formal guarantees. We then synthesize
concise high-level edit scripts by effectively merging low-level edits in the
appropriate topological order. Our empirical results demonstrate that SatDiff
outperforms existing heuristic-based approaches by a significant margin in
terms of conciseness while maintaining a reasonable runtime.
