| 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) %G%"; |
| 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 | } |