libsablot/src/engine/tree.h

   1 /*
   2  * The contents of this file are subject to the Mozilla Public
   3  * License Version 1.1 (the "License"); you may not use this file
   4  * except in compliance with the License. You may obtain a copy of
   5  * the License at http://www.mozilla.org/MPL/
   6  *
   7  * Software distributed under the License is distributed on an "AS
   8  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
   9  * implied. See the License for the specific language governing
  10  * rights and limitations under the License.
  11  *
  12  * The Original Code is the Sablotron XSLT Processor.
  13  *
  14  * The Initial Developer of the Original Code is Ginger Alliance Ltd.
  15  * Portions created by Ginger Alliance are Copyright (C) 2000-2002
  16  * Ginger Alliance Ltd. All Rights Reserved.
  17  *
  18  * Contributor(s):
  19  *
  20  * Alternatively, the contents of this file may be used under the
  21  * terms of the GNU General Public License Version 2 or later (the
  22  * "GPL"), in which case the provisions of the GPL are applicable
  23  * instead of those above.  If you wish to allow use of your
  24  * version of this file only under the terms of the GPL and not to
  25  * allow others to use your version of this file under the MPL,
  26  * indicate your decision by deleting the provisions above and
  27  * replace them with the notice and other provisions required by
  28  * the GPL.  If you do not delete the provisions above, a recipient
  29  * may use your version of this file under either the MPL or the
  30  * GPL.
  31  */
  32
  33 #ifndef TreeHIncl
  34 #define TreeHIncl
  35
  36 // GP: clean
  37
  38 #include "base.h"
  39 #include "verts.h"
  40 #include "datastr.h"
  41 #include "output.h"
  42
  43 #ifdef HAVE_CONFIG_H
  44 #include <config.h>
  45 #endif
  46
  47 class RootNode;
  48
  49 #define TREE_ARENA_SIZE      0x10000
  50 #define TREE_DICT_LOGSIZE    10
  51
  52 //atts cache used for parsing
  53 class AttsCache: public PList<Attribute*>
  54 {
  55 public:
  56   AttsCache(): keep(FALSE) {};
  57   ~AttsCache() {if (!keep) freeall(FALSE);};
  58   void keepThem() { keep = TRUE; };
  59   Attribute* find(XSL_ATT what);
  60   Attribute* find(const QName& attName);
  61   int findNdx(const QName& attName);
  62 private:
  63   Bool keep;
  64 };
  65
  66 //_TH_ v
  67
  68 /****************************************
  69 T m p L i s t
  70 ****************************************/
  71
  72 class TmpList : public PList<Vertex *>
  73 {
  74 public:
  75   TmpList();
  76   ~TmpList();
  77   void append(void *what);
  78   void rm(int n);
  79   void freeall(Bool a);
  80   //  void freeall(SablotSituation s);
  81   //  void dump(SablotSituation sit, int p=0);
  82   void dump(int p=0);
  83   int findNum(void *p) const;
  84   void rmP(void *p);
  85 };
  86 //_TH_ ^
  87
  88 class StylesheetStructure;
  89
  90 //
  91 // SubtreeInfo
  92 // holds information about a document which is (1) xsl:included,
  93 // (2) xsl:imported or (3) included as external entity to form a part of
  94 // the tree. The SubtreeInfo records are linked to form a tree, each one
  95 // holds the base URI, pointer to the associated StylesheetStructure
  96 // (only exists for xsl:imports) and 'dependency type' which is
  97 // (1), (2) or (3) above (with values XSL_INCLUDE, XSL_IMPORT and XSL_NONE,
  98 // respectively).
  99 //
 100
 101 class SubtreeInfo
 102 {
 103 public:
 104     SubtreeInfo(const Str& baseURI_, XSL_OP dependency_,
 105                 StylesheetStructure* structure_, Bool inline_) :
 106 #ifdef SABLOT_DEBUGGER
 107       nextBPIndex(-2),
 108 #endif
 109       baseURI(baseURI_), dependency(dependency_), inlineVal(inline_),
 110       structure(structure_), parentSubtree(NULL), masterSubtree(NULL) {};
 111     ~SubtreeInfo();
 112     Str& getBaseURI()
 113         { return baseURI; }
 114     XSL_OP getDependency()
 115         { return dependency; }
 116     StylesheetStructure* getStructure()
 117         { return structure; }
 118     SubtreeInfo* getParentSubtree()
 119         { return parentSubtree; }
 120     void setParentSubtree(SubtreeInfo *parentSubtree_)
 121         { parentSubtree = parentSubtree_; }
 122     SubtreeInfo* getMasterSubtree()
 123       { return masterSubtree ? masterSubtree : this; };
 124     void setMasterSubtree(SubtreeInfo *mstr)
 125       { masterSubtree = mstr; };
 126     Bool isInline() { return inlineVal; };
 127     UriList &getExcludedNS() { return excludedNS; };
 128     void pushNamespaceMarks();
 129     void popNamespaceMarks();
 130     UriList &getExtensionNS() { return extensionNS; };
 131
 132     // this is not thread safe, but it is used by the debugger only,
 133     // what is single threaded by default
 134 #ifdef SABLOT_DEBUGGER
 135     int nextBPIndex;
 136 #endif
 137
 138 private:
 139     Str baseURI;
 140     XSL_OP dependency;
 141     Bool inlineVal;
 142     StylesheetStructure* structure;
 143     //was not used; now it hold pointer to the closest non-inline tree
 144     SubtreeInfo* parentSubtree;
 145     SubtreeInfo* masterSubtree;
 146     UriList excludedNS;
 147     UriList extensionNS;
 148     List<int> excludedCount;
 149     List<int> extensionCount;
 150 };
 151
 152 // the list of subtrees
 153 // although a list, it also has a rooted tree structure
 154
 155 class SubtreeList : public PList<SubtreeInfo*>
 156 {
 157 public:
 158     SubtreeList()
 159         : currentSub(NULL)
 160         {
 161         };
 162
 163     // append subtree to list, make it current in the tree structure
 164     void push(SubtreeInfo* newSub)
 165         {
 166             append(newSub);
 167             NZ(newSub) -> setParentSubtree(currentSub);
 168             currentSub = newSub;
 169         };
 170
 171     // go one level higher in the tree structure (but keep subtree in list!)
 172     SubtreeInfo* pop()
 173         {
 174             assert(currentSub);
 175                 SubtreeInfo *was = currentSub;
 176             currentSub = currentSub -> getParentSubtree();
 177                 return was;
 178         };
 179
 180     // get current subtree
 181     SubtreeInfo* getCurrent()
 182         {
 183             return currentSub;
 184         }
 185
 186     SubtreeInfo* findAmongPredecessors(const Str& uri)
 187         {
 188             assert(currentSub);
 189             for (SubtreeInfo* i = currentSub -> getParentSubtree();
 190                  i;
 191                  i = i -> getParentSubtree() )
 192                 if (i -> getBaseURI() == uri)
 193                     return i;
 194             return NULL;
 195         }
 196
 197 private:
 198     SubtreeInfo* currentSub;
 199 };
 200
 201 //
 202 //
 203 //  VarDirectory
 204 //  list of top-level variables and params used to find those of
 205 //  highest import precedence, while checking for duplicates in
 206 //  each source document
 207 //
 208
 209 class VarDirectoryItem
 210 {
 211 public:
 212     VarDirectoryItem(QName &name_, XSLElement *varElem_)
 213         : varElem(varElem_), name(name_)
 214         {};
 215     XSLElement* getElement()
 216         { return varElem; }
 217     void setElement(XSLElement *varElem_)
 218         { varElem = varElem_; }
 219     const QName &getName()
 220         { return name; }
 221     void setName(const QName &name_)
 222         { name = name_; }
 223 private:
 224     XSLElement *varElem;
 225     QName name;
 226 };
 227
 228 class VarDirectory : public PList<VarDirectoryItem*>
 229 {
 230 public:
 231     VarDirectory();
 232     // kills all VarDirectoryItems
 233     ~VarDirectory();
 234     // find the var/param of the given QName (relative to the stylesheet
 235     // dictionary), NULL if not found
 236     XSLElement* find(QName& name);
 237     // insert the var/param (overwriting any previous entry of the same name)
 238     eFlag insert(Sit S, QName &name, XSLElement* var);
 239 private:
 240     // find index of entry with the given QName, -1 if not found
 241     int findNdx(const QName& name);
 242     void report(Sit S, MsgType type, MsgCode code,
 243                 const Str &arg1, const Str &arg2) const
 244         { S.message(type, code, arg1, arg2); }
 245 };
 246
 247 class SpaceNameList : public PList<EQName*>
 248 {
 249 public:
 250   Bool findName(EQName &ename, double &prio);
 251 };
 252
 253 /****************************************
 254 StylesheetStructure
 255
 256 Holds information about the stylesheet tree (pointers
 257 to template rules etc.)
 258 Created when a document is parsed as stylesheet.
 259 The 'imports' list points to structures for all
 260 imported stylesheets (these form a tree).
 261 ****************************************/
 262
 263 class StylesheetStructure
 264 {
 265 public:
 266     StylesheetStructure(int importPrecedence_)
 267         : importPrecedence(importPrecedence_), topLevelFound(false) {};
 268     ~StylesheetStructure()
 269         {
 270             importChildren.freeall(FALSE);
 271             // rulesList.freeall(FALSE); - done in ~RuleSList
 272             strippedNamesList.freeall(FALSE);
 273             preservedNamesList.freeall(FALSE);
 274         }
 275
 276 /***
 277     findBestRule
 278
 279     Finds the rule of highest import precedence and highest priority
 280     that is satisfied by the current node of the context c. If
 281     several rules are satisfied, returns the one that occurs last.
 282     The current mode is given in currMode (may be NULL). The result,
 283     a pointer to the template rule node, is returned in ret.
 284
 285     If no rule is found, asks the structures for imported stylesheets.
 286     If this doesn't yield a match too, returns NULL.
 287
 288     If 'importsOnly' is true, looks only at the imported stylesheets.
 289
 290     ASSUMPTION: 'rules' is sorted by priority in reverse order.
 291 ***/
 292
 293     eFlag findBestRule(Sit S, XSLElement *&ret, Context *c,
 294                        QName *currMode, Bool importsOnly);
 295
 296     // finds the rule of given name with highest import precedence
 297     // 't' is the stylesheet
 298     XSLElement* findRuleByName(Tree& t, QName &q);
 299
 300     // return the list of template rules from this structure
 301     RuleSList &rules()
 302         { return rulesList; }
 303
 304     // insert a template rule into 'rulesList'
 305     // the rule is given as a pointer to the corresponding xsl:template
 306     eFlag insertRule(Sit S, XSLElement *tmpl);
 307
 308     // add structure for imported stylesheet
 309     void addImportStructure(Sit S, StylesheetStructure *imported)
 310       //{ importChildren.append(imported); }
 311       { importChildren.insertBefore(imported, 0); }
 312
 313     // get the import precedence associated with this imported subtree
 314     int getImportPrecedence()
 315       { return importPrecedence; }
 316
 317     //set the import precedence
 318     void setImportPrecedence(int prec)
 319       { importPrecedence = prec; }
 320
 321     SpaceNameList &strippedNames() { return strippedNamesList; }
 322     SpaceNameList &preservedNames() { return preservedNamesList; }
 323     Bool findStrippedName(EQName &ename, int &prec, double &prio);
 324     Bool findPreservedName(EQName &ename, int &prec, double &prio);
 325     Bool hasAnyStripped();
 326     Bool hasAnyPreserved();
 327     Bool getTopLevelFound() { return topLevelFound; };
 328     void setTopLevelFound(Bool val) { topLevelFound = val; }
 329 private:
 330     PList<StylesheetStructure*> importChildren;
 331     RuleSList rulesList;
 332     SpaceNameList strippedNamesList;
 333     SpaceNameList preservedNamesList;
 334     int importPrecedence;
 335     Bool topLevelFound; //used during the xslt parse only, thread safe
 336     void report(Sit S, MsgType type, MsgCode code,
 337                 const Str &arg1, const Str &arg2) const
 338         { S.message(type, code, arg1, arg2); }
 339 };
 340
 341 /****************************************************************
 342
 343 AttributeSets
 344
 345 *****************************************************************/
 346
 347 class AttSetMember
 348 {
 349 public:
 350     AttSetMember(QName &attName_)
 351         : attDef(NULL), redefinition(NULL),
 352       attName(attName_), precedence(-1) {};
 353     XSLElement* getAttributeDef()
 354         {return attDef;}
 355     // see if there was multiple definition with highest import precedence
 356     XSLElement* getRedefinition()
 357         {return redefinition;}
 358
 359     QName &getAttName()
 360         { return attName; }
 361     // sets to a new value if importPrecedence is smaller (stronger)
 362     // sets 'redefinition' if equal precedence
 363     void set(XSLElement *newAttDef);
 364 private:
 365     XSLElement
 366         *attDef,
 367         *redefinition;
 368     QName attName;
 369     int precedence;
 370 };
 371
 372 class AttSet : public PList<AttSetMember*>
 373 {
 374 public:
 375     AttSet(QName &name_);
 376     ~AttSet();
 377     void insertAttributeDef(XSLElement *attDef, QName &attName);
 378     void insertUses(QName &usedSet);
 379     const QName& getName()
 380         { return name; }
 381     eFlag checkRedefinitions(Sit S);
 382     // execute the attribute set
 383     eFlag execute(Sit S, Context *c, Tree& sheet,
 384                   QNameList& history,  Bool resolvingGlobals);
 385     int findNdx(QName &attName);
 386 private:
 387     QName name;
 388     QNameList usedSets;
 389     void report(Sit S, MsgType type, MsgCode code,
 390                 const Str &arg1, const Str &arg2) const
 391         { S.message(type, code, arg1, arg2); }
 392 };
 393
 394 class AttSetList : public PList<AttSet*>
 395 {
 396 public:
 397     AttSetList();
 398     ~AttSetList();
 399     // check all attribute sets for multiply defined attributes
 400     eFlag checkRedefinitions(Sit S);
 401     // insert an AttSet named 'name' and return pointer (the set may already exist)
 402     AttSet* insert(QName& name);
 403     eFlag executeAttSet(Sit S, QName &name, Context *c, Tree &sheet,
 404                         QNameList& history, Bool resolvingGlobals);
 405     AttSet* findByName(const QName &name) const
 406         { int ndx = findNdx(name); return (ndx == -1) ? NULL : (*this)[ndx]; }
 407 private:
 408     int findNdx(const QName &name) const;
 409     void report(Sit S, MsgType type, MsgCode code,
 410                 const Str &arg1, const Str &arg2) const
 411         { S.message(type, code, arg1, arg2); }
 412 };
 413
 414 //
 415 //
 416 //  AliasItem
 417 //  records one alias for use in AliasPrecList
 418 //  holds the key-value pair, checks import precedence on setting
 419 //
 420 //
 421
 422 class AliasItem
 423 {
 424 public:
 425     AliasItem()
 426       :key(UNDEF_PHRASE), value(UNDEF_PHRASE), prefix(UNDEF_PHRASE),
 427       precedence(-1), redefinition(NULL) {};
 428     Phrase getKey() {return key;}
 429     Phrase getValue() {return value;}
 430     Phrase getPrefix() {return prefix;}
 431
 432     // see if there was multiple definition with highest import precedence
 433     XSLElement* getRedefinition()
 434         {return redefinition;}
 435     // sets to a new value if newPrecedence is smaller (stronger)
 436     // sets 'redefinition' if precedences were equal (typically an error)
 437     // but sets key/value anyway
 438     void set(Phrase newKey, Phrase newValue, Phrase newPrefix,
 439              int newPrecedence, XSLElement *source);
 440 private:
 441     Phrase key, value, prefix;
 442     int precedence;
 443     XSLElement *redefinition;
 444 };
 445
 446 //
 447 //
 448 //  AliasList
 449 //  list of namespace aliases defined by xsl:namespace-alias
 450 //  checks import precedence when inserting
 451 //
 452 //
 453
 454 class AliasList : public PList<AliasItem*>
 455 {
 456 public:
 457     // find the value of the element with the given key
 458     Phrase find(Phrase) const;
 459     // insert an alias (or overwrite old if precedence is not weaker)
 460     void insertAlias(Phrase key, Phrase value, Phrase prefix, int precedence,
 461                      XSLElement *source);
 462     eFlag checkRedefinitions(Sit S, Tree &sheet);
 463 private:
 464     // find the index of the element with the given key
 465     int findNdx(Phrase) const;
 466     void report(Sit S, MsgType type, MsgCode code, const Str &arg1,
 467                 const Str &arg2) const
 468         { S.message(type, code, arg1, arg2); }
 469 };
 470
 471
 472
 473
 474 /****************************************
 475 T r e e
 476
 477 Represents a XML tree in memory. Created by parsing a document.
 478 A tree can be used in several processing sessions and even by
 479 several threads, so it SHOULD NOT CHANGE during processing (in other
 480 words, it holds information which is static with respect to processing).
 481 ****************************************/
 482
 483 class Tree
 484 {
 485 public:
 486     // pass the URI of the tree's document
 487     // isXSL_ = TRUE iff the tree represents a stylesheet
 488     Tree(const Str& uri, Bool isXSL_);
 489     ~Tree();
 490     BOOL XSLTree;
 491     eFlag appendVertex(Sit S, Vertex *);
 492     Vertex* popVertex();
 493     Vertex* appendText(Sit S, char *, int);
 494     eFlag parseFinished(Sit S);
 495     void dump();
 496     Vertex *stackTop;
 497     NSList &pendingNS() {return *(pendingNSList.last());};
 498     void dropCurrentElement(Vertex *);
 499     void flushPendingText();
 500     Element& dummyElement() const;
 501     HashTable& dict();
 502     SabArena& getArena();
 503     const QName& getTheEmptyQName() const;
 504     Phrase stdPhrase(StandardPhrase phrase_) const
 505     {
 506         assert(phrase_ <= PHRASE_LAST);
 507             return stdPhrases[phrase_];
 508     };
 509     Bool cmpQNames(const QName &q1, const QName &q2) const;
 510     Bool cmpQNamesForeign(const QName &q, const HashTable& dictForeign, const QName &qForeign);
 511     Bool cmpQNameStrings(const QName &q, const Str& uri, const Str& local);
 512     void expandQ(const QName& q, EQName &expanded);
 513     void expandQStr(const QName& q, Str &expName);
 514     const Str& expand(Phrase ph);
 515     Phrase unexpand(const Str& strg);
 516     RootNode& getRoot() const {return* NZ(root);}
 517     eFlag serialize(Sit S, char *& result);
 518     eFlag serializeNode(Sit S, Element *v, char *& result);
 519     void makeStamps();
 520
 521     //// methods to access stylesheet structure
 522
 523     // finds the best matching rule
 524     // see StylesheetStructure::findBestRule for description
 525     eFlag findBestRule(Sit S, XSLElement *&ret, Context *c,
 526                        QName *currMode, Bool importsOnly,
 527                        SubtreeInfo *subtree = NULL);
 528
 529     // finds the rule of given name with highest import precedence
 530     XSLElement* findRuleByName(QName &q);
 531
 532
 533     // returns the list of attribute sets defined
 534     AttSetList &attSets()
 535         { return attSetList; }
 536
 537     // The list of namespace aliases
 538     AliasList &aliases()
 539         { return aliasesList; }
 540
 541     // Output definition holding compiled information from various
 542     //   xsl:output elements
 543     // At runtime, this is copied by Processor and defaults are provided
 544     //   FOR THE COPY (cannot be guessed at parse time)
 545     OutputDefinition outputDef;
 546
 547     // this is called after each element has been parsed in
 548     // used to compile StylesheetStructure (template rule pointers), process
 549     //   includes/imports, etc.
 550     eFlag processVertexAfterParse(Sit S, Vertex *v, TreeConstructer* tc);
 551
 552     // creates this tree by parsing the given dataline
 553     eFlag parse(Sit S, DataLine *d);
 554
 555     // returns in 'result' the list of elements matching the given expression
 556     // used for key creation
 557     eFlag getMatchingList(Sit S, Expression& match, Context& result);
 558
 559     // find global variable in directory
 560     XSLElement* findVarInDirectory(QName &name)
 561         { return toplevelVars.find(name); }
 562
 563     // the list of temporary nodes which belong to the tree but are not part
 564     // of it (used for cleaning up in SDOM)
 565     TmpList tmpList;
 566
 567     // EXTENSION NAMESPACES
 568     // FIXME: efficiency?
 569     // FIXME: extension URIs are only valid outside imports/includes!!
 570     Bool isExtensionUri(Phrase uri);
 571     // MAIN METHODS TO RECORD THE PARSING OF EXTERNAL ENTITIES/INCLUDES/IMPORTS
 572     // start a subtree, recording its base URI.
 573     // 'dependency' is XSL_NONE (external entity), XSL_INCLUDE or XSL_IMPORT
 574     eFlag startSubtree(Sit S, const Str& baseURI, XSL_OP dependency,
 575                        Bool isInline = FALSE);
 576     // end a subtree
 577     eFlag endSubtree(Sit S, XSL_OP dependency);
 578     // get the tree's URI
 579     const Str& getURI()
 580       {
 581         return subtrees[0] -> getBaseURI();
 582       }
 583     // resolve all global variables before starting execute
 584     // called from Processor::resolveGlobals
 585     //eFlag resolveGlobals(Sit S, Context *c, Processor *proc);
 586     //unparsed entties storge
 587     void setUnparsedEntityUri(Str &name, Str &uri);
 588     Str* getUnparsedEntityUri(Str &name);
 589     int stripped;
 590     Bool hasAnyStrippedName();
 591     Bool hasAnyPreservedName();
 592     Bool findPreservedName(EQName &name, int &prec, double &prio);
 593     Bool findStrippedName(EQName &name, int &prec, double &prio);
 594     Element* findStylesheet(Daddy& d);
 595     eFlag pushPendingNS(Sit S, Tree* srcTree, NSList &other);
 596     eFlag popPendingNS(Sit S);
 597     SubtreeInfo* getRootSubtree() { return subtrees[0]; }
 598     SubtreeInfo* getCurrentInfo()
 599       {return subtrees.getCurrent()->getMasterSubtree();}
 600     eFlag markNamespacePrefixes(Sit S);
 601     eFlag pushNamespacePrefixes(Sit, Str&, XSL_ATT);
 602     eFlag popNamespacePrefixes(Sit);
 603     void updateImportStatus();
 604     //void speakDebug();
 605 private:
 606     SabArena theArena;
 607     Text *pendingTextNode;
 608     DStr pendingText;
 609     int vcount;             // # of vertices in tree
 610     Element *theDummyElement;
 611     HashTable theDictionary;
 612     PList<NSList*> pendingNSList;
 613     const QName theEmptyQName;
 614     Phrase stdPhrases[PHRASE_LAST];
 615     void initDict();
 616     RootNode *root;
 617     RuleSList rulesList;
 618     StrStrList unparsedEntities;
 619     eFlag insertRule(Sit S, XSLElement *tmpl);
 620     eFlag insertAttSet(Sit S, XSLElement *tmpl);
 621     double defaultPriorityLP(Expression *);
 622     double defaultPriority(XSLElement *);
 623     void report(Sit S, MsgType type, MsgCode code, const Str &arg1, const Str &arg2) const
 624         { S.message(type, code, arg1, arg2); }
 625     eFlag getSpaceNames(Sit S, Element &e, Str &str, SpaceNameList &where);
 626     eFlag extractUsedSets(Sit S, Element *e);
 627     void excludeStdNamespaces();
 628     // create a new structure
 629     StylesheetStructure* createStylesheetStructure(Sit S);
 630
 631     // the structure information about the stylesheet
 632     // (separated for import purposes)
 633     StylesheetStructure structure;
 634
 635     // list of subtrees
 636     SubtreeList subtrees;
 637     AttSetList attSetList;
 638     AliasList aliasesList;
 639     VarDirectory toplevelVars;
 640     int hasAnyStripped, hasAnyPreserved;
 641     int importUnique;
 642 };
 643
 644 #endif //ifndef TreeHIncl
 645
 646