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