lily/break-substitution.cc

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