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));
153 forall b in broken-childs:
154 forall p in properties:
155 forall g in p (if grob-list):
158 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
159 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
161 This is problematic: with large (long) scores, the costs can be
162 significant; especially all-elements in System, can become huge. For
163 a typical 50 page score, it requires running through a 100k list 50
168 forall p in properties:
171 put grob list in array,
173 reorder array so spanners are separate -- O (grobcount)
175 find first and last indexes of grobs on a specific system
177 for items this is O (itemcount)
179 for spanners this is O (sum-of spanner-system-ranges)
181 perform the substitution O (sum-of spanner-system-ranges)
184 The complexity is harder to determine, but should be subquadratic;
186 For the situation above, we run through the entire 100k list once,
187 and also (more or less) once through the item part of the 100k (say
188 98k elements) of the list.
191 These timings were measured without -O2.
193 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
195 coriolan, before 2:30, after: 1:59. Increase of 20%.
197 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
201 spanner_system_range (Spanner *sp)
205 if (System *st = sp->get_system ())
206 rv = Slice (st->get_rank (), st->get_rank ());
209 if (sp->broken_intos_.size ())
210 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
211 sp->broken_intos_.back ()->get_system ()->get_rank ());
217 item_system_range (Item *it)
219 if (System *st = it->get_system ())
220 return Slice (st->get_rank (), st->get_rank ());
223 for (LEFT_and_RIGHT (d))
225 Item *bi = it->find_prebroken_piece (d);
226 if (bi && bi->get_system ())
227 sr.add_point (bi->get_system ()->get_rank ());
234 grob_system_range (Grob *g)
236 if (Spanner *s = dynamic_cast<Spanner *> (g))
237 return spanner_system_range (s);
238 else if (Item *it = dynamic_cast<Item *> (g))
239 return item_system_range (it);
244 struct Substitution_entry
248 /* Assumption: we have less than 32k paper columns. */
252 void set (Grob *g, Slice sr)
256 duh, don't support scores with more than 32000 systems.
261 overflow if we don't treat this specially.
268 left_ = (short) sr[LEFT];
269 right_ = (short) sr[RIGHT];
272 Substitution_entry ()
278 int length () { return right_ - left_; }
280 item_compare (void const *a, void const *b)
282 return ((Substitution_entry *)a)->left_
283 - ((Substitution_entry *)b)->left_;
287 spanner_compare (void const *a, void const *b)
289 return ((Substitution_entry *)a)->length ()
290 - ((Substitution_entry *)b)->length ();
295 Spanner::fast_substitute_grob_array (SCM sym,
296 Grob_array *grob_array)
298 int len = grob_array->size ();
300 if (grob_array->ordered ())
307 We store items on the left, spanners on the right in this vector.
309 FIXME: will not multithread.
311 static Substitution_entry *vec;
316 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
320 Slice system_range = spanner_system_range (this);
322 int spanner_index = len;
325 for (vsize i = 0; i < grob_array->size (); i++)
327 Grob *g = grob_array->grob (i);
329 Slice sr = grob_system_range (g);
330 sr.intersect (system_range);
333 if (dynamic_cast<Spanner *> (g))
334 idx = --spanner_index;
335 else if (dynamic_cast<Item *> (g))
338 vec[idx].set (g, sr);
341 qsort (vec, item_index,
342 sizeof (Substitution_entry), &Substitution_entry::item_compare);
344 vector<Slice> item_indices;
345 vector<Slice> spanner_indices;
346 for (int i = 0; i <= system_range.length (); i++)
348 item_indices.push_back (Slice (len, 0));
349 spanner_indices.push_back (Slice (len, 0));
352 vector<Slice> *arrs[]
355 &item_indices, &spanner_indices
358 for (int i = 0; i < item_index; i++)
360 for (int j = vec[i].left_; j <= vec[i].right_; j++)
361 item_indices[j - system_range[LEFT]].add_point (i);
365 sorting vec[spanner_index.. len]
366 is a waste of time -- the staff-spanners screw up the
367 ordering, since they go across the entire score.
369 for (vsize i = spanner_indices.size (); i--;)
370 spanner_indices[i] = Slice (spanner_index, len - 1);
372 assert (item_index <= spanner_index);
374 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
375 || (broken_intos_.empty () && system_range.length () == 0));
376 for (vsize i = 0; i < broken_intos_.size (); i++)
378 Grob *sc = broken_intos_[i];
379 System *l = sc->get_system ();
380 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
382 SCM newval = sc->internal_get_object (sym);
383 if (!unsmob<Grob_array> (newval))
385 newval = Grob_array::make_array ();
386 sc->set_object (sym, newval);
389 Grob_array *new_array = unsmob<Grob_array> (newval);
390 for (int k = 0; k < 2; k++)
391 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
393 Grob *substituted = substitute_grob (vec[j].grob_);
395 new_array->add (substituted);
399 printf ("%d (%d), sp %d (%d)\n",
400 item_indices [i].length (), item_index,
401 spanner_indices[i].length (), len - spanner_index);
404 SCM l1 = substitute_grob_list (grob_list);
405 assert (scm_ilength (l1) == scm_ilength (newval));
414 Although the substitution can be written as
416 property_alist = do_substitution (other_property_alist),
418 we have a special function here: we want to invoke a special
419 function for lists of grobs. These can be very long for large
420 orchestral scores (eg. 1M elements). do_break_substitution () can
421 recurse many levels, taking lots of stack space.
423 This becomes a problem if lily is linked against guile with
424 pthreads. pthreads impose small limits on the stack size.
427 substitute_object_alist (SCM alist, SCM dest)
431 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
433 SCM sym = scm_caar (s);
434 SCM val = scm_cdar (s);
436 if (Grob_array *orig = unsmob<Grob_array> (val))
438 SCM handle = scm_assq (sym, dest);
440 = (scm_is_pair (handle))
442 : Grob_array::make_array ();
444 Grob_array *new_arr = unsmob<Grob_array> (newval);
445 // TODO: What if new_arr is null?
446 new_arr->filter_map_assign (*orig, substitute_grob);
450 val = do_break_substitution (val);
452 if (!SCM_UNBNDP (val))
455 for ly:grob? properties, SCM_UNDEFINED could leak out
456 through ly:grob-property
458 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
459 tail = SCM_CDRLOC (*tail);
466 Spanner::substitute_one_mutable_property (SCM sym,
471 bool fast_done = false;
472 Grob_array *grob_array = unsmob<Grob_array> (val);
474 fast_done = s->fast_substitute_grob_array (sym, grob_array);
477 for (vsize i = 0; i < s->broken_intos_.size (); i++)
479 Grob *sc = s->broken_intos_[i];
480 System *l = sc->get_system ();
481 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
485 SCM newval = sc->internal_get_object (sym);
486 if (!unsmob<Grob_array> (newval))
488 newval = Grob_array::make_array ();
489 sc->set_object (sym, newval);
491 Grob_array *new_arr = unsmob<Grob_array> (newval);
492 new_arr->filter_map_assign (*grob_array, substitute_grob);
496 SCM newval = do_break_substitution (val);
497 sc->set_object (sym, newval);
503 Grob::substitute_object_links (SCM crit, SCM orig)
505 set_break_subsititution (crit);
506 object_alist_ = substitute_object_alist (orig, object_alist_);