cde/programs/nsgmls/parseMode.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: parseMode.C /main/1 1996/07/29 17:09:27 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #include "splib.h"
  28 #include "Parser.h"
  29 #include "ParserMessages.h"
  30 #include "MessageArg.h"
  31 #include "TokenMessageArg.h"
  32 #include "ModeInfo.h"
  33 #include "Partition.h"
  34 #include "SrInfo.h"
  35 #include "Vector.h"
  36 #include "ISetIter.h"
  37 #include "token.h"
  38 #include "TrieBuilder.h"
  39 #include "macros.h"
  40
  41 #ifdef SP_NAMESPACE
  42 namespace SP_NAMESPACE {
  43 #endif
  44
  45 enum {
  46   modeUsedInSd = 01,
  47   modeUsedInProlog = 02,
  48   modeUsedInInstance = 04,
  49   modeUsesSr = 010
  50 };
  51
  52 static struct {
  53   Mode mode;
  54   unsigned flags;
  55 } modeTable[] = {
  56   { grpMode, modeUsedInProlog|modeUsedInInstance },
  57   { alitMode, modeUsedInProlog|modeUsedInInstance },
  58   { alitaMode, modeUsedInProlog|modeUsedInInstance },
  59   { aliteMode, modeUsedInProlog|modeUsedInInstance },
  60   { talitMode, modeUsedInProlog|modeUsedInInstance },
  61   { talitaMode, modeUsedInProlog|modeUsedInInstance },
  62   { taliteMode, modeUsedInProlog|modeUsedInInstance },
  63   { mdMode, modeUsedInProlog|modeUsedInInstance|modeUsedInSd },
  64   { mdMinusMode, modeUsedInProlog },
  65   { mdPeroMode, modeUsedInProlog },
  66   { comMode, modeUsedInProlog|modeUsedInInstance },
  67   { sdcomMode, modeUsedInSd },
  68   { piMode, modeUsedInProlog|modeUsedInInstance },
  69   { refMode, modeUsedInProlog|modeUsedInInstance|modeUsedInSd },
  70   { imsMode, modeUsedInProlog|modeUsedInInstance },
  71   { cmsMode, modeUsedInProlog|modeUsedInInstance },
  72   { rcmsMode, modeUsedInProlog|modeUsedInInstance },
  73   { proMode, modeUsedInProlog },
  74   { dsMode, modeUsedInProlog },
  75   { dsiMode, modeUsedInProlog },
  76   { plitMode, modeUsedInProlog },
  77   { plitaMode, modeUsedInProlog },
  78   { pliteMode, modeUsedInProlog },
  79   { sdplitMode, modeUsedInSd },
  80   { sdplitaMode, modeUsedInSd },
  81   { grpsufMode, modeUsedInProlog },
  82   { mlitMode, modeUsedInProlog|modeUsedInSd },
  83   { mlitaMode, modeUsedInProlog|modeUsedInSd },
  84   { asMode, modeUsedInProlog },
  85   { slitMode, modeUsedInProlog },
  86   { slitaMode, modeUsedInProlog },
  87   { cconMode, modeUsedInInstance },
  88   { rcconMode, modeUsedInInstance },
  89   { cconnetMode, modeUsedInInstance },
  90   { rcconnetMode, modeUsedInInstance },
  91   { rcconeMode, modeUsedInInstance },
  92   { tagMode, modeUsedInInstance },
  93   { econMode, modeUsedInInstance|modeUsesSr },
  94   { mconMode, modeUsedInInstance|modeUsesSr },
  95   { econnetMode, modeUsedInInstance|modeUsesSr },
  96   { mconnetMode, modeUsedInInstance|modeUsesSr },
  97 };
  98
  99 void Parser::compileSdModes()
 100 {
 101   Mode modes[nModes];
 102   int n = 0;
 103   for (size_t i = 0; i < SIZEOF(modeTable); i++)
 104     if (modeTable[i].flags & modeUsedInSd)
 105       modes[n++] = modeTable[i].mode;
 106   compileModes(modes, n, 0);
 107 }
 108
 109 void Parser::compilePrologModes()
 110 {
 111   Boolean scopeInstance = sd().scopeInstance();
 112   Boolean haveSr = syntax().hasShortrefs();
 113   Mode modes[nModes];
 114   int n = 0;
 115   for (size_t i = 0; i < SIZEOF(modeTable); i++) {
 116     if (scopeInstance) {
 117       if (modeTable[i].flags & modeUsedInProlog)
 118         modes[n++] = modeTable[i].mode;
 119     }
 120     else if (haveSr) {
 121       if ((modeTable[i].flags & (modeUsedInInstance|modeUsedInProlog))
 122           && !(modeTable[i].flags & modeUsesSr))
 123         modes[n++] = modeTable[i].mode;
 124     }
 125     else {
 126       if (modeTable[i].flags & (modeUsedInInstance|modeUsedInProlog))
 127         modes[n++] = modeTable[i].mode;
 128     }
 129   }
 130   compileModes(modes, n, 0);
 131 }
 132
 133 void Parser::compileInstanceModes()
 134 {
 135   Boolean scopeInstance = sd().scopeInstance();
 136   compileNormalMap();
 137   if (!scopeInstance && !syntax().hasShortrefs())
 138     return;
 139   Mode modes[nModes];
 140   int n = 0;
 141   for (size_t i = 0; i < SIZEOF(modeTable); i++) {
 142     if (scopeInstance) {
 143       if (modeTable[i].flags & modeUsedInInstance)
 144         modes[n++] = modeTable[i].mode;
 145     }
 146     else {
 147       if (modeTable[i].flags & modeUsesSr)
 148         modes[n++] = modeTable[i].mode;
 149     }
 150   }
 151   compileModes(modes, n, &currentDtd());
 152 }
 153
 154 void Parser::compileModes(const Mode *modes,
 155                           int n,
 156                           const Dtd *dtd)
 157 {
 158   PackedBoolean sets[Syntax::nSet];
 159   PackedBoolean delims[Syntax::nDelimGeneral];
 160   PackedBoolean functions[3];
 161   int i;
 162   Boolean includesShortref = 0;
 163   for (i = 0; i < Syntax::nSet; i++)
 164     sets[i] = 0;
 165   for (i = 0; i < Syntax::nDelimGeneral; i++)
 166     delims[i] = 0;
 167   for (i = 0; i < 3; i++)
 168     functions[i] = 0;
 169
 170   for (i = 0; i < n; i++) {
 171     ModeInfo iter(modes[i], sd());
 172     TokenInfo ti;
 173     while (iter.nextToken(&ti)) {
 174       switch (ti.type) {
 175       case TokenInfo::delimType:
 176         delims[ti.delim1] = 1;
 177         break;
 178       case TokenInfo::delimDelimType:
 179         delims[ti.delim1] = 1;
 180         delims[ti.delim2] = 1;
 181         break;
 182       case TokenInfo::delimSetType:
 183         delims[ti.delim1] = 1;
 184         // fall through
 185       case TokenInfo::setType:
 186         sets[ti.set] = 1;
 187         break;
 188       case TokenInfo::functionType:
 189         functions[ti.function] = 1;
 190         break;
 191       }
 192     }
 193     if (!includesShortref && iter.includesShortref())
 194       includesShortref = 1;
 195   }
 196
 197   ISet<Char> chars;
 198
 199   for (i = 0; i < 3; i++)
 200     if (functions[i])
 201       chars.add(syntax().standardFunction(i));
 202   for (i = 0; i < Syntax::nDelimGeneral; i++)
 203     if (delims[i]) {
 204       const StringC &str = syntax().delimGeneral(i);
 205       for (size_t j = 0; j < str.size(); j++)
 206         chars.add(str[j]);
 207     }
 208   if (includesShortref && dtd) {
 209     size_t n = dtd->nShortref();
 210     for (size_t i = 0; i < n; i++) {
 211       const StringC &delim = dtd->shortref(i);
 212       size_t len = delim.size();
 213       for (size_t j = 0; j < len; j++)
 214         if (delim[j] == sd().execToDoc('B'))
 215           sets[Syntax::blank] = 1;
 216         else
 217           chars.add(delim[j]);
 218     }
 219   }
 220
 221   const ISet<Char> *csets[Syntax::nSet];
 222   int usedSets = 0;
 223   for (i = 0; i < Syntax::nSet; i++)
 224     if (sets[i])
 225       csets[usedSets++] = syntax().charSet(i);
 226
 227   Partition partition(chars, csets, usedSets, *syntax().generalSubstTable());
 228
 229   String<EquivCode> setCodes[Syntax::nSet];
 230
 231   int nCodes = 0;
 232   for (i = 0; i < Syntax::nSet; i++)
 233     if (sets[i])
 234       setCodes[i] = partition.setCodes(nCodes++);
 235
 236   String<EquivCode> delimCodes[Syntax::nDelimGeneral];
 237   for (i = 0; i < Syntax::nDelimGeneral; i++)
 238     if (delims[i]) {
 239       StringC str = syntax().delimGeneral(i);
 240       for (size_t j = 0; j < str.size(); j++)
 241         delimCodes[i] += partition.charCode(str[j]);
 242     }
 243
 244   String<EquivCode> functionCode[3];
 245   for (i = 0; i < 3; i++)
 246     if (functions[i])
 247       functionCode[i] += partition.charCode(syntax().standardFunction(i));
 248
 249   Vector<SrInfo> srInfo;
 250
 251   int nShortref;
 252   if (!includesShortref || !dtd)
 253     nShortref = 0;
 254   else {
 255     nShortref = dtd->nShortref();
 256     srInfo.resize(nShortref);
 257
 258     for (i = 0; i < nShortref; i++) {
 259       const StringC delim = dtd->shortref(i);
 260       SrInfo *p = &srInfo[i];
 261       size_t j;
 262       for (j = 0; j < delim.size(); j++) {
 263         if (delim[j] == sd().execToDoc('B'))
 264           break;
 265         p->chars += partition.charCode(delim[j]);
 266       }
 267       if (j < delim.size()) {
 268         p->bSequenceLength = 1;
 269         for (++j; j < delim.size(); j++) {
 270           if (delim[j] != sd().execToDoc('B'))
 271             break;
 272           p->bSequenceLength += 1;
 273         }
 274         for (; j < delim.size(); j++)
 275           p->chars2 += partition.charCode(delim[j]);
 276       }
 277       else
 278         p->bSequenceLength = 0;
 279     }
 280   }
 281
 282   const String<EquivCode> emptyString;
 283   Boolean multicode = syntax().multicode();
 284   for (i = 0; i < n; i++) {
 285     TrieBuilder tb(partition.maxCode() + 1);
 286     TrieBuilder::TokenVector ambiguities;
 287     Vector<Token> suppressTokens;
 288     if (multicode) {
 289       suppressTokens.assign(partition.maxCode() + 1, 0);
 290       suppressTokens[partition.eECode()] = tokenEe;
 291     }
 292     tb.recognizeEE(partition.eECode(), tokenEe);
 293     ModeInfo iter(modes[i], sd());
 294     TokenInfo ti;
 295     // We try to handle the possibility that some delimiters may be empty;
 296     // this might happen when compiling recognizers for the SGML declaration.
 297     while (iter.nextToken(&ti)) {
 298       switch (ti.type) {
 299       case TokenInfo::delimType:
 300         if (delimCodes[ti.delim1].size() > 0)
 301           tb.recognize(delimCodes[ti.delim1], ti.token,
 302                        ti.priority, ambiguities);
 303         break;
 304       case TokenInfo::delimDelimType:
 305         {
 306           String<EquivCode> str(delimCodes[ti.delim1]);
 307           if (str.size() > 0 && delimCodes[ti.delim2].size() > 0) {
 308             str += delimCodes[ti.delim2];
 309             tb.recognize(str, ti.token, ti.priority, ambiguities);
 310           }
 311         }
 312         break;
 313       case TokenInfo::delimSetType:
 314         if (delimCodes[ti.delim1].size() > 0)
 315           tb.recognize(delimCodes[ti.delim1], setCodes[ti.set],
 316                        ti.token, ti.priority, ambiguities);
 317         break;
 318       case TokenInfo::setType:
 319         tb.recognize(emptyString, setCodes[ti.set], ti.token,
 320                      ti.priority, ambiguities);
 321         if (multicode) {
 322           const String<EquivCode> &equivCodes = setCodes[ti.set];
 323           for (size_t j = 0; j < equivCodes.size(); j++)
 324             suppressTokens[equivCodes[j]] = ti.token;
 325         }
 326         break;
 327       case TokenInfo::functionType:
 328         tb.recognize(functionCode[ti.function], ti.token,
 329                      ti.priority, ambiguities);
 330         if (multicode)
 331           suppressTokens[functionCode[ti.function][0]] = ti.token;
 332         break;
 333       }
 334     }
 335     if (iter.includesShortref()) {
 336       for (int j = 0; j < nShortref; j++) {
 337         const SrInfo *p = &srInfo[j];
 338         if (p->bSequenceLength > 0)
 339           tb.recognizeB(p->chars, p->bSequenceLength,
 340                         syntax().quantity(Syntax::qBSEQLEN),
 341                         setCodes[Syntax::blank],
 342                         p->chars2, tokenFirstShortref + j,
 343                         ambiguities);
 344         else
 345           tb.recognize(p->chars, tokenFirstShortref + j,
 346                        Priority::delim, ambiguities);
 347       }
 348     }
 349     setRecognizer(modes[i],
 350                   (multicode
 351                    ? new Recognizer(tb.extractTrie(), partition.map(),
 352                                     suppressTokens)
 353                    : new Recognizer(tb.extractTrie(), partition.map())));
 354     // FIXME give more information
 355     for (size_t j = 0; j < ambiguities.size(); j += 2)
 356       message(ParserMessages::lexicalAmbiguity,
 357               TokenMessageArg(ambiguities[j], modes[i], syntaxPointer(),
 358                               sdPointer()),
 359               TokenMessageArg(ambiguities[j + 1], modes[i], syntaxPointer(),
 360                               sdPointer()));
 361   }
 362 }
 363
 364 void Parser::compileNormalMap()
 365 {
 366   XcharMap<PackedBoolean> map(0);
 367   ISetIter<Char> sgmlCharIter(*syntax().charSet(Syntax::sgmlChar));
 368   Char min, max;
 369   while (sgmlCharIter.next(min, max))
 370     map.setRange(min, max, 1);
 371   ModeInfo iter(mconnetMode, sd());
 372   TokenInfo ti;
 373   while (iter.nextToken(&ti)) {
 374     switch (ti.type) {
 375     case TokenInfo::delimType:
 376     case TokenInfo::delimDelimType:
 377     case TokenInfo::delimSetType:
 378       {
 379         Char c = syntax().delimGeneral(ti.delim1)[0];
 380         map.setChar(c, 0);
 381         StringC str(syntax().generalSubstTable()->inverse(c));
 382         for (size_t i = 0; i < str.size(); i++)
 383           map.setChar(str[i], 0);
 384       }
 385       break;
 386     case TokenInfo::setType:
 387       if (ti.token != tokenChar) {
 388         ISetIter<Char> setIter(*syntax().charSet(ti.set));
 389         Char min, max;
 390         while (setIter.next(min, max))
 391           map.setRange(min, max, 0);
 392       }
 393       break;
 394     case TokenInfo::functionType:
 395       if (ti.token != tokenChar)
 396         map.setChar(syntax().standardFunction(ti.function), 0);
 397       break;
 398     }
 399   }
 400   int nShortref = currentDtd().nShortref();
 401   for (int i = 0; i < nShortref; i++) {
 402     Char c = currentDtd().shortref(i)[0];
 403     if (c == sd().execToDoc('B')) {
 404       ISetIter<Char> setIter(*syntax().charSet(Syntax::blank));
 405       Char min, max;
 406       while (setIter.next(min, max))
 407         map.setRange(min, max, 0);
 408     }
 409     else {
 410       map.setChar(c, 0);
 411       StringC str(syntax().generalSubstTable()->inverse(c));
 412       for (size_t j = 0; j < str.size(); j++)
 413         map.setChar(str[j], 0);
 414     }
 415   }
 416   setNormalMap(map);
 417 }
 418
 419 void Parser::addNeededShortrefs(Dtd &dtd, const Syntax &syntax)
 420 {
 421   if (!syntax.hasShortrefs())
 422     return;
 423   PackedBoolean delimRelevant[Syntax::nDelimGeneral];
 424   size_t i;
 425   for (i = 0; i < Syntax::nDelimGeneral; i++)
 426     delimRelevant[i] = 0;
 427   ModeInfo iter(mconnetMode, sd());
 428   TokenInfo ti;
 429   while (iter.nextToken(&ti)) {
 430     switch (ti.type) {
 431     case TokenInfo::delimType:
 432     case TokenInfo::delimDelimType:
 433     case TokenInfo::delimSetType:
 434       delimRelevant[ti.delim1] = 1;
 435       break;
 436     default:
 437       break;
 438     }
 439   }
 440
 441   // PIO and NET are the only delimiters that are recognized in con
 442   // mode without context.  If a short reference delimiter is
 443   // identical to one of these delimiters, then we'll have an
 444   // ambiguity.   We make such a short reference delimiter needed
 445   // to ensure that this ambiguity is reported.
 446   if (syntax.isValidShortref(syntax.delimGeneral(Syntax::dPIO)))
 447     dtd.addNeededShortref(syntax.delimGeneral(Syntax::dPIO));
 448   if (syntax.isValidShortref(syntax.delimGeneral(Syntax::dNET)))
 449     dtd.addNeededShortref(syntax.delimGeneral(Syntax::dNET));
 450
 451   size_t nShortrefComplex = syntax.nDelimShortrefComplex();
 452
 453   // A short reference delimiter is needed if it is used or if it can
 454   // contains some other shorter delimiter that is either a relevant general
 455   // delimiter or a shortref delimiter that is used.
 456
 457   for (i = 0; i < nShortrefComplex; i++) {
 458     size_t j;
 459     for (j = 0; j < Syntax::nDelimGeneral; j++)
 460       if (delimRelevant[j]
 461           && shortrefCanPreemptDelim(syntax.delimShortrefComplex(i),
 462                                      syntax.delimGeneral(j),
 463                                      0,
 464                                      syntax)) {
 465         dtd.addNeededShortref(syntax.delimShortrefComplex(i));
 466         break;
 467       }
 468     for (j = 0; j < dtd.nShortref(); j++)
 469       if (shortrefCanPreemptDelim(syntax.delimShortrefComplex(i),
 470                                   dtd.shortref(j),
 471                                   1,
 472                                   syntax)) {
 473         dtd.addNeededShortref(syntax.delimShortrefComplex(i));
 474         break;
 475       }
 476   }
 477
 478 }
 479
 480 Boolean Parser::shortrefCanPreemptDelim(const StringC &sr,
 481                                         const StringC &d,
 482                                         Boolean dIsSr,
 483                                         const Syntax &syntax)
 484 {
 485   Char letterB = sd().execToDoc('B');
 486   for (size_t i = 0; i < sr.size(); i++) {
 487     size_t j = 0;
 488     size_t k = i;
 489     for (;;) {
 490       if (j == d.size())
 491         return 1;
 492       if (k >= sr.size())
 493         break;
 494       if (sr[k] == letterB) {
 495         if (dIsSr && d[j] == letterB) {
 496           j++;
 497           k++;
 498         }
 499         else if (syntax.isB(d[j])) {
 500           j++;
 501           k++;
 502           if (k == sr.size() || sr[k] != letterB) {
 503             // it was the last B in the sequence
 504             while (j < d.size() && syntax.isB(d[j]))
 505               j++;
 506           }
 507         }
 508         else
 509           break;
 510       }
 511       else if (dIsSr && d[j] == letterB) {
 512         if (syntax.isB(sr[k])) {
 513           ++j;
 514           ++k;
 515           if (j < d.size() && d[j] != letterB) {
 516             while (k < sr.size() && syntax.isB(sr[k]))
 517               k++;
 518           }
 519         }
 520         else
 521           break;
 522       }
 523       else if (d[j] == sr[k]) {
 524         j++;
 525         k++;
 526       }
 527       else
 528         break;
 529     }
 530   }
 531   return 0;
 532 }
 533
 534 #ifdef SP_NAMESPACE
 535 }
 536 #endif