Add conditional type narrowing

[heshanpadmasiri]

Needs #84 . We need to do this before semantic analysis after we have created the CFG

[heshanpadmasiri]

Conditional type narrowing

• Relevant section of the spec
• At expression level we need to know the type of the expression, thus needs to be done after type resolution
  • But this needs to be done before semantic analysis since it do the type checking of the code.
  • We will also need to mutate symbols in the AST while doing this so semantic analysis will work as is
• Having control flow information with us will be useful so probably we should do this after CFG
  • Otherwise this will need to "create" a CFG of it's own

Design

• I think the way to do this is with a binding chain

  type binding struct {
    // this is the reference to the underlying symbol
    ref SymbolRef
    bindingSymbol *model.Symbol
    prev *binding
  }

• Analyze expression will take a binding chain and return a expression effect

  type expressionEffect struct {
    ifTrue *binding
    // For expression that are not conditional both will be same
    ifFalse *binding
  }

  • When we have a var ref we'll go over the binding chain until we find the nearest binding to the symbol

• Same is true for statements. This needs to handle cases like return, it will bind the type to never

  type statementEffect struct {
    // this is nil for statements like return/ panic which will not effect the bindings?
    // -- I think the CFG graph already handle them properly but just in case
    binding *binding
  }

• We can implement type merging on top of CFG, we analyze all the parent (only those with forward edges), take their statement effects and merge them

  • First we need to group all the binding symbols by the underlying symbol (ref in binding). Then we take the type of each binding symbols type and intersect it to form the type of the new symbol.
    • One optimization would be to keep track if in any branch the bindingSymbol is a narrowed symbol. If that is not the case we can simply bind it back to original symbol without the need for narrowing.
    • For each binding chain we need to take the nearest binding

• We'll introduce a new Symbol kind for narrowed symbols

  • Do we need this to be public in model? I don't think reset of the code needs to know what kind of symbol this is

  • All operations except type will be deligated to the underlying symbol

    type NarrowedSymbol struct {
      ty Semtype
    
      // underlying is the reference to the "original" un-narrowed symbol. Repeated narrowings should point to the same
      // underlying symbol and this would allow us to add un-narrowing symbol easily
      underlying SymbolRef
    }

Statements/Expressions with special effects

1. Type check expression (E is T)
   • if E is a var-ref then create a expression Effect with intersection of T and current type of var-ref
     • Note this can create nested bindings
2. Assignment

• This should "unnarrow" the value. I think we can do this by adding a new binding to the chain?

Refactorings

• I think it is better to make the fact AST nodes have *SymbolRef explicit instead of having *Symbol
  • Maybe then we can make it no longer a pointer as well?
• CFG should distinguish between back edges. This would make things much simpler for both declaration analysis and conditional type narrowing
  • In both cases we can ignore the back edges