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