2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2001--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
26 #include "grob-array.hh"
30 static SCM break_criterion;
32 set_break_subsititution (SCM criterion)
34 break_criterion = criterion;
38 Perform the substitution for a single grob.
41 substitute_grob (Grob *sc)
43 if (scm_is_integer (break_criterion))
45 Item *i = dynamic_cast<Item *> (sc);
46 Direction d = to_dir (break_criterion);
47 if (i && i->break_status_dir () != d)
49 Item *br = i->find_prebroken_piece (d);
56 = unsmob<System> (break_criterion);
57 if (sc->get_system () != line)
58 sc = sc->find_broken_piece (line);
60 /* now: !sc || (sc && sc->get_system () == line) */
64 /* now: sc && sc->get_system () == line */
69 We don't return SCM_UNDEFINED for
70 suicided grobs, for two reasons
72 - it doesn't work (strange disappearing objects)
74 - it forces us to mark the parents of a grob, leading to
75 a huge recursion in the GC routine.
78 if (sc->common_refpoint (line, X_AXIS)
79 && sc->common_refpoint (line, Y_AXIS))
88 Do break substitution in S, using CRITERION. Return new value.
89 CRITERION is either a SMOB pointer to the desired line, or a number
90 representing the break direction. Do not modify SRC.
92 It is rather tightly coded, since it takes a lot of time; it is
93 one of the top functions in the profile.
95 We don't pass break_criterion as a parameter, since it is
96 `constant', but takes up stack space.
98 It would be nice if we could do this in-place partially. We now
99 generate a lot of garbage.
102 do_break_substitution (SCM src)
106 if (unsmob<Grob> (src))
108 Grob *new_ptr = substitute_grob (unsmob<Grob> (src));
109 return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
111 else if (scm_is_vector (src))
113 int len = scm_c_vector_length (src);
114 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
115 for (int i = 0; i < len; i++)
117 SCM si = scm_from_int (i);
118 scm_vector_set_x (nv, si,
119 do_break_substitution (scm_vector_ref (src, si)));
122 else if (scm_is_pair (src))
125 UGH! breaks on circular lists.
127 SCM newcar = do_break_substitution (scm_car (src));
128 SCM oldcdr = scm_cdr (src);
130 if (SCM_UNBNDP (newcar)
131 && (scm_is_pair (oldcdr) || scm_is_null (oldcdr)))
134 This is tail-recursion, ie.
136 return do_break_substution (cdr);
138 We don't want to rely on the compiler to do this. Without
139 tail-recursion, this easily crashes with a stack overflow. */
144 return scm_cons (newcar, do_break_substitution (oldcdr));
155 forall b in broken-childs:
156 forall p in properties:
157 forall g in p (if grob-list):
160 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
161 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
163 This is problematic: with large (long) scores, the costs can be
164 significant; especially all-elements in System, can become huge. For
165 a typical 50 page score, it requires running through a 100k list 50
170 forall p in properties:
173 put grob list in array,
175 reorder array so spanners are separate -- O (grobcount)
177 find first and last indexes of grobs on a specific system
179 for items this is O (itemcount)
181 for spanners this is O (sum-of spanner-system-ranges)
183 perform the substitution O (sum-of spanner-system-ranges)
186 The complexity is harder to determine, but should be subquadratic;
188 For the situation above, we run through the entire 100k list once,
189 and also (more or less) once through the item part of the 100k (say
190 98k elements) of the list.
193 These timings were measured without -O2.
195 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
197 coriolan, before 2:30, after: 1:59. Increase of 20%.
199 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
203 spanner_system_range (Spanner *sp)
207 if (System *st = sp->get_system ())
208 rv = Slice (st->get_rank (), st->get_rank ());
211 if (sp->broken_intos_.size ())
212 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
213 sp->broken_intos_.back ()->get_system ()->get_rank ());
219 item_system_range (Item *it)
221 if (System *st = it->get_system ())
222 return Slice (st->get_rank (), st->get_rank ());
225 for (LEFT_and_RIGHT (d))
227 Item *bi = it->find_prebroken_piece (d);
228 if (bi && bi->get_system ())
229 sr.add_point (bi->get_system ()->get_rank ());
236 grob_system_range (Grob *g)
238 if (Spanner *s = dynamic_cast<Spanner *> (g))
239 return spanner_system_range (s);
240 else if (Item *it = dynamic_cast<Item *> (g))
241 return item_system_range (it);
246 struct Substitution_entry
250 /* Assumption: we have less than 32k paper columns. */
254 void set (Grob *g, Slice sr)
258 duh, don't support scores with more than 32000 systems.
263 overflow if we don't treat this specially.
270 left_ = (short) sr[LEFT];
271 right_ = (short) sr[RIGHT];
274 Substitution_entry ()
280 int length () { return right_ - left_; }
282 item_compare (void const *a, void const *b)
284 return ((Substitution_entry *)a)->left_
285 - ((Substitution_entry *)b)->left_;
289 spanner_compare (void const *a, void const *b)
291 return ((Substitution_entry *)a)->length ()
292 - ((Substitution_entry *)b)->length ();
297 Spanner::fast_substitute_grob_array (SCM sym,
298 Grob_array *grob_array)
300 int len = grob_array->size ();
302 if (grob_array->ordered ())
309 We store items on the left, spanners on the right in this vector.
311 FIXME: will not multithread.
313 static Substitution_entry *vec;
318 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
322 Slice system_range = spanner_system_range (this);
324 int spanner_index = len;
327 for (vsize i = 0; i < grob_array->size (); i++)
329 Grob *g = grob_array->grob (i);
331 Slice sr = grob_system_range (g);
332 sr.intersect (system_range);
335 if (dynamic_cast<Spanner *> (g))
336 idx = --spanner_index;
337 else if (dynamic_cast<Item *> (g))
340 vec[idx].set (g, sr);
343 qsort (vec, item_index,
344 sizeof (Substitution_entry), &Substitution_entry::item_compare);
346 vector<Slice> item_indices;
347 vector<Slice> spanner_indices;
348 for (int i = 0; i <= system_range.length (); i++)
350 item_indices.push_back (Slice (len, 0));
351 spanner_indices.push_back (Slice (len, 0));
354 vector<Slice> *arrs[]
357 &item_indices, &spanner_indices
360 for (int i = 0; i < item_index; i++)
362 for (int j = vec[i].left_; j <= vec[i].right_; j++)
363 item_indices[j - system_range[LEFT]].add_point (i);
367 sorting vec[spanner_index.. len]
368 is a waste of time -- the staff-spanners screw up the
369 ordering, since they go across the entire score.
371 for (vsize i = spanner_indices.size (); i--;)
372 spanner_indices[i] = Slice (spanner_index, len - 1);
374 assert (item_index <= spanner_index);
376 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
377 || (broken_intos_.empty () && system_range.length () == 0));
378 for (vsize i = 0; i < broken_intos_.size (); i++)
380 Grob *sc = broken_intos_[i];
381 System *l = sc->get_system ();
382 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
384 SCM newval = sc->internal_get_object (sym);
385 if (!unsmob<Grob_array> (newval))
387 newval = Grob_array::make_array ();
388 sc->set_object (sym, newval);
391 Grob_array *new_array = unsmob<Grob_array> (newval);
392 for (int k = 0; k < 2; k++)
393 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
395 Grob *substituted = substitute_grob (vec[j].grob_);
397 new_array->add (substituted);
401 printf ("%d (%d), sp %d (%d)\n",
402 item_indices [i].length (), item_index,
403 spanner_indices[i].length (), len - spanner_index);
406 SCM l1 = substitute_grob_list (grob_list);
407 assert (scm_ilength (l1) == scm_ilength (newval));
416 Although the substitution can be written as
418 property_alist = do_substitution (other_property_alist),
420 we have a special function here: we want to invoke a special
421 function for lists of grobs. These can be very long for large
422 orchestral scores (eg. 1M elements). do_break_substitution () can
423 recurse many levels, taking lots of stack space.
425 This becomes a problem if lily is linked against guile with
426 pthreads. pthreads impose small limits on the stack size.
429 substitute_object_alist (SCM alist, SCM dest)
433 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
435 SCM sym = scm_caar (s);
436 SCM val = scm_cdar (s);
438 if (Grob_array *orig = unsmob<Grob_array> (val))
440 SCM handle = scm_assq (sym, dest);
442 = (scm_is_pair (handle))
444 : Grob_array::make_array ();
446 Grob_array *new_arr = unsmob<Grob_array> (newval);
447 // TODO: What if new_arr is null?
448 new_arr->filter_map_assign (*orig, substitute_grob);
452 val = do_break_substitution (val);
454 if (!SCM_UNBNDP (val))
457 for ly:grob? properties, SCM_UNDEFINED could leak out
458 through ly:grob-property
460 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
461 tail = SCM_CDRLOC (*tail);
468 Spanner::substitute_one_mutable_property (SCM sym,
473 bool fast_done = false;
474 Grob_array *grob_array = unsmob<Grob_array> (val);
476 fast_done = s->fast_substitute_grob_array (sym, grob_array);
479 for (vsize i = 0; i < s->broken_intos_.size (); i++)
481 Grob *sc = s->broken_intos_[i];
482 System *l = sc->get_system ();
483 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
487 SCM newval = sc->internal_get_object (sym);
488 if (!unsmob<Grob_array> (newval))
490 newval = Grob_array::make_array ();
491 sc->set_object (sym, newval);
493 Grob_array *new_arr = unsmob<Grob_array> (newval);
494 new_arr->filter_map_assign (*grob_array, substitute_grob);
498 SCM newval = do_break_substitution (val);
499 sc->set_object (sym, newval);
505 Grob::substitute_object_links (SCM crit, SCM orig)
507 set_break_subsititution (crit);
508 object_alist_ = substitute_object_alist (orig, object_alist_);