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>
12 #include "grob-array.hh"
16 static SCM break_criterion;
18 set_break_subsititution (SCM criterion)
20 break_criterion = criterion;
24 Perform the substitution for a single grob.
27 substitute_grob (Grob *sc)
29 if (scm_is_integer (break_criterion))
31 Item *i = dynamic_cast<Item *> (sc);
32 Direction d = to_dir (break_criterion);
33 if (i && i->break_status_dir () != d)
35 Item *br = i->find_prebroken_piece (d);
42 = dynamic_cast<System *> (unsmob_grob (break_criterion));
43 if (sc->get_system () != line)
44 sc = sc->find_broken_piece (line);
46 /* now: !sc || (sc && sc->get_system () == line) */
50 /* now: sc && sc->get_system () == line */
55 We don't return SCM_UNDEFINED for
56 suicided grobs, for two reasons
58 - it doesn't work (strange disappearing objects)
60 - it forces us to mark the parents of a grob, leading to
61 a huge recursion in the GC routine.
64 if (sc->common_refpoint (line, X_AXIS)
65 && sc->common_refpoint (line, Y_AXIS))
74 Do break substitution in S, using CRITERION. Return new value.
75 CRITERION is either a SMOB pointer to the desired line, or a number
76 representing the break direction. Do not modify SRC.
78 It is rather tightly coded, since it takes a lot of time; it is
79 one of the top functions in the profile.
81 We don't pass break_criterion as a parameter, since it is
82 `constant', but takes up stack space.
84 It would be nice if we could do this in-place partially. We now
85 generate a lot of garbage.
88 do_break_substitution (SCM src)
92 if (unsmob_grob (src))
94 Grob *new_ptr = substitute_grob (unsmob_grob (src));
95 return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
97 else if (scm_is_vector (src))
99 int len = scm_c_vector_length (src);
100 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
101 for (int i = 0; i < len; i++)
103 SCM si = scm_from_int (i);
104 scm_vector_set_x (nv, si,
105 do_break_substitution (scm_vector_ref (src, si)));
108 else if (scm_is_pair (src))
111 UGH! breaks on circular lists.
113 SCM newcar = do_break_substitution (scm_car (src));
114 SCM oldcdr = scm_cdr (src);
116 if (newcar == SCM_UNDEFINED
117 && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
120 This is tail-recursion, ie.
122 return do_break_substution (cdr);
124 We don't want to rely on the compiler to do this. Without
125 tail-recursion, this easily crashes with a stack overflow. */
130 return scm_cons (newcar, do_break_substitution (oldcdr));
139 Perform substitution on GROB_LIST using a constant amount of stack.
141 Link_array<Grob> temporary_substition_array;
143 substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr)
145 Link_array<Grob> &old_grobs (grob_arr->array_reference ());
146 Link_array<Grob> *new_grobs (new_arr == grob_arr
147 ? & temporary_substition_array
148 : &new_arr->array_reference ());
150 new_grobs->set_size (old_grobs.size ());
151 Grob **array = (Grob **) new_grobs->accesses ();
153 for (int i = 0; i < old_grobs.size (); i++)
155 Grob *orig = old_grobs[i];
156 Grob *new_grob = substitute_grob (orig);
161 new_grobs->set_size (ptr - array);
162 if (new_arr == grob_arr)
164 new_arr->set_array (*new_grobs);
171 forall b in broken-childs:
172 forall p in properties:
173 forall g in p (if grob-list):
176 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
177 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
179 This is problematic: with large (long) scores, the costs can be
180 significant; especially all-elements in System, can become huge. For
181 a typical 50 page score, it requires running through a 100k list 50
186 forall p in properties:
189 put grob list in array,
191 reorder array so spanners are separate -- O (grobcount)
193 find first and last indexes of grobs on a specific system
195 for items this is O (itemcount)
197 for spanners this is O (sum-of spanner-system-ranges)
199 perform the substitution O (sum-of spanner-system-ranges)
202 The complexity is harder to determine, but should be subquadratic;
204 For the situation above, we run through the entire 100k list once,
205 and also (more or less) once through the item part of the 100k (say
206 98k elements) of the list.
209 These timings were measured without -O2.
211 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
213 coriolan, before 2:30, after: 1:59. Increase of 20%.
215 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
219 spanner_system_range (Spanner *sp)
223 if (System *st = sp->get_system ())
225 rv = Slice (st->get_rank (), st->get_rank ());
229 if (sp->broken_intos_.size ())
230 rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
231 sp->broken_intos_.top ()->get_system ()->get_rank ());
237 item_system_range (Item *it)
239 if (System *st = it->get_system ())
240 return Slice (st->get_rank (), st->get_rank ());
246 Item *bi = it->find_prebroken_piece (d);
247 if (bi && bi->get_system ())
248 sr.add_point (bi->get_system ()->get_rank ());
250 while (flip (&d) != LEFT);
256 grob_system_range (Grob *g)
258 if (Spanner *s = dynamic_cast<Spanner *> (g))
259 return spanner_system_range (s);
260 else if (Item *it = dynamic_cast<Item *> (g))
261 return item_system_range (it);
266 struct Substitution_entry
272 void set (Grob *g, Slice sr)
276 duh, don't support scores with more than 32000 systems.
281 overflow if we don't treat this specially.
292 Substitution_entry ()
298 int length () { return right_ - left_; }
300 item_compare (void const *a, void const *b)
302 return ((Substitution_entry *)a)->left_
303 - ((Substitution_entry *)b)->left_;
307 spanner_compare (void const *a, void const *b)
309 return ((Substitution_entry *)a)->length ()
310 - ((Substitution_entry *)b)->length ();
315 Spanner::fast_substitute_grob_array (SCM sym,
316 Grob_array *grob_array)
318 int len = grob_array->size ();
320 if (grob_array->ordered ())
327 We store items on the left, spanners on the right in this vector.
329 static Substitution_entry *vec;
334 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
338 Slice system_range = spanner_system_range (this);
340 int spanner_index = len;
343 for (int i = 0; i < grob_array->size (); i++)
345 Grob *g = grob_array->grob (i);
347 Slice sr = grob_system_range (g);
348 sr.intersect (system_range);
351 if (dynamic_cast<Spanner *> (g))
352 idx = --spanner_index;
353 else if (dynamic_cast<Item *> (g))
356 vec[idx].set (g, sr);
359 qsort (vec, item_index,
360 sizeof (Substitution_entry), &Substitution_entry::item_compare);
362 Array<Slice> item_indices;
363 Array<Slice> spanner_indices;
364 for (int i = 0; i <= system_range.length (); i++)
366 item_indices.push (Slice (len, 0));
367 spanner_indices.push (Slice (len, 0));
372 &item_indices, &spanner_indices
375 for (int i = 0; i < item_index;i++)
377 for (int j = vec[i].left_; j <= vec[i].right_; j++)
378 item_indices[j - system_range[LEFT]].add_point (i);
382 sorting vec[spanner_index.. len]
383 is a waste of time -- the staff-spanners screw up the
384 ordering, since they go across the entire score.
386 for (int i = spanner_indices.size (); i--;)
387 spanner_indices[i] = Slice (spanner_index, len - 1);
389 assert (item_index <= spanner_index);
391 assert ((broken_intos_.size () == system_range.length () + 1)
392 || (broken_intos_.is_empty () && system_range.length () == 0));
393 for (int i = 0; i < broken_intos_.size (); i++)
395 Grob *sc = broken_intos_[i];
396 System *l = sc->get_system ();
397 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
399 SCM newval = sc->internal_get_object (sym);
400 if (!unsmob_grob_array (newval))
402 newval = Grob_array::make_array ();
403 sc->internal_set_object (sym, newval);
406 Grob_array *new_array = unsmob_grob_array (newval);
407 for (int k = 0; k < 2;k++)
408 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
410 Grob *substituted = substitute_grob (vec[j].grob_);
412 new_array->add (substituted);
416 printf ("%d (%d), sp %d (%d)\n",
417 item_indices [i].length (), item_index,
418 spanner_indices[i].length (), len -spanner_index);
421 SCM l1 = substitute_grob_list (grob_list);
422 assert (scm_ilength (l1) == scm_ilength (newval));
431 Although the substitution can be written as
433 property_alist = do_substitution (other_property_alist),
435 we have a special function here: we want to invoke a special
436 function for lists of grobs. These can be very long for large
437 orchestral scores (eg. 1M elements). do_break_substitution () can
438 recurse many levels, taking lots of stack space.
440 This becomes a problem if lily is linked against guile with
441 pthreads. pthreads impose small limits on the stack size.
444 substitute_object_alist (SCM alist, SCM dest)
448 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
450 SCM sym = scm_caar (s);
451 SCM val = scm_cdar (s);
453 if (Grob_array *orig = unsmob_grob_array (val))
455 SCM handle = scm_assq (sym, dest);
457 = (scm_is_pair (handle))
459 : Grob_array::make_array ();
461 Grob_array *new_arr = unsmob_grob_array (newval);
463 substitute_grob_array (orig, new_arr);
467 val = do_break_substitution (val);
469 if (val != SCM_UNDEFINED)
472 for ly:grob? properties, SCM_UNDEFINED could leak out
473 through ly:grob-property
475 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
476 tail = SCM_CDRLOC (*tail);
483 Spanner::substitute_one_mutable_property (SCM sym,
488 bool fast_done = false;
489 Grob_array *grob_array = unsmob_grob_array (val);
491 fast_done = s->fast_substitute_grob_array (sym, grob_array);
494 for (int i = 0; i < s->broken_intos_.size (); i++)
496 Grob *sc = s->broken_intos_[i];
497 System *l = sc->get_system ();
498 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
502 SCM newval = sc->internal_get_object (sym);
503 if (!unsmob_grob_array (newval))
505 newval = Grob_array::make_array ();
506 sc->internal_set_object (sym, newval);
508 substitute_grob_array (grob_array, unsmob_grob_array (newval));
512 SCM newval = do_break_substitution (val);
513 sc->internal_set_object (sym, newval);