[Papyrus] Script array limitation?

[ElPolloAzul]

Linked lists are only feasible with the lack of pointers in that you are allowed ObjectReferences. So the implementation necessarily involves the creation of "physically" instantiated objects (whether they are activators or MiscObjects) somewhere in the game world. It's not too surprising given that the save game format largely mirrors the plugin format in some parts and everything is tied to records. I think that the array limitation might have been viewed as a good thing in some behavioral sense. If you have to consciously resort to these shenanigans, you *might be* less likely to just create unbounded arrays and request hilariously too much space in a savegame with a bad loop (very easy to write). Across a mod ecosystem with lots of different authors, chasing down lots of memory without an accounting of who owned it (the accounting tight coupling with a record/OR/RefID implies) might be unpleasant. So there is a maybe unintended protective effect of Bethesda's choice here.

FormID exhaustion could be a realistic problem, but pretty much every effect and short-lived entity (including some projectiles?) in the game uses one, so the long-term sustainability problem is potentially there anyway. It matters what the real consequences of invoking Delete and other tools are, and in turn, it matters what solution BGS actually used in between now and original Oblivion.

Some people who have been here for Shivering Isles remember the reference bug triggered at least by the Golden Saint guards in Mania's Greenmote Silo. The patch for that bug introduced a new-at-the-time method for recycling ephemeral FormIDs in the FF range that reportedly also used some of the unallocated, unloaded sub-FF range. In SI, though, the scripts were generating at least several RefIDs per frame!

So the linked list possibility using the cheesing approach is not just academic. From an old and less tested version (that still bears the very ugly debug comments and I'm quite sure obvious bugs) of the script in Papyrus Computer Club:

Scriptname PapyrusGun:EPAArrayList extends ObjectReference

var[] Property raw_array Auto
PapyrusGun:EPAArrayList Property nextSegment Auto
PapyrusGun:EPAArrayList Property tailSegment Auto

int Property currentSize Auto
int Property currentCapacity Auto
int Property currentSegmentCount Auto

bool Property isHead Auto

ObjectReference Property monadRef Auto Const
MiscObject Property BreadBoxProto Auto Const

Function Initialize()

	self.nextSegment = None
	self.tailSegment = self

	if self.isHead
		currentSize = 0
		currentCapacity = 100
		currentSegmentCount = 1
	else
		currentSize = -1
		currentCapacity = -1
		currentSegmentCount = -1
	endif

	self.raw_array = new var[100]

EndFunction

PapyrusGun:EPAArrayList Function ConstructMe(ObjectReference localMonad, Form arrayProto, bool makeHead) global
	PapyrusGun:EPAArrayList newRef = localMonad.PlaceAtMe(arrayProto, 1,1,1,0) as PapyrusGun:EPAArrayList
	newRef.isHead = makeHead
	newRef.Initialize()
	return newRef
EndFunction

PapyrusGun:EPAArrayList Function DestructMe()

	int segmentIdx = currentSegmentCount - 1

	while segmentIdx > 0
		GetSegment(segmentIdx).DestructMe()
		segmentIdx -= 1
	endwhile

	self.Delete()

EndFunction

int Function RFind(var object)
	int objFind = -1

	int segmentIdx = currentSegmentCount - 1
	while segmentIdx >= 0
		int candObjFind = GetSegment(segmentIdx).raw_array.find(object)
		if candObjFind != -1
			return Math.Floor(segmentIdx*100.0 + candObjFind)
		endif
		segmentIdx -= 1
	endwhile

	return objFind
EndFunction

int Function SequentialFind(var object, var[] arrayObj) global
 	int arrayIdx = 0
	string stringObj = object as String
	Form formObj = object as Form
	while arrayIdx <= arrayObj.length - 1
		if stringObj == arrayObj[arrayIdx] as String
			return arrayIdx
		elseif formObj == arrayObj[arrayIdx] as Form && (object as Form != None)
			return arrayIdx
	;	elseif object as Int == arrayObj[arrayIdx] as Int && (object as Int) > 0
	;		return arrayIdx
		;elseif object as Float == arrayObj[arrayIdx] as Float
	;		return arrayIdx
		endif
		arrayIdx += 1
	endwhile

	return -1
EndFunction

int Function Find(var object)
	int objFind = -1

	int segmentIdx = 0
	while segmentIdx <= currentSegmentCount - 1
		int candObjFind = SequentialFind(object,GetSegment(segmentIdx).raw_array)
		if candObjFind != -1
		;	debug.notification("Find at " + segmentIdx + ": " + candObjFind)
			return Math.Floor(segmentIdx*100.0 + candObjFind)
		endif
		segmentIdx += 1
	endwhile

	return objFind
EndFunction

PapyrusGun:EPAArrayList Function GetSegment(int segmentIndex)
	
	PapyrusGun:EPAArrayList traverser = self
	
	if segmentIndex >= currentSegmentCount
		;debug.notification("Segment fault " + segmentIndex)
		return None
	endif

	int segmentIdx = 0
	while segmentIdx < currentSegmentCount && traverser != None
		if segmentIdx == segmentIndex
			return traverser
		endif
		traverser = traverser.nextSegment
		segmentIdx += 1
	endwhile

	;debug.notification("Couldn't find segment " + segmentIndex + ": " + segmentIdx + ":" + currentSegmentCount)

EndFunction

var Function GetAt(int index)
	
	if index >= currentSize
		return None
	endif
	
	int segIdx = Math.Floor(index / 100.0)
	int partIdx = index % 100
	var returnObj = GetSegment(segIdx).raw_array[partIdx]
	;if returnObj as String == None
	;	debug.notification("Fetching object @ " + index + "," + segIdx + "," + partIdx)
;	endif
	return returnObj

EndFunction

PapyrusGun:EPAArrayList Function BlockCopy(int indexStart, int indexEnd, PapyrusGun:EPAArrayList destArrayNew)

	if destArrayNew == None
;		debug.notification("Empty Array")
	endif
;	debug.notification("BLOCKCOPY " + indexStart + ": " + indexEnd + " of " + destArrayNew)

	int capNeeded = indexEnd - indexStart
	int segCapNeeded = Math.Floor(capNeeded / 100.0)
	PapyrusGun:EPAArrayList destArray = destArrayNew;PapyrusGun:EPAArrayList.ConstructMe(monadRef, BreadBoxProto, 1)

	int expandIdx = 0
	while expandIdx < segCapNeeded
		destArray.ExpandArray()
		expandIdx += 1
	endwhile
	
	int segIdx = Math.Floor(indexStart/ 100.0)
	int partIdx = indexStart % 100
	int lastSegIdx = -1
	int lastPartIdx = -1
	int traverserIdxIn = indexStart
	int traverserIdxOut = 0
	int segIdxOut = -1
	PapyrusGun:EPAArrayList curSegIn
	PapyrusGun:EPAArrayList curSegOut

	while traverserIdxIn <= indexEnd


		segIdx = Math.Floor(traverserIdxIn / 100.0)
		partIdx = traverserIdxIn % 100
 
		if segIdx != lastSegIdx
			lastSegIdx = segIdx
			curSegIn = self.GetSegment(segIdx)
			segIdxOut += 1
			curSegOut = destArray.GetSegment(segIdxOut)
		endif

		curSegOut.raw_array[traverserIdxOut] = curSegIn.raw_array[traverserIdxIn]
		destArray.currentSize += 1

		traverserIdxIn += 1
		traverserIdxOut += 1
	endwhile

;	debug.notification("DESTARRAY SIZE " + destArray.currentSize)
	return destArray

EndFunction

Function SetAt(int index, var obj)
	
	while (index + 1) > currentCapacity
		ExpandArray()
	endwhile

	int segIdx = Math.Floor(index / 100.0)
	int partIdx = index % 100
	GetSegment(segIdx).raw_array[partIdx] = obj

	if index >= currentSize
		currentSize = index + 1
	endif

EndFunction

Function ExpandArray()
	tailSegment.nextSegment = PapyrusGun:EPAArrayList.ConstructMe(monadRef, BreadBoxProto, 0)
	tailSegment = tailSegment.nextSegment
	currentSegmentCount += 1
	currentCapacity += 100
EndFunction

Function DebugPrint()
	debug.notification("Item Count: " + currentSize)
	debug.notification("Item Capacity: " + currentCapacity)
	debug.notification("Segment Count: " + currentSegmentCount)
EndFunction

Function Push(var obj)

	while (currentSize + 1) > currentCapacity
		ExpandArray()
	endwhile
	int insertIdx = currentSize
	self.SetAt(insertIdx, obj)
	
EndFunction

var Function Pop()
	var thingContained = self.GetAt(currentSize-1)
	self.SetAt(currentSize-1, None)
	if currentSize > 0
		currentSize -= 1
	endif
	return thingContained
EndFunction

int Function PareDown()

	int segmentIdx = currentSegmentCount - 1
	int segmentsTossed = 0

	while segmentIdx > 0
		if (currentSize+100) < currentCapacity
		    segmentsTossed += 1
		    currentCapacity -= 100
		    GetSegment(segmentIdx).DestructMe()
		endif
		segmentIdx -= 1
	endwhile

	return segmentsTossed

EndFunction

That's why a community effort to produce a well-tested native data structures library might be useful (if Starfield or ES6 reuses Papyrus).

 

As for the structs, you can make a similarly embodied MyRecord type class that has all of the same fields -- it's true that there was an array restriction on structs!

Also, I feel like Papyrus is closer to a pared down Java (single inheritance, variable references, bytecode, garbage collection etc.) than a pared down C++.

[niston]

Aahh, var arrays, the stuff of nightmares :)

 

I'm tempted to try it out.

[SKKmods]

Next we shall place the whole papyrus subsystem in the 64K himemory area and use the A20 handler to manage it.

 

/old people