# Module CST

    module CST: sig .. end

The type for concrete syntax trees of POSIX shell scripts. These trees are produced by the Morbig parser.

These type definitions refer directly to the grammar production rules of the POSIX standard. We use the following convention to name data constructors: given a rule `A -> P1 ... PN` of the grammar, the constructor for this rule starts with the name of the non terminal A and continues with the names of producers `Pi` appearing in the right-hand-side of the production rule. We do not need types for operators and reserved words.

These concrete syntax trees are actually richer than the production trees defined by the grammar. Indeed, they also embed concrete syntax trees for WORDs while the grammar sees WORDs are mere tokens. For instance, `echo `cat bar`` is interpreted by the grammar as a simple command with two WORDs `echo` and ``cat bar``. Morbig does not stop its work here: it also parses `cat bar` and the resulting concrete syntax tree is attached to the WORD ``cat bar``. See the type definition for `word` below for more details.

The PPX syntax extension package "visitors", written by François Pottier, is used to macro-generate many traversal functions over this concrete syntax tree. Note that we expose the .ml file of this module because the types generated by `visitors` are too complex to be displayed.

    type position = {

`` | `start_p : `lexing_position`;`
`` | `end_p : `lexing_position`;`

`}`

    type lexing_position = Stdlib.Lexing.position = {

`` | `pos_fname : `string`;`
`` | `pos_lnum : `int`;`
`` | `pos_bol : `int`;`
`` | `pos_cnum : `int`;`

`}`

    type 'a located = {

`` | `value : `'a`;`
`` | `position : `position`;`

`}`

    type program =

`|` | `Program_LineBreak_CompleteCommands_LineBreak of `linebreak' * complete_commands' * linebreak'``
`|` | `Program_LineBreak of `linebreak'``

    type complete_commands =

`|` | `CompleteCommands_CompleteCommands_NewlineList_CompleteCommand of `complete_commands' * newline_list' * complete_command'``
`|` | `CompleteCommands_CompleteCommand of `complete_command'``

    type complete_command =

`|` | `CompleteCommand_CList_SeparatorOp of `clist' * separator_op'``
`|` | `CompleteCommand_CList of `clist'``

    type clist =

`|` | `CList_CList_SeparatorOp_AndOr of `clist' * separator_op' * and_or'``
`|` | `CList_AndOr of `and_or'``

    type and_or =

`|` | `AndOr_Pipeline of `pipeline'``
`|` | `AndOr_AndOr_AndIf_LineBreak_Pipeline of `and_or' * linebreak' * pipeline'``
`|` | `AndOr_AndOr_OrIf_LineBreak_Pipeline of `and_or' * linebreak' * pipeline'``

    type pipeline =

`|` | `Pipeline_PipeSequence of `pipe_sequence'``
`|` | `Pipeline_Bang_PipeSequence of `pipe_sequence'``

    type pipe_sequence =

`|` | `PipeSequence_Command of `command'``
`|` | `PipeSequence_PipeSequence_Pipe_LineBreak_Command of `pipe_sequence' * linebreak' * command'``

    type command =

`|` | `Command_SimpleCommand of `simple_command'``
`|` | `Command_CompoundCommand of `compound_command'``
`|` | `Command_CompoundCommand_RedirectList of `compound_command' * redirect_list'``
`|` | `Command_FunctionDefinition of `function_definition'``

    type compound_command =

`|` | `CompoundCommand_BraceGroup of `brace_group'``
`|` | `CompoundCommand_Subshell of `subshell'``
`|` | `CompoundCommand_ForClause of `for_clause'``
`|` | `CompoundCommand_CaseClause of `case_clause'``
`|` | `CompoundCommand_IfClause of `if_clause'``
`|` | `CompoundCommand_WhileClause of `while_clause'``
`|` | `CompoundCommand_UntilClause of `until_clause'``

    type subshell =

`|` | `Subshell_Lparen_CompoundList_Rparen of `compound_list'``

    type compound_list =

`|` | `CompoundList_LineBreak_Term of `linebreak' * term'``
`|` | `CompoundList_LineBreak_Term_Separator of `linebreak' * term' * separator'``

    type term =

`|` | `Term_Term_Separator_AndOr of `term' * separator' * and_or'``
`|` | `Term_AndOr of `and_or'``

    type for_clause =

`|` | `ForClause_For_Name_DoGroup of `name' * do_group'``
`|` | `ForClause_For_Name_SequentialSep_DoGroup of `name' * sequential_sep' * do_group'``
`|` | `ForClause_For_Name_LineBreak_In_SequentialSep_DoGroup of `name' * linebreak' * sequential_sep' * do_group'``
`|` | `ForClause_For_Name_LineBreak_In_WordList_SequentialSep_DoGroup of `name' * linebreak' * wordlist' * sequential_sep' * do_group'``

    type wordlist =

`|` | `WordList_WordList_Word of `wordlist' * word'``
`|` | `WordList_Word of `word'``

    type case_clause =

`|` | `CaseClause_Case_Word_LineBreak_In_LineBreak_CaseList_Esac of `word' * linebreak' * linebreak' * case_list'``
`|` | `CaseClause_Case_Word_LineBreak_In_LineBreak_CaseListNS_Esac of `word' * linebreak' * linebreak' * case_list_ns'``
`|` | `CaseClause_Case_Word_LineBreak_In_LineBreak_Esac of `word' * linebreak' * linebreak'``

    type case_list_ns =

`|` | `CaseListNS_CaseList_CaseItemNS of `case_list' * case_item_ns'``
`|` | `CaseListNS_CaseItemNS of `case_item_ns'``

    type case_list =

`|` | `CaseList_CaseList_CaseItem of `case_list' * case_item'``
`|` | `CaseList_CaseItem of `case_item'``

    type case_item_ns =

`|` | `CaseItemNS_Pattern_Rparen_LineBreak of `pattern' * linebreak'``
`|` | `CaseItemNS_Pattern_Rparen_CompoundList of `pattern' * compound_list'``
`|` | `CaseItemNS_Lparen_Pattern_Rparen_LineBreak of `pattern' * linebreak'``
`|` | `CaseItemNS_Lparen_Pattern_Rparen_CompoundList of `pattern' * compound_list'``

    type case_item =

`|` | `CaseItem_Pattern_Rparen_LineBreak_Dsemi_LineBreak of `pattern' * linebreak' * linebreak'``
`|` | `CaseItem_Pattern_Rparen_CompoundList_Dsemi_LineBreak of `pattern' * compound_list' * linebreak'``
`|` | `CaseItem_Lparen_Pattern_Rparen_LineBreak_Dsemi_LineBreak of `pattern' * linebreak' * linebreak'``
`|` | `CaseItem_Lparen_Pattern_Rparen_CompoundList_Dsemi_LineBreak of `pattern' * compound_list' * linebreak'``

    type pattern =

`|` | `Pattern_Word of `word'``
`|` | `Pattern_Pattern_Pipe_Word of `pattern' * word'``

    type if_clause =

`|` | `IfClause_If_CompoundList_Then_CompoundList_ElsePart_Fi of `compound_list' * compound_list' * else_part'``
`|` | `IfClause_If_CompoundList_Then_CompoundList_Fi of `compound_list' * compound_list'``

    type else_part =

`|` | `ElsePart_Elif_CompoundList_Then_CompoundList of `compound_list' * compound_list'``
`|` | `ElsePart_Elif_CompoundList_Then_CompoundList_ElsePart of `compound_list' * compound_list' * else_part'``
`|` | `ElsePart_Else_CompoundList of `compound_list'``

    type while_clause =

`|` | `WhileClause_While_CompoundList_DoGroup of `compound_list' * do_group'``

    type until_clause =

`|` | `UntilClause_Until_CompoundList_DoGroup of `compound_list' * do_group'``

    type function_definition =

`|` | `FunctionDefinition_Fname_Lparen_Rparen_LineBreak_FunctionBody of `fname' * linebreak' * function_body'``

    type function_body =

`|` | `FunctionBody_CompoundCommand of `compound_command'``
`|` | `FunctionBody_CompoundCommand_RedirectList of `compound_command' * redirect_list'``

    type fname =

`|` | `Fname_Name of `name``

    type brace_group =

`|` | `BraceGroup_LBrace_CompoundList_RBrace of `compound_list'``

    type do_group =

`|` | `DoGroup_Do_CompoundList_Done of `compound_list'``

    type simple_command =

`|` | `SimpleCommand_CmdPrefix_CmdWord_CmdSuffix of `cmd_prefix' * cmd_word' * cmd_suffix'``
`|` | `SimpleCommand_CmdPrefix_CmdWord of `cmd_prefix' * cmd_word'``
`|` | `SimpleCommand_CmdPrefix of `cmd_prefix'``
`|` | `SimpleCommand_CmdName_CmdSuffix of `cmd_name' * cmd_suffix'``
`|` | `SimpleCommand_CmdName of `cmd_name'``

    type cmd_name =

`|` | `CmdName_Word of `word'``

    type cmd_word =

`|` | `CmdWord_Word of `word'``

    type cmd_prefix =

`|` | `CmdPrefix_IoRedirect of `io_redirect'``
`|` | `CmdPrefix_CmdPrefix_IoRedirect of `cmd_prefix' * io_redirect'``
`|` | `CmdPrefix_AssignmentWord of `assignment_word'``
`|` | `CmdPrefix_CmdPrefix_AssignmentWord of `cmd_prefix' * assignment_word'``

    type cmd_suffix =

`|` | `CmdSuffix_IoRedirect of `io_redirect'``
`|` | `CmdSuffix_CmdSuffix_IoRedirect of `cmd_suffix' * io_redirect'``
`|` | `CmdSuffix_Word of `word'``
`|` | `CmdSuffix_CmdSuffix_Word of `cmd_suffix' * word'``

    type redirect_list =

`|` | `RedirectList_IoRedirect of `io_redirect'``
`|` | `RedirectList_RedirectList_IoRedirect of `redirect_list' * io_redirect'``

    type io_redirect =

`|` | `IoRedirect_IoFile of `io_file'``
`|` | `IoRedirect_IoNumber_IoFile of `io_number * io_file'``
`|` | `IoRedirect_IoHere of `io_here'``
`|` | `IoRedirect_IoNumber_IoHere of `io_number * io_here'``

    type io_file =

`|` | `IoFile_Less_FileName of `filename'``
`|` | `IoFile_LessAnd_FileName of `filename'``
`|` | `IoFile_Great_FileName of `filename'``
`|` | `IoFile_GreatAnd_FileName of `filename'``
`|` | `IoFile_DGreat_FileName of `filename'``
`|` | `IoFile_LessGreat_FileName of `filename'``
`|` | `IoFile_Clobber_FileName of `filename'``

    type filename =

`|` | `Filename_Word of `word'``

    type io_here =

`|` | `IoHere_DLess_HereEnd of `here_end' * word' Stdlib.ref``
`|` | `IoHere_DLessDash_HereEnd of `here_end' * word' Stdlib.ref``

The two IoHere constructors have two arguments. The second argument is the word holding the contents of the here document, which does not figure in the grammar.

    type here_end =

`|` | `HereEnd_Word of `word'``

    type newline_list =

`|` | `NewLineList_NewLine`
`|` | `NewLineList_NewLineList_NewLine of `newline_list'``

    type linebreak =

`|` | `LineBreak_NewLineList of `newline_list'``
`|` | `LineBreak_Empty`

    type separator_op =

`|` | `SeparatorOp_Uppersand`
`|` | `SeparatorOp_Semicolon`

    type separator =

`|` | `Separator_SeparatorOp_LineBreak of `separator_op' * linebreak'``
`|` | `Separator_NewLineList of `newline_list'``

    type sequential_sep =

`|` | `SequentialSep_Semicolon_LineBreak of `linebreak'``
`|` | `SequentialSep_NewLineList of `newline_list'``

    type word =

`|` | `Word of `string * word_cst``

    type word_cst = word_component list

    type word_component =

`|` | `WordSubshell of `subshell_kind * program located``
`|` | `WordName of `string``
`|` | `WordAssignmentWord of `assignment_word``
`|` | `WordDoubleQuoted of `word``
`|` | `WordSingleQuoted of `word``
`|` | `WordTildePrefix of `string``
`|` | `WordLiteral of `string``
`|` | `WordVariable of `variable``
`|` | `WordGlobAll`
`|` | `WordGlobAny`
`|` | `WordReBracketExpression of `bracket_expression``
`|` | `WordEmpty`

    type bracket_expression =

`|` | `BracketExpression_LBRACKET_MatchingList_RBRACKET of `matching_list``
`|` | `BracketExpression_LBRACKET_NonMatchingList_RBRACKET of `nonmatching_list``

    type matching_list =

`|` | `MatchingList_BracketList of `bracket_list``

    type nonmatching_list =

`|` | `NonMatchingList_BracketList of `bracket_list``

    type bracket_list =

`|` | `BracketList_FollowList of `follow_list``
`|` | `BracketList_FollowList_MINUS of `follow_list``

    type follow_list =

`|` | `FollowList_ExpressionTerm of `expression_term``
`|` | `FollowList_FollowList_ExpressionTerm of `follow_list * expression_term``

    type expression_term =

`|` | `ExpressionTerm_SingleExpression of `single_expression``
`|` | `ExpressionTerm_RangeExpression of `range_expression``

    type single_expression =

`|` | `SingleExpression_EndRange of `end_range``
`|` | `SingleExpression_CharacterClass of `character_class``
`|` | `SingleExpression_EquivalenceClass of `equivalence_class``

    type range_expression =

`|` | `RangeExpression_StartRange_EndRange of `start_range * end_range``
`|` | `RangeExpression_StartRange_MINUS of `start_range``

    type start_range =

`|` | `StartRange_EndRange_MINUS of `end_range``

    type end_range =

`|` | `EndRange_COLLELEMSINGLE of `char``
`|` | `EndRangeCollatingSymbol of `collating_symbol``

    type collating_symbol =

`|` | `CollatingSymbol_OpenDot_COLLELEMSINGLE_DotClose of `char``
`|` | `CollatingSymbol_OpenDot_COLLELEMMULTI_DotClose of `string``
`|` | `CollatingSymbol_OpenDot_METACHAR_DotClose of `char``

    type equivalence_class =

`|` | `EquivalenceClass_OpenEqual_COLLELEMSINGLE_EqualClose of `char``
`|` | `EquivalenceClass_OpenEqual_COLLELEMMULTI_EqualClose of `string``

    type character_class =

`|` | `CharacterClass_OpenColon_CLASSNAME_ColonClose of `class_name``

    type class_name =

`|` | `ClassName of `string``

    type character_range =

`|` | `Range of `char list``

    type variable =

`|` | `VariableAtom of `string * variable_attribute``

    type variable_attribute =

`|` | `NoAttribute`
`|` | `ParameterLength`
`|` | `UseDefaultValues of `string * word``
`|` | `AssignDefaultValues of `string * word``
`|` | `IndicateErrorifNullorUnset of `string * word``
`|` | `UseAlternativeValue of `string * word``
`|` | `RemoveSmallestSuffixPattern of `word``
`|` | `RemoveLargestSuffixPattern of `word``
`|` | `RemoveSmallestPrefixPattern of `word``
`|` | `RemoveLargestPrefixPattern of `word``

    type subshell_kind =

`|` | `SubShellKindBackQuote`
`|` | `SubShellKindParentheses`

    type name =

`|` | `Name of `string``

    type assignment_word = name * word

    type io_number =

`|` | `IONumber of `string``

    type program' = program located

    type complete_commands' = complete_commands located

    type complete_command' = complete_command located

    type clist' = clist located

    type and_or' = and_or located

    type pipeline' = pipeline located

    type pipe_sequence' = pipe_sequence located

    type command' = command located

    type compound_command' = compound_command located

    type subshell' = subshell located

    type compound_list' = compound_list located

    type term' = term located

    type for_clause' = for_clause located

    type wordlist' = wordlist located

    type case_clause' = case_clause located

    type case_list_ns' = case_list_ns located

    type case_list' = case_list located

    type case_item_ns' = case_item_ns located

    type case_item' = case_item located

    type pattern' = pattern located

    type if_clause' = if_clause located

    type else_part' = else_part located

    type while_clause' = while_clause located

    type until_clause' = until_clause located

    type function_definition' = function_definition located

    type function_body' = function_body located

    type fname' = fname located

    type brace_group' = brace_group located

    type do_group' = do_group located

    type simple_command' = simple_command located

    type cmd_name' = cmd_name located

    type cmd_word' = cmd_word located

    type cmd_prefix' = cmd_prefix located

    type cmd_suffix' = cmd_suffix located

    type redirect_list' = redirect_list located

    type io_redirect' = io_redirect located

    type io_file' = io_file located

    type filename' = filename located

    type io_here' = io_here located

    type here_end' = here_end located

    type newline_list' = newline_list located

    type linebreak' = linebreak located

    type separator_op' = separator_op located

    type separator' = separator located

    type sequential_sep' = sequential_sep located

    type word' = word located

    type name' = name located

    type assignment_word' = assignment_word located