query/parse.go - zoekt - Git at Google

 // Copyright 2016 Google Inc. All rights reserved.
 //
 // 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 query

 import (
 	"bytes"
 	"fmt"
 	"log"
 	"regexp/syntax"
 )

 var _ = log.Printf

 type SuggestQueryError struct {
 	Message    string
 	Suggestion string
 }

 func (e *SuggestQueryError) Error() string {
 	return fmt.Sprintf("%s. Suggestion: %s", e.Message, e.Suggestion)
 }

 // parseStringLiteral parses a string literal, consumes the starting
 // quote too.
 func parseStringLiteral(in []byte) (lit []byte, n int, err error) {
 	left := in[1:]
 	found := false

 loop:
 	for len(left) > 0 {
 		c := left[0]
 		left = left[1:]
 		switch c {
 		case '"':
 			found = true
 			break loop
 		case '\\':
 			// TODO - other escape sequences.
 			if len(left) == 0 {
 				return nil, 0, fmt.Errorf("query: missing char after \\")
 			}
 			c = left[0]
 			left = left[1:]

 			lit = append(lit, c)
 		default:
 			lit = append(lit, c)
 		}
 	}
 	if !found {
 		return nil, 0, fmt.Errorf("query: unterminated quoted string")
 	}
 	return lit, len(in) - len(left), nil
 }

 // orOperator is a placeholder intermediate so we can represent [A,
 // or, B] before we convert it to Or{A, B}
 type orOperator struct{}

 func (o *orOperator) String() string {
 	return "orOp"
 }

 func isSpace(c byte) bool {
 	return c == ' ' || c == '\t'
 }

 // Parse parses a string into a query.
 func Parse(qStr string) (Q, error) {
 	b := []byte(qStr)

 	qs, _, err := parseExprList(b)
 	if err != nil {
 		return nil, err
 	}

 	q, err := parseOperators(qs)
 	if err != nil {
 		return nil, err
 	}

 	return Simplify(q), nil
 }

 // parseExpr parses a single expression, returning the result, and the
 // number of bytes consumed.
 func parseExpr(in []byte) (Q, int, error) {
 	b := in[:]
 	var expr Q
 	for len(b) > 0 && isSpace(b[0]) {
 		b = b[1:]
 	}

 	tok, err := nextToken(b)
 	if err != nil {
 		return nil, 0, err
 	}
 	if tok == nil {
 		return nil, 0, nil
 	}
 	b = b[len(tok.Input):]

 	text := string(tok.Text)
 	switch tok.Type {
 	case tokCase:
 		switch text {
 		case "yes":
 		case "no":
 		case "auto":
 		default:
 			return nil, 0, fmt.Errorf("query: unknown case argument %q, want {yes,no,auto}", text)
 		}
 		expr = &caseQ{text}
 	case tokRepo:
 		expr = &Repo{Pattern: text}
 	case tokBranch:
 		expr = &Branch{Pattern: text}
 	case tokText, tokRegex:
 		q, err := regexpQuery(text, false, false)
 		if err != nil {
 			return nil, 0, err
 		}
 		expr = q
 	case tokFile:
 		q, err := regexpQuery(text, false, true)
 		if err != nil {
 			return nil, 0, err
 		}
 		expr = q

 	case tokContent:
 		q, err := regexpQuery(text, true, false)
 		if err != nil {
 			return nil, 0, err
 		}
 		expr = q
 	case tokLang:
 		expr = &Language{Language: text}

 	case tokSym:
 		if text == "" {
 			return nil, 0, fmt.Errorf("the sym: atom must have an argument")
 		}
 		expr = &Symbol{&Substring{Pattern: text}}

 	case tokParenClose:
 		// Caller must consume paren.
 		expr = nil

 	case tokParenOpen:
 		qs, n, err := parseExprList(b)
 		b = b[n:]
 		if err != nil {
 			return nil, 0, err
 		}

 		pTok, err := nextToken(b)
 		if err != nil {
 			return nil, 0, err
 		}
 		if pTok == nil || pTok.Type != tokParenClose {
 			return nil, 0, fmt.Errorf("query: missing close paren, got token %v", pTok)
 		}

 		b = b[len(pTok.Input):]
 		expr, err = parseOperators(qs)
 		if err != nil {
 			return nil, 0, err
 		}
 	case tokNegate:
 		subQ, n, err := parseExpr(b)
 		if err != nil {
 			return nil, 0, err
 		}
 		if subQ == nil {
 			return nil, 0, fmt.Errorf("query: '-' operator needs an argument")
 		}
 		b = b[n:]
 		expr = &Not{subQ}

 	}

 	return expr, len(in) - len(b), nil
 }

 // regexpQuery parses an atom into either a regular expression, or a
 // simple substring atom.
 func regexpQuery(text string, content, file bool) (Q, error) {
 	var expr Q

 	r, err := syntax.Parse(text, syntax.ClassNL|syntax.PerlX|syntax.UnicodeGroups)
 	if err != nil {
 		return nil, err
 	}

 	if r.Op == syntax.OpLiteral {
 		expr = &Substring{
 			Pattern:  string(r.Rune),
 			FileName: file,
 			Content:  content,
 		}
 	} else {
 		expr = &Regexp{
 			Regexp:   r,
 			FileName: file,
 			Content:  content,
 		}
 	}

 	return expr, nil
 }

 // parseOperators interprets the orOperator in a list of queries.
 func parseOperators(in []Q) (Q, error) {
 	top := &Or{}
 	cur := &And{}

 	seenOr := false
 	for _, q := range in {
 		if _, ok := q.(*orOperator); ok {
 			seenOr = true
 			if len(cur.Children) == 0 {
 				return nil, fmt.Errorf("query: OR operator should have operand")
 			}
 			top.Children = append(top.Children, cur)
 			cur = &And{}
 		} else {
 			cur.Children = append(cur.Children, q)
 		}
 	}

 	if seenOr && len(cur.Children) == 0 {
 		return nil, fmt.Errorf("query: OR operator should have operand")
 	}
 	top.Children = append(top.Children, cur)
 	return top, nil
 }

 // parseExprList parses a list of query expressions. It is the
 // workhorse of the Parse function.
 func parseExprList(in []byte) ([]Q, int, error) {
 	b := in[:]
 	var qs []Q
 	for len(b) > 0 {
 		for len(b) > 0 && isSpace(b[0]) {
 			b = b[1:]
 		}
 		tok, _ := nextToken(b)
 		if tok != nil && tok.Type == tokParenClose {
 			break
 		} else if tok != nil && tok.Type == tokOr {
 			qs = append(qs, &orOperator{})
 			b = b[len(tok.Input):]
 			continue
 		}

 		q, n, err := parseExpr(b)
 		if err != nil {
 			return nil, 0, err
 		}

 		if q == nil {
 			// eof or a ')'
 			break
 		}
 		qs = append(qs, q)
 		b = b[n:]
 	}

 	setCase := "auto"
 	newQS := qs[:0]
 	for _, q := range qs {
 		if sc, ok := q.(*caseQ); ok {
 			setCase = sc.Flavor
 		} else {
 			newQS = append(newQS, q)
 		}
 	}
 	qs = mapQueryList(newQS, func(q Q) Q {
 		if sc, ok := q.(setCaser); ok {
 			sc.setCase(setCase)
 		}
 		return q
 	})
 	return qs, len(in) - len(b), nil
 }

 type token struct {
 	Type int
 	// The value of the token
 	Text []byte

 	// The input that we consumed to form the token.
 	Input []byte
 }

 func (t *token) String() string {
 	return fmt.Sprintf("%s:%q", tokNames[t.Type], t.Text)
 }

 // token types.
 const (
 	tokText       = 0
 	tokFile       = 1
 	tokRepo       = 2
 	tokCase       = 3
 	tokBranch     = 4
 	tokParenOpen  = 5
 	tokParenClose = 6
 	tokError      = 7
 	tokNegate     = 8
 	tokRegex      = 9
 	tokOr         = 10
 	tokContent    = 11
 	tokLang       = 12
 	tokSym        = 13
 )

 var tokNames = map[int]string{
 	tokBranch:     "Branch",
 	tokCase:       "Case",
 	tokError:      "Error",
 	tokFile:       "File",
 	tokNegate:     "Negate",
 	tokOr:         "Or",
 	tokParenClose: "ParenClose",
 	tokParenOpen:  "ParenOpen",
 	tokRegex:      "Regex",
 	tokRepo:       "Repo",
 	tokText:       "Text",
 	tokLang:       "Language",
 	tokSym:        "Symbol",
 }

 var prefixes = map[string]int{
 	"b:":       tokBranch,
 	"branch:":  tokBranch,
 	"c:":       tokContent,
 	"case:":    tokCase,
 	"content:": tokContent,
 	"f:":       tokFile,
 	"file:":    tokFile,
 	"r:":       tokRepo,
 	"regex:":   tokRegex,
 	"repo:":    tokRepo,
 	"lang:":    tokLang,
 	"sym:":     tokSym,
 }

 var reservedWords = map[string]int{
 	"or": tokOr,
 }

 func (t *token) setType() {
 	// After we consumed the input, we have to interpret some of the text,
 	// eg. to distinguish between ")" the text and ) the query grouping
 	// parenthesis.
 	if len(t.Text) == 1 && t.Text[0] == '(' {
 		t.Type = tokParenOpen
 	}
 	if len(t.Text) == 1 && t.Text[0] == ')' {
 		t.Type = tokParenClose
 	}

 	for w, typ := range reservedWords {
 		if string(t.Text) == w && string(t.Input) == w {
 			t.Type = typ
 			break
 		}
 	}

 	for pref, typ := range prefixes {
 		if !bytes.HasPrefix(t.Input, []byte(pref)) {
 			continue
 		}

 		t.Text = t.Text[len(pref):]
 		t.Type = typ
 		break
 	}
 }

 // nextToken returns the next token from the given input.
 func nextToken(in []byte) (*token, error) {
 	left := in[:]
 	parenCount := 0
 	var cur token
 	if len(left) == 0 {
 		return nil, nil
 	}

 	if left[0] == '-' {
 		return &token{
 			Type:  tokNegate,
 			Text:  []byte{'-'},
 			Input: in[:1],
 		}, nil
 	}

 	foundSpace := false

 loop:
 	for len(left) > 0 {
 		c := left[0]
 		switch c {
 		case '(':
 			parenCount++
 			cur.Text = append(cur.Text, c)
 			left = left[1:]
 		case ')':
 			if parenCount == 0 {
 				if len(cur.Text) == 0 {
 					cur.Text = []byte{')'}
 					left = left[1:]
 				}
 				break loop
 			}

 			cur.Text = append(cur.Text, c)
 			left = left[1:]
 			parenCount--

 		case '"':
 			t, n, err := parseStringLiteral(left)
 			if err != nil {
 				return nil, err
 			}
 			cur.Text = append(cur.Text, t...)
 			left = left[n:]
 		case '\\':
 			left = left[1:]
 			if len(left) == 0 {
 				return nil, fmt.Errorf("query: lone \\ at end")
 			}
 			c := left[0]
 			cur.Text = append(cur.Text, '\\', c)
 			left = left[1:]

 		case ' ', '\n', '\t':
 			if parenCount > 0 {
 				foundSpace = true
 			}
 			break loop
 		default:
 			cur.Text = append(cur.Text, c)
 			left = left[1:]
 		}
 	}

 	if len(cur.Text) == 0 {
 		return nil, nil
 	}

 	if foundSpace && cur.Text[0] == '(' {
 		cur.Text = cur.Text[:1]
 		cur.Input = in[:1]
 	} else {
 		cur.Input = in[:len(in)-len(left)]
 	}
 	cur.setType()
 	return &cur, nil
 }
	// Copyright 2016 Google Inc. All rights reserved.
	//
	// 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 query

	import (
	"bytes"
	"fmt"
	"log"
	"regexp/syntax"
	)

	var _ = log.Printf

	type SuggestQueryError struct {
	Message string
	Suggestion string
	}

	func (e *SuggestQueryError) Error() string {
	return fmt.Sprintf("%s. Suggestion: %s", e.Message, e.Suggestion)
	}

	// parseStringLiteral parses a string literal, consumes the starting
	// quote too.
	func parseStringLiteral(in []byte) (lit []byte, n int, err error) {
	left := in[1:]
	found := false

	loop:
	for len(left) > 0 {
	c := left[0]
	left = left[1:]
	switch c {
	case '"':
	found = true
	break loop
	case '\\':
	// TODO - other escape sequences.
	if len(left) == 0 {
	return nil, 0, fmt.Errorf("query: missing char after \\")
	}
	c = left[0]
	left = left[1:]

	lit = append(lit, c)
	default:
	lit = append(lit, c)
	}
	}
	if !found {
	return nil, 0, fmt.Errorf("query: unterminated quoted string")
	}
	return lit, len(in) - len(left), nil
	}

	// orOperator is a placeholder intermediate so we can represent [A,
	// or, B] before we convert it to Or{A, B}
	type orOperator struct{}

	func (o *orOperator) String() string {
	return "orOp"
	}

	func isSpace(c byte) bool {
	return c == ' ' \|\| c == '\t'
	}

	// Parse parses a string into a query.
	func Parse(qStr string) (Q, error) {
	b := []byte(qStr)

	qs, _, err := parseExprList(b)
	if err != nil {
	return nil, err
	}

	q, err := parseOperators(qs)
	if err != nil {
	return nil, err
	}

	return Simplify(q), nil
	}

	// parseExpr parses a single expression, returning the result, and the
	// number of bytes consumed.
	func parseExpr(in []byte) (Q, int, error) {
	b := in[:]
	var expr Q
	for len(b) > 0 && isSpace(b[0]) {
	b = b[1:]
	}

	tok, err := nextToken(b)
	if err != nil {
	return nil, 0, err
	}
	if tok == nil {
	return nil, 0, nil
	}
	b = b[len(tok.Input):]

	text := string(tok.Text)
	switch tok.Type {
	case tokCase:
	switch text {
	case "yes":
	case "no":
	case "auto":
	default:
	return nil, 0, fmt.Errorf("query: unknown case argument %q, want {yes,no,auto}", text)
	}
	expr = &caseQ{text}
	case tokRepo:
	expr = &Repo{Pattern: text}
	case tokBranch:
	expr = &Branch{Pattern: text}
	case tokText, tokRegex:
	q, err := regexpQuery(text, false, false)
	if err != nil {
	return nil, 0, err
	}
	expr = q
	case tokFile:
	q, err := regexpQuery(text, false, true)
	if err != nil {
	return nil, 0, err
	}
	expr = q

	case tokContent:
	q, err := regexpQuery(text, true, false)
	if err != nil {
	return nil, 0, err
	}
	expr = q
	case tokLang:
	expr = &Language{Language: text}

	case tokSym:
	if text == "" {
	return nil, 0, fmt.Errorf("the sym: atom must have an argument")
	}
	expr = &Symbol{&Substring{Pattern: text}}

	case tokParenClose:
	// Caller must consume paren.
	expr = nil

	case tokParenOpen:
	qs, n, err := parseExprList(b)
	b = b[n:]
	if err != nil {
	return nil, 0, err
	}

	pTok, err := nextToken(b)
	if err != nil {
	return nil, 0, err
	}
	if pTok == nil \|\| pTok.Type != tokParenClose {
	return nil, 0, fmt.Errorf("query: missing close paren, got token %v", pTok)
	}

	b = b[len(pTok.Input):]
	expr, err = parseOperators(qs)
	if err != nil {
	return nil, 0, err
	}
	case tokNegate:
	subQ, n, err := parseExpr(b)
	if err != nil {
	return nil, 0, err
	}
	if subQ == nil {
	return nil, 0, fmt.Errorf("query: '-' operator needs an argument")
	}
	b = b[n:]
	expr = &Not{subQ}

	}

	return expr, len(in) - len(b), nil
	}

	// regexpQuery parses an atom into either a regular expression, or a
	// simple substring atom.
	func regexpQuery(text string, content, file bool) (Q, error) {
	var expr Q

	r, err := syntax.Parse(text, syntax.ClassNL\|syntax.PerlX\|syntax.UnicodeGroups)
	if err != nil {
	return nil, err
	}

	if r.Op == syntax.OpLiteral {
	expr = &Substring{
	Pattern: string(r.Rune),
	FileName: file,
	Content: content,
	}
	} else {
	expr = &Regexp{
	Regexp: r,
	FileName: file,
	Content: content,
	}
	}

	return expr, nil
	}

	// parseOperators interprets the orOperator in a list of queries.
	func parseOperators(in []Q) (Q, error) {
	top := &Or{}
	cur := &And{}

	seenOr := false
	for _, q := range in {
	if _, ok := q.(*orOperator); ok {
	seenOr = true
	if len(cur.Children) == 0 {
	return nil, fmt.Errorf("query: OR operator should have operand")
	}
	top.Children = append(top.Children, cur)
	cur = &And{}
	} else {
	cur.Children = append(cur.Children, q)
	}
	}

	if seenOr && len(cur.Children) == 0 {
	return nil, fmt.Errorf("query: OR operator should have operand")
	}
	top.Children = append(top.Children, cur)
	return top, nil
	}

	// parseExprList parses a list of query expressions. It is the
	// workhorse of the Parse function.
	func parseExprList(in []byte) ([]Q, int, error) {
	b := in[:]
	var qs []Q
	for len(b) > 0 {
	for len(b) > 0 && isSpace(b[0]) {
	b = b[1:]
	}
	tok, _ := nextToken(b)
	if tok != nil && tok.Type == tokParenClose {
	break
	} else if tok != nil && tok.Type == tokOr {
	qs = append(qs, &orOperator{})
	b = b[len(tok.Input):]
	continue
	}

	q, n, err := parseExpr(b)
	if err != nil {
	return nil, 0, err
	}

	if q == nil {
	// eof or a ')'
	break
	}
	qs = append(qs, q)
	b = b[n:]
	}

	setCase := "auto"
	newQS := qs[:0]
	for _, q := range qs {
	if sc, ok := q.(*caseQ); ok {
	setCase = sc.Flavor
	} else {
	newQS = append(newQS, q)
	}
	}
	qs = mapQueryList(newQS, func(q Q) Q {
	if sc, ok := q.(setCaser); ok {
	sc.setCase(setCase)
	}
	return q
	})
	return qs, len(in) - len(b), nil
	}

	type token struct {
	Type int
	// The value of the token
	Text []byte

	// The input that we consumed to form the token.
	Input []byte
	}

	func (t *token) String() string {
	return fmt.Sprintf("%s:%q", tokNames[t.Type], t.Text)
	}

	// token types.
	const (
	tokText = 0
	tokFile = 1
	tokRepo = 2
	tokCase = 3
	tokBranch = 4
	tokParenOpen = 5
	tokParenClose = 6
	tokError = 7
	tokNegate = 8
	tokRegex = 9
	tokOr = 10
	tokContent = 11
	tokLang = 12
	tokSym = 13
	)

	var tokNames = map[int]string{
	tokBranch: "Branch",
	tokCase: "Case",
	tokError: "Error",
	tokFile: "File",
	tokNegate: "Negate",
	tokOr: "Or",
	tokParenClose: "ParenClose",
	tokParenOpen: "ParenOpen",
	tokRegex: "Regex",
	tokRepo: "Repo",
	tokText: "Text",
	tokLang: "Language",
	tokSym: "Symbol",
	}

	var prefixes = map[string]int{
	"b:": tokBranch,
	"branch:": tokBranch,
	"c:": tokContent,
	"case:": tokCase,
	"content:": tokContent,
	"f:": tokFile,
	"file:": tokFile,
	"r:": tokRepo,
	"regex:": tokRegex,
	"repo:": tokRepo,
	"lang:": tokLang,
	"sym:": tokSym,
	}

	var reservedWords = map[string]int{
	"or": tokOr,
	}

	func (t *token) setType() {
	// After we consumed the input, we have to interpret some of the text,
	// eg. to distinguish between ")" the text and ) the query grouping
	// parenthesis.
	if len(t.Text) == 1 && t.Text[0] == '(' {
	t.Type = tokParenOpen
	}
	if len(t.Text) == 1 && t.Text[0] == ')' {
	t.Type = tokParenClose
	}

	for w, typ := range reservedWords {
	if string(t.Text) == w && string(t.Input) == w {
	t.Type = typ
	break
	}
	}

	for pref, typ := range prefixes {
	if !bytes.HasPrefix(t.Input, []byte(pref)) {
	continue
	}

	t.Text = t.Text[len(pref):]
	t.Type = typ
	break
	}
	}

	// nextToken returns the next token from the given input.
	func nextToken(in []byte) (*token, error) {
	left := in[:]
	parenCount := 0
	var cur token
	if len(left) == 0 {
	return nil, nil
	}

	if left[0] == '-' {
	return &token{
	Type: tokNegate,
	Text: []byte{'-'},
	Input: in[:1],
	}, nil
	}

	foundSpace := false

	loop:
	for len(left) > 0 {
	c := left[0]
	switch c {
	case '(':
	parenCount++
	cur.Text = append(cur.Text, c)
	left = left[1:]
	case ')':
	if parenCount == 0 {
	if len(cur.Text) == 0 {
	cur.Text = []byte{')'}
	left = left[1:]
	}
	break loop
	}

	cur.Text = append(cur.Text, c)
	left = left[1:]
	parenCount--

	case '"':
	t, n, err := parseStringLiteral(left)
	if err != nil {
	return nil, err
	}
	cur.Text = append(cur.Text, t...)
	left = left[n:]
	case '\\':
	left = left[1:]
	if len(left) == 0 {
	return nil, fmt.Errorf("query: lone \\ at end")
	}
	c := left[0]
	cur.Text = append(cur.Text, '\\', c)
	left = left[1:]

	case ' ', '\n', '\t':
	if parenCount > 0 {
	foundSpace = true
	}
	break loop
	default:
	cur.Text = append(cur.Text, c)
	left = left[1:]
	}
	}

	if len(cur.Text) == 0 {
	return nil, nil
	}

	if foundSpace && cur.Text[0] == '(' {
	cur.Text = cur.Text[:1]
	cur.Input = in[:1]
	} else {
	cur.Input = in[:len(in)-len(left)]
	}
	cur.setType()
	return &cur, nil
	}