cde/programs/dthelp/parser/pass2/parser/minim.c

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