use std::collections::VecDeque;
use crate::config::BuildConfig;
use crate::parse::{MutationSummary, ParseContext};
use crate::rewrite::registry;
use crate::rewrite::rule::{
PackageName, RewriteRule, RuleKey, RuleTarget, RuleTargetKey, RuleTargetKind,
};
#[derive(Clone, Debug)]
pub struct Plan {
rules: Vec<&'static dyn RewriteRule>,
eliminated_forms: Vec<RuleTargetKey>,
}
impl Plan {
pub fn build(config: &BuildConfig, parse_ctx: &ParseContext) -> Result<Self, PlanBuildError> {
let enabled = filter_rules(registry::all_rules(), config, parse_ctx)?;
let ordered = topological_sort(enabled.as_slice())?;
let eliminated_forms = derive_eliminated_forms(ordered.as_slice());
Ok(Self {
rules: ordered,
eliminated_forms,
})
}
pub fn rules(&self) -> &[&'static dyn RewriteRule] {
self.rules.as_slice()
}
pub fn eliminated_forms(&self) -> &[RuleTargetKey] {
self.eliminated_forms.as_slice()
}
#[cfg(test)]
pub(crate) fn from_rules_for_tests(rules: Vec<&'static dyn RewriteRule>) -> Self {
let eliminated_forms = derive_eliminated_forms(rules.as_slice());
Self {
rules,
eliminated_forms,
}
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) enum RuleSelection {
#[default]
All,
Only(Vec<RuleKey>),
Except(Vec<RuleKey>),
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum PlanBuildError {
SelectedRuleUnavailable {
rule: RuleKey,
reason: RuleAvailabilityFailure,
},
InvalidRuleMetadata {
rule: RuleKey,
message: &'static str,
},
DependencyCycle {
chain: Vec<RuleKey>,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuleAvailabilityFailure {
DisabledByPackage {
required: Vec<PackageName>,
active: Vec<PackageName>,
},
ProducedTargetUnavailable {
target: RuleTargetKey,
active: Vec<PackageName>,
},
}
impl std::fmt::Display for PlanBuildError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
PlanBuildError::SelectedRuleUnavailable { rule, reason } => {
write!(f, "selected transform rule {rule} is unavailable: {reason}")
}
PlanBuildError::InvalidRuleMetadata { rule, message } => {
write!(f, "transform rule {rule} has invalid metadata: {message}")
}
PlanBuildError::DependencyCycle { chain } => {
let chain = chain
.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(" -> ");
write!(f, "transform dependency cycle detected: {chain}")
}
}
}
}
impl std::fmt::Display for RuleAvailabilityFailure {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
RuleAvailabilityFailure::DisabledByPackage { required, active } => write!(
f,
"enabled_by_packages {:?} does not intersect active packages {:?}",
package_names_for_message(required.as_slice()),
package_names_for_message(active.as_slice())
),
RuleAvailabilityFailure::ProducedTargetUnavailable { target, active } => write!(
f,
"produced {} `{}` is unavailable in active packages {:?}",
target.kind_label(),
target.name,
package_names_for_message(active.as_slice())
),
}
}
}
impl std::error::Error for PlanBuildError {}
fn package_names_for_message(packages: &[PackageName]) -> Vec<&'static str> {
packages.iter().map(|package| package.as_str()).collect()
}
fn filter_rules(
rules: &[&'static dyn RewriteRule],
config: &BuildConfig,
parse_ctx: &ParseContext,
) -> Result<Vec<&'static dyn RewriteRule>, PlanBuildError> {
let mut enabled = Vec::new();
for rule in rules.iter().copied() {
let key = rule.meta().key;
let in_selection = match &config.selection {
RuleSelection::All => true,
RuleSelection::Only(keys) => keys.contains(&key),
RuleSelection::Except(keys) => !keys.contains(&key),
};
let explicitly_selected =
matches!(&config.selection, RuleSelection::Only(keys) if keys.contains(&key));
if !in_selection {
continue;
}
if !config.levels.contains(rule.meta().level) {
continue;
}
if rule_touched_by_mutations(rule, parse_ctx.mutation_summary()) {
continue;
}
validate_rule_metadata(rule)?;
if let Some(reason) = package_availability_failure(rule, parse_ctx) {
if explicitly_selected {
return Err(PlanBuildError::SelectedRuleUnavailable { rule: key, reason });
}
continue;
}
if let Some(reason) = produced_target_availability_failure(rule, parse_ctx) {
if explicitly_selected {
return Err(PlanBuildError::SelectedRuleUnavailable { rule: key, reason });
}
continue;
}
enabled.push(rule);
}
Ok(enabled)
}
fn validate_rule_metadata(rule: &'static dyn RewriteRule) -> Result<(), PlanBuildError> {
let meta = rule.meta();
if meta.triggers.is_empty() {
return Err(PlanBuildError::InvalidRuleMetadata {
rule: meta.key,
message: "triggers must be non-empty",
});
}
if meta.fidelity < meta.level.min_fidelity() {
return Err(PlanBuildError::InvalidRuleMetadata {
rule: meta.key,
message: "fidelity must not be below the normalization level floor",
});
}
let consumes = meta
.consumes
.eliminates
.iter()
.chain(meta.consumes.touches.iter())
.copied()
.map(RuleTarget::key)
.collect::<Vec<_>>();
if meta
.triggers
.iter()
.copied()
.map(RuleTarget::key)
.any(|trigger| !consumes.contains(&trigger))
{
return Err(PlanBuildError::InvalidRuleMetadata {
rule: meta.key,
message: "triggers must be a subset of consumes",
});
}
Ok(())
}
fn package_availability_failure(
rule: &'static dyn RewriteRule,
parse_ctx: &ParseContext,
) -> Option<RuleAvailabilityFailure> {
let active = parse_ctx.enabled_packages();
if rule
.meta()
.enabled_by_packages
.iter()
.any(|package| active.contains(package))
{
return None;
}
Some(RuleAvailabilityFailure::DisabledByPackage {
required: rule.meta().enabled_by_packages.to_vec(),
active: active.to_vec(),
})
}
fn produced_target_availability_failure(
rule: &'static dyn RewriteRule,
parse_ctx: &ParseContext,
) -> Option<RuleAvailabilityFailure> {
rule.meta()
.produces
.targets
.iter()
.copied()
.map(RuleTarget::key)
.find(|target| !parse_context_knows_target(parse_ctx, *target))
.map(
|target| RuleAvailabilityFailure::ProducedTargetUnavailable {
target,
active: parse_ctx.enabled_packages().to_vec(),
},
)
}
fn parse_context_knows_target(parse_ctx: &ParseContext, target: RuleTargetKey) -> bool {
match target.kind {
RuleTargetKind::Command => parse_ctx.knows_command_name(target.name),
RuleTargetKind::Environment => parse_ctx.knows_env_name(target.name),
RuleTargetKind::Character => parse_ctx.knows_character_name(target.name),
}
}
fn rule_touched_by_mutations(rule: &'static dyn RewriteRule, summary: &MutationSummary) -> bool {
rule.meta()
.consumes
.eliminates
.iter()
.chain(rule.meta().consumes.touches.iter())
.chain(rule.meta().produces.targets.iter())
.copied()
.map(RuleTarget::key)
.any(|target| match target.kind {
RuleTargetKind::Command | RuleTargetKind::Character => {
summary.touched_commands.contains(target.name)
}
RuleTargetKind::Environment => summary.touched_environments.contains(target.name),
})
}
fn derive_eliminated_forms(rules: &[&'static dyn RewriteRule]) -> Vec<RuleTargetKey> {
let mut forms = Vec::new();
for rule in rules {
for target in rule
.meta()
.consumes
.eliminates
.iter()
.copied()
.map(RuleTarget::key)
{
if !forms.contains(&target) {
forms.push(target);
}
}
}
forms
}
fn topological_sort(
rules: &[&'static dyn RewriteRule],
) -> Result<Vec<&'static dyn RewriteRule>, PlanBuildError> {
let mut incoming = vec![0usize; rules.len()];
let mut edges = vec![Vec::<usize>::new(); rules.len()];
for (from_index, from_rule) in rules.iter().enumerate() {
for (to_index, to_rule) in rules.iter().enumerate() {
if from_index == to_index {
continue;
}
if rules_intersect(*from_rule, *to_rule) {
edges[from_index].push(to_index);
incoming[to_index] += 1;
}
}
}
let mut queue = VecDeque::new();
for (index, &count) in incoming.iter().enumerate() {
if count == 0 {
queue.push_back(index);
}
}
let mut ordered = Vec::with_capacity(rules.len());
while let Some(index) = queue.pop_front() {
ordered.push(rules[index]);
for next in &edges[index] {
incoming[*next] -= 1;
if incoming[*next] == 0 {
queue.push_back(*next);
}
}
}
if ordered.len() == rules.len() {
return Ok(ordered);
}
Err(PlanBuildError::DependencyCycle {
chain: detect_cycle(rules, edges.as_slice()),
})
}
fn rules_intersect(from_rule: &'static dyn RewriteRule, to_rule: &'static dyn RewriteRule) -> bool {
from_rule
.meta()
.produces
.targets
.iter()
.copied()
.map(RuleTarget::key)
.any(|produced| {
to_rule
.meta()
.consumes
.eliminates
.iter()
.chain(to_rule.meta().consumes.touches.iter())
.copied()
.map(RuleTarget::key)
.any(|consumed| consumed == produced)
})
}
fn detect_cycle(rules: &[&'static dyn RewriteRule], edges: &[Vec<usize>]) -> Vec<RuleKey> {
let mut stack = Vec::new();
let mut state = vec![0u8; rules.len()];
for index in 0..rules.len() {
if let Some(chain) = visit_cycle(index, rules, edges, &mut state, &mut stack) {
return chain;
}
}
rules.iter().map(|rule| rule.meta().key).collect()
}
fn visit_cycle(
index: usize,
rules: &[&'static dyn RewriteRule],
edges: &[Vec<usize>],
state: &mut [u8],
stack: &mut Vec<usize>,
) -> Option<Vec<RuleKey>> {
if state[index] == 1 {
let cycle_start = stack.iter().position(|node| *node == index).unwrap_or(0);
let mut chain = stack[cycle_start..]
.iter()
.map(|node| rules[*node].meta().key)
.collect::<Vec<_>>();
chain.push(rules[index].meta().key);
return Some(chain);
}
if state[index] == 2 {
return None;
}
state[index] = 1;
stack.push(index);
for &next in &edges[index] {
if let Some(chain) = visit_cycle(next, rules, edges, state, stack) {
return Some(chain);
}
}
stack.pop();
state[index] = 2;
None
}
#[cfg(test)]
mod tests {
use texform_knowledge::builtin::base;
use super::*;
use crate::ast::NodeId;
use crate::rewrite::rule::{
NormalizationLevel, RuleConsumes, RuleEffect, RuleFidelity, RuleMeta, RuleProduces,
};
use crate::rewrite::rule_context::RuleContext;
use crate::rewrite::{RuleError, cmd_targets};
#[test]
fn metadata_validation_rejects_fidelity_below_level_floor() {
let err = validate_rule_metadata(&SEMANTIC_STANDARD_RULE)
.expect_err("standard rules must not declare semantic fidelity");
assert_eq!(
err,
PlanBuildError::InvalidRuleMetadata {
rule: SemanticStandardRule::KEY,
message: "fidelity must not be below the normalization level floor",
}
);
}
struct SemanticStandardRule;
static SEMANTIC_STANDARD_RULE: SemanticStandardRule = SemanticStandardRule;
impl SemanticStandardRule {
const KEY: RuleKey = RuleKey {
package: PackageName::Base,
name: "semantic-standard-test",
};
}
impl RewriteRule for SemanticStandardRule {
fn meta(&self) -> &'static RuleMeta {
static META: RuleMeta = RuleMeta {
key: SemanticStandardRule::KEY,
enabled_by_packages: &[PackageName::Base],
level: NormalizationLevel::Standard,
summary: "Test-only invalid metadata.",
fidelity: RuleFidelity::Semantic,
triggers: cmd_targets![&base::cmd::BREAK],
consumes: RuleConsumes {
eliminates: cmd_targets![&base::cmd::BREAK],
touches: &[],
},
produces: RuleProduces { targets: &[] },
};
&META
}
fn apply(
&self,
_cx: &mut RuleContext<'_>,
_node_id: NodeId,
) -> Result<RuleEffect, RuleError> {
Ok(RuleEffect::Skipped)
}
}
}