| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2015 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 package memory | |
| 6 | |
| 7 import ( | |
| 8 "bytes" | |
| 9 "errors" | |
| 10 "fmt" | |
| 11 "math" | |
| 12 "strings" | |
| 13 | |
| 14 ds "github.com/luci/gae/service/datastore" | |
| 15 "github.com/luci/gkvlite" | |
| 16 "github.com/luci/luci-go/common/cmpbin" | |
| 17 ) | |
| 18 | |
| 19 type qDirection bool | |
| 20 | |
| 21 const ( | |
| 22 qASC qDirection = true | |
| 23 qDEC = false | |
| 24 ) | |
| 25 | |
| 26 var builtinQueryPrefix = []byte{0} | |
| 27 var complexQueryPrefix = []byte{1} | |
| 28 | |
| 29 type qSortBy struct { | |
| 30 prop string | |
| 31 dir qDirection | |
| 32 } | |
| 33 | |
| 34 func (q qSortBy) WriteBinary(buf *bytes.Buffer) { | |
| 35 if q.dir == qASC { | |
| 36 buf.WriteByte(0) | |
| 37 } else { | |
| 38 buf.WriteByte(1) | |
| 39 } | |
| 40 cmpbin.WriteString(buf, q.prop) | |
| 41 } | |
| 42 | |
| 43 func (q *qSortBy) ReadBinary(buf *bytes.Buffer) error { | |
| 44 dir, err := buf.ReadByte() | |
| 45 if err != nil { | |
| 46 return err | |
| 47 } | |
| 48 q.dir = dir == 0 | |
| 49 q.prop, _, err = cmpbin.ReadString(buf) | |
| 50 return err | |
| 51 } | |
| 52 | |
| 53 type qIndex struct { | |
| 54 kind string | |
| 55 ancestor bool | |
| 56 sortby []qSortBy | |
| 57 } | |
| 58 | |
| 59 func (i *qIndex) Builtin() bool { | |
| 60 return !i.ancestor && len(i.sortby) <= 1 | |
| 61 } | |
| 62 | |
| 63 func (i *qIndex) Less(o *qIndex) bool { | |
| 64 ibuf, obuf := &bytes.Buffer{}, &bytes.Buffer{} | |
| 65 i.WriteBinary(ibuf) | |
| 66 o.WriteBinary(obuf) | |
| 67 return i.String() < o.String() | |
| 68 } | |
| 69 | |
| 70 // Valid verifies that this qIndex doesn't have duplicate sortBy fields. | |
| 71 func (i *qIndex) Valid() bool { | |
| 72 names := map[string]bool{} | |
| 73 for _, sb := range i.sortby { | |
| 74 if names[sb.prop] { | |
| 75 return false | |
| 76 } | |
| 77 names[sb.prop] = true | |
| 78 } | |
| 79 return true | |
| 80 } | |
| 81 | |
| 82 func (i *qIndex) WriteBinary(buf *bytes.Buffer) { | |
| 83 // TODO(riannucci): do a Grow call here? | |
| 84 if i.Builtin() { | |
| 85 buf.Write(builtinQueryPrefix) | |
| 86 } else { | |
| 87 buf.Write(complexQueryPrefix) | |
| 88 } | |
| 89 cmpbin.WriteString(buf, i.kind) | |
| 90 if i.ancestor { | |
| 91 buf.WriteByte(0) | |
| 92 } else { | |
| 93 buf.WriteByte(1) | |
| 94 } | |
| 95 cmpbin.WriteUint(buf, uint64(len(i.sortby))) | |
| 96 for _, sb := range i.sortby { | |
| 97 sb.WriteBinary(buf) | |
| 98 } | |
| 99 } | |
| 100 | |
| 101 func (i *qIndex) String() string { | |
| 102 ret := &bytes.Buffer{} | |
| 103 if i.Builtin() { | |
| 104 ret.WriteRune('B') | |
| 105 } else { | |
| 106 ret.WriteRune('C') | |
| 107 } | |
| 108 ret.WriteRune(':') | |
| 109 ret.WriteString(i.kind) | |
| 110 if i.ancestor { | |
| 111 ret.WriteString("|A") | |
| 112 } | |
| 113 for _, sb := range i.sortby { | |
| 114 ret.WriteRune('/') | |
| 115 if sb.dir == qDEC { | |
| 116 ret.WriteRune('-') | |
| 117 } | |
| 118 ret.WriteString(sb.prop) | |
| 119 } | |
| 120 return ret.String() | |
| 121 } | |
| 122 | |
| 123 func (i *qIndex) ReadBinary(buf *bytes.Buffer) error { | |
| 124 // discard builtin/complex byte | |
| 125 _, err := buf.ReadByte() | |
| 126 if err != nil { | |
| 127 return err | |
| 128 } | |
| 129 | |
| 130 i.kind, _, err = cmpbin.ReadString(buf) | |
| 131 if err != nil { | |
| 132 return err | |
| 133 } | |
| 134 anc, err := buf.ReadByte() | |
| 135 if err != nil { | |
| 136 return err | |
| 137 } | |
| 138 i.ancestor = anc == 1 | |
| 139 | |
| 140 numSorts, _, err := cmpbin.ReadUint(buf) | |
| 141 if err != nil { | |
| 142 return err | |
| 143 } | |
| 144 if numSorts > 64 { | |
| 145 return fmt.Errorf("qIndex.ReadBinary: Got over 64 sort orders: %
d", numSorts) | |
| 146 } | |
| 147 i.sortby = make([]qSortBy, numSorts) | |
| 148 for idx := range i.sortby { | |
| 149 err = (&i.sortby[idx]).ReadBinary(buf) | |
| 150 if err != nil { | |
| 151 return err | |
| 152 } | |
| 153 } | |
| 154 | |
| 155 return nil | |
| 156 } | |
| 157 | |
| 158 type queryOp int | |
| 159 | |
| 160 const ( | |
| 161 qInvalid queryOp = iota | |
| 162 qEqual | |
| 163 qLessThan | |
| 164 qLessEq | |
| 165 qGreaterEq | |
| 166 qGreaterThan | |
| 167 ) | |
| 168 | |
| 169 func (o queryOp) isEQOp() bool { | |
| 170 return o == qEqual | |
| 171 } | |
| 172 | |
| 173 func (o queryOp) isINEQOp() bool { | |
| 174 return o >= qLessThan && o <= qGreaterThan | |
| 175 } | |
| 176 | |
| 177 var queryOpMap = map[string]queryOp{ | |
| 178 "=": qEqual, | |
| 179 "<": qLessThan, | |
| 180 "<=": qLessEq, | |
| 181 ">=": qGreaterEq, | |
| 182 ">": qGreaterThan, | |
| 183 } | |
| 184 | |
| 185 type queryFilter struct { | |
| 186 field string | |
| 187 op queryOp | |
| 188 value interface{} | |
| 189 } | |
| 190 | |
| 191 func parseFilter(f string, v interface{}) (ret queryFilter, err error) { | |
| 192 toks := strings.SplitN(strings.TrimSpace(f), " ", 2) | |
| 193 if len(toks) != 2 { | |
| 194 err = errors.New("datastore: invalid filter: " + f) | |
| 195 } else { | |
| 196 op := queryOpMap[toks[1]] | |
| 197 if op == qInvalid { | |
| 198 err = fmt.Errorf("datastore: invalid operator %q in filt
er %q", toks[1], f) | |
| 199 } else { | |
| 200 ret.field = toks[0] | |
| 201 ret.op = op | |
| 202 ret.value = v | |
| 203 } | |
| 204 } | |
| 205 return | |
| 206 } | |
| 207 | |
| 208 type queryOrder struct { | |
| 209 field string | |
| 210 direction qDirection | |
| 211 } | |
| 212 | |
| 213 type queryCursor string | |
| 214 | |
| 215 func (q queryCursor) String() string { return string(q) } | |
| 216 func (q queryCursor) Valid() bool { return q != "" } | |
| 217 | |
| 218 type queryImpl struct { | |
| 219 ns string | |
| 220 | |
| 221 kind string | |
| 222 ancestor ds.Key | |
| 223 filter []queryFilter | |
| 224 order []queryOrder | |
| 225 project []string | |
| 226 | |
| 227 distinct bool | |
| 228 eventualConsistency bool | |
| 229 keysOnly bool | |
| 230 limit int32 | |
| 231 offset int32 | |
| 232 | |
| 233 start queryCursor | |
| 234 end queryCursor | |
| 235 | |
| 236 err error | |
| 237 } | |
| 238 | |
| 239 var _ ds.Query = (*queryImpl)(nil) | |
| 240 | |
| 241 func (q *queryImpl) normalize() (ret *queryImpl) { | |
| 242 // ported from GAE SDK datastore_index.py;Normalize() | |
| 243 ret = q.clone() | |
| 244 | |
| 245 bs := newMemStore() | |
| 246 | |
| 247 eqProperties := bs.MakePrivateCollection(nil) | |
| 248 | |
| 249 ineqProperties := bs.MakePrivateCollection(nil) | |
| 250 | |
| 251 for _, f := range ret.filter { | |
| 252 // if we supported the IN operator, we would check to see if the
re were | |
| 253 // multiple value operands here, but the go SDK doesn't support
this. | |
| 254 if f.op.isEQOp() { | |
| 255 eqProperties.Set([]byte(f.field), []byte{}) | |
| 256 } else if f.op.isINEQOp() { | |
| 257 ineqProperties.Set([]byte(f.field), []byte{}) | |
| 258 } | |
| 259 } | |
| 260 | |
| 261 ineqProperties.VisitItemsAscend(nil, false, func(i *gkvlite.Item) bool { | |
| 262 eqProperties.Delete(i.Key) | |
| 263 return true | |
| 264 }) | |
| 265 | |
| 266 removeSet := bs.MakePrivateCollection(nil) | |
| 267 eqProperties.VisitItemsAscend(nil, false, func(i *gkvlite.Item) bool { | |
| 268 removeSet.Set(i.Key, []byte{}) | |
| 269 return true | |
| 270 }) | |
| 271 | |
| 272 newOrders := []queryOrder{} | |
| 273 for _, o := range ret.order { | |
| 274 if removeSet.Get([]byte(o.field)) == nil { | |
| 275 removeSet.Set([]byte(o.field), []byte{}) | |
| 276 newOrders = append(newOrders, o) | |
| 277 } | |
| 278 } | |
| 279 ret.order = newOrders | |
| 280 | |
| 281 // need to fix ret.filters if we ever support the EXISTS operator and/or | |
| 282 // projections. | |
| 283 // | |
| 284 // newFilters = [] | |
| 285 // for f in ret.filters: | |
| 286 // if f.op != qExists: | |
| 287 // newFilters = append(newFilters, f) | |
| 288 // if !removeSet.Has(f.field): | |
| 289 // removeSet.InsertNoReplace(f.field) | |
| 290 // newFilters = append(newFilters, f) | |
| 291 // | |
| 292 // so ret.filters == newFilters becuase none of ret.filters has op == qE
xists | |
| 293 // | |
| 294 // then: | |
| 295 // | |
| 296 // for prop in ret.project: | |
| 297 // if !removeSet.Has(prop): | |
| 298 // removeSet.InsertNoReplace(prop) | |
| 299 // ... make new EXISTS filters, add them to newFilters ... | |
| 300 // ret.filters = newFilters | |
| 301 // | |
| 302 // However, since we don't support projection queries, this is moot. | |
| 303 | |
| 304 if eqProperties.Get([]byte("__key__")) != nil { | |
| 305 ret.order = []queryOrder{} | |
| 306 } | |
| 307 | |
| 308 newOrders = []queryOrder{} | |
| 309 for _, o := range ret.order { | |
| 310 if o.field == "__key__" { | |
| 311 newOrders = append(newOrders, o) | |
| 312 break | |
| 313 } | |
| 314 newOrders = append(newOrders, o) | |
| 315 } | |
| 316 ret.order = newOrders | |
| 317 | |
| 318 return | |
| 319 } | |
| 320 | |
| 321 func (q *queryImpl) checkCorrectness(ns string, isTxn bool) (ret *queryImpl) { | |
| 322 // ported from GAE SDK datastore_stub_util.py;CheckQuery() | |
| 323 ret = q.clone() | |
| 324 | |
| 325 if ns != ret.ns { | |
| 326 ret.err = errors.New( | |
| 327 "gae/memory: Namespace mismatched. Query and Datastore d
on't agree " + | |
| 328 "on the current namespace") | |
| 329 return | |
| 330 } | |
| 331 | |
| 332 if ret.err != nil { | |
| 333 return | |
| 334 } | |
| 335 | |
| 336 // if projection && keys_only: | |
| 337 // "projection and keys_only cannot both be set" | |
| 338 | |
| 339 // if projection props match /^__.*__$/: | |
| 340 // "projections are not supported for the property: %(prop)s" | |
| 341 | |
| 342 if isTxn && ret.ancestor == nil { | |
| 343 ret.err = errors.New( | |
| 344 "gae/memory: Only ancestor queries are allowed inside tr
ansactions") | |
| 345 return | |
| 346 } | |
| 347 | |
| 348 numComponents := len(ret.filter) + len(ret.order) | |
| 349 if ret.ancestor != nil { | |
| 350 numComponents++ | |
| 351 } | |
| 352 if numComponents > 100 { | |
| 353 ret.err = errors.New( | |
| 354 "gae/memory: query is too large. may not have more than
" + | |
| 355 "100 filters + sort orders ancestor total") | |
| 356 } | |
| 357 | |
| 358 // if ret.ancestor.appid() != current appid | |
| 359 // "query app is x but ancestor app is x" | |
| 360 // if ret.ancestor.namespace() != current namespace | |
| 361 // "query namespace is x but ancestor namespace is x" | |
| 362 | |
| 363 // if not all(g in orders for g in group_by) | |
| 364 // "items in the group by clause must be specified first in the orderin
g" | |
| 365 | |
| 366 ineqPropName := "" | |
| 367 for _, f := range ret.filter { | |
| 368 if f.field == "__key__" { | |
| 369 k, ok := f.value.(ds.Key) | |
| 370 if !ok { | |
| 371 ret.err = errors.New( | |
| 372 "gae/memory: __key__ filter value must b
e a Key") | |
| 373 return | |
| 374 } | |
| 375 if !ds.KeyValid(k, false, globalAppID, q.ns) { | |
| 376 // See the comment in queryImpl.Ancestor; basica
lly this check | |
| 377 // never happens in the real env because the SDK
silently swallows | |
| 378 // this condition :/ | |
| 379 ret.err = ds.ErrInvalidKey | |
| 380 return | |
| 381 } | |
| 382 if k.Namespace() != ns { | |
| 383 ret.err = fmt.Errorf("bad namespace: %q (expecte
d %q)", k.Namespace(), ns) | |
| 384 return | |
| 385 } | |
| 386 // __key__ filter app is X but query app is X | |
| 387 // __key__ filter namespace is X but query namespace is
X | |
| 388 } | |
| 389 // if f.op == qEqual and f.field in ret.project_fields | |
| 390 // "cannot use projection on a proprety with an equality filte
r" | |
| 391 | |
| 392 if f.op.isINEQOp() { | |
| 393 if ineqPropName == "" { | |
| 394 ineqPropName = f.field | |
| 395 } else if f.field != ineqPropName { | |
| 396 ret.err = fmt.Errorf( | |
| 397 "gae/memory: Only one inequality filter
per query is supported. "+ | |
| 398 "Encountered both %s and %s", in
eqPropName, f.field) | |
| 399 return | |
| 400 } | |
| 401 } | |
| 402 } | |
| 403 | |
| 404 // if ineqPropName != "" && len(group_by) > 0 && len(orders) ==0 | |
| 405 // "Inequality filter on X must also be a group by property "+ | |
| 406 // "when group by properties are set." | |
| 407 | |
| 408 if ineqPropName != "" && len(ret.order) != 0 { | |
| 409 if ret.order[0].field != ineqPropName { | |
| 410 ret.err = fmt.Errorf( | |
| 411 "gae/memory: The first sort property must be the
same as the property "+ | |
| 412 "to which the inequality filter is appli
ed. In your query "+ | |
| 413 "the first sort property is %s but the i
nequality filter "+ | |
| 414 "is on %s", ret.order[0].field, ineqProp
Name) | |
| 415 return | |
| 416 } | |
| 417 } | |
| 418 | |
| 419 if ret.kind == "" { | |
| 420 for _, f := range ret.filter { | |
| 421 if f.field != "__key__" { | |
| 422 ret.err = errors.New( | |
| 423 "gae/memory: kind is required for non-__
key__ filters") | |
| 424 return | |
| 425 } | |
| 426 } | |
| 427 for _, o := range ret.order { | |
| 428 if o.field != "__key__" || o.direction != qASC { | |
| 429 ret.err = errors.New( | |
| 430 "gae/memory: kind is required for all or
ders except __key__ ascending") | |
| 431 return | |
| 432 } | |
| 433 } | |
| 434 } | |
| 435 return | |
| 436 } | |
| 437 | |
| 438 func (q *queryImpl) calculateIndex() *qIndex { | |
| 439 // as a nod to simplicity in this code, we'll require that a single inde
x | |
| 440 // is able to service the entire query. E.g. no zigzag merge joins or | |
| 441 // multiqueries. This will mean that the user will need to rely on | |
| 442 // dev_appserver to tell them what indicies they need for real, and for
thier | |
| 443 // tests they'll need to specify the missing composite indices manually. | |
| 444 // | |
| 445 // This COULD lead to an exploding indicies problem, but we can fix that
when | |
| 446 // we get to it. | |
| 447 | |
| 448 //sortOrders := []qSortBy{} | |
| 449 | |
| 450 return nil | |
| 451 } | |
| 452 | |
| 453 func (q *queryImpl) clone() *queryImpl { | |
| 454 ret := *q | |
| 455 ret.filter = append([]queryFilter(nil), q.filter...) | |
| 456 ret.order = append([]queryOrder(nil), q.order...) | |
| 457 ret.project = append([]string(nil), q.project...) | |
| 458 return &ret | |
| 459 } | |
| 460 | |
| 461 func (q *queryImpl) Ancestor(k ds.Key) ds.Query { | |
| 462 q = q.clone() | |
| 463 q.ancestor = k | |
| 464 if k == nil { | |
| 465 // SDK has an explicit nil-check | |
| 466 q.err = errors.New("datastore: nil query ancestor") | |
| 467 } else if !ds.KeyValid(k, false, globalAppID, q.ns) { | |
| 468 // technically the SDK implementation does a Weird Thing (tm) if
both the | |
| 469 // stringID and intID are set on a key; it only serializes the s
tringID in | |
| 470 // the proto. This means that if you set the Ancestor to an inva
lid key, | |
| 471 // you'll never actually hear about it. Instead of doing that in
sanity, we | |
| 472 // just swap to an error here. | |
| 473 q.err = ds.ErrInvalidKey | |
| 474 } else if k.Namespace() != q.ns { | |
| 475 q.err = fmt.Errorf("bad namespace: %q (expected %q)", k.Namespac
e(), q.ns) | |
| 476 } | |
| 477 return q | |
| 478 } | |
| 479 | |
| 480 func (q *queryImpl) Distinct() ds.Query { | |
| 481 q = q.clone() | |
| 482 q.distinct = true | |
| 483 return q | |
| 484 } | |
| 485 | |
| 486 func (q *queryImpl) Filter(fStr string, val interface{}) ds.Query { | |
| 487 q = q.clone() | |
| 488 f, err := parseFilter(fStr, val) | |
| 489 if err != nil { | |
| 490 q.err = err | |
| 491 return q | |
| 492 } | |
| 493 q.filter = append(q.filter, f) | |
| 494 return q | |
| 495 } | |
| 496 | |
| 497 func (q *queryImpl) Order(field string) ds.Query { | |
| 498 q = q.clone() | |
| 499 field = strings.TrimSpace(field) | |
| 500 o := queryOrder{field, qASC} | |
| 501 if strings.HasPrefix(field, "-") { | |
| 502 o.direction = qDEC | |
| 503 o.field = strings.TrimSpace(field[1:]) | |
| 504 } else if strings.HasPrefix(field, "+") { | |
| 505 q.err = fmt.Errorf("datastore: invalid order: %q", field) | |
| 506 return q | |
| 507 } | |
| 508 if len(o.field) == 0 { | |
| 509 q.err = errors.New("datastore: empty order") | |
| 510 return q | |
| 511 } | |
| 512 q.order = append(q.order, o) | |
| 513 return q | |
| 514 } | |
| 515 | |
| 516 func (q *queryImpl) Project(fieldName ...string) ds.Query { | |
| 517 q = q.clone() | |
| 518 q.project = append(q.project, fieldName...) | |
| 519 return q | |
| 520 } | |
| 521 | |
| 522 func (q *queryImpl) KeysOnly() ds.Query { | |
| 523 q = q.clone() | |
| 524 q.keysOnly = true | |
| 525 return q | |
| 526 } | |
| 527 | |
| 528 func (q *queryImpl) Limit(limit int) ds.Query { | |
| 529 q = q.clone() | |
| 530 if limit < math.MinInt32 || limit > math.MaxInt32 { | |
| 531 q.err = errors.New("datastore: query limit overflow") | |
| 532 return q | |
| 533 } | |
| 534 q.limit = int32(limit) | |
| 535 return q | |
| 536 } | |
| 537 | |
| 538 func (q *queryImpl) Offset(offset int) ds.Query { | |
| 539 q = q.clone() | |
| 540 if offset < 0 { | |
| 541 q.err = errors.New("datastore: negative query offset") | |
| 542 return q | |
| 543 } | |
| 544 if offset > math.MaxInt32 { | |
| 545 q.err = errors.New("datastore: query offset overflow") | |
| 546 return q | |
| 547 } | |
| 548 q.offset = int32(offset) | |
| 549 return q | |
| 550 } | |
| 551 | |
| 552 func (q *queryImpl) Start(c ds.Cursor) ds.Query { | |
| 553 q = q.clone() | |
| 554 curs := c.(queryCursor) | |
| 555 if !curs.Valid() { | |
| 556 q.err = errors.New("datastore: invalid cursor") | |
| 557 return q | |
| 558 } | |
| 559 q.start = curs | |
| 560 return q | |
| 561 } | |
| 562 | |
| 563 func (q *queryImpl) End(c ds.Cursor) ds.Query { | |
| 564 q = q.clone() | |
| 565 curs := c.(queryCursor) | |
| 566 if !curs.Valid() { | |
| 567 q.err = errors.New("datastore: invalid cursor") | |
| 568 return q | |
| 569 } | |
| 570 q.end = curs | |
| 571 return q | |
| 572 } | |
| 573 | |
| 574 func (q *queryImpl) EventualConsistency() ds.Query { | |
| 575 q = q.clone() | |
| 576 q.eventualConsistency = true | |
| 577 return q | |
| 578 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1281173002:
Refactor: Rename some files. (Closed)
Base URL: https://github.com/luci/gae.git@tweak_testable