LilyPond internals

Han-Wen Nienhuys

Table of Contents

1: OVERVIEW

2: mudela

3: Request_engraver

4: ITEMS and SPANNERS

5: DEPENDENCIES

6: BREAKING

7: SPACING



This documents some aspects of the internals of GNU LilyPond. Some of this stuff comes from e-mail I wrote, some from e-mail others wrote, some are large comments taken away from the headers. This page may be a little incoherent. Unfortunately, it is also quite outdated. A more thorough and understandable document is in the works.

You should use doc++ to take a peek at the sources.

1: OVERVIEW

GNU LilyPond is a "multi-pass" system. The different passes have been created so that they do not depend on each other. In a later stage some parts may be moved into libraries, or seperate programs, or they might be integrated in larger systems.

Parsing:

No difficult algorithms. The .ly file is read, and converted to a list of Scores, which each contain Music and paper/midi-definitions.

Interpreting music

The music is walked through in time-order. The iterators which do the walking report Music to Translators which use this information to create elements, either MIDI or "visual" elements. The translators form a hierarchy; the ones for paper output are Engravers, for MIDI Performers.

The translators swallow Music (mostly atomic gobs called Requests), create elements, broadcast them to other translators on higher or same level in the hierarchy:

The stem of a voice A is broadcast to the staff which contains A, but not to the stems, beams and noteheads of a different voice (say B) or a different staff. The stem and noteheads of A are coupled, because the the Note_heads_engraver broadcasts its heads, and the Stem_engraver catches these.

The engraver which agrees to handle a request decides whether to to honor the request, ignore it, or merge it with other requests. Merging of requests is preferably done with other requests done by members of the same voicegroups (beams, brackets, stems). In this way you can put the voices of 2 instruments in a conductor's score so they make chords (the Beam requests of both instruments will be merged).

Prebreaking

Breakable stuff (eg. clefs and bars) are copied into pre and postbreaks.

Preprocessing

Some dependencies are resolved, such as the direction of stems, beams, and "horizontal" placement issues (the order of clefs, keys etc, placement of chords in multi-voice music),

Break calculation:

The lines and horizontal positions of the columns are determined.

Breaking

Through some magical interactions with Line_of_score and Super_elem (check out the source) the "lines" are produced.

All other spanners can figure across which lines they are spread. If applicable, they break themselves into pieces. After this, each piece (or, if there are no pieces, the original spanner itself) throws out any dependencies which are in the wrong line.

Postprocesing:

Some items and all spanners need computation after the Paper_column positions are determined. Examples: slurs, vertical positions of staffs.

Output paper

2: mudela

Most information is stored in the form of a request. In music typesetting, the user might want to cram a lot more symbols on the paper than actually fits. To reflect this idea (the user asks more than we can do), the container for this data is called Request.

In a lot of other formats this would be called an 'Event'

Barcheck_req
Checks during music processing if start of this voice element coincides with the start of a measure. Handy to check if you left out some voice elts.

Note_req
LilyPond has to decide if the ball should be hanging left or right. This influences the horizontal dimensions of a column, and this is why request processing should be done before horizontal spacing. Other voices' frivolities may cause the need for accidentals, so this is also for the to decide. The engraver can decide on positioning based on ottava commands and the appropriate clef.

Rest_req
Typeset a rest.

Span_req
This type of request typically results in the creation of a Spanner

Beam_req
Start/stop a beam. Engraver has to combine this request with the stem_request, since the number of flags that a stem wants to carry will determine the number of beams.

Dynamic
Each dynamic is bound to one note (a crescendo spanning multiple notes is thought to be made of two "dynamics": a start and a stop). Dynamic changes can occur in a smaller time than the length of its note, therefore fore each Dynamic request carries a time, measured from the start of its note.

3: Request_engraver

In the previous section the idea of Request has been explained, but this only solves one half of the problem. The other half is deciding which requests should be honored, which should merged with other requests, and which should be ignored. Consider this input


	\type Staff < % chord
		{ \meter 2/4; [c8 c8] }
		{\meter 2/4;  [e8 e8] }
	>

Both the cs and es are part of a staff (they are in the same Voice_group), so they should share meters, but the two [ ] pairs should be merged.

The judge in this "allocation" problem a set of brokers: the requests are transmitted to so-called engravers which respond if they want to accept a request eg, the Notehead_engraver will accept Note_reqs, and turn down Slur_reqs. If the Music_iterator cannot find a engraver that wants the request, it is junked (with a warning message).

After all requests have been either assigned, or junked, the Engraver will process the requests (which usually means creating an Item or Spanner). If a Request_engraver creates something, it tells the enclosing context. If all items/spanners have been created, then each Engraver is notified of any created Score_element, via a broadcasting system.

example:


	c4

produces:


	Note_request (duration 1/4)
	Stem_request (duration 1/4)

Note_request will be taken by a Notehead_engraver, stem_request will be taken by a Stem_beam_engraver. Notehead_engraver creates a Notehead, Stem_beam_engraver creates a Stem. Both announce this to the Staff_engraver. Staff_engraver will tell Stem_beam_engraver about the Notehead, which will add the Notehead to the Stem it just created.

To decide on merging, several engravers have been grouped. Please check init/engraver.ly.

4: ITEMS and SPANNERS

The symbols that are printed, are generated by items and spanners (staff-elements). An item has one horizontal position, whereas a spanner spans several columns.

5: DEPENDENCIES

In music symbols depend on each other: the stems of a beam should point in the same direction as the beam itself, so the stems of a beam depend on the beam. In the same way do scripts depend on the direction of the stem. To reflect this, LilyPond has the notion of dependency. It works in the same fashion that make uses to build programs: before a stem is calculated, its dependencies (the beam) should be calculated. Before a slur is calculated, its dependencies (stems, noteheads) should be calculated.

6: BREAKING

So what is this PREBREAK and POSTBREAK stuff?

Let's take text as an example. In German some compound words change their spelling if they are broken: "backen" becomes "bak-ken". TeX has a mechanism to deal with this, you would define the spelling of "backen" in TeX in this way

\discretionary{bak-}{ken}{backen}

These 3 arguments are called "prebreak", "postbreak" and "nobreak" text.

The same problem exists when typesetting music. If a line of music is broken, the next line usually gets a clef. So in TeX terms, the clef is a postbreak. The same thing happens with meter signs: Normally the meter follows the bar. If a line is broken at that bar, the bar along with the meter stays on the "last" line, but the next line also gets a meter sign after the clef. Using the previous notation,

\discretionary{bar meter}{clef meter}{ bar meter }

In GNU Lilypond, we have the same concepts (and the same terminology). Each (nonrhythmic) symbol is typeset in a nonrhythmic column At a breakpoint, multiple symbols are printed; symbols to be printed if the line is not broken, symbols to appear on the previous line, and on the next line if it is broken.

7: SPACING

Some terminology: I call a vertical group of symbols (notes) which start at the same time a "column". Each line of a score has notes in it, grouped in columns. The difference in starting time between those columns makes it possible to determine ideal distances between those columns.

Example:


	time ----->

	cols:   col1    col2    col3    col4


	voice1  1               1

	voice2  2       2       2       2


	(1 is a whole note, 2 a half note.)

	time_difference (col1 , col2) = 0.5 wholes,
	time_difference (col1 , col3) = 1 wholes,
	time_difference (col2 , col3) = 0.5 wholes,
	etc.

these differences are translated into ideal distances


        distance (col1,col2) = 10 pt
        distance (col1,col3) = 14.1 pt
        distance (col2,col3) = 10 pt
        etc.

as you can see, these distance are conflicting. So instead of satisfying all those ideals simultaneously, a compromise is sought.

This is Columbus' egg: GNU LilyPond attaches "springs" to each column-pair. each spring has an equilibrium-position which is equal to the above mentioned distance, so

spring (col1, col2) and spring (col2,col3) try to push column 1 and 3 away (to a distance of 20pt) from each other, whereas the spring between col 1 and col 3 tries to pull those two together (to a distance of 14.1 pt). The net result of this pushing and pulling is an equilibrium situation (the pushing cancels the pulling), which can be calculated as the solution of Quadratic program: it is the solution with minimum potential energy, for you physicists out there.

This algorithm for doing one line, gives a "badness" parameter for each line (the potential energy). Now one can use TeX's algorithm for making paragraphs (using this new version of "badness"): one should try to minimise the overall badness of a paragraph. GNU LilyPond also uses the concept of pre- and post-breaks.

(actually, it is a bit more complicated: each column also has a minimum distance to other columns, to prevent symbols from running into symbols of other columns.)


Return to GNU LilyPond's home page.

Please send GNU LilyPond questions and comments to gnu-music-discuss@gnu.org.

Please send comments on these web pages to (address unknown), send other FSF & GNU inquiries and questions to gnu@gnu.org.

Copyright (c) 1997, 1998, 1999 Han-Wen Nienhuys and Jan Nieuwenhuizen.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.


This page was built from GNU LilyPond-1.1.57 by

root <(address unknown)>, at Tue Jul 13 11:31:20 1999 CDT.