cde/programs/dthelp/parser.ccdf/htag/parser/minim.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: minim.c /main/3 1995/11/08 11:25:32 rswiston $ */
  24 /*
  25               Copyright 1986 Tandem Computers Incorporated.
  26 This product and information is proprietary of Tandem Computers Incorporated.
  27                    Copyright 1986, 1987, 1988, 1989 Hewlett-Packard Co.
  28 */
  29
  30 /* Minim.c contains procedures relevant to tag minimization */
  31
  32 #include <stdio.h>
  33 #include <string.h>
  34 #if defined(MSDOS)
  35 #include <process.h>
  36 #endif
  37 #include "basic.h"
  38 #include "trie.h"
  39 #include "dtdext.h"
  40 #include "parser.h"
  41 #include "delim.h"
  42 #include "context.h"
  43
  44 /* M_expecting reports to the user the possible valid content at a particular
  45    state in the parse of the document */
  46 void m_expecting(M_NOPAR)
  47   {
  48     LOGICAL expstart = TRUE ;
  49     M_PARSE *stackptr ;
  50     M_OPENFSA *fsastack ;
  51     M_ANDLIST *usedand ;
  52     M_ANDGROUP pand ;
  53     LOGICAL required = FALSE ;
  54     LOGICAL data = FALSE ;
  55
  56     m_expcount = 0 ;
  57     if (m_stacktop->intext) m_expline(&expstart, &data, M_NULLVAL) ;
  58     for (stackptr = m_stacktop ; stackptr ; stackptr = stackptr->oldtop) {
  59       if (m_explimit && m_expcount > M_EXPLIMIT) return ;
  60       if (m_start && ! stackptr->oldtop) return ;
  61       /* First check for possible start-tags.
  62          Begin by testing if at start of document or not within a
  63            CDATA or RCDATA element. */
  64       if (! stackptr->oldtop ||
  65           m_element[stackptr->element - 1].content == M_REGEXP) {
  66         /* Note the following statement, which checks the type of the
  67            element at the top of the stack, is not a repeat of the previous
  68            one, which checks the type of an element embedded in the stack.
  69            The second comparison prevents traversing paths from
  70            a parent of an RCDATA or CDATA element and still allows displaying
  71            the end-tag of the parent */
  72         if (! stackptr->oldtop ||
  73             m_element[m_stacktop->element - 1].content == M_REGEXP)
  74           for (fsastack = stackptr->fsastack ;
  75                fsastack ;
  76                fsastack = fsastack->oldtop) {
  77             for (pand = fsastack->andgroup ;
  78                  pand ;
  79                  pand = m_andgroup[pand - 1].next) {
  80               for (usedand = fsastack->usedand ;
  81                    usedand ;
  82                    usedand = usedand->next)
  83                 if (usedand->group == pand) break ;
  84               if (! usedand)
  85                 m_expexpand(&expstart, m_andgroup[pand - 1].start, &required,
  86                             &data) ;
  87               }
  88             if (required) return ;
  89             m_expexpand(&expstart, fsastack->current, &required, &data) ;
  90             if (! m_state[fsastack->current - 1].final) return ;
  91             }
  92         }
  93       else if (m_element[stackptr->element - 1].content == M_CDATA ||
  94                m_element[stackptr->element - 1].content == M_RCDATA)
  95         m_expline(&expstart, &data, M_NULLVAL) ;
  96       if (m_explimit && m_expcount > M_EXPLIMIT) return ;
  97       /* Now report the end-tag */
  98       m_exptend(&expstart, stackptr) ;
  99       if (! m_element[stackptr->element - 1].emin) return ;
 100       }
 101     }
 102
 103 /* Recursive procedure first called from expecting() to display
 104    names of elements reachable from a particular node */
 105 void m_expexpand(expstart, node, required, data)
 106   LOGICAL *expstart ;
 107   M_STATE node ;
 108   LOGICAL *required ;
 109   LOGICAL *data ;
 110   {
 111     M_ARC parc ;
 112     M_ANDGROUP pand ;
 113
 114     for (parc = m_state[node - 1].first ;
 115          parc ;
 116          parc = m_arc[parc - 1].next) {
 117       if (m_explimit && m_expcount > M_EXPLIMIT) return ;
 118       if (m_arc[parc - 1].group)
 119         for (pand = m_arc[parc - 1].group ;
 120              pand ;
 121              pand = m_andgroup[pand - 1].next)
 122           m_expexpand(expstart, m_andgroup[pand - 1].start, required, data) ;
 123       else {
 124         if (! m_state[node - 1].final) *required = TRUE ;
 125         m_expline(expstart, data, m_arc[parc - 1].label) ;
 126         }
 127       }
 128     }
 129
 130 /* M_expline writes one line for m_expecting() */
 131 void m_expline(expstart, data, label)
 132   LOGICAL *expstart ;
 133   LOGICAL *data ;
 134   M_ELEMENT label ;
 135   {
 136     char buffer[M_NAMELEN + 2*MAXD + 1] ;
 137
 138     if (! label && *data) return ;
 139     if (m_excluded(label)) return ;
 140     if (*expstart) {
 141       sprintf(buffer, "Expecting ") ;
 142       m_errline(buffer) ;
 143       *expstart = FALSE ;
 144       }
 145     else {
 146       sprintf(buffer, "   or     ") ;
 147       m_errline(buffer) ;
 148       }
 149     if (m_explimit && m_expcount == M_EXPLIMIT) {
 150       sprintf(buffer, ". . .\n") ;
 151       m_errline(buffer) ;
 152       }
 153     else if (label) {
 154       char *mb_enptr;
 155
 156       mb_enptr = MakeMByteString(&m_ename[m_element[label - 1].enptr]);
 157       sprintf(buffer, "%s%s%s\n", m_stago, mb_enptr, m_tagc) ;
 158       m_free(mb_enptr,"multi-byte string");
 159       m_errline(buffer) ;
 160       }
 161     else {
 162       sprintf(buffer, "data characters\n") ;
 163       m_errline(buffer) ;
 164       *data = TRUE ;
 165       }
 166     m_expcount++ ;
 167     }
 168
 169 /* M_exptend is called from m_expecting to inform the user after an
 170    error if an end tag is permitted */
 171 void m_exptend(expstart, stackptr)
 172   LOGICAL *expstart ;
 173   M_PARSE *stackptr ;
 174   {
 175     char buffer[M_NAMELEN + 2*MAXD + 1] ;
 176
 177     if (*expstart) {
 178       sprintf(buffer, "Expecting ") ;
 179       m_errline(buffer) ;
 180       *expstart = FALSE ;
 181       }
 182     else {
 183       sprintf(buffer, "   or     ") ;
 184       m_errline(buffer) ;
 185       }
 186     if (m_explimit && m_expcount == M_EXPLIMIT) {
 187       sprintf(buffer, ". . .\n") ;
 188       m_errline(buffer) ;
 189       }
 190     else if (stackptr->neednet) {
 191       sprintf(buffer, "%s\n", m_net) ;
 192       m_errline(buffer) ;
 193       }
 194     else {
 195       char *mb_enptr;
 196
 197       mb_enptr =
 198           MakeMByteString(&m_ename[m_element[stackptr->element - 1].enptr]);
 199       sprintf(buffer, "%s%s%s\n", m_etago, mb_enptr, m_tagc) ;
 200       m_free(mb_enptr,"multi-byte string");
 201       m_errline(buffer) ;
 202       }
 203     m_expcount++ ;
 204     }
 205
 206 /* M_findunique is used to test for start tag minimization.  If the current
 207    parse state permits at least one element with explicit start-tag
 208    minimization, the left-most such element to occur in the content model
 209    is returned.  Otherwise, the contextually-required element, if any,
 210    is returned.  Finally, if the parse state permits a unique valid element,
 211    and the flag for conformance to ISO 8879 is not set, the unique valid
 212    element is returned by m_findunique.
 213
 214    Before returning, m_findunique verifies that the element to be returned
 215    permits start-tag minimization.  If not, the value is returned only if
 216    conformance to ISO 8879 is set.
 217
 218    Actually m_findunique returns 1 greater than the index of the unique
 219    element, 1 if character data is expected, and 0 (FALSE) if there is
 220    no unique element.
 221 */
 222 M_ELEMENT m_findunique(from, newleft)
 223   M_STATE from ;
 224   int *newleft ;
 225   {
 226     M_ARC parc ;
 227     M_ELEMENT cr = 0, minim = 0;
 228     int leftmost = M_BIGINT ;
 229     int testleft = M_BIGINT ;
 230     int testminim ;
 231     M_ANDGROUP pand ;
 232
 233     for (parc = m_state[from - 1].first ;
 234          parc ;
 235          parc = m_arc[parc - 1].next) {
 236       if (m_arc[parc - 1].group) {
 237         if (! m_conform)
 238           for (pand = m_arc[parc - 1].group ;
 239                pand ;
 240                pand = m_andgroup[pand - 1].next) {
 241             testminim = m_findunique(m_andgroup[pand - 1].start, &testleft) ;
 242             if (testminim && testleft < leftmost) {
 243               minim = testminim ;
 244               leftmost = testleft ;
 245               }
 246             }
 247         }
 248       else {
 249         if (! m_conform) {
 250           if (m_arc[parc - 1].minim &&
 251               m_arc[parc - 1].minim < leftmost &&
 252               ! m_excluded(m_arc[parc - 1].label)) {
 253             /* Save the explicitly minimizable element plus its position
 254                in the content model */
 255             leftmost = m_arc[parc - 1].minim ;
 256             minim = m_arc[parc - 1].label + 1 ;
 257             } /* End arc.minim > leftmost */
 258           else if (m_arc[parc - 1].optional &&
 259                    parc == m_state[from - 1].first &&
 260                    ! m_arc[parc - 1].next &&
 261                    m_element[m_arc[parc - 1].label -1].smin &&
 262                    ! m_excluded(m_arc[parc - 1].label))
 263             /* Save the only element that can occur */
 264             cr = m_arc[parc - 1].label ;
 265           } /* End if (! m_conform) */
 266         /* Save the contextually-required element */
 267         if (! m_arc[parc - 1].optional && ! m_excluded(m_arc[parc - 1].label))
 268           cr = m_arc[parc - 1].label ;
 269         } /* End if (! group) */
 270       } /* End for parc */
 271     *newleft = leftmost ;
 272     if (minim) return(minim) ;
 273     if (cr) return(cr + 1) ;
 274     return(FALSE) ;
 275     }
 276
 277 /* M_nullendtag is called when a null end tag is encountered; i.e., at the
 278    end of a short element */
 279 void m_nullendtag(M_NOPAR)
 280   {
 281     LOGICAL foundnet ;
 282
 283     while (m_stacktop->oldtop) {
 284       foundnet = m_stacktop->neednet ;
 285       if (! foundnet && ! m_element[m_stacktop->element - 1].emin) {
 286         m_err1("Missing end tag for %s",
 287                m_nameofelt(m_stacktop->element)) ;
 288         m_showcurelt() ;
 289         }
 290       if (! m_ckend(m_stacktop->element, foundnet)) {
 291         M_WCHAR *wc_found;
 292
 293         wc_found = MakeWideCharString(foundnet ? "Null" : "Implied");
 294         m_err2("%s end tag for %s unexpected",
 295                wc_found,
 296                m_nameofelt(m_stacktop->element)) ;
 297         m_free(wc_found,"wide character string");
 298         m_expecting() ;
 299         m_showcurelt() ;
 300         m_frcend(m_stacktop->element) ;
 301         }
 302       if (foundnet) return ;
 303       }
 304     m_error("Internal error: Invalid stack in Nullendtag") ;
 305     m_exit(TRUE) ;
 306     }
 307
 308 /* Tests to see if an end tag may have been omitted at this point in the
 309    parse.*/
 310 LOGICAL m_omitend(M_NOPAR)
 311   {
 312     M_ANDGROUP pand ;
 313     M_OPENFSA *fsastack ;
 314     M_ANDLIST *usedand ;
 315
 316     if (! m_stacktop->oldtop) return(FALSE) ;
 317     if (m_element[m_stacktop->element - 1].content != M_REGEXP) return(TRUE) ;
 318     for (fsastack = m_stacktop->fsastack ;
 319          fsastack ;
 320          fsastack = fsastack->oldtop) {
 321       for (pand = fsastack->andgroup ;
 322            pand ;
 323            pand = m_andgroup[pand - 1].next) {
 324         /* Doesn't matter if optional submodel of and-group has occurred */
 325         if (m_state[m_andgroup[pand - 1].start - 1].final) continue ;
 326         for (usedand = fsastack->usedand ;
 327              usedand ;
 328              usedand = usedand->next)
 329           if (usedand->group == pand) break ;
 330         /* Required submodel of and-group has not occurred */
 331         if (! usedand) return(FALSE) ;
 332         }
 333       /* Current FSA not in final state */
 334       if (! m_state[fsastack->current - 1].final) return(FALSE) ;
 335       }
 336     *m_nextme = (M_MIN *) m_malloc(sizeof(M_MIN), "end-tag minimization") ;
 337     (*m_nextme)->val = m_stacktop->element ;
 338     (*m_nextme)->next = NULL ;
 339     m_nextme = &(*m_nextme)->next ;
 340     return(TRUE) ;
 341     }
 342
 343 /* Tests to see if a start tag may have been omitted at this point of
 344    the parse.  If so, saves the element name in the MINVAL array*/
 345 LOGICAL m_omitstart()
 346   {
 347     M_ELEMENT c = M_NULLVAL ;
 348
 349     /* int par ;  (used in commented-out code below) */
 350     M_OPENFSA *fsastack ;
 351     M_ANDLIST *usedand ;
 352     M_ANDGROUP pand ;
 353     int leftmost = M_BIGINT ;
 354     int newleft = M_BIGINT ;
 355     M_ELEMENT newc = M_NULLVAL ;
 356     LOGICAL required = FALSE ;
 357     M_MIN *min ;
 358
 359     /* Make sure are in an element that has a content model */
 360     if (m_stacktop->oldtop &&
 361         m_element[m_stacktop->element - 1].content != M_REGEXP)
 362       return(FALSE) ;
 363
 364     /* Test for unique element expected, or only allowed token is #PCDATA */
 365     for (fsastack = m_stacktop->fsastack ;
 366          fsastack ;
 367          fsastack = fsastack->oldtop) {
 368       for (pand = fsastack->andgroup ;
 369            pand ;
 370            pand = m_andgroup[pand - 1].next) {
 371         for (usedand = fsastack->usedand ;
 372              usedand ;
 373              usedand = usedand->next)
 374           if (usedand->group == pand) break ;
 375         if (! usedand) {
 376           if (! m_state[m_andgroup[pand - 1].start - 1].final)
 377             required = TRUE ;
 378           newc = m_findunique(m_andgroup[pand - 1].start, &newleft) ;
 379           if (newleft < leftmost) {
 380             leftmost = newleft ;
 381             c = newc ;
 382             }
 383           }
 384         }
 385       if (! required) {
 386         newc = m_findunique(fsastack->current, &newleft) ;
 387         if (newleft < leftmost) {
 388           leftmost = newleft ;
 389           c = newc ;
 390           }
 391         }
 392       if (c > 1) break ;
 393       if (fsastack == m_stacktop->fsastack && newc) {
 394         c = newc ;
 395         break ;
 396         }
 397       if (m_conform) return(FALSE) ;
 398       if (! m_state[fsastack->current - 1].final) return(FALSE) ;
 399       }
 400     if (! c) return(FALSE) ;
 401
 402     /* Have found a unique element.  Can its start-tag be omitted? */
 403     c-- ;
 404     if (m_element[c - 1].content == M_NONE) return(FALSE) ;
 405     if (m_element[c - 1].content == M_CDATA) return(FALSE) ;
 406     if (m_element[c - 1].content == M_RCDATA) return(FALSE) ;
 407
 408     /* Following code allows start-tag to be omitted only if all required
 409        parameters are specified:
 410     for (par = m_element[c - 1].parptr ; par ;
 411          par = m_parameter[par - 1].next)
 412       if (m_parameter[par - 1].deftype == M_REQUIRED) return(FALSE) ;
 413     */
 414
 415     /* Check for recursive sequences of omitted tags */
 416     for (min = m_minstart ; min ; min = min->next)
 417       if (c == min->val) return(FALSE) ;
 418
 419     m_push(c, m_element[c - 1].start, FALSE) ;
 420     *m_nextms = (M_MIN *) m_malloc(sizeof(M_MIN), "start-tag minimization") ;
 421     (*m_nextms)->val = m_stacktop->element ;
 422     (*m_nextms)->next = NULL ;
 423     m_nextms = &(*m_nextms)->next ;
 424     return(TRUE) ;
 425     }
 426