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
  10 #include <cstdio>
  11 #include <cstdlib>
  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 SCM
  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) ? br->self_scm () : SCM_UNDEFINED;
  38         }
  39     }
  40   else
  41     {
  42       System *line
  43         = dynamic_cast<System *> (unsmob_grob (break_criterion));
  44       if (sc->get_system () != line)
  45         {
  46           sc = sc->find_broken_piece (line);
  47         }
  48
  49       /* now: !sc || (sc && sc->get_system () == line) */
  50       if (!sc)
  51         return SCM_UNDEFINED;
  52
  53       /* now: sc && sc->get_system () == line */
  54       if (!line)
  55         return sc->self_scm ();
  56
  57       /*
  58         We don't return SCM_UNDEFINED for
  59         suicided grobs, for two reasons
  60
  61         - it doesn't work (strange disappearing objects)
  62
  63         - it forces us to mark the parents of a grob, leading to
  64         a huge recursion in the GC routine.
  65       */
  66
  67       if (sc->common_refpoint (line, X_AXIS)
  68           && sc->common_refpoint (line, Y_AXIS))
  69         {
  70           return sc->self_scm ();
  71         }
  72       return SCM_UNDEFINED;
  73     }
  74
  75   return sc->self_scm ();
  76 }
  77
  78 /*
  79   Do break substitution in S, using CRITERION. Return new value.
  80   CRITERION is either a SMOB pointer to the desired line, or a number
  81   representing the break direction. Do not modify SRC.
  82
  83   It is rather tightly coded, since it takes a lot of time; it is
  84   one of the top functions in the profile.
  85
  86   We don't pass break_criterion as a parameter, since it is
  87   `constant', but takes up stack space.
  88
  89   It would be nice if we could do this in-place partially.  We now
  90   generate a lot of garbage.
  91 */
  92 SCM
  93 do_break_substitution (SCM src)
  94 {
  95  again:
  96
  97   if (unsmob_grob (src))
  98     return substitute_grob (unsmob_grob (src));
  99   else if (scm_is_vector (src))
 100     {
 101       int len = scm_c_vector_length (src);
 102       SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
 103       for (int i = 0; i < len; i++)
 104         {
 105           SCM si = scm_int2num (i);
 106           scm_vector_set_x (nv, si,
 107                             do_break_substitution (scm_vector_ref (src, si)));
 108         }
 109     }
 110   else if (scm_is_pair (src))
 111     {
 112       /*
 113         UGH! breaks on circular lists.
 114       */
 115       SCM newcar = do_break_substitution (scm_car (src));
 116       SCM oldcdr = scm_cdr (src);
 117
 118       if (newcar == SCM_UNDEFINED
 119           && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
 120         {
 121           /*
 122             This is tail-recursion, ie.
 123
 124             return do_break_substution (cdr);
 125
 126             We don't want to rely on the compiler to do this.  Without
 127             tail-recursion, this easily crashes with a stack overflow.  */
 128           src = oldcdr;
 129           goto again;
 130         }
 131
 132       return scm_cons (newcar, do_break_substitution (oldcdr));
 133     }
 134   else
 135     return src;
 136
 137   return src;
 138 }
 139
 140 /*
 141   Perform substitution on GROB_LIST using a constant amount of stack.
 142 */
 143 void
 144 substitute_grob_array (Grob_array *grob_arr, Grob_array * new_arr)
 145 {
 146   Link_array<Grob> &old_grobs (grob_arr->array_reference ());
 147   Link_array<Grob> *new_grobs (new_arr == grob_arr
 148                                ? new Link_array<Grob>
 149                                : &new_arr->array_reference ());
 150
 151   for (int i = 0; i < old_grobs.size (); i++)
 152     {
 153       Grob * orig = old_grobs[i];
 154       SCM new_grob = substitute_grob (orig);
 155       if (new_grob != SCM_UNDEFINED)
 156         {
 157           new_grobs->push (unsmob_grob (new_grob));
 158         }
 159     }
 160
 161   if (new_arr == grob_arr)
 162     {
 163       new_arr->set_array (*new_grobs);
 164     }
 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     {
 224       rv = Slice (st->get_rank (), st->get_rank ());
 225     }
 226   else
 227     {
 228       if (sp->broken_intos_.size ())
 229         rv = Slice (sp->broken_intos_[0]->get_system ()->get_rank (),
 230                     sp->broken_intos_.top ()->get_system ()->get_rank());
 231     }
 232   return rv;
 233 }
 234
 235 Slice
 236 item_system_range (Item *it)
 237 {
 238   if (System *st = it->get_system ())
 239     return Slice (st->get_rank (), st->get_rank ());
 240
 241   Slice sr;
 242   Direction d = LEFT;
 243   do
 244     {
 245       Item *bi = it->find_prebroken_piece (d);
 246       if (bi && bi->get_system ())
 247         sr.add_point (bi->get_system ()->get_rank ());
 248     }
 249   while (flip (&d) != LEFT);
 250
 251   return sr;
 252 }
 253
 254 Slice
 255 grob_system_range (Grob *g)
 256 {
 257   if (Spanner *s = dynamic_cast<Spanner *> (g))
 258     return spanner_system_range (s);
 259   else if (Item *it = dynamic_cast<Item *> (g))
 260     return item_system_range (it);
 261   else
 262     return Slice ();
 263 }
 264
 265 struct Substitution_entry
 266 {
 267   Grob *grob_;
 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   /*
 320     Only do this complicated thing for large sets. This has the added
 321     advantage that we won't screw up the ordering for elements in
 322     alignments (which typically don't have more than 10 grobs.)
 323   */
 324
 325   if (len < 300)
 326     return false;
 327
 328   /*
 329     We store items on the left, spanners on the right in this vector.
 330   */
 331   static Substitution_entry *vec;
 332   static int vec_room;
 333
 334   if (vec_room < len)
 335     {
 336       vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
 337       vec_room = len;
 338     }
 339
 340   Slice system_range = spanner_system_range (this);
 341
 342   int spanner_index = len;
 343   int item_index = 0;
 344
 345   for (int i = 0 ; i < grob_array->size (); i++)
 346     {
 347       Grob *g = grob_array->grob (i);
 348
 349       Slice sr = grob_system_range (g);
 350       sr.intersect (system_range);
 351
 352       int idx = 0;
 353       if (dynamic_cast<Spanner *> (g))
 354         {
 355           idx = --spanner_index;
 356         }
 357       else if (dynamic_cast<Item *> (g))
 358         {
 359           idx = item_index++;
 360         }
 361
 362       vec[idx].set (g, sr);
 363     }
 364
 365   qsort (vec, item_index,
 366          sizeof (Substitution_entry), &Substitution_entry::item_compare);
 367
 368   Array<Slice> item_indices;
 369   Array<Slice> spanner_indices;
 370   for (int i = 0; i <= system_range.length (); i++)
 371     {
 372       item_indices.push (Slice (len, 0));
 373       spanner_indices.push (Slice (len, 0));
 374     }
 375
 376   Array<Slice> *arrs[]
 377     = {
 378     &item_indices, &spanner_indices
 379   };
 380
 381   for (int i = 0; i < item_index;i++)
 382     {
 383       for (int j = vec[i].left_; j <= vec[i].right_; j++)
 384         {
 385           item_indices[j - system_range[LEFT]].add_point (i);
 386         }
 387     }
 388
 389   /*
 390     sorting vec[spanner_index.. len]
 391     is a waste of time -- the staff-spanners screw up the
 392     ordering, since they go across the entire score.
 393   */
 394   for (int i = spanner_indices.size (); i--;)
 395     spanner_indices[i] = Slice (spanner_index, len - 1);
 396
 397   assert (item_index <= spanner_index);
 398
 399   assert (broken_intos_.size () == system_range.length () + 1);
 400   for (int i = 0; i < broken_intos_.size (); i++)
 401     {
 402       Grob *sc = broken_intos_[i];
 403       System *l = sc->get_system ();
 404       set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 405
 406       SCM newval = sc->internal_get_object (sym);
 407       if (!unsmob_grob_array (newval))
 408         {
 409           newval = Grob_array::make_array ();
 410           sc->internal_set_object (sym, newval);
 411         }
 412
 413       Grob_array *new_array = unsmob_grob_array (newval);
 414       for (int k = 0; k < 2;k++)
 415         for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
 416           {
 417             SCM subs = substitute_grob (vec[j].grob_);
 418             if (subs != SCM_UNDEFINED)
 419               {
 420                 new_array->add (unsmob_grob (subs));
 421               }
 422           }
 423
 424 #ifdef PARANOIA
 425       printf ("%d (%d), sp %d (%d)\n",
 426               item_indices [i].length (), item_index,
 427               spanner_indices[i].length (), len -spanner_index);
 428
 429       {
 430         SCM l1 = substitute_grob_list (grob_list);
 431         assert (scm_ilength (l1) == scm_ilength (newval));
 432       }
 433 #endif
 434     }
 435
 436   return true;
 437 }
 438
 439 /*
 440   Although the substitution can be written as
 441
 442   property_alist = do_substitution (other_property_alist),
 443
 444   we have a special function here: we want to invoke a special
 445   function for lists of grobs. These can be very long for large
 446   orchestral scores (eg. 1M elements). do_break_substitution () can
 447   recurse many levels, taking lots of stack space.
 448
 449   This becomes a problem if lily is linked against guile with
 450   pthreads. pthreads impose small limits on the stack size.
 451 */
 452 SCM
 453 substitute_object_alist (SCM alist, SCM dest)
 454 {
 455   SCM l = SCM_EOL;
 456   SCM *tail = &l;
 457   for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
 458     {
 459       SCM sym = scm_caar (s);
 460       SCM val = scm_cdar (s);
 461
 462       if (Grob_array * orig = unsmob_grob_array (val))
 463         {
 464           SCM handle = scm_assq (sym, dest);
 465           SCM newval =
 466             (scm_is_pair (handle))
 467             ? scm_cdr (handle)
 468             : Grob_array::make_array ();
 469
 470           Grob_array *new_arr = unsmob_grob_array (newval);
 471
 472           substitute_grob_array (orig, new_arr);
 473           val = newval;
 474         }
 475       else
 476         val = do_break_substitution (val);
 477
 478       if (val != SCM_UNDEFINED)
 479         {
 480           /*
 481             for ly:grob? properties, SCM_UNDEFINED could leak out
 482             through ly:grob-property
 483           */
 484           *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
 485           tail = SCM_CDRLOC (*tail);
 486         }
 487     }
 488   return l;
 489 }
 490
 491 void
 492 Spanner::substitute_one_mutable_property (SCM sym,
 493                                           SCM val)
 494 {
 495   Spanner *s = this;
 496
 497   bool fast_done = false;
 498   Grob_array * grob_array = unsmob_grob_array (val);
 499   if (grob_array)
 500     fast_done = s->fast_substitute_grob_array (sym, grob_array);
 501
 502   if (!fast_done)
 503     for (int i = 0; i < s->broken_intos_.size (); i++)
 504       {
 505         Grob *sc = s->broken_intos_[i];
 506         System *l = sc->get_system ();
 507         set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
 508
 509         if (grob_array)
 510           {
 511             SCM newval = sc->internal_get_object (sym);
 512             if (!unsmob_grob_array (newval))
 513               {
 514                 newval = Grob_array::make_array ();
 515                 sc->internal_set_object  (sym, newval);
 516               }
 517             substitute_grob_array (grob_array, unsmob_grob_array (newval));
 518           }
 519         else
 520           {
 521             SCM newval = do_break_substitution (val);
 522             sc->internal_set_object (sym, newval);
 523           }
 524       }
 525 }
 526