001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one
003     * or more contributor license agreements. See the NOTICE file
004     * distributed with this work for additional information
005     * regarding copyright ownership. The ASF licenses this file
006     * to you under the Apache License, Version 2.0 (the  "License");
007     * you may not use this file except in compliance with the License.
008     * You may obtain a copy of the License at
009     *
010     *     http://www.apache.org/licenses/LICENSE-2.0
011     *
012     * Unless required by applicable law or agreed to in writing, software
013     * distributed under the License is distributed on an "AS IS" BASIS,
014     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015     * See the License for the specific language governing permissions and
016     * limitations under the License.
017     */
018    /*
019     * $Id: VariableStack.java 524812 2007-04-02 15:52:03Z zongaro $
020     */
021    package org.apache.xpath;
022    
023    import javax.xml.transform.TransformerException;
024    
025    import org.apache.xalan.res.XSLMessages;
026    import org.apache.xpath.objects.XObject;
027    import org.apache.xpath.res.XPATHErrorResources;
028    
029    /**
030     * Defines a class to keep track of a stack for
031     * template arguments and variables.
032     *
033     * <p>This has been changed from the previous incarnations of this
034     * class to be fairly low level.</p>
035     * @xsl.usage internal
036     */
037    public class VariableStack implements Cloneable
038    {
039      /**
040       * limitation for 1K
041       */
042      public static final int CLEARLIMITATION= 1024;
043    
044      /**
045       * Constructor for a variable stack.
046       */
047      public VariableStack()
048      {
049        reset();
050      }
051    
052      /**
053       * Constructor for a variable stack.
054       * @param initStackSize The initial stack size.  Must be at least one.  The
055       *                      stack can grow if needed.
056       */
057      public VariableStack(int initStackSize)
058      {
059        // Allow for twice as many variables as stack link entries
060        reset(initStackSize, initStackSize*2);
061      }
062    
063      /**
064       * Returns a clone of this variable stack.
065       *
066       * @return  a clone of this variable stack.
067       *
068       * @throws CloneNotSupportedException
069       */
070      public synchronized Object clone() throws CloneNotSupportedException
071      {
072    
073        VariableStack vs = (VariableStack) super.clone();
074    
075        // I *think* I can get away with a shallow clone here?
076        vs._stackFrames = (XObject[]) _stackFrames.clone();
077        vs._links = (int[]) _links.clone();
078    
079        return vs;
080      }
081    
082      /**
083       * The stack frame where all variables and params will be kept.
084       * @serial
085       */
086      XObject[] _stackFrames;
087    
088      /**
089       * The top of the stack frame (<code>_stackFrames</code>).
090       * @serial
091       */
092      int _frameTop;
093    
094      /**
095       * The bottom index of the current frame (relative to <code>_stackFrames</code>).
096       * @serial
097       */
098      private int _currentFrameBottom;
099    
100      /**
101       * The stack of frame positions.  I call 'em links because of distant
102       * <a href="http://math.millikin.edu/mprogers/Courses/currentCourses/CS481-ComputerArchitecture/cs481.Motorola68000.html">
103       * Motorola 68000 assembler</a> memories.  :-)
104       * @serial
105       */
106      int[] _links;
107    
108      /**
109       * The top of the links stack.
110       */
111      int _linksTop;
112    
113      /**
114       * Get the element at the given index, regardless of stackframe.
115       *
116       * @param i index from zero.
117       *
118       * @return The item at the given index.
119       */
120      public XObject elementAt(final int i)
121      {
122        return _stackFrames[i];
123      }
124    
125      /**
126       * Get size of the stack.
127       *
128       * @return the total size of the execution stack.
129       */
130      public int size()
131      {
132        return _frameTop;
133      }
134    
135      /**
136       * Reset the stack to a start position.
137       */
138      public void reset()
139      {
140        // If the stack was previously allocated, assume that about the same
141        // amount of stack space will be needed again; otherwise, use a very
142        // large stack size.
143        int linksSize = (_links == null) ? XPathContext.RECURSIONLIMIT
144                                         : _links.length;
145        int varArraySize = (_stackFrames == null) ? XPathContext.RECURSIONLIMIT * 2
146                                                  : _stackFrames.length;
147        reset(linksSize, varArraySize);
148      }
149    
150      /**
151       * Reset the stack to a start position.
152       * @param linksSize Initial stack size to use
153       * @param varArraySize Initial variable array size to use
154       */
155      protected void reset(int linksSize, int varArraySize) {
156        _frameTop = 0;
157        _linksTop = 0;
158    
159        // Don't bother reallocating _links array if it exists already
160        if (_links == null) {
161          _links = new int[linksSize];
162        }
163    
164        // Adding one here to the stack of frame positions will allow us always 
165        // to look one under without having to check if we're at zero.
166        // (As long as the caller doesn't screw up link/unlink.)
167        _links[_linksTop++] = 0;
168    
169        // Get a clean _stackFrames array and discard the old one.
170        _stackFrames = new XObject[varArraySize]; 
171      }
172    
173      /**
174       * Set the current stack frame.
175       *
176       * @param sf The new stack frame position.
177       */
178      public void setStackFrame(int sf)
179      {
180        _currentFrameBottom = sf;
181      }
182    
183      /**
184       * Get the position from where the search should start,
185       * which is either the searchStart property, or the top
186       * of the stack if that value is -1.
187       *
188       * @return The current stack frame position.
189       */
190      public int getStackFrame()
191      {
192        return _currentFrameBottom;
193      }
194    
195      /**
196       * Allocates memory (called a stackframe) on the stack; used to store
197       * local variables and parameter arguments.
198       *
199       * <p>I use the link/unlink concept because of distant
200       * <a href="http://math.millikin.edu/mprogers/Courses/currentCourses/CS481-ComputerArchitecture/cs481.Motorola68000.html">
201       * Motorola 68000 assembler</a> memories.</p>
202       *
203       * @param size The size of the stack frame allocation.  This ammount should
204       * normally be the maximum number of variables that you can have allocated
205       * at one time in the new stack frame.
206       *
207       * @return The bottom of the stack frame, from where local variable addressing
208       * should start from.
209       */
210      public int link(final int size)
211      {
212    
213        _currentFrameBottom = _frameTop;
214        _frameTop += size;
215    
216        if (_frameTop >= _stackFrames.length)
217        {
218          XObject newsf[] = new XObject[_stackFrames.length + XPathContext.RECURSIONLIMIT + size];
219    
220          System.arraycopy(_stackFrames, 0, newsf, 0, _stackFrames.length);
221    
222          _stackFrames = newsf;
223        }
224    
225        if (_linksTop + 1 >= _links.length)
226        {
227          int newlinks[] = new int[_links.length + (CLEARLIMITATION * 2)];
228    
229          System.arraycopy(_links, 0, newlinks, 0, _links.length);
230    
231          _links = newlinks;
232        }
233    
234        _links[_linksTop++] = _currentFrameBottom;
235    
236        return _currentFrameBottom;
237      }
238    
239      /**
240       * Free up the stack frame that was last allocated with
241       * {@link #link(int size)}.
242       */
243      public  void unlink()
244      {
245        _frameTop = _links[--_linksTop];
246        _currentFrameBottom = _links[_linksTop - 1];
247      }
248      
249      /**
250       * Free up the stack frame that was last allocated with
251       * {@link #link(int size)}.
252       * @param currentFrame The current frame to set to 
253       * after the unlink.
254       */
255      public  void unlink(int currentFrame)
256      {
257        _frameTop = _links[--_linksTop];
258        _currentFrameBottom = currentFrame; 
259      }
260    
261      /**
262       * Set a local variable or parameter in the current stack frame.
263       *
264       *
265       * @param index Local variable index relative to the current stack
266       * frame bottom.
267       *
268       * @param val The value of the variable that is being set.
269       */
270      public void setLocalVariable(int index, XObject val)
271      {
272        _stackFrames[index + _currentFrameBottom] = val;
273      }
274    
275      /**
276       * Set a local variable or parameter in the specified stack frame.
277       *
278       *
279       * @param index Local variable index relative to the current stack
280       * frame bottom.
281       * NEEDSDOC @param stackFrame
282       *
283       * @param val The value of the variable that is being set.
284       */
285      public void setLocalVariable(int index, XObject val, int stackFrame)
286      {
287        _stackFrames[index + stackFrame] = val;
288      }
289    
290      /**
291       * Get a local variable or parameter in the current stack frame.
292       *
293       *
294       * @param xctxt The XPath context, which must be passed in order to
295       * lazy evaluate variables.
296       *
297       * @param index Local variable index relative to the current stack
298       * frame bottom.
299       *
300       * @return The value of the variable.
301       *
302       * @throws TransformerException
303       */
304      public XObject getLocalVariable(XPathContext xctxt, int index)
305              throws TransformerException
306      {
307    
308        index += _currentFrameBottom;
309    
310        XObject val = _stackFrames[index];
311        
312        if(null == val)
313          throw new TransformerException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_VARIABLE_ACCESSED_BEFORE_BIND, null),
314                         xctxt.getSAXLocator());
315          // "Variable accessed before it is bound!", xctxt.getSAXLocator());
316    
317        // Lazy execution of variables.
318        if (val.getType() == XObject.CLASS_UNRESOLVEDVARIABLE)
319          return (_stackFrames[index] = val.execute(xctxt));
320    
321        return val;
322      }
323    
324      /**
325       * Get a local variable or parameter in the current stack frame.
326       *
327       *
328       * @param index Local variable index relative to the given
329       * frame bottom.
330       * NEEDSDOC @param frame
331       *
332       * @return The value of the variable.
333       *
334       * @throws TransformerException
335       */
336      public XObject getLocalVariable(int index, int frame)
337              throws TransformerException
338      {
339    
340        index += frame;
341    
342        XObject val = _stackFrames[index];
343    
344        return val;
345      }
346      
347      /**
348       * Get a local variable or parameter in the current stack frame.
349       *
350       *
351       * @param xctxt The XPath context, which must be passed in order to
352       * lazy evaluate variables.
353       *
354       * @param index Local variable index relative to the current stack
355       * frame bottom.
356       *
357       * @return The value of the variable.
358       *
359       * @throws TransformerException
360       */
361      public XObject getLocalVariable(XPathContext xctxt, int index, boolean destructiveOK)
362              throws TransformerException
363      {
364    
365        index += _currentFrameBottom;
366    
367        XObject val = _stackFrames[index];
368        
369        if(null == val)
370          throw new TransformerException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_VARIABLE_ACCESSED_BEFORE_BIND, null),
371                         xctxt.getSAXLocator());
372          // "Variable accessed before it is bound!", xctxt.getSAXLocator());
373    
374        // Lazy execution of variables.
375        if (val.getType() == XObject.CLASS_UNRESOLVEDVARIABLE)
376          return (_stackFrames[index] = val.execute(xctxt));
377    
378        return destructiveOK ? val : val.getFresh();
379      }
380    
381      /**
382       * Tell if a local variable has been set or not.
383       *
384       * @param index Local variable index relative to the current stack
385       * frame bottom.
386       *
387       * @return true if the value at the index is not null.
388       *
389       * @throws TransformerException
390       */
391      public boolean isLocalSet(int index) throws TransformerException
392      {
393        return (_stackFrames[index + _currentFrameBottom] != null);
394      }
395    
396      /** NEEDSDOC Field m_nulls          */
397      private static XObject[] m_nulls = new XObject[CLEARLIMITATION];
398    
399      /**
400       * Use this to clear the variables in a section of the stack.  This is
401       * used to clear the parameter section of the stack, so that default param
402       * values can tell if they've already been set.  It is important to note that
403       * this function has a 1K limitation.
404       *
405       * @param start The start position, relative to the current local stack frame.
406       * @param len The number of slots to be cleared.
407       */
408      public void clearLocalSlots(int start, int len)
409      {
410    
411        start += _currentFrameBottom;
412    
413        System.arraycopy(m_nulls, 0, _stackFrames, start, len);
414      }
415    
416      /**
417       * Set a global variable or parameter in the global stack frame.
418       *
419       *
420       * @param index Local variable index relative to the global stack frame
421       * bottom.
422       *
423       * @param val The value of the variable that is being set.
424       */
425      public void setGlobalVariable(final int index, final XObject val)
426      {
427        _stackFrames[index] = val;
428      }
429    
430      /**
431       * Get a global variable or parameter from the global stack frame.
432       *
433       *
434       * @param xctxt The XPath context, which must be passed in order to
435       * lazy evaluate variables.
436       *
437       * @param index Global variable index relative to the global stack
438       * frame bottom.
439       *
440       * @return The value of the variable.
441       *
442       * @throws TransformerException
443       */
444      public XObject getGlobalVariable(XPathContext xctxt, final int index)
445              throws TransformerException
446      {
447    
448        XObject val = _stackFrames[index];
449    
450        // Lazy execution of variables.
451        if (val.getType() == XObject.CLASS_UNRESOLVEDVARIABLE)
452          return (_stackFrames[index] = val.execute(xctxt));
453    
454        return val;
455      }
456      
457      /**
458       * Get a global variable or parameter from the global stack frame.
459       *
460       *
461       * @param xctxt The XPath context, which must be passed in order to
462       * lazy evaluate variables.
463       *
464       * @param index Global variable index relative to the global stack
465       * frame bottom.
466       *
467       * @return The value of the variable.
468       *
469       * @throws TransformerException
470       */
471      public XObject getGlobalVariable(XPathContext xctxt, final int index, boolean destructiveOK)
472              throws TransformerException
473      {
474    
475        XObject val = _stackFrames[index];
476    
477        // Lazy execution of variables.
478        if (val.getType() == XObject.CLASS_UNRESOLVEDVARIABLE)
479          return (_stackFrames[index] = val.execute(xctxt));
480    
481        return destructiveOK ? val : val.getFresh();
482      }
483    
484      /**
485       * Get a variable based on it's qualified name.
486       * This is for external use only.
487       *
488       * @param xctxt The XPath context, which must be passed in order to
489       * lazy evaluate variables.
490       * 
491       * @param qname The qualified name of the variable.
492       *
493       * @return The evaluated value of the variable.
494       *
495       * @throws javax.xml.transform.TransformerException
496       */
497      public XObject getVariableOrParam(
498              XPathContext xctxt, org.apache.xml.utils.QName qname)
499                throws javax.xml.transform.TransformerException
500      {
501    
502        org.apache.xml.utils.PrefixResolver prefixResolver =
503          xctxt.getNamespaceContext();
504    
505        // Get the current ElemTemplateElement, which must be pushed in as the 
506        // prefix resolver, and then walk backwards in document order, searching 
507        // for an xsl:param element or xsl:variable element that matches our 
508        // qname.  If we reach the top level, use the StylesheetRoot's composed
509        // list of top level variables and parameters.
510    
511        if (prefixResolver instanceof org.apache.xalan.templates.ElemTemplateElement)
512        {
513          
514          org.apache.xalan.templates.ElemVariable vvar;
515    
516          org.apache.xalan.templates.ElemTemplateElement prev =
517            (org.apache.xalan.templates.ElemTemplateElement) prefixResolver;
518    
519          if (!(prev instanceof org.apache.xalan.templates.Stylesheet))
520          {
521            while ( !(prev.getParentNode() instanceof org.apache.xalan.templates.Stylesheet) )
522            {
523              org.apache.xalan.templates.ElemTemplateElement savedprev = prev;
524    
525              while (null != (prev = prev.getPreviousSiblingElem()))
526              {
527                if (prev instanceof org.apache.xalan.templates.ElemVariable)
528                {
529                  vvar = (org.apache.xalan.templates.ElemVariable) prev;
530    
531                  if (vvar.getName().equals(qname))
532                    return getLocalVariable(xctxt, vvar.getIndex());
533                }
534              }
535              prev = savedprev.getParentElem();
536            }
537          }
538    
539          vvar = prev.getStylesheetRoot().getVariableOrParamComposed(qname);
540          if (null != vvar)
541            return getGlobalVariable(xctxt, vvar.getIndex());
542        }
543    
544        throw new javax.xml.transform.TransformerException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_VAR_NOT_RESOLVABLE, new Object[]{qname.toString()})); //"Variable not resolvable: " + qname);
545      }
546    }  // end VariableStack
547