//! AST traversal with ability to read up the tree from visitors.
//!
//! Please see [`traverse_mut`] for an explanation of API.
//!
//! # Implementation details
//!
//! Most of the code in this crate is generated by a codegen.
//! Codegen is currently written in JavaScript (`scripts/build.mjs`).
//!
//! Do not edit those files, as they'll be over-written by the build script on next run.
//!
//! The scheme which allows reading up the tree is based on making it statically impossible
//! to violate Rust's aliasing rules.
//!
//! Rust's aliasing rules are (roughly):
//! 1. For any object, you can have as many immutable `&` references simultaneously as you like.
//! 2. For any object, you cannot obtain a mutable `&mut` reference if any other references
//!    (immutable or mutable) to that same object exist.
//! 3. A `&`/`&mut` ref covers the object itself and the entire tree below it.
//!    i.e. you can't hold a `&mut` to child and any reference to parent at same time (except by
//!    "re-borrowing").
//!
//! This poses a problem for reading back up the tree in a mutating visitor.
//! In a visitor you hold a `&mut` reference to a node, so therefore cannot obtain a `&` ref to
//! its parent, because the parent owns the node. If you had a `&` ref to the parent, that also acts
//! as a `&` ref to the current node = holding `&` and `&mut` refs to same node simultaneously.
//! Disaster!
//!
//! The solution this crate uses is:
//! 1. Don't create references while traversing down the AST in `walk_*` functions.
//!    Use raw pointers instead. `&mut` references are only created in the `enter_*` / `exit_*` methods.
//! 2. Don't allow `enter_*` / `exit_*` to access its entire parent or ancestor, only *other branches*
//!    of the tree which lead from the parent/ancestor. The parts of the tree above current node
//!    which can be accessed via `ctx.parent()` etc **do not overlap** the part of the tree which
//!    is available via `&mut` ref inside `enter_*` / `exit_*`. This makes it impossible to obtain
//!    2 references to same AST node at same time.
//! 3. Again, don't create transient references while getting the fields of ancestors. Use raw pointers
//!    to go to the field directly, before creating a `&` ref.
//!
//! The mechanism for this is the `Ancestor` enum. Each AST node type has several `Ancestor` variants
//! e.g. `ProgramWithoutDirectives`, `ProgramWithoutHashbang`, `ProgramWithoutBody`.
//! As the names suggest, each of these types grants access to all the fields of `Program` except one.
//!
//! As `walk_*` functions walk down the tree, they add to the stack of `Ancestors` the appropriate type
//! to prevent access to the path which is being walked down.
//!
//! `walk_*` uses `TraverseCtx::retag_stack` to make it as cheap as possible to update the ancestry
//! stack, but this is purely a performance optimization, not essential to the safety of the scheme.
//!
//! # SAFETY
//! This crate contains a great deal of unsafe code. The entirety of `walk.rs` is unsafe functions
//! using raw pointers.
//!
//! To avoid a drain on compile time asking Rust to parse 1000s of `# SAFETY` comments, the codegen-ed
//! files do not contain comments explaining the safety of every unsafe operation.
//! But everything works according to the principles outlined above.
//!
//! Almost all the code is currently codegen-ed. I (@overlookmotel) would recommend continuing to
//! exclusively use a codegen, and not manually editing these files for "special cases". The safety
//! scheme could very easily be derailed entirely by a single mistake, so in my opinion, it's unwise
//! to edit by hand.

use oxc_allocator::Allocator;

use oxc_ast::ast::Program;

pub mod ancestor;
pub use ancestor::Ancestor;
mod context;
pub use context::{FinderRet, TraverseCtx};
#[allow(clippy::module_inception)]
mod traverse;
pub use traverse::Traverse;
mod walk;

/// Traverse AST with a [`Traverse`] impl.
///
/// This allows:
/// 1. Reading and mutating down the tree (i.e. children, children's children, ...)
/// 2. Reading up the tree (i.e. parent, grandparent, ...)
///
/// `traverser`'s `enter_*` and `exit_*` methods will be called with a `&mut` ref to current AST node
/// and a [`TraverseCtx`] object.
///
/// [`TraverseCtx`] can be used to access parent or ancestors further up the tree.
/// [`TraverseCtx::parent`] and [`TraverseCtx::ancestor`] return an [`Ancestor`] type.
///
/// [`Ancestor`] is an enum, whose discriminant encodes both the *type* of the parent,
/// and *location* of the child within the parent.
/// e.g. `Ancestor` has variants for `BinaryExpressionLeft` and `BinaryExpressionRight`,
/// not just `BinaryExpression`.
///
/// To avoid violating Rust's aliasing rules, you cannot access the property of the parent
/// which current node is the child of.
///
/// Or, to state the rule more generally: You can read from any branch of the AST *except*
/// the one you are on.
///
/// A silly analogy: You are a tree surgeon working on pruning an old oak tree. You are sitting
/// on a branch high up in the tree. From that position, you can cut off other branches of the tree
/// no problem, but it would be unwise to saw off the branch that you are sitting on.
///
/// In practice: For this JS code:
///
/// ```js
/// x == 1
/// ```
///
/// ```
/// use oxc_ast::ast::*;
/// use oxc_traverse::{Ancestor, Traverse, TraverseCtx};
///
/// struct MyTransform;
///
/// impl<'a> Traverse<'a> for MyTransform {
///     fn enter_numeric_literal(&mut self, node: &mut NumericLiteral<'a>, ctx: &TraverseCtx<'a>) {
///         // Read parent
///         if let Ancestor::BinaryExpressionRight(bin_expr_ref) = ctx.parent() {
///             // This is legal
///             if let Expression::Identifier(id) = bin_expr_ref.left() {
///                 println!("left side is ID: {}", &id.name);
///             }
///
///             // This would be a compile failure, because the right side is where we came from
///             // dbg!(bin_expr_ref.right());
///         }
///
///         // Read grandparent
///         if let Some(Ancestor::ExpressionStatementExpression(stmt_ref)) = ctx.ancestor(2) {
///             // This is legal
///             println!("expression stmt's span: {:?}", stmt_ref.span());
///
///             // This would be a compile failure, because the expression is where we came from
///             // dbg!(stmt_ref.expression());
///         }
///     }
/// }
/// ```
#[allow(unsafe_code)]
pub fn traverse_mut<'a, Tr: Traverse<'a>>(
    traverser: &mut Tr,
    program: &mut Program<'a>,
    allocator: &'a Allocator,
) {
    let mut ctx = TraverseCtx::new(allocator);
    // SAFETY: Walk functions are constructed to avoid unsoundness
    unsafe { walk::walk_program(traverser, program as *mut Program, &mut ctx) };
    debug_assert!(ctx.ancestors_depth() == 1);
    debug_assert!(ctx.scopes_depth() == 1);
}