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"
28 static SCM break_criterion;
30 set_break_subsititution (SCM criterion)
32 break_criterion = criterion;
36 Perform the substitution for a single grob.
39 substitute_grob (Grob *sc)
41 if (scm_is_integer (break_criterion))
43 Item *i = dynamic_cast<Item *> (sc);
44 Direction d = to_dir (break_criterion);
45 if (i && i->break_status_dir () != d)
47 Item *br = i->find_prebroken_piece (d);
54 = unsmob<System> (break_criterion);
55 if (sc->get_system () != line)
56 sc = sc->find_broken_piece (line);
58 /* now: !sc || (sc && sc->get_system () == line) */
62 /* now: sc && sc->get_system () == line */
67 We don't return SCM_UNDEFINED for
68 suicided grobs, for two reasons
70 - it doesn't work (strange disappearing objects)
72 - it forces us to mark the parents of a grob, leading to
73 a huge recursion in the GC routine.
76 if (sc->common_refpoint (line, X_AXIS)
77 && sc->common_refpoint (line, Y_AXIS))
86 Do break substitution in S, using CRITERION. Return new value.
87 CRITERION is either a SMOB pointer to the desired line, or a number
88 representing the break direction. Do not modify SRC.
90 It is rather tightly coded, since it takes a lot of time; it is
91 one of the top functions in the profile.
93 We don't pass break_criterion as a parameter, since it is
94 `constant', but takes up stack space.
96 It would be nice if we could do this in-place partially. We now
97 generate a lot of garbage.
100 do_break_substitution (SCM src)
104 if (unsmob<Grob> (src))
106 Grob *new_ptr = substitute_grob (unsmob<Grob> (src));
107 return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
109 else if (scm_is_vector (src))
111 int len = scm_c_vector_length (src);
112 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
113 for (int i = 0; i < len; i++)
115 SCM si = scm_from_int (i);
116 scm_vector_set_x (nv, si,
117 do_break_substitution (scm_vector_ref (src, si)));
120 else if (scm_is_pair (src))
123 UGH! breaks on circular lists.
125 SCM newcar = do_break_substitution (scm_car (src));
126 SCM oldcdr = scm_cdr (src);
128 if (SCM_UNBNDP (newcar)
129 && (scm_is_pair (oldcdr) || scm_is_null (oldcdr)))
132 This is tail-recursion, ie.
134 return do_break_substution (cdr);
136 We don't want to rely on the compiler to do this. Without
137 tail-recursion, this easily crashes with a stack overflow. */
142 return scm_cons (newcar, do_break_substitution (oldcdr));
151 Perform substitution on GROB_LIST using a constant amount of stack.
153 vector<Grob *> temporary_substition_array;
155 substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr)
157 vector<Grob *> &old_grobs (grob_arr->array_reference ());
158 vector<Grob *> *new_grobs (new_arr == grob_arr
159 ? & temporary_substition_array
160 : &new_arr->array_reference ());
162 new_grobs->resize (old_grobs.size ());
163 Grob **array = (Grob **) new_grobs->data ();
165 for (vsize i = 0; i < old_grobs.size (); i++)
167 Grob *orig = old_grobs[i];
168 Grob *new_grob = substitute_grob (orig);
173 new_grobs->resize (ptr - array);
174 if (new_arr == grob_arr)
175 new_arr->set_array (*new_grobs);
181 forall b in broken-childs:
182 forall p in properties:
183 forall g in p (if grob-list):
186 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
187 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
189 This is problematic: with large (long) scores, the costs can be
190 significant; especially all-elements in System, can become huge. For
191 a typical 50 page score, it requires running through a 100k list 50
196 forall p in properties:
199 put grob list in array,
201 reorder array so spanners are separate -- O (grobcount)
203 find first and last indexes of grobs on a specific system
205 for items this is O (itemcount)
207 for spanners this is O (sum-of spanner-system-ranges)
209 perform the substitution O (sum-of spanner-system-ranges)
212 The complexity is harder to determine, but should be subquadratic;
214 For the situation above, we run through the entire 100k list once,
215 and also (more or less) once through the item part of the 100k (say
216 98k elements) of the list.
219 These timings were measured without -O2.
221 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
223 coriolan, before 2:30, after: 1:59. Increase of 20%.
225 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
229 spanner_system_range (Spanner *sp)
233 if (System *st = sp->get_system ())
234 rv = Slice (st->get_rank (), st->get_rank ());
237 if (sp->broken_intos_.size ())
238 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
239 sp->broken_intos_.back ()->get_system ()->get_rank ());
245 item_system_range (Item *it)
247 if (System *st = it->get_system ())
248 return Slice (st->get_rank (), st->get_rank ());
251 for (LEFT_and_RIGHT (d))
253 Item *bi = it->find_prebroken_piece (d);
254 if (bi && bi->get_system ())
255 sr.add_point (bi->get_system ()->get_rank ());
262 grob_system_range (Grob *g)
264 if (Spanner *s = dynamic_cast<Spanner *> (g))
265 return spanner_system_range (s);
266 else if (Item *it = dynamic_cast<Item *> (g))
267 return item_system_range (it);
272 struct Substitution_entry
276 /* Assumption: we have less than 32k paper columns. */
280 void set (Grob *g, Slice sr)
284 duh, don't support scores with more than 32000 systems.
289 overflow if we don't treat this specially.
296 left_ = (short) sr[LEFT];
297 right_ = (short) sr[RIGHT];
300 Substitution_entry ()
306 int length () { return right_ - left_; }
308 item_compare (void const *a, void const *b)
310 return ((Substitution_entry *)a)->left_
311 - ((Substitution_entry *)b)->left_;
315 spanner_compare (void const *a, void const *b)
317 return ((Substitution_entry *)a)->length ()
318 - ((Substitution_entry *)b)->length ();
323 Spanner::fast_substitute_grob_array (SCM sym,
324 Grob_array *grob_array)
326 int len = grob_array->size ();
328 if (grob_array->ordered ())
335 We store items on the left, spanners on the right in this vector.
337 FIXME: will not multithread.
339 static Substitution_entry *vec;
344 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
348 Slice system_range = spanner_system_range (this);
350 int spanner_index = len;
353 for (vsize i = 0; i < grob_array->size (); i++)
355 Grob *g = grob_array->grob (i);
357 Slice sr = grob_system_range (g);
358 sr.intersect (system_range);
361 if (dynamic_cast<Spanner *> (g))
362 idx = --spanner_index;
363 else if (dynamic_cast<Item *> (g))
366 vec[idx].set (g, sr);
369 qsort (vec, item_index,
370 sizeof (Substitution_entry), &Substitution_entry::item_compare);
372 vector<Slice> item_indices;
373 vector<Slice> spanner_indices;
374 for (int i = 0; i <= system_range.length (); i++)
376 item_indices.push_back (Slice (len, 0));
377 spanner_indices.push_back (Slice (len, 0));
380 vector<Slice> *arrs[]
383 &item_indices, &spanner_indices
386 for (int i = 0; i < item_index; i++)
388 for (int j = vec[i].left_; j <= vec[i].right_; j++)
389 item_indices[j - system_range[LEFT]].add_point (i);
393 sorting vec[spanner_index.. len]
394 is a waste of time -- the staff-spanners screw up the
395 ordering, since they go across the entire score.
397 for (vsize i = spanner_indices.size (); i--;)
398 spanner_indices[i] = Slice (spanner_index, len - 1);
400 assert (item_index <= spanner_index);
402 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
403 || (broken_intos_.empty () && system_range.length () == 0));
404 for (vsize i = 0; i < broken_intos_.size (); i++)
406 Grob *sc = broken_intos_[i];
407 System *l = sc->get_system ();
408 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
410 SCM newval = sc->internal_get_object (sym);
411 if (!unsmob<Grob_array> (newval))
413 newval = Grob_array::make_array ();
414 sc->set_object (sym, newval);
417 Grob_array *new_array = unsmob<Grob_array> (newval);
418 for (int k = 0; k < 2; k++)
419 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
421 Grob *substituted = substitute_grob (vec[j].grob_);
423 new_array->add (substituted);
427 printf ("%d (%d), sp %d (%d)\n",
428 item_indices [i].length (), item_index,
429 spanner_indices[i].length (), len - spanner_index);
432 SCM l1 = substitute_grob_list (grob_list);
433 assert (scm_ilength (l1) == scm_ilength (newval));
442 Although the substitution can be written as
444 property_alist = do_substitution (other_property_alist),
446 we have a special function here: we want to invoke a special
447 function for lists of grobs. These can be very long for large
448 orchestral scores (eg. 1M elements). do_break_substitution () can
449 recurse many levels, taking lots of stack space.
451 This becomes a problem if lily is linked against guile with
452 pthreads. pthreads impose small limits on the stack size.
455 substitute_object_alist (SCM alist, SCM dest)
459 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
461 SCM sym = scm_caar (s);
462 SCM val = scm_cdar (s);
464 if (Grob_array *orig = unsmob<Grob_array> (val))
466 SCM handle = scm_assq (sym, dest);
468 = (scm_is_pair (handle))
470 : Grob_array::make_array ();
472 Grob_array *new_arr = unsmob<Grob_array> (newval);
474 substitute_grob_array (orig, new_arr);
478 val = do_break_substitution (val);
480 if (!SCM_UNBNDP (val))
483 for ly:grob? properties, SCM_UNDEFINED could leak out
484 through ly:grob-property
486 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
487 tail = SCM_CDRLOC (*tail);
494 Spanner::substitute_one_mutable_property (SCM sym,
499 bool fast_done = false;
500 Grob_array *grob_array = unsmob<Grob_array> (val);
502 fast_done = s->fast_substitute_grob_array (sym, grob_array);
505 for (vsize i = 0; i < s->broken_intos_.size (); i++)
507 Grob *sc = s->broken_intos_[i];
508 System *l = sc->get_system ();
509 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
513 SCM newval = sc->internal_get_object (sym);
514 if (!unsmob<Grob_array> (newval))
516 newval = Grob_array::make_array ();
517 sc->set_object (sym, newval);
519 substitute_grob_array (grob_array, unsmob<Grob_array> (newval));
523 SCM newval = do_break_substitution (val);
524 sc->set_object (sym, newval);
530 Grob::substitute_object_links (SCM crit, SCM orig)
532 set_break_subsititution (crit);
533 object_alist_ = substitute_object_alist (orig, object_alist_);