2 break-substitution.cc -- implement grob break substitution.
4 source file of the GNU LilyPond music typesetter
6 (c) 2001--2005 Han-Wen Nienhuys <hanwen@xs4all.nl>
13 #include "grob-array.hh"
17 static SCM break_criterion;
19 set_break_subsititution (SCM criterion)
21 break_criterion = criterion;
25 Perform the substitution for a single grob.
28 substitute_grob (Grob *sc)
30 if (scm_is_integer (break_criterion))
32 Item *i = dynamic_cast<Item *> (sc);
33 Direction d = to_dir (break_criterion);
34 if (i && i->break_status_dir () != d)
36 Item *br = i->find_prebroken_piece (d);
43 = dynamic_cast<System *> (unsmob_grob (break_criterion));
44 if (sc->get_system () != line)
46 sc = sc->find_broken_piece (line);
49 /* now: !sc || (sc && sc->get_system () == line) */
53 /* now: sc && sc->get_system () == line */
58 We don't return SCM_UNDEFINED for
59 suicided grobs, for two reasons
61 - it doesn't work (strange disappearing objects)
63 - it forces us to mark the parents of a grob, leading to
64 a huge recursion in the GC routine.
67 if (sc->common_refpoint (line, X_AXIS)
68 && sc->common_refpoint (line, Y_AXIS))
79 Do break substitution in S, using CRITERION. Return new value.
80 CRITERION is either a SMOB pointer to the desired line, or a number
81 representing the break direction. Do not modify SRC.
83 It is rather tightly coded, since it takes a lot of time; it is
84 one of the top functions in the profile.
86 We don't pass break_criterion as a parameter, since it is
87 `constant', but takes up stack space.
89 It would be nice if we could do this in-place partially. We now
90 generate a lot of garbage.
93 do_break_substitution (SCM src)
97 if (unsmob_grob (src))
99 Grob * new_ptr = substitute_grob (unsmob_grob (src));
100 return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
102 else if (scm_is_vector (src))
104 int len = scm_c_vector_length (src);
105 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
106 for (int i = 0; i < len; i++)
108 SCM si = scm_int2num (i);
109 scm_vector_set_x (nv, si,
110 do_break_substitution (scm_vector_ref (src, si)));
113 else if (scm_is_pair (src))
116 UGH! breaks on circular lists.
118 SCM newcar = do_break_substitution (scm_car (src));
119 SCM oldcdr = scm_cdr (src);
121 if (newcar == SCM_UNDEFINED
122 && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
125 This is tail-recursion, ie.
127 return do_break_substution (cdr);
129 We don't want to rely on the compiler to do this. Without
130 tail-recursion, this easily crashes with a stack overflow. */
135 return scm_cons (newcar, do_break_substitution (oldcdr));
144 Perform substitution on GROB_LIST using a constant amount of stack.
146 Link_array<Grob> temporary_substition_array;
148 substitute_grob_array (Grob_array *grob_arr, Grob_array * new_arr)
150 Link_array<Grob> &old_grobs (grob_arr->array_reference ());
151 Link_array<Grob> *new_grobs (new_arr == grob_arr
152 ? &temporary_substition_array
153 : &new_arr->array_reference ());
155 new_grobs->set_size (old_grobs.size ());
156 Grob **array = (Grob**) new_grobs->accesses();
158 for (int i = 0; i < old_grobs.size (); i++)
160 Grob *orig = old_grobs[i];
161 Grob *new_grob = substitute_grob (orig);
168 new_grobs->set_size (ptr - array);
169 if (new_arr == grob_arr)
171 new_arr->set_array (*new_grobs);
178 forall b in broken-childs:
179 forall p in properties:
180 forall g in p (if grob-list):
183 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
184 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
186 This is problematic: with large (long) scores, the costs can be
187 significant; especially all-elements in System, can become huge. For
188 a typical 50 page score, it requires running through a 100k list 50
193 forall p in properties:
196 put grob list in array,
198 reorder array so spanners are separate -- O (grobcount)
200 find first and last indexes of grobs on a specific system
202 for items this is O (itemcount)
204 for spanners this is O (sum-of spanner-system-ranges)
206 perform the substitution O (sum-of spanner-system-ranges)
209 The complexity is harder to determine, but should be subquadratic;
211 For the situation above, we run through the entire 100k list once,
212 and also (more or less) once through the item part of the 100k (say
213 98k elements) of the list.
216 These timings were measured without -O2.
218 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
220 coriolan, before 2:30, after: 1:59. Increase of 20%.
222 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
226 spanner_system_range (Spanner *sp)
230 if (System *st = sp->get_system ())
232 rv = Slice (st->get_rank (), st->get_rank ());
236 if (sp->broken_intos_.size ())
237 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
238 sp->broken_intos_.top ()->get_system ()->get_rank());
244 item_system_range (Item *it)
246 if (System *st = it->get_system ())
247 return Slice (st->get_rank (), st->get_rank ());
253 Item *bi = it->find_prebroken_piece (d);
254 if (bi && bi->get_system ())
255 sr.add_point (bi->get_system ()->get_rank ());
257 while (flip (&d) != LEFT);
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
279 void set (Grob *g, Slice sr)
283 duh, don't support scores with more than 32000 systems.
288 overflow if we don't treat this specially.
299 Substitution_entry ()
305 int length () { return right_ - left_; }
307 item_compare (void const *a, void const *b)
309 return ((Substitution_entry *)a)->left_
310 - ((Substitution_entry *)b)->left_;
314 spanner_compare (void const *a, void const *b)
316 return ((Substitution_entry *)a)->length ()
317 - ((Substitution_entry *)b)->length ();
322 Spanner::fast_substitute_grob_array (SCM sym,
323 Grob_array *grob_array)
325 int len = grob_array->size();
327 if (grob_array->ordered ())
334 We store items on the left, spanners on the right in this vector.
336 static Substitution_entry *vec;
341 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
345 Slice system_range = spanner_system_range (this);
347 int spanner_index = len;
350 for (int i = 0 ; i < grob_array->size (); i++)
352 Grob *g = grob_array->grob (i);
354 Slice sr = grob_system_range (g);
355 sr.intersect (system_range);
358 if (dynamic_cast<Spanner *> (g))
360 idx = --spanner_index;
362 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 Array<Slice> item_indices;
374 Array<Slice> spanner_indices;
375 for (int i = 0; i <= system_range.length (); i++)
377 item_indices.push (Slice (len, 0));
378 spanner_indices.push (Slice (len, 0));
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++)
390 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 (int 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 () == system_range.length () + 1)
405 || (broken_intos_.is_empty () && system_range.length () == 0));
406 for (int 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->internal_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_);
426 new_array->add (substituted);
431 printf ("%d (%d), sp %d (%d)\n",
432 item_indices [i].length (), item_index,
433 spanner_indices[i].length (), len -spanner_index);
436 SCM l1 = substitute_grob_list (grob_list);
437 assert (scm_ilength (l1) == scm_ilength (newval));
446 Although the substitution can be written as
448 property_alist = do_substitution (other_property_alist),
450 we have a special function here: we want to invoke a special
451 function for lists of grobs. These can be very long for large
452 orchestral scores (eg. 1M elements). do_break_substitution () can
453 recurse many levels, taking lots of stack space.
455 This becomes a problem if lily is linked against guile with
456 pthreads. pthreads impose small limits on the stack size.
459 substitute_object_alist (SCM alist, SCM dest)
463 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
465 SCM sym = scm_caar (s);
466 SCM val = scm_cdar (s);
468 if (Grob_array * orig = unsmob_grob_array (val))
470 SCM handle = scm_assq (sym, dest);
472 (scm_is_pair (handle))
474 : Grob_array::make_array ();
476 Grob_array *new_arr = unsmob_grob_array (newval);
478 substitute_grob_array (orig, new_arr);
482 val = do_break_substitution (val);
484 if (val != SCM_UNDEFINED)
487 for ly:grob? properties, SCM_UNDEFINED could leak out
488 through ly:grob-property
490 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
491 tail = SCM_CDRLOC (*tail);
498 Spanner::substitute_one_mutable_property (SCM sym,
503 bool fast_done = false;
504 Grob_array * grob_array = unsmob_grob_array (val);
506 fast_done = s->fast_substitute_grob_array (sym, grob_array);
509 for (int i = 0; i < s->broken_intos_.size (); i++)
511 Grob *sc = s->broken_intos_[i];
512 System *l = sc->get_system ();
513 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
517 SCM newval = sc->internal_get_object (sym);
518 if (!unsmob_grob_array (newval))
520 newval = Grob_array::make_array ();
521 sc->internal_set_object (sym, newval);
523 substitute_grob_array (grob_array, unsmob_grob_array (newval));
527 SCM newval = do_break_substitution (val);
528 sc->internal_set_object (sym, newval);