Даже математики ошибаются09.08.2024 12:00

Мы знаем, что математика — наука точная. Значит ли это, что GeoGebra — программное обеспечение для интерактивного изучения математики — столь же точно? Проанализируем же исходный код проекта с помощью PVS-Studio!

Введение

Помните изучение программирования в университете? Умножение векторов и матриц, расчёт полиномов, интерполяция, экстраполяция… Что насчёт того, чтобы посмотреть применение этих страшных формул в настоящем проекте, а не в очередной лабораторной работе? А что насчёт поиска проблем в такой кодовой базе? Предлагаю запустить PVS-Studio и открыть учебники математики. Зачем учебники? Сейчас покажу.

Математические трудности

Одна из основных трудностей при изучении исходного кода программ данного калибра — попытка понять, что происходит. При просмотре отчёта анализатора часто возникали вопросы о действительности наличия или отсутствия проблем в части срабатываний.

Рассмотрим, например, следующий фрагмент:

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

Получаем следующее предупреждение PVS-Studio:

V6072 Two similar code fragments were found. Perhaps, this is a typo and 'b' variable should be used instead of 'a'. AlgoTriangularDF.java 145, AlgoTriangularDF.java 146, AlgoTriangularDF.java 147, AlgoTriangularDF.java 148

Действительно ли это опечатка? После небольшого исследования и найденной необходимой формулы можем спокойно заявить — всё написано верно.

Объяснение фрагмента.

Потому для разбора некоторых полученных предупреждений пришлось изучать математический материал. И не столь тяжело убедиться, действительно ли произошла ошибка при написании кода, сколь понять, что должно было быть на её месте.

Ошибки

Потерянный сегмент

Начинаем с простого. Посмотрим на следующий метод:

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

Обнаруживаем, что кто-то забыл заменить s[2] на s[3]. Эффект последней строки во всей своей красе. Легендарная и уж слишком распространённая ошибка copy-paste. В результате получаем, что четвёртый элемент массива отсутствует и является null!

V6033 An item with the same key '2' has already been changed. AlgoPolyhedronNetPrism.java 376, AlgoPolyhedronNetPrism.java 377

Что там по значениям?

А теперь попробуйте найти проблему в следующем фрагменте:

static synchronized HashMap getGeogebraMap() {
  ....
  geogebraMap.put("−", "-");
  geogebraMap.put("⊥", "# ");
  geogebraMap.put("∼", "~ ");
  geogebraMap.put("′", "# ");
  geogebraMap.put("≤", Unicode.LESS_EQUAL + "");
  geogebraMap.put("≥", Unicode.GREATER_EQUAL + "");
  geogebraMap.put("∞", Unicode.INFINITY + "");
  ....
  geogebraMap.put("∏", "# ");
  geogebraMap.put("∏", "# ");
  geogebraMap.put("〉", "# ");
  geogebraMap.put("⟩", "# ");
  geogebraMap.put("→", "# ");
  geogebraMap.put("⇒", "# ");
  geogebraMap.put("⟩", "# ");
  geogebraMap.put("→", "# ");
  geogebraMap.put("⇒", "# ");
  geogebraMap.put("→", "# ");
  geogebraMap.put("⋅", "* ");
  geogebraMap.put("∼", "# ");
  geogebraMap.put("∝", "# ");
  geogebraMap.put("∝", "# ");
  geogebraMap.put("∝", "# ");
  geogebraMap.put("⊂", "# ");
  ....
  return geogebraMap;
}

Какой великолепный вид! Читать это — сплошное удовольствие, а это лишь малая часть, ведь данный метод начинается на строке 66 и заканчивается на 404. Мы также получаем целых 50 срабатываний диагностики V6033. Быстро посмотрим одно из этих предупреждений:

V6033 An item with the same key '»∼»' has already been added. MathMLParser.java 229, MathMLParser.java 355

Уберём лишние фрагменты и посмотрим конкретно на выражения из предупреждения:

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

Интересно. Что насчёт расстояния между этими вызовами методов? 126 строк. Успехов обнаружить такое вручную!

Большая часть — дубликаты и по ключу, и по значению, но несколько случаев аналогичны примеру сверху, где значение переписывается на иное. Какое из двух должно использоваться?

Окружности и эллипсы

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

Что для эллипса, что для окружности вызывается метод для эллипса. Можно, конечно, предположить, что это не ошибочно ввиду того, что окружность — это эллипс. Однако в этом классе также присутствует метод updateCircle. Так как должно быть? Попробуем зайти чуть глубже.

Всё происходит в классе DrawConic3D. Методы для эллипса и для окружности:

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

Делаем выводы, и они… придают не так много уверенности. Да, тела методов разные, но, в общем и целом, ничего здесь не кричит, что мы рискуем образованием на экране неприемлемых геометрических объектов в случае неверного вызова метода.

Может есть другие улики? Целая одна! Метод updateCircle ни разу не используется в проекте. В то же время *updateEllipse *используется 4 раза: два раза в первом фрагменте, и ещё два — уже в классе-наследнике класса DrawConic3D — DrawConicSection3D:

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

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

Данный updateCircle также не используется. Что оставляет updateEllipse лишь с вызовом в собственном переопределении и в updateForItSelf — во фрагменте, который мы и рассматривали изначально. В виде схемы структуру можно представить так:

С одной стороны, кажется, что разработчики и правда хотели использовать универсальный метод отрисовки окружности в виде updateEllipse. С другой стороны, странно, что в DrawConicSection3D есть метод updateCircle, вызывающий updateEllipse. Но сам updateCircle никогда не вызовется.

Сложно предположить, как должен выглядеть исправленный код, если ошибка в нём действительно присутствует. Например, если в DrawConicSection3D updateCircle должен вызывать updateEllipse, а в DrawConic3D нужен более оптимизированный алгоритм для круга, то исправленная схема может выглядеть так:

По итогу есть ощущение, что updateCircle был однажды написан и с тех пор потерян, а мы, вполне вероятно, нашли его предполагаемое место жительства. Либо это следы оставшегося рефакторинга и о бездомном методе забыли. В любом случае, стоит сделать этот код понятнее, чтобы такого количества вопросов не возникало.

А у нас они возникли благодаря одному из предупреждений PVS-Studio. Оно, кстати, следующее:

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

Порядок ненайденного объекта

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

Получаем следующее предупреждение:

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

Выходит любопытно, ведь в блоке else переменная index гарантированно приобретает значение 0, а, следовательно, мы получаем -1 как аргумент для метода get. Результат? Ловим IndexOutOfBoundsException.

Треугольники

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

Код новый, а ошибка уже знакомая. Вполне очевидно, что вместо GL.GL_TRIANGLE_STRIP должен быть GL.GL_TRIANGLE_FAN. Методы может чем-то и похожие, но результат всё же дают разный. Об этом можно прочитать в спойлере.

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

Для любопытных про Triangle Strip и Triangle Fan.

Перетирая значения

public static void addToJsObject(JsPropertyMap