#
#
#           The Nimrod Compiler
#        (c) Copyright 2011 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

# abstract syntax tree + symbol table

import 
  msgs, nhashes, nversion, options, strutils, crc, ropes, idents, lists

const 
  ImportTablePos* = 0
  ModuleTablePos* = 1

type 
  TCallingConvention* = enum 
    ccDefault,                # proc has no explicit calling convention
    ccStdCall,                # procedure is stdcall
    ccCDecl,                  # cdecl
    ccSafeCall,               # safecall
    ccSysCall,                # system call
    ccInline,                 # proc should be inlined
    ccNoInline,               # proc should not be inlined
    ccFastCall,               # fastcall (pass parameters in registers)
    ccClosure,                # proc has a closure
    ccNoConvention            # needed for generating proper C procs sometimes

const 
  CallingConvToStr*: array[TCallingConvention, string] = ["", "stdcall", 
    "cdecl", "safecall", "syscall", "inline", "noinline", "fastcall",
    "closure", "noconv"]

type 
  TNodeKind* = enum # order is extremely important, because ranges are used
                    # to check whether a node belongs to a certain class
    nkNone,               # unknown node kind: indicates an error
                          # Expressions:
                          # Atoms:
    nkEmpty,              # the node is empty
    nkIdent,              # node is an identifier
    nkSym,                # node is a symbol
    nkType,               # node is used for its typ field

    nkCharLit,            # a character literal ''
    nkIntLit,             # an integer literal
    nkInt8Lit,
    nkInt16Lit,
    nkInt32Lit,
    nkInt64Lit,
    nkFloatLit,           # a floating point literal
    nkFloat32Lit,
    nkFloat64Lit,
    nkStrLit,             # a string literal ""
    nkRStrLit,            # a raw string literal r""
    nkTripleStrLit,       # a triple string literal """
    nkMetaNode,           # difficult to explan; represents itself
                          # (used for macros)
    nkNilLit,             # the nil literal
                          # end of atoms
    nkDotCall,            # used to temporarily flag a nkCall node; 
                          # this is used
                          # for transforming ``s.len`` to ``len(s)``
    nkCommand,            # a call like ``p 2, 4`` without parenthesis
    nkCall,               # a call like p(x, y) or an operation like +(a, b)
    nkCallStrLit,         # a call with a string literal 
                          # x"abc" has two sons: nkIdent, nkRStrLit
                          # x"""abc""" has two sons: nkIdent, nkTripleStrLit
    nkExprEqExpr,         # a named parameter with equals: ''expr = expr''
    nkExprColonExpr,      # a named parameter with colon: ''expr: expr''
    nkIdentDefs,          # a definition like `a, b: typeDesc = expr`
                          # either typeDesc or expr may be nil; used in
                          # formal parameters, var statements, etc.
    nkVarTuple,           # a ``var (a, b) = expr`` construct
    nkInfix,              # a call like (a + b)
    nkPrefix,             # a call like !a
    nkPostfix,            # something like a! (also used for visibility)
    nkPar,                # syntactic (); may be a tuple constructor
    nkCurly,              # syntactic {}
    nkBracket,            # syntactic []
    nkBracketExpr,        # an expression like a[i..j, k]
    nkPragmaExpr,         # an expression like a{.pragmas.}
    nkRange,              # an expression like i..j
    nkDotExpr,            # a.b
    nkCheckedFieldExpr,   # a.b, but b is a field that needs to be checked
    nkDerefExpr,          # a^
    nkIfExpr,             # if as an expression
    nkElifExpr,
    nkElseExpr,
    nkLambda,             # lambda expression
    nkAccQuoted,          # `a` as a node

    nkTableConstr,        # a table constructor {expr: expr}
    nkBind,               # ``bind expr`` node
    nkSymChoice,          # symbol choice node
    nkHiddenStdConv,      # an implicit standard type conversion
    nkHiddenSubConv,      # an implicit type conversion from a subtype
                          # to a supertype
    nkHiddenCallConv,     # an implicit type conversion via a type converter
    nkConv,               # a type conversion
    nkCast,               # a type cast
    nkAddr,               # a addr expression
    nkHiddenAddr,         # implicit address operator
    nkHiddenDeref,        # implicit ^ operator
    nkObjDownConv,        # down conversion between object types
    nkObjUpConv,          # up conversion between object types
    nkChckRangeF,         # range check for floats
    nkChckRange64,        # range check for 64 bit ints
    nkChckRange,          # range check for ints
    nkStringToCString,    # string to cstring
    nkCStringToString,    # cstring to string
    nkPassAsOpenArray,    # thing is passed as an open array
                          # end of expressions

    nkAsgn,               # a = b
    nkFastAsgn,           # internal node for a fast ``a = b``
                          # (no string copy) 
    nkGenericParams,      # generic parameters
    nkFormalParams,       # formal parameters
    nkOfInherit,          # inherited from symbol

    nkModule,             # the syntax tree of a module
    nkProcDef,            # a proc
    nkMethodDef,          # a method
    nkConverterDef,       # a converter
    nkMacroDef,           # a macro
    nkTemplateDef,        # a template
    nkIteratorDef,        # an iterator

    nkOfBranch,           # used inside case statements
                          # for (cond, action)-pairs
    nkElifBranch,         # used in if statements
    nkExceptBranch,       # an except section
    nkElse,               # an else part
    nkMacroStmt,          # a macro statement
    nkAsmStmt,            # an assembler block
    nkPragma,             # a pragma statement
    nkIfStmt,             # an if statement
    nkWhenStmt,           # a when statement
    nkForStmt,            # a for statement
    nkWhileStmt,          # a while statement
    nkCaseStmt,           # a case statement
    nkVarSection,         # a var section
    nkConstSection,       # a const section
    nkConstDef,           # a const definition
    nkTypeSection,        # a type section (consists of type definitions)
    nkTypeDef,            # a type definition
    nkYieldStmt,          # the yield statement as a tree
    nkTryStmt,            # a try statement
    nkFinally,            # a finally section
    nkRaiseStmt,          # a raise statement
    nkReturnStmt,         # a return statement
    nkBreakStmt,          # a break statement
    nkContinueStmt,       # a continue statement
    nkBlockStmt,          # a block statement
    nkDiscardStmt,        # a discard statement
    nkStmtList,           # a list of statements
    nkImportStmt,         # an import statement
    nkFromStmt,           # a from * import statement
    nkIncludeStmt,        # an include statement
    nkCommentStmt,        # a comment statement
    nkStmtListExpr,       # a statement list followed by an expr; this is used
                          # to allow powerful multi-line templates
    nkBlockExpr,          # a statement block ending in an expr; this is used
                          # to allowe powerful multi-line templates that open a
                          # temporary scope
    nkStmtListType,       # a statement list ending in a type; for macros
    nkBlockType,          # a statement block ending in a type; for macros
                          # types as syntactic trees:
    nkTypeOfExpr,
    nkObjectTy,
    nkTupleTy,
    nkRecList,            # list of object parts
    nkRecCase,            # case section of object
    nkRecWhen,            # when section of object
    nkRefTy,
    nkPtrTy,
    nkVarTy,
    nkDistinctTy,         # distinct type
    nkProcTy,
    nkEnumTy,
    nkEnumFieldDef,       # `ident = expr` in an enumeration
    nkReturnToken         # token used for interpretation
  TNodeKinds* = set[TNodeKind]

type 
  TSymFlag* = enum    # already 30 flags! 
    sfUsed,           # read access of sym (for warnings) or simply used
    sfStar,           # symbol has * visibility
    sfMinus,          # symbol has - visibility
    sfInInterface,    # symbol is in interface section declared
    sfFromGeneric,    # symbol is instantiation of a generic; this is needed 
                      # for symbol file generation; such symbols should always
                      # be written into the ROD file
    sfGlobal,         # symbol is at global scope

    sfForward,        # symbol is forward directed
    sfImportc,        # symbol is external; imported
    sfExportc,        # symbol is exported (under a specified name)
    sfVolatile,       # variable is volatile
    sfRegister,       # variable should be placed in a register
    sfPure,           # object is "pure" that means it has no type-information
    
    sfResult,         # variable is 'result' in proc
    sfNoSideEffect,   # proc has no side effects
    sfSideEffect,     # proc may have side effects; cannot prove it has none
    sfMainModule,     # module is the main module
    sfSystemModule,   # module is the system module
    sfNoReturn,       # proc never returns (an exit proc)
    sfAddrTaken,      # the variable's address is taken (ex- or implicitely)
    sfCompilerProc,   # proc is a compiler proc, that is a C proc that is
                      # needed for the code generator
    sfProcvar,        # proc can be passed to a proc var
    sfDiscriminant,   # field is a discriminant in a record/object
    sfDeprecated,     # symbol is deprecated
    sfInClosure,      # variable is accessed by a closure
    sfTypeCheck,      # wether macro parameters should be type checked
    sfCompileTime,    # proc can be evaluated at compile time
    sfThreadVar,      # variable is a thread variable
    sfMerge,          # proc can be merged with itself
    sfDeadCodeElim,   # dead code elimination for the module is turned on
    sfBorrow          # proc is borrowed

  TSymFlags* = set[TSymFlag]

  TTypeKind* = enum  # order is important!
                     # Don't forget to change hti.nim if you make a change here
                     # XXX put this into an include file to avoid this issue!
    tyNone, tyBool, tyChar,
    tyEmpty, tyArrayConstr, tyNil, tyExpr, tyStmt, tyTypeDesc,
    tyGenericInvokation, # ``T[a, b]`` for types to invoke
    tyGenericBody,       # ``T[a, b, body]`` last parameter is the body
    tyGenericInst,       # ``T[a, b, realInstance]`` instantiated generic type
    tyGenericParam,      # ``a`` in the example
    tyDistinct,
    tyEnum,
    tyOrdinal,           # misnamed: should become 'tyConstraint'
    tyArray,
    tyObject,
    tyTuple,
    tySet,
    tyRange,
    tyPtr, tyRef,
    tyVar,
    tySequence,
    tyProc,
    tyPointer, tyOpenArray,
    tyString, tyCString, tyForward,
    tyInt, tyInt8, tyInt16, tyInt32, tyInt64, # signed integers
    tyFloat, tyFloat32, tyFloat64, tyFloat128

  TTypeKinds* = set[TTypeKind]

  TNodeFlag* = enum
    nfNone,
    nfBase2,    # nfBase10 is default, so not needed
    nfBase8,
    nfBase16,
    nfAllConst, # used to mark complex expressions constant
    nfTransf,   # node has been transformed
    nfSem       # node has been checked for semantics

  TNodeFlags* = set[TNodeFlag]
  TTypeFlag* = enum 
    tfVarargs,        # procedure has C styled varargs
    tfNoSideEffect,   # procedure type does not allow side effects
    tfFinal,          # is the object final?
    tfAcyclic,        # type is acyclic (for GC optimization)
    tfEnumHasWholes,  # enum cannot be mapped into a range
    tfShallow         # type can be shallow copied on assignment

  TTypeFlags* = set[TTypeFlag]

  TSymKind* = enum # the different symbols (start with the prefix sk);
                   # order is important for the documentation generator!
    skUnknown,            # unknown symbol: used for parsing assembler blocks
                          # and first phase symbol lookup in generics
    skConditional,        # symbol for the preprocessor (may become obsolete)
    skDynLib,             # symbol represents a dynamic library; this is used
                          # internally; it does not exist in Nimrod code
    skParam,              # a parameter
    skGenericParam,       # a generic parameter; eq in ``proc x[eq=`==`]()``
    skTemp,               # a temporary variable (introduced by compiler)
    skModule,             # module identifier
    skType,               # a type
    skConst,              # a constant
    skVar,                # a variable
    skProc,               # a proc
    skMethod,             # a method
    skIterator,           # an iterator
    skConverter,          # a type converter
    skMacro,              # a macro
    skTemplate,           # a template; currently also misused for user-defined
                          # pragmas
    skField,              # a field in a record or object
    skEnumField,          # an identifier in an enum
    skForVar,             # a for loop variable
    skLabel,              # a label (for block statement)
    skStub                # symbol is a stub and not yet loaded from the ROD
                          # file (it is loaded on demand, which may
                          # mean: never)
  TSymKinds* = set[TSymKind]

  TMagic* = enum # symbols that require compiler magic:
    mNone, mDefined, mDefinedInScope, mLow, mHigh, mSizeOf, mIs, mEcho, 
    mUnaryLt, mSucc, 
    mPred, mInc, mDec, mOrd, mNew, mNewFinalize, mNewSeq, mLengthOpenArray, 
    mLengthStr, mLengthArray, mLengthSeq, mIncl, mExcl, mCard, mChr, mGCref, 
    mGCunref, mAddI, mSubI, mMulI, mDivI, mModI, mAddI64, mSubI64, mMulI64, 
    mDivI64, mModI64,
    mAddF64, mSubF64, mMulF64, mDivF64,
    mShrI, mShlI, mBitandI, mBitorI, mBitxorI, mMinI, mMaxI, 
    mShrI64, mShlI64, mBitandI64, mBitorI64, mBitxorI64, mMinI64, mMaxI64,
    mMinF64, mMaxF64, mAddU, mSubU, mMulU, 
    mDivU, mModU, mAddU64, mSubU64, mMulU64, mDivU64, mModU64, mEqI, mLeI,
    mLtI, 
    mEqI64, mLeI64, mLtI64, mEqF64, mLeF64, mLtF64, 
    mLeU, mLtU, mLeU64, mLtU64, 
    mEqEnum, mLeEnum, mLtEnum, mEqCh, mLeCh, mLtCh, mEqB, mLeB, mLtB, mEqRef, 
    mEqProc, mEqUntracedRef, mLePtr, mLtPtr, mEqCString, mXor, mUnaryMinusI, 
    mUnaryMinusI64, mAbsI, mAbsI64, mNot, 
    mUnaryPlusI, mBitnotI, mUnaryPlusI64, 
    mBitnotI64, mUnaryPlusF64, mUnaryMinusF64, mAbsF64, mZe8ToI, mZe8ToI64, 
    mZe16ToI, mZe16ToI64, mZe32ToI64, mZeIToI64, mToU8, mToU16, mToU32, 
    mToFloat, mToBiggestFloat, mToInt, mToBiggestInt, mCharToStr, mBoolToStr, 
    mIntToStr, mInt64ToStr, mFloatToStr, mCStrToStr, mStrToStr, mEnumToStr, 
    mAnd, mOr, mEqStr, mLeStr, mLtStr, mEqSet, mLeSet, mLtSet, mMulSet, 
    mPlusSet, mMinusSet, mSymDiffSet, mConStrStr, mConArrArr, mConArrT, 
    mConTArr, mConTT, mSlice, 
    mFields, mFieldPairs,
    mAppendStrCh, mAppendStrStr, mAppendSeqElem, 
    mInRange, mInSet, mRepr, mExit, mSetLengthStr, mSetLengthSeq, mAssert, 
    mSwap, mIsNil, mArrToSeq, mCopyStr, mCopyStrLast, mNewString, mReset, 
    mArray, mOpenArray, mRange, mSet, mSeq, 
    mOrdinal, mInt, mInt8, mInt16, mInt32, 
    mInt64, mFloat, mFloat32, mFloat64, mBool, mChar, mString, mCstring, 
    mPointer, mEmptySet, mIntSetBaseType, mNil, mExpr, mStmt, mTypeDesc, 
    mIsMainModule, mCompileDate, mCompileTime, mNimrodVersion, mNimrodMajor, 
    mNimrodMinor, mNimrodPatch, mCpuEndian, mHostOS, mHostCPU, mAppType, 
    mNaN, mInf, mNegInf, 
    mCompileOption, mCompileOptionArg,
    mNLen, mNChild, mNSetChild, mNAdd, mNAddMultiple, mNDel, mNKind, 
    mNIntVal, mNFloatVal, mNSymbol, mNIdent, mNGetType, mNStrVal, mNSetIntVal, 
    mNSetFloatVal, mNSetSymbol, mNSetIdent, mNSetType, mNSetStrVal, 
    mNNewNimNode, mNCopyNimNode, mNCopyNimTree, mStrToIdent, mIdentToStr, 
    mEqIdent, mEqNimrodNode, mNHint, mNWarning, mNError

type 
  PNode* = ref TNode
  PNodePtr* = ptr PNode
  TNodeSeq* = seq[PNode]
  PType* = ref TType
  PSym* = ref TSym
  TNode*{.acyclic, final.} = object # on a 32bit machine, this takes 32 bytes
    typ*: PType
    comment*: string
    info*: TLineInfo
    flags*: TNodeFlags
    case Kind*: TNodeKind
    of nkCharLit..nkInt64Lit: 
      intVal*: biggestInt
    of nkFloatLit..nkFloat64Lit: 
      floatVal*: biggestFloat
    of nkStrLit..nkTripleStrLit: 
      strVal*: string
    of nkSym: 
      sym*: PSym
    of nkIdent: 
      ident*: PIdent
    else: 
      sons*: TNodeSeq
  
  TSymSeq* = seq[PSym]
  TStrTable* = object         # a table[PIdent] of PSym
    counter*: int
    data*: TSymSeq
  
  # -------------- backend information -------------------------------
  TLocKind* = enum 
    locNone,                  # no location
    locTemp,                  # temporary location
    locLocalVar,              # location is a local variable
    locGlobalVar,             # location is a global variable
    locParam,                 # location is a parameter
    locField,                 # location is a record field
    locArrayElem,             # location is an array element
    locExpr,                  # "location" is really an expression
    locProc,                  # location is a proc (an address of a procedure)
    locData,                  # location is a constant
    locCall,                  # location is a call expression
    locOther                  # location is something other
  TLocFlag* = enum 
    lfIndirect,               # backend introduced a pointer
    lfParamCopy,              # backend introduced a parameter copy (LLVM)
    lfNoDeepCopy,             # no need for a deep copy
    lfNoDecl,                 # do not declare it in C
    lfDynamicLib,             # link symbol to dynamic library
    lfExportLib,              # export symbol for dynamic library generation
    lfHeader                  # include header file for symbol
  TStorageLoc* = enum 
    OnUnknown,                # location is unknown (stack, heap or static)
    OnStack,                  # location is on hardware stack
    OnHeap                    # location is on heap or global
                              # (reference counting needed)
  TLocFlags* = set[TLocFlag]
  TLoc*{.final.} = object     
    k*: TLocKind              # kind of location
    s*: TStorageLoc
    flags*: TLocFlags         # location's flags
    t*: PType                 # type of location
    r*: PRope                 # rope value of location (code generators)
    a*: int                   # location's "address", i.e. slot for temporaries

  # ---------------- end of backend information ------------------------------

  TLibKind* = enum 
    libHeader, libDynamic
  TLib* = object of lists.TListEntry # also misused for headers!
    kind*: TLibKind
    generated*: bool          # needed for the backends:
    name*: PRope
    path*: PNode              # can be a string literal!
    

  PLib* = ref TLib
  TSym* = object of TIdObj
    kind*: TSymKind
    magic*: TMagic
    typ*: PType
    name*: PIdent
    info*: TLineInfo
    owner*: PSym
    flags*: TSymFlags
    tab*: TStrTable           # interface table for modules
    ast*: PNode               # syntax tree of proc, iterator, etc.:
                              # the whole proc including header; this is used
                              # for easy generation of proper error messages
                              # for variant record fields the discriminant
                              # expression
    options*: TOptions
    position*: int            # used for many different things:
                              # for enum fields its position;
                              # for fields its offset
                              # for parameters its position
                              # for a conditional:
                              # 1 iff the symbol is defined, else 0
                              # (or not in symbol table)
    offset*: int              # offset of record field
    loc*: TLoc
    annex*: PLib              # additional fields (seldom used, so we use a
                              # reference to another object to safe space)
  
  TTypeSeq* = seq[PType]
  TType* = object of TIdObj   # types are identical iff they have the
                              # same id; there may be multiple copies of a type
                              # in memory!
    kind*: TTypeKind          # kind of type
    sons*: TTypeSeq           # base types, etc.
    n*: PNode                 # node for types:
                              # for range types a nkRange node
                              # for record types a nkRecord node
                              # for enum types a list of symbols
                              # else: unused
    flags*: TTypeFlags        # flags of the type
    callConv*: TCallingConvention # for procs
    owner*: PSym              # the 'owner' of the type
    sym*: PSym                # types have the sym associated with them
                              # it is used for converting types to strings
    size*: BiggestInt         # the size of the type in bytes
                              # -1 means that the size is unkwown
    align*: int               # the type's alignment requirements
    containerID*: int         # used for type checking of generics
    loc*: TLoc

  TPair*{.final.} = object 
    key*, val*: PObject

  TPairSeq* = seq[TPair]
  TTable*{.final.} = object   # the same as table[PObject] of PObject
    counter*: int
    data*: TPairSeq

  TIdPair*{.final.} = object 
    key*: PIdObj
    val*: PObject

  TIdPairSeq* = seq[TIdPair]
  TIdTable*{.final.} = object # the same as table[PIdent] of PObject
    counter*: int
    data*: TIdPairSeq

  TIdNodePair*{.final.} = object 
    key*: PIdObj
    val*: PNode

  TIdNodePairSeq* = seq[TIdNodePair]
  TIdNodeTable*{.final.} = object # the same as table[PIdObj] of PNode
    counter*: int
    data*: TIdNodePairSeq

  TNodePair*{.final.} = object 
    h*: THash                 # because it is expensive to compute!
    key*: PNode
    val*: int

  TNodePairSeq* = seq[TNodePair]
  TNodeTable*{.final.} = object # the same as table[PNode] of int;
                                # nodes are compared by structure!
    counter*: int
    data*: TNodePairSeq

  TObjectSeq* = seq[PObject]
  TObjectSet*{.final.} = object 
    counter*: int
    data*: TObjectSeq

# BUGFIX: a module is overloadable so that a proc can have the
# same name as an imported module. This is necessary because of
# the poor naming choices in the standard library.

const 
  OverloadableSyms* = {skProc, skMethod, skIterator, skConverter, skModule}

  GenericTypes*: TTypeKinds = {tyGenericInvokation, tyGenericBody, 
    tyGenericParam}
  StructuralEquivTypes*: TTypeKinds = {tyArrayConstr, tyNil, tyTuple, tyArray, 
    tySet, tyRange, tyPtr, tyRef, tyVar, tySequence, tyProc, tyOpenArray}
  ConcreteTypes*: TTypeKinds = { # types of the expr that may occur in::
                                 # var x = expr
    tyBool, tyChar, tyEnum, tyArray, tyObject, 
    tySet, tyTuple, tyRange, tyPtr, tyRef, tyVar, tySequence, tyProc,
    tyPointer, 
    tyOpenArray, tyString, tyCString, tyInt..tyInt64, tyFloat..tyFloat128} 
  
  ConstantDataTypes*: TTypeKinds = {tyArray, tySet, tyTuple}
  ExportableSymKinds* = {skVar, skConst, skProc, skMethod, skType, skIterator, 
    skMacro, skTemplate, skConverter, skStub}
  PersistentNodeFlags*: TNodeFlags = {nfBase2, nfBase8, nfBase16, nfAllConst}
  namePos* = 0
  genericParamsPos* = 1
  paramsPos* = 2
  pragmasPos* = 3
  codePos* = 4
  resultPos* = 5
  dispatcherPos* = 6

var gId*: int

proc getID*(): int {.inline.}
proc setID*(id: int) {.inline.}
proc IDsynchronizationPoint*(idRange: int)

# creator procs:
proc NewSym*(symKind: TSymKind, Name: PIdent, owner: PSym): PSym
proc NewType*(kind: TTypeKind, owner: PSym): PType
proc newNode*(kind: TNodeKind): PNode
proc newIntNode*(kind: TNodeKind, intVal: BiggestInt): PNode
proc newIntTypeNode*(kind: TNodeKind, intVal: BiggestInt, typ: PType): PNode
proc newFloatNode*(kind: TNodeKind, floatVal: BiggestFloat): PNode
proc newStrNode*(kind: TNodeKind, strVal: string): PNode
proc newIdentNode*(ident: PIdent, info: TLineInfo): PNode
proc newSymNode*(sym: PSym): PNode
proc newNodeI*(kind: TNodeKind, info: TLineInfo): PNode
proc newNodeIT*(kind: TNodeKind, info: TLineInfo, typ: PType): PNode
proc initStrTable*(x: var TStrTable)
proc initTable*(x: var TTable)
proc initIdTable*(x: var TIdTable)
proc initObjectSet*(x: var TObjectSet)
proc initIdNodeTable*(x: var TIdNodeTable)
proc initNodeTable*(x: var TNodeTable)
  
# copy procs:
proc copyType*(t: PType, owner: PSym, keepId: bool): PType
proc copySym*(s: PSym, keepId: bool = false): PSym
proc assignType*(dest, src: PType)
proc copyStrTable*(dest: var TStrTable, src: TStrTable)
proc copyTable*(dest: var TTable, src: TTable)
proc copyObjectSet*(dest: var TObjectSet, src: TObjectSet)
proc copyIdTable*(dest: var TIdTable, src: TIdTable)
proc sonsLen*(n: PNode): int {.inline.}
proc sonsLen*(n: PType): int {.inline.}
proc lastSon*(n: PNode): PNode {.inline.}
proc lastSon*(n: PType): PType {.inline.}
proc newSons*(father: PNode, length: int)
proc newSons*(father: PType, length: int)
proc addSon*(father, son: PNode)
proc addSon*(father, son: PType)
proc delSon*(father: PNode, idx: int)
proc hasSonWith*(n: PNode, kind: TNodeKind): bool
proc hasSubnodeWith*(n: PNode, kind: TNodeKind): bool
proc replaceSons*(n: PNode, oldKind, newKind: TNodeKind)
proc copyNode*(src: PNode): PNode
  # does not copy its sons!
proc copyTree*(src: PNode): PNode
  # does copy its sons!

proc discardSons*(father: PNode)

var emptyNode* = newNode(nkEmpty)
# There is a single empty node that is shared! Do not overwrite it!


const                         # for all kind of hash tables:
  GrowthFactor* = 2           # must be power of 2, > 0
  StartSize* = 8              # must be power of 2, > 0

proc SameValue*(a, b: PNode): bool
  # a, b are literals
proc leValue*(a, b: PNode): bool
  # a <= b? a, b are literals
proc ValueToString*(a: PNode): string
 
# ------------- efficient integer sets -------------------------------------
type 
  TBitScalar* = int

const 
  InitIntSetSize* = 8         # must be a power of two!
  TrunkShift* = 9
  BitsPerTrunk* = 1 shl TrunkShift # needs to be a power of 2 and
                                   # divisible by 64
  TrunkMask* = BitsPerTrunk - 1
  IntsPerTrunk* = BitsPerTrunk div (sizeof(TBitScalar) * 8)
  IntShift* = 5 + ord(sizeof(TBitScalar) == 8) # 5 or 6, depending on int width
  IntMask* = 1 shl IntShift - 1

type 
  PTrunk* = ref TTrunk
  TTrunk*{.final.} = object 
    next*: PTrunk             # all nodes are connected with this pointer
    key*: int                 # start address at bit 0
    bits*: array[0..IntsPerTrunk - 1, TBitScalar] # a bit vector
  
  TTrunkSeq* = seq[PTrunk]
  TIntSet*{.final.} = object 
    counter*, max*: int
    head*: PTrunk
    data*: TTrunkSeq


proc IntSetContains*(s: TIntSet, key: int): bool
proc IntSetIncl*(s: var TIntSet, key: int)
proc IntSetExcl*(s: var TIntSet, key: int)
proc IntSetInit*(s: var TIntSet)
proc IntSetContainsOrIncl*(s: var TIntSet, key: int): bool
const 
  debugIds* = false

proc registerID*(id: PIdObj)
# implementation

var usedIds: TIntSet

proc registerID(id: PIdObj) = 
  if debugIDs: 
    if (id.id == - 1) or IntSetContainsOrIncl(usedIds, id.id): 
      InternalError("ID already used: " & $(id.id))
  
proc getID(): int = 
  result = gId
  inc(gId)

proc setId(id: int) = 
  gId = max(gId, id + 1)

proc IDsynchronizationPoint(idRange: int) = 
  gId = (gId div IdRange + 1) * IdRange + 1

proc leValue(a, b: PNode): bool = 
  # a <= b?
  result = false
  case a.kind
  of nkCharLit..nkInt64Lit: 
    if b.kind in {nkCharLit..nkInt64Lit}: result = a.intVal <= b.intVal
  of nkFloatLit..nkFloat64Lit: 
    if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal <= b.floatVal
  of nkStrLit..nkTripleStrLit: 
    if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal <= b.strVal
  else: InternalError(a.info, "leValue")
  
proc SameValue(a, b: PNode): bool = 
  result = false
  case a.kind
  of nkCharLit..nkInt64Lit: 
    if b.kind in {nkCharLit..nkInt64Lit}: result = a.intVal == b.intVal
  of nkFloatLit..nkFloat64Lit: 
    if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal == b.floatVal
  of nkStrLit..nkTripleStrLit: 
    if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal == b.strVal
  else: InternalError(a.info, "SameValue")
  
proc ValueToString(a: PNode): string = 
  case a.kind
  of nkCharLit..nkInt64Lit: result = $(a.intVal)
  of nkFloatLit, nkFloat32Lit, nkFloat64Lit: result = $(a.floatVal)
  of nkStrLit..nkTripleStrLit: result = a.strVal
  else: 
    InternalError(a.info, "valueToString")
    result = ""

proc copyStrTable(dest: var TStrTable, src: TStrTable) = 
  dest.counter = src.counter
  if isNil(src.data): return 
  setlen(dest.data, len(src.data))
  for i in countup(0, high(src.data)): dest.data[i] = src.data[i]
  
proc copyIdTable(dest: var TIdTable, src: TIdTable) = 
  dest.counter = src.counter
  if isNil(src.data): return 
  newSeq(dest.data, len(src.data))
  for i in countup(0, high(src.data)): dest.data[i] = src.data[i]
  
proc copyTable(dest: var TTable, src: TTable) = 
  dest.counter = src.counter
  if isNil(src.data): return 
  setlen(dest.data, len(src.data))
  for i in countup(0, high(src.data)): dest.data[i] = src.data[i]
  
proc copyObjectSet(dest: var TObjectSet, src: TObjectSet) = 
  dest.counter = src.counter
  if isNil(src.data): return 
  setlen(dest.data, len(src.data))
  for i in countup(0, high(src.data)): dest.data[i] = src.data[i]
  
proc discardSons(father: PNode) = 
  father.sons = nil

proc newNode(kind: TNodeKind): PNode = 
  new(result)
  result.kind = kind
  #result.info = UnknownLineInfo() inlined:
  result.info.fileIndex = int32(- 1)
  result.info.col = int16(- 1)
  result.info.line = int16(- 1)

proc newIntNode(kind: TNodeKind, intVal: BiggestInt): PNode = 
  result = newNode(kind)
  result.intVal = intVal

proc newIntTypeNode(kind: TNodeKind, intVal: BiggestInt, typ: PType): PNode = 
  result = newIntNode(kind, intVal)
  result.typ = typ

proc newFloatNode(kind: TNodeKind, floatVal: BiggestFloat): PNode = 
  result = newNode(kind)
  result.floatVal = floatVal

proc newStrNode(kind: TNodeKind, strVal: string): PNode = 
  result = newNode(kind)
  result.strVal = strVal

proc newIdentNode(ident: PIdent, info: TLineInfo): PNode = 
  result = newNode(nkIdent)
  result.ident = ident
  result.info = info

proc newSymNode(sym: PSym): PNode = 
  result = newNode(nkSym)
  result.sym = sym
  result.typ = sym.typ
  result.info = sym.info

proc newSymNode*(sym: PSym, info: TLineInfo): PNode = 
  result = newNode(nkSym)
  result.sym = sym
  result.typ = sym.typ
  result.info = info

proc newNodeI(kind: TNodeKind, info: TLineInfo): PNode = 
  result = newNode(kind)
  result.info = info

proc newNodeIT(kind: TNodeKind, info: TLineInfo, typ: PType): PNode = 
  result = newNode(kind)
  result.info = info
  result.typ = typ

proc NewType(kind: TTypeKind, owner: PSym): PType = 
  new(result)
  result.kind = kind
  result.owner = owner
  result.size = - 1
  result.align = 2            # default alignment
  result.id = getID()
  if debugIds: 
    RegisterId(result)        
  #if result.id < 2000 then
  #  MessageOut(typeKindToStr[kind] & ' has id: ' & toString(result.id))
  
proc assignType(dest, src: PType) = 
  dest.kind = src.kind
  dest.flags = src.flags
  dest.callConv = src.callConv
  dest.n = src.n
  dest.size = src.size
  dest.align = src.align
  dest.containerID = src.containerID
  newSons(dest, sonsLen(src))
  for i in countup(0, sonsLen(src) - 1): dest.sons[i] = src.sons[i]
  
proc copyType(t: PType, owner: PSym, keepId: bool): PType = 
  result = newType(t.Kind, owner)
  assignType(result, t)
  if keepId: 
    result.id = t.id
  else: 
    result.id = getID()
    if debugIds: RegisterId(result)
  result.sym = t.sym          # backend-info should not be copied
  
proc copySym(s: PSym, keepId: bool = false): PSym = 
  result = newSym(s.kind, s.name, s.owner)
  result.ast = nil            # BUGFIX; was: s.ast which made problems
  result.info = s.info
  result.typ = s.typ
  if keepId: 
    result.id = s.id
  else: 
    result.id = getID()
    if debugIds: RegisterId(result)
  result.flags = s.flags
  result.magic = s.magic
  copyStrTable(result.tab, s.tab)
  result.options = s.options
  result.position = s.position
  result.loc = s.loc
  result.annex = s.annex      # BUGFIX
  
proc NewSym(symKind: TSymKind, Name: PIdent, owner: PSym): PSym = 
  # generates a symbol and initializes the hash field too
  new(result)
  result.Name = Name
  result.Kind = symKind
  result.flags = {}
  result.info = UnknownLineInfo()
  result.options = gOptions
  result.owner = owner
  result.offset = - 1
  result.id = getID()
  if debugIds: 
    RegisterId(result)
  #if result.id < 2000:
  #  MessageOut(name.s & " has id: " & toString(result.id))
  
proc initStrTable(x: var TStrTable) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc initTable(x: var TTable) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc initIdTable(x: var TIdTable) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc initObjectSet(x: var TObjectSet) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc initIdNodeTable(x: var TIdNodeTable) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc initNodeTable(x: var TNodeTable) = 
  x.counter = 0
  newSeq(x.data, startSize)

proc sonsLen(n: PType): int = 
  if isNil(n.sons): result = 0
  else: result = len(n.sons)
  
proc newSons(father: PType, length: int) = 
  if isNil(father.sons): father.sons = @[]
  setlen(father.sons, len(father.sons) + length)

proc addSon(father, son: PType) = 
  if isNil(father.sons): father.sons = @[]
  add(father.sons, son)
  #assert((father.kind != tyGenericInvokation) or (son.kind != tyGenericInst))

proc sonsLen(n: PNode): int = 
  if isNil(n.sons): result = 0
  else: result = len(n.sons)
  
proc len*(n: PNode): int {.inline.} =
  if isNil(n.sons): result = 0
  else: result = len(n.sons)
  
proc safeLen*(n: PNode): int {.inline.} =
  ## works even for leaves.
  if n.kind in {nkNone..nkNilLit} or isNil(n.sons): result = 0
  else: result = len(n.sons)
  
proc add*(father, son: PNode) =
  assert son != nil
  if isNil(father.sons): father.sons = @[]
  add(father.sons, son)  
  
proc `[]`*(n: PNode, i: int): PNode {.inline.} =
  result = n.sons[i]
  
proc newSons(father: PNode, length: int) = 
  if isNil(father.sons): father.sons = @[]
  setlen(father.sons, len(father.sons) + length)

proc addSon(father, son: PNode) = 
  assert son != nil
  if isNil(father.sons): father.sons = @[]
  add(father.sons, son)

proc delSon(father: PNode, idx: int) = 
  if isNil(father.sons): return 
  var length = sonsLen(father)
  for i in countup(idx, length - 2): father.sons[i] = father.sons[i + 1]
  setlen(father.sons, length - 1)

proc copyNode(src: PNode): PNode = 
  # does not copy its sons!
  if src == nil: 
    return nil
  result = newNode(src.kind)
  result.info = src.info
  result.typ = src.typ
  result.flags = src.flags * PersistentNodeFlags
  case src.Kind
  of nkCharLit..nkInt64Lit: result.intVal = src.intVal
  of nkFloatLit, nkFloat32Lit, nkFloat64Lit: result.floatVal = src.floatVal
  of nkSym: result.sym = src.sym
  of nkIdent: result.ident = src.ident
  of nkStrLit..nkTripleStrLit: result.strVal = src.strVal
  else: nil

proc shallowCopy*(src: PNode): PNode = 
  # does not copy its sons, but provides space for them:
  if src == nil: return nil
  result = newNode(src.kind)
  result.info = src.info
  result.typ = src.typ
  result.flags = src.flags * PersistentNodeFlags
  case src.Kind
  of nkCharLit..nkInt64Lit: result.intVal = src.intVal
  of nkFloatLit, nkFloat32Lit, nkFloat64Lit: result.floatVal = src.floatVal
  of nkSym: result.sym = src.sym
  of nkIdent: result.ident = src.ident
  of nkStrLit..nkTripleStrLit: result.strVal = src.strVal
  else: newSons(result, sonsLen(src))

proc copyTree(src: PNode): PNode = 
  # copy a whole syntax tree; performs deep copying
  if src == nil: 
    return nil
  result = newNode(src.kind)
  result.info = src.info
  result.typ = src.typ
  result.flags = src.flags * PersistentNodeFlags
  case src.Kind
  of nkCharLit..nkInt64Lit: result.intVal = src.intVal
  of nkFloatLit, nkFloat32Lit, nkFloat64Lit: result.floatVal = src.floatVal
  of nkSym: result.sym = src.sym
  of nkIdent: result.ident = src.ident
  of nkStrLit..nkTripleStrLit: result.strVal = src.strVal
  else: 
    result.sons = nil
    newSons(result, sonsLen(src))
    for i in countup(0, sonsLen(src) - 1): 
      result.sons[i] = copyTree(src.sons[i])
  
proc lastSon(n: PNode): PNode = 
  result = n.sons[sonsLen(n) - 1]

proc lastSon(n: PType): PType = 
  result = n.sons[sonsLen(n) - 1]

proc hasSonWith(n: PNode, kind: TNodeKind): bool = 
  for i in countup(0, sonsLen(n) - 1): 
    if n.sons[i].kind == kind: 
      return true
  result = false

proc hasSubnodeWith(n: PNode, kind: TNodeKind): bool = 
  case n.kind
  of nkEmpty..nkNilLit: result = n.kind == kind
  else: 
    for i in countup(0, sonsLen(n) - 1): 
      if (n.sons[i].kind == kind) or hasSubnodeWith(n.sons[i], kind): 
        return true
    result = false

proc replaceSons(n: PNode, oldKind, newKind: TNodeKind) = 
  for i in countup(0, sonsLen(n) - 1): 
    if n.sons[i].kind == oldKind: n.sons[i].kind = newKind
  
proc sonsNotNil(n: PNode): bool = 
  for i in countup(0, sonsLen(n) - 1): 
    if n.sons[i] == nil: 
      return false
  result = true

proc getInt*(a: PNode): biggestInt = 
  case a.kind
  of nkIntLit..nkInt64Lit: result = a.intVal
  else: 
    internalError(a.info, "getInt")
    result = 0

proc getFloat*(a: PNode): biggestFloat = 
  case a.kind
  of nkFloatLit..nkFloat64Lit: result = a.floatVal
  else: 
    internalError(a.info, "getFloat")
    result = 0.0

proc getStr*(a: PNode): string = 
  case a.kind
  of nkStrLit..nkTripleStrLit: result = a.strVal
  else: 
    internalError(a.info, "getStr")
    result = ""

proc getStrOrChar*(a: PNode): string = 
  case a.kind
  of nkStrLit..nkTripleStrLit: result = a.strVal
  of nkCharLit: result = chr(int(a.intVal)) & ""
  else: 
    internalError(a.info, "getStrOrChar")
    result = ""
  
proc mustRehash(length, counter: int): bool {.inline.} = 
  assert(length > counter)
  result = (length * 2 < counter * 3) or (length - counter < 4)

proc nextTry(h, maxHash: THash): THash {.inline.} = 
  result = ((5 * h) + 1) and maxHash 
  # For any initial h in range(maxHash), repeating that maxHash times
  # generates each int in range(maxHash) exactly once (see any text on
  # random-number generation for proof).
  
proc IntSetInit(s: var TIntSet) = 
  newSeq(s.data, InitIntSetSize)
  s.max = InitIntSetSize - 1
  s.counter = 0
  s.head = nil

proc IntSetGet(t: TIntSet, key: int): PTrunk = 
  var h = key and t.max
  while t.data[h] != nil: 
    if t.data[h].key == key: 
      return t.data[h]
    h = nextTry(h, t.max)
  result = nil

proc IntSetRawInsert(t: TIntSet, data: var TTrunkSeq, desc: PTrunk) = 
  var h = desc.key and t.max
  while data[h] != nil: 
    assert(data[h] != desc)
    h = nextTry(h, t.max)
  assert(data[h] == nil)
  data[h] = desc

proc IntSetEnlarge(t: var TIntSet) = 
  var 
    n: TTrunkSeq
    oldMax: int
  oldMax = t.max
  t.max = ((t.max + 1) * 2) - 1
  newSeq(n, t.max + 1)
  for i in countup(0, oldmax): 
    if t.data[i] != nil: IntSetRawInsert(t, n, t.data[i])
  swap(t.data, n)

proc IntSetPut(t: var TIntSet, key: int): PTrunk = 
  var h = key and t.max
  while t.data[h] != nil: 
    if t.data[h].key == key: 
      return t.data[h]
    h = nextTry(h, t.max)
  if mustRehash(t.max + 1, t.counter): IntSetEnlarge(t)
  inc(t.counter)
  h = key and t.max
  while t.data[h] != nil: h = nextTry(h, t.max)
  assert(t.data[h] == nil)
  new(result)
  result.next = t.head
  result.key = key
  t.head = result
  t.data[h] = result

proc IntSetContains(s: TIntSet, key: int): bool = 
  var 
    u: TBitScalar
    t: PTrunk
  t = IntSetGet(s, `shr`(key, TrunkShift))
  if t != nil: 
    u = key and TrunkMask
    result = (t.bits[`shr`(u, IntShift)] and `shl`(1, u and IntMask)) != 0
  else: 
    result = false
  
proc IntSetIncl(s: var TIntSet, key: int) = 
  var 
    u: TBitScalar
    t: PTrunk
  t = IntSetPut(s, `shr`(key, TrunkShift))
  u = key and TrunkMask
  t.bits[`shr`(u, IntShift)] = t.bits[`shr`(u, IntShift)] or
      `shl`(1, u and IntMask)

proc IntSetExcl(s: var TIntSet, key: int) = 
  var 
    u: TBitScalar
    t: PTrunk
  t = IntSetGet(s, `shr`(key, TrunkShift))
  if t != nil: 
    u = key and TrunkMask
    t.bits[`shr`(u, IntShift)] = t.bits[`shr`(u, IntShift)] and
        not `shl`(1, u and IntMask)

proc IntSetContainsOrIncl(s: var TIntSet, key: int): bool = 
  var 
    u: TBitScalar
    t: PTrunk
  t = IntSetGet(s, `shr`(key, TrunkShift))
  if t != nil: 
    u = key and TrunkMask
    result = (t.bits[`shr`(u, IntShift)] and `shl`(1, u and IntMask)) != 0
    if not result: 
      t.bits[`shr`(u, IntShift)] = t.bits[`shr`(u, IntShift)] or
          `shl`(1, u and IntMask)
  else: 
    IntSetIncl(s, key)
    result = false

if debugIDs: IntSetInit(usedIds)