天天看點
傳回

STLport源代碼中的一個BUG

STLport是世界上使用最廣泛的開源STL實作，很多人通過學習STLport源代碼來了解STL中的實作細節。

STLport中的copy算法用于将一個容器中指定範圍的元素拷貝到另一個容器中。它是這麼實作的（原始代碼中有很多編譯宏隔離，為了表述友善，隻展開預編譯選項中有效的代碼，下同）：

// _algobase.h
template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) 
{
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  return _STLP_PRIV __copy_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter>::_Answer());
}

這裡是想在編譯期根據疊代器的不同類型，選擇調用不同的函數。_BothPtrType模闆判斷copy的參數是否都是指針類型，如果是，就會調用這個函數版本：

// _algobase.h
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
                              const __true_type& /*BothPtrType*/) 
{
  return _STLP_PRIV __copy_ptrs(__first, __last, __result,
                                _UseTrivialCopy(_STLP_VALUE_TYPE(__first, _InputIter),
                                                _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
}

這裡又做了一次分發，依據的是_UseTrivialCopy模闆。如果模闆傳回__true_type，就會調用下面這個函數：

// _algobase.h
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
                               const __true_type& /*IsOKToMemCpy*/) 
{
  return (_OutputIter)_STLP_PRIV __copy_trivial(__first, __last, __result);
}

inline void* __copy_trivial(const void* __first, const void* __last, void* __result) 
{
  size_t __n = (const char*)__last - (const char*)__first;
  return __n ? (void *)((char*)memmove(__result, __first, __n) + __n) : __result;
}

省事了，直接用memmove代替for循環來完成元素拷貝。這是STL的一大優點：根據參數的類型選擇性能最優的操作方式。

那麼，問題的關鍵在于怎樣判斷參數類型是可以直接用memmove拷貝的？首先，兩個參數必須都是原生指針，這在第一步由_BothPtrType模闆判斷。接下來，對于這兩個指針，用_UseTrivialCopy模闆判斷能否直接memmove。下面來看看_UseTrivialCopy模闆的實作：

// type_traits.h
template <class _Src, class _Dst>
inline _TrivialCopy<_Src, _Dst> _UseTrivialCopy(_Src*, _Dst*)
{ return _TrivialCopy<_Src, _Dst>(); }

template <class _Src, class _Dst>
struct _TrivialCopy {
  typedef typename _TrivialNativeTypeCopy<_Src, _Dst>::_Ret _NativeRet;    // 是否内置基本類型
  typedef typename __type_traits<_Src>::has_trivial_assignment_operator _Tr1;    // 是否需要調用operator=指派操作符重載
  typedef typename _AreCopyable<_Src, _Dst>::_Ret _Tr2;    // 兩個類型間是否允許拷貝
  typedef typename _Land2<_Tr1, _Tr2>::_Ret _UserRet;    // 綜合判斷，“與”
  typedef typename _Lor2<_NativeRet, _UserRet>::_Ret _Ret;    // 綜合判斷，“或”
  static _Ret _Answer() { return _Ret(); }
};

這個模闆的判斷分了幾個步驟：

1、對于元素為char，int，指針等等的内置類型，用_TrivialNativeTypeCopy模闆判斷能否采用memmove；

2、對于使用者自定義的類，結構體等類型，則綜合看是否有operator=和是否允許拷貝。

再詳細看看第一種情況：内置基本類型。_TrivialNativeTypeCopy模闆的實作是這樣的：

// type_traits.h
template <class _Src, class _Dst>
struct _TrivialNativeTypeCopy {
  typedef typename _IsPtr<_Src>::_Ret _Ptr1;    // Src是否是指針
  typedef typename _IsPtr<_Dst>::_Ret _Ptr2;    // Dst是否是指針
  typedef typename _Land2<_Ptr1, _Ptr2>::_Ret _BothPtrs;    // 是否Src和Dst都是指針
  typedef typename _IsCVConvertibleIf<_BothPtrs, _Src, _Dst>::_Ret _Convertible;    // 兩個指針能否自動轉換
  typedef typename _Land2<_BothPtrs, _Convertible>::_Ret _Trivial1;    // 都滿足則可以memmove

  typedef typename __bool2type<(sizeof(_Src) == sizeof(_Dst))>::_Ret _SameSize;    // 元素大小是否相等

  typedef typename _IsIntegral<_Src>::_Ret _Int1;    // Src是否是整型
  typedef typename _IsIntegral<_Dst>::_Ret _Int2;    // Dst是否是整型
  typedef typename _Land2<_Int1, _Int2>::_Ret _BothInts;    // 是否Src和Dst都是整型

  typedef typename _IsRational<_Src>::_Ret _Rat1;    // Src是否是有理數（浮點型）
  typedef typename _IsRational<_Dst>::_Ret _Rat2;    // Dst是否是有理數（浮點型）
  typedef typename _Land2<_Rat1, _Rat2>::_Ret _BothRats;    // 是否Src和Dst都是有理數（浮點型）

  typedef typename _Lor2<_BothInts, _BothRats>::_Ret _BothNatives;    // 都是整型或者都是有理數
  typedef typename _Land2<_BothNatives, _SameSize>::_Ret _Trivial2;    // 并且具有同樣的大小
  typedef typename _Lor2<_Trivial1, _Trivial2>::_Ret _Ret;
};

對于判斷步驟的說明我寫在了注釋中。顯然，對于元素類型都是整型或者浮點型的情況，用memmove操作是沒有疑問的。而對于元素類型是指針的情形，另外又調用了一個模闆_IsCVConvertibleIf來判斷能否直接memmove拷貝：

// type_traits.h
template <class _ArePtrs, class _Src, class _Dst>
struct _IsCVConvertibleIf
{ typedef typename _IsCVConvertible<_Src, _Dst>::_Ret _Ret; };

// type_manips.h
template <class _Src, class _Dst>
struct _IsCVConvertible {
  typedef _ConversionHelper<_Src, _Dst> _H;
  enum { value = (sizeof(char) == sizeof(_H::_Test(false, _H::_MakeSource()))) };
  typedef typename __bool2type<value>::_Ret _Ret;
};

template <class _Src, class _Dst>
struct _ConversionHelper {
  static char _Test(bool, _Dst);
  static char* _Test(bool, ...);
  static _Src _MakeSource();
};

這個實作可就相當的tricky了。代碼中定義了兩個同名的_Test函數，但參數類型不同。在傳入不同的參數時，編譯器會根據參數類型選擇用哪一個函數版本。如果_Src可以自動類型轉換為_Dst，那麼編譯器就會比對到char _Test(bool, _Dst)這個函數上去，傳回值就是char。是以可以根據函數調用的傳回值為char來推斷出_Src可以自動類型轉換為_Dst。真是高明！可問題是：隻要源指針能自動轉換為目标指針，就可以用memmove來拷貝指針嗎？

我在《萬惡的void*指針類型轉換》這篇部落格中，曾經指出C++中由于多重繼承的原因，在指針類型轉換時，指針的值也會跟着變化。在那篇文章裡我詳細分析了指針值會變化的原因，并警示了當有類型轉換時，絕不能暴力的使用原始指針值。

那麼顯然，當_Src指針轉換為_Dst指針時，其值可能會變，用memmove來拷貝可能出現錯誤！

是否真的如此？我寫了一個小程式來測試一下：

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class BaseA
{
public:
    int elementA;
    virtual void funcA()
    {
        cout << "I am funcA!" << endl;
    };
};

class BaseB
{
public:
    int elementB;
    virtual void funcB()
    {
        cout << "I am funcB!" << endl;
    };
};

class Derived : public BaseA, public BaseB
{
public:
    int elementD;
    virtual void funcA()
    {
        cout << "I am derived for funcA!" << endl;
    };
    virtual void funcB()
    {
        cout << "I am derived for funcB!" << endl;
    };
};

int _tmain(int argc, char* argv[])
{
    vector<Derived*> v_derived;
    vector<BaseB*> v_baseb(1);    // 容器大小為1

    Derived* derived = new Derived();
    v_derived.push_back(derived);
    copy(v_derived.begin(), v_derived.end(), v_baseb.begin());    // 好戲開始了！
    BaseB* baseb = derived;    // 這個是用來示範正确的指派結果，以作對比。

    cout << "derived pointer : " << v_derived.front() << endl
         << "copied base pointer : " << v_baseb.front() << endl
         << "cast base pointer : " << baseb << endl;

    baseb = v_baseb.front();
    baseb->funcB();
    return 0;
}

使用STLport的頭檔案，程式在VS2008下編譯通過，運作結果為：

derived pointer : 0x00112928

copyed base pointer : 0x00112928

cast base pointer : 0x00112930

I am derived for funcA!

Aha！末日來了！正常指派得到的指針和用copy算法得到的指針值不一樣！如果你用這個錯誤的值去調用虛函數，會調用到錯誤的函數上；如果用這個指針去通路成員，就會出現嚴重的運作時錯誤。當你碰到這個詭異的運作時錯誤時，會想得到這是STLport源代碼的BUG嗎？

除STLport外，其他版本的STL實作是否有問題呢？我迫不及待的嘗試了下VS2008自帶的STL，同樣的程式，運作結果如下：

derived pointer : 001F12D8

copyed base pointer : 001F12E0

cast base pointer : 001F12E0

I am derived for funcB!

謝天謝地！這回終于運作正确了。看來VS自帶的STL版本并沒有這種BUG。看看它的源代碼是怎麼實作的吧：

// xutility
template<class _InIt, class _OutIt>
inline
_IF_CHK(_OutIt) __CLRCALL_OR_CDECL copy(_InIt _First, _InIt _Last, _OutIt _Dest)
    {   // copy [_First, _Last) to [_Dest, ...)
    return (_Copy_opt(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
        _Iter_random(_First, _Dest), _Ptr_cat(_First, _Dest), _Range_checked_iterator_tag()));
    }

/* use _Ptr_cat_helper to determine the type of the pointer category */
template<class _T1, class _T2> inline
typename _Ptr_cat_helper<_T1, _T2>::_Ptr_cat __CLRCALL_OR_CDECL _Ptr_cat(_T1&, _T2&)
    {
    typename _Ptr_cat_helper<_T1, _T2>::_Ptr_cat _Cat;
    return (_Cat);
    }

template<class _Ty>
struct _Ptr_cat_helper<_Ty **, _Ty **>
    {   // return pointer category from pointer to pointer arguments
    typedef _Scalar_ptr_iterator_tag _Ptr_cat;    // 可以memmove
    };

template<class _T1,  class _T2>
struct _Ptr_cat_helper
    {
    typedef typename _Ptr_cat_with_checked_cat_helper<_T1, _T2,
        typename _Checked_iterator_category<_T1>::_Checked_cat,
        typename _Checked_iterator_category<_T2>::_Checked_cat>::_Ptr_cat _Ptr_cat;
    };

template<class _T1, class _T2, class _Checked_Cat1, class _Checked_Cat2>
struct _Ptr_cat_with_checked_cat_helper
    {
    typedef _Nonscalar_ptr_iterator_tag _Ptr_cat;    // 不可以memmove
    };

template<class _InIt, class _OutIt, class _InOutItCat>
inline
    _OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
        _InOutItCat, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
    {   // copy [_First, _Last) to [_Dest, ...), arbitrary iterators
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_Dest, ++_First)
        *_Dest = *_First;
    return (_Dest);
    }

template<class _InIt, class _OutIt, class _InOutItCat>
inline
    _OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
        _InOutItCat, _Scalar_ptr_iterator_tag, _Range_checked_iterator_tag)
    {   // copy [_First, _Last) to [_Dest, ...), pointers to scalars

    ptrdiff_t _Off = _Last - _First;    // NB: non-overlapping move
    // if _OutIt is range checked, this will make sure there is enough space for the memmove
    _OutIt _Result = _Dest + _Off;
    if (_Off > 0)
        _CRT_SECURE_MEMMOVE(&*_Dest, _Off * sizeof (*_First), &*_First, _Off * sizeof(*_First));
    return _Result;
    }

看得出來，VS的源代碼對于指針元素是否采用memmove的判斷标準是“兩個指針類型是否相同”，而不是“兩個指針能否自動轉換”。是以保證了功能的正确性。

經檢查，STLport中除了copy算法外，uninitialized_copy算法也有同樣的問題。這個BUG即使在最新的STLport 5.2.1版本中也存在，一旦被撞上，後果将是奇怪的運作時錯誤。作為一套全世界廣泛使用的開源代碼，存在這樣的問題實在不太應該。

對于STLport的使用者來說，我的建議是盡量避免在存在類型轉換的指針之間進行操作，至少避免對于有多重繼承的指針進行操作。最後吐槽一句：C++的多重繼承真是個大陷阱。

stlport copy 指針 多重繼承 c++
上一篇: 最新的stlport 在c++ builder 2007中安裝
下一篇: STLport開源庫的編譯和Vs2008下的配置

繼續閱讀