  Fix (not necessarily distinct) objects $i$ and $j$ of a locally small
category $S$, and write $S_{ij}$ for the set of all morphisms $i\to j$. Fix a
morphism $a\in S_{ji}$, and define an operation $\star_a$ on $S_{ij}$ by
$x\star_ay=xay$ for all $x,y\in S_{ij}$. Then $(S_{ij},\star_a)$ is a
semigroup, known as a sandwich semigroup, and denoted by $S_{ij}^a$. This
article develops a general theory of sandwich semigroups in locally small
categories. We begin with structural issues such as regularity, Green's
relations and stability, focusing on the relationships between these properties
on $S_{ij}^a$ and the whole category $S$. We then identify a natural condition
on $a$, called sandwich regularity, under which the set Reg$(S_{ij}^a)$ of all
regular elements of $S_{ij}^a$ is a subsemigroup of $S_{ij}^a$. Under this
condition, we carefully analyse the structure of the semigroup Reg$(S_{ij}^a)$,
relating it via pullback products to certain regular subsemigroups of $S_{ii}$
and $S_{jj}$, and to a certain regular sandwich monoid defined on a subset of
$S_{ji}$; among other things, this allows us to also describe the
idempotent-generated subsemigroup $\mathbb E(S_{ij}^a)$ of $S_{ij}^a$. We also
study combinatorial invariants such as the rank (minimal size of a generating
set) of the semigroups $S_{ij}^a$, Reg$(S_{ij}^a)$ and $\mathbb E(S_{ij}^a)$;
we give lower bounds for these ranks, and in the case of Reg$(S_{ij}^a)$ and
$\mathbb E(S_{ij}^a)$ show that the bounds are sharp under a certain condition
we call MI-domination. Applications to concrete categories of transformations
and partial transformations are given in Part II.
