2 spacing-spanner.cc -- implement Spacing_spanner
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
15 #include "output-def.hh"
16 #include "paper-score.hh"
17 #include "paper-column.hh"
19 #include "note-spacing.hh"
22 #include "staff-spacing.hh"
24 #include "paper-column.hh"
25 #include "spaceable-grob.hh"
26 #include "break-align-interface.hh"
27 #include "spacing-interface.hh"
30 TODO: this file/class is too complex. Should figure out how to chop
37 static void standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
38 Real *fixed, Real *space, Moment);
40 static Real default_bar_spacing (Grob *, Grob *, Grob *, Moment);
41 static Real note_spacing (Grob *, Grob *, Grob *, Moment, bool *);
42 static Real get_duration_space (Grob *, Moment dur, Rational shortest, bool *);
43 static Rational find_shortest (Grob *, Link_array<Grob> const &);
44 static void breakable_column_spacing (Grob *, Item *l, Item *r, Moment);
45 static void find_loose_columns () {}
46 static void prune_loose_columns (Grob *, Link_array<Grob> *cols, Rational);
47 static void find_loose_columns (Link_array<Grob> cols);
48 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
49 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
50 static void do_measure (Rational, Grob *me, Link_array<Grob> *cols);
51 static void musical_column_spacing (Grob *, Item *, Item *, Real, Rational);
52 DECLARE_SCHEME_CALLBACK (set_springs, (SCM));
53 static bool has_interface (Grob *);
57 Return whether COL is fixed to its neighbors by some kind of spacing
61 If in doubt, then we're not loose; the spacing engine should space
62 for it, risking suboptimal spacing.
64 (Otherwise, we might risk core dumps, and other weird stuff.)
67 loose_column (Grob *l, Grob *c, Grob *r)
69 SCM rns = c->get_property ("right-neighbors");
70 SCM lns = c->get_property ("left-neighbors");
73 If this column doesn't have a proper neighbor, we should really
74 make it loose, but spacing it correctly is more than we can
77 (this happens in the following situation:
88 the column containing the clef is really loose, and should be
89 attached right to the first column, but that is a lot of work for
90 such a borderline case.)
93 if (!scm_is_pair (lns) || !scm_is_pair (rns))
96 Item *l_neighbor = dynamic_cast<Item *> (unsmob_grob (scm_car (lns)));
97 Item *r_neighbor = dynamic_cast<Item *> (unsmob_grob (scm_car (rns)));
99 if (!l_neighbor || !r_neighbor)
102 l_neighbor = l_neighbor->get_column ();
103 r_neighbor = dynamic_cast<Item *> (Note_spacing::right_column (r_neighbor));
105 if (l == l_neighbor && r == r_neighbor)
108 if (!l_neighbor || !r_neighbor)
112 Only declare loose if the bounds make a little sense. This means
113 some cases (two isolated, consecutive clef changes) won't be
114 nicely folded, but hey, then don't do that.
116 if (! ((Paper_column::is_musical (l_neighbor) || Item::is_breakable (l_neighbor))
117 && (Paper_column::is_musical (r_neighbor) || Item::is_breakable (r_neighbor))))
123 A rather hairy check, but we really only want to move around clefs. (anything else?)
125 in any case, we don't want to move bar lines.
127 for (SCM e = c->get_property ("elements"); scm_is_pair (e); e = scm_cdr (e))
129 Grob *g = unsmob_grob (scm_car (e));
130 if (g && Break_align_interface::has_interface (g))
132 for (SCM s = g->get_property ("elements"); scm_is_pair (s);
135 Grob *h = unsmob_grob (scm_car (s));
138 ugh. -- fix staff-bar name?
140 if (h && h->get_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
150 Remove columns that are not tightly fitting from COLS. In the
151 removed columns, set 'between-cols to the columns where it is in
155 Spacing_spanner::prune_loose_columns (Grob *me, Link_array<Grob> *cols, Rational shortest)
157 Link_array<Grob> newcols;
158 Real increment = robust_scm2double (me->get_property ("spacing-increment"), 1.2);
159 for (int i = 0; i < cols->size (); i++)
161 if (Item::is_breakable (cols->elem (i)) || Paper_column::is_musical (cols->elem (i)))
163 newcols.push (cols->elem (i));
167 Grob *c = cols->elem (i);
168 if (loose_column (cols->elem (i - 1), c, cols->elem (i + 1)))
170 SCM lns = c->get_property ("left-neighbors");
171 lns = scm_is_pair (lns) ? scm_car (lns) : SCM_BOOL_F;
173 SCM rns = c->get_property ("right-neighbors");
174 rns = scm_is_pair (rns) ? scm_car (rns) : SCM_BOOL_F;
177 Either object can be non existent, if the score ends
180 rns = scm_car (unsmob_grob (rns)->get_property ("right-items"));
181 c->set_property ("between-cols", scm_cons (lns,
185 Set distance constraints for loose columns
187 Drul_array<Grob *> next_door;
188 next_door[LEFT] = cols->elem (i - 1);
189 next_door[RIGHT] = cols->elem (i + 1);
191 Drul_array<Real> dists (0, 0);
196 Item *lc = dynamic_cast<Item *> ((d == LEFT) ? next_door[LEFT] : c);
197 Item *rc = dynamic_cast<Item *> (d == LEFT ? c : next_door[RIGHT]);
199 for (SCM s = lc->get_property ("spacing-wishes");
200 scm_is_pair (s); s = scm_cdr (s))
202 Grob *sp = unsmob_grob (scm_car (s));
203 if (Note_spacing::left_column (sp) != lc
204 || Note_spacing::right_column (sp) != rc)
214 The note spacing should be taken from the musical
218 Real base = note_spacing (me, lc, rc, shortest, &dummy);
219 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
223 dists[d] = dists[d] >? space;
227 Real space, fixed_space;
228 Staff_spacing::get_spacing_params (sp,
229 &space, &fixed_space);
231 dists[d] = dists[d] >? fixed_space;
235 while (flip (&d) != LEFT);
238 r.distance_ = dists[LEFT] + dists[RIGHT];
239 r.item_drul_[LEFT] = dynamic_cast<Item *> (cols->elem (i - 1));
240 r.item_drul_[RIGHT] = dynamic_cast<Item *> (cols->elem (i + 1));
254 Set neighboring columns determined by the spacing-wishes grob property.
257 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
259 for (int i = 0; i < cols.size (); i++)
261 SCM right_neighbors = SCM_EOL;
262 int min_rank = 100000; // inf.
265 SCM wishes = cols[i]->get_property ("spacing-wishes");
266 for (SCM s = wishes; scm_is_pair (s); s = scm_cdr (s))
268 Item *wish = dynamic_cast<Item *> (unsmob_grob (scm_car (s)));
270 Item *lc = wish->get_column ();
271 Grob *right = Note_spacing::right_column (wish);
276 Item *rc = dynamic_cast<Item *> (right);
278 int right_rank = Paper_column::get_rank (rc);
279 int left_rank = Paper_column::get_rank (lc);
282 update the left column.
284 if (right_rank <= min_rank)
286 if (right_rank < min_rank)
287 right_neighbors = SCM_EOL;
289 min_rank = right_rank;
290 right_neighbors = scm_cons (wish->self_scm (), right_neighbors);
294 update the right column of the wish.
297 SCM left_neighs = rc->get_property ("left-neighbors");
298 if (scm_is_pair (left_neighs)
299 && unsmob_grob (scm_car (left_neighs)))
301 Item *it = dynamic_cast<Item *> (unsmob_grob (scm_car (left_neighs)));
302 maxrank = Paper_column::get_rank (it->get_column ());
305 if (left_rank >= maxrank)
307 if (left_rank > maxrank)
308 left_neighs = SCM_EOL;
310 left_neighs = scm_cons (wish->self_scm (), left_neighs);
311 rc->set_property ("left-neighbors", right_neighbors);
315 if (scm_is_pair (right_neighbors))
317 cols[i]->set_property ("right-neighbors", right_neighbors);
323 Set neighboring columns that have no left/right-neighbor set
324 yet. Only do breakable non-musical columns, and musical columns.
327 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
329 for (int i = 0; i < cols.size (); i++)
331 Item *it = dynamic_cast<Item *> (cols[i]);
332 if (!Item::is_breakable (it) && !Paper_column::is_musical (it))
335 // it->breakable || it->musical
338 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
340 SCM ln = cols[i]->get_property ("left-neighbors");
341 if (!scm_is_pair (ln) && i)
343 cols[i]->set_property ("left-neighbors", scm_cons (cols[i - 1]->self_scm (), SCM_EOL));
346 SCM rn = cols[i]->get_property ("right-neighbors");
347 if (!scm_is_pair (rn) && i < cols.size () - 1)
349 cols[i]->set_property ("right-neighbors", scm_cons (cols[i + 1]->self_scm (), SCM_EOL));
354 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
356 Spacing_spanner::set_springs (SCM smob)
358 Grob *me = unsmob_grob (smob);
361 can't use get_system() ? --hwn.
363 Link_array<Grob> all (me->pscore_->system_->columns ());
365 set_explicit_neighbor_columns (all);
367 SCM preset_shortest = me->get_property ("common-shortest-duration");
368 Rational global_shortest;
369 if (unsmob_moment (preset_shortest))
371 global_shortest = unsmob_moment (preset_shortest)->main_part_;
375 global_shortest = find_shortest (me, all);
376 if (be_verbose_global)
377 progress_indication (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
379 prune_loose_columns (me, &all, global_shortest);
380 set_implicit_neighbor_columns (all);
383 for (int i = 1; i < all.size (); i++)
386 if (Item::is_breakable (sc))
388 Link_array<Grob> measure (all.slice (j, i + 1));
389 do_measure (global_shortest, me, &measure);
394 return SCM_UNSPECIFIED;
398 We want the shortest note that is also "common" in the piece, so we
399 find the shortest in each measure, and take the most frequently
402 This probably gives weird effects with modern music, where every
403 note has a different duration, but hey, don't write that kind of
407 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
410 ascending in duration
412 Array<Rational> durations;
415 Rational shortest_in_measure;
416 shortest_in_measure.set_infinite (1);
418 for (int i = 0; i < cols.size (); i++)
420 if (Paper_column::is_musical (cols[i]))
422 Moment *when = unsmob_moment (cols[i]->get_property ("when"));
425 ignore grace notes for shortest notes.
427 if (when && when->grace_part_)
430 SCM st = cols[i]->get_property ("shortest-starter-duration");
431 Moment this_shortest = *unsmob_moment (st);
432 assert (this_shortest.to_bool ());
433 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
435 else if (!shortest_in_measure.is_infinity ()
436 && Item::is_breakable (cols[i]))
439 for (; j < durations.size (); j++)
441 if (durations[j] > shortest_in_measure)
443 counts.insert (1, j);
444 durations.insert (shortest_in_measure, j);
447 else if (durations[j] == shortest_in_measure)
454 if (durations.size () == j)
456 durations.push (shortest_in_measure);
460 shortest_in_measure.set_infinite (1);
466 for (int i = durations.size (); i--;)
468 if (counts[i] >= max_count)
471 max_count = counts[i];
474 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
477 SCM bsd = me->get_property ("base-shortest-duration");
478 Rational d = Rational (1, 8);
479 if (Moment *m = unsmob_moment (bsd))
483 d = d <? durations[max_idx];
489 Generate spacing for a single measure. We used to have code that did
490 per-measure spacing. Now we have piecewise spacing. We should fix
491 this to support "spacing-regions": some regions have different notes
492 (different time sigs) than others, and should be spaced differently.
495 Spacing_spanner::do_measure (Rational global_shortest, Grob *me,
496 Link_array<Grob> *cols)
499 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
500 for (int i = 0; i < cols->size () - 1; i++)
502 Item *l = dynamic_cast<Item *> (cols->elem (i));
503 Item *r = dynamic_cast<Item *> (cols->elem (i + 1));
505 Paper_column *lc = dynamic_cast<Paper_column *> (l);
506 Paper_column *rc = dynamic_cast<Paper_column *> (r);
508 if (!Paper_column::is_musical (l))
510 breakable_column_spacing (me, l, r, global_shortest);
513 The case that the right part is broken as well is rather
514 rare, but it is possible, eg. with a single empty measure,
515 or if one staff finishes a tad earlier than the rest.
518 Item *lb = l->find_prebroken_piece (RIGHT);
519 Item *rb = r->find_prebroken_piece (LEFT);
522 breakable_column_spacing (me, lb, r, global_shortest);
525 breakable_column_spacing (me, l, rb, global_shortest);
527 breakable_column_spacing (me, lb, rb, global_shortest);
531 musical_column_spacing (me, lc, rc, headwid, global_shortest);
532 if (Item *rb = r->find_prebroken_piece (LEFT))
533 musical_column_spacing (me, lc, rb, headwid, global_shortest);
539 Generate the space between two musical columns LC and RC, given
540 spacing parameters INCR and SHORTEST.
543 Spacing_spanner::musical_column_spacing (Grob *me, Item *lc, Item *rc, Real increment, Rational global_shortest)
545 bool expand_only = false;
546 Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
548 Real compound_note_space = 0.0;
549 Real compound_fixed_note_space = 0.0;
552 SCM seq = lc->get_property ("right-neighbors");
555 We adjust the space following a note only if the next note
556 happens after the current note (this is set in the grob
557 property SPACING-SEQUENCE.
559 for (SCM s = seq; scm_is_pair (s); s = scm_cdr (s))
561 Grob *wish = unsmob_grob (scm_car (s));
563 Item *wish_rcol = Note_spacing::right_column (wish);
564 if (Note_spacing::left_column (wish) != lc
565 || (wish_rcol != rc && wish_rcol != rc->original_))
569 This is probably a waste of time in the case of polyphonic
571 if (Note_spacing::has_interface (wish))
576 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
578 compound_note_space = compound_note_space + space;
579 compound_fixed_note_space = compound_fixed_note_space + fixed;
584 if (Paper_column::when_mom (rc).grace_part_
585 && !Paper_column::when_mom (lc).grace_part_)
588 Ugh. 0.8 is arbitrary.
590 compound_note_space *= 0.8;
593 if (compound_note_space < 0 || wish_count == 0)
595 compound_note_space = base_note_space;
596 compound_fixed_note_space = increment;
600 compound_note_space /= wish_count;
601 compound_fixed_note_space /= wish_count;
605 Whatever we do, the fixed space is smaller than the real
608 TODO: this criterion is discontinuous in the derivative.
609 Maybe it should be continuous?
611 compound_fixed_note_space = compound_fixed_note_space <? compound_note_space;
613 bool packed = to_boolean (me->get_layout ()->c_variable ("packed"));
614 Real strength, distance;
617 TODO: make sure that the space doesn't exceed the right margin.
622 In packed mode, pack notes as tight as possible. This makes
623 sense mostly in combination with raggedright mode: the notes
624 are then printed at minimum distance. This is mostly useful
625 for ancient notation, but may also be useful for some flavours
626 of contemporary music. If not in raggedright mode, lily will
627 pack as much bars of music as possible into a line, but the
628 line will then be stretched to fill the whole linewidth.
631 distance = compound_fixed_note_space;
635 strength = 1 / (compound_note_space - compound_fixed_note_space);
636 distance = compound_note_space;
639 Spaceable_grob::add_spring (lc, rc, distance, strength);
643 The one-size-fits all spacing. It doesn't take into account
644 different spacing wishes from one to the next column.
647 Spacing_spanner::standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
648 Real *fixed, Real *space,
653 Drul_array<Item *> cols (l, r);
657 if (!Paper_column::is_musical (cols[d]))
660 Tied accidentals over barlines cause problems, so lets see
661 what happens if we do this for non musical columns only.
663 Interval lext = cols[d]->extent (cols [d], X_AXIS);
664 if (!lext.is_empty ())
665 *fixed += -d * lext[-d];
668 while (flip (&d) != LEFT);
670 if (l->is_breakable (l) && r->is_breakable (r))
672 Moment *dt = unsmob_moment (l->get_property ("measure-length"));
677 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
679 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
683 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
685 if (dt == Moment (0, 0))
688 In this case, Staff_spacing should handle the job,
689 using dt when it is 0 is silly.
691 *space = *fixed + 0.5;
696 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
702 Read hints from L and generate springs.
705 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r, Moment shortest)
707 Real compound_fixed = 0.0;
708 Real compound_space = 0.0;
711 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
713 if (dt == Moment (0, 0))
715 for (SCM s = l->get_property ("spacing-wishes");
716 scm_is_pair (s); s = scm_cdr (s))
718 Item *spacing_grob = dynamic_cast<Item *> (unsmob_grob (scm_car (s)));
720 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
727 column for the left one settings should be ok due automatic
731 assert (spacing_grob->get_column () == l);
733 Staff_spacing::get_spacing_params (spacing_grob,
734 &space, &fixed_space);
736 if (Paper_column::when_mom (r).grace_part_)
739 Correct for grace notes.
741 Ugh. The 0.8 is arbitrary.
746 compound_space += space;
747 compound_fixed += fixed_space;
752 if (compound_space <= 0.0 || !wish_count)
754 standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
760 compound_space /= wish_count;
761 compound_fixed /= wish_count;
764 assert (!isinf (compound_space));
765 compound_space = compound_space >? compound_fixed;
768 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
769 works on all architectures.
773 There used to be code that changed spacing depending on
774 raggedright setting. Ugh.
776 Do it more cleanly, or rename the property.
779 Real strength = 1 / (compound_space - compound_fixed);
780 Real distance = compound_space;
781 Spaceable_grob::add_spring (l, r, distance, strength);
785 Get the measure wide ant for arithmetic spacing.
788 Spacing_spanner::get_duration_space (Grob *me, Moment d, Rational shortest, bool *expand_only)
790 Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
791 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
796 We don't space really short notes using the log of the
797 duration, since it would disproportionally stretches the long
798 notes in a piece. In stead, we use geometric spacing with constant 0.5
801 This should probably be tunable, to use other base numbers.
803 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
804 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
805 mm for 8th. (white space), suggesting that we use
807 (1.2 / 1.5)^{-log2(duration ratio)}
811 Rational ratio = d.main_part_ / shortest;
813 return ((k - 1) + double (ratio)) * incr;
818 John S. Gourlay. ``Spacing a Line of Music, '' Technical
819 Report OSU-CISRC-10/87-TR35, Department of Computer and
820 Information Science, The Ohio State University, 1987.
822 Real log = log_2 (shortest);
824 Rational compdur = d.main_part_ + d.grace_part_ / Rational (3);
825 *expand_only = false;
827 return (log_2 (compdur) + k) * incr;
832 Spacing_spanner::note_spacing (Grob *me, Grob *lc, Grob *rc,
833 Moment shortest, bool *expand_only)
835 Moment shortest_playing_len = 0;
836 SCM s = lc->get_property ("shortest-playing-duration");
838 if (unsmob_moment (s))
839 shortest_playing_len = *unsmob_moment (s);
841 if (! shortest_playing_len.to_bool ())
843 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
844 shortest_playing_len = 1;
847 Moment lwhen = Paper_column::when_mom (lc);
848 Moment rwhen = Paper_column::when_mom (rc);
850 Moment delta_t = rwhen - lwhen;
851 if (!Paper_column::is_musical (rc))
854 when toying with mmrests, it is possible to have musical
855 column on the left and non-musical on the right, spanning
859 Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
862 delta_t = delta_t <? * dt;
865 The following is an extra safety measure, such that
866 the length of a mmrest event doesn't cause havoc.
868 shortest_playing_len = shortest_playing_len <? * dt;
874 In normal situations, the next column is at most
875 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
876 with durations, invalidating this assumption. Here we kludge
877 around to get chord tremolos to behave properly.
880 shortest_playing_len = shortest_playing_len >? delta_t;
881 if (delta_t.main_part_ && !lwhen.grace_part_)
883 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
884 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
886 else if (delta_t.grace_part_)
889 TODO: figure out how to space grace notes.
891 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
894 = robust_scm2double (me->get_property ("grace-space-factor"), 1);
902 ADD_INTERFACE (Spacing_spanner, "spacing-spanner-interface",
903 "The space taken by a note is dependent on its duration. Doubling a\n"
904 "duration adds spacing-increment to the space. The most common shortest\n"
905 "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
906 "spaced proportonial to their duration.\n"
908 "Typically, the increment is the width of a black note head. In a\n"
909 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
910 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
911 "head width) A 16th note is followed by 0.5 note head width. The\n"
912 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
913 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
915 ADD_INTERFACE (Spacing_interface, "spacing-interface",
916 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",