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