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