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--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include <cstdio>
  10 #include <cstdlib>
  11 using namespace std;
  12
  13 #include "grob-array.hh"
  14 #include "item.hh"
  15 #include "system.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   static Substitution_entry *vec;
 327   static int vec_room;
 328
 329   if (vec_room < len)
 330     {
 331       vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
 332       vec_room = len;
 333     }
 334
 335   Slice system_range = spanner_system_range (this);
 336
 337   int spanner_index = len;
 338   int item_index = 0;
 339
 340   for (vsize i = 0; i < grob_array->size (); i++)
 341     {
 342       Grob *g = grob_array->grob (i);
 343
 344       Slice sr = grob_system_range (g);
 345       sr.intersect (system_range);
 346
 347       int idx = 0;
 348       if (dynamic_cast<Spanner *> (g))
 349         idx = --spanner_index;
 350       else if (dynamic_cast<Item *> (g))
 351         idx = item_index++;
 352
 353       vec[idx].set (g, sr);
 354     }
 355
 356   qsort (vec, item_index,
 357          sizeof (Substitution_entry), &Substitution_entry::item_compare);
 358
 359   vector<Slice> item_indices;
 360   vector<Slice> spanner_indices;
 361   for (int i = 0; i <= system_range.length (); i++)
 362     {
 363       item_indices.push_back (Slice (len, 0));
 364       spanner_indices.push_back (Slice (len, 0));
 365     }
 366
 367   vector<Slice> *arrs[]
 368     = {
 369     &item_indices, &spanner_indices
 370   };
 371
 372   for (int i = 0; i < item_index;i++)
 373     {
 374       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 375         item_indices[j - system_range[LEFT]].add_point (i);
 376     }
 377
 378   /*
 379     sorting vec[spanner_index.. len]
 380     is a waste of time -- the staff-spanners screw up the
 381     ordering, since they go across the entire score.
 382   */
 383   for (vsize i = spanner_indices.size (); i--;)
 384     spanner_indices[i] = Slice (spanner_index, len - 1);
 385
 386   assert (item_index <= spanner_index);
 387
 388   assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
 389           || (broken_intos_.empty () && system_range.length () == 0));
 390   for (vsize i = 0; i < broken_intos_.size (); i++)
 391     {
 392       Grob *sc = broken_intos_[i];
 393       System *l = sc->get_system ();
 394       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 395
 396       SCM newval = sc->internal_get_object (sym);
 397       if (!unsmob_grob_array (newval))
 398         {
 399           newval = Grob_array::make_array ();
 400           sc->set_object (sym, newval);
 401         }
 402
 403       Grob_array *new_array = unsmob_grob_array (newval);
 404       for (int k = 0; k < 2;k++)
 405         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 406           {
 407             Grob *substituted = substitute_grob (vec[j].grob_);
 408             if (substituted)
 409               new_array->add (substituted);
 410           }
 411
 412 #ifdef PARANOIA
 413       printf ("%d (%d), sp %d (%d)\n",
 414               item_indices [i].length (), item_index,
 415               spanner_indices[i].length (), len -spanner_index);
 416
 417       {
 418         SCM l1 = substitute_grob_list (grob_list);
 419         assert (scm_ilength (l1) == scm_ilength (newval));
 420       }
 421 #endif
 422     }
 423
 424   return true;
 425 }
 426
 427 /*
 428   Although the substitution can be written as
 429
 430   property_alist = do_substitution (other_property_alist),
 431
 432   we have a special function here: we want to invoke a special
 433   function for lists of grobs. These can be very long for large
 434   orchestral scores (eg. 1M elements). do_break_substitution () can
 435   recurse many levels, taking lots of stack space.
 436
 437   This becomes a problem if lily is linked against guile with
 438   pthreads. pthreads impose small limits on the stack size.
 439 */
 440 SCM
 441 substitute_object_alist (SCM alist, SCM dest)
 442 {
 443   SCM l = SCM_EOL;
 444   SCM *tail = &l;
 445   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 446     {
 447       SCM sym = scm_caar (s);
 448       SCM val = scm_cdar (s);
 449
 450       if (Grob_array *orig = unsmob_grob_array (val))
 451         {
 452           SCM handle = scm_assq (sym, dest);
 453           SCM newval
 454             = (scm_is_pair (handle))
 455             ? scm_cdr (handle)
 456             : Grob_array::make_array ();
 457
 458           Grob_array *new_arr = unsmob_grob_array (newval);
 459
 460           substitute_grob_array (orig, new_arr);
 461           val = newval;
 462         }
 463       else
 464         val = do_break_substitution (val);
 465
 466       if (val != SCM_UNDEFINED)
 467         {
 468           /*
 469             for ly:grob? properties, SCM_UNDEFINED could leak out
 470             through ly:grob-property
 471           */
 472           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 473           tail = SCM_CDRLOC (*tail);
 474         }
 475     }
 476   return l;
 477 }
 478
 479 void
 480 Spanner::substitute_one_mutable_property (SCM sym,
 481                                           SCM val)
 482 {
 483   Spanner *s = this;
 484
 485   bool fast_done = false;
 486   Grob_array *grob_array = unsmob_grob_array (val);
 487   if (grob_array)
 488     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 489
 490   if (!fast_done)
 491     for (vsize i = 0; i < s->broken_intos_.size (); i++)
 492       {
 493         Grob *sc = s->broken_intos_[i];
 494         System *l = sc->get_system ();
 495         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 496
 497         if (grob_array)
 498           {
 499             SCM newval = sc->internal_get_object (sym);
 500             if (!unsmob_grob_array (newval))
 501               {
 502                 newval = Grob_array::make_array ();
 503                 sc->set_object (sym, newval);
 504               }
 505             substitute_grob_array (grob_array, unsmob_grob_array (newval));
 506           }
 507         else
 508           {
 509             SCM newval = do_break_substitution (val);
 510             sc->set_object (sym, newval);
 511           }
 512       }
 513 }
 514
 515 void
 516 Grob::substitute_object_links (SCM crit, SCM orig)
 517 {
 518   set_break_subsititution (crit);
 519   object_alist_ = substitute_object_alist (orig, object_alist_);
 520 }