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
 267   /* Assumption: we have less than 32k paper columns. */
 268   short left_;
 269   short right_;
 270
 271   void set (Grob *g, Slice sr)
 272   {
 273     grob_ = g;
 274     /*
 275       duh, don't support scores with more than 32000 systems.
 276     */
 277     if (sr.is_empty ())
 278       {
 279         /*
 280           overflow if we don't treat this specially.
 281         */
 282         left_ = 1;
 283         right_ = -1;
 284       }
 285     else
 286       {
 287         left_ = sr[LEFT];
 288         right_ = sr[RIGHT];
 289       }
 290   }
 291   Substitution_entry ()
 292   {
 293     grob_ = 0;
 294     left_ = right_ = -2;
 295   }
 296
 297   int length () { return right_ - left_; }
 298   static int
 299   item_compare (void const *a, void const *b)
 300   {
 301     return ((Substitution_entry *)a)->left_
 302       - ((Substitution_entry *)b)->left_;
 303   }
 304
 305   static int
 306   spanner_compare (void const *a, void const *b)
 307   {
 308     return ((Substitution_entry *)a)->length ()
 309       - ((Substitution_entry *)b)->length ();
 310   }
 311 };
 312
 313 bool
 314 Spanner::fast_substitute_grob_array (SCM sym,
 315                                      Grob_array *grob_array)
 316 {
 317   int len = grob_array->size ();
 318
 319   if (grob_array->ordered ())
 320     return false;
 321
 322   if (len < 15)
 323     return false;
 324
 325   /*
 326     We store items on the left, spanners on the right in this vector.
 327
 328     FIXME: will not multithread.
 329   */
 330   static Substitution_entry *vec;
 331   static int vec_room;
 332
 333   if (vec_room < len)
 334     {
 335       vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
 336       vec_room = len;
 337     }
 338
 339   Slice system_range = spanner_system_range (this);
 340
 341   int spanner_index = len;
 342   int item_index = 0;
 343
 344   for (vsize i = 0; i < grob_array->size (); i++)
 345     {
 346       Grob *g = grob_array->grob (i);
 347
 348       Slice sr = grob_system_range (g);
 349       sr.intersect (system_range);
 350
 351       int idx = 0;
 352       if (dynamic_cast<Spanner *> (g))
 353         idx = --spanner_index;
 354       else if (dynamic_cast<Item *> (g))
 355         idx = item_index++;
 356
 357       vec[idx].set (g, sr);
 358     }
 359
 360   qsort (vec, item_index,
 361          sizeof (Substitution_entry), &Substitution_entry::item_compare);
 362
 363   vector<Slice> item_indices;
 364   vector<Slice> spanner_indices;
 365   for (int i = 0; i <= system_range.length (); i++)
 366     {
 367       item_indices.push_back (Slice (len, 0));
 368       spanner_indices.push_back (Slice (len, 0));
 369     }
 370
 371   vector<Slice> *arrs[]
 372     = {
 373     &item_indices, &spanner_indices
 374   };
 375
 376   for (int i = 0; i < item_index;i++)
 377     {
 378       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 379         item_indices[j - system_range[LEFT]].add_point (i);
 380     }
 381
 382   /*
 383     sorting vec[spanner_index.. len]
 384     is a waste of time -- the staff-spanners screw up the
 385     ordering, since they go across the entire score.
 386   */
 387   for (vsize i = spanner_indices.size (); i--;)
 388     spanner_indices[i] = Slice (spanner_index, len - 1);
 389
 390   assert (item_index <= spanner_index);
 391
 392   assert ((broken_intos_.size () == (vsize)system_range.length () + 1)
 393           || (broken_intos_.empty () && system_range.length () == 0));
 394   for (vsize i = 0; i < broken_intos_.size (); i++)
 395     {
 396       Grob *sc = broken_intos_[i];
 397       System *l = sc->get_system ();
 398       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 399
 400       SCM newval = sc->internal_get_object (sym);
 401       if (!unsmob_grob_array (newval))
 402         {
 403           newval = Grob_array::make_array ();
 404           sc->set_object (sym, newval);
 405         }
 406
 407       Grob_array *new_array = unsmob_grob_array (newval);
 408       for (int k = 0; k < 2;k++)
 409         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 410           {
 411             Grob *substituted = substitute_grob (vec[j].grob_);
 412             if (substituted)
 413               new_array->add (substituted);
 414           }
 415
 416 #ifdef PARANOIA
 417       printf ("%d (%d), sp %d (%d)\n",
 418               item_indices [i].length (), item_index,
 419               spanner_indices[i].length (), len -spanner_index);
 420
 421       {
 422         SCM l1 = substitute_grob_list (grob_list);
 423         assert (scm_ilength (l1) == scm_ilength (newval));
 424       }
 425 #endif
 426     }
 427
 428   return true;
 429 }
 430
 431 /*
 432   Although the substitution can be written as
 433
 434   property_alist = do_substitution (other_property_alist),
 435
 436   we have a special function here: we want to invoke a special
 437   function for lists of grobs. These can be very long for large
 438   orchestral scores (eg. 1M elements). do_break_substitution () can
 439   recurse many levels, taking lots of stack space.
 440
 441   This becomes a problem if lily is linked against guile with
 442   pthreads. pthreads impose small limits on the stack size.
 443 */
 444 SCM
 445 substitute_object_alist (SCM alist, SCM dest)
 446 {
 447   SCM l = SCM_EOL;
 448   SCM *tail = &l;
 449   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 450     {
 451       SCM sym = scm_caar (s);
 452       SCM val = scm_cdar (s);
 453
 454       if (Grob_array *orig = unsmob_grob_array (val))
 455         {
 456           SCM handle = scm_assq (sym, dest);
 457           SCM newval
 458             = (scm_is_pair (handle))
 459             ? scm_cdr (handle)
 460             : Grob_array::make_array ();
 461
 462           Grob_array *new_arr = unsmob_grob_array (newval);
 463
 464           substitute_grob_array (orig, new_arr);
 465           val = newval;
 466         }
 467       else
 468         val = do_break_substitution (val);
 469
 470       if (val != SCM_UNDEFINED)
 471         {
 472           /*
 473             for ly:grob? properties, SCM_UNDEFINED could leak out
 474             through ly:grob-property
 475           */
 476           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 477           tail = SCM_CDRLOC (*tail);
 478         }
 479     }
 480   return l;
 481 }
 482
 483 void
 484 Spanner::substitute_one_mutable_property (SCM sym,
 485                                           SCM val)
 486 {
 487   Spanner *s = this;
 488
 489   bool fast_done = false;
 490   Grob_array *grob_array = unsmob_grob_array (val);
 491   if (grob_array)
 492     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 493
 494   if (!fast_done)
 495     for (vsize i = 0; i < s->broken_intos_.size (); i++)
 496       {
 497         Grob *sc = s->broken_intos_[i];
 498         System *l = sc->get_system ();
 499         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 500
 501         if (grob_array)
 502           {
 503             SCM newval = sc->internal_get_object (sym);
 504             if (!unsmob_grob_array (newval))
 505               {
 506                 newval = Grob_array::make_array ();
 507                 sc->set_object (sym, newval);
 508               }
 509             substitute_grob_array (grob_array, unsmob_grob_array (newval));
 510           }
 511         else
 512           {
 513             SCM newval = do_break_substitution (val);
 514             sc->set_object (sym, newval);
 515           }
 516       }
 517 }
 518
 519 void
 520 Grob::substitute_object_links (SCM crit, SCM orig)
 521 {
 522   set_break_subsititution (crit);
 523   object_alist_ = substitute_object_alist (orig, object_alist_);
 524 }