1use bool_logic::ast::{All, Any, Not, Var, any, expr};
2use bool_logic::cfg::ast::{Expr, Pred, flag, target_family};
3use bool_logic::visit_mut::{VisitMut, walk_mut_expr, walk_mut_expr_list};
4
5use bool_logic::transforms::dedup_list::DedupList;
6use bool_logic::transforms::eval_const::EvalConst;
7use bool_logic::transforms::flatten_nested_list::FlattenNestedList;
8use bool_logic::transforms::flatten_single::FlattenSingle;
9use bool_logic::transforms::merge_all_of_any::MergeAllOfAny;
10use bool_logic::transforms::merge_all_of_not_any::MergeAllOfNotAny;
11use bool_logic::transforms::simplify_all_not_any::SimplifyAllNotAny;
12use bool_logic::transforms::simplify_by_short_circuit::SimplifyByShortCircuit;
13use bool_logic::transforms::simplify_nested_list::SimplifyNestedList;
14
15use std::cmp::Ordering;
16use std::cmp::Ordering::{Equal, Greater, Less};
17use std::mem;
18
19use stdx::iter::filter_map_collect_vec;
20use stdx::iter::map_collect_vec;
21use stdx::vec::VecExt;
22
23use log::debug;
24use log::trace;
25
26pub fn simplified_expr(x: impl Into<Expr>) -> Expr {
27 let mut x = x.into();
28
29 debug!("input: {x}");
30
31 UnifyTargetFamily.visit_mut_expr(&mut x);
32 trace!("after UnifyTargetFamily: {x}");
33
34 for _ in 0..3 {
35 FlattenSingle.visit_mut_expr(&mut x);
36 trace!("after FlattenSingle: {x}");
37
38 FlattenNestedList.visit_mut_expr(&mut x);
39 trace!("after FlattenNestedList: {x}");
40
41 DedupList.visit_mut_expr(&mut x);
42 trace!("after DedupList: {x}");
43
44 EvalConst.visit_mut_expr(&mut x);
45 trace!("after EvalConst: {x}");
46
47 SimplifyNestedList.visit_mut_expr(&mut x);
48 trace!("after SimplifyNestedList: {x}");
49
50 MergeAllOfNotAny.visit_mut_expr(&mut x);
51 trace!("after MergeAllOfNotAny: {x}");
52
53 SimplifyAllNotAny.visit_mut_expr(&mut x);
54 trace!("after SimplifyAllNotAny: {x}");
55
56 MergeAllOfAny.visit_mut_expr(&mut x);
57 trace!("after MergeAllOfAny: {x}");
58
59 ImplyByKey.visit_mut_expr(&mut x);
60 trace!("after ImplyByKey: {x}");
61
62 SuppressTargetFamily.visit_mut_expr(&mut x);
63 trace!("after SuppressTargetFamily: {x}");
64
65 EvalConst.visit_mut_expr(&mut x);
66 trace!("after EvalConst: {x}");
67
68 MergePattern.visit_mut_expr(&mut x);
69 trace!("after MergePattern: {x}");
70
71 EvalConst.visit_mut_expr(&mut x);
72 trace!("after EvalConst: {x}");
73
74 SimplifyByShortCircuit.visit_mut_expr(&mut x);
75 trace!("after SimplifyByShortCircuit: {x}");
76
77 EvalConst.visit_mut_expr(&mut x);
78 trace!("after EvalConst: {x}");
79 }
80
81 SimplifyTargetFamily.visit_mut_expr(&mut x);
82 trace!("after SimplifyTargetFamily: {x}");
83
84 SortByPriority.visit_mut_expr(&mut x);
85 trace!("after SortByPriority: {x}");
86
87 SortByValue.visit_mut_expr(&mut x);
88 trace!("after SortByValue: {x}");
89
90 debug!("output: {x}");
91
92 x
93}
94
95struct SortByPriority;
96
97impl SortByPriority {
98 fn get_priority(x: &Expr) -> u32 {
99 match x {
100 Expr::Not(_) => 103,
101 Expr::Any(_) => 101,
102 Expr::All(_) => 102,
103 Expr::Var(Var(pred)) => match pred.key.as_str() {
104 "target_family" => 1,
105 "target_arch" => 2,
106 "target_vendor" => 3,
107 "target_os" => 4,
108 "target_env" => 5,
109 "target_pointer_width" => 6,
110 _ => 0,
111 },
112 Expr::Const(_) => panic!(),
113 }
114 }
115}
116
117impl VisitMut<Pred> for SortByPriority {
118 fn visit_mut_expr(&mut self, expr: &mut Expr) {
119 if let Some(list) = expr.as_mut_expr_list() {
120 list.sort_by(|lhs, rhs| {
121 let lhs = Self::get_priority(lhs);
122 let rhs = Self::get_priority(rhs);
123 lhs.cmp(&rhs)
124 });
125 }
126
127 walk_mut_expr(self, expr);
128 }
129}
130
131struct SortByValue;
132
133impl SortByValue {
134 fn cmp_var(lhs: &Expr, rhs: &Expr) -> Ordering {
135 let Expr::Var(Var(lhs)) = lhs else {
136 return Equal;
137 };
138 let Expr::Var(Var(rhs)) = rhs else {
139 return Equal;
140 };
141
142 let ok = Ord::cmp(lhs.key.as_str(), rhs.key.as_str());
143
144 match (lhs.value.as_deref(), rhs.value.as_deref()) {
145 (None, None) => ok,
146 (Some(lv), Some(rv)) => ok.then_with(|| Ord::cmp(lv, rv)),
147 (None, Some(_)) => Less,
148 (Some(_), None) => Greater,
149 }
150 }
151
152 fn cmp_not(lhs: &Expr, rhs: &Expr) -> Ordering {
153 let Expr::Not(Not(lhs)) = lhs else {
154 return Equal;
155 };
156 let Expr::Not(Not(rhs)) = rhs else {
157 return Equal;
158 };
159
160 Self::cmp_var(lhs, rhs)
161 }
162}
163
164impl VisitMut<Pred> for SortByValue {
165 fn visit_mut_expr(&mut self, expr: &mut Expr) {
166 if let Some(list) = expr.as_mut_expr_list() {
167 list.sort_by(Self::cmp_var);
168 list.sort_by(Self::cmp_not);
169 }
170
171 walk_mut_expr(self, expr);
172 }
173}
174
175struct UnifyTargetFamily;
176
177impl VisitMut<Pred> for UnifyTargetFamily {
178 fn visit_mut_var(&mut self, Var(pred): &mut Var<Pred>) {
179 if pred.value.is_none() && matches!(pred.key.as_str(), "unix" | "windows" | "wasm") {
180 *pred = target_family(pred.key.clone());
181 }
182 }
183}
184
185struct SimplifyTargetFamily;
186
187impl VisitMut<Pred> for SimplifyTargetFamily {
188 fn visit_mut_var(&mut self, Var(pred): &mut Var<Pred>) {
189 if pred.key == "target_family" {
190 if let Some(value) = pred.value.as_deref() {
191 if matches!(value, "unix" | "windows" | "wasm") {
192 *pred = flag(value);
193 }
194 }
195 }
196 }
197}
198
199struct ImplyByKey;
200
201impl ImplyByKey {
202 const UNIQUE_VALUED_KEYS: &'static [&'static str] = &[
203 "target_family",
204 "target_arch",
205 "target_vendor",
206 "target_os",
207 "target_env",
208 "target_pointer_width",
209 ];
210
211 fn is_expr_any_pred(any: &[Expr], key: &str) -> bool {
212 any.iter()
213 .all(|x| x.as_var().is_some_and(|Var(var)| var.key == key))
214 }
215
216 fn fix(pos_key: &str, pos_any_values: &[&str], expr: &mut Expr) {
217 match expr {
218 Expr::Any(Any(any)) => {
219 for x in any.iter_mut() {
220 Self::fix(pos_key, pos_any_values, x);
221 }
222 }
223 Expr::All(All(all)) => {
224 for x in all.iter_mut() {
225 Self::fix(pos_key, pos_any_values, x);
226 }
227 }
228 Expr::Not(Not(not)) => {
229 Self::fix(pos_key, pos_any_values, not);
230 }
231 Expr::Var(Var(var)) => {
232 if var.key == pos_key {
233 let var_value = var.value.as_deref().unwrap();
234 if pos_any_values.contains(&var_value) {
235 if pos_any_values.len() == 1 {
236 *expr = Expr::Const(true);
237 }
238 } else {
239 *expr = Expr::Const(false);
240 }
241 }
242 }
243 Expr::Const(_) => {}
244 }
245 }
246}
247
248impl VisitMut<Pred> for ImplyByKey {
249 fn visit_mut_all(&mut self, All(all): &mut All<Pred>) {
250 walk_mut_expr_list(self, all);
251
252 let mut i = 0;
253 while i < all.len() {
254 match &all[i] {
255 Expr::Var(Var(pos)) => {
256 if Self::UNIQUE_VALUED_KEYS.contains(&pos.key.as_str()) {
257 assert!(pos.value.is_some());
258
259 let pos = pos.clone();
260 let pos_key = pos.key.as_str();
261 let pos_any_values = &[pos.value.as_deref().unwrap()];
262
263 for (_, x) in all.iter_mut().enumerate().filter(|&(j, _)| j != i) {
264 Self::fix(pos_key, pos_any_values, x);
265 }
266 }
267 }
268 Expr::Any(Any(any)) => {
269 if let Some(pos_key) = Self::UNIQUE_VALUED_KEYS
270 .iter()
271 .find(|k| Self::is_expr_any_pred(any, k))
272 {
273 let any = any.clone();
274 let pos_any_values = map_collect_vec(&any, |x| {
275 x.as_var().unwrap().0.value.as_deref().unwrap()
276 });
277
278 for (_, x) in all.iter_mut().enumerate().filter(|&(j, _)| j != i) {
279 Self::fix(pos_key, &pos_any_values, x);
280 }
281 }
282 }
283 _ => {}
284 }
285 i += 1;
286 }
287 }
288}
289
290struct SuppressTargetFamily;
291
292impl SuppressTargetFamily {
293 fn is_target_os_pred(x: &Expr) -> bool {
294 match x {
295 Expr::Var(Var(var)) => var.key == "target_os",
296 _ => false,
297 }
298 }
299
300 fn has_specified_target_os(x: &Expr) -> bool {
301 if Self::is_target_os_pred(x) {
302 return true;
303 }
304
305 if let Expr::Any(Any(any)) = x {
306 return any.iter().all(Self::is_target_os_pred);
307 }
308
309 false
310 }
311
312 #[allow(clippy::match_like_matches_macro)]
313 fn is_suppressed_target_family(pred: &Pred) -> bool {
314 match (pred.key.as_str(), pred.value.as_deref()) {
315 ("target_family", Some("unix")) => true,
316 ("target_family", Some("windows")) => true,
317 _ => false,
318 }
319 }
320}
321
322impl VisitMut<Pred> for SuppressTargetFamily {
323 fn visit_mut_all(&mut self, All(all): &mut All<Pred>) {
324 if all.iter().any(Self::has_specified_target_os) {
325 all.remove_if(|x| match x {
326 Expr::Var(Var(pred)) => Self::is_suppressed_target_family(pred),
327 Expr::Not(Not(not)) => match &**not {
328 Expr::Var(Var(pred)) => Self::is_suppressed_target_family(pred),
329 _ => false,
330 },
331 _ => false,
332 });
333 }
334
335 walk_mut_expr_list(self, all);
336 }
337}
338
339struct MergePattern;
340
341impl MergePattern {
342 fn merge(any_list: &mut [Expr]) {
343 let mut pattern_list = filter_map_collect_vec(any_list, |x| {
344 if let Expr::All(All(all)) = x {
345 if let [first, second] = all.as_mut_slice() {
346 if first.is_any() || first.is_var() {
347 return Some((first, second));
348 }
349 }
350 }
351 None
352 });
353
354 if let [head, rest @ ..] = pattern_list.as_mut_slice() {
355 let agg = match head.0 {
356 Expr::Any(Any(any)) => any,
357 Expr::Var(var) => {
358 *head.0 = expr(any((var.clone(),)));
359 head.0.as_mut_any().map(|x| &mut x.0).unwrap()
360 }
361 _ => panic!(),
362 };
363
364 for x in rest {
365 let to_agg = if x.1 == head.1 {
366 &mut *x.0
367 } else if x.0 == head.1 {
368 &mut *x.1
369 } else {
370 continue;
371 };
372
373 match mem::replace(to_agg, Expr::Const(false)) {
374 Expr::Any(Any(any)) => agg.extend(any),
375 Expr::Var(var) => agg.push(expr(var.clone())),
376 other => *to_agg = other,
377 }
378 }
379
380 if agg.len() == 1 {
381 *head.0 = agg.pop().unwrap();
382 }
383 }
384 }
385}
386
387impl VisitMut<Pred> for MergePattern {
388 fn visit_mut_any(&mut self, Any(any_list): &mut Any<Pred>) {
389 Self::merge(any_list);
390 Self::merge(&mut any_list[1..]);
391 }
392}
393
394#[cfg(test)]
395mod tests {
396 use bool_logic::ast::all;
397 use bool_logic::ast::not;
398 use bool_logic::cfg::ast::target_os;
399
400 use super::*;
401
402 #[test]
403 fn sort() {
404 let mut expr = expr(all((not(flag("unix")), flag("unix"))));
405 SortByPriority.visit_mut_expr(&mut expr);
406 assert_eq!(expr.to_string(), "all(unix, not(unix))");
407 }
408
409 #[test]
410 fn imply() {
411 {
412 let mut expr = expr(all((target_os("linux"), not(target_os("emscripten")))));
413 ImplyByKey.visit_mut_expr(&mut expr);
414 assert_eq!(expr.to_string(), r#"all(target_os = "linux", not(false))"#);
415 }
416 {
417 let mut expr = expr(all((
418 any((target_os("ios"), target_os("macos"))), any((target_os("linux"), target_os("android"))), )));
421 ImplyByKey.visit_mut_expr(&mut expr);
422 assert_eq!(
423 expr.to_string(),
424 r#"all(any(target_os = "ios", target_os = "macos"), any(false, false))"#
425 );
426 }
427 }
428}