lily/break-substitution.cc

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