lily/break-substitution.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2001--2012 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   {
 385     &item_indices, &spanner_indices
 386   };
 387
 388   for (int i = 0; i < item_index; i++)
 389     {
 390       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 391         item_indices[j - system_range[LEFT]].add_point (i);
 392     }
 393
 394   /*
 395     sorting vec[spanner_index.. len]
 396     is a waste of time -- the staff-spanners screw up the
 397     ordering, since they go across the entire score.
 398   */
 399   for (vsize i = spanner_indices.size (); i--;)
 400     spanner_indices[i] = Slice (spanner_index, len - 1);
 401
 402   assert (item_index <= spanner_index);
 403
 404   assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
 405           || (broken_intos_.empty () && system_range.length () == 0));
 406   for (vsize i = 0; i < broken_intos_.size (); i++)
 407     {
 408       Grob *sc = broken_intos_[i];
 409       System *l = sc->get_system ();
 410       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 411
 412       SCM newval = sc->internal_get_object (sym);
 413       if (!unsmob_grob_array (newval))
 414         {
 415           newval = Grob_array::make_array ();
 416           sc->set_object (sym, newval);
 417         }
 418
 419       Grob_array *new_array = unsmob_grob_array (newval);
 420       for (int k = 0; k < 2; k++)
 421         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 422           {
 423             Grob *substituted = substitute_grob (vec[j].grob_);
 424             if (substituted)
 425               new_array->add (substituted);
 426           }
 427
 428 #ifdef PARANOIA
 429       printf ("%d (%d), sp %d (%d)\n",
 430               item_indices [i].length (), item_index,
 431               spanner_indices[i].length (), len - spanner_index);
 432
 433       {
 434         SCM l1 = substitute_grob_list (grob_list);
 435         assert (scm_ilength (l1) == scm_ilength (newval));
 436       }
 437 #endif
 438     }
 439
 440   return true;
 441 }
 442
 443 /*
 444   Although the substitution can be written as
 445
 446   property_alist = do_substitution (other_property_alist),
 447
 448   we have a special function here: we want to invoke a special
 449   function for lists of grobs. These can be very long for large
 450   orchestral scores (eg. 1M elements). do_break_substitution () can
 451   recurse many levels, taking lots of stack space.
 452
 453   This becomes a problem if lily is linked against guile with
 454   pthreads. pthreads impose small limits on the stack size.
 455 */
 456 SCM
 457 substitute_object_alist (SCM alist, SCM dest)
 458 {
 459   SCM l = SCM_EOL;
 460   SCM *tail = &l;
 461   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 462     {
 463       SCM sym = scm_caar (s);
 464       SCM val = scm_cdar (s);
 465
 466       if (Grob_array *orig = unsmob_grob_array (val))
 467         {
 468           SCM handle = scm_assq (sym, dest);
 469           SCM newval
 470             = (scm_is_pair (handle))
 471               ? scm_cdr (handle)
 472               : Grob_array::make_array ();
 473
 474           Grob_array *new_arr = unsmob_grob_array (newval);
 475
 476           substitute_grob_array (orig, new_arr);
 477           val = newval;
 478         }
 479       else
 480         val = do_break_substitution (val);
 481
 482       if (val != SCM_UNDEFINED)
 483         {
 484           /*
 485             for ly:grob? properties, SCM_UNDEFINED could leak out
 486             through ly:grob-property
 487           */
 488           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 489           tail = SCM_CDRLOC (*tail);
 490         }
 491     }
 492   return l;
 493 }
 494
 495 void
 496 Spanner::substitute_one_mutable_property (SCM sym,
 497                                           SCM val)
 498 {
 499   Spanner *s = this;
 500
 501   bool fast_done = false;
 502   Grob_array *grob_array = unsmob_grob_array (val);
 503   if (grob_array)
 504     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 505
 506   if (!fast_done)
 507     for (vsize i = 0; i < s->broken_intos_.size (); i++)
 508       {
 509         Grob *sc = s->broken_intos_[i];
 510         System *l = sc->get_system ();
 511         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 512
 513         if (grob_array)
 514           {
 515             SCM newval = sc->internal_get_object (sym);
 516             if (!unsmob_grob_array (newval))
 517               {
 518                 newval = Grob_array::make_array ();
 519                 sc->set_object (sym, newval);
 520               }
 521             substitute_grob_array (grob_array, unsmob_grob_array (newval));
 522           }
 523         else
 524           {
 525             SCM newval = do_break_substitution (val);
 526             sc->set_object (sym, newval);
 527           }
 528       }
 529 }
 530
 531 void
 532 Grob::substitute_object_links (SCM crit, SCM orig)
 533 {
 534   set_break_subsititution (crit);
 535   object_alist_ = substitute_object_alist (orig, object_alist_);
 536 }