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 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #ifndef lint 38 static char sccsid[] = "@(#)operator.c 5.4 (Berkeley) 5/24/91"; 39 #endif /* not lint */ 40 41 #include <sys/types.h> 42 #include <stdio.h> 43 #include "find.h" 44 45 /* 46 * yanknode -- 47 * destructively removes the top from the plan 48 */ 49 static PLAN * 50 yanknode(planp) 51 PLAN **planp; /* pointer to top of plan (modified) */ 52 { 53 PLAN *node; /* top node removed from the plan */ 54 55 if ((node = (*planp)) == NULL) 56 return(NULL); 57 (*planp) = (*planp)->next; 58 node->next = NULL; 59 return(node); 60 } 61 62 /* 63 * yankexpr -- 64 * Removes one expression from the plan. This is used mainly by 65 * paren_squish. In comments below, an expression is either a 66 * simple node or a N_EXPR node containing a list of simple nodes. 67 */ 68 static PLAN * 69 yankexpr(planp) 70 PLAN **planp; /* pointer to top of plan (modified) */ 71 { 72 register PLAN *next; /* temp node holding subexpression results */ 73 PLAN *node; /* pointer to returned node or expression */ 74 PLAN *tail; /* pointer to tail of subplan */ 75 PLAN *subplan; /* pointer to head of ( ) expression */ 76 int f_expr(); 77 78 /* first pull the top node from the plan */ 79 if ((node = yanknode(planp)) == NULL) 80 return(NULL); 81 82 /* 83 * If the node is an '(' then we recursively slurp up expressions 84 * until we find its associated ')'. If it's a closing paren we 85 * just return it and unwind our recursion; all other nodes are 86 * complete expressions, so just return them. 87 */ 88 if (node->type == N_OPENPAREN) 89 for (tail = subplan = NULL;;) { 90 if ((next = yankexpr(planp)) == NULL) 91 err("%s: %s", "(", "missing closing ')'"); 92 /* 93 * If we find a closing ')' we store the collected 94 * subplan in our '(' node and convert the node to 95 * a N_EXPR. The ')' we found is ignored. Otherwise, 96 * we just continue to add whatever we get to our 97 * subplan. 98 */ 99 if (next->type == N_CLOSEPAREN) { 100 if (subplan == NULL) 101 err("%s: %s", 102 "()", "empty inner expression"); 103 node->p_data[0] = subplan; 104 node->type = N_EXPR; 105 node->eval = f_expr; 106 break; 107 } else { 108 if (subplan == NULL) 109 tail = subplan = next; 110 else { 111 tail->next = next; 112 tail = next; 113 } 114 tail->next = NULL; 115 } 116 } 117 return(node); 118 } 119 120 /* 121 * paren_squish -- 122 * replaces "parentheisized" plans in our search plan with "expr" nodes. 123 */ 124 PLAN * 125 paren_squish(plan) 126 PLAN *plan; /* plan with ( ) nodes */ 127 { 128 register PLAN *expr; /* pointer to next expression */ 129 register PLAN *tail; /* pointer to tail of result plan */ 130 PLAN *result; /* pointer to head of result plan */ 131 132 result = tail = NULL; 133 134 /* 135 * the basic idea is to have yankexpr do all our work and just 136 * collect it's results together. 137 */ 138 while ((expr = yankexpr(&plan)) != NULL) { 139 /* 140 * if we find an unclaimed ')' it means there is a missing 141 * '(' someplace. 142 */ 143 if (expr->type == N_CLOSEPAREN) 144 err("%s: %s", ")", "no beginning '('"); 145 146 /* add the expression to our result plan */ 147 if (result == NULL) 148 tail = result = expr; 149 else { 150 tail->next = expr; 151 tail = expr; 152 } 153 tail->next = NULL; 154 } 155 return(result); 156 } 157 158 /* 159 * not_squish -- 160 * compresses "!" expressions in our search plan. 161 */ 162 PLAN * 163 not_squish(plan) 164 PLAN *plan; /* plan to process */ 165 { 166 register PLAN *next; /* next node being processed */ 167 register PLAN *node; /* temporary node used in N_NOT processing */ 168 register PLAN *tail; /* pointer to tail of result plan */ 169 PLAN *result; /* pointer to head of result plan */ 170 171 tail = result = next = NULL; 172 173 while ((next = yanknode(&plan)) != NULL) { 174 /* 175 * if we encounter a ( expression ) then look for nots in 176 * the expr subplan. 177 */ 178 if (next->type == N_EXPR) 179 next->p_data[0] = not_squish(next->p_data[0]); 180 181 /* 182 * if we encounter a not, then snag the next node and place 183 * it in the not's subplan. As an optimization we compress 184 * several not's to zero or one not. 185 */ 186 if (next->type == N_NOT) { 187 int notlevel = 1; 188 189 node = yanknode(&plan); 190 while (node->type == N_NOT) { 191 ++notlevel; 192 node = yanknode(&plan); 193 } 194 if (node == NULL) 195 err("%s: %s", "!", "no following expression"); 196 if (node->type == N_OR) 197 err("%s: %s", "!", "nothing between ! and -o"); 198 if (notlevel % 2 != 1) 199 next = node; 200 else 201 next->p_data[0] = node; 202 } 203 204 /* add the node to our result plan */ 205 if (result == NULL) 206 tail = result = next; 207 else { 208 tail->next = next; 209 tail = next; 210 } 211 tail->next = NULL; 212 } 213 return(result); 214 } 215 216 /* 217 * or_squish -- 218 * compresses -o expressions in our search plan. 219 */ 220 PLAN * 221 or_squish(plan) 222 PLAN *plan; /* plan with ors to be squished */ 223 { 224 register PLAN *next; /* next node being processed */ 225 register PLAN *tail; /* pointer to tail of result plan */ 226 PLAN *result; /* pointer to head of result plan */ 227 228 tail = result = next = NULL; 229 230 while ((next = yanknode(&plan)) != NULL) { 231 /* 232 * if we encounter a ( expression ) then look for or's in 233 * the expr subplan. 234 */ 235 if (next->type == N_EXPR) 236 next->p_data[0] = or_squish(next->p_data[0]); 237 238 /* if we encounter a not then look for not's in the subplan */ 239 if (next->type == N_NOT) 240 next->p_data[0] = or_squish(next->p_data[0]); 241 242 /* 243 * if we encounter an or, then place our collected plan in the 244 * or's first subplan and then recursively collect the 245 * remaining stuff into the second subplan and return the or. 246 */ 247 if (next->type == N_OR) { 248 if (result == NULL) 249 err("%s: %s", "-o", "no expression before -o"); 250 next->p_data[0] = result; 251 next->p_data[1] = or_squish(plan); 252 if (next->p_data[1] == NULL) 253 err("%s: %s", "-o", "no expression after -o"); 254 return(next); 255 } 256 257 /* add the node to our result plan */ 258 if (result == NULL) 259 tail = result = next; 260 else { 261 tail->next = next; 262 tail = next; 263 } 264 tail->next = NULL; 265 } 266 return(result); 267 } 268