music21/humdrum/

mod.rs

//! Humdrum: music21's `humdrum.spineParser`, which reads `**kern` scores.
//!
//! A Humdrum file is a table. Each column is a *spine* -- a part -- and each
//! line a moment; a cell holds a note (`4c#` is a quarter C sharp above
//! middle C), a barline (`=12`), an instruction (`*clefG2`, `*M3/4`) or a
//! dot where nothing new happens. A spine may split into two voices (`*^`)
//! and come together again (`*v`). `**dynam` spines carry dynamics and
//! `**text` spines the words sung, and `**harm` spines the harmony read
//! into the music, each said by `*staff` to belong to a `**kern` spine.

mod comment;
pub mod harm;
mod tables;
mod tandem;

use std::collections::BTreeMap;

use crate::articulations::{Articulation, ArticulationKind};
use crate::bar::{Barline, BarlineType, RepeatDirection};
use crate::chord::Chord;
use crate::clef::{Clef, ClefKind};
use crate::defaults::{FloatType, IntegerType};
use crate::duration::{Duration, DurationType, Grace, Tuplet, TupletType};
use crate::dynamics::Dynamic;
use crate::error::{Error, Position, Result};
use crate::expressions::{Expression, Fermata, Ornament, OrnamentKind};
use crate::instrument::Instrument;
use crate::key::{Key, KeySignature};
use crate::makenotation::op_frac;
use crate::metadata::{Metadata, is_contributor_unique_name};
use crate::meter::TimeSignature;
use crate::notation::{BeamDirection, BeamType, StemDirection, Tie, TieType};
use crate::note::Note;
use crate::pitch::{Accidental, PitchOptions};
use crate::rest::Rest;
use crate::roman::{Minor67Default, RomanNumeral};
use crate::stream::{Stream, StreamElement, StreamEvent, StreamKind};
use crate::tempo::MetronomeMark;

pub use comment::{GlobalComment, SpineComment};
pub use tables::{INSTRUMENT_CLASSES, INSTRUMENTS};
pub use tandem::MiscTandem;

use tables::REFERENCE_NAMES;

fn humdrum_error(message: impl Into<String>) -> Error {
    Error::humdrum(message.into())
}

/// The tokens that say where a spine goes rather than what it holds.
const SPINE_PATHS: [&str; 6] = ["*+", "*-", "*^", "*v", "*x", "*"];

/// A barline as a spine states it: the measure it opens.
#[derive(Clone, Debug, Default)]
struct Measure {
    number: IntegerType,
    suffix: Option<String>,
    left: Option<Barline>,
    right: Option<Barline>,
}

/// What a cell of a spine came to.
// Nearly every thing is an element, so boxing it would cost more than the
// few smaller variants waste.
#[allow(clippy::large_enum_variant)]
#[derive(Clone, Debug)]
enum Thing {
    Element(StreamElement),
    Measure(Measure),
    /// An instruction with no meaning here, kept for `*staff`.
    Tandem(String),
    /// A word of a `**text` spine.
    Word(String),
}

/// A thing in a spine's stream: where it stands, the line it was written
/// on -- which music21 sorts by ahead of everything but the offset -- and
/// the voice it belongs to while a spine is split.
#[derive(Clone, Debug)]
struct Placed {
    offset: FloatType,
    line: usize,
    /// Nought for a thing no line can be asked for any more.
    priority: usize,
    voice: Option<usize>,
    thing: Thing,
}

impl Placed {
    fn length(&self) -> FloatType {
        match &self.thing {
            Thing::Element(element) => element.quarter_length(),
            _ => 0.0,
        }
    }

    fn class_order(&self) -> i32 {
        match &self.thing {
            Thing::Element(element) => element.class_sort_order(),
            Thing::Measure(_) => -20,
            _ => 0,
        }
    }
}

/// music21's stream order: offset, then the priority, then the class.
fn sort(things: &mut [Placed]) {
    things.sort_by(|left, right| {
        left.offset
            .total_cmp(&right.offset)
            .then(left.priority.cmp(&right.priority))
            .then(left.class_order().cmp(&right.class_order()))
    });
}

fn highest(things: &[Placed]) -> FloatType {
    things
        .iter()
        .map(|thing| thing.offset + thing.length())
        .fold(0.0, FloatType::max)
}

/// One spine: music21's `HumdrumSpine`.
#[derive(Clone, Debug, Default)]
struct Spine {
    events: Vec<(String, usize)>,
    parent: Option<usize>,
    first_voice: bool,
    /// The spines this one splits into, by the line it splits on.
    splits: BTreeMap<usize, Vec<usize>>,
    kind: String,
    stream: Vec<Placed>,
}

/// The lengths a number names: music21's `typeFromNumDict`.
fn type_of_number(number: u64) -> Option<DurationType> {
    ((1..=2048).contains(&number) && number.is_power_of_two())
        .then(|| {
            DurationType::ALL
                .into_iter()
                .find(|kind| kind.quarter_length() == 4.0 / number as FloatType)
        })
        .flatten()
}

fn first_number(text: &str) -> Option<&str> {
    let start = text.find(|c: char| c.is_ascii_digit())?;
    let rest = &text[start..];
    let end = rest
        .find(|c: char| !c.is_ascii_digit())
        .unwrap_or(rest.len());
    Some(&rest[..end])
}

/// music21's `hdStringToDuration`: `4` is a quarter, `8.` a dotted eighth,
/// `12` an eighth of a triplet, `0` a breve, and `q` a grace note.
fn duration_of(contents: &str) -> Result<Duration> {
    let dots = contents.matches('.').count() as u32;
    let has_grace = contents.contains('q') || contents.contains('Q');
    let number = first_number(contents);
    let rational = contents.contains('%').then(|| {
        let at = contents.find('%')?;
        let before = &contents[..at];
        let start = before
            .rfind(|c: char| !c.is_ascii_digit())
            .map_or(0, |index| index + 1);
        let first = before[start..].parse::<FloatType>().ok()?;
        let second = first_number(&contents[at + 1..])
            .filter(|_| contents[at + 1..].starts_with(|c: char| c.is_ascii_digit()))?
            .parse::<FloatType>()
            .ok()?;
        Some((first, second))
    });
    let mut duration = if let Some(Some((first, second))) = rational {
        let plain = Duration::new(op_frac(4.0 * second / first))?;
        match plain.type_and_dots() {
            Some((kind, _)) if dots > 0 => Duration::from_type_with_dots(kind, dots),
            _ => plain,
        }
    } else if let Some(number) = number {
        let value: u64 = number
            .parse()
            .map_err(|_| humdrum_error(format!("Could not find a duration in {contents:?}")))?;
        if value == 0 {
            let kind = match number {
                "000" => DurationType::Maxima,
                "00" => DurationType::Longa,
                _ => DurationType::Breve,
            };
            Duration::from_type_with_dots(kind, dots)
        } else if let Some(kind) = type_of_number(value) {
            Duration::from_type_with_dots(kind, dots)
        } else {
            // A number that is no power of two is that many in the time of
            // the power of two below it: twelfths are triplet eighths.
            let base = 1_u64 << value.ilog2();
            let kind = type_of_number(base)
                .ok_or_else(|| humdrum_error(format!("no note value for {value}")))?;
            let divisor = gcd(value, base);
            let mut tuplet =
                Tuplet::new((value / divisor) as u32, (base / divisor) as u32, kind, 0);
            if dots > 0 {
                tuplet.set_duration_normal(Some((kind, dots)));
            }
            let mut duration = Duration::from_type(kind);
            duration.append_tuplet(tuplet);
            duration
        }
    } else if has_grace {
        Duration::from_type(DurationType::Eighth)
    } else {
        return Err(humdrum_error(format!(
            "Could not find a duration in {contents:?}"
        )));
    };
    if has_grace {
        duration = duration.grace_duration();
        let mut grace = Grace::new();
        if contents.matches('q').count() != 1 {
            grace.set_slash(false);
        }
        duration.set_grace(Some(grace));
    } else if contents.contains('P') {
        duration = duration.grace_duration();
        duration.set_grace(Some(Grace::appoggiatura()));
    }
    Ok(duration)
}

fn gcd(mut left: u64, mut right: u64) -> u64 {
    while right != 0 {
        (left, right) = (right, left % right);
    }
    left
}

/// What is read off a note's token besides the note itself.
struct Marks {
    tie: Option<TieType>,
    expressions: Vec<Expression>,
    articulations: Vec<Articulation>,
    stem: StemDirection,
    beams: Vec<(BeamType, Option<BeamDirection>)>,
}

fn marks_of(contents: &str) -> Marks {
    let has = |mark: char| contents.contains(mark);
    let tie = if has('[') {
        Some(TieType::Start)
    } else if has(']') {
        Some(TieType::Stop)
    } else if has('_') {
        Some(TieType::Continue)
    } else {
        None
    };
    let ornament = |kind: OrnamentKind| Expression::from(Ornament::of_kind(kind));
    let mut expressions = Vec::new();
    if has('t') {
        expressions.push(ornament(OrnamentKind::HalfStepTrill));
    } else if has('T') {
        expressions.push(ornament(OrnamentKind::WholeStepTrill));
    }
    if has('w') {
        expressions.push(ornament(OrnamentKind::HalfStepInvertedMordent));
    } else if has('W') {
        expressions.push(ornament(OrnamentKind::WholeStepInvertedMordent));
    } else if has('m') {
        expressions.push(ornament(OrnamentKind::HalfStepMordent));
    } else if has('M') {
        expressions.push(ornament(OrnamentKind::WholeStepMordent));
    }
    if has('S') {
        expressions.push(ornament(OrnamentKind::Turn));
    } else if has('$') {
        expressions.push(ornament(OrnamentKind::InvertedTurn));
    } else if has('R') {
        expressions.push(ornament(OrnamentKind::Turn));
    }
    if has('O') {
        expressions.push(ornament(OrnamentKind::Ornament));
    }
    let mut articulations = Vec::new();
    let mut articulation = |class: &str| {
        if let Some(kind) = ArticulationKind::from_class_name(class) {
            articulations.push(Articulation::of_kind(kind));
        }
    };
    if has('\'') {
        articulation("Staccato");
    }
    if has('"') {
        articulation("Pizzicato");
    }
    if has('`') {
        articulation("Staccatissimo");
    }
    if has('~') {
        articulation("Tenuto");
    }
    if has('^') {
        articulation("Accent");
    }
    if has(';') {
        expressions.push(Expression::Fermata(Fermata::new()));
    }
    if has('v') {
        articulation("UpBow");
    } else if has('u') {
        articulation("DownBow");
    }
    let stem = if has('/') {
        StemDirection::Up
    } else if has('\\') {
        StemDirection::Down
    } else {
        StemDirection::Unspecified
    };
    let mut beams = Vec::new();
    for (mark, beam, direction) in [
        ('L', BeamType::Start, None),
        ('J', BeamType::Stop, None),
        ('k', BeamType::PartialBeam, Some(BeamDirection::Left)),
        ('K', BeamType::PartialBeam, Some(BeamDirection::Right)),
    ] {
        for _ in 0..contents.matches(mark).count() {
            beams.push((beam, direction));
        }
    }
    Marks {
        tie,
        expressions,
        articulations,
        stem,
        beams,
    }
}

/// music21's `hdStringToNote`: a note or a rest from its token.
fn note_of(contents: &str, given: Option<&Duration>) -> Result<StreamElement> {
    // A token with no length is a quarter, as music21 makes it with a
    // warning.
    let duration = match given {
        Some(duration) => duration.clone(),
        None => duration_of(contents).unwrap_or_else(|_| Duration::quarter()),
    };
    let marks = marks_of(contents);
    if contents.contains('r') {
        let mut rest = Rest::new(duration);
        rest.set_tie(marks.tie.map(Tie::new));
        *rest.expressions_mut() = marks.expressions;
        *rest.articulations_mut() = marks.articulations;
        return Ok(rest.into());
    }
    let letters = |c: char| matches!(c, 'a'..='g' | 'A'..='G');
    let start = contents
        .find(letters)
        .ok_or_else(|| humdrum_error(format!("Could not parse {contents} for note information")))?;
    let name: Vec<char> = contents[start..]
        .chars()
        .take_while(|c| letters(*c))
        .collect();
    let first = name[0];
    let count = name.len() as IntegerType;
    let octave = if first.is_ascii_lowercase() {
        3 + count
    } else {
        4 - count
    };
    let mut pitch = PitchOptions::new()
        .step(first.to_ascii_uppercase())
        .octave(octave)
        .build()?;
    let sharps = contents.matches('#').count() as IntegerType;
    let flats = contents.matches('-').count() as IntegerType;
    if sharps > 0 {
        pitch.set_written_accidental(Some(Accidental::new(sharps)?));
    } else if flats > 0 {
        pitch.set_written_accidental(Some(Accidental::new(-flats)?));
    } else if contents.contains('n') {
        pitch.set_written_accidental(Some(Accidental::new("n")?));
    }
    let mut note = Note::from_pitch(pitch).with_duration(duration);
    note.set_tie(marks.tie.map(Tie::new));
    *note.expressions_mut() = marks.expressions;
    *note.articulations_mut() = marks.articulations;
    note.set_stem_direction(marks.stem);
    let mut beams = note.beams().clone();
    for (beam, direction) in marks.beams {
        beams.append(beam, direction);
    }
    note.set_beams(beams);
    Ok(note.into())
}

/// music21's `hdStringToMeasure`: the measure a barline opens, and the
/// barline it puts at the end of the measure before.
fn measure_of(contents: &str, has_previous: bool) -> (Measure, Barline) {
    let mut measure = Measure::default();
    if let Some(number) = first_number(contents) {
        measure.number = number.parse().unwrap_or(0);
        let after = &contents[contents.find(number).unwrap_or(0) + number.len()..];
        measure.suffix = after
            .chars()
            .next()
            .filter(char::is_ascii_lowercase)
            .map(String::from);
    }
    let bar_type = if contents.contains('-') {
        Some(BarlineType::None)
    } else if contents.contains('\'') {
        Some(BarlineType::Short)
    } else if contents.contains('`') {
        Some(BarlineType::Tick)
    } else if contents.contains("||") || contents.contains("==") {
        Some(BarlineType::Double)
    } else if contents.contains("!!") {
        Some(BarlineType::HeavyHeavy)
    } else if contents.contains("|!") {
        Some(BarlineType::Final)
    } else if contents.contains("!|") {
        Some(BarlineType::HeavyLight)
    } else if contents.contains('|') {
        Some(BarlineType::Regular)
    } else {
        None
    };
    let chars: Vec<char> = contents.chars().collect();
    let beside = |colon_first: bool| {
        chars.windows(2).any(|pair| {
            let (colon, bar) = if colon_first {
                (pair[0], pair[1])
            } else {
                (pair[1], pair[0])
            };
            colon == ':' && matches!(bar, '|' | '!' | '=')
        })
    };
    let both = contents.matches(':').count() > 1;
    let end_repeat = both || beside(true);
    let start_repeat = both || beside(false);
    let make = |direction: Option<RepeatDirection>| {
        let mut barline = match direction {
            Some(direction) => Barline::repeat(direction, None),
            None => Barline::new(BarlineType::Regular),
        };
        if let Some(bar_type) = bar_type {
            barline.set_bar_type(bar_type);
        }
        barline
    };
    let right = make(end_repeat.then_some(RepeatDirection::End));
    if has_previous {
        if start_repeat {
            measure.left = Some(make(Some(RepeatDirection::Start)));
        }
    } else {
        measure.left = Some(if start_repeat {
            make(Some(RepeatDirection::Start))
        } else {
            right.clone()
        });
    }
    (measure, right)
}

/// music21's `kernTandemToObject`: what an instruction in a `**kern` spine
/// stands for.
fn tandem_of(tandem: &str) -> Result<Option<Thing>> {
    let element = |element: StreamElement| Ok(Some(Thing::Element(element)));
    if SPINE_PATHS.contains(&tandem) {
        return Ok(None);
    }
    if let Some(kind) = tandem.strip_prefix("*clef") {
        let clef = match kind {
            "-" => Clef::of_kind(ClefKind::NoClef),
            "X" => Clef::of_kind(ClefKind::PercussionClef),
            "Gv2" | "Gv" => Clef::of_kind(ClefKind::Treble8vbClef),
            "G^2" | "G^" => Clef::of_kind(ClefKind::Treble8vaClef),
            "Fv4" | "Fv" => Clef::of_kind(ClefKind::Bass8vbClef),
            other => Clef::from_string(other, 0)
                .map_err(|_| humdrum_error(format!("Unknown clef type {tandem} found")))?,
        };
        return element(clef.into());
    }
    if let Some(text) = tandem.strip_prefix("*MM") {
        let mark = match text.parse::<FloatType>() {
            Ok(number) => MetronomeMark::new(number),
            Err(_) => {
                let text = text.strip_prefix('[').unwrap_or(text);
                let text = text.trim_end();
                MetronomeMark::from_text(text.strip_suffix(']').unwrap_or(text))
            }
        };
        return element(mark.into());
    }
    if let Some(meter) = tandem.strip_prefix("*M") {
        let digits = |text: &str| text.chars().take_while(char::is_ascii_digit).count();
        let top = digits(meter);
        let bottom = meter
            .get(top + 1..)
            .filter(|_| top > 0 && meter[top..].starts_with('/'))
            .map(|rest| &rest[..digits(rest)])
            .filter(|bottom| !bottom.is_empty())
            .ok_or_else(|| humdrum_error(format!("Incorrect meter: {tandem} found")))?;
        let numerator: u32 = meter[..top]
            .parse()
            .map_err(|_| humdrum_error(format!("Incorrect meter: {tandem} found")))?;
        let signature = match bottom {
            "0" => TimeSignature::new(numerator * 2, 1)?,
            "00" => TimeSignature::new(numerator * 4, 1)?,
            "000" => TimeSignature::new(numerator * 8, 1)?,
            _ => TimeSignature::from_ratio_string(meter)?,
        };
        return element(signature.into());
    }
    let instrument = |table: &[(&str, &str)], code: &str| -> Option<Instrument> {
        let class = table.iter().find(|(held, _)| *held == code)?.1;
        Instrument::of_kind(class).ok()
    };
    if let Some(class) = tandem.strip_prefix("*IC") {
        return Ok(Some(match instrument(INSTRUMENT_CLASSES, class) {
            Some(instrument) => Thing::Element(instrument.into()),
            None => Thing::Tandem(class.to_string()),
        }));
    }
    if tandem.starts_with("*IG") || tandem.starts_with("*ITr") {
        return Ok(Some(Thing::Tandem(tandem.to_string())));
    }
    if let Some(code) = tandem.strip_prefix("*I") {
        return Ok(Some(match instrument(INSTRUMENTS, code) {
            Some(instrument) => Thing::Element(instrument.into()),
            None => Thing::Tandem(code.to_string()),
        }));
    }
    if tandem.starts_with("*k") {
        let mut sharps = tandem.matches('#').count() as IntegerType;
        if sharps == 0 {
            sharps = -(tandem.matches('-').count() as IntegerType);
        }
        return element(KeySignature::new(sharps).into());
    }
    if let Some(key) = tandem.strip_suffix(':') {
        return element(StreamElement::Key(Key::from_tonic(&key[1..])?));
    }
    Ok(Some(Thing::Tandem(tandem.to_string())))
}

/// What a `**kern` spine keeps from one note to the next: music21's
/// `KernSpine` state.
#[derive(Default)]
struct KernState {
    /// music21's `inTuplet`, with its `currentTupletQL` and
    /// `desiredTupletQL`, which are both zero whenever it is false.
    tuplet: Option<TupletRun>,
    /// music21's `lastNote`, as an index into the stream.
    last_note: Option<usize>,
    /// music21's `currentBeamNumbers`.
    beams: usize,
}

/// A run of tuplet notes being read: how long it is so far and how long
/// its bracket is.
struct TupletRun {
    /// music21's `currentTupletQL`.
    length: FloatType,
    /// music21's `desiredTupletQL`.
    wanted: FloatType,
}

fn with_duration(element: &mut StreamElement, change: impl FnOnce(&mut Duration)) {
    let Some(mut duration) = element.duration().cloned() else {
        return;
    };
    change(&mut duration);
    match element {
        StreamElement::Note(note) => note.set_duration(duration),
        StreamElement::Chord(chord) => chord.set_duration(duration),
        StreamElement::Rest(rest) => rest.set_duration(duration),
        _ => {}
    }
}

fn mark_first_tuplet(element: &mut StreamElement, kind: TupletType) {
    with_duration(element, |duration| {
        let mut tuplets = duration.tuplets();
        if let Some(first) = tuplets.first_mut() {
            first.set_tuplet_type(Some(kind));
        }
        duration.set_tuplets(tuplets);
    });
}

impl KernState {
    /// music21's `setBeamsForNote`: a note between the start and the end of
    /// a beam carries it on.
    fn beam(&mut self, element: &mut StreamElement) {
        let beams = match element {
            StreamElement::Note(note) => note.beams().clone(),
            StreamElement::Chord(chord) => chord.beams().clone(),
            _ => return,
        };
        if self.beams != 0 && beams.is_empty() {
            let mut carried = beams;
            for _ in 0..self.beams {
                carried.append(BeamType::Continue, None);
            }
            match element {
                StreamElement::Note(note) => note.set_beams(carried),
                StreamElement::Chord(chord) => chord.set_beams(carried),
                _ => {}
            }
        } else if let Some(first) = beams.beams().first() {
            if first.beam_type() == Some(BeamType::Stop) {
                self.beams = 0;
            } else {
                self.beams += beams
                    .beams()
                    .iter()
                    .filter(|beam| beam.beam_type() != Some(BeamType::Stop))
                    .count();
            }
        }
    }

    /// music21's `setTupletTypeForNote`: where a run of tuplet notes starts
    /// and where it has filled its bracket. A grace note neither counts
    /// toward a tuplet nor ends one.
    fn tuplet(&mut self, stream: &mut [Placed], element: &mut StreamElement) {
        let Some(duration) = element.duration().cloned() else {
            return;
        };
        if duration.is_grace() {
            return;
        }
        let tuplets = duration.tuplets();
        let Some(run) = &mut self.tuplet else {
            if !tuplets.is_empty() {
                self.tuplet = Some(TupletRun {
                    length: duration.quarter_length(),
                    wanted: tuplets[0].total_tuplet_length(),
                });
                mark_first_tuplet(element, TupletType::Start);
            }
            return;
        };
        if tuplets.is_empty() {
            self.tuplet = None;
            if let Some(last) = self.last_note
                && let Thing::Element(last) = &mut stream[last].thing
            {
                mark_first_tuplet(last, TupletType::Stop);
            }
            return;
        }

        run.length = op_frac(run.length + duration.quarter_length());
        if run.length >= run.wanted && run.length % run.wanted == 0.0 {
            mark_first_tuplet(element, TupletType::Stop);
            self.tuplet = None;
        }
    }
}

/// music21's `processChordEvent`: the notes of a cell holding several.
fn chord_of(contents: &str) -> Result<StreamElement> {
    let mut notes: Vec<Note> = Vec::new();
    let mut first: Option<(Duration, String)> = None;
    for token in contents.split_whitespace() {
        let length: String = token
            .chars()
            .filter(|c| c.is_ascii_digit() || matches!(c, '.' | '%'))
            .collect();
        let bare: String = token
            .chars()
            .filter(|c| !(c.is_ascii_digit() || matches!(c, '.' | '%')))
            .collect();
        let element = match &first {
            Some((duration, written)) if length.is_empty() || length == *written => {
                note_of(&bare, Some(duration))?
            }
            _ => {
                let element = note_of(token, None)?;
                if first.is_none()
                    && let Some(duration) = element.duration()
                {
                    first = Some((duration.clone(), length));
                }
                element
            }
        };
        if let StreamElement::Note(note) = element {
            notes.push(note);
        }
    }
    let last_beams = notes
        .last()
        .map(|note| note.beams().clone())
        .ok_or_else(|| humdrum_error("a chord with no notes in it"))?;
    let duration = first.map(|(duration, _)| duration).unwrap_or_default();
    let mut chord = Chord::new(notes)?.with_duration(duration);
    chord.set_beams(last_beams);
    Ok(chord.into())
}

/// Appends a thing to a spine's stream, after all it holds.
fn append(stream: &mut Vec<Placed>, line: usize, priority: usize, thing: Thing) -> usize {
    let offset = highest(stream);
    stream.push(Placed {
        offset,
        line,
        priority,
        voice: None,
        thing,
    });
    stream.len() - 1
}

/// music21's `KernSpine.parse`.
fn parse_kern(events: &[(String, usize)]) -> Vec<Placed> {
    let mut stream: Vec<Placed> = Vec::new();
    let mut state = KernState::default();
    // The measure a barline closes, by its place in the stream.
    let mut last_measure: Option<usize> = None;
    for (contents, line) in events {
        let made: Result<Option<Thing>> = (|| {
            if contents == "." || contents.is_empty() {
                return Ok(None);
            }
            if contents.starts_with('*') {
                return tandem_of(contents);
            }
            if contents.starts_with('=') {
                // music21 starts every spine off with a measure nought of
                // its own, so the first barline always has one before it.
                let (measure, right) = measure_of(contents, true);
                if let Some(previous) = last_measure
                    && let Thing::Measure(previous) = &mut stream[previous].thing
                {
                    previous.right = Some(right);
                }
                return Ok(Some(Thing::Measure(measure)));
            }
            if contents.starts_with('!') {
                // music21's `SpineComment`: the line without its bangs and
                // one space, kept where it says anything.
                let text = contents.trim_start_matches('!');
                let text = text.strip_prefix(char::is_whitespace).unwrap_or(text);
                if text.is_empty() {
                    return Ok(None);
                }
                return Ok(Some(Thing::Element(SpineComment::new(text).into())));
            }
            let mut element = if contents.contains(' ') {
                chord_of(contents)?
            } else {
                note_of(contents, None)?
            };
            state.beam(&mut element);
            state.tuplet(&mut stream, &mut element);
            Ok(Some(Thing::Element(element)))
        })();
        // A cell that cannot be read is passed over, as music21 passes over
        // it with a warning.
        let Ok(Some(thing)) = made else {
            continue;
        };
        let is_measure = matches!(thing, Thing::Measure(_));
        let sounds = matches!(
            &thing,
            Thing::Element(
                element @ (StreamElement::Note(_) | StreamElement::Chord(_) | StreamElement::Rest(_))
            ) if !element.duration().is_some_and(Duration::is_grace)
        );
        let index = append(&mut stream, *line, *line, thing);
        if is_measure {
            last_measure = Some(index);
        }
        if sounds {
            state.last_note = Some(index);
        }
    }
    stream
}

/// music21's `DynamSpine.parse` and the generic one: the marks and words of
/// a spine that is no `**kern`, each with its line.
fn parse_other(events: &[(String, usize)], dynamics: bool) -> Vec<Placed> {
    let mut stream = Vec::new();
    for (contents, line) in events {
        let thing = if contents == "." || contents.is_empty() {
            continue;
        } else if contents.starts_with('*') {
            if SPINE_PATHS.contains(&contents.as_str()) {
                continue;
            }
            Thing::Tandem(contents.clone())
        } else if contents.starts_with('=') || contents.starts_with('!') {
            continue;
        } else if dynamics {
            if contents.starts_with('<') || contents.starts_with('>') {
                continue;
            }
            Thing::Element(Dynamic::new(contents.as_str()).into())
        } else {
            Thing::Word(contents.clone())
        };
        append(&mut stream, *line, 0, thing);
    }
    stream
}

/// music21's `HarmSpine.parse`: the harmonic annotations of a `**harm`
/// spine, each read as a roman numeral in the key the spine last named.
///
/// A chord carries the numeral, as every numeral this crate reads does, so
/// the notes are the ones the figure stands for in that key. The minor
/// sixth and seventh are read as music21 reads them here -- the sixth flat
/// and the seventh sharp -- and a token that is no `**harm` token is passed
/// over, which is what music21 does after warning about it.
fn parse_harm(events: &[(String, usize)]) -> Result<Vec<Placed>> {
    let mut stream = Vec::new();
    // music21's `HarmSpine` starts in C major and takes every later key
    // from the spine's own tandems.
    let mut key = Key::from_tonic("C")?;
    for (contents, line) in events {
        if contents == "." || contents.is_empty() {
            continue;
        }
        if contents.starts_with('*') {
            if SPINE_PATHS.contains(&contents.as_str()) {
                continue;
            }
            match contents.strip_suffix(':') {
                Some(named) => key = Key::from_tonic(&named[1..])?,
                // Anything else is kept as it stands, `*staff` among it,
                // which is what says whose harmony this is.
                None => {
                    append(&mut stream, *line, 0, Thing::Tandem(contents.clone()));
                }
            }
            continue;
        }
        if contents.starts_with('=') || contents.starts_with('!') {
            continue;
        }
        let Some(figure) = harm::convert_harm_to_roman(contents) else {
            continue;
        };
        let numeral = RomanNumeral::with_minor_defaults(
            &figure,
            key.clone(),
            Minor67Default::Flat,
            Minor67Default::Sharp,
        )?;
        let chord = numeral.to_chord()?.with_numeral(numeral);
        append(&mut stream, *line, 0, Thing::Element(chord.into()));
    }
    Ok(stream)
}

/// music21's `createHumdrumSpines`: the spines a table's columns run
/// through, splitting, joining and changing places as the table says.
fn spines_of(lines: &[(usize, Vec<String>)], width: usize) -> Result<Vec<Spine>> {
    let mut spines: Vec<Spine> = Vec::new();
    let mut current: Vec<Option<usize>> = Vec::new();
    for (line, cells) in lines {
        if current.len() < width {
            current.resize(width, None);
        }
        for (column, cell) in cells.iter().enumerate().take(width) {
            let spine = match current[column] {
                Some(spine) => spine,
                None => {
                    spines.push(Spine::default());
                    current[column] = Some(spines.len() - 1);
                    spines.len() - 1
                }
            };
            spines[spine].events.push((cell.clone(), *line));
        }
        if !cells
            .iter()
            .any(|cell| SPINE_PATHS.contains(&cell.as_str()))
        {
            continue;
        }
        let mut next: Vec<Option<usize>> = Vec::new();
        let mut merging = false;
        let mut merge_parent: Option<usize> = None;
        let mut exchange: Option<usize> = None;
        for (column, spine) in current.clone().into_iter().enumerate().take(width) {
            let Some(cell) = cells.get(column) else {
                if spine.is_some() {
                    next.push(spine);
                }
                continue;
            };
            let Some(spine) = spine else {
                return Err(humdrum_error(format!(
                    "spine-path token at line {line} has no active spine"
                ))
                .placed(|| Position::line(*line)));
            };
            match cell.as_str() {
                "*-" => {}
                "*^" => {
                    let mut voices = Vec::new();
                    for first in [true, false] {
                        spines.push(Spine {
                            parent: Some(spine),
                            first_voice: first,
                            ..Spine::default()
                        });
                        voices.push(spines.len() - 1);
                        next.push(Some(spines.len() - 1));
                    }
                    spines[spine].splits.insert(*line, voices);
                }
                "*v" => {
                    if merging {
                        let parent = spines[spine].parent.or(merge_parent);
                        match parent {
                            Some(parent) => next.push(Some(parent)),
                            None => {
                                spines.push(Spine::default());
                                next.push(Some(spines.len() - 1));
                            }
                        }
                        merging = false;
                        merge_parent = None;
                    } else {
                        merging = true;
                        merge_parent = spines[spine].parent;
                    }
                }
                "*x" => match exchange.take() {
                    None => exchange = Some(spine),
                    Some(waiting) => {
                        next.push(Some(spine));
                        next.push(Some(waiting));
                    }
                },
                _ => next.push(Some(spine)),
            }
        }
        if exchange.is_some() {
            return Err(humdrum_error(format!(
                "ProtoSpine found with unpaired exchange instruction at line {line}"
            ))
            .placed(|| Position::line(*line)));
        }
        current = next;
    }
    Ok(spines)
}

/// The kind of a spine: what its `**` heading says, or its parent's.
fn kind_of(spines: &[Spine], index: usize) -> Result<String> {
    let mut at = Some(index);
    while let Some(spine) = at {
        if let Some(kind) = spines[spine]
            .events
            .iter()
            .find_map(|(contents, _)| contents.strip_prefix("**"))
        {
            return Ok(kind.to_string());
        }
        at = spines[spine].parent;
    }
    Err(humdrum_error(format!(
        "Could not determine spineType for spine with id {index}"
    )))
}

/// music21's `performInsertions`: the voices a spine split into, put back
/// into it where it split.
fn insert_voices(spines: &mut [Spine], index: usize) {
    let mut points: Vec<usize> = spines[index].splits.keys().copied().collect();
    if points.is_empty() {
        return;
    }
    let old = std::mem::take(&mut spines[index].stream);
    let mut new: Vec<Placed> = Vec::new();
    let insert = |new: &mut Vec<Placed>, spines: &[Spine], point: usize| {
        let start = highest(new);
        for (number, child) in spines[index].splits[&point].iter().enumerate() {
            for thing in &spines[*child].stream {
                if !spines[*child].first_voice && matches!(thing.thing, Thing::Measure(_)) {
                    continue;
                }
                let mut thing = thing.clone();
                thing.offset += start;
                thing.voice.get_or_insert(number + 1);
                new.push(thing);
            }
        }
    };
    let mut last: Option<usize> = None;
    for thing in old {
        // Python walks the list it is taking things out of, so the point
        // after one that is used is passed over until the next element.
        let mut at = 0;
        while at < points.len() {
            let point = points[at];
            if last.is_some_and(|last| last > point) || thing.line < point {
                at += 1;
                continue;
            }
            insert(&mut new, spines, point);
            points.remove(at);
            at += 1;
        }
        last = Some(thing.line);
        let offset = highest(&new);
        new.push(Placed { offset, ..thing });
    }
    for point in points {
        insert(&mut new, spines, point);
    }
    spines[index].stream = new;
}

/// A measure while elements are gathered into it.
struct Gathered {
    measure: Measure,
    offset: FloatType,
    /// The line of the barline opening it, which music21 sorts it by.
    priority: usize,
    things: Vec<Placed>,
}

/// music21's `moveElementsIntoMeasures`: the barlines of a spine as the
/// measures its notes are in.
fn into_measures(mut stream: Vec<Placed>) -> (Vec<Gathered>, Vec<Placed>) {
    sort(&mut stream);
    let mut measures: Vec<Gathered> = Vec::new();
    let mut loose: Vec<Placed> = Vec::new();
    let mut current = Gathered {
        measure: Measure::default(),
        offset: 0.0,
        priority: 0,
        things: Vec::new(),
    };
    let mut number = 0;
    let mut has_one = false;
    for thing in stream {
        match thing.thing {
            Thing::Measure(measure) => {
                if number != 0 || !current.things.is_empty() {
                    measures.push(current);
                }
                number = measure.number;
                has_one |= number == 1;
                current = Gathered {
                    measure,
                    offset: thing.offset,
                    priority: thing.priority,
                    things: Vec::new(),
                };
            }
            _ => {
                if number != 0 || thing.length() != 0.0 {
                    let offset = thing.offset - current.offset;
                    current.things.push(Placed { offset, ..thing });
                } else {
                    loose.push(thing);
                }
            }
        }
    }
    if !current.things.is_empty() {
        measures.push(current);
    }
    if let Some(first) = measures.first_mut() {
        if !has_one {
            first.measure.number = 1;
        }
        // What stands at the very start outside any measure goes into the
        // first, but for the instructions that name nothing.
        let (moved, kept): (Vec<Placed>, Vec<Placed>) = loose
            .into_iter()
            .partition(|thing| thing.offset == 0.0 && matches!(thing.thing, Thing::Element(_)));
        first.things.extend(moved);
        loose = kept;
    }
    (measures, loose)
}

/// music21's `TupletFixer`: a run of tuplet notes that does not fill its
/// bracket is written in the longest or the shortest value among them.
fn fix_tuplets(things: &mut [Placed]) {
    let tuplets = |thing: &Placed| match &thing.thing {
        Thing::Element(
            element @ (StreamElement::Note(_) | StreamElement::Chord(_) | StreamElement::Rest(_)),
        ) => Some(
            element
                .duration()
                .map(Duration::tuplets)
                .unwrap_or_default(),
        ),
        _ => None,
    };
    let mut groups: Vec<Vec<usize>> = Vec::new();
    let mut current: Vec<usize> = Vec::new();
    for (index, thing) in things.iter().enumerate() {
        let Some(held) = tuplets(thing) else {
            continue;
        };
        let Some(first) = held.first() else {
            if !current.is_empty() {
                groups.push(std::mem::take(&mut current));
            }
            continue;
        };
        current.push(index);
        if first.tuplet_type() == Some(TupletType::Stop) {
            groups.push(std::mem::take(&mut current));
        }
    }
    if !current.is_empty() {
        groups.push(current);
    }
    let ordinal = |kind: DurationType| DurationType::ALL.iter().position(|held| *held == kind);
    for group in groups {
        let Some(first) = tuplets(&things[group[0]]).and_then(|held| held.into_iter().next())
        else {
            continue;
        };
        let total = op_frac(first.total_tuplet_length());
        let mut length = 0.0;
        let mut smallest: Option<usize> = None;
        let mut largest: Option<usize> = None;
        for index in &group {
            length = op_frac(length + things[*index].length());
            let Some(kind) = tuplets(&things[*index])
                .and_then(|held| held.into_iter().next())
                .and_then(|tuplet| ordinal(tuplet.duration_type()))
            else {
                continue;
            };
            smallest = Some(smallest.map_or(kind, |held| held.max(kind)));
            largest = Some(largest.map_or(kind, |held| held.min(kind)));
        }
        if length == total || total == 0.0 {
            continue;
        }
        let excess = op_frac(length / total);
        let inverse = op_frac(1.0 / excess);
        let chosen = if excess.fract() == 0.0 {
            largest
        } else if inverse.fract() == 0.0 {
            smallest
        } else {
            None
        };
        let Some(kind) = chosen.map(|index| DurationType::ALL[index]) else {
            continue;
        };
        for index in group {
            if let Thing::Element(element) = &mut things[index].thing {
                with_duration(element, |duration| {
                    let mut held = duration.tuplets();
                    if let Some(first) = held.first_mut() {
                        let normal = first.duration_normal().map_or(0, |(_, dots)| dots);
                        let actual = first.duration_actual().map_or(0, |(_, dots)| dots);
                        first.set_duration_normal(Some((kind, normal)));
                        first.set_duration_actual(Some((kind, actual)));
                    }
                    duration.set_tuplets(held);
                });
            }
        }
    }
}

/// music21's `makeVoices`: the things of a split spine, in the voices they
/// came from.
fn measure_stream(gathered: Gathered) -> Stream {
    let mut things = gathered.things;
    sort(&mut things);
    fix_tuplets(&mut things);
    let lowest = things
        .iter()
        .find(|thing| thing.voice == Some(1))
        .map(|thing| thing.offset);
    let mut voices: BTreeMap<usize, Vec<Placed>> = BTreeMap::new();
    let mut own: Vec<Placed> = Vec::new();
    for thing in things {
        match (lowest, thing.voice) {
            (Some(lowest), Some(voice)) => voices.entry(voice).or_default().push(Placed {
                offset: thing.offset - lowest,
                ..thing
            }),
            _ => own.push(thing),
        }
    }
    let events = |things: Vec<Placed>| -> Vec<(FloatType, usize, i32, StreamElement)> {
        things
            .into_iter()
            .filter_map(|thing| {
                let priority = thing.priority;
                let element = element_of(thing.thing, priority)?;
                Some((thing.offset, priority, element.class_sort_order(), element))
            })
            .collect()
    };
    let mut held = events(own);
    for (_, things) in voices {
        let voice = Stream::with_kind(StreamKind::Voice).with_events(
            events(things)
                .into_iter()
                .map(|(offset, priority, _, element)| placed_event(offset, priority, element))
                .collect(),
        );
        held.push((lowest.unwrap_or(0.0), 0, 5, voice.into()));
    }
    held.sort_by(|left, right| {
        left.0
            .total_cmp(&right.0)
            .then(left.1.cmp(&right.1))
            .then(left.2.cmp(&right.2))
    });
    let mut measure = Stream::with_kind(StreamKind::Measure).with_events(
        held.into_iter()
            .map(|(offset, priority, _, element)| placed_event(offset, priority, element))
            .collect(),
    );
    measure.set_number(gathered.measure.number);
    measure.set_number_suffix(gathered.measure.suffix);
    measure.set_left_barline(gathered.measure.left);
    measure.set_right_barline(gathered.measure.right);
    measure
}

/// An element where it stands, sorted by the line it was written on.
fn placed_event(offset: FloatType, priority: usize, element: StreamElement) -> StreamEvent {
    StreamEvent::new(offset, element).with_priority(i32::try_from(priority).unwrap_or(i32::MAX))
}

/// What a thing stands in the score as: an element as itself, an
/// instruction as a `MiscTandem` sorted by its priority, and nothing for
/// the rest.
fn element_of(thing: Thing, priority: usize) -> Option<StreamElement> {
    match thing {
        Thing::Element(element) => Some(element),
        Thing::Tandem(tandem) => Some(MiscTandem::new(tandem, priority as i32).into()),
        Thing::Measure(_) | Thing::Word(_) => None,
    }
}

/// A first measure shorter than the bar of the meter it opens with is a
/// pickup, padded on the left by what it lacks: music21's
/// `moveElementsIntoMeasures`.
fn pad_pickup(measure: &mut Stream, length: FloatType) {
    let opening = measure
        .events()
        .iter()
        .find_map(|event| match event.element() {
            StreamElement::TimeSignature(meter) if event.offset() == 0.0 => Some(meter),
            _ => None,
        });
    let Some(meter) = opening else {
        return;
    };
    let bar = meter.bar_duration().quarter_length();
    if length < bar {
        measure.set_padding_left(op_frac(bar - length));
    }
}

/// The staff a spine says it belongs to, or the staves.
fn staves_of(things: &[Placed]) -> Vec<IntegerType> {
    things
        .iter()
        .find_map(|thing| match &thing.thing {
            Thing::Tandem(tandem) => tandem.strip_prefix("*staff"),
            _ => None,
        })
        .map(|staves| {
            staves
                .split('/')
                .filter_map(|staff| staff.parse().ok())
                .collect()
        })
        .unwrap_or_default()
}

/// music21's `GlobalReference.updateMetadata`: a `!!!` line as a fact about
/// the piece.
fn reference(metadata: &mut Metadata, line: &str) -> Result<()> {
    let text = line.trim_start_matches('!');
    let (code, value) = text
        .split_once(':')
        .ok_or_else(|| humdrum_error(format!("a reference line with no code: {line}")))?;
    let code = code.trim().replace("@@", "@");
    let code = code.split('@').next().unwrap_or("");
    let value = value.trim();
    match REFERENCE_NAMES.iter().find(|(held, _)| *held == code) {
        Some((_, "")) => metadata.add_text(format!("humdrum:{code}"), value),
        Some((_, name)) if is_contributor_unique_name(name) => {
            metadata.add_contributor(*name, value);
        }
        Some((_, name)) => metadata.add_text(*name, value),
        None => metadata.add_text(code, value),
    }
    Ok(())
}

/// music21's `parseNonOpus`: one table as a score.
fn score_of(lines: &[&str]) -> Result<Stream> {
    let mut metadata = Metadata::new();
    let mut rows: Vec<(usize, Vec<String>)> = Vec::new();
    let mut globals: Vec<GlobalLine> = Vec::new();
    let mut run = 0;
    let mut width = 0;
    for (index, line) in lines.iter().enumerate() {
        let line = line.trim_end();
        if line.is_empty() {
            run = 0;
            continue;
        }
        if line.starts_with("!!") {
            run += 1;
        } else {
            run = 0;
        }
        if line.starts_with("!!!") {
            reference(&mut metadata, line)
                .map_err(|error| error.placed(|| Position::line(index + 1)))?;
        } else if line.starts_with("!!") {
            globals.push(GlobalLine {
                line: index + 1,
                run,
                comment: comment_text(line).to_string(),
            });
        } else {
            let cells: Vec<String> = line
                .split('\t')
                .enumerate()
                .filter(|(place, cell)| *place == 0 || !cell.is_empty())
                .map(|(_, cell)| cell.to_string())
                .collect();
            width = width.max(cells.len());
            rows.push((index + 1, cells));
        }
    }
    let mut spines = spines_of(&rows, width)?;
    for index in 0..spines.len() {
        spines[index].kind = kind_of(&spines, index)?;
    }
    for spine in &mut spines {
        spine.stream = match spine.kind.as_str() {
            "kern" => parse_kern(&spine.events),
            "dynam" => parse_other(&spine.events, true),
            "harm" => parse_harm(&spine.events)?,
            _ => parse_other(&spine.events, false),
        };
    }
    let places = line_places(&spines);
    for index in 0..spines.len() {
        if spines[index].parent.is_none() {
            insert_voices(&mut spines, index);
        }
    }

    // The top spines as measures, with what stands outside them.
    let mut parts: Vec<(usize, Vec<Gathered>, Vec<Placed>)> = Vec::new();
    for (index, spine) in spines.iter().enumerate() {
        if spine.parent.is_none() && spine.kind == "kern" {
            let (measures, loose) = into_measures(spine.stream.clone());
            parts.push((index, measures, loose));
        }
    }
    // Which part each staff is: the first `*staff` a spine leaves standing
    // outside its measures.
    let staff_of = |loose: &[Placed]| -> Option<IntegerType> {
        loose.iter().find_map(|thing| match &thing.thing {
            Thing::Tandem(tandem) => tandem
                .strip_prefix("*staff")
                .and_then(|staff| staff.parse().ok()),
            _ => None,
        })
    };
    for spine in spines
        .iter()
        .filter(|spine| spine.parent.is_none() && spine.kind != "kern")
    {
        let staves = staves_of(&spine.stream);
        let is_words = matches!(spine.kind.as_str(), "lyrics" | "text");
        let is_marks = matches!(spine.kind.as_str(), "dynam" | "harm");
        if !is_marks && !is_words {
            continue;
        }
        for staff in staves {
            let Some((_, measures, _)) = parts
                .iter_mut()
                .find(|(_, _, loose)| staff_of(loose) == Some(staff))
            else {
                if is_marks {
                    return Err(humdrum_error(format!(
                        "no staff {staff} for the {} spine",
                        spine.kind
                    )));
                }
                continue;
            };
            for thing in &spine.stream {
                for measure in measures.iter_mut() {
                    let found = measure
                        .things
                        .iter()
                        .position(|held| held.priority == thing.line);
                    match (&thing.thing, found) {
                        (
                            Thing::Element(
                                mark @ (StreamElement::Dynamic(_) | StreamElement::Chord(_)),
                            ),
                            Some(found),
                        ) => {
                            let offset = measure.things[found].offset;
                            // music21's `HarmSpine` gives its numerals the
                            // line they were written on as their priority,
                            // which sorts them after the meter and the key
                            // standing at the same offset; its `DynamSpine`
                            // gives a dynamic none.
                            let priority = match mark {
                                StreamElement::Chord(_) => thing.line,
                                _ => 0,
                            };
                            measure.things.push(Placed {
                                offset,
                                line: thing.line,
                                priority,
                                voice: None,
                                thing: Thing::Element(mark.clone()),
                            });
                            break;
                        }
                        (Thing::Word(word), Some(_)) => {
                            for held in &mut measure.things {
                                if held.priority != thing.line {
                                    continue;
                                }
                                match &mut held.thing {
                                    Thing::Element(StreamElement::Note(note)) => {
                                        note.set_lyric(Some(word))?;
                                    }
                                    Thing::Element(StreamElement::Rest(rest)) => {
                                        rest.set_lyric(Some(word));
                                    }
                                    Thing::Element(StreamElement::Chord(chord)) => {
                                        if let Some(singer) = chord.notes_mut().first_mut() {
                                            singer.set_lyric(Some(word))?;
                                        }
                                    }
                                    _ => {}
                                }
                            }
                        }
                        _ => {}
                    }
                }
            }
        }
    }

    // The parts come out in the order opposite to the file's, which is
    // written lowest part first.
    let mut events = Vec::new();
    for (spine, measures, loose) in parts.into_iter().rev() {
        // The instructions before the first barline stay in the part, ahead
        // of its measures, where music21 leaves them.
        let mut held: Vec<StreamEvent> = loose
            .into_iter()
            .filter(|thing| matches!(thing.thing, Thing::Tandem(_)))
            .filter_map(|thing| {
                let element = element_of(thing.thing, thing.priority)?;
                Some(placed_event(thing.offset, thing.priority, element))
            })
            .collect();
        let mut offset = 0.0;
        for (index, gathered) in measures.into_iter().enumerate() {
            let priority = gathered.priority;
            let mut measure = measure_stream(gathered);
            let length = measure.end_offset();
            if index == 0 {
                pad_pickup(&mut measure, length);
            }
            held.push(placed_event(offset, priority, measure.into()));
            offset = op_frac(offset + length);
        }
        let mut part = Stream::with_kind(StreamKind::Part).with_events(held);
        // music21 names a part by the spine it was read from.
        part.set_id(Some(format!("spine_{spine}")));
        events.push(StreamEvent::new(0.0, part));
    }
    place_comments(&mut events, &globals, &places);
    let mut score = Stream::with_kind(StreamKind::Score).with_events(events);
    score.set_metadata(Some(metadata));
    Ok(score)
}

/// A `!!` line: its line number, how many global lines run into it, and
/// what it says.
struct GlobalLine {
    line: usize,
    run: usize,
    comment: String,
}

/// music21's `GlobalCommentLine.value`: the line without its bangs and the
/// one space after them.
fn comment_text(line: &str) -> &str {
    let text = line.trim_start_matches('!');
    text.strip_prefix(char::is_whitespace).unwrap_or(text)
}

/// music21's `getOffsetsAndPrioritiesByLineNumber`: the offset and priority
/// of the first thing each line holds, the top spines read in order and
/// their measures passed over.
fn line_places(spines: &[Spine]) -> BTreeMap<usize, (FloatType, usize)> {
    let mut places = BTreeMap::new();
    let tops = spines.iter().filter(|spine| spine.parent.is_none());
    for placed in tops.flat_map(|spine| &spine.stream) {
        if matches!(placed.thing, Thing::Measure(_)) {
            continue;
        }
        places
            .entry(placed.line)
            .or_insert((placed.offset, placed.priority));
    }
    places
}

/// music21's `insertGlobalEvents`: each comment before the next line that
/// holds anything, 40 ahead of its priority and one back for each global
/// line running into it; a comment with no such line goes at the end.
///
/// ```text
/// !!a        -> offset of `4c`, priority 6 - 40 + 1
/// !!!COM: X     (counted in the run, but metadata)
/// !!b        -> offset of `4c`, priority 6 - 40 + 3
/// 4c            (line 6)
/// ```
fn place_comments(
    events: &mut Vec<StreamEvent>,
    globals: &[GlobalLine],
    places: &BTreeMap<usize, (FloatType, usize)>,
) {
    const AHEAD: i32 = 40;
    let key = |event: &StreamEvent| match event.element() {
        StreamElement::GlobalComment(said) => (event.offset(), said.priority()),
        _ => (event.offset(), 0),
    };
    let mut trailing = Vec::new();
    for global in globals {
        let Some((_, (offset, priority))) = places.range(global.line..).next() else {
            trailing.push(GlobalComment::new(global.comment.clone(), 0));
            continue;
        };
        let priority = *priority as i32 - AHEAD + global.run as i32;
        let comment = GlobalComment::new(global.comment.clone(), priority);
        let index = events
            .iter()
            .position(|event| {
                let (held, ahead) = key(event);
                held > *offset || (held == *offset && ahead > priority)
            })
            .unwrap_or(events.len());
        events.insert(index, StreamEvent::new(*offset, comment));
    }
    let end = events
        .iter()
        .map(StreamEvent::end_offset)
        .fold(0.0, FloatType::max);
    for comment in trailing {
        events.push(StreamEvent::new(end, comment));
    }
}

/// Reads a Humdrum file into a score: music21's `converter.parse` of one.
///
/// Every `**kern` spine is a part, the last in the file first; its barlines
/// are the measures, its instructions the clefs, keys, meters, tempos and
/// instruments, and a spine split in two is two voices in the measures where
/// it is split. `**dynam` and `**text` spines put their dynamics and words
/// on the notes of the staff they name. A cell that cannot be read is passed
/// over, as music21 passes over it.
///
/// A file holding several tables, each closed before the next opens, comes
/// back as an opus of scores. `**harm` spines, and a voice that splits
/// again, are not read.
///
/// ```
/// use music21::humdrum::from_humdrum;
///
/// let score = from_humdrum("**kern\n*clefG2\n*M2/4\n=1\n4c\n4d\n=2\n2e\n==\n*-\n")?;
/// let part = score.parts()[0];
/// assert_eq!(part.measures().len(), 2);
/// assert_eq!(part.measures()[1].pitches()[0].name_with_octave(), "E4");
/// # Ok::<(), music21::Error>(())
/// ```
pub fn from_humdrum(text: &str) -> Result<Stream> {
    let lines: Vec<&str> = text.lines().collect();
    if lines.is_empty() {
        return Err(humdrum_error("Need a list of lines to parse!"));
    }
    // music21's `determineIfDataStreamIsOpus`: a line of nothing but `**`
    // headings opens a table, one of nothing but `*-` closes it.
    let all = |line: &str, test: fn(&str) -> bool| {
        let line = line.trim_end();
        !line.is_empty() && line.split('\t').all(test)
    };
    let heading: fn(&str) -> bool = |cell| {
        cell.strip_prefix("**").is_some_and(|name| {
            !name.is_empty() && name.chars().all(|c| c.is_alphanumeric() || c == '_')
        })
    };
    let starts: Vec<usize> = (0..lines.len())
        .filter(|index| all(lines[*index], heading))
        .collect();
    let mut ends: Vec<usize> = (0..lines.len())
        .filter(|index| all(lines[*index], |cell| cell == "*-"))
        .collect();
    if starts.len() < 2 {
        return score_of(&lines);
    }
    if ends.last().copied().unwrap_or(0) <= starts[starts.len() - 1] {
        ends.push(lines.len());
    }
    // Each piece, with how many lines of the document stand before it.
    let mut pieces: Vec<(usize, &[&str])> = Vec::new();
    for (index, end) in ends.iter().enumerate() {
        let start = if index == 0 { 0 } else { ends[index - 1] + 1 };
        let stop = if index + 1 == ends.len() {
            lines.len()
        } else {
            (*end + 1).min(lines.len())
        };
        pieces.push((start.min(stop), &lines[start.min(stop)..stop]));
    }
    if pieces.len() < 2 {
        return Err(humdrum_error(
            "Malformed Humdrum data: possibly multiple **tags without closing information.",
        ));
    }
    let mut events = Vec::new();
    let mut offset = 0.0;
    for (index, (before, piece)) in pieces.iter().enumerate() {
        let mut score = score_of(piece).map_err(|error| error.lines_down(*before))?;
        let mut metadata = score.metadata().cloned().unwrap_or_default();
        metadata.set(
            "number",
            vec![crate::metadata::MetadataValue::new((index + 1).to_string())],
        );
        score.set_metadata(Some(metadata));
        score.set_id(Some(format!("section_{}", index + 1)));
        let length = score.end_offset();
        events.push(StreamEvent::new(offset, score));
        offset = op_frac(offset + length);
    }
    // The opus says what its first score says, numbered `0`.
    let mut metadata = events
        .first()
        .and_then(|event| event.element().as_stream())
        .and_then(Stream::metadata)
        .cloned()
        .unwrap_or_default();
    metadata.set(
        "number",
        vec![crate::metadata::MetadataValue::new("0".to_string())],
    );
    let mut opus = Stream::with_kind(StreamKind::Opus).with_events(events);
    opus.set_metadata(Some(metadata));
    Ok(opus)
}

#[cfg(test)]
mod tests {
    /// A `!!` line stands in the score at the offset of the next line
    /// holding anything, before what stands there, as music21's
    /// `insertGlobalEvents` puts it; one after the music goes at the end.
    #[test]
    fn global_comments_stand_in_the_score() {
        let text = "!!first\n**kern\n*M2/4\n=1\n!!mid\n4c\n!!second\n!!!COM: X\n\
                    !!third\n4d\n=2\n2e\n==\n*-\n!!last\n";
        let score = from_humdrum(text).unwrap();
        let seen: Vec<(FloatType, String, i32)> = score
            .events()
            .iter()
            .map(|event| match event.element() {
                StreamElement::GlobalComment(said) => {
                    (event.offset(), said.comment().to_string(), said.priority())
                }
                _ => (event.offset(), "part".to_string(), 0),
            })
            .collect();
        let expected = [
            (0.0, "first", -37),
            (0.0, "mid", -33),
            (0.0, "part", 0),
            (1.0, "second", -29),
            (1.0, "third", -27),
            (4.0, "last", 0),
        ];
        let expected: Vec<(FloatType, String, i32)> = expected
            .iter()
            .map(|(offset, said, priority)| (*offset, said.to_string(), *priority))
            .collect();
        assert_eq!(seen, expected);
    }

    /// An instruction the reader has no object for stands where it was
    /// written as a `MiscTandem`, its line its priority, as music21 keeps
    /// it: those before the first barline in the part, the rest in their
    /// measure.
    #[test]
    fn tandems_stand_where_they_were_written() {
        let text = "**kern\t**dynam\n*staff1\t*staff1\n*clefG2\t*\n*Xtandy\t*\n\
                    *M2/4\t*\n=1\t=1\n4c\tp\n*foo\t*\n4d\t.\n==\t==\n*-\t*-\n";
        let score = from_humdrum(text).unwrap();
        let tandems = |stream: &Stream| -> Vec<(FloatType, String, i32)> {
            stream
                .events()
                .iter()
                .filter_map(|event| match event.element() {
                    StreamElement::MiscTandem(tandem) => Some((
                        event.offset(),
                        tandem.tandem().to_string(),
                        tandem.priority(),
                    )),
                    _ => None,
                })
                .collect()
        };
        let part = score.events()[0].element().as_stream().unwrap();
        let measure = part
            .events()
            .iter()
            .find_map(|event| event.element().as_stream())
            .unwrap();
        let owned = |held: &[(FloatType, &str, i32)]| -> Vec<(FloatType, String, i32)> {
            held.iter()
                .map(|(offset, said, priority)| (*offset, said.to_string(), *priority))
                .collect()
        };
        assert_eq!(
            tandems(part),
            owned(&[(0.0, "**kern", 1), (0.0, "*staff1", 2), (0.0, "*Xtandy", 4)])
        );
        assert_eq!(tandems(measure), owned(&[(1.0, "*foo", 8)]));
    }

    /// An opus is named as music21 names it: its scores `section_1` on,
    /// and its own metadata a copy of the first score's, numbered `0`.
    #[test]
    fn an_opus_takes_its_first_scores_metadata() {
        let text = "!!!OTL: Piece\n**kern\n4c\n*-\n!!!OTL: Other\n**kern\n4d\n*-\n";
        let opus = from_humdrum(text).unwrap();
        let read = |stream: &Stream, name: &str| -> String {
            stream.metadata().unwrap().get(name)[0].text().to_string()
        };
        assert_eq!(read(&opus, "title"), "Piece");
        assert_eq!(read(&opus, "number"), "0");
        let ids: Vec<Option<&str>> = opus
            .events()
            .iter()
            .filter_map(|event| event.element().as_stream())
            .map(Stream::id)
            .collect();
        assert_eq!(ids, [Some("section_1"), Some("section_2")]);
    }

    /// A first measure shorter than its bar is a pickup, padded on the left
    /// by what it lacks, as music21's `moveElementsIntoMeasures` pads it.
    #[test]
    fn a_short_first_measure_is_padded_as_a_pickup() {
        let padding = |body: &str| {
            let text = format!("**kern\n*M2/4\n{body}\n=1\n2d\n=2\n*-\n");
            let score = from_humdrum(&text).unwrap();
            let part = score.parts()[0].clone();
            part.measures()
                .iter()
                .map(|measure| measure.padding_left())
                .collect::<Vec<_>>()
        };
        assert_eq!(padding("4c"), [1.0, 0.0]);
        assert_eq!(
            padding("12c"),
            [crate::makenotation::op_frac(5.0 / 3.0), 0.0]
        );
        assert_eq!(padding("2c"), [0.0, 0.0]);
    }

    use super::*;

    #[test]
    fn a_length_is_a_number_and_its_dots() {
        assert_eq!(duration_of("4c").unwrap().quarter_length(), 1.0);
        assert_eq!(duration_of("8.d").unwrap().quarter_length(), 0.75);
        assert_eq!(duration_of("0r").unwrap().quarter_length(), 8.0);
        // Twelfths are eighths, three in the time of two.
        let triplet = duration_of("12e").unwrap();
        assert!((triplet.quarter_length() - 1.0 / 3.0).abs() < 1e-9);
        assert_eq!(triplet.tuplets()[0].actual(), 3);
        assert!(duration_of("qf").unwrap().is_grace());
        assert!(duration_of("c").is_err());
    }

    #[test]
    fn a_refusal_names_its_line_in_the_whole_document() {
        let unpaired = "**kern\t**kern\n*x\t*\n4c\t4d\n*-\t*-\n";
        let error = from_humdrum(unpaired).unwrap_err();
        assert_eq!(
            error.to_string(),
            "Humdrum error: ProtoSpine found with unpaired exchange instruction at line 2"
        );
        assert_eq!(error.position(), Some(&Position::line(2)));

        let opus = format!("**kern\n4c\n*-\n{unpaired}");
        let error = from_humdrum(&opus).unwrap_err();
        assert_eq!(error.position(), Some(&Position::line(5)));
    }

    #[test]
    fn letters_say_the_octave() {
        let name = |token: &str| match note_of(token, None).unwrap() {
            StreamElement::Note(note) => note.pitch().name_with_octave(),
            _ => "rest".to_string(),
        };
        assert_eq!(name("4c"), "C4");
        assert_eq!(name("4cc#"), "C#5");
        assert_eq!(name("4C"), "C3");
        assert_eq!(name("4BB-"), "Bb2");
        assert_eq!(name("4r"), "rest");
    }

    #[test]
    fn a_grace_note_leaves_a_tuplet_whole() {
        // music21's `testGraceNoteInsideTuplet`.
        let types = |cells: &[&str]| -> Vec<Option<&'static str>> {
            let events: Vec<(String, usize)> = cells
                .iter()
                .enumerate()
                .map(|(line, cell)| (cell.to_string(), line))
                .collect();
            parse_kern(&events)
                .iter()
                .filter_map(|placed| match &placed.thing {
                    Thing::Element(element) => Some(
                        element
                            .duration()?
                            .tuplets()
                            .first()
                            .and_then(|tuplet| tuplet.tuplet_type())
                            .map(TupletType::as_str),
                    ),
                    _ => None,
                })
                .collect()
        };
        assert_eq!(
            types(&["12c", "12qd", "12e", "12f", "4g"]),
            [Some("start"), None, None, Some("stop"), None]
        );
        assert_eq!(
            types(&["12c", "12e", "12qd", "12f", "4g"]),
            [Some("start"), None, None, Some("stop"), None]
        );
        // A grace note after an unfinished tuplet: it still stops on its last note.
        assert_eq!(
            types(&["12c", "12e", "16qd", "4g"]),
            [Some("start"), Some("stop"), None, None]
        );
    }

    #[test]
    fn a_barline_says_how_the_measure_before_ends() {
        let (measure, right) = measure_of("=12a:|!", true);
        assert_eq!(measure.number, 12);
        assert_eq!(measure.suffix.as_deref(), Some("a"));
        assert_eq!(right.repeat_direction(), Some(RepeatDirection::End));
        let (_, double) = measure_of("==", true);
        assert_eq!(double.bar_type(), BarlineType::Double);
    }

    #[test]
    fn spines_are_parts_and_the_last_comes_first() {
        let score = from_humdrum(
            "**kern\t**kern\n*clefF4\t*clefG2\n*M2/4\t*M2/4\n=1\t=1\n2C\t4c\n.\t4d\n=2\t=2\n\
             2D\t2e\n==\t==\n*-\t*-\n",
        )
        .unwrap();
        let parts = score.parts();
        assert_eq!(parts.len(), 2);
        assert_eq!(parts[0].measures()[0].pitches().len(), 2);
        assert_eq!(parts[1].measures()[0].pitches()[0].name_with_octave(), "C3");
    }

    /// music21 gives each thing it reads the line it was written on as its
    /// priority, a measure that of its barline, and names a part by its
    /// spine.
    #[test]
    fn what_is_read_keeps_its_line_and_its_spine() {
        let score = from_humdrum(
            "**kern\t**kern\n*clefF4\t*clefG2\n*M2/4\t*M2/4\n=1\t=1\n2C\t4c\n.\t4d\n=2\t=2\n\
             2D\t2e\n==\t==\n*-\t*-\n",
        )
        .unwrap();
        let parts = score.parts();
        assert_eq!(parts[0].id(), Some("spine_1"));
        assert_eq!(parts[1].id(), Some("spine_0"));
        let measures: Vec<i32> = parts[0]
            .events()
            .iter()
            .filter(|event| event.element().as_stream().is_some())
            .map(StreamEvent::priority)
            .collect();
        assert_eq!(measures, [4, 7]);
        let first = parts[0].measures()[0];
        let lines: Vec<i32> = first.events().iter().map(StreamEvent::priority).collect();
        // The clef, the meter and the two notes.
        assert_eq!(lines, [2, 3, 5, 6]);
    }

    /// A `!` comment in a `**kern` spine stands where it was written, as
    /// music21's `SpineComment`; an empty one is passed over.
    #[test]
    fn a_spine_comment_stands_where_it_was_written() {
        let score = from_humdrum("**kern\n*M2/4\n!Cantus\n!\n=1\n2c\n==\n*-\n").unwrap();
        let said: Vec<(&str, i32)> = score.parts()[0].measures()[0]
            .events()
            .iter()
            .filter_map(|event| match event.element() {
                StreamElement::SpineComment(said) => Some((said.comment(), event.priority())),
                _ => None,
            })
            .collect();
        assert_eq!(said, [("Cantus", 3)]);
    }

    #[test]
    fn a_split_spine_is_two_voices() {
        let score = from_humdrum("**kern\n*M2/4\n=1\n*^\n4c\t4e\n4d\t4f\n*v\t*v\n=2\n2g\n==\n*-\n")
            .unwrap();
        let part = score.parts()[0];
        let measures = part.measures();
        assert_eq!(measures[0].voices().len(), 2);
        assert!(measures[1].voices().is_empty());
    }
}