lily/break-substitution.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2001--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include <cstdio>
  21 #include <cstdlib>
  22 using namespace std;
  23
  24 #include "item.hh"
  25 #include "system.hh"
  26 #include "grob-array.hh"
  27
  28 using std::vector;
  29
  30 static SCM break_criterion;
  31 void
  32 set_break_subsititution (SCM criterion)
  33 {
  34   break_criterion = criterion;
  35 }
  36
  37 /*
  38   Perform the substitution for a single grob.
  39 */
  40 Grob *
  41 substitute_grob (Grob *sc)
  42 {
  43   if (scm_is_integer (break_criterion))
  44     {
  45       Item *i = dynamic_cast<Item *> (sc);
  46       Direction d = to_dir (break_criterion);
  47       if (i && i->break_status_dir () != d)
  48         {
  49           Item *br = i->find_prebroken_piece (d);
  50           return br;
  51         }
  52     }
  53   else
  54     {
  55       System *line
  56         = unsmob<System> (break_criterion);
  57       if (sc->get_system () != line)
  58         sc = sc->find_broken_piece (line);
  59
  60       /* now: !sc || (sc && sc->get_system () == line) */
  61       if (!sc)
  62         return 0;
  63
  64       /* now: sc && sc->get_system () == line */
  65       if (!line)
  66         return sc;
  67
  68       /*
  69         We don't return SCM_UNDEFINED for
  70         suicided grobs, for two reasons
  71
  72         - it doesn't work (strange disappearing objects)
  73
  74         - it forces us to mark the parents of a grob, leading to
  75         a huge recursion in the GC routine.
  76       */
  77
  78       if (sc->common_refpoint (line, X_AXIS)
  79           && sc->common_refpoint (line, Y_AXIS))
  80         return sc;
  81       return 0;
  82     }
  83
  84   return sc;
  85 }
  86
  87 /*
  88   Do break substitution in S, using CRITERION. Return new value.
  89   CRITERION is either a SMOB pointer to the desired line, or a number
  90   representing the break direction. Do not modify SRC.
  91
  92   It is rather tightly coded, since it takes a lot of time; it is
  93   one of the top functions in the profile.
  94
  95   We don't pass break_criterion as a parameter, since it is
  96   `constant', but takes up stack space.
  97
  98   It would be nice if we could do this in-place partially.  We now
  99   generate a lot of garbage.
 100 */
 101 SCM
 102 do_break_substitution (SCM src)
 103 {
 104 again:
 105
 106   if (unsmob<Grob> (src))
 107     {
 108       Grob *new_ptr = substitute_grob (unsmob<Grob> (src));
 109       return new_ptr ? new_ptr->self_scm () : SCM_UNDEFINED;
 110     }
 111   else if (scm_is_vector (src))
 112     {
 113       int len = scm_c_vector_length (src);
 114       SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
 115       for (int i = 0; i < len; i++)
 116         {
 117           SCM si = scm_from_int (i);
 118           scm_vector_set_x (nv, si,
 119                             do_break_substitution (scm_vector_ref (src, si)));
 120         }
 121     }
 122   else if (scm_is_pair (src))
 123     {
 124       /*
 125         UGH! breaks on circular lists.
 126       */
 127       SCM newcar = do_break_substitution (scm_car (src));
 128       SCM oldcdr = scm_cdr (src);
 129
 130       if (SCM_UNBNDP (newcar)
 131           && (scm_is_pair (oldcdr) || scm_is_null (oldcdr)))
 132         {
 133           /*
 134             This is tail-recursion, ie.
 135
 136             return do_break_substution (cdr);
 137
 138             We don't want to rely on the compiler to do this.  Without
 139             tail-recursion, this easily crashes with a stack overflow.  */
 140           src = oldcdr;
 141           goto again;
 142         }
 143
 144       return scm_cons (newcar, do_break_substitution (oldcdr));
 145     }
 146   else
 147     return src;
 148
 149   return src;
 150 }
 151
 152 /*
 153   We don't do
 154
 155   forall b in broken-childs:
 156   forall p in properties:
 157   forall g in p (if grob-list):
 158   g := substitute (g)
 159
 160   for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
 161   O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
 162
 163   This is problematic: with large (long) scores, the costs can be
 164   significant; especially all-elements in System, can become huge. For
 165   a typical 50 page score, it requires running through a 100k list 50
 166   times.
 167
 168   Instead:
 169
 170   forall p in properties:
 171   (if grob list)
 172
 173   put  grob list in array,
 174
 175   reorder array so spanners are separate -- O (grobcount)
 176
 177   find first and last indexes of grobs on a specific system
 178
 179   for items this is O (itemcount)
 180
 181   for spanners this is O (sum-of spanner-system-ranges)
 182
 183   perform the substitution O (sum-of spanner-system-ranges)
 184
 185
 186   The complexity is harder to determine, but should be subquadratic;
 187
 188   For the situation above, we run through the entire 100k list once,
 189   and also (more or less) once through the item part of the 100k (say
 190   98k elements) of the list.
 191
 192
 193   These timings were measured without -O2.
 194
 195   lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
 196
 197   coriolan, before 2:30, after:  1:59. Increase of 20%.
 198
 199   moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
 200 */
 201
 202 Slice
 203 spanner_system_range (Spanner *sp)
 204 {
 205   Slice rv;
 206
 207   if (System *st = sp->get_system ())
 208     rv = Slice (st->get_rank (), st->get_rank ());
 209   else
 210     {
 211       if (sp->broken_intos_.size ())
 212         rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
 213                     sp->broken_intos_.back ()->get_system ()->get_rank ());
 214     }
 215   return rv;
 216 }
 217
 218 Slice
 219 item_system_range (Item *it)
 220 {
 221   if (System *st = it->get_system ())
 222     return Slice (st->get_rank (), st->get_rank ());
 223
 224   Slice sr;
 225   for (LEFT_and_RIGHT (d))
 226     {
 227       Item *bi = it->find_prebroken_piece (d);
 228       if (bi && bi->get_system ())
 229         sr.add_point (bi->get_system ()->get_rank ());
 230     }
 231
 232   return sr;
 233 }
 234
 235 Slice
 236 grob_system_range (Grob *g)
 237 {
 238   if (Spanner *s = dynamic_cast<Spanner *> (g))
 239     return spanner_system_range (s);
 240   else if (Item *it = dynamic_cast<Item *> (g))
 241     return item_system_range (it);
 242   else
 243     return Slice ();
 244 }
 245
 246 struct Substitution_entry
 247 {
 248   Grob *grob_;
 249
 250   /* Assumption: we have less than 32k paper columns. */
 251   short left_;
 252   short right_;
 253
 254   void set (Grob *g, Slice sr)
 255   {
 256     grob_ = g;
 257     /*
 258       duh, don't support scores with more than 32000 systems.
 259     */
 260     if (sr.is_empty ())
 261       {
 262         /*
 263           overflow if we don't treat this specially.
 264         */
 265         left_ = 1;
 266         right_ = -1;
 267       }
 268     else
 269       {
 270         left_ = (short) sr[LEFT];
 271         right_ = (short) sr[RIGHT];
 272       }
 273   }
 274   Substitution_entry ()
 275   {
 276     grob_ = 0;
 277     left_ = right_ = -2;
 278   }
 279
 280   int length () { return right_ - left_; }
 281   static int
 282   item_compare (void const *a, void const *b)
 283   {
 284     return ((Substitution_entry *)a)->left_
 285            - ((Substitution_entry *)b)->left_;
 286   }
 287
 288   static int
 289   spanner_compare (void const *a, void const *b)
 290   {
 291     return ((Substitution_entry *)a)->length ()
 292            - ((Substitution_entry *)b)->length ();
 293   }
 294 };
 295
 296 bool
 297 Spanner::fast_substitute_grob_array (SCM sym,
 298                                      Grob_array *grob_array)
 299 {
 300   int len = grob_array->size ();
 301
 302   if (grob_array->ordered ())
 303     return false;
 304
 305   if (len < 15)
 306     return false;
 307
 308   /*
 309     We store items on the left, spanners on the right in this vector.
 310
 311     FIXME: will not multithread.
 312   */
 313   static Substitution_entry *vec;
 314   static int vec_room;
 315
 316   if (vec_room < len)
 317     {
 318       vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
 319       vec_room = len;
 320     }
 321
 322   Slice system_range = spanner_system_range (this);
 323
 324   int spanner_index = len;
 325   int item_index = 0;
 326
 327   for (vsize i = 0; i < grob_array->size (); i++)
 328     {
 329       Grob *g = grob_array->grob (i);
 330
 331       Slice sr = grob_system_range (g);
 332       sr.intersect (system_range);
 333
 334       int idx = 0;
 335       if (dynamic_cast<Spanner *> (g))
 336         idx = --spanner_index;
 337       else if (dynamic_cast<Item *> (g))
 338         idx = item_index++;
 339
 340       vec[idx].set (g, sr);
 341     }
 342
 343   qsort (vec, item_index,
 344          sizeof (Substitution_entry), &Substitution_entry::item_compare);
 345
 346   vector<Slice> item_indices;
 347   vector<Slice> spanner_indices;
 348   for (int i = 0; i <= system_range.length (); i++)
 349     {
 350       item_indices.push_back (Slice (len, 0));
 351       spanner_indices.push_back (Slice (len, 0));
 352     }
 353
 354   vector<Slice> *arrs[]
 355   =
 356   {
 357     &item_indices, &spanner_indices
 358   };
 359
 360   for (int i = 0; i < item_index; i++)
 361     {
 362       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 363         item_indices[j - system_range[LEFT]].add_point (i);
 364     }
 365
 366   /*
 367     sorting vec[spanner_index.. len]
 368     is a waste of time -- the staff-spanners screw up the
 369     ordering, since they go across the entire score.
 370   */
 371   for (vsize i = spanner_indices.size (); i--;)
 372     spanner_indices[i] = Slice (spanner_index, len - 1);
 373
 374   assert (item_index <= spanner_index);
 375
 376   assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
 377           || (broken_intos_.empty () && system_range.length () == 0));
 378   for (vsize i = 0; i < broken_intos_.size (); i++)
 379     {
 380       Grob *sc = broken_intos_[i];
 381       System *l = sc->get_system ();
 382       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 383
 384       SCM newval = sc->internal_get_object (sym);
 385       if (!unsmob<Grob_array> (newval))
 386         {
 387           newval = Grob_array::make_array ();
 388           sc->set_object (sym, newval);
 389         }
 390
 391       Grob_array *new_array = unsmob<Grob_array> (newval);
 392       for (int k = 0; k < 2; k++)
 393         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 394           {
 395             Grob *substituted = substitute_grob (vec[j].grob_);
 396             if (substituted)
 397               new_array->add (substituted);
 398           }
 399
 400 #ifdef PARANOIA
 401       printf ("%d (%d), sp %d (%d)\n",
 402               item_indices [i].length (), item_index,
 403               spanner_indices[i].length (), len - spanner_index);
 404
 405       {
 406         SCM l1 = substitute_grob_list (grob_list);
 407         assert (scm_ilength (l1) == scm_ilength (newval));
 408       }
 409 #endif
 410     }
 411
 412   return true;
 413 }
 414
 415 /*
 416   Although the substitution can be written as
 417
 418   property_alist = do_substitution (other_property_alist),
 419
 420   we have a special function here: we want to invoke a special
 421   function for lists of grobs. These can be very long for large
 422   orchestral scores (eg. 1M elements). do_break_substitution () can
 423   recurse many levels, taking lots of stack space.
 424
 425   This becomes a problem if lily is linked against guile with
 426   pthreads. pthreads impose small limits on the stack size.
 427 */
 428 SCM
 429 substitute_object_alist (SCM alist, SCM dest)
 430 {
 431   SCM l = SCM_EOL;
 432   SCM *tail = &l;
 433   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 434     {
 435       SCM sym = scm_caar (s);
 436       SCM val = scm_cdar (s);
 437
 438       if (Grob_array *orig = unsmob<Grob_array> (val))
 439         {
 440           SCM handle = scm_assq (sym, dest);
 441           SCM newval
 442             = (scm_is_pair (handle))
 443               ? scm_cdr (handle)
 444               : Grob_array::make_array ();
 445
 446           Grob_array *new_arr = unsmob<Grob_array> (newval);
 447           // TODO: What if new_arr is null?
 448           new_arr->filter_map_assign (*orig, substitute_grob);
 449           val = newval;
 450         }
 451       else
 452         val = do_break_substitution (val);
 453
 454       if (!SCM_UNBNDP (val))
 455         {
 456           /*
 457             for ly:grob? properties, SCM_UNDEFINED could leak out
 458             through ly:grob-property
 459           */
 460           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 461           tail = SCM_CDRLOC (*tail);
 462         }
 463     }
 464   return l;
 465 }
 466
 467 void
 468 Spanner::substitute_one_mutable_property (SCM sym,
 469                                           SCM val)
 470 {
 471   Spanner *s = this;
 472
 473   bool fast_done = false;
 474   Grob_array *grob_array = unsmob<Grob_array> (val);
 475   if (grob_array)
 476     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 477
 478   if (!fast_done)
 479     for (vsize i = 0; i < s->broken_intos_.size (); i++)
 480       {
 481         Grob *sc = s->broken_intos_[i];
 482         System *l = sc->get_system ();
 483         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 484
 485         if (grob_array)
 486           {
 487             SCM newval = sc->internal_get_object (sym);
 488             if (!unsmob<Grob_array> (newval))
 489               {
 490                 newval = Grob_array::make_array ();
 491                 sc->set_object (sym, newval);
 492               }
 493             Grob_array *new_arr = unsmob<Grob_array> (newval);
 494             new_arr->filter_map_assign (*grob_array, substitute_grob);
 495           }
 496         else
 497           {
 498             SCM newval = do_break_substitution (val);
 499             sc->set_object (sym, newval);
 500           }
 501       }
 502 }
 503
 504 void
 505 Grob::substitute_object_links (SCM crit, SCM orig)
 506 {
 507   set_break_subsititution (crit);
 508   object_alist_ = substitute_object_alist (orig, object_alist_);
 509 }