X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fbreak-substitution.cc;h=d198753d673b88bda66d51e8029259f9d4307681;hb=HEAD;hp=563eda0939ea5a09ddf5db893be8c4c876f38227;hpb=cf33d3709d3b5028fa9c208aa490ce066960ad5c;p=lilypond.git diff --git a/lily/break-substitution.cc b/lily/break-substitution.cc index 563eda0939..d198753d67 100644 --- a/lily/break-substitution.cc +++ b/lily/break-substitution.cc @@ -1,9 +1,31 @@ -#include "grob.hh" +/* + This file is part of LilyPond, the GNU music typesetter. + + Copyright (C) 2001--2015 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 "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) { @@ -11,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)); - if (sc->line_l () != line) - { - sc = sc->find_broken_piece (line); - - } - - /* now: !sc || (sc && sc->line_l () == line) */ + System *line + = unsmob (break_criterion); + if (sc->get_system () != line) + sc = sc->find_broken_piece (line); + + /* now: !sc || (sc && sc->get_system () == line) */ if (!sc) - return SCM_UNDEFINED; + return 0; - /* now: sc && sc->line_l () == line */ + /* 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 - - - it doesn't work (strange disappearing objects) + We don't return SCM_UNDEFINED for + suicided grobs, for two reasons - - it forces us to mark the parents of a grob, leading to - a huge recursion in the GC routine. - */ + - it doesn't work (strange disappearing objects) - /* - 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 @@ -93,44 +99,45 @@ substitute_grob (Grob *sc) SCM do_break_substitution (SCM src) { - again: - - if (unsmob_grob (src)) +again: + + if (unsmob (src)) { - return substitute_grob (unsmob_grob (src)); + Grob *new_ptr = substitute_grob (unsmob (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 = gh_int2scm (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); - - 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 newcar = do_break_substitution (scm_car (src)); + SCM oldcdr = scm_cdr (src); + + if (SCM_UNBNDP (newcar) + && (scm_is_pair (oldcdr) || scm_is_null (oldcdr))) + { + /* + 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)); } @@ -140,32 +147,268 @@ 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) + We don't do + + forall b in broken-childs: + 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 + + 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) + + put grob list in array, + + reorder array so spanners are separate -- O (grobcount) + + find first and last indexes of grobs on a specific system + + for items this is O (itemcount) + + 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. + + + These timings were measured without -O2. + + 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) { - SCM l = SCM_EOL; - SCM * tail = &l; + Slice rv; - for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s)) + if (System *st = sp->get_system ()) + rv = Slice (st->get_rank (), st->get_rank ()); + else { - SCM n= substitute_grob (unsmob_grob (gh_car (s))); + 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) +{ + if (System *st = it->get_system ()) + return Slice (st->get_rank (), st->get_rank ()); - if (n != SCM_UNDEFINED) - { - *tail = gh_cons (n, SCM_EOL); - tail = SCM_CDRLOC(*tail); - } + Slice sr; + for (LEFT_and_RIGHT (d)) + { + Item *bi = it->find_prebroken_piece (d); + if (bi && bi->get_system ()) + sr.add_point (bi->get_system ()->get_rank ()); } - return l; + 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 (); +} -SCM grob_list_p; +struct Substitution_entry +{ + Grob *grob_; + + /* Assumption: we have less than 32k paper columns. */ + short left_; + short right_; + + void set (Grob *g, Slice sr) + { + grob_ = g; + /* + duh, don't support scores with more than 32000 systems. + */ + if (sr.is_empty ()) + { + /* + overflow if we don't treat this specially. + */ + left_ = 1; + right_ = -1; + } + else + { + left_ = (short) sr[LEFT]; + right_ = (short) sr[RIGHT]; + } + } + Substitution_entry () + { + grob_ = 0; + left_ = right_ = -2; + } + + int length () { return right_ - left_; } + static int + item_compare (void const *a, void const *b) + { + return ((Substitution_entry *)a)->left_ + - ((Substitution_entry *)b)->left_; + } + + static int + spanner_compare (void const *a, void const *b) + { + return ((Substitution_entry *)a)->length () + - ((Substitution_entry *)b)->length (); + } +}; + +bool +Spanner::fast_substitute_grob_array (SCM sym, + Grob_array *grob_array) +{ + int len = grob_array->size (); + + if (grob_array->ordered ()) + return false; + + if (len < 15) + return false; + + /* + 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_room = len; + } + + Slice system_range = spanner_system_range (this); + + int spanner_index = len; + int item_index = 0; + + for (vsize i = 0; i < grob_array->size (); i++) + { + Grob *g = grob_array->grob (i); + + Slice sr = grob_system_range (g); + sr.intersect (system_range); + + int idx = 0; + if (dynamic_cast (g)) + idx = --spanner_index; + else if (dynamic_cast (g)) + idx = item_index++; + + vec[idx].set (g, sr); + } + + 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 = sc->internal_get_object (sym); + if (!unsmob (newval)) + { + newval = Grob_array::make_array (); + sc->set_object (sym, newval); + } + + Grob_array *new_array = unsmob (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", + 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)); + } +#endif + } + + return true; +} /* Although the substitution can be written as @@ -174,36 +417,91 @@ 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 (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 (newval); + // TODO: What if new_arr is null? + new_arr->filter_map_assign (*orig, substitute_grob); + 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 (!SCM_UNBNDP (val)) + { + /* + 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) +{ + Spanner *s = this; + + bool fast_done = false; + Grob_array *grob_array = unsmob (val); + if (grob_array) + fast_done = s->fast_substitute_grob_array (sym, grob_array); + + 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); + + if (grob_array) + { + SCM newval = sc->internal_get_object (sym); + if (!unsmob (newval)) + { + newval = Grob_array::make_array (); + sc->set_object (sym, newval); + } + Grob_array *new_arr = unsmob (newval); + new_arr->filter_map_assign (*grob_array, substitute_grob); + } + 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_); +}