/*
 * DMNTK - Decision Model and Notation Toolkit
 *
 * FEEL definitions.
 *
 * Copyright 2018-2021 Dariusz Depta Engos Software <dariusz.depta@engos.software>
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

//! Implementation of a node in Abstract Syntax Tree for `FEEL` grammar.

use {
  crate::{types::FeelType, Name, Scope},
  dmntk_common::Stringify,
  std::{borrow::Borrow, str::FromStr},
};

/// Type for optional AST node.
pub type OptAstNode = Option<AstNode>;

/// Node of the Abstract Syntax Tree for `FEEL` grammar.
#[derive(Debug, Clone, PartialEq)]
pub enum AstNode {
  /// Node representing an arithmetic operator `+`.
  Add(Box<AstNode>, Box<AstNode>),

  /// Node representing a logical operator `and`.
  And(Box<AstNode>, Box<AstNode>),

  /// Node representing a date and time literal `@`.
  At(String),

  /// Node representing a comparison operator `between`.
  Between(Box<AstNode>, Box<AstNode>, Box<AstNode>),

  /// Node representing a value of type `boolean`.
  Boolean(bool),

  /// Node representing a comma separated list of nodes.
  CommaList(Vec<AstNode>),

  /// Node representing a context.
  /// Context entries are stored in the order of appearance in definition.
  Context(Vec<AstNode>),

  /// Node representing single context entry; key-value pair.
  ContextEntry(Box<AstNode>, Box<AstNode>),

  /// Node representing the key of the context entry; the key in context entry
  /// may be a name or string literal. String literals are converted to one segment names
  /// containing exactly the value of the string.
  ContextEntryKey(Name),

  /// Node representing the type of a context. Context type is defined by names
  /// and types of all entries. This node contains a collection of types
  /// for all context entries in order of appearance in definition.
  ContextType(Vec<AstNode>),

  /// Node representing single context type entry, name-type pair.
  ContextTypeEntry(Box<AstNode>, FeelType),

  /// Node representing arithmetic operator `/` (division).
  Div(Box<AstNode>, Box<AstNode>),

  ///
  Eq(Box<AstNode>, Box<AstNode>),

  ///
  Exp(Box<AstNode>, Box<AstNode>),

  ///
  ExpressionList(Vec<AstNode>),

  /// Node representing filter expression.
  FilterExpression(Box<AstNode>, Box<AstNode>),

  /// Node representing `for` expression (iteration clauses, evaluated expression).
  ForExpression(Vec<(Name, AstNode, OptAstNode)>, Box<AstNode>),

  /// Node representing function's formal parameter.
  /// This node holds mandatory parameter's name and optional parameter's type.
  /// Parameter's type must be valid `FEEL` type.
  FormalParameter(Name, FeelType),

  /// Node representing a list of formal parameters.
  FormalParameters(Vec<AstNode>),

  /// Node representing function's body. This node holds mandatory function body
  /// and a flag indicating if the function is external.
  FunctionBody(Box<AstNode>, bool),

  /// Node representing function definition.
  /// This node holds function's formal parameter list and  function's body.
  FunctionDefinition(Box<AstNode>, Box<AstNode>),

  /// Node representing function invocation.
  FunctionInvocation(Box<AstNode>, Box<AstNode>),

  /// Node representing function type (parameter types, result type).
  FunctionType(Box<AstNode>, FeelType),

  ///
  Ge(Box<AstNode>, Box<AstNode>),

  ///
  Gt(Box<AstNode>, Box<AstNode>),

  /// Node representing `IF` expression (condition, result_when_true, result_when_false).
  If(Box<AstNode>, Box<AstNode>, Box<AstNode>),

  ///
  In(Box<AstNode>, Box<AstNode>),

  ///
  InstanceOf(Box<AstNode>, FeelType),

  /// Node representing the interval end used in ranges.
  IntervalEnd(Box<AstNode>, bool),

  /// Node representing the interval start used in ranges.
  IntervalStart(Box<AstNode>, bool),

  /// Node representing the comparison operator `irrelevant`.
  Irrelevant,

  /// List of iteration clauses, containing list of variables bounded to iteration contexts.
  IterationClauses(Vec<AstNode>),

  /// Iteration context returning a single list of elements to iterate over.
  IterationContextSingle(Box<AstNode>),

  /// Iteration context built from the range of integers.
  IterationContextRange(Box<AstNode>, Box<AstNode>),

  ///
  Le(Box<AstNode>, Box<AstNode>),

  ///
  Lt(Box<AstNode>, Box<AstNode>),

  /// Node representing a list.
  List(Vec<AstNode>),

  /// Node representing list type; contains the type of list items.
  ListType(FeelType),

  /// Node representing arithmetic operator `*` (multiplication).
  Mul(Box<AstNode>, Box<AstNode>),

  ///
  Name(Name),

  /// Node representing single named parameter.
  NamedParameter(Box<AstNode>, Box<AstNode>),

  /// Node representing a collection of named parameters.
  NamedParameters(Vec<AstNode>),

  /// Node representing a negated list (used in negated unary tests).
  NegatedList(Vec<AstNode>),

  /// Unary arithmetic negation `-`.
  Neg(Box<AstNode>),

  ///
  Nq(Box<AstNode>, Box<AstNode>),

  /// Value of type `Null`.
  Null,

  /// Numeric value.
  Numeric(String, String),

  ///
  Or(Box<AstNode>, Box<AstNode>),

  ///
  Out(Box<AstNode>, Box<AstNode>),

  /// Name of the parameter in named parameter of the function invocation.
  ParameterName(Name),

  /// Node representing a collection of function parameter types.
  ParameterTypes(Vec<FeelType>),

  /// Node representing a path expression.
  Path(Box<AstNode>, Box<AstNode>),

  /// Node representing a collection of positional parameters.
  PositionalParameters(Vec<AstNode>),

  ///
  QualifiedName(Vec<Name>),

  /// List of quantified clauses, containing list of names bounded to expressions.
  QuantifiedClauses(Vec<AstNode>),

  ///
  QuantifiedExpressionEvery(Box<AstNode>, Box<AstNode>),

  ///
  QuantifiedExpressionSome(Box<AstNode>, Box<AstNode>),

  ///
  Range(Box<AstNode>, Box<AstNode>),

  /// Node representing a definition of type `range`.
  RangeType(FeelType),

  /// Value of type `string`.
  String(String),

  ///
  Sub(Box<AstNode>, Box<AstNode>),

  ///
  UnaryGe(Box<AstNode>),

  ///
  UnaryGt(Box<AstNode>),

  ///
  UnaryLe(Box<AstNode>),

  ///
  UnaryLt(Box<AstNode>),
}

impl ToString for AstNode {
  /// Converts [AstNode] to textual representation, including child nodes.
  fn to_string(&self) -> String {
    let mut output = "\n".to_string();
    self.trace_node(&mut output, 1);
    output.push_str("      ");
    output
  }
}

impl AstNode {
  /// Evaluates the type of the expression represented by this node.
  pub fn type_of(&self, scope: &Scope) -> FeelType {
    match self {
      AstNode::Add(lhs, rhs) => lhs.type_of(scope).zip(&rhs.type_of(scope)),
      AstNode::And { .. } => FeelType::Any,
      AstNode::At { .. } => FeelType::Any,
      AstNode::Between { .. } => FeelType::Any,
      AstNode::Boolean(_) => FeelType::Any,
      AstNode::CommaList { .. } => FeelType::Any,
      AstNode::Context { .. } => FeelType::Any,
      AstNode::ContextEntry { .. } => FeelType::Any,
      AstNode::ContextEntryKey(_) => FeelType::Any,
      AstNode::ContextType(items) => {
        if items.is_empty() {
          FeelType::Any
        } else {
          let mut type_entries = vec![];
          for item in items {
            if let AstNode::ContextTypeEntry(entry_name, feel_type) = item {
              if let AstNode::Name(name) = entry_name.borrow() {
                type_entries.push((name, feel_type));
              }
            }
          }
          FeelType::context(&type_entries)
        }
      }
      AstNode::ContextTypeEntry(_, feel_type) => feel_type.clone(),
      AstNode::Div(lhs, rhs) => lhs.type_of(scope).zip(&rhs.type_of(scope)),
      AstNode::Eq { .. } => FeelType::Boolean,
      AstNode::Exp { .. } => FeelType::Any,
      AstNode::ExpressionList { .. } => FeelType::Any,
      AstNode::FilterExpression { .. } => FeelType::Any,
      AstNode::ForExpression { .. } => {
        //
        FeelType::Any
      }
      AstNode::FormalParameter(_, feel_type) => feel_type.clone(),
      AstNode::FormalParameters(_) => FeelType::Any,
      AstNode::FunctionBody { .. } => FeelType::Any,
      AstNode::FunctionDefinition { .. } => FeelType::Any,
      AstNode::FunctionInvocation { .. } => FeelType::Any,
      AstNode::FunctionType(a, b) => {
        if let AstNode::ParameterTypes(items) = a.borrow() {
          FeelType::function(items, b)
        } else {
          FeelType::Any
        }
      }
      AstNode::Gt { .. } => FeelType::Any,
      AstNode::Ge { .. } => FeelType::Any,
      AstNode::If { .. } => FeelType::Any,
      AstNode::In { .. } => FeelType::Any,
      AstNode::InstanceOf { .. } => FeelType::Any,
      AstNode::Irrelevant => FeelType::Any,
      AstNode::IterationClauses { .. } => FeelType::Any,
      AstNode::IterationContextSingle { .. } => FeelType::Any,
      AstNode::IterationContextRange { .. } => FeelType::Any,
      AstNode::Lt { .. } => FeelType::Any,
      AstNode::Le { .. } => FeelType::Any,
      AstNode::Neg { .. } => FeelType::Any,
      AstNode::List(nodes) => {
        if nodes.is_empty() {
          FeelType::Any
        } else {
          let mut base_type = nodes[0].type_of(scope);
          for node in nodes.iter().skip(1) {
            base_type = base_type.zip(&node.type_of(scope));
          }
          base_type
        }
      }
      AstNode::ListType(feel_type) => FeelType::list(feel_type),
      AstNode::Mul { .. } => FeelType::Any,
      AstNode::Name(name) => {
        if let Ok(feel_type) = FeelType::from_str(name.to_string().as_str()) {
          feel_type
        } else {
          FeelType::Any
        }
      }
      AstNode::NamedParameter { .. } => FeelType::Any,
      AstNode::NamedParameters { .. } => FeelType::Any,
      AstNode::NegatedList { .. } => FeelType::Any,
      AstNode::Nq { .. } => FeelType::Boolean,
      AstNode::Null => FeelType::Null,
      AstNode::Numeric(_, _) => FeelType::Number,
      AstNode::Or { .. } => FeelType::Any,
      AstNode::Out { .. } => FeelType::Any,
      AstNode::ParameterName(_) => FeelType::Any,
      AstNode::ParameterTypes(_) => FeelType::Any,
      AstNode::Path { .. } => FeelType::Any,
      AstNode::PositionalParameters { .. } => FeelType::Any,
      AstNode::QualifiedName(_) => FeelType::Any,
      AstNode::QuantifiedClauses { .. } => FeelType::Any,
      AstNode::QuantifiedExpressionEvery { .. } => FeelType::Any,
      AstNode::QuantifiedExpressionSome { .. } => FeelType::Any,
      AstNode::Range { .. } => FeelType::Any,
      AstNode::RangeType(feel_type) => FeelType::range(feel_type),
      AstNode::String(_) => FeelType::String,
      AstNode::Sub { .. } => FeelType::Any,
      AstNode::UnaryGe { .. } => FeelType::Any,
      AstNode::UnaryGt { .. } => FeelType::Any,
      AstNode::UnaryLt { .. } => FeelType::Any,
      AstNode::UnaryLe { .. } => FeelType::Any,
      AstNode::IntervalEnd(_, _) => FeelType::Any,
      AstNode::IntervalStart(_, _) => FeelType::Any,
    }
  }

  /// Writes a trace of the AST starting from this node.
  pub fn trace(&self) {
    println!("      AST:{}", self.to_string());
  }

  /// Creates and indentation based on the level and margin.
  fn indent(&self, level: usize, number: usize) -> String {
    let mut indent = "      ".to_string();
    indent.push_str(&" ".repeat((level + number) * 2));
    indent
  }

  /// Writes a trace of a single AST node.
  fn trace_node(&self, output: &mut String, level: usize) {
    let i0 = self.indent(level, 0);
    let i1 = self.indent(level, 1);
    let i2 = self.indent(level, 2);
    let i3 = self.indent(level, 3);
    let i4 = self.indent(level, 4);
    match self {
      AstNode::Add(left, right) => {
        output.push_str(&&format!("{}Add\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::And(left, right) => {
        output.push_str(&format!("{}And\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::At(right) => {
        output.push_str(&format!("{}At `{}`\n", i0, right));
      }
      AstNode::Between(left, inner, right) => {
        output.push_str(&format!("{}Between\n", i0));
        left.trace_node(output, level + 1);
        inner.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Boolean(value) => {
        output.push_str(&format!("{}Boolean {}\n", i0, value));
      }
      AstNode::CommaList(items) => {
        if items.is_empty() {
          output.push_str(&format!("{}CommaList\n{}[]\n", i0, i1));
        } else {
          output.push_str(&format!("{}CommaList\n", i0));
          for item in items {
            item.trace_node(output, level + 1);
          }
        }
      }
      AstNode::Context(items) => {
        output.push_str(&format!("{}Context\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::ContextEntry(left, right) => {
        output.push_str(&format!("{}ContextEntry\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::ContextEntryKey(inner) => {
        output.push_str(&format!("{}ContextEntryKey `{}`\n", i0, inner.to_string()));
      }
      AstNode::ContextType(items) => {
        output.push_str(&format!("{}ContextType\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::ContextTypeEntry(left, right) => {
        output.push_str(&format!("{}ContextTypeEntry\n", i0));
        left.trace_node(output, level + 1);
        output.push_str(&format!("{}Type {}`{:?}`\n", i2, i3, right));
      }
      AstNode::Div(lhs, rhs) => {
        output.push_str(&format!("{}Div\n", i0));
        lhs.trace_node(output, level + 1);
        rhs.trace_node(output, level + 1);
      }
      AstNode::Eq(left, right) => {
        output.push_str(&format!("{}Eq\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Exp(left, right) => {
        output.push_str(&format!("{}Exp\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::FilterExpression(left, right) => {
        output.push_str(&format!("{}Filter\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::FormalParameter(parameter_name, parameter_type) => {
        output.push_str(&format!("{}FormalParameter\n", i0));
        output.push_str(&format!("{}`{}`: {}\n", i1, parameter_name.to_string(), parameter_type.stringify()));
      }
      AstNode::FormalParameters(items) => {
        if items.is_empty() {
          output.push_str(&format!("{}FormalParameters\n{}(no parameters)\n", i0, i1));
        } else {
          output.push_str(&format!("{}FormalParameters\n", i0));
          for item in items {
            item.trace_node(output, level + 1);
          }
        }
      }
      AstNode::FunctionBody(left, external) => {
        output.push_str(&format!("{}FunctionBody (external={})\n", i0, external));
        left.trace_node(output, level + 1);
      }
      AstNode::FunctionDefinition(lhs, rhs) => {
        output.push_str(&format!("{}FunctionDefinition\n", i0));
        lhs.trace_node(output, level + 1);
        rhs.trace_node(output, level + 1);
      }
      AstNode::FunctionType(lhs, feel_type) => {
        output.push_str(&format!("{}FunctionType\n", i0));
        lhs.trace_node(output, level + 1);
        output.push_str(&format!("{}ResultType\n{}{:?}\n", i1, i2, feel_type));
      }
      AstNode::Gt(left, right) => {
        output.push_str(&format!("{}Gt\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Ge(left, right) => {
        output.push_str(&format!("{}Ge\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::In(left, right) => {
        output.push_str(&format!("{}In\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::IntervalEnd(left, closed) => {
        output.push_str(&format!("{}IntervalEnd\n{}closed={}\n", i0, i1, closed));
        left.trace_node(output, level + 1);
      }
      AstNode::IntervalStart(left, closed) => {
        output.push_str(&format!("{}IntervalStart\n{}closed={}\n", i0, i1, closed));
        left.trace_node(output, level + 1);
      }
      AstNode::Irrelevant => {
        output.push_str(&format!("{}Irrelevant\n", i0));
      }
      AstNode::Lt(left, right) => {
        output.push_str(&format!("{}Lt\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Le(left, right) => {
        output.push_str(&format!("{}Le\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::List(items) => {
        if items.is_empty() {
          output.push_str(&format!("{}List\n{}[]\n", i0, i1));
        } else {
          output.push_str(&format!("{}List\n", i0));
          for item in items {
            item.trace_node(output, level + 1);
          }
        }
      }
      AstNode::ListType(inner) => {
        output.push_str(&format!("{}ListType\n{}{:?}\n", i0, i1, inner));
      }
      AstNode::Mul(left, right) => {
        output.push_str(&format!("{}Mul\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Name(name) => {
        output.push_str(&format!("{}Name\n{}`{}`\n", i0, i1, name.to_string()));
      }
      AstNode::Neg(right) => {
        output.push_str(&format!("{}Neg\n", i0));
        right.trace_node(output, level + 1);
      }
      AstNode::NegatedList(items) => {
        output.push_str(&format!("{}NegatedList\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::Nq(lhs, rhs) => {
        output.push_str(&format!("{}Nq", i0));
        lhs.trace_node(output, level + 1);
        rhs.trace_node(output, level + 1);
      }
      AstNode::Null => {
        output.push_str(&format!("{}Null\n", i0));
      }
      AstNode::Numeric(before, after) => {
        output.push_str(&format!("{}Numeric {}.{}\n", i0, before, after));
      }
      AstNode::Or(left, right) => {
        output.push_str(&format!("{}Or\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::ParameterName(name) => {
        output.push_str(&format!("{}ParameterName\n{}`{}`\n", i0, i1, name.to_string()));
      }
      AstNode::PositionalParameters(items) => {
        output.push_str(&format!("{}PositionalParameters\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::String(value) => {
        output.push_str(&format!("{}String `{}`\n", i0, value));
      }
      AstNode::Sub(left, right) => {
        output.push_str(&format!("{}Sub\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::ParameterTypes(items) => {
        if items.is_empty() {
          output.push_str(&format!("{}ParameterTypes\n{}[]\n", i0, i1));
        } else {
          output.push_str(&format!("{}ParameterTypes\n", i0));
          for item in items {
            output.push_str(&format!("{}{:?}\n", i1, item));
          }
        }
      }
      AstNode::QualifiedName(segments) => {
        let qn = segments.iter().map(|n| n.into()).collect::<Vec<String>>().join(".");
        output.push_str(&format!("{}QualifiedName  \n  {}'{}'\n", i0, i0, qn));
      }
      AstNode::RangeType(inner) => {
        output.push_str(&format!("{}RangeType\n{}{:?}\n", i0, i1, inner));
      }
      AstNode::ExpressionList(items) => {
        output.push_str(&format!("{}ExpressionList\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::UnaryLt(right) => {
        output.push_str(&format!("{}UnaryLt\n", i0));
        right.trace_node(output, level + 1);
      }
      AstNode::UnaryLe(right) => {
        output.push_str(&format!("{}UnaryLe\n", i0));
        right.trace_node(output, level + 1);
      }
      AstNode::UnaryGt(right) => {
        output.push_str(&format!("{}UnaryGt\n", i0));
        right.trace_node(output, level + 1);
      }
      AstNode::UnaryGe(right) => {
        output.push_str(&format!("{}UnaryGe\n", i0));
        right.trace_node(output, level + 1);
      }
      AstNode::Range(left, right) => {
        output.push_str(&format!("{}Range\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::InstanceOf(left, right) => {
        output.push_str(&format!("{}InstanceOf\n", i0));
        left.trace_node(output, level + 1);
        output.push_str(&format!("{}{:?}\n", i1, right));
      }
      AstNode::FunctionInvocation(left, right) => {
        output.push_str(&format!("{}FunctionInvocation\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::NamedParameters(items) => {
        output.push_str(&format!("{}NamedParameters\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::NamedParameter(left, right) => {
        output.push_str(&format!("{}NamedParameter\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::ForExpression(left, right) => {
        output.push_str(&format!("{}For\n", i0));
        output.push_str(&format!("{}IterationClauses\n", i1));
        for (variable_name, node, opt_node) in left {
          output.push_str(&format!("{}IterationClause\n", i2));
          output.push_str(&format!("{}Variable\n{}`{}`\n", i3, i4, variable_name.to_string()));
          output.push_str(&format!("{}IterationContext\n", i3));
          node.trace_node(output, level + 4);
          if let Some(range_end) = opt_node {
            range_end.trace_node(output, level + 4);
          }
        }
        output.push_str(&format!("{}EvaluatedExpression\n", i1));
        right.trace_node(output, level + 2);
      }
      AstNode::If(condition, when_true, when_false) => {
        output.push_str(&format!("{}If\n", i0));
        condition.trace_node(output, level + 1);
        when_true.trace_node(output, level + 1);
        when_false.trace_node(output, level + 1);
      }
      AstNode::IterationClauses(items) => {
        output.push_str(&format!("{}IterationClauses\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::IterationContextSingle(left) => {
        output.push_str(&format!("{}IterationContext (single)\n", i0));
        left.trace_node(output, level + 1);
      }
      AstNode::IterationContextRange(left, right) => {
        output.push_str(&format!("{}IterationContext (range)\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Out(left, right) => {
        output.push_str(&format!("{}Out\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::Path(lhs, rhs) => {
        output.push_str(&format!("{}Path\n", i0));
        lhs.trace_node(output, level + 1);
        rhs.trace_node(output, level + 1);
      }
      AstNode::QuantifiedClauses(items) => {
        output.push_str(&format!("{}QuantifiedClauses\n", i0));
        for item in items {
          item.trace_node(output, level + 1);
        }
      }
      AstNode::QuantifiedExpressionEvery(left, right) => {
        output.push_str(&format!("{}QuantifiedExpressionEvery\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
      AstNode::QuantifiedExpressionSome(left, right) => {
        output.push_str(&format!("{}QuantifiedExpressionSome\n", i0));
        left.trace_node(output, level + 1);
        right.trace_node(output, level + 1);
      }
    }
  }
}