Refectoring of the Token class

[ollydbg]

We have many discussion on the link: BerliOS Developer: Patch Detail: 3494

The Token class has too many member variables. Some member variables are only used for specific type of Tokens, this waste a lot of memory.

My idea is:

We can create a Token class as a base class, and define some interface (use virtual function), then we can have many derived classes like:

Code

FunctionToken
ClassToken
TypedefToken
ClassTemplateToken
ClassTemplateSpecilicationToken
VariableToken
...

What's your opinion?

EDIT:
How can we do the type kind compare?
We have many code to check the m_TokenKind members, like:

Code

if ((curToken->m_ParentIndex == parent) && (curToken->m_TokenKind & kindMask))

or

Code

const Token* tk = tree->at(tree->TokenExists(token->m_BaseType, -1, tkPreprocessor | tkFunction));

Do we still need to put the m_TokenKind in the base class? so that every derived class has a m_TokenKind variable.

Or, do we need some kind of RTTI? See: Finding the type of an object in C++ - Stack Overflow
and
C++ polymorphism: Checking data type of sub class [duplicate]

[MortenMacFly]

Well first of all it hopefully won't conflict with Alphas work.

Using a bit mask and some consts/enums to compare is enough I'd say. If its feasible/doable, the specialisation could be stored into another "specialisation" bitmask. Thus they would become one variable.

So like:
((curToken->m_TokenKind & kindMask) && (curToken->m_TokenKindSpecial & kindMaskSpecial))

[oBFusCATed]

Do we still need to put the m_TokenKind in the base class? so that every derived class has a m_TokenKind variable.

No, you can make a virtual getTokenKind method.

Or, do we need some kind of RTTI? See: Finding the type of an object in C++ - Stack Overflow
and
C++ polymorphism: Checking data type of sub class [duplicate]

People that are proficient with OOP say that if you need dynamic_cast then you have problems with your design

[p2rkw]

People that are proficient with OOP say that if you need dynamic_cast then you have problems with your design

Tell it to llvm developers: llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates 
In my opinion rare data can be stored in separate hash maps as I did with docentation.

[oBFusCATed]

Tell it to llvm developers: llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates 

This doesn't make my statement invalid. dynamic_cast is useful tool, but should be used with care.

[ollydbg]

Hi, guys, here is the draft, can you give some comments?

Code

// the base class
class Token
{
friend class TokenTree;
public:
    Token(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~Token();

    virtual wxString DisplayName() const {return wxEmptyString};
    virtual TokenKind GetTokenKind() const {return tkUndefined};
    virtual wxString GetTokenKindString() const {return wxEmptyString};
    virtual wxString GetNamespace() const {return wxEmptyString};

    wxString GetAccessorKindString() const;
    wxString GetFilename() const;
    size_t GetTicket() const { return m_Ticket; }
    bool MatchesFiles(const TokenFileSet& files);
    TokenTree* GetTree() const { return m_TokenTree; }

    TokenKind    m_TokenKind;// See TokenKind class
    wxString     m_Name;     // Token's name, it can be searched in the TokenTree

    unsigned int m_FileIdx;       // File index in TokenTree
    unsigned int m_Line;          // Line index where the token was met, which is 0/1 based

    TokenScope   m_AccessKind;         // public? private? protected?

    bool         m_IsLocal;       // found in a local source file, otherwise in wxString buffer
    bool         m_IsTemp;        // local (automatic) variable
    bool         m_IsConst;       // the member method is const (yes/no)

    int          m_Index;         // current Token index in the tree
    int          m_ParentIndex;   // Parent Token index

    void*        m_UserData;      // custom user-data (the classbrowser expects it to be a pointer to a cbProject)

protected:
    TokenTree*   m_TokenTree;       // a pointer to TokenTree
    size_t       m_Ticket;          // This is used in classbrowser to avoid duplication
};

// a ScopeToken can have children, also some inherent information, such as class, a function
class ScopeToken: public Token
{
    ScopeToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~ScopeToken();

    bool AddChild(int childIdx);
    bool DeleteAllChildren();
    bool HasChildren() const { return !m_Children.empty(); }
    bool InheritsFrom(int idx) const;
    bool IsValidAncestor(const wxString& ancestor);

    TokenIdxSet  m_Children;        // if it is a class kind token, then it contains all the member tokens

    wxString     m_AncestorsString; // all ancestors comma-separated list
    TokenIdxSet  m_Ancestors;       // all the ancestors in the inheritance hierarchy
    TokenIdxSet  m_DirectAncestors; //the nearest ancestors

    TokenIdxSet  m_Descendants;     // all the descendants in the inheritance hierarchy

};

class VariableToken: public Token
{
friend class TokenTree;
public:
    VariableToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~VariableToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkVariable};
    virtual wxString GetTokenKindString() const {return _T("variable");};

    // some public functions

    wxString     m_FullType; // this is the full return value (if any): e.g. const wxString&
    wxString     m_BaseType; // this is what the parser believes is the actual return value: e.g. wxString
};

class FunctionToken: public ScopeToken
{
friend class TokenTree;
public:
    FunctionToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~FunctionToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkFunction};
    virtual wxString GetTokenKindString() const {return _T("function");};

     // some public functions
    wxString GetFormattedArgs() const; // remove all '\n'
    wxString GetStrippedArgs() const; // remove all default value

    wxString     m_FullType; // this is the full return value (if any): e.g. const wxString&
    wxString     m_BaseType; // this is what the parser believes is the actual return value: e.g. wxString

    wxString     m_Args;     // If it is a function Token, then this value is function arguments
                             // e.g.   (int arg1 = 10, float arg2 = 9.0)
                             // If it is an enumerator, then this is the assigned (inferred) value
    wxString     m_BaseArgs; // stripped arguments e.g. (int arg1, float arg2)

    unsigned int  m_ImplFileIdx;   // function implementation file index
    unsigned int  m_ImplLine;      // function implementation line index
    unsigned int  m_ImplLineStart; // if token is impl, opening brace line
    unsigned int  m_ImplLineEnd;   // if token is impl, closing brace line

    // To do: make them as enum, since they are exclusive
    bool          m_IsOperator;    // is operator overload function?
    bool          m_IsConstructor; // class constructor
    bool          m_IsDestructor;  // class destructor
};

class ClassToken: public ScopeToken
{
friend class TokenTree;
public:
    ClassToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~ClassToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkClass};
    virtual wxString GetTokenKindString() const {return _T("class");};

    // some public functions
    wxString GetImplFilename() const;

    unsigned int  m_ImplLineStart; // if token is impl, opening brace line
    unsigned int  m_ImplLineEnd;   // if token is impl, closing brace line
    bool          m_IsAnonymous;   // Is anonymous token? (e.g. unnamed struct or union)
};

class TypeDefineToken: public Token
{
friend class TokenTree;
public:
    TypeDefineToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~TypeDefineToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkTypedef};
    virtual wxString GetTokenKindString() const {return _T("typedef");};

    // some public functions

    wxString m_ReferenceType;
};

class MacroDefineToken: public Token
{
friend class TokenTree;
public:
    MacroDefineToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~MacroDefineToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkMacro};
    virtual wxString GetTokenKindString() const {return _T("macro");};

    // some public functions

    wxString m_Replacement;
};


class ClassTemplateToken: public ClassToken
{
friend class TokenTree;
public:
    ClassTemplateToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~ClassTemplateToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkClassTemplate};
    virtual wxString GetTokenKindString() const {return _T("class-template");};

    // some public functions

    wxString        m_TemplateParameter;
    wxArrayString   m_TemplateParameterList; //for a class template, this is the formal template argument list
};


class ScopeAliasToken: public Token
{
friend class TokenTree;
public:
    ScopeAliasToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~ScopeAliasToken();

    // some public functions

    wxString   m_TemplateAlias;
    int        m_ReferenceTokenIdx;
};

class FunctionTemplateToken: public FunctionToken
{
friend class TokenTree;
public:
    FunctionTemplateToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~FunctionTemplateToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkFunctionTemplate};
    virtual wxString GetTokenKindString() const {return _T("function-template");};

    // some public functions

    wxString        m_TemplateParameter; //formal parameter
    wxArrayString   m_TemplateParameterList;
};

class FunctionTemplateSpecializationToken: public FunctionTemplateToken
{
friend class TokenTree;
public:
    FunctionTemplateSpecializationToken(const wxString& name, unsigned int file, unsigned int line, size_t ticket);
    virtual ~FunctionTemplateSpecializationToken();
    virtual wxString DisplayName() const;
    virtual TokenKind GetTokenKind() const {return tkFunctionTemplateSpecialization};
    virtual wxString GetTokenKindString() const {return _T("function-template-specialization");};

    // some public functions

    wxString   m_TemplateArgument; // actual parameter
    std::map<wxString, wxString> m_TemplateMap;
};

I divide the template and template specialization, because sometimes, a template specialization has its own class definition lines.

One question remains:

The Token tree are generally std::vector<Token*>
So, once I get a pointer, I need to translate the base type pointer to derived type.

So, here is the proposed method:

Code

Token * tk = GetSomeTokenFromTokenTree();
If (tk->GetTokenKind == tkFunction)
{
    TokenFunctionToken * tk1 = (TokenFunctionToken *)tk;
    tk->SomeFunctionOfFunctionToken();
}

BTW: I don't know how llvm's method did, I have little knowledge about advanced C++.

[oBFusCATed]

Code

    virtual wxString DisplayName() const {return wxEmptyString};
    virtual TokenKind GetTokenKind() const {return tkUndefined};
    virtual wxString GetTokenKindString() const {return wxEmptyString};
    virtual wxString GetNamespace() const {return wxEmptyString};

These functions look inefficient, why don't you make them return const wxString& and be pure virtual?

BTW: I don't know how llvm's method did, I have little knowledge about advanced C++.

Look at their code, I doubt it is that complex.
But if you need dynamic_cast only in CC plugin it is safe to use it instead of some home-made solution.
Just keep in mind that dynamic_cast won't work across dlopened shared libraries.

And one final note:
Is this change needed now?
Because, if you do it in trunk it will cause quite a lot of pain for merging the cc_interface branch back to trunk.
So either post pone it for after the merge or communicate with Alpha if it is OK to apply it in his branch.
Or even fork his branch and work on your fork, then use rebase to move your changes on top of his branch when he pushes commits.

[ollydbg]

Code

    virtual wxString DisplayName() const {return wxEmptyString};
    virtual TokenKind GetTokenKind() const {return tkUndefined};
    virtual wxString GetTokenKindString() const {return wxEmptyString};
    virtual wxString GetNamespace() const {return wxEmptyString};

These functions look inefficient, why don't you make them return const wxString& and be pure virtual?

Will do it, thanks.

BTW: I don't know how llvm's method did, I have little knowledge about advanced C++.

Look at their code, I doubt it is that complex.
But if you need dynamic_cast only in CC plugin it is safe to use it instead of some home-made solution.
Just keep in mind that dynamic_cast won't work across dlopened shared libraries.

Do we need a dynamic_cast here in my code snippet?

Code

Token * tk = GetSomeTokenFromTokenTree();
If (tk->GetTokenKind == tkFunction)
{
    TokenFunctionToken * tk1 = (TokenFunctionToken *)tk;
    tk->SomeFunctionOfFunctionToken();
}

Here, dynamic_cast and static_cast are the same, right? I think I will have some code like:

Code

Token * tk = GetSomeTokenFromTokenTree();
if (tk->GetTokenKind() == tkFunction)
{
    TokenFunctionToken * tk1 = (TokenFunctionToken *)tk;
    tk->SomeFunctionOfFunctionToken();
}
else if (tk->GetTokenKind() == tkClass)
{
    TokenClassToken * tk1 = (TokenClassToken *)tk;
    tk->SomeFunctionOfClassToken();
}
else if (tk->GetTokenKind() == tkClass)
{

}
else if ...

Is it OK that we have a lot of if-else clause?

And one final note:
Is this change needed now?
Because, if you do it in trunk it will cause quite a lot of pain for merging the cc_interface branch back to trunk.
So either post pone it for after the merge or communicate with Alpha if it is OK to apply it in his branch.
Or even fork his branch and work on your fork, then use rebase to move your changes on top of his branch when he pushes commits.

No hurry, I will avoid the pain by your suggestion, I think I can not finish the refactoring soon. If the draft code snippet get approved by your guys, then I can start coding, I think it will take some months.

[oBFusCATed]

Is it OK that we have a lot of if-else clause?

Probably you need to have a virtual function in your base class for this case.
You can use a switch statement, but as far as I know this is why people want to use inheritance - to have less cases where they need switches.
I guess you need to read one-two-three articles on clean OOP design, to see what options you have with classes.

I can't comment on the usefulness of some design, when I don't know the old design.
My comments are just general in this case.

btw: Please don't use C style cases. Try to use only C++ (static_cast, const_cast, reinterpret_cast, dynamic_cast, they are generally safer).

[ollydbg]

Is it OK that we have a lot of if-else clause?

Probably you need to have a virtual function in your base class for this case.
You can use a switch statement, but as far as I know this is why people want to use inheritance - to have less cases where they need switches.
I guess you need to read one-two-three articles on clean OOP design, to see what options you have with classes.

Thanks, I generally know this idea, by adding a virtual function in the base class, I can wrap all the if-else clause's contents to every virtual function of the derived class, thus avoid the if-else or switch statements. I will read some articles about this idea.

btw: Please don't use C style cases. Try to use only C++ (static_cast, const_cast, reinterpret_cast, dynamic_cast, they are generally safer).

Ok, will do it.

[blauzahn]

I agree with oBFusCATed.

a general advice: Inheritance should be used only, if you really need polymorphic use -- that is:
runtime dispatch via virtual functions. This helps to avoid having "if" or "switch"
at all places you use the things, which is error prone and fragile, especially in maintenance.

I usually try to reduce the the base class to have one single responsability: Providing
a pure interface that expresses a concept of polymorphic use. That means:
neither any implementation nor any data-member. Think of "design
by contract". All implementors have to follow the Liskov-Substitution principle as soon as
the instance is created. Usually, you have a factory method, that is the only place which
knows the distinction and decides, what instance to create properly and give back to the caller.

In the proposed design, the caller still has to know all the types and therefore
still forces you to use "if" or "switch" and casts, which is unfortunate.

The fact, that the subclasses have a ctor which all take the same arguments is another hint,
that they stand for a missing concept (class) which wants to be born. Perhaps
the subclasses should HAVE one data-member of this kind instead of BEING them in form
of several data-members in the base class.

Or is it even better to split the class into a) token and b) TreeItem
because these seem to be separate ideas and can help to separate things that
may have to remain mutable from things that can become const.

Do you know this stuff?
* Talks, given by Bjarne Stroustrup and Sean Parent at Going Native Conference GN2013,
  see also the Panel Videos
* book by Kent Beck: "Implementation Patterns"
* books by Robert C. Martin: "Clean Code", "Agile Software Development"
* podcast on hanselminutes.com: Robert C. Martin: SOLID-principle
* book by Michael Feathers: "Working Effectively with Legacy Code"

[Alpha]

My plan with the cc_interface branch is to try to stabilize all current implemented features, and port over the Fortran plugin.  Then try for a merge.  (I am realizing that if I wait until everything I wanted to add is complete, this branch will be a very long time in coming.)

(Changing the structure of the Token class will require modifications in the implementation of CC's interface functions, but CCManager should not require any changes.)

[ollydbg]

I agree with oBFusCATed.

a general advice: Inheritance should be used only, if you really need polymorphic use -- that is:
runtime dispatch via virtual functions. This helps to avoid having "if" or "switch"
at all places you use the things, which is error prone and fragile, especially in maintenance.

Thanks for the comments.

I usually try to reduce the the base class to have one single responsability: Providing
a pure interface that expresses a concept of polymorphic use. That means:
neither any implementation nor any data-member. Think of "design
by contract". All implementors have to follow the Liskov-Substitution principle as soon as
the instance is created. Usually, you have a factory method, that is the only place which
knows the distinction and decides, what instance to create properly and give back to the caller.

In the proposed design, the caller still has to know all the types and therefore
still forces you to use "if" or "switch" and casts, which is unfortunate.

OK, Thanks. I still have a question. For example, I have a Token (base class), and some derived class, like ScopeToken, ClassToken, FunctionToken, ClassTemplateToken..... Note: Here the name "Token" just means "Symbol" in the sense of "symbol table".
Some class has its special member functions, like: FunctionToken and FunctionTemplateToken class may have some functions to handle arguments, so do we need to collect all the interface to the abstract base class? I mean the base class may have a pure virtual function named XXXArguments()? I need to store all the Token* pointers in the TokenTree(yes, it is the symbol table), If I want to avoid the use of "if" or "switch", the only way I can do is to extract all the functions in the base class?

The fact, that the subclasses have a ctor which all take the same arguments is another hint,
that they stand for a missing concept (class) which wants to be born. Perhaps
the subclasses should HAVE one data-member of this kind instead of BEING them in form
of several data-members in the base class.

Or is it even better to split the class into a) token and b) TreeItem
because these seem to be separate ideas and can help to separate things that
may have to remain mutable from things that can become const.

Sorry, I don't understand much well, can you give more details? Thanks.

Do you know this stuff?
* Talks, given by Bjarne Stroustrup and Sean Parent at Going Native Conference GN2013,
  see also the Panel Videos
* book by Kent Beck: "Implementation Patterns"
* books by Robert C. Martin: "Clean Code", "Agile Software Development"
* podcast on hanselminutes.com: Robert C. Martin: SOLID-principle
* book by Michael Feathers: "Working Effectively with Legacy Code"

I just watch the lecture by Bjarne Stroustrup, very nice. But I found that most books are using Java as examples in the book, not C++.

[oBFusCATed]

If I want to avoid the use of "if" or "switch", the only way I can do is to extract all the functions in the base class?

But then you'll end with a class that looks like the current Token class.
The new token class must have only common stuff in it.
The idea is to minimize the usage of switches, but most of the time you can't remove them all.

One option is to use http://en.wikipedia.org/wiki/Visitor_pattern but I always fill guilty when I use it.
Another option is to find all switch statements and then define a single method in the base class for each switch...

[blauzahn]

But then you'll end with a class that looks like the current Token class.

Yes. And if it works now, there is no need to hurry for a change. Let the ideas ripen.

the base class may have a pure virtual function named XXXArguments()?

No. The methods should get the necessary things inseparable from the call. Just ordinary arguments.
That makes it easy to understand and to use it right and harder to do it wrong. And it minimizes
state and side effects.

I need to store all the Token* pointers in the TokenTree

...but be aware of who owns them, who deletes them, even in case of exceptions. That's why
alternatives to raw pointers may be an option (see GN2013 Sean Parent). No leaks! No
dangling pointer!

Sorry, I don't understand much well, can you give more details?

e.g. separate the functionality/data in the existing Token Class that does not have to be coupled.
(strive for loose coupling, high cohesion, single responsabilty etc.)
a) class TokenLocation{ wxString name, unsigned int file, unsigned int line, size_t ticket };
b) class TokenTreeItem{
       bool AddChild(int childIdx);
       bool DeleteAllChildren();
       bool HasChildren() const;
   }

class Token
{
  ...
   TokenLocation m_Location; // naming needs improvement
   TokenTreeItem m_TreeItem;
};

If the interface remains the same, all changes are simply implementation details. The code
could be improved by applying small refactoring steps without affecting client code.

But I found that most books are using Java as examples in the book, not C++.

Yes. And with C++ you are not limited to "true OO-Style". Nevertheless, you could
learn a lot of language independant things from the text. The code-samples are
general enough and easy to understand for a C++-programmer. Just do not to transfer
everything blindly to C++. E.g: in C++, the default is value semantics whereas in
Java and C#, it is reference semantics. That makes quite a difference. Exploit this in
your design (using constness, immutability, minimized state, especially shared one etc).