source: src/ResolvExpr/CurrentObject.cc@ 0b0a285

Last change on this file since 0b0a285 was 8f557161, checked in by Michael Brooks <mlbrooks@…>, 2 years ago

Clarify and fix accuracy in eval public API, on reporting "unable to evaluate."

While the eval internals always used the flag pair valid and cfavalid almost correctly, the public interface exposed the outcome as a single flag, and the various interpretations of this flag were a mess.

Old cfacc treated sizeof(whatever) in some contexts as "known to be zero," which is wrong.
The generally correct answer, which new cfacc now uses is, "unknown now, but GCC will see it as a fine constant."
New tests/eval.cfa captures this fact: is runnable and would fail on old cfacc; it passes with new cfacc.
  • Property mode set to 100644
File size: 39.8 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// CurrentObject.h --
8//
9// Author : Rob Schluntz
10// Created On : Tue Jun 13 15:28:32 2017
11// Last Modified By : Andrew Beach
12// Last Modified On : Mon Apr 10 9:40:00 2023
13// Update Count : 18
14//
15
16#include <stddef.h> // for size_t
17#include <cassert> // for assertf, assert, safe_dynamic_...
18#include <deque>
19#include <iostream> // for ostream, operator<<, basic_ost...
20#include <stack> // for stack
21#include <string> // for string, operator<<, allocator
22
23#include "AST/Copy.hpp" // for shallowCopy
24#include "AST/Expr.hpp" // for InitAlternative
25#include "AST/GenericSubstitution.hpp" // for genericSubstitution
26#include "AST/Init.hpp" // for Designation
27#include "AST/Node.hpp" // for readonly
28#include "AST/Print.hpp" // for readonly
29#include "AST/Type.hpp"
30#include "Common/Eval.h" // for eval
31#include "Common/Indenter.h" // for Indenter, operator<<
32#include "Common/SemanticError.h" // for SemanticError
33#include "Common/utility.h" // for toString
34#include "CurrentObject.h"
35#include "SynTree/Constant.h" // for Constant
36#include "SynTree/Declaration.h" // for ObjectDecl, Declaration, Struc...
37#include "SynTree/Expression.h" // for InitAlternative, VariableExpr
38#include "SynTree/Initializer.h" // for Designation, operator<<
39#include "SynTree/Type.h" // for Type, StructInstType, UnionIns...
40#include "SynTree/TypeSubstitution.h" // for TypeSubstitution
41
42#if 0
43#define PRINT(x) x
44#else
45#define PRINT(x)
46#endif
47
48namespace ResolvExpr {
49 template< typename AggrInst >
50 TypeSubstitution makeGenericSubstitution( AggrInst * inst ) {
51 assert( inst );
52 assert( inst->get_baseParameters() );
53 std::list< TypeDecl * > baseParams = *inst->get_baseParameters();
54 std::list< Expression * > typeSubs = inst->get_parameters();
55 TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
56 return subs;
57 }
58
59 TypeSubstitution makeGenericSubstitution( Type * type ) {
60 if ( StructInstType * inst = dynamic_cast< StructInstType * >( type ) ) {
61 return makeGenericSubstitution( inst );
62 } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( type ) ) {
63 return makeGenericSubstitution( inst );
64 } else {
65 return TypeSubstitution();
66 }
67 }
68
69 class MemberIterator {
70 public:
71 virtual ~MemberIterator() {}
72
73 /// walks the current object using the given designators as a guide
74 virtual void setPosition( std::list< Expression * > & designators ) = 0;
75
76 /// retrieve the list of possible Type/Designation pairs for the current position in the currect object
77 virtual std::list<InitAlternative> operator*() const = 0;
78
79 /// true if the iterator is not currently at the end
80 virtual operator bool() const = 0;
81
82 /// moves the iterator by one member in the current object
83 virtual MemberIterator & bigStep() = 0;
84
85 /// moves the iterator by one member in the current subobject
86 virtual MemberIterator & smallStep() = 0;
87
88 /// the type of the current object
89 virtual Type * getType() = 0;
90
91 /// the type of the current subobject
92 virtual Type * getNext() = 0;
93
94 /// printing for debug
95 virtual void print( std::ostream & out, Indenter indent ) const = 0;
96
97 /// helper for operator*; aggregates must add designator to each init alternative, but
98 /// adding designators in operator* creates duplicates.
99 virtual std::list<InitAlternative> first() const = 0; // should be protected
100 };
101
102 std::ostream & operator<<(std::ostream & out, const MemberIterator & it) {
103 Indenter indenter;
104 it.print( out, indenter );
105 return out;
106 }
107
108 /// create a new MemberIterator that traverses a type correctly
109 MemberIterator * createMemberIterator( Type * type );
110
111 /// iterates "other" types, e.g. basic types, pointer types, etc. which do not change at list initializer entry
112 class SimpleIterator : public MemberIterator {
113 public:
114 SimpleIterator( Type * type ) : type( type ) {}
115
116 virtual void setPosition( std::list< Expression * > & designators ) {
117 assertf( designators.empty(), "simple iterator given non-empty designator..." ); // xxx - might be semantic error
118 }
119
120 virtual std::list<InitAlternative> operator*() const { return first(); }
121 virtual operator bool() const { return type; }
122
123 // big step is the same as small step
124 virtual MemberIterator & bigStep() { return smallStep(); }
125 virtual MemberIterator & smallStep() {
126 type = nullptr; // type is nullified on increment since SimpleIterators do not have members
127 return *this;
128 }
129
130 virtual void print( std::ostream & out, __attribute__((unused)) Indenter indent ) const {
131 out << "SimpleIterator(" << type << ")";
132 }
133
134 virtual Type * getType() { return type; }
135 virtual Type * getNext() { return type; }
136
137 protected:
138 virtual std::list<InitAlternative> first() const {
139 if ( type ) return std::list<InitAlternative>{ { type->clone(), new Designation( {} ) } };
140 else return std::list<InitAlternative>{};
141 }
142 private:
143 Type * type = nullptr;
144 };
145
146 class ArrayIterator : public MemberIterator {
147 public:
148 ArrayIterator( ArrayType * at ) : array( at ) {
149 PRINT( std::cerr << "Creating array iterator: " << at << std::endl; )
150 base = at->base;
151 memberIter = createMemberIterator( base );
152 if ( at->isVarLen ) SemanticError( at, "VLA initialization does not support @=: " );
153 setSize( at->dimension );
154 }
155
156 ~ArrayIterator() {
157 delete memberIter;
158 }
159
160 private:
161 void setSize( Expression * expr ) {
162 auto res = eval( expr );
163 if (res.second) {
164 size = res.first;
165 } else {
166 SemanticError( expr->location, toString("Array designator must be a constant expression: ", expr) );
167 }
168 }
169
170 public:
171 void setPosition( Expression * expr ) {
172 // need to permit integer-constant-expressions, including: integer constants, enumeration constants, character constants, sizeof expressions, _Alignof expressions, cast expressions
173 auto arg = eval( expr );
174 index = arg.first;
175 return;
176
177 // if ( ConstantExpr * constExpr = dynamic_cast< ConstantExpr * >( expr ) ) {
178 // try {
179 // index = constExpr->intValue();
180 // } catch( SemanticErrorException & ) {
181 // SemanticError( expr, "Constant expression of non-integral type in array designator: " );
182 // }
183 // } else if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
184 // setPosition( castExpr->get_arg() );
185 // } else if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( expr ) ) {
186 // EnumInstType * inst = dynamic_cast<EnumInstType *>( varExpr->get_result() );
187 // assertf( inst, "ArrayIterator given variable that isn't an enum constant : %s", toString( expr ).c_str() );
188 // long long int value;
189 // if ( inst->baseEnum->valueOf( varExpr->var, value ) ) {
190 // index = value;
191 // }
192 // } else if ( dynamic_cast< SizeofExpr * >( expr ) || dynamic_cast< AlignofExpr * >( expr ) ) {
193 // index = 0; // xxx - get actual sizeof/alignof value?
194 // } else {
195 // assertf( false, "4 bad designator given to ArrayIterator: %s", toString( expr ).c_str() );
196 // }
197 }
198
199 virtual void setPosition( std::list< Expression * > & designators ) {
200 if ( ! designators.empty() ) {
201 setPosition( designators.front() );
202 designators.pop_front();
203 memberIter->setPosition( designators );
204 }
205 }
206
207 virtual std::list<InitAlternative> operator*() const {
208 return first();
209 }
210
211 virtual operator bool() const { return index < size; }
212
213 virtual MemberIterator & bigStep() {
214 PRINT( std::cerr << "bigStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
215 ++index;
216 delete memberIter;
217 if ( index < size ) memberIter = createMemberIterator( base );
218 else memberIter = nullptr;
219 return *this;
220 }
221
222 virtual MemberIterator & smallStep() {
223 PRINT( std::cerr << "smallStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
224 if ( memberIter ) {
225 PRINT( std::cerr << "has member iter: " << *memberIter << std::endl; )
226 memberIter->smallStep();
227 if ( *memberIter ) {
228 PRINT( std::cerr << "has valid member iter" << std::endl; )
229 return *this;
230 }
231 }
232 return bigStep();
233 }
234
235 virtual Type * getType() { return array; }
236 virtual Type * getNext() { return base; }
237
238 virtual std::list<InitAlternative> first() const {
239 PRINT( std::cerr << "first in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
240 if ( memberIter && *memberIter ) {
241 std::list<InitAlternative> ret = memberIter->first();
242 for ( InitAlternative & alt : ret ) {
243 alt.designation->get_designators().push_front( new ConstantExpr( Constant::from_ulong( index ) ) );
244 }
245 return ret;
246 }
247 return std::list<InitAlternative>();
248 }
249
250 virtual void print( std::ostream & out, Indenter indent ) const {
251 out << "ArrayIterator(Array of " << base << ")";
252 if ( memberIter ) {
253 Indenter childIndent = indent+1;
254 out << std::endl << childIndent;
255 memberIter->print( out, childIndent );
256 }
257 }
258
259 private:
260 ArrayType * array = nullptr;
261 Type * base = nullptr;
262 size_t index = 0;
263 size_t size = 0;
264 MemberIterator * memberIter = nullptr;
265 };
266
267 class AggregateIterator : public MemberIterator {
268 public:
269 typedef std::list<Declaration *> MemberList;
270 typedef MemberList::const_iterator iterator;
271 std::string kind = ""; // for debug
272 std::string name;
273 Type * inst = nullptr;
274 const MemberList & members;
275 iterator curMember;
276 bool atbegin = true; // false at first {small,big}Step -- this aggr type is only added to the possibilities at the beginning
277 Type * curType = nullptr;
278 MemberIterator * memberIter = nullptr;
279 mutable TypeSubstitution sub;
280
281 AggregateIterator( const std::string & kind, const std::string & name, Type * inst, const MemberList & members ) : kind( kind ), name( name ), inst( inst ), members( members ), curMember( members.begin() ), sub( makeGenericSubstitution( inst ) ) {
282 PRINT( std::cerr << "Creating " << kind << "(" << name << ")"; )
283 init();
284 }
285
286 virtual ~AggregateIterator() {
287 delete memberIter;
288 }
289
290 bool init() {
291 PRINT( std::cerr << "--init()--" << members.size() << std::endl; )
292 if ( curMember != members.end() ) {
293 if ( ObjectDecl * field = dynamic_cast< ObjectDecl * >( *curMember ) ) {
294 PRINT( std::cerr << "incremented to field: " << field << std::endl; )
295 curType = field->get_type();
296 memberIter = createMemberIterator( curType );
297 return true;
298 }
299 }
300 return false;
301 }
302
303 virtual std::list<InitAlternative> operator*() const {
304 if (memberIter && *memberIter) {
305 std::list<InitAlternative> ret = memberIter->first();
306 PRINT( std::cerr << "sub: " << sub << std::endl; )
307 for ( InitAlternative & alt : ret ) {
308 PRINT( std::cerr << "iterating and adding designators" << std::endl; )
309 alt.designation->get_designators().push_front( new VariableExpr( strict_dynamic_cast< ObjectDecl * >( *curMember ) ) );
310 // need to substitute for generic types, so that casts are to concrete types
311 PRINT( std::cerr << " type is: " << alt.type; )
312 sub.apply( alt.type ); // also apply to designation??
313 PRINT( std::cerr << " ==> " << alt.type << std::endl; )
314 }
315 return ret;
316 }
317 return std::list<InitAlternative>();
318 }
319
320 virtual void setPosition( std::list< Expression * > & designators ) {
321 if ( ! designators.empty() ) {
322 if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( designators.front() ) ) {
323 for ( curMember = members.begin(); curMember != members.end(); ++curMember ) {
324 if ( *curMember == varExpr->get_var() ) {
325 designators.pop_front();
326 delete memberIter;
327 memberIter = createMemberIterator( varExpr->get_result() );
328 curType = varExpr->get_result();
329 atbegin = curMember == members.begin() && designators.empty(); // xxx - is this the right condition for atbegin??
330 memberIter->setPosition( designators );
331 return;
332 } // if
333 } // for
334 assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
335 } else {
336 assertf( false, "3 bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() );
337 } // if
338 } // if
339 }
340
341 virtual MemberIterator & smallStep() {
342 PRINT( std::cerr << "smallStep in " << kind << std::endl; )
343 atbegin = false;
344 if ( memberIter ) {
345 PRINT( std::cerr << "has member iter, incrementing..." << std::endl; )
346 memberIter->smallStep();
347 if ( *memberIter ) {
348 PRINT( std::cerr << "success!" << std::endl; )
349 return *this;
350 }
351 }
352 return bigStep();
353 }
354
355 virtual Type * getType() { return inst; }
356 virtual Type * getNext() {
357 if ( memberIter && *memberIter ) return memberIter->getType(); // xxx - ??? recursive call???
358 return nullptr;
359 }
360
361 virtual std::list<InitAlternative> first() const {
362 std::list<InitAlternative> ret;
363 PRINT( std::cerr << "first " << kind << std::endl; )
364 if ( memberIter && *memberIter ) { // might not need *memberIter??
365 PRINT( std::cerr << "adding children" << std::endl; )
366 ret = memberIter->first();
367 for ( InitAlternative & alt : ret ) {
368 PRINT( std::cerr << "iterating and adding designators" << std::endl; )
369 alt.designation->get_designators().push_front( new VariableExpr( strict_dynamic_cast< ObjectDecl * >( *curMember ) ) );
370 }
371 }
372 if ( atbegin ) {
373 // xxx - what about case of empty struct??
374 // only add self if at the very beginning of the structure
375 PRINT( std::cerr << "adding self" << std::endl; )
376 ret.push_front( { inst->clone(), new Designation( {} ) } );
377 }
378 return ret;
379 }
380
381 virtual void print( std::ostream & out, Indenter indent ) const {
382 out << kind << "(" << name << ")";
383 if ( memberIter ) {
384 Indenter childIndent = indent+1;
385 out << std::endl << childIndent;
386 memberIter->print( out, childIndent );
387 }
388 }
389 };
390
391 class UnionIterator : public AggregateIterator {
392 public:
393 UnionIterator( UnionInstType * inst ) : AggregateIterator( "UnionIterator", inst->get_name(), inst, inst->get_baseUnion()->get_members() ) {}
394
395 virtual operator bool() const { return (memberIter && *memberIter); }
396 virtual MemberIterator & bigStep() {
397 // unions only initialize one member
398 PRINT( std::cerr << "bigStep in " << kind << std::endl; )
399 atbegin = false;
400 delete memberIter;
401 memberIter = nullptr;
402 curType = nullptr;
403 curMember = members.end();
404 return *this;
405 }
406 };
407
408 class StructIterator : public AggregateIterator {
409 public:
410 StructIterator( StructInstType * inst ) : AggregateIterator( "StructIterator", inst->get_name(), inst, inst->get_baseStruct()->get_members() ) {}
411
412 virtual operator bool() const { return curMember != members.end() || (memberIter && *memberIter); }
413
414 virtual MemberIterator & bigStep() {
415 PRINT( std::cerr << "bigStep in " << kind << std::endl; )
416 atbegin = false;
417 delete memberIter;
418 memberIter = nullptr;
419 curType = nullptr;
420 for ( ; curMember != members.end(); ) {
421 ++curMember;
422 if ( init() ) {
423 return *this;
424 }
425 }
426 return *this;
427 }
428 };
429
430 class TupleIterator : public AggregateIterator {
431 public:
432 TupleIterator( TupleType * inst ) : AggregateIterator( "TupleIterator", toString("Tuple", inst->size()), inst, inst->get_members() ) {}
433
434 virtual operator bool() const { return curMember != members.end() || (memberIter && *memberIter); }
435
436 virtual MemberIterator & bigStep() {
437 PRINT( std::cerr << "bigStep in " << kind << std::endl; )
438 atbegin = false;
439 delete memberIter;
440 memberIter = nullptr;
441 curType = nullptr;
442 for ( ; curMember != members.end(); ) {
443 ++curMember;
444 if ( init() ) {
445 return *this;
446 }
447 }
448 return *this;
449 }
450 };
451
452 MemberIterator * createMemberIterator( Type * type ) {
453 if ( ReferenceToType * aggr = dynamic_cast< ReferenceToType * >( type ) ) {
454 if ( StructInstType * sit = dynamic_cast< StructInstType * >( aggr ) ) {
455 return new StructIterator( sit );
456 } else if ( UnionInstType * uit = dynamic_cast< UnionInstType * >( aggr ) ) {
457 return new UnionIterator( uit );
458 } else {
459 assertf( dynamic_cast< EnumInstType * >( type ) || dynamic_cast< TypeInstType * >( type ), "Encountered unhandled ReferenceToType in createMemberIterator: %s", toString( type ).c_str() );
460 return new SimpleIterator( type );
461 }
462 } else if ( ArrayType * at = dynamic_cast< ArrayType * >( type ) ) {
463 return new ArrayIterator( at );
464 } else if ( TupleType * tt = dynamic_cast< TupleType * >( type ) ) {
465 return new TupleIterator( tt );
466 } else {
467 return new SimpleIterator( type );
468 }
469 }
470
471 CurrentObject::CurrentObject() {}
472 CurrentObject::CurrentObject( Type * type ) {
473 objStack.push( new SimpleIterator( type ) );
474 }
475
476
477 void CurrentObject::setNext( Designation * designation ) {
478 assertf( ! objStack.empty(), "obj stack empty in setNext" );
479 PRINT( std::cerr << "____setNext" << designation << std::endl; )
480 objStack.top()->setPosition( designation->get_designators() );
481 }
482
483 Designation * CurrentObject::findNext( Designation * designation ) {
484 typedef std::list< Expression * > DesignatorChain;
485 PRINT( std::cerr << "___findNext" << std::endl; )
486 // find all the d's
487 std::list<DesignatorChain> desigAlts{ { } }, newDesigAlts;
488 std::list<Type *> curTypes { (objStack.top())->getType() }, newTypes;
489 for ( Expression * expr : designation->get_designators() ) {
490 PRINT( std::cerr << "____untyped: " << expr << std::endl; )
491 std::list<DesignatorChain>::iterator dit = desigAlts.begin();
492 if ( NameExpr * nexpr = dynamic_cast<NameExpr *>(expr) ) {
493 for ( Type * t : curTypes ) {
494 assert( dit != desigAlts.end() );
495 DesignatorChain & d = *dit;
496 PRINT( std::cerr << "____actual: " << t << std::endl; )
497 ReferenceToType * refType = dynamic_cast<ReferenceToType *>(t);
498 std::list<Declaration *> members;
499 if ( refType ) {
500 refType->lookup( nexpr->get_name(), members ); // concatenate identical field name
501 // xxx - need to also include anonymous members in this somehow...
502 for ( Declaration * mem: members ) {
503 if ( ObjectDecl * field = dynamic_cast<ObjectDecl *>(mem) ) {
504 PRINT( std::cerr << "____alt: " << field->get_type() << std::endl; )
505 DesignatorChain newD = d;
506 newD.push_back( new VariableExpr( field ) );
507 newDesigAlts.push_back( newD );
508 newTypes.push_back( field->get_type() );
509 } // if
510 } // for
511 } // if
512 ++dit;
513 } // for
514 } else {
515 for ( Type * t : curTypes ) {
516 assert( dit != desigAlts.end() );
517 DesignatorChain & d = *dit;
518 if ( ArrayType * at = dynamic_cast< ArrayType * > ( t ) ) {
519 PRINT( std::cerr << "____alt: " << at->get_base() << std::endl; )
520 d.push_back( expr );
521 newDesigAlts.push_back( d );
522 newTypes.push_back( at->get_base() );
523 }
524 ++dit;
525 } // for
526 } // if
527 desigAlts = newDesigAlts;
528 newDesigAlts.clear();
529 curTypes = newTypes;
530 newTypes.clear();
531 assertf( desigAlts.size() == curTypes.size(), "Designator alternatives (%zu) and current types (%zu) out of sync", desigAlts.size(), curTypes.size() );
532 } // for
533 if ( desigAlts.size() > 1 ) {
534 SemanticError( designation, toString("Too many alternatives (", desigAlts.size(), ") for designation: ") );
535 } else if ( desigAlts.size() == 0 ) {
536 SemanticError( designation, "No reasonable alternatives for designation: " );
537 }
538 DesignatorChain & d = desigAlts.back();
539 PRINT( for ( Expression * expr : d ) {
540 std::cerr << "____desig: " << expr << std::endl;
541 } ) // for
542 assertf( ! curTypes.empty(), "empty designator chosen");
543
544 // set new designators
545 assertf( ! objStack.empty(), "empty object stack when setting designation" );
546 Designation * actualDesignation = new Designation( d );
547 objStack.top()->setPosition( d ); // destroys d
548 return actualDesignation;
549 }
550
551 void CurrentObject::increment() {
552 PRINT( std::cerr << "____increment" << std::endl; )
553 if ( ! objStack.empty() ) {
554 PRINT( std::cerr << *objStack.top() << std::endl; )
555 objStack.top()->smallStep();
556 }
557 }
558
559 void CurrentObject::enterListInit() {
560 PRINT( std::cerr << "____entering list init" << std::endl; )
561 assertf( ! objStack.empty(), "empty obj stack entering list init" );
562 Type * type = objStack.top()->getNext();
563 if ( type ) {
564 objStack.push( createMemberIterator( type ) );
565 } else {
566 assertf( false, "not sure about this case..." );
567 }
568 }
569
570 void CurrentObject::exitListInit() {
571 PRINT( std::cerr << "____exiting list init" << std::endl; )
572 assertf( ! objStack.empty(), "objstack empty" );
573 delete objStack.top();
574 objStack.pop();
575 if ( ! objStack.empty() ) {
576 PRINT( std::cerr << *objStack.top() << std::endl; )
577 objStack.top()->bigStep();
578 }
579 }
580
581 std::list< InitAlternative > CurrentObject::getOptions() {
582 PRINT( std::cerr << "____getting current options" << std::endl; )
583 assertf( ! objStack.empty(), "objstack empty in getOptions" );
584 return **objStack.top();
585 }
586
587 Type * CurrentObject::getCurrentType() {
588 PRINT( std::cerr << "____getting current type" << std::endl; )
589 assertf( ! objStack.empty(), "objstack empty in getCurrentType" );
590 return objStack.top()->getNext();
591 }
592} // namespace ResolvExpr
593
594namespace ast {
595 /// Iterates members of a type by initializer.
596 class MemberIterator {
597 public:
598 virtual ~MemberIterator() {}
599
600 /// Internal set position based on iterator ranges.
601 virtual void setPosition(
602 std::deque< ptr< Expr > >::const_iterator it,
603 std::deque< ptr< Expr > >::const_iterator end ) = 0;
604
605 /// Walks the current object using the given designators as a guide.
606 void setPosition( const std::deque< ptr< Expr > > & designators ) {
607 setPosition( designators.begin(), designators.end() );
608 }
609
610 /// Retrieve the list of possible (Type,Designation) pairs for the
611 /// current position in the current object.
612 virtual std::deque< InitAlternative > operator* () const = 0;
613
614 /// True if the iterator is not currently at the end.
615 virtual operator bool() const = 0;
616
617 /// Moves the iterator by one member in the current object.
618 virtual MemberIterator & bigStep() = 0;
619
620 /// Moves the iterator by one member in the current subobject.
621 virtual MemberIterator & smallStep() = 0;
622
623 /// The type of the current object.
624 virtual const Type * getType() = 0;
625
626 /// The type of the current subobject.
627 virtual const Type * getNext() = 0;
628
629 /// Helper for operator*; aggregates must add designator to each init
630 /// alternative, but adding designators in operator* creates duplicates.
631 virtual std::deque< InitAlternative > first() const = 0;
632 };
633
634 /// create a new MemberIterator that traverses a type correctly
635 MemberIterator * createMemberIterator( const CodeLocation & loc, const Type * type );
636
637 /// Iterates "other" types (e.g. basic, pointer) which do not change at list initializer entry
638 class SimpleIterator final : public MemberIterator {
639 CodeLocation location;
640 const Type * type = nullptr;
641 public:
642 SimpleIterator( const CodeLocation & loc, const Type * t ) : location( loc ), type( t ) {}
643
644 void setPosition(
645 std::deque< ptr< Expr > >::const_iterator begin,
646 std::deque< ptr< Expr > >::const_iterator end
647 ) override {
648 if ( begin != end ) {
649 SemanticError( location, "Un-designated initializer given non-empty designator" );
650 }
651 }
652
653 std::deque< InitAlternative > operator* () const override { return first(); }
654
655 operator bool() const override { return type; }
656
657 SimpleIterator & bigStep() override { return smallStep(); }
658 SimpleIterator & smallStep() override {
659 type = nullptr; // empty on increment because no members
660 return *this;
661 }
662
663 const Type * getType() override { return type; }
664
665 const Type * getNext() override { return type; }
666
667 std::deque< InitAlternative > first() const override {
668 if ( type ) return { InitAlternative{ type, new Designation{ location } } };
669 return {};
670 }
671 };
672
673 /// Iterates over an indexed type:
674 class IndexIterator : public MemberIterator {
675 protected:
676 CodeLocation location;
677 size_t index = 0;
678 size_t size = 0;
679 std::unique_ptr<MemberIterator> memberIter;
680 public:
681 IndexIterator( const CodeLocation & loc, size_t size ) :
682 location( loc ), size( size )
683 {}
684
685 void setPosition( const Expr * expr ) {
686 // need to permit integer-constant-expressions, including: integer constants,
687 // enumeration constants, character constants, sizeof expressions, alignof expressions,
688 // cast expressions
689
690 auto arg = eval( expr );
691 assertf( arg.hasKnownValue, "Non-evaluable expression made it to IndexIterator" );
692 index = arg.knownValue;
693
694 // if ( auto constExpr = dynamic_cast< const ConstantExpr * >( expr ) ) {
695 // try {
696 // index = constExpr->intValue();
697 // } catch ( SemanticErrorException & ) {
698 // SemanticError( expr, "Constant expression of non-integral type in array designator: " );
699 // }
700 // } else if ( auto castExpr = dynamic_cast< const CastExpr * >( expr ) ) {
701 // setPosition( castExpr->arg );
702 // } else if ( dynamic_cast< const SizeofExpr * >( expr ) || dynamic_cast< const AlignofExpr * >( expr ) ) {
703 // index = 0;
704 // } else {
705 // assertf( false, "2 bad designator given to ArrayIterator: %s", toString( expr ).c_str() );
706 // }
707 }
708
709 void setPosition(
710 std::deque<ast::ptr<ast::Expr>>::const_iterator begin,
711 std::deque<ast::ptr<ast::Expr>>::const_iterator end
712 ) override {
713 if ( begin == end ) return;
714
715 setPosition( *begin );
716 memberIter->setPosition( ++begin, end );
717 }
718
719 std::deque< InitAlternative > operator* () const override { return first(); }
720
721 operator bool() const override { return index < size; }
722 };
723
724 /// Iterates over the members of array types:
725 class ArrayIterator final : public IndexIterator {
726 const ArrayType * array = nullptr;
727 const Type * base = nullptr;
728
729 size_t getSize( const Expr * expr ) {
730 auto res = eval( expr );
731 if ( !res.hasKnownValue ) {
732 SemanticError( location, toString( "Array designator must be a constant expression: ", expr ) );
733 }
734 return res.knownValue;
735 }
736
737 public:
738 ArrayIterator( const CodeLocation & loc, const ArrayType * at ) :
739 IndexIterator( loc, getSize( at->dimension) ),
740 array( at ), base( at->base ) {
741 PRINT( std::cerr << "Creating array iterator: " << at << std::endl; )
742 memberIter.reset( createMemberIterator( loc, base ) );
743 if ( at->isVarLen ) {
744 SemanticError( location, at, "VLA initialization does not support @=: " );
745 }
746 }
747
748 ArrayIterator & bigStep() override {
749 PRINT( std::cerr << "bigStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
750 ++index;
751 memberIter.reset( index < size ? createMemberIterator( location, base ) : nullptr );
752 return *this;
753 }
754
755 ArrayIterator & smallStep() override {
756 PRINT( std::cerr << "smallStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
757 if ( memberIter ) {
758 PRINT( std::cerr << "has member iter: " << *memberIter << std::endl; )
759 memberIter->smallStep();
760 if ( *memberIter ) {
761 PRINT( std::cerr << "has valid member iter" << std::endl; )
762 return *this;
763 }
764 }
765 return bigStep();
766 }
767
768 const Type * getType() override { return array; }
769
770 const Type * getNext() override { return base; }
771
772 std::deque< InitAlternative > first() const override {
773 PRINT( std::cerr << "first in ArrayIterator (" << index << "/" << size << ")" << std::endl; )
774 if ( memberIter && *memberIter ) {
775 std::deque< InitAlternative > ret = memberIter->first();
776 for ( InitAlternative & alt : ret ) {
777 alt.designation.get_and_mutate()->designators.emplace_front( ConstantExpr::from_ulong( location, index ) );
778 }
779 return ret;
780 }
781 return {};
782 }
783 };
784
785 class AggregateIterator : public MemberIterator {
786 protected:
787 using MemberList = std::vector< ptr< Decl > >;
788
789 CodeLocation location;
790 std::string kind; // for debug
791 std::string name;
792 const Type * inst;
793 const MemberList & members;
794 MemberList::const_iterator curMember;
795 bool atbegin = true; // false at first {small,big}Step
796 const Type * curType = nullptr;
797 std::unique_ptr< MemberIterator > memberIter = nullptr;
798 TypeSubstitution sub;
799
800 bool init() {
801 PRINT( std::cerr << "--init()--" << members.size() << std::endl; )
802 if ( curMember != members.end() ) {
803 if ( auto field = curMember->as< ObjectDecl >() ) {
804 PRINT( std::cerr << "incremented to field: " << field << std::endl; )
805 curType = field->get_type();
806 memberIter.reset( createMemberIterator( location, curType ) );
807 return true;
808 }
809 }
810 return false;
811 }
812
813 AggregateIterator(
814 const CodeLocation & loc, const std::string k, const std::string & n, const Type * i,
815 const MemberList & ms )
816 : location( loc ), kind( k ), name( n ), inst( i ), members( ms ), curMember( ms.begin() ),
817 sub( genericSubstitution( i ) ) {
818 PRINT( std::cerr << "Creating " << kind << "(" << name << ")"; )
819 init();
820 }
821
822 public:
823 void setPosition(
824 std::deque< ptr< Expr > >::const_iterator begin,
825 std::deque< ptr< Expr > >::const_iterator end
826 ) final {
827 if ( begin == end ) return;
828
829 if ( auto varExpr = begin->as< VariableExpr >() ) {
830 for ( curMember = members.begin(); curMember != members.end(); ++curMember ) {
831 if ( *curMember != varExpr->var ) continue;
832
833 ++begin;
834
835 memberIter.reset( createMemberIterator( location, varExpr->result ) );
836 curType = varExpr->result;
837 atbegin = curMember == members.begin() && begin == end;
838 memberIter->setPosition( begin, end );
839 return;
840 }
841 assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() );
842 } else {
843 assertf( false, "1 bad designator given to %s: %s", kind.c_str(), toString( *begin ).c_str() );
844 }
845 }
846
847 std::deque< InitAlternative > operator* () const final {
848 if ( memberIter && *memberIter ) {
849 std::deque< InitAlternative > ret = memberIter->first();
850 PRINT( std::cerr << "sub: " << sub << std::endl; )
851 for ( InitAlternative & alt : ret ) {
852 PRINT( std::cerr << "iterating and adding designators" << std::endl; )
853 alt.designation.get_and_mutate()->designators.emplace_front(
854 new VariableExpr{ location, curMember->strict_as< ObjectDecl >() } );
855 // need to substitute for generic types so that casts are to concrete types
856 alt.type = shallowCopy(alt.type.get());
857 PRINT( std::cerr << " type is: " << alt.type; )
858 sub.apply( alt.type ); // also apply to designation??
859 PRINT( std::cerr << " ==> " << alt.type << std::endl; )
860 }
861 return ret;
862 }
863 return {};
864 }
865
866 AggregateIterator & smallStep() final {
867 PRINT( std::cerr << "smallStep in " << kind << std::endl; )
868 atbegin = false;
869 if ( memberIter ) {
870 PRINT( std::cerr << "has member iter, incrementing..." << std::endl; )
871 memberIter->smallStep();
872 if ( *memberIter ) {
873 PRINT( std::cerr << "success!" << std::endl; )
874 return *this;
875 }
876 }
877 return bigStep();
878 }
879
880 AggregateIterator & bigStep() override = 0;
881
882 const Type * getType() final { return inst; }
883
884 const Type * getNext() final {
885 bool hasMember = memberIter && *memberIter;
886 return hasMember ? memberIter->getType() : nullptr;
887 }
888
889 std::deque< InitAlternative > first() const final {
890 std::deque< InitAlternative > ret;
891 PRINT( std::cerr << "first " << kind << std::endl; )
892 if ( memberIter && *memberIter ) {
893 PRINT( std::cerr << "adding children" << std::endl; )
894 ret = memberIter->first();
895 for ( InitAlternative & alt : ret ) {
896 PRINT( std::cerr << "iterating and adding designators" << std::endl; )
897 alt.designation.get_and_mutate()->designators.emplace_front(
898 new VariableExpr{ location, curMember->strict_as< ObjectDecl >() } );
899 }
900 }
901 if ( atbegin ) {
902 // only add self if at the very beginning of the structure
903 PRINT( std::cerr << "adding self" << std::endl; )
904 ret.emplace_front( inst, new Designation{ location } );
905 }
906 return ret;
907 }
908 };
909
910 class StructIterator final : public AggregateIterator {
911 public:
912 StructIterator( const CodeLocation & loc, const StructInstType * inst )
913 : AggregateIterator( loc, "StructIterator", inst->name, inst, inst->base->members ) {}
914
915 operator bool() const override {
916 return curMember != members.end() || (memberIter && *memberIter);
917 }
918
919 StructIterator & bigStep() override {
920 PRINT( std::cerr << "bigStep in " << kind << std::endl; )
921 atbegin = false;
922 memberIter = nullptr;
923 curType = nullptr;
924 while ( curMember != members.end() ) {
925 ++curMember;
926 if ( init() ) return *this;
927 }
928 return *this;
929 }
930 };
931
932 class UnionIterator final : public AggregateIterator {
933 public:
934 UnionIterator( const CodeLocation & loc, const UnionInstType * inst )
935 : AggregateIterator( loc, "UnionIterator", inst->name, inst, inst->base->members ) {}
936
937 operator bool() const override { return memberIter && *memberIter; }
938
939 UnionIterator & bigStep() override {
940 // unions only initialize one member
941 PRINT( std::cerr << "bigStep in " << kind << std::endl; )
942 atbegin = false;
943 memberIter = nullptr;
944 curType = nullptr;
945 curMember = members.end();
946 return *this;
947 }
948 };
949
950 /// Iterates across the positions in a tuple:
951 class TupleIterator final : public IndexIterator {
952 ast::TupleType const * const tuple;
953
954 const ast::Type * typeAtIndex() const {
955 assert( index < size );
956 return tuple->types[ index ].get();
957 }
958
959 public:
960 TupleIterator( const CodeLocation & loc, const TupleType * type )
961 : IndexIterator( loc, type->size() ), tuple( type ) {
962 PRINT( std::cerr << "Creating tuple iterator: " << type << std::endl; )
963 memberIter.reset( createMemberIterator( loc, typeAtIndex() ) );
964 }
965
966 TupleIterator & bigStep() override {
967 ++index;
968 memberIter.reset( index < size ?
969 createMemberIterator( location, typeAtIndex() ) : nullptr );
970 return *this;
971 }
972
973 TupleIterator & smallStep() override {
974 if ( memberIter ) {
975 PRINT( std::cerr << "has member iter: " << *memberIter << std::endl; )
976 memberIter->smallStep();
977 if ( !memberIter ) {
978 PRINT( std::cerr << "has valid member iter" << std::endl; )
979 return *this;
980 }
981 }
982 return bigStep();
983 }
984
985 const ast::Type * getType() override {
986 return tuple;
987 }
988
989 const ast::Type * getNext() override {
990 bool hasMember = memberIter && *memberIter;
991 return hasMember ? memberIter->getType() : nullptr;
992 }
993
994 std::deque< InitAlternative > first() const override {
995 PRINT( std::cerr << "first in TupleIterator (" << index << "/" << size << ")" << std::endl; )
996 if ( memberIter && *memberIter ) {
997 std::deque< InitAlternative > ret = memberIter->first();
998 for ( InitAlternative & alt : ret ) {
999 alt.designation.get_and_mutate()->designators.emplace_front(
1000 ConstantExpr::from_ulong( location, index ) );
1001 }
1002 return ret;
1003 }
1004 return {};
1005 }
1006 };
1007
1008 MemberIterator * createMemberIterator( const CodeLocation & loc, const Type * type ) {
1009 if ( auto aggr = dynamic_cast< const BaseInstType * >( type ) ) {
1010 if ( auto sit = dynamic_cast< const StructInstType * >( aggr ) ) {
1011 assert( sit->base );
1012 return new StructIterator{ loc, sit };
1013 } else if ( auto uit = dynamic_cast< const UnionInstType * >( aggr ) ) {
1014 assert( uit->base );
1015 return new UnionIterator{ loc, uit };
1016 } else {
1017 assertf(
1018 dynamic_cast< const EnumInstType * >( type )
1019 || dynamic_cast< const TypeInstType * >( type ),
1020 "Encountered unhandled BaseInstType in createMemberIterator: %s",
1021 toString( type ).c_str() );
1022 return new SimpleIterator{ loc, type };
1023 }
1024 } else if ( auto at = dynamic_cast< const ArrayType * >( type ) ) {
1025 return new ArrayIterator{ loc, at };
1026 } else if ( auto tt = dynamic_cast< const TupleType * >( type ) ) {
1027 return new TupleIterator{ loc, tt };
1028 } else {
1029 return new SimpleIterator{ loc, type };
1030 }
1031 }
1032
1033 CurrentObject::CurrentObject( const CodeLocation & loc, const Type * type ) : objStack() {
1034 objStack.emplace_back( new SimpleIterator{ loc, type } );
1035 }
1036
1037 const Designation * CurrentObject::findNext( const Designation * designation ) {
1038 using DesignatorChain = std::deque< ptr< Expr > >;
1039 PRINT( std::cerr << "___findNext" << std::endl; )
1040
1041 // find all the d's
1042 std::vector< DesignatorChain > desigAlts{ {} }, newDesigAlts;
1043 std::deque< const Type * > curTypes{ objStack.back()->getType() }, newTypes;
1044 for ( const Expr * expr : designation->designators ) {
1045 PRINT( std::cerr << "____untyped: " << expr << std::endl; )
1046 auto dit = desigAlts.begin();
1047 if ( auto nexpr = dynamic_cast< const NameExpr * >( expr ) ) {
1048 for ( const Type * t : curTypes ) {
1049 assert( dit != desigAlts.end() );
1050
1051 DesignatorChain & d = *dit;
1052 PRINT( std::cerr << "____actual: " << t << std::endl; )
1053 if ( auto refType = dynamic_cast< const BaseInstType * >( t ) ) {
1054 // concatenate identical field names
1055 for ( const Decl * mem : refType->lookup( nexpr->name ) ) {
1056 if ( auto field = dynamic_cast< const ObjectDecl * >( mem ) ) {
1057 PRINT( std::cerr << "____alt: " << field->type << std::endl; )
1058 DesignatorChain d2 = d;
1059 d2.emplace_back( new VariableExpr{ expr->location, field } );
1060 newDesigAlts.emplace_back( std::move( d2 ) );
1061 newTypes.emplace_back( field->type );
1062 }
1063 }
1064 }
1065
1066 ++dit;
1067 }
1068 } else {
1069 for ( const Type * t : curTypes ) {
1070 assert( dit != desigAlts.end() );
1071
1072 DesignatorChain & d = *dit;
1073 if ( auto at = dynamic_cast< const ArrayType * >( t ) ) {
1074 PRINT( std::cerr << "____alt: " << at->get_base() << std::endl; )
1075 d.emplace_back( expr );
1076 newDesigAlts.emplace_back( d );
1077 newTypes.emplace_back( at->base );
1078 }
1079 }
1080 }
1081
1082 // reset queue
1083 desigAlts = std::move( newDesigAlts );
1084 newDesigAlts.clear();
1085 curTypes = std::move( newTypes );
1086 newTypes.clear();
1087 assertf( desigAlts.size() == curTypes.size(), "Designator alternatives (%zu) and current types (%zu) out of sync", desigAlts.size(), curTypes.size() );
1088 }
1089
1090 if ( desigAlts.size() > 1 ) {
1091 SemanticError( designation, toString("Too many alternatives (", desigAlts.size(), ") for designation: ") );
1092 } else if ( desigAlts.empty() ) {
1093 SemanticError( designation, "No reasonable alternatives for designation: " );
1094 }
1095
1096 DesignatorChain & d = desigAlts.back();
1097 PRINT( for ( Expression * expr : d ) {
1098 std::cerr << "____desig: " << expr << std::endl;
1099 } ) // for
1100 assertf( ! curTypes.empty(), "empty designator chosen");
1101
1102 // set new designators
1103 assertf( ! objStack.empty(), "empty object stack when setting designation" );
1104 Designation * actualDesignation =
1105 new Designation{ designation->location, DesignatorChain{d} };
1106 objStack.back()->setPosition( d ); // destroys d
1107 return actualDesignation;
1108 }
1109
1110 void CurrentObject::setNext( const Designation * designation ) {
1111 PRINT( std::cerr << "____setNext" << designation << std::endl; )
1112 assertf( ! objStack.empty(), "obj stack empty in setNext" );
1113 objStack.back()->setPosition( designation->designators );
1114 }
1115
1116 void CurrentObject::increment() {
1117 PRINT( std::cerr << "____increment" << std::endl; )
1118 if ( objStack.empty() ) return;
1119 PRINT( std::cerr << *objStack.back() << std::endl; )
1120 objStack.back()->smallStep();
1121 }
1122
1123 void CurrentObject::enterListInit( const CodeLocation & loc ) {
1124 PRINT( std::cerr << "____entering list init" << std::endl; )
1125 assertf( ! objStack.empty(), "empty obj stack entering list init" );
1126 const ast::Type * type = objStack.back()->getNext();
1127 assert( type );
1128 objStack.emplace_back( createMemberIterator( loc, type ) );
1129 }
1130
1131 void CurrentObject::exitListInit() {
1132 PRINT( std::cerr << "____exiting list init" << std::endl; )
1133 assertf( ! objStack.empty(), "objstack empty" );
1134 objStack.pop_back();
1135 if ( ! objStack.empty() ) {
1136 PRINT( std::cerr << *objStack.back() << std::endl; )
1137 objStack.back()->bigStep();
1138 }
1139 }
1140
1141 std::deque< InitAlternative > CurrentObject::getOptions() {
1142 PRINT( std::cerr << "____getting current options" << std::endl; )
1143 assertf( ! objStack.empty(), "objstack empty in getOptions" );
1144 return **objStack.back();
1145 }
1146
1147 const Type * CurrentObject::getCurrentType() {
1148 PRINT( std::cerr << "____getting current type" << std::endl; )
1149 assertf( ! objStack.empty(), "objstack empty in getCurrentType" );
1150 return objStack.back()->getNext();
1151 }
1152}
1153
1154// Local Variables: //
1155// tab-width: 4 //
1156// mode: c++ //
1157// compile-command: "make install" //
1158// End: //
Note: See TracBrowser for help on using the repository browser.