NodeTree


1   // Copyright (c) 2003, 2006  Per M.A. Bothner.
2   // This is free software;  for terms and warranty disclaimer see ./COPYING.
3   
4   package gnu.xml;
5   import gnu.lists.*;
6   import gnu.mapping.*;
7   import gnu.text.URI_utils;
8   import gnu.kawa.xml.KNode;
9   import gnu.xml.XName;
10  import gnu.kawa.xml.UntypedAtomic;  // FIXME - bad cross-package dependency.
11  import gnu.kawa.xml.ElementType; // FIXME - bad cross-package dependency.
12  
13  /** Use to represent a Document or Document Fragment, in the XML DOM sense.
14   * More compact than traditional DOM, since it uses many fewer objects.
15   */
16  
17  public class NodeTree extends TreeList
18  {
19    public int nextPos (int position)
20    {
21      boolean isAfter = (position & 1) != 0;
22      int index = posToDataIndex(position);
23      int next = nextNodeIndex(index, -1 >>> 1);
24      if (next != index)
25        return next << 1;
26      if (index == data.length)
27        return 0;
28      return (index << 1) + 3;
29    }
30  
31    public static NodeTree make ()
32    {
33      return new NodeTree();
34    }
35  
36    static int counter;
37    int id;
38  
39    /** Get/create a new unique number. */
40    public int getId()
41    {
42      if (id == 0)
43        id = ++counter;
44      return id;
45    }
46  
47    public int stableCompare (AbstractSequence other)
48    {
49      if (this == other)
50        return 0;
51      // If other is also a NodeTree it would be simpler to just compare
52      // the results of getId, but if we always did that there is the
53      // slight risk that counter could overflow in the case of a
54      // long-running program.  So we use system.identityHashCode as
55      // the primary "key" and getId only when needed as a tie-breaker.
56      int comp = super.stableCompare(other);
57      if (comp == 0 && other instanceof NodeTree)
58        {
59      int id1 = this.getId();
60      int id2 = ((NodeTree) other).getId();
61      comp = id1 < id2 ? -1 : id1 > id2 ? 1 : 0;
62        }
63      return comp;
64    }
65  
66    public SeqPosition getIteratorAtPos(int ipos)
67    {
68      return KNode.make(this, ipos);
69    }
70  
71    public String   posNamespaceURI (int ipos)
72    {
73      Object   type = getNextTypeObject(ipos);
74      if (type instanceof XName)
75        return ((XName) type).getNamespaceURI();
76      if (type instanceof Symbol)
77        return ((Symbol) type).getNamespaceURI();
78      return null;
79    }
80  
81    public String   posPrefix (int ipos)
82    {
83      String   name = getNextTypeName(ipos);
84      if (name == null)
85        return null;
86      int colon = name.indexOf(':');
87      return colon < 0 ? null : name.substring(0, colon);
88    }
89  
90    public String   posLocalName (int ipos)
91    {
92      Object   type = getNextTypeObject(ipos);
93      if (type instanceof XName)
94        return ((XName) type).getLocalPart();
95      if (type instanceof Symbol)
96        return ((Symbol) type).getLocalName();
97      return getNextTypeName(ipos);
98    }
99  
100   public boolean posIsDefaultNamespace (int ipos, String   namespaceURI)
101   {
102     throw new Error  ("posIsDefaultNamespace not implemented");
103   }
104 
105   public String   posLookupNamespaceURI (int ipos, String   prefix)
106   {
107     int kind = getNextKind(ipos);
108     if (kind != Sequence.GROUP_VALUE)
109       throw new IllegalArgumentException  ("argument must be an element");
110     Object   type = getNextTypeObject(ipos);
111     if (type instanceof XName)
112       return ((XName) type).lookupNamespaceURI(prefix);
113     else
114       return null;
115   }
116 
117   public String   posLookupPrefix (int ipos, String   namespaceURI)
118   {
119     throw new Error  ("posLookupPrefix not implemented");
120   }
121 
122   public int posFirstChild(int ipos)
123   {
124     int index = gotoChildrenStart(posToDataIndex(ipos));
125     if (index < 0)
126       return -1;
127     char datum = data[index];
128     if (datum == END_GROUP_SHORT || datum == END_GROUP_LONG
129     || datum == END_DOCUMENT)
130       return -1;
131     return index << 1;
132   }
133 
134   public boolean posHasAttributes (int ipos)
135   {
136     int index = gotoAttributesStart(posToDataIndex(ipos));
137     if (index < 0)
138       return false;
139     return index >= 0 && data[index] == BEGIN_ATTRIBUTE_LONG;
140   }
141 
142   /** Find named attribute.
143    * @param namespaceURI need not be interned,
144    *   or null which matches any namespace
145    * @param localName need not be interned,
146    *   or null which matches any local name
147    * @return attribute ipos or 0
148    */
149   public int getAttribute (int parent, String   namespaceURI, String   localName)
150   {
151     return getAttributeI(parent,
152                          namespaceURI == null ? null : namespaceURI.intern(),
153                          localName == null ? null : localName.intern());
154   }
155 
156   /** Find named attribute.
157    * @param namespaceURI an interned String or null which matches any namespace
158    * @param localName an interned String, or null which matches any local name
159    * @return attribute ipos or 0
160    */
161   public int getAttributeI (int parent, String   namespaceURI, String   localName)
162   {
163     int attr = firstAttributePos(parent);
164     for (;;)
165       {
166         if (attr == 0 || getNextKind(attr) != Sequence.ATTRIBUTE_VALUE)
167           return 0;
168         if ((localName == null || posLocalName(attr) == localName)
169             && (namespaceURI == null || posNamespaceURI(attr) == namespaceURI))
170           return attr;
171         attr = nextPos(attr);
172       }
173   }
174 
175   /** Return the type-value of the node at the specified position. */
176   public Object   typedValue (int ipos)
177   {
178     // FIXME when we support validation.
179     StringBuffer   sbuf = new StringBuffer  ();
180     stringValue(posToDataIndex(ipos), sbuf);
181     String   str = sbuf.toString();
182     int kind = getNextKind(ipos);
183     if (kind == Sequence.PROCESSING_INSTRUCTION_VALUE
184         || kind == Sequence.COMMENT_VALUE)
185       return str;
186     return new UntypedAtomic(str);
187   }
188 
189   /** Get the target of a process-instruction. */
190   public String   posTarget (int ipos)
191   {
192     int index = posToDataIndex(ipos);
193     if (data[index] != PROCESSING_INSTRUCTION)
194       throw new ClassCastException  ("expected process-instruction");
195     return (String  ) objects[getIntN(index+1)];
196   }
197 
198   /** Look for matching attribute in ancestor or self.
199    * @param namespace namespaceURI (interned) of required attribute
200    * @param name localName(interned) of required attribute 
201    * @return attribute ipos or 0
202    */
203   public int ancestorAttribute (int ipos,
204                                 String   namespace, String   name)
205   {
206     for (;;)
207       {
208         if (ipos == -1)
209           return 0;
210         int attr = getAttributeI(ipos, namespace, name);
211         if (attr != 0)
212           return attr;
213         ipos = parentPos(ipos);
214       }
215   }
216 
217   /** Return of the base-uri property, if known, of the node at pos. */
218   public Object   baseUriOfPos (int pos, boolean resolveRelative)
219   {
220     Object   base = null;
221     int index = posToDataIndex(pos);
222     for (;;)
223       {
224     if (index == data.length)
225       return null;
226     char datum = data[index];
227         Object   uri = null;
228         if (datum == BEGIN_ENTITY)
229           {
230             int oindex = getIntN(index+1);
231             if (oindex >= 0)
232               uri = objects[oindex];
233           }
234     else if ((datum >= BEGIN_GROUP_SHORT
235          && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
236         || datum == BEGIN_GROUP_LONG)
237           {
238             int attr = getAttributeI(pos, NamespaceBinding.XML_NAMESPACE, "base");
239             if (attr != 0)
240               uri = KNode.getNodeValue(this, attr);
241           }
242         if (uri != null)
243           {
244             try
245               {
246                 base = base == null || ! resolveRelative ? uri
247                   : URI_utils.resolve(base, uri);
248               }
249             catch (java.net.URISyntaxException   ex)
250               {
251                 // Or maybe return null;
252                 throw new WrappedException(ex);
253               }
254             if (URI_utils.isAbsolute(base) || ! resolveRelative)
255               return base;
256           }
257     index = parentOrEntityI(index);
258     if (index == -1)
259           return base;
260         pos = index << 1;
261       }
262   }
263 
264   public String   toString ()
265   {
266     CharArrayOutPort wr = new CharArrayOutPort();
267     XMLPrinter xp = new XMLPrinter(wr);
268     consume(xp);
269     wr.close();
270     return wr.toString();
271   }
272 
273   /** If non-null, a hash-table of ID names. */
274   String  [] idNames;
275   /** If non-null, a mapping of element ipos values mapped by idNames.
276    * If {@code idNames[i]} is non-null, then {@code idOffsets[i]} is the
277    * ipos value of the first element that has the former as its ID property. */
278   int[] idOffsets;
279   /** Number of non-null entries in idNames. */
280   int idCount;
281 
282   public void makeIDtableIfNeeded ()
283   {
284     if (idNames != null)
285       return;
286     // Force allocation - in case there are no xml:id nodes,
287     // so we don't scan multiple times.
288     int size = 64;
289     idNames = new String  [size];
290     idOffsets = new int[size];
291     int limit = endPos();
292     int ipos = 0;
293     for (;;)
294       {
295     ipos = nextMatching(ipos, ElementType.anyElement, limit, true);
296     if (ipos == 0)
297       break;
298         // Until we do validation, we only recognize 'xml:id' as setting
299         // the is-id property.  FIXME.
300         int attr = getAttributeI(ipos, NamespaceBinding.XML_NAMESPACE, "id");
301         if (attr != 0)
302           {
303             enterID(KNode.getNodeValue(this, attr), ipos);
304           }
305       }
306   }
307 
308   void enterID (String   name, int offset)
309   {
310     int size;
311     String  [] tmpNames = idNames;
312     int[] tmpOffsets = idOffsets;
313     if (tmpNames == null)
314       {
315         size = 64;
316         idNames = new String  [size];
317         idOffsets = new int[size];
318       }
319     else if (4 * idCount >= 3 * (size = idNames.length))
320       {
321         idNames = new String  [2 * size];
322         idOffsets = new int[2 * size];
323         idCount = 0;
324         for (int i = size;  --i >= 0; )
325           {
326             String   oldName = tmpNames[i];
327             if (oldName != null)
328               enterID(oldName, tmpOffsets[i]);
329           }
330         tmpNames = idNames;
331         tmpOffsets = idOffsets;
332         size = 2 * size;
333       }
334     int hash = name.hashCode();
335     int mask = size - 1;
336     int index = hash & mask;
337     // Must be odd - or more specifically relatively prime with size,
338     int step = (~hash << 1) | 1;
339     for (;;)
340       {
341         String   oldName = tmpNames[index];
342         if (oldName == null)
343           {
344             tmpNames[index] = name;
345             tmpOffsets[index] = offset;
346             break;
347           }
348         if (oldName.equals(name)) // intern and == ?? FIXME
349           {
350             // Nothing to do.
351             return;
352           }
353         index = (index + step) & mask;
354       }
355     idCount++;
356   }
357 
358   /** Look for an element with matching ID.
359    * Returns an element ipos, or -1 if not found.
360    * Since we don't do any validation, for now only attributes with the
361    * name {@code xml:id} are recognized has having the {@code is-id} property.
362    * Assumes makeIDtableIfNeeded has been called at soem point.
363    */
364   public int lookupID (String   name)
365   {
366     String  [] tmpNames = idNames;
367     int[] tmpOffsets = idOffsets;
368     int size = idNames.length;
369     int hash = name.hashCode();
370     int mask = size - 1;
371     int index = hash & mask;
372     // Must be odd - or more specifically relatively prime with size,
373     int step = (~hash << 1) | 1;
374     for (;;)
375       {
376         String   oldName = tmpNames[index];
377         if (oldName == null)
378           return -1;
379         if (oldName.equals(name)) // intern and == ?? FIXME
380           {
381             return tmpOffsets[index];
382           }
383         index = (index + step) & mask;
384       }
385   }
386 }
387
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags