use alloc::{
collections::{BTreeMap, BTreeSet},
format,
string::{String, ToString},
vec::Vec,
};
use super::{
PLAN_SCHEMA, PlanDocument, PlanError, PlanLane, PlanNode, PlanTopology, TOPOLOGY_SCHEMA,
VerifiedPlanSeed,
};
const FOURTH_REJECTION: &str =
"malignant-revoke-quarantine-preserve-evidence-no-resume-root-lineage-replacement";
const ROOT_CONTINUATION: &str = "fresh-root-preferred-new-run-binding-clears-child-authority";
pub fn validate_plan_structure(
plan: &PlanDocument,
seed: &VerifiedPlanSeed,
) -> Result<PlanTopology, PlanError> {
let manifest = &plan.manifest;
if manifest.schema != PLAN_SCHEMA {
return Err(structure(format!(
"schema must be `{PLAN_SCHEMA}`, found `{}`",
manifest.schema
)));
}
if manifest.run != seed.run || manifest.seed != seed.relative_path || manifest.mesh != seed.mesh
{
return Err(structure(
"run, seed, and mesh must match the verified seed",
));
}
validate_identifier(&manifest.run, "run")?;
validate_relative_path(&manifest.seed, "seed")?;
validate_relative_path(&manifest.mesh, "mesh")?;
validate_relative_path(&manifest.planning_evidence, "planning evidence")?;
require_text(&manifest.goal, "goal")?;
validate_closed_roles(manifest)?;
let deliverables = unique_set(&manifest.deliverables, "deliverable")?;
let seed_deliverables = unique_set(&seed.deliverables, "seed deliverable")?;
if deliverables != seed_deliverables {
return Err(structure(format!(
"plan deliverables do not exactly cover verified seed deliverables: plan={deliverables:?} seed={seed_deliverables:?}"
)));
}
let lanes = unique_set(&manifest.lanes, "lane")?;
if lanes.is_empty() {
return Err(structure("plan has zero lanes"));
}
for lane in &lanes {
validate_identifier(lane, "lane")?;
}
validate_capacity(plan, seed, &lanes)?;
let mut node_by_id = BTreeMap::new();
let mut deliverable_producers: BTreeMap<&str, &str> = BTreeMap::new();
let mut interface_producers: BTreeMap<&str, &str> = BTreeMap::new();
for node in &manifest.nodes {
validate_node(node, &lanes, &deliverables)?;
if node_by_id.insert(node.id.as_str(), node).is_some() {
return Err(structure(format!("duplicate node id `{}`", node.id)));
}
for deliverable in &node.seed_deliverables {
if let Some(previous) = deliverable_producers.insert(deliverable, &node.id) {
return Err(structure(format!(
"seed deliverable `{deliverable}` has duplicate producer nodes `{previous}` and `{}`",
node.id
)));
}
}
for interface in &node.produces {
validate_interface(interface)?;
if let Some(previous) = interface_producers.insert(interface, &node.id) {
return Err(structure(format!(
"interface producer is duplicated for `{interface}` by `{previous}` and `{}`",
node.id
)));
}
}
for interface in &node.consumes {
validate_interface(interface)?;
}
}
for deliverable in &deliverables {
if !deliverable_producers.contains_key(deliverable.as_str()) {
return Err(structure(format!(
"verified seed deliverable `{deliverable}` is uncovered"
)));
}
}
for node in &manifest.nodes {
for dependency in &node.depends_on {
if !node_by_id.contains_key(dependency.as_str()) {
return Err(structure(format!(
"node `{}` has dangling dependency `{dependency}`",
node.id
)));
}
if dependency == &node.id {
return Err(structure(format!("dependency cycle at `{}`", node.id)));
}
}
}
let topological_order = topological_order(&node_by_id)?;
validate_reachability(&node_by_id)?;
validate_concurrent_ownership(&node_by_id)?;
let cargo_targets = manifest
.capacity
.cargo_targets
.iter()
.map(|binding| (binding.lane.as_str(), binding.value.as_str()))
.collect::<BTreeMap<_, _>>();
let conductors = manifest
.capacity
.conductors
.iter()
.map(|binding| (binding.lane.as_str(), binding.value.as_str()))
.collect::<BTreeMap<_, _>>();
let mut topology_lanes = Vec::new();
for lane in &manifest.lanes {
let mut node_ids = manifest
.nodes
.iter()
.filter(|node| &node.lane == lane)
.map(|node| node.id.clone())
.collect::<Vec<_>>();
node_ids.sort();
if node_ids.is_empty() {
return Err(structure(format!("lane `{lane}` has zero nodes")));
}
let mut lane_deliverables = manifest
.nodes
.iter()
.filter(|node| &node.lane == lane)
.flat_map(|node| node.seed_deliverables.iter().cloned())
.collect::<Vec<_>>();
lane_deliverables.sort();
lane_deliverables.dedup();
if lane_deliverables.is_empty() {
return Err(structure(format!(
"lane `{lane}` is not vertical because it binds no seed deliverable"
)));
}
topology_lanes.push(PlanLane {
id: lane.clone(),
conductor: conductors[lane.as_str()].to_string(),
cargo_target: cargo_targets[lane.as_str()].to_string(),
node_ids,
deliverables: lane_deliverables,
});
}
topology_lanes.sort_by(|left, right| left.id.cmp(&right.id));
let mut nodes = manifest.nodes.clone();
nodes.sort_by(|left, right| left.id.cmp(&right.id));
for node in &mut nodes {
node.seed_deliverables.sort();
node.depends_on.sort();
node.owns.sort();
node.forbidden.sort();
node.consumes.sort();
node.produces.sort();
}
let mut projected_deliverables = manifest.deliverables.clone();
projected_deliverables.sort();
let mut capacity = manifest.capacity.clone();
capacity
.cargo_targets
.sort_by(|left, right| left.lane.cmp(&right.lane));
capacity
.conductors
.sort_by(|left, right| left.lane.cmp(&right.lane));
for wave in &mut capacity.schedule {
wave.lanes.sort();
}
capacity
.schedule
.sort_by(|left, right| left.lanes.cmp(&right.lanes));
Ok(PlanTopology {
schema: TOPOLOGY_SCHEMA.to_string(),
run: manifest.run.clone(),
seed: manifest.seed.clone(),
mesh: manifest.mesh.clone(),
planning_evidence: manifest.planning_evidence.clone(),
goal: manifest.goal.clone(),
deliverables: projected_deliverables,
lanes: topology_lanes,
nodes,
topological_order,
capacity,
capacity_policy: capacity_policy(manifest.lanes.len()).to_string(),
})
}
fn validate_closed_roles(manifest: &super::PlanManifestV2) -> Result<(), PlanError> {
if manifest.root_roles != ["shepherd", "planter"] {
return Err(structure(
"root roles must be exactly `[shepherd, planter]` in that order",
));
}
if manifest.child_lead_roles != ["engineer", "conductor"] {
return Err(structure(
"child lead roles must be exactly `[engineer, conductor]` in that order",
));
}
if manifest.planning_lead != "engineer" || manifest.engineer_count != 1 {
return Err(structure(
"normal planning requires exactly one active Engineer child lead",
));
}
if manifest.review_rejection_limit != 3 || manifest.fourth_rejection != FOURTH_REJECTION {
return Err(structure(
"review custody requires three redos then fourth-rejection malignant revocation, quarantine, evidence preservation, no resume, and root-lineage replacement",
));
}
if manifest.root_continuation != ROOT_CONTINUATION {
return Err(structure(
"root continuation must prefer a fresh root and clear prior child authority under a new run binding before reuse",
));
}
Ok(())
}
fn validate_node(
node: &PlanNode,
lanes: &BTreeSet<String>,
deliverables: &BTreeSet<String>,
) -> Result<(), PlanError> {
validate_identifier(&node.id, "node id")?;
if !lanes.contains(&node.lane) {
return Err(structure(format!(
"node `{}` names unknown lane `{}`",
node.id, node.lane
)));
}
for deliverable in &node.seed_deliverables {
if !deliverables.contains(deliverable) {
return Err(structure(format!(
"node `{}` names unknown seed deliverable `{deliverable}`",
node.id
)));
}
}
let expected_work = match node.role.as_str() {
"coder" => "production",
"worker" => "artifact",
"engineer" => "planning",
"auditor" | "critic" => "review",
"discovery" => "research",
"conductor" => "coordination",
"shepherd" | "planter" => {
return Err(structure(format!(
"root role `{}` cannot be assigned a plan node",
node.role
)));
}
_ => return Err(structure(format!("invalid role `{}`", node.role))),
};
if node.work_kind != expected_work {
let detail = if node.role == "conductor" {
"Conductor consumes an immutable lane slice and may only coordinate; planning, rescoping, and implementation are forbidden"
} else {
"role and work kind are incompatible"
};
return Err(structure(format!(
"node `{}`: {detail}; role `{}` requires work kind `{expected_work}`, found `{}`",
node.id, node.role, node.work_kind
)));
}
require_text(&node.outcome, &format!("node `{}` outcome", node.id))?;
if node.owns.is_empty() {
return Err(structure(format!("node `{}` owns is empty", node.id)));
}
for path in &node.owns {
validate_relative_path(path, &format!("node `{}` owned path", node.id))?;
if path == ".shepherd" || path.starts_with(".shepherd/") {
return Err(structure(format!(
"node `{}` cannot own native state or run evidence paths",
node.id
)));
}
}
if node.forbidden.is_empty() {
return Err(structure(format!("node `{}` forbidden is empty", node.id)));
}
for command in [&node.red.command, &node.green.command, &node.eval.command] {
validate_argv(command, &node.id)?;
}
if node.red.expects != "failure" || node.green.expects != "success" {
return Err(structure(format!(
"node `{}` RED must expect failure and GREEN must expect success",
node.id
)));
}
require_text(&node.red.reason, "red reason")?;
require_text(&node.green.reason, "green reason")?;
if !matches!(node.eval.threshold, Some(1..=100)) {
return Err(structure(format!(
"node `{}` eval threshold must be an integer from 1 through 100",
node.id
)));
}
validate_relative_path(&node.evidence, "evidence")?;
if !node.evidence.starts_with(".shepherd/runs/") {
return Err(structure(format!(
"node `{}` evidence must be run-relative",
node.id
)));
}
if !matches!(node.review.role.as_str(), "auditor" | "critic") {
return Err(structure(format!(
"node `{}` review role must be auditor or critic",
node.id
)));
}
require_text(&node.review.predicate, "review predicate")?;
require_text(&node.failure_route, "failure_route")?;
require_text(&node.rollback, "rollback")?;
Ok(())
}
fn validate_capacity(
plan: &PlanDocument,
seed: &VerifiedPlanSeed,
lanes: &BTreeSet<String>,
) -> Result<(), PlanError> {
let capacity = &plan.manifest.capacity;
if capacity.logical_lane_limit == 0
|| capacity.host_process_ceiling == 0
|| capacity.project_spawn_max_parallel == 0
|| capacity.plan_process_ceiling == 0
|| capacity.parent_role_cap == 0
|| capacity.run_budget == 0
|| capacity.simultaneous_process_ceiling == 0
|| capacity.per_lane_child_wave_ceiling == 0
|| capacity.model_quota == 0
|| capacity.disk_min_mib < 1024
{
return Err(structure(
"capacity values must be nonzero and disk_min_mib at least 1024",
));
}
if capacity.logical_lane_limit > lanes.len() {
return Err(structure(
"capacity logical lane limit cannot exceed the authored lane count",
));
}
let effective = [
capacity.host_process_ceiling,
capacity.project_spawn_max_parallel,
capacity.plan_process_ceiling,
capacity.parent_role_cap,
capacity.run_budget,
]
.into_iter()
.min()
.expect("fixed nonempty ceiling set");
if capacity.simultaneous_process_ceiling != effective {
return Err(structure(
"capacity simultaneous process ceiling must equal min(host, project spawn.max_parallel, plan, parent/role cap, run budget)",
));
}
if capacity.model_quota < capacity.simultaneous_process_ceiling {
return Err(structure(
"capacity model quota cannot be lower than the simultaneous process ceiling",
));
}
if !matches!(capacity.backpressure.as_str(), "queue" | "queue-fair") {
return Err(structure(
"capacity backpressure must be the deterministic `queue` or `queue-fair` policy",
));
}
validate_bindings(&capacity.cargo_targets, lanes, "cargo target", None)?;
validate_bindings(&capacity.conductors, lanes, "conductor", Some("conductor"))?;
if lanes.len() >= 4 && capacity.schedule.is_empty() {
return Err(structure(
"capacity schedule is required for four or more lanes",
));
}
let mut scheduled = BTreeSet::new();
for wave in &capacity.schedule {
if wave.lanes.is_empty()
|| wave.lanes.len() > capacity.logical_lane_limit
|| wave.process_slots == 0
|| wave.process_slots > capacity.simultaneous_process_ceiling
|| wave.process_slots
> wave
.lanes
.len()
.saturating_mul(capacity.per_lane_child_wave_ceiling)
{
return Err(structure(
"capacity schedule contains a zero or unsafe wave",
));
}
for lane in &wave.lanes {
if !lanes.contains(lane) {
return Err(structure(format!(
"capacity schedule names unknown lane `{lane}`"
)));
}
if !scheduled.insert(lane.as_str()) {
return Err(structure(format!(
"capacity schedule overlaps lane `{lane}`"
)));
}
}
}
if !capacity.schedule.is_empty() && scheduled != lanes.iter().map(String::as_str).collect() {
return Err(structure(
"capacity schedule must cover every lane exactly once",
));
}
if lanes.len() >= 6 {
let scale = capacity.scale_outcome.as_deref().ok_or_else(|| {
structure("six or more lanes require an explicit scale outcome binding")
})?;
if !seed.outcomes.iter().any(|outcome| outcome == scale) {
return Err(structure(format!(
"scale outcome `{scale}` is not bound to a verified seed outcome"
)));
}
}
Ok(())
}
fn capacity_policy(lane_count: usize) -> &'static str {
match lane_count {
0..=1 => "small: minimize lanes; no arbitrary minimum",
2 => "routine: two complete vertical Conductor subsprints",
3 => "beefy: three complete vertical Conductor subsprints",
4 => "beefy-mega boundary: explicit host and quota schedule required",
5 => "mega: explicit host and quota schedule required",
6 => "mega-exceptional boundary: seed-backed OS-scale reason and capacity proof required",
7..=8 => "exceptional OS-scale: seed-backed reason and capacity proof required",
_ => {
"outside the 99 percent two-to-six envelope: no global cap; seed-backed OS-scale reason and capacity proof required"
}
}
}
fn validate_bindings(
bindings: &[super::LaneBinding],
lanes: &BTreeSet<String>,
name: &str,
exact_value: Option<&str>,
) -> Result<(), PlanError> {
let mut bound_lanes = BTreeSet::new();
let mut values = BTreeSet::new();
for binding in bindings {
if !lanes.contains(&binding.lane) || !bound_lanes.insert(binding.lane.as_str()) {
return Err(structure(format!(
"{name} bindings must name each lane exactly once"
)));
}
validate_identifier(&binding.value, name)?;
if let Some(exact) = exact_value {
if binding.value != exact {
return Err(structure(format!(
"{name} for `{}` must be `{exact}`",
binding.lane
)));
}
} else if !values.insert(binding.value.as_str()) {
return Err(structure(format!(
"cargo target `{}` overlaps multiple lanes",
binding.value
)));
}
}
if bound_lanes != lanes.iter().map(String::as_str).collect() {
return Err(structure(format!(
"{name} bindings must cover every lane exactly once"
)));
}
Ok(())
}
fn topological_order(nodes: &BTreeMap<&str, &PlanNode>) -> Result<Vec<String>, PlanError> {
let mut indegree = nodes
.iter()
.map(|(id, node)| (*id, node.depends_on.len()))
.collect::<BTreeMap<_, _>>();
let mut dependents: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for (id, node) in nodes {
for dependency in &node.depends_on {
dependents.entry(dependency).or_default().push(id);
}
}
let mut ready = indegree
.iter()
.filter_map(|(id, count)| (*count == 0).then_some(*id))
.collect::<BTreeSet<_>>();
let mut order = Vec::new();
while let Some(id) = ready.pop_first() {
order.push(id.to_string());
if let Some(children) = dependents.get(id) {
for child in children {
let count = indegree.get_mut(child).expect("known dependent");
*count -= 1;
if *count == 0 {
ready.insert(child);
}
}
}
}
if order.len() != nodes.len() {
return Err(structure("dependency cycle detected"));
}
Ok(order)
}
fn validate_reachability(nodes: &BTreeMap<&str, &PlanNode>) -> Result<(), PlanError> {
let mut reachable = BTreeSet::new();
let mut pending = nodes
.values()
.filter(|node| !node.seed_deliverables.is_empty())
.map(|node| node.id.as_str())
.collect::<Vec<_>>();
while let Some(id) = pending.pop() {
if !reachable.insert(id) {
continue;
}
pending.extend(nodes[id].depends_on.iter().map(String::as_str));
}
if let Some(id) = nodes.keys().find(|id| !reachable.contains(**id)) {
return Err(structure(format!(
"node `{id}` is unreachable from any seed deliverable"
)));
}
Ok(())
}
fn validate_concurrent_ownership(nodes: &BTreeMap<&str, &PlanNode>) -> Result<(), PlanError> {
let ids = nodes.keys().copied().collect::<Vec<_>>();
for (index, left_id) in ids.iter().enumerate() {
for right_id in &ids[index + 1..] {
if depends_transitively(nodes, left_id, right_id)
|| depends_transitively(nodes, right_id, left_id)
{
continue;
}
for left in &nodes[left_id].owns {
for right in &nodes[right_id].owns {
if paths_overlap(left, right) {
return Err(structure(format!(
"concurrently ready nodes `{left_id}` and `{right_id}` overlap owned paths `{left}` and `{right}`"
)));
}
}
}
}
}
Ok(())
}
fn depends_transitively(nodes: &BTreeMap<&str, &PlanNode>, node: &str, target: &str) -> bool {
let mut pending = nodes[node]
.depends_on
.iter()
.map(String::as_str)
.collect::<Vec<_>>();
let mut seen = BTreeSet::new();
while let Some(id) = pending.pop() {
if id == target {
return true;
}
if seen.insert(id) {
pending.extend(nodes[id].depends_on.iter().map(String::as_str));
}
}
false
}
fn paths_overlap(left: &str, right: &str) -> bool {
left == right
|| left
.strip_prefix(right)
.is_some_and(|suffix| suffix.starts_with('/'))
|| right
.strip_prefix(left)
.is_some_and(|suffix| suffix.starts_with('/'))
}
fn validate_argv(argv: &[String], node: &str) -> Result<(), PlanError> {
if argv.is_empty() {
return Err(structure(format!("node `{node}` command argv is empty")));
}
let program = argv[0].as_str();
if matches!(
program,
"sh" | "bash" | "zsh" | "fish" | "cmd" | "powershell" | "pwsh"
) || argv.iter().any(|argument| {
argument.is_empty()
|| argument.contains('\n')
|| argument.contains("&&")
|| argument.contains(';')
|| argument == "|"
}) {
return Err(structure(format!(
"node `{node}` command must be bounded argv without a shell"
)));
}
Ok(())
}
fn validate_interface(value: &str) -> Result<(), PlanError> {
let Some((id, version)) = value.rsplit_once('@') else {
return Err(structure(format!(
"interface `{value}` must carry `@version`"
)));
};
validate_identifier(id, "interface id")?;
if version.is_empty()
|| !version
.bytes()
.all(|byte| byte.is_ascii_alphanumeric() || byte == b'.')
{
return Err(structure(format!(
"interface `{value}` has an invalid version"
)));
}
Ok(())
}
fn unique_set(values: &[String], context: &str) -> Result<BTreeSet<String>, PlanError> {
let mut set = BTreeSet::new();
for value in values {
validate_identifier(value, context)?;
if !set.insert(value.clone()) {
return Err(structure(format!("duplicate {context} `{value}`")));
}
}
Ok(set)
}
fn validate_identifier(value: &str, context: &str) -> Result<(), PlanError> {
if value.is_empty()
|| value.starts_with('-')
|| value.ends_with('-')
|| !value
.bytes()
.all(|byte| byte.is_ascii_lowercase() || byte.is_ascii_digit() || byte == b'-')
{
return Err(structure(format!("invalid {context} `{value}`")));
}
Ok(())
}
fn validate_relative_path(path: &str, context: &str) -> Result<(), PlanError> {
validate_repository_path(path)
.map_err(|message| structure(format!("invalid {context} path `{path}`: {message}")))?;
require_text(path, context)
}
pub fn validate_plan_repository_path(path: &str) -> Result<(), &'static str> {
if path.is_empty() || path.len() > 4_096 || path.starts_with('/') || path.starts_with("//") {
return Err("absolute and empty paths are forbidden");
}
if path.contains('\\') || path.contains(':') {
return Err("drive, UNC, backslash, and alternate-stream forms are forbidden");
}
if path
.chars()
.any(|character| character.is_control() || character == '\0')
{
return Err("control characters are forbidden");
}
if !path.is_ascii() {
return Err("non-ASCII path aliases are forbidden");
}
if path.chars().any(char::is_uppercase) || path.contains(['*', '?', '[', ']']) {
return Err("ambiguous-case and glob path forms are forbidden");
}
for part in path.split('/') {
if part.is_empty() || matches!(part, "." | "..") || part.contains('~') {
return Err("empty, dot, dotdot, and home-alias components are forbidden");
}
if part.ends_with('.') || part.ends_with(' ') {
return Err("trailing-dot and trailing-space aliases are forbidden");
}
let device = part
.split_once('.')
.map_or(part, |(stem, _)| stem)
.to_ascii_uppercase();
if matches!(device.as_str(), "CON" | "PRN" | "AUX" | "NUL")
|| device.strip_prefix("COM").is_some_and(|suffix| {
matches!(suffix, "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")
})
|| device.strip_prefix("LPT").is_some_and(|suffix| {
matches!(suffix, "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")
})
{
return Err("Windows device aliases are forbidden");
}
}
Ok(())
}
pub(super) fn validate_repository_path(path: &str) -> Result<(), &'static str> {
validate_plan_repository_path(path)
}
fn require_text(value: &str, context: &str) -> Result<(), PlanError> {
let lower = value.to_ascii_lowercase();
if value.trim().is_empty()
|| value.contains('<')
|| value.contains('>')
|| lower.contains("todo")
|| lower.contains("tbd")
|| value.contains("???")
{
return Err(structure(format!(
"{context} is empty or contains placeholder text"
)));
}
Ok(())
}
fn structure(message: impl Into<String>) -> PlanError {
PlanError::Structure(message.into())
}