1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Cimarron D. Taylor of the University of California, Berkeley. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)operator.c 5.4 (Berkeley) 05/24/91"; 13 #endif /* not lint */ 14 15 #include <sys/types.h> 16 #include <stdio.h> 17 #include "find.h" 18 19 /* 20 * yanknode -- 21 * destructively removes the top from the plan 22 */ 23 static PLAN * 24 yanknode(planp) 25 PLAN **planp; /* pointer to top of plan (modified) */ 26 { 27 PLAN *node; /* top node removed from the plan */ 28 29 if ((node = (*planp)) == NULL) 30 return(NULL); 31 (*planp) = (*planp)->next; 32 node->next = NULL; 33 return(node); 34 } 35 36 /* 37 * yankexpr -- 38 * Removes one expression from the plan. This is used mainly by 39 * paren_squish. In comments below, an expression is either a 40 * simple node or a N_EXPR node containing a list of simple nodes. 41 */ 42 static PLAN * 43 yankexpr(planp) 44 PLAN **planp; /* pointer to top of plan (modified) */ 45 { 46 register PLAN *next; /* temp node holding subexpression results */ 47 PLAN *node; /* pointer to returned node or expression */ 48 PLAN *tail; /* pointer to tail of subplan */ 49 PLAN *subplan; /* pointer to head of ( ) expression */ 50 int f_expr(); 51 52 /* first pull the top node from the plan */ 53 if ((node = yanknode(planp)) == NULL) 54 return(NULL); 55 56 /* 57 * If the node is an '(' then we recursively slurp up expressions 58 * until we find its associated ')'. If it's a closing paren we 59 * just return it and unwind our recursion; all other nodes are 60 * complete expressions, so just return them. 61 */ 62 if (node->type == N_OPENPAREN) 63 for (tail = subplan = NULL;;) { 64 if ((next = yankexpr(planp)) == NULL) 65 err("%s: %s", "(", "missing closing ')'"); 66 /* 67 * If we find a closing ')' we store the collected 68 * subplan in our '(' node and convert the node to 69 * a N_EXPR. The ')' we found is ignored. Otherwise, 70 * we just continue to add whatever we get to our 71 * subplan. 72 */ 73 if (next->type == N_CLOSEPAREN) { 74 if (subplan == NULL) 75 err("%s: %s", 76 "()", "empty inner expression"); 77 node->p_data[0] = subplan; 78 node->type = N_EXPR; 79 node->eval = f_expr; 80 break; 81 } else { 82 if (subplan == NULL) 83 tail = subplan = next; 84 else { 85 tail->next = next; 86 tail = next; 87 } 88 tail->next = NULL; 89 } 90 } 91 return(node); 92 } 93 94 /* 95 * paren_squish -- 96 * replaces "parentheisized" plans in our search plan with "expr" nodes. 97 */ 98 PLAN * 99 paren_squish(plan) 100 PLAN *plan; /* plan with ( ) nodes */ 101 { 102 register PLAN *expr; /* pointer to next expression */ 103 register PLAN *tail; /* pointer to tail of result plan */ 104 PLAN *result; /* pointer to head of result plan */ 105 106 result = tail = NULL; 107 108 /* 109 * the basic idea is to have yankexpr do all our work and just 110 * collect it's results together. 111 */ 112 while ((expr = yankexpr(&plan)) != NULL) { 113 /* 114 * if we find an unclaimed ')' it means there is a missing 115 * '(' someplace. 116 */ 117 if (expr->type == N_CLOSEPAREN) 118 err("%s: %s", ")", "no beginning '('"); 119 120 /* add the expression to our result plan */ 121 if (result == NULL) 122 tail = result = expr; 123 else { 124 tail->next = expr; 125 tail = expr; 126 } 127 tail->next = NULL; 128 } 129 return(result); 130 } 131 132 /* 133 * not_squish -- 134 * compresses "!" expressions in our search plan. 135 */ 136 PLAN * 137 not_squish(plan) 138 PLAN *plan; /* plan to process */ 139 { 140 register PLAN *next; /* next node being processed */ 141 register PLAN *node; /* temporary node used in N_NOT processing */ 142 register PLAN *tail; /* pointer to tail of result plan */ 143 PLAN *result; /* pointer to head of result plan */ 144 145 tail = result = next = NULL; 146 147 while ((next = yanknode(&plan)) != NULL) { 148 /* 149 * if we encounter a ( expression ) then look for nots in 150 * the expr subplan. 151 */ 152 if (next->type == N_EXPR) 153 next->p_data[0] = not_squish(next->p_data[0]); 154 155 /* 156 * if we encounter a not, then snag the next node and place 157 * it in the not's subplan. As an optimization we compress 158 * several not's to zero or one not. 159 */ 160 if (next->type == N_NOT) { 161 int notlevel = 1; 162 163 node = yanknode(&plan); 164 while (node->type == N_NOT) { 165 ++notlevel; 166 node = yanknode(&plan); 167 } 168 if (node == NULL) 169 err("%s: %s", "!", "no following expression"); 170 if (node->type == N_OR) 171 err("%s: %s", "!", "nothing between ! and -o"); 172 if (notlevel % 2 != 1) 173 next = node; 174 else 175 next->p_data[0] = node; 176 } 177 178 /* add the node to our result plan */ 179 if (result == NULL) 180 tail = result = next; 181 else { 182 tail->next = next; 183 tail = next; 184 } 185 tail->next = NULL; 186 } 187 return(result); 188 } 189 190 /* 191 * or_squish -- 192 * compresses -o expressions in our search plan. 193 */ 194 PLAN * 195 or_squish(plan) 196 PLAN *plan; /* plan with ors to be squished */ 197 { 198 register PLAN *next; /* next node being processed */ 199 register PLAN *tail; /* pointer to tail of result plan */ 200 PLAN *result; /* pointer to head of result plan */ 201 202 tail = result = next = NULL; 203 204 while ((next = yanknode(&plan)) != NULL) { 205 /* 206 * if we encounter a ( expression ) then look for or's in 207 * the expr subplan. 208 */ 209 if (next->type == N_EXPR) 210 next->p_data[0] = or_squish(next->p_data[0]); 211 212 /* if we encounter a not then look for not's in the subplan */ 213 if (next->type == N_NOT) 214 next->p_data[0] = or_squish(next->p_data[0]); 215 216 /* 217 * if we encounter an or, then place our collected plan in the 218 * or's first subplan and then recursively collect the 219 * remaining stuff into the second subplan and return the or. 220 */ 221 if (next->type == N_OR) { 222 if (result == NULL) 223 err("%s: %s", "-o", "no expression before -o"); 224 next->p_data[0] = result; 225 next->p_data[1] = or_squish(plan); 226 if (next->p_data[1] == NULL) 227 err("%s: %s", "-o", "no expression after -o"); 228 return(next); 229 } 230 231 /* add the node to our result plan */ 232 if (result == NULL) 233 tail = result = next; 234 else { 235 tail->next = next; 236 tail = next; 237 } 238 tail->next = NULL; 239 } 240 return(result); 241 } 242