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   Perform substitution on GROB_LIST using a constant amount of stack.
 154 */
 155 vector<Grob *> temporary_substition_array;
 156 void
 157 substitute_grob_array (Grob_array *grob_arr, Grob_array *new_arr)
 158 {
 159   vector<Grob *> &old_grobs (grob_arr->array_reference ());
 160   vector<Grob *> *new_grobs (new_arr == grob_arr
 161                              ? & temporary_substition_array
 162                              : &new_arr->array_reference ());
 163
 164   new_grobs->resize (old_grobs.size ());
 165   Grob **array = (Grob **) new_grobs->data ();
 166   Grob **ptr = array;
 167   for (vsize i = 0; i < old_grobs.size (); i++)
 168     {
 169       Grob *orig = old_grobs[i];
 170       Grob *new_grob = substitute_grob (orig);
 171       if (new_grob)
 172         *ptr++ = new_grob;
 173     }
 174
 175   new_grobs->resize (ptr - array);
 176   if (new_arr == grob_arr)
 177     new_arr->set_array (*new_grobs);
 178 }
 179
 180 /*
 181   We don't do
 182
 183   forall b in broken-childs:
 184   forall p in properties:
 185   forall g in p (if grob-list):
 186   g := substitute (g)
 187
 188   for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
 189   O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
 190
 191   This is problematic: with large (long) scores, the costs can be
 192   significant; especially all-elements in System, can become huge. For
 193   a typical 50 page score, it requires running through a 100k list 50
 194   times.
 195
 196   Instead:
 197
 198   forall p in properties:
 199   (if grob list)
 200
 201   put  grob list in array,
 202
 203   reorder array so spanners are separate -- O (grobcount)
 204
 205   find first and last indexes of grobs on a specific system
 206
 207   for items this is O (itemcount)
 208
 209   for spanners this is O (sum-of spanner-system-ranges)
 210
 211   perform the substitution O (sum-of spanner-system-ranges)
 212
 213
 214   The complexity is harder to determine, but should be subquadratic;
 215
 216   For the situation above, we run through the entire 100k list once,
 217   and also (more or less) once through the item part of the 100k (say
 218   98k elements) of the list.
 219
 220
 221   These timings were measured without -O2.
 222
 223   lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
 224
 225   coriolan, before 2:30, after:  1:59. Increase of 20%.
 226
 227   moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
 228 */
 229
 230 Slice
 231 spanner_system_range (Spanner *sp)
 232 {
 233   Slice rv;
 234
 235   if (System *st = sp->get_system ())
 236     rv = Slice (st->get_rank (), st->get_rank ());
 237   else
 238     {
 239       if (sp->broken_intos_.size ())
 240         rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
 241                     sp->broken_intos_.back ()->get_system ()->get_rank ());
 242     }
 243   return rv;
 244 }
 245
 246 Slice
 247 item_system_range (Item *it)
 248 {
 249   if (System *st = it->get_system ())
 250     return Slice (st->get_rank (), st->get_rank ());
 251
 252   Slice sr;
 253   for (LEFT_and_RIGHT (d))
 254     {
 255       Item *bi = it->find_prebroken_piece (d);
 256       if (bi && bi->get_system ())
 257         sr.add_point (bi->get_system ()->get_rank ());
 258     }
 259
 260   return sr;
 261 }
 262
 263 Slice
 264 grob_system_range (Grob *g)
 265 {
 266   if (Spanner *s = dynamic_cast<Spanner *> (g))
 267     return spanner_system_range (s);
 268   else if (Item *it = dynamic_cast<Item *> (g))
 269     return item_system_range (it);
 270   else
 271     return Slice ();
 272 }
 273
 274 struct Substitution_entry
 275 {
 276   Grob *grob_;
 277
 278   /* Assumption: we have less than 32k paper columns. */
 279   short left_;
 280   short right_;
 281
 282   void set (Grob *g, Slice sr)
 283   {
 284     grob_ = g;
 285     /*
 286       duh, don't support scores with more than 32000 systems.
 287     */
 288     if (sr.is_empty ())
 289       {
 290         /*
 291           overflow if we don't treat this specially.
 292         */
 293         left_ = 1;
 294         right_ = -1;
 295       }
 296     else
 297       {
 298         left_ = (short) sr[LEFT];
 299         right_ = (short) sr[RIGHT];
 300       }
 301   }
 302   Substitution_entry ()
 303   {
 304     grob_ = 0;
 305     left_ = right_ = -2;
 306   }
 307
 308   int length () { return right_ - left_; }
 309   static int
 310   item_compare (void const *a, void const *b)
 311   {
 312     return ((Substitution_entry *)a)->left_
 313            - ((Substitution_entry *)b)->left_;
 314   }
 315
 316   static int
 317   spanner_compare (void const *a, void const *b)
 318   {
 319     return ((Substitution_entry *)a)->length ()
 320            - ((Substitution_entry *)b)->length ();
 321   }
 322 };
 323
 324 bool
 325 Spanner::fast_substitute_grob_array (SCM sym,
 326                                      Grob_array *grob_array)
 327 {
 328   int len = grob_array->size ();
 329
 330   if (grob_array->ordered ())
 331     return false;
 332
 333   if (len < 15)
 334     return false;
 335
 336   /*
 337     We store items on the left, spanners on the right in this vector.
 338
 339     FIXME: will not multithread.
 340   */
 341   static Substitution_entry *vec;
 342   static int vec_room;
 343
 344   if (vec_room < len)
 345     {
 346       vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
 347       vec_room = len;
 348     }
 349
 350   Slice system_range = spanner_system_range (this);
 351
 352   int spanner_index = len;
 353   int item_index = 0;
 354
 355   for (vsize i = 0; i < grob_array->size (); i++)
 356     {
 357       Grob *g = grob_array->grob (i);
 358
 359       Slice sr = grob_system_range (g);
 360       sr.intersect (system_range);
 361
 362       int idx = 0;
 363       if (dynamic_cast<Spanner *> (g))
 364         idx = --spanner_index;
 365       else if (dynamic_cast<Item *> (g))
 366         idx = item_index++;
 367
 368       vec[idx].set (g, sr);
 369     }
 370
 371   qsort (vec, item_index,
 372          sizeof (Substitution_entry), &Substitution_entry::item_compare);
 373
 374   vector<Slice> item_indices;
 375   vector<Slice> spanner_indices;
 376   for (int i = 0; i <= system_range.length (); i++)
 377     {
 378       item_indices.push_back (Slice (len, 0));
 379       spanner_indices.push_back (Slice (len, 0));
 380     }
 381
 382   vector<Slice> *arrs[]
 383   =
 384   {
 385     &item_indices, &spanner_indices
 386   };
 387
 388   for (int i = 0; i < item_index; i++)
 389     {
 390       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 391         item_indices[j - system_range[LEFT]].add_point (i);
 392     }
 393
 394   /*
 395     sorting vec[spanner_index.. len]
 396     is a waste of time -- the staff-spanners screw up the
 397     ordering, since they go across the entire score.
 398   */
 399   for (vsize i = spanner_indices.size (); i--;)
 400     spanner_indices[i] = Slice (spanner_index, len - 1);
 401
 402   assert (item_index <= spanner_index);
 403
 404   assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
 405           || (broken_intos_.empty () && system_range.length () == 0));
 406   for (vsize i = 0; i < broken_intos_.size (); i++)
 407     {
 408       Grob *sc = broken_intos_[i];
 409       System *l = sc->get_system ();
 410       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 411
 412       SCM newval = sc->internal_get_object (sym);
 413       if (!unsmob<Grob_array> (newval))
 414         {
 415           newval = Grob_array::make_array ();
 416           sc->set_object (sym, newval);
 417         }
 418
 419       Grob_array *new_array = unsmob<Grob_array> (newval);
 420       for (int k = 0; k < 2; k++)
 421         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 422           {
 423             Grob *substituted = substitute_grob (vec[j].grob_);
 424             if (substituted)
 425               new_array->add (substituted);
 426           }
 427
 428 #ifdef PARANOIA
 429       printf ("%d (%d), sp %d (%d)\n",
 430               item_indices [i].length (), item_index,
 431               spanner_indices[i].length (), len - spanner_index);
 432
 433       {
 434         SCM l1 = substitute_grob_list (grob_list);
 435         assert (scm_ilength (l1) == scm_ilength (newval));
 436       }
 437 #endif
 438     }
 439
 440   return true;
 441 }
 442
 443 /*
 444   Although the substitution can be written as
 445
 446   property_alist = do_substitution (other_property_alist),
 447
 448   we have a special function here: we want to invoke a special
 449   function for lists of grobs. These can be very long for large
 450   orchestral scores (eg. 1M elements). do_break_substitution () can
 451   recurse many levels, taking lots of stack space.
 452
 453   This becomes a problem if lily is linked against guile with
 454   pthreads. pthreads impose small limits on the stack size.
 455 */
 456 SCM
 457 substitute_object_alist (SCM alist, SCM dest)
 458 {
 459   SCM l = SCM_EOL;
 460   SCM *tail = &l;
 461   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 462     {
 463       SCM sym = scm_caar (s);
 464       SCM val = scm_cdar (s);
 465
 466       if (Grob_array *orig = unsmob<Grob_array> (val))
 467         {
 468           SCM handle = scm_assq (sym, dest);
 469           SCM newval
 470             = (scm_is_pair (handle))
 471               ? scm_cdr (handle)
 472               : Grob_array::make_array ();
 473
 474           Grob_array *new_arr = unsmob<Grob_array> (newval);
 475
 476           substitute_grob_array (orig, new_arr);
 477           val = newval;
 478         }
 479       else
 480         val = do_break_substitution (val);
 481
 482       if (!SCM_UNBNDP (val))
 483         {
 484           /*
 485             for ly:grob? properties, SCM_UNDEFINED could leak out
 486             through ly:grob-property
 487           */
 488           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 489           tail = SCM_CDRLOC (*tail);
 490         }
 491     }
 492   return l;
 493 }
 494
 495 void
 496 Spanner::substitute_one_mutable_property (SCM sym,
 497                                           SCM val)
 498 {
 499   Spanner *s = this;
 500
 501   bool fast_done = false;
 502   Grob_array *grob_array = unsmob<Grob_array> (val);
 503   if (grob_array)
 504     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 505
 506   if (!fast_done)
 507     for (vsize i = 0; i < s->broken_intos_.size (); i++)
 508       {
 509         Grob *sc = s->broken_intos_[i];
 510         System *l = sc->get_system ();
 511         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 512
 513         if (grob_array)
 514           {
 515             SCM newval = sc->internal_get_object (sym);
 516             if (!unsmob<Grob_array> (newval))
 517               {
 518                 newval = Grob_array::make_array ();
 519                 sc->set_object (sym, newval);
 520               }
 521             substitute_grob_array (grob_array, unsmob<Grob_array> (newval));
 522           }
 523         else
 524           {
 525             SCM newval = do_break_substitution (val);
 526             sc->set_object (sym, newval);
 527           }
 528       }
 529 }
 530
 531 void
 532 Grob::substitute_object_links (SCM crit, SCM orig)
 533 {
 534   set_break_subsititution (crit);
 535   object_alist_ = substitute_object_alist (orig, object_alist_);
 536 }