| // Copyright (C) 2019 Google Inc. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // Package parser implements a SPIR-V assembly parser. |
| package parser |
| |
| import ( |
| "fmt" |
| "io" |
| "log" |
| "strings" |
| "unicode" |
| "unicode/utf8" |
| |
| "github.com/KhronosGroup/SPIRV-Tools/utils/vscode/src/schema" |
| ) |
| |
| // Type is an enumerator of token types. |
| type Type int |
| |
| // Type enumerators |
| const ( |
| Ident Type = iota // Foo |
| PIdent // %32, %foo |
| Integer |
| Float |
| String |
| Operator |
| Comment |
| Newline |
| ) |
| |
| func (t Type) String() string { |
| switch t { |
| case Ident: |
| return "Ident" |
| case PIdent: |
| return "PIdent" |
| case Integer: |
| return "Integer" |
| case Float: |
| return "Float" |
| case String: |
| return "String" |
| case Operator: |
| return "Operator" |
| case Comment: |
| return "Comment" |
| default: |
| return "<unknown>" |
| } |
| } |
| |
| // Token represents a single lexed token. |
| type Token struct { |
| Type Type |
| Range Range |
| } |
| |
| func (t Token) String() string { return fmt.Sprintf("{%v %v}", t.Type, t.Range) } |
| |
| // Text returns the tokens text from the source. |
| func (t Token) Text(lines []string) string { return t.Range.Text(lines) } |
| |
| // Range represents an interval in a text file. |
| type Range struct { |
| Start Position |
| End Position |
| } |
| |
| func (r Range) String() string { return fmt.Sprintf("[%v %v]", r.Start, r.End) } |
| |
| // Text returns the text for the given Range in the provided lines. |
| func (r Range) Text(lines []string) string { |
| sl, sc := r.Start.Line-1, r.Start.Column-1 |
| if sl < 0 || sc < 0 || sl > len(lines) || sc > len(lines[sl]) { |
| return fmt.Sprintf("<invalid start position %v>", r.Start) |
| } |
| el, ec := r.End.Line-1, r.End.Column-1 |
| if el < 0 || ec < 0 || el > len(lines) || ec > len(lines[sl]) { |
| return fmt.Sprintf("<invalid end position %v>", r.End) |
| } |
| |
| sb := strings.Builder{} |
| if sl != el { |
| sb.WriteString(lines[sl][sc:]) |
| for l := sl + 1; l < el; l++ { |
| sb.WriteString(lines[l]) |
| } |
| sb.WriteString(lines[el][:ec]) |
| } else { |
| sb.WriteString(lines[sl][sc:ec]) |
| } |
| return sb.String() |
| } |
| |
| // Contains returns true if p is in r. |
| func (r Range) Contains(p Position) bool { |
| return !(p.LessThan(r.Start) || p.GreaterThan(r.End)) |
| } |
| |
| func (r *Range) grow(o Range) { |
| if !r.Start.IsValid() || o.Start.LessThan(r.Start) { |
| r.Start = o.Start |
| } |
| if !r.End.IsValid() || o.End.GreaterThan(r.End) { |
| r.End = o.End |
| } |
| } |
| |
| // Position holds a line and column position in a text file. |
| type Position struct { |
| Line, Column int |
| } |
| |
| func (p Position) String() string { return fmt.Sprintf("%v:%v", p.Line, p.Column) } |
| |
| // IsValid returns true if the position has a line and column greater than 1. |
| func (p Position) IsValid() bool { return p.Line > 0 && p.Column > 0 } |
| |
| // LessThan returns true iff o is before p. |
| func (p Position) LessThan(o Position) bool { |
| switch { |
| case !p.IsValid() || !o.IsValid(): |
| return false |
| case p.Line < o.Line: |
| return true |
| case p.Line > o.Line: |
| return false |
| case p.Column < o.Column: |
| return true |
| default: |
| return false |
| } |
| } |
| |
| // GreaterThan returns true iff o is greater than p. |
| func (p Position) GreaterThan(o Position) bool { |
| switch { |
| case !p.IsValid() || !o.IsValid(): |
| return false |
| case p.Line > o.Line: |
| return true |
| case p.Line < o.Line: |
| return false |
| case p.Column > o.Column: |
| return true |
| default: |
| return false |
| } |
| } |
| |
| type lexer struct { |
| source string |
| lexerState |
| diags []Diagnostic |
| e error |
| } |
| |
| type lexerState struct { |
| offset int // byte offset in source |
| toks []*Token // all the lexed tokens |
| pos Position // current position |
| } |
| |
| // err appends an fmt.Printf style error into l.diags for the given token. |
| func (l *lexer) err(tok *Token, msg string, args ...interface{}) { |
| rng := Range{} |
| if tok != nil { |
| rng = tok.Range |
| } |
| l.diags = append(l.diags, Diagnostic{ |
| Range: rng, |
| Severity: SeverityError, |
| Message: fmt.Sprintf(msg, args...), |
| }) |
| } |
| |
| // next returns the next rune, or io.EOF if the last rune has already been |
| // consumed. |
| func (l *lexer) next() rune { |
| if l.offset >= len(l.source) { |
| l.e = io.EOF |
| return 0 |
| } |
| r, n := utf8.DecodeRuneInString(l.source[l.offset:]) |
| l.offset += n |
| if n == 0 { |
| l.e = io.EOF |
| return 0 |
| } |
| if r == '\n' { |
| l.pos.Line++ |
| l.pos.Column = 1 |
| } else { |
| l.pos.Column++ |
| } |
| return r |
| } |
| |
| // save returns the current lexerState. |
| func (l *lexer) save() lexerState { |
| return l.lexerState |
| } |
| |
| // restore restores the current lexer state with s. |
| func (l *lexer) restore(s lexerState) { |
| l.lexerState = s |
| } |
| |
| // pident processes the PIdent token at the current position. |
| // The lexer *must* know the next token is a PIdent before calling. |
| func (l *lexer) pident() { |
| tok := &Token{Type: PIdent, Range: Range{Start: l.pos, End: l.pos}} |
| if r := l.next(); r != '%' { |
| log.Fatalf("lexer expected '%%', got '%v'", r) |
| return |
| } |
| for l.e == nil { |
| s := l.save() |
| r := l.next() |
| if !isAlphaNumeric(r) && r != '_' { |
| l.restore(s) |
| break |
| } |
| } |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| } |
| |
| // numberOrIdent processes the Ident, Float or Integer token at the current |
| // position. |
| func (l *lexer) numberOrIdent() { |
| const Unknown Type = -1 |
| tok := &Token{Type: Unknown, Range: Range{Start: l.pos, End: l.pos}} |
| loop: |
| for l.e == nil { |
| s := l.save() |
| r := l.next() |
| switch { |
| case r == '-', r == '+', isNumeric(r): |
| continue |
| case isAlpha(r), r == '_': |
| switch tok.Type { |
| case Unknown: |
| tok.Type = Ident |
| case Float, Integer: |
| l.err(tok, "invalid number") |
| return |
| } |
| case r == '.': |
| switch tok.Type { |
| case Unknown: |
| tok.Type = Float |
| default: |
| l.restore(s) |
| break loop |
| } |
| default: |
| if tok.Type == Unknown { |
| tok.Type = Integer |
| } |
| l.restore(s) |
| break loop |
| } |
| } |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| } |
| |
| // string processes the String token at the current position. |
| // The lexer *must* know the next token is a String before calling. |
| func (l *lexer) string() { |
| tok := &Token{Type: String, Range: Range{Start: l.pos, End: l.pos}} |
| if r := l.next(); r != '"' { |
| log.Fatalf("lexer expected '\"', got '%v'", r) |
| return |
| } |
| escape := false |
| for l.e == nil { |
| switch l.next() { |
| case '"': |
| if !escape { |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| return |
| } |
| case '\\': |
| escape = !escape |
| default: |
| escape = false |
| } |
| } |
| } |
| |
| // operator processes the Operator token at the current position. |
| // The lexer *must* know the next token is a Operator before calling. |
| func (l *lexer) operator() { |
| tok := &Token{Type: Operator, Range: Range{Start: l.pos, End: l.pos}} |
| for l.e == nil { |
| switch l.next() { |
| case '=', '|': |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| return |
| } |
| } |
| } |
| |
| // lineComment processes the Comment token at the current position. |
| // The lexer *must* know the next token is a Comment before calling. |
| func (l *lexer) lineComment() { |
| tok := &Token{Type: Comment, Range: Range{Start: l.pos, End: l.pos}} |
| if r := l.next(); r != ';' { |
| log.Fatalf("lexer expected ';', got '%v'", r) |
| return |
| } |
| for l.e == nil { |
| s := l.save() |
| switch l.next() { |
| case '\n': |
| l.restore(s) |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| return |
| } |
| } |
| } |
| |
| // newline processes the Newline token at the current position. |
| // The lexer *must* know the next token is a Newline before calling. |
| func (l *lexer) newline() { |
| tok := &Token{Type: Newline, Range: Range{Start: l.pos, End: l.pos}} |
| if r := l.next(); r != '\n' { |
| log.Fatalf("lexer expected '\n', got '%v'", r) |
| return |
| } |
| tok.Range.End = l.pos |
| l.toks = append(l.toks, tok) |
| } |
| |
| // lex returns all the tokens and diagnostics after lexing source. |
| func lex(source string) ([]*Token, []Diagnostic, error) { |
| l := lexer{source: source, lexerState: lexerState{pos: Position{1, 1}}} |
| |
| lastPos := Position{} |
| for l.e == nil { |
| // Integrity check that the parser is making progress |
| if l.pos == lastPos { |
| log.Panicf("Parsing stuck at %v", l.pos) |
| } |
| lastPos = l.pos |
| |
| s := l.save() |
| r := l.next() |
| switch { |
| case r == '%': |
| l.restore(s) |
| l.pident() |
| case r == '+' || r == '-' || r == '_' || isAlphaNumeric(r): |
| l.restore(s) |
| l.numberOrIdent() |
| case r == '"': |
| l.restore(s) |
| l.string() |
| case r == '=', r == '|': |
| l.restore(s) |
| l.operator() |
| case r == ';': |
| l.restore(s) |
| l.lineComment() |
| case r == '\n': |
| l.restore(s) |
| l.newline() |
| } |
| } |
| if l.e != nil && l.e != io.EOF { |
| return nil, nil, l.e |
| } |
| return l.toks, l.diags, nil |
| } |
| |
| func isNumeric(r rune) bool { return unicode.IsDigit(r) } |
| func isAlpha(r rune) bool { return unicode.IsLetter(r) } |
| func isAlphaNumeric(r rune) bool { return isAlpha(r) || isNumeric(r) } |
| |
| type parser struct { |
| lines []string // all source lines |
| toks []*Token // all tokens |
| diags []Diagnostic // parser emitted diagnostics |
| idents map[string]*Identifier // identifiers by name |
| mappings map[*Token]interface{} // tokens to semantic map |
| extInstImports map[string]schema.OpcodeMap // extension imports by identifier |
| insts []*Instruction // all instructions |
| } |
| |
| func (p *parser) parse() error { |
| for i := 0; i < len(p.toks); { |
| if p.newline(i) || p.comment(i) { |
| i++ |
| continue |
| } |
| if n := p.instruction(i); n > 0 { |
| i += n |
| } else { |
| p.unexpected(i) |
| i++ |
| } |
| } |
| return nil |
| } |
| |
| // instruction parses the instruction starting at the i'th token. |
| func (p *parser) instruction(i int) (n int) { |
| inst := &Instruction{} |
| |
| switch { |
| case p.opcode(i) != nil: |
| inst.Opcode = p.opcode(i) |
| inst.Tokens = []*Token{p.tok(i)} |
| p.mappings[p.tok(i)] = inst |
| n++ |
| case p.opcode(i+2) != nil: // try '%id' '=' |
| inst.Result, inst.Opcode = p.pident(i), p.opcode(i+2) |
| if inst.Result == nil || p.operator(i+1) != "=" { |
| return 0 |
| } |
| n += 3 |
| inst.Tokens = []*Token{p.tok(i), p.tok(i + 1), p.tok(i + 2)} |
| p.mappings[p.tok(i+2)] = inst |
| default: |
| return |
| } |
| |
| expectsResult := len(inst.Opcode.Operands) > 0 && IsResult(inst.Opcode.Operands[0].Kind) |
| operands := inst.Opcode.Operands |
| switch { |
| case inst.Result != nil && !expectsResult: |
| p.err(inst.Result, "'%s' does not have a result", inst.Opcode.Opname) |
| return |
| case inst.Result == nil && expectsResult: |
| p.err(p.tok(i), "'%s' expects a result", inst.Opcode.Opname) |
| return |
| case inst.Result != nil && expectsResult: |
| // Check the result is of the correct type |
| o := inst.Opcode.Operands[0] |
| p.operand(o.Name, o.Kind, i, false) |
| operands = operands[1:] |
| p.addIdentDef(inst.Result.Text(p.lines), inst, p.tok(i)) |
| } |
| |
| processOperand := func(o schema.Operand) bool { |
| if p.newline(i + n) { |
| return false |
| } |
| |
| switch o.Quantifier { |
| case schema.Once: |
| if op, c := p.operand(o.Name, o.Kind, i+n, false); op != nil { |
| inst.Tokens = append(inst.Tokens, op.Tokens...) |
| n += c |
| } |
| case schema.ZeroOrOnce: |
| if op, c := p.operand(o.Name, o.Kind, i+n, true); op != nil { |
| inst.Tokens = append(inst.Tokens, op.Tokens...) |
| n += c |
| } |
| case schema.ZeroOrMany: |
| for !p.newline(i + n) { |
| if op, c := p.operand(o.Name, o.Kind, i+n, true); op != nil { |
| inst.Tokens = append(inst.Tokens, op.Tokens...) |
| n += c |
| } else { |
| return false |
| } |
| } |
| } |
| return true |
| } |
| |
| for _, o := range operands { |
| if !processOperand(o) { |
| break |
| } |
| |
| if inst.Opcode == schema.OpExtInst && n == 4 { |
| extImportTok, extNameTok := p.tok(i+n), p.tok(i+n+1) |
| extImport := extImportTok.Text(p.lines) |
| if extOpcodes, ok := p.extInstImports[extImport]; ok { |
| extName := extNameTok.Text(p.lines) |
| if extOpcode, ok := extOpcodes[extName]; ok { |
| n += 2 // skip ext import, ext name |
| for _, o := range extOpcode.Operands { |
| if !processOperand(o) { |
| break |
| } |
| } |
| } else { |
| p.err(extNameTok, "Unknown extension opcode '%s'", extName) |
| } |
| } else { |
| p.err(extImportTok, "Expected identifier to OpExtInstImport") |
| } |
| } |
| } |
| |
| for _, t := range inst.Tokens { |
| inst.Range.grow(t.Range) |
| } |
| |
| p.insts = append(p.insts, inst) |
| |
| if inst.Opcode == schema.OpExtInstImport && len(inst.Tokens) >= 4 { |
| // Instruction is a OpExtInstImport. Keep track of this. |
| extTok := inst.Tokens[3] |
| extName := strings.Trim(extTok.Text(p.lines), `"`) |
| extOpcodes, ok := schema.ExtOpcodes[extName] |
| if !ok { |
| p.err(extTok, "Unknown extension '%s'", extName) |
| } |
| extImport := inst.Result.Text(p.lines) |
| p.extInstImports[extImport] = extOpcodes |
| } |
| |
| return |
| } |
| |
| // operand parses the operand with the name n, kind k, starting at the i'th |
| // token. |
| func (p *parser) operand(n string, k *schema.OperandKind, i int, optional bool) (*Operand, int) { |
| tok := p.tok(i) |
| if tok == nil { |
| return nil, 0 |
| } |
| |
| op := &Operand{ |
| Name: n, |
| Kind: k, |
| Tokens: []*Token{tok}, |
| } |
| p.mappings[tok] = op |
| |
| switch k.Category { |
| case schema.OperandCategoryBitEnum, schema.OperandCategoryValueEnum: |
| s := tok.Text(p.lines) |
| for _, e := range k.Enumerants { |
| if e.Enumerant == s { |
| count := 1 |
| for _, param := range e.Parameters { |
| p, c := p.operand(param.Name, param.Kind, i+count, false) |
| if p != nil { |
| op.Tokens = append(op.Tokens, p.Tokens...) |
| op.Parameters = append(op.Parameters, p) |
| } |
| count += c |
| } |
| |
| // Handle bitfield '|' chains |
| if p.tok(i+count).Text(p.lines) == "|" { |
| count++ // '|' |
| p, c := p.operand(n, k, i+count, false) |
| if p != nil { |
| op.Tokens = append(op.Tokens, p.Tokens...) |
| op.Parameters = append(op.Parameters, p) |
| } |
| count += c |
| } |
| |
| return op, count |
| } |
| } |
| if !optional { |
| p.err(p.tok(i), "invalid operand value '%s'", s) |
| } |
| |
| return nil, 0 |
| |
| case schema.OperandCategoryID: |
| id := p.pident(i) |
| if id != nil { |
| p.addIdentRef(p.tok(i)) |
| return op, 1 |
| } |
| if !optional { |
| p.err(p.tok(i), "operand requires id, got '%s'", tok.Text(p.lines)) |
| } |
| return nil, 0 |
| |
| case schema.OperandCategoryLiteral: |
| switch tok.Type { |
| case String, Integer, Float, Ident: |
| return op, 1 |
| } |
| if !optional { |
| p.err(p.tok(i), "operand requires literal, got '%s'", tok.Text(p.lines)) |
| } |
| return nil, 0 |
| |
| case schema.OperandCategoryComposite: |
| n := 1 |
| for _, b := range k.Bases { |
| o, c := p.operand(b.Kind, b, i+n, optional) |
| if o != nil { |
| op.Tokens = append(op.Tokens, o.Tokens...) |
| } |
| n += c |
| } |
| return op, n |
| |
| default: |
| p.err(p.tok(i), "OperandKind '%s' has unexpected category '%s'", k.Kind, k.Category) |
| return nil, 0 |
| } |
| } |
| |
| // tok returns the i'th token, or nil if i is out of bounds. |
| func (p *parser) tok(i int) *Token { |
| if i < 0 || i >= len(p.toks) { |
| return nil |
| } |
| return p.toks[i] |
| } |
| |
| // opcode returns the schema.Opcode for the i'th token, or nil if the i'th token |
| // does not represent an opcode. |
| func (p *parser) opcode(i int) *schema.Opcode { |
| if tok := p.ident(i); tok != nil { |
| name := tok.Text(p.lines) |
| if inst, found := schema.Opcodes[name]; found { |
| return inst |
| } |
| } |
| return nil |
| } |
| |
| // operator returns the operator for the i'th token, or and empty string if the |
| // i'th token is not an operator. |
| func (p *parser) operator(i int) string { |
| if tok := p.tok(i); tok != nil && tok.Type == Operator { |
| return tok.Text(p.lines) |
| } |
| return "" |
| } |
| |
| // ident returns the i'th token if it is an Ident, otherwise nil. |
| func (p *parser) ident(i int) *Token { |
| if tok := p.tok(i); tok != nil && tok.Type == Ident { |
| return tok |
| } |
| return nil |
| } |
| |
| // pident returns the i'th token if it is an PIdent, otherwise nil. |
| func (p *parser) pident(i int) *Token { |
| if tok := p.tok(i); tok != nil && tok.Type == PIdent { |
| return tok |
| } |
| return nil |
| } |
| |
| // comment returns true if the i'th token is a Comment, otherwise false. |
| func (p *parser) comment(i int) bool { |
| if tok := p.tok(i); tok != nil && tok.Type == Comment { |
| return true |
| } |
| return false |
| } |
| |
| // newline returns true if the i'th token is a Newline, otherwise false. |
| func (p *parser) newline(i int) bool { |
| if tok := p.tok(i); tok != nil && tok.Type == Newline { |
| return true |
| } |
| return false |
| } |
| |
| // unexpected emits an 'unexpected token error' for the i'th token. |
| func (p *parser) unexpected(i int) { |
| p.err(p.toks[i], "syntax error: unexpected '%s'", p.toks[i].Text(p.lines)) |
| } |
| |
| // addIdentDef records the token definition for the instruction inst with the |
| // given id. |
| func (p *parser) addIdentDef(id string, inst *Instruction, def *Token) { |
| i, existing := p.idents[id] |
| if !existing { |
| i = &Identifier{} |
| p.idents[id] = i |
| } |
| if i.Definition == nil { |
| i.Definition = inst |
| } else { |
| p.err(def, "id '%v' redeclared", id) |
| } |
| } |
| |
| // addIdentRef adds a identifier reference for the token ref. |
| func (p *parser) addIdentRef(ref *Token) { |
| id := ref.Text(p.lines) |
| i, existing := p.idents[id] |
| if !existing { |
| i = &Identifier{} |
| p.idents[id] = i |
| } |
| i.References = append(i.References, ref) |
| } |
| |
| // err appends an fmt.Printf style error into l.diags for the given token. |
| func (p *parser) err(tok *Token, msg string, args ...interface{}) { |
| rng := Range{} |
| if tok != nil { |
| rng = tok.Range |
| } |
| p.diags = append(p.diags, Diagnostic{ |
| Range: rng, |
| Severity: SeverityError, |
| Message: fmt.Sprintf(msg, args...), |
| }) |
| } |
| |
| // Parse parses the SPIR-V assembly string source, returning the parse results. |
| func Parse(source string) (Results, error) { |
| toks, diags, err := lex(source) |
| if err != nil { |
| return Results{}, err |
| } |
| lines := strings.SplitAfter(source, "\n") |
| p := parser{ |
| lines: lines, |
| toks: toks, |
| idents: map[string]*Identifier{}, |
| mappings: map[*Token]interface{}{}, |
| extInstImports: map[string]schema.OpcodeMap{}, |
| } |
| if err := p.parse(); err != nil { |
| return Results{}, err |
| } |
| diags = append(diags, p.diags...) |
| return Results{ |
| Lines: lines, |
| Tokens: toks, |
| Diagnostics: p.diags, |
| Identifiers: p.idents, |
| Mappings: p.mappings, |
| }, nil |
| } |
| |
| // IsResult returns true if k is used to store the result of an instruction. |
| func IsResult(k *schema.OperandKind) bool { |
| switch k { |
| case schema.OperandKindIdResult, schema.OperandKindIdResultType: |
| return true |
| default: |
| return false |
| } |
| } |
| |
| // Results holds the output of Parse(). |
| type Results struct { |
| Lines []string |
| Tokens []*Token |
| Diagnostics []Diagnostic |
| Identifiers map[string]*Identifier // identifiers by name |
| Mappings map[*Token]interface{} // tokens to semantic map |
| } |
| |
| // Instruction describes a single instruction instance |
| type Instruction struct { |
| Tokens []*Token // all the tokens that make up the instruction |
| Result *Token // the token that represents the result of the instruction, or nil |
| Operands []*Operand // the operands of the instruction |
| Range Range // the textual range of the instruction |
| Opcode *schema.Opcode // the opcode for the instruction |
| } |
| |
| // Operand describes a single operand instance |
| type Operand struct { |
| Name string // name of the operand |
| Kind *schema.OperandKind // kind of the operand |
| Tokens []*Token // all the tokens that make up the operand |
| Parameters []*Operand // all the parameters for the operand |
| } |
| |
| // Identifier describes a single, unique SPIR-V identifier (i.e. %32) |
| type Identifier struct { |
| Definition *Instruction // where the identifier was defined |
| References []*Token // all the places the identifier was referenced |
| } |
| |
| // Severity is an enumerator of diagnositc seeverities |
| type Severity int |
| |
| // Severity levels |
| const ( |
| SeverityError Severity = iota |
| SeverityWarning |
| SeverityInformation |
| SeverityHint |
| ) |
| |
| // Diagnostic holds a single diagnostic message that was generated while |
| // parsing. |
| type Diagnostic struct { |
| Range Range |
| Severity Severity |
| Message string |
| } |
