X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fbreak-substitution.cc;h=75053c34fd00ebe243eb32d23ece6b987b201c17;hb=9e781b7dc83b60a543ce218aa1a5f139f74c760f;hp=d9a766ff9f0a06cca985910b087f6fc171adfd8d;hpb=366ac5a9c6dfb5a32111c8dd6ba40e49334402c3;p=lilypond.git diff --git a/lily/break-substitution.cc b/lily/break-substitution.cc index d9a766ff9f..75053c34fd 100644 --- a/lily/break-substitution.cc +++ b/lily/break-substitution.cc @@ -1,12 +1,31 @@ -#include -#include +/* + This file is part of LilyPond, the GNU music typesetter. + + Copyright (C) 2001--2014 Han-Wen Nienhuys + + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see . +*/ + +#include +#include +using namespace std; -#include "grob.hh" #include "item.hh" -#include "spanner.hh" -#include "system.hh" +#include "system.hh" +#include "grob-array.hh" -static SCM break_criterion; +static SCM break_criterion; void set_break_subsititution (SCM criterion) { @@ -14,71 +33,55 @@ set_break_subsititution (SCM criterion) } /* - Perform the substitution for a single grob. - */ -SCM + Perform the substitution for a single grob. +*/ +Grob * substitute_grob (Grob *sc) { - if (SCM_INUMP (break_criterion)) + if (scm_is_integer (break_criterion)) { - Item * i = dynamic_cast (sc); + Item *i = dynamic_cast (sc); Direction d = to_dir (break_criterion); if (i && i->break_status_dir () != d) - { - Item *br = i->find_prebroken_piece (d); - return (br) ? br->self_scm () : SCM_UNDEFINED; - } + { + Item *br = i->find_prebroken_piece (d); + return br; + } } else { - System * line - = dynamic_cast (unsmob_grob (break_criterion)); + System *line + = dynamic_cast (unsmob_grob (break_criterion)); if (sc->get_system () != line) - { - sc = sc->find_broken_piece (line); + sc = sc->find_broken_piece (line); - } - /* now: !sc || (sc && sc->get_system () == line) */ if (!sc) - return SCM_UNDEFINED; + return 0; /* now: sc && sc->get_system () == line */ if (!line) - return sc->self_scm(); + return sc; /* - We don't return SCM_UNDEFINED for - suicided grobs, for two reasons + We don't return SCM_UNDEFINED for + suicided grobs, for two reasons - - it doesn't work (strange disappearing objects) + - it doesn't work (strange disappearing objects) - - it forces us to mark the parents of a grob, leading to - a huge recursion in the GC routine. - */ - - /* - This was introduced in 1.3.49 as a measure to prevent - programming errors. It looks rather expensive (?). - - TODO: - - benchmark , document when (what kind of programming - errors) this happens. + - it forces us to mark the parents of a grob, leading to + a huge recursion in the GC routine. */ + if (sc->common_refpoint (line, X_AXIS) - && sc->common_refpoint (line, Y_AXIS)) - { - return sc->self_scm (); - } - return SCM_UNDEFINED; + && sc->common_refpoint (line, Y_AXIS)) + return sc; + return 0; } - return sc->self_scm(); + return sc; } - - /* Do break substitution in S, using CRITERION. Return new value. CRITERION is either a SMOB pointer to the desired line, or a number @@ -96,44 +99,45 @@ substitute_grob (Grob *sc) SCM do_break_substitution (SCM src) { - again: - +again: + if (unsmob_grob (src)) { - return substitute_grob (unsmob_grob (src)); + Grob *new_ptr = substitute_grob (unsmob_grob (src)); + return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED; } - else if (gh_vector_p (src)) + else if (scm_is_vector (src)) { - int l = SCM_VECTOR_LENGTH (src); - SCM nv = scm_c_make_vector (l, SCM_UNDEFINED); - - for (int i =0 ; i< l ; i++) - { - SCM si = scm_int2num (i); - scm_vector_set_x (nv, si, do_break_substitution (scm_vector_ref (src, si))); - } + int len = scm_c_vector_length (src); + SCM nv = scm_c_make_vector (len, SCM_UNDEFINED); + for (int i = 0; i < len; i++) + { + SCM si = scm_from_int (i); + scm_vector_set_x (nv, si, + do_break_substitution (scm_vector_ref (src, si))); + } } - else if (ly_pair_p (src)) + else if (scm_is_pair (src)) { /* - UGH! breaks on circular lists. + UGH! breaks on circular lists. */ - SCM newcar = do_break_substitution (ly_car (src)); - SCM oldcdr = ly_cdr (src); - + SCM newcar = do_break_substitution (scm_car (src)); + SCM oldcdr = scm_cdr (src); + if (newcar == SCM_UNDEFINED - && (gh_pair_p (oldcdr) || oldcdr == SCM_EOL)) - { - /* - This is tail-recursion, ie. - - return do_break_substution (cdr); - - We don't want to rely on the compiler to do this. Without - tail-recursion, this easily crashes with a stack overflow. */ - src = oldcdr; - goto again; - } + && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL)) + { + /* + This is tail-recursion, ie. + + return do_break_substution (cdr); + + We don't want to rely on the compiler to do this. Without + tail-recursion, this easily crashes with a stack overflow. */ + src = oldcdr; + goto again; + } return scm_cons (newcar, do_break_substitution (oldcdr)); } @@ -143,140 +147,137 @@ do_break_substitution (SCM src) return src; } - /* Perform substitution on GROB_LIST using a constant amount of stack. - */ -SCM -substitute_grob_list (SCM grob_list) +*/ +vector temporary_substition_array; +void +substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr) { - SCM l = SCM_EOL; - SCM * tail = &l; - - for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s)) + vector &old_grobs (grob_arr->array_reference ()); + vector *new_grobs (new_arr == grob_arr + ? & temporary_substition_array + : &new_arr->array_reference ()); + + new_grobs->resize (old_grobs.size ()); + Grob **array = (Grob **) new_grobs->data (); + Grob **ptr = array; + for (vsize i = 0; i < old_grobs.size (); i++) { - SCM n= substitute_grob (unsmob_grob (gh_car (s))); - - if (n != SCM_UNDEFINED) - { - *tail = gh_cons (n, SCM_EOL); - tail = SCM_CDRLOC(*tail); - } + Grob *orig = old_grobs[i]; + Grob *new_grob = substitute_grob (orig); + if (new_grob) + *ptr++ = new_grob; } - return l; + new_grobs->resize (ptr - array); + if (new_arr == grob_arr) + new_arr->set_array (*new_grobs); } /* We don't do forall b in broken-childs: - forall p in properties: - forall g in p (if grob-list): - g := substitute (g) + forall p in properties: + forall g in p (if grob-list): + g := substitute (g) - for spanners since this is O(SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT = - O(GROBCOUNT), we have a quadratic algorithm. --for a single spanner + for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT = + O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner This is problematic: with large (long) scores, the costs can be significant; especially all-elements in System, can become huge. For a typical 50 page score, it requires running through a 100k list 50 times. - + Instead: forall p in properties: - (if grob list) + (if grob list) - put grob list in array, + put grob list in array, - reorder array so spanners are separate -- O(grobcount) - - find first and last indexes of grobs on a specific system + reorder array so spanners are separate -- O (grobcount) - for items this is O(itemcount) + find first and last indexes of grobs on a specific system - for spanners this is O(sum-of spanner-system-ranges) + for items this is O (itemcount) - perform the substitution O(sum-of spanner-system-ranges) + for spanners this is O (sum-of spanner-system-ranges) + + perform the substitution O (sum-of spanner-system-ranges) The complexity is harder to determine, but should be subquadratic; For the situation above, we run through the entire 100k list once, and also (more or less) once through the item part of the 100k (say - 98k elements) of the list. + 98k elements) of the list. -These timings were measured without -O2. + These timings were measured without -O2. - lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %. + lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %. coriolan, before 2:30, after: 1:59. Increase of 20%. moz-k498-p1, before 24.10, after: 19.790s, Increase of 18% - - */ - Slice -spanner_system_range (Spanner* sp) +spanner_system_range (Spanner *sp) { Slice rv; - - if (System*st = sp->get_system()) - { - rv = Slice (st->rank_, st->rank_); - } - else + + if (System *st = sp->get_system ()) + rv = Slice (st->get_rank (), st->get_rank ()); + else { - if (sp->broken_intos_.size()) - rv = Slice (sp->broken_intos_[0]->get_system()->rank_, - sp->broken_intos_.top()->get_system()->rank_); + if (sp->broken_intos_.size ()) + rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (), + sp->broken_intos_.back ()->get_system ()->get_rank ()); } return rv; } Slice -item_system_range (Item* it) +item_system_range (Item *it) { - if (System*st= it->get_system()) - return Slice (st->rank_, st->rank_); + if (System *st = it->get_system ()) + return Slice (st->get_rank (), st->get_rank ()); Slice sr; - Direction d = LEFT; - do + for (LEFT_and_RIGHT (d)) { Item *bi = it->find_prebroken_piece (d); - if (bi && bi->get_system()) - sr.add_point (bi->get_system()->rank_); + if (bi && bi->get_system ()) + sr.add_point (bi->get_system ()->get_rank ()); } - while (flip(&d)!=LEFT); - + return sr; } Slice grob_system_range (Grob *g) { - if (Spanner*s = dynamic_cast(g)) - return spanner_system_range (s); - else if (Item* it = dynamic_cast (g)) - return item_system_range (it); - else - return Slice(); + if (Spanner *s = dynamic_cast (g)) + return spanner_system_range (s); + else if (Item *it = dynamic_cast (g)) + return item_system_range (it); + else + return Slice (); } - - struct Substitution_entry { - Grob * grob_; + Grob *grob_; + + /* Assumption: we have less than 32k paper columns. */ short left_; short right_; - - void set (Grob*g, Slice sr) + + void set (Grob *g, Slice sr) { grob_ = g; /* @@ -284,174 +285,159 @@ struct Substitution_entry */ if (sr.is_empty ()) { - /* - overflow if we don't treat this specially. - */ - left_ = 1; - right_ = -1; + /* + overflow if we don't treat this specially. + */ + left_ = 1; + right_ = -1; } else { - left_ = sr[LEFT]; - right_ = sr[RIGHT]; + left_ = (short) sr[LEFT]; + right_ = (short) sr[RIGHT]; } } - Substitution_entry() + Substitution_entry () { - grob_ =0; + grob_ = 0; left_ = right_ = -2; } - - int length () { return right_ - left_ ; } + + int length () { return right_ - left_; } static int - item_compare (void const * a , void const * b) + item_compare (void const *a, void const *b) { - return ((Substitution_entry*)a)->left_ - - ((Substitution_entry*)b)->left_; + return ((Substitution_entry *)a)->left_ + - ((Substitution_entry *)b)->left_; } - + static int - spanner_compare (void const * a , void const * b) + spanner_compare (void const *a, void const *b) { - return ((Substitution_entry*)a)->length() - - ((Substitution_entry*)b)->length (); + return ((Substitution_entry *)a)->length () + - ((Substitution_entry *)b)->length (); } }; - - bool -Spanner::fast_fubstitute_grob_list (SCM sym, - SCM grob_list) +Spanner::fast_substitute_grob_array (SCM sym, + Grob_array *grob_array) { - int len = scm_ilength (grob_list); + int len = grob_array->size (); - /* - Only do this complicated thing for large lists. This has the added - advantage that we won't screw up the ordering for elements in - alignments (which typically don't have more than 10 grobs.) - */ - - if (len < 300) + if (grob_array->ordered ()) return false; + if (len < 15) + return false; /* - TODO : should not free it some time? - */ - static Substitution_entry * vec; + We store items on the left, spanners on the right in this vector. + + FIXME: will not multithread. + */ + static Substitution_entry *vec; static int vec_room; if (vec_room < len) { - vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len); + vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len); vec_room = len; } - + Slice system_range = spanner_system_range (this); - Array it_indices; - Array sp_indices; - for (int i = 0; i <= system_range.length (); i++) - { - it_indices.push (Slice (len, 0)); - sp_indices.push (Slice (len, 0)); - } - - - int sp_index = len; - int it_index = 0; - for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s)) + int spanner_index = len; + int item_index = 0; + + for (vsize i = 0; i < grob_array->size (); i++) { - Grob * g = unsmob_grob (gh_car(s)); + Grob *g = grob_array->grob (i); Slice sr = grob_system_range (g); sr.intersect (system_range); int idx = 0; - if (dynamic_cast(g)) - { - idx =--sp_index; - } - else if (dynamic_cast (g)) - { - idx = it_index++; - } + if (dynamic_cast (g)) + idx = --spanner_index; + else if (dynamic_cast (g)) + idx = item_index++; vec[idx].set (g, sr); } - qsort (vec, it_index, - sizeof (Substitution_entry), &Substitution_entry::item_compare); - - Array *arrs[] = { - &it_indices, &sp_indices - }; - - for (int i = 0; i < it_index ;i++) - { - for (int j = vec[i].left_; j <= vec[i].right_; j++) - { - it_indices[j - system_range[LEFT]].add_point (i); - } - } - - /* - sorting vec[sp_index.. len] - is a waste of time -- the staff-spanners screw up the - ordering, since they go across the entire score. - */ - for (int i = sp_indices.size(); i--;) - sp_indices[i]= Slice (sp_index, len-1); - - - assert (it_index <= sp_index); - - assert (broken_intos_.size () == system_range.length () + 1); - for (int i = 0; i < broken_intos_.size(); i++) + qsort (vec, item_index, + sizeof (Substitution_entry), &Substitution_entry::item_compare); + + vector item_indices; + vector spanner_indices; + for (int i = 0; i <= system_range.length (); i++) + { + item_indices.push_back (Slice (len, 0)); + spanner_indices.push_back (Slice (len, 0)); + } + + vector *arrs[] + = + { + &item_indices, &spanner_indices + }; + + for (int i = 0; i < item_index; i++) + { + for (int j = vec[i].left_; j <= vec[i].right_; j++) + item_indices[j - system_range[LEFT]].add_point (i); + } + + /* + sorting vec[spanner_index.. len] + is a waste of time -- the staff-spanners screw up the + ordering, since they go across the entire score. + */ + for (vsize i = spanner_indices.size (); i--;) + spanner_indices[i] = Slice (spanner_index, len - 1); + + assert (item_index <= spanner_index); + + assert ((broken_intos_.size () == (vsize)system_range.length () + 1) + || (broken_intos_.empty () && system_range.length () == 0)); + for (vsize i = 0; i < broken_intos_.size (); i++) { - Grob * sc = broken_intos_[i]; - System * l = sc->get_system (); - set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED); - - SCM newval = SCM_EOL; - SCM * tail = &newval; - - for (int k = 0; k < 2;k++) - for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++) - { - SCM subs =substitute_grob (vec[j].grob_); - if (subs!= SCM_UNDEFINED) - { - *tail = scm_cons (subs, SCM_EOL); - - tail = SCM_CDRLOC(*tail); - } - - } - + Grob *sc = broken_intos_[i]; + System *l = sc->get_system (); + set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED); + + SCM newval = sc->internal_get_object (sym); + if (!unsmob_grob_array (newval)) + { + newval = Grob_array::make_array (); + sc->set_object (sym, newval); + } + + Grob_array *new_array = unsmob_grob_array (newval); + for (int k = 0; k < 2; k++) + for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++) + { + Grob *substituted = substitute_grob (vec[j].grob_); + if (substituted) + new_array->add (substituted); + } + #ifdef PARANOIA - printf ("%d (%d), sp %d (%d)\n", - it_indices [i].length (), it_index, - sp_indices[i].length() , len -sp_index); - + item_indices [i].length (), item_index, + spanner_indices[i].length (), len - spanner_index); + { - SCM l1 =substitute_grob_list (grob_list); - assert (scm_ilength (l1) == scm_ilength (newval)); + SCM l1 = substitute_grob_list (grob_list); + assert (scm_ilength (l1) == scm_ilength (newval)); } #endif - - sc->mutable_property_alist_ = scm_acons (sym, newval, - sc->mutable_property_alist_); } return true; } - -SCM grob_list_p; - /* Although the substitution can be written as @@ -459,63 +445,90 @@ SCM grob_list_p; we have a special function here: we want to invoke a special function for lists of grobs. These can be very long for large - orchestral scores (eg. 1M elements). do_break_substitution() can + orchestral scores (eg. 1M elements). do_break_substitution () can recurse many levels, taking lots of stack space. This becomes a problem if lily is linked against guile with pthreads. pthreads impose small limits on the stack size. - */ +*/ SCM -substitute_mutable_property_alist (SCM alist) +substitute_object_alist (SCM alist, SCM dest) { - if (!grob_list_p) - grob_list_p = scm_c_eval_string ("grob-list?"); - SCM l = SCM_EOL; SCM *tail = &l; - for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s)) + for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s)) { - SCM sym = gh_caar(s); - SCM val = gh_cdar(s); - SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?")); - - if (type == grob_list_p) - val = substitute_grob_list (val); + SCM sym = scm_caar (s); + SCM val = scm_cdar (s); + + if (Grob_array *orig = unsmob_grob_array (val)) + { + SCM handle = scm_assq (sym, dest); + SCM newval + = (scm_is_pair (handle)) + ? scm_cdr (handle) + : Grob_array::make_array (); + + Grob_array *new_arr = unsmob_grob_array (newval); + + substitute_grob_array (orig, new_arr); + val = newval; + } else - val = do_break_substitution (val); - - *tail = gh_cons (gh_cons (sym, val), SCM_EOL); - tail = SCM_CDRLOC (*tail); + val = do_break_substitution (val); + + if (val != SCM_UNDEFINED) + { + /* + for ly:grob? properties, SCM_UNDEFINED could leak out + through ly:grob-property + */ + *tail = scm_cons (scm_cons (sym, val), SCM_EOL); + tail = SCM_CDRLOC (*tail); + } } - return l; } - void Spanner::substitute_one_mutable_property (SCM sym, - SCM val) + SCM val) { - SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?")); - Spanner*s = this; - + Spanner *s = this; + bool fast_done = false; - if (type == grob_list_p) - fast_done = s->fast_fubstitute_grob_list (sym, val); + Grob_array *grob_array = unsmob_grob_array (val); + if (grob_array) + fast_done = s->fast_substitute_grob_array (sym, grob_array); - if (!fast_done) - for (int i = 0; i < s->broken_intos_ .size (); i++) + if (!fast_done) + for (vsize i = 0; i < s->broken_intos_.size (); i++) { - Grob * sc = s->broken_intos_[i]; - System * l = sc->get_system (); - set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED); - - SCM newval = (type == grob_list_p) - ? substitute_grob_list (val) - : do_break_substitution(val); - - sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval), - sc->mutable_property_alist_); + Grob *sc = s->broken_intos_[i]; + System *l = sc->get_system (); + set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED); + + if (grob_array) + { + SCM newval = sc->internal_get_object (sym); + if (!unsmob_grob_array (newval)) + { + newval = Grob_array::make_array (); + sc->set_object (sym, newval); + } + substitute_grob_array (grob_array, unsmob_grob_array (newval)); + } + else + { + SCM newval = do_break_substitution (val); + sc->set_object (sym, newval); + } } } - + +void +Grob::substitute_object_links (SCM crit, SCM orig) +{ + set_break_subsititution (crit); + object_alist_ = substitute_object_alist (orig, object_alist_); +}