lily/break-substitution.cc

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