/* $Id: rcsview.c,v 1.11 2002/01/24 11:46:00 furuta Exp $ */

/*
 * Copyright (c) 2002 Atsushi Furuta.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <time.h>

/****************************************************************
 *
 * misc
 *
 */

void
error(char *s)
{
    fprintf(stderr, "rcslib: %s\n", s);
    exit(2);
    /*NOTREACHED*/
}

void *
emalloc(size_t size)
{
    void *ptr = malloc(size);

    if (ptr == NULL)
	error("emalloc");
    return ptr;
}

void *
erealloc(void *optr, size_t size)
{
    void *ptr = realloc(optr, size);

    if (ptr == NULL)
	error("erealloc");
    return ptr;
}

char *
estrdup(char *a)
{
    char *s = strdup(a);

    if (s == NULL)
	error("estrdup");
    return s;
}

/****************************************************************
 *
 * lexical analyzer
 *
 */

enum rcs_token_type {
    RCS_PARSE_EOF,
    RCS_PARSE_STRING, 
    RCS_PARSE_COLON, 
    RCS_PARSE_SEMICOLON, 
    RCS_PARSE_ID,
    RCS_PARSE_ID_head,
    RCS_PARSE_ID_branch,
    RCS_PARSE_ID_access,
    RCS_PARSE_ID_symbols,
    RCS_PARSE_ID_locks,
    RCS_PARSE_ID_strict,
    RCS_PARSE_ID_comment,
    RCS_PARSE_ID_expand,
    RCS_PARSE_ID_date,
    RCS_PARSE_ID_author,
    RCS_PARSE_ID_state,
    RCS_PARSE_ID_branches,
    RCS_PARSE_ID_next,
    RCS_PARSE_ID_desc,
    RCS_PARSE_ID_log,
    RCS_PARSE_ID_text,
};

#define RCS_PARSE_TOKEN_LIMIT 256

struct rcslex {
    FILE *fd;
    int lineno;
    enum rcs_token_type toktype;

    char nextid[RCS_PARSE_TOKEN_LIMIT];
    char *string;
    int nextchar;
};

#define rcs_parse_token_id_p(lex) (lex->toktype >= RCS_PARSE_ID)

static int
rcs_parse_token_num_p(struct rcslex *lex)
{
    char *s;

    if (!rcs_parse_token_id_p(lex))
	return 0;

    for (s = lex->nextid; *s != '\0'; s++) {
	if (!isdigit(*s) && *s != '.')
	    return 0;
    }
    return 1;
}

static int
rcs_parse_token_sym_p(struct rcslex *lex)
{
    char *s;

    if (!rcs_parse_token_id_p(lex))
	return 0;

    for (s = lex->nextid; *s != '\0'; s++) {
	if (*s == '.')
	    return 0;
    }
    return 1;
}

static int
rcs_parse_token_word_p(struct rcslex *lex)
{
    if (rcs_parse_token_id_p(lex))
	return 1;

    if (lex->toktype == RCS_PARSE_STRING)
	return 1;

    if (lex->toktype == RCS_PARSE_COLON)
	return 1;
    return 0;
}

struct rcs_parse_keyword {
    char *name;
    enum rcs_token_type type;
};

static struct rcs_parse_keyword rcs_parse_keywords[] = {
    {"head",     RCS_PARSE_ID_head},
    {"branch",   RCS_PARSE_ID_branch},
    {"access",   RCS_PARSE_ID_access},
    {"symbols",  RCS_PARSE_ID_symbols},
    {"locks",    RCS_PARSE_ID_locks},
    {"strict",   RCS_PARSE_ID_strict},
    {"comment",  RCS_PARSE_ID_comment},
    {"expand",   RCS_PARSE_ID_expand},
    {"date",     RCS_PARSE_ID_date},
    {"author",   RCS_PARSE_ID_author},
    {"state",    RCS_PARSE_ID_state},
    {"branches", RCS_PARSE_ID_branches},
    {"next",     RCS_PARSE_ID_next},
    {"desc",     RCS_PARSE_ID_desc},
    {"log",      RCS_PARSE_ID_log},
    {"text",     RCS_PARSE_ID_text},
    {NULL,       RCS_PARSE_ID},
};

static int
rcs_parse_token_newphrase_p(struct rcslex *lex)
{
    int i;

    if (!rcs_parse_token_id_p(lex))
	return 0;

    if (rcs_parse_token_num_p(lex))
	return 0;

    for (i = 0; rcs_parse_keywords[i].name != NULL; i++) {
	if (strcmp(rcs_parse_keywords[i].name, lex->nextid))
	    return 0;
    }
    return 1;
}

#define RCS_PARSE_STRING_SIZE_INIT 32
#define RCS_PARSE_STRING_SIZE_REINIT(size) (((size)*4)/3)

/*  should not be used ISO 8859/1 (Latin-1) specific chars */
#define RCS_PARSE_ID_CHARS "[]!\"#%&'()*+./\\`{|}~_^-"
#define RCS_ID_CHAR_P(c) \
	(isalnum(c) || strchr(RCS_PARSE_ID_CHARS, (c)) != NULL)

static void
rcs_parse_get_token(struct rcslex *lex)
{
    /* skip space */

    while (isspace(lex->nextchar)) {
	if (lex->nextchar == '\n')
	    lex->lineno++;
	lex->nextchar = getc(lex->fd);
    }

    if (lex->nextchar == EOF) {
	lex->toktype = RCS_PARSE_EOF;
    }
    else if (lex->nextchar == '@') {
	int i, csize, c;
	char *s;
	lex->toktype = RCS_PARSE_STRING;

	csize = RCS_PARSE_STRING_SIZE_INIT;
	s = emalloc(csize);

	i = 0;
	while ((c = getc(lex->fd)) != EOF) {
	    if (c == '\n')
		lex->lineno++;

	    if (i >= csize) {
		csize = RCS_PARSE_STRING_SIZE_REINIT(csize);
		s = erealloc(s, csize);
	    }

	    if (c == '@') {
		c = getc(lex->fd);

		if (c != '@') {
		    lex->nextchar = c;
		    break;
		}
	    }
	    s[i++] = c;
	}
	s[i] = '\0';
	lex->string = s;
    }
    else if (lex->nextchar == ':') {
	lex->toktype = RCS_PARSE_COLON;
	lex->nextchar = getc(lex->fd);
    }
    else if (lex->nextchar == ';') {
	lex->toktype = RCS_PARSE_SEMICOLON;
	lex->nextchar = getc(lex->fd);
    }
    else if (RCS_ID_CHAR_P(lex->nextchar)) {
	int i = 0;

	do {
	    lex->nextid[i++] = lex->nextchar;
	    lex->nextchar = getc(lex->fd);
	    if (i >= RCS_PARSE_TOKEN_LIMIT-2) {
				/* XXX errror */
		break;
	    }
	} while(RCS_ID_CHAR_P(lex->nextchar));

	lex->nextid[i] = '\0';

	lex->toktype = RCS_PARSE_ID;
	for (i = 0; rcs_parse_keywords[i].name != NULL; i++) {
	    if (strcmp(rcs_parse_keywords[i].name, lex->nextid) == 0) {
		lex->toktype = rcs_parse_keywords[i].type;
		break;
	    }
	}
    }
    else {
	error("unknown token");
    }
}

static void
rcs_parse_semicolon(struct rcslex *lex)
{
    if (lex->toktype != RCS_PARSE_SEMICOLON)
	error("`;' required");
    rcs_parse_get_token(lex);
}

static void
rcs_parse_colon(struct rcslex *lex)
{
    if (lex->toktype != RCS_PARSE_COLON)
	error("`:' required");
    rcs_parse_get_token(lex);
}

static void
rcs_parse_token_expect(struct rcslex *lex, enum rcs_token_type exp)
{
    if (!rcs_parse_token_id_p(lex))
	error("Syntax error");

    if (exp != lex->toktype)
	error("Unexpected token");
	/* error("Unexpected token %s: %s required" rcs_parse_next_token exp); */
    rcs_parse_get_token(lex);
}

struct rcslex *
rcs_lex_create(FILE *fd)
{
    struct rcslex *lex = emalloc(sizeof (struct rcslex));

    lex->fd = fd;
    lex->toktype = RCS_PARSE_EOF;
    lex->nextid[0] = '\n';
    lex->string = NULL;
    lex->lineno = 1;
    lex->nextchar = getc(fd);

    return lex;
}

/****************************************************************
 *
 * lists
 *
 */

struct link {
    void *obj;
    struct link *next;
};

struct list {
    struct link *first;
    struct link *last;
};

void
list_foreach(struct list *list, void *ptr, void (*func)(void*, void*))
{
    struct link *link;

    for (link = list->first; link != NULL; link = link->next)
	(*func)(ptr, link->obj);
}

struct list *
list_create_empty()
{
    struct list *list = emalloc(sizeof (struct list));

    list->first = NULL;
    list->last = NULL;
    return list;
}

void
list_insert_head(struct list *list, void *obj)
{
    struct link *link = emalloc(sizeof (struct link));

    link->obj = obj;
    link->next = list->first;
    if (list->first == NULL)
	list->last = link;
    list->first = link;
}

void
list_append_tail(struct list *list, void *obj)
{
    struct link *link = emalloc(sizeof (struct link));

    link->obj = obj;
    link->next = NULL;
    if (list->first != NULL)
	list->last->next = link;
    else
	list->first = link;
    list->last = link;
}

/****************************************************************
 *
 * Hash
 *
 */

#define HASH_SIZE_INIT  127
#define HASH_SIZE_REINIT(old) ((old)*6+1)

struct hashent {
    char *key;
    void *obj;
    struct hashent *next;
};

struct hash {
    int size;
    int count;
    struct hashent **ent;
};

struct hash *
hash_create()
{
    struct hash *hash = emalloc(sizeof (struct hash));
    struct hashent **ent;
    int i;

    hash->size = HASH_SIZE_INIT;
    hash->ent  = ent = emalloc(sizeof (struct hashent*) * hash->size);
    for (i = 0; i < hash->size; i++)
	ent[i] = NULL;
    hash->count = 0;
    return hash;
}

static int
hashval(char *key, int size)
{
    int h = 0;
    char *s;

    for (s = key; *s != '\0'; s++) {
	h = ((h*3) + 269 + (int) *s) % size;
    }

    return h;
}

struct hash *
hash_reinit(struct hash *hash)
{
    struct hashent **oldent = hash->ent;
    struct hashent **ent;
    struct hashent *next;
    struct hashent *prev;
    int oldsize = hash->size;
    int i;
    int hval;

    hash->size = HASH_SIZE_REINIT(oldsize);
    hash->ent  = ent = emalloc(sizeof (struct hashent*) * hash->size);
    for (i = 0; i < hash->size; i++)
	ent[i] = NULL;

    for (i = 0; i < oldsize; i++) {
	for (prev = oldent[i]; prev != NULL; prev = next) {
	    next = prev->next;
	    hval = hashval(prev->key, hash->size);
	    prev->next = hash->ent[hval];
	    hash->ent[hval] = prev;
	}
    }
    free(oldent);

    return hash;
}

static struct hashent *
hashent_create(struct hash *hash, char *key, int hval)
{
    struct hashent *ent = emalloc(sizeof (struct hashent));
    ent->key = estrdup(key);
    ent->obj = NULL;
    ent->next = hash->ent[hval];
    hash->ent[hval] = ent;
    hash->count++;

    if (hash->count >= hash->size) {
	hash_reinit(hash);
    }
    return ent;
}

#define ENTRY_CREATE 1
#define ENTRY_NOCREATE 0

static struct hashent *
hash_lookup(struct hash *hash, char *key, int crflag)
{
    int hval = hashval(key, hash->size);
    struct hashent *ent;

    for (ent = hash->ent[hval]; ent != NULL; ent = ent->next) {
	if (strcmp(ent->key, key) == 0)
	    return ent;
    }
    if (crflag == ENTRY_CREATE)
	ent = hashent_create(hash, key, hval); 

    return ent;
}

static void
hash_foreach(struct hash *hash, void *ptr,
	     void (*func)(void*, struct hashent *))
{
    int i;
    struct hashent *ent;

    for (i = 0; i < hash->size; i++) {
	for (ent = hash->ent[i]; ent != NULL; ent = ent->next) {
	    (*func)(ptr, ent);
	}
    }
}

/****************************************************************
 *
 * revision number
 *
 */

struct rcsnum {
    int level;
    int *nums;
    char *str;
};

static struct rcsnum *
rcsnum_create(char *rev)
{
    char *s;
    char *t;
    int count = 1;
    int first = 1;
    int i;
    struct rcsnum *revs;

    /* check lexical validity of revision string */
    for (s = rev; *s != '\0'; s++) {
	if (*s == '.') {
	    if (first)		/* empty label */
		return NULL;
	    count++;
	    first = 1;
	}
	else if (isdigit(*s)) {
	    if (first && *s == '0') { /* leading zero */
		/* it is valid only if single zero */
		if (s[1] != '.' && s[1] != '\0')
		    return NULL;
	    }
	    first = 0;
	}
	else {
	    return NULL;
	}
    }

    /* object allocate and setup */
    revs = emalloc(sizeof (struct rcsnum));
    revs->level = count;
    revs->nums  = emalloc(sizeof (int) * count);
    revs->str   = estrdup(rev);

    s = rev;
    for (i = 0; i < count; i++) {
	revs->nums[i] = (int)strtol(s, &t, 10);	/* XXX */
	s = t+1;
    }

    return revs;
}

static int
rcsnum_trunk_p(struct rcsnum *rev)
{
    return rev->level == 2;
}

static int
rcsnum_ancestor_p(struct rcsnum *p, struct rcsnum *r)
{
    int i;

    if (p->level > r->level)
	return 0;

    if (rcsnum_trunk_p(p)) {
	if (p->nums[0] < r->nums[0])
	    return 1;
	else if (p->nums[0] == r->nums[0])
	    return p->nums[1] <= r->nums[1];
	return 0;
    }

    for (i = 0; i < p->level-1; i++) {
	if (p->nums[i] != r->nums[i])
	    return 0;
    }
    return p->nums[i] <= r->nums[i];
}

/****************************************************************
 *
 * rcsfile parser
 *
 */

struct rcsdate {
    char *str;
    struct tm tm_;
#if 0				/* XXX */
    time_t time;
#endif
};

struct rcslock {
    char *id;
    struct rcsnum *rev;
};

#define LNKTYPE_NONE 0
#define LNKTYPE_HEAD 1
#define LNKTYPE_BRANCH 2
#define LNKTYPE_NEXT 3

struct rcsrev {
    struct rcsnum *num;
    struct rcsrev *newest;
    struct rcsrev *parent;
    struct rcsrev *oldest;
    struct rcsrev *next;
    struct rcsrev *prev;
    struct rcsrev *old;
    struct rcsrev *new;
    struct rcsdate *date;
    int lnktype;
    char *author;
    char *state;
    struct list *branches;
    char *log;
    char *text;
};

struct rcsfile {
    struct rcsrev *head;
    struct rcsrev *branch;	/* default branch */
    struct hash *revisions;
    struct hash *symbols;
    struct list *access;
    struct list *locks;
    int lockstrict;		/* true if "strict" exists */
    struct rcsrev *root;	/* root revision; provably 1.1 */
    char *comment;
    char *expand;
    char *desc;
};

struct rcsio {
    char *fname;
    FILE *infd;
    FILE *outfd;
    struct rcsfile *rcs;
    struct rcslex *lex;
};

struct rcsdate *
rcs_parse_date(char *str)
{
    struct rcsdate *date;
    struct tm tm;

    /* Y.mm.dd.hh.mm.ss */
    if (sscanf(str, "%d.%d.%d.%d.%d.%d",
	   &tm.tm_year,		/* if ?? then 19?? */
	   &tm.tm_mon,		/* 01-12, should be -1 */
	   &tm.tm_mday,		/* 01-31 */
	   &tm.tm_hour,		/* 00-23 */
	   &tm.tm_min,		/* 00-59 */
	   &tm.tm_sec		/* 00-60 */
	) < 6) {
	return NULL;
    }

    if (tm.tm_year < 100)
	tm.tm_year += 1900;
    tm.tm_mon--;

    date = emalloc(sizeof(struct rcsdate));
    date->str = str;
    date->tm_ = tm;
    return date;
}

struct rcsrev *
rcs_get_revision(struct rcsfile *rcs, char *num, int crflag)
{
    struct hashent *ent;
    struct rcsrev *rev;

    ent = hash_lookup(rcs->revisions, num, crflag);
    if (ent == NULL)
	return NULL;

    if (ent->obj != NULL)
	return ent->obj;

    ent->obj = rev = emalloc(sizeof (struct rcsrev));

    rev->num    = rcsnum_create(num);
    rev->newest = NULL;
    rev->oldest = NULL;
    rev->parent = NULL;
    rev->next   = NULL;
    rev->old    = NULL;
    rev->new    = NULL;
    rev->date   = NULL;
    rev->author = NULL;
    rev->state  = NULL;
    rev->log    = NULL;
    rev->text   = NULL;
    rev->branches = list_create_empty();
    rev->lnktype = LNKTYPE_NONE;

    return rev;
}

void
rcs_parse_newphrase(struct rcslex *lex)
{
    /* id { id | num | string | : }* ; */

    rcs_parse_get_token(lex);
    while (rcs_parse_token_word_p(lex))
	rcs_parse_get_token(lex);
    rcs_parse_semicolon(lex);
}

void
rcs_parse_admin(struct rcsio *io)
{
    struct rcslex *lex = io->lex;
    struct rcsfile *rcs = io->rcs;

    rcs->revisions = hash_create();

    /* head {num}; */
    {
	struct rcsrev *head = NULL;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_head);
	if (rcs_parse_token_num_p(lex)) {
	    head = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);
	    rcs_parse_get_token(lex);

	    if (rcsnum_trunk_p(head->num))
		head->newest = head;

	    head->lnktype = LNKTYPE_HEAD;
	}
	rcs_parse_semicolon(lex);
	rcs->head = head;
    }

    /* { branch {num}; } */
    if (rcs_parse_token_id_p(lex) && lex->toktype == RCS_PARSE_ID_branch) {
	struct rcsrev *branch = NULL;

	rcs_parse_get_token(lex);
	if (rcs_parse_token_num_p(lex)) {
	    branch = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
	rcs->branch = branch;
    }
    else {
	rcs->branch = NULL;
    }

    /* access {id}*; */
    {
	struct list *aclist = list_create_empty();

	rcs_parse_token_expect(lex, RCS_PARSE_ID_access);
	while (rcs_parse_token_id_p(lex)) {
	    list_append_tail(aclist, estrdup(lex->nextid));
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
	rcs->access = aclist;
    }

    /* symbols {sym : num}*; */
    {
	char *sym;
	char *num;
	struct hashent *ent;

	rcs->symbols = hash_create();
	rcs_parse_token_expect(lex, RCS_PARSE_ID_symbols);
	while (rcs_parse_token_sym_p(lex)) {
	    /*
	     * store a revision number as string instead of struct rcsnum
	     * because RCS file may have a symbol which points
	     * a revision which does not exist, such as 1.4.0.2
	     */
	    sym = estrdup(lex->nextid);
	    rcs_parse_get_token(lex);
	    rcs_parse_colon(lex);
	    if (!rcs_parse_token_num_p(lex))
		error("num required");
	    num = estrdup(lex->nextid);
	    ent = hash_lookup(rcs->symbols, sym, ENTRY_CREATE);
	    if (ent->obj != NULL)
		error("symbol redefined");
	    ent->obj = num;
	    rcs_parse_get_token(lex);
	    free(sym);
	}
	rcs_parse_semicolon(lex);
    }

    /* locks {id : num}*; { strict ; } */
    {
	char *id;
	struct rcsnum *num;
	struct list *locklist = list_create_empty();
	struct rcslock *lock;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_locks);
	while (rcs_parse_token_id_p(lex)) {
	    id = estrdup(lex->nextid);
	    rcs_parse_get_token(lex);
	    rcs_parse_colon(lex);
	    if (!rcs_parse_token_num_p(lex))
		error("num required");
	    num = rcsnum_create(lex->nextid);
	    lock = emalloc(sizeof(struct rcslock));
	    lock->id = id;
	    lock->rev = num;
	    list_append_tail(locklist, lock);
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
	rcs->locks = locklist;

	if (rcs_parse_token_id_p(lex) && lex->toktype == RCS_PARSE_ID_strict) {
	    rcs_parse_get_token(lex);
	    rcs_parse_semicolon(lex);
	    rcs->lockstrict = 1;
	}
	else {
	    rcs->lockstrict = 0;
	}
    }

    /* { comment {string}; } */
    rcs->comment = NULL;
    if (rcs_parse_token_id_p(lex) && lex->toktype == RCS_PARSE_ID_comment) {
	rcs_parse_get_token(lex);
	if (lex->toktype == RCS_PARSE_STRING) {
	    rcs->comment = lex->string;
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
    }

    /* { expand {string}; } */
    rcs->expand = NULL;
    if (rcs_parse_token_id_p(lex) && lex->toktype == RCS_PARSE_ID_expand) {
	rcs_parse_get_token(lex);
	if (lex->toktype == RCS_PARSE_STRING) {
	    rcs->expand = lex->string;
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
    }

    /* { newphrase }* */
    while (rcs_parse_token_newphrase_p(lex)) {
	rcs_parse_newphrase(lex);
    }
}

void
rcs_parse_delta(struct rcsio *io)
{
    struct rcslex *lex = io->lex;
    struct rcsfile *rcs = io->rcs;
    struct rcsrev *rev = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);

    rcs_parse_get_token(lex);

    /* date num; */
    {
	struct rcsdate *date;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_date);
	if (!rcs_parse_token_num_p(lex))
	    error("Date required");

	date = rcs_parse_date(lex->nextid);
	rcs_parse_get_token(lex);
	rcs_parse_semicolon(lex);
	rev->date = date;
    }

    /* author id; */
    {
	char *author;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_author);
	if (!rcs_parse_token_id_p(lex))
	    error("Author required");
	author = estrdup(lex->nextid);
	rcs_parse_get_token(lex);
	rcs_parse_semicolon(lex);
	rev->author = author;
    }

    /* state {id}; */
    {
	char *state = NULL;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_state);
	if (rcs_parse_token_id_p(lex)) {
	    state = estrdup(lex->nextid);
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
	rev->state = state;
    }

    /* branches {num}*; */
    {
	struct list *branches = list_create_empty();
	struct rcsrev *branch;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_branches);
	while (rcs_parse_token_num_p(lex)) {
	    branch = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);
	    list_append_tail(branches, branch);
	    branch->lnktype = LNKTYPE_BRANCH;
	    branch->parent = rev;
	    branch->oldest = branch;
	    rcs_parse_get_token(lex);
	}
	rcs_parse_semicolon(lex);
	rev->branches = branches;
    }

    /* next {num}; */
    {
	struct rcsrev *next = NULL;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_next);
	if (rcs_parse_token_num_p(lex)) {
	    next = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);
	    rcs_parse_get_token(lex);

	    next->lnktype = LNKTYPE_NEXT;
	    if (rcsnum_trunk_p(rev->num)) {
		next->new    = rev;
		next->newest = rev->newest;
	    }
	    else {
		next->old    = rev;
		next->oldest = rev->oldest;
	    }
	    next->prev = rev;
	}
	else {
	    /* no next */
	    struct rcsrev *r;

	    if (rcsnum_trunk_p(rev->num)) {
		rcs->root = rev;
		for (r = rev; r != NULL; r = r->new)
		    r->oldest = rev;
	    }
	    else {
		for (r = rev; r != NULL; r = r->old)
		    r->newest = rev;
	    }
	}
	rcs_parse_semicolon(lex);

	rev->next = next;
	if (rcsnum_trunk_p(rev->num))
	    rev->old = next;
	else
	    rev->new = next;
    }

    /* { newphrase }* */
    while (rcs_parse_token_newphrase_p(lex))
	rcs_parse_newphrase(lex);
}

void
rcs_parse_deltatext(struct rcsio *io)
{
    struct rcslex *lex = io->lex;
    struct rcsfile *rcs = io->rcs;
    struct rcsrev *rev = rcs_get_revision(rcs, lex->nextid, ENTRY_CREATE);

    rcs_parse_get_token(lex);

    /* log string */
    {
	char *log;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_log);
	if (lex->toktype != RCS_PARSE_STRING)
	    error("Log string required");
	log = lex->string;
	rcs_parse_get_token(lex);
	rev->log = log;
    }

    /* { newphrase }* */
    while (rcs_parse_token_newphrase_p(lex))
	rcs_parse_newphrase(lex);

    /* text string */
    {
	char *text;

	rcs_parse_token_expect(lex, RCS_PARSE_ID_text);
	if (lex->toktype != RCS_PARSE_STRING)
	    error("Text string required");
	text = lex->string;
	rcs_parse_get_token(lex);
	rev->text = text;
    }
}

static void
rcs_parse_check_sub(void *ptr, struct hashent *ent)
{
    struct rcsrev *rev = ent->obj;

    if (rev->lnktype == LNKTYPE_NONE)
	error("Revision is not linked any node");
    if (rev->text == NULL)
	error("Revision has no text");
}

void
rcs_parse_check(struct rcsfile *rcs)
{
    struct hash *revs = rcs->revisions;

    hash_foreach(revs, NULL, rcs_parse_check_sub);
}

void
rcs_parse_rcstext(struct rcsio *io)
{
    struct rcslex *lex = io->lex;
    struct rcsfile *rcs = io->rcs;

    rcs_parse_get_token(lex);
    rcs_parse_admin(io);

    while (rcs_parse_token_num_p(lex))
	rcs_parse_delta(io);

    /* desc string */
    rcs_parse_token_expect(lex, RCS_PARSE_ID_desc);
    if (lex->toktype != RCS_PARSE_STRING)
	error("Description string required");
    rcs->desc = lex->string;
    rcs_parse_get_token(lex);

    while (rcs_parse_token_num_p(lex))
	rcs_parse_deltatext(io);

    if (lex->toktype != RCS_PARSE_EOF)
	error("garbage found at end of file");
    rcs_parse_check(rcs);
}

struct rcsio *
rcs_rcstext_readin(char *fname)
{
    struct rcsio *io;

    io = emalloc(sizeof (struct rcsio));
    io->fname = estrdup(fname);
    io->outfd = NULL;
    io->infd = fopen(io->fname, "r");
    if (io->infd == NULL)
	goto fail1;
    io->lex = rcs_lex_create(io->infd);
    io->rcs = emalloc(sizeof (struct rcsfile));
    rcs_parse_rcstext(io);
    if (io->rcs == NULL)
	goto fail2;
    fclose(io->infd);
    io->infd = NULL;
    return io;

 fail2:
    fclose(io->infd);
 fail1:
    free(io->fname);
    free(io);
    return NULL;
}

/****************************************************************
 *
 * rcsfile accessor
 *
 */

struct rcsrev *
rcs_get_head(struct rcsfile *rcs)
{
    return rcs->head;
}

struct rcsrev *
rcs_get_default_branch(struct rcsfile *rcs)
{
    return rcs->branch;
}

struct rcsrev *
rcs_get_root(struct rcsfile *rcs)
{
    return rcs->root;
}

int
rcs_strict_p(struct rcsfile *rcs)
{
    return rcs->lockstrict;
}

struct rcslock_frame {
    void (*func)(void*, char *id, struct rcsnum *rev);
    void *ptr;
};

static void
rcs_locker_sub(void *ptr, void *obj)
{
    struct rcslock_frame *e = ptr;
    struct rcslock *lock = obj;
    (*e->func)(e->ptr, lock->id, lock->rev);
}

void
rcs_locker_foreach(struct rcsfile *rcs, void *ptr,
		   void (*func)(void*, char *id, struct rcsnum *rev))
{
    struct rcslock_frame e;

    e.func = func;
    e.ptr  = ptr;
    list_foreach(rcs->locks, &e, rcs_locker_sub);
}

char *
rcs_get_comment(struct rcsfile *rcs)
{
    return rcs->comment;
}

char *
rcs_get_expand(struct rcsfile *rcs)
{
    return rcs->expand;
}

char *
rcs_get_desc(struct rcsfile *rcs)
{
    return rcs->desc;
}

struct rcs_access_frame {
    void (*func)(void*, char *id);
    void *ptr;
};

static void
rcs_access_sub(void *ptr, void *obj)
{
    struct rcs_access_frame *e = ptr;
    char *id = obj;
    (*e->func)(e->ptr, id);
}

void
rcs_access_foreach(struct rcsfile *rcs, void *ptr,
		   void (*func)(void*, char *id))
{
    struct rcs_access_frame e;

    e.func = func;
    e.ptr  = ptr;
    list_foreach(rcs->access, &e, rcs_access_sub);
}

struct rcs_symbol_frame {
    void (*func)(void *ptr, char *sym, char *revnum);
    void *ptr;
};

static void
rcs_symbol_sub(void *ptr, struct hashent *ent)
{
    struct rcs_symbol_frame *e = ptr;
    char *revnum = ent->obj;

    (*e->func)(e->ptr, ent->key, revnum);
}

void
rcs_symbol_foreach(struct rcsfile *rcs, void *ptr,
		   void (*func)(void*, char *sym, char *revnum))
{
    struct rcs_symbol_frame e;
    e.ptr = ptr;
    e.func = func;
    hash_foreach(rcs->symbols, &e, rcs_symbol_sub);
}

/***/
struct rcsnum *
rcsrev_get_num(struct rcsrev *rev)
{
    return rev->num;
}

struct rcsrev *
rcsrev_get_newest(struct rcsrev *rev)
{
    return rev->newest;
}

struct rcsrev *
rcsrev_get_oldest(struct rcsrev *rev)
{
    return rev->oldest;
}

struct rcsrev *
rcsrev_get_parent(struct rcsrev *rev)
{
    return rev->parent;
}

struct rcsrev *
rcsrev_get_nextlink(struct rcsrev *rev)
{
    return rev->next;
}

struct rcsrev *
rcsrev_get_old(struct rcsrev *rev)
{
    return rev->old;
}

struct rcsrev *
rcsrev_get_new(struct rcsrev *rev)
{
    return rev->new;
}

struct rcsdate *
rcsrev_get_date(struct rcsrev *rev)
{
    return rev->date;
}

int
rcsrev_get_linktype(struct rcsrev *rev)
{
    return rev->lnktype;
}

char *
rcsrev_get_author(struct rcsrev *rev)
{
    return rev->author;
}

char *
rcsrev_get_state(struct rcsrev *rev)
{
    return rev->state;
}

char *
rcsrev_get_log(struct rcsrev *rev)
{
    return rev->log;
}

char *
rcsrev_get_text(struct rcsrev *rev)
{
    return rev->text;
}

struct rcsrev_branch_frame {
    void (*func)(void *ptr, struct rcsrev *rev);
    void *ptr;
};

static void
rcsrev_branch_sub(void *ptr, void *obj)
{
    struct rcsrev_branch_frame *e = ptr;
    struct rcsrev *rev = obj;

    (*e->func)(e->ptr, rev);
}

void
rcsrev_branch_foreach(struct rcsrev *rev, void *ptr,
		      void (*func)(void*, struct rcsrev *branch))
{
    struct rcsrev_branch_frame e;
    e.ptr = ptr;
    e.func = func;
    list_foreach(rev->branches, &e, rcsrev_branch_sub);
}

struct rcsrev *
rcsrev_find_branch(struct rcsrev *rev, struct rcsrev *targ)
{
    struct rcsrev *b;
    struct link *l;

    for (l = rev->branches->first; l != NULL; l = l->next) {
	b = l->obj;
	if (rcsnum_ancestor_p(b->num, targ->num))
	    break;
    }
    if (l == NULL)
	return NULL;
    return b;
}

/****************************************************************
 *
 * rcs text edit
 *
 */

struct rcsdelta {
    int editcmd;		/* 'a' or 'd' or EOF */
    int lineno;
    int lines;
    char *text;
};

static char *
rcsedit_skip_line(char *text)
{
    while (*text != '\0') {
	if (*text == '\n')
	    return text+1;
	text++;
    }
    return NULL;
}

struct rcsdelta *
rcsedit_parse_delta(char *delta)
{
    char *s;
    int line;
    int num;
    int i;
    int j;
    int count;
    struct rcsdelta *cmd;

    /* prescan; to count the number of edit command */
    count = 0;
    s = delta;
    while (*s != '\0') {
	if (*s == 'a') {
	    count++;
	    sscanf(s+1, "%d %d", &line, &num);
	    for (i = 0; i < num+1; i++)
		s = rcsedit_skip_line(s);
	}
	else if (*s == 'd') {
	    count++;
	    sscanf(s+1, "%d %d", &line, &num);
	    s = rcsedit_skip_line(s);
	}
	else {
	    return NULL;
	}
    }

    cmd = emalloc(sizeof (struct rcsdelta) * (count+1));
    s = delta;
    for (j = 0; j < count; j++) {
	cmd[j].editcmd = *s;
	sscanf(s+1, "%d %d", &line, &num);
	cmd[j].lineno = line;
	cmd[j].lines  = num;
	if (*s == 'a') {
	    s = rcsedit_skip_line(s);
	    cmd[j].text = s;
	    for (i = 0; i < num; i++)
		s = rcsedit_skip_line(s);
	}
	else if (*s == 'd') {
	    s = rcsedit_skip_line(s);
	    cmd[j].text = NULL;
	}
    }
    cmd[j].editcmd = EOF;
    cmd[j].lineno = 0;
    cmd[j].lines = 0;
    cmd[j].text = NULL;
    return cmd;
}

struct rcslinfo {
    char *text;
    struct rcsrev *birth;	/* first revision it springs into  */
    struct list *dead;		/* first revisions it is gone away;
				 * next of last revisions it is alive */
    struct rcslinfo *prev;
    struct rcslinfo *next;
};

struct rcslinfo *
rcsedit_info_create(char *text, struct rcsrev *rev)
{
    struct rcslinfo *info;

    info = emalloc(sizeof (struct rcslinfo));
    info->text = text;
    info->prev = NULL;
    info->next = NULL;
    info->birth = NULL;
    info->dead  = list_create_empty();
    /* 1.1 -- 1.2 -- 1.3 */
    if (rcsnum_trunk_p(rev->num)) {
	if (rev->prev != NULL)
	    list_append_tail(info->dead, rev->prev);
    }
    else
	info->birth = rev;
    return info;
}

void
rcsedit_info_link(struct rcslinfo *prev, struct rcslinfo *next)
{
    prev->next = next;
    next->prev = prev;
}

void
rcsedit_info_terminate(struct rcslinfo *info, struct rcsrev *rev)
{
    if (rcsnum_trunk_p(rev->num))
	info->birth = rev;
    else
	list_append_tail(info->dead, rev);
}

#define RCS_PRINT_STYLE_NONE 0
#define RCS_PRINT_STYLE_ANNO 1

void
rcsedit_info_print(struct rcslinfo *info, FILE *fd, int style)
{
    char *s = info->text;
    static char* mon[] = {
	"Jan", "Feb", "Mar", "Apr", "May", "Jun",
	"Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
    };

    if (style == RCS_PRINT_STYLE_ANNO) {
	/* 123456789012345678901234 */
	/* 1.1          (furuta   04-Jun-01): ....*/

	struct rcsrev *rev = info->birth;
	struct rcsdate *dt = rev->date;
	struct tm *tp = &dt->tm_;
	fprintf(fd, "%-12s (%-8s %02d-%s-%02d): ",
		rev->num->str, rev->author, 
		tp->tm_mday, mon[tp->tm_mon], tp->tm_year%100
	    );
    }

    while (*s != '\n') {
	putc(*s, fd);
	s++;
    }
    putc('\n', fd);
}

/*
 * ||------------            ----------------||
 *               ^gap1       ^gap2           ^end
 * both edges have sentinel
 *
 */
struct rcslines {
    int gap1;
    int gap2;
    int end;
    struct rcslinfo **info;
};

void
rcsedit_lines_print(struct rcslines *ls, FILE *fd, int style)
{
    int i;

    for (i = 1; i < ls->gap1; i++)
	rcsedit_info_print(ls->info[i], fd, style);

    for (i = ls->gap2; i < ls->end; i++)
	rcsedit_info_print(ls->info[i], fd, style);
}

static void
rcsedit_print_lifetime(struct rcslinfo *ls, FILE *fd)
{
    struct link *l;
    struct rcsrev *r;
    struct rcsnum *num;

    num = rcsrev_get_num(ls->birth);
    fprintf(fd, "%s", num->str);

    for (l = ls->dead->first; l != NULL; l = l->next) {
	r = l->obj;
	num = rcsrev_get_num(r);
	fprintf(fd, ",%s", num->str);
    }
}

static int
rcsedit_comp_lifetime(struct rcslinfo *ls1, struct rcslinfo *ls2)
{
    struct link *l1;
    struct link *l2;
    struct rcsrev *r1;
    struct rcsrev *r2;

    if (ls1->birth != ls2->birth)
	return 0;

    for (l1 = ls1->dead->first, l2 = ls2->dead->first; l1 != NULL;
	 l1 = l1->next, l2 = l2->next) {

	if (l2 == NULL)
	    return 0;
	r1 = l1->obj;
	r2 = l2->obj;
	if (r1 != r2)
	    return 0;
    }

    if (l2 != NULL)
	return 0;

    return 1;
}

void
rcsedit_union_print(struct rcslines *ls, FILE *fd)
{
    struct rcslinfo *info = ls->info[0];
    struct rcslinfo *k;
    struct rcslinfo *l;
    struct rcslinfo *end = ls->info[ls->end];
    int count;

    for (info = info->next; info != end; info = l) {
	count = 1;
	for (l = info->next; l != end; l = l->next) {
	    if (rcsedit_comp_lifetime(info, l) == 0)
		break;
	    count++;
	}
	fprintf(fd, "%d ", count);
	rcsedit_print_lifetime(info, fd);
	fprintf(fd, "\n");

	for (k = info; k != l; k = k->next)
	    rcsedit_info_print(k, fd, RCS_PRINT_STYLE_NONE);
    }
}

/*
 * both side edges have NULL link; it is responsible for caller
 * to link them.
 */
void
rcsedit_place_text(struct rcslinfo **info, char *s, struct rcsrev *rev,
		   int lines)
{
    int i;

    info[0] = rcsedit_info_create(s, rev);
    s = rcsedit_skip_line(s);
    for (i = 1; i < lines; i++) {
	info[i] = rcsedit_info_create(s, rev);
	s = rcsedit_skip_line(s);
	rcsedit_info_link(info[i-1], info[i]);
    }
}

/* rev must be head; rev->text is plain text rather than edit command */
struct rcslines *
rcsedit_lines_create(struct rcsrev *rev)
{
    char *s = rev->text;
    int lines = 0;
    int alloc;
    struct rcslines *ls;

    while (*s != '\0') {
	s = rcsedit_skip_line(s);
	lines++;
    }

    alloc = ((lines+2)/3)*4;	/* (with both sentinels) * 3/4 */
    ls = emalloc(sizeof (struct rcslines));
    ls->info = emalloc(sizeof (struct rcslinfo *) * alloc);

    rcsedit_place_text(&ls->info[1], rev->text, rev, lines);

    /* make sentinels */
    ls->info[0] = rcsedit_info_create(NULL, rev);
    ls->info[alloc-1] = rcsedit_info_create(NULL, rev);

    rcsedit_info_link(ls->info[0], ls->info[1]);
    rcsedit_info_link(ls->info[lines], ls->info[alloc-1]);

    ls->gap1 = lines+1;
    ls->gap2 = ls->end = alloc-1;

    return ls;
}

struct rcslines *
rcsedit_lines_copy(struct rcslines *ls)
{
    struct rcslines *ls2;
    int len2 = (ls->end - ls->gap2);
    int lines = len2 + (ls->gap1 - 1);
    int alloc = ((lines+2)/3)*4;	/* (with both sentinels) * 3/4 */

    ls2 = emalloc(sizeof (struct rcslines));
    ls2->info = emalloc(sizeof (struct rcslinfo *) * alloc);
    ls2->end = alloc-1;
    ls2->gap1 = ls->gap1;
    ls2->gap2 = ls2->end - len2;

    memmove(ls2->info, ls->info, sizeof (struct rcslinfo *) * ls->gap1);
    memmove(&ls2->info[ls2->gap2], &ls->info[ls->gap2],
	    sizeof (struct rcslinfo *) * (len2+1));

    return ls2;
}

void
rcsedit_lines_free(struct rcslines *ls)
{
    free(ls->info);
    free(ls);
}

static void
rcsedit_move_gap(struct rcslines *ls, int lineno)
{
    int width = lineno - ls->gap1;

    if (width > 0) {
	/*
	 *                width
	 *               |------|  <==   |------|
	 * ||------------                ----------------||
	 *               ^gap1  ^lineno  ^gap2           ^end
	 *
	 */
	memmove(&ls->info[ls->gap1], &ls->info[ls->gap2],
		sizeof (struct rcslinfo *) * width);
    }
    else if (width < 0) {
	/*
	 *        -width
	 *     |---------| ===> |---------|
	 * ||------------                  ----------------||
	 *     ^lineno   ^gap1             ^gap2           ^end
	 *
	 */
	memmove(&ls->info[ls->gap2+width], &ls->info[lineno],
		sizeof (struct rcslinfo *) * (-width));
    }
    ls->gap1 += width;
    ls->gap2 += width;
}

static void
rcsedit_realloc_lines(struct rcslines *ls, int num)
{
    int gaplen = ls->gap2 - ls->gap1;
    int len2 = ls->end - ls->gap2 + 1; /* with sentinel */
    int total = ls->end - gaplen + num + 1;
    int alloc = (total/3)*4;
    int newgap2 = alloc-len2;
    struct rcslinfo **newinfo;

    newinfo = emalloc(sizeof (struct rcslinfo *) * alloc);
    memmove(newinfo, ls->info,
	    sizeof (struct rcslinfo *) * ls->gap1);
    memmove(&newinfo[newgap2], &ls->info[ls->gap2],
	    sizeof (struct rcslinfo *) * len2);
    free(ls->info);
    ls->info = newinfo;
    ls->gap2 = newgap2;
    ls->end = alloc-1;
}

void
rcsedit_append_lines(struct rcslines *ls, struct rcsrev *rev,
		     int lineno, int num, char *text)
{
    struct rcslinfo *prev;
    struct rcslinfo *next;

    /* if no more room then expand lines array */
    if ((ls->gap2 - ls->gap1) <= num)
	rcsedit_realloc_lines(ls, num);
    rcsedit_move_gap(ls, lineno);
    rcsedit_place_text(&ls->info[ls->gap1], text, rev, num);

    if (rcsnum_trunk_p(rev->num)) {
	/* insert just after live texts; next may or may not live */
	prev = ls->info[ls->gap1-1];
	next = prev->next;
    }
    else {
	/* insert just before live texts; prev may or may not live */
	next = ls->info[ls->gap2];
	prev = next->prev;
    }
    rcsedit_info_link(prev, ls->info[ls->gap1]);
    rcsedit_info_link(ls->info[ls->gap1+num-1], next);

    ls->gap1 += num;
}

void
rcsedit_delete_lines(struct rcslines *ls, struct rcsrev *rev,
		     int lineno, int num)
{
    int i;

    /*
     * 1.1 -- 1.2 -- 1.3
     *  \ 1.1.1.1 -- 1.1.1.2
     */
    rcsedit_move_gap(ls, lineno);
    if (rcsnum_trunk_p(rev->num))
	rev = rev->prev;
    for (i = 0; i < num; i++)
	rcsedit_info_terminate(ls->info[ls->gap2+i], rev);
    ls->gap2 += num;
}

void
rcsedit_apply_delta(struct rcslines *ls, struct rcsdelta *delta,
		    struct rcsrev *rev)
{
    struct rcsdelta *d;
    int last = 0;
    int pos;
    int offset = 0;

    for (d = delta; d->editcmd != EOF; d++) {
	/*
	 * 'a': lineno points a line located *before* an append point
	 * 'd': lineno points a line located *after* a deletion start
	 * exception 'a' into deleted area such as:
	 * ------------------------
	 * d 3 2
	 * a 3 1
	 * if (hoge == 0) {
	 * ------------------------
	 * in this case, "d 3 2" deletes line 3, 4; "a 3 1" append the
	 * text just after the line 3 which is already deleted.
	 */

	if (d->editcmd == 'a') {
	    pos = d->lineno + 1;
	    if (pos < last)
		pos = last;
	    rcsedit_append_lines(ls, rev, pos+offset, d->lines, d->text);
	    last = pos;
	    offset += d->lines;
	}
	else if (d->editcmd == 'd') {
	    pos = d->lineno;
	    rcsedit_delete_lines(ls, rev, pos+offset, d->lines);
	    last = pos + d->lines;
	    offset -= d->lines;
	}
    }
}

void
rcsedit_apply_rev(struct rcslines *ls, struct rcsrev *rev)
{
    struct rcsdelta *delta = rcsedit_parse_delta(rcsrev_get_text(rev));

    rcsedit_apply_delta(ls, delta, rev);
    free(delta);
}

void
rcsedit_apply_nonext(struct rcslines *ls, struct rcsrev *rev)
{
    int i;

    if (!rcsnum_trunk_p(rev->num))
	return;			/* do nothing */

    for (i = 1; i < ls->gap1; i++)
	rcsedit_info_terminate(ls->info[i], rev);
    for (i = ls->gap2; i < ls->end; i++)
	rcsedit_info_terminate(ls->info[i], rev);
}

/****************************************************************
 *
 * application
 *
 */

struct rcslines *
rcs_get_revision_text(struct rcsfile *rcs, struct rcsrev *rev, int anflag)
{
    struct rcsrev *r = rcs_get_head(rcs);
    struct rcslines *ls = rcsedit_lines_create(r);
    struct rcsrev *next;

    while (!rcsnum_ancestor_p(r->num, rev->num)) {
	r = rcsrev_get_nextlink(r);
	if (r == NULL)
	    return NULL;
	rcsedit_apply_rev(ls, r);
    }

    if (anflag) {
	struct rcslines *ls2 = rcsedit_lines_copy(ls);
	struct rcsrev *r2 = r;

	next = rcsrev_get_nextlink(r2);
	while (next != NULL) {
	    r2 = next;
	    rcsedit_apply_rev(ls2, r2);
	    next = rcsrev_get_nextlink(r2);
	}
	rcsedit_apply_nonext(ls2, r2);
	rcsedit_lines_free(ls2);
    }

    while (r != rev) {
	r = rcsrev_find_branch(r, rev);
	if (r == NULL)
	    return NULL;

	rcsedit_apply_rev(ls, r);
	next = rcsrev_get_nextlink(r);

	while (next != NULL && rcsnum_ancestor_p(next->num, rev->num)) {
	    r = next;
	    rcsedit_apply_rev(ls, r);
	    next = rcsrev_get_nextlink(r);
	}
    }

    return ls;
}

static void
rcs_get_union_sub(struct rcsfile *rcs, struct rcslines *ls, struct list *list)
{
    struct link *l;
    struct rcsrev *r;
    struct rcslines *ls2;

    for (l = list->first; l != NULL; l = l->next) {
	r = l->obj;
	ls2 = (l->next == NULL) ? ls : rcsedit_lines_copy(ls);
	while (r != NULL) {
	    rcsedit_apply_rev(ls2, r);

	    if (r->branches != NULL)
		rcs_get_union_sub(rcs, rcsedit_lines_copy(ls2), r->branches);

	    r = rcsrev_get_nextlink(r);
	}
    }
}

struct rcslines *
rcs_get_union(struct rcsfile *rcs)
{
    struct rcsrev *r = rcs_get_head(rcs);
    struct rcslines *ls = rcsedit_lines_create(r);
    struct rcsrev *next;

    /* retro-traversal of main trunk */
    next = rcsrev_get_nextlink(r);
    while (next != NULL) {
	r = next;
	rcsedit_apply_rev(ls, r);

	if (r->branches != NULL)
	    rcs_get_union_sub(rcs, rcsedit_lines_copy(ls), r->branches);

	next = rcsrev_get_nextlink(r);
    }
    rcsedit_apply_nonext(ls, r);

    return ls;
}

static void
usage()
{
    fprintf(stderr, "\
Usage: \n\
    rcsview -u <rcsfile>\n\
    rcsview -a <revision> <rcsfile>\n\
    rcsview [-p] <revision> <rcsfile>\n");
    exit(2);
}

#define RCS_OFORMAT_DEFAULT 0
#define RCS_OFORMAT_NORMAL 1
#define RCS_OFORMAT_ANNO   2
#define RCS_OFORMAT_UNION  3

int
main(int argc, char **argv)
{
    int i;
    char *arg;
    char *revnum;
    char *rcsfile;
    int oformat = RCS_OFORMAT_DEFAULT;
    struct rcsio *io;
    struct rcsrev *rev;
    struct rcslines *ls;

    /* XXX: getopt  */
    for (i = 1; i < argc; i++) {
	arg = argv[i];
	if (*arg != '-')
	    break;
	if (oformat != RCS_OFORMAT_DEFAULT)
	    usage();
	switch (tolower(arg[1])) {
	case 'p':
	    oformat = RCS_OFORMAT_NORMAL;
	    break;
	case 'a':
	    oformat = RCS_OFORMAT_ANNO;
	    break;
	case 'u':
	    oformat = RCS_OFORMAT_UNION;
	    break;
	default:
	    usage();
	}
    }

    switch (oformat) {
    case RCS_OFORMAT_DEFAULT:
    case RCS_OFORMAT_NORMAL:
    case RCS_OFORMAT_ANNO:
	if (i+2 != argc)
	    usage();
	revnum = argv[i];
	rcsfile = argv[i+1];

	io = rcs_rcstext_readin(rcsfile);
	if (io == NULL) {
	    fprintf(stderr, "open fail %s\n", rcsfile);
	    usage();
	}

	rev = rcs_get_revision(io->rcs, revnum, ENTRY_NOCREATE);
	if (rev == NULL) {
	    fprintf(stderr, "no such a revision %s\n", revnum);
	    usage();
	}
	if (oformat == RCS_OFORMAT_ANNO) {
	    ls = rcs_get_revision_text(io->rcs, rev, 1);
	    rcsedit_lines_print(ls, stdout, RCS_PRINT_STYLE_ANNO);
	}
	else {
	    ls = rcs_get_revision_text(io->rcs, rev, 0);
	    rcsedit_lines_print(ls, stdout, RCS_PRINT_STYLE_NONE);
	}
	return 0;

    case RCS_OFORMAT_UNION:
	if (i+1 != argc)
	    usage();
	rcsfile = argv[i];

	io = rcs_rcstext_readin(rcsfile);
	if (io == NULL) {
	    fprintf(stderr, "open fail %s\n", rcsfile);
	    usage();
	}

	ls = rcs_get_union(io->rcs);
	rcsedit_union_print(ls, stdout);
	return 0;
    }
    return 1;
}

/* end of rcsview.c */