Recursion level limit

[MvGulik]

Aha. Roger.

[UEZ]

I updated the code from post#1. Now you can see how it works.

Br,

UEZ

[UEZ]

I modified the code from post#1 slightly.

Can somebody explain me why the recursion stack limit is reached when starting at coordinate 0,0 at $iRec = 13269 but when starting it with coordinate 82, 24 it will not break and $iRec is 28989.

This is the result on my machine and may differ on yours.

Thanks,

UEZ

Edited January 12, 2013 by UEZ

[Jos]

The reason is that the recursion count with 0,0 hits 3900, which is the limit for x64 systems:

Changed your debug a little to demonstrate it:

expandcollapse popup

#include <GDIPlus.au3>
Global $recur = 1

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")
$iW = _GDIPlus_ImageGetWidth($hImage)
$iH = _GDIPlus_ImageGetHeight($hImage)
$hGUI = GUICreate("Test", $iW, $iH)
GUISetState()
$hGfx = _GDIPlus_GraphicsCreateFromHWND($hGUI)
AdlibRegister("UpdateView", 10)

$iColor2Fill = 0xFFFFFFFF
_GDIPlus_FloodFill($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
;~ _GDIPlus_FloodFill($hImage, 82, 24, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
;~ ShellExecute(@ScriptDir & "\Filled.png")
AdlibUnRegister("UpdateView")
ConsoleWrite("Done" & @LF)
Do
Until GUIGetMsg() = -3

_GDIPlus_ImageDispose($hImage)
_GDIPlus_GraphicsDispose($hGfx)
_GDIPlus_Shutdown()
Exit

Func _GDIPlus_FloodFill(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-11
Local Static $iRec = 1
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $recur = ' & $recur & ' $iRec = ' & $iRec & ' >Error code: ' & @error & @CRLF) ;### Debug Console
;~   If $iRec > 13268 Then Return -1 ;max recursion stack reached
Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint*", 0)
If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
     DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint", $iColorNew)
;~       Sleep(10)
Else
     Return 0
EndIf
$iRec += 1
$aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
If ($iX + 1) < $aResult[2] + 1 Then
     $iRec += 1
     $recur += 1
     _GDIPlus_FloodFill($hBitmap, $iX + 1, $iY, $iColorOld, $iColorNew) ;go east
     $recur -= 1
EndIf
If ($iY + 1) < $aResult[3] + 1 Then
     $iRec += 1
     $recur += 1
     _GDIPlus_FloodFill($hBitmap, $iX, $iY + 1, $iColorOld, $iColorNew) ;go south
     $recur -= 1
EndIf
If ($iX - 1) > -1 Then
     $iRec += 1
     $recur += 1
     _GDIPlus_FloodFill($hBitmap, $iX - 1, $iY, $iColorOld, $iColorNew) ;go west
     $recur -= 1
EndIf
If ($iY - 1) > -1 Then
     $iRec += 1
     $recur += 1
     _GDIPlus_FloodFill($hBitmap, $iX, $iY - 1, $iColorOld, $iColorNew) ;go north
     $recur -= 1
EndIf
Return 1
EndFunc ;==>_GDIPlus_FloodFill

Func UpdateView()
_GDIPlus_GraphicsDrawImage($hGfx, $hImage, 0, 0)
EndFunc ;==>UpdateView

Jos

Edited January 12, 2013 by Jos

[UEZ]

Thanks for the clarification Jos.

That means the stack will be decreased when returning from the function. That was a misunderstanding from me.

$iRec is the sum of recursion calls not the recursion level.

Br,

UEZ

Edited January 13, 2013 by UEZ

[Jos]

Maybe trancexx or Jon can comment here, but looking at the source it seems we have a 3900 limit for x64 and a 1900 limit for x86 for both Call and Execute while the helpfile states 5100.

Jos

[James]

Stack-based recursion is awesome. I had to do something similar in node.js a few months ago, like monoceres pointed out, visualizing the output from it is cool

[UEZ]

Here the iterative version which is much slower because I used an array for the stack simulation:

expandcollapse popup

#include <Array.au3>
#include <GDIPlus.au3>;~~~

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")
$iW = _GDIPlus_ImageGetWidth($hImage)
$iH = _GDIPlus_ImageGetHeight($hImage)
$hGUI = GUICreate("Test", $iW, $iH)
GUISetState()
$hGfx = _GDIPlus_GraphicsCreateFromHWND($hGUI)
AdlibRegister("UpdateView", 10)

$iColor2Fill = 0xFFFFFFFF
;~ _GDIPlus_FloodFillRecRec($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_FloodFillRecIter($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.gif")
;~ ShellExecute(@ScriptDir & "\Filled.png")
AdlibUnRegister("UpdateView")
ConsoleWrite("Done" & @LF)
Do
Until GUIGetMsg() = -3

_GDIPlus_ImageDispose($hImage)
_GDIPlus_GraphicsDispose($hGfx)
_GDIPlus_Shutdown()
Exit

Func _GDIPlus_FloodFillRecIter(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-12
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    Local $iW = $aResult[2], $iH = $aResult[3]
    If BitOR($iX < 0, $iY < 0, $iX > $iW - 1, $iY > $iH - 1) Then
        Return 0
    EndIf
    Local $x, $y
    Local $aStack[1] ;stack ->x,y coordinate
    _ArrayAdd($aStack, $iX & ";" & $iY)
    While UBound($aStack)  > 1
        $sPoint = $aStack[UBound($aStack) - 1]
        _ArrayDelete($aStack, UBound($aStack) - 1) ;pop
        $x = Int(StringRegExpReplace($sPoint, "(\d+);\d+", "$1"))
        $y = Int(StringRegExpReplace($sPoint, "\d+;(\d+)", "$1"))
        If BitOR($x< 0, $y < 0, $x > $iW - 1, $y > $iH - 1) Then ContinueLoop
        $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint*", 0)
        If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
            DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint", $iColorNew)
            _ArrayAdd($aStack, $x + 1 & ";" & $y) ;push
            _ArrayAdd($aStack, $x & ";" & $y + 1) ;push
            _ArrayAdd($aStack, $x - 1 & ";" & $y) ;push
            _ArrayAdd($aStack, $x & ";" & $y - 1) ;push
        EndIf
    WEnd
EndFunc

Func _GDIPlus_FloodFillRec(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-12
    Local Static $iRec = 1
    If $iRec = 3898 Then
        ConsoleWrite("max recursion level has been reached" & @LF)
        Return -1 ;max recursion level has been reached
    EndIf
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint*", 0)
    If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
        DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint", $iColorNew)
    Else
        Return 0
    EndIf
    $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    If ($iX + 1) < $aResult[2] + 1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX + 1, $iY, $iColorOld, $iColorNew) ;go east
        $iRec -= 1
    EndIf
    If ($iY + 1) < $aResult[3] + 1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY + 1, $iColorOld, $iColorNew) ;go south
        $iRec -= 1
    EndIf
    If ($iX - 1) > -1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX - 1, $iY, $iColorOld, $iColorNew) ;go west
        $iRec -= 1
    EndIf
    If ($iY - 1) > -1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY - 1, $iColorOld, $iColorNew) ;go north
        $iRec -= 1
    EndIf
    Return 1
EndFunc

Func UpdateView()
    _GDIPlus_GraphicsDrawImage($hGfx, $hImage, 0, 0)
EndFunc

Searching for a much faster stack simulation code!

Btw, how can I use AutoIt objects to do some p.x or p.y to read/write it?

Br,

UEZ

[KaFu]

Use a dictionary object, much faster than an array.

Alternatively do not use the Array UDF functions, as they redim the array on each call. Redim the array only every 500 or 1000 elements and perform the additions and deletions manually with an own counter... but I still would first try the dictionary object ...

Edit: Wasn't there something with vtables in the last beta? Wouldn't this be a good application for those?

Edited January 12, 2013 by KaFu

[Jos]

Try this one... its a little faster

expandcollapse popup

#include <Array.au3>
#include <GDIPlus.au3>;~~~

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")
$iW = _GDIPlus_ImageGetWidth($hImage)
$iH = _GDIPlus_ImageGetHeight($hImage)
$hGUI = GUICreate("Test", $iW, $iH)
GUISetState()
$hGfx = _GDIPlus_GraphicsCreateFromHWND($hGUI)
AdlibRegister("UpdateView", 10)

$iColor2Fill = 0xFFFFFFFF
;~ _GDIPlus_FloodFillRecRec($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_FloodFillRecIter($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.gif")
;~ ShellExecute(@ScriptDir & "\Filled.png")
AdlibUnRegister("UpdateView")
ConsoleWrite("Done" & @LF)
Do
Until GUIGetMsg() = -3

_GDIPlus_ImageDispose($hImage)
_GDIPlus_GraphicsDispose($hGfx)
_GDIPlus_Shutdown()
Exit

Func _GDIPlus_FloodFillRecIter(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-12
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    Local $iW = $aResult[2], $iH = $aResult[3]
    If BitOR($iX < 0, $iY < 0, $iX > $iW - 1, $iY > $iH - 1) Then
        Return 0
    EndIf
    Local $x, $y
    Local $aStack[5000] ;stack ->x,y coordinate
    Local $iStack = 1
    StackAdd($aStack, $iX & ";" & $iY, $iStack)
    While $iStack > 0
        $sPoint = $aStack[$iStack - 1]
        StackDelete($aStack, $iStack) ;pop
        $x = Int(StringRegExpReplace($sPoint, "(\d+);\d+", "$1"))
        $y = Int(StringRegExpReplace($sPoint, "\d+;(\d+)", "$1"))
        If BitOR($x< 0, $y < 0, $x > $iW - 1, $y > $iH - 1) Then ContinueLoop
        $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint*", 0)
        If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
            DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint", $iColorNew)
            StackAdd($aStack, $x + 1 & ";" & $y,  $iStack) ;push
            StackAdd($aStack, $x & ";" & $y + 1,  $iStack) ;push
            StackAdd($aStack, $x - 1 & ";" & $y,  $iStack) ;push
            StackAdd($aStack, $x & ";" & $y - 1,  $iStack) ;push
        EndIf
    WEnd
EndFunc

Func _GDIPlus_FloodFillRec(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-12
    Local Static $iRec = 1
    If $iRec = 3898 Then
        ConsoleWrite("max recursion level has been reached" & @LF)
        Return -1 ;max recursion level has been reached
    EndIf
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint*", 0)
    If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
        DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $iX, "int", $iY, "uint", $iColorNew)
    Else
        Return 0
    EndIf
    $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    If ($iX + 1) < $aResult[2] + 1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX + 1, $iY, $iColorOld, $iColorNew) ;go east
        $iRec -= 1
    EndIf
    If ($iY + 1) < $aResult[3] + 1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY + 1, $iColorOld, $iColorNew) ;go south
        $iRec -= 1
    EndIf
    If ($iX - 1) > -1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX - 1, $iY, $iColorOld, $iColorNew) ;go west
        $iRec -= 1
    EndIf
    If ($iY - 1) > -1 Then
        $iRec += 1
        _GDIPlus_FloodFillRec($hBitmap, $iX, $iY - 1, $iColorOld, $iColorNew) ;go north
        $iRec -= 1
    EndIf
    Return 1
EndFunc

Func UpdateView()
    _GDIPlus_GraphicsDrawImage($hGfx, $hImage, 0, 0)
EndFunc
;
Func StackAdd(Byref $aStack, $SVal,ByRef $iStack)
    If $iStack+2 > UBound($aStack) then ReDim $aStack[$iStack+500]
    $aStack[$iStack] = $SVal
    $iStack += 1
EndFunc
;
Func StackDelete(ByRef $aStack,Byref $iStack)
    $iStack -= 1
EndFunc

[UEZ]

Thanks guys!

Currently I was doing also some tuning for the stack implementation but the array was implemented just to test whether it will work or not.

One of my ideas was also to use dictionary object as suggested by KaFu.

Br,

UEZ

[UEZ]

Here the Scripting Dictionary iterative version

expandcollapse popup

#include <GDIPlus.au3>

$sRegPath = "HKLM\SOFTWARE\AutoIt v3\AutoIt"
If StringInStr("X64IA64", @OSArch) Then $sRegPath = StringReplace($sRegPath, "SOFTWARE", "SOFTWARE\Wow6432Node")

_GDIPlus_Startup()
$hImage = _GDIPlus_ImageLoadFromFile(RegRead($sRegPath, "InstallDir") & "\Examples\GUI\logo4.gif")
$iW = _GDIPlus_ImageGetWidth($hImage)
$iH = _GDIPlus_ImageGetHeight($hImage)
$hGUI = GUICreate("Test", $iW, $iH)
GUISetState()
$hGfx = _GDIPlus_GraphicsCreateFromHWND($hGUI)
AdlibRegister("UpdateView", 10)

$iColor2Fill = 0xFFFFFFFF
_GDIPlus_FloodFillIter2($hImage, 0, 0, 0xFF000080, 0xFFFFFF00)
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & "\Filled.png")
;~ ShellExecute(@ScriptDir & "\Filled.png")
AdlibUnRegister("UpdateView")
ConsoleWrite("Done" & @LF)
Do
Until GUIGetMsg() = -3

_GDIPlus_ImageDispose($hImage)
_GDIPlus_GraphicsDispose($hGfx)
_GDIPlus_Shutdown()
Exit

Func _GDIPlus_FloodFillIter2(ByRef $hBitmap, $iX, $iY, $iColorOld, $iColorNew) ;coded by UEZ 2013-01-13
    Local $aResult = DllCall($ghGDIPDll, "uint", "GdipGetImageDimension", "handle", $hBitmap, "float*", 0, "float*", 0)
    Local $iW = $aResult[2], $iH = $aResult[3]
    If BitOR($iX < 0, $iY < 0, $iX > $iW - 1, $iY > $iH - 1) Then Return SetError(1, 0, 0)
    Local $x, $y, $i = 1
    Local $oD = ObjCreate('Scripting.Dictionary')
    $oD.Add($i, $iX & ";" & $iY) ;push
    $i += 1
    While $oD.Count > 0
        $sPoint = $oD.Item($i - 1)
        $oD.Remove($i - 1) ;pop
        $i -= 1
        $x = Int(StringRegExpReplace($sPoint, "(\d+);\d+", "$1"))
        $y = Int(StringRegExpReplace($sPoint, "\d+;(\d+)", "$1"))
        If BitOR($x < 0, $y < 0, $x > $iW - 1, $y > $iH - 1) Then ContinueLoop
        $aResult = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint*", 0)
        If $aResult[4] = "0x" & Hex($iColorOld, 8) Then
            DllCall($ghGDIPDll, "uint", "GdipBitmapSetPixel", "handle", $hBitmap, "int", $x, "int", $y, "uint", $iColorNew)
            $oD.Add($i, $x + 1 & ";" & $y) ;push
            $i += 1
            $oD.Add($i, $x & ";" & $y + 1) ;push
            $i += 1
            $oD.Add($i, $x - 1 & ";" & $y) ;push
            $i += 1
            $oD.Add($i, $x & ";" & $y - 1) ;push
            $i += 1
        EndIf
    WEnd
    $oD = 0
    Return 1
EndFunc   ;==>_GDIPlus_FloodFillIter2

Func UpdateView()
    _GDIPlus_GraphicsDrawImage($hGfx, $hImage, 0, 0)
EndFunc

@Jos: While $iStack > 0 must be While $iStack > 1, otherwise flooding will continue at 0, 0.

Br,

UEZ

[KaFu]

Now, well done, seems fast enough for me .

[Jon]

Maybe trancexx or Jon can comment here, but looking at the source it seems we have a 3900 limit for x64 and a 1900 limit for x86 for both Call and Execute while the helpfile states 5100.

Jos

It changes each version. I didn't even know it was in the helpfile. It should probably be removed.

[guinness]

It changes each version. I didn't even know it was in the helpfile. It should probably be removed.

Do I remove it?

[Mat]

Do I remove it?

Might be worth keeping a note that there is a recursion limit. It's one of those gotchas for people who haven't programmed before that still comes up as a question from time to time.

[guinness]

But how to word it so it doesn't raise questions of: What is the limit?

[Mat]

But how to word it so it doesn't raise questions of: What is the limit?

When you call a function, an entry ("frame") is added to the call stack. Further nested function calls add to this stack and returning from a function removes its entry. The call stack has a fixed size, which depends on the version of AutoIt being run, but is made large enough that it should only be overflowed by very deep or infinite recursion. If a function is likely to call itself more than 1000 times then you should switch to an iterative method (one involving loops).

That's a very rough attempt. Does have to give some sort of reference to the stack size being in the order of a thousand.

[jchd]

I can't say. If the call stack is direct and fixed size, the limit should strongly depend on the number, type and size of parameters pushed at each round. If the stack is indirect, then merely depends on 32- vs 64-bit and release (but in this case it's questionable that a recursion limit even exists, beside process memory exhausted). Only devs can say for sure.

In the later case, maybe a simple runable script made available online would avoid too many "how much" questions, so that users can actually determine themselves which is the limit for the installation they use. If the former style is in fact in use, then users would have to try by themselves with the exact function prototype they use in their real-world application. All of this provided that OnAutoItExitRegister can actually run a function which prints a variable, which is far from obvious in case of stack overflow. But using ConsoleWrite can overcome the issue, as we're not talking about billion recursions/lines. Can't test that from where I am currently.

Edited January 14, 2013 by jchd

[AZJIO]

Can't test that from where I am currently.

_FuncName()
Func _FuncName($F = True, $L=0)
    MsgBox(0, 'Level', $L)
    If Not $F Then Return
    If $L = 5 Then $F = False
    _FuncName($F, $L+1)
EndFunc