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"
28 #include "pointer-group-interface.hh"
29 #include "grob-array.hh"
32 TODO: this file/class is too complex. Should figure out how to chop
39 static void standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
40 Real *fixed, Real *space, Moment);
42 static Real default_bar_spacing (Grob *, Grob *, Grob *, Moment);
43 static Real note_spacing (Grob *, Grob *, Grob *, Moment, bool *);
44 static Real get_duration_space (Grob *, Moment dur, Rational shortest, bool *);
45 static Rational find_shortest (Grob *, Link_array<Grob> const &);
46 static void breakable_column_spacing (Grob *, Item *l, Item *r, Moment);
47 static void find_loose_columns () {}
48 static void prune_loose_columns (Grob *, Link_array<Grob> *cols, Rational);
49 static void find_loose_columns (Link_array<Grob> cols);
50 static void set_explicit_neighbor_columns (Link_array<Grob> const &cols);
51 static void set_implicit_neighbor_columns (Link_array<Grob> const &cols);
52 static void do_measure (Rational, Grob *me, Link_array<Grob> *cols);
53 static void musical_column_spacing (Grob *, Item *, Item *, Real, Rational);
54 DECLARE_SCHEME_CALLBACK (set_springs, (SCM));
55 static bool has_interface (Grob *);
59 Return whether COL is fixed to its neighbors by some kind of spacing
63 If in doubt, then we're not loose; the spacing engine should space
64 for it, risking suboptimal spacing.
66 (Otherwise, we might risk core dumps, and other weird stuff.)
69 loose_column (Grob *l, Grob *c, Grob *r)
71 extract_grob_set (c, "right-neighbors", rns);
72 extract_grob_set (c, "left-neighbors", lns);
75 If this column doesn't have a proper neighbor, we should really
76 make it loose, but spacing it correctly is more than we can
79 (this happens in the following situation:
90 the column containing the clef is really loose, and should be
91 attached right to the first column, but that is a lot of work for
92 such a borderline case.)
95 if (lns.is_empty () || rns.is_empty ())
98 Item *l_neighbor = dynamic_cast<Item *> (lns[0]);
99 Item *r_neighbor = dynamic_cast<Item *> (rns[0]);
101 if (!l_neighbor || !r_neighbor)
104 l_neighbor = l_neighbor->get_column ();
105 r_neighbor = dynamic_cast<Item *> (Note_spacing::right_column (r_neighbor));
107 if (l == l_neighbor && r == r_neighbor)
110 if (!l_neighbor || !r_neighbor)
114 Only declare loose if the bounds make a little sense. This means
115 some cases (two isolated, consecutive clef changes) won't be
116 nicely folded, but hey, then don't do that.
118 if (! ((Paper_column::is_musical (l_neighbor) || Item::is_breakable (l_neighbor))
119 && (Paper_column::is_musical (r_neighbor) || Item::is_breakable (r_neighbor))))
125 A rather hairy check, but we really only want to move around
126 clefs. (anything else?)
128 in any case, we don't want to move bar lines.
130 extract_grob_set (c, "elements", elts);
131 for (int i = elts.size (); i--; )
134 if (g && Break_align_interface::has_interface (g))
136 extract_grob_set (g, "elements", gelts);
137 for (int j = gelts.size (); j--; )
142 ugh. -- fix staff-bar name?
144 if (h && h->get_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
154 Remove columns that are not tightly fitting from COLS. In the
155 removed columns, set 'between-cols to the columns where it is in
159 Spacing_spanner::prune_loose_columns (Grob *me, Link_array<Grob> *cols, Rational shortest)
161 Link_array<Grob> newcols;
162 Real increment = robust_scm2double (me->get_property ("spacing-increment"), 1.2);
163 for (int i = 0; i < cols->size (); i++)
165 if (Item::is_breakable (cols->elem (i)) || Paper_column::is_musical (cols->elem (i)))
167 newcols.push (cols->elem (i));
171 Grob *c = cols->elem (i);
172 if (loose_column (cols->elem (i - 1), c, cols->elem (i + 1)))
174 extract_grob_set (c, "right-neighbors", rns_arr);
175 extract_grob_set (c, "left-neighbors", lns_arr);
177 SCM lns = lns_arr.size () ? lns_arr.top()->self_scm () : SCM_BOOL_F;
178 SCM rns = rns_arr.size () ? rns_arr.top()->self_scm () : SCM_BOOL_F;
181 Either object can be non existent, if the score ends
185 extract_grob_set (unsmob_grob (rns), "right-items", right_items);
186 c->set_object ("between-cols", scm_cons (lns,
187 right_items[0]->self_scm ()));
190 Set distance constraints for loose columns
192 Drul_array<Grob *> next_door;
193 next_door[LEFT] = cols->elem (i - 1);
194 next_door[RIGHT] = cols->elem (i + 1);
196 Drul_array<Real> dists (0, 0);
201 Item *lc = dynamic_cast<Item *> ((d == LEFT) ? next_door[LEFT] : c);
202 Item *rc = dynamic_cast<Item *> (d == LEFT ? c : next_door[RIGHT]);
205 extract_grob_set (lc, "spacing-wishes", wishes);
206 for (int k = wishes.size(); k--;)
208 Grob *sp = wishes[k];
209 if (Note_spacing::left_column (sp) != lc
210 || Note_spacing::right_column (sp) != rc)
220 The note spacing should be taken from the musical
224 Real base = note_spacing (me, lc, rc, shortest, &dummy);
225 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
229 dists[d] = max (dists[d], space);
233 Real space, fixed_space;
234 Staff_spacing::get_spacing_params (sp,
235 &space, &fixed_space);
237 dists[d] = max (dists[d], fixed_space);
241 while (flip (&d) != LEFT);
244 r.distance_ = dists[LEFT] + dists[RIGHT];
245 r.item_drul_[LEFT] = dynamic_cast<Item *> (cols->elem (i - 1));
246 r.item_drul_[RIGHT] = dynamic_cast<Item *> (cols->elem (i + 1));
260 Set neighboring columns determined by the spacing-wishes grob property.
263 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> const &cols)
265 for (int i = 0; i < cols.size (); i++)
267 SCM right_neighbors = Grob_array::make_array ();
268 Grob_array *rn_arr = unsmob_grob_array (right_neighbors);
269 int min_rank = 100000; // inf.
271 extract_grob_set (cols[i], "spacing-wishes", wishes);
272 for (int k = wishes.size(); k--;)
274 Item *wish = dynamic_cast<Item *> ( wishes[k]);
276 Item *lc = wish->get_column ();
277 Grob *right = Note_spacing::right_column (wish);
282 Item *rc = dynamic_cast<Item *> (right);
284 int right_rank = Paper_column::get_rank (rc);
285 int left_rank = Paper_column::get_rank (lc);
288 update the left column.
290 if (right_rank <= min_rank)
292 if (right_rank < min_rank)
295 min_rank = right_rank;
300 update the right column of the wish.
304 extract_grob_set (rc, "left-neighbors", lns_arr);
307 Item *it = dynamic_cast<Item *> (lns_arr.top());
308 maxrank = Paper_column::get_rank (it->get_column ());
311 if (left_rank >= maxrank)
314 if (left_rank > maxrank)
316 Grob_array *ga = unsmob_grob_array (rc->get_object ("left-neighbors"));
321 Pointer_group_interface::add_grob (rc, ly_symbol2scm ("left-neighbors"), wish);
327 cols[i]->set_object ("right-neighbors", right_neighbors);
333 Set neighboring columns that have no left/right-neighbor set
334 yet. Only do breakable non-musical columns, and musical columns.
337 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> const &cols)
339 for (int i = 0; i < cols.size (); i++)
341 Item *it = dynamic_cast<Item *> (cols[i]);
342 if (!Item::is_breakable (it) && !Paper_column::is_musical (it))
345 // it->breakable || it->musical
348 sloppy with typing left/right-neighbors should take list, but paper-column found instead.
350 extract_grob_set (cols[i], "left-neighbors", lns);
351 if (lns.is_empty () && i )
353 SCM ga_scm = Grob_array::make_array();
354 Grob_array *ga = unsmob_grob_array (ga_scm);
356 cols[i]->set_object ("left-neighbors", ga_scm);
358 extract_grob_set (cols[i], "right-neighbors", rns);
359 if (rns.is_empty () && i < cols.size () - 1)
361 SCM ga_scm = Grob_array::make_array();
362 Grob_array *ga = unsmob_grob_array (ga_scm);
364 cols[i]->set_object ("right-neighbors", ga_scm);
369 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
371 Spacing_spanner::set_springs (SCM smob)
373 Grob *me = unsmob_grob (smob);
376 can't use get_system() ? --hwn.
378 Link_array<Grob> all (me->pscore_->root_system ()->columns ());
380 set_explicit_neighbor_columns (all);
382 SCM preset_shortest = me->get_property ("common-shortest-duration");
383 Rational global_shortest;
384 if (unsmob_moment (preset_shortest))
386 global_shortest = unsmob_moment (preset_shortest)->main_part_;
390 global_shortest = find_shortest (me, all);
391 if (be_verbose_global)
392 message (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
394 prune_loose_columns (me, &all, global_shortest);
395 set_implicit_neighbor_columns (all);
398 for (int i = 1; i < all.size (); i++)
401 if (Item::is_breakable (sc))
403 Link_array<Grob> measure (all.slice (j, i + 1));
404 do_measure (global_shortest, me, &measure);
409 return SCM_UNSPECIFIED;
413 We want the shortest note that is also "common" in the piece, so we
414 find the shortest in each measure, and take the most frequently
417 This probably gives weird effects with modern music, where every
418 note has a different duration, but hey, don't write that kind of
422 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
425 ascending in duration
427 Array<Rational> durations;
430 Rational shortest_in_measure;
431 shortest_in_measure.set_infinite (1);
433 for (int i = 0; i < cols.size (); i++)
435 if (Paper_column::is_musical (cols[i]))
437 Moment *when = unsmob_moment (cols[i]->get_property ("when"));
440 ignore grace notes for shortest notes.
442 if (when && when->grace_part_)
445 SCM st = cols[i]->get_property ("shortest-starter-duration");
446 Moment this_shortest = *unsmob_moment (st);
447 assert (this_shortest.to_bool ());
448 shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
450 else if (!shortest_in_measure.is_infinity ()
451 && Item::is_breakable (cols[i]))
454 for (; j < durations.size (); j++)
456 if (durations[j] > shortest_in_measure)
458 counts.insert (1, j);
459 durations.insert (shortest_in_measure, j);
462 else if (durations[j] == shortest_in_measure)
469 if (durations.size () == j)
471 durations.push (shortest_in_measure);
475 shortest_in_measure.set_infinite (1);
481 for (int i = durations.size (); i--;)
483 if (counts[i] >= max_count)
486 max_count = counts[i];
489 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
492 SCM bsd = me->get_property ("base-shortest-duration");
493 Rational d = Rational (1, 8);
494 if (Moment *m = unsmob_moment (bsd))
498 d = min (d, durations[max_idx]);
504 Generate spacing for a single measure. We used to have code that did
505 per-measure spacing. Now we have piecewise spacing. We should fix
506 this to support "spacing-regions": some regions have different notes
507 (different time sigs) than others, and should be spaced differently.
510 Spacing_spanner::do_measure (Rational global_shortest, Grob *me,
511 Link_array<Grob> *cols)
513 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
514 for (int i = 0; i < cols->size () - 1; i++)
516 Item *l = dynamic_cast<Item *> (cols->elem (i));
517 Item *r = dynamic_cast<Item *> (cols->elem (i + 1));
519 Paper_column *lc = dynamic_cast<Paper_column *> (l);
520 Paper_column *rc = dynamic_cast<Paper_column *> (r);
522 if (Paper_column::is_musical (l))
524 musical_column_spacing (me, lc, rc, headwid, global_shortest);
525 if (Item *rb = r->find_prebroken_piece (LEFT))
526 musical_column_spacing (me, lc, rb, headwid, global_shortest);
531 The case that the right part is broken as well is rather
532 rare, but it is possible, eg. with a single empty measure,
533 or if one staff finishes a tad earlier than the rest.
535 Item *lb = l->find_prebroken_piece (RIGHT);
536 Item *rb = r->find_prebroken_piece (LEFT);
538 if (i == 0 && Paper_column::get_rank (l) == 0)
542 breakable_column_spacing (me, l, r, global_shortest);
545 breakable_column_spacing (me, lb, r, global_shortest);
548 breakable_column_spacing (me, l, rb, global_shortest);
551 breakable_column_spacing (me, lb, rb, global_shortest);
557 Generate the space between two musical columns LC and RC, given
558 spacing parameters INCR and SHORTEST.
561 Spacing_spanner::musical_column_spacing (Grob *me, Item *lc, Item *rc, Real increment, Rational global_shortest)
563 bool expand_only = false;
564 Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
566 Real compound_note_space = 0.0;
567 Real compound_fixed_note_space = 0.0;
570 extract_grob_set (lc, "right-neighbors", neighbors);
573 We adjust the space following a note only if the next note
574 happens after the current note (this is set in the grob
575 property SPACING-SEQUENCE.
577 for (int i = 0; i < neighbors.size (); i++)
579 Grob *wish = neighbors[i];
581 Item *wish_rcol = Note_spacing::right_column (wish);
582 if (Note_spacing::left_column (wish) != lc
583 || (wish_rcol != rc && wish_rcol != rc->original_))
587 This is probably a waste of time in the case of polyphonic
589 if (Note_spacing::has_interface (wish))
594 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
596 compound_note_space = compound_note_space + space;
597 compound_fixed_note_space = compound_fixed_note_space + fixed;
602 if (Paper_column::when_mom (rc).grace_part_
603 && !Paper_column::when_mom (lc).grace_part_)
606 Ugh. 0.8 is arbitrary.
608 compound_note_space *= 0.8;
611 if (compound_note_space < 0 || wish_count == 0)
613 compound_note_space = base_note_space;
614 compound_fixed_note_space = increment;
618 compound_note_space /= wish_count;
619 compound_fixed_note_space /= wish_count;
623 Whatever we do, the fixed space is smaller than the real
626 TODO: this criterion is discontinuous in the derivative.
627 Maybe it should be continuous?
629 compound_fixed_note_space = min (compound_fixed_note_space, compound_note_space);
631 bool packed = to_boolean (me->get_layout ()->c_variable ("packed"));
632 Real inverse_strength = 1.0;
636 TODO: make sure that the space doesn't exceed the right margin.
641 In packed mode, pack notes as tight as possible. This makes
642 sense mostly in combination with raggedright mode: the notes
643 are then printed at minimum distance. This is mostly useful
644 for ancient notation, but may also be useful for some flavours
645 of contemporary music. If not in raggedright mode, lily will
646 pack as much bars of music as possible into a line, but the
647 line will then be stretched to fill the whole linewidth.
649 inverse_strength = 1.0;
650 distance = compound_fixed_note_space;
654 inverse_strength = (compound_note_space - compound_fixed_note_space);
655 distance = compound_note_space;
658 Spaceable_grob::add_spring (lc, rc, distance, inverse_strength);
662 The one-size-fits all spacing. It doesn't take into account
663 different spacing wishes from one to the next column.
666 Spacing_spanner::standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
667 Real *fixed, Real *space,
672 Drul_array<Item *> cols (l, r);
676 if (!Paper_column::is_musical (cols[d]))
679 Tied accidentals over barlines cause problems, so lets see
680 what happens if we do this for non musical columns only.
682 Interval lext = cols[d]->extent (cols [d], X_AXIS);
683 if (!lext.is_empty ())
684 *fixed += -d * lext[-d];
687 while (flip (&d) != LEFT);
689 if (l->is_breakable (l) && r->is_breakable (r))
691 Moment *dt = unsmob_moment (l->get_property ("measure-length"));
696 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
698 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
702 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
704 if (dt == Moment (0, 0))
707 In this case, Staff_spacing should handle the job,
708 using dt when it is 0 is silly.
710 *space = *fixed + 0.5;
715 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
721 Read hints from L and generate springs.
724 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r, Moment shortest)
726 Real compound_fixed = 0.0;
727 Real compound_space = 0.0;
730 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
732 if (dt == Moment (0, 0))
734 extract_grob_set (l, "spacing-wishes", wishes);
736 for (int i = 0; i < wishes.size (); i++)
738 Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
740 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
747 column for the left one settings should be ok due automatic
751 assert (spacing_grob->get_column () == l);
753 Staff_spacing::get_spacing_params (spacing_grob,
754 &space, &fixed_space);
756 if (Paper_column::when_mom (r).grace_part_)
759 Correct for grace notes.
761 Ugh. The 0.8 is arbitrary.
766 compound_space += space;
767 compound_fixed += fixed_space;
772 if (compound_space <= 0.0 || !wish_count)
774 standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
780 compound_space /= wish_count;
781 compound_fixed /= wish_count;
784 assert (!isinf (compound_space));
785 compound_space = max (compound_space, compound_fixed);
788 There used to be code that changed spacing depending on
789 raggedright setting. Ugh.
791 Do it more cleanly, or rename the property.
794 Real inverse_strength = (compound_space - compound_fixed);
795 Real distance = compound_space;
796 Spaceable_grob::add_spring (l, r, distance, inverse_strength);
800 Get the measure wide ant for arithmetic spacing.
803 Spacing_spanner::get_duration_space (Grob *me, Moment d, Rational shortest, bool *expand_only)
805 Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
806 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
811 We don't space really short notes using the log of the
812 duration, since it would disproportionally stretches the long
813 notes in a piece. In stead, we use geometric spacing with constant 0.5
816 This should probably be tunable, to use other base numbers.
818 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
819 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
820 mm for 8th. (white space), suggesting that we use
822 (1.2 / 1.5)^{-log2(duration ratio)}
826 Rational ratio = d.main_part_ / shortest;
828 return ((k - 1) + double (ratio)) * incr;
833 John S. Gourlay. ``Spacing a Line of Music, '' Technical
834 Report OSU-CISRC-10/87-TR35, Department of Computer and
835 Information Science, The Ohio State University, 1987.
837 Real log = log_2 (shortest);
839 Rational compdur = d.main_part_ + d.grace_part_ / Rational (3);
840 *expand_only = false;
842 return (log_2 (compdur) + k) * incr;
847 Spacing_spanner::note_spacing (Grob *me, Grob *lc, Grob *rc,
848 Moment shortest, bool *expand_only)
850 Moment shortest_playing_len = 0;
851 SCM s = lc->get_property ("shortest-playing-duration");
853 if (unsmob_moment (s))
854 shortest_playing_len = *unsmob_moment (s);
856 if (! shortest_playing_len.to_bool ())
858 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
859 shortest_playing_len = 1;
862 Moment lwhen = Paper_column::when_mom (lc);
863 Moment rwhen = Paper_column::when_mom (rc);
865 Moment delta_t = rwhen - lwhen;
866 if (!Paper_column::is_musical (rc))
869 when toying with mmrests, it is possible to have musical
870 column on the left and non-musical on the right, spanning
874 Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
877 delta_t = min (delta_t, *dt);
880 The following is an extra safety measure, such that
881 the length of a mmrest event doesn't cause havoc.
883 shortest_playing_len = min (shortest_playing_len, *dt);
889 In normal situations, the next column is at most
890 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
891 with durations, invalidating this assumption. Here we kludge
892 around to get chord tremolos to behave properly.
895 shortest_playing_len = max (shortest_playing_len, delta_t);
896 if (delta_t.main_part_ && !lwhen.grace_part_)
898 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
899 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
901 else if (delta_t.grace_part_)
904 TODO: figure out how to space grace notes.
906 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
909 = robust_scm2double (me->get_property ("grace-space-factor"), 1);
917 ADD_INTERFACE (Spacing_spanner, "spacing-spanner-interface",
918 "The space taken by a note is dependent on its duration. Doubling a\n"
919 "duration adds spacing-increment to the space. The most common shortest\n"
920 "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
921 "spaced proportonial to their duration.\n"
923 "Typically, the increment is the width of a black note head. In a\n"
924 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
925 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
926 "head width) A 16th note is followed by 0.5 note head width. The\n"
927 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
928 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
930 ADD_INTERFACE (Spacing_interface, "spacing-interface",
931 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",