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

Last change on this file since 6213 was 6213, checked in by cameron, 6 months ago

Matches can be moved to EOL by RE modification

File size: 32.7 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 <kernels/cc_kernel.h>
14#include <kernels/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 <util/aligned_allocator.h>
56#include <sys/stat.h>
57#include <fcntl.h>
58#include <errno.h>
59#include <llvm/ADT/STLExtras.h> // for make_unique
60#include <llvm/Support/CommandLine.h>
61#include <llvm/Support/Debug.h>
62#include <llvm/Support/Casting.h>
63#include <kernels/pipeline_builder.h>
64#include <sched.h>
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
83using Alphabets = ICGrepKernel::Alphabets;
84
85void GrepCallBackObject::handle_signal(unsigned s) {
86    if (static_cast<GrepSignal>(s) == GrepSignal::BinaryFile) {
87        mBinaryFile = true;
88    } else {
89        llvm::report_fatal_error("Unknown GrepSignal");
90    }
91}
92
93extern "C" void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, char * line_start, char * line_end) {
94    reinterpret_cast<MatchAccumulator *>(accum_addr)->accumulate_match(lineNum, line_start, line_end);
95}
96
97extern "C" void finalize_match_wrapper(intptr_t accum_addr, char * buffer_end) {
98    reinterpret_cast<MatchAccumulator *>(accum_addr)->finalize_match(buffer_end);
99}
100
101inline static size_t ceil_log2(const size_t v) {
102    assert ("log2(0) is undefined!" && v != 0);
103    assert ("sizeof(size_t) == sizeof(long)" && sizeof(size_t) == sizeof(long));
104    return (sizeof(size_t) * CHAR_BIT) - __builtin_clzl(v - 1UL);
105}
106
107void SearchableBuffer::addSearchCandidate(const char * C_string_ptr) {
108    size_t length = strlen(C_string_ptr)+1;
109    if (mSpace_used + length >= mAllocated_capacity) {
110        size_t new_capacity = size_t{1} << (ceil_log2(mSpace_used + length + 1));
111        AlignedAllocator<char, BUFFER_ALIGNMENT> alloc;
112        char * new_buffer = mAllocator.allocate(new_capacity, 0);
113        memcpy(new_buffer, mBuffer_base, mSpace_used);
114        memset(&new_buffer[mSpace_used], 0, new_capacity-mSpace_used);
115        if (mBuffer_base != mInitial_buffer) {
116            alloc.deallocate(mBuffer_base, 0);
117        }
118        mBuffer_base = new_buffer;
119        mAllocated_capacity = new_capacity;
120    }
121    memcpy((void * ) &mBuffer_base[mSpace_used], C_string_ptr, length);
122    mSpace_used += length;
123    assert("Search candidate not null terminated" && (mBuffer_base[mSpace_used] == '\0'));
124    mEntries++;
125}
126
127SearchableBuffer::SearchableBuffer() :
128    mAllocated_capacity(INITIAL_CAPACITY),
129    mSpace_used(0),
130    mEntries(0),
131    mBuffer_base(mInitial_buffer) {
132    memset(mBuffer_base, 0, INITIAL_CAPACITY);
133}
134
135SearchableBuffer::~SearchableBuffer() {
136    if (mBuffer_base != mInitial_buffer) {
137        mAllocator.deallocate(mBuffer_base, 0);
138    }
139}
140
141// Grep Engine construction and initialization.
142
143GrepEngine::GrepEngine(BaseDriver &driver) :
144    mSuppressFileMessages(false),
145    mBinaryFilesMode(argv::Text),
146    mPreferMMap(true),
147    mShowFileNames(false),
148    mStdinLabel("(stdin)"),
149    mShowLineNumbers(false),
150    mInitialTab(false),
151    mCaseInsensitive(false),
152    mInvertMatches(false),
153    mMaxCount(0),
154    mGrepStdIn(false),
155    mGrepDriver(driver),
156    mMainMethod(nullptr),
157    mNextFileToGrep(0),
158    mNextFileToPrint(0),
159    grepMatchFound(false),
160    mGrepRecordBreak(GrepRecordBreakKind::LF),
161    mRequiredComponents(static_cast<Component>(0)),
162    mMoveMatchesToEOL(true),
163    mEngineThread(pthread_self()) {}
164
165QuietModeEngine::QuietModeEngine(BaseDriver &driver) : GrepEngine(driver) {
166    mEngineKind = EngineKind::QuietMode;
167    mMaxCount = 1;
168}
169
170MatchOnlyEngine::MatchOnlyEngine(BaseDriver & driver, bool showFilesWithMatch, bool useNullSeparators) :
171    GrepEngine(driver), mRequiredCount(showFilesWithMatch) {
172    mEngineKind = EngineKind::MatchOnly;
173    mFileSuffix = useNullSeparators ? std::string("\0", 1) : "\n";
174    mMaxCount = 1;
175    mShowFileNames = true;
176}
177
178CountOnlyEngine::CountOnlyEngine(BaseDriver &driver) : GrepEngine(driver) {
179    mEngineKind = EngineKind::CountOnly;
180    mFileSuffix = ":";
181}
182
183EmitMatchesEngine::EmitMatchesEngine(BaseDriver &driver)
184: GrepEngine(driver) {
185    mEngineKind = EngineKind::EmitMatches;
186    mFileSuffix = mInitialTab ? "\t:" : ":";
187}
188
189bool GrepEngine::hasComponent(Component compon_set, Component c) {
190    return (static_cast<component_t>(compon_set) & static_cast<component_t>(c)) != 0;
191}
192
193void GrepEngine::GrepEngine::setComponent(Component & compon_set, Component c) {
194    compon_set = static_cast<Component>(static_cast<component_t>(compon_set) | static_cast<component_t>(c));
195}
196
197void GrepEngine::setRecordBreak(GrepRecordBreakKind b) {
198    mGrepRecordBreak = b;
199}
200
201void GrepEngine::initFileResult(std::vector<boost::filesystem::path> & paths) {
202    const unsigned n = paths.size();
203    mResultStrs.resize(n);
204    mFileStatus.resize(n, FileStatus::Pending);
205    inputPaths = paths;
206}
207
208void GrepEngine::initREs(std::vector<re::RE *> & REs) {
209    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
210        mBreakCC = re::makeCC(re::makeCC(0x0A, 0x0D), re::makeCC(re::makeCC(0x85), re::makeCC(0x2028, 0x2029)));
211    } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
212        mBreakCC = re::makeByte(0);  // Null
213    } else {
214        mBreakCC = re::makeByte(0x0A); // LF
215    }
216    re::RE * anchorRE = mBreakCC;
217    if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
218        re::Name * anchorName = re::makeName("UTF8_LB", re::Name::Type::Unicode);
219        anchorName->setDefinition(re::makeUnicodeBreak());
220        anchorRE = anchorName;
221    }
222
223    mREs = REs;
224    bool allAnchored = true;
225    for(unsigned i = 0; i < mREs.size(); ++i) {
226        if (!hasEndAnchor(mREs[i])) allAnchored = false;
227        mREs[i] = resolveModesAndExternalSymbols(mREs[i], mCaseInsensitive);
228        mREs[i] = re::exclude_CC(mREs[i], mBreakCC);
229        mREs[i] = resolveAnchors(mREs[i], anchorRE);
230        re::gatherUnicodeProperties(mREs[i], mUnicodeProperties);
231        mREs[i] = regular_expression_passes(mREs[i]);
232    }
233    if ((mEngineKind == EngineKind::EmitMatches) || (mEngineKind == EngineKind::CountOnly)) {
234        if (!allAnchored || (mGrepRecordBreak == GrepRecordBreakKind::Unicode)) {
235            setComponent(mRequiredComponents, Component::MoveMatchesToEOL);
236        }
237    }
238}
239
240// Code Generation
241//
242// All engines share a common pipeline to compute a stream of Matches from a given input Bytestream.
243
244std::pair<StreamSet *, StreamSet *> GrepEngine::grepPipeline(const std::unique_ptr<PipelineBuilder> & P, StreamSet *SourceStream) {
245
246    Scalar * const callbackObject = P->getInputScalar("callbackObject");
247
248    //  Regular Expression Processing and Analysis Phase
249
250    StreamSet * ByteStream = nullptr;
251    if (mBinaryFilesMode == argv::Text) {
252        ByteStream = SourceStream;
253    } else if (mBinaryFilesMode == argv::WithoutMatch) {
254        ByteStream = P->CreateStreamSet(1, 8);
255        Kernel * binaryCheckK = P->CreateKernelCall<AbortOnNull>(SourceStream, ByteStream, callbackObject);
256        mGrepDriver.LinkFunction(binaryCheckK, "signal_dispatcher", kernel::signal_dispatcher);
257    } else {
258        llvm::report_fatal_error("Binary mode not supported.");
259    }
260
261    const auto numOfREs = mREs.size();
262    bool hasGCB[numOfREs];
263    bool anyGCB = false;
264
265    for(unsigned i = 0; i < numOfREs; ++i) {
266        hasGCB[i] = hasGraphemeClusterBoundary(mREs[i]);
267        anyGCB |= hasGCB[i];
268    }
269    if (anyGCB) {
270        setComponent(mRequiredComponents, Component::GraphemeClusterBoundary);
271    }
272
273
274    StreamSet * LineBreakStream = P->CreateStreamSet();
275    std::vector<StreamSet *> MatchResultsBufs(numOfREs);
276
277    re::RE * prefixRE;
278    re::RE * suffixRE;
279
280    // For simple regular expressions with a small number of characters, we
281    // can bypass transposition and use the Direct CC compiler.
282    const auto isSimple = (numOfREs == 1) && (mGrepRecordBreak != GrepRecordBreakKind::Unicode) && (!anyGCB);
283    if (isSimple) {
284        mREs[0] = toUTF8(mREs[0]);
285    }
286
287    bool requiresComplexTest = true;
288    Component internalComponents = Component::NoComponents;
289
290
291    if (isSimple) {
292        if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL)) {
293            re::RE * notBreak = re::makeDiff(re::makeByte(0x00, 0xFF), mBreakCC);
294            mREs[0] = re::makeSeq({mREs[0], re::makeRep(notBreak, 0, re::Rep::UNBOUNDED_REP), makeNegativeLookAheadAssertion(notBreak)});
295            setComponent(internalComponents, Component::MoveMatchesToEOL);
296        }
297        const auto isWithinByteTestLimit = byteTestsWithinLimit(mREs[0], ByteCClimit);
298        const auto hasTriCC = hasTriCCwithinLimit(mREs[0], ByteCClimit, prefixRE, suffixRE);
299        ICGrepKernel::Externals externals;
300        if (isWithinByteTestLimit || hasTriCC) {
301            if (MultithreadedSimpleRE && hasTriCC) {
302                auto CCs = re::collectCCs(prefixRE, cc::Byte);
303                for (auto cc : CCs) {
304                    auto ccName = makeName(cc);
305                    mREs[0] = re::replaceCC(mREs[0], cc, ccName);
306                    auto ccNameStr = ccName->getFullName();
307                    StreamSet * const ccStream = P->CreateStreamSet(1, 1);
308                    P->CreateKernelCall<DirectCharacterClassKernelBuilder>(ccNameStr, std::vector<re::CC *>{cc}, ByteStream, ccStream);
309                    externals.emplace_back(ccNameStr, ccStream);
310                }
311            }
312            StreamSet * const MatchResults = P->CreateStreamSet(1, 1);
313            MatchResultsBufs[0] = MatchResults;
314            if (isWithinByteTestLimit) {
315                P->CreateKernelCall<ICGrepKernel>(mREs[0], ByteStream, MatchResults, externals);
316            } else {
317                P->CreateKernelCall<ByteBitGrepKernel>(prefixRE, suffixRE, ByteStream, MatchResults, externals);
318            }
319            P->CreateKernelCall<DirectCharacterClassKernelBuilder>( "breakCC", std::vector<re::CC *>{mBreakCC}, ByteStream, LineBreakStream);
320            requiresComplexTest = false;
321        }
322    }
323
324    if (requiresComplexTest) {
325
326        StreamSet * const BasisBits = P->CreateStreamSet(ENCODING_BITS, 1);
327        if (PabloTransposition) {
328            P->CreateKernelCall<S2P_PabloKernel>(ByteStream, BasisBits);
329        } else {
330            P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
331        }
332
333        StreamSet * const RequiredStreams = P->CreateStreamSet();
334        StreamSet * const UnicodeLB = P->CreateStreamSet();
335        StreamSet * const LineFeedStream = P->CreateStreamSet();
336
337        P->CreateKernelCall<LineFeedKernelBuilder>(BasisBits, LineFeedStream);
338        P->CreateKernelCall<RequiredStreams_UTF8>(BasisBits, LineFeedStream, RequiredStreams, UnicodeLB);
339
340        if (mGrepRecordBreak == GrepRecordBreakKind::LF) {
341            LineBreakStream = LineFeedStream;
342        } else if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
343            LineBreakStream = P->CreateStreamSet();
344            P->CreateKernelCall<DirectCharacterClassKernelBuilder>( "Null", std::vector<re::CC *>{mBreakCC}, BasisBits, LineBreakStream);
345        } else {
346            LineBreakStream = UnicodeLB;
347        }
348
349        std::map<std::string, StreamSet *> propertyStream;
350        if (PropertyKernels) {
351            for (auto p : mUnicodeProperties) {
352                auto name = p->getFullName();
353                StreamSet * property = P->CreateStreamSet(1, 1);
354                propertyStream.emplace(name, property);
355                P->CreateKernelCall<UnicodePropertyKernelBuilder>(p, BasisBits, property);
356            }
357        }
358
359        StreamSet * GCB_stream = nullptr;
360        if (hasComponent(mRequiredComponents, Component::GraphemeClusterBoundary)) {
361            GCB_stream = P->CreateStreamSet();
362            P->CreateKernelCall<GraphemeClusterBreakKernel>(BasisBits, RequiredStreams, GCB_stream);
363        }
364
365        for(unsigned i = 0; i < numOfREs; ++i) {
366            ICGrepKernel::Externals externals;
367            if (mGrepRecordBreak == GrepRecordBreakKind::Unicode) {
368                externals.emplace_back("UTF8_LB", LineBreakStream);
369                externals.emplace_back("UTF8_nonfinal", RequiredStreams);
370            }
371            std::set<re::Name *> UnicodeProperties;
372            if (PropertyKernels) {
373                re::gatherUnicodeProperties(mREs[i], UnicodeProperties);
374                for (const auto & p : UnicodeProperties) {
375                    auto name = p->getFullName();
376                    const auto f = propertyStream.find(name);
377                    if (LLVM_UNLIKELY(f == propertyStream.end())) {
378                        report_fatal_error(name + " not found");
379                    }
380                    externals.emplace_back(name, f->second);
381                }
382            }
383            if (hasGCB[i]) { assert (GCB_stream);
384                externals.emplace_back("\\b{g}", GCB_stream);
385            }
386
387            StreamSet * const MatchResults = P->CreateStreamSet(1, 1);
388            MatchResultsBufs[i] = MatchResults;
389
390            if (CC_Multiplexing) {
391                const auto UnicodeSets = re::collectCCs(mREs[i], cc::Unicode, std::set<re::Name *>{re::makeZeroWidth("\\b{g}")});
392                if (UnicodeSets.size() <= 1) {
393                    P->CreateKernelCall<ICGrepKernel>(mREs[i], BasisBits, MatchResults, externals);
394                } else {
395                    auto mpx = std::make_shared<MultiplexedAlphabet>("mpx", UnicodeSets);
396                    mREs[i] = transformCCs(mpx, mREs[i]);
397                    auto mpx_basis = mpx->getMultiplexedCCs();
398                    StreamSet * const CharClasses = P->CreateStreamSet(mpx_basis.size());
399                    P->CreateKernelCall<CharClassesKernel>(std::move(mpx_basis), BasisBits, CharClasses);
400
401                    #warning TODO: multiplexed CCs ought to generate unique names. Make the name also dependent on alphabet.
402                    // Multiplexing Grep Kernel is not Cachable, since for now it use string representation of RE AST as cache key,
403                    // whileit is possible that two multiplexed REs with the same name "mpx_1" have different alphabets
404
405                    Alphabets alphabets;
406                    alphabets.emplace_back(mpx, CharClasses);
407                    P->CreateKernelCall<ICGrepKernel>(mREs[i], BasisBits, MatchResults, externals, alphabets, cc::BitNumbering::LittleEndian, false);
408                }
409            } else {
410                P->CreateKernelCall<ICGrepKernel>(mREs[i], BasisBits, MatchResults, externals);
411            }
412        }
413
414    } // end of requiresComplexTest
415
416    StreamSet * Matches = MatchResultsBufs[0];
417    if (MatchResultsBufs.size() > 1) {
418        StreamSet * const MergedMatches = P->CreateStreamSet();
419        P->CreateKernelCall<StreamsMerge>(MatchResultsBufs, MergedMatches);
420        Matches = MergedMatches;
421    }
422    if (hasComponent(mRequiredComponents, Component::MoveMatchesToEOL) && !hasComponent(internalComponents, Component::MoveMatchesToEOL)) {
423        StreamSet * const MovedMatches = P->CreateStreamSet();
424        P->CreateKernelCall<MatchedLinesKernel>(Matches, LineBreakStream, MovedMatches);
425        Matches = MovedMatches;
426    }
427    if (mInvertMatches) {
428        StreamSet * const InvertedMatches = P->CreateStreamSet();
429        P->CreateKernelCall<InvertMatchesKernel>(Matches, LineBreakStream, InvertedMatches);
430        Matches = InvertedMatches;
431    }
432    if (mMaxCount > 0) {
433        StreamSet * const TruncatedMatches = P->CreateStreamSet();
434        Scalar * const maxCount = P->getInputScalar("maxCount");
435        P->CreateKernelCall<UntilNkernel>(maxCount, Matches, TruncatedMatches);
436        Matches = TruncatedMatches;
437    }
438    return std::pair<StreamSet *, StreamSet *>(LineBreakStream, Matches);
439}
440
441
442
443// The QuietMode, MatchOnly and CountOnly engines share a common code generation main function,
444// which returns a count of the matches found (possibly subject to a MaxCount).
445//
446
447void GrepEngine::grepCodeGen() {
448    auto & idb = mGrepDriver.getBuilder();
449
450    auto P = mGrepDriver.makePipeline(
451                // inputs
452                {Binding{idb->getInt8Ty(), "useMMap"},
453                Binding{idb->getInt32Ty(), "fileDescriptor"},
454                Binding{idb->getIntAddrTy(), "callbackObject"},
455                Binding{idb->getSizeTy(), "maxCount"}}
456                ,// output
457                {Binding{idb->getInt64Ty(), "countResult"}});
458
459    Scalar * const useMMap = P->getInputScalar("useMMap");
460    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
461
462    StreamSet * const ByteStream = P->CreateStreamSet(1, ENCODING_BITS);
463    P->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
464    StreamSet * const Matches = grepPipeline(P, ByteStream).second;
465    P->CreateKernelCall<PopcountKernel>(Matches, P->getOutputScalar("countResult"));
466
467    mMainMethod = P->compile();
468}
469
470//
471//  Default Report Match:  lines are emitted with whatever line terminators are found in the
472//  input.  However, if the final line is not terminated, a new line is appended.
473//
474void EmitMatch::accumulate_match (const size_t lineNum, char * line_start, char * line_end) {
475    mResultStr << mLinePrefix;
476    if (mShowLineNumbers) {
477        // Internally line numbers are counted from 0.  For display, adjust
478        // the line number so that lines are numbered from 1.
479        if (mInitialTab) {
480            mResultStr << lineNum+1 << "\t:";
481        }
482        else {
483            mResultStr << lineNum+1 << ":";
484        }
485    }
486
487    const auto bytes = line_end - line_start + 1;
488    mResultStr.write(line_start, bytes);
489    mLineCount++;
490    unsigned last_byte = *line_end;
491    mTerminated = (last_byte >= 0x0A) && (last_byte <= 0x0D);
492    if (LLVM_UNLIKELY(!mTerminated)) {
493        if (last_byte == 0x85) {  //  Possible NEL terminator.
494            mTerminated = (bytes >= 2) && (static_cast<unsigned>(line_end[-1]) == 0xC2);
495        }
496        else {
497            // Possible LS or PS terminators.
498            mTerminated = (bytes >= 3) && (static_cast<unsigned>(line_end[-2]) == 0xE2)
499                                       && (static_cast<unsigned>(line_end[-1]) == 0x80)
500                                       && ((last_byte == 0xA8) || (last_byte == 0xA9));
501        }
502    }
503}
504
505void EmitMatch::finalize_match(char * buffer_end) {
506    if (!mTerminated) mResultStr << "\n";
507}
508
509void EmitMatchesEngine::grepCodeGen() {
510    auto & idb = mGrepDriver.getBuilder();
511
512    auto E = mGrepDriver.makePipeline(
513                // inputs
514                {Binding{idb->getInt8Ty(), "useMMap"},
515                Binding{idb->getInt32Ty(), "fileDescriptor"},
516                Binding{idb->getIntAddrTy(), "callbackObject"},
517                Binding{idb->getSizeTy(), "maxCount"}}
518                ,// output
519                {Binding{idb->getInt64Ty(), "countResult"}});
520
521    Scalar * const useMMap = E->getInputScalar("useMMap");
522    Scalar * const fileDescriptor = E->getInputScalar("fileDescriptor");
523
524    StreamSet * const ByteStream = E->CreateStreamSet(1, ENCODING_BITS);
525    E->CreateKernelCall<FDSourceKernel>(useMMap, fileDescriptor, ByteStream);
526
527    StreamSet * LineBreakStream;
528    StreamSet * Matches;
529    std::tie(LineBreakStream, Matches) = grepPipeline(E, ByteStream);
530
531    Scalar * const callbackObject = E->getInputScalar("callbackObject");
532    Kernel * const scanMatchK = E->CreateKernelCall<ScanMatchKernel>(Matches, LineBreakStream, ByteStream, callbackObject);
533    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
534    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
535
536    E->setOutputScalar("countResult", E->CreateConstant(idb->getInt64(0)));
537
538    mMainMethod = E->compile();
539}
540
541
542//
543//  The doGrep methods apply a GrepEngine to a single file, processing the results
544//  differently based on the engine type.
545
546bool canMMap(const std::string & fileName) {
547    if (fileName == "-") return false;
548    namespace fs = boost::filesystem;
549    fs::path p(fileName);
550    boost::system::error_code errc;
551    fs::file_status s = fs::status(p, errc);
552    return !errc && is_regular_file(s);
553}
554
555
556uint64_t GrepEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
557    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, GrepCallBackObject *, size_t maxCount);
558    bool useMMap = mPreferMMap && canMMap(fileName);
559    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
560
561    int32_t fileDescriptor = openFile(fileName, strm);
562    if (fileDescriptor == -1) return 0;
563    GrepCallBackObject handler;
564    uint64_t grepResult = f(useMMap, fileDescriptor, &handler, mMaxCount);
565
566    close(fileDescriptor);
567    if (handler.binaryFileSignalled()) {
568        return 0;
569    }
570    else {
571        showResult(grepResult, fileName, strm);
572        return grepResult;
573    }
574}
575
576std::string GrepEngine::linePrefix(std::string fileName) {
577    if (!mShowFileNames) return "";
578    if (fileName == "-") {
579        return mStdinLabel + mFileSuffix;
580    }
581    else {
582        return fileName + mFileSuffix;
583    }
584}
585
586// Default: do not show anything
587void GrepEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
588}
589
590void CountOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
591    if (mShowFileNames) strm << linePrefix(fileName);
592    strm << grepResult << "\n";
593}
594
595void MatchOnlyEngine::showResult(uint64_t grepResult, const std::string & fileName, std::ostringstream & strm) {
596    if (grepResult == mRequiredCount) {
597       strm << linePrefix(fileName);
598    }
599}
600
601uint64_t EmitMatchesEngine::doGrep(const std::string & fileName, std::ostringstream & strm) {
602    typedef uint64_t (*GrepFunctionType)(bool useMMap, int32_t fileDescriptor, EmitMatch *, size_t maxCount);
603    bool useMMap = mPreferMMap && canMMap(fileName);
604    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
605    int32_t fileDescriptor = openFile(fileName, strm);
606    if (fileDescriptor == -1) return 0;
607    EmitMatch accum(linePrefix(fileName), mShowLineNumbers, mInitialTab, strm);
608    f(useMMap, fileDescriptor, &accum, mMaxCount);
609    close(fileDescriptor);
610    if (accum.binaryFileSignalled()) {
611        accum.mResultStr.clear();
612        accum.mResultStr << "Binary file " << fileName << " skipped.\n";
613    }
614    if (accum.mLineCount > 0) grepMatchFound = true;
615    return accum.mLineCount;
616}
617
618// Open a file and return its file desciptor.
619int32_t GrepEngine::openFile(const std::string & fileName, std::ostringstream & msgstrm) {
620    if (fileName == "-") {
621        return STDIN_FILENO;
622    }
623    else {
624        struct stat sb;
625        int32_t fileDescriptor = open(fileName.c_str(), O_RDONLY);
626        if (LLVM_UNLIKELY(fileDescriptor == -1)) {
627            if (!mSuppressFileMessages) {
628                if (errno == EACCES) {
629                    msgstrm << "icgrep: " << fileName << ": Permission denied.\n";
630                }
631                else if (errno == ENOENT) {
632                    msgstrm << "icgrep: " << fileName << ": No such file.\n";
633                }
634                else {
635                    msgstrm << "icgrep: " << fileName << ": Failed.\n";
636                }
637            }
638            return fileDescriptor;
639        }
640        if (stat(fileName.c_str(), &sb) == 0 && S_ISDIR(sb.st_mode)) {
641            if (!mSuppressFileMessages) {
642                msgstrm << "icgrep: " << fileName << ": Is a directory.\n";
643            }
644            close(fileDescriptor);
645            return -1;
646        }
647        return fileDescriptor;
648    }
649}
650
651// The process of searching a group of files may use a sequential or a task
652// parallel approach.
653
654void * DoGrepThreadFunction(void *args) {
655    assert (args);
656    return reinterpret_cast<GrepEngine *>(args)->DoGrepThreadMethod();
657}
658
659bool GrepEngine::searchAllFiles() {
660    const unsigned numOfThreads = std::min(static_cast<unsigned>(Threads), static_cast<unsigned>(inputPaths.size()));
661    std::vector<pthread_t> threads(numOfThreads);
662
663    for(unsigned long i = 1; i < numOfThreads; ++i) {
664        const int rc = pthread_create(&threads[i], nullptr, DoGrepThreadFunction, (void *)this);
665        if (rc) {
666            llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
667        }
668    }
669    // Main thread also does the work;
670    DoGrepThreadMethod();
671    for(unsigned i = 1; i < numOfThreads; ++i) {
672        void * status = nullptr;
673        const int rc = pthread_join(threads[i], &status);
674        if (rc) {
675            llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
676        }
677    }
678    return grepMatchFound;
679}
680
681
682// DoGrep thread function.
683void * GrepEngine::DoGrepThreadMethod() {
684
685    unsigned fileIdx = mNextFileToGrep++;
686    while (fileIdx < inputPaths.size()) {
687        if (codegen::DebugOptionIsSet(codegen::TraceCounts)) {
688            errs() << "Tracing " << inputPaths[fileIdx].string() << "\n";
689        }
690        const auto grepResult = doGrep(inputPaths[fileIdx].string(), mResultStrs[fileIdx]);
691        mFileStatus[fileIdx] = FileStatus::GrepComplete;
692        if (grepResult > 0) {
693            grepMatchFound = true;
694        }
695        if ((mEngineKind == EngineKind::QuietMode) && grepMatchFound) {
696            if (pthread_self() != mEngineThread) {
697                pthread_exit(nullptr);
698            }
699            return nullptr;
700        }
701        fileIdx = mNextFileToGrep++;
702    }
703
704    unsigned printIdx = mNextFileToPrint++;
705    while (printIdx < inputPaths.size()) {
706        const bool readyToPrint = ((printIdx == 0) || (mFileStatus[printIdx - 1] == FileStatus::PrintComplete)) && (mFileStatus[printIdx] == FileStatus::GrepComplete);
707        if (readyToPrint) {
708            const auto output = mResultStrs[printIdx].str();
709            if (!output.empty()) {
710                llvm::outs() << output;
711            }
712            mFileStatus[printIdx] = FileStatus::PrintComplete;
713            printIdx = mNextFileToPrint++;
714        }
715        //sched_yield();
716    }
717
718    if (pthread_self() != mEngineThread) {
719        pthread_exit(nullptr);
720    } else {
721        if (mGrepStdIn) {
722            std::ostringstream s;
723            const auto grepResult = doGrep("-", s);
724            llvm::outs() << s.str();
725            if (grepResult) grepMatchFound = true;
726        }
727    }
728    return nullptr;
729}
730
731InternalSearchEngine::InternalSearchEngine(BaseDriver &driver) :
732    mGrepRecordBreak(GrepRecordBreakKind::LF),
733    mCaseInsensitive(false),
734    mGrepDriver(driver),
735    mMainMethod(nullptr) {}
736
737void InternalSearchEngine::grepCodeGen(re::RE * matchingRE, re::RE * excludedRE) {
738    auto & idb = mGrepDriver.getBuilder();
739    mSaveSegmentPipelineParallel = codegen::SegmentPipelineParallel;
740    codegen::SegmentPipelineParallel = false;
741
742    re::CC * breakCC = nullptr;
743    if (mGrepRecordBreak == GrepRecordBreakKind::Null) {
744        breakCC = re::makeByte(0x0);
745    } else {// if (mGrepRecordBreak == GrepRecordBreakKind::LF)
746        breakCC = re::makeByte(0x0A);
747    }
748    bool excludeNothing = (excludedRE == nullptr) || (isa<re::Alt>(excludedRE) && cast<re::Alt>(excludedRE)->empty());
749    bool matchAllLines = (matchingRE == nullptr) || isa<re::End>(matchingRE);
750    if (!matchAllLines) {
751        matchingRE = resolveCaseInsensitiveMode(matchingRE, mCaseInsensitive);
752        matchingRE = regular_expression_passes(matchingRE);
753        matchingRE = re::exclude_CC(matchingRE, breakCC);
754        matchingRE = resolveAnchors(matchingRE, breakCC);
755        matchingRE = toUTF8(matchingRE);
756    }
757    if (!excludeNothing) {
758        excludedRE = resolveCaseInsensitiveMode(excludedRE, mCaseInsensitive);
759        excludedRE = regular_expression_passes(excludedRE);
760        excludedRE = re::exclude_CC(excludedRE, breakCC);
761        excludedRE = resolveAnchors(excludedRE, breakCC);
762        excludedRE = toUTF8(excludedRE);
763    }
764
765    auto E = mGrepDriver.makePipeline({Binding{idb->getInt8PtrTy(), "buffer"},
766                                       Binding{idb->getSizeTy(), "length"},
767                                       Binding{idb->getIntAddrTy(), "accumulator"}});
768
769    Scalar * const buffer = E->getInputScalar(0);
770    Scalar * const length = E->getInputScalar(1);
771    StreamSet * ByteStream = E->CreateStreamSet(1, 8);
772    E->CreateKernelCall<MemorySourceKernel>(buffer, length, ByteStream);
773
774
775    StreamSet * RecordBreakStream = E->CreateStreamSet();
776    const auto RBname = (mGrepRecordBreak == GrepRecordBreakKind::Null) ? "Null" : "LF";
777
778    StreamSet * BasisBits = nullptr;
779
780    if (matchAllLines && excludeNothing) {
781        E->CreateKernelCall<DirectCharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, ByteStream, RecordBreakStream);
782    } else {
783        BasisBits = E->CreateStreamSet(8);
784        E->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
785        E->CreateKernelCall<ParabixCharacterClassKernelBuilder>(RBname, std::vector<re::CC *>{breakCC}, BasisBits, RecordBreakStream);
786    }
787
788    StreamSet * MatchingRecords = nullptr;
789    if (matchAllLines) {
790        MatchingRecords = RecordBreakStream;
791    } else {
792        StreamSet * MatchResults = E->CreateStreamSet();
793        E->CreateKernelCall<ICGrepKernel>(matchingRE, BasisBits, MatchResults);
794        MatchingRecords = E->CreateStreamSet();
795        E->CreateKernelCall<MatchedLinesKernel>(MatchResults, RecordBreakStream, MatchingRecords);
796    }
797    if (!excludeNothing) {
798        StreamSet * ExcludedResults = E->CreateStreamSet();
799        E->CreateKernelCall<ICGrepKernel>(excludedRE, BasisBits, ExcludedResults);
800        StreamSet * ExcludedRecords = E->CreateStreamSet();
801        E->CreateKernelCall<MatchedLinesKernel>(ExcludedResults, RecordBreakStream, ExcludedRecords);
802
803        if (!matchAllLines) {
804            StreamSet * nonExcluded = E->CreateStreamSet();
805            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, nonExcluded);
806            StreamSet * const included = MatchingRecords;
807            MatchingRecords = E->CreateStreamSet();
808            E->CreateKernelCall<StreamsIntersect>(std::vector<StreamSet *>{included, nonExcluded}, MatchingRecords);
809        } else {
810            MatchingRecords = E->CreateStreamSet();
811            E->CreateKernelCall<InvertMatchesKernel>(ExcludedRecords, RecordBreakStream, MatchingRecords);
812        }
813    }
814
815    Kernel * scanMatchK = E->CreateKernelCall<ScanMatchKernel>(MatchingRecords, RecordBreakStream, ByteStream, E->getInputScalar(2));
816    mGrepDriver.LinkFunction(scanMatchK, "accumulate_match_wrapper", accumulate_match_wrapper);
817    mGrepDriver.LinkFunction(scanMatchK, "finalize_match_wrapper", finalize_match_wrapper);
818
819    mMainMethod = E->compile();
820}
821
822void InternalSearchEngine::doGrep(const char * search_buffer, size_t bufferLength, MatchAccumulator & accum) {
823    typedef void (*GrepFunctionType)(const char * buffer, const size_t length, MatchAccumulator *);
824    auto f = reinterpret_cast<GrepFunctionType>(mMainMethod);
825    f(search_buffer, bufferLength, &accum);
826    codegen::SegmentPipelineParallel = mSaveSegmentPipelineParallel;
827}
828
829GrepEngine::~GrepEngine() { }
830
831InternalSearchEngine::InternalSearchEngine(const std::unique_ptr<grep::GrepEngine> & engine)
832: InternalSearchEngine(engine->mGrepDriver) {
833
834}
835
836InternalSearchEngine::~InternalSearchEngine() { }
837
838}
Note: See TracBrowser for help on using the repository browser.