Java > Open Source Codes > org > objectstyle > cayenne > access > util > FlatPrefetchTreeNode


1 /* ====================================================================
2  *
3  * The ObjectStyle Group Software License, version 1.1
4  * ObjectStyle Group - http://objectstyle.org/
5  *
6  * Copyright (c) 2002-2005, Andrei (Andrus) Adamchik and individual authors
7  * of the software. All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in
18  * the documentation and/or other materials provided with the
19  * distribution.
20  *
21  * 3. The end-user documentation included with the redistribution, if any,
22  * must include the following acknowlegement:
23  * "This product includes software developed by independent contributors
24  * and hosted on ObjectStyle Group web site (http://objectstyle.org/)."
25  * Alternately, this acknowlegement may appear in the software itself,
26  * if and wherever such third-party acknowlegements normally appear.
27  *
28  * 4. The names "ObjectStyle Group" and "Cayenne" must not be used to endorse
29  * or promote products derived from this software without prior written
30  * permission. For written permission, email
31  * "andrus at objectstyle dot org".
32  *
33  * 5. Products derived from this software may not be called "ObjectStyle"
34  * or "Cayenne", nor may "ObjectStyle" or "Cayenne" appear in their
35  * names without prior written permission.
36  *
37  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40  * DISCLAIMED. IN NO EVENT SHALL THE OBJECTSTYLE GROUP OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
44  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
45  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
46  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
47  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
48  * SUCH DAMAGE.
49  * ====================================================================
50  *
51  * This software consists of voluntary contributions made by many
52  * individuals and hosted on ObjectStyle Group web site. For more
53  * information on the ObjectStyle Group, please see
54  * <http://objectstyle.org/>.
55  */
56 package org.objectstyle.cayenne.access.util;
57
58 import java.util.ArrayList ;
59 import java.util.Arrays ;
60 import java.util.Collection ;
61 import java.util.Collections ;
62 import java.util.HashMap ;
63 import java.util.HashSet ;
64 import java.util.Iterator ;
65 import java.util.List ;
66 import java.util.Map ;
67 import java.util.TreeMap ;
68
69 import org.apache.commons.collections.Closure;
70 import org.apache.commons.collections.Factory;
71 import org.apache.commons.collections.MapUtils;
72 import org.apache.log4j.Logger;
73 import org.objectstyle.cayenne.CayenneRuntimeException;
74 import org.objectstyle.cayenne.DataObject;
75 import org.objectstyle.cayenne.DataRow;
76 import org.objectstyle.cayenne.access.ToManyList;
77 import org.objectstyle.cayenne.access.jdbc.ColumnDescriptor;
78 import org.objectstyle.cayenne.exp.Expression;
79 import org.objectstyle.cayenne.exp.TraversalHelper;
80 import org.objectstyle.cayenne.map.DbAttribute;
81 import org.objectstyle.cayenne.map.DbJoin;
82 import org.objectstyle.cayenne.map.DbRelationship;
83 import org.objectstyle.cayenne.map.ObjAttribute;
84 import org.objectstyle.cayenne.map.ObjEntity;
85 import org.objectstyle.cayenne.map.ObjRelationship;
86
87 /**
88  * Converts DataRows representing a cartesian product of one or more tables into a tree of
89  * objects. Row keys in input DataRows must be DB path expressions rooted in the main
90  * entity. Instances are not reentrant or reusable as they store intermediate processing
91  * state.
92  *
93  * @since 1.2
94  * @author Andrei Adamchik
95  */
96 class FlatPrefetchTreeNode {
97
98     final static Logger logObj = Logger.getLogger(FlatPrefetchTreeNode.class);
99
100     // tree linking
101 FlatPrefetchTreeNode parent;
102     ObjEntity entity;
103     ObjRelationship incoming;
104     Collection children;
105     boolean phantom;
106     boolean categorizeByParent;
107
108     // column mapping
109 ColumnDescriptor[] columns;
110     int[] idIndices;
111     int rowCapacity;
112
113     // processing results
114 Map partitionedByParent;
115     Map resolved;
116
117     /**
118      * Creates new FlatPrefetchTreeNode. Last argument is used to block certain to-many
119      * prefetches that conflict with qualifier expression. This is somewhat of a hack in
120      * search of a better solution.
121      */
122     FlatPrefetchTreeNode(ObjEntity entity, Collection jointPrefetchKeys,
123             Expression queryQualifier) {
124         this();
125
126         this.entity = entity;
127
128         Collection qualifierKeys = extractQualifierKeys(queryQualifier);
129         buildTree(jointPrefetchKeys, qualifierKeys);
130     }
131
132     /**
133      * Creates new FlatPrefetchTreeNode.
134      */
135     private FlatPrefetchTreeNode() {
136         Factory listFactory = new Factory() {
137
138             public Object create() {
139                 return new ArrayList ();
140             }
141         };
142
143         this.partitionedByParent = MapUtils.lazyMap(new HashMap (), listFactory);
144         this.resolved = new HashMap ();
145     }
146
147     /**
148      * Returns a collection of qualifier DB PATH keys.
149      */
150     private Collection extractQualifierKeys(Expression qualifier) {
151         if (qualifier == null) {
152             return Collections.EMPTY_SET;
153         }
154
155         DBPathExtractor extractor = new DBPathExtractor(entity);
156         qualifier.traverse(extractor);
157         return extractor.getPaths();
158     }
159
160     ObjEntity getEntity() {
161         return entity;
162     }
163
164     void setEntity(ObjEntity entity) {
165         this.entity = entity;
166     }
167
168     ObjRelationship getIncoming() {
169         return incoming;
170     }
171
172     void setIncoming(ObjRelationship incoming) {
173         this.incoming = incoming;
174         this.categorizeByParent = incoming != null && incoming.isToMany();
175     }
176
177     FlatPrefetchTreeNode getParent() {
178         return parent;
179     }
180
181     void setParent(FlatPrefetchTreeNode parent) {
182         this.parent = parent;
183     }
184
185     Collection getChildren() {
186         return children;
187     }
188
189     /**
190      * Finds
191      */
192     // TODO: there should be a better solution..
193 void disableNodesConflictingWithQualifier(Expression qualifier) {
194
195     }
196
197     /**
198      * Returns whether this tree node is "phantom", i.e. query result is not expected to
199      * provide data for it and it simply sits between two other nodes.
200      */
201     boolean isPhantom() {
202         return phantom;
203     }
204
205     void setPhantom(boolean phantom) {
206         this.phantom = phantom;
207     }
208
209     /**
210      * Returns a source label for a given target label.
211      */
212     String sourceForTarget(String targetColumn) {
213         if (targetColumn != null && columns != null) {
214             for (int i = 0; i < columns.length; i++) {
215                 if (targetColumn.equals(columns[i].getName())) {
216                     return columns[i].getLabel();
217                 }
218             }
219         }
220
221         return null;
222     }
223
224     /**
225      * Looks up a previously resolved object using an ObjectId map as a key. Returns null
226      * if no matching object exists.
227      */
228     DataObject getResolved(Map id) {
229         return (DataObject) resolved.get(id);
230     }
231
232     /**
233      * Registers an object in a map of resolved objects, connects this object to parent if
234      * parent exists.
235      */
236     void putResolved(Map id, DataObject object) {
237         resolved.put(id, object);
238     }
239
240     void connectToParent(DataObject object, DataObject parent) {
241         if (parent != null && categorizeByParent) {
242             // TODO: this leaves a hole - duplicates
243 List peers = (List ) partitionedByParent.get(parent);
244             peers.add(object);
245         }
246     }
247
248     void connectToParents() {
249         if (!isPhantom() && categorizeByParent) {
250             Iterator it = partitionedByParent.entrySet().iterator();
251             while (it.hasNext()) {
252                 Map.Entry entry = (Map.Entry ) it.next();
253
254                 DataObject root = (DataObject) entry.getKey();
255                 List related = (List ) entry.getValue();
256                 ToManyList toManyList = (ToManyList) root
257                         .readProperty(incoming.getName());
258                 toManyList.setObjectList(related);
259             }
260         }
261
262         // recursively connect to children
263 if (children != null) {
264
265             Iterator it = children.iterator();
266             while (it.hasNext()) {
267                 FlatPrefetchTreeNode child = (FlatPrefetchTreeNode) it.next();
268                 child.connectToParents();
269             }
270         }
271     }
272
273     /**
274      * Returns an ObjectId map from the flat row.
275      */
276     Map idFromFlatRow(DataRow flatRow) {
277
278         // TODO: should we also check for nulls in ID (and skip such rows) - this will
279 // likely be an indicator of an outer join ... and considering SQLTemplate,
280 // this is reasonable to expect...
281
282         Map id = new TreeMap ();
283         for (int i = 0; i < idIndices.length; i++) {
284             Object value = flatRow.get(columns[idIndices[i]].getLabel());
285             id.put(columns[idIndices[i]].getName(), value);
286         }
287
288         return id;
289     }
290
291     /**
292      * Returns a DataRow from the flat row.
293      */
294     DataRow rowFromFlatRow(DataRow flatRow) {
295         DataRow row = new DataRow(rowCapacity);
296
297         // extract subset of flat row columns, recasting to the target keys
298 for (int i = 0; i < columns.length; i++) {
299             row.put(columns[i].getName(), flatRow.get(columns[i].getLabel()));
300         }
301
302         return row;
303     }
304
305     /**
306      * Builds a prefetch tree for a cartesian product of joined DataRows from multiple
307      * entities.
308      */
309     private void buildTree(Collection jointPrefetchKeys, Collection qualifierDBKeys) {
310
311         this.phantom = false;
312
313         // assemble tree...
314 Iterator it = jointPrefetchKeys.iterator();
315         while (it.hasNext()) {
316             String prefetchPath = (String ) it.next();
317             addChildWithPath(prefetchPath, qualifierDBKeys);
318         }
319
320         // tree is complete; now create descriptors of non-phantom nodes
321 Closure c = new Closure() {
322
323             public void execute(Object input) {
324                 FlatPrefetchTreeNode node = (FlatPrefetchTreeNode) input;
325                 if (!node.isPhantom()) {
326                     node.buildRowMapping();
327                     node.buildPKIndex();
328                 }
329             }
330         };
331         executeDepthFirst(c);
332     }
333
334     /**
335      * Configures row columns mapping for this node entity.
336      */
337     private void buildRowMapping() {
338         Map targetSource = new TreeMap ();
339         String prefix = buildPrefix(new StringBuffer ()).toString();
340
341         // find propagated keys, assuming that only one-step joins
342 // share their column(s) with parent
343
344         if (getParent() != null
345                 && !getParent().isPhantom()
346                 && getIncoming() != null
347                 && !getIncoming().isFlattened()) {
348
349             DbRelationship r = (DbRelationship) getIncoming().getDbRelationships().get(0);
350             Iterator it = r.getJoins().iterator();
351             while (it.hasNext()) {
352                 DbJoin join = (DbJoin) it.next();
353                 String source = getParent().sourceForTarget(join.getSourceName());
354
355                 if (source == null) {
356                     throw new CayenneRuntimeException(
357                             "Propagated column value is not configured for parent node. Join: "
358                                     + join);
359                 }
360
361                 appendColumn(targetSource, join.getTargetName(), source);
362             }
363         }
364
365         // add class attributes
366 Iterator attributes = getEntity().getAttributes().iterator();
367         while (attributes.hasNext()) {
368             ObjAttribute attribute = (ObjAttribute) attributes.next();
369             String target = attribute.getDbAttributePath();
370
371             appendColumn(targetSource, target, prefix + target);
372         }
373
374         // add relationships
375 Iterator relationships = entity.getRelationships().iterator();
376         while (relationships.hasNext()) {
377             ObjRelationship rel = (ObjRelationship) relationships.next();
378             DbRelationship dbRel = (DbRelationship) rel.getDbRelationships().get(0);
379             Iterator dbAttributes = dbRel.getSourceAttributes().iterator();
380
381             while (dbAttributes.hasNext()) {
382                 DbAttribute attribute = (DbAttribute) dbAttributes.next();
383                 String target = attribute.getName();
384
385                 appendColumn(targetSource, target, prefix + target);
386             }
387         }
388
389         // add unmapped PK
390 Iterator pks = getEntity().getDbEntity().getPrimaryKey().iterator();
391         while (pks.hasNext()) {
392             DbAttribute pk = (DbAttribute) pks.next();
393             appendColumn(targetSource, pk.getName(), prefix + pk.getName());
394         }
395
396         int size = targetSource.size();
397         this.rowCapacity = (int) Math.ceil(size / 0.75);
398         this.columns = new ColumnDescriptor[size];
399         targetSource.values().toArray(columns);
400     }
401
402     private ColumnDescriptor appendColumn(Map map, String name, String label) {
403         ColumnDescriptor column = (ColumnDescriptor) map.get(name);
404
405         if (column == null) {
406             column = new ColumnDescriptor();
407             column.setName(name);
408             column.setLabel(label);
409             map.put(name, column);
410         }
411
412         return column;
413     }
414
415     /**
416      * Recursively prepends "prefix" to provided buffer. Prefix is DB path from the first
417      * non-phantom parent node in the tree.
418      */
419     StringBuffer buildPrefix(StringBuffer buffer) {
420
421         if (this.getIncoming() == null || getParent() == null) {
422             return buffer;
423         }
424
425         if (getIncoming() != null) {
426             String subpath = getIncoming().getDbRelationshipPath();
427             buffer.insert(0, '.');
428             buffer.insert(0, subpath);
429         }
430
431         if (parent != null) {
432             parent.buildPrefix(buffer);
433         }
434
435         return buffer;
436     }
437
438     /**
439      * Creates an internal index of PK columns in the result.
440      */
441     private void buildPKIndex() {
442         // index PK
443 List pks = getEntity().getDbEntity().getPrimaryKey();
444         this.idIndices = new int[pks.size()];
445
446         // this is needed for checking that a valid index is made
447 Arrays.fill(idIndices, -1);
448
449         for (int i = 0; i < idIndices.length; i++) {
450             DbAttribute pk = (DbAttribute) pks.get(i);
451
452             for (int j = 0; j < columns.length; j++) {
453                 if (pk.getName().equals(columns[j].getName())) {
454                     idIndices[i] = j;
455                     break;
456                 }
457             }
458
459             // sanity check
460 if (idIndices[i] == -1) {
461                 throw new CayenneRuntimeException("PK column is not part of result row: "
462                         + pk.getName());
463             }
464         }
465     }
466
467     /**
468      * Walks the tree in depth-first manner, executing provided closure with each node.
469      */
470     void executeDepthFirst(Closure closure) {
471
472         closure.execute(this);
473
474         if (children != null) {
475             Iterator it = children.iterator();
476             while (it.hasNext()) {
477                 FlatPrefetchTreeNode child = (FlatPrefetchTreeNode) it.next();
478                 child.executeDepthFirst(closure);
479             }
480         }
481     }
482
483     /**
484      * Processes path, linking all intermediate children to each other.
485      */
486     private FlatPrefetchTreeNode addChildWithPath(
487             String prefetchPath,
488             Collection qualifierDBKeys) {
489
490         Iterator it = entity.resolvePathComponents(prefetchPath);
491
492         if (!it.hasNext()) {
493             return null;
494         }
495
496         ObjRelationship r = null;
497         FlatPrefetchTreeNode lastChild = this;
498
499         while (it.hasNext()) {
500             r = (ObjRelationship) it.next();
501             lastChild = lastChild.addChild(r);
502         }
503
504         // mark last node as non-phantom if qualifier keys rules don't block it
505 boolean block = shouldBlockPrefetch(prefetchPath, r, qualifierDBKeys);
506
507         lastChild.setPhantom(block);
508         return lastChild;
509     }
510
511     // a hack for blocking prefetches on to many with conflicting qualifier that would
512 // otherwise result in incorrect to-many list.
513 private boolean shouldBlockPrefetch(
514             String prefetchKey,
515             ObjRelationship lastRelationship,
516             Collection qualifierDBKeys) {
517
518         if (qualifierDBKeys.isEmpty()) {
519             return false;
520         }
521
522         if (lastRelationship == null || !lastRelationship.isToMany()) {
523             return false;
524         }
525
526         Expression dbPath = entity.translateToDbPath(Expression.fromString(prefetchKey));
527         String path = dbPath.getOperand(0).toString();
528
529         Iterator it = qualifierDBKeys.iterator();
530         while (it.hasNext()) {
531             String next = (String ) it.next();
532             if (next.startsWith(path)) {
533                 logObj.warn("*** Joint prefetch '"
534                         + path
535                         + "' was ignored as it conflicts with qualifier path '"
536                         + next
537                         + "'. Consider using regular prefetch.");
538                 return true;
539             }
540         }
541
542         return false;
543     }
544
545     /**
546      * Adds a direct child to this node.
547      */
548     private FlatPrefetchTreeNode addChild(ObjRelationship outgoing) {
549         FlatPrefetchTreeNode child = null;
550
551         if (children == null) {
552             children = new ArrayList ();
553         }
554         else {
555             Iterator it = children.iterator();
556             while (it.hasNext()) {
557                 FlatPrefetchTreeNode next = (FlatPrefetchTreeNode) it.next();
558                 if (next.getIncoming() == outgoing) {
559                     child = next;
560                     break;
561                 }
562             }
563         }
564
565         if (child == null) {
566             child = new FlatPrefetchTreeNode();
567             child.setPhantom(true);
568             child.setIncoming(outgoing);
569             child.setEntity((ObjEntity) outgoing.getTargetEntity());
570             child.setParent(this);
571             children.add(child);
572         }
573
574         return child;
575     }
576
577     final class DBPathExtractor extends TraversalHelper {
578
579         Collection paths;
580         ObjEntity rootEntity;
581
582         DBPathExtractor(ObjEntity rootEntity) {
583             this.rootEntity = rootEntity;
584         }
585
586         Collection getPaths() {
587             return paths != null ? paths : Collections.EMPTY_SET;
588         }
589
590         public void startNode(Expression node, Expression parentNode) {
591             Expression dbPath;
592             if (node.getType() == Expression.OBJ_PATH) {
593                 dbPath = rootEntity.translateToDbPath(node);
594             }
595             else if (node.getType() == Expression.DB_PATH) {
596                 dbPath = node;
597             }
598             else {
599                 return;
600             }
601
602             if (paths == null) {
603                 paths = new HashSet ();
604             }
605             paths.add(dbPath.getOperand(0));
606         }
607     }
608 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags