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));
153 Perform substitution on GROB_LIST using a constant amount of stack.
155 vector<Grob *> temporary_substition_array;
157 substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr)
159 vector<Grob *> &old_grobs (grob_arr->array_reference ());
160 vector<Grob *> *new_grobs (new_arr == grob_arr
161 ? & temporary_substition_array
162 : &new_arr->array_reference ());
164 new_grobs->resize (old_grobs.size ());
165 Grob **array = (Grob **) new_grobs->data ();
167 for (vsize i = 0; i < old_grobs.size (); i++)
169 Grob *orig = old_grobs[i];
170 Grob *new_grob = substitute_grob (orig);
175 new_grobs->resize (ptr - array);
176 if (new_arr == grob_arr)
177 new_arr->set_array (*new_grobs);
183 forall b in broken-childs:
184 forall p in properties:
185 forall g in p (if grob-list):
188 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
189 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
191 This is problematic: with large (long) scores, the costs can be
192 significant; especially all-elements in System, can become huge. For
193 a typical 50 page score, it requires running through a 100k list 50
198 forall p in properties:
201 put grob list in array,
203 reorder array so spanners are separate -- O (grobcount)
205 find first and last indexes of grobs on a specific system
207 for items this is O (itemcount)
209 for spanners this is O (sum-of spanner-system-ranges)
211 perform the substitution O (sum-of spanner-system-ranges)
214 The complexity is harder to determine, but should be subquadratic;
216 For the situation above, we run through the entire 100k list once,
217 and also (more or less) once through the item part of the 100k (say
218 98k elements) of the list.
221 These timings were measured without -O2.
223 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
225 coriolan, before 2:30, after: 1:59. Increase of 20%.
227 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
231 spanner_system_range (Spanner *sp)
235 if (System *st = sp->get_system ())
236 rv = Slice (st->get_rank (), st->get_rank ());
239 if (sp->broken_intos_.size ())
240 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
241 sp->broken_intos_.back ()->get_system ()->get_rank ());
247 item_system_range (Item *it)
249 if (System *st = it->get_system ())
250 return Slice (st->get_rank (), st->get_rank ());
253 for (LEFT_and_RIGHT (d))
255 Item *bi = it->find_prebroken_piece (d);
256 if (bi && bi->get_system ())
257 sr.add_point (bi->get_system ()->get_rank ());
264 grob_system_range (Grob *g)
266 if (Spanner *s = dynamic_cast<Spanner *> (g))
267 return spanner_system_range (s);
268 else if (Item *it = dynamic_cast<Item *> (g))
269 return item_system_range (it);
274 struct Substitution_entry
278 /* Assumption: we have less than 32k paper columns. */
282 void set (Grob *g, Slice sr)
286 duh, don't support scores with more than 32000 systems.
291 overflow if we don't treat this specially.
298 left_ = (short) sr[LEFT];
299 right_ = (short) sr[RIGHT];
302 Substitution_entry ()
308 int length () { return right_ - left_; }
310 item_compare (void const *a, void const *b)
312 return ((Substitution_entry *)a)->left_
313 - ((Substitution_entry *)b)->left_;
317 spanner_compare (void const *a, void const *b)
319 return ((Substitution_entry *)a)->length ()
320 - ((Substitution_entry *)b)->length ();
325 Spanner::fast_substitute_grob_array (SCM sym,
326 Grob_array *grob_array)
328 int len = grob_array->size ();
330 if (grob_array->ordered ())
337 We store items on the left, spanners on the right in this vector.
339 FIXME: will not multithread.
341 static Substitution_entry *vec;
346 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
350 Slice system_range = spanner_system_range (this);
352 int spanner_index = len;
355 for (vsize i = 0; i < grob_array->size (); i++)
357 Grob *g = grob_array->grob (i);
359 Slice sr = grob_system_range (g);
360 sr.intersect (system_range);
363 if (dynamic_cast<Spanner *> (g))
364 idx = --spanner_index;
365 else if (dynamic_cast<Item *> (g))
368 vec[idx].set (g, sr);
371 qsort (vec, item_index,
372 sizeof (Substitution_entry), &Substitution_entry::item_compare);
374 vector<Slice> item_indices;
375 vector<Slice> spanner_indices;
376 for (int i = 0; i <= system_range.length (); i++)
378 item_indices.push_back (Slice (len, 0));
379 spanner_indices.push_back (Slice (len, 0));
382 vector<Slice> *arrs[]
385 &item_indices, &spanner_indices
388 for (int i = 0; i < item_index; i++)
390 for (int j = vec[i].left_; j <= vec[i].right_; j++)
391 item_indices[j - system_range[LEFT]].add_point (i);
395 sorting vec[spanner_index.. len]
396 is a waste of time -- the staff-spanners screw up the
397 ordering, since they go across the entire score.
399 for (vsize i = spanner_indices.size (); i--;)
400 spanner_indices[i] = Slice (spanner_index, len - 1);
402 assert (item_index <= spanner_index);
404 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
405 || (broken_intos_.empty () && system_range.length () == 0));
406 for (vsize i = 0; i < broken_intos_.size (); i++)
408 Grob *sc = broken_intos_[i];
409 System *l = sc->get_system ();
410 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
412 SCM newval = sc->internal_get_object (sym);
413 if (!unsmob<Grob_array> (newval))
415 newval = Grob_array::make_array ();
416 sc->set_object (sym, newval);
419 Grob_array *new_array = unsmob<Grob_array> (newval);
420 for (int k = 0; k < 2; k++)
421 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
423 Grob *substituted = substitute_grob (vec[j].grob_);
425 new_array->add (substituted);
429 printf ("%d (%d), sp %d (%d)\n",
430 item_indices [i].length (), item_index,
431 spanner_indices[i].length (), len - spanner_index);
434 SCM l1 = substitute_grob_list (grob_list);
435 assert (scm_ilength (l1) == scm_ilength (newval));
444 Although the substitution can be written as
446 property_alist = do_substitution (other_property_alist),
448 we have a special function here: we want to invoke a special
449 function for lists of grobs. These can be very long for large
450 orchestral scores (eg. 1M elements). do_break_substitution () can
451 recurse many levels, taking lots of stack space.
453 This becomes a problem if lily is linked against guile with
454 pthreads. pthreads impose small limits on the stack size.
457 substitute_object_alist (SCM alist, SCM dest)
461 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
463 SCM sym = scm_caar (s);
464 SCM val = scm_cdar (s);
466 if (Grob_array *orig = unsmob<Grob_array> (val))
468 SCM handle = scm_assq (sym, dest);
470 = (scm_is_pair (handle))
472 : Grob_array::make_array ();
474 Grob_array *new_arr = unsmob<Grob_array> (newval);
476 substitute_grob_array (orig, new_arr);
480 val = do_break_substitution (val);
482 if (!SCM_UNBNDP (val))
485 for ly:grob? properties, SCM_UNDEFINED could leak out
486 through ly:grob-property
488 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
489 tail = SCM_CDRLOC (*tail);
496 Spanner::substitute_one_mutable_property (SCM sym,
501 bool fast_done = false;
502 Grob_array *grob_array = unsmob<Grob_array> (val);
504 fast_done = s->fast_substitute_grob_array (sym, grob_array);
507 for (vsize i = 0; i < s->broken_intos_.size (); i++)
509 Grob *sc = s->broken_intos_[i];
510 System *l = sc->get_system ();
511 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
515 SCM newval = sc->internal_get_object (sym);
516 if (!unsmob<Grob_array> (newval))
518 newval = Grob_array::make_array ();
519 sc->set_object (sym, newval);
521 substitute_grob_array (grob_array, unsmob<Grob_array> (newval));
525 SCM newval = do_break_substitution (val);
526 sc->set_object (sym, newval);
532 Grob::substitute_object_links (SCM crit, SCM orig)
534 set_break_subsititution (crit);
535 object_alist_ = substitute_object_alist (orig, object_alist_);