Dynamic array as type member not allowed.. why not? WHY!!

For other topics related to the FreeBASIC project or its community.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Dynamic array as type member not allowed.. why not? WHY!!

Postby AGS » Mar 07, 2012 4:32

Apart from OO related language features the feature "possibility to have dynamic arrays as part of type declaration" must be one of those features that is high on the wishlist of fb programmers.

I've looked around on the forum for answers to the question why you can't use a dynamic array as a member of a type but found very little. Perhaps I should have searched a little better but apart from lots of posts describing 'workarounds' (basically hacks to make up for the lack of support for dynamic arrays in type declarations) I found nothing.

I did find a feature request on sourceforge requesting dynamic arrays as part of a type declaration
http://sourceforge.net/tracker/?func=de ... tid=693199

The request was dated 2008.

As "dynamic arrays as part of a type declaration" is high on the wishlist of fb programmars you'd think it's high on the TODO list of the fb devs. But it's not even on the 'official' TODO list. I don't think it has ever been on the TODO list. That could mean a couple of things.

The most likely reason would be that the toolchain used (mingw/gcc) does 'something' that makes it impossible to have dynamic arrays as part of a type declaration. I don't know what that 'something' is but it could be a low - level, unsolvable binary problem.

A less likely reason would be that changing the implementation of dynamic arrays takes too much time. Perhaps it involves changing a substantial part of the source code. Who knows?

But I think that's exactly the problem: who knows? I don't and I have been on this forum since 2007. And the answers given to programmers new to fb asking about the lack of support for dynamic arrays usually amount to: 'can't do that, it's not possible'. Yet no real explanation is given (why is it not possible? why has it not been implemented?).

The manual tells you this about dynamic arrays:
ReDim cannot be used on fixed-size arrays - i.e. arrays with constant bounds made with Dim. This includes arrays contained in UDTs (user-defined Types), because currently only fixed-size arrays are supported in UDTs. This also includes fixed-length arrays passed as parameters in a function. FreeBASIC cannot prevent you trying this at compile-time, but the results at run-time will be undefined


So... who can explain (in plain English) why using dynamic arrays as part of a type declaration will result in undefined run-time behaviour? And what, if anything, can be done so we can use dynamic arrays as part of type declarations (or union declarations).
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby TJF » Mar 07, 2012 7:47

I agree: dynamic arrays are important and I also didn't find an explanation why they aren't implemented yet.

Just a guess: memory for dynamic arrays is reserved by the ALLOCATE / CALLOCATE functions. But these functions are not thread save on all platforms.

When we introduced 'Geany mode' in h_2_bi you found a bug regarding this matter: running as a Geany thread h_2_bi couldn't allocate a second block of memory under win32.

But this is not a killer issue for dynamic arrays in UDTs. FB can allocate memory in the way STRING memory is allocated. That works thread-safe on all platforms. It may be a little slower but it works well in h_2_bi, libFBla, VarField, BitArray, ...
1000101
Posts: 2556
Joined: Jun 13, 2005 23:14
Location: SK, Canada

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby 1000101 » Mar 07, 2012 18:53

Dynamic arrays, like strings, are quirk datatypes. While strings have been implemented, dynamic arrays are more complex, require more data and require a lot of special case code to properly process. Further, if you are at the point where you need arrays in complex types then you are better served by managing your memory directly and not using an inefficient dynamic array anyway. FB has had only limited support for dynamic arrays and it was always intended that you should directly manage your own variadic memory pools.

Q) Why doesn't fb have dynamic arrays in structs?
A) Same reason cars don't have wings, boats don't have rocket engines and the space shuttle doesn't have a wet bar - Not intended for that purpose.

Don't complain about it, it will never happen as it isn't in the design.
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby TJF » Mar 07, 2012 20:45

I've seen cars with wings and boats with rocket engines.

Don't get me wrong. I don't miss dynamic arrays in UDTs since I found my workaround in the VarField project (with the given FB design).

But I think I'm not cleverer than the FB developers. What I can implement in a few hours as an FB code extension they can implement in the FB compiler as well.
1000101
Posts: 2556
Joined: Jun 13, 2005 23:14
Location: SK, Canada

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby 1000101 » Mar 08, 2012 2:05

I wasn't saying it couldn't be done just that it's not likely so don't expect it. Also, implementing your own method will undoubtedly be optimal over a one-size-fits-all solution.

And yes, I have seen boats with rocket engines and cars with wings too. For that matter I've seen semi's with jet engines but that wasn't really my point. :P
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Postby AGS » Mar 11, 2012 11:41

One of the reasons why I want to know why it does not work has to do with possible workarounds.

If I (and others) do not know the reason for 'no dynamic array allowed in udt' than any solution I
come up with might suffer from the same problems as the current implementation of UTDs.

As TJF pointer out there is an issue with memory allocation on win32. Something goes wrong
when you try to combine dynamic memory allocation with the use of types (I think it's constructor related
but I'm not sure). The problem seems to be platform specific.
As far as I know calloc and malloc are thread safe on win32.

I do not completely agree with the explanation given by 1000101.

His explanation does not explain why a dynamic array inside a type is currently not possible
(even worse: using a dynamic array inside a type leads to your program crashing).

And as far as use cases for a dynamic array are concerned: a dynamic array as part of a type
would free the programmer from having to dabble with pointers himself.

A small drop in performance in exchange for not having to mess around with memory
allocation would be very convenient. I will gladly hand over memory management to the rtlib.

Programming data structures like lists/trees/other could be programmed so much
easier using dynamic arrays. Now I have to allocate and reallocate memory by hand.
Which is very error prone.

If changing the rtlib so dynamic arrays can be part of a type is extremely hard to get right
then so be it. I would still like to know wwwhhhyyy you can't have a dynamic array as part
of a type but I guess I am going to have to figure that one out for myself. If I find out
I will post a message somewhere on this forum (and no doubt I will add that text to the
wiki).

For now I'll just head over to http://datadraw.sourceforge.net/, slap
a fb back end onto datadraw and get that dynamic array inside a type by means of hacks
so atrocious you'll go blind just looking at them :)
marcov
Posts: 3049
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby marcov » Mar 11, 2012 12:10

TJF wrote:I agree: dynamic arrays are important and I also didn't find an explanation why they aren't implemented yet.

Just a guess: memory for dynamic arrays is reserved by the ALLOCATE / CALLOCATE functions. But these functions are not thread save on all platforms.


My guess would be that they require some initialization which needs some metadata (RTTI). That metadata is generated for the global symbol, but not for the dyn array nested in a struct.

That being said, while fixable in principle doesn't mean it is EASY. It might require reworking of the RTTI handling.
jevans4949
Posts: 1156
Joined: May 08, 2006 21:58
Location: Crewe, England

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby jevans4949 » Mar 11, 2012 19:46

Fundamental to UDTs is that they are of fixed length - so that an array of UDTs can sensibly be declared. You will find that when a (varying-length) STRING is declared within a TYPE, what you get is a string descriptor; the data content is elsewhere.

When an array is declared within a type, the space allocated is a multiple of the SIZEOF the variable type.

If a solution is required what is needed is a new type (ARRAYDESCRIPTOR?) which would have all the contents of the descriptor used in FreeBasic.

Builtin functions such as LBOUND and UBOUND would have to be modified.

Special attention would have to be given to arrays of ARRAYDESCIPTORS. Presumably the first index is into the array of descriptors, and the second into the array itself? You could even have arrays of arrays of ARRAYDESCRIPTORS.

Would one be allowed to have multiple dimensions to an array defined by ARRAYDESCRIPTOR? would you want to vary the number of dimensions?

And what is the syntax for defining the content of the array (integer/double/whatever?)
marcov
Posts: 3049
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby marcov » Mar 11, 2012 20:05

jevans4949 wrote:Fundamental to UDTs is that they are of fixed length - so that an array of UDTs can sensibly be declared.


You will find that when a (varying-length) STRING is declared within a TYPE, what you get is a string descriptor; the data content is elsewhere.


Both statements are true, but different things. The descriptor can be chosed fixed size, so the first statement still holds true. (the primary udt is constant). Of course this has consequences for serialization. The descriptor is typically a pointer to the data prefixed with some record:

The record contains some or all of the following:

- lbound, ubound,
- elementsize and
- a pointer to RTTI of the element (or special RTTI of the specific array type). This in case the array is special (e.g. another dynamic array). Runtime helpers can walk this RTTI to perform actions on e.g. new elements (e.g. zero them out)

RTTI are just compiler generated tables (arrays) of metadata.

If a solution is required what is needed is a new type (ARRAYDESCRIPTOR?) which would have all the contents of the descriptor used in FreeBasic.

Builtin functions such as LBOUND and UBOUND would have to be modified.


Not generalizing it, will cause bugreports for the odd cases to pile up in time. As legacy builds, changing only gets more painful.

Special attention would have to be given to arrays of ARRAYDESCIPTORS. Presumably the first index is into the array of descriptors, and the second into the array itself? You could even have arrays of arrays of ARRAYDESCRIPTORS.


See above for _a_ way that it is handled. This also allows combinations of other "special" types.

Would one be allowed to have multiple dimensions to an array defined by ARRAYDESCRIPTOR? would you want to vary the number of dimensions?


We (FPC) don't. The most important reason is that VB doesn't, and we (or actually Delphi) aligned our dynamic array type with COM.

It is possible, but makes codegeneration for array indexing magnitudes more complex (you always need a mul anyway), and complicates helpers. The latter can have an overall slowing effect on the more commonly used (one dimension) effect.


If the special type also
And what is the syntax for defining the content of the array (integer/double/whatever?)


Why limit it? If you rework it, in principle all types (UDT or not) should be allowed to be element types. Of course there can be exceptions (e.g. for types with external memory management), but they should be the exception rather than the rule.
dkl
Site Admin
Posts: 3217
Joined: Jul 28, 2005 14:45
Location: Germany

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby dkl » Mar 11, 2012 23:30

I'm sure dynamic array descriptors inside UDTs can be done, 1) the field declaration and Redim parsers must be updated to allow it, that's trivial in theory, and 2) dynamic arrays must be treated as fake objects with constructor/destructor like dynamic strings, that requires some more extensive work on the compiler, but I'd know where to start because I did something similar for temporary wstrings. Currently there only seems to be a hack in place which cleans up local dynamic arrays at scope exits but not global ones after program exit.

Seeing that dynamic array descriptors contain information like sizeof(array_element), they couldn't just be zero-initialized like dynamic strings, but would have to use a constructor. There'd be worse usage restrictions than with dynamic strings, although they're no problem once you know about them.
creek23
Posts: 261
Joined: Sep 09, 2007 1:57
Location: Philippines
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby creek23 » Mar 12, 2012 4:16

I'm posting to let the FBC dev know that I also want this feature.

I was using a lot of this Dynamic Array inside Types from my old VB6 app... But when I ported it to FB, I have to use Pointers instead. But every once in a while I get these weird crashes -- not always. Instead of further developing the app, I keep coming back patching the code which is really frustrating.

If only this feature gets done. :(

~creek23
1000101
Posts: 2556
Joined: Jun 13, 2005 23:14
Location: SK, Canada

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby 1000101 » Mar 12, 2012 6:04

jevans4949 wrote:If a solution is required what is needed is a new type (ARRAYDESCRIPTOR?) which would have all the contents of the descriptor used in FreeBasic.

Builtin functions such as LBOUND and UBOUND would have to be modified.

Special attention would have to be given to arrays of ARRAYDESCIPTORS. Presumably the first index is into the array of descriptors, and the second into the array itself? You could even have arrays of arrays of ARRAYDESCRIPTORS.

Would one be allowed to have multiple dimensions to an array defined by ARRAYDESCRIPTOR? would you want to vary the number of dimensions?

And what is the syntax for defining the content of the array (integer/double/whatever?)


That all already exists and is done exactly as you describe (FB_ARRAYDESC, FB_ARRAYDESCLEN, FB_ARRAYDESC_DIMLEN (see stabs.bas)). As I said previously and as dkl emphasized (though not directly) in his response, dynamic arrays are quirk datatypes which require special case handling in complex situations (new/delete, scope, etc). Although I did not go into the specifics of why it is none the less the case.

Download the fbc source from sourceforge and you will see there is quite a lot of complex code already in place to handle arrays and strings. (Strings are really just even quirkier quirky arrays, btw).

As to thread safety of code on a specific platform, it's a directly related issue but it beyond the scope of this conversation and poses it's own problems to deal with when writing code "which should work."
marcov
Posts: 3049
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby marcov » Mar 12, 2012 12:13

1000101 wrote:
As to thread safety of code on a specific platform, it's a directly related issue but it beyond the scope of this conversation and poses it's own problems to deal with when writing code "which should work."


Making element level access threadsafe comes at a significant cost. (since every array access will have to be locked, and thus a loop iterating over the elements has the lock cost times the loopcount)
gothon
Posts: 224
Joined: Apr 11, 2011 22:22

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby gothon » Mar 13, 2012 7:11

When I first discovered FB, I was translating code from VB that used dynamic arrays in UDTs as well. The workarround I developed to solve the issue is nearly perfect now. I too would like to see this implemented in the language itself, but its not really necessary given that I was able to implement the needed functionality myself.

Because FB supports types containing constructors, destructors, and copiers (eg: overloaded let operator), implementing dynamic memory types that behave perfectly is doable. Furthermore use of the high level new[] and delete[], operators to allocate the memory ensures that these functions will be called. And, the use of Macros allows for a variable data type without circumventing type checking.

Thus my solution is simple yet powerful. It can handle any combination of types containing arrays containing types...etc. However, I have not implemented the extra features of custom LBound or multidimensional arrays. But, the essential work of automatically managing the memory is done. User defined LBound and multidimensional arrays can be fashioned manually by adding members for LBound and additional dimensions, and doing arithmetic with these values on indexes when accessing elements.

Implementing something similar into FB itself would be quite a bit harder but the principle is the same; it could definitely be done if someone is willing to do it. I'm not sure about the thread safety issues though; this seems to be yet another complication to the correct implementation of this feature.

My workarround ex:

Code: Select all

#Include Once "VarArray.bi"

Type Point
    As Double X, Y
End Type

'Define the VarArray_Point type using macros:
VA_DECLARE_WRAPPER(Point)
VA_WRAPPER(Point)

Type Polyline
    Verts As VarArray_Point
    Color As UInteger
End Type

Dim I As Integer
Dim P As Polyline

Randomize
P.Verts.ReDim_(Rnd * 10 - 1)
P.Color = RGB(Rnd*254, Rnd*254, Rnd*254)

For I = 0 To P.Verts.UBound_
    'Use the property function to safely access the data when running in a debugger
    P.Verts.P(I)->X = Rnd * 100
    P.Verts.P(I)->Y = Rnd * 100
    'Or access it directly for speed
    P.Verts.A[I].X = Rnd * 100
    P.Verts.A[I].Y = Rnd * 100
Next I

ScreenRes 320, 200, 32

For I = 0 To P.Verts.UBound_ - 1
    With P.Verts
        Line (.A[I].X, .A[I].Y)-(.A[I+1].X, .A[I+1].Y), P.Color
    End With
Next I

Sleep


VarArray.bi

Code: Select all

#Ifndef NULL
#Define NULL 0
#EndIf

#Ifndef VA_UBOUND
#Define VA_UBOUND(ARRAY) ARRAY##_UBound

#MACRO VA_EXTERN(ARRAY, VARTYPE)
    Extern ARRAY As VARTYPE Ptr
    Extern ARRAY##_UBound As Integer
#ENDMACRO

#MACRO VA_DIM(ARRAY, VARTYPE)
    Dim ARRAY As VARTYPE Ptr = NULL
    Dim ARRAY##_UBound As Integer = -1
#ENDMACRO

#MACRO VA_DIM_SHARED(ARRAY, VARTYPE)
    Dim Shared ARRAY As VARTYPE Ptr = NULL
    Dim Shared ARRAY##_UBound As Integer = -1
#ENDMACRO

#MACRO VARARRAY(ARRAY, VARTYPE)
    ARRAY As VARTYPE Ptr = NULL
    ARRAY##_UBound As Integer = -1
#ENDMACRO

' Same Effect as VA_ReDim(ARRAY, -1)
#MACRO VA_FREE(ARRAY)
    If ARRAY <> NULL Then Delete[] ARRAY
    ARRAY = NULL
    ARRAY##_UBound = -1
#ENDMACRO

#MACRO VA_ERASE(ARRAY)
    VA_FREE(ARRAY)
#ENDMACRO

#MACRO VA_LET(ARRAY_LHS, ARRAY_RHS)
    If ARRAY_LHS <> NULL Then Delete[] ARRAY_LHS
    ARRAY_LHS = New TypeOf(*(ARRAY_RHS))[ARRAY_RHS##_UBound + 1]
    ARRAY_LHS##_UBound = ARRAY_RHS##_UBound
    Scope
        For Temp_Array_Index As Integer = 0 To ARRAY_RHS##_UBound
            ARRAY_LHS[Temp_Array_Index] = ARRAY_RHS[Temp_Array_Index]
        Next Temp_Array_Index
    End Scope
#ENDMACRO

#MACRO VA_REDIM(ARRAY, NEW_UBOUND)
    If ARRAY <> NULL Then Delete[] ARRAY
    ARRAY##_UBound = (NEW_UBOUND)
    If NEW_UBOUND < 0 Then
        ARRAY = NULL
    Else
        ARRAY = New TypeOf(*(ARRAY))[ARRAY##_UBound + 1]
    End If
#ENDMACRO

#MACRO VA_REDIM_PRESERVE(ARRAY, NEW_UBOUND)
    If NEW_UBOUND < 0 Then
        ARRAY = NULL
    Else
        If ARRAY = NULL Then
            ARRAY = New TypeOf(*(ARRAY))[(NEW_UBOUND) + 1]
        Else
            Scope
                Dim Temp_Array_Ptr As TypeOf(ARRAY) = New TypeOf(*(ARRAY))[(NEW_UBOUND) + 1]
                Dim Temp_Array_Index As Integer
                If (NEW_UBOUND) > ARRAY##_UBound Then
                    For Temp_Array_Index = 0 To ARRAY##_UBound
                        Temp_Array_Ptr[Temp_Array_Index] = ARRAY[Temp_Array_Index]
                    Next Temp_Array_Index
                Else
                    For Temp_Array_Index = 0 To (NEW_UBOUND)
                        Temp_Array_Ptr[Temp_Array_Index] = ARRAY[Temp_Array_Index]
                    Next Temp_Array_Index
                End If
                Delete[] ARRAY
                ARRAY = Temp_Array_Ptr
            End Scope
        End If
    End If
    ARRAY##_UBound = (NEW_UBOUND)
#ENDMACRO

#MACRO VA_DECLARE_WRAPPER(VARTYPE)
    Type VARARRAY_##VARTYPE
        VARARRAY(A, VARTYPE)
       
        Declare Constructor
        Declare Constructor(New_UBound As Integer)
        Declare Constructor(Source As VARARRAY_##VARTYPE)
        Declare Destructor
       
        Declare Operator Let(Rhs As VARARRAY_##VARTYPE)
        Declare Operator Cast () As VARTYPE Ptr
       
        Declare Property P(ByVal Index As Integer) As VARTYPE Ptr
        Declare Property V(ByVal Index As Integer) As VARTYPE
        Declare Property V(ByVal Index As Integer, ByVal Rhs As VARTYPE)
        Declare Sub ReDim_(ByVal New_UBound AS Integer)
        Declare Sub ReDim_Preserve_(ByVal New_UBound AS Integer)
        Declare Function UBound_() As Integer
    End Type
#ENDMACRO

#MACRO VA_WRAPPER(VARTYPE)
    Constructor VARARRAY_##VARTYPE
        'No Initialization Needed
    End Constructor
   
    Constructor VARARRAY_##VARTYPE(New_UBound As Integer)
        VA_ReDim(A, New_UBound)
    End Constructor
   
    Constructor VARARRAY_##VARTYPE(Source As VARARRAY_##VARTYPE)
        VA_LET(A, Source.A)
    End Constructor

    Destructor VARARRAY_##VARTYPE
        VA_FREE(A)
    End Destructor
   
    Operator VARARRAY_##VARTYPE.Let(Rhs As VARARRAY_##VARTYPE)
        VA_LET(A, Rhs.A)
    End Operator
   
    Operator VARARRAY_##VARTYPE.Cast () As VARTYPE Ptr
        Return A
    End Operator
   
    Property VARARRAY_##VARTYPE.P(ByVal Index As Integer) As VARTYPE Ptr
        Assert(Index >= 0)
        Assert(Index <= VA_UBound(A))
        Return @(A[Index])
    End Property
   
    Property VARARRAY_##VARTYPE.V(ByVal Index As Integer) As VARTYPE
        Assert(Index >= 0)
        Assert(Index <= VA_UBound(A))
        Return A[Index]
    End Property
   
    Property VARARRAY_##VARTYPE.V(ByVal Index As Integer, ByVal Rhs As VARTYPE)
        Assert(Index >= 0)
        Assert(Index <= VA_UBound(A))
        A[Index] = Rhs
    End Property
   
    Sub VARARRAY_##VARTYPE.ReDim_(ByVal New_UBound AS Integer)
        VA_ReDim(A, New_UBound)
    End Sub
   
    Sub VARARRAY_##VARTYPE.ReDim_Preserve_(ByVal New_UBound AS Integer)
        VA_ReDim_Preserve(A, New_UBound)
    End Sub
   
    Function VARARRAY_##VARTYPE.UBound_() As Integer
        Return VA_UBound(A)
    End Function
#ENDMACRO
#EndIf 'VA_UBOUND
gothon
Posts: 224
Joined: Apr 11, 2011 22:22

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby gothon » Mar 13, 2012 12:18

AGS wrote:The manual tells you this about dynamic arrays:
ReDim cannot be used on fixed-size arrays - i.e. arrays with constant bounds made with Dim. This includes arrays contained in UDTs (user-defined Types), because currently only fixed-size arrays are supported in UDTs. This also includes fixed-length arrays passed as parameters in a function. FreeBASIC cannot prevent you trying this at compile-time, but the results at run-time will be undefined


So... who can explain (in plain English) why using dynamic arrays as part of a type declaration will result in undefined run-time behaviour?


I believe the manual here is referring to the use of redim on fixed length arrays passed to procedures not to dynamic arrays in UDTs. This is because the compiler can prohibit you from declaring an array without explicit size in a UDT at compile time. However because the syntax is the same, the compiler can't tell whether an array passed as a parameter to a function is dynamic or static. Thus, it is possible to pass a static array to a function and use redim from within that function, and the compiler can't detect it as an error at compile time.

Return to “Community Discussion”

Who is online

Users browsing this forum: No registered users and 9 guests