U E D R , A S I H C RSS

Gof/Visitor


1. Visitor

1.1. Intent

object structure 의 element듀에 μˆ˜ν–‰λ  operation 을 ν‘œν˜„ν•œλ‹€. VisitorλŠ” ν•΄λ‹Ή operation이 μˆ˜ν–‰λ˜λŠ” element의 class에 λŒ€ν•œ λ³€ν™” 없이 μƒˆλ‘œμš΄ operation을 μ •μ˜ν•  수 μžˆλ„λ‘ ν•΄μ€λ‹€.

1.2. Motivation

μ»΄νŒŒμΌλŸ¬κ°€ abstact syntax tree둜 ν”„λ‘œκ·Έλž¨μ„ ν‘œν˜„ν•œλ‹€κ³  ν•˜μž. μ»΄νŒŒμΌλŸ¬λŠ” λͺ¨λ“  λ³€μˆ˜λ“€μ΄ μ •μ˜κ°€ λ˜μ–΄μžˆλŠ” μ§€λΌ κ²€μ‚¬ν•˜λŠ” 것과 같은 '정적인 의λΈ' 뢄석을 μœ„ν•΄ abstract syntax tree에 λŒ€ν•΄ operation을 μˆ˜ν–‰ν•  ν•„μš”κ°€ μžˆμ„ 것이닀. μ»΄νŒŒμΌλŸ¬λŠ” λ˜ν•œ code λ³€ν™˜μ„ ν•  ν•„μš”κ°€ μžˆλ‹€. λ˜ν•œ μ»΄νŒŒμΌλŸ¬λŠ” type-checking, code optimization, flow analysis 와 ν•΄λ‹Ή λ³€μˆ˜κ°€ 이용되기 μ „ μ„ μ–Έλ˜μ—ˆλŠ”μ§€ λ“±μ˜ μ—¬λΆ€λΌ κ²€μ‚¬ν•˜κΈ° μœ„ν•΄μ„œ ν•΄λ‹Ή operations듀을 μˆ˜ν–‰ν•  ν•„μš”κ°€ μžˆλ‹€. 더 λ‚˜μ•„κ°€ μš°λ¦¬λŠ” pretty-printing, program restructuring, code instrumentation, 그리고 ν”„λ‘œκ·Έλž¨μ˜ λ‹€μ–‘ν•œ κΈ°μ€λ“€μ— λŒ€ν•œ 계산을 ν•˜κΈ° μœ„ν•΄ abstract syntax treeλΌ μ΄μš©ν•  것이닀.

μ΄λŸ¬ν•œ operationsλ“€μ˜ λŒ€λΆ€λΆ„λ“€μ€ variableλ“€μ΄λ‚˜ arithmetic expression듀을 ν‘œν˜„ν•˜λŠ” nodeλ“€κ³Ό λ‹€λ₯΄κ²Œ assignment statement듀을 ν‘œν˜„ν•˜λŠ” nodeλΌ μ·¨κΈ‰ν•  ν•„μš”κ°€ μžˆλ‹€. λ”°λΌμ„œ, 각각 assignment statement λΌ μœ„ν•œ ν΄λž˜μŠ€μ™€, variable 에 μ ‘κ·Ό ν•˜κΈ° μœ„ν•œ 클래슀, arithmetic expression을 μœ„ν•œ ν΄λž˜μŠ€λ“€μ΄ μžˆμ–΄μ•Ό ν•  것이닀. μ΄λŸ¬ν•œ node class듀은 컴파일 될 언어에 의쑴적이며, λ˜ν•œ 주어진 μ–Έμ–΄λΌ μœ„ν•΄ λ°”λ€Œμ§€ μ•ŠλŠ”λ‹€.


이 λ‹€μ΄μ–΄κ·Έλž¨μ€ Node class κ³„μΈ΅κ΅¬μ‘°μ˜ 일뢀뢄을 보여μ€λ‹€. μ—¬κΈ°μ„œμ˜ λ¬Έμ œλŠ” λ‹€μ–‘ν•œ node class듀에 μžˆλŠ” μ΄λŸ¬ν•œ operationλ“€μ˜ 뢄산은 μ‹œμŠ€ν…œμœΌλ‘œ ν•˜μ—¬κΈˆ μ΄ν•΄ν•˜κΈ° μ–΄λ ΅κ³ , μœ μ§€ν•˜κ±°λ‚˜ μ½”λ“œλΌ λ°”κΎΈκΈ° νž˜λ“€κ²Œ ν•œλ‹€. Node 에 type-checking μ½”λ“œκ°€ pretty-printing codeλ‚˜ flow analysis codeλ“€κ³Ό μ„žμ—¬ μžˆλŠ” 것은 ν˜Όλž€μŠ€λŸ½λ‹€. κ²Œλ‹€κ°€ μƒˆλ‘œμš΄ operation을 μΆ”κ°€ν•˜κΈ° μœ„ν•΄μ„œλŠ” 일반적으둜 이 ν΄λž˜μŠ€λ“€μ„ μž¬μ»΄νŒŒμΌν•΄μ•Ό ν•œλ‹€. 만일 각각의 μƒˆ operation이 λ…λ¦½μ μœΌλ‘œ 좔가될 수 있고, 이 node class듀이 operation듀에 λŒ€ν•΄ 독립적이라면 λ”μš± 쒋을 것이닀.

μš°λ¦¬λŠ” 각각의 ν΄λž˜μŠ€λ“€λ‘œλΆ€ν„° κ΄€λ ¨λœ operation듀을 νŒ¨ν‚€μ§•ν™” ν•˜κ³ , traverse 될 (tree 의 각 node듀을 이동) abstract syntax tree의 elementλ“€μ—κ²Œ 인자둜 λ„˜κ²¨μ„ μˆ˜ μžˆλ‹€. μ΄λΌ visitor라고 ν•œλ‹€. elementκ°€ visitorλΌ 'accepts' ν• λ•Œ elementλŠ” element의 ν΄λž˜μŠ€λΌ μΈμ½”λ”©ν•  visitorμ—κ²Œ requestλΌ λ³΄λ‚Έλ‹€. 이 request λ˜ν•œ ν•΄λ‹Ή elementλΌ μΈμžλ‘œ ν¬ν•¨ν•˜κ³  μžˆλ‹€. 그러면 visitorλŠ” ν•΄λ‹Ή element에 λŒ€ν•œ operation을 μˆ˜ν–‰ν•  것이닀.

예λΌλ“ λ‹€λ©΄, visitorλΌ μ΄μš©ν•˜μ§€ μ•ŠλŠ” μ»΄νŒŒμΌλŸ¬λŠ” 컴파일러의 abstact syntax tree의 TypeCheck operation을 ν˜ΈμΆœν•¨μœΌλ‘œμ„œ type-check 을 μˆ˜ν–‰ν•  것이닀. 각각의 node듀은 node듀이 가지고 μžˆλŠ” TypeCheckλΌ ν˜ΈμΆœν•¨μœΌλ‘œμ¨ TypeCheckλΌ κ΅¬ν˜„ν•  것이닀. (μ•žμ˜ class diagram μ°Έμ‘°). 만일 visitorλΌ μ΄μš©ν•œλ‹€λ©΄, TypeCheckingVisior κ°μ²΄λΌ λ§Œλ“  λ’€, TypeCheckingVisitor κ°μ²΄λΌ μΈμžλ‘œ λ„˜κ²¨μ£Όλ©΄μ„œ abstract syntax tree의 Accept operation을 ν˜ΈμΆœν•  것이닀. 각각의 node듀은 visitorλΌ λ„λ‘œ ν˜ΈμΆœν•¨μœΌλ‘œμ¨ AcceptλΌ κ΅¬ν˜„ν•  것이닀 (μ˜ˆλΌ λ“€μ–΄, assignment node의 경우 visitor의 VisitAssignment operation을 ν˜ΈμΆœν•  것이고, varible referenceλŠ” VisitVaribleReferenceλΌ ν˜ΈμΆœν•  것이닀.) AssignmentNode 클래슀의 TypeCheck operation은 이제 TypeCheckingVisitor의 VisitAssignment operation으둜 λŒ€μ²΄λ  것이닀.

type-checking 의 κΈ°λŠ₯을 λ„˜μ–΄ 일반적인 visitorλΌ λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” abstract syntax tree의 λͺ¨λ“  visitor듀을 μœ„ν•œ abstract parent class인 NodeVisitorκ°€ ν•„μš”ν•˜λ‹€. NodeVisitorλŠ” 각 node class듀에 μžˆλŠ” operation듀을 μ •μ˜ν•΄μ•Ό ν•œλ‹€. ν•΄λ‹Ή ν”„λ‘œκ·Έλž¨μ˜ κΈ°μ€ λ“±μ„ κ³„μ‚°ν•˜κΈ° μ›ν•˜λŠ” application은 node class 에 application-specificν•œ μ½”λ“œλΌ μΆ”κ°€ν•  ν•„μš” 없이, κ·Έλƒ₯ NodeVisitor에 λŒ€ν•œ μƒˆλ‘œμš΄ subclassλΌ μ •μ˜ν•˜λ©΄ λœλ‹€. VisitorPattern은 ν•΄λ‹Ή Visitor 와 μ—°κ΄€λœ λΆ€λΆ„μ—μ„œ 컴파일된 ꡬ문듀을 μœ„ν•œ operation듀을 μΊ‘μŠν™”ν•œλ‹€.



VisitorPattern으둜, κ°œλ°œμžλŠ” λ‘κ°œμ˜ 클래슀 계측을 μ •μ˜ν•œλ‹€. ν•˜λ‚˜λŠ” operation이 μˆ˜ν–‰λ  element에 λŒ€ν•œ 계측이고 (Node hierarchy), ν•˜λ‚˜λŠ” element에 λŒ€ν•œ operation듀을 μ •μ˜ν•˜λŠ” visitor듀이닀. (NodeVisitor hierarchy). κ°œλ°œμžλŠ” visitor hierarchy 에 μƒˆλ‘œμš΄ subclassλΌ μΆ”κ°€ν•¨μœΌλ‘œμ„œ μƒˆ operation을 λ§Œλ“€ 수 μžˆλ‹€.

1.3. Applicability

VisitorPattern은 λ‹€μŒκ³Ό κ°™μ€κ²½μš°μ— μ΄μš©ν•œλ‹€.


1.5. Participants

  • Visitor (NodeVisitor)
    - declares a Visit operations for each class of ConcreteElement in the object structure. The operation's name and signature identifies the class that sends the Visit request to the visitor. That lets the visitor determine the concrete class of the element being visited. Then the visitor can access the element directly through its particular interface.
  • ConcreteVisitor (TypeCheckingVisitor)
    - implements each operation declared by Visitor. Each operation implements a fragment of the algorithm defined for the corresponding class of object in the structure. ConcreteVisitor provides the context for the algorithm and stores its local state. This state often accumulates result during the traversal of the structure.
  • Element (Node)
    - defines an Accept operation that takes a visitor as an argument.
  • ConcreteElement (AssignmentNode, VariableRefNode)
    - implements an Accept operation that takes a visitor as an argument.
  • ObjectStructure (Program)
    - can enumerate its elements.

    - may provide a high-level interface to allow the visitor to visit its elements.

    - may either be a composite (See CompositePattern) or a collection such as a list or a set.


1.6. Collaborations

1.7. Consequences

template <class Item>
class Iterator {
	// ...
	Item CurrentItem () const;
};

class Visitor {
public:
	// ...
	void VisitMyType (MyType*);
	void VisitYourType (YourType*);
};

1.8. Implementation

class Visitor {
public:
	virtual void VisitElementA (ElementA*);
	virtual void VisitElementB (ElementB*);

	// and so on for other concrete elements
protected:
	Visitor ();
};

class Element {
public:
	virtual ~Element ();
	virtual void Accept (Visitor&) = 0;
protected:
	Element ();
};

class ElementA : public Element {
public:
	ElementA ();
	virtual void Accept (Visitor& v) { v.VisitElementA (this); }
};

class ElementB : public Element {
public:
	ElementB ();
	virtual void Accept (Visitor& v) { v.VisitElementB (this); }
};

class CompositeElement : public Element {
public:
	virtual void Accept (Visitor&);
private:
	List<Element*>* _children;
};

void CompositeElement::Accept (Visitor& v) {
	ListIterator<Element*> i (_children);

	for (i.First (); !i.IsDone(); i.Next ()) {
		i.CurrentItem ()->Accept (v);
	}
	v.VisitCompositeElement (this);
}

1.9. Sample Code


class Equipment {
public:
	virtual ~Equipment ();

	const char* Name () { return _name; } 
	
	virtual Watt Power ();
	virtual Currency NetPrice ();
	virtual Currency DiscountPrice ();

	virtual void Accept (EquipmentVisitor&);

protected:
	Equipment (const char*);
private:
	const char* _name;
};

class EquipmentVisitor {
public:
	virtual ~EquipmentVisitor ();

	virtual void VisitFloppyDisk (FloppyDisk*);
	virtual void VisitCard (Card*);
	virtual void VisitrChassis (Chassis*);
	virtual void VisitBus (Bus*);

	// and so on for other concrete subclasses of Equipment
protected:
	EquipmentVisitor ();
};

void FloppyDisk::Accept (EquipmentVisitor& visitor) {
	visitor.VisitFloppyDisk (this);
}

void Chassis::Accept (EquipmentVisitor& visitor) {
	for (ListIterator<Equipment*> i(_parts); !i.IsDone (); i.Next ()) {
		i.CurrentItem ()->Accept (visitor);
	}
	visitor.VisitChassis (this);
}

class PricingVisitor : public EquipmentVisitor {
public:
	PricingVisitor ();

	Currency& GetTotalPrice ();

	virtual void VisitFloppyDisk (FloppyDisk*);
	virtual void VisitCard (Card*);
	virtual void VisitChassis (Chassis*);
	virtual void VisitBus (Bus*);
	// ...
private:
	Currency _total;
};

void PricingVisitor::VisitFloppyDisk (FloppyDisk* e) {
	_total += e->NextPrice ();
}

void PricingVisitor::VisitChassis (Chassis* e) {
	_total += e->DiscountPrice ();
}

class InventoryVisitoy : public EquipmentVisitor {
public:
	InventoryVisitor ();

	Inventory& GetInventory ();

	virtual void VisitFloppyDisk (FloppyDisk*);
	virtual void VisitCard (Card*);
	virtual void VisitChassis (Chassis*);
	virtual void VisitBus (Bus*);
	// ...

private:
	Inventory _inventory;
};


void InventoryVisitor::VisitFloppyDisk (FloppyDisk* e) {
	_inventory.Accumulate (e);
}

void InventoryVisitor::VisitChassis (Chassis* e) {
	_inventory.Accumulate (e);
}

Equipment* component;
InventoryVisitor visitor;

component->Accept (visitor);
cout << "Inventory "
	<< componet->Name ()
	<< visitor.GetInventory ();


accept: aVisitor
	^ aVisitor visitSequence : self

visitSequence: sequenceExp
	inputState := sequenceExp expression1 accept: self.
	^ sequenceExp expression2 accept: self.

visitRepeat : repeatExp
	| finalState |
	finalState := inputState copy.
	[inputState isEmpty]
		whileFalse:
		[inputState := repeatExp repetition accept: self.
		finalState addAll: inputState].
	^ finalState

visitAlternation: alternateExp
	| finalState originalState |
	originalState := inputState.
	finalState := alternateExp alternative1 accept: self.
	inputState := originalState.
	finalState addAll: (alternateExp alternative2 accept: self).
	^ finalState

visitLiteral: literalExp
	| finalState tStream |
	finalState := Set new.
	inputState
		do:
			[:stream | tStream := stream copy.
				(tStream nextAvailable:
					literalExp components size
				) = literalExp components
					ifTrue: [finalState add: tStream]
			].
	^ finalState

1.10. Known Uses


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:19
Processing time 0.0289 sec