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