Skip to main content

solow_formula/
design.rs

1//! Design-matrix construction: the patsy coding pipeline.
2//!
3//! The flow mirrors patsy's `build.py`:
4//!
5//! 1. parse the formula into terms,
6//! 2. bucket terms by their set of *numeric* factors (the empty bucket first,
7//!    other buckets in first-appearance order), and within a bucket sort
8//!    stably by interaction degree,
9//! 3. for each term pick categorical contrast codings that avoid structural
10//!    redundancy ([`crate::redundancy::pick_contrasts_for_term`]),
11//! 4. expand each subterm into concrete columns with patsy's column ordering
12//!    (left-most factor iterates fastest), and
13//! 5. evaluate the columns over the data.
14
15use crate::ast::{Expr, Factor};
16use crate::contrasts::Coding;
17use crate::data::DataFrame;
18use crate::eval::eval_column;
19use crate::parser::parse;
20use crate::redundancy::{pick_contrasts_for_term, UsedSubterms};
21use crate::terms::Term;
22use ndarray::{Array1, Array2};
23use solow_core::{Error, Result};
24use std::collections::BTreeSet;
25
26/// The result of [`build`].
27#[derive(Debug, Clone)]
28pub struct DesignOutput {
29    /// The response column, if the formula had a `~` left-hand side.
30    pub y: Option<Array1<f64>>,
31    /// The design matrix (rows = observations, columns = model terms).
32    pub design: Array2<f64>,
33    /// Column names, in patsy order.
34    pub names: Vec<String>,
35}
36
37/// Build a design matrix from a formula string and a [`DataFrame`].
38///
39/// Returns the (optional) response vector, the numeric design matrix, and the
40/// column names — matching patsy's `dmatrices` output exactly.
41pub fn build(formula: &str, data: &DataFrame) -> Result<DesignOutput> {
42    let parsed = parse(formula)?;
43    let nrows = data
44        .nrows()
45        .ok_or_else(|| Error::Value("data frame has no columns".into()))?;
46    check_lengths(data, nrows)?;
47
48    let y = match &parsed.response {
49        Some(f) => Some(eval_response(f, data, nrows)?),
50        None => None,
51    };
52
53    // Full ordered term list (intercept first if present).
54    let mut terms: Vec<Term> = Vec::new();
55    if parsed.rhs.intercept {
56        terms.push(Term::intercept());
57    }
58    terms.extend(parsed.rhs.terms.iter().cloned());
59
60    for t in &terms {
61        for f in &t.factors {
62            check_factor(f, data)?;
63        }
64    }
65
66    let ordered = order_terms(&terms, data);
67
68    let mut columns: Vec<Vec<f64>> = Vec::new();
69    let mut names: Vec<String> = Vec::new();
70    build_all(&ordered, data, nrows, &mut columns, &mut names)?;
71
72    let ncols = columns.len();
73    let mut flat = Vec::with_capacity(nrows * ncols);
74    for row in 0..nrows {
75        for col in &columns {
76            flat.push(col[row]);
77        }
78    }
79    let design = Array2::from_shape_vec((nrows, ncols), flat)
80        .map_err(|e| Error::Shape(format!("design matrix assembly: {e}")))?;
81
82    Ok(DesignOutput { y, design, names })
83}
84
85// --------------------------------------------------------------------------
86// Validation
87// --------------------------------------------------------------------------
88
89fn check_lengths(data: &DataFrame, nrows: usize) -> Result<()> {
90    for name in &data.order {
91        let len = if let Some(c) = data.numeric_col(name) {
92            c.len()
93        } else if let Some(c) = data.categorical_col(name) {
94            c.len()
95        } else {
96            continue;
97        };
98        if len != nrows {
99            return Err(Error::Shape(format!(
100                "column `{name}` has length {len}, expected {nrows}"
101            )));
102        }
103    }
104    Ok(())
105}
106
107fn check_factor(f: &Factor, data: &DataFrame) -> Result<()> {
108    match f {
109        Factor::Numeric(n) => {
110            if data.is_categorical(n) {
111                return Err(Error::Value(format!(
112                    "`{n}` is categorical; reference it as C({n})"
113                )));
114            }
115            if !data.has(n) {
116                return Err(Error::Value(format!("unknown variable `{n}`")));
117            }
118        }
119        Factor::Categorical { var, .. } => {
120            if !data.has(var) {
121                return Err(Error::Value(format!("unknown variable `{var}`")));
122            }
123        }
124        Factor::Identity { expr, .. } => check_expr_vars(expr, data)?,
125    }
126    Ok(())
127}
128
129fn check_expr_vars(expr: &Expr, data: &DataFrame) -> Result<()> {
130    match expr {
131        Expr::Num(_) => Ok(()),
132        Expr::Var(n) => {
133            if data.numeric_col(n).is_none() {
134                Err(Error::Value(format!(
135                    "I(...): `{n}` is not a numeric column"
136                )))
137            } else {
138                Ok(())
139            }
140        }
141        Expr::Neg(a) => check_expr_vars(a, data),
142        Expr::Add(a, b) | Expr::Sub(a, b) | Expr::Mul(a, b) | Expr::Div(a, b) | Expr::Pow(a, b) => {
143            check_expr_vars(a, data)?;
144            check_expr_vars(b, data)
145        }
146    }
147}
148
149fn eval_response(f: &Factor, data: &DataFrame, nrows: usize) -> Result<Array1<f64>> {
150    match f {
151        Factor::Numeric(n) => {
152            let col = data
153                .numeric_col(n)
154                .ok_or_else(|| Error::Value(format!("response `{n}` is not numeric")))?;
155            Ok(Array1::from(col.to_vec()))
156        }
157        Factor::Identity { expr, .. } => Ok(Array1::from(eval_column(expr, data, nrows)?)),
158        Factor::Categorical { var, .. } => Err(Error::NotImplemented(format!(
159            "categorical response C({var}) is not supported"
160        ))),
161    }
162}
163
164// --------------------------------------------------------------------------
165// Term ordering (patsy buckets)
166// --------------------------------------------------------------------------
167
168fn is_numeric_factor(f: &Factor) -> bool {
169    matches!(f, Factor::Numeric(_) | Factor::Identity { .. })
170}
171
172fn numeric_key(t: &Term) -> BTreeSet<String> {
173    t.factors
174        .iter()
175        .filter(|f| is_numeric_factor(f))
176        .map(|f| f.key())
177        .collect()
178}
179
180/// patsy term ordering: bucket by the set of numeric factors (empty bucket
181/// first, others in first-appearance order), then within a bucket sort stably
182/// by interaction degree.
183fn order_terms(terms: &[Term], _data: &DataFrame) -> Vec<Term> {
184    let mut bucket_order: Vec<BTreeSet<String>> = Vec::new();
185    for t in terms {
186        let k = numeric_key(t);
187        if !bucket_order.contains(&k) {
188            bucket_order.push(k);
189        }
190    }
191    let empty: BTreeSet<String> = BTreeSet::new();
192    if let Some(pos) = bucket_order.iter().position(|k| k == &empty) {
193        let e = bucket_order.remove(pos);
194        bucket_order.insert(0, e);
195    }
196
197    let mut out = Vec::new();
198    for bucket in &bucket_order {
199        let mut bterms: Vec<Term> = terms
200            .iter()
201            .filter(|t| &numeric_key(t) == bucket)
202            .cloned()
203            .collect();
204        bterms.sort_by_key(|t| t.factors.len()); // stable, by degree
205        out.extend(bterms);
206    }
207    out
208}
209
210// --------------------------------------------------------------------------
211// Column construction
212// --------------------------------------------------------------------------
213
214fn build_all(
215    ordered: &[Term],
216    data: &DataFrame,
217    nrows: usize,
218    columns: &mut Vec<Vec<f64>>,
219    names: &mut Vec<String>,
220) -> Result<()> {
221    // Walk contiguous buckets (already grouped by `order_terms`); the
222    // redundancy state is shared within a bucket.
223    let mut i = 0;
224    while i < ordered.len() {
225        let key = numeric_key(&ordered[i]);
226        let start = i;
227        while i < ordered.len() && numeric_key(&ordered[i]) == key {
228            i += 1;
229        }
230        let mut used = UsedSubterms::default();
231        for term in &ordered[start..i] {
232            emit_term(term, data, nrows, &mut used, columns, names)?;
233        }
234    }
235    Ok(())
236}
237
238/// Emit all columns of one term, consulting and updating the shared `used` set.
239fn emit_term(
240    term: &Term,
241    data: &DataFrame,
242    nrows: usize,
243    used: &mut UsedSubterms,
244    columns: &mut Vec<Vec<f64>>,
245    names: &mut Vec<String>,
246) -> Result<()> {
247    // Categorical factor keys in term order (used for the redundancy lattice).
248    let cat_keys: Vec<String> = term
249        .factors
250        .iter()
251        .filter(|f| matches!(f, Factor::Categorical { .. }))
252        .map(|f| f.key())
253        .collect();
254
255    // One coding per subterm; each maps cat-key -> full(bool).
256    let codings = pick_contrasts_for_term(&cat_keys, used);
257
258    for coding in &codings {
259        // Build the subterm by walking the term's factors in order. Numeric
260        // factors join every subterm; a categorical factor joins only if the
261        // coding includes it (patsy: `elif factor in factor_coding`).
262        let mut specs: Vec<FactorSpec> = Vec::new();
263        for f in &term.factors {
264            match f {
265                Factor::Categorical { var, contrast, .. } => {
266                    let Some(&full) = coding.get(&f.key()) else {
267                        continue;
268                    };
269                    let col = data.categorical_col(var).ok_or_else(|| {
270                        Error::Value(format!("C({var}): `{var}` is not categorical"))
271                    })?;
272                    let levels = sorted_levels(col);
273                    let coding = contrast.coding(&levels, full);
274                    specs.push(FactorSpec::Categorical {
275                        label: f.label(),
276                        rows: col.to_vec(),
277                        levels,
278                        coding,
279                    });
280                }
281                _ => specs.push(FactorSpec::Numeric {
282                    label: f.label(),
283                    values: numeric_values(f, data, nrows)?,
284                }),
285            }
286        }
287        expand_subterm(&specs, nrows, columns, names);
288    }
289    Ok(())
290}
291
292enum FactorSpec {
293    Numeric {
294        label: String,
295        values: Vec<f64>,
296    },
297    Categorical {
298        label: String,
299        rows: Vec<String>,
300        levels: Vec<String>,
301        coding: Coding,
302    },
303}
304
305impl FactorSpec {
306    fn width(&self) -> usize {
307        match self {
308            FactorSpec::Numeric { .. } => 1,
309            FactorSpec::Categorical { coding, .. } => coding.suffixes.len(),
310        }
311    }
312
313    /// (column suffix, per-row values) for the `j`-th column of this factor.
314    fn column(&self, j: usize, nrows: usize) -> (String, Vec<f64>) {
315        match self {
316            FactorSpec::Numeric { label, values } => (label.clone(), values.clone()),
317            FactorSpec::Categorical {
318                label,
319                rows,
320                levels,
321                coding,
322            } => {
323                // Each row's value is the contrast-matrix entry for that row's
324                // level in column `j`; the suffix comes straight from the coding.
325                let suffix = format!("{label}{}", coding.suffixes[j]);
326                let mut v = vec![0.0; nrows];
327                for (i, val) in v.iter_mut().enumerate() {
328                    let level_idx = levels.iter().position(|l| l == &rows[i]);
329                    if let Some(li) = level_idx {
330                        *val = coding.matrix[li][j];
331                    }
332                }
333                (suffix, v)
334            }
335        }
336    }
337}
338
339/// Expand a subterm into design columns. Combination order matches patsy/R:
340/// the left-most factor iterates fastest.
341fn expand_subterm(
342    specs: &[FactorSpec],
343    nrows: usize,
344    columns: &mut Vec<Vec<f64>>,
345    names: &mut Vec<String>,
346) {
347    let widths: Vec<usize> = specs.iter().map(FactorSpec::width).collect();
348    if widths.contains(&0) {
349        return;
350    }
351    for combo in column_combinations(&widths) {
352        let mut pieces: Vec<String> = Vec::new();
353        let mut col = vec![1.0f64; nrows];
354        for (fi, &j) in combo.iter().enumerate() {
355            let (suffix, values) = specs[fi].column(j, nrows);
356            pieces.push(suffix);
357            for (c, x) in col.iter_mut().zip(values.iter()) {
358                *c *= x;
359            }
360        }
361        names.push(if pieces.is_empty() {
362            "Intercept".to_string()
363        } else {
364            pieces.join(":")
365        });
366        columns.push(col);
367    }
368}
369
370/// Index combinations across factors with the left-most factor iterating
371/// fastest.
372fn column_combinations(widths: &[usize]) -> Vec<Vec<usize>> {
373    if widths.is_empty() {
374        return vec![vec![]];
375    }
376    let total: usize = widths.iter().product();
377    let mut out = Vec::with_capacity(total);
378    let mut idx = vec![0usize; widths.len()];
379    for _ in 0..total {
380        out.push(idx.clone());
381        let mut k = 0;
382        loop {
383            idx[k] += 1;
384            if idx[k] < widths[k] {
385                break;
386            }
387            idx[k] = 0;
388            k += 1;
389            if k == widths.len() {
390                break;
391            }
392        }
393    }
394    out
395}
396
397fn sorted_levels(col: &[String]) -> Vec<String> {
398    let mut set: BTreeSet<String> = BTreeSet::new();
399    for v in col {
400        set.insert(v.clone());
401    }
402    set.into_iter().collect()
403}
404
405fn numeric_values(f: &Factor, data: &DataFrame, nrows: usize) -> Result<Vec<f64>> {
406    match f {
407        Factor::Numeric(n) => {
408            let c = data
409                .numeric_col(n)
410                .ok_or_else(|| Error::Value(format!("`{n}` is not numeric")))?;
411            Ok(c.to_vec())
412        }
413        Factor::Identity { expr, .. } => eval_column(expr, data, nrows),
414        Factor::Categorical { .. } => Err(Error::Value("numeric_values on categorical".into())),
415    }
416}