mangle_analysis/lib.rs
1// Copyright 2024 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Analysis and Transformation Pipeline for Mangle.
16//!
17//! This crate provides the core analysis passes and transformations that turn
18//! a parsed Mangle AST into an executable plan.
19//!
20//! # Transformation Stages
21//!
22//! 1. **Program Structure**: The raw AST is wrapped in a [`Program`] abstraction
23//! which distinguishes between extensional (data) and intensional (rules) predicates.
24//!
25//! 2. **Stratification**: The program is analyzed for dependencies and stratified
26//! to handle negation correctly. This produces a [`StratifiedProgram`], where
27//! predicates are grouped into layers (strata) that can be evaluated sequentially.
28//!
29//! 3. **Lowering**: The AST (or stratified program parts) is lowered into the
30//! Intermediate Representation (IR). See [`LoweringContext`].
31//!
32//! 4. **Type Checking**: The IR is checked for type consistency and safety.
33//! See [`TypeChecker`].
34//!
35//! 5. **Planning**: The Logical IR rules are transformed into Physical Operations
36//! (like nested-loop joins) ready for execution or codegen.
37//! See [`Planner`].
38
39use mangle_ast as ast;
40
41mod type_check;
42
43pub use type_check::TypeChecker;
44
45#[cfg(test)]
46mod tests;
47
48mod lowering;
49
50pub use lowering::LoweringContext;
51
52mod rename;
53
54pub use rename::rewrite_unit;
55
56mod planner;
57
58pub use planner::Planner;
59
60mod stratification;
61
62pub use stratification::{Program, StratifiedProgram};
63
64/// A set of predicate symbols, typically used to represent a stratum or a
65/// collection of EDB/IDB predicates.
66pub type PredicateSet = fxhash::FxHashSet<ast::PredicateIndex>;