Recursive function value seems to be copied even though passed by reference

I have a function that takes a reference to an array as an argument. It is callred recursively.


I find that the second time that the function is called, it seems to handle the parameter as a normal value type, copying it and not passing it by reference.


In the code below, I call createDataPoints with "A.B.C" as argument. It should create a data point named "A" and call addDataPoint with "B.C" as argument. This should add "B" as a child data point to "A" and call it with "C" as argument.


If I step through the code, it does all of this, and it seems to work correctly. But my original array, dataPoints only contains the result of the first call to addDataPoint(), which is "A" and it has zero children.


From what I can tell, it works correctly when addDataPoint() is called for the firt time at line 44, but not when it is called when it is called recursively at line 37.


What am I missing? I am expecting dataPoints (created line 48) to contain one item with name "A" which contains one child called "B" which contains a child called "C" after createDataPoints() line 49 has returned.


[ Paste the code below in a playground, or a command line app to step through it ]


import Foundation

struct DataPointInfo {
  var name: String
  var children = [DataPointInfo]()
  
  init(name: String) {
    self.name = name
  }
}

extension Array where Element == DataPointInfo {
  func dataPointWithName<T:StringProtocol>(name: T) -> DataPointInfo? {
    for dataPoint in self {
      if dataPoint.name == name {
        return dataPoint
      }
    }
    return nil
  }
}

let name1 = "A.B.C"
let name2 = "A.B.D"
let name3 = "A.Last"
let names = [name1] // ,name2, name3]

func addDataPoint(parentLevel: inout [DataPointInfo], parts: [Substring]) {
  if parts.count == 1 {
    parentLevel.append(DataPointInfo(name: String(parts[0])))
  } else {
    var parent = parentLevel.dataPointWithName(name: parts[0])
    if (parent == nil) {
      parent = DataPointInfo(name: String(parts[0]))
      parentLevel.append(parent!)
    }
    addDataPoint(parentLevel: &parent!.children, parts: Array(parts.suffix(from: 1)))
  }
}

func createDataPoints(names: [String]) {
  for name in names {
    let parts = name.split(separator: ".")
    addDataPoint(parentLevel: &dataPoints, parts: parts)
  }
}

var dataPoints = [DataPointInfo]()
createDataPoints(names: names)

Accepted Reply

No, I think your code is wrong. This kind of complexity makes may head hurt, so I might be misunderstanding but …


When you get to line 37, parent contains a DataPointInfo struct that's local. That is, as a value type in a local variable, it's a copy of the value in the array. Adding a child to this value in line 37 doesn't change the array passed in as parentLevel. As soon as this instance of the recursive function exits, the parent value is discarded, and your function effectively did nothing.


If you need to stick with value semantics, your dataPointWithName function should return an index into the array, not a value from the array. You can then append to the right instance (parentLevel[index].children) in line 37.


However, you probably want reference semantics for DataPointInfo (class rather than struct). The inout parameter is a bit of a code smell here. You use it because you want references but don't have them. Having them from the get-go will likely simplify everything.

Replies

No, I think your code is wrong. This kind of complexity makes may head hurt, so I might be misunderstanding but …


When you get to line 37, parent contains a DataPointInfo struct that's local. That is, as a value type in a local variable, it's a copy of the value in the array. Adding a child to this value in line 37 doesn't change the array passed in as parentLevel. As soon as this instance of the recursive function exits, the parent value is discarded, and your function effectively did nothing.


If you need to stick with value semantics, your dataPointWithName function should return an index into the array, not a value from the array. You can then append to the right instance (parentLevel[index].children) in line 37.


However, you probably want reference semantics for DataPointInfo (class rather than struct). The inout parameter is a bit of a code smell here. You use it because you want references but don't have them. Having them from the get-go will likely simplify everything.

IO ionstrumented your code (what you should do in such case), with a counter var :


var counter = 0

extension Array where Element == DataPointInfo {
    func dataPointWithName(name: T) -> DataPointInfo? {
        print("->1 dataPointWithName", name, self)
        for dataPoint in self {
            print("->2 dataPoint.name", dataPoint.name, name)
            if dataPoint.name == name {
                return dataPoint
            }
        }
        return nil
    }
}


let name1 = "A.B.C"
let name2 = "A.B.D"
let name3 = "A.Last"
let names = [name1] // ,name2, name3]


func addDataPoint(parentLevel: inout [DataPointInfo], parts: [Substring]) {
    counter += 1
    print("->3 ", counter, parentLevel, parts)
    if parts.count == 1 {
        parentLevel.append(DataPointInfo(name: String(parts[0])))
    } else {
        var parent = parentLevel.dataPointWithName(name: parts[0])
        print("->4 parent", parent, parts[0])
        if (parent == nil) {
            parent = DataPointInfo(name: String(parts[0]))
            parentLevel.append(parent!)
        }
        addDataPoint(parentLevel: &parent!.children, parts: Array(parts.suffix(from: 1)))
    }
}

func createDataPoints(names: [String]) {
    for name in names {
        let parts = name.split(separator: ".")
        addDataPoint(parentLevel: &dataPoints, parts: parts)
    }
}

And get the following:

->3 1 [] ["A", "B", "C"]

->1 dataPointWithName A []

->4 parent nil A

->3 2 [] ["B", "C"]

->1 dataPointWithName B []

->4 parent nil B

->3 3 [] ["C"]



So, parentLevel.dataPointWithName(name: parts[0]) is always nil.

Because dataPointWithName is always an empty array in extension Array where Element == DataPointInfo

You should investigate why.

Thanks. I got sucked in to trying to make everythig Structs recently and it never occured to me that line 37 was the place where I made the copy.

I did instrument my code as Claude31 suggested (did this before posting, but cleaned up before posting) but did not pick it up since it looked correct up to the point where I called my function again, becasue at that point it would not longer change the parent, now I know why.

Thanks for pointing out my error so quickly.