7 static SCM break_criterion;
9 set_break_subsititution (SCM criterion)
11 break_criterion = criterion;
15 Perform the substitution for a single grob.
18 substitute_grob (Grob *sc)
20 if (scm_is_integer (break_criterion))
22 Item *i = dynamic_cast<Item *> (sc);
23 Direction d = to_dir (break_criterion);
24 if (i && i->break_status_dir () != d)
26 Item *br = i->find_prebroken_piece (d);
27 return (br) ? br->self_scm () : SCM_UNDEFINED;
33 = dynamic_cast<System *> (unsmob_grob (break_criterion));
34 if (sc->get_system () != line)
36 sc = sc->find_broken_piece (line);
39 /* now: !sc || (sc && sc->get_system () == line) */
43 /* now: sc && sc->get_system () == line */
45 return sc->self_scm ();
48 We don't return SCM_UNDEFINED for
49 suicided grobs, for two reasons
51 - it doesn't work (strange disappearing objects)
53 - it forces us to mark the parents of a grob, leading to
54 a huge recursion in the GC routine.
57 if (sc->common_refpoint (line, X_AXIS)
58 && sc->common_refpoint (line, Y_AXIS))
60 return sc->self_scm ();
65 return sc->self_scm ();
69 Do break substitution in S, using CRITERION. Return new value.
70 CRITERION is either a SMOB pointer to the desired line, or a number
71 representing the break direction. Do not modify SRC.
73 It is rather tightly coded, since it takes a lot of time; it is
74 one of the top functions in the profile.
76 We don't pass break_criterion as a parameter, since it is
77 `constant', but takes up stack space.
79 It would be nice if we could do this in-place partially. We now
80 generate a lot of garbage.
83 do_break_substitution (SCM src)
87 if (unsmob_grob (src))
88 return substitute_grob (unsmob_grob (src));
89 else if (scm_is_vector (src))
91 int len = scm_c_vector_length (src);
92 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
93 for (int i = 0; i < len; i++)
95 SCM si = scm_int2num (i);
96 scm_vector_set_x (nv, si,
97 do_break_substitution (scm_vector_ref (src, si)));
100 else if (scm_is_pair (src))
103 UGH! breaks on circular lists.
105 SCM newcar = do_break_substitution (scm_car (src));
106 SCM oldcdr = scm_cdr (src);
108 if (newcar == SCM_UNDEFINED
109 && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
112 This is tail-recursion, ie.
114 return do_break_substution (cdr);
116 We don't want to rely on the compiler to do this. Without
117 tail-recursion, this easily crashes with a stack overflow. */
122 return scm_cons (newcar, do_break_substitution (oldcdr));
131 Perform substitution on GROB_LIST using a constant amount of stack.
134 substitute_grob_list (SCM grob_list)
139 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
141 SCM n = substitute_grob (unsmob_grob (scm_car (s)));
143 if (n != SCM_UNDEFINED)
145 *tail = scm_cons (n, SCM_EOL);
146 tail = SCM_CDRLOC (*tail);
156 forall b in broken-childs:
157 forall p in properties:
158 forall g in p (if grob-list):
161 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
162 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
164 This is problematic: with large (long) scores, the costs can be
165 significant; especially all-elements in System, can become huge. For
166 a typical 50 page score, it requires running through a 100k list 50
171 forall p in properties:
174 put grob list in array,
176 reorder array so spanners are separate -- O (grobcount)
178 find first and last indexes of grobs on a specific system
180 for items this is O (itemcount)
182 for spanners this is O (sum-of spanner-system-ranges)
184 perform the substitution O (sum-of spanner-system-ranges)
187 The complexity is harder to determine, but should be subquadratic;
189 For the situation above, we run through the entire 100k list once,
190 and also (more or less) once through the item part of the 100k (say
191 98k elements) of the list.
194 These timings were measured without -O2.
196 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
198 coriolan, before 2:30, after: 1:59. Increase of 20%.
200 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
204 spanner_system_range (Spanner *sp)
208 if (System *st = sp->get_system ())
210 rv = Slice (st->rank_, st->rank_);
214 if (sp->broken_intos_.size ())
215 rv = Slice (sp->broken_intos_[0]->get_system ()->rank_,
216 sp->broken_intos_.top ()->get_system ()->rank_);
222 item_system_range (Item *it)
224 if (System *st = it->get_system ())
225 return Slice (st->rank_, st->rank_);
231 Item *bi = it->find_prebroken_piece (d);
232 if (bi && bi->get_system ())
233 sr.add_point (bi->get_system ()->rank_);
235 while (flip (&d) != LEFT);
241 grob_system_range (Grob *g)
243 if (Spanner *s = dynamic_cast<Spanner *> (g))
244 return spanner_system_range (s);
245 else if (Item *it = dynamic_cast<Item *> (g))
246 return item_system_range (it);
251 struct Substitution_entry
257 void set (Grob *g, Slice sr)
261 duh, don't support scores with more than 32000 systems.
266 overflow if we don't treat this specially.
277 Substitution_entry ()
283 int length () { return right_ - left_; }
285 item_compare (void const *a, void const *b)
287 return ((Substitution_entry *)a)->left_
288 - ((Substitution_entry *)b)->left_;
292 spanner_compare (void const *a, void const *b)
294 return ((Substitution_entry *)a)->length ()
295 - ((Substitution_entry *)b)->length ();
300 Spanner::fast_fubstitute_grob_list (SCM sym,
303 int len = scm_ilength (grob_list);
306 Only do this complicated thing for large lists. This has the added
307 advantage that we won't screw up the ordering for elements in
308 alignments (which typically don't have more than 10 grobs.)
315 TODO : should not free it some time?
317 static Substitution_entry *vec;
322 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
326 Slice system_range = spanner_system_range (this);
328 Array<Slice> it_indices;
329 Array<Slice> sp_indices;
330 for (int i = 0; i <= system_range.length (); i++)
332 it_indices.push (Slice (len, 0));
333 sp_indices.push (Slice (len, 0));
338 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
340 Grob *g = unsmob_grob (scm_car (s));
342 Slice sr = grob_system_range (g);
343 sr.intersect (system_range);
346 if (dynamic_cast<Spanner *> (g))
350 else if (dynamic_cast<Item *> (g))
355 vec[idx].set (g, sr);
358 qsort (vec, it_index,
359 sizeof (Substitution_entry), &Substitution_entry::item_compare);
363 &it_indices, &sp_indices
366 for (int i = 0; i < it_index;i++)
368 for (int j = vec[i].left_; j <= vec[i].right_; j++)
370 it_indices[j - system_range[LEFT]].add_point (i);
375 sorting vec[sp_index.. len]
376 is a waste of time -- the staff-spanners screw up the
377 ordering, since they go across the entire score.
379 for (int i = sp_indices.size (); i--;)
380 sp_indices[i] = Slice (sp_index, len - 1);
382 assert (it_index <= sp_index);
384 assert (broken_intos_.size () == system_range.length () + 1);
385 for (int i = 0; i < broken_intos_.size (); i++)
387 Grob *sc = broken_intos_[i];
388 System *l = sc->get_system ();
389 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
391 SCM newval = SCM_EOL;
394 for (int k = 0; k < 2;k++)
395 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
397 SCM subs = substitute_grob (vec[j].grob_);
398 if (subs != SCM_UNDEFINED)
400 *tail = scm_cons (subs, SCM_EOL);
402 tail = SCM_CDRLOC (*tail);
408 printf ("%d (%d), sp %d (%d)\n",
409 it_indices [i].length (), it_index,
410 sp_indices[i].length (), len -sp_index);
413 SCM l1 = substitute_grob_list (grob_list);
414 assert (scm_ilength (l1) == scm_ilength (newval));
421 if (sym == ly_symbol2scm ("all-elements"))
422 sc->mutable_property_alist_
423 = scm_assq_remove_x (sc->mutable_property_alist_,
424 ly_symbol2scm ("all-elements"));
426 sc->mutable_property_alist_ = scm_acons (sym, newval,
427 sc->mutable_property_alist_);
434 Although the substitution can be written as
436 property_alist = do_substitution (other_property_alist),
438 we have a special function here: we want to invoke a special
439 function for lists of grobs. These can be very long for large
440 orchestral scores (eg. 1M elements). do_break_substitution () can
441 recurse many levels, taking lots of stack space.
443 This becomes a problem if lily is linked against guile with
444 pthreads. pthreads impose small limits on the stack size.
447 substitute_mutable_property_alist (SCM alist)
449 SCM grob_list_p = ly_lily_module_constant ("grob-list?");
453 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
455 SCM sym = scm_caar (s);
456 SCM val = scm_cdar (s);
457 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
459 if (type == grob_list_p)
460 val = substitute_grob_list (val);
462 val = do_break_substitution (val);
464 if (val != SCM_UNDEFINED)
467 for ly:grob? properties, SCM_UNDEFINED could leak out
468 through ly:grob-property
470 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
471 tail = SCM_CDRLOC (*tail);
478 Spanner::substitute_one_mutable_property (SCM sym,
481 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
484 bool fast_done = false;
485 SCM grob_list_p = ly_lily_module_constant ("grob-list?");
486 if (type == grob_list_p)
487 fast_done = s->fast_fubstitute_grob_list (sym, val);
490 for (int i = 0; i < s->broken_intos_.size (); i++)
492 Grob *sc = s->broken_intos_[i];
493 System *l = sc->get_system ();
494 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
496 SCM newval = (type == grob_list_p)
497 ? substitute_grob_list (val)
498 : do_break_substitution (val);
501 For the substitution of a single property, we tack the result onto
502 mutable_property_alist_ ; mutable_property_alist_ is empty after
503 Grob::Grob (Grob const&), except that System has all-elements set,
504 as a side product of typeset_grob () on newly copied spanners.
506 Here we clear that list explicitly to free some memory and
507 counter some of the confusion I encountered while debugging
512 if (sym == ly_symbol2scm ("all-elements"))
513 sc->mutable_property_alist_
514 = scm_assq_remove_x (sc->mutable_property_alist_,
515 ly_symbol2scm ("all-elements"));
517 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
518 sc->mutable_property_alist_);