source: icGREP/icgrep-devel/icgrep/grep/grep_engine.cpp

Last change on this file was 6297, checked in by cameron, 4 months ago

Merge branch 'master' of https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel

File size: 32.0 KB
RevLine 
[4324]1/*
[5892]2 *  Copyright (c) 2018 International Characters.
[4324]3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
[5881]6#include <set>
[5234]7#include "grep_engine.h"
[5267]8#include <llvm/IR/Module.h>
[5234]9#include <boost/filesystem.hpp>
[5206]10#include <UCD/resolve_properties.h>
[6207]11#include <kernels/callback.h>
[5585]12#include <kernels/charclasses.h>
[6221]13#include <cc/cc_kernel.h>
[6294]14#include <grep/grep_kernel.h>
[5887]15#include <kernels/UCD_property_kernel.h>
[5881]16#include <kernels/grapheme_kernel.h>
[5357]17#include <kernels/linebreak_kernel.h>
[5338]18#include <kernels/streams_merge.h>
[5429]19#include <kernels/source_kernel.h>
[5234]20#include <kernels/s2p_kernel.h>
21#include <kernels/scanmatchgen.h>
22#include <kernels/streamset.h>
[5450]23#include <kernels/until_n.h>
[5436]24#include <kernels/kernel_builder.h>
[5087]25#include <pablo/pablo_kernel.h>
[5934]26#include <cc/alphabet.h>
[5234]27#include <re/re_cc.h>
[6213]28#include <re/re_diff.h>
29#include <re/re_seq.h>
30#include <re/re_rep.h>
[5970]31#include <re/re_alt.h>
32#include <re/re_end.h>
[5881]33#include <re/re_name.h>
[6213]34#include <re/re_assertion.h>
[5769]35#include <re/casing.h>
[5779]36#include <re/exclude_CC.h>
[5902]37#include <re/to_utf8.h>
[5234]38#include <re/re_toolchain.h>
[5425]39#include <toolchain/toolchain.h>
[5902]40#include <re/re_analysis.h>
[5770]41#include <re/re_name_resolve.h>
[5887]42#include <re/re_name_gather.h>
[5934]43#include <re/collect_ccs.h>
44#include <re/replaceCC.h>
[5585]45#include <re/re_multiplex.h>
[5772]46#include <re/grapheme_clusters.h>
[5998]47#include <re/re_utility.h>
[5801]48#include <re/printer_re.h>
[5700]49#include <toolchain/toolchain.h>
[5464]50#include <toolchain/cpudriver.h>
[5234]51#include <iostream>
[5369]52#include <cc/multiplex_CCs.h>
[5377]53#include <llvm/Support/raw_ostream.h>
[5945]54#include <util/file_select.h>
[5386]55#include <sys/stat.h>
[5418]56#include <fcntl.h>
[5484]57#include <errno.h>
[5696]58#include <llvm/ADT/STLExtras.h> // for make_unique
[5700]59#include <llvm/Support/CommandLine.h>
[5735]60#include <llvm/Support/Debug.h>
[5945]61#include <llvm/Support/Casting.h>
[6184]62#include <kernels/pipeline_builder.h>
[5762]63#include <sched.h>
[6229]64#include <atomic>
[5377]65
[5267]66using namespace llvm;
[5795]67using namespace cc;
[5861]68using namespace kernel;
[5795]69
[5703]70static cl::opt<int> Threads("t", cl::desc("Total number of threads."), cl::init(2));
[5837]71static cl::opt<bool> PabloTransposition("enable-pablo-s2p", cl::desc("Enable experimental pablo transposition."));
[5881]72static cl::opt<bool> CC_Multiplexing("CC-multiplexing", cl::desc("Enable CC multiplexing."), cl::init(false));
[5887]73static cl::opt<bool> PropertyKernels("enable-property-kernels", cl::desc("Enable Unicode property kernels."), cl::init(false));
[5934]74static cl::opt<bool> MultithreadedSimpleRE("enable-simple-RE-kernels", cl::desc("Enable individual CC kernels for simple REs."), cl::init(false));
[5908]75const unsigned DefaultByteCClimit = 6;
[5892]76
[5908]77static cl::opt<unsigned> ByteCClimit("byte-CC-limit", cl::desc("Max number of CCs for byte CC pipeline."), cl::init(DefaultByteCClimit));
78
[6184]79const auto ENCODING_BITS = 8;
[5908]80
[5473]81namespace grep {
[6184]82
[5989]83void GrepCallBackObject::handle_signal(unsigned s) {
84    if (static_cast<GrepSignal>(s) == GrepSignal::BinaryFile) {
85        mBinaryFile = true;
86    } else {
87        llvm::report_fatal_error("Unknown GrepSignal");
88    }
89}
[5473]90
[5913]91extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end) {
[5892]92    reinterpret_cast<MatchAccumulator *>(accum_addr)->accumulate_match(lineNum, line_start, line_end);
93}
94
[5913]95extern "C" void finalize_match_wrapper(intptr_t accum_addr, char * buffer_end) {
[5892]96    reinterpret_cast<MatchAccumulator *>(accum_addr)->finalize_match(buffer_end);
97}
[5952]98
[5945]99inline static size_t ceil_log2(const size_t v) {
100    assert ("log2(0) is undefined!" && v != 0);
[5963]101    assert ("sizeof(size_t) == sizeof(long)" && sizeof(size_t) == sizeof(long));
[5952]102    return (sizeof(size_t) * CHAR_BIT) - __builtin_clzl(v - 1UL);
[5945]103}
[5892]104
[5704]105// Grep Engine construction and initialization.
[5770]106
[6184]107GrepEngine::GrepEngine(BaseDriver &driver) :
[5945]108    mSuppressFileMessages(false),
[5992]109    mBinaryFilesMode(argv::Text),
[5945]110    mPreferMMap(true),
111    mShowFileNames(false),
112    mStdinLabel("(stdin)"),
113    mShowLineNumbers(false),
114    mInitialTab(false),
115    mCaseInsensitive(false),
116    mInvertMatches(false),
117    mMaxCount(0),
[5964]118    mGrepStdIn(false),
[6184]119    mGrepDriver(driver),
120    mMainMethod(nullptr),
[5735]121    mNextFileToGrep(0),
122    mNextFileToPrint(0),
[5704]123    grepMatchFound(false),
[5900]124    mGrepRecordBreak(GrepRecordBreakKind::LF),
[6203]125    mRequiredComponents(static_cast<Component>(0)),
[5735]126    mMoveMatchesToEOL(true),
127    mEngineThread(pthread_self()) {}
[5770]128
[6184]129QuietModeEngine::QuietModeEngine(BaseDriver &driver) : GrepEngine(driver) {
[5945]130    mEngineKind = EngineKind::QuietMode;
131    mMaxCount = 1;
[5704]132}
[5473]133
[6184]134MatchOnlyEngine::MatchOnlyEngine(BaseDriver & driver, bool showFilesWithMatch, bool useNullSeparators) :
135    GrepEngine(driver), mRequiredCount(showFilesWithMatch) {
[5945]136    mEngineKind = EngineKind::MatchOnly;
137    mFileSuffix = useNullSeparators ? std::string("\0", 1) : "\n";
138    mMaxCount = 1;
[5971]139    mShowFileNames = true;
[5704]140}
[5484]141
[6184]142CountOnlyEngine::CountOnlyEngine(BaseDriver &driver) : GrepEngine(driver) {
[5945]143    mEngineKind = EngineKind::CountOnly;
[5704]144    mFileSuffix = ":";
145}
[5484]146
[6184]147EmitMatchesEngine::EmitMatchesEngine(BaseDriver &driver)
148: GrepEngine(driver) {
[5945]149    mEngineKind = EngineKind::EmitMatches;
150    mFileSuffix = mInitialTab ? "\t:" : ":";
[5484]151}
[5704]152
[6203]153bool GrepEngine::hasComponent(Component compon_set, Component c) {
154    return (static_cast<component_t>(compon_set) & static_cast<component_t>(c)) != 0;
155}
156
157void GrepEngine::GrepEngine::setComponent(Component & compon_set, Component c) {
158    compon_set = static_cast<Component>(static_cast<component_t>(compon_set) | static_cast<component_t>(c));
159}
160
[5894]161void GrepEngine::setRecordBreak(GrepRecordBreakKind b) {
162    mGrepRecordBreak = b;
163}
[6209]164
[6229]165void GrepEngine::initFileResult(const std::vector<boost::filesystem::path> & paths) {
[5964]166    const unsigned n = paths.size();
[5704]167    mResultStrs.resize(n);
[5771]168    mFileStatus.resize(n, FileStatus::Pending);
[5964]169    inputPaths = paths;
[5704]170}
171
[5913]172void GrepEngine::initREs(std::vector<re::RE *> & REs) {
173    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
174        mBreakCC = re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029)));
175    } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
176        mBreakCC = re::makeByte(0);  // Null
177    } else {
178        mBreakCC = re::makeByte(0x0A); // LF
179    }
180    re::RE * anchorRE = mBreakCC;
181    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
182        re::Name * anchorName = re::makeName("UTF8_LB", re::Name::Type::Unicode);
[5998]183        anchorName->setDefinition(re::makeUnicodeBreak());
[5913]184        anchorRE = anchorName;
185    }
[6209]186
[5913]187    mREs = REs;
[5914]188    bool allAnchored = true;
[5913]189    for(unsigned i = 0; i < mREs.size(); ++i) {
[5914]190        if (!hasEndAnchor(mREs[i])) allAnchored = false;
[5945]191        mREs[i] = resolveModesAndExternalSymbols(mREs[i], mCaseInsensitive);
[5913]192        mREs[i] = re::exclude_CC(mREs[i], mBreakCC);
193        mREs[i] = resolveAnchors(mREs[i], anchorRE);
194        re::gatherUnicodeProperties(mREs[i], mUnicodeProperties);
195        mREs[i] = regular_expression_passes(mREs[i]);
196    }
[6203]197    if ((mEngineKind == EngineKind::EmitMatches) || (mEngineKind == EngineKind::CountOnly)) {
198        if (!allAnchored || (mGrepRecordBreak == GrepRecordBreakKind::Unicode)) {
199            setComponent(mRequiredComponents, Component::MoveMatchesToEOL);
200        }
201    }
[5913]202}
203
[5704]204// Code Generation
205//
206// All engines share a common pipeline to compute a stream of Matches from a given input Bytestream.
207
[6297]208std::pair<StreamSet *, StreamSet *> GrepEngine::grepPipeline(const std::unique_ptr<ProgramBuilder> & P, StreamSet * InputStream) {
[6184]209
210    Scalar * const callbackObject = P->getInputScalar("callbackObject");
211
[5887]212    //  Regular Expression Processing and Analysis Phase
[5894]213
[6184]214    StreamSet * ByteStream = nullptr;
[5992]215    if (mBinaryFilesMode == argv::Text) {
[6297]216        ByteStream = InputStream;
[5992]217    } else if (mBinaryFilesMode == argv::WithoutMatch) {
[6184]218        ByteStream = P->CreateStreamSet(1, 8);
[6297]219        Kernel * binaryCheckK = P->CreateKernelCall<AbortOnNull>(InputStream, ByteStream, callbackObject);
[6207]220        mGrepDriver.LinkFunction(binaryCheckK, "signal_dispatcher", kernel::signal_dispatcher);
[5992]221    } else {
222        llvm::report_fatal_error("Binary mode not supported.");
223    }
[6184]224
225    const auto numOfREs = mREs.size();
226    bool hasGCB[numOfREs];
227    bool anyGCB = false;
228
229    for(unsigned i = 0; i < numOfREs; ++i) {
230        hasGCB[i] = hasGraphemeClusterBoundary(mREs[i]);
231        anyGCB |= hasGCB[i];
232    }
[6203]233    if (anyGCB) {
234        setComponent(mRequiredComponents, Component::GraphemeClusterBoundary);
235    }
[6184]236
237    StreamSet * LineBreakStream = P->CreateStreamSet();
238    std::vector<StreamSet *> MatchResultsBufs(numOfREs);
239
[5908]240    re::RE * prefixRE;
241    re::RE * suffixRE;
[6213]242
[5902]243    // For simple regular expressions with a small number of characters, we
244    // can bypass transposition and use the Direct CC compiler.
[6184]245    const auto isSimple = (numOfREs == 1) && (mGrepRecordBreak != GrepRecordBreakKind::Unicode) && (!anyGCB);
[6297]246    const auto isWithinByteTestLimit = byteTestsWithinLimit(mREs[0], ByteCClimit);
247    const auto hasTriCC = hasTriCCwithinLimit(mREs[0], ByteCClimit, prefixRE, suffixRE);
248    const auto internalS2P = isSimple && (isWithinByteTestLimit || hasTriCC);
249   
[6213]250    Component internalComponents = Component::NoComponents;
[6297]251    if (internalS2P && hasComponent(mRequiredComponents, Component::MoveMatchesToEOL)) {
252        setComponent(internalComponents, Component::MoveMatchesToEOL);
[6184]253    }
254
[6297]255    StreamSet * SourceStream = ByteStream;
256    StreamSet * const RequiredStreams = P->CreateStreamSet();
257    StreamSet * UnicodeLB = nullptr;
258    std::map<std::string, StreamSet *> propertyStream;
259    StreamSet * GCB_stream = nullptr;
260   
261    if (!internalS2P) {
262        StreamSet * BasisBits = P->CreateStreamSet(ENCODING_BITS, 1);
[5902]263        if (PabloTransposition) {
[6297]264            P->CreateKernelCall<S2P_PabloKernel>(SourceStream, BasisBits);
[6184]265        } else {
[6218]266            //P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
[6297]267            Kernel * s2pK = P->CreateKernelCall<S2PKernel>(SourceStream, BasisBits, cc::BitNumbering::LittleEndian, callbackObject);
[6216]268            mGrepDriver.LinkFunction(s2pK, "signal_dispatcher", kernel::signal_dispatcher);
[5887]269        }
[6297]270        SourceStream = BasisBits;
271    }
[5887]272
[6297]273    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
274        UnicodeLB = P->CreateStreamSet();
275        StreamSet * const LineFeedStream = P->CreateStreamSet();
276        P->CreateKernelCall<LineFeedKernelBuilder>(SourceStream, LineFeedStream);
277        P->CreateKernelCall<RequiredStreams_UTF8>(SourceStream, LineFeedStream, RequiredStreams, UnicodeLB);
278        LineBreakStream = UnicodeLB;
279    }
280    else if (!internalS2P) {
281        P->CreateKernelCall<UTF8_nonFinal>(SourceStream, RequiredStreams);
282        if (mGrepRecordBreak == GrepRecordBreakKind::LF) {
283            P->CreateKernelCall<LineFeedKernelBuilder>(SourceStream, LineBreakStream);
284        } else { // if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
285            P->CreateKernelCall<CharacterClassKernelBuilder>( "Null", std::vector<re::CC *>{mBreakCC}, SourceStream, LineBreakStream);
286        }
287    }
[6253]288
[6297]289    if (PropertyKernels) {
290        for (auto p : mUnicodeProperties) {
291            auto name = p->getFullName();
292            StreamSet * property = P->CreateStreamSet(1, 1);
293            propertyStream.emplace(name, property);
294            P->CreateKernelCall<UnicodePropertyKernelBuilder>(p, SourceStream, property);
[5902]295        }
[6297]296    }
[6184]297
[6297]298    if (hasComponent(mRequiredComponents, Component::GraphemeClusterBoundary)) {
299        GCB_stream = P->CreateStreamSet();
300        P->CreateKernelCall<GraphemeClusterBreakKernel>(SourceStream, RequiredStreams, GCB_stream);
301    }
302
303    for(unsigned i = 0; i < numOfREs; ++i) {
304        StreamSet * const MatchResults = P->CreateStreamSet(1, 1);
305        MatchResultsBufs[0] = MatchResults;
306        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
307        options->setIndexingAlphabet(&cc::UTF8);
308        options->setSource(SourceStream);
309        options->setResults(MatchResults);
310        if (hasComponent(internalComponents, Component::MoveMatchesToEOL)) {
311            re::RE * notBreak = re::makeDiff(re::makeByte(0x00, 0xFF), mBreakCC);
312            if (isWithinByteTestLimit) {
313                mREs[i] = re::makeSeq({mREs[i], re::makeRep(notBreak, 0, re::Rep::UNBOUNDED_REP), makeNegativeLookAheadAssertion(notBreak)});
314            } else {
315                suffixRE = re::makeSeq({suffixRE, re::makeRep(notBreak, 0, re::Rep::UNBOUNDED_REP), makeNegativeLookAheadAssertion(notBreak)});
[5887]316            }
317        }
[6297]318        options->setRE(mREs[i]);
319        if (internalS2P) {
320            if (!isWithinByteTestLimit) {
321                if (MultithreadedSimpleRE) {
322                    auto CCs = re::collectCCs(prefixRE, cc::Byte);
323                    for (auto cc : CCs) {
324                        auto ccName = makeName(cc);
325                        prefixRE = re::replaceCC(prefixRE, cc, ccName);
326                        suffixRE = re::replaceCC(suffixRE, cc, ccName);
327                        auto ccNameStr = ccName->getFullName();
328                        StreamSet * const ccStream = P->CreateStreamSet(1, 1);
329                        P->CreateKernelCall<CharacterClassKernelBuilder>(ccNameStr, std::vector<re::CC *>{cc}, SourceStream, ccStream);
330                        options->addExternal(ccNameStr, ccStream);
331                    }
332                }
333                options->setPrefixRE(prefixRE);
334                options->setRE(suffixRE);
335            }
336            Kernel * LB_nullK = P->CreateKernelCall<CharacterClassKernelBuilder>( "breakCC", std::vector<re::CC *>{mBreakCC}, SourceStream, LineBreakStream, callbackObject);
337            mGrepDriver.LinkFunction(LB_nullK, "signal_dispatcher", kernel::signal_dispatcher);
338        } else {
[6250]339            options->addExternal("UTF8_nonfinal", RequiredStreams);
[5902]340            if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
[6218]341                options->addExternal("UTF8_LB", LineBreakStream);
[5902]342            }
343            std::set<re::Name *> UnicodeProperties;
344            if (PropertyKernels) {
[5913]345                re::gatherUnicodeProperties(mREs[i], UnicodeProperties);
[6184]346                for (const auto & p : UnicodeProperties) {
[5902]347                    auto name = p->getFullName();
[6184]348                    const auto f = propertyStream.find(name);
349                    if (LLVM_UNLIKELY(f == propertyStream.end())) {
350                        report_fatal_error(name + " not found");
351                    }
[6218]352                    options->addExternal(name, f->second);
[5902]353                }
354            }
[6184]355            if (hasGCB[i]) { assert (GCB_stream);
[6218]356                options->addExternal("\\b{g}", GCB_stream);
[5902]357            }
358            if (CC_Multiplexing) {
[6184]359                const auto UnicodeSets = re::collectCCs(mREs[i], cc::Unicode, std::set<re::Name *>{re::makeZeroWidth("\\b{g}")});
[5902]360                if (UnicodeSets.size() <= 1) {
[6218]361                    options->setRE(mREs[i]);
[5902]362                } else {
[6184]363                    auto mpx = std::make_shared<MultiplexedAlphabet>("mpx", UnicodeSets);
364                    mREs[i] = transformCCs(mpx, mREs[i]);
[6297]365                    options->setRE(mREs[i]);
[6184]366                    auto mpx_basis = mpx->getMultiplexedCCs();
367                    StreamSet * const CharClasses = P->CreateStreamSet(mpx_basis.size());
[6297]368                    P->CreateKernelCall<CharClassesKernel>(std::move(mpx_basis), SourceStream, CharClasses);
[6218]369                    options->addAlphabet(mpx, CharClasses);
[5902]370                }
[5841]371            }
[5816]372        }
[6297]373        P->CreateKernelCall<ICGrepKernel>(std::move(options));
374    }
[5913]375
[6184]376    StreamSet * Matches = MatchResultsBufs[0];
377    if (MatchResultsBufs.size() > 1) {
378        StreamSet * const MergedMatches = P->CreateStreamSet();
379        P->CreateKernelCall<StreamsMerge>(MatchResultsBufs, MergedMatches);
380        Matches = MergedMatches;
[5704]381    }
[6213]382    if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL) && !hasComponent(internalComponents, Component::MoveMatchesToEOL)) {
[6184]383        StreamSet * const MovedMatches = P->CreateStreamSet();
384        P->CreateKernelCall<MatchedLinesKernel>(Matches, LineBreakStream, MovedMatches);
385        Matches = MovedMatches;
[5704]386    }
[5945]387    if (mInvertMatches) {
[6184]388        StreamSet * const InvertedMatches = P->CreateStreamSet();
389        P->CreateKernelCall<InvertMatchesKernel>(Matches, LineBreakStream, InvertedMatches);
390        Matches = InvertedMatches;
[5704]391    }
[5945]392    if (mMaxCount > 0) {
[6184]393        StreamSet * const TruncatedMatches = P->CreateStreamSet();
394        Scalar * const maxCount = P->getInputScalar("maxCount");
395        P->CreateKernelCall<UntilNkernel>(maxCount, Matches, TruncatedMatches);
396        Matches = TruncatedMatches;
[5704]397    }
[6184]398    return std::pair<StreamSet *, StreamSet *>(LineBreakStream, Matches);
[5700]399}
[5704]400
[6184]401
402
[5704]403// The QuietMode, MatchOnly and CountOnly engines share a common code generation main function,
404// which returns a count of the matches found (possibly subject to a MaxCount).
[5700]405//
406
[5913]407void GrepEngine::grepCodeGen() {
[6184]408    auto & idb = mGrepDriver.getBuilder();
[5770]409
[6184]410    auto P = mGrepDriver.makePipeline(
411                // inputs
[6249]412                {Binding{idb->getSizeTy(), "useMMap"},
[6184]413                Binding{idb->getInt32Ty(), "fileDescriptor"},
414                Binding{idb->getIntAddrTy(), "callbackObject"},
415                Binding{idb->getSizeTy(), "maxCount"}}
416                ,// output
417                {Binding{idb->getInt64Ty(), "countResult"}});
[5770]418
[6184]419    Scalar * const useMMap = P->getInputScalar("useMMap");
420    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
[5770]421
[6184]422    StreamSet * const ByteStream = P->CreateStreamSet(1, ENCODING_BITS);
423    P->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
424    StreamSet * const Matches = grepPipeline(P, ByteStream).second;
425    P->CreateKernelCall<PopcountKernel>(Matches, P->getOutputScalar("countResult"));
[5770]426
[6184]427    mMainMethod = P->compile();
[5704]428}
429
430//
431//  Default Report Match:  lines are emitted with whatever line terminators are found in the
432//  input.  However, if the final line is not terminated, a new line is appended.
[5726]433//
[5700]434void EmitMatch::accumulate_match (const size_t lineNum, char * line_start, char * line_end) {
[5945]435    mResultStr << mLinePrefix;
436    if (mShowLineNumbers) {
[5758]437        // Internally line numbers are counted from 0.  For display, adjust
438        // the line number so that lines are numbered from 1.
[5945]439        if (mInitialTab) {
[5771]440            mResultStr << lineNum+1 << "\t:";
[5695]441        }
[5758]442        else {
[5771]443            mResultStr << lineNum+1 << ":";
[5700]444        }
[5695]445    }
[6184]446
447    const auto bytes = line_end - line_start + 1;
[5771]448    mResultStr.write(line_start, bytes);
[5700]449    mLineCount++;
[5758]450    unsigned last_byte = *line_end;
451    mTerminated = (last_byte >= 0x0A) && (last_byte <= 0x0D);
452    if (LLVM_UNLIKELY(!mTerminated)) {
453        if (last_byte == 0x85) {  //  Possible NEL terminator.
454            mTerminated = (bytes >= 2) && (static_cast<unsigned>(line_end[-1]) == 0xC2);
[5726]455        }
456        else {
[5758]457            // Possible LS or PS terminators.
458            mTerminated = (bytes >= 3) && (static_cast<unsigned>(line_end[-2]) == 0xE2)
459                                       && (static_cast<unsigned>(line_end[-1]) == 0x80)
460                                       && ((last_byte == 0xA8) || (last_byte == 0xA9));
[5726]461        }
[5700]462    }
463}
464
[5758]465void EmitMatch::finalize_match(char * buffer_end) {
[5771]466    if (!mTerminated) mResultStr << "\n";
[5758]467}
468
[5913]469void EmitMatchesEngine::grepCodeGen() {
[6184]470    auto & idb = mGrepDriver.getBuilder();
[5770]471
[6184]472    auto E = mGrepDriver.makePipeline(
473                // inputs
[6249]474                {Binding{idb->getSizeTy(), "useMMap"},
[6184]475                Binding{idb->getInt32Ty(), "fileDescriptor"},
476                Binding{idb->getIntAddrTy(), "callbackObject"},
477                Binding{idb->getSizeTy(), "maxCount"}}
478                ,// output
479                {Binding{idb->getInt64Ty(), "countResult"}});
[5770]480
[6184]481    Scalar * const useMMap = E->getInputScalar("useMMap");
482    Scalar * const fileDescriptor = E->getInputScalar("fileDescriptor");
[5770]483
[6184]484    StreamSet * const ByteStream = E->CreateStreamSet(1, ENCODING_BITS);
485    E->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
[5770]486
[6184]487    StreamSet * LineBreakStream;
488    StreamSet * Matches;
489    std::tie(LineBreakStream, Matches) = grepPipeline(E, ByteStream);
[5770]490
[6184]491    Scalar * const callbackObject = E->getInputScalar("callbackObject");
492    Kernel * const scanMatchK = E->CreateKernelCall<ScanMatchKernel>(Matches, LineBreakStream, ByteStream, callbackObject);
493    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
494    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
[5770]495
[6184]496    E->setOutputScalar("countResult", E->CreateConstant(idb->getInt64(0)));
[5770]497
[6184]498    mMainMethod = E->compile();
[5704]499}
[5700]500
501
[5704]502//
503//  The doGrep methods apply a GrepEngine to a single file, processing the results
504//  differently based on the engine type.
[5770]505
[5999]506bool canMMap(const std::string & fileName) {
507    if (fileName == "-") return false;
508    namespace fs = boost::filesystem;
509    fs::path p(fileName);
510    boost::system::error_code errc;
511    fs::file_status s = fs::status(p, errc);
512    return !errc && is_regular_file(s);
513}
514
515
[5964]516uint64_t GrepEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
[6184]517    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, GrepCallBackObject *, size_t maxCount);
[5999]518    bool useMMap = mPreferMMap && canMMap(fileName);
[6184]519    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
[5927]520
[5964]521    int32_t fileDescriptor = openFile(fileName, strm);
[5704]522    if (fileDescriptor == -1) return 0;
[5989]523    GrepCallBackObject handler;
[6184]524    uint64_t grepResult = f(useMMap, fileDescriptor, &handler, mMaxCount);
525
[5704]526    close(fileDescriptor);
[5989]527    if (handler.binaryFileSignalled()) {
[6218]528        llvm::errs() << "Binary file " << fileName << "\n";
[5989]529        return 0;
530    }
531    else {
532        showResult(grepResult, fileName, strm);
533        return grepResult;
534    }
[5704]535}
536
537std::string GrepEngine::linePrefix(std::string fileName) {
[5945]538    if (!mShowFileNames) return "";
[5704]539    if (fileName == "-") {
[5945]540        return mStdinLabel + mFileSuffix;
[5548]541    }
[5704]542    else {
543        return fileName + mFileSuffix;
[5548]544    }
545}
[5770]546
[5989]547// Default: do not show anything
548void GrepEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
549}
[6209]550
[5989]551void CountOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
552    if (mShowFileNames) strm << linePrefix(fileName);
553    strm << grepResult << "\n";
554}
[6209]555
[5989]556void MatchOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
[5704]557    if (grepResult == mRequiredCount) {
[5964]558       strm << linePrefix(fileName);
[5704]559    }
560}
[5700]561
[5964]562uint64_t EmitMatchesEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
[6184]563    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, EmitMatch *, size_t maxCount);
[5999]564    bool useMMap = mPreferMMap && canMMap(fileName);
[6184]565    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
[5964]566    int32_t fileDescriptor = openFile(fileName, strm);
[5704]567    if (fileDescriptor == -1) return 0;
[5964]568    EmitMatch accum(linePrefix(fileName), mShowLineNumbers, mInitialTab, strm);
[6184]569    f(useMMap, fileDescriptor, &accum, mMaxCount);
[5704]570    close(fileDescriptor);
[5989]571    if (accum.binaryFileSignalled()) {
572        accum.mResultStr.clear();
[6218]573        if (!mSuppressFileMessages) {
574            accum.mResultStr << "Binary file " << fileName << " skipped.\n";
575        }
[5989]576    }
[5704]577    if (accum.mLineCount > 0) grepMatchFound = true;
578    return accum.mLineCount;
579}
580
[5703]581// Open a file and return its file desciptor.
[5771]582int32_t GrepEngine::openFile(const std::string & fileName, std::ostringstream & msgstrm) {
[5693]583    if (fileName == "-") {
[5700]584        return STDIN_FILENO;
[5693]585    }
[5700]586    else {
587        struct stat sb;
588        int32_t fileDescriptor = open(fileName.c_str(), O_RDONLY);
589        if (LLVM_UNLIKELY(fileDescriptor == -1)) {
[5945]590            if (!mSuppressFileMessages) {
[5700]591                if (errno == EACCES) {
[5771]592                    msgstrm << "icgrep: " << fileName << ": Permission denied.\n";
[5700]593                }
594                else if (errno == ENOENT) {
[5771]595                    msgstrm << "icgrep: " << fileName << ": No such file.\n";
[5700]596                }
597                else {
[5771]598                    msgstrm << "icgrep: " << fileName << ": Failed.\n";
[5700]599                }
[5484]600            }
[5700]601            return fileDescriptor;
602        }
603        if (stat(fileName.c_str(), &sb) == 0 && S_ISDIR(sb.st_mode)) {
[5945]604            if (!mSuppressFileMessages) {
[5771]605                msgstrm << "icgrep: " << fileName << ": Is a directory.\n";
[5484]606            }
[5700]607            close(fileDescriptor);
[5704]608            return -1;
[5484]609        }
[5700]610        return fileDescriptor;
[4788]611    }
[5700]612}
613
[5704]614// The process of searching a group of files may use a sequential or a task
615// parallel approach.
[5770]616
[5735]617void * DoGrepThreadFunction(void *args) {
[6184]618    assert (args);
[5740]619    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
[5735]620}
[4949]621
[5704]622bool GrepEngine::searchAllFiles() {
[5964]623    const unsigned numOfThreads = std::min(static_cast<unsigned>(Threads), static_cast<unsigned>(inputPaths.size()));
[5795]624    std::vector<pthread_t> threads(numOfThreads);
[5770]625
[5735]626    for(unsigned long i = 1; i < numOfThreads; ++i) {
627        const int rc = pthread_create(&threads[i], nullptr, DoGrepThreadFunction, (void *)this);
628        if (rc) {
629            llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
[5484]630        }
[5735]631    }
632    // Main thread also does the work;
633    DoGrepThreadMethod();
634    for(unsigned i = 1; i < numOfThreads; ++i) {
635        void * status = nullptr;
636        const int rc = pthread_join(threads[i], &status);
637        if (rc) {
638            llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
[5704]639        }
[5484]640    }
[5704]641    return grepMatchFound;
[5377]642}
[5314]643
[5338]644
[5704]645// DoGrep thread function.
[5735]646void * GrepEngine::DoGrepThreadMethod() {
[5748]647
[5771]648    unsigned fileIdx = mNextFileToGrep++;
[5964]649    while (fileIdx < inputPaths.size()) {
[5945]650        if (codegen::DebugOptionIsSet(codegen::TraceCounts)) {
[5964]651            errs() << "Tracing " << inputPaths[fileIdx].string() << "\n";
[5945]652        }
[5964]653        const auto grepResult = doGrep(inputPaths[fileIdx].string(), mResultStrs[fileIdx]);
[5735]654        mFileStatus[fileIdx] = FileStatus::GrepComplete;
[5761]655        if (grepResult > 0) {
656            grepMatchFound = true;
[5735]657        }
[5945]658        if ((mEngineKind == EngineKind::QuietMode) && grepMatchFound) {
[5761]659            if (pthread_self() != mEngineThread) {
660                pthread_exit(nullptr);
661            }
[5735]662            return nullptr;
663        }
[5761]664        fileIdx = mNextFileToGrep++;
[5574]665    }
[5740]666
[5771]667    unsigned printIdx = mNextFileToPrint++;
[6229]668    if (printIdx == 0) {
669
670        while (printIdx < inputPaths.size()) {
671            const bool readyToPrint = (mFileStatus[printIdx] == FileStatus::GrepComplete);
672            if (readyToPrint) {
673                const auto output = mResultStrs[printIdx].str();
674                if (!output.empty()) {
675                    llvm::outs() << output;
676                }
677                mFileStatus[printIdx] = FileStatus::PrintComplete;
[6241]678                printIdx++;
[6229]679            } else {
680                sched_yield();
[5761]681            }
[5735]682        }
[5761]683
[5964]684        if (mGrepStdIn) {
685            std::ostringstream s;
686            const auto grepResult = doGrep("-", s);
687            llvm::outs() << s.str();
688            if (grepResult) grepMatchFound = true;
689        }
[5735]690    }
[6229]691    if (pthread_self() != mEngineThread) {
692        pthread_exit(nullptr);
693    }
[5812]694    return nullptr;
[5703]695}
[5740]696
[6184]697InternalSearchEngine::InternalSearchEngine(BaseDriver &driver) :
[5953]698    mGrepRecordBreak(GrepRecordBreakKind::LF),
699    mCaseInsensitive(false),
[6184]700    mGrepDriver(driver),
701    mMainMethod(nullptr) {}
[6209]702
[6184]703void InternalSearchEngine::grepCodeGen(re::RE * matchingRE, re::RE * excludedRE) {
704    auto & idb = mGrepDriver.getBuilder();
[5969]705    mSaveSegmentPipelineParallel = codegen::SegmentPipelineParallel;
706    codegen::SegmentPipelineParallel = false;
[6209]707
[5953]708    re::CC * breakCC = nullptr;
709    if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
[5963]710        breakCC = re::makeByte(0x0);
[5953]711    } else {// if (mGrepRecordBreak == GrepRecordBreakKind::LF)
712        breakCC = re::makeByte(0x0A);
713    }
[5970]714    bool excludeNothing = (excludedRE == nullptr) || (isa<re::Alt>(excludedRE) && cast<re::Alt>(excludedRE)->empty());
715    bool matchAllLines = (matchingRE == nullptr) || isa<re::End>(matchingRE);
716    if (!matchAllLines) {
[5953]717        matchingRE = resolveCaseInsensitiveMode(matchingRE, mCaseInsensitive);
718        matchingRE = regular_expression_passes(matchingRE);
[5954]719        matchingRE = re::exclude_CC(matchingRE, breakCC);
720        matchingRE = resolveAnchors(matchingRE, breakCC);
[5963]721        matchingRE = toUTF8(matchingRE);
[5953]722    }
[5970]723    if (!excludeNothing) {
[5954]724        excludedRE = resolveCaseInsensitiveMode(excludedRE, mCaseInsensitive);
725        excludedRE = regular_expression_passes(excludedRE);
[5953]726        excludedRE = re::exclude_CC(excludedRE, breakCC);
727        excludedRE = resolveAnchors(excludedRE, breakCC);
[5963]728        excludedRE = toUTF8(excludedRE);
[5953]729    }
[5954]730
[6184]731    auto E = mGrepDriver.makePipeline({Binding{idb->getInt8PtrTy(), "buffer"},
732                                       Binding{idb->getSizeTy(), "length"},
733                                       Binding{idb->getIntAddrTy(), "accumulator"}});
734
735    Scalar * const buffer = E->getInputScalar(0);
736    Scalar * const length = E->getInputScalar(1);
737    StreamSet * ByteStream = E->CreateStreamSet(1, 8);
738    E->CreateKernelCall<MemorySourceKernel>(buffer, length, ByteStream);
739
740
741    StreamSet * RecordBreakStream = E->CreateStreamSet();
742    const auto RBname = (mGrepRecordBreak == GrepRecordBreakKind::Null) ? "Null" : "LF";
743
744    StreamSet * BasisBits = nullptr;
[6209]745
[5970]746    if (matchAllLines && excludeNothing) {
[6221]747        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, ByteStream, RecordBreakStream);
[5970]748    } else {
[6184]749        BasisBits = E->CreateStreamSet(8);
750        E->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
[6221]751        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, BasisBits, RecordBreakStream);
[5971]752    }
[6209]753
[6184]754    StreamSet * MatchingRecords = nullptr;
[5971]755    if (matchAllLines) {
756        MatchingRecords = RecordBreakStream;
757    } else {
[6184]758        StreamSet * MatchResults = E->CreateStreamSet();
[6218]759        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
760        options->setRE(matchingRE);
761        options->setSource(BasisBits);
762        options->setResults(MatchResults);
763        E->CreateKernelCall<ICGrepKernel>(std::move(options));
[6184]764        MatchingRecords = E->CreateStreamSet();
765        E->CreateKernelCall<MatchedLinesKernel>(MatchResults, RecordBreakStream, MatchingRecords);
[5971]766    }
767    if (!excludeNothing) {
[6184]768        StreamSet * ExcludedResults = E->CreateStreamSet();
[6218]769        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
770        options->setRE(excludedRE);
771        options->setSource(BasisBits);
772        options->setResults(ExcludedResults);
773        E->CreateKernelCall<ICGrepKernel>(std::move(options));
[6184]774        StreamSet * ExcludedRecords = E->CreateStreamSet();
775        E->CreateKernelCall<MatchedLinesKernel>(ExcludedResults, RecordBreakStream, ExcludedRecords);
[5971]776
777        if (!matchAllLines) {
[6184]778            StreamSet * nonExcluded = E->CreateStreamSet();
779            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, nonExcluded);
780            StreamSet * const included = MatchingRecords;
781            MatchingRecords = E->CreateStreamSet();
782            E->CreateKernelCall<StreamsIntersect>(std::vector<StreamSet *>{included, nonExcluded}, MatchingRecords);
783        } else {
784            MatchingRecords = E->CreateStreamSet();
785            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, MatchingRecords);
[5953]786        }
787    }
[6184]788
789    Kernel * scanMatchK = E->CreateKernelCall<ScanMatchKernel>(MatchingRecords, RecordBreakStream, ByteStream, E->getInputScalar(2));
790    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
791    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
792
793    mMainMethod = E->compile();
[5953]794}
795
[6184]796void InternalSearchEngine::doGrep(const char * search_buffer, size_t bufferLength, MatchAccumulator & accum) {
797    typedef void (*GrepFunctionType)(const char * buffer, const size_t length, MatchAccumulator *);
798    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
799    f(search_buffer, bufferLength, &accum);
[5969]800    codegen::SegmentPipelineParallel = mSaveSegmentPipelineParallel;
[5953]801}
802
[5998]803GrepEngine::~GrepEngine() { }
804
[6184]805InternalSearchEngine::InternalSearchEngine(const std::unique_ptr<grep::GrepEngine> & engine)
806: InternalSearchEngine(engine->mGrepDriver) {
807
808}
809
[5998]810InternalSearchEngine::~InternalSearchEngine() { }
811
[5953]812}
Note: See TracBrowser for help on using the repository browser.