Source code: org/enhydra/xml/xmlc/dom/generic/BuildMethodMappings.java
1 /*
2 * Enhydra Java Application Server Project
3 *
4 * The contents of this file are subject to the Enhydra Public License
5 * Version 1.1 (the "License"); you may not use this file except in
6 * compliance with the License. You may obtain a copy of the License on
7 * the Enhydra web site ( http://www.enhydra.org/ ).
8 *
9 * Software distributed under the License is distributed on an "AS IS"
10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
11 * the License for the specific terms governing rights and limitations
12 * under the License.
13 *
14 * The Initial Developer of the Enhydra Application Server is Lutris
15 * Technologies, Inc. The Enhydra Application Server and portions created
16 * by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc.
17 * All Rights Reserved.
18 *
19 * Contributor(s):
20 *
21 * $Id$
22 */
23
24 package org.enhydra.xml.xmlc.dom.generic;
25
26 import org.enhydra.xml.xmlc.XMLCError;
27 import org.enhydra.xml.xmlc.codegen.JavaLang;
28 import org.enhydra.xml.dom.DOMOps;
29 import java.util.HashMap;
30 import java.util.ArrayList;
31 import java.util.Collections;
32 import java.util.Map;
33 import java.util.Iterator;
34 import java.lang.Comparable;
35 import org.w3c.dom.*;
36
37 /*
38 * FIXME: If children were moved to methods that create multiple children
39 * of a single node (using the mechanism for chaining, only adding a
40 * lastChild argument, it should create better packed methods.
41 */
42
43 //FIXME: Need better overview.
44
45 /**
46 * Class to calculate which elements are to have build methods created for
47 * them based on trying to optimize the amount of code (create-cost) in each
48 * build methods without overflowing the maximum create-cost.
49 * <P>
50 * The advantage of this object determining where build methods are created in
51 * a seperate traversal from creating the build methods is that the
52 * determination is best down from the bottom up, which creating the methods
53 * is done top-down. The seperation also keeps the code cleaner and easier to
54 * understand. The cost is building an intermediate table.
55 */
56 final class BuildMethodMappings {
57 /**
58 * Create-cost to call a build-method.
59 */
60 public static final int BUILD_METHOD_CALL_CREATE_COST = 1;
61
62 /**
63 * Create-cost to create an element node. Slightly higher due
64 * to possibility of initializing access methods.
65 */
66 public static final int CREATE_ELEMENT_NODE_CREATE_COST = 2;
67
68 /**
69 * Maximum creation-cost that a single build method can handle.
70 */
71 private int fMaxCreateCostPerBuildMethod;
72
73 /*
74 * Table of node record.
75 */
76 private HashMap fNodeRecordTable = new HashMap();
77
78 /**
79 * Temporary table used for sorting child elements. This table
80 * never used recursively, so one can be reused for efficient.
81 */
82 private ArrayList fTmpElementSort = new ArrayList();
83
84 /**
85 * Node record.
86 */
87 private class Record implements Comparable {
88 /**
89 * The node we are associated with.
90 */
91 public Node fNode;
92
93 /**
94 * The minimum cost to create this node in a method. This includes
95 * non-element children and attribute costs, with element-children
96 * costs being the cost to call another build method.
97 */
98 public int fMinMethodCost;
99
100 /**
101 * The total cost to create this node and its children in this build
102 * method. It includes calls to other build methods, but not the cost
103 * in other build methods.
104 */
105 public int fMethodTotalCost;
106
107 /**
108 * The total cost to create this node and its children. This
109 * includes cost in other build methods, but excludes the cost
110 * of calls to other build methods. Its the cost to create the
111 * tree to this point.
112 */
113 public int fTreeTotalCost;
114
115 /**
116 * Should this element be at the root of a build method?
117 */
118 public boolean fMethodRoot;
119
120 /**
121 * Should the children be created in a chained method?
122 */
123 public boolean fChainedChildrenMethods;
124
125 /**
126 * Constructor. Initialize base costs.
127 */
128 public Record(Node node) {
129 fNode = node;
130 if (node instanceof Document) {
131 fMinMethodCost = 0;
132 } else if (fNode instanceof Element) {
133 fMinMethodCost = CREATE_ELEMENT_NODE_CREATE_COST;
134 } else {
135 fMinMethodCost = 1;
136 }
137 fMethodTotalCost = fMinMethodCost;
138 fTreeTotalCost = fMinMethodCost;
139
140 // Add self to table
141 fNodeRecordTable.put(node, this);
142 }
143
144 /**
145 * Sort by method cost in descending order. Allows this to be
146 * this object ot be used as key and value in a SortedMap.
147 */
148 public int compareTo(Object elem2) {
149 int cost2 = ((Record)elem2).fMethodTotalCost;
150 return ((fMethodTotalCost > cost2) ? -1 : ((fMethodTotalCost < cost2) ? 1 : 0));
151 }
152
153 /**
154 * Get string description for debugging.
155 */
156 public String toString() {
157 return "Node-rec: " + JavaLang.simpleClassName(fNode)
158 + " methodRoot=" + fMethodRoot
159 + " chained=" + fChainedChildrenMethods
160 + " minMethod=" + fMinMethodCost
161 + " methodTotal=" + fMethodTotalCost
162 + " treeTotal=" + fTreeTotalCost;
163 }
164 }
165
166 /**
167 * Constructor.
168 */
169 public BuildMethodMappings(int maxCreateCostPerBuildMethod,
170 Document document) {
171 fMaxCreateCostPerBuildMethod = maxCreateCostPerBuildMethod;
172 calculateTreeCosts(document);
173 }
174
175 /**
176 * Get the cost of creating a single node based on its type. This does
177 * not provide cumulative costs, its based on type only.
178 */
179 public static int getNodeTypeCost(Node node) {
180 if (node instanceof Element) {
181 return BuildMethodMappings.CREATE_ELEMENT_NODE_CREATE_COST;
182 } else {
183 return 1;
184 }
185 }
186
187 /**
188 * Get a record.
189 */
190 private Record getRecord(Node node) {
191 Record rec = (Record)fNodeRecordTable.get(node);
192 if (rec == null) {
193 throw new XMLCError("BUG: record not found: " + node);
194 }
195 return rec;
196 }
197
198 /**
199 * Convert a child to being build in another element, if this will reduce
200 * the cost of building the parent. Adjust the size of the parent.
201 */
202 private void moveChildIntoMethod(Record parent,
203 Record child) {
204 if ((!child.fMethodRoot)
205 && (child.fMethodTotalCost > BUILD_METHOD_CALL_CREATE_COST)) {
206 parent.fMethodTotalCost -= child.fMethodTotalCost;
207 parent.fMethodTotalCost += BUILD_METHOD_CALL_CREATE_COST;
208 child.fMethodRoot = true;
209 }
210 }
211
212 /**
213 * Move element children into other build methods until the cost of
214 * this element is below the maximum. Sorting to move largest first
215 * results in fewer methods being created.
216 */
217 private void adjustElementBuild(Record rec) {
218 // Build a descending sorted list of element children.
219 fTmpElementSort.clear();
220 for (Node child = rec.fNode.getFirstChild();
221 (child != null) && (rec.fMethodTotalCost >= fMaxCreateCostPerBuildMethod);
222 child = child.getNextSibling()) {
223 if (child instanceof Element) {
224 Record childRec = getRecord(child);
225 fTmpElementSort.add(childRec);
226 }
227 }
228
229 // Move largest-first into their own build methods until this
230 // method is no longer full.
231 Collections.sort(fTmpElementSort);
232 int numChildren = fTmpElementSort.size();
233 for (int idx = 0;
234 (idx < numChildren) && (rec.fMethodTotalCost >= fMaxCreateCostPerBuildMethod);
235 idx++) {
236 moveChildIntoMethod(rec, (Record)fTmpElementSort.get(idx));
237 }
238 if (rec.fMethodTotalCost > fMaxCreateCostPerBuildMethod) {
239 throw new XMLCError("BUG: adjustElementBuild failed to adjust method cost below max: " + rec);
240 }
241 }
242
243 /**
244 * Adjust an element record, if nececssary, to keep it from overflowing
245 * the maximum build method create-cost. This must be called *before* the
246 * parent record is created.
247 */
248 private void adjustElementRecord(Record rec) {
249 if (rec.fMinMethodCost > fMaxCreateCostPerBuildMethod) {
250 // Create a chained method.
251 rec.fMethodRoot = true;
252 rec.fChainedChildrenMethods = true;
253 } else if (rec.fMethodTotalCost >= fMaxCreateCostPerBuildMethod) {
254 // Split children into other build methods until this one fits
255 adjustElementBuild(rec);
256 }
257 }
258
259 /**
260 * Sum a record with one of its children.
261 */
262 private void sumRecords(Record nodeRec,
263 Record childRec) {
264 // Min cost is based on if node could be but in seperate method
265 if (childRec.fNode instanceof Element) {
266 nodeRec.fMinMethodCost += BUILD_METHOD_CALL_CREATE_COST;
267 } else {
268 nodeRec.fMinMethodCost += childRec.fMethodTotalCost;
269 }
270 // Cost is based on if node is in seperate method
271 if (!childRec.fMethodRoot) {
272 nodeRec.fMethodTotalCost += childRec.fMethodTotalCost;
273 }
274 // Complete tree cost
275 nodeRec.fTreeTotalCost += childRec.fTreeTotalCost;
276 }
277
278 /**
279 * Calculate the costs of an element and its element's attributes.
280 */
281 private Record calculateElementCosts(Node element) {
282 Record rec = new Record(element);
283 NamedNodeMap attrList = element.getAttributes();
284 if (attrList != null) {
285 for (int idx = 0; idx < attrList.getLength(); idx++) {
286 Attr attr = (Attr)attrList.item(idx);
287 if (attr.getSpecified()) {
288 Record attrRec = calculateTreeCosts(attr);
289 sumRecords(rec, attrRec);
290 }
291 }
292 }
293 return rec;
294 }
295
296 /**
297 * Traverse the tree, calculating costs and determining where build methods
298 * should be created. This builds the table of node records.
299 * @return The node record.
300 */
301 private Record calculateTreeCosts(Node node) {
302 Record rec;
303 if (node instanceof Element) {
304 rec = calculateElementCosts(node);
305 } else {
306 rec = new Record(node);
307 }
308
309 // depth-fist traversal, summing cost of child elements;
310 for (Node child = node.getFirstChild(); child != null;
311 child = child.getNextSibling()) {
312 sumRecords(rec, calculateTreeCosts(child));
313 }
314 if (node instanceof Element) {
315 adjustElementRecord(rec);
316 }
317 return rec;
318 }
319
320 /**
321 * Should a new method be created at the root of this element.
322 */
323 public boolean isMethodRoot(Node element) {
324 return getRecord(element).fMethodRoot;
325 }
326
327 /**
328 * Should the children be created in a chained method?
329 */
330 public boolean useChainedChildrenMethods(Node node) {
331 return getRecord(node).fChainedChildrenMethods;
332 }
333
334 /**
335 * Get the minimum method cost of a node.
336 */
337 public int getMinMethodCost(Node node) {
338 return getRecord(node).fMinMethodCost;
339 }
340
341 /**
342 * Get the method total cost of a node.
343 */
344 public int getMethodTotalCost(Node node) {
345 return getRecord(node).fMethodTotalCost;
346 }
347
348 /**
349 * Get the tree total cost of a node.
350 */
351 public int getTreeTotalCost(Node node) {
352 return getRecord(node).fTreeTotalCost;
353 }
354
355 /**
356 * Get a string repersentation of an entry for debugging.
357 */
358 public String toString(Node node) {
359 return getRecord(node).toString();
360 }
361 }