Documentation/internals.yo

   1 article(LilyPond internals)(Han-Wen Nienhuys)()
   2
   3 This documents some aspects of the internals of GNU LilyPond. Some of
   4 this stuff comes from e-mail I wrote, some from e-mail others wrote,
   5 some are large comments taken away from the headers. This page may be
   6 a little incoherent.  Unfortunately, it is also quite outdated.  A
   7 more thorough  and understandable document is in the works.
   8
   9 You should use code(doc++) to take a peek at the sources.
  10
  11
  12 sect(OVERVIEW)
  13
  14 GNU LilyPond is a "multi-pass" system. The different passes have been
  15 created so that they do not depend on each other. In a later stage
  16 some parts may be moved into libraries, or seperate programs, or they
  17 might be integrated in larger systems.
  18
  19 description(
  20
  21 dit(Parsing:)
  22
  23 No difficult algorithms. The .ly file is read, and converted to a list
  24 of code(Scores), which each contain code(Music) and paper/midi-definitions.
  25
  26 dit(Interpreting music)
  27
  28 The music is walked column by column. The iterators which do the
  29 walking report the Request to Translators which use this information
  30 to create elements, either MIDI or "visual" elements. The translators
  31 form a hierarchy; the ones for paper output are Engravers, for MIDI
  32 Performers.
  33
  34 The translators swallow requests, create elements, broadcast them to
  35 other translators on higher or same level  in the hierarchy:
  36
  37 The stem of a voice A is broadcast to the staff which contains A, but
  38 not to the noteheads of A, and not to the stems, beams and noteheads
  39 of a different voice (say B) or a different staff. The stem and
  40 noteheads of A are coupled, because the the Notehead_engraver
  41 broadcasts its heads, and the Stem catches these.
  42
  43 The engraver which agrees to handle a request decides whether to to
  44 honor the request, ignore it, or merge it with other requests. Merging
  45 of requests is preferably done with other requests done by members of
  46 the same voicegroups (beams, brackets, stems). In this way you can put
  47 the voices of 2 instruments in a conductor's score so they make chords
  48 (the Stem_reqs of both instruments will be merged).
  49
  50 dit(Prebreaking)
  51
  52 Breakable stuff (eg. clefs and bars) are copied into pre and
  53 postbreaks.
  54
  55 dit(Preprocessing)
  56
  57 Some dependencies are resolved, such as the direction of stems, beams,
  58 and "horizontal" placement issues (the order of clefs,  keys etc,
  59 placement of chords in multi-voice music),
  60
  61 dit(Break calculation:)
  62
  63 The lines and horizontal positions of the columns are determined.
  64
  65 dit(Breaking)
  66
  67 Through some magical interactions with Line_of_score and Super_elem
  68 (check out the source) the "lines" are produced.
  69
  70 All other spanners can figure across which lines they are spread. If
  71 applicable, they break themselves into pieces. After this, each piece
  72 (or, if there are no pieces, the original spanner itself) throws out
  73 any dependencies which are in the wrong line.
  74
  75 dit(Postprocesing:)
  76
  77 Some items and all spanners need computation after the Paper_column
  78 positions are determined. Examples: slurs, vertical positions of
  79 staffs.
  80
  81 dit(Output paper)
  82
  83 )
  84
  85 sect(mudela)
  86
  87 Most information is stored in the form of a request.  In music
  88 typesetting, the user might want to cram a lot more symbols on the
  89 paper than actually fits. To reflect this idea (the user asks more
  90 than we can do), the container for this data is called Request.
  91
  92 In a lot of other formats this would be called an 'Event'
  93
  94 description(
  95 dit(code(Barcheck_req))
  96     Checks during music processing if start of this voice element
  97     coincides with the start of a measure. Handy to check if you left out
  98     some voice elts.
  99 dit(code(Note_req))
 100     LilyPond has to decide if the ball should be hanging left or
 101     right. This influences the horizontal dimensions of a column, and this
 102     is why request processing should be done before horizontal spacing.
 103     Other voices' frivolities may cause the need for accidentals, so this
 104     is also for the to decide. The engraver can decide on positioning based on
 105     ottava commands and the appropriate clef.
 106 dit(code(Rest_req))
 107     Typeset a rest.
 108 dit(code(Span_req))
 109     This type of request typically results in the creation of a code(Spanner)
 110 dit(code(Beam_req))
 111     Start/stop a beam.
 112     Engraver has to combine this request with the stem_request, since the
 113     number of flags that a stem wants to carry will determine the
 114     number of beams.
 115 dit(code(Dynamic))
 116     Each dynamic is bound to one note (a crescendo spanning multiple
 117     notes is thought to be made of two "dynamics": a start and a stop).
 118     Dynamic changes can occur in a smaller time than the length of its
 119     note, therefore fore each  code(Dynamic) request carries a time, measured
 120     from the start of its note.
 121 )
 122
 123 sect(Request_engraver)
 124
 125 In the previous section the idea of Request has been explained, but
 126 this only solves one half of the problem. The other half is deciding
 127 which requests should be honored, which should merged with other
 128 requests, and which should be ignored. Consider this input
 129
 130 verb(
 131         \type Staff < % chord
 132                 { \meter 2/4; [c8 c8] }
 133                 {\meter 2/4;  [e8 e8] }
 134         >
 135 )
 136
 137 Both the cs and es are part of a staff (they are in the same
 138 Voice_group), so they should share meters, but the two [ ] pairs
 139 should be merged.
 140
 141 The judge in this "allocation" problem a set of brokers: the requests
 142 are transmitted to so-called engravers which respond if they want to
 143 accept a request eg, the code(Notehead_engraver) will accept
 144 code(Note_req)s, and turn down code(Slur_req)s. If the Music_iterator
 145 cannot find a engraver that wants the request, it is junked (with a
 146 warning message).
 147
 148 After all requests have been either assigned, or junked, the Engraver
 149 will process the requests (which usually means creating an code(Item)
 150 or code(Spanner)). If a code(Request_engraver) creates something, it
 151 tells the enclosing context. If all items/spanners have been created,
 152 then each Engraver is notified of any created Score_element, via a
 153 broadcasting system.
 154
 155 nsubsect(example:)
 156
 157 verb(
 158         c4
 159 )
 160
 161 produces:
 162
 163 verb(
 164         Note_request (duration 1/4)
 165         Stem_request (duration 1/4)
 166 )
 167
 168 Note_request will be taken by a code(Notehead_engraver), stem_request
 169 will be taken by a code(Stem_beam_engraver). code(Notehead_engraver)
 170 creates a code(Notehead), code(Stem_beam_engraver) creates a
 171 code(Stem). Both announce this to the Staff_engraver. Staff_engraver
 172 will tell code(Stem_beam_engraver) about the code(Notehead), which
 173 will add the code(Notehead) to the code(Stem) it just created.
 174
 175 To decide on merging, several engravers have been grouped. Please
 176 check file(init/engraver.ly).
 177
 178
 179 sect(ITEMS and SPANNERS)
 180
 181 The symbols that are printed, are generated by items and spanners
 182 (staff-elements). An item has one horizontal position, whereas a
 183 spanner spans several columns.
 184
 185 sect(DEPENDENCIES)
 186
 187 In music symbols depend on each other: the stems of a beam should
 188 point in the same direction as the beam itself, so the stems of a beam
 189 depend on the beam. In the same way do scripts depend on the direction
 190 of the stem. To reflect this, LilyPond has the notion of dependency.
 191 It works in the same fashion that code(make) uses to build programs:
 192 before a stem is calculated, its dependencies (the beam) should be
 193 calculated. Before a slur is calculated, its dependencies (stems,
 194 noteheads) should be calculated.
 195
 196 sect(BREAKING)
 197
 198 So what is this PREBREAK and POSTBREAK stuff?
 199
 200 Let's take text as an example. In German some compound
 201 words change their spelling if they are broken: "backen" becomes
 202 "bak-ken".  TeX has a mechanism to deal with this, you would define
 203 the spelling of "backen" in TeX in this way
 204
 205         \discretionary{bak-}{ken}{backen}
 206
 207 These 3 arguments are called "prebreak", "postbreak" and "nobreak"
 208 text.
 209
 210 The same problem exists when typesetting music. If a line of music is
 211 broken, the next line usually gets a clef. So in TeX terms, the clef
 212 is a postbreak. The same thing happens with meter signs: Normally the
 213 meter follows the bar. If a line is broken at that bar, the bar along
 214 with the meter stays on the "last" line, but the next line also gets a
 215 meter sign after the clef. Using the previous notation,
 216
 217         \discretionary{bar meter}{clef meter}{ bar meter }
 218
 219 In GNU Lilypond, we have the same concepts (and the same
 220 terminology). Each (nonrhythmic) symbol is typeset in  a nonrhythmic column
 221 At a breakpoint, multiple symbols are printed; symbols to be printed
 222 if the line is not broken, symbols to appear on the previous line, and
 223 on the next line if it is broken.
 224
 225 sect(SPACING)
 226
 227
 228 Some terminology: I call a vertical group of symbols (notes) which
 229 start at the same time a "column".  Each line of a score has notes in
 230 it, grouped in columns. The difference in starting time between those
 231 columns makes it possible to determine ideal distances between those
 232 columns.
 233
 234 Example:
 235
 236 verb(
 237         time ----->
 238
 239         cols:   col1    col2    col3    col4
 240
 241
 242         voice1  1               1
 243
 244         voice2  2       2       2       2
 245
 246
 247         (1 is a whole note, 2 a half note.)
 248
 249         time_difference (col1 , col2) = 0.5 wholes,
 250         time_difference (col1 , col3) = 1 wholes,
 251         time_difference (col2 , col3) = 0.5 wholes,
 252         etc.
 253 )
 254
 255 these differences are translated into ideal distances
 256
 257 verb(
 258         distance (col1,col2) = 10 pt
 259         distance (col1,col3) = 14.1 pt
 260         distance (col2,col3) = 10 pt
 261         etc.
 262 )
 263
 264 as you can see, these distance are conflicting. So instead of
 265 satisfying all those ideals simultaneously, a compromise is sought.
 266
 267 This is Columbus' egg: GNU LilyPond attaches "springs" to each
 268 column-pair.  each spring has an equilibrium-position which is equal to
 269 the above mentioned distance, so
 270
 271 spring (col1, col2) and spring (col2,col3) try to push column 1
 272 and 3 away (to a distance of 20pt) from each other, whereas the spring
 273 between col 1 and col 3 tries to pull those two together (to a
 274 distance of 14.1 pt). The net result of this pushing and pulling is an
 275 equilibrium situation (the pushing cancels the pulling), which can be
 276 calculated as the solution of Quadratic program: it is the solution
 277 with minimum potential energy, for you physicists out there.
 278
 279 This algorithm for doing one line, gives a "badness" parameter for
 280 each line (the potential energy). Now one can use TeX's algorithm for
 281 making paragraphs (using this new version of "badness"): one should
 282 try to minimise the overall badness of a paragraph. GNU LilyPond also
 283 uses the concept of pre- and post-breaks.
 284
 285 (actually, it is a bit more complicated: each column also has a
 286 minimum distance to other columns, to prevent symbols from running
 287 into symbols of other columns.)
 288