Selbst große Mathematiker machen Fehler

Wir wissen, dass Mathematik eine Wissenschaft der Präzision ist. Können wir dasselbe über GeoGebra sagen, eine interaktive Mathematik-Lernsoftware? Lassen Sie uns den Quellcode des Projekts mit PVS-Studio analysieren!

Einführung

Erinnern Sie sich noch daran, wie Sie an der Universität Informatik gelernt haben? All diese Matrix- und Vektormultiplikationen, Polynomgleichungen, Interpolationen, Extrapolationen ... Was wäre, wenn wir uns diese gruseligen Formeln in einem echten Projekt ansehen und nicht in einem anderen Laborbericht? Was wäre, wenn wir in einer solchen Codebasis nach Problemen suchen würden? Ich schlage vor, PVS-Studio zu starten und Mathematiklehrbücher abzustauben. Warum Lehrbücher? Lass es mich dir zeigen.

Mathe-Herausforderungen

Eine der größten Herausforderungen bei der Untersuchung des Quellcodes solcher Programme besteht darin, zu verstehen, was vor sich geht. Bei der Durchsicht des Analyseberichts hatten wir Fragen, ob die Warnungen auf echte Probleme hinweisen.

Schauen wir uns das folgende Fragment an:

@Override
public void compute() {
  ....
  if (cumulative != null && cumulative.getBoolean()) {
    ....
  } else {
    ....
    branchAtoMode = fv.wrap().subtract(a).multiplyR(2)
      .divide(bEn.subtract(a).multiply(modeEn.subtract(a)));
    branchModeToB = fv.wrap().subtract(b).multiplyR(2)                
      .divide(bEn.subtract(a).multiply(modeEn.subtract(b)));
      rightBranch = new MyDouble(kernel, 0);
  }
  ....
}

Wir erhalten die folgende PVS-Studio-Warnung:

V6072 Es wurden zwei ähnliche Codefragmente gefunden. Möglicherweise ist dies ein Tippfehler und die Variable „b“ sollte anstelle von „a“ verwendet werden. AlgoTriangularDF.java 145, AlgoTriangularDF.java 146, AlgoTriangularDF.java 147, AlgoTriangularDF.java 148

Ist es wirklich ein Tippfehler? Nach einer kurzen Recherche und nachdem wir die richtige Formel gefunden haben, können wir sagen, dass alles richtig geschrieben ist.

Das Codefragment wertet die Dreiecksverteilung aus, also die Wahrscheinlichkeitsdichtefunktion (PDF) für diese Verteilung. Wir haben die Formel gefunden:

Jetzt gehen wir den Code durch.

Hier ist* fv* eine Funktionsvariable. wrap gibt wrapper zurück und dann werden die notwendigen mathematischen Operationen ausgeführt. Es ist interessant festzustellen, dass es sowohl die Methoden multiply als auch multiplyR gibt. Bei der zweiten Methode steht R für richtig und vertauscht Operanden, da die Multiplikation nicht immer kommutativ ist.

Das Ergebnis des zweiten Ausdrucks wird also in branchAToMode geschrieben, und der vierte Ausdruck wird in branchModeToB geschrieben.

Uns ist außerdem aufgefallen, dass in branchModeToB die Vorzeichen für Zähler und Nenner geändert wurden. Wir erhalten den folgenden Ausdruck:

Der Ausdruckswert hat sich nicht geändert.

Also haben wir unsere mathematischen Kenntnisse aufgefrischt, um einige der Warnungen zu verstehen, die wir erhalten haben. Es ist nicht schwer zu erkennen, ob ein echter Fehler im Code vorliegt, aber es ist schwer zu verstehen, was er stattdessen hier bedeuten soll.

Fehler

Codesegment verloren

Lass uns einfach beginnen und uns die folgende Methode ansehen:

private void updateSide(int index, int newBottomPointsLength) {
  ....
  GeoSegmentND[] s = new GeoSegmentND[4];
  GeoSegmentND segmentBottom = outputSegmentsBottom.getElement(index);
  s[0] = segmentBottom;
  s[1] = segmentSide1;
  s[2] = segmentSide2;
  s[2] = segmentSide3;
  polygon.setSegments(s);
  polygon.calcArea();
}

Wir sehen, dass jemand vergessen hat, s[2] durch s[3] zu ersetzen. Der letzte Zeileneffekt ist in seiner ganzen Brillanz. Es ist der legendäre und allzu häufige Fehler beim Kopieren und Einfügen. Infolgedessen fehlt das vierte Array-Element und ist null!

V6033 Ein Artikel mit demselben Schlüssel „2“ wurde bereits geändert. AlgoPolyhedronNetPrism.java 376, AlgoPolyhedronNetPrism.java 377

Was ist mit Werten?

Versuchen Sie nun, das Problem im folgenden Codeausschnitt zu erkennen:

static synchronized HashMap<String, String> getGeogebraMap() {
  ....
  geogebraMap.put("−", "-");
  geogebraMap.put("⊥", "# ");
  geogebraMap.put("∼", "~ ");
  geogebraMap.put("′", "# ");
  geogebraMap.put("≤", Unicode.LESS_EQUAL + "");
  geogebraMap.put("&ge;", Unicode.GREATER_EQUAL + "");
  geogebraMap.put("&infin;", Unicode.INFINITY + "");
  ....
  geogebraMap.put("∏", "# ");
  geogebraMap.put("&Product;", "# ");
  geogebraMap.put("〉", "# ");
  geogebraMap.put("&rangle;", "# ");
  geogebraMap.put("&rarr;", "# ");
  geogebraMap.put("&rArr;", "# ");
  geogebraMap.put("&RightAngleBracket;", "# ");
  geogebraMap.put("&rightarrow;", "# ");
  geogebraMap.put("&Rightarrow;", "# ");
  geogebraMap.put("&RightArrow;", "# ");
  geogebraMap.put("&sdot;", "* ");
  geogebraMap.put("∼", "# ");
  geogebraMap.put("∝", "# ");
  geogebraMap.put("&Proportional;", "# ");
  geogebraMap.put("&propto;", "# ");
  geogebraMap.put("⊂", "# ");
  ....
  return geogebraMap;
}

Was für eine grandiose Aussicht! Es ist eine Freude, es zu lesen, und dies ist nur ein kleiner Teil, da diese Methode in Zeile 66 beginnt und in Zeile 404 endet. Der Analysator gibt 50 Warnungen vom Typ V6033 aus. Werfen wir einen kurzen Blick auf eine dieser Warnungen:

V6033 Ein Artikel mit demselben Schlüssel „∼“ wurde bereits hinzugefügt. MathMLParser.java 229, MathMLParser.java 355

Lassen Sie uns die überflüssigen Fragmente entfernen und uns die Ausdrücke ansehen, auf die sich die Warnung bezieht:

geogebraMap.put("∼", "~ ");
....
geogebraMap.put("∼", "# ");

Es ist jedoch interessant. Wie groß ist der Abstand zwischen den Methodenaufrufen? Es gibt 126 Zeilen. Nun, viel Glück beim manuellen Finden eines solchen Fehlers!

Bei den meisten handelt es sich um Duplikate in Schlüssel und Wert. Allerdings ähneln einige Fälle dem obigen Beispiel, in denen Entwickler den Wert mit einem anderen überschreiben. Welches sollten wir verwenden?

Kreise oder Ellipsen

@Override
protected boolean updateForItSelf() {
  ....
  if (conic.getType() == GeoConicNDConstants.CONIC_SINGLE_POINT) {
    ....
  } else {
    if (visible != Visible.FRUSTUM_INSIDE) {
      ....
      switch (conic.getType()) {
        case GeoConicNDConstants.CONIC_CIRCLE:
          updateEllipse(brush);                     // <=
          break;
        case GeoConicNDConstants.CONIC_ELLIPSE:
          updateEllipse(brush);                     // <=
          break;
        case GeoConicNDConstants.CONIC_HYPERBOLA:
          updateHyperbola(brush);
          break;
        case GeoConicNDConstants.CONIC_PARABOLA:
          updateParabola(brush);
          break;
        case GeoConicNDConstants.CONIC_DOUBLE_LINE:
          createTmpCoordsIfNeeded();
          brush.segment(tmpCoords1.setAdd3(m, tmpCoords1.setMul3(d, minmax[0])),
              tmpCoords2.setAdd3(m, tmpCoords2.setMul3(d, minmax[1])));
          break;
        case GeoConicNDConstants.CONIC_INTERSECTING_LINES:
        case GeoConicNDConstants.CONIC_PARALLEL_LINES:
          updateLines(brush);
          break;
        default:
          break;
      }
    }
  }
}

Die Methode für die Ellipse wird sowohl für die Ellipse als auch für den Kreis aufgerufen. Tatsächlich können wir davon ausgehen, dass dies in Ordnung ist, da ein Kreis auch eine Ellipse ist. Allerdings verfügt die Klasse auch über die Methode updateCircle. Was soll es dann sein? Lasst uns etwas tiefer in die Materie eintauchen.

Alles findet in der Klasse DrawConic3D statt. Hier sind die Methoden für die Ellipse und den Kreis:

protected void updateCircle(PlotterBrush brush) {
  if (visible == Visible.CENTER_OUTSIDE) {
    longitude = brush.calcArcLongitudesNeeded(e1, alpha,
          getView3D().getScale());
    brush.arc(m, ev1, ev2, e1, beta - alpha, 2 * alpha, longitude);
  } else {
    longitude = brush.calcArcLongitudesNeeded(e1, Math.PI,
          getView3D().getScale());
    brush.circle(m, ev1, ev2, e1, longitude);
  }
}
protected void updateEllipse(PlotterBrush brush) {
  if (visible == Visible.CENTER_OUTSIDE) {
    brush.arcEllipse(m, ev1, ev2, e1, e2, beta - alpha, 2 * alpha);
  } else {
    brush.arcEllipse(m, ev1, ev2, e1, e2, 0, 2 * Math.PI);
  }
}

Well... It doesn't give that much confidence. The method bodies are different, but nothing here indicates that we risk displaying unacceptable geometric objects if the method is called incorrectly.

Could there be other clues? A whole single one! The updateCircle method is never used in the project. Meanwhile, updateEllipse is used four times: twice in the first fragment and then twice in DrawConicSection3D, the inheritor class of* DrawConic3D*:

@Override
protected void updateCircle(PlotterBrush brush) {
  updateEllipse(brush);
}

@Override
protected void updateEllipse(PlotterBrush brush) {
  // ....
  } else {
    super.updateEllipse(brush);
  }
}

This updateCircle isn't used, either. So, updateEllipse only has a call in its own override and in the fragment where we first found updateForItSelf. In schematic form, the structure looks like as follows:

On the one hand, it seems that the developers wanted to use the all-purpose updateEllipse method to draw a circle. On the other hand, it's a bit strange that DrawConicSection3D has the updateCircle method that calls updateEllipse. However, updateCircle will never be called.

It's hard to guess what the fixed code may look like if the error is actually in the code. For example, if updateCircle needs to call updateEllipse in DrawConicSection3D, but DrawConic3D needs a more optimized algorithm for the circle, the fixed scheme might look like this:

So, it seems that developers once wrote updateCircle and then lost it, and we may have found its intended "home". Looks like we have discovered the ruins of the refactoring after which the developers forgot about the "homeless" method. In any case, it's worth rewriting this code to make it clearer so that we don't end up with so many questions.

All these questions have arisen because of the PVS-Studio warning. That's the warning, by the way:

V6067 Two or more case-branches perform the same actions. DrawConic3D.java 212, DrawConic3D.java 215

Order of missing object

private void updateOrdering(GeoElement geo, ObjectMovement movement) {
  ....
  switch (movement) {
    ....
    case FRONT:
      ....
      if (index == firstIndex) {
        if (index != 0) { 
          geo.setOrdering(orderingDepthMidpoint(index));
        }
        else { 
          geo.setOrdering(drawingOrder.get(index - 1).getOrdering() - 1);
        }
      }
    ....
  }
  ....
}

We get the following warning:

V6025 Index 'index - 1' is out of bounds. LayerManager.java 393

This is curious because, in the else block, the index variable is guaranteed to get the value 0. So, we pass -1 as an argument to the get method. What's the result? We catch an IndexOutOfBoundsException.

Triangles

@Override
protected int getGLType(Type type) {
  switch (type) {
  case TRIANGLE_STRIP:
    return GL.GL_TRIANGLE_STRIP;
  case TRIANGLE_FAN:
    return GL.GL_TRIANGLE_STRIP;     // <=
  case TRIANGLES:
    return GL.GL_TRIANGLES;
  case LINE_LOOP:
    return GL.GL_LINE_LOOP;
  case LINE_STRIP:
    return GL.GL_LINE_STRIP;
  }

  return 0;
}

The code is new, but the error is already well-known. It's quite obvious that GL.GL_TRIANGLE_STRIP should be GL.GL_TRIANGLE_FAN instead*.* The methods may be similar in some ways, but the results are different. You can read about it under the spoiler.

V6067 Two or more case-branches perform the same actions. RendererImplShadersD.java 243, RendererImplShadersD.java 245

To describe a series of triangles, we need to save the coordinates of the three vertices of each triangle. Thus, given N triangles, we need the saved 3N vertices. If we describe a polyhedral object using a polygon mesh, it's important to know if the triangles are connected. If they are, we can use the Triangle Strip or the Triangle Fan to describe the set of triangles using N + 2 vertices.

We note that the Triangle Fan has been removed in Direct3D 10. In OpenGL 4.6, this primitive still exists.

The Triangle Fan uses one center vertex as common, as well as the last vertex and the new vertex. Look at the following example:

To describe it, we'd need the entry (A, B, C, D, E, F, G). There are five triangles and seven vertices in the entry.

The Triangle Strip uses the last two vertices and a new one. For instance, we can create the image below using the same sequence of vertices:

Therefore, if we use the wrong primitive, we'll get dramatically different results.

Overwritten values

public static void addToJsObject(
JsPropertyMap<Object> jsMap, Map<String, Object> map) {
  for (Entry<String, Object> entry : map.entrySet()) {
    Object object = entry.getValue();
      if (object instanceof Integer) {
        jsMap.set(entry.getKey(), unbox((Integer) object));
      } if (object instanceof String[]) {                          // <=
        JsArray<String> clean = JsArray.of();
        for (String s: (String[]) object) {
          clean.push(s);
        }
        jsMap.set(entry.getKey(), clean);
    } else {                                                       // <=
      jsMap.set(entry.getKey(), object);                           // <=
    }
  }
}

If we don't look closely, we may not notice the issue right away. However, let's speed up and just check the analyzer message.

V6086 Suspicious code formatting. 'else' keyword is probably missing. ScriptManagerW.java 209

Finally, a more interesting bug is here. The object instanceof String[] check will occur regardless of the result of object instanceof Integer. It may not be a big deal, but there's also the else block that will be executed after a failed check for String[]. As the result, the jsMap value by entry.getKey() will be overwritten if the object was Integer.

There's another similar case, but the potential consequences are a little harder to understand:

public void bkspCharacter(EditorState editorState) {
  int currentOffset = editorState.getCurrentOffsetOrSelection();
  if (currentOffset > 0) {
    MathComponent prev = editorState.getCurrentField()
        .getArgument(currentOffset - 1);
    if (prev instanceof MathArray) {
      MathArray parent = (MathArray) prev;
      extendBrackets(parent, editorState);
    } if (prev instanceof MathFunction) {                          // <=
      bkspLastFunctionArg((MathFunction) prev, editorState);
    } else {                                                       // <=
      deleteSingleArg(editorState);
    }
  } else {
    RemoveContainer.withBackspace(editorState);
  }
}

V6086 Suspicious code formatting. 'else' keyword is probably missing. InputController.java 854

Almost correct

Do you often have to write many repetitious checks? Are these checks prone to typos? Let's look at the following method:

public boolean contains(BoundingBox other) {
  return !(isNull() || other.isNull()) && other.minx >= minx
      && other.maxy <= maxx && other.miny >= miny
      && other.maxy <= maxy;
}

V6045 Possible misprint in expression 'other.maxy <= maxx'. BoundingBox.java 139

We find a typo, we fix it. The answer is simple, there should be other.maxx <= maxx.

Mixed up numbers

public PointDt[] calcVoronoiCell(TriangleDt triangle, PointDt p) {
  ....
  // find the neighbor triangle
  if (!halfplane.next_12().isHalfplane()) {
    neighbor = halfplane.next_12();
  } else if (!halfplane.next_23().isHalfplane()) {
    neighbor = halfplane.next_23();
  } else if (!halfplane.next_23().isHalfplane()) { // <=
    neighbor = halfplane.next_31();
  } else {
    Log.error("problem in Delaunay_Triangulation");
    // TODO fix added by GeoGebra
    // should we do something else?
    return null;
  }
  ....
}

Let's see the warning:

V6003 The use of 'if (A) {...} else if (A) {...}' pattern was detected. There is a probability of logical error presence. DelaunayTriangulation.java 678, DelaunayTriangulation.java 680

We don't even need to figure out what happens to half-planes, because it's clear that the !halfplane.next_31().isHalfplane() check is missing.

Wrong operation

public static ExpressionNode get(
    ExpressionValue left, ExpressionValue right, 
    Operation operation, FunctionVariable fv, 
    Kernel kernel0
) {
  ....
  switch (operation) {
    ....
    case VEC_FUNCTION:
      break;
    case ZETA:
      break;
    case DIRAC:
      return new ExpressionNode(kernel0, left, Operation.DIRAC, fv);
    case HEAVISIDE:
      return new ExpressionNode(kernel0, left, Operation.DIRAC, fv);
    default:
      break;
  }
  ....
}

It seems that, in the second case, Operation.DIRAC should probably be replaced with Operation.HEAVISIDE. Or not? This method is called to obtain the derivative. After researching, we understand what HEAVISIDE *is—the use of *Operation.DIRAC for it is correct. What about the Dirac derivative? This one is a bit tricky to understand. We may trust the developers and suppress the warning. Still, it'd be better if they'd left any explanatory comment as they had done in some cases before.

case FACTORIAL:
  // x! -> psi(x+1) * x!
  return new ExpressionNode(kernel0, left.wrap().plus(1),
      Operation.PSI, null)
          .multiply(new ExpressionNode(kernel0, left,
              Operation.FACTORIAL, null))
          .multiply(left.derivative(fv, kernel0));

case GAMMA:
  // gamma(x) -> gamma(x) psi(x)
  return new ExpressionNode(kernel0, left, Operation.PSI, null)
      .multiply(new ExpressionNode(kernel0, left, Operation.GAMMA,
          null))
      .multiply(left.derivative(fv, kernel0));

And we were motivated to conduct such research by the message of already favorite diagnostic V6067:

V6067 Two or more case-branches perform the same actions. Derivative.java 442, Derivative.java 444

On the one hand, this is an interesting case because we could have a false positive here. On the other, the warning would be useful either way, as it often highlights a genuine error. Regardless of the results, we need to check such code and either fix the error or write explanatory comments. Then the warning can be suppressed.

Vector or point?

private static GeoElement doGetTemplate(Construction cons,
    GeoClass listElement) {
  switch (listElement) {
  case POINT:
    return new GeoPoint(cons);
  case POINT3D:
    return (GeoElement) cons.getKernel().getGeoFactory().newPoint(3, cons);
  case VECTOR:
    return new GeoVector(cons);
  case VECTOR3D:
    return (GeoElement) cons.getKernel().getGeoFactory().newPoint(3, cons);
  }
  return new GeoPoint(cons);
}

The warning isn't hard to guess:

V6067 Two or more case-branches perform the same actions. PointNDFold.java 38, PointNDFold.java 43

Instead of cons.getKernel().getGeoFactory().newPoint(3, cons) in the second case, cons.getKernel().getGeoFactory().newVector(3, cons) may have been intended. If we want to make sure of it, we need to go deeper again. Well, let's dive into it.

So,* getGeoFactory() returns GeoFactory, let's look at the *newPoint *and newVector* methods:

public GeoPointND newPoint(int dimension, Construction cons) {
  return new GeoPoint(cons);
}
public GeoVectorND newVector(int dimension, Construction cons) {
  return new GeoVector(cons);
}

It looks a bit strange. The dimension argument isn't used at all. What's going on here? Inheritance, of course! Let's find the GeoFactory3D inheritor class and see what happens in it.

@Override
public GeoVectorND newVector(int dimension, Construction cons) {
  if (dimension == 3) {
    return new GeoVector3D(cons);
  }
  return new GeoVector(cons);
}
@Override
public GeoPointND newPoint(int dimension, Construction cons) {
  return dimension == 3 ? new GeoPoint3D(cons) : new GeoPoint(cons);
}

Excellent! Now we can admire the creation of four different objects in all their glory. We return to the code fragment with the possible error. For POINT and POINT3D, the objects of the GeoPoint and GeoPoint3D classes are created. GeoVector is created for VECTOR, but poor GeoVector3D seems to have been abandoned.

Sure, it's a bit strange to use a factory method pattern in two cases and call constructors directly in the remaining two. Is this a leftover from the refactoring process, or is it some kind of temporary solution that'll stick around until the end of time? In my opinion, if the responsibility for creating objects has been handed over to another class, it'd be better to fully delegate that responsibility.

Missing quadrillions

@Override
final public void update() {
  ....
  switch (angle.getAngleStyle()) {
    ....
    case EuclidianStyleConstants.RIGHT_ANGLE_STYLE_L:
      // Belgian offset |_
      if (square == null) {
        square = AwtFactory.getPrototype().newGeneralPath();
      } else {
        square.reset();
      }
      length = arcSize * 0.7071067811865;                   // <=
      double offset = length * 0.4;
      square.moveTo(
          coords[0] + length * Math.cos(angSt)
              + offset * Math.cos(angSt)
              + offset * Math.cos(angSt + Kernel.PI_HALF),
          coords[1]
              - length * Math.sin(angSt)
                  * view.getScaleRatio()
              - offset * Math.sin(angSt)
              - offset * Math.sin(angSt + Kernel.PI_HALF));
      ....
      break;
    }
}

Where's the warning? There it is:

V6107 The constant 0.7071067811865 is being utilized. The resulting value could be inaccurate. Consider using Math.sqrt(0.5). DrawAngle.java 303

Wir haben vier Instanzen dieses Codefragments gefunden. Der genauere Wert ist 0,7071067811865476. Fordern Sie sich selbst heraus und versuchen Sie, es auswendig zu lernen, hehe. Die letzten drei Ziffern werden weggelassen. Ist es kritisch? Die Genauigkeit ist wahrscheinlich ausreichend, aber die Verwendung vordefinierter Konstanten oder von Math.sqrt(0.5) – wie in diesem Fall – hilft nicht nur bei der Wiederherstellung verlorener Ziffern, sondern eliminiert auch das Risiko von Tippfehlern. Beachten Sie, wie sich die Lesbarkeit des Codes verbessert. Vielleicht versteht jemand sofort, was für eine magische Zahl das ist, wenn er 0,707 sieht. Manchmal können wir jedoch etwas weniger Magie anwenden, um die Lesbarkeit des Codes zu verbessern.

Abschluss

Unsere kleine Mathe-Reise ist vorbei. Wie wir sehen, können Menschen auch nach der Bewältigung vieler geometrischer Herausforderungen immer noch einfache Fehler im Code machen! Schön, wenn der Code frisch ist und Entwickler ihre früheren Absichten noch im Auge behalten können. In solchen Fällen verstehen die Leute möglicherweise, welche Änderungen gegebenenfalls erforderlich sind, aber nach langer Zeit ist es möglicherweise nicht mehr so ​​einfach, die Notwendigkeit einer Behebung dieser Probleme zu erkennen.

Der Analysator erweist sich also bereits beim Schreiben von Code als recht effizient, anstatt ihn wie ich nur einmal auszuführen. Vor allem jetzt, wo uns Tools wie der PVS-Studio-Analysator zur Verfügung stehen.

Unsere anderen Artikel zu ähnlichen Themen

1. Kopfschmerzen durch die Verwendung mathematischer Software.
2. Mathematiker: Vertrauen, aber überprüfen.
3. Der große Rechner ist verrückt geworden.
4. Analyse des Trans-Proteomic Pipeline (TPP)-Projekts.
5. COVID-19-Forschung und nicht initialisierte Variable.
6. Analyse des Codes von ROOT, wissenschaftliches Datenanalyse-Framework.
7. NCBI Genome Workbench: Wissenschaftliche Forschung in Gefahr.

Das obige ist der detaillierte Inhalt vonSelbst große Mathematiker machen Fehler. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!