lily/break-substitution.cc

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