Java > Open Source Codes > net > sf > saxon > trans > KeyManager


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags