(* Copyright (C) 1990, Digital Equipment Corporation.         *)
(* All rights reserved.                                       *)
(* See the file COPYRIGHT for a full description.             *)

(* Last modified on Wed Mar 21 06:33:25 1990 by muller        *)

INTERFACE M3AST;

(*  Abstract Syntax Trees
    Draft, 16 January 1990
    

   This interface defines a data structure for Modula-3 parse trees. 
        
   An AST.T (or "node") represents a syntactically valid sequence 
   of tokens from a Modula-3 program or program fragment.  This 
   interface reveals enough information to reconstruct the sequence 
   of tokens in the concrete syntax that corresponds to an abstract 
   tree, except that:

       the tree contains no comments or pragmas other than <*INLINE*> 
       and <*EXTERNAL*>,

       unnecessary trailing semicolons and leading vertical bars have 
       no effect on the tree,
       
       the tree reflects only the value of literals; not the source 
       that produced them. 

   If you care about the concrete syntax in these three cases, you 
   can use the companion interface NoisyAST, which defines a data 
   structure in which comments, pragmas, and redundent occurrences 
   of "VALUE", ";" and "|" are attached to an AST.T.    
    
   This interface reveals only the context-free tree structure. If 
   you need information about the types of nodes or the scopes of 
   identifiers, see the companion interface TypedAST. 
   
   The remainder of this interface consists mostly of declarations 
   for various node types.  Each declaration is followed by the syntax 
   for the token sequences that a node of that type can represent.  
   We use the following notation for syntax:
   
       A B        A followed by B
       A|B        A or B
       [A]        A or empty
       {A}        A possibly empty list of A's.
       {A B...}   [A {B A}]

   That is, {A B...} is a list of A's separated by B's.    

   The Modula-3 Report used A&B when either A or B could be omitted 
   but not both.   We will simply write [A] [B] in this case, and 
   relegate the restriction that at least one must be present to a 
   comment.

   The following conventions are used to declare the node types:

   1. If syntax class X is defined as the EBNF alternative Y | Z, 
   then node types Y and Z are subtypes of X.  For example, 
   
       CompilationUnit <: T; 
       (* Interface | Module *)

   This means that a node of type CompilationUnit represents a string 
   in one of the syntactic classes Interface or Module, and implies 
   that the node types Interface and Module are subtypes of 
   CompilationUnit, and that they are its only direct subtypes.

   2. If a syntax class X is defined as an EBNF sequence Y1 ... Yn, 
   then the node type X contains a field for each of the Y's, excluding 
   operators and keywords.  The fields are in the same order as the 
   Y's.  For example,

       SelectiveImport <: Import OBJECT id: Id; idlist: IDList END;
       (* FROM id IMPORT idlist *)

   This means that a node p of type SelectiveImport represents a string 
   with the syntax FROM Id IMPORT IDList. The field p.id represents 
   the Id part of the string and p.idlist represents the IDList part 
   of the string.  There is no need to represent the FROM and IMPORT 
   keywords explicitly, since they are implied by the node type. 

   3. If any of the Y's in the above rule are surrounded by [], the 
   corresponding fields of the node will be NIL if Y is omitted. 
   If any of the Y's is surrounded by {}, the corresponding part 
   of the node type is a REF ARRAY with one entry for each repetition.
   For example, consider

       ForStmt <: Stmt OBJECT
         id: Id;
         lo: Expr;
         hi: Expr;
         step: Expr;
         stmts: REF ARRAY OF Stmt
       END;
       (* FOR Id := Expr TO Expr [BY Expr] DO {Stmt ;...} END *)

  If p is a node of type ForStmt, then p.step = NIL means the [BY 
  Expr] clause is absent from the concrete syntax.  Also, p.stmt[i] 
  denotes the ith statement in the body of the FOR statement.  The 
  field p.stmts will never be NIL; if the body of the loop is empty, 
  then NUMBER(p.stmts^) will be zero.  The mnemonic names for the 
  fields help you to tell which Expr in the object goes with which 
  Expr in the syntax; if there is any doubt, the rule is that the 
  object fields are in the same order as the syntax non-terminals.

  If the optional part of the syntax consists only of keywords, 
  then an enumerated type (generally a boolean) is used to record 
  whether the option was present.  For example,

       Interface <: CompilationUnit OBJECT 
         safe: BOOLEAN;
         name: Id;
         imports: REF ARRAY OF Import;
         decls: REF ARRAY OF Declaration;
       END;
       (* [UNSAFE] INTERFACE Id; {Import ;} {Declaration} END Id. *)

    The presense of the UNSAFE keyword in the concrete syntax will 
    cause p.safe to be set to FALSE in the abstract syntax tree.

    This last example illustrates a final point: the repeated names 
    at the ends of procedures and compilation units are not repeated 
    in the node. 

   *)

IMPORT Property, Atom, M3Value;

TYPE 
  T <: Property.Set;
  (* So you can use Property.Put and Property.Get to store  
     your own attributes on an AST node. *)

(*  A node ch is a "child" of a node p if

        (1) both ch and p are members of type AST.T

        (2) ch = p.f or ch = p.f[i] for some field f declared in this 
            interface, and for some integer i. (This includes the 
            possibility that ch = NIL.)

    The children of a node are ordered first by field, then (in case 
    the field is an array) by index.   *)
    
PROCEDURE Children (nd: T): CARDINAL;
(* The number of children of nd. *)

PROCEDURE Ith(nd: T; i: CARDINAL): T;
(* Child number i of nd.  A checked runtime error if i >= NUMBER(nd). *) 

(* The rest of the interface corresponds directly to the M3 
   context-free syntax. *)

TYPE
  CompilationUnit <: T; 
  (* Interface | Module *)

  Interface <: CompilationUnit OBJECT 
    safe: BOOLEAN;
    name: Id;
    imports: REF ARRAY OF Import;
    decls: REF ARRAY OF Declaration;
  END;
  (* [UNSAFE] INTERFACE Id; {Import ;} {Declaration} END Id. *)

  Module <: CompilationUnit OBJECT
    safe: BOOLEAN;
    name: Id;
    imports: REF ARRAY OF Import;
    exports: IDList;
    block: Block
  END;
  (* [UNSAFE] MODULE Id [EXPORTS IDList]; {Import ;}; Block END Id. *)
  
  Import <: T; 
  (* SelectiveImport | CompleteImport *)
  
  SelectiveImport <: Import OBJECT id: Id; idlist: IDList END;
  (* FROM Id IMPORT IDList *)

  CompleteImport <: Import OBJECT idlist: IDList END;
  (* IMPORT IDList *)

  Block <: T OBJECT 
    decls: REF ARRAY OF Declaration; 
    body: REF ARRAY OF Stmt 
  END;
  (* {Declaration} BEGIN {Stmt ;...} END *)

  Declaration <: T;
  (* ConstDeclaration | TypeDeclaration | ExceptionDeclaration |
     VarDeclaration | ProcDeclaration | Revelation *)

  ConstDeclaration <: Declaration OBJECT 
    decls: REF ARRAY OF ConstDecl 
  END;
  (* CONST {ConstDecl ;} *)

  TypeDeclaration <: Declaration OBJECT 
    decls: REF ARRAY OF TypeDecl 
  END;
  (* TYPE {TypeDecl ;} *)

  ExceptionDeclaration <: Declaration OBJECT 
    decls: REF ARRAY OF ExceptionDecl 
  END;
  (* EXCEPTION {ExceptionDecl ;} *)

  VarDeclaration <: Declaration OBJECT 
    decls: REF ARRAY OF VarDecl 
  END;
  (* VAR {Declaration ;} *)

  ProcDeclaration <: Declaration OBJECT 
    name: Id; 
    signature: Signature; 
    body: Block 
  END;
  (* PROCEDURE Id Signature [= Block Id]; *)

  Revelation <: Declaration; 
  (* DefinitiveRevelation | PartialRevelation *)

  DefinitiveRevelation <: Revelation OBJECT
    qid: QualID; 
    type: Type 
  END;
  (* REVEAL QualID = Type ; *)

  PartialRevelation <: Revelation OBJECT
    qid: QualID; 
    type: Type 
  END;
  (* REVEAL QualID <: Type ; *)

  ConstDecl <: T OBJECT id: Id; type: Type; value: M3Value.T END;
  (* Id [: Type] = Value *)

  TypeDecl <: T;
  (* OpaqueDecl | ConcreteDecl *)

  OpaqueDecl <: TypeDecl OBJECT id: Id; type: Type END;
  (* Id <: Type *)

  ConcreteDecl <: TypeDecl OBJECT id: Id; type: Type END;
  (* Id = Type *)

  ExceptionDecl <: T OBJECT 
    id: Id; 
    type: Type 
  END;
  (* Id [(Type)] *)

  VarDecl <: T OBJECT
    ids: IDList; type: Type; init: Expr END;
   (* IDList [: Type] [:= Expr] *)
   (* The type and init parts cannot both be omitted. *)
      
   Signature <: T OBJECT
     formals: REF ARRAY OF Formal;
     resultType: Type;
     raises: REF ARRAY OF QualID;
     END;
   (* ({Formal ;...}) [: Type] [RAISES {QualID ,...}] *)

   Mode = {Value, Var, Readonly, Blank};
   
   Formal <: T OBJECT
     mode: Mode;
     idlist: IDList;
     type: Type;
     default: ConstExpr
   END;
   (* [VALUE | VAR | READONLY] IDList [: Type] [:= ConstExpr] *)
   (* The type and default cannot both be omitted. *)
   (* Note that mode = Blank and mode = VALUE have the same
      semantics. *) 

  Stmt <: T; 
  (* AssignStmt | Block | CallStmt | CaseStmt | ExitStmt | 
     EvalStmt | ForStmt | IfStmt | LockStmt | LoopStmt | RaiseStmt | 
     RepeatStmt | ReturnStmt | TryFinStmt | TryXptStmt | TCaseStmt | 
     WhileStmt | WithStmt *)

  AssignStmt <: Stmt OBJECT lhs, rhs: Expr END;
  (* Expr := Expr *)
  
  CallStmt <: Stmt OBJECT proc: Expr; args: REF ARRAY OF Actual END;
  (* Expr({Actual ,...}) *)
  
  CaseStmt <: Stmt OBJECT 
    exp: Expr; 
    cases: REF ARRAY OF Case; 
    else: REF ARRAY OF Stmt 
  END;
  (* CASE Expr OF {Case |...} [ELSE {Stmt ;...}] END *)

  Case <: T OBJECT
    labels: REF ARRAY OF CaseLabel;
    stmts: REF ARRAY OF Stmt
  END;
  (* {CaseLabel ,...} => {Stmt ;...} *)

  CaseLabel <: T OBJECT
    exp1: ConstExpr;
    exp2: ConstExpr
  END;
  (* ConstExpr [ .. ConstExpr  ] *)

  ExitStmt <: Stmt OBJECT END;
  (* EXIT *)

  EvalStmt <: Stmt OBJECT expr: Expr END;
  (* EVAL Expr *)

  ForStmt <: Stmt OBJECT
    id: Id;
    lo: Expr;
    hi: Expr;
    step: Expr;
    stmts: REF ARRAY OF Stmt;
  END;
  (* FOR Id := Expr TO Expr [BY Expr] DO {Stmt ;...} END *)

  IfStmt <: Stmt OBJECT
    cases: REF ARRAY OF IfCase;
    else: REF ARRAY OF Stmt
  END;
  (* IF {IfCase ELSIF...} [ELSE {Stmt ;...}] END *)

  IfCase <: T OBJECT exp: Expr; stmts: REF ARRAY OF Stmt END;
  (* Expr THEN {Stmt ;...} *)

  LockStmt <: Stmt OBJECT expr: Expr; stmts: REF ARRAY OF Stmt END;
  (* LOCK Expr DO {Stmt ;...} END *)

  LoopStmt <: Stmt OBJECT stmts: REF ARRAY OF Stmt END;
  (* LOOP {Stmt ;...} END *)
  
  RaiseStmt <: Stmt OBJECT qid: QualID; arg: Expr END;
  (* RAISE QualID [ (Expr) ] *)

  RepeatStmt <: Stmt OBJECT stmts: REF ARRAY OF Stmt; expr: Expr END;
  (* REPEAT {Stmt ;...} UNTIL Expr END *)

  ReturnStmt <: Stmt OBJECT expr: Expr END;
  (* RETURN [ (Expr) ] *)

  TCaseStmt <: Stmt OBJECT
    exp: Expr;
    cases: REF ARRAY OF TCase;
    stmts: REF ARRAY OF Stmt
  END;
  (* TYPECASE Expr OF {TCase |...} [ ELSE {Stmt ;...}] END *)

  TCase <: T OBJECT
    types: REF ARRAY OF Type;
    id: Id;
    stmts: REF ARRAY OF Stmt
  END;
  (* {Type ,...} [ (Id) ] => {Stmt ;...} *)
  
  TryXptStmt <: Stmt OBJECT
    stmts1: REF ARRAY OF Stmt;
    handlers: REF ARRAY OF Handler;
    stmts2: REF ARRAY OF Stmt
  END;
  (* TRY {Stmt ;...} EXCEPT {Handler |...} [ELSE {Stmt ;...}] END *)

  Handler <: T OBJECT
    qids: REF ARRAY OF QualID;
    id: Id;
    stmts: REF ARRAY OF Stmt
  END;
  (* {QualId ,...} [ (Id) ] => {Stmt} *)

  TryFinStmt <: Stmt OBJECT
    stmts1: REF ARRAY OF Stmt;
    stmts2: REF ARRAY OF Stmt 
  END;
  (* TRY {Stmt ;...} FINALLY {Stmt ;...} END *)
  
  WhileStmt <: Stmt OBJECT
    exp: Expr;
    stmts: REF ARRAY OF Stmt
  END;
  (* WHILE Expr DO {Stmt ;...} END *)

  WithStmt <: Stmt OBJECT
    bindings: REF ARRAY OF WithBinding;
    stmts: REF ARRAY OF Stmt
  END;
  (* WITH {WithBinding ,...} DO {Stmt ;...} END *)

  WithBinding <: T OBJECT id: Id; expr: Expr END;
  (* Id = Expr *)

  Actual <: T;
  (* TypeActual | ExprActual *)

  TypeActual <: Actual OBJECT type: Type END;
  (* Type *)

  ExprActual <: Actual OBJECT id: Id; expr: Expr END;
  (* [ Id := ] Expr *)

  (* Warning: the context-free parser cannot tell whether an identifier 
     denotes a type.  Therefore, if p is an ExprActual, p.expr could be 
     a type identifier. *)
      
  Type <: T;
  (* TypeName | ArrayType | PackedType | EnumType | ObjectType | 
     ProcedureType | RecordType | RefType | SubrangeType | 
     ParenthesizedType *)
  
  ArrayType <: Type OBJECT
    indexes: REF ARRAY OF Type;
    element: Type
  END;
  (* ARRAY [{Type ,...}] OF Type *)
  (* If indexes # NIL, then NUMBER(indexes^) > 0 *)

  PackedType <: Type OBJECT
    size: ConstExpr;
    type: Type
  END;
  (* BITS ConstExpr FOR Type *)

  EnumType <: Type OBJECT
    idlist: IDList
  END;
  (* "{" idlist ,... "}" *)

  ObjectType <: Type OBJECT
    ancester: Type;
    brand: Brand;
    fields: REF ARRAY OF Field;
    methods: REF ARRAY OF Method;
  END;
  (* [Type] [Brand] OBJECT {Field ;...} [METHODS {Method ;...}] END *)

  Brand <: T OBJECT
    text: TextLiteral
  END;
  (* BRANDED [TextLiteral] *)
  
  Field <: T OBJECT
    idlist: IDList;
    type: Type;
    default: ConstExpr;
  END;
  (* IdList [: Type] [:= ConstExpr] *)
  (* type and default will not both be NIL *)

  Method <: T OBJECT
    id: Id;
    signature: Signature;
    qid: QualID;
  END;
  (* Id [Signature] [:= QualID] *)
  (* signature and qid will not both be NIL *)

  ProcedureType <: Type OBJECT sig: Signature END;
  (* PROCEDURE Signature *)
  
  RecordType <: Type OBJECT fields: REF ARRAY OF Field END;
  (* RECORD {Field ;...} END *)
  
  RefType <: Type OBJECT
    traced: BOOLEAN;
    brand: Brand;
    type: Type
  END;
  (* [ UNTRACED ] [Brand] REF Type *)

  SetType <: Type OBJECT
    type: Type
  END;
  (* SET OF Type *)

  SubrangeType <: Type OBJECT
    lo, hi: ConstExpr
  END;
  (* "[" ConstExpr .. ConstExpr "]" *)

  Expr <: T;
  (* Ident | Literal | Application *)

  (* For the syntax of identifiers and literals, see the M3 report. 
     The nodes for these syntactic clases contain value of the token. 
     If you need to get at the source characters for the tokens, 
     use the NoisyAST interface. *)

  Ident <: Expr OBJECT id: Id END;

  Literal <: Expr;
  (* CharLiteral | TextLiteral | Number *)

  CharLiteral <: Literal OBJECT ch: CHAR END;

  TextLiteral <: Literal OBJECT text: TEXT END;

  Number <: Literal;
  (* Int | Real | LongReal *)

  Int <: Number OBJECT val: INTEGER END;

  Real <: Number OBJECT val: REAL END;

  LongReal <: Number OBJECT val: LONGREAL END;
  
  Application <: Expr;
  (* Prefix | Infix | Postfix | ProcApp | Indexed | Constructor *)

  Prefix <: Application OBJECT
    op: Atom.T;
    arg: Expr
  END;
  (* op arg *)
  (* op will be eq to one of Plus, Minus, Not. *)

  Infix <: Application OBJECT
    arg1: Expr;
    op: Atom.T;
    arg2: Expr
  END;
  (* arg1 op arg2 *)
  (* op will be eq to one of Eq, Neq, Le, Lt, 
     Gt, Ge, In, Plus, Minus, Concat, Times, Divide, 
     Div, Dot from the BuiltIn interface. *)

  Postfix <: Application OBJECT
    arg: Expr;
    op: Atom.T
  END;
  (* arg ^ *)
  (* op will be eq to BuiltIn.Hat. *)

  ProcApp <: Application OBJECT
    proc: Expr;
    args: REF ARRAY OF Actual
  END;
  (* proc({Actual , ...}) *)

  Indexed <: Application OBJECT
    array: Expr;
    indexes: REF ARRAY OF Expr
  END;
  (* Expr[{Expr ,...}] *)

  Constructor <: Application OBJECT
    t: Type;
    args: REF ARRAY OF ConsArg
  END;
  (* Type "{" {ConsArg ,...} "}" *)
  
  ConsArg <: T;
  (* SimpleArg | RangeArg | KeywordArg | DotDotArg *)
  
  SimpleArg <: ConsArg OBJECT expr: Expr END;
  (* Expr *)
  
  RangeArg <: ConsArg OBJECT expr1, expr2: Expr END;
  (* Expr [.. Expr] *)
  (* Allowed only in set constructors. *)

  KeywordArg <: ConsArg OBJECT id: Id; expr: Expr END;
  (* Id := Expr *)
  (* Allowed only in record constructors. *)

  DotDotArg <: ConsArg OBJECT END;
  (* ".." *)
  (* Allowed only as the last argument in an array constructor. *)

  ConstExpr <: Expr;

  QualID <: Expr; (* Will be an application of Dot to two IDs. *)

  IDList = REF ARRAY OF Id;
  (* {Id ,...} *)

  Id = Atom.T;
  
END M3AST.