1//===------------- InterpBuiltinObjectSize.cpp ------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// Implementation of the frontend part of the __builtin_object_size and
10// __builtin_dynamic_object_size builtins.
11
12#include "InterpHelpers.h"
13#include "Pointer.h"
14#include "Record.h"
15#include "clang/AST/RecordLayout.h"
16
17using namespace clang;
18using namespace clang::interp;
19
20enum : uint8_t {
21 Regular = 1 << 0,
22 IgnoreBaseCasts = 1 << 1,
23 SurroundingArray = 1 << 2,
24};
25
26// Helper to check if a Type can be passed to
27// ASTContext::getRecordLayout().
28static bool validType(QualType T) {
29 if (const RecordDecl *RD = T->getAsRecordDecl())
30 return ASTContext::hasLayout(D: RD);
31 return true;
32}
33
34static QualType computeFieldType(const ASTContext &ASTCtx,
35 const OpaquePointer &OP,
36 unsigned TypeModifier = 0) {
37 QualType CurType = OP.getObjectType();
38
39 unsigned Drop = 0;
40 if (TypeModifier & IgnoreBaseCasts && OP.PathLength != 0 &&
41 OP.path().back().Kind == PointerPathEntry::Base)
42 Drop = 1;
43
44 if (TypeModifier & SurroundingArray && OP.PathLength != 0 &&
45 OP.path().back().Kind == PointerPathEntry::Array)
46 Drop = 1;
47
48 for (const PointerPathEntry &Entry : OP.path().drop_back(N: Drop)) {
49 switch (Entry.Kind) {
50 case PointerPathEntry::Base:
51 CurType = ASTCtx.getCanonicalTagType(TD: Entry.RD.getPointer());
52 break;
53 case PointerPathEntry::Field:
54 CurType = Entry.FD->getType();
55 break;
56 case PointerPathEntry::Array:
57 case PointerPathEntry::NegativeArray:
58 if (!CurType->isArrayType())
59 continue;
60 CurType = CurType->getAsArrayTypeUnsafe()->getElementType();
61 }
62 }
63
64 return CurType;
65}
66
67static std::optional<unsigned> computeFullDescSize(const ASTContext &ASTCtx,
68 const Descriptor *Desc) {
69 if (Desc->isPrimitive() || Desc->isArray()) {
70 QualType T = Desc->getType();
71 if (!validType(T))
72 return std::nullopt;
73 return ASTCtx.getTypeSizeInChars(T).getQuantity();
74 }
75
76 if (Desc->isRecord()) {
77 // Can't use Descriptor::getType() as that may return a pointer type. Look
78 // at the decl directly.
79
80 const RecordDecl *RD = Desc->ElemRecord->getDecl();
81 if (!ASTContext::hasLayout(D: RD))
82 return std::nullopt;
83
84 return ASTCtx.getTypeSizeInChars(T: ASTCtx.getCanonicalTagType(TD: RD))
85 .getQuantity();
86 }
87
88 return std::nullopt;
89}
90
91/// Compute the byte offset of \p Ptr in the full declaration.
92static unsigned computePointerOffset(const ASTContext &ASTCtx,
93 const Pointer &Ptr) {
94 return Ptr.computeLayoutOffset(ASTCtx).value_or(u: 0);
95}
96
97/// Does Ptr point to the last subobject?
98static bool pointsToLastObject(const Pointer &Ptr) {
99 Pointer P = Ptr;
100 while (!P.isRoot()) {
101
102 if (P.isArrayElement()) {
103 P = P.expand().getArray();
104 continue;
105 }
106 if (P.isBaseClass()) {
107 if (P.getRecord()->getNumFields() > 0)
108 return false;
109 P = P.getBase();
110 continue;
111 }
112
113 Pointer Base = P.getBase();
114 if (const Record *R = Base.getRecord()) {
115 assert(P.getField());
116 if (P.getField()->getFieldIndex() != R->getNumFields() - 1)
117 return false;
118 }
119 P = Base;
120 }
121
122 return true;
123}
124
125/// Does Ptr point to the last object AND to a flexible array member?
126static bool isUserWritingOffTheEnd(const ASTContext &Ctx, const Pointer &Ptr,
127 bool InvalidBase) {
128 auto isFlexibleArrayMember = [&](const Descriptor *FieldDesc) {
129 using FAMKind = LangOptions::StrictFlexArraysLevelKind;
130 FAMKind StrictFlexArraysLevel =
131 Ctx.getLangOpts().getStrictFlexArraysLevel();
132
133 if (StrictFlexArraysLevel == FAMKind::Default)
134 return true;
135
136 unsigned NumElems = FieldDesc->getNumElems();
137 if (NumElems == 0 && StrictFlexArraysLevel != FAMKind::IncompleteOnly)
138 return true;
139
140 if (NumElems == 1 && StrictFlexArraysLevel == FAMKind::OneZeroOrIncomplete)
141 return true;
142 return false;
143 };
144
145 const Descriptor *FieldDesc = Ptr.getFieldDesc();
146 if (!FieldDesc->isArray())
147 return false;
148
149 return InvalidBase && pointsToLastObject(Ptr) &&
150 isFlexibleArrayMember(FieldDesc);
151}
152
153static bool isUserWritingOffTheEnd(const ASTContext &ASTCtx,
154 const OpaquePointer &OP) {
155 if (OP.PathLength == 0)
156 return false;
157
158 QualType CurType = OP.getObjectType();
159 for (unsigned I = 0; I != OP.PathLength; ++I) {
160 const PointerPathEntry &Entry = OP.Path[I];
161 switch (Entry.Kind) {
162 case PointerPathEntry::Base:
163 return false;
164 case PointerPathEntry::Field: {
165 const FieldDecl *FD = OP.Path[I].FD;
166 if (!FD->getParent()->isUnion() &&
167 FD->getFieldIndex() != FD->getParent()->getNumFields() - 1)
168 return false;
169 CurType = FD->getType();
170 } break;
171 case PointerPathEntry::Array: {
172 if (I == OP.PathLength - 1)
173 break;
174
175 if (!CurType->isArrayType())
176 break;
177
178 unsigned Index = OP.Path[I].Index;
179 const ArrayType *AT = CurType->getAsArrayTypeUnsafe();
180 assert(AT);
181 if (const auto *CAT = dyn_cast<ConstantArrayType>(Val: AT)) {
182 if (Index != CAT->getLimitedSize() - 1)
183 return false;
184 CurType = CAT->getElementType();
185 } else {
186 return false;
187 }
188 } break;
189 case PointerPathEntry::NegativeArray:
190 return false;
191 }
192 }
193
194 // We're pointing to the last field in the full object.
195 // CurType is now the most derived type.
196 if (!CurType->isArrayType())
197 return false;
198
199 if (isa<IncompleteArrayType>(Val: CurType))
200 return true;
201
202 const auto *CAT = dyn_cast<ConstantArrayType>(Val&: CurType);
203 if (!CAT)
204 return false;
205
206 using FAMKind = LangOptions::StrictFlexArraysLevelKind;
207 FAMKind StrictFlexArraysLevel =
208 ASTCtx.getLangOpts().getStrictFlexArraysLevel();
209
210 if (StrictFlexArraysLevel == FAMKind::Default)
211 return true;
212
213 unsigned Size = CAT->getZExtSize();
214 if (Size == 0 && StrictFlexArraysLevel != FAMKind::IncompleteOnly)
215 return true;
216
217 if (Size == 1 && StrictFlexArraysLevel == FAMKind::OneZeroOrIncomplete)
218 return true;
219 return false;
220}
221
222/// Determine the offset of the given pointer. Depending on \c
223/// UseClosestSurroundingVariable, the offset is either relative to the full
224/// object or to the closest surrounding field or array.
225static std::optional<uint64_t>
226computeOpaquePtrOffset(const ASTContext &ASTCtx, const Pointer &Ptr,
227 bool UseClosestSurroundingVariable,
228 bool &OffsetIsNegative) {
229 const OpaquePointer &OP = Ptr.asOpaquePointer();
230
231 uint64_t Offset = 0;
232 std::optional<uint64_t> SurroundingArrayOffset;
233 QualType CurType = OP.getObjectType();
234 for (const PointerPathEntry &Entry : OP.path()) {
235 switch (Entry.Kind) {
236 case PointerPathEntry::Base: {
237 const RecordDecl *RD = CurType->getAsRecordDecl();
238 if (!ASTContext::hasLayout(D: RD))
239 return std::nullopt;
240
241 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: RD);
242 Offset += Layout.getBaseClassOffset(Base: Entry.RD.getPointer()).getQuantity();
243
244 CurType = ASTCtx.getCanonicalTagType(TD: Entry.RD.getPointer());
245 } break;
246
247 case PointerPathEntry::Field: {
248 const FieldDecl *FD = Entry.FD;
249 const RecordDecl *RD = FD->getParent();
250 if (!ASTContext::hasLayout(D: RD))
251 return std::nullopt;
252
253 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: RD);
254 Offset +=
255 ASTCtx.toCharUnitsFromBits(BitSize: Layout.getFieldOffset(FieldNo: FD->getFieldIndex()))
256 .getQuantity();
257
258 CurType = FD->getType();
259 } break;
260 case PointerPathEntry::Array:
261 case PointerPathEntry::NegativeArray: {
262 bool Add = (Entry.Kind == PointerPathEntry::Array);
263 uint64_t Index = Entry.Index;
264 if (!Add) {
265 // NegativeArray is always > 0.
266 OffsetIsNegative = true;
267 }
268 SurroundingArrayOffset = Offset;
269 if (!CurType->isArrayType()) {
270 if (Add)
271 Offset += Index * ASTCtx.getTypeSizeInChars(T: CurType).getQuantity();
272 else
273 Offset -= Index * ASTCtx.getTypeSizeInChars(T: CurType).getQuantity();
274 continue;
275 }
276 const ArrayType *AT = CurType->getAsArrayTypeUnsafe();
277 assert(AT);
278 QualType ElemTy = AT->getElementType();
279 if (!validType(T: ElemTy) || isa<VariableArrayType>(Val: AT))
280 return std::nullopt;
281 if (Add)
282 Offset += Index * ASTCtx.getTypeSizeInChars(T: ElemTy).getQuantity();
283 else
284 Offset -= Index * ASTCtx.getTypeSizeInChars(T: ElemTy).getQuantity();
285 CurType = AT->getElementType();
286 } break;
287 }
288 }
289
290 if (UseClosestSurroundingVariable && SurroundingArrayOffset)
291 return Offset - *SurroundingArrayOffset;
292
293 QualType Ty = CurType.getNonReferenceType();
294
295 if (UseClosestSurroundingVariable &&
296 (Ty->isIncompleteType() || Ty->isFunctionType()))
297 return std::nullopt;
298
299 if (isa<VariableArrayType>(Val: Ty))
300 return std::nullopt;
301
302 if (OP.PathLength == 1 && OP.path().back().Kind == PointerPathEntry::Field &&
303 isa<IncompleteArrayType>(Val: CurType)) {
304 return Offset;
305 }
306
307 if (UseClosestSurroundingVariable)
308 return 0;
309
310 return Offset;
311}
312
313/// Check if the given pointer points to the complete object, i.e. either to the
314/// very beginning or after the end (into the flexible array member) of the
315/// object.
316static bool pointsToCompleteObject(const ASTContext &ASTCtx,
317 const Pointer &Ptr) {
318 const OpaquePointer &OP = Ptr.asOpaquePointer();
319 if (OP.PathLength == 0)
320 return true;
321
322 QualType FieldType = computeFieldType(ASTCtx, OP);
323 if (OP.isArrayElement())
324 FieldType = OP.getSurroundingArray();
325 return isa<IncompleteArrayType>(Val: FieldType);
326}
327
328static std::optional<unsigned>
329computeOpaqueSize(const ASTContext &ASTCtx, const Pointer &Ptr,
330 bool UseClosestSurroundingVariable, bool WritingOffTheEnd,
331 bool DetermineForCompleteObject) {
332 const OpaquePointer &OP = Ptr.asOpaquePointer();
333
334 CharUnits TypeSize;
335 // NOTE: Clang does not consider base casts. GCC does.
336 if (UseClosestSurroundingVariable) {
337 QualType FieldTy =
338 computeFieldType(ASTCtx, OP, TypeModifier: SurroundingArray | IgnoreBaseCasts);
339 if (!validType(T: FieldTy))
340 return std::nullopt;
341 TypeSize = ASTCtx.getTypeSizeInChars(T: FieldTy);
342 } else {
343 QualType ObjectTy = OP.getObjectType();
344 if (!validType(T: ObjectTy))
345 return std::nullopt;
346 TypeSize = ASTCtx.getTypeSizeInChars(T: ObjectTy);
347 }
348
349 // The Flexible array member should only be checked if we're pointing to the
350 // object as a whole, or if we're looking for the whole object size.
351 if (!WritingOffTheEnd && !DetermineForCompleteObject)
352 return TypeSize.getQuantity();
353
354 // Check if we need to add the flexible array member size.
355 const VarDecl *Base = OP.getBaseDecl();
356 if (!Base)
357 return TypeSize.getQuantity();
358
359 // If the base type is an incomplete array type (not a flexible array member
360 // of a struct), and we're looking for the complete object... we can't.
361 if (DetermineForCompleteObject && isa<IncompleteArrayType>(Val: Base->getType()))
362 return std::nullopt;
363
364 if (!Base->getType()->isRecordType())
365 return TypeSize.getQuantity();
366
367 if (!Base->hasInit())
368 return TypeSize.getQuantity();
369 CharUnits FlexibleArraySize = Base->getFlexibleArrayInitChars(Ctx: ASTCtx);
370 return (TypeSize + FlexibleArraySize).getQuantity();
371}
372
373namespace clang {
374namespace interp {
375
376/// Evaluate __builtin_object_size or __builtin_dynamic_object_size for the
377/// given pointer and Kind.
378///
379/// When computing the final result, the most important variable is
380/// UseClosestSurroundingVariable. If it is true, we will use the field the
381/// pointer points to, or the parent array of the element.
382/// UseClosestSurroundingVariable is true for Kind 1 and 3.
383UnsignedOrNone evaluateBuiltinObjectSize(const ASTContext &ASTCtx,
384 unsigned Kind, Pointer &Ptr,
385 const Expr *E, bool IsDynamic) {
386 if (Ptr.isZero())
387 return std::nullopt;
388
389 bool InvalidBase = false;
390 if (Ptr.isOpaquePointer()) {
391 bool UseClosestSurroundingVariable = (Kind == 1) || (Kind == 3);
392 const OpaquePointer &OP = Ptr.asOpaquePointer();
393 InvalidBase = OP.Base.getType()->isPointerType();
394 bool DetermineForCompleteObject = pointsToCompleteObject(ASTCtx, Ptr);
395 bool WritingOffTheEnd = isUserWritingOffTheEnd(ASTCtx, OP);
396
397 // Either the size of the full variable (Kind = 0 or 2) or the size of the
398 // closest surrounding variable (Kind = 1 or 3).
399 std::optional<unsigned> FullSize =
400 computeOpaqueSize(ASTCtx, Ptr, UseClosestSurroundingVariable,
401 WritingOffTheEnd, DetermineForCompleteObject);
402
403 if (!FullSize)
404 return std::nullopt;
405
406 // Similar to the FullSize above, the offset is relative either to the full
407 // variable or to the closest surrounding variable.
408 bool OffsetIsNegative = false;
409 std::optional<uint64_t> Offset = computeOpaquePtrOffset(
410 ASTCtx, Ptr, UseClosestSurroundingVariable, OffsetIsNegative);
411
412 if (!Offset)
413 return std::nullopt;
414
415 if (OffsetIsNegative)
416 return 0u;
417
418 // For __builtin_dynamic_object_size on a counted_by-annotated flexible
419 // array member, defer to IR generation (emitCountedBySize in CGBuiltin):
420 // its runtime computation uses the live 'count' field and is more accurate
421 // than the layout/initializer-derived size we'd produce here. Use the same
422 // findStructFieldAccess form-recognition CGBuiltin does, so we refuse to
423 // fold on exactly the shapes that path handles (and, importantly, *not*
424 // on '&af.fam' which designates the array-as-a-whole and stays on the
425 // layout-derived path to match GCC).
426 if (IsDynamic) {
427 const auto *ME =
428 dyn_cast_if_present<MemberExpr>(Val: findStructFieldAccess(E));
429 const auto *FD = ME ? dyn_cast<FieldDecl>(Val: ME->getMemberDecl()) : nullptr;
430 if (FD && FD->getType()->isCountAttributedType())
431 return std::nullopt;
432 }
433
434 if (!UseClosestSurroundingVariable || DetermineForCompleteObject) {
435 // Kind=3 wants a lower bound, so we can't fall back to this.
436 if (Kind == 3 && !DetermineForCompleteObject)
437 return std::nullopt;
438
439 if (InvalidBase)
440 return std::nullopt;
441
442 QualType ObjectTy = OP.getObjectType();
443 if (ObjectTy->isIncompleteType() || isa<VariableArrayType>(Val: ObjectTy) ||
444 ObjectTy->isFunctionType())
445 return std::nullopt;
446 }
447
448 *Offset += (Ptr.getByteOffset() *
449 ASTCtx.getTypeSizeInChars(T: OP.getFieldType()).getQuantity());
450
451 if (*Offset > *FullSize)
452 return 0u;
453
454 if (Kind == 1 && InvalidBase && WritingOffTheEnd)
455 return std::nullopt;
456
457 assert(*Offset <= *FullSize);
458 return static_cast<unsigned>(*FullSize - *Offset);
459 }
460
461 // ----------------------------------------------------------------------------------------------------
462
463 if (Ptr.isDummy() && Ptr.getType()->isPointerType())
464 return std::nullopt;
465
466 if (!Ptr.isBlockPointer())
467 return std::nullopt;
468
469 if (Ptr.isDummy()) {
470 if (const VarDecl *VD = Ptr.getRootVarDecl();
471 VD && VD->getType()->isPointerType())
472 InvalidBase = true;
473 }
474
475 bool UseFieldDesc = (Kind & 1u);
476 bool ReportMinimum = (Kind & 2u);
477
478 // According to the GCC documentation, we want the size of the subobject
479 // denoted by the pointer. But that's not quite right -- what we actually
480 // want is the size of the immediately-enclosing array, if there is one.
481 if (Ptr.isArrayElement())
482 Ptr = Ptr.expand();
483
484 bool DetermineForCompleteObject = Ptr.getFieldDesc() == Ptr.getDeclDesc();
485 const Descriptor *DeclDesc = Ptr.getDeclDesc();
486 assert(DeclDesc);
487
488 if (!UseFieldDesc || DetermineForCompleteObject) {
489 // Can't read beyond the pointer decl desc.
490 if (!ReportMinimum && DeclDesc->getDataType(Ctx: ASTCtx)->isPointerType())
491 return std::nullopt;
492
493 if (InvalidBase)
494 return std::nullopt;
495 } else {
496 if (isUserWritingOffTheEnd(Ctx: ASTCtx, Ptr, InvalidBase)) {
497 // If we cannot determine the size of the initial allocation, then we
498 // can't given an accurate upper-bound. However, we are still able to give
499 // conservative lower-bounds for Type=3.
500 if (Kind == 1)
501 return std::nullopt;
502 }
503 }
504
505 // The "closest surrounding subobject" is NOT a base class,
506 // so strip the base class casts.
507 if (UseFieldDesc && Ptr.isBaseClass())
508 Ptr = Ptr.stripBaseCasts();
509
510 const Descriptor *Desc = UseFieldDesc ? Ptr.getFieldDesc() : DeclDesc;
511 assert(Desc);
512
513 std::optional<unsigned> FullSize = computeFullDescSize(ASTCtx, Desc);
514 if (!FullSize)
515 return std::nullopt;
516
517 unsigned ByteOffset;
518 if (UseFieldDesc) {
519 if (Ptr.isBaseClass()) {
520 assert(computePointerOffset(ASTCtx, Ptr.getBase()) <=
521 computePointerOffset(ASTCtx, Ptr));
522 ByteOffset = computePointerOffset(ASTCtx, Ptr: Ptr.getBase()) -
523 computePointerOffset(ASTCtx, Ptr);
524 } else {
525 if (Ptr.inArray())
526 ByteOffset =
527 computePointerOffset(ASTCtx, Ptr) -
528 computePointerOffset(ASTCtx, Ptr: Ptr.expand().atIndex(Idx: 0).narrow());
529 else
530 ByteOffset = 0;
531 }
532 } else
533 ByteOffset = computePointerOffset(ASTCtx, Ptr);
534
535 assert(ByteOffset <= *FullSize);
536 return *FullSize - ByteOffset;
537}
538} // namespace interp
539} // namespace clang
540