  The halos of galaxies preserve unique records of their formation histories.
We carry out the first combined observational and theoretical study of
phase-space halo substructure in an early-type galaxy: M87, the central galaxy
in the Virgo cluster. We analyze an unprecedented wide-field, high-precision
photometric and spectroscopic data set for 488 globular clusters (GCs), which
includes new, large-radius Subaru/Suprime-Cam and Keck/DEIMOS observations. We
find signatures of two substructures in position-velocity phase-space. One is a
small, cold stream associated with a known stellar filament in the outer halo;
the other is a large shell-like pattern in the inner halo that implies a
massive, hitherto unrecognized accretion event. We perform extensive
statistical tests and independent metallicity analyses to verify the presence
and characterize the properties of these features, and to provide more general
methodologies for future extragalactic studies of phase-space substructure. The
cold outer stream is consistent with a dwarf galaxy accretion event, while for
the inner shell there is tension between a low progenitor mass implied by the
cold velocity dispersion, and a high mass from the large number of GCs, which
might be resolved by a ~0.5 L* E/S0 progenitor. We also carry out
proof-of-principle numerical simulations of the accretion of smaller galaxies
in an M87-like gravitational potential. These produce analogous features to the
observed substructures, which should have observable lifetimes of ~1 Gyr. The
shell and stream GCs together support a scenario where the extended stellar
envelope of M87 has been built up by a steady rain of material that continues
until the present day. This phase-space method demonstrates unique potential
for detailed tests of galaxy formation beyond the Local Group.
