Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. This turns out to be a little bit less trivial than it sounds but has been worked on (see here and here) and very nice interfaces exist. When formatting text there's a classic dynamic programming algorithm for getting the trailing space to be as uniform as possible.
Real world code formatting can be much more complex however because of alignment (and additionally you might want this with the & operand in LaTeX). For instance see this code
data UserT f = User
{ _userId :: Columnar f Int64
, _userName :: Columnar f Text
, _userEmail :: Columnar f Text
, _userAge :: Columnar f Int
, _userOccupation :: Columnar f Text
} deriving (Generic)
You can see that the double colons are aligned in it (as well as the left side but you can chock that up to indentation). So the goal is to put as much on one line as possible while preserving the alignment constraints. In the terminology of the pretty printing papers its as if we need a new notion of an alignment point and the goal is to find the best layout that preserves the alignment constraints.
Do any algorithms or papers exist that explain how to solve this optimization problem? What makes this particularly difficult is that you may have to insert a lot of space on an earlier line in order to satisfy a later line's constraints so it isn't sufficient to just use back-tracking (and hope for an ok running time), additionally the dependence graph may be very large. I'm far more interested in the code formatting case but I figure there's also a tie in to LaTeX here since LaTeX has the &/&& formatting in its align blocks.
