· 8 years ago · Jun 07, 2018, 06:40 AM
1##############################################################################
2#
3# Copyright (c) 2002 Zope Corporation and Contributors. All Rights Reserved.
4#
5# This software is subject to the provisions of the Zope Public License,
6# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
7# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
8# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
9# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
10# FOR A PARTICULAR PURPOSE
11#
12##############################################################################
13
14import types
15import logging
16from bisect import bisect
17from random import randint
18
19import Acquisition
20import ExtensionClass
21from Missing import MV
22from Persistence import Persistent
23
24import BTrees.Length
25from BTrees.IIBTree import intersection, weightedIntersection, IISet
26from BTrees.OIBTree import OIBTree
27from BTrees.IOBTree import IOBTree
28from Lazy import LazyMap, LazyCat, LazyValues
29from CatalogBrains import AbstractCatalogBrain, NoBrainer
30
31
32LOG = logging.getLogger('Zope.ZCatalog')
33
34
35try:
36 from DocumentTemplate.cDocumentTemplate import safe_callable
37except ImportError:
38 # Fallback to python implementation to avoid dependancy on DocumentTemplate
39 def safe_callable(ob):
40 # Works with ExtensionClasses and Acquisition.
41 if hasattr(ob, '__class__'):
42 return hasattr(ob, '__call__') or isinstance(ob, types.ClassType)
43 else:
44 return callable(ob)
45
46
47class CatalogError(Exception):
48 pass
49
50class Catalog(Persistent, Acquisition.Implicit, ExtensionClass.Base):
51 """ An Object Catalog
52
53 An Object Catalog maintains a table of object metadata, and a
54 series of manageable indexes to quickly search for objects
55 (references in the metadata) that satisfy a search query.
56
57 This class is not Zope specific, and can be used in any python
58 program to build catalogs of objects. Note that it does require
59 the objects to be Persistent, and thus must be used with ZODB3.
60 """
61
62 _v_brains = NoBrainer
63
64 def __init__(self, vocabulary=None, brains=None):
65 # Catalogs no longer care about vocabularies and lexicons
66 # so the vocabulary argument is ignored. (Casey)
67
68 self.schema = {} # mapping from attribute name to column number
69 self.names = () # sequence of column names
70 self.indexes = {} # maping from index name to index object
71
72 # The catalog maintains a BTree of object meta_data for
73 # convenient display on result pages. meta_data attributes
74 # are turned into brain objects and returned by
75 # searchResults. The indexing machinery indexes all records
76 # by an integer id (rid). self.data is a mapping from the
77 # integer id to the meta_data, self.uids is a mapping of the
78 # object unique identifier to the rid, and self.paths is a
79 # mapping of the rid to the unique identifier.
80
81 self.clear()
82
83 if brains is not None:
84 self._v_brains = brains
85
86 self.updateBrains()
87
88
89 def __len__(self):
90 return self._length()
91
92 def migrate__len__(self):
93 """ migration of old __len__ magic for Zope 2.8 """
94 if not hasattr(self, '_length'):
95 n = self.__dict__['__len__']()
96 del self.__dict__['__len__']
97 self._length = BTrees.Length.Length(n)
98
99 def clear(self):
100 """ clear catalog """
101
102 self.data = IOBTree() # mapping of rid to meta_data
103 self.uids = OIBTree() # mapping of uid to rid
104 self.paths = IOBTree() # mapping of rid to uid
105 self._length = BTrees.Length.Length()
106
107 for index in self.indexes.keys():
108 self.getIndex(index).clear()
109
110 def updateBrains(self):
111 self.useBrains(self._v_brains)
112
113 def __getitem__(self, index, ttype=type(())):
114 """
115 Returns instances of self._v_brains, or whatever is passed
116 into self.useBrains.
117 """
118 if type(index) is ttype:
119 # then it contains a score...
120 normalized_score, score, key = index
121 r=self._v_result_class(self.data[key]).__of__(self.aq_parent)
122 r.data_record_id_ = key
123 r.data_record_score_ = score
124 r.data_record_normalized_score_ = normalized_score
125 else:
126 # otherwise no score, set all scores to 1
127 r=self._v_result_class(self.data[index]).__of__(self.aq_parent)
128 r.data_record_id_ = index
129 r.data_record_score_ = 1
130 r.data_record_normalized_score_ = 1
131 return r
132
133 def __setstate__(self, state):
134 """ initialize your brains. This method is called when the
135 catalog is first activated (from the persistent storage) """
136 Persistent.__setstate__(self, state)
137 self.updateBrains()
138
139 def useBrains(self, brains):
140 """ Sets up the Catalog to return an object (ala ZTables) that
141 is created on the fly from the tuple stored in the self.data
142 Btree.
143 """
144
145 class mybrains(AbstractCatalogBrain, brains):
146 pass
147
148 scopy = self.schema.copy()
149
150 scopy['data_record_id_']=len(self.schema.keys())
151 scopy['data_record_score_']=len(self.schema.keys())+1
152 scopy['data_record_normalized_score_']=len(self.schema.keys())+2
153
154 mybrains.__record_schema__ = scopy
155
156 self._v_brains = brains
157 self._v_result_class = mybrains
158
159 def addColumn(self, name, default_value=None):
160 """
161 adds a row to the meta data schema
162 """
163
164 schema = self.schema
165 names = list(self.names)
166
167 if schema.has_key(name):
168 raise CatalogError, 'The column %s already exists' % name
169
170 if name[0] == '_':
171 raise CatalogError, \
172 'Cannot cache fields beginning with "_"'
173
174 if not schema.has_key(name):
175 if schema.values():
176 schema[name] = max(schema.values())+1
177 else:
178 schema[name] = 0
179 names.append(name)
180
181 if default_value is None or default_value == '':
182 default_value = MV
183
184 for key in self.data.keys():
185 rec = list(self.data[key])
186 rec.append(default_value)
187 self.data[key] = tuple(rec)
188
189 self.names = tuple(names)
190 self.schema = schema
191
192 # new column? update the brain
193 self.updateBrains()
194
195 self._p_changed = 1 # why?
196
197 def delColumn(self, name):
198 """
199 deletes a row from the meta data schema
200 """
201 names = list(self.names)
202 _index = names.index(name)
203
204 if not self.schema.has_key(name):
205 LOG.error('delColumn attempted to delete nonexistent column %s.' % str(name))
206 return
207
208 del names[_index]
209
210 # rebuild the schema
211 i=0; schema = {}
212 for name in names:
213 schema[name] = i
214 i = i + 1
215
216 self.schema = schema
217 self.names = tuple(names)
218
219 # update the brain
220 self.updateBrains()
221
222 # remove the column value from each record
223 for key in self.data.keys():
224 rec = list(self.data[key])
225 del rec[_index]
226 self.data[key] = tuple(rec)
227
228 def addIndex(self, name, index_type):
229 """Create a new index, given a name and a index_type.
230
231 Old format: index_type was a string, 'FieldIndex' 'TextIndex' or
232 'KeywordIndex' is no longer valid; the actual index must be instantiated
233 and passed in to addIndex.
234
235 New format: index_type is the actual index object to be stored.
236
237 """
238
239 if self.indexes.has_key(name):
240 raise CatalogError, 'The index %s already exists' % name
241
242 if name.startswith('_'):
243 raise CatalogError, 'Cannot index fields beginning with "_"'
244
245 if not name:
246 raise CatalogError, 'Name of index is empty'
247
248 indexes = self.indexes
249
250 if isinstance(index_type, str):
251 raise TypeError,"""Catalog addIndex now requires the index type to
252 be resolved prior to adding; create the proper index in the caller."""
253
254 indexes[name] = index_type;
255
256 self.indexes = indexes
257
258 def delIndex(self, name):
259 """ deletes an index """
260
261 if not self.indexes.has_key(name):
262 raise CatalogError, 'The index %s does not exist' % name
263
264 indexes = self.indexes
265 del indexes[name]
266 self.indexes = indexes
267
268 def getIndex(self, name):
269 """ get an index wrapped in the catalog """
270 return self.indexes[name].__of__(self)
271
272 def updateMetadata(self, object, uid):
273 """ Given an object and a uid, update the column data for the
274 uid with the object data iff the object has changed """
275 data = self.data
276 index = self.uids.get(uid, None)
277 newDataRecord = self.recordify(object)
278
279 if index is None:
280 if type(data) is IOBTree:
281 # New style, get random id
282
283 index=getattr(self, '_v_nextid', 0)
284 if index % 4000 == 0:
285 index = randint(-2000000000, 2000000000)
286 while not data.insert(index, newDataRecord):
287 index = randint(-2000000000, 2000000000)
288
289 # We want ids to be somewhat random, but there are
290 # advantages for having some ids generated
291 # sequentially when many catalog updates are done at
292 # once, such as when reindexing or bulk indexing.
293 # We allocate ids sequentially using a volatile base,
294 # so different threads get different bases. This
295 # further reduces conflict and reduces churn in
296 # here and it result sets when bulk indexing.
297 self._v_nextid=index+1
298 else:
299 if data:
300 # find the next available unique id
301 index = data.keys()[-1] + 1
302 else:
303 index=0
304 # meta_data is stored as a tuple for efficiency
305 data[index] = newDataRecord
306 else:
307 if data.get(index, 0) != newDataRecord:
308 data[index] = newDataRecord
309 return index
310
311 # the cataloging API
312
313 def catalogObject(self, object, uid, threshold=None, idxs=None,
314 update_metadata=1):
315 """
316 Adds an object to the Catalog by iteratively applying it to
317 all indexes.
318
319 'object' is the object to be cataloged
320
321 'uid' is the unique Catalog identifier for this object
322
323 If 'idxs' is specified (as a sequence), apply the object only
324 to the named indexes.
325
326 If 'update_metadata' is true (the default), also update metadata for
327 the object. If the object is new to the catalog, this flag has
328 no effect (metadata is always created for new objects).
329
330 """
331
332 if idxs is None:
333 idxs = []
334
335 data = self.data
336 index = self.uids.get(uid, None)
337
338 if index is None: # we are inserting new data
339 index = self.updateMetadata(object, uid)
340
341 if not hasattr(self, '_length'):
342 self.migrate__len__()
343 self._length.change(1)
344 self.uids[uid] = index
345 self.paths[index] = uid
346
347 elif update_metadata: # we are updating and we need to update metadata
348 self.updateMetadata(object, uid)
349
350 # do indexing
351
352 total = 0
353
354 if idxs==[]: use_indexes = self.indexes.keys()
355 else: use_indexes = idxs
356
357 for name in use_indexes:
358 x = self.getIndex(name)
359 if hasattr(x, 'index_object'):
360 blah = x.index_object(index, object, threshold)
361 total = total + blah
362 else:
363 LOG.error('catalogObject was passed bad index object %s.' % str(x))
364
365 return total
366
367 def uncatalogObject(self, uid):
368 """
369 Uncatalog and object from the Catalog. and 'uid' is a unique
370 Catalog identifier
371
372 Note, the uid must be the same as when the object was
373 catalogued, otherwise it will not get removed from the catalog
374
375 This method should not raise an exception if the uid cannot
376 be found in the catalog.
377
378 """
379 data = self.data
380 uids = self.uids
381 paths = self.paths
382 indexes = self.indexes.keys()
383 rid = uids.get(uid, None)
384
385 if rid is not None:
386 for name in indexes:
387 x = self.getIndex(name)
388 if hasattr(x, 'unindex_object'):
389 x.unindex_object(rid)
390 del data[rid]
391 del paths[rid]
392 del uids[uid]
393 if not hasattr(self, '_length'):
394 self.migrate__len__()
395 self._length.change(-1)
396
397 else:
398 LOG.error('uncatalogObject unsuccessfully '
399 'attempted to uncatalog an object '
400 'with a uid of %s. ' % str(uid))
401
402
403 def uniqueValuesFor(self, name):
404 """ return unique values for FieldIndex name """
405 return self.getIndex(name).uniqueValues()
406
407 def hasuid(self, uid):
408 """ return the rid if catalog contains an object with uid """
409 return self.uids.get(uid)
410
411 def recordify(self, object):
412 """ turns an object into a record tuple """
413 record = []
414 # the unique id is allways the first element
415 for x in self.names:
416 attr=getattr(object, x, MV)
417 if(attr is not MV and safe_callable(attr)): attr=attr()
418 record.append(attr)
419 return tuple(record)
420
421 def instantiate(self, record):
422 r=self._v_result_class(record[1])
423 r.data_record_id_ = record[0]
424 return r.__of__(self)
425
426
427 def getMetadataForRID(self, rid):
428 record = self.data[rid]
429 result = {}
430 for (key, pos) in self.schema.items():
431 result[key] = record[pos]
432 return result
433
434 def getIndexDataForRID(self, rid):
435 result = {}
436 for name in self.indexes.keys():
437 result[name] = self.getIndex(name).getEntryForObject(rid, "")
438 return result
439
440## This is the Catalog search engine. Most of the heavy lifting happens below
441
442 def search(self, request, sort_index=None, reverse=0, limit=None, merge=1):
443 """Iterate through the indexes, applying the query to each one. If
444 merge is true then return a lazy result set (sorted if appropriate)
445 otherwise return the raw (possibly scored) results for later merging.
446 Limit is used in conjuntion with sorting or scored results to inform
447 the catalog how many results you are really interested in. The catalog
448 can then use optimizations to save time and memory. The number of
449 results is not guaranteed to fall within the limit however, you should
450 still slice or batch the results as usual."""
451
452 rs = None # resultset
453
454 # Indexes fulfill a fairly large contract here. We hand each
455 # index the request mapping we are given (which may be composed
456 # of some combination of web request, kw mappings or plain old dicts)
457 # and the index decides what to do with it. If the index finds work
458 # for itself in the request, it returns the results and a tuple of
459 # the attributes that were used. If the index finds nothing for it
460 # to do then it returns None.
461
462 # For hysterical reasons, if all indexes return None for a given
463 # request (and no attributes were used) then we append all results
464 # in the Catalog. This generally happens when the search values
465 # in request are all empty strings or do not coorespond to any of
466 # the indexes.
467
468 # Note that if the indexes find query arguments, but the end result
469 # is an empty sequence, we do nothing
470
471 for i in self.indexes.keys():
472 index = self.getIndex(i)
473 _apply_index = getattr(index, "_apply_index", None)
474 if _apply_index is None:
475 continue
476 r = _apply_index(request)
477
478 if r is not None:
479 r, u = r
480 w, rs = weightedIntersection(rs, r)
481
482 if rs is None:
483 # None of the indexes found anything to do with the request
484 # We take this to mean that the query was empty (an empty filter)
485 # and so we return everything in the catalog
486 if sort_index is None:
487 return LazyMap(self.instantiate, self.data.items(), len(self))
488 else:
489 return self.sortResults(
490 self.data, sort_index, reverse, limit, merge)
491 elif rs:
492 # We got some results from the indexes.
493 # Sort and convert to sequences.
494 # XXX: The check for 'values' is really stupid since we call
495 # items() and *not* values()
496 if sort_index is None and hasattr(rs, 'values'):
497 # having a 'values' means we have a data structure with
498 # scores. Build a new result set, sort it by score, reverse
499 # it, compute the normalized score, and Lazify it.
500
501 if not merge:
502 # Don't bother to sort here, return a list of
503 # three tuples to be passed later to mergeResults
504 # note that data_record_normalized_score_ cannot be
505 # calculated and will always be 1 in this case
506 getitem = self.__getitem__
507 return [(score, (1, score, rid), getitem)
508 for rid, score in rs.items()]
509
510 rs = rs.byValue(0) # sort it by score
511 max = float(rs[0][0])
512
513 # Here we define our getter function inline so that
514 # we can conveniently store the max value as a default arg
515 # and make the normalized score computation lazy
516 def getScoredResult(item, max=max, self=self):
517 """
518 Returns instances of self._v_brains, or whatever is passed
519 into self.useBrains.
520 """
521 score, key = item
522 r=self._v_result_class(self.data[key])\
523 .__of__(self.aq_parent)
524 r.data_record_id_ = key
525 r.data_record_score_ = score
526 r.data_record_normalized_score_ = int(100. * score / max)
527 return r
528
529 return LazyMap(getScoredResult, rs, len(rs))
530
531 elif sort_index is None and not hasattr(rs, 'values'):
532 # no scores
533 if hasattr(rs, 'keys'):
534 rs = rs.keys()
535 return LazyMap(self.__getitem__, rs, len(rs))
536 else:
537 # sort. If there are scores, then this block is not
538 # reached, therefore 'sort-on' does not happen in the
539 # context of a text index query. This should probably
540 # sort by relevance first, then the 'sort-on' attribute.
541 return self.sortResults(rs, sort_index, reverse, limit, merge)
542 else:
543 # Empty result set
544 return LazyCat([])
545
546 def sortResults(self, rs, sort_index, reverse=0, limit=None, merge=1):
547 # Sort a result set using a sort index. Return a lazy
548 # result set in sorted order if merge is true otherwise
549 # returns a list of (sortkey, uid, getter_function) tuples
550 #
551 # The two 'for' loops in here contribute a significant
552 # proportion of the time to perform an indexed search.
553 # Try to avoid all non-local attribute lookup inside
554 # those loops.
555 assert limit is None or limit > 0, 'Limit value must be 1 or greater'
556 _lazymap = LazyMap
557 _intersection = intersection
558 _self__getitem__ = self.__getitem__
559 index_key_map = sort_index.documentToKeyMap()
560 _None = None
561 _keyerror = KeyError
562 result = []
563 append = result.append
564 if hasattr(rs, 'keys'):
565 rs = rs.keys()
566 rlen = len(rs)
567
568 if merge and limit is None and (
569 rlen > (len(sort_index) * (rlen / 100 + 1))):
570 # The result set is much larger than the sorted index,
571 # so iterate over the sorted index for speed.
572 # This is rarely exercised in practice...
573
574 length = 0
575
576 try:
577 intersection(rs, IISet(()))
578 except TypeError:
579 # rs is not an object in the IIBTree family.
580 # Try to turn rs into an IISet.
581 rs = IISet(rs)
582
583 for k, intset in sort_index.items():
584 # We have an index that has a set of values for
585 # each sort key, so we intersect with each set and
586 # get a sorted sequence of the intersections.
587 intset = _intersection(rs, intset)
588 if intset:
589 keys = getattr(intset, 'keys', _None)
590 if keys is not _None:
591 # Is this ever true?
592 intset = keys()
593 length += len(intset)
594 append((k, intset, _self__getitem__))
595 # Note that sort keys are unique.
596
597 result.sort()
598 if reverse:
599 result.reverse()
600 result = LazyCat(LazyValues(result), length)
601 elif limit is None or (limit * 4 > rlen):
602 # Iterate over the result set getting sort keys from the index
603 for did in rs:
604 try:
605 key = index_key_map[did]
606 except _keyerror:
607 # This document is not in the sort key index, skip it.
608 pass
609 else:
610 append((key, did, _self__getitem__))
611 # The reference back to __getitem__ is used in case
612 # we do not merge now and need to intermingle the
613 # results with those of other catalogs while avoiding
614 # the cost of instantiating a LazyMap per result
615 if merge:
616 result.sort()
617 if reverse:
618 result.reverse()
619 if limit is not None:
620 result = result[:limit]
621 result = LazyValues(result)
622 else:
623 return result
624 elif reverse:
625 # Limit/sort results using N-Best algorithm
626 # This is faster for large sets then a full sort
627 # And uses far less memory
628 keys = []
629 n = 0
630 worst = None
631 for did in rs:
632 try:
633 key = index_key_map[did]
634 except _keyerror:
635 # This document is not in the sort key index, skip it.
636 pass
637 else:
638 if n >= limit and key <= worst:
639 continue
640 i = bisect(keys, key)
641 keys.insert(i, key)
642 result.insert(i, (key, did, _self__getitem__))
643 if n == limit:
644 del keys[0], result[0]
645 else:
646 n += 1
647 worst = keys[0]
648 result.reverse()
649 if merge:
650 result = LazyValues(result)
651 else:
652 return result
653 elif not reverse:
654 # Limit/sort results using N-Best algorithm in reverse (N-Worst?)
655 keys = []
656 n = 0
657 best = None
658 for did in rs:
659 try:
660 key = index_key_map[did]
661 except _keyerror:
662 # This document is not in the sort key index, skip it.
663 pass
664 else:
665 if n >= limit and key >= best:
666 continue
667 i = bisect(keys, key)
668 keys.insert(i, key)
669 result.insert(i, (key, did, _self__getitem__))
670 if n == limit:
671 del keys[-1], result[-1]
672 else:
673 n += 1
674 best = keys[-1]
675 if merge:
676 result = LazyValues(result)
677 else:
678 return result
679
680 result = LazyMap(self.__getitem__, result, len(result))
681 result.actual_result_count = rlen
682 return result
683
684 def _get_sort_attr(self, attr, kw):
685 """Helper function to find sort-on or sort-order."""
686 # There are three different ways to find the attribute:
687 # 1. kw[sort-attr]
688 # 2. self.sort-attr
689 # 3. kw[sort_attr]
690 # kw may be a dict or an ExtensionClass MultiMapping, which
691 # differ in what get() returns with no default value.
692 name = "sort-%s" % attr
693 val = kw.get(name, None)
694 if val is not None:
695 return val
696 val = getattr(self, name, None)
697 if val is not None:
698 return val
699 return kw.get("sort_%s" % attr, None)
700
701
702 def _getSortIndex(self, args):
703 """Returns a search index object or None."""
704 sort_index_name = self._get_sort_attr("on", args)
705 if sort_index_name is not None:
706 # self.indexes is always a dict, so get() w/ 1 arg works
707 sort_index = self.indexes.get(sort_index_name)
708 if sort_index is None:
709 raise CatalogError, 'Unknown sort_on index (%s)' % sort_index_name
710 else:
711 if not hasattr(sort_index, 'keyForDocument'):
712 raise CatalogError(
713 'The index chosen for sort_on (%s) is not capable of being'
714 ' used as a sort index.' % sort_index_name
715 )
716 return sort_index
717 else:
718 return None
719
720 def searchResults(self, REQUEST=None, used=None, _merge=1, **kw):
721 # The used argument is deprecated and is ignored
722 if REQUEST is None and not kw:
723 # Try to acquire request if we get no args for bw compat
724 REQUEST = getattr(self, 'REQUEST', None)
725 args = CatalogSearchArgumentsMap(REQUEST, kw)
726 sort_index = self._getSortIndex(args)
727 sort_limit = self._get_sort_attr('limit', args)
728 reverse = 0
729 if sort_index is not None:
730 order = self._get_sort_attr("order", args)
731 if (isinstance(order, str) and
732 order.lower() in ('reverse', 'descending')):
733 reverse = 1
734 # Perform searches with indexes and sort_index
735 return self.search(args, sort_index, reverse, sort_limit, _merge)
736
737 __call__ = searchResults
738
739
740class CatalogSearchArgumentsMap:
741 """Multimap catalog arguments coming simultaneously from keywords
742 and request.
743
744 Values that are empty strings are treated as non-existent. This is
745 to ignore empty values, thereby ignoring empty form fields to be
746 consistent with hysterical behavior.
747 """
748
749 def __init__(self, request, keywords):
750 self.request = request or {}
751 self.keywords = keywords or {}
752
753 def __getitem__(self, key):
754 marker = []
755 v = self.keywords.get(key, marker)
756 if v is marker or v == '':
757 v = self.request[key]
758 if v == '':
759 raise KeyError(key)
760 return v
761
762 def get(self, key, default=None):
763 try:
764 v = self[key]
765 except KeyError:
766 return default
767 else:
768 return v
769
770 def has_key(self, key):
771 try:
772 self[key]
773 except KeyError:
774 return 0
775 else:
776 return 1
777
778
779def mergeResults(results, has_sort_keys, reverse):
780 """Sort/merge sub-results, generating a flat sequence.
781
782 results is a list of result set sequences, all with or without sort keys
783 """
784 if not has_sort_keys:
785 return LazyCat(results)
786 else:
787 # Concatenate the catalog results into one list and sort it
788 # Each result record consists of a list of tuples with three values:
789 # (sortkey, docid, catalog__getitem__)
790 if len(results) > 1:
791 all = []
792 for r in results:
793 all.extend(r)
794 elif len(results) == 1:
795 all = results[0]
796 else:
797 return []
798 all.sort()
799 if reverse:
800 all.reverse()
801 return LazyMap(lambda rec: rec[2](rec[1]), all, len(all))