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