mirror of https://github.com/fadden/6502bench.git
510 lines
22 KiB
C#
510 lines
22 KiB
C#
/*
|
|
* Copyright 2019 faddenSoft
|
|
*
|
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
* you may not use this file except in compliance with the License.
|
|
* You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
using System;
|
|
using System.Collections.Generic;
|
|
using System.Diagnostics;
|
|
|
|
namespace SourceGen {
|
|
/// <summary>
|
|
/// Given a list of LocalVariableTables, this determines the mapping of values to symbols
|
|
/// at a specific offset.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// We guarantee that the label will be unique within its scope. This happens at two
|
|
/// different levels:
|
|
/// (1) If the local variable label is present in the main symbol table, we use the
|
|
/// "de-duplication" table to remap it. We try not to let this happen, but it can.
|
|
/// The symbol table is latched when the object is constructed.
|
|
/// (2) If the assembler doesn't define a way to re-use variable names, we make them
|
|
/// globally unique. [currently not needed]
|
|
///
|
|
/// De-duplication changes the label in *most* circumstances. We want to show the de-dup
|
|
/// form everywhere except for the LvTable editor and the Lv editor. Using the correct
|
|
/// string at the correct time is necessary for some basic editor operations:
|
|
/// - Double-click on the opcode of LDA [lvar]. The selection should jump to the specific
|
|
/// entry in the LvTable.
|
|
/// - Double-click on the operand of LDA [lvar]. The instruction operand editor should
|
|
/// open and offer to edit the de-dup form. Clicking on the shortcut button should open
|
|
/// the Lv editor, with the original label shown (and perhaps a warning about
|
|
/// non-uniqueness).
|
|
/// - Double-click on the LvTable. The table listing should show the original label.
|
|
/// - Click on a de-duped entry and verify that the correct cross-references exist.
|
|
///
|
|
/// To reduce confusion, the fact that something has been de-duped should be obvious.
|
|
///
|
|
/// A few quick clicks in the 2019-local-variables test should confirm these.
|
|
/// </remarks>
|
|
public class LocalVariableLookup {
|
|
/// <summary>
|
|
/// List of tables. The table's file offset is used as the key.
|
|
/// </summary>
|
|
private SortedList<int, LocalVariableTable> mLvTables;
|
|
|
|
/// <summary>
|
|
/// Reference to project, so we can query the Anattrib array to identify "hidden" tables.
|
|
/// </summary>
|
|
private DisasmProject mProject;
|
|
|
|
/// <summary>
|
|
/// Set to true when generating symbols for assemblers like 64tass, which assign a
|
|
/// special meaning to labels with leading underscores.
|
|
/// </summary>
|
|
private bool mMaskLeadingUnderscores;
|
|
|
|
/// <summary>
|
|
/// Set to true if we want all variables to be globally unique (because the assembler
|
|
/// can't redefine them).
|
|
/// </summary>
|
|
private bool mDoUniquify;
|
|
|
|
/// <summary>
|
|
/// List of all non-variable symbols, for uniquification. This is generated from the
|
|
/// project symbol table. When generating assembly sources, the labels are transformed
|
|
/// through the label map.
|
|
/// </summary>
|
|
private Dictionary<string, Symbol> mAllNvSymbols;
|
|
|
|
private Dictionary<string, string> mLabelMap;
|
|
|
|
/// <summary>
|
|
/// Label uniquification helper.
|
|
///
|
|
/// The BaseLabel does not change, but Label is updated by MakeUnique.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// LvLookup is run multiple times, and can be restarted in the middle of a run. It's
|
|
/// essential that UniqueLabel behaves deterministically. For this to happen, the
|
|
/// contents of SymbolTable can't change in a way that affects the outcome unless it
|
|
/// also causes us to redo the uniquification. This mostly means that we have to be
|
|
/// very careful about creating duplicate symbols, so that we don't get halfway through
|
|
/// the analysis pass and invalidate our previous work. It's best to leave
|
|
/// uniquification disabled until we're generating assembly source code.
|
|
///
|
|
/// The issues also make it hard to do the uniquification once, rather than every time we
|
|
/// walk the code. Not all symbol changes cause a re-analysis (e.g. renaming a user
|
|
/// label does not), and we don't want to fill the symbol table with the uniquified
|
|
/// names because it could block user labels that would otherwise be valid.
|
|
/// </remarks>
|
|
private class UniqueLabel {
|
|
public string BaseLabel { get; private set; }
|
|
public string Label { get; private set; }
|
|
private int Counter { get; set; }
|
|
|
|
public UniqueLabel(string baseLabel) {
|
|
Label = BaseLabel = baseLabel;
|
|
Counter = 0;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Updates the Label to be unique. Call this when a symbol is defined or
|
|
/// re-defined.
|
|
/// </summary>
|
|
/// <param name="symbolTable">Symbol table, for uniqueness check.</param>
|
|
public void MakeUnique(Dictionary<string, Symbol> allNvSymbols) {
|
|
// The main symbol table might have user-supplied labels like "ptr_2", so we
|
|
// need to keep testing against that. However, it should not be possible for
|
|
// us to clash with other uniquified variables. So we don't need to check
|
|
// for clashes in the UniqueLabel list.
|
|
//
|
|
// It *is* possible to clash with other variable base names, so we can't
|
|
// exclude variables from our SymbolTable lookup.
|
|
string testLabel;
|
|
do {
|
|
Counter++;
|
|
testLabel = BaseLabel + "_" + Counter;
|
|
} while (allNvSymbols.TryGetValue(testLabel, out Symbol unused));
|
|
Label = testLabel;
|
|
}
|
|
}
|
|
private Dictionary<string, UniqueLabel> mUniqueLabels;
|
|
|
|
/// <summary>
|
|
/// Duplicate label re-map. This is applied before uniquification.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// It's hard to do this as part of uniquification because the remapped base name ends
|
|
/// up in the symbol table, and the uniquifier isn't able to tell that the entry in the
|
|
/// symbol table is itself. The logic is simpler if we just rename the label before
|
|
/// the uniquifier ever sees it.
|
|
///
|
|
/// I feel like there has to be a simpler way to do this. This'll do for now.
|
|
/// </remarks>
|
|
private Dictionary<string, string> mDupRemap;
|
|
|
|
/// <summary>
|
|
/// Most recently processed offset.
|
|
/// </summary>
|
|
private int mRecentOffset;
|
|
|
|
/// <summary>
|
|
/// Symbols defined at mRecentOffset.
|
|
/// </summary>
|
|
private List<DefSymbol> mRecentSymbols;
|
|
|
|
/// <summary>
|
|
/// Cumulative symbols defined at the current offset.
|
|
/// </summary>
|
|
private LocalVariableTable mCurrentTable;
|
|
|
|
// Next point of interest.
|
|
private int mNextLvtIndex;
|
|
private int mNextLvtOffset;
|
|
|
|
/// <summary>
|
|
/// Constructor.
|
|
/// </summary>
|
|
/// <param name="lvTables">List of tables from the DisasmProject.</param>
|
|
/// <param name="project">Project reference.</param>
|
|
/// <param name="labelMap">Label map dictionary, used to rename the labels in
|
|
/// the project symbol table. May be null.</param>
|
|
/// <param name="maskLeadingUnderscores">If true, labels with leading underscores
|
|
/// will be prefixed.</param>
|
|
/// <param name="uniquify">Set to true if variable names cannot be redefined.</param>
|
|
public LocalVariableLookup(SortedList<int, LocalVariableTable> lvTables,
|
|
DisasmProject project, Dictionary<string, string> labelMap,
|
|
bool maskLeadingUnderscores, bool uniquify) {
|
|
mLvTables = lvTables;
|
|
mProject = project;
|
|
mLabelMap = labelMap;
|
|
mMaskLeadingUnderscores = maskLeadingUnderscores;
|
|
mDoUniquify = uniquify;
|
|
|
|
mCurrentTable = new LocalVariableTable();
|
|
mDupRemap = new Dictionary<string, string>();
|
|
if (uniquify) {
|
|
mUniqueLabels = new Dictionary<string, UniqueLabel>();
|
|
}
|
|
Reset();
|
|
}
|
|
|
|
public void Reset(bool rebuildSyms = true) {
|
|
mRecentOffset = -1;
|
|
mRecentSymbols = null;
|
|
mCurrentTable.Clear();
|
|
mUniqueLabels?.Clear();
|
|
mDupRemap.Clear();
|
|
if (mLvTables.Count == 0) {
|
|
mNextLvtIndex = -1;
|
|
mNextLvtOffset = mProject.FileDataLength;
|
|
} else {
|
|
mNextLvtIndex = 0;
|
|
mNextLvtOffset = mLvTables.Keys[0];
|
|
}
|
|
CreateAllSymbolsDict();
|
|
}
|
|
|
|
private void CreateAllSymbolsDict() {
|
|
// TODO(someday): we don't need to regenerate the all-symbols list if the list
|
|
// of symbols hasn't actually changed. Currently no way to tell.
|
|
|
|
Dictionary<string, string> labelMap = mLabelMap;
|
|
|
|
SymbolTable symTab = mProject.SymbolTable;
|
|
mAllNvSymbols = new Dictionary<string, Symbol>(symTab.Count);
|
|
foreach (Symbol sym in symTab) {
|
|
if (sym.SymbolSource == Symbol.Source.Variable) {
|
|
continue;
|
|
}
|
|
if (labelMap != null && labelMap.TryGetValue(sym.Label, out string newLabel)) {
|
|
// Non-unique labels may map multiple entries to a single entry. That's
|
|
// fine; our goal here is just to avoid duplication. Besides, any symbols
|
|
// being output as locals will have the local prefix character and won't
|
|
// be a match.
|
|
mAllNvSymbols[newLabel] = sym;
|
|
} else {
|
|
mAllNvSymbols[sym.Label] = sym;
|
|
}
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the symbol associated with the operand of an instruction.
|
|
/// </summary>
|
|
/// <param name="offset">Offset of start of instruction.</param>
|
|
/// <param name="operandValue">Operand value.</param>
|
|
/// <param name="type">Operand type. Should be ExternalAddress for DP ops, or
|
|
/// Constant for StackRel ops.</param>
|
|
/// <returns>Symbol, or null if no match found.</returns>
|
|
public DefSymbol GetSymbol(int offset, int operandValue, Symbol.Type type) {
|
|
AdvanceToOffset(offset);
|
|
return mCurrentTable.GetByValueRange(operandValue, 1, type);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the symbol associated with a symbol reference. If uniquification is enabled,
|
|
/// the unique-label map for the specified offset will be used to transform the
|
|
/// symbol reference.
|
|
/// </summary>
|
|
/// <param name="offset">Offset of start of instruction.</param>
|
|
/// <param name="symRef">Reference to symbol.</param>
|
|
/// <returns>Symbol, or null if no match found.</returns>
|
|
public DefSymbol GetSymbol(int offset, WeakSymbolRef symRef) {
|
|
AdvanceToOffset(offset);
|
|
|
|
// The symRef uses the non-uniquified symbol, so we need to get the unique value at
|
|
// the current offset. We may need to do this even when variables can be
|
|
// redefined, because we might have a variable that's a duplicate of a user label
|
|
// or project symbol.
|
|
|
|
// Start by applying the de-duplication map.
|
|
string label = symRef.Label;
|
|
if (mDupRemap.TryGetValue(symRef.Label, out string remap)) {
|
|
label = remap;
|
|
}
|
|
//Debug.WriteLine("GetSymbol " + symRef.Label + " -> " + label);
|
|
if (mUniqueLabels != null && mUniqueLabels.TryGetValue(label, out UniqueLabel ulab)) {
|
|
//Debug.WriteLine(" Unique var " + symRef.Label + " -> " + ulab.Label);
|
|
label = ulab.Label;
|
|
}
|
|
DefSymbol defSym = mCurrentTable.GetByLabel(label);
|
|
|
|
// In theory this is okay, but in practice the only things asking for symbols are
|
|
// entirely convinced that the symbol exists here. So this is probably a bug.
|
|
Debug.Assert(defSym != null);
|
|
|
|
return defSym;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Identifies the LocalVariableTable that defined the symbol reference.
|
|
/// </summary>
|
|
/// <param name="offset">Offset at which the symbol was referenced.</param>
|
|
/// <param name="symRef">Reference to symbol.</param>
|
|
/// <returns>Table index, or -1 if not found.</returns>
|
|
public int GetDefiningTableOffset(int offset, WeakSymbolRef symRef) {
|
|
// Get mDupRemap et. al. into the right state.
|
|
AdvanceToOffset(offset);
|
|
|
|
// symRef is the non-uniquified, de-duplicated symbol that was generated
|
|
// during the analysis pass. We either need to un-de-duplicate the label,
|
|
// or de-duplicate what we pull out of the Lv tables. The former requires
|
|
// a linear string search but will be faster if there are a lot of tables.
|
|
string label = UnDeDuplicate(symRef.Label);
|
|
|
|
// Walk backward through the list of tables until we find a match.
|
|
IList<int> keys = mLvTables.Keys;
|
|
for (int i = keys.Count - 1; i >= 0; i--) {
|
|
if (keys[i] > offset) {
|
|
// table comes after the point of reference
|
|
continue;
|
|
}
|
|
|
|
if (mLvTables.Values[i].GetByLabel(label) != null) {
|
|
// found it
|
|
return keys[i];
|
|
}
|
|
}
|
|
|
|
// if we didn't find it, it doesn't exist... right?
|
|
Debug.Assert(mCurrentTable.GetByLabel(label) == null);
|
|
return -1;
|
|
}
|
|
|
|
private string UnDeDuplicate(string label) {
|
|
foreach (KeyValuePair<string, string> kvp in mDupRemap) {
|
|
if (kvp.Value == label) {
|
|
return kvp.Key;
|
|
}
|
|
}
|
|
return label;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Restores a de-duplicated symbol to original form.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// Another kluge on the de-duplication system. This is used by the instruction
|
|
/// operand editor's "edit variable" shortcut mechanism, because trying to edit the
|
|
/// DefSymbol with the de-duplicated name ends badly.
|
|
/// </remarks>
|
|
/// <param name="sym">Symbol to un-de-duplicate.</param>
|
|
/// <returns>Original or un-de-duplicated symbol.</returns>
|
|
public DefSymbol GetOriginalForm(DefSymbol sym) {
|
|
string orig = UnDeDuplicate(sym.Label);
|
|
if (orig == sym.Label) {
|
|
return sym;
|
|
}
|
|
return new DefSymbol(sym, orig);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets a LocalVariableTable that is the result of merging all tables up to this point.
|
|
/// </summary>
|
|
/// <param name="offset">Target offset.</param>
|
|
/// <returns>Combined table.</returns>
|
|
public LocalVariableTable GetMergedTableAtOffset(int offset) {
|
|
AdvanceToOffset(offset);
|
|
return mCurrentTable;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Finds the closest table that is defined at or before the specified offset. Will
|
|
/// attempt to only return un-hidden tables, but will return a hidden table if no
|
|
/// others are available.
|
|
/// </summary>
|
|
/// <param name="offset">Target offset.</param>
|
|
/// <returns>The table's definition offset, or -1 if no tables were defined before this
|
|
/// point.</returns>
|
|
public int GetNearestTableOffset(int offset) {
|
|
int nearest = -1;
|
|
int nearestUnhidden = -1;
|
|
|
|
// Could do a smarter search, but I'm expecting the set to be small.
|
|
foreach (KeyValuePair<int, LocalVariableTable> kvp in mLvTables) {
|
|
if (kvp.Key > offset) {
|
|
break;
|
|
}
|
|
nearest = kvp.Key;
|
|
if (mProject.GetAnattrib(nearest).IsStart) {
|
|
nearestUnhidden = nearest;
|
|
}
|
|
}
|
|
if (nearestUnhidden >= 0) {
|
|
return nearestUnhidden;
|
|
} else {
|
|
return nearest;
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Generates a list of variables defined at the specified offset, if a table is
|
|
/// associated with that offset.
|
|
/// </summary>
|
|
/// <param name="offset">File data offset.</param>
|
|
/// <returns>List of symbols, uniquified if desired, or null if no LocalVariableTable
|
|
/// exists at the specified offset.</returns>
|
|
public List<DefSymbol> GetVariablesDefinedAtOffset(int offset) {
|
|
AdvanceToOffset(offset);
|
|
|
|
if (mRecentOffset == offset) {
|
|
return mRecentSymbols;
|
|
}
|
|
return null;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Updates internal state to reflect the state of the world at the specified offset.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// When the offset is greater than or equal to its value on a previous call, we can
|
|
/// do an incremental update. If the offset moves backward, we have to reset and walk
|
|
/// forward again.
|
|
/// </remarks>
|
|
/// <param name="targetOffset">Target offset.</param>
|
|
private void AdvanceToOffset(int targetOffset) {
|
|
if (mNextLvtIndex < 0) {
|
|
return;
|
|
}
|
|
if (targetOffset < mRecentOffset) {
|
|
// We went backwards.
|
|
Reset(false);
|
|
}
|
|
while (mNextLvtOffset <= targetOffset) {
|
|
if (!mProject.GetAnattrib(mNextLvtOffset).IsStart) {
|
|
// Hidden table, ignore it.
|
|
Debug.WriteLine("Ignoring LvTable at +" + mNextLvtOffset.ToString("x6"));
|
|
} else {
|
|
// Process this table.
|
|
LocalVariableTable lvt = mLvTables.Values[mNextLvtIndex];
|
|
if (lvt.ClearPrevious) {
|
|
mCurrentTable.Clear();
|
|
}
|
|
|
|
// Create a list for GetVariablesDefinedAtOffset
|
|
mRecentSymbols = new List<DefSymbol>();
|
|
mRecentOffset = mNextLvtOffset;
|
|
|
|
// Merge the new entries into the work table. This automatically
|
|
// discards entries that clash by name or value.
|
|
for (int i = 0; i < lvt.Count; i++) {
|
|
DefSymbol defSym = lvt[i];
|
|
string newLabel = defSym.Label;
|
|
|
|
if (mMaskLeadingUnderscores && newLabel[0] == '_') {
|
|
newLabel = AsmGen.LabelLocalizer.NO_UNDER_PFX + newLabel;
|
|
}
|
|
|
|
// Look for non-variable symbols with the same label. Ordinarily the
|
|
// editor prevents this from happening, but there are ways to trick
|
|
// the system (e.g. add a symbol while the LvTable is hidden, or have
|
|
// a non-unique local promoted to global). We deal with it here.
|
|
//
|
|
// TODO(someday): this is not necessary for assemblers like Merlin 32
|
|
// that put variables in a separate namespace.
|
|
if (mAllNvSymbols.TryGetValue(newLabel, out Symbol unused)) {
|
|
Debug.WriteLine("Detected duplicate non-var label " + newLabel +
|
|
" at +" + mNextLvtOffset.ToString("x6"));
|
|
newLabel = GenerateDeDupLabel(newLabel);
|
|
}
|
|
|
|
if (newLabel != defSym.Label) {
|
|
mDupRemap[defSym.Label] = newLabel;
|
|
defSym = new DefSymbol(defSym, newLabel);
|
|
}
|
|
|
|
if (mDoUniquify) {
|
|
if (mUniqueLabels.TryGetValue(defSym.Label, out UniqueLabel ulab)) {
|
|
// We've seen this label before; generate a unique version by
|
|
// increasing the appended number.
|
|
ulab.MakeUnique(mAllNvSymbols);
|
|
defSym = new DefSymbol(defSym, ulab.Label);
|
|
} else {
|
|
// Haven't seen this before. Add it to the unique-labels table.
|
|
mUniqueLabels.Add(defSym.Label, new UniqueLabel(defSym.Label));
|
|
}
|
|
}
|
|
mCurrentTable.AddOrReplace(defSym);
|
|
|
|
mRecentSymbols.Add(defSym);
|
|
}
|
|
|
|
//mCurrentTable.DebugDump(mNextLvtOffset);
|
|
}
|
|
|
|
// Update state to look for next table.
|
|
mNextLvtIndex++;
|
|
if (mNextLvtIndex < mLvTables.Keys.Count) {
|
|
mNextLvtOffset = mLvTables.Keys[mNextLvtIndex];
|
|
} else {
|
|
mNextLvtOffset = mProject.FileDataLength; // never reached
|
|
}
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Generates a unique label for the duplicate remap table.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// We need to worry about clashes with the main symbol table, but we don't have to
|
|
/// worry about other entries in the remap table because we know their baseLabels
|
|
/// are different.
|
|
/// </remarks>
|
|
private string GenerateDeDupLabel(string baseLabel) {
|
|
string testLabel;
|
|
int counter = 0;
|
|
do {
|
|
counter++;
|
|
testLabel = baseLabel + "_DUP" + counter;
|
|
} while (mAllNvSymbols.TryGetValue(testLabel, out Symbol unused));
|
|
return testLabel;
|
|
}
|
|
|
|
public static bool IsTableHidden(int offset, DisasmProject project) {
|
|
return !project.GetAnattrib(offset).IsStart;
|
|
}
|
|
}
|
|
}
|