lily/break-substitution.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2001--2011 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   Direction d = LEFT;
 252   do
 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   while (flip (&d) != LEFT);
 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     &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 (val != SCM_UNDEFINED)
 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 }