001: package net.sf.saxon.trans;
002:
003: import net.sf.saxon.Configuration;
004: import net.sf.saxon.functions.Tokenize;
005: import net.sf.saxon.functions.SystemFunction;
006: import net.sf.saxon.expr.*;
007: import net.sf.saxon.instruct.SlotManager;
008: import net.sf.saxon.om.*;
009: import net.sf.saxon.pattern.ContentTypeTest;
010: import net.sf.saxon.pattern.NodeTestPattern;
011: import net.sf.saxon.pattern.Pattern;
012: import net.sf.saxon.pattern.UnionPattern;
013: import net.sf.saxon.sort.LocalOrderComparer;
014: import net.sf.saxon.sort.IntHashMap;
015: import net.sf.saxon.style.StandardNames;
016: import net.sf.saxon.type.BuiltInSchemaFactory;
017: import net.sf.saxon.type.SchemaType;
018: import net.sf.saxon.type.Type;
019: import net.sf.saxon.value.AtomicValue;
020: import net.sf.saxon.value.NumericValue;
021: import net.sf.saxon.value.StringValue;
022:
023: import javax.xml.transform.TransformerConfigurationException;
024: import java.io.Serializable;
025: import java.lang.ref.WeakReference;
026: import java.text.Collator;
027: import java.util.ArrayList;
028: import java.util.HashMap;
029: import java.util.List;
030: import java.util.WeakHashMap;
031:
032: /**
033: * KeyManager manages the set of key definitions in a stylesheet, and the indexes
034: * associated with these key definitions. It handles xsl:sort-key as well as xsl:key
035: * definitions.
036: *
037: * <p>The memory management in this class is subtle, with extensive use of weak references.
038: * The idea is that an index should continue to exist in memory so long as both the compiled
039: * stylesheet and the source document exist in memory: if either is removed, the index should
040: * go too. The document itself holds no reference to the index. The compiled stylesheet (which
041: * owns the KeyManager) holds a weak reference to the index. The index, of course, holds strong
042: * references to the nodes in the document. The Controller holds a strong reference to the
043: * list of indexes used for each document, so that indexes remain in memory for the duration
044: * of a transformation even if the documents themselves are garbage collected.</p>
045: *
046: * <p>Potentially there is a need for more than one index for a given key name, depending
047: * on the primitive type of the value provided to the key() function. An index is built
048: * corresponding to the type of the requested value; if subsequently the key() function is
049: * called with the same name and a different type of value, then a new index is built.</p>
050: *
051: * @author Michael H. Kay
052: */
053:
054: public class KeyManager implements Serializable {
055:
056: private IntHashMap keyList; // one entry for each named key; the entry contains
057: // a list of key definitions with that name
058: private transient WeakHashMap docIndexes;
059:
060: // one entry for each document that is in memory;
061: // the entry contains a HashMap mapping the fingerprint of
062: // the key name plus the primitive item type
063: // to the HashMap that is the actual index
064: // of key/value pairs.
065:
066: /**
067: * create a KeyManager and initialise variables
068: */
069:
070: public KeyManager(Configuration config) {
071: keyList = new IntHashMap(10);
072: docIndexes = new WeakHashMap(10);
073: // Create a key definition for the idref() function
074: registerIdrefKey(config);
075: }
076:
077: /**
078: * An internal key definition is used to support the idref() function. The key definition
079: * is equivalent to xsl:key match="element(*, xs:IDREF) | element(*, IDREFS) |
080: * attribute(*, xs:IDREF) | attribute(*, IDREFS)" use=".". This method creates this
081: * key definition.
082: * @param config The configuration. This is needed because the patterns that are
083: * generated need access to schema information.
084: */
085:
086: private void registerIdrefKey(Configuration config) {
087: SchemaType idref = BuiltInSchemaFactory
088: .getSchemaType(StandardNames.XS_IDREF);
089: SchemaType idrefs = BuiltInSchemaFactory
090: .getSchemaType(StandardNames.XS_IDREFS);
091:
092: ContentTypeTest idrefTest = new ContentTypeTest(Type.ATTRIBUTE,
093: idref, config);
094: idrefTest.setMatchDTDTypes(true);
095: Pattern idrefAtt = new NodeTestPattern(idrefTest);
096:
097: ContentTypeTest idrefsTest = new ContentTypeTest(
098: Type.ATTRIBUTE, idrefs, config);
099: idrefsTest.setMatchDTDTypes(true);
100: Pattern idrefsAtt = new NodeTestPattern(idrefsTest);
101:
102: Pattern idrefElem = new NodeTestPattern(new ContentTypeTest(
103: Type.ELEMENT, idref, config));
104: Pattern idrefsElem = new NodeTestPattern(new ContentTypeTest(
105: Type.ELEMENT, idrefs, config));
106: Pattern att = new UnionPattern(idrefAtt, idrefsAtt);
107: Pattern elem = new UnionPattern(idrefElem, idrefsElem);
108: Pattern all = new UnionPattern(att, elem);
109: Expression eval = new Atomizer(new ContextItemExpression(),
110: config);
111: Tokenize use = (Tokenize) SystemFunction.makeSystemFunction(
112: "tokenize", 2, config.getNamePool());
113: StringValue regex = new StringValue("\\s");
114: Expression[] params = { eval, regex };
115: use.setArguments(params);
116: KeyDefinition key = new KeyDefinition(all, use, null, null);
117: try {
118: addKeyDefinition(StandardNames.XS_IDREFS, key, config
119: .getNamePool());
120: } catch (TransformerConfigurationException err) {
121: throw new AssertionError(err); // shouldn't happen
122: }
123: }
124:
125: /**
126: * Register a key definition. Note that multiple key definitions with the same name are
127: * allowed
128: * @param fingerprint Integer representing the name of the key
129: * @param keydef The details of the key's definition
130: * @param namePool
131: */
132:
133: public void addKeyDefinition(int fingerprint, KeyDefinition keydef,
134: NamePool namePool) throws TransformerConfigurationException {
135: //Integer keykey = new Integer(fingerprint);
136: ArrayList v = (ArrayList) keyList.get(fingerprint);
137: if (v == null) {
138: v = new ArrayList(3);
139: keyList.put(fingerprint, v);
140: } else {
141: // check the consistency of the key definitions
142: String collation = keydef.getCollationName();
143: if (collation == null) {
144: for (int i = 0; i < v.size(); i++) {
145: if (((KeyDefinition) v.get(i)).getCollationName() != null) {
146: throw new TransformerConfigurationException(
147: "All keys with the same name must use the same collation");
148: }
149: }
150: } else {
151: for (int i = 0; i < v.size(); i++) {
152: if (!collation.equals(((KeyDefinition) v.get(i))
153: .getCollationName())) {
154: throw new TransformerConfigurationException(
155: "All keys with the same name must use the same collation");
156: }
157: }
158: }
159:
160: }
161: v.add(keydef);
162: boolean bc = false;
163: for (int i = 0; i < v.size(); i++) {
164: if (((KeyDefinition) v.get(i)).isBackwardsCompatible()) {
165: bc = true;
166: break;
167: }
168: }
169: if (bc) {
170: // In backwards compatibility mode, convert all the use-expression results to sequences of strings
171: for (int i = 0; i < v.size(); i++) {
172: KeyDefinition kd = (KeyDefinition) v.get(i);
173: kd.setBackwardsCompatible(true);
174: if (kd.getBody().getItemType(
175: namePool.getTypeHierarchy()) != Type.STRING_TYPE) {
176: Expression exp = new AtomicSequenceConverter(kd
177: .getBody(), Type.STRING_TYPE);
178: kd.setBody(exp);
179: }
180: }
181: }
182:
183: }
184:
185: /**
186: * Get all the key definitions that match a particular fingerprint
187: * @param fingerprint The fingerprint of the name of the required key
188: * @return The key definition of the named key if there is one, or null otherwise.
189: */
190:
191: public List getKeyDefinitions(int fingerprint) {
192: return (List) keyList.get(fingerprint);
193: }
194:
195: /**
196: * Build the index for a particular document for a named key
197: * @param fingerprint The fingerprint of the name of the required key
198: * @param doc The source document in question
199: * @param context The dynamic context
200: * @return the index in question, as a HashMap mapping a key value onto a ArrayList of nodes
201: */
202:
203: private synchronized HashMap buildIndex(int fingerprint,
204: int itemType, DocumentInfo doc, XPathContext context)
205: throws XPathException {
206:
207: List definitions = getKeyDefinitions(fingerprint);
208: if (definitions == null) {
209: DynamicError de = new DynamicError("Key "
210: + context.getNamePool().getDisplayName(fingerprint)
211: + " has not been defined");
212: de.setXPathContext(context);
213: de.setErrorCode("XTDE1260");
214: throw de;
215: }
216:
217: HashMap index = new HashMap(100);
218:
219: // There may be multiple xsl:key definitions with the same name. Index them all.
220: for (int k = 0; k < definitions.size(); k++) {
221: constructIndex(doc, index, (KeyDefinition) definitions
222: .get(k), itemType, context, k == 0);
223: }
224:
225: return index;
226:
227: }
228:
229: /**
230: * Process one key definition to add entries to an index
231: */
232:
233: private void constructIndex(DocumentInfo doc, HashMap index,
234: KeyDefinition keydef, int soughtItemType,
235: XPathContext context, boolean isFirst)
236: throws XPathException {
237:
238: Pattern match = keydef.getMatch();
239: Expression use = keydef.getUse();
240: Collator collator = keydef.getCollation();
241:
242: NodeInfo curr;
243: XPathContextMajor xc = context.newContext();
244: xc.setOrigin(keydef);
245:
246: // The use expression (or sequence constructor) may contain local variables.
247: SlotManager map = keydef.getStackFrameMap();
248: if (map != null) {
249: xc.openStackFrame(map);
250: }
251:
252: int nodeType = match.getNodeKind();
253:
254: if (nodeType == Type.ATTRIBUTE || nodeType == Type.NODE
255: || nodeType == Type.DOCUMENT) {
256: // If the match pattern allows attributes to appear, we must visit them.
257: // We also take this path in the pathological case where the pattern can match
258: // document nodes.
259: SequenceIterator all = doc
260: .iterateAxis(Axis.DESCENDANT_OR_SELF);
261: while (true) {
262: curr = (NodeInfo) all.next();
263: if (curr == null) {
264: break;
265: }
266: if (curr.getNodeKind() == Type.ELEMENT) {
267: SequenceIterator atts = curr
268: .iterateAxis(Axis.ATTRIBUTE);
269: while (true) {
270: NodeInfo att = (NodeInfo) atts.next();
271: if (att == null) {
272: break;
273: }
274: if (match.matches(att, xc)) {
275: processKeyNode(att, use, soughtItemType,
276: collator, index, xc, isFirst);
277: }
278: }
279: if (nodeType == Type.NODE) {
280: // index the element as well as its attributes
281: if (match.matches(curr, xc)) {
282: processKeyNode(curr, use, soughtItemType,
283: collator, index, xc, isFirst);
284: }
285: }
286: } else {
287: if (match.matches(curr, xc)) {
288: processKeyNode(curr, use, soughtItemType,
289: collator, index, xc, isFirst);
290: }
291: }
292: }
293:
294: } else {
295: SequenceIterator all = doc.iterateAxis(Axis.DESCENDANT,
296: match.getNodeTest());
297: // If the match is a nodetest, we avoid testing it again
298: while (true) {
299: curr = (NodeInfo) all.next();
300: if (curr == null) {
301: break;
302: }
303: if (match instanceof NodeTestPattern
304: || match.matches(curr, xc)) {
305: processKeyNode(curr, use, soughtItemType, collator,
306: index, xc, isFirst);
307: }
308: }
309: }
310: //if (map != null) {
311: // b.closeStackFrame();
312: //}
313: }
314:
315: /**
316: * Process one matching node, adding entries to the index if appropriate
317: * @param curr the node being processed
318: * @param use the expression used to compute the key values for this node
319: * @param soughtItemType the primitive item type of the argument to the key() function that triggered
320: * this index to be built
321: * @param collation the collation defined in the key definition
322: * @param index the index being constructed
323: * @param xc the context for evaluating expressions
324: * @param isFirst indicates whether this is the first key definition with a given key name (which means
325: * no sort of the resulting key entries is required)
326: */
327:
328: private void processKeyNode(NodeInfo curr, Expression use,
329: int soughtItemType, Collator collation, HashMap index,
330: XPathContext xc, boolean isFirst) throws XPathException {
331:
332: // Make the node we are testing the context node and the current node,
333: // with context position and context size set to 1
334:
335: AxisIterator si = SingletonIterator.makeIterator(curr);
336: si.next(); // need to position iterator at first node
337:
338: xc.setCurrentIterator(si);
339: //xc.getController().setCurrentIterator(si); X
340:
341: // Evaluate the "use" expression against this context node
342:
343: SequenceIterator useval = use.iterate(xc);
344: while (true) {
345: AtomicValue item = (AtomicValue) useval.next();
346: if (item == null) {
347: break;
348: }
349: int actualItemType = item.getItemType(null)
350: .getPrimitiveType();
351: if (!Type.isComparable(actualItemType, soughtItemType)) {
352: // if the types aren't comparable, simply ignore this key value
353: break;
354: }
355: Object val;
356:
357: if (soughtItemType == Type.UNTYPED_ATOMIC) {
358: // if the supplied key value is untyped atomic, we build an index using the
359: // actual type returned by the use expression
360: if (collation == null) {
361: val = item.getStringValue();
362: } else {
363: val = collation.getCollationKey(item
364: .getStringValue());
365: }
366: } else if (soughtItemType == Type.STRING) {
367: // if the supplied key value is a string, there is no match unless the use expression
368: // returns a string or an untyped atomic value
369: if (collation == null) {
370: val = item.getStringValue();
371: } else {
372: val = collation.getCollationKey(item
373: .getStringValue());
374: }
375: } else {
376: // Ignore NaN values
377: if (item instanceof NumericValue
378: && ((NumericValue) item).isNaN()) {
379: break;
380: }
381: try {
382: val = item.convert(soughtItemType, xc);
383: } catch (XPathException err) {
384: // ignore values that can't be converted to the required type
385: break;
386: }
387: }
388:
389: ArrayList nodes = (ArrayList) index.get(val);
390: if (nodes == null) {
391: // this is the first node with this key value
392: nodes = new ArrayList(4);
393: index.put(val, nodes);
394: nodes.add(curr);
395: } else {
396: // this is not the first node with this key value.
397: // add the node to the list of nodes for this key,
398: // unless it's already there
399: if (isFirst) {
400: // if this is the first index definition that we're processing,
401: // then this node must be after all existing nodes in document
402: // order, or the same node as the last existing node
403: if (nodes.get(nodes.size() - 1) != curr) {
404: nodes.add(curr);
405: }
406: } else {
407: // otherwise, we need to insert the node at the correct
408: // position in document order.
409: LocalOrderComparer comparer = LocalOrderComparer
410: .getInstance();
411: for (int i = 0; i < nodes.size(); i++) {
412: int d = comparer.compare(curr, (NodeInfo) nodes
413: .get(i));
414: if (d <= 0) {
415: if (d == 0) {
416: // node already in list; do nothing
417: } else {
418: // add the node at this position
419: nodes.add(i, curr);
420: }
421: return;
422: }
423: // else continue round the loop
424: }
425: // if we're still here, add the new node at the end
426: nodes.add(curr);
427: }
428: }
429: }
430:
431: }
432:
433: /**
434: * Get the nodes with a given key value
435: * @param fingerprint The fingerprint of the name of the required key
436: * @param doc The source document in question
437: * @param value The required key value
438: * @param context The dynamic context, needed only the first time when the key is being built
439: * @return an enumeration of nodes, always in document order
440: */
441:
442: public SequenceIterator selectByKey(int fingerprint,
443: DocumentInfo doc, AtomicValue value, XPathContext context)
444: throws XPathException {
445:
446: KeyDefinition definition = (KeyDefinition) getKeyDefinitions(
447: fingerprint).get(0);
448: // the itemType and collation and BC mode will be the same for all keys with the same name
449: Collator collation = definition.getCollation();
450: boolean backwardsCompatible = definition
451: .isBackwardsCompatible();
452:
453: if (backwardsCompatible) {
454: value = value.convert(Type.STRING, context);
455: }
456:
457: // If the key value is numeric, promote it to a double
458:
459: int itemType = value.getItemType(null).getPrimitiveType();
460: if (itemType == StandardNames.XS_INTEGER
461: || itemType == StandardNames.XS_DECIMAL
462: || itemType == StandardNames.XS_FLOAT) {
463: itemType = StandardNames.XS_DOUBLE;
464: value = value.convert(itemType, context);
465: }
466:
467: // No special action needed for anyURI to string promotion (it just seems to work: tests idky44, 45)
468:
469: Object indexObject = getIndex(doc, fingerprint, itemType);
470: if (indexObject instanceof String) {
471: // index is under construction
472: DynamicError de = new DynamicError(
473: "Key definition is circular");
474: de.setXPathContext(context);
475: de.setErrorCode("XTDE0640");
476: throw de;
477: }
478: HashMap index = (HashMap) indexObject;
479:
480: // If the index does not yet exist, then create it.
481: if (index == null) {
482: // Mark the index as being under construction, in case the definition is circular
483: putIndex(doc, fingerprint, itemType, "Under Construction",
484: context);
485: index = buildIndex(fingerprint, itemType, doc, context);
486: putIndex(doc, fingerprint, itemType, index, context);
487: }
488:
489: Object val;
490: if (itemType == Type.STRING || itemType == Type.UNTYPED_ATOMIC) {
491: if (collation == null) {
492: val = value.getStringValue();
493: } else {
494: val = collation.getCollationKey(value.getStringValue());
495: }
496: } else {
497: val = value;
498: }
499:
500: ArrayList nodes = (ArrayList) index.get(val);
501: if (nodes == null) {
502: return EmptyIterator.getInstance();
503: } else {
504: return new ListIterator(nodes);
505: }
506: }
507:
508: /**
509: * Save the index associated with a particular key, a particular item type,
510: * and a particular document. This
511: * needs to be done in such a way that the index is discarded by the garbage collector
512: * if the document is discarded. We therefore use a WeakHashMap indexed on the DocumentInfo,
513: * which returns HashMap giving the index for each key fingerprint. This index is itself another
514: * HashMap.
515: * The methods need to be synchronized because several concurrent transformations (which share
516: * the same KeyManager) may be creating indexes for the same or different documents at the same
517: * time.
518: */
519:
520: private synchronized void putIndex(DocumentInfo doc,
521: int keyFingerprint, int itemType, Object index,
522: XPathContext context) {
523: if (docIndexes == null) {
524: // it's transient, so it will be null when reloading a compiled stylesheet
525: docIndexes = new WeakHashMap(10);
526: }
527: WeakReference indexRef = (WeakReference) docIndexes.get(doc);
528: HashMap indexList;
529: if (indexRef == null || indexRef.get() == null) {
530: indexList = new HashMap(10);
531: // ensure there is a firm reference to the indexList for the duration of a transformation
532: context.getController().setUserData(doc, "key-index-list",
533: indexList);
534: docIndexes.put(doc, new WeakReference(indexList));
535: } else {
536: indexList = (HashMap) indexRef.get();
537: }
538: indexList.put(
539: new Long(((long) keyFingerprint) << 32 | itemType),
540: index);
541: }
542:
543: /**
544: * Get the index associated with a particular key, a particular source document,
545: * and a particular primitive item type
546: */
547:
548: private synchronized Object getIndex(DocumentInfo doc,
549: int keyFingerprint, int itemType) {
550: if (docIndexes == null) {
551: // it's transient, so it will be null when reloading a compiled stylesheet
552: docIndexes = new WeakHashMap(10);
553: }
554: WeakReference ref = (WeakReference) docIndexes.get(doc);
555: if (ref == null)
556: return null;
557: HashMap indexList = (HashMap) ref.get();
558: if (indexList == null)
559: return null;
560: return indexList.get(new Long(((long) keyFingerprint) << 32
561: | itemType));
562: }
563: }
564:
565: //
566: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
567: // you may not use this file except in compliance with the License. You may obtain a copy of the
568: // License at http://www.mozilla.org/MPL/
569: //
570: // Software distributed under the License is distributed on an "AS IS" basis,
571: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
572: // See the License for the specific language governing rights and limitations under the License.
573: //
574: // The Original Code is: all this file.
575: //
576: // The Initial Developer of the Original Code is Michael H. Kay.
577: //
578: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
579: //
580: // Contributor(s): none.
581: //
|