Optimise deep recursion

[chrisburr]

Currently deeply nested functions result in a RecursionError. This could be optimised by having a simpler parser find functions and then evaluate their arguments iteratively instead of recursively.

[alexpearce]

Here's an example cut string that produces a RecursionError:

((1 && Ds_h1_PT > 800 && Ds_h1_P > 3000.0 && Ds_h1_Loki_MIPCHI2DV > 10.0 && Ds_h1_TRACK_CHI2NDOF < 3.0 && Ds_h1_Loki_nVeloHits > 9)||(1 && Ds_h2_PT > 800 && Ds_h2_P > 3000.0 && Ds_h2_Loki_MIPCHI2DV > 10.0 && Ds_h2_TRACK_CHI2NDOF < 3.0 && Ds_h2_Loki_nVeloHits > 9)||(1 && Ds_h3_PT > 800 && Ds_h3_P > 3000.0 && Ds_h3_Loki_MIPCHI2DV > 10.0 && Ds_h3_TRACK_CHI2NDOF < 3.0 && Ds_h3_Loki_nVeloHits > 9))&&1 && (ROOTex::Leading(Ds_h1_PT,Ds_h2_PT,Ds_h3_PT)) > 1000.0 && (ROOTex::SecondLeading(Ds_h1_PT,Ds_h2_PT,Ds_h3_PT)) > 400.0 && (ROOTex::ThirdLeading(Ds_h1_PT,Ds_h2_PT,Ds_h3_PT)) > 200.0 && Ds_h1_P > 2000.0 && Ds_h2_P > 2000.0 && Ds_h3_P > 2000.0 && Ds_h1_TRACK_CHI2NDOF < 3.0 && Ds_h2_TRACK_CHI2NDOF < 3.0 && Ds_h3_TRACK_CHI2NDOF < 3.0 && (ROOTex::Leading(Ds_h1_Loki_MIPCHI2DV,Ds_h2_Loki_MIPCHI2DV,Ds_h3_Loki_MIPCHI2DV)) > 50.0 && (ROOTex::SecondLeading(Ds_h1_Loki_MIPCHI2DV,Ds_h2_Loki_MIPCHI2DV,Ds_h3_Loki_MIPCHI2DV)) > 10.0 && (ROOTex::ThirdLeading(Ds_h1_Loki_MIPCHI2DV,Ds_h2_Loki_MIPCHI2DV,Ds_h3_Loki_MIPCHI2DV)) > 4.0 && Ds_M > 1889.0 && Ds_M < 2049.0 && Ds_ENDVERTEX_CHI2/Ds_ENDVERTEX_NDOF < 25.0 && Ds_DIRA_OWNPV > 0.9994 && Ds_FDCHI2_OWNPV > 16.0 && Ds_Loki_BPVLTIME > 0.00015&&1 && Ds_M > 1900 && Ds_M < 2050 && Ds_Loki_M12 > 999.46 && Ds_Loki_M12 < 1039.46 && Ds_ENDVERTEX_CHI2/Ds_ENDVERTEX_NDOF < 6.0 && Ds_DIRA_OWNPV > 0.9999 && Ds_h1_P > 3000.0 && Ds_h1_P < 100000.0 && Ds_h2_P > 3000.0 && Ds_h2_P < 100000.0 && Ds_h3_P > 3000.0 && Ds_h3_P < 100000.0 && Ds_h1_ETA > 2.0 && Ds_h1_ETA < 5.0 && Ds_h2_ETA > 2.0 && Ds_h2_ETA < 5.0 && Ds_h3_ETA > 2.0 && Ds_h3_ETA < 5.0 && Ds_h1_TRACK_GhostProb < 0.3 && Ds_h2_TRACK_GhostProb < 0.3 && Ds_h3_TRACK_GhostProb < 0.3&&(Ds_BKGCAT == 0 || Ds_BKGCAT == 10)&&(TMath::Sqrt(((Ds_h1_PE+Ds_h2_PE)*(Ds_h1_PE+Ds_h2_PE)) - (((Ds_h1_PX+Ds_h2_PX)*(Ds_h1_PX+Ds_h2_PX)) + ((Ds_h1_PY+Ds_h2_PY)*(Ds_h1_PY+Ds_h2_PY)) + ((Ds_h1_PZ+Ds_h2_PZ)*(Ds_h1_PZ+Ds_h2_PZ)))) > (1019.46-20.) && TMath::Sqrt(((Ds_h1_PE+Ds_h2_PE)*(Ds_h1_PE+Ds_h2_PE)) - (((Ds_h1_PX+Ds_h2_PX)*(Ds_h1_PX+Ds_h2_PX)) + ((Ds_h1_PY+Ds_h2_PY)*(Ds_h1_PY+Ds_h2_PY)) + ((Ds_h1_PZ+Ds_h2_PZ)*(Ds_h1_PZ+Ds_h2_PZ)))) < (1019.46+20.))

To reproduce, run:

python -m formulate --from-root $CUTSTRING --to-root

[jonas-eschle]

I think with 1.0, this should be resolved: https://github.com/scikit-hep/formulate/releases/tag/v1.0.1

We're glad to have feedback and feel free to clone if this resolves the issue