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		for {
   193			c, err = p.parseOperand()
   194			if err != nil {
   195				return
   196			}
   197			switch p.peek().typ {
   198			case tokenAnd:
   199				p.next()
   200			case tokenOr, tokenClose, tokenEOF:
   201				return
   202			}
   203			return p.parseAndRHS(c)
   204		}
   205	}
   206	
   207	func (p *parser) parseAndRHS(lhs *Constraint) (c *Constraint, err error) {
   208		var rhs *Constraint
   209		c = lhs
   210		for {
   211			rhs, err = p.parseOperand()
   212			if err != nil {
   213				return
   214			}
   215			c = andConst(c, rhs)
   216			switch p.peek().typ {
   217			case tokenOr, tokenClose, tokenEOF:
   218				return
   219			case tokenAnd:
   220				p.next()
   221				continue
   222			}
   223			return
   224		}
   225	}
   226	
   227	func (p *parser) parseOperand() (c *Constraint, err error) {
   228		negated := p.stripNot()
   229		i := p.peek()
   230		switch i.typ {
   231		case tokenError:
   232			err = newParseExpError(i.val, *i)
   233			return
   234		case tokenEOF:
   235			err = newParseExpError(expectedAtom, *i)
   236			return
   237		case tokenClose:
   238			err = newParseExpError(noMatchingOpening, *i)
   239			return
   240		case tokenLiteral, tokenQuotedLiteral, tokenPredicate, tokenColon, tokenArg:
   241			c, err = p.parseAtom()
   242		case tokenOpen:
   243			c, err = p.parseGroup()
   244		}
   245		if err != nil {
   246			return
   247		}
   248		if negated {
   249			c = notConst(c)
   250		}
   251		return
   252	}
   253	
   254	// AtomWords returns the parsed atom, the starting position of this
   255	// atom and an error.
   256	func (p *parser) atomWords() (a atom, start int, err error) {
   257		i := p.peek()
   258		start = i.start
   259		a = atom{}
   260		switch i.typ {
   261		case tokenLiteral:
   262			err = newParseExpError(noLiteralSupport, *i)
   263			return
   264		case tokenQuotedLiteral:
   265			err = newParseExpError(noQuotedLiteralSupport, *i)
   266			return
   267		case tokenColon:
   268			err = newParseExpError(predicateError, *i)
   269			return
   270		case tokenPredicate:
   271			i := p.next()
   272			a.predicate = i.val
   273		}
   274		for {
   275			switch p.peek().typ {
   276			case tokenColon:
   277				p.next()
   278				continue
   279			case tokenArg:
   280				i := p.next()
   281				a.args = append(a.args, i.val)
   282				continue
   283			case tokenQuotedArg:
   284				i := p.next()
   285				var uq string
   286				uq, err = strconv.Unquote(i.val)
   287				if err != nil {
   288					return
   289				}
   290				a.args = append(a.args, uq)
   291				continue
   292			}
   293			return
   294		}
   295	}
   296	
   297	func (p *parser) parseAtom() (*Constraint, error) {
   298		a, start, err := p.atomWords()
   299		if err != nil {
   300			return nil, err
   301		}
   302		faultToken := func() token {
   303			return token{
   304				typ:   tokenError,
   305				val:   a.String(),
   306				start: start,
   307			}
   308		}
   309		var c *Constraint
   310		for _, k := range keywords {
   311			matched, err := k.Match(a)
   312			if err != nil {
   313				return nil, newParseExpError(err.Error(), faultToken())
   314			}
   315			if matched {
   316				c, err = k.Predicate(p.ctx, a.args)
   317				if err != nil {
   318					return nil, newParseExpError(err.Error(), faultToken())
   319				}
   320				return c, nil
   321			}
   322		}
   323		t := faultToken()
   324		err = newParseExpError(fmt.Sprintf("Unknown search predicate: %q", t.val), t)
   325		log.Printf(err.Error())
   326		return nil, err
   327	}
   328	
   329	func parseExpression(ctx context.Context, exp string) (*SearchQuery, error) {
   330		base := &Constraint{
   331			Permanode: &PermanodeConstraint{
   332				SkipHidden: true,
   333			},
   334		}
   335		sq := &SearchQuery{
   336			Constraint: base,
   337		}
   338	
   339		exp = strings.TrimSpace(exp)
   340		if exp == "" {
   341			return sq, nil
   342		}
   343		p := newParser(ctx, exp)
   344	
   345		c, err := p.parseExp()
   346		if err != nil {
   347			return nil, err
   348		}
   349		lastToken := p.next()
   350		if lastToken.typ != tokenEOF {
   351			switch lastToken.typ {
   352			case tokenClose:
   353				return nil, newParseExpError(noMatchingOpening, *lastToken)
   354			}
   355			return nil, newParseExpError(trailingTokens, *lastToken)
   356		}
   357		if c != nil {
   358			sq.Constraint = andConst(base, c)
   359		}
   360		return sq, nil
   361	}