From e5ae4ea1288a555c4019dad43ee27e960eec46b9 Mon Sep 17 00:00:00 2001 From: Mel Date: Tue, 12 Jul 2022 00:29:56 +0200 Subject: Extract scopes and scope chain from compiler --- pkg/lang/compiler/compiler.go | 33 ++--- pkg/lang/compiler/scope/scope_chain.go | 191 +++++++++++++++++++++++++ pkg/lang/compiler/scope/scopes.go | 50 +++++++ pkg/lang/compiler/scope/symbol.go | 65 +++++++++ pkg/lang/compiler/scope_chain.go | 254 --------------------------------- pkg/lang/compiler/symbol.go | 39 ----- 6 files changed, 323 insertions(+), 309 deletions(-) create mode 100644 pkg/lang/compiler/scope/scope_chain.go create mode 100644 pkg/lang/compiler/scope/scopes.go create mode 100644 pkg/lang/compiler/scope/symbol.go delete mode 100644 pkg/lang/compiler/scope_chain.go delete mode 100644 pkg/lang/compiler/symbol.go (limited to 'pkg') diff --git a/pkg/lang/compiler/compiler.go b/pkg/lang/compiler/compiler.go index 728dec1..ad37ded 100644 --- a/pkg/lang/compiler/compiler.go +++ b/pkg/lang/compiler/compiler.go @@ -3,6 +3,7 @@ package compiler import ( "fmt" "jinx/pkg/lang/ast" + "jinx/pkg/lang/compiler/scope" "jinx/pkg/lang/vm/code" ) @@ -11,14 +12,14 @@ type Compiler struct { funcs []*code.Builder - scopes ScopeChain + scopes scope.ScopeChain } func New(ast ast.Program) *Compiler { return &Compiler{ ast: ast, funcs: make([]*code.Builder, 0), - scopes: NewScopeChain(), + scopes: scope.NewScopeChain(), } } @@ -114,7 +115,7 @@ func (comp *Compiler) compileFnDeclStmt(t *code.Builder, fnDeclStmt ast.StmtFnDe symbol := comp.scopes.GetFunction(symbolID) - marker = symbol.data.marker + marker = symbol.Data().Marker() } else { return fmt.Errorf("function %s already declared", fnDeclStmt.Name.Value) } @@ -382,8 +383,8 @@ func (comp *Compiler) compileForInStmt(t *code.Builder, forInStmt ast.StmtForIn) func (comp *Compiler) compileReturnStmt(t *code.Builder, returnStmt ast.StmtReturn) error { // Check that we are in fact in a function functionScope := comp.scopes.CurrentFunction() - if functionScope.data.(ScopeFunction).IsRootScope() { - return fmt.Errorf("can't return when not inside a function" + functionScope.data.(ScopeFunction).unit.String()) + if functionScope.IsRootScope() { + return fmt.Errorf("can't return when not inside a function") } if returnStmt.Value.IsEmpty() { @@ -491,8 +492,8 @@ func (comp *Compiler) compileAssignExpr(t *code.Builder, expr ast.ExprBinary) er return fmt.Errorf("variable %s not declared", name) } - if symbolId.symbolKind != SymbolKindVariable { - return fmt.Errorf("can't assign to a %v", symbolId.symbolKind) + if symbolId.SymbolKind() != scope.SymbolKindVariable { + return fmt.Errorf("can't assign to a %v", symbolId.SymbolKind()) } symbol := comp.scopes.GetVariable(symbolId) @@ -502,7 +503,7 @@ func (comp *Compiler) compileAssignExpr(t *code.Builder, expr ast.ExprBinary) er } t.AppendOp(code.OpSetLocal) - t.AppendInt(int64(symbol.data.localIndex)) + t.AppendInt(int64(symbol.Data().LocalIndex())) return nil } @@ -587,24 +588,24 @@ func (comp *Compiler) compileIdentExpr(t *code.Builder, expr ast.ExprIdent) erro } // TODO: Add other ways how the symbol should be fetched. (local, env, global, etc.) - switch symbolId.symbolKind { - case SymbolKindVariable: + switch symbolId.SymbolKind() { + case scope.SymbolKindVariable: symbol := comp.scopes.GetVariable(symbolId) t.AppendOp(code.OpGetLocal) - t.AppendInt(int64(symbol.data.localIndex)) - case SymbolKindFunction: + t.AppendInt(int64(symbol.Data().LocalIndex())) + case scope.SymbolKindFunction: symbol := comp.scopes.GetFunction(symbolId) t.AppendOp(code.OpPushFunction) - t.AppendMarkerReference(symbol.data.marker) + t.AppendMarkerReference(symbol.Data().Marker()) - if symbol.data.args != 0 { + if symbol.Data().Args() != 0 { t.AppendOp(code.OpSetArgCount) - t.AppendInt(int64(symbol.data.args)) + t.AppendInt(int64(symbol.Data().Args())) } default: - panic(fmt.Errorf("unknown symbol kind: %v", symbolId.symbolKind)) + panic(fmt.Errorf("unknown symbol kind: %v", symbolId.SymbolKind())) } return nil diff --git a/pkg/lang/compiler/scope/scope_chain.go b/pkg/lang/compiler/scope/scope_chain.go new file mode 100644 index 0000000..683d53a --- /dev/null +++ b/pkg/lang/compiler/scope/scope_chain.go @@ -0,0 +1,191 @@ +package scope + +import ( + "fmt" + "jinx/pkg/lang/vm/code" +) + +type ScopeChain struct { + nameToSymbol map[string]SymbolID + + symbolScopes []SymbolScope // All other scopes are bound to this by ID. + functionScopes []FunctionScope +} + +func NewScopeChain() ScopeChain { + symbolScopes := make([]SymbolScope, 1) + symbolScopes[0] = NewSymbolScope() + + functionScopes := make([]FunctionScope, 1) + functionScopes[0] = NewFunctionScope(0, "") // Root function to house top-scope sub units + + return ScopeChain{ + nameToSymbol: make(map[string]SymbolID), + + symbolScopes: symbolScopes, + functionScopes: functionScopes, + } +} + +func (sc *ScopeChain) CurrentScopeID() ScopeID { + return ScopeID(len(sc.symbolScopes) - 1) +} + +func (sc *ScopeChain) IsRootScope() bool { + return sc.CurrentScopeID() == ScopeID(0) +} + +func (sc *ScopeChain) Current() *SymbolScope { + if len(sc.functionScopes) == 0 { + panic("root scope is missing") + } + + return &sc.symbolScopes[sc.CurrentScopeID()] +} + +func (sc *ScopeChain) CurrentFunction() *FunctionScope { + if len(sc.functionScopes) == 0 { + panic("root function scope is missing") + } + + return &sc.functionScopes[len(sc.functionScopes)-1] +} + +func (sc *ScopeChain) Enter() { + sc.symbolScopes = append(sc.symbolScopes, NewSymbolScope()) +} + +func (sc *ScopeChain) EnterFunction(unit code.Marker) { + sc.Enter() + sc.functionScopes = append(sc.functionScopes, NewFunctionScope(sc.CurrentScopeID(), unit)) +} + +func (sc *ScopeChain) Exit() { + if sc.CurrentScopeID() == 0 { + return + } + + sc.symbolScopes[sc.CurrentScopeID()] = SymbolScope{} + sc.symbolScopes = sc.symbolScopes[:sc.CurrentScopeID()] +} + +func (sc *ScopeChain) Declare(name string) (int, bool) { + // Check whether the symbol is already declared in any of the scopes. + if _, ok := sc.nameToSymbol[name]; ok { + return 0, false + } + + current := sc.Current() + indexInScope := len(current.variableSymbols) + + symbolID := SymbolID{ + symbolKind: SymbolKindVariable, + scopeID: sc.CurrentScopeID(), + indexInScope: indexInScope, + } + + // Declare the symbol in the current scope. + current.variableSymbols = append(current.variableSymbols, Symbol[SymbolVariable]{ + name: name, + data: SymbolVariable{ + localIndex: indexInScope, + }, + }) + + sc.nameToSymbol[name] = symbolID + + return indexInScope, true +} + +func (sc *ScopeChain) DeclareFunction(name string, args uint) (code.Marker, bool) { + if _, ok := sc.nameToSymbol[name]; ok { + return "", false + } + + current := sc.Current() + index := len(current.functionSymbols) + + symbolID := SymbolID{ + symbolKind: SymbolKindFunction, + scopeID: sc.CurrentScopeID(), + indexInScope: index, + } + + unitName := sc.CreateFunctionSubUnit(name) + + current.functionSymbols = append(current.functionSymbols, Symbol[SymbolFunction]{ + name: name, + data: SymbolFunction{ + marker: unitName, + args: args, + }, + }) + + sc.nameToSymbol[name] = symbolID + + return unitName, true +} + +func (sc *ScopeChain) DeclareAnonymous() int { + current := sc.Current() + index := len(current.variableSymbols) + + current.variableSymbols = append(current.variableSymbols, Symbol[SymbolVariable]{ + name: "", // An anonymous symbol has no name. + data: SymbolVariable{ + localIndex: index, + }, + }) + + return index +} + +func (sc *ScopeChain) DeclareTemporary() int { + return len(sc.Current().variableSymbols) // :) +} + +func (sc *ScopeChain) CreateAnonymousFunctionSubUnit() code.Marker { + fnScope := sc.CurrentFunction() + + index := fnScope.subUnitCount + fnScope.subUnitCount++ + + return sc.CreateFunctionSubUnit(fmt.Sprintf("anon_%d", index)) +} + +func (sc *ScopeChain) CreateFunctionSubUnit(subUnitName string) code.Marker { + fnScope := sc.CurrentFunction() + + name := fnScope.unit + if name == "" { + name = code.Marker(subUnitName) + } else { + name = name.SubUnit(subUnitName) + } + + return name +} + +func (sc *ScopeChain) Lookup(name string) (SymbolID, bool) { + if id, ok := sc.nameToSymbol[name]; ok { + return id, true + } + + return SymbolID{}, false +} + +func (sc *ScopeChain) GetVariable(id SymbolID) Symbol[SymbolVariable] { + if id.symbolKind != SymbolKindVariable { + panic("incorrect symbol id kind given") + } + + return sc.symbolScopes[id.scopeID].variableSymbols[id.indexInScope] +} + +func (sc *ScopeChain) GetFunction(id SymbolID) Symbol[SymbolFunction] { + if id.symbolKind != SymbolKindFunction { + panic("incorrect symbol id kind given") + } + + return sc.symbolScopes[id.scopeID].functionSymbols[id.indexInScope] +} diff --git a/pkg/lang/compiler/scope/scopes.go b/pkg/lang/compiler/scope/scopes.go new file mode 100644 index 0000000..39e48ef --- /dev/null +++ b/pkg/lang/compiler/scope/scopes.go @@ -0,0 +1,50 @@ +package scope + +import "jinx/pkg/lang/vm/code" + +type ScopeID int + +type ScopeKind int + +const ( + ScopeKindNormal ScopeKind = iota + ScopeKindFunction +) + +type SymbolScope struct { + variableSymbols []Symbol[SymbolVariable] + functionSymbols []Symbol[SymbolFunction] +} + +func NewSymbolScope() SymbolScope { + return SymbolScope{ + variableSymbols: make([]Symbol[SymbolVariable], 0), + functionSymbols: make([]Symbol[SymbolFunction], 0), + } +} + +type FunctionScope struct { + id ScopeID + unit code.Marker + subUnitCount int +} + +func NewFunctionScope(id ScopeID, unit code.Marker) FunctionScope { + return FunctionScope{ + id: id, + unit: unit, + subUnitCount: 0, + } +} + +func (sf FunctionScope) ID() ScopeID { + return sf.id +} + +func (sf FunctionScope) Unit() code.Marker { + return sf.unit +} + +func (sf FunctionScope) IsRootScope() bool { + return sf.ID() == ScopeID(0) +} diff --git a/pkg/lang/compiler/scope/symbol.go b/pkg/lang/compiler/scope/symbol.go new file mode 100644 index 0000000..df91899 --- /dev/null +++ b/pkg/lang/compiler/scope/symbol.go @@ -0,0 +1,65 @@ +package scope + +import "jinx/pkg/lang/vm/code" + +type SymbolID struct { + symbolKind SymbolKind + scopeID ScopeID + indexInScope int +} + +func (id SymbolID) SymbolKind() SymbolKind { + return id.symbolKind +} + +type SymbolKind int + +const ( + SymbolKindVariable SymbolKind = iota + SymbolKindFunction +) + +func (s SymbolKind) String() string { + switch s { + case SymbolKindVariable: + return "variable" + case SymbolKindFunction: + return "function" + default: + panic("unknown symbol kind") + } +} + +type Symbol[D SymbolData] struct { + name string + data D +} + +func (s Symbol[D]) Data() D { + return s.data +} + +type SymbolData interface { + SymbolVariable | SymbolFunction +} + +type SymbolVariable struct { + localIndex int +} + +func (sv SymbolVariable) LocalIndex() int { + return sv.localIndex +} + +type SymbolFunction struct { + marker code.Marker + args uint +} + +func (sf SymbolFunction) Marker() code.Marker { + return sf.marker +} + +func (sf SymbolFunction) Args() uint { + return sf.args +} diff --git a/pkg/lang/compiler/scope_chain.go b/pkg/lang/compiler/scope_chain.go deleted file mode 100644 index 6705852..0000000 --- a/pkg/lang/compiler/scope_chain.go +++ /dev/null @@ -1,254 +0,0 @@ -package compiler - -import ( - "fmt" - "jinx/pkg/lang/vm/code" -) - -type ScopeID int - -type ScopeChain struct { - nameToSymbol map[string]SymbolID - scopes []Scope -} - -func NewScopeChain() ScopeChain { - scopes := make([]Scope, 1) - scopes[0] = NewFunctionScope(0, "") // Top-most scope is a function scope, so it can have sub-units - - return ScopeChain{ - nameToSymbol: make(map[string]SymbolID), - scopes: scopes, - } -} - -func (sc *ScopeChain) CurrentScopeID() ScopeID { - return ScopeID(len(sc.scopes) - 1) -} - -func (sc *ScopeChain) IsRootScope() bool { - return sc.CurrentScopeID() == ScopeID(0) -} - -func (sc *ScopeChain) Current() *Scope { - return &sc.scopes[sc.CurrentScopeID()] -} - -func (sc *ScopeChain) CurrentFunction() *Scope { - // TODO: Probably should make this lookup constant by making a seperate array of function scopes - for i := len(sc.scopes) - 1; i >= 0; i++ { - if sc.scopes[i].kind == ScopeKindFunction { - return &sc.scopes[i] - } - } - - panic("top scope should always be a function scope") -} - -func (sc *ScopeChain) Enter() { - sc.scopes = append(sc.scopes, NewNormalScope()) -} - -func (sc *ScopeChain) EnterFunction(unit code.Marker) { - id := sc.CurrentScopeID() + 1 - sc.scopes = append(sc.scopes, NewFunctionScope(id, unit)) -} - -func (sc *ScopeChain) Exit() { - if sc.CurrentScopeID() == 0 { - return - } - - sc.scopes[sc.CurrentScopeID()] = Scope{} - sc.scopes = sc.scopes[:sc.CurrentScopeID()] -} - -func (sc *ScopeChain) Declare(name string) (int, bool) { - // Check whether the symbol is already declared in any of the scopes. - if _, ok := sc.nameToSymbol[name]; ok { - return 0, false - } - - current := sc.Current() - indexInScope := len(current.variableSymbols) - - symbolID := SymbolID{ - symbolKind: SymbolKindVariable, - scopeID: sc.CurrentScopeID(), - indexInScope: indexInScope, - } - - // Declare the symbol in the current scope. - current.variableSymbols = append(current.variableSymbols, Symbol[SymbolVariable]{ - name: name, - data: SymbolVariable{ - localIndex: indexInScope, - }, - }) - - sc.nameToSymbol[name] = symbolID - - return indexInScope, true -} - -func (sc *ScopeChain) DeclareFunction(name string, args uint) (code.Marker, bool) { - if _, ok := sc.nameToSymbol[name]; ok { - return "", false - } - - current := sc.Current() - index := len(current.functionSymbols) - - symbolID := SymbolID{ - symbolKind: SymbolKindFunction, - scopeID: sc.CurrentScopeID(), - indexInScope: index, - } - - unitName := sc.CreateFunctionSubUnit(name) - - current.functionSymbols = append(current.functionSymbols, Symbol[SymbolFunction]{ - name: name, - data: SymbolFunction{ - marker: unitName, - args: args, - }, - }) - - sc.nameToSymbol[name] = symbolID - - return unitName, true -} - -func (sc *ScopeChain) DeclareAnonymous() int { - current := sc.Current() - index := len(current.variableSymbols) - - current.variableSymbols = append(current.variableSymbols, Symbol[SymbolVariable]{ - name: "", // An anonymous symbol has no name. - data: SymbolVariable{ - localIndex: index, - }, - }) - - return index -} - -func (sc *ScopeChain) DeclareTemporary() int { - return len(sc.Current().variableSymbols) // :) -} - -func (sc *ScopeChain) CreateAnonymousFunctionSubUnit() code.Marker { - fnScope := sc.CurrentFunction() - data := fnScope.data.(ScopeFunction) - - index := data.subUnitCount - data.subUnitCount++ - - fnScope.data = data - - return sc.CreateFunctionSubUnit(fmt.Sprintf("anon_%d", index)) -} - -func (sc *ScopeChain) CreateFunctionSubUnit(subUnitName string) code.Marker { - fnScope := sc.CurrentFunction() - data := fnScope.data.(ScopeFunction) - - name := data.unit - if name == "" { - name = code.Marker(subUnitName) - } else { - name = name.SubUnit(subUnitName) - } - - return name -} - -func (sc *ScopeChain) Lookup(name string) (SymbolID, bool) { - if id, ok := sc.nameToSymbol[name]; ok { - return id, true - } - - return SymbolID{}, false -} - -func (sc *ScopeChain) GetVariable(id SymbolID) Symbol[SymbolVariable] { - if id.symbolKind != SymbolKindVariable { - panic("incorrect symbol id kind given") - } - - return sc.scopes[id.scopeID].variableSymbols[id.indexInScope] -} - -func (sc *ScopeChain) GetFunction(id SymbolID) Symbol[SymbolFunction] { - if id.symbolKind != SymbolKindFunction { - panic("incorrect symbol id kind given") - } - - return sc.scopes[id.scopeID].functionSymbols[id.indexInScope] -} - -type SymbolID struct { - symbolKind SymbolKind - scopeID ScopeID - indexInScope int -} - -type ScopeKind int - -const ( - ScopeKindNormal ScopeKind = iota - ScopeKindFunction - ScopeKindLoop -) - -type Scope struct { - variableSymbols []Symbol[SymbolVariable] - functionSymbols []Symbol[SymbolFunction] - - kind ScopeKind - data any -} - -func NewNormalScope() Scope { - return Scope{ - variableSymbols: make([]Symbol[SymbolVariable], 0), - functionSymbols: make([]Symbol[SymbolFunction], 0), - kind: ScopeKindNormal, - data: ScopeNormal{}, - } -} - -func NewFunctionScope(id ScopeID, unit code.Marker) Scope { - return Scope{ - variableSymbols: make([]Symbol[SymbolVariable], 0), - functionSymbols: make([]Symbol[SymbolFunction], 0), - kind: ScopeKindFunction, - data: ScopeFunction{ - id: id, - unit: unit, - subUnitCount: 0, - }, - } -} - -type ScopeNormal struct{} - -type ScopeFunction struct { - id ScopeID - unit code.Marker - subUnitCount int -} - -func (sf ScopeFunction) ID() ScopeID { - return sf.id -} - -func (sf ScopeFunction) IsRootScope() bool { - return sf.ID() == ScopeID(0) -} - -type ScopeLoop struct { - breakMarker code.Marker - continueMarker code.Marker -} diff --git a/pkg/lang/compiler/symbol.go b/pkg/lang/compiler/symbol.go deleted file mode 100644 index 453cb2b..0000000 --- a/pkg/lang/compiler/symbol.go +++ /dev/null @@ -1,39 +0,0 @@ -package compiler - -import "jinx/pkg/lang/vm/code" - -type SymbolKind int - -const ( - SymbolKindVariable SymbolKind = iota - SymbolKindFunction -) - -func (s SymbolKind) String() string { - switch s { - case SymbolKindVariable: - return "variable" - case SymbolKindFunction: - return "function" - default: - panic("unknown symbol kind") - } -} - -type Symbol[D SymbolData] struct { - name string - data D -} - -type SymbolData interface { - SymbolVariable | SymbolFunction -} - -type SymbolVariable struct { - localIndex int -} - -type SymbolFunction struct { - marker code.Marker - args uint -} -- cgit 1.4.1