3 LilyGuts - doco to the internals of GNU LilyPond
7 This page documents some aspects of the internals of GNU LilyPond. Some of
8 this stuff comes from e-mail I wrote, some from e-mail others wrote,
9 some are large comments taken away from the headers
11 You should use doc++ to take a peek at the sources.
13 This should become a Hacking-HOWTO. If you find any confusing stuff
14 here, let me know. I am a hacker, and don't spend enough time doccing
15 what I write. (Most stuff here which refers to the code is slightly outdated)
17 If you finally have mastered some internal piece of lily, your
18 explanation could be added here.
22 GNU LilyPond is a "multi-pass" system. The different passes have been
23 created so that they do not depend on each other. In a later stage
24 some parts may be moved into libraries, or seperate programs, or they
25 might be integrated in larger systems.
31 No difficult algorithms. Associated datastructures have prefix Input
32 (eg Input_score, Input_command). The .ly file is read, and converted
35 =item Creating elements
37 Requests are processed and used to create elements (like balls, stems,
38 slurs etc). This is done by a hierarchy of "brokers" (called
39 Translators: the ones for paper output are Engravers, for MIDI
40 Performers), which swallow requests, broadcast them and couple
43 In this step data-structures for the next steps are created and filled
44 with data: Score_elements, PScore, PCol.
48 Breakable stuff (eg. clefs and bars) are copied into pre and postbreaks.
52 Some dependencies are resolved, such as the direction of stems, beams,
54 =item Break calculation:
56 The lines and horizontal positions of the columns are determined
61 Through some magical interactions with Line_of_score and Super_elem
62 (check out the source) the "lines" are produced.
64 All other spanners can figure across which lines they are spread. If
65 applicable, they break themselves into pieces. After this, each piece
66 works (or, if there are no pieces) the spanner throws out any
67 dependencies which are in the wrong line.
71 Some items and all spanners need computation after the PCol positions
79 The music is run through a translator (called Performer) which
80 creates midi-items from the requests.
86 This chapter deals with the internals of Mudela.
90 As you can see, most information is stored in the form of a request.
91 In music typesetting, the user might want to cram a lot more symbols
92 on the paper than actually fits. To reflect this idea (the user asks
93 more than we can do), the container for this data is called Request.
95 The music (requests) are read/interpreted by a set of objects
96 (translators), the Performers/Engravers. The engraver which agrees to
97 handle a request decides whether to to honor the request, ignore it,
98 or merge it with other requests. Merging of requests is preferably
99 done with other requests done by members of the same voicegroups
100 (beams, brackets, stems).
102 The result of a request will be an C<Item> or a C<Spanner>, which
103 will be put on the score.
105 Different staffs can produce different outputs; a melodious voice
106 which is put into a percussion-Staff, will be typeset as the rythm of
109 After C<Staff> made up her mind, the resultant items and
110 spanners are put on the PScore.
112 Some of the important requests are:
116 =item C<Barcheck_req>
118 Checks during music processing if start of this voice element
119 coincides with the start of a measure. Handy to check if you left out
124 LilyPond has to decide if the ball should be hanging left or
125 right. This influences the horizontal dimensions of a column, and this
126 is why request processing should be done before horizontal spacing.
128 Other voices' frivolities may cause the need for accidentals, so this
129 is also for the to decide. The engraver can decide on positioning based on
130 ottava commands and the appropriate clef.
138 This type of request typically results in the creation of a C<Spanner>
144 Engraver has to combine this request with the stem_request, since the
145 number of flags that a stem wants to carry will determine the
150 Each dynamic is bound to one note (a crescendo spanning multiple
151 notes is thought to be made of two "dynamics": a start and a stop).
152 Dynamic changes can occur in a smaller time than the length of its
153 note, therefore fore each C<Dynamic> request carries a time, measured
154 from the start of its note.
158 Voice group is a (time-dependent) collection of voices which share
159 some characteristics (slurs, stems) at some time.
161 =head1 Request_engraver
163 In the previous section the idea of Request has been explained, but
164 this only solves one half of the problem. The other half is
165 deciding which requests should be honored, which should merged with
166 other requests, and which should be ignored. Consider this (pseudo)input
173 Both the c and e are part of a chord (they are in the same
174 Voice_group), so they should share the beams, and the two [ ] pairs
175 should be merged. The slurs OTOH are specific for each voice, so they
176 should not be shared.
178 The judge in this "allocation" problem a set of broker. It uses the
179 C<Request_engraver> to do most of the work. For each request
180 C<Complex_staff> queries so-called C<Request_engraver>s if they want
181 to accept a request eg, the C<Notehead_engraver> will accept
182 C<Note_req>s, and turn down C<Slur_req>s. If the Music_iterator
183 cannot find a engraver that wants the request, it is junked (with a
186 After all requests have been either assigned, or junked, the Engraver
187 will process the requests (which usually means creating an C<Item> or
188 C<Spanner>). If a C<Request_engraver> creates something, it tells
189 If all requests have been processed, then each Engraver is notified
190 of any created Score_element, via a broadcasting system.
198 note_request (duration 1/4)
199 stem_request (duration 1/4)
201 note_request will be taken by a C<Notehead_engraver>, stem_request
202 will be taken by a C<Stem_beam_engraver>. C<Notehead_engraver> creates
203 a C<Notehead>, C<Stem_beam_engraver> creates a C<Stem>. Both announce
204 this to the Staff_engraver. Staff_engraver will tell
205 C<Stem_beam_engraver> about the C<Notehead>, which will add the
206 C<Notehead> to the C<Stem> it just created.
208 To decide on merging, C<Complex_staff> has grouped several
209 engravers. Please check F<init/engraver.ly>.
212 =head1 ITEMS and SPANNERS
214 The symbols that are printed, are generated by items and spanners
215 (staff-elements). An item has one horizontal position, whereas a
216 spanner spans several columns.
220 In music symbols depend on each other: the stems of a beam should
221 point in the same direction as the beam itself, so the stems of a beam
222 depend on the beam. In the same way do scripts depend on the direction
223 of the stem. To reflect this, LilyPond has the notion of dependency.
224 It works in the same fashion that C<make> uses to build programs: before
225 a stem is calculated, its dependencies (the beam) should be
226 calculated. Before a slur is calculated, its dependencies (stems, noteheads)
227 should be calculated.
231 So what's the deal with PREBREAK and POSTBREAK and all this
234 Let's take text as an example. In German some compound
235 words change their spelling if they are broken: "backen" becomes
236 "bak-ken". TeX has a mechanism to deal with this, you would define
237 the spelling of "backen" in TeX in this way
239 \discretionary{bak-}{ken}{backen}
241 These 3 arguments are called "prebreak", "postbreak" and "nobreak"
244 The same problem exists when typesetting music. If a line of music is
245 broken, the next line usually gets a clef. So in TeX terms, the clef
246 is a postbreak. The same thing happens with meter signs: Normally the
247 meter follows the bar. If a line is broken at that bar, the bar along
248 with the meter stays on the "last" line, but the next line also gets a
249 meter sign after the clef. Using the previous notation,
251 \discretionary{bar meter}{clef meter}{ bar meter }
253 In GNU Lilypond, we have the same concepts (and the same
254 terminology). Each (nonrhythmic) symbol is typeset in a nonrhythmic column
255 At a breakpoint, multiple symbols are printed; symbols to be printed
256 if the line is not broken, symbols to appear on the previous line, and
257 on the next line if it is broken.
261 I think my method is the most elegant algorithm i've seen so far.
262 Some terminology: I call a vertical group of symbols (notes) which
263 start at the same time a "column". Each line of a score has notes in
264 it, grouped in columns. The difference in starting time between those
265 columns makes it possible to determine ideal distances between those
280 (1 is a whole note, 2 a half note.)
282 time_difference (col1 , col2) = 0.5 wholes,
283 time_difference (col1 , col3) = 1 wholes,
284 time_difference (col2 , col3) = 0.5 wholes,
287 these differences are translated into ideal distances (these translations
288 have been the subject of discussion in this thread).
290 distance (col1,col2) = 10 pt
291 distance (col1,col3) = 14.1 pt
292 distance (col2,col3) = 10 pt
295 as you can see, these distance are conflicting. So instead of
296 satisfying all those ideals simultaneously, a compromise is sought.
298 This is Columbus' egg: GNU LilyPond attaches "springs" to each
299 column-pair. each spring has an equilibrium-position which is equal to
300 the above mentioned distance, so
302 spring (col1, col2) and spring (col2,col3) try to push column 1
303 and 3 away (to a distance of 20pt) from each other, whereas the spring
304 between col 1 and col 3 tries to pull those two together (to a
305 distance of 14.1 pt). The net result of this pushing and pulling is an
306 equilibrium situation (the pushing cancels the pulling), which can be
307 calculated as the solution of Quadratic program: it is the solution
308 with minimum potential energy, for you physicists out there.
310 This algorithm for doing one line, gives a "badness" parameter for
311 each line (the potential energy). Now one can use TeX's algorithm for
312 making paragraphs (using this new version of "badness"): one should
313 try to minimise the overall badness of a paragraph. GNU LilyPond also
314 uses the concept of pre- and post-breaks.
316 (actually, it is a bit more complicated: each column also has a
317 minimum distance to other columns, to prevent symbols from running
318 into symbols of other columns.)
324 This of course does not solve the problem of generating the
325 springs. This is an area that needs a lot of work, and the optimal
326 solution to find is not of a mathematical nature.
328 Gourlay's solution is used.