001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.query.processor;
022:
023: import com.db4o.*;
024: import com.db4o.foundation.*;
025: import com.db4o.internal.*;
026: import com.db4o.internal.classindex.*;
027: import com.db4o.internal.diagnostic.*;
028: import com.db4o.internal.fieldindex.*;
029: import com.db4o.internal.marshall.*;
030:
031: /**
032: * Holds the tree of {@link QCandidate} objects and the list of {@link QCon} during query evaluation.
033: * The query work (adding and removing nodes) happens here.
034: * Candidates during query evaluation. {@link QCandidate} objects are stored in i_root
035: *
036: * @exclude
037: */
038: public final class QCandidates implements Visitor4 {
039:
040: // Transaction necessary as reference to stream
041: public final LocalTransaction i_trans;
042:
043: // root of the QCandidate tree
044: public Tree i_root;
045:
046: // collection of all constraints
047: private List4 i_constraints;
048:
049: // possible class information
050: ClassMetadata i_yapClass;
051:
052: // possible field information
053: private QField i_field;
054:
055: // current executing constraint, only set where needed
056: QCon i_currentConstraint;
057:
058: // QOrder tree
059: Tree i_ordered;
060:
061: //
062: private int _majorOrderingID;
063:
064: private IDGenerator _idGenerator;
065:
066: QCandidates(LocalTransaction a_trans, ClassMetadata a_yapClass,
067: QField a_field) {
068: i_trans = a_trans;
069: i_yapClass = a_yapClass;
070: i_field = a_field;
071:
072: if (a_field == null
073: || a_field.i_yapField == null
074: || !(a_field.i_yapField.getHandler() instanceof ClassMetadata)) {
075: return;
076: }
077:
078: ClassMetadata yc = (ClassMetadata) a_field.i_yapField
079: .getHandler();
080: if (i_yapClass == null) {
081: i_yapClass = yc;
082: } else {
083: yc = i_yapClass.getHigherOrCommonHierarchy(yc);
084: if (yc != null) {
085: i_yapClass = yc;
086: }
087: }
088: }
089:
090: public QCandidate addByIdentity(QCandidate candidate) {
091: i_root = Tree.add(i_root, candidate);
092: if (candidate._size == 0) {
093:
094: // This means that the candidate was already present
095: // and QCandidate does not allow duplicates.
096:
097: // In this case QCandidate#isDuplicateOf will have
098: // placed the existing QCandidate in the i_root
099: // variable of the new candidate. We return it here:
100:
101: return candidate.getRoot();
102:
103: }
104: return candidate;
105: }
106:
107: void addConstraint(QCon a_constraint) {
108: i_constraints = new List4(i_constraints, a_constraint);
109: }
110:
111: void addOrder(QOrder a_order) {
112: i_ordered = Tree.add(i_ordered, a_order);
113: }
114:
115: void applyOrdering(Tree orderedCandidates, int orderingID) {
116:
117: if (orderedCandidates == null || i_root == null) {
118: return;
119: }
120:
121: int absoluteOrderingID = Math.abs(orderingID);
122:
123: final boolean major = treatOrderingIDAsMajor(absoluteOrderingID);
124:
125: if (major && !isUnordered()) {
126: swapMajorOrderToMinor();
127: }
128:
129: hintNewOrder(orderedCandidates, major);
130:
131: i_root = recreateTreeFromCandidates();
132:
133: if (major) {
134: _majorOrderingID = absoluteOrderingID;
135: }
136: }
137:
138: public QCandidate readSubCandidate(QueryingReadContext context,
139: TypeHandler4 handler) {
140: ObjectID objectID = ObjectID.NOT_POSSIBLE;
141: try {
142: int offset = context.offset();
143: if (handler instanceof ClassMetadata) {
144: ClassMetadata classMetadata = (ClassMetadata) handler;
145: objectID = classMetadata.readObjectID(context);
146: }
147: if (objectID.isValid()) {
148: return new QCandidate(this , null, objectID._id, true);
149: }
150: if (objectID == ObjectID.NOT_POSSIBLE) {
151: context.seek(offset);
152: Object obj = context.read(handler);
153: if (obj != null) {
154: return new QCandidate(this , obj, 0, true);
155: }
156: }
157:
158: } catch (Exception e) {
159:
160: // FIXME: Catchall
161:
162: }
163: return null;
164: }
165:
166: private Tree recreateTreeFromCandidates() {
167: Collection4 col = collectCandidates();
168:
169: Tree newTree = null;
170: Iterator4 i = col.iterator();
171: while (i.moveNext()) {
172: QCandidate candidate = (QCandidate) i.current();
173: candidate._preceding = null;
174: candidate._subsequent = null;
175: candidate._size = 1;
176: newTree = Tree.add(newTree, candidate);
177: }
178: return newTree;
179: }
180:
181: private Collection4 collectCandidates() {
182: final Collection4 col = new Collection4();
183: i_root.traverse(new Visitor4() {
184: public void visit(Object a_object) {
185: QCandidate candidate = (QCandidate) a_object;
186: col.add(candidate);
187: }
188: });
189: return col;
190: }
191:
192: private void hintNewOrder(Tree orderedCandidates,
193: final boolean major) {
194: final int[] currentOrder = { 0 };
195: final QOrder[] lastOrder = { null };
196:
197: orderedCandidates.traverse(new Visitor4() {
198: public void visit(Object a_object) {
199: QOrder qo = (QOrder) a_object;
200: if (!qo.isEqual(lastOrder[0])) {
201: currentOrder[0]++;
202: }
203: QCandidate candidate = qo._candidate.getRoot();
204: candidate.hintOrder(currentOrder[0], major);
205: lastOrder[0] = qo;
206: }
207: });
208: }
209:
210: private void swapMajorOrderToMinor() {
211: i_root.traverse(new Visitor4() {
212: public void visit(Object obj) {
213: QCandidate candidate = (QCandidate) obj;
214: Order order = (Order) candidate._order;
215: order.swapMajorToMinor();
216: }
217: });
218: }
219:
220: private boolean treatOrderingIDAsMajor(int absoluteOrderingID) {
221: return (isUnordered())
222: || (isMoreRelevantOrderingID(absoluteOrderingID));
223: }
224:
225: private boolean isUnordered() {
226: return _majorOrderingID == 0;
227: }
228:
229: private boolean isMoreRelevantOrderingID(int absoluteOrderingID) {
230: return absoluteOrderingID < _majorOrderingID;
231: }
232:
233: void collect(final QCandidates a_candidates) {
234: Iterator4 i = iterateConstraints();
235: while (i.moveNext()) {
236: QCon qCon = (QCon) i.current();
237: setCurrentConstraint(qCon);
238: qCon.collect(a_candidates);
239: }
240: setCurrentConstraint(null);
241: }
242:
243: void execute() {
244: if (DTrace.enabled) {
245: DTrace.QUERY_PROCESS.log();
246: }
247: final FieldIndexProcessorResult result = processFieldIndexes();
248: if (result.foundIndex()) {
249: i_root = result.toQCandidate(this );
250: } else {
251: loadFromClassIndex();
252: }
253: evaluate();
254: }
255:
256: public Iterator4 executeSnapshot(Collection4 executionPath) {
257: IntIterator4 indexIterator = new IntIterator4Adaptor(
258: iterateIndex(processFieldIndexes()));
259: Tree idRoot = TreeInt.addAll(null, indexIterator);
260: Iterator4 snapshotIterator = new TreeKeyIterator(idRoot);
261: Iterator4 singleObjectQueryIterator = singleObjectSodaProcessor(snapshotIterator);
262: return mapIdsToExecutionPath(singleObjectQueryIterator,
263: executionPath);
264: }
265:
266: private Iterator4 singleObjectSodaProcessor(Iterator4 indexIterator) {
267: return new MappingIterator(indexIterator) {
268: protected Object map(Object current) {
269: int id = ((Integer) current).intValue();
270: QCandidate candidate = new QCandidate(QCandidates.this ,
271: null, id, true);
272: i_root = candidate;
273: evaluate();
274: if (!candidate.include()) {
275: return MappingIterator.SKIP;
276: }
277: return current;
278: }
279: };
280: }
281:
282: public Iterator4 executeLazy(Collection4 executionPath) {
283: Iterator4 indexIterator = iterateIndex(processFieldIndexes());
284: Iterator4 singleObjectQueryIterator = singleObjectSodaProcessor(indexIterator);
285: return mapIdsToExecutionPath(singleObjectQueryIterator,
286: executionPath);
287: }
288:
289: private Iterator4 iterateIndex(FieldIndexProcessorResult result) {
290: if (result.noMatch()) {
291: return Iterators.EMPTY_ITERATOR;
292: }
293: if (result.foundIndex()) {
294: return result.iterateIDs();
295: }
296: if (i_yapClass.isPrimitive()) {
297: return Iterators.EMPTY_ITERATOR;
298: }
299: return BTreeClassIndexStrategy.iterate(i_yapClass, i_trans);
300: }
301:
302: private Iterator4 mapIdsToExecutionPath(
303: Iterator4 singleObjectQueryIterator,
304: Collection4 executionPath) {
305:
306: if (executionPath == null) {
307: return singleObjectQueryIterator;
308: }
309:
310: Iterator4 res = singleObjectQueryIterator;
311:
312: Iterator4 executionPathIterator = executionPath.iterator();
313: while (executionPathIterator.moveNext()) {
314:
315: final String fieldName = (String) executionPathIterator
316: .current();
317:
318: Iterator4 mapIdToFieldIdsIterator = new MappingIterator(res) {
319:
320: protected Object map(Object current) {
321: int id = ((Integer) current).intValue();
322: StatefulBuffer reader = stream().readWriterByID(
323: i_trans, id);
324: if (reader == null) {
325: return MappingIterator.SKIP;
326: }
327:
328: ObjectHeader oh = new ObjectHeader(stream(), reader);
329:
330: Tree idTree = oh.classMetadata().collectFieldIDs(
331: oh._marshallerFamily, oh._headerAttributes,
332: null, reader, fieldName);
333:
334: return new TreeKeyIterator(idTree);
335: }
336:
337: };
338:
339: res = new CompositeIterator4(mapIdToFieldIdsIterator);
340:
341: }
342: return res;
343: }
344:
345: public ObjectContainerBase stream() {
346: return i_trans.container();
347: }
348:
349: public int classIndexEntryCount() {
350: return i_yapClass.indexEntryCount(i_trans);
351: }
352:
353: private FieldIndexProcessorResult processFieldIndexes() {
354: if (i_constraints == null) {
355: return FieldIndexProcessorResult.NO_INDEX_FOUND;
356: }
357: return new FieldIndexProcessor(this ).run();
358: }
359:
360: void evaluate() {
361:
362: if (i_constraints == null) {
363: return;
364: }
365:
366: Iterator4 i = iterateConstraints();
367: while (i.moveNext()) {
368: QCon qCon = (QCon) i.current();
369: qCon.setCandidates(this );
370: qCon.evaluateSelf();
371: }
372:
373: i = iterateConstraints();
374: while (i.moveNext()) {
375: ((QCon) i.current()).evaluateSimpleChildren();
376: }
377:
378: i = iterateConstraints();
379: while (i.moveNext()) {
380: ((QCon) i.current()).evaluateEvaluations();
381: }
382:
383: i = iterateConstraints();
384: while (i.moveNext()) {
385: ((QCon) i.current()).evaluateCreateChildrenCandidates();
386: }
387:
388: i = iterateConstraints();
389: while (i.moveNext()) {
390: ((QCon) i.current()).evaluateCollectChildren();
391: }
392:
393: i = iterateConstraints();
394: while (i.moveNext()) {
395: ((QCon) i.current()).evaluateChildren();
396: }
397: }
398:
399: boolean isEmpty() {
400: final boolean[] ret = new boolean[] { true };
401: traverse(new Visitor4() {
402: public void visit(Object obj) {
403: if (((QCandidate) obj)._include) {
404: ret[0] = false;
405: }
406: }
407: });
408: return ret[0];
409: }
410:
411: boolean filter(Visitor4 a_host) {
412: if (i_root != null) {
413: i_root.traverse(a_host);
414: i_root = i_root.filter(new Predicate4() {
415: public boolean match(Object a_candidate) {
416: return ((QCandidate) a_candidate)._include;
417: }
418: });
419: }
420: return i_root != null;
421: }
422:
423: int generateCandidateId() {
424: if (_idGenerator == null) {
425: _idGenerator = new IDGenerator();
426: }
427: return -_idGenerator.next();
428: }
429:
430: public Iterator4 iterateConstraints() {
431: if (i_constraints == null) {
432: return Iterators.EMPTY_ITERATOR;
433: }
434: return new Iterator4Impl(i_constraints);
435: }
436:
437: final static class TreeIntBuilder {
438: public TreeInt tree;
439:
440: public void add(TreeInt node) {
441: tree = (TreeInt) Tree.add(tree, node);
442: }
443: }
444:
445: void loadFromClassIndex() {
446: if (!isEmpty()) {
447: return;
448: }
449:
450: final TreeIntBuilder result = new TreeIntBuilder();
451: final ClassIndexStrategy index = i_yapClass.index();
452: index.traverseAll(i_trans, new Visitor4() {
453: public void visit(Object obj) {
454: result.add(new QCandidate(QCandidates.this , null,
455: ((Integer) obj).intValue(), true));
456: }
457: });
458:
459: i_root = result.tree;
460:
461: DiagnosticProcessor dp = i_trans.container()._handlers._diagnosticProcessor;
462: if (dp.enabled()) {
463: dp.loadedFromClassIndex(i_yapClass);
464: }
465:
466: }
467:
468: void setCurrentConstraint(QCon a_constraint) {
469: i_currentConstraint = a_constraint;
470: }
471:
472: void traverse(Visitor4 a_visitor) {
473: if (i_root != null) {
474: i_root.traverse(a_visitor);
475: }
476: }
477:
478: boolean tryAddConstraint(QCon a_constraint) {
479:
480: if (i_field != null) {
481: QField qf = a_constraint.getField();
482: if (qf != null) {
483: if (i_field.i_name != null
484: && !i_field.i_name.equals(qf.i_name)) {
485: return false;
486: }
487: }
488: }
489:
490: if (i_yapClass == null || a_constraint.isNullConstraint()) {
491: addConstraint(a_constraint);
492: return true;
493: }
494: ClassMetadata yc = a_constraint.getYapClass();
495: if (yc != null) {
496: yc = i_yapClass.getHigherOrCommonHierarchy(yc);
497: if (yc != null) {
498: i_yapClass = yc;
499: addConstraint(a_constraint);
500: return true;
501: }
502: }
503: return false;
504: }
505:
506: public void visit(Object a_tree) {
507: final QCandidate parent = (QCandidate) a_tree;
508: if (parent.createChild(this )) {
509: return;
510: }
511:
512: // No object found.
513: // All children constraints are necessarily false.
514: // Check immediately.
515: Iterator4 i = iterateConstraints();
516: while (i.moveNext()) {
517: ((QCon) i.current()).visitOnNull(parent.getRoot());
518: }
519:
520: }
521:
522: public String toString() {
523: final StringBuffer sb = new StringBuffer();
524: i_root.traverse(new Visitor4() {
525: public void visit(Object obj) {
526: QCandidate candidate = (QCandidate) obj;
527: sb.append(" ");
528: sb.append(candidate._key);
529: }
530: });
531: return sb.toString();
532: }
533:
534: public void clearOrdering() {
535: i_ordered = null;
536: }
537:
538: public final Transaction transaction() {
539: return i_trans;
540: }
541: }
|