  We apply the method of nonlinear steepest descent to compute the long-time
asymptotics of solutions of the Korteweg--de Vries equation which are decaying
perturbations of a quasi-periodic finite-gap background solution. We compute a
nonlinear dispersion relation and show that the $x/t$ plane splits into $g+1$
soliton regions which are interlaced by $g+1$ oscillatory regions, where $g+1$
is the number of spectral gaps.
  In the soliton regions the solution is asymptotically given by a number of
solitons travelling on top of finite-gap solutions which are in the same
isospectral class as the background solution. In the oscillatory region the
solution can be described by a modulated finite-gap solution plus a decaying
dispersive tail. The modulation is given by phase transition on the isospectral
torus and is, together with the dispersive tail, explicitly characterized in
terms of Abelian integrals on the underlying hyperelliptic curve.
