music21/alpha/analysis/
hasher.rs

1//! Notes as tuples of what they are -- pitch, length, offset -- to compare
2//! two streams by: music21's `alpha.analysis.hasher`.
3
4use crate::{
5    defaults::FloatType,
6    error::Result,
7    interval::Interval,
8    pitch::Pitch,
9    stream::{Stream, StreamElement, StreamKind},
10};
11
12/// One part of a note's hash.
13#[derive(Clone, Debug, PartialEq)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub enum HashValue {
16    /// A whole number: a MIDI pitch, an octave, an interval class.
17    Integer(i64),
18    /// A length or an offset.
19    Float(FloatType),
20    /// A name: a pitch's, or a chord's normal order or prime form.
21    Text(String),
22    /// Nothing, as music21 hashes what it cannot say.
23    None,
24}
25
26/// Which element a hash was made from: its place among the elements of the
27/// stream music21's `recurse` walks, and for a note of a chord hashed as
28/// notes, which note.
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
31pub struct HashReference {
32    /// The element's place in [`Stream::recurse`].
33    pub element: usize,
34    /// The note of a chord, where a chord is hashed note by note.
35    pub component: Option<usize>,
36}
37
38/// A note's hash: the values the hasher says, named, and what it was made
39/// from where asked: music21's `NoteHash` and `NoteHashWithReference`.
40#[derive(Clone, Debug, PartialEq)]
41#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
42pub struct NoteHash {
43    /// What each value is: `Pitch`, `Duration`, `Offset` and the rest.
44    pub keys: Vec<String>,
45    /// The values, one a key.
46    pub values: Vec<HashValue>,
47    /// What the hash was made from, where the hasher includes it.
48    pub reference: Option<HashReference>,
49}
50
51/// What a hasher hashes of each note, rest and chord: music21's `Hasher`.
52///
53/// By default a note is its MIDI pitch, its length and its offset, each
54/// rounded to a 32nd of a quarter, and a chord is hashed note by note.
55#[derive(Clone, Debug, PartialEq, Eq)]
56pub struct Hasher {
57    /// Whether each hash says what it was made from.
58    pub include_reference: bool,
59    /// Whether a note's pitch is hashed.
60    pub hash_pitch: bool,
61    /// Whether the pitch is its MIDI number rather than its name.
62    pub hash_midi: bool,
63    /// Whether a named pitch leaves out its octave: music21's
64    /// `hashNoteNameOctave`.
65    pub hash_note_name_octave: bool,
66    /// Whether the octave is hashed.
67    pub hash_octave: bool,
68    /// Whether the length is hashed.
69    pub hash_duration: bool,
70    /// Whether lengths and offsets are rounded to `granularity`.
71    pub round_duration_and_offset: bool,
72    /// Whether the offset in the element's own measure or voice is hashed.
73    pub hash_offset: bool,
74    /// How many parts of a quarter lengths and offsets are rounded to.
75    pub granularity: u32,
76    /// Whether the interval class from the note before in the same part is
77    /// hashed; a part's first note has none.
78    pub hash_interval_from_last_note: bool,
79    /// Whether whether a note is altered is hashed: music21 hashes nothing
80    /// for it yet, so the value is always nothing.
81    pub hash_is_accidental: bool,
82    /// Whether ties are hashed: music21 does not use it.
83    pub hash_is_tied: bool,
84    /// Whether a chord is hashed note by note.
85    pub hash_chords_as_notes: bool,
86    /// Whether a chord is hashed as one.
87    pub hash_chords_as_chords: bool,
88    /// Whether a chord's normal order is hashed, where chords are hashed
89    /// as chords.
90    pub hash_normal_order_string: bool,
91    /// Whether a chord's prime form is hashed, where chords are hashed as
92    /// chords.
93    pub hash_prime_form_string: bool,
94}
95
96impl Default for Hasher {
97    fn default() -> Self {
98        Self {
99            include_reference: false,
100            hash_pitch: true,
101            hash_midi: true,
102            hash_note_name_octave: false,
103            hash_octave: false,
104            hash_duration: true,
105            round_duration_and_offset: true,
106            hash_offset: true,
107            granularity: 32,
108            hash_interval_from_last_note: false,
109            hash_is_accidental: false,
110            hash_is_tied: false,
111            hash_chords_as_notes: true,
112            hash_chords_as_chords: false,
113            hash_normal_order_string: false,
114            hash_prime_form_string: false,
115        }
116    }
117}
118
119/// What is being hashed: a note or rest standing alone, a note of a chord,
120/// or a chord as one.
121enum Hashed<'a> {
122    Alone(&'a StreamElement),
123    InChord(&'a crate::note::Note, &'a crate::chord::Chord),
124    Chord(&'a crate::chord::Chord),
125}
126
127impl Hasher {
128    /// The names of the values each hash holds, in order: music21's
129    /// `tupleList`.
130    pub fn tuple_list(&self) -> Vec<&'static str> {
131        let mut keys = Vec::new();
132        if self.hash_pitch {
133            keys.push("Pitch");
134            if self.hash_is_accidental {
135                keys.push("IsAccidental");
136            }
137        }
138        if self.hash_octave {
139            keys.push("Octave");
140        }
141        if !self.hash_chords_as_notes && self.hash_chords_as_chords {
142            if self.hash_normal_order_string {
143                keys.push("NormalOrderString");
144            }
145            if self.hash_prime_form_string {
146                keys.push("PrimeFormString");
147            }
148        }
149        if self.hash_duration {
150            keys.push("Duration");
151        }
152        if self.hash_offset {
153            keys.push("Offset");
154        }
155        if self.hash_interval_from_last_note {
156            keys.push("IntervalFromLastNote");
157        }
158        keys
159    }
160
161    /// A length or offset rounded to the hasher's granularity, a half to
162    /// the even, as Python rounds.
163    fn rounded(&self, value: FloatType) -> FloatType {
164        let granularity = FloatType::from(self.granularity);
165        (value * granularity).round_ties_even() / granularity
166    }
167
168    /// Every note, rest and chord of a stream, hashed in the order music21's
169    /// `recurse` walks them: music21's `hashStream`. A chord is hashed note
170    /// by note, as one, or not at all as the hasher says. Offsets are each
171    /// element's own in its measure or voice.
172    ///
173    /// music21 also rounds each element's own length and offset in the
174    /// stream as it hashes them; the stream here is left as it is.
175    ///
176    /// # Errors
177    ///
178    /// An interval from the note before that cannot be measured, a chord
179    /// symbol whose notes cannot be worked out, or octaves asked of chords
180    /// hashed as chords, which music21 cannot hash.
181    pub fn hash_stream(&self, stream: &Stream) -> Result<Vec<NoteHash>> {
182        let keys = self.tuple_list();
183        let walked = recurse_with_local_offsets(stream);
184        let mut hashes = Vec::new();
185        let previous_notes = if self.hash_interval_from_last_note {
186            notes_before(stream)
187        } else {
188            vec![None; walked.len()]
189        };
190        for (index, (offset, element)) in walked.iter().enumerate() {
191            match element {
192                StreamElement::Note(_) => {
193                    let values = self.values(
194                        &keys,
195                        Hashed::Alone(element),
196                        *offset,
197                        previous_notes[index].as_ref(),
198                    )?;
199                    hashes.push(self.hash(&keys, values, index, None));
200                }
201                StreamElement::Rest(_) => {
202                    let values = self.values(
203                        &keys,
204                        Hashed::Alone(element),
205                        *offset,
206                        previous_notes[index].as_ref(),
207                    )?;
208                    hashes.push(self.hash(&keys, values, index, None));
209                }
210                StreamElement::ChordSymbol(symbol) => {
211                    // music21 hashes a chord symbol as the chord it stands
212                    // for, its notes each a quarter.
213                    let mut chord = crate::chord::Chord::new(symbol.pitches()?.as_slice())?;
214                    chord.set_duration(symbol.duration().clone());
215                    self.hash_chord(&keys, &chord, *offset, index, &mut hashes)?;
216                }
217                StreamElement::Chord(chord) => {
218                    self.hash_chord(&keys, chord, *offset, index, &mut hashes)?;
219                }
220                _ => {}
221            }
222        }
223        Ok(hashes)
224    }
225
226    fn hash_chord(
227        &self,
228        keys: &[&'static str],
229        chord: &crate::chord::Chord,
230        offset: FloatType,
231        index: usize,
232        hashes: &mut Vec<NoteHash>,
233    ) -> Result<()> {
234        if self.hash_chords_as_notes {
235            for (component, note) in chord.notes().iter().enumerate() {
236                let values = self.values(keys, Hashed::InChord(note, chord), offset, None)?;
237                hashes.push(self.hash(keys, values, index, Some(component)));
238            }
239        } else if self.hash_chords_as_chords {
240            let values = self.values(keys, Hashed::Chord(chord), offset, None)?;
241            hashes.push(self.hash(keys, values, index, None));
242        }
243        Ok(())
244    }
245
246    fn hash(
247        &self,
248        keys: &[&'static str],
249        values: Vec<HashValue>,
250        element: usize,
251        component: Option<usize>,
252    ) -> NoteHash {
253        NoteHash {
254            keys: keys.iter().map(|key| (*key).to_string()).collect(),
255            values,
256            reference: self
257                .include_reference
258                .then_some(HashReference { element, component }),
259        }
260    }
261
262    /// One named value of a hash, read on its own: what music21's own
263    /// `_hashMIDIPitchName`, `_hashRoundedDuration` and the rest answer,
264    /// each of which its own examples ask for one element at a time.
265    ///
266    /// The element is the note or rest hashed, with the chord it stands in
267    /// where it is a chord's note, or no element and the chord itself
268    /// where a chord is hashed as one -- which is how music21 calls them
269    /// (`_hashDuration(n, thisChord=c)`).
270    ///
271    /// # Errors
272    ///
273    /// As [`Self::hash_stream`], and a name no hash holds.
274    pub fn hash_value(
275        &self,
276        key: &str,
277        element: Option<&StreamElement>,
278        chord: Option<&crate::chord::Chord>,
279        offset: FloatType,
280        previous_note: Option<&Pitch>,
281    ) -> Result<HashValue> {
282        let named: &'static str = match key {
283            "Pitch" => "Pitch",
284            "Octave" => "Octave",
285            "Duration" => "Duration",
286            "Offset" => "Offset",
287            "IntervalFromLastNote" => "IntervalFromLastNote",
288            "IsAccidental" => "IsAccidental",
289            "NormalOrderString" => "NormalOrderString",
290            "PrimeFormString" => "PrimeFormString",
291            _ => return Err(crate::Error::Analysis(format!("no hash holds a {key}"))),
292        };
293        // music21's `_hashOctave` answers less one for a chord handed to it
294        // as the element, where chords are hashed as chords, rather than
295        // reading an octave off it -- and raises where it is handed no
296        // element at all, which is what hashing a whole stream that way
297        // does.
298        if named == "Octave"
299            && self.hash_chords_as_chords
300            && matches!(element, Some(StreamElement::Chord(_)))
301        {
302            return Ok(HashValue::Integer(-1));
303        }
304        let hashed = match (element, chord) {
305            (Some(StreamElement::Note(note)), Some(chord)) => Hashed::InChord(note, chord),
306            (Some(element), _) => Hashed::Alone(element),
307            (None, Some(chord)) => Hashed::Chord(chord),
308            (None, None) => {
309                return Err(crate::Error::Analysis(
310                    "nothing was given to hash".to_string(),
311                ));
312            }
313        };
314        let values = self.values(&[named], hashed, offset, previous_note)?;
315        values
316            .into_iter()
317            .next()
318            .ok_or_else(|| crate::Error::Analysis(format!("no hash holds a {key}")))
319    }
320
321    fn values(
322        &self,
323        keys: &[&'static str],
324        hashed: Hashed<'_>,
325        offset: FloatType,
326        previous_note: Option<&Pitch>,
327    ) -> Result<Vec<HashValue>> {
328        let as_chord =
329            matches!(hashed, Hashed::InChord(..) | Hashed::Chord(_)) && self.hash_chords_as_chords;
330        let pitch: Option<&Pitch> = match &hashed {
331            Hashed::Alone(StreamElement::Note(note)) => Some(note.pitch()),
332            Hashed::InChord(note, _) => Some(note.pitch()),
333            _ => None,
334        };
335        let is_rest = matches!(hashed, Hashed::Alone(StreamElement::Rest(_)));
336        let chord = match &hashed {
337            Hashed::InChord(_, chord) | Hashed::Chord(chord) => Some(*chord),
338            _ => None,
339        };
340        let length = match &hashed {
341            Hashed::Alone(element) => element.quarter_length(),
342            Hashed::InChord(_, chord) | Hashed::Chord(chord) => chord
343                .duration()
344                .map_or(1.0, crate::duration::Duration::quarter_length),
345        };
346        let mut values = Vec::new();
347        for key in keys {
348            values.push(match *key {
349                "Pitch" => {
350                    if as_chord {
351                        if self.hash_midi {
352                            HashValue::Integer(1)
353                        } else {
354                            HashValue::Text("z".to_string())
355                        }
356                    } else if is_rest {
357                        if self.hash_midi {
358                            HashValue::Integer(0)
359                        } else {
360                            HashValue::Text("r".to_string())
361                        }
362                    } else if let Some(pitch) = pitch {
363                        let name = pitch_str(pitch);
364                        if self.hash_midi {
365                            HashValue::Integer(i64::from(pitch.midi()))
366                        } else if self.hash_note_name_octave {
367                            let mut name = name;
368                            name.pop();
369                            HashValue::Text(name)
370                        } else {
371                            HashValue::Text(name)
372                        }
373                    } else {
374                        HashValue::None
375                    }
376                }
377                "IsAccidental" => HashValue::None,
378                "Octave" => {
379                    if matches!(hashed, Hashed::Chord(_)) {
380                        // music21 hands its octave hash nothing for a chord
381                        // hashed as one, and asks nothing for its octave.
382                        return Err(crate::error::Error::Analysis(
383                            "a chord hashed whole has no octave to hash".to_string(),
384                        ));
385                    }
386                    if is_rest {
387                        HashValue::Integer(-1)
388                    } else {
389                        pitch
390                            .and_then(Pitch::octave)
391                            .map_or(HashValue::None, |octave| {
392                                HashValue::Integer(i64::from(octave))
393                            })
394                    }
395                }
396                "NormalOrderString" => match chord {
397                    Some(chord) => HashValue::Text(chord.normal_order_string()),
398                    None => HashValue::Text("<>".to_string()),
399                },
400                "PrimeFormString" => match chord {
401                    Some(chord) => HashValue::Text(chord.prime_form_string()),
402                    None => HashValue::Text("<>".to_string()),
403                },
404                "Duration" => HashValue::Float(if self.round_duration_and_offset {
405                    self.rounded(length)
406                } else {
407                    length
408                }),
409                "Offset" => HashValue::Float(if self.round_duration_and_offset {
410                    self.rounded(offset)
411                } else {
412                    offset
413                }),
414                "IntervalFromLastNote" => match (&hashed, previous_note) {
415                    (Hashed::Alone(StreamElement::Note(note)), Some(previous)) => {
416                        let interval = Interval::between_pitches(previous, note.pitch())?;
417                        HashValue::Integer(i64::from(interval.interval_class()))
418                    }
419                    _ => HashValue::None,
420                },
421                _ => HashValue::None,
422            });
423        }
424        Ok(values)
425    }
426}
427
428/// A pitch as music21's `str` writes it: its letter, its accidental in
429/// music21's spelling -- a flat as `-`, a natural as nothing -- and its
430/// octave.
431fn pitch_str(pitch: &Pitch) -> String {
432    let modifier = match pitch
433        .written_accidental()
434        .map(|accidental| accidental.name())
435    {
436        None | Some("natural") => String::new(),
437        Some("sharp") => "#".to_string(),
438        Some("double-sharp") => "##".to_string(),
439        Some("triple-sharp") => "###".to_string(),
440        Some("quadruple-sharp") => "####".to_string(),
441        Some("flat") => "-".to_string(),
442        Some("double-flat") => "--".to_string(),
443        Some("triple-flat") => "---".to_string(),
444        Some("quadruple-flat") => "----".to_string(),
445        Some("half-sharp") => "~".to_string(),
446        Some("one-and-a-half-sharp") => "#~".to_string(),
447        Some("half-flat") => "`".to_string(),
448        Some("one-and-a-half-flat") => "-`".to_string(),
449        Some(_) => pitch.accidental().modifier().to_string(),
450    };
451    let octave = pitch
452        .octave()
453        .map(|octave| octave.to_string())
454        .unwrap_or_default();
455    format!("{}{modifier}{octave}", pitch.step().as_char())
456}
457
458/// Where an element of a stream's walk stands: the stream holding it, the
459/// part it is in, and how a flattened part sorts it.
460struct Placed {
461    container: Option<usize>,
462    part: Option<usize>,
463    offset: FloatType,
464    sort_order: i32,
465    grace: bool,
466    pitch: Option<Pitch>,
467    leaf: bool,
468}
469
470/// The note before each note of a stream's walk, as music21's
471/// `previous('Note')` finds it: the last note before it in its own measure
472/// or voice, and failing that the last before it in its part, flattened and
473/// sorted by offset, class and grace notes first. A part's first note has
474/// none.
475fn notes_before(stream: &Stream) -> Vec<Option<Pitch>> {
476    fn walk(
477        stream: &Stream,
478        container: Option<usize>,
479        part: Option<usize>,
480        base: FloatType,
481        out: &mut Vec<Placed>,
482    ) {
483        for event in stream.events() {
484            let element = event.element();
485            let offset = crate::makenotation::op_frac(base + event.offset());
486            let index = out.len();
487            out.push(Placed {
488                container,
489                part,
490                offset,
491                sort_order: element.class_sort_order(),
492                grace: element
493                    .duration()
494                    .is_some_and(crate::duration::Duration::is_grace),
495                pitch: match element {
496                    StreamElement::Note(note) => Some(note.pitch().clone()),
497                    _ => None,
498                },
499                leaf: !matches!(element, StreamElement::Stream(_)),
500            });
501            if let StreamElement::Stream(inner) = element {
502                let inner_part = if matches!(inner.kind(), StreamKind::Part | StreamKind::PartStaff)
503                {
504                    Some(index)
505                } else {
506                    part
507                };
508                walk(inner, Some(index), inner_part, offset, out);
509            }
510        }
511    }
512    let mut placed = Vec::new();
513    walk(stream, None, None, 0.0, &mut placed);
514    // Each part's leaves in flattened order.
515    let mut flattened: std::collections::BTreeMap<Option<usize>, Vec<usize>> =
516        std::collections::BTreeMap::new();
517    for (index, item) in placed.iter().enumerate() {
518        if item.leaf {
519            flattened.entry(item.part).or_default().push(index);
520        }
521    }
522    let mut place_in_part = vec![0; placed.len()];
523    for leaves in flattened.values_mut() {
524        leaves.sort_by(|&a, &b| {
525            placed[a]
526                .offset
527                .total_cmp(&placed[b].offset)
528                .then(placed[a].sort_order.cmp(&placed[b].sort_order))
529                .then(placed[b].grace.cmp(&placed[a].grace))
530        });
531        for (place, &index) in leaves.iter().enumerate() {
532            place_in_part[index] = place;
533        }
534    }
535    // The last note met in each measure or voice, walking forward.
536    let mut last_in: std::collections::HashMap<Option<usize>, usize> =
537        std::collections::HashMap::new();
538    let mut out = vec![None; placed.len()];
539    for index in 0..placed.len() {
540        if placed[index].pitch.is_none() {
541            continue;
542        }
543        let container = placed[index].container;
544        out[index] = match last_in.get(&container) {
545            Some(&before) => placed[before].pitch.clone(),
546            None => flattened[&placed[index].part][..place_in_part[index]]
547                .iter()
548                .rev()
549                .find_map(|&before| placed[before].pitch.clone()),
550        };
551        last_in.insert(container, index);
552    }
553    out
554}
555
556/// Every element of a stream in the order music21's `recurse` walks it,
557/// each with its offset in the stream holding it.
558fn recurse_with_local_offsets(stream: &Stream) -> Vec<(FloatType, StreamElement)> {
559    fn walk(stream: &Stream, out: &mut Vec<(FloatType, StreamElement)>) {
560        for event in stream.events() {
561            out.push((event.offset(), event.element().clone()));
562            if let StreamElement::Stream(inner) = event.element() {
563                walk(inner, out);
564            }
565        }
566    }
567    let mut out = Vec::new();
568    walk(stream, &mut out);
569    out
570}
571
572#[cfg(test)]
573mod tests {
574    use super::*;
575    use crate::{chord::Chord, duration::Duration, note::Note, rest::Rest};
576
577    #[test]
578    fn notes_chords_and_rests_are_hashed_as_music21_hashes_them() -> Result<()> {
579        // music21's testBasicHash.
580        let mut stream = Stream::new();
581        stream.push(Note::from_name("C4")?.with_duration(Duration::new(2.0)?));
582        stream.push(Note::from_name("F#4")?);
583        stream.push(Note::from_name("B-2")?);
584        stream.push(Chord::new("C4 G4 E-5")?.with_duration(Duration::new(2.0)?));
585        stream.push(Rest::new(Duration::new(1.5)?));
586        let hashes: Vec<Vec<HashValue>> = Hasher::default()
587            .hash_stream(&stream)?
588            .into_iter()
589            .map(|hash| hash.values)
590            .collect();
591        let expected = [
592            (60, 2.0, 0.0),
593            (66, 1.0, 2.0),
594            (46, 1.0, 3.0),
595            (60, 2.0, 4.0),
596            (67, 2.0, 4.0),
597            (75, 2.0, 4.0),
598            (0, 1.5, 6.0),
599        ];
600        let expected: Vec<Vec<HashValue>> = expected
601            .iter()
602            .map(|(pitch, length, offset)| {
603                vec![
604                    HashValue::Integer(*pitch),
605                    HashValue::Float(*length),
606                    HashValue::Float(*offset),
607                ]
608            })
609            .collect();
610        assert_eq!(hashes, expected);
611        Ok(())
612    }
613}
music21/alpha/analysis/hasher.rs

music21/alpha/analysis/
hasher.rs
