music21_rs/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    fn values(
263        &self,
264        keys: &[&'static str],
265        hashed: Hashed<'_>,
266        offset: FloatType,
267        previous_note: Option<&Pitch>,
268    ) -> Result<Vec<HashValue>> {
269        let as_chord =
270            matches!(hashed, Hashed::InChord(..) | Hashed::Chord(_)) && self.hash_chords_as_chords;
271        let pitch: Option<&Pitch> = match &hashed {
272            Hashed::Alone(StreamElement::Note(note)) => Some(note.pitch()),
273            Hashed::InChord(note, _) => Some(note.pitch()),
274            _ => None,
275        };
276        let is_rest = matches!(hashed, Hashed::Alone(StreamElement::Rest(_)));
277        let chord = match &hashed {
278            Hashed::InChord(_, chord) | Hashed::Chord(chord) => Some(*chord),
279            _ => None,
280        };
281        let length = match &hashed {
282            Hashed::Alone(element) => element.quarter_length(),
283            Hashed::InChord(_, chord) | Hashed::Chord(chord) => chord
284                .duration()
285                .map_or(1.0, crate::duration::Duration::quarter_length),
286        };
287        let mut values = Vec::new();
288        for key in keys {
289            values.push(match *key {
290                "Pitch" => {
291                    if as_chord {
292                        if self.hash_midi {
293                            HashValue::Integer(1)
294                        } else {
295                            HashValue::Text("z".to_string())
296                        }
297                    } else if is_rest {
298                        if self.hash_midi {
299                            HashValue::Integer(0)
300                        } else {
301                            HashValue::Text("r".to_string())
302                        }
303                    } else if let Some(pitch) = pitch {
304                        let name = pitch_str(pitch);
305                        if self.hash_midi {
306                            HashValue::Integer(i64::from(pitch.midi()))
307                        } else if self.hash_note_name_octave {
308                            let mut name = name;
309                            name.pop();
310                            HashValue::Text(name)
311                        } else {
312                            HashValue::Text(name)
313                        }
314                    } else {
315                        HashValue::None
316                    }
317                }
318                "IsAccidental" => HashValue::None,
319                "Octave" => {
320                    if matches!(hashed, Hashed::Chord(_)) {
321                        // music21 hands its octave hash nothing for a chord
322                        // hashed as one, and asks nothing for its octave.
323                        return Err(crate::error::Error::Analysis(
324                            "'NoneType' object has no attribute 'octave'".to_string(),
325                        ));
326                    }
327                    if is_rest {
328                        HashValue::Integer(-1)
329                    } else {
330                        pitch
331                            .and_then(Pitch::octave)
332                            .map_or(HashValue::None, |octave| {
333                                HashValue::Integer(i64::from(octave))
334                            })
335                    }
336                }
337                "NormalOrderString" => match chord {
338                    Some(chord) => HashValue::Text(chord.normal_order_string()),
339                    None => HashValue::Text("<>".to_string()),
340                },
341                "PrimeFormString" => match chord {
342                    Some(chord) => HashValue::Text(chord.prime_form_string()),
343                    None => HashValue::Text("<>".to_string()),
344                },
345                "Duration" => HashValue::Float(if self.round_duration_and_offset {
346                    self.rounded(length)
347                } else {
348                    length
349                }),
350                "Offset" => HashValue::Float(if self.round_duration_and_offset {
351                    self.rounded(offset)
352                } else {
353                    offset
354                }),
355                "IntervalFromLastNote" => match (&hashed, previous_note) {
356                    (Hashed::Alone(StreamElement::Note(note)), Some(previous)) => {
357                        let interval = Interval::between_pitches(previous, note.pitch())?;
358                        HashValue::Integer(i64::from(interval.interval_class()))
359                    }
360                    _ => HashValue::None,
361                },
362                _ => HashValue::None,
363            });
364        }
365        Ok(values)
366    }
367}
368
369/// A pitch as music21's `str` writes it: its letter, its accidental in
370/// music21's spelling -- a flat as `-`, a natural as nothing -- and its
371/// octave.
372fn pitch_str(pitch: &Pitch) -> String {
373    let modifier = match pitch
374        .written_accidental()
375        .map(|accidental| accidental.name())
376    {
377        None | Some("natural") => String::new(),
378        Some("sharp") => "#".to_string(),
379        Some("double-sharp") => "##".to_string(),
380        Some("triple-sharp") => "###".to_string(),
381        Some("quadruple-sharp") => "####".to_string(),
382        Some("flat") => "-".to_string(),
383        Some("double-flat") => "--".to_string(),
384        Some("triple-flat") => "---".to_string(),
385        Some("quadruple-flat") => "----".to_string(),
386        Some("half-sharp") => "~".to_string(),
387        Some("one-and-a-half-sharp") => "#~".to_string(),
388        Some("half-flat") => "`".to_string(),
389        Some("one-and-a-half-flat") => "-`".to_string(),
390        Some(_) => pitch.accidental().modifier().to_string(),
391    };
392    let octave = pitch
393        .octave()
394        .map(|octave| octave.to_string())
395        .unwrap_or_default();
396    format!("{}{modifier}{octave}", pitch.step().as_char())
397}
398
399/// Where an element of a stream's walk stands: the stream holding it, the
400/// part it is in, and how a flattened part sorts it.
401struct Placed {
402    container: Option<usize>,
403    part: Option<usize>,
404    offset: FloatType,
405    sort_order: i32,
406    grace: bool,
407    pitch: Option<Pitch>,
408    leaf: bool,
409}
410
411/// The note before each note of a stream's walk, as music21's
412/// `previous('Note')` finds it: the last note before it in its own measure
413/// or voice, and failing that the last before it in its part, flattened and
414/// sorted by offset, class and grace notes first. A part's first note has
415/// none.
416fn notes_before(stream: &Stream) -> Vec<Option<Pitch>> {
417    fn walk(
418        stream: &Stream,
419        container: Option<usize>,
420        part: Option<usize>,
421        base: FloatType,
422        out: &mut Vec<Placed>,
423    ) {
424        for event in stream.events() {
425            let element = event.element();
426            let offset = crate::makenotation::op_frac(base + event.offset());
427            let index = out.len();
428            out.push(Placed {
429                container,
430                part,
431                offset,
432                sort_order: element.class_sort_order(),
433                grace: element
434                    .duration()
435                    .is_some_and(crate::duration::Duration::is_grace),
436                pitch: match element {
437                    StreamElement::Note(note) => Some(note.pitch().clone()),
438                    _ => None,
439                },
440                leaf: !matches!(element, StreamElement::Stream(_)),
441            });
442            if let StreamElement::Stream(inner) = element {
443                let inner_part = if matches!(inner.kind(), StreamKind::Part | StreamKind::PartStaff)
444                {
445                    Some(index)
446                } else {
447                    part
448                };
449                walk(inner, Some(index), inner_part, offset, out);
450            }
451        }
452    }
453    let mut placed = Vec::new();
454    walk(stream, None, None, 0.0, &mut placed);
455    // Each part's leaves in flattened order.
456    let mut flattened: std::collections::BTreeMap<Option<usize>, Vec<usize>> =
457        std::collections::BTreeMap::new();
458    for (index, item) in placed.iter().enumerate() {
459        if item.leaf {
460            flattened.entry(item.part).or_default().push(index);
461        }
462    }
463    let mut place_in_part = vec![0; placed.len()];
464    for leaves in flattened.values_mut() {
465        leaves.sort_by(|&a, &b| {
466            placed[a]
467                .offset
468                .total_cmp(&placed[b].offset)
469                .then(placed[a].sort_order.cmp(&placed[b].sort_order))
470                .then(placed[b].grace.cmp(&placed[a].grace))
471        });
472        for (place, &index) in leaves.iter().enumerate() {
473            place_in_part[index] = place;
474        }
475    }
476    // The last note met in each measure or voice, walking forward.
477    let mut last_in: std::collections::HashMap<Option<usize>, usize> =
478        std::collections::HashMap::new();
479    let mut out = vec![None; placed.len()];
480    for index in 0..placed.len() {
481        if placed[index].pitch.is_none() {
482            continue;
483        }
484        let container = placed[index].container;
485        out[index] = match last_in.get(&container) {
486            Some(&before) => placed[before].pitch.clone(),
487            None => flattened[&placed[index].part][..place_in_part[index]]
488                .iter()
489                .rev()
490                .find_map(|&before| placed[before].pitch.clone()),
491        };
492        last_in.insert(container, index);
493    }
494    out
495}
496
497/// Every element of a stream in the order music21's `recurse` walks it,
498/// each with its offset in the stream holding it.
499fn recurse_with_local_offsets(stream: &Stream) -> Vec<(FloatType, StreamElement)> {
500    fn walk(stream: &Stream, out: &mut Vec<(FloatType, StreamElement)>) {
501        for event in stream.events() {
502            out.push((event.offset(), event.element().clone()));
503            if let StreamElement::Stream(inner) = event.element() {
504                walk(inner, out);
505            }
506        }
507    }
508    let mut out = Vec::new();
509    walk(stream, &mut out);
510    out
511}
512
513#[cfg(test)]
514mod tests {
515    use super::*;
516    use crate::{chord::Chord, duration::Duration, note::Note, rest::Rest};
517
518    #[test]
519    fn notes_chords_and_rests_are_hashed_as_music21_hashes_them() -> Result<()> {
520        // music21's testBasicHash.
521        let mut stream = Stream::new();
522        stream.push(Note::from_name("C4")?.with_duration(Duration::new(2.0)?));
523        stream.push(Note::from_name("F#4")?);
524        stream.push(Note::from_name("B-2")?);
525        stream.push(Chord::new("C4 G4 E-5")?.with_duration(Duration::new(2.0)?));
526        stream.push(Rest::new(Duration::new(1.5)?));
527        let hashes: Vec<Vec<HashValue>> = Hasher::default()
528            .hash_stream(&stream)?
529            .into_iter()
530            .map(|hash| hash.values)
531            .collect();
532        let expected = [
533            (60, 2.0, 0.0),
534            (66, 1.0, 2.0),
535            (46, 1.0, 3.0),
536            (60, 2.0, 4.0),
537            (67, 2.0, 4.0),
538            (75, 2.0, 4.0),
539            (0, 1.5, 6.0),
540        ];
541        let expected: Vec<Vec<HashValue>> = expected
542            .iter()
543            .map(|(pitch, length, offset)| {
544                vec![
545                    HashValue::Integer(*pitch),
546                    HashValue::Float(*length),
547                    HashValue::Float(*offset),
548                ]
549            })
550            .collect();
551        assert_eq!(hashes, expected);
552        Ok(())
553    }
554}
music21_rs/alpha/analysis/hasher.rs

music21_rs/alpha/analysis/
hasher.rs
