1da2e3ebchin/***********************************************************************
2da2e3ebchin*                                                                      *
3da2e3ebchin*               This software is part of the ast package               *
43e14f97Roger A. Faulkner*          Copyright (c) 1982-2010 AT&T Intellectual Property          *
5da2e3ebchin*                      and is licensed under the                       *
6da2e3ebchin*                  Common Public License, Version 1.0                  *
77c2fbfbApril Chin*                    by AT&T Intellectual Property                     *
8da2e3ebchin*                                                                      *
9da2e3ebchin*                A copy of the License is available at                 *
10da2e3ebchin*            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebchin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebchin*                                                                      *
13da2e3ebchin*              Information and Software Systems Research               *
14da2e3ebchin*                            AT&T Research                             *
15da2e3ebchin*                           Florham Park NJ                            *
16da2e3ebchin*                                                                      *
17da2e3ebchin*                  David Korn <dgk@research.att.com>                   *
18da2e3ebchin*                                                                      *
19da2e3ebchin***********************************************************************/
20da2e3ebchin#pragma prototyped
21da2e3ebchin
22da2e3ebchin/*
23da2e3ebchin * code for tree nodes and name walking
24da2e3ebchin *
25da2e3ebchin *   David Korn
26da2e3ebchin *   AT&T Labs
27da2e3ebchin *
28da2e3ebchin */
29da2e3ebchin
30da2e3ebchin#include	"defs.h"
31da2e3ebchin#include	"name.h"
32da2e3ebchin#include	"argnod.h"
337c2fbfbApril Chin#include	"lexstates.h"
34da2e3ebchin
35da2e3ebchinstruct nvdir
36da2e3ebchin{
37da2e3ebchin	Dt_t		*root;
38da2e3ebchin	Namval_t	*hp;
39da2e3ebchin	Namval_t	*table;
407c2fbfbApril Chin	Namval_t	*otable;
41da2e3ebchin	Namval_t	*(*nextnode)(Namval_t*,Dt_t*,Namfun_t*);
42da2e3ebchin	Namfun_t	*fun;
43da2e3ebchin	struct nvdir	*prev;
44da2e3ebchin	int		len;
45da2e3ebchin	char		data[1];
46da2e3ebchin};
47da2e3ebchin
48da2e3ebchinchar *nv_getvtree(Namval_t*, Namfun_t *);
49da2e3ebchinstatic void put_tree(Namval_t*, const char*, int,Namfun_t*);
507c2fbfbApril Chinstatic char *walk_tree(Namval_t*, Namval_t*, int);
517c2fbfbApril Chin
527c2fbfbApril Chinstatic int read_tree(Namval_t* np, Sfio_t *iop, int n, Namfun_t *dp)
537c2fbfbApril Chin{
547c2fbfbApril Chin	Sfio_t	*sp;
557c2fbfbApril Chin	char	*cp;
567c2fbfbApril Chin	int	c;
577c2fbfbApril Chin	if(n>=0)
587c2fbfbApril Chin		return(-1);
597c2fbfbApril Chin	while((c = sfgetc(iop)) &&  isblank(c));
607c2fbfbApril Chin	sfungetc(iop,c);
617c2fbfbApril Chin	sfprintf(sh.strbuf,"%s=%c",nv_name(np),0);
627c2fbfbApril Chin	cp = sfstruse(sh.strbuf);
637c2fbfbApril Chin	sp = sfopen((Sfio_t*)0,cp,"s");
647c2fbfbApril Chin	sfstack(iop,sp);
657c2fbfbApril Chin	c=sh_eval(iop,SH_READEVAL);
667c2fbfbApril Chin	return(c);
677c2fbfbApril Chin}
68da2e3ebchin
69da2e3ebchinstatic Namval_t *create_tree(Namval_t *np,const char *name,int flag,Namfun_t *dp)
70da2e3ebchin{
71da2e3ebchin	register Namfun_t *fp=dp;
723e14f97Roger A. Faulkner	fp->dsize = 0;
73da2e3ebchin	while(fp=fp->next)
74da2e3ebchin	{
75da2e3ebchin		if(fp->disc && fp->disc->createf)
76da2e3ebchin		{
77da2e3ebchin			if(np=(*fp->disc->createf)(np,name,flag,fp))
78da2e3ebchin				dp->last = fp->last;
79da2e3ebchin			return(np);
80da2e3ebchin		}
81da2e3ebchin	}
82da2e3ebchin	return((flag&NV_NOADD)?0:np);
83da2e3ebchin}
84da2e3ebchin
857c2fbfbApril Chinstatic Namfun_t *clone_tree(Namval_t *np, Namval_t *mp, int flags, Namfun_t *fp){
867c2fbfbApril Chin	Namfun_t	*dp;
877c2fbfbApril Chin	if ((flags&NV_MOVE) && nv_type(np))
887c2fbfbApril Chin		return(fp);
897c2fbfbApril Chin	dp = nv_clone_disc(fp,flags);
907c2fbfbApril Chin	if((flags&NV_COMVAR) && !(flags&NV_RAW))
917c2fbfbApril Chin	{
927c2fbfbApril Chin		walk_tree(np,mp,flags);
937c2fbfbApril Chin		if((flags&NV_MOVE) && !(fp->nofree&1))
947c2fbfbApril Chin			free((void*)fp);
957c2fbfbApril Chin	}
967c2fbfbApril Chin	return(dp);
977c2fbfbApril Chin}
987c2fbfbApril Chin
99da2e3ebchinstatic const Namdisc_t treedisc =
100da2e3ebchin{
101da2e3ebchin	0,
102da2e3ebchin	put_tree,
103da2e3ebchin	nv_getvtree,
104da2e3ebchin	0,
105da2e3ebchin	0,
1067c2fbfbApril Chin	create_tree,
1077c2fbfbApril Chin	clone_tree
1087c2fbfbApril Chin	,0,0,0,
1097c2fbfbApril Chin	read_tree
110da2e3ebchin};
111da2e3ebchin
112da2e3ebchinstatic char *nextdot(const char *str)
113da2e3ebchin{
114da2e3ebchin	register char *cp;
1157c2fbfbApril Chin	register int c;
116da2e3ebchin	if(*str=='.')
117da2e3ebchin		str++;
1187c2fbfbApril Chin	for(cp=(char*)str;c= *cp; cp++)
119da2e3ebchin	{
1207c2fbfbApril Chin		if(c=='[')
1217c2fbfbApril Chin		{
1227c2fbfbApril Chin			cp = nv_endsubscript((Namval_t*)0,(char*)cp,0);
1237c2fbfbApril Chin			return(*cp=='.'?cp:0);
1247c2fbfbApril Chin		}
1257c2fbfbApril Chin		if(c=='.')
1267c2fbfbApril Chin			return(cp);
127da2e3ebchin	}
1287c2fbfbApril Chin	return(0);
129da2e3ebchin}
130da2e3ebchin
131da2e3ebchinstatic  Namfun_t *nextdisc(Namval_t *np)
132da2e3ebchin{
133da2e3ebchin	register Namfun_t *fp;
134da2e3ebchin	if(nv_isref(np))
135da2e3ebchin		return(0);
136da2e3ebchin        for(fp=np->nvfun;fp;fp=fp->next)
137da2e3ebchin	{
138da2e3ebchin		if(fp && fp->disc && fp->disc->nextf)
139da2e3ebchin			return(fp);
140da2e3ebchin	}
141da2e3ebchin	return(0);
142da2e3ebchin}
143da2e3ebchin
1447c2fbfbApril Chinvoid *nv_diropen(Namval_t *np,const char *name)
145da2e3ebchin{
146da2e3ebchin	char *next,*last;
147da2e3ebchin	int c,len=strlen(name);
148da2e3ebchin	struct nvdir *save, *dp = new_of(struct nvdir,len);
1497c2fbfbApril Chin	Namval_t *nq=0,fake;
1507c2fbfbApril Chin	Namfun_t *nfp=0;
151da2e3ebchin	if(!dp)
152da2e3ebchin		return(0);
153da2e3ebchin	memset((void*)dp, 0, sizeof(*dp));
154da2e3ebchin	if(name[len-1]=='*' || name[len-1]=='@')
155da2e3ebchin		len -= 1;
1567c2fbfbApril Chin	name = memcpy(dp->data,name,len);
1577c2fbfbApril Chin	dp->data[len] = 0;
158da2e3ebchin	dp->len = len;
1597c2fbfbApril Chin	dp->root = sh.last_root?sh.last_root:sh.var_tree;
1607c2fbfbApril Chin#if 1
1617c2fbfbApril Chin	while(1)
1627c2fbfbApril Chin	{
1637c2fbfbApril Chin		dp->table = sh.last_table;
1647c2fbfbApril Chin		sh.last_table = 0;
1657c2fbfbApril Chin		if(*(last=(char*)name)==0)
1667c2fbfbApril Chin			break;
1677c2fbfbApril Chin		if(!(next=nextdot(last)))
1687c2fbfbApril Chin			break;
1697c2fbfbApril Chin		*next = 0;
1707c2fbfbApril Chin		np = nv_open(name, dp->root, NV_NOFAIL);
1717c2fbfbApril Chin		*next = '.';
1727c2fbfbApril Chin		if(!np || !nv_istable(np))
1737c2fbfbApril Chin			break;
1747c2fbfbApril Chin		dp->root = nv_dict(np);
1757c2fbfbApril Chin		name = next+1;
1767c2fbfbApril Chin	}
1777c2fbfbApril Chin#else
178da2e3ebchin	dp->table = sh.last_table;
1797c2fbfbApril Chin	sh.last_table = 0;
1807c2fbfbApril Chin	last = dp->data;
1817c2fbfbApril Chin#endif
182da2e3ebchin	if(*name)
183da2e3ebchin	{
184da2e3ebchin		fake.nvname = (char*)name;
1857c2fbfbApril Chin		if(dp->hp = (Namval_t*)dtprev(dp->root,&fake))
1867c2fbfbApril Chin		{
1877c2fbfbApril Chin			char *cp = nv_name(dp->hp);
1887c2fbfbApril Chin			c = strlen(cp);
1897c2fbfbApril Chin			if(memcmp(name,cp,c) || name[c]!='[')
1907c2fbfbApril Chin				dp->hp = (Namval_t*)dtnext(dp->root,dp->hp);
1917c2fbfbApril Chin			else
1927c2fbfbApril Chin			{
1937c2fbfbApril Chin				np = dp->hp;
1947c2fbfbApril Chin				last = 0;
1957c2fbfbApril Chin			}
1967c2fbfbApril Chin		}
19734f9b3eRoland Mainz		else
19834f9b3eRoland Mainz			dp->hp = (Namval_t*)dtfirst(dp->root);
199da2e3ebchin	}
200da2e3ebchin	else
201da2e3ebchin		dp->hp = (Namval_t*)dtfirst(dp->root);
2027c2fbfbApril Chin	while(1)
203da2e3ebchin	{
2047c2fbfbApril Chin		if(!last)
2057c2fbfbApril Chin			next = 0;
2067c2fbfbApril Chin		else if(next= nextdot(last))
2077c2fbfbApril Chin		{
2087c2fbfbApril Chin			c = *next;
2097c2fbfbApril Chin			*next = 0;
2107c2fbfbApril Chin		}
2117c2fbfbApril Chin		if(!np)
2127c2fbfbApril Chin		{
2137c2fbfbApril Chin			if(nfp && nfp->disc && nfp->disc->createf)
2147c2fbfbApril Chin			{
2157c2fbfbApril Chin				np =  (*nfp->disc->createf)(nq,last,0,nfp);
2167c2fbfbApril Chin				if(*nfp->last == '[')
2177c2fbfbApril Chin				{
2187c2fbfbApril Chin					nv_endsubscript(np,nfp->last,NV_NOADD);
2197c2fbfbApril Chin					if(nq = nv_opensub(np))
2207c2fbfbApril Chin						np = nq;
2217c2fbfbApril Chin				}
2227c2fbfbApril Chin			}
2237c2fbfbApril Chin			else
2247c2fbfbApril Chin				np = nv_search(last,dp->root,0);
2257c2fbfbApril Chin		}
2267c2fbfbApril Chin		if(next)
2277c2fbfbApril Chin			*next = c;
2287c2fbfbApril Chin		if(np==dp->hp && !next)
2297c2fbfbApril Chin			dp->hp = (Namval_t*)dtnext(dp->root,dp->hp);
230da2e3ebchin		if(np && ((nfp=nextdisc(np)) || nv_istable(np)))
231da2e3ebchin		{
232da2e3ebchin			if(!(save = new_of(struct nvdir,0)))
233da2e3ebchin				return(0);
234da2e3ebchin			*save = *dp;
235da2e3ebchin			dp->prev = save;
236da2e3ebchin			if(nv_istable(np))
237da2e3ebchin				dp->root = nv_dict(np);
238da2e3ebchin			else
2397c2fbfbApril Chin				dp->root = (Dt_t*)np;
240da2e3ebchin			if(nfp)
241da2e3ebchin			{
242da2e3ebchin				dp->nextnode = nfp->disc->nextf;
243da2e3ebchin				dp->table = np;
2447c2fbfbApril Chin				dp->otable = sh.last_table;
245da2e3ebchin				dp->fun = nfp;
246da2e3ebchin				dp->hp = (*dp->nextnode)(np,(Dt_t*)0,nfp);
247da2e3ebchin			}
248da2e3ebchin			else
249da2e3ebchin				dp->nextnode = 0;
250da2e3ebchin		}
251da2e3ebchin		else
252da2e3ebchin			break;
2537c2fbfbApril Chin		if(!next || next[1]==0)
2547c2fbfbApril Chin			break;
255da2e3ebchin		last = next+1;
2567c2fbfbApril Chin		nq = np;
2577c2fbfbApril Chin		np = 0;
258da2e3ebchin	}
259da2e3ebchin	return((void*)dp);
260da2e3ebchin}
261da2e3ebchin
262da2e3ebchin
263da2e3ebchinstatic Namval_t *nextnode(struct nvdir *dp)
264da2e3ebchin{
265da2e3ebchin	if(dp->nextnode)
266da2e3ebchin		return((*dp->nextnode)(dp->hp,dp->root,dp->fun));
267da2e3ebchin	if(dp->len && memcmp(dp->data, dp->hp->nvname, dp->len))
268da2e3ebchin		return(0);
269da2e3ebchin	return((Namval_t*)dtnext(dp->root,dp->hp));
270da2e3ebchin}
271da2e3ebchin
272da2e3ebchinchar *nv_dirnext(void *dir)
273da2e3ebchin{
274da2e3ebchin	register struct nvdir *save, *dp = (struct nvdir*)dir;
275da2e3ebchin	register Namval_t *np, *last_table;
276da2e3ebchin	register char *cp;
277da2e3ebchin	Namfun_t *nfp;
2787c2fbfbApril Chin	Namval_t *nq;
279da2e3ebchin	while(1)
280da2e3ebchin	{
281da2e3ebchin		while(np=dp->hp)
282da2e3ebchin		{
2837c2fbfbApril Chin#if 0
2847c2fbfbApril Chin			char *sptr;
2857c2fbfbApril Chin#endif
2867c2fbfbApril Chin			if(nv_isarray(np))
2877c2fbfbApril Chin				nv_putsub(np,(char*)0, ARRAY_UNDEF);
288da2e3ebchin			dp->hp = nextnode(dp);
28934f9b3eRoland Mainz			if(nv_isnull(np) && !nv_isarray(np) && !nv_isattr(np,NV_INTEGER))
290da2e3ebchin				continue;
291da2e3ebchin			last_table = sh.last_table;
2927c2fbfbApril Chin#if 0
2937c2fbfbApril Chin			if(dp->table && dp->otable && !nv_isattr(dp->table,NV_MINIMAL))
2947c2fbfbApril Chin			{
2957c2fbfbApril Chin				sptr = dp->table->nvenv;
2967c2fbfbApril Chin				dp->table->nvenv = (char*)dp->otable;
2977c2fbfbApril Chin			}
2987c2fbfbApril Chin#endif
299da2e3ebchin			sh.last_table = dp->table;
300da2e3ebchin			cp = nv_name(np);
3017c2fbfbApril Chin#if 0
3027c2fbfbApril Chin			if(dp->table && dp->otable && !nv_isattr(dp->table,NV_MINIMAL))
3037c2fbfbApril Chin				dp->table->nvenv = sptr;
3047c2fbfbApril Chin#endif
3057c2fbfbApril Chin			if(dp->nextnode && !dp->hp && (nq = (Namval_t*)dp->table))
3067c2fbfbApril Chin			{
3077c2fbfbApril Chin				Namarr_t  *ap = nv_arrayptr(nq);
3087c2fbfbApril Chin				if(ap && (ap->nelem&ARRAY_SCAN) && nv_nextsub(nq))
3097c2fbfbApril Chin					dp->hp = (*dp->nextnode)(np,(Dt_t*)0,dp->fun);
3107c2fbfbApril Chin			}
311da2e3ebchin			sh.last_table = last_table;
3127c2fbfbApril Chin			if(!dp->len || memcmp(cp,dp->data,dp->len)==0)
313da2e3ebchin			{
3147c2fbfbApril Chin				if((nfp=nextdisc(np)) && (nfp->disc->getval||nfp->disc->getnum) && nv_isvtree(np) && strcmp(cp,dp->data))
3157c2fbfbApril Chin					nfp = 0;
3167c2fbfbApril Chin				if(nfp || nv_istable(np))
317da2e3ebchin				{
318da2e3ebchin					Dt_t *root;
319da2e3ebchin					if(nv_istable(np))
320da2e3ebchin						root = nv_dict(np);
321da2e3ebchin					else
3227c2fbfbApril Chin						root = (Dt_t*)np;
323da2e3ebchin					/* check for recursive walk */
324da2e3ebchin					for(save=dp; save;  save=save->prev)
325da2e3ebchin					{
326da2e3ebchin						if(save->root==root)
327da2e3ebchin							break;
328da2e3ebchin					}
329da2e3ebchin					if(save)
3307c2fbfbApril Chin						return(cp);
331da2e3ebchin					if(!(save = new_of(struct nvdir,0)))
332da2e3ebchin						return(0);
333da2e3ebchin					*save = *dp;
334da2e3ebchin					dp->prev = save;
335da2e3ebchin					dp->root = root;
336da2e3ebchin					dp->len = 0;
337da2e3ebchin					if(nfp && np->nvfun)
338da2e3ebchin					{
3397c2fbfbApril Chin#if 0
3407c2fbfbApril Chin				                Namarr_t *ap = nv_arrayptr(np);
3417c2fbfbApril Chin				                if(ap && (ap->nelem&ARRAY_UNDEF))
3427c2fbfbApril Chin				                        nv_putsub(np,(char*)0,ARRAY_SCAN);
3437c2fbfbApril Chin#endif
344da2e3ebchin						dp->nextnode = nfp->disc->nextf;
3457c2fbfbApril Chin						dp->otable = dp->table;
346da2e3ebchin						dp->table = np;
347da2e3ebchin						dp->fun = nfp;
348da2e3ebchin						dp->hp = (*dp->nextnode)(np,(Dt_t*)0,nfp);
349da2e3ebchin					}
350da2e3ebchin					else
351da2e3ebchin						dp->nextnode = 0;
352da2e3ebchin				}
353da2e3ebchin				return(cp);
354da2e3ebchin			}
355da2e3ebchin		}
356da2e3ebchin		if(!(save=dp->prev))
357da2e3ebchin			break;
358da2e3ebchin		*dp = *save;
359da2e3ebchin		free((void*)save);
360da2e3ebchin	}
361da2e3ebchin	return(0);
362da2e3ebchin}
363da2e3ebchin
364da2e3ebchinvoid nv_dirclose(void *dir)
365da2e3ebchin{
366da2e3ebchin	struct nvdir *dp = (struct nvdir*)dir;
367da2e3ebchin	if(dp->prev)
368da2e3ebchin		nv_dirclose((void*)dp->prev);
369da2e3ebchin	free(dir);
370da2e3ebchin}
371da2e3ebchin
372da2e3ebchinstatic void outtype(Namval_t *np, Namfun_t *fp, Sfio_t* out, const char *prefix)
373da2e3ebchin{
374da2e3ebchin	char *type=0;
375da2e3ebchin	Namval_t *tp = fp->type;
376da2e3ebchin	if(!tp && fp->disc && fp->disc->typef)
377da2e3ebchin		tp = (*fp->disc->typef)(np,fp);
378da2e3ebchin	for(fp=fp->next;fp;fp=fp->next)
379da2e3ebchin	{
380da2e3ebchin		if(fp->type || (fp->disc && fp->disc->typef &&(*fp->disc->typef)(np,fp)))
381da2e3ebchin		{
382da2e3ebchin			outtype(np,fp,out,prefix);
383da2e3ebchin			break;
384da2e3ebchin		}
385da2e3ebchin	}
386da2e3ebchin	if(prefix && *prefix=='t')
387da2e3ebchin		type = "-T";
388da2e3ebchin	else if(!prefix)
389da2e3ebchin		type = "type";
390da2e3ebchin	if(type)
3917c2fbfbApril Chin	{
3927c2fbfbApril Chin		char *cp=tp->nvname;
393