Определение порядка расчета связанных формул

Пару лет назад возникла идея реализовать некий аналог таблицы Excel на основе табличного документа 1С. Главной задачей подобной разработки было создание алгоритма, позволяющего определить по формулам связи ячеек документа и их порядок расчета. Позже приоритеты сместились и разработку пришлось забросить. Но необходимость реализации Excel-подобного интерфейса ввода все таки возникла и теоретические наработки наконец-то превратились в работающий код.

На реальном проекте с помощью такой методики удалось реализовать обработку расчета плана производства, суммарное количество формул составило около тысячи (от 70 строк, 12 месяцев + итоги), порядок расчета связанных областей при изменении ячейки достигал 260 элементов.

Общая концепция заключается в том, что связи областей, используемых в формулах, представляются в виде ориентированного графа. Для определения порядка расчета формул используется способ обхода графа "поиск в ширину". Теперь перейдем к практической реализации.

Допустим, есть ряд именованных ячеек табличного документа [a..g] и определены формулы расчета:
b = a + 1
c = a + f
d = a * c + e
g = b + d

Тогда связь ячеек можно представить в виде графа:

Для демонстрации метода я сделал небольшую обработку:

&НаСервере
Процедура ТестНаСервере()
 
 Результат.Очистить();
 
 Вершины = Новый Соответствие;
 Формулы = Новый Соответствие;
 //формирование списка формул
 Формулы.Вставить("b", "[a]+1");
 Формулы.Вставить("c", "[a]+[f]");
 Формулы.Вставить("d", "[a]*[c]+[e]");
 Формулы.Вставить("g", "[b]+[d]");
 
 ЧтениеДОМ = Новый ПостроительDOM; 
 ЧтениеФормулы = Новый ЧтениеXML;
 
 Для Каждого Формула Из Формулы Цикл
  
  ТекущаяВершина = Формула.Ключ;
  ТекущаяФормула = Формула.Значение;
  
  ЗначениеВершины = Вершины[ТекущаяВершина];
  Если ЗначениеВершины = Неопределено Тогда
   СписокСвязей = Новый СписокЗначений;
   ЗначенияФормулы = Новый СписокЗначений;
   Вершины.Вставить(ТекущаяВершина, Новый Структура("Формула, СписокСвязей, ЗначенияФормулы", ТекущаяФормула, СписокСвязей, ЗначенияФормулы));
  Иначе
   ЗначениеВершины.Формула = ТекущаяФормула;
   ЗначенияФормулы = ЗначениеВершины.ЗначенияФормулы;
  КонецЕсли;
  
  //первый вариант обнаружения имени области был через поиск по строке символов "[", "]"
  ЧтениеФормулы.УстановитьСтроку(ПолучитьПредставлениеФормулыXML(ТекущаяФормула));
  ПредставлениеФормулы = ЧтениеДОМ.Прочитать(ЧтениеФормулы);
  Разыменователь = Новый РазыменовательПространствИменDOM(ПредставлениеФормулы);
  РезультатПоиска = ПредставлениеФормулы.ВычислитьВыражениеXPath("//param", ПредставлениеФормулы, Разыменователь);
  
  ПолучитьСледующий = Истина;
  Пока ПолучитьСледующий Цикл
   ЭлементРезультата = РезультатПоиска.ПолучитьСледующий();
   Если ЭлементРезультата = Неопределено Тогда
    ПолучитьСледующий = Ложь;
   Иначе
    ВершинаФормулы = ЭлементРезультата.ТекстовоеСодержимое;
    ДобавитьСвязьВершины(Вершины, ВершинаФормулы, ТекущаяВершина);
    ЗначенияФормулы.Добавить(ВершинаФормулы);
   КонецЕсли;
  КонецЦикла;
  
 КонецЦикла;
 
 ПоместитьВоВременноеХранилище(Вершины, АдресКэш); 
 ТипЧисло = Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(15, 2));
 
 Для СтрокаДокумента = 1 По 2 Цикл
  Сч = 1;
  Для Каждого ЭлементСтруктуры Из Вершины Цикл
   ОбластьДокумента = Результат.Область(СтрокаДокумента, Сч);
   Если СтрокаДокумента = 1 Тогда
    ОбластьДокумента.Текст = ЭлементСтруктуры.Ключ;
   Иначе
    ИмяОбласти = ЭлементСтруктуры.Ключ;
    //пришлось добавить подчеркивание к имени области, 
    //при установке ОбластьДокумента.Имя = "d" имя не присваивается
    ОбластьДокумента.Имя = "_" + ИмяОбласти;
    ОбластьДокумента.СодержитЗначение = Истина;
    ОбластьДокумента.УстановитьЭлементУправления(Тип("ПолеВводаФормы"));
    ОбластьДокумента.ТипЗначения = ТипЧисло;
    Если НЕ ЭлементСтруктуры.Значение.ЗначенияФормулы.Количество() Тогда
     ОбластьДокумента.Защита = Ложь;
     ОбластьДокумента.ЦветФона = WebЦвета.Желтый;
    КонецЕсли;
    
   КонецЕсли;
   Сч = Сч + 1;
  КонецЦикла;
 КонецЦикла;
 
КонецПроцедуры

&НаСервере
Функция ПолучитьПредставлениеФормулыXML(ТекстФормулы)
 
 ПредставлениеФормулы = СтрЗаменить(ТекстФормулы, "(", "<group>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, ")", "</group>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, "[", "<param>");
 ПредставлениеФормулы = СтрЗаменить(ПредставлениеФормулы, "]", "</param>");
 
 Возврат "<formula>" + ПредставлениеФормулы +  "</formula>";
 
КонецФункции // ПолучитьПредставлениеФормулыXML()

&НаСервере
Процедура ДобавитьСвязьВершины(Вершины, Знач Вершина1, Знач Вершина2)
 
 ЗначениеВершины = Вершины[Вершина1];
 Если ЗначениеВершины = Неопределено Тогда
  СписокСвязей = Новый СписокЗначений;
  СписокСвязей.Добавить(Вершина2);
  Вершины.Вставить(Вершина1, Новый Структура("Формула, СписокСвязей, ЗначенияФормулы",, СписокСвязей, Новый СписокЗначений));
 Иначе
  ЗначениеВершины.СписокСвязей.Добавить(Вершина2);
 КонецЕсли;
 
КонецПроцедуры // ДобавитьСвязьВершины()

&НаКлиенте
Процедура Тест(Команда)
 ТестНаСервере();
КонецПроцедуры

&НаСервере
Процедура ПриСозданииНаСервере(Отказ, СтандартнаяОбработка)
 
 АдресКэш = ПоместитьВоВременноеХранилище(Неопределено, УникальныйИдентификатор);
 
КонецПроцедуры

&НаКлиенте
Процедура РезультатПриИзмененииСодержимогоОбласти(Элемент, Область)
 
 Области = Результат.Области;
 ИмяОбласти = СтрЗаменить(Область.Имя, "_", "");
 
 Вершины = ПолучитьИзВременногоХранилища(АдресКэш);
 
 РасчетОбласти = Вершины[ИмяОбласти];
 Если РасчетОбласти = Неопределено Тогда
  Возврат;
 КонецЕсли;
 
 СписокСвязей = РасчетОбласти.СписокСвязей;
 Очередь = Новый СписокЗначений;
 Очередь.ЗагрузитьЗначения(СписокСвязей.ВыгрузитьЗначения());
 ПорядокРасчета = Новый СписокЗначений;
 
 Пока Очередь.Количество() Цикл
  
  ЭлементОчереди = Очередь[0];
  Вершина = ЭлементОчереди.Значение;
  ПорядокРасчета.Добавить(Вершина);
  Очередь.Удалить(ЭлементОчереди);
  
  СписокОчереди = Вершины[Вершина].СписокСвязей.ВыгрузитьЗначения();
  Для Каждого ВершинаОчереди Из СписокОчереди Цикл
   
   ЭлементСписка = Очередь.НайтиПоЗначению(ВершинаОчереди);
   Если НЕ ЭлементСписка = Неопределено Тогда
    Очередь.Удалить(ЭлементСписка);
   КонецЕсли;
   ЭлементСписка = ПорядокРасчета.НайтиПоЗначению(ВершинаОчереди);
   Если НЕ ЭлементСписка = Неопределено Тогда
    ПорядокРасчета.Удалить(ЭлементСписка);
   КонецЕсли;
   Очередь.Добавить(ВершинаОчереди);
  КонецЦикла;
  
 КонецЦикла;
 
 Для Каждого ВершинаПорядка Из ПорядокРасчета Цикл
  
  Вершина = Вершины[ВершинаПорядка.Значение];
  Если Вершина = Неопределено Тогда
   Продолжить;
  КонецЕсли;
  
  Формула = Вершина.Формула; 
  Если Формула = Неопределено Тогда
   Продолжить;
  КонецЕсли;
  
  Формула = СтрЗаменить(Формула, "[", "Области[""_");
  Формула = СтрЗаменить(Формула, "]", """].Значение");
  Области["_" + ВершинаПорядка.Значение].Значение = ВычислитьРезультат(Формула, Области);
  
 КонецЦикла;
 
КонецПроцедуры

&НаКлиенте
Функция ВычислитьРезультат(Формула, Области)

 Перем Результат;
 
 Выполнить("Результат = " + Формула);
 
 Возврат Результат;

КонецФункции // ВычислитьРезультат()

Запускаем на выполнение и введем в область "а" единицу.

В отладчике можно посмотреть список связей области и порядок расчета.

Корректность порядка расчета можно проверить по вышеприведенной схеме графа.

По результатам обработки получаем следующие значения в связанных ячейках.

Порядок расчета для области "e":

Соответственно, для области "f":

Результаты расчета можно проверить по изначальным формулам, либо в Excel.

Обработка для теста.