Implementing compile-time mechanism checking uniqueness of a string

Question

The simplest way of defining my problem is that I'm trying to implement a mechanism that would check whether the same string had already been used (or a pair (number, string)). I would like this mechanism to be implemented in a smart way using C preprocessor. I would also like that this mechanism gave me compile errors when there is a conflict or run-time errors in Debug mode (by checking assertions). We don't want the developer to make a mistake when adding a message, as every message should be unique. I know that it could be done by calculating a hash or for example crc/md5 but this mechanism would be conflict-vulnerable which I need to avoid. It is crucial that every message can be used only once.

Example behaviour of this mechanism:

addMessage(1, "Message1") //OK 
addMessage(2, "Message2") //OK 
. 
. 
. 
addMessage(N, "MessageN") //OK 
addMessage(2, "Message2") //Compile error, Message2 has already been used

Alternative behaviour (when Debugging code):

addMessage(1, "Message1") //OK 
addMessage(2, "Message2") //OK 
. 
. 
. 
addMessage(N, "MessageN") //OK 
addMessage(2, "Message2") //Assertion failed, because Message2 has already been used

The preferred way of doing it would be smart usage of #define and #undef directives. In general the preprocessor should be used in a smart way (I am not sure if this is possible) maybe it can be achieved by appropriate combinations of macros? Any C preprocessor hacker that could help me solve this problem?

//EDIT: I need those messages to be unique globally, not only inside one code block (like function of if-statement).

//EDIT2: The best description of the problem would be that I have 100 different source files and I would like to check with a preprocessor (or possibly other mechanism other than parsing source files with a script at a start of the compilation every-time, which would be very time-consuming and would add another stage to an enough complicated project) if a string (or a preprocessor definition) was used more than one time. I still have no idea how to do it (I know it may not be possible at all but I hope it actually is).

In what context would you use `addMessage()`? Within a function, type definition, initialization, globally... — cdhowie, Aug 20 '14 at 19:14
Generally, it would be locally used within a class, however It could also be added globally (by a macro) to the global scope (if it would help solving this problem). There are no limitations about the scope, it can be used globally if there is such need. — Paweł Jastrzębski, Aug 20 '14 at 19:17
I see. If you can use it anywhere then it's a much more complex beast than if you could only use it, say, globally in one specific header file. — cdhowie, Aug 20 '14 at 19:19
I can use it globally in a header file, but how would it help me checking the repetitions of the strings at the compile step or at the Debug binary. — Paweł Jastrzębski, Aug 20 '14 at 19:25
Would it be an option to store the messages in something other than a C/C++ source file, and write a script that will read the file, verify your requirements, and produce a C/C++ file with the messages defined however you need? This C/C++ file would be considered a build product, and would not be checked in to your VCS. — cdhowie, Aug 20 '14 at 19:31
I seriously doubt that this is possible with Standard C++. You are expecting the *compiler* to keep custom non-trivial global state for you around. Why not generate GUIDs or something? Can you be more explicit on what you want to achieve? — filmor, Aug 21 '14 at 08:11
I would like to implement a mechanism which would catch non-unique strings (added by the developer) at compile time and report them as an error or at least catch them in Debug mode and report them as failed asserts. — Paweł Jastrzębski, Aug 21 '14 at 08:14

score 5 · Answer 1 · answered Aug 20 '14 at 21:07

This will give an error on duplicate strings:

constexpr bool isequal(char const *one, char const *two) {
  return (*one && *two) ? (*one == *two && isequal(one + 1, two + 1))
    : (!*one && !*two);
}

constexpr bool isunique(const char *test, const char* const* list)
{
    return *list == 0 || !isequal(test, *list) && isunique(test, list + 1);
}

constexpr int no_duplicates(const char* const* list, int idx)
{
    return *list == 0 ? -1 : (isunique(*list, list + 1) ? no_duplicates(list + 1, idx + 1) : idx);
}

template <int V1, int V2> struct assert_equality
{
    static const char not_equal_warning = V1 + V2 + 1000;
};

template <int V> struct assert_equality<V, V>
{
    static const bool not_equal_warning = 0;
};

constexpr const char* l[] = {"aa", "bb", "aa", 0};
static_assert(assert_equality<no_duplicates(l, 0), -1>::not_equal_warning == 0, "duplicates found");

Output from g++:

g++ -std=c++11 unique.cpp 
unique.cpp: In instantiation of ‘const char assert_equality<0, -1>::not_equal_warning’:
unique.cpp:29:57:   required from here
unique.cpp:20:53: warning: overflow in implicit constant conversion [-Woverflow]
unique.cpp:29:1: error: static assertion failed: duplicates found

The first template parameter (in this case 0) to 'assert_equality' tells you the fist position of a duplicate string.

Basile Starynkevitch · Answer 2 · 2014-08-20T19:39:32.423

I am not sure that it is easily doable using the standard C++ preprocessor (I guess that it is not). You might use some other preprocessor (e.g. GPP)

You could make it the other way: generate some X-macro "header" file from some other source (using e.g. a tiny awk script, which would verify the unicity). Then customize your build (e.g. add some rules to your Makefile) to run that generating script to produce the header file.

Alternatively, if you insist that processing being done inside the compiler, and if your compiler is a recent GCC, consider customizing GCC with MELT (e.g. by adding appropriate builtins or pragmas doing the job).

In the previous century, I hacked a small Emacs function to do a similar job (uniquely numbering error messages) within the emacs editor (renumbering some #define-s before saving the C file).

randomusername · Answer 3 · 2014-08-20T19:47:58.623

I am going to assume that something like this will work:

addMessage(1, "Message1")
addMessage(2, "Message1")

Or:

addMessage(1, "Message") /* transforms into "Message_1" */
addMessage(2, "Message_1") /* transforms into "Message_1_2" */

Because the C preprocessor expands tokens lazily and prohibits defining a macro from within another macro, it is impossible to save the results of executing one macro so that another macro can make use of it.

On the other hand, it is definitely possible to force uniqueness of symbols:

#define addMessage(N, MSG) const char *_error_message_##N (void) { return MSG; }

Or:

#define addMessage(N, MSG) const char *_error_message_##N (void) { return MSG "_" #N; }

Because during the link step, duplicate symbols with the name _error_message_NUMBER will trigger an error. And because it is a function, it cannot be used inside of another function without triggering an error.

It will only work inside one block (like for example in a function or one if block). I would like to be able to have unique identifiers in whole program, regardless where the call took place. — Paweł Jastrzębski, Aug 21 '14 at 07:34

Abhijit · Answer 4 · 2014-08-21T10:27:53.160

Assuming your compiler is still not C++11 compliant as you have not tagged appropiately. I am also assuming that you are not particular about the Error Message, its just that you want it to work. In which case, the following Macro Based Solution might work for you

#include <iostream>
#include <string>
#define ADD_MESSAGE(N, MSG) \
char * MSG;                   \
addMessage(N, #MSG); 


void addMessage(int n, std::string msg)
    {
    std::cout << msg << std::endl;
    }

int main() {
    ADD_MESSAGE(1, Message1); //OK 
    ADD_MESSAGE(2, Message2); //OK 
    ADD_MESSAGE(3, MessageN); //OK 
    ADD_MESSAGE(4, Message2); //Compile error, Message2 has already been used 
    };

Compile Output

prog.cpp: In function ‘int main()’:
prog.cpp:17:17: error: redeclaration of ‘char* Message2’
  ADD_MESSAGE(4, Message2); //Compile error, Message2 has already been used 
                 ^
prog.cpp:4:8: note: in definition of macro ‘ADD_MESSAGE’
 char * MSG;                   \
        ^
prog.cpp:15:17: error: ‘char* Message2’ previously declared here
  ADD_MESSAGE(2, Message2); //OK 
                 ^
prog.cpp:4:8: note: in definition of macro ‘ADD_MESSAGE’
 char * MSG;                   \
        ^

I am not sure about the actual version of standard that can be used in the project, but as far as I know we are not using C++11. I will check your solution tomorrow and give you feedback then if it worked for me. — Paweł Jastrzębski, Aug 20 '14 at 19:53
This fails for multi-word error messages, any error message with a C keyword in it, or any error message that doesn't compile as a valid C identifier. — randomusername, Aug 20 '14 at 20:10

randomusername · Answer 5 · 2014-08-20T21:23:11.993

If you don't care about large amounts of useless boiler plate then here's one that's entirely the preprocessor, so no worries about scope, and then checks that they are unique at program startup.

In a file:

#ifndef ERROR1
#define ERROR1 "1"
#endif
#ifndef ERROR2
#define ERROR2 "2"
#endif
...
#ifndef ERROR255
#define ERROR255 "255"
#endif

#include <assert.h>
#include <set>
#include <string>

class CheckUnique {
    CheckUnique() {
        std::set<std::string> s;
        static const char *messages = {
#if HAVE_BOOST
# include <boost/preprocessor.hpp>
# define BOOST_PP_LOCAL_LIMITS (1, 254)
# define BOOST_PP_LOCAL_MACRO(N) ERROR ## N,
# include BOOST_PP_LOCAL_ITERATE()
#else // HAVE_BOOST
             ERROR1,
             ERROR2,
             ...
#endif // HAVE_BOOST
             ERROR255
        };
        for (int i = 0; i < sizeof messages / sizeof *messages; i++) {
            if (s.count(messages[i]))
                assert(! "I found two error messages that were the same");
            else
                s.insert(messages[i]);
        }
     }
 };

 static CheckUnique check;

This file can then be #included at the end of each source file, or you can place it into a file of its own and include every single file that has a #define ERROR line in it. That way, as soon as the operating system loads the program, the constructor for check will run and throw the exception.

This also requires you to have access to the Boost.Preprocessor library (and it's header only so it's pretty easy to set up). Although if you can't use that, then you can just hard code the error macros as I have shown with the #if HAVE_BOOST block.

Most of the boiler plate here is pretty simple, so if you generated it with a program (like some sort of portable script) then it would make your life far easier, but it can still be done all in one shot.

I can't use boost in the project. – Paweł Jastrzębski Aug 20 '14 at 20:52 — Paweł Jastrzębski, Aug 20 '14 at 20:52

Implementing compile-time mechanism checking uniqueness of a string

5 Answers5

Linked