  We show that, given a word equation over a finitely generated free group, the
set of all solutions in reduced words forms an EDT0L language. In particular,
it is an indexed language in the sense of Aho. The question of whether a
description of solution sets in reduced words as an indexed language is
possible has been been open for some years, apparently without much hope that a
positive answer could hold. Nevertheless, our answer goes far beyond: they are
EDT0L, which is a proper subclass of indexed languages. We can additionally
handle the existential theory of equations with rational constraints in free
products $\star_{1 \leq i \leq s}F_i$, where each $F_i$ is either a free or
finite group, or a free monoid with involution. In all cases the result is the
same: the set of all solutions in reduced words is EDT0L. This was known only
for quadratic word equations by Fert\'e, Marin and S\'enizergues (ToCS 2014),
which is a very restricted case. Our general result became possible due to the
recent recompression technique of Je\.z. In this paper we use a new method to
integrate solutions of linear Diophantine equations into the process and obtain
more general results than in the related paper (arXiv 1405.5133). For example,
we improve the complexity from quadratic nondeterministic space in (arXiv
1405.5133) to quasi-linear nondeterministic space here. This implies an
improved complexity for deciding the existential theory of non-abelian free
groups: NSPACE($n\log n$). The conjectured complexity is NP, however, we
believe that our results are optimal with respect to space complexity,
independent of the conjectured NP.
