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));
154 forall b in broken-childs:
155 forall p in properties:
156 forall g in p (if grob-list):
159 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
160 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
162 This is problematic: with large (long) scores, the costs can be
163 significant; especially all-elements in System, can become huge. For
164 a typical 50 page score, it requires running through a 100k list 50
169 forall p in properties:
172 put grob list in array,
174 reorder array so spanners are separate -- O (grobcount)
176 find first and last indexes of grobs on a specific system
178 for items this is O (itemcount)
180 for spanners this is O (sum-of spanner-system-ranges)
182 perform the substitution O (sum-of spanner-system-ranges)
185 The complexity is harder to determine, but should be subquadratic;
187 For the situation above, we run through the entire 100k list once,
188 and also (more or less) once through the item part of the 100k (say
189 98k elements) of the list.
192 These timings were measured without -O2.
194 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
196 coriolan, before 2:30, after: 1:59. Increase of 20%.
198 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
202 spanner_system_range (Spanner *sp)
206 if (System *st = sp->get_system ())
207 rv = Slice (st->get_rank (), st->get_rank ());
210 if (sp->broken_intos_.size ())
211 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
212 sp->broken_intos_.back ()->get_system ()->get_rank ());
218 item_system_range (Item *it)
220 if (System *st = it->get_system ())
221 return Slice (st->get_rank (), st->get_rank ());
224 for (LEFT_and_RIGHT (d))
226 Item *bi = it->find_prebroken_piece (d);
227 if (bi && bi->get_system ())
228 sr.add_point (bi->get_system ()->get_rank ());
235 grob_system_range (Grob *g)
237 if (Spanner *s = dynamic_cast<Spanner *> (g))
238 return spanner_system_range (s);
239 else if (Item *it = dynamic_cast<Item *> (g))
240 return item_system_range (it);
245 struct Substitution_entry
249 /* Assumption: we have less than 32k paper columns. */
253 void set (Grob *g, Slice sr)
257 duh, don't support scores with more than 32000 systems.
262 overflow if we don't treat this specially.
269 left_ = (short) sr[LEFT];
270 right_ = (short) sr[RIGHT];
273 Substitution_entry ()
279 int length () { return right_ - left_; }
281 item_compare (void const *a, void const *b)
283 return ((Substitution_entry *)a)->left_
284 - ((Substitution_entry *)b)->left_;
288 spanner_compare (void const *a, void const *b)
290 return ((Substitution_entry *)a)->length ()
291 - ((Substitution_entry *)b)->length ();
296 Spanner::fast_substitute_grob_array (SCM sym,
297 Grob_array *grob_array)
299 int len = grob_array->size ();
301 if (grob_array->ordered ())
308 We store items on the left, spanners on the right in this vector.
310 FIXME: will not multithread.
312 static Substitution_entry *vec;
317 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
321 Slice system_range = spanner_system_range (this);
323 int spanner_index = len;
326 for (vsize i = 0; i < grob_array->size (); i++)
328 Grob *g = grob_array->grob (i);
330 Slice sr = grob_system_range (g);
331 sr.intersect (system_range);
334 if (dynamic_cast<Spanner *> (g))
335 idx = --spanner_index;
336 else if (dynamic_cast<Item *> (g))
339 vec[idx].set (g, sr);
342 qsort (vec, item_index,
343 sizeof (Substitution_entry), &Substitution_entry::item_compare);
345 vector<Slice> item_indices;
346 vector<Slice> spanner_indices;
347 for (int i = 0; i <= system_range.length (); i++)
349 item_indices.push_back (Slice (len, 0));
350 spanner_indices.push_back (Slice (len, 0));
353 vector<Slice> *arrs[]
356 &item_indices, &spanner_indices
359 for (int i = 0; i < item_index; i++)
361 for (int j = vec[i].left_; j <= vec[i].right_; j++)
362 item_indices[j - system_range[LEFT]].add_point (i);
366 sorting vec[spanner_index.. len]
367 is a waste of time -- the staff-spanners screw up the
368 ordering, since they go across the entire score.
370 for (vsize i = spanner_indices.size (); i--;)
371 spanner_indices[i] = Slice (spanner_index, len - 1);
373 assert (item_index <= spanner_index);
375 assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
376 || (broken_intos_.empty () && system_range.length () == 0));
377 for (vsize i = 0; i < broken_intos_.size (); i++)
379 Grob *sc = broken_intos_[i];
380 System *l = sc->get_system ();
381 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
383 SCM newval = sc->internal_get_object (sym);
384 if (!unsmob<Grob_array> (newval))
386 newval = Grob_array::make_array ();
387 sc->set_object (sym, newval);
390 Grob_array *new_array = unsmob<Grob_array> (newval);
391 for (int k = 0; k < 2; k++)
392 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
394 Grob *substituted = substitute_grob (vec[j].grob_);
396 new_array->add (substituted);
400 printf ("%d (%d), sp %d (%d)\n",
401 item_indices [i].length (), item_index,
402 spanner_indices[i].length (), len - spanner_index);
405 SCM l1 = substitute_grob_list (grob_list);
406 assert (scm_ilength (l1) == scm_ilength (newval));
415 Although the substitution can be written as
417 property_alist = do_substitution (other_property_alist),
419 we have a special function here: we want to invoke a special
420 function for lists of grobs. These can be very long for large
421 orchestral scores (eg. 1M elements). do_break_substitution () can
422 recurse many levels, taking lots of stack space.
424 This becomes a problem if lily is linked against guile with
425 pthreads. pthreads impose small limits on the stack size.
428 substitute_object_alist (SCM alist, SCM dest)
432 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
434 SCM sym = scm_caar (s);
435 SCM val = scm_cdar (s);
437 if (Grob_array *orig = unsmob<Grob_array> (val))
439 SCM handle = scm_assq (sym, dest);
441 = (scm_is_pair (handle))
443 : Grob_array::make_array ();
445 Grob_array *new_arr = unsmob<Grob_array> (newval);
446 // TODO: What if new_arr is null?
447 new_arr->filter_map_assign (*orig, substitute_grob);
451 val = do_break_substitution (val);
453 if (!SCM_UNBNDP (val))
456 for ly:grob? properties, SCM_UNDEFINED could leak out
457 through ly:grob-property
459 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
460 tail = SCM_CDRLOC (*tail);
467 Spanner::substitute_one_mutable_property (SCM sym,
472 bool fast_done = false;
473 Grob_array *grob_array = unsmob<Grob_array> (val);
475 fast_done = s->fast_substitute_grob_array (sym, grob_array);
478 for (vsize i = 0; i < s->broken_intos_.size (); i++)
480 Grob *sc = s->broken_intos_[i];
481 System *l = sc->get_system ();
482 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
486 SCM newval = sc->internal_get_object (sym);
487 if (!unsmob<Grob_array> (newval))
489 newval = Grob_array::make_array ();
490 sc->set_object (sym, newval);
492 Grob_array *new_arr = unsmob<Grob_array> (newval);
493 new_arr->filter_map_assign (*grob_array, substitute_grob);
497 SCM newval = do_break_substitution (val);
498 sc->set_object (sym, newval);
504 Grob::substitute_object_links (SCM crit, SCM orig)
506 set_break_subsititution (crit);
507 object_alist_ = substitute_object_alist (orig, object_alist_);