001: package net.sf.saxon.type;
002:
003: import net.sf.saxon.pattern.AnyNodeTest;
004: import net.sf.saxon.pattern.DocumentNodeTest;
005: import net.sf.saxon.pattern.NoNodeTest;
006: import net.sf.saxon.pattern.NodeTest;
007: import net.sf.saxon.sort.IntHashSet;
008:
009: import java.io.Serializable;
010: import java.util.HashMap;
011:
012: /**
013: * This class exists to provide answers to questions about the type hierarchy. Because
014: * such questions are potentially expensive, it caches the answers.
015: */
016:
017: public class TypeHierarchy implements Serializable {
018:
019: private HashMap map = new HashMap(100);
020: /**
021: * Constant denoting relationship between two types: A is the same type as B
022: */
023: public static final int SAME_TYPE = 0;
024: /**
025: * Constant denoting relationship between two types: A subsumes B
026: */
027: public static final int SUBSUMES = 1;
028: /**
029: * Constant denoting relationship between two types: A is subsumed by B
030: */
031: public static final int SUBSUMED_BY = 2;
032: /**
033: * Constant denoting relationship between two types: A overlaps B
034: */
035: public static final int OVERLAPS = 3;
036: /**
037: * Constant denoting relationship between two types: A is disjoint from B
038: */
039: public static final int DISJOINT = 4;
040:
041: //private String[] relnames = {"SAME", "SUBSUMES", "SUBSUMED_BY", "OVERLAPS", "DISJOINT"};
042:
043: public TypeHierarchy() {
044: }
045:
046: /**
047: * Determine whether type A is type B or one of its subtypes, recursively
048: *
049: * @param subtype identifies the first type
050: * @param supertype identifies the second type
051: * @return true if the first type is the second type or a (direct or
052: * indirect) subtype of the second type
053: */
054:
055: public boolean isSubType(ItemType subtype, ItemType super type) {
056: int relation = relationship(subtype, super type);
057: return (relation == SAME_TYPE || relation == SUBSUMED_BY);
058: }
059:
060: /**
061: * Determine the relationship of one item type to another.
062: * @param t1 the first item type
063: * @param t2 the second item type
064: * @return {@link #SAME_TYPE} if the types are the same; {@link #SUBSUMES} if the first
065: * type subsumes the second (that is, all instances of the second type are also instances
066: * of the first); {@link #SUBSUMED_BY} if the second type subsumes the first;
067: * {@link #OVERLAPS} if the two types overlap (have a non-empty intersection, but neither
068: * subsumes the other); {@link #DISJOINT} if the two types are disjoint (have an empty intersection)
069: */
070:
071: public int relationship(ItemType t1, ItemType t2) {
072: if (t1 == null) {
073: throw new NullPointerException();
074: }
075: if (t1.equals(t2)) {
076: return SAME_TYPE;
077: }
078: //System.err.println("getRelationship " + t1 + ", " + t2);
079: // Implement a cache
080: HashMap secondary = (HashMap) map.get(t1);
081: if (secondary == null) {
082: secondary = new HashMap(5);
083: map.put(t1, secondary);
084: }
085: Integer result = (Integer) secondary.get(t2);
086: if (result == null) {
087: int r = computeRelationship(t1, t2);
088: //System.err.println("Result " + relnames[r] + " computed");
089: secondary.put(t2, new Integer(r));
090: return r;
091: } else {
092: //System.err.println("Result " + relnames[result.intValue()] + " found in cache");
093: return result.intValue();
094: }
095: }
096:
097: /**
098: * Determine the relationship of one item type to another.
099: * @param t1 the first item type
100: * @param t2 the second item type
101: * @return {@link #SAME_TYPE} if the types are the same; {@link #SUBSUMES} if the first
102: * type subsumes the second (that is, all instances of the second type are also instances
103: * of the first); {@link #SUBSUMED_BY} if the second type subsumes the first;
104: * {@link #OVERLAPS} if the two types overlap (have a non-empty intersection, but neither
105: * subsumes the other); {@link #DISJOINT} if the two types are disjoint (have an empty intersection)
106: */
107:
108: private int computeRelationship(ItemType t1, ItemType t2) {
109: //System.err.println("computeRelationship " + t1 + ", " + t2);
110: if (t1 == t2) {
111: return SAME_TYPE;
112: }
113: if (t1 instanceof AnyItemType) {
114: if (t2 instanceof AnyItemType) {
115: return SAME_TYPE;
116: } else {
117: return SUBSUMES;
118: }
119: } else if (t2 instanceof AnyItemType) {
120: return SUBSUMED_BY;
121: } else if (t1 instanceof AtomicType) {
122: if (t2 instanceof NodeTest) {
123: return DISJOINT;
124: } else {
125: if (((AtomicType) t1).getFingerprint() == ((AtomicType) t2)
126: .getFingerprint()) {
127: return SAME_TYPE;
128: }
129: ItemType t = t2;
130: while (t instanceof AtomicType) {
131: if (((AtomicType) t1).getFingerprint() == ((AtomicType) t)
132: .getFingerprint()) {
133: return SUBSUMES;
134: }
135: t = t.getSuperType(this );
136: }
137: t = t1;
138: while (t instanceof AtomicType) {
139: if (((AtomicType) t).getFingerprint() == ((AtomicType) t2)
140: .getFingerprint()) {
141: return SUBSUMED_BY;
142: }
143: t = t.getSuperType(this );
144: }
145: return DISJOINT;
146: }
147: } else {
148: // t1 is a NodeTest
149: if (t2 instanceof AtomicType) {
150: return DISJOINT;
151: } else {
152: // both types are NodeTests
153: if (t1 instanceof AnyNodeTest) {
154: if (t2 instanceof AnyNodeTest) {
155: return SAME_TYPE;
156: } else {
157: return SUBSUMES;
158: }
159: } else if (t2 instanceof AnyNodeTest) {
160: return SUBSUMED_BY;
161: } else if (t1 instanceof NoNodeTest) {
162: return DISJOINT;
163: } else if (t2 instanceof NoNodeTest) {
164: return DISJOINT;
165: } else {
166: // first find the relationship between the node kinds allowed
167: int nodeKindRelationship;
168: int m1 = ((NodeTest) t1).getNodeKindMask();
169: int m2 = ((NodeTest) t2).getNodeKindMask();
170: if ((m1 & m2) == 0) {
171: return DISJOINT;
172: } else if (m1 == m2) {
173: nodeKindRelationship = SAME_TYPE;
174: } else if ((m1 & m2) == m1) {
175: nodeKindRelationship = SUBSUMED_BY;
176: } else if ((m1 & m2) == m2) {
177: nodeKindRelationship = SUBSUMES;
178: } else {
179: nodeKindRelationship = OVERLAPS;
180: }
181:
182: // now find the relationship between the node names allowed. Note that although
183: // NamespaceTest and LocalNameTest are NodeTests, they do not occur in SequenceTypes,
184: // so we don't need to consider them.
185: int nodeNameRelationship;
186: IntHashSet n1 = ((NodeTest) t1)
187: .getRequiredNodeNames(); // null means all names allowed
188: IntHashSet n2 = ((NodeTest) t2)
189: .getRequiredNodeNames(); // null means all names allowed
190: if (n1 == null) {
191: if (n2 == null) {
192: nodeNameRelationship = SAME_TYPE;
193: } else {
194: nodeNameRelationship = SUBSUMES;
195: }
196: } else if (n2 == null) {
197: nodeNameRelationship = SUBSUMED_BY;
198: } else if (n1.containsAll(n2)) {
199: if (n1.size() == n2.size()) {
200: nodeNameRelationship = SAME_TYPE;
201: } else {
202: nodeNameRelationship = SUBSUMES;
203: }
204: } else if (n2.containsAll(n1)) {
205: nodeNameRelationship = SUBSUMED_BY;
206: } else if (n1.containsSome(n2)) {
207: nodeNameRelationship = OVERLAPS;
208: } else {
209: nodeNameRelationship = DISJOINT;
210: }
211:
212: // now find the relationship between the content types allowed
213:
214: int contentRelationship;
215:
216: if (t1 instanceof DocumentNodeTest) {
217: if (t2 instanceof DocumentNodeTest) {
218: contentRelationship = relationship(
219: ((DocumentNodeTest) t1)
220: .getElementTest(),
221: ((DocumentNodeTest) t2)
222: .getElementTest());
223: } else {
224: contentRelationship = SUBSUMED_BY;
225: }
226: } else if (t2 instanceof DocumentNodeTest) {
227: contentRelationship = SUBSUMES;
228: } else {
229: SchemaType s1 = ((NodeTest) t1)
230: .getContentType();
231: SchemaType s2 = ((NodeTest) t2)
232: .getContentType();
233: contentRelationship = Type
234: .schemaTypeRelationship(s1, s2);
235: }
236:
237: // now analyse the three different relationsships
238:
239: if (nodeKindRelationship == SAME_TYPE
240: && nodeNameRelationship == SAME_TYPE
241: && contentRelationship == SAME_TYPE) {
242: return SAME_TYPE;
243: } else if ((nodeKindRelationship == SAME_TYPE || nodeKindRelationship == SUBSUMES)
244: && (nodeNameRelationship == SAME_TYPE || nodeNameRelationship == SUBSUMES)
245: && (contentRelationship == SAME_TYPE || contentRelationship == SUBSUMES)) {
246: return SUBSUMES;
247: } else if ((nodeKindRelationship == SAME_TYPE || nodeKindRelationship == SUBSUMED_BY)
248: && (nodeNameRelationship == SAME_TYPE || nodeNameRelationship == SUBSUMED_BY)
249: && (contentRelationship == SAME_TYPE || contentRelationship == SUBSUMED_BY)) {
250: return SUBSUMED_BY;
251: } else if (nodeKindRelationship == DISJOINT
252: || nodeNameRelationship == DISJOINT
253: || contentRelationship == DISJOINT) {
254: return DISJOINT;
255: } else {
256: return OVERLAPS;
257: }
258: }
259: }
260: }
261:
262: }
263:
264: // public static void main(String[] args) throws Exception {
265: // int runs = 10000000;
266: // final Configuration config = new Configuration();
267: // final NamePool pool = config.getNamePool();
268: // final StaticQueryContext sqc = new StaticQueryContext(config);
269: // final NodeInfo doc = sqc.buildDocument(new StreamSource(new File("c:/MyJava/samples/data/books.xml")));
270: // final XQueryExpression exp = sqc.compileQuery(
271: // "declare variable $x external; count($x//*)");
272: // for (int i=1; i < runs; i++) {
273: // Configuration config2 = new Configuration();
274: // config2.setNamePool(pool);
275: // final DynamicQueryContext dynamicContext = new DynamicQueryContext(config2);
276: // dynamicContext.setParameter("x", doc);
277: // final Properties props = new Properties();
278: // exp.run(dynamicContext, new Sink(), props);
279: // if (i % 1000 == 0) {
280: // System.out.print(".");
281: // }
282: // if (i % 10000 == 0) {
283: // Runtime.getRuntime().gc();
284: // System.out.println("i=" + i + " free memory = " + Runtime.getRuntime().freeMemory());
285: // }
286: // }
287: // }
288:
289: }
290:
291: //
292: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
293: // you may not use this file except in compliance with the License. You may obtain a copy of the
294: // License at http://www.mozilla.org/MPL/
295: //
296: // Software distributed under the License is distributed on an "AS IS" basis,
297: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
298: // See the License for the specific language governing rights and limitations under the License.
299: //
300: // The Original Code is: all this file.
301: //
302: // The Initial Developer of the Original Code is Michael H. Kay.
303: //
304: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
305: //
306: // Contributor(s): none.
307: //
|