HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_TagManager.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_TagManager.h ( UT Library, C++)
7  *
8  * COMMENTS: Manage lists of tags. Tags are simply name strings. A list of
9  * tags is a list of names. The names may contain alphanumeric characters
10  * along with the characters:
11  * '_' (underscore)
12  * '.' (period)
13  * '-' (minus) (we also support ^)
14  * ':' (colon)
15  * Names may NOT begin with '-' (minus). Invalid characters will be
16  * forced to an '_' (underscore) character.
17  *
18  * Pattern expression can also be created which can be matched against tag
19  * lists (see below for more documentation).
20  *
21  * A global list of used tags are kept and may be retrieved. The list is
22  * not cleared (TODO: it would be nice to have a garbage collection
23  * process)
24  */
25 
26 #ifndef __UT_TagManager__
27 #define __UT_TagManager__
28 
29 #include "UT_API.h"
30 #include "UT_SymbolTable.h"
31 #include "UT_SmallObject.h"
32 #include "UT_IntrusivePtr.h"
33 #include "UT_IntArray.h"
34 #include "UT_BitArray.h"
35 #include "UT_Memory.h"
36 #include "UT_ConcurrentVector.h"
37 #include "UT_ConcurrentHashMap.h"
38 #include "UT_HashFunctor.h"
39 
40 class UT_String;
41 class UT_StringArray;
42 class UT_TagManager;
43 class UT_TagList;
44 class UT_TagExpression;
45 
46 // #define UT_TAG_USE_SMALL_OBJECTS
47 
48 /// A comma separated list of tags (i.e. "fill,spot,red")
50  : public UT_IntrusiveRefCounter<UT_TagList>
51 #if defined(UT_TAG_USE_SMALL_OBJECTS)
52  , public UT_SmallObject<UT_TagList,
53  UT_SMALLOBJECT_CLEANPAGES_ON,
54  512,
55  UT_SMALLOBJECT_THREADSAFE_ON>
56 #endif
57 {
58 public:
59  UT_TagList(UT_TagManager &manager, const UT_IntArray &bits, int max);
60  UT_TagList(UT_TagManager &manager, int single_name_index);
61  ~UT_TagList();
62 
63  void getListString(UT_WorkBuffer &buffer) const;
64  bool match(const UT_TagExpression &pattern) const;
65  uint hash() const;
66  bool compare(const UT_TagList &list) const;
67 
68  bool operator==(const UT_TagList &list) const
69  { return compare(list); }
70  bool operator!=(const UT_TagList &list) const
71  { return !compare(list); }
72 
73  /// @{
74  /// Get the tag manager
75  const UT_TagManager &getManager() const { return myManager; }
76  UT_TagManager &getManager() { return myManager; }
77  /// @}
78 
80  { return sizeof(*this) + myBits.getMemoryUsage(); }
81 
82 private:
83  bool isEmpty() const
84  { return mySingle < 0 && myBits.size() == 0; }
85  bool hasTag(int id) const
86  {
87  return id == mySingle ||
88  (id < myBits.size() && myBits.getBit(id));
89  }
90  void validateList(int namecount);
91  void setSingleBit(int bit);
92 
93 private:
94  UT_TagManager &myManager;
95  UT_BitArray myBits;
96  int mySingle;
97  friend class UT_TagManager;
98  friend class UT_TagExpression;
99 
100 };
101 
102 /// An expression to match tags (i.e. "* & ^fill")
104  : public UT_IntrusiveRefCounter<UT_TagExpression>
105 #if defined(UT_TAG_USE_SMALL_OBJECTS)
106  , public UT_SmallObject<UT_TagExpression,
107  UT_SMALLOBJECT_CLEANPAGES_ON,
108  512,
109  UT_SMALLOBJECT_THREADSAFE_ON>
110 #endif
111 {
112 public:
114  ~UT_TagExpression();
115 
116  /// @{
117  /// Allocate a new expression with the appropriate edits
118 
119  /// (expr) -> A|(expr). However, we can also simplify some components of
120  /// expression. For example, (A|-A) -> * (Complementary Law)
121  UT_TagExpression *addTags(const UT_TagList &list) const;
122 
123  /// (expr) -> -A & (expr). Since | has a greater precedence, we need to
124  /// expand using distributive property. Some components of the expression
125  /// can be simplified (i.e. -A & A -> -*).
126  UT_TagExpression *rmTags(const UT_TagList &list) const;
127 
128  /// @}
129 
130  /// @{
131  /// Get the tag manager
132  const UT_TagManager &getManager() const { return myManager; }
133  UT_TagManager &getManager() { return myManager; }
134  /// @}
135 
136  bool compare(const UT_TagExpression &expr) const;
137  bool operator==(const UT_TagExpression &expr) const
138  { return compare(expr); }
139  bool operator!=(const UT_TagExpression &expr) const
140  { return !compare(expr); }
141  uint hash() const;
142 
143  void getExpressionString(UT_WorkBuffer &buffer) const;
144  bool match(const UT_TagList &list) const;
145  bool isTautology() const;
146 
147  /// Determine whether any known names match. The matching names will
148  /// be returned in 'matching' and names that don't match are put in
149  /// 'failing'. 'outmatch' will be set to true when unknown names will
150  /// produce a match.
151  void matchAllNames(UT_Array<const char *> &matching,
152  UT_Array<const char *> &failing,
153  bool &outmatch);
154 
156 
158  { return sizeof(*this) + myCode.getMemoryUsage(); }
159 private:
160  // Break up a complex expression into multiple sub-expressions which can be
161  // or'ed together.
162  void extractOrComponents(SubExpressionList &elist) const;
163 
164  // Combine multiple sub-expressions into a single expression by or'ing them
165  // together.
166  void combineOrComponents(const SubExpressionList &elist);
167 
168  static bool simplifyExpressions(SubExpressionList &elist,
169  int bit,
170  UT_TagExpression *expr,
171  UT_BitArray &need_final_or);
172  static void addExpressionOr(UT_TagExpression *expr,
173  int bit,
174  const UT_BitArray &need_final_or);
175 
176  void clear();
177  void validateExpr(int namecount);
178  void addOpCode(int opcode, int operand = 0);
179  bool addOpCode(UT_IntArray &stack)
180  {
181  int n;
182  n = stack.entries();
183  if (n < 2)
184  return false;
185  addOpCode(stack(n-2), stack(n-1));
186  stack.entries(n-2);
187  return true;
188  }
189 
190 
191 private:
192  UT_TagManager &myManager;
193  UT_IntArray myCode;
194  friend class UT_TagManager;
195 };
196 
199 
200 /// A tag manager keeps track of lists of tags and expressions. It stores them
201 /// very compactly for efficient processing.
203 {
204 public:
205  class WeakKey
206  {
207  public:
208  // Copy in as a weak pointer when passed a const char *
209  WeakKey(const char *key)
210  : myKey(UTmakeUnsafeRef(key))
211  {
212  }
213  // Given a UT_StringHolder, we can just store the holder
215  : myKey(key)
216  {
217  }
218  // The copy c-tor is used when inserting into the map, so we need to
219  // ensure the key is hardened.
220  WeakKey(const WeakKey &k)
221  : myKey(k.myKey.c_str()) // UT_StringHolder will duplicate
222  {
223  }
224  WeakKey &operator=(const WeakKey &key)
225  {
226  // We need to harden the string in the source key
227  myKey = UT_StringHolder(key.c_str());
228  return *this;
229  }
230  const char *c_str() const { return myKey.c_str(); }
231  uint hash() const { return myKey.hash(); }
232  bool operator==(const WeakKey &k) const
233  {
234  return myKey == k.myKey;
235  }
236  private:
237  UT_StringHolder myKey;
238  };
239  using tag_ListType = UT_ConcurrentVector<const char *>;
242  UT_TagManager();
243  ~UT_TagManager();
244 
245  /// getTagList() creates a tag-list object. This is a list of names which
246  /// are considered as tags for matching (see below).
247  /// The names allow alphanumeric letters and characters from "_.:"
248  UT_TagListPtr createList(const char *list, UT_String &errs)
249  {
250  return UT_TagListPtr(createTagList(list, errs));
251  }
253  {
254  return UT_TagListPtr(createTagListForName(name_index));
255  }
256 
257  /// createTagExpression() is used to create a pattern to match against tag
258  /// lists.
259  ///
260  /// The tag expression can be a very simple expression consisting of
261  /// - @b name @n Matches tag lists which have the name
262  /// - @b -name @n Matches tag lists which do NOT contain the name
263  /// - @b + @n Matches tag lists which have ANY entries
264  /// - @b - @n Matches tag lists which have NO entries
265  /// - @b * @n Matches all tag lists (Equivalent to "+|-")
266  /// - @b -* @n Matches no tag lists (Equivalend to "+&-")
267  ///
268  /// Expressions may be joined with & or | (AND or OR). For example
269  /// - <tt>-foo</tt> @n Match all tags except those with "foo"
270  /// - <tt>* & -foo</tt> @n Equivalent to "-foo"
271  /// - <tt>-foo & -bar</tt> @n
272  /// Match all tags except those with "foo" or "bar"
273  /// - <tt>foo & -bar</tt> @n
274  /// Match all tags that have "foo" but don't have "bar"
275  ///
276  /// Expressions are processed left to right with AND at a higher
277  /// precedence in the order of operations than OR. Thus:
278  /// @code
279  /// a & b & c | d & e | f | g & h
280  /// @endcode
281  /// is equivalent to:
282  /// @code
283  /// (a & b & c) | (d & e) | f | (g & h)
284  /// @endcode
285  ///
286  /// @note You are responsible for deleting this
287  /// Smart pointer access to tag expressions
289  UT_String &errs)
290  {
291  return UT_TagExpressionPtr(
292  createTagExpression(expr, errs));
293  }
294 
296  {
297  TAG_OP_ADD, // Add name to expression
298  TAG_OP_RM, // Remove name from expression
299  TAG_OP_SET, // Set the expression to the name
300  };
301 
302  /// Apply an edit to an expression. This operation may have bugs, but will
303  /// always work on a simplified expression.
304  UT_TagExpressionPtr editExpression(const UT_TagExpressionPtr &expr,
305  const char *name,
306  UT_TagEditOperation op,
307  UT_String &errors);
308 
309  /// Get a list of all the tags used by any list or pattern we've
310  /// constructed
311  void getAllNames(UT_StringArray &tags);
312 
313  /// @private accessors
314  const tag_ListType &nameList() const { return myNameList; }
315 
316 private:
317  UT_TagList *createTagListForName(int name_index);
318  UT_TagList *createTagList(const char *list,
319  UT_String &errs);
320  UT_TagExpression *createTagExpression(const char *expression,
321  UT_String &errs);
322 
323  // Returns the index of the the tag
324  int findOrCreateTag(const char *tag);
325 
326  tag_MapType myNameTable;
327  tag_ListType myNameList;
328 
329  friend class UT_TagList;
330  friend class UT_TagExpression;
331 };
332 
333 #endif
An expression to match tags (i.e. "* & ^fill")
bool operator!=(const UT_TagList &list) const
Definition: UT_TagManager.h:70
WeakKey(const UT_StringHolder &key)
UT_IntrusivePtr< UT_TagExpression > UT_TagExpressionPtr
const char * c_str() const
#define UT_API
Definition: UT_API.h:12
bool operator!=(const UT_TagExpression &expr) const
const UT_TagManager & getManager() const
UT_ConcurrentVector< const char * > tag_ListType
bool operator==(const UT_TagExpression &expr) const
A reference counter base class for use with UT_IntrusivePtr.
GLuint buffer
Definition: glcorearb.h:659
UT_TagListPtr createList(const char *list, UT_String &errs)
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
bool operator==(const UT_TagList &list) const
Definition: UT_TagManager.h:68
long long int64
Definition: SYS_Types.h:106
GLdouble n
Definition: glcorearb.h:2007
UT_TagManager & getManager()
WeakKey(const char *key)
SYS_FORCE_INLINE const UT_StringHolder & UTmakeUnsafeRef(const UT_StringRef &ref)
Convert a UT_StringRef into a UT_StringHolder that is a shallow reference.
A comma separated list of tags (i.e. "fill,spot,red")
Definition: UT_TagManager.h:49
Wrapper around hboost::intrusive_ptr.
UT_ConcurrentHashMap< WeakKey, int, UT_HashFunctor< WeakKey > > tag_MapType
GLuint const GLchar * name
Definition: glcorearb.h:785
unsigned int uint
Definition: SYS_Types.h:39
WeakKey(const WeakKey &k)
UT_IntrusivePtr< UT_TagList > UT_TagListPtr
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:446
#define UT_ConcurrentHashMap
UT_TagListPtr createListForName(int name_index)
WeakKey & operator=(const WeakKey &key)
typedef int
Definition: png.h:1175
const UT_TagManager & getManager() const
Definition: UT_TagManager.h:75
int64 getMemUsage() const
int64 getMemUsage() const
Definition: UT_TagManager.h:79
UT_TagManager & getManager()
Definition: UT_TagManager.h:76
bool operator==(const WeakKey &k) const
UT_TagExpressionPtr createExpression(const char *expr, UT_String &errs)