common.w

模拟器提供了一个简单易用的平台

with the identifier names, but a hash table is not used for them because
\.{CTANGLE} needs to be able to recognize a section name when given a prefix of
that name. A conventional binary search tree is used to retrieve section names,
with fields called |llink| and |rlink| (where |llink| takes the place
of |link|).  The root of this tree is stored in |name_dir->rlink|;
this will be the only information in |name_dir[0]|.

Since the space used by |rlink| has a different function for
identifiers than for section names, we declare it as a |union|.

@d llink link /* left link in binary search tree for section names */
@d rlink dummy.Rlink /* right link in binary search tree for section names */
@d root name_dir->rlink /* the root of the binary search tree
  for section names */

@<More elements of |name...@>=
union {
  struct name_info *Rlink; /* right link in binary search tree for section
    names */
  char Ilk; /* used by identifiers in \.{CWEAVE} only */
} dummy;

@ @<Init...@>=
root=NULL; /* the binary search tree starts out with nothing in it */

@ If |p| is a |name_pointer| variable, as we have seen,
|p->byte_start| is the beginning of the area where the name
corresponding to |p| is stored.  However, if |p| refers to a section
name, the name may need to be stored in chunks, because it may
``grow'': a prefix of the section name may be encountered before
the full name.  Furthermore we need to know the length of the shortest
prefix of the name that was ever encountered.

We solve this problem by inserting two extra bytes at |p->byte_start|,
representing the length of the shortest prefix, when |p| is a
section name. Furthermore, the last byte of the name will be a blank
space if |p| is a prefix. In the latter case, the name pointer
|p+1| will allow us to access additional chunks of the name:
The second chunk will begin at the name pointer |(p+1)->link|,
and if it too is a prefix (ending with blank) its |link| will point
to additional chunks in the same way. Null links are represented by
|name_dir|.

@d first_chunk(p)  ((p)->byte_start+2)
@d prefix_length(p) (int)((unsigned char)*((p)->byte_start)*256 +
                (unsigned char)*((p)->byte_start+1))
@d set_prefix_length(p,m) (*((p)->byte_start)=(m)/256,
                 *((p)->byte_start+1)=(m)%256)

@c
void
print_section_name(p)
name_pointer p;
{
  char *ss, *s = first_chunk(p);
  name_pointer q = p+1;
  while (p!=name_dir) {
    ss = (p+1)->byte_start-1;
    if (*ss==' ' && ss>=s) {
      term_write(s,ss-s); p=q->link; q=p;
    } else {
      term_write(s,ss+1-s); p=name_dir; q=NULL;
    }
    s = p->byte_start;
  }
  if (q) term_write("...",3); /* complete name not yet known */
}

@ @c
void
sprint_section_name(dest,p)
  char*dest;
  name_pointer p;
{
  char *ss, *s = first_chunk(p);
  name_pointer q = p+1;
  while (p!=name_dir) {
    ss = (p+1)->byte_start-1;
    if (*ss==' ' && ss>=s) {
      p=q->link; q=p;
    } else {
      ss++; p=name_dir;
    }
    strncpy(dest,s,ss-s), dest+=ss-s;
    s = p->byte_start;
  }
  *dest='\0';
}

@ @c
void
print_prefix_name(p)
name_pointer p;
{
  char *s = first_chunk(p);
  int l = prefix_length(p);
  term_write(s,l);
  if (s+l<(p+1)->byte_start) term_write("...",3);
}

@ When we compare two section names, we'll need a function analogous to
|strcmp|. But we do not assume the strings
are null-terminated, and we keep an eye open for prefixes and extensions.

@d less 0 /* the first name is lexicographically less than the second */
@d equal 1 /* the first name is equal to the second */
@d greater 2 /* the first name is lexicographically greater than the second */
@d prefix 3 /* the first name is a proper prefix of the second */
@d extension 4 /* the first name is a proper extension of the second */

@c
int web_strcmp(j,j_len,k,k_len) /* fuller comparison than |strcmp| */
  char *j, *k; /* beginning of first and second strings */
  int j_len, k_len; /* length of strings */
{
  char *j1=j+j_len, *k1=k+k_len;
  while (k<k1 && j<j1 && *j==*k) k++, j++;
  if (k==k1) if (j==j1) return equal;
    else return extension;
  else if (j==j1) return prefix;
  else if (*j<*k) return less;
  else return greater;
}

@ Adding a section name to the tree is straightforward if we know its
parent and whether it's the |rlink| or |llink| of the parent.  As a
special case, when the name is the first section being added, we set the
``parent'' to |NULL|.  When a section name is created, it has only one
chunk, which however may be just a prefix; the full name will
hopefully be unveiled later.  Obviously, |prefix_length| starts
out as the length of the first chunk, though it may decrease later.

The information associated with a new node must be initialized
differently in \.{CWEAVE} and \.{CTANGLE}; hence the
|init_node| procedure, which is defined differently in \.{cweave.w}
and \.{ctangle.w}.

@<Prede...@>=
extern void init_node();

@ @c
name_pointer
add_section_name(par,c,first,last,ispref) /* install a new node in the tree */
name_pointer par; /* parent of new node */
int c; /* right or left? */
char *first; /* first character of section name */
char *last; /* last character of section name, plus one */
int ispref; /* are we adding a prefix or a full name? */
{
  name_pointer p=name_ptr; /* new node */
  char *s=first_chunk(p);
  int name_len=last-first+ispref; /* length of section name */
  if (s+name_len>byte_mem_end) overflow("byte memory");
  if (name_ptr+1>=name_dir_end) overflow("name");
  (++name_ptr)->byte_start=byte_ptr=s+name_len;
  if (ispref) {
    *(byte_ptr-1)=' ';
    name_len--;
    name_ptr->link=name_dir;
    (++name_ptr)->byte_start=byte_ptr;
  }
  set_prefix_length(p,name_len);
  strncpy(s,first,name_len);
  p->llink=NULL;
  p->rlink=NULL;
  init_node(p);
  return par==NULL ? (root=p) : c==less ? (par->llink=p) : (par->rlink=p);
}

@ @c
void
extend_section_name(p,first,last,ispref)
name_pointer p; /* name to be extended */
char *first; /* beginning of extension text */
char *last; /* one beyond end of extension text */
int ispref; /* are we adding a prefix or a full name? */
{
  char *s;
  name_pointer q=p+1;
  int name_len=last-first+ispref;
  if (name_ptr>=name_dir_end) overflow("name");
  while (q->link!=name_dir) q=q->link;
  q->link=name_ptr;
  s=name_ptr->byte_start;
  name_ptr->link=name_dir;
  if (s+name_len>byte_mem_end) overflow("byte memory");
  (++name_ptr)->byte_start=byte_ptr=s+name_len;
  strncpy(s,first,name_len);
  if (ispref) *(byte_ptr-1)=' ';
}

@ The |section_lookup| procedure is supposed to find a
section name that matches a new name, installing the new name if
it doesn't match an existing one. The new name is the string
between |first| and |last|; a ``match'' means that the new name
exactly equals or is a prefix or extension of a name in the tree.

@c
name_pointer
section_lookup(first,last,ispref) /* find or install section name in tree */
char *first, *last; /* first and last characters of new name */
int ispref; /* is the new name a prefix or a full name? */
{
  int c=0; /* comparison between two names; initialized so some compilers won't complain */
  name_pointer p=root; /* current node of the search tree */
  name_pointer q=NULL; /* another place to look in the tree */
  name_pointer r=NULL; /* where a match has been found */
  name_pointer par=NULL; /* parent of |p|, if |r| is |NULL|;
            otherwise parent of |r| */
  int name_len=last-first+1;
  @<Look for matches for new name among shortest prefixes, complaining
        if more than one is found@>;
  @<If no match found, add new name to tree@>;
  @<If one match found, check for compatibility and return match@>;
}

@ A legal new name matches an existing section name if and only if it
matches the shortest prefix of that section name.  Therefore we can
limit our search for matches to shortest prefixes, which eliminates
the need for chunk-chasing at this stage.

@<Look for matches for new name among...@>=
while (p) { /* compare shortest prefix of |p| with new name */
  c=web_strcmp(first,name_len,first_chunk(p),prefix_length(p));
  if (c==less || c==greater) { /* new name does not match |p| */
    if (r==NULL) /* no previous matches have been found */
      par=p;
    p=(c==less?p->llink:p->rlink);
  } else { /* new name matches |p| */
    if (r!=NULL) {  /* and also |r|: illegal */
      printf("\n! Ambiguous prefix: matches <");
@.Ambiguous prefix ... @>
      print_prefix_name(p);
      printf(">\n and <");
      print_prefix_name(r);
      err_print(">");
      return name_dir; /* the unsection */
    }
    r=p; /* remember match */
    p=p->llink; /* try another */
    q=r->rlink; /* we'll get back here if the new |p| doesn't match */
  }
  if (p==NULL)
    p=q, q=NULL; /* |q| held the other branch of |r| */
}

@ @<If no match ...@>=
  if (r==NULL) /* no matches were found */
    return add_section_name(par,c,first,last+1,ispref);

@ Although error messages are given in anomalous cases, we do return the
unique best match when a discrepancy is found, because users often
change a title in one place while forgetting to change it elsewhere.

@<If one match found, check for compatibility and return match@>=
switch(section_name_cmp(&first,name_len,r)) {
              /* compare all of |r| with new name */
  case prefix:
    if (!ispref) {
      printf("\n! New name is a prefix of <");
@.New name is a prefix...@>
      print_section_name(r);
      err_print(">");
    }
    else if (name_len<prefix_length(r)) set_prefix_length(r,name_len);
    /* fall through */
  case equal: return r;
  case extension: if (!ispref || first<=last)
        extend_section_name(r,first,last+1,ispref);
      return r;
  case bad_extension:
      printf("\n! New name extends <");
@.New name extends...@>
      print_section_name(r);
      err_print(">");
    return r;
  default: /* no match: illegal */
    printf("\n! Section name incompatible with <");
@.Section name incompatible...@>
    print_prefix_name(r);
    printf(">,\n which abbreviates <");
    print_section_name(r);
    err_print(">");
    return r;
}

@ The return codes of |section_name_cmp|, which compares a string with
the full name of a section, are those of |web_strcmp| plus
|bad_extension|, used when the string is an extension of a
supposedly already complete section name.  This function has a side
effect when the comparison string is an extension: It advances the
address of the first character of the string by an amount equal to
the length of the known part of the section name.

The name \.{@@<foo...@@>} should be an acceptable ``abbreviation''
for \.{@@<foo@@>}. If such an abbreviation comes after the complete
name, there's no trouble recognizing it. If it comes before the
complete name, we simply append a null chunk. This logic requires
us to regard \.{@@<foo...@@>} as an ``extension'' of itself.

@d bad_extension 5

@<Predec...@>=
int section_name_cmp();

@ @c
int section_name_cmp(pfirst,len,r)
char **pfirst; /* pointer to beginning of comparison string */
int len; /* length of string */
name_pointer r; /* section name being compared */
{
  char *first=*pfirst; /* beginning of comparison string */
  name_pointer q=r+1; /* access to subsequent chunks */
  char *ss, *s=first_chunk(r);
  int c; /* comparison */
  int ispref; /* is chunk |r| a prefix? */
  while (1) {
    ss=(r+1)->byte_start-1;
    if (*ss==' ' && ss>=r->byte_start) ispref=1,q=q->link;
    else ispref=0,ss++,q=name_dir;
    switch(c=web_strcmp(first,len,s,ss-s)) {
    case equal: if (q==name_dir)
        if (ispref) {
          *pfirst=first+(ss-s);
          return extension; /* null extension */
        } else return equal;
      else return (q->byte_start==(q+1)->byte_start)? equal: prefix;
    case extension:
      if (!ispref) return bad_extension;
      first += ss-s;
      if (q!=name_dir) {len -= ss-s; s=q->byte_start; r=q; continue;}
      *pfirst=first; return extension;
    default: return c;
    }
  }
}

@ The last component of |name_info| is different for \.{CTANGLE} and
\.{CWEAVE}.  In \.{CTANGLE}, if |p| is a pointer to a section name,
|p->equiv| is a pointer to its replacement text, an element of the
array |text_info|.  In \.{CWEAVE}, on the other hand, if
|p| points to an identifier, |p->xref| is a pointer to its
list of cross-references, an element of the array |xmem|.  The make-up
of |text_info| and |xmem| is discussed in the \.{CTANGLE} and \.{CWEAVE}
source files, respectively; here we just declare a common field
|equiv_or_xref| as a pointer to a |char|.

@<More elements of |name...@>=
char *equiv_or_xref; /* info corresponding to names */

@** Reporting errors to the user.
A global variable called |history| will contain one of four values
at the end of every run: |spotless| means that no unusual messages were
printed; |harmless_message| means that a message of possible interest