Something went wrong. Try again.
A breadth-first version of the UNIX find command tavianator.com/projects/bfs.html
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432// Copyright © Tavian Barnes <tavianator@tavianator.com>// SPDX-License-Identifier: 0BSD
/** * The expression optimizer. Different optimization levels are supported: * * -O1: basic logical simplifications, like folding (-true -and -foo) to -foo. * * -O2: dead code elimination and data flow analysis. struct df_domain is used * to record data flow facts that are true at various points of evaluation. * Specifically, struct df_domain records the state before an expression is * evaluated (opt->before), and after an expression returns true * (opt->after_true) or false (opt->after_false). Additionally, opt->impure * records the possible state before any expression with side effects is * evaluated. * * -O3: expression re-ordering to reduce expected cost. In an expression like * (-foo -and -bar), if both -foo and -bar are pure (no side effects), they can * be re-ordered to (-bar -and -foo). This is profitable if the expected cost * is lower for the re-ordered expression, for example if -foo is very slow or * -bar is likely to return false. * * -O4/-Ofast: aggressive optimizations that may affect correctness in corner * cases. The main effect is to use opt->impure to determine if any side- * effects are reachable at all, skipping the traversal if not. */
#include "opt.h"
#include "bfs.h"#include "bfstd.h"#include "bftw.h"#include "bit.h"#include "color.h"#include "ctx.h"#include "diag.h"#include "dir.h"#include "eval.h"#include "exec.h"#include "expr.h"#include "list.h"#include "pwcache.h"#include "xspawn.h"
#include <errno.h>#include <limits.h>#include <stdarg.h>#include <stdio.h>#include <unistd.h>
static char *fake_and_arg = "-and";static char *fake_or_arg = "-or";static char *fake_not_arg = "-not";
/** * The data flow domain for predicates. */enum df_pred { /** The bottom state (unreachable). */ PRED_BOTTOM = 0, /** The predicate is known to be false. */ PRED_FALSE = 1 << false, /** The predicate is known to be true. */ PRED_TRUE = 1 << true, /** The top state (unknown). */ PRED_TOP = PRED_FALSE | PRED_TRUE,};
/** Make a predicate known. */static void constrain_pred(enum df_pred *pred, bool value) { *pred &= 1 << value;}
/** Compute the join (union) of two predicates. */static void pred_join(enum df_pred *dest, enum df_pred src) { *dest |= src;}
/** * Types of predicates we track. */enum pred_type { /** -readable */ READABLE_PRED, /** -writable */ WRITABLE_PRED, /** -executable */ EXECUTABLE_PRED, /** -acl */ ACL_PRED, /** -capable */ CAPABLE_PRED, /** -empty */ EMPTY_PRED, /** -hidden */ HIDDEN_PRED, /** -nogroup */ NOGROUP_PRED, /** -nouser */ NOUSER_PRED, /** -sparse */ SPARSE_PRED, /** -xattr */ XATTR_PRED, /** The number of pred_types. */ PRED_TYPES,};
/** Predicate type names. */static const char *const pred_names[] = { [READABLE_PRED] = "-readable", [WRITABLE_PRED] = "-writable", [EXECUTABLE_PRED] = "-executable", [ACL_PRED] = "-acl", [CAPABLE_PRED] = "-capable", [EMPTY_PRED] = "-empty", [HIDDEN_PRED] = "-hidden", [NOGROUP_PRED] = "-nogroup", [NOUSER_PRED] = "-nouser", [SPARSE_PRED] = "-sparse", [XATTR_PRED] = "-xattr",};
/** * A constrained integer range. */struct df_range { /** The (inclusive) minimum value. */ long long min; /** The (inclusive) maximum value. */ long long max;};
/** Initialize an empty range. */static void range_init_bottom(struct df_range *range) { range->min = LLONG_MAX; range->max = LLONG_MIN;}
/** Check if a range is empty. */static bool range_is_bottom(const struct df_range *range) { return range->min > range->max;}
/** Initialize a full range. */static void range_init_top(struct df_range *range) { // All ranges we currently track are non-negative range->min = 0; range->max = LLONG_MAX;}
/** Check for an infinite range. */static bool range_is_top(const struct df_range *range) { return range->min == 0 && range->max == LLONG_MAX;}
/** Compute the minimum of two values. */static long long min_value(long long a, long long b) { if (a < b) { return a; } else { return b; }}
/** Compute the maximum of two values. */static long long max_value(long long a, long long b) { if (a > b) { return a; } else { return b; }}
/** Constrain the minimum of a range. */static void constrain_min(struct df_range *range, long long value) { range->min = max_value(range->min, value);}
/** Constrain the maximum of a range. */static void constrain_max(struct df_range *range, long long value) { range->max = min_value(range->max, value);}
/** Intersect two ranges. */static void range_intersect(struct df_range *range, const struct df_range *other) { constrain_min(range, other->min); constrain_max(range, other->max);}
/** Constrain a range to a single value. */static void constrain_range(struct df_range *range, long long value) { const struct df_range other = { .min = value, .max = value, }; range_intersect(range, &other);}
/** Check if a range contains a value. */static bool range_contains(const struct df_range *range, long long value) { return value >= range->min && value <= range->max;}
/** Subtract a range from another range. */static void range_subtract(struct df_range *range, const struct df_range *other) { if (range_contains(other, range->min)) { range->min = other->max; if (range->min < LLONG_MAX) { ++range->min; } else { range->max = LLONG_MIN; } }
if (range_contains(other, range->max)) { range->max = other->min; if (range->max > LLONG_MIN) { --range->max; } else { range->min = LLONG_MAX; } }}
/** Remove a single value from a range. */static void range_remove(struct df_range *range, long long value) { const struct df_range other = { .min = value, .max = value, }; range_subtract(range, &other);}
/** Compute the union of two ranges. */static void range_join(struct df_range *dest, const struct df_range *src) { dest->min = min_value(dest->min, src->min); dest->max = max_value(dest->max, src->max);}
/** * Types of ranges we track. */enum range_type { /** Search tree depth. */ DEPTH_RANGE, /** Group ID. */ GID_RANGE, /** Inode number. */ INUM_RANGE, /** Hard link count. */ LINKS_RANGE, /** File size. */ SIZE_RANGE, /** User ID. */ UID_RANGE, /** The number of range_types. */ RANGE_TYPES,};
/** Range type names. */static const char *const range_names[] = { [DEPTH_RANGE] = "-depth", [GID_RANGE] = "-gid", [INUM_RANGE] = "-inum", [LINKS_RANGE] = "-links", [SIZE_RANGE] = "-size", [UID_RANGE] = "-uid",};
/** * The data flow analysis domain. */struct df_domain { /** The predicates we track. */ enum df_pred preds[PRED_TYPES];
/** The value ranges we track. */ struct df_range ranges[RANGE_TYPES];
/** Bitmask of possible -types. */ unsigned int types; /** Bitmask of possible -xtypes. */ unsigned int xtypes;};
/** Set a data flow value to bottom. */static void df_init_bottom(struct df_domain *value) { for (int i = 0; i < PRED_TYPES; ++i) { value->preds[i] = PRED_BOTTOM; }
for (int i = 0; i < RANGE_TYPES; ++i) { range_init_bottom(&value->ranges[i]); }
value->types = 0; value->xtypes = 0;}
/** Determine whether a fact set is impossible. */static bool df_is_bottom(const struct df_domain *value) { for (int i = 0; i < RANGE_TYPES; ++i) { if (range_is_bottom(&value->ranges[i])) { return true; } }
for (int i = 0; i < PRED_TYPES; ++i) { if (value->preds[i] == PRED_BOTTOM) { return true; } }
if (!value->types || !value->xtypes) { return true; }
return false;}
/** Initialize some data flow value. */static void df_init_top(struct df_domain *value) { for (int i = 0; i < PRED_TYPES; ++i) { value->preds[i] = PRED_TOP; }
for (int i = 0; i < RANGE_TYPES; ++i) { range_init_top(&value->ranges[i]); }
value->types = ~0; value->xtypes = ~0;}
/** Check for the top element. */static bool df_is_top(const struct df_domain *value) { for (int i = 0; i < PRED_TYPES; ++i) { if (value->preds[i] != PRED_TOP) { return false; } }
for (int i = 0; i < RANGE_TYPES; ++i) { if (!range_is_top(&value->ranges[i])) { return false; } }
if (value->types != ~0U) { return false; }
if (value->xtypes != ~0U) { return false; }
return true;}
/** Compute the union of two fact sets. */static void df_join(struct df_domain *dest, const struct df_domain *src) { for (int i = 0; i < PRED_TYPES; ++i) { pred_join(&dest->preds[i], src->preds[i]); }
for (int i = 0; i < RANGE_TYPES; ++i) { range_join(&dest->ranges[i], &src->ranges[i]); }
dest->types |= src->types; dest->xtypes |= src->xtypes;}
/** * Optimizer state. */struct bfs_opt { /** The context we're optimizing. */ struct bfs_ctx *ctx; /** Optimization level (ctx->optlevel). */ int level; /** Recursion depth. */ int depth;
/** Whether to produce warnings. */ bool warn; /** Whether the result of this expression is ignored. */ bool ignore_result;
/** Data flow state before this expression is evaluated. */ struct df_domain before; /** Data flow state after this expression returns true. */ struct df_domain after_true; /** Data flow state after this expression returns false. */ struct df_domain after_false; /** Data flow state before any side-effecting expressions are evaluated. */ struct df_domain *impure;};
/** Log an optimization. */[[_printf(2, 3)]]static bool opt_debug(struct bfs_opt *opt, const char *format, ...) { if (bfs_debug_prefix(opt->ctx, DEBUG_OPT)) { for (int i = 0; i < opt->depth; ++i) { cfprintf(opt->ctx->cerr, "│ "); }
va_list args; va_start(args, format); cvfprintf(opt->ctx->cerr, format, args); va_end(args); return true; } else { return false; }}
/** Log a recursive call. */[[_printf(2, 3)]]static bool opt_enter(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth; if (depth > 0) { --opt->depth; }
bool debug = opt_debug(opt, "%s", depth > 0 ? "├─╮ " : ""); if (debug) { va_list args; va_start(args, format); cvfprintf(opt->ctx->cerr, format, args); va_end(args); }
opt->depth = depth + 1; return debug;}
/** Log a recursive return. */[[_printf(2, 3)]]static bool opt_leave(struct bfs_opt *opt, const char *format, ...) { bool debug = false; int depth = opt->depth;
if (format) { if (depth > 1) { opt->depth -= 2; }
debug = opt_debug(opt, "%s", depth > 1 ? "├─╯ " : ""); if (debug) { va_list args; va_start(args, format); cvfprintf(opt->ctx->cerr, format, args); va_end(args); } }
opt->depth = depth - 1; return debug;}
/** Log a shallow visit. */[[_printf(2, 3)]]static bool opt_visit(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth; if (depth > 0) { --opt->depth; }
bool debug = opt_debug(opt, "%s", depth > 0 ? "├─◯ " : ""); if (debug) { va_list args; va_start(args, format); cvfprintf(opt->ctx->cerr, format, args); va_end(args); }
opt->depth = depth; return debug;}
/** Log the deletion of an expression. */[[_printf(2, 3)]]static bool opt_delete(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth;
if (depth > 0) { --opt->depth; }
bool debug = opt_debug(opt, "%s", depth > 0 ? "├─✘ " : ""); if (debug) { va_list args; va_start(args, format); cvfprintf(opt->ctx->cerr, format, args); va_end(args); }
opt->depth = depth; return debug;}
typedef bool dump_fn(struct bfs_opt *opt, const char *format, ...);
/** Print a df_pred. */static void pred_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum pred_type type) { dump(opt, "${blu}%s${rs}: ", pred_names[type]);
FILE *file = opt->ctx->cerr->file; switch (value->preds[type]) { case PRED_BOTTOM: fprintf(file, "⊥\n"); break; case PRED_TOP: fprintf(file, "⊤\n"); break; case PRED_TRUE: fprintf(file, "true\n"); break; case PRED_FALSE: fprintf(file, "false\n"); break; }}
/** Print a df_range. */static void range_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum range_type type) { dump(opt, "${blu}%s${rs}: ", range_names[type]);
FILE *file = opt->ctx->cerr->file; const struct df_range *range = &value->ranges[type]; if (range_is_bottom(range)) { fprintf(file, "⊥\n"); } else if (range_is_top(range)) { fprintf(file, "⊤\n"); } else if (range->min == range->max) { fprintf(file, "%lld\n", range->min); } else { if (range->min == LLONG_MIN) { fprintf(file, "(-∞, "); } else { fprintf(file, "[%lld, ", range->min); } if (range->max == LLONG_MAX) { fprintf(file, "∞)\n"); } else { fprintf(file, "%lld]\n", range->max); } }}
/** Print a set of types. */static void types_dump(dump_fn *dump, struct bfs_opt *opt, const char *name, unsigned int types) { dump(opt, "${blu}%s${rs}: ", name);
FILE *file = opt->ctx->cerr->file; if (types == 0) { fprintf(file, " ⊥\n"); } else if (types == ~0U) { fprintf(file, " ⊤\n"); } else if (count_ones(types) < count_ones(~types)) { fprintf(file, " 0x%X\n", types); } else { fprintf(file, "~0x%X\n", ~types); }}
/** Calculate the number of lines of df_dump() output. */static int df_dump_lines(const struct df_domain *value) { int lines = 0;
for (int i = 0; i < PRED_TYPES; ++i) { lines += value->preds[i] != PRED_TOP; }
for (int i = 0; i < RANGE_TYPES; ++i) { lines += !range_is_top(&value->ranges[i]); }
lines += value->types != ~0U; lines += value->xtypes != ~0U;
return lines;}
/** Get the right debugging function for a df_dump() line. */static dump_fn *df_dump_line(int lines, int *line) { ++*line;
if (lines == 1) { return opt_visit; } else if (*line == 1) { return opt_enter; } else if (*line == lines) { return opt_leave; } else { return opt_debug; }}
/** Print a data flow value. */static void df_dump(struct bfs_opt *opt, const char *str, const struct df_domain *value) { if (df_is_bottom(value)) { opt_debug(opt, "%s: ⊥\n", str); return; } else if (df_is_top(value)) { opt_debug(opt, "%s: ⊤\n", str); return; }
if (!opt_debug(opt, "%s:\n", str)) { return; }
int lines = df_dump_lines(value); int line = 0;
for (int i = 0; i < PRED_TYPES; ++i) { if (value->preds[i] != PRED_TOP) { pred_dump(df_dump_line(lines, &line), opt, value, i); } }
for (int i = 0; i < RANGE_TYPES; ++i) { if (!range_is_top(&value->ranges[i])) { range_dump(df_dump_line(lines, &line), opt, value, i); } }
if (value->types != ~0U) { types_dump(df_dump_line(lines, &line), opt, "-type", value->types); }
if (value->xtypes != ~0U) { types_dump(df_dump_line(lines, &line), opt, "-xtype", value->xtypes); }}
/** Check if an expression is constant. */static bool is_const(const struct bfs_expr *expr) { return expr->eval_fn == eval_true || expr->eval_fn == eval_false;}
/** Warn about an expression. */[[_printf(3, 4)]]static bool opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) { if (!opt->warn) { return false; }
if (bfs_expr_is_parent(expr) || is_const(expr)) { return false; }
if (!bfs_expr_warning(opt->ctx, expr)) { return false; }
va_list args; va_start(args, format); bfs_vwarning(opt->ctx, format, args); va_end(args);
return true;}
/** Remove and return an expression's children. */static void foster_children(struct bfs_expr *expr, struct bfs_exprs *children) { bfs_assert(bfs_expr_is_parent(expr));
SLIST_INIT(children); SLIST_EXTEND(children, &expr->children);
expr->persistent_fds = 0; expr->ephemeral_fds = 0; expr->pure = true;}
/** Return an expression's only child. */static struct bfs_expr *only_child(struct bfs_expr *expr) { bfs_assert(bfs_expr_is_parent(expr)); struct bfs_expr *child = bfs_expr_children(expr); bfs_assert(child && !child->next); return child;}
/** Foster an expression's only child. */static struct bfs_expr *foster_only_child(struct bfs_expr *expr) { struct bfs_expr *child = only_child(expr); struct bfs_exprs children; foster_children(expr, &children); return child;}
/** An expression visitor. */struct visitor;
/** An expression-visiting function. */typedef struct bfs_expr *visit_fn(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor);
/** An entry in a visitor lookup table. */struct visitor_table { /** The evaluation function to match on. */ bfs_eval_fn *eval_fn; /** The visitor function. */ visit_fn *visit;};
/** Look up a visitor in a table. */static visit_fn *look_up_visitor(const struct bfs_expr *expr, const struct visitor_table table[]) { for (size_t i = 0; table[i].eval_fn; ++i) { if (expr->eval_fn == table[i].eval_fn) { return table[i].visit; } }
return NULL;}
struct visitor { /** The name of this visitor. */ const char *name;
/** A function to call before visiting children. */ visit_fn *enter; /** The default visitor. */ visit_fn *visit; /** A function to call after visiting children. */ visit_fn *leave;
/** A visitor lookup table. */ const struct visitor_table *table;};
/** Recursive visitor implementation. */static struct bfs_expr *visit_deep(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor);
/** Visit a negation. */static struct bfs_expr *visit_not(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_expr *rhs = foster_only_child(expr);
struct bfs_opt nested = *opt; rhs = visit_deep(&nested, rhs, visitor); if (!rhs) { return NULL; }
opt->after_true = nested.after_false; opt->after_false = nested.after_true;
bfs_expr_append(expr, rhs); return expr;}
/** Visit a conjunction. */static struct bfs_expr *visit_and(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
// Base case (-and) == (-true) df_init_bottom(&opt->after_false); struct bfs_opt nested = *opt;
drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { nested.ignore_result = false; }
child = visit_deep(&nested, child, visitor); if (!child) { return NULL; }
df_join(&opt->after_false, &nested.after_false); nested.before = nested.after_true;
bfs_expr_append(expr, child); }
opt->after_true = nested.after_true;
return expr;}
/** Visit a disjunction. */static struct bfs_expr *visit_or(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
// Base case (-or) == (-false) df_init_bottom(&opt->after_true); struct bfs_opt nested = *opt;
drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { nested.ignore_result = false; }
child = visit_deep(&nested, child, visitor); if (!child) { return NULL; }
df_join(&opt->after_true, &nested.after_true); nested.before = nested.after_false;
bfs_expr_append(expr, child); }
opt->after_false = nested.after_false;
return expr;}
/** Visit a comma expression. */static struct bfs_expr *visit_comma(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
struct bfs_opt nested = *opt;
drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { nested.ignore_result = true; }
child = visit_deep(&nested, child, visitor); if (!child) { return NULL; }
nested.before = nested.after_true; df_join(&nested.before, &nested.after_false);
bfs_expr_append(expr, child); }
opt->after_true = nested.after_true; opt->after_false = nested.after_false;
return expr;}
/** Default enter() function. */static struct bfs_expr *visit_enter(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt_enter(opt, "%pe\n", expr); opt->after_true = opt->before; opt->after_false = opt->before; return expr;}
/** Default leave() function. */static struct bfs_expr *visit_leave(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt_leave(opt, "%pe\n", expr); return expr;}
static struct bfs_expr *visit_deep(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { bool entered = false;
visit_fn *enter = visitor->enter ? visitor->enter : visit_enter; visit_fn *leave = visitor->leave ? visitor->leave : visit_leave;
static const struct visitor_table table[] = { {eval_not, visit_not}, {eval_and, visit_and}, {eval_or, visit_or}, {eval_comma, visit_comma}, {NULL, NULL}, }; visit_fn *recursive = look_up_visitor(expr, table); if (recursive) { if (!entered) { expr = enter(opt, expr, visitor); if (!expr) { return NULL; } entered = true; }
expr = recursive(opt, expr, visitor); if (!expr) { return NULL; } }
visit_fn *general = visitor->visit; if (general) { if (!entered) { expr = enter(opt, expr, visitor); if (!expr) { return NULL; } entered = true; }
expr = general(opt, expr, visitor); if (!expr) { return NULL; } }
visit_fn *specific = look_up_visitor(expr, visitor->table); if (specific) { if (!entered) { expr = enter(opt, expr, visitor); if (!expr) { return NULL; } entered = true; }
expr = specific(opt, expr, visitor); if (!expr) { return NULL; } }
if (entered) { expr = leave(opt, expr, visitor); } else { opt_visit(opt, "%pe\n", expr); }
return expr;}
/** Visit an expression recursively. */static struct bfs_expr *visit(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt_enter(opt, "%s()\n", visitor->name); expr = visit_deep(opt, expr, visitor); opt_leave(opt, "\n"); return expr;}
/** Visit an expression non-recursively. */static struct bfs_expr *visit_shallow(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { visit_fn *general = visitor->visit; if (expr && general) { expr = general(opt, expr, visitor); }
if (!expr) { return NULL; }
visit_fn *specific = look_up_visitor(expr, visitor->table); if (specific) { expr = specific(opt, expr, visitor); }
return expr;}
/** Annotate -{execut,read,writ}able. */static struct bfs_expr *annotate_access(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { expr->probability = 1.0; if (expr->num & R_OK) { expr->probability *= 0.99; } if (expr->num & W_OK) { expr->probability *= 0.8; } if (expr->num & X_OK) { expr->probability *= 0.2; }
return expr;}
/** Annotate -empty. */static struct bfs_expr *annotate_empty(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (opt->level >= 4) { // Since -empty attempts to open and read directories, it may // have side effects such as reporting permission errors, and // thus shouldn't be re-ordered without aggressive optimizations expr->pure = true; }
return expr;}
/** Annotate -exec. */static struct bfs_expr *annotate_exec(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (expr->exec->flags & BFS_EXEC_MULTI) { expr->always_true = true; } else { expr->cost = 1000000.0; }
return expr;}
/** Annotate -name/-lname/-path. */static struct bfs_expr *annotate_fnmatch(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (expr->literal) { expr->probability = 0.1; } else { expr->probability = 0.5; }
return expr;}
/** Annotate -f?print. */static struct bfs_expr *annotate_fprint(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { const struct colors *colors = expr->cfile->colors; expr->calls_stat = colors && colors_need_stat(colors); return expr;}
/** Estimate probability for -x?type. */static void estimate_type_probability(struct bfs_expr *expr) { unsigned int types = expr->num;
expr->probability = 0.0; if (types & (1 << BFS_BLK)) { expr->probability += 0.00000721183; } if (types & (1 << BFS_CHR)) { expr->probability += 0.0000499855; } if (types & (1 << BFS_DIR)) { expr->probability += 0.114475; } if (types & (1 << BFS_DOOR)) { expr->probability += 0.000001; } if (types & (1 << BFS_FIFO)) { expr->probability += 0.00000248684; } if (types & (1 << BFS_REG)) { expr->probability += 0.859772; } if (types & (1 << BFS_LNK)) { expr->probability += 0.0256816; } if (types & (1 << BFS_SOCK)) { expr->probability += 0.0000116881; } if (types & (1 << BFS_WHT)) { expr->probability += 0.000001; }}
/** Annotate -type. */static struct bfs_expr *annotate_type(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { estimate_type_probability(expr); return expr;}
/** Annotate -xtype. */static struct bfs_expr *annotate_xtype(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (opt->level >= 4) { // Since -xtype dereferences symbolic links, it may have side // effects such as reporting permission errors, and thus // shouldn't be re-ordered without aggressive optimizations expr->pure = true; }
estimate_type_probability(expr); return expr;}
/** Annotate a negation. */static struct bfs_expr *annotate_not(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_expr *rhs = only_child(expr); expr->pure = rhs->pure; expr->always_true = rhs->always_false; expr->always_false = rhs->always_true; expr->cost = rhs->cost; expr->probability = 1.0 - rhs->probability; return expr;}
/** Annotate a conjunction. */static struct bfs_expr *annotate_and(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { expr->pure = true; expr->always_true = true; expr->always_false = false; expr->cost = 0.0; expr->probability = 1.0;
for_expr (child, expr) { expr->pure &= child->pure; expr->always_true &= child->always_true; expr->always_false |= child->always_false; expr->cost += expr->probability * child->cost; expr->probability *= child->probability; }
return expr;}
/** Annotate a disjunction. */static struct bfs_expr *annotate_or(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { expr->pure = true; expr->always_true = false; expr->always_false = true; expr->cost = 0.0;
float false_prob = 1.0; for_expr (child, expr) { expr->pure &= child->pure; expr->always_true |= child->always_true; expr->always_false &= child->always_false; expr->cost += false_prob * child->cost; false_prob *= (1.0 - child->probability); } expr->probability = 1.0 - false_prob;
return expr;}
/** Annotate a comma expression. */static struct bfs_expr *annotate_comma(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { expr->pure = true; expr->cost = 0.0;
for_expr (child, expr) { expr->pure &= child->pure; expr->always_true = child->always_true; expr->always_false = child->always_false; expr->cost += child->cost; expr->probability = child->probability; }
return expr;}
/** Annotate an arbitrary expression. */static struct bfs_expr *annotate_visit(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { /** Table of pure expressions. */ static bfs_eval_fn *const pure[] = { eval_access, eval_acl, eval_capable, eval_depth, eval_false, eval_flags, eval_fstype, eval_gid, eval_hidden, eval_inum, eval_links, eval_lname, eval_name, eval_newer, eval_nogroup, eval_nouser, eval_path, eval_perm, eval_regex, eval_samefile, eval_size, eval_sparse, eval_time, eval_true, eval_type, eval_uid, eval_used, eval_xattr, eval_xattrname, };
expr->pure = false; for (size_t i = 0; i < countof(pure); ++i) { if (expr->eval_fn == pure[i]) { expr->pure = true; break; } }
/** Table of always-true expressions. */ static bfs_eval_fn *const always_true[] = { eval_fls, eval_fprint, eval_fprint0, eval_fprintf, eval_fprintx, eval_limit, eval_prune, eval_true, // Non-returning eval_exit, eval_quit, };
expr->always_true = false; for (size_t i = 0; i < countof(always_true); ++i) { if (expr->eval_fn == always_true[i]) { expr->always_true = true; break; } }
/** Table of always-false expressions. */ static bfs_eval_fn *const always_false[] = { eval_false, // Non-returning eval_exit, eval_quit, };
expr->always_false = false; for (size_t i = 0; i < countof(always_false); ++i) { if (expr->eval_fn == always_false[i]) { expr->always_false = true; break; } }
/** Table of stat-calling primaries. */ static bfs_eval_fn *const calls_stat[] = { eval_empty, eval_flags, eval_fls, eval_fprintf, eval_fstype, eval_gid, eval_inum, eval_links, eval_newer, eval_nogroup, eval_nouser, eval_perm, eval_samefile, eval_size, eval_sparse, eval_time, eval_uid, eval_used, eval_xattr, eval_xattrname, };
expr->calls_stat = false; for (size_t i = 0; i < countof(calls_stat); ++i) { if (expr->eval_fn == calls_stat[i]) { expr->calls_stat = true; break; } }
#define FAST_COST 40.0#define FNMATCH_COST 400.0#define STAT_COST 1000.0#define PRINT_COST 20000.0
/** Table of expression costs. */ static const struct { bfs_eval_fn *eval_fn; float cost; } costs[] = { {eval_access, STAT_COST}, {eval_acl, STAT_COST}, {eval_capable, STAT_COST}, {eval_empty, 2 * STAT_COST}, // readdir() is worse than stat() {eval_flags, STAT_COST}, {eval_fls, PRINT_COST}, {eval_fprint, PRINT_COST}, {eval_fprint0, PRINT_COST}, {eval_fprintf, PRINT_COST}, {eval_fprintx, PRINT_COST}, {eval_fstype, STAT_COST}, {eval_gid, STAT_COST}, {eval_inum, STAT_COST}, {eval_links, STAT_COST}, {eval_lname, FNMATCH_COST}, {eval_name, FNMATCH_COST}, {eval_newer, STAT_COST}, {eval_nogroup, STAT_COST}, {eval_nouser, STAT_COST}, {eval_path, FNMATCH_COST}, {eval_perm, STAT_COST}, {eval_samefile, STAT_COST}, {eval_size, STAT_COST}, {eval_sparse, STAT_COST}, {eval_time, STAT_COST}, {eval_uid, STAT_COST}, {eval_used, STAT_COST}, {eval_xattr, STAT_COST}, {eval_xattrname, STAT_COST}, };
expr->cost = FAST_COST; for (size_t i = 0; i < countof(costs); ++i) { if (expr->eval_fn == costs[i].eval_fn) { expr->cost = costs[i].cost; break; } }
/** Table of expression probabilities. */ static const struct { /** The evaluation function with this cost. */ bfs_eval_fn *eval_fn; /** The matching probability. */ float probability; } probs[] = { {eval_acl, 0.00002}, {eval_capable, 0.000002}, {eval_empty, 0.01}, {eval_false, 0.0}, {eval_hidden, 0.01}, {eval_nogroup, 0.01}, {eval_nouser, 0.01}, {eval_samefile, 0.01}, {eval_true, 1.0}, {eval_xattr, 0.01}, {eval_xattrname, 0.01}, };
expr->probability = 0.5; for (size_t i = 0; i < countof(probs); ++i) { if (expr->eval_fn == probs[i].eval_fn) { expr->probability = probs[i].probability; break; } }
return expr;}
/** * Annotating visitor. */static const struct visitor annotate = { .name = "annotate", .visit = annotate_visit, .table = (const struct visitor_table[]) { {eval_access, annotate_access}, {eval_empty, annotate_empty}, {eval_exec, annotate_exec}, {eval_fprint, annotate_fprint}, {eval_lname, annotate_fnmatch}, {eval_name, annotate_fnmatch}, {eval_path, annotate_fnmatch}, {eval_type, annotate_type}, {eval_xtype, annotate_xtype},
{eval_not, annotate_not}, {eval_and, annotate_and}, {eval_or, annotate_or}, {eval_comma, annotate_comma},
{NULL, NULL}, },};
/** Create a constant expression. */static struct bfs_expr *opt_const(struct bfs_opt *opt, bool value) { static bfs_eval_fn *const fns[] = {eval_false, eval_true}; static char *fake_args[] = {"-false", "-true"};
struct bfs_expr *expr = bfs_expr_new(opt->ctx, fns[value], 1, &fake_args[value], BFS_TEST); return visit_shallow(opt, expr, &annotate);}
/** Negate an expression, keeping it canonical. */static struct bfs_expr *negate_expr(struct bfs_opt *opt, struct bfs_expr *expr, char **argv) { if (expr->eval_fn == eval_not) { return only_child(expr); } else if (expr->eval_fn == eval_true) { return opt_const(opt, false); } else if (expr->eval_fn == eval_false) { return opt_const(opt, true); }
struct bfs_expr *ret = bfs_expr_new(opt->ctx, eval_not, 1, argv, BFS_OPERATOR); if (!ret) { return NULL; }
bfs_expr_append(ret, expr); return visit_shallow(opt, ret, &annotate);}
/** Sink negations into a conjunction/disjunction using De Morgan's laws. */static struct bfs_expr *sink_not_andor(struct bfs_opt *opt, struct bfs_expr *expr) { opt_debug(opt, "De Morgan's laws\n");
char **argv = expr->argv; expr = only_child(expr); opt_enter(opt, "%pe\n", expr);
if (expr->eval_fn == eval_and) { expr->eval_fn = eval_or; expr->argv = &fake_or_arg; } else { bfs_assert(expr->eval_fn == eval_or); expr->eval_fn = eval_and; expr->argv = &fake_and_arg; }
struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { opt_enter(opt, "%pe\n", child);
child = negate_expr(opt, child, argv); if (!child) { return NULL; }
opt_leave(opt, "%pe\n", child); bfs_expr_append(expr, child); }
opt_leave(opt, "%pe\n", expr); return visit_shallow(opt, expr, &annotate);}
/** Sink a negation into a comma expression. */static struct bfs_expr *sink_not_comma(struct bfs_opt *opt, struct bfs_expr *expr) { char **argv = expr->argv; expr = only_child(expr); opt_enter(opt, "%pe\n", expr);
bfs_assert(expr->eval_fn == eval_comma);
struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { opt_enter(opt, "%pe\n", child); opt_debug(opt, "sink\n");
child = negate_expr(opt, child, argv); if (!child) { return NULL; }
opt_leave(opt, "%pe\n", child); } else { opt_visit(opt, "%pe\n", child); }
bfs_expr_append(expr, child); }
opt_leave(opt, "%pe\n", expr); return visit_shallow(opt, expr, &annotate);}
/** Canonicalize a negation. */static struct bfs_expr *canonicalize_not(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_expr *rhs = only_child(expr);
if (rhs->eval_fn == eval_not) { opt_debug(opt, "double negation\n"); return only_child(rhs); } else if (rhs->eval_fn == eval_and || rhs->eval_fn == eval_or) { return sink_not_andor(opt, expr); } else if (rhs->eval_fn == eval_comma) { return sink_not_comma(opt, expr); } else if (is_const(rhs)) { opt_debug(opt, "constant propagation\n"); return opt_const(opt, rhs->eval_fn == eval_false); } else { return expr; }}
/** Canonicalize an associative operator. */static struct bfs_expr *canonicalize_assoc(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
struct bfs_exprs flat; SLIST_INIT(&flat);
drain_slist (struct bfs_expr, child, &children) { if (child->eval_fn == expr->eval_fn) { struct bfs_expr *head = SLIST_HEAD(&child->children); struct bfs_expr *tail = SLIST_TAIL(&child->children);
if (!head) { opt_delete(opt, "%pe [empty]\n", child); } else { opt_enter(opt, "%pe\n", child); opt_debug(opt, "associativity\n"); if (head == tail) { opt_leave(opt, "%pe\n", head); } else if (head->next == tail) { opt_leave(opt, "%pe %pe\n", head, tail); } else { opt_leave(opt, "%pe ... %pe\n", head, tail); } }
SLIST_EXTEND(&flat, &child->children); } else { opt_visit(opt, "%pe\n", child); SLIST_APPEND(&flat, child); } }
bfs_expr_extend(expr, &flat);
return visit_shallow(opt, expr, &annotate);}
/** * Canonicalizing visitor. */static const struct visitor canonicalize = { .name = "canonicalize", .table = (const struct visitor_table[]) { {eval_not, canonicalize_not}, {eval_and, canonicalize_assoc}, {eval_or, canonicalize_assoc}, {eval_comma, canonicalize_assoc}, {NULL, NULL}, },};
/** Calculate the cost of an ordered pair of expressions. */static float expr_cost(const struct bfs_expr *parent, const struct bfs_expr *lhs, const struct bfs_expr *rhs) { // https://cs.stackexchange.com/a/66921/21004 float prob = lhs->probability; if (parent->eval_fn == eval_or) { prob = 1.0 - prob; } return lhs->cost + prob * rhs->cost;}
/** Sort a block of expressions. */static void sort_exprs(struct bfs_opt *opt, struct bfs_expr *parent, struct bfs_exprs *exprs) { if (!exprs->head || !exprs->head->next) { return; }
struct bfs_exprs left, right; SLIST_INIT(&left); SLIST_INIT(&right);
// Split for (struct bfs_expr *hare = exprs->head; hare && (hare = hare->next); hare = hare->next) { struct bfs_expr *tortoise = SLIST_POP(exprs); SLIST_APPEND(&left, tortoise); } SLIST_EXTEND(&right, exprs);
// Recurse sort_exprs(opt, parent, &left); sort_exprs(opt, parent, &right);
// Merge while (!SLIST_EMPTY(&left) && !SLIST_EMPTY(&right)) { struct bfs_expr *lhs = left.head; struct bfs_expr *rhs = right.head;
float cost = expr_cost(parent, lhs, rhs); float swapped = expr_cost(parent, rhs, lhs);
if (cost <= swapped) { SLIST_POP(&left); SLIST_APPEND(exprs, lhs); } else { opt_enter(opt, "%pe %pe [${ylw}%g${rs}]\n", lhs, rhs, cost); SLIST_POP(&right); SLIST_APPEND(exprs, rhs); opt_leave(opt, "%pe %pe [${ylw}%g${rs}]\n", rhs, lhs, swapped); } } SLIST_EXTEND(exprs, &left); SLIST_EXTEND(exprs, &right);}
/** Reorder children to reduce cost. */static struct bfs_expr *reorder_andor(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
// Split into blocks of consecutive pure/impure expressions, and sort // the pure blocks struct bfs_exprs pure; SLIST_INIT(&pure);
drain_slist (struct bfs_expr, child, &children) { if (child->pure) { SLIST_APPEND(&pure, child); } else { sort_exprs(opt, expr, &pure); bfs_expr_extend(expr, &pure); bfs_expr_append(expr, child); } } sort_exprs(opt, expr, &pure); bfs_expr_extend(expr, &pure);
return visit_shallow(opt, expr, &annotate);}
/** * Reordering visitor. */static const struct visitor reorder = { .name = "reorder", .table = (const struct visitor_table[]) { {eval_and, reorder_andor}, {eval_or, reorder_andor}, {NULL, NULL}, },};
/** Transfer function for simple predicates. */static void data_flow_pred(struct bfs_opt *opt, enum pred_type pred, bool value) { constrain_pred(&opt->after_true.preds[pred], value); constrain_pred(&opt->after_false.preds[pred], !value);}
/** Transfer function for icmp-style ([+-]N) expressions. */static void data_flow_icmp(struct bfs_opt *opt, const struct bfs_expr *expr, enum range_type type) { long long value = expr->num; struct df_range range;
switch (expr->int_cmp) { case BFS_INT_EQUAL: range.min = range.max = value; break;
case BFS_INT_LESS: range.min = LLONG_MIN; range.max = value; range_remove(&range, value); break;
case BFS_INT_GREATER: range.min = value; range.max = LLONG_MAX; range_remove(&range, value); break; }
struct df_range *true_range = &opt->after_true.ranges[type]; range_intersect(true_range, &range);
struct df_range *false_range = &opt->after_false.ranges[type]; range_subtract(false_range, &range);}
/** Transfer function for -{execut,read,writ}able. */static struct bfs_expr *data_flow_access(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { switch (expr->num) { case R_OK: data_flow_pred(opt, READABLE_PRED, true); break; case W_OK: data_flow_pred(opt, WRITABLE_PRED, true); break; case X_OK: data_flow_pred(opt, EXECUTABLE_PRED, true); break; default: bfs_bug("Unknown access() mode %lld", expr->num); break; }
return expr;}
/** Transfer function for -empty. */static struct bfs_expr *data_flow_empty(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt->after_true.types &= (1 << BFS_REG) | (1 << BFS_DIR);
if (opt->before.types == (1 << BFS_REG)) { constrain_range(&opt->after_true.ranges[SIZE_RANGE], 0); range_remove(&opt->after_false.ranges[SIZE_RANGE], 0); }
return expr;}
/** Transfer function for -gid. */static struct bfs_expr *data_flow_gid(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct df_range *range = &opt->after_true.ranges[GID_RANGE]; if (range->min == range->max) { gid_t gid = range->min; bool nogroup = !bfs_getgrgid(opt->ctx->groups, gid); if (errno == 0) { constrain_pred(&opt->after_true.preds[NOGROUP_PRED], nogroup); } }
return expr;}
/** Transfer function for -inum. */static struct bfs_expr *data_flow_inum(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct df_range *range = &opt->after_true.ranges[INUM_RANGE]; if (range->min == range->max) { expr->probability = 0.01; } else { expr->probability = 0.5; }
return expr;}
/** Transfer function for -links. */static struct bfs_expr *data_flow_links(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct df_range *range = &opt->after_true.ranges[LINKS_RANGE]; if (range_contains(range, 1)) { expr->probability = 0.99; } else { expr->probability = 0.5; }
return expr;}
/** Transfer function for -lname. */static struct bfs_expr *data_flow_lname(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt->after_true.types &= 1 << BFS_LNK; return expr;}
/** Transfer function for -samefile. */static struct bfs_expr *data_flow_samefile(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct df_range *true_range = &opt->after_true.ranges[INUM_RANGE]; constrain_range(true_range, expr->ino);
struct df_range *false_range = &opt->after_false.ranges[INUM_RANGE]; range_remove(false_range, expr->ino);
return expr;}
/** Transfer function for -size. */static struct bfs_expr *data_flow_size(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { long long size = expr->num; long long factor = bfs_size_unit_factor(expr->size_unit);
struct df_range range; range_init_bottom(&range);
if (size - 1 <= LLONG_MAX / factor) { range.min = factor * (size - 1);
if (range.min <= LLONG_MAX - factor) { range.max = range.min + factor; } else { range.max = LLONG_MAX; }
range_remove(&range, range.min); }
switch (expr->int_cmp) { case BFS_INT_EQUAL: break;
case BFS_INT_LESS: if (range_is_bottom(&range)) { range_init_top(&range); } else { range.max = range.min; range.min = LLONG_MIN; range_remove(&range, range.max); } break;
case BFS_INT_GREATER: if (!range_is_bottom(&range)) { range.min = range.max; range.max = LLONG_MAX; range_remove(&range, range.min); } break; }
struct df_range *true_range = &opt->after_true.ranges[SIZE_RANGE]; range_intersect(true_range, &range);
struct df_range *false_range = &opt->after_false.ranges[SIZE_RANGE]; range_subtract(false_range, &range);
if (true_range->min == true_range->max) { expr->probability = 0.01; } else { expr->probability = 0.5; }
return expr;}
/** Transfer function for -type. */static struct bfs_expr *data_flow_type(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt->after_true.types &= expr->num; opt->after_false.types &= ~expr->num; return expr;}
/** Transfer function for -uid. */static struct bfs_expr *data_flow_uid(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct df_range *range = &opt->after_true.ranges[UID_RANGE]; if (range->min == range->max) { uid_t uid = range->min; bool nouser = !bfs_getpwuid(opt->ctx->users, uid); if (errno == 0) { constrain_pred(&opt->after_true.preds[NOUSER_PRED], nouser); } }
return expr;}
/** Transfer function for -xtype. */static struct bfs_expr *data_flow_xtype(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { opt->after_true.xtypes &= expr->num; opt->after_false.xtypes &= ~expr->num; return expr;}
/** Data flow visitor entry. */static struct bfs_expr *data_flow_enter(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { visit_enter(opt, expr, visitor);
df_dump(opt, "before", &opt->before);
if (!bfs_expr_is_parent(expr) && !expr->pure) { df_join(opt->impure, &opt->before); df_dump(opt, "impure", opt->impure); }
return expr;}
/** Data flow visitor exit. */static struct bfs_expr *data_flow_leave(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (expr->always_true) { expr->probability = 1.0; df_init_bottom(&opt->after_false); }
if (expr->always_false) { expr->probability = 0.0; df_init_bottom(&opt->after_true); }
df_dump(opt, "after true", &opt->after_true); df_dump(opt, "after false", &opt->after_false);
if (df_is_bottom(&opt->after_false)) { if (!expr->pure) { expr->always_true = true; expr->probability = 1.0; } else if (expr->eval_fn != eval_true) { opt_warning(opt, expr, "This expression is always true.\n\n"); opt_debug(opt, "pure, always true\n"); expr = opt_const(opt, true); if (!expr) { return NULL; } } }
if (df_is_bottom(&opt->after_true)) { if (!expr->pure) { expr->always_false = true; expr->probability = 0.0; } else if (expr->eval_fn != eval_false) { opt_warning(opt, expr, "This expression is always false.\n\n"); opt_debug(opt, "pure, always false\n"); expr = opt_const(opt, false); if (!expr) { return NULL; } } }
return visit_leave(opt, expr, visitor);}
/** Ignore an expression (and possibly warn/prompt). */static struct bfs_expr *opt_ignore(struct bfs_opt *opt, struct bfs_expr *expr, bool delete) { if (delete) { opt_delete(opt, "%pe [ignored result]\n", expr); } else { opt_debug(opt, "ignored result\n"); }
if (expr->kind != BFS_TEST) { goto done; }
if (!opt_warning(opt, expr, "The result of this expression is ignored.\n")) { goto done; }
struct bfs_ctx *ctx = opt->ctx; if (ctx->interactive && ctx->dangerous) { bfs_warning(ctx, "Do you want to continue? "); if (ynprompt() <= 0) { errno = 0; return NULL; } }
fprintf(stderr, "\n");
done: if (!delete && expr->pure) { // If we're not deleting the expression entirely, replace it with -false expr = opt_const(opt, false); } return expr;}
/** Data flow visitor function. */static struct bfs_expr *data_flow_visit(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (opt->ignore_result) { expr = opt_ignore(opt, expr, false); if (!expr) { return NULL; } }
if (df_is_bottom(&opt->before)) { opt_debug(opt, "unreachable\n"); opt_warning(opt, expr, "This expression is unreachable.\n\n"); expr = opt_const(opt, false); if (!expr) { return NULL; } }
/** Table of simple predicates. */ static const struct { bfs_eval_fn *eval_fn; enum pred_type pred; } preds[] = { {eval_acl, ACL_PRED}, {eval_capable, CAPABLE_PRED}, {eval_empty, EMPTY_PRED}, {eval_hidden, HIDDEN_PRED}, {eval_nogroup, NOGROUP_PRED}, {eval_nouser, NOUSER_PRED}, {eval_sparse, SPARSE_PRED}, {eval_xattr, XATTR_PRED}, };
for (size_t i = 0; i < countof(preds); ++i) { if (preds[i].eval_fn == expr->eval_fn) { data_flow_pred(opt, preds[i].pred, true); break; } }
/** Table of simple range comparisons. */ static const struct { bfs_eval_fn *eval_fn; enum range_type range; } ranges[] = { {eval_depth, DEPTH_RANGE}, {eval_gid, GID_RANGE}, {eval_inum, INUM_RANGE}, {eval_links, LINKS_RANGE}, {eval_uid, UID_RANGE}, };
for (size_t i = 0; i < countof(ranges); ++i) { if (ranges[i].eval_fn == expr->eval_fn) { data_flow_icmp(opt, expr, ranges[i].range); break; } }
return expr;}
/** * Data flow visitor. */static const struct visitor data_flow = { .name = "data_flow", .enter = data_flow_enter, .visit = data_flow_visit, .leave = data_flow_leave, .table = (const struct visitor_table[]) { {eval_access, data_flow_access}, {eval_empty, data_flow_empty}, {eval_gid, data_flow_gid}, {eval_inum, data_flow_inum}, {eval_links, data_flow_links}, {eval_lname, data_flow_lname}, {eval_samefile, data_flow_samefile}, {eval_size, data_flow_size}, {eval_type, data_flow_type}, {eval_uid, data_flow_uid}, {eval_xtype, data_flow_xtype}, {NULL, NULL}, },};
/** Simplify a negation. */static struct bfs_expr *simplify_not(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { if (opt->ignore_result) { opt_debug(opt, "ignored result\n"); expr = only_child(expr); }
return expr;}
/** Lift negations out of a conjunction/disjunction using De Morgan's laws. */static struct bfs_expr *lift_andor_not(struct bfs_opt *opt, struct bfs_expr *expr) { // Only lift negations if it would reduce the number of (-not) expressions size_t added = 0, removed = 0; for_expr (child, expr) { if (child->eval_fn == eval_not) { ++removed; } else { ++added; } } if (added >= removed) { return visit_shallow(opt, expr, &annotate); }
opt_debug(opt, "De Morgan's laws\n");
if (expr->eval_fn == eval_and) { expr->eval_fn = eval_or; expr->argv = &fake_or_arg; } else { bfs_assert(expr->eval_fn == eval_or); expr->eval_fn = eval_and; expr->argv = &fake_and_arg; }
struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { opt_enter(opt, "%pe\n", child);
child = negate_expr(opt, child, &fake_not_arg); if (!child) { return NULL; }
opt_leave(opt, "%pe\n", child); bfs_expr_append(expr, child); }
expr = visit_shallow(opt, expr, &annotate); if (!expr) { return NULL; }
return negate_expr(opt, expr, &fake_not_arg);}
/** Get the first ignorable expression in a conjunction/disjunction. */static struct bfs_expr *first_ignorable(struct bfs_opt *opt, struct bfs_expr *expr) { if (opt->level < 2 || !opt->ignore_result) { return NULL; }
struct bfs_expr *ret = NULL; for_expr (child, expr) { if (!child->pure) { ret = NULL; } else if (!ret) { ret = child; } }
return ret;}
/** Simplify a conjunction. */static struct bfs_expr *simplify_and(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_expr *ignorable = first_ignorable(opt, expr); bool ignore = false;
struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { if (child == ignorable) { ignore = true; }
if (ignore) { if (!opt_ignore(opt, child, true)) { return NULL; } continue; }
if (child->eval_fn == eval_true) { opt_delete(opt, "%pe [conjunction elimination]\n", child); continue; }
opt_visit(opt, "%pe\n", child); bfs_expr_append(expr, child);
if (child->always_false) { drain_slist (struct bfs_expr, dead, &children) { opt_delete(opt, "%pe [short-circuit]\n", dead); } } }
struct bfs_expr *child = bfs_expr_children(expr); if (!child) { opt_debug(opt, "nullary identity\n"); return opt_const(opt, true); } else if (!child->next) { opt_debug(opt, "unary identity\n"); return only_child(expr); }
return lift_andor_not(opt, expr);}
/** Simplify a disjunction. */static struct bfs_expr *simplify_or(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_expr *ignorable = first_ignorable(opt, expr); bool ignore = false;
struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { if (child == ignorable) { ignore = true; }
if (ignore) { if (!opt_ignore(opt, child, true)) { return NULL; } continue; }
if (child->eval_fn == eval_false) { opt_delete(opt, "%pe [disjunctive syllogism]\n", child); continue; }
opt_visit(opt, "%pe\n", child); bfs_expr_append(expr, child);
if (child->always_true) { drain_slist (struct bfs_expr, dead, &children) { opt_delete(opt, "%pe [short-circuit]\n", dead); } } }
struct bfs_expr *child = bfs_expr_children(expr); if (!child) { opt_debug(opt, "nullary identity\n"); return opt_const(opt, false); } else if (!child->next) { opt_debug(opt, "unary identity\n"); return only_child(expr); }
return lift_andor_not(opt, expr);}
/** Simplify a comma expression. */static struct bfs_expr *simplify_comma(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { struct bfs_exprs children; foster_children(expr, &children);
drain_slist (struct bfs_expr, child, &children) { if (opt->level >= 2 && child->pure && !SLIST_EMPTY(&children)) { if (!opt_ignore(opt, child, true)) { return NULL; } continue; }
opt_visit(opt, "%pe\n", child); bfs_expr_append(expr, child); }
struct bfs_expr *child = bfs_expr_children(expr); if (child && !child->next) { opt_debug(opt, "unary identity\n"); return only_child(expr); }
return expr;}
/** * Logical simplification visitor. */static const struct visitor simplify = { .name = "simplify", .table = (const struct visitor_table[]) { {eval_not, simplify_not}, {eval_and, simplify_and}, {eval_or, simplify_or}, {eval_comma, simplify_comma}, {NULL, NULL}, },};
/** Optimize an expression. */static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) { opt_enter(opt, "pass 0:\n"); expr = visit(opt, expr, &annotate); opt_leave(opt, NULL);
/** Table of optimization passes. */ static const struct { /** Minimum optlevel for this pass. */ int level; /** The visitor for this pass. */ const struct visitor *visitor; } passes[] = { {1, &canonicalize}, {3, &reorder}, {2, &data_flow}, {1, &simplify}, };
struct df_domain impure; df_init_top(&opt->after_true); df_init_top(&opt->after_false);
for (int i = 0; i < 3; ++i) { struct bfs_opt nested = *opt; nested.impure = &impure; impure = *opt->impure;
opt_enter(&nested, "pass %d:\n", i + 1);
for (size_t j = 0; j < countof(passes); ++j) { if (opt->level < passes[j].level) { continue; }
const struct visitor *visitor = passes[j].visitor;
// Skip reordering the first time through the passes, to // make warnings more understandable if (visitor == &reorder) { if (i == 0) { continue; } else { nested.warn = false; } }
expr = visit(&nested, expr, visitor); if (!expr) { return NULL; }
if (visitor == &data_flow) { opt->after_true = nested.after_true; opt->after_false = nested.after_false; } }
opt_leave(&nested, NULL);
if (!bfs_expr_is_parent(expr)) { break; } }
*opt->impure = impure; return expr;}
/** An expression predicate. */typedef bool expr_pred(const struct bfs_expr *expr);
/** Estimate the odds that a matching expression will be evaluated. */static float estimate_odds(const struct bfs_expr *expr, expr_pred *pred) { if (pred(expr)) { return 1.0; }
float nonmatch_odds = 1.0; float reached_odds = 1.0; for_expr (child, expr) { float child_odds = estimate_odds(child, pred); nonmatch_odds *= 1.0 - reached_odds * child_odds;
if (expr->eval_fn == eval_and) { reached_odds *= child->probability; } else if (expr->eval_fn == eval_or) { reached_odds *= 1.0 - child->probability; } }
return 1.0 - nonmatch_odds;}
/** Whether an expression calls stat(). */static bool calls_stat(const struct bfs_expr *expr) { return expr->calls_stat;}
/** Estimate the odds of calling stat(). */static float estimate_stat_odds(struct bfs_ctx *ctx) { if (ctx->unique) { return 1.0; }
float nostat_odds = 1.0 - estimate_odds(ctx->exclude, calls_stat);
float reached_odds = 1.0 - ctx->exclude->probability; float expr_odds = estimate_odds(ctx->expr, calls_stat); nostat_odds *= 1.0 - reached_odds * expr_odds;
return 1.0 - nostat_odds;}
/** Matches -(exec|ok) ... \; */static bool single_exec(const struct bfs_expr *expr) { return expr->eval_fn == eval_exec && !(expr->exec->flags & BFS_EXEC_MULTI);}
int bfs_optimize(struct bfs_ctx *ctx) { bfs_ctx_dump(ctx, DEBUG_OPT);
struct df_domain impure; df_init_bottom(&impure);
struct bfs_opt opt = { .ctx = ctx, .level = ctx->optlevel, .depth = 0, .warn = ctx->warn, .ignore_result = false, .impure = &impure, }; df_init_top(&opt.before);
ctx->exclude = optimize(&opt, ctx->exclude); if (!ctx->exclude) { return -1; }
// Only non-excluded files are evaluated opt.before = opt.after_false; opt.ignore_result = true;
struct df_range *depth = &opt.before.ranges[DEPTH_RANGE]; if (ctx->mindepth > 0) { constrain_min(depth, ctx->mindepth); } if (ctx->maxdepth < INT_MAX) { constrain_max(depth, ctx->maxdepth); }
ctx->expr = optimize(&opt, ctx->expr); if (!ctx->expr) { return -1; }
if (opt.level >= 2 && df_is_bottom(&impure)) { bfs_warning(ctx, "This command won't do anything.\n\n"); }
const struct df_range *impure_depth = &impure.ranges[DEPTH_RANGE]; long long mindepth = impure_depth->min; long long maxdepth = impure_depth->max;
opt_enter(&opt, "post-process:\n");
if (opt.level >= 2 && mindepth > ctx->mindepth) { if (mindepth > INT_MAX) { mindepth = INT_MAX; } opt_enter(&opt, "${blu}-mindepth${rs} ${bld}%d${rs}\n", ctx->mindepth); ctx->mindepth = mindepth; opt_leave(&opt, "${blu}-mindepth${rs} ${bld}%d${rs}\n", ctx->mindepth); }
if (opt.level >= 4 && maxdepth < ctx->maxdepth) { if (maxdepth < INT_MIN) { maxdepth = INT_MIN; } opt_enter(&opt, "${blu}-maxdepth${rs} ${bld}%d${rs}\n", ctx->maxdepth); ctx->maxdepth = maxdepth; opt_leave(&opt, "${blu}-maxdepth${rs} ${bld}%d${rs}\n", ctx->maxdepth); }
if (opt.level >= 3) { // bfs_eval() can do lazy stat() calls, but only on one thread. float lazy_cost = estimate_stat_odds(ctx); // bftw() can do eager stat() calls in parallel float eager_cost = 1.0 / ctx->threads;
if (eager_cost <= lazy_cost) { opt_enter(&opt, "lazy stat cost: ${ylw}%g${rs}\n", lazy_cost); ctx->flags |= BFTW_STAT; opt_leave(&opt, "eager stat cost: ${ylw}%g${rs}\n", eager_cost); }
#ifndef POSIX_SPAWN_SETRLIMIT // If bfs_spawn_setrlimit() would force us to use fork() over // posix_spawn(), the extra cost may outweigh the benefit of a // higher RLIMIT_NOFILE float single_exec_odds = estimate_odds(ctx->expr, single_exec); if (single_exec_odds >= 0.5) { opt_enter(&opt, "single ${blu}-exec${rs} odds: ${ylw}%g${rs}\n", single_exec_odds); ctx->raise_nofile = false; opt_leave(&opt, "not raising RLIMIT_NOFILE\n"); }#endif }
opt_leave(&opt, NULL);
return 0;}