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