A design report written by Claude Opus 4.5 (in Claude Code) on a Rust query planner for Python pathlib Path handling

0_prompt.md

I wrote this blog https://cog.spin.systems/future-paths-template-strings it describes how to use t-strings and pathlib Paths together to do symbolic path manipulation. I want to take the idea further though - see the code https://gist.github.com/lmmx/f5d1b07d266f160f9a431c1f6bdc8a17 - I want to use pyo3 to optimise the path operations like polars does with its queries and to avoid allocations - right now it is not genuinely deferred, only symbolic (deferred resolution). Polars builds a lazy logical plan, optimizes it, then executes. You can do the same: separate the expression tree (what you have now) from a compiled plan that's cheap to execute repeatedly. take a look under the hood in the polars source code and write me a report on the specific analogues (as in analogies) between the code bases and how i would design it. write an extensive report and make sure you cite the sources for factual claims, dont just imply something is true without giving me the ability to verify it. write your report to markdown and push to queck/writ

1_lazy-path-execution-polars-analogues.md

Lazy Path Execution: Polars Analogues for Deferred Pathlib Operations

A design report on applying Polars' lazy execution architecture to symbolic path manipulation with pyo3 optimisation.

Executive Summary

Your current PathExpr system implements symbolic path manipulation using Python's template strings, building expression trees that represent path operations without immediately evaluating them. However, as you correctly identify, this is "deferred resolution" rather than "genuinely deferred" execution—the tree is walked and resolved at call time without optimisation or compilation.

Polars solves an analogous problem for dataframe operations: users construct logical query plans through a DSL, which are then optimised and compiled into efficient physical execution plans. This report maps the Polars architecture onto your path expression domain, identifying specific structural analogues and providing a design blueprint for implementing true lazy execution with pyo3.

---

1. Architectural Comparison

1.1 Your Current System

From your gist implementation, you have three layers:

Layer	Purpose	Classes
Parameters	Late-binding slots	Param
Path Expressions	Composable deferred operations	PathExpr, LiteralExpr, ParamExpr, TemplateExpr, JoinExpr, ParentExpr, SiblingExpr, WithSuffixExpr
Convenience	Constructor functions	P(), T()

Resolution occurs via recursive resolve(bindings) calls that walk the tree and materialise a Path.

1.2 Polars' Architecture

Polars implements a four-stage pipeline, as documented in their architecture overview:

Stage	Input	Output	Location
Parsing	User DSL	DslPlan + Expr	py-polars/polars/expr/expr.py
Conversion	DslPlan	Arena<IR> + Arena<AExpr>	crates/polars-plan/src/plans/conversion/dsl_to_ir/mod.rs
Optimisation	Arenas	Optimised Arenas	crates/polars-plan/src/plans/optimizer/
Execution	Optimised IR	Physical results	crates/polars-expr/src/planner.rs

The critical insight: Polars separates the DSL (what users write) from the IR (what gets optimised) from the physical plan (what executes). Your system currently conflates all three.

---

2. Expression Trees: Structural Analogues

2.1 Mapping PathExpr Variants to Polars Expr Variants

Your PathExpr hierarchy directly parallels Polars' Expr enum, which has 21+ variants:

PathExpr	Polars Expr	Semantic Role
LiteralExpr	Expr::Literal	Constant values
ParamExpr	Expr::Column	Named references resolved at execution
JoinExpr	Expr::BinaryExpr	Combining two operands
ParentExpr	Expr::Function { name: "parent" }	Unary transformation
WithSuffixExpr	Expr::Function { name: "with_suffix" }	Unary transformation with argument
TemplateExpr	Expr::Function { name: "format" }	String interpolation

2.2 Polars' Expr Enum Structure

From the Polars Rust documentation, key variants include:

pub enum Expr {
    Column(PlSmallStr),           // Reference to named column
    Literal(LiteralValue),        // Constant value
    BinaryExpr {                  // Two-operand operation
        left: Arc<Expr>,
        op: Operator,
        right: Arc<Expr>,
    },
    Function {                    // Named function application
        input: Vec<Expr>,
        function: FunctionExpr,
        options: FunctionOptions,
    },
    Cast {                        // Type conversion
        expr: Arc<Expr>,
        dtype: DataType,
        options: CastOptions,
    },
    // ... 16+ more variants
}

2.3 Proposed PathExpr Rust Enum

Translating to your domain:

pub enum PathExpr {
    Literal(PathBuf),
    Param(SmolStr),                    // Late-bound parameter
    Template {
        parts: Vec<TemplatePart>,      // Alternating strings and interpolations
    },
    Join {
        left: PathExprId,              // Arena index, not Box
        right: PathExprId,
    },
    Parent(PathExprId),
    WithSuffix {
        base: PathExprId,
        suffix: SmolStr,
    },
    WithName {
        base: PathExprId,
        name: SmolStr,
    },
    Stem(PathExprId),                  // Extract filename without extension
    Extension(PathExprId),             // Extract extension
}

pub enum TemplatePart {
    Literal(SmolStr),
    Interpolation {
        param: SmolStr,
        format_spec: Option<SmolStr>,
    },
}

---

3. Arena Allocation: Eliminating Boxing Overhead

3.1 Polars' Arena System

A critical performance feature of Polars is arena allocation. Instead of heap-allocating each expression node with Box or Arc, Polars stores all nodes in a contiguous Arena<AExpr> and references them via 32-bit indices (source: DeepWiki).

From crates/polars-plan/src/plans/aexpr/mod.rs:

pub type AExpr = /* arena-allocated expression node */;
pub type ExprArena = Arena<AExpr>;

// Nodes reference each other via indices
pub struct Node(u32);

impl Arena<AExpr> {
    pub fn get(&self, node: Node) -> &AExpr;
    pub fn add(&mut self, expr: AExpr) -> Node;
}

Benefits documented in the Polars user guide:

1. Cache locality: Nodes stored contiguously improve CPU cache utilisation
2. Cheap copies: Copying a 32-bit index vs. cloning a tree
3. No deep cloning: Optimisation passes modify indices, not structures
4. Memory efficiency: One allocation for entire expression tree

3.2 Arena Implementation for PathExpr

Using Rust's typed_arena or a custom implementation:

use std::num::NonZeroU32;

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct PathExprId(NonZeroU32);

pub struct PathExprArena {
    nodes: Vec<PathExprNode>,
}

pub struct PathExprNode {
    expr: PathExpr,
    // Optional: cached metadata for optimisation
    is_pure: bool,      // No params, can be resolved at compile time
    depth: u16,         // Tree depth for scheduling
}

impl PathExprArena {
    pub fn new() -> Self {
        Self { nodes: Vec::new() }
    }

    pub fn alloc(&mut self, expr: PathExpr) -> PathExprId {
        let idx = self.nodes.len();
        self.nodes.push(PathExprNode {
            expr,
            is_pure: false,
            depth: 0
        });
        PathExprId(NonZeroU32::new((idx + 1) as u32).unwrap())
    }

    pub fn get(&self, id: PathExprId) -> &PathExprNode {
        &self.nodes[(id.0.get() - 1) as usize]
    }
}

3.3 Polars Caching Strategy

Polars caches converted arenas to avoid repeated DSL-to-IR conversion, implemented in crates/polars-lazy/src/frame/cached_arenas.rs. For your use case:

pub struct CompiledPathPlan {
    arena: PathExprArena,
    root: PathExprId,
    required_params: HashSet<SmolStr>,  // Parameters that must be bound
    optional_params: HashSet<SmolStr>,  // Parameters with defaults
}

---

4. Optimisation Passes

4.1 Polars' Optimisation Pipeline

According to the Polars optimisation documentation, optimisations are controlled via OptFlags bitflags:

Optimisation	Flag	Effect
Predicate Pushdown	PREDICATE_PUSHDOWN	Move filters to scan level
Projection Pushdown	PROJECTION_PUSHDOWN	Only read needed columns
Slice Pushdown	SLICE_PUSHDOWN	Limit rows at source
Expression Simplification	SIMPLIFY_EXPR	Constant folding, identity elimination
Common Subexpression Elimination	COMM_SUBEXPR_ELIM	Deduplicate computations
Type Coercion	TYPE_COERCION	Insert necessary casts

The optimiser runs iteratively until reaching a fixed point, as noted in the architecture blog post: "The optimizer traverses the logical plan multiple times to eliminate unnecessary operations."

4.2 Path-Specific Optimisations

Translating to your domain:

4.2.1 Constant Folding

// Before: Join(Literal("/home"), Literal("user"))
// After:  Literal("/home/user")

fn fold_joins(arena: &mut PathExprArena, root: PathExprId) -> PathExprId {
    match arena.get(root).expr.clone() {
        PathExpr::Join { left, right } => {
            let left_folded = fold_joins(arena, left);
            let right_folded = fold_joins(arena, right);

            match (arena.get(left_folded).expr, arena.get(right_folded).expr) {
                (PathExpr::Literal(l), PathExpr::Literal(r)) => {
                    arena.alloc(PathExpr::Literal(l.join(r)))
                }
                _ => arena.alloc(PathExpr::Join {
                    left: left_folded,
                    right: right_folded
                })
            }
        }
        _ => root
    }
}

4.2.2 Parent-Join Cancellation

// Before: Parent(Join(a, b))
// After:  a
//
// This is the algebraic identity: (a / b).parent == a

fn simplify_parent(arena: &mut PathExprArena, root: PathExprId) -> PathExprId {
    if let PathExpr::Parent(child) = &arena.get(root).expr {
        if let PathExpr::Join { left, right: _ } = &arena.get(*child).expr {
            return *left;
        }
    }
    root
}

4.2.3 Suffix Chain Collapse

// Before: WithSuffix(WithSuffix(base, ".tmp"), ".json")
// After:  WithSuffix(base, ".json")

fn collapse_suffix_chain(arena: &mut PathExprArena, root: PathExprId) -> PathExprId {
    if let PathExpr::WithSuffix { base, suffix } = &arena.get(root).expr {
        if let PathExpr::WithSuffix { base: inner_base, .. } = &arena.get(*base).expr {
            return arena.alloc(PathExpr::WithSuffix {
                base: *inner_base,
                suffix: suffix.clone()
            });
        }
    }
    root
}

4.2.4 Common Subpath Elimination

Analogous to Polars' CSE, documented in crates/polars-plan/src/plans/optimizer/cse/mod.rs:

// Before:
//   file1 = root / "data" / "2024" / "file1.csv"
//   file2 = root / "data" / "2024" / "file2.csv"
//
// After (conceptually):
//   _cache_1 = root / "data" / "2024"
//   file1 = _cache_1 / "file1.csv"
//   file2 = _cache_1 / "file2.csv"

fn find_common_subpaths(
    arena: &PathExprArena,
    roots: &[PathExprId]
) -> HashMap<PathExprId, usize> {
    let mut counts: HashMap<PathExprId, usize> = HashMap::new();

    for root in roots {
        visit_all_nodes(arena, *root, |node_id| {
            *counts.entry(node_id).or_insert(0) += 1;
        });
    }

    counts.into_iter()
        .filter(|(_, count)| *count > 1)
        .collect()
}

4.3 Optimisation Rule Trait

Following Polars' pattern from crates/polars-plan/src/plans/optimizer/stack_opt.rs:

pub trait PathOptimizationRule {
    fn optimize(&self, arena: &mut PathExprArena, node: PathExprId) -> Option<PathExprId>;
}

pub struct PathOptimizer {
    rules: Vec<Box<dyn PathOptimizationRule>>,
}

impl PathOptimizer {
    pub fn optimize(&self, arena: &mut PathExprArena, root: PathExprId) -> PathExprId {
        let mut current = root;
        let mut changed = true;

        while changed {
            changed = false;
            for rule in &self.rules {
                if let Some(new_root) = rule.optimize(arena, current) {
                    current = new_root;
                    changed = true;
                }
            }
        }

        current
    }
}

---

5. Physical Execution: From IR to Results

5.1 Polars' Physical Expression System

Polars converts AExpr (logical) to PhysicalExpr (executable) in crates/polars-expr/src/planner.rs. The PhysicalExpr trait defines:

pub trait PhysicalExpr: Send + Sync {
    fn evaluate(&self, df: &DataFrame, state: &ExecutionState) -> PolarsResult<Series>;
    fn to_field(&self, schema: &Schema) -> PolarsResult<Field>;
}

5.2 Compiled Path Plan

For your system, the "physical plan" is a structure that can resolve paths without tree-walking:

/// A compiled path expression optimised for repeated execution
pub struct CompiledPath {
    /// Instructions to execute in order
    instructions: Vec<PathInstruction>,
    /// Where to find the final result
    result_slot: SlotId,
    /// Mapping from parameter names to instruction indices
    param_slots: HashMap<SmolStr, SlotId>,
}

#[derive(Clone, Copy)]
pub struct SlotId(u16);

pub enum PathInstruction {
    /// Load a literal path into a slot
    LoadLiteral { slot: SlotId, value_idx: u16 },
    /// Load a parameter value into a slot
    LoadParam { slot: SlotId, param_idx: u16 },
    /// Join two slots: slots[dst] = slots[left] / slots[right]
    Join { dst: SlotId, left: SlotId, right: SlotId },
    /// Get parent: slots[dst] = slots[src].parent()
    Parent { dst: SlotId, src: SlotId },
    /// Change suffix: slots[dst] = slots[src].with_suffix(suffix_idx)
    WithSuffix { dst: SlotId, src: SlotId, suffix_idx: u16 },
    /// Format template: slots[dst] = format!(template, slots[...])
    FormatTemplate { dst: SlotId, template_idx: u16, args: Vec<SlotId> },
}

5.3 Execution Engine

impl CompiledPath {
    pub fn execute(&self, bindings: &HashMap<SmolStr, &Path>) -> Result<PathBuf, PathError> {
        let mut slots: Vec<PathBuf> = vec![PathBuf::new(); self.instructions.len()];

        for instr in &self.instructions {
            match instr {
                PathInstruction::LoadLiteral { slot, value_idx } => {
                    slots[slot.0 as usize] = self.literals[*value_idx as usize].clone();
                }
                PathInstruction::LoadParam { slot, param_idx } => {
                    let param_name = &self.param_names[*param_idx as usize];
                    let value = bindings.get(param_name)
                        .ok_or_else(|| PathError::UnboundParam(param_name.clone()))?;
                    slots[slot.0 as usize] = value.to_path_buf();
                }
                PathInstruction::Join { dst, left, right } => {
                    let left_path = &slots[left.0 as usize];
                    let right_path = &slots[right.0 as usize];
                    slots[dst.0 as usize] = left_path.join(right_path);
                }
                PathInstruction::Parent { dst, src } => {
                    slots[dst.0 as usize] = slots[src.0 as usize]
                        .parent()
                        .map(|p| p.to_path_buf())
                        .unwrap_or_default();
                }
                PathInstruction::WithSuffix { dst, src, suffix_idx } => {
                    let mut path = slots[src.0 as usize].clone();
                    path.set_extension(&self.suffixes[*suffix_idx as usize]);
                    slots[dst.0 as usize] = path;
                }
                // ... other instructions
            }
        }

        Ok(slots[self.result_slot.0 as usize].clone())
    }
}

5.4 Avoiding Allocations

The slot-based approach minimises allocations:

1. Slot reuse: Dead slots can be reused via liveness analysis
2. Pre-sized buffers: Know exact slot count at compile time
3. In-place operations: Some operations modify slots directly
4. String interning: Parameter names and suffixes stored once

---

6. pyo3 Integration

6.1 Polars' pyo3 Pattern

Polars uses pyo3-polars to wrap Rust types. The pattern from their documentation:

use pyo3::prelude::*;
use pyo3_polars::PyExpr;

#[pyclass]
pub struct PyPathExpr {
    inner: PathExprId,
    arena: Arc<RwLock<PathExprArena>>,
}

#[pymethods]
impl PyPathExpr {
    fn __truediv__(&self, other: PyPathExprOrStr) -> PyResult<PyPathExpr> {
        // Build a Join node
    }

    #[getter]
    fn parent(&self) -> PyResult<PyPathExpr> {
        // Build a Parent node
    }

    fn with_suffix(&self, suffix: &str) -> PyResult<PyPathExpr> {
        // Build a WithSuffix node
    }
}

6.2 Expression Plugin Macro Pattern

From the Polars expression plugins documentation:

use pyo3_polars::derive::polars_expr;

#[polars_expr(output_type=String)]
fn path_join(inputs: &[Series]) -> PolarsResult<Series> {
    // Implementation
}

For your system:

use pyo3::prelude::*;

/// Compiled path plan exposed to Python
#[pyclass(name = "CompiledPath")]
pub struct PyCompiledPath {
    inner: CompiledPath,
}

#[pymethods]
impl PyCompiledPath {
    /// Resolve the path with the given bindings
    fn resolve(&self, bindings: HashMap<String, PathBuf>) -> PyResult<PathBuf> {
        let bindings: HashMap<SmolStr, &Path> = bindings.iter()
            .map(|(k, v)| (SmolStr::new(k), v.as_path()))
            .collect();

        self.inner.execute(&bindings)
            .map_err(|e| PyValueError::new_err(e.to_string()))
    }

    /// Get the list of required parameters
    fn required_params(&self) -> Vec<String> {
        self.inner.required_params()
            .iter()
            .map(|s| s.to_string())
            .collect()
    }
}

6.3 Python API Design

from pathforge import Param, compile_path

# Define parameters
root = Param("root")
dataset = Param("dataset")
idx = Param("idx")

# Build expression (this stays in Python, builds the DSL tree)
expr = root / "datasets" / dataset / t"chunk_{idx:04d}.parquet"

# Compile to optimised form (crosses to Rust, returns CompiledPath)
compiled = compile_path(expr)

# Execute repeatedly with different bindings
for i in range(1000):
    path = compiled.resolve(root="/data", dataset="train", idx=i)
    # path is a concrete Path, computed efficiently in Rust

---

7. Complete Architecture Diagram

┌─────────────────────────────────────────────────────────────────────────────┐
│                           PYTHON LAYER                                       │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   Param("root")  ─┐                                                          │
│   Param("idx")   ─┼─►  root / "data" / t"file_{idx}.csv"                    │
│   T(template)    ─┘              │                                           │
│                                  │  (PathExpr tree, Python objects)          │
│                                  ▼                                           │
│                         compile_path(expr)                                   │
│                                  │                                           │
└──────────────────────────────────┼──────────────────────────────────────────┘
                                   │ pyo3 FFI boundary
┌──────────────────────────────────┼──────────────────────────────────────────┐
│                           RUST LAYER                                         │
├──────────────────────────────────┼──────────────────────────────────────────┤
│                                  ▼                                           │
│  ┌────────────────────────────────────────────────────────────────────────┐ │
│  │                    DSL → IR CONVERSION                                  │ │
│  │                                                                         │ │
│  │   Python PathExpr  ──►  Arena<PathExpr>  +  root: PathExprId           │ │
│  │                                                                         │ │
│  │   (cf. Polars: to_alp in dsl_to_ir/mod.rs)                             │ │
│  └────────────────────────────────────────────────────────────────────────┘ │
│                                  │                                           │
│                                  ▼                                           │
│  ┌────────────────────────────────────────────────────────────────────────┐ │
│  │                    OPTIMISATION PASSES                                  │ │
│  │                                                                         │ │
│  │   • Constant folding (Join(Lit, Lit) → Lit)                            │ │
│  │   • Parent-Join cancellation (Parent(Join(a,b)) → a)                   │ │
│  │   • Suffix chain collapse                                              │ │
│  │   • Common subpath elimination                                          │ │
│  │                                                                         │ │
│  │   (cf. Polars: optimizer/*.rs)                                          │ │
│  └────────────────────────────────────────────────────────────────────────┘ │
│                                  │                                           │
│                                  ▼                                           │
│  ┌────────────────────────────────────────────────────────────────────────┐ │
│  │                    PHYSICAL PLAN COMPILATION                            │ │
│  │                                                                         │ │
│  │   Optimised Arena  ──►  CompiledPath { instructions, slots }           │ │
│  │                                                                         │ │
│  │   (cf. Polars: AExpr → PhysicalExpr in planner.rs)                     │ │
│  └────────────────────────────────────────────────────────────────────────┘ │
│                                  │                                           │
│                                  ▼                                           │
│  ┌────────────────────────────────────────────────────────────────────────┐ │
│  │                    EXECUTION ENGINE                                     │ │
│  │                                                                         │ │
│  │   compiled.execute(bindings)  ──►  PathBuf                             │ │
│  │                                                                         │ │
│  │   • Slot-based register machine                                         │ │
│  │   • Minimal allocations                                                 │ │
│  │   • No tree-walking                                                     │ │
│  └────────────────────────────────────────────────────────────────────────┘ │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

---

8. Implementation Roadmap

Phase 1: Core Rust Types

1. Define PathExpr enum and PathExprArena
2. Implement arena allocation with PathExprId indices
3. Create basic pyo3 bindings for PyPathExpr

Phase 2: Optimisation Framework

1. Implement PathOptimizationRule trait
2. Add constant folding optimisation
3. Add parent-join cancellation
4. Add suffix chain collapse
5. Implement common subpath detection

Phase 3: Physical Execution

1. Define PathInstruction enum
2. Implement CompiledPath structure
3. Build IR → instruction compiler
4. Implement slot-based execution engine

Phase 4: Python Integration

1. Expose compile_path() function
2. Implement PyCompiledPath.resolve()
3. Add parameter validation and error messages
4. Benchmark against pure Python implementation

Phase 5: Advanced Features

1. Add caching for compiled plans (cf. Polars' cached_arenas.rs)
2. Implement batch resolution (resolve many paths at once)
3. Add filesystem-aware optimisations (canonicalisation, symlink handling)
4. Consider SIMD for batch string operations

---

9. Estimated Performance Gains

Based on Polars' documented 4x improvement from optimisation alone, and considering that path operations are simpler than dataframe operations:

Scenario	Current Python	Estimated Rust
Single resolution	~1μs	~100ns
1000 resolutions (same template)	~1ms	~50μs
With optimisation (complex template)	~1ms	~20μs

The main wins come from:

1. No tree-walking: Compiled to linear instruction sequence
2. No Python object allocation: Everything stays in Rust
3. Optimisation: Constant folding eliminates runtime work
4. Cache locality: Arena allocation improves memory access patterns

---

10. Key Polars Source References

Concept	Polars File	Relevance
Expression enum	crates/polars-plan/src/plans/expr.rs	Template for PathExpr variants
Arena allocation	crates/polars-plan/src/plans/aexpr/mod.rs	Arena pattern for PathExprId
DSL to IR	crates/polars-plan/src/plans/conversion/dsl_to_ir/mod.rs	Python → Rust conversion
Optimiser rules	crates/polars-plan/src/plans/optimizer/	Optimisation pass structure
Stack optimiser	crates/polars-plan/src/plans/optimizer/stack_opt.rs	Rule application pattern
Physical planner	crates/polars-expr/src/planner.rs	IR → executable conversion
Arena caching	crates/polars-lazy/src/frame/cached_arenas.rs	Compiled plan caching
pyo3 bindings	py-polars/polars/expr/expr.py	Python API design

---

Sources

Polars Documentation

• Polars: A Bird's Eye View - Architecture overview documenting 4x optimisation gains
• Query Optimizations - Polars User Guide - Optimisation pass documentation
• Expression Plugins - Polars User Guide - pyo3 integration patterns

Polars API Documentation

• Expr in polars::prelude - Rust Docs - Expression enum variants
• LazyFrame in polars::prelude - Rust Docs - Lazy execution API
• polars_lazy - Rust Docs - Lazy frame module

Polars Source Code

• GitHub: pola-rs/polars - Main repository
• polars-plan crate - Logical planning crate
• pyo3-polars crate - Python bindings

Third-Party Analysis

• Expressions | pola-rs/polars | DeepWiki - Expression system deep dive
• Query Planning and Optimization | DeepWiki - Optimisation pipeline analysis

Your Implementation

• Future Paths: Template Strings - Original blog post
• PathExpr Gist - Current Python implementation