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