2.11BSD#431 - /usr/ingres/source/qrymod/trscan.c

   1: # include   "../ingres.h"
   2: # include   "../symbol.h"
   3: # include   "../tree.h"
   4: # include   "qrymod.h"
   5: 
   6: /*
   7: **  TRSCAN -- scan trees for various conditions
   8: **
   9: **	These are basically utility routines which do tree scans for
  10: **	one thing or another.  Really, there is nothing exciting at
  11: **	all in this module.
  12: **
  13: **	Defines:
  14: **		aggcheck -- scan tree for aggregates
  15: **		vfind -- find definition for VAR in a view tree
  16: **		qscan -- scan qualification for a variable
  17: **
  18: **	Requires:
  19: **		-
  20: **
  21: **	Required By:
  22: **		MANY
  23: **
  24: **	Compilation Flags:
  25: **		14
  26: **
  27: **	Trace Flags:
  28: **		14
  29: **
  30: **	History:
  31: **		2/14/79 -- version 6.2/0 release.
  32: **		3/22/78 (eric) -- written
  33: */
  34: /*
  35: **  AGGCHECK -- check for any aggregate in subtree.
  36: **
  37: **	This routine checks to insure that the view algorithm can
  38: **	proceed safely by checking for aggregates in the view tree.
  39: **
  40: **	Parameters:
  41: **		root -- the root of the tree to check.
  42: **
  43: **	Returns:
  44: **		TRUE -- an aggregate found.
  45: **		FALSE -- no aggregates in tree.
  46: **
  47: **	Side Effects:
  48: **		none
  49: **
  50: **	Called By:
  51: **		view
  52: **
  53: **	Trace Flags:
  54: **		14
  55: */
  56: 
  57: aggcheck(root)
  58: QTREE   *root;
  59: {
  60:     register QTREE  *t;
  61: 
  62:     t = root;
  63: 
  64:     /* check for no pointer */
  65:     while (t != NULL)
  66:     {
  67:         /* check for this node an AGHEAD */
  68:         if (t->sym.type == AGHEAD)
  69:             return (TRUE);
  70: 
  71:         /* check left subtree recursively */
  72:         if (aggcheck(t->left))
  73:             return (TRUE);
  74: 
  75:         /* check right subtree iteratively */
  76:         t = t->right;
  77:     }
  78: 
  79:     return (FALSE);
  80: }
  81: /*
  82: **  VFIND -- find definition for attribute in view tree
  83: **
  84: **	The view tree is scanned for a specified RESDOM; a pointer
  85: **	to the value is returned.
  86: **
  87: **	Parameters:
  88: **		vn -- the variable number to dig out.
  89: **		vtree -- a pointer to the target list of the
  90: **			view definition tree.
  91: **
  92: **	Returns:
  93: **		a pointer to the substitution value for the specified
  94: **			'vn'.
  95: **		NULL -- if not found.
  96: **
  97: **	Side Effects:
  98: **		none
  99: **
 100: **	Requires:
 101: **
 102: **	Called By:
 103: **		subsvars
 104: **		vrscan
 105: **
 106: **	Trace Flags:
 107: **		14
 108: **
 109: **	Diagnostics:
 110: **		none
 111: **
 112: **	Syserrs:
 113: **		vfind: bad RESDOM %d -- a node was found which was not
 114: **			a RESDOM node, nor a TREE node, in 'vtree'.
 115: */
 116: 
 117: QTREE *
 118: vfind(vn, vtree)
 119: int vn;
 120: QTREE   *vtree;
 121: {
 122:     register int    n;
 123:     register QTREE  *v;
 124: 
 125:     n = vn;
 126: 
 127:     for (v = vtree; v->sym.type == RESDOM; v = v->left)
 128:     {
 129:         if (((struct qt_res *)v)->resno != n)
 130:             continue;
 131: 
 132:         /* found the correct replacement */
 133:         return (v->right);
 134:     }
 135: 
 136:     if (v->sym.type != TREE)
 137:         syserr("vfind: bad RESDOM node %d", v->sym.type);
 138:     return (NULL);
 139: }
 140: /*
 141: **  QSCAN -- find specified VAR node in subtree
 142: **
 143: **	Intended for finding a variable in a qualification, this
 144: **	routine just scans a tree recursively looking for a node
 145: **	with the specified VAR (varno.attno) node.
 146: **
 147: **	Parameters:
 148: **		root -- the root of the tree to scan.
 149: **		vn -- the varno to scan for.
 150: **		an -- the attno to scan for.
 151: **
 152: **	Returns:
 153: **		A pointer to the first found VAR node which matches.
 154: **			Scan is prefix.
 155: **		NULL if not found at all.
 156: **
 157: **	Side Effects:
 158: **		none
 159: **
 160: **	Requires:
 161: **		none
 162: **
 163: **	Called By:
 164: **		vrscan
 165: **
 166: **	Trace Flags:
 167: **		15
 168: **
 169: **	Diagnostics:
 170: **		none
 171: **
 172: **	Syserrs:
 173: **		none
 174: */
 175: 
 176: QTREE *
 177: qscan(root, vn, an)
 178: QTREE   *root;
 179: int vn;
 180: int an;
 181: {
 182:     register QTREE  *t;
 183:     register QTREE  *u;
 184: 
 185:     t = root;
 186: 
 187:     /* check for null node */
 188:     if (t == NULL)
 189:         return (t);
 190: 
 191:     /* check to see if this node qualifies */
 192:     if (t->sym.type == VAR && ((struct qt_var *)t)->varno == vn && ((struct qt_var *)t)->attno == an)
 193:         return (t);
 194: 
 195:     /* check other nodes */
 196:     if ((u = qscan(t->left, vn, an)) != NULL)
 197:         return (u);
 198:     return (qscan(t->right, vn, an));
 199: }
 200: /*
 201: **  VARSET -- scan tree and set a bit vector of variables
 202: **
 203: **	The return value is a bit vector representing the set of
 204: **	variables used in that subtree.
 205: **
 206: **	Parameters:
 207: **		root -- the root of the tree to check.
 208: **
 209: **	Returns:
 210: **		A bit vector, such that bit zero (on the low order,
 211: **			right-hand end) means var zero.
 212: **
 213: **	Side Effects:
 214: **		none
 215: **
 216: **	Requires:
 217: **		none
 218: **
 219: **	Called By:
 220: **		vrscan
 221: **
 222: **	Trace Flags:
 223: **		none
 224: **
 225: **	Diagnostics:
 226: **		none
 227: **
 228: **	Syserrs:
 229: **		none
 230: */
 231: 
 232: varset(root)
 233: QTREE   *root;
 234: {
 235:     register QTREE  *t;
 236:     register int    s;
 237: 
 238:     t = root;
 239: 
 240:     if (t == NULL)
 241:         return (0);
 242: 
 243:     /* scan left and right branches */
 244:     s = varset(t->left);
 245:     s |= varset(t->right);
 246: 
 247:     /* check out this node */
 248:     if (t->sym.type == VAR)
 249:     {
 250:         /* or in bit corresponding to this varno */
 251:         s |= 1 << ((struct qt_var *)t)->varno;
 252:     }
 253: 
 254:     return (s);
 255: }
 256: /*
 257: **  SUBSVARS -- scan query tree and replace VAR nodes
 258: **
 259: **	Scans a tree and finds all VAR nodes for this variable.
 260: **	These nodes are looked up in the translation tree and
 261: **	replaced by the value found there.  If this is for a
 262: **	view, the corresponding node must exist in the translation
 263: **	tree, otherwise, a 'zero' node (of a type appropriate based
 264: **	on the context) is created and inserted.
 265: **
 266: **	This routine is one half of the guts of the whole view
 267: **	algorithm.
 268: **
 269: **	VAR nodes are detached and replaced with the replacement
 270: **	as defined by the view.  Note that there can never be any
 271: **	problems here, since VAR nodes are only used in retrieve
 272: **	contexts.
 273: **
 274: **	It does some extra processing with RESDOM nodes with
 275: **	resno = 0.  These nodes specify a 'tid' domain, and are
 276: **	included by the parser on REPLACE and DELETE commands
 277: **	(for some reason decomp wants them).  Subsvars will allow
 278: **	this construct iff the right hand pointer is a VAR node
 279: **	with attno = 0.  In this case it just changes the varno
 280: **	of the VAR node to be the Resultvar number.  This is be-
 281: **	cause the Resultvar is the variable number of the one and
 282: **	only underlying base relation of the view on an update
 283: **	(which is presumably the only case where this can come
 284: **	up).  Vrscan has already insured that there can only be
 285: **	a single base relation in this case.
 286: **
 287: **	This whole messy thing is only done with view substitutions.
 288: **
 289: **	Parameters:
 290: **		proot -- a pointer to the pointer to the root of the
 291: **			tree to be updated.
 292: **		vn -- the varno of the view variable.  This is the
 293: **			varno which will be scanned for.
 294: **		transtree -- a pointer to the left branch (target list)
 295: **			of the translation tree.
 296: **		vmode -- mdVIEW if called from view processor, mdAPP
 297: **			if called from the integrity processor with
 298: **			an APPEND command, else something else.
 299: **			Mostly, changes the handling of TID type
 300: **			nodes, and forces an error on a view if the
 301: **			VAR node in the scanned tree does not exist
 302: **			in the vtree.
 303: **
 304: **	Returns:
 305: **		none
 306: **		(non-local on error).
 307: **
 308: **	Side Effects:
 309: **		The tree pointed to by *proot is updated in possibly
 310: **			very exciting ways.
 311: **
 312: **	Requires:
 313: **		Newresvar -- in the view case, the new result variable
 314: **			number of the query.
 315: **		treedup -- to dup the tree from vfind.
 316: **		makezero -- to make a zero node when vmode == mdAPP.
 317: **
 318: **	Called By:
 319: **		view
 320: **
 321: **	Trace Flags:
 322: **		32
 323: **
 324: **	Diagnostics:
 325: **		3340: views do not have tids -- the user has tried to
 326: **			reference 'v.tid', where v is the range variable
 327: **			for the view.  This can be determined un-
 328: **			ambiguously if the view ranges over only one
 329: **			relation, but is impossible otherwise; for the
 330: **			time being it is impossible to reference the
 331: **			'tid' field at all.
 332: */
 333: 
 334: subsvars(proot, vn, transtree, vmode)
 335: QTREE   **proot;
 336: int vn;
 337: QTREE   *transtree;
 338: int vmode;
 339: {
 340:     register QTREE  *t;
 341:     register QTREE  *v;
 342:     register int    i;
 343:     extern QTREE    *vfind(), *makezero(), *treedup();
 344:     extern int  Newresvar;  /* defined in view.c */
 345: 
 346:     t = *proot;
 347:     v = transtree;
 348: 
 349: #	ifdef xQTR3
 350:     if (tTf(32, 0))
 351:         printf("subsvars: vn %d root %u transtree %u\n", vn, t, v);
 352: #	endif
 353: 
 354:     if (t == NULL)
 355:         return;
 356: 
 357:     /* check left branch of the tree */
 358:     subsvars(&t->left, vn, v, vmode);
 359: 
 360:     /* check for special 'tid' RESDOM (used by DEL and REPL) */
 361:     if (t->sym.type == RESDOM && ((struct qt_res *)t)->resno == 0)
 362:     {
 363:         /* test for not Resultvar, in which case we ignore leaf */
 364:         if (vn != Resultvar)
 365:             return;
 366: 
 367:         /* t->right better be VAR node, attno 0 */
 368:         t = t->right;
 369:         if (t->sym.type != VAR || ((struct qt_var *)t)->attno != 0 || ((struct qt_var *)t)->varno != vn)
 370:             syserr("subsvars: RESDOM 0 not VAR 0 %d, %d, %d",
 371:                 vn, ((struct qt_var *)t)->attno, t->sym.type);
 372: 
 373:         /* change varno to new Newresvar (set by vrscan) */
 374: #		ifdef xQTR3
 375:         if (tTf(32, 1))
 376:             printf("RESDOM 0: Newresvar %d\n", Newresvar);
 377: #		endif
 378:         ((struct qt_var *)t)->varno = Newresvar;
 379:         return;
 380:     }
 381: 
 382:     /* scan right branch */
 383:     subsvars(&t->right, vn, v, vmode);
 384: 
 385:     /* check for interesting node */
 386:     if (t->sym.type != VAR || ((struct qt_var *)t)->varno != vn)
 387:         return;
 388: 
 389:     /* test for special 'tid' attribute case */
 390:     if (((struct qt_var *)t)->attno == 0 && vmode == mdVIEW)
 391:     {
 392:         ferror(3340, Qmode, vn, 0); /* views do not have tids */
 393:     }
 394: 
 395:     /* find var in vtree */
 396:     v = vfind(((struct qt_var *)t)->attno, v);
 397:     if (v == NULL)
 398:     {
 399:         if (vmode == mdVIEW)
 400:             syserr("subsvars: attno %d", ((struct qt_var *)t)->attno);
 401:         else if (vmode == mdAPP)
 402:             v = makezero();
 403:     }
 404:     else
 405:         v = treedup(v);
 406: 
 407:     /* replace VAR node */
 408:     if (v != NULL)
 409:         *proot = v;
 410: }

Defined functions