0

I am going to give some classes about C++ and data structures, and to check students' progress I'd like them to develop the structures I talk about. This is the common approach for data structures classes, I guess. But I want more, I want the students to have a quick feedback on what they are missing, so I developed several unit tests for the classes that check the behavior and give them instant results on what is wrong.

This has been working properly for the past two semesters, but I want a step further on that automatized correction. I've been studying how to check what are the internal components of a class, so I can know if someone has implemented correctly a tree with a node* root and size_t size and hasn't used additional not-necessary attributes, for instance.

I know that I can have a rough approximation of an object size with sizeof, but the results are not that precise. It frequently is different from what I expect, for example: I tested creating a class with a pointer (8 bytes) and an int (4 bytes), but the sizeof was 28. From what I learnt, probably this has something to do with virtual function table and other alignment stuff.

So, how far and further can I go analyzing if someone has coded a data structure the proper and expected manner? How can I check that someone just didn't #include <list> and created an adaptor (for this I know I can just strip the includes but anyway)?

ranieri
  • 2,030
  • 2
  • 21
  • 39
  • 3
    Why not actually parse the code and check it that way? E.g. via clang-ast? – Kerrek SB Jul 24 '15 at 00:24
  • @KerrekSB I haven't found about that tool yet. I'm going to have a read. – ranieri Jul 24 '15 at 00:29
  • *"How can I check that someone just didn't #include and created an adaptor"* - you might need to decide whether you're really content to giving students "quick feedback" vs. aiming for fully automated marking. If you're going to read over the submission you'll notice deliberate abuses like adapting ``, and if they're trying to get away with it you don't owe them the favour of "catching" them early. Focusing effort on helping students who're genuinely trying to create a good implementation sounds more productive to me. – Tony Delroy Jul 24 '15 at 00:50
  • Did something very similar to what @KerrekSB suggests. Took student code, got the AST output from the compiler, and ran the AST through a set of rules to order variants to make structures as similar as possible before comparing against a database of standard algorithms and data structures. Then ran out of funding. The goal was to assist students in near-real time. System was called MAPPIE. Professor in charge was Vivek Kumar. No idea if anyone wrote any public papers on it. – user4581301 Jul 24 '15 at 01:25

1 Answers1

0

Let's break this answer into two parts, we'll split on the return from is_standard_layout.

1. Virtual Classes

is_standard_layout will return false, meaning the class is virtual. virtual classes will contain all the members from their parents aside from just a virtual function pointer. You can find more info here. Basically, your best bet for finding the size of the members here is to do sizeof the class in question reduced by sizeof(void*) And that's the size of your virtual class's members.

2. Non-Virtual Classes

is_standard_layout will return true meaning this is not a virtual class. In this case we can use offsetof to find the first member variable past the header information. Finding the end of the object with the pointer to the object and sizeof will you to measure the distance to the point returned by offsetof.

Both of these methods should yield the size of the members in the classes. determining an allowable range for class size is a matter of preference. But placing the evaluation in a static_assert will allow you to also provide a compile time message indicating the reason for the assert.

Community
  • 1
  • 1
Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288