selector.c

HTML-XML-utils由一套小型C程序（过滤器）组成

/*
 * Type definitions and a parser for CSS selectors.
 *
 * Only parses selectors that allow incremental rendering
 * of a document.
 *
 * The Selector type is a linked list of simple selectors, with the
 * subject at the head, and its context linked from the "context"
 * field. The "combinator" field is the relation between this simple
 * selector and its context.
 *
 * To do: backslash escapes elsewhere than in element names.
 *
 * Author: Bert Bos <[e-mail]>
 * Created: 8 July 2001
 * Version: $Id: selector.c,v 1.5 2002/02/14 10:22:48 bbos Exp $
 **/

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include "export.h"
#include "heap.e"
#include "types.e"
#include "errexit.e"

EXPORT typedef enum {				/* Pseudo-classes */
  Root, NthChild, NthOfType, FirstChild, FirstOfType, Lang
} PseudoType;

EXPORT typedef struct _PseudoCond {
  PseudoType type;
  int a, b;					/* :nth-child(an+b) */
  string s;					/* :lang(s) */
  struct _PseudoCond *next;
} PseudoCond;

EXPORT typedef enum {				/* =, ~=, ^=, $= *= |= */
  Exists, Equals, Includes, StartsWith, EndsWidth, Contains, LangMatch,
  HasClass, HasID				/* ".foo", "#foo" */
} Operator;

EXPORT typedef struct _AttribCond {
  Operator op;
  string name;					/* If not HasClass/ID */
  string value;					/* If op!=Exists */
  struct _AttribCond *next;
} AttribCond;

EXPORT typedef enum {
  Descendant, Child, Adjacent, Sibling
} Combinator;

EXPORT typedef struct _SimpleSelector {
  string name;					/* NULL is "*" */
  AttribCond *attribs;
  PseudoCond *pseudos;
  Combinator combinator;			/* If context not NULL */
  struct _SimpleSelector *context;
} SimpleSelector, *Selector;

typedef enum {
  INIT, SLASH, START_SIMPLE, START_CLASS, START_ID, COMMENT,
  AFTER_SIMPLE, COMMENT_STAR, START_ATTR, START_PSEUDO, ESC0,
  TYPE, AFTER_TYPE, ESCAPE, CLASS, ID, ATTR, AFTER_ATTR, EQ,
  START_VALUE, DSTRING, SSTRING, VALUE, HASH, AFTER_VALUE, PSEUDO_R,
  PSEUDO_RO, PSEUDO_ROO, PSEUDO_ROOT, PSEUDO_F, PSEUDO_FI, PSEUDO_FIR,
  PSEUDO_FIRS, PSEUDO_FIRST, PSEUDO_FIRST_, PSEUDO_FIRST_C,
  PSEUDO_FIRST_CH, PSEUDO_FIRST_CHI, PSEUDO_FIRST_CHIL,
  PSEUDO_FIRST_CHILD, PSEUDO_FIRST_CHILD_, PSEUDO_N, PSEUDO_NT,
  PSEUDO_NTH, PSEUDO_NTH_, PSEUDO_NTH_C, PSEUDO_NTH_CH,
  PSEUDO_NTH_CHI, PSEUDO_NTH_CHIL, PSEUDO_NTH_CHILD, PSEUDO_NTH_CHILD_,
  PSEUDO_L, PSEUDO_LA, PSEUDO_NTH_LAN, PSEUDO_NTH_LANG, PSEUDO_NTH_LANG_,
  PSEUDO_NTH_O, PSEUDO_NTH_OF, PSEUDO_NTH_OF_, PSEUDO_NTH_OF_T,
  PSEUDO_NTH_OF_TY, PSEUDO_NTH_OF_TYP, PSEUDO_NTH_OF_TYPE,
  PSEUDO_NTH_OF_TYPE_, PSEUDO_FIRST_O, PSEUDO_FIRST_OF,
  PSEUDO_FIRST_OF_, PSEUDO_FIRST_OF_T, PSEUDO_FIRST_OF_TY,
  PSEUDO_FIRST_OF_TYP, PSEUDO_FIRST_OF_TYPE, END_PSEUDO,
  START_INT, INT, PSEUDO_LAN, PSEUDO_LANG, PSEUDO_LANG_, LANG,
  AFTER_MUL, AFTER_MUL_N, AFTER_MUL_NPLUS, PSEUDO__O,
  PSEUDO__OD, PSEUDO__ODD, PSEUDO__E,
  PSEUDO__EV, PSEUDO__EVE, PSEUDO__EVEN, PSEUDO__MINUS, PSEUDO__NEG
  
} State;


/* strappc -- append a character to a malloc'ed string */
static void strappc(string *s, unsigned char c)
{
  int len = strlen(*s);
  renewarray(*s, len + 2);
  (*s)[len] = c;
  (*s)[len+1] = '\0';
}

/* pseudos_to_string -- convert pseudo-class selectors to a string */
static string pseudos_to_string(const PseudoCond *p)
{
  string h, s = newstring("");
  unsigned char t1[30], t2[30];

  sprintf(t1, "%d", p->a);
  sprintf(t2, "%d", p->b);
  switch (p->type) {
  case Root:
    strapp(&s, ":root", NULL); break;
  case NthChild:
    strapp(&s, ":nth-child(", t1, "n+", t2, ")", NULL); break;
  case NthOfType:
    strapp(&s, ":nth-of-type(", t1, "n+", t2, ")", NULL); break;
  case Lang:
    strapp(&s, ":lang(", p->s, ")", NULL); break;
  case FirstChild:
    strapp(&s, ":first-child", NULL); break;
  case FirstOfType:
    strapp(&s, ":first-of-type", NULL); break;
  default:
    assert(!"Cannot happen");
  }
  if (p->next) {
    strapp(&s, (h = pseudos_to_string(p->next)), NULL);
    dispose(h);
  }
  return s;
}

/* attribs_to_string -- convert attribute selectors to a string */
static string attribs_to_string(const AttribCond *a)
{
  string h, s = newstring("");

  /* To do: escape illegal characters */
  switch (a->op) {
  case HasClass:
    strapp(&s, ".", a->value, NULL); break;
  case HasID:
    strapp(&s, "#", a->value, NULL); break;
  case Exists:
    strapp(&s, "[", a->name, "]", NULL); break;
  case Equals:
    strapp(&s, "[", a->name, "=\"",  a->value, "\"]", NULL); break;
  case Includes:
    strapp(&s, "[", a->name, "~=\"", a->value, "\"]", NULL); break;
  case StartsWith:
    strapp(&s, "[", a->name, "^=\"", a->value, "\"]", NULL); break;
  case EndsWidth:
    strapp(&s, "[", a->name, "$=\"", a->value, "\"]", NULL); break;
  case LangMatch:
    strapp(&s, "[", a->name, "|=\"", a->value, "\"]", NULL); break;
  case Contains:
    strapp(&s, "[", a->name, "*=\"", a->value, "\"]", NULL); break;
  default:
    assert(!"Cannot happen");
  }
  if (a->next) {
    strapp(&s, (h = attribs_to_string(a->next)), NULL);
    dispose(h);
  }
  return s;
}

/* selector_to_string -- convert selector back to a string */
EXPORT string selector_to_string(const Selector selector)
{
  string h, s = newstring("");

  strapp(&s, selector->name ? selector->name : (string)"*", NULL);
  if (selector->attribs) {
    h = attribs_to_string(selector->attribs);
    strapp(&s, h, NULL);
    dispose(h);
  }
  if (selector->pseudos) {
    h = pseudos_to_string(selector->pseudos);
    strapp(&s, h, NULL);
    dispose(h);
  }
  if (selector->context) {
    h = s;
    s = selector_to_string(selector->context);
    switch (selector->combinator) {
    case Descendant: strapp(&s, " ", h, NULL); break;
    case Child:      strapp(&s, " > ", h, NULL); break;
    case Adjacent:   strapp(&s, " + ", h, NULL); break;
    case Sibling:    strapp(&s, " ~ ", h, NULL); break;
    default: assert(!"Cannot happen");
    }
    dispose(h);
  }
  return s;
}

/* push_sel -- allocate memory for a new selector; initialize */
static void push_sel(Selector *selector, Combinator combinator)
{
  Selector h;

  new(h);
  h->name = NULL;
  h->attribs = NULL;
  h->pseudos = NULL;
  h->context = *selector;
  h->combinator = combinator;
  *selector = h;
}

/* isnmstart -- check if a character can start an identifier */
static Boolean isnmstart(unsigned int c)
{
  return ('a' <= c && c <= 'z')
    || ('A' <= c && c <= 'Z')
    || (c == '_')
    || (c >= '\200');
}

/* isnmchar -- check if a character can be inside an identifier */
static Boolean isnmchar(unsigned int c)
{
  return ('a' <= c && c <= 'z')
    || ('A' <= c && c <= 'Z')
    || ('0' <= c && c <= '9')
    || (c == '_')
    || (c == '-')
    || (c >= '\200');
}

/* parse_selector -- parse the selector in s */
EXPORT Selector parse_selector(const string selector)
{
  State saved_state, state = INIT;
  string s = selector;
  AttribCond *attsel;
  PseudoCond *pseudosel;
  Selector sel = NULL;
  int n, esc;

  /* To do: pseudos should be case-insensitive */

  push_sel(&sel, Descendant);

  while (*s) {
    switch (state) {
    case INIT:					/* Expect a simple sel */
      if (isspace(*s)) s++;
      else if (*s == '/') {s++; saved_state = INIT; state = SLASH;}
      else state = START_SIMPLE;
      break;
    case AFTER_SIMPLE:				/* Expect a combinator */
      if (isspace(*s)) {s++;}
      else if (*s == '/') {s++; saved_state = AFTER_SIMPLE; state=SLASH;}
      else if (*s == '+') {s++; push_sel(&sel, Adjacent); state = INIT;}
      else if (*s == '>') {s++; push_sel(&sel, Child); state = INIT;}
      else if (*s == '~') {s++; push_sel(&sel, Sibling); state = INIT;}
      else {push_sel(&sel, Descendant); state = START_SIMPLE;}
      break;
    case SLASH:					/* Expect a '*'  */
      if (*s == '*') {s++; state = COMMENT;}
      else errexit("Syntax error in selector at '/'\n");
      break;
    case COMMENT:				/* Inside comment */
      if (*s == '*') state = COMMENT_STAR;
      s++;
      break;
    case COMMENT_STAR:				/* Maybe end comment */
      if (*s == '/') state = saved_state;
      else if (*s != '*') state = COMMENT;
      s++;
      break;
    case START_SIMPLE:				/* Start simple sel */
      if (*s == '*') {s++; state = AFTER_TYPE;}	/* Universal selector */
      else if (*s == '.') {s++; state = START_CLASS;}
      else if (*s == '#') {s++; state = START_ID;}
      else if (*s == '[') {s++; state = START_ATTR;}
      else if (*s == ':') {s++; state = START_PSEUDO;}
      else if (*s == '\\') {sel->name = newstring(""); s++; state=ESC0;}
      else if (isnmstart(*s)) {sel->name = newstring(""); state = TYPE;}
      else  errexit("Syntax error at \"%c\"\n", *s);
      break;
    case TYPE:					/* Type selector */
      if (*s == '\\') {s++; state = ESC0;}
      else if (isnmchar(*s)) {strappc(&sel->name, *s); s++;}
      else state = AFTER_TYPE;
      break;
    case ESC0:				/* Just seen a '\' */
      if (isxdigit(*s)) {esc = 0; state = ESCAPE;}
      else {strappc(&sel->name, *s); s++; state = TYPE;}
      break;
    case ESCAPE:				/* Hex escape */
      if ('a' <= *s && *s <= 'f') {esc = 16 * esc + *s - 'a' + 10; s++;}
      else if ('A'<=*s && *s<='F') {esc = 16 * esc + *s - 'A' + 10; s++;}
      else if ('0'<=*s && *s<='9') {esc = 16 * esc + *s - '0'; s++;}
      else if (isspace(*s)) {strappc(&sel->name, esc); s++; state=TYPE;}
      else {strappc(&sel->name, esc); state = TYPE;}
      break;
    case AFTER_TYPE:				/* After a type sel */
      if (*s == '.') {s++; state = START_CLASS;}
      else if (*s == '#') {s++; state = START_ID;}
      else if (*s == '[') {s++; state = START_ATTR;}
      else if (*s == ':') {s++; state = START_PSEUDO;}
      else state = AFTER_SIMPLE;
      break;
    case START_CLASS:				/* Just seen a '.' */
      if (isnmstart(*s)) {
	new(attsel);
	attsel->op = HasClass;
	attsel->value = newstring("");
	attsel->next = sel->attribs;
	sel->attribs = attsel;
	strappc(&sel->attribs->value, *s);
	s++;
	state = CLASS;
      } else errexit("Expected letter instead of \"%c\" after \".\"",*s);
      break;
    case CLASS:					/* Inside class name */
      if (isnmchar(*s)) {strappc(&sel->attribs->value, *s); s++;}
      else state = AFTER_TYPE;
      break;
    case START_ID:				/* Just seen a '#' */
      if (isnmchar(*s)) {
	new(attsel);
	attsel->op = HasID;
	attsel->value = newstring("");
	attsel->next = sel->attribs;
	sel->attribs = attsel;
	strappc(&sel->attribs->value, *s);
	s++;
	state = ID;
      } else errexit("Expected letter instead of \"%c\" after \".\"",*s);
      break;
    case ID:					/* Inside name of ID */
      if (isnmchar(*s)) {strappc(&sel->attribs->value, *s); s++;}
      else state = AFTER_TYPE;
      break;
    case START_ATTR:				/* Just seen a '[' */
      if (isspace(*s)) s++;
      else if (*s == '/') {saved_state = START_ATTR; state = SLASH; s++;}
      else if (isnmstart(*s)) {
	new(attsel);
	attsel->name = newstring("");
	attsel->next = sel->attribs;
	sel->attribs = attsel;
	strappc(&sel->attribs->name, *s);