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: TemplateList.java 468643 2006-10-28 06:56:03Z minchau $
020     */
021    package org.apache.xalan.templates;
022    
023    import java.util.Enumeration;
024    import java.util.Hashtable;
025    import java.util.Vector;
026    
027    import javax.xml.transform.TransformerException;
028    
029    import org.apache.xalan.res.XSLTErrorResources;
030    import org.apache.xml.dtm.DTM;
031    import org.apache.xml.utils.QName;
032    import org.apache.xpath.Expression;
033    import org.apache.xpath.XPath;
034    import org.apache.xpath.XPathContext;
035    import org.apache.xpath.compiler.PsuedoNames;
036    import org.apache.xpath.patterns.NodeTest;
037    import org.apache.xpath.patterns.StepPattern;
038    import org.apache.xpath.patterns.UnionPattern;
039    
040    /**
041     * Encapsulates a template list, and helps locate individual templates.
042     * @xsl.usage advanced
043     */
044    public class TemplateList implements java.io.Serializable
045    {
046        static final long serialVersionUID = 5803675288911728791L;
047    
048      /**
049       * Construct a TemplateList object. Needs to be public so it can
050       * be invoked from the CompilingStylesheetHandler.
051       */
052      public TemplateList()
053      {
054        super();
055      }
056    
057      /**
058       * Add a template to the table of named templates and/or the table of templates
059       * with match patterns.  This routine should
060       * be called in decreasing order of precedence but it checks nonetheless.
061       *
062       * @param template
063       */
064      public void setTemplate(ElemTemplate template)
065      {
066        XPath matchXPath = template.getMatch();
067        
068        if (null == template.getName() && null == matchXPath)
069        {  
070          template.error(XSLTErrorResources.ER_NEED_NAME_OR_MATCH_ATTRIB,
071              new Object[]{ "xsl:template" });
072        }
073        
074        if (null != template.getName())
075        {
076          ElemTemplate existingTemplate = (ElemTemplate) m_namedTemplates.get(template.getName());
077          if (null == existingTemplate)
078          {
079            m_namedTemplates.put(template.getName(), template);
080          }
081          else
082          {
083            int existingPrecedence =
084                            existingTemplate.getStylesheetComposed().getImportCountComposed();
085            int newPrecedence = template.getStylesheetComposed().getImportCountComposed();
086            if (newPrecedence > existingPrecedence)
087            {
088              // This should never happen
089              m_namedTemplates.put(template.getName(), template);
090            }
091            else if (newPrecedence == existingPrecedence)
092              template.error(XSLTErrorResources.ER_DUPLICATE_NAMED_TEMPLATE,
093                           new Object[]{ template.getName() });
094          }
095        }
096    
097        
098    
099        if (null != matchXPath)
100        {
101          Expression matchExpr = matchXPath.getExpression();
102    
103          if (matchExpr instanceof StepPattern)
104          {
105            insertPatternInTable((StepPattern) matchExpr, template);
106          }
107          else if (matchExpr instanceof UnionPattern)
108          {
109            UnionPattern upat = (UnionPattern) matchExpr;
110            StepPattern[] pats = upat.getPatterns();
111            int n = pats.length;
112    
113            for (int i = 0; i < n; i++)
114            {
115              insertPatternInTable(pats[i], template);
116            }
117          }
118          else
119          {
120    
121            // TODO: assert error
122          }
123        }
124      }
125    
126      /** Flag to indicate whether in DEBUG mode          */
127      final static boolean DEBUG = false;
128    
129      /**
130       * Dump all patterns and elements that match those patterns
131       *
132       */
133      void dumpAssociationTables()
134      {
135    
136        Enumeration associations = m_patternTable.elements();
137    
138        while (associations.hasMoreElements())
139        {
140          TemplateSubPatternAssociation head =
141            (TemplateSubPatternAssociation) associations.nextElement();
142    
143          while (null != head)
144          {
145            System.out.print("(" + head.getTargetString() + ", "
146                             + head.getPattern() + ")");
147    
148            head = head.getNext();
149          }
150    
151          System.out.println("\n.....");
152        }
153    
154        TemplateSubPatternAssociation head = m_wildCardPatterns;
155    
156        System.out.print("wild card list: ");
157    
158        while (null != head)
159        {
160          System.out.print("(" + head.getTargetString() + ", "
161                           + head.getPattern() + ")");
162    
163          head = head.getNext();
164        }
165    
166        System.out.println("\n.....");
167      }
168    
169      /**
170       * After all templates have been added, this function
171       * should be called.
172       */
173      public void compose(StylesheetRoot sroot)
174      {
175    
176        if (DEBUG)
177        {
178          System.out.println("Before wildcard insert...");
179          dumpAssociationTables();
180        }
181    
182        if (null != m_wildCardPatterns)
183        {
184          Enumeration associations = m_patternTable.elements();
185    
186          while (associations.hasMoreElements())
187          {
188            TemplateSubPatternAssociation head =
189              (TemplateSubPatternAssociation) associations.nextElement();
190            TemplateSubPatternAssociation wild = m_wildCardPatterns;
191    
192            while (null != wild)
193            {
194              try
195              {
196                head = insertAssociationIntoList(
197                  head, (TemplateSubPatternAssociation) wild.clone(), true);
198              }
199              catch (CloneNotSupportedException cnse){}
200    
201              wild = wild.getNext();
202            }
203          }
204        }
205    
206        if (DEBUG)
207        {
208          System.out.println("After wildcard insert...");
209          dumpAssociationTables();
210        }
211      }
212    
213      /**
214       * Insert the given TemplateSubPatternAssociation into the the linked
215       * list.  Sort by import precedence, then priority, then by document order.
216       *
217       * @param head The first TemplateSubPatternAssociation in the linked list.
218       * @param item The item that we want to insert into the proper place.
219       * @param isWildCardInsert <code>true</code> if we are inserting a wild card 
220       *             template onto this list.
221       * @return the new head of the list.
222       */
223      private TemplateSubPatternAssociation
224                  insertAssociationIntoList(TemplateSubPatternAssociation head,
225                                             TemplateSubPatternAssociation item,
226                                             boolean isWildCardInsert)
227      {
228    
229        // Sort first by import level (higher level is at front),
230        // then by priority (highest priority is at front),
231        // then by document order (later in document is at front).
232    
233        double priority = getPriorityOrScore(item);
234        double workPriority;
235        int importLevel = item.getImportLevel();
236        int docOrder = item.getDocOrderPos();
237        TemplateSubPatternAssociation insertPoint = head;
238        TemplateSubPatternAssociation next;
239        boolean insertBefore;         // true means insert before insertPoint; otherwise after
240                                      // This can only be true if insertPoint is pointing to
241                                      // the first or last template.
242    
243        // Spin down so that insertPoint points to:
244        // (a) the template immediately _before_ the first template on the chain with
245        // a precedence that is either (i) less than ours or (ii) the same as ours but
246        // the template document position is less than ours
247        // -or-
248        // (b) the last template on the chain if no such template described in (a) exists.
249        // If we are pointing to the first template or the last template (that is, case b),
250        // we need to determine whether to insert before or after the template.  Otherwise,
251        // we always insert after the insertPoint.
252    
253        while (true)
254        {
255          next = insertPoint.getNext();
256          if (null == next)
257            break;
258          else
259          {
260            workPriority = getPriorityOrScore(next);
261            if (importLevel > next.getImportLevel())
262              break;
263            else if (importLevel < next.getImportLevel())
264              insertPoint = next;
265            else if (priority > workPriority)               // import precedence is equal
266              break;
267            else if (priority < workPriority)
268              insertPoint = next;
269            else if (docOrder >= next.getDocOrderPos())     // priorities, import are equal
270              break;
271            else
272              insertPoint = next;
273          }
274        }
275    
276        if ( (null == next) || (insertPoint == head) )      // insert point is first or last
277        {
278          workPriority = getPriorityOrScore(insertPoint);
279          if (importLevel > insertPoint.getImportLevel())
280            insertBefore = true;
281          else if (importLevel < insertPoint.getImportLevel())
282            insertBefore = false;
283          else if (priority > workPriority)
284            insertBefore = true;
285          else if (priority < workPriority)
286            insertBefore = false;
287          else if (docOrder >= insertPoint.getDocOrderPos())
288            insertBefore = true;
289          else
290            insertBefore = false;
291        }
292        else
293          insertBefore = false;
294    
295        // System.out.println("appending: "+target+" to "+matchPat.getPattern());
296        
297        if (isWildCardInsert)
298        {
299          if (insertBefore)
300          {
301            item.setNext(insertPoint);
302    
303            String key = insertPoint.getTargetString();
304    
305            item.setTargetString(key);
306            putHead(key, item);
307            return item;
308          }
309          else
310          {
311            item.setNext(next);
312            insertPoint.setNext(item);
313            return head;
314          }
315        }
316        else
317        {
318          if (insertBefore)
319          {
320            item.setNext(insertPoint);
321    
322            if (insertPoint.isWild() || item.isWild())
323              m_wildCardPatterns = item;
324            else
325              putHead(item.getTargetString(), item);
326            return item;
327          }
328          else
329          {
330            item.setNext(next);
331            insertPoint.setNext(item);
332            return head;
333          }
334        }
335      }
336    
337      /**
338       * Add a template to the template list.
339       *
340       * @param pattern
341       * @param template
342       */
343      private void insertPatternInTable(StepPattern pattern, ElemTemplate template)
344      {
345    
346        String target = pattern.getTargetString();
347    
348        if (null != target)
349        {
350          String pstring = template.getMatch().getPatternString();
351          TemplateSubPatternAssociation association =
352            new TemplateSubPatternAssociation(template, pattern, pstring);
353    
354          // See if there's already one there
355          boolean isWildCard = association.isWild();
356          TemplateSubPatternAssociation head = isWildCard
357                                               ? m_wildCardPatterns
358                                               : getHead(target);
359    
360          if (null == head)
361          {
362            if (isWildCard)
363              m_wildCardPatterns = association;
364            else
365              putHead(target, association);
366          }
367          else
368          {
369            insertAssociationIntoList(head, association, false);
370          }
371        }
372      }
373    
374      /**
375       * Given a match pattern and template association, return the 
376       * score of that match.  This score or priority can always be 
377       * statically calculated.
378       *
379       * @param matchPat The match pattern to template association.
380       *
381       * @return {@link org.apache.xpath.patterns.NodeTest#SCORE_NODETEST}, 
382       *         {@link org.apache.xpath.patterns.NodeTest#SCORE_NONE}, 
383       *         {@link org.apache.xpath.patterns.NodeTest#SCORE_NSWILD}, 
384       *         {@link org.apache.xpath.patterns.NodeTest#SCORE_QNAME}, or
385       *         {@link org.apache.xpath.patterns.NodeTest#SCORE_OTHER}, or 
386       *         the value defined by the priority attribute of the template.
387       *
388       */
389      private double getPriorityOrScore(TemplateSubPatternAssociation matchPat)
390      {
391    
392        double priority = matchPat.getTemplate().getPriority();
393    
394        if (priority == XPath.MATCH_SCORE_NONE)
395        {
396          Expression ex = matchPat.getStepPattern();
397    
398          if (ex instanceof NodeTest)
399          {
400            return ((NodeTest) ex).getDefaultScore();
401          }
402        }
403    
404        return priority;
405      }
406    
407      /**
408       * Locate a named template.
409       *
410       * @param qname  Qualified name of the template.
411       *
412       * @return Template argument with the requested name, or null if not found.
413       */
414      public ElemTemplate getTemplate(QName qname)
415      {
416        return (ElemTemplate) m_namedTemplates.get(qname);
417      }
418    
419      /**
420       * Get the head of the most likely list of associations to check, based on 
421       * the name and type of the targetNode argument.
422       *
423       * @param xctxt The XPath runtime context.
424       * @param targetNode The target node that will be checked for a match.
425       * @param dtm The dtm owner for the target node.
426       *
427       * @return The head of a linked list that contains all possible match pattern to 
428       * template associations.
429       */
430      public TemplateSubPatternAssociation getHead(XPathContext xctxt, 
431                                                   int targetNode, DTM dtm)
432      {
433        short targetNodeType = dtm.getNodeType(targetNode);
434        TemplateSubPatternAssociation head;
435    
436        switch (targetNodeType)
437        {
438        case DTM.ELEMENT_NODE :
439        case DTM.ATTRIBUTE_NODE :
440          head = (TemplateSubPatternAssociation) m_patternTable.get(
441            dtm.getLocalName(targetNode));
442          break;
443        case DTM.TEXT_NODE :
444        case DTM.CDATA_SECTION_NODE :
445          head = m_textPatterns;
446          break;
447        case DTM.ENTITY_REFERENCE_NODE :
448        case DTM.ENTITY_NODE :
449          head = (TemplateSubPatternAssociation) m_patternTable.get(
450            dtm.getNodeName(targetNode)); // %REVIEW% I think this is right
451          break;
452        case DTM.PROCESSING_INSTRUCTION_NODE :
453          head = (TemplateSubPatternAssociation) m_patternTable.get(
454            dtm.getLocalName(targetNode));
455          break;
456        case DTM.COMMENT_NODE :
457          head = m_commentPatterns;
458          break;
459        case DTM.DOCUMENT_NODE :
460        case DTM.DOCUMENT_FRAGMENT_NODE :
461          head = m_docPatterns;
462          break;
463        case DTM.NOTATION_NODE :
464        default :
465          head = (TemplateSubPatternAssociation) m_patternTable.get(
466            dtm.getNodeName(targetNode)); // %REVIEW% I think this is right
467        }
468    
469        return (null == head) ? m_wildCardPatterns : head;
470      }
471      
472      /**
473       * Given a target element, find the template that best
474       * matches in the given XSL document, according
475       * to the rules specified in the xsl draft.  This variation of getTemplate 
476       * assumes the current node and current expression node have already been 
477       * pushed. 
478       *
479       * @param xctxt
480       * @param targetNode
481       * @param mode A string indicating the display mode.
482       * @param maxImportLevel The maximum importCountComposed that we should consider or -1
483       *        if we should consider all import levels.  This is used by apply-imports to
484       *        access templates that have been overridden.
485       * @param quietConflictWarnings
486       * @return Rule that best matches targetElem.
487       * @throws XSLProcessorException thrown if the active ProblemListener and XPathContext decide
488       * the error condition is severe enough to halt processing.
489       *
490       * @throws TransformerException
491       */
492      public ElemTemplate getTemplateFast(XPathContext xctxt,
493                                    int targetNode,
494                                    int expTypeID,
495                                    QName mode,
496                                    int maxImportLevel,
497                                    boolean quietConflictWarnings,
498                                    DTM dtm)
499                throws TransformerException
500      {
501        
502        TemplateSubPatternAssociation head;
503    
504        switch (dtm.getNodeType(targetNode))
505        {
506        case DTM.ELEMENT_NODE :
507        case DTM.ATTRIBUTE_NODE :
508          head = (TemplateSubPatternAssociation) m_patternTable.get(
509            dtm.getLocalNameFromExpandedNameID(expTypeID));
510          break;
511        case DTM.TEXT_NODE :
512        case DTM.CDATA_SECTION_NODE :
513          head = m_textPatterns;
514          break;
515        case DTM.ENTITY_REFERENCE_NODE :
516        case DTM.ENTITY_NODE :
517          head = (TemplateSubPatternAssociation) m_patternTable.get(
518            dtm.getNodeName(targetNode)); // %REVIEW% I think this is right
519          break;
520        case DTM.PROCESSING_INSTRUCTION_NODE :
521          head = (TemplateSubPatternAssociation) m_patternTable.get(
522            dtm.getLocalName(targetNode));
523          break;
524        case DTM.COMMENT_NODE :
525          head = m_commentPatterns;
526          break;
527        case DTM.DOCUMENT_NODE :
528        case DTM.DOCUMENT_FRAGMENT_NODE :
529          head = m_docPatterns;
530          break;
531        case DTM.NOTATION_NODE :
532        default :
533          head = (TemplateSubPatternAssociation) m_patternTable.get(
534            dtm.getNodeName(targetNode)); // %REVIEW% I think this is right
535        }
536    
537        if(null == head)
538        {
539          head = m_wildCardPatterns;
540          if(null == head)
541            return null;
542        }                                              
543    
544        // XSLT functions, such as xsl:key, need to be able to get to 
545        // current ElemTemplateElement via a cast to the prefix resolver.
546        // Setting this fixes bug idkey03.
547        xctxt.pushNamespaceContextNull();
548        try
549        {
550          do
551          {
552            if ( (maxImportLevel > -1) && (head.getImportLevel() > maxImportLevel) )
553            {
554              continue;
555            }
556            ElemTemplate template = head.getTemplate();        
557            xctxt.setNamespaceContext(template);
558            
559            if ((head.m_stepPattern.execute(xctxt, targetNode, dtm, expTypeID) != NodeTest.SCORE_NONE)
560                    && head.matchMode(mode))
561            {
562              if (quietConflictWarnings)
563                checkConflicts(head, xctxt, targetNode, mode);
564    
565              return template;
566            }
567          }
568          while (null != (head = head.getNext()));
569        }
570        finally
571        {
572          xctxt.popNamespaceContext();
573        }
574    
575        return null;
576      }  // end findTemplate
577    
578      /**
579       * Given a target element, find the template that best
580       * matches in the given XSL document, according
581       * to the rules specified in the xsl draft.
582       *
583       * @param xctxt
584       * @param targetNode
585       * @param mode A string indicating the display mode.
586       * @param quietConflictWarnings
587       * @return Rule that best matches targetElem.
588       * @throws XSLProcessorException thrown if the active ProblemListener and XPathContext decide
589       * the error condition is severe enough to halt processing.
590       *
591       * @throws TransformerException
592       */
593      public ElemTemplate getTemplate(XPathContext xctxt,
594                                    int targetNode,
595                                    QName mode,
596                                    boolean quietConflictWarnings,
597                                    DTM dtm)
598                throws TransformerException
599      {
600    
601        TemplateSubPatternAssociation head = getHead(xctxt, targetNode, dtm);
602    
603        if (null != head)
604        {
605          // XSLT functions, such as xsl:key, need to be able to get to 
606          // current ElemTemplateElement via a cast to the prefix resolver.
607          // Setting this fixes bug idkey03.
608          xctxt.pushNamespaceContextNull();
609          xctxt.pushCurrentNodeAndExpression(targetNode, targetNode);
610          try
611          {
612            do
613            {
614              ElemTemplate template = head.getTemplate();        
615              xctxt.setNamespaceContext(template);
616              
617              if ((head.m_stepPattern.execute(xctxt, targetNode) != NodeTest.SCORE_NONE)
618                      && head.matchMode(mode))
619              {
620                if (quietConflictWarnings)
621                  checkConflicts(head, xctxt, targetNode, mode);
622    
623                return template;
624              }
625            }
626            while (null != (head = head.getNext()));
627          }
628          finally
629          {
630            xctxt.popCurrentNodeAndExpression();
631            xctxt.popNamespaceContext();
632          }
633        }
634    
635        return null;
636      }  // end findTemplate
637      
638      /**
639       * Given a target element, find the template that best
640       * matches in the given XSL document, according
641       * to the rules specified in the xsl draft.
642       *
643       * @param xctxt
644       * @param targetNode
645       * @param mode A string indicating the display mode.
646       * @param maxImportLevel The maximum importCountComposed that we should consider or -1
647       *        if we should consider all import levels.  This is used by apply-imports to
648       *        access templates that have been overridden.
649       * @param endImportLevel The count of composed imports
650       * @param quietConflictWarnings
651       * @return Rule that best matches targetElem.
652       * @throws XSLProcessorException thrown if the active ProblemListener and XPathContext decide
653       * the error condition is severe enough to halt processing.
654       *
655       * @throws TransformerException
656       */
657      public ElemTemplate getTemplate(XPathContext xctxt,
658                                    int targetNode,
659                                    QName mode,
660                                    int maxImportLevel, int endImportLevel,
661                                    boolean quietConflictWarnings,
662                                    DTM dtm)
663                throws TransformerException
664      {
665    
666        TemplateSubPatternAssociation head = getHead(xctxt, targetNode, dtm);
667    
668        if (null != head)
669        {
670          // XSLT functions, such as xsl:key, need to be able to get to 
671          // current ElemTemplateElement via a cast to the prefix resolver.
672          // Setting this fixes bug idkey03.
673          xctxt.pushNamespaceContextNull();
674          xctxt.pushCurrentNodeAndExpression(targetNode, targetNode);
675          try
676          {
677            do
678            {
679              if ( (maxImportLevel > -1) && (head.getImportLevel() > maxImportLevel))
680              {
681                continue;
682              }
683              if (head.getImportLevel()<= maxImportLevel - endImportLevel)
684                return null;
685              ElemTemplate template = head.getTemplate();        
686              xctxt.setNamespaceContext(template);
687              
688              if ((head.m_stepPattern.execute(xctxt, targetNode) != NodeTest.SCORE_NONE)
689                      && head.matchMode(mode))
690              {
691                if (quietConflictWarnings)
692                  checkConflicts(head, xctxt, targetNode, mode);
693    
694                return template;
695              }
696            }
697            while (null != (head = head.getNext()));
698          }
699          finally
700          {
701            xctxt.popCurrentNodeAndExpression();
702            xctxt.popNamespaceContext();
703          }
704        }
705    
706        return null;
707      }  // end findTemplate
708    
709      /**
710       * Get a TemplateWalker for use by a compiler.  See the documentation for
711       * the TreeWalker inner class for further details.
712       */
713      public TemplateWalker getWalker()
714      {
715        return new TemplateWalker();
716      }
717    
718      /**
719       * Check for match conflicts, and warn the stylesheet author.
720       *
721       * @param head Template pattern
722       * @param xctxt Current XPath context
723       * @param targetNode Node matching the pattern
724       * @param mode reference, which may be null, to the <a href="http://www.w3.org/TR/xslt#modes">current mode</a>.
725       */
726      private void checkConflicts(TemplateSubPatternAssociation head,
727                                  XPathContext xctxt, int targetNode, QName mode)
728      {
729    
730        // TODO: Check for conflicts.
731      }
732    
733      /**
734       * Add object to vector if not already there.
735       *
736       * @param obj
737       * @param v
738       */
739      private void addObjectIfNotFound(Object obj, Vector v)
740      {
741    
742        int n = v.size();
743        boolean addIt = true;
744    
745        for (int i = 0; i < n; i++)
746        {
747          if (v.elementAt(i) == obj)
748          {
749            addIt = false;
750    
751            break;
752          }
753        }
754    
755        if (addIt)
756        {
757          v.addElement(obj);
758        }
759      }
760    
761      /**
762       * Keyed on string macro names, and holding values
763       * that are macro elements in the XSL DOM tree.
764       * Initialized in initMacroLookupTable, and used in
765       * findNamedTemplate.
766       * @serial
767       */
768      private Hashtable m_namedTemplates = new Hashtable(89);
769    
770      /**
771       * This table is keyed on the target elements
772       * of patterns, and contains linked lists of
773       * the actual patterns that match the target element
774       * to some degree of specifity.
775       * @serial
776       */
777      private Hashtable m_patternTable = new Hashtable(89);
778    
779      /** Wildcard patterns.
780       *  @serial          */
781      private TemplateSubPatternAssociation m_wildCardPatterns = null;
782    
783      /** Text Patterns.
784       *  @serial          */
785      private TemplateSubPatternAssociation m_textPatterns = null;
786    
787      /** Root document Patterns.
788       *  @serial          */
789      private TemplateSubPatternAssociation m_docPatterns = null;
790    
791      /** Comment Patterns.
792       *  @serial          */
793      private TemplateSubPatternAssociation m_commentPatterns = null;
794    
795      /**
796       * Get table of named Templates.
797       * These are keyed on template names, and holding values
798       * that are template elements.
799       *
800       * @return A Hashtable dictionary that contains {@link java.lang.String}s 
801       * as the keys, and {@link org.apache.xalan.templates.ElemTemplate}s as the 
802       * values. 
803       */
804      private Hashtable getNamedTemplates()
805      {
806        return m_namedTemplates;
807      }
808    
809      /**
810       * Set table of named Templates.
811       * These are keyed on string macro names, and holding values
812       * that are template elements in the XSL DOM tree.
813       *
814       * @param v Hashtable dictionary that contains {@link java.lang.String}s 
815       * as the keys, and {@link org.apache.xalan.templates.ElemTemplate}s as the 
816       * values.
817       */
818      private void setNamedTemplates(Hashtable v)
819      {
820        m_namedTemplates = v;
821      }
822    
823      /**
824       * Get the head of the assocation list that is keyed by target.
825       *
826       * @param key The name of a node. 
827       *
828       * @return The head of a linked list that contains all possible match pattern to 
829       * template associations for the given key.
830       */
831      private TemplateSubPatternAssociation getHead(String key)
832      {
833        return (TemplateSubPatternAssociation) m_patternTable.get(key);
834      }
835    
836      /**
837       * Get the head of the assocation list that is keyed by target.
838       *
839       * @param key
840       * @param assoc
841       */
842      private void putHead(String key, TemplateSubPatternAssociation assoc)
843      {
844    
845        if (key.equals(PsuedoNames.PSEUDONAME_TEXT))
846          m_textPatterns = assoc;
847        else if (key.equals(PsuedoNames.PSEUDONAME_ROOT))
848          m_docPatterns = assoc;
849        else if (key.equals(PsuedoNames.PSEUDONAME_COMMENT))
850          m_commentPatterns = assoc;
851    
852        m_patternTable.put(key, assoc);
853      }
854    
855      /**
856       * An inner class used by a compiler to iterate over all of the ElemTemplates
857       * stored in this TemplateList.  The compiler can replace returned templates
858       * with their compiled equivalent.
859       */
860      public class TemplateWalker
861      {
862        private Enumeration hashIterator;
863        private boolean inPatterns;
864        private TemplateSubPatternAssociation curPattern;
865    
866        private Hashtable m_compilerCache = new Hashtable();
867    
868        private TemplateWalker()
869        {
870          hashIterator = m_patternTable.elements();
871          inPatterns = true;
872          curPattern = null;
873        }
874    
875        public ElemTemplate next()
876        {
877    
878          ElemTemplate retValue = null;
879          ElemTemplate ct;
880    
881          while (true)
882          {
883            if (inPatterns)
884            {
885              if (null != curPattern)
886                curPattern = curPattern.getNext();
887    
888              if (null != curPattern)
889                retValue = curPattern.getTemplate();
890              else
891              {
892                if (hashIterator.hasMoreElements())
893                {
894                  curPattern = (TemplateSubPatternAssociation) hashIterator.nextElement();
895                  retValue =  curPattern.getTemplate();
896                }
897                else
898                {
899                  inPatterns = false;
900                  hashIterator = m_namedTemplates.elements();
901                }
902              }
903            }
904    
905            if (!inPatterns)
906            {
907              if (hashIterator.hasMoreElements())
908                retValue = (ElemTemplate) hashIterator.nextElement();
909              else
910                return null;
911            }
912    
913            ct = (ElemTemplate) m_compilerCache.get(new Integer(retValue.getUid()));
914            if (null == ct)
915            {
916              m_compilerCache.put(new Integer(retValue.getUid()), retValue);
917              return retValue;
918            }
919          }
920        }
921      }
922    
923    }