001: // Copyright (c) 2003, 2006 Per M.A. Bothner.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.xml;
005:
006: import gnu.lists.*;
007: import gnu.mapping.*;
008: import gnu.text.*;
009: import gnu.kawa.xml.KNode;
010: import gnu.xml.XName;
011: import gnu.kawa.xml.UntypedAtomic; // FIXME - bad cross-package dependency.
012: import gnu.kawa.xml.ElementType; // FIXME - bad cross-package dependency.
013:
014: /** Use to represent a Document or Document Fragment, in the XML DOM sense.
015: * More compact than traditional DOM, since it uses many fewer objects.
016: */
017:
018: public class NodeTree extends TreeList {
019: public int nextPos(int position) {
020: boolean isAfter = (position & 1) != 0;
021: int index = posToDataIndex(position);
022: int next = nextNodeIndex(index, -1 >>> 1);
023: if (next != index)
024: return next << 1;
025: if (index == data.length)
026: return 0;
027: return (index << 1) + 3;
028: }
029:
030: public static NodeTree make() {
031: return new NodeTree();
032: }
033:
034: static int counter;
035: int id;
036:
037: /** Get/create a new unique number. */
038: public int getId() {
039: if (id == 0)
040: id = ++counter;
041: return id;
042: }
043:
044: public int stableCompare(AbstractSequence other) {
045: if (this == other)
046: return 0;
047: // If other is also a NodeTree it would be simpler to just compare
048: // the results of getId, but if we always did that there is the
049: // slight risk that counter could overflow in the case of a
050: // long-running program. So we use system.identityHashCode as
051: // the primary "key" and getId only when needed as a tie-breaker.
052: int comp = super .stableCompare(other);
053: if (comp == 0 && other instanceof NodeTree) {
054: int id1 = this .getId();
055: int id2 = ((NodeTree) other).getId();
056: comp = id1 < id2 ? -1 : id1 > id2 ? 1 : 0;
057: }
058: return comp;
059: }
060:
061: public SeqPosition getIteratorAtPos(int ipos) {
062: return KNode.make(this , ipos);
063: }
064:
065: public String posNamespaceURI(int ipos) {
066: Object type = getNextTypeObject(ipos);
067: if (type instanceof XName)
068: return ((XName) type).getNamespaceURI();
069: if (type instanceof Symbol)
070: return ((Symbol) type).getNamespaceURI();
071: return null;
072: }
073:
074: public String posPrefix(int ipos) {
075: String name = getNextTypeName(ipos);
076: if (name == null)
077: return null;
078: int colon = name.indexOf(':');
079: return colon < 0 ? null : name.substring(0, colon);
080: }
081:
082: public String posLocalName(int ipos) {
083: Object type = getNextTypeObject(ipos);
084: if (type instanceof XName)
085: return ((XName) type).getLocalPart();
086: if (type instanceof Symbol)
087: return ((Symbol) type).getLocalName();
088: return getNextTypeName(ipos);
089: }
090:
091: public boolean posIsDefaultNamespace(int ipos, String namespaceURI) {
092: throw new Error("posIsDefaultNamespace not implemented");
093: }
094:
095: public String posLookupNamespaceURI(int ipos, String prefix) {
096: int kind = getNextKind(ipos);
097: if (kind != Sequence.ELEMENT_VALUE)
098: throw new IllegalArgumentException(
099: "argument must be an element");
100: Object type = getNextTypeObject(ipos);
101: if (type instanceof XName)
102: return ((XName) type).lookupNamespaceURI(prefix);
103: else
104: return null;
105: }
106:
107: public String posLookupPrefix(int ipos, String namespaceURI) {
108: throw new Error("posLookupPrefix not implemented");
109: }
110:
111: public int posFirstChild(int ipos) {
112: int index = gotoChildrenStart(posToDataIndex(ipos));
113: if (index < 0)
114: return -1;
115: char datum = data[index];
116: if (datum == END_ELEMENT_SHORT || datum == END_ELEMENT_LONG
117: || datum == END_DOCUMENT)
118: return -1;
119: return index << 1;
120: }
121:
122: public boolean posHasAttributes(int ipos) {
123: int index = gotoAttributesStart(posToDataIndex(ipos));
124: if (index < 0)
125: return false;
126: return index >= 0 && data[index] == BEGIN_ATTRIBUTE_LONG;
127: }
128:
129: /** Find named attribute.
130: * @param namespaceURI need not be interned,
131: * or null which matches any namespace
132: * @param localName need not be interned,
133: * or null which matches any local name
134: * @return attribute ipos or 0
135: */
136: public int getAttribute(int parent, String namespaceURI,
137: String localName) {
138: return getAttributeI(parent, namespaceURI == null ? null
139: : namespaceURI.intern(), localName == null ? null
140: : localName.intern());
141: }
142:
143: /** Find named attribute.
144: * @param namespaceURI an interned String or null which matches any namespace
145: * @param localName an interned String, or null which matches any local name
146: * @return attribute ipos or 0
147: */
148: public int getAttributeI(int parent, String namespaceURI,
149: String localName) {
150: int attr = firstAttributePos(parent);
151: for (;;) {
152: if (attr == 0
153: || getNextKind(attr) != Sequence.ATTRIBUTE_VALUE)
154: return 0;
155: if ((localName == null || posLocalName(attr) == localName)
156: && (namespaceURI == null || posNamespaceURI(attr) == namespaceURI))
157: return attr;
158: attr = nextPos(attr);
159: }
160: }
161:
162: /** Return the type-value of the node at the specified position. */
163: public Object typedValue(int ipos) {
164: // FIXME when we support validation.
165: StringBuffer sbuf = new StringBuffer();
166: stringValue(posToDataIndex(ipos), sbuf);
167: String str = sbuf.toString();
168: int kind = getNextKind(ipos);
169: if (kind == Sequence.PROCESSING_INSTRUCTION_VALUE
170: || kind == Sequence.COMMENT_VALUE)
171: return str;
172: return new UntypedAtomic(str);
173: }
174:
175: /** Get the target of a process-instruction. */
176: public String posTarget(int ipos) {
177: int index = posToDataIndex(ipos);
178: if (data[index] != PROCESSING_INSTRUCTION)
179: throw new ClassCastException("expected process-instruction");
180: return (String) objects[getIntN(index + 1)];
181: }
182:
183: /** Look for matching attribute in ancestor or self.
184: * @param namespace namespaceURI (interned) of required attribute
185: * @param name localName(interned) of required attribute
186: * @return attribute ipos or 0
187: */
188: public int ancestorAttribute(int ipos, String namespace, String name) {
189: for (;;) {
190: if (ipos == -1)
191: return 0;
192: int attr = getAttributeI(ipos, namespace, name);
193: if (attr != 0)
194: return attr;
195: ipos = parentPos(ipos);
196: }
197: }
198:
199: /** Return of the base-uri property, if known, of the node at pos. */
200: public Path baseUriOfPos(int pos, boolean resolveRelative) {
201: Path uri = null;
202: int index = posToDataIndex(pos);
203: for (;;) {
204: if (index == data.length)
205: return null;
206: char datum = data[index];
207: Path base = null;
208: if (datum == BEGIN_ENTITY) {
209: int oindex = getIntN(index + 1);
210: if (oindex >= 0)
211: base = URIPath.makeURI(objects[oindex]);
212: } else if ((datum >= BEGIN_ELEMENT_SHORT && datum <= BEGIN_ELEMENT_SHORT
213: + BEGIN_ELEMENT_SHORT_INDEX_MAX)
214: || datum == BEGIN_ELEMENT_LONG) {
215: int attr = getAttributeI(pos,
216: NamespaceBinding.XML_NAMESPACE, "base");
217: if (attr != 0)
218: base = URIPath.valueOf(KNode.getNodeValue(this ,
219: attr));
220: }
221: if (base != null) {
222: uri = uri == null || !resolveRelative ? base : base
223: .resolve(uri);
224: if (uri.isAbsolute() || !resolveRelative)
225: return uri;
226: }
227: index = parentOrEntityI(index);
228: if (index == -1)
229: return uri;
230: pos = index << 1;
231: }
232: }
233:
234: public String toString() {
235: CharArrayOutPort wr = new CharArrayOutPort();
236: XMLPrinter xp = new XMLPrinter(wr);
237: consume(xp);
238: wr.close();
239: return wr.toString();
240: }
241:
242: /** If non-null, a hash-table of ID names. */
243: String[] idNames;
244: /** If non-null, a mapping of element ipos values mapped by idNames.
245: * If {@code idNames[i]} is non-null, then {@code idOffsets[i]} is the
246: * ipos value of the first element that has the former as its ID property. */
247: int[] idOffsets;
248: /** Number of non-null entries in idNames. */
249: int idCount;
250:
251: public void makeIDtableIfNeeded() {
252: if (idNames != null)
253: return;
254: // Force allocation - in case there are no xml:id nodes,
255: // so we don't scan multiple times.
256: int size = 64;
257: idNames = new String[size];
258: idOffsets = new int[size];
259: int limit = endPos();
260: int ipos = 0;
261: for (;;) {
262: ipos = nextMatching(ipos, ElementType.anyElement, limit,
263: true);
264: if (ipos == 0)
265: break;
266: // Until we do validation, we only recognize 'xml:id' as setting
267: // the is-id property. FIXME.
268: int attr = getAttributeI(ipos,
269: NamespaceBinding.XML_NAMESPACE, "id");
270: if (attr != 0) {
271: enterID(KNode.getNodeValue(this , attr), ipos);
272: }
273: }
274: }
275:
276: void enterID(String name, int offset) {
277: int size;
278: String[] tmpNames = idNames;
279: int[] tmpOffsets = idOffsets;
280: if (tmpNames == null) {
281: size = 64;
282: idNames = new String[size];
283: idOffsets = new int[size];
284: } else if (4 * idCount >= 3 * (size = idNames.length)) {
285: idNames = new String[2 * size];
286: idOffsets = new int[2 * size];
287: idCount = 0;
288: for (int i = size; --i >= 0;) {
289: String oldName = tmpNames[i];
290: if (oldName != null)
291: enterID(oldName, tmpOffsets[i]);
292: }
293: tmpNames = idNames;
294: tmpOffsets = idOffsets;
295: size = 2 * size;
296: }
297: int hash = name.hashCode();
298: int mask = size - 1;
299: int index = hash & mask;
300: // Must be odd - or more specifically relatively prime with size,
301: int step = (~hash << 1) | 1;
302: for (;;) {
303: String oldName = tmpNames[index];
304: if (oldName == null) {
305: tmpNames[index] = name;
306: tmpOffsets[index] = offset;
307: break;
308: }
309: if (oldName.equals(name)) // intern and == ?? FIXME
310: {
311: // Nothing to do.
312: return;
313: }
314: index = (index + step) & mask;
315: }
316: idCount++;
317: }
318:
319: /** Look for an element with matching ID.
320: * Returns an element ipos, or -1 if not found.
321: * Since we don't do any validation, for now only attributes with the
322: * name {@code xml:id} are recognized has having the {@code is-id} property.
323: * Assumes makeIDtableIfNeeded has been called at soem point.
324: */
325: public int lookupID(String name) {
326: String[] tmpNames = idNames;
327: int[] tmpOffsets = idOffsets;
328: int size = idNames.length;
329: int hash = name.hashCode();
330: int mask = size - 1;
331: int index = hash & mask;
332: // Must be odd - or more specifically relatively prime with size,
333: int step = (~hash << 1) | 1;
334: for (;;) {
335: String oldName = tmpNames[index];
336: if (oldName == null)
337: return -1;
338: if (oldName.equals(name)) // intern and == ?? FIXME
339: {
340: return tmpOffsets[index];
341: }
342: index = (index + step) & mask;
343: }
344: }
345: }
|