AST_generic.ml

(* Yoann Padioleau
 *
 * Copyright (C) 2019-2022 r2c
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation, with the
 * special exception on linking described in file license.txt.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the file
 * license.txt for more details.
 *)

(*****************************************************************************)
(* Prelude *)
(*****************************************************************************)
(* A generic AST, to factorize similar "analysis" in different programming
 * languages (e.g., naming, semantic code highlighting, semgrep!).
 *
 * Right now this generic AST is mostly the factorized union of:
 *  - Python, Ruby, Lua
 *  - Javascript, Typescript
 *  - PHP, Hack
 *  - Java, CSharp, Kotlin
 *  - C, C++
 *  - Go
 *  - JSON, YAML, HCL
 *  - OCaml, Scala, Rust
 *  - TODO Bash, SQL, Docker
 *
 * rational: In the end, programming languages have a lot in Common.
 * Even though some interesting analysis are probably better done on a
 * per-language basis, many analysis are simple and require just an
 * AST and a visitor. One could duplicate those analysis for each language
 * or design an AST (this file) generic enough to factorize all those
 * analysis (e.g., unused entity). Note that we want to remain
 * as precise as possible and not lose too much information while going
 * from the specific language AST to the generic AST. We don't want
 * to be too generic as in ast_fuzzy.ml, where we have a very general
 * tree of nodes, but all the structure of the original AST is lost.
 *
 * The generic AST tries to be as close as possible to the original code but
 * not too close. When a programming language feature is really sugar or
 * an alternative way to do a thing, we usually unsugar. Here are the
 * simplifications done:
 *  - we do not keep the comma tokens in arguments. More generally we
 *    just keep the tokens to get the range right (see the discussions on
 *    invariants below) and get rid of the other (e.g., we remove
 *    parens around conditions in if). We keep the parens for 'Call'
 *    because we want to get the right range for those so we need the
 *    rightmost tokens in the AST.
 *  - multiple var declarations in one declaration (e.g., int a,b; in C)
 *    are expanded in multiple 'variable_definition'. Note that
 *    tuple assignments (e.g., a,b=1,2) are not expanded in multiple assigns
 *    because this is not always possible (e.g., a,b=foo()) and people may
 *    want to explicitely match tuples assignments (we do some magic in
 *    Generic_vs_generic though to let 'a=1' matches also 'a,b=1,2').
 *  - multiple ways to define a function are converted all to a
 *    'function_definition' (e.g., Javascript arrows are converted in that)
 *    update: but we now have a more precise function_body type
 *  - we are more general and impose less restrictions on where certain
 *    constructs can appear to simplify things.
 *     * there is no special lhs/lvalue type (see IL.ml for that) and so
 *      'Assign' takes a general 'expr' on its lhs.
 *     * there is no special toplevel/item vs stmt. Certain programming
 *       languages impose restrictions on where a function or directive can
 *       appear (e.g., just at the toplevel), but we allow those constructs
 *       at the stmt level.
 *     * the Splat and HashSplat operator can usually appear just in arguments
 *       or inside arrays or in struct definitions (a field) but we are more
 *       general and put it at the 'expr' level.
 *     * certain attributes are valid only for certain constructs but instead
 *       we use one attribute type (no class_attribute vs func_attribute etc.)
 *
 * Note that this generic AST has become gradually more and more a
 * generic CST, to fix issues in autofix in Semgrep.
 * TODO? it may be time to rename this file CST_generic.ml
 *
 * todo:
 *  - improve things for Kotlin/Scala/Rust/C++/Java
 *  - see ast_fuzzy.ml todos for ideas to use AST_generic for sgrep?
 *
 * related work:
 *  - ast_fuzzy.ml (in pfff)
 *  - github semantic (seems dead)
 *    https://github.com/github/semantic
 *  - UAST of babelfish
 *    https://doc.bblf.sh/uast/uast-specification-v2.html
 *  - Coverity common program representation?
 *  - Semmle internal common representation?
 *  - Sonarcube generic language
 *    https://github.com/SonarSource/slang
 *  - Facebook Infer SIL (for C++, Java, Objective-C)
 *  - Dawson Engler and Fraser Brown micro-checkers for multiple languages
 *  - Comby common representation by Rijnard,
 *    see "Lightweight Multi-language syntax transformation", but does not
 *    really operate on an AST
 *  - https://tabnine.com/ which supports multiple languages, but probably
 *    again does not operate on an AST
 *  - srcML https://www.srcml.org/doc/srcMLGrammar.html
 *    but just for C/C++/C#/Java and seems pretty heavy
 *
 * design choices to have a generic data structure:
 *  - add some 'a, 'b, 'c around expr/stmt/...
 *  - data-type a la carte like in github-semantic but IMHO too high-level
 *    with astronaut-style architecture (too abstract, too advanced features).
 *  - CURRENT SOLUTION: the OtherXxx strategy used in this file (simple)
 *    update: actually switch to OtherXxx of todo_kind, even simpler
 *  - functorize and add some type hole (type tstmt; type texpr; ...),
 *    todo? not a bad idea if later we want to add type information on each
 *    expression nodes
 *
 * history:
 *  - started with crossproduct of Javascript, Python, PHP, Java, and C
 *    (and a bit of OCaml) after wanting to port checked_return from Js to
 *    Python and got the idea to factorize things
 *
 * INVARIANTS:
 *  - all the other_xxx types should contain only simple constructors (enums)
 *    without any parameter. I rely on that to simplify the code
 *    of the generic mapper and matcher.
 *    update: prefer todo_kind to those other_xxx types now.
 *    Same for keyword_attributes.
 *  - each expression or statement must have at least one token in it
 *    so that semgrep can track a location (e.g., 'Return of expr option'
 *    is not enough because with no expr, there is no location information
 *    for this return, so it must be 'Return of tok * expr option' instead)
 *  - each expression or statement should ideally have enough tokens in it
 *    to get its range, so at least the leftmost and rightmost token in
 *    all constructs, so the Return above should even be
 *    'Return of tok * expr option * tok' for the ending semicolon
 *    (alt: have the range info in each expr/stmt/pattern but big refactoring)
 *  - to correctly compute a CFG (Control Flow Graph), the stmt type
 *    should list all constructs that contains other statements and
 *    try to avoid to use the very generic 'OtherXxx of any'
 *  - to correctly compute a DFG (Data Flow Graph), and to correctly resolve
 *    names (see Naming_AST.ml), each constructs that introduce a new
 *    variable should have a relevant comment 'newvar:'
 *  - to correctly resolve names, each construct that introduces a new scope
 *    should have a relevant comment 'newscope:'
 *  - todo? each language should add the VarDefs that defines the locals
 *    used in a function (instead of having the first Assign play the role
 *    of a VarDef, as done in Python for example).
 *)

(* Provide hash_* and hash_fold_* for the core ocaml types *)
open Ppx_hash_lib.Std.Hash.Builtin

(* ppx_hash refuses to hash mutable fields but we do it anyway. *)
let hash_fold_ref hash_fold_x acc x = hash_fold_x acc !x

(*****************************************************************************)
(* Token (leaf) *)
(*****************************************************************************)
(* Contains among other things the position of the token through
 * the Parse_info.token_location embedded inside it, as well as the
 * transformation field that makes possible spatch on the code.
 *)
type tok = Parse_info.t [@@deriving show]

(* sgrep: we do not care about position when comparing for equality 2 ASTs.
 * related: Lib_AST.abstract_position_info_any and then use OCaml generic '='.
 *)
let equal_tok _t1 _t2 = true

let hash_tok _t = 0

let hash_fold_tok acc _t = acc

(* a shortcut to annotate some information with position information *)
type 'a wrap = 'a * tok [@@deriving show, eq, hash]

(* Use for round(), square[], curly{}, and angle<> brackets.
 * note: in theory we should not care about those tokens in an AST,
 * but they are useful to report correct ranges in sgrep when we match
 * something that can just be those brackets (e.g., an empty container).
 *)
type 'a bracket = tok * 'a * tok [@@deriving show, eq, hash]

(* semicolon, a FakeTok in languages that do not require them (e.g., Python).
 * alt: tok option.
 * See the sc value also at the end of this file to build an sc.
 *)
type sc = tok [@@deriving show, eq, hash]

(* an AST element not yet handled.
 * history: I started by having some precise OtherXxx of other_xxx
 * constructors and types to record what was not handled
 * (e.g., OE_Delete, OE_Define, etc.), but it was quickly getting tedious
 * each time to add new constructs. In fact, in the language-specific
 * ASTs I started to use also some Todo constructs, so I switched to a
 * more general todo_kind in the generic AST too. Anyway, we were
 * not doing anything with the precise information. If something
 * is important and require some semantic equivalence in semgrep, then
 * we should support the construct directly, not via an other_xxx.
 *)
type todo_kind = string wrap [@@deriving show, eq, hash]

(*****************************************************************************)
(* Names *)
(*****************************************************************************)

type ident = string wrap [@@deriving show, eq, hash]

(* Usually separated by a '.', but can be used also with '::' separators.
 * less: we often need to get the last elt or adjust the qualifier part,
 * so maybe we should define it as = ident list * ident
 *)
type dotted_ident = ident list (* at least 1 element *)
[@@deriving show, eq, hash]

(* module_name can also be used for a package name or a namespace.
 * TODO? prefix with M and add MQualifiedName for C++?
 * less: can even be dynamic in C with #include of expr
 *)
type module_name =
  | DottedName of dotted_ident (* ex: Python *)
  (* in FileName the '/' is similar to the '.' in DottedName *)
  | FileName of string wrap (* ex: Js import, C #include, Go import *)
[@@deriving show { with_path = false }, eq, hash]

(* A single unique id: sid (uid would be a better name, but it usually
 * means "user id" for people).
 *
 * This single id simplifies further analysis which need less to care about
 * maintaining scoping information, for example to deal with variable
 * shadowing, or functions using the same parameter names
 * (even though you still need to handle specially recursive functions), etc.
 *
 * See Naming_AST.ml for more information.
 *
 * Most generic ASTs have a fake value (sid_TODO = -1) at first.
 * You need to call Naming_AST.resolve (or one of the lang-specific
 * Resolve_xxx.resolve) on the generic AST to set it correctly.
 *)
(* a single unique gensym'ed number. See gensym() below *)
type sid = int

and resolved_name = resolved_name_kind * sid

and resolved_name_kind =
  (* Global is useful in codemap/efuns to highlight differently and warn
   * about the use of globals inside functions.
   * old: Global was merged with ImportedEntity before but simpler to split, as
   * anyway I was putting often an empty list for dotted_ident with a
   * todo note in the code.
   *)
  | Global
  (* Those could be merged, but again this is useful in codemap/efuns *)
  | Local
  | Param
  (* For closures; can refer to a Local or Param.
   * With sid this is potentially less useful for scoping-related issues,
   * but this can be useful in codemap to again highlight specially
   * enclosed vars.
   * todo: this is currently used also for fields, but we should use another
   * constructor.
   * Note that it's tempting to add a depth parameter to EnclosedVar, but
   * that would prevent semgrep to work because whatever the depth you are,
   * if you reference the same entity, this entity must have the same
   * resolved_name (sid and resolved_name_kind).
   *)
  | EnclosedVar (* less: add depth? *)
  (* sgrep: those cases allow to match entities/modules even if they were
   * aliased when imported.
   * both dotted_ident must at least contain one element *)
  | ImportedEntity of dotted_ident (* can also use 0 for gensym *)
  | ImportedModule of module_name
  (* used in Go, where you can pass types as arguments and where we
   * need to resolve those cases
   *)
  | TypeName
  (* used for C *)
  | Macro
  | EnumConstant
[@@deriving show { with_path = false }, eq, hash]

(* Start of big mutually recursive types because of the use of 'any'
 * in OtherXxx *)

(* old: Id below used to be called Name and was generalizing also IdQualified
 * but some analysis are easier when they just need to
 * handle a simple Id, hence the split. For example, there was some bugs
 * in sgrep because sometimes an identifier was an ident (in function header)
 * and sometimes a name (when called). For naming, we also need to do
 * things differently for Id vs IdQualified and would need many times to
 * inspect the name.name_qualifier to know if we have an Id or IdQualified.
 * We do the same split for Fid vs FName for fields.
 *
 * newvar: Id is sometimes abused to also introduce a newvar (as in Python)
 * but ultimately those cases should be rewritten to first introduce
 * a VarDef.
 *
 * DEBT? Sometimes some DotAccess should really be transformed in IdQualified
 * with a better qualifier because the obj is actually the name of a package
 * or module, but you may need advanced semantic information and global
 * analysis to disambiguate. In the meantime, you can use
 * AST_generic_helpers.name_of_dot_access to convert a DotAccess of idents
 * into an IdQualified name.
 *)
type name = Id of ident * id_info | IdQualified of qualified_info

(* A qualified (via type arguments or module/namespace/package) id.
 * The type should be enough to represent Java/Rust/C++ generics.
 * less: it is still not enough to represent OCaml functors applications.
 *
 * invariant: you can't have name_top = None, name_middle = QNone, and
 * name_last = (id * None) at the same time. If that's the case, then we
 * build an Id, not an Idqualified
 *)
and qualified_info = {
  name_last : ident * type_arguments option;
  name_middle : qualifier option;
  (* ::, Ruby, C++, also '`' abuse for PolyVariant in OCaml *)
  name_top : tok option;
  name_info : id_info;
}

and qualifier =
  (* Java/C++/Rust *)
  | QDots of (ident * type_arguments option) list
  (* Ruby/Lua *)
  | QExpr of expr * tok

(*****************************************************************************)
(* Naming/typing *)
(*****************************************************************************)
and id_info = {
  id_resolved : resolved_name option ref;
  (* variable tagger (naming) *)
  (* sgrep: in OCaml we also use that to store the type of
   * a typed entity, which can be interpreted as a TypedMetavar in semgrep.
   * alt: have an explicity type_ field in entity.
   *)
  id_type : type_ option ref;
  (* type checker (typing) *)
  (* sgrep: this is for sgrep constant propagation hack.
   * todo? associate only with Id?
   * note that we do not use the constness for equality (hence the adhoc
   * @equal below) because the constness analysis is now controlflow-sensitive
   * meaning the same variable might have different id_constness value
   * depending where it is used.
   *)
  id_constness : constness option ref; [@equal fun _a _b -> true]
  (* THINK: Drop option? *)
  (* id_hidden=true must be set for any artificial identifier that never
     appears in source code but is introduced in the AST after parsing.

     Don't use this for syntax desugaring or transpilation because the
     resulting function name might exist in some source code. Consider the
     following normalization:

       !foo -> foo.contents
                   ^^^^^^^^
                 should not be marked as hidden because it could appear
                 in target source code.

     However, an artificial identifier like "!sh_quoted_expand!" should
     be marked as hidden in bash.

     This allows not breaking the -fast/-filter_irrelevant_rules optimization
     that skips a target file if some identifier in the pattern AST doesn't
     exist in the source of the target.
  *)
  id_hidden : bool;
}

(*****************************************************************************)
(* Expression *)
(*****************************************************************************)

(* todo? we could store more semantic information at each expr node,
 * e.g., type information, constant evaluation.
 *)
and expr = {
  e : expr_kind;
  e_id : int;
  (* used to quickly get the range of an expression *)
  mutable e_range :
    (Parse_info.token_location * Parse_info.token_location) option;
      [@equal fun _a _b -> true] [@hash.ignore]
}

and expr_kind =
  (* basic (atomic) values *)
  | L of literal
  (* composite values
   * TODO? element list bracket, so can encode KeyVal, Designator,
   * IndexArray for C++.
   * ArrayInitDesignator [x] = ... use ArrayAccess in container?
   *)
  | Container of container_operator * expr list bracket
  | Comprehension of container_operator * comprehension bracket
  (* And-type (field.vinit should be a Some) *)
  | Record of field list bracket
  (* Or-type (could be used instead of Container, Cons, Nil, etc.).
   * (ab)used also for polymorphic variants where qualifier is QTop with
   * the '`' token.
   *
   * Note that in OCaml constructors do not always need brackets.
   * For example, you can have 'let x = Foo 1'. However, you often
   * need the parenthesis, for example when you have multiple arguments
   * (e.g., 'let x = Foo (1,2)').
   * In that case, we could make '(1,2)' a single Tuple argument, and
   * that is mostly what is done in ast_ml.ml, but this is a bit ugly.
   * Morever, even with a single argument, you need extra parenthesis
   * if the argument is a complex expression (e.g., 'let x = Foo(1+2)').
   * And if those parenthesis are not in the AST, then matching range
   * or autofix on such construct may fail.
   * Finally, in some languages like Scala or Rust, constructors require
   * the parenthesis.
   * Thus, it is simpler to add the bracket here, because this is mostly
   * how user think.
   *)
  | Constructor of name * expr list bracket
  (* see also Call(IdSpecial (New,_), [ArgType _;...] for other values *)
  | N of name
  | IdSpecial of special wrap (*e: [[AST_generic.expr]] other identifier cases *)
  (* operators and function application *)
  | Call of expr * arguments
  (* TODO? Separate regular Calls from OpCalls where no need bracket and Arg *)
  (* (XHP, JSX, TSX), could be transpiled also (done in IL.ml?) *)
  | Xml of xml
  (* IntepolatedString of expr list is simulated with a
   * Call(IdSpecial (Concat ...)) *)

  (* The left part should be an lvalue (Id, DotAccess, ArrayAccess, Deref)
   * but it can also be a pattern (Container, even Record), but
   * you should really use LetPattern for that.
   * Assign can also be abused to declare new variables, but you should use
   * variable_definition for that.
   * less: should be in stmt, but most languages allow this at expr level :(
   * todo: see IL.ml where we normalize this AST with expr/instr/stmt
   * update: should even be in a separate simple_stmt, as in Go
   *)
  | Assign of
      expr * tok (* '=', '<-' in OCaml. ':=' Go is AssignOp (Eq) *) * expr
  (* less: could desugar in Assign, should be only binary_operator *)
  | AssignOp of expr * operator wrap * expr
  (* newvar:! newscope:? in OCaml yes but we miss the 'in' part here  *)
  | LetPattern of pattern * expr (*e: [[AST_generic.expr]] other assign cases *)
  (* can be used for Record, Class, or Module access depending on expr.
   * In the last case it should be rewritten as a (N IdQualified) with a
   * qualifier though.
   * TODO? have a dot_operator to differentiate ., .?, and :: in Kotlin?
   *)
  | DotAccess of expr * tok (* ., ::, ->, # *) * field_name
  (* in Js ArrayAccess is also abused to perform DotAccess (..., FDynamic) *)
  | ArrayAccess of expr * expr bracket
  (* could also use ArrayAccess with a Tuple rhs, or use a special *)
  | SliceAccess of
      expr
      * (expr option (* lower *) * expr option (* upper *) * expr option)
        (* step *)
        bracket
  (* very special value. 'fbody' is usually an FExpr. *)
  | Lambda of function_definition
  (* also a special value. Usually an argument of a New
   * (used in Java, Javascript, etc.) *)
  | AnonClass of class_definition
  (* a.k.a ternary expression. Note that even in languages like OCaml
   * where 'if's are expressions, we still prefer to use the stmt 'If'
   * because it allows an optional else part. We need to sometimes
   * wrap those stmts inside an OE_StmtExpr though.
   * TODO: add toks? TODO? in C++ the second expr can be an option
   *)
  | Conditional of expr * expr * expr
  | Yield of tok * expr option * bool (* 'from' for Python *)
  | Await of tok * expr
  (* Send/Recv of Go are currently in OtherExpr *)
  | Cast of type_ * tok (* ':' or leftmost '(' or 'as' *) * expr
  (* less: should be in statement *)
  | Seq of expr list (* at least 2 elements *)
  (* less: could be in Special, but pretty important so I've lifted them here*)
  | Ref of tok (* &, address of *) * expr
  | DeRef of tok (* '*' in C, '!' or '<-' in OCaml, ^ in Reason *) * expr
  (* In some rare cases, we need to keep the parenthesis around an expression
   * otherwise in autofix semgrep could produce incorrect code. For example,
   * in Go a cast int(3.0) requires the parenthesis.
   * alt: change cast to take a expr bracket, but this is used only for Go.
   * Note that this data structure is really becoming more a CST than an AST.
   *)
  | ParenExpr of expr bracket
  (* sgrep: ... in expressions, args, stmts, items, and fields
   * (and unfortunately also in types in Python) *)
  | Ellipsis of tok (* '...' *)
  | DeepEllipsis of expr bracket (* <... ...> *)
  | DisjExpr of expr * expr
  | TypedMetavar of ident * tok (* : *) * type_
  (* for ellipsis in method chaining *)
  | DotAccessEllipsis of expr * tok (* '...' *)
  (* Dual of ExprStmt. See stmt_to_expr() below and its comment.
   * OCaml/Ruby/Scala/... have just expressions, not separate statements.
   *)
  | StmtExpr of stmt
  (* e.g., TypeId in C++, MethodRef/ClassLiteral in Java, Send/Receive in Go,
   * Checked/Unchecked in C#, Repr in Python, RecordWith in OCaml/C#,
   * Subshell in Ruby, Delete/Unset in JS/Hack/Solidity/C++,
   * Unpack/ArrayAppend in PHP (the AST for $x[] = 1 used to be
   * handled as an AssignOp with special Append).
   * Define/Arguments/NewTarget/YieldStar/Exports/Module/Require/UseStrict JS,
   * UnitLiteral/HexString/UnicodeString/TupleHole/StructExpr in Solidity
   * TODO? lift up to program attribute/directive UseStrict, Require in Import?
   * TODO? of replace 'any list' by 'expr list'? any way there's still
   * StmtExpr above to wrap stmt if it's not an expr but a stmt
   *)
  | OtherExpr of todo_kind * any list

and literal =
  | Bool of bool wrap
  (* the numbers are an option because OCaml numbers
   * may not be able to represent all numbers. For example, OCaml integers
   * are limited to 63 bits, but C integers can use 64 bits.
   *)
  | Int of int option wrap
  | Float of float option wrap
  | Char of string wrap
  | String of string wrap (* TODO? bracket, ', ", or even """ *)
  | Regexp of string wrap bracket (* // *) * string wrap option (* modifiers *)
  | Atom of tok (* ':' in Ruby, ''' in Scala *) * string wrap
  | Unit of tok
  (* a.k.a Void *)
  | Null of tok
  | Undefined of tok (* JS *)
  | Imag of string wrap
  (* Go, Python *)
  | Ratio of string wrap

(* The type of an unknown constant. *)
and const_type = Cbool | Cint | Cstr | Cany

(* set by the constant propagation algorithm and used in semgrep *)
and constness = Lit of literal | Cst of const_type | NotCst

and container_operator =
  | Array (* todo? designator? use ArrayAccess for designator? *)
  | List
  | Set
  (* a.k.a Hash or Map (combine with Tuple to get Key/value pair) *)
  (* TODO? merge with Record *)
  | Dict
  (* Tuples usually contain at least 2 elements, except for Python where
   * you can actually have 1-uple, e.g., '(1,)'.
   *)
  | Tuple

(* For Python/HCL (and Haskell later). The 'expr' can be a 'Tuple' to
 * represent a Key/Value pair (like in Container). See keyval() below.
 * newscope: for_or_if_comp introduce new local variables whose scope
 *  is just the first expr.
 *)
and comprehension = expr * for_or_if_comp list

(* at least one element *)
and for_or_if_comp =
  (* newvar: *)
  | CompFor of tok (*'for'*) * pattern * tok (* 'in' *) * expr
  | CompIf of tok (*'if'*) * expr

and field_name =
  (* In the case of a field, it may be hard to resolve the id_info inside name.
   * For example, a method id can refer to many method definitions.
   * But for certain things, like a private field, we can resolve it
   * (right now we use an EnclosedVar for those fields).
   *
   * The IdQualified inside name is Useful for OCaml field access.
   *)
  | FN of name
  (* for PHP/JS fields (even though JS use ArrayAccess for that), or Ruby
   * or C++ ArrowStarAccess ->*
   *)
  | FDynamic of expr

(* It's useful to keep track in the AST of all those special identifiers.
 * They need to be handled in a special way by certain analysis and just
 * using Name for them would be error-prone.
 * Note though that by putting all of them together in a type, we lose
 * typing information. For example, Eval takes only one argument and
 * InstanceOf takes a type and an expr. This is a tradeoff to also not
 * polluate too much expr with too many constructs.
 * TODO: split in IdSpecial of special_id and CallSpecial of special_op
 * and then also just CallOp. And also a separate InterpolatedString.
 *)
and special =
  (* special vars *)
  | This
  | Super (* called 'base' in C# *)
  (* less: how different self/parent is from this/super? *)
  | Self
  | Parent
  (* for Lua, todo: just remove it, create Dict without key *)
  | NextArrayIndex
  (* special calls *)
  | Eval
  | Typeof (* for C? and Go in switch x.(type) *)
  (* todo? make a SpecialType, also use for ClassLiteral *)
  | Instanceof
  | Sizeof (* takes a ArgType *)
  | Defined (* defined? in Ruby, other? *)
  (* Note that certain languages do not have a 'new' keyword
   * (e.g., Python, Scala 3), instead certain 'Call' are really 'New'.
   * Note that 'new' by itself is not a valid expression
   *)
  | New (* usually associated with Call(New, [ArgType _;...]) *)
  (* used for interpolated strings constructs
   * TODO: move out of 'special' and make special construct InterpolatedConcat
   * in 'expr' instead of abusing Call for that? that way can also
   * avoid those InterpolatedElement stuff.
   *)
  | ConcatString of concat_string_kind
  | EncodedString of string (* only for Python for now (e.g., b"foo") *)
  (* TaggedString? for Javascript, for styled.div`bla{xx}`?
   * We could have this TaggedString where the first arg of Call
   * will be the tagging function, and the rest will be a Call ConcatString.
   * However, it is simpler to just transform those special calls as
   * regular calls even though they do not have parenthesis
   * (not all calls have parenthesis anyway, as in OCaml or Ruby).
   *)
  (* Use this to separate interpolated elements in interpolated strings
   * but this is a bit of a hack.
   * TODO: We should probably add InterpolatedConcat as an expression
   *)
  | InterpolatedElement
  (* "Inline" the content of a var containing a list (a.k.a Splat in Ruby).
   * Used in a Container or Call argument context.
   * The corresponding constructor in a parameter context is ParamRest.
   *)
  | Spread (* ...x in JS, *x in Python/Ruby *)
  (* Similar to Spread, but for a var containing a hashtbl.
   * The corresponding constructor in a parameter context is ParamHashSplat.
   *)
  | HashSplat (* **x in Python/Ruby
               * (not to confused with Pow below which is a Binary op *)
  | ForOf (* Javascript, for generators, used in ForEach *)
  (* used for unary and binary operations
   * TODO: move out of special too, in separate OpCall? (where can also
   * have 1 or 2 argument (or maybe even 0 for op reference?)
   *)
  | Op of operator
  (* less: should be lift up and transformed in Assign at stmt level *)
  | IncrDecr of (incr_decr * prefix_postfix)

(* mostly binary operators.
 * less: could be divided in really Arith vs Logical (bool) operators,
 * but see is_boolean_operator() helper below.
 * Note that Mod can be used for %style string formatting in Python.
 * Note that Plus can also be used for string concatenations in Go/??.
 * todo? use a Special operator intead for that? but need type info?
 *)
and operator =
  (* unary too *)
  | Plus
  (* unary too *)
  | Minus
  | Mult
  | Div
  | Mod
  | Pow (* ** binary op; for unary see HashSplat above *)
  | FloorDiv
  | MatMult (* Python *)
  | LSL
  | LSR
  | ASR (* L = logic, A = Arithmetic, SL = shift left *)
  | BitOr
  | BitXor
  | BitAnd
  (* unary too *)
  | BitNot
  | BitClear (* Go *)
  (* And/Or are also shortcut operator.
   * todo? rewrite in CondExpr? They have a special behavior.
   *)
  | And
  | Or
  (* PHP has a xor shortcut operator ... hmmm *)
  | Xor
  (* unary *)
  | Not
  | Eq (* '=' in OCaml, '==' in Go/... *)
  | NotEq (* less: could be desugared to Not Eq *)
  | PhysEq (* '==' in OCaml, '===' in JS/... *)
  | NotPhysEq (* less: could be desugared to Not PhysEq *)
  | Lt
  | LtE
  | Gt
  | GtE (* less: could be desugared to Or (Eq Lt) *)
  | Cmp (* <=>, PHP *)
  | Concat (* '.' PHP, '..' Lua *)
  | Append (* x[] = ... in PHP, just in AssignOp *)
  | RegexpMatch (* =~, Ruby (and Perl) *)
  | NotMatch (* !~ Ruby less: could be desugared to Not RegexpMatch *)
  | Range (* .. or ..., Ruby, one arg can be nil for endless range *)
  | RangeInclusive (* '..=' in Rust *)
  | NotNullPostfix (* ! in Typescript, postfix operator *)
  | Length (* '#' in Lua *)
  (* See https://en.wikipedia.org/wiki/Elvis_operator.
   * In PHP we currently generate a Conditional instead of a Binary Elvis.
   * It looks like the Nullish operator is quite similar to the Elvis
   * operator, so we may want to merge those operators at some point.
   *)
  | Elvis (* ?: in Kotlin, can compare possible null value *)
  | Nullish (* ?? in Javascript *)
  | In (* in: checks that value belongs to a collection *)
  | NotIn (* !in *)
  (* Is (and NotIs) checks whether a value has a certain type.
   * The second argument in OpCall is always an ArgType!
   * Can also be used as an unary operation in Kotlin in a 'when'
   *)
  | Is
  | NotIs
  (* Shell & and | *)
  | Background
  | Pipe

(* '++', '--' *)
and incr_decr = Incr | Decr

and prefix_postfix = Prefix | Postfix

and concat_string_kind =
  (* many languages do not require a special syntax to use interpolated
   * strings e.g. simply "this is {a}". Javascript uses backquotes.
   *)
  | InterpolatedConcat (* Javascript/PHP/Ruby/Perl *)
  (* many languages have a binary Concat operator to concatenate strings,
   * but some languages also allow the simple juxtaposition of multiple
   * strings to be concatenated, e.g. "hello" "world" in Python.
   *)
  | SequenceConcat (* Python/C *)
  (* Python requires the special f"" syntax to use interpolated strings,
   * and some semgrep users may want to explicitely match only f-strings,
   * which is why we record this information here.
   * update: also use for interpolated Scala strings
   * TODO: add of string ('f' or something else)
   *)
  | FString
  (* Javascript uses a special syntax called tagged template literals, e.g.,
   * foo`template string = ${id}`. We must use a different representation
   * for foo(`template string = ${id}`) because some semgrep users want
   * to find one and not the other.
   * In both case it will be inside Call (Apply (ConcatString  ... but then
   * the kind will differ.
   * example: foo`template ${id}`
   *)
  | TaggedTemplateLiteral

(* This is for JSX/TSX in javascript land (old: and XHP in PHP land).
 * less: we could make it more generic by adding a 'expr so it could be
 * reused in ast_js.ml, ast_php.ml
 *)
and xml = {
  xml_kind : xml_kind;
  xml_attrs : xml_attribute list;
  xml_body : xml_body list;
}

and xml_kind =
  | XmlClassic of tok (*'<'*) * ident * tok (*'>'*) * tok (*'</foo>'*)
  | XmlSingleton of tok (*'<'*) * ident * tok (* '/>', with xml_body = [] *)
  (* React/JS specific *)
  | XmlFragment of tok (* '<>' *) * (* '</>', with xml_attrs = [] *) tok

and xml_attribute =
  | XmlAttr of ident * tok (* = *) * a_xml_attr_value
  (* less: XmlAttrNoValue of ident. <foo a /> <=> <foo a=true /> *)
  (* jsx: usually a Spread operation, e.g., <foo {...bar} /> *)
  | XmlAttrExpr of expr bracket
  (* sgrep: *)
  | XmlEllipsis of tok

(* either a String or a bracketed expr, but right now we just use expr *)
and a_xml_attr_value = expr

and xml_body =
  (* sgrep-ext: can contain "..." *)
  | XmlText of string wrap
  (* this can be None when people abuse {} to put comments in it *)
  | XmlExpr of expr option bracket
  | XmlXml of xml

(* brackets can be fake '()' for OCaml/Ruby *)
and arguments = argument list bracket

and argument =
  (* regular argument *)
  | Arg of expr (* can be Call (IdSpecial Spread, Id foo) *)
  (* keyword argument *)
  | ArgKwd of ident * expr
  (* type argument for New, instanceof/sizeof/typeof, C macros *)
  | ArgType of type_
  (* e.g., ArgMacro for C/Rust, ArgQuestion for OCaml, ArgIds in Solidity *)
  | OtherArg of todo_kind * any list

(*****************************************************************************)
(* Statement *)
(*****************************************************************************)
and stmt = {
  s : stmt_kind;
      [@equal AST_utils.equal_stmt_field_s equal_stmt_kind] [@hash.ignore]
  (* this can be used to compare and hash more efficiently stmts,
   * or in semgrep to quickly know if a stmt is a children of another stmt.
   *)
  s_id : AST_utils.Node_ID.t; [@equal AST_utils.equal_stmt_field_s_id]
  (* todo? we could store a range: (tok * tok) to delimit the range of a stmt
   * which would allow us to remove some of the extra 'tok' in stmt_kind.
   * Indeed, the main use of those 'tok' is to accurately report a match range
   * in semgrep.
   *)
  mutable s_use_cache : bool; [@equal fun _a _b -> true] [@hash.ignore]
  (* whether this is a strategic point for match result caching.
     This field is relevant for patterns only.

     This applies to the caching optimization, in which the results of
     matching lists of statements can be cached. A list of statements
     is identified by its leading node. In the current implementation,
     the fields 's_id', 's_use_caching', and 's_backrefs' are treated as
     properties of a (non-empty) list of statements, rather than of individual
     statements. A cleaner implementation would consist of a custom
     list type in which each list has these properties, including the
     empty list.
  *)
  mutable s_backrefs : AST_utils.String_set.t option;
      [@equal fun _a _b -> true] [@hash.ignore]
  (* set of metavariables referenced in the "rest of the pattern", as
     determined by matching order.
     This field is relevant for patterns only.

     This is used to determine which of the bound
     metavariables should be added to the cache key for this node.
     This field is set on pattern ASTs only, in a pass right after parsing
     and before matching.
  *)
  (* used in semgrep to skip some AST matching *)
  mutable s_bf : Bloom_filter.t option;
      [@equal fun _a _b -> true] [@hash.ignore]
  (* used to quickly get the range of a statement *)
  mutable s_range :
    (Parse_info.token_location * Parse_info.token_location) option;
      [@equal fun _a _b -> true] [@hash.ignore]
}

and stmt_kind =
  (* See also IL.ml where Call/Assign/Seq are not in expr and where there are
   * separate expr, instr, and stmt types *)
  | ExprStmt of expr * sc (* fake tok in Python, but also in JS/Go with ASI *)
  (* newscope: in C++/Java/Go *)
  | Block of stmt list bracket (* can be fake {} in Python where use layout *)
  (* EmptyStmt = Block [], or separate so can not be matched by $S? $
   * see also emptystmt() at the end of this file.
   *)
  (* newscope: for vardef in condition in C++/Go/... *)
  | If of tok (* 'if' or 'elif' *) * condition * stmt * stmt option
  | While of tok * condition * stmt
  | Return of tok * expr option * sc
  | DoWhile of tok * stmt * expr
  (* newscope: *)
  | For of tok (* 'for', 'foreach'*) * for_header * stmt
  (* The expr can be None for Go and Ruby.
   * less: could be merged with ExprStmt (MatchPattern ...) *)
  | Switch of
      tok (* 'switch', also 'select' in Go, or 'case' in Bash *)
      * condition option
      * case_and_body list (* TODO brace *)
  (* todo: merge Match with Switch?
   * In Scala and C# the match is infix (after the expr)
   *)
  | Match of tok * expr * action list
  | Continue of tok * label_ident * sc
  | Break of tok * label_ident * sc
  (* todo? remove stmt argument? more symetric to Goto *)
  | Label of label * stmt
  | Goto of tok * label * sc (* less: use label_ident for computed goto in C*)
  (* TODO? move in expr! in C++ the expr can be an option *)
  | Throw of tok (* 'raise' in OCaml, 'throw' in Java/PHP *) * expr * sc
  | Try of tok * stmt * catch list * finally option
  | WithUsingResource of
      tok (* 'with' in Python, 'using' in C# *)
      * stmt (* resource acquisition *)
      * stmt (* newscope: block *)
  (* old: was 'expr * expr option' for Python/Java, but better to generalize.
   * alt: could move in expr and have Assert be an IdSpecial
   *)
  | Assert of tok * arguments * sc
  (* TODO? move this out of stmt and have a stmt_or_def_or_dir in Block?
   * or an item list where item is a stmt_or_def_or_dir (as well as field)
   *)
  | DefStmt of definition
  | DirectiveStmt of directive
  (* sgrep: *)
  | DisjStmt of stmt * stmt
  (* This is important to correctly compute a CFG. The any should not
   * contain any stmt! *)
  | OtherStmtWithStmt of other_stmt_with_stmt_operator * any list * stmt
  (* any here should _not_ contain any statement! otherwise the CFG will be
   * incorrect and some analysis (e.g., liveness) will be incorrect.
   * TODO: other_stmt_operator wrap, so enforce at least one token instead
   * of relying that the any list contains at least one token
   *)
  | OtherStmt of other_stmt_operator * any list

(* TODO: can also introduce var in some languages
 * less: factorize with for_var_or_expr
 *)
and condition =
  | Cond of expr
  (* e.g., CondWithDecl, CondDecl in C++ *)
  | OtherCond of todo_kind * any list

(* newscope: *)
(* less: could merge even more with pattern
 * list = PatDisj and Default = PatUnderscore,
 * so case_and_body of Switch <=> action of MatchPattern
 *)
and case_and_body =
  | CasesAndBody of (case list * stmt)
  (* sgrep: *)
  | CaseEllipsis of (* ... *) tok

(* less: we use expr_to_pattern for many languages to build a Case so
 * maybe we should instead have a CaseExpr and CasePattern?
 *)
and case =
  | Case of tok * pattern
  (* less: could unsugar as Case (PatUnderscore _) *)
  | Default of tok
  (* For Go, expr can contain some Assign bindings.
   * todo? could merge with regular Case? can 'case x := <-chan' be
   * transformed in a pattern?
   *)
  | CaseEqualExpr of tok * expr
  (* e.g., CaseRange for C++ *)
  | OtherCase of todo_kind * any list

(* todo: merge with case at some point *)
(* newscope: newvar: *)
and action = pattern * expr

(* newvar: newscope: usually a PatVar *)
and catch = tok (* 'catch', 'except' in Python *) * catch_exn * stmt

(* alt: we could reuse parameter, which has a ParamPattern and ParamClassic *)
and catch_exn =
  | CatchPattern of pattern
  (* for Java/C++/PHP/etc.
   * old: PatVar of type_ * (ident * id_info) option
   * and was in pattern as PatVar, but better to move out of pattern.
   * alt: we could abuse pattern and use PatTyped, but ugly.
   *)
  | CatchParam of parameter_classic
  (* e.g., CatchEmpty/CatchParams in Solidity *)
  | OtherCatch of todo_kind * any list

(* ptype should never be None *)

(* newscope: *)
and finally = tok (* 'finally' *) * stmt

and label = ident

and label_ident =
  | LNone (* C/Python *)
  | LId of label (* Java/Go/Kotlin *)
  | LInt of int wrap (* PHP *)
  (* PHP, woohoo, dynamic break! bailout for CFG, also in C gccext: goto *)
  | LDynamic of expr

(* todo? put also user-defined iterators here? like MacroIteration in C++ *)
and for_header =
  (* todo? copy Go and have 'of simple option * expr * simple option'? *)
  | ForClassic of
      for_var_or_expr list (* init *) * expr option (* cond *) * expr option (* next *)
  (* newvar: *)
  | ForEach of
      pattern * tok (* 'in' Python, 'range' Go, 'as' PHP, '' Java *) * expr (* pattern 'in' expr *)
  (* Lua. todo: merge with ForEach? *)
  (* pattern 'in' expr *)
  | ForIn of for_var_or_expr list (* init *) * expr list
  (* sgrep: *)
  | ForEllipsis of (* ... *) tok

and for_var_or_expr =
  (* newvar: *)
  | ForInitVar of entity * variable_definition
  (* less: should rename ForInitAssign really *)
  | ForInitExpr of expr

and other_stmt_with_stmt_operator =
  (* Python/Javascript *)
  (* TODO: used in C# with 'Using', make new stmt TryWithResource? do Java?*)
  | OSWS_With (* newscope: newvar: in OtherStmtWithStmt with LetPattern *)
  (* Ruby *)
  | OSWS_BEGIN
  | OSWS_END (* also in Awk, Perl? *)
  | OSWS_Else_in_try
  (* Rust *)
  | OSWS_UnsafeBlock
  | OSWS_AsyncBlock
  | OSWS_ConstBlock
  | OSWS_ForeignBlock
  | OSWS_ImplBlock
  (* Java's synchronize / C#'s lock *)
  | OSWS_Sync
  (* C# *)
  | OSWS_CheckedBlock
  | OSWS_UncheckedBlock
  (* C/C++/cpp *)
  | OSWS_Iterator
  (* e.g., Assembly in Solidity *)
  | OSWS_Todo

and other_stmt_operator =
  (* Python *)
  | OS_Delete
  (* todo: reduce? transpile? *)
  | OS_ForOrElse
  | OS_WhileOrElse
  | OS_TryOrElse
  | OS_ThrowFrom
  | OS_ThrowNothing
  | OS_ThrowArgsLocation (* Python2: `raise expr, expr` and `raise expr, expr, exr` *)
  | OS_Pass
  | OS_Async
  (* C/C++ *)
  | OS_Asm
  (* Go *)
  | OS_Go
  | OS_Defer
  | OS_Fallthrough (* only in Switch *)
  (* PHP *)
  | OS_GlobalComplex (* e.g., global $$x, argh *)
  (* Ruby *)
  | OS_Redo
  | OS_Retry
  (* OCaml *)
  | OS_ExprStmt2
  (* Other: Leave/Emit in Solidity *)
  | OS_Todo

(*****************************************************************************)
(* Pattern *)
(*****************************************************************************)
(* This is quite similar to expr. A few constructs in expr have
 * equivalent here prefixed with Pat (e.g., PaLiteral, PatId). We could
 * maybe factorize with expr, and this may help semgrep, but I think it's
 * cleaner to have a separate type because the scoping rules for a pattern and
 * an expr are quite different and not any expr is allowed here.
 *)
and pattern =
  | PatLiteral of literal
  (* Or-Type, used also to match OCaml exceptions.
   * Used with Rust path expressions, with an empty pattern list.
   *)
  | PatConstructor of name * pattern list (* TODO: bracket also here *)
  (* And-Type*)
  | PatRecord of (dotted_ident * pattern) list bracket
  (* newvar:! *)
  | PatId of ident * id_info (* Usually Local/Param, Global in toplevel let *)
  (* special cases of PatConstructor *)
  | PatTuple of pattern list bracket (* at least 2 elements *)
  (* less: generalize to other container_operator? *)
  | PatList of pattern list bracket
  | PatKeyVal of pattern * pattern (* a kind of PatTuple *)
  (* special case of PatId, TODO: name PatAny *)
  | PatUnderscore of tok
  (* OCaml and Scala *)
  | PatDisj of pattern * pattern (* also abused for catch in Java *)
  | PatTyped of pattern * type_
  | PatWhen of pattern * expr (* TODO: add tok, 'when' OCaml, 'if' Scala *)
  | PatAs of pattern * (ident * id_info)
  (* For Go also in switch x.(type) { case int: ... } *)
  | PatType of type_
  (* sgrep: *)
  | PatEllipsis of tok
  | DisjPat of pattern * pattern
  (* e.g., ???
   * todo: Python should transform expr pattern via expr_to_pattern(),
   * so maybe have a PatExpr like we have StmtExpr?
   *)
  | OtherPat of todo_kind * any list

(*****************************************************************************)
(* Type *)
(*****************************************************************************)
and type_ = {
  t : type_kind;
  (* used for C++ and Kotlin type qualifiers *)
  t_attrs : attribute list;
}

and type_kind =
  (* old: was originally TyApply (name, []), but better to differentiate.
   * old: there used to be also a 'TyBuiltin of string wrap' but simpler to
   * just use (TyN Id) instead.
   * todo? a type_builtin = TInt | TBool | ... that mimics the literal type?
   * todo? may need also TySpecial because the name can actually be
   *  self/parent/static (e.g., in PHP)
   *)
  | TyN of name
  (* covers list, hashtbl, etc.
   * note: the type_ should always be a TyN, so really it's a TyNameApply
   * but it's simpler to not repeat TyN to factorize code in semgrep regarding
   * aliasing.
   * TODO: could merge with TyN when name has proper qualifiers?
   *)
  | TyApply of type_ * type_arguments
  (* old: was 'TyFun of type_ list * type*' , but languages such as C and
   * Go allow also to name those parameters, and Go even allow ParamRest
   * parameters so we need at least 'type_ * attributes', at which point
   * it's simpler to just reuse parameter.
   *)
  | TyFun of parameter list * type_ (* return type *)
  (* a special case of TApply, also a special case of TPointer *)
  | TyArray of (* const_expr *) expr option bracket * type_
  | TyTuple of type_ list bracket
  | TyVar of ident (* type variable in polymorphic types (not a typedef) *)
  (* anonymous type, '_' in OCaml, 'dynamic' in Kotlin, 'auto' in C++.
   * TODO: type bounds Scala? *)
  | TyAny of tok
  | TyPointer of tok * type_
  | TyRef of tok * type_ (* C++/Rust *)
  | TyQuestion of type_ * tok (* a.k.a option type *)
  | TyRest of tok * type_ (* '...foo' e.g. in a typescript tuple type *)
  (* intersection types, used for Java Cast, and in Typescript *)
  | TyAnd of type_ * tok (* &, or 'with' in Scala *) * type_
  (* union types in Typescript *)
  | TyOr of type_ * tok (* | *) * type_
  (* Anonymous record type, a.k.a shape in PHP/Hack. See also AndType.
   * Most record types are defined via a TypeDef and are then referenced
   * via a TyName. Here we have flexible record types (a.k.a. rows in OCaml).
   *
   * TODO? just generalize as TClass of name option * class_definition
   * for C++. Those are ugly because it would be cleaner to have
   * definitions only at the toplevel, but C/C++/Go allow those nested
   * class defs. We could lift them up at the top and introduce gensym'ed
   * classnames, but it's maybe better to stay close to the code.
   *
   * The Class(Struct) of class_kind are used for Hack and Go, and Interface
   * only for Go.
   *)
  | TyRecordAnon of
      class_kind wrap (* 'struct/shape', fake in other *) * field list bracket
  (* TODO? a TyParen, like ParenExpr? A few languages may need that
   * for autofix to work correctly.
   *)
  (* sgrep-ext: *)
  | TyEllipsis of tok
  (* For languages such as Python which abuse expr to represent types.
   * At some point AST_generic_helpers.expr_to_type should be good enough
   * to transpile every expr construct, but for now we have this.
   * todo? have a TyLiteral of literal for Scala/JS, or use TyExpr for that?
   *)
  | TyExpr of expr
  (* e.g., Struct/Union/Enum names (convert in unique TyName?), TypeOf/TSized
   * TRefRef in C++, EnumAnon in C++/Hack, TyTodo in OCaml, TyLit in Scala/JS,
   * lots of stuff in C#, Lifetime in Rust, Delegation in Kotlin
   *)
  | OtherType of todo_kind * any list

(* <> in Java/C#/C++/Kotlin/Rust/..., [] in Scala and Go (for Map) *)
and type_arguments = type_argument list bracket

(* TODO? make a record also? *)
and type_argument =
  | TA of type_
  (* Java use-site variance *)
  | TAWildcard of
      tok (* '?' *) * (bool wrap (* extends|super, true=super *) * type_) option
  (* C++/Rust (Rust restrict expr to literals and ConstBlock) *)
  | TAExpr of expr
  (* e.g., Rust Lifetime 'x, Kotlin use-site variance *)
  | OtherTypeArg of todo_kind * any list

(*****************************************************************************)
(* Attribute *)
(*****************************************************************************)
and attribute =
  (* a.k.a modifiers *)
  | KeywordAttr of keyword_attribute wrap
  (* a.k.a decorators, annotations *)
  | NamedAttr of tok (* '@' *) * name * arguments (* less: option *)
  (* e.g,, per-language specific keywords like 'transient', 'synchronized'
   * todo: Expr used for Python, but should transform in NamedAttr when can *)
  | OtherAttribute of todo_kind * any list

and keyword_attribute =
  (* the classic C modifiers (except Auto) *)
  | Static (* a.k.a Intern in Solidity *)
  | Extern (* less: of string? like extern "C" in C++ or Rust *)
  | Volatile
  (* the classic C++ modifiers for fields/methods *)
  | Public
  | Private
  | Protected
  | Abstract (* a.k.a virtual in C++/Solidity *)
  (* for fields/methods in classes and also classes *)
  | Final
  | Override
  | Mutable (* 'var' in Scala *)
  | Const (* 'readonly' in Typescript, 'val' in Scala *)
  (* for classes (mostly for JVM languages) *)
  (* Scala 'case class', Java 'record', Kotlin 'data class' *)
  | RecordClass
  (* '@interface' in Java, 'annotation class' in Kotlin *)
  | AnnotationClass
  | EnumClass
  | SealedClass
  (* for variables (JS) *)
  | Var
  | Let
  (* less: should be part of the type? *)
  | Optional
  (* Typescript '?' *)
  | NotNull (* Typescript '!' *)
  (* for functions and methods *)
  | Recursive
  | MutuallyRecursive
  | Generator (* '*' in JS *)
  | Async
  | Inline
  (* for methods *)
  | Ctor
  | Dtor
  | Getter
  | Setter
  (* Rust *)
  | Unsafe
  | DefaultImpl (* Rust unstable, RFC 1210 *)
  (* Scala *)
  | Lazy

(* By name application in Scala, via => T, in parameter *)

(*****************************************************************************)
(* Definitions *)
(*****************************************************************************)
(* definition (or just declaration sometimes) *)
and definition = entity * definition_kind

(* old: type_: type_ option; but redundant with the type information in
 * the different definition_kind, as well as in id_info, and does not
 * have any meanings for certain defs (e.g., ClassDef) so not worth
 * factoring.
 * update: this could be useful in OCaml when you explicitely type an
 * entity (as in 'let (f: int -> int) = fun i -> i + 1), but we
 * currently abuse id_info.id_type for that.
 *
 * Note that with the new entity_name type and EPattern, one entity value
 * can actually correspond to the definition of multiple vairables.
 *
 * less: could be renamed entity_def, and name is a kind of entity_use.
 *)
and entity = {
  (* In Ruby you can define a class with a qualified name as in
   * class A::B::C, and even dynamically.
   * In C++ you can define a method with a class qualifier outside a class,
   * hence the use of entity_name below and not just ident.
   *)
  name : entity_name;
  attrs : attribute list;
  tparams : type_parameters;
}

(* old: used to be merged with field_name in a unique name_or_dynamic
 * but we want multiple entities (via EPattern) just here, hence the fork.
 *)
and entity_name =
  | EN of name
  | EDynamic of expr
  (* TODO: replace LetPattern and multivardef hack with that *)
  | EPattern of pattern
  (* e.g., AnonBitfield in C++ *)
  | OtherEntity of todo_kind * any list

and definition_kind =
  (* newvar: can be used also for methods or nested functions.
   * note: can have an empty body when the def is actually a declaration
   * in a header file (called a prototype in C).
   *)
  | FuncDef of function_definition
  (* newvar: can be used also for constants.
   * note: can contain special_multivardef_pattern!! ident in which case vinit
   * is the pattern assignment.
   *)
  | VarDef of variable_definition
  (* FieldDefColon can be used only inside a record (in a FieldStmt).
   * This used to be merged with VarDef, but in semgrep we don't want
   * a VarDef to match a field definition for certain languages
   * (e.g., JS, OCaml), and we definitely don't want the
   * vardef_to_assign equivalence to be used on FieldDefColon.
   * TODO? maybe merge back with VarDef but add a field in
   *  variable_definition saying whether it's using a colon syntax?
   * TODO? merge instead JS objects with Containers?
   *
   * Note that we could have used a FieldVar in the field type instead
   * of this FieldDef here, which would be more precise, but
   * this complicates things in semgrep where it's convenient to have
   * a uniform FieldStmt(DefStmt) that covers field and methods
   * (see m_list__m_field in semgrep).
   * Note that FieldDefColon where vinit is a Lambda instead be converted
   * in a FuncDef!
   *)
  | FieldDefColon of (* todo: tok (*':'*) * *) variable_definition
  | ClassDef of class_definition
  (* just inside a ClassDef with EnumClass *)
  | EnumEntryDef of enum_entry_definition
  | TypeDef of type_definition
  | ModuleDef of module_definition
  | MacroDef of macro_definition
  (* in a header file (e.g., .mli in OCaml or 'module sig') *)
  | Signature of type_
  (* Only used inside a function.
   * Needed for languages without local VarDef (e.g., Python/PHP)
   * where the first use is also its declaration. In that case when we
   * want to access a global we need to disambiguate with creating a new
   * local.
   *)
  | UseOuterDecl of tok (* 'global' or 'nonlocal' in Python, 'use' in PHP *)
  (* e.g., MacroDecl and MacroVar in C++, method alias in Ruby,
   * BitField in C/C++, Event/Modifier in Solidity
   *)
  | OtherDef of todo_kind * any list

(* template/generics/polymorphic-type *)
and type_parameter =
  | TP of type_parameter_classic
  (* sgrep-ext: *)
  | TParamEllipsis of tok
  (* e.g., Lifetime in Rust, complex types in OCaml, HasConstructor in C#,
   * regular Param in C++, AnonTypeParam/TPRest/TPNested in C++
   *)
  | OtherTypeParam of todo_kind * any list

and type_parameter_classic = {
  (* it would be nice to reuse entity here, but then the types would be
   * mutually recursive.
   * note: in Scala the ident can be a wildcard.
   *)
  tp_id : ident;
  tp_attrs : attribute list;
  (* upper type bounds (must-be-a-subtype-of)
   * alt: we could just use 'type_' and TyAnd for intersection types *)
  tp_bounds : type_ list;
  (* for Rust/C++. Similar to parameter_classic, but with type here. *)
  tp_default : type_ option;
  (* declaration-site variance (Kotlin/Hack/Scala) *)
  tp_variance : variance wrap option;
}

(* TODO bracket *)
and type_parameters = type_parameter list

(* less: have also Invariant? *)
and variance =
  (* '+' in Scala/Hack, 'out' in C#/Kotlin *)
  | Covariant
  (* '-' in Scala/Hack, 'in' in C#/Kotlin *)
  | Contravariant

(* ------------------------------------------------------------------------- *)
(* Function (or method) definition *)
(* ------------------------------------------------------------------------- *)
(* We could merge this type with variable_definition, and use a
 * Lambda for vinit, but it feels better to use a separate type.
 * TODO? add ctor initializer here instead of storing them in fbody?
 *)
and function_definition = {
  fkind : function_kind wrap;
  fparams : parameters;
  (* return type *)
  frettype : type_ option;
  (* TODO: fthrow *)
  (* newscope: *)
  fbody : function_body;
}

(* We don't really care about the function_kind in semgrep, but who
 * knows, maybe one day we will. We care about the token in the
 * function_kind wrap in fkind though for semgrep for accurate range.
 *)
and function_kind =
  | Function
  (* This is a bit redundant with having the func in a field *)
  | Method
  (* Also redundant; can just check if the fdef is in a Lambda *)
  | LambdaKind
  (* a.k.a short lambdas *)
  | Arrow
  (* for Scala *)
  | BlockCases

and parameters = parameter list

(* newvar: *)
and parameter =
  | Param of parameter_classic
  (* in OCaml, but also now JS, Python2, Rust *)
  | ParamPattern of pattern
  (* Both those ParamXxx used to be handled as a ParamClassic with special
   * VariadicXxx attribute in p_attr, but they are used in so many
   * languages that it's better to move then in a separate type.
   * We could do a ParamXxx of tok * ident, but some of those params
   * may have attribute, they need a id_info, so simpler to reuse
   * parameter_classic, but pname is always a Some (except for Ruby).
   * ParamRest could be called ParamSpread.
   * alt: move that in ParamPattern instead.
   *)
  | ParamRest of tok (* '...' in JS, '*' in Python *) * parameter_classic
  | ParamHashSplat of tok (* '**' in Python *) * parameter_classic
  (* sgrep: ... in parameters
   * note: foo(...x) of Js/Go is using the ParamRest, not this *)
  | ParamEllipsis of tok
  (* e.g., ParamTodo in OCaml, Reciever param in Go, SingleStar and Slash
   * in Python to delimit regular parameters from special one.
   * TODO ParamRef of tok * parameter_classic in PHP/Ruby *)
  | OtherParam of todo_kind * any list

(* less: could be merged with variable_definition, or pattern
 * less: could factorize pname/pattrs/pinfo with entity
 *)
and parameter_classic = {
  (* alt: use a 'ParamNoIdent of type_' when pname is None instead? *)
  pname : ident option;
  ptype : type_ option;
  pdefault : expr option;
  pattrs : attribute list;
  (* naming *)
  pinfo : id_info; (* Always Param *)
}

(* old: this used to be just an alias for 'stmt'; we were using
 * fake empty Block for FBDecl of fake ExprStmt for FBExpr.
 * However, some semgreo users may not like to treat a FBStmt
 * pattern to match an FBExpr, hence the more explicit cases.
 *)
and function_body =
  (* usually just a Block (where the brackets are fake in Ruby/Python/...) *)
  | FBStmt of stmt
  (* used for short lambdas in JS/Python, or regular func in OCaml/... *)
  | FBExpr of expr
  (* C/C++ prototypes or interface method declarations in Go/Java/... *)
  | FBDecl of sc
  (* Partial *)
  | FBNothing

(* ------------------------------------------------------------------------- *)
(* Variable definition *)
(* ------------------------------------------------------------------------- *)
(* Also used for constant_definition with attrs = [Const].
 * Also used for field definition in a class (and record).
 * We could use it for function_definition with vinit = Some (Lambda (...))
 * but maybe useful to explicitely makes the difference for now.
 *)
and variable_definition = {
  (* todo? should remove vinit and transform a VarDef with init with a VarDef
   * followed by an Assign (possibly to Null). See vardef_to_assign().
   *)
  vinit : expr option;
  (* less: (tok * expr) option? *)
  vtype : type_ option;
}

(* ------------------------------------------------------------------------- *)
(* Type definition *)
(* ------------------------------------------------------------------------- *)
and type_definition = { tbody : type_definition_kind }

and type_definition_kind =
  (* Algrebraic data types (ADTs), and basic enums.
   * For enum class see class_definition *)
  | OrType of or_type_element list
  (* Record definitions (for struct/class, see class_definition).
   * The fields will be defined via a DefStmt (VarDef variable_definition)
   * where the field.vtype should be defined.
   *)
  | AndType of field list bracket
  (* a.k.a typedef in C (and alias type in Go) *)
  | AliasType of type_
  (* Haskell/Hack/Go ('type x foo' vs 'type x = foo' in Go) *)
  | NewType of type_
  (* OCaml/Rust *)
  | AbstractType of tok (* usually a fake token *)
  | Exception of ident (* same name than entity *) * type_ list
  (* e.g., TdTodo types in OCaml *)
  | OtherTypeKind of todo_kind * any list

and or_type_element =
  (* OCaml *)
  | OrConstructor of ident * type_ list
  (* C enums (for enum class in Java/Kotlin, see EnumClass and EnumEntryDef *)
  | OrEnum of ident * expr option
  (* C union *)
  | OrUnion of ident * type_

(* ------------------------------------------------------------------------- *)
(* Object/struct/record/class field definition *)
(* ------------------------------------------------------------------------- *)

(* Field definition and use, for classes, objects, and records.
 *
 * note: I don't call it field_definition because it's used both to
 * define the shape of a field (a definition), and when creating
 * an actual field (a value).
 * note: It is tempting to want to 'field' be just an alias for 'stmt',
 * but fields can be matched in any order, so it is probably better
 * to keep them separate.
 * note: not all stmt in FieldStmt are definitions. You can have also
 * a Block like in Kotlin for 'init' stmts.
 * However ideally 'field' should really be just an alias for 'definition'.
 *
 * old: there used to be a FieldVar and FieldMethod similar to
 * VarDef and FuncDef but they are now converted into a FieldStmt(DefStmt).
 * This simplifies semgrep so that a function pattern can match
 * toplevel functions, nested functions, and methods.
 * Note that for FieldVar, we sometimes converts it to a FieldDefColon
 * (which is very similar to a VarDef) because some people don't want a VarDef
 * to match a field definition in certain languages (e.g., Javascript) where
 * the variable declaration and field definition have a different syntax.
 * Note: the FieldStmt(DefStmt(FuncDef(...))) can have empty body
 * for interface methods.
 * old: there was a special FieldSpread before (just for JS and Go) but we
 * now abuse ExprStmt(IdSpecial(Spread)) to represent it.
 *)
and field = F of stmt

(* ------------------------------------------------------------------------- *)
(* Class definition *)
(* ------------------------------------------------------------------------- *)
(* less: could be a special kind of type_definition *)
and class_definition = {
  ckind : class_kind wrap;
  (* 'cextends' contains usually 0 or 1 parent, and type_ should be TyN *)
  cextends : class_parent list;
  (* the class_kind in type_ must be Interface *)
  cimplements : type_ list;
  (* the class_kind in type_ are usually Trait *)
  (* PHP 'uses' *)
  cmixins : type_ list;
  (* for Java/Kotlin/Scala RecordClass (we could transpile them into fields) *)
  cparams : parameters;
  (* newscope:
   * note: this can be an empty fake bracket when used in Partial.
   * TODO? use an option here?
   *)
  cbody : field list bracket;
}

(* invariant: this must remain a simple enum; Map_AST relies on it.
 * for EnumClass/AnnotationClass/etc. see keyword_attribute.
 *)
and class_kind =
  | Class (* or Struct for C/Solidity *)
  | Interface (* abused for Contract in Solidity *)
  | Trait
  (* Kotlin/Scala *)
  | Object

(* A parent can have arguments in Scala/Java/Kotlin (because constructors
 * can be defined in the class header via cparams and then this class
 * header can call its parent constructor using those cparams).
 * alt: keep just 'type_' and add constructor calls in cbody.
 * TODO: also can have visibility modifier in C++ or virtual
 *)
and class_parent = type_ * arguments option

(* ------------------------------------------------------------------------- *)
(* Enum entry  *)
(* ------------------------------------------------------------------------- *)
(* for EnumClass, complex enums-as-classes in Java/Kotlin/Scala? *)
and enum_entry_definition = {
  (* the enum identifier is in the corresponding entity *)
  ee_args : arguments option;
  ee_body : field list bracket option;
}

(* ------------------------------------------------------------------------- *)
(* Module definition  *)
(* ------------------------------------------------------------------------- *)
and module_definition = { mbody : module_definition_kind }

and module_definition_kind =
  (* note that those could be converted also in ImportAs *)
  | ModuleAlias of dotted_ident
  (* newscope: *)
  | ModuleStruct of dotted_ident option * item list
  (* e.g., OCaml functors *)
  | OtherModule of todo_kind * any list

(* ------------------------------------------------------------------------- *)
(* Macro definition *)
(* ------------------------------------------------------------------------- *)
(* Used by cpp in C/C++
 * todo? differentiate MacroVar from MacroDef? some macro can take
 * an empty list of parameters, but they are not MacroVar
 *)
and macro_definition = { macroparams : ident list; macrobody : any list }

(*****************************************************************************)
(* Directives (Module import/export, package) *)
(*****************************************************************************)
and directive = {
  d : directive_kind;
  (* Right now d_attrs is used just for Static import in Java, and for
   * OCaml attributes of directives (e.g., open).
   *)
  d_attrs : attribute list;
}

(* It is tempting to simplify all those ImportXxx in a simpler
 * 'Import of dotted_ident * ...', but module_name is not always a DottedName
 * so it is better to clearly separate what is module_name/namespace from an
 * entity (in this module/namespace) even though some languages such as Python
 * blur the difference.
 *)
and directive_kind =
  (* newvar: *)
  | ImportFrom of
      tok (* 'import'/'from' for Python *) * module_name * ident * alias option (* as name alias *)
  | ImportAs of tok * module_name * alias option (* as name *)
  (* Bad practice! hard to resolve name locally.
   * We use ImportAll for C/C++ #include and C++ 'using namespace'.
   * The last tok is '.' in Go, '*' in Java/Python, '_' in Scala, and a fake
   * token in C++ 'using namespace std;'.
   *)
  | ImportAll of tok * module_name * tok
  (* packages are different from modules in that multiple files can reuse
   * the same package name; they are agglomerated in the same package.
   * The dotted_ident can be empty in C++.
   *)
  | Package of tok * dotted_ident (* a.k.a namespace *)
  (* This is used for languages such as C++/PHP/Scala with scoped namespaces.
   * alt: Package of tok * dotted_ident * item list bracket, but less
   * consistent with other directives, so better to use PackageEnd.
   *)
  | PackageEnd of tok
  | Pragma of ident * any list
  (* e.g., Dynamic include in C, Extern "C" in C++/Rust, Undef in C++/Ruby,
   * Export/Reexport in Javascript, Using in Solidity
   * TODO: Declare, move OE_UseStrict here for JS?
   *)
  | OtherDirective of todo_kind * any list

(* xxx as name *)
and alias = ident * id_info

(*****************************************************************************)
(* Toplevel *)
(*****************************************************************************)
(* item (a.k.a toplevel element, toplevel decl) is now equal to stmt.
 * Indeed, many languages allow nested functions, nested class definitions,
 * and even nested imports, so it is just simpler to merge item with stmt.
 * This simplifies semgrep too.
 * TODO? make it an alias to stmt_or_def_or_dir instead?
 *)
and item = stmt

and program = item list

(*****************************************************************************)
(* Partial *)
(*****************************************************************************)
(* sgrep: this is only used by semgrep *)
and partial =
  (* partial defs. The fbody or cbody in definition will be empty. *)
  | PartialDef of definition
  (* partial stmts *)
  | PartialIf of tok * expr (* todo? bracket? TODO? switch to condition? *)
  | PartialTry of tok * stmt
  | PartialCatch of catch
  | PartialFinally of tok * stmt
  | PartialMatch of tok * expr
  (* partial objects (just used in JSON and YAML patterns for now)
   * alt: todo? could be considered a full thing and use Fld?
   *)
  | PartialSingleField of string wrap (* id or str *) * tok (*:*) * expr
  (* not really a partial, but the partial machinery can help with that *)
  | PartialLambdaOrFuncDef of function_definition

(*****************************************************************************)
(* Any *)
(*****************************************************************************)

(* mentioned in many OtherXxx so must be part of the mutually recursive type *)
and any =
  (* main patterns used for semgrep *)
  | E of expr
  | S of stmt
  | Ss of stmt list
  (* also used for semgrep *)
  | T of type_
  | P of pattern
  | At of attribute
  | Fld of field
  | Flds of field list
  | Args of argument list
  | Partial of partial
  (* misc *)
  | I of ident
  | Str of string wrap
  | Def of definition
  | Dir of directive
  | Pr of program
  | Tk of tok
  | TodoK of todo_kind
  | Ar of argument
  | Pa of parameter
  | Tp of type_parameter
  | Ta of type_argument
  | Modn of module_name
  | Ce of catch_exn
  | Cs of case
  | ForOrIfComp of for_or_if_comp
  (* todo: get rid of some? *)
  | ModDk of module_definition_kind
  | En of entity
  | Dk of definition_kind
  | Di of dotted_ident
  | Lbli of label_ident
  (* Used only for Rust macro arguments for now *)
  | Anys of any list
[@@deriving show { with_path = false }, eq, hash]

(*****************************************************************************)
(* Special constants *)
(*****************************************************************************)

(* In JS one can do 'var {x,y} = foo();'. We used to transpile that
 * in multiple vars, but in sgrep one may want to match over those patterns.
 * However those multivars do not fit well with the (entity * definition_kind)
 * model we currently use, so for now we need this ugly hack of converting
 * the statement above in
 * ({name = "!MultiVarDef"}, VarDef {vinit = Assign (Record {...}, foo())}).
 * This is bit ugly, but at some point we may want to remove completely
 * VarDef by transforming them in Assign (see vardef_to_assign() below)
 * so this temporary hack is not too bad.
 *)
let special_multivardef_pattern = AST_generic_.special_multivardef_pattern

(*****************************************************************************)
(* Error *)
(*****************************************************************************)

(* This can be used in the xxx_to_generic.ml file to signal limitations.
 * This is captured in Main.exn_to_error to pinpoint the error location.
 * alt: reuse Parse_info.Ast_builder_error exn.
 *)
exception Error of string * Parse_info.t

let error tok msg = raise (Error (msg, tok))

(*****************************************************************************)
(* Fake tokens *)
(*****************************************************************************)

(* Try avoid using them! if you build new constructs, you should try
 * to derive the tokens in those new constructs from existing constructs
 * and use the Parse_info.fake_info variant, not the unsafe_xxx one.
 *)
let fake s = Parse_info.unsafe_fake_info s

let fake_bracket x = (fake "(", x, fake ")")

(* bugfix: I used to put ";" but now Parse_info.str_of_info prints
 * the string of a fake info
 *)
let sc = Parse_info.unsafe_fake_info ""

(*****************************************************************************)
(* AST builder helpers *)
(*****************************************************************************)
(* see also AST_generic_helpers.ml *)

(* ------------------------------------------------------------------------- *)
(* Shortcuts *)
(* ------------------------------------------------------------------------- *)

(* statements *)
let s skind =
  {
    s = skind;
    s_id = AST_utils.Node_ID.create ();
    s_use_cache = false;
    s_backrefs = None;
    s_bf = None;
    s_range = None;
  }

(* expressions *)
let e ekind = { e = ekind; e_id = 0; e_range = None }

(* directives *)
let d dkind = { d = dkind; d_attrs = [] }

(* types *)
let t tkind = { t = tkind; t_attrs = [] }

(* patterns *)
(* less: nothing yet, but at some point we may want to use a record
 * also for patterns *)
let p x = x

(* ------------------------------------------------------------------------- *)
(* Ident and names *)
(* ------------------------------------------------------------------------- *)

(* before Naming_AST.resolve can do its job *)
let sid_TODO = -1

let empty_var = { vinit = None; vtype = None }

let empty_id_info ?(hidden = false) () =
  {
    id_resolved = ref None;
    id_type = ref None;
    id_constness = ref None;
    id_hidden = hidden;
  }

let basic_id_info ?(hidden = false) resolved =
  {
    id_resolved = ref (Some resolved);
    id_type = ref None;
    id_constness = ref None;
    id_hidden = hidden;
  }

(* TODO: move AST_generic_helpers.name_of_id and ids here *)

(* ------------------------------------------------------------------------- *)
(* Entities *)
(* ------------------------------------------------------------------------- *)

(* alt: could use @@deriving make *)
let basic_entity ?hidden ?(attrs = []) ?(tparams = []) id =
  let idinfo = empty_id_info ?hidden () in
  { name = EN (Id (id, idinfo)); attrs; tparams }

(* ------------------------------------------------------------------------- *)
(* Arguments *)
(* ------------------------------------------------------------------------- *)

(* easier to use in List.map than each time (fun e -> Arg e) *)
let arg e = Arg e

(* ------------------------------------------------------------------------- *)
(* Expressions *)
(* ------------------------------------------------------------------------- *)
let special spec es =
  Call (IdSpecial spec |> e, fake_bracket (es |> List.map arg)) |> e

let opcall (op, tok) exprs : expr = special (Op op, tok) exprs

(* TODO: have a separate InterpolatedConcat in expr with a cleaner type
 * instead of abusing special?
 *)
let interpolated (lquote, xs, rquote) =
  match xs with
  | [ Common.Left3 (str, tstr) ] ->
      L (String (str, Parse_info.combine_infos lquote [ tstr; rquote ])) |> e
  | _ ->
      let special = IdSpecial (ConcatString InterpolatedConcat, lquote) |> e in
      Call
        ( special,
          ( lquote,
            xs
            |> List.map (function
                 | Common.Left3 str -> Arg (L (String str) |> e)
                 | Common.Right3 (lbrace, eopt, rbrace) ->
                     let special =
                       IdSpecial (InterpolatedElement, lbrace) |> e
                     in
                     let args = eopt |> Common.opt_to_list |> List.map arg in
                     Arg (Call (special, (lbrace, args, rbrace)) |> e)
                 | Common.Middle3 e -> Arg e),
            rquote ) )
      |> e

(* todo? use a special construct KeyVal valid only inside Dict? *)
let keyval k _tarrow v = Container (Tuple, fake_bracket [ k; v ]) |> e

(* ------------------------------------------------------------------------- *)
(* Parameters *)
(* ------------------------------------------------------------------------- *)

(* alt: could use @@deriving make *)
let param_of_id ?(pattrs = []) ?(ptype = None) ?(pdefault = None) id =
  {
    pname = Some id;
    pdefault;
    ptype;
    pattrs;
    pinfo = basic_id_info (Param, sid_TODO);
  }

let param_of_type ?(pattrs = []) ?(pdefault = None) ?(pname = None) typ =
  {
    ptype = Some typ;
    pname;
    pdefault;
    pattrs;
    pinfo = basic_id_info (Param, sid_TODO);
  }

(* ------------------------------------------------------------------------- *)
(* Types *)
(* ------------------------------------------------------------------------- *)
let ty_builtin id = TyN (Id (id, empty_id_info ())) |> t

(* ------------------------------------------------------------------------- *)
(* Type parameters *)
(* ------------------------------------------------------------------------- *)
let tparam_of_id ?(tp_attrs = []) ?(tp_variance = None) ?(tp_bounds = [])
    ?(tp_default = None) tp_id =
  TP { tp_id; tp_attrs; tp_variance; tp_bounds; tp_default }

(* ------------------------------------------------------------------------- *)
(* Statements *)
(* ------------------------------------------------------------------------- *)

let exprstmt e = s (ExprStmt (e, sc))

(* alt: EmptyStmt of sc? of ExprStmt of expr option * sc *)
let emptystmt t = s (Block (t, [], t))

(* The dual of exprstmt.
 * This is mostly used for languages where the division
 * between stmt and expr is fuzzy or nonexistent (e.g., OCaml, Scala)
 * and where things like While, Match are expressions, but in the
 * generic AST they are statements.
 * See also AST_generic_helpers with expr_to_pattern, expr_to_type,
 * pattern_to_expr, etc.
 *)
let stmt_to_expr st = e (StmtExpr st)

let empty_body = fake_bracket []

let stmt1 xs =
  match xs with
  | [] -> s (Block (fake_bracket []))
  | [ st ] -> st
  | xs -> s (Block (fake_bracket xs))

(* ------------------------------------------------------------------------- *)
(* Fields *)
(* ------------------------------------------------------------------------- *)

(* this should be simpler at some point if we get rid of FieldStmt *)
let fld (ent, def) = F (s (DefStmt (ent, def)))

let basic_field id vopt typeopt =
  let entity = basic_entity id in
  fld (entity, VarDef { vinit = vopt; vtype = typeopt })

let fieldEllipsis t = F (exprstmt (e (Ellipsis t)))

(* ------------------------------------------------------------------------- *)
(* Attributes *)
(* ------------------------------------------------------------------------- *)

let attr kwd tok = KeywordAttr (kwd, tok)

let unhandled_keywordattr (s, t) =
  (* TODO? or use OtherAttribue? *)
  NamedAttr (t, Id ((s, t), empty_id_info ()), fake_bracket [])

(*****************************************************************************)
(* AST accessors *)
(*****************************************************************************)

let unbracket (_, x, _) = x