//! 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 `tasks/ast_tools/src/generators/traverse/`.
//!
//! Do not edit those generated files, as they'll be over-written on next run of `just ast`.
//!
//! 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 std::ptr;

use oxc_allocator::Allocator;
use oxc_ast::ast::Program;
use oxc_semantic::Scoping;

pub mod ast_operations;
mod context;
pub use context::{
    BoundIdentifier, MaybeBoundIdentifier, ReusableTraverseCtx, TraverseAncestry, TraverseCtx,
    TraverseScoping,
};

mod generated {
    pub mod ancestor;
    pub mod scopes_collector;
    pub mod traverse;
    pub mod walk;
}
pub use generated::{ancestor, ancestor::Ancestor, traverse::Traverse};
use generated::{scopes_collector, walk::walk_ast};

mod compile_fail_tests;

/// 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: &mut 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 Ancestor::ExpressionStatementExpression(stmt_ref) = ctx.ancestor(1) {
///             // 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());
///         }
///     }
/// }
/// ```
pub fn traverse_mut<'a, State, Tr: Traverse<'a, State>>(
    traverser: &mut Tr,
    allocator: &'a Allocator,
    program: &mut Program<'a>,
    scoping: Scoping,
    state: State,
) -> Scoping {
    let mut ctx = ReusableTraverseCtx::new(state, scoping, allocator);
    traverse_mut_with_ctx(traverser, program, &mut ctx);
    ctx.into_scoping()
}

/// Traverse AST with a [`Traverse`] impl, reusing an existing [`ReusableTraverseCtx`].
///
/// [`ReusableTraverseCtx`] is specific to a single AST. It will likely cause malfunction if
/// `traverse_mut_with_ctx` is called with a [`Program`] and [`ReusableTraverseCtx`] which do not match.
///
/// See [`traverse_mut`] for more details of how traversal works.
pub fn traverse_mut_with_ctx<'a, State, Tr: Traverse<'a, State>>(
    traverser: &mut Tr,
    program: &mut Program<'a>,
    ctx: &mut ReusableTraverseCtx<'a, State>,
) {
    let program = ptr::from_mut(program);

    let ctx = ctx.get_mut();

    // Check that `TraverseAncestry`'s stack is in correct state
    debug_assert_eq!(ctx.ancestors_depth(), 1);
    debug_assert!(matches!(ctx.parent(), Ancestor::None));

    // SAFETY:
    // `program` is a valid pointer to a `Program<'a>` - it was created from a `&mut Program<'a>`.
    //
    // `TraverseCtx`s are always created with only `Ancestor::None` on `TraverseAncestry` stack.
    // `TraverseCtx` provides no external interfaces for caller to mutate `TraverseAncestry`,
    // so that cannot be changed by the caller.
    //
    // `walk_*` methods never alter the initial entry on `TraverseAncestry`'s stack.
    // `walk_*` methods always follow a `push` to `TraverseAncestry`'s stack with a corresponding `pop`.
    // So at end of traversal, `TraverseAncestry`'s stack is always back in the state it was at start
    // of traversal (single `Ancestor::None` entry).
    //
    // `ctx` was contained in a `ReusableTraverseCtx<'a>`. `ReusableTraverseCtx<'a>` provides no external
    // interfaces for caller to mutate the `TraverseCtx` it contains.
    //
    // Therefore `TraverseAncestry`'s stack is guaranteed to only contain single `Ancestor::None` entry.
    unsafe { walk_ast(traverser, program, ctx) };

    // Check that `TraverseAncestry`'s stack is in correct state
    debug_assert_eq!(ctx.ancestors_depth(), 1);
    debug_assert!(matches!(ctx.parent(), Ancestor::None));
}
