fixed issue with version check
[feisty_meow.git] / infobase / examples / cpp_grammar_code / CxxParsing.cxx
1 #include <iostream.h>
2 #include <memory.h>
3 #include <CxxToken.hxx>
4
5 extern CxxToken *yylex_token();
6
7 #ifdef BISON_PP_CLASS
8 BISON_PP_CLASS theParser;
9 #define PARSE_DOT theParser .
10 #define PARSE_SCOPE BISON_PP_CLASS ::
11 #else
12 #define PARSE_DOT
13 #define PARSE_SCOPE
14 extern int yydebug;
15 #ifndef YYEMPTY
16 #define YYEMPTY -1
17 #endif
18 #endif
19
20 class CxxSearchContext
21 {
22     friend class ios;                   // Suppress GNU error message for no public constructors.
23         CxxSearchContext *_next;
24         size_t _index;
25         size_t _depth;
26         size_t _size;
27         size_t _mark;
28         bool _enable_type1;
29         size_t _line;
30         size_t _advances;
31         bool _status[32];
32 private:
33         CxxSearchContext(CxxSearchContext *nextSearch)
34                 : _next(nextSearch), _index(0), _depth(0), _size(sizeof(_status)/sizeof(_status[0])),
35                 _mark(0), _enable_type1(false), _line(0), _advances(0) {}
36         CxxSearchContext(const CxxSearchContext&);
37         CxxSearchContext& operator=(const CxxSearchContext&);
38         bool did_search() const { return _depth > 0 ? true : false; }
39         void initialise(size_t markIndex, bool enableType1);
40         CxxSearchContext *queue(CxxSearchContext *& listHead);
41         void reset();
42 public:
43         bool advance();
44         bool enable_type1() const { return _enable_type1; }
45         bool is_template();
46         size_t mark() const { return _mark; }
47 private:
48         static CxxSearchContext *_current;
49         static CxxSearchContext *_free;
50 public:
51         static size_t actual_searches;
52         static size_t advances[16];
53         static size_t max_search_depth;
54         static size_t nested_searches;
55         static size_t releases;
56         static size_t search_advances;
57         static size_t unnested_searches;
58 public:
59         static CxxSearchContext *current() { return _current; }
60         static void release();
61         static void start(YACC_MARK_TYPE anIndex, bool enableType1);
62 };
63
64 size_t bang_depth = 0;
65 size_t error_count = 0;
66 size_t marked_error_count = 0;
67 bool in_type1 = false;
68 bool show_marked = false;
69
70 int main(int argc, char *argv[])
71 {
72         for (--argc, ++argv; argc-- > 0; ++argv)
73         {
74                 char *p = *argv;
75                 if (*p == '-')
76                 {
77                         switch (*(p+1))
78                         {
79                                 case 'c':
80                                         c_keywords = true;
81                                         break;
82                                 case 't':
83                                         echo_line_text = true;
84                                         break;
85                                 case 'm':
86                                         show_marked = true;
87                                         break;
88                                 case 'n':
89                                         echo_line_numbers = true;
90                                         break;
91                                 case 'y':
92                                         PARSE_DOT yydebug = true;
93                                         break;
94                         }
95                 }
96         }
97         if (PARSE_DOT yyparse() != 0)
98                 ERRMSG("Failed to parse to end of file,");
99         cout << "error_count = " << error_count
100                  << ", marked_error_count = " << marked_error_count
101                  << ", lines = " << line_number
102                  << ", unnested_searches = " << CxxSearchContext::unnested_searches
103                  << ", nested_searches = " << CxxSearchContext::nested_searches
104                  << ", releases = " << CxxSearchContext::releases
105                  << ", actual_searches = " << CxxSearchContext::actual_searches
106                  << ", max_search_depth = " << CxxSearchContext::max_search_depth
107                  << ", search_advances = " << CxxSearchContext::search_advances << endl;
108         cout << "number of occurences of each advance"; 
109         for (size_t i = 0; i < sizeof(CxxSearchContext::advances)/sizeof(CxxSearchContext::advances[0]); i++)
110                 cout << ' ' << CxxSearchContext::advances[i];
111         cout << endl;   
112         return 0;
113 }
114
115 static CxxToken **tokenBuffer = 0;                              // Allocated buffer
116 static YACC_MARK_TYPE tokenReadIndex = 0;               // Read index
117 static size_t tokenSize = 0;                                    // Allocate buffer size
118 static YACC_MARK_TYPE tokenWriteIndex = 0;              // Write index
119 int tokenMarkDepth = 0;                                         // Write index
120 static CxxToken *primed_tokens[3] = {0, 0};             // Restarting sequence
121 static void token_put(CxxToken *aToken);
122
123 CxxSearchContext *CxxSearchContext::_current = 0;
124 CxxSearchContext *CxxSearchContext::_free = 0;
125 size_t CxxSearchContext::actual_searches = 0;
126 size_t CxxSearchContext::advances[16] = { 0 };
127 size_t CxxSearchContext::max_search_depth = 0;
128 size_t CxxSearchContext::nested_searches = 0;
129 size_t CxxSearchContext::releases = 0;
130 size_t CxxSearchContext::search_advances;
131 size_t CxxSearchContext::unnested_searches;
132
133 //
134 //      Implements a binary search counter, performing the increment at the
135 //      _index of othe failed search.
136 //
137 bool CxxSearchContext::advance()
138 {
139         _advances++;
140         size_t i = _depth;
141         if (i <= 0)
142                 return false;
143         while (--i > _index)
144                 _status[i] = false;
145         while (true)
146         {
147                 if (!_status[i])
148                 {
149                         _status[i] = true;
150                         _index = 0;
151                         return true;
152                 }
153                 if (i <= 0)
154                         return false;
155                 _status[i--] = false;
156         }
157 }
158
159 void CxxSearchContext::initialise(size_t markIndex, bool enableType1)
160 {
161         _index = 0;
162         _depth = 0;
163         _mark = markIndex;
164     _enable_type1 = enableType1;
165         _line = line_number;
166         _advances = 0;
167 }
168
169 bool CxxSearchContext::is_template()
170 {
171         if (_index >= _depth)
172         {
173                 if (_depth >= _size)
174                 {
175                         ERRMSG("Binary search depth exceeded.");
176                         return false;
177                 }
178                 _status[_depth++] = false;
179                 if (_depth > max_search_depth)
180                         max_search_depth = _depth;
181         }
182         return _status[_index++] ? false : true;
183 }
184
185 //
186 //      Put this element onto listHead, returning element under this one.
187 //
188 CxxSearchContext *CxxSearchContext::queue(CxxSearchContext *& listHead)
189 {
190         CxxSearchContext *oldNext = _next;
191         _next = listHead;
192         listHead = this;
193         return oldNext;
194 }
195
196 //
197 //      Release the current search buffer.
198 //
199 void CxxSearchContext::release()
200 {
201         if (_current)
202         {
203                 releases++;
204                 _current->reset();
205                 _current = _current->queue(_free);
206         }
207 }
208
209 void CxxSearchContext::reset()
210 {
211         if (did_search())
212         {
213                 _advances++;
214                 actual_searches++;
215         }
216         if (_advances >= sizeof(advances)/sizeof(advances[0]))
217                 advances[sizeof(advances)/sizeof(advances[0])-1]++;
218         else
219                 advances[_advances]++;
220 }
221
222 void CxxSearchContext::start(YACC_MARK_TYPE anIndex, bool enableType1)
223 {
224         if (!_current)
225                 unnested_searches++;
226         else
227                 nested_searches++;
228         if (!_free)
229                 _current = new CxxSearchContext(_current);
230         else
231                 _free = _free->queue(_current);
232         _current->initialise(anIndex, enableType1);
233 }
234
235 static CxxToken angleToken('<');
236 static CxxToken colonToken(':');
237 static CxxToken hashToken('#');
238 static CxxToken plusToken('+');
239 static CxxToken minusToken('-');
240
241 void PARSE_SCOPE yyerror(const char *s)
242 {
243         if (!bang_depth && (tokenMarkDepth == 0))
244         {
245                 cout << s << endl;
246                 increment_error_count();
247         }
248         else
249         {
250                 if (show_marked)
251                         cout << "Marked " << s << endl;         
252                 marked_error_count++;
253         }
254 }
255
256 //
257 //      Get the next token for the parser, invoking yylex_token to get the next token from the lexer.
258 //      This routine gets renamed to buffered_yylex by a #define when using yacc so that the two purposes
259 //      above are split allowing lookahead buffering and primimimg to occur.
260 //
261 int PARSE_SCOPE yylex()
262 {
263         CxxToken *aToken = primed_tokens[0];
264         if (aToken)
265         {
266                 primed_tokens[0] = primed_tokens[1];
267                 primed_tokens[1] = primed_tokens[2];
268                 primed_tokens[2] = 0;
269         }
270         else if (tokenReadIndex < tokenWriteIndex)
271                 aToken = tokenBuffer[tokenReadIndex++];
272         else
273         {
274                 aToken = yylex_token();
275                 if (!aToken)
276                         return 0;
277                 if (tokenMarkDepth > 0)
278                         token_put(aToken);
279                 else
280                 {
281                         tokenWriteIndex = 0;
282                         tokenReadIndex = 0;
283                 }
284         }
285         yylval.token = aToken;
286         return aToken->value();
287 }
288
289 //
290 //      Advance the binary search of template attempts. Rewinds and forces true into the input sequence
291 //      to proceed with the search. Rewinds and forces false to terminate it. Also forces a # that may then
292 //      be used to initiate error propagation.
293 //
294 void advance_search()
295 {
296         CxxSearchContext::search_advances++;
297         remark(CxxSearchContext::current()->mark());
298         if (CxxSearchContext::current() && CxxSearchContext::current()->advance())
299         {
300                 primed_tokens[0] = &plusToken;
301                 primed_tokens[1] = 0;
302         }
303         else
304         {
305                 primed_tokens[0] = &minusToken;
306                 primed_tokens[1] = &hashToken;
307         }
308 }
309
310 //
311 //      Complete a search, releasing the search context object and popping a mark off the stack.
312 //
313 void end_search(CxxToken *aToken)
314 {
315         CxxSearchContext::release();
316         unmark(aToken);
317 }
318
319 //
320 //      Notch up an error and establish a good break point.
321 //
322 void increment_error_count()
323 {
324         error_count++;
325 }
326
327 //
328 //      Push a new marked context onto the stack, returning its identity for use by remark().
329 //      Any parser readahead is incorporated within the marked region.
330 //
331 YACC_MARK_TYPE mark()
332 {
333         if (primed_tokens[0])
334                 ERRMSG("Unexpected primed_tokens[0] in mark.");
335         YACC_MARK_TYPE markIndex = tokenReadIndex;
336         if (PARSE_DOT yychar != YYEMPTY)
337         {
338 //              if (primed_tokens[2])
339 //                      token_put(primed_tokens[2]);
340 //              if (primed_tokens[1])
341 //                      token_put(primed_tokens[1]);
342 //              if (primed_tokens[0])
343 //                      token_put(primed_tokens[0]);
344 //              if (!tokenMarkDepth)
345                 if (!tokenReadIndex && !tokenWriteIndex)
346                 {
347                         token_put(PARSE_DOT yylval.token);
348                         tokenReadIndex = 0;
349                 }
350                 else if (!tokenReadIndex)
351                         ERRMSG("Unexpected 0 read index in mark.");
352                 else if (tokenBuffer[--tokenReadIndex] != PARSE_DOT yylval.token)
353                         ERRMSG("Unexpected unget in mark.");
354                 markIndex = tokenReadIndex;
355                 yyclearin;
356                 primed_tokens[0] = 0;
357                 primed_tokens[1] = 0;
358         }
359         tokenMarkDepth++; 
360         bang_depth++;
361         return markIndex;
362 }
363
364 //
365 //      If it is appropriate to do type I function parameter parsing perform a mark and force a rrue token
366 //      into the input stream. Otherwise just force a false token in.
367 //
368 YACC_MARK_TYPE mark_type1()
369 {
370         if (!in_type1 && CxxSearchContext::current() && CxxSearchContext::current()->enable_type1())
371         {
372                 YACC_MARK_TYPE markIndex = mark();
373                 primed_tokens[0] = &plusToken;
374                 primed_tokens[1] = 0;
375                 in_type1 = true;
376         yyclearin; 
377                 return markIndex;
378         }
379         else
380         {
381                 primed_tokens[0] = &minusToken;
382                 primed_tokens[1] = PARSE_DOT yychar != YYEMPTY ? PARSE_DOT yylval.token : 0;
383         yyclearin; 
384                 return 0;                       // Never used.
385         }
386 }       
387
388 //
389 //      Push a bang context onto the error suppression stack, returning the context for restoration by pop_bang.
390 //
391 void pop_bang(YACC_BANG_TYPE bangValue)
392 {
393         bang_depth = bangValue;
394 }
395
396 //
397 //      Push a bang context onto the error suppression stack, returning the context for restoration by pop_bang.
398 //
399 YACC_BANG_TYPE push_bang()
400 {
401         return bang_depth++;
402 }
403
404 //
405 //      Reposition the input to restart at the position returned by a mark().
406 //
407 void remark(YACC_MARK_TYPE anIndex)
408 {
409         tokenReadIndex = anIndex;
410     yyclearin;
411 }
412
413 //
414 //      Reposition the input to restart at the position returned by a mark().
415 //
416 void remark_type1(YACC_MARK_TYPE anIndex)
417 {
418         remark(anIndex);
419         in_type1 = false;
420 }
421
422 //
423 //      Rewind the input stream back to anIndex and force a : prior to resuming input.
424 //
425 void rewind_colon(YACC_MARK_TYPE anIndex, const CxxToken *aToken)
426 {
427         remark(anIndex);
428         unmark();
429         primed_tokens[0] = &colonToken;
430         primed_tokens[1] = PARSE_DOT yylval.token;
431 }
432
433 //
434 //      Start a new binary search over the template/arithmetic alternative parses of a statement.
435 //      Marks the current position and saves it in a binary search context maintained on a private stack.
436 //
437 void start_search(bool enableType1)
438 {
439         bool type1Enabled = !CxxSearchContext::current() || CxxSearchContext::current()->enable_type1() ? true : false;
440         CxxSearchContext::start(mark(), enableType1 && type1Enabled ? true : false);
441 }
442
443 //
444 //      Determine whether the just parsed < should be interpreted as a template or arithmetic operator.
445 //      The implementation here intersacts with a binary search to traverse all possibilities in
446 //      multiple passes. The search proceeds by branch and bound presuming the template interpretation.
447 //      A true token is forced into the input stream to take the template interpretaion. A false token
448 //      otherwise.
449 //
450 //      An alternate implementation that keeps track of scopes may interact with semantic knowledge to make
451 //      the correct decision directly.
452 //
453 void template_test()
454 {
455         if (!CxxSearchContext::current() || CxxSearchContext::current()->is_template())
456         {
457                 primed_tokens[0] = &plusToken;
458                 primed_tokens[1] = 0;
459         }
460         else
461         {
462                 primed_tokens[0] = &minusToken;
463                 primed_tokens[1] = &angleToken;
464         }
465 }
466
467 void token_put(CxxToken *aToken)
468 {
469         if (!tokenBuffer || !tokenSize)
470                 tokenBuffer = new CxxToken *[tokenSize = 256];
471         else if (tokenWriteIndex >= tokenSize)
472         {
473                 CxxToken **oldTokenBuffer = tokenBuffer;
474                 size_t oldTokenSize = tokenSize;
475                 tokenBuffer = new CxxToken *[tokenSize *= 2];
476                 memcpy(tokenBuffer, oldTokenBuffer, oldTokenSize * sizeof(*oldTokenBuffer));
477                 delete[] oldTokenBuffer;
478         }
479         tokenBuffer[tokenWriteIndex++] = aToken;
480         tokenReadIndex = tokenWriteIndex;
481 }
482
483 //
484 //      Pop a marked context off the stack.
485 //
486 void unmark(const CxxToken *aToken)
487 {
488     if (bang_depth)
489         bang_depth--;
490     else
491         ERRMSG("BUG - should not unmark with 0 bang.");
492         if (tokenMarkDepth <= 0)
493                 ERRMSG("Unexpected unmark.");
494         else
495                 tokenMarkDepth--;
496 }