use etdl_parser::ast::{EtlDocument, FaultTree, GateType};
use std::collections::{BTreeMap, HashMap, VecDeque};
use crate::validate::Diagnostic;
pub type FaultTreeProbabilities = BTreeMap<String, f64>;
pub fn resolve_fault_trees(
doc: &EtlDocument,
diagnostics: &mut Vec<Diagnostic>,
) -> FaultTreeProbabilities {
let mut results = BTreeMap::new();
let fault_trees = match &doc.fault_trees {
Some(fts) => fts,
None => return results,
};
for (ft_id, ft) in fault_trees {
match compute_top_event_probability(ft) {
Ok(prob) => {
results.insert(ft_id.clone(), prob);
}
Err(e) => {
diagnostics.push(Diagnostic::error(
"V-401",
format!(
"fault tree '{}': error computing probability: {}",
ft_id, e
),
));
}
}
}
results
}
fn compute_top_event_probability(ft: &FaultTree) -> Result<f64, String> {
let mut probs: HashMap<String, f64> = HashMap::new();
for (be_id, be) in &ft.basic_events {
let prob = compute_basic_event_probability(be)?;
probs.insert(be_id.clone(), prob);
}
let gates = match &ft.gates {
Some(g) => g,
None => {
let root_id = &ft.top_event.root_cause;
if let Some(&prob) = probs.get(root_id) {
return Ok(prob);
} else {
return Err(format!(
"topEvent.rootCause '{}' not found in basic events and no gates defined",
root_id
));
}
}
};
let order = topological_sort_gates(gates, &ft.top_event.root_cause)?;
for gate_id in &order {
let gate = gates.get(gate_id).ok_or_else(|| {
format!("gate '{}' not found during resolution", gate_id)
})?;
let input_probs: Vec<f64> = gate
.inputs
.iter()
.map(|input| {
probs
.get(input.as_str())
.copied()
.ok_or_else(|| format!("probability for '{}' not resolved", input))
})
.collect::<Result<Vec<_>, _>>()?;
let gate_prob = compute_gate_probability(&gate.gate_type, &input_probs, gate.k)?;
probs.insert(gate_id.clone(), gate_prob);
}
let root_id = &ft.top_event.root_cause;
probs
.get(root_id)
.copied()
.ok_or_else(|| format!("topEvent.rootCause '{}' probability not resolved", root_id))
}
fn compute_basic_event_probability(
be: &etdl_parser::ast::BasicEvent,
) -> Result<f64, String> {
if let Some(ref failure_rate) = be.failure_rate {
let mission_time = be
.mission_time
.ok_or("failureRate set but missionTime missing")?;
Ok(1.0 - (-failure_rate * mission_time).exp())
} else if let Some(prob) = be.probability {
if prob < 0.0 || prob > 1.0 {
return Err(format!(
"probability {} out of range [0, 1]",
prob
));
}
Ok(prob)
} else {
Err("basic event has neither probability nor failureRate".to_string())
}
}
fn compute_gate_probability(
gate_type: &GateType,
inputs: &[f64],
k: Option<u32>,
) -> Result<f64, String> {
match gate_type {
GateType::And => {
Ok(inputs.iter().product())
}
GateType::Or => {
let complement: f64 = inputs.iter().map(|p| 1.0 - p).product();
Ok(1.0 - complement)
}
GateType::Not => {
if inputs.len() != 1 {
return Err("NOT gate requires exactly 1 input".to_string());
}
if inputs[0] < 0.0 || inputs[0] > 1.0 {
return Err(format!("NOT gate input probability {} out of range", inputs[0]));
}
Ok(1.0 - inputs[0])
}
GateType::Xor => {
if inputs.len() != 2 {
return Err("XOR gate requires exactly 2 inputs".to_string());
}
Ok(inputs[0] + inputs[1] - 2.0 * inputs[0] * inputs[1])
}
GateType::Voting => {
let k_val = k.ok_or("VOTING gate requires k")? as usize;
let n = inputs.len();
if k_val < 1 || k_val > n {
return Err(format!(
"VOTING gate: k={} out of range [1, {}]",
k_val, n
));
}
if inputs.iter().all(|&p| (p - inputs[0]).abs() < 1e-10) {
let p = inputs[0];
let mut total = 0.0;
for j in k_val..=n {
total += binomial_coeff(n, j) as f64
* p.powi(j as i32)
* (1.0 - p).powi((n - j) as i32);
}
Ok(total)
} else {
let mut poly = vec![1.0];
for &p in inputs {
poly = multiply_polynomial(&poly, &[1.0 - p, p]);
}
let mut total = 0.0;
for j in k_val..=n {
if j < poly.len() {
total += poly[j];
}
}
Ok(total.clamp(0.0, 1.0))
}
}
}
}
fn binomial_coeff(n: usize, k: usize) -> usize {
if k > n {
return 0;
}
let mut result = 1usize;
for i in 0..k {
result = result * (n - i) / (i + 1);
}
result
}
fn multiply_polynomial(a: &[f64], b: &[f64]) -> Vec<f64> {
let mut result = vec![0.0; a.len() + b.len() - 1];
for (i, &coeff_a) in a.iter().enumerate() {
for (j, &coeff_b) in b.iter().enumerate() {
result[i + j] += coeff_a * coeff_b;
}
}
result
}
fn topological_sort_gates(
gates: &BTreeMap<String, etdl_parser::ast::Gate>,
root_id: &str,
) -> Result<Vec<String>, String> {
let mut in_degree: HashMap<&str, usize> = HashMap::new();
let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
for gate_id in gates.keys() {
in_degree.entry(gate_id.as_str()).or_insert(0);
adj.entry(gate_id.as_str()).or_default();
}
for (gate_id, gate) in gates {
for input in &gate.inputs {
if gates.contains_key(input.as_str()) {
adj.entry(input.as_str())
.or_default()
.push(gate_id.as_str());
*in_degree.entry(gate_id.as_str()).or_insert(0) += 1;
}
}
}
let mut queue: VecDeque<&str> = VecDeque::new();
for (&id, °) in &in_degree {
if deg == 0 {
queue.push_back(id);
}
}
let mut order = Vec::new();
while let Some(id) = queue.pop_front() {
order.push(id.to_string());
if let Some(children) = adj.get(id) {
for &child in children {
if let Some(deg) = in_degree.get_mut(child) {
*deg -= 1;
if *deg == 0 {
queue.push_back(child);
}
}
}
}
}
if order.len() != gates.len() {
return Err("cycle detected in fault tree gates (V-403)".to_string());
}
if !order.contains(&root_id.to_string()) {
order.push(root_id.to_string());
}
Ok(order)
}
pub fn enumerate_minimal_cut_sets(ft: &FaultTree) -> Result<Vec<Vec<String>>, String> {
let gates = match &ft.gates {
Some(g) => g,
None => {
return Ok(vec![vec![ft.top_event.root_cause.clone()]]);
}
};
for (_id, gate) in gates {
if matches!(gate.gate_type, GateType::Not | GateType::Xor) {
return Err(
"cannot enumerate cut sets for non-coherent fault tree (contains NOT or XOR gate)"
.to_string(),
);
}
}
let mut rows: Vec<Vec<String>> = vec![vec![ft.top_event.root_cause.clone()]];
let mut changed = true;
while changed {
changed = false;
let mut new_rows = Vec::new();
for row in &rows {
let gate_positions: Vec<(usize, &str)> = row
.iter()
.enumerate()
.filter(|(_, item)| gates.contains_key(item.as_str()))
.map(|(i, item)| (i, item.as_str()))
.collect();
if gate_positions.is_empty() {
new_rows.push(row.clone());
continue;
}
changed = true;
let (pos, gate_id) = gate_positions[0];
let gate = &gates[gate_id];
match gate.gate_type {
GateType::Or => {
for input in &gate.inputs {
let mut new_row = row.clone();
new_row.remove(pos);
new_row.insert(pos, input.clone());
new_rows.push(new_row);
}
}
GateType::And => {
let mut new_row = row.clone();
new_row.remove(pos);
for (offset, input) in gate.inputs.iter().enumerate() {
new_row.insert(pos + offset, input.clone());
}
new_rows.push(new_row);
}
GateType::Voting => {
let k = gate.k.unwrap_or(1) as usize;
let combinations = generate_combinations(&gate.inputs, k);
for combo in &combinations {
let mut new_row = row.clone();
new_row.remove(pos);
for (offset, input) in combo.iter().enumerate() {
new_row.insert(pos + offset, input.clone());
}
new_rows.push(new_row);
}
}
_ => {
return Err(format!(
"unexpected gate type {:?} in cut set enumeration",
gate.gate_type
));
}
}
}
rows = new_rows;
rows = minimize_rows(rows);
}
Ok(rows)
}
fn generate_combinations<T: Clone>(items: &[T], k: usize) -> Vec<Vec<T>> {
if k == 0 {
return vec![vec![]];
}
if items.is_empty() {
return vec![];
}
let mut result = Vec::new();
let first = &items[0];
let rest = &items[1..];
for mut combo in generate_combinations(rest, k - 1) {
let mut new_combo = vec![first.clone()];
new_combo.append(&mut combo);
result.push(new_combo);
}
for combo in generate_combinations(rest, k) {
result.push(combo);
}
result
}
fn minimize_rows(rows: Vec<Vec<String>>) -> Vec<Vec<String>> {
let mut sorted_rows: Vec<Vec<String>> = rows
.into_iter()
.map(|mut row| {
row.sort();
row.dedup();
row
})
.collect();
let mut i = 0;
while i < sorted_rows.len() {
let row_i = sorted_rows[i].clone();
sorted_rows.retain(|row_j| {
if std::ptr::eq(row_j, &row_i) {
return true;
}
let set_i: std::collections::BTreeSet<_> = row_i.iter().collect();
let set_j: std::collections::BTreeSet<_> = row_j.iter().collect();
!set_i.is_subset(&set_j)
});
i += 1;
}
sorted_rows
}