lily/break-substitution.cc

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