]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/accidental-engraver.cc
Fix quadratic memory consumption for accidentals.
[lilypond.git] / lily / accidental-engraver.cc
index 910c62d282040d55021db4cca8703f4bcdd0520c..d74c8fb110ae89affdb4a222b4b7751b18c33709 100644 (file)
@@ -1,24 +1,36 @@
 /*
-  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--2007 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"
 #include "arpeggio.hh"
-#include "spanner.hh"
 #include "context.hh"
-#include "item.hh"
+#include "duration.hh"
 #include "engraver.hh"
 #include "international.hh"
+#include "item.hh"
 #include "pitch.hh"
 #include "protected-scm.hh"
 #include "rhythmic-head.hh"
 #include "separation-item.hh"
 #include "side-position-interface.hh"
+#include "spanner.hh"
 #include "stream-event.hh"
 #include "tie.hh"
 #include "warn.hh"
@@ -51,7 +63,6 @@ Accidental_entry::Accidental_entry ()
 
 class Accidental_engraver : public Engraver
 {
-  int get_bar_number ();
   void update_local_key_signature (SCM new_signature);
   void create_accidental (Accidental_entry *entry, bool, bool);
   Grob *make_standard_accidental (Stream_event *note, Grob *note_head, Engraver *trans, bool);
@@ -69,7 +80,7 @@ protected:
 
   void stop_translation_timestep ();
   void process_acknowledged ();
-  
+
   virtual void finalize ();
   virtual void derived_mark () const;
 
@@ -114,172 +125,78 @@ 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_cdr (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;
   bool need_restore;
 
-  Accidental_result () {
+  Accidental_result ()
+  {
     need_restore = need_acc = false;
   }
 
-  int score () const {
+  Accidental_result (bool restore, bool acc)
+  {
+    need_restore = restore;
+    need_acc = acc;
+  }
+
+  Accidental_result (SCM scm)
+  {
+    need_restore = to_boolean (scm_car (scm));
+    need_acc = to_boolean (scm_cdr (scm));
+  }
+
+  int score () const
+  {
     return need_acc ? 1 : 0
       + need_restore ? 1 : 0;
   }
 };
 
-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;
-}
-
 static
 Accidental_result
 check_pitch_against_rules (Pitch const &pitch, Context *origin,
-                                SCM rules, int bar_number)
+                          SCM rules, int bar_number, SCM measurepos)
 {
   Accidental_result result;
+  SCM pitch_scm = pitch.smobbed_copy ();
+  SCM barnum_scm = scm_from_int (bar_number);
+
   if (scm_is_pair (rules) && !scm_is_symbol (scm_car (rules)))
     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 (scm_is_pair (rule))
+      if (ly_is_procedure (rule))
        {
-         SCM type = scm_car (rule);
-         SCM laziness = scm_cdr (rule);
-         SCM localsig = origin->get_property ("localKeySignature");
-
-         bool same_octave
-           = (ly_symbol2scm ("same-octave") == type);
-         bool any_octave
-           = (ly_symbol2scm ("any-octave") == type);
+         SCM rule_result_scm = scm_call_4 (rule, origin->self_scm (),
+                                           pitch_scm, barnum_scm, measurepos);
+         Accidental_result rule_result (rule_result_scm);
 
-         if (same_octave || any_octave)
-           {
-             Accidental_result rule_result = check_pitch_against_signature
-               (localsig, pitch, bar_number, laziness, any_octave);
-
-             result.need_acc |= rule_result.need_acc;
-             result.need_restore |= rule_result.need_restore;
-           }
-         else
-           warning (_f ("ignoring unknown accidental rule: %s",
-                        ly_symbol2string (type).c_str ()));
+         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;
@@ -290,28 +207,13 @@ check_pitch_against_rules (Pitch const &pitch, Context *origin,
            origin = dad;
        }
       else
-       warning (_f ("pair or context-name expected for accidental rule, found %s",
-                    ly_scm2string (rule).c_str ()));
+       warning (_f ("procedure or context-name expected for accidental rule, found %s",
+                    print_scm_val (rule).c_str ()));
     }
 
   return result;
 }
 
-int
-Accidental_engraver::get_bar_number ()
-{
-  SCM barnum = get_property ("internalBarNumber");
-  SCM smp = get_property ("measurePosition");
-
-  int bn = robust_scm2int (barnum, 0);
-
-  Moment mp = robust_scm2moment (smp, Moment (0));
-  if (mp.main_part_ < Rational (0))
-    bn--;
-
-  return bn;
-}
-
 void
 Accidental_engraver::process_acknowledged ()
 {
@@ -319,7 +221,8 @@ Accidental_engraver::process_acknowledged ()
     {
       SCM accidental_rules = get_property ("autoAccidentals");
       SCM cautionary_rules = get_property ("autoCautionaries");
-      int barnum = get_bar_number ();
+      SCM measure_position = get_property ("measurePosition");
+      int barnum = measure_number (context());
 
       for (vsize i = 0; i < accidentals_.size (); i++)
        {
@@ -334,16 +237,16 @@ Accidental_engraver::process_acknowledged ()
          if (!pitch)
            continue;
 
-         Accidental_result acc = check_pitch_against_rules (*pitch, origin,
-                                                            accidental_rules, barnum);
-         Accidental_result caut = check_pitch_against_rules (*pitch, origin,
-                                                             cautionary_rules, barnum);
+         Accidental_result acc = check_pitch_against_rules (*pitch, origin, accidental_rules,
+                                                            barnum, measure_position);
+         Accidental_result caut = check_pitch_against_rules (*pitch, origin, cautionary_rules,
+                                                             barnum, measure_position);
 
          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;
            }
@@ -352,14 +255,18 @@ 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. */
-         if (acc.need_acc
-             && !note->in_event_class ("trill-span-event"))
-           create_accidental (&accidentals_[i], acc.need_restore, cautionary);
+         /*
+           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)
+               create_accidental (&accidentals_[i], acc.need_restore, cautionary);
 
-         if (forced || cautionary)
-           accidentals_[i].accidental_->set_property ("forced", SCM_BOOL_T);
+             if (forced || cautionary)
+               accidentals_[i].accidental_->set_property ("forced", SCM_BOOL_T);
+           }
        }
     }
 }
@@ -388,13 +295,11 @@ Accidental_engraver::create_accidental (Accidental_entry *entry,
 }
 
 Grob *
-Accidental_engraver::make_standard_accidental (Stream_event *note,
+Accidental_engraver::make_standard_accidental (Stream_event * /* note */,
                                               Grob *note_head,
                                               Engraver *trans,
                                               bool cautionary)
 {
-  (void)note;
-
   /*
     We construct the accidentals at the originating Voice
     level, so that we get the property settings for
@@ -427,17 +332,15 @@ 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;
 }
 
 Grob *
-Accidental_engraver::make_suggested_accidental (Stream_event *note,
+Accidental_engraver::make_suggested_accidental (Stream_event * /* note */,
                                                Grob *note_head,
                                                Engraver *trans)
 {
-  (void) note;
-
   Grob *a = trans->make_item ("AccidentalSuggestion", note_head->self_scm ());
 
   Side_position_interface::add_support (a, note_head);
@@ -475,11 +378,11 @@ Accidental_engraver::stop_translation_timestep ()
 
   for (vsize i = accidentals_.size (); i--;)
     {
-      int barnum = get_bar_number ();
-
       Stream_event *note = accidentals_[i].melodic_;
       Context *origin = accidentals_[i].origin_;
 
+      int barnum = measure_number (origin);
+
       Pitch *pitch = unsmob_pitch (note->get_property ("pitch"));
       if (!pitch)
        continue;
@@ -489,31 +392,35 @@ Accidental_engraver::stop_translation_timestep ()
       Rational a = pitch->get_alteration ();
       SCM key = scm_cons (scm_from_int (o), scm_from_int (n));
 
+      Moment end_mp = measure_position (context (),
+                                       unsmob_duration (note->get_property ("duration")));
+      SCM position = scm_cons (scm_from_int (barnum), end_mp.smobbed_copy ());
+
       SCM localsig = SCM_EOL;
       while (origin
             && origin->where_defined (ly_symbol2scm ("localKeySignature"), &localsig))
        {
          bool change = false;
-         if (accidentals_[i].tied_)
+         if (accidentals_[i].tied_
+             && !(to_boolean (accidentals_[i].accidental_->get_property ("forced"))))
            {
              /*
                Remember an alteration that is different both from
                that of the tied note and of the key signature.
              */
-             localsig = ly_assoc_prepend_x (localsig, key, scm_cons (ly_symbol2scm ("tied"),
-                                                                     scm_from_int (barnum)));
-
+             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),
-                                                    scm_from_int (barnum)));
+                                            scm_cons (ly_rational2scm (a),
+                                                      position));
              change = true;
            }
 
@@ -530,6 +437,7 @@ Accidental_engraver::stop_translation_timestep ()
 
   accidental_placement_ = 0;
   accidentals_.clear ();
+  note_columns_.clear ();
   left_objects_.clear ();
   right_objects_.clear ();
 }
@@ -598,24 +506,28 @@ ADD_ACKNOWLEDGER (Accidental_engraver, tie);
 ADD_ACKNOWLEDGER (Accidental_engraver, note_column);
 
 ADD_TRANSLATOR (Accidental_engraver,
-               
-               "Make accidentals.  "
-               "Catch note heads, ties and notices key-change events.  "
-               "This engraver usually lives at Staff level, but "
-               "reads the settings for Accidental at @code{Voice} level, "
-               "so you can @code{\\override} them at @code{Voice}. ",
-
-               /* grobs */
+               /* doc */
+               "Make accidentals."
+               "  Catch note heads, ties and notices key-change events."
+               "  This engraver usually lives at Staff level, but"
+               " reads the settings for Accidental at @code{Voice} level,"
+               " so you can @code{\\override} them at @code{Voice}.",
+
+               /* create */
                "Accidental "
                "AccidentalCautionary "
+               "AccidentalPlacement "
                "AccidentalSuggestion ",
 
-               /* props */
+               /* read */
                "autoAccidentals "
                "autoCautionaries "
                "internalBarNumber "
                "extraNatural "
                "harmonicAccidentals "
+               "keySignature "
                "localKeySignature ",
+
+               /* write */
                "localKeySignature "
                );