// © 2016 and later: Unicode, Inc. and others. // License & terms of use: http://www.unicode.org/copyright.html // // rbbitblb.h // /* ********************************************************************** * Copyright (c) 2002-2016, International Business Machines * Corporation and others. All Rights Reserved. ********************************************************************** */ #ifndef RBBITBLB_H #define RBBITBLB_H #include "unicode/utypes.h" #include "unicode/uobject.h" #include "unicode/rbbi.h" #include "rbbirb.h" #include "rbbinode.h" U_NAMESPACE_BEGIN class RBBIRuleScanner; class RBBIRuleBuilder; class UVector32; // // class RBBITableBuilder is part of the RBBI rule compiler. // It builds the state transition table used by the RBBI runtime // from the expression syntax tree generated by the rule scanner. // // This class is part of the RBBI implementation only. // There is no user-visible public API here. // class RBBITableBuilder : public UMemory { public: RBBITableBuilder(RBBIRuleBuilder *rb, RBBINode **rootNode, UErrorCode &status); ~RBBITableBuilder(); void buildForwardTable(); /** Return the runtime size in bytes of the built state table. */ int32_t getTableSize() const; /** Fill in the runtime state table. Sufficient memory must exist at the specified location. */ void exportTable(void *where); /** * Find duplicate (redundant) character classes. Begin looking with categories.first. * Duplicate, if found are returned in the categories parameter. * This is an iterator-like function, used to identify character classes * (state table columns) that can be eliminated. * @param categories in/out parameter, specifies where to start looking for duplicates, * and returns the first pair of duplicates found, if any. * @return true if duplicate char classes were found, false otherwise. */ bool findDuplCharClassFrom(IntPair *categories); /** Remove a column from the state table. Used when two character categories * have been found equivalent, and merged together, to eliminate the uneeded table column. */ void removeColumn(int32_t column); /** Check for, and remove dupicate states (table rows). */ void removeDuplicateStates(); /** Build the safe reverse table from the already-constructed forward table. */ void buildSafeReverseTable(UErrorCode &status); /** Return the runtime size in bytes of the built safe reverse state table. */ int32_t getSafeTableSize() const; /** Fill in the runtime safe state table. Sufficient memory must exist at the specified location. */ void exportSafeTable(void *where); private: void calcNullable(RBBINode *n); void calcFirstPos(RBBINode *n); void calcLastPos(RBBINode *n); void calcFollowPos(RBBINode *n); void calcChainedFollowPos(RBBINode *n); void bofFixup(); void buildStateTable(); void flagAcceptingStates(); void flagLookAheadStates(); void flagTaggedStates(); void mergeRuleStatusVals(); /** * Merge redundant state table columns, eliminating character classes with identical behavior. * Done after the state tables are generated, just before converting to their run-time format. */ int32_t mergeColumns(); void addRuleRootNodes(UVector *dest, RBBINode *node); /** * Find duplicate (redundant) states, beginning at the specified pair, * within this state table. This is an iterator-like function, used to * identify states (state table rows) that can be eliminated. * @param states in/out parameter, specifies where to start looking for duplicates, * and returns the first pair of duplicates found, if any. * @return true if duplicate states were found, false otherwise. */ bool findDuplicateState(IntPair *states); /** Remove a duplicate state. * @param duplStates The duplicate states. The first is kept, the second is removed. * All references to the second in the state table are retargeted * to the first. */ void removeState(IntPair duplStates); /** Find the next duplicate state in the safe reverse table. An iterator function. * @param states in/out parameter, specifies where to start looking for duplicates, * and returns the first pair of duplicates found, if any. * @return true if a duplicate pair of states was found. */ bool findDuplicateSafeState(IntPair *states); /** Remove a duplicate state from the safe table. * @param duplStates The duplicate states. The first is kept, the second is removed. * All references to the second in the state table are retargeted * to the first. */ void removeSafeState(IntPair duplStates); // Set functions for UVector. // TODO: make a USet subclass of UVector void setAdd(UVector *dest, UVector *source); UBool setEquals(UVector *a, UVector *b); void sortedAdd(UVector **dest, int32_t val); public: #ifdef RBBI_DEBUG void printSet(UVector *s); void printPosSets(RBBINode *n /* = NULL*/); void printStates(); void printRuleStatusTable(); void printReverseTable(); #else #define printSet(s) #define printPosSets(n) #define printStates() #define printRuleStatusTable() #define printReverseTable() #endif private: RBBIRuleBuilder *fRB; RBBINode *&fTree; // The root node of the parse tree to build a // table for. UErrorCode *fStatus; /** State Descriptors, UVector<RBBIStateDescriptor> */ UVector *fDStates; // D states (Aho's terminology) // Index is state number // Contents are RBBIStateDescriptor pointers. /** Synthesized safe table, UVector of UnicodeString, one string per table row. */ UVector *fSafeTable; RBBITableBuilder(const RBBITableBuilder &other); // forbid copying of this class RBBITableBuilder &operator=(const RBBITableBuilder &other); // forbid copying of this class }; // // RBBIStateDescriptor - The DFA is constructed as a set of these descriptors, // one for each state. class RBBIStateDescriptor : public UMemory { public: UBool fMarked; int32_t fAccepting; int32_t fLookAhead; UVector *fTagVals; int32_t fTagsIdx; UVector *fPositions; // Set of parse tree positions associated // with this state. Unordered (it's a set). // UVector contents are RBBINode * UVector32 *fDtran; // Transitions out of this state. // indexed by input character // contents is int index of dest state // in RBBITableBuilder.fDStates RBBIStateDescriptor(int maxInputSymbol, UErrorCode *fStatus); ~RBBIStateDescriptor(); private: RBBIStateDescriptor(const RBBIStateDescriptor &other); // forbid copying of this class RBBIStateDescriptor &operator=(const RBBIStateDescriptor &other); // forbid copying of this class }; U_NAMESPACE_END #endif