View Issue Details

IDProjectCategoryView StatusLast Update
0003534OpenFOAMBugpublic2020-08-18 14:13
Reporterpeltonp1 Assigned Tohenry  
PrioritynormalSeveritymajorReproducibilityalways
Status resolvedResolutionfixed 
PlatformGNU/LinuxOSUbuntuOS Version14.04
Fixed in Versiondev 
Summary0003534: The UList::reverse_iterator does not behave like a reverse iterator
DescriptionThe operator ++ and -- for the UList::reverse_iterator shifts the pointer to the wrong direction causing confusing behaviour. For instance, this disables the use of many of the std::algorithms (such as find_if, count_if, count etc) with reverse iterators since they run into an infinite loop. For a reverse iterator it would be more natural that the ++ operator shifts the pointer to the opposite direction as in the forward_iterator.

Steps To Reproduceusing namespace Foam;

    std::vector<int> v_std = {1, 10, 3, 5};
    DynamicList<int> v_of(4, int());

    std::copy(v_std.begin(), v_std.end(), v_of.begin());
    CHECK(v_of[1] == 10);

   //this prints the std::vector in a reverse order
    for (auto it = v_std.rbegin(); it != v_std.rend(); it++){
        Info << *it << endl;
    }
 
    //this is an infinite loop as the pointer is always shifted right
    for (auto it = v_of.rbegin(); it != v_of.rend(); it++){
        Info << *it << endl;
    }
    
    //this fails because of an infinite loop
    int number_of_ones = std::count(v_of.rbegin(), v_of.rend(), 1);
    Info << number_of_ones << endl;

Additional InformationFix: Return a std::reverse_iterator from the UList::rbegin/rend (and possibly some other containers)
TagsNo tags attached.

Activities

henry

2020-08-17 10:25

manager   ~0011459

> For a reverse iterator it would be more natural that the ++ operator shifts the pointer to the opposite direction as in the forward_iterator.

This doesn't seem logical to me, the -- operator should be used to reduce the pointer.

Note that I wrote the containers in OpenFOAM before STL was developed and while there has been some attempt to update them over the years to make them STL compliant this is a lot of work without funding and hence not complete.

> Fix: Return a std::reverse_iterator from the UList::rbegin/rend (and possibly some other containers)

Did you try this approach? It is not clear to me how it would work, could you send the version of UList you have developed which returns std::reverse_iterator?

peltonp1

2020-08-17 10:51

reporter   ~0011460

I understand that the actual operation ++ shifting pointer to left is counter intuitive, but imo it would be more safe to not provide a reverse iterator at all if it behaves like a forward iterator. I actually encountered this while trying to call std::find_if on a array I knew was sorted with a reverse iterator. I did not make any adjustments to UList, instead I call the algorithms like this:
///
///@brief Converts an iterator to a reverse iterator
///
///@tparam InputIt input iterator type
///@param i the iterator to convert
///@return std::reverse_iterator<Iter> a reverse iterator
/// with ++ and -- operators shifting to left and right, respectively.
///
template<class InputIt>
std::reverse_iterator<InputIt> make_reverse(InputIt i){
    return std::reverse_iterator<InputIt>(i);
}
auto rbegin = make_reverse(problems.end());
auto rend = make_reverse(problems.begin());
//... do stuff



For a fix in the UList, without trying, I guess just defining the reverse iterator as:

// STL reverse_iterator (not really -Petteri)

        //- Reverse iterator for reverse traversal of UList
       // typedef T* reverse_iterator; //old one
       typedef std::reverse_iterator<iterator> reverse_iterator; //new one

and implemeting the functions as:

template<class T>
inline typename Foam::UList<T>::reverse_iterator
Foam::UList<T>::rbegin()
{
    return reverse_iterator(end());
}

would fix the issue.

henry

2020-08-17 11:05

manager   ~0011461

Last edited: 2020-08-17 11:18

I just quickly tested your proposal and it works, many thanks for the idea. I will check the other components as well, const iterators rend etc.

henry

2020-08-17 11:38

manager   ~0011462

Last edited: 2020-08-17 11:42

I got const_reverse_iterator to work


        //- Reverse iterator for reverse traversal of constant UList
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;


template<class T>
inline typename Foam::UList<T>::const_reverse_iterator
Foam::UList<T>::crbegin() const
{
    return const_reverse_iterator(cend());
}

template<class T>
inline typename Foam::UList<T>::const_reverse_iterator
Foam::UList<T>::crend() const
{
    return const_reverse_iterator(cbegin());
}

template<class T>
inline typename Foam::UList<T>::const_reverse_iterator
Foam::UList<T>::rbegin() const
{
    return const_reverse_iterator(cend());
}

template<class T>
inline typename Foam::UList<T>::const_reverse_iterator
Foam::UList<T>::rend() const
{
    return const_reverse_iterator(cbegin());
}

peltonp1

2020-08-17 12:14

reporter   ~0011463

Very good! Thanks for the quick reply and patch.

henry

2020-08-17 14:06

manager   ~0011464

Try this:

commit 17c40d2aa57b1f922cdddc315d8cf3471c9bc600 (HEAD -> master, origin/master, origin/HEAD)
Author: Henry Weller <http://cfd.direct>
Date: Mon Aug 17 14:04:42 2020 +0100

    UList,FixedList: Updated reverse_iterators for STL compliance
    
    Resolves bug-report https://bugs.openfoam.org/view.php?id=3534

peltonp1

2020-08-18 11:13

reporter   ~0011465

I tested the fix and it appears to be working. The applications/test/List/Test-List.C I used is attached. It fails before the aforementioned commit^.
Test-List.C (6,370 bytes)   
/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     | Website:  https://openfoam.org
    \\  /    A nd           | Copyright (C) 2011-2020 OpenFOAM Foundation
     \\/     M anipulation  |
-------------------------------------------------------------------------------
License
    This file is part of OpenFOAM.

    OpenFOAM is free software: you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    for more details.

    You should have received a copy of the GNU General Public License
    along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.

Application
    Test-List

Description
    Simple tests and examples of use of List

See also
    Foam::List

\*---------------------------------------------------------------------------*/

#include <vector> //std::vector


#include "OSspecific.H"
#include "argList.H"
#include "wordReList.H"

#include "IOstreams.H"
#include "IStringStream.H"
#include "scalar.H"
#include "vector.H"
#include "ListOps.H"

using namespace Foam;

namespace ListTestDetail
{

template<class InputIt>
static void linearIncrement(InputIt first, InputIt last)
{

    int i = 1;
    for (; first != last; first++)
    {
        *first += 1;
        i++;
    }

}


template<class T>
static bool isEqual(const std::vector<T>& vStd, const List<T>& vOf)
{
    if (vStd.size() != static_cast<size_t>(vOf.size())) 
    {
        return false;
    }

    for (size_t i = 0; i < vStd.size(); ++i)
    {
        if (vStd[i] != vOf[i])
        {
            return false;
        }
    }
    return true;
}

} //namespace ListTestDetail

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
//  Main program:

int main(int argc, char *argv[])
{
    argList::noParallel();
    argList::addOption("reList", "reList");
    argList::addOption("wordList", "wordList");
    argList::addOption("stringList", "stringList");
    argList::addOption("float", "xx");
    argList::addBoolOption("flag");

    #include "setRootCase.H"

    List<vector> list1(IStringStream("1 ((0 1 2))")());
    Info<< "list1: " << list1 << endl;

    List<vector> list2
    {
        vector(0, 1, 2),
        vector(3, 4, 5),
        vector(6, 7, 8)
    };
    Info<< "list2: " << list2 << endl;

    list1.append(list2);
    Info<< "list1.append(list2): " << list1 << endl;

    Info<< findIndex(list2, vector(3, 4, 5)) << endl;

    list2.setSize(10, vector(1, 2, 3));
    Info<< "list2: " << list2 << endl;

    List<vector> list3(move(list2));
    Info<< "Transferred move" << endl;
    Info<< "list2: " << list2 << nl
        << "list3: " << list3 << endl;

    List<vector> list4
    {
        vector(0, 1, 2),
        vector(3, 4, 5),
        vector(6, 7, 8)
    };
    Info<< "list4: " << list4 << endl;

    List<vector> list5
    {
        {5, 3, 1},
        {10, 2, 2},
        {8, 1, 0}
    };
    Info<< "list5: " << list5 << endl;
    list5 =
    {
        {8, 1, 0},
        {5, 3, 1},
        {10, 2, 2}

    };
    Info<< "list5: " << list5 << endl;

    list4.swap(list5);
    Info<< "Swapped via the swap() method" << endl;
    Info<< "list4: " << list4 << nl
        << "list5: " << list5 << endl;

    List<vector> list6(list4.begin(), list4.end());
    Info<< "list6: " << list6 << endl;

    // Subset
    const labelList map{0, 2};
    List<vector> subList3(list3, map);
    Info<< "Elements " << map << " out of " << list3
        << " => " << subList3 << endl;

    wordReList reLst;
    wordList wLst;
    stringList sLst;


    scalar xxx(-1);

    if (args.optionFound("flag"))
    {
        Info<<"-flag:" << args["flag"] << endl;
    }

    if (args.optionReadIfPresent<scalar>("float", xxx))
    {
        Info<<"read float " << xxx << endl;
    }

    if (args.optionFound("reList"))
    {
        reLst = args.optionReadList<wordRe>("reList");
    }

    if (args.optionFound("wordList"))
    {
        wLst = args.optionReadList<word>("wordList");
    }

    if (args.optionFound("stringList"))
    {
        sLst = args.optionReadList<string>("stringList");
    }

    Info<< nl
        << "-reList: " << reLst << nl
        << "-wordList: " << wLst << nl
        << "-stringList: " << sLst << endl;





    ///Iterator tests

    std::vector<int> vStd = {1,2,3,4};
    List<int> vOf(4, int());
    std::copy(vStd.begin(), vStd.end(), vOf.begin());

    if (!ListTestDetail::isEqual(vStd, vOf))
    {
        Info << "std::copy fails for Foam::List" << endl;
    }    

    //non-constant forward iterators
    ListTestDetail::linearIncrement(vStd.begin(), vStd.end());
    ListTestDetail::linearIncrement(vOf.begin(), vOf.end());

    if (!ListTestDetail::isEqual(vStd, vOf))
    {
        Info << "Non const forward iterators not working for Foam::List." << endl;
    }    

    //non-constant reverse iterators
    ListTestDetail::linearIncrement(vStd.rbegin(), vStd.rend());
    ListTestDetail::linearIncrement(vOf.rbegin(), vOf.rend());

    if (!ListTestDetail::isEqual(vStd, vOf))
    {
        Info << "Non const reverse iterators not working for Foam::List." << endl;
    }  

    //constant forward iterators
    Info << "std::vector: ";
    for (auto it = vStd.cbegin(); it != vStd.cend(); it++)
    {
        Info << *it << " ";
    }
    Info << endl;

    Info << "Foam::List: ";
    for (auto it = vOf.cbegin(); it != vOf.cend(); it++)
    {
        Info << *it << " ";
    }
    Info << endl;


    //constant revese iterators
    Info << "std::vector (reverse): ";
    for (auto it = vStd.crbegin(); it != vStd.crend(); it++)
    {
        Info << *it << " ";
    }
    Info << endl;

    Info << "Foam::List (reverse): ";
    for (auto it = vOf.crbegin(); it != vOf.crend(); it++)
    {
        Info << *it << " ";
    }
    Info << endl;



    return 0;
}

// ************************************************************************* //

Test-List.C (6,370 bytes)   

henry

2020-08-18 14:13

manager   ~0011466

Resolved by commit 17c40d2aa57b1f922cdddc315d8cf3471c9bc600

Issue History

Date Modified Username Field Change
2020-08-17 08:59 peltonp1 New Issue
2020-08-17 10:25 henry Note Added: 0011459
2020-08-17 10:51 peltonp1 Note Added: 0011460
2020-08-17 11:05 henry Note Added: 0011461
2020-08-17 11:18 henry Note Edited: 0011461
2020-08-17 11:38 henry Note Added: 0011462
2020-08-17 11:42 henry Note Edited: 0011462
2020-08-17 12:14 peltonp1 Note Added: 0011463
2020-08-17 14:06 henry Note Added: 0011464
2020-08-18 11:13 peltonp1 File Added: Test-List.C
2020-08-18 11:13 peltonp1 Note Added: 0011465
2020-08-18 14:13 henry Assigned To => henry
2020-08-18 14:13 henry Status new => resolved
2020-08-18 14:13 henry Resolution open => fixed
2020-08-18 14:13 henry Fixed in Version => dev
2020-08-18 14:13 henry Note Added: 0011466