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.1 (Berkeley) 04/16/90"; 13 #endif /* not lint */ 14 15 #include <sys/types.h> 16 #include <stdio.h> 17 #include "find.h" 18 19 /* 20 * find_yanknode -- 21 * destructively removes the top from the plan 22 */ 23 PLAN * 24 find_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 * find_yankexpr -- 38 * Removes one expression from the plan. This is used mainly by 39 * find_squish_paren. In comments below, an expression is either 40 * a simple node or a T_EXPR node containing a list of simple nodes. 41 */ 42 PLAN * 43 find_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 = find_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 == T_OPENPAREN) 63 for (tail = subplan = NULL;;) { 64 if ((next = find_yankexpr(planp)) == NULL) 65 bad_arg("(", "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 T_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 == T_CLOSEPAREN) { 74 if (subplan == NULL) 75 bad_arg("()", "empty inner expression"); 76 node->p_data[0] = subplan; 77 node->type = T_EXPR; 78 node->eval = f_expr; 79 break; 80 } else { 81 if (subplan == NULL) 82 tail = subplan = next; 83 else { 84 tail->next = next; 85 tail = next; 86 } 87 tail->next = NULL; 88 } 89 } 90 return(node); 91 } 92 93 /* 94 * find_squish_paren -- 95 * replaces "parentheisized" plans in our search plan with "expr" nodes. 96 */ 97 PLAN * 98 find_squish_paren(plan) 99 PLAN *plan; /* plan with ( ) nodes */ 100 { 101 register PLAN *expr; /* pointer to next expression */ 102 register PLAN *tail; /* pointer to tail of result plan */ 103 PLAN *result; /* pointer to head of result plan */ 104 105 result = tail = NULL; 106 107 /* 108 * the basic idea is to have find_yankexpr do all our work and just 109 * collect it's results together. 110 */ 111 while ((expr = find_yankexpr(&plan)) != NULL) { 112 /* 113 * if we find an unclaimed ')' it means there is a missing 114 * '(' someplace. 115 */ 116 if (expr->type == T_CLOSEPAREN) 117 bad_arg(")", "no beginning '('"); 118 119 /* add the expression to our result plan */ 120 if (result == NULL) 121 tail = result = expr; 122 else { 123 tail->next = expr; 124 tail = expr; 125 } 126 tail->next = NULL; 127 } 128 return(result); 129 } 130 131 /* 132 * find_squish_not -- 133 * compresses "!" expressions in our search plan. 134 */ 135 PLAN * 136 find_squish_not(plan) 137 PLAN *plan; /* plan to process */ 138 { 139 register PLAN *next; /* next node being processed */ 140 register PLAN *node; /* temporary node used in T_NOT processing */ 141 register PLAN *tail; /* pointer to tail of result plan */ 142 PLAN *result; /* pointer to head of result plan */ 143 144 tail = result = next = NULL; 145 146 while ((next = find_yanknode(&plan)) != NULL) { 147 /* 148 * if we encounter a ( expression ) then look for nots in 149 * the expr subplan. 150 */ 151 if (next->type == T_EXPR) 152 next->p_data[0] = find_squish_not(next->p_data[0]); 153 154 /* 155 * if we encounter a not, then snag the next node and place 156 * it in the not's subplan. As an optimization we compress 157 * several not's to zero or one not. 158 */ 159 if (next->type == T_NOT) { 160 int notlevel = 1; 161 162 node = find_yanknode(&plan); 163 while (node->type == T_NOT) { 164 ++notlevel; 165 node = find_yanknode(&plan); 166 } 167 if (node == NULL) 168 bad_arg("!", "no following expression"); 169 if (node->type == T_OR) 170 bad_arg("!", "nothing between ! and -o"); 171 if (notlevel % 2 != 1) 172 next = node; 173 else 174 next->p_data[0] = node; 175 } 176 177 /* add the node to our result plan */ 178 if (result == NULL) 179 tail = result = next; 180 else { 181 tail->next = next; 182 tail = next; 183 } 184 tail->next = NULL; 185 } 186 return(result); 187 } 188 189 /* 190 * find_squish_or -- 191 * compresses -o expressions in our search plan. 192 */ 193 PLAN * 194 find_squish_or(plan) 195 PLAN *plan; /* plan with ors to be squished */ 196 { 197 register PLAN *next; /* next node being processed */ 198 register PLAN *tail; /* pointer to tail of result plan */ 199 PLAN *result; /* pointer to head of result plan */ 200 201 tail = result = next = NULL; 202 203 while ((next = find_yanknode(&plan)) != NULL) { 204 /* 205 * if we encounter a ( expression ) then look for or's in 206 * the expr subplan. 207 */ 208 if (next->type == T_EXPR) 209 next->p_data[0] = find_squish_or(next->p_data[0]); 210 211 /* if we encounter a not then look for not's in the subplan */ 212 if (next->type == T_NOT) 213 next->p_data[0] = find_squish_or(next->p_data[0]); 214 215 /* 216 * if we encounter an or, then place our collected plan in the 217 * or's first subplan and then recursively collect the 218 * remaining stuff into the second subplan and return the or. 219 */ 220 if (next->type == T_OR) { 221 if (result == NULL) 222 bad_arg("-o", "no expression before -o"); 223 next->p_data[0] = result; 224 next->p_data[1] = find_squish_or(plan); 225 if (next->p_data[1] == NULL) 226 bad_arg("-o", "no expression after -o"); 227 return(next); 228 } 229 230 /* add the node to our result plan */ 231 if (result == NULL) 232 tail = result = next; 233 else { 234 tail->next = next; 235 tail = next; 236 } 237 tail->next = NULL; 238 } 239 return(result); 240 } 241