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