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