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
Line 
1/*
2 *  Copyright (c) 2018 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6#include <set>
7#include "grep_engine.h"
8#include <llvm/IR/Module.h>
9#include <boost/filesystem.hpp>
10#include <UCD/resolve_properties.h>
11#include <kernels/callback.h>
12#include <kernels/charclasses.h>
13#include <cc/cc_kernel.h>
14#include <grep/grep_kernel.h>
15#include <kernels/UCD_property_kernel.h>
16#include <kernels/grapheme_kernel.h>
17#include <kernels/linebreak_kernel.h>
18#include <kernels/streams_merge.h>
19#include <kernels/source_kernel.h>
20#include <kernels/s2p_kernel.h>
21#include <kernels/scanmatchgen.h>
22#include <kernels/streamset.h>
23#include <kernels/until_n.h>
24#include <kernels/kernel_builder.h>
25#include <pablo/pablo_kernel.h>
26#include <cc/alphabet.h>
27#include <re/re_cc.h>
28#include <re/re_diff.h>
29#include <re/re_seq.h>
30#include <re/re_rep.h>
31#include <re/re_alt.h>
32#include <re/re_end.h>
33#include <re/re_name.h>
34#include <re/re_assertion.h>
35#include <re/casing.h>
36#include <re/exclude_CC.h>
37#include <re/to_utf8.h>
38#include <re/re_toolchain.h>
39#include <toolchain/toolchain.h>
40#include <re/re_analysis.h>
41#include <re/re_name_resolve.h>
42#include <re/re_name_gather.h>
43#include <re/collect_ccs.h>
44#include <re/replaceCC.h>
45#include <re/re_multiplex.h>
46#include <re/grapheme_clusters.h>
47#include <re/re_utility.h>
48#include <re/printer_re.h>
49#include <toolchain/toolchain.h>
50#include <toolchain/cpudriver.h>
51#include <iostream>
52#include <cc/multiplex_CCs.h>
53#include <llvm/Support/raw_ostream.h>
54#include <util/file_select.h>
55#include <sys/stat.h>
56#include <fcntl.h>
57#include <errno.h>
58#include <llvm/ADT/STLExtras.h> // for make_unique
59#include <llvm/Support/CommandLine.h>
60#include <llvm/Support/Debug.h>
61#include <llvm/Support/Casting.h>
62#include <kernels/pipeline_builder.h>
63#include <sched.h>
64#include <atomic>
65
66using namespace llvm;
67using namespace cc;
68using namespace kernel;
69
70static cl::opt<int> Threads("t", cl::desc("Total number of threads."), cl::init(2));
71static cl::opt<bool> PabloTransposition("enable-pablo-s2p", cl::desc("Enable experimental pablo transposition."));
72static cl::opt<bool> CC_Multiplexing("CC-multiplexing", cl::desc("Enable CC multiplexing."), cl::init(false));
73static cl::opt<bool> PropertyKernels("enable-property-kernels", cl::desc("Enable Unicode property kernels."), cl::init(false));
74static cl::opt<bool> MultithreadedSimpleRE("enable-simple-RE-kernels", cl::desc("Enable individual CC kernels for simple REs."), cl::init(false));
75const unsigned DefaultByteCClimit = 6;
76
77static cl::opt<unsigned> ByteCClimit("byte-CC-limit", cl::desc("Max number of CCs for byte CC pipeline."), cl::init(DefaultByteCClimit));
78
79const auto ENCODING_BITS = 8;
80
81namespace grep {
82
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}
90
91extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end) {
92    reinterpret_cast<MatchAccumulator *>(accum_addr)->accumulate_match(lineNum, line_start, line_end);
93}
94
95extern "C" void finalize_match_wrapper(intptr_t accum_addr, char * buffer_end) {
96    reinterpret_cast<MatchAccumulator *>(accum_addr)->finalize_match(buffer_end);
97}
98
99inline static size_t ceil_log2(const size_t v) {
100    assert ("log2(0) is undefined!" && v != 0);
101    assert ("sizeof(size_t) == sizeof(long)" && sizeof(size_t) == sizeof(long));
102    return (sizeof(size_t) * CHAR_BIT) - __builtin_clzl(v - 1UL);
103}
104
105// Grep Engine construction and initialization.
106
107GrepEngine::GrepEngine(BaseDriver &driver) :
108    mSuppressFileMessages(false),
109    mBinaryFilesMode(argv::Text),
110    mPreferMMap(true),
111    mShowFileNames(false),
112    mStdinLabel("(stdin)"),
113    mShowLineNumbers(false),
114    mInitialTab(false),
115    mCaseInsensitive(false),
116    mInvertMatches(false),
117    mMaxCount(0),
118    mGrepStdIn(false),
119    mGrepDriver(driver),
120    mMainMethod(nullptr),
121    mNextFileToGrep(0),
122    mNextFileToPrint(0),
123    grepMatchFound(false),
124    mGrepRecordBreak(GrepRecordBreakKind::LF),
125    mRequiredComponents(static_cast<Component>(0)),
126    mMoveMatchesToEOL(true),
127    mEngineThread(pthread_self()) {}
128
129QuietModeEngine::QuietModeEngine(BaseDriver &driver) : GrepEngine(driver) {
130    mEngineKind = EngineKind::QuietMode;
131    mMaxCount = 1;
132}
133
134MatchOnlyEngine::MatchOnlyEngine(BaseDriver & driver, bool showFilesWithMatch, bool useNullSeparators) :
135    GrepEngine(driver), mRequiredCount(showFilesWithMatch) {
136    mEngineKind = EngineKind::MatchOnly;
137    mFileSuffix = useNullSeparators ? std::string("\0", 1) : "\n";
138    mMaxCount = 1;
139    mShowFileNames = true;
140}
141
142CountOnlyEngine::CountOnlyEngine(BaseDriver &driver) : GrepEngine(driver) {
143    mEngineKind = EngineKind::CountOnly;
144    mFileSuffix = ":";
145}
146
147EmitMatchesEngine::EmitMatchesEngine(BaseDriver &driver)
148: GrepEngine(driver) {
149    mEngineKind = EngineKind::EmitMatches;
150    mFileSuffix = mInitialTab ? "\t:" : ":";
151}
152
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
161void GrepEngine::setRecordBreak(GrepRecordBreakKind b) {
162    mGrepRecordBreak = b;
163}
164
165void GrepEngine::initFileResult(const std::vector<boost::filesystem::path> & paths) {
166    const unsigned n = paths.size();
167    mResultStrs.resize(n);
168    mFileStatus.resize(n, FileStatus::Pending);
169    inputPaths = paths;
170}
171
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);
183        anchorName->setDefinition(re::makeUnicodeBreak());
184        anchorRE = anchorName;
185    }
186
187    mREs = REs;
188    bool allAnchored = true;
189    for(unsigned i = 0; i < mREs.size(); ++i) {
190        if (!hasEndAnchor(mREs[i])) allAnchored = false;
191        mREs[i] = resolveModesAndExternalSymbols(mREs[i], mCaseInsensitive);
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    }
197    if ((mEngineKind == EngineKind::EmitMatches) || (mEngineKind == EngineKind::CountOnly)) {
198        if (!allAnchored || (mGrepRecordBreak == GrepRecordBreakKind::Unicode)) {
199            setComponent(mRequiredComponents, Component::MoveMatchesToEOL);
200        }
201    }
202}
203
204// Code Generation
205//
206// All engines share a common pipeline to compute a stream of Matches from a given input Bytestream.
207
208std::pair<StreamSet *, StreamSet *> GrepEngine::grepPipeline(const std::unique_ptr<ProgramBuilder> & P, StreamSet * InputStream) {
209
210    Scalar * const callbackObject = P->getInputScalar("callbackObject");
211
212    //  Regular Expression Processing and Analysis Phase
213
214    StreamSet * ByteStream = nullptr;
215    if (mBinaryFilesMode == argv::Text) {
216        ByteStream = InputStream;
217    } else if (mBinaryFilesMode == argv::WithoutMatch) {
218        ByteStream = P->CreateStreamSet(1, 8);
219        Kernel * binaryCheckK = P->CreateKernelCall<AbortOnNull>(InputStream, ByteStream, callbackObject);
220        mGrepDriver.LinkFunction(binaryCheckK, "signal_dispatcher", kernel::signal_dispatcher);
221    } else {
222        llvm::report_fatal_error("Binary mode not supported.");
223    }
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    }
233    if (anyGCB) {
234        setComponent(mRequiredComponents, Component::GraphemeClusterBoundary);
235    }
236
237    StreamSet * LineBreakStream = P->CreateStreamSet();
238    std::vector<StreamSet *> MatchResultsBufs(numOfREs);
239
240    re::RE * prefixRE;
241    re::RE * suffixRE;
242
243    // For simple regular expressions with a small number of characters, we
244    // can bypass transposition and use the Direct CC compiler.
245    const auto isSimple = (numOfREs == 1) && (mGrepRecordBreak != GrepRecordBreakKind::Unicode) && (!anyGCB);
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   
250    Component internalComponents = Component::NoComponents;
251    if (internalS2P && hasComponent(mRequiredComponents, Component::MoveMatchesToEOL)) {
252        setComponent(internalComponents, Component::MoveMatchesToEOL);
253    }
254
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);
263        if (PabloTransposition) {
264            P->CreateKernelCall<S2P_PabloKernel>(SourceStream, BasisBits);
265        } else {
266            //P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
267            Kernel * s2pK = P->CreateKernelCall<S2PKernel>(SourceStream, BasisBits, cc::BitNumbering::LittleEndian, callbackObject);
268            mGrepDriver.LinkFunction(s2pK, "signal_dispatcher", kernel::signal_dispatcher);
269        }
270        SourceStream = BasisBits;
271    }
272
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    }
288
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);
295        }
296    }
297
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)});
316            }
317        }
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 {
339            options->addExternal("UTF8_nonfinal", RequiredStreams);
340            if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
341                options->addExternal("UTF8_LB", LineBreakStream);
342            }
343            std::set<re::Name *> UnicodeProperties;
344            if (PropertyKernels) {
345                re::gatherUnicodeProperties(mREs[i], UnicodeProperties);
346                for (const auto & p : UnicodeProperties) {
347                    auto name = p->getFullName();
348                    const auto f = propertyStream.find(name);
349                    if (LLVM_UNLIKELY(f == propertyStream.end())) {
350                        report_fatal_error(name + " not found");
351                    }
352                    options->addExternal(name, f->second);
353                }
354            }
355            if (hasGCB[i]) { assert (GCB_stream);
356                options->addExternal("\\b{g}", GCB_stream);
357            }
358            if (CC_Multiplexing) {
359                const auto UnicodeSets = re::collectCCs(mREs[i], cc::Unicode, std::set<re::Name *>{re::makeZeroWidth("\\b{g}")});
360                if (UnicodeSets.size() <= 1) {
361                    options->setRE(mREs[i]);
362                } else {
363                    auto mpx = std::make_shared<MultiplexedAlphabet>("mpx", UnicodeSets);
364                    mREs[i] = transformCCs(mpx, mREs[i]);
365                    options->setRE(mREs[i]);
366                    auto mpx_basis = mpx->getMultiplexedCCs();
367                    StreamSet * const CharClasses = P->CreateStreamSet(mpx_basis.size());
368                    P->CreateKernelCall<CharClassesKernel>(std::move(mpx_basis), SourceStream, CharClasses);
369                    options->addAlphabet(mpx, CharClasses);
370                }
371            }
372        }
373        P->CreateKernelCall<ICGrepKernel>(std::move(options));
374    }
375
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;
381    }
382    if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL) && !hasComponent(internalComponents, Component::MoveMatchesToEOL)) {
383        StreamSet * const MovedMatches = P->CreateStreamSet();
384        P->CreateKernelCall<MatchedLinesKernel>(Matches, LineBreakStream, MovedMatches);
385        Matches = MovedMatches;
386    }
387    if (mInvertMatches) {
388        StreamSet * const InvertedMatches = P->CreateStreamSet();
389        P->CreateKernelCall<InvertMatchesKernel>(Matches, LineBreakStream, InvertedMatches);
390        Matches = InvertedMatches;
391    }
392    if (mMaxCount > 0) {
393        StreamSet * const TruncatedMatches = P->CreateStreamSet();
394        Scalar * const maxCount = P->getInputScalar("maxCount");
395        P->CreateKernelCall<UntilNkernel>(maxCount, Matches, TruncatedMatches);
396        Matches = TruncatedMatches;
397    }
398    return std::pair<StreamSet *, StreamSet *>(LineBreakStream, Matches);
399}
400
401
402
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).
405//
406
407void GrepEngine::grepCodeGen() {
408    auto & idb = mGrepDriver.getBuilder();
409
410    auto P = mGrepDriver.makePipeline(
411                // inputs
412                {Binding{idb->getSizeTy(), "useMMap"},
413                Binding{idb->getInt32Ty(), "fileDescriptor"},
414                Binding{idb->getIntAddrTy(), "callbackObject"},
415                Binding{idb->getSizeTy(), "maxCount"}}
416                ,// output
417                {Binding{idb->getInt64Ty(), "countResult"}});
418
419    Scalar * const useMMap = P->getInputScalar("useMMap");
420    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
421
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"));
426
427    mMainMethod = P->compile();
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.
433//
434void EmitMatch::accumulate_match (const size_t lineNum, char * line_start, char * line_end) {
435    mResultStr << mLinePrefix;
436    if (mShowLineNumbers) {
437        // Internally line numbers are counted from 0.  For display, adjust
438        // the line number so that lines are numbered from 1.
439        if (mInitialTab) {
440            mResultStr << lineNum+1 << "\t:";
441        }
442        else {
443            mResultStr << lineNum+1 << ":";
444        }
445    }
446
447    const auto bytes = line_end - line_start + 1;
448    mResultStr.write(line_start, bytes);
449    mLineCount++;
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);
455        }
456        else {
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));
461        }
462    }
463}
464
465void EmitMatch::finalize_match(char * buffer_end) {
466    if (!mTerminated) mResultStr << "\n";
467}
468
469void EmitMatchesEngine::grepCodeGen() {
470    auto & idb = mGrepDriver.getBuilder();
471
472    auto E = mGrepDriver.makePipeline(
473                // inputs
474                {Binding{idb->getSizeTy(), "useMMap"},
475                Binding{idb->getInt32Ty(), "fileDescriptor"},
476                Binding{idb->getIntAddrTy(), "callbackObject"},
477                Binding{idb->getSizeTy(), "maxCount"}}
478                ,// output
479                {Binding{idb->getInt64Ty(), "countResult"}});
480
481    Scalar * const useMMap = E->getInputScalar("useMMap");
482    Scalar * const fileDescriptor = E->getInputScalar("fileDescriptor");
483
484    StreamSet * const ByteStream = E->CreateStreamSet(1, ENCODING_BITS);
485    E->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
486
487    StreamSet * LineBreakStream;
488    StreamSet * Matches;
489    std::tie(LineBreakStream, Matches) = grepPipeline(E, ByteStream);
490
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);
495
496    E->setOutputScalar("countResult", E->CreateConstant(idb->getInt64(0)));
497
498    mMainMethod = E->compile();
499}
500
501
502//
503//  The doGrep methods apply a GrepEngine to a single file, processing the results
504//  differently based on the engine type.
505
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
516uint64_t GrepEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
517    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, GrepCallBackObject *, size_t maxCount);
518    bool useMMap = mPreferMMap && canMMap(fileName);
519    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
520
521    int32_t fileDescriptor = openFile(fileName, strm);
522    if (fileDescriptor == -1) return 0;
523    GrepCallBackObject handler;
524    uint64_t grepResult = f(useMMap, fileDescriptor, &handler, mMaxCount);
525
526    close(fileDescriptor);
527    if (handler.binaryFileSignalled()) {
528        llvm::errs() << "Binary file " << fileName << "\n";
529        return 0;
530    }
531    else {
532        showResult(grepResult, fileName, strm);
533        return grepResult;
534    }
535}
536
537std::string GrepEngine::linePrefix(std::string fileName) {
538    if (!mShowFileNames) return "";
539    if (fileName == "-") {
540        return mStdinLabel + mFileSuffix;
541    }
542    else {
543        return fileName + mFileSuffix;
544    }
545}
546
547// Default: do not show anything
548void GrepEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
549}
550
551void CountOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
552    if (mShowFileNames) strm << linePrefix(fileName);
553    strm << grepResult << "\n";
554}
555
556void MatchOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
557    if (grepResult == mRequiredCount) {
558       strm << linePrefix(fileName);
559    }
560}
561
562uint64_t EmitMatchesEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
563    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, EmitMatch *, size_t maxCount);
564    bool useMMap = mPreferMMap && canMMap(fileName);
565    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
566    int32_t fileDescriptor = openFile(fileName, strm);
567    if (fileDescriptor == -1) return 0;
568    EmitMatch accum(linePrefix(fileName), mShowLineNumbers, mInitialTab, strm);
569    f(useMMap, fileDescriptor, &accum, mMaxCount);
570    close(fileDescriptor);
571    if (accum.binaryFileSignalled()) {
572        accum.mResultStr.clear();
573        if (!mSuppressFileMessages) {
574            accum.mResultStr << "Binary file " << fileName << " skipped.\n";
575        }
576    }
577    if (accum.mLineCount > 0) grepMatchFound = true;
578    return accum.mLineCount;
579}
580
581// Open a file and return its file desciptor.
582int32_t GrepEngine::openFile(const std::string & fileName, std::ostringstream & msgstrm) {
583    if (fileName == "-") {
584        return STDIN_FILENO;
585    }
586    else {
587        struct stat sb;
588        int32_t fileDescriptor = open(fileName.c_str(), O_RDONLY);
589        if (LLVM_UNLIKELY(fileDescriptor == -1)) {
590            if (!mSuppressFileMessages) {
591                if (errno == EACCES) {
592                    msgstrm << "icgrep: " << fileName << ": Permission denied.\n";
593                }
594                else if (errno == ENOENT) {
595                    msgstrm << "icgrep: " << fileName << ": No such file.\n";
596                }
597                else {
598                    msgstrm << "icgrep: " << fileName << ": Failed.\n";
599                }
600            }
601            return fileDescriptor;
602        }
603        if (stat(fileName.c_str(), &sb) == 0 && S_ISDIR(sb.st_mode)) {
604            if (!mSuppressFileMessages) {
605                msgstrm << "icgrep: " << fileName << ": Is a directory.\n";
606            }
607            close(fileDescriptor);
608            return -1;
609        }
610        return fileDescriptor;
611    }
612}
613
614// The process of searching a group of files may use a sequential or a task
615// parallel approach.
616
617void * DoGrepThreadFunction(void *args) {
618    assert (args);
619    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
620}
621
622bool GrepEngine::searchAllFiles() {
623    const unsigned numOfThreads = std::min(static_cast<unsigned>(Threads), static_cast<unsigned>(inputPaths.size()));
624    std::vector<pthread_t> threads(numOfThreads);
625
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));
630        }
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));
639        }
640    }
641    return grepMatchFound;
642}
643
644
645// DoGrep thread function.
646void * GrepEngine::DoGrepThreadMethod() {
647
648    unsigned fileIdx = mNextFileToGrep++;
649    while (fileIdx < inputPaths.size()) {
650        if (codegen::DebugOptionIsSet(codegen::TraceCounts)) {
651            errs() << "Tracing " << inputPaths[fileIdx].string() << "\n";
652        }
653        const auto grepResult = doGrep(inputPaths[fileIdx].string(), mResultStrs[fileIdx]);
654        mFileStatus[fileIdx] = FileStatus::GrepComplete;
655        if (grepResult > 0) {
656            grepMatchFound = true;
657        }
658        if ((mEngineKind == EngineKind::QuietMode) && grepMatchFound) {
659            if (pthread_self() != mEngineThread) {
660                pthread_exit(nullptr);
661            }
662            return nullptr;
663        }
664        fileIdx = mNextFileToGrep++;
665    }
666
667    unsigned printIdx = mNextFileToPrint++;
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;
678                printIdx++;
679            } else {
680                sched_yield();
681            }
682        }
683
684        if (mGrepStdIn) {
685            std::ostringstream s;
686            const auto grepResult = doGrep("-", s);
687            llvm::outs() << s.str();
688            if (grepResult) grepMatchFound = true;
689        }
690    }
691    if (pthread_self() != mEngineThread) {
692        pthread_exit(nullptr);
693    }
694    return nullptr;
695}
696
697InternalSearchEngine::InternalSearchEngine(BaseDriver &driver) :
698    mGrepRecordBreak(GrepRecordBreakKind::LF),
699    mCaseInsensitive(false),
700    mGrepDriver(driver),
701    mMainMethod(nullptr) {}
702
703void InternalSearchEngine::grepCodeGen(re::RE * matchingRE, re::RE * excludedRE) {
704    auto & idb = mGrepDriver.getBuilder();
705    mSaveSegmentPipelineParallel = codegen::SegmentPipelineParallel;
706    codegen::SegmentPipelineParallel = false;
707
708    re::CC * breakCC = nullptr;
709    if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
710        breakCC = re::makeByte(0x0);
711    } else {// if (mGrepRecordBreak == GrepRecordBreakKind::LF)
712        breakCC = re::makeByte(0x0A);
713    }
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) {
717        matchingRE = resolveCaseInsensitiveMode(matchingRE, mCaseInsensitive);
718        matchingRE = regular_expression_passes(matchingRE);
719        matchingRE = re::exclude_CC(matchingRE, breakCC);
720        matchingRE = resolveAnchors(matchingRE, breakCC);
721        matchingRE = toUTF8(matchingRE);
722    }
723    if (!excludeNothing) {
724        excludedRE = resolveCaseInsensitiveMode(excludedRE, mCaseInsensitive);
725        excludedRE = regular_expression_passes(excludedRE);
726        excludedRE = re::exclude_CC(excludedRE, breakCC);
727        excludedRE = resolveAnchors(excludedRE, breakCC);
728        excludedRE = toUTF8(excludedRE);
729    }
730
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;
745
746    if (matchAllLines && excludeNothing) {
747        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, ByteStream, RecordBreakStream);
748    } else {
749        BasisBits = E->CreateStreamSet(8);
750        E->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
751        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, BasisBits, RecordBreakStream);
752    }
753
754    StreamSet * MatchingRecords = nullptr;
755    if (matchAllLines) {
756        MatchingRecords = RecordBreakStream;
757    } else {
758        StreamSet * MatchResults = E->CreateStreamSet();
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));
764        MatchingRecords = E->CreateStreamSet();
765        E->CreateKernelCall<MatchedLinesKernel>(MatchResults, RecordBreakStream, MatchingRecords);
766    }
767    if (!excludeNothing) {
768        StreamSet * ExcludedResults = E->CreateStreamSet();
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));
774        StreamSet * ExcludedRecords = E->CreateStreamSet();
775        E->CreateKernelCall<MatchedLinesKernel>(ExcludedResults, RecordBreakStream, ExcludedRecords);
776
777        if (!matchAllLines) {
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);
786        }
787    }
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();
794}
795
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);
800    codegen::SegmentPipelineParallel = mSaveSegmentPipelineParallel;
801}
802
803GrepEngine::~GrepEngine() { }
804
805InternalSearchEngine::InternalSearchEngine(const std::unique_ptr<grep::GrepEngine> & engine)
806: InternalSearchEngine(engine->mGrepDriver) {
807
808}
809
810InternalSearchEngine::~InternalSearchEngine() { }
811
812}
Note: See TracBrowser for help on using the repository browser.