Mailing-List: contact dev-help@lucenenet.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucenenet.apache.org
From: Shad Storhaug <shad@shadstorhaug.com>
To: "Van Den Berghe, Vincent" <Vincent.VanDenBerghe@bvdinfo.com>,
	"dev@lucenenet.apache.org" <dev@lucenenet.apache.org>
Subject: RE: TestAgainstBrzozowski weirdness
Thread-Topic: TestAgainstBrzozowski weirdness
Thread-Index: AdKj4t5DZcp2Xe9pRTeW10lOX84ccAAYlfHA
Date: Fri, 24 Mar 2017 02:22:46 +0000
Message-ID: <4606B227B7AF19498F107C2C59CC9849B82B50F7@EX10DAG10-N1>
References: <B0097E2F0EB1484296C8F63879FC227D7BA26349@mail-mbx-a.bvdep.net>
In-Reply-To: <B0097E2F0EB1484296C8F63879FC227D7BA26349@mail-mbx-a.bvdep.net>
Accept-Language: en-US
Content-Language: en-US
Content-Type: multipart/alternative;
	boundary="_000_4606B227B7AF19498F107C2C59CC9849B82B50F7EX10DAG10N1_"
MIME-Version: 1.0
archived-at: Fri, 24 Mar 2017 02:22:13 -0000

--_000_4606B227B7AF19498F107C2C59CC9849B82B50F7EX10DAG10N1_
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

Vincent,

I put the GetHashCode() fix into both ValueList and ValueHashSet. You unwit=
tingly reverted it back to its original Java state.

Thanks,
Shad Storhaug (NightOwl888)

From: Van Den Berghe, Vincent [mailto:Vincent.VanDenBerghe@bvdinfo.com]
Sent: Thursday, March 23, 2017 9:57 PM
To: dev@lucenenet.apache.org
Cc: Shad Storhaug
Subject: TestAgainstBrzozowski weirdness

Here's a fun fact about TestAgainstBrzozowski.
This is the original test which fails every time:

                Automaton a =3D AutomatonTestUtil.RandomAutomaton(Random())=
;
                AutomatonTestUtil.MinimizeSimple(a);
                Automaton b =3D (Automaton)a.Clone();
                MinimizationOperations.Minimize(b);
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());

If we change the call to AutomatonTestUtil.MinimizeSimple(a) by Minimizatio=
nOperations.Minimize(a), the test succeeds:

                Automaton a =3D AutomatonTestUtil.RandomAutomaton(Random())=
;
                MinimizationOperations.Minimize(a);
                Automaton b =3D (Automaton)a.Clone();
                MinimizationOperations.Minimize(b);
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());

Before you say "big deal", if we replace the call to MinimizationOperations=
.Minimize(b) by AutomatonTestUtil.MinimizeSimple(b), the test fails every t=
ime:

                Automaton a =3D AutomatonTestUtil.RandomAutomaton(Random())=
;
                AutomatonTestUtil.MinimizeSimple(a);
                Automaton b =3D (Automaton)a.Clone();
                AutomatonTestUtil.MinimizeSimple(b);
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());

Not only that, but if we re-order the clone operation to be executed on the=
 un-minimized automaton (to make sure we really have 2 identical automatons=
) like this:

                Automaton a =3D AutomatonTestUtil.RandomAutomaton(Random())=
;
                Automaton b =3D (Automaton)a.Clone();
                AutomatonTestUtil.MinimizeSimple(a);
                AutomatonTestUtil.MinimizeSimple(b);
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());

... the test fails as well. This is contrary to what is claimed in the big =
giant comment.
To make sure that cloning works, this:

                Automaton a =3D AutomatonTestUtil.RandomAutomaton(Random())=
;
                Automaton b =3D (Automaton)a.Clone();
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());
                AutomatonTestUtil.MinimizeSimple(a);
                AutomatonTestUtil.MinimizeSimple(b);
                Assert.IsTrue(BasicOperations.SameLanguage(a, b));
                Assert.AreEqual(a.GetNumberOfStates(), b.GetNumberOfStates(=
));
                Assert.AreEqual(a.GetNumberOfTransitions(), b.GetNumberOfTr=
ansitions());

... never fails in the first 3 assertions. Always fails in one of the last =
ones.

Preliminary conclusion:  if AutomatonTestUtil.MinimizeSimple can't give the=
 same results for identical automatons, it's not a good basis for a test.
As to why... I searched for random factors in the AutomatonTestUtil.Minimiz=
eSimple, but found none.  It looks like the algorithm is deterministic.
The only strange thing is the GetHashCode() implementation on State: it's b=
ad form to define a hash code without an Equals method, especially if you'r=
e putting States in hash sets or dictionaries. But it seems like reference =
comparison is all that's needed, and since the hashcode is a different one =
for every instance, removing the GetHashCode method or adding the Equals me=
thod has no effect.

However, I can make the last 3 failing tests cited above work by correcting=
 a bug in ValueHashSet<T>.GetHashCode. The current definition is this:


        public override int GetHashCode()
        {
            int h =3D 0;
            var i =3D GetEnumerator();
            while (i.MoveNext())
            {
                T obj =3D i.Current;
                if (!EqualityComparer<T>.Default.Equals(obj, default(T)))
                {
                    h =3D HashHelpers.CombineHashCodes(h, obj.GetHashCode()=
);
                }
            }
            return h;
        }


This definition is wrong, since it relies on the incorrect assumption that =
sets containing identical elements will enumerate them in identical order. =
There is no order defined in a HashSet<T>, and if you have 2 sets to which =
you add items a after b in one, and b after a in another, the sets are iden=
tical but their enumerators will not necessarily be. The operation HashHelp=
ers.CombineHashCodes(h, obj.GetHashCode()) is noncommutative, causing equal=
 set to generate different hashcodes. Using:

        public override int GetHashCode()
        {
            int h =3D 0;
            foreach(var obj in this)
            {
                if (!EqualityComparer<T>.Default.Equals(obj, default(T)))
                {
                                      h +=3D obj.GetHashCode();
                }
            }
            return h;
        }


Will make the last 3 failing tests work correct. But not the original one!


More weirdness, I suppose.

Vincent

--_000_4606B227B7AF19498F107C2C59CC9849B82B50F7EX10DAG10N1_--