4.3BSD - /usr/ingres/source/qrymod/trscan.c

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

Defined functions