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

Last change on this file since 6294 was 6294, checked in by cameron, 3 months ago

Move grep kernel files into grep subdirectory.

File size: 33.1 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 *SourceStream) {
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 = SourceStream;
217    } else if (mBinaryFilesMode == argv::WithoutMatch) {
218        ByteStream = P->CreateStreamSet(1, 8);
219        Kernel * binaryCheckK = P->CreateKernelCall<AbortOnNull>(SourceStream, 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
238    StreamSet * LineBreakStream = P->CreateStreamSet();
239    std::vector<StreamSet *> MatchResultsBufs(numOfREs);
240
241    re::RE * prefixRE;
242    re::RE * suffixRE;
243
244    // For simple regular expressions with a small number of characters, we
245    // can bypass transposition and use the Direct CC compiler.
246    const auto isSimple = (numOfREs == 1) && (mGrepRecordBreak != GrepRecordBreakKind::Unicode) && (!anyGCB);
247    if (isSimple) {
248        mREs[0] = toUTF8(mREs[0]);
249    }
250
251    bool requiresComplexTest = true;
252    Component internalComponents = Component::NoComponents;
253
254
255
256    if (isSimple) {
257        if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL)) {
258            re::RE * notBreak = re::makeDiff(re::makeByte(0x00, 0xFF), mBreakCC);
259            mREs[0] = re::makeSeq({mREs[0], re::makeRep(notBreak, 0, re::Rep::UNBOUNDED_REP), makeNegativeLookAheadAssertion(notBreak)});
260            setComponent(internalComponents, Component::MoveMatchesToEOL);
261        }
262        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
263        const auto isWithinByteTestLimit = byteTestsWithinLimit(mREs[0], ByteCClimit);
264        const auto hasTriCC = hasTriCCwithinLimit(mREs[0], ByteCClimit, prefixRE, suffixRE);
265        if (isWithinByteTestLimit || hasTriCC) {
266            if (MultithreadedSimpleRE && hasTriCC) {
267                auto CCs = re::collectCCs(prefixRE, cc::Byte);
268                for (auto cc : CCs) {
269                    auto ccName = makeName(cc);
270                    mREs[0] = re::replaceCC(mREs[0], cc, ccName);
271                    auto ccNameStr = ccName->getFullName();
272                    StreamSet * const ccStream = P->CreateStreamSet(1, 1);
273                    P->CreateKernelCall<CharacterClassKernelBuilder>(ccNameStr, std::vector<re::CC *>{cc}, ByteStream, ccStream);
274                    options->addExternal(ccNameStr, ccStream);
275                }
276            }
277            StreamSet * const MatchResults = P->CreateStreamSet(1, 1);
278            MatchResultsBufs[0] = MatchResults;
279            if (isWithinByteTestLimit) {
280                options->setRE(mREs[0]);
281                options->setSource(ByteStream);
282                options->setResults(MatchResults);
283                P->CreateKernelCall<ICGrepKernel>(std::move(options));
284            } else {
285                //P->CreateKernelCall<ByteBitGrepKernel>(prefixRE, suffixRE, ByteStream, MatchResults, externals);
286                options->setPrefixRE(prefixRE);
287                options->setRE(suffixRE);
288                options->setSource(ByteStream);
289                options->setResults(MatchResults);
290                P->CreateKernelCall<ICGrepKernel>(std::move(options));
291            }
292            Kernel * LB_nullK = P->CreateKernelCall<CharacterClassKernelBuilder>( "breakCC", std::vector<re::CC *>{mBreakCC}, ByteStream, LineBreakStream, callbackObject);
293            mGrepDriver.LinkFunction(LB_nullK, "signal_dispatcher", kernel::signal_dispatcher);
294            requiresComplexTest = false;
295        }
296    }
297
298    if (requiresComplexTest) {
299
300        StreamSet * const BasisBits = P->CreateStreamSet(ENCODING_BITS, 1);
301        if (PabloTransposition) {
302            P->CreateKernelCall<S2P_PabloKernel>(ByteStream, BasisBits);
303        } else {
304            //P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
305            Kernel * s2pK = P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits, cc::BitNumbering::LittleEndian, callbackObject);
306            mGrepDriver.LinkFunction(s2pK, "signal_dispatcher", kernel::signal_dispatcher);
307        }
308
309        StreamSet * const RequiredStreams = P->CreateStreamSet();
310        StreamSet * UnicodeLB = nullptr;
311
312        if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
313            UnicodeLB = P->CreateStreamSet();
314            StreamSet * const LineFeedStream = P->CreateStreamSet();
315            P->CreateKernelCall<LineFeedKernelBuilder>(BasisBits, LineFeedStream);
316            P->CreateKernelCall<RequiredStreams_UTF8>(BasisBits, LineFeedStream, RequiredStreams, UnicodeLB);
317            LineBreakStream = UnicodeLB;
318        } else {
319            P->CreateKernelCall<UTF8_nonFinal>(BasisBits, RequiredStreams);
320            if (mGrepRecordBreak == GrepRecordBreakKind::LF) {
321                P->CreateKernelCall<LineFeedKernelBuilder>(BasisBits, LineBreakStream);
322            } else { // if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
323                P->CreateKernelCall<CharacterClassKernelBuilder>( "Null", std::vector<re::CC *>{mBreakCC}, BasisBits, LineBreakStream);
324            }
325        }
326
327        std::map<std::string, StreamSet *> propertyStream;
328        if (PropertyKernels) {
329            for (auto p : mUnicodeProperties) {
330                auto name = p->getFullName();
331                StreamSet * property = P->CreateStreamSet(1, 1);
332                propertyStream.emplace(name, property);
333                P->CreateKernelCall<UnicodePropertyKernelBuilder>(p, BasisBits, property);
334            }
335        }
336
337        StreamSet * GCB_stream = nullptr;
338        if (hasComponent(mRequiredComponents, Component::GraphemeClusterBoundary)) {
339            GCB_stream = P->CreateStreamSet();
340            P->CreateKernelCall<GraphemeClusterBreakKernel>(BasisBits, RequiredStreams, GCB_stream);
341        }
342
343        for(unsigned i = 0; i < numOfREs; ++i) {
344            std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
345            options->addExternal("UTF8_nonfinal", RequiredStreams);
346            if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
347                options->addExternal("UTF8_LB", LineBreakStream);
348            }
349            std::set<re::Name *> UnicodeProperties;
350            if (PropertyKernels) {
351                re::gatherUnicodeProperties(mREs[i], UnicodeProperties);
352                for (const auto & p : UnicodeProperties) {
353                    auto name = p->getFullName();
354                    const auto f = propertyStream.find(name);
355                    if (LLVM_UNLIKELY(f == propertyStream.end())) {
356                        report_fatal_error(name + " not found");
357                    }
358                    options->addExternal(name, f->second);
359                }
360            }
361            if (hasGCB[i]) { assert (GCB_stream);
362                options->addExternal("\\b{g}", GCB_stream);
363            }
364
365            StreamSet * const MatchResults = P->CreateStreamSet(1, 1);
366            MatchResultsBufs[i] = MatchResults;
367
368            if (CC_Multiplexing) {
369                const auto UnicodeSets = re::collectCCs(mREs[i], cc::Unicode, std::set<re::Name *>{re::makeZeroWidth("\\b{g}")});
370                if (UnicodeSets.size() <= 1) {
371                    options->setRE(mREs[i]);
372                    options->setSource(BasisBits);
373                    options->setResults(MatchResults);
374                } else {
375                    auto mpx = std::make_shared<MultiplexedAlphabet>("mpx", UnicodeSets);
376                    mREs[i] = transformCCs(mpx, mREs[i]);
377                    auto mpx_basis = mpx->getMultiplexedCCs();
378                    StreamSet * const CharClasses = P->CreateStreamSet(mpx_basis.size());
379                    P->CreateKernelCall<CharClassesKernel>(std::move(mpx_basis), BasisBits, CharClasses);
380
381                    #warning TODO: multiplexed CCs ought to generate unique names. Make the name also dependent on alphabet.
382                    // Multiplexing Grep Kernel is not Cachable, since for now it use string representation of RE AST as cache key,
383                    // whileit is possible that two multiplexed REs with the same name "mpx_1" have different alphabets
384                    options->setRE(mREs[i]);
385                    options->setSource(BasisBits);
386                    options->setResults(MatchResults);
387                    options->addAlphabet(mpx, CharClasses);
388                    P->CreateKernelCall<ICGrepKernel>(std::move(options));
389                }
390            } else {
391                options->setRE(mREs[i]);
392                options->setSource(BasisBits);
393                options->setResults(MatchResults);
394                P->CreateKernelCall<ICGrepKernel>(std::move(options));
395            }
396        }
397
398    } // end of requiresComplexTest
399
400    StreamSet * Matches = MatchResultsBufs[0];
401    if (MatchResultsBufs.size() > 1) {
402        StreamSet * const MergedMatches = P->CreateStreamSet();
403        P->CreateKernelCall<StreamsMerge>(MatchResultsBufs, MergedMatches);
404        Matches = MergedMatches;
405    }
406    if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL) && !hasComponent(internalComponents, Component::MoveMatchesToEOL)) {
407        StreamSet * const MovedMatches = P->CreateStreamSet();
408        P->CreateKernelCall<MatchedLinesKernel>(Matches, LineBreakStream, MovedMatches);
409        Matches = MovedMatches;
410    }
411    if (mInvertMatches) {
412        StreamSet * const InvertedMatches = P->CreateStreamSet();
413        P->CreateKernelCall<InvertMatchesKernel>(Matches, LineBreakStream, InvertedMatches);
414        Matches = InvertedMatches;
415    }
416    if (mMaxCount > 0) {
417        StreamSet * const TruncatedMatches = P->CreateStreamSet();
418        Scalar * const maxCount = P->getInputScalar("maxCount");
419        P->CreateKernelCall<UntilNkernel>(maxCount, Matches, TruncatedMatches);
420        Matches = TruncatedMatches;
421    }
422    return std::pair<StreamSet *, StreamSet *>(LineBreakStream, Matches);
423}
424
425
426
427// The QuietMode, MatchOnly and CountOnly engines share a common code generation main function,
428// which returns a count of the matches found (possibly subject to a MaxCount).
429//
430
431void GrepEngine::grepCodeGen() {
432    auto & idb = mGrepDriver.getBuilder();
433
434    auto P = mGrepDriver.makePipeline(
435                // inputs
436                {Binding{idb->getSizeTy(), "useMMap"},
437                Binding{idb->getInt32Ty(), "fileDescriptor"},
438                Binding{idb->getIntAddrTy(), "callbackObject"},
439                Binding{idb->getSizeTy(), "maxCount"}}
440                ,// output
441                {Binding{idb->getInt64Ty(), "countResult"}});
442
443    Scalar * const useMMap = P->getInputScalar("useMMap");
444    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
445
446    StreamSet * const ByteStream = P->CreateStreamSet(1, ENCODING_BITS);
447    P->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
448    StreamSet * const Matches = grepPipeline(P, ByteStream).second;
449    P->CreateKernelCall<PopcountKernel>(Matches, P->getOutputScalar("countResult"));
450
451    mMainMethod = P->compile();
452}
453
454//
455//  Default Report Match:  lines are emitted with whatever line terminators are found in the
456//  input.  However, if the final line is not terminated, a new line is appended.
457//
458void EmitMatch::accumulate_match (const size_t lineNum, char * line_start, char * line_end) {
459    mResultStr << mLinePrefix;
460    if (mShowLineNumbers) {
461        // Internally line numbers are counted from 0.  For display, adjust
462        // the line number so that lines are numbered from 1.
463        if (mInitialTab) {
464            mResultStr << lineNum+1 << "\t:";
465        }
466        else {
467            mResultStr << lineNum+1 << ":";
468        }
469    }
470
471    const auto bytes = line_end - line_start + 1;
472    mResultStr.write(line_start, bytes);
473    mLineCount++;
474    unsigned last_byte = *line_end;
475    mTerminated = (last_byte >= 0x0A) && (last_byte <= 0x0D);
476    if (LLVM_UNLIKELY(!mTerminated)) {
477        if (last_byte == 0x85) {  //  Possible NEL terminator.
478            mTerminated = (bytes >= 2) && (static_cast<unsigned>(line_end[-1]) == 0xC2);
479        }
480        else {
481            // Possible LS or PS terminators.
482            mTerminated = (bytes >= 3) && (static_cast<unsigned>(line_end[-2]) == 0xE2)
483                                       && (static_cast<unsigned>(line_end[-1]) == 0x80)
484                                       && ((last_byte == 0xA8) || (last_byte == 0xA9));
485        }
486    }
487}
488
489void EmitMatch::finalize_match(char * buffer_end) {
490    if (!mTerminated) mResultStr << "\n";
491}
492
493void EmitMatchesEngine::grepCodeGen() {
494    auto & idb = mGrepDriver.getBuilder();
495
496    auto E = mGrepDriver.makePipeline(
497                // inputs
498                {Binding{idb->getSizeTy(), "useMMap"},
499                Binding{idb->getInt32Ty(), "fileDescriptor"},
500                Binding{idb->getIntAddrTy(), "callbackObject"},
501                Binding{idb->getSizeTy(), "maxCount"}}
502                ,// output
503                {Binding{idb->getInt64Ty(), "countResult"}});
504
505    Scalar * const useMMap = E->getInputScalar("useMMap");
506    Scalar * const fileDescriptor = E->getInputScalar("fileDescriptor");
507
508    StreamSet * const ByteStream = E->CreateStreamSet(1, ENCODING_BITS);
509    E->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
510
511    StreamSet * LineBreakStream;
512    StreamSet * Matches;
513    std::tie(LineBreakStream, Matches) = grepPipeline(E, ByteStream);
514
515    Scalar * const callbackObject = E->getInputScalar("callbackObject");
516    Kernel * const scanMatchK = E->CreateKernelCall<ScanMatchKernel>(Matches, LineBreakStream, ByteStream, callbackObject);
517    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
518    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
519
520    E->setOutputScalar("countResult", E->CreateConstant(idb->getInt64(0)));
521
522    mMainMethod = E->compile();
523}
524
525
526//
527//  The doGrep methods apply a GrepEngine to a single file, processing the results
528//  differently based on the engine type.
529
530bool canMMap(const std::string & fileName) {
531    if (fileName == "-") return false;
532    namespace fs = boost::filesystem;
533    fs::path p(fileName);
534    boost::system::error_code errc;
535    fs::file_status s = fs::status(p, errc);
536    return !errc && is_regular_file(s);
537}
538
539
540uint64_t GrepEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
541    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, GrepCallBackObject *, size_t maxCount);
542    bool useMMap = mPreferMMap && canMMap(fileName);
543    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
544
545    int32_t fileDescriptor = openFile(fileName, strm);
546    if (fileDescriptor == -1) return 0;
547    GrepCallBackObject handler;
548    uint64_t grepResult = f(useMMap, fileDescriptor, &handler, mMaxCount);
549
550    close(fileDescriptor);
551    if (handler.binaryFileSignalled()) {
552        llvm::errs() << "Binary file " << fileName << "\n";
553        return 0;
554    }
555    else {
556        showResult(grepResult, fileName, strm);
557        return grepResult;
558    }
559}
560
561std::string GrepEngine::linePrefix(std::string fileName) {
562    if (!mShowFileNames) return "";
563    if (fileName == "-") {
564        return mStdinLabel + mFileSuffix;
565    }
566    else {
567        return fileName + mFileSuffix;
568    }
569}
570
571// Default: do not show anything
572void GrepEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
573}
574
575void CountOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
576    if (mShowFileNames) strm << linePrefix(fileName);
577    strm << grepResult << "\n";
578}
579
580void MatchOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
581    if (grepResult == mRequiredCount) {
582       strm << linePrefix(fileName);
583    }
584}
585
586uint64_t EmitMatchesEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
587    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, EmitMatch *, size_t maxCount);
588    bool useMMap = mPreferMMap && canMMap(fileName);
589    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
590    int32_t fileDescriptor = openFile(fileName, strm);
591    if (fileDescriptor == -1) return 0;
592    EmitMatch accum(linePrefix(fileName), mShowLineNumbers, mInitialTab, strm);
593    f(useMMap, fileDescriptor, &accum, mMaxCount);
594    close(fileDescriptor);
595    if (accum.binaryFileSignalled()) {
596        accum.mResultStr.clear();
597        if (!mSuppressFileMessages) {
598            accum.mResultStr << "Binary file " << fileName << " skipped.\n";
599        }
600    }
601    if (accum.mLineCount > 0) grepMatchFound = true;
602    return accum.mLineCount;
603}
604
605// Open a file and return its file desciptor.
606int32_t GrepEngine::openFile(const std::string & fileName, std::ostringstream & msgstrm) {
607    if (fileName == "-") {
608        return STDIN_FILENO;
609    }
610    else {
611        struct stat sb;
612        int32_t fileDescriptor = open(fileName.c_str(), O_RDONLY);
613        if (LLVM_UNLIKELY(fileDescriptor == -1)) {
614            if (!mSuppressFileMessages) {
615                if (errno == EACCES) {
616                    msgstrm << "icgrep: " << fileName << ": Permission denied.\n";
617                }
618                else if (errno == ENOENT) {
619                    msgstrm << "icgrep: " << fileName << ": No such file.\n";
620                }
621                else {
622                    msgstrm << "icgrep: " << fileName << ": Failed.\n";
623                }
624            }
625            return fileDescriptor;
626        }
627        if (stat(fileName.c_str(), &sb) == 0 && S_ISDIR(sb.st_mode)) {
628            if (!mSuppressFileMessages) {
629                msgstrm << "icgrep: " << fileName << ": Is a directory.\n";
630            }
631            close(fileDescriptor);
632            return -1;
633        }
634        return fileDescriptor;
635    }
636}
637
638// The process of searching a group of files may use a sequential or a task
639// parallel approach.
640
641void * DoGrepThreadFunction(void *args) {
642    assert (args);
643    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
644}
645
646bool GrepEngine::searchAllFiles() {
647    const unsigned numOfThreads = std::min(static_cast<unsigned>(Threads), static_cast<unsigned>(inputPaths.size()));
648    std::vector<pthread_t> threads(numOfThreads);
649
650    for(unsigned long i = 1; i < numOfThreads; ++i) {
651        const int rc = pthread_create(&threads[i], nullptr, DoGrepThreadFunction, (void *)this);
652        if (rc) {
653            llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
654        }
655    }
656    // Main thread also does the work;
657    DoGrepThreadMethod();
658    for(unsigned i = 1; i < numOfThreads; ++i) {
659        void * status = nullptr;
660        const int rc = pthread_join(threads[i], &status);
661        if (rc) {
662            llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
663        }
664    }
665    return grepMatchFound;
666}
667
668
669// DoGrep thread function.
670void * GrepEngine::DoGrepThreadMethod() {
671
672    unsigned fileIdx = mNextFileToGrep++;
673    while (fileIdx < inputPaths.size()) {
674        if (codegen::DebugOptionIsSet(codegen::TraceCounts)) {
675            errs() << "Tracing " << inputPaths[fileIdx].string() << "\n";
676        }
677        const auto grepResult = doGrep(inputPaths[fileIdx].string(), mResultStrs[fileIdx]);
678        mFileStatus[fileIdx] = FileStatus::GrepComplete;
679        if (grepResult > 0) {
680            grepMatchFound = true;
681        }
682        if ((mEngineKind == EngineKind::QuietMode) && grepMatchFound) {
683            if (pthread_self() != mEngineThread) {
684                pthread_exit(nullptr);
685            }
686            return nullptr;
687        }
688        fileIdx = mNextFileToGrep++;
689    }
690
691    unsigned printIdx = mNextFileToPrint++;
692    if (printIdx == 0) {
693
694        while (printIdx < inputPaths.size()) {
695            const bool readyToPrint = (mFileStatus[printIdx] == FileStatus::GrepComplete);
696            if (readyToPrint) {
697                const auto output = mResultStrs[printIdx].str();
698                if (!output.empty()) {
699                    llvm::outs() << output;
700                }
701                mFileStatus[printIdx] = FileStatus::PrintComplete;
702                printIdx++;
703            } else {
704                sched_yield();
705            }
706        }
707
708        if (mGrepStdIn) {
709            std::ostringstream s;
710            const auto grepResult = doGrep("-", s);
711            llvm::outs() << s.str();
712            if (grepResult) grepMatchFound = true;
713        }
714    }
715    if (pthread_self() != mEngineThread) {
716        pthread_exit(nullptr);
717    }
718    return nullptr;
719}
720
721InternalSearchEngine::InternalSearchEngine(BaseDriver &driver) :
722    mGrepRecordBreak(GrepRecordBreakKind::LF),
723    mCaseInsensitive(false),
724    mGrepDriver(driver),
725    mMainMethod(nullptr) {}
726
727void InternalSearchEngine::grepCodeGen(re::RE * matchingRE, re::RE * excludedRE) {
728    auto & idb = mGrepDriver.getBuilder();
729    mSaveSegmentPipelineParallel = codegen::SegmentPipelineParallel;
730    codegen::SegmentPipelineParallel = false;
731
732    re::CC * breakCC = nullptr;
733    if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
734        breakCC = re::makeByte(0x0);
735    } else {// if (mGrepRecordBreak == GrepRecordBreakKind::LF)
736        breakCC = re::makeByte(0x0A);
737    }
738    bool excludeNothing = (excludedRE == nullptr) || (isa<re::Alt>(excludedRE) && cast<re::Alt>(excludedRE)->empty());
739    bool matchAllLines = (matchingRE == nullptr) || isa<re::End>(matchingRE);
740    if (!matchAllLines) {
741        matchingRE = resolveCaseInsensitiveMode(matchingRE, mCaseInsensitive);
742        matchingRE = regular_expression_passes(matchingRE);
743        matchingRE = re::exclude_CC(matchingRE, breakCC);
744        matchingRE = resolveAnchors(matchingRE, breakCC);
745        matchingRE = toUTF8(matchingRE);
746    }
747    if (!excludeNothing) {
748        excludedRE = resolveCaseInsensitiveMode(excludedRE, mCaseInsensitive);
749        excludedRE = regular_expression_passes(excludedRE);
750        excludedRE = re::exclude_CC(excludedRE, breakCC);
751        excludedRE = resolveAnchors(excludedRE, breakCC);
752        excludedRE = toUTF8(excludedRE);
753    }
754
755    auto E = mGrepDriver.makePipeline({Binding{idb->getInt8PtrTy(), "buffer"},
756                                       Binding{idb->getSizeTy(), "length"},
757                                       Binding{idb->getIntAddrTy(), "accumulator"}});
758
759    Scalar * const buffer = E->getInputScalar(0);
760    Scalar * const length = E->getInputScalar(1);
761    StreamSet * ByteStream = E->CreateStreamSet(1, 8);
762    E->CreateKernelCall<MemorySourceKernel>(buffer, length, ByteStream);
763
764
765    StreamSet * RecordBreakStream = E->CreateStreamSet();
766    const auto RBname = (mGrepRecordBreak == GrepRecordBreakKind::Null) ? "Null" : "LF";
767
768    StreamSet * BasisBits = nullptr;
769
770    if (matchAllLines && excludeNothing) {
771        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, ByteStream, RecordBreakStream);
772    } else {
773        BasisBits = E->CreateStreamSet(8);
774        E->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
775        E->CreateKernelCall<CharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, BasisBits, RecordBreakStream);
776    }
777
778    StreamSet * MatchingRecords = nullptr;
779    if (matchAllLines) {
780        MatchingRecords = RecordBreakStream;
781    } else {
782        StreamSet * MatchResults = E->CreateStreamSet();
783        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
784        options->setRE(matchingRE);
785        options->setSource(BasisBits);
786        options->setResults(MatchResults);
787        E->CreateKernelCall<ICGrepKernel>(std::move(options));
788        MatchingRecords = E->CreateStreamSet();
789        E->CreateKernelCall<MatchedLinesKernel>(MatchResults, RecordBreakStream, MatchingRecords);
790    }
791    if (!excludeNothing) {
792        StreamSet * ExcludedResults = E->CreateStreamSet();
793        std::unique_ptr<GrepKernelOptions> options = make_unique<GrepKernelOptions>();
794        options->setRE(excludedRE);
795        options->setSource(BasisBits);
796        options->setResults(ExcludedResults);
797        E->CreateKernelCall<ICGrepKernel>(std::move(options));
798        StreamSet * ExcludedRecords = E->CreateStreamSet();
799        E->CreateKernelCall<MatchedLinesKernel>(ExcludedResults, RecordBreakStream, ExcludedRecords);
800
801        if (!matchAllLines) {
802            StreamSet * nonExcluded = E->CreateStreamSet();
803            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, nonExcluded);
804            StreamSet * const included = MatchingRecords;
805            MatchingRecords = E->CreateStreamSet();
806            E->CreateKernelCall<StreamsIntersect>(std::vector<StreamSet *>{included, nonExcluded}, MatchingRecords);
807        } else {
808            MatchingRecords = E->CreateStreamSet();
809            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, MatchingRecords);
810        }
811    }
812
813    Kernel * scanMatchK = E->CreateKernelCall<ScanMatchKernel>(MatchingRecords, RecordBreakStream, ByteStream, E->getInputScalar(2));
814    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
815    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
816
817    mMainMethod = E->compile();
818}
819
820void InternalSearchEngine::doGrep(const char * search_buffer, size_t bufferLength, MatchAccumulator & accum) {
821    typedef void (*GrepFunctionType)(const char * buffer, const size_t length, MatchAccumulator *);
822    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
823    f(search_buffer, bufferLength, &accum);
824    codegen::SegmentPipelineParallel = mSaveSegmentPipelineParallel;
825}
826
827GrepEngine::~GrepEngine() { }
828
829InternalSearchEngine::InternalSearchEngine(const std::unique_ptr<grep::GrepEngine> & engine)
830: InternalSearchEngine(engine->mGrepDriver) {
831
832}
833
834InternalSearchEngine::~InternalSearchEngine() { }
835
836}
Note: See TracBrowser for help on using the repository browser.