selector.go

Documentation: github.com/go-kivik/kivik/v4/x/mango

     1  // Licensed under the Apache License, Version 2.0 (the "License"); you may not
     2  // use this file except in compliance with the License. You may obtain a copy of
     3  // the License at
     4  //
     5  //  http://www.apache.org/licenses/LICENSE-2.0
     6  //
     7  // Unless required by applicable law or agreed to in writing, software
     8  // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
     9  // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
    10  // License for the specific language governing permissions and limitations under
    11  // the License.
    12  
    13  // Package mango provides a Mango query language parser and evaluator.
    14  package mango
    15  
    16  import (
    17  	"fmt"
    18  	"regexp"
    19  	"strings"
    20  
    21  	"github.com/go-kivik/kivik/v4/x/collate"
    22  )
    23  
    24  // Node represents a node in the Mango Selector.
    25  type Node interface {
    26  	Op() Operator
    27  	Value() interface{}
    28  	String() string
    29  	Match(interface{}) bool
    30  }
    31  
    32  type notNode struct {
    33  	sel Node
    34  }
    35  
    36  var _ Node = (*notNode)(nil)
    37  
    38  func (*notNode) Op() Operator {
    39  	return OpNot
    40  }
    41  
    42  func (n *notNode) Value() interface{} {
    43  	return n.sel
    44  }
    45  
    46  func (n *notNode) String() string {
    47  	return fmt.Sprintf("%s %s", OpNot, n.sel)
    48  }
    49  
    50  func (n *notNode) Match(doc interface{}) bool {
    51  	return !n.sel.Match(doc)
    52  }
    53  
    54  type combinationNode struct {
    55  	op  Operator
    56  	sel []Node
    57  }
    58  
    59  var _ Node = (*combinationNode)(nil)
    60  
    61  func (c *combinationNode) Op() Operator {
    62  	return c.op
    63  }
    64  
    65  func (c *combinationNode) Value() interface{} {
    66  	return c.sel
    67  }
    68  
    69  func (c *combinationNode) String() string {
    70  	var sb strings.Builder
    71  	sb.WriteString(string(c.op))
    72  	sb.WriteString(" [")
    73  	for i, sel := range c.sel {
    74  		if i > 0 {
    75  			sb.WriteString(", ")
    76  		}
    77  		sb.WriteString(fmt.Sprintf("%v", sel))
    78  	}
    79  	sb.WriteString("]")
    80  	return sb.String()
    81  }
    82  
    83  func (c *combinationNode) Match(doc interface{}) bool {
    84  	switch c.op {
    85  	case OpAnd:
    86  		for _, sel := range c.sel {
    87  			if !sel.Match(doc) {
    88  				return false
    89  			}
    90  		}
    91  		return true
    92  	case OpOr:
    93  		for _, sel := range c.sel {
    94  			if sel.Match(doc) {
    95  				return true
    96  			}
    97  		}
    98  		return false
    99  	case OpNor:
   100  		for _, sel := range c.sel {
   101  			if sel.Match(doc) {
   102  				return false
   103  			}
   104  		}
   105  		return true
   106  	}
   107  	panic("not implemented")
   108  }
   109  
   110  type fieldNode struct {
   111  	field string
   112  	cond  Node
   113  }
   114  
   115  var _ Node = (*fieldNode)(nil)
   116  
   117  func (f *fieldNode) Op() Operator {
   118  	return f.cond.Op()
   119  }
   120  
   121  func (f *fieldNode) Value() interface{} {
   122  	return f.cond.Value()
   123  }
   124  
   125  func (f *fieldNode) String() string {
   126  	return fmt.Sprintf("%s %s", f.field, f.cond.String())
   127  }
   128  
   129  func (f *fieldNode) Match(doc interface{}) bool {
   130  	val := doc
   131  
   132  	// Traverse nested fields (e.g. "foo.bar.baz")
   133  	segments := SplitKeys(f.field)
   134  	for _, segment := range segments {
   135  		m, ok := val.(map[string]interface{})
   136  		if !ok {
   137  			return false
   138  		}
   139  
   140  		val = m[segment]
   141  	}
   142  
   143  	// Even if the field does not exist we need to pass it to the condition expression because of `$exists`
   144  	return f.cond.Match(val)
   145  }
   146  
   147  type conditionNode struct {
   148  	op   Operator
   149  	cond interface{}
   150  }
   151  
   152  var _ Node = (*conditionNode)(nil)
   153  
   154  func (e *conditionNode) Op() Operator {
   155  	return e.op
   156  }
   157  
   158  func (e *conditionNode) Value() interface{} {
   159  	return e.cond
   160  }
   161  
   162  func (e *conditionNode) String() string {
   163  	return fmt.Sprintf("%s %v", e.op, e.cond)
   164  }
   165  
   166  func (e *conditionNode) Match(doc interface{}) bool {
   167  	switch e.op {
   168  	case OpEqual:
   169  		return collate.CompareObject(doc, e.cond) == 0
   170  	case OpNotEqual:
   171  		return collate.CompareObject(doc, e.cond) != 0
   172  	case OpLessThan:
   173  		return collate.CompareObject(doc, e.cond) < 0
   174  	case OpLessThanOrEqual:
   175  		return collate.CompareObject(doc, e.cond) <= 0
   176  	case OpGreaterThan:
   177  		return collate.CompareObject(doc, e.cond) > 0
   178  	case OpGreaterThanOrEqual:
   179  		return collate.CompareObject(doc, e.cond) >= 0
   180  	case OpExists:
   181  		return (doc != nil) == e.cond.(bool)
   182  	case OpType:
   183  		switch tp := e.cond.(string); tp {
   184  		case "null":
   185  			return doc == nil
   186  		case "boolean":
   187  			_, ok := doc.(bool)
   188  			return ok
   189  		case "number":
   190  			_, ok := doc.(float64)
   191  			return ok
   192  		case "string":
   193  			_, ok := doc.(string)
   194  			return ok
   195  		case "array":
   196  			_, ok := doc.([]interface{})
   197  			return ok
   198  		case "object":
   199  			_, ok := doc.(map[string]interface{})
   200  			return ok
   201  		default:
   202  			panic("unexpected $type value: " + tp)
   203  		}
   204  	case OpIn:
   205  		for _, v := range e.cond.([]interface{}) {
   206  			if collate.CompareObject(doc, v) == 0 {
   207  				return true
   208  			}
   209  		}
   210  		return false
   211  	case OpNotIn:
   212  		for _, v := range e.cond.([]interface{}) {
   213  			if collate.CompareObject(doc, v) == 0 {
   214  				return false
   215  			}
   216  		}
   217  		return true
   218  	case OpSize:
   219  		array, ok := doc.([]interface{})
   220  		if !ok {
   221  			return false
   222  		}
   223  		return float64(len(array)) == e.cond.(float64)
   224  	case OpMod:
   225  		num, ok := doc.(float64)
   226  		if !ok {
   227  			return false
   228  		}
   229  		if num != float64(int(num)) {
   230  			return false
   231  		}
   232  		mod := e.cond.([2]int64)
   233  		return int64(num)%mod[0] == mod[1]
   234  	case OpRegex:
   235  		str, ok := doc.(string)
   236  		if !ok {
   237  			return false
   238  		}
   239  		return e.cond.(*regexp.Regexp).MatchString(str)
   240  	case OpAll:
   241  		array, ok := doc.([]interface{})
   242  		if !ok {
   243  			return false
   244  		}
   245  		for _, v := range e.cond.([]interface{}) {
   246  			if !contains(array, v) {
   247  				return false
   248  			}
   249  		}
   250  		return true
   251  	}
   252  	return false
   253  }
   254  
   255  func contains(haystack []interface{}, needle interface{}) bool {
   256  	for _, v := range haystack {
   257  		if collate.CompareObject(v, needle) == 0 {
   258  			return true
   259  		}
   260  	}
   261  	return false
   262  }
   263  
   264  type elementNode struct {
   265  	op   Operator
   266  	cond *conditionNode
   267  }
   268  
   269  var _ Node = (*elementNode)(nil)
   270  
   271  func (e *elementNode) Op() Operator {
   272  	return e.op
   273  }
   274  
   275  func (e *elementNode) Value() interface{} {
   276  	return e.cond
   277  }
   278  
   279  func (e *elementNode) String() string {
   280  	return fmt.Sprintf("%s {%s}", e.op, e.cond)
   281  }
   282  
   283  func (e *elementNode) Match(doc interface{}) bool {
   284  	switch e.op {
   285  	case OpElemMatch:
   286  		array, ok := doc.([]interface{})
   287  		if !ok {
   288  			return false
   289  		}
   290  		for _, v := range array {
   291  			if e.cond.Match(v) {
   292  				return true
   293  			}
   294  		}
   295  		return false
   296  	case OpAllMatch:
   297  		array, ok := doc.([]interface{})
   298  		if !ok {
   299  			return false
   300  		}
   301  		for _, v := range array {
   302  			if !e.cond.Match(v) {
   303  				return false
   304  			}
   305  		}
   306  		return true
   307  	case OpKeyMapMatch:
   308  		object, ok := doc.(map[string]interface{})
   309  		if !ok {
   310  			return false
   311  		}
   312  		for k := range object {
   313  			if k == e.cond.cond.(string) {
   314  				return e.cond.Match(k)
   315  			}
   316  		}
   317  		return false
   318  	}
   319  	panic("unready")
   320  }
   321  
   322  // cmpValues compares two arbitrary values by converting them to strings.
   323  func cmpValues(a, b interface{}) int {
   324  	return strings.Compare(fmt.Sprintf("%v", a), fmt.Sprintf("%v", b))
   325  }
   326  
   327  // cmpSelectors compares two selectors, for ordering.
   328  func cmpSelectors(a, b Node) int {
   329  	// Naively sort operators alphabetically.
   330  	if c := strings.Compare(string(a.Op()), string(b.Op())); c != 0 {
   331  		return c
   332  	}
   333  	switch t := a.(type) {
   334  	case *notNode:
   335  		u := b.(*notNode)
   336  		return cmpSelectors(t.sel, u.sel)
   337  	case *combinationNode:
   338  		u := b.(*combinationNode)
   339  		for i := 0; i < len(t.sel) && i < len(u.sel); i++ {
   340  			if c := cmpSelectors(t.sel[i], u.sel[i]); c != 0 {
   341  				return c
   342  			}
   343  		}
   344  		return len(t.sel) - len(u.sel)
   345  	case *fieldNode:
   346  		u := b.(*fieldNode)
   347  		if c := strings.Compare(t.field, u.field); c != 0 {
   348  			return c
   349  		}
   350  		return cmpSelectors(t.cond, u.cond)
   351  	case *conditionNode:
   352  		u := b.(*conditionNode)
   353  		switch t.op {
   354  		case OpIn, OpNotIn:
   355  			for i := 0; i < len(t.cond.([]interface{})) && i < len(u.cond.([]interface{})); i++ {
   356  				if c := cmpValues(t.cond.([]interface{})[i], u.cond.([]interface{})[i]); c != 0 {
   357  					return c
   358  				}
   359  			}
   360  			return len(t.cond.([]interface{})) - len(u.cond.([]interface{}))
   361  		case OpMod:
   362  			tm := t.cond.([2]int)
   363  			um := u.cond.([2]int)
   364  			if tm[0] != um[0] {
   365  				return tm[0] - um[0]
   366  			}
   367  			return tm[1] - um[1]
   368  		default:
   369  			return cmpValues(t.cond, u.cond)
   370  		}
   371  	}
   372  	return 0
   373  }
   374  
   375  // SplitKeys splits a field into its component keys. For example,
   376  // "foo.bar" is split into `["foo", "bar"]`. Escaped dots are not treated
   377  // as separators, so `"foo\\.bar"` becomes `["foo.bar"]`.
   378  func SplitKeys(field string) []string {
   379  	var escaped bool
   380  	result := []string{}
   381  	word := make([]byte, 0, len(field))
   382  	for _, ch := range field {
   383  		if escaped {
   384  			word = append(word, byte(ch))
   385  			escaped = false
   386  			continue
   387  		}
   388  		if ch == '\\' {
   389  			escaped = true
   390  			continue
   391  		}
   392  		if ch == '.' {
   393  			result = append(result, string(word))
   394  			word = word[:0]
   395  			continue
   396  		}
   397  		word = append(word, byte(ch))
   398  	}
   399  	if escaped {
   400  		word = append(word, '\\')
   401  	}
   402  	return append(result, string(word))
   403  }
   404
View as plain text