1	/*
     2	Copyright 2013 The Perkeep Authors
     3	
     4	Licensed under the Apache License, Version 2.0 (the "License");
     5	you may not use this file except in compliance with the License.
     6	You may obtain a copy of the License at
     7	
     8	     http://www.apache.org/licenses/LICENSE-2.0
     9	
    10	Unless required by applicable law or agreed to in writing, software
    11	distributed under the License is distributed on an "AS IS" BASIS,
    12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	See the License for the specific language governing permissions and
    14	limitations under the License.
    15	*/
    16	
    17	package search
    18	
    19	import (
    20		"context"
    21		"fmt"
    22		"log"
    23		"strconv"
    24		"strings"
    25	)
    26	
    27	const seeDocs = "\nSee: https://perkeep.org/doc/search-ui"
    28	
    29	var (
    30		noMatchingOpening      = "No matching opening parenthesis"
    31		noMatchingClosing      = "No matching closing parenthesis"
    32		noLiteralSupport       = "No support for literals yet"
    33		noQuotedLiteralSupport = "No support for quoted literals yet"
    34		expectedAtom           = "Expected an atom"
    35		predicateError         = "Predicates do not start with a colon"
    36		trailingTokens         = "After parsing finished there is still input left"
    37	)
    38	
    39	type parseExpError struct {
    40		mesg string
    41		t    token
    42	}
    43	
    44	func (e parseExpError) Error() string {
    45		return fmt.Sprintf("%s at position %d, token: %q %s", e.mesg, e.t.start, e.t.val, seeDocs)
    46	}
    47	
    48	func newParseExpError(mesg string, t token) error {
    49		return parseExpError{mesg: mesg, t: t}
    50	}
    51	
    52	func andConst(a, b *Constraint) *Constraint {
    53		return &Constraint{
    54			Logical: &LogicalConstraint{
    55				Op: "and",
    56				A:  a,
    57				B:  b,
    58			},
    59		}
    60	}
    61	
    62	func orConst(a, b *Constraint) *Constraint {
    63		return &Constraint{
    64			Logical: &LogicalConstraint{
    65				Op: "or",
    66				A:  a,
    67				B:  b,
    68			},
    69		}
    70	}
    71	
    72	func notConst(a *Constraint) *Constraint {
    73		return &Constraint{
    74			Logical: &LogicalConstraint{
    75				Op: "not",
    76				A:  a,
    77			},
    78		}
    79	}
    80	
    81	type parser struct {
    82		tokens chan token
    83		peeked *token
    84		ctx    context.Context
    85	}
    86	
    87	func newParser(ctx context.Context, exp string) parser {
    88		_, tokens := lex(exp)
    89		return parser{tokens: tokens, ctx: ctx}
    90	}
    91	
    92	func (p *parser) next() *token {
    93		if p.peeked != nil {
    94			t := p.peeked
    95			p.peeked = nil
    96			return t
    97		}
    98		return p.readInternal()
    99	}
   100	
   101	func (p *parser) peek() *token {
   102		if p.peeked == nil {
   103			p.peeked = p.readInternal()
   104		}
   105		return p.peeked
   106	}
   107	
   108	// ReadInternal should not be called directly, use 'next' or 'peek'
   109	func (p *parser) readInternal() *token {
   110		for t := range p.tokens {
   111			return &t
   112		}
   113		return &token{tokenEOF, "", -1}
   114	}
   115	
   116	func (p *parser) stripNot() (negated bool) {
   117		for {
   118			switch p.peek().typ {
   119			case tokenNot:
   120				p.next()
   121				negated = !negated
   122				continue
   123			}
   124			return negated
   125		}
   126	}
   127	
   128	func (p *parser) parseExp() (c *Constraint, err error) {
   129		if p.peek().typ == tokenEOF {
   130			return
   131		}
   132		c, err = p.parseOperand()
   133		if err != nil {
   134			return
   135		}
   136		for {
   137			switch p.peek().typ {
   138			case tokenAnd:
   139				p.next()
   140			case tokenOr:
   141				p.next()
   142				return p.parseOrRHS(c)
   143			case tokenClose, tokenEOF:
   144				return
   145			}
   146			c, err = p.parseAndRHS(c)
   147			if err != nil {
   148				return
   149			}
   150		}
   151	}
   152	
   153	func (p *parser) parseGroup() (c *Constraint, err error) {
   154		i := p.next()
   155		switch i.typ {
   156		case tokenOpen:
   157			c, err = p.parseExp()
   158			if err != nil {
   159				return
   160			}
   161			if p.peek().typ == tokenClose {
   162				p.next()
   163				return
   164			} else {
   165				err = newParseExpError(noMatchingClosing, *i)
   166				return
   167			}
   168		}
   169		err = newParseExpError("internal: do not call parseGroup when not on a '('", *i)
   170		return
   171	}
   172	
   173	func (p *parser) parseOrRHS(lhs *Constraint) (c *Constraint, err error) {
   174		var rhs *Constraint
   175		c = lhs
   176		for {
   177			rhs, err = p.parseAnd()
   178			if err != nil {
   179				return
   180			}
   181			c = orConst(c, rhs)
   182			switch p.peek().typ {
   183			case tokenOr:
   184				p.next()
   185			case tokenAnd, tokenClose, tokenEOF:
   186				return
   187			}
   188		}
   189	}
   190	
   191	func (p *parser) parseAnd() (c *Constraint, err error) {
   192		c, err = p.parseOperand()
   193		if err != nil {
   194			return
   195		}
   196		switch p.peek().typ {
   197		case tokenAnd:
   198			p.next()
   199		case tokenOr, tokenClose, tokenEOF:
   200			return
   201		}
   202		return p.parseAndRHS(c)
   203	}
   204	
   205	func (p *parser) parseAndRHS(lhs *Constraint) (c *Constraint, err error) {
   206		var rhs *Constraint
   207		c = lhs
   208		for {
   209			rhs, err = p.parseOperand()
   210			if err != nil {
   211				return
   212			}
   213			c = andConst(c, rhs)
   214			switch p.peek().typ {
   215			case tokenOr, tokenClose, tokenEOF:
   216				return
   217			case tokenAnd:
   218				p.next()
   219				continue
   220			}
   221			return
   222		}
   223	}
   224	
   225	func (p *parser) parseOperand() (c *Constraint, err error) {
   226		negated := p.stripNot()
   227		i := p.peek()
   228		switch i.typ {
   229		case tokenError:
   230			err = newParseExpError(i.val, *i)
   231			return
   232		case tokenEOF:
   233			err = newParseExpError(expectedAtom, *i)
   234			return
   235		case tokenClose:
   236			err = newParseExpError(noMatchingOpening, *i)
   237			return
   238		case tokenLiteral, tokenQuotedLiteral, tokenPredicate, tokenColon, tokenArg:
   239			c, err = p.parseAtom()
   240		case tokenOpen:
   241			c, err = p.parseGroup()
   242		}
   243		if err != nil {
   244			return
   245		}
   246		if negated {
   247			c = notConst(c)
   248		}
   249		return
   250	}
   251	
   252	// AtomWords returns the parsed atom, the starting position of this
   253	// atom and an error.
   254	func (p *parser) atomWords() (a atom, start int, err error) {
   255		i := p.peek()
   256		start = i.start
   257		a = atom{}
   258		switch i.typ {
   259		case tokenLiteral:
   260			err = newParseExpError(noLiteralSupport, *i)
   261			return
   262		case tokenQuotedLiteral:
   263			err = newParseExpError(noQuotedLiteralSupport, *i)
   264			return
   265		case tokenColon:
   266			err = newParseExpError(predicateError, *i)
   267			return
   268		case tokenPredicate:
   269			i := p.next()
   270			a.predicate = i.val
   271		}
   272		for {
   273			switch p.peek().typ {
   274			case tokenColon:
   275				p.next()
   276				continue
   277			case tokenArg:
   278				i := p.next()
   279				a.args = append(a.args, i.val)
   280				continue
   281			case tokenQuotedArg:
   282				i := p.next()
   283				var uq string
   284				uq, err = strconv.Unquote(i.val)
   285				if err != nil {
   286					return
   287				}
   288				a.args = append(a.args, uq)
   289				continue
   290			}
   291			return
   292		}
   293	}
   294	
   295	func (p *parser) parseAtom() (*Constraint, error) {
   296		a, start, err := p.atomWords()
   297		if err != nil {
   298			return nil, err
   299		}
   300		faultToken := func() token {
   301			return token{
   302				typ:   tokenError,
   303				val:   a.String(),
   304				start: start,
   305			}
   306		}
   307		var c *Constraint
   308		for _, k := range keywords {
   309			matched, err := k.Match(a)
   310			if err != nil {
   311				return nil, newParseExpError(err.Error(), faultToken())
   312			}
   313			if matched {
   314				c, err = k.Predicate(p.ctx, a.args)
   315				if err != nil {
   316					return nil, newParseExpError(err.Error(), faultToken())
   317				}
   318				return c, nil
   319			}
   320		}
   321		t := faultToken()
   322		err = newParseExpError(fmt.Sprintf("Unknown search predicate: %q", t.val), t)
   323		log.Printf("parsing search expression atom: %v", err)
   324		return nil, err
   325	}
   326	
   327	func parseExpression(ctx context.Context, exp string) (*SearchQuery, error) {
   328		base := &Constraint{
   329			Permanode: &PermanodeConstraint{
   330				SkipHidden: true,
   331			},
   332		}
   333		sq := &SearchQuery{
   334			Constraint: base,
   335		}
   336	
   337		exp = strings.TrimSpace(exp)
   338		if exp == "" {
   339			return sq, nil
   340		}
   341		p := newParser(ctx, exp)
   342	
   343		c, err := p.parseExp()
   344		if err != nil {
   345			return nil, err
   346		}
   347		lastToken := p.next()
   348		if lastToken.typ != tokenEOF {
   349			switch lastToken.typ {
   350			case tokenClose:
   351				return nil, newParseExpError(noMatchingOpening, *lastToken)
   352			}
   353			return nil, newParseExpError(trailingTokens, *lastToken)
   354		}
   355		if c != nil {
   356			sq.Constraint = andConst(base, c)
   357		}
   358		return sq, nil
   359	}