]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/accidental-engraver.cc
Fix quadratic memory consumption for accidentals.
[lilypond.git] / lily / accidental-engraver.cc
index 7fcea1ccfe003a658927816bee7927b495258dce..d74c8fb110ae89affdb4a222b4b7751b18c33709 100644 (file)
@@ -1,10 +1,21 @@
 /*
-  accidental-engraver.cc -- implement Accidental_engraver
+  This file is part of LilyPond, the GNU music typesetter.
 
-  source file of the GNU LilyPond music typesetter
-
-  (c) 1997--2008 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  Copyright (C) 1997--2010 Han-Wen Nienhuys <hanwen@xs4all.nl>
   Modified 2001--2002 by Rune Zedeler <rz@daimi.au.dk>
+
+  LilyPond is free software: you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation, either version 3 of the License, or
+  (at your option) any later version.
+
+  LilyPond is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
 */
 
 #include "accidental-placement.hh"
@@ -69,7 +80,7 @@ protected:
 
   void stop_translation_timestep ();
   void process_acknowledged ();
-  
+
   virtual void finalize ();
   virtual void derived_mark () const;
 
@@ -114,59 +125,19 @@ Accidental_engraver::update_local_key_signature (SCM new_sig)
 
   Context *trans = context ()->get_parent_context ();
 
-  /* Reset parent contexts so that e.g. piano-accidentals won't remember old
-     cross-staff accidentals after key-sig-changes */
+  /*
+    Reset parent contexts so that e.g. piano-accidentals won't remember old
+    cross-staff accidentals after key-sig-changes.
+  */
 
   SCM val;
-  while (trans && trans->where_defined (ly_symbol2scm ("localKeySignature"), &val)==trans)
+  while (trans && trans->where_defined (ly_symbol2scm ("localKeySignature"), &val) == trans)
     {
       trans->set_property ("localKeySignature", ly_deep_copy (last_keysig_));
       trans = trans->get_parent_context ();
     }
 }
 
-
-/** Calculate the number of accidentals on basis of the current local key
-    sig (passed as argument)
-
-    * First check step+octave (taking into account barnumbers if necessary).
-
-    * Then check the global signature (only step).
-
-    Return number of accidentals (0, 1 or 2).  */
-
-static bool
-recent_enough (int bar_number, SCM alteration_def, SCM laziness)
-{
-  if (scm_is_number (alteration_def)
-      || laziness == SCM_BOOL_T)
-    return true;
-
-  return (bar_number <= scm_to_int (scm_cadr (alteration_def)) + scm_to_int (laziness));
-}
-
-static Rational
-extract_alteration (SCM alteration_def)
-{
-  if (scm_is_number (alteration_def))
-    return ly_scm2rational (alteration_def);
-  else if (scm_is_pair (alteration_def))
-    return ly_scm2rational (scm_car (alteration_def));
-  else if (alteration_def == SCM_BOOL_F)
-    return Rational (0);
-  else
-    assert (0);
-  return Rational (0);
-}
-
-bool
-is_tied (SCM alteration_def)
-{
-  SCM tied = ly_symbol2scm ("tied");
-  return (alteration_def == tied
-         || (scm_is_pair (alteration_def) && scm_car (alteration_def) == tied));
-}
-
 struct Accidental_result
 {
   bool need_acc;
@@ -196,95 +167,6 @@ struct Accidental_result
   }
 };
 
-Accidental_result
-check_pitch_against_signature (SCM key_signature, Pitch const &pitch,
-                              int bar_number, SCM laziness, bool ignore_octave)
-{
-  Accidental_result result;
-  int n = pitch.get_notename ();
-  int o = pitch.get_octave ();
-
-  SCM previous_alteration = SCM_BOOL_F;
-
-  SCM from_same_octave = ly_assoc_get (scm_cons (scm_from_int (o),
-                                                scm_from_int (n)), key_signature, SCM_BOOL_F);
-  SCM from_key_signature = ly_assoc_get (scm_from_int (n), key_signature, SCM_BOOL_F);
-  SCM from_other_octaves = SCM_BOOL_F;
-  for (SCM s = key_signature; scm_is_pair (s); s = scm_cdr (s))
-    {
-      SCM entry = scm_car (s);
-      if (scm_is_pair (scm_car (entry))
-         && scm_cdar (entry) == scm_from_int (n))
-       {
-         from_other_octaves = scm_cdr (entry);
-         break;
-       }
-    }
-
-  if (!ignore_octave
-      && from_same_octave != SCM_BOOL_F
-      && recent_enough (bar_number, from_same_octave, laziness))
-    previous_alteration = from_same_octave;
-  else if (ignore_octave
-          && from_other_octaves != SCM_BOOL_F
-          && recent_enough (bar_number, from_other_octaves, laziness))
-    previous_alteration = from_other_octaves;
-  else if (from_key_signature != SCM_BOOL_F)
-    previous_alteration = from_key_signature;
-
-  if (is_tied (previous_alteration))
-    {
-      result.need_acc = true;
-    }
-  else
-    {
-      Rational prev = extract_alteration (previous_alteration);
-      Rational alter = pitch.get_alteration ();
-
-      if (alter != prev)
-        {
-         result.need_acc = true;
-         if (alter.sign ()
-             && (alter.abs () < prev.abs ()
-                 || (prev * alter).sign () < 0))
-           result.need_restore = true;
-       }
-    }
-
-  return result;
-}
-
-// TODO: consider moving check_pitch_against_signature to SCM (in which case
-// we can delete this function).
-LY_DEFINE (ly_find_accidentals_simple, "ly:find-accidentals-simple", 5, 0, 0,
-          (SCM keysig, SCM pitch_scm, SCM barnum, SCM laziness, SCM octaveness ),
-          "Checks the need for an accidental and a @q{restore} accidental against a"
-          " key signature.  The @var{laziness} is the number of bars for which reminder"
-          " accidentals are used (ie. if @var{laziness} is zero, we only cancel accidentals"
-          " in the same bar; if @var{laziness} is three, we cancel accidentals up to three"
-          " bars after they first appear.  @var{octaveness} is either"
-          " @code{'same-octave} or @code{'any-octave} and it specifies whether"
-          " accidentals should be canceled in different octaves.")
-{
-  LY_ASSERT_TYPE (unsmob_pitch, pitch_scm, 2);
-  LY_ASSERT_TYPE (scm_is_integer, barnum, 3);
-  LY_ASSERT_TYPE (ly_is_symbol, octaveness, 5);
-
-  bool symbol_ok = octaveness == ly_symbol2scm ("any-octave") ||
-    octaveness == ly_symbol2scm ("same-octave");
-
-  SCM_ASSERT_TYPE (symbol_ok, octaveness, SCM_ARG5, __FUNCTION__, "'any-octave or 'same-octave");
-
-  Pitch *pitch = unsmob_pitch (pitch_scm);
-
-  int bar_number = scm_to_int (barnum);
-  bool ignore_octave = ly_symbol2scm ("any-octave") == octaveness; 
-  Accidental_result result = check_pitch_against_signature (keysig, *pitch, bar_number,
-                                                           laziness, ignore_octave);
-
-  return scm_cons (scm_from_bool (result.need_restore), scm_from_bool (result.need_acc));
-}
-
 static
 Accidental_result
 check_pitch_against_rules (Pitch const &pitch, Context *origin,
@@ -298,23 +180,23 @@ check_pitch_against_rules (Pitch const &pitch, Context *origin,
     warning (_f ("accidental typesetting list must begin with context-name: %s",
                 ly_scm2string (scm_car (rules)).c_str ()));
 
-  for (; scm_is_pair (rules) && origin;
-       rules = scm_cdr (rules))
+  for (; scm_is_pair (rules) && origin; rules = scm_cdr (rules))
     {
       SCM rule = scm_car (rules);
       if (ly_is_procedure (rule))
        {
          SCM rule_result_scm = scm_call_4 (rule, origin->self_scm (),
                                            pitch_scm, barnum_scm, measurepos);
-
          Accidental_result rule_result (rule_result_scm);
 
          result.need_acc |= rule_result.need_acc;
          result.need_restore |= rule_result.need_restore;
        }
 
-      /* if symbol then it is a context name.  Scan parent contexts to
-        find it. */
+      /*
+       If symbol then it is a context name.  Scan parent contexts to
+       find it.
+      */
       else if (scm_is_symbol (rule))
        {
          Context *dad = origin;
@@ -363,8 +245,8 @@ Accidental_engraver::process_acknowledged ()
          bool cautionary = to_boolean (note->get_property ("cautionary"));
          if (caut.score () > acc.score ())
            {
-             acc.need_acc |= caut.need_acc; 
-             acc.need_restore |= caut.need_restore; 
+             acc.need_acc |= caut.need_acc;
+             acc.need_restore |= caut.need_restore;
 
              cautionary = true;
            }
@@ -373,11 +255,13 @@ Accidental_engraver::process_acknowledged ()
          if (!acc.need_acc && forced)
            acc.need_acc = true;
 
-         /* Cannot look for ties: it's not guaranteed that they reach
-            us before the notes. */
+         /*
+           Cannot look for ties: it's not guaranteed that they reach
+           us before the notes.
+         */
          if (!note->in_event_class ("trill-span-event"))
            {
-             if (acc.need_acc)       
+             if (acc.need_acc)
                create_accidental (&accidentals_[i], acc.need_restore, cautionary);
 
              if (forced || cautionary)
@@ -448,7 +332,7 @@ Accidental_engraver::make_standard_accidental (Stream_event * /* note */,
   Accidental_placement::add_accidental (accidental_placement_, a);
 
   note_head->set_object ("accidental-grob", a->self_scm ());
-  
+
   return a;
 }
 
@@ -493,7 +377,7 @@ Accidental_engraver::stop_translation_timestep ()
     }
 
   for (vsize i = accidentals_.size (); i--;)
-    {      
+    {
       Stream_event *note = accidentals_[i].melodic_;
       Context *origin = accidentals_[i].origin_;
 
@@ -526,14 +410,13 @@ Accidental_engraver::stop_translation_timestep ()
              */
              localsig = ly_assoc_prepend_x (localsig, key,scm_cons (ly_symbol2scm ("tied"),
                                                                     position));
-
              change = true;
            }
          else
            {
              /*
-               not really really correct if there are more than one
-               noteheads with the same notename.
+               not really correct if there is more than one
+               note head with the same notename.
              */
              localsig = ly_assoc_prepend_x (localsig, key,
                                             scm_cons (ly_rational2scm (a),
@@ -554,6 +437,7 @@ Accidental_engraver::stop_translation_timestep ()
 
   accidental_placement_ = 0;
   accidentals_.clear ();
+  note_columns_.clear ();
   left_objects_.clear ();
   right_objects_.clear ();
 }