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