Malah ahli matematik yang hebat melakukan kesilapan

Kita tahu bahawa matematik adalah sains ketepatan. Bolehkah kita mengatakan perkara yang sama tentang GeoGebra, perisian pembelajaran matematik interaktif? Mari analisa kod sumber projek menggunakan PVS-Studio!

pengenalan

Adakah anda masih ingat bagaimana anda belajar sains komputer di universiti? Semua pendaraban matriks dan vektor ini, persamaan polinomial, interpolasi, ekstrapolasi... Bagaimana jika kita melihat formula yang menakutkan ini dalam projek sebenar, dan bukannya dalam laporan makmal yang lain? Bagaimana jika kita mencari isu dalam pangkalan kod sedemikian? Saya cadangkan menjalankan PVS-Studio dan membersihkan buku teks matematik. Mengapa buku teks? Biar saya tunjukkan.

Cabaran matematik

Salah satu cabaran utama dalam meneliti kod sumber program sedemikian adalah untuk memahami perkara yang sedang berlaku. Semasa menyemak laporan penganalisis, kami mempunyai soalan sama ada amaran itu menunjukkan isu sebenar.

Mari kita lihat serpihan berikut:

@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);
  }
  ....
}

Kami mendapat amaran PVS-Studio berikut:

V6072 Dua serpihan kod serupa ditemui. Mungkin, ini adalah kesilapan taip dan pembolehubah 'b' harus digunakan dan bukannya 'a'. AlgoTriangularDF.java 145, AlgoTriangularDF.java 146, AlgoTriangularDF.java 147, AlgoTriangularDF.java 148

Adakah ia benar-benar salah taip? Selepas penyelidikan pantas, dan setelah kami menemui formula yang betul, kami boleh mengatakan bahawa semuanya ditulis dengan betul.

Serpihan kod menilai taburan segi tiga, iaitu fungsi ketumpatan kebarangkalian (PDF) untuk taburan ini. Kami menemui formula:

Sekarang mari kita lihat kod tersebut.

Di sini,* fv* ialah pembolehubah fungsi. wrap mengembalikan wrapper, dan kemudian operasi matematik yang diperlukan dilakukan. Adalah menarik untuk diperhatikan bahawa terdapat kedua-dua kaedah darab dan darab. Dalam kaedah kedua, R bermaksud kanan dan menukar operan, kerana pendaraban tidak selalunya komutatif.

Jadi, hasil ungkapan kedua ditulis kepada branchAToMode, dan ungkapan keempat ditulis kepada branchModeToB.

Kami juga mendapati bahawa dalam branchModeToB, tanda untuk pengangka dan penyebut telah ditukar. Kami mendapat ungkapan berikut:

Nilai ungkapan tidak berubah.

Jadi, kami menyegarkan semula pengetahuan matematik kami untuk memahami beberapa amaran yang kami terima. Tidak sukar untuk mengenal pasti sama ada terdapat ralat sebenar dalam kod, tetapi sukar untuk memahami perkara yang sepatutnya ada di sini.

Kesilapan

Segmen kod hilang

Mari kita mulakan dengan mudah dan lihat kaedah berikut:

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();
}

Kami melihat bahawa seseorang telah terlupa untuk menggantikan s[2] dengan s[3]. Kesan baris terakhir adalah dalam semua kecemerlangannya. Ia adalah ralat salin-tampal yang legenda dan terlalu biasa. Akibatnya, item tatasusunan keempat tiada dan null!

V6033 Item dengan kunci yang sama '2' telah pun ditukar. AlgoPolyhedronNetPrism.java 376, AlgoPolyhedronNetPrism.java 377

Bagaimana dengan nilai?

Sekarang cuba lihat isu tersebut dalam coretan kod berikut:

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;
}

Sungguh menakjubkan pemandangan! Seronok membaca, dan ini hanya sebahagian kecil kerana kaedah ini bermula pada baris 66 dan berakhir pada 404. Penganalisis mengeluarkan 50 amaran jenis V6033. Mari kita lihat sekilas salah satu amaran ini:

V6033 Item dengan kunci yang sama '"∼"' telah ditambahkan. MathMLParser.java 229, MathMLParser.java 355

Mari kita keluarkan serpihan yang berlebihan dan lihat ungkapan yang dirujuk kepada amaran:

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

Memang menarik. Apakah jarak antara panggilan kaedah? Terdapat 126 baris. Nah, semoga berjaya menemui ralat sedemikian dengan tangan!

Kebanyakan adalah pendua dalam kunci dan nilai. Walau bagaimanapun, beberapa kes adalah serupa dengan contoh di atas, di mana pembangun menimpa nilai dengan yang berbeza. Mana satu yang patut kita gunakan?

Bulatan atau elips

@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;
      }
    }
  }
}

Kaedah untuk elips dipanggil untuk kedua-dua elips dan bulatan. Sesungguhnya, kita boleh menganggap bahawa ini tidak mengapa kerana bulatan juga adalah elips. Walau bagaimanapun, kelas itu juga mempunyai kaedah updateCircle. Apa yang sepatutnya, kemudian? Mari kita menyelaminya dengan lebih mendalam.

Semuanya berlaku dalam kelas DrawConic3D. Berikut ialah kaedah untuk elips dan bulatan:

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

Kami menemui empat contoh serpihan kod ini. Nilai yang lebih tepat ialah 0.7071067811865476. Cabar diri sendiri dan cuba belajar dengan hati, hehe. Tiga digit terakhir ditinggalkan. Adakah ia kritikal? Ketepatan mungkin cukup, tetapi menggunakan pemalar yang dipratentukan atau Math.sqrt(0.5)—seperti dalam kes ini—bukan sahaja membantu memulihkan digit yang hilang tetapi juga menghapuskan risiko kesilapan menaip. Perhatikan bagaimana kebolehbacaan kod akan dipertingkatkan. Mungkin apabila melihat 0.707... seseorang segera memahami jenis nombor ajaib itu. Walau bagaimanapun, kadangkala kita boleh melakukan sedikit keajaiban hanya untuk meningkatkan kebolehbacaan kod.

Kesimpulan

Perjalanan matematik kecil kami telah berakhir. Seperti yang kita dapat lihat, walaupun selepas menangani banyak cabaran geometri, orang ramai masih boleh membuat kesilapan mudah dalam kod! Bagus jika kod itu segar dan pembangun masih boleh mengingati niat masa lalu mereka. Dalam kes sedemikian, orang mungkin memahami perubahan yang diperlukan jika ada, tetapi selepas masa yang lama mungkin tidak begitu mudah untuk mengenali keperluan untuk membetulkan isu ini.

Jadi, penganalisis terbukti agak cekap betul semasa menulis kod dan bukannya menjalankannya sekali seperti yang saya lakukan. Terutamanya sekarang apabila kami mempunyai alat seperti penganalisis PVS-Studio yang kami gunakan.

Artikel kami yang lain mengenai topik yang sama

1. Sakit kepala kerana menggunakan perisian matematik.
2. Ahli Matematik: Percaya, tetapi Sahkan.
3. Kalkulator Besar Menjadi Gila.
4. Analisis projek Trans-Proteomic Pipeline (TPP).
5. Penyelidikan COVID-19 dan pembolehubah tidak dimulakan.
6. Menganalisis kod ROOT, Rangka Kerja Analisis Data saintifik.
7. Meja Kerja Genom NCBI: Penyelidikan Saintifik di Bawah Ancaman.

Atas ialah kandungan terperinci Malah ahli matematik yang hebat melakukan kesilapan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!