1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0
3
4#include "cppgenerator.h"
5
6#include "lalr.h"
7#include "recognizer.h"
8
9#include <QtCore/qbitarray.h>
10#include <QtCore/qtextstream.h>
11#include <QtCore/qfile.h>
12#include <QtCore/qmap.h>
13#include <QtCore/private/qconfig_p.h>
14
15#include <iterator>
16
17using namespace Qt::StringLiterals;
18
19namespace {
20
21void generateSeparator(int i, QTextStream &out)
22{
23 if (!(i % 10)) {
24 if (i)
25 out << ",";
26 out << Qt::endl << " ";
27 } else {
28 out << ", ";
29 }
30}
31
32void generateList(const QList<int> &list, QTextStream &out)
33{
34 for (int i = 0; i < list.size(); ++i) {
35 generateSeparator(i, out);
36
37 out << list[i];
38 }
39}
40
41}
42
43QString CppGenerator::copyrightHeader() const
44{
45 return
46 "// " QT_COPYRIGHT "\n"
47 "// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0\n"
48 "\n"_L1;
49}
50
51QString CppGenerator::privateCopyrightHeader() const
52{
53 return
54 "//\n"
55 "// W A R N I N G\n"
56 "// -------------\n"
57 "//\n"
58 "// This file is not part of the Qt API. It exists for the convenience\n"
59 "// of other Qt classes. This header file may change from version to\n"
60 "// version without notice, or even be removed.\n"
61 "//\n"
62 "// We mean it.\n"
63 "//\n"_L1;
64}
65
66QString CppGenerator::startIncludeGuard(const QString &fileName)
67{
68 const QString normalized(QString(fileName).replace(before: u'.', after: u'_').toUpper());
69
70 return QString::fromLatin1(ba: "#ifndef %1\n"
71 "#define %2\n").arg(args: normalized, args: normalized);
72}
73
74QString CppGenerator::endIncludeGuard(const QString &fileName)
75{
76 const QString normalized(QString(fileName).replace(before: u'.', after: u'_').toUpper());
77
78 return QString::fromLatin1(ba: "#endif // %1\n").arg(a: normalized);
79}
80
81void CppGenerator::operator () ()
82{
83 // action table...
84 state_count = static_cast<int>(aut.states.size());
85 terminal_count = static_cast<int>(grammar.terminals.size());
86 non_terminal_count = static_cast<int>(grammar.non_terminals.size());
87
88#define ACTION(i, j) table [(i) * terminal_count + (j)]
89#define GOTO(i, j) pgoto [(i) * non_terminal_count + (j)]
90
91 int *table = new int [state_count * terminal_count];
92 ::memset (s: table, c: 0, n: state_count * terminal_count * sizeof (int));
93
94 int *pgoto = new int [state_count * non_terminal_count];
95 ::memset (s: pgoto, c: 0, n: state_count * non_terminal_count * sizeof (int));
96
97 accept_state = -1;
98 int shift_reduce_conflict_count = 0;
99 int reduce_reduce_conflict_count = 0;
100
101 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state)
102 {
103 int q = aut.id (state);
104
105 for (Bundle::iterator a = state->bundle.begin (); a != state->bundle.end (); ++a)
106 {
107 int symbol = aut.id (name: a.key ());
108 int r = aut.id (state: a.value ());
109
110 Q_ASSERT (r < state_count);
111
112 if (grammar.isNonTerminal (name: a.key ()))
113 {
114 Q_ASSERT(symbol >= terminal_count && symbol < static_cast<int>(grammar.names.size()));
115 GOTO (q, symbol - terminal_count) = r;
116 }
117
118 else
119 ACTION (q, symbol) = r;
120 }
121
122 for (ItemPointer item = state->closure.begin (); item != state->closure.end (); ++item)
123 {
124 if (item->dot != item->end_rhs ())
125 continue;
126
127 int r = aut.id (rule: item->rule);
128
129 const NameSet lookaheads = aut.lookaheads.value (key: item);
130
131 if (item->rule == grammar.goal)
132 accept_state = q;
133
134 for (const Name &s : lookaheads)
135 {
136 int &u = ACTION (q, aut.id (s));
137
138 if (u == 0)
139 u = - r;
140
141 else if (u < 0)
142 {
143 if (verbose)
144 qout() << "*** Warning. Found a reduce/reduce conflict in state " << q << " on token ``" << s << "'' between rule "
145 << r << " and " << -u << Qt::endl;
146
147 ++reduce_reduce_conflict_count;
148
149 u = qMax (a: u, b: -r);
150
151 if (verbose)
152 qout() << "\tresolved using rule " << -u << Qt::endl;
153 }
154
155 else if (u > 0)
156 {
157 if (item->rule->prec != grammar.names.end() && grammar.token_info.contains (key: s))
158 {
159 Grammar::TokenInfo info_r = grammar.token_info.value (key: item->rule->prec);
160 Grammar::TokenInfo info_s = grammar.token_info.value (key: s);
161
162 if (info_r.prec > info_s.prec)
163 u = -r;
164 else if (info_r.prec == info_s.prec)
165 {
166 switch (info_r.assoc) {
167 case Grammar::Left:
168 u = -r;
169 break;
170 case Grammar::Right:
171 // shift... nothing to do
172 break;
173 case Grammar::NonAssoc:
174 u = 0;
175 break;
176 } // switch
177 }
178 }
179
180 else
181 {
182 ++shift_reduce_conflict_count;
183
184 if (verbose)
185 qout() << "*** Warning. Found a shift/reduce conflict in state " << q << " on token ``" << s << "'' with rule " << r << Qt::endl;
186 }
187 }
188 }
189 }
190 }
191
192 if (shift_reduce_conflict_count || reduce_reduce_conflict_count)
193 {
194 if (shift_reduce_conflict_count != grammar.expected_shift_reduce
195 || reduce_reduce_conflict_count != grammar.expected_reduce_reduce)
196 {
197 qerr() << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << Qt::endl;
198 if (warnings_are_errors)
199 {
200 qerr() << "qlalr: error: warning occurred, treating as error due to "
201 "--exit-on-warn." << Qt::endl;
202 exit(status: 2);
203 }
204 }
205
206 if (verbose)
207 qout() << Qt::endl << "*** Conflicts: " << shift_reduce_conflict_count << " shift/reduce, " << reduce_reduce_conflict_count << " reduce/reduce" << Qt::endl
208 << Qt::endl;
209 }
210
211 QBitArray used_rules{static_cast<int>(grammar.rules.size())};
212
213 int q = 0;
214 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
215 {
216 for (int j = 0; j < terminal_count; ++j)
217 {
218 int &u = ACTION (q, j);
219
220 if (u < 0)
221 used_rules.setBit (-u - 1);
222 }
223 }
224
225 auto rule = grammar.rules.begin();
226 for (int i = 0; i < used_rules.size(); ++i, ++rule)
227 {
228 if (! used_rules.testBit (i))
229 {
230 if (rule != grammar.goal)
231 {
232 qerr() << "*** Warning: Rule ``" << *rule << "'' is useless!" << Qt::endl;
233 if (warnings_are_errors)
234 {
235 qerr() << "qlalr: error: warning occurred, treating as error due to "
236 "--exit-on-warn." << Qt::endl;
237 exit(status: 2);
238 }
239 }
240 }
241 }
242
243 q = 0;
244 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q)
245 {
246 for (int j = 0; j < terminal_count; ++j)
247 {
248 int &u = ACTION (q, j);
249
250 if (u >= 0)
251 continue;
252
253 RulePointer rule = std::next(x: grammar.rules.begin(), n: - u - 1);
254
255 if (state->defaultReduce == rule)
256 u = 0;
257 }
258 }
259
260 // ... compress the goto table
261 defgoto.resize (size: non_terminal_count);
262 for (int j = 0; j < non_terminal_count; ++j)
263 {
264 count.fill (t: 0, newSize: state_count);
265
266 int &mx = defgoto [j];
267
268 for (int i = 0; i < state_count; ++i)
269 {
270 int r = GOTO (i, j);
271
272 if (! r)
273 continue;
274
275 ++count [r];
276
277 if (count [r] > count [mx])
278 mx = r;
279 }
280 }
281
282 for (int i = 0; i < state_count; ++i)
283 {
284 for (int j = 0; j < non_terminal_count; ++j)
285 {
286 int &r = GOTO (i, j);
287
288 if (r == defgoto [j])
289 r = 0;
290 }
291 }
292
293 compressed_action (table, state_count, terminal_count);
294 compressed_goto (pgoto, state_count, non_terminal_count);
295
296 delete[] table;
297 table = nullptr;
298
299 delete[] pgoto;
300 pgoto = nullptr;
301
302#undef ACTION
303#undef GOTO
304
305 if (! grammar.merged_output.isEmpty())
306 {
307 QFile f(grammar.merged_output);
308 if (! f.open (flags: QFile::WriteOnly))
309 {
310 fprintf (stderr, format: "*** cannot create %s\n", qPrintable(grammar.merged_output));
311 return;
312 }
313
314 QTextStream out (&f);
315
316 // copyright headers must come first, otherwise the headers tests will fail
317 if (copyright)
318 {
319 out << copyrightHeader()
320 << privateCopyrightHeader()
321 << Qt::endl;
322 }
323
324 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
325
326 out << startIncludeGuard(fileName: grammar.merged_output) << Qt::endl;
327
328 if (copyright) {
329 out << "#if defined(ERROR)" << Qt::endl
330 << "# undef ERROR" << Qt::endl
331 << "#endif" << Qt::endl << Qt::endl;
332 }
333
334 generateDecl (out);
335 generateImpl (out);
336 out << p.decls();
337 out << p.impls();
338 out << Qt::endl;
339
340 out << endIncludeGuard(fileName: grammar.merged_output) << Qt::endl;
341
342 return;
343 }
344
345 // default behaviour
346 QString declFileName = grammar.table_name.toLower () + "_p.h"_L1;
347 QString bitsFileName = grammar.table_name.toLower () + ".cpp"_L1;
348
349 { // decls...
350 QFile f (declFileName);
351 f.open (flags: QFile::WriteOnly);
352 QTextStream out (&f);
353
354 QString prot = declFileName.toUpper ().replace (before: QLatin1Char ('.'), after: QLatin1Char ('_'));
355
356 // copyright headers must come first, otherwise the headers tests will fail
357 if (copyright)
358 {
359 out << copyrightHeader()
360 << privateCopyrightHeader()
361 << Qt::endl;
362 }
363
364 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
365
366 out << "#ifndef " << prot << Qt::endl
367 << "#define " << prot << Qt::endl
368 << Qt::endl;
369
370 if (copyright) {
371 out << "#include <QtCore/qglobal.h>" << Qt::endl << Qt::endl;
372 out << "QT_BEGIN_NAMESPACE" << Qt::endl << Qt::endl;
373 }
374 generateDecl (out);
375 if (copyright)
376 out << "QT_END_NAMESPACE" << Qt::endl;
377
378 out << "#endif // " << prot << Qt::endl << Qt::endl;
379 } // end decls
380
381 { // bits...
382 QFile f (bitsFileName);
383 f.open (flags: QFile::WriteOnly);
384 QTextStream out (&f);
385
386 // copyright headers must come first, otherwise the headers tests will fail
387 if (copyright)
388 out << copyrightHeader();
389
390 out << "// This file was generated by qlalr - DO NOT EDIT!\n";
391
392 out << "#include \"" << declFileName << "\"" << Qt::endl << Qt::endl;
393 if (copyright)
394 out << "QT_BEGIN_NAMESPACE" << Qt::endl << Qt::endl;
395 generateImpl(out);
396 if (copyright)
397 out << "QT_END_NAMESPACE" << Qt::endl;
398
399 } // end bits
400
401 if (! grammar.decl_file_name.isEmpty ())
402 {
403 QFile f (grammar.decl_file_name);
404 f.open (flags: QFile::WriteOnly);
405 QTextStream out (&f);
406 out << p.decls();
407 }
408
409 if (! grammar.impl_file_name.isEmpty ())
410 {
411 QFile f (grammar.impl_file_name);
412 f.open (flags: QFile::WriteOnly);
413 QTextStream out (&f);
414 out << p.impls();
415 }
416}
417
418QString CppGenerator::debugInfoProt() const
419{
420 QString prot = "QLALR_NO_"_L1;
421 prot += grammar.table_name.toUpper();
422 prot += "_DEBUG_INFO"_L1;
423 return prot;
424}
425
426void CppGenerator::generateDecl (QTextStream &out)
427{
428 out << "class " << grammar.table_name << Qt::endl
429 << "{" << Qt::endl
430 << "public:" << Qt::endl
431 << " enum VariousConstants {" << Qt::endl;
432
433 for (const Name &t : std::as_const(t&: grammar.terminals))
434 {
435 QString name = *t;
436 int value = std::distance (first: grammar.names.begin (), last: t);
437
438 if (name == "$end"_L1)
439 name = "EOF_SYMBOL"_L1;
440
441 else if (name == "$accept"_L1)
442 name = "ACCEPT_SYMBOL"_L1;
443
444 else
445 name.prepend (s: grammar.token_prefix);
446
447 out << " " << name << " = " << value << "," << Qt::endl;
448 }
449
450 out << Qt::endl
451 << " ACCEPT_STATE = " << accept_state << "," << Qt::endl
452 << " RULE_COUNT = " << grammar.rules.size () << "," << Qt::endl
453 << " STATE_COUNT = " << state_count << "," << Qt::endl
454 << " TERMINAL_COUNT = " << terminal_count << "," << Qt::endl
455 << " NON_TERMINAL_COUNT = " << non_terminal_count << "," << Qt::endl
456 << Qt::endl
457 << " GOTO_INDEX_OFFSET = " << compressed_action.index.size () << "," << Qt::endl
458 << " GOTO_INFO_OFFSET = " << compressed_action.info.size () << "," << Qt::endl
459 << " GOTO_CHECK_OFFSET = " << compressed_action.check.size () << Qt::endl
460 << " };" << Qt::endl
461 << Qt::endl
462 << " static const char *const spell[];" << Qt::endl
463 << " static const short lhs[];" << Qt::endl
464 << " static const short rhs[];" << Qt::endl;
465
466 if (debug_info)
467 {
468 QString prot = debugInfoProt();
469
470 out << Qt::endl << "#ifndef " << prot << Qt::endl
471 << " static const int rule_index[];" << Qt::endl
472 << " static const int rule_info[];" << Qt::endl
473 << "#endif // " << prot << Qt::endl << Qt::endl;
474 }
475
476 out << " static const short goto_default[];" << Qt::endl
477 << " static const short action_default[];" << Qt::endl
478 << " static const short action_index[];" << Qt::endl
479 << " static const short action_info[];" << Qt::endl
480 << " static const short action_check[];" << Qt::endl
481 << Qt::endl
482 << " static inline int nt_action (int state, int nt)" << Qt::endl
483 << " {" << Qt::endl
484 << " const int yyn = action_index [GOTO_INDEX_OFFSET + state] + nt;" << Qt::endl
485 << " if (yyn < 0 || action_check [GOTO_CHECK_OFFSET + yyn] != nt)" << Qt::endl
486 << " return goto_default [nt];" << Qt::endl
487 << Qt::endl
488 << " return action_info [GOTO_INFO_OFFSET + yyn];" << Qt::endl
489 << " }" << Qt::endl
490 << Qt::endl
491 << " static inline int t_action (int state, int token)" << Qt::endl
492 << " {" << Qt::endl
493 << " const int yyn = action_index [state] + token;" << Qt::endl
494 << Qt::endl
495 << " if (yyn < 0 || action_check [yyn] != token)" << Qt::endl
496 << " return - action_default [state];" << Qt::endl
497 << Qt::endl
498 << " return action_info [yyn];" << Qt::endl
499 << " }" << Qt::endl
500 << "};" << Qt::endl
501 << Qt::endl
502 << Qt::endl;
503}
504
505void CppGenerator::generateImpl (QTextStream &out)
506{
507 int idx = 0;
508
509 out << "const char *const " << grammar.table_name << "::spell [] = {";
510 idx = 0;
511
512 QMap<Name, int> name_ids;
513 bool first_nt = true;
514
515 for (Name t = grammar.names.begin (); t != grammar.names.end (); ++t, ++idx)
516 {
517 bool terminal = grammar.isTerminal (name: t);
518
519 if (! (debug_info || terminal))
520 break;
521
522 name_ids.insert (key: t, value: idx);
523
524 generateSeparator(i: idx, out);
525
526 if (terminal)
527 {
528 QString spell = grammar.spells.value (key: t);
529
530 if (spell.isEmpty ())
531 out << "0";
532 else
533 out << "\"" << spell << "\"";
534 }
535 else
536 {
537 if (first_nt)
538 {
539 first_nt = false;
540 QString prot = debugInfoProt();
541 out << Qt::endl << "#ifndef " << prot << Qt::endl;
542 }
543 out << "\"" << *t << "\"";
544 }
545 }
546
547 if (debug_info)
548 out << Qt::endl << "#endif // " << debugInfoProt() << Qt::endl;
549
550 out << Qt::endl << "};" << Qt::endl << Qt::endl;
551
552 out << "const short " << grammar.table_name << "::lhs [] = {";
553 idx = 0;
554 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
555 {
556 generateSeparator(i: idx, out);
557
558 out << aut.id (name: rule->lhs);
559 }
560 out << Qt::endl << "};" << Qt::endl << Qt::endl;
561
562 out << "const short " << grammar.table_name << "::rhs [] = {";
563 idx = 0;
564 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
565 {
566 generateSeparator(i: idx, out);
567
568 out << rule->rhs.size ();
569 }
570 out << Qt::endl << "};" << Qt::endl << Qt::endl;
571
572 if (debug_info)
573 {
574 QString prot = debugInfoProt();
575
576 out << Qt::endl << "#ifndef " << prot << Qt::endl;
577 out << "const int " << grammar.table_name << "::rule_info [] = {";
578 idx = 0;
579 for (auto rule = grammar.rules.cbegin (); rule != grammar.rules.cend (); ++rule, ++idx)
580 {
581 generateSeparator(i: idx, out);
582
583 out << name_ids.value(key: rule->lhs);
584
585 for (const Name &n : rule->rhs)
586 out << ", " << name_ids.value (key: n);
587 }
588 out << Qt::endl << "};" << Qt::endl << Qt::endl;
589
590 out << "const int " << grammar.table_name << "::rule_index [] = {";
591 idx = 0;
592 size_t offset = 0;
593 for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx)
594 {
595 generateSeparator(i: idx, out);
596
597 out << offset;
598 offset += rule->rhs.size () + 1;
599 }
600 out << Qt::endl << "};" << Qt::endl
601 << "#endif // " << prot << Qt::endl << Qt::endl;
602 }
603
604 out << "const short " << grammar.table_name << "::action_default [] = {";
605 idx = 0;
606 for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++idx)
607 {
608 generateSeparator(i: idx, out);
609
610 if (state->defaultReduce != grammar.rules.end ())
611 out << aut.id (rule: state->defaultReduce);
612 else
613 out << "0";
614 }
615 out << Qt::endl << "};" << Qt::endl << Qt::endl;
616
617 out << "const short " << grammar.table_name << "::goto_default [] = {";
618 generateList(list: defgoto, out);
619 out << Qt::endl << "};" << Qt::endl << Qt::endl;
620
621 out << "const short " << grammar.table_name << "::action_index [] = {";
622 generateList(list: compressed_action.index, out);
623 out << "," << Qt::endl;
624 generateList(list: compressed_goto.index, out);
625 out << Qt::endl << "};" << Qt::endl << Qt::endl;
626
627 out << "const short " << grammar.table_name << "::action_info [] = {";
628 generateList(list: compressed_action.info, out);
629 out << "," << Qt::endl;
630 generateList(list: compressed_goto.info, out);
631 out << Qt::endl << "};" << Qt::endl << Qt::endl;
632
633 out << "const short " << grammar.table_name << "::action_check [] = {";
634 generateList(list: compressed_action.check, out);
635 out << "," << Qt::endl;
636 generateList(list: compressed_goto.check, out);
637 out << Qt::endl << "};" << Qt::endl << Qt::endl;
638}
639

source code of qtbase/src/tools/qlalr/cppgenerator.cpp