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