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/>.
25 #include "grob-array.hh"
29 static SCM break_criterion;
31 set_break_subsititution (SCM criterion)
33 break_criterion = criterion;
37 Perform the substitution for a single grob.
40 substitute_grob (Grob *sc)
42 if (scm_is_integer (break_criterion))
44 Item *i = dynamic_cast<Item *> (sc);
45 Direction d = to_dir (break_criterion);
46 if (i && i->break_status_dir () != d)
48 Item *br = i->find_prebroken_piece (d);
55 = unsmob<System> (break_criterion);
56 if (sc->get_system () != line)
57 sc = sc->find_broken_piece (line);
59 /* now: !sc || (sc && sc->get_system () == line) */
63 /* now: sc && sc->get_system () == line */
68 We don't return SCM_UNDEFINED for
69 suicided grobs, for two reasons
71 - it doesn't work (strange disappearing objects)
73 - it forces us to mark the parents of a grob, leading to
74 a huge recursion in the GC routine.
77 if (sc->common_refpoint (line, X_AXIS)
78 && sc->common_refpoint (line, Y_AXIS))
87 Do break substitution in S, using CRITERION. Return new value.
88 CRITERION is either a SMOB pointer to the desired line, or a number
89 representing the break direction. Do not modify SRC.
91 It is rather tightly coded, since it takes a lot of time; it is
92 one of the top functions in the profile.
94 We don't pass break_criterion as a parameter, since it is
95 `constant', but takes up stack space.
97 It would be nice if we could do this in-place partially. We now
98 generate a lot of garbage.
101 do_break_substitution (SCM src)
105 if (unsmob<Grob> (src))
107 Grob *new_ptr = substitute_grob (unsmob<Grob> (src));
108 return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
110 else if (scm_is_vector (src))
112 int len = scm_c_vector_length (src);
113 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
114 for (int i = 0; i < len; i++)
116 SCM si = scm_from_int (i);
117 scm_vector_set_x (nv, si,
118 do_break_substitution (scm_vector_ref (src, si)));
121 else if (scm_is_pair (src))
124 UGH! breaks on circular lists.
126 SCM newcar = do_break_substitution (scm_car (src));
127 SCM oldcdr = scm_cdr (src);
129 if (SCM_UNBNDP (newcar)
130 && (scm_is_pair (oldcdr) || scm_is_null (oldcdr)))
133 This is tail-recursion, ie.
135 return do_break_substution (cdr);
137 We don't want to rely on the compiler to do this. Without
138 tail-recursion, this easily crashes with a stack overflow. */
143 return scm_cons (newcar, do_break_substitution (oldcdr));
152 Perform substitution on GROB_LIST using a constant amount of stack.
154 vector<Grob *> temporary_substition_array;
156 substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr)
158 vector<Grob *> &old_grobs (grob_arr->array_reference ());
159 vector<Grob *> *new_grobs (new_arr == grob_arr
160 ? & temporary_substition_array
161 : &new_arr->array_reference ());
163 new_grobs->resize (old_grobs.size ());
164 Grob **array = (Grob **) new_grobs->data ();
166 for (vsize i = 0; i < old_grobs.size (); i++)
168 Grob *orig = old_grobs[i];
169 Grob *new_grob = substitute_grob (orig);
174 new_grobs->resize (ptr - array);
175 if (new_arr == grob_arr)
176 new_arr->set_array (*new_grobs);
182 forall b in broken-childs:
183 forall p in properties:
184 forall g in p (if grob-list):
187 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
188 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
190 This is problematic: with large (long) scores, the costs can be
191 significant; especially all-elements in System, can become huge. For
192 a typical 50 page score, it requires running through a 100k list 50
197 forall p in properties:
200 put grob list in array,
202 reorder array so spanners are separate -- O (grobcount)
204 find first and last indexes of grobs on a specific system
206 for items this is O (itemcount)
208 for spanners this is O (sum-of spanner-system-ranges)
210 perform the substitution O (sum-of spanner-system-ranges)
213 The complexity is harder to determine, but should be subquadratic;
215 For the situation above, we run through the entire 100k list once,
216 and also (more or less) once through the item part of the 100k (say
217 98k elements) of the list.
220 These timings were measured without -O2.
222 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
224 coriolan, before 2:30, after: 1:59. Increase of 20%.
226 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
230 spanner_system_range (Spanner *sp)
234 if (System *st = sp->get_system ())
235 rv = Slice (st->get_rank (), st->get_rank ());
238 if (sp->broken_intos_.size ())
239 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
240 sp->broken_intos_.back ()->get_system ()->get_rank ());
246 item_system_range (Item *it)
248 if (System *st = it->get_system ())
249 return Slice (st->get_rank (), st->get_rank ());
252 for (LEFT_and_RIGHT (d))
254 Item *bi = it->find_prebroken_piece (d);
255 if (bi && bi->get_system ())
256 sr.add_point (bi->get_system ()->get_rank ());
263 grob_system_range (Grob *g)
265 if (Spanner *s = dynamic_cast<Spanner *> (g))
266 return spanner_system_range (s);
267 else if (Item *it = dynamic_cast<Item *> (g))
268 return item_system_range (it);
273 struct Substitution_entry
277 /* Assumption: we have less than 32k paper columns. */
281 void set (Grob *g, Slice sr)
285 duh, don't support scores with more than 32000 systems.
290 overflow if we don't treat this specially.
297 left_ = (short) sr[LEFT];
298 right_ = (short) sr[RIGHT];
301 Substitution_entry ()
307 int length () { return right_ - left_; }
309 item_compare (void const *a, void const *b)
311 return ((Substitution_entry *)a)->left_
312 - ((Substitution_entry *)b)->left_;
316 spanner_compare (void const *a, void const *b)
318 return ((Substitution_entry *)a)->length ()
319 - ((Substitution_entry *)b)->length ();
324 Spanner::fast_substitute_grob_array (SCM sym,
325 Grob_array *grob_array)
327 int len = grob_array->size ();
329 if (grob_array->ordered ())
336 We store items on the left, spanners on the right in this vector.
338 FIXME: will not multithread.
340 static Substitution_entry *vec;
345 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
349 Slice system_range = spanner_system_range (this);
351 int spanner_index = len;
354 for (vsize i = 0; i < grob_array->size (); i++)
356 Grob *g = grob_array->grob (i);
358 Slice sr = grob_system_range (g);
359 sr.intersect (system_range);
362 if (dynamic_cast<Spanner *> (g))
363 idx = --spanner_index;
364 else if (dynamic_cast<Item *> (g))
367 vec[idx].set (g, sr);
370 qsort (vec, item_index,
371 sizeof (Substitution_entry), &Substitution_entry::item_compare);
373 vector<Slice> item_indices;
374 vector<Slice> spanner_indices;
375 for (int i = 0; i <= system_range.length (); i++)
377 item_indices.push_back (Slice (len, 0));
378 spanner_indices.push_back (Slice (len, 0));
381 vector<Slice> *arrs[]
384 &item_indices, &spanner_indices
387 for (int i = 0; i < item_index; i++)
389 for (int j = vec[i].left_; j <= vec[i].right_; j++)
390 item_indices[j - system_range[LEFT]].add_point (i);
394 sorting vec[spanner_index.. len]
395 is a waste of time -- the staff-spanners screw up the
396 ordering, since they go across the entire score.
398 for (vsize i = spanner_indices.size (); i--;)
399 spanner_indices[i] = Slice (spanner_index, len - 1);
401 assert (item_index <= spanner_index);
403 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
404 || (broken_intos_.empty () && system_range.length () == 0));
405 for (vsize i = 0; i < broken_intos_.size (); i++)
407 Grob *sc = broken_intos_[i];
408 System *l = sc->get_system ();
409 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
411 SCM newval = sc->internal_get_object (sym);
412 if (!unsmob<Grob_array> (newval))
414 newval = Grob_array::make_array ();
415 sc->set_object (sym, newval);
418 Grob_array *new_array = unsmob<Grob_array> (newval);
419 for (int k = 0; k < 2; k++)
420 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
422 Grob *substituted = substitute_grob (vec[j].grob_);
424 new_array->add (substituted);
428 printf ("%d (%d), sp %d (%d)\n",
429 item_indices [i].length (), item_index,
430 spanner_indices[i].length (), len - spanner_index);
433 SCM l1 = substitute_grob_list (grob_list);
434 assert (scm_ilength (l1) == scm_ilength (newval));
443 Although the substitution can be written as
445 property_alist = do_substitution (other_property_alist),
447 we have a special function here: we want to invoke a special
448 function for lists of grobs. These can be very long for large
449 orchestral scores (eg. 1M elements). do_break_substitution () can
450 recurse many levels, taking lots of stack space.
452 This becomes a problem if lily is linked against guile with
453 pthreads. pthreads impose small limits on the stack size.
456 substitute_object_alist (SCM alist, SCM dest)
460 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
462 SCM sym = scm_caar (s);
463 SCM val = scm_cdar (s);
465 if (Grob_array *orig = unsmob<Grob_array> (val))
467 SCM handle = scm_assq (sym, dest);
469 = (scm_is_pair (handle))
471 : Grob_array::make_array ();
473 Grob_array *new_arr = unsmob<Grob_array> (newval);
475 substitute_grob_array (orig, new_arr);
479 val = do_break_substitution (val);
481 if (!SCM_UNBNDP (val))
484 for ly:grob? properties, SCM_UNDEFINED could leak out
485 through ly:grob-property
487 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
488 tail = SCM_CDRLOC (*tail);
495 Spanner::substitute_one_mutable_property (SCM sym,
500 bool fast_done = false;
501 Grob_array *grob_array = unsmob<Grob_array> (val);
503 fast_done = s->fast_substitute_grob_array (sym, grob_array);
506 for (vsize i = 0; i < s->broken_intos_.size (); i++)
508 Grob *sc = s->broken_intos_[i];
509 System *l = sc->get_system ();
510 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
514 SCM newval = sc->internal_get_object (sym);
515 if (!unsmob<Grob_array> (newval))
517 newval = Grob_array::make_array ();
518 sc->set_object (sym, newval);
520 substitute_grob_array (grob_array, unsmob<Grob_array> (newval));
524 SCM newval = do_break_substitution (val);
525 sc->set_object (sym, newval);
531 Grob::substitute_object_links (SCM crit, SCM orig)
533 set_break_subsititution (crit);
534 object_alist_ = substitute_object_alist (orig, object_alist_);