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